Skip to contentSkip to conversation

RFC: chasing all idr_remove() misses

DISCUSSION Alexandre Ferrieux 3 participants 6 messages Nov 16, 2024 – Nov 20, 2024 Kernel janitors

lore
Share & tools
lore
#0 lore raw

Hi,

In the recent fix of u32's IDR leaks:

73af53d82076 net: sched: cls_u32: Fix u32's systematic failure to free IDR
entries for hnodes.

... one side remark is that the problem went unnoticed for 7 years due to the NULL result from idr_remove() being ignored at this call site.

Now, a cursory grep over the whole Linux tree shows 306 out of 386 call sites (excluding those hidden in macros, if any) don't bother to extract the value returned by idr_remove().

Indeed, a failed IDR removal is "mostly harmless" since IDs are not pointers so the mismatch is detectable (and is detected, returning NULL). However, in racy situations you may end up killing an innocent fresh entry, which may really break things a bit later. And in all cases, a true bug is the root cause.

So, unless we have reasons to think cls_u32 was the only place where two ID encodings might lend themselves to confusion, I'm wondering if it wouldn't make sense to chase the issue more systematically:

- either with WARN_ON[_ONCE](idr_remove()==NULL) on each call site individually
(a year-long endeavor implying tens of maintainers)

- or with WARN_ON[_ONCE] just before returning NULL within idr_remove() itself,
or even radix_tree_delete_item() (quicker but possibly disruptive)

- a variant of the latter being to do it only for harsh bug-hunting builds (the
ones typically used by patrolling bots)

Opinions ?

#1 lore raw

Matthew Wilcox maintains IDR so it's really up to him. I don't think adding a WARN_ON_ONCE() in idr_remove() for NULL returns is a bad idea but we could hide it behind a #if DEBUG_IDR or something and try run syzkaller on it first.

regards,
dan carpenter

Quoted 33 lines · Alexandre Ferrieux

Hi,

In the recent fix of u32's IDR leaks:

73af53d82076 net: sched: cls_u32: Fix u32's systematic failure to free IDR
entries for hnodes.

... one side remark is that the problem went unnoticed for 7 years due to the NULL result from idr_remove() being ignored at this call site.

Now, a cursory grep over the whole Linux tree shows 306 out of 386 call sites (excluding those hidden in macros, if any) don't bother to extract the value returned by idr_remove().

Indeed, a failed IDR removal is "mostly harmless" since IDs are not pointers so the mismatch is detectable (and is detected, returning NULL). However, in racy situations you may end up killing an innocent fresh entry, which may really break things a bit later. And in all cases, a true bug is the root cause.

So, unless we have reasons to think cls_u32 was the only place where two ID encodings might lend themselves to confusion, I'm wondering if it wouldn't make sense to chase the issue more systematically:

- either with WARN_ON[_ONCE](idr_remove()==NULL) on each call site individually
(a year-long endeavor implying tens of maintainers)

- or with WARN_ON[_ONCE] just before returning NULL within idr_remove() itself,
or even radix_tree_delete_item() (quicker but possibly disruptive)

- a variant of the latter being to do it only for harsh bug-hunting builds (the
ones typically used by patrolling bots)

Opinions ?

#2 lore raw
Quoted 6 lines · Dan Carpenter
Quoted 4 lines · Alexandre Ferrieux

73af53d82076 net: sched: cls_u32: Fix u32's systematic failure to free IDR
entries for hnodes.

Quoted 7 lines
Quoted 4 lines

So, unless we have reasons to think cls_u32 was the only place where two ID encodings might lend themselves to confusion, I'm wondering if it wouldn't make sense to chase the issue more systematically

Matthew Wilcox maintains IDR so it's really up to him. I don't think adding a WARN_ON_ONCE() in idr_remove() for NULL returns is a bad idea but we could hide it behind a #if DEBUG_IDR or something and try run syzkaller on it first.

Thanks Dan. Now, I'm not familiar with the syzbot feeding process, can you help me out ? Is the next step to:

(a) invent the new debug flag (e.g. "DEBUG_IDR") then post a patch using it;
wait for its acceptation and merge ; then contact syzbot operators to add it in (some of) its builds

(b) use some existing wide-range debug flag so that syzbot will automagically
test IDR once the patch is merged

(c) wait for you or Matthew to handle all of this

Thanks in advance,

-Alex

#3 lore raw
Quoted 18 lines · Alexandre Ferrieux
Quoted 6 lines · Dan Carpenter
Quoted 4 lines · Alexandre Ferrieux

73af53d82076 net: sched: cls_u32: Fix u32's systematic failure to free IDR
entries for hnodes.

Quoted 7 lines
Quoted 4 lines

