[Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Zhang Changzhong]

Hi,

We got the following weird neighbor cache entry on a machine that's been running for over a year:
172.16.1.18 dev bond0 lladdr 0a:0e:0f:01:12:01 ref 1 used 350521/15994171/350520 probes 4 REACHABLE

350520 seconds have elapsed since this entry was last updated, but it is still in the REACHABLE
state (base_reachable_time_ms is 30000), preventing lladdr from being updated through probe.

After some analysis, we found a scenario that may cause such a neighbor entry:

          Entry used          	  DELAY_PROBE_TIME expired
NUD_STALE ------------> NUD_DELAY ------------------------> NUD_PROBE
                            |
                            | DELAY_PROBE_TIME not expired
                            v
                      NUD_REACHABLE

The neigh_timer_handler() use time_before_eq() to compare 'now' with 'neigh->confirmed +
NEIGH_VAR(neigh->parms, DELAY_PROBE_TIME)', but time_before_eq() only works if delta < ULONG_MAX/2.

This means that if an entry stays in the NUD_STALE state for more than ULONG_MAX/2 ticks, it enters
the NUD_RACHABLE state directly when it is used again and cannot be switched to the NUD_STALE state
(the timer is set too long).

On 64-bit machines, ULONG_MAX/2 ticks are a extremely long time, but in my case (32-bit machine and
kernel compiled with CONFIG_HZ=250), ULONG_MAX/2 ticks are about 99.42 days, which is possible in
reality.

Does anyone have a good idea to solve this problem? Or are there other scenarios that might cause
such a neighbor entry?

-----
Best Regards,
Changzhong Zhang

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Julian Anastasov]

	Hello,

On Sun, 29 Jan 2023, Zhang Changzhong wrote:

> Hi,
> 
> We got the following weird neighbor cache entry on a machine that's been running for over a year:
> 172.16.1.18 dev bond0 lladdr 0a:0e:0f:01:12:01 ref 1 used 350521/15994171/350520 probes 4 REACHABLE

	confirmed time (15994171) is 13 days in the future, more likely
185 days behind (very outdated), anything above 99 days is invalid

> 350520 seconds have elapsed since this entry was last updated, but it is still in the REACHABLE
> state (base_reachable_time_ms is 30000), preventing lladdr from being updated through probe.
> 
> After some analysis, we found a scenario that may cause such a neighbor entry:
> 
>           Entry used          	  DELAY_PROBE_TIME expired
> NUD_STALE ------------> NUD_DELAY ------------------------> NUD_PROBE
>                             |
>                             | DELAY_PROBE_TIME not expired
>                             v
>                       NUD_REACHABLE
> 
> The neigh_timer_handler() use time_before_eq() to compare 'now' with 'neigh->confirmed +
> NEIGH_VAR(neigh->parms, DELAY_PROBE_TIME)', but time_before_eq() only works if delta < ULONG_MAX/2.
> 
> This means that if an entry stays in the NUD_STALE state for more than ULONG_MAX/2 ticks, it enters
> the NUD_RACHABLE state directly when it is used again and cannot be switched to the NUD_STALE state
> (the timer is set too long).
> 
> On 64-bit machines, ULONG_MAX/2 ticks are a extremely long time, but in my case (32-bit machine and
> kernel compiled with CONFIG_HZ=250), ULONG_MAX/2 ticks are about 99.42 days, which is possible in
> reality.
> 
> Does anyone have a good idea to solve this problem? Or are there other scenarios that might cause
> such a neighbor entry?

	Is the neigh entry modified somehow, for example,
with 'arp -s' or 'ip neigh change' ? Or is bond0 reconfigured
after initial setup? I mean, 4 days ago?

	Looking at __neigh_update, there are few cases that
can assign NUD_STALE without touching neigh->confirmed:
lladdr = neigh->ha should be called, NEIGH_UPDATE_F_ADMIN
should be provided. Later, as you explain, it can wrongly
switch to NUD_REACHABLE state for long time.

	May be there should be some measures to keep
neigh->confirmed valid during admin modifications.

	What is the kernel version?

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Zhang Changzhong]

