[PATCH] ext2/namei.c lookup performance patch

Sang-yong Suh (sysuh@kigam.re.kr)
Mon, 9 Aug 1999 15:27:37 +0900 (GMT+0900)


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/