1 /* $OpenBSD: rde_prefix.c,v 1.39 2019/07/01 07:07:08 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 memcpy(&addr->v6, &((struct pt_entry6 *)pte)->prefix6, 83 sizeof(addr->v6)); 84 /* XXX scope_id ??? */ 85 break; 86 case AID_VPN_IPv4: 87 addr->vpn4.addr = ((struct pt_entry_vpn4 *)pte)->prefix4; 88 addr->vpn4.rd = ((struct pt_entry_vpn4 *)pte)->rd; 89 addr->vpn4.labellen = ((struct pt_entry_vpn4 *)pte)->labellen; 90 memcpy(addr->vpn4.labelstack, 91 ((struct pt_entry_vpn4 *)pte)->labelstack, 92 addr->vpn4.labellen); 93 break; 94 case AID_VPN_IPv6: 95 memcpy(&addr->vpn6.addr, 96 &((struct pt_entry_vpn6 *)pte)->prefix6, 97 sizeof(addr->vpn6.addr)); 98 addr->vpn6.rd = ((struct pt_entry_vpn6 *)pte)->rd; 99 addr->vpn6.labellen = ((struct pt_entry_vpn6 *)pte)->labellen; 100 memcpy(addr->vpn6.labelstack, 101 ((struct pt_entry_vpn6 *)pte)->labelstack, 102 addr->vpn6.labellen); 103 break; 104 default: 105 fatalx("pt_getaddr: unknown af"); 106 } 107 } 108 109 struct pt_entry * 110 pt_fill(struct bgpd_addr *prefix, int prefixlen) 111 { 112 static struct pt_entry4 pte4; 113 static struct pt_entry6 pte6; 114 static struct pt_entry_vpn4 pte_vpn4; 115 static struct pt_entry_vpn6 pte_vpn6; 116 117 switch (prefix->aid) { 118 case AID_INET: 119 bzero(&pte4, sizeof(pte4)); 120 pte4.aid = prefix->aid; 121 if (prefixlen > 32) 122 fatalx("pt_fill: bad IPv4 prefixlen"); 123 inet4applymask(&pte4.prefix4, &prefix->v4, prefixlen); 124 pte4.prefixlen = prefixlen; 125 return ((struct pt_entry *)&pte4); 126 case AID_INET6: 127 bzero(&pte6, sizeof(pte6)); 128 pte6.aid = prefix->aid; 129 if (prefixlen > 128) 130 fatalx("pt_fill: bad IPv6 prefixlen"); 131 inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen); 132 pte6.prefixlen = prefixlen; 133 return ((struct pt_entry *)&pte6); 134 case AID_VPN_IPv4: 135 bzero(&pte_vpn4, sizeof(pte_vpn4)); 136 pte_vpn4.aid = prefix->aid; 137 if (prefixlen > 32) 138 fatalx("pt_fill: bad IPv4 prefixlen"); 139 inet4applymask(&pte_vpn4.prefix4, &prefix->vpn4.addr, 140 prefixlen); 141 pte_vpn4.prefixlen = prefixlen; 142 pte_vpn4.rd = prefix->vpn4.rd; 143 pte_vpn4.labellen = prefix->vpn4.labellen; 144 memcpy(pte_vpn4.labelstack, prefix->vpn4.labelstack, 145 prefix->vpn4.labellen); 146 return ((struct pt_entry *)&pte_vpn4); 147 case AID_VPN_IPv6: 148 memset(&pte_vpn6, 0, sizeof(pte_vpn6)); 149 pte_vpn6.aid = prefix->aid; 150 if (prefixlen > 128) 151 fatalx("pt_get: bad IPv6 prefixlen"); 152 inet6applymask(&pte_vpn6.prefix6, &prefix->vpn6.addr, 153 prefixlen); 154 pte_vpn6.prefixlen = prefixlen; 155 pte_vpn6.rd = prefix->vpn6.rd; 156 pte_vpn6.labellen = prefix->vpn6.labellen; 157 memcpy(pte_vpn6.labelstack, prefix->vpn6.labelstack, 158 prefix->vpn6.labellen); 159 return ((struct pt_entry *)&pte_vpn6); 160 default: 161 fatalx("pt_fill: unknown af"); 162 } 163 } 164 165 struct pt_entry * 166 pt_get(struct bgpd_addr *prefix, int prefixlen) 167 { 168 struct pt_entry *pte; 169 170 pte = pt_fill(prefix, prefixlen); 171 return RB_FIND(pt_tree, &pttable, pte); 172 } 173 174 struct pt_entry * 175 pt_add(struct bgpd_addr *prefix, int prefixlen) 176 { 177 struct pt_entry *p = NULL; 178 179 p = pt_fill(prefix, prefixlen); 180 p = pt_alloc(p); 181 182 if (RB_INSERT(pt_tree, &pttable, p) != NULL) 183 fatalx("pt_add: insert failed"); 184 185 return (p); 186 } 187 188 void 189 pt_remove(struct pt_entry *pte) 190 { 191 if (pte->refcnt != 0) 192 fatalx("pt_remove: entry still holds references"); 193 194 if (RB_REMOVE(pt_tree, &pttable, pte) == NULL) 195 log_warnx("pt_remove: remove failed."); 196 pt_free(pte); 197 } 198 199 struct pt_entry * 200 pt_lookup(struct bgpd_addr *addr) 201 { 202 struct pt_entry *p; 203 int i; 204 205 switch (addr->aid) { 206 case AID_INET: 207 case AID_VPN_IPv4: 208 i = 32; 209 break; 210 case AID_INET6: 211 case AID_VPN_IPv6: 212 i = 128; 213 break; 214 default: 215 fatalx("pt_lookup: unknown af"); 216 } 217 for (; i >= 0; i--) { 218 p = pt_get(addr, i); 219 if (p != NULL) 220 return (p); 221 } 222 return (NULL); 223 } 224 225 int 226 pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b) 227 { 228 const struct pt_entry4 *a4, *b4; 229 const struct pt_entry6 *a6, *b6; 230 const struct pt_entry_vpn4 *va4, *vb4; 231 const struct pt_entry_vpn6 *va6, *vb6; 232 int i; 233 234 if (a->aid > b->aid) 235 return (1); 236 if (a->aid < b->aid) 237 return (-1); 238 239 switch (a->aid) { 240 case AID_INET: 241 a4 = (const struct pt_entry4 *)a; 242 b4 = (const struct pt_entry4 *)b; 243 if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr)) 244 return (1); 245 if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr)) 246 return (-1); 247 if (a4->prefixlen > b4->prefixlen) 248 return (1); 249 if (a4->prefixlen < b4->prefixlen) 250 return (-1); 251 return (0); 252 case AID_INET6: 253 a6 = (const struct pt_entry6 *)a; 254 b6 = (const struct pt_entry6 *)b; 255 256 i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr)); 257 if (i > 0) 258 return (1); 259 if (i < 0) 260 return (-1); 261 if (a6->prefixlen < b6->prefixlen) 262 return (-1); 263 if (a6->prefixlen > b6->prefixlen) 264 return (1); 265 return (0); 266 case AID_VPN_IPv4: 267 va4 = (const struct pt_entry_vpn4 *)a; 268 vb4 = (const struct pt_entry_vpn4 *)b; 269 if (be64toh(va4->rd) > be64toh(vb4->rd)) 270 return (1); 271 if (be64toh(va4->rd) < be64toh(vb4->rd)) 272 return (-1); 273 if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr)) 274 return (1); 275 if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr)) 276 return (-1); 277 if (va4->prefixlen > vb4->prefixlen) 278 return (1); 279 if (va4->prefixlen < vb4->prefixlen) 280 return (-1); 281 return (0); 282 case AID_VPN_IPv6: 283 va6 = (const struct pt_entry_vpn6 *)a; 284 vb6 = (const struct pt_entry_vpn6 *)b; 285 if (be64toh(va6->rd) > be64toh(vb6->rd)) 286 return (1); 287 if (be64toh(va6->rd) < be64toh(vb6->rd)) 288 return (-1); 289 i = memcmp(&va6->prefix6, &vb6->prefix6, 290 sizeof(struct in6_addr)); 291 if (i > 0) 292 return (1); 293 if (i < 0) 294 return (-1); 295 if (va6->prefixlen > vb6->prefixlen) 296 return (1); 297 if (va6->prefixlen < vb6->prefixlen) 298 return (-1); 299 return (0); 300 default: 301 fatalx("pt_prefix_cmp: unknown af"); 302 } 303 return (-1); 304 } 305 306 /* 307 * Returns a pt_entry cloned from the one passed in. 308 * Function may not return on failure. 309 */ 310 static struct pt_entry * 311 pt_alloc(struct pt_entry *op) 312 { 313 struct pt_entry *p; 314 315 p = malloc(pt_sizes[op->aid]); 316 if (p == NULL) 317 fatal("pt_alloc"); 318 rdemem.pt_cnt[op->aid]++; 319 memcpy(p, op, pt_sizes[op->aid]); 320 321 return (p); 322 } 323 324 static void 325 pt_free(struct pt_entry *pte) 326 { 327 rdemem.pt_cnt[pte->aid]--; 328 free(pte); 329 } 330