From: Kent Overstreet <kent.overstreet@linux.dev>
To: akpm@linux-foundation.org
Cc: linux-kernel@vger.kernel.org,
Kent Overstreet <kent.overstreet@linux.dev>
Subject: [PATCH v2 8/8] generix-radix-tree: Overflow checking
Date: Sun, 12 Oct 2025 17:24:11 -0400 [thread overview]
Message-ID: <20251012212414.3225948-9-kent.overstreet@linux.dev> (raw)
In-Reply-To: <20251012212414.3225948-1-kent.overstreet@linux.dev>
Internally, genradixes index based on the byte offset into the radix
tree - index * obj_size - which means accidental overflows are a real
concern.
This was noticed in bcachefs where we were using them to index inode
numbers, for hardlink checking/detection.
Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
---
include/linux/generic-radix-tree.h | 110 +++++++++++++++++------------
1 file changed, 65 insertions(+), 45 deletions(-)
diff --git a/include/linux/generic-radix-tree.h b/include/linux/generic-radix-tree.h
index 5b51c3d582d6..52b012efe8f4 100644
--- a/include/linux/generic-radix-tree.h
+++ b/include/linux/generic-radix-tree.h
@@ -155,20 +155,27 @@ void __genradix_free(struct __genradix *);
*/
#define genradix_free(_radix) __genradix_free(&(_radix)->tree)
-static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
+static inline bool __idx_to_offset(size_t idx, size_t obj_size, size_t *offset)
{
+ /*
+ * XXX: check for overflow, we have a bug in multiple places where we
+ * assume idx fits in 64 bits (because it's an inode number; already a
+ * bug on 32 bit) - but we then multiply by the object size and we
+ * overflow
+ */
if (__builtin_constant_p(obj_size))
BUILD_BUG_ON(obj_size > GENRADIX_NODE_SIZE);
else
BUG_ON(obj_size > GENRADIX_NODE_SIZE);
if (!is_power_of_2(obj_size)) {
- size_t objs_per_page = GENRADIX_NODE_SIZE / obj_size;
+ size_t objs_per_page = GENRADIX_NODE_SIZE / obj_size, node, node_offset;
- return (idx / objs_per_page) * GENRADIX_NODE_SIZE +
- (idx % objs_per_page) * obj_size;
+ return check_mul_overflow(idx / objs_per_page, GENRADIX_NODE_SIZE, &node) ? true :
+ check_mul_overflow(idx % objs_per_page, obj_size, &node_offset) ? true :
+ check_add_overflow(node, node_offset, offset);
} else {
- return idx * obj_size;
+ return check_mul_overflow(idx, obj_size, offset);
}
}
@@ -179,8 +186,8 @@ static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
#define __genradix_page_remainder(_radix) \
(GENRADIX_NODE_SIZE % sizeof((_radix)->type[0]))
-#define __genradix_idx_to_offset(_radix, _idx) \
- __idx_to_offset(_idx, __genradix_obj_size(_radix))
+#define __genradix_idx_to_offset(_radix, _idx, _offset) \
+ __idx_to_offset(_idx, __genradix_obj_size(_radix), _offset)
static inline void *__genradix_ptr_inlined(struct __genradix *radix, size_t offset)
{
@@ -202,9 +209,13 @@ static inline void *__genradix_ptr_inlined(struct __genradix *radix, size_t offs
}
#define genradix_ptr_inlined(_radix, _idx) \
- (__genradix_cast(_radix) \
- __genradix_ptr_inlined(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx)))
+({ \
+ size_t _offset; \
+ !__genradix_idx_to_offset(_radix, _idx, &_offset) \
+ ? __genradix_cast(_radix) \
+ __genradix_ptr_inlined(&(_radix)->tree, _offset) \
+ : NULL; \
+})
void *__genradix_ptr(struct __genradix *, size_t);
@@ -216,28 +227,39 @@ void *__genradix_ptr(struct __genradix *, size_t);
* Returns a pointer to entry at @_idx, or NULL if that entry does not exist.
*/
#define genradix_ptr(_radix, _idx) \
- (__genradix_cast(_radix) \
- __genradix_ptr(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx)))
+({ \
+ size_t _offset; \
+ !__genradix_idx_to_offset(_radix, _idx, &_offset) \
+ ? __genradix_cast(_radix) \
+ __genradix_ptr(&(_radix)->tree, _offset) \
+ : NULL; \
+})
void *__genradix_ptr_alloc(struct __genradix *, size_t,
struct genradix_node **, gfp_t);
-#define genradix_ptr_alloc_inlined(_radix, _idx, _gfp) \
- (__genradix_cast(_radix) \
- (__genradix_ptr_inlined(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx)) ?: \
- __genradix_ptr_alloc(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx), \
- NULL, _gfp)))
-
#define genradix_ptr_alloc_preallocated_inlined(_radix, _idx, _new_node, _gfp)\
- (__genradix_cast(_radix) \
- (__genradix_ptr_inlined(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx)) ?: \
- __genradix_ptr_alloc(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx), \
- _new_node, _gfp)))
+({ \
+ size_t _offset; \
+ !__genradix_idx_to_offset(_radix, _idx, &_offset) \
+ ? __genradix_cast(_radix) \
+ (__genradix_ptr_inlined(&(_radix)->tree, _offset) ?: \
+ __genradix_ptr_alloc(&(_radix)->tree, _offset, \
+ _new_node, _gfp)) \
+ : NULL; \
+})
+
+#define genradix_ptr_alloc_inlined(_radix, _idx, _gfp) \
+ genradix_ptr_alloc_preallocated_inlined(_radix, _idx, NULL, _gfp)
+
+#define genradix_ptr_alloc_preallocated(_radix, _idx, _new_node, _gfp) \
+({ \
+ size_t _offset; \
+ !__genradix_idx_to_offset(_radix, _idx, &_offset) \
+ ? __genradix_cast(_radix) \
+ __genradix_ptr_alloc(&(_radix)->tree, _offset, _new_node, _gfp) \
+ : NULL; \
+})
/**
* genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
@@ -248,17 +270,8 @@ void *__genradix_ptr_alloc(struct __genradix *, size_t,
*
* Returns a pointer to entry at @_idx, or NULL on allocation failure
*/
-#define genradix_ptr_alloc(_radix, _idx, _gfp) \
- (__genradix_cast(_radix) \
- __genradix_ptr_alloc(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx), \
- NULL, _gfp))
-
-#define genradix_ptr_alloc_preallocated(_radix, _idx, _new_node, _gfp)\
- (__genradix_cast(_radix) \
- __genradix_ptr_alloc(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _idx), \
- _new_node, _gfp))
+#define genradix_ptr_alloc(_radix, _idx, _gfp) \
+ genradix_ptr_alloc_preallocated(_radix, _idx, NULL, _gfp)
struct genradix_iter {
size_t offset;
@@ -271,10 +284,15 @@ struct genradix_iter {
* @_idx: index to start iterating from
*/
#define genradix_iter_init(_radix, _idx) \
- ((struct genradix_iter) { \
+({ \
+ size_t _offset; \
+ __genradix_idx_to_offset(_radix, _idx, &_offset); \
+ \
+ (struct genradix_iter) { \
.pos = (_idx), \
- .offset = __genradix_idx_to_offset((_radix), (_idx)),\
- })
+ .offset = _offset, \
+ }; \
+})
void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
@@ -394,9 +412,11 @@ int __genradix_prealloc(struct __genradix *, size_t, gfp_t);
* Returns 0 on success, -ENOMEM on failure
*/
#define genradix_prealloc(_radix, _nr, _gfp) \
- __genradix_prealloc(&(_radix)->tree, \
- __genradix_idx_to_offset(_radix, _nr + 1),\
- _gfp)
-
+({ \
+ size_t _offset; \
+ !__genradix_idx_to_offset(_radix, _nr + 1, &_offset) \
+ ? __genradix_prealloc(&(_radix)->tree, _offset, _gfp) \
+ : -ENOMEM; \
+})
#endif /* _LINUX_GENERIC_RADIX_TREE_H */
--
2.51.0
next prev parent reply other threads:[~2025-10-12 21:24 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-10-12 21:24 [PATCH v2 0/8] bcachefs out-of-tree series Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 1/8] closures: Improve closure_put_after_sub_checks Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 2/8] closures: closure_sub() uses cmpxchg Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 3/8] closures: CLOSURE_SLEEPING Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 4/8] closures: kill closure.closure_get_happened Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 5/8] lib: Give closures, min_heap config opts names Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 6/8] lib: Give XOR_BLOCKS, RAID6_PQ " Kent Overstreet
2025-10-12 21:24 ` [PATCH v2 7/8] lib: Give compression, checksum, crypto " Kent Overstreet
2025-10-12 21:24 ` Kent Overstreet [this message]
2025-10-13 6:38 ` [PATCH v2 0/8] bcachefs out-of-tree series Christoph Hellwig
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20251012212414.3225948-9-kent.overstreet@linux.dev \
--to=kent.overstreet@linux.dev \
--cc=akpm@linux-foundation.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox