dlm: convert rsb list to rb_tree

Change the linked lists to rb_tree's in the rsb
hash table to speed up searches.  Slow rsb searches
were having a large impact on gfs2 performance due
to the large number of dlm locks gfs2 uses.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
Signed-off-by: David Teigland <teigland@redhat.com>

1 files changed, 9 insertions, 14 deletions

diff --git a/fs/dlm/lockspace.c b/fs/dlm/lockspace.c
index a1d8f1af144b..1d16a23b0a06 100644
--- a/fs/dlm/lockspace.c
+++ b/fs/dlm/lockspace.c
@@ -457,8 +457,8 @@ static int new_lockspace(const char *name, int namelen, void **lockspace,
         if (!ls->ls_rsbtbl)
                 goto out_lsfree;
         for (i = 0; i < size; i++) {
-                INIT_LIST_HEAD(&ls->ls_rsbtbl[i].list);
-                INIT_LIST_HEAD(&ls->ls_rsbtbl[i].toss);
+                ls->ls_rsbtbl[i].keep.rb_node = NULL;
+                ls->ls_rsbtbl[i].toss.rb_node = NULL;
                 spin_lock_init(&ls->ls_rsbtbl[i].lock);
         }
 
@@ -685,7 +685,7 @@ static int lockspace_busy(struct dlm_ls *ls, int force)
 static int release_lockspace(struct dlm_ls *ls, int force)
 {
         struct dlm_rsb *rsb;
-        struct list_head *head;
+        struct rb_node *n;
         int i, busy, rv;
 
         busy = lockspace_busy(ls, force);
@@ -746,20 +746,15 @@ static int release_lockspace(struct dlm_ls *ls, int force)
          */
 
         for (i = 0; i < ls->ls_rsbtbl_size; i++) {
-                head = &ls->ls_rsbtbl[i].list;
-                while (!list_empty(head)) {
-                        rsb = list_entry(head->next, struct dlm_rsb,
-                                         res_hashchain);
-
-                        list_del(&rsb->res_hashchain);
+                while ((n = rb_first(&ls->ls_rsbtbl[i].keep))) {
+                        rsb = rb_entry(n, struct dlm_rsb, res_hashnode);
+                        rb_erase(n, &ls->ls_rsbtbl[i].keep);
                         dlm_free_rsb(rsb);
                 }
 
-                head = &ls->ls_rsbtbl[i].toss;
-                while (!list_empty(head)) {
-                        rsb = list_entry(head->next, struct dlm_rsb,
-                                         res_hashchain);
-                        list_del(&rsb->res_hashchain);
+                while ((n = rb_first(&ls->ls_rsbtbl[i].toss))) {
+                        rsb = rb_entry(n, struct dlm_rsb, res_hashnode);
+                        rb_erase(n, &ls->ls_rsbtbl[i].toss);
                         dlm_free_rsb(rsb);
                 }
         }