lib/plist.c

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