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

#ifndef _LTTNG_UST_RCULFHASH_INTERNAL_H
#define _LTTNG_UST_RCULFHASH_INTERNAL_H

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