[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <1226675797.7685.7796.camel@twins>
Date: Fri, 14 Nov 2008 16:16:37 +0100
From: Peter Zijlstra <a.p.zijlstra@...llo.nl>
To: Eric Dumazet <dada1@...mosbay.com>
Cc: Corey Minyard <minyard@....org>,
"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
David Miller <davem@...emloft.net>,
Stephen Hemminger <shemminger@...tta.com>,
benny+usenet@...rsen.dk,
Linux Netdev List <netdev@...r.kernel.org>,
Christoph Lameter <cl@...ux-foundation.org>,
Evgeniy Polyakov <zbr@...emap.net>,
Christian Bell <christian@...i.com>
Subject: Re: [PATCH 1/3] rcu: Introduce hlist_nulls variant of hlist
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 <dada1@...mosbay.com>
Acked-by: Peter Zijlstra <a.p.zijlstra@...llo.nl>
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists