X-Git-Url: https://git.liburcu.org/?a=blobdiff_plain;ds=sidebyside;f=rculfhash.c;h=4a611a1718451f229d03ea8d7ea5800b18b633dd;hb=747d725c1dd45d5072e0e411642c4d5c6403b4be;hp=807191593c6e7d7671b7ca6f236657771a7d3f32;hpb=d0d8f9aa03e9df3ca61b8c823678e5c3a9640a4d;p=urcu.git diff --git a/rculfhash.c b/rculfhash.c index 8071915..4a611a1 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -238,28 +238,24 @@ struct ht_items_count { unsigned long add, del; } __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]; }; /* @@ -269,8 +265,9 @@ 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; + unsigned long max_nr_buckets; int flags; /* * We need to put the work threads offline (QSBR) when taking this @@ -761,15 +758,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 */ } /* @@ -782,9 +779,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 @@ -793,9 +790,9 @@ 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]->nodes[index]; + return &ht->t.tbl[0][index]; } /* * equivalent to get_count_order_ulong(index + 1), but optimizes @@ -805,7 +802,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 @@ -1368,7 +1365,8 @@ 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, + unsigned long max_nr_buckets, int flags, void (*cds_lfht_call_rcu)(struct rcu_head *head, void (*func)(struct rcu_head *head)), @@ -1384,14 +1382,25 @@ 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); + + 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; @@ -1409,8 +1418,9 @@ 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); + ht->max_nr_buckets = max_nr_buckets; cds_lfht_create_bucket(ht, 1UL << order); ht->t.size = 1UL << order; return ht; @@ -1770,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); } @@ -1827,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; @@ -1845,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 */