1 /* $NetBSD: npf_tableset.c,v 1.14 2012/08/12 03:35:14 rmind Exp $ */ 2 3 /*- 4 * Copyright (c) 2009-2012 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This material is based upon work partially supported by The 8 * NetBSD Foundation under a contract with Mindaugas Rasiukevicius. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * NPF tableset module. 34 * 35 * TODO: 36 * - Dynamic hash growing/shrinking (i.e. re-hash functionality), maybe? 37 * - Dynamic array resize. 38 */ 39 40 #include <sys/cdefs.h> 41 __KERNEL_RCSID(0, "$NetBSD: npf_tableset.c,v 1.14 2012/08/12 03:35:14 rmind Exp $"); 42 43 #include <sys/param.h> 44 #include <sys/types.h> 45 46 #include <sys/atomic.h> 47 #include <sys/hash.h> 48 #include <sys/kmem.h> 49 #include <sys/pool.h> 50 #include <sys/queue.h> 51 #include <sys/rwlock.h> 52 #include <sys/systm.h> 53 #include <sys/types.h> 54 55 #include "npf_impl.h" 56 57 /* 58 * Table structures. 59 */ 60 61 struct npf_tblent { 62 union { 63 LIST_ENTRY(npf_tblent) hashq; 64 pt_node_t node; 65 } te_entry; 66 int te_alen; 67 npf_addr_t te_addr; 68 }; 69 70 LIST_HEAD(npf_hashl, npf_tblent); 71 72 struct npf_table { 73 char t_name[16]; 74 /* Lock and reference count. */ 75 krwlock_t t_lock; 76 u_int t_refcnt; 77 /* Table ID. */ 78 u_int t_id; 79 /* The storage type can be: a) hash b) tree. */ 80 int t_type; 81 struct npf_hashl * t_hashl; 82 u_long t_hashmask; 83 pt_tree_t t_tree[2]; 84 }; 85 86 #define NPF_ADDRLEN2TREE(alen) ((alen) >> 4) 87 88 static pool_cache_t tblent_cache __read_mostly; 89 90 /* 91 * npf_table_sysinit: initialise tableset structures. 92 */ 93 void 94 npf_tableset_sysinit(void) 95 { 96 97 tblent_cache = pool_cache_init(sizeof(npf_tblent_t), coherency_unit, 98 0, 0, "npftblpl", NULL, IPL_NONE, NULL, NULL, NULL); 99 } 100 101 void 102 npf_tableset_sysfini(void) 103 { 104 105 pool_cache_destroy(tblent_cache); 106 } 107 108 npf_tableset_t * 109 npf_tableset_create(void) 110 { 111 const size_t sz = NPF_TABLE_SLOTS * sizeof(npf_table_t *); 112 113 return kmem_zalloc(sz, KM_SLEEP); 114 } 115 116 void 117 npf_tableset_destroy(npf_tableset_t *tblset) 118 { 119 const size_t sz = NPF_TABLE_SLOTS * sizeof(npf_table_t *); 120 npf_table_t *t; 121 u_int tid; 122 123 /* 124 * Destroy all tables (no references should be held, as ruleset 125 * should be destroyed before). 126 */ 127 for (tid = 0; tid < NPF_TABLE_SLOTS; tid++) { 128 t = tblset[tid]; 129 if (t != NULL) { 130 npf_table_destroy(t); 131 } 132 } 133 kmem_free(tblset, sz); 134 } 135 136 /* 137 * npf_tableset_insert: insert the table into the specified tableset. 138 * 139 * => Returns 0 on success. Fails and returns error if ID is already used. 140 */ 141 int 142 npf_tableset_insert(npf_tableset_t *tblset, npf_table_t *t) 143 { 144 const u_int tid = t->t_id; 145 int error; 146 147 KASSERT((u_int)tid < NPF_TABLE_SLOTS); 148 149 if (tblset[tid] == NULL) { 150 tblset[tid] = t; 151 error = 0; 152 } else { 153 error = EEXIST; 154 } 155 return error; 156 } 157 158 /* 159 * Few helper routines. 160 */ 161 162 static npf_tblent_t * 163 table_hash_lookup(const npf_table_t *t, const npf_addr_t *addr, 164 const int alen, struct npf_hashl **rhtbl) 165 { 166 const uint32_t hidx = hash32_buf(addr, alen, HASH32_BUF_INIT); 167 struct npf_hashl *htbl = &t->t_hashl[hidx & t->t_hashmask]; 168 npf_tblent_t *ent; 169 170 /* 171 * Lookup the hash table and check for duplicates. 172 * Note: mask is ignored for the hash storage. 173 */ 174 LIST_FOREACH(ent, htbl, te_entry.hashq) { 175 if (ent->te_alen != alen) { 176 continue; 177 } 178 if (memcmp(&ent->te_addr, addr, alen) == 0) { 179 break; 180 } 181 } 182 *rhtbl = htbl; 183 return ent; 184 } 185 186 static void 187 table_tree_destroy(pt_tree_t *tree) 188 { 189 npf_tblent_t *ent; 190 191 while ((ent = ptree_iterate(tree, NULL, PT_ASCENDING)) != NULL) { 192 ptree_remove_node(tree, ent); 193 pool_cache_put(tblent_cache, ent); 194 } 195 } 196 197 /* 198 * npf_table_create: create table with a specified ID. 199 */ 200 npf_table_t * 201 npf_table_create(u_int tid, int type, size_t hsize) 202 { 203 npf_table_t *t; 204 205 KASSERT((u_int)tid < NPF_TABLE_SLOTS); 206 207 t = kmem_zalloc(sizeof(npf_table_t), KM_SLEEP); 208 switch (type) { 209 case NPF_TABLE_TREE: 210 ptree_init(&t->t_tree[0], &npf_table_ptree_ops, 211 (void *)(sizeof(struct in_addr) / sizeof(uint32_t)), 212 offsetof(npf_tblent_t, te_entry.node), 213 offsetof(npf_tblent_t, te_addr)); 214 ptree_init(&t->t_tree[1], &npf_table_ptree_ops, 215 (void *)(sizeof(struct in6_addr) / sizeof(uint32_t)), 216 offsetof(npf_tblent_t, te_entry.node), 217 offsetof(npf_tblent_t, te_addr)); 218 break; 219 case NPF_TABLE_HASH: 220 t->t_hashl = hashinit(hsize, HASH_LIST, true, &t->t_hashmask); 221 if (t->t_hashl == NULL) { 222 kmem_free(t, sizeof(npf_table_t)); 223 return NULL; 224 } 225 break; 226 default: 227 KASSERT(false); 228 } 229 rw_init(&t->t_lock); 230 t->t_type = type; 231 t->t_refcnt = 1; 232 t->t_id = tid; 233 return t; 234 } 235 236 /* 237 * npf_table_destroy: free all table entries and table itself. 238 */ 239 void 240 npf_table_destroy(npf_table_t *t) 241 { 242 243 switch (t->t_type) { 244 case NPF_TABLE_HASH: { 245 for (unsigned n = 0; n <= t->t_hashmask; n++) { 246 npf_tblent_t *ent; 247 248 while ((ent = LIST_FIRST(&t->t_hashl[n])) != NULL) { 249 LIST_REMOVE(ent, te_entry.hashq); 250 pool_cache_put(tblent_cache, ent); 251 } 252 } 253 hashdone(t->t_hashl, HASH_LIST, t->t_hashmask); 254 break; 255 } 256 case NPF_TABLE_TREE: { 257 table_tree_destroy(&t->t_tree[0]); 258 table_tree_destroy(&t->t_tree[1]); 259 break; 260 } 261 default: 262 KASSERT(false); 263 } 264 rw_destroy(&t->t_lock); 265 kmem_free(t, sizeof(npf_table_t)); 266 } 267 268 /* 269 * npf_table_ref: holds the reference on table. 270 * 271 * => Table must be locked. 272 */ 273 void 274 npf_table_ref(npf_table_t *t) 275 { 276 277 KASSERT(rw_lock_held(&t->t_lock)); 278 atomic_inc_uint(&t->t_refcnt); 279 } 280 281 /* 282 * npf_table_unref: drop reference from the table and destroy the table if 283 * it is the last reference. 284 */ 285 void 286 npf_table_unref(npf_table_t *t) 287 { 288 289 if (atomic_dec_uint_nv(&t->t_refcnt) != 0) { 290 return; 291 } 292 npf_table_destroy(t); 293 } 294 295 /* 296 * npf_table_get: find the table according to ID and "get it" by locking it. 297 */ 298 npf_table_t * 299 npf_table_get(npf_tableset_t *tset, u_int tid) 300 { 301 npf_table_t *t; 302 303 KASSERT(tset != NULL); 304 305 if ((u_int)tid >= NPF_TABLE_SLOTS) { 306 return NULL; 307 } 308 t = tset[tid]; 309 if (t != NULL) { 310 rw_enter(&t->t_lock, RW_READER); 311 } 312 return t; 313 } 314 315 /* 316 * npf_table_put: "put table back" by unlocking it. 317 */ 318 void 319 npf_table_put(npf_table_t *t) 320 { 321 322 rw_exit(&t->t_lock); 323 } 324 325 /* 326 * npf_table_check: validate ID and type. 327 */ 328 int 329 npf_table_check(const npf_tableset_t *tset, u_int tid, int type) 330 { 331 332 if ((u_int)tid >= NPF_TABLE_SLOTS) { 333 return EINVAL; 334 } 335 if (tset[tid] != NULL) { 336 return EEXIST; 337 } 338 if (type != NPF_TABLE_TREE && type != NPF_TABLE_HASH) { 339 return EINVAL; 340 } 341 return 0; 342 } 343 344 static int 345 npf_table_validate_cidr(const u_int aidx, const npf_addr_t *addr, 346 const npf_netmask_t mask) 347 { 348 349 if (mask > NPF_MAX_NETMASK && mask != NPF_NO_NETMASK) { 350 return EINVAL; 351 } 352 if (aidx > 1) { 353 return EINVAL; 354 } 355 356 /* 357 * For IPv4 (aidx = 0) - 32 and for IPv6 (aidx = 1) - 128. 358 * If it is a host - shall use NPF_NO_NETMASK. 359 */ 360 if (mask >= (aidx ? 128 : 32) && mask != NPF_NO_NETMASK) { 361 return EINVAL; 362 } 363 return 0; 364 } 365 366 /* 367 * npf_table_insert: add an IP CIDR entry into the table. 368 */ 369 int 370 npf_table_insert(npf_tableset_t *tset, u_int tid, const int alen, 371 const npf_addr_t *addr, const npf_netmask_t mask) 372 { 373 const u_int aidx = NPF_ADDRLEN2TREE(alen); 374 npf_tblent_t *ent; 375 npf_table_t *t; 376 int error; 377 378 error = npf_table_validate_cidr(aidx, addr, mask); 379 if (error) { 380 return error; 381 } 382 ent = pool_cache_get(tblent_cache, PR_WAITOK); 383 memcpy(&ent->te_addr, addr, alen); 384 ent->te_alen = alen; 385 386 /* Get the table (acquire the lock). */ 387 t = npf_table_get(tset, tid); 388 if (t == NULL) { 389 pool_cache_put(tblent_cache, ent); 390 return EINVAL; 391 } 392 393 /* 394 * Insert the entry. Return an error on duplicate. 395 */ 396 switch (t->t_type) { 397 case NPF_TABLE_HASH: { 398 struct npf_hashl *htbl; 399 400 /* 401 * Hash tables by the concept support only IPs. 402 */ 403 if (mask != NPF_NO_NETMASK) { 404 error = EINVAL; 405 break; 406 } 407 if (!table_hash_lookup(t, addr, alen, &htbl)) { 408 LIST_INSERT_HEAD(htbl, ent, te_entry.hashq); 409 } else { 410 error = EEXIST; 411 } 412 break; 413 } 414 case NPF_TABLE_TREE: { 415 pt_tree_t *tree = &t->t_tree[aidx]; 416 bool ok; 417 418 /* 419 * If no mask specified, use maximum mask. 420 */ 421 if (mask != NPF_NO_NETMASK) { 422 ok = ptree_insert_mask_node(tree, ent, mask); 423 } else { 424 ok = ptree_insert_node(tree, ent); 425 } 426 error = ok ? 0 : EEXIST; 427 break; 428 } 429 default: 430 KASSERT(false); 431 } 432 npf_table_put(t); 433 434 if (error) { 435 pool_cache_put(tblent_cache, ent); 436 } 437 return error; 438 } 439 440 /* 441 * npf_table_remove: remove the IP CIDR entry from the table. 442 */ 443 int 444 npf_table_remove(npf_tableset_t *tset, u_int tid, const int alen, 445 const npf_addr_t *addr, const npf_netmask_t mask) 446 { 447 const u_int aidx = NPF_ADDRLEN2TREE(alen); 448 npf_tblent_t *ent; 449 npf_table_t *t; 450 int error; 451 452 error = npf_table_validate_cidr(aidx, addr, mask); 453 if (error) { 454 return error; 455 } 456 t = npf_table_get(tset, tid); 457 if (t == NULL) { 458 return EINVAL; 459 } 460 461 switch (t->t_type) { 462 case NPF_TABLE_HASH: { 463 struct npf_hashl *htbl; 464 465 ent = table_hash_lookup(t, addr, alen, &htbl); 466 if (__predict_true(ent != NULL)) { 467 LIST_REMOVE(ent, te_entry.hashq); 468 } 469 break; 470 } 471 case NPF_TABLE_TREE: { 472 pt_tree_t *tree = &t->t_tree[aidx]; 473 474 ent = ptree_find_node(tree, addr); 475 if (__predict_true(ent != NULL)) { 476 ptree_remove_node(tree, ent); 477 } 478 break; 479 } 480 default: 481 KASSERT(false); 482 ent = NULL; 483 } 484 npf_table_put(t); 485 486 if (ent == NULL) { 487 return ENOENT; 488 } 489 pool_cache_put(tblent_cache, ent); 490 return 0; 491 } 492 493 /* 494 * npf_table_lookup: find the table according to ID, lookup and match 495 * the contents with the specified IP address. 496 */ 497 int 498 npf_table_lookup(npf_tableset_t *tset, u_int tid, 499 const int alen, const npf_addr_t *addr) 500 { 501 const u_int aidx = NPF_ADDRLEN2TREE(alen); 502 npf_tblent_t *ent; 503 npf_table_t *t; 504 505 if (__predict_false(aidx > 1)) { 506 return EINVAL; 507 } 508 509 t = npf_table_get(tset, tid); 510 if (__predict_false(t == NULL)) { 511 return EINVAL; 512 } 513 switch (t->t_type) { 514 case NPF_TABLE_HASH: { 515 struct npf_hashl *htbl; 516 ent = table_hash_lookup(t, addr, alen, &htbl); 517 break; 518 } 519 case NPF_TABLE_TREE: { 520 ent = ptree_find_node(&t->t_tree[aidx], addr); 521 break; 522 } 523 default: 524 KASSERT(false); 525 ent = NULL; 526 } 527 npf_table_put(t); 528 529 return ent ? 0 : ENOENT; 530 } 531