> On 10. 7. 2025, at 16:05, Mathieu Desnoyers <mathieu.desnoy...@efficios.com>
> wrote:
>
> On 2025-07-09 14:57, Ondřej Surý via lttng-dev wrote:
>> Hi,
>> as the answer to this might be useful to more people, I am asking here:
>> The cds_lfht_new documentation specifies 3 sizes.
>> * cds_lfht_new - allocate a hash table.
>> * @init_size: number of buckets to allocate initially. Must be power of two.
>> * @min_nr_alloc_buckets: the minimum number of allocated buckets.
>> * (must be power of two)
>> * @max_nr_buckets: the maximum number of hash table buckets allowed.
>> * (must be power of two, 0 is accepted, means
>> * "infinite")
>> The max number of buckets is obvious, but the interaction between init
>> and min is confusing.
>> If I am reading the code right, then init_size < min_nr_alloc_buckets have no
>> effect, the buckets table will be at least 1 << min_nr_alloc_buckets.
>
> You are correct that the documentation of interaction between init_size
> and min_nr_alloc_buckets should be improved. Especially the semantic
> of "allocated" vs "initialized" buckets.
>
> Re-reading the code, here is my understanding:
>
> - The init_size parameter is responsible for initializing a certain
> number of buckets at hash table creation (during the call to
> cds_lfht_new()) and for setting an initial resize target to the
> init_size value. It allocates the buckets memory _and_ chains
> those buckets into the hash table.
>
> - The min_nr_alloc_buckets only acts as a lower bound below which
> the hash table resize algorithm won't free the _memory_ used for
> buckets below that threshold and will keep the buckets allocated even
> when the hash table size shrinks. It does not affect the fact buckets
> are unlinked from the hash table when it shrinks below that threshold
> though, it only keeps their memory allocated.
>
> This parameter only applies when an explicit cds_lfht_resize,
> cds_lfht_resize_lazy_count are done, or when the hash table is
> created with the CDS_LFHT_AUTO_RESIZE flag.
>
> So my understanding does not match yours. In case I missed something,
> what is leading you conclude that the
> "buckets table will be at least 1 << min_nr_alloc_buckets"
> at hash table creation when init_size < min_nr_alloc_buckets ?
It's not so obvious from the mmap implementation, but the mm-order has:
static
void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order)
{
if (order == 0) {
ht->tbl_order[0] = ht->alloc->calloc(ht->alloc->state,
ht->min_nr_alloc_buckets, sizeof(struct cds_lfht_node));
urcu_posix_assert(ht->tbl_order[0]);
} else if (order > ht->min_alloc_buckets_order) {
ht->tbl_order[order] = ht->alloc->calloc(ht->alloc->state,
1UL << (order -1), sizeof(struct cds_lfht_node));
urcu_posix_assert(ht->tbl_order[order]);
}
/* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order
*/
}
Similar code is in the mm-chunk. The mmap allocates largest mmap and then it
marks
the pages as needed, so it is bit hidden behind mmap semantics, but it also
populates
min_nr_alloc_buckets:
/* 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));
and cds_lfht_alloc_bucket_table(..., 0) is called when initializing the from
cds_lfht_new(),
so my assumption was that the buckets table is .tbl_<impl> and that's always at
least
min_nr_alloc_buckets large.
The loop in cds_lfht_create_bucket() then does not change the underlying table
size,
but it doesn't initialize buckets for orders > init size & < min_nr_alloc_size.
>> But what happens if init_size > min_nr_alloc_buckets? It feels like it will
>> work
>> as expected if you pre-populate the table, but if you use it "normally",
>> e.g. there
>> could be single add / del, the table will shrink immediately.
>
> In that case, cds_lfht_new would allocate and initialize buckets based
> on init_size, and set an initial resize_target value based on init_size.
>
> For a hash table created with the CDS_LFHT_AUTO_RESIZE flag, indeed if
> the init_size > min_nr_alloc_buckets, doing a add/del will indeed
> trigger a hash table auto-resize, which will unlink and free buckets
> between min_nr_alloc_buckets and init_size, and will just unlink buckets
> (not free memory) below min_nr_alloc_buckets.
>
> So it does not make much sense to have a large init_size value for an
> auto-resize hash table, because it will very undo initialization
> and allocation soon after creation when the first items are added
> and removed.
However, it could make sense to have init_size smaller than min_nr_alloc_size
to make the bucket initialization deferred, but until we reach min_nr... the
table
will never auto-shrink.
> For a hash table created without auto-resize, then the behavior depends
> on the explicit resizes done with cds_lfht_resize,
> cds_lfht_resize_lazy_grow, and cds_lfht_resize_lazy_count, so it makes
> more sense to have a larger init_size value (even larger than
> min_nr_alloc_buckets).
>
> Does this explanation help ?
Absolutely, I was also thinking inside the CDS_LFHT_AUTO_RESIZE flag
because it is ubiquitous in our code and you made me realize that the resizes
could be done automatically.
Ondrej
--
Ondřej Surý (He/Him)
ond...@sury.org
