Skip to contentSkip to conversation

neigh: Force garbage collection if an entry is deleted administratively

PATCH In review Steffen Klassert 3 participants 8 messages Nov 12, 2013 – Nov 21, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 neigh: Force garbage collection if an entry is deleted administratively

Since git commit 2724680 ("neigh: Keep neighbour cache entries if number of them is small enough."), we keep all neighbour cache entries if the number is below a threshold. But if we now delete an entry administratively and then try to replace this by a permanent one, we get -EEXIST because the old entry ist still in the table (in NUD_FAILED state).

So lets force a garbage collect if we delete an entry administratively.

---
 net/core/neighbour.c |    2 ++
 1 file changed, 2 insertions(+)
net/core/neighbour.c +2 -0
index 6072610..ec20880 100644
@@ -1659,6 +1659,8 @@ static int neigh_delete(struct sk_buff *skb, struct nlmsghdr *nlh)
 				   NEIGH_UPDATE_F_OVERRIDE |
 				   NEIGH_UPDATE_F_ADMIN);
 		neigh_release(neigh);
+
+		neigh_forced_gc(tbl);
 		goto out;
 	}
 	read_unlock(&neigh_tbl_lock);
Signature · 1 line
1.7.9.5
maintainer
#1 lore raw

From: Steffen Klassert <[email protected]>
Date: Tue, 12 Nov 2013 09:57:14 +0100

Quoted 9 lines

Since git commit 2724680 ("neigh: Keep neighbour cache entries if number of them is small enough."), we keep all neighbour cache entries if the number is below a threshold. But if we now delete an entry administratively and then try to replace this by a permanent one, we get -EEXIST because the old entry ist still in the table (in NUD_FAILED state).

So lets force a garbage collect if we delete an entry administratively.

I don't think this is a sufficient fix.

If some entity refers to this entry (refcnt != 1) then the forced GC won't do anything, and this is very much possible.

It is the difficult situation mentioned in a comment in neigh_flush_dev() below the "refcnt != 1" test there.

#2 lore raw
Quoted 9 lines · David Miller

From: Steffen Klassert <[email protected]>
Date: Tue, 12 Nov 2013 09:57:14 +0100

Quoted 6 lines

Since git commit 2724680 ("neigh: Keep neighbour cache entries if number of them is small enough."), we keep all neighbour cache entries if the number is below a threshold. But if we now delete an entry administratively and then try to replace this by a permanent one, we get -EEXIST because the old entry ist still in the table (in NUD_FAILED state).

Quoted 5 lines
Quoted 3 lines

So lets force a garbage collect if we delete an entry administratively.

I don't think this is a sufficient fix.

Yes, looks like that.

Quoted 6 lines

If some entity refers to this entry (refcnt != 1) then the forced GC won't do anything, and this is very much possible.

It is the difficult situation mentioned in a comment in neigh_flush_dev() below the "refcnt != 1" test there.

We ensured that an entry will go away if the refcount got to 1 by cyclic garbage collecting. Now we do this only if the cached entries are above a threshold, so we have to handle this somehow different if the cached entries are below this threshold.

Currently we do cyclic rescheduling of the gc worker but the worker exits immediately if cached entries are below the threshold. I'm testing an approach where we schedule the gc worker only if the entries are above the threshold or if there is an administrative change.

The patch I'm testing is below. It is pure RFC at the moment, but I would be grateful for comments on the approach.

Subject: [PATCH RFC] neigh: Fix garbage collection if the cached entries are
below the threshold

Since git commit 2724680 ("neigh: Keep neighbour cache entries if number of them is small enough."), we keep all neighbour cache entries if the number is below a threshold. But if we now delete an entry administratively and then try to replace this by a permanent one, we get -EEXIST because the old entry ist still in the table (in NUD_FAILED state).

So remove the threshold check in neigh_periodic_work() and schedule the gc_work only when needed, i.e. if gc_thresh1 is reached or if there is an administrative change. We reschedule gc_work either if the number of cache entries is still above gc_thresh1 or if there are invalid entries with "refcnt != 1" cached.

---
 net/core/neighbour.c |   29 ++++++++++++++++++++---------
 1 file changed, 20 insertions(+), 9 deletions(-)
net/core/neighbour.c +20 -9
index ca15f32..39c2a24 100644
@@ -239,6 +239,9 @@ static void neigh_flush_dev(struct neigh_table *tbl, struct net_device *dev)
 				else
 					n->nud_state = NUD_NONE;
 				neigh_dbg(2, "neigh %p is stray\n", n);
