[Cluster-devel] [PATCH 2/3] dlm_controld: Introduce RB tree for improving plock resources searching efficiency
Jiaju Zhang
jjzhang.linux at gmail.com
Thu May 26 23:48:06 UTC 2011
In some workload where there are many many plock resources, the plock
searching time is a bottleneck of the overall performance. In this patch
the RB tree is introduced and it can reduce the searching time from O(n)
to O(lgn).
Signed-off-by: Jiaju Zhang <jjzhang at suse.de>
---
group/dlm_controld/dlm_daemon.h | 2 +
group/dlm_controld/main.c | 1 +
group/dlm_controld/plock.c | 62 +++++++++++++++++++++++++++++++++++---
3 files changed, 60 insertions(+), 5 deletions(-)
diff --git a/group/dlm_controld/dlm_daemon.h b/group/dlm_controld/dlm_daemon.h
index 71e3bf4..264d068 100644
--- a/group/dlm_controld/dlm_daemon.h
+++ b/group/dlm_controld/dlm_daemon.h
@@ -43,6 +43,7 @@
#include "dlm_controld.h"
#include "list.h"
#include "linux_endian.h"
+#include "rbtree.h"
/* DLM_LOCKSPACE_LEN: maximum lockspace name length, from linux/dlmconstants.h.
Copied in libdlm.h so apps don't need to include the kernel header.
@@ -208,6 +209,7 @@ struct lockspace {
uint32_t associated_mg_id;
struct list_head saved_messages;
struct list_head plock_resources;
+ struct rb_root plock_resources_root;
time_t last_checkpoint_time;
time_t last_plock_time;
struct timeval drop_resources_last;
diff --git a/group/dlm_controld/main.c b/group/dlm_controld/main.c
index 0436205..afc22bd 100644
--- a/group/dlm_controld/main.c
+++ b/group/dlm_controld/main.c
@@ -164,6 +164,7 @@ static struct lockspace *create_ls(char *name)
INIT_LIST_HEAD(&ls->node_history);
INIT_LIST_HEAD(&ls->saved_messages);
INIT_LIST_HEAD(&ls->plock_resources);
+ ls->plock_resources_root = RB_ROOT;
INIT_LIST_HEAD(&ls->deadlk_nodes);
INIT_LIST_HEAD(&ls->transactions);
INIT_LIST_HEAD(&ls->resources);
diff --git a/group/dlm_controld/plock.c b/group/dlm_controld/plock.c
index 41b0423..66b20a1 100644
--- a/group/dlm_controld/plock.c
+++ b/group/dlm_controld/plock.c
@@ -47,6 +47,7 @@ struct resource {
struct list_head locks; /* one lock for each range */
struct list_head waiters;
struct list_head pending; /* discovering r owner */
+ struct rb_node rb_node;
};
#define P_SYNCING 0x00000001 /* plock has been sent as part of sync but not
@@ -237,6 +238,52 @@ static uint64_t dt_usec(struct timeval *start, struct timeval *stop)
return dt;
}
+static struct resource * rb_search_plock_resource(struct lockspace *ls, uint64_t number)
+{
+ struct rb_node *n = ls->plock_resources_root.rb_node;
+ struct resource *r;
+
+ while (n) {
+ r = rb_entry(n, struct resource, rb_node);
+ if (number < r->number)
+ n = n->rb_left;
+ else if (number > r->number)
+ n = n->rb_right;
+ else
+ return r;
+ }
+ return NULL;
+}
+
+static void rb_insert_plock_resource(struct lockspace *ls, struct resource *r)
+{
+ struct resource *entry;
+ struct rb_node **p;
+ struct rb_node *parent = NULL;
+
+ p = &ls->plock_resources_root.rb_node;
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct resource, rb_node);
+ if (r->number < entry->number)
+ p = &parent->rb_left;
+ else if (r->number > entry->number)
+ p = &parent->rb_right;
+ else
+ return;
+ }
+ rb_link_node(&r->rb_node, parent, p);
+ rb_insert_color(&r->rb_node, &ls->plock_resources_root);
+}
+
+static void rb_del_plock_resource(struct lockspace *ls, struct resource *r)
+{
+ if (!RB_EMPTY_NODE(&r->rb_node)) {
+ rb_erase(&r->rb_node, &ls->plock_resources_root);
+ RB_CLEAR_NODE(&r->rb_node);
+ }
+}
+
static struct resource *search_resource(struct lockspace *ls, uint64_t number)
{
struct resource *r;
@@ -254,7 +301,7 @@ static int find_resource(struct lockspace *ls, uint64_t number, int create,
struct resource *r = NULL;
int rv = 0;
- r = search_resource(ls, number);
+ r = rb_search_plock_resource(ls, number);
if (r)
goto out;
@@ -282,6 +329,7 @@ static int find_resource(struct lockspace *ls, uint64_t number, int create,
r->owner = 0;
list_add_tail(&r->list, &ls->plock_resources);
+ rb_insert_plock_resource(ls, r);
out:
if (r)
gettimeofday(&r->last_access, NULL);
@@ -289,13 +337,14 @@ static int find_resource(struct lockspace *ls, uint64_t number, int create,
return rv;
}
-static void put_resource(struct resource *r)
+static void put_resource(struct lockspace *ls, struct resource *r)
{
/* with ownership, resources are only freed via drop messages */
if (cfgd_plock_ownership)
return;
if (list_empty(&r->locks) && list_empty(&r->waiters)) {
+ rb_del_plock_resource(ls, r);
list_del(&r->list);
free(r);
}
@@ -705,7 +754,7 @@ static void do_lock(struct lockspace *ls, struct dlm_plock_info *in,
write_result(ls, in, rv);
do_waiters(ls, r);
- put_resource(r);
+ put_resource(ls, r);
}
static void do_unlock(struct lockspace *ls, struct dlm_plock_info *in,
@@ -719,7 +768,7 @@ static void do_unlock(struct lockspace *ls, struct dlm_plock_info *in,
write_result(ls, in, rv);
do_waiters(ls, r);
- put_resource(r);
+ put_resource(ls, r);
}
/* we don't even get to this function if the getlk isn't from us */
@@ -735,7 +784,7 @@ static void do_get(struct lockspace *ls, struct dlm_plock_info *in,
rv = 0;
write_result(ls, in, rv);
- put_resource(r);
+ put_resource(ls, r);
}
static void save_message(struct lockspace *ls, struct dlm_header *hd, int len,
@@ -1341,6 +1390,7 @@ static void _receive_drop(struct lockspace *ls, struct dlm_header *hd, int len)
guaranteed to be the same on all nodes */
if (list_empty(&r->locks) && list_empty(&r->waiters)) {
+ rb_del_plock_resource(ls, r);
list_del(&r->list);
free(r);
} else {
@@ -1738,6 +1788,7 @@ static int unpack_section_buf(struct lockspace *ls, char *numbuf, int buflen,
}
list_add_tail(&r->list, &ls->plock_resources);
+ rb_insert_plock_resource(ls, r);
*lock_count = count;
return 0;
}
@@ -2239,6 +2290,7 @@ void purge_plocks(struct lockspace *ls, int nodeid, int unmount)
if (!cfgd_plock_ownership &&
list_empty(&r->locks) && list_empty(&r->waiters)) {
+ rb_del_plock_resource(ls, r);
list_del(&r->list);
free(r);
}
More information about the Cluster-devel
mailing list