X-Git-Url: http://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=rculfhash.c;h=d7d107f3788f3a70cec57be5380ae1ff1bbff173;hp=8a8ede7a6cadd1027a2c55c450ac3016f696fa6c;hb=7be759d1adf95b168f09e513232ea26de15e1eaf;hpb=e54ec2f5c366fcf32d9568066c2f2828dd2fe3e7 diff --git a/rculfhash.c b/rculfhash.c index 8a8ede7..d7d107f 100644 --- a/rculfhash.c +++ b/rculfhash.c @@ -117,7 +117,7 @@ * To discuss these guarantees, we first define "read" operation as any * of the the basic cds_lfht_lookup, cds_lfht_next_duplicate, * cds_lfht_first, cds_lfht_next operation, as well as - * cds_lfht_add_unique (failure). + * cds_lfht_add_unique (failure). * * We define "read traversal" operation as any of the following * group of operations @@ -225,12 +225,12 @@ * shrink hash table from order 6 to 5: fini the index=6 bucket node table * * A bit of ascii art explanation: - * + * * The order index is the off-by-one compared to the actual power of 2 * because we use index 0 to deal with the 0 special-case. - * + * * This shows the nodes for a small table ordered by reversed bits: - * + * * bits reverse * 0 000 000 * 4 100 001 @@ -240,10 +240,10 @@ * 5 101 101 * 3 011 110 * 7 111 111 - * - * This shows the nodes in order of non-reversed bits, linked by + * + * This shows the nodes in order of non-reversed bits, linked by * reversed-bit order. - * + * * order bits reverse * 0 0 000 000 * 1 | 1 001 100 <- @@ -264,9 +264,11 @@ #include #include #include +#include #include "config.h" -#include +#include "compat-getcpu.h" +#include #include #include #include @@ -364,7 +366,7 @@ struct partition_resize_work { * Originally from Public Domain. */ -static const uint8_t BitReverseTable256[256] = +static const uint8_t BitReverseTable256[256] = { #define R2(n) (n), (n) + 2*64, (n) + 1*64, (n) + 3*64 #define R4(n) R2(n), R2((n) + 2*16), R2((n) + 1*16), R2((n) + 3*16) @@ -385,21 +387,21 @@ uint8_t bit_reverse_u8(uint8_t v) static uint32_t bit_reverse_u32(uint32_t v) { - return ((uint32_t) bit_reverse_u8(v) << 24) | - ((uint32_t) bit_reverse_u8(v >> 8) << 16) | - ((uint32_t) bit_reverse_u8(v >> 16) << 8) | + return ((uint32_t) bit_reverse_u8(v) << 24) | + ((uint32_t) bit_reverse_u8(v >> 8) << 16) | + ((uint32_t) bit_reverse_u8(v >> 16) << 8) | ((uint32_t) bit_reverse_u8(v >> 24)); } #else static uint64_t bit_reverse_u64(uint64_t v) { - return ((uint64_t) bit_reverse_u8(v) << 56) | - ((uint64_t) bit_reverse_u8(v >> 8) << 48) | + return ((uint64_t) bit_reverse_u8(v) << 56) | + ((uint64_t) bit_reverse_u8(v >> 8) << 48) | ((uint64_t) bit_reverse_u8(v >> 16) << 40) | ((uint64_t) bit_reverse_u8(v >> 24) << 32) | - ((uint64_t) bit_reverse_u8(v >> 32) << 24) | - ((uint64_t) bit_reverse_u8(v >> 40) << 16) | + ((uint64_t) bit_reverse_u8(v >> 32) << 24) | + ((uint64_t) bit_reverse_u8(v >> 40) << 16) | ((uint64_t) bit_reverse_u8(v >> 48) << 8) | ((uint64_t) bit_reverse_u8(v >> 56)); } @@ -426,7 +428,7 @@ unsigned int fls_u32(uint32_t x) { int r; - asm("bsrl %1,%0\n\t" + __asm__ ("bsrl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n\t" "1:\n\t" @@ -442,7 +444,7 @@ unsigned int fls_u64(uint64_t x) { long r; - asm("bsrq %1,%0\n\t" + __asm__ ("bsrq %1,%0\n\t" "jnz 1f\n\t" "movq $-1,%0\n\t" "1:\n\t" @@ -619,26 +621,18 @@ void free_split_items_count(struct cds_lfht *ht) poison_free(ht->split_count); } -#if defined(HAVE_SCHED_GETCPU) static int ht_get_split_count_index(unsigned long hash) { int cpu; assert(split_count_mask >= 0); - cpu = sched_getcpu(); + cpu = urcu_sched_getcpu(); if (caa_unlikely(cpu < 0)) return hash & split_count_mask; else return cpu & split_count_mask; } -#else /* #if defined(HAVE_SCHED_GETCPU) */ -static -int ht_get_split_count_index(unsigned long hash) -{ - return hash & split_count_mask; -} -#endif /* #else #if defined(HAVE_SCHED_GETCPU) */ static void ht_count_add(struct cds_lfht *ht, unsigned long size, unsigned long hash) @@ -1176,6 +1170,10 @@ void partition_resize_helper(struct cds_lfht *ht, unsigned long i, int thread, ret; unsigned long nr_threads; + assert(nr_cpus_mask != -1); + if (nr_cpus_mask < 0 || len < 2 * MIN_PARTITION_PER_THREAD) + goto fallback; + /* * Note: nr_cpus_mask + 1 is always power of 2. * We spawn just the number of threads we need to satisfy the minimum @@ -1268,13 +1266,6 @@ static void init_table_populate(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->flavor->thread_online(); - init_table_populate_partition(ht, i, 0, len); - ht->flavor->thread_offline(); - return; - } partition_resize_helper(ht, i, len, init_table_populate_partition); } @@ -1367,14 +1358,6 @@ void remove_table_partition(struct cds_lfht *ht, unsigned long i, static 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->flavor->thread_online(); - remove_table_partition(ht, i, 0, len); - ht->flavor->thread_offline(); - return; - } partition_resize_helper(ht, i, len, remove_table_partition); } @@ -1397,7 +1380,7 @@ void fini_table(struct cds_lfht *ht, unsigned long len; len = 1UL << (i - 1); - dbg_printf("fini order %lu len: %lu\n", i, len); + dbg_printf("fini order %ld len: %lu\n", i, len); /* Stop shrink if the resize target changes under us */ if (CMM_LOAD_SHARED(ht->resize_target) > (1UL << (i - 1))) @@ -1816,6 +1799,9 @@ int cds_lfht_destroy(struct cds_lfht *ht, pthread_attr_t **attr) free_split_items_count(ht); if (attr) *attr = ht->resize_attr; + ret = pthread_mutex_destroy(&ht->resize_mutex); + if (ret) + ret = -EBUSY; poison_free(ht); end: return ret;