uatomic/x86: Remove redundant memory barriers

[urcu.git] / src / rculfhash-internal.h

// SPDX-FileCopyrightText: 2011 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
// SPDX-FileCopyrightText: 2011 Lai Jiangshan <laijs@cn.fujitsu.com>
//
// SPDX-License-Identifier: LGPL-2.1-or-later

#ifndef _URCU_RCULFHASH_INTERNAL_H
#define _URCU_RCULFHASH_INTERNAL_H

/*
 * Internal header for Lock-Free RCU Hash Table
 */

#include <urcu/assert.h>
#include <urcu/rculfhash.h>
#include <stdio.h>
#include <stdlib.h>

#include "workqueue.h"

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

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 cds_lfht_alloc *alloc;	/* memory allocator for mm */
	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 *caller_resize_attr;	/* resize threads attributes from lfht_new caller */
	pthread_attr_t resize_attr;
	unsigned int in_progress_destroy;
	unsigned long resize_target;
	int resize_initiated;
	struct urcu_work destroy_work;

	/*
	 * 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(alloc, ptr)					\
	do {							\
		if (ptr) {					\
			memset(ptr, 0x42, sizeof(*(ptr)));	\
			alloc->free(alloc->state, ptr);				\
		}						\
	} while (0)
#else
#define poison_free(alloc, ptr)	alloc->free(alloc->state, ptr)
#endif

static inline
struct cds_lfht *__default_alloc_cds_lfht(
		const struct cds_lfht_mm_type *mm,
		const struct cds_lfht_alloc *alloc,
		unsigned long cds_lfht_size,
		unsigned long min_nr_alloc_buckets,
		unsigned long max_nr_buckets)
{
	struct cds_lfht *ht;

	ht = alloc->calloc(alloc->state, 1, cds_lfht_size);
	urcu_posix_assert(ht);

	ht->mm = mm;
	ht->alloc = alloc;
	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 */