Skip to contentSkip to conversation

dlm_controld: update rbtree implementation

PATCH New Alexander Aring 1 participant 3 messages Aug 21, 2023

lore
Share & tools
lore
#0 lore raw

PATCH 1/3 dlm_controld: update rbtree implementation

This patch updates the rbtree implementation taken from the Linux kernel.

---
 README.license                  |   3 +
 dlm_controld/linux_helpers.h    |  11 +
 dlm_controld/list.h             |   1 -
 dlm_controld/rbtree.c           | 724 +++++++++++++++++++++-----------
 dlm_controld/rbtree.h           | 393 ++++++++++++-----
 dlm_controld/rbtree_augmented.h | 303 +++++++++++++
 dlm_controld/rbtree_types.h     |  34 ++
 7 files changed, 1097 insertions(+), 372 deletions(-)
 create mode 100644 dlm_controld/linux_helpers.h
 create mode 100644 dlm_controld/rbtree_augmented.h
 create mode 100644 dlm_controld/rbtree_types.h
README.license +3 -0
index ededf669..d53f5894 100644
@@ -7,10 +7,13 @@ libdlm/libdlm_internal.h
 GPLv2
 
 dlm_controld/list.h (copied from linux kernel)
+dlm_controld/linux_helpers.h (various GPLv2 functions copied from linux kernel)
 
 GPLv2+
 
 dlm_controld/rbtree.c (copied from linux kernel)
 dlm_controld/rbtree.h (copied from linux kernel)
+dlm_controld/rbtree_augmented.h (copied from linux kernel)
+dlm_controld/rbtree_types.h (copied from linux kernel)
 all other original files
 
dlm_controld/linux_helpers.h new file +11 -0
new file mode 100644
index 00000000..5ef13466
@@ -0,0 +1,11 @@
+/*  Copied from linux kernel */
+
+#ifndef __DLM_LINUX_HELPERS__
+#define __DLM_LINUX_HELPERS__
+
+#define WRITE_ONCE(x, val)				\
+do {							\
+	*(volatile typeof(x) *)&(x) = (val);		\
+} while (0)
+
+#endif /* __DLM_LINUX_HELPERS__ */
dlm_controld/list.h +0 -1
index 8100cbc7..a2a5e5f3 100644
@@ -15,7 +15,6 @@
 	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 	(type *)( (char *)__mptr - offsetof(type,member) );})
 
