Messages in this thread | | | Subject | Re: [PATCH v2 01/11] counters: Introduce counter_atomic* counters | From | Shuah Khan <> | Date | Wed, 7 Oct 2020 13:26:53 -0600 |
| |
On 10/7/20 12:11 PM, Kees Cook wrote: > On Tue, Oct 06, 2020 at 02:44:32PM -0600, Shuah Khan wrote: >> Introduce Simple atomic counters. >> >> There are a number of atomic_t usages in the kernel where atomic_t api >> is used strictly for counting and not for managing object lifetime. In >> some cases, atomic_t might not even be needed. >> >> The purpose of these counters is to clearly differentiate atomic_t >> counters from atomic_t usages that guard object lifetimes, hence prone >> to overflow and underflow errors. It allows tools that scan for underflow >> and overflow on atomic_t usages to detect overflow and underflows to scan >> just the cases that are prone to errors. >> >> Simple atomic counters api provides interfaces for simple atomic counters >> that just count, and don't guard resource lifetimes. Counter will wrap >> around to 0 when it overflows and should not be used to guard resource >> lifetimes, device usage and open counts that control state changes, and >> pm states. >> >> Using counter_atomic* to guard lifetimes could lead to use-after free >> when it overflows and undefined behavior when used to manage state >> changes and device usage/open states. >> >> Reviewed-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> >> Signed-off-by: Shuah Khan <skhan@linuxfoundation.org> >> --- >> Documentation/core-api/counters.rst | 103 +++++++++++++++++ >> MAINTAINERS | 7 ++ >> include/linux/counters.h | 173 ++++++++++++++++++++++++++++ >> lib/Kconfig | 10 ++ >> lib/Makefile | 1 + >> lib/test_counters.c | 157 +++++++++++++++++++++++++ >> 6 files changed, 451 insertions(+) >> create mode 100644 Documentation/core-api/counters.rst >> create mode 100644 include/linux/counters.h >> create mode 100644 lib/test_counters.c >> >> diff --git a/Documentation/core-api/counters.rst b/Documentation/core-api/counters.rst >> new file mode 100644 >> index 000000000000..ba1ce325b639 >> --- /dev/null >> +++ b/Documentation/core-api/counters.rst >> @@ -0,0 +1,103 @@ >> +.. SPDX-License-Identifier: GPL-2.0 >> + >> +====================== >> +Simple atomic counters >> +====================== >> + >> +:Author: Shuah Khan >> + >> +There are a number of atomic_t usages in the kernel where atomic_t api >> +is used strictly for counting and not for managing object lifetime. In >> +some cases, atomic_t might not even be needed. >> + >> +The purpose of these counters is to clearly differentiate atomic_t counters >> +from atomic_t usages that guard object lifetimes, hence prone to overflow >> +and underflow errors. It allows tools that scan for underflow and overflow >> +on atomic_t usages to detect overflow and underflows to scan just the cases >> +that are prone to errors. >> + >> +Simple atomic counters api provides interfaces for simple atomic counters >> +that just count, and don't guard resource lifetimes. Counter will wrap >> +around to 0 when it overflows and should not be used to guard resource >> +lifetimes, device usage and open counts that control state changes, and >> +pm states. >> + >> +Using counter_atomic32_* to guard lifetimes could lead to use-after free >> +when it overflows and undefined behavior when used to manage state >> +changes and device usage/open states. >> + >> +Use refcount_t interfaces for guarding resources. >> + >> +.. warning:: >> + Counter will wrap around to 0 when it overflows. >> + Should not be used to guard resource lifetimes. >> + Should not be used to manage device state and pm state. >> + >> +Test Counters Module and selftest >> +--------------------------------- >> + >> +Please see :ref:`lib/test_counters.c <Test Counters Module>` for how to >> +use these interfaces and also test them. >> + >> +Selftest for testing: >> +:ref:`testing/selftests/lib/test_counters.sh <selftest for counters>` >> + >> +Atomic counter interfaces >> +========================= >> + >> +counter_atomic32 and counter_atomic64 types use atomic_t and atomic64_t >> +underneath to leverage atomic_t api, providing a small subset of atomic_t >> +interfaces necessary to support simple counters. :: >> + >> + struct counter_atomic32 { atomic_t cnt; }; >> + struct counter_atomic64 { atomic64_t cnt; }; >> + >> +Please see :ref:`Documentation/core-api/atomic_ops.rst <atomic_ops>` for >> +information on the Semantics and Behavior of Atomic operations. >> + >> +.. warning:: >> + It is important to keep the ops to a very small subset to ensure >> + that the Counter API will never be used for guarding resource >> + lifetimes and state management. >> + >> + inc_return() is added to support current atomic_inc_return() >> + usages and avoid forcing the use of _inc() followed by _read(). >> + >> +Initializers >> +------------ >> + >> +Interfaces for initializing counters are write operations which in turn >> +invoke their ``ATOMIC_INIT() and atomic_set()`` counterparts :: >> + >> + #define COUNTER_ATOMIC_INIT(i) { .cnt = ATOMIC_INIT(i) } >> + counter_atomic32_set() --> atomic_set() >> + >> + static struct counter_atomic32 acnt = COUNTER_ATOMIC_INIT(0); >> + counter_atomic32_set(0); >> + >> + static struct counter_atomic64 acnt = COUNTER_ATOMIC_INIT(0); >> + counter_atomic64_set(0); >> + >> +Increment interface >> +------------------- >> + >> +Increments counter and doesn't return the new counter value. :: >> + >> + counter_atomic32_inc() --> atomic_inc() >> + counter_atomic64_inc() --> atomic64_inc() >> + >> +Increment and return new counter value interface >> +------------------------------------------------ >> + >> +Increments counter and returns the new counter value. :: >> + >> + counter_atomic32_inc_return() --> atomic_inc_return() >> + counter_atomic64_inc_return() --> atomic64_inc_return() >> + >> +Decrement interface >> +------------------- >> + >> +Decrements counter and doesn't return the new counter value. :: >> + >> + counter_atomic32_dec() --> atomic_dec() >> + counter_atomic64_dec() --> atomic64_dec() >> diff --git a/MAINTAINERS b/MAINTAINERS >> index 33b27e62ce19..4e82d0ffcab0 100644 >> --- a/MAINTAINERS >> +++ b/MAINTAINERS >> @@ -15839,6 +15839,13 @@ S: Maintained >> F: Documentation/fb/sm712fb.rst >> F: drivers/video/fbdev/sm712* >> >> +SIMPLE ATOMIC and NON-ATOMIC COUNTERS >> +M: Shuah Khan <skhan@linuxfoundation.org> >> +L: linux-kernel@vger.kernel.org >> +S: Maintained >> +F: include/linux/counters.h >> +F: lib/test_counters.c >> + >> SIMPLE FIRMWARE INTERFACE (SFI) >> S: Obsolete >> W: http://simplefirmware.org/ >> diff --git a/include/linux/counters.h b/include/linux/counters.h >> new file mode 100644 >> index 000000000000..c0c26a13f768 >> --- /dev/null >> +++ b/include/linux/counters.h >> @@ -0,0 +1,173 @@ >> +/* SPDX-License-Identifier: GPL-2.0 */ >> +/* >> + * Interface for simple atomic counters that just count. >> + * >> + * Counter will wrap around to 0 when it overflows and should not be >> + * used to guard resource lifetimes, device usage and open counts that >> + * control state changes, and pm states. Using counter_atomic to guard >> + * lifetimes could lead to use-after free when it overflows and undefined >> + * behavior when used to manage state changes and device usage/open states. >> + * >> + * Use refcount_t interfaces for guarding resources. >> + * >> + * The interface provides: >> + * atomic32 & atomic64 functions: >> + * increment and no return >> + * increment and return value >> + * decrement and no return >> + * read >> + * set >> + * >> + * counter_atomic32 unctions leverage/use atomic_t interfaces. > > typo: functions
Thanks for the catch.
> >> + * counter_atomic64 functions leverage/use atomic64_t interfaces. >> + * The counter will wrap around to 0 when it overflows. >> + * These interfaces should not be used to guard resource lifetimes. >> + * >> + * Reference and API guide: >> + * Documentation/core-api/counters.rst for more information. >> + * >> + */ >> + >> +#ifndef __LINUX_COUNTERS_H >> +#define __LINUX_COUNTERS_H >> + >> +#include <linux/atomic.h> >> + >> +/** >> + * struct counter_atomic32 - Simple atomic counter >> + * @cnt: int >> + * >> + * The counter wraps around to 0, when it overflows. Should not >> + * be used to guard object lifetimes. >> + **/ >> +struct counter_atomic32 { >> + atomic_t cnt; >> +}; >> + >> +#define COUNTER_ATOMIC_INIT(i) { .cnt = ATOMIC_INIT(i) } >> + >> +/* >> + * counter_atomic32_inc() - increment counter value >> + * @cntr: struct counter_atomic32 pointer >> + * >> + */ >> +static inline void counter_atomic32_inc(struct counter_atomic32 *cntr) >> +{ >> + atomic_inc(&cntr->cnt); >> +} >> + >> +/* >> + * counter_atomic32_inc_return() - increment counter value and return it >> + * @cntr: struct counter_atomic32 pointer >> + * >> + * Return: returns the new counter value after incrementing it >> + */ >> +static inline int counter_atomic32_inc_return(struct counter_atomic32 *cntr) >> +{ >> + return atomic_inc_return(&cntr->cnt); >> +} > > So, there's an issue here between the types and the documentation: while > this will eventually wrap around to 0, it will first go through the > negative value space (i.e. INT_MAX + 1 == INT_MIN, INT_MIN < 0). >
Right. It does go through INT_MIN state before it wraps around.
> Current users of atomic_t should already be expecting this, but does it > make sense? > > i.e. should the documentation be updated to "wraps around to negative > values", or should the counter API be updated to force the unsigned > value: > > +static inline u32 counter_atomic32_inc_return(struct counter_atomic32 *cntr) > +{ > + return (u32)atomic_inc_return(&cntr->cnt); > +} > > I see many forcing the return type from atomic_*{read,return}*(): > > $ git grep -E '\((unsigned|unsigned int|u32)\).*\batomic.*(read|return)' | wc -l > 67 > > My instinct is to say leave it "int" and adjust documentation, which is > the least disruptive, but I am enticed by the desire to make sure a > counter doesn't "misbehave" and go negative when the usage wants it > always positive. >
I would recommend leaving it as "int". Changing the API to unsigned has other ramifications and cascading changes.
My quick search shows me there are 612 atomic_inc_return usages and 14 out of them are forcing the return type from int to u32.
For atomic_read the numbers are 51 out of 5833 forcing u32. We have couple of options:
1. Update the documentation since we have more cases where int is just fine. 2. Add counter_atomic32_inc_return_u32() variant to cover these few cases that are forcing the return.
I recommend going with option 1 with Documentation update and add option 2 when we convert one of these 60+.
>> +static void test_counter_atomic32_overflow(void) >> +{ >> + static struct counter_atomic32 ucnt = COUNTER_ATOMIC_INIT(0); >> + static struct counter_atomic32 ocnt = COUNTER_ATOMIC_INIT(INT_MAX); >> + int start_val; >> + int end_val; >> + >> + start_val = counter_atomic32_read(&ucnt); >> + counter_atomic32_dec(&ucnt); >> + end_val = counter_atomic32_read(&ucnt); > > This is testing that counter operations match native int operations, > which seems fine. I wonder if hard-coded values should be added too, to > just more directly map the explicit expectations? E.g. adding a second > test with each: > > test_counter_result_print32("Test underflow (int)", > start_val, end_val, start_val-1); > test_counter_result_print32("Test underflow (-1)", > start_val, end_val, -1); > >
Yeah. I can add that.
>> + >> + start_val = counter_atomic32_read(&ocnt); >> + end_val = counter_atomic32_inc_return(&ocnt); > > and: > > test_counter_result_print32("Test overflow (int)", > start_val, end_val, start_val+1); > test_counter_result_print32("Test underflow (INT_MIN)", > start_val, end_val, INT_MIN); >
Sure.
> > Otherwise, yes, looks great; thank you! >
thanks, -- Shuah
| |