1 /* $OpenBSD: rde_prefix.c,v 1.40 2021/01/18 12:15:36 claudio Exp $ */
2
3 /*
4 * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>
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 #include <sys/types.h>
20 #include <sys/queue.h>
21
22 #include <endian.h>
23 #include <errno.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "bgpd.h"
28 #include "rde.h"
29 #include "log.h"
30
31 /*
32 * Prefix Table functions:
33 * pt_add: create new prefix and link it into the prefix table
34 * pt_remove: Checks if there is no bgp prefix linked to the prefix,
35 * unlinks from the prefix table and frees the pt_entry.
36 * pt_get: get a prefix/prefixlen entry. While pt_lookup searches for the
37 * best matching prefix pt_get only finds the prefix/prefixlen
38 * entry. The speed of pt_get is important for the bgp updates.
39 * pt_getaddr: convert the address into a struct bgpd_addr.
40 * pt_lookup: lookup a IP in the prefix table. Mainly for "show ip bgp".
41 * pt_empty: returns true if there is no bgp prefix linked to the pt_entry.
42 * pt_init: initialize prefix table.
43 * pt_alloc: allocate a AF specific pt_entry. Internal function.
44 * pt_free: free a pt_entry. Internal function.
45 */
46
47 /* internal prototypes */
48 static struct pt_entry *pt_alloc(struct pt_entry *);
49 static void pt_free(struct pt_entry *);
50
51 size_t pt_sizes[AID_MAX] = AID_PTSIZE;
52
53 RB_HEAD(pt_tree, pt_entry);
54 RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
55 RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
56
57 struct pt_tree pttable;
58
59 void
pt_init(void)60 pt_init(void)
61 {
62 RB_INIT(&pttable);
63 }
64
65 void
pt_shutdown(void)66 pt_shutdown(void)
67 {
68 if (!RB_EMPTY(&pttable))
69 log_debug("pt_shutdown: tree is not empty.");
70 }
71
72 void
pt_getaddr(struct pt_entry * pte,struct bgpd_addr * addr)73 pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
74 {
75 bzero(addr, sizeof(struct bgpd_addr));
76 addr->aid = pte->aid;
77 switch (addr->aid) {
78 case AID_INET:
79 addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
80 break;
81 case AID_INET6:
82 addr->v6 = ((struct pt_entry6 *)pte)->prefix6;
83 /* XXX scope_id ??? */
84 break;
85 case AID_VPN_IPv4:
86 addr->v4 = ((struct pt_entry_vpn4 *)pte)->prefix4;
87 addr->rd = ((struct pt_entry_vpn4 *)pte)->rd;
88 addr->labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
89 memcpy(addr->labelstack,
90 ((struct pt_entry_vpn4 *)pte)->labelstack,
91 addr->labellen);
92 break;
93 case AID_VPN_IPv6:
94 addr->v6 = ((struct pt_entry_vpn6 *)pte)->prefix6;
95 addr->rd = ((struct pt_entry_vpn6 *)pte)->rd;
96 addr->labellen = ((struct pt_entry_vpn6 *)pte)->labellen;
97 memcpy(addr->labelstack,
98 ((struct pt_entry_vpn6 *)pte)->labelstack,
99 addr->labellen);
100 break;
101 default:
102 fatalx("pt_getaddr: unknown af");
103 }
104 }
105
106 struct pt_entry *
pt_fill(struct bgpd_addr * prefix,int prefixlen)107 pt_fill(struct bgpd_addr *prefix, int prefixlen)
108 {
109 static struct pt_entry4 pte4;
110 static struct pt_entry6 pte6;
111 static struct pt_entry_vpn4 pte_vpn4;
112 static struct pt_entry_vpn6 pte_vpn6;
113
114 switch (prefix->aid) {
115 case AID_INET:
116 bzero(&pte4, sizeof(pte4));
117 pte4.aid = prefix->aid;
118 if (prefixlen > 32)
119 fatalx("pt_fill: bad IPv4 prefixlen");
120 inet4applymask(&pte4.prefix4, &prefix->v4, prefixlen);
121 pte4.prefixlen = prefixlen;
122 return ((struct pt_entry *)&pte4);
123 case AID_INET6:
124 bzero(&pte6, sizeof(pte6));
125 pte6.aid = prefix->aid;
126 if (prefixlen > 128)
127 fatalx("pt_fill: bad IPv6 prefixlen");
128 inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
129 pte6.prefixlen = prefixlen;
130 return ((struct pt_entry *)&pte6);
131 case AID_VPN_IPv4:
132 bzero(&pte_vpn4, sizeof(pte_vpn4));
133 pte_vpn4.aid = prefix->aid;
134 if (prefixlen > 32)
135 fatalx("pt_fill: bad IPv4 prefixlen");
136 inet4applymask(&pte_vpn4.prefix4, &prefix->v4, prefixlen);
137 pte_vpn4.prefixlen = prefixlen;
138 pte_vpn4.rd = prefix->rd;
139 pte_vpn4.labellen = prefix->labellen;
140 memcpy(pte_vpn4.labelstack, prefix->labelstack,
141 prefix->labellen);
142 return ((struct pt_entry *)&pte_vpn4);
143 case AID_VPN_IPv6:
144 memset(&pte_vpn6, 0, sizeof(pte_vpn6));
145 pte_vpn6.aid = prefix->aid;
146 if (prefixlen > 128)
147 fatalx("pt_get: bad IPv6 prefixlen");
148 inet6applymask(&pte_vpn6.prefix6, &prefix->v6, prefixlen);
149 pte_vpn6.prefixlen = prefixlen;
150 pte_vpn6.rd = prefix->rd;
151 pte_vpn6.labellen = prefix->labellen;
152 memcpy(pte_vpn6.labelstack, prefix->labelstack,
153 prefix->labellen);
154 return ((struct pt_entry *)&pte_vpn6);
155 default:
156 fatalx("pt_fill: unknown af");
157 }
158 }
159
160 struct pt_entry *
pt_get(struct bgpd_addr * prefix,int prefixlen)161 pt_get(struct bgpd_addr *prefix, int prefixlen)
162 {
163 struct pt_entry *pte;
164
165 pte = pt_fill(prefix, prefixlen);
166 return RB_FIND(pt_tree, &pttable, pte);
167 }
168
169 struct pt_entry *
pt_add(struct bgpd_addr * prefix,int prefixlen)170 pt_add(struct bgpd_addr *prefix, int prefixlen)
171 {
172 struct pt_entry *p = NULL;
173
174 p = pt_fill(prefix, prefixlen);
175 p = pt_alloc(p);
176
177 if (RB_INSERT(pt_tree, &pttable, p) != NULL)
178 fatalx("pt_add: insert failed");
179
180 return (p);
181 }
182
183 void
pt_remove(struct pt_entry * pte)184 pt_remove(struct pt_entry *pte)
185 {
186 if (pte->refcnt != 0)
187 fatalx("pt_remove: entry still holds references");
188
189 if (RB_REMOVE(pt_tree, &pttable, pte) == NULL)
190 log_warnx("pt_remove: remove failed.");
191 pt_free(pte);
192 }
193
194 struct pt_entry *
pt_lookup(struct bgpd_addr * addr)195 pt_lookup(struct bgpd_addr *addr)
196 {
197 struct pt_entry *p;
198 int i;
199
200 switch (addr->aid) {
201 case AID_INET:
202 case AID_VPN_IPv4:
203 i = 32;
204 break;
205 case AID_INET6:
206 case AID_VPN_IPv6:
207 i = 128;
208 break;
209 default:
210 fatalx("pt_lookup: unknown af");
211 }
212 for (; i >= 0; i--) {
213 p = pt_get(addr, i);
214 if (p != NULL)
215 return (p);
216 }
217 return (NULL);
218 }
219
220 int
pt_prefix_cmp(const struct pt_entry * a,const struct pt_entry * b)221 pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
222 {
223 const struct pt_entry4 *a4, *b4;
224 const struct pt_entry6 *a6, *b6;
225 const struct pt_entry_vpn4 *va4, *vb4;
226 const struct pt_entry_vpn6 *va6, *vb6;
227 int i;
228
229 if (a->aid > b->aid)
230 return (1);
231 if (a->aid < b->aid)
232 return (-1);
233
234 switch (a->aid) {
235 case AID_INET:
236 a4 = (const struct pt_entry4 *)a;
237 b4 = (const struct pt_entry4 *)b;
238 if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
239 return (1);
240 if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
241 return (-1);
242 if (a4->prefixlen > b4->prefixlen)
243 return (1);
244 if (a4->prefixlen < b4->prefixlen)
245 return (-1);
246 return (0);
247 case AID_INET6:
248 a6 = (const struct pt_entry6 *)a;
249 b6 = (const struct pt_entry6 *)b;
250
251 i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
252 if (i > 0)
253 return (1);
254 if (i < 0)
255 return (-1);
256 if (a6->prefixlen < b6->prefixlen)
257 return (-1);
258 if (a6->prefixlen > b6->prefixlen)
259 return (1);
260 return (0);
261 case AID_VPN_IPv4:
262 va4 = (const struct pt_entry_vpn4 *)a;
263 vb4 = (const struct pt_entry_vpn4 *)b;
264 if (be64toh(va4->rd) > be64toh(vb4->rd))
265 return (1);
266 if (be64toh(va4->rd) < be64toh(vb4->rd))
267 return (-1);
268 if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
269 return (1);
270 if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
271 return (-1);
272 if (va4->prefixlen > vb4->prefixlen)
273 return (1);
274 if (va4->prefixlen < vb4->prefixlen)
275 return (-1);
276 return (0);
277 case AID_VPN_IPv6:
278 va6 = (const struct pt_entry_vpn6 *)a;
279 vb6 = (const struct pt_entry_vpn6 *)b;
280 if (be64toh(va6->rd) > be64toh(vb6->rd))
281 return (1);
282 if (be64toh(va6->rd) < be64toh(vb6->rd))
283 return (-1);
284 i = memcmp(&va6->prefix6, &vb6->prefix6,
285 sizeof(struct in6_addr));
286 if (i > 0)
287 return (1);
288 if (i < 0)
289 return (-1);
290 if (va6->prefixlen > vb6->prefixlen)
291 return (1);
292 if (va6->prefixlen < vb6->prefixlen)
293 return (-1);
294 return (0);
295 default:
296 fatalx("pt_prefix_cmp: unknown af");
297 }
298 return (-1);
299 }
300
301 /*
302 * Returns a pt_entry cloned from the one passed in.
303 * Function may not return on failure.
304 */
305 static struct pt_entry *
pt_alloc(struct pt_entry * op)306 pt_alloc(struct pt_entry *op)
307 {
308 struct pt_entry *p;
309
310 p = malloc(pt_sizes[op->aid]);
311 if (p == NULL)
312 fatal("pt_alloc");
313 rdemem.pt_cnt[op->aid]++;
314 memcpy(p, op, pt_sizes[op->aid]);
315
316 return (p);
317 }
318
319 static void
pt_free(struct pt_entry * pte)320 pt_free(struct pt_entry *pte)
321 {
322 rdemem.pt_cnt[pte->aid]--;
323 free(pte);
324 }
325