[lttng-ust.git] / liblttng-ust / rculfhash-internal.h

/*
 * SPDX-License-Identifier: LGPL-2.1-or-later
 *
 * Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
 * Copyright 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
 *
 * Internal header for Lock-Free RCU Hash Table
 */

#ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H
#define _LTTNG_UST_RCULFHASH_INTERNAL_H

#include "rculfhash.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "helper.h"

#ifdef DEBUG
#define dbg_printf(fmt, args...)     printf("[debug lttng-ust rculfhash] " fmt, ## args)
#else
#define dbg_printf(fmt, args...)				\
do {								\
	/* do nothing but check printf format */		\
	if (0)							\
		printf("[debug lttng-ust rculfhash] " fmt, ## args);	\
} while (0)
#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

/*
 * lttng_ust_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 lttng_ust_lfht {
	/* Initial configuration items */
	unsigned long max_nr_buckets;
	const struct lttng_ust_lfht_mm_type *mm;	/* memory management plugin */
	const struct rcu_flavor_struct *flavor;	/* RCU flavor */

	/*
	 * 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 */
	unsigned int 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;

	/*
	 * 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 lttng_ust_lfht_node *(*bucket_at)(struct lttng_ust_lfht *ht,
			unsigned long index);
	/*
	 * Dynamic length "tbl_chunk" needs to be at the end of
	 * lttng_ust_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 lttng_ust_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 lttng_ust_lfht_node *tbl_chunk[0];

		/*
		 * Memory mapping with room for all possible buckets.
		 * Their memory is allocated when needed.
		 */
		struct lttng_ust_lfht_node *tbl_mmap;
	};
	/*
	 * End of variables needed for the lookup, add and remove
	 * fast-paths.
	 */
};

