From 4cef6f97536820c7b4d685d6243cbb87ba34a4a1 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 3 Jun 2013 02:48:29 -0400 Subject: [PATCH] rcuja: lookup lower equal cannot reach dead-end Thanks to the guarantees provided by ja_detach_node(), lookups can _never_ see a branch that would lead to a dead-end. Therefore, lookup lower/equal never needs to retry, and we thus have a bounded number of operations for cds_ja_lookup_lower_equal(). Signed-off-by: Mathieu Desnoyers --- rcuja/rcuja.c | 30 +++++++++--------------------- 1 file changed, 9 insertions(+), 21 deletions(-) diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index e6c6d5b..74bb391 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -1738,10 +1738,6 @@ struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key) return head; } -/* - * cds_ja_lookup_lower_equal() may need to retry if a concurrent removal - * causes failure to find the previous node. - */ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) { int tree_depth, level; @@ -1751,7 +1747,6 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) if (caa_unlikely(key > ja->key_max || !key)) return head; -retry: memset(cur_node_depth, 0, sizeof(cur_node_depth)); tree_depth = ja->tree_depth; node_flag = rcu_dereference(ja->root); @@ -1806,14 +1801,9 @@ retry: level++; /* - * From this point, we should be able to find a "lower than" - * match. The only reason why we could fail to find such a match - * would be due to a concurrent removal of the branch that - * contains the match. If this happens, we have no choice but to - * retry the entire lookup. Indeed, just because we reached a - * dead-end due to concurrent removal of the branch does not - * mean that other match don't exist. However, this requires - * going up into the tree, hence the retry. + * From this point, we are guaranteed to be able to find a + * "lower than" match. ja_detach_node() guarantees that it is + * not possible for a lookup to reach a dead-end. */ /* Find rightmost child of rightmost child (recursively). */ @@ -1824,15 +1814,8 @@ retry: break; } - if (level != tree_depth) { - /* - * We did not get a match. Caused by concurrent removal. - * We need to retry the entire lookup. - */ - goto retry; - } + assert(level == tree_depth); - /* Last level lookup succeded. We got a "lower than" match. */ head.next = (struct cds_hlist_node *) node_flag; return head; } @@ -2163,6 +2146,11 @@ struct cds_ja_node *cds_ja_add_unique(struct cds_ja *ja, uint64_t key, * However, when a child is removed from "linear" nodes, its pointer * is set to NULL. We therefore check, while holding the locks, if this * pointer is NULL, and return -ENOENT to the caller if it is the case. + * + * ja_detach_node() ensures that a lookup will _never_ see a branch that + * leads to a dead-end: when removing branch, it makes sure to perform + * the "cut" at the highest node that has only one child, effectively + * replacing it with a NULL pointer. */ static int ja_detach_node(struct cds_ja *ja, -- 2.34.1