| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20251012212414.3225948-9-kent.overstreet@linux.dev>
Date: Sun, 12 Oct 2025 17:24:11 -0400
From: Kent Overstreet <kent.overstreet@...ux.dev>
To: akpm@...ux-foundation.org
Cc: linux-kernel@...r.kernel.org,
Kent Overstreet <kent.overstreet@...ux.dev>
Subject: [PATCH v2 8/8] generix-radix-tree: Overflow checking
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@...ux.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
Powered by blists - more mailing lists