X-Git-Url: https://git.lttng.org/?p=lttng-tools.git;a=blobdiff_plain;f=liblttng-ht%2Frculfhash-internal.h;fp=liblttng-ht%2Frculfhash-internal.h;h=cb13ffa73f773486d77dca0a9fcb5407a8202356;hp=0000000000000000000000000000000000000000;hb=bec399405a4667411ae06bbbcbed678e42e93a30;hpb=67cea2c94b841ee9b38ba80ab8a9eafff5f76408 diff --git a/liblttng-ht/rculfhash-internal.h b/liblttng-ht/rculfhash-internal.h new file mode 100644 index 000000000..cb13ffa73 --- /dev/null +++ b/liblttng-ht/rculfhash-internal.h @@ -0,0 +1,177 @@ +#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 + * Copyright 2011 - Lai Jiangshan + * + * 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.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 + +#define MAX_CHUNK_TABLE (1UL << 10) + +#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. + * + * 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. + * 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]; + + /* + * 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]; + + /* + * Memory mapping with room for all possible buckets. + * Their memory is allocated when needed. + */ + struct cds_lfht_node *tbl_mmap; + }; + /* + * End of variables needed for the lookup, add and remove + * fast-paths. + */ +}; + +extern unsigned int cds_lfht_fls_ulong(unsigned long x); +extern int cds_lfht_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 + +static inline +struct cds_lfht *__default_alloc_cds_lfht( + const struct cds_lfht_mm_type *mm, + unsigned long cds_lfht_size, + unsigned long min_nr_alloc_buckets, + unsigned long max_nr_buckets) +{ + struct cds_lfht *ht; + + ht = calloc(1, cds_lfht_size); + assert(ht); + + ht->mm = mm; + ht->bucket_at = mm->bucket_at; + ht->min_nr_alloc_buckets = min_nr_alloc_buckets; + ht->min_alloc_buckets_order = + cds_lfht_get_count_order_ulong(min_nr_alloc_buckets); + ht->max_nr_buckets = max_nr_buckets; + + return ht; +} + +#endif /* _URCU_RCULFHASH_INTERNAL_H */