lib/plist.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* Prefix list functions.
   3  * Copyright (C) 1999 Kunihiro Ishiguro
   4  */
   5
   6 #include <zebra.h>
   7
   8 #include "prefix.h"
   9 #include "command.h"
  10 #include "memory.h"
  11 #include "plist.h"
  12 #include "sockunion.h"
  13 #include "buffer.h"
  14 #include "log.h"
  15 #include "routemap.h"
  16 #include "lib/json.h"
  17 #include "libfrr.h"
  18
  19 #include <typesafe.h>
  20 #include "plist_int.h"
  21
  22 DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST, "Prefix List");
  23 DEFINE_MTYPE_STATIC(LIB, MPREFIX_LIST_STR, "Prefix List Str");
  24 DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST_ENTRY, "Prefix List Entry");
  25 DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST_TRIE, "Prefix List Trie Table");
  26
  27 /* not currently changeable, code assumes bytes further down */
  28 #define PLC_BITS        8
  29 #define PLC_LEN         (1 << PLC_BITS)
  30 #define PLC_MAXLEVELV4  2       /* /24 for IPv4 */
  31 #define PLC_MAXLEVELV6  4       /* /48 for IPv6 */
  32 #define PLC_MAXLEVEL    4       /* max(v4,v6) */
  33
  34 struct pltrie_entry {
  35         union {
  36                 struct pltrie_table *next_table;
  37                 struct prefix_list_entry *final_chain;
  38         };
  39
  40         struct prefix_list_entry *up_chain;
  41 };
  42
  43 struct pltrie_table {
  44         struct pltrie_entry entries[PLC_LEN];
  45 };
  46
  47 /* Master structure of prefix_list. */
  48 struct prefix_master {
  49         /* The latest update. */
  50         struct prefix_list *recent;
  51
  52         /* Hook function which is executed when new prefix_list is added. */
  53         void (*add_hook)(struct prefix_list *);
  54
  55         /* Hook function which is executed when prefix_list is deleted. */
  56         void (*delete_hook)(struct prefix_list *);
  57
  58         /* number of bytes that have a trie level */
  59         size_t trie_depth;
  60
  61         struct plist_head str;
  62 };
  63 static int prefix_list_compare_func(const struct prefix_list *a,
  64                                     const struct prefix_list *b);
  65 DECLARE_RBTREE_UNIQ(plist, struct prefix_list, plist_item,
  66                     prefix_list_compare_func);
  67
  68 /* Static structure of IPv4 prefix_list's master. */
  69 static struct prefix_master prefix_master_ipv4 = {
  70         NULL, NULL, NULL, PLC_MAXLEVELV4,
  71 };
  72
  73 /* Static structure of IPv6 prefix-list's master. */
  74 static struct prefix_master prefix_master_ipv6 = {
  75         NULL, NULL, NULL, PLC_MAXLEVELV6,
  76 };
  77
  78 /* Static structure of BGP ORF prefix_list's master. */
  79 static struct prefix_master prefix_master_orf_v4 = {
  80         NULL, NULL, NULL, PLC_MAXLEVELV4,
  81 };
  82
  83 /* Static structure of BGP ORF prefix_list's master. */
  84 static struct prefix_master prefix_master_orf_v6 = {
  85         NULL, NULL, NULL, PLC_MAXLEVELV6,
  86 };
  87
  88 static struct prefix_master *prefix_master_get(afi_t afi, int orf)
  89 {
  90         if (afi == AFI_IP)
  91                 return orf ? &prefix_master_orf_v4 : &prefix_master_ipv4;
  92         if (afi == AFI_IP6)
  93                 return orf ? &prefix_master_orf_v6 : &prefix_master_ipv6;
  94         return NULL;
  95 }
  96
  97 const char *prefix_list_name(struct prefix_list *plist)
  98 {
  99         return plist->name;
 100 }
 101
 102 afi_t prefix_list_afi(struct prefix_list *plist)
 103 {
 104         if (plist->master == &prefix_master_ipv4
 105             || plist->master == &prefix_master_orf_v4)
 106                 return AFI_IP;
 107         return AFI_IP6;
 108 }
 109
 110 static int prefix_list_compare_func(const struct prefix_list *a,
 111                                     const struct prefix_list *b)
 112 {
 113         return strcmp(a->name, b->name);
 114 }
 115
 116 /* Lookup prefix_list from list of prefix_list by name. */
 117 static struct prefix_list *prefix_list_lookup_do(afi_t afi, int orf,
 118                                                  const char *name)
 119 {
 120         struct prefix_list *plist, lookup;
 121         struct prefix_master *master;
 122
 123         if (name == NULL)
 124                 return NULL;
 125
 126         master = prefix_master_get(afi, orf);
 127         if (master == NULL)
 128                 return NULL;
 129
 130         lookup.name = XSTRDUP(MTYPE_TMP, name);
 131         plist = plist_find(&master->str, &lookup);
 132         XFREE(MTYPE_TMP, lookup.name);
 133         return plist;
 134 }
 135
 136 struct prefix_list *prefix_list_lookup(afi_t afi, const char *name)
 137 {
 138         return prefix_list_lookup_do(afi, 0, name);
 139 }
 140
 141 struct prefix_list *prefix_bgp_orf_lookup(afi_t afi, const char *name)
 142 {
 143         return prefix_list_lookup_do(afi, 1, name);
 144 }
 145
 146 static struct prefix_list *prefix_list_new(void)
 147 {
 148         struct prefix_list *new;
 149
 150         new = XCALLOC(MTYPE_PREFIX_LIST, sizeof(struct prefix_list));
 151         return new;
 152 }
 153
 154 static void prefix_list_free(struct prefix_list *plist)
 155 {
 156         XFREE(MTYPE_PREFIX_LIST, plist);
 157 }
 158
 159 struct prefix_list_entry *prefix_list_entry_new(void)
 160 {
 161         struct prefix_list_entry *new;
 162
 163         new = XCALLOC(MTYPE_PREFIX_LIST_ENTRY,
 164                       sizeof(struct prefix_list_entry));
 165         return new;
 166 }
 167
 168 void prefix_list_entry_free(struct prefix_list_entry *pentry)
 169 {
 170         XFREE(MTYPE_PREFIX_LIST_ENTRY, pentry);
 171 }
 172
 173 /* Insert new prefix list to list of prefix_list.  Each prefix_list
 174    is sorted by the name. */
 175 static struct prefix_list *prefix_list_insert(afi_t afi, int orf,
 176                                               const char *name)
 177 {
 178         struct prefix_list *plist;
 179         struct prefix_master *master;
 180
 181         master = prefix_master_get(afi, orf);
 182         if (master == NULL)
 183                 return NULL;
 184
 185         /* Allocate new prefix_list and copy given name. */
 186         plist = prefix_list_new();
 187         plist->name = XSTRDUP(MTYPE_MPREFIX_LIST_STR, name);
 188         plist->master = master;
 189         plist->trie =
 190                 XCALLOC(MTYPE_PREFIX_LIST_TRIE, sizeof(struct pltrie_table));
 191
 192         plist_add(&master->str, plist);
 193
 194         return plist;
 195 }
 196
 197 struct prefix_list *prefix_list_get(afi_t afi, int orf, const char *name)
 198 {
 199         struct prefix_list *plist;
 200
 201         plist = prefix_list_lookup_do(afi, orf, name);
 202
 203         if (plist == NULL)
 204                 plist = prefix_list_insert(afi, orf, name);
 205         return plist;
 206 }
 207
 208 static void prefix_list_trie_del(struct prefix_list *plist,
 209                                  struct prefix_list_entry *pentry);
 210
 211 /* Delete prefix-list from prefix_list_master and free it. */
 212 void prefix_list_delete(struct prefix_list *plist)
 213 {
 214         struct prefix_master *master;
 215         struct prefix_list_entry *pentry;
 216         struct prefix_list_entry *next;
 217
 218         /* If prefix-list contain prefix_list_entry free all of it. */
 219         for (pentry = plist->head; pentry; pentry = next) {
 220                 route_map_notify_pentry_dependencies(plist->name, pentry,
 221                                                      RMAP_EVENT_PLIST_DELETED);
 222                 next = pentry->next;
 223                 prefix_list_trie_del(plist, pentry);
 224                 prefix_list_entry_free(pentry);
 225                 plist->count--;
 226         }
 227
 228         master = plist->master;
 229
 230         plist_del(&master->str, plist);
 231
 232         XFREE(MTYPE_TMP, plist->desc);
 233
 234         /* Make sure master's recent changed prefix-list information is
 235            cleared. */
 236         master->recent = NULL;
 237
 238         route_map_notify_dependencies(plist->name, RMAP_EVENT_PLIST_DELETED);
 239
 240         if (master->delete_hook)
 241                 (*master->delete_hook)(plist);
 242
 243         XFREE(MTYPE_MPREFIX_LIST_STR, plist->name);
 244
 245         XFREE(MTYPE_PREFIX_LIST_TRIE, plist->trie);
 246
 247         prefix_list_free(plist);
 248 }
 249
 250 static struct prefix_list_entry *
 251 prefix_list_entry_make(struct prefix *prefix, enum prefix_list_type type,
 252                        int64_t seq, int le, int ge, bool any)
 253 {
 254         struct prefix_list_entry *pentry;
 255
 256         pentry = prefix_list_entry_new();
 257
 258         if (any)
 259                 pentry->any = true;
 260
 261         prefix_copy(&pentry->prefix, prefix);
 262         pentry->type = type;
 263         pentry->seq = seq;
 264         pentry->le = le;
 265         pentry->ge = ge;
 266
 267         return pentry;
 268 }
 269
 270 /* Add hook function. */
 271 void prefix_list_add_hook(void (*func)(struct prefix_list *plist))
 272 {
 273         prefix_master_ipv4.add_hook = func;
 274         prefix_master_ipv6.add_hook = func;
 275 }
 276
 277 /* Delete hook function. */
 278 void prefix_list_delete_hook(void (*func)(struct prefix_list *plist))
 279 {
 280         prefix_master_ipv4.delete_hook = func;
 281         prefix_master_ipv6.delete_hook = func;
 282 }
 283
 284 /* Calculate new sequential number. */
 285 int64_t prefix_new_seq_get(struct prefix_list *plist)
 286 {
 287         int64_t maxseq;
 288         int64_t newseq;
 289         struct prefix_list_entry *pentry;
 290
 291         maxseq = 0;
 292
 293         for (pentry = plist->head; pentry; pentry = pentry->next) {
 294                 if (maxseq < pentry->seq)
 295                         maxseq = pentry->seq;
 296         }
 297
 298         newseq = ((maxseq / 5) * 5) + 5;
 299
 300         return (newseq > UINT_MAX) ? UINT_MAX : newseq;
 301 }
 302
 303 /* Return prefix list entry which has same seq number. */
 304 static struct prefix_list_entry *prefix_seq_check(struct prefix_list *plist,
 305                                                   int64_t seq)
 306 {
 307         struct prefix_list_entry *pentry;
 308
 309         for (pentry = plist->head; pentry; pentry = pentry->next)
 310                 if (pentry->seq == seq)
 311                         return pentry;
 312         return NULL;
 313 }
 314
 315 struct prefix_list_entry *
 316 prefix_list_entry_lookup(struct prefix_list *plist, struct prefix *prefix,
 317                          enum prefix_list_type type, int64_t seq,
 318                          int le, int ge)
 319 {
 320         struct prefix_list_entry *pentry;
 321
 322         for (pentry = plist->head; pentry; pentry = pentry->next)
 323                 if (prefix_same(&pentry->prefix, prefix)
 324                     && pentry->type == type) {
 325                         if (seq >= 0 && pentry->seq != seq)
 326                                 continue;
 327
 328                         if (pentry->le != le)
 329                                 continue;
 330                         if (pentry->ge != ge)
 331                                 continue;
 332
 333                         return pentry;
 334                 }
 335
 336         return NULL;
 337 }
 338
 339 static void trie_walk_affected(size_t validbits, struct pltrie_table *table,
 340                                uint8_t byte, struct prefix_list_entry *object,
 341                                void (*fn)(struct prefix_list_entry *object,
 342                                           struct prefix_list_entry **updptr))
 343 {
 344         uint8_t mask;
 345         uint16_t bwalk;
 346
 347         if (validbits > PLC_BITS) {
 348                 fn(object, &table->entries[byte].final_chain);
 349                 return;
 350         }
 351
 352         mask = (1 << (8 - validbits)) - 1;
 353         for (bwalk = byte & ~mask; bwalk <= byte + mask; bwalk++) {
 354                 fn(object, &table->entries[bwalk].up_chain);
 355         }
 356 }
 357
 358 static void trie_uninstall_fn(struct prefix_list_entry *object,
 359                               struct prefix_list_entry **updptr)
 360 {
 361         for (; *updptr; updptr = &(*updptr)->next_best)
 362                 if (*updptr == object) {
 363                         *updptr = object->next_best;
 364                         break;
 365                 }
 366 }
 367
 368 static int trie_table_empty(struct pltrie_table *table)
 369 {
 370         size_t i;
 371         for (i = 0; i < PLC_LEN; i++)
 372                 if (table->entries[i].next_table || table->entries[i].up_chain)
 373                         return 0;
 374         return 1;
 375 }
 376
 377 static void prefix_list_trie_del(struct prefix_list *plist,
 378                                  struct prefix_list_entry *pentry)
 379 {
 380         size_t depth, maxdepth = plist->master->trie_depth;
 381         uint8_t *bytes = pentry->prefix.u.val;
 382         size_t validbits = pentry->prefix.prefixlen;
 383         struct pltrie_table *table, **tables[PLC_MAXLEVEL];
 384
 385         table = plist->trie;
 386         for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) {
 387                 uint8_t byte = bytes[depth];
 388                 assert(table->entries[byte].next_table);
 389
 390                 tables[depth + 1] = &table->entries[byte].next_table;
 391                 table = table->entries[byte].next_table;
 392
 393                 validbits -= PLC_BITS;
 394         }
 395
 396         trie_walk_affected(validbits, table, bytes[depth], pentry,
 397                            trie_uninstall_fn);
 398
 399         for (; depth > 0; depth--)
 400                 if (trie_table_empty(*tables[depth])) {
 401                         XFREE(MTYPE_PREFIX_LIST_TRIE, *tables[depth]);
 402                 }
 403 }
 404
 405
 406 void prefix_list_entry_delete(struct prefix_list *plist,
 407                               struct prefix_list_entry *pentry,
 408                               int update_list)
 409 {
 410         if (plist == NULL || pentry == NULL)
 411                 return;
 412
 413         prefix_list_trie_del(plist, pentry);
 414
 415         if (pentry->prev)
 416                 pentry->prev->next = pentry->next;
 417         else
 418                 plist->head = pentry->next;
 419         if (pentry->next)
 420                 pentry->next->prev = pentry->prev;
 421         else
 422                 plist->tail = pentry->prev;
 423
 424         route_map_notify_pentry_dependencies(plist->name, pentry,
 425                                              RMAP_EVENT_PLIST_DELETED);
 426         prefix_list_entry_free(pentry);
 427
 428         plist->count--;
 429
 430         if (update_list) {
 431                 route_map_notify_dependencies(plist->name,
 432                                               RMAP_EVENT_PLIST_DELETED);
 433                 if (plist->master->delete_hook)
 434                         (*plist->master->delete_hook)(plist);
 435
 436                 if (plist->head == NULL && plist->tail == NULL
 437                     && plist->desc == NULL)
 438                         prefix_list_delete(plist);
 439                 else
 440                         plist->master->recent = plist;
 441         }
 442 }
 443
 444 static void trie_install_fn(struct prefix_list_entry *object,
 445                             struct prefix_list_entry **updptr)
 446 {
 447         while (*updptr) {
 448                 if (*updptr == object)
 449                         return;
 450                 if ((*updptr)->prefix.prefixlen < object->prefix.prefixlen)
 451                         break;
 452                 if ((*updptr)->prefix.prefixlen == object->prefix.prefixlen
 453                     && (*updptr)->seq > object->seq)
 454                         break;
 455                 updptr = &(*updptr)->next_best;
 456         }
 457
 458         if (!object->next_best)
 459                 object->next_best = *updptr;
 460         else
 461                 assert(object->next_best == *updptr || !*updptr);
 462
 463         *updptr = object;
 464 }
 465
 466 static void prefix_list_trie_add(struct prefix_list *plist,
 467                                  struct prefix_list_entry *pentry)
 468 {
 469         size_t depth = plist->master->trie_depth;
 470         uint8_t *bytes = pentry->prefix.u.val;
 471         size_t validbits = pentry->prefix.prefixlen;
 472         struct pltrie_table *table;
 473
 474         table = plist->trie;
 475         while (validbits > PLC_BITS && depth > 1) {
 476                 if (!table->entries[*bytes].next_table)
 477                         table->entries[*bytes].next_table =
 478                                 XCALLOC(MTYPE_PREFIX_LIST_TRIE,
 479                                         sizeof(struct pltrie_table));
 480                 table = table->entries[*bytes].next_table;
 481                 bytes++;
 482                 depth--;
 483                 validbits -= PLC_BITS;
 484         }
 485
 486         trie_walk_affected(validbits, table, *bytes, pentry, trie_install_fn);
 487 }
 488
 489 static void prefix_list_entry_add(struct prefix_list *plist,
 490                                   struct prefix_list_entry *pentry)
 491 {
 492         struct prefix_list_entry *replace;
 493         struct prefix_list_entry *point;
 494
 495         /* Automatic asignment of seq no. */
 496         if (pentry->seq == -1)
 497                 pentry->seq = prefix_new_seq_get(plist);
 498
 499         if (plist->tail && pentry->seq > plist->tail->seq)
 500                 point = NULL;
 501         else {
 502                 /* Is there any same seq prefix list entry? */
 503                 replace = prefix_seq_check(plist, pentry->seq);
 504                 if (replace)
 505                         prefix_list_entry_delete(plist, replace, 0);
 506
 507                 /* Check insert point. */
 508                 for (point = plist->head; point; point = point->next)
 509                         if (point->seq >= pentry->seq)
 510                                 break;
 511         }
 512
 513         /* In case of this is the first element of the list. */
 514         pentry->next = point;
 515
 516         if (point) {
 517                 if (point->prev)
 518                         point->prev->next = pentry;
 519                 else
 520                         plist->head = pentry;
 521
 522                 pentry->prev = point->prev;
 523                 point->prev = pentry;
 524         } else {
 525                 if (plist->tail)
 526                         plist->tail->next = pentry;
 527                 else
 528                         plist->head = pentry;
 529
 530                 pentry->prev = plist->tail;
 531                 plist->tail = pentry;
 532         }
 533
 534         prefix_list_trie_add(plist, pentry);
 535
 536         /* Increment count. */
 537         plist->count++;
 538
 539         route_map_notify_pentry_dependencies(plist->name, pentry,
 540                                              RMAP_EVENT_PLIST_ADDED);
 541
 542         /* Run hook function. */
 543         if (plist->master->add_hook)
 544                 (*plist->master->add_hook)(plist);
 545
 546         route_map_notify_dependencies(plist->name, RMAP_EVENT_PLIST_ADDED);
 547         plist->master->recent = plist;
 548 }
 549
 550 /**
 551  * Prefix list entry update start procedure:
 552  * Remove entry from previosly installed master list, tries and notify
 553  * observers.
 554  *
 555  * \param[in] ple prefix list entry.
 556  */
 557 void prefix_list_entry_update_start(struct prefix_list_entry *ple)
 558 {
 559         struct prefix_list *pl = ple->pl;
 560
 561         /* Not installed, nothing to do. */
 562         if (!ple->installed)
 563                 return;
 564
 565         prefix_list_trie_del(pl, ple);
 566
 567         /* List manipulation: shameless copy from `prefix_list_entry_delete`. */
 568         if (ple->prev)
 569                 ple->prev->next = ple->next;
 570         else
 571                 pl->head = ple->next;
 572         if (ple->next)
 573                 ple->next->prev = ple->prev;
 574         else
 575                 pl->tail = ple->prev;
 576
 577         route_map_notify_pentry_dependencies(pl->name, ple,
 578                                              RMAP_EVENT_PLIST_DELETED);
 579         pl->count--;
 580
 581         route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_DELETED);
 582         if (pl->master->delete_hook)
 583                 (*pl->master->delete_hook)(pl);
 584
 585         if (pl->head || pl->tail || pl->desc)
 586                 pl->master->recent = pl;
 587
 588         ple->next_best = NULL;
 589         ple->installed = false;
 590 }
 591
 592 /**
 593  * Prefix list entry update finish procedure:
 594  * Add entry back master list, to the trie, notify observers and call master
 595  * hook.
 596  *
 597  * \param[in] ple prefix list entry.
 598  */
 599 void prefix_list_entry_update_finish(struct prefix_list_entry *ple)
 600 {
 601         struct prefix_list *pl = ple->pl;
 602         struct prefix_list_entry *point;
 603
 604         /* Already installed, nothing to do. */
 605         if (ple->installed)
 606                 return;
 607
 608         /*
 609          * Check if the entry is installable:
 610          * We can only install entry if at least the prefix is provided (IPv4
 611          * or IPv6).
 612          */
 613         if (ple->prefix.family != AF_INET && ple->prefix.family != AF_INET6)
 614                 return;
 615
 616         /* List manipulation: shameless copy from `prefix_list_entry_add`. */
 617         if (pl->tail && ple->seq > pl->tail->seq)
 618                 point = NULL;
 619         else {
 620                 /* Check insert point. */
 621                 for (point = pl->head; point; point = point->next)
 622                         if (point->seq >= ple->seq)
 623                                 break;
 624         }
 625
 626         /* In case of this is the first element of the list. */
 627         ple->next = point;
 628
 629         if (point) {
 630                 if (point->prev)
 631                         point->prev->next = ple;
 632                 else
 633                         pl->head = ple;
 634
 635                 ple->prev = point->prev;
 636                 point->prev = ple;
 637         } else {
 638                 if (pl->tail)
 639                         pl->tail->next = ple;
 640                 else
 641                         pl->head = ple;
 642
 643                 ple->prev = pl->tail;
 644                 pl->tail = ple;
 645         }
 646
 647         prefix_list_trie_add(pl, ple);
 648         pl->count++;
 649
 650         route_map_notify_pentry_dependencies(pl->name, ple,
 651                                              RMAP_EVENT_PLIST_ADDED);
 652
 653         /* Run hook function. */
 654         if (pl->master->add_hook)
 655                 (*pl->master->add_hook)(pl);
 656
 657         route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_ADDED);
 658         pl->master->recent = pl;
 659
 660         ple->installed = true;
 661 }
 662
 663 /**
 664  * Same as `prefix_list_entry_delete` but without `free()`ing the list if its
 665  * empty.
 666  *
 667  * \param[in] ple prefix list entry.
 668  */
 669 void prefix_list_entry_delete2(struct prefix_list_entry *ple)
 670 {
 671         /* Does the boiler plate list removal and entry removal notification. */
 672         prefix_list_entry_update_start(ple);
 673
 674         /* Effective `free()` memory. */
 675         prefix_list_entry_free(ple);
 676 }
 677
 678 /* Return string of prefix_list_type. */
 679 static const char *prefix_list_type_str(struct prefix_list_entry *pentry)
 680 {
 681         switch (pentry->type) {
 682         case PREFIX_PERMIT:
 683                 return "permit";
 684         case PREFIX_DENY:
 685                 return "deny";
 686         default:
 687                 return "";
 688         }
 689 }
 690
 691 static int prefix_list_entry_match(struct prefix_list_entry *pentry,
 692                                    const struct prefix *p, bool address_mode)
 693 {
 694         int ret;
 695
 696         if (pentry->prefix.family != p->family)
 697                 return 0;
 698
 699         ret = prefix_match(&pentry->prefix, p);
 700         if (!ret)
 701                 return 0;
 702
 703         if (address_mode)
 704                 return 1;
 705
 706         /* In case of le nor ge is specified, exact match is performed. */
 707         if (!pentry->le && !pentry->ge) {
 708                 if (pentry->prefix.prefixlen != p->prefixlen)
 709                         return 0;
 710         } else {
 711                 if (pentry->le)
 712                         if (p->prefixlen > pentry->le)
 713                                 return 0;
 714
 715                 if (pentry->ge)
 716                         if (p->prefixlen < pentry->ge)
 717                                 return 0;
 718         }
 719         return 1;
 720 }
 721
 722 enum prefix_list_type prefix_list_apply_ext(
 723         struct prefix_list *plist,
 724         const struct prefix_list_entry **which,
 725         union prefixconstptr object,
 726         bool address_mode)
 727 {
 728         struct prefix_list_entry *pentry, *pbest = NULL;
 729
 730         const struct prefix *p = object.p;
 731         const uint8_t *byte = p->u.val;
 732         size_t depth;
 733         size_t validbits = p->prefixlen;
 734         struct pltrie_table *table;
 735
 736         if (plist == NULL) {
 737                 if (which)
 738                         *which = NULL;
 739                 return PREFIX_DENY;
 740         }
 741
 742         if (plist->count == 0) {
 743                 if (which)
 744                         *which = NULL;
 745                 return PREFIX_PERMIT;
 746         }
 747
 748         depth = plist->master->trie_depth;
 749         table = plist->trie;
 750         while (1) {
 751                 for (pentry = table->entries[*byte].up_chain; pentry;
 752                      pentry = pentry->next_best) {
 753                         if (pbest && pbest->seq < pentry->seq)
 754                                 continue;
 755                         if (prefix_list_entry_match(pentry, p, address_mode))
 756                                 pbest = pentry;
 757                 }
 758
 759                 if (validbits <= PLC_BITS)
 760                         break;
 761                 validbits -= PLC_BITS;
 762
 763                 if (--depth) {
 764                         if (!table->entries[*byte].next_table)
 765                                 break;
 766
 767                         table = table->entries[*byte].next_table;
 768                         byte++;
 769                         continue;
 770                 }
 771
 772                 for (pentry = table->entries[*byte].final_chain; pentry;
 773                      pentry = pentry->next_best) {
 774                         if (pbest && pbest->seq < pentry->seq)
 775                                 continue;
 776                         if (prefix_list_entry_match(pentry, p, address_mode))
 777                                 pbest = pentry;
 778                 }
 779                 break;
 780         }
 781
 782         if (which) {
 783                 if (pbest)
 784                         *which = pbest;
 785                 else
 786                         *which = NULL;
 787         }
 788
 789         if (pbest == NULL)
 790                 return PREFIX_DENY;
 791
 792         pbest->hitcnt++;
 793         return pbest->type;
 794 }
 795
 796 static void __attribute__((unused)) prefix_list_print(struct prefix_list *plist)
 797 {
 798         struct prefix_list_entry *pentry;
 799
 800         if (plist == NULL)
 801                 return;
 802
 803         printf("ip prefix-list %s: %d entries\n", plist->name, plist->count);
 804
 805         for (pentry = plist->head; pentry; pentry = pentry->next) {
 806                 if (pentry->any)
 807                         printf("any %s\n", prefix_list_type_str(pentry));
 808                 else {
 809                         struct prefix *p;
 810
 811                         p = &pentry->prefix;
 812
 813                         printf("  seq %lld %s %pFX", (long long)pentry->seq,
 814                                prefix_list_type_str(pentry), p);
 815                         if (pentry->ge)
 816                                 printf(" ge %d", pentry->ge);
 817                         if (pentry->le)
 818                                 printf(" le %d", pentry->le);
 819                         printf("\n");
 820                 }
 821         }
 822 }
 823
 824 /* Return 1 when plist already include pentry policy. */
 825 static struct prefix_list_entry *
 826 prefix_entry_dup_check(struct prefix_list *plist, struct prefix_list_entry *new)
 827 {
 828         size_t depth, maxdepth = plist->master->trie_depth;
 829         uint8_t byte, *bytes = new->prefix.u.val;
 830         size_t validbits = new->prefix.prefixlen;
 831         struct pltrie_table *table;
 832         struct prefix_list_entry *pentry;
 833         int64_t seq = 0;
 834
 835         if (new->seq == -1)
 836                 seq = prefix_new_seq_get(plist);
 837         else
 838                 seq = new->seq;
 839
 840         table = plist->trie;
 841         for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) {
 842                 byte = bytes[depth];
 843                 if (!table->entries[byte].next_table)
 844                         return NULL;
 845
 846                 table = table->entries[byte].next_table;
 847                 validbits -= PLC_BITS;
 848         }
 849
 850         byte = bytes[depth];
 851         if (validbits > PLC_BITS)
 852                 pentry = table->entries[byte].final_chain;
 853         else
 854                 pentry = table->entries[byte].up_chain;
 855
 856         for (; pentry; pentry = pentry->next_best) {
 857                 if (prefix_same(&pentry->prefix, &new->prefix)
 858                     && pentry->type == new->type && pentry->le == new->le
 859                     && pentry->ge == new->ge && pentry->seq != seq)
 860                         return pentry;
 861         }
 862         return NULL;
 863 }
 864
 865 enum display_type {
 866         normal_display,
 867         summary_display,
 868         detail_display,
 869         sequential_display,
 870         longer_display,
 871         first_match_display
 872 };
 873
 874 static void vty_show_prefix_entry(struct vty *vty, json_object *json, afi_t afi,
 875                                   struct prefix_list *plist,
 876                                   struct prefix_master *master,
 877                                   enum display_type dtype, int seqnum)
 878 {
 879         struct prefix_list_entry *pentry;
 880         json_object *json_pl = NULL;
 881
 882         /* Print the name of the protocol */
 883         if (json) {
 884                 json_pl = json_object_new_object();
 885                 json_object_object_add(json, plist->name, json_pl);
 886         } else
 887                 vty_out(vty, "%s: ", frr_protoname);
 888
 889         if (dtype == normal_display) {
 890                 if (json) {
 891                         json_object_string_add(json_pl, "addressFamily",
 892                                                afi2str(afi));
 893                         json_object_int_add(json_pl, "entries", plist->count);
 894                         if (plist->desc)
 895                                 json_object_string_add(json_pl, "description",
 896                                                        plist->desc);
 897                 } else {
 898                         vty_out(vty, "ip%s prefix-list %s: %d entries\n",
 899                                 afi == AFI_IP ? "" : "v6", plist->name,
 900                                 plist->count);
 901                         if (plist->desc)
 902                                 vty_out(vty, "   Description: %s\n",
 903                                         plist->desc);
 904                 }
 905         } else if (dtype == summary_display || dtype == detail_display) {
 906                 if (json) {
 907                         json_object_string_add(json_pl, "addressFamily",
 908                                                afi2str(afi));
 909                         if (plist->desc)
 910                                 json_object_string_add(json_pl, "description",
 911                                                        plist->desc);
 912                         json_object_int_add(json_pl, "count", plist->count);
 913                         json_object_int_add(json_pl, "rangeEntries",
 914                                             plist->rangecount);
 915                         json_object_int_add(json_pl, "sequenceStart",
 916                                             plist->head ? plist->head->seq : 0);
 917                         json_object_int_add(json_pl, "sequenceEnd",
 918                                             plist->tail ? plist->tail->seq : 0);
 919                 } else {
 920                         vty_out(vty, "ip%s prefix-list %s:\n",
 921                                 afi == AFI_IP ? "" : "v6", plist->name);
 922
 923                         if (plist->desc)
 924                                 vty_out(vty, "   Description: %s\n",
 925                                         plist->desc);
 926
 927                         vty_out(vty,
 928                                 "   count: %d, range entries: %d, sequences: %" PRId64
 929                                 " - %" PRId64 "\n",
 930                                 plist->count, plist->rangecount,
 931                                 plist->head ? plist->head->seq : 0,
 932                                 plist->tail ? plist->tail->seq : 0);
 933                 }
 934         }
 935
 936         if (dtype != summary_display) {
 937                 json_object *json_entries = NULL;
 938
 939                 if (json) {
 940                         json_entries = json_object_new_array();
 941                         json_object_object_add(json_pl, "entries",
 942                                                json_entries);
 943                 }
 944
 945                 for (pentry = plist->head; pentry; pentry = pentry->next) {
 946                         if (dtype == sequential_display
 947                             && pentry->seq != seqnum)
 948                                 continue;
 949
 950                         if (json) {
 951                                 json_object *json_entry;
 952
 953                                 json_entry = json_object_new_object();
 954                                 json_object_array_add(json_entries, json_entry);
 955
 956                                 json_object_int_add(json_entry,
 957                                                     "sequenceNumber",
 958                                                     pentry->seq);
 959                                 json_object_string_add(
 960                                         json_entry, "type",
 961                                         prefix_list_type_str(pentry));
 962                                 json_object_string_addf(json_entry, "prefix",
 963                                                         "%pFX",
 964                                                         &pentry->prefix);
 965
 966                                 if (pentry->ge)
 967                                         json_object_int_add(
 968                                                 json_entry,
 969                                                 "minimumPrefixLength",
 970                                                 pentry->ge);
 971                                 if (pentry->le)
 972                                         json_object_int_add(
 973                                                 json_entry,
 974                                                 "maximumPrefixLength",
 975                                                 pentry->le);
 976
 977                                 if (dtype == detail_display
 978                                     || dtype == sequential_display) {
 979                                         json_object_int_add(json_entry,
 980                                                             "hitCount",
 981                                                             pentry->hitcnt);
 982                                         json_object_int_add(json_entry,
 983                                                             "referenceCount",
 984                                                             pentry->refcnt);
 985                                 }
 986                         } else {
 987                                 vty_out(vty, "   ");
 988
 989                                 vty_out(vty, "seq %" PRId64 " ", pentry->seq);
 990
 991                                 vty_out(vty, "%s ",
 992                                         prefix_list_type_str(pentry));
 993
 994                                 if (pentry->any)
 995                                         vty_out(vty, "any");
 996                                 else {
 997                                         struct prefix *p = &pentry->prefix;
 998
 999                                         vty_out(vty, "%pFX", p);
1000
1001                                         if (pentry->ge)
1002                                                 vty_out(vty, " ge %d",
1003                                                         pentry->ge);
1004                                         if (pentry->le)
1005                                                 vty_out(vty, " le %d",
1006                                                         pentry->le);
1007                                 }
1008
1009                                 if (dtype == detail_display
1010                                     || dtype == sequential_display)
1011                                         vty_out(vty,
1012                                                 " (hit count: %ld, refcount: %ld)",
1013                                                 pentry->hitcnt, pentry->refcnt);
1014
1015                                 vty_out(vty, "\n");
1016                         }
1017                 }
1018         }
1019 }
1020
1021 static int vty_show_prefix_list(struct vty *vty, afi_t afi, const char *name,
1022                                 const char *seq, enum display_type dtype,
1023                                 bool uj)
1024 {
1025         struct prefix_list *plist;
1026         struct prefix_master *master;
1027         int64_t seqnum = 0;
1028         json_object *json = NULL;
1029         json_object *json_proto = NULL;
1030
1031         master = prefix_master_get(afi, 0);
1032         if (master == NULL)
1033                 return CMD_WARNING;
1034
1035         if (uj) {
1036                 json = json_object_new_object();
1037                 json_proto = json_object_new_object();
1038                 json_object_object_add(json, frr_protoname, json_proto);
1039         }
1040
1041         if (seq)
1042                 seqnum = (int64_t)atol(seq);
1043
1044         if (name) {
1045                 plist = prefix_list_lookup(afi, name);
1046                 if (!plist) {
1047                         if (!uj)
1048                                 vty_out(vty,
1049                                         "%% Can't find specified prefix-list\n");
1050                         return CMD_WARNING;
1051                 }
1052                 vty_show_prefix_entry(vty, json_proto, afi, plist, master,
1053                                       dtype, seqnum);
1054         } else {
1055                 if (dtype == detail_display || dtype == summary_display) {
1056                         if (master->recent && !uj)
1057                                 vty_out(vty,
1058                                         "Prefix-list with the last deletion/insertion: %s\n",
1059                                         master->recent->name);
1060                 }
1061
1062                 frr_each (plist, &master->str, plist)
1063                         vty_show_prefix_entry(vty, json_proto, afi, plist,
1064                                               master, dtype, seqnum);
1065         }
1066
1067         return vty_json(vty, json);
1068 }
1069
1070 static int vty_show_prefix_list_prefix(struct vty *vty, afi_t afi,
1071                                        const char *name, const char *prefix,
1072                                        enum display_type type)
1073 {
1074         struct prefix_list *plist;
1075         struct prefix_list_entry *pentry;
1076         struct prefix p;
1077         int ret;
1078         int match;
1079
1080         plist = prefix_list_lookup(afi, name);
1081         if (!plist) {
1082                 vty_out(vty, "%% Can't find specified prefix-list\n");
1083                 return CMD_WARNING;
1084         }
1085
1086         ret = str2prefix(prefix, &p);
1087         if (ret <= 0) {
1088                 vty_out(vty, "%% prefix is malformed\n");
1089                 return CMD_WARNING;
1090         }
1091
1092         for (pentry = plist->head; pentry; pentry = pentry->next) {
1093                 match = 0;
1094
1095                 if (type == normal_display || type == first_match_display)
1096                         if (prefix_same(&p, &pentry->prefix))
1097                                 match = 1;
1098
1099                 if (type == longer_display) {
1100                         if ((p.family == pentry->prefix.family)
1101                             && (prefix_match(&p, &pentry->prefix)))
1102                                 match = 1;
1103                 }
1104
1105                 if (match) {
1106                         vty_out(vty, "   seq %" PRId64 " %s ", pentry->seq,
1107                                 prefix_list_type_str(pentry));
1108
1109                         if (pentry->any)
1110                                 vty_out(vty, "any");
1111                         else {
1112                                 struct prefix *pf = &pentry->prefix;
1113
1114                                 vty_out(vty, "%pFX", pf);
1115
1116                                 if (pentry->ge)
1117                                         vty_out(vty, " ge %d", pentry->ge);
1118                                 if (pentry->le)
1119                                         vty_out(vty, " le %d", pentry->le);
1120                         }
1121
1122                         if (type == normal_display
1123                             || type == first_match_display)
1124                                 vty_out(vty, " (hit count: %ld, refcount: %ld)",
1125                                         pentry->hitcnt, pentry->refcnt);
1126
1127                         vty_out(vty, "\n");
1128
1129                         if (type == first_match_display)
1130                                 return CMD_SUCCESS;
1131                 }
1132         }
1133         return CMD_SUCCESS;
1134 }
1135
1136 static int vty_clear_prefix_list(struct vty *vty, afi_t afi, const char *name,
1137                                  const char *prefix)
1138 {
1139         struct prefix_master *master;
1140         struct prefix_list *plist;
1141         struct prefix_list_entry *pentry;
1142         int ret;
1143         struct prefix p;
1144
1145         master = prefix_master_get(afi, 0);
1146         if (master == NULL)
1147                 return CMD_WARNING;
1148
1149         if (name == NULL && prefix == NULL) {
1150                 frr_each (plist, &master->str, plist)
1151                         for (pentry = plist->head; pentry;
1152                              pentry = pentry->next)
1153                                 pentry->hitcnt = 0;
1154         } else {
1155                 plist = prefix_list_lookup(afi, name);
1156                 if (!plist) {
1157                         vty_out(vty, "%% Can't find specified prefix-list\n");
1158                         return CMD_WARNING;
1159                 }
1160
1161                 if (prefix) {
1162                         ret = str2prefix(prefix, &p);
1163                         if (ret <= 0) {
1164                                 vty_out(vty, "%% prefix is malformed\n");
1165                                 return CMD_WARNING;
1166                         }
1167                 }
1168
1169                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1170                         if (prefix) {
1171                                 if (pentry->prefix.family == p.family
1172                                     && prefix_match(&pentry->prefix, &p))
1173                                         pentry->hitcnt = 0;
1174                         } else
1175                                 pentry->hitcnt = 0;
1176                 }
1177         }
1178         return CMD_SUCCESS;
1179 }
1180
1181 #include "lib/plist_clippy.c"
1182
1183 DEFPY (show_ip_prefix_list,
1184        show_ip_prefix_list_cmd,
1185        "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1186        SHOW_STR
1187        IP_STR
1188        PREFIX_LIST_STR
1189        "Name of a prefix list\n"
1190        "sequence number of an entry\n"
1191        "Sequence number\n"
1192        JSON_STR)
1193 {
1194         enum display_type dtype = normal_display;
1195         if (dseq)
1196                 dtype = sequential_display;
1197
1198         return vty_show_prefix_list(vty, AFI_IP, prefix_list, arg_str, dtype,
1199                                     !!uj);
1200 }
1201
1202 DEFPY (show_ip_prefix_list_prefix,
1203        show_ip_prefix_list_prefix_cmd,
1204        "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]",
1205        SHOW_STR
1206        IP_STR
1207        PREFIX_LIST_STR
1208        "Name of a prefix list\n"
1209        "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n"
1210        "Lookup longer prefix\n"
1211        "First matched prefix\n")
1212 {
1213         enum display_type dtype = normal_display;
1214         if (dl)
1215                 dtype = longer_display;
1216         else if (dfm)
1217                 dtype = first_match_display;
1218
1219         return vty_show_prefix_list_prefix(vty, AFI_IP, prefix_list, prefix_str,
1220                                            dtype);
1221 }
1222
1223 DEFPY (show_ip_prefix_list_summary,
1224        show_ip_prefix_list_summary_cmd,
1225        "show ip prefix-list summary [WORD$prefix_list] [json$uj]",
1226        SHOW_STR
1227        IP_STR
1228        PREFIX_LIST_STR
1229        "Summary of prefix lists\n"
1230        "Name of a prefix list\n"
1231        JSON_STR)
1232 {
1233         return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL,
1234                                     summary_display, !!uj);
1235 }
1236
1237 DEFPY (show_ip_prefix_list_detail,
1238        show_ip_prefix_list_detail_cmd,
1239        "show ip prefix-list detail [WORD$prefix_list] [json$uj]",
1240        SHOW_STR
1241        IP_STR
1242        PREFIX_LIST_STR
1243        "Detail of prefix lists\n"
1244        "Name of a prefix list\n"
1245        JSON_STR)
1246 {
1247         return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL,
1248                                     detail_display, !!uj);
1249 }
1250
1251 DEFPY (clear_ip_prefix_list,
1252        clear_ip_prefix_list_cmd,
1253        "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]",
1254        CLEAR_STR
1255        IP_STR
1256        PREFIX_LIST_STR
1257        "Name of a prefix list\n"
1258        "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n")
1259 {
1260         return vty_clear_prefix_list(vty, AFI_IP, prefix_list, prefix_str);
1261 }
1262
1263 DEFPY (show_ipv6_prefix_list,
1264        show_ipv6_prefix_list_cmd,
1265        "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1266        SHOW_STR
1267        IPV6_STR
1268        PREFIX_LIST_STR
1269        "Name of a prefix list\n"
1270        "sequence number of an entry\n"
1271        "Sequence number\n"
1272        JSON_STR)
1273 {
1274         enum display_type dtype = normal_display;
1275         if (dseq)
1276                 dtype = sequential_display;
1277
1278         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, arg_str, dtype,
1279                                     !!uj);
1280 }
1281
1282 DEFPY (show_ipv6_prefix_list_prefix,
1283        show_ipv6_prefix_list_prefix_cmd,
1284        "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]",
1285        SHOW_STR
1286        IPV6_STR
1287        PREFIX_LIST_STR
1288        "Name of a prefix list\n"
1289        "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n"
1290        "Lookup longer prefix\n"
1291        "First matched prefix\n")
1292 {
1293         enum display_type dtype = normal_display;
1294         if (dl)
1295                 dtype = longer_display;
1296         else if (dfm)
1297                 dtype = first_match_display;
1298
1299         return vty_show_prefix_list_prefix(vty, AFI_IP6, prefix_list,
1300                                            prefix_str, dtype);
1301 }
1302
1303 DEFPY (show_ipv6_prefix_list_summary,
1304        show_ipv6_prefix_list_summary_cmd,
1305        "show ipv6 prefix-list summary [WORD$prefix-list] [json$uj]",
1306        SHOW_STR
1307        IPV6_STR
1308        PREFIX_LIST_STR
1309        "Summary of prefix lists\n"
1310        "Name of a prefix list\n"
1311        JSON_STR)
1312 {
1313         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL,
1314                                     summary_display, !!uj);
1315 }
1316
1317 DEFPY (show_ipv6_prefix_list_detail,
1318        show_ipv6_prefix_list_detail_cmd,
1319        "show ipv6 prefix-list detail [WORD$prefix-list] [json$uj]",
1320        SHOW_STR
1321        IPV6_STR
1322        PREFIX_LIST_STR
1323        "Detail of prefix lists\n"
1324        "Name of a prefix list\n"
1325        JSON_STR)
1326 {
1327         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL,
1328                                     detail_display, !!uj);
1329 }
1330
1331 DEFPY (clear_ipv6_prefix_list,
1332        clear_ipv6_prefix_list_cmd,
1333        "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]",
1334        CLEAR_STR
1335        IPV6_STR
1336        PREFIX_LIST_STR
1337        "Name of a prefix list\n"
1338        "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n")
1339 {
1340         return vty_clear_prefix_list(vty, AFI_IP6, prefix_list, prefix_str);
1341 }
1342
1343 DEFPY (debug_prefix_list_match,
1344        debug_prefix_list_match_cmd,
1345        "debug prefix-list WORD$prefix-list match <A.B.C.D/M|X:X::X:X/M>"
1346        " [address-mode$addr_mode]",
1347        DEBUG_STR
1348        "Prefix-list test access\n"
1349        "Name of a prefix list\n"
1350        "Test prefix for prefix list result\n"
1351        "Prefix to test in ip prefix-list\n"
1352        "Prefix to test in ipv6 prefix-list\n"
1353        "Use address matching mode (PIM RP)\n")
1354 {
1355         struct prefix_list *plist;
1356         const struct prefix_list_entry *entry = NULL;
1357         enum prefix_list_type ret;
1358
1359         plist = prefix_list_lookup(family2afi(match->family), prefix_list);
1360         if (!plist) {
1361                 vty_out(vty, "%% no prefix list named %s for AFI %s\n",
1362                         prefix_list, afi2str(family2afi(match->family)));
1363                 return CMD_WARNING;
1364         }
1365
1366         ret = prefix_list_apply_ext(plist, &entry, match, !!addr_mode);
1367
1368         vty_out(vty, "%s prefix list %s yields %s for %pFX, ",
1369                 afi2str(family2afi(match->family)), prefix_list,
1370                 ret == PREFIX_DENY ? "DENY" : "PERMIT", match);
1371
1372         if (!entry)
1373                 vty_out(vty, "no match found\n");
1374         else {
1375                 vty_out(vty, "matching entry #%"PRId64": %pFX", entry->seq,
1376                         &entry->prefix);
1377                 if (entry->ge)
1378                         vty_out(vty, " ge %d", entry->ge);
1379                 if (entry->le)
1380                         vty_out(vty, " le %d", entry->le);
1381                 vty_out(vty, "\n");
1382         }
1383
1384         /* allow using this in scripts for quick prefix-list member tests */
1385         return (ret == PREFIX_PERMIT) ? CMD_SUCCESS : CMD_WARNING;
1386 }
1387
1388 struct stream *prefix_bgp_orf_entry(struct stream *s, struct prefix_list *plist,
1389                                     uint8_t init_flag, uint8_t permit_flag,
1390                                     uint8_t deny_flag)
1391 {
1392         struct prefix_list_entry *pentry;
1393
1394         if (!plist)
1395                 return s;
1396
1397         for (pentry = plist->head; pentry; pentry = pentry->next) {
1398                 uint8_t flag = init_flag;
1399                 struct prefix *p = &pentry->prefix;
1400
1401                 flag |= (pentry->type == PREFIX_PERMIT ? permit_flag
1402                                                        : deny_flag);
1403                 stream_putc(s, flag);
1404                 stream_putl(s, (uint32_t)pentry->seq);
1405                 stream_putc(s, (uint8_t)pentry->ge);
1406                 stream_putc(s, (uint8_t)pentry->le);
1407                 stream_put_prefix(s, p);
1408         }
1409
1410         return s;
1411 }
1412
1413 int prefix_bgp_orf_set(char *name, afi_t afi, struct orf_prefix *orfp,
1414                        int permit, int set)
1415 {
1416         struct prefix_list *plist;
1417         struct prefix_list_entry *pentry;
1418
1419         /* ge and le value check */
1420         if (orfp->ge && orfp->ge < orfp->p.prefixlen)
1421                 return CMD_WARNING_CONFIG_FAILED;
1422         if (orfp->le && orfp->le < orfp->p.prefixlen)
1423                 return CMD_WARNING_CONFIG_FAILED;
1424         if (orfp->le && orfp->ge > orfp->le)
1425                 return CMD_WARNING_CONFIG_FAILED;
1426
1427         if (orfp->ge && orfp->le == (afi == AFI_IP ? 32 : 128))
1428                 orfp->le = 0;
1429
1430         plist = prefix_list_get(afi, 1, name);
1431         if (!plist)
1432                 return CMD_WARNING_CONFIG_FAILED;
1433
1434         apply_mask(&orfp->p);
1435
1436         if (set) {
1437                 pentry = prefix_list_entry_make(
1438                         &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY),
1439                         orfp->seq, orfp->le, orfp->ge, false);
1440
1441                 if (prefix_entry_dup_check(plist, pentry)) {
1442                         prefix_list_entry_free(pentry);
1443                         return CMD_WARNING_CONFIG_FAILED;
1444                 }
1445
1446                 prefix_list_entry_add(plist, pentry);
1447         } else {
1448                 pentry = prefix_list_entry_lookup(
1449                         plist, &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY),
1450                         orfp->seq, orfp->le, orfp->ge);
1451
1452                 if (!pentry)
1453                         return CMD_WARNING_CONFIG_FAILED;
1454
1455                 prefix_list_entry_delete(plist, pentry, 1);
1456         }
1457
1458         return CMD_SUCCESS;
1459 }
1460
1461 void prefix_bgp_orf_remove_all(afi_t afi, char *name)
1462 {
1463         struct prefix_list *plist;
1464
1465         plist = prefix_bgp_orf_lookup(afi, name);
1466         if (plist)
1467                 prefix_list_delete(plist);
1468 }
1469
1470 /* return prefix count */
1471 int prefix_bgp_show_prefix_list(struct vty *vty, afi_t afi, char *name,
1472                                 bool use_json)
1473 {
1474         struct prefix_list *plist;
1475         struct prefix_list_entry *pentry;
1476         json_object *json = NULL;
1477         json_object *json_prefix = NULL;
1478         json_object *json_list = NULL;
1479
1480         plist = prefix_bgp_orf_lookup(afi, name);
1481         if (!plist)
1482                 return 0;
1483
1484         if (!vty)
1485                 return plist->count;
1486
1487         if (use_json) {
1488                 json = json_object_new_object();
1489                 json_prefix = json_object_new_object();
1490                 json_list = json_object_new_object();
1491
1492                 json_object_int_add(json_prefix, "prefixListCounter",
1493                                     plist->count);
1494                 json_object_string_add(json_prefix, "prefixListName",
1495                                        plist->name);
1496
1497                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1498                         struct prefix *p = &pentry->prefix;
1499                         char buf_a[BUFSIZ];
1500
1501                         snprintf(buf_a, sizeof(buf_a), "%pFX", p);
1502
1503                         json_object_int_add(json_list, "seq", pentry->seq);
1504                         json_object_string_add(json_list, "seqPrefixListType",
1505                                                prefix_list_type_str(pentry));
1506
1507                         if (pentry->ge)
1508                                 json_object_int_add(json_list, "ge",
1509                                                     pentry->ge);
1510                         if (pentry->le)
1511                                 json_object_int_add(json_list, "le",
1512                                                     pentry->le);
1513
1514                         json_object_object_add(json_prefix, buf_a, json_list);
1515                 }
1516                 if (afi == AFI_IP)
1517                         json_object_object_add(json, "ipPrefixList",
1518                                                json_prefix);
1519                 else
1520                         json_object_object_add(json, "ipv6PrefixList",
1521                                                json_prefix);
1522
1523                 vty_json(vty, json);
1524         } else {
1525                 vty_out(vty, "ip%s prefix-list %s: %d entries\n",
1526                         afi == AFI_IP ? "" : "v6", plist->name, plist->count);
1527
1528                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1529                         struct prefix *p = &pentry->prefix;
1530
1531                         vty_out(vty, "   seq %" PRId64 " %s %pFX", pentry->seq,
1532                                 prefix_list_type_str(pentry), p);
1533
1534                         if (pentry->ge)
1535                                 vty_out(vty, " ge %d", pentry->ge);
1536                         if (pentry->le)
1537                                 vty_out(vty, " le %d", pentry->le);
1538
1539                         vty_out(vty, "\n");
1540                 }
1541         }
1542         return plist->count;
1543 }
1544
1545 static void prefix_list_reset_afi(afi_t afi, int orf)
1546 {
1547         struct prefix_list *plist;
1548         struct prefix_master *master;
1549
1550         master = prefix_master_get(afi, orf);
1551         if (master == NULL)
1552                 return;
1553
1554         while ((plist = plist_first(&master->str))) {
1555                 prefix_list_delete(plist);
1556         }
1557
1558         master->recent = NULL;
1559 }
1560
1561 /* Prefix-list node. */
1562 static struct cmd_node prefix_node = {
1563         .name = "ipv4 prefix list",
1564         .node = PREFIX_NODE,
1565         .prompt = "",
1566 };
1567
1568 static void plist_autocomplete_afi(afi_t afi, vector comps,
1569                                    struct cmd_token *token)
1570 {
1571         struct prefix_list *plist;
1572         struct prefix_master *master;
1573
1574         master = prefix_master_get(afi, 0);
1575         if (master == NULL)
1576                 return;
1577
1578         frr_each (plist, &master->str, plist)
1579                 vector_set(comps, XSTRDUP(MTYPE_COMPLETION, plist->name));
1580 }
1581
1582 static void plist_autocomplete(vector comps, struct cmd_token *token)
1583 {
1584         plist_autocomplete_afi(AFI_IP, comps, token);
1585         plist_autocomplete_afi(AFI_IP6, comps, token);
1586 }
1587
1588 static const struct cmd_variable_handler plist_var_handlers[] = {
1589         {/* "prefix-list WORD" */
1590          .varname = "prefix_list",
1591          .completions = plist_autocomplete},
1592         {.tokenname = "PREFIXLIST_NAME",
1593          .completions = plist_autocomplete},
1594         {.completions = NULL}};
1595
1596
1597 static void prefix_list_init_ipv4(void)
1598 {
1599         install_node(&prefix_node);
1600
1601         install_element(VIEW_NODE, &show_ip_prefix_list_cmd);
1602         install_element(VIEW_NODE, &show_ip_prefix_list_prefix_cmd);
1603         install_element(VIEW_NODE, &show_ip_prefix_list_summary_cmd);
1604         install_element(VIEW_NODE, &show_ip_prefix_list_detail_cmd);
1605
1606         install_element(ENABLE_NODE, &clear_ip_prefix_list_cmd);
1607 }
1608
1609 /* Prefix-list node. */
1610 static struct cmd_node prefix_ipv6_node = {
1611         .name = "ipv6 prefix list",
1612         .node = PREFIX_IPV6_NODE,
1613         .prompt = "",
1614 };
1615
1616 static void prefix_list_init_ipv6(void)
1617 {
1618         install_node(&prefix_ipv6_node);
1619
1620         install_element(VIEW_NODE, &show_ipv6_prefix_list_cmd);
1621         install_element(VIEW_NODE, &show_ipv6_prefix_list_prefix_cmd);
1622         install_element(VIEW_NODE, &show_ipv6_prefix_list_summary_cmd);
1623         install_element(VIEW_NODE, &show_ipv6_prefix_list_detail_cmd);
1624         install_element(VIEW_NODE, &debug_prefix_list_match_cmd);
1625
1626         install_element(ENABLE_NODE, &clear_ipv6_prefix_list_cmd);
1627 }
1628
1629 void prefix_list_init(void)
1630 {
1631         plist_init(&prefix_master_ipv4.str);
1632         plist_init(&prefix_master_orf_v4.str);
1633         plist_init(&prefix_master_ipv6.str);
1634         plist_init(&prefix_master_orf_v6.str);
1635
1636         cmd_variable_handler_register(plist_var_handlers);
1637
1638         prefix_list_init_ipv4();
1639         prefix_list_init_ipv6();
1640 }
1641
1642 void prefix_list_reset(void)
1643 {
1644         prefix_list_reset_afi(AFI_IP, 0);
1645         prefix_list_reset_afi(AFI_IP6, 0);
1646         prefix_list_reset_afi(AFI_IP, 1);
1647         prefix_list_reset_afi(AFI_IP6, 1);
1648 }