* [lttng-dev] [PATCH 00/12] rculfhash memory managements
@ 2011-11-28 8:07 Lai Jiangshan
2011-11-28 8:07 ` [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability Lai Jiangshan
` (12 more replies)
0 siblings, 13 replies; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:07 UTC (permalink / raw)
Patch 1-9: extract memory managements (internal)APIs and prepare
for memory managements
(Patch 7 add general struct rcu_flavor)
Patch 10-12: Add memory managements.
Lai Jiangshan (12):
introduce bucket_at() and improve readability
proper wrapper for bucket table alloc and free
it is not required that ht->t.size >= ht->min_table_size now
remove struct rcu_level
rename min_alloc_size/min_alloc_order
add max_nr_buckets argument
Add rcu_flavor
use rcu_flavor for rculfhash
remove struct rcu_table
move memory management code out as rculfhash-mm-order.c
add rculfhash-mm-chunk.c
add rculfhash-mm-mmap.c
Makefile.am | 8 +-
rculfhash-internal.h | 131 +++++++++++++++
rculfhash-mm-chunk.c | 107 ++++++++++++
rculfhash-mm-mmap.c | 147 +++++++++++++++++
rculfhash-mm-order.c | 101 ++++++++++++
rculfhash.c | 417 +++++++++++++++++++-----------------------------
tests/test_urcu_hash.c | 4 +-
urcu-bp.c | 2 +
urcu-bp.h | 1 +
urcu-flavor.h | 65 ++++++++
urcu-qsbr.c | 2 +
urcu-qsbr.h | 1 +
urcu.c | 2 +
urcu.h | 1 +
urcu/map/urcu-bp.h | 2 +
urcu/map/urcu-qsbr.h | 2 +
urcu/map/urcu.h | 6 +
urcu/rculfhash.h | 43 +++--
18 files changed, 768 insertions(+), 274 deletions(-)
create mode 100644 rculfhash-internal.h
create mode 100644 rculfhash-mm-chunk.c
create mode 100644 rculfhash-mm-mmap.c
create mode 100644 rculfhash-mm-order.c
create mode 100644 urcu-flavor.h
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
@ 2011-11-28 8:07 ` Lai Jiangshan
2011-11-28 13:01 ` Mathieu Desnoyers
2011-11-28 8:07 ` [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free Lai Jiangshan
` (11 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:07 UTC (permalink / raw)
Fast path is not changed.
It will slow down very little for slow path.
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 115 +++++++++++++++++++++++++++++++---------------------------
1 files changed, 61 insertions(+), 54 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 4f82da4..5ad7583 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -756,18 +756,14 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
return old2;
}
-static
-struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
- unsigned long hash)
+static inline
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
{
- unsigned long index, order;
-
- assert(size > 0);
- index = hash & (size - 1);
+ unsigned long order;
- if (index < ht->min_alloc_size) {
- dbg_printf("lookup hash %lu index %lu order 0 aridx 0\n",
- hash, index);
+ if ((__builtin_constant_p(index) && index == 0)
+ || index < ht->min_alloc_size) {
+ dbg_printf("bucket index %lu order 0 aridx 0\n", index);
return &ht->t.tbl[0]->nodes[index];
}
/*
@@ -776,11 +772,19 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
* get_count_order_ulong.
*/
order = fls_ulong(index);
- dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
- hash, index, order, index & ((1UL << (order - 1)) - 1));
+ dbg_printf("bucket index %lu order %lu aridx %lu\n",
+ index, order, index & ((1UL << (order - 1)) - 1));
return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)];
}
+static inline
+struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
+ unsigned long hash)
+{
+ assert(size > 0);
+ return bucket_at(ht, hash & (size - 1));
+}
+
/*
* Remove all logically deleted nodes from a bucket up to a certain node key.
*/
@@ -1106,19 +1110,18 @@ static
void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
unsigned long start, unsigned long len)
{
- unsigned long j;
+ unsigned long j, size = 1UL << (i - 1);
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
- for (j = start; j < start + len; j++) {
- struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
-
- dbg_printf("init populate: i %lu j %lu hash %lu\n",
- i, j, (1UL << (i - 1)) + j);
- new_node->reverse_hash =
- bit_reverse_ulong((1UL << (i - 1)) + j);
- _cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1),
- new_node, NULL, 1);
+ for (j = size + start; j < size + start + len; j++) {
+ struct cds_lfht_node *new_node = bucket_at(ht, j);
+
+ assert(j >= size && j < (size << 1));
+ dbg_printf("init populate: order %lu index %lu hash %lu\n",
+ i, j, j);
+ new_node->reverse_hash = bit_reverse_ulong(j);
+ _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
}
ht->cds_lfht_rcu_read_unlock();
}
@@ -1206,18 +1209,18 @@ static
void remove_table_partition(struct cds_lfht *ht, unsigned long i,
unsigned long start, unsigned long len)
{
- unsigned long j;
+ unsigned long j, size = 1UL << (i - 1);
assert(i > ht->min_alloc_order);
ht->cds_lfht_rcu_read_lock();
- for (j = start; j < start + len; j++) {
- struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
-
- dbg_printf("remove entry: i %lu j %lu hash %lu\n",
- i, j, (1UL << (i - 1)) + j);
- fini_node->reverse_hash =
- bit_reverse_ulong((1UL << (i - 1)) + j);
- (void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
+ for (j = size + start; j < size + start + len; j++) {
+ struct cds_lfht_node *fini_node = bucket_at(ht, j);
+
+ assert(j >= size && j < (size << 1));
+ dbg_printf("remove entry: order %lu index %lu hash %lu\n",
+ i, j, j);
+ fini_node->reverse_hash = bit_reverse_ulong(j);
+ (void) _cds_lfht_del(ht, size, fini_node, 1);
}
ht->cds_lfht_rcu_read_unlock();
}
@@ -1294,14 +1297,15 @@ static
void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
{
struct cds_lfht_node *prev, *node;
- unsigned long order, len, i, j;
+ unsigned long order, len, i;
ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
assert(ht->t.tbl[0]);
- dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0);
- ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end());
- ht->t.tbl[0]->nodes[0].reverse_hash = 0;
+ dbg_printf("create bucket: order 0 index 0 hash 0\n");
+ node = bucket_at(ht, 0);
+ node->next = flag_bucket(get_end());
+ node->reverse_hash = 0;
for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
len = 1UL << (order - 1);
@@ -1312,22 +1316,28 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
assert(ht->t.tbl[order]);
}
- i = 0;
- prev = ht->t.tbl[i]->nodes;
- for (j = 0; j < len; j++) {
- if (j & (j - 1)) { /* Between power of 2 */
- prev++;
- } else if (j) { /* At each power of 2 */
- i++;
- prev = ht->t.tbl[i]->nodes;
- }
+ for (i = 0; i < len; i++) {
+ /*
+ * Now, we are trying to init the node with the
+ * hash=(len+i) (which is also a bucket with the
+ * index=(len+i)) and insert it into the hash table,
+ * so this node has to be inserted after the bucket
+ * with the index=(len+i)&(len-1)=i. And because there
+ * is no other non-bucket node nor bucket node with
+ * larger index/hash inserted, so the bucket node
+ * being inserted should be inserted directly linked
+ * after the bucket node with index=i.
+ */
+ prev = bucket_at(ht, i);
+ node = bucket_at(ht, len + i);
- node = &ht->t.tbl[order]->nodes[j];
dbg_printf("create bucket: order %lu index %lu hash %lu\n",
- order, j, j + len);
+ order, len + i, len + i);
+ node->reverse_hash = bit_reverse_ulong(len + i);
+
+ /* insert after prev */
+ assert(is_bucket(prev->next));
node->next = prev->next;
- assert(is_bucket(node->next));
- node->reverse_hash = bit_reverse_ulong(j + len);
prev->next = flag_bucket(node);
}
}
@@ -1477,14 +1487,11 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
{
- struct cds_lfht_node *lookup;
-
/*
* Get next after first bucket node. The first bucket node is the
* first node of the linked list.
*/
- lookup = &ht->t.tbl[0]->nodes[0];
- iter->next = lookup->next;
+ iter->next = bucket_at(ht, 0)->next;
cds_lfht_next(ht, iter);
}
@@ -1570,7 +1577,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
unsigned long order, i, size;
/* Check that the table is empty */
- node = &ht->t.tbl[0]->nodes[0];
+ node = bucket_at(ht, 0);
do {
node = clear_flag(node)->next;
if (!is_bucket(node))
@@ -1649,7 +1656,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
*removed = 0;
/* Count non-bucket nodes in the table */
- node = &ht->t.tbl[0]->nodes[0];
+ node = bucket_at(ht, 0);
do {
next = rcu_dereference(node->next);
if (is_removed(next)) {
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
2011-11-28 8:07 ` [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability Lai Jiangshan
@ 2011-11-28 8:07 ` Lai Jiangshan
2011-11-28 13:02 ` Mathieu Desnoyers
2011-11-28 8:07 ` [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now Lai Jiangshan
` (10 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:07 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 78 +++++++++++++++++++++++++++++++++++-----------------------
1 files changed, 47 insertions(+), 31 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 5ad7583..46bfa7a 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -756,6 +756,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
return old2;
}
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ ht->t.tbl[0] = calloc(ht->min_alloc_size,
+ sizeof(struct cds_lfht_node));
+ assert(ht->t.tbl[0]);
+ } else if (order > ht->min_alloc_order) {
+ ht->t.tbl[order] = calloc(1UL << (order -1),
+ sizeof(struct cds_lfht_node));
+ assert(ht->t.tbl[order]);
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0)
+ poison_free(ht->t.tbl[0]);
+ else if (order > ht->min_alloc_order)
+ poison_free(ht->t.tbl[order]);
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+}
+
static inline
struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
{
@@ -1159,8 +1189,7 @@ void init_table(struct cds_lfht *ht,
if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
break;
- ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
- assert(ht->t.tbl[i]);
+ cds_lfht_alloc_bucket_table(ht, i);
/*
* Set all bucket nodes reverse hash values for a level and
@@ -1244,7 +1273,7 @@ void fini_table(struct cds_lfht *ht,
unsigned long first_order, unsigned long last_order)
{
long i;
- void *free_by_rcu = NULL;
+ unsigned long free_by_rcu_order = 0;
dbg_printf("fini table: first_order %lu last_order %lu\n",
first_order, last_order);
@@ -1269,8 +1298,8 @@ void fini_table(struct cds_lfht *ht,
* return a logically removed node as insert position.
*/
ht->cds_lfht_synchronize_rcu();
- if (free_by_rcu)
- free(free_by_rcu);
+ if (free_by_rcu_order)
+ cds_lfht_free_bucket_table(ht, free_by_rcu_order);
/*
* Set "removed" flag in bucket nodes about to be removed.
@@ -1280,16 +1309,16 @@ void fini_table(struct cds_lfht *ht,
*/
remove_table(ht, i, len);
- free_by_rcu = ht->t.tbl[i];
+ free_by_rcu_order = i;
dbg_printf("fini new size: %lu\n", 1UL << i);
if (CMM_LOAD_SHARED(ht->in_progress_destroy))
break;
}
- if (free_by_rcu) {
+ if (free_by_rcu_order) {
ht->cds_lfht_synchronize_rcu();
- free(free_by_rcu);
+ cds_lfht_free_bucket_table(ht, free_by_rcu_order);
}
}
@@ -1299,8 +1328,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
struct cds_lfht_node *prev, *node;
unsigned long order, len, i;
- ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
- assert(ht->t.tbl[0]);
+ cds_lfht_alloc_bucket_table(ht, 0);
dbg_printf("create bucket: order 0 index 0 hash 0\n");
node = bucket_at(ht, 0);
@@ -1309,12 +1337,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
len = 1UL << (order - 1);
- if (order <= ht->min_alloc_order) {
- ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
- } else {
- ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
- assert(ht->t.tbl[order]);
- }
+ cds_lfht_alloc_bucket_table(ht, order);
for (i = 0; i < len; i++) {
/*
@@ -1590,23 +1613,16 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
*/
size = ht->t.size;
/* Internal sanity check: all nodes left should be bucket */
- for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
- unsigned long len;
+ for (i = 0; i < size; i++) {
+ node = bucket_at(ht, i);
+ dbg_printf("delete bucket: index %lu expected hash %lu hash %lu\n",
+ i, i, bit_reverse_ulong(node->reverse_hash));
+ assert(is_bucket(node->next));
+ }
- len = !order ? 1 : 1UL << (order - 1);
- for (i = 0; i < len; i++) {
- dbg_printf("delete order %lu i %lu hash %lu\n",
- order, i,
- bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
- assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
- }
+ for (order = get_count_order_ulong(size); (long)order >= 0; order--)
+ cds_lfht_free_bucket_table(ht, order);
- if (order == ht->min_alloc_order)
- poison_free(ht->t.tbl[0]);
- else if (order > ht->min_alloc_order)
- poison_free(ht->t.tbl[order]);
- /* Nothing to delete for order < ht->min_alloc_order */
- }
return 0;
}
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
2011-11-28 8:07 ` [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability Lai Jiangshan
2011-11-28 8:07 ` [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free Lai Jiangshan
@ 2011-11-28 8:07 ` Lai Jiangshan
2011-11-28 13:07 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 04/12] remove struct rcu_level Lai Jiangshan
` (9 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:07 UTC (permalink / raw)
Original code always ensure ht->t.size >= ht->min_table_size.
It is not good, ht->min_table_size should be used for allocation,
not for the bucket size in used.
Why does original code need to always ensure:
Original code don't do special alloc/free when ht->t.size < ht->min_table_size
in init_table()/fini_table(), so we have to force ht->t.size >= ht->min_table_size.
Why does new code become flexible:
New code use the wrappers, they handle the special cases.
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 19 ++++++++++---------
tests/test_urcu_hash.c | 2 +-
2 files changed, 11 insertions(+), 10 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 46bfa7a..8071915 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -187,7 +187,8 @@
/*
* Define the minimum table size.
*/
-#define MIN_TABLE_SIZE 1
+#define MIN_TABLE_ORDER 0
+#define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
#if (CAA_BITS_PER_LONG == 32)
#define MAX_TABLE_ORDER 32
@@ -1142,7 +1143,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
{
unsigned long j, size = 1UL << (i - 1);
- assert(i > ht->min_alloc_order);
+ assert(i > MIN_TABLE_ORDER);
ht->cds_lfht_rcu_read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *new_node = bucket_at(ht, j);
@@ -1178,7 +1179,7 @@ void init_table(struct cds_lfht *ht,
dbg_printf("init table: first_order %lu last_order %lu\n",
first_order, last_order);
- assert(first_order > ht->min_alloc_order);
+ assert(first_order > MIN_TABLE_ORDER);
for (i = first_order; i <= last_order; i++) {
unsigned long len;
@@ -1240,7 +1241,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
{
unsigned long j, size = 1UL << (i - 1);
- assert(i > ht->min_alloc_order);
+ assert(i > MIN_TABLE_ORDER);
ht->cds_lfht_rcu_read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *fini_node = bucket_at(ht, j);
@@ -1277,7 +1278,7 @@ void fini_table(struct cds_lfht *ht,
dbg_printf("fini table: first_order %lu last_order %lu\n",
first_order, last_order);
- assert(first_order > ht->min_alloc_order);
+ assert(first_order > MIN_TABLE_ORDER);
for (i = last_order; i >= first_order; i--) {
unsigned long len;
@@ -1390,7 +1391,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
if (!init_size || (init_size & (init_size - 1)))
return NULL;
min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
- init_size = max(init_size, min_alloc_size);
+ init_size = max(init_size, MIN_TABLE_SIZE);
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
@@ -1720,7 +1721,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
{
unsigned long old_order, new_order;
- new_size = max(new_size, ht->min_alloc_size);
+ new_size = max(new_size, MIN_TABLE_SIZE);
old_order = get_count_order_ulong(old_size);
new_order = get_count_order_ulong(new_size);
dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
@@ -1768,7 +1769,7 @@ static
void resize_target_update_count(struct cds_lfht *ht,
unsigned long count)
{
- count = max(count, ht->min_alloc_size);
+ count = max(count, MIN_TABLE_SIZE);
uatomic_set(&ht->t.resize_target, count);
}
@@ -1843,7 +1844,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
{
if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
return;
- count = max(count, ht->min_alloc_size);
+ count = max(count, MIN_TABLE_SIZE);
if (count == size)
return; /* Already the right size, no resize needed */
if (count > size) { /* lazy grow */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index fe650f3..01ae01a 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -896,7 +896,7 @@ int main(int argc, char **argv)
return -1;
}
- if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
+ if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
printf("Error: Min hash alloc size %lu is not a power of 2.\n",
min_hash_alloc_size);
return -1;
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 04/12] remove struct rcu_level
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (2 preceding siblings ...)
2011-11-28 8:07 ` [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:08 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order Lai Jiangshan
` (8 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 28 ++++++++++++----------------
1 files changed, 12 insertions(+), 16 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 8071915..fd9241d 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -239,27 +239,23 @@ struct ht_items_count {
} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
/*
- * rcu_level: Contains the per order-index-level bucket node table. The
- * size of each bucket node table is half the number of hashes contained
- * in this order (except for order 0). The minimum allocation size
- * parameter allows combining the bucket node arrays of the lowermost
- * levels to improve cache locality for small index orders.
- */
-struct rcu_level {
- /* Note: manually update allocation length when adding a field */
- struct cds_lfht_node nodes[0];
-};
-
-/*
* rcu_table: Contains the size and desired new size if a resize
* operation is in progress, as well as the statically-sized array of
- * rcu_level pointers.
+ * bucket table pointers.
*/
struct rcu_table {
unsigned long size; /* always a power of 2, shared (RCU) */
unsigned long resize_target;
int resize_initiated;
- struct rcu_level *tbl[MAX_TABLE_ORDER];
+
+ /*
+ * Contains the per order-index-level bucket node table. The size
+ * of each bucket node table is half the number of hashes contained
+ * in this order (except for order 0). The minimum allocation size
+ * parameter allows combining the bucket node arrays of the lowermost
+ * levels to improve cache locality for small index orders.
+ */
+ struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
};
/*
@@ -795,7 +791,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
if ((__builtin_constant_p(index) && index == 0)
|| index < ht->min_alloc_size) {
dbg_printf("bucket index %lu order 0 aridx 0\n", index);
- return &ht->t.tbl[0]->nodes[index];
+ return &ht->t.tbl[0][index];
}
/*
* equivalent to get_count_order_ulong(index + 1), but optimizes
@@ -805,7 +801,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
order = fls_ulong(index);
dbg_printf("bucket index %lu order %lu aridx %lu\n",
index, order, index & ((1UL << (order - 1)) - 1));
- return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)];
+ return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
}
static inline
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (3 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 04/12] remove struct rcu_level Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:14 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 06/12] add max_nr_buckets argument Lai Jiangshan
` (7 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Suggested-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 28 ++++++++++++++--------------
urcu/rculfhash.h | 8 ++++----
2 files changed, 18 insertions(+), 18 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index fd9241d..8282f09 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -265,8 +265,8 @@ struct rcu_table {
*/
struct cds_lfht {
struct rcu_table t;
- unsigned long min_alloc_order;
- unsigned long min_alloc_size;
+ unsigned long min_alloc_buckets_order;
+ unsigned long min_nr_alloc_buckets;
int flags;
/*
* We need to put the work threads offline (QSBR) when taking this
@@ -757,15 +757,15 @@ static
void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
{
if (order == 0) {
- ht->t.tbl[0] = calloc(ht->min_alloc_size,
+ ht->t.tbl[0] = calloc(ht->min_nr_alloc_buckets,
sizeof(struct cds_lfht_node));
assert(ht->t.tbl[0]);
- } else if (order > ht->min_alloc_order) {
+ } else if (order > ht->min_alloc_buckets_order) {
ht->t.tbl[order] = calloc(1UL << (order -1),
sizeof(struct cds_lfht_node));
assert(ht->t.tbl[order]);
}
- /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
}
/*
@@ -778,9 +778,9 @@ void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
{
if (order == 0)
poison_free(ht->t.tbl[0]);
- else if (order > ht->min_alloc_order)
+ else if (order > ht->min_alloc_buckets_order)
poison_free(ht->t.tbl[order]);
- /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
}
static inline
@@ -789,7 +789,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
unsigned long order;
if ((__builtin_constant_p(index) && index == 0)
- || index < ht->min_alloc_size) {
+ || index < ht->min_nr_alloc_buckets) {
dbg_printf("bucket index %lu order 0 aridx 0\n", index);
return &ht->t.tbl[0][index];
}
@@ -1364,7 +1364,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
}
struct cds_lfht *_cds_lfht_new(unsigned long init_size,
- unsigned long min_alloc_size,
+ unsigned long min_nr_alloc_buckets,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
void (*func)(struct rcu_head *head)),
@@ -1380,13 +1380,13 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
struct cds_lfht *ht;
unsigned long order;
- /* min_alloc_size must be power of two */
- if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
+ /* min_nr_alloc_buckets must be power of two */
+ if (!min_nr_alloc_buckets || (min_nr_alloc_buckets & (min_nr_alloc_buckets - 1)))
return NULL;
/* init_size must be power of two */
if (!init_size || (init_size & (init_size - 1)))
return NULL;
- min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
+ min_nr_alloc_buckets = max(min_nr_alloc_buckets, MIN_TABLE_SIZE);
init_size = max(init_size, MIN_TABLE_SIZE);
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
@@ -1405,8 +1405,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
pthread_mutex_init(&ht->resize_mutex, NULL);
order = get_count_order_ulong(init_size);
ht->t.resize_target = 1UL << order;
- ht->min_alloc_size = min_alloc_size;
- ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
cds_lfht_create_bucket(ht, 1UL << order);
ht->t.size = 1UL << order;
return ht;
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index d3018b7..d242ff6 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -98,7 +98,7 @@ enum {
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
*/
struct cds_lfht *_cds_lfht_new(unsigned long init_size,
- unsigned long min_alloc_size,
+ unsigned long min_nr_alloc_buckets,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
void (*func)(struct rcu_head *head)),
@@ -114,7 +114,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
/*
* cds_lfht_new - allocate a hash table.
* @init_size: number of nodes to allocate initially. Must be power of two.
- * @min_alloc_size: the smallest allocation size to use. Must be power of two.
+ * @min_nr_alloc_buckets: the smallest allocation size to use. Must be power of two.
* @flags: hash table creation flags (can be combined with bitwise or: '|').
* 0: no flags.
* CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
@@ -137,11 +137,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
*/
static inline
struct cds_lfht *cds_lfht_new(unsigned long init_size,
- unsigned long min_alloc_size,
+ unsigned long min_nr_alloc_buckets,
int flags,
pthread_attr_t *attr)
{
- return _cds_lfht_new(init_size, min_alloc_size, flags,
+ return _cds_lfht_new(init_size, min_nr_alloc_buckets, flags,
call_rcu, synchronize_rcu, rcu_read_lock,
rcu_read_unlock, rcu_thread_offline,
rcu_thread_online, rcu_register_thread,
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 06/12] add max_nr_buckets argument
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (4 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:24 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 07/12] Add rcu_flavor Lai Jiangshan
` (6 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 17 +++++++++++++++++
tests/test_urcu_hash.c | 2 +-
urcu/rculfhash.h | 9 ++++++---
3 files changed, 24 insertions(+), 4 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 8282f09..4a611a1 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -267,6 +267,7 @@ struct cds_lfht {
struct rcu_table t;
unsigned long min_alloc_buckets_order;
unsigned long min_nr_alloc_buckets;
+ unsigned long max_nr_buckets;
int flags;
/*
* We need to put the work threads offline (QSBR) when taking this
@@ -1365,6 +1366,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
void (*func)(struct rcu_head *head)),
@@ -1383,11 +1385,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
/* min_nr_alloc_buckets must be power of two */
if (!min_nr_alloc_buckets || (min_nr_alloc_buckets & (min_nr_alloc_buckets - 1)))
return NULL;
+
/* init_size must be power of two */
if (!init_size || (init_size & (init_size - 1)))
return NULL;
+
+ if (!max_nr_buckets)
+ max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
+
+ /* max_nr_buckets must be power of two */
+ if (!max_nr_buckets || (max_nr_buckets & (max_nr_buckets - 1)))
+ return NULL;
+
min_nr_alloc_buckets = max(min_nr_alloc_buckets, MIN_TABLE_SIZE);
init_size = max(init_size, MIN_TABLE_SIZE);
+ max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
+ init_size = min(init_size, max_nr_buckets);
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
@@ -1407,6 +1420,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
ht->t.resize_target = 1UL << order;
ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
cds_lfht_create_bucket(ht, 1UL << order);
ht->t.size = 1UL << order;
return ht;
@@ -1766,6 +1780,7 @@ void resize_target_update_count(struct cds_lfht *ht,
unsigned long count)
{
count = max(count, MIN_TABLE_SIZE);
+ count = min(count, ht->max_nr_buckets);
uatomic_set(&ht->t.resize_target, count);
}
@@ -1823,6 +1838,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
{
unsigned long target_size = size << growth;
+ target_size = min(target_size, ht->max_nr_buckets);
if (resize_target_grow(ht, target_size) >= target_size)
return;
@@ -1841,6 +1857,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
return;
count = max(count, MIN_TABLE_SIZE);
+ count = min(count, ht->max_nr_buckets);
if (count == size)
return; /* Already the right size, no resize needed */
if (count > size) { /* lazy grow */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index 01ae01a..043a33a 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -967,7 +967,7 @@ int main(int argc, char **argv)
* thread from the point of view of resize.
*/
rcu_register_thread();
- test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
+ test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
(opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
CDS_LFHT_ACCOUNTING, NULL);
ret = populate_hash();
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index d242ff6..bff883f 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -99,6 +99,7 @@ enum {
*/
struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets,
int flags,
void (*cds_lfht_call_rcu)(struct rcu_head *head,
void (*func)(struct rcu_head *head)),
@@ -113,8 +114,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
/*
* cds_lfht_new - allocate a hash table.
- * @init_size: number of nodes to allocate initially. Must be power of two.
- * @min_nr_alloc_buckets: the smallest allocation size to use. Must be power of two.
+ * @init_size: number of buckets to allocate initially. Must be power of two.
+ * @min_nr_alloc_buckets: the smallest allocation buckets size to use. Must be power of two.
+ * @max_nr_buckets: the max size of buckets for future growing. Must be power of two.
* @flags: hash table creation flags (can be combined with bitwise or: '|').
* 0: no flags.
* CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
@@ -138,10 +140,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
static inline
struct cds_lfht *cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets,
int flags,
pthread_attr_t *attr)
{
- return _cds_lfht_new(init_size, min_nr_alloc_buckets, flags,
+ return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags,
call_rcu, synchronize_rcu, rcu_read_lock,
rcu_read_unlock, rcu_thread_offline,
rcu_thread_online, rcu_register_thread,
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 07/12] Add rcu_flavor
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (5 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 06/12] add max_nr_buckets argument Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:23 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash Lai Jiangshan
` (5 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Not all related functions are added.
Left functions will be added when needed.
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
Makefile.am | 2 +-
urcu-bp.c | 2 +
urcu-bp.h | 1 +
urcu-flavor.h | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++
urcu-qsbr.c | 2 +
urcu-qsbr.h | 1 +
urcu.c | 2 +
urcu.h | 1 +
urcu/map/urcu-bp.h | 2 +
urcu/map/urcu-qsbr.h | 2 +
urcu/map/urcu.h | 6 ++++
11 files changed, 85 insertions(+), 1 deletions(-)
create mode 100644 urcu-flavor.h
diff --git a/Makefile.am b/Makefile.am
index 4e4ce89..1290551 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -8,7 +8,7 @@ AM_CFLAGS=-Wall
SUBDIRS = . tests
include_HEADERS = urcu.h urcu-bp.h urcu-call-rcu.h urcu-defer.h \
- urcu-pointer.h urcu-qsbr.h
+ urcu-pointer.h urcu-qsbr.h urcu-flavor.h
nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \
urcu/rculist.h urcu/rcuhlist.h urcu/system.h urcu/futex.h \
urcu/uatomic/generic.h urcu/arch/generic.h urcu/wfstack.h \
diff --git a/urcu-bp.c b/urcu-bp.c
index 4c0ab54..3b2062d 100644
--- a/urcu-bp.c
+++ b/urcu-bp.c
@@ -421,5 +421,7 @@ void rcu_bp_after_fork_child(void)
assert(!ret);
}
+DEFINE_RCU_FLAVOR()
+
#include "urcu-call-rcu-impl.h"
#include "urcu-defer-impl.h"
diff --git a/urcu-bp.h b/urcu-bp.h
index 451bedb..efb5dca 100644
--- a/urcu-bp.h
+++ b/urcu-bp.h
@@ -135,5 +135,6 @@ static inline void rcu_thread_online(void)
#include <urcu-call-rcu.h>
#include <urcu-defer.h>
+#include <urcu-flavor.h>
#endif /* _URCU_BP_H */
diff --git a/urcu-flavor.h b/urcu-flavor.h
new file mode 100644
index 0000000..e46c9a1
--- /dev/null
+++ b/urcu-flavor.h
@@ -0,0 +1,65 @@
+#ifndef _URCU_FLAVOR_H
+#define _URCU_FLAVOR_H
+
+/*
+ * urcu-flavor.h
+ *
+ * Userspace RCU header - rcu flavor declarations
+ *
+ * Copyright (c) 2011 Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct rcu_flavor_struct {
+ void (*read_lock)(void);
+ void (*read_unlock)(void);
+ void (*read_quiescent_state)(void);
+ void (*update_call_rcu)(struct rcu_head *head,
+ void (*func)(struct rcu_head *head));
+ void (*update_synchronize_rcu)(void);
+ void (*update_defer_rcu)(void (*fct)(void *p), void *p);
+
+ void (*thread_offline)(void);
+ void (*thread_online)(void);
+ void (*register_thread)(void);
+ void (*unregister_thread)(void);
+};
+
+#define DEFINE_RCU_FLAVOR() \
+const struct rcu_flavor_struct rcu_flavor = { \
+ .read_lock = rcu_read_lock, \
+ .read_unlock = rcu_read_unlock, \
+ .read_quiescent_state = rcu_quiescent_state, \
+ .update_call_rcu = call_rcu, \
+ .update_synchronize_rcu = synchronize_rcu, \
+ .update_defer_rcu = defer_rcu, \
+ .thread_offline = rcu_thread_offline, \
+ .thread_online = rcu_thread_online, \
+ .register_thread = rcu_register_thread, \
+ .unregister_thread = rcu_unregister_thread,\
+};
+
+extern const struct rcu_flavor_struct rcu_flavor;
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _URCU_FLAVOR_H */
diff --git a/urcu-qsbr.c b/urcu-qsbr.c
index 5530295..06e81c7 100644
--- a/urcu-qsbr.c
+++ b/urcu-qsbr.c
@@ -356,5 +356,7 @@ void rcu_exit(void)
*/
}
+DEFINE_RCU_FLAVOR()
+
#include "urcu-call-rcu-impl.h"
#include "urcu-defer-impl.h"
diff --git a/urcu-qsbr.h b/urcu-qsbr.h
index b362304..a2f6575 100644
--- a/urcu-qsbr.h
+++ b/urcu-qsbr.h
@@ -127,5 +127,6 @@ extern void rcu_unregister_thread(void);
#include <urcu-call-rcu.h>
#include <urcu-defer.h>
+#include <urcu-flavor.h>
#endif /* _URCU_QSBR_H */
diff --git a/urcu.c b/urcu.c
index ba013d9..b434655 100644
--- a/urcu.c
+++ b/urcu.c
@@ -452,5 +452,7 @@ void rcu_exit(void)
#endif /* #ifdef RCU_SIGNAL */
+DEFINE_RCU_FLAVOR()
+
#include "urcu-call-rcu-impl.h"
#include "urcu-defer-impl.h"
diff --git a/urcu.h b/urcu.h
index 1ad971c..cd4fcbb 100644
--- a/urcu.h
+++ b/urcu.h
@@ -128,5 +128,6 @@ static inline void rcu_thread_online(void)
#include <urcu-call-rcu.h>
#include <urcu-defer.h>
+#include <urcu-flavor.h>
#endif /* _URCU_H */
diff --git a/urcu/map/urcu-bp.h b/urcu/map/urcu-bp.h
index 4abe8dc..16601a1 100644
--- a/urcu/map/urcu-bp.h
+++ b/urcu/map/urcu-bp.h
@@ -64,4 +64,6 @@
#define rcu_defer_barrier rcu_defer_barrier_bp
#define rcu_defer_barrier_thread rcu_defer_barrier_thread_bp
+#define rcu_flavor rcu_flavor_bp
+
#endif /* _URCU_BP_MAP_H */
diff --git a/urcu/map/urcu-qsbr.h b/urcu/map/urcu-qsbr.h
index 0d88d83..a95441d 100644
--- a/urcu/map/urcu-qsbr.h
+++ b/urcu/map/urcu-qsbr.h
@@ -66,4 +66,6 @@
#define rcu_defer_barrier rcu_defer_barrier_qsbr
#define rcu_defer_barrier_thread rcu_defer_barrier_thread_qsbr
+#define rcu_flavor rcu_flavor_qsbr
+
#endif /* _URCU_QSBR_MAP_H */
diff --git a/urcu/map/urcu.h b/urcu/map/urcu.h
index 3f436a7..dd7a691 100644
--- a/urcu/map/urcu.h
+++ b/urcu/map/urcu.h
@@ -95,6 +95,8 @@
#define rcu_defer_barrier rcu_defer_barrier_memb
#define rcu_defer_barrier_thread rcu_defer_barrier_thread_memb
+#define rcu_flavor rcu_flavor_memb
+
#elif defined(RCU_SIGNAL)
#define rcu_read_lock rcu_read_lock_sig
@@ -127,6 +129,8 @@
#define rcu_defer_barrier rcu_defer_barrier_sig
#define rcu_defer_barrier_thread rcu_defer_barrier_thread_sig
+#define rcu_flavor rcu_flavor_sig
+
#elif defined(RCU_MB)
#define rcu_read_lock rcu_read_lock_mb
@@ -159,6 +163,8 @@
#define rcu_defer_barrier rcu_defer_barrier_mb
#define rcu_defer_barrier_thread rcu_defer_barrier_thread_mb
+#define rcu_flavor rcu_flavor_mb
+
#else
#error "Undefined selection"
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (6 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 07/12] Add rcu_flavor Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:24 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 09/12] remove struct rcu_table Lai Jiangshan
` (4 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Make the sizeof(struct cds_lfht) smaller
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 64 +++++++++++++++++------------------------------------
urcu/rculfhash.h | 18 +++-----------
2 files changed, 25 insertions(+), 57 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 4a611a1..18cead3 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -160,6 +160,7 @@
#include "config.h"
#include <urcu.h>
#include <urcu-call-rcu.h>
+#include <urcu-flavor.h>
#include <urcu/arch.h>
#include <urcu/uatomic.h>
#include <urcu/compiler.h>
@@ -278,15 +279,7 @@ struct cds_lfht {
*/
pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
unsigned int in_progress_resize, in_progress_destroy;
- void (*cds_lfht_call_rcu)(struct rcu_head *head,
- void (*func)(struct rcu_head *head));
- void (*cds_lfht_synchronize_rcu)(void);
- void (*cds_lfht_rcu_read_lock)(void);
- void (*cds_lfht_rcu_read_unlock)(void);
- void (*cds_lfht_rcu_thread_offline)(void);
- void (*cds_lfht_rcu_thread_online)(void);
- void (*cds_lfht_rcu_register_thread)(void);
- void (*cds_lfht_rcu_unregister_thread)(void);
+ const struct rcu_flavor_struct *flavor;
pthread_attr_t *resize_attr; /* Resize threads attributes */
long count; /* global approximate item count */
struct ht_items_count *split_count; /* split item count */
@@ -1075,9 +1068,9 @@ void *partition_resize_thread(void *arg)
{
struct partition_resize_work *work = arg;
- work->ht->cds_lfht_rcu_register_thread();
+ work->ht->flavor->register_thread();
work->fct(work->ht, work->i, work->start, work->len);
- work->ht->cds_lfht_rcu_unregister_thread();
+ work->ht->flavor->unregister_thread();
return NULL;
}
@@ -1141,7 +1134,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
unsigned long j, size = 1UL << (i - 1);
assert(i > MIN_TABLE_ORDER);
- ht->cds_lfht_rcu_read_lock();
+ ht->flavor->read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *new_node = bucket_at(ht, j);
@@ -1151,7 +1144,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
new_node->reverse_hash = bit_reverse_ulong(j);
_cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
}
- ht->cds_lfht_rcu_read_unlock();
+ ht->flavor->read_unlock();
}
static
@@ -1160,9 +1153,9 @@ void init_table_populate(struct cds_lfht *ht, unsigned long i,
{
assert(nr_cpus_mask != -1);
if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD) {
- ht->cds_lfht_rcu_thread_online();
+ ht->flavor->thread_online();
init_table_populate_partition(ht, i, 0, len);
- ht->cds_lfht_rcu_thread_offline();
+ ht->flavor->thread_offline();
return;
}
partition_resize_helper(ht, i, len, init_table_populate_partition);
@@ -1239,7 +1232,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
unsigned long j, size = 1UL << (i - 1);
assert(i > MIN_TABLE_ORDER);
- ht->cds_lfht_rcu_read_lock();
+ ht->flavor->read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *fini_node = bucket_at(ht, j);
@@ -1249,7 +1242,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
fini_node->reverse_hash = bit_reverse_ulong(j);
(void) _cds_lfht_del(ht, size, fini_node, 1);
}
- ht->cds_lfht_rcu_read_unlock();
+ ht->flavor->read_unlock();
}
static
@@ -1258,9 +1251,9 @@ void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
assert(nr_cpus_mask != -1);
if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD) {
- ht->cds_lfht_rcu_thread_online();
+ ht->flavor->thread_online();
remove_table_partition(ht, i, 0, len);
- ht->cds_lfht_rcu_thread_offline();
+ ht->flavor->thread_offline();
return;
}
partition_resize_helper(ht, i, len, remove_table_partition);
@@ -1295,7 +1288,7 @@ void fini_table(struct cds_lfht *ht,
* releasing the old bucket nodes. Otherwise their lookup will
* return a logically removed node as insert position.
*/
- ht->cds_lfht_synchronize_rcu();
+ ht->flavor->update_synchronize_rcu();
if (free_by_rcu_order)
cds_lfht_free_bucket_table(ht, free_by_rcu_order);
@@ -1315,7 +1308,7 @@ void fini_table(struct cds_lfht *ht,
}
if (free_by_rcu_order) {
- ht->cds_lfht_synchronize_rcu();
+ ht->flavor->update_synchronize_rcu();
cds_lfht_free_bucket_table(ht, free_by_rcu_order);
}
}
@@ -1368,15 +1361,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
unsigned long max_nr_buckets,
int flags,
- void (*cds_lfht_call_rcu)(struct rcu_head *head,
- void (*func)(struct rcu_head *head)),
- void (*cds_lfht_synchronize_rcu)(void),
- void (*cds_lfht_rcu_read_lock)(void),
- void (*cds_lfht_rcu_read_unlock)(void),
- void (*cds_lfht_rcu_thread_offline)(void),
- void (*cds_lfht_rcu_thread_online)(void),
- void (*cds_lfht_rcu_register_thread)(void),
- void (*cds_lfht_rcu_unregister_thread)(void),
+ const struct rcu_flavor_struct *flavor,
pthread_attr_t *attr)
{
struct cds_lfht *ht;
@@ -1404,14 +1389,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
- ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
- ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
- ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
- ht->cds_lfht_rcu_read_unlock = cds_lfht_rcu_read_unlock;
- ht->cds_lfht_rcu_thread_offline = cds_lfht_rcu_thread_offline;
- ht->cds_lfht_rcu_thread_online = cds_lfht_rcu_thread_online;
- ht->cds_lfht_rcu_register_thread = cds_lfht_rcu_register_thread;
- ht->cds_lfht_rcu_unregister_thread = cds_lfht_rcu_unregister_thread;
+ ht->flavor = flavor;
ht->resize_attr = attr;
alloc_split_items_count(ht);
/* this mutex should not nest in read-side C.S. */
@@ -1788,11 +1766,11 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
{
resize_target_update_count(ht, new_size);
CMM_STORE_SHARED(ht->t.resize_initiated, 1);
- ht->cds_lfht_rcu_thread_offline();
+ ht->flavor->thread_offline();
pthread_mutex_lock(&ht->resize_mutex);
_do_cds_lfht_resize(ht);
pthread_mutex_unlock(&ht->resize_mutex);
- ht->cds_lfht_rcu_thread_online();
+ ht->flavor->thread_online();
}
static
@@ -1802,11 +1780,11 @@ void do_resize_cb(struct rcu_head *head)
caa_container_of(head, struct rcu_resize_work, head);
struct cds_lfht *ht = work->ht;
- ht->cds_lfht_rcu_thread_offline();
+ ht->flavor->thread_offline();
pthread_mutex_lock(&ht->resize_mutex);
_do_cds_lfht_resize(ht);
pthread_mutex_unlock(&ht->resize_mutex);
- ht->cds_lfht_rcu_thread_online();
+ ht->flavor->thread_online();
poison_free(work);
cmm_smp_mb(); /* finish resize before decrement */
uatomic_dec(&ht->in_progress_resize);
@@ -1828,7 +1806,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
}
work = malloc(sizeof(*work));
work->ht = ht;
- ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
+ ht->flavor->update_call_rcu(&work->head, do_resize_cb);
CMM_STORE_SHARED(ht->t.resize_initiated, 1);
}
}
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index bff883f..a886b04 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -29,6 +29,7 @@
#include <stdint.h>
#include <urcu/compiler.h>
#include <urcu-call-rcu.h>
+#include <urcu-flavor.h>
#ifdef __cplusplus
extern "C" {
@@ -101,15 +102,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
unsigned long max_nr_buckets,
int flags,
- void (*cds_lfht_call_rcu)(struct rcu_head *head,
- void (*func)(struct rcu_head *head)),
- void (*cds_lfht_synchronize_rcu)(void),
- void (*cds_lfht_rcu_read_lock)(void),
- void (*cds_lfht_rcu_read_unlock)(void),
- void (*cds_lfht_rcu_thread_offline)(void),
- void (*cds_lfht_rcu_thread_online)(void),
- void (*cds_lfht_rcu_register_thread)(void),
- void (*cds_lfht_rcu_unregister_thread)(void),
+ const struct rcu_flavor_struct *flavor,
pthread_attr_t *attr);
/*
@@ -144,11 +137,8 @@ struct cds_lfht *cds_lfht_new(unsigned long init_size,
int flags,
pthread_attr_t *attr)
{
- return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags,
- call_rcu, synchronize_rcu, rcu_read_lock,
- rcu_read_unlock, rcu_thread_offline,
- rcu_thread_online, rcu_register_thread,
- rcu_unregister_thread, attr);
+ return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
+ flags, &rcu_flavor, attr);
}
/*
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 09/12] remove struct rcu_table
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (7 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:25 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c Lai Jiangshan
` (3 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
rculfhash.c | 107 +++++++++++++++++++++++++++-------------------------------
1 files changed, 50 insertions(+), 57 deletions(-)
diff --git a/rculfhash.c b/rculfhash.c
index 18cead3..8dc9c59 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -240,36 +240,14 @@ struct ht_items_count {
} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
/*
- * rcu_table: Contains the size and desired new size if a resize
- * operation is in progress, as well as the statically-sized array of
- * bucket table pointers.
- */
-struct rcu_table {
- unsigned long size; /* always a power of 2, shared (RCU) */
- unsigned long resize_target;
- int resize_initiated;
-
- /*
- * Contains the per order-index-level bucket node table. The size
- * of each bucket node table is half the number of hashes contained
- * in this order (except for order 0). The minimum allocation size
- * parameter allows combining the bucket node arrays of the lowermost
- * levels to improve cache locality for small index orders.
- */
- struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
-};
-
-/*
* cds_lfht: Top-level data structure representing a lock-free hash
* table. Defined in the implementation file to make it be an opaque
* cookie to users.
*/
struct cds_lfht {
- struct rcu_table t;
- unsigned long min_alloc_buckets_order;
- unsigned long min_nr_alloc_buckets;
- unsigned long max_nr_buckets;
+ unsigned long size; /* always a power of 2, shared (RCU) */
int flags;
+
/*
* We need to put the work threads offline (QSBR) when taking this
* mutex, because we use synchronize_rcu within this mutex critical
@@ -278,11 +256,26 @@ struct cds_lfht {
* completion.
*/
pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
+ pthread_attr_t *resize_attr; /* Resize threads attributes */
unsigned int in_progress_resize, in_progress_destroy;
+ unsigned long resize_target;
+ int resize_initiated;
const struct rcu_flavor_struct *flavor;
- pthread_attr_t *resize_attr; /* Resize threads attributes */
+
long count; /* global approximate item count */
struct ht_items_count *split_count; /* split item count */
+
+ unsigned long min_alloc_buckets_order;
+ unsigned long min_nr_alloc_buckets;
+ unsigned long max_nr_buckets;
+ /*
+ * Contains the per order-index-level bucket node table. The size
+ * of each bucket node table is half the number of hashes contained
+ * in this order (except for order 0). The minimum allocation size
+ * parameter allows combining the bucket node arrays of the lowermost
+ * levels to improve cache locality for small index orders.
+ */
+ struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
};
/*
@@ -751,13 +744,13 @@ static
void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
{
if (order == 0) {
- ht->t.tbl[0] = calloc(ht->min_nr_alloc_buckets,
+ ht->tbl[0] = calloc(ht->min_nr_alloc_buckets,
sizeof(struct cds_lfht_node));
- assert(ht->t.tbl[0]);
+ assert(ht->tbl[0]);
} else if (order > ht->min_alloc_buckets_order) {
- ht->t.tbl[order] = calloc(1UL << (order -1),
+ ht->tbl[order] = calloc(1UL << (order -1),
sizeof(struct cds_lfht_node));
- assert(ht->t.tbl[order]);
+ assert(ht->tbl[order]);
}
/* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
}
@@ -771,9 +764,9 @@ static
void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
{
if (order == 0)
- poison_free(ht->t.tbl[0]);
+ poison_free(ht->tbl[0]);
else if (order > ht->min_alloc_buckets_order)
- poison_free(ht->t.tbl[order]);
+ poison_free(ht->tbl[order]);
/* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
}
@@ -785,7 +778,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
if ((__builtin_constant_p(index) && index == 0)
|| index < ht->min_nr_alloc_buckets) {
dbg_printf("bucket index %lu order 0 aridx 0\n", index);
- return &ht->t.tbl[0][index];
+ return &ht->tbl[0][index];
}
/*
* equivalent to get_count_order_ulong(index + 1), but optimizes
@@ -795,7 +788,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
order = fls_ulong(index);
dbg_printf("bucket index %lu order %lu aridx %lu\n",
index, order, index & ((1UL << (order - 1)) - 1));
- return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
+ return &ht->tbl[order][index & ((1UL << (order - 1)) - 1)];
}
static inline
@@ -1177,7 +1170,7 @@ void init_table(struct cds_lfht *ht,
dbg_printf("init order %lu len: %lu\n", i, len);
/* Stop expand if the resize target changes under us */
- if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
+ if (CMM_LOAD_SHARED(ht->resize_target) < (1UL << i))
break;
cds_lfht_alloc_bucket_table(ht, i);
@@ -1192,7 +1185,7 @@ void init_table(struct cds_lfht *ht,
* Update table size.
*/
cmm_smp_wmb(); /* populate data before RCU size */
- CMM_STORE_SHARED(ht->t.size, 1UL << i);
+ CMM_STORE_SHARED(ht->size, 1UL << i);
dbg_printf("init new size: %lu\n", 1UL << i);
if (CMM_LOAD_SHARED(ht->in_progress_destroy))
@@ -1276,11 +1269,11 @@ void fini_table(struct cds_lfht *ht,
dbg_printf("fini order %lu len: %lu\n", i, len);
/* Stop shrink if the resize target changes under us */
- if (CMM_LOAD_SHARED(ht->t.resize_target) > (1UL << (i - 1)))
+ if (CMM_LOAD_SHARED(ht->resize_target) > (1UL << (i - 1)))
break;
cmm_smp_wmb(); /* populate data before RCU size */
- CMM_STORE_SHARED(ht->t.size, 1UL << (i - 1));
+ CMM_STORE_SHARED(ht->size, 1UL << (i - 1));
/*
* We need to wait for all add operations to reach Q.S. (and
@@ -1395,12 +1388,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
/* this mutex should not nest in read-side C.S. */
pthread_mutex_init(&ht->resize_mutex, NULL);
order = get_count_order_ulong(init_size);
- ht->t.resize_target = 1UL << order;
+ ht->resize_target = 1UL << order;
ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
ht->max_nr_buckets = max_nr_buckets;
cds_lfht_create_bucket(ht, 1UL << order);
- ht->t.size = 1UL << order;
+ ht->size = 1UL << order;
return ht;
}
@@ -1413,7 +1406,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
reverse_hash = bit_reverse_ulong(hash);
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
bucket = lookup_bucket(ht, size, hash);
/* We can always skip the bucket node initially */
node = rcu_dereference(bucket->next);
@@ -1513,7 +1506,7 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
unsigned long size;
node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
_cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
ht_count_add(ht, size, hash);
}
@@ -1528,7 +1521,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
struct cds_lfht_iter iter;
node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
_cds_lfht_add(ht, match, key, size, node, &iter, 0);
if (iter.node == node)
ht_count_add(ht, size, hash);
@@ -1545,7 +1538,7 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
struct cds_lfht_iter iter;
node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
for (;;) {
_cds_lfht_add(ht, match, key, size, node, &iter, 0);
if (iter.node == node) {
@@ -1563,7 +1556,7 @@ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
{
unsigned long size;
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
return _cds_lfht_replace(ht, size, old_iter->node, old_iter->next,
new_node);
}
@@ -1573,7 +1566,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
unsigned long size, hash;
int ret;
- size = rcu_dereference(ht->t.size);
+ size = rcu_dereference(ht->size);
ret = _cds_lfht_del(ht, size, iter->node, 0);
if (!ret) {
hash = bit_reverse_ulong(iter->node->reverse_hash);
@@ -1600,7 +1593,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
* size accessed without rcu_dereference because hash table is
* being destroyed.
*/
- size = ht->t.size;
+ size = ht->size;
/* Internal sanity check: all nodes left should be bucket */
for (i = 0; i < size; i++) {
node = bucket_at(ht, i);
@@ -1734,23 +1727,23 @@ void _do_cds_lfht_resize(struct cds_lfht *ht)
assert(uatomic_read(&ht->in_progress_resize));
if (CMM_LOAD_SHARED(ht->in_progress_destroy))
break;
- ht->t.resize_initiated = 1;
- old_size = ht->t.size;
- new_size = CMM_LOAD_SHARED(ht->t.resize_target);
+ ht->resize_initiated = 1;
+ old_size = ht->size;
+ new_size = CMM_LOAD_SHARED(ht->resize_target);
if (old_size < new_size)
_do_cds_lfht_grow(ht, old_size, new_size);
else if (old_size > new_size)
_do_cds_lfht_shrink(ht, old_size, new_size);
- ht->t.resize_initiated = 0;
+ ht->resize_initiated = 0;
/* write resize_initiated before read resize_target */
cmm_smp_mb();
- } while (ht->t.size != CMM_LOAD_SHARED(ht->t.resize_target));
+ } while (ht->size != CMM_LOAD_SHARED(ht->resize_target));
}
static
unsigned long resize_target_grow(struct cds_lfht *ht, unsigned long new_size)
{
- return _uatomic_xchg_monotonic_increase(&ht->t.resize_target, new_size);
+ return _uatomic_xchg_monotonic_increase(&ht->resize_target, new_size);
}
static
@@ -1759,13 +1752,13 @@ void resize_target_update_count(struct cds_lfht *ht,
{
count = max(count, MIN_TABLE_SIZE);
count = min(count, ht->max_nr_buckets);
- uatomic_set(&ht->t.resize_target, count);
+ uatomic_set(&ht->resize_target, count);
}
void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
{
resize_target_update_count(ht, new_size);
- CMM_STORE_SHARED(ht->t.resize_initiated, 1);
+ CMM_STORE_SHARED(ht->resize_initiated, 1);
ht->flavor->thread_offline();
pthread_mutex_lock(&ht->resize_mutex);
_do_cds_lfht_resize(ht);
@@ -1797,7 +1790,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
/* Store resize_target before read resize_initiated */
cmm_smp_mb();
- if (!CMM_LOAD_SHARED(ht->t.resize_initiated)) {
+ if (!CMM_LOAD_SHARED(ht->resize_initiated)) {
uatomic_inc(&ht->in_progress_resize);
cmm_smp_mb(); /* increment resize count before load destroy */
if (CMM_LOAD_SHARED(ht->in_progress_destroy)) {
@@ -1807,7 +1800,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
work = malloc(sizeof(*work));
work->ht = ht;
ht->flavor->update_call_rcu(&work->head, do_resize_cb);
- CMM_STORE_SHARED(ht->t.resize_initiated, 1);
+ CMM_STORE_SHARED(ht->resize_initiated, 1);
}
}
@@ -1845,7 +1838,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
for (;;) {
unsigned long s;
- s = uatomic_cmpxchg(&ht->t.resize_target, size, count);
+ s = uatomic_cmpxchg(&ht->resize_target, size, count);
if (s == size)
break; /* no resize needed */
if (s > size)
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (8 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 09/12] remove struct rcu_table Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:27 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management Lai Jiangshan
` (2 subsequent siblings)
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
Makefile.am | 5 ++-
rculfhash-internal.h | 115 ++++++++++++++++++++++++++++++++++++++++++++++++
rculfhash-mm-order.c | 101 ++++++++++++++++++++++++++++++++++++++++++
rculfhash.c | 119 +++++---------------------------------------------
urcu/rculfhash.h | 14 +++++-
5 files changed, 245 insertions(+), 109 deletions(-)
create mode 100644 rculfhash-internal.h
create mode 100644 rculfhash-mm-order.c
diff --git a/Makefile.am b/Makefile.am
index 1290551..4d3f7bd 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -22,6 +22,7 @@ EXTRA_DIST = $(top_srcdir)/urcu/arch/*.h $(top_srcdir)/urcu/uatomic/*.h \
gpl-2.0.txt lgpl-2.1.txt lgpl-relicensing.txt \
README LICENSE compat_arch_x86.c \
urcu-call-rcu-impl.h urcu-defer-impl.h \
+ rculfhash-internal.h \
ChangeLog API.txt
if COMPAT_ARCH
@@ -34,6 +35,8 @@ if COMPAT_FUTEX
COMPAT+=compat_futex.c
endif
+RCULFHASH=rculfhash.c rculfhash-mm-order.c
+
lib_LTLIBRARIES = liburcu-common.la \
liburcu.la liburcu-qsbr.la \
liburcu-mb.la liburcu-signal.la liburcu-bp.la \
@@ -62,7 +65,7 @@ liburcu_signal_la_LIBADD = liburcu-common.la
liburcu_bp_la_SOURCES = urcu-bp.c urcu-pointer.c $(COMPAT)
liburcu_bp_la_LIBADD = liburcu-common.la
-liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c rculfhash.c $(COMPAT)
+liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c $(RCULFHASH) $(COMPAT)
liburcu_cds_la_LIBADD = liburcu-common.la
pkgconfigdir = $(libdir)/pkgconfig
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
new file mode 100644
index 0000000..820e62c
--- /dev/null
+++ b/rculfhash-internal.h
@@ -0,0 +1,115 @@
+#ifndef _URCU_RCULFHASH_INTERNAL_H
+#define _URCU_RCULFHASH_INTERNAL_H
+
+/*
+ * urcu/rculfhash-internal.h
+ *
+ * Internal header for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <urcu/rculfhash.h>
+
+#ifdef DEBUG
+#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
+#else
+#define dbg_printf(fmt, args...)
+#endif
+
+#if (CAA_BITS_PER_LONG == 32)
+#define MAX_TABLE_ORDER 32
+#else
+#define MAX_TABLE_ORDER 64
+#endif
+
+#ifndef min
+#define min(a, b) ((a) < (b) ? (a) : (b))
+#endif
+
+#ifndef max
+#define max(a, b) ((a) > (b) ? (a) : (b))
+#endif
+
+struct ht_items_count;
+
+/*
+ * cds_lfht: Top-level data structure representing a lock-free hash
+ * table. Defined in the implementation file to make it be an opaque
+ * cookie to users.
+ */
+struct cds_lfht {
+ unsigned long size; /* always a power of 2, shared (RCU) */
+ int flags;
+
+ /*
+ * We need to put the work threads offline (QSBR) when taking this
+ * mutex, because we use synchronize_rcu within this mutex critical
+ * section, which waits on read-side critical sections, and could
+ * therefore cause grace-period deadlock if we hold off RCU G.P.
+ * completion.
+ */
+ pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
+ pthread_attr_t *resize_attr; /* Resize threads attributes */
+ unsigned int in_progress_resize, in_progress_destroy;
+ unsigned long resize_target;
+ int resize_initiated;
+ const struct rcu_flavor_struct *flavor;
+
+ long count; /* global approximate item count */
+ struct ht_items_count *split_count; /* split item count */
+
+ /* memory management related fields are located at the end */
+ const struct cds_lfht_mm_type *mm;
+
+ unsigned long min_alloc_buckets_order;
+ unsigned long min_nr_alloc_buckets;
+ unsigned long max_nr_buckets;
+
+ struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
+ unsigned long index);
+
+ union {
+ /*
+ * Contains the per order-index-level bucket node table.
+ * The size of each bucket node table is half the number
+ * of hashes contained in this order (except for order 0).
+ * The minimum allocation buckets size parameter allows
+ * combining the bucket node arrays of the lowermost
+ * levels to improve cache locality for small index orders.
+ */
+ struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
+ };
+};
+
+extern unsigned int fls_ulong(unsigned long x);
+extern int get_count_order_ulong(unsigned long x);
+
+#ifdef POISON_FREE
+#define poison_free(ptr) \
+ do { \
+ if (ptr) { \
+ memset(ptr, 0x42, sizeof(*(ptr))); \
+ free(ptr); \
+ } \
+ } while (0)
+#else
+#define poison_free(ptr) free(ptr)
+#endif
+
+#endif /* _URCU_RCULFHASH_INTERNAL_H */
diff --git a/rculfhash-mm-order.c b/rculfhash-mm-order.c
new file mode 100644
index 0000000..69e2b62
--- /dev/null
+++ b/rculfhash-mm-order.c
@@ -0,0 +1,101 @@
+/*
+ * rculfhash-mm-order.c
+ *
+ * Order based memory management for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <rculfhash-internal.h>
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ ht->tbl_order[0] = calloc(ht->min_nr_alloc_buckets,
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_order[0]);
+ } else if (order > ht->min_alloc_buckets_order) {
+ ht->tbl_order[order] = calloc(1UL << (order -1),
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_order[order]);
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0)
+ poison_free(ht->tbl_order[0]);
+ else if (order > ht->min_alloc_buckets_order)
+ poison_free(ht->tbl_order[order]);
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+static
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+ unsigned long order;
+
+ if (index < ht->min_nr_alloc_buckets) {
+ dbg_printf("bucket index %lu order 0 aridx 0\n", index);
+ return &ht->tbl_order[0][index];
+ }
+ /*
+ * equivalent to get_count_order_ulong(index + 1), but optimizes
+ * away the non-existing 0 special-case for
+ * get_count_order_ulong.
+ */
+ order = fls_ulong(index);
+ dbg_printf("bucket index %lu order %lu aridx %lu\n",
+ index, order, index & ((1UL << (order - 1)) - 1));
+ return &ht->tbl_order[order][index & ((1UL << (order - 1)) - 1)];
+}
+
+static
+struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets)
+{
+ struct cds_lfht *ht;
+
+ ht = calloc(1, sizeof(struct cds_lfht));
+ assert(ht);
+
+ ht->mm = &cds_lfht_mm_order;
+
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
+
+ ht->bucket_at = bucket_at;
+
+ return ht;
+}
+
+const struct cds_lfht_mm_type cds_lfht_mm_order = {
+ .alloc_cds_lfht = alloc_cds_lfht,
+ .alloc_bucket_table = cds_lfht_alloc_bucket_table,
+ .free_bucket_table = cds_lfht_free_bucket_table,
+ .bucket_at = bucket_at,
+};
diff --git a/rculfhash.c b/rculfhash.c
index 8dc9c59..49c7863 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -165,15 +165,10 @@
#include <urcu/uatomic.h>
#include <urcu/compiler.h>
#include <urcu/rculfhash.h>
+#include <rculfhash-internal.h>
#include <stdio.h>
#include <pthread.h>
-#ifdef DEBUG
-#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
-#else
-#define dbg_printf(fmt, args...)
-#endif
-
/*
* Split-counters lazily update the global counter each 1024
* addition/removal. It automatically keeps track of resize required.
@@ -191,26 +186,12 @@
#define MIN_TABLE_ORDER 0
#define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
-#if (CAA_BITS_PER_LONG == 32)
-#define MAX_TABLE_ORDER 32
-#else
-#define MAX_TABLE_ORDER 64
-#endif
-
/*
* Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
*/
#define MIN_PARTITION_PER_THREAD_ORDER 12
#define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
-#ifndef min
-#define min(a, b) ((a) < (b) ? (a) : (b))
-#endif
-
-#ifndef max
-#define max(a, b) ((a) > (b) ? (a) : (b))
-#endif
-
/*
* The removed flag needs to be updated atomically with the pointer.
* It indicates that no node must attach to the node scheduled for
@@ -240,45 +221,6 @@ struct ht_items_count {
} __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
/*
- * cds_lfht: Top-level data structure representing a lock-free hash
- * table. Defined in the implementation file to make it be an opaque
- * cookie to users.
- */
-struct cds_lfht {
- unsigned long size; /* always a power of 2, shared (RCU) */
- int flags;
-
- /*
- * We need to put the work threads offline (QSBR) when taking this
- * mutex, because we use synchronize_rcu within this mutex critical
- * section, which waits on read-side critical sections, and could
- * therefore cause grace-period deadlock if we hold off RCU G.P.
- * completion.
- */
- pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
- pthread_attr_t *resize_attr; /* Resize threads attributes */
- unsigned int in_progress_resize, in_progress_destroy;
- unsigned long resize_target;
- int resize_initiated;
- const struct rcu_flavor_struct *flavor;
-
- long count; /* global approximate item count */
- struct ht_items_count *split_count; /* split item count */
-
- unsigned long min_alloc_buckets_order;
- unsigned long min_nr_alloc_buckets;
- unsigned long max_nr_buckets;
- /*
- * Contains the per order-index-level bucket node table. The size
- * of each bucket node table is half the number of hashes contained
- * in this order (except for order 0). The minimum allocation size
- * parameter allows combining the bucket node arrays of the lowermost
- * levels to improve cache locality for small index orders.
- */
- struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
-};
-
-/*
* rcu_resize_work: Contains arguments passed to RCU worker thread
* responsible for performing lazy resize.
*/
@@ -505,18 +447,6 @@ int get_count_order_ulong(unsigned long x)
return fls_ulong(x - 1);
}
-#ifdef POISON_FREE
-#define poison_free(ptr) \
- do { \
- if (ptr) { \
- memset(ptr, 0x42, sizeof(*(ptr))); \
- free(ptr); \
- } \
- } while (0)
-#else
-#define poison_free(ptr) free(ptr)
-#endif
-
static
void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth);
@@ -743,16 +673,7 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
static
void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
{
- if (order == 0) {
- ht->tbl[0] = calloc(ht->min_nr_alloc_buckets,
- sizeof(struct cds_lfht_node));
- assert(ht->tbl[0]);
- } else if (order > ht->min_alloc_buckets_order) {
- ht->tbl[order] = calloc(1UL << (order -1),
- sizeof(struct cds_lfht_node));
- assert(ht->tbl[order]);
- }
- /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+ return ht->mm->alloc_bucket_table(ht, order);
}
/*
@@ -763,32 +684,13 @@ void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
static
void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
{
- if (order == 0)
- poison_free(ht->tbl[0]);
- else if (order > ht->min_alloc_buckets_order)
- poison_free(ht->tbl[order]);
- /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+ return ht->mm->free_bucket_table(ht, order);
}
static inline
struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
{
- unsigned long order;
-
- if ((__builtin_constant_p(index) && index == 0)
- || index < ht->min_nr_alloc_buckets) {
- dbg_printf("bucket index %lu order 0 aridx 0\n", index);
- return &ht->tbl[0][index];
- }
- /*
- * equivalent to get_count_order_ulong(index + 1), but optimizes
- * away the non-existing 0 special-case for
- * get_count_order_ulong.
- */
- order = fls_ulong(index);
- dbg_printf("bucket index %lu order %lu aridx %lu\n",
- index, order, index & ((1UL << (order - 1)) - 1));
- return &ht->tbl[order][index & ((1UL << (order - 1)) - 1)];
+ return ht->bucket_at(ht, index);
}
static inline
@@ -1354,6 +1256,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
unsigned long max_nr_buckets,
int flags,
+ const struct cds_lfht_mm_type *mm,
const struct rcu_flavor_struct *flavor,
pthread_attr_t *attr)
{
@@ -1368,7 +1271,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
if (!init_size || (init_size & (init_size - 1)))
return NULL;
- if (!max_nr_buckets)
+ /* max_nr_buckets == 0 for order based mm means infinite */
+ if (mm == &cds_lfht_mm_order && !max_nr_buckets)
max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
/* max_nr_buckets must be power of two */
@@ -1379,8 +1283,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
init_size = max(init_size, MIN_TABLE_SIZE);
max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
init_size = min(init_size, max_nr_buckets);
- ht = calloc(1, sizeof(struct cds_lfht));
+
+ ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets);
assert(ht);
+ assert(ht->mm == mm);
+ assert(ht->bucket_at == mm->bucket_at);
+
ht->flags = flags;
ht->flavor = flavor;
ht->resize_attr = attr;
@@ -1389,9 +1297,6 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
pthread_mutex_init(&ht->resize_mutex, NULL);
order = get_count_order_ulong(init_size);
ht->resize_target = 1UL << order;
- ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
- ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
- ht->max_nr_buckets = max_nr_buckets;
cds_lfht_create_bucket(ht, 1UL << order);
ht->size = 1UL << order;
return ht;
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index a886b04..926aa14 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -95,6 +95,17 @@ enum {
CDS_LFHT_ACCOUNTING = (1U << 1),
};
+struct cds_lfht_mm_type {
+ struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets);
+ void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order);
+ void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order);
+ struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
+ unsigned long index);
+};
+
+extern const struct cds_lfht_mm_type cds_lfht_mm_order;
+
/*
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
*/
@@ -102,6 +113,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
unsigned long min_nr_alloc_buckets,
unsigned long max_nr_buckets,
int flags,
+ const struct cds_lfht_mm_type *mm,
const struct rcu_flavor_struct *flavor,
pthread_attr_t *attr);
@@ -138,7 +150,7 @@ struct cds_lfht *cds_lfht_new(unsigned long init_size,
pthread_attr_t *attr)
{
return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
- flags, &rcu_flavor, attr);
+ flags, &cds_lfht_mm_order, &rcu_flavor, attr);
}
/*
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (9 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:33 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c " Lai Jiangshan
2011-11-28 13:43 ` [lttng-dev] [PATCH 00/12] rculfhash memory managements Mathieu Desnoyers
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
Makefile.am | 2 +-
rculfhash-internal.h | 9 ++++
rculfhash-mm-chunk.c | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++
urcu/rculfhash.h | 1 +
4 files changed, 118 insertions(+), 1 deletions(-)
create mode 100644 rculfhash-mm-chunk.c
diff --git a/Makefile.am b/Makefile.am
index 4d3f7bd..853ecd5 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,7 +35,7 @@ if COMPAT_FUTEX
COMPAT+=compat_futex.c
endif
-RCULFHASH=rculfhash.c rculfhash-mm-order.c
+RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
lib_LTLIBRARIES = liburcu-common.la \
liburcu.la liburcu-qsbr.la \
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index 820e62c..fda4251 100644
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -38,6 +38,8 @@
#define MAX_TABLE_ORDER 64
#endif
+#define MAX_CHUNK_TABLE (1UL << 10)
+
#ifndef min
#define min(a, b) ((a) < (b) ? (a) : (b))
#endif
@@ -94,6 +96,13 @@ struct cds_lfht {
* levels to improve cache locality for small index orders.
*/
struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
+
+ /*
+ * Contains the bucket node chunks. The size of each bucket node
+ * chunk is ->min_alloc_size(avoid to alloc chunks with different
+ * size). chunks improve cache locality for small index orders
+ */
+ struct cds_lfht_node *tbl_chunk[0];
};
};
diff --git a/rculfhash-mm-chunk.c b/rculfhash-mm-chunk.c
new file mode 100644
index 0000000..0469776
--- /dev/null
+++ b/rculfhash-mm-chunk.c
@@ -0,0 +1,107 @@
+/*
+ * rculfhash-mm-chunk.c
+ *
+ * Chunk based memory management for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stddef.h>
+#include <rculfhash-internal.h>
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ ht->tbl_chunk[0] = calloc(ht->min_nr_alloc_buckets,
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_chunk[0]);
+ } else if (order > ht->min_alloc_buckets_order) {
+ unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order);
+
+ for (i = len; i < 2 * len; i++) {
+ ht->tbl_chunk[i] = calloc(ht->min_nr_alloc_buckets,
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_chunk[i]);
+ }
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0)
+ poison_free(ht->tbl_chunk[0]);
+ else if (order > ht->min_alloc_buckets_order) {
+ unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order);
+
+ for (i = len; i < 2 * len; i++)
+ poison_free(ht->tbl_chunk[i]);
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+static
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+ unsigned long chunk, offset;
+
+ chunk = index >> ht->min_alloc_buckets_order;
+ offset = index & (ht->min_nr_alloc_buckets - 1);
+ return &ht->tbl_chunk[chunk][offset];
+}
+
+static
+struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets)
+{
+ struct cds_lfht *ht;
+ unsigned long nr_chunks, cds_lfht_size;
+
+ min_nr_alloc_buckets = max(min_nr_alloc_buckets,
+ max_nr_buckets / MAX_CHUNK_TABLE);
+
+ nr_chunks = max_nr_buckets / min_nr_alloc_buckets;
+ cds_lfht_size = offsetof(struct cds_lfht, tbl_chunk) +
+ sizeof(ht->tbl_chunk[0]) * nr_chunks;
+ cds_lfht_size = max(cds_lfht_size, sizeof(struct cds_lfht));
+ ht = calloc(1, cds_lfht_size);
+ assert(ht);
+
+ ht->mm = &cds_lfht_mm_chunk;
+
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
+
+ ht->bucket_at = bucket_at;
+
+ return ht;
+}
+
+const struct cds_lfht_mm_type cds_lfht_mm_chunk = {
+ .alloc_cds_lfht = alloc_cds_lfht,
+ .alloc_bucket_table = cds_lfht_alloc_bucket_table,
+ .free_bucket_table = cds_lfht_free_bucket_table,
+ .bucket_at = bucket_at,
+};
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 926aa14..54e0cd8 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -105,6 +105,7 @@ struct cds_lfht_mm_type {
};
extern const struct cds_lfht_mm_type cds_lfht_mm_order;
+extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
/*
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (10 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management Lai Jiangshan
@ 2011-11-28 8:08 ` Lai Jiangshan
2011-11-28 13:43 ` Mathieu Desnoyers
2011-11-28 13:43 ` [lttng-dev] [PATCH 00/12] rculfhash memory managements Mathieu Desnoyers
12 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 8:08 UTC (permalink / raw)
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
---
Makefile.am | 3 +-
rculfhash-internal.h | 7 +++
rculfhash-mm-mmap.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++
urcu/rculfhash.h | 1 +
4 files changed, 157 insertions(+), 1 deletions(-)
create mode 100644 rculfhash-mm-mmap.c
diff --git a/Makefile.am b/Makefile.am
index 853ecd5..91a9fd1 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,7 +35,8 @@ if COMPAT_FUTEX
COMPAT+=compat_futex.c
endif
-RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
+RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \
+ rculfhash-mm-mmap.c
lib_LTLIBRARIES = liburcu-common.la \
liburcu.la liburcu-qsbr.la \
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index fda4251..5e65685 100644
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -103,6 +103,13 @@ struct cds_lfht {
* size). chunks improve cache locality for small index orders
*/
struct cds_lfht_node *tbl_chunk[0];
+
+ /*
+ * Contains all the room of buckets without memory allocated.
+ * All the per order-index-level bucket node tables will be
+ * allocated inside it when used.
+ */
+ struct cds_lfht_node *tbl_buckets;
};
};
diff --git a/rculfhash-mm-mmap.c b/rculfhash-mm-mmap.c
new file mode 100644
index 0000000..26aa2ed
--- /dev/null
+++ b/rculfhash-mm-mmap.c
@@ -0,0 +1,147 @@
+/*
+ * rculfhash-mm-mmap.c
+ *
+ * mmap/reservation based memory management for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <unistd.h>
+#include <sys/mman.h>
+#include <rculfhash-internal.h>
+
+/* reserve inaccessible memory space without allocation any memory */
+static void *memory_map(size_t length)
+{
+ void *ret = mmap(NULL, length, PROT_NONE,
+ MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret != MAP_FAILED);
+ return ret;
+}
+
+static void memory_unmap(void *ptr, size_t length)
+{
+ int ret = munmap(ptr, length);
+
+ assert(ret == 0);
+}
+
+static void memory_populate(void *ptr, size_t length)
+{
+ void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
+ MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret == ptr);
+}
+
+/*
+ * Discard garbage memory and avoid system save it when try to swap it out.
+ * Make it still reserved, inaccessible.
+ */
+static void memory_discard(void *ptr, size_t length)
+{
+ void *ret = mmap(ptr, length, PROT_NONE,
+ MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret == ptr);
+}
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) { /* small table */
+ ht->tbl_buckets = calloc(ht->max_nr_buckets, sizeof(*ht->tbl_buckets));
+ assert(ht->tbl_buckets);
+ return;
+ }
+ /* large table */
+ ht->tbl_buckets = memory_map(ht->max_nr_buckets * sizeof(*ht->tbl_buckets));
+ memory_populate(ht->tbl_buckets, ht->min_nr_alloc_buckets * sizeof(*ht->tbl_buckets));
+ } else if (order > ht->min_alloc_buckets_order) { /* large table */
+ unsigned long len = 1UL << (order - 1);
+
+ assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
+ memory_populate(ht->tbl_buckets + len, len * sizeof(*ht->tbl_buckets));
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) { /* small table */
+ poison_free(ht->tbl_buckets);
+ return;
+ }
+ /* large table */
+ memory_unmap(ht->tbl_buckets, ht->max_nr_buckets * sizeof(*ht->tbl_buckets));
+ } else if (order > ht->min_alloc_buckets_order) { /* large table */
+ unsigned long len = 1UL << (order - 1);
+
+ assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
+ memory_discard(ht->tbl_buckets + len, len * sizeof(*ht->tbl_buckets));
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+static
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+ return &ht->tbl_buckets[index];
+}
+
+static
+struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets)
+{
+ struct cds_lfht *ht;
+ unsigned long page_bucket_size = getpagesize() / sizeof(*ht->tbl_buckets);
+
+ if (max_nr_buckets <= page_bucket_size) /* small table */
+ min_nr_alloc_buckets = max_nr_buckets;
+ else /* large table */
+ min_nr_alloc_buckets = max(min_nr_alloc_buckets, page_bucket_size);
+
+
+ ht = calloc(1, sizeof(struct cds_lfht));
+ assert(ht);
+
+ ht->mm = &cds_lfht_mm_mmap;
+
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
+
+ ht->bucket_at = bucket_at;
+
+ return ht;
+}
+
+const struct cds_lfht_mm_type cds_lfht_mm_mmap = {
+ .alloc_cds_lfht = alloc_cds_lfht,
+ .alloc_bucket_table = cds_lfht_alloc_bucket_table,
+ .free_bucket_table = cds_lfht_free_bucket_table,
+ .bucket_at = bucket_at,
+};
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 54e0cd8..ec91e35 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -106,6 +106,7 @@ struct cds_lfht_mm_type {
extern const struct cds_lfht_mm_type cds_lfht_mm_order;
extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
+extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
/*
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
--
1.7.4.4
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability
2011-11-28 8:07 ` [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability Lai Jiangshan
@ 2011-11-28 13:01 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:01 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Fast path is not changed.
> It will slow down very little for slow path.
Merged, thanks Lai!
Mathieu
>
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
> rculfhash.c | 115 +++++++++++++++++++++++++++++++---------------------------
> 1 files changed, 61 insertions(+), 54 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 4f82da4..5ad7583 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -756,18 +756,14 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> return old2;
> }
>
> -static
> -struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
> - unsigned long hash)
> +static inline
> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> {
> - unsigned long index, order;
> -
> - assert(size > 0);
> - index = hash & (size - 1);
> + unsigned long order;
>
> - if (index < ht->min_alloc_size) {
> - dbg_printf("lookup hash %lu index %lu order 0 aridx 0\n",
> - hash, index);
> + if ((__builtin_constant_p(index) && index == 0)
> + || index < ht->min_alloc_size) {
> + dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> return &ht->t.tbl[0]->nodes[index];
> }
> /*
> @@ -776,11 +772,19 @@ struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
> * get_count_order_ulong.
> */
> order = fls_ulong(index);
> - dbg_printf("lookup hash %lu index %lu order %lu aridx %lu\n",
> - hash, index, order, index & ((1UL << (order - 1)) - 1));
> + dbg_printf("bucket index %lu order %lu aridx %lu\n",
> + index, order, index & ((1UL << (order - 1)) - 1));
> return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)];
> }
>
> +static inline
> +struct cds_lfht_node *lookup_bucket(struct cds_lfht *ht, unsigned long size,
> + unsigned long hash)
> +{
> + assert(size > 0);
> + return bucket_at(ht, hash & (size - 1));
> +}
> +
> /*
> * Remove all logically deleted nodes from a bucket up to a certain node key.
> */
> @@ -1106,19 +1110,18 @@ static
> void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> unsigned long start, unsigned long len)
> {
> - unsigned long j;
> + unsigned long j, size = 1UL << (i - 1);
>
> assert(i > ht->min_alloc_order);
> ht->cds_lfht_rcu_read_lock();
> - for (j = start; j < start + len; j++) {
> - struct cds_lfht_node *new_node = &ht->t.tbl[i]->nodes[j];
> -
> - dbg_printf("init populate: i %lu j %lu hash %lu\n",
> - i, j, (1UL << (i - 1)) + j);
> - new_node->reverse_hash =
> - bit_reverse_ulong((1UL << (i - 1)) + j);
> - _cds_lfht_add(ht, NULL, NULL, 1UL << (i - 1),
> - new_node, NULL, 1);
> + for (j = size + start; j < size + start + len; j++) {
> + struct cds_lfht_node *new_node = bucket_at(ht, j);
> +
> + assert(j >= size && j < (size << 1));
> + dbg_printf("init populate: order %lu index %lu hash %lu\n",
> + i, j, j);
> + new_node->reverse_hash = bit_reverse_ulong(j);
> + _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
> }
> ht->cds_lfht_rcu_read_unlock();
> }
> @@ -1206,18 +1209,18 @@ static
> void remove_table_partition(struct cds_lfht *ht, unsigned long i,
> unsigned long start, unsigned long len)
> {
> - unsigned long j;
> + unsigned long j, size = 1UL << (i - 1);
>
> assert(i > ht->min_alloc_order);
> ht->cds_lfht_rcu_read_lock();
> - for (j = start; j < start + len; j++) {
> - struct cds_lfht_node *fini_node = &ht->t.tbl[i]->nodes[j];
> -
> - dbg_printf("remove entry: i %lu j %lu hash %lu\n",
> - i, j, (1UL << (i - 1)) + j);
> - fini_node->reverse_hash =
> - bit_reverse_ulong((1UL << (i - 1)) + j);
> - (void) _cds_lfht_del(ht, 1UL << (i - 1), fini_node, 1);
> + for (j = size + start; j < size + start + len; j++) {
> + struct cds_lfht_node *fini_node = bucket_at(ht, j);
> +
> + assert(j >= size && j < (size << 1));
> + dbg_printf("remove entry: order %lu index %lu hash %lu\n",
> + i, j, j);
> + fini_node->reverse_hash = bit_reverse_ulong(j);
> + (void) _cds_lfht_del(ht, size, fini_node, 1);
> }
> ht->cds_lfht_rcu_read_unlock();
> }
> @@ -1294,14 +1297,15 @@ static
> void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
> {
> struct cds_lfht_node *prev, *node;
> - unsigned long order, len, i, j;
> + unsigned long order, len, i;
>
> ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
> assert(ht->t.tbl[0]);
>
> - dbg_printf("create bucket: order %lu index %lu hash %lu\n", 0, 0, 0);
> - ht->t.tbl[0]->nodes[0].next = flag_bucket(get_end());
> - ht->t.tbl[0]->nodes[0].reverse_hash = 0;
> + dbg_printf("create bucket: order 0 index 0 hash 0\n");
> + node = bucket_at(ht, 0);
> + node->next = flag_bucket(get_end());
> + node->reverse_hash = 0;
>
> for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
> len = 1UL << (order - 1);
> @@ -1312,22 +1316,28 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
> assert(ht->t.tbl[order]);
> }
>
> - i = 0;
> - prev = ht->t.tbl[i]->nodes;
> - for (j = 0; j < len; j++) {
> - if (j & (j - 1)) { /* Between power of 2 */
> - prev++;
> - } else if (j) { /* At each power of 2 */
> - i++;
> - prev = ht->t.tbl[i]->nodes;
> - }
> + for (i = 0; i < len; i++) {
> + /*
> + * Now, we are trying to init the node with the
> + * hash=(len+i) (which is also a bucket with the
> + * index=(len+i)) and insert it into the hash table,
> + * so this node has to be inserted after the bucket
> + * with the index=(len+i)&(len-1)=i. And because there
> + * is no other non-bucket node nor bucket node with
> + * larger index/hash inserted, so the bucket node
> + * being inserted should be inserted directly linked
> + * after the bucket node with index=i.
> + */
> + prev = bucket_at(ht, i);
> + node = bucket_at(ht, len + i);
>
> - node = &ht->t.tbl[order]->nodes[j];
> dbg_printf("create bucket: order %lu index %lu hash %lu\n",
> - order, j, j + len);
> + order, len + i, len + i);
> + node->reverse_hash = bit_reverse_ulong(len + i);
> +
> + /* insert after prev */
> + assert(is_bucket(prev->next));
> node->next = prev->next;
> - assert(is_bucket(node->next));
> - node->reverse_hash = bit_reverse_ulong(j + len);
> prev->next = flag_bucket(node);
> }
> }
> @@ -1477,14 +1487,11 @@ void cds_lfht_next(struct cds_lfht *ht, struct cds_lfht_iter *iter)
>
> void cds_lfht_first(struct cds_lfht *ht, struct cds_lfht_iter *iter)
> {
> - struct cds_lfht_node *lookup;
> -
> /*
> * Get next after first bucket node. The first bucket node is the
> * first node of the linked list.
> */
> - lookup = &ht->t.tbl[0]->nodes[0];
> - iter->next = lookup->next;
> + iter->next = bucket_at(ht, 0)->next;
> cds_lfht_next(ht, iter);
> }
>
> @@ -1570,7 +1577,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
> unsigned long order, i, size;
>
> /* Check that the table is empty */
> - node = &ht->t.tbl[0]->nodes[0];
> + node = bucket_at(ht, 0);
> do {
> node = clear_flag(node)->next;
> if (!is_bucket(node))
> @@ -1649,7 +1656,7 @@ void cds_lfht_count_nodes(struct cds_lfht *ht,
> *removed = 0;
>
> /* Count non-bucket nodes in the table */
> - node = &ht->t.tbl[0]->nodes[0];
> + node = bucket_at(ht, 0);
> do {
> next = rcu_dereference(node->next);
> if (is_removed(next)) {
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free
2011-11-28 8:07 ` [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free Lai Jiangshan
@ 2011-11-28 13:02 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:02 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
merged, thanks!
Mathieu
> ---
> rculfhash.c | 78 +++++++++++++++++++++++++++++++++++-----------------------
> 1 files changed, 47 insertions(+), 31 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 5ad7583..46bfa7a 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -756,6 +756,36 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> return old2;
> }
>
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0) {
> + ht->t.tbl[0] = calloc(ht->min_alloc_size,
> + sizeof(struct cds_lfht_node));
> + assert(ht->t.tbl[0]);
> + } else if (order > ht->min_alloc_order) {
> + ht->t.tbl[order] = calloc(1UL << (order -1),
> + sizeof(struct cds_lfht_node));
> + assert(ht->t.tbl[order]);
> + }
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0)
> + poison_free(ht->t.tbl[0]);
> + else if (order > ht->min_alloc_order)
> + poison_free(ht->t.tbl[order]);
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> +}
> +
> static inline
> struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> {
> @@ -1159,8 +1189,7 @@ void init_table(struct cds_lfht *ht,
> if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
> break;
>
> - ht->t.tbl[i] = calloc(1, len * sizeof(struct cds_lfht_node));
> - assert(ht->t.tbl[i]);
> + cds_lfht_alloc_bucket_table(ht, i);
>
> /*
> * Set all bucket nodes reverse hash values for a level and
> @@ -1244,7 +1273,7 @@ void fini_table(struct cds_lfht *ht,
> unsigned long first_order, unsigned long last_order)
> {
> long i;
> - void *free_by_rcu = NULL;
> + unsigned long free_by_rcu_order = 0;
>
> dbg_printf("fini table: first_order %lu last_order %lu\n",
> first_order, last_order);
> @@ -1269,8 +1298,8 @@ void fini_table(struct cds_lfht *ht,
> * return a logically removed node as insert position.
> */
> ht->cds_lfht_synchronize_rcu();
> - if (free_by_rcu)
> - free(free_by_rcu);
> + if (free_by_rcu_order)
> + cds_lfht_free_bucket_table(ht, free_by_rcu_order);
>
> /*
> * Set "removed" flag in bucket nodes about to be removed.
> @@ -1280,16 +1309,16 @@ void fini_table(struct cds_lfht *ht,
> */
> remove_table(ht, i, len);
>
> - free_by_rcu = ht->t.tbl[i];
> + free_by_rcu_order = i;
>
> dbg_printf("fini new size: %lu\n", 1UL << i);
> if (CMM_LOAD_SHARED(ht->in_progress_destroy))
> break;
> }
>
> - if (free_by_rcu) {
> + if (free_by_rcu_order) {
> ht->cds_lfht_synchronize_rcu();
> - free(free_by_rcu);
> + cds_lfht_free_bucket_table(ht, free_by_rcu_order);
> }
> }
>
> @@ -1299,8 +1328,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
> struct cds_lfht_node *prev, *node;
> unsigned long order, len, i;
>
> - ht->t.tbl[0] = calloc(1, ht->min_alloc_size * sizeof(struct cds_lfht_node));
> - assert(ht->t.tbl[0]);
> + cds_lfht_alloc_bucket_table(ht, 0);
>
> dbg_printf("create bucket: order 0 index 0 hash 0\n");
> node = bucket_at(ht, 0);
> @@ -1309,12 +1337,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>
> for (order = 1; order < get_count_order_ulong(size) + 1; order++) {
> len = 1UL << (order - 1);
> - if (order <= ht->min_alloc_order) {
> - ht->t.tbl[order] = (struct rcu_level *) (ht->t.tbl[0]->nodes + len);
> - } else {
> - ht->t.tbl[order] = calloc(1, len * sizeof(struct cds_lfht_node));
> - assert(ht->t.tbl[order]);
> - }
> + cds_lfht_alloc_bucket_table(ht, order);
>
> for (i = 0; i < len; i++) {
> /*
> @@ -1590,23 +1613,16 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
> */
> size = ht->t.size;
> /* Internal sanity check: all nodes left should be bucket */
> - for (order = 0; order < get_count_order_ulong(size) + 1; order++) {
> - unsigned long len;
> + for (i = 0; i < size; i++) {
> + node = bucket_at(ht, i);
> + dbg_printf("delete bucket: index %lu expected hash %lu hash %lu\n",
> + i, i, bit_reverse_ulong(node->reverse_hash));
> + assert(is_bucket(node->next));
> + }
>
> - len = !order ? 1 : 1UL << (order - 1);
> - for (i = 0; i < len; i++) {
> - dbg_printf("delete order %lu i %lu hash %lu\n",
> - order, i,
> - bit_reverse_ulong(ht->t.tbl[order]->nodes[i].reverse_hash));
> - assert(is_bucket(ht->t.tbl[order]->nodes[i].next));
> - }
> + for (order = get_count_order_ulong(size); (long)order >= 0; order--)
> + cds_lfht_free_bucket_table(ht, order);
>
> - if (order == ht->min_alloc_order)
> - poison_free(ht->t.tbl[0]);
> - else if (order > ht->min_alloc_order)
> - poison_free(ht->t.tbl[order]);
> - /* Nothing to delete for order < ht->min_alloc_order */
> - }
> return 0;
> }
>
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now
2011-11-28 8:07 ` [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now Lai Jiangshan
@ 2011-11-28 13:07 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:07 UTC (permalink / raw)
Merged as:
commit d0d8f9aa03e9df3ca61b8c823678e5c3a9640a4d
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date: Mon Nov 28 08:05:09 2011 -0500
it is not required that ht->t.size >= ht->min_table_size anymore
Original code always ensure ht->t.size >= ht->min_table_size.
This can be improved: ht->min_table_size should be used for allocation,
not for the bucket size in use.
Why does the original code need to always ensure this ?
Original code don't do special alloc/free when
ht->t.size < ht->min_table_size
in init_table()/fini_table(), so we have to force
ht->t.size >= ht->min_table_size.
Why does new code become flexible ?
New code use the wrappers, they handle the special cases.
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
diff --git a/rculfhash.c b/rculfhash.c
index 46bfa7a..8071915 100644
--- a/rculfhash.c
+++ b/rculfhash.c
@@ -187,7 +187,8 @@
/*
* Define the minimum table size.
*/
-#define MIN_TABLE_SIZE 1
+#define MIN_TABLE_ORDER 0
+#define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
#if (CAA_BITS_PER_LONG == 32)
#define MAX_TABLE_ORDER 32
@@ -1142,7 +1143,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
{
unsigned long j, size = 1UL << (i - 1);
- assert(i > ht->min_alloc_order);
+ assert(i > MIN_TABLE_ORDER);
ht->cds_lfht_rcu_read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *new_node = bucket_at(ht, j);
@@ -1178,7 +1179,7 @@ void init_table(struct cds_lfht *ht,
dbg_printf("init table: first_order %lu last_order %lu\n",
first_order, last_order);
- assert(first_order > ht->min_alloc_order);
+ assert(first_order > MIN_TABLE_ORDER);
for (i = first_order; i <= last_order; i++) {
unsigned long len;
@@ -1240,7 +1241,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
{
unsigned long j, size = 1UL << (i - 1);
- assert(i > ht->min_alloc_order);
+ assert(i > MIN_TABLE_ORDER);
ht->cds_lfht_rcu_read_lock();
for (j = size + start; j < size + start + len; j++) {
struct cds_lfht_node *fini_node = bucket_at(ht, j);
@@ -1277,7 +1278,7 @@ void fini_table(struct cds_lfht *ht,
dbg_printf("fini table: first_order %lu last_order %lu\n",
first_order, last_order);
- assert(first_order > ht->min_alloc_order);
+ assert(first_order > MIN_TABLE_ORDER);
for (i = last_order; i >= first_order; i--) {
unsigned long len;
@@ -1390,7 +1391,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
if (!init_size || (init_size & (init_size - 1)))
return NULL;
min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
- init_size = max(init_size, min_alloc_size);
+ init_size = max(init_size, MIN_TABLE_SIZE);
ht = calloc(1, sizeof(struct cds_lfht));
assert(ht);
ht->flags = flags;
@@ -1720,7 +1721,7 @@ void _do_cds_lfht_shrink(struct cds_lfht *ht,
{
unsigned long old_order, new_order;
- new_size = max(new_size, ht->min_alloc_size);
+ new_size = max(new_size, MIN_TABLE_SIZE);
old_order = get_count_order_ulong(old_size);
new_order = get_count_order_ulong(new_size);
dbg_printf("resize from %lu (order %lu) to %lu (order %lu) buckets\n",
@@ -1768,7 +1769,7 @@ static
void resize_target_update_count(struct cds_lfht *ht,
unsigned long count)
{
- count = max(count, ht->min_alloc_size);
+ count = max(count, MIN_TABLE_SIZE);
uatomic_set(&ht->t.resize_target, count);
}
@@ -1843,7 +1844,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
{
if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
return;
- count = max(count, ht->min_alloc_size);
+ count = max(count, MIN_TABLE_SIZE);
if (count == size)
return; /* Already the right size, no resize needed */
if (count > size) { /* lazy grow */
diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
index fe650f3..01ae01a 100644
--- a/tests/test_urcu_hash.c
+++ b/tests/test_urcu_hash.c
@@ -896,7 +896,7 @@ int main(int argc, char **argv)
return -1;
}
- if (min_hash_alloc_size && min_hash_alloc_size * (min_hash_alloc_size - 1)) {
+ if (min_hash_alloc_size && min_hash_alloc_size & (min_hash_alloc_size - 1)) {
printf("Error: Min hash alloc size %lu is not a power of 2.\n",
min_hash_alloc_size);
return -1;
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 04/12] remove struct rcu_level
2011-11-28 8:08 ` [lttng-dev] [PATCH 04/12] remove struct rcu_level Lai Jiangshan
@ 2011-11-28 13:08 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:08 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Merged, thanks!
Mathieu
> ---
> rculfhash.c | 28 ++++++++++++----------------
> 1 files changed, 12 insertions(+), 16 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 8071915..fd9241d 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -239,27 +239,23 @@ struct ht_items_count {
> } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>
> /*
> - * rcu_level: Contains the per order-index-level bucket node table. The
> - * size of each bucket node table is half the number of hashes contained
> - * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the bucket node arrays of the lowermost
> - * levels to improve cache locality for small index orders.
> - */
> -struct rcu_level {
> - /* Note: manually update allocation length when adding a field */
> - struct cds_lfht_node nodes[0];
> -};
> -
> -/*
> * rcu_table: Contains the size and desired new size if a resize
> * operation is in progress, as well as the statically-sized array of
> - * rcu_level pointers.
> + * bucket table pointers.
> */
> struct rcu_table {
> unsigned long size; /* always a power of 2, shared (RCU) */
> unsigned long resize_target;
> int resize_initiated;
> - struct rcu_level *tbl[MAX_TABLE_ORDER];
> +
> + /*
> + * Contains the per order-index-level bucket node table. The size
> + * of each bucket node table is half the number of hashes contained
> + * in this order (except for order 0). The minimum allocation size
> + * parameter allows combining the bucket node arrays of the lowermost
> + * levels to improve cache locality for small index orders.
> + */
> + struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> };
>
> /*
> @@ -795,7 +791,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> if ((__builtin_constant_p(index) && index == 0)
> || index < ht->min_alloc_size) {
> dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> - return &ht->t.tbl[0]->nodes[index];
> + return &ht->t.tbl[0][index];
> }
> /*
> * equivalent to get_count_order_ulong(index + 1), but optimizes
> @@ -805,7 +801,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> order = fls_ulong(index);
> dbg_printf("bucket index %lu order %lu aridx %lu\n",
> index, order, index & ((1UL << (order - 1)) - 1));
> - return &ht->t.tbl[order]->nodes[index & ((1UL << (order - 1)) - 1)];
> + return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
> }
>
> static inline
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order
2011-11-28 8:08 ` [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order Lai Jiangshan
@ 2011-11-28 13:14 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:14 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Suggested-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Merged, thanks!
Mathieu
> ---
> rculfhash.c | 28 ++++++++++++++--------------
> urcu/rculfhash.h | 8 ++++----
> 2 files changed, 18 insertions(+), 18 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index fd9241d..8282f09 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -265,8 +265,8 @@ struct rcu_table {
> */
> struct cds_lfht {
> struct rcu_table t;
> - unsigned long min_alloc_order;
> - unsigned long min_alloc_size;
> + unsigned long min_alloc_buckets_order;
> + unsigned long min_nr_alloc_buckets;
> int flags;
> /*
> * We need to put the work threads offline (QSBR) when taking this
> @@ -757,15 +757,15 @@ static
> void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> if (order == 0) {
> - ht->t.tbl[0] = calloc(ht->min_alloc_size,
> + ht->t.tbl[0] = calloc(ht->min_nr_alloc_buckets,
> sizeof(struct cds_lfht_node));
> assert(ht->t.tbl[0]);
> - } else if (order > ht->min_alloc_order) {
> + } else if (order > ht->min_alloc_buckets_order) {
> ht->t.tbl[order] = calloc(1UL << (order -1),
> sizeof(struct cds_lfht_node));
> assert(ht->t.tbl[order]);
> }
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> }
>
> /*
> @@ -778,9 +778,9 @@ void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> if (order == 0)
> poison_free(ht->t.tbl[0]);
> - else if (order > ht->min_alloc_order)
> + else if (order > ht->min_alloc_buckets_order)
> poison_free(ht->t.tbl[order]);
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_order */
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> }
>
> static inline
> @@ -789,7 +789,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> unsigned long order;
>
> if ((__builtin_constant_p(index) && index == 0)
> - || index < ht->min_alloc_size) {
> + || index < ht->min_nr_alloc_buckets) {
> dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> return &ht->t.tbl[0][index];
> }
> @@ -1364,7 +1364,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
> }
>
> struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> - unsigned long min_alloc_size,
> + unsigned long min_nr_alloc_buckets,
> int flags,
> void (*cds_lfht_call_rcu)(struct rcu_head *head,
> void (*func)(struct rcu_head *head)),
> @@ -1380,13 +1380,13 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> struct cds_lfht *ht;
> unsigned long order;
>
> - /* min_alloc_size must be power of two */
> - if (!min_alloc_size || (min_alloc_size & (min_alloc_size - 1)))
> + /* min_nr_alloc_buckets must be power of two */
> + if (!min_nr_alloc_buckets || (min_nr_alloc_buckets & (min_nr_alloc_buckets - 1)))
> return NULL;
> /* init_size must be power of two */
> if (!init_size || (init_size & (init_size - 1)))
> return NULL;
> - min_alloc_size = max(min_alloc_size, MIN_TABLE_SIZE);
> + min_nr_alloc_buckets = max(min_nr_alloc_buckets, MIN_TABLE_SIZE);
> init_size = max(init_size, MIN_TABLE_SIZE);
> ht = calloc(1, sizeof(struct cds_lfht));
> assert(ht);
> @@ -1405,8 +1405,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> pthread_mutex_init(&ht->resize_mutex, NULL);
> order = get_count_order_ulong(init_size);
> ht->t.resize_target = 1UL << order;
> - ht->min_alloc_size = min_alloc_size;
> - ht->min_alloc_order = get_count_order_ulong(min_alloc_size);
> + ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> + ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
> cds_lfht_create_bucket(ht, 1UL << order);
> ht->t.size = 1UL << order;
> return ht;
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index d3018b7..d242ff6 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -98,7 +98,7 @@ enum {
> * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
> */
> struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> - unsigned long min_alloc_size,
> + unsigned long min_nr_alloc_buckets,
> int flags,
> void (*cds_lfht_call_rcu)(struct rcu_head *head,
> void (*func)(struct rcu_head *head)),
> @@ -114,7 +114,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> /*
> * cds_lfht_new - allocate a hash table.
> * @init_size: number of nodes to allocate initially. Must be power of two.
> - * @min_alloc_size: the smallest allocation size to use. Must be power of two.
> + * @min_nr_alloc_buckets: the smallest allocation size to use. Must be power of two.
> * @flags: hash table creation flags (can be combined with bitwise or: '|').
> * 0: no flags.
> * CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
> @@ -137,11 +137,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> */
> static inline
> struct cds_lfht *cds_lfht_new(unsigned long init_size,
> - unsigned long min_alloc_size,
> + unsigned long min_nr_alloc_buckets,
> int flags,
> pthread_attr_t *attr)
> {
> - return _cds_lfht_new(init_size, min_alloc_size, flags,
> + return _cds_lfht_new(init_size, min_nr_alloc_buckets, flags,
> call_rcu, synchronize_rcu, rcu_read_lock,
> rcu_read_unlock, rcu_thread_offline,
> rcu_thread_online, rcu_register_thread,
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 07/12] Add rcu_flavor
2011-11-28 8:08 ` [lttng-dev] [PATCH 07/12] Add rcu_flavor Lai Jiangshan
@ 2011-11-28 13:23 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:23 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Not all related functions are added.
> Left functions will be added when needed.
merged, thanks!
Mathieu
>
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> ---
> Makefile.am | 2 +-
> urcu-bp.c | 2 +
> urcu-bp.h | 1 +
> urcu-flavor.h | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++
> urcu-qsbr.c | 2 +
> urcu-qsbr.h | 1 +
> urcu.c | 2 +
> urcu.h | 1 +
> urcu/map/urcu-bp.h | 2 +
> urcu/map/urcu-qsbr.h | 2 +
> urcu/map/urcu.h | 6 ++++
> 11 files changed, 85 insertions(+), 1 deletions(-)
> create mode 100644 urcu-flavor.h
>
> diff --git a/Makefile.am b/Makefile.am
> index 4e4ce89..1290551 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -8,7 +8,7 @@ AM_CFLAGS=-Wall
> SUBDIRS = . tests
>
> include_HEADERS = urcu.h urcu-bp.h urcu-call-rcu.h urcu-defer.h \
> - urcu-pointer.h urcu-qsbr.h
> + urcu-pointer.h urcu-qsbr.h urcu-flavor.h
> nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \
> urcu/rculist.h urcu/rcuhlist.h urcu/system.h urcu/futex.h \
> urcu/uatomic/generic.h urcu/arch/generic.h urcu/wfstack.h \
> diff --git a/urcu-bp.c b/urcu-bp.c
> index 4c0ab54..3b2062d 100644
> --- a/urcu-bp.c
> +++ b/urcu-bp.c
> @@ -421,5 +421,7 @@ void rcu_bp_after_fork_child(void)
> assert(!ret);
> }
>
> +DEFINE_RCU_FLAVOR()
> +
> #include "urcu-call-rcu-impl.h"
> #include "urcu-defer-impl.h"
> diff --git a/urcu-bp.h b/urcu-bp.h
> index 451bedb..efb5dca 100644
> --- a/urcu-bp.h
> +++ b/urcu-bp.h
> @@ -135,5 +135,6 @@ static inline void rcu_thread_online(void)
>
> #include <urcu-call-rcu.h>
> #include <urcu-defer.h>
> +#include <urcu-flavor.h>
>
> #endif /* _URCU_BP_H */
> diff --git a/urcu-flavor.h b/urcu-flavor.h
> new file mode 100644
> index 0000000..e46c9a1
> --- /dev/null
> +++ b/urcu-flavor.h
> @@ -0,0 +1,65 @@
> +#ifndef _URCU_FLAVOR_H
> +#define _URCU_FLAVOR_H
> +
> +/*
> + * urcu-flavor.h
> + *
> + * Userspace RCU header - rcu flavor declarations
> + *
> + * Copyright (c) 2011 Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +struct rcu_flavor_struct {
> + void (*read_lock)(void);
> + void (*read_unlock)(void);
> + void (*read_quiescent_state)(void);
> + void (*update_call_rcu)(struct rcu_head *head,
> + void (*func)(struct rcu_head *head));
> + void (*update_synchronize_rcu)(void);
> + void (*update_defer_rcu)(void (*fct)(void *p), void *p);
> +
> + void (*thread_offline)(void);
> + void (*thread_online)(void);
> + void (*register_thread)(void);
> + void (*unregister_thread)(void);
> +};
> +
> +#define DEFINE_RCU_FLAVOR() \
> +const struct rcu_flavor_struct rcu_flavor = { \
> + .read_lock = rcu_read_lock, \
> + .read_unlock = rcu_read_unlock, \
> + .read_quiescent_state = rcu_quiescent_state, \
> + .update_call_rcu = call_rcu, \
> + .update_synchronize_rcu = synchronize_rcu, \
> + .update_defer_rcu = defer_rcu, \
> + .thread_offline = rcu_thread_offline, \
> + .thread_online = rcu_thread_online, \
> + .register_thread = rcu_register_thread, \
> + .unregister_thread = rcu_unregister_thread,\
> +};
> +
> +extern const struct rcu_flavor_struct rcu_flavor;
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _URCU_FLAVOR_H */
> diff --git a/urcu-qsbr.c b/urcu-qsbr.c
> index 5530295..06e81c7 100644
> --- a/urcu-qsbr.c
> +++ b/urcu-qsbr.c
> @@ -356,5 +356,7 @@ void rcu_exit(void)
> */
> }
>
> +DEFINE_RCU_FLAVOR()
> +
> #include "urcu-call-rcu-impl.h"
> #include "urcu-defer-impl.h"
> diff --git a/urcu-qsbr.h b/urcu-qsbr.h
> index b362304..a2f6575 100644
> --- a/urcu-qsbr.h
> +++ b/urcu-qsbr.h
> @@ -127,5 +127,6 @@ extern void rcu_unregister_thread(void);
>
> #include <urcu-call-rcu.h>
> #include <urcu-defer.h>
> +#include <urcu-flavor.h>
>
> #endif /* _URCU_QSBR_H */
> diff --git a/urcu.c b/urcu.c
> index ba013d9..b434655 100644
> --- a/urcu.c
> +++ b/urcu.c
> @@ -452,5 +452,7 @@ void rcu_exit(void)
>
> #endif /* #ifdef RCU_SIGNAL */
>
> +DEFINE_RCU_FLAVOR()
> +
> #include "urcu-call-rcu-impl.h"
> #include "urcu-defer-impl.h"
> diff --git a/urcu.h b/urcu.h
> index 1ad971c..cd4fcbb 100644
> --- a/urcu.h
> +++ b/urcu.h
> @@ -128,5 +128,6 @@ static inline void rcu_thread_online(void)
>
> #include <urcu-call-rcu.h>
> #include <urcu-defer.h>
> +#include <urcu-flavor.h>
>
> #endif /* _URCU_H */
> diff --git a/urcu/map/urcu-bp.h b/urcu/map/urcu-bp.h
> index 4abe8dc..16601a1 100644
> --- a/urcu/map/urcu-bp.h
> +++ b/urcu/map/urcu-bp.h
> @@ -64,4 +64,6 @@
> #define rcu_defer_barrier rcu_defer_barrier_bp
> #define rcu_defer_barrier_thread rcu_defer_barrier_thread_bp
>
> +#define rcu_flavor rcu_flavor_bp
> +
> #endif /* _URCU_BP_MAP_H */
> diff --git a/urcu/map/urcu-qsbr.h b/urcu/map/urcu-qsbr.h
> index 0d88d83..a95441d 100644
> --- a/urcu/map/urcu-qsbr.h
> +++ b/urcu/map/urcu-qsbr.h
> @@ -66,4 +66,6 @@
> #define rcu_defer_barrier rcu_defer_barrier_qsbr
> #define rcu_defer_barrier_thread rcu_defer_barrier_thread_qsbr
>
> +#define rcu_flavor rcu_flavor_qsbr
> +
> #endif /* _URCU_QSBR_MAP_H */
> diff --git a/urcu/map/urcu.h b/urcu/map/urcu.h
> index 3f436a7..dd7a691 100644
> --- a/urcu/map/urcu.h
> +++ b/urcu/map/urcu.h
> @@ -95,6 +95,8 @@
> #define rcu_defer_barrier rcu_defer_barrier_memb
> #define rcu_defer_barrier_thread rcu_defer_barrier_thread_memb
>
> +#define rcu_flavor rcu_flavor_memb
> +
> #elif defined(RCU_SIGNAL)
>
> #define rcu_read_lock rcu_read_lock_sig
> @@ -127,6 +129,8 @@
> #define rcu_defer_barrier rcu_defer_barrier_sig
> #define rcu_defer_barrier_thread rcu_defer_barrier_thread_sig
>
> +#define rcu_flavor rcu_flavor_sig
> +
> #elif defined(RCU_MB)
>
> #define rcu_read_lock rcu_read_lock_mb
> @@ -159,6 +163,8 @@
> #define rcu_defer_barrier rcu_defer_barrier_mb
> #define rcu_defer_barrier_thread rcu_defer_barrier_thread_mb
>
> +#define rcu_flavor rcu_flavor_mb
> +
> #else
>
> #error "Undefined selection"
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 06/12] add max_nr_buckets argument
2011-11-28 8:08 ` [lttng-dev] [PATCH 06/12] add max_nr_buckets argument Lai Jiangshan
@ 2011-11-28 13:24 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:24 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Merged, thanks!
[ Edit by Mathieu Desnoyers: clarify cds_lfht_new() description. ]
Mathieu
> ---
> rculfhash.c | 17 +++++++++++++++++
> tests/test_urcu_hash.c | 2 +-
> urcu/rculfhash.h | 9 ++++++---
> 3 files changed, 24 insertions(+), 4 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 8282f09..4a611a1 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -267,6 +267,7 @@ struct cds_lfht {
> struct rcu_table t;
> unsigned long min_alloc_buckets_order;
> unsigned long min_nr_alloc_buckets;
> + unsigned long max_nr_buckets;
> int flags;
> /*
> * We need to put the work threads offline (QSBR) when taking this
> @@ -1365,6 +1366,7 @@ void cds_lfht_create_bucket(struct cds_lfht *ht, unsigned long size)
>
> struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets,
> int flags,
> void (*cds_lfht_call_rcu)(struct rcu_head *head,
> void (*func)(struct rcu_head *head)),
> @@ -1383,11 +1385,22 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> /* min_nr_alloc_buckets must be power of two */
> if (!min_nr_alloc_buckets || (min_nr_alloc_buckets & (min_nr_alloc_buckets - 1)))
> return NULL;
> +
> /* init_size must be power of two */
> if (!init_size || (init_size & (init_size - 1)))
> return NULL;
> +
> + if (!max_nr_buckets)
> + max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
> +
> + /* max_nr_buckets must be power of two */
> + if (!max_nr_buckets || (max_nr_buckets & (max_nr_buckets - 1)))
> + return NULL;
> +
> min_nr_alloc_buckets = max(min_nr_alloc_buckets, MIN_TABLE_SIZE);
> init_size = max(init_size, MIN_TABLE_SIZE);
> + max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
> + init_size = min(init_size, max_nr_buckets);
> ht = calloc(1, sizeof(struct cds_lfht));
> assert(ht);
> ht->flags = flags;
> @@ -1407,6 +1420,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> ht->t.resize_target = 1UL << order;
> ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
> + ht->max_nr_buckets = max_nr_buckets;
> cds_lfht_create_bucket(ht, 1UL << order);
> ht->t.size = 1UL << order;
> return ht;
> @@ -1766,6 +1780,7 @@ void resize_target_update_count(struct cds_lfht *ht,
> unsigned long count)
> {
> count = max(count, MIN_TABLE_SIZE);
> + count = min(count, ht->max_nr_buckets);
> uatomic_set(&ht->t.resize_target, count);
> }
>
> @@ -1823,6 +1838,7 @@ void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int grow
> {
> unsigned long target_size = size << growth;
>
> + target_size = min(target_size, ht->max_nr_buckets);
> if (resize_target_grow(ht, target_size) >= target_size)
> return;
>
> @@ -1841,6 +1857,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
> if (!(ht->flags & CDS_LFHT_AUTO_RESIZE))
> return;
> count = max(count, MIN_TABLE_SIZE);
> + count = min(count, ht->max_nr_buckets);
> if (count == size)
> return; /* Already the right size, no resize needed */
> if (count > size) { /* lazy grow */
> diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c
> index 01ae01a..043a33a 100644
> --- a/tests/test_urcu_hash.c
> +++ b/tests/test_urcu_hash.c
> @@ -967,7 +967,7 @@ int main(int argc, char **argv)
> * thread from the point of view of resize.
> */
> rcu_register_thread();
> - test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size,
> + test_ht = cds_lfht_new(init_hash_size, min_hash_alloc_size, (1UL << 18),
> (opt_auto_resize ? CDS_LFHT_AUTO_RESIZE : 0) |
> CDS_LFHT_ACCOUNTING, NULL);
> ret = populate_hash();
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index d242ff6..bff883f 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -99,6 +99,7 @@ enum {
> */
> struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets,
> int flags,
> void (*cds_lfht_call_rcu)(struct rcu_head *head,
> void (*func)(struct rcu_head *head)),
> @@ -113,8 +114,9 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
>
> /*
> * cds_lfht_new - allocate a hash table.
> - * @init_size: number of nodes to allocate initially. Must be power of two.
> - * @min_nr_alloc_buckets: the smallest allocation size to use. Must be power of two.
> + * @init_size: number of buckets to allocate initially. Must be power of two.
> + * @min_nr_alloc_buckets: the smallest allocation buckets size to use. Must be power of two.
> + * @max_nr_buckets: the max size of buckets for future growing. Must be power of two.
> * @flags: hash table creation flags (can be combined with bitwise or: '|').
> * 0: no flags.
> * CDS_LFHT_AUTO_RESIZE: automatically resize hash table.
> @@ -138,10 +140,11 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> static inline
> struct cds_lfht *cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets,
> int flags,
> pthread_attr_t *attr)
> {
> - return _cds_lfht_new(init_size, min_nr_alloc_buckets, flags,
> + return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags,
> call_rcu, synchronize_rcu, rcu_read_lock,
> rcu_read_unlock, rcu_thread_offline,
> rcu_thread_online, rcu_register_thread,
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash
2011-11-28 8:08 ` [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash Lai Jiangshan
@ 2011-11-28 13:24 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:24 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Make the sizeof(struct cds_lfht) smaller
>
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Merged, thanks!
Mathieu
> ---
> rculfhash.c | 64 +++++++++++++++++------------------------------------
> urcu/rculfhash.h | 18 +++-----------
> 2 files changed, 25 insertions(+), 57 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 4a611a1..18cead3 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -160,6 +160,7 @@
> #include "config.h"
> #include <urcu.h>
> #include <urcu-call-rcu.h>
> +#include <urcu-flavor.h>
> #include <urcu/arch.h>
> #include <urcu/uatomic.h>
> #include <urcu/compiler.h>
> @@ -278,15 +279,7 @@ struct cds_lfht {
> */
> pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> unsigned int in_progress_resize, in_progress_destroy;
> - void (*cds_lfht_call_rcu)(struct rcu_head *head,
> - void (*func)(struct rcu_head *head));
> - void (*cds_lfht_synchronize_rcu)(void);
> - void (*cds_lfht_rcu_read_lock)(void);
> - void (*cds_lfht_rcu_read_unlock)(void);
> - void (*cds_lfht_rcu_thread_offline)(void);
> - void (*cds_lfht_rcu_thread_online)(void);
> - void (*cds_lfht_rcu_register_thread)(void);
> - void (*cds_lfht_rcu_unregister_thread)(void);
> + const struct rcu_flavor_struct *flavor;
> pthread_attr_t *resize_attr; /* Resize threads attributes */
> long count; /* global approximate item count */
> struct ht_items_count *split_count; /* split item count */
> @@ -1075,9 +1068,9 @@ void *partition_resize_thread(void *arg)
> {
> struct partition_resize_work *work = arg;
>
> - work->ht->cds_lfht_rcu_register_thread();
> + work->ht->flavor->register_thread();
> work->fct(work->ht, work->i, work->start, work->len);
> - work->ht->cds_lfht_rcu_unregister_thread();
> + work->ht->flavor->unregister_thread();
> return NULL;
> }
>
> @@ -1141,7 +1134,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> unsigned long j, size = 1UL << (i - 1);
>
> assert(i > MIN_TABLE_ORDER);
> - ht->cds_lfht_rcu_read_lock();
> + ht->flavor->read_lock();
> for (j = size + start; j < size + start + len; j++) {
> struct cds_lfht_node *new_node = bucket_at(ht, j);
>
> @@ -1151,7 +1144,7 @@ void init_table_populate_partition(struct cds_lfht *ht, unsigned long i,
> new_node->reverse_hash = bit_reverse_ulong(j);
> _cds_lfht_add(ht, NULL, NULL, size, new_node, NULL, 1);
> }
> - ht->cds_lfht_rcu_read_unlock();
> + ht->flavor->read_unlock();
> }
>
> static
> @@ -1160,9 +1153,9 @@ void init_table_populate(struct cds_lfht *ht, unsigned long i,
> {
> assert(nr_cpus_mask != -1);
> if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD) {
> - ht->cds_lfht_rcu_thread_online();
> + ht->flavor->thread_online();
> init_table_populate_partition(ht, i, 0, len);
> - ht->cds_lfht_rcu_thread_offline();
> + ht->flavor->thread_offline();
> return;
> }
> partition_resize_helper(ht, i, len, init_table_populate_partition);
> @@ -1239,7 +1232,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
> unsigned long j, size = 1UL << (i - 1);
>
> assert(i > MIN_TABLE_ORDER);
> - ht->cds_lfht_rcu_read_lock();
> + ht->flavor->read_lock();
> for (j = size + start; j < size + start + len; j++) {
> struct cds_lfht_node *fini_node = bucket_at(ht, j);
>
> @@ -1249,7 +1242,7 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i,
> fini_node->reverse_hash = bit_reverse_ulong(j);
> (void) _cds_lfht_del(ht, size, fini_node, 1);
> }
> - ht->cds_lfht_rcu_read_unlock();
> + ht->flavor->read_unlock();
> }
>
> static
> @@ -1258,9 +1251,9 @@ void remove_table(struct cds_lfht *ht, unsigned long i, unsigned long len)
>
> assert(nr_cpus_mask != -1);
> if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD) {
> - ht->cds_lfht_rcu_thread_online();
> + ht->flavor->thread_online();
> remove_table_partition(ht, i, 0, len);
> - ht->cds_lfht_rcu_thread_offline();
> + ht->flavor->thread_offline();
> return;
> }
> partition_resize_helper(ht, i, len, remove_table_partition);
> @@ -1295,7 +1288,7 @@ void fini_table(struct cds_lfht *ht,
> * releasing the old bucket nodes. Otherwise their lookup will
> * return a logically removed node as insert position.
> */
> - ht->cds_lfht_synchronize_rcu();
> + ht->flavor->update_synchronize_rcu();
> if (free_by_rcu_order)
> cds_lfht_free_bucket_table(ht, free_by_rcu_order);
>
> @@ -1315,7 +1308,7 @@ void fini_table(struct cds_lfht *ht,
> }
>
> if (free_by_rcu_order) {
> - ht->cds_lfht_synchronize_rcu();
> + ht->flavor->update_synchronize_rcu();
> cds_lfht_free_bucket_table(ht, free_by_rcu_order);
> }
> }
> @@ -1368,15 +1361,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> unsigned long max_nr_buckets,
> int flags,
> - void (*cds_lfht_call_rcu)(struct rcu_head *head,
> - void (*func)(struct rcu_head *head)),
> - void (*cds_lfht_synchronize_rcu)(void),
> - void (*cds_lfht_rcu_read_lock)(void),
> - void (*cds_lfht_rcu_read_unlock)(void),
> - void (*cds_lfht_rcu_thread_offline)(void),
> - void (*cds_lfht_rcu_thread_online)(void),
> - void (*cds_lfht_rcu_register_thread)(void),
> - void (*cds_lfht_rcu_unregister_thread)(void),
> + const struct rcu_flavor_struct *flavor,
> pthread_attr_t *attr)
> {
> struct cds_lfht *ht;
> @@ -1404,14 +1389,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> ht = calloc(1, sizeof(struct cds_lfht));
> assert(ht);
> ht->flags = flags;
> - ht->cds_lfht_call_rcu = cds_lfht_call_rcu;
> - ht->cds_lfht_synchronize_rcu = cds_lfht_synchronize_rcu;
> - ht->cds_lfht_rcu_read_lock = cds_lfht_rcu_read_lock;
> - ht->cds_lfht_rcu_read_unlock = cds_lfht_rcu_read_unlock;
> - ht->cds_lfht_rcu_thread_offline = cds_lfht_rcu_thread_offline;
> - ht->cds_lfht_rcu_thread_online = cds_lfht_rcu_thread_online;
> - ht->cds_lfht_rcu_register_thread = cds_lfht_rcu_register_thread;
> - ht->cds_lfht_rcu_unregister_thread = cds_lfht_rcu_unregister_thread;
> + ht->flavor = flavor;
> ht->resize_attr = attr;
> alloc_split_items_count(ht);
> /* this mutex should not nest in read-side C.S. */
> @@ -1788,11 +1766,11 @@ void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
> {
> resize_target_update_count(ht, new_size);
> CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> - ht->cds_lfht_rcu_thread_offline();
> + ht->flavor->thread_offline();
> pthread_mutex_lock(&ht->resize_mutex);
> _do_cds_lfht_resize(ht);
> pthread_mutex_unlock(&ht->resize_mutex);
> - ht->cds_lfht_rcu_thread_online();
> + ht->flavor->thread_online();
> }
>
> static
> @@ -1802,11 +1780,11 @@ void do_resize_cb(struct rcu_head *head)
> caa_container_of(head, struct rcu_resize_work, head);
> struct cds_lfht *ht = work->ht;
>
> - ht->cds_lfht_rcu_thread_offline();
> + ht->flavor->thread_offline();
> pthread_mutex_lock(&ht->resize_mutex);
> _do_cds_lfht_resize(ht);
> pthread_mutex_unlock(&ht->resize_mutex);
> - ht->cds_lfht_rcu_thread_online();
> + ht->flavor->thread_online();
> poison_free(work);
> cmm_smp_mb(); /* finish resize before decrement */
> uatomic_dec(&ht->in_progress_resize);
> @@ -1828,7 +1806,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
> }
> work = malloc(sizeof(*work));
> work->ht = ht;
> - ht->cds_lfht_call_rcu(&work->head, do_resize_cb);
> + ht->flavor->update_call_rcu(&work->head, do_resize_cb);
> CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> }
> }
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index bff883f..a886b04 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -29,6 +29,7 @@
> #include <stdint.h>
> #include <urcu/compiler.h>
> #include <urcu-call-rcu.h>
> +#include <urcu-flavor.h>
>
> #ifdef __cplusplus
> extern "C" {
> @@ -101,15 +102,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> unsigned long max_nr_buckets,
> int flags,
> - void (*cds_lfht_call_rcu)(struct rcu_head *head,
> - void (*func)(struct rcu_head *head)),
> - void (*cds_lfht_synchronize_rcu)(void),
> - void (*cds_lfht_rcu_read_lock)(void),
> - void (*cds_lfht_rcu_read_unlock)(void),
> - void (*cds_lfht_rcu_thread_offline)(void),
> - void (*cds_lfht_rcu_thread_online)(void),
> - void (*cds_lfht_rcu_register_thread)(void),
> - void (*cds_lfht_rcu_unregister_thread)(void),
> + const struct rcu_flavor_struct *flavor,
> pthread_attr_t *attr);
>
> /*
> @@ -144,11 +137,8 @@ struct cds_lfht *cds_lfht_new(unsigned long init_size,
> int flags,
> pthread_attr_t *attr)
> {
> - return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets, flags,
> - call_rcu, synchronize_rcu, rcu_read_lock,
> - rcu_read_unlock, rcu_thread_offline,
> - rcu_thread_online, rcu_register_thread,
> - rcu_unregister_thread, attr);
> + return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
> + flags, &rcu_flavor, attr);
> }
>
> /*
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 09/12] remove struct rcu_table
2011-11-28 8:08 ` [lttng-dev] [PATCH 09/12] remove struct rcu_table Lai Jiangshan
@ 2011-11-28 13:25 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:25 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Merged as:
"Merge struct rcu_table into struct cds_lfht"
Thanks!
Mathieu
> ---
> rculfhash.c | 107 +++++++++++++++++++++++++++-------------------------------
> 1 files changed, 50 insertions(+), 57 deletions(-)
>
> diff --git a/rculfhash.c b/rculfhash.c
> index 18cead3..8dc9c59 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -240,36 +240,14 @@ struct ht_items_count {
> } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>
> /*
> - * rcu_table: Contains the size and desired new size if a resize
> - * operation is in progress, as well as the statically-sized array of
> - * bucket table pointers.
> - */
> -struct rcu_table {
> - unsigned long size; /* always a power of 2, shared (RCU) */
> - unsigned long resize_target;
> - int resize_initiated;
> -
> - /*
> - * Contains the per order-index-level bucket node table. The size
> - * of each bucket node table is half the number of hashes contained
> - * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the bucket node arrays of the lowermost
> - * levels to improve cache locality for small index orders.
> - */
> - struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> -};
> -
> -/*
> * cds_lfht: Top-level data structure representing a lock-free hash
> * table. Defined in the implementation file to make it be an opaque
> * cookie to users.
> */
> struct cds_lfht {
> - struct rcu_table t;
> - unsigned long min_alloc_buckets_order;
> - unsigned long min_nr_alloc_buckets;
> - unsigned long max_nr_buckets;
> + unsigned long size; /* always a power of 2, shared (RCU) */
> int flags;
> +
> /*
> * We need to put the work threads offline (QSBR) when taking this
> * mutex, because we use synchronize_rcu within this mutex critical
> @@ -278,11 +256,26 @@ struct cds_lfht {
> * completion.
> */
> pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> + pthread_attr_t *resize_attr; /* Resize threads attributes */
> unsigned int in_progress_resize, in_progress_destroy;
> + unsigned long resize_target;
> + int resize_initiated;
> const struct rcu_flavor_struct *flavor;
> - pthread_attr_t *resize_attr; /* Resize threads attributes */
> +
> long count; /* global approximate item count */
> struct ht_items_count *split_count; /* split item count */
> +
> + unsigned long min_alloc_buckets_order;
> + unsigned long min_nr_alloc_buckets;
> + unsigned long max_nr_buckets;
> + /*
> + * Contains the per order-index-level bucket node table. The size
> + * of each bucket node table is half the number of hashes contained
> + * in this order (except for order 0). The minimum allocation size
> + * parameter allows combining the bucket node arrays of the lowermost
> + * levels to improve cache locality for small index orders.
> + */
> + struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> };
>
> /*
> @@ -751,13 +744,13 @@ static
> void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> if (order == 0) {
> - ht->t.tbl[0] = calloc(ht->min_nr_alloc_buckets,
> + ht->tbl[0] = calloc(ht->min_nr_alloc_buckets,
> sizeof(struct cds_lfht_node));
> - assert(ht->t.tbl[0]);
> + assert(ht->tbl[0]);
> } else if (order > ht->min_alloc_buckets_order) {
> - ht->t.tbl[order] = calloc(1UL << (order -1),
> + ht->tbl[order] = calloc(1UL << (order -1),
> sizeof(struct cds_lfht_node));
> - assert(ht->t.tbl[order]);
> + assert(ht->tbl[order]);
> }
> /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> }
> @@ -771,9 +764,9 @@ static
> void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> if (order == 0)
> - poison_free(ht->t.tbl[0]);
> + poison_free(ht->tbl[0]);
> else if (order > ht->min_alloc_buckets_order)
> - poison_free(ht->t.tbl[order]);
> + poison_free(ht->tbl[order]);
> /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> }
>
> @@ -785,7 +778,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> if ((__builtin_constant_p(index) && index == 0)
> || index < ht->min_nr_alloc_buckets) {
> dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> - return &ht->t.tbl[0][index];
> + return &ht->tbl[0][index];
> }
> /*
> * equivalent to get_count_order_ulong(index + 1), but optimizes
> @@ -795,7 +788,7 @@ struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> order = fls_ulong(index);
> dbg_printf("bucket index %lu order %lu aridx %lu\n",
> index, order, index & ((1UL << (order - 1)) - 1));
> - return &ht->t.tbl[order][index & ((1UL << (order - 1)) - 1)];
> + return &ht->tbl[order][index & ((1UL << (order - 1)) - 1)];
> }
>
> static inline
> @@ -1177,7 +1170,7 @@ void init_table(struct cds_lfht *ht,
> dbg_printf("init order %lu len: %lu\n", i, len);
>
> /* Stop expand if the resize target changes under us */
> - if (CMM_LOAD_SHARED(ht->t.resize_target) < (1UL << i))
> + if (CMM_LOAD_SHARED(ht->resize_target) < (1UL << i))
> break;
>
> cds_lfht_alloc_bucket_table(ht, i);
> @@ -1192,7 +1185,7 @@ void init_table(struct cds_lfht *ht,
> * Update table size.
> */
> cmm_smp_wmb(); /* populate data before RCU size */
> - CMM_STORE_SHARED(ht->t.size, 1UL << i);
> + CMM_STORE_SHARED(ht->size, 1UL << i);
>
> dbg_printf("init new size: %lu\n", 1UL << i);
> if (CMM_LOAD_SHARED(ht->in_progress_destroy))
> @@ -1276,11 +1269,11 @@ void fini_table(struct cds_lfht *ht,
> dbg_printf("fini order %lu len: %lu\n", i, len);
>
> /* Stop shrink if the resize target changes under us */
> - if (CMM_LOAD_SHARED(ht->t.resize_target) > (1UL << (i - 1)))
> + if (CMM_LOAD_SHARED(ht->resize_target) > (1UL << (i - 1)))
> break;
>
> cmm_smp_wmb(); /* populate data before RCU size */
> - CMM_STORE_SHARED(ht->t.size, 1UL << (i - 1));
> + CMM_STORE_SHARED(ht->size, 1UL << (i - 1));
>
> /*
> * We need to wait for all add operations to reach Q.S. (and
> @@ -1395,12 +1388,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> /* this mutex should not nest in read-side C.S. */
> pthread_mutex_init(&ht->resize_mutex, NULL);
> order = get_count_order_ulong(init_size);
> - ht->t.resize_target = 1UL << order;
> + ht->resize_target = 1UL << order;
> ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
> ht->max_nr_buckets = max_nr_buckets;
> cds_lfht_create_bucket(ht, 1UL << order);
> - ht->t.size = 1UL << order;
> + ht->size = 1UL << order;
> return ht;
> }
>
> @@ -1413,7 +1406,7 @@ void cds_lfht_lookup(struct cds_lfht *ht, unsigned long hash,
>
> reverse_hash = bit_reverse_ulong(hash);
>
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> bucket = lookup_bucket(ht, size, hash);
> /* We can always skip the bucket node initially */
> node = rcu_dereference(bucket->next);
> @@ -1513,7 +1506,7 @@ void cds_lfht_add(struct cds_lfht *ht, unsigned long hash,
> unsigned long size;
>
> node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> _cds_lfht_add(ht, NULL, NULL, size, node, NULL, 0);
> ht_count_add(ht, size, hash);
> }
> @@ -1528,7 +1521,7 @@ struct cds_lfht_node *cds_lfht_add_unique(struct cds_lfht *ht,
> struct cds_lfht_iter iter;
>
> node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> _cds_lfht_add(ht, match, key, size, node, &iter, 0);
> if (iter.node == node)
> ht_count_add(ht, size, hash);
> @@ -1545,7 +1538,7 @@ struct cds_lfht_node *cds_lfht_add_replace(struct cds_lfht *ht,
> struct cds_lfht_iter iter;
>
> node->reverse_hash = bit_reverse_ulong((unsigned long) hash);
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> for (;;) {
> _cds_lfht_add(ht, match, key, size, node, &iter, 0);
> if (iter.node == node) {
> @@ -1563,7 +1556,7 @@ int cds_lfht_replace(struct cds_lfht *ht, struct cds_lfht_iter *old_iter,
> {
> unsigned long size;
>
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> return _cds_lfht_replace(ht, size, old_iter->node, old_iter->next,
> new_node);
> }
> @@ -1573,7 +1566,7 @@ int cds_lfht_del(struct cds_lfht *ht, struct cds_lfht_iter *iter)
> unsigned long size, hash;
> int ret;
>
> - size = rcu_dereference(ht->t.size);
> + size = rcu_dereference(ht->size);
> ret = _cds_lfht_del(ht, size, iter->node, 0);
> if (!ret) {
> hash = bit_reverse_ulong(iter->node->reverse_hash);
> @@ -1600,7 +1593,7 @@ int cds_lfht_delete_bucket(struct cds_lfht *ht)
> * size accessed without rcu_dereference because hash table is
> * being destroyed.
> */
> - size = ht->t.size;
> + size = ht->size;
> /* Internal sanity check: all nodes left should be bucket */
> for (i = 0; i < size; i++) {
> node = bucket_at(ht, i);
> @@ -1734,23 +1727,23 @@ void _do_cds_lfht_resize(struct cds_lfht *ht)
> assert(uatomic_read(&ht->in_progress_resize));
> if (CMM_LOAD_SHARED(ht->in_progress_destroy))
> break;
> - ht->t.resize_initiated = 1;
> - old_size = ht->t.size;
> - new_size = CMM_LOAD_SHARED(ht->t.resize_target);
> + ht->resize_initiated = 1;
> + old_size = ht->size;
> + new_size = CMM_LOAD_SHARED(ht->resize_target);
> if (old_size < new_size)
> _do_cds_lfht_grow(ht, old_size, new_size);
> else if (old_size > new_size)
> _do_cds_lfht_shrink(ht, old_size, new_size);
> - ht->t.resize_initiated = 0;
> + ht->resize_initiated = 0;
> /* write resize_initiated before read resize_target */
> cmm_smp_mb();
> - } while (ht->t.size != CMM_LOAD_SHARED(ht->t.resize_target));
> + } while (ht->size != CMM_LOAD_SHARED(ht->resize_target));
> }
>
> static
> unsigned long resize_target_grow(struct cds_lfht *ht, unsigned long new_size)
> {
> - return _uatomic_xchg_monotonic_increase(&ht->t.resize_target, new_size);
> + return _uatomic_xchg_monotonic_increase(&ht->resize_target, new_size);
> }
>
> static
> @@ -1759,13 +1752,13 @@ void resize_target_update_count(struct cds_lfht *ht,
> {
> count = max(count, MIN_TABLE_SIZE);
> count = min(count, ht->max_nr_buckets);
> - uatomic_set(&ht->t.resize_target, count);
> + uatomic_set(&ht->resize_target, count);
> }
>
> void cds_lfht_resize(struct cds_lfht *ht, unsigned long new_size)
> {
> resize_target_update_count(ht, new_size);
> - CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> + CMM_STORE_SHARED(ht->resize_initiated, 1);
> ht->flavor->thread_offline();
> pthread_mutex_lock(&ht->resize_mutex);
> _do_cds_lfht_resize(ht);
> @@ -1797,7 +1790,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
>
> /* Store resize_target before read resize_initiated */
> cmm_smp_mb();
> - if (!CMM_LOAD_SHARED(ht->t.resize_initiated)) {
> + if (!CMM_LOAD_SHARED(ht->resize_initiated)) {
> uatomic_inc(&ht->in_progress_resize);
> cmm_smp_mb(); /* increment resize count before load destroy */
> if (CMM_LOAD_SHARED(ht->in_progress_destroy)) {
> @@ -1807,7 +1800,7 @@ void __cds_lfht_resize_lazy_launch(struct cds_lfht *ht)
> work = malloc(sizeof(*work));
> work->ht = ht;
> ht->flavor->update_call_rcu(&work->head, do_resize_cb);
> - CMM_STORE_SHARED(ht->t.resize_initiated, 1);
> + CMM_STORE_SHARED(ht->resize_initiated, 1);
> }
> }
>
> @@ -1845,7 +1838,7 @@ void cds_lfht_resize_lazy_count(struct cds_lfht *ht, unsigned long size,
> for (;;) {
> unsigned long s;
>
> - s = uatomic_cmpxchg(&ht->t.resize_target, size, count);
> + s = uatomic_cmpxchg(&ht->resize_target, size, count);
> if (s == size)
> break; /* no resize needed */
> if (s > size)
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c
2011-11-28 8:08 ` [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c Lai Jiangshan
@ 2011-11-28 13:27 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:27 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Yep, this is clean! :)
Merged, thanks!
Mathieu
> ---
> Makefile.am | 5 ++-
> rculfhash-internal.h | 115 ++++++++++++++++++++++++++++++++++++++++++++++++
> rculfhash-mm-order.c | 101 ++++++++++++++++++++++++++++++++++++++++++
> rculfhash.c | 119 +++++---------------------------------------------
> urcu/rculfhash.h | 14 +++++-
> 5 files changed, 245 insertions(+), 109 deletions(-)
> create mode 100644 rculfhash-internal.h
> create mode 100644 rculfhash-mm-order.c
>
> diff --git a/Makefile.am b/Makefile.am
> index 1290551..4d3f7bd 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -22,6 +22,7 @@ EXTRA_DIST = $(top_srcdir)/urcu/arch/*.h $(top_srcdir)/urcu/uatomic/*.h \
> gpl-2.0.txt lgpl-2.1.txt lgpl-relicensing.txt \
> README LICENSE compat_arch_x86.c \
> urcu-call-rcu-impl.h urcu-defer-impl.h \
> + rculfhash-internal.h \
> ChangeLog API.txt
>
> if COMPAT_ARCH
> @@ -34,6 +35,8 @@ if COMPAT_FUTEX
> COMPAT+=compat_futex.c
> endif
>
> +RCULFHASH=rculfhash.c rculfhash-mm-order.c
> +
> lib_LTLIBRARIES = liburcu-common.la \
> liburcu.la liburcu-qsbr.la \
> liburcu-mb.la liburcu-signal.la liburcu-bp.la \
> @@ -62,7 +65,7 @@ liburcu_signal_la_LIBADD = liburcu-common.la
> liburcu_bp_la_SOURCES = urcu-bp.c urcu-pointer.c $(COMPAT)
> liburcu_bp_la_LIBADD = liburcu-common.la
>
> -liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c rculfhash.c $(COMPAT)
> +liburcu_cds_la_SOURCES = rculfqueue.c rculfstack.c $(RCULFHASH) $(COMPAT)
> liburcu_cds_la_LIBADD = liburcu-common.la
>
> pkgconfigdir = $(libdir)/pkgconfig
> diff --git a/rculfhash-internal.h b/rculfhash-internal.h
> new file mode 100644
> index 0000000..820e62c
> --- /dev/null
> +++ b/rculfhash-internal.h
> @@ -0,0 +1,115 @@
> +#ifndef _URCU_RCULFHASH_INTERNAL_H
> +#define _URCU_RCULFHASH_INTERNAL_H
> +
> +/*
> + * urcu/rculfhash-internal.h
> + *
> + * Internal header for Lock-Free RCU Hash Table
> + *
> + * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <urcu/rculfhash.h>
> +
> +#ifdef DEBUG
> +#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
> +#else
> +#define dbg_printf(fmt, args...)
> +#endif
> +
> +#if (CAA_BITS_PER_LONG == 32)
> +#define MAX_TABLE_ORDER 32
> +#else
> +#define MAX_TABLE_ORDER 64
> +#endif
> +
> +#ifndef min
> +#define min(a, b) ((a) < (b) ? (a) : (b))
> +#endif
> +
> +#ifndef max
> +#define max(a, b) ((a) > (b) ? (a) : (b))
> +#endif
> +
> +struct ht_items_count;
> +
> +/*
> + * cds_lfht: Top-level data structure representing a lock-free hash
> + * table. Defined in the implementation file to make it be an opaque
> + * cookie to users.
> + */
> +struct cds_lfht {
> + unsigned long size; /* always a power of 2, shared (RCU) */
> + int flags;
> +
> + /*
> + * We need to put the work threads offline (QSBR) when taking this
> + * mutex, because we use synchronize_rcu within this mutex critical
> + * section, which waits on read-side critical sections, and could
> + * therefore cause grace-period deadlock if we hold off RCU G.P.
> + * completion.
> + */
> + pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> + pthread_attr_t *resize_attr; /* Resize threads attributes */
> + unsigned int in_progress_resize, in_progress_destroy;
> + unsigned long resize_target;
> + int resize_initiated;
> + const struct rcu_flavor_struct *flavor;
> +
> + long count; /* global approximate item count */
> + struct ht_items_count *split_count; /* split item count */
> +
> + /* memory management related fields are located at the end */
> + const struct cds_lfht_mm_type *mm;
> +
> + unsigned long min_alloc_buckets_order;
> + unsigned long min_nr_alloc_buckets;
> + unsigned long max_nr_buckets;
> +
> + struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
> + unsigned long index);
> +
> + union {
> + /*
> + * Contains the per order-index-level bucket node table.
> + * The size of each bucket node table is half the number
> + * of hashes contained in this order (except for order 0).
> + * The minimum allocation buckets size parameter allows
> + * combining the bucket node arrays of the lowermost
> + * levels to improve cache locality for small index orders.
> + */
> + struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
> + };
> +};
> +
> +extern unsigned int fls_ulong(unsigned long x);
> +extern int get_count_order_ulong(unsigned long x);
> +
> +#ifdef POISON_FREE
> +#define poison_free(ptr) \
> + do { \
> + if (ptr) { \
> + memset(ptr, 0x42, sizeof(*(ptr))); \
> + free(ptr); \
> + } \
> + } while (0)
> +#else
> +#define poison_free(ptr) free(ptr)
> +#endif
> +
> +#endif /* _URCU_RCULFHASH_INTERNAL_H */
> diff --git a/rculfhash-mm-order.c b/rculfhash-mm-order.c
> new file mode 100644
> index 0000000..69e2b62
> --- /dev/null
> +++ b/rculfhash-mm-order.c
> @@ -0,0 +1,101 @@
> +/*
> + * rculfhash-mm-order.c
> + *
> + * Order based memory management for Lock-Free RCU Hash Table
> + *
> + * Copyright 2011 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <rculfhash-internal.h>
> +
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0) {
> + ht->tbl_order[0] = calloc(ht->min_nr_alloc_buckets,
> + sizeof(struct cds_lfht_node));
> + assert(ht->tbl_order[0]);
> + } else if (order > ht->min_alloc_buckets_order) {
> + ht->tbl_order[order] = calloc(1UL << (order -1),
> + sizeof(struct cds_lfht_node));
> + assert(ht->tbl_order[order]);
> + }
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0)
> + poison_free(ht->tbl_order[0]);
> + else if (order > ht->min_alloc_buckets_order)
> + poison_free(ht->tbl_order[order]);
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> +}
> +
> +static
> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> +{
> + unsigned long order;
> +
> + if (index < ht->min_nr_alloc_buckets) {
> + dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> + return &ht->tbl_order[0][index];
> + }
> + /*
> + * equivalent to get_count_order_ulong(index + 1), but optimizes
> + * away the non-existing 0 special-case for
> + * get_count_order_ulong.
> + */
> + order = fls_ulong(index);
> + dbg_printf("bucket index %lu order %lu aridx %lu\n",
> + index, order, index & ((1UL << (order - 1)) - 1));
> + return &ht->tbl_order[order][index & ((1UL << (order - 1)) - 1)];
> +}
> +
> +static
> +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets)
> +{
> + struct cds_lfht *ht;
> +
> + ht = calloc(1, sizeof(struct cds_lfht));
> + assert(ht);
> +
> + ht->mm = &cds_lfht_mm_order;
> +
> + ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> + ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
> + ht->max_nr_buckets = max_nr_buckets;
> +
> + ht->bucket_at = bucket_at;
> +
> + return ht;
> +}
> +
> +const struct cds_lfht_mm_type cds_lfht_mm_order = {
> + .alloc_cds_lfht = alloc_cds_lfht,
> + .alloc_bucket_table = cds_lfht_alloc_bucket_table,
> + .free_bucket_table = cds_lfht_free_bucket_table,
> + .bucket_at = bucket_at,
> +};
> diff --git a/rculfhash.c b/rculfhash.c
> index 8dc9c59..49c7863 100644
> --- a/rculfhash.c
> +++ b/rculfhash.c
> @@ -165,15 +165,10 @@
> #include <urcu/uatomic.h>
> #include <urcu/compiler.h>
> #include <urcu/rculfhash.h>
> +#include <rculfhash-internal.h>
> #include <stdio.h>
> #include <pthread.h>
>
> -#ifdef DEBUG
> -#define dbg_printf(fmt, args...) printf("[debug rculfhash] " fmt, ## args)
> -#else
> -#define dbg_printf(fmt, args...)
> -#endif
> -
> /*
> * Split-counters lazily update the global counter each 1024
> * addition/removal. It automatically keeps track of resize required.
> @@ -191,26 +186,12 @@
> #define MIN_TABLE_ORDER 0
> #define MIN_TABLE_SIZE (1UL << MIN_TABLE_ORDER)
>
> -#if (CAA_BITS_PER_LONG == 32)
> -#define MAX_TABLE_ORDER 32
> -#else
> -#define MAX_TABLE_ORDER 64
> -#endif
> -
> /*
> * Minimum number of bucket nodes to touch per thread to parallelize grow/shrink.
> */
> #define MIN_PARTITION_PER_THREAD_ORDER 12
> #define MIN_PARTITION_PER_THREAD (1UL << MIN_PARTITION_PER_THREAD_ORDER)
>
> -#ifndef min
> -#define min(a, b) ((a) < (b) ? (a) : (b))
> -#endif
> -
> -#ifndef max
> -#define max(a, b) ((a) > (b) ? (a) : (b))
> -#endif
> -
> /*
> * The removed flag needs to be updated atomically with the pointer.
> * It indicates that no node must attach to the node scheduled for
> @@ -240,45 +221,6 @@ struct ht_items_count {
> } __attribute__((aligned(CAA_CACHE_LINE_SIZE)));
>
> /*
> - * cds_lfht: Top-level data structure representing a lock-free hash
> - * table. Defined in the implementation file to make it be an opaque
> - * cookie to users.
> - */
> -struct cds_lfht {
> - unsigned long size; /* always a power of 2, shared (RCU) */
> - int flags;
> -
> - /*
> - * We need to put the work threads offline (QSBR) when taking this
> - * mutex, because we use synchronize_rcu within this mutex critical
> - * section, which waits on read-side critical sections, and could
> - * therefore cause grace-period deadlock if we hold off RCU G.P.
> - * completion.
> - */
> - pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
> - pthread_attr_t *resize_attr; /* Resize threads attributes */
> - unsigned int in_progress_resize, in_progress_destroy;
> - unsigned long resize_target;
> - int resize_initiated;
> - const struct rcu_flavor_struct *flavor;
> -
> - long count; /* global approximate item count */
> - struct ht_items_count *split_count; /* split item count */
> -
> - unsigned long min_alloc_buckets_order;
> - unsigned long min_nr_alloc_buckets;
> - unsigned long max_nr_buckets;
> - /*
> - * Contains the per order-index-level bucket node table. The size
> - * of each bucket node table is half the number of hashes contained
> - * in this order (except for order 0). The minimum allocation size
> - * parameter allows combining the bucket node arrays of the lowermost
> - * levels to improve cache locality for small index orders.
> - */
> - struct cds_lfht_node *tbl[MAX_TABLE_ORDER];
> -};
> -
> -/*
> * rcu_resize_work: Contains arguments passed to RCU worker thread
> * responsible for performing lazy resize.
> */
> @@ -505,18 +447,6 @@ int get_count_order_ulong(unsigned long x)
> return fls_ulong(x - 1);
> }
>
> -#ifdef POISON_FREE
> -#define poison_free(ptr) \
> - do { \
> - if (ptr) { \
> - memset(ptr, 0x42, sizeof(*(ptr))); \
> - free(ptr); \
> - } \
> - } while (0)
> -#else
> -#define poison_free(ptr) free(ptr)
> -#endif
> -
> static
> void cds_lfht_resize_lazy_grow(struct cds_lfht *ht, unsigned long size, int growth);
>
> @@ -743,16 +673,7 @@ unsigned long _uatomic_xchg_monotonic_increase(unsigned long *ptr,
> static
> void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> - if (order == 0) {
> - ht->tbl[0] = calloc(ht->min_nr_alloc_buckets,
> - sizeof(struct cds_lfht_node));
> - assert(ht->tbl[0]);
> - } else if (order > ht->min_alloc_buckets_order) {
> - ht->tbl[order] = calloc(1UL << (order -1),
> - sizeof(struct cds_lfht_node));
> - assert(ht->tbl[order]);
> - }
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> + return ht->mm->alloc_bucket_table(ht, order);
> }
>
> /*
> @@ -763,32 +684,13 @@ void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> static
> void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> {
> - if (order == 0)
> - poison_free(ht->tbl[0]);
> - else if (order > ht->min_alloc_buckets_order)
> - poison_free(ht->tbl[order]);
> - /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> + return ht->mm->free_bucket_table(ht, order);
> }
>
> static inline
> struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> {
> - unsigned long order;
> -
> - if ((__builtin_constant_p(index) && index == 0)
> - || index < ht->min_nr_alloc_buckets) {
> - dbg_printf("bucket index %lu order 0 aridx 0\n", index);
> - return &ht->tbl[0][index];
> - }
> - /*
> - * equivalent to get_count_order_ulong(index + 1), but optimizes
> - * away the non-existing 0 special-case for
> - * get_count_order_ulong.
> - */
> - order = fls_ulong(index);
> - dbg_printf("bucket index %lu order %lu aridx %lu\n",
> - index, order, index & ((1UL << (order - 1)) - 1));
> - return &ht->tbl[order][index & ((1UL << (order - 1)) - 1)];
> + return ht->bucket_at(ht, index);
> }
>
> static inline
> @@ -1354,6 +1256,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> unsigned long max_nr_buckets,
> int flags,
> + const struct cds_lfht_mm_type *mm,
> const struct rcu_flavor_struct *flavor,
> pthread_attr_t *attr)
> {
> @@ -1368,7 +1271,8 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> if (!init_size || (init_size & (init_size - 1)))
> return NULL;
>
> - if (!max_nr_buckets)
> + /* max_nr_buckets == 0 for order based mm means infinite */
> + if (mm == &cds_lfht_mm_order && !max_nr_buckets)
> max_nr_buckets = 1UL << (MAX_TABLE_ORDER - 1);
>
> /* max_nr_buckets must be power of two */
> @@ -1379,8 +1283,12 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> init_size = max(init_size, MIN_TABLE_SIZE);
> max_nr_buckets = max(max_nr_buckets, min_nr_alloc_buckets);
> init_size = min(init_size, max_nr_buckets);
> - ht = calloc(1, sizeof(struct cds_lfht));
> +
> + ht = mm->alloc_cds_lfht(min_nr_alloc_buckets, max_nr_buckets);
> assert(ht);
> + assert(ht->mm == mm);
> + assert(ht->bucket_at == mm->bucket_at);
> +
> ht->flags = flags;
> ht->flavor = flavor;
> ht->resize_attr = attr;
> @@ -1389,9 +1297,6 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> pthread_mutex_init(&ht->resize_mutex, NULL);
> order = get_count_order_ulong(init_size);
> ht->resize_target = 1UL << order;
> - ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> - ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
> - ht->max_nr_buckets = max_nr_buckets;
> cds_lfht_create_bucket(ht, 1UL << order);
> ht->size = 1UL << order;
> return ht;
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index a886b04..926aa14 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -95,6 +95,17 @@ enum {
> CDS_LFHT_ACCOUNTING = (1U << 1),
> };
>
> +struct cds_lfht_mm_type {
> + struct cds_lfht *(*alloc_cds_lfht)(unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets);
> + void (*alloc_bucket_table)(struct cds_lfht *ht, unsigned long order);
> + void (*free_bucket_table)(struct cds_lfht *ht, unsigned long order);
> + struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
> + unsigned long index);
> +};
> +
> +extern const struct cds_lfht_mm_type cds_lfht_mm_order;
> +
> /*
> * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
> */
> @@ -102,6 +113,7 @@ struct cds_lfht *_cds_lfht_new(unsigned long init_size,
> unsigned long min_nr_alloc_buckets,
> unsigned long max_nr_buckets,
> int flags,
> + const struct cds_lfht_mm_type *mm,
> const struct rcu_flavor_struct *flavor,
> pthread_attr_t *attr);
>
> @@ -138,7 +150,7 @@ struct cds_lfht *cds_lfht_new(unsigned long init_size,
> pthread_attr_t *attr)
> {
> return _cds_lfht_new(init_size, min_nr_alloc_buckets, max_nr_buckets,
> - flags, &rcu_flavor, attr);
> + flags, &cds_lfht_mm_order, &rcu_flavor, attr);
> }
>
> /*
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management
2011-11-28 8:08 ` [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management Lai Jiangshan
@ 2011-11-28 13:33 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:33 UTC (permalink / raw)
Merged as:
commit 308d1cb3650b63d373e60eef0582d6e238b0d2d0
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date: Mon Nov 28 08:30:55 2011 -0500
add rculfhash-mm-chunk.c memory management
[ Edit by Mathieu Desnoyers: Update comment above
struct cds_lfht_node *tbl_chunk. ]
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
diff --git a/Makefile.am b/Makefile.am
index 4d3f7bd..853ecd5 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,7 +35,7 @@ if COMPAT_FUTEX
COMPAT+=compat_futex.c
endif
-RCULFHASH=rculfhash.c rculfhash-mm-order.c
+RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
lib_LTLIBRARIES = liburcu-common.la \
liburcu.la liburcu-qsbr.la \
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index 820e62c..f7c6590 100644
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -38,6 +38,8 @@
#define MAX_TABLE_ORDER 64
#endif
+#define MAX_CHUNK_TABLE (1UL << 10)
+
#ifndef min
#define min(a, b) ((a) < (b) ? (a) : (b))
#endif
@@ -94,6 +96,18 @@ struct cds_lfht {
* levels to improve cache locality for small index orders.
*/
struct cds_lfht_node *tbl_order[MAX_TABLE_ORDER];
+
+ /*
+ * Contains the bucket node chunks. The size of each
+ * bucket node chunk is ->min_alloc_size (we avoid to
+ * allocate chunks with different size). Chunks improve
+ * cache locality for small index orders, and are more
+ * friendly with environments where allocation of large
+ * contiguous memory areas is challenging due to memory
+ * fragmentation concerns or inability to use virtual
+ * memory addressing.
+ */
+ struct cds_lfht_node *tbl_chunk[0];
};
};
diff --git a/rculfhash-mm-chunk.c b/rculfhash-mm-chunk.c
new file mode 100644
index 0000000..0469776
--- /dev/null
+++ b/rculfhash-mm-chunk.c
@@ -0,0 +1,107 @@
+/*
+ * rculfhash-mm-chunk.c
+ *
+ * Chunk based memory management for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <stddef.h>
+#include <rculfhash-internal.h>
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ ht->tbl_chunk[0] = calloc(ht->min_nr_alloc_buckets,
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_chunk[0]);
+ } else if (order > ht->min_alloc_buckets_order) {
+ unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order);
+
+ for (i = len; i < 2 * len; i++) {
+ ht->tbl_chunk[i] = calloc(ht->min_nr_alloc_buckets,
+ sizeof(struct cds_lfht_node));
+ assert(ht->tbl_chunk[i]);
+ }
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0)
+ poison_free(ht->tbl_chunk[0]);
+ else if (order > ht->min_alloc_buckets_order) {
+ unsigned long i, len = 1UL << (order - 1 - ht->min_alloc_buckets_order);
+
+ for (i = len; i < 2 * len; i++)
+ poison_free(ht->tbl_chunk[i]);
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+static
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+ unsigned long chunk, offset;
+
+ chunk = index >> ht->min_alloc_buckets_order;
+ offset = index & (ht->min_nr_alloc_buckets - 1);
+ return &ht->tbl_chunk[chunk][offset];
+}
+
+static
+struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets)
+{
+ struct cds_lfht *ht;
+ unsigned long nr_chunks, cds_lfht_size;
+
+ min_nr_alloc_buckets = max(min_nr_alloc_buckets,
+ max_nr_buckets / MAX_CHUNK_TABLE);
+
+ nr_chunks = max_nr_buckets / min_nr_alloc_buckets;
+ cds_lfht_size = offsetof(struct cds_lfht, tbl_chunk) +
+ sizeof(ht->tbl_chunk[0]) * nr_chunks;
+ cds_lfht_size = max(cds_lfht_size, sizeof(struct cds_lfht));
+ ht = calloc(1, cds_lfht_size);
+ assert(ht);
+
+ ht->mm = &cds_lfht_mm_chunk;
+
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order = get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
+
+ ht->bucket_at = bucket_at;
+
+ return ht;
+}
+
+const struct cds_lfht_mm_type cds_lfht_mm_chunk = {
+ .alloc_cds_lfht = alloc_cds_lfht,
+ .alloc_bucket_table = cds_lfht_alloc_bucket_table,
+ .free_bucket_table = cds_lfht_free_bucket_table,
+ .bucket_at = bucket_at,
+};
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index c03baf4..1224ea8 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -105,6 +105,7 @@ struct cds_lfht_mm_type {
};
extern const struct cds_lfht_mm_type cds_lfht_mm_order;
+extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
/*
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management
2011-11-28 8:08 ` [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c " Lai Jiangshan
@ 2011-11-28 13:43 ` Mathieu Desnoyers
2011-11-28 14:05 ` Lai Jiangshan
0 siblings, 1 reply; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:43 UTC (permalink / raw)
Merged as:
commit b0b5525153fce8abae07b9573da1d5169e02eb2b
Author: Lai Jiangshan <laijs at cn.fujitsu.com>
Date: Mon Nov 28 08:41:10 2011 -0500
add rculfhash-mm-mmap.c memory management
[ Edit by Mathieu Desnoyers:
- change "buckets" for "mmap" to better show the mapping between the
union member and the mm plugin.
- 80 col coding style fixups. ]
Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
diff --git a/Makefile.am b/Makefile.am
index 853ecd5..91a9fd1 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,7 +35,8 @@ if COMPAT_FUTEX
COMPAT+=compat_futex.c
endif
-RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
+RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \
+ rculfhash-mm-mmap.c
lib_LTLIBRARIES = liburcu-common.la \
liburcu.la liburcu-qsbr.la \
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index f7c6590..cc14664 100644
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -108,6 +108,12 @@ struct cds_lfht {
* memory addressing.
*/
struct cds_lfht_node *tbl_chunk[0];
+
+ /*
+ * Memory mapping with room for all possible buckets.
+ * Their memory is allocated when needed.
+ */
+ struct cds_lfht_node *tbl_mmap;
};
};
diff --git a/rculfhash-mm-mmap.c b/rculfhash-mm-mmap.c
new file mode 100644
index 0000000..542c884
--- /dev/null
+++ b/rculfhash-mm-mmap.c
@@ -0,0 +1,160 @@
+/*
+ * rculfhash-mm-mmap.c
+ *
+ * mmap/reservation based memory management for Lock-Free RCU Hash Table
+ *
+ * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <unistd.h>
+#include <sys/mman.h>
+#include "rculfhash-internal.h"
+
+/* reserve inaccessible memory space without allocation any memory */
+static void *memory_map(size_t length)
+{
+ void *ret = mmap(NULL, length, PROT_NONE,
+ MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret != MAP_FAILED);
+ return ret;
+}
+
+static void memory_unmap(void *ptr, size_t length)
+{
+ int ret = munmap(ptr, length);
+
+ assert(ret == 0);
+}
+
+static void memory_populate(void *ptr, size_t length)
+{
+ void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
+ MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret == ptr);
+}
+
+/*
+ * Discard garbage memory and avoid system save it when try to swap it out.
+ * Make it still reserved, inaccessible.
+ */
+static void memory_discard(void *ptr, size_t length)
+{
+ void *ret = mmap(ptr, length, PROT_NONE,
+ MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+ assert(ret == ptr);
+}
+
+static
+void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
+ /* small table */
+ ht->tbl_mmap = calloc(ht->max_nr_buckets,
+ sizeof(*ht->tbl_mmap));
+ assert(ht->tbl_mmap);
+ return;
+ }
+ /* large table */
+ ht->tbl_mmap = memory_map(ht->max_nr_buckets
+ * sizeof(*ht->tbl_mmap));
+ memory_populate(ht->tbl_mmap,
+ ht->min_nr_alloc_buckets * sizeof(*ht->tbl_mmap));
+ } else if (order > ht->min_alloc_buckets_order) {
+ /* large table */
+ unsigned long len = 1UL << (order - 1);
+
+ assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
+ memory_populate(ht->tbl_mmap + len,
+ len * sizeof(*ht->tbl_mmap));
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+/*
+ * cds_lfht_free_bucket_table() should be called with decreasing order.
+ * When cds_lfht_free_bucket_table(0) is called, it means the whole
+ * lfht is destroyed.
+ */
+static
+void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
+{
+ if (order == 0) {
+ if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
+ /* small table */
+ poison_free(ht->tbl_mmap);
+ return;
+ }
+ /* large table */
+ memory_unmap(ht->tbl_mmap,
+ ht->max_nr_buckets * sizeof(*ht->tbl_mmap));
+ } else if (order > ht->min_alloc_buckets_order) {
+ /* large table */
+ unsigned long len = 1UL << (order - 1);
+
+ assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
+ memory_discard(ht->tbl_mmap + len, len * sizeof(*ht->tbl_mmap));
+ }
+ /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
+}
+
+static
+struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
+{
+ return &ht->tbl_mmap[index];
+}
+
+static
+struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
+ unsigned long max_nr_buckets)
+{
+ struct cds_lfht *ht;
+ unsigned long page_bucket_size = getpagesize() / sizeof(*ht->tbl_mmap);
+
+ if (max_nr_buckets <= page_bucket_size) {
+ /* small table */
+ min_nr_alloc_buckets = max_nr_buckets;
+ } else {
+ /* large table */
+ min_nr_alloc_buckets = max(min_nr_alloc_buckets,
+ page_bucket_size);
+ }
+
+ ht = calloc(1, sizeof(struct cds_lfht));
+ assert(ht);
+
+ ht->mm = &cds_lfht_mm_mmap;
+
+ ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
+ ht->min_alloc_buckets_order =
+ get_count_order_ulong(min_nr_alloc_buckets);
+ ht->max_nr_buckets = max_nr_buckets;
+
+ ht->bucket_at = bucket_at;
+
+ return ht;
+}
+
+const struct cds_lfht_mm_type cds_lfht_mm_mmap = {
+ .alloc_cds_lfht = alloc_cds_lfht,
+ .alloc_bucket_table = cds_lfht_alloc_bucket_table,
+ .free_bucket_table = cds_lfht_free_bucket_table,
+ .bucket_at = bucket_at,
+};
diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
index 1224ea8..6ed7c8c 100644
--- a/urcu/rculfhash.h
+++ b/urcu/rculfhash.h
@@ -106,6 +106,7 @@ struct cds_lfht_mm_type {
extern const struct cds_lfht_mm_type cds_lfht_mm_order;
extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
+extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
/*
* _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 00/12] rculfhash memory managements
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
` (11 preceding siblings ...)
2011-11-28 8:08 ` [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c " Lai Jiangshan
@ 2011-11-28 13:43 ` Mathieu Desnoyers
2011-11-28 14:23 ` Lai Jiangshan
12 siblings, 1 reply; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 13:43 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> Patch 1-9: extract memory managements (internal)APIs and prepare
> for memory managements
>
> (Patch 7 add general struct rcu_flavor)
>
> Patch 10-12: Add memory managements.
All merged, thanks Lai!
Mathieu
>
>
> Lai Jiangshan (12):
> introduce bucket_at() and improve readability
> proper wrapper for bucket table alloc and free
> it is not required that ht->t.size >= ht->min_table_size now
> remove struct rcu_level
> rename min_alloc_size/min_alloc_order
> add max_nr_buckets argument
> Add rcu_flavor
> use rcu_flavor for rculfhash
> remove struct rcu_table
> move memory management code out as rculfhash-mm-order.c
> add rculfhash-mm-chunk.c
> add rculfhash-mm-mmap.c
>
> Makefile.am | 8 +-
> rculfhash-internal.h | 131 +++++++++++++++
> rculfhash-mm-chunk.c | 107 ++++++++++++
> rculfhash-mm-mmap.c | 147 +++++++++++++++++
> rculfhash-mm-order.c | 101 ++++++++++++
> rculfhash.c | 417 +++++++++++++++++++-----------------------------
> tests/test_urcu_hash.c | 4 +-
> urcu-bp.c | 2 +
> urcu-bp.h | 1 +
> urcu-flavor.h | 65 ++++++++
> urcu-qsbr.c | 2 +
> urcu-qsbr.h | 1 +
> urcu.c | 2 +
> urcu.h | 1 +
> urcu/map/urcu-bp.h | 2 +
> urcu/map/urcu-qsbr.h | 2 +
> urcu/map/urcu.h | 6 +
> urcu/rculfhash.h | 43 +++--
> 18 files changed, 768 insertions(+), 274 deletions(-)
> create mode 100644 rculfhash-internal.h
> create mode 100644 rculfhash-mm-chunk.c
> create mode 100644 rculfhash-mm-mmap.c
> create mode 100644 rculfhash-mm-order.c
> create mode 100644 urcu-flavor.h
>
> --
> 1.7.4.4
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management
2011-11-28 13:43 ` Mathieu Desnoyers
@ 2011-11-28 14:05 ` Lai Jiangshan
2011-11-28 14:15 ` Mathieu Desnoyers
0 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 14:05 UTC (permalink / raw)
On 11/28/2011 09:43 PM, Mathieu Desnoyers wrote:
> Merged as:
>
> commit b0b5525153fce8abae07b9573da1d5169e02eb2b
> Author: Lai Jiangshan <laijs at cn.fujitsu.com>
> Date: Mon Nov 28 08:41:10 2011 -0500
>
> add rculfhash-mm-mmap.c memory management
>
> [ Edit by Mathieu Desnoyers:
> - change "buckets" for "mmap" to better show the mapping between the
> union member and the mm plugin.
> - 80 col coding style fixups. ]
tbl_order contains pointers of bucket _order_ table
tbl_chunk contains pointers of bucket _chunk_ table
tbl_buckets is a table which contains _buckets_
But here, we focus on memory, so tbl_mmap is also good for me.
Thanks,
Lai
>
> Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
>
> diff --git a/Makefile.am b/Makefile.am
> index 853ecd5..91a9fd1 100644
> --- a/Makefile.am
> +++ b/Makefile.am
> @@ -35,7 +35,8 @@ if COMPAT_FUTEX
> COMPAT+=compat_futex.c
> endif
>
> -RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
> +RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \
> + rculfhash-mm-mmap.c
>
> lib_LTLIBRARIES = liburcu-common.la \
> liburcu.la liburcu-qsbr.la \
> diff --git a/rculfhash-internal.h b/rculfhash-internal.h
> index f7c6590..cc14664 100644
> --- a/rculfhash-internal.h
> +++ b/rculfhash-internal.h
> @@ -108,6 +108,12 @@ struct cds_lfht {
> * memory addressing.
> */
> struct cds_lfht_node *tbl_chunk[0];
> +
> + /*
> + * Memory mapping with room for all possible buckets.
> + * Their memory is allocated when needed.
> + */
> + struct cds_lfht_node *tbl_mmap;
> };
> };
>
> diff --git a/rculfhash-mm-mmap.c b/rculfhash-mm-mmap.c
> new file mode 100644
> index 0000000..542c884
> --- /dev/null
> +++ b/rculfhash-mm-mmap.c
> @@ -0,0 +1,160 @@
> +/*
> + * rculfhash-mm-mmap.c
> + *
> + * mmap/reservation based memory management for Lock-Free RCU Hash Table
> + *
> + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU Lesser General Public
> + * License as published by the Free Software Foundation; either
> + * version 2.1 of the License, or (at your option) any later version.
> + *
> + * This library is distributed in the hope that it will be useful,
> + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + * Lesser General Public License for more details.
> + *
> + * You should have received a copy of the GNU Lesser General Public
> + * License along with this library; if not, write to the Free Software
> + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> + */
> +
> +#include <unistd.h>
> +#include <sys/mman.h>
> +#include "rculfhash-internal.h"
> +
> +/* reserve inaccessible memory space without allocation any memory */
> +static void *memory_map(size_t length)
> +{
> + void *ret = mmap(NULL, length, PROT_NONE,
> + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> + assert(ret != MAP_FAILED);
> + return ret;
> +}
> +
> +static void memory_unmap(void *ptr, size_t length)
> +{
> + int ret = munmap(ptr, length);
> +
> + assert(ret == 0);
> +}
> +
> +static void memory_populate(void *ptr, size_t length)
> +{
> + void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
> + MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> + assert(ret == ptr);
> +}
> +
> +/*
> + * Discard garbage memory and avoid system save it when try to swap it out.
> + * Make it still reserved, inaccessible.
> + */
> +static void memory_discard(void *ptr, size_t length)
> +{
> + void *ret = mmap(ptr, length, PROT_NONE,
> + MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> +
> + assert(ret == ptr);
> +}
> +
> +static
> +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0) {
> + if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
> + /* small table */
> + ht->tbl_mmap = calloc(ht->max_nr_buckets,
> + sizeof(*ht->tbl_mmap));
> + assert(ht->tbl_mmap);
> + return;
> + }
> + /* large table */
> + ht->tbl_mmap = memory_map(ht->max_nr_buckets
> + * sizeof(*ht->tbl_mmap));
> + memory_populate(ht->tbl_mmap,
> + ht->min_nr_alloc_buckets * sizeof(*ht->tbl_mmap));
> + } else if (order > ht->min_alloc_buckets_order) {
> + /* large table */
> + unsigned long len = 1UL << (order - 1);
> +
> + assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> + memory_populate(ht->tbl_mmap + len,
> + len * sizeof(*ht->tbl_mmap));
> + }
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> +}
> +
> +/*
> + * cds_lfht_free_bucket_table() should be called with decreasing order.
> + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> + * lfht is destroyed.
> + */
> +static
> +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> +{
> + if (order == 0) {
> + if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
> + /* small table */
> + poison_free(ht->tbl_mmap);
> + return;
> + }
> + /* large table */
> + memory_unmap(ht->tbl_mmap,
> + ht->max_nr_buckets * sizeof(*ht->tbl_mmap));
> + } else if (order > ht->min_alloc_buckets_order) {
> + /* large table */
> + unsigned long len = 1UL << (order - 1);
> +
> + assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> + memory_discard(ht->tbl_mmap + len, len * sizeof(*ht->tbl_mmap));
> + }
> + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> +}
> +
> +static
> +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> +{
> + return &ht->tbl_mmap[index];
> +}
> +
> +static
> +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
> + unsigned long max_nr_buckets)
> +{
> + struct cds_lfht *ht;
> + unsigned long page_bucket_size = getpagesize() / sizeof(*ht->tbl_mmap);
> +
> + if (max_nr_buckets <= page_bucket_size) {
> + /* small table */
> + min_nr_alloc_buckets = max_nr_buckets;
> + } else {
> + /* large table */
> + min_nr_alloc_buckets = max(min_nr_alloc_buckets,
> + page_bucket_size);
> + }
> +
> + ht = calloc(1, sizeof(struct cds_lfht));
> + assert(ht);
> +
> + ht->mm = &cds_lfht_mm_mmap;
> +
> + ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> + ht->min_alloc_buckets_order =
> + get_count_order_ulong(min_nr_alloc_buckets);
> + ht->max_nr_buckets = max_nr_buckets;
> +
> + ht->bucket_at = bucket_at;
> +
> + return ht;
> +}
> +
> +const struct cds_lfht_mm_type cds_lfht_mm_mmap = {
> + .alloc_cds_lfht = alloc_cds_lfht,
> + .alloc_bucket_table = cds_lfht_alloc_bucket_table,
> + .free_bucket_table = cds_lfht_free_bucket_table,
> + .bucket_at = bucket_at,
> +};
> diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> index 1224ea8..6ed7c8c 100644
> --- a/urcu/rculfhash.h
> +++ b/urcu/rculfhash.h
> @@ -106,6 +106,7 @@ struct cds_lfht_mm_type {
>
> extern const struct cds_lfht_mm_type cds_lfht_mm_order;
> extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
> +extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
>
> /*
> * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
>
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c memory management
2011-11-28 14:05 ` Lai Jiangshan
@ 2011-11-28 14:15 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 14:15 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/28/2011 09:43 PM, Mathieu Desnoyers wrote:
> > Merged as:
> >
> > commit b0b5525153fce8abae07b9573da1d5169e02eb2b
> > Author: Lai Jiangshan <laijs at cn.fujitsu.com>
> > Date: Mon Nov 28 08:41:10 2011 -0500
> >
> > add rculfhash-mm-mmap.c memory management
> >
> > [ Edit by Mathieu Desnoyers:
> > - change "buckets" for "mmap" to better show the mapping between the
> > union member and the mm plugin.
> > - 80 col coding style fixups. ]
>
> tbl_order contains pointers of bucket _order_ table
> tbl_chunk contains pointers of bucket _chunk_ table
> tbl_buckets is a table which contains _buckets_
>
> But here, we focus on memory, so tbl_mmap is also good for me.
I agree that "buckets" was also correct, but my primary intent here is
to show the mapping between the union entries and the individual memory
management plugins, which I think is better conveyed by "mmap" than
"buckets". I think it is also good that the field name reflects that
this points to a memory mapping that is not entirely populated rather
than to buckets, because "buckets" could mean those are all
pre-allocated (from the point of view of someone who reviews the code).
Using "mmap" for the mmap-plugin field leaves room, for instance, for a
new mm plugin called "bucket", which would pre-populate all memory for
all buckets. This could be useful for tables with maximum fixed-size
number of buckets.
By the way, I just pushed a few cleanup updates of my own into the tree.
Thanks!
Mathieu
>
> Thanks,
> Lai
>
> >
> > Signed-off-by: Lai Jiangshan <laijs at cn.fujitsu.com>
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> >
> > diff --git a/Makefile.am b/Makefile.am
> > index 853ecd5..91a9fd1 100644
> > --- a/Makefile.am
> > +++ b/Makefile.am
> > @@ -35,7 +35,8 @@ if COMPAT_FUTEX
> > COMPAT+=compat_futex.c
> > endif
> >
> > -RCULFHASH=rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c
> > +RCULFHASH = rculfhash.c rculfhash-mm-order.c rculfhash-mm-chunk.c \
> > + rculfhash-mm-mmap.c
> >
> > lib_LTLIBRARIES = liburcu-common.la \
> > liburcu.la liburcu-qsbr.la \
> > diff --git a/rculfhash-internal.h b/rculfhash-internal.h
> > index f7c6590..cc14664 100644
> > --- a/rculfhash-internal.h
> > +++ b/rculfhash-internal.h
> > @@ -108,6 +108,12 @@ struct cds_lfht {
> > * memory addressing.
> > */
> > struct cds_lfht_node *tbl_chunk[0];
> > +
> > + /*
> > + * Memory mapping with room for all possible buckets.
> > + * Their memory is allocated when needed.
> > + */
> > + struct cds_lfht_node *tbl_mmap;
> > };
> > };
> >
> > diff --git a/rculfhash-mm-mmap.c b/rculfhash-mm-mmap.c
> > new file mode 100644
> > index 0000000..542c884
> > --- /dev/null
> > +++ b/rculfhash-mm-mmap.c
> > @@ -0,0 +1,160 @@
> > +/*
> > + * rculfhash-mm-mmap.c
> > + *
> > + * mmap/reservation based memory management for Lock-Free RCU Hash Table
> > + *
> > + * Copyright 2011 - Lai Jiangshan <laijs at cn.fujitsu.com>
> > + *
> > + * This library is free software; you can redistribute it and/or
> > + * modify it under the terms of the GNU Lesser General Public
> > + * License as published by the Free Software Foundation; either
> > + * version 2.1 of the License, or (at your option) any later version.
> > + *
> > + * This library is distributed in the hope that it will be useful,
> > + * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> > + * Lesser General Public License for more details.
> > + *
> > + * You should have received a copy of the GNU Lesser General Public
> > + * License along with this library; if not, write to the Free Software
> > + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > + */
> > +
> > +#include <unistd.h>
> > +#include <sys/mman.h>
> > +#include "rculfhash-internal.h"
> > +
> > +/* reserve inaccessible memory space without allocation any memory */
> > +static void *memory_map(size_t length)
> > +{
> > + void *ret = mmap(NULL, length, PROT_NONE,
> > + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> > +
> > + assert(ret != MAP_FAILED);
> > + return ret;
> > +}
> > +
> > +static void memory_unmap(void *ptr, size_t length)
> > +{
> > + int ret = munmap(ptr, length);
> > +
> > + assert(ret == 0);
> > +}
> > +
> > +static void memory_populate(void *ptr, size_t length)
> > +{
> > + void *ret = mmap(ptr, length, PROT_READ | PROT_WRITE,
> > + MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> > +
> > + assert(ret == ptr);
> > +}
> > +
> > +/*
> > + * Discard garbage memory and avoid system save it when try to swap it out.
> > + * Make it still reserved, inaccessible.
> > + */
> > +static void memory_discard(void *ptr, size_t length)
> > +{
> > + void *ret = mmap(ptr, length, PROT_NONE,
> > + MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> > +
> > + assert(ret == ptr);
> > +}
> > +
> > +static
> > +void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
> > +{
> > + if (order == 0) {
> > + if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
> > + /* small table */
> > + ht->tbl_mmap = calloc(ht->max_nr_buckets,
> > + sizeof(*ht->tbl_mmap));
> > + assert(ht->tbl_mmap);
> > + return;
> > + }
> > + /* large table */
> > + ht->tbl_mmap = memory_map(ht->max_nr_buckets
> > + * sizeof(*ht->tbl_mmap));
> > + memory_populate(ht->tbl_mmap,
> > + ht->min_nr_alloc_buckets * sizeof(*ht->tbl_mmap));
> > + } else if (order > ht->min_alloc_buckets_order) {
> > + /* large table */
> > + unsigned long len = 1UL << (order - 1);
> > +
> > + assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> > + memory_populate(ht->tbl_mmap + len,
> > + len * sizeof(*ht->tbl_mmap));
> > + }
> > + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> > +}
> > +
> > +/*
> > + * cds_lfht_free_bucket_table() should be called with decreasing order.
> > + * When cds_lfht_free_bucket_table(0) is called, it means the whole
> > + * lfht is destroyed.
> > + */
> > +static
> > +void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order)
> > +{
> > + if (order == 0) {
> > + if (ht->min_nr_alloc_buckets == ht->max_nr_buckets) {
> > + /* small table */
> > + poison_free(ht->tbl_mmap);
> > + return;
> > + }
> > + /* large table */
> > + memory_unmap(ht->tbl_mmap,
> > + ht->max_nr_buckets * sizeof(*ht->tbl_mmap));
> > + } else if (order > ht->min_alloc_buckets_order) {
> > + /* large table */
> > + unsigned long len = 1UL << (order - 1);
> > +
> > + assert(ht->min_nr_alloc_buckets < ht->max_nr_buckets);
> > + memory_discard(ht->tbl_mmap + len, len * sizeof(*ht->tbl_mmap));
> > + }
> > + /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */
> > +}
> > +
> > +static
> > +struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index)
> > +{
> > + return &ht->tbl_mmap[index];
> > +}
> > +
> > +static
> > +struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets,
> > + unsigned long max_nr_buckets)
> > +{
> > + struct cds_lfht *ht;
> > + unsigned long page_bucket_size = getpagesize() / sizeof(*ht->tbl_mmap);
> > +
> > + if (max_nr_buckets <= page_bucket_size) {
> > + /* small table */
> > + min_nr_alloc_buckets = max_nr_buckets;
> > + } else {
> > + /* large table */
> > + min_nr_alloc_buckets = max(min_nr_alloc_buckets,
> > + page_bucket_size);
> > + }
> > +
> > + ht = calloc(1, sizeof(struct cds_lfht));
> > + assert(ht);
> > +
> > + ht->mm = &cds_lfht_mm_mmap;
> > +
> > + ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
> > + ht->min_alloc_buckets_order =
> > + get_count_order_ulong(min_nr_alloc_buckets);
> > + ht->max_nr_buckets = max_nr_buckets;
> > +
> > + ht->bucket_at = bucket_at;
> > +
> > + return ht;
> > +}
> > +
> > +const struct cds_lfht_mm_type cds_lfht_mm_mmap = {
> > + .alloc_cds_lfht = alloc_cds_lfht,
> > + .alloc_bucket_table = cds_lfht_alloc_bucket_table,
> > + .free_bucket_table = cds_lfht_free_bucket_table,
> > + .bucket_at = bucket_at,
> > +};
> > diff --git a/urcu/rculfhash.h b/urcu/rculfhash.h
> > index 1224ea8..6ed7c8c 100644
> > --- a/urcu/rculfhash.h
> > +++ b/urcu/rculfhash.h
> > @@ -106,6 +106,7 @@ struct cds_lfht_mm_type {
> >
> > extern const struct cds_lfht_mm_type cds_lfht_mm_order;
> > extern const struct cds_lfht_mm_type cds_lfht_mm_chunk;
> > +extern const struct cds_lfht_mm_type cds_lfht_mm_mmap;
> >
> > /*
> > * _cds_lfht_new - API used by cds_lfht_new wrapper. Do not use directly.
> >
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 00/12] rculfhash memory managements
2011-11-28 13:43 ` [lttng-dev] [PATCH 00/12] rculfhash memory managements Mathieu Desnoyers
@ 2011-11-28 14:23 ` Lai Jiangshan
2011-11-28 14:39 ` Mathieu Desnoyers
0 siblings, 1 reply; 30+ messages in thread
From: Lai Jiangshan @ 2011-11-28 14:23 UTC (permalink / raw)
3fd3f554f6eb18ae5ec526b82025a53a554f775d are wrong,
1) dynamic len tbl_chunk must at the end of cds_lfht, (so I put all the mm field at the end of cds_lfht).
2) lists of hot access fields:
size
tbl_order/chunk/mmap
bucket_at
flags (testing for counting)
split_count
min_alloc_buckets_order (bucket_at() for chunk mm)
min_nr_alloc_buckets (buket_at() for order mm and chunk mm)
They are many, so I group them by functional, not accessing ratio.
On 11/28/2011 09:43 PM, Mathieu Desnoyers wrote:
> * Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
>> Patch 1-9: extract memory managements (internal)APIs and prepare
>> for memory managements
>>
>> (Patch 7 add general struct rcu_flavor)
>>
>> Patch 10-12: Add memory managements.
>
> All merged, thanks Lai!
>
> Mathieu
>
>>
>>
>> Lai Jiangshan (12):
>> introduce bucket_at() and improve readability
>> proper wrapper for bucket table alloc and free
>> it is not required that ht->t.size >= ht->min_table_size now
>> remove struct rcu_level
>> rename min_alloc_size/min_alloc_order
>> add max_nr_buckets argument
>> Add rcu_flavor
>> use rcu_flavor for rculfhash
>> remove struct rcu_table
>> move memory management code out as rculfhash-mm-order.c
>> add rculfhash-mm-chunk.c
>> add rculfhash-mm-mmap.c
>>
>> Makefile.am | 8 +-
>> rculfhash-internal.h | 131 +++++++++++++++
>> rculfhash-mm-chunk.c | 107 ++++++++++++
>> rculfhash-mm-mmap.c | 147 +++++++++++++++++
>> rculfhash-mm-order.c | 101 ++++++++++++
>> rculfhash.c | 417 +++++++++++++++++++-----------------------------
>> tests/test_urcu_hash.c | 4 +-
>> urcu-bp.c | 2 +
>> urcu-bp.h | 1 +
>> urcu-flavor.h | 65 ++++++++
>> urcu-qsbr.c | 2 +
>> urcu-qsbr.h | 1 +
>> urcu.c | 2 +
>> urcu.h | 1 +
>> urcu/map/urcu-bp.h | 2 +
>> urcu/map/urcu-qsbr.h | 2 +
>> urcu/map/urcu.h | 6 +
>> urcu/rculfhash.h | 43 +++--
>> 18 files changed, 768 insertions(+), 274 deletions(-)
>> create mode 100644 rculfhash-internal.h
>> create mode 100644 rculfhash-mm-chunk.c
>> create mode 100644 rculfhash-mm-mmap.c
>> create mode 100644 rculfhash-mm-order.c
>> create mode 100644 urcu-flavor.h
>>
>> --
>> 1.7.4.4
>>
>
^ permalink raw reply [flat|nested] 30+ messages in thread
* [lttng-dev] [PATCH 00/12] rculfhash memory managements
2011-11-28 14:23 ` Lai Jiangshan
@ 2011-11-28 14:39 ` Mathieu Desnoyers
0 siblings, 0 replies; 30+ messages in thread
From: Mathieu Desnoyers @ 2011-11-28 14:39 UTC (permalink / raw)
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> 3fd3f554f6eb18ae5ec526b82025a53a554f775d are wrong,
>
> 1) dynamic len tbl_chunk must at the end of cds_lfht, (so I put all the mm field at the end of cds_lfht).
My bad, will fix.
>
> 2) lists of hot access fields:
> size
> tbl_order/chunk/mmap
> bucket_at
> flags (testing for counting)
> split_count
> min_alloc_buckets_order (bucket_at() for chunk mm)
> min_nr_alloc_buckets (buket_at() for order mm and chunk mm)
>
> They are many, so I group them by functional, not accessing ratio.
Here is the fix. Please note that we could probably do better by
putting the fast-path fields into a cacheline-aligned structure. I'm
just unsure about the effect of putting the union with a variable-sized
field into such a structure, so I'll let you look into this if you want.
Here is my fix:
commit f45b03e03cc09b539b6f6c4f6a72663c212343d8
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date: Mon Nov 28 09:37:21 2011 -0500
Fix cds_lfht field order
* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> 3fd3f554f6eb18ae5ec526b82025a53a554f775d are wrong,
>
> 1) dynamic len tbl_chunk must at the end of cds_lfht, (so I put all the mm field at the end of cds_lfht).
My bad, will fix.
>
> 2) lists of hot access fields:
> size
> tbl_order/chunk/mmap
> bucket_at
> flags (testing for counting)
> split_count
> min_alloc_buckets_order (bucket_at() for chunk mm)
> min_nr_alloc_buckets (buket_at() for order mm and chunk mm)
Suggested-by: Lai Jiangshan <laijs at cn.fujitsu.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
diff --git a/rculfhash-internal.h b/rculfhash-internal.h
index 792e04d..38a0317 100644
--- a/rculfhash-internal.h
+++ b/rculfhash-internal.h
@@ -54,12 +54,54 @@ struct ht_items_count;
* cds_lfht: Top-level data structure representing a lock-free hash
* table. Defined in the implementation file to make it be an opaque
* cookie to users.
+ *
+ * The fields used in fast-paths are placed near the end of the
+ * structure, because we need to have a variable-sized union to contain
+ * the mm plugin fields, which are used in the fast path.
*/
struct cds_lfht {
+ /* Initial configuration items */
+ unsigned long max_nr_buckets;
+ const struct cds_lfht_mm_type *mm; /* memory management plugin */
+ const struct rcu_flavor_struct *flavor; /* RCU flavor */
+
+ long count; /* global approximate item count */
+
+ /*
+ * We need to put the work threads offline (QSBR) when taking this
+ * mutex, because we use synchronize_rcu within this mutex critical
+ * section, which waits on read-side critical sections, and could
+ * therefore cause grace-period deadlock if we hold off RCU G.P.
+ * completion.
+ */
+ pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
+ pthread_attr_t *resize_attr; /* Resize threads attributes */
+ unsigned int in_progress_resize, in_progress_destroy;
+ unsigned long resize_target;
+ int resize_initiated;
+
+ /*
+ * Variables needed for add and remove fast-paths.
+ */
+ int flags;
+ unsigned long min_alloc_buckets_order;
+ unsigned long min_nr_alloc_buckets;
+ struct ht_items_count *split_count; /* split item count */
+
/*
* Variables needed for the lookup, add and remove fast-paths.
*/
unsigned long size; /* always a power of 2, shared (RCU) */
+ /*
+ * bucket_at pointer is kept here to skip the extra level of
+ * dereference needed to get to "mm" (this is a fast-path).
+ */
+ struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
+ unsigned long index);
+ /*
+ * Dynamic length "tbl_chunk" needs to be at the end of
+ * cds_lfht.
+ */
union {
/*
* Contains the per order-index-level bucket node table.
@@ -90,42 +132,9 @@ struct cds_lfht {
struct cds_lfht_node *tbl_mmap;
};
/*
- * bucket_at pointer is kept here to skip the extra level of
- * dereference needed to get to "mm" (this is a fast-path).
- */
- struct cds_lfht_node *(*bucket_at)(struct cds_lfht *ht,
- unsigned long index);
- /*
- * End of variables needed for lookup fast-path.
- */
-
- struct ht_items_count *split_count; /* split item count */
- /*
- * End of variables needed for add/remove fast-path.
- */
-
- /* Initial configuration items */
- int flags;
- unsigned long min_alloc_buckets_order;
- unsigned long min_nr_alloc_buckets;
- unsigned long max_nr_buckets;
- const struct cds_lfht_mm_type *mm; /* memory management plugin */
- const struct rcu_flavor_struct *flavor; /* RCU flavor */
-
- long count; /* global approximate item count */
-
- /*
- * We need to put the work threads offline (QSBR) when taking this
- * mutex, because we use synchronize_rcu within this mutex critical
- * section, which waits on read-side critical sections, and could
- * therefore cause grace-period deadlock if we hold off RCU G.P.
- * completion.
+ * End of variables needed for the lookup, add and remove
+ * fast-paths.
*/
- pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
- pthread_attr_t *resize_attr; /* Resize threads attributes */
- unsigned int in_progress_resize, in_progress_destroy;
- unsigned long resize_target;
- int resize_initiated;
};
extern unsigned int fls_ulong(unsigned long x);
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 30+ messages in thread
end of thread, other threads:[~2011-11-28 14:39 UTC | newest]
Thread overview: 30+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-11-28 8:07 [lttng-dev] [PATCH 00/12] rculfhash memory managements Lai Jiangshan
2011-11-28 8:07 ` [lttng-dev] [PATCH 01/12] introduce bucket_at() and improve readability Lai Jiangshan
2011-11-28 13:01 ` Mathieu Desnoyers
2011-11-28 8:07 ` [lttng-dev] [PATCH 02/12] proper wrapper for bucket table alloc and free Lai Jiangshan
2011-11-28 13:02 ` Mathieu Desnoyers
2011-11-28 8:07 ` [lttng-dev] [PATCH 03/12] it is not required that ht->t.size >= ht->min_table_size now Lai Jiangshan
2011-11-28 13:07 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 04/12] remove struct rcu_level Lai Jiangshan
2011-11-28 13:08 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 05/12] rename min_alloc_size/min_alloc_order Lai Jiangshan
2011-11-28 13:14 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 06/12] add max_nr_buckets argument Lai Jiangshan
2011-11-28 13:24 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 07/12] Add rcu_flavor Lai Jiangshan
2011-11-28 13:23 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 08/12] use rcu_flavor for rculfhash Lai Jiangshan
2011-11-28 13:24 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 09/12] remove struct rcu_table Lai Jiangshan
2011-11-28 13:25 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 10/12] move memory management code out as rculfhash-mm-order.c Lai Jiangshan
2011-11-28 13:27 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 11/12] add rculfhash-mm-chunk.c memory management Lai Jiangshan
2011-11-28 13:33 ` Mathieu Desnoyers
2011-11-28 8:08 ` [lttng-dev] [PATCH 12/12] add rculfhash-mm-mmap.c " Lai Jiangshan
2011-11-28 13:43 ` Mathieu Desnoyers
2011-11-28 14:05 ` Lai Jiangshan
2011-11-28 14:15 ` Mathieu Desnoyers
2011-11-28 13:43 ` [lttng-dev] [PATCH 00/12] rculfhash memory managements Mathieu Desnoyers
2011-11-28 14:23 ` Lai Jiangshan
2011-11-28 14:39 ` Mathieu Desnoyers
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox