ospf6d/ospf6_route.c

   1 /*
   2  * Copyright (C) 2003 Yasuhiro Ohara
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22
  23 #include "log.h"
  24 #include "memory.h"
  25 #include "prefix.h"
  26 #include "table.h"
  27 #include "vty.h"
  28 #include "command.h"
  29 #include "linklist.h"
  30
  31 #include "ospf6_proto.h"
  32 #include "ospf6_lsa.h"
  33 #include "ospf6_lsdb.h"
  34 #include "ospf6_route.h"
  35 #include "ospf6_top.h"
  36 #include "ospf6_area.h"
  37 #include "ospf6_interface.h"
  38 #include "ospf6d.h"
  39 #include "ospf6_zebra.h"
  40
  41 DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_ROUTE,   "OSPF6 route");
  42 DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_ROUTE_TABLE, "OSPF6 route table");
  43 DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_NEXTHOP, "OSPF6 nexthop");
  44 DEFINE_MTYPE_STATIC(OSPF6D, OSPF6_PATH,    "OSPF6 Path");
  45
  46 unsigned char conf_debug_ospf6_route = 0;
  47
  48 static char *ospf6_route_table_name(struct ospf6_route_table *table)
  49 {
  50         static char name[64];
  51         switch (table->scope_type) {
  52         case OSPF6_SCOPE_TYPE_GLOBAL: {
  53                 switch (table->table_type) {
  54                 case OSPF6_TABLE_TYPE_ROUTES:
  55                         snprintf(name, sizeof(name), "global route table");
  56                         break;
  57                 case OSPF6_TABLE_TYPE_BORDER_ROUTERS:
  58                         snprintf(name, sizeof(name), "global brouter table");
  59                         break;
  60                 case OSPF6_TABLE_TYPE_EXTERNAL_ROUTES:
  61                         snprintf(name, sizeof(name), "global external table");
  62                         break;
  63                 default:
  64                         snprintf(name, sizeof(name), "global unknown table");
  65                         break;
  66                 }
  67         } break;
  68
  69         case OSPF6_SCOPE_TYPE_AREA: {
  70                 struct ospf6_area *oa = (struct ospf6_area *)table->scope;
  71                 switch (table->table_type) {
  72                 case OSPF6_TABLE_TYPE_SPF_RESULTS:
  73                         snprintf(name, sizeof(name), "area %s spf table",
  74                                  oa->name);
  75                         break;
  76                 case OSPF6_TABLE_TYPE_ROUTES:
  77                         snprintf(name, sizeof(name), "area %s route table",
  78                                  oa->name);
  79                         break;
  80                 case OSPF6_TABLE_TYPE_PREFIX_RANGES:
  81                         snprintf(name, sizeof(name), "area %s range table",
  82                                  oa->name);
  83                         break;
  84                 case OSPF6_TABLE_TYPE_SUMMARY_PREFIXES:
  85                         snprintf(name, sizeof(name),
  86                                  "area %s summary prefix table", oa->name);
  87                         break;
  88                 case OSPF6_TABLE_TYPE_SUMMARY_ROUTERS:
  89                         snprintf(name, sizeof(name),
  90                                  "area %s summary router table", oa->name);
  91                         break;
  92                 default:
  93                         snprintf(name, sizeof(name), "area %s unknown table",
  94                                  oa->name);
  95                         break;
  96                 }
  97         } break;
  98
  99         case OSPF6_SCOPE_TYPE_INTERFACE: {
 100                 struct ospf6_interface *oi =
 101                         (struct ospf6_interface *)table->scope;
 102                 switch (table->table_type) {
 103                 case OSPF6_TABLE_TYPE_CONNECTED_ROUTES:
 104                         snprintf(name, sizeof(name),
 105                                  "interface %s connected table",
 106                                  oi->interface->name);
 107                         break;
 108                 default:
 109                         snprintf(name, sizeof(name),
 110                                  "interface %s unknown table",
 111                                  oi->interface->name);
 112                         break;
 113                 }
 114         } break;
 115
 116         default: {
 117                 switch (table->table_type) {
 118                 case OSPF6_TABLE_TYPE_SPF_RESULTS:
 119                         snprintf(name, sizeof(name), "temporary spf table");
 120                         break;
 121                 default:
 122                         snprintf(name, sizeof(name), "temporary unknown table");
 123                         break;
 124                 }
 125         } break;
 126         }
 127         return name;
 128 }
 129
 130 void ospf6_linkstate_prefix(uint32_t adv_router, uint32_t id,
 131                             struct prefix *prefix)
 132 {
 133         memset(prefix, 0, sizeof(struct prefix));
 134         prefix->family = AF_INET6;
 135         prefix->prefixlen = 64;
 136         memcpy(&prefix->u.prefix6.s6_addr[0], &adv_router, 4);
 137         memcpy(&prefix->u.prefix6.s6_addr[4], &id, 4);
 138 }
 139
 140 void ospf6_linkstate_prefix2str(struct prefix *prefix, char *buf, int size)
 141 {
 142         uint32_t adv_router, id;
 143         char adv_router_str[16], id_str[16];
 144         memcpy(&adv_router, &prefix->u.prefix6.s6_addr[0], 4);
 145         memcpy(&id, &prefix->u.prefix6.s6_addr[4], 4);
 146         inet_ntop(AF_INET, &adv_router, adv_router_str, sizeof(adv_router_str));
 147         inet_ntop(AF_INET, &id, id_str, sizeof(id_str));
 148         if (ntohl(id))
 149                 snprintf(buf, size, "%s Net-ID: %s", adv_router_str, id_str);
 150         else
 151                 snprintf(buf, size, "%s", adv_router_str);
 152 }
 153
 154 /* Global strings for logging */
 155 const char *const ospf6_dest_type_str[OSPF6_DEST_TYPE_MAX] = {
 156         "Unknown", "Router", "Network", "Discard", "Linkstate", "AddressRange",
 157 };
 158
 159 const char *const ospf6_dest_type_substr[OSPF6_DEST_TYPE_MAX] = {
 160         "?", "R", "N", "D", "L", "A",
 161 };
 162
 163 const char *const ospf6_path_type_str[OSPF6_PATH_TYPE_MAX] = {
 164         "Unknown", "Intra-Area", "Inter-Area", "External-1", "External-2",
 165 };
 166
 167 const char *const ospf6_path_type_substr[OSPF6_PATH_TYPE_MAX] = {
 168         "??", "IA", "IE", "E1", "E2",
 169 };
 170
 171 const char *ospf6_path_type_json[OSPF6_PATH_TYPE_MAX] = {
 172         "UnknownRoute", "IntraArea", "InterArea", "External1", "External2",
 173 };
 174
 175
 176 struct ospf6_nexthop *ospf6_nexthop_create(void)
 177 {
 178         struct ospf6_nexthop *nh;
 179
 180         nh = XCALLOC(MTYPE_OSPF6_NEXTHOP, sizeof(struct ospf6_nexthop));
 181         return nh;
 182 }
 183
 184 void ospf6_nexthop_delete(struct ospf6_nexthop *nh)
 185 {
 186         XFREE(MTYPE_OSPF6_NEXTHOP, nh);
 187 }
 188
 189 void ospf6_clear_nexthops(struct list *nh_list)
 190 {
 191         struct listnode *node;
 192         struct ospf6_nexthop *nh;
 193
 194         if (nh_list) {
 195                 for (ALL_LIST_ELEMENTS_RO(nh_list, node, nh))
 196                         ospf6_nexthop_clear(nh);
 197         }
 198 }
 199
 200 static struct ospf6_nexthop *
 201 ospf6_route_find_nexthop(struct list *nh_list, struct ospf6_nexthop *nh_match)
 202 {
 203         struct listnode *node;
 204         struct ospf6_nexthop *nh;
 205
 206         if (nh_list && nh_match) {
 207                 for (ALL_LIST_ELEMENTS_RO(nh_list, node, nh)) {
 208                         if (ospf6_nexthop_is_same(nh, nh_match))
 209                                 return (nh);
 210                 }
 211         }
 212
 213         return (NULL);
 214 }
 215
 216 void ospf6_copy_nexthops(struct list *dst, struct list *src)
 217 {
 218         struct ospf6_nexthop *nh_new, *nh;
 219         struct listnode *node;
 220
 221         if (dst && src) {
 222                 for (ALL_LIST_ELEMENTS_RO(src, node, nh)) {
 223                         if (ospf6_nexthop_is_set(nh)) {
 224                                 nh_new = ospf6_nexthop_create();
 225                                 ospf6_nexthop_copy(nh_new, nh);
 226                                 listnode_add_sort(dst, nh_new);
 227                         }
 228                 }
 229         }
 230 }
 231
 232 void ospf6_merge_nexthops(struct list *dst, struct list *src)
 233 {
 234         struct listnode *node;
 235         struct ospf6_nexthop *nh, *nh_new;
 236
 237         if (src && dst) {
 238                 for (ALL_LIST_ELEMENTS_RO(src, node, nh)) {
 239                         if (!ospf6_route_find_nexthop(dst, nh)) {
 240                                 nh_new = ospf6_nexthop_create();
 241                                 ospf6_nexthop_copy(nh_new, nh);
 242                                 listnode_add_sort(dst, nh_new);
 243                         }
 244                 }
 245         }
 246 }
 247
 248 int ospf6_route_cmp_nexthops(struct ospf6_route *a, struct ospf6_route *b)
 249 {
 250         struct listnode *anode, *bnode;
 251         struct ospf6_nexthop *anh, *bnh;
 252         bool identical = false;
 253
 254         if (a && b) {
 255                 if (listcount(a->nh_list) == listcount(b->nh_list)) {
 256                         for (ALL_LIST_ELEMENTS_RO(a->nh_list, anode, anh)) {
 257                                 identical = false;
 258                                 for (ALL_LIST_ELEMENTS_RO(b->nh_list, bnode,
 259                                                           bnh)) {
 260                                         if (ospf6_nexthop_is_same(anh, bnh))
 261                                                 identical = true;
 262                                 }
 263                                 /* Currnet List A element not found List B
 264                                  * Non-Identical lists return */
 265                                 if (identical == false)
 266                                         return 1;
 267                         }
 268                         return 0;
 269                 } else
 270                         return 1;
 271         }
 272         /* One of the routes doesn't exist ? */
 273         return (1);
 274 }
 275
 276 int ospf6_num_nexthops(struct list *nh_list)
 277 {
 278         return (listcount(nh_list));
 279 }
 280
 281 void ospf6_add_nexthop(struct list *nh_list, int ifindex, struct in6_addr *addr)
 282 {
 283         struct ospf6_nexthop *nh;
 284         struct ospf6_nexthop nh_match;
 285
 286         if (nh_list) {
 287                 nh_match.ifindex = ifindex;
 288                 if (addr != NULL)
 289                         memcpy(&nh_match.address, addr,
 290                                sizeof(struct in6_addr));
 291                 else
 292                         memset(&nh_match.address, 0, sizeof(struct in6_addr));
 293
 294                 if (!ospf6_route_find_nexthop(nh_list, &nh_match)) {
 295                         nh = ospf6_nexthop_create();
 296                         ospf6_nexthop_copy(nh, &nh_match);
 297                         listnode_add(nh_list, nh);
 298                 }
 299         }
 300 }
 301
 302 void ospf6_route_zebra_copy_nexthops(struct ospf6_route *route,
 303                                      struct zapi_nexthop nexthops[],
 304                                      int entries, vrf_id_t vrf_id)
 305 {
 306         struct ospf6_nexthop *nh;
 307         struct listnode *node;
 308         char buf[64];
 309         int i;
 310
 311         if (route) {
 312                 i = 0;
 313                 for (ALL_LIST_ELEMENTS_RO(route->nh_list, node, nh)) {
 314                         if (IS_OSPF6_DEBUG_ZEBRA(SEND)) {
 315                                 const char *ifname;
 316                                 inet_ntop(AF_INET6, &nh->address, buf,
 317                                           sizeof(buf));
 318                                 ifname = ifindex2ifname(nh->ifindex, vrf_id);
 319                                 zlog_debug("  nexthop: %s%%%.*s(%d)", buf,
 320                                            IFNAMSIZ, ifname, nh->ifindex);
 321                         }
 322                         if (i >= entries)
 323                                 return;
 324
 325                         nexthops[i].vrf_id = vrf_id;
 326                         nexthops[i].ifindex = nh->ifindex;
 327                         if (!IN6_IS_ADDR_UNSPECIFIED(&nh->address)) {
 328                                 nexthops[i].gate.ipv6 = nh->address;
 329                                 nexthops[i].type = NEXTHOP_TYPE_IPV6_IFINDEX;
 330                         } else
 331                                 nexthops[i].type = NEXTHOP_TYPE_IFINDEX;
 332                         i++;
 333                 }
 334         }
 335 }
 336
 337 int ospf6_route_get_first_nh_index(struct ospf6_route *route)
 338 {
 339         struct ospf6_nexthop *nh;
 340
 341         if (route) {
 342                 nh = listnode_head(route->nh_list);
 343                 if (nh)
 344                         return nh->ifindex;
 345         }
 346
 347         return -1;
 348 }
 349
 350 int ospf6_nexthop_cmp(struct ospf6_nexthop *a, struct ospf6_nexthop *b)
 351 {
 352         if (a->ifindex < b->ifindex)
 353                 return -1;
 354         else if (a->ifindex > b->ifindex)
 355                 return 1;
 356         else
 357                 return memcmp(&a->address, &b->address,
 358                               sizeof(struct in6_addr));
 359
 360         return 0;
 361 }
 362
 363 static int ospf6_path_cmp(struct ospf6_path *a, struct ospf6_path *b)
 364 {
 365         if (a->origin.adv_router < b->origin.adv_router)
 366                 return -1;
 367         else if (a->origin.adv_router > b->origin.adv_router)
 368                 return 1;
 369         else
 370                 return 0;
 371 }
 372
 373 void ospf6_path_free(struct ospf6_path *op)
 374 {
 375         if (op->nh_list)
 376                 list_delete(&op->nh_list);
 377         XFREE(MTYPE_OSPF6_PATH, op);
 378 }
 379
 380 struct ospf6_path *ospf6_path_dup(struct ospf6_path *path)
 381 {
 382         struct ospf6_path *new;
 383
 384         new = XCALLOC(MTYPE_OSPF6_PATH, sizeof(struct ospf6_path));
 385         memcpy(new, path, sizeof(struct ospf6_path));
 386         new->nh_list = list_new();
 387         new->nh_list->cmp = (int (*)(void *, void *))ospf6_nexthop_cmp;
 388         new->nh_list->del = (void (*)(void *))ospf6_nexthop_delete;
 389
 390         return new;
 391 }
 392
 393 void ospf6_copy_paths(struct list *dst, struct list *src)
 394 {
 395         struct ospf6_path *path_new, *path;
 396         struct listnode *node;
 397
 398         if (dst && src) {
 399                 for (ALL_LIST_ELEMENTS_RO(src, node, path)) {
 400                         path_new = ospf6_path_dup(path);
 401                         ospf6_copy_nexthops(path_new->nh_list, path->nh_list);
 402                         listnode_add_sort(dst, path_new);
 403                 }
 404         }
 405 }
 406
 407 struct ospf6_route *ospf6_route_create(void)
 408 {
 409         struct ospf6_route *route;
 410
 411         route = XCALLOC(MTYPE_OSPF6_ROUTE, sizeof(struct ospf6_route));
 412         route->nh_list = list_new();
 413         route->nh_list->cmp = (int (*)(void *, void *))ospf6_nexthop_cmp;
 414         route->nh_list->del = (void (*)(void *))ospf6_nexthop_delete;
 415         route->paths = list_new();
 416         route->paths->cmp = (int (*)(void *, void *))ospf6_path_cmp;
 417         route->paths->del = (void (*)(void *))ospf6_path_free;
 418         return route;
 419 }
 420
 421 void ospf6_route_delete(struct ospf6_route *route)
 422 {
 423         if (route) {
 424                 if (route->nh_list)
 425                         list_delete(&route->nh_list);
 426                 if (route->paths)
 427                         list_delete(&route->paths);
 428                 XFREE(MTYPE_OSPF6_ROUTE, route);
 429         }
 430 }
 431
 432 struct ospf6_route *ospf6_route_copy(struct ospf6_route *route)
 433 {
 434         struct ospf6_route *new;
 435
 436         new = ospf6_route_create();
 437         new->type = route->type;
 438         memcpy(&new->prefix, &route->prefix, sizeof(struct prefix));
 439         new->installed = route->installed;
 440         new->changed = route->changed;
 441         new->flag = route->flag;
 442         new->route_option = route->route_option;
 443         new->linkstate_id = route->linkstate_id;
 444         new->path = route->path;
 445         ospf6_copy_nexthops(new->nh_list, route->nh_list);
 446         ospf6_copy_paths(new->paths, route->paths);
 447         new->rnode = NULL;
 448         new->prev = NULL;
 449         new->next = NULL;
 450         new->table = NULL;
 451         new->lock = 0;
 452         return new;
 453 }
 454
 455 void ospf6_route_lock(struct ospf6_route *route)
 456 {
 457         route->lock++;
 458 }
 459
 460 void ospf6_route_unlock(struct ospf6_route *route)
 461 {
 462         assert(route->lock > 0);
 463         route->lock--;
 464         if (route->lock == 0) {
 465                 /* Can't detach from the table until here
 466                    because ospf6_route_next () will use
 467                    the 'route->table' pointer for logging */
 468                 route->table = NULL;
 469                 ospf6_route_delete(route);
 470         }
 471 }
 472
 473 /* Route compare function. If ra is more preferred, it returns
 474    less than 0. If rb is more preferred returns greater than 0.
 475    Otherwise (neither one is preferred), returns 0 */
 476 int ospf6_route_cmp(struct ospf6_route *ra, struct ospf6_route *rb)
 477 {
 478         assert(ospf6_route_is_same(ra, rb));
 479         assert(OSPF6_PATH_TYPE_NONE < ra->path.type
 480                && ra->path.type < OSPF6_PATH_TYPE_MAX);
 481         assert(OSPF6_PATH_TYPE_NONE < rb->path.type
 482                && rb->path.type < OSPF6_PATH_TYPE_MAX);
 483
 484         if (ra->type != rb->type)
 485                 return (ra->type - rb->type);
 486
 487         if (ra->path.type != rb->path.type)
 488                 return (ra->path.type - rb->path.type);
 489
 490         if (ra->path.type == OSPF6_PATH_TYPE_EXTERNAL2) {
 491                 if (ra->path.u.cost_e2 != rb->path.u.cost_e2)
 492                         return (ra->path.u.cost_e2 - rb->path.u.cost_e2);
 493                 else
 494                         return (ra->path.cost - rb->path.cost);
 495         } else {
 496                 if (ra->path.cost != rb->path.cost)
 497                         return (ra->path.cost - rb->path.cost);
 498         }
 499
 500         if (ra->path.area_id != rb->path.area_id)
 501                 return (ntohl(ra->path.area_id) - ntohl(rb->path.area_id));
 502
 503         return 0;
 504 }
 505
 506 struct ospf6_route *ospf6_route_lookup(struct prefix *prefix,
 507                                        struct ospf6_route_table *table)
 508 {
 509         struct route_node *node;
 510         struct ospf6_route *route;
 511
 512         node = route_node_lookup(table->table, prefix);
 513         if (node == NULL)
 514                 return NULL;
 515
 516         route = (struct ospf6_route *)node->info;
 517         route_unlock_node(node); /* to free the lookup lock */
 518         return route;
 519 }
 520
 521 struct ospf6_route *
 522 ospf6_route_lookup_identical(struct ospf6_route *route,
 523                              struct ospf6_route_table *table)
 524 {
 525         struct ospf6_route *target;
 526
 527         for (target = ospf6_route_lookup(&route->prefix, table); target;
 528              target = target->next) {
 529                 if (target->type == route->type
 530                     && (memcmp(&target->prefix, &route->prefix,
 531                                sizeof(struct prefix))
 532                         == 0)
 533                     && target->path.type == route->path.type
 534                     && target->path.cost == route->path.cost
 535                     && target->path.u.cost_e2 == route->path.u.cost_e2
 536                     && ospf6_route_cmp_nexthops(target, route) == 0)
 537                         return target;
 538         }
 539         return NULL;
 540 }
 541
 542 struct ospf6_route *
 543 ospf6_route_lookup_bestmatch(struct prefix *prefix,
 544                              struct ospf6_route_table *table)
 545 {
 546         struct route_node *node;
 547         struct ospf6_route *route;
 548
 549         node = route_node_match(table->table, prefix);
 550         if (node == NULL)
 551                 return NULL;
 552         route_unlock_node(node);
 553
 554         route = (struct ospf6_route *)node->info;
 555         return route;
 556 }
 557
 558 #ifdef DEBUG
 559 static void route_table_assert(struct ospf6_route_table *table)
 560 {
 561         struct ospf6_route *prev, *r, *next;
 562         unsigned int link_error = 0, num = 0;
 563
 564         r = ospf6_route_head(table);
 565         prev = NULL;
 566         while (r) {
 567                 if (r->prev != prev)
 568                         link_error++;
 569
 570                 next = ospf6_route_next(r);
 571
 572                 if (r->next != next)
 573                         link_error++;
 574
 575                 prev = r;
 576                 r = next;
 577         }
 578
 579         for (r = ospf6_route_head(table); r; r = ospf6_route_next(r))
 580                 num++;
 581
 582         if (link_error == 0 && num == table->count)
 583                 return;
 584
 585         flog_err(EC_LIB_DEVELOPMENT, "PANIC !!");
 586         flog_err(EC_LIB_DEVELOPMENT,
 587                  "Something has gone wrong with ospf6_route_table[%p]", table);
 588         zlog_debug("table count = %d, real number = %d", table->count, num);
 589         zlog_debug("DUMP START");
 590         for (r = ospf6_route_head(table); r; r = ospf6_route_next(r))
 591                 zlog_info("%p<-[%p]->%p : %pFX", r->prev, r, r->next,
 592                           &r->prefix);
 593         zlog_debug("DUMP END");
 594
 595         assert(link_error == 0 && num == table->count);
 596 }
 597 #define ospf6_route_table_assert(t) (route_table_assert (t))
 598 #else
 599 #define ospf6_route_table_assert(t) ((void) 0)
 600 #endif /*DEBUG*/
 601
 602 struct ospf6_route *ospf6_route_add(struct ospf6_route *route,
 603                                     struct ospf6_route_table *table)
 604 {
 605         struct route_node *node, *nextnode, *prevnode;
 606         struct ospf6_route *current = NULL;
 607         struct ospf6_route *prev = NULL, *old = NULL, *next = NULL;
 608         char buf[PREFIX2STR_BUFFER];
 609         struct timeval now;
 610
 611         assert(route->rnode == NULL);
 612         assert(route->lock == 0);
 613         assert(route->next == NULL);
 614         assert(route->prev == NULL);
 615
 616         if (route->type == OSPF6_DEST_TYPE_LINKSTATE)
 617                 ospf6_linkstate_prefix2str(&route->prefix, buf, sizeof(buf));
 618         else
 619                 prefix2str(&route->prefix, buf, sizeof(buf));
 620
 621         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 622                 zlog_debug("%s %p: route add %p: %s paths %u nh %u",
 623                            ospf6_route_table_name(table), (void *)table,
 624                            (void *)route, buf, listcount(route->paths),
 625                            listcount(route->nh_list));
 626         else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 627                 zlog_debug("%s: route add: %s", ospf6_route_table_name(table),
 628                            buf);
 629
 630         monotime(&now);
 631
 632         node = route_node_get(table->table, &route->prefix);
 633         route->rnode = node;
 634
 635         /* find place to insert */
 636         for (current = node->info; current; current = current->next) {
 637                 if (!ospf6_route_is_same(current, route))
 638                         next = current;
 639                 else if (current->type != route->type)
 640                         prev = current;
 641                 else if (ospf6_route_is_same_origin(current, route))
 642                         old = current;
 643                 else if (ospf6_route_cmp(current, route) > 0)
 644                         next = current;
 645                 else
 646                         prev = current;
 647
 648                 if (old || next)
 649                         break;
 650         }
 651
 652         if (old) {
 653                 /* if route does not actually change, return unchanged */
 654                 if (ospf6_route_is_identical(old, route)) {
 655                         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 656                                 zlog_debug(
 657                                         "%s %p: route add %p: needless update of %p old cost %u",
 658                                         ospf6_route_table_name(table),
 659                                         (void *)table, (void *)route,
 660                                         (void *)old, old->path.cost);
 661                         else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 662                                 zlog_debug("%s: route add: needless update",
 663                                            ospf6_route_table_name(table));
 664
 665                         ospf6_route_delete(route);
 666                         SET_FLAG(old->flag, OSPF6_ROUTE_ADD);
 667                         ospf6_route_table_assert(table);
 668
 669                         /* to free the lookup lock */
 670                         route_unlock_node(node);
 671                         return old;
 672                 }
 673
 674                 if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 675                         zlog_debug(
 676                                 "%s %p: route add %p cost %u paths %u nh %u: update of %p cost %u paths %u nh %u",
 677                                 ospf6_route_table_name(table), (void *)table,
 678                                 (void *)route, route->path.cost,
 679                                 listcount(route->paths),
 680                                 listcount(route->nh_list), (void *)old,
 681                                 old->path.cost, listcount(old->paths),
 682                                 listcount(old->nh_list));
 683                 else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 684                         zlog_debug("%s: route add: update",
 685                                    ospf6_route_table_name(table));
 686
 687                 /* replace old one if exists */
 688                 if (node->info == old) {
 689                         node->info = route;
 690                         SET_FLAG(route->flag, OSPF6_ROUTE_BEST);
 691                         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 692                                 zlog_debug("%s:  replace old route %s",
 693                                            __func__, buf);
 694                 }
 695
 696                 if (old->prev)
 697                         old->prev->next = route;
 698                 route->prev = old->prev;
 699                 if (old->next)
 700                         old->next->prev = route;
 701                 route->next = old->next;
 702
 703                 route->installed = old->installed;
 704                 route->changed = now;
 705                 assert(route->table == NULL);
 706                 route->table = table;
 707
 708                 ospf6_route_unlock(old); /* will be deleted later */
 709                 ospf6_route_lock(route);
 710
 711                 SET_FLAG(route->flag, OSPF6_ROUTE_CHANGE);
 712                 ospf6_route_table_assert(table);
 713
 714                 if (table->hook_add)
 715                         (*table->hook_add)(route);
 716
 717                 return route;
 718         }
 719
 720         /* insert if previous or next node found */
 721         if (prev || next) {
 722                 if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 723                         zlog_debug(
 724                                 "%s %p: route add %p cost %u: another path: prev %p, next %p node ref %u",
 725                                 ospf6_route_table_name(table), (void *)table,
 726                                 (void *)route, route->path.cost, (void *)prev,
 727                                 (void *)next, route_node_get_lock_count(node));
 728                 else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 729                         zlog_debug("%s: route add cost %u: another path found",
 730                                    ospf6_route_table_name(table),
 731                                    route->path.cost);
 732
 733                 if (prev == NULL)
 734                         prev = next->prev;
 735                 if (next == NULL)
 736                         next = prev->next;
 737
 738                 if (prev)
 739                         prev->next = route;
 740                 route->prev = prev;
 741                 if (next)
 742                         next->prev = route;
 743                 route->next = next;
 744
 745                 if (node->info == next) {
 746                         assert(next && next->rnode == node);
 747                         node->info = route;
 748                         UNSET_FLAG(next->flag, OSPF6_ROUTE_BEST);
 749                         SET_FLAG(route->flag, OSPF6_ROUTE_BEST);
 750                         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 751                                 zlog_debug(
 752                                         "%s %p: route add %p cost %u: replacing previous best: %p cost %u",
 753                                         ospf6_route_table_name(table),
 754                                         (void *)table, (void *)route,
 755                                         route->path.cost, (void *)next,
 756                                         next->path.cost);
 757                 }
 758
 759                 route->installed = now;
 760                 route->changed = now;
 761                 assert(route->table == NULL);
 762                 route->table = table;
 763
 764                 ospf6_route_lock(route);
 765                 table->count++;
 766                 ospf6_route_table_assert(table);
 767
 768                 SET_FLAG(route->flag, OSPF6_ROUTE_ADD);
 769                 if (table->hook_add)
 770                         (*table->hook_add)(route);
 771
 772                 return route;
 773         }
 774
 775         /* Else, this is the brand new route regarding to the prefix */
 776         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 777                 zlog_debug("%s %p: route add %p %s cost %u: brand new route",
 778                            ospf6_route_table_name(table), (void *)table,
 779                            (void *)route, buf, route->path.cost);
 780         else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 781                 zlog_debug("%s: route add: brand new route",
 782                            ospf6_route_table_name(table));
 783
 784         assert(node->info == NULL);
 785         node->info = route;
 786         SET_FLAG(route->flag, OSPF6_ROUTE_BEST);
 787         ospf6_route_lock(route);
 788         route->installed = now;
 789         route->changed = now;
 790         assert(route->table == NULL);
 791         route->table = table;
 792
 793         /* lookup real existing next route */
 794         nextnode = node;
 795         route_lock_node(nextnode);
 796         do {
 797                 nextnode = route_next(nextnode);
 798         } while (nextnode && nextnode->info == NULL);
 799
 800         /* set next link */
 801         if (nextnode == NULL)
 802                 route->next = NULL;
 803         else {
 804                 route_unlock_node(nextnode);
 805
 806                 next = nextnode->info;
 807                 route->next = next;
 808                 next->prev = route;
 809         }
 810
 811         /* lookup real existing prev route */
 812         prevnode = node;
 813         route_lock_node(prevnode);
 814         do {
 815                 prevnode = route_prev(prevnode);
 816         } while (prevnode && prevnode->info == NULL);
 817
 818         /* set prev link */
 819         if (prevnode == NULL)
 820                 route->prev = NULL;
 821         else {
 822                 route_unlock_node(prevnode);
 823
 824                 prev = prevnode->info;
 825                 while (prev->next && ospf6_route_is_same(prev, prev->next))
 826                         prev = prev->next;
 827                 route->prev = prev;
 828                 prev->next = route;
 829         }
 830
 831         table->count++;
 832         ospf6_route_table_assert(table);
 833
 834         SET_FLAG(route->flag, OSPF6_ROUTE_ADD);
 835         if (table->hook_add)
 836                 (*table->hook_add)(route);
 837
 838         return route;
 839 }
 840
 841 void ospf6_route_remove(struct ospf6_route *route,
 842                         struct ospf6_route_table *table)
 843 {
 844         struct route_node *node;
 845         struct ospf6_route *current;
 846         char buf[PREFIX2STR_BUFFER];
 847
 848         if (route->type == OSPF6_DEST_TYPE_LINKSTATE)
 849                 ospf6_linkstate_prefix2str(&route->prefix, buf, sizeof(buf));
 850         else
 851                 prefix2str(&route->prefix, buf, sizeof(buf));
 852
 853         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 854                 zlog_debug("%s %p: route remove %p: %s cost %u refcount %u",
 855                            ospf6_route_table_name(table), (void *)table,
 856                            (void *)route, buf, route->path.cost, route->lock);
 857         else if (IS_OSPF6_DEBUG_ROUTE(TABLE))
 858                 zlog_debug("%s: route remove: %s",
 859                            ospf6_route_table_name(table), buf);
 860
 861         node = route_node_lookup(table->table, &route->prefix);
 862         assert(node);
 863
 864         /* find the route to remove, making sure that the route pointer
 865            is from the route table. */
 866         current = node->info;
 867         while (current && current != route)
 868                 current = current->next;
 869
 870         assert(current == route);
 871
 872         /* adjust doubly linked list */
 873         if (route->prev)
 874                 route->prev->next = route->next;
 875         if (route->next)
 876                 route->next->prev = route->prev;
 877
 878         if (node->info == route) {
 879                 if (route->next && route->next->rnode == node) {
 880                         node->info = route->next;
 881                         SET_FLAG(route->next->flag, OSPF6_ROUTE_BEST);
 882                         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 883                                 zlog_debug("%s: remove route %s", __func__,
 884                                            buf);
 885                 } else {
 886                         node->info = NULL;
 887                         route->rnode = NULL;
 888                         route_unlock_node(node); /* to free the original lock */
 889                 }
 890         }
 891
 892         route_unlock_node(node); /* to free the lookup lock */
 893         table->count--;
 894         ospf6_route_table_assert(table);
 895
 896         SET_FLAG(route->flag, OSPF6_ROUTE_WAS_REMOVED);
 897
 898         /* Note hook_remove may call ospf6_route_remove */
 899         if (table->hook_remove)
 900                 (*table->hook_remove)(route);
 901
 902         ospf6_route_unlock(route);
 903 }
 904
 905 struct ospf6_route *ospf6_route_head(struct ospf6_route_table *table)
 906 {
 907         struct route_node *node;
 908         struct ospf6_route *route;
 909
 910         node = route_top(table->table);
 911         if (node == NULL)
 912                 return NULL;
 913
 914         /* skip to the real existing entry */
 915         while (node && node->info == NULL)
 916                 node = route_next(node);
 917         if (node == NULL)
 918                 return NULL;
 919
 920         route_unlock_node(node);
 921         assert(node->info);
 922
 923         route = (struct ospf6_route *)node->info;
 924         assert(route->prev == NULL);
 925         assert(route->table == table);
 926         ospf6_route_lock(route);
 927
 928         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 929                 zlog_info("%s %p: route head: %p<-[%p]->%p",
 930                           ospf6_route_table_name(table), (void *)table,
 931                           (void *)route->prev, (void *)route,
 932                           (void *)route->next);
 933
 934         return route;
 935 }
 936
 937 struct ospf6_route *ospf6_route_next(struct ospf6_route *route)
 938 {
 939         struct ospf6_route *next = route->next;
 940
 941         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
 942                 zlog_info("%s %p: route next: %p<-[%p]->%p , route ref count %u",
 943                           ospf6_route_table_name(route->table),
 944                           (void *)route->table, (void *)route->prev,
 945                           (void *)route, (void *)route->next,
 946                           route->lock);
 947
 948         ospf6_route_unlock(route);
 949         if (next)
 950                 ospf6_route_lock(next);
 951
 952         return next;
 953 }
 954
 955 struct ospf6_route *ospf6_route_best_next(struct ospf6_route *route)
 956 {
 957         struct route_node *rnode;
 958         struct ospf6_route *next;
 959
 960         ospf6_route_unlock(route);
 961
 962         rnode = route->rnode;
 963         route_lock_node(rnode);
 964         rnode = route_next(rnode);
 965         while (rnode && rnode->info == NULL)
 966                 rnode = route_next(rnode);
 967         if (rnode == NULL)
 968                 return NULL;
 969         route_unlock_node(rnode);
 970
 971         assert(rnode->info);
 972         next = (struct ospf6_route *)rnode->info;
 973         ospf6_route_lock(next);
 974         return next;
 975 }
 976
 977 struct ospf6_route *ospf6_route_match_head(struct prefix *prefix,
 978                                            struct ospf6_route_table *table)
 979 {
 980         struct route_node *node;
 981         struct ospf6_route *route;
 982
 983         /* Walk down tree. */
 984         node = table->table->top;
 985         while (node && node->p.prefixlen < prefix->prefixlen
 986                && prefix_match(&node->p, prefix))
 987                 node = node->link[prefix_bit(&prefix->u.prefix,
 988                                              node->p.prefixlen)];
 989
 990         if (node)
 991                 route_lock_node(node);
 992         while (node && node->info == NULL)
 993                 node = route_next(node);
 994         if (node == NULL)
 995                 return NULL;
 996         route_unlock_node(node);
 997
 998         if (!prefix_match(prefix, &node->p))
 999                 return NULL;
1000
1001         route = node->info;
1002         ospf6_route_lock(route);
1003         return route;
1004 }
1005
1006 struct ospf6_route *ospf6_route_match_next(struct prefix *prefix,
1007                                            struct ospf6_route *route)
1008 {
1009         struct ospf6_route *next;
1010
1011         next = ospf6_route_next(route);
1012         if (next && !prefix_match(prefix, &next->prefix)) {
1013                 ospf6_route_unlock(next);
1014                 next = NULL;
1015         }
1016
1017         return next;
1018 }
1019
1020 void ospf6_route_remove_all(struct ospf6_route_table *table)
1021 {
1022         struct ospf6_route *route;
1023         for (route = ospf6_route_head(table); route;
1024              route = ospf6_route_next(route))
1025                 ospf6_route_remove(route, table);
1026 }
1027
1028 struct ospf6_route_table *ospf6_route_table_create(int s, int t)
1029 {
1030         struct ospf6_route_table *new;
1031         new = XCALLOC(MTYPE_OSPF6_ROUTE_TABLE,
1032                       sizeof(struct ospf6_route_table));
1033         new->table = route_table_init();
1034         new->scope_type = s;
1035         new->table_type = t;
1036         return new;
1037 }
1038
1039 void ospf6_route_table_delete(struct ospf6_route_table *table)
1040 {
1041         ospf6_route_remove_all(table);
1042         bf_free(table->idspace);
1043         route_table_finish(table->table);
1044         XFREE(MTYPE_OSPF6_ROUTE_TABLE, table);
1045 }
1046
1047
1048 /* VTY commands */
1049 void ospf6_route_show(struct vty *vty, struct ospf6_route *route,
1050                       json_object *json_routes, bool use_json)
1051 {
1052         int i;
1053         char destination[PREFIX2STR_BUFFER], nexthop[64];
1054         char duration[64];
1055         struct timeval now, res;
1056         struct listnode *node;
1057         struct ospf6_nexthop *nh;
1058         json_object *json_route = NULL;
1059         json_object *json_array_next_hops = NULL;
1060         json_object *json_next_hop;
1061
1062         if (om6->ospf6 == NULL) {
1063                 vty_out(vty, "OSPFv3 is not running\n");
1064                 return;
1065         }
1066
1067         monotime(&now);
1068         timersub(&now, &route->changed, &res);
1069         timerstring(&res, duration, sizeof(duration));
1070
1071         /* destination */
1072         if (route->type == OSPF6_DEST_TYPE_LINKSTATE)
1073                 ospf6_linkstate_prefix2str(&route->prefix, destination,
1074                                            sizeof(destination));
1075         else if (route->type == OSPF6_DEST_TYPE_ROUTER)
1076                 inet_ntop(route->prefix.family, &route->prefix.u.prefix,
1077                           destination, sizeof(destination));
1078         else
1079                 prefix2str(&route->prefix, destination, sizeof(destination));
1080
1081         if (use_json) {
1082                 json_route = json_object_new_object();
1083                 json_object_boolean_add(json_route, "isBestRoute",
1084                                         ospf6_route_is_best(route));
1085                 json_object_string_add(json_route, "destinationType",
1086                                        OSPF6_DEST_TYPE_SUBSTR(route->type));
1087                 json_object_string_add(
1088                         json_route, "pathType",
1089                         OSPF6_PATH_TYPE_SUBSTR(route->path.type));
1090                 json_object_string_add(json_route, "duration", duration);
1091         }
1092
1093         /* Nexthops */
1094         if (use_json)
1095                 json_array_next_hops = json_object_new_array();
1096         else
1097                 i = 0;
1098         for (ALL_LIST_ELEMENTS_RO(route->nh_list, node, nh)) {
1099                 struct interface *ifp;
1100                 /* nexthop */
1101                 inet_ntop(AF_INET6, &nh->address, nexthop, sizeof(nexthop));
1102                 ifp = if_lookup_by_index_all_vrf(nh->ifindex);
1103                 if (use_json) {
1104                         json_next_hop = json_object_new_object();
1105                         json_object_string_add(json_next_hop, "nextHop",
1106                                                nexthop);
1107                         json_object_string_add(json_next_hop, "interfaceName",
1108                                                ifp->name);
1109                         json_object_array_add(json_array_next_hops,
1110                                               json_next_hop);
1111                 } else {
1112                         if (!i) {
1113                                 vty_out(vty, "%c%1s %2s %-30s %-25s %6.*s %s\n",
1114                                         (ospf6_route_is_best(route) ? '*'
1115                                                                     : ' '),
1116                                         OSPF6_DEST_TYPE_SUBSTR(route->type),
1117                                         OSPF6_PATH_TYPE_SUBSTR(
1118                                                 route->path.type),
1119                                         destination, nexthop, IFNAMSIZ,
1120                                         ifp->name, duration);
1121                                 i++;
1122                         } else
1123                                 vty_out(vty, "%c%1s %2s %-30s %-25s %6.*s %s\n",
1124                                         ' ', "", "", "", nexthop, IFNAMSIZ,
1125                                         ifp->name, "");
1126                 }
1127         }
1128         if (use_json) {
1129                 json_object_object_add(json_route, "nextHops",
1130                                        json_array_next_hops);
1131                 json_object_object_add(json_routes, destination, json_route);
1132         }
1133 }
1134
1135 void ospf6_route_show_detail(struct vty *vty, struct ospf6_route *route,
1136                              json_object *json_routes, bool use_json)
1137 {
1138         char destination[PREFIX2STR_BUFFER], nexthop[64];
1139         char area_id[16], id[16], adv_router[16], capa[16], options[16];
1140         struct timeval now, res;
1141         char duration[64];
1142         struct listnode *node;
1143         struct ospf6_nexthop *nh;
1144         char flag[6];
1145         json_object *json_route = NULL;
1146         json_object *json_array_next_hops = NULL;
1147         json_object *json_next_hop;
1148
1149         if (om6->ospf6 == NULL) {
1150                 vty_out(vty, "OSPFv3 is not running\n");
1151                 return;
1152         }
1153
1154         monotime(&now);
1155
1156         /* destination */
1157         if (route->type == OSPF6_DEST_TYPE_LINKSTATE)
1158                 ospf6_linkstate_prefix2str(&route->prefix, destination,
1159                                            sizeof(destination));
1160         else if (route->type == OSPF6_DEST_TYPE_ROUTER)
1161                 inet_ntop(route->prefix.family, &route->prefix.u.prefix,
1162                           destination, sizeof(destination));
1163         else
1164                 prefix2str(&route->prefix, destination, sizeof(destination));
1165
1166         if (use_json) {
1167                 json_route = json_object_new_object();
1168                 json_object_string_add(json_route, "destinationType",
1169                                        OSPF6_DEST_TYPE_NAME(route->type));
1170         } else {
1171                 vty_out(vty, "Destination: %s\n", destination);
1172                 vty_out(vty, "Destination type: %s\n",
1173                         OSPF6_DEST_TYPE_NAME(route->type));
1174         }
1175
1176         /* Time */
1177         timersub(&now, &route->installed, &res);
1178         timerstring(&res, duration, sizeof(duration));
1179         if (use_json)
1180                 json_object_string_add(json_route, "installedTimeSince",
1181                                        duration);
1182         else
1183                 vty_out(vty, "Installed Time: %s ago\n", duration);
1184
1185         timersub(&now, &route->changed, &res);
1186         timerstring(&res, duration, sizeof(duration));
1187         if (use_json)
1188                 json_object_string_add(json_route, "changedTimeSince",
1189                                        duration);
1190         else
1191                 vty_out(vty, "Changed Time: %s ago\n", duration);
1192
1193         /* Debugging info */
1194         if (use_json) {
1195                 json_object_int_add(json_route, "numberOfLock", route->lock);
1196                 snprintf(
1197                         flag, sizeof(flag), "%s%s%s%s",
1198                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_BEST) ? "B" : "-"),
1199                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD) ? "A" : "-"),
1200                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE) ? "R"
1201                                                                      : "-"),
1202                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE) ? "C"
1203                                                                      : "-"));
1204                 json_object_string_add(json_route, "flags", flag);
1205         } else {
1206                 vty_out(vty, "Lock: %d Flags: %s%s%s%s\n", route->lock,
1207                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_BEST) ? "B" : "-"),
1208                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_ADD) ? "A" : "-"),
1209                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_REMOVE) ? "R"
1210                                                                      : "-"),
1211                         (CHECK_FLAG(route->flag, OSPF6_ROUTE_CHANGE) ? "C"
1212                                                                      : "-"));
1213                 vty_out(vty, "Memory: prev: %p this: %p next: %p\n",
1214                         (void *)route->prev, (void *)route,
1215                         (void *)route->next);
1216         }
1217
1218         /* Path section */
1219
1220         /* Area-ID */
1221         inet_ntop(AF_INET, &route->path.area_id, area_id, sizeof(area_id));
1222         if (use_json)
1223                 json_object_string_add(json_route, "associatedArea", area_id);
1224         else
1225                 vty_out(vty, "Associated Area: %s\n", area_id);
1226
1227         /* Path type */
1228         if (use_json)
1229                 json_object_string_add(json_route, "pathType",
1230                                        OSPF6_PATH_TYPE_NAME(route->path.type));
1231         else
1232                 vty_out(vty, "Path Type: %s\n",
1233                         OSPF6_PATH_TYPE_NAME(route->path.type));
1234
1235         /* LS Origin */
1236         inet_ntop(AF_INET, &route->path.origin.id, id, sizeof(id));
1237         inet_ntop(AF_INET, &route->path.origin.adv_router, adv_router,
1238                   sizeof(adv_router));
1239         if (use_json) {
1240                 json_object_string_add(
1241                         json_route, "lsOriginRoutePathType",
1242                         ospf6_lstype_name(route->path.origin.type));
1243                 json_object_string_add(json_route, "lsId", id);
1244                 json_object_string_add(json_route, "lsAdvertisingRouter",
1245                                        adv_router);
1246         } else {
1247                 vty_out(vty, "LS Origin: %s Id: %s Adv: %s\n",
1248                         ospf6_lstype_name(route->path.origin.type), id,
1249                         adv_router);
1250         }
1251
1252         /* Options */
1253         ospf6_options_printbuf(route->path.options, options, sizeof(options));
1254         if (use_json)
1255                 json_object_string_add(json_route, "options", options);
1256         else
1257                 vty_out(vty, "Options: %s\n", options);
1258
1259         /* Router Bits */
1260         ospf6_capability_printbuf(route->path.router_bits, capa, sizeof(capa));
1261         if (use_json)
1262                 json_object_string_add(json_route, "routerBits", capa);
1263         else
1264                 vty_out(vty, "Router Bits: %s\n", capa);
1265
1266         /* Prefix Options */
1267         if (use_json)
1268                 json_object_string_add(json_route, "prefixOptions", "xxx");
1269         else
1270                 vty_out(vty, "Prefix Options: xxx\n");
1271
1272         /* Metrics */
1273         if (use_json) {
1274                 json_object_int_add(json_route, "metricType",
1275                                     route->path.metric_type);
1276                 json_object_int_add(json_route, "metricCost", route->path.cost);
1277                 json_object_int_add(json_route, "metricCostE2",
1278                                     route->path.u.cost_e2);
1279
1280                 json_object_int_add(json_route, "pathsCount",
1281                                     route->paths->count);
1282                 json_object_int_add(json_route, "nextHopCount",
1283                                     route->nh_list->count);
1284         } else {
1285                 vty_out(vty, "Metric Type: %d\n", route->path.metric_type);
1286                 vty_out(vty, "Metric: %d (%d)\n", route->path.cost,
1287                         route->path.u.cost_e2);
1288
1289                 vty_out(vty, "Paths count: %u\n", route->paths->count);
1290                 vty_out(vty, "Nexthop count: %u\n", route->nh_list->count);
1291         }
1292
1293         /* Nexthops */
1294         if (use_json)
1295                 json_array_next_hops = json_object_new_array();
1296         else
1297                 vty_out(vty, "Nexthop:\n");
1298
1299         for (ALL_LIST_ELEMENTS_RO(route->nh_list, node, nh)) {
1300                 struct interface *ifp;
1301                 ifp = if_lookup_by_index_all_vrf(nh->ifindex);
1302                 /* nexthop */
1303                 if (use_json) {
1304                         inet_ntop(AF_INET6, &nh->address, nexthop,
1305                                   sizeof(nexthop));
1306                         json_next_hop = json_object_new_object();
1307                         json_object_string_add(json_next_hop, "nextHop",
1308                                                nexthop);
1309                         json_object_string_add(json_next_hop, "interfaceName",
1310                                                ifp->name);
1311                         json_object_array_add(json_array_next_hops,
1312                                               json_next_hop);
1313                 } else
1314                         vty_out(vty, "  %pI6 %.*s\n", &nh->address, IFNAMSIZ,
1315                                 ifp->name);
1316         }
1317         if (use_json) {
1318                 json_object_object_add(json_route, "nextHops",
1319                                        json_array_next_hops);
1320                 json_object_object_add(json_routes, destination, json_route);
1321         } else
1322                 vty_out(vty, "\n");
1323 }
1324
1325 static void ospf6_route_show_table_summary(struct vty *vty,
1326                                            struct ospf6_route_table *table,
1327                                            json_object *json, bool use_json)
1328 {
1329         struct ospf6_route *route, *prev = NULL;
1330         int i, pathtype[OSPF6_PATH_TYPE_MAX];
1331         unsigned int number = 0;
1332         int nh_count = 0, nhinval = 0, ecmp = 0;
1333         int alternative = 0, destination = 0;
1334         char path_str[30];
1335
1336         for (i = 0; i < OSPF6_PATH_TYPE_MAX; i++)
1337                 pathtype[i] = 0;
1338
1339         for (route = ospf6_route_head(table); route;
1340              route = ospf6_route_next(route)) {
1341                 if (prev == NULL || !ospf6_route_is_same(prev, route))
1342                         destination++;
1343                 else
1344                         alternative++;
1345                 nh_count = ospf6_num_nexthops(route->nh_list);
1346                 if (!nh_count)
1347                         nhinval++;
1348                 else if (nh_count > 1)
1349                         ecmp++;
1350                 pathtype[route->path.type]++;
1351                 number++;
1352
1353                 prev = route;
1354         }
1355
1356         assert(number == table->count);
1357         if (use_json) {
1358                 json_object_int_add(json, "numberOfOspfv3Routes", number);
1359                 json_object_int_add(json, "numberOfDestination", destination);
1360                 json_object_int_add(json, "numberOfAlternativeRoutes",
1361                                     alternative);
1362                 json_object_int_add(json, "numberOfEcmp", ecmp);
1363         } else {
1364                 vty_out(vty, "Number of OSPFv3 routes: %d\n", number);
1365                 vty_out(vty, "Number of Destination: %d\n", destination);
1366                 vty_out(vty, "Number of Alternative routes: %d\n", alternative);
1367                 vty_out(vty, "Number of Equal Cost Multi Path: %d\n", ecmp);
1368         }
1369         for (i = OSPF6_PATH_TYPE_INTRA; i <= OSPF6_PATH_TYPE_EXTERNAL2; i++) {
1370                 if (use_json) {
1371                         snprintf(path_str, sizeof(path_str), "numberOf%sRoutes",
1372                                  OSPF6_PATH_TYPE_JSON(i));
1373                         json_object_int_add(json, path_str, pathtype[i]);
1374                 } else
1375                         vty_out(vty, "Number of %s routes: %d\n",
1376                                 OSPF6_PATH_TYPE_NAME(i), pathtype[i]);
1377         }
1378 }
1379
1380 static void ospf6_route_show_table_prefix(struct vty *vty,
1381                                           struct prefix *prefix,
1382                                           struct ospf6_route_table *table,
1383                                           json_object *json, bool use_json)
1384 {
1385         struct ospf6_route *route;
1386         json_object *json_routes = NULL;
1387
1388         route = ospf6_route_lookup(prefix, table);
1389         if (route == NULL)
1390                 return;
1391
1392         if (use_json)
1393                 json_routes = json_object_new_object();
1394         ospf6_route_lock(route);
1395         while (route && ospf6_route_is_prefix(prefix, route)) {
1396                 /* Specifying a prefix will always display details */
1397                 ospf6_route_show_detail(vty, route, json_routes, use_json);
1398                 route = ospf6_route_next(route);
1399         }
1400
1401         if (use_json)
1402                 json_object_object_add(json, "routes", json_routes);
1403         if (route)
1404                 ospf6_route_unlock(route);
1405 }
1406
1407 static void ospf6_route_show_table_address(struct vty *vty,
1408                                            struct prefix *prefix,
1409                                            struct ospf6_route_table *table,
1410                                            json_object *json, bool use_json)
1411 {
1412         struct ospf6_route *route;
1413         json_object *json_routes = NULL;
1414
1415         route = ospf6_route_lookup_bestmatch(prefix, table);
1416         if (route == NULL)
1417                 return;
1418
1419         if (use_json)
1420                 json_routes = json_object_new_object();
1421         prefix = &route->prefix;
1422         ospf6_route_lock(route);
1423         while (route && ospf6_route_is_prefix(prefix, route)) {
1424                 /* Specifying a prefix will always display details */
1425                 ospf6_route_show_detail(vty, route, json_routes, use_json);
1426                 route = ospf6_route_next(route);
1427         }
1428         if (use_json)
1429                 json_object_object_add(json, "routes", json_routes);
1430         if (route)
1431                 ospf6_route_unlock(route);
1432 }
1433
1434 static void ospf6_route_show_table_match(struct vty *vty, int detail,
1435                                          struct prefix *prefix,
1436                                          struct ospf6_route_table *table,
1437                                          json_object *json, bool use_json)
1438 {
1439         struct ospf6_route *route;
1440         json_object *json_routes = NULL;
1441
1442         assert(prefix->family);
1443
1444         route = ospf6_route_match_head(prefix, table);
1445         if (use_json)
1446                 json_routes = json_object_new_object();
1447         while (route) {
1448                 if (detail)
1449                         ospf6_route_show_detail(vty, route, json_routes,
1450                                                 use_json);
1451                 else
1452                         ospf6_route_show(vty, route, json_routes, use_json);
1453                 route = ospf6_route_match_next(prefix, route);
1454         }
1455         if (use_json)
1456                 json_object_object_add(json, "routes", json_routes);
1457 }
1458
1459 static void ospf6_route_show_table_type(struct vty *vty, int detail,
1460                                         uint8_t type,
1461                                         struct ospf6_route_table *table,
1462                                         json_object *json, bool use_json)
1463 {
1464         struct ospf6_route *route;
1465         json_object *json_routes = NULL;
1466
1467         route = ospf6_route_head(table);
1468         if (use_json)
1469                 json_routes = json_object_new_object();
1470         while (route) {
1471                 if (route->path.type == type) {
1472                         if (detail)
1473                                 ospf6_route_show_detail(vty, route, json_routes,
1474                                                         use_json);
1475                         else
1476                                 ospf6_route_show(vty, route, json_routes,
1477                                                  use_json);
1478                 }
1479                 route = ospf6_route_next(route);
1480         }
1481         if (use_json)
1482                 json_object_object_add(json, "routes", json_routes);
1483 }
1484
1485 static void ospf6_route_show_table(struct vty *vty, int detail,
1486                                    struct ospf6_route_table *table,
1487                                    json_object *json, bool use_json)
1488 {
1489         struct ospf6_route *route;
1490         json_object *json_routes = NULL;
1491
1492         route = ospf6_route_head(table);
1493         if (use_json)
1494                 json_routes = json_object_new_object();
1495         while (route) {
1496                 if (detail)
1497                         ospf6_route_show_detail(vty, route, json_routes,
1498                                                 use_json);
1499                 else
1500                         ospf6_route_show(vty, route, json_routes, use_json);
1501                 route = ospf6_route_next(route);
1502         }
1503         if (use_json)
1504                 json_object_object_add(json, "routes", json_routes);
1505 }
1506
1507 int ospf6_route_table_show(struct vty *vty, int argc_start, int argc,
1508                            struct cmd_token **argv,
1509                            struct ospf6_route_table *table, bool use_json)
1510 {
1511         int summary = 0;
1512         int match = 0;
1513         int detail = 0;
1514         int slash = 0;
1515         int isprefix = 0;
1516         int i, ret;
1517         struct prefix prefix;
1518         uint8_t type = 0;
1519         int arg_end = use_json ? (argc - 1) : argc;
1520         json_object *json = NULL;
1521
1522         memset(&prefix, 0, sizeof(struct prefix));
1523
1524         if (use_json)
1525                 json = json_object_new_object();
1526
1527         for (i = argc_start; i < arg_end; i++) {
1528                 if (strmatch(argv[i]->text, "summary")) {
1529                         summary++;
1530                         continue;
1531                 }
1532
1533                 if (strmatch(argv[i]->text, "intra-area")) {
1534                         type = OSPF6_PATH_TYPE_INTRA;
1535                         continue;
1536                 }
1537
1538                 if (strmatch(argv[i]->text, "inter-area")) {
1539                         type = OSPF6_PATH_TYPE_INTER;
1540                         continue;
1541                 }
1542
1543                 if (strmatch(argv[i]->text, "external-1")) {
1544                         type = OSPF6_PATH_TYPE_EXTERNAL1;
1545                         continue;
1546                 }
1547
1548                 if (strmatch(argv[i]->text, "external-2")) {
1549                         type = OSPF6_PATH_TYPE_EXTERNAL2;
1550                         continue;
1551                 }
1552
1553                 if (strmatch(argv[i]->text, "detail")) {
1554                         detail++;
1555                         continue;
1556                 }
1557
1558                 if (strmatch(argv[i]->text, "match")) {
1559                         match++;
1560                         continue;
1561                 }
1562
1563                 ret = str2prefix(argv[i]->arg, &prefix);
1564                 if (ret == 1 && prefix.family == AF_INET6) {
1565                         isprefix++;
1566                         if (strchr(argv[i]->arg, '/'))
1567                                 slash++;
1568                         continue;
1569                 }
1570                 if (use_json)
1571                         json_object_string_add(json, "malformedArgument",
1572                                                argv[i]->arg);
1573                 else
1574                         vty_out(vty, "Malformed argument: %s\n", argv[i]->arg);
1575
1576                 return CMD_SUCCESS;
1577         }
1578
1579         /* Give summary of this route table */
1580         if (summary) {
1581                 ospf6_route_show_table_summary(vty, table, json, use_json);
1582                 if (use_json) {
1583                         vty_out(vty, "%s\n",
1584                                 json_object_to_json_string_ext(
1585                                         json, JSON_C_TO_STRING_PRETTY));
1586                         json_object_free(json);
1587                 }
1588                 return CMD_SUCCESS;
1589         }
1590
1591         /* Give exact prefix-match route */
1592         if (isprefix && !match) {
1593                 /* If exact address, give best matching route */
1594                 if (!slash)
1595                         ospf6_route_show_table_address(vty, &prefix, table,
1596                                                        json, use_json);
1597                 else
1598                         ospf6_route_show_table_prefix(vty, &prefix, table, json,
1599                                                       use_json);
1600
1601                 if (use_json) {
1602                         vty_out(vty, "%s\n",
1603                                 json_object_to_json_string_ext(
1604                                         json, JSON_C_TO_STRING_PRETTY));
1605                         json_object_free(json);
1606                 }
1607                 return CMD_SUCCESS;
1608         }
1609
1610         if (match)
1611                 ospf6_route_show_table_match(vty, detail, &prefix, table, json,
1612                                              use_json);
1613         else if (type)
1614                 ospf6_route_show_table_type(vty, detail, type, table, json,
1615                                             use_json);
1616         else
1617                 ospf6_route_show_table(vty, detail, table, json, use_json);
1618
1619         if (use_json) {
1620                 vty_out(vty, "%s\n",
1621                         json_object_to_json_string_ext(
1622                                 json, JSON_C_TO_STRING_PRETTY));
1623                 json_object_free(json);
1624         }
1625         return CMD_SUCCESS;
1626 }
1627
1628 static void ospf6_linkstate_show_header(struct vty *vty)
1629 {
1630         vty_out(vty, "%-7s %-15s %-15s %-8s %-14s %s\n", "Type", "Router-ID",
1631                 "Net-ID", "Rtr-Bits", "Options", "Cost");
1632 }
1633
1634 static void ospf6_linkstate_show(struct vty *vty, struct ospf6_route *route)
1635 {
1636         uint32_t router, id;
1637         char routername[16], idname[16], rbits[16], options[16];
1638
1639         router = ospf6_linkstate_prefix_adv_router(&route->prefix);
1640         inet_ntop(AF_INET, &router, routername, sizeof(routername));
1641         id = ospf6_linkstate_prefix_id(&route->prefix);
1642         inet_ntop(AF_INET, &id, idname, sizeof(idname));
1643
1644         ospf6_capability_printbuf(route->path.router_bits, rbits,
1645                                   sizeof(rbits));
1646         ospf6_options_printbuf(route->path.options, options, sizeof(options));
1647
1648         if (ntohl(id))
1649                 vty_out(vty, "%-7s %-15s %-15s %-8s %-14s %lu\n", "Network",
1650                         routername, idname, rbits, options,
1651                         (unsigned long)route->path.cost);
1652         else
1653                 vty_out(vty, "%-7s %-15s %-15s %-8s %-14s %lu\n", "Router",
1654                         routername, idname, rbits, options,
1655                         (unsigned long)route->path.cost);
1656 }
1657
1658
1659 static void ospf6_linkstate_show_table_exact(struct vty *vty,
1660                                              struct prefix *prefix,
1661                                              struct ospf6_route_table *table)
1662 {
1663         struct ospf6_route *route;
1664
1665         route = ospf6_route_lookup(prefix, table);
1666         if (route == NULL)
1667                 return;
1668
1669         ospf6_route_lock(route);
1670         while (route && ospf6_route_is_prefix(prefix, route)) {
1671                 /* Specifying a prefix will always display details */
1672                 ospf6_route_show_detail(vty, route, NULL, false);
1673                 route = ospf6_route_next(route);
1674         }
1675         if (route)
1676                 ospf6_route_unlock(route);
1677 }
1678
1679 static void ospf6_linkstate_show_table(struct vty *vty, int detail,
1680                                        struct ospf6_route_table *table)
1681 {
1682         struct ospf6_route *route;
1683
1684         if (!detail)
1685                 ospf6_linkstate_show_header(vty);
1686
1687         route = ospf6_route_head(table);
1688         while (route) {
1689                 if (detail)
1690                         ospf6_route_show_detail(vty, route, NULL, false);
1691                 else
1692                         ospf6_linkstate_show(vty, route);
1693                 route = ospf6_route_next(route);
1694         }
1695 }
1696
1697 int ospf6_linkstate_table_show(struct vty *vty, int idx_ipv4, int argc,
1698                                struct cmd_token **argv,
1699                                struct ospf6_route_table *table)
1700 {
1701         int detail = 0;
1702         int is_id = 0;
1703         int is_router = 0;
1704         int i, ret;
1705         struct prefix router, id, prefix;
1706
1707         memset(&router, 0, sizeof(struct prefix));
1708         memset(&id, 0, sizeof(struct prefix));
1709         memset(&prefix, 0, sizeof(struct prefix));
1710
1711         for (i = idx_ipv4; i < argc; i++) {
1712                 if (strmatch(argv[i]->text, "detail")) {
1713                         detail++;
1714                         continue;
1715                 }
1716
1717                 if (!is_router) {
1718                         ret = str2prefix(argv[i]->arg, &router);
1719                         if (ret == 1 && router.family == AF_INET) {
1720                                 is_router++;
1721                                 continue;
1722                         }
1723                         vty_out(vty, "Malformed argument: %s\n", argv[i]->arg);
1724                         return CMD_SUCCESS;
1725                 }
1726
1727                 if (!is_id) {
1728                         ret = str2prefix(argv[i]->arg, &id);
1729                         if (ret == 1 && id.family == AF_INET) {
1730                                 is_id++;
1731                                 continue;
1732                         }
1733                         vty_out(vty, "Malformed argument: %s\n", argv[i]->arg);
1734                         return CMD_SUCCESS;
1735                 }
1736
1737                 vty_out(vty, "Malformed argument: %s\n", argv[i]->arg);
1738                 return CMD_SUCCESS;
1739         }
1740
1741         if (is_router)
1742                 ospf6_linkstate_prefix(router.u.prefix4.s_addr,
1743                                        id.u.prefix4.s_addr, &prefix);
1744
1745         if (prefix.family)
1746                 ospf6_linkstate_show_table_exact(vty, &prefix, table);
1747         else
1748                 ospf6_linkstate_show_table(vty, detail, table);
1749
1750         return CMD_SUCCESS;
1751 }
1752
1753
1754 void ospf6_brouter_show_header(struct vty *vty)
1755 {
1756         vty_out(vty, "%-15s %-8s %-14s %-10s %-15s\n", "Router-ID", "Rtr-Bits",
1757                 "Options", "Path-Type", "Area");
1758 }
1759
1760 void ospf6_brouter_show(struct vty *vty, struct ospf6_route *route)
1761 {
1762         uint32_t adv_router;
1763         char adv[16], rbits[16], options[16], area[16];
1764
1765         adv_router = ospf6_linkstate_prefix_adv_router(&route->prefix);
1766         inet_ntop(AF_INET, &adv_router, adv, sizeof(adv));
1767         ospf6_capability_printbuf(route->path.router_bits, rbits,
1768                                   sizeof(rbits));
1769         ospf6_options_printbuf(route->path.options, options, sizeof(options));
1770         inet_ntop(AF_INET, &route->path.area_id, area, sizeof(area));
1771
1772         /* vty_out (vty, "%-15s %-8s %-14s %-10s %-15s\n",
1773                  "Router-ID", "Rtr-Bits", "Options", "Path-Type", "Area"); */
1774         vty_out(vty, "%-15s %-8s %-14s %-10s %-15s\n", adv, rbits, options,
1775                 OSPF6_PATH_TYPE_NAME(route->path.type), area);
1776 }
1777
1778 DEFUN (debug_ospf6_route,
1779        debug_ospf6_route_cmd,
1780        "debug ospf6 route <table|intra-area|inter-area|memory>",
1781        DEBUG_STR
1782        OSPF6_STR
1783        "Debug routes\n"
1784        "Debug route table calculation\n"
1785        "Debug intra-area route calculation\n"
1786        "Debug inter-area route calculation\n"
1787        "Debug route memory use\n"
1788        )
1789 {
1790         int idx_type = 3;
1791         unsigned char level = 0;
1792
1793         if (!strcmp(argv[idx_type]->text, "table"))
1794                 level = OSPF6_DEBUG_ROUTE_TABLE;
1795         else if (!strcmp(argv[idx_type]->text, "intra-area"))
1796                 level = OSPF6_DEBUG_ROUTE_INTRA;
1797         else if (!strcmp(argv[idx_type]->text, "inter-area"))
1798                 level = OSPF6_DEBUG_ROUTE_INTER;
1799         else if (!strcmp(argv[idx_type]->text, "memory"))
1800                 level = OSPF6_DEBUG_ROUTE_MEMORY;
1801         OSPF6_DEBUG_ROUTE_ON(level);
1802         return CMD_SUCCESS;
1803 }
1804
1805 DEFUN (no_debug_ospf6_route,
1806        no_debug_ospf6_route_cmd,
1807        "no debug ospf6 route <table|intra-area|inter-area|memory>",
1808        NO_STR
1809        DEBUG_STR
1810        OSPF6_STR
1811        "Debug routes\n"
1812        "Debug route table calculation\n"
1813        "Debug intra-area route calculation\n"
1814        "Debug inter-area route calculation\n"
1815        "Debug route memory use\n")
1816 {
1817         int idx_type = 4;
1818         unsigned char level = 0;
1819
1820         if (!strcmp(argv[idx_type]->text, "table"))
1821                 level = OSPF6_DEBUG_ROUTE_TABLE;
1822         else if (!strcmp(argv[idx_type]->text, "intra-area"))
1823                 level = OSPF6_DEBUG_ROUTE_INTRA;
1824         else if (!strcmp(argv[idx_type]->text, "inter-area"))
1825                 level = OSPF6_DEBUG_ROUTE_INTER;
1826         else if (!strcmp(argv[idx_type]->text, "memory"))
1827                 level = OSPF6_DEBUG_ROUTE_MEMORY;
1828         OSPF6_DEBUG_ROUTE_OFF(level);
1829         return CMD_SUCCESS;
1830 }
1831
1832 int config_write_ospf6_debug_route(struct vty *vty)
1833 {
1834         if (IS_OSPF6_DEBUG_ROUTE(TABLE))
1835                 vty_out(vty, "debug ospf6 route table\n");
1836         if (IS_OSPF6_DEBUG_ROUTE(INTRA))
1837                 vty_out(vty, "debug ospf6 route intra-area\n");
1838         if (IS_OSPF6_DEBUG_ROUTE(INTER))
1839                 vty_out(vty, "debug ospf6 route inter-area\n");
1840         if (IS_OSPF6_DEBUG_ROUTE(MEMORY))
1841                 vty_out(vty, "debug ospf6 route memory\n");
1842
1843         return 0;
1844 }
1845
1846 void install_element_ospf6_debug_route(void)
1847 {
1848         install_element(ENABLE_NODE, &debug_ospf6_route_cmd);
1849         install_element(ENABLE_NODE, &no_debug_ospf6_route_cmd);
1850         install_element(CONFIG_NODE, &debug_ospf6_route_cmd);
1851         install_element(CONFIG_NODE, &no_debug_ospf6_route_cmd);
1852 }