So, unless we have reasons to think cls_u32 was the only place where two ID encodings might lend themselves to confusion, I'm wondering if it wouldn't make sense to chase the issue more systematically

Matthew Wilcox maintains IDR so it's really up to him. I don't think adding a WARN_ON_ONCE() in idr_remove() for NULL returns is a bad idea but we could hide it behind a #if DEBUG_IDR or something and try run syzkaller on it first.

Thanks Dan. Now, I'm not familiar with the syzbot feeding process, can you help me out ? Is the next step to:

Quoted 8 lines

(a) invent the new debug flag (e.g. "DEBUG_IDR") then post a patch using it;
wait for its acceptation and merge ; then contact syzbot operators to add it in (some of) its builds

(b) use some existing wide-range debug flag so that syzbot will automagically
test IDR once the patch is merged

(c) wait for you or Matthew to handle all of this

IDR is deprecated. I'm not excited about patches that make it better. IDR users should be converted to use the XArray API.

#4 lore raw
Quoted 23 lines · Matthew Wilcox
Quoted 22 lines · Alexandre Ferrieux
Quoted 6 lines · Dan Carpenter
Quoted 4 lines · Alexandre Ferrieux

73af53d82076 net: sched: cls_u32: Fix u32's systematic failure to free IDR
entries for hnodes.

Quoted 7 lines
Quoted 4 lines

So, unless we have reasons to think cls_u32 was the only place where two ID encodings might lend themselves to confusion, I'm wondering if it wouldn't make sense to chase the issue more systematically

Matthew Wilcox maintains IDR so it's really up to him. I don't think adding a WARN_ON_ONCE() in idr_remove() for NULL returns is a bad idea but we could hide it behind a #if DEBUG_IDR or something and try run syzkaller on it first.

Thanks Dan. Now, I'm not familiar with the syzbot feeding process, can you help me out ? Is the next step to:

(a) invent the new debug flag (e.g. "DEBUG_IDR") then post a patch using it;
wait for its acceptation and merge ; then contact syzbot operators to add it in (some of) its builds

Quoted 7 lines
Quoted 4 lines

(b) use some existing wide-range debug flag so that syzbot will automagically
test IDR once the patch is merged

(c) wait for you or Matthew to handle all of this

IDR is deprecated. I'm not excited about patches that make it better. IDR users should be converted to use the XArray API.

Well, the problem is more about chasing a bad usage pattern than an API's limitations. Indeed, doing the same grep for Xarray shows that, out of 434 (naked) call sites of xa_erase() in the kernel, 307 fail to check the result.

So, independently from the IDR->XArray transition (which may still take some time), it looks like there's a Damocles sword over a possibly huge number of areas, and that would handily be grabbed by a syzbot scan, with a ridiculous time investment: just add #ifdef ... WARN_ON_ONCE() ...#endif on the "return NULL" path of both idr_remove() and xa_erase().

Again, I'm not asking to do this on production kernels. All I'm asking is the detailed procedure to let the "established" fuzzers exercise that, as using syzkaller locally on my limited hardware is not an serious option.

#5 lore raw
Quoted 15 lines · Alexandre Ferrieux
Quoted 3 lines · Matthew Wilcox

IDR is deprecated. I'm not excited about patches that make it better. IDR users should be converted to use the XArray API.

Well, the problem is more about chasing a bad usage pattern than an API's limitations. Indeed, doing the same grep for Xarray shows that, out of 434 (naked) call sites of xa_erase() in the kernel, 307 fail to check the result.

So, independently from the IDR->XArray transition (which may still take some time), it looks like there's a Damocles sword over a possibly huge number of areas, and that would handily be grabbed by a syzbot scan, with a ridiculous time investment: just add #ifdef ... WARN_ON_ONCE() ...#endif on the "return NULL" path of both idr_remove() and xa_erase().

Quoted 3 lines

Again, I'm not asking to do this on production kernels. All I'm asking is the detailed procedure to let the "established" fuzzers exercise that, as using syzkaller locally on my limited hardware is not an serious option.

Reading up on syzbot documentation, I can see that the recommended idiom for such cases is #if IS_ENABLED(CONFIG_DEBUG_AID_FOR_SYZBOT):

Quoted 7 lines
Quoted 1 line

https://github.com/google/syzkaller/blob/master/docs/syzbot.md says:

However, syzbot kernel config always includes CONFIG_DEBUG_AID_FOR_SYZBOT=y setting, which is not normally present in kernel. What was used for particularly elusive bugs in the past is temporary merging some additional debugging code into linux-next under this config setting (e.g. more debug checks and/or debug output) and waiting for new crash reports from syzbot

So, if I submitted a patch doing WARN_ON_ONCE(..==NULL) under this flag in all naked idr_remove() and xa_erase() call sites, with suitable macro decoration to keep readability, would it stand a chance to be committed ?