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