From mboxrd@z Thu Jan 1 00:00:00 1970 From: Peter Zijlstra Subject: Re: [PATCH 1/3] rcu: Introduce hlist_nulls variant of hlist Date: Fri, 14 Nov 2008 16:16:37 +0100 Message-ID: <1226675797.7685.7796.camel@twins> References: <4908627C.6030001@acm.org> <490874F2.2060306@cosmosbay.com> <49088288.6050805@acm.org> <49088AD1.7040805@cosmosbay.com> <20081029163739.GB6732@linux.vnet.ibm.com> <49089BE5.3090705@acm.org> <4908A134.4040705@cosmosbay.com> <4908AB3F.1060003@acm.org> <20081029185200.GE6732@linux.vnet.ibm.com> <4908C0CD.5050406@cosmosbay.com> <20081029201759.GF6732@linux.vnet.ibm.com> <4908DEDE.5030706@cosmosbay.com> <4909D551.9080309@cosmosbay.com> <491C282A.5050802@cosmosbay.com> Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit Cc: Corey Minyard , "Paul E. McKenney" , David Miller , Stephen Hemminger , benny+usenet@amorsen.dk, Linux Netdev List , Christoph Lameter , Evgeniy Polyakov , Christian Bell To: Eric Dumazet Return-path: Received: from viefep18-int.chello.at ([213.46.255.22]:11146 "EHLO viefep18-int.chello.at" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751159AbYKNPc2 (ORCPT ); Fri, 14 Nov 2008 10:32:28 -0500 In-Reply-To: <491C282A.5050802@cosmosbay.com> Sender: netdev-owner@vger.kernel.org List-ID: On Thu, 2008-11-13 at 14:14 +0100, Eric Dumazet wrote: > hlist uses NULL value to finish a chain. > > hlist_nulls variant use the low order bit set to 1 to signal an end-of-list marker. > > This allows to store many different end markers, so that some RCU lockless > algos (used in TCP/UDP stack for example) can save some memory barriers in > fast paths. > > Two new files are added : > > include/linux/list_nulls.h > - mimics hlist part of include/linux/list.h, derived to hlist_nulls variant > > include/linux/rculist_nulls.h > - mimics hlist part of include/linux/rculist.h, derived to hlist_nulls variant > > Only four helpers are declared for the moment : > > hlist_nulls_del_init_rcu(), hlist_nulls_del_rcu(), > hlist_nulls_add_head_rcu() and hlist_nulls_for_each_entry_rcu() > > prefetches() were removed, since an end of list is not anymore NULL value. > prefetches() could trigger useless (and possibly dangerous) memory transactions. > > Example of use (extracted from __udp4_lib_lookup()) > > struct sock *sk, *result; > struct hlist_nulls_node *node; > unsigned short hnum = ntohs(dport); > unsigned int hash = udp_hashfn(net, hnum); > struct udp_hslot *hslot = &udptable->hash[hash]; > int score, badness; > > rcu_read_lock(); > begin: > result = NULL; > badness = -1; > sk_nulls_for_each_rcu(sk, node, &hslot->head) { > score = compute_score(sk, net, saddr, hnum, sport, > daddr, dport, dif); > if (score > badness) { > result = sk; > badness = score; > } > } > /* > * if the nulls value we got at the end of this lookup is > * not the expected one, we must restart lookup. > * We probably met an item that was moved to another chain. > */ > if (get_nulls_value(node) != hash) > goto begin; > > if (result) { > if (unlikely(!atomic_inc_not_zero(&result->sk_refcnt))) > result = NULL; > else if (unlikely(compute_score(result, net, saddr, hnum, sport, > daddr, dport, dif) < badness)) { > sock_put(result); > goto begin; > } > } > rcu_read_unlock(); > return result; > > Signed-off-by: Eric Dumazet Acked-by: Peter Zijlstra