kernel - RB_SCAN() requires a short-term spinlock

* RB_SCAN() links and unlinks an info structure.  If called with a shared
  lock the linking and unlinking operations requires a very short-term spin
  lock to avoid clobbering each other.

* Note that RB_REMOVE() scans the inprog list but this function can only
  be safely called with the RB tree held exclusively anyway, so there's
  no need to spinlock the info list.

* Add kern/subr_rbtree.c glue functions for acquiring and releasing the
  spinlock, so sys/tree.h only needs to include sys/spinlock.h and not
  also sys/spinlock2.h

Reported-by: sephe

diff --git a/sys/conf/files b/sys/conf/files
index 85bbb88..d2756ad 100644 (file)
--- a/sys/conf/files
+++ b/sys/conf/files
@@ -964,6 +964,7 @@ kern/subr_blist.c   standard
 kern/subr_sbuf.c       standard
 kern/subr_scanf.c      standard
 kern/subr_taskqueue.c  standard
+kern/subr_rbtree.c     standard
 kern/sys_generic.c     standard
 kern/sys_pipe.c                standard
 kern/sys_process.c     standard

diff --git a/sys/kern/subr_rbtree.c b/sys/kern/subr_rbtree.c
new file mode 100644 (file)
index 0000000..2f7c7e7
--- /dev/null
+++ b/sys/kern/subr_rbtree.c
@@ -0,0 +1,61 @@
+/*
+ * SUBR_RBTREE.C - Generic red-black tree support
+ *
+ * Copyright (c) 2011 The DragonFly Project.  All rights reserved.
+ *
+ * This code is derived from software contributed to The DragonFly Project
+ * by Matthew Dillon <dillon@backplane.com>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name of The DragonFly Project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific, prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/param.h>
+#include <sys/kernel.h>
+#include <sys/spinlock.h>
+#include <sys/tree.h>
+
+#include <sys/spinlock2.h>
+
+/*
+ * Support function for RB_SCAN.  The info linkage functions require a
+ * temporary spinlock to avoid running over each other when RB_SCAN()
+ * is called with a shared lock held instread of an exclusive lock.
+ *
+ * (e.g. shared VM object locks).
+ */
+void
+rb_spin_lock(struct spinlock *spin)
+{
+       spin_lock(spin);
+}
+
+void
+rb_spin_unlock(struct spinlock *spin)
+{
+       spin_unlock(spin);
+}

diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 5d35db3..fdaa8c0 100644 (file)
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -29,6 +29,13 @@
 #ifndef        _SYS_TREE_H_
 #define        _SYS_TREE_H_
 
+#ifndef _SYS_SPINLOCK_H_
+#include <sys/spinlock.h>
+#endif
+
+void rb_spin_lock(struct spinlock *spin);
+void rb_spin_unlock(struct spinlock *spin);
+
 /*
  * This file defines data structures for different types of trees:
  * splay trees and red-black trees.
@@ -289,7 +296,9 @@ void name##_SPLAY_MINMAX(struct name *head, int __comp) \
             (x) != NULL;                                               \
             (x) = SPLAY_NEXT(name, head, x))
 
-/* Macros that define a red-black tree */
+/*
+ * Macros that define a red-black tree
+ */
 
 #define RB_SCAN_INFO(name, type)                                       \
 struct name##_scan_info {                                              \
@@ -301,16 +310,25 @@ struct name##_scan_info {                                         \
 struct name {                                                          \
        struct type *rbh_root;               /* root of the tree */     \
        struct name##_scan_info *rbh_inprog; /* scans in progress */    \
+       struct spinlock rbh_spin;                                       \
 }
 
 #define RB_INITIALIZER(root)                                           \
-       { NULL, NULL }
+       { NULL, NULL, SPINLOCK_INITIALIZER(root.spin) }
 
 #define RB_INIT(root) do {                                             \
        (root)->rbh_root = NULL;                                        \
        (root)->rbh_inprog = NULL;                                      \
 } while (/*CONSTCOND*/ 0)
 
+#ifdef _KERNEL
+#define RB_SCAN_LOCK(spin)     rb_spin_lock(spin)
+#define RB_SCAN_UNLOCK(spin)   rb_spin_unlock(spin)
+#else
+#define RB_SCAN_LOCK(spin)
+#define RB_SCAN_UNLOCK(spin)
+#endif
+
 #define RB_BLACK       0
 #define RB_RED         1
 #define RB_ENTRY(type)                                                 \
@@ -698,8 +716,10 @@ name##_SCANCMP_ALL(struct type *type __unused, void *data __unused)        \
 static __inline void                                                   \
 name##_scan_info_link(struct name##_scan_info *scan, struct name *head)        \
 {                                                                      \
+       RB_SCAN_LOCK(&head->rbh_spin);                                  \
        scan->link = RB_INPROG(head);                                   \
        RB_INPROG(head) = scan;                                         \
+       RB_SCAN_UNLOCK(&head->rbh_spin);                                \
 }                                                                      \
                                                                        \
 static __inline void                                                   \
@@ -707,10 +727,12 @@ name##_scan_info_done(struct name##_scan_info *scan, struct name *head)   \
 {                                                                      \
        struct name##_scan_info **infopp;                               \
                                                                        \
+       RB_SCAN_LOCK(&head->rbh_spin);                                  \
        infopp = &RB_INPROG(head);                                      \
        while (*infopp != scan)                                         \
                infopp = &(*infopp)->link;                              \
        *infopp = scan->link;                                           \
+       RB_SCAN_UNLOCK(&head->rbh_spin);                                \
 }                                                                      \
                                                                        \
 STORQUAL int                                                           \