-
 /*
  * These are non-NULL pointers that will result in page faults
  * under normal circumstances, used to verify that nobody uses
dlm_controld/rbtree.c +468 -256

816 lines not on this page · raw message

dlm_controld/rbtree.h +278 -115

436 lines not on this page · raw message

dlm_controld/rbtree_augmented.h new file +303 -0

303 lines not on this page · raw message

dlm_controld/rbtree_types.h new file +34 -0
new file mode 100644
index 00000000..d6ed9045
@@ -0,0 +1,34 @@
+/* Copied from linux/include/linux/rbtree_types.h */
+#ifndef _LINUX_RBTREE_TYPES_H
+#define _LINUX_RBTREE_TYPES_H
+
+struct rb_node {
+	unsigned long  __rb_parent_color;
+	struct rb_node *rb_right;
+	struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+/* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root {
+	struct rb_node *rb_node;
+};
+
+/*
+ * Leftmost-cached rbtrees.
+ *
+ * We do not cache the rightmost node based on footprint
+ * size vs number of potential users that could benefit
+ * from O(1) rb_last(). Just not worth it, users that want
+ * this feature can always implement the logic explicitly.
+ * Furthermore, users that want to cache both pointers may
+ * find it a bit asymmetric, but that's ok.
+ */
+struct rb_root_cached {
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
+};
+
+#define RB_ROOT (struct rb_root) { NULL, }
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
+
+#endif
Signature · 1 line
2.31.1
#1 lore raw

PATCH 2/3 dlm_controld: update container_of() implementation

This patch updates the container_of() implementation taken from the Linux kernel.

We need to turn off -Wpointer-arith as the new container_of() implementation does void pointer artihmetic as shown by this example warning:

linux_helpers.h:43:26: warning: pointer of type ‘void *’ used in arithmetic [-Wpointer-arith]

---
 dlm_controld/Makefile        |  2 +-
 dlm_controld/linux_helpers.h | 36 ++++++++++++++++++++++++++++++++++++
 dlm_controld/list.h          | 12 +-----------
 dlm_controld/rbtree.h        |  2 +-
 4 files changed, 39 insertions(+), 13 deletions(-)
dlm_controld/Makefile +1 -1
index 28b6bb0a..328a64ba 100644
@@ -38,7 +38,7 @@ LIB_SOURCE = lib.c
 
 CFLAGS += -D_GNU_SOURCE -O2 -ggdb \
 	-Wall -Wformat -Wformat-security -Wmissing-prototypes -Wnested-externs \
-	-Wpointer-arith -Wextra -Wshadow -Wcast-align -Wwrite-strings \
+	-Wextra -Wshadow -Wcast-align -Wwrite-strings \
 	-Waggregate-return -Wstrict-prototypes -Winline -Wredundant-decls \
 	-Wno-sign-compare -Wno-unused-parameter -Wp,-D_FORTIFY_SOURCE=2 \
 	-fexceptions -fasynchronous-unwind-tables -fdiagnostics-show-option \
dlm_controld/linux_helpers.h +36 -0
index 5ef13466..09705cff 100644
@@ -3,6 +3,42 @@
 #ifndef __DLM_LINUX_HELPERS__
 #define __DLM_LINUX_HELPERS__
 
+/*
+ * static_assert - check integer constant expression at build time
+ *
+ * static_assert() is a wrapper for the C11 _Static_assert, with a
+ * little macro magic to make the message optional (defaulting to the
+ * stringification of the tested expression).
+ *
+ * Contrary to BUILD_BUG_ON(), static_assert() can be used at global
+ * scope, but requires the expression to be an integer constant
+ * expression (i.e., it is not enough that __builtin_constant_p() is
+ * true for expr).
+ *
+ * Also note that BUILD_BUG_ON() fails the build if the condition is
+ * true, while static_assert() fails the build if the expression is
+ * false.
+ */
+#define static_assert(expr, ...) __static_assert(expr, ##__VA_ARGS__, #expr)
+#define __static_assert(expr, msg, ...) _Static_assert(expr, msg)
+
+#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ * WARNING: any const qualifier of @ptr is lost.
+ */
+#define container_of(ptr, type, member) ({				\
+	void *__mptr = (void *)(ptr);					\
+	static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
+		      __same_type(*(ptr), void),			\
+		      "pointer type mismatch in container_of()");	\
+	((type *)(__mptr - offsetof(type, member))); })
+
 #define WRITE_ONCE(x, val)				\
 do {							\
 	*(volatile typeof(x) *)&(x) = (val);		\
dlm_controld/list.h +1 -11
index a2a5e5f3..e9df2ef2 100644
@@ -3,17 +3,7 @@
 #ifndef _LINUX_LIST_H
 #define _LINUX_LIST_H
 
-/**
- * container_of - cast a member of a structure out to the containing structure
- *
- * @ptr:        the pointer to the member.
- * @type:       the type of the container struct this is embedded in.
- * @member:     the name of the member within the struct.
- *
- */
-#define container_of(ptr, type, member) ({                      \
-	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
-	(type *)( (char *)__mptr - offsetof(type,member) );})
+#include "linux_helpers.h"
 
 /*
  * These are non-NULL pointers that will result in page faults
dlm_controld/rbtree.h +1 -1
index ddb86ff6..48b6e32f 100644
@@ -20,7 +20,7 @@
 #include <stdbool.h>
 #include <string.h>
 
-#include "list.h"
+#include "linux_helpers.h"
 #include "rbtree_types.h"
 
 #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
Signature · 1 line
2.31.1
#2 lore raw

PATCH 3/3 dlm_controld: update list implementation

In reply to Alexander Aring

This patch updates the list implementation taken from the Linux kernel. There are new list manipulation functions introduced that could be became useful later.

---
 dlm_controld/linux_helpers.h |   7 +
 dlm_controld/list.h          | 667 ++++++++++++++++++++++++++++++-----
 2 files changed, 576 insertions(+), 98 deletions(-)
dlm_controld/linux_helpers.h +7 -0
index 09705cff..f959cf55 100644
@@ -24,6 +24,11 @@
 
 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
 
+#define POISON_POINTER_DELTA 0xdeadbeef
+
+#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
+#define LIST_POISON2  ((void *) 0x122 + POISON_POINTER_DELTA)
+
 /**
  * container_of - cast a member of a structure out to the containing structure
  * @ptr:	the pointer to the member.
@@ -39,6 +44,8 @@
 		      "pointer type mismatch in container_of()");	\
 	((type *)(__mptr - offsetof(type, member))); })
 
+#define READ_ONCE(x)  (*(const volatile typeof(x) *)&(x))
+
 #define WRITE_ONCE(x, val)				\
 do {							\
 	*(volatile typeof(x) *)&(x) = (val);		\
dlm_controld/list.h +569 -98

846 lines not on this page · raw message

Signature · 1 line
2.31.1