ospf6d/ospf6_route.c

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