Skip to contentSkip to conversation

neighbor: Improve garbage collection

PATCH In review David Ahern 5 participants 6 messages Dec 7, 2018 – Dec 10, 2018

Subsystems (3)
Networking Network drivers Documentation
lore
Share & tools
lore

David Ahern

author
#0 lore raw

PATCH v2 1/1 neighbor: Improve garbage collection

From: David Ahern <[email protected]>

The existing garbage collection algorithm has a number of problems:

1. The gc algorithm will not evict PERMANENT entries as those entries are managed by userspace, yet the existing algorithm walks the entire hash table which means it always considers PERMANENT entries when looking for entries to evict. In some use cases (e.g., EVPN) there can be tens of thousands of PERMANENT entries leading to wasted CPU cycles when gc kicks in. As an example, with 32k permanent entries, neigh_alloc has been observed taking more than 4 msec per invocation.

2. Currently, when the number of neighbor entries hits gc_thresh2 and the last flush for the table was more than 5 seconds ago gc kicks in walks the entire hash table evicting *all* entries not in PERMANENT or REACHABLE state and not marked as externally learned. There is no discriminator on when the neigh entry was created or if it just moved from REACHABLE to another NUD_VALID state (e.g., NUD_STALE).

It is possible for entries to be created or for established neighbor entries to be moved to STALE (e.g., an external node sends an ARP request) right before the 5 second window lapses:

-----|---------x|----------|-----
t-5 t t+5

If that happens those entries are evicted during gc causing unnecessary thrashing on neighbor entries and userspace caches trying to track them.

Further, this contradicts the description of gc_thresh2 which says "Entries older than 5 seconds will be cleared".

One workaround is to make gc_thresh2 == gc_thresh3 but that negates the whole point of having separate thresholds.

3. Clearing *all* neigh non-PERMANENT/REACHABLE/externally learned entries when gc_thresh2 is exceeded is over kill and contributes to trashing especially during startup.

This patch addresses these problems as follows:

1. Use of a separate list_head to track entries that can be garbage collected along with a separate counter. PERMANENT entries are not added to this list.

The gc_thresh parameters are only compared to the new counter, not the total entries in the table. The forced_gc function is updated to only walk this new gc_list looking for entries to evict.

2. Entries are added to the list head at the tail and removed from the front.

3. Entries are only evicted if they were last updated more than 5 seconds ago, adhering to the original intent of gc_thresh2.

4. Forced gc is stopped once the number of gc_entries drops below gc_thresh2.

5. Since gc checks do not apply to PERMANENT entries, gc levels are skipped when allocating a new neighbor for a PERMANENT entry. By extension this means there are no explicit limits on the number of PERMANENT entries that can be created, but this is no different than FIB entries or FDB entries.

Signed-off-by David Ahern <[email protected]>

---
v2
- remove on_gc_list boolean in favor of !list_empty
- fix neigh_alloc to add new entry to tail of list_head

 Documentation/networking/ip-sysctl.txt |   4 +-
 include/net/neighbour.h                |   3 +
 net/core/neighbour.c                   | 119 +++++++++++++++++++++++----------
 3 files changed, 90 insertions(+), 36 deletions(-)
Documentation/networking/ip-sysctl.txt +2 -2
index af2a69439b93..acdfb5d2bcaa 100644
@@ -108,8 +108,8 @@ neigh/default/gc_thresh2 - INTEGER
 	Default: 512
 
 neigh/default/gc_thresh3 - INTEGER
-	Maximum number of neighbor entries allowed.  Increase this
-	when using large numbers of interfaces and when communicating
+	Maximum number of non-PERMANENT neighbor entries allowed.  Increase
+	this when using large numbers of interfaces and when communicating
 	with large numbers of directly-connected peers.
 	Default: 1024