On 2023/1/30 3:43, Julian Anastasov wrote:
> 
> 	Hello,
> 
> On Sun, 29 Jan 2023, Zhang Changzhong wrote:
> 
>> Hi,
>>
>> We got the following weird neighbor cache entry on a machine that's been running for over a year:
>> 172.16.1.18 dev bond0 lladdr 0a:0e:0f:01:12:01 ref 1 used 350521/15994171/350520 probes 4 REACHABLE
> 
> 	confirmed time (15994171) is 13 days in the future, more likely
> 185 days behind (very outdated), anything above 99 days is invalid
> 
>> 350520 seconds have elapsed since this entry was last updated, but it is still in the REACHABLE
>> state (base_reachable_time_ms is 30000), preventing lladdr from being updated through probe.
>>
>> After some analysis, we found a scenario that may cause such a neighbor entry:
>>
>>           Entry used          	  DELAY_PROBE_TIME expired
>> NUD_STALE ------------> NUD_DELAY ------------------------> NUD_PROBE
>>                             |
>>                             | DELAY_PROBE_TIME not expired
>>                             v
>>                       NUD_REACHABLE
>>
>> The neigh_timer_handler() use time_before_eq() to compare 'now' with 'neigh->confirmed +
>> NEIGH_VAR(neigh->parms, DELAY_PROBE_TIME)', but time_before_eq() only works if delta < ULONG_MAX/2.
>>
>> This means that if an entry stays in the NUD_STALE state for more than ULONG_MAX/2 ticks, it enters
>> the NUD_RACHABLE state directly when it is used again and cannot be switched to the NUD_STALE state
>> (the timer is set too long).
>>
>> On 64-bit machines, ULONG_MAX/2 ticks are a extremely long time, but in my case (32-bit machine and
>> kernel compiled with CONFIG_HZ=250), ULONG_MAX/2 ticks are about 99.42 days, which is possible in
>> reality.
>>
>> Does anyone have a good idea to solve this problem? Or are there other scenarios that might cause
>> such a neighbor entry?
> 
> 	Is the neigh entry modified somehow, for example,
> with 'arp -s' or 'ip neigh change' ? Or is bond0 reconfigured
> after initial setup? I mean, 4 days ago?>

So far, we haven't found any user-space program that modifies the neigh
entry or bond0.

In fact, the neigh entry has been rarely used since initialization.
4 days ago, our machine just needed to download files from 172.16.1.18.
However, the laddr has changed, and the neigh entry wrongly switched to
NUD_REACHABLE state, causing the laddr to fail to update.

> 	Looking at __neigh_update, there are few cases that
> can assign NUD_STALE without touching neigh->confirmed:
> lladdr = neigh->ha should be called, NEIGH_UPDATE_F_ADMIN
> should be provided. Later, as you explain, it can wrongly
> switch to NUD_REACHABLE state for long time.
> 
> 	May be there should be some measures to keep
> neigh->confirmed valid during admin modifications.
> 

This problem can also occur if the neigh entry stays in NUD_STALE state
for more than 99 days, even if it is not modified by the administrator.

> 	What is the kernel version?
> 

We encountered this problem in 4.4 LTS, and the mainline doesn't seem
to fix it yet.

Regards,
Changzhong Zhang

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Julian Anastasov]

	Hello,

On Mon, 30 Jan 2023, Zhang Changzhong wrote:

> On 2023/1/30 3:43, Julian Anastasov wrote:
> > 
> >> Does anyone have a good idea to solve this problem? Or are there other scenarios that might cause
> >> such a neighbor entry?
> > 
> > 	Is the neigh entry modified somehow, for example,
> > with 'arp -s' or 'ip neigh change' ? Or is bond0 reconfigured
> > after initial setup? I mean, 4 days ago?>
> 
> So far, we haven't found any user-space program that modifies the neigh
> entry or bond0.

	Ouch, we do not need tools to hit the problem,
thanks to gc_thresh1.

> In fact, the neigh entry has been rarely used since initialization.
> 4 days ago, our machine just needed to download files from 172.16.1.18.
> However, the laddr has changed, and the neigh entry wrongly switched to
> NUD_REACHABLE state, causing the laddr to fail to update.

	Received ARP packets should be able to change
the address. But we do not refresh the entry because
its timer is scheduled days ahead.

> > 	Looking at __neigh_update, there are few cases that
> > can assign NUD_STALE without touching neigh->confirmed:
> > lladdr = neigh->ha should be called, NEIGH_UPDATE_F_ADMIN
> > should be provided. Later, as you explain, it can wrongly
> > switch to NUD_REACHABLE state for long time.
> > 
> > 	May be there should be some measures to keep
> > neigh->confirmed valid during admin modifications.
> > 
> 
> This problem can also occur if the neigh entry stays in NUD_STALE state
> for more than 99 days, even if it is not modified by the administrator.

	I see.

> > 	What is the kernel version?
> > 
> 
> We encountered this problem in 4.4 LTS, and the mainline doesn't seem
> to fix it yet.

	Yep, kernel version is irrelevant.

	Here is a change that you can comment/test but
