#include <sys/cdefs.h>
#include "opt_ddb.h"
#include <sys/param.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/pctrie.h>
#include <sys/proc.h>
#include <sys/smr.h>
#include <sys/smr_types.h>

Include dependency graph for subr_pctrie.c:

Macros
#define	PCTRIE_MASK (PCTRIE_COUNT - 1)

#define	PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1)

#define	PCTRIE_ISLEAF 0x1

#define	PCTRIE_FLAGS 0x1

#define	PCTRIE_PAD PCTRIE_FLAGS

#define	PCTRIE_UNITLEVEL(lev) ((uint64_t)1 << ((lev) * PCTRIE_WIDTH))

Enumerations
enum	pctrie_access { PCTRIE_SMR , PCTRIE_LOCKED , PCTRIE_UNSERIALIZED }

Functions
	__FBSDID ("$FreeBSD$")

typedef	SMR_POINTER (struct pctrie_node *)

static __inline void	pctrie_node_store (smr_pctnode_t p, void val, enum pctrie_access access)

static struct pctrie_node *	pctrie_node_get (struct pctrie *ptree, pctrie_alloc_t allocfn, uint64_t owner, uint16_t count, uint16_t clevel)

static __inline void	pctrie_node_put (struct pctrie ptree, struct pctrie_node node, pctrie_free_t freefn, int8_t last)

static __inline int	pctrie_slot (uint64_t index, uint16_t level)

static __inline uint64_t	pctrie_trimkey (uint64_t index, uint16_t level)

static __inline struct pctrie_node *	pctrie_node_load (smr_pctnode_t *p, smr_t smr, enum pctrie_access access)

static __inline struct pctrie_node *	pctrie_root_load (struct pctrie *ptree, smr_t smr, enum pctrie_access access)

static __inline void	pctrie_root_store (struct pctrie ptree, struct pctrie_node node, enum pctrie_access access)

static __inline bool	pctrie_isleaf (struct pctrie_node *node)

static __inline uint64_t *	pctrie_toval (struct pctrie_node *node)

static __inline void	pctrie_addval (struct pctrie_node node, uint64_t index, uint16_t clev, uint64_t val, enum pctrie_access access)

static __inline uint16_t	pctrie_keydiff (uint64_t index1, uint64_t index2)

static __inline bool	pctrie_keybarr (struct pctrie_node *node, uint64_t idx)

static void	pctrie_reclaim_allnodes_int (struct pctrie ptree, struct pctrie_node node, pctrie_free_t freefn)

int	pctrie_zone_init (void *mem, int size __unused, int flags __unused)

size_t	pctrie_node_size (void)

int	pctrie_insert (struct pctrie ptree, uint64_t val, pctrie_alloc_t allocfn)

static __always_inline uint64_t *	_pctrie_lookup (struct pctrie *ptree, uint64_t index, smr_t smr, enum pctrie_access access)

uint64_t *	pctrie_lookup (struct pctrie *ptree, uint64_t index)

uint64_t *	pctrie_lookup_unlocked (struct pctrie *ptree, uint64_t index, smr_t smr)

uint64_t *	pctrie_lookup_ge (struct pctrie *ptree, uint64_t index)

uint64_t *	pctrie_lookup_le (struct pctrie *ptree, uint64_t index)

void	pctrie_remove (struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)

void	pctrie_reclaim_allnodes (struct pctrie *ptree, pctrie_free_t freefn)

Macro Definition Documentation

◆ PCTRIE_FLAGS

#define PCTRIE_FLAGS 0x1

Definition at line 71 of file subr_pctrie.c.

◆ PCTRIE_ISLEAF

#define PCTRIE_ISLEAF 0x1

Definition at line 70 of file subr_pctrie.c.

◆ PCTRIE_LIMIT

#define PCTRIE_LIMIT (howmany(sizeof(uint64_t) * NBBY, PCTRIE_WIDTH) - 1)

Definition at line 67 of file subr_pctrie.c.

◆ PCTRIE_MASK

#define PCTRIE_MASK (PCTRIE_COUNT - 1)

Definition at line 66 of file subr_pctrie.c.

◆ PCTRIE_PAD

