sys/net/route/nhop_utils.h

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2020 Alexander V. Chernikov
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  *
  27  * $FreeBSD$
  28  */
  29
  30 #ifndef _NET_ROUTE_NHOP_UTILS_H_
  31 #define _NET_ROUTE_NHOP_UTILS_H_
  32
  33 /* Chained hash table */
  34 struct _cht_head {
  35         uint32_t        hash_size;
  36         uint32_t        items_count;
  37         void            **ptr;
  38 };
  39
  40 static inline uint32_t
  41 _cht_get_resize_size(const struct _cht_head *head)
  42 {
  43         uint32_t new_size = 0;
  44
  45         if ((head->items_count * 2 > head->hash_size) && (head->hash_size < 65536))
  46                 new_size = head->hash_size * 2;
  47         else if ((head->items_count * 4 < head->hash_size) && head->hash_size > 16)
  48                 new_size = head->hash_size / 2;
  49
  50         return (new_size);
  51 }
  52
  53 static inline int
  54 _cht_need_resize(const struct _cht_head *head)
  55 {
  56
  57         return (_cht_get_resize_size(head) > 0);
  58 }
  59
  60 #ifndef typeof
  61 #define typeof  __typeof
  62 #endif
  63
  64 #define CHT_SLIST_NEED_RESIZE(_head)            \
  65         _cht_need_resize((const struct _cht_head *)(_head))
  66 #define CHT_SLIST_GET_RESIZE_BUCKETS(_head)     \
  67         _cht_get_resize_size((const struct _cht_head *)(_head))
  68 #define CHT_SLIST_GET_RESIZE_SIZE(_buckets)     ((_buckets) * sizeof(void *))
  69
  70 #define CHT_SLIST_DEFINE(_HNAME, _ITEM_TYPE)    \
  71 struct _HNAME##_head {                          \
  72         uint32_t        hash_size;              \
  73         uint32_t        items_count;            \
  74         _ITEM_TYPE      **ptr;                  \
  75 }
  76
  77 #define CHT_SLIST_INIT(_head, _ptr, _num_buckets)       \
  78         (_head)->hash_size = _num_buckets;              \
  79         (_head)->items_count = 0;                       \
  80         (_head)->ptr = _ptr;
  81
  82 /* Default hash method for constant-size keys */
  83
  84 #define CHT_GET_BUCK(_head, _PX, _key)  _PX##_hash_key(_key) & ((_head)->hash_size - 1)
  85 #define CHT_GET_BUCK_OBJ(_head, _PX, _obj)      _PX##_hash_obj(_obj) & ((_head)->hash_size - 1)
  86
  87 #define CHT_FIRST(_head, idx)   _CHT_FIRST((_head)->ptr, idx)
  88 #define _CHT_FIRST(_ptr, idx)   (_ptr)[idx]
  89
  90 #define CHT_SLIST_FIND(_head, _PX, _key, _ret) do {                     \
  91         uint32_t _buck = CHT_GET_BUCK(_head, _PX, _key);                \
  92         _ret = CHT_FIRST(_head, _buck);                                 \
  93         for ( ; _ret != NULL; _ret = _PX##_next(_ret)) {                \
  94                 if (_PX##_cmp(_key, (_ret)))                            \
  95                         break;                                          \
  96         }                                                               \
  97 } while(0)
  98
  99 /*
 100  * hash_obj, nhop_cmp
 101  */
 102 #define CHT_SLIST_FIND_BYOBJ(_head, _PX, _obj, _ret) do {               \
 103         uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);            \
 104         _ret = CHT_FIRST(_head, _buck);                                 \
 105         for ( ; _ret != NULL; _ret = _PX##_next(_ret)) {                \
 106                 if (_PX##_cmp(_obj, _ret))                              \
 107                         break;                                          \
 108         }                                                               \
 109 } while(0)
 110
 111 #define CHT_SLIST_INSERT_HEAD(_head, _PX, _obj) do {                    \
 112         uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);            \
 113         _PX##_next(_obj) = CHT_FIRST(_head, _buck);                     \
 114         CHT_FIRST(_head, _buck) = _obj;                                 \
 115         (_head)->items_count++;                                         \
 116 } while(0)
 117
 118 #define CHT_SLIST_REMOVE(_head, _PX, _obj, _ret) do {                   \
 119         typeof(*(_head)->ptr) _tmp;                                     \
 120         uint32_t _buck = CHT_GET_BUCK_OBJ(_head, _PX, _obj);            \
 121         _ret = CHT_FIRST(_head, _buck);                                 \
 122         _tmp = NULL;                                                    \
 123         for ( ; _ret != NULL; _tmp = _ret, _ret = _PX##_next(_ret)) {   \
 124                 if (_obj == _ret)                                       \
 125                         break;                                          \
 126         }                                                               \
 127         if (_ret != NULL) {                                             \
 128                 if (_tmp == NULL)                                       \
 129                         CHT_FIRST(_head, _buck) = _PX##_next(_ret);     \
 130                 else                                                    \
 131                         _PX##_next(_tmp) = _PX##_next(_ret);            \
 132                 (_head)->items_count--;                                 \
 133         }                                                               \
 134 } while(0)
 135 #define CHT_SLIST_REMOVE_BYOBJ  CHT_SLIST_REMOVE
 136
 137 #define CHT_SLIST_FOREACH(_head, _PX, _x)                               \
 138         for (uint32_t _i = 0; _i < (_head)->hash_size; _i++) {          \
 139                 for (_x = CHT_FIRST(_head, _i); _x; _x = _PX##_next(_x))
 140 #define CHT_SLIST_FOREACH_END   }
 141
 142 #define CHT_SLIST_RESIZE(_head, _PX, _new_void_ptr, _new_hsize)         \
 143         uint32_t _new_idx;                                              \
 144         typeof((_head)->ptr) _new_ptr = (void *)_new_void_ptr;          \
 145         typeof(*(_head)->ptr) _x, _y;                                   \
 146         for (uint32_t _old_idx = 0; _old_idx < (_head)->hash_size; _old_idx++) {\
 147                 _x = CHT_FIRST(_head, _old_idx);                        \
 148                 _y = _x;                                                \
 149                 while (_y != NULL) {                                    \
 150                         _y = _PX##_next(_x);                            \
 151                         _new_idx = _PX##_hash_obj(_x) & (_new_hsize - 1);\
 152                         _PX##_next(_x) = _CHT_FIRST(_new_ptr, _new_idx);\
 153                         _CHT_FIRST(_new_ptr, _new_idx) = _x;            \
 154                         _x = _y;                                        \
 155                 }                                                       \
 156         }                                                               \
 157         (_head)->hash_size = _new_hsize;                                \
 158         _new_void_ptr = (void *)(_head)->ptr;                           \
 159         (_head)->ptr = _new_ptr;
 160
 161 /* bitmasks */
 162
 163 struct bitmask_head {
 164         uint16_t        free_off; /* index of the first potentially free block */
 165         uint16_t        blocks; /* number of 4/8-byte blocks in the index */
 166         uint32_t        items_count; /* total number of items */
 167         u_long          *idx;
 168 };
 169
 170 size_t bitmask_get_size(uint32_t items);
 171 uint32_t bitmask_get_resize_items(const struct bitmask_head *nh);
 172 int bitmask_should_resize(const struct bitmask_head *bh);
 173 void bitmask_swap(struct bitmask_head *bh, void *new_idx, uint32_t new_items, void **pidx);
 174 void bitmask_init(struct bitmask_head *bh, void *idx, uint32_t num_items);
 175 int bitmask_copy(const struct bitmask_head *bi, void *new_idx, uint32_t new_items);
 176 int bitmask_alloc_idx(struct bitmask_head *bi, uint16_t *pidx);
 177 int bitmask_free_idx(struct bitmask_head *bi, uint16_t idx);
 178
 179 #endif