1 /* 2 * Longest prefix match list implementation 3 * 4 * Copyright (c) 2016,2017 Daniel Mack 5 * Copyright (c) 2016 David Herrmann 6 * 7 * This file is subject to the terms and conditions of version 2 of the GNU 8 * General Public License. See the file COPYING in the main directory of the 9 * Linux distribution for more details. 10 */ 11 12 #include <linux/bpf.h> 13 #include <linux/err.h> 14 #include <linux/slab.h> 15 #include <linux/spinlock.h> 16 #include <linux/vmalloc.h> 17 #include <net/ipv6.h> 18 19 /* Intermediate node */ 20 #define LPM_TREE_NODE_FLAG_IM BIT(0) 21 22 struct lpm_trie_node; 23 24 struct lpm_trie_node { 25 struct rcu_head rcu; 26 struct lpm_trie_node __rcu *child[2]; 27 u32 prefixlen; 28 u32 flags; 29 u8 data[0]; 30 }; 31 32 struct lpm_trie { 33 struct bpf_map map; 34 struct lpm_trie_node __rcu *root; 35 size_t n_entries; 36 size_t max_prefixlen; 37 size_t data_size; 38 raw_spinlock_t lock; 39 }; 40 41 /* This trie implements a longest prefix match algorithm that can be used to 42 * match IP addresses to a stored set of ranges. 43 * 44 * Data stored in @data of struct bpf_lpm_key and struct lpm_trie_node is 45 * interpreted as big endian, so data[0] stores the most significant byte. 46 * 47 * Match ranges are internally stored in instances of struct lpm_trie_node 48 * which each contain their prefix length as well as two pointers that may 49 * lead to more nodes containing more specific matches. Each node also stores 50 * a value that is defined by and returned to userspace via the update_elem 51 * and lookup functions. 52 * 53 * For instance, let's start with a trie that was created with a prefix length 54 * of 32, so it can be used for IPv4 addresses, and one single element that 55 * matches 192.168.0.0/16. The data array would hence contain 56 * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will 57 * stick to IP-address notation for readability though. 58 * 59 * As the trie is empty initially, the new node (1) will be places as root 60 * node, denoted as (R) in the example below. As there are no other node, both 61 * child pointers are %NULL. 62 * 63 * +----------------+ 64 * | (1) (R) | 65 * | 192.168.0.0/16 | 66 * | value: 1 | 67 * | [0] [1] | 68 * +----------------+ 69 * 70 * Next, let's add a new node (2) matching 192.168.0.0/24. As there is already 71 * a node with the same data and a smaller prefix (ie, a less specific one), 72 * node (2) will become a child of (1). In child index depends on the next bit 73 * that is outside of what (1) matches, and that bit is 0, so (2) will be 74 * child[0] of (1): 75 * 76 * +----------------+ 77 * | (1) (R) | 78 * | 192.168.0.0/16 | 79 * | value: 1 | 80 * | [0] [1] | 81 * +----------------+ 82 * | 83 * +----------------+ 84 * | (2) | 85 * | 192.168.0.0/24 | 86 * | value: 2 | 87 * | [0] [1] | 88 * +----------------+ 89 * 90 * The child[1] slot of (1) could be filled with another node which has bit #17 91 * (the next bit after the ones that (1) matches on) set to 1. For instance, 92 * 192.168.128.0/24: 93 * 94 * +----------------+ 95 * | (1) (R) | 96 * | 192.168.0.0/16 | 97 * | value: 1 | 98 * | [0] [1] | 99 * +----------------+ 100 * | | 101 * +----------------+ +------------------+ 102 * | (2) | | (3) | 103 * | 192.168.0.0/24 | | 192.168.128.0/24 | 104 * | value: 2 | | value: 3 | 105 * | [0] [1] | | [0] [1] | 106 * +----------------+ +------------------+ 107 * 108 * Let's add another node (4) to the game for 192.168.1.0/24. In order to place 109 * it, node (1) is looked at first, and because (4) of the semantics laid out 110 * above (bit #17 is 0), it would normally be attached to (1) as child[0]. 111 * However, that slot is already allocated, so a new node is needed in between. 112 * That node does not have a value attached to it and it will never be 113 * returned to users as result of a lookup. It is only there to differentiate 114 * the traversal further. It will get a prefix as wide as necessary to 115 * distinguish its two children: 116 * 117 * +----------------+ 118 * | (1) (R) | 119 * | 192.168.0.0/16 | 120 * | value: 1 | 121 * | [0] [1] | 122 * +----------------+ 123 * | | 124 * +----------------+ +------------------+ 125 * | (4) (I) | | (3) | 126 * | 192.168.0.0/23 | | 192.168.128.0/24 | 127 * | value: --- | | value: 3 | 128 * | [0] [1] | | [0] [1] | 129 * +----------------+ +------------------+ 130 * | | 131 * +----------------+ +----------------+ 132 * | (2) | | (5) | 133 * | 192.168.0.0/24 | | 192.168.1.0/24 | 134 * | value: 2 | | value: 5 | 135 * | [0] [1] | | [0] [1] | 136 * +----------------+ +----------------+ 137 * 138 * 192.168.1.1/32 would be a child of (5) etc. 139 * 140 * An intermediate node will be turned into a 'real' node on demand. In the 141 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie. 142 * 143 * A fully populated trie would have a height of 32 nodes, as the trie was 144 * created with a prefix length of 32. 145 * 146 * The lookup starts at the root node. If the current node matches and if there 147 * is a child that can be used to become more specific, the trie is traversed 148 * downwards. The last node in the traversal that is a non-intermediate one is 149 * returned. 150 */ 151 152 static inline int extract_bit(const u8 *data, size_t index) 153 { 154 return !!(data[index / 8] & (1 << (7 - (index % 8)))); 155 } 156 157 /** 158 * longest_prefix_match() - determine the longest prefix 159 * @trie: The trie to get internal sizes from 160 * @node: The node to operate on 161 * @key: The key to compare to @node 162 * 163 * Determine the longest prefix of @node that matches the bits in @key. 164 */ 165 static size_t longest_prefix_match(const struct lpm_trie *trie, 166 const struct lpm_trie_node *node, 167 const struct bpf_lpm_trie_key *key) 168 { 169 size_t prefixlen = 0; 170 size_t i; 171 172 for (i = 0; i < trie->data_size; i++) { 173 size_t b; 174 175 b = 8 - fls(node->data[i] ^ key->data[i]); 176 prefixlen += b; 177 178 if (prefixlen >= node->prefixlen || prefixlen >= key->prefixlen) 179 return min(node->prefixlen, key->prefixlen); 180 181 if (b < 8) 182 break; 183 } 184 185 return prefixlen; 186 } 187 188 /* Called from syscall or from eBPF program */ 189 static void *trie_lookup_elem(struct bpf_map *map, void *_key) 190 { 191 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); 192 struct lpm_trie_node *node, *found = NULL; 193 struct bpf_lpm_trie_key *key = _key; 194 195 /* Start walking the trie from the root node ... */ 196 197 for (node = rcu_dereference(trie->root); node;) { 198 unsigned int next_bit; 199 size_t matchlen; 200 201 /* Determine the longest prefix of @node that matches @key. 202 * If it's the maximum possible prefix for this trie, we have 203 * an exact match and can return it directly. 204 */ 205 matchlen = longest_prefix_match(trie, node, key); 206 if (matchlen == trie->max_prefixlen) { 207 found = node; 208 break; 209 } 210 211 /* If the number of bits that match is smaller than the prefix 212 * length of @node, bail out and return the node we have seen 213 * last in the traversal (ie, the parent). 214 */ 215 if (matchlen < node->prefixlen) 216 break; 217 218 /* Consider this node as return candidate unless it is an 219 * artificially added intermediate one. 220 */ 221 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) 222 found = node; 223 224 /* If the node match is fully satisfied, let's see if we can 225 * become more specific. Determine the next bit in the key and 226 * traverse down. 227 */ 228 next_bit = extract_bit(key->data, node->prefixlen); 229 node = rcu_dereference(node->child[next_bit]); 230 } 231 232 if (!found) 233 return NULL; 234 235 return found->data + trie->data_size; 236 } 237 238 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie, 239 const void *value) 240 { 241 struct lpm_trie_node *node; 242 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; 243 244 if (value) 245 size += trie->map.value_size; 246 247 node = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN); 248 if (!node) 249 return NULL; 250 251 node->flags = 0; 252 253 if (value) 254 memcpy(node->data + trie->data_size, value, 255 trie->map.value_size); 256 257 return node; 258 } 259 260 /* Called from syscall or from eBPF program */ 261 static int trie_update_elem(struct bpf_map *map, 262 void *_key, void *value, u64 flags) 263 { 264 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); 265 struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL; 266 struct lpm_trie_node __rcu **slot; 267 struct bpf_lpm_trie_key *key = _key; 268 unsigned long irq_flags; 269 unsigned int next_bit; 270 size_t matchlen = 0; 271 int ret = 0; 272 273 if (unlikely(flags > BPF_EXIST)) 274 return -EINVAL; 275 276 if (key->prefixlen > trie->max_prefixlen) 277 return -EINVAL; 278 279 raw_spin_lock_irqsave(&trie->lock, irq_flags); 280 281 /* Allocate and fill a new node */ 282 283 if (trie->n_entries == trie->map.max_entries) { 284 ret = -ENOSPC; 285 goto out; 286 } 287 288 new_node = lpm_trie_node_alloc(trie, value); 289 if (!new_node) { 290 ret = -ENOMEM; 291 goto out; 292 } 293 294 trie->n_entries++; 295 296 new_node->prefixlen = key->prefixlen; 297 RCU_INIT_POINTER(new_node->child[0], NULL); 298 RCU_INIT_POINTER(new_node->child[1], NULL); 299 memcpy(new_node->data, key->data, trie->data_size); 300 301 /* Now find a slot to attach the new node. To do that, walk the tree 302 * from the root and match as many bits as possible for each node until 303 * we either find an empty slot or a slot that needs to be replaced by 304 * an intermediate node. 305 */ 306 slot = &trie->root; 307 308 while ((node = rcu_dereference_protected(*slot, 309 lockdep_is_held(&trie->lock)))) { 310 matchlen = longest_prefix_match(trie, node, key); 311 312 if (node->prefixlen != matchlen || 313 node->prefixlen == key->prefixlen || 314 node->prefixlen == trie->max_prefixlen) 315 break; 316 317 next_bit = extract_bit(key->data, node->prefixlen); 318 slot = &node->child[next_bit]; 319 } 320 321 /* If the slot is empty (a free child pointer or an empty root), 322 * simply assign the @new_node to that slot and be done. 323 */ 324 if (!node) { 325 rcu_assign_pointer(*slot, new_node); 326 goto out; 327 } 328 329 /* If the slot we picked already exists, replace it with @new_node 330 * which already has the correct data array set. 331 */ 332 if (node->prefixlen == matchlen) { 333 new_node->child[0] = node->child[0]; 334 new_node->child[1] = node->child[1]; 335 336 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) 337 trie->n_entries--; 338 339 rcu_assign_pointer(*slot, new_node); 340 kfree_rcu(node, rcu); 341 342 goto out; 343 } 344 345 /* If the new node matches the prefix completely, it must be inserted 346 * as an ancestor. Simply insert it between @node and *@slot. 347 */ 348 if (matchlen == key->prefixlen) { 349 next_bit = extract_bit(node->data, matchlen); 350 rcu_assign_pointer(new_node->child[next_bit], node); 351 rcu_assign_pointer(*slot, new_node); 352 goto out; 353 } 354 355 im_node = lpm_trie_node_alloc(trie, NULL); 356 if (!im_node) { 357 ret = -ENOMEM; 358 goto out; 359 } 360 361 im_node->prefixlen = matchlen; 362 im_node->flags |= LPM_TREE_NODE_FLAG_IM; 363 memcpy(im_node->data, node->data, trie->data_size); 364 365 /* Now determine which child to install in which slot */ 366 if (extract_bit(key->data, matchlen)) { 367 rcu_assign_pointer(im_node->child[0], node); 368 rcu_assign_pointer(im_node->child[1], new_node); 369 } else { 370 rcu_assign_pointer(im_node->child[0], new_node); 371 rcu_assign_pointer(im_node->child[1], node); 372 } 373 374 /* Finally, assign the intermediate node to the determined spot */ 375 rcu_assign_pointer(*slot, im_node); 376 377 out: 378 if (ret) { 379 if (new_node) 380 trie->n_entries--; 381 382 kfree(new_node); 383 kfree(im_node); 384 } 385 386 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); 387 388 return ret; 389 } 390 391 static int trie_delete_elem(struct bpf_map *map, void *key) 392 { 393 /* TODO */ 394 return -ENOSYS; 395 } 396 397 #define LPM_DATA_SIZE_MAX 256 398 #define LPM_DATA_SIZE_MIN 1 399 400 #define LPM_VAL_SIZE_MAX (KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \ 401 sizeof(struct lpm_trie_node)) 402 #define LPM_VAL_SIZE_MIN 1 403 404 #define LPM_KEY_SIZE(X) (sizeof(struct bpf_lpm_trie_key) + (X)) 405 #define LPM_KEY_SIZE_MAX LPM_KEY_SIZE(LPM_DATA_SIZE_MAX) 406 #define LPM_KEY_SIZE_MIN LPM_KEY_SIZE(LPM_DATA_SIZE_MIN) 407 408 static struct bpf_map *trie_alloc(union bpf_attr *attr) 409 { 410 struct lpm_trie *trie; 411 u64 cost = sizeof(*trie), cost_per_node; 412 int ret; 413 414 if (!capable(CAP_SYS_ADMIN)) 415 return ERR_PTR(-EPERM); 416 417 /* check sanity of attributes */ 418 if (attr->max_entries == 0 || 419 attr->map_flags != BPF_F_NO_PREALLOC || 420 attr->key_size < LPM_KEY_SIZE_MIN || 421 attr->key_size > LPM_KEY_SIZE_MAX || 422 attr->value_size < LPM_VAL_SIZE_MIN || 423 attr->value_size > LPM_VAL_SIZE_MAX) 424 return ERR_PTR(-EINVAL); 425 426 trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN); 427 if (!trie) 428 return ERR_PTR(-ENOMEM); 429 430 /* copy mandatory map attributes */ 431 trie->map.map_type = attr->map_type; 432 trie->map.key_size = attr->key_size; 433 trie->map.value_size = attr->value_size; 434 trie->map.max_entries = attr->max_entries; 435 trie->data_size = attr->key_size - 436 offsetof(struct bpf_lpm_trie_key, data); 437 trie->max_prefixlen = trie->data_size * 8; 438 439 cost_per_node = sizeof(struct lpm_trie_node) + 440 attr->value_size + trie->data_size; 441 cost += (u64) attr->max_entries * cost_per_node; 442 if (cost >= U32_MAX - PAGE_SIZE) { 443 ret = -E2BIG; 444 goto out_err; 445 } 446 447 trie->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT; 448 449 ret = bpf_map_precharge_memlock(trie->map.pages); 450 if (ret) 451 goto out_err; 452 453 raw_spin_lock_init(&trie->lock); 454 455 return &trie->map; 456 out_err: 457 kfree(trie); 458 return ERR_PTR(ret); 459 } 460 461 static void trie_free(struct bpf_map *map) 462 { 463 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); 464 struct lpm_trie_node __rcu **slot; 465 struct lpm_trie_node *node; 466 467 raw_spin_lock(&trie->lock); 468 469 /* Always start at the root and walk down to a node that has no 470 * children. Then free that node, nullify its reference in the parent 471 * and start over. 472 */ 473 474 for (;;) { 475 slot = &trie->root; 476 477 for (;;) { 478 node = rcu_dereference_protected(*slot, 479 lockdep_is_held(&trie->lock)); 480 if (!node) 481 goto unlock; 482 483 if (rcu_access_pointer(node->child[0])) { 484 slot = &node->child[0]; 485 continue; 486 } 487 488 if (rcu_access_pointer(node->child[1])) { 489 slot = &node->child[1]; 490 continue; 491 } 492 493 kfree(node); 494 RCU_INIT_POINTER(*slot, NULL); 495 break; 496 } 497 } 498 499 unlock: 500 raw_spin_unlock(&trie->lock); 501 } 502 503 static int trie_get_next_key(struct bpf_map *map, void *key, void *next_key) 504 { 505 return -ENOTSUPP; 506 } 507 508 const struct bpf_map_ops trie_map_ops = { 509 .map_alloc = trie_alloc, 510 .map_free = trie_free, 511 .map_get_next_key = trie_get_next_key, 512 .map_lookup_elem = trie_lookup_elem, 513 .map_update_elem = trie_update_elem, 514 .map_delete_elem = trie_delete_elem, 515 }; 516