pbrd/pbr_nht.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * PBR-nht Code
   4  * Copyright (C) 2018 Cumulus Networks, Inc.
   5  *               Donald Sharp
   6  */
   7 #include <zebra.h>
   8
   9 #include <log.h>
  10 #include <nexthop.h>
  11 #include "nexthop_group.h"
  12 #include "nexthop_group_private.h"
  13 #include <hash.h>
  14 #include <jhash.h>
  15 #include <vty.h>
  16 #include <zclient.h>
  17 #include <debug.h>
  18
  19 #include "pbrd/pbr_nht.h"
  20 #include "pbrd/pbr_map.h"
  21 #include "pbrd/pbr_zebra.h"
  22 #include "pbrd/pbr_memory.h"
  23 #include "pbrd/pbr_debug.h"
  24
  25 DEFINE_MTYPE_STATIC(PBRD, PBR_NHG, "PBR Nexthop Groups");
  26
  27 struct hash *pbr_nhg_hash;
  28 static struct hash *pbr_nhrc_hash;
  29 static struct hash *pbr_nhg_allocated_id_hash;
  30
  31 static uint32_t pbr_nhg_low_table;
  32 static uint32_t pbr_nhg_high_table;
  33 static uint32_t pbr_next_unallocated_table_id;
  34 static uint32_t pbr_nhg_low_rule;
  35 static uint32_t pbr_nhg_high_rule;
  36
  37 static void pbr_nht_install_nexthop_group(struct pbr_nexthop_group_cache *pnhgc,
  38                                           struct nexthop_group nhg);
  39 static void
  40 pbr_nht_uninstall_nexthop_group(struct pbr_nexthop_group_cache *pnhgc,
  41                                 struct nexthop_group nhg,
  42                                 enum nexthop_types_t nh_type);
  43
  44 /*
  45  * Nexthop refcount.
  46  */
  47 struct nhrc {
  48         struct nexthop nexthop;
  49         unsigned int refcount;
  50 };
  51
  52 /* Hash functions for pbr_nhrc_hash ---------------------------------------- */
  53
  54 static void *pbr_nhrc_hash_alloc(void *p)
  55 {
  56         struct nhrc *nhrc = XCALLOC(MTYPE_PBR_NHG, sizeof(struct nhrc));
  57         nhrc->nexthop = *(struct nexthop *)p;
  58         nhrc->nexthop.next = NULL;
  59         nhrc->nexthop.prev = NULL;
  60         return nhrc;
  61 }
  62
  63 static bool pbr_nhrc_hash_equal(const void *arg1, const void *arg2)
  64 {
  65         const struct nexthop *nh1, *nh2;
  66
  67         nh1 = arg1;
  68         nh2 = arg2;
  69
  70         return nexthop_same(nh1, nh2);
  71 }
  72
  73 /* ------------------------------------------------------------------------- */
  74
  75 static void *pbr_nh_alloc(void *p)
  76 {
  77         struct pbr_nexthop_cache *new;
  78         struct pbr_nexthop_cache *pnhc = (struct pbr_nexthop_cache *)p;
  79         struct nhrc *nhrc;
  80
  81         new = XCALLOC(MTYPE_PBR_NHG, sizeof(*new));
  82         nhrc = hash_get(pbr_nhrc_hash, &pnhc->nexthop, pbr_nhrc_hash_alloc);
  83         new->nexthop = nhrc->nexthop;
  84
  85         /* Decremented again in pbr_nh_delete */
  86         ++nhrc->refcount;
  87
  88         DEBUGD(&pbr_dbg_nht, "%s: Sending nexthop to Zebra", __func__);
  89
  90         pbr_send_rnh(&new->nexthop, true);
  91
  92         new->valid = false;
  93         return new;
  94 }
  95
  96 static void pbr_nh_delete(struct pbr_nexthop_cache **pnhc)
  97 {
  98         struct nhrc *nhrc;
  99
 100         nhrc = hash_lookup(pbr_nhrc_hash, &((*pnhc)->nexthop));
 101
 102         if (nhrc)
 103                 --nhrc->refcount;
 104         if (!nhrc || nhrc->refcount == 0) {
 105                 DEBUGD(&pbr_dbg_nht, "%s: Removing nexthop from Zebra",
 106                        __func__);
 107                 pbr_send_rnh(&((*pnhc)->nexthop), false);
 108         }
 109         if (nhrc && nhrc->refcount == 0) {
 110                 hash_release(pbr_nhrc_hash, nhrc);
 111                 XFREE(MTYPE_PBR_NHG, nhrc);
 112         }
 113
 114         XFREE(MTYPE_PBR_NHG, *pnhc);
 115 }
 116
 117 static void pbr_nh_delete_iterate(struct hash_bucket *b, void *p)
 118 {
 119         pbr_nh_delete((struct pbr_nexthop_cache **)&b->data);
 120 }
 121
 122 static uint32_t pbr_nh_hash_key(const void *arg)
 123 {
 124         uint32_t key;
 125         const struct pbr_nexthop_cache *pbrnc = arg;
 126
 127         key = nexthop_hash(&pbrnc->nexthop);
 128
 129         return key;
 130 }
 131
 132 static bool pbr_nh_hash_equal(const void *arg1, const void *arg2)
 133 {
 134         const struct pbr_nexthop_cache *pbrnc1 =
 135                 (const struct pbr_nexthop_cache *)arg1;
 136         const struct pbr_nexthop_cache *pbrnc2 =
 137                 (const struct pbr_nexthop_cache *)arg2;
 138
 139         if (pbrnc1->nexthop.vrf_id != pbrnc2->nexthop.vrf_id)
 140                 return false;
 141
 142         if (pbrnc1->nexthop.ifindex != pbrnc2->nexthop.ifindex)
 143                 return false;
 144
 145         if (pbrnc1->nexthop.type != pbrnc2->nexthop.type)
 146                 return false;
 147
 148         switch (pbrnc1->nexthop.type) {
 149         case NEXTHOP_TYPE_IFINDEX:
 150                 return pbrnc1->nexthop.ifindex == pbrnc2->nexthop.ifindex;
 151         case NEXTHOP_TYPE_IPV4_IFINDEX:
 152         case NEXTHOP_TYPE_IPV4:
 153                 return pbrnc1->nexthop.gate.ipv4.s_addr
 154                        == pbrnc2->nexthop.gate.ipv4.s_addr;
 155         case NEXTHOP_TYPE_IPV6_IFINDEX:
 156         case NEXTHOP_TYPE_IPV6:
 157                 return !memcmp(&pbrnc1->nexthop.gate.ipv6,
 158                                &pbrnc2->nexthop.gate.ipv6, 16);
 159         case NEXTHOP_TYPE_BLACKHOLE:
 160                 return pbrnc1->nexthop.bh_type == pbrnc2->nexthop.bh_type;
 161         }
 162
 163         /*
 164          * We should not get here
 165          */
 166         return false;
 167 }
 168
 169 static void pbr_nhgc_delete(struct pbr_nexthop_group_cache *p)
 170 {
 171         hash_iterate(p->nhh, pbr_nh_delete_iterate, NULL);
 172         hash_free(p->nhh);
 173         XFREE(MTYPE_PBR_NHG, p);
 174 }
 175
 176 static void *pbr_nhgc_alloc(void *p)
 177 {
 178         struct pbr_nexthop_group_cache *new;
 179         struct pbr_nexthop_group_cache *pnhgc =
 180                 (struct pbr_nexthop_group_cache *)p;
 181
 182         new = XCALLOC(MTYPE_PBR_NHG, sizeof(*new));
 183
 184         strlcpy(new->name, pnhgc->name, sizeof(pnhgc->name));
 185         pbr_nht_reserve_next_table_id(new);
 186
 187         DEBUGD(&pbr_dbg_nht, "%s: NHT: %s assigned Table ID: %u", __func__,
 188                new->name, new->table_id);
 189
 190         new->nhh = hash_create_size(8, pbr_nh_hash_key, pbr_nh_hash_equal,
 191                                     "PBR NH Cache Hash");
 192         return new;
 193 }
 194
 195
 196 void pbr_nhgroup_add_cb(const char *name)
 197 {
 198         struct pbr_nexthop_group_cache *pnhgc;
 199         struct nexthop_group_cmd *nhgc;
 200
 201         nhgc = nhgc_find(name);
 202
 203         if (!nhgc) {
 204                 DEBUGD(&pbr_dbg_nht, "%s: Could not find nhgc with name: %s",
 205                        __func__, name);
 206                 return;
 207         }
 208
 209         pnhgc = pbr_nht_add_group(name);
 210
 211         if (!pnhgc)
 212                 return;
 213
 214         DEBUGD(&pbr_dbg_nht, "%s: Added nexthop-group %s", __func__, name);
 215
 216         pbr_map_check_nh_group_change(name);
 217 }
 218
 219 void pbr_nhgroup_modify_cb(const struct nexthop_group_cmd *nhgc)
 220 {
 221 }
 222
 223 void pbr_nhgroup_add_nexthop_cb(const struct nexthop_group_cmd *nhgc,
 224                                 const struct nexthop *nhop)
 225 {
 226         char debugstr[256];
 227         struct pbr_nexthop_group_cache pnhgc_find = {};
 228         struct pbr_nexthop_group_cache *pnhgc;
 229         struct pbr_nexthop_cache pnhc_find = {};
 230         struct pbr_nexthop_cache *pnhc;
 231
 232         /* find pnhgc by name */
 233         strlcpy(pnhgc_find.name, nhgc->name, sizeof(pnhgc_find.name));
 234         pnhgc = hash_lookup(pbr_nhg_hash, &pnhgc_find);
 235
 236         if (!pnhgc) {
 237                 /* Check if configured table range is exhausted */
 238                 if (!pbr_nht_has_unallocated_table()) {
 239                         zlog_warn(
 240                                 "%s: Exhausted all table identifiers; cannot create nexthop-group cache for nexthop-group '%s'",
 241                                 __func__, nhgc->name);
 242                         return;
 243                 }
 244
 245                 /* No nhgc but range not exhausted? Then alloc it */
 246                 pnhgc = hash_get(pbr_nhg_hash, &pnhgc_find, pbr_nhgc_alloc);
 247         }
 248
 249         /* create & insert new pnhc into pnhgc->nhh */
 250         pnhc_find.nexthop = *nhop;
 251         pnhc = hash_get(pnhgc->nhh, &pnhc_find, pbr_nh_alloc);
 252
 253         /* set parent pnhgc */
 254         pnhc->parent = pnhgc;
 255
 256         if (DEBUG_MODE_CHECK(&pbr_dbg_nht, DEBUG_MODE_ALL)) {
 257                 nexthop2str(nhop, debugstr, sizeof(debugstr));
 258                 DEBUGD(&pbr_dbg_nht, "%s: Added %s to nexthop-group %s",
 259                        __func__, debugstr, nhgc->name);
 260         }
 261
 262         pbr_nht_install_nexthop_group(pnhgc, nhgc->nhg);
 263         pbr_map_check_nh_group_change(nhgc->name);
 264
 265         if (nhop->type == NEXTHOP_TYPE_IFINDEX
 266             || (nhop->type == NEXTHOP_TYPE_IPV6_IFINDEX
 267                 && IN6_IS_ADDR_LINKLOCAL(&nhop->gate.ipv6))) {
 268                 struct interface *ifp;
 269
 270                 ifp = if_lookup_by_index(nhop->ifindex, nhop->vrf_id);
 271                 if (ifp)
 272                         pbr_nht_nexthop_interface_update(ifp);
 273         }
 274 }
 275
 276 void pbr_nhgroup_del_nexthop_cb(const struct nexthop_group_cmd *nhgc,
 277                                 const struct nexthop *nhop)
 278 {
 279         char debugstr[256];
 280         struct pbr_nexthop_group_cache pnhgc_find = {};
 281         struct pbr_nexthop_group_cache *pnhgc;
 282         struct pbr_nexthop_cache pnhc_find = {};
 283         struct pbr_nexthop_cache *pnhc;
 284         enum nexthop_types_t nh_type = nhop->type;
 285
 286         /* find pnhgc by name */
 287         strlcpy(pnhgc_find.name, nhgc->name, sizeof(pnhgc_find.name));
 288         pnhgc = hash_lookup(pbr_nhg_hash, &pnhgc_find);
 289
 290         /*
 291          * Ignore deletions of nhg we did not / could not allocate nhgc for
 292          * Occurs when PBR table range is full but new nhg keep coming in
 293          */
 294         if (!pnhgc)
 295                 return;
 296
 297         /* delete pnhc from pnhgc->nhh */
 298         pnhc_find.nexthop = *nhop;
 299         pnhc = hash_release(pnhgc->nhh, &pnhc_find);
 300
 301         /* delete pnhc */
 302         pbr_nh_delete(&pnhc);
 303
 304         if (DEBUG_MODE_CHECK(&pbr_dbg_nht, DEBUG_MODE_ALL)) {
 305                 nexthop2str(nhop, debugstr, sizeof(debugstr));
 306                 DEBUGD(&pbr_dbg_nht, "%s: Removed %s from nexthop-group %s",
 307                        __func__, debugstr, nhgc->name);
 308         }
 309
 310         if (pnhgc->nhh->count)
 311                 pbr_nht_install_nexthop_group(pnhgc, nhgc->nhg);
 312         else
 313                 pbr_nht_uninstall_nexthop_group(pnhgc, nhgc->nhg, nh_type);
 314
 315         pbr_map_check_nh_group_change(nhgc->name);
 316 }
 317
 318 void pbr_nhgroup_delete_cb(const char *name)
 319 {
 320         DEBUGD(&pbr_dbg_nht, "%s: Removed nexthop-group %s", __func__, name);
 321
 322         /* delete group from all pbrms's */
 323         pbr_nht_delete_group(name);
 324
 325         pbr_map_check_nh_group_change(name);
 326 }
 327
 328 static void
 329 pbr_nht_find_nhg_from_table_update(struct pbr_nexthop_group_cache *pnhgc,
 330                                    uint32_t table_id, bool installed)
 331 {
 332         if (pnhgc->table_id == table_id) {
 333                 DEBUGD(&pbr_dbg_nht, "%s: %s: Table ID (%u) matches %s",
 334                        __func__, (installed ? "install" : "remove"), table_id,
 335                        pnhgc->name);
 336
 337                 pnhgc->installed = installed;
 338                 pnhgc->valid = installed;
 339                 pbr_map_schedule_policy_from_nhg(pnhgc->name, pnhgc->installed);
 340         }
 341 }
 342
 343 static void pbr_nht_find_nhg_from_table_install(struct hash_bucket *b,
 344                                                 void *data)
 345 {
 346         struct pbr_nexthop_group_cache *pnhgc =
 347                 (struct pbr_nexthop_group_cache *)b->data;
 348         uint32_t table_id = *(uint32_t *)data;
 349
 350         pbr_nht_find_nhg_from_table_update(pnhgc, table_id, true);
 351 }
 352
 353 void pbr_nht_route_installed_for_table(uint32_t table_id)
 354 {
 355         hash_iterate(pbr_nhg_hash, pbr_nht_find_nhg_from_table_install,
 356                      &table_id);
 357 }
 358
 359 static void pbr_nht_find_nhg_from_table_remove(struct hash_bucket *b,
 360                                                void *data)
 361 {
 362         struct pbr_nexthop_group_cache *pnhgc =
 363                 (struct pbr_nexthop_group_cache *)b->data;
 364         uint32_t table_id = *(uint32_t *)data;
 365
 366         pbr_nht_find_nhg_from_table_update(pnhgc, table_id, false);
 367 }
 368
 369 void pbr_nht_route_removed_for_table(uint32_t table_id)
 370 {
 371         hash_iterate(pbr_nhg_hash, pbr_nht_find_nhg_from_table_remove,
 372                      &table_id);
 373 }
 374
 375 /*
 376  * Loop through all nexthops in a nexthop group to check that they are all the
 377  * same. If they are not all the same, log this peculiarity.
 378  *
 379  * nhg
 380  *    The nexthop group to check
 381  *
 382  * Returns:
 383  *    - AFI of last nexthop in the group
 384  *    - AFI_MAX on error
 385  */
 386 static afi_t pbr_nht_which_afi(struct nexthop_group nhg,
 387                                enum nexthop_types_t nh_type)
 388 {
 389         struct nexthop *nexthop;
 390         afi_t install_afi = AFI_MAX;
 391         bool v6, v4, bh;
 392
 393         if (nh_type) {
 394                 switch (nh_type) {
 395                 case NEXTHOP_TYPE_IPV4:
 396                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 397                         return AFI_IP;
 398                 case NEXTHOP_TYPE_IPV6:
 399                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 400                         return AFI_IP6;
 401                 case NEXTHOP_TYPE_IFINDEX:
 402                 case NEXTHOP_TYPE_BLACKHOLE:
 403                         return AFI_MAX;
 404                 }
 405         }
 406
 407         v6 = v4 = bh = false;
 408
 409         for (ALL_NEXTHOPS(nhg, nexthop)) {
 410                 nh_type = nexthop->type;
 411
 412                 switch (nh_type) {
 413                 case NEXTHOP_TYPE_IFINDEX:
 414                         break;
 415                 case NEXTHOP_TYPE_IPV4:
 416                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 417                         v6 = true;
 418                         install_afi = AFI_IP;
 419                         break;
 420                 case NEXTHOP_TYPE_IPV6:
 421                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 422                         v4 = true;
 423                         install_afi = AFI_IP6;
 424                         break;
 425                 case NEXTHOP_TYPE_BLACKHOLE:
 426                         bh = true;
 427                         break;
 428                 }
 429         }
 430
 431         /* Interface and/or blackhole nexthops only. */
 432         if (!v4 && !v6)
 433                 install_afi = AFI_MAX;
 434
 435         if (!bh && v6 && v4)
 436                 DEBUGD(&pbr_dbg_nht,
 437                        "%s: Saw both V6 and V4 nexthops...using %s", __func__,
 438                        afi2str(install_afi));
 439         if (bh && (v6 || v4))
 440                 DEBUGD(&pbr_dbg_nht,
 441                        "%s: Saw blackhole nexthop(s) with %s%s%s nexthop(s), using AFI_MAX.",
 442                        __func__, v4 ? "v4" : "", (v4 && v6) ? " and " : "",
 443                        v6 ? "v6" : "");
 444
 445         return install_afi;
 446 }
 447
 448 static void pbr_nht_install_nexthop_group(struct pbr_nexthop_group_cache *pnhgc,
 449                                           struct nexthop_group nhg)
 450 {
 451         afi_t install_afi;
 452         enum nexthop_types_t nh_type = 0;
 453
 454         install_afi = pbr_nht_which_afi(nhg, nh_type);
 455
 456         route_add(pnhgc, nhg, install_afi);
 457 }
 458
 459 static void
 460 pbr_nht_uninstall_nexthop_group(struct pbr_nexthop_group_cache *pnhgc,
 461                                 struct nexthop_group nhg,
 462                                 enum nexthop_types_t nh_type)
 463 {
 464         afi_t install_afi;
 465
 466         install_afi = pbr_nht_which_afi(nhg, nh_type);
 467
 468         pnhgc->installed = false;
 469         pnhgc->valid = false;
 470         route_delete(pnhgc, install_afi);
 471 }
 472
 473 void pbr_nht_change_group(const char *name)
 474 {
 475         struct nexthop_group_cmd *nhgc;
 476         struct pbr_nexthop_group_cache *pnhgc;
 477         struct pbr_nexthop_group_cache find;
 478         struct nexthop *nhop;
 479
 480         nhgc = nhgc_find(name);
 481         if (!nhgc)
 482                 return;
 483
 484         memset(&find, 0, sizeof(find));
 485         snprintf(find.name, sizeof(find.name), "%s", name);
 486         pnhgc = hash_lookup(pbr_nhg_hash, &find);
 487
 488         if (!pnhgc) {
 489                 DEBUGD(&pbr_dbg_nht,
 490                        "%s: Could not find nexthop-group cache w/ name '%s'",
 491                        __func__, name);
 492                 return;
 493         }
 494
 495         for (ALL_NEXTHOPS(nhgc->nhg, nhop)) {
 496                 struct pbr_nexthop_cache lookup;
 497                 struct pbr_nexthop_cache *pnhc;
 498
 499                 lookup.nexthop = *nhop;
 500                 pnhc = hash_lookup(pnhgc->nhh, &lookup);
 501                 if (!pnhc) {
 502                         pnhc = hash_get(pnhgc->nhh, &lookup, pbr_nh_alloc);
 503                         pnhc->parent = pnhgc;
 504                 }
 505         }
 506         pbr_nht_install_nexthop_group(pnhgc, nhgc->nhg);
 507 }
 508
 509 char *pbr_nht_nexthop_make_name(char *name, size_t l,
 510                                 uint32_t seqno, char *buffer)
 511 {
 512         snprintf(buffer, l, "%s%u", name, seqno);
 513         return buffer;
 514 }
 515
 516 /* Set data derived from nhg in pbrms */
 517 void pbr_nht_set_seq_nhg_data(struct pbr_map_sequence *pbrms,
 518                               const struct nexthop_group_cmd *nhgc)
 519 {
 520         const struct nexthop_group *nhg;
 521
 522         if (!nhgc)
 523                 return;
 524
 525         nhg = &nhgc->nhg;
 526         if (!nhg->nexthop)
 527                 return;
 528
 529         switch (nhg->nexthop->type) {
 530         case NEXTHOP_TYPE_IPV6:
 531         case NEXTHOP_TYPE_IPV6_IFINDEX:
 532                 pbrms->family = AF_INET6;
 533                 break;
 534         case NEXTHOP_TYPE_IPV4:
 535         case NEXTHOP_TYPE_IPV4_IFINDEX:
 536                 pbrms->family = AF_INET;
 537         case NEXTHOP_TYPE_IFINDEX:
 538         case NEXTHOP_TYPE_BLACKHOLE:
 539                 break;
 540         }
 541 }
 542
 543 /* Configure a routemap sequence to use a given nexthop group */
 544 void pbr_nht_set_seq_nhg(struct pbr_map_sequence *pbrms, const char *name)
 545 {
 546         struct nexthop_group_cmd *nhgc;
 547
 548         if (!name)
 549                 return;
 550
 551         pbrms->nhgrp_name = XSTRDUP(MTYPE_TMP, name);
 552
 553         nhgc = nhgc_find(name);
 554         if (!nhgc)
 555                 return;
 556
 557         pbr_nht_set_seq_nhg_data(pbrms, nhgc);
 558 }
 559
 560 void pbr_nht_add_individual_nexthop(struct pbr_map_sequence *pbrms,
 561                                     const struct nexthop *nhop)
 562 {
 563         struct pbr_nexthop_group_cache *pnhgc;
 564         struct pbr_nexthop_group_cache find;
 565         struct pbr_nexthop_cache *pnhc;
 566         struct pbr_nexthop_cache lookup;
 567         struct nexthop *nh;
 568         char buf[PBR_NHC_NAMELEN];
 569
 570         pbrms->nhg = nexthop_group_new();
 571         pbrms->internal_nhg_name = XSTRDUP(
 572                 MTYPE_TMP,
 573                 pbr_nht_nexthop_make_name(pbrms->parent->name, PBR_NHC_NAMELEN,
 574                                           pbrms->seqno, buf));
 575
 576         nh = nexthop_new();
 577         memcpy(nh, nhop, sizeof(*nh));
 578
 579         nexthop_group_add_sorted(pbrms->nhg, nh);
 580
 581         memset(&find, 0, sizeof(find));
 582         pbr_nht_nexthop_make_name(pbrms->parent->name, PBR_NHC_NAMELEN,
 583                                   pbrms->seqno, find.name);
 584
 585         if (!pbr_nht_has_unallocated_table()) {
 586                 zlog_warn(
 587                         "%s: Exhausted all table identifiers; cannot create nexthop-group cache for nexthop-group '%s'",
 588                         __func__, find.name);
 589                 return;
 590         }
 591
 592         if (!pbrms->internal_nhg_name)
 593                 pbrms->internal_nhg_name = XSTRDUP(MTYPE_TMP, find.name);
 594
 595         pnhgc = hash_get(pbr_nhg_hash, &find, pbr_nhgc_alloc);
 596
 597         lookup.nexthop = *pbrms->nhg->nexthop;
 598         pnhc = hash_get(pnhgc->nhh, &lookup, pbr_nh_alloc);
 599         pnhc->parent = pnhgc;
 600         if (nhop->vrf_id != VRF_DEFAULT) {
 601                 struct vrf *vrf = vrf_lookup_by_id(nhop->vrf_id);
 602
 603                 if (vrf)
 604                         strlcpy(pnhc->vrf_name, vrf->name,
 605                                 sizeof(pnhc->vrf_name));
 606         }
 607
 608         if (nhop->ifindex != 0) {
 609                 struct interface *ifp =
 610                         if_lookup_by_index(nhop->ifindex, nhop->vrf_id);
 611
 612                 if (ifp)
 613                         strlcpy(pnhc->intf_name, ifp->name,
 614                                 sizeof(pnhc->intf_name));
 615         }
 616         pbr_nht_install_nexthop_group(pnhgc, *pbrms->nhg);
 617 }
 618
 619 static void pbr_nht_release_individual_nexthop(struct pbr_map_sequence *pbrms)
 620 {
 621         struct pbr_nexthop_group_cache *pnhgc;
 622         struct pbr_nexthop_group_cache find;
 623         struct pbr_nexthop_cache *pnhc;
 624         struct pbr_nexthop_cache lup;
 625         struct nexthop *nh;
 626         enum nexthop_types_t nh_type = 0;
 627
 628         memset(&find, 0, sizeof(find));
 629         snprintf(find.name, sizeof(find.name), "%s", pbrms->internal_nhg_name);
 630         pnhgc = hash_lookup(pbr_nhg_hash, &find);
 631
 632         nh = pbrms->nhg->nexthop;
 633         nh_type = nh->type;
 634         lup.nexthop = *nh;
 635         pnhc = hash_lookup(pnhgc->nhh, &lup);
 636         pnhc->parent = NULL;
 637         hash_release(pnhgc->nhh, pnhc);
 638         pbr_nh_delete(&pnhc);
 639         pbr_nht_uninstall_nexthop_group(pnhgc, *pbrms->nhg, nh_type);
 640
 641         hash_release(pbr_nhg_hash, pnhgc);
 642         pbr_nhgc_delete(pnhgc);
 643
 644         nexthop_group_delete(&pbrms->nhg);
 645         XFREE(MTYPE_TMP, pbrms->internal_nhg_name);
 646 }
 647
 648 void pbr_nht_delete_individual_nexthop(struct pbr_map_sequence *pbrms)
 649 {
 650         pbr_map_delete_nexthops(pbrms);
 651
 652         pbr_nht_release_individual_nexthop(pbrms);
 653 }
 654
 655 struct pbr_nexthop_group_cache *pbr_nht_add_group(const char *name)
 656 {
 657         struct nexthop *nhop;
 658         struct nexthop_group_cmd *nhgc;
 659         struct pbr_nexthop_group_cache *pnhgc;
 660         struct pbr_nexthop_group_cache lookup;
 661
 662         if (!pbr_nht_has_unallocated_table()) {
 663                 zlog_warn(
 664                         "%s: Exhausted all table identifiers; cannot create nexthop-group cache for nexthop-group '%s'",
 665                         __func__, name);
 666                 return NULL;
 667         }
 668
 669         nhgc = nhgc_find(name);
 670
 671         if (!nhgc) {
 672                 DEBUGD(&pbr_dbg_nht, "%s: Could not find nhgc with name: %s",
 673                        __func__, name);
 674                 return NULL;
 675         }
 676
 677         snprintf(lookup.name, sizeof(lookup.name), "%s", name);
 678         pnhgc = hash_get(pbr_nhg_hash, &lookup, pbr_nhgc_alloc);
 679         DEBUGD(&pbr_dbg_nht, "%s: Retrieved NHGC @ %p", __func__, pnhgc);
 680
 681         for (ALL_NEXTHOPS(nhgc->nhg, nhop)) {
 682                 struct pbr_nexthop_cache lookupc;
 683                 struct pbr_nexthop_cache *pnhc;
 684
 685                 lookupc.nexthop = *nhop;
 686                 pnhc = hash_lookup(pnhgc->nhh, &lookupc);
 687                 if (!pnhc) {
 688                         pnhc = hash_get(pnhgc->nhh, &lookupc, pbr_nh_alloc);
 689                         pnhc->parent = pnhgc;
 690                 }
 691         }
 692
 693         return pnhgc;
 694 }
 695
 696 void pbr_nht_delete_group(const char *name)
 697 {
 698         struct pbr_map_sequence *pbrms;
 699         struct listnode *snode;
 700         struct pbr_map *pbrm;
 701         struct pbr_nexthop_group_cache pnhgc_find;
 702         struct pbr_nexthop_group_cache *pnhgc;
 703
 704         RB_FOREACH (pbrm, pbr_map_entry_head, &pbr_maps) {
 705                 for (ALL_LIST_ELEMENTS_RO(pbrm->seqnumbers, snode, pbrms)) {
 706                         if (pbrms->nhgrp_name
 707                             && strmatch(pbrms->nhgrp_name, name)) {
 708                                 pbrms->reason |= PBR_MAP_INVALID_NO_NEXTHOPS;
 709                                 pbrms->nhg = NULL;
 710                                 pbrms->internal_nhg_name = NULL;
 711                                 pbrm->valid = false;
 712                         }
 713                 }
 714         }
 715
 716         strlcpy(pnhgc_find.name, name, sizeof(pnhgc_find.name));
 717         pnhgc = hash_release(pbr_nhg_hash, &pnhgc_find);
 718
 719         /*
 720          * Ignore deletions of nh we did not / could not allocate nhgc for
 721          * Occurs when PBR table range is full but new nhg keep coming in
 722          */
 723         if (!pnhgc)
 724                 return;
 725
 726         /* Remove and recalculate the next table id */
 727         hash_release(pbr_nhg_allocated_id_hash, pnhgc);
 728         pbr_nht_update_next_unallocated_table_id();
 729
 730         pbr_nhgc_delete(pnhgc);
 731 }
 732
 733 bool pbr_nht_nexthop_valid(struct nexthop_group *nhg)
 734 {
 735         DEBUGD(&pbr_dbg_nht, "%s: %p", __func__, nhg);
 736         return true;
 737 }
 738
 739 bool pbr_nht_nexthop_group_valid(const char *name)
 740 {
 741         struct pbr_nexthop_group_cache *pnhgc;
 742         struct pbr_nexthop_group_cache lookup;
 743
 744         DEBUGD(&pbr_dbg_nht, "%s: %s", __func__, name);
 745
 746         snprintf(lookup.name, sizeof(lookup.name), "%s", name);
 747         pnhgc = hash_get(pbr_nhg_hash, &lookup, NULL);
 748         if (!pnhgc)
 749                 return false;
 750         DEBUGD(&pbr_dbg_nht, "%s:    %d %d", __func__, pnhgc->valid,
 751                pnhgc->installed);
 752         if (pnhgc->valid && pnhgc->installed)
 753                 return true;
 754
 755         return false;
 756 }
 757
 758 struct pbr_nht_individual {
 759         struct zapi_route *nhr;
 760         struct interface *ifp;
 761         struct pbr_vrf *pbr_vrf;
 762         struct pbr_nexthop_cache *pnhc;
 763         vrf_id_t old_vrf_id;
 764
 765         bool valid;
 766
 767         bool nhr_matched;
 768 };
 769
 770 static bool
 771 pbr_nht_individual_nexthop_gw_update(struct pbr_nexthop_cache *pnhc,
 772                                      struct pbr_nht_individual *pnhi)
 773 {
 774         bool is_valid = pnhc->valid;
 775
 776         /*
 777          * If we have an interface down event, let's note that
 778          * it is happening and find all the nexthops that depend
 779          * on that interface.  As that if we have an interface
 780          * flapping fast enough it means that zebra might turn
 781          * those nexthop tracking events into a no-update
 782          * So let's search and do the right thing on the
 783          * interface event.
 784          */
 785         if (!pnhi->nhr) {
 786                 switch (pnhc->nexthop.type) {
 787                 case NEXTHOP_TYPE_BLACKHOLE:
 788                 case NEXTHOP_TYPE_IPV4:
 789                 case NEXTHOP_TYPE_IPV6:
 790                         goto done;
 791                 case NEXTHOP_TYPE_IFINDEX:
 792                 case NEXTHOP_TYPE_IPV4_IFINDEX:
 793                 case NEXTHOP_TYPE_IPV6_IFINDEX:
 794                         if (pnhc->nexthop.ifindex == pnhi->ifp->ifindex)
 795                                 is_valid = if_is_up(pnhi->ifp);
 796                         goto done;
 797                 }
 798
 799                 goto done;
 800         }
 801
 802         switch (pnhi->nhr->prefix.family) {
 803         case AF_INET:
 804                 if (pnhc->nexthop.gate.ipv4.s_addr
 805                     != pnhi->nhr->prefix.u.prefix4.s_addr)
 806                         goto done; /* Unrelated change */
 807                 break;
 808         case AF_INET6:
 809                 if (memcmp(&pnhc->nexthop.gate.ipv6,
 810                            &pnhi->nhr->prefix.u.prefix6, 16)
 811                     != 0)
 812                         goto done; /* Unrelated change */
 813                 break;
 814         }
 815
 816         pnhi->nhr_matched = true;
 817         if (!pnhi->nhr->nexthop_num) {
 818                 is_valid = false;
 819                 goto done;
 820         }
 821
 822         if (pnhc->nexthop.type == NEXTHOP_TYPE_IPV4_IFINDEX
 823             || pnhc->nexthop.type == NEXTHOP_TYPE_IPV6_IFINDEX) {
 824
 825                 /* GATEWAY_IFINDEX type shouldn't resolve to group */
 826                 if (pnhi->nhr->nexthop_num > 1) {
 827                         is_valid = false;
 828                         goto done;
 829                 }
 830
 831                 /* If whatever we resolved to wasn't on the interface we
 832                  * specified. (i.e. not a connected route), its invalid.
 833                  */
 834                 if (pnhi->nhr->nexthops[0].ifindex != pnhc->nexthop.ifindex) {
 835                         is_valid = false;
 836                         goto done;
 837                 }
 838         }
 839
 840         is_valid = true;
 841
 842 done:
 843         pnhc->valid = is_valid;
 844
 845         return pnhc->valid;
 846 }
 847
 848 static bool
 849 pbr_nht_individual_nexthop_interface_update(struct pbr_nexthop_cache *pnhc,
 850                                             struct pbr_nht_individual *pnhi)
 851 {
 852         bool is_valid = pnhc->valid;
 853
 854         if (!pnhi->ifp) /* It doesn't care about non-interface updates */
 855                 goto done;
 856
 857         if (pnhc->nexthop.ifindex
 858             != pnhi->ifp->ifindex) /* Un-related interface */
 859                 goto done;
 860
 861         pnhi->nhr_matched = true;
 862         is_valid = !!if_is_up(pnhi->ifp);
 863
 864 done:
 865         pnhc->valid = is_valid;
 866
 867         return pnhc->valid;
 868 }
 869
 870 /* Given this update either from interface or nexthop tracking, re-validate this
 871  * nexthop.
 872  *
 873  * If the update is un-related, the subroutines shoud just return their cached
 874  * valid state.
 875  */
 876 static void pbr_nht_individual_nexthop_update(struct pbr_nexthop_cache *pnhc,
 877                                               struct pbr_nht_individual *pnhi)
 878 {
 879         assert(pnhi->nhr || pnhi->ifp); /* Either nexthop or interface update */
 880
 881         switch (pnhc->nexthop.type) {
 882         case NEXTHOP_TYPE_IFINDEX:
 883                 pbr_nht_individual_nexthop_interface_update(pnhc, pnhi);
 884                 break;
 885         case NEXTHOP_TYPE_IPV6_IFINDEX:
 886                 if (IN6_IS_ADDR_LINKLOCAL(&pnhc->nexthop.gate.ipv6)) {
 887                         pbr_nht_individual_nexthop_interface_update(pnhc, pnhi);
 888                         break;
 889                 }
 890                 /* Intentional fall thru */
 891         case NEXTHOP_TYPE_IPV4_IFINDEX:
 892         case NEXTHOP_TYPE_IPV4:
 893         case NEXTHOP_TYPE_IPV6:
 894                 pbr_nht_individual_nexthop_gw_update(pnhc, pnhi);
 895                 break;
 896         case NEXTHOP_TYPE_BLACKHOLE:
 897                 pnhc->valid = true;
 898                 break;
 899         }
 900 }
 901
 902 static void pbr_nht_individual_nexthop_update_lookup(struct hash_bucket *b,
 903                                                      void *data)
 904 {
 905         struct pbr_nexthop_cache *pnhc = b->data;
 906         struct pbr_nht_individual *pnhi = data;
 907         bool old_valid;
 908
 909         old_valid = pnhc->valid;
 910
 911         pbr_nht_individual_nexthop_update(pnhc, pnhi);
 912
 913         DEBUGD(&pbr_dbg_nht, "    Found %pFX: old: %d new: %d",
 914                &pnhi->nhr->prefix, old_valid, pnhc->valid);
 915
 916         if (pnhc->valid)
 917                 pnhi->valid = true;
 918 }
 919
 920 static void pbr_nexthop_group_cache_iterate_to_group(struct hash_bucket *b,
 921                                                      void *data)
 922 {
 923         struct pbr_nexthop_cache *pnhc = b->data;
 924         struct nexthop_group *nhg = data;
 925         struct nexthop *nh = NULL;
 926
 927         copy_nexthops(&nh, &pnhc->nexthop, NULL);
 928
 929         _nexthop_add(&nhg->nexthop, nh);
 930 }
 931
 932 static void
 933 pbr_nexthop_group_cache_to_nexthop_group(struct nexthop_group *nhg,
 934                                          struct pbr_nexthop_group_cache *pnhgc)
 935 {
 936         hash_iterate(pnhgc->nhh, pbr_nexthop_group_cache_iterate_to_group, nhg);
 937 }
 938
 939 static void pbr_nht_nexthop_update_lookup(struct hash_bucket *b, void *data)
 940 {
 941         struct pbr_nexthop_group_cache *pnhgc = b->data;
 942         struct pbr_nht_individual pnhi = {};
 943         struct nexthop_group nhg = {};
 944         bool old_valid;
 945
 946         old_valid = pnhgc->valid;
 947
 948         pnhi.nhr = (struct zapi_route *)data;
 949         pnhi.valid = false;
 950         pnhi.nhr_matched = false;
 951         hash_iterate(pnhgc->nhh, pbr_nht_individual_nexthop_update_lookup,
 952                      &pnhi);
 953
 954         if (!pnhi.nhr_matched)
 955                 return;
 956
 957         /*
 958          * If any of the specified nexthops are valid we are valid
 959          */
 960         pnhgc->valid = !!pnhi.valid;
 961
 962         pbr_nexthop_group_cache_to_nexthop_group(&nhg, pnhgc);
 963
 964         if (pnhgc->valid)
 965                 pbr_nht_install_nexthop_group(pnhgc, nhg);
 966         else
 967                 pbr_nht_uninstall_nexthop_group(pnhgc, nhg, 0);
 968
 969         /* Don't need copied nexthops anymore */
 970         nexthops_free(nhg.nexthop);
 971
 972         if (old_valid != pnhgc->valid)
 973                 pbr_map_check_nh_group_change(pnhgc->name);
 974 }
 975
 976 void pbr_nht_nexthop_update(struct zapi_route *nhr)
 977 {
 978         hash_iterate(pbr_nhg_hash, pbr_nht_nexthop_update_lookup, nhr);
 979 }
 980
 981 struct nhrc_vrf_info {
 982         struct pbr_vrf *pbr_vrf;
 983         uint32_t old_vrf_id;
 984         struct nhrc *nhrc;
 985 };
 986
 987 static int pbr_nht_nhrc_vrf_change(struct hash_bucket *b, void *data)
 988 {
 989         struct nhrc *nhrc = b->data;
 990         struct nhrc_vrf_info *nhrcvi = data;
 991
 992         if (nhrc->nexthop.vrf_id == nhrcvi->old_vrf_id) {
 993                 nhrcvi->nhrc = nhrc;
 994                 return HASHWALK_ABORT;
 995         }
 996
 997         return HASHWALK_CONTINUE;
 998 }
 999
