master
1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
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
31#ifndef _SYS_PCTRIE_H_
32#define _SYS_PCTRIE_H_
33
34#include <sys/_pctrie.h>
35#include <sys/_smr.h>
36
37#ifdef _KERNEL
38
39#define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
40 PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
41 \
42static __inline struct type * \
43name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
44{ \
45 \
46 return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \
47 key, (smr))); \
48} \
49
50#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
51 \
52CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
53/* \
54 * XXX This assert protects flag bits, it does not enforce natural \
55 * alignment. 32bit architectures do not naturally align 64bit fields. \
56 */ \
57CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
58 \
59static __inline struct type * \
60name##_PCTRIE_VAL2PTR(uint64_t *val) \
61{ \
62 \
63 if (val == NULL) \
64 return (NULL); \
65 return (struct type *) \
66 ((uintptr_t)val - __offsetof(struct type, field)); \
67} \
68 \
69static __inline uint64_t * \
70name##_PCTRIE_PTR2VAL(struct type *ptr) \
71{ \
72 \
73 return &ptr->field; \
74} \
75 \
76static __inline int \
77name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \
78{ \
79 struct pctrie_node *parent; \
80 void *parentp; \
81 uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
82 \
83 parentp = pctrie_insert_lookup(ptree, val); \
84 if (parentp == NULL) \
85 return (0); \
86 parent = allocfn(ptree); \
87 if (parent == NULL) \
88 return (ENOMEM); \
89 pctrie_insert_node(parentp, parent, val); \
90 return (0); \
91} \
92 \
93static __inline __unused struct type * \
94name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
95{ \
96 \
97 return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key)); \
98} \
99 \
100static __inline __unused struct type * \
101name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key) \
102{ \
103 \
104 return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key)); \
105} \
106 \
107static __inline __unused struct type * \
108name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key) \
109{ \
110 \
111 return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key)); \
112} \
113 \
114static __inline __unused void \
115name##_PCTRIE_RECLAIM(struct pctrie *ptree) \
116{ \
117 struct pctrie_node *freenode, *node; \
118 \
119 for (freenode = pctrie_reclaim_begin(&node, ptree); \
120 freenode != NULL; \
121 freenode = pctrie_reclaim_resume(&node)) \
122 freefn(ptree, freenode); \
123} \
124 \
125static __inline __unused struct type * \
126name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
127{ \
128 \
129 return name##_PCTRIE_VAL2PTR( \
130 pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
131} \
132 \
133static __inline __unused void \
134name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
135{ \
136 uint64_t *val; \
137 struct pctrie_node *freenode; \
138 \
139 val = pctrie_remove_lookup(ptree, key, &freenode); \
140 if (val == NULL) \
141 panic("%s: key not found", __func__); \
142 if (freenode != NULL) \
143 freefn(ptree, freenode); \
144} \
145 \
146static __inline __unused struct type * \
147name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \
148{ \
149 uint64_t *val; \
150 struct pctrie_node *freenode; \
151 \
152 val = pctrie_remove_lookup(ptree, key, &freenode); \
153 if (freenode != NULL) \
154 freefn(ptree, freenode); \
155 return name##_PCTRIE_VAL2PTR(val); \
156}
157
158void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val);
159void pctrie_insert_node(void *parentp,
160 struct pctrie_node *parent, uint64_t *val);
161uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
162uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
163uint64_t *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
164uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
165 smr_t smr);
166struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
167 struct pctrie *ptree);
168struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
169uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
170 struct pctrie_node **killnode);
171uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
172size_t pctrie_node_size(void);
173int pctrie_zone_init(void *mem, int size, int flags);
174
175/*
176 * Each search path in the trie terminates at a leaf, which is a pointer to a
177 * value marked with a set 1-bit. A leaf may be associated with a null pointer
178 * to indicate no value there.
179 */
180#define PCTRIE_ISLEAF 0x1
181#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF
182
183static __inline void
184pctrie_init(struct pctrie *ptree)
185{
186 ptree->pt_root = PCTRIE_NULL;
187}
188
189static __inline bool
190pctrie_is_empty(struct pctrie *ptree)
191{
192 return (ptree->pt_root == PCTRIE_NULL);
193}
194
195/* Set of all flag bits stored in node pointers. */
196#define PCTRIE_FLAGS (PCTRIE_ISLEAF)
197/* Minimum align parameter for uma_zcreate. */
198#define PCTRIE_PAD PCTRIE_FLAGS
199
200/*
201 * These widths should allow the pointers to a node's children to fit within
202 * a single cache line. The extra levels from a narrow width should not be
203 * a problem thanks to path compression.
204 */
205#ifdef __LP64__
206#define PCTRIE_WIDTH 4
207#else
208#define PCTRIE_WIDTH 3
209#endif
210
211#define PCTRIE_COUNT (1 << PCTRIE_WIDTH)
212
213#endif /* _KERNEL */
214#endif /* !_SYS_PCTRIE_H_ */