lib/plist.c

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