LTTNG_HIDDEN
extern unsigned int lttng_ust_lfht_fls_ulong(unsigned long x);
LTTNG_HIDDEN
extern int lttng_ust_lfht_get_count_order_u32(uint32_t x);
LTTNG_HIDDEN
extern int lttng_ust_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 lttng_ust_lfht *__default_alloc_lttng_ust_lfht(
		const struct lttng_ust_lfht_mm_type *mm,
		unsigned long lttng_ust_lfht_size,
		unsigned long min_nr_alloc_buckets,
		unsigned long max_nr_buckets)
{
	struct lttng_ust_lfht *ht;

	ht = calloc(1, lttng_ust_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 =
		lttng_ust_lfht_get_count_order_ulong(min_nr_alloc_buckets);
	ht->max_nr_buckets = max_nr_buckets;

	return ht;
}

#endif /* _LTTNG_UST_RCULFHASH_INTERNAL_H */
Commit	Line	Data
10544ee8	1	/*
c0c0989a	2	* SPDX-License-Identifier: LGPL-2.1-or-later
10544ee8	3	*
c0c0989a MJ	4	* Copyright 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
c0c0989a MJ	5	* Copyright 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
10544ee8	6	*
c0c0989a	7	* Internal header for Lock-Free RCU Hash Table
10544ee8 MD	8	*/
10544ee8 MD	9
c0c0989a MJ	10	#ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H
	11	#define _LTTNG_UST_RCULFHASH_INTERNAL_H
	12
10544ee8 MD	13	#include "rculfhash.h"
	14	#include <stdio.h>
	15	#include <stdlib.h>
	16	#include <assert.h>
d2dd7baa	17	#include "helper.h"
10544ee8 MD	18
	19	#ifdef DEBUG
	20	#define dbg_printf(fmt, args...) printf("[debug lttng-ust rculfhash] " fmt, ## args)
	21	#else
	22	#define dbg_printf(fmt, args...) \
	23	do { \
	24	/* do nothing but check printf format */ \
	25	if (0) \
	26	printf("[debug lttng-ust rculfhash] " fmt, ## args); \
	27	} while (0)
	28	#endif
	29
	30	#if (CAA_BITS_PER_LONG == 32)
	31	#define MAX_TABLE_ORDER 32
	32	#else
	33	#define MAX_TABLE_ORDER 64
	34	#endif
	35
	36	#define MAX_CHUNK_TABLE (1UL << 10)
	37
	38	#ifndef min
	39	#define min(a, b) ((a) < (b) ? (a) : (b))
	40	#endif
	41
	42	#ifndef max
	43	#define max(a, b) ((a) > (b) ? (a) : (b))
	44	#endif
	45
	46	/*
	47	* lttng_ust_lfht: Top-level data structure representing a lock-free hash
	48	* table. Defined in the implementation file to make it be an opaque
	49	* cookie to users.
	50	*
	51	* The fields used in fast-paths are placed near the end of the
	52	* structure, because we need to have a variable-sized union to contain
	53	* the mm plugin fields, which are used in the fast path.
	54	*/
	55	struct lttng_ust_lfht {
	56	/* Initial configuration items */
	57	unsigned long max_nr_buckets;
	58	const struct lttng_ust_lfht_mm_type mm; / memory management plugin */
	59	const struct rcu_flavor_struct flavor; / RCU flavor */
	60
	61	/*
	62	* We need to put the work threads offline (QSBR) when taking this
	63	* mutex, because we use synchronize_rcu within this mutex critical
	64	* section, which waits on read-side critical sections, and could
	65	* therefore cause grace-period deadlock if we hold off RCU G.P.
	66	* completion.
	67	*/
	68	pthread_mutex_t resize_mutex; /* resize mutex: add/del mutex */
	69	unsigned int in_progress_destroy;
	70	unsigned long resize_target;
	71	int resize_initiated;
	72
	73	/*
	74	* Variables needed for add and remove fast-paths.
	75	*/
	76	int flags;
	77	unsigned long min_alloc_buckets_order;
	78	unsigned long min_nr_alloc_buckets;
	79
	80	/*
	81	* Variables needed for the lookup, add and remove fast-paths.
82	*/
83	unsigned long size; /* always a power of 2, shared (RCU) */
84	/*
85	* bucket_at pointer is kept here to skip the extra level of
86	* dereference needed to get to "mm" (this is a fast-path).
87	*/
88	struct lttng_ust_lfht_node (bucket_at)(struct lttng_ust_lfht *ht,
89	unsigned long index);
90	/*
91	* Dynamic length "tbl_chunk" needs to be at the end of
92	* lttng_ust_lfht.
93	*/
94	union {
95	/*
96	* Contains the per order-index-level bucket node table.
97	* The size of each bucket node table is half the number
98	* of hashes contained in this order (except for order 0).
99	* The minimum allocation buckets size parameter allows
100	* combining the bucket node arrays of the lowermost
101	* levels to improve cache locality for small index orders.
102	*/
103	struct lttng_ust_lfht_node *tbl_order[MAX_TABLE_ORDER];
104
105	/*
106	* Contains the bucket node chunks. The size of each
107	* bucket node chunk is ->min_alloc_size (we avoid to
108	* allocate chunks with different size). Chunks improve
109	* cache locality for small index orders, and are more
110	* friendly with environments where allocation of large
111	* contiguous memory areas is challenging due to memory
112	* fragmentation concerns or inability to use virtual
113	* memory addressing.
114	*/
115	struct lttng_ust_lfht_node *tbl_chunk[0];
116
117	/*
118	* Memory mapping with room for all possible buckets.
119	* Their memory is allocated when needed.
120	*/
121	struct lttng_ust_lfht_node *tbl_mmap;
122	};
123	/*
124	* End of variables needed for the lookup, add and remove
125	* fast-paths.
126	*/
127	};
128
d2dd7baa	129	LTTNG_HIDDEN
10544ee8	130	extern unsigned int lttng_ust_lfht_fls_ulong(unsigned long x);
d2dd7baa MJ	131	LTTNG_HIDDEN
	132	extern int lttng_ust_lfht_get_count_order_u32(uint32_t x);
	133	LTTNG_HIDDEN
10544ee8 MD	134	extern int lttng_ust_lfht_get_count_order_ulong(unsigned long x);
	135
	136	#ifdef POISON_FREE
	137	#define poison_free(ptr) \
	138	do { \
	139	if (ptr) { \
	140	memset(ptr, 0x42, sizeof(*(ptr))); \
	141	free(ptr); \
	142	} \
	143	} while (0)
	144	#else
	145	#define poison_free(ptr) free(ptr)
	146	#endif
	147
	148	static inline
	149	struct lttng_ust_lfht *__default_alloc_lttng_ust_lfht(
	150	const struct lttng_ust_lfht_mm_type *mm,
	151	unsigned long lttng_ust_lfht_size,
	152	unsigned long min_nr_alloc_buckets,
	153	unsigned long max_nr_buckets)
	154	{
	155	struct lttng_ust_lfht *ht;
	156
	157	ht = calloc(1, lttng_ust_lfht_size);
	158	assert(ht);
	159
	160	ht->mm = mm;
	161	ht->bucket_at = mm->bucket_at;
	162	ht->min_nr_alloc_buckets = min_nr_alloc_buckets;
	163	ht->min_alloc_buckets_order =
	164	lttng_ust_lfht_get_count_order_ulong(min_nr_alloc_buckets);
	165	ht->max_nr_buckets = max_nr_buckets;
	166
	167	return ht;
	168	}
	169
	170	#endif /* _LTTNG_UST_RCULFHASH_INTERNAL_H */