1 /* $OpenBSD: art.h,v 1.18 2019/03/31 14:03:40 mpi 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 struct art_root { 31 struct srp ar_root; /* First table */ 32 struct rwlock ar_lock; /* Serialise modifications */ 33 uint8_t ar_bits[ART_MAXLVL]; /* Per level stride */ 34 uint8_t ar_nlvl; /* Number of levels */ 35 uint8_t ar_alen; /* Address length in bits */ 36 uint8_t ar_off; /* Offset of the key in bytes */ 37 unsigned int ar_rtableid; /* ID of this routing table */ 38 }; 39 40 #define ISLEAF(e) (((unsigned long)(e) & 1) == 0) 41 #define SUBTABLE(e) ((struct art_table *)((unsigned long)(e) & ~1)) 42 #define ASNODE(t) ((struct art_node *)((unsigned long)(t) | 1)) 43 44 /* 45 * Allotment Table. 46 */ 47 struct art_table { 48 struct art_table *at_parent; /* Parent table */ 49 uint32_t at_index; /* Index in the parent table */ 50 uint32_t at_minfringe; /* Index that fringe begins */ 51 uint32_t at_level; /* Level of the table */ 52 uint8_t at_bits; /* Stride length of the table */ 53 uint8_t at_offset; /* Sum of parents' stride len */ 54 55 /* 56 * Items stored in the heap are pointers to nodes, in the leaf 57 * case, or tables otherwise. One exception is index 0 which 58 * is a route counter. 59 */ 60 union { 61 struct srp node; 62 unsigned long count; 63 } *at_heap; /* Array of 2^(slen+1) items */ 64 }; 65 #define at_refcnt at_heap[0].count/* Refcounter (1 per different route) */ 66 #define at_default at_heap[1].node /* Default route (was in parent heap) */ 67 68 /* Heap size for an ART table of stride length ``slen''. */ 69 #define AT_HEAPSIZE(slen) ((1 << ((slen) + 1)) * sizeof(void *)) 70 71 /* 72 * Forward declaration needed for the list of mpath routes 73 * attached to a single ART node. 74 */ 75 struct rtentry; 76 77 /* 78 * A node is the internal representation of a route entry. 79 */ 80 struct art_node { 81 union { 82 SRPL_HEAD(, rtentry) an__rtlist; /* Route related to this node */ 83 struct art_node *an__gc; /* Entry on GC list */ 84 } an_pointer; 85 uint8_t an_plen; /* Prefix length */ 86 }; 87 #define an_rtlist an_pointer.an__rtlist 88 #define an_gc an_pointer.an__gc 89 90 void art_init(void); 91 struct art_root *art_alloc(unsigned int, unsigned int, unsigned int); 92 struct art_node *art_insert(struct art_root *, struct art_node *, void *, 93 int); 94 struct art_node *art_delete(struct art_root *, struct art_node *, void *, 95 int); 96 struct art_node *art_match(struct art_root *, void *, struct srp_ref *); 97 struct art_node *art_lookup(struct art_root *, void *, int, 98 struct srp_ref *); 99 int art_walk(struct art_root *, 100 int (*)(struct art_node *, void *), void *); 101 102 struct art_node *art_get(void *, uint8_t); 103 void art_put(struct art_node *); 104 105 #endif /* _NET_ART_H_ */ 106