2003-06-07 18:32:54

by Arnaldo Carvalho de Melo

[permalink] [raw]
Subject: list.h: improve hlist

Hi Linus,

Please consider pulling from:

bk://kernel.bkbits.net/acme/hlist-2.5

I discussed this with Andi and he gave me an ACK to submit, please
let me know if you don't like anything and I'll be happy to fix it. The
hlist_for_each_entry is being used in my current work of converting net/
to use hlist_{head,node}.

Best Regards,

- Arnaldo

You can import this changeset into BK by piping this whole message to:
'| bk receive [path to repository]' or apply the patch as usual.

===================================================================


[email protected], 2003-06-07 14:22:10-03:00, [email protected]
o list.h: improve hlist

This changeset:

1. Implements hlist_add_after
2. uses prefetch in hlist_for_each, using a trick that ends up being
equivalent to having the prefetch instruction in the first block
of the hlist_for_each for block, the compiler optimizes the second
"test" away, as its result is constant
3. implements hlist_for_each_entry and hlist_for_each_entry safe,
using a struct hlist_node as iterator to avoid the extra branches a
similar implementation to list_for_each_entry would have if used
a typed iterator, but while avoiding having to have the explicit
hlist_entry as in hlist_for_each.

4. Converts the hlist_for_each users that had explicit prefetches, i.e.
removed the explicit prefetch

5. fix a harmless list_entry use in a hlist_for_each in inode.c



fs/dcache.c | 3 ---
fs/inode.c | 4 +---
include/linux/list.h | 35 ++++++++++++++++++++++++++++++++++-
3 files changed, 35 insertions(+), 7 deletions(-)


diff -Nru a/fs/dcache.c b/fs/dcache.c
--- a/fs/dcache.c Sat Jun 7 15:39:03 2003
+++ b/fs/dcache.c Sat Jun 7 15:39:03 2003
@@ -983,8 +983,6 @@
struct dentry *dentry;
unsigned long move_count;
struct qstr * qstr;
-
- prefetch(node->next);