+				schedule_delayed_work(&tbl->gc_work,
+						      tbl->parms.base_reachable_time >> 1);
+
 			}
 			write_unlock(&n->lock);
 			neigh_cleanup_and_release(n);
@@ -282,6 +285,9 @@ static struct neighbour *neigh_alloc(struct neigh_table *tbl, struct net_device
 			goto out_entries;
 	}
 
+	if (entries >= tbl->gc_thresh1)
+		schedule_delayed_work(&tbl->gc_work, 0);
+
 	n = kzalloc(tbl->entry_size + dev->neigh_priv_len, GFP_ATOMIC);
 	if (!n)
 		goto out_entries;
@@ -757,6 +763,7 @@ static void neigh_periodic_work(struct work_struct *work)
 	struct neighbour __rcu **np;
 	unsigned int i;
 	struct neigh_hash_table *nht;
+	bool schedule = false;
 
 	NEIGH_CACHE_STAT_INC(tbl, periodic_gc_runs);
 
@@ -764,9 +771,6 @@ static void neigh_periodic_work(struct work_struct *work)
 	nht = rcu_dereference_protected(tbl->nht,
 					lockdep_is_held(&tbl->lock));
 
-	if (atomic_read(&tbl->entries) < tbl->gc_thresh1)
-		goto out;
-
 	/*
 	 *	periodically recompute ReachableTime from random function
 	 */
@@ -785,6 +789,7 @@ static void neigh_periodic_work(struct work_struct *work)
 		while ((n = rcu_dereference_protected(*np,
 				lockdep_is_held(&tbl->lock))) != NULL) {
 			unsigned int state;
+			int refcnt;
 
 			write_lock(&n->lock);
 
@@ -797,7 +802,8 @@ static void neigh_periodic_work(struct work_struct *work)
 			if (time_before(n->used, n->confirmed))
 				n->used = n->confirmed;
 
-			if (atomic_read(&n->refcnt) == 1 &&
+			refcnt = atomic_read(&n->refcnt);
+			if (refcnt == 1 &&
 			    (state == NUD_FAILED ||
 			     time_after(jiffies, n->used + n->parms->gc_staletime))) {
 				*np = n->next;
@@ -805,7 +811,8 @@ static void neigh_periodic_work(struct work_struct *work)
 				write_unlock(&n->lock);
 				neigh_cleanup_and_release(n);
 				continue;
-			}
+			} else if (refcnt != 1 && !(state & NUD_VALID))
+				schedule = true;
 			write_unlock(&n->lock);
 
 next_elt:
@@ -821,13 +828,15 @@ next_elt:
 		nht = rcu_dereference_protected(tbl->nht,
 						lockdep_is_held(&tbl->lock));
 	}
-out:
-	/* Cycle through all hash buckets every base_reachable_time/2 ticks.
+
+	/* Cycle through all hash buckets every base_reachable_time/2 ticks
+	 * as long as we have more than gc_thresh1 entries cached.
 	 * ARP entry timeouts range from 1/2 base_reachable_time to 3/2
 	 * base_reachable_time.
 	 */
-	schedule_delayed_work(&tbl->gc_work,
-			      tbl->parms.base_reachable_time >> 1);
+	if (schedule == true || atomic_read(&tbl->entries) >= tbl->gc_thresh1)
+		schedule_delayed_work(&tbl->gc_work,
+				      tbl->parms.base_reachable_time >> 1);
 	write_unlock_bh(&tbl->lock);
 }
 
@@ -1659,6 +1668,8 @@ static int neigh_delete(struct sk_buff *skb, struct nlmsghdr *nlh)
 				   NEIGH_UPDATE_F_OVERRIDE |
 				   NEIGH_UPDATE_F_ADMIN);
 		neigh_release(neigh);
+
+		schedule_delayed_work(&tbl->gc_work, 0);
 		goto out;
 	}
 	read_unlock(&neigh_tbl_lock);
Signature · 1 line
1.7.9.5
maintainer
#3 lore raw

From: Steffen Klassert <[email protected]>
Date: Mon, 18 Nov 2013 11:08:43 +0100

Quoted 9 lines

Subject: [PATCH RFC] neigh: Fix garbage collection if the cached entries are
below the threshold