#define PCTRIE_PAD PCTRIE_FLAGS

Definition at line 72 of file subr_pctrie.c.

◆ PCTRIE_UNITLEVEL

#define PCTRIE_UNITLEVEL ( lev ) ((uint64_t)1 << ((lev) * PCTRIE_WIDTH))

Definition at line 75 of file subr_pctrie.c.

Enumeration Type Documentation

◆ pctrie_access

enum pctrie_access

Enumerator
PCTRIE_SMR
PCTRIE_LOCKED
PCTRIE_UNSERIALIZED

Definition at line 89 of file subr_pctrie.c.

Function Documentation

◆ __FBSDID()

__FBSDID ( "$FreeBSD$" )

◆ _pctrie_lookup()

static __always_inline uint64_t * _pctrie_lookup	(	struct pctrie *	ptree,
		uint64_t	index,
		smr_t	smr,
		enum pctrie_access	access
	)

static

Definition at line 426 of file subr_pctrie.c.

References pctrie_isleaf(), pctrie_keybarr(), pctrie_node_load(), pctrie_root_load(), pctrie_slot(), and pctrie_toval().

Referenced by pctrie_lookup(), and pctrie_lookup_unlocked().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_addval()

static __inline void pctrie_addval	(	struct pctrie_node *	node,
		uint64_t	index,
		uint16_t	clev,
		uint64_t *	val,
		enum pctrie_access	access
	)

static

Definition at line 251 of file subr_pctrie.c.

References PCTRIE_ISLEAF, pctrie_node_store(), and pctrie_slot().

Referenced by pctrie_insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_insert()

int pctrie_insert	(	struct pctrie *	ptree,
		uint64_t *	val,
		pctrie_alloc_t	allocfn
	)

Definition at line 347 of file subr_pctrie.c.

References panic(), pctrie_addval(), PCTRIE_ISLEAF, pctrie_isleaf(), pctrie_keybarr(), pctrie_keydiff(), PCTRIE_LOCKED, pctrie_node_get(), pctrie_node_load(), pctrie_node_store(), pctrie_root_load(), pctrie_slot(), pctrie_toval(), pctrie_trimkey(), and PCTRIE_UNSERIALIZED.

Referenced by rangeset_copy(), rangeset_insert(), and rangeset_remove_pred().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_isleaf()

static __inline bool pctrie_isleaf ( struct pctrie_node * node )

static

Definition at line 231 of file subr_pctrie.c.

References PCTRIE_ISLEAF.

Referenced by _pctrie_lookup(), pctrie_insert(), pctrie_lookup_ge(), pctrie_lookup_le(), pctrie_reclaim_allnodes(), pctrie_reclaim_allnodes_int(), and pctrie_remove().

Here is the caller graph for this function:

◆ pctrie_keybarr()

static __inline bool pctrie_keybarr	(	struct pctrie_node *	node,
		uint64_t	idx
	)

static

Definition at line 284 of file subr_pctrie.c.

References PCTRIE_LIMIT, and pctrie_trimkey().

Referenced by _pctrie_lookup(), pctrie_insert(), pctrie_lookup_ge(), and pctrie_lookup_le().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_keydiff()

static __inline uint16_t pctrie_keydiff	(	uint64_t	index1,
		uint64_t	index2
	)

static

Definition at line 266 of file subr_pctrie.c.

References PCTRIE_LIMIT, and pctrie_slot().

Referenced by pctrie_insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_lookup()

uint64_t * pctrie_lookup	(	struct pctrie *	ptree,
		uint64_t	index
	)

Definition at line 456 of file subr_pctrie.c.

References _pctrie_lookup(), and PCTRIE_LOCKED.

Here is the call graph for this function:

◆ pctrie_lookup_ge()

uint64_t * pctrie_lookup_ge	(	struct pctrie *	ptree,
		uint64_t	index
	)

Definition at line 482 of file subr_pctrie.c.

References child, pctrie_isleaf(), pctrie_keybarr(), PCTRIE_LIMIT, PCTRIE_LOCKED, pctrie_node_load(), pctrie_root_load(), pctrie_slot(), pctrie_toval(), pctrie_trimkey(), and PCTRIE_UNITLEVEL.