smp_read_barrier_depends();
dentry = hlist_entry(node, struct dentry, d_hash);
@@ -1072,7 +1070,6 @@
spin_lock(&dcache_lock);
base = d_hash(dparent, dentry->d_name.hash);
hlist_for_each(lhp,base) {
- prefetch(lhp->next);
/* read_barrier_depends() not required for d_hash list
* as it is parsed under dcache_lock
*/
diff -Nru a/fs/inode.c b/fs/inode.c
--- a/fs/inode.c Sat Jun 7 15:39:03 2003
+++ b/fs/inode.c Sat Jun 7 15:39:03 2003
@@ -484,7 +484,6 @@

repeat:
hlist_for_each (node, head) {
- prefetch(node->next);
inode = hlist_entry(node, struct inode, i_hash);
if (inode->i_sb != sb)
continue;
@@ -510,8 +509,7 @@

repeat:
hlist_for_each (node, head) {
- prefetch(node->next);
- inode = list_entry(node, struct inode, i_hash);
+ inode = hlist_entry(node, struct inode, i_hash);
if (inode->i_ino != ino)
continue;
if (inode->i_sb != sb)
diff -Nru a/include/linux/list.h b/include/linux/list.h
--- a/include/linux/list.h Sat Jun 7 15:39:03 2003
+++ b/include/linux/list.h Sat Jun 7 15:39:03 2003
@@ -443,17 +443,50 @@
*(n->pprev) = n;
}

+static __inline__ void hlist_add_after(struct hlist_node *n,
+ struct hlist_node *next)
+{
+ next->next = n->next;
+ *(next->pprev) = n;
+ n->next = next;
+}
+
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

/* Cannot easily do prefetch unfortunately */
#define hlist_for_each(pos, head) \
- for (pos = (head)->first; pos; \
+ for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; n = pos ? pos->next : 0, pos; \
pos = n)

+/**
+ * hlist_for_each_entry - iterate over list of given type
+ * @tpos: the type * to use as a loop counter.
+ * @pos: the &struct hlist_node to use as a loop counter.
+ * @head: the head for your list.
+ * @member: the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry(tpos, pos, head, member) \
+ for (pos = (head)->first; \
+ pos && ({ prefetch(pos->next); 1;}) && \
+ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
+ pos = pos->next)
+/**
+ * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
+ * @tpos: the type * to use as a loop counter.
+ * @pos: the &struct hlist_node to use as a loop counter.
+ * @n: another &struct hlist_node to use as temporary storage
+ * @head: the head for your list.
+ * @member: the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
+ for (pos = (head)->first; \
+ pos && ({ n = pos->next; 1; }) && \
+ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
+ pos = n)
#else
#warning "don't include kernel headers in userspace"
#endif /* __KERNEL__ */

===================================================================


This BitKeeper patch contains the following changesets:
1.1320
## Wrapped with gzip_uu ##


M'XL( $<QXCX ^U9;6_;-A#^+/V*0PL4=F;+I%[\%KC(E@Q;L $KNO73.ABT
M1$5")-$3*:=9W?^^(VD[MN,F35!L_6#)D&3>\>[XW/$Y.7D)[R2OQPZ+2^Z^
MA)^%5&,G%A6/5;Y@7BQ*;U:CX*T0*.AEHN2]V74O*W*INKX7N2A[PU2<P8+7
M<NQ0+]B,J-LY'SMO?_SIW:_?OW7=R03.,U9=\=^Y@LG$5:)>L"*19TQEA:@\
M5;-*EEP9K\N-ZM(GQ,<SHH. 1/TE[9-PL(QI0BD+*4^('P[[H5LW4MV>Z6LL
MZKD)G#6[5@+2)P-]HW3IAR$-W0N@'@U\ B3HD7Z/#("&8]\?4](EP9@0T+"<
M[<,!WP70)>X/\'57<.[&($ #ZV5CR,MY+18<#-(HP<\?62XA-E8E5V,[2#VX
M+.<%+WFEI-6>LB29LE3Q&N6^!XWD$N8U3[G.2EZMM%)13SF+LPXJY-45,%!U
M'E^#RI@"7B42FCG,.(K0#![\[P8Q*- /+APRMM"35,:W34M5-PB5J+0;+4OS
M6BJ8%2*^ME9$:L9W0P!\L$H=(T7XYGG!:Q!SE9?Y/QB_'I8<4Y%8.R\4E^H%
ML!MVVP$F(<?5UUPVA0*-DL!06*6!"SR-Y2Y :[]3'*MO@57)88%D*>]8?VN,
M[ I7ZI5(N'7.:X;5H(%A"Y$G)ES^ 0L"9E@4<88K8-:0Q 45K+X+BAF\E$W]
M?@0WHBD2#3:'/-697"V?F=V5;#QW8-8HN,D0-1N!CG:=(V$-V)CF11[GREJQ
MJUB!(.^7AF=K+/3@7%2XP94\E#R,JI:V;#*6;%QLZH++#N0>]ZS/FI=8U\E.
M-!M5ZR_RL&X^X!HS5I<%EQ*VXD1O.E"V'T6N:P[SX<76C_L+^$$_&+IO[FC'
M[3[Q<%W"B/OZD9V>RM[*]?96'P7#)6YM.EK."!T&0YZ.2)+,^@$]3"M[9@Q;
M43P)789#GT9?$D82(Q0'XO )]?UE.F T(,,1BV(_B>/X\W%LV]D.A(["0?!H
M('D5%TW">T5>-1]ZEM%V(QHM?4J#:.E'<1+/(I(,_2CEGT7F<P:W0R.$1$/3
M9;;B?[S//!DTEUW/R[,DO^)"&_AS;?ZO^[A%?N3[- C\I1\$PY%I-]%@I]G0
MP9C0AYL-@6YP;#;'9G-L-M]TL['4^!MTZQOSP>;Q9IN*GM%[+D;#/OCN!26#
M".B:VU:.OXC:GM26'F2VG<YDB8WZ9!GY9#0PQ#9Z,K'1([$=B>U(;-\ZL=F7
MS_O$MM9[!J^%0^0(]R*B =+;941#_.8XQB!,MO%LZ:'.NEQR^RV?9DQF[5-#
MB(=>#1^GQN>_H;I/?4.-\ RB 7*EWQ]AA]!<&9"G<F400I<>R?)(ED>R_*;)
M$G^"[C'E(69X!F=>AF$$0U?JW,4PG>85&N33*9C<[VW"UOV2.:DZ2+&. _8X
MI(#%TW8_NHY^Z+[65V<"E7TZ=9V3EA7,$;E%6XMP<"5V]%>C]LE]C_P>$63T
M2WMS]$YKS85$:F]EG"7M[FNS1T]!#[YZ!:V/FVQH/6NR?0KT%#[A[;VVA"_"
MD=L[.7'AY.#&<;JKPN2 N:Y-^O3.O\H7O#*5JV>>*;0_=G0AZ"$<P4K5Z<52
M9% (,<=]W%1HR#/J&^U7]P%[>*9>J)VJGPS;W(K&QF4U2E[.])_>M4[%2K[+
M4\;%3:ZR%:M9_WIFSWV9\!23?Q"'EEYA!\Q%>^Z ]=/6N7__0#(<9Z5AZN/1
MS'QJHWPUPT$U96UN]VX3@X99I*T3+6]O@K$63G?<3>#.PT.9GFJ*A$?3;9@4
MV!73+<)2 "NTBE$UEO[;BJC&CL,J@7/KAR<K7LY%S70S0)IE5_Q_+2@#]W95
M57N%!<\LK&H[XZO-KD7.5ZZJJGWW3RKL#/&U;,H)932=D5GJ_@M\)<.9 1L
!