pbrd/pbr_nht.c

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