1 /* $OpenBSD: art.h,v 1.25 2023/11/11 12:17:50 bluhm Exp $ */ 2 3 /* 4 * Copyright (c) 2015 Martin Pieuchot 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #ifndef _NET_ART_H_ 20 #define _NET_ART_H_ 21 22 #include <sys/rwlock.h> 23 #include <sys/srp.h> 24 25 #define ART_MAXLVL 32 /* We currently use 32 levels for IPv6. */ 26 27 /* 28 * Root of the ART tables, equivalent to the radix head. 29 * 30 * Locks used to protect struct members in this file: 31 * I immutable after creation 32 * l root's `ar_lock' 33 * K kernel lock 34 * For SRP related structures that allow lock-free reads, the write lock 35 * is indicated below. 36 */ 37 struct art_root { 38 struct srp ar_root; /* [l] First table */ 39 struct rwlock ar_lock; /* [] Serialise modifications */ 40 uint8_t ar_bits[ART_MAXLVL]; /* [I] Per level stride */ 41 uint8_t ar_nlvl; /* [I] Number of levels */ 42 uint8_t ar_alen; /* [I] Address length in bits */ 43 uint8_t ar_off; /* [I] Offset of key in bytes */ 44 struct sockaddr *ar_source; /* [N] use optional src addr */ 45 }; 46 47 #define ISLEAF(e) (((unsigned long)(e) & 1) == 0) 48 #define SUBTABLE(e) ((struct art_table *)((unsigned long)(e) & ~1)) 49 #define ASNODE(t) ((struct art_node *)((unsigned long)(t) | 1)) 50 51 /* 52 * Allotment Table. 53 */ 54 struct art_table { 55 struct art_table *at_parent; /* Parent table */ 56 uint32_t at_index; /* Index in the parent table */ 57 uint32_t at_minfringe; /* Index that fringe begins */ 58 uint32_t at_level; /* Level of the table */ 59 uint8_t at_bits; /* Stride length of the table */ 60 uint8_t at_offset; /* Sum of parents' stride len */ 61 62 /* 63 * Items stored in the heap are pointers to nodes, in the leaf 64 * case, or tables otherwise. One exception is index 0 which 65 * is a route counter. 66 */ 67 union { 68 struct srp node; 69 unsigned long count; 70 } *at_heap; /* Array of 2^(slen+1) items */ 71 }; 72 #define at_refcnt at_heap[0].count/* Refcounter (1 per different route) */ 73 #define at_default at_heap[1].node /* Default route (was in parent heap) */ 74 75 /* Heap size for an ART table of stride length ``slen''. */ 76 #define AT_HEAPSIZE(slen) ((1 << ((slen) + 1)) * sizeof(void *)) 77 78 /* 79 * Forward declaration needed for the list of mpath routes 80 * attached to a single ART node. 81 */ 82 struct rtentry; 83 84 /* 85 * A node is the internal representation of a route entry. 86 */ 87 struct art_node { 88 union { 89 SRPL_HEAD(, rtentry) an__rtlist; /* Route related to this node */ 90 struct art_node *an__gc; /* Entry on GC list */ 91 } an_pointer; 92 uint8_t an_plen; /* Prefix length */ 93 }; 94 #define an_rtlist an_pointer.an__rtlist 95 #define an_gc an_pointer.an__gc 96 97 void art_init(void); 98 struct art_root *art_alloc(unsigned int, unsigned int, unsigned int); 99 struct art_node *art_insert(struct art_root *, struct art_node *, const void *, 100 int); 101 struct art_node *art_delete(struct art_root *, struct art_node *, const void *, 102 int); 103 struct art_node *art_match(struct art_root *, const void *, struct srp_ref *); 104 struct art_node *art_lookup(struct art_root *, const void *, int, 105 struct srp_ref *); 106 int art_walk(struct art_root *, 107 int (*)(struct art_node *, void *), void *); 108 109 struct art_node *art_get(uint8_t); 110 void art_put(struct art_node *); 111 112 #endif /* _NET_ART_H_ */ 113