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