1/* BGP routing table 2 Copyright (C) 1998, 2001 Kunihiro Ishiguro 3 4This file is part of GNU Zebra. 5 6GNU Zebra is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GNU Zebra is distributed in the hope that it will be useful, but 12WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU Zebra; see the file COPYING. If not, write to the Free 18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21#include <zebra.h> 22 23#include "prefix.h" 24#include "memory.h" 25#include "sockunion.h" 26#include "vty.h" 27 28#include "bgpd/bgpd.h" 29#include "bgpd/bgp_table.h" 30 31void bgp_node_delete (struct bgp_node *); 32void bgp_table_free (struct bgp_table *); 33 34struct bgp_table * 35bgp_table_init (void) 36{ 37 struct bgp_table *rt; 38 39 rt = XMALLOC (MTYPE_BGP_TABLE, sizeof (struct bgp_table)); 40 memset (rt, 0, sizeof (struct bgp_table)); 41 return rt; 42} 43 44void 45bgp_table_finish (struct bgp_table *rt) 46{ 47 bgp_table_free (rt); 48} 49 50struct bgp_node * 51bgp_node_create () 52{ 53 struct bgp_node *rn; 54 55 rn = (struct bgp_node *) XMALLOC (MTYPE_BGP_NODE, sizeof (struct bgp_node)); 56 memset (rn, 0, sizeof (struct bgp_node)); 57 return rn; 58} 59 60/* Allocate new route node with prefix set. */ 61struct bgp_node * 62bgp_node_set (struct bgp_table *table, struct prefix *prefix) 63{ 64 struct bgp_node *node; 65 66 node = bgp_node_create (); 67 68 prefix_copy (&node->p, prefix); 69 node->table = table; 70 71 return node; 72} 73 74/* Free route node. */ 75void 76bgp_node_free (struct bgp_node *node) 77{ 78 XFREE (MTYPE_BGP_NODE, node); 79} 80 81/* Free route table. */ 82void 83bgp_table_free (struct bgp_table *rt) 84{ 85 struct bgp_node *tmp_node; 86 struct bgp_node *node; 87 88 if (rt == NULL) 89 return; 90 91 node = rt->top; 92 93 while (node) 94 { 95 if (node->l_left) 96 { 97 node = node->l_left; 98 continue; 99 } 100 101 if (node->l_right) 102 { 103 node = node->l_right; 104 continue; 105 } 106 107 tmp_node = node; 108 node = node->parent; 109 110 if (node != NULL) 111 { 112 if (node->l_left == tmp_node) 113 node->l_left = NULL; 114 else 115 node->l_right = NULL; 116 117 bgp_node_free (tmp_node); 118 } 119 else 120 { 121 bgp_node_free (tmp_node); 122 break; 123 } 124 } 125 126 XFREE (MTYPE_BGP_TABLE, rt); 127 return; 128} 129 130/* Utility mask array. */ 131static u_char maskbit[] = 132{ 133 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff 134}; 135 136/* Common prefix route genaration. */ 137static void 138route_common (struct prefix *n, struct prefix *p, struct prefix *new) 139{ 140 int i; 141 u_char diff; 142 u_char mask; 143 144 u_char *np = (u_char *)&n->u.prefix; 145 u_char *pp = (u_char *)&p->u.prefix; 146 u_char *newp = (u_char *)&new->u.prefix; 147 148 for (i = 0; i < p->prefixlen / 8; i++) 149 { 150 if (np[i] == pp[i]) 151 newp[i] = np[i]; 152 else 153 break; 154 } 155 156 new->prefixlen = i * 8; 157 158 if (new->prefixlen != p->prefixlen) 159 { 160 diff = np[i] ^ pp[i]; 161 mask = 0x80; 162 while (new->prefixlen < p->prefixlen && !(mask & diff)) 163 { 164 mask >>= 1; 165 new->prefixlen++; 166 } 167 newp[i] = np[i] & maskbit[new->prefixlen % 8]; 168 } 169} 170 171/* Macro version of check_bit (). */ 172#define CHECK_BIT(X,P) ((((u_char *)(X))[(P) / 8]) >> (7 - ((P) % 8)) & 1) 173 174/* Check bit of the prefix. */ 175static int 176check_bit (u_char *prefix, u_char prefixlen) 177{ 178 int offset; 179 int shift; 180 u_char *p = (u_char *)prefix; 181 182 assert (prefixlen <= 128); 183 184 offset = prefixlen / 8; 185 shift = 7 - (prefixlen % 8); 186 187 return (p[offset] >> shift & 1); 188} 189 190/* Macro version of set_link (). */ 191#define SET_LINK(X,Y) (X)->link[CHECK_BIT(&(Y)->prefix,(X)->prefixlen)] = (Y);\ 192 (Y)->parent = (X) 193 194static void 195set_link (struct bgp_node *node, struct bgp_node *new) 196{ 197 int bit; 198 199 bit = check_bit (&new->p.u.prefix, node->p.prefixlen); 200 201 assert (bit == 0 || bit == 1); 202 203 node->link[bit] = new; 204 new->parent = node; 205} 206 207/* Lock node. */ 208struct bgp_node * 209bgp_lock_node (struct bgp_node *node) 210{ 211 node->lock++; 212 return node; 213} 214 215/* Unlock node. */ 216void 217bgp_unlock_node (struct bgp_node *node) 218{ 219 node->lock--; 220 221 if (node->lock == 0) 222 bgp_node_delete (node); 223} 224 225/* Find matched prefix. */ 226struct bgp_node * 227bgp_node_match (struct bgp_table *table, struct prefix *p) 228{ 229 struct bgp_node *node; 230 struct bgp_node *matched; 231 232 matched = NULL; 233 node = table->top; 234 235 /* Walk down tree. If there is matched route then store it to 236 matched. */ 237 while (node && node->p.prefixlen <= p->prefixlen && 238 prefix_match (&node->p, p)) 239 { 240 if (node->info) 241 matched = node; 242 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; 243 } 244 245 /* If matched route found, return it. */ 246 if (matched) 247 return bgp_lock_node (matched); 248 249 return NULL; 250} 251 252struct bgp_node * 253bgp_node_match_ipv4 (struct bgp_table *table, struct in_addr *addr) 254{ 255 struct prefix_ipv4 p; 256 257 memset (&p, 0, sizeof (struct prefix_ipv4)); 258 p.family = AF_INET; 259 p.prefixlen = IPV4_MAX_PREFIXLEN; 260 p.prefix = *addr; 261 262 return bgp_node_match (table, (struct prefix *) &p); 263} 264 265#ifdef HAVE_IPV6 266struct bgp_node * 267bgp_node_match_ipv6 (struct bgp_table *table, struct in6_addr *addr) 268{ 269 struct prefix_ipv6 p; 270 271 memset (&p, 0, sizeof (struct prefix_ipv6)); 272 p.family = AF_INET6; 273 p.prefixlen = IPV6_MAX_PREFIXLEN; 274 p.prefix = *addr; 275 276 return bgp_node_match (table, (struct prefix *) &p); 277} 278#endif /* HAVE_IPV6 */ 279 280/* Lookup same prefix node. Return NULL when we can't find route. */ 281struct bgp_node * 282bgp_node_lookup (struct bgp_table *table, struct prefix *p) 283{ 284 struct bgp_node *node; 285 286 node = table->top; 287 288 while (node && node->p.prefixlen <= p->prefixlen && 289 prefix_match (&node->p, p)) 290 { 291 if (node->p.prefixlen == p->prefixlen && node->info) 292 return bgp_lock_node (node); 293 294 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; 295 } 296 297 return NULL; 298} 299 300/* Add node to routing table. */ 301struct bgp_node * 302bgp_node_get (struct bgp_table *table, struct prefix *p) 303{ 304 struct bgp_node *new; 305 struct bgp_node *node; 306 struct bgp_node *match; 307 308 match = NULL; 309 node = table->top; 310 while (node && node->p.prefixlen <= p->prefixlen && 311 prefix_match (&node->p, p)) 312 { 313 if (node->p.prefixlen == p->prefixlen) 314 { 315 bgp_lock_node (node); 316 return node; 317 } 318 match = node; 319 node = node->link[check_bit(&p->u.prefix, node->p.prefixlen)]; 320 } 321 322 if (node == NULL) 323 { 324 new = bgp_node_set (table, p); 325 if (match) 326 set_link (match, new); 327 else 328 table->top = new; 329 } 330 else 331 { 332 new = bgp_node_create (); 333 route_common (&node->p, p, &new->p); 334 new->p.family = p->family; 335 new->table = table; 336 set_link (new, node); 337 338 if (match) 339 set_link (match, new); 340 else 341 table->top = new; 342 343 if (new->p.prefixlen != p->prefixlen) 344 { 345 match = new; 346 new = bgp_node_set (table, p); 347 set_link (match, new); 348 } 349 } 350 bgp_lock_node (new); 351 352 return new; 353} 354 355/* Delete node from the routing table. */ 356void 357bgp_node_delete (struct bgp_node *node) 358{ 359 struct bgp_node *child; 360 struct bgp_node *parent; 361 362 assert (node->lock == 0); 363 assert (node->info == NULL); 364 365 if (node->l_left && node->l_right) 366 return; 367 368 if (node->l_left) 369 child = node->l_left; 370 else 371 child = node->l_right; 372 373 parent = node->parent; 374 375 if (child) 376 child->parent = parent; 377 378 if (parent) 379 { 380 if (parent->l_left == node) 381 parent->l_left = child; 382 else 383 parent->l_right = child; 384 } 385 else 386 node->table->top = child; 387 388 bgp_node_free (node); 389 390 /* If parent node is stub then delete it also. */ 391 if (parent && parent->lock == 0) 392 bgp_node_delete (parent); 393} 394 395/* Get fist node and lock it. This function is useful when one want 396 to lookup all the node exist in the routing table. */ 397struct bgp_node * 398bgp_table_top (struct bgp_table *table) 399{ 400 /* If there is no node in the routing table return NULL. */ 401 if (table->top == NULL) 402 return NULL; 403 404 /* Lock the top node and return it. */ 405 bgp_lock_node (table->top); 406 return table->top; 407} 408 409/* Unlock current node and lock next node then return it. */ 410struct bgp_node * 411bgp_route_next (struct bgp_node *node) 412{ 413 struct bgp_node *next; 414 struct bgp_node *start; 415 416 /* Node may be deleted from bgp_unlock_node so we have to preserve 417 next node's pointer. */ 418 419 if (node->l_left) 420 { 421 next = node->l_left; 422 bgp_lock_node (next); 423 bgp_unlock_node (node); 424 return next; 425 } 426 if (node->l_right) 427 { 428 next = node->l_right; 429 bgp_lock_node (next); 430 bgp_unlock_node (node); 431 return next; 432 } 433 434 start = node; 435 while (node->parent) 436 { 437 if (node->parent->l_left == node && node->parent->l_right) 438 { 439 next = node->parent->l_right; 440 bgp_lock_node (next); 441 bgp_unlock_node (start); 442 return next; 443 } 444 node = node->parent; 445 } 446 bgp_unlock_node (start); 447 return NULL; 448} 449 450/* Unlock current node and lock next node until limit. */ 451struct bgp_node * 452bgp_route_next_until (struct bgp_node *node, struct bgp_node *limit) 453{ 454 struct bgp_node *next; 455 struct bgp_node *start; 456 457 /* Node may be deleted from bgp_unlock_node so we have to preserve 458 next node's pointer. */ 459 460 if (node->l_left) 461 { 462 next = node->l_left; 463 bgp_lock_node (next); 464 bgp_unlock_node (node); 465 return next; 466 } 467 if (node->l_right) 468 { 469 next = node->l_right; 470 bgp_lock_node (next); 471 bgp_unlock_node (node); 472 return next; 473 } 474 475 start = node; 476 while (node->parent && node != limit) 477 { 478 if (node->parent->l_left == node && node->parent->l_right) 479 { 480 next = node->parent->l_right; 481 bgp_lock_node (next); 482 bgp_unlock_node (start); 483 return next; 484 } 485 node = node->parent; 486 } 487 bgp_unlock_node (start); 488 return NULL; 489} 490