rcuja: fix iteration and lookup below/above equal

[userspace-rcu.git] / rcuja / rcuja-range.c

diff --git a/rcuja/rcuja-range.c b/rcuja/rcuja-range.c
index 761affb249e343a39e9911621a82456e0f35b4dc..00d68befa20d35b552f314bc680a3a3de81a310d 100644 (file)
--- a/rcuja/rcuja-range.c
+++ b/rcuja/rcuja-range.c
@@ -94,6 +94,28 @@
 
 #define CDS_JA_RANGE_KEY_BITS  64
 
+enum cds_ja_range_type {
+       CDS_JA_RANGE_ALLOCATED,
+       CDS_JA_RANGE_FREE,
+       CDS_JA_RANGE_REMOVED,
+};
+
+/*
+ * Range goes from start (inclusive) to end (inclusive).
+ * Range start is used as node key in the Judy array.
+ */
+struct cds_ja_range {
+       uint64_t end;
+       struct cds_ja_node ja_node;
+       pthread_mutex_t lock;
+       void *priv;
+       enum cds_ja_range_type type;
+
+       /* not required on lookup fast-path */
+       uint64_t start;
+       struct rcu_head head;
+};
+
 struct cds_ja_range *cds_ja_range_lookup(struct cds_ja *ja, uint64_t key)
 {
        struct cds_ja_node *node, *last_node;
@@ -150,6 +172,7 @@ static
 struct cds_ja_range *range_create(
                uint64_t start,         /* inclusive */
                uint64_t end,           /* inclusive */
+               void *priv,
                enum cds_ja_range_type type)
 {
        struct cds_ja_range *range;
@@ -159,6 +182,7 @@ struct cds_ja_range *range_create(
                return NULL;
        range->start = start;
        range->end = end;
+       range->priv = priv;
        range->type = type;
        pthread_mutex_init(&range->lock, NULL);
        return range;
@@ -185,9 +209,10 @@ void rcu_free_range(struct cds_ja *ja, struct cds_ja_range *range)
                        free_range_cb);
 }
 
-struct cds_ja_range *cds_ja_range_add(struct cds_ja *ja,
+int cds_ja_range_add(struct cds_ja *ja,
                uint64_t start,         /* inclusive */
-               uint64_t end)           /* inclusive */
+               uint64_t end,           /* inclusive */
+               void *priv)
 {
        struct cds_ja_node *old_node, *old_node_end;
        struct cds_ja_range *old_range, *old_range_end, *new_range, *ranges[3];
@@ -205,7 +230,7 @@ retry:
        old_range = caa_container_of(old_node, struct cds_ja_range, ja_node);
        switch (CMM_LOAD_SHARED(old_range->type)) {
        case CDS_JA_RANGE_ALLOCATED:
-               return NULL;
+               return -EEXIST;
        case CDS_JA_RANGE_FREE:
                break;
        case CDS_JA_RANGE_REMOVED:
@@ -220,7 +245,7 @@ retry:
                switch (CMM_LOAD_SHARED(old_range->type)) {
                case CDS_JA_RANGE_ALLOCATED:
                case CDS_JA_RANGE_FREE:         /* fall-through */
-                       return NULL;
+                       return -EEXIST;
                case CDS_JA_RANGE_REMOVED:
                        goto retry;
                }
@@ -238,32 +263,32 @@ retry:
                if (end == old_range->end) {
                        /* 1 range */
                        ranges[0] = new_range = range_create(start, end,
-                               CDS_JA_RANGE_ALLOCATED);
+                               priv, CDS_JA_RANGE_ALLOCATED);
                        nr_ranges = 1;
                } else {
                        /* 2 ranges */
                        ranges[0] = new_range = range_create(start, end,
-                               CDS_JA_RANGE_ALLOCATED);
+                               priv, CDS_JA_RANGE_ALLOCATED);
                        ranges[1] = range_create(end + 1, old_range->end,
-                               CDS_JA_RANGE_FREE);
+                               NULL, CDS_JA_RANGE_FREE);
                        nr_ranges = 2;
                }
        } else {
                if (end == old_range->end) {
                        /* 2 ranges */
                        ranges[0] = range_create(old_range->start, start - 1,
-                               CDS_JA_RANGE_FREE);
+                               NULL, CDS_JA_RANGE_FREE);
                        ranges[1] = new_range = range_create(start, end,
-                               CDS_JA_RANGE_ALLOCATED);
+                               priv, CDS_JA_RANGE_ALLOCATED);
                        nr_ranges = 2;
                } else {
                        /* 3 ranges */
                        ranges[0] = range_create(old_range->start, start - 1,
-                               CDS_JA_RANGE_FREE);
+                               NULL, CDS_JA_RANGE_FREE);
                        ranges[1] = new_range = range_create(start, end,
-                               CDS_JA_RANGE_ALLOCATED);
+                               priv, CDS_JA_RANGE_ALLOCATED);
                        ranges[2] = range_create(end + 1, old_range->end,
-                               CDS_JA_RANGE_FREE);
+                               NULL, CDS_JA_RANGE_FREE);
                        nr_ranges = 3;
                }
        }
