Add rbtree_callbydata for sane threadsafe/garbage-collected operations

  When working with an rbtree which is exposed to multiple threads,
  it is not safe to do much of anything with data retrieved by functions
  such as rbtree_finddata, other than to feed it directly to rbtree_delete.

  This is because once rbtree_finddata has returned, another thread may
  obtain a pointer to that data (and hence may begin mangling non-key
  material such as container_of or any child allocs.)  This is especially
  true for rbtrees that have a freeNode garbage collection routine defined.

  This function allows safe operations while the rbtree lock is still
  held.  It also allows for a conditional delete operation based on
  criteria which may only be safe to ascertain while the lock is held.
  In addition to short operations, it could be used, with due care, to
  trylock a more granular lock associated with the key before deleting
  the key or before operating with it outside of the rbtree lock.

diff --git a/src/include/libradius.h b/src/include/libradius.h
index b4fabaa..2dfb159 100644 (file)
--- a/src/include/libradius.h
+++ b/src/include/libradius.h
@@ -628,6 +628,26 @@ typedef enum { PreOrder, InOrder, PostOrder } RBTREE_ORDER;
 int rbtree_walk(rbtree_t *tree, RBTREE_ORDER order, int (*callback)(void *, void *), void *context);
 
 /*
+ *     Find a matching data item in an rbtree and, if one is found,
+ *     perform a callback on it.
+ *
+ *     The callback is similar to rbtree_walk above, except that a
+ *     positive return code from the callback will cause the found node
+ *     to be deleted from the tree.  If the tree was created with
+ *     RBTREE_FLAG_LOCK, then the entire find/callback/delete/rebalance
+ *     sequence happens while the lock is held.
+ *
+ *     Note that the callback MUST NOT alter any of the data which
+ *     is used as the rbtree key, nor attempt to alter the rest of
+ *     the rbtree in any way.
+ *
+ *     Returns a pointer to the user data in the found node, or NULL if the
+ *     item was not found, or NULL if the item was deleted and the tree was
+ *     created with a freeNode garbage collection routine.
+ */
+void *rbtree_callbydata(rbtree_t *tree, void const *Data, int (*callback)(void *, void *), void *context);
+
+/*
  *     FIFOs
  */
 typedef struct fr_fifo_t fr_fifo_t;

diff --git a/src/lib/rbtree.c b/src/lib/rbtree.c
index 4429973..fd4a71e 100644 (file)
--- a/src/lib/rbtree.c
+++ b/src/lib/rbtree.c
@@ -401,7 +401,7 @@ static void DeleteFixup(rbtree_t *tree, rbnode_t *X, rbnode_t *Parent)
 /*
  *     Delete an element from the tree.
  */
-void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
+static void rbtree_delete_internal(rbtree_t *tree, rbnode_t *Z, int skiplock)
 {
        rbnode_t *X, *Y;
        rbnode_t *Parent;
@@ -412,7 +412,9 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
 
        if (!Z || Z == NIL) return;
 
-       PTHREAD_MUTEX_LOCK(tree);
+       if (!skiplock) {
+               PTHREAD_MUTEX_LOCK(tree);
+       }
 
        if (Z->Left == NIL || Z->Right == NIL) {
                /* Y has a NIL node as a child */
@@ -479,7 +481,12 @@ void rbtree_delete(rbtree_t *tree, rbnode_t *Z)
        }
 
        tree->num_elements--;
-       PTHREAD_MUTEX_UNLOCK(tree);
+       if (!skiplock) {
+               PTHREAD_MUTEX_UNLOCK(tree);
+       }
+}
+void rbtree_delete(rbtree_t *tree, rbnode_t *Z) {
+       rbtree_delete_internal(tree, Z, 0);
 }
 
 /*
@@ -543,6 +550,46 @@ void *rbtree_finddata(rbtree_t *tree, void const *Data)
 }
 
 /*
+ * Find a node by data, perform a callback, and perhaps delete the node.
+ */
+void *rbtree_callbydata(rbtree_t *tree, void const *Data,
+                       int (*callback)(void *, void *), void *context) {
+
+       /*******************************
+        *  find node containing Data  *
+        *******************************/
+
+       rbnode_t *Current;
+
+
+       PTHREAD_MUTEX_LOCK(tree);
+       Current = tree->Root;
+
+       while (Current != NIL) {
+               int result = tree->Compare(Data, Current->Data);
+
+               if (result == 0) {
+                       void *data = Current->Data;
+
+                       if (callback(context, data) > 0) {
+                               rbtree_delete_internal(tree, Current, 1);
+                               if (tree->freeNode) {
+                                       data = NULL;
+                               }
+                       }
+                       PTHREAD_MUTEX_UNLOCK(tree);
+                       return data;
+               } else {
+                       Current = (result < 0) ?
+                               Current->Left : Current->Right;
+               }
+       }
+
+       PTHREAD_MUTEX_UNLOCK(tree);
+       return NULL;
+}
+
+/*
  *     Walk the tree, Pre-order
  *
  *     We call ourselves recursively for each function, but that's OK,