Since git commit 2724680 ("neigh: Keep neighbour cache entries if number of them is small enough."), we keep all neighbour cache entries if the number is below a threshold. But if we now delete an entry administratively and then try to replace this by a permanent one, we get -EEXIST because the old entry ist still in the table (in NUD_FAILED state).

Quoted 7 lines

So remove the threshold check in neigh_periodic_work() and schedule the gc_work only when needed, i.e. if gc_thresh1 is reached or if there is an administrative change. We reschedule gc_work either if the number of cache entries is still above gc_thresh1 or if there are invalid entries with "refcnt != 1" cached.

I think the main issue is that after this patch, the problem is really still there.

Let's say some device holds onto the neigh for a long time, then during this time an administrative replacement will still get that -EEXIST failure.

My conclusion is that the management of the state is the problem. Specifically, if we invalidate an entry then we should remove it's visisbility. This means the table should operate by unhashing the entry unconditionally during such operations.

If some stray references exist, that's fine, the entity holding the reference will perform the final neigh cleanup at release time.

Does this make sense to you?

#4 lore raw
Quoted 7 lines · David Miller

I think the main issue is that after this patch, the problem is really still there.

Let's say some device holds onto the neigh for a long time, then during this time an administrative replacement will still get that -EEXIST failure.

Well, I think we had this problem even before we stopped to do cyclic garbage collecting. This patch would just restore the behaviour we had before this change.

Quoted 10 lines

My conclusion is that the management of the state is the problem. Specifically, if we invalidate an entry then we should remove it's visisbility. This means the table should operate by unhashing the entry unconditionally during such operations.

If some stray references exist, that's fine, the entity holding the reference will perform the final neigh cleanup at release time.

Does this make sense to you?

Yes, makes sense :-)

I'm not sure how invasive this will be, so maybe we should do one patch to restore the old behaviour (for net) and one on top of this to improve the situation as you described (for net-next).

#5 lore raw
Quoted 11 lines
Quoted 9 lines

My conclusion is that the management of the state is the problem. Specifically, if we invalidate an entry then we should remove it's visisbility. This means the table should operate by unhashing the entry unconditionally during such operations.

If some stray references exist, that's fine, the entity holding the reference will perform the final neigh cleanup at release time.

Does this make sense to you?

Yes, makes sense :-)

Isn't it enough to act as if the entry were not in the hash tables. So an attempt to add such an entry wouldn't fail.

I've not looked at these code paths, but it can easily be that when the entry is invalidated the hash table isn't (and can't easily be) locked - just having the entry locked may make it difficult.

Whereas the code path to add an entry can easily delete old entries.

David

#6 lore raw
Quoted 8 lines · David Laight
Quoted 8 lines
Quoted 8 lines

My conclusion is that the management of the state is the problem. Specifically, if we invalidate an entry then we should remove it's visisbility. This means the table should operate by unhashing the entry unconditionally during such operations.

If some stray references exist, that's fine, the entity holding the reference will perform the final neigh cleanup at release time.

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

Does this make sense to you?

Yes, makes sense :-)

Isn't it enough to act as if the entry were not in the hash tables. So an attempt to add such an entry wouldn't fail.

Hm, how you want to do that?

Quoted 5 lines

I've not looked at these code paths, but it can easily be that when the entry is invalidated the hash table isn't (and can't easily be) locked - just having the entry locked may make it difficult.

We have the table locked in neigh_periodic_work() so we can unlink invalidated entries there. This function could then periodically check and remove the unlinked entries if they lost their references. Unlinking with neigh_periodic_work() would have some seconds delay of course, but I think this is acceptable.

Quoted 2 lines

Whereas the code path to add an entry can easily delete old entries.

Well, it can not if the old entry is still referenced. That's why we need to look periodically for stale entries and remove them when they lost their references.

maintainer
#7 lore raw

From: Steffen Klassert <[email protected]>
Date: Tue, 19 Nov 2013 13:41:02 +0100

Quoted 5 lines

We have the table locked in neigh_periodic_work() so we can unlink invalidated entries there. This function could then periodically check and remove the unlinked entries if they lost their references. Unlinking with neigh_periodic_work() would have some seconds delay of course, but I think this is acceptable.

Create an "invalidated_list", and at the moment the neigh is administratively deleted you can remove it from the hash table and link it into this new list.

Then neigh_periodic_work() can scan both the hash tables and this "invalidated_list" for refcnt==1 entries.

It seems a good solution, and should avoid the need to handle forcibly freeing a neigh which still has external references.