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