1/* $OpenBSD: art.h,v 1.28 2025/07/10 05:28:13 dlg 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/*
23 * Allotment Routing Table (ART)
24 *
25 * Yoichi Hariguchi paper can be found at:
26 * http://www.hariguchi.org/art/art.pdf
27 *
28 * Locking:
29 *
30 * Modification (ie, art_insert or art_delete) and iteration
31 * (art_iter_next, etc) over the ART must be serialised by the caller.
32 * Lookups (ie, art_match and art_lookup) run within an SMR critical
33 * section.
34 *
35 * Iteration requires serialisation as it manipulates the reference
36 * counts on tables as it traverses the tree. The iterator maintains
37 * these references until it runs out of entries. This allows code
38 * iterating over the ART to release locks in between calls to
39 * art_iter_open and art_iter_next. The references may be dropped
40 * early with art_iter_close.
41 *
42 * Note, the iterator does not hold a reference to the art_node
43 * structure or the data hanging off the an_value pointer, they must
44 * be accounted for separately or their use must be serialised with
45 * art_delete.
46 */
47
48typedef uintptr_t art_heap_entry;
49
50/*
51 * Root of the ART, equivalent to the radix head.
52 */
53
54struct art {
55 art_heap_entry *art_root;
56 const unsigned int *art_levels;
57 unsigned int art_nlevels;
58 unsigned int art_alen;
59};
60
61/*
62 * Allotment Table.
63 */
64struct art_table {
65 art_heap_entry *at_heap;
66 struct art_table *at_parent; /* Parent table */
67
68 unsigned int at_index; /* Index in the parent table */
69 unsigned int at_minfringe; /* Index that fringe begins */
70
71 unsigned int at_level; /* Level of the table */
72 unsigned int at_bits; /* Stride length of the table */
73 unsigned int at_offset; /* Sum of parents' stride len */
74
75 unsigned int at_refcnt;
76};
77
78#define ART_HEAP_IDX_TABLE 0
79#define ART_HEAP_IDX_DEFAULT 1
80
81#define AT_HEAPSIZE(bits) ((1 << ((bits) + 1)) * sizeof(art_heap_entry))
82
83/*
84 * A node is the internal representation of a route entry.
85 */
86struct art_node {
87 void *an_value;
88 union {
89 struct art_node *an__gc;
90 uint8_t an__addr[16];
91 } an__u;
92#define an_gc an__u.an__gc
93#define an_addr an__u.an__addr
94 unsigned int an_plen;
95};
96
97static inline struct art_table *
98art_heap_to_table(art_heap_entry *heap)
99{
100 return ((struct art_table *)heap[ART_HEAP_IDX_TABLE]);
101}
102
103static inline int
104art_heap_entry_is_node(art_heap_entry ahe)
105{
106 return ((ahe & 1UL) == 0);
107}
108
109static inline struct art_node *
110art_heap_entry_to_node(art_heap_entry ahe)
111{
112 return ((struct art_node *)ahe);
113}
114
115static inline art_heap_entry *
116art_heap_entry_to_heap(art_heap_entry ahe)
117{
118 return ((art_heap_entry *)(ahe & ~1UL));
119}
120
121static inline art_heap_entry
122art_node_to_heap_entry(struct art_node *an)
123{
124 return ((art_heap_entry)an);
125}
126
127static inline art_heap_entry
128art_heap_to_heap_entry(art_heap_entry *heap)
129{
130 return ((art_heap_entry)heap | 1UL);
131}
132
133#ifdef _KERNEL
134void art_boot(void);
135struct art *art_alloc(unsigned int);
136void art_init(struct art *, unsigned int);
137struct art_node *art_insert(struct art *, struct art_node *);
138struct art_node *art_delete(struct art *, const void *, unsigned int);
139struct art_node *art_match(struct art *, const void *);
140struct art_node *art_lookup(struct art *, const void *, unsigned int);
141int art_is_empty(struct art *);
142
143struct art_node *art_get(const uint8_t *, unsigned int);
144void art_node_init(struct art_node *,
145 const uint8_t *, unsigned int);
146void art_put(struct art_node *);
147
148struct art_iter {
149 struct art *ai_art;
150 struct art_table *ai_table;
151 unsigned int ai_j;
152 unsigned int ai_i;
153};
154
155struct art_node *art_iter_open(struct art *, struct art_iter *);
156struct art_node *art_iter_next(struct art_iter *);
157void art_iter_close(struct art_iter *);
158
159#define ART_FOREACH(_an, _art, _ai) \
160 for ((_an) = art_iter_open((_art), (_ai)); \
161 (_an) != NULL; \
162 (_an) = art_iter_next((_ai)))
163
164int art_walk(struct art *,
165 int (*)(struct art_node *, void *), void *);
166
167#endif /* _KERNEL */
168
169#endif /* _NET_ART_H_ */