Re: [RESEND PATCH v4 05/10] lib/refcount: Improve performance of generic REFCOUNT_FULL code

* Re: [RESEND PATCH v4 05/10] lib/refcount: Improve performance of generic REFCOUNT_FULL code
       [not found] ` <20191121115902.2551-6-will@kernel.org>
@ 2020-02-26  4:10   ` Jann Horn
  2020-02-28 10:43     ` Will Deacon
  0 siblings, 1 reply; 3+ messages in thread
From: Jann Horn @ 2020-02-26  4:10 UTC (permalink / raw)
  To: Will Deacon
  Cc: kernel list, Kees Cook, Ingo Molnar, Elena Reshetova,
	Peter Zijlstra, Ard Biesheuvel, Hanjun Guo, Jan Glauber,
	Kernel Hardening

On Thu, Nov 21, 2019 at 12:58 PM Will Deacon <will@kernel.org> wrote:
> Rewrite the generic REFCOUNT_FULL implementation so that the saturation
> point is moved to INT_MIN / 2. This allows us to defer the sanity checks
> until after the atomic operation, which removes many uses of cmpxchg()
> in favour of atomic_fetch_{add,sub}().

Oh, I never saw this, this is really neat! CCing the kernel-hardening
list on this might've been a good idea.

> + * Saturation semantics
> + * ====================
> + *
> + * refcount_t differs from atomic_t in that the counter saturates at
> + * REFCOUNT_SATURATED and will not move once there. This avoids wrapping the
> + * counter and causing 'spurious' use-after-free issues. In order to avoid the
> + * cost associated with introducing cmpxchg() loops into all of the saturating
> + * operations, we temporarily allow the counter to take on an unchecked value
> + * and then explicitly set it to REFCOUNT_SATURATED on detecting that underflow
> + * or overflow has occurred. Although this is racy when multiple threads
> + * access the refcount concurrently, by placing REFCOUNT_SATURATED roughly
> + * equidistant from 0 and INT_MAX we minimise the scope for error:
> + *
> + *                                INT_MAX     REFCOUNT_SATURATED   UINT_MAX
> + *   0                          (0x7fff_ffff)    (0xc000_0000)    (0xffff_ffff)
> + *   +--------------------------------+----------------+----------------+
> + *                                     <---------- bad value! ---------->
> + *
> + * (in a signed view of the world, the "bad value" range corresponds to
> + * a negative counter value).
[...]
> + * If another thread also performs a refcount_inc() operation between the two
> + * atomic operations, then the count will continue to edge closer to 0. If it
> + * reaches a value of 1 before /any/ of the threads reset it to the saturated
> + * value, then a concurrent refcount_dec_and_test() may erroneously free the
> + * underlying object. Given the precise timing details involved with the
> + * round-robin scheduling of each thread manipulating the refcount and the need
> + * to hit the race multiple times in succession, there doesn't appear to be a
> + * practical avenue of attack even if using refcount_add() operations with
> + * larger increments.

On top of that, the number of threads that can actually be running at
a given time is capped. See include/linux/threads.h, where it is
capped to pow(2, 22):

    /*
     * A maximum of 4 million PIDs should be enough for a while.
     * [NOTE: PID/TIDs are limited to 2^29 ~= 500+ million, see futex.h.]
     */
    #define PID_MAX_LIMIT (CONFIG_BASE_SMALL ? PAGE_SIZE * 8 : \
            (sizeof(long) > 4 ? 4 * 1024 * 1024 : PID_MAX_DEFAULT))

And in the futex UAPI header, we have this, baking a TID limit into
the userspace API (note that this is pow(2,30), not pow(2,29) as the
comment in threads.h claims - I'm not sure where that difference comes
from):

    /*
     * The rest of the robust-futex field is for the TID:
     */
    #define FUTEX_TID_MASK 0x3fffffff

So AFAICS, with the current PID_MAX_LIMIT, if you assume that all
participating refcount operations are non-batched (delta 1) and the
attacker can't cause the threads to oops in the middle of the refcount
operation (maybe that would be possible if you managed to find
something like a NULL pointer dereference in perf software event code
and had perf paranoia at <=1 , or something like that? - I'm not
sure), then even in a theoretical scenario where an attacker spawns
the maximum number of tasks possible and manages to get all of them to
sequentially preempt while being in the middle of increment operations
in several nested contexts (I'm not sure whether that can even happen
- you're not going to take typical sleeping exceptions like page
faults in the middle of a refcount op), the attacker will stay
comfortably inside the saturated range. Even if the PID_MAX_LIMIT is
at some point raised to the maximum permitted by the futex UAPI, this
still holds as long as you assume no nesting. Hm, should I send a
patch to add something like this to the explanatory comment?

Of course, if someone uses refcount batching with sufficiently large
values, those guarantees go out of the window - if we wanted to be
perfectionist about this, we could make the batched operations do slow
cmpxchg stuff while letting the much more performance-critical
single-reference case continue to use the fast saturation scheme.
OTOH, the networking folks would probably hate that, since they're
using the batched ops for ->sk_wmem_alloc stuff, where they count
bytes as references? So I guess maybe we should leave it as-is.

^ permalink raw reply	[flat|nested] 3+ messages in thread