@@ -290,7 +315,7 @@ retry:
 
        rcu_free_range(ja, old_range);
 
-       return new_range;
+       return 0;
 }
 
 int cds_ja_range_del(struct cds_ja *ja, struct cds_ja_range *range)
@@ -342,7 +367,7 @@ retry:
        /* Create new free range */
        start = merge_ranges[0]->start;
        end = merge_ranges[nr_merge - 1]->end;
-       new_range = range_create(start, end, CDS_JA_RANGE_FREE);
+       new_range = range_create(start, end, NULL, CDS_JA_RANGE_FREE);
        ret = cds_ja_add(ja, start, &new_range->ja_node);
        assert(!ret);
 
@@ -377,10 +402,12 @@ struct cds_ja *_cds_ja_range_new(const struct rcu_flavor_struct *flavor)
        ja = _cds_ja_new(CDS_JA_RANGE_KEY_BITS, flavor);
        if (!ja)
                return NULL;
-       range = range_create(0, UINT64_MAX, CDS_JA_RANGE_FREE);
+       range = range_create(0, UINT64_MAX, NULL, CDS_JA_RANGE_FREE);
        if (!range)
                goto free_ja;
+       cds_lfht_rcu_flavor(ja->ht)->read_lock();
        ret = cds_ja_add(ja, 0, &range->ja_node);
+       cds_lfht_rcu_flavor(ja->ht)->read_unlock();
        if (ret)
                goto free_range;
        return ja;
@@ -393,12 +420,14 @@ free_ja:
        return NULL;
 }
 
-int cds_ja_range_destroy(struct cds_ja *ja)
+int cds_ja_range_destroy(struct cds_ja *ja,
+               void (*free_priv)(void *ptr))
 {
        uint64_t key;
        struct cds_ja_node *ja_node;
        int ret = 0;
 
+       cds_lfht_rcu_flavor(ja->ht)->read_lock();
        cds_ja_for_each_key_rcu(ja, key, ja_node) {
                struct cds_ja_node *tmp_node;
 
@@ -410,12 +439,16 @@ int cds_ja_range_destroy(struct cds_ja *ja)
                        ret = cds_ja_del(ja, key, &range->ja_node);
                        if (ret)
                                goto error;
+                       if (free_priv)
+                               free_priv(range->priv);
                        /* Alone using Judy array, OK to free now */
                        free_range(range);
                }
        }
+       cds_lfht_rcu_flavor(ja->ht)->read_unlock();
        return cds_ja_destroy(ja);
 
 error:
+       cds_lfht_rcu_flavor(ja->ht)->read_unlock();
        return ret;
 }