I'm not sure how many days (100?) are needed :) Not tested.

: From: Julian Anastasov <ja@ssi.bg>
Subject: [PATCH] neigh: make sure used and confirmed times are valid

Entries can linger without timer for days, thanks to
the gc_thresh1 limit. Later, on traffic, NUD_STALE entries
can switch to NUD_DELAY and start the timer which can see
confirmed time in the future causing switch to NUD_REACHABLE.
But then timer is started again based on the wrong
confirmed time, so days in the future. This is more
visible on 32-bit platforms.

Problem and the wrong state change reported by Zhang Changzhong:

172.16.1.18 dev bond0 lladdr 0a:0e:0f:01:12:01 ref 1 used 350521/15994171/350520 probes 4 REACHABLE

350520 seconds have elapsed since this entry was last updated, but it is
still in the REACHABLE state (base_reachable_time_ms is 30000),
preventing lladdr from being updated through probe.

Fix it by ensuring timer is started with valid used/confirmed
times. There are also places that need used/updated times to be
validated.

Reported-by: Zhang Changzhong <zhangchangzhong@huawei.com>
Signed-off-by: Julian Anastasov <ja@ssi.bg>
---
 net/core/neighbour.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/net/core/neighbour.c b/net/core/neighbour.c
index a77a85e357e0..f063e8b8fb7d 100644
--- a/net/core/neighbour.c
+++ b/net/core/neighbour.c
@@ -269,7 +269,7 @@ static int neigh_forced_gc(struct neigh_table *tbl)
 			    (n->nud_state == NUD_NOARP) ||
 			    (tbl->is_multicast &&
 			     tbl->is_multicast(n->primary_key)) ||
-			    time_after(tref, n->updated))
+			    !time_in_range(n->updated, tref, jiffies))
 				remove = true;
 			write_unlock(&n->lock);
 
