X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=rcuja%2Frcuja.c;h=c6095956ab14f23e20227f8f05b8b317ce65646f;hb=1cee749c44c680a4834681bc88d95a6b6c2267b1;hp=74bb3910a384b67cc410ff09a12c953447b3cded;hpb=4cef6f97536820c7b4d685d6243cbb87ba34a4a1;p=userspace-rcu.git diff --git a/rcuja/rcuja.c b/rcuja/rcuja.c index 74bb391..c609595 100644 --- a/rcuja/rcuja.c +++ b/rcuja/rcuja.c @@ -120,7 +120,9 @@ const struct cds_ja_type ja_types[] = { { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .max_linear_child = ja_type_4_max_linear_child, .order = 7, }, /* Pools may fill sooner than max_child */ + /* This pool is hardcoded at index 5. See ja_node_ptr(). */ { .type_class = RCU_JA_POOL, .min_child = 20, .max_child = ja_type_5_max_child, .max_linear_child = ja_type_5_max_linear_child, .order = 8, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 7, }, + /* This pool is hardcoded at index 6. See ja_node_ptr(). */ { .type_class = RCU_JA_POOL, .min_child = 45, .max_child = ja_type_6_max_child, .max_linear_child = ja_type_6_max_linear_child, .order = 9, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 7, }, /* @@ -168,7 +170,9 @@ const struct cds_ja_type ja_types[] = { { .type_class = RCU_JA_LINEAR, .min_child = 10, .max_child = ja_type_4_max_child, .max_linear_child = ja_type_4_max_linear_child, .order = 8, }, /* Pools may fill sooner than max_child. */ + /* This pool is hardcoded at index 5. See ja_node_ptr(). */ { .type_class = RCU_JA_POOL, .min_child = 22, .max_child = ja_type_5_max_child, .max_linear_child = ja_type_5_max_linear_child, .order = 9, .nr_pool_order = ja_type_5_nr_pool_order, .pool_size_order = 8, }, + /* This pool is hardcoded at index 6. See ja_node_ptr(). */ { .type_class = RCU_JA_POOL, .min_child = 51, .max_child = ja_type_6_max_child, .max_linear_child = ja_type_6_max_linear_child, .order = 10, .nr_pool_order = ja_type_6_nr_pool_order, .pool_size_order = 8, }, /* @@ -261,30 +265,6 @@ unsigned long ja_node_type(struct cds_ja_inode_flag *node) return type; } -struct cds_ja_inode *ja_node_ptr(struct cds_ja_inode_flag *node) -{ - unsigned long type_index = ja_node_type(node); - const struct cds_ja_type *type; - - type = &ja_types[type_index]; - switch (type->type_class) { - case RCU_JA_LINEAR: - case RCU_JA_PIGEON: /* fall-through */ - case RCU_JA_NULL: /* fall-through */ - default: /* fall-through */ - return _ja_node_mask_ptr(node); - case RCU_JA_POOL: - switch (type->nr_pool_order) { - case 1: - return (struct cds_ja_inode *) (((unsigned long) node) & ~(JA_POOL_1D_MASK | JA_TYPE_MASK)); - case 2: - return (struct cds_ja_inode *) (((unsigned long) node) & ~(JA_POOL_2D_MASK | JA_POOL_1D_MASK | JA_TYPE_MASK)); - default: - assert(0); - } - } -} - static struct cds_ja_inode *alloc_cds_ja_node(struct cds_ja *ja, const struct cds_ja_type *ja_type) @@ -1707,20 +1687,19 @@ int ja_node_clear_ptr(struct cds_ja *ja, return ret; } -struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key) +struct cds_ja_node *cds_ja_lookup(struct cds_ja *ja, uint64_t key) { unsigned int tree_depth, i; struct cds_ja_inode_flag *node_flag; - struct cds_hlist_head head = { NULL }; if (caa_unlikely(key > ja->key_max)) - return head; + return NULL; tree_depth = ja->tree_depth; node_flag = rcu_dereference(ja->root); /* level 0: root node */ if (!ja_node_ptr(node_flag)) - return head; + return NULL; for (i = 1; i < tree_depth; i++) { uint8_t iter_key; @@ -1730,22 +1709,20 @@ struct cds_hlist_head cds_ja_lookup(struct cds_ja *ja, uint64_t key) dbg_printf("cds_ja_lookup iter key lookup %u finds node_flag %p\n", (unsigned int) iter_key, node_flag); if (!ja_node_ptr(node_flag)) - return head; + return NULL; } /* Last level lookup succeded. We got an actual match. */ - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } -struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) +struct cds_ja_node *cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) { int tree_depth, level; struct cds_ja_inode_flag *node_flag, *cur_node_depth[JA_MAX_DEPTH]; - struct cds_hlist_head head = { NULL }; if (caa_unlikely(key > ja->key_max || !key)) - return head; + return NULL; memset(cur_node_depth, 0, sizeof(cur_node_depth)); tree_depth = ja->tree_depth; @@ -1754,7 +1731,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) /* level 0: root node */ if (!ja_node_ptr(node_flag)) - return head; + return NULL; for (level = 1; level < tree_depth; level++) { uint8_t iter_key; @@ -1770,8 +1747,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) if (level == tree_depth) { /* Last level lookup succeded. We got an equal match. */ - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } /* @@ -1795,15 +1771,16 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) if (!level) { /* Reached the root and could not find a left sibling. */ - return head; + return NULL; } level++; /* * 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. + * "lower than" match. ja_attach_node() and ja_detach_node() + * both guarantee that it is not possible for a lookup to reach + * a dead-end. */ /* Find rightmost child of rightmost child (recursively). */ @@ -1816,8 +1793,7 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) assert(level == tree_depth); - head.next = (struct cds_hlist_node *) node_flag; - return head; + return (struct cds_ja_node *) node_flag; } /* @@ -1831,6 +1807,12 @@ struct cds_hlist_head cds_ja_lookup_lower_equal(struct cds_ja *ja, uint64_t key) * parent lock (if needed). Then we can proceed to create the new * branch. Publish the new branch, and release locks. * TODO: we currently always take the parent lock even when not needed. + * + * ja_attach_node() ensures that a lookup will _never_ see a branch that + * leads to a dead-end: before attaching a branch, the entire content of + * the new branch is populated, thus creating a cluster, before + * attaching the cluster to the rest of the tree, thus making it visible + * to lookups. */ static int ja_attach_node(struct cds_ja *ja, @@ -1845,7 +1827,6 @@ int ja_attach_node(struct cds_ja *ja, { struct cds_ja_shadow_node *shadow_node = NULL, *parent_shadow_node = NULL; - struct cds_hlist_head head; struct cds_ja_inode_flag *iter_node_flag, *iter_dest_node_flag; int ret, i; struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH]; @@ -1914,9 +1895,7 @@ int ja_attach_node(struct cds_ja *ja, } /* Create new branch, starting from bottom */ - CDS_INIT_HLIST_HEAD(&head); - cds_hlist_add_head_rcu(&child_node->list, &head); - iter_node_flag = (struct cds_ja_inode_flag *) head.next; + iter_node_flag = (struct cds_ja_inode_flag *) child_node; for (i = ja->tree_depth - 1; i >= (int) level; i--) { uint8_t iter_key; @@ -1996,9 +1975,9 @@ end: } /* - * Lock the parent containing the hlist head pointer, and add node to list of - * duplicates. Failure can happen if concurrent update changes the - * parent before we get the lock. We return -EAGAIN in that case. + * Lock the parent containing the pointer to list of duplicates, and add + * node to this list. Failure can happen if concurrent update changes + * the parent before we get the lock. We return -EAGAIN in that case. * Return 0 on success, negative error value on failure. */ static @@ -2019,7 +1998,12 @@ int ja_chain_node(struct cds_ja *ja, ret = -EAGAIN; goto end; } - cds_hlist_add_head_rcu(&node->list, (struct cds_hlist_head *) node_flag_ptr); + /* + * Add node to head of list. Safe against concurrent RCU read + * traversals. + */ + node->next = (struct cds_ja_node *) node_flag; + rcu_assign_pointer(*node_flag_ptr, (struct cds_ja_inode_flag *) node); end: rcuja_shadow_unlock(shadow_node); return ret; @@ -2305,8 +2289,7 @@ int ja_unchain_node(struct cds_ja *ja, struct cds_ja_node *node) { struct cds_ja_shadow_node *shadow_node; - struct cds_hlist_node *hlist_node; - struct cds_hlist_head hlist_head; + struct cds_ja_node *iter_node, **iter_node_ptr, **prev_node_ptr = NULL; int ret = 0, count = 0, found = 0; shadow_node = rcuja_shadow_lookup_lock(ja->ht, parent_node_flag); @@ -2316,28 +2299,30 @@ int ja_unchain_node(struct cds_ja *ja, ret = -EAGAIN; goto end; } - hlist_head.next = (struct cds_hlist_node *) ja_node_ptr(node_flag); /* - * Retry if another thread removed all but one of duplicates - * since check (this check was performed without lock). - * Ensure that the node we are about to remove is still in the - * list (while holding lock). + * Find the previous node's next pointer pointing to our node, + * so we can update it. Retry if another thread removed all but + * one of duplicates since check (this check was performed + * without lock). Ensure that the node we are about to remove is + * still in the list (while holding lock). No need for RCU + * traversal here since we hold the lock on the parent. */ - cds_hlist_for_each_rcu(hlist_node, &hlist_head) { - if (count == 0) { - /* FIXME: currently a work-around */ - hlist_node->prev = (struct cds_hlist_node *) node_flag_ptr; - } + iter_node_ptr = (struct cds_ja_node **) node_flag_ptr; + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + cds_ja_for_each_duplicate(iter_node) { count++; - if (hlist_node == &node->list) + if (iter_node == node) { + prev_node_ptr = iter_node_ptr; found++; + } + iter_node_ptr = &iter_node->next; } assert(found <= 1); if (!found || count == 1) { ret = -EAGAIN; goto end; } - cds_hlist_del_rcu(&node->list); + CMM_STORE_SHARED(*prev_node_ptr, node->next); /* * Validate that we indeed removed the node from linked list. */ @@ -2412,22 +2397,17 @@ retry: key); return -ENOENT; } else { - struct cds_hlist_head hlist_head; - struct cds_hlist_node *hlist_node; - struct cds_ja_node *entry, *match = NULL; + struct cds_ja_node *iter_node, *match = NULL; int count = 0; - hlist_head.next = - (struct cds_hlist_node *) ja_node_ptr(node_flag); - cds_hlist_for_each_entry_rcu(entry, - hlist_node, - &hlist_head, - list) { - dbg_printf("cds_ja_del: compare %p with entry %p\n", node, entry); - if (entry == node) - match = entry; + iter_node = (struct cds_ja_node *) ja_node_ptr(node_flag); + cds_ja_for_each_duplicate_rcu(iter_node) { + dbg_printf("cds_ja_del: compare %p with iter_node %p\n", node, iter_node); + if (iter_node == node) + match = iter_node; count++; } + if (!match) { dbg_printf("cds_ja_del: no node match for node %p key %" PRIu64 "\n", node, key); return -ENOENT; @@ -2522,14 +2502,12 @@ ja_error: __attribute__((visibility("protected"))) void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, struct cds_ja_inode_flag *node_flag, - void (*free_node_cb)(struct rcu_head *head)) + void (*rcu_free_node)(struct cds_ja_node *node)) { - const struct rcu_flavor_struct *flavor; unsigned int type_index; struct cds_ja_inode *node; const struct cds_ja_type *type; - flavor = cds_lfht_rcu_flavor(shadow_node->ja->ht); node = ja_node_ptr(node_flag); assert(node != NULL); type_index = ja_node_type(node_flag); @@ -2544,17 +2522,13 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (i = 0; i < nr_child; i++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; uint8_t v; ja_linear_node_get_ith_pos(type, node, i, &v, &iter); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - flavor->update_call_rcu(&entry->head, free_node_cb); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } break; @@ -2572,17 +2546,13 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (j = 0; j < nr_child; j++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; uint8_t v; ja_linear_node_get_ith_pos(type, pool, j, &v, &iter); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - flavor->update_call_rcu(&entry->head, free_node_cb); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } } @@ -2596,16 +2566,12 @@ void rcuja_free_all_children(struct cds_ja_shadow_node *shadow_node, for (i = 0; i < JA_ENTRY_PER_NODE; i++) { struct cds_ja_inode_flag *iter; - struct cds_hlist_head head; - struct cds_ja_node *entry; - struct cds_hlist_node *pos, *tmp; + struct cds_ja_node *node_iter, *n; iter = ja_pigeon_node_get_ith_pos(type, node, i); - if (!iter) - continue; - head.next = (struct cds_hlist_node *) iter; - cds_hlist_for_each_entry_safe(entry, pos, tmp, &head, list) { - flavor->update_call_rcu(&entry->head, free_node_cb); + node_iter = (struct cds_ja_node *) iter; + cds_ja_for_each_duplicate_safe(node_iter, n) { + rcu_free_node(node_iter); } } break; @@ -2664,7 +2630,7 @@ int ja_final_checks(struct cds_ja *ja) * being destroyed (ensured by the caller). */ int cds_ja_destroy(struct cds_ja *ja, - void (*free_node_cb)(struct rcu_head *head)) + void (*rcu_free_node)(struct cds_ja_node *node)) { const struct rcu_flavor_struct *flavor; int ret; @@ -2672,7 +2638,7 @@ int cds_ja_destroy(struct cds_ja *ja, flavor = cds_lfht_rcu_flavor(ja->ht); rcuja_shadow_prune(ja->ht, RCUJA_SHADOW_CLEAR_FREE_NODE | RCUJA_SHADOW_CLEAR_FREE_LOCK, - free_node_cb); + rcu_free_node); flavor->thread_offline(); ret = rcuja_delete_ht(ja->ht); if (ret)