diff options
Diffstat (limited to '')
| -rw-r--r-- | lib/plist.c | 1665 |
1 files changed, 1665 insertions, 0 deletions
diff --git a/lib/plist.c b/lib/plist.c new file mode 100644 index 0000000..ff2a59b --- /dev/null +++ b/lib/plist.c @@ -0,0 +1,1665 @@ +/* Prefix list functions. + * Copyright (C) 1999 Kunihiro Ishiguro + * + * This file is part of GNU Zebra. + * + * GNU Zebra is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published + * by the Free Software Foundation; either version 2, or (at your + * option) any later version. + * + * GNU Zebra is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <zebra.h> + +#include "prefix.h" +#include "command.h" +#include "memory.h" +#include "plist.h" +#include "sockunion.h" +#include "buffer.h" +#include "log.h" +#include "routemap.h" +#include "lib/json.h" +#include "libfrr.h" + +#include <typesafe.h> +#include "plist_int.h" + +DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST, "Prefix List"); +DEFINE_MTYPE_STATIC(LIB, MPREFIX_LIST_STR, "Prefix List Str"); +DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST_ENTRY, "Prefix List Entry"); +DEFINE_MTYPE_STATIC(LIB, PREFIX_LIST_TRIE, "Prefix List Trie Table"); + +/* not currently changeable, code assumes bytes further down */ +#define PLC_BITS 8 +#define PLC_LEN (1 << PLC_BITS) +#define PLC_MAXLEVELV4 2 /* /24 for IPv4 */ +#define PLC_MAXLEVELV6 4 /* /48 for IPv6 */ +#define PLC_MAXLEVEL 4 /* max(v4,v6) */ + +struct pltrie_entry { + union { + struct pltrie_table *next_table; + struct prefix_list_entry *final_chain; + }; + + struct prefix_list_entry *up_chain; +}; + +struct pltrie_table { + struct pltrie_entry entries[PLC_LEN]; +}; + +/* Master structure of prefix_list. */ +struct prefix_master { + /* The latest update. */ + struct prefix_list *recent; + + /* Hook function which is executed when new prefix_list is added. */ + void (*add_hook)(struct prefix_list *); + + /* Hook function which is executed when prefix_list is deleted. */ + void (*delete_hook)(struct prefix_list *); + + /* number of bytes that have a trie level */ + size_t trie_depth; + + struct plist_head str; +}; +static int prefix_list_compare_func(const struct prefix_list *a, + const struct prefix_list *b); +DECLARE_RBTREE_UNIQ(plist, struct prefix_list, plist_item, + prefix_list_compare_func); + +/* Static structure of IPv4 prefix_list's master. */ +static struct prefix_master prefix_master_ipv4 = { + NULL, NULL, NULL, PLC_MAXLEVELV4, +}; + +/* Static structure of IPv6 prefix-list's master. */ +static struct prefix_master prefix_master_ipv6 = { + NULL, NULL, NULL, PLC_MAXLEVELV6, +}; + +/* Static structure of BGP ORF prefix_list's master. */ +static struct prefix_master prefix_master_orf_v4 = { + NULL, NULL, NULL, PLC_MAXLEVELV4, +}; + +/* Static structure of BGP ORF prefix_list's master. */ +static struct prefix_master prefix_master_orf_v6 = { + NULL, NULL, NULL, PLC_MAXLEVELV6, +}; + +static struct prefix_master *prefix_master_get(afi_t afi, int orf) +{ + if (afi == AFI_IP) + return orf ? &prefix_master_orf_v4 : &prefix_master_ipv4; + if (afi == AFI_IP6) + return orf ? &prefix_master_orf_v6 : &prefix_master_ipv6; + return NULL; +} + +const char *prefix_list_name(struct prefix_list *plist) +{ + return plist->name; +} + +afi_t prefix_list_afi(struct prefix_list *plist) +{ + if (plist->master == &prefix_master_ipv4 + || plist->master == &prefix_master_orf_v4) + return AFI_IP; + return AFI_IP6; +} + +static int prefix_list_compare_func(const struct prefix_list *a, + const struct prefix_list *b) +{ + return strcmp(a->name, b->name); +} + +/* Lookup prefix_list from list of prefix_list by name. */ +static struct prefix_list *prefix_list_lookup_do(afi_t afi, int orf, + const char *name) +{ + struct prefix_list *plist, lookup; + struct prefix_master *master; + + if (name == NULL) + return NULL; + + master = prefix_master_get(afi, orf); + if (master == NULL) + return NULL; + + lookup.name = XSTRDUP(MTYPE_TMP, name); + plist = plist_find(&master->str, &lookup); + XFREE(MTYPE_TMP, lookup.name); + return plist; +} + +struct prefix_list *prefix_list_lookup(afi_t afi, const char *name) +{ + return prefix_list_lookup_do(afi, 0, name); +} + +struct prefix_list *prefix_bgp_orf_lookup(afi_t afi, const char *name) +{ + return prefix_list_lookup_do(afi, 1, name); +} + +static struct prefix_list *prefix_list_new(void) +{ + struct prefix_list *new; + + new = XCALLOC(MTYPE_PREFIX_LIST, sizeof(struct prefix_list)); + return new; +} + +static void prefix_list_free(struct prefix_list *plist) +{ + XFREE(MTYPE_PREFIX_LIST, plist); +} + +struct prefix_list_entry *prefix_list_entry_new(void) +{ + struct prefix_list_entry *new; + + new = XCALLOC(MTYPE_PREFIX_LIST_ENTRY, + sizeof(struct prefix_list_entry)); + return new; +} + +void prefix_list_entry_free(struct prefix_list_entry *pentry) +{ + XFREE(MTYPE_PREFIX_LIST_ENTRY, pentry); +} + +/* Insert new prefix list to list of prefix_list. Each prefix_list + is sorted by the name. */ +static struct prefix_list *prefix_list_insert(afi_t afi, int orf, + const char *name) +{ + struct prefix_list *plist; + struct prefix_master *master; + + master = prefix_master_get(afi, orf); + if (master == NULL) + return NULL; + + /* Allocate new prefix_list and copy given name. */ + plist = prefix_list_new(); + plist->name = XSTRDUP(MTYPE_MPREFIX_LIST_STR, name); + plist->master = master; + plist->trie = + XCALLOC(MTYPE_PREFIX_LIST_TRIE, sizeof(struct pltrie_table)); + + plist_add(&master->str, plist); + + return plist; +} + +struct prefix_list *prefix_list_get(afi_t afi, int orf, const char *name) +{ + struct prefix_list *plist; + + plist = prefix_list_lookup_do(afi, orf, name); + + if (plist == NULL) + plist = prefix_list_insert(afi, orf, name); + return plist; +} + +static void prefix_list_trie_del(struct prefix_list *plist, + struct prefix_list_entry *pentry); + +/* Delete prefix-list from prefix_list_master and free it. */ +void prefix_list_delete(struct prefix_list *plist) +{ + struct prefix_master *master; + struct prefix_list_entry *pentry; + struct prefix_list_entry *next; + + /* If prefix-list contain prefix_list_entry free all of it. */ + for (pentry = plist->head; pentry; pentry = next) { + route_map_notify_pentry_dependencies(plist->name, pentry, + RMAP_EVENT_PLIST_DELETED); + next = pentry->next; + prefix_list_trie_del(plist, pentry); + prefix_list_entry_free(pentry); + plist->count--; + } + + master = plist->master; + + plist_del(&master->str, plist); + + XFREE(MTYPE_TMP, plist->desc); + + /* Make sure master's recent changed prefix-list information is + cleared. */ + master->recent = NULL; + + route_map_notify_dependencies(plist->name, RMAP_EVENT_PLIST_DELETED); + + if (master->delete_hook) + (*master->delete_hook)(plist); + + XFREE(MTYPE_MPREFIX_LIST_STR, plist->name); + + XFREE(MTYPE_PREFIX_LIST_TRIE, plist->trie); + + prefix_list_free(plist); +} + +static struct prefix_list_entry * +prefix_list_entry_make(struct prefix *prefix, enum prefix_list_type type, + int64_t seq, int le, int ge, bool any) +{ + struct prefix_list_entry *pentry; + + pentry = prefix_list_entry_new(); + + if (any) + pentry->any = true; + + prefix_copy(&pentry->prefix, prefix); + pentry->type = type; + pentry->seq = seq; + pentry->le = le; + pentry->ge = ge; + + return pentry; +} + +/* Add hook function. */ +void prefix_list_add_hook(void (*func)(struct prefix_list *plist)) +{ + prefix_master_ipv4.add_hook = func; + prefix_master_ipv6.add_hook = func; +} + +/* Delete hook function. */ +void prefix_list_delete_hook(void (*func)(struct prefix_list *plist)) +{ + prefix_master_ipv4.delete_hook = func; + prefix_master_ipv6.delete_hook = func; +} + +/* Calculate new sequential number. */ +int64_t prefix_new_seq_get(struct prefix_list *plist) +{ + int64_t maxseq; + int64_t newseq; + struct prefix_list_entry *pentry; + + maxseq = 0; + + for (pentry = plist->head; pentry; pentry = pentry->next) { + if (maxseq < pentry->seq) + maxseq = pentry->seq; + } + + newseq = ((maxseq / 5) * 5) + 5; + + return (newseq > UINT_MAX) ? UINT_MAX : newseq; +} + +/* Return prefix list entry which has same seq number. */ +static struct prefix_list_entry *prefix_seq_check(struct prefix_list *plist, + int64_t seq) +{ + struct prefix_list_entry *pentry; + + for (pentry = plist->head; pentry; pentry = pentry->next) + if (pentry->seq == seq) + return pentry; + return NULL; +} + +struct prefix_list_entry * +prefix_list_entry_lookup(struct prefix_list *plist, struct prefix *prefix, + enum prefix_list_type type, int64_t seq, + int le, int ge) +{ + struct prefix_list_entry *pentry; + + for (pentry = plist->head; pentry; pentry = pentry->next) + if (prefix_same(&pentry->prefix, prefix) + && pentry->type == type) { + if (seq >= 0 && pentry->seq != seq) + continue; + + if (pentry->le != le) + continue; + if (pentry->ge != ge) + continue; + + return pentry; + } + + return NULL; +} + +static void trie_walk_affected(size_t validbits, struct pltrie_table *table, + uint8_t byte, struct prefix_list_entry *object, + void (*fn)(struct prefix_list_entry *object, + struct prefix_list_entry **updptr)) +{ + uint8_t mask; + uint16_t bwalk; + + if (validbits > PLC_BITS) { + fn(object, &table->entries[byte].final_chain); + return; + } + + mask = (1 << (8 - validbits)) - 1; + for (bwalk = byte & ~mask; bwalk <= byte + mask; bwalk++) { + fn(object, &table->entries[bwalk].up_chain); + } +} + +static void trie_uninstall_fn(struct prefix_list_entry *object, + struct prefix_list_entry **updptr) +{ + for (; *updptr; updptr = &(*updptr)->next_best) + if (*updptr == object) { + *updptr = object->next_best; + break; + } +} + +static int trie_table_empty(struct pltrie_table *table) +{ + size_t i; + for (i = 0; i < PLC_LEN; i++) + if (table->entries[i].next_table || table->entries[i].up_chain) + return 0; + return 1; +} + +static void prefix_list_trie_del(struct prefix_list *plist, + struct prefix_list_entry *pentry) +{ + size_t depth, maxdepth = plist->master->trie_depth; + uint8_t *bytes = pentry->prefix.u.val; + size_t validbits = pentry->prefix.prefixlen; + struct pltrie_table *table, **tables[PLC_MAXLEVEL]; + + table = plist->trie; + for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) { + uint8_t byte = bytes[depth]; + assert(table->entries[byte].next_table); + + tables[depth + 1] = &table->entries[byte].next_table; + table = table->entries[byte].next_table; + + validbits -= PLC_BITS; + } + + trie_walk_affected(validbits, table, bytes[depth], pentry, + trie_uninstall_fn); + + for (; depth > 0; depth--) + if (trie_table_empty(*tables[depth])) { + XFREE(MTYPE_PREFIX_LIST_TRIE, *tables[depth]); + } +} + + +void prefix_list_entry_delete(struct prefix_list *plist, + struct prefix_list_entry *pentry, + int update_list) +{ + if (plist == NULL || pentry == NULL) + return; + + prefix_list_trie_del(plist, pentry); + + if (pentry->prev) + pentry->prev->next = pentry->next; + else + plist->head = pentry->next; + if (pentry->next) + pentry->next->prev = pentry->prev; + else + plist->tail = pentry->prev; + + route_map_notify_pentry_dependencies(plist->name, pentry, + RMAP_EVENT_PLIST_DELETED); + prefix_list_entry_free(pentry); + + plist->count--; + + if (update_list) { + route_map_notify_dependencies(plist->name, + RMAP_EVENT_PLIST_DELETED); + if (plist->master->delete_hook) + (*plist->master->delete_hook)(plist); + + if (plist->head == NULL && plist->tail == NULL + && plist->desc == NULL) + prefix_list_delete(plist); + else + plist->master->recent = plist; + } +} + +static void trie_install_fn(struct prefix_list_entry *object, + struct prefix_list_entry **updptr) +{ + while (*updptr) { + if (*updptr == object) + return; + if ((*updptr)->prefix.prefixlen < object->prefix.prefixlen) + break; + if ((*updptr)->prefix.prefixlen == object->prefix.prefixlen + && (*updptr)->seq > object->seq) + break; + updptr = &(*updptr)->next_best; + } + + if (!object->next_best) + object->next_best = *updptr; + else + assert(object->next_best == *updptr || !*updptr); + + *updptr = object; +} + +static void prefix_list_trie_add(struct prefix_list *plist, + struct prefix_list_entry *pentry) +{ + size_t depth = plist->master->trie_depth; + uint8_t *bytes = pentry->prefix.u.val; + size_t validbits = pentry->prefix.prefixlen; + struct pltrie_table *table; + + table = plist->trie; + while (validbits > PLC_BITS && depth > 1) { + if (!table->entries[*bytes].next_table) + table->entries[*bytes].next_table = + XCALLOC(MTYPE_PREFIX_LIST_TRIE, + sizeof(struct pltrie_table)); + table = table->entries[*bytes].next_table; + bytes++; + depth--; + validbits -= PLC_BITS; + } + + trie_walk_affected(validbits, table, *bytes, pentry, trie_install_fn); +} + +static void prefix_list_entry_add(struct prefix_list *plist, + struct prefix_list_entry *pentry) +{ + struct prefix_list_entry *replace; + struct prefix_list_entry *point; + + /* Automatic asignment of seq no. */ + if (pentry->seq == -1) + pentry->seq = prefix_new_seq_get(plist); + + if (plist->tail && pentry->seq > plist->tail->seq) + point = NULL; + else { + /* Is there any same seq prefix list entry? */ + replace = prefix_seq_check(plist, pentry->seq); + if (replace) + prefix_list_entry_delete(plist, replace, 0); + + /* Check insert point. */ + for (point = plist->head; point; point = point->next) + if (point->seq >= pentry->seq) + break; + } + + /* In case of this is the first element of the list. */ + pentry->next = point; + + if (point) { + if (point->prev) + point->prev->next = pentry; + else + plist->head = pentry; + + pentry->prev = point->prev; + point->prev = pentry; + } else { + if (plist->tail) + plist->tail->next = pentry; + else + plist->head = pentry; + + pentry->prev = plist->tail; + plist->tail = pentry; + } + + prefix_list_trie_add(plist, pentry); + + /* Increment count. */ + plist->count++; + + route_map_notify_pentry_dependencies(plist->name, pentry, + RMAP_EVENT_PLIST_ADDED); + + /* Run hook function. */ + if (plist->master->add_hook) + (*plist->master->add_hook)(plist); + + route_map_notify_dependencies(plist->name, RMAP_EVENT_PLIST_ADDED); + plist->master->recent = plist; +} + +/** + * Prefix list entry update start procedure: + * Remove entry from previosly installed master list, tries and notify + * observers. + * + * \param[in] ple prefix list entry. + */ +void prefix_list_entry_update_start(struct prefix_list_entry *ple) +{ + struct prefix_list *pl = ple->pl; + + /* Not installed, nothing to do. */ + if (!ple->installed) + return; + + prefix_list_trie_del(pl, ple); + + /* List manipulation: shameless copy from `prefix_list_entry_delete`. */ + if (ple->prev) + ple->prev->next = ple->next; + else + pl->head = ple->next; + if (ple->next) + ple->next->prev = ple->prev; + else + pl->tail = ple->prev; + + route_map_notify_pentry_dependencies(pl->name, ple, + RMAP_EVENT_PLIST_DELETED); + pl->count--; + + route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_DELETED); + if (pl->master->delete_hook) + (*pl->master->delete_hook)(pl); + + if (pl->head || pl->tail || pl->desc) + pl->master->recent = pl; + + ple->next_best = NULL; + ple->installed = false; +} + +/** + * Prefix list entry update finish procedure: + * Add entry back master list, to the trie, notify observers and call master + * hook. + * + * \param[in] ple prefix list entry. + */ +void prefix_list_entry_update_finish(struct prefix_list_entry *ple) +{ + struct prefix_list *pl = ple->pl; + struct prefix_list_entry *point; + + /* Already installed, nothing to do. */ + if (ple->installed) + return; + + /* + * Check if the entry is installable: + * We can only install entry if at least the prefix is provided (IPv4 + * or IPv6). + */ + if (ple->prefix.family != AF_INET && ple->prefix.family != AF_INET6) + return; + + /* List manipulation: shameless copy from `prefix_list_entry_add`. */ + if (pl->tail && ple->seq > pl->tail->seq) + point = NULL; + else { + /* Check insert point. */ + for (point = pl->head; point; point = point->next) + if (point->seq >= ple->seq) + break; + } + + /* In case of this is the first element of the list. */ + ple->next = point; + + if (point) { + if (point->prev) + point->prev->next = ple; + else + pl->head = ple; + + ple->prev = point->prev; + point->prev = ple; + } else { + if (pl->tail) + pl->tail->next = ple; + else + pl->head = ple; + + ple->prev = pl->tail; + pl->tail = ple; + } + + prefix_list_trie_add(pl, ple); + pl->count++; + + route_map_notify_pentry_dependencies(pl->name, ple, + RMAP_EVENT_PLIST_ADDED); + + /* Run hook function. */ + if (pl->master->add_hook) + (*pl->master->add_hook)(pl); + + route_map_notify_dependencies(pl->name, RMAP_EVENT_PLIST_ADDED); + pl->master->recent = pl; + + ple->installed = true; +} + +/** + * Same as `prefix_list_entry_delete` but without `free()`ing the list if its + * empty. + * + * \param[in] ple prefix list entry. + */ +void prefix_list_entry_delete2(struct prefix_list_entry *ple) +{ + /* Does the boiler plate list removal and entry removal notification. */ + prefix_list_entry_update_start(ple); + + /* Effective `free()` memory. */ + prefix_list_entry_free(ple); +} + +/* Return string of prefix_list_type. */ +static const char *prefix_list_type_str(struct prefix_list_entry *pentry) +{ + switch (pentry->type) { + case PREFIX_PERMIT: + return "permit"; + case PREFIX_DENY: + return "deny"; + default: + return ""; + } +} + +static int prefix_list_entry_match(struct prefix_list_entry *pentry, + const struct prefix *p, bool address_mode) +{ + int ret; + + if (pentry->prefix.family != p->family) + return 0; + + ret = prefix_match(&pentry->prefix, p); + if (!ret) + return 0; + + if (address_mode) + return 1; + + /* In case of le nor ge is specified, exact match is performed. */ + if (!pentry->le && !pentry->ge) { + if (pentry->prefix.prefixlen != p->prefixlen) + return 0; + } else { + if (pentry->le) + if (p->prefixlen > pentry->le) + return 0; + + if (pentry->ge) + if (p->prefixlen < pentry->ge) + return 0; + } + return 1; +} + +enum prefix_list_type prefix_list_apply_ext( + struct prefix_list *plist, + const struct prefix_list_entry **which, + union prefixconstptr object, + bool address_mode) +{ + struct prefix_list_entry *pentry, *pbest = NULL; + + const struct prefix *p = object.p; + const uint8_t *byte = p->u.val; + size_t depth; + size_t validbits = p->prefixlen; + struct pltrie_table *table; + + if (plist == NULL) { + if (which) + *which = NULL; + return PREFIX_DENY; + } + + if (plist->count == 0) { + if (which) + *which = NULL; + return PREFIX_PERMIT; + } + + depth = plist->master->trie_depth; + table = plist->trie; + while (1) { + for (pentry = table->entries[*byte].up_chain; pentry; + pentry = pentry->next_best) { + if (pbest && pbest->seq < pentry->seq) + continue; + if (prefix_list_entry_match(pentry, p, address_mode)) + pbest = pentry; + } + + if (validbits <= PLC_BITS) + break; + validbits -= PLC_BITS; + + if (--depth) { + if (!table->entries[*byte].next_table) + break; + + table = table->entries[*byte].next_table; + byte++; + continue; + } + + for (pentry = table->entries[*byte].final_chain; pentry; + pentry = pentry->next_best) { + if (pbest && pbest->seq < pentry->seq) + continue; + if (prefix_list_entry_match(pentry, p, address_mode)) + pbest = pentry; + } + break; + } + + if (which) { + if (pbest) + *which = pbest; + else + *which = NULL; + } + + if (pbest == NULL) + return PREFIX_DENY; + + pbest->hitcnt++; + return pbest->type; +} + +static void __attribute__((unused)) prefix_list_print(struct prefix_list *plist) +{ + struct prefix_list_entry *pentry; + + if (plist == NULL) + return; + + printf("ip prefix-list %s: %d entries\n", plist->name, plist->count); + + for (pentry = plist->head; pentry; pentry = pentry->next) { + if (pentry->any) + printf("any %s\n", prefix_list_type_str(pentry)); + else { + struct prefix *p; + + p = &pentry->prefix; + + printf(" seq %lld %s %pFX", (long long)pentry->seq, + prefix_list_type_str(pentry), p); + if (pentry->ge) + printf(" ge %d", pentry->ge); + if (pentry->le) + printf(" le %d", pentry->le); + printf("\n"); + } + } +} + +/* Return 1 when plist already include pentry policy. */ +static struct prefix_list_entry * +prefix_entry_dup_check(struct prefix_list *plist, struct prefix_list_entry *new) +{ + size_t depth, maxdepth = plist->master->trie_depth; + uint8_t byte, *bytes = new->prefix.u.val; + size_t validbits = new->prefix.prefixlen; + struct pltrie_table *table; + struct prefix_list_entry *pentry; + int64_t seq = 0; + + if (new->seq == -1) + seq = prefix_new_seq_get(plist); + else + seq = new->seq; + + table = plist->trie; + for (depth = 0; validbits > PLC_BITS && depth < maxdepth - 1; depth++) { + byte = bytes[depth]; + if (!table->entries[byte].next_table) + return NULL; + + table = table->entries[byte].next_table; + validbits -= PLC_BITS; + } + + byte = bytes[depth]; + if (validbits > PLC_BITS) + pentry = table->entries[byte].final_chain; + else + pentry = table->entries[byte].up_chain; + + for (; pentry; pentry = pentry->next_best) { + if (prefix_same(&pentry->prefix, &new->prefix) + && pentry->type == new->type && pentry->le == new->le + && pentry->ge == new->ge && pentry->seq != seq) + return pentry; + } + return NULL; +} + +enum display_type { + normal_display, + summary_display, + detail_display, + sequential_display, + longer_display, + first_match_display +}; + +static void vty_show_prefix_entry(struct vty *vty, json_object *json, afi_t afi, + struct prefix_list *plist, + struct prefix_master *master, + enum display_type dtype, int seqnum) +{ + struct prefix_list_entry *pentry; + json_object *json_pl = NULL; + + /* Print the name of the protocol */ + if (json) { + json_pl = json_object_new_object(); + json_object_object_add(json, plist->name, json_pl); + } else + vty_out(vty, "%s: ", frr_protoname); + + if (dtype == normal_display) { + if (json) { + json_object_string_add(json_pl, "addressFamily", + afi2str(afi)); + json_object_int_add(json_pl, "entries", plist->count); + if (plist->desc) + json_object_string_add(json_pl, "description", + plist->desc); + } else { + vty_out(vty, "ip%s prefix-list %s: %d entries\n", + afi == AFI_IP ? "" : "v6", plist->name, + plist->count); + if (plist->desc) + vty_out(vty, " Description: %s\n", + plist->desc); + } + } else if (dtype == summary_display || dtype == detail_display) { + if (json) { + json_object_string_add(json_pl, "addressFamily", + afi2str(afi)); + if (plist->desc) + json_object_string_add(json_pl, "description", + plist->desc); + json_object_int_add(json_pl, "count", plist->count); + json_object_int_add(json_pl, "rangeEntries", + plist->rangecount); + json_object_int_add(json_pl, "sequenceStart", + plist->head ? plist->head->seq : 0); + json_object_int_add(json_pl, "sequenceEnd", + plist->tail ? plist->tail->seq : 0); + } else { + vty_out(vty, "ip%s prefix-list %s:\n", + afi == AFI_IP ? "" : "v6", plist->name); + + if (plist->desc) + vty_out(vty, " Description: %s\n", + plist->desc); + + vty_out(vty, + " count: %d, range entries: %d, sequences: %" PRId64 + " - %" PRId64 "\n", + plist->count, plist->rangecount, + plist->head ? plist->head->seq : 0, + plist->tail ? plist->tail->seq : 0); + } + } + + if (dtype != summary_display) { + json_object *json_entries = NULL; + + if (json) { + json_entries = json_object_new_array(); + json_object_object_add(json_pl, "entries", + json_entries); + } + + for (pentry = plist->head; pentry; pentry = pentry->next) { + if (dtype == sequential_display + && pentry->seq != seqnum) + continue; + + if (json) { + json_object *json_entry; + + json_entry = json_object_new_object(); + json_object_array_add(json_entries, json_entry); + + json_object_int_add(json_entry, + "sequenceNumber", + pentry->seq); + json_object_string_add( + json_entry, "type", + prefix_list_type_str(pentry)); + json_object_string_addf(json_entry, "prefix", + "%pFX", + &pentry->prefix); + + if (pentry->ge) + json_object_int_add( + json_entry, + "minimumPrefixLength", + pentry->ge); + if (pentry->le) + json_object_int_add( + json_entry, + "maximumPrefixLength", + pentry->le); + + if (dtype == detail_display + || dtype == sequential_display) { + json_object_int_add(json_entry, + "hitCount", + pentry->hitcnt); + json_object_int_add(json_entry, + "referenceCount", + pentry->refcnt); + } + } else { + vty_out(vty, " "); + + vty_out(vty, "seq %" PRId64 " ", pentry->seq); + + vty_out(vty, "%s ", + prefix_list_type_str(pentry)); + + if (pentry->any) + vty_out(vty, "any"); + else { + struct prefix *p = &pentry->prefix; + + vty_out(vty, "%pFX", p); + + if (pentry->ge) + vty_out(vty, " ge %d", + pentry->ge); + if (pentry->le) + vty_out(vty, " le %d", + pentry->le); + } + + if (dtype == detail_display + || dtype == sequential_display) + vty_out(vty, + " (hit count: %ld, refcount: %ld)", + pentry->hitcnt, pentry->refcnt); + + vty_out(vty, "\n"); + } + } + } +} + +static int vty_show_prefix_list(struct vty *vty, afi_t afi, const char *name, + const char *seq, enum display_type dtype, + bool uj) +{ + struct prefix_list *plist; + struct prefix_master *master; + int64_t seqnum = 0; + json_object *json = NULL; + json_object *json_proto = NULL; + + master = prefix_master_get(afi, 0); + if (master == NULL) + return CMD_WARNING; + + if (uj) { + json = json_object_new_object(); + json_proto = json_object_new_object(); + json_object_object_add(json, frr_protoname, json_proto); + } + + if (seq) + seqnum = (int64_t)atol(seq); + + if (name) { + plist = prefix_list_lookup(afi, name); + if (!plist) { + if (!uj) + vty_out(vty, + "%% Can't find specified prefix-list\n"); + return CMD_WARNING; + } + vty_show_prefix_entry(vty, json_proto, afi, plist, master, + dtype, seqnum); + } else { + if (dtype == detail_display || dtype == summary_display) { + if (master->recent && !uj) + vty_out(vty, + "Prefix-list with the last deletion/insertion: %s\n", + master->recent->name); + } + + frr_each (plist, &master->str, plist) + vty_show_prefix_entry(vty, json_proto, afi, plist, + master, dtype, seqnum); + } + + return vty_json(vty, json); +} + +static int vty_show_prefix_list_prefix(struct vty *vty, afi_t afi, + const char *name, const char *prefix, + enum display_type type) +{ + struct prefix_list *plist; + struct prefix_list_entry *pentry; + struct prefix p; + int ret; + int match; + + plist = prefix_list_lookup(afi, name); + if (!plist) { + vty_out(vty, "%% Can't find specified prefix-list\n"); + return CMD_WARNING; + } + + ret = str2prefix(prefix, &p); + if (ret <= 0) { + vty_out(vty, "%% prefix is malformed\n"); + return CMD_WARNING; + } + + for (pentry = plist->head; pentry; pentry = pentry->next) { + match = 0; + + if (type == normal_display || type == first_match_display) + if (prefix_same(&p, &pentry->prefix)) + match = 1; + + if (type == longer_display) { + if ((p.family == pentry->prefix.family) + && (prefix_match(&p, &pentry->prefix))) + match = 1; + } + + if (match) { + vty_out(vty, " seq %" PRId64 " %s ", pentry->seq, + prefix_list_type_str(pentry)); + + if (pentry->any) + vty_out(vty, "any"); + else { + struct prefix *pf = &pentry->prefix; + + vty_out(vty, "%pFX", pf); + + if (pentry->ge) + vty_out(vty, " ge %d", pentry->ge); + if (pentry->le) + vty_out(vty, " le %d", pentry->le); + } + + if (type == normal_display + || type == first_match_display) + vty_out(vty, " (hit count: %ld, refcount: %ld)", + pentry->hitcnt, pentry->refcnt); + + vty_out(vty, "\n"); + + if (type == first_match_display) + return CMD_SUCCESS; + } + } + return CMD_SUCCESS; +} + +static int vty_clear_prefix_list(struct vty *vty, afi_t afi, const char *name, + const char *prefix) +{ + struct prefix_master *master; + struct prefix_list *plist; + struct prefix_list_entry *pentry; + int ret; + struct prefix p; + + master = prefix_master_get(afi, 0); + if (master == NULL) + return CMD_WARNING; + + if (name == NULL && prefix == NULL) { + frr_each (plist, &master->str, plist) + for (pentry = plist->head; pentry; + pentry = pentry->next) + pentry->hitcnt = 0; + } else { + plist = prefix_list_lookup(afi, name); + if (!plist) { + vty_out(vty, "%% Can't find specified prefix-list\n"); + return CMD_WARNING; + } + + if (prefix) { + ret = str2prefix(prefix, &p); + if (ret <= 0) { + vty_out(vty, "%% prefix is malformed\n"); + return CMD_WARNING; + } + } + + for (pentry = plist->head; pentry; pentry = pentry->next) { + if (prefix) { + if (pentry->prefix.family == p.family + && prefix_match(&pentry->prefix, &p)) + pentry->hitcnt = 0; + } else + pentry->hitcnt = 0; + } + } + return CMD_SUCCESS; +} + +#ifndef VTYSH_EXTRACT_PL +#include "lib/plist_clippy.c" +#endif + +DEFPY (show_ip_prefix_list, + show_ip_prefix_list_cmd, + "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]", + SHOW_STR + IP_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "sequence number of an entry\n" + "Sequence number\n" + JSON_STR) +{ + enum display_type dtype = normal_display; + if (dseq) + dtype = sequential_display; + + return vty_show_prefix_list(vty, AFI_IP, prefix_list, arg_str, dtype, + !!uj); +} + +DEFPY (show_ip_prefix_list_prefix, + show_ip_prefix_list_prefix_cmd, + "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]", + SHOW_STR + IP_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n" + "Lookup longer prefix\n" + "First matched prefix\n") +{ + enum display_type dtype = normal_display; + if (dl) + dtype = longer_display; + else if (dfm) + dtype = first_match_display; + + return vty_show_prefix_list_prefix(vty, AFI_IP, prefix_list, prefix_str, + dtype); +} + +DEFPY (show_ip_prefix_list_summary, + show_ip_prefix_list_summary_cmd, + "show ip prefix-list summary [WORD$prefix_list] [json$uj]", + SHOW_STR + IP_STR + PREFIX_LIST_STR + "Summary of prefix lists\n" + "Name of a prefix list\n" + JSON_STR) +{ + return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL, + summary_display, !!uj); +} + +DEFPY (show_ip_prefix_list_detail, + show_ip_prefix_list_detail_cmd, + "show ip prefix-list detail [WORD$prefix_list] [json$uj]", + SHOW_STR + IP_STR + PREFIX_LIST_STR + "Detail of prefix lists\n" + "Name of a prefix list\n" + JSON_STR) +{ + return vty_show_prefix_list(vty, AFI_IP, prefix_list, NULL, + detail_display, !!uj); +} + +DEFPY (clear_ip_prefix_list, + clear_ip_prefix_list_cmd, + "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]", + CLEAR_STR + IP_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n") +{ + return vty_clear_prefix_list(vty, AFI_IP, prefix_list, prefix_str); +} + +DEFPY (show_ipv6_prefix_list, + show_ipv6_prefix_list_cmd, + "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]", + SHOW_STR + IPV6_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "sequence number of an entry\n" + "Sequence number\n" + JSON_STR) +{ + enum display_type dtype = normal_display; + if (dseq) + dtype = sequential_display; + + return vty_show_prefix_list(vty, AFI_IP6, prefix_list, arg_str, dtype, + !!uj); +} + +DEFPY (show_ipv6_prefix_list_prefix, + show_ipv6_prefix_list_prefix_cmd, + "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]", + SHOW_STR + IPV6_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n" + "Lookup longer prefix\n" + "First matched prefix\n") +{ + enum display_type dtype = normal_display; + if (dl) + dtype = longer_display; + else if (dfm) + dtype = first_match_display; + + return vty_show_prefix_list_prefix(vty, AFI_IP6, prefix_list, + prefix_str, dtype); +} + +DEFPY (show_ipv6_prefix_list_summary, + show_ipv6_prefix_list_summary_cmd, + "show ipv6 prefix-list summary [WORD$prefix-list] [json$uj]", + SHOW_STR + IPV6_STR + PREFIX_LIST_STR + "Summary of prefix lists\n" + "Name of a prefix list\n" + JSON_STR) +{ + return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL, + summary_display, !!uj); +} + +DEFPY (show_ipv6_prefix_list_detail, + show_ipv6_prefix_list_detail_cmd, + "show ipv6 prefix-list detail [WORD$prefix-list] [json$uj]", + SHOW_STR + IPV6_STR + PREFIX_LIST_STR + "Detail of prefix lists\n" + "Name of a prefix list\n" + JSON_STR) +{ + return vty_show_prefix_list(vty, AFI_IP6, prefix_list, NULL, + detail_display, !!uj); +} + +DEFPY (clear_ipv6_prefix_list, + clear_ipv6_prefix_list_cmd, + "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]", + CLEAR_STR + IPV6_STR + PREFIX_LIST_STR + "Name of a prefix list\n" + "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n") +{ + return vty_clear_prefix_list(vty, AFI_IP6, prefix_list, prefix_str); +} + +DEFPY (debug_prefix_list_match, + debug_prefix_list_match_cmd, + "debug prefix-list WORD$prefix-list match <A.B.C.D/M|X:X::X:X/M>" + " [address-mode$addr_mode]", + DEBUG_STR + "Prefix-list test access\n" + "Name of a prefix list\n" + "Test prefix for prefix list result\n" + "Prefix to test in ip prefix-list\n" + "Prefix to test in ipv6 prefix-list\n" + "Use address matching mode (PIM RP)\n") +{ + struct prefix_list *plist; + const struct prefix_list_entry *entry = NULL; + enum prefix_list_type ret; + + plist = prefix_list_lookup(family2afi(match->family), prefix_list); + if (!plist) { + vty_out(vty, "%% no prefix list named %s for AFI %s\n", + prefix_list, afi2str(family2afi(match->family))); + return CMD_WARNING; + } + + ret = prefix_list_apply_ext(plist, &entry, match, !!addr_mode); + + vty_out(vty, "%s prefix list %s yields %s for %pFX, ", + afi2str(family2afi(match->family)), prefix_list, + ret == PREFIX_DENY ? "DENY" : "PERMIT", match); + + if (!entry) + vty_out(vty, "no match found\n"); + else { + vty_out(vty, "matching entry #%"PRId64": %pFX", entry->seq, + &entry->prefix); + if (entry->ge) + vty_out(vty, " ge %d", entry->ge); + if (entry->le) + vty_out(vty, " le %d", entry->le); + vty_out(vty, "\n"); + } + + /* allow using this in scripts for quick prefix-list member tests */ + return (ret == PREFIX_PERMIT) ? CMD_SUCCESS : CMD_WARNING; +} + +struct stream *prefix_bgp_orf_entry(struct stream *s, struct prefix_list *plist, + uint8_t init_flag, uint8_t permit_flag, + uint8_t deny_flag) +{ + struct prefix_list_entry *pentry; + + if (!plist) + return s; + + for (pentry = plist->head; pentry; pentry = pentry->next) { + uint8_t flag = init_flag; + struct prefix *p = &pentry->prefix; + + flag |= (pentry->type == PREFIX_PERMIT ? permit_flag + : deny_flag); + stream_putc(s, flag); + stream_putl(s, (uint32_t)pentry->seq); + stream_putc(s, (uint8_t)pentry->ge); + stream_putc(s, (uint8_t)pentry->le); + stream_put_prefix(s, p); + } + + return s; +} + +int prefix_bgp_orf_set(char *name, afi_t afi, struct orf_prefix *orfp, + int permit, int set) +{ + struct prefix_list *plist; + struct prefix_list_entry *pentry; + + /* ge and le value check */ + if (orfp->ge && orfp->ge < orfp->p.prefixlen) + return CMD_WARNING_CONFIG_FAILED; + if (orfp->le && orfp->le < orfp->p.prefixlen) + return CMD_WARNING_CONFIG_FAILED; + if (orfp->le && orfp->ge > orfp->le) + return CMD_WARNING_CONFIG_FAILED; + + if (orfp->ge && orfp->le == (afi == AFI_IP ? 32 : 128)) + orfp->le = 0; + + plist = prefix_list_get(afi, 1, name); + if (!plist) + return CMD_WARNING_CONFIG_FAILED; + + apply_mask(&orfp->p); + + if (set) { + pentry = prefix_list_entry_make( + &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY), + orfp->seq, orfp->le, orfp->ge, false); + + if (prefix_entry_dup_check(plist, pentry)) { + prefix_list_entry_free(pentry); + return CMD_WARNING_CONFIG_FAILED; + } + + prefix_list_entry_add(plist, pentry); + } else { + pentry = prefix_list_entry_lookup( + plist, &orfp->p, (permit ? PREFIX_PERMIT : PREFIX_DENY), + orfp->seq, orfp->le, orfp->ge); + + if (!pentry) + return CMD_WARNING_CONFIG_FAILED; + + prefix_list_entry_delete(plist, pentry, 1); + } + + return CMD_SUCCESS; +} + +void prefix_bgp_orf_remove_all(afi_t afi, char *name) +{ + struct prefix_list *plist; + + plist = prefix_bgp_orf_lookup(afi, name); + if (plist) + prefix_list_delete(plist); +} + +/* return prefix count */ +int prefix_bgp_show_prefix_list(struct vty *vty, afi_t afi, char *name, + bool use_json) +{ + struct prefix_list *plist; + struct prefix_list_entry *pentry; + json_object *json = NULL; + json_object *json_prefix = NULL; + json_object *json_list = NULL; + + plist = prefix_bgp_orf_lookup(afi, name); + if (!plist) + return 0; + + if (!vty) + return plist->count; + + if (use_json) { + json = json_object_new_object(); + json_prefix = json_object_new_object(); + json_list = json_object_new_object(); + + json_object_int_add(json_prefix, "prefixListCounter", + plist->count); + json_object_string_add(json_prefix, "prefixListName", + plist->name); + + for (pentry = plist->head; pentry; pentry = pentry->next) { + struct prefix *p = &pentry->prefix; + char buf_a[BUFSIZ]; + + snprintf(buf_a, sizeof(buf_a), "%pFX", p); + + json_object_int_add(json_list, "seq", pentry->seq); + json_object_string_add(json_list, "seqPrefixListType", + prefix_list_type_str(pentry)); + + if (pentry->ge) + json_object_int_add(json_list, "ge", + pentry->ge); + if (pentry->le) + json_object_int_add(json_list, "le", + pentry->le); + + json_object_object_add(json_prefix, buf_a, json_list); + } + if (afi == AFI_IP) + json_object_object_add(json, "ipPrefixList", + json_prefix); + else + json_object_object_add(json, "ipv6PrefixList", + json_prefix); + + vty_json(vty, json); + } else { + vty_out(vty, "ip%s prefix-list %s: %d entries\n", + afi == AFI_IP ? "" : "v6", plist->name, plist->count); + + for (pentry = plist->head; pentry; pentry = pentry->next) { + struct prefix *p = &pentry->prefix; + + vty_out(vty, " seq %" PRId64 " %s %pFX", pentry->seq, + prefix_list_type_str(pentry), p); + + if (pentry->ge) + vty_out(vty, " ge %d", pentry->ge); + if (pentry->le) + vty_out(vty, " le %d", pentry->le); + + vty_out(vty, "\n"); + } + } + return plist->count; +} + +static void prefix_list_reset_afi(afi_t afi, int orf) +{ + struct prefix_list *plist; + struct prefix_master *master; + + master = prefix_master_get(afi, orf); + if (master == NULL) + return; + + while ((plist = plist_first(&master->str))) { + prefix_list_delete(plist); + } + + master->recent = NULL; +} + +/* Prefix-list node. */ +static struct cmd_node prefix_node = { + .name = "ipv4 prefix list", + .node = PREFIX_NODE, + .prompt = "", +}; + +static void plist_autocomplete_afi(afi_t afi, vector comps, + struct cmd_token *token) +{ + struct prefix_list *plist; + struct prefix_master *master; + + master = prefix_master_get(afi, 0); + if (master == NULL) + return; + + frr_each (plist, &master->str, plist) + vector_set(comps, XSTRDUP(MTYPE_COMPLETION, plist->name)); +} + +static void plist_autocomplete(vector comps, struct cmd_token *token) +{ + plist_autocomplete_afi(AFI_IP, comps, token); + plist_autocomplete_afi(AFI_IP6, comps, token); +} + +static const struct cmd_variable_handler plist_var_handlers[] = { + {/* "prefix-list WORD" */ + .varname = "prefix_list", + .completions = plist_autocomplete}, + {.tokenname = "PREFIXLIST_NAME", + .completions = plist_autocomplete}, + {.completions = NULL}}; + + +static void prefix_list_init_ipv4(void) +{ + install_node(&prefix_node); + + install_element(VIEW_NODE, &show_ip_prefix_list_cmd); + install_element(VIEW_NODE, &show_ip_prefix_list_prefix_cmd); + install_element(VIEW_NODE, &show_ip_prefix_list_summary_cmd); + install_element(VIEW_NODE, &show_ip_prefix_list_detail_cmd); + + install_element(ENABLE_NODE, &clear_ip_prefix_list_cmd); +} + +/* Prefix-list node. */ +static struct cmd_node prefix_ipv6_node = { + .name = "ipv6 prefix list", + .node = PREFIX_IPV6_NODE, + .prompt = "", +}; + +static void prefix_list_init_ipv6(void) +{ + install_node(&prefix_ipv6_node); + + install_element(VIEW_NODE, &show_ipv6_prefix_list_cmd); + install_element(VIEW_NODE, &show_ipv6_prefix_list_prefix_cmd); + install_element(VIEW_NODE, &show_ipv6_prefix_list_summary_cmd); + install_element(VIEW_NODE, &show_ipv6_prefix_list_detail_cmd); + install_element(VIEW_NODE, &debug_prefix_list_match_cmd); + + install_element(ENABLE_NODE, &clear_ipv6_prefix_list_cmd); +} + +void prefix_list_init(void) +{ + plist_init(&prefix_master_ipv4.str); + plist_init(&prefix_master_orf_v4.str); + plist_init(&prefix_master_ipv6.str); + plist_init(&prefix_master_orf_v6.str); + + cmd_variable_handler_register(plist_var_handlers); + + prefix_list_init_ipv4(); + prefix_list_init_ipv6(); +} + +void prefix_list_reset(void) +{ + prefix_list_reset_afi(AFI_IP, 0); + prefix_list_reset_afi(AFI_IP6, 0); + prefix_list_reset_afi(AFI_IP, 1); + prefix_list_reset_afi(AFI_IP6, 1); +} |