@@ -289,7 +289,13 @@ static int neigh_forced_gc(struct neigh_table *tbl)
 
 static void neigh_add_timer(struct neighbour *n, unsigned long when)
 {
+	unsigned long mint = jiffies - MAX_JIFFY_OFFSET + 86400 * HZ;
+
 	neigh_hold(n);
+	if (!time_in_range(n->confirmed, mint, jiffies))
+		n->confirmed = mint;
+	if (time_before(n->used, n->confirmed))
+		n->used = n->confirmed;
 	if (unlikely(mod_timer(&n->timer, when))) {
 		printk("NEIGH: BUG, double timer add, state is %x\n",
 		       n->nud_state);
@@ -982,12 +988,14 @@ static void neigh_periodic_work(struct work_struct *work)
 				goto next_elt;
 			}
 
-			if (time_before(n->used, n->confirmed))
+			if (time_before(n->used, n->confirmed) &&
+			    time_is_before_eq_jiffies(n->confirmed))
 				n->used = n->confirmed;
 
 			if (refcount_read(&n->refcnt) == 1 &&
 			    (state == NUD_FAILED ||
-			     time_after(jiffies, n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
+			     !time_in_range_open(jiffies, n->used,
+						 n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
 				*np = n->next;
 				neigh_mark_dead(n);
 				write_unlock(&n->lock);
-- 
2.39.1

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Zhang Changzhong]

On 2023/1/30 19:01, Julian Anastasov wrote:> On Mon, 30 Jan 2023, Zhang Changzhong wrote:
> 
>> On 2023/1/30 3:43, Julian Anastasov wrote:
>>>
>>>> Does anyone have a good idea to solve this problem? Or are there other scenarios that might cause
>>>> such a neighbor entry?
>>>
>>> 	Is the neigh entry modified somehow, for example,
>>> with 'arp -s' or 'ip neigh change' ? Or is bond0 reconfigured
>>> after initial setup? I mean, 4 days ago?>
>>
>> So far, we haven't found any user-space program that modifies the neigh
>> entry or bond0.
> 
> 	Ouch, we do not need tools to hit the problem,
> thanks to gc_thresh1.
> 
>> In fact, the neigh entry has been rarely used since initialization.
>> 4 days ago, our machine just needed to download files from 172.16.1.18.
>> However, the laddr has changed, and the neigh entry wrongly switched to
>> NUD_REACHABLE state, causing the laddr to fail to update.
> 
> 	Received ARP packets should be able to change
> the address. But we do not refresh the entry because
> its timer is scheduled days ahead.
> 

Yep.

>>> 	Looking at __neigh_update, there are few cases that
>>> can assign NUD_STALE without touching neigh->confirmed:
>>> lladdr = neigh->ha should be called, NEIGH_UPDATE_F_ADMIN
>>> should be provided. Later, as you explain, it can wrongly
>>> switch to NUD_REACHABLE state for long time.
>>>
>>> 	May be there should be some measures to keep
>>> neigh->confirmed valid during admin modifications.
>>>
>>
>> This problem can also occur if the neigh entry stays in NUD_STALE state
>> for more than 99 days, even if it is not modified by the administrator.
> 
> 	I see.
> 
>>> 	What is the kernel version?
>>>
>>
>> We encountered this problem in 4.4 LTS, and the mainline doesn't seem
>> to fix it yet.
> 
> 	Yep, kernel version is irrelevant.
> 
> 	Here is a change that you can comment/test but
> I'm not sure how many days (100?) are needed :) Not tested.
> 
> : From: Julian Anastasov <ja@ssi.bg>
> Subject: [PATCH] neigh: make sure used and confirmed times are valid
> 
> Entries can linger without timer for days, thanks to
> the gc_thresh1 limit. Later, on traffic, NUD_STALE entries
> can switch to NUD_DELAY and start the timer which can see
> confirmed time in the future causing switch to NUD_REACHABLE.
> But then timer is started again based on the wrong
> confirmed time, so days in the future. This is more
> visible on 32-bit platforms.
> 
> Problem and the wrong state change reported by Zhang Changzhong:
> 
> 172.16.1.18 dev bond0 lladdr 0a:0e:0f:01:12:01 ref 1 used 350521/15994171/350520 probes 4 REACHABLE
> 
> 350520 seconds have elapsed since this entry was last updated, but it is
> still in the REACHABLE state (base_reachable_time_ms is 30000),
> preventing lladdr from being updated through probe.
> 
> Fix it by ensuring timer is started with valid used/confirmed
> times. There are also places that need used/updated times to be
> validated.
> 
> Reported-by: Zhang Changzhong <zhangchangzhong@huawei.com>
> Signed-off-by: Julian Anastasov <ja@ssi.bg>
> ---
>  net/core/neighbour.c | 14 +++++++++++---
>  1 file changed, 11 insertions(+), 3 deletions(-)
> 
> diff --git a/net/core/neighbour.c b/net/core/neighbour.c
> index a77a85e357e0..f063e8b8fb7d 100644
> --- a/net/core/neighbour.c
> +++ b/net/core/neighbour.c
> @@ -269,7 +269,7 @@ static int neigh_forced_gc(struct neigh_table *tbl)
>  			    (n->nud_state == NUD_NOARP) ||
>  			    (tbl->is_multicast &&
>  			     tbl->is_multicast(n->primary_key)) ||
> -			    time_after(tref, n->updated))
> +			    !time_in_range(n->updated, tref, jiffies))
>  				remove = true;
>  			write_unlock(&n->lock);
>  
> @@ -289,7 +289,13 @@ static int neigh_forced_gc(struct neigh_table *tbl)
>  
>  static void neigh_add_timer(struct neighbour *n, unsigned long when)
>  {
> +	unsigned long mint = jiffies - MAX_JIFFY_OFFSET + 86400 * HZ;
> +
>  	neigh_hold(n);
> +	if (!time_in_range(n->confirmed, mint, jiffies))
> +		n->confirmed = mint;
> +	if (time_before(n->used, n->confirmed))
> +		n->used = n->confirmed;
>  	if (unlikely(mod_timer(&n->timer, when))) {
>  		printk("NEIGH: BUG, double timer add, state is %x\n",
>  		       n->nud_state);
> @@ -982,12 +988,14 @@ static void neigh_periodic_work(struct work_struct *work)
>  				goto next_elt;
>  			}
>  
> -			if (time_before(n->used, n->confirmed))
> +			if (time_before(n->used, n->confirmed) &&
> +			    time_is_before_eq_jiffies(n->confirmed))
>  				n->used = n->confirmed;
>  
>  			if (refcount_read(&n->refcnt) == 1 &&
>  			    (state == NUD_FAILED ||
> -			     time_after(jiffies, n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
> +			     !time_in_range_open(jiffies, n->used,
> +						 n->used + NEIGH_VAR(n->parms, GC_STALETIME)))) {
>  				*np = n->next;
>  				neigh_mark_dead(n);
>  				write_unlock(&n->lock);
> 

Thanks for your fix!

I reproduced this problem by directly modifying the confirmed time of
the neigh entry in STALE state. Your change can fix the problem in this
scenario.

Just curious, why did you choose 'jiffies - MAX_JIFFY_OFFSET + 86400 * HZ'
as the value of 'mint'?

Regards,
Changzhong

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Julian Anastasov]

	Hello,

On Tue, 31 Jan 2023, Zhang Changzhong wrote:

> Thanks for your fix!
> 
> I reproduced this problem by directly modifying the confirmed time of
> the neigh entry in STALE state. Your change can fix the problem in this
> scenario.

	I'm glad that you have a way to test it :) Thanks!

> Just curious, why did you choose 'jiffies - MAX_JIFFY_OFFSET + 86400 * HZ'
> as the value of 'mint'?

	It is too arbitrary :) Probably, just 'jiffies - MAX_JIFFY_OFFSET'
is enough or something depending on HZ/USER_HZ. I added 1 day for
timer to advance without leaving confirmed time behind the
jiffies - MAX_JIFFY_OFFSET zone but it is not needed.

	What limits play here:

- the HZ/USER_HZ difference: jiffies_to_clock_t reports the 3 times
to user space, so we want to display values as large as possible.
Any HZ > 100 for USER_HZ=100 works for the jiffies - MAX_JIFFY_OFFSET.
HZ=100 does not work.

- users can use large values for sysctl vars which can keep the timer
running for long time and reach some outdated confirmed time
before neigh_add_timer() is called to correct it

	If we choose mint = jiffies - MAX_JIFFY_OFFSET,
for 32-bit we will have:

Past                     Future
++++++++++++++++++++++++++++++++++++++++++++++++++++
|  49  days   |  49 days  |         99 days        |
++++++++++++++^+++++++++++^+++++++++++++++++++++++++
              ^           ^
DELAY+PROBE   |           |
            mint         now

- used/confirmed times should be up to 49 days behind jiffies but
we have 49 days to stay in timer without correcting them,
so they can go up to 99 days in the past before going in
the future and trigger the problem

- as we avoid the checks in neigh_timer_handler to save CPU cycles,
one needs crazy sysctl settings to keep the timer in DELAY+PROBE
states for 49 days. With default settings, it is no more than
half minute. In this case even
mint = jiffies - LONG_MAX + 86400 * HZ should work.

- REACHABLE state extends while confirmed time advances,
otherwise PROBE will need ARP reply to recheck the
times in neigh_add_timer while entering REACHABLE again

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [Question] neighbor entry doesn't switch to the STALE state after the reachable timer expires

[Zhang Changzhong]

On 2023/2/1 0:13, Julian Anastasov wrote:
> 
>> Just curious, why did you choose 'jiffies - MAX_JIFFY_OFFSET + 86400 * HZ'
>> as the value of 'mint'?
> 
> 	It is too arbitrary :) Probably, just 'jiffies - MAX_JIFFY_OFFSET'
> is enough or something depending on HZ/USER_HZ. I added 1 day for
> timer to advance without leaving confirmed time behind the
> jiffies - MAX_JIFFY_OFFSET zone but it is not needed.
> 
> 	What limits play here:
> 
> - the HZ/USER_HZ difference: jiffies_to_clock_t reports the 3 times
> to user space, so we want to display values as large as possible.
> Any HZ > 100 for USER_HZ=100 works for the jiffies - MAX_JIFFY_OFFSET.
> HZ=100 does not work.
> 
> - users can use large values for sysctl vars which can keep the timer
> running for long time and reach some outdated confirmed time
> before neigh_add_timer() is called to correct it
> 
> 	If we choose mint = jiffies - MAX_JIFFY_OFFSET,
> for 32-bit we will have:
> 
> Past                     Future
> ++++++++++++++++++++++++++++++++++++++++++++++++++++
> |  49  days   |  49 days  |         99 days        |
> ++++++++++++++^+++++++++++^+++++++++++++++++++++++++
>               ^           ^
> DELAY+PROBE   |           |
>             mint         now
> 
> - used/confirmed times should be up to 49 days behind jiffies but
> we have 49 days to stay in timer without correcting them,
> so they can go up to 99 days in the past before going in
> the future and trigger the problem
> 
> - as we avoid the checks in neigh_timer_handler to save CPU cycles,
> one needs crazy sysctl settings to keep the timer in DELAY+PROBE
> states for 49 days. With default settings, it is no more than
> half minute. In this case even
> mint = jiffies - LONG_MAX + 86400 * HZ should work.
> 
> - REACHABLE state extends while confirmed time advances,
> otherwise PROBE will need ARP reply to recheck the
> times in neigh_add_timer while entering REACHABLE again
> 

Wow, thank you so much for the detailed explanation! Are you planning
to mainline it?

Regards,
Changzhong