sys/sys/pctrie.h

   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                                                                         \
  42 static __inline struct type *                                           \
  43 name##_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                                                                         \
  52 CTASSERT(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  */                                                                     \
  57 CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \
  58                                                                         \
  59 static __inline struct type *                                           \
  60 name##_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                                                                         \
  69 static __inline uint64_t *                                              \
  70 name##_PCTRIE_PTR2VAL(struct type *ptr)                                 \
  71 {                                                                       \
  72                                                                         \
  73         return &ptr->field;                                             \
  74 }                                                                       \
  75                                                                         \
  76 static __inline int                                                     \
  77 name##_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                                                                         \
  93 static __inline __unused struct type *                                  \
  94 name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key)                \
  95 {                                                                       \
  96                                                                         \
  97         return name##_PCTRIE_VAL2PTR(pctrie_lookup(ptree, key));        \
  98 }                                                                       \
  99                                                                         \
 100 static __inline __unused struct type *                                  \
 101 name##_PCTRIE_LOOKUP_LE(struct pctrie *ptree, uint64_t key)             \
 102 {                                                                       \
 103                                                                         \
 104         return name##_PCTRIE_VAL2PTR(pctrie_lookup_le(ptree, key));     \
 105 }                                                                       \
 106                                                                         \
 107 static __inline __unused struct type *                                  \
 108 name##_PCTRIE_LOOKUP_GE(struct pctrie *ptree, uint64_t key)             \
 109 {                                                                       \
 110                                                                         \
 111         return name##_PCTRIE_VAL2PTR(pctrie_lookup_ge(ptree, key));     \
 112 }                                                                       \
 113                                                                         \
 114 static __inline __unused void                                           \
 115 name##_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                                                                         \
 125 static __inline __unused struct type *                                  \
 126 name##_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                                                                         \
 133 static __inline __unused void                                           \
 134 name##_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                                                                         \
 146 static __inline __unused struct type *                                  \
 147 name##_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
 158 void            *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val);
 159 void            pctrie_insert_node(void *parentp,
 160                     struct pctrie_node *parent, uint64_t *val);
 161 uint64_t        *pctrie_lookup(struct pctrie *ptree, uint64_t key);
 162 uint64_t        *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
 163 uint64_t        *pctrie_lookup_le(struct pctrie *ptree, uint64_t key);
 164 uint64_t        *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
 165                     smr_t smr);
 166 struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
 167                     struct pctrie *ptree);
 168 struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
 169 uint64_t        *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
 170                     struct pctrie_node **killnode);
 171 uint64_t        *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
 172 size_t          pctrie_node_size(void);
 173 int             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
 183 static __inline void
 184 pctrie_init(struct pctrie *ptree)
 185 {
 186         ptree->pt_root = PCTRIE_NULL;
 187 }
 188
 189 static __inline bool
 190 pctrie_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_ */