1 /* $NetBSD: npf_conndb.c,v 1.3 2016/12/26 23:05:06 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 2010-2014 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 connection storage. 34 */ 35 36 #ifdef _KERNEL 37 #include <sys/cdefs.h> 38 __KERNEL_RCSID(0, "$NetBSD: npf_conndb.c,v 1.3 2016/12/26 23:05:06 christos Exp $"); 39 40 #include <sys/param.h> 41 #include <sys/types.h> 42 43 #include <sys/atomic.h> 44 #include <sys/cprng.h> 45 #include <sys/hash.h> 46 #include <sys/kmem.h> 47 #endif 48 49 #define __NPF_CONN_PRIVATE 50 #include "npf_conn.h" 51 #include "npf_impl.h" 52 53 #define CONNDB_HASH_BUCKETS 1024 /* XXX tune + make tunable */ 54 #define CONNDB_HASH_MASK (CONNDB_HASH_BUCKETS - 1) 55 56 typedef struct { 57 rb_tree_t hb_tree; 58 krwlock_t hb_lock; 59 u_int hb_count; 60 } npf_hashbucket_t; 61 62 struct npf_conndb { 63 npf_conn_t * cd_recent; 64 npf_conn_t * cd_list; 65 npf_conn_t * cd_tail; 66 uint32_t cd_seed; 67 void * cd_tree; 68 npf_hashbucket_t cd_hashtbl[]; 69 }; 70 71 /* 72 * Connection hash table and RB-tree helper routines. 73 * Note: (node1 < node2) shall return negative. 74 */ 75 76 static signed int 77 conndb_rbtree_cmp_nodes(void *ctx, const void *n1, const void *n2) 78 { 79 const npf_connkey_t * const ck1 = n1; 80 const npf_connkey_t * const ck2 = n2; 81 const u_int keylen = MIN(NPF_CONN_KEYLEN(ck1), NPF_CONN_KEYLEN(ck2)); 82 83 KASSERT((keylen >> 2) <= NPF_CONN_NKEYWORDS); 84 return memcmp(ck1->ck_key, ck2->ck_key, keylen); 85 } 86 87 static signed int 88 conndb_rbtree_cmp_key(void *ctx, const void *n1, const void *key) 89 { 90 const npf_connkey_t * const ck1 = n1; 91 const npf_connkey_t * const ck2 = key; 92 return conndb_rbtree_cmp_nodes(ctx, ck1, ck2); 93 } 94 95 static const rb_tree_ops_t conndb_rbtree_ops = { 96 .rbto_compare_nodes = conndb_rbtree_cmp_nodes, 97 .rbto_compare_key = conndb_rbtree_cmp_key, 98 .rbto_node_offset = offsetof(npf_connkey_t, ck_rbnode), 99 .rbto_context = NULL 100 }; 101 102 static npf_hashbucket_t * 103 conndb_hash_bucket(npf_conndb_t *cd, const npf_connkey_t *key) 104 { 105 const u_int keylen = NPF_CONN_KEYLEN(key); 106 uint32_t hash = murmurhash2(key->ck_key, keylen, cd->cd_seed); 107 return &cd->cd_hashtbl[hash & CONNDB_HASH_MASK]; 108 } 109 110 npf_conndb_t * 111 npf_conndb_create(void) 112 { 113 size_t len = offsetof(npf_conndb_t, cd_hashtbl[CONNDB_HASH_BUCKETS]); 114 npf_conndb_t *cd; 115 116 cd = kmem_zalloc(len, KM_SLEEP); 117 for (u_int i = 0; i < CONNDB_HASH_BUCKETS; i++) { 118 npf_hashbucket_t *hb = &cd->cd_hashtbl[i]; 119 120 rb_tree_init(&hb->hb_tree, &conndb_rbtree_ops); 121 rw_init(&hb->hb_lock); 122 hb->hb_count = 0; 123 } 124 cd->cd_seed = cprng_fast32(); 125 return cd; 126 } 127 128 void 129 npf_conndb_destroy(npf_conndb_t *cd) 130 { 131 size_t len = offsetof(npf_conndb_t, cd_hashtbl[CONNDB_HASH_BUCKETS]); 132 133 KASSERT(cd->cd_recent == NULL); 134 KASSERT(cd->cd_list == NULL); 135 KASSERT(cd->cd_tail == NULL); 136 137 for (u_int i = 0; i < CONNDB_HASH_BUCKETS; i++) { 138 npf_hashbucket_t *hb = &cd->cd_hashtbl[i]; 139 140 KASSERT(hb->hb_count == 0); 141 KASSERT(!rb_tree_iterate(&hb->hb_tree, NULL, RB_DIR_LEFT)); 142 rw_destroy(&hb->hb_lock); 143 } 144 #ifdef USE_JUDY 145 Word_t bytes; 146 JHSFA(bytes, cd->cd_tree); 147 #endif 148 kmem_free(cd, len); 149 } 150 151 /* 152 * npf_conndb_lookup: find a connection given the key. 153 */ 154 npf_conn_t * 155 npf_conndb_lookup(npf_conndb_t *cd, const npf_connkey_t *key, bool *forw) 156 { 157 npf_connkey_t *foundkey; 158 npf_hashbucket_t *hb; 159 npf_conn_t *con; 160 161 /* Get a hash bucket from the cached key data. */ 162 hb = conndb_hash_bucket(cd, key); 163 if (hb->hb_count == 0) { 164 return NULL; 165 } 166 167 /* Lookup the tree given the key and get the actual connection. */ 168 rw_enter(&hb->hb_lock, RW_READER); 169 foundkey = rb_tree_find_node(&hb->hb_tree, key); 170 if (foundkey == NULL) { 171 rw_exit(&hb->hb_lock); 172 return NULL; 173 } 174 con = foundkey->ck_backptr; 175 *forw = (foundkey == &con->c_forw_entry); 176 177 /* Acquire the reference and return the connection. */ 178 atomic_inc_uint(&con->c_refcnt); 179 rw_exit(&hb->hb_lock); 180 return con; 181 } 182 183 /* 184 * npf_conndb_insert: insert the key representing the connection. 185 */ 186 bool 187 npf_conndb_insert(npf_conndb_t *cd, npf_connkey_t *key, npf_conn_t *con) 188 { 189 #ifdef USE_JUDY 190 PWord_t pval; 191 192 JHSI(pval, cd->cd_tree, key, NPF_CONN_KEYLEN(key)); 193 if (pval == PJERR || *pval != 0) 194 return false; 195 *pval = (uintptr_t)key; 196 return true; 197 #else 198 npf_hashbucket_t *hb = conndb_hash_bucket(cd, key); 199 bool ok; 200 201 rw_enter(&hb->hb_lock, RW_WRITER); 202 ok = rb_tree_insert_node(&hb->hb_tree, key) == key; 203 hb->hb_count += (u_int)ok; 204 rw_exit(&hb->hb_lock); 205 return ok; 206 #endif 207 } 208 209 /* 210 * npf_conndb_remove: find and delete the key and return the connection 211 * it represents. 212 */ 213 npf_conn_t * 214 npf_conndb_remove(npf_conndb_t *cd, npf_connkey_t *key) 215 { 216 #ifdef USE_JUDY 217 PWord_t rc; 218 219 JHSD(rc, cd->cd_tree, key, NPF_CONN_KEYLEN(key)); 220 return rc ? key->ck_backptr : NULL; 221 #else 222 npf_hashbucket_t *hb = conndb_hash_bucket(cd, key); 223 npf_connkey_t *foundkey; 224 npf_conn_t *con; 225 226 rw_enter(&hb->hb_lock, RW_WRITER); 227 if ((foundkey = rb_tree_find_node(&hb->hb_tree, key)) != NULL) { 228 rb_tree_remove_node(&hb->hb_tree, foundkey); 229 con = foundkey->ck_backptr; 230 hb->hb_count--; 231 } else { 232 con = NULL; 233 } 234 rw_exit(&hb->hb_lock); 235 return con; 236 #endif 237 } 238 239 /* 240 * npf_conndb_enqueue: atomically insert the connection into the 241 * singly-linked list of "recent" connections. 242 */ 243 void 244 npf_conndb_enqueue(npf_conndb_t *cd, npf_conn_t *con) 245 { 246 npf_conn_t *head; 247 248 do { 249 head = cd->cd_recent; 250 con->c_next = head; 251 } while (atomic_cas_ptr(&cd->cd_recent, head, con) != head); 252 } 253 254 /* 255 * npf_conndb_dequeue: remove the connection from a singly-linked list 256 * given the previous element; no concurrent writers are allowed here. 257 */ 258 void 259 npf_conndb_dequeue(npf_conndb_t *cd, npf_conn_t *con, npf_conn_t *prev) 260 { 261 if (prev == NULL) { 262 KASSERT(cd->cd_list == con); 263 cd->cd_list = con->c_next; 264 } else { 265 prev->c_next = con->c_next; 266 } 267 } 268 269 /* 270 * npf_conndb_getlist: atomically take the "recent" connections and add 271 * them to the singly-linked list of the connections. 272 */ 273 npf_conn_t * 274 npf_conndb_getlist(npf_conndb_t *cd) 275 { 276 npf_conn_t *con, *prev; 277 278 con = atomic_swap_ptr(&cd->cd_recent, NULL); 279 if ((prev = cd->cd_tail) == NULL) { 280 KASSERT(cd->cd_list == NULL); 281 cd->cd_list = con; 282 } else { 283 KASSERT(prev->c_next == NULL); 284 prev->c_next = con; 285 } 286 return cd->cd_list; 287 } 288 289 /* 290 * npf_conndb_settail: assign a new tail of the singly-linked list. 291 */ 292 void 293 npf_conndb_settail(npf_conndb_t *cd, npf_conn_t *con) 294 { 295 KASSERT(con || cd->cd_list == NULL); 296 KASSERT(!con || con->c_next == NULL); 297 cd->cd_tail = con; 298 } 299