Referenced by rangeset_copy(), and rangeset_remove_all().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_lookup_le()

uint64_t * pctrie_lookup_le	(	struct pctrie *	ptree,
		uint64_t	index
	)

Definition at line 597 of file subr_pctrie.c.

References child, pctrie_isleaf(), pctrie_keybarr(), PCTRIE_LIMIT, PCTRIE_LOCKED, pctrie_node_load(), pctrie_root_load(), pctrie_slot(), pctrie_toval(), pctrie_trimkey(), and PCTRIE_UNITLEVEL.

Referenced by rangeset_check_empty(), rangeset_lookup(), and rangeset_remove_pred().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_lookup_unlocked()

uint64_t * pctrie_lookup_unlocked	(	struct pctrie *	ptree,
		uint64_t	index,
		smr_t	smr
	)

Definition at line 467 of file subr_pctrie.c.

References _pctrie_lookup(), PCTRIE_SMR, and res.

Here is the call graph for this function:

◆ pctrie_node_get()

static struct pctrie_node * pctrie_node_get	(	struct pctrie *	ptree,
		pctrie_alloc_t	allocfn,
		uint64_t	owner,
		uint16_t	count,
		uint16_t	clevel
	)

static

Definition at line 99 of file subr_pctrie.c.

References count, pctrie_node_store(), and PCTRIE_UNSERIALIZED.

Referenced by pctrie_insert().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_node_load()

static __inline struct pctrie_node * pctrie_node_load	(	smr_pctnode_t *	p,
		smr_t	smr,
		enum pctrie_access	access
	)

static

Definition at line 176 of file subr_pctrie.c.

References PCTRIE_LOCKED, PCTRIE_SMR, and PCTRIE_UNSERIALIZED.

Referenced by _pctrie_lookup(), pctrie_insert(), pctrie_lookup_ge(), pctrie_lookup_le(), pctrie_reclaim_allnodes_int(), pctrie_remove(), and pctrie_root_load().

Here is the caller graph for this function:

◆ pctrie_node_put()

static __inline void pctrie_node_put	(	struct pctrie *	ptree,
		struct pctrie_node *	node,
		pctrie_free_t	freefn,
		int8_t	last
	)

static

Definition at line 128 of file subr_pctrie.c.

Referenced by pctrie_reclaim_allnodes_int(), and pctrie_remove().

Here is the caller graph for this function:

◆ pctrie_node_size()

size_t pctrie_node_size ( void )

Definition at line 336 of file subr_pctrie.c.

Referenced by rs_rangeset_init(), and vntblinit().

Here is the caller graph for this function:

◆ pctrie_node_store()

static __inline void pctrie_node_store	(	smr_pctnode_t *	p,
		void *	val,
		enum pctrie_access	access
	)

static

Definition at line 190 of file subr_pctrie.c.

References panic(), PCTRIE_LOCKED, PCTRIE_SMR, and PCTRIE_UNSERIALIZED.

Referenced by pctrie_addval(), pctrie_insert(), pctrie_node_get(), pctrie_reclaim_allnodes_int(), pctrie_remove(), and pctrie_root_store().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_reclaim_allnodes()

void pctrie_reclaim_allnodes	(	struct pctrie *	ptree,
		pctrie_free_t	freefn
	)

Definition at line 782 of file subr_pctrie.c.

References pctrie_isleaf(), PCTRIE_LOCKED, pctrie_reclaim_allnodes_int(), pctrie_root_load(), pctrie_root_store(), and PCTRIE_UNSERIALIZED.

Here is the call graph for this function:

◆ pctrie_reclaim_allnodes_int()

static void pctrie_reclaim_allnodes_int	(	struct pctrie *	ptree,
		struct pctrie_node *	node,
		pctrie_free_t	freefn
	)

static

Definition at line 299 of file subr_pctrie.c.

References child, pctrie_isleaf(), pctrie_node_load(), pctrie_node_put(), pctrie_node_store(), pctrie_reclaim_allnodes_int(), and PCTRIE_UNSERIALIZED.

Referenced by pctrie_reclaim_allnodes(), and pctrie_reclaim_allnodes_int().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_remove()

