Messages in this thread | | | Date | Mon, 9 Aug 1999 15:27:37 +0900 (GMT+0900) | From | Sang-yong Suh <> | Subject | [PATCH] ext2/namei.c lookup performance patch |
| |
It looks like that ext2_find_entry() is one of the most frequently referenced functions and affects the system performance. Therefore, I browsed the source code and found a little spot, i.e., When sys_unlink() does directory look up, it calls ext2_find_entry() if the target is not dcached. Getting the dentry, it checks the permission, and calls ext2_unlink(). However, the function ext2_unlink() calls ext2_find_entry() once again.
Because the target is linearly searched, it is not effective to searching the same file from the start of the directory. If the "offset" of the "de" is remembered in the dentry struct, the next lookup can directly jump to the right block and right offset.
Fortunately, there is a good field in the dentry, i.e., d_fsdata. It is initialized to NULL whenever the dentry is newly allocated. However, the current ext2 code never uses this field. Therefore we can save the "modified offset" there. We save the offset in a modified form to distinguish offset 0 and uninitialized offset NULL.
Due to this change, synopsys of ext2_find_entry() and ext2_add_entry() are changed to use dentry directly. Also, a new function ext2_has_entry() is added.
The lookup statitistics can be generated by defining EXT2_LOOKUP_STATS. The following is an example of the statitics on my personal news server.
Aug 9 13:43:49 news kernel: ext2_de_stats: lookup 2653 hit 680 found 856 miss 1117 init 1079 del 697 Aug 9 13:48:49 news kernel: ext2_de_stats: lookup 2582 hit 650 found 904 miss 1028 init 1006 del 666 Aug 9 13:53:49 news kernel: ext2_de_stats: lookup 3126 hit 756 found 1071 miss 1299 init 1265 del 776
The number "lookup" is the total number of lookups during the collecting period, 5 minutes. "hit" is the cache hit, meaning the remembered offset in the dentry is used to locate the ext2_dentry_2. The number "found " is the total number of existing file loops, while the number "miss" is that of the non-existing file lookups. The number "init" is the number of newly created directory entries, and the number "del" is the number of deleted files.
I made a diff against kernel-2.2.10. The patch updates only one file linux/fs/ext2.namei.c. -- Sang-yong Suh, Group Leader, Seismic Data Processing Lab. Korea Institute of Geology Mining and Materials (KIGAM) 30 Gajeong-dong, Yuseong-gu, Taejeon, Korea 305-350 Tel: 82+42-868-3400 Fax: 82+42-861-9720 Email: sysuh@kigam.re.kr
begin 644 ext2-lookup.patch.gz M'XL("$UKKC< V5X=#(M;&]O:W5P+G!A=&-H .4\^W?:QIH_T[]BXMZD8(0- MXNW$V>,DI/4VL7ML9]M[TQX= 8-1#1*K1USO3?9OW^\Q(XU @)UKI^G=G(2 M9N:;[_V:@=W=7>&[<^GMC?:"T+LLO0X]\=:]$8V6:+0/[/9!NR<:_7[_FUJM MIF>6W@:^.$HNA>C#O(-F^Z#9Y4F[^3_X632LEJ /" $^M 6\J7TCQ/[N-U48 M$7\['A]HT-8'T=BSFP1MO][;K_=%'=#HX@[1391,Q>"/A7KW-UR^#R_PEV ) M\5,8_"Y'<70@SA=2CD6R$&,OA"=!>"-F07"5+/9X@1#',3V)Q,R[DB*>NK&0 M?\2V,_'\L2/].+PI5X07B<"7(IC !"GF012+22C_.X'QV0V!">5$AM(?P6Z3 MQ!_%'O#&]<?"G4P0$UH'^,9R+A8RG 3AW(7)>[3V8@I+X9&TQ+$8AL%U!%!H M09"$(RE&P5@2L$F0($A -8YG,+P(8DMX>W+/TG!P#R?Q9YY_!6B/ QDM40Z\ ML,3UU!M-Q:7T9>C.9C=B!*\1@2@@G6F.W?!2QL@(/XC%>.2.IG*\!^S+#<L_ MO"B.&!LO%C!G=,6T ]%S+XJ +1:10EOR=AI=9L:+BY\M6I&R,3=)N)>NYYO+ M36Q3J;Z0(S>)Y!+J $*Z(1 <P7](@(58*IHD2<K[ L"@L&3//^290&:*28> ML'T2!G-^!)!CK10IFYD,Q9>=8#*)9+RC9^V,Y0YN&,JYG ]![&,!U-!Z(@%@ MALDH9@[B8Q]H5"H+1/MJ&R#A]V2^ $QI$ECL-!;#63"Z(N;R9]XZ9<GK((P3 MWXWE[(88'$I$Q!6700":Y<G9$BI*L\38F41C-W;WM+G *L_W8L^=>?^#BAJ( MDW=OWH!2@3Y]D*%)#;)67@.V(*Y@!'N/&<H/P35.94&/DA LA\V.=!T7(2 0 M("H/ "'T]@Q+(2C7DE@2N1]8T#OS8.S!U+'07"<R8=W/,IO%8TBK2U#216B4 M2,T8=!BDGGC15$^N$UL3WZ1;#2'M*8]?)9)E CB/IJY_"28=W?C! LP256#5 MO! N/77'Z4,"Y8)\& 2Q&)59,56K -!U-(L"L"=D\I*]3-TH!PY%/1XS_U-G MH?0*]#@&NH#J440<'4KE'$!@8@@[2L 9#6'PRX7MO#D]_?'=3\[YQ='%>>K M@'L@XFN<A%LA%NY\,4M]IMIC%*4(Z,C1/&C!WS[2$(DK&?IR=L TC*6#R\"- M*T3M3KLIIF"RG5Y=.<->NT/0[O8'79%H-!I=TF31J'?[0.1,=/K=%>1ZMT6N MW;,9N;9&KE]O?39R=;NGD:MW&+E.9QFY]FTYUVS8'4*NV^XHY(#HQF=C9_?[ M"CN0"6'7[7;R@1CF[@ITN<D?^Y-H'_':5^&=QGC"RV!QP^ZJ_+*"\=ZV\+5) MKRUZ;1?F$\V>U6IF&46W;P&C=$[Q+6FL%"=';P?'SMF1\^+-Z<L?SX5H%0V> M'_]CH,DKIT]?_O#N!);L+@.I%($X/GDU^*4\LH85 %$NCRH%ZT15E(<5-$>U MO$3F=/KZ]?G@PGE]=OK6>7W^ZNCBJ.Q62N5RXD?>I0\&. O\RPH\$Y W&:N% MN?KB5*\-)A&N!M<1BMT*?82-:>'RSJ8AXY@W@='B(7/+B^.W@]-W%\Y_'K]^ M?3PX+Y7*3>#\KOCA'[A):7\7]"'G6MBQ?'!GH><.9^#324M*-#82.3IAJ<-+ MGY80TK?H/U)PVU:"@O,R2D](WS<O($O@)>Q;V32&.DO<LAQM0>;6N\,(0]GF M96@X^65F7('-TUBP!1#8G21(*2#U9-,ZS"B<W[T)Q+R(5F+@QA 3R@6D"+ST M6^E#5$2=$8)S=++6D].+P2.!N=@5NO30'\TAG227,W=CR"E#&2>A#PX"HZF( MDM%(1I$EZO1QXGJS!.)QH3VW;0MJ#/HH1*G$@$3]*7Z"'+3\:"QKSST?TH/* MTH1'0G]X!$D58%1&-P.)"RS@=S/I5Q#0IY0:*D+JX#.Z#>TS[KHG3D#P[VLU M@/^;>'28[O@>'U1P4B&:9<1'_,=&=,6!:.":3_ /_@+*CU *[$=G_*0*R(/ M(B[G,I ^8:Y=D'/L40ZG$F L:R [PP!-V2-#BA9RQ&!T0JA30"'^'B1BGD0J MMZ=1,&QO[,4W9*IJ)@,:4JY&R3JGT9C*J31ECZ;LPZO24LY\Q3"!/#QTIM(= MK] KRFH2R02&(16RB,WPA]RW&E>9TJY.98OF<*#T0@;MV%B#AC+"1\C6?^(: M\J(H%%CSWFYW?B,Q*@!1 D6-PUDW,&UHCN6I&$[-L=6-QY(URE=)/)A4&-*C M4> 3K]&9(Q[I//P >D*?\_;->:F%M,1/67M*NXHP<4CY*F,SA$_P##3<4<@K MH/B<<*L]'SOX;$_OI'4>)SWG:(!1SGDS.!$?/Z;0P(^)9X>B7E'^(-L4%Z^" MUY3A#)56'XIUP3%;RZI623%32Y\?FHA46)*E10ALNRK_.#@[<09G9V(GKUH' MH%.DR#JO?SQ+$ P3\W@V_M7?46JD&6QN0CB4EE$SV5U:9@5:=HFUYU!O^EPQ ME3(&RDN<%\<7Y^5HR#L,IS"7$!^&H%IEU'^M,G5+/ &UR=CQ:#A=%0!J1;9? M#3(2PN#9L[4;,\ QBJV\5H,K &A:>SYTB.PJ*5^&B<Y& $A5:RXJ2&Y)-*P] MC]B<D*7$LR=/C."B-<\2VF%6<I/((V5HE9<DO$,2PV7 LJFE6%#1^F&8B#)' M+3%EO2RO4,XB";0R<>C %S=EY2$T8@K/2JKQZ#W4P]\ _G>_UK^CL:TZ"<58 M+-!WB\>1H9BI+J8;*V((*H1TI<M0OV6-"NVI]EF<ZS4UIS)FT"P*VQT;\FY; MQVVQFV8 5-E3&L:^$&,)]YUPA/WSM1MQQL4]H72 (7EQ)&>@/2YV*19N"+3& M *>6>ND]C&34XX*\1*!!$ @.#EQW,B3>K29N@N2[V4Q,J14 A7[ _3YX'-)6 MH*OP'M "KL?!'BW>_T9LCU!9>-T>HDR7KCZPVAANW:)TXRX!2X :BPVA2:P- M34X2R?>Y6NBWC=.1SROS:\51B#.I+*S% :X&4E6$(\U:C4ZB*#IMB3^5(B>+ MD,!&T6S*3"GY2?0OH!_J485RPQ+C!KMR_H<):UF[Y_I3U5U[EJ\:GXIJE08J MS/[UX5\0_NP--[I<03YW.8BQ!J'3OR+LC$AP*>/A[$JLB04\EV1,8^A_&!]& M!N" _WRD$$X6<8!> QT<I[PE+7%F3[5J /BDJ,JS2CLC9IMZ_\RD1C&S6KT% MUTKKLR;RTSA#V=)XYLV]6"N5R>K'J[7X(6"'E#-9&I'2;.:$U\IPRF>#HU>9 MSBI&*)[FU(6JB6[;LELM74W\FWG"*I89^(*S(WVHPE4$-=%U0SLR>ZRJ]Z<; MO&/)();:S)I@AB:N/4!L*"]A5MIIWS$BV X#80YBGS68+Q*L>=/9NO'](.Y[ M787Q%W/8F_URM:CRJ"Y5'M5U/E]/5 2116YL+V'*$GMS4&FC7\0M#%6&JZ80 M-9A*9@<##%"_JQ:VIP@=3-I0I\MZ+KA7$PK:?W6I2'@U>/'N>WBZ4]Q1A9* M&DSX/W>-\!UU1Q_348H:P]ZH+A]PBU)*C*5:5E;:B;*RII*5-8HLH]53(7(R M&)2M(A!^PX@<9F#X/</A][I#1([K\[CY"5]2%*K5IV;#B"2V4J,I_JYU])O5 MH\0T+N]D!,&L):)R?'8MVMJ8TGW<2T33( &YX)'?4/+1E3N[=F^TQJFPF)9. MC!X%NUMF*ENJW(<NLS\SYP$:M<5BJ6=NLJ$LI>;R R=,# E-5N%7$7^)3$CQ MX%GJ"!\\[T'U3;.OK97]TR^=)Q7>"ZGWK$:CE75^.8;N9-<6OL56#(2CV/5\ M3("FP4P*-S;JX1W+6*D4%P*X418+[39J60='5 ^7FPX*9]S,\Q/UD2R_=.UZ ML1/XCLKAN 6 B9_=KEMV6UUG*:30[EJ-9M.@T*-DR"%S5]EJKD\BEALE+&*0 M Z<B2*;1="]HC*2"0J>GKXWP[%K&J]^QD0L)'?C!*,'K)Y 'NF*20 +&[5U* MGTH*NT<;NBQ9!@6R(*YT>I;=;67-]7LF^FNCN5#P35!M\Y#2[O8MN]<WF,)% M'68GRC&_]W[3EJ,4;Z4U5=4T7DFY2)-KMD4_P21\Z4Z)BFN%_<EUAXC*;K;$ M98K,Q.I<;&:TC?A)#Q0Y@/@BE!\09T@@%G@P@'>EQ!"\1-JB*F1G"]C9[AIV MM*TIJ1!94C%6PHHV[AKK8B8&U<PEW52.L9J/8I6MQ3M!,+P1%_$JC)C9 Z6F MQL":0+:,@1G82+/Z+:M9-\ZR[H<W:QE3B%0N1#\0L86*T>Y;C8YQ>/BOAW-2 M"G5>>9!F-QY'=:\HJ_$J2]S*67-13Q7EUJPWK6;#<)/WD8G<%]Z;C3^M,99- MOXC60K%UVU:CUTC%EB\<=$*\VN<S3F('9V?.3Q=GY=H AR].3]^<GGQ?T<EC MIF-F@6\4"+G4?.4A19<G8UE1U7) )I4JLRX3..CD*V&8#%-GLFD[<>",%DDY M.TEF@VW:#:MI=U/!?WGB'X:V(D';=<B0LA0/FTBZOV4)-Q)1,)=XO98T<$Z7 M@:@QE6 !"QG ]12O76(_*IK)Q5T:.]E%BFU]G5Q7?G,_?GMW)S<=P>RB\](M MG[6-\G0 2M006VHC1U>$GW6L3$==^-K8?&RMNO" (PBV-C@^^:\C5H.5<I<T MM]6QFAW;:'1^7=(LW:)#][6(</O% M?ULN/&PZ%"JP'<CV[VXNZT) ;'<NV M&UE"V^Q VM&U5Z[0K&V.<(VZ]O2QNKEW4MW6.]'W=O0);"%.:TXR[19XJ8Y9 MB"Z=MBOON?VHWA(-ZJ/J1%X?QN?SXBPK8N>?;^JH##PM:9:G'%+?1X]F$CTY M'9Q<Z *B8*LLX85LC!N;P^12E'=&0")>>^8;YZ1>O_H[&*T$%\W;KP!DQ_EZ MLS0RI,=JZJ$R# HDC8X.)$O5>%H(Y0C7 EBY,9";G>P1AMZ>YTQF[F4DGAR* M_V6!79P-!L[KE"%S-[QR"$FD)Z8.HM[Y$WNQ?Z[A673E+:B @7KR'MGVR<B^ MUQ:A0E6AJ5-<NM_ ]MEO6*U&W2@+OH1.5V]3?ZR2_66MX"XF\&^FS'?4Y'O4 MR4*_V^E:=J]G^EVSXJ0G*Q+\E%:BM^V#I;HQ^.7X/-6-U:V*]DK;I,59;]HD M-<5O* :=YJ?O/WXD>'39?-,"DN^KXS/G;/ 2<_^ROB#*,ZHIQ KYIY+9UEP' MU["T8E+T;2A4[,:V&U^YUH%.OS:CK5H(!-XT', "D4&\US.E=NL]BFS3W.+6 M "C/:.0;6$5^P%P/CXU\2PWB-\><^&8ALQL#K4;3:C6[IG/^/,7_?ZSWMU9G MS((]L0WZT\]4?N']*XJ-W^SP'D!IN4.;>04OU6,5H>^[&YP>-:]V@^_#:(JB M1]/N6<U6=KBRR#<R[IJ%<'%:QDX9CYA7B+?&/3Y;3T,?8F$)H\N@KYYZ%76A M2]D<%&*GV6'<F/(:#-S"U/"%_A9""8DTE$2G.>M4;9&SL*J>3I:84TE,-5*= M5&+(.K8J<5F28>X[$]IE; Y!Y/NZ7:O5[Z2^[R'%MK^+7X?P)C?J]A.= 7^ M2.JCGE6F5],4]^[BKA:*NVKZV$S>7Z=D;V'GZAK)JJ%_AD(4VG77MIK=+"LD M[#!O#O#.RQ/5V)Q)E>P&"_RVJA?XT=/<[#G3A/_QQ8CE_%CW+7,=4Z/1=.=N ML7G?(+V%SV:<8D7?9:_5F$5K44([:=MMJ]W,SG6^ C;<,Y5%PF_5>U"VME:% MGWAXDT =>4)\B.#!9DKS#$OON#^<K(G:RP#JJ"")'3]@X,JK95:6FG33+J<X MPALM]T[#:G>ZJW+_8AQX0 *+1-ZNMZQVHYX_#.)*F0AZ(LZ=X_/OCU]5\DI& M@Q\/]>B?:.3W(_A.NVMU.LW\N="?P(<O+/Y.O6EUZOU4_-LN/^$<B#0?W)G9 M[[GW,[\5FB'0.>$<P!$2],7S=L?J9L<A#XCY'1 K9+%M6QV[:WQEOMNVNKTL MMB@UTU\=/135*EW32'=DM(LWW=35UZJHCCY8%S$Q:F34')\[YW\_>4G]*AU) M<I?,?CX[OAA0%_()%:V%)+9;8#SUOX06\0_:I&K4@Y#7,RX"_(EJ9&!6R.0N M,+G;S_2H!R58KYFAGJ*UDB1CFHTI<66S2FD$MNC41GV]L\(5D=IMU:UNJ[.: MAZCFK;?9S2X?Q'^=$:?7;UO]>D&*>9]$?N%PTNV!X'J=7#:1STO33M.;XY,? MG;='O^3."FN#M_C\"XE0;:J_$8="Z3=!**U&+@UX0 +NA%\1PWO-)OB -'[C MLF V=FA?7U[S&_1CN0MA]'UO/6W%9^$(GT[AFR)&%PPPLWF@HH][X15_B^8E MW>_$&U&L5OJR9"1 \6)'C/G7FQ9!%'G#F13'ITAS$$9[&L+/^D8#13WC-]HL MOHSIQ7@#8G&-WR*GBQ!B$0;X$Q@LU%[/ZO=31_E03/HJZ2]4FE;'ZK6-B]%9 M4B'YP)^9A+S1C@#?9R*GI_R="LV_%0[1"N10?FFF1JI!5S#,RL0#F5WP5FFY M2_<--(9I3UHWV-5D]1W!>KV!/U-D]/R_%,GW1D>A("$EZ/5LXPBO@"SN!:7; M\,[T)?8<'8:#NJWDMHDNG?=$I1M/\Q2GQ]C%6+/D(,EIU)OFA?:'HC'#6WP> MPH4BZC>L7K]C_ 1GO=4$BEK&;73>-=]V9T]B/*,]\%]!=L>3V1>1LE39=6W( 3XK03W%I\Y%3S_P"4GP<WL%0 '3> end
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |