| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20241008073855.811502-1-gnaaman@drivenets.com>
Date: Tue, 8 Oct 2024 07:38:55 +0000
From: Gilad Naaman <gnaaman@...venets.com>
To: kuniyu@...zon.com
Cc: davem@...emloft.net,
edumazet@...gle.com,
gnaaman@...venets.com,
kuba@...nel.org,
netdev@...r.kernel.org,
pabeni@...hat.com
Subject: Re: [PATCH net-next v2 1/2] Convert neighbour-table to use hlist
Thank you for reviewing this
> > Use doubly-linked instead of singly-linked list when linking neighbours,
> > so that it is possible to remove neighbours without traversing the
> > entire table.
> >
> > Signed-off-by: Gilad Naaman <gnaaman@...venets.com>
> > ---
> > include/net/neighbour.h | 8 +--
> > net/core/neighbour.c | 124 ++++++++++++++--------------------------
> > 2 files changed, 46 insertions(+), 86 deletions(-)
> >
> > diff --git a/include/net/neighbour.h b/include/net/neighbour.h
> > index a44f262a7384..5dde118323e3 100644
> > --- a/include/net/neighbour.h
> > +++ b/include/net/neighbour.h
> > @@ -135,7 +135,7 @@ struct neigh_statistics {
> > #define NEIGH_CACHE_STAT_INC(tbl, field) this_cpu_inc((tbl)->stats->field)
> >
> > struct neighbour {
> > - struct neighbour __rcu *next;
> > + struct hlist_node list;
> > struct neigh_table *tbl;
> > struct neigh_parms *parms;
> > unsigned long confirmed;
> > @@ -190,7 +190,7 @@ struct pneigh_entry {
> > #define NEIGH_NUM_HASH_RND 4
> >
> > struct neigh_hash_table {
> > - struct neighbour __rcu **hash_buckets;
> > + struct hlist_head *hash_buckets;
> > unsigned int hash_shift;
> > __u32 hash_rnd[NEIGH_NUM_HASH_RND];
> > struct rcu_head rcu;
> > @@ -304,9 +304,9 @@ static inline struct neighbour *___neigh_lookup_noref(
> > u32 hash_val;
> >
> > hash_val = hash(pkey, dev, nht->hash_rnd) >> (32 - nht->hash_shift);
> > - for (n = rcu_dereference(nht->hash_buckets[hash_val]);
> > + for (n = (struct neighbour *)rcu_dereference(hlist_first_rcu(&nht->hash_buckets[hash_val]));
>
> This for loop and hlist_first_rcu(&nht->hash_buckets[hash_val])
> can also be written with a macro and an inline function.
Good point, I'll convert all of these to use `neigh_{first,next}_rcu{,protected}`.
>
> > n != NULL;
> > - n = rcu_dereference(n->next)) {
> > + n = (struct neighbour *)rcu_dereference(hlist_next_rcu(&n->list))) {
>
> This part is also reused multiple times so should be an inline function.
>
> I have similar patches for struct in_ifaddr.ifa_next (not upstreamed yet),
> and this will be a good example for you.
> https://github.com/q2ven/linux/commit/a51fdf7ccc14bf6edba58bacf7faaeebe811d41b
>
>
> > if (n->dev == dev && key_eq(n, pkey))
> > return n;
> > }
> > diff --git a/net/core/neighbour.c b/net/core/neighbour.c
> > index 77b819cd995b..86b174baae27 100644
> > --- a/net/core/neighbour.c
> > +++ b/net/core/neighbour.c
> > @@ -37,6 +37,7 @@
> > #include <linux/string.h>
> > #include <linux/log2.h>
> > #include <linux/inetdevice.h>
> > +#include <linux/rculist.h>
> > #include <net/addrconf.h>
> >
> > #include <trace/events/neigh.h>
> > @@ -205,18 +206,13 @@ static void neigh_update_flags(struct neighbour *neigh, u32 flags, int *notify,
> > }
> > }
> >
> > -static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
> > - struct neigh_table *tbl)
> > +static bool neigh_del(struct neighbour *n, struct neigh_table *tbl)
> > {
> > bool retval = false;
> >
> > write_lock(&n->lock);
> > if (refcount_read(&n->refcnt) == 1) {
> > - struct neighbour *neigh;
> > -
> > - neigh = rcu_dereference_protected(n->next,
> > - lockdep_is_held(&tbl->lock));
> > - rcu_assign_pointer(*np, neigh);
> > + hlist_del_rcu(&n->list);
> > neigh_mark_dead(n);
> > retval = true;
> > }
> > @@ -228,25 +224,7 @@ static bool neigh_del(struct neighbour *n, struct neighbour __rcu **np,
> >
> > bool neigh_remove_one(struct neighbour *ndel, struct neigh_table *tbl)
> > {
> > - struct neigh_hash_table *nht;
> > - void *pkey = ndel->primary_key;
> > - u32 hash_val;
> > - struct neighbour *n;
> > - struct neighbour __rcu **np;
> > -
> > - nht = rcu_dereference_protected(tbl->nht,
> > - lockdep_is_held(&tbl->lock));
> > - hash_val = tbl->hash(pkey, ndel->dev, nht->hash_rnd);
> > - hash_val = hash_val >> (32 - nht->hash_shift);
> > -
> > - np = &nht->hash_buckets[hash_val];
> > - while ((n = rcu_dereference_protected(*np,
> > - lockdep_is_held(&tbl->lock)))) {
> > - if (n == ndel)
> > - return neigh_del(n, np, tbl);
> > - np = &n->next;
> > - }
> > - return false;
> > + return neigh_del(ndel, tbl);
> > }
> >
> > static int neigh_forced_gc(struct neigh_table *tbl)
> > @@ -388,21 +366,20 @@ static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev,
> >
> > for (i = 0; i < (1 << nht->hash_shift); i++) {
> > struct neighbour *n;
> > - struct neighbour __rcu **np = &nht->hash_buckets[i];
> > + struct neighbour __rcu **np =
> > + (struct neighbour __rcu **)&nht->hash_buckets[i].first;
>
> This will be no longer needed for doubly linked list,
This is not as-necessary with a doubly-linked list, but unfortunately
I cannot eliminate it completely, as the `n` might be released in the loop
body.
I can convert this function to use a `struct neighour *next` instead,
if it is more palatable.
>
> >
> > while ((n = rcu_dereference_protected(*np,
> > lockdep_is_held(&tbl->lock))) != NULL) {
>
> and this while can be converted to the for-loop macro.
As far as I understand, this cannot be converted into the for-loop macro,
as the cursor can be released during the loop-body, resulting in use-after-free
when trying to increment it.
>
> > if (dev && n->dev != dev) {
> > - np = &n->next;
> > + np = (struct neighbour __rcu **)&n->list.next;
> > continue;
> > }
> > if (skip_perm && n->nud_state & NUD_PERMANENT) {
> > - np = &n->next;
> > + np = (struct neighbour __rcu **)&n->list.next;
> > continue;
> > }
> > - rcu_assign_pointer(*np,
> > - rcu_dereference_protected(n->next,
> > - lockdep_is_held(&tbl->lock)));
> > + hlist_del_rcu(&n->list);
> > write_lock(&n->lock);
> > neigh_del_timer(n);
> > neigh_mark_dead(n);
== SNIP ==
>
> > + hlist_del_rcu(&n->list);
> > + hlist_add_head_rcu(&n->list, &new_nht->hash_buckets[hash]);
> > }
> > }
> >
> > @@ -693,11 +666,10 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
> > goto out_tbl_unlock;
> > }
> >
> > - for (n1 = rcu_dereference_protected(nht->hash_buckets[hash_val],
> > - lockdep_is_held(&tbl->lock));
> > - n1 != NULL;
> > - n1 = rcu_dereference_protected(n1->next,
> > - lockdep_is_held(&tbl->lock))) {
> > + hlist_for_each_entry_rcu(n1,
> > + &nht->hash_buckets[hash_val],
> > + list,
> > + lockdep_is_held(&tbl->lock)) {
>
> Let's define hlist_for_each_entry_rcu() as neigh-specific macro.
Can you elaborate on this?
Do you want the `list` parameter to be eliminated?
>
> > if (dev == n1->dev && !memcmp(n1->primary_key, n->primary_key, key_len)) {
> > if (want_ref)
> > neigh_hold(n1);
> > @@ -713,10 +685,7 @@ ___neigh_create(struct neigh_table *tbl, const void *pkey,
> > list_add_tail(&n->managed_list, &n->tbl->managed_list);
> > if (want_ref)
> > neigh_hold(n);
> > - rcu_assign_pointer(n->next,
> > - rcu_dereference_protected(nht->hash_buckets[hash_val],
> > - lockdep_is_held(&tbl->lock)));
> > - rcu_assign_pointer(nht->hash_buckets[hash_val], n);
> > + hlist_add_head_rcu(&n->list, &nht->hash_buckets[hash_val]);
> > write_unlock_bh(&tbl->lock);
> > neigh_dbg(2, "neigh %p is created\n", n);
> > rc = n;
> > @@ -976,7 +945,7 @@ static void neigh_periodic_work(struct work_struct *work)
> > goto out;
> >
> > for (i = 0 ; i < (1 << nht->hash_shift); i++) {
> > - np = &nht->hash_buckets[i];
> > + np = (struct neighbour __rcu **)&nht->hash_buckets[i].first;
>
> No np here too,
Same as the other loop in `neigh_flush_dev`, we must keep `np` in order to avoid
UAF, because `n` might be freed in the loop body.
Powered by blists - more mailing lists