1000 static int pbr_nht_individual_nexthop_vrf_handle(struct hash_bucket *b,
1001                                                  void *data)
1002 {
1003         struct pbr_nexthop_cache *pnhc = b->data;
1004         struct pbr_nht_individual *pnhi = data;
1005
1006         if (pnhc->looked_at == true)
1007                 return HASHWALK_CONTINUE;
1008
1009         if (pnhc->nexthop.vrf_id == VRF_DEFAULT)
1010                 return HASHWALK_CONTINUE;
1011
1012         if (strncmp(pnhc->vrf_name, pbr_vrf_name(pnhi->pbr_vrf),
1013                     sizeof(pnhc->vrf_name))
1014             == 0) {
1015                 pnhi->pnhc = pnhc;
1016
1017                 if (pnhc->nexthop.vrf_id != pbr_vrf_id(pnhi->pbr_vrf)) {
1018                         struct nhrc_vrf_info nhrcvi;
1019
1020                         memset(&nhrcvi, 0, sizeof(nhrcvi));
1021                         nhrcvi.pbr_vrf = pnhi->pbr_vrf;
1022                         nhrcvi.old_vrf_id = pnhc->nexthop.vrf_id;
1023
1024                         pnhi->nhr_matched = true;
1025                         pnhi->old_vrf_id = pnhc->nexthop.vrf_id;
1026
1027                         do {
1028                                 nhrcvi.nhrc = NULL;
1029                                 hash_walk(pbr_nhrc_hash,
1030                                           pbr_nht_nhrc_vrf_change, &nhrcvi);
1031                                 if (nhrcvi.nhrc) {
1032                                         hash_release(pbr_nhrc_hash,
1033                                                      nhrcvi.nhrc);
1034                                         nhrcvi.nhrc->nexthop.vrf_id =
1035                                                 pbr_vrf_id(pnhi->pbr_vrf);
1036                                         (void)hash_get(pbr_nhrc_hash,
1037                                                        nhrcvi.nhrc,
1038                                                        hash_alloc_intern);
1039                                         pbr_send_rnh(&nhrcvi.nhrc->nexthop, true);
1040                                 }
1041                         } while (nhrcvi.nhrc);
1042                 }
1043
1044                 pnhc->looked_at = true;
1045                 return HASHWALK_ABORT;
1046         }
1047
1048         return HASHWALK_CONTINUE;
1049 }
1050
1051 static void pbr_nht_clear_looked_at(struct hash_bucket *b, void *data)
1052 {
1053         struct pbr_nexthop_cache *pnhc = b->data;
1054
1055         pnhc->looked_at = false;
1056 }
1057
1058 static void pbr_nht_nexthop_vrf_handle(struct hash_bucket *b, void *data)
1059 {
1060         struct pbr_nexthop_group_cache *pnhgc = b->data;
1061         struct pbr_vrf *pbr_vrf = data;
1062         struct pbr_nht_individual pnhi = {};
1063
1064         hash_iterate(pnhgc->nhh, pbr_nht_clear_looked_at, NULL);
1065         memset(&pnhi, 0, sizeof(pnhi));
1066         pnhi.pbr_vrf = pbr_vrf;
1067         do {
1068                 struct pbr_nexthop_cache *pnhc;
1069
1070                 pnhi.pnhc = NULL;
1071                 hash_walk(pnhgc->nhh, pbr_nht_individual_nexthop_vrf_handle,
1072                           &pnhi);
1073
1074                 if (!pnhi.pnhc)
1075                         continue;
1076
1077                 pnhc = pnhi.pnhc;
1078                 pnhc->nexthop.vrf_id = pnhi.old_vrf_id;
1079                 pnhi.pnhc = hash_release(pnhgc->nhh, pnhi.pnhc);
1080                 if (pnhi.pnhc) {
1081                         pnhi.pnhc->nexthop.vrf_id = pbr_vrf_id(pbr_vrf);
1082
1083                         (void)hash_get(pnhgc->nhh, pnhi.pnhc,
1084                                        hash_alloc_intern);
1085                 } else
1086                         pnhc->nexthop.vrf_id = pbr_vrf_id(pbr_vrf);
1087
1088                 pbr_map_check_vrf_nh_group_change(pnhgc->name, pbr_vrf,
1089                                                   pnhi.old_vrf_id);
1090         } while (pnhi.pnhc);
1091 }
1092
1093 void pbr_nht_vrf_update(struct pbr_vrf *pbr_vrf)
1094 {
1095         hash_iterate(pbr_nhg_hash, pbr_nht_nexthop_vrf_handle, pbr_vrf);
1096 }
1097
1098 static void pbr_nht_individual_nexthop_interface_handle(struct hash_bucket *b,
1099                                                         void *data)
1100 {
1101         struct pbr_nexthop_cache *pnhc = b->data;
1102         struct pbr_nht_individual *pnhi = data;
1103
1104         if (pnhc->nexthop.ifindex == 0)
1105                 return;
1106
1107         if ((strncmp(pnhc->intf_name, pnhi->ifp->name, sizeof(pnhc->intf_name))
1108              == 0)
1109             && pnhc->nexthop.ifindex != pnhi->ifp->ifindex)
1110                 pnhi->pnhc = pnhc;
1111 }
1112
1113 static void pbr_nht_nexthop_interface_handle(struct hash_bucket *b, void *data)
1114 {
1115         struct pbr_nexthop_group_cache *pnhgc = b->data;
1116         struct interface *ifp = data;
1117         struct pbr_nht_individual pnhi = {};
1118         struct nhrc *nhrc;
1119         uint32_t old_ifindex;
1120
1121         do {
1122                 memset(&pnhi, 0, sizeof(pnhi));
1123                 pnhi.ifp = ifp;
1124                 hash_iterate(pnhgc->nhh,
1125                              pbr_nht_individual_nexthop_interface_handle,
1126                              &pnhi);
1127
1128                 if (!pnhi.pnhc)
1129                         continue;
1130
1131                 pnhi.pnhc = hash_release(pnhgc->nhh, pnhi.pnhc);
1132                 old_ifindex = pnhi.pnhc->nexthop.ifindex;
1133
1134                 nhrc = hash_lookup(pbr_nhrc_hash, &pnhi.pnhc->nexthop);
1135                 if (nhrc) {
1136                         hash_release(pbr_nhrc_hash, nhrc);
1137                         nhrc->nexthop.ifindex = ifp->ifindex;
1138                         (void)hash_get(pbr_nhrc_hash, nhrc, hash_alloc_intern);
1139                 }
1140                 pnhi.pnhc->nexthop.ifindex = ifp->ifindex;
1141
1142                 (void)hash_get(pnhgc->nhh, pnhi.pnhc, hash_alloc_intern);
1143
1144                 pbr_map_check_interface_nh_group_change(pnhgc->name, ifp,
1145                                                         old_ifindex);
1146         } while (pnhi.pnhc);
1147 }
1148
1149 void pbr_nht_interface_update(struct interface *ifp)
1150 {
1151         hash_iterate(pbr_nhg_hash, pbr_nht_nexthop_interface_handle, ifp);
1152 }
1153
1154 static void
1155 pbr_nht_individual_nexthop_interface_update_lookup(struct hash_bucket *b,
1156                                                    void *data)
1157 {
1158         struct pbr_nexthop_cache *pnhc = b->data;
1159         struct pbr_nht_individual *pnhi = data;
1160         bool old_valid;
1161
1162         old_valid = pnhc->valid;
1163
1164         pbr_nht_individual_nexthop_update(pnhc, pnhi);
1165
1166         DEBUGD(&pbr_dbg_nht, "    Found %s: old: %d new: %d", pnhi->ifp->name,
1167                old_valid, pnhc->valid);
1168
1169         if (pnhc->valid)
1170                 pnhi->valid = true;
1171 }
1172
1173 static void pbr_nht_nexthop_interface_update_lookup(struct hash_bucket *b,
1174                                                     void *data)
1175 {
1176         struct pbr_nexthop_group_cache *pnhgc = b->data;
1177         struct pbr_nht_individual pnhi = {};
1178         struct nexthop_group nhg = {};
1179         bool old_valid;
1180
1181         old_valid = pnhgc->valid;
1182
1183         pnhi.ifp = data;
1184         pnhi.valid = false;
1185         hash_iterate(pnhgc->nhh,
1186                      pbr_nht_individual_nexthop_interface_update_lookup, &pnhi);
1187
1188         /*
1189          * If any of the specified nexthops are valid we are valid
1190          */
1191         pnhgc->valid = pnhi.valid;
1192
1193         pbr_nexthop_group_cache_to_nexthop_group(&nhg, pnhgc);
1194
1195         if (pnhgc->valid)
1196                 pbr_nht_install_nexthop_group(pnhgc, nhg);
1197         else
1198                 pbr_nht_uninstall_nexthop_group(pnhgc, nhg, 0);
1199
1200         nexthops_free(nhg.nexthop);
1201
1202         if (old_valid != pnhgc->valid)
1203                 pbr_map_check_nh_group_change(pnhgc->name);
1204 }
1205
1206 void pbr_nht_nexthop_interface_update(struct interface *ifp)
1207 {
1208         hash_iterate(pbr_nhg_hash, pbr_nht_nexthop_interface_update_lookup,
1209                      ifp);
1210 }
1211
1212 static bool pbr_nhg_allocated_id_hash_equal(const void *arg1, const void *arg2)
1213 {
1214         const struct pbr_nexthop_group_cache *left, *right;
1215
1216         left = (const struct pbr_nexthop_group_cache *)arg1;
1217         right = (const struct pbr_nexthop_group_cache *)arg2;
1218
1219         return left->table_id == right->table_id;
1220 }
1221
1222 static uint32_t pbr_nhg_allocated_id_hash_key(const void *arg)
1223 {
1224         const struct pbr_nexthop_group_cache *nhgc = arg;
1225
1226         /* table_id makes elements in this hash unique */
1227         return nhgc->table_id;
1228 }
1229
1230 static uint32_t pbr_nhg_hash_key(const void *arg)
1231 {
1232         const struct pbr_nexthop_group_cache *nhgc = arg;
1233
1234         return jhash(&nhgc->name, strlen(nhgc->name), 0x52c34a96);
1235 }
1236
1237 static bool pbr_nhg_hash_equal(const void *arg1, const void *arg2)
1238 {
1239         const struct pbr_nexthop_group_cache *nhgc1 =
1240                 (const struct pbr_nexthop_group_cache *)arg1;
1241         const struct pbr_nexthop_group_cache *nhgc2 =
1242                 (const struct pbr_nexthop_group_cache *)arg2;
1243
1244         return !strcmp(nhgc1->name, nhgc2->name);
1245 }
1246
1247 uint32_t pbr_nht_find_next_unallocated_table_id(void)
1248 {
1249         struct pbr_nexthop_group_cache iter;
1250
1251         /*
1252          * Find the smallest unallocated table id
1253          * This can be non-trivial considering nhg removals / shifting upper &
1254          * lower bounds, so start at the lowest in the range and continue until
1255          * an unallocated space is found
1256          */
1257         for (iter.table_id = pbr_nhg_low_table;
1258              iter.table_id < pbr_nhg_high_table; ++iter.table_id)
1259                 if (!hash_lookup(pbr_nhg_allocated_id_hash, &iter))
1260                         return iter.table_id;
1261
1262         /* Configured range is full, cannot install anywhere */
1263         return 0;
1264 }
1265
1266 bool pbr_nht_has_unallocated_table(void)
1267 {
1268         return !!pbr_next_unallocated_table_id;
1269 }
1270
1271 void pbr_nht_update_next_unallocated_table_id(void)
1272 {
1273         pbr_next_unallocated_table_id =
1274                 pbr_nht_find_next_unallocated_table_id();
1275 }
1276
1277 uint32_t pbr_nht_reserve_next_table_id(struct pbr_nexthop_group_cache *nhgc)
1278 {
1279         /* Nothing to reserve if all tables in range already used */
1280         if (!pbr_next_unallocated_table_id)
1281                 return 0;
1282
1283         /* Reserve this table id */
1284         nhgc->table_id = pbr_next_unallocated_table_id;
1285
1286         /* Mark table id as allocated in id-indexed hash */
1287         (void)hash_get(pbr_nhg_allocated_id_hash, nhgc, hash_alloc_intern);
1288
1289         /* Pre-compute the next unallocated table id */
1290         pbr_nht_update_next_unallocated_table_id();
1291
1292         /* Present caller with reserved table id */
1293         return nhgc->table_id;
1294 }
1295
1296 void pbr_nht_set_tableid_range(uint32_t low, uint32_t high)
1297 {
1298         pbr_nhg_low_table = low;
1299         pbr_nhg_high_table = high;
1300
1301         /* Re-compute next unallocated id within new range */
1302         pbr_nht_update_next_unallocated_table_id();
1303 }
1304
1305 void pbr_nht_write_table_range(struct vty *vty)
1306 {
1307         if (pbr_nhg_low_table != PBR_NHT_DEFAULT_LOW_TABLEID
1308             || pbr_nhg_high_table != PBR_NHT_DEFAULT_HIGH_TABLEID) {
1309                 vty_out(vty, "pbr table range %u %u\n", pbr_nhg_low_table,
1310                         pbr_nhg_high_table);
1311         }
1312 }
1313
1314 uint32_t pbr_nht_get_next_rule(uint32_t seqno)
1315 {
1316         return seqno + pbr_nhg_low_rule - 1;
1317 }
1318 void pbr_nht_set_rule_range(uint32_t low, uint32_t high)
1319 {
1320         pbr_nhg_low_rule = low;
1321         pbr_nhg_high_rule = high;
1322 }
1323
1324 void pbr_nht_write_rule_range(struct vty *vty)
1325 {
1326         if (pbr_nhg_low_rule != PBR_NHT_DEFAULT_LOW_RULE
1327             || pbr_nhg_high_rule != PBR_NHT_DEFAULT_HIGH_RULE) {
1328                 vty_out(vty, "pbr rule range %u %u\n", pbr_nhg_low_rule,
1329                         pbr_nhg_high_rule);
1330         }
1331 }
1332
1333 uint32_t pbr_nht_get_table(const char *name)
1334 {
1335         struct pbr_nexthop_group_cache find;
1336         struct pbr_nexthop_group_cache *pnhgc;
1337
1338         memset(&find, 0, sizeof(find));
1339         snprintf(find.name, sizeof(find.name), "%s", name);
1340         pnhgc = hash_lookup(pbr_nhg_hash, &find);
1341
1342         if (!pnhgc) {
1343                 DEBUGD(&pbr_dbg_nht,
1344                        "%s: Could not find nexthop-group cache w/ name '%s'",
1345                        __func__, name);
1346                 return 5000;
1347         }
1348
1349         return pnhgc->table_id;
1350 }
1351
1352 bool pbr_nht_get_installed(const char *name)
1353 {
1354         struct pbr_nexthop_group_cache find;
1355         struct pbr_nexthop_group_cache *pnhgc;
1356
1357         memset(&find, 0, sizeof(find));
1358         snprintf(find.name, sizeof(find.name), "%s", name);
1359
1360         pnhgc = hash_lookup(pbr_nhg_hash, &find);
1361
1362         if (!pnhgc)
1363                 return false;
1364
1365         return pnhgc->installed;
1366 }
1367
1368 static void pbr_nht_show_nhg_nexthops(struct hash_bucket *b, void *data)
1369 {
1370         struct pbr_nexthop_cache *pnhc = b->data;
1371         struct vty *vty = data;
1372
1373         vty_out(vty, "\tValid: %d ", pnhc->valid);
1374         nexthop_group_write_nexthop(vty, &pnhc->nexthop);
1375 }
1376
1377 static void pbr_nht_json_nhg_nexthops(struct hash_bucket *b, void *data)
1378 {
1379         struct pbr_nexthop_cache *pnhc = b->data;
1380         json_object *all_hops = data;
1381         json_object *this_hop;
1382
1383         this_hop = json_object_new_object();
1384         nexthop_group_json_nexthop(this_hop, &pnhc->nexthop);
1385         json_object_boolean_add(this_hop, "valid", pnhc->valid);
1386
1387         json_object_array_add(all_hops, this_hop);
1388 }
1389
1390 struct pbr_nht_show {
1391         struct vty *vty;
1392         json_object *json;
1393         const char *name;
1394 };
1395
1396 static void pbr_nht_show_nhg(struct hash_bucket *b, void *data)
1397 {
1398         struct pbr_nexthop_group_cache *pnhgc = b->data;
1399         struct pbr_nht_show *pns = data;
1400         struct vty *vty;
1401
1402         if (pns->name && strcmp(pns->name, pnhgc->name) != 0)
1403                 return;
1404
1405         vty = pns->vty;
1406         vty_out(vty, "Nexthop-Group: %s Table: %u Valid: %d Installed: %d\n",
1407                 pnhgc->name, pnhgc->table_id, pnhgc->valid, pnhgc->installed);
1408
1409         hash_iterate(pnhgc->nhh, pbr_nht_show_nhg_nexthops, vty);
1410 }
1411
1412 static void pbr_nht_json_nhg(struct hash_bucket *b, void *data)
1413 {
1414         struct pbr_nexthop_group_cache *pnhgc = b->data;
1415         struct pbr_nht_show *pns = data;
1416         json_object *j, *this_group, *group_hops;
1417
1418         if (pns->name && strcmp(pns->name, pnhgc->name) != 0)
1419                 return;
1420
1421         j = pns->json;
1422         this_group = json_object_new_object();
1423
1424         if (!j || !this_group)
1425                 return;
1426
1427         json_object_int_add(this_group, "id", pnhgc->table_id);
1428         json_object_string_add(this_group, "name", pnhgc->name);
1429         json_object_boolean_add(this_group, "valid", pnhgc->valid);
1430         json_object_boolean_add(this_group, "installed", pnhgc->installed);
1431
1432         group_hops = json_object_new_array();
1433
1434         if (group_hops) {
1435                 hash_iterate(pnhgc->nhh, pbr_nht_json_nhg_nexthops, group_hops);
1436                 json_object_object_add(this_group, "nexthops", group_hops);
1437         }
1438
1439         json_object_array_add(j, this_group);
1440 }
1441
1442 void pbr_nht_show_nexthop_group(struct vty *vty, const char *name)
1443 {
1444         struct pbr_nht_show pns;
1445
1446         pns.vty = vty;
1447         pns.name = name;
1448
1449         hash_iterate(pbr_nhg_hash, pbr_nht_show_nhg, &pns);
1450 }
1451
1452 void pbr_nht_json_nexthop_group(json_object *j, const char *name)
1453 {
1454         struct pbr_nht_show pns;
1455
1456         pns.name = name;
1457         pns.json = j;
1458
1459         hash_iterate(pbr_nhg_hash, pbr_nht_json_nhg, &pns);
1460 }
1461
1462 void pbr_nht_init(void)
1463 {
1464         pbr_nhg_hash = hash_create_size(
1465                 16, pbr_nhg_hash_key, pbr_nhg_hash_equal, "PBR NHG Cache Hash");
1466         pbr_nhrc_hash =
1467                 hash_create_size(16, (unsigned int (*)(const void *))nexthop_hash,
1468                                  pbr_nhrc_hash_equal, "PBR NH Hash");
1469         pbr_nhg_allocated_id_hash = hash_create_size(
1470                 16, pbr_nhg_allocated_id_hash_key,
1471                 pbr_nhg_allocated_id_hash_equal, "PBR Allocated Table Hash");
1472
1473         pbr_nhg_low_table = PBR_NHT_DEFAULT_LOW_TABLEID;
1474         pbr_nhg_high_table = PBR_NHT_DEFAULT_HIGH_TABLEID;
1475         pbr_nhg_low_rule = PBR_NHT_DEFAULT_LOW_RULE;
1476         pbr_nhg_high_rule = PBR_NHT_DEFAULT_HIGH_RULE;
1477
1478         /* First unallocated table is lowest in range on init */
1479         pbr_next_unallocated_table_id = PBR_NHT_DEFAULT_LOW_TABLEID;
1480 }