Commit | Line | Data |
---|---|---|
acdb82a2 MJ |
1 | // SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> |
2 | // SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com> | |
3 | // | |
4 | // SPDX-License-Identifier: LGPL-2.1-or-later | |
5 | ||
0b6aa001 | 6 | /* |
0b6aa001 | 7 | * Order based memory management for Lock-Free RCU Hash Table |
0b6aa001 LJ |
8 | */ |
9 | ||
01477510 | 10 | #include <urcu/assert.h> |
0d0409b1 | 11 | #include "rculfhash-internal.h" |
0b6aa001 LJ |
12 | |
13 | static | |
14 | void cds_lfht_alloc_bucket_table(struct cds_lfht *ht, unsigned long order) | |
15 | { | |
16 | if (order == 0) { | |
ac735254 XF |
17 | ht->tbl_order[0] = ht->alloc->calloc(ht->alloc->state, |
18 | ht->min_nr_alloc_buckets, sizeof(struct cds_lfht_node)); | |
01477510 | 19 | urcu_posix_assert(ht->tbl_order[0]); |
0b6aa001 | 20 | } else if (order > ht->min_alloc_buckets_order) { |
ac735254 XF |
21 | ht->tbl_order[order] = ht->alloc->calloc(ht->alloc->state, |
22 | 1UL << (order -1), sizeof(struct cds_lfht_node)); | |
01477510 | 23 | urcu_posix_assert(ht->tbl_order[order]); |
0b6aa001 LJ |
24 | } |
25 | /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ | |
26 | } | |
27 | ||
28 | /* | |
29 | * cds_lfht_free_bucket_table() should be called with decreasing order. | |
30 | * When cds_lfht_free_bucket_table(0) is called, it means the whole | |
31 | * lfht is destroyed. | |
32 | */ | |
33 | static | |
34 | void cds_lfht_free_bucket_table(struct cds_lfht *ht, unsigned long order) | |
35 | { | |
36 | if (order == 0) | |
ac735254 | 37 | poison_free(ht->alloc, ht->tbl_order[0]); |
0b6aa001 | 38 | else if (order > ht->min_alloc_buckets_order) |
ac735254 | 39 | poison_free(ht->alloc, ht->tbl_order[order]); |
0b6aa001 LJ |
40 | /* Nothing to do for 0 < order && order <= ht->min_alloc_buckets_order */ |
41 | } | |
42 | ||
43 | static | |
44 | struct cds_lfht_node *bucket_at(struct cds_lfht *ht, unsigned long index) | |
45 | { | |
46 | unsigned long order; | |
47 | ||
48 | if (index < ht->min_nr_alloc_buckets) { | |
49 | dbg_printf("bucket index %lu order 0 aridx 0\n", index); | |
50 | return &ht->tbl_order[0][index]; | |
51 | } | |
52 | /* | |
5bc6b66f MD |
53 | * equivalent to cds_lfht_get_count_order_ulong(index + 1), but |
54 | * optimizes away the non-existing 0 special-case for | |
55 | * cds_lfht_get_count_order_ulong. | |
0b6aa001 | 56 | */ |
5bc6b66f | 57 | order = cds_lfht_fls_ulong(index); |
0b6aa001 LJ |
58 | dbg_printf("bucket index %lu order %lu aridx %lu\n", |
59 | index, order, index & ((1UL << (order - 1)) - 1)); | |
60 | return &ht->tbl_order[order][index & ((1UL << (order - 1)) - 1)]; | |
61 | } | |
62 | ||
63 | static | |
64 | struct cds_lfht *alloc_cds_lfht(unsigned long min_nr_alloc_buckets, | |
ac735254 | 65 | unsigned long max_nr_buckets, const struct cds_lfht_alloc *alloc) |
0b6aa001 | 66 | { |
1228af1c | 67 | return __default_alloc_cds_lfht( |
ac735254 | 68 | &cds_lfht_mm_order, alloc, sizeof(struct cds_lfht), |
1228af1c | 69 | min_nr_alloc_buckets, max_nr_buckets); |
0b6aa001 LJ |
70 | } |
71 | ||
72 | const struct cds_lfht_mm_type cds_lfht_mm_order = { | |
73 | .alloc_cds_lfht = alloc_cds_lfht, | |
74 | .alloc_bucket_table = cds_lfht_alloc_bucket_table, | |
75 | .free_bucket_table = cds_lfht_free_bucket_table, | |
76 | .bucket_at = bucket_at, | |
77 | }; |