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 bool
 340 prefix_list_entry_lookup_prefix(struct prefix_list *plist,
 341                                 struct prefix_list_entry *plist_entry)
 342 {
 343         struct prefix_list_entry *pentry = NULL;
 344
 345         for (pentry = plist->head; pentry; pentry = pentry->next) {
 346                 if (pentry == plist_entry)
 347                         continue;
 348                 if (prefix_same(&pentry->prefix, &plist_entry->prefix))
 349                         return true;
 350         }
 351
 352         return false;
 353 }
 354
 355 static void trie_walk_affected(size_t validbits, struct pltrie_table *table,
 356                                uint8_t byte, struct prefix_list_entry *object,
 357                                void (*fn)(struct prefix_list_entry *object,
 358                                           struct prefix_list_entry **updptr))
 359 {
 360         uint8_t mask;
 361         uint16_t bwalk;
 362
 363         if (validbits > PLC_BITS) {
 364                 fn(object, &table->entries[byte].final_chain);
 365                 return;
 366         }
 367
 368         mask = (1 << (8 - validbits)) - 1;
 369         for (bwalk = byte & ~mask; bwalk <= byte + mask; bwalk++) {
 370                 fn(object, &table->entries[bwalk].up_chain);
 371         }
 372 }
 373
 374 static void trie_uninstall_fn(struct prefix_list_entry *object,
 375                               struct prefix_list_entry **updptr)
 376 {
 377         for (; *updptr; updptr = &(*updptr)->next_best)
 378                 if (*updptr == object) {
 379                         *updptr = object->next_best;
 380                         break;
 381                 }
 382 }
 383
 384 static int trie_table_empty(struct pltrie_table *table)
 385 {
 386         size_t i;
 387         for (i = 0; i < PLC_LEN; i++)
 388                 if (table->entries[i].next_table || table->entries[i].up_chain)
 389                         return 0;
 390         return 1;
 391 }
 392
 393 static void prefix_list_trie_del(struct prefix_list *plist,
 394                                  struct prefix_list_entry *pentry)
 395 {
 396         size_t depth, maxdepth = plist->master->trie_depth;
 397         uint8_t *bytes = pentry->prefix.u.val;
 398         size_t validbits = pentry->prefix.prefixlen;
 399         struct pltrie_table *table, **tables[PLC_MAXLEVEL];
 400
 401         table = plist->trie;
 402         for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) {
 403                 uint8_t byte = bytes[depth];
 404                 assert(table->entries[byte].next_table);
 405
 406                 tables[depth + 1] = &table->entries[byte].next_table;
 407                 table = table->entries[byte].next_table;
 408
 409                 validbits -= PLC_BITS;
 410         }
 411
 412         trie_walk_affected(validbits, table, bytes[depth], pentry,
 413                            trie_uninstall_fn);
 414
 415         for (; depth > 0; depth--)
 416                 if (trie_table_empty(*tables[depth])) {
 417                         XFREE(MTYPE_PREFIX_LIST_TRIE, *tables[depth]);
 418                 }
 419 }
 420
 421
 422 void prefix_list_entry_delete(struct prefix_list *plist,
 423                               struct prefix_list_entry *pentry, int update_list)
 424 {
 425         bool duplicate = false;
 426
 427         if (plist == NULL || pentry == NULL)
 428                 return;
 429
 430         if (prefix_list_entry_lookup_prefix(plist, pentry))
 431                 duplicate = true;
 432
 433         prefix_list_trie_del(plist, pentry);
 434
 435         if (pentry->prev)
 436                 pentry->prev->next = pentry->next;
 437         else
 438                 plist->head = pentry->next;
 439         if (pentry->next)
 440                 pentry->next->prev = pentry->prev;
 441         else
 442                 plist->tail = pentry->prev;
 443
 444         if (!duplicate)
 445                 route_map_notify_pentry_dependencies(plist->name, pentry,
 446                                                      RMAP_EVENT_PLIST_DELETED);
 447
 448         prefix_list_entry_free(pentry);
 449
 450         plist->count--;
 451
 452         if (update_list) {
 453                 route_map_notify_dependencies(plist->name,
 454                                               RMAP_EVENT_PLIST_DELETED);
 455                 if (plist->master->delete_hook)
 456                         (*plist->master->delete_hook)(plist);
 457
 458                 if (plist->head == NULL && plist->tail == NULL
 459                     && plist->desc == NULL)
 460                         prefix_list_delete(plist);
 461                 else
 462                         plist->master->recent = plist;
 463         }
 464 }
 465
 466 static void trie_install_fn(struct prefix_list_entry *object,
 467                             struct prefix_list_entry **updptr)
 468 {
 469         while (*updptr) {
 470                 if (*updptr == object)
 471                         return;
 472                 if ((*updptr)->prefix.prefixlen < object->prefix.prefixlen)
 473                         break;
 474                 if ((*updptr)->prefix.prefixlen == object->prefix.prefixlen
 475                     && (*updptr)->seq > object->seq)
 476                         break;
 477                 updptr = &(*updptr)->next_best;
 478         }
 479
 480         if (!object->next_best)
 481                 object->next_best = *updptr;
 482         else
 483                 assert(object->next_best == *updptr || !*updptr);
 484
 485         *updptr = object;
 486 }
 487
 488 static void prefix_list_trie_add(struct prefix_list *plist,
 489                                  struct prefix_list_entry *pentry)
 490 {
 491         size_t depth = plist->master->trie_depth;
 492         uint8_t *bytes = pentry->prefix.u.val;
 493         size_t validbits = pentry->prefix.prefixlen;
 494         struct pltrie_table *table;
 495
 496         table = plist->trie;
 497         while (validbits > PLC_BITS && depth > 1) {
 498                 if (!table->entries[*bytes].next_table)
 499                         table->entries[*bytes].next_table =
 500                                 XCALLOC(MTYPE_PREFIX_LIST_TRIE,
 501                                         sizeof(struct pltrie_table));
 502                 table = table->entries[*bytes].next_table;
 503                 bytes++;
 504                 depth--;
 505                 validbits -= PLC_BITS;
 506         }
 507
 508         trie_walk_affected(validbits, table, *bytes, pentry, trie_install_fn);
 509 }
 510
 511 static void prefix_list_entry_add(struct prefix_list *plist,
 512                                   struct prefix_list_entry *pentry)
 513 {
 514         struct prefix_list_entry *replace;
 515         struct prefix_list_entry *point;
 516
 517         /* Automatic asignment of seq no. */
 518         if (pentry->seq == -1)
 519                 pentry->seq = prefix_new_seq_get(plist);
 520
 521         if (plist->tail && pentry->seq > plist->tail->seq)
 522                 point = NULL;
 523         else {
 524                 /* Is there any same seq prefix list entry? */
 525                 replace = prefix_seq_check(plist, pentry->seq);
 526                 if (replace)
 527                         prefix_list_entry_delete(plist, replace, 0);
 528
 529                 /* Check insert point. */
 530                 for (point = plist->head; point; point = point->next)
 531                         if (point->seq >= pentry->seq)
 532                                 break;
 533         }
 534
 535         /* In case of this is the first element of the list. */
 536         pentry->next = point;
 537
 538         if (point) {
 539                 if (point->prev)
 540                         point->prev->next = pentry;
 541                 else
 542                         plist->head = pentry;
 543
 544                 pentry->prev = point->prev;
 545                 point->prev = pentry;
 546         } else {
 547                 if (plist->tail)
 548                         plist->tail->next = pentry;
 549                 else
 550                         plist->head = pentry;
 551
 552                 pentry->prev = plist->tail;
 553                 plist->tail = pentry;
 554         }
 555
 556         prefix_list_trie_add(plist, pentry);
 557
 558         /* Increment count. */
 559         plist->count++;
 560
 561         route_map_notify_pentry_dependencies(plist->name, pentry,
 562                                              RMAP_EVENT_PLIST_ADDED);
 563
 564         /* Run hook function. */
 565         if (plist->master->add_hook)
 566                 (*plist->master->add_hook)(plist);
 567
 568         route_map_notify_dependencies(plist->name, RMAP_EVENT_PLIST_ADDED);
 569         plist->master->recent = plist;
 570 }
 571
 572 /**
 573  * Prefix list entry update start procedure:
 574  * Remove entry from previosly installed master list, tries and notify
 575  * observers.
 576  *
 577  * \param[in] ple prefix list entry.
 578  */
 579 void prefix_list_entry_update_start(struct prefix_list_entry *ple)
 580 {
 581         struct prefix_list *pl = ple->pl;
 582         bool duplicate = false;
 583
 584         /* Not installed, nothing to do. */
 585         if (!ple->installed)
 586                 return;
 587
 588         if (prefix_list_entry_lookup_prefix(pl, ple))
 589                 duplicate = true;
 590
 591         prefix_list_trie_del(pl, ple);
 592
 593         /* List manipulation: shameless copy from `prefix_list_entry_delete`. */
 594         if (ple->prev)
 595                 ple->prev->next = ple->next;
 596         else
 597                 pl->head = ple->next;
 598         if (ple->next)
 599                 ple->next->prev = ple->prev;
 600         else
 601                 pl->tail = ple->prev;
 602
 603         if (!duplicate)
 604                 route_map_notify_pentry_dependencies(pl->name, ple,
 605                                                      RMAP_EVENT_PLIST_DELETED);
 606         pl->count--;
 607
 608         route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_DELETED);
 609         if (pl->master->delete_hook)
 610                 (*pl->master->delete_hook)(pl);
 611
 612         if (pl->head || pl->tail || pl->desc)
 613                 pl->master->recent = pl;
 614
 615         ple->next_best = NULL;
 616         ple->installed = false;
 617 }
 618
 619 /**
 620  * Prefix list entry update finish procedure:
 621  * Add entry back master list, to the trie, notify observers and call master
 622  * hook.
 623  *
 624  * \param[in] ple prefix list entry.
 625  */
 626 void prefix_list_entry_update_finish(struct prefix_list_entry *ple)
 627 {
 628         struct prefix_list *pl = ple->pl;
 629         struct prefix_list_entry *point;
 630
 631         /* Already installed, nothing to do. */
 632         if (ple->installed)
 633                 return;
 634
 635         /*
 636          * Check if the entry is installable:
 637          * We can only install entry if at least the prefix is provided (IPv4
 638          * or IPv6).
 639          */
 640         if (ple->prefix.family != AF_INET && ple->prefix.family != AF_INET6)
 641                 return;
 642
 643         /* List manipulation: shameless copy from `prefix_list_entry_add`. */
 644         if (pl->tail && ple->seq > pl->tail->seq)
 645                 point = NULL;
 646         else {
 647                 /* Check insert point. */
 648                 for (point = pl->head; point; point = point->next)
 649                         if (point->seq >= ple->seq)
 650                                 break;
 651         }
 652
 653         /* In case of this is the first element of the list. */
 654         ple->next = point;
 655
 656         if (point) {
 657                 if (point->prev)
 658                         point->prev->next = ple;
 659                 else
 660                         pl->head = ple;
 661
 662                 ple->prev = point->prev;
 663                 point->prev = ple;
 664         } else {
 665                 if (pl->tail)
 666                         pl->tail->next = ple;
 667                 else
 668                         pl->head = ple;
 669
 670                 ple->prev = pl->tail;
 671                 pl->tail = ple;
 672         }
 673
 674         prefix_list_trie_add(pl, ple);
 675         pl->count++;
 676
 677         route_map_notify_pentry_dependencies(pl->name, ple,
 678                                              RMAP_EVENT_PLIST_ADDED);
 679
 680         /* Run hook function. */
 681         if (pl->master->add_hook)
 682                 (*pl->master->add_hook)(pl);
 683
 684         route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_ADDED);
 685         pl->master->recent = pl;
 686
 687         ple->installed = true;
 688 }
 689
 690 /**
 691  * Same as `prefix_list_entry_delete` but without `free()`ing the list if its
 692  * empty.
 693  *
 694  * \param[in] ple prefix list entry.
 695  */
 696 void prefix_list_entry_delete2(struct prefix_list_entry *ple)
 697 {
 698         /* Does the boiler plate list removal and entry removal notification. */
 699         prefix_list_entry_update_start(ple);
 700
 701         /* Effective `free()` memory. */
 702         prefix_list_entry_free(ple);
 703 }
 704
 705 /* Return string of prefix_list_type. */
 706 static const char *prefix_list_type_str(struct prefix_list_entry *pentry)
 707 {
 708         switch (pentry->type) {
 709         case PREFIX_PERMIT:
 710                 return "permit";
 711         case PREFIX_DENY:
 712                 return "deny";
 713         default:
 714                 return "";
 715         }
 716 }
 717
 718 static int prefix_list_entry_match(struct prefix_list_entry *pentry,
 719                                    const struct prefix *p, bool address_mode)
 720 {
 721         int ret;
 722
 723         if (pentry->prefix.family != p->family)
 724                 return 0;
 725
 726         ret = prefix_match(&pentry->prefix, p);
 727         if (!ret)
 728                 return 0;
 729
 730         if (address_mode)
 731                 return 1;
 732
 733         /* In case of le nor ge is specified, exact match is performed. */
 734         if (!pentry->le && !pentry->ge) {
 735                 if (pentry->prefix.prefixlen != p->prefixlen)
 736                         return 0;
 737         } else {
 738                 if (pentry->le)
 739                         if (p->prefixlen > pentry->le)
 740                                 return 0;
 741
 742                 if (pentry->ge)
 743                         if (p->prefixlen < pentry->ge)
 744                                 return 0;
 745         }
 746         return 1;
 747 }
 748
 749 enum prefix_list_type prefix_list_apply_ext(
 750         struct prefix_list *plist,
 751         const struct prefix_list_entry **which,
 752         union prefixconstptr object,
 753         bool address_mode)
 754 {
 755         struct prefix_list_entry *pentry, *pbest = NULL;
 756
 757         const struct prefix *p = object.p;
 758         const uint8_t *byte = p->u.val;
 759         size_t depth;
 760         size_t validbits = p->prefixlen;
 761         struct pltrie_table *table;
 762
 763         if (plist == NULL) {
 764                 if (which)
 765                         *which = NULL;
 766                 return PREFIX_DENY;
 767         }
 768
 769         if (plist->count == 0) {
 770                 if (which)
 771                         *which = NULL;
 772                 return PREFIX_PERMIT;
 773         }
 774
 775         depth = plist->master->trie_depth;
 776         table = plist->trie;
 777         while (1) {
 778                 for (pentry = table->entries[*byte].up_chain; pentry;
 779                      pentry = pentry->next_best) {
 780                         if (pbest && pbest->seq < pentry->seq)
 781                                 continue;
 782                         if (prefix_list_entry_match(pentry, p, address_mode))
 783                                 pbest = pentry;
 784                 }
 785
 786                 if (validbits <= PLC_BITS)
 787                         break;
 788                 validbits -= PLC_BITS;
 789
 790                 if (--depth) {
 791                         if (!table->entries[*byte].next_table)
 792                                 break;
 793
 794                         table = table->entries[*byte].next_table;
 795                         byte++;
 796                         continue;
 797                 }
 798
 799                 for (pentry = table->entries[*byte].final_chain; pentry;
 800                      pentry = pentry->next_best) {
 801                         if (pbest && pbest->seq < pentry->seq)
 802                                 continue;
 803                         if (prefix_list_entry_match(pentry, p, address_mode))
 804                                 pbest = pentry;
 805                 }
 806                 break;
 807         }
 808
 809         if (which) {
 810                 if (pbest)
 811                         *which = pbest;
 812                 else
 813                         *which = NULL;
 814         }
 815
 816         if (pbest == NULL)
 817                 return PREFIX_DENY;
 818
 819         pbest->hitcnt++;
 820         return pbest->type;
 821 }
 822
 823 static void __attribute__((unused)) prefix_list_print(struct prefix_list *plist)
 824 {
 825         struct prefix_list_entry *pentry;
 826
 827         if (plist == NULL)
 828                 return;
 829
 830         printf("ip prefix-list %s: %d entries\n", plist->name, plist->count);
 831
 832         for (pentry = plist->head; pentry; pentry = pentry->next) {
 833                 if (pentry->any)
 834                         printf("any %s\n", prefix_list_type_str(pentry));
 835                 else {
 836                         struct prefix *p;
 837
 838                         p = &pentry->prefix;
 839
 840                         printf("  seq %lld %s %pFX", (long long)pentry->seq,
 841                                prefix_list_type_str(pentry), p);
 842                         if (pentry->ge)
 843                                 printf(" ge %d", pentry->ge);
 844                         if (pentry->le)
 845                                 printf(" le %d", pentry->le);
 846                         printf("\n");
 847                 }
 848         }
 849 }
 850
 851 /* Return 1 when plist already include pentry policy. */
 852 static struct prefix_list_entry *
 853 prefix_entry_dup_check(struct prefix_list *plist, struct prefix_list_entry *new)
 854 {
 855         size_t depth, maxdepth = plist->master->trie_depth;
 856         uint8_t byte, *bytes = new->prefix.u.val;
 857         size_t validbits = new->prefix.prefixlen;
 858         struct pltrie_table *table;
 859         struct prefix_list_entry *pentry;
 860         int64_t seq = 0;
 861
 862         if (new->seq == -1)
 863                 seq = prefix_new_seq_get(plist);
 864         else
 865                 seq = new->seq;
 866
 867         table = plist->trie;
 868         for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) {
 869                 byte = bytes[depth];
 870                 if (!table->entries[byte].next_table)
 871                         return NULL;
 872
 873                 table = table->entries[byte].next_table;
 874                 validbits -= PLC_BITS;
 875         }
 876
 877         byte = bytes[depth];
 878         if (validbits > PLC_BITS)
 879                 pentry = table->entries[byte].final_chain;
 880         else
 881                 pentry = table->entries[byte].up_chain;
 882
 883         for (; pentry; pentry = pentry->next_best) {
 884                 if (prefix_same(&pentry->prefix, &new->prefix)
 885                     && pentry->type == new->type && pentry->le == new->le
 886                     && pentry->ge == new->ge && pentry->seq != seq)
 887                         return pentry;
 888         }
 889         return NULL;
 890 }
 891
 892 enum display_type {
 893         normal_display,
 894         summary_display,
 895         detail_display,
 896         sequential_display,
 897         longer_display,
 898         first_match_display
 899 };
 900
 901 static void vty_show_prefix_entry(struct vty *vty, json_object *json, afi_t afi,
 902                                   struct prefix_list *plist,
 903                                   struct prefix_master *master,
 904                                   enum display_type dtype, int seqnum)
 905 {
 906         struct prefix_list_entry *pentry;
 907         json_object *json_pl = NULL;
 908
 909         /* Print the name of the protocol */
 910         if (json) {
 911                 json_pl = json_object_new_object();
 912                 json_object_object_add(json, plist->name, json_pl);
 913         } else
 914                 vty_out(vty, "%s: ", frr_protoname);
 915
 916         if (dtype == normal_display) {
 917                 if (json) {
 918                         json_object_string_add(json_pl, "addressFamily",
 919                                                afi2str(afi));
 920                         json_object_int_add(json_pl, "entries", plist->count);
 921                         if (plist->desc)
 922                                 json_object_string_add(json_pl, "description",
 923                                                        plist->desc);
 924                 } else {
 925                         vty_out(vty, "ip%s prefix-list %s: %d entries\n",
 926                                 afi == AFI_IP ? "" : "v6", plist->name,
 927                                 plist->count);
 928                         if (plist->desc)
 929                                 vty_out(vty, "   Description: %s\n",
 930                                         plist->desc);
 931                 }
 932         } else if (dtype == summary_display || dtype == detail_display) {
 933                 if (json) {
 934                         json_object_string_add(json_pl, "addressFamily",
 935                                                afi2str(afi));
 936                         if (plist->desc)
 937                                 json_object_string_add(json_pl, "description",
 938                                                        plist->desc);
 939                         json_object_int_add(json_pl, "count", plist->count);
 940                         json_object_int_add(json_pl, "rangeEntries",
 941                                             plist->rangecount);
 942                         json_object_int_add(json_pl, "sequenceStart",
 943                                             plist->head ? plist->head->seq : 0);
 944                         json_object_int_add(json_pl, "sequenceEnd",
 945                                             plist->tail ? plist->tail->seq : 0);
 946                 } else {
 947                         vty_out(vty, "ip%s prefix-list %s:\n",
 948                                 afi == AFI_IP ? "" : "v6", plist->name);
 949
 950                         if (plist->desc)
 951                                 vty_out(vty, "   Description: %s\n",
 952                                         plist->desc);
 953
 954                         vty_out(vty,
 955                                 "   count: %d, range entries: %d, sequences: %" PRId64
 956                                 " - %" PRId64 "\n",
 957                                 plist->count, plist->rangecount,
 958                                 plist->head ? plist->head->seq : 0,
 959                                 plist->tail ? plist->tail->seq : 0);
 960                 }
 961         }
 962
 963         if (dtype != summary_display) {
 964                 json_object *json_entries = NULL;
 965
 966                 if (json) {
 967                         json_entries = json_object_new_array();
 968                         json_object_object_add(json_pl, "entries",
 969                                                json_entries);
 970                 }
 971
 972                 for (pentry = plist->head; pentry; pentry = pentry->next) {
 973                         if (dtype == sequential_display
 974                             && pentry->seq != seqnum)
 975                                 continue;
 976
 977                         if (json) {
 978                                 json_object *json_entry;
 979
 980                                 json_entry = json_object_new_object();
 981                                 json_object_array_add(json_entries, json_entry);
 982
 983                                 json_object_int_add(json_entry,
 984                                                     "sequenceNumber",
 985                                                     pentry->seq);
 986                                 json_object_string_add(
 987                                         json_entry, "type",
 988                                         prefix_list_type_str(pentry));
 989                                 json_object_string_addf(json_entry, "prefix",
 990                                                         "%pFX",
 991                                                         &pentry->prefix);
 992
 993                                 if (pentry->ge)
 994                                         json_object_int_add(
 995                                                 json_entry,
 996                                                 "minimumPrefixLength",
 997                                                 pentry->ge);
 998                                 if (pentry->le)
 999                                         json_object_int_add(
1000                                                 json_entry,
1001                                                 "maximumPrefixLength",
1002                                                 pentry->le);
1003
1004                                 if (dtype == detail_display
1005                                     || dtype == sequential_display) {
1006                                         json_object_int_add(json_entry,
1007                                                             "hitCount",
1008                                                             pentry->hitcnt);
1009                                         json_object_int_add(json_entry,
1010                                                             "referenceCount",
1011                                                             pentry->refcnt);
1012                                 }
1013                         } else {
1014                                 vty_out(vty, "   ");
1015
1016                                 vty_out(vty, "seq %" PRId64 " ", pentry->seq);
1017
1018                                 vty_out(vty, "%s ",
1019                                         prefix_list_type_str(pentry));
1020
1021                                 if (pentry->any)
1022                                         vty_out(vty, "any");
1023                                 else {
1024                                         struct prefix *p = &pentry->prefix;
1025
1026                                         vty_out(vty, "%pFX", p);
1027
1028                                         if (pentry->ge)
1029                                                 vty_out(vty, " ge %d",
1030                                                         pentry->ge);
1031                                         if (pentry->le)
1032                                                 vty_out(vty, " le %d",
1033                                                         pentry->le);
1034                                 }
1035
1036                                 if (dtype == detail_display
1037                                     || dtype == sequential_display)
1038                                         vty_out(vty,
1039                                                 " (hit count: %ld, refcount: %ld)",
1040                                                 pentry->hitcnt, pentry->refcnt);
1041
1042                                 vty_out(vty, "\n");
1043                         }
1044                 }
1045         }
1046 }
1047
1048 static int vty_show_prefix_list(struct vty *vty, afi_t afi, const char *name,
1049                                 const char *seq, enum display_type dtype,
1050                                 bool uj)
1051 {
1052         struct prefix_list *plist;
1053         struct prefix_master *master;
1054         int64_t seqnum = 0;
1055         json_object *json = NULL;
1056         json_object *json_proto = NULL;
1057
1058         master = prefix_master_get(afi, 0);
1059         if (master == NULL)
1060                 return CMD_WARNING;
1061
1062         if (uj) {
1063                 json = json_object_new_object();
1064                 json_proto = json_object_new_object();
1065                 json_object_object_add(json, frr_protoname, json_proto);
1066         }
1067
1068         if (seq)
1069                 seqnum = (int64_t)atol(seq);
1070
1071         if (name) {
1072                 plist = prefix_list_lookup(afi, name);
1073                 if (!plist) {
1074                         if (!uj)
1075                                 vty_out(vty,
1076                                         "%% Can't find specified prefix-list\n");
1077                         return CMD_WARNING;
1078                 }
1079                 vty_show_prefix_entry(vty, json_proto, afi, plist, master,
1080                                       dtype, seqnum);
1081         } else {
1082                 if (dtype == detail_display || dtype == summary_display) {
1083                         if (master->recent && !uj)
1084                                 vty_out(vty,
1085                                         "Prefix-list with the last deletion/insertion: %s\n",
1086                                         master->recent->name);
1087                 }
1088
1089                 frr_each (plist, &master->str, plist)
1090                         vty_show_prefix_entry(vty, json_proto, afi, plist,
1091                                               master, dtype, seqnum);
1092         }
1093
1094         return vty_json(vty, json);
1095 }
1096
1097 static int vty_show_prefix_list_prefix(struct vty *vty, afi_t afi,
1098                                        const char *name, const char *prefix,
1099                                        enum display_type type)
1100 {
1101         struct prefix_list *plist;
1102         struct prefix_list_entry *pentry;
1103         struct prefix p;
1104         int ret;
1105         int match;
1106
1107         plist = prefix_list_lookup(afi, name);
1108         if (!plist) {
1109                 vty_out(vty, "%% Can't find specified prefix-list\n");
1110                 return CMD_WARNING;
1111         }
1112
1113         ret = str2prefix(prefix, &p);
1114         if (ret <= 0) {
1115                 vty_out(vty, "%% prefix is malformed\n");
1116                 return CMD_WARNING;
1117         }
1118
1119         for (pentry = plist->head; pentry; pentry = pentry->next) {
1120                 match = 0;
1121
1122                 if (type == normal_display || type == first_match_display)
1123                         if (prefix_same(&p, &pentry->prefix))
1124                                 match = 1;
1125
1126                 if (type == longer_display) {
1127                         if ((p.family == pentry->prefix.family)
1128                             && (prefix_match(&p, &pentry->prefix)))
1129                                 match = 1;
1130                 }
1131
1132                 if (match) {
1133                         vty_out(vty, "   seq %" PRId64 " %s ", pentry->seq,
1134                                 prefix_list_type_str(pentry));
1135
1136                         if (pentry->any)
1137                                 vty_out(vty, "any");
1138                         else {
1139                                 struct prefix *pf = &pentry->prefix;
1140
1141                                 vty_out(vty, "%pFX", pf);
1142
1143                                 if (pentry->ge)
1144                                         vty_out(vty, " ge %d", pentry->ge);
1145                                 if (pentry->le)
1146                                         vty_out(vty, " le %d", pentry->le);
1147                         }
1148
1149                         if (type == normal_display
1150                             || type == first_match_display)
1151                                 vty_out(vty, " (hit count: %ld, refcount: %ld)",
1152                                         pentry->hitcnt, pentry->refcnt);
1153
1154                         vty_out(vty, "\n");
1155
1156                         if (type == first_match_display)
1157                                 return CMD_SUCCESS;
1158                 }
1159         }
1160         return CMD_SUCCESS;
1161 }
1162
1163 static int vty_clear_prefix_list(struct vty *vty, afi_t afi, const char *name,
1164                                  const char *prefix)
1165 {
1166         struct prefix_master *master;
1167         struct prefix_list *plist;
1168         struct prefix_list_entry *pentry;
1169         int ret;
1170         struct prefix p;
1171
1172         master = prefix_master_get(afi, 0);
1173         if (master == NULL)
1174                 return CMD_WARNING;
1175
1176         if (name == NULL && prefix == NULL) {
1177                 frr_each (plist, &master->str, plist)
1178                         for (pentry = plist->head; pentry;
1179                              pentry = pentry->next)
1180                                 pentry->hitcnt = 0;
1181         } else {
1182                 plist = prefix_list_lookup(afi, name);
1183                 if (!plist) {
1184                         vty_out(vty, "%% Can't find specified prefix-list\n");
1185                         return CMD_WARNING;
1186                 }
1187
1188                 if (prefix) {
1189                         ret = str2prefix(prefix, &p);
1190                         if (ret <= 0) {
1191                                 vty_out(vty, "%% prefix is malformed\n");
1192                                 return CMD_WARNING;
1193                         }
1194                 }
1195
1196                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1197                         if (prefix) {
1198                                 if (pentry->prefix.family == p.family
1199                                     && prefix_match(&pentry->prefix, &p))
1200                                         pentry->hitcnt = 0;
1201                         } else
1202                                 pentry->hitcnt = 0;
1203                 }
1204         }
1205         return CMD_SUCCESS;
1206 }
1207
1208 #include "lib/plist_clippy.c"
1209
1210 DEFPY (show_ip_prefix_list,
1211        show_ip_prefix_list_cmd,
1212        "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1213        SHOW_STR
1214        IP_STR
1215        PREFIX_LIST_STR
1216        "Name of a prefix list\n"
1217        "sequence number of an entry\n"
1218        "Sequence number\n"
1219        JSON_STR)
1220 {
1221         enum display_type dtype = normal_display;
1222         if (dseq)
1223                 dtype = sequential_display;
1224
1225         return vty_show_prefix_list(vty, AFI_IP, prefix_list, arg_str, dtype,
1226                                     !!uj);
1227 }
1228
1229 DEFPY (show_ip_prefix_list_prefix,
1230        show_ip_prefix_list_prefix_cmd,
1231        "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]",
1232        SHOW_STR
1233        IP_STR
1234        PREFIX_LIST_STR
1235        "Name of a prefix list\n"
1236        "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n"
1237        "Lookup longer prefix\n"
1238        "First matched prefix\n")
1239 {
1240         enum display_type dtype = normal_display;
1241         if (dl)
1242                 dtype = longer_display;
1243         else if (dfm)
1244                 dtype = first_match_display;
1245
1246         return vty_show_prefix_list_prefix(vty, AFI_IP, prefix_list, prefix_str,
1247                                            dtype);
1248 }
1249
1250 DEFPY (show_ip_prefix_list_summary,
1251        show_ip_prefix_list_summary_cmd,
1252        "show ip prefix-list summary [WORD$prefix_list] [json$uj]",
1253        SHOW_STR
1254        IP_STR
1255        PREFIX_LIST_STR
1256        "Summary of prefix lists\n"
1257        "Name of a prefix list\n"
1258        JSON_STR)
1259 {
1260         return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL,
1261                                     summary_display, !!uj);
1262 }
1263
1264 DEFPY (show_ip_prefix_list_detail,
1265        show_ip_prefix_list_detail_cmd,
1266        "show ip prefix-list detail [WORD$prefix_list] [json$uj]",
1267        SHOW_STR
1268        IP_STR
1269        PREFIX_LIST_STR
1270        "Detail of prefix lists\n"
1271        "Name of a prefix list\n"
1272        JSON_STR)
1273 {
1274         return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL,
1275                                     detail_display, !!uj);
1276 }
1277
1278 DEFPY (clear_ip_prefix_list,
1279        clear_ip_prefix_list_cmd,
1280        "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]",
1281        CLEAR_STR
1282        IP_STR
1283        PREFIX_LIST_STR
1284        "Name of a prefix list\n"
1285        "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n")
1286 {
1287         return vty_clear_prefix_list(vty, AFI_IP, prefix_list, prefix_str);
1288 }
1289
1290 DEFPY (show_ipv6_prefix_list,
1291        show_ipv6_prefix_list_cmd,
1292        "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1293        SHOW_STR
1294        IPV6_STR
1295        PREFIX_LIST_STR
1296        "Name of a prefix list\n"
1297        "sequence number of an entry\n"
1298        "Sequence number\n"
1299        JSON_STR)
1300 {
1301         enum display_type dtype = normal_display;
1302         if (dseq)
1303                 dtype = sequential_display;
1304
1305         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, arg_str, dtype,
1306                                     !!uj);
1307 }
1308
1309 DEFPY (show_ipv6_prefix_list_prefix,
1310        show_ipv6_prefix_list_prefix_cmd,
1311        "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]",
1312        SHOW_STR
1313        IPV6_STR
1314        PREFIX_LIST_STR
1315        "Name of a prefix list\n"
1316        "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n"
1317        "Lookup longer prefix\n"
1318        "First matched prefix\n")
1319 {
1320         enum display_type dtype = normal_display;
1321         if (dl)
1322                 dtype = longer_display;
1323         else if (dfm)
1324                 dtype = first_match_display;
1325
1326         return vty_show_prefix_list_prefix(vty, AFI_IP6, prefix_list,
1327                                            prefix_str, dtype);
1328 }
1329
1330 DEFPY (show_ipv6_prefix_list_summary,
1331        show_ipv6_prefix_list_summary_cmd,
1332        "show ipv6 prefix-list summary [WORD$prefix-list] [json$uj]",
1333        SHOW_STR
1334        IPV6_STR
1335        PREFIX_LIST_STR
1336        "Summary of prefix lists\n"
1337        "Name of a prefix list\n"
1338        JSON_STR)
1339 {
1340         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL,
1341                                     summary_display, !!uj);
1342 }
1343
1344 DEFPY (show_ipv6_prefix_list_detail,
1345        show_ipv6_prefix_list_detail_cmd,
1346        "show ipv6 prefix-list detail [WORD$prefix-list] [json$uj]",
1347        SHOW_STR
1348        IPV6_STR
1349        PREFIX_LIST_STR
1350        "Detail of prefix lists\n"
1351        "Name of a prefix list\n"
1352        JSON_STR)
1353 {
1354         return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL,
1355                                     detail_display, !!uj);
1356 }
1357
1358 DEFPY (clear_ipv6_prefix_list,
1359        clear_ipv6_prefix_list_cmd,
1360        "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]",
1361        CLEAR_STR
1362        IPV6_STR
1363        PREFIX_LIST_STR
1364        "Name of a prefix list\n"
1365        "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n")
1366 {
1367         return vty_clear_prefix_list(vty, AFI_IP6, prefix_list, prefix_str);
1368 }
1369
1370 DEFPY (debug_prefix_list_match,
1371        debug_prefix_list_match_cmd,
1372        "debug prefix-list WORD$prefix-list match <A.B.C.D/M|X:X::X:X/M>"
1373        " [address-mode$addr_mode]",
1374        DEBUG_STR
1375        "Prefix-list test access\n"
1376        "Name of a prefix list\n"
1377        "Test prefix for prefix list result\n"
1378        "Prefix to test in ip prefix-list\n"
1379        "Prefix to test in ipv6 prefix-list\n"
1380        "Use address matching mode (PIM RP)\n")
1381 {
1382         struct prefix_list *plist;
1383         const struct prefix_list_entry *entry = NULL;
1384         enum prefix_list_type ret;
1385
1386         plist = prefix_list_lookup(family2afi(match->family), prefix_list);
1387         if (!plist) {
1388                 vty_out(vty, "%% no prefix list named %s for AFI %s\n",
1389                         prefix_list, afi2str(family2afi(match->family)));
1390                 return CMD_WARNING;
1391         }
1392
1393         ret = prefix_list_apply_ext(plist, &entry, match, !!addr_mode);
1394
1395         vty_out(vty, "%s prefix list %s yields %s for %pFX, ",
1396                 afi2str(family2afi(match->family)), prefix_list,
1397                 ret == PREFIX_DENY ? "DENY" : "PERMIT", match);
1398
1399         if (!entry)
1400                 vty_out(vty, "no match found\n");
1401         else {
1402                 vty_out(vty, "matching entry #%"PRId64": %pFX", entry->seq,
1403                         &entry->prefix);
1404                 if (entry->ge)
1405                         vty_out(vty, " ge %d", entry->ge);
1406                 if (entry->le)
1407                         vty_out(vty, " le %d", entry->le);
1408                 vty_out(vty, "\n");
1409         }
1410
1411         /* allow using this in scripts for quick prefix-list member tests */
1412         return (ret == PREFIX_PERMIT) ? CMD_SUCCESS : CMD_WARNING;
1413 }
1414
1415 struct stream *prefix_bgp_orf_entry(struct stream *s, struct prefix_list *plist,
1416                                     uint8_t init_flag, uint8_t permit_flag,
1417                                     uint8_t deny_flag)
1418 {
1419         struct prefix_list_entry *pentry;
1420
1421         if (!plist)
1422                 return s;
1423
1424         for (pentry = plist->head; pentry; pentry = pentry->next) {
1425                 uint8_t flag = init_flag;
1426                 struct prefix *p = &pentry->prefix;
1427
1428                 flag |= (pentry->type == PREFIX_PERMIT ? permit_flag
1429                                                        : deny_flag);
1430                 stream_putc(s, flag);
1431                 stream_putl(s, (uint32_t)pentry->seq);
1432                 stream_putc(s, (uint8_t)pentry->ge);
1433                 stream_putc(s, (uint8_t)pentry->le);
1434                 stream_put_prefix(s, p);
1435         }
1436
1437         return s;
1438 }
1439
1440 int prefix_bgp_orf_set(char *name, afi_t afi, struct orf_prefix *orfp,
1441                        int permit, int set)
1442 {
1443         struct prefix_list *plist;
1444         struct prefix_list_entry *pentry;
1445
1446         /* ge and le value check */
1447         if (orfp->ge && orfp->ge < orfp->p.prefixlen)
1448                 return CMD_WARNING_CONFIG_FAILED;
1449         if (orfp->le && orfp->le < orfp->p.prefixlen)
1450                 return CMD_WARNING_CONFIG_FAILED;
1451         if (orfp->le && orfp->ge > orfp->le)
1452                 return CMD_WARNING_CONFIG_FAILED;
1453
1454         if (orfp->ge && orfp->le == (afi == AFI_IP ? 32 : 128))
1455                 orfp->le = 0;
1456
1457         plist = prefix_list_get(afi, 1, name);
1458         if (!plist)
1459                 return CMD_WARNING_CONFIG_FAILED;
1460
1461         apply_mask(&orfp->p);
1462
1463         if (set) {
1464                 pentry = prefix_list_entry_make(
1465                         &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY),
1466                         orfp->seq, orfp->le, orfp->ge, false);
1467
1468                 if (prefix_entry_dup_check(plist, pentry)) {
1469                         prefix_list_entry_free(pentry);
1470                         return CMD_WARNING_CONFIG_FAILED;
1471                 }
1472
1473                 prefix_list_entry_add(plist, pentry);
1474         } else {
1475                 pentry = prefix_list_entry_lookup(
1476                         plist, &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY),
1477                         orfp->seq, orfp->le, orfp->ge);
1478
1479                 if (!pentry)
1480                         return CMD_WARNING_CONFIG_FAILED;
1481
1482                 prefix_list_entry_delete(plist, pentry, 1);
1483         }
1484
1485         return CMD_SUCCESS;
1486 }
1487
1488 void prefix_bgp_orf_remove_all(afi_t afi, char *name)
1489 {
1490         struct prefix_list *plist;
1491
1492         plist = prefix_bgp_orf_lookup(afi, name);
1493         if (plist)
1494                 prefix_list_delete(plist);
1495 }
1496
1497 /* return prefix count */
1498 int prefix_bgp_show_prefix_list(struct vty *vty, afi_t afi, char *name,
1499                                 bool use_json)
1500 {
1501         struct prefix_list *plist;
1502         struct prefix_list_entry *pentry;
1503         json_object *json = NULL;
1504         json_object *json_prefix = NULL;
1505         json_object *json_list = NULL;
1506
1507         plist = prefix_bgp_orf_lookup(afi, name);
1508         if (!plist)
1509                 return 0;
1510
1511         if (!vty)
1512                 return plist->count;
1513
1514         if (use_json) {
1515                 json = json_object_new_object();
1516                 json_prefix = json_object_new_object();
1517                 json_list = json_object_new_object();
1518
1519                 json_object_int_add(json_prefix, "prefixListCounter",
1520                                     plist->count);
1521                 json_object_string_add(json_prefix, "prefixListName",
1522                                        plist->name);
1523
1524                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1525                         struct prefix *p = &pentry->prefix;
1526                         char buf_a[BUFSIZ];
1527
1528                         snprintf(buf_a, sizeof(buf_a), "%pFX", p);
1529
1530                         json_object_int_add(json_list, "seq", pentry->seq);
1531                         json_object_string_add(json_list, "seqPrefixListType",
1532                                                prefix_list_type_str(pentry));
1533
1534                         if (pentry->ge)
1535                                 json_object_int_add(json_list, "ge",
1536                                                     pentry->ge);
1537                         if (pentry->le)
1538                                 json_object_int_add(json_list, "le",
1539                                                     pentry->le);
1540
1541                         json_object_object_add(json_prefix, buf_a, json_list);
1542                 }
1543                 if (afi == AFI_IP)
1544                         json_object_object_add(json, "ipPrefixList",
1545                                                json_prefix);
1546                 else
1547                         json_object_object_add(json, "ipv6PrefixList",
1548                                                json_prefix);
1549
1550                 vty_json(vty, json);
1551         } else {
1552                 vty_out(vty, "ip%s prefix-list %s: %d entries\n",
1553                         afi == AFI_IP ? "" : "v6", plist->name, plist->count);
1554
1555                 for (pentry = plist->head; pentry; pentry = pentry->next) {
1556                         struct prefix *p = &pentry->prefix;
1557
1558                         vty_out(vty, "   seq %" PRId64 " %s %pFX", pentry->seq,
1559                                 prefix_list_type_str(pentry), p);
1560
1561                         if (pentry->ge)
1562                                 vty_out(vty, " ge %d", pentry->ge);
1563                         if (pentry->le)
1564                                 vty_out(vty, " le %d", pentry->le);
1565
1566                         vty_out(vty, "\n");
1567                 }
1568         }
1569         return plist->count;
1570 }
1571
1572 static void prefix_list_reset_afi(afi_t afi, int orf)
1573 {
1574         struct prefix_list *plist;
1575         struct prefix_master *master;
1576
1577         master = prefix_master_get(afi, orf);
1578         if (master == NULL)
1579                 return;
1580
1581         while ((plist = plist_first(&master->str))) {
1582                 prefix_list_delete(plist);
1583         }
1584
1585         master->recent = NULL;
1586 }
1587
1588 /* Prefix-list node. */
1589 static struct cmd_node prefix_node = {
1590         .name = "ipv4 prefix list",
1591         .node = PREFIX_NODE,
1592         .prompt = "",
1593 };
1594
1595 static void plist_autocomplete_afi(afi_t afi, vector comps,
1596                                    struct cmd_token *token)
1597 {
1598         struct prefix_list *plist;
1599         struct prefix_master *master;
1600
1601         master = prefix_master_get(afi, 0);
1602         if (master == NULL)
1603                 return;
1604
1605         frr_each (plist, &master->str, plist)
1606                 vector_set(comps, XSTRDUP(MTYPE_COMPLETION, plist->name));
1607 }
1608
1609 static void plist_autocomplete(vector comps, struct cmd_token *token)
1610 {
1611         plist_autocomplete_afi(AFI_IP, comps, token);
1612         plist_autocomplete_afi(AFI_IP6, comps, token);
1613 }
1614
1615 static const struct cmd_variable_handler plist_var_handlers[] = {
1616         {/* "prefix-list WORD" */
1617          .varname = "prefix_list",
1618          .completions = plist_autocomplete},
1619         {.tokenname = "PREFIXLIST_NAME",
1620          .completions = plist_autocomplete},
1621         {.completions = NULL}};
1622
1623
1624 static void prefix_list_init_ipv4(void)
1625 {
1626         install_node(&prefix_node);
1627
1628         install_element(VIEW_NODE, &show_ip_prefix_list_cmd);
1629         install_element(VIEW_NODE, &show_ip_prefix_list_prefix_cmd);
1630         install_element(VIEW_NODE, &show_ip_prefix_list_summary_cmd);
1631         install_element(VIEW_NODE, &show_ip_prefix_list_detail_cmd);
1632
1633         install_element(ENABLE_NODE, &clear_ip_prefix_list_cmd);
1634 }
1635
1636 /* Prefix-list node. */
1637 static struct cmd_node prefix_ipv6_node = {
1638         .name = "ipv6 prefix list",
1639         .node = PREFIX_IPV6_NODE,
1640         .prompt = "",
1641 };
1642
1643 static void prefix_list_init_ipv6(void)
1644 {
1645         install_node(&prefix_ipv6_node);
1646
1647         install_element(VIEW_NODE, &show_ipv6_prefix_list_cmd);
1648         install_element(VIEW_NODE, &show_ipv6_prefix_list_prefix_cmd);
1649         install_element(VIEW_NODE, &show_ipv6_prefix_list_summary_cmd);
1650         install_element(VIEW_NODE, &show_ipv6_prefix_list_detail_cmd);
1651         install_element(VIEW_NODE, &debug_prefix_list_match_cmd);
1652
1653         install_element(ENABLE_NODE, &clear_ipv6_prefix_list_cmd);
1654 }
1655
1656 void prefix_list_init(void)
1657 {
1658         plist_init(&prefix_master_ipv4.str);
1659         plist_init(&prefix_master_orf_v4.str);
1660         plist_init(&prefix_master_ipv6.str);
1661         plist_init(&prefix_master_orf_v6.str);
1662
1663         cmd_variable_handler_register(plist_var_handlers);
1664
1665         prefix_list_init_ipv4();
1666         prefix_list_init_ipv6();
1667 }
1668
1669 void prefix_list_reset(void)
1670 {
1671         prefix_list_reset_afi(AFI_IP, 0);
1672         prefix_list_reset_afi(AFI_IP6, 0);
1673         prefix_list_reset_afi(AFI_IP, 1);
1674         prefix_list_reset_afi(AFI_IP6, 1);
1675 }