void pctrie_remove	(	struct pctrie *	ptree,
		uint64_t	index,
		pctrie_free_t	freefn
	)

Definition at line 714 of file subr_pctrie.c.

References panic(), parent, pctrie_isleaf(), PCTRIE_LOCKED, pctrie_node_load(), pctrie_node_put(), pctrie_node_store(), pctrie_root_load(), pctrie_root_store(), pctrie_slot(), and pctrie_toval().

Referenced by rangeset_remove_all(), and rangeset_remove_pred().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_root_load()

static __inline struct pctrie_node * pctrie_root_load	(	struct pctrie *	ptree,
		smr_t	smr,
		enum pctrie_access	access
	)

static

Definition at line 212 of file subr_pctrie.c.

References pctrie_node_load().

Referenced by _pctrie_lookup(), pctrie_insert(), pctrie_lookup_ge(), pctrie_lookup_le(), pctrie_reclaim_allnodes(), and pctrie_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_root_store()

static __inline void pctrie_root_store	(	struct pctrie *	ptree,
		struct pctrie_node *	node,
		enum pctrie_access	access
	)

static

Definition at line 221 of file subr_pctrie.c.

References pctrie_node_store().

Referenced by pctrie_reclaim_allnodes(), and pctrie_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ pctrie_slot()

static __inline int pctrie_slot	(	uint64_t	index,
		uint16_t	level
	)

static

Definition at line 152 of file subr_pctrie.c.

References level, and PCTRIE_MASK.

Referenced by _pctrie_lookup(), pctrie_addval(), pctrie_insert(), pctrie_keydiff(), pctrie_lookup_ge(), pctrie_lookup_le(), and pctrie_remove().

Here is the caller graph for this function:

◆ pctrie_toval()

static __inline uint64_t * pctrie_toval ( struct pctrie_node * node )

static

Definition at line 241 of file subr_pctrie.c.

References PCTRIE_FLAGS.

Referenced by _pctrie_lookup(), pctrie_insert(), pctrie_lookup_ge(), pctrie_lookup_le(), and pctrie_remove().

Here is the caller graph for this function:

◆ pctrie_trimkey()

static __inline uint64_t pctrie_trimkey	(	uint64_t	index,
		uint16_t	level
	)

static

Definition at line 160 of file subr_pctrie.c.

References level.

Referenced by pctrie_insert(), pctrie_keybarr(), pctrie_lookup_ge(), and pctrie_lookup_le().

Here is the caller graph for this function:

◆ pctrie_zone_init()

int pctrie_zone_init	(	void *	mem,
		int size	__unused,
		int flags	__unused
	)

Definition at line 325 of file subr_pctrie.c.

Referenced by rs_rangeset_init(), and vntblinit().

Here is the caller graph for this function:

◆ SMR_POINTER()

typedef SMR_POINTER ( struct pctrie_node * )

Definition at line 79 of file subr_pctrie.c.

Macros

Enumerations

Functions

Macro Definition Documentation

◆ PCTRIE_FLAGS

◆ PCTRIE_ISLEAF

◆ PCTRIE_LIMIT

◆ PCTRIE_MASK

◆ PCTRIE_PAD

◆ PCTRIE_UNITLEVEL

Enumeration Type Documentation

◆ pctrie_access

Function Documentation

◆ __FBSDID()

◆ _pctrie_lookup()

◆ pctrie_addval()

◆ pctrie_insert()

◆ pctrie_isleaf()

◆ pctrie_keybarr()

◆ pctrie_keydiff()

◆ pctrie_lookup()

◆ pctrie_lookup_ge()

◆ pctrie_lookup_le()

◆ pctrie_lookup_unlocked()

◆ pctrie_node_get()

◆ pctrie_node_load()

◆ pctrie_node_put()

◆ pctrie_node_size()

◆ pctrie_node_store()

◆ pctrie_reclaim_allnodes()

◆ pctrie_reclaim_allnodes_int()

◆ pctrie_remove()

◆ pctrie_root_load()

◆ pctrie_root_store()

◆ pctrie_slot()

◆ pctrie_toval()

◆ pctrie_trimkey()

◆ pctrie_zone_init()

◆ SMR_POINTER()