[PATCH v1 0/3] ida: fix the allocation failure paths of ida_alloc_range()

[Nickolai Zeldovich]

These three patches fix what ida_alloc_range() does when its xas_store()
fails for want of a node, found while formally verifying the function
against the kernel binary, where its resource accounting could not be
established against the code as it is.

Patch 1: the bit set in a new bitmap before the failed store is not
cleared again, so a retry can store an ID that nobody owns (exact-ID
callers then get -ENOSPC for a free ID, and the chunk's bitmap can never
be freed).  Patch 2: the bitmap of the failed store is leaked, on the
-ENOMEM return and on a successful retry.  Patch 3: the node
preallocated by xas_nomem() is leaked on the "nospc:" exit and on the
-ENOMEM return at "alloc:".  These need an allocation failure under
memory pressure and, for two of them, a concurrent allocation on the
same IDA; they affect every ida_alloc_*() user, so they are tagged for
stable.

Patches 1 and 3 add tests to tools/testing/radix-tree/idr-test.c which
use the node cache callback of the user-space harness to run a second
allocation in the window where xas_nomem() has dropped the lock; they
fail without their fix.  The leaks of patch 2 cannot be reached in the
harness (it cannot fail a GFP_KERNEL node allocation or let a
GFP_NOWAIT kmalloc() succeed) and were reproduced with a user-space
copy of the function with fault injection at its four allocation sites.
The complete lib/test_ida.c suite and idr-test pass at XA_CHUNK_SHIFT 3
and 6, and in x86_64 and RISC-V defconfig kernels with CONFIG_TEST_IDA=y
booted under QEMU; lib/idr.o builds without warnings with W=1 and C=1
(sparse) on both architectures.

Nickolai Zeldovich (3):
  ida: clear the bit of a bitmap that ida_alloc_range() failed to store
  ida: free the bitmaps that ida_alloc_range() fails to store
  ida: free the preallocated node on the ida_alloc_range() failure paths

 lib/idr.c                           | 16 ++++--
 tools/testing/radix-tree/idr-test.c | 77 +++++++++++++++++++++++++++++
 tools/testing/radix-tree/test.h     |  4 ++
 3 files changed, 94 insertions(+), 3 deletions(-)


base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0