dlm_controld: update rbtree implementation
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
@@ -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
@@ -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
@@ -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
@@ -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
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
@@ -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
@@ -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
@@ -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
@@ -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
PATCH 3/3 dlm_controld: update list implementation
In reply to Alexander AringThis 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
@@ -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