Re: [PATCH v2 01/11] counters: Introduce counter_atomic* counters

[Shuah Khan <skhan@linuxfoundation.org>]

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