1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (c) 2013 EMC Corp.
5 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
6 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 *
30 * $FreeBSD$
31 */
32
33#ifndef _SYS_PCTRIE_H_
34#define _SYS_PCTRIE_H_
35
36#include <sys/_pctrie.h>
37#include <sys/_smr.h>
38
39#ifdef _KERNEL
40
41#define	PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr)	\
42    PCTRIE_DEFINE(name, type, field, allocfn, freefn)			\
43									\
44static __inline struct type *						\
45name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key)	\
46{									\
47									\
48	return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree,	\
49	    key, (smr)));						\
50}									\
51
52#define	PCTRIE_DEFINE(name, type, field, allocfn, freefn)		\
53									\
54CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t));	\
55/*									\
56 * XXX This assert protects flag bits, it does not enforce natural	\
57 * alignment.  32bit architectures do not naturally align 64bit fields.	\
58 */									\
59CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
60									\
61static __inline struct type *						\
62name##_PCTRIE_VAL2PTR(uint64_t *val)					\
63{									\
64									\
65	if (val == NULL)						\
66		return (NULL);						\
67	return (struct type *)						\
68	    ((uintptr_t)val - __offsetof(struct type, field));		\
69}									\
70									\
71static __inline uint64_t *						\
72name##_PCTRIE_PTR2VAL(struct type *ptr)					\
73{									\
74									\
75	return &ptr->field;						\
76}									\
77									\
78static __inline int							\
79name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr)		\
80{									\
81									\
82	return pctrie_insert(ptree, name##_PCTRIE_PTR2VAL(ptr),		\
83	    allocfn);							\
84}									\
85									\
86static __inline struct type *						\
87name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key)		\
88{									\
89									\
90	return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key));	\
91}									\
92									\
93static __inline __unused struct type *						\
94name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key)		\
95{									\
96									\
97	return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key));	\
98}									\
99									\
100static __inline __unused struct type *					\
101name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key)		\
102{									\
103									\
104	return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key));	\
105}									\
106									\
107static __inline __unused void						\
108name##_PCTRIE_RECLAIM(struct pctrie *ptree)				\
109{									\
110									\
111	pctrie_reclaim_allnodes(ptree, freefn);				\
112}									\
113									\
114static __inline void							\
115name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key)		\
116{									\
117									\
118	pctrie_remove(ptree, key, freefn);				\
119}
120
121typedef	void	*(*pctrie_alloc_t)(struct pctrie *ptree);
122typedef	void 	(*pctrie_free_t)(struct pctrie *ptree, void *node);
123
124int		pctrie_insert(struct pctrie *ptree, uint64_t *val,
125		    pctrie_alloc_t allocfn);
126uint64_t	*pctrie_lookup(struct pctrie *ptree, uint64_t key);
127uint64_t	*pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
128uint64_t	*pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
129uint64_t	*pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
130		    smr_t smr);
131void		pctrie_reclaim_allnodes(struct pctrie *ptree,
132		    pctrie_free_t freefn);
133void		pctrie_remove(struct pctrie *ptree, uint64_t key,
134		    pctrie_free_t freefn);
135size_t		pctrie_node_size(void);
136int		pctrie_zone_init(void *mem, int size, int flags);
137
138static __inline void
139pctrie_init(struct pctrie *ptree)
140{
141
142	ptree->pt_root = 0;
143}
144
145static __inline bool
146pctrie_is_empty(struct pctrie *ptree)
147{
148
149	return (ptree->pt_root == 0);
150}
151
152/*
153 * These widths should allow the pointers to a node's children to fit within
154 * a single cache line.  The extra levels from a narrow width should not be
155 * a problem thanks to path compression.
156 */
157#ifdef __LP64__
158#define	PCTRIE_WIDTH	4
159#else
160#define	PCTRIE_WIDTH	3
161#endif
162
163#define	PCTRIE_COUNT	(1 << PCTRIE_WIDTH)
164
165#endif /* _KERNEL */
166#endif /* !_SYS_PCTRIE_H_ */
167