#include <urcu/arch.h>
#include <assert.h>
#include <urcu-pointer.h>
+#include <urcu/uatomic.h>
#include <stdint.h>
#include "rcuja-internal.h"
*/
#define NODE_INDEX_NULL 8
+/*
+ * Number of removals needed on a fallback node before we try to shrink
+ * it.
+ */
+#define JA_FALLBACK_REMOVAL_COUNT 8
+
/*
* Iteration on the array to find the right node size for the number of
* children stops when it reaches .max_child == 256 (this is the largest
{
unsigned int new_type_index;
struct cds_ja_inode *new_node;
+ struct cds_ja_shadow_node *new_shadow_node;
const struct cds_ja_type *new_type;
struct cds_ja_inode_flag *new_node_flag;
- int new_shadow = 0;
int ret;
+ int fallback = 0;
if (!shadow_node || old_type_index == NODE_INDEX_NULL) {
new_type_index = 0;
} else {
new_type_index = old_type_index + 1;
}
- dbg_printf("Recompact to type %d\n", new_type_index);
+retry: /* for fallback */
+ dbg_printf("Recompact to type %d\n", new_type_index);
new_type = &ja_types[new_type_index];
new_node = alloc_cds_ja_node(new_type);
if (!new_node)
new_node_flag = ja_node_flag(new_node, new_type_index);
dbg_printf("Recompact inherit lock from %p\n", shadow_node);
- ret = rcuja_shadow_set(ja->ht, new_node, shadow_node);
- if (ret) {
+ new_shadow_node = rcuja_shadow_set(ja->ht, new_node, shadow_node);
+ if (!new_shadow_node) {
free(new_node);
- return ret;
- }
-
- if (!shadow_node) {
- shadow_node = rcuja_shadow_lookup_lock(ja->ht, new_node);
- assert(shadow_node);
- new_shadow = 1;
+ return -ENOMEM;
}
-
- /*
- * We need to clear nr_child, because it will be re-incremented
- * by _ja_node_set_nth().
- */
- shadow_node->nr_child = 0;
+ if (fallback)
+ new_shadow_node->fallback_removal_count =
+ JA_FALLBACK_REMOVAL_COUNT;
assert(old_type->type_class != RCU_JA_PIGEON);
switch (old_type->type_class) {
ja_linear_node_get_ith_pos(old_type, old_node, i, &v, &iter);
if (!iter)
continue;
- ret = _ja_node_set_nth(new_type, new_node, shadow_node,
+ ret = _ja_node_set_nth(new_type, new_node,
+ new_shadow_node,
v, iter);
+ if (new_type->type_class == RCU_JA_POOL && ret) {
+ goto fallback_toosmall;
+ }
assert(!ret);
}
break;
j, &v, &iter);
if (!iter)
continue;
- ret = _ja_node_set_nth(new_type, new_node, shadow_node,
+ ret = _ja_node_set_nth(new_type, new_node,
+ new_shadow_node,
v, iter);
+ if (new_type->type_class == RCU_JA_POOL
+ && ret) {
+ goto fallback_toosmall;
+ }
assert(!ret);
}
}
default:
assert(0);
ret = -EINVAL;
- goto unlock_new_shadow;
+ goto end;
}
/* add node */
- ret = _ja_node_set_nth(new_type, new_node, shadow_node,
+ ret = _ja_node_set_nth(new_type, new_node,
+ new_shadow_node,
n, child_node_flag);
assert(!ret);
/* Return pointer to new recompacted new through old_node_flag */
}
ret = 0;
-
-unlock_new_shadow:
- if (new_shadow)
- rcuja_shadow_unlock(shadow_node);
+end:
return ret;
+
+fallback_toosmall:
+ /* fallback if next pool is too small */
+ ret = rcuja_shadow_clear(ja->ht, new_node, new_shadow_node,
+ RCUJA_SHADOW_CLEAR_FREE_NODE);
+ assert(!ret);
+
+ /* Last type: pigeon */
+ new_type_index = (1UL << JA_TYPE_BITS) - 1;
+ dbg_printf("Fallback to type %d\n", new_type_index);
+ uatomic_inc(&ja->nr_fallback);
+ fallback = 1;
+ goto retry;
}
/*
return NULL;
for (i = 1; i < tree_depth; i++) {
+ uint8_t iter_key;
+
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
node_flag = ja_node_get_nth(node_flag, NULL,
- (unsigned char) key);
+ iter_key);
if (!ja_node_ptr(node_flag))
return NULL;
- key >>= JA_BITS_PER_BYTE;
}
/* Last level lookup succeded. We got an actual match. */
struct cds_ja_inode_flag *node_flag,
struct cds_ja_inode_flag *parent_node_flag,
uint64_t key,
- unsigned int depth,
+ unsigned int level,
struct cds_ja_node *child_node)
{
struct cds_ja_shadow_node *shadow_node = NULL,
- *parent_shadow_node = NULL;
+ *parent_shadow_node = NULL,
+ *iter_shadow_node;
struct cds_ja_inode *node = ja_node_ptr(node_flag);
struct cds_ja_inode *parent_node = ja_node_ptr(parent_node_flag);
struct cds_hlist_head head;
struct cds_ja_inode_flag *created_nodes[JA_MAX_DEPTH];
int nr_created_nodes = 0;
- dbg_printf("Attach node at depth %u\n", depth);
+ dbg_printf("Attach node at level %u\n", level);
assert(node);
shadow_node = rcuja_shadow_lookup_lock(ja->ht, node);
/* Create shadow node for the leaf node */
dbg_printf("leaf shadow node creation\n");
- ret = rcuja_shadow_set(ja->ht, ja_node_ptr(iter_node_flag), NULL);
- if (ret)
+ iter_shadow_node = rcuja_shadow_set(ja->ht,
+ ja_node_ptr(iter_node_flag), NULL);
+ if (!iter_shadow_node) {
+ ret = -ENOMEM;
goto check_error;
+ }
created_nodes[nr_created_nodes++] = iter_node_flag;
- for (i = ja->tree_depth - 1; i >= (int) depth; i--) {
- dbg_printf("branch creation level %d, key %" PRIu64 "\n",
- i, key >> (JA_BITS_PER_BYTE * (i - 2)));
+ for (i = ja->tree_depth; i > (int) level; i--) {
+ uint8_t iter_key;
+
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - i)));
+ dbg_printf("branch creation level %d, key %u\n",
+ i - 1, (unsigned int) iter_key);
iter_dest_node_flag = NULL;
ret = ja_node_set_nth(ja, &iter_dest_node_flag,
- key >> (JA_BITS_PER_BYTE * (i - 2)),
+ iter_key,
iter_node_flag,
NULL);
if (ret)
iter_node_flag = iter_dest_node_flag;
}
- if (depth > 1) {
+ if (level > 1) {
+ uint8_t iter_key;
+
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (ja->tree_depth - level)));
/* We need to use set_nth on the previous level. */
iter_dest_node_flag = node_flag;
ret = ja_node_set_nth(ja, &iter_dest_node_flag,
- key >> (JA_BITS_PER_BYTE * (depth - 2)),
+ iter_key,
iter_node_flag,
shadow_node);
if (ret)
struct cds_ja_node *new_node)
{
unsigned int tree_depth, i;
- uint64_t iter_key;
struct cds_ja_inode_flag **node_flag_ptr; /* in parent */
struct cds_ja_inode_flag *node_flag,
*parent_node_flag,
retry:
dbg_printf("cds_ja_add attempt: key %" PRIu64 ", node %p\n",
key, new_node);
- iter_key = key;
parent2_node_flag = NULL;
parent_node_flag =
(struct cds_ja_inode_flag *) &ja->root; /* Use root ptr address as key for mutex */
/* Iterate on all internal levels */
for (i = 1; i < tree_depth; i++) {
+ uint8_t iter_key;
+
if (!ja_node_ptr(node_flag)) {
ret = ja_attach_node(ja, node_flag_ptr,
parent_node_flag, parent2_node_flag,
else
goto end;
}
+ iter_key = (uint8_t) (key >> (JA_BITS_PER_BYTE * (tree_depth - i - 1)));
parent2_node_flag = parent_node_flag;
parent_node_flag = node_flag;
node_flag = ja_node_get_nth(node_flag,
&node_flag_ptr,
- (unsigned char) iter_key);
- iter_key >>= JA_BITS_PER_BYTE;
+ iter_key);
}
/*
{
struct cds_ja *ja;
int ret;
+ struct cds_ja_shadow_node *root_shadow_node;
ja = calloc(sizeof(*ja), 1);
if (!ja)
/*
* Note: we should not free this node until judy array destroy.
*/
- ret = rcuja_shadow_set(ja->ht,
+ root_shadow_node = rcuja_shadow_set(ja->ht,
ja_node_ptr((struct cds_ja_inode_flag *) &ja->root),
NULL);
- if (ret)
+ if (!root_shadow_node) {
+ ret = -ENOMEM;
goto ht_node_error;
+ }
return ja;
ret = rcuja_delete_ht(ja->ht);
if (ret)
return ret;
+ if (uatomic_read(&ja->nr_fallback))
+ fprintf(stderr,
+ "[warning] RCU Judy Array used %lu fallback node(s)\n",
+ uatomic_read(&ja->nr_fallback));
free(ja);
return 0;
}
projects / userspace-rcu.git / blobdiff