1 /*- 2 * Copyright (c) 2016 Mindaugas Rasiukevicius <rmind at noxt eu> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 /* 28 * Longest Prefix Match (LPM) library supporting IPv4 and IPv6. 29 * 30 * Algorithm: 31 * 32 * Each prefix gets its own hash map and all added prefixes are saved 33 * in a bitmap. On a lookup, we perform a linear scan of hash maps, 34 * iterating through the added prefixes only. Usually, there are only 35 * a few unique prefixes used and such simple algorithm is very efficient. 36 * With many IPv6 prefixes, the linear scan might become a bottleneck. 37 */ 38 39 #if defined(_KERNEL) 40 #include <sys/cdefs.h> 41 __KERNEL_RCSID(0, "$NetBSD: lpm.c,v 1.7 2026/09/28 17:45:10 christos Exp $"); 42 43 #include <sys/param.h> 44 #include <sys/types.h> 45 #include <sys/malloc.h> 46 #include <sys/kmem.h> 47 #else 48 #include <sys/socket.h> 49 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <stdbool.h> 53 #include <stddef.h> 54 #include <string.h> 55 #include <strings.h> 56 #include <errno.h> 57 #include <assert.h> 58 #define kmem_alloc(a, b) malloc(a) 59 #define kmem_free(a, b) free(a) 60 #define kmem_zalloc(a, b) calloc(a, 1) 61 #endif 62 63 #include "lpm.h" 64 65 #define LPM_MAX_PREFIX (128) 66 #define LPM_MAX_WORDS (LPM_MAX_PREFIX >> 5) 67 #define LPM_TO_WORDS(x) ((x) >> 2) 68 #define LPM_HASH_STEP (8) 69 #define LPM_LEN_IDX(len) ((len) >> 4) 70 71 #ifdef DEBUG 72 #define ASSERT assert 73 #else 74 #define ASSERT(x) 75 #endif 76 77 typedef struct lpm_ent { 78 struct lpm_ent *next; 79 void * val; 80 unsigned len; 81 uint8_t key[]; 82 } lpm_ent_t; 83 84 typedef struct { 85 unsigned hashsize; 86 unsigned nitems; 87 lpm_ent_t ** bucket; 88 } lpm_hmap_t; 89 90 struct lpm { 91 uint32_t bitmask[LPM_MAX_WORDS]; 92 int flags; 93 void * defvals[2]; 94 lpm_hmap_t prefix[LPM_MAX_PREFIX + 1]; 95 }; 96 97 static const uint32_t zero_address[LPM_MAX_WORDS]; 98 99 lpm_t * 100 lpm_create(int flags) 101 { 102 lpm_t *lpm = kmem_zalloc(sizeof(*lpm), KM_SLEEP); 103 lpm->flags = flags; 104 return lpm; 105 } 106 107 void 108 lpm_clear(lpm_t *lpm, lpm_dtor_t dtor, void *arg) 109 { 110 for (unsigned n = 0; n <= LPM_MAX_PREFIX; n++) { 111 lpm_hmap_t *hmap = &lpm->prefix[n]; 112 113 if (!hmap->hashsize) { 114 KASSERT(!hmap->bucket); 115 continue; 116 } 117 for (unsigned i = 0; i < hmap->hashsize; i++) { 118 lpm_ent_t *entry = hmap->bucket[i]; 119 120 while (entry) { 121 lpm_ent_t *next = entry->next; 122 123 if (dtor) { 124 dtor(arg, entry->key, 125 entry->len, entry->val); 126 } 127 kmem_free(entry, 128 offsetof(lpm_ent_t, key[entry->len])); 129 entry = next; 130 } 131 } 132 kmem_free(hmap->bucket, hmap->hashsize * sizeof(lpm_ent_t *)); 133 hmap->bucket = NULL; 134 hmap->hashsize = 0; 135 hmap->nitems = 0; 136 } 137 if (dtor) { 138 dtor(arg, zero_address, 4, lpm->defvals[0]); 139 dtor(arg, zero_address, 16, lpm->defvals[1]); 140 } 141 memset(lpm->bitmask, 0, sizeof(lpm->bitmask)); 142 memset(lpm->defvals, 0, sizeof(lpm->defvals)); 143 } 144 145 void 146 lpm_destroy(lpm_t *lpm) 147 { 148 lpm_clear(lpm, NULL, NULL); 149 kmem_free(lpm, sizeof(*lpm)); 150 } 151 152 /* 153 * fnv1a_hash: Fowler-Noll-Vo hash function (FNV-1a variant). 154 */ 155 static uint32_t 156 fnv1a_hash(const void *buf, size_t len) 157 { 158 uint32_t hash = 2166136261UL; 159 const uint8_t *p = buf; 160 161 while (len--) { 162 hash ^= *p++; 163 hash *= 16777619U; 164 } 165 return hash; 166 } 167 168 static bool 169 hashmap_rehash(lpm_hmap_t *hmap, unsigned size, int flags) 170 { 171 lpm_ent_t **bucket; 172 unsigned hashsize; 173 174 for (hashsize = 1; hashsize < size; hashsize <<= 1) { 175 continue; 176 } 177 bucket = kmem_zalloc(hashsize * sizeof(lpm_ent_t *), flags); 178 if (bucket == NULL) 179 return false; 180 for (unsigned n = 0; n < hmap->hashsize; n++) { 181 lpm_ent_t *list = hmap->bucket[n]; 182 183 while (list) { 184 lpm_ent_t *entry = list; 185 uint32_t hash = fnv1a_hash(entry->key, entry->len); 186 const unsigned i = hash & (hashsize - 1); 187 188 list = entry->next; 189 entry->next = bucket[i]; 190 bucket[i] = entry; 191 } 192 } 193 if (hmap->bucket) 194 kmem_free(hmap->bucket, hmap->hashsize * sizeof(lpm_ent_t *)); 195 hmap->bucket = bucket; 196 hmap->hashsize = hashsize; 197 return true; 198 } 199 200 static lpm_ent_t * 201 hashmap_insert(lpm_hmap_t *hmap, const void *key, size_t len, int flags) 202 { 203 const unsigned target = hmap->nitems + LPM_HASH_STEP; 204 const size_t entlen = offsetof(lpm_ent_t, key[len]); 205 uint32_t hash, i; 206 lpm_ent_t *entry; 207 208 if (hmap->hashsize < target && !hashmap_rehash(hmap, target, flags)) { 209 return NULL; 210 } 211 212 hash = fnv1a_hash(key, len); 213 i = hash & (hmap->hashsize - 1); 214 entry = hmap->bucket[i]; 215 while (entry) { 216 if (entry->len == len && memcmp(entry->key, key, len) == 0) { 217 return entry; 218 } 219 entry = entry->next; 220 } 221 222 if ((entry = kmem_alloc(entlen, flags)) != NULL) { 223 memcpy(entry->key, key, len); 224 entry->next = hmap->bucket[i]; 225 entry->len = len; 226 227 hmap->bucket[i] = entry; 228 hmap->nitems++; 229 } 230 return entry; 231 } 232 233 static lpm_ent_t * 234 hashmap_lookup(lpm_hmap_t *hmap, const void *key, size_t len) 235 { 236 const uint32_t hash = fnv1a_hash(key, len); 237 const unsigned i = hash & (hmap->hashsize - 1); 238 lpm_ent_t *entry; 239 240 if (hmap->hashsize == 0) { 241 return NULL; 242 } 243 entry = hmap->bucket[i]; 244 245 while (entry) { 246 if (entry->len == len && memcmp(entry->key, key, len) == 0) { 247 return entry; 248 } 249 entry = entry->next; 250 } 251 return NULL; 252 } 253 254 static int 255 hashmap_remove(lpm_hmap_t *hmap, const void *key, size_t len) 256 { 257 const uint32_t hash = fnv1a_hash(key, len); 258 const unsigned i = hash & (hmap->hashsize - 1); 259 lpm_ent_t *prev = NULL, *entry; 260 261 if (hmap->hashsize == 0) { 262 return -1; 263 } 264 entry = hmap->bucket[i]; 265 266 while (entry) { 267 if (entry->len == len && memcmp(entry->key, key, len) == 0) { 268 if (prev) { 269 prev->next = entry->next; 270 } else { 271 hmap->bucket[i] = entry->next; 272 } 273 kmem_free(entry, offsetof(lpm_ent_t, key[len])); 274 return 0; 275 } 276 prev = entry; 277 entry = entry->next; 278 } 279 return -1; 280 } 281 282 /* 283 * compute_prefix: given the address and prefix length, compute and 284 * return the address prefix. 285 */ 286 static inline void 287 compute_prefix(const unsigned nwords, const uint32_t *addr, 288 unsigned preflen, uint32_t *prefix) 289 { 290 uint32_t addr2[4]; 291 292 if ((uintptr_t)addr & 3) { 293 /* Unaligned address: just copy for now. */ 294 memcpy(addr2, addr, nwords * 4); 295 addr = addr2; 296 } 297 for (unsigned i = 0; i < nwords; i++) { 298 if (preflen == 0) { 299 prefix[i] = 0; 300 continue; 301 } 302 if (preflen < 32) { 303 uint32_t mask = htonl(0xffffffff << (32 - preflen)); 304 prefix[i] = addr[i] & mask; 305 preflen = 0; 306 } else { 307 prefix[i] = addr[i]; 308 preflen -= 32; 309 } 310 } 311 } 312 313 /* 314 * lpm_insert: insert the CIDR into the LPM table. 315 * 316 * => Returns zero on success and -1 on failure. 317 */ 318 int 319 lpm_insert(lpm_t *lpm, const void *addr, 320 size_t len, unsigned preflen, void *val) 321 { 322 const unsigned nwords = LPM_TO_WORDS(len); 323 uint32_t prefix[LPM_MAX_WORDS]; 324 lpm_ent_t *entry; 325 KASSERT(len == 4 || len == 16); 326 327 if (preflen == 0) { 328 /* 0-length prefix is a special case. */ 329 lpm->defvals[LPM_LEN_IDX(len)] = val; 330 return 0; 331 } 332 compute_prefix(nwords, addr, preflen, prefix); 333 entry = hashmap_insert(&lpm->prefix[preflen], prefix, len, lpm->flags); 334 if (entry) { 335 const unsigned n = --preflen >> 5; 336 lpm->bitmask[n] |= 0x80000000U >> (preflen & 31); 337 entry->val = val; 338 return 0; 339 } 340 return -1; 341 } 342 343 /* 344 * lpm_remove: remove the specified prefix. 345 */ 346 int 347 lpm_remove(lpm_t *lpm, const void *addr, size_t len, unsigned preflen) 348 { 349 const unsigned nwords = LPM_TO_WORDS(len); 350 uint32_t prefix[LPM_MAX_WORDS]; 351 KASSERT(len == 4 || len == 16); 352 353 if (preflen == 0) { 354 lpm->defvals[LPM_LEN_IDX(len)] = NULL; 355 return 0; 356 } 357 compute_prefix(nwords, addr, preflen, prefix); 358 return hashmap_remove(&lpm->prefix[preflen], prefix, len); 359 } 360 361 /* 362 * lpm_lookup: find the longest matching prefix given the IP address. 363 * 364 * => Returns the associated value on success or NULL on failure. 365 */ 366 void * 367 lpm_lookup(lpm_t *lpm, const void *addr, size_t len) 368 { 369 const unsigned nwords = LPM_TO_WORDS(len); 370 unsigned i, n = nwords; 371 uint32_t prefix[LPM_MAX_WORDS]; 372 373 while (n--) { 374 uint32_t bitmask = lpm->bitmask[n]; 375 376 while ((i = ffs(bitmask)) != 0) { 377 const unsigned preflen = (32 * n) + (32 - --i); 378 lpm_hmap_t *hmap = &lpm->prefix[preflen]; 379 lpm_ent_t *entry; 380 381 compute_prefix(nwords, addr, preflen, prefix); 382 entry = hashmap_lookup(hmap, prefix, len); 383 if (entry) { 384 return entry->val; 385 } 386 bitmask &= ~(1U << i); 387 } 388 } 389 return lpm->defvals[LPM_LEN_IDX(len)]; 390 } 391 392 /* 393 * lpm_lookup_prefix: return the value associated with a prefix 394 * 395 * => Returns the associated value on success or NULL on failure. 396 */ 397 void * 398 lpm_lookup_prefix(lpm_t *lpm, const void *addr, size_t len, unsigned preflen) 399 { 400 const unsigned nwords = LPM_TO_WORDS(len); 401 uint32_t prefix[LPM_MAX_WORDS]; 402 lpm_ent_t *entry; 403 KASSERT(len == 4 || len == 16); 404 405 if (preflen == 0) { 406 return lpm->defvals[LPM_LEN_IDX(len)]; 407 } 408 compute_prefix(nwords, addr, preflen, prefix); 409 entry = hashmap_lookup(&lpm->prefix[preflen], prefix, len); 410 if (entry) { 411 return entry->val; 412 } 413 return NULL; 414 } 415 416 #if !defined(_KERNEL) 417 /* 418 * lpm_strtobin: convert CIDR string to the binary IP address and mask. 419 * 420 * => The address will be in the network byte order. 421 * => Returns 0 on success or -1 on failure. 422 */ 423 int 424 lpm_strtobin(const char *cidr, void *addr, size_t *len, unsigned *preflen) 425 { 426 char *p, buf[INET6_ADDRSTRLEN]; 427 428 strncpy(buf, cidr, sizeof(buf)); 429 buf[sizeof(buf) - 1] = '\0'; 430 431 if ((p = strchr(buf, '/')) != NULL) { 432 const ptrdiff_t off = p - buf; 433 *preflen = atoi(&buf[off + 1]); 434 buf[off] = '\0'; 435 } else { 436 *preflen = LPM_MAX_PREFIX; 437 } 438 439 if (inet_pton(AF_INET6, buf, addr) == 1) { 440 *len = 16; 441 return 0; 442 } 443 if (inet_pton(AF_INET, buf, addr) == 1) { 444 if (*preflen == LPM_MAX_PREFIX) { 445 *preflen = 32; 446 } 447 *len = 4; 448 return 0; 449 } 450 return -1; 451 } 452 #endif 453
Indexes created Sun Oct 25 00:26:45 UTC 2026