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