From dff8625703a7f2ab4a8877b1366210327650b56d Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Fri, 27 May 2011 20:39:52 -0400 Subject: [PATCH] Reimplement basic non-RCU rbtree Use as a starting point for RCU rbtree iterative development/test starting from this non-RCU implementation. Signed-off-by: Mathieu Desnoyers --- Makefile.am | 6 +- tests/Makefile.am | 6 +- tests/test_urcu_rbtree.c | 475 +++++++++++++++++++++++++++++++++++ urcu-rbtree.c | 521 +++++++++++++++++++++++++++++++++++++++ urcu/rcurbtree.h | 147 +++++++++++ 5 files changed, 1152 insertions(+), 3 deletions(-) create mode 100644 tests/test_urcu_rbtree.c create mode 100644 urcu-rbtree.c create mode 100644 urcu/rcurbtree.h diff --git a/Makefile.am b/Makefile.am index 7956e7e..d51ff7a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -12,7 +12,7 @@ nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \ urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h \ urcu/wfqueue-static.h urcu/wfstack-static.h \ urcu/rculfqueue-static.h urcu/rculfstack-static.h \ - urcu/urcu_ref.h + urcu/urcu_ref.h urcu/rcurbtree.h nobase_nodist_include_HEADERS = urcu/arch.h urcu/uatomic_arch.h urcu/config.h EXTRA_DIST = $(top_srcdir)/urcu/arch_*.h $(top_srcdir)/urcu/uatomic_arch_*.h \ @@ -31,7 +31,8 @@ endif lib_LTLIBRARIES = liburcu.la liburcu-qsbr.la liburcu-mb.la liburcu-signal.la \ liburcu-bp.la liburcu-defer.la liburcu-call.la \ - libwfqueue.la libwfstack.la librculfqueue.la librculfstack.la + libwfqueue.la libwfstack.la librculfqueue.la \ + liburcu-rbtree.la librculfstack.la liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT) @@ -52,3 +53,4 @@ libwfqueue_la_SOURCES = wfqueue.c $(COMPAT) libwfstack_la_SOURCES = wfstack.c $(COMPAT) librculfqueue_la_SOURCES = rculfqueue.c $(COMPAT) librculfstack_la_SOURCES = rculfstack.c $(COMPAT) +liburcu_rbtree_la_SOURCES = urcu-rbtree.c $(COMPAT) diff --git a/tests/Makefile.am b/tests/Makefile.am index 3c025a4..0abfb8b 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -15,7 +15,8 @@ noinst_PROGRAMS = test_urcu test_urcu_dynamic_link test_urcu_timing \ test_urcu_bp test_urcu_bp_dynamic_link test_cycles_per_loop \ test_urcu_lfq test_urcu_wfq test_urcu_lfs test_urcu_wfs \ test_urcu_wfq_dynlink test_urcu_wfs_dynlink \ - test_urcu_lfq_dynlink test_urcu_lfs_dynlink + test_urcu_lfq_dynlink test_urcu_lfs_dynlink \ + test_urcu_rbtree noinst_HEADERS = rcutorture.h if COMPAT_ARCH @@ -47,6 +48,7 @@ WFQUEUE_LIB=$(top_builddir)/libwfqueue.la WFSTACK_LIB=$(top_builddir)/libwfstack.la RCULFQUEUE_LIB=$(top_builddir)/librculfqueue.la RCULFSTACK_LIB=$(top_builddir)/librculfstack.la +URCU_RBTREE=$(URCU_DEFER) $(top_srcdir)/urcu-rbtree.c EXTRA_DIST = $(top_srcdir)/tests/api_*.h @@ -179,6 +181,8 @@ test_urcu_wfs_dynlink_SOURCES = test_urcu_wfs.c test_urcu_wfs_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS) test_urcu_wfs_dynlink_LDADD = $(WFSTACK_LIB) +test_urcu_rbtree_SOURCES = test_urcu_rbtree.c $(URCU_RBTREE) + urcutorture.c: api.h check-am: diff --git a/tests/test_urcu_rbtree.c b/tests/test_urcu_rbtree.c new file mode 100644 index 0000000..7f505b1 --- /dev/null +++ b/tests/test_urcu_rbtree.c @@ -0,0 +1,475 @@ +/* + * test_urcu_rbtree.c + * + * Userspace RCU library - test program for RB tree + * + * Copyright February 2010 - Mathieu Desnoyers + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#define _GNU_SOURCE +#ifndef DYNAMIC_LINK_TEST +#define _LGPL_SOURCE +#else +#define debug_yield_read() +#endif +#include "../config.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +/* hardcoded number of CPUs */ +#define NR_CPUS 16384 + +/* number of insert/delete */ +#define NR_RAND 4 + +#if defined(_syscall0) +_syscall0(pid_t, gettid) +#elif defined(__NR_gettid) +static inline pid_t gettid(void) +{ + return syscall(__NR_gettid); +} +#else +#warning "use pid as tid" +static inline pid_t gettid(void) +{ + return getpid(); +} +#endif + +#include +#include +#include + +/* TODO: error handling testing for -ENOMEM */ +struct rcu_rbtree_node *rbtree_alloc(void) +{ + return calloc(1, sizeof(struct rcu_rbtree_node)); +} + +void rbtree_free(void *node) +{ + free(node); +} + +int tree_comp(void *a, void *b) +{ + if ((unsigned long)a < (unsigned long)b) + return -1; + else if ((unsigned long)a > (unsigned long)b) + return 1; + else + return 0; +} + +static DEFINE_RCU_RBTREE(rbtree, tree_comp, rbtree_alloc, rbtree_free); + +static volatile int test_go, test_stop; + +static unsigned long wdelay; + +static unsigned long duration; + +/* read-side C.S. duration, in loops */ +static unsigned long rduration; + +/* write-side C.S. duration, in loops */ +static unsigned long wduration; + +static inline void loop_sleep(unsigned long l) +{ + while(l-- != 0) + caa_cpu_relax(); +} + +static int verbose_mode; + +#define printf_verbose(fmt, args...) \ + do { \ + if (verbose_mode) \ + printf(fmt, args); \ + } while (0) + +static unsigned int cpu_affinities[NR_CPUS]; +static unsigned int next_aff = 0; +static int use_affinity = 0; + +pthread_mutex_t affinity_mutex = PTHREAD_MUTEX_INITIALIZER; + +#ifndef HAVE_CPU_SET_T +typedef unsigned long cpu_set_t; +# define CPU_ZERO(cpuset) do { *(cpuset) = 0; } while(0) +# define CPU_SET(cpu, cpuset) do { *(cpuset) |= (1UL << (cpu)); } while(0) +#endif + +static void set_affinity(void) +{ + cpu_set_t mask; + int cpu; + int ret; + + if (!use_affinity) + return; + +#if HAVE_SCHED_SETAFFINITY + ret = pthread_mutex_lock(&affinity_mutex); + if (ret) { + perror("Error in pthread mutex lock"); + exit(-1); + } + cpu = cpu_affinities[next_aff++]; + ret = pthread_mutex_unlock(&affinity_mutex); + if (ret) { + perror("Error in pthread mutex unlock"); + exit(-1); + } + + CPU_ZERO(&mask); + CPU_SET(cpu, &mask); +#if SCHED_SETAFFINITY_ARGS == 2 + sched_setaffinity(0, &mask); +#else + sched_setaffinity(0, sizeof(mask), &mask); +#endif +#endif /* HAVE_SCHED_SETAFFINITY */ +} + +/* + * returns 0 if test should end. + */ +static int test_duration_write(void) +{ + return !test_stop; +} + +static int test_duration_read(void) +{ + return !test_stop; +} + +static unsigned long long __thread nr_writes; +static unsigned long long __thread nr_reads; + +static unsigned int nr_readers; +static unsigned int nr_writers; + +pthread_mutex_t rcu_copy_mutex = PTHREAD_MUTEX_INITIALIZER; + +void rcu_copy_mutex_lock(void) +{ + int ret; + ret = pthread_mutex_lock(&rcu_copy_mutex); + if (ret) { + perror("Error in pthread mutex lock"); + exit(-1); + } +} + +void rcu_copy_mutex_unlock(void) +{ + int ret; + + ret = pthread_mutex_unlock(&rcu_copy_mutex); + if (ret) { + perror("Error in pthread mutex unlock"); + exit(-1); + } +} + +void *thr_reader(void *_count) +{ + unsigned long long *count = _count; + + printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", + "reader", pthread_self(), (unsigned long)gettid()); + + set_affinity(); + + rcu_register_thread(); + + while (!test_go) + { + } + cmm_smp_mb(); + + for (;;) { + rcu_read_lock(); + + debug_yield_read(); + if (unlikely(rduration)) + loop_sleep(rduration); + rcu_read_unlock(); + nr_reads++; + if (unlikely(!test_duration_read())) + break; + } + + rcu_unregister_thread(); + + /* test extra thread registration */ + rcu_register_thread(); + rcu_unregister_thread(); + + *count = nr_reads; + printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", + "reader", pthread_self(), (unsigned long)gettid()); + return ((void*)1); + +} + +void *thr_writer(void *_count) +{ + unsigned long long *count = _count; + struct rcu_rbtree_node *node; + void *key[NR_RAND]; + int i; + + printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", + "writer", pthread_self(), (unsigned long)gettid()); + + set_affinity(); + + rcu_defer_register_thread(); + + while (!test_go) + { + } + cmm_smp_mb(); + + for (;;) { + rcu_copy_mutex_lock(); + + for (i = 0; i < NR_RAND; i++) { + node = rbtree_alloc(); + key[i] = (void *)(unsigned long)(rand() % 2048); + node->key = key[i]; + rcu_rbtree_insert(&rbtree, node); + } + + if (unlikely(wduration)) + loop_sleep(wduration); + + for (i = 0; i < NR_RAND; i++) { +#if 0 + node = rcu_rbtree_min(rbtree, rbtree->root); + while (!rcu_rbtree_is_nil(node)) { + printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ", + (unsigned long)node->key, + node->p->key, + node->right->key, + node->left->key, + node->color ? "red" : "black", + node->pos ? "right" : "left", + node->nil ? "nil" : ""); + node = rcu_rbtree_next(rbtree, node); + } + printf("\n"); +#endif + node = rcu_rbtree_search(&rbtree, rbtree.root, key[i]); + assert(!rcu_rbtree_is_nil(node)); + rcu_rbtree_remove(&rbtree, node); + defer_rcu((void (*)(void *))rbtree_free, node); + } + + rcu_copy_mutex_unlock(); + nr_writes++; + if (unlikely(!test_duration_write())) + break; + if (unlikely(wdelay)) + loop_sleep(wdelay); + } + + rcu_defer_unregister_thread(); + + printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", + "writer", pthread_self(), (unsigned long)gettid()); + *count = nr_writes; + return ((void*)2); +} + +void show_usage(int argc, char **argv) +{ + printf("Usage : %s nr_readers nr_writers duration (s)", argv[0]); +#ifdef DEBUG_YIELD + printf(" [-r] [-w] (yield reader and/or writer)"); +#endif + printf(" [-d delay] (writer period (us))"); + printf(" [-c duration] (reader C.S. duration (in loops))"); + printf(" [-e duration] (writer C.S. duration (in loops))"); + printf(" [-v] (verbose output)"); + printf(" [-a cpu#] [-a cpu#]... (affinity)"); + printf("\n"); +} + +int main(int argc, char **argv) +{ + int err; + pthread_t *tid_reader, *tid_writer; + void *tret; + unsigned long long *count_reader, *count_writer; + unsigned long long tot_reads = 0, tot_writes = 0; + int i, a; + + if (argc < 4) { + show_usage(argc, argv); + return -1; + } + + err = sscanf(argv[1], "%u", &nr_readers); + if (err != 1) { + show_usage(argc, argv); + return -1; + } + + err = sscanf(argv[2], "%u", &nr_writers); + if (err != 1) { + show_usage(argc, argv); + return -1; + } + + err = sscanf(argv[3], "%lu", &duration); + if (err != 1) { + show_usage(argc, argv); + return -1; + } + + for (i = 4; i < argc; i++) { + if (argv[i][0] != '-') + continue; + switch (argv[i][1]) { +#ifdef DEBUG_YIELD + case 'r': + yield_active |= YIELD_READ; + break; + case 'w': + yield_active |= YIELD_WRITE; + break; +#endif + case 'a': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + a = atoi(argv[++i]); + cpu_affinities[next_aff++] = a; + use_affinity = 1; + printf_verbose("Adding CPU %d affinity\n", a); + break; + case 'c': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + rduration = atol(argv[++i]); + break; + case 'd': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + wdelay = atol(argv[++i]); + break; + case 'e': + if (argc < i + 2) { + show_usage(argc, argv); + return -1; + } + wduration = atol(argv[++i]); + break; + case 'v': + verbose_mode = 1; + break; + } + } + + printf_verbose("running test for %lu seconds, %u readers, %u writers.\n", + duration, nr_readers, nr_writers); + printf_verbose("Writer delay : %lu loops.\n", wdelay); + printf_verbose("Reader duration : %lu loops.\n", rduration); + printf_verbose("thread %-6s, thread id : %lx, tid %lu\n", + "main", pthread_self(), (unsigned long)gettid()); + + tid_reader = malloc(sizeof(*tid_reader) * nr_readers); + tid_writer = malloc(sizeof(*tid_writer) * nr_writers); + count_reader = malloc(sizeof(*count_reader) * nr_readers); + count_writer = malloc(sizeof(*count_writer) * nr_writers); + + srand(time(NULL)); + + next_aff = 0; + + for (i = 0; i < nr_readers; i++) { + err = pthread_create(&tid_reader[i], NULL, thr_reader, + &count_reader[i]); + if (err != 0) + exit(1); + } + for (i = 0; i < nr_writers; i++) { + err = pthread_create(&tid_writer[i], NULL, thr_writer, + &count_writer[i]); + if (err != 0) + exit(1); + } + + cmm_smp_mb(); + + test_go = 1; + + sleep(duration); + + test_stop = 1; + + for (i = 0; i < nr_readers; i++) { + err = pthread_join(tid_reader[i], &tret); + if (err != 0) + exit(1); + tot_reads += count_reader[i]; + } + for (i = 0; i < nr_writers; i++) { + err = pthread_join(tid_writer[i], &tret); + if (err != 0) + exit(1); + tot_writes += count_writer[i]; + } + + printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads, + tot_writes); + printf("SUMMARY %-25s testdur %4lu nr_readers %3u rdur %6lu wdur %6lu " + "nr_writers %3u " + "wdelay %6lu nr_reads %12llu nr_writes %12llu nr_ops %12llu\n", + argv[0], duration, nr_readers, rduration, wduration, + nr_writers, wdelay, tot_reads, tot_writes, + tot_reads + tot_writes); + free(tid_reader); + free(tid_writer); + free(count_reader); + free(count_writer); + return 0; +} diff --git a/urcu-rbtree.c b/urcu-rbtree.c new file mode 100644 index 0000000..df9e506 --- /dev/null +++ b/urcu-rbtree.c @@ -0,0 +1,521 @@ +/* + * urcu-rbtree.c + * + * Userspace RCU library - Red-Black Tree + * + * Copyright (c) 2010 Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Implementation of RCU-adapted data structures and operations based on the RB + * tree algorithms found in chapter 12 of: + * + * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and + * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT + * Press, September 2009. + */ + +#define _BSD_SOURCE +#define _LGPL_SOURCE + +#include +#include +#include + +#include +#include +#include + +#define DEBUG + +#ifdef DEBUG +#define dbg_printf(args...) printf(args) +#else +#define dbg_printf(args...) +#endif + +/* + * TODO + * Deal with memory allocation errors. + * Can be ensured by reserving a pool of memory entries before doing the + * insertion, which will have to be function of number of + * transplantations/rotations required for the operation. + */ + +static +void show_tree(struct rcu_rbtree *rbtree) +{ + struct rcu_rbtree_node *node; + + node = rcu_rbtree_min(rbtree, rbtree->root); + while (!rcu_rbtree_is_nil(node)) { + printf("{ 0x%lX p:%lX r:%lX l:%lX %s %s %s} ", + (unsigned long)node->key, + node->p->key, + node->right->key, + node->left->key, + node->color ? "red" : "black", + node->pos ? "right" : "left", + node->nil ? "nil" : ""); + node = rcu_rbtree_next(rbtree, node); + } + printf("\n"); +} + +static +struct rcu_rbtree_node *make_nil(struct rcu_rbtree *rbtree) +{ + return &rbtree->nil_node; +} + +/* + * Iterative rbtree search. + */ +struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x, + void *k) +{ + x = rcu_dereference(x); + + while (!rcu_rbtree_is_nil(x) && k != x->key) { + if (rbtree->comp(k, x->key) < 0) + x = rcu_dereference(x->left); + else + x = rcu_dereference(x->right); + } + return x; +} + +struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *xl; + + x = rcu_dereference(x); + + if (rcu_rbtree_is_nil(x)) + return x; + + while (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) + x = xl; + return x; +} + +struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *xr; + + x = rcu_dereference(x); + + if (rcu_rbtree_is_nil(x)) + return x; + + while (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right))) + x = xr; + return x; +} + +/* + * FIXME: + * Updates should wait for a grace period between update of the + * redirect pointer and update of the parent child pointer. This is to make sure + * that no reference to the old entry exist. + */ + +/* + * next and prev need to have mutex held to ensure that parent pointer is + * coherent. + */ +struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *xr, *y, *yr; + + x = rcu_dereference(x); + + if (!rcu_rbtree_is_nil(xr = rcu_dereference(x->right))) + return rcu_rbtree_min(rbtree, xr); + y = rcu_dereference(x->p); + while (!rcu_rbtree_is_nil(y) && x->pos == IS_RIGHT) { + x = y; + y = rcu_dereference(y->p); + } + return y; +} + +struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *xl, *y, *yl; + + x = rcu_dereference(x); + + if (!rcu_rbtree_is_nil(xl = rcu_dereference(x->left))) + return rcu_rbtree_min(rbtree, xl); + y = rcu_dereference(x->p); + while (!rcu_rbtree_is_nil(y) && x->pos == IS_LEFT) { + x = y; + y = rcu_dereference(y->p); + } + return y; +} + +/* + * We have to ensure these assumptions are correct for prev/next + * traversal: + * + * with x being a right child, the assumption that: + * x->p->right == x + * or if x is a left child, the assumption that: + * x->p->left == x + * + * This explains why we have to allocate a vc copy of the node for left_rotate, + * right_rotate and transplant operations. + * + * We always ensure that the right/left child and correct parent is set in the + * node copies *before* we reparent the children and make the upper-level point + * to the copy. + */ + +/* RCU: copy x and y, atomically point to new versions. GC old. */ +/* Should be eventually followed by a cmm_smp_wmc() */ +/* Returns the new x. Previous x->right references are changed to yc. + * Previous y->left->right is changed to bc. */ + +static +struct rcu_rbtree_node *left_rotate(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *y; + struct rcu_rbtree_node *t; + + t = x->p; + y = x->right; + x->right = y->left; + if (!rcu_rbtree_is_nil(y->left)) { + y->left->p = x; + y->left->pos = IS_RIGHT; + } + y->p = x->p; + if (rcu_rbtree_is_nil(x->p)) + rbtree->root = y; + else if (x == x->p->left) { + x->p->left = y; + y->pos = IS_LEFT; + } else { + x->p->right = y; + y->pos = IS_RIGHT; + } + y->left = x; + x->pos = IS_LEFT; + x->p = y; + return t; +} + +static +struct rcu_rbtree_node *right_rotate(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + struct rcu_rbtree_node *y; + struct rcu_rbtree_node *t; + + t = x->p; + y = x->left; + x->left = y->right; + if (!rcu_rbtree_is_nil(y->right)) { + y->right->p = x; + y->right->pos = IS_LEFT; + } + y->p = x->p; + if (rcu_rbtree_is_nil(x->p)) + rbtree->root = y; + else if (x == x->p->right) { + x->p->right = y; + y->pos = IS_RIGHT; + } else { + x->p->left = y; + y->pos = IS_LEFT; + } + y->right = x; + x->pos = IS_RIGHT; + x->p = y; + return t; +} + +static void rcu_rbtree_insert_fixup(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *z) +{ + struct rcu_rbtree_node *y; + + dbg_printf("insert fixup %p\n", z->key); + + while (z->p->color == COLOR_RED) { + if (z->p == z->p->p->left) { + y = z->p->p->right; + if (y->color == COLOR_RED) { + z->p->color = COLOR_BLACK; + y->color = COLOR_BLACK; + z->p->p->color = COLOR_RED; + z = z->p->p; + } else { + if (z == z->p->right) { + z = z->p; + left_rotate(rbtree, z); + } + z->p->color = COLOR_BLACK; + z->p->p->color = COLOR_RED; + right_rotate(rbtree, z->p->p); + } + } else { + y = z->p->p->left; + if (y->color == COLOR_RED) { + z->p->color = COLOR_BLACK; + y->color = COLOR_BLACK; + z->p->p->color = COLOR_RED; + z = z->p->p; + } else { + if (z == z->p->left) { + z = z->p; + right_rotate(rbtree, z); + } + z->p->color = COLOR_BLACK; + z->p->p->color = COLOR_RED; + left_rotate(rbtree, z->p->p); + } + } + } + rbtree->root->color = COLOR_BLACK; +} + +/* + * rcu_rbtree_insert - Insert a node in the RCU rbtree + * + * Returns 0 on success, or < 0 on error. + */ +int rcu_rbtree_insert(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *z) +{ + struct rcu_rbtree_node *x, *y; + + dbg_printf("insert %p\n", z->key); + + y = make_nil(rbtree); + if (!rbtree->root) + rbtree->root = make_nil(rbtree); + x = rbtree->root; + while (!rcu_rbtree_is_nil(x)) { + y = x; + if (rbtree->comp(z->key, x->key) < 0) + x = x->left; + else + x = x->right; + } + + z->p = y; + + z->left = make_nil(rbtree); + z->right = make_nil(rbtree); + z->color = COLOR_RED; + z->nil = 0; + + if (rcu_rbtree_is_nil(y)) + z->pos = IS_RIGHT; /* arbitrary for root node */ + else if (rbtree->comp(z->key, y->key) < 0) + z->pos = IS_LEFT; + else + z->pos = IS_RIGHT; + + /* + * Order stores to z (children/parents) before stores that will make it + * visible to the rest of the tree. + */ + cmm_smp_wmb(); + + if (rcu_rbtree_is_nil(y)) + _CMM_STORE_SHARED(rbtree->root, z); + else if (rbtree->comp(z->key, y->key) < 0) + _CMM_STORE_SHARED(y->left, z); + else + _CMM_STORE_SHARED(y->right, z); + rcu_rbtree_insert_fixup(rbtree, z); + /* + * Make sure to commit all _CMM_STORE_SHARED() for non-coherent caches. + */ + cmm_smp_wmc(); + show_tree(rbtree); + + return 0; +} + +/* + * Transplant v into u position. + * Returns new copy of v. + */ +static struct rcu_rbtree_node * +rcu_rbtree_transplant(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *u, + struct rcu_rbtree_node *v) +{ + struct rcu_rbtree_node *vc; + + dbg_printf("transplant %p\n", v->key); + + if (rcu_rbtree_is_nil(u->p)) + rbtree->root = v; + else if (u == u->p->left) { + u->p->left = v; + v->pos = IS_LEFT; + } else { + u->p->right = v; + v->pos = IS_RIGHT; + } + v->p = u->p; + return v; +} + +static void rcu_rbtree_remove_fixup(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x) +{ + dbg_printf("remove fixup %p\n", x->key); + + while (x != rbtree->root && x->color == COLOR_BLACK) { + if (x == x->p->left) { + struct rcu_rbtree_node *w, *t; + + w = x->p->right; + + if (w->color == COLOR_RED) { + w->color == COLOR_BLACK; + x->p->color = COLOR_RED; + t = left_rotate(rbtree, x->p); + assert(x->p->left == t->left); + /* x is a left node, not copied by rotation */ + w = x->p->right; + } + if (w->left->color == COLOR_BLACK + && w->right->color == COLOR_BLACK) { + w->color = COLOR_RED; + x = x->p; + } else { + if (w->right->color == COLOR_BLACK) { + w->left->color = COLOR_BLACK; + w->color = COLOR_RED; + right_rotate(rbtree, w); + w = x->p->right; + } + w->color = x->p->color; + x->p->color = COLOR_BLACK; + w->right->color = COLOR_BLACK; + left_rotate(rbtree, x->p); + x = rbtree->root; + } + } else { + struct rcu_rbtree_node *w, *t; + + w = x->p->left; + + if (w->color == COLOR_RED) { + w->color == COLOR_BLACK; + x->p->color = COLOR_RED; + t = right_rotate(rbtree, x->p); + assert(x->p->right == t->right); + /* x is a right node, not copied by rotation */ + w = x->p->left; + } + if (w->right->color == COLOR_BLACK + && w->left->color == COLOR_BLACK) { + w->color = COLOR_RED; + x = x->p; + } else { + if (w->left->color == COLOR_BLACK) { + w->right->color = COLOR_BLACK; + w->color = COLOR_RED; + left_rotate(rbtree, w); + w = x->p->left; + } + w->color = x->p->color; + x->p->color = COLOR_BLACK; + w->left->color = COLOR_BLACK; + right_rotate(rbtree, x->p); + x = rbtree->root; + } + } + } + x->color = COLOR_BLACK; +} + +/* + * Returns the new copy of y->right. + * Delete z. All non-copied children left/right positions are unchanged. */ +static struct rcu_rbtree_node * +rcu_rbtree_remove_nonil(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *z, + struct rcu_rbtree_node *y) +{ + struct rcu_rbtree_node *x, *xc, *yc; + + dbg_printf("remove nonil %p\n", z->key); + show_tree(rbtree); + + x = y->right; + if (y->p == z) + x->p = y; + else { + rcu_rbtree_transplant(rbtree, y, y->right); + y->right = z->right; + y->right->p = y; + } + rcu_rbtree_transplant(rbtree, z, y); + y->left = z->left; + y->left->p = y; + y->color = z->color; + return x; +} + +int rcu_rbtree_remove(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *z) +{ + struct rcu_rbtree_node *x, *y; + unsigned int y_original_color; + + dbg_printf("remove %p\n", z->key); + show_tree(rbtree); + + y = z; + y_original_color = y->color; + + if (rcu_rbtree_is_nil(z->left)) { + x = rcu_rbtree_transplant(rbtree, z, z->right); + show_tree(rbtree); + } else if (rcu_rbtree_is_nil(z->right)) { + x = rcu_rbtree_transplant(rbtree, z, z->left); + show_tree(rbtree); + } else { + y = rcu_rbtree_min(rbtree, z->right); + y_original_color = y->color; + x = rcu_rbtree_remove_nonil(rbtree, z, y); + show_tree(rbtree); + } + if (y_original_color == COLOR_BLACK) + rcu_rbtree_remove_fixup(rbtree, x); + show_tree(rbtree); + /* + * Commit all _CMM_STORE_SHARED(). + */ + cmm_smp_wmc(); + + return 0; +} diff --git a/urcu/rcurbtree.h b/urcu/rcurbtree.h new file mode 100644 index 0000000..17d219f --- /dev/null +++ b/urcu/rcurbtree.h @@ -0,0 +1,147 @@ +#ifndef URCU_RBTREE_H +#define URCU_RBTREE_H + +/* + * urcu-rbtree.h + * + * Userspace RCU library - Red-Black Tree + * + * Copyright (c) 2010 Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + * Implementation of RCU-adapted data structures and operations based on the RB + * tree algorithms found in chapter 12 of: + * + * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and + * Clifford Stein. Introduction to Algorithms, Third Edition. The MIT + * Press, September 2009. + */ + +#include + +#define COLOR_BLACK 0 +#define COLOR_RED 1 + +#define IS_LEFT 0 +#define IS_RIGHT 1 + +/* + * Node key comparison function. + * < 0 : a lower than b. + * > 0 : a greater than b. + * == 0 : a equals b. + */ +typedef int (*rcu_rbtree_comp)(void *a, void *b); + +/* + * Node allocation and deletion functions. + */ +typedef struct rcu_rbtree_node *(*rcu_rbtree_alloc)(void); +typedef void (*rcu_rbtree_free)(void *node); + +struct rcu_rbtree_node { + /* must be set upon insertion */ + void *key; + + /* internally reserved */ + struct rcu_rbtree_node *p, *left, *right; + unsigned int color:1; + unsigned int pos:1; + unsigned int nil:1; +}; + +struct rcu_rbtree { + struct rcu_rbtree_node *root; + struct rcu_rbtree_node nil_node; + rcu_rbtree_comp comp; + rcu_rbtree_alloc rballoc; + rcu_rbtree_free rbfree; +}; + +#define DEFINE_RCU_RBTREE(x, _comp, _rballoc, _rbfree) \ + struct rcu_rbtree x = \ + { \ + .comp = _comp, \ + .rballoc = _rballoc, \ + .rbfree = _rbfree, \ + .nil_node = { \ + .color = COLOR_BLACK, \ + .nil = 1, \ + }, \ + .root = &x.nil_node, \ + }; + +/* + * Each of the search primitive and "prev"/"next" iteration must be called with + * the RCU read-side lock held. + * + * Insertion and removal must be protected by a mutex. At the moment, insertion + * and removal use defer_rcu, so calling them with rcu read-lock held is + * prohibited. + */ + +/* + * Node insertion. Returns 0 on success. May fail with -ENOMEM. + */ +int rcu_rbtree_insert(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *node); + +/* + * Remove node from tree. + * Must wait for a grace period after removal before performing deletion of the + * node. Note: it is illegal to re-use the same node pointer passed to "insert" + * also to "remove", because it may have been copied and garbage-collected since + * the insertion. A "search" for the key in the tree should be done to get + * "node". + * Returns 0 on success. May fail with -ENOMEM. + * + * The caller is responsible for freeing the node after a grace period. + */ +int rcu_rbtree_remove(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *node); + +/* RCU read-side */ + +/* + * Search key starting from node x. Returns &rcu_rbtree_nil if not found. + */ +struct rcu_rbtree_node* rcu_rbtree_search(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x, + void *key); + +struct rcu_rbtree_node *rcu_rbtree_min(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x); + +struct rcu_rbtree_node *rcu_rbtree_max(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x); + +struct rcu_rbtree_node *rcu_rbtree_next(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x); + +struct rcu_rbtree_node *rcu_rbtree_prev(struct rcu_rbtree *rbtree, + struct rcu_rbtree_node *x); + +/* + * Sentinel (bottom nodes). + * Don't care about p, left, right, pos and key values. + */ +static +int rcu_rbtree_is_nil(struct rcu_rbtree_node *node) +{ + return node->nil; +} + +#endif /* URCU_RBTREE_H */ -- 2.34.1