linux-kernel - [PATCH] maple_tree: Fix 32b parent pointers

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Date:   Tue, 17 May 2022 15:22:20 +0000
From:   Liam Howlett <liam.howlett@...cle.com>
To:     "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        "linux-next@...r.kernel.org" <linux-next@...r.kernel.org>
Subject: [PATCH] maple_tree: Fix 32b parent pointers

32 bit parent pointers need an extra bit to account for increased slot
count.  Update the constants and documentation to use the remaining high
bit.

Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>
---
 include/linux/maple_tree.h |  2 +-
 lib/maple_tree.c           | 14 +++++++-------
 2 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index fb689d628cf7..d044140a3a2d 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -37,7 +37,7 @@
 #define MAPLE_NODE_SLOTS	63	/* 256 bytes including ->parent */
 #define MAPLE_RANGE64_SLOTS	32	/* 256 bytes */
 #define MAPLE_ARANGE64_SLOTS	21	/* 240 bytes */
-#define MAPLE_ARANGE64_META_MAX	22	/* Out of range for metadata */
+#define MAPLE_ARANGE64_META_MAX	31	/* Out of range for metadata */
 #define MAPLE_ALLOC_SLOTS	(MAPLE_NODE_SLOTS - 2)
 #endif /* defined(CONFIG_64BIT) || defined(BUILD_VDSO32_64) */
 
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 751aafd01c42..8cde2edcb4f8 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -354,7 +354,7 @@ static inline bool mt_is_alloc(struct maple_tree *mt)
 /*
  * The Parent Pointer
  * Excluding root, the parent pointer is 256B aligned like all other tree nodes.
- * When storing a 32 or 64 bit values, the offset can fit into 4 bits.  The 16
+ * When storing a 32 or 64 bit values, the offset can fit into 5 bits.  The 16
  * bit values need an extra bit to store the offset.  This extra bit comes from
  * a reuse of the last bit in the node type.  This is possible by using bit 1 to
  * indicate if bit 2 is part of the type or the slot.
@@ -366,19 +366,19 @@ static inline bool mt_is_alloc(struct maple_tree *mt)
  *  0x110 = 64 bit nodes
  *
  * Slot size and alignment
- *  0x??1 : Root
- *  0x?00 : 16 bit values, type in 0-1, slot in 2-6
- *  0x010 : 32 bit values, type in 0-2, slot in 3-6
- *  0x110 : 64 bit values, type in 0-2, slot in 3-6
+ *  0b??1 : Root
+ *  0b?00 : 16 bit values, type in 0-1, slot in 2-7
+ *  0b010 : 32 bit values, type in 0-2, slot in 3-7
+ *  0b110 : 64 bit values, type in 0-2, slot in 3-7
  */
 
 #define MAPLE_PARENT_ROOT		0x01
 
 #define MAPLE_PARENT_SLOT_SHIFT		0x03
-#define MAPLE_PARENT_SLOT_MASK		0x78
+#define MAPLE_PARENT_SLOT_MASK		0xF8
 
 #define MAPLE_PARENT_16B_SLOT_SHIFT	0x02
-#define MAPLE_PARENT_16B_SLOT_MASK	0x7C
+#define MAPLE_PARENT_16B_SLOT_MASK	0xFC
 
 #define MAPLE_PARENT_RANGE64		0x06
 #define MAPLE_PARENT_RANGE32		0x04
-- 
2.35.1