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 60 pt_init(void) 61 { 62 RB_INIT(&pttable); 63 } 64 65 void 66 pt_shutdown(void) 67 { 68 if (!RB_EMPTY(&pttable)) 69 log_debug("pt_shutdown: tree is not empty."); 70 } 71 72 void 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 * 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 * 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 * 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 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 * 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 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 * 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 320 pt_free(struct pt_entry *pte) 321 { 322 rdemem.pt_cnt[pte->aid]--; 323 free(pte); 324 } 325