1 /*- 2 * Copyright (c) 2019 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 * NPF port map mechanism. 29 * 30 * The port map is a bitmap used to track TCP/UDP ports used for 31 * translation. Port maps are per IP addresses, therefore multiple 32 * NAT policies operating on the same IP address will share the 33 * same port map. 34 */ 35 36 #ifdef _KERNEL 37 #include <sys/cdefs.h> 38 __KERNEL_RCSID(0, "$NetBSD: npf_portmap.c,v 1.7 2020/08/28 06:35:50 riastradh Exp $"); 39 40 #include <sys/param.h> 41 #include <sys/types.h> 42 43 #include <sys/atomic.h> 44 #include <sys/bitops.h> 45 #include <sys/kmem.h> 46 #include <sys/mutex.h> 47 #include <sys/cprng.h> 48 #include <sys/thmap.h> 49 #endif 50 51 #include "npf_impl.h" 52 53 /* 54 * Port map uses two-level bitmaps with compression to efficiently 55 * represent the maximum of 65536 (2^16) values. 56 * 57 * Level 0: 64 chunks each representing 1048 bits in two modes: 58 * 59 * a) If PORTMAP_L1_TAG, then up to 5 values are packed in the 60 * 64-bit integer using 12 bits for each value, starting from the 61 * most significant bits. The four 4 least significant bits are 62 * unused or reserved for pointer tagging. 63 * 64 * b) If there are more than 5 values, then PORTMAP_L1_TAG is set 65 * and the value serves as a pointer to the second level bitmap. 66 * 67 * Level 1: 16 chunks each representing 64 bits in plain uint64_t. 68 */ 69 70 #define PORTMAP_MAX_BITS (65536U) 71 #define PORTMAP_MASK (PORTMAP_MAX_BITS - 1) 72 73 #define PORTMAP_L0_SHIFT (10) // or 11 74 #define PORTMAP_L0_MASK ((1U << PORTMAP_L0_SHIFT) - 1) 75 #define PORTMAP_L0_WORDS (PORTMAP_MAX_BITS >> PORTMAP_L0_SHIFT) 76 77 #define PORTMAP_L1_SHIFT (6) 78 #define PORTMAP_L1_MASK ((1U << PORTMAP_L1_SHIFT) - 1) 79 #define PORTMAP_L1_WORDS \ 80 ((PORTMAP_MAX_BITS / PORTMAP_L0_WORDS) >> PORTMAP_L1_SHIFT) 81 82 #define PORTMAP_L1_TAG (UINT64_C(1)) // use level 1 83 #define PORTMAP_L1_GET(p) ((void *)((uintptr_t)(p) & ~(uintptr_t)3)) 84 85 CTASSERT(sizeof(uint64_t) >= sizeof(uintptr_t)); 86 87 typedef struct { 88 volatile uint64_t bits1[PORTMAP_L1_WORDS]; 89 } bitmap_l1_t; 90 91 typedef struct bitmap { 92 npf_addr_t addr; 93 volatile uint64_t bits0[PORTMAP_L0_WORDS]; 94 LIST_ENTRY(bitmap) entry; 95 unsigned addr_len; 96 } bitmap_t; 97 98 #define NPF_PORTMAP_MINPORT 1024 99 #define NPF_PORTMAP_MAXPORT 65535 100 101 struct npf_portmap { 102 thmap_t * addr_map; 103 LIST_HEAD(, bitmap) bitmap_list; 104 kmutex_t list_lock; 105 int min_port; 106 int max_port; 107 }; 108 109 static kmutex_t portmap_lock; 110 111 void 112 npf_portmap_sysinit(void) 113 { 114 115 mutex_init(&portmap_lock, MUTEX_DEFAULT, IPL_SOFTNET); 116 } 117 118 void 119 npf_portmap_sysfini(void) 120 { 121 122 mutex_destroy(&portmap_lock); 123 } 124 125 void 126 npf_portmap_init(npf_t *npf) 127 { 128 npf_portmap_t *pm = npf_portmap_create( 129 NPF_PORTMAP_MINPORT, NPF_PORTMAP_MAXPORT); 130 npf_param_t param_map[] = { 131 { 132 "portmap.min_port", 133 &pm->min_port, 134 .default_val = NPF_PORTMAP_MINPORT, 135 .min = 1024, .max = 65535 136 }, 137 { 138 "portmap.max_port", 139 &pm->max_port, 140 .default_val = 49151, // RFC 6335 141 .min = 1024, .max = 65535 142 } 143 }; 144 145 npf_param_register(npf, param_map, __arraycount(param_map)); 146 npf->portmap = pm; 147 } 148 149 void 150 npf_portmap_fini(npf_t *npf) 151 { 152 153 npf_portmap_destroy(npf->portmap); 154 npf->portmap = NULL; // diagnostic 155 } 156 157 npf_portmap_t * 158 npf_portmap_create(int min_port, int max_port) 159 { 160 npf_portmap_t *pm; 161 162 pm = kmem_zalloc(sizeof(npf_portmap_t), KM_SLEEP); 163 mutex_init(&pm->list_lock, MUTEX_DEFAULT, IPL_SOFTNET); 164 pm->addr_map = thmap_create(0, NULL, THMAP_NOCOPY); 165 pm->min_port = min_port; 166 pm->max_port = max_port; 167 return pm; 168 } 169 170 void 171 npf_portmap_destroy(npf_portmap_t *pm) 172 { 173 npf_portmap_flush(pm); 174 KASSERT(LIST_EMPTY(&pm->bitmap_list)); 175 176 thmap_destroy(pm->addr_map); 177 mutex_destroy(&pm->list_lock); 178 kmem_free(pm, sizeof(npf_portmap_t)); 179 } 180 181 ///////////////////////////////////////////////////////////////////////// 182 183 #if defined(_LP64) 184 #define __npf_atomic_cas_64 atomic_cas_64 185 #else 186 static uint64_t 187 __npf_atomic_cas_64(volatile uint64_t *ptr, uint64_t old, uint64_t new) 188 { 189 uint64_t prev; 190 191 mutex_enter(&portmap_lock); 192 prev = *ptr; 193 if (prev == old) { 194 *ptr = new; 195 } 196 mutex_exit(&portmap_lock); 197 198 return prev; 199 } 200 #endif 201 202 /* 203 * bitmap_word_isset: test whether the bit value is in the packed array. 204 * 205 * => Return true if any value equals the bit number value. 206 * 207 * Packed array: 60 MSB bits, 5 values, 12 bits each. 208 * 209 * Reference: "Bit Twiddling Hacks" by S.E. Anderson, Stanford. 210 * Based on the hasvalue() and haszero() ideas. Since values are 211 * represented by upper 60 bits, we shift right by 4. 212 */ 213 static bool 214 bitmap_word_isset(uint64_t x, unsigned bit) 215 { 216 uint64_t m, r; 217 218 bit++; 219 KASSERT((x & PORTMAP_L1_TAG) == 0); 220 KASSERT(bit <= (PORTMAP_L0_MASK + 1)); 221 222 m = (x >> 4) ^ (UINT64_C(0x1001001001001) * bit); 223 r = (m - UINT64_C(0x1001001001001)) & (~m & UINT64_C(0x800800800800800)); 224 return r != 0; 225 } 226 227 /* 228 * bitmap_word_cax: compare-and-xor on packed array elements. 229 */ 230 static uint64_t 231 bitmap_word_cax(uint64_t x, int exp, int bit) 232 { 233 unsigned e = exp + 1; 234 235 /* 236 * We need to distinguish "no value" from zero. Just add one, 237 * since we use 12 bits to represent 11 bit values. 238 */ 239 bit++; 240 KASSERT((unsigned)bit <= (PORTMAP_L0_MASK + 1)); 241 KASSERT((x & PORTMAP_L1_TAG) == 0); 242 243 if (((x >> 52) & 0xfff) == e) 244 return x ^ ((uint64_t)bit << 52); 245 if (((x >> 40) & 0xfff) == e) 246 return x ^ ((uint64_t)bit << 40); 247 if (((x >> 28) & 0xfff) == e) 248 return x ^ ((uint64_t)bit << 28); 249 if (((x >> 16) & 0xfff) == e) 250 return x ^ ((uint64_t)bit << 16); 251 if (((x >> 4) & 0xfff) == e) 252 return x ^ ((uint64_t)bit << 4); 253 return 0; 254 } 255 256 static unsigned 257 bitmap_word_unpack(uint64_t x, unsigned bitvals[static 5]) 258 { 259 unsigned n = 0; 260 uint64_t v; 261 262 KASSERT((x & PORTMAP_L1_TAG) == 0); 263 264 if ((v = ((x >> 52)) & 0xfff) != 0) 265 bitvals[n++] = v - 1; 266 if ((v = ((x >> 40)) & 0xfff) != 0) 267 bitvals[n++] = v - 1; 268 if ((v = ((x >> 28)) & 0xfff) != 0) 269 bitvals[n++] = v - 1; 270 if ((v = ((x >> 16)) & 0xfff) != 0) 271 bitvals[n++] = v - 1; 272 if ((v = ((x >> 4)) & 0xfff) != 0) 273 bitvals[n++] = v - 1; 274 return n; 275 } 276 277 #if 0 278 static bool 279 bitmap_isset(const bitmap_t *bm, unsigned bit) 280 { 281 unsigned i, chunk_bit; 282 uint64_t bval, b; 283 bitmap_l1_t *bm1; 284 285 KASSERT(bit < PORTMAP_MAX_BITS); 286 i = bit >> PORTMAP_L0_SHIFT; 287 bval = atomic_load_relaxed(&bm->bits0[i]); 288 289 /* 290 * Empty check. Note: we can test the whole word against zero, 291 * since zero bit values in the packed array result in bits set. 292 */ 293 if (bval == 0) 294 return false; 295 296 /* Level 0 check. */ 297 chunk_bit = bit & PORTMAP_L0_MASK; 298 if ((bval & PORTMAP_L1_TAG) == 0) 299 return bitmap_word_isset(bval, chunk_bit); 300 301 /* Level 1 check. */ 302 bm1 = PORTMAP_L1_GET(bval); 303 KASSERT(bm1 != NULL); 304 i = chunk_bit >> PORTMAP_L1_SHIFT; 305 b = UINT64_C(1) << (chunk_bit & PORTMAP_L1_MASK); 306 return (bm1->bits1[i] & b) != 0; 307 } 308 #endif 309 310 static bool 311 bitmap_set(bitmap_t *bm, unsigned bit) 312 { 313 unsigned i, chunk_bit; 314 uint64_t bval, b, oval, nval; 315 bitmap_l1_t *bm1; 316 again: 317 KASSERT(bit < PORTMAP_MAX_BITS); 318 i = bit >> PORTMAP_L0_SHIFT; 319 chunk_bit = bit & PORTMAP_L0_MASK; 320 bval = bm->bits0[i]; 321 322 if ((bval & PORTMAP_L1_TAG) == 0) { 323 unsigned n = 0, bitvals[5]; 324 uint64_t bm1p; 325 326 if (bitmap_word_isset(bval, chunk_bit)) { 327 return false; 328 } 329 330 /* 331 * Look for a zero-slot and put a value there. 332 */ 333 if ((nval = bitmap_word_cax(bval, -1, chunk_bit)) != 0) { 334 KASSERT((nval & PORTMAP_L1_TAG) == 0); 335 if (__npf_atomic_cas_64(&bm->bits0[i], bval, nval) != bval) { 336 goto again; 337 } 338 return true; 339 } 340 341 /* 342 * Full: allocate L1 block and copy over the current 343 * values into the level. 344 */ 345 bm1 = kmem_intr_zalloc(sizeof(bitmap_l1_t), KM_NOSLEEP); 346 if (bm1 == NULL) { 347 return false; // error 348 } 349 n = bitmap_word_unpack(bval, bitvals); 350 while (n--) { 351 const unsigned v = bitvals[n]; 352 const unsigned off = v >> PORTMAP_L1_SHIFT; 353 354 KASSERT(v <= PORTMAP_L0_MASK); 355 KASSERT(off < (sizeof(uint64_t) * CHAR_BIT)); 356 bm1->bits1[off] |= UINT64_C(1) << (v & PORTMAP_L1_MASK); 357 } 358 359 /* 360 * Attempt to set the L1 structure. Note: there is no 361 * ABA problem since the we compare the actual values. 362 * Note: CAS serves as a memory barrier. 363 */ 364 bm1p = (uintptr_t)bm1; 365 KASSERT((bm1p & PORTMAP_L1_TAG) == 0); 366 bm1p |= PORTMAP_L1_TAG; 367 if (__npf_atomic_cas_64(&bm->bits0[i], bval, bm1p) != bval) { 368 kmem_intr_free(bm1, sizeof(bitmap_l1_t)); 369 goto again; 370 } 371 bval = bm1p; 372 } 373 374 bm1 = PORTMAP_L1_GET(bval); 375 KASSERT(bm1 != NULL); 376 i = chunk_bit >> PORTMAP_L1_SHIFT; 377 b = UINT64_C(1) << (chunk_bit & PORTMAP_L1_MASK); 378 379 oval = bm1->bits1[i]; 380 if (oval & b) { 381 return false; 382 } 383 nval = oval | b; 384 if (__npf_atomic_cas_64(&bm1->bits1[i], oval, nval) != oval) { 385 goto again; 386 } 387 return true; 388 } 389 390 static bool 391 bitmap_clr(bitmap_t *bm, unsigned bit) 392 { 393 unsigned i, chunk_bit; 394 uint64_t bval, b, oval, nval; 395 bitmap_l1_t *bm1; 396 again: 397 KASSERT(bit < PORTMAP_MAX_BITS); 398 i = bit >> PORTMAP_L0_SHIFT; 399 chunk_bit = bit & PORTMAP_L0_MASK; 400 bval = bm->bits0[i]; 401 402 if ((bval & PORTMAP_L1_TAG) == 0) { 403 if (!bitmap_word_isset(bval, chunk_bit)) { 404 return false; 405 } 406 nval = bitmap_word_cax(bval, chunk_bit, chunk_bit); 407 KASSERT((nval & PORTMAP_L1_TAG) == 0); 408 if (__npf_atomic_cas_64(&bm->bits0[i], bval, nval) != bval) { 409 goto again; 410 } 411 return true; 412 } 413 414 bm1 = PORTMAP_L1_GET(bval); 415 KASSERT(bm1 != NULL); 416 i = chunk_bit >> PORTMAP_L1_SHIFT; 417 b = UINT64_C(1) << (chunk_bit & PORTMAP_L1_MASK); 418 419 oval = bm1->bits1[i]; 420 if ((oval & b) == 0) { 421 return false; 422 } 423 nval = oval & ~b; 424 if (__npf_atomic_cas_64(&bm1->bits1[i], oval, nval) != oval) { 425 goto again; 426 } 427 return true; 428 } 429 430 ///////////////////////////////////////////////////////////////////////// 431 432 static bitmap_t * 433 npf_portmap_autoget(npf_portmap_t *pm, unsigned alen, const npf_addr_t *addr) 434 { 435 bitmap_t *bm; 436 437 KASSERT(pm && pm->addr_map); 438 KASSERT(alen && alen <= sizeof(npf_addr_t)); 439 440 /* Lookup the port map for this address. */ 441 bm = thmap_get(pm->addr_map, addr, alen); 442 if (bm == NULL) { 443 void *ret; 444 445 /* 446 * Allocate a new port map for this address and 447 * attempt to insert it. 448 */ 449 bm = kmem_intr_zalloc(sizeof(bitmap_t), KM_NOSLEEP); 450 if (bm == NULL) { 451 return NULL; 452 } 453 memcpy(&bm->addr, addr, alen); 454 bm->addr_len = alen; 455 456 int s = splsoftnet(); 457 ret = thmap_put(pm->addr_map, &bm->addr, alen, bm); 458 splx(s); 459 460 if (ret == bm) { 461 /* Success: insert the bitmap into the list. */ 462 mutex_enter(&pm->list_lock); 463 LIST_INSERT_HEAD(&pm->bitmap_list, bm, entry); 464 mutex_exit(&pm->list_lock); 465 } else { 466 /* Race: use an existing bitmap. */ 467 kmem_free(bm, sizeof(bitmap_t)); 468 bm = ret; 469 } 470 } 471 return bm; 472 } 473 474 /* 475 * npf_portmap_flush: free all bitmaps and remove all addresses. 476 * 477 * => Concurrent calls to this routine are not allowed; therefore no 478 * need to acquire locks. 479 */ 480 void 481 npf_portmap_flush(npf_portmap_t *pm) 482 { 483 bitmap_t *bm; 484 485 while ((bm = LIST_FIRST(&pm->bitmap_list)) != NULL) { 486 for (unsigned i = 0; i < PORTMAP_L0_WORDS; i++) { 487 uintptr_t bm1 = bm->bits0[i]; 488 489 if (bm1 & PORTMAP_L1_TAG) { 490 bitmap_l1_t *bm1p = PORTMAP_L1_GET(bm1); 491 kmem_intr_free(bm1p, sizeof(bitmap_l1_t)); 492 } 493 bm->bits0[i] = UINT64_C(0); 494 } 495 LIST_REMOVE(bm, entry); 496 thmap_del(pm->addr_map, &bm->addr, bm->addr_len); 497 kmem_intr_free(bm, sizeof(bitmap_t)); 498 } 499 /* Note: the caller ensures there are no active references. */ 500 thmap_gc(pm->addr_map, thmap_stage_gc(pm->addr_map)); 501 } 502 503 /* 504 * npf_portmap_get: allocate and return a port from the given portmap. 505 * 506 * => Returns the port value in network byte-order. 507 * => Zero indicates a failure. 508 */ 509 in_port_t 510 npf_portmap_get(npf_portmap_t *pm, int alen, const npf_addr_t *addr) 511 { 512 const unsigned min_port = atomic_load_relaxed(&pm->min_port); 513 const unsigned max_port = atomic_load_relaxed(&pm->max_port); 514 const unsigned port_delta = max_port - min_port + 1; 515 unsigned bit, target; 516 bitmap_t *bm; 517 518 /* Sanity check: the user might set incorrect parameters. */ 519 if (__predict_false(min_port > max_port)) { 520 return 0; 521 } 522 523 bm = npf_portmap_autoget(pm, alen, addr); 524 if (__predict_false(bm == NULL)) { 525 /* No memory. */ 526 return 0; 527 } 528 529 /* Randomly select a port. */ 530 target = min_port + (cprng_fast32() % port_delta); 531 bit = target; 532 next: 533 if (bitmap_set(bm, bit)) { 534 /* Success. */ 535 return htons(bit); 536 } 537 bit = min_port + ((bit + 1) % port_delta); 538 if (target != bit) { 539 /* Next.. */ 540 goto next; 541 } 542 /* No space. */ 543 return 0; 544 } 545 546 /* 547 * npf_portmap_take: allocate a specific port in the portmap. 548 */ 549 bool 550 npf_portmap_take(npf_portmap_t *pm, int alen, 551 const npf_addr_t *addr, in_port_t port) 552 { 553 bitmap_t *bm = npf_portmap_autoget(pm, alen, addr); 554 555 port = ntohs(port); 556 if (!bm || port < pm->min_port || port > pm->max_port) { 557 /* Out of memory / invalid port. */ 558 return false; 559 } 560 return bitmap_set(bm, port); 561 } 562 563 /* 564 * npf_portmap_put: release the port, making it available in the portmap. 565 * 566 * => The port value should be in network byte-order. 567 */ 568 void 569 npf_portmap_put(npf_portmap_t *pm, int alen, 570 const npf_addr_t *addr, in_port_t port) 571 { 572 bitmap_t *bm; 573 574 bm = npf_portmap_autoget(pm, alen, addr); 575 if (bm) { 576 port = ntohs(port); 577 bitmap_clr(bm, port); 578 } 579 } 580
Indexes created Sat Sep 20 22:09:52 GMT 2025