| 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: <20240607042615.2069840-19-chengzhihao1@huawei.com>
Date: Fri, 7 Jun 2024 12:24:43 +0800
From: Zhihao Cheng <chengzhihao1@...wei.com>
To: <richard@....at>, <david.oberhollenzer@...ma-star.at>,
<miquel.raynal@...tlin.com>, <yi.zhang@...wei.com>, <xiangyang3@...wei.com>,
<huangxiaojia2@...wei.com>
CC: <linux-mtd@...ts.infradead.org>, <linux-kernel@...r.kernel.org>
Subject: [RFC PATCH mtd-utils 018/110] mtd-utils: Extract rbtree implementation to common lib
Current rbtree implementation code is put under jffs utils, extract it
into common lib, and add more rbtree operations(eg. rb_first_postorder,
rb_next_postorder, etc.).
This is a preparation for replacing implementation of UBIFS utils with
linux kernel libs.
Signed-off-by: Zhihao Cheng <chengzhihao1@...wei.com>
---
{jffsX-utils => include}/rbtree.h | 32 ++++++++++++++++++++++++++++++++
jffsX-utils/Makemodule.am | 6 ++----
lib/Makemodule.am | 2 ++
{jffsX-utils => lib}/rbtree.c | 38 ++++++++++++++++++++++++++++++++++++++
4 files changed, 74 insertions(+), 4 deletions(-)
rename {jffsX-utils => include}/rbtree.h (79%)
rename {jffsX-utils => lib}/rbtree.c (90%)
diff --git a/jffsX-utils/rbtree.h b/include/rbtree.h
similarity index 79%
rename from jffsX-utils/rbtree.h
rename to include/rbtree.h
index 0d77b65f..89926e74 100644
--- a/jffsX-utils/rbtree.h
+++ b/include/rbtree.h
@@ -155,6 +155,38 @@ extern struct rb_node *rb_prev(struct rb_node *);
extern struct rb_node *rb_first(struct rb_root *);
extern struct rb_node *rb_last(struct rb_root *);
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
+
+#define rb_entry_safe(ptr, type, member) \
+ ({ typeof(ptr) ____ptr = (ptr); \
+ ____ptr ? rb_entry(____ptr, type, member) : NULL; \
+ })
+
+/**
+ * rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of
+ * given type allowing the backing memory of @pos to be invalidated
+ *
+ * @pos: the 'type *' to use as a loop cursor.
+ * @n: another 'type *' to use as temporary storage
+ * @root: 'rb_root *' of the rbtree.
+ * @field: the name of the rb_node field within 'type'.
+ *
+ * rbtree_postorder_for_each_entry_safe() provides a similar guarantee as
+ * list_for_each_entry_safe() and allows the iteration to continue independent
+ * of changes to @pos by the body of the loop.
+ *
+ * Note, however, that it cannot handle other modifications that re-order the
+ * rbtree it is iterating over. This includes calling rb_erase() on @pos, as
+ * rb_erase() may rebalance the tree, causing us to miss some nodes.
+ */
+#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
+ for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
+ pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
+ typeof(*pos), field); 1; }); \
+ pos = n)
+
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root);
diff --git a/jffsX-utils/Makemodule.am b/jffsX-utils/Makemodule.am
index 2374b858..4ae4c57b 100644
--- a/jffsX-utils/Makemodule.am
+++ b/jffsX-utils/Makemodule.am
@@ -1,16 +1,14 @@
mkfs_jffs2_SOURCES = \
jffsX-utils/mkfs.jffs2.c \
- jffsX-utils/rbtree.h \
jffsX-utils/compr.h \
- jffsX-utils/rbtree.c \
jffsX-utils/compr.c \
jffsX-utils/compr_rtime.c \
jffsX-utils/compr.h \
- jffsX-utils/rbtree.h \
jffsX-utils/summary.h \
include/linux/jffs2.h \
include/mtd/jffs2-user.h \
- include/list.h
+ include/list.h \
+ include/rbtree.h
mkfs_jffs2_LDADD = libmtd.a $(ZLIB_LIBS) $(LZO_LIBS)
mkfs_jffs2_CPPFLAGS = $(AM_CPPFLAGS) $(ZLIB_CFLAGS) $(LZO_CFLAGS)
diff --git a/lib/Makemodule.am b/lib/Makemodule.am
index 7f890daa..441532de 100644
--- a/lib/Makemodule.am
+++ b/lib/Makemodule.am
@@ -7,6 +7,8 @@ libmtd_a_SOURCES = \
include/common.h \
lib/list_sort.c \
include/list.h \
+ lib/rbtree.c \
+ include/rbtree.h \
lib/libcrc32.c \
include/crc32.h \
lib/libmtd_legacy.c \
diff --git a/jffsX-utils/rbtree.c b/lib/rbtree.c
similarity index 90%
rename from jffsX-utils/rbtree.c
rename to lib/rbtree.c
index 329e0986..32c87556 100644
--- a/jffsX-utils/rbtree.c
+++ b/lib/rbtree.c
@@ -388,3 +388,41 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+ for (;;) {
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+ else
+ return (struct rb_node *)node;
+ }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+ const struct rb_node *parent;
+ if (!node)
+ return NULL;
+ parent = rb_parent(node);
+
+ /* If we're sitting on node, we've already seen our children */
+ if (parent && node == parent->rb_left && parent->rb_right) {
+ /* If we are the parent's left node, go to the parent's right
+ * node then all the way down to the left */
+ return rb_left_deepest_node(parent->rb_right);
+ } else
+ /* Otherwise we are the parent's right node, and the parent
+ * should be next */
+ return (struct rb_node *)parent;
+}
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+ if (!root->rb_node)
+ return NULL;
+
+ return rb_left_deepest_node(root->rb_node);
+}
--
2.13.6
Powered by blists - more mailing lists