include/net/neighbour.h +3 -0
index f58b384aa6c9..6c13072910ab 100644
@@ -154,6 +154,7 @@ struct neighbour {
 	struct hh_cache		hh;
 	int			(*output)(struct neighbour *, struct sk_buff *);
 	const struct neigh_ops	*ops;
+	struct list_head	gc_list;
 	struct rcu_head		rcu;
 	struct net_device	*dev;
 	u8			primary_key[0];

@@ -214,6 +215,8 @@ struct neigh_table {
 	struct timer_list 	proxy_timer;
 	struct sk_buff_head	proxy_queue;
 	atomic_t		entries;
+	atomic_t		gc_entries;
+	struct list_head	gc_list;
 	rwlock_t		lock;
 	unsigned long		last_rand;
 	struct neigh_statistics	__percpu *stats;
net/core/neighbour.c +85 -34

228 lines not on this page · raw message

Signature · 1 line
2.11.0
maintainer
#1 lore raw

From: David Ahern <[email protected]>
Date: Fri, 7 Dec 2018 12:24:57 -0800

Quoted 3 lines

From: David Ahern <[email protected]>

The existing garbage collection algorithm has a number of problems:

...

Quoted 25 lines

This patch addresses these problems as follows:

1. Use of a separate list_head to track entries that can be garbage collected along with a separate counter. PERMANENT entries are not added to this list.

The gc_thresh parameters are only compared to the new counter, not the total entries in the table. The forced_gc function is updated to only walk this new gc_list looking for entries to evict.

2. Entries are added to the list head at the tail and removed from the front.

3. Entries are only evicted if they were last updated more than 5 seconds ago, adhering to the original intent of gc_thresh2.

4. Forced gc is stopped once the number of gc_entries drops below gc_thresh2.

5. Since gc checks do not apply to PERMANENT entries, gc levels are skipped when allocating a new neighbor for a PERMANENT entry. By extension this means there are no explicit limits on the number of PERMANENT entries that can be created, but this is no different than FIB entries or FDB entries.

Quoted 5 lines
Signed-off-by David Ahern <[email protected]>

---
v2
- remove on_gc_list boolean in favor of !list_empty
- fix neigh_alloc to add new entry to tail of list_head

Again, looks great, applied.

#2 lore raw
Quoted 32 lines · David Miller

From: David Ahern <[email protected]>
Date: Fri, 7 Dec 2018 12:24:57 -0800

Quoted 3 lines

From: David Ahern <[email protected]>

The existing garbage collection algorithm has a number of problems:

...

Quoted 25 lines

This patch addresses these problems as follows:

1. Use of a separate list_head to track entries that can be garbage collected along with a separate counter. PERMANENT entries are not added to this list.

The gc_thresh parameters are only compared to the new counter, not the total entries in the table. The forced_gc function is updated to only walk this new gc_list looking for entries to evict.

2. Entries are added to the list head at the tail and removed from the front.

3. Entries are only evicted if they were last updated more than 5 seconds ago, adhering to the original intent of gc_thresh2.

4. Forced gc is stopped once the number of gc_entries drops below gc_thresh2.

5. Since gc checks do not apply to PERMANENT entries, gc levels are skipped when allocating a new neighbor for a PERMANENT entry. By extension this means there are no explicit limits on the number of PERMANENT entries that can be created, but this is no different than FIB entries or FDB entries.

Quoted 8 lines
Quoted 5 lines
Signed-off-by David Ahern <[email protected]>

---
v2
- remove on_gc_list boolean in favor of !list_empty
- fix neigh_alloc to add new entry to tail of list_head

Again, looks great, applied.

What protects gc_list linkage ?

We can not use list_del_init(&n->gc_list); or

               list_add_tail(&n->gc_list, &n->tbl->gc_list);

if tbl->lock is not held.

It seems to me this patch needs more care.

#3 lore raw
Quoted 9 lines · Eric Dumazet

What protects gc_list linkage ?

We can not use list_del_init(&n->gc_list); or

               list_add_tail(&n->gc_list, &n->tbl->gc_list);

if tbl->lock is not held.

It seems to me this patch needs more care.

I am playing with a LOCKDEP assist :

net/core/neighbour.c +6 -1
index c3b58712e98b9157ca717951da40eb5ae2fe810b..213e56a3816918e599f9a658bcb851711c578f7b 100644
@@ -122,6 +122,7 @@ static void neigh_mark_dead(struct neighbour *n)
 {
        n->dead = 1;
        if (!list_empty(&n->gc_list)) {
+               WARN_ON_ONCE(debug_locks && !lockdep_is_held(&n->tbl->lock));
                list_del_init(&n->gc_list);
                atomic_dec(&n->tbl->gc_entries);
        }

@@ -138,10 +139,12 @@ static void neigh_change_state(struct neighbour *n, u8 new)
         * add to the gc list if new state is not permanent
         */
        if (new_is_perm && on_gc_list) {
+               WARN_ON_ONCE(debug_locks && !lockdep_is_held(&n->tbl->lock));
                list_del_init(&n->gc_list);
                atomic_dec(&n->tbl->gc_entries);
        } else if (!new_is_perm && !on_gc_list) {
                /* add entries to the tail; cleaning removes from the front */
+               WARN_ON_ONCE(debug_locks && !lockdep_is_held(&n->tbl->lock));
                list_add_tail(&n->gc_list, &n->tbl->gc_list);
                atomic_inc(&n->tbl->gc_entries);
        }

@@ -391,8 +394,10 @@ static struct neighbour *neigh_alloc(struct neigh_table *tbl,
        refcount_set(&n->refcnt, 1);
        n->dead           = 1;
 
-       if (!permanent)
+       if (!permanent) {
+               WARN_ON_ONCE(debug_locks && !lockdep_is_held(&n->tbl->lock));
                list_add_tail(&n->gc_list, &n->tbl->gc_list);
+       }
        else
                INIT_LIST_HEAD(&n->gc_list);
#4 lore raw
In reply to Eric Dumazet
Quoted 44 lines · Eric Dumazet
Quoted 32 lines · David Miller

From: David Ahern <[email protected]>
Date: Fri, 7 Dec 2018 12:24:57 -0800

Quoted 3 lines

From: David Ahern <[email protected]>

The existing garbage collection algorithm has a number of problems:

...

Quoted 25 lines

This patch addresses these problems as follows:

1. Use of a separate list_head to track entries that can be garbage collected along with a separate counter. PERMANENT entries are not added to this list.

The gc_thresh parameters are only compared to the new counter, not the total entries in the table. The forced_gc function is updated to only walk this new gc_list looking for entries to evict.

2. Entries are added to the list head at the tail and removed from the front.

3. Entries are only evicted if they were last updated more than 5 seconds ago, adhering to the original intent of gc_thresh2.

4. Forced gc is stopped once the number of gc_entries drops below gc_thresh2.

5. Since gc checks do not apply to PERMANENT entries, gc levels are skipped when allocating a new neighbor for a PERMANENT entry. By extension this means there are no explicit limits on the number of PERMANENT entries that can be created, but this is no different than FIB entries or FDB entries.

Quoted 8 lines
Quoted 5 lines
Signed-off-by David Ahern <[email protected]>

---
v2
- remove on_gc_list boolean in favor of !list_empty
- fix neigh_alloc to add new entry to tail of list_head

Again, looks great, applied.

Quoted 9 lines

What protects gc_list linkage ?

We can not use list_del_init(&n->gc_list); or

               list_add_tail(&n->gc_list, &n->tbl->gc_list);

if tbl->lock is not held.

It seems to me this patch needs more care.

This seems to be problematic in neigh_create() which uses neigh_alloc() before grabbing the lock (which uses list_add_tail()), as seen in the syzbot traces:
-> KASAN: use-after-free Read in ___neigh_create
[email protected]
-> KASAN: slab-out-of-bounds Read in ___neigh_create
[email protected]
-> BUG: corrupted list in ___neigh_create
[email protected]

#5 lore raw
In reply to Eric Dumazet
Quoted 1 line · Eric Dumazet

What protects gc_list linkage ?

Yes, I found this yesterday morning as well: the list_add_tail in neigh_alloc needs to be moved to ___neigh_create. Internet to our lab has been knocked out for a while now; I will send a patch when I can.