1 /* Prefix list functions.
2 * Copyright (C) 1999 Kunihiro Ishiguro
4 * This file is part of GNU Zebra.
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.
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.
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
27 #include "sockunion.h"
35 #include "plist_int.h"
37 DEFINE_MTYPE_STATIC(LIB
, PREFIX_LIST
, "Prefix List");
38 DEFINE_MTYPE_STATIC(LIB
, MPREFIX_LIST_STR
, "Prefix List Str");
39 DEFINE_MTYPE_STATIC(LIB
, PREFIX_LIST_ENTRY
, "Prefix List Entry");
40 DEFINE_MTYPE_STATIC(LIB
, PREFIX_LIST_TRIE
, "Prefix List Trie Table");
42 /* not currently changeable, code assumes bytes further down */
44 #define PLC_LEN (1 << PLC_BITS)
45 #define PLC_MAXLEVELV4 2 /* /24 for IPv4 */
46 #define PLC_MAXLEVELV6 4 /* /48 for IPv6 */
47 #define PLC_MAXLEVEL 4 /* max(v4,v6) */
51 struct pltrie_table
*next_table
;
52 struct prefix_list_entry
*final_chain
;
55 struct prefix_list_entry
*up_chain
;
59 struct pltrie_entry entries
[PLC_LEN
];
62 /* Master structure of prefix_list. */
63 struct prefix_master
{
64 /* The latest update. */
65 struct prefix_list
*recent
;
67 /* Hook function which is executed when new prefix_list is added. */
68 void (*add_hook
)(struct prefix_list
*);
70 /* Hook function which is executed when prefix_list is deleted. */
71 void (*delete_hook
)(struct prefix_list
*);
73 /* number of bytes that have a trie level */
76 struct plist_head str
;
78 static int prefix_list_compare_func(const struct prefix_list
*a
,
79 const struct prefix_list
*b
);
80 DECLARE_RBTREE_UNIQ(plist
, struct prefix_list
, plist_item
,
81 prefix_list_compare_func
);
83 /* Static structure of IPv4 prefix_list's master. */
84 static struct prefix_master prefix_master_ipv4
= {
85 NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
88 /* Static structure of IPv6 prefix-list's master. */
89 static struct prefix_master prefix_master_ipv6
= {
90 NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
93 /* Static structure of BGP ORF prefix_list's master. */
94 static struct prefix_master prefix_master_orf_v4
= {
95 NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
98 /* Static structure of BGP ORF prefix_list's master. */
99 static struct prefix_master prefix_master_orf_v6
= {
100 NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
103 static struct prefix_master
*prefix_master_get(afi_t afi
, int orf
)
106 return orf
? &prefix_master_orf_v4
: &prefix_master_ipv4
;
108 return orf
? &prefix_master_orf_v6
: &prefix_master_ipv6
;
112 const char *prefix_list_name(struct prefix_list
*plist
)
117 afi_t
prefix_list_afi(struct prefix_list
*plist
)
119 if (plist
->master
== &prefix_master_ipv4
120 || plist
->master
== &prefix_master_orf_v4
)
125 static int prefix_list_compare_func(const struct prefix_list
*a
,
126 const struct prefix_list
*b
)
128 return strcmp(a
->name
, b
->name
);
131 /* Lookup prefix_list from list of prefix_list by name. */
132 static struct prefix_list
*prefix_list_lookup_do(afi_t afi
, int orf
,
135 struct prefix_list
*plist
, lookup
;
136 struct prefix_master
*master
;
141 master
= prefix_master_get(afi
, orf
);
145 lookup
.name
= XSTRDUP(MTYPE_TMP
, name
);
146 plist
= plist_find(&master
->str
, &lookup
);
147 XFREE(MTYPE_TMP
, lookup
.name
);
151 struct prefix_list
*prefix_list_lookup(afi_t afi
, const char *name
)
153 return prefix_list_lookup_do(afi
, 0, name
);
156 struct prefix_list
*prefix_bgp_orf_lookup(afi_t afi
, const char *name
)
158 return prefix_list_lookup_do(afi
, 1, name
);
161 static struct prefix_list
*prefix_list_new(void)
163 struct prefix_list
*new;
165 new = XCALLOC(MTYPE_PREFIX_LIST
, sizeof(struct prefix_list
));
169 static void prefix_list_free(struct prefix_list
*plist
)
171 XFREE(MTYPE_PREFIX_LIST
, plist
);
174 struct prefix_list_entry
*prefix_list_entry_new(void)
176 struct prefix_list_entry
*new;
178 new = XCALLOC(MTYPE_PREFIX_LIST_ENTRY
,
179 sizeof(struct prefix_list_entry
));
183 void prefix_list_entry_free(struct prefix_list_entry
*pentry
)
185 XFREE(MTYPE_PREFIX_LIST_ENTRY
, pentry
);
188 /* Insert new prefix list to list of prefix_list. Each prefix_list
189 is sorted by the name. */
190 static struct prefix_list
*prefix_list_insert(afi_t afi
, int orf
,
193 struct prefix_list
*plist
;
194 struct prefix_master
*master
;
196 master
= prefix_master_get(afi
, orf
);
200 /* Allocate new prefix_list and copy given name. */
201 plist
= prefix_list_new();
202 plist
->name
= XSTRDUP(MTYPE_MPREFIX_LIST_STR
, name
);
203 plist
->master
= master
;
205 XCALLOC(MTYPE_PREFIX_LIST_TRIE
, sizeof(struct pltrie_table
));
207 plist_add(&master
->str
, plist
);
212 struct prefix_list
*prefix_list_get(afi_t afi
, int orf
, const char *name
)
214 struct prefix_list
*plist
;
216 plist
= prefix_list_lookup_do(afi
, orf
, name
);
219 plist
= prefix_list_insert(afi
, orf
, name
);
223 static void prefix_list_trie_del(struct prefix_list
*plist
,
224 struct prefix_list_entry
*pentry
);
226 /* Delete prefix-list from prefix_list_master and free it. */
227 void prefix_list_delete(struct prefix_list
*plist
)
229 struct prefix_master
*master
;
230 struct prefix_list_entry
*pentry
;
231 struct prefix_list_entry
*next
;
233 /* If prefix-list contain prefix_list_entry free all of it. */
234 for (pentry
= plist
->head
; pentry
; pentry
= next
) {
235 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
236 RMAP_EVENT_PLIST_DELETED
);
238 prefix_list_trie_del(plist
, pentry
);
239 prefix_list_entry_free(pentry
);
243 master
= plist
->master
;
245 plist_del(&master
->str
, plist
);
247 XFREE(MTYPE_TMP
, plist
->desc
);
249 /* Make sure master's recent changed prefix-list information is
251 master
->recent
= NULL
;
253 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_DELETED
);
255 if (master
->delete_hook
)
256 (*master
->delete_hook
)(plist
);
258 XFREE(MTYPE_MPREFIX_LIST_STR
, plist
->name
);
260 XFREE(MTYPE_PREFIX_LIST_TRIE
, plist
->trie
);
262 prefix_list_free(plist
);
265 static struct prefix_list_entry
*
266 prefix_list_entry_make(struct prefix
*prefix
, enum prefix_list_type type
,
267 int64_t seq
, int le
, int ge
, bool any
)
269 struct prefix_list_entry
*pentry
;
271 pentry
= prefix_list_entry_new();
276 prefix_copy(&pentry
->prefix
, prefix
);
285 /* Add hook function. */
286 void prefix_list_add_hook(void (*func
)(struct prefix_list
*plist
))
288 prefix_master_ipv4
.add_hook
= func
;
289 prefix_master_ipv6
.add_hook
= func
;
292 /* Delete hook function. */
293 void prefix_list_delete_hook(void (*func
)(struct prefix_list
*plist
))
295 prefix_master_ipv4
.delete_hook
= func
;
296 prefix_master_ipv6
.delete_hook
= func
;
299 /* Calculate new sequential number. */
300 int64_t prefix_new_seq_get(struct prefix_list
*plist
)
304 struct prefix_list_entry
*pentry
;
308 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
309 if (maxseq
< pentry
->seq
)
310 maxseq
= pentry
->seq
;
313 newseq
= ((maxseq
/ 5) * 5) + 5;
315 return (newseq
> UINT_MAX
) ? UINT_MAX
: newseq
;
318 /* Return prefix list entry which has same seq number. */
319 static struct prefix_list_entry
*prefix_seq_check(struct prefix_list
*plist
,
322 struct prefix_list_entry
*pentry
;
324 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
325 if (pentry
->seq
== seq
)
330 struct prefix_list_entry
*
331 prefix_list_entry_lookup(struct prefix_list
*plist
, struct prefix
*prefix
,
332 enum prefix_list_type type
, int64_t seq
,
335 struct prefix_list_entry
*pentry
;
337 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
338 if (prefix_same(&pentry
->prefix
, prefix
)
339 && pentry
->type
== type
) {
340 if (seq
>= 0 && pentry
->seq
!= seq
)
343 if (pentry
->le
!= le
)
345 if (pentry
->ge
!= ge
)
354 static void trie_walk_affected(size_t validbits
, struct pltrie_table
*table
,
355 uint8_t byte
, struct prefix_list_entry
*object
,
356 void (*fn
)(struct prefix_list_entry
*object
,
357 struct prefix_list_entry
**updptr
))
362 if (validbits
> PLC_BITS
) {
363 fn(object
, &table
->entries
[byte
].final_chain
);
367 mask
= (1 << (8 - validbits
)) - 1;
368 for (bwalk
= byte
& ~mask
; bwalk
<= byte
+ mask
; bwalk
++) {
369 fn(object
, &table
->entries
[bwalk
].up_chain
);
373 static void trie_uninstall_fn(struct prefix_list_entry
*object
,
374 struct prefix_list_entry
**updptr
)
376 for (; *updptr
; updptr
= &(*updptr
)->next_best
)
377 if (*updptr
== object
) {
378 *updptr
= object
->next_best
;
383 static int trie_table_empty(struct pltrie_table
*table
)
386 for (i
= 0; i
< PLC_LEN
; i
++)
387 if (table
->entries
[i
].next_table
|| table
->entries
[i
].up_chain
)
392 static void prefix_list_trie_del(struct prefix_list
*plist
,
393 struct prefix_list_entry
*pentry
)
395 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
396 uint8_t *bytes
= pentry
->prefix
.u
.val
;
397 size_t validbits
= pentry
->prefix
.prefixlen
;
398 struct pltrie_table
*table
, **tables
[PLC_MAXLEVEL
];
401 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
402 uint8_t byte
= bytes
[depth
];
403 assert(table
->entries
[byte
].next_table
);
405 tables
[depth
+ 1] = &table
->entries
[byte
].next_table
;
406 table
= table
->entries
[byte
].next_table
;
408 validbits
-= PLC_BITS
;
411 trie_walk_affected(validbits
, table
, bytes
[depth
], pentry
,
414 for (; depth
> 0; depth
--)
415 if (trie_table_empty(*tables
[depth
])) {
416 XFREE(MTYPE_PREFIX_LIST_TRIE
, *tables
[depth
]);
421 void prefix_list_entry_delete(struct prefix_list
*plist
,
422 struct prefix_list_entry
*pentry
,
425 if (plist
== NULL
|| pentry
== NULL
)
428 prefix_list_trie_del(plist
, pentry
);
431 pentry
->prev
->next
= pentry
->next
;
433 plist
->head
= pentry
->next
;
435 pentry
->next
->prev
= pentry
->prev
;
437 plist
->tail
= pentry
->prev
;
439 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
440 RMAP_EVENT_PLIST_DELETED
);
441 prefix_list_entry_free(pentry
);
446 route_map_notify_dependencies(plist
->name
,
447 RMAP_EVENT_PLIST_DELETED
);
448 if (plist
->master
->delete_hook
)
449 (*plist
->master
->delete_hook
)(plist
);
451 if (plist
->head
== NULL
&& plist
->tail
== NULL
452 && plist
->desc
== NULL
)
453 prefix_list_delete(plist
);
455 plist
->master
->recent
= plist
;
459 static void trie_install_fn(struct prefix_list_entry
*object
,
460 struct prefix_list_entry
**updptr
)
463 if (*updptr
== object
)
465 if ((*updptr
)->prefix
.prefixlen
< object
->prefix
.prefixlen
)
467 if ((*updptr
)->prefix
.prefixlen
== object
->prefix
.prefixlen
468 && (*updptr
)->seq
> object
->seq
)
470 updptr
= &(*updptr
)->next_best
;
473 if (!object
->next_best
)
474 object
->next_best
= *updptr
;
476 assert(object
->next_best
== *updptr
|| !*updptr
);
481 static void prefix_list_trie_add(struct prefix_list
*plist
,
482 struct prefix_list_entry
*pentry
)
484 size_t depth
= plist
->master
->trie_depth
;
485 uint8_t *bytes
= pentry
->prefix
.u
.val
;
486 size_t validbits
= pentry
->prefix
.prefixlen
;
487 struct pltrie_table
*table
;
490 while (validbits
> PLC_BITS
&& depth
> 1) {
491 if (!table
->entries
[*bytes
].next_table
)
492 table
->entries
[*bytes
].next_table
=
493 XCALLOC(MTYPE_PREFIX_LIST_TRIE
,
494 sizeof(struct pltrie_table
));
495 table
= table
->entries
[*bytes
].next_table
;
498 validbits
-= PLC_BITS
;
501 trie_walk_affected(validbits
, table
, *bytes
, pentry
, trie_install_fn
);
504 static void prefix_list_entry_add(struct prefix_list
*plist
,
505 struct prefix_list_entry
*pentry
)
507 struct prefix_list_entry
*replace
;
508 struct prefix_list_entry
*point
;
510 /* Automatic asignment of seq no. */
511 if (pentry
->seq
== -1)
512 pentry
->seq
= prefix_new_seq_get(plist
);
514 if (plist
->tail
&& pentry
->seq
> plist
->tail
->seq
)
517 /* Is there any same seq prefix list entry? */
518 replace
= prefix_seq_check(plist
, pentry
->seq
);
520 prefix_list_entry_delete(plist
, replace
, 0);
522 /* Check insert point. */
523 for (point
= plist
->head
; point
; point
= point
->next
)
524 if (point
->seq
>= pentry
->seq
)
528 /* In case of this is the first element of the list. */
529 pentry
->next
= point
;
533 point
->prev
->next
= pentry
;
535 plist
->head
= pentry
;
537 pentry
->prev
= point
->prev
;
538 point
->prev
= pentry
;
541 plist
->tail
->next
= pentry
;
543 plist
->head
= pentry
;
545 pentry
->prev
= plist
->tail
;
546 plist
->tail
= pentry
;
549 prefix_list_trie_add(plist
, pentry
);
551 /* Increment count. */
554 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
555 RMAP_EVENT_PLIST_ADDED
);
557 /* Run hook function. */
558 if (plist
->master
->add_hook
)
559 (*plist
->master
->add_hook
)(plist
);
561 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_ADDED
);
562 plist
->master
->recent
= plist
;
566 * Prefix list entry update start procedure:
567 * Remove entry from previosly installed master list, tries and notify
570 * \param[in] ple prefix list entry.
572 void prefix_list_entry_update_start(struct prefix_list_entry
*ple
)
574 struct prefix_list
*pl
= ple
->pl
;
576 /* Not installed, nothing to do. */
580 prefix_list_trie_del(pl
, ple
);
582 /* List manipulation: shameless copy from `prefix_list_entry_delete`. */
584 ple
->prev
->next
= ple
->next
;
586 pl
->head
= ple
->next
;
588 ple
->next
->prev
= ple
->prev
;
590 pl
->tail
= ple
->prev
;
592 route_map_notify_pentry_dependencies(pl
->name
, ple
,
593 RMAP_EVENT_PLIST_DELETED
);
596 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_DELETED
);
597 if (pl
->master
->delete_hook
)
598 (*pl
->master
->delete_hook
)(pl
);
600 if (pl
->head
|| pl
->tail
|| pl
->desc
)
601 pl
->master
->recent
= pl
;
603 ple
->next_best
= NULL
;
604 ple
->installed
= false;
608 * Prefix list entry update finish procedure:
609 * Add entry back master list, to the trie, notify observers and call master
612 * \param[in] ple prefix list entry.
614 void prefix_list_entry_update_finish(struct prefix_list_entry
*ple
)
616 struct prefix_list
*pl
= ple
->pl
;
617 struct prefix_list_entry
*point
;
619 /* Already installed, nothing to do. */
624 * Check if the entry is installable:
625 * We can only install entry if at least the prefix is provided (IPv4
628 if (ple
->prefix
.family
!= AF_INET
&& ple
->prefix
.family
!= AF_INET6
)
631 /* List manipulation: shameless copy from `prefix_list_entry_add`. */
632 if (pl
->tail
&& ple
->seq
> pl
->tail
->seq
)
635 /* Check insert point. */
636 for (point
= pl
->head
; point
; point
= point
->next
)
637 if (point
->seq
>= ple
->seq
)
641 /* In case of this is the first element of the list. */
646 point
->prev
->next
= ple
;
650 ple
->prev
= point
->prev
;
654 pl
->tail
->next
= ple
;
658 ple
->prev
= pl
->tail
;
662 prefix_list_trie_add(pl
, ple
);
665 route_map_notify_pentry_dependencies(pl
->name
, ple
,
666 RMAP_EVENT_PLIST_ADDED
);
668 /* Run hook function. */
669 if (pl
->master
->add_hook
)
670 (*pl
->master
->add_hook
)(pl
);
672 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_ADDED
);
673 pl
->master
->recent
= pl
;
675 ple
->installed
= true;
679 * Same as `prefix_list_entry_delete` but without `free()`ing the list if its
682 * \param[in] ple prefix list entry.
684 void prefix_list_entry_delete2(struct prefix_list_entry
*ple
)
686 /* Does the boiler plate list removal and entry removal notification. */
687 prefix_list_entry_update_start(ple
);
689 /* Effective `free()` memory. */
690 prefix_list_entry_free(ple
);
693 /* Return string of prefix_list_type. */
694 static const char *prefix_list_type_str(struct prefix_list_entry
*pentry
)
696 switch (pentry
->type
) {
706 static int prefix_list_entry_match(struct prefix_list_entry
*pentry
,
707 const struct prefix
*p
, bool address_mode
)
711 if (pentry
->prefix
.family
!= p
->family
)
714 ret
= prefix_match(&pentry
->prefix
, p
);
721 /* In case of le nor ge is specified, exact match is performed. */
722 if (!pentry
->le
&& !pentry
->ge
) {
723 if (pentry
->prefix
.prefixlen
!= p
->prefixlen
)
727 if (p
->prefixlen
> pentry
->le
)
731 if (p
->prefixlen
< pentry
->ge
)
737 enum prefix_list_type
prefix_list_apply_ext(
738 struct prefix_list
*plist
,
739 const struct prefix_list_entry
**which
,
740 union prefixconstptr object
,
743 struct prefix_list_entry
*pentry
, *pbest
= NULL
;
745 const struct prefix
*p
= object
.p
;
746 const uint8_t *byte
= p
->u
.val
;
748 size_t validbits
= p
->prefixlen
;
749 struct pltrie_table
*table
;
757 if (plist
->count
== 0) {
760 return PREFIX_PERMIT
;
763 depth
= plist
->master
->trie_depth
;
766 for (pentry
= table
->entries
[*byte
].up_chain
; pentry
;
767 pentry
= pentry
->next_best
) {
768 if (pbest
&& pbest
->seq
< pentry
->seq
)
770 if (prefix_list_entry_match(pentry
, p
, address_mode
))
774 if (validbits
<= PLC_BITS
)
776 validbits
-= PLC_BITS
;
779 if (!table
->entries
[*byte
].next_table
)
782 table
= table
->entries
[*byte
].next_table
;
787 for (pentry
= table
->entries
[*byte
].final_chain
; pentry
;
788 pentry
= pentry
->next_best
) {
789 if (pbest
&& pbest
->seq
< pentry
->seq
)
791 if (prefix_list_entry_match(pentry
, p
, address_mode
))
811 static void __attribute__((unused
)) prefix_list_print(struct prefix_list
*plist
)
813 struct prefix_list_entry
*pentry
;
818 printf("ip prefix-list %s: %d entries\n", plist
->name
, plist
->count
);
820 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
822 printf("any %s\n", prefix_list_type_str(pentry
));
828 printf(" seq %lld %s %pFX", (long long)pentry
->seq
,
829 prefix_list_type_str(pentry
), p
);
831 printf(" ge %d", pentry
->ge
);
833 printf(" le %d", pentry
->le
);
839 /* Return 1 when plist already include pentry policy. */
840 static struct prefix_list_entry
*
841 prefix_entry_dup_check(struct prefix_list
*plist
, struct prefix_list_entry
*new)
843 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
844 uint8_t byte
, *bytes
= new->prefix
.u
.val
;
845 size_t validbits
= new->prefix
.prefixlen
;
846 struct pltrie_table
*table
;
847 struct prefix_list_entry
*pentry
;
851 seq
= prefix_new_seq_get(plist
);
856 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
858 if (!table
->entries
[byte
].next_table
)
861 table
= table
->entries
[byte
].next_table
;
862 validbits
-= PLC_BITS
;
866 if (validbits
> PLC_BITS
)
867 pentry
= table
->entries
[byte
].final_chain
;
869 pentry
= table
->entries
[byte
].up_chain
;
871 for (; pentry
; pentry
= pentry
->next_best
) {
872 if (prefix_same(&pentry
->prefix
, &new->prefix
)
873 && pentry
->type
== new->type
&& pentry
->le
== new->le
874 && pentry
->ge
== new->ge
&& pentry
->seq
!= seq
)
889 static void vty_show_prefix_entry(struct vty
*vty
, json_object
*json
, afi_t afi
,
890 struct prefix_list
*plist
,
891 struct prefix_master
*master
,
892 enum display_type dtype
, int seqnum
)
894 struct prefix_list_entry
*pentry
;
895 json_object
*json_pl
= NULL
;
897 /* Print the name of the protocol */
899 json_pl
= json_object_new_object();
900 json_object_object_add(json
, plist
->name
, json_pl
);
902 vty_out(vty
, "%s: ", frr_protoname
);
904 if (dtype
== normal_display
) {
906 json_object_string_add(json_pl
, "addressFamily",
908 json_object_int_add(json_pl
, "entries", plist
->count
);
910 json_object_string_add(json_pl
, "description",
913 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
914 afi
== AFI_IP
? "" : "v6", plist
->name
,
917 vty_out(vty
, " Description: %s\n",
920 } else if (dtype
== summary_display
|| dtype
== detail_display
) {
922 json_object_string_add(json_pl
, "addressFamily",
925 json_object_string_add(json_pl
, "description",
927 json_object_int_add(json_pl
, "count", plist
->count
);
928 json_object_int_add(json_pl
, "rangeEntries",
930 json_object_int_add(json_pl
, "sequenceStart",
931 plist
->head
? plist
->head
->seq
: 0);
932 json_object_int_add(json_pl
, "sequenceEnd",
933 plist
->tail
? plist
->tail
->seq
: 0);
935 vty_out(vty
, "ip%s prefix-list %s:\n",
936 afi
== AFI_IP
? "" : "v6", plist
->name
);
939 vty_out(vty
, " Description: %s\n",
943 " count: %d, range entries: %d, sequences: %" PRId64
945 plist
->count
, plist
->rangecount
,
946 plist
->head
? plist
->head
->seq
: 0,
947 plist
->tail
? plist
->tail
->seq
: 0);
951 if (dtype
!= summary_display
) {
952 json_object
*json_entries
= NULL
;
955 json_entries
= json_object_new_array();
956 json_object_object_add(json_pl
, "entries",
960 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
961 if (dtype
== sequential_display
962 && pentry
->seq
!= seqnum
)
966 json_object
*json_entry
;
968 json_entry
= json_object_new_object();
969 json_object_array_add(json_entries
, json_entry
);
971 json_object_int_add(json_entry
,
974 json_object_string_add(
976 prefix_list_type_str(pentry
));
977 json_object_string_addf(json_entry
, "prefix",
984 "minimumPrefixLength",
989 "maximumPrefixLength",
992 if (dtype
== detail_display
993 || dtype
== sequential_display
) {
994 json_object_int_add(json_entry
,
997 json_object_int_add(json_entry
,
1004 vty_out(vty
, "seq %" PRId64
" ", pentry
->seq
);
1007 prefix_list_type_str(pentry
));
1010 vty_out(vty
, "any");
1012 struct prefix
*p
= &pentry
->prefix
;
1014 vty_out(vty
, "%pFX", p
);
1017 vty_out(vty
, " ge %d",
1020 vty_out(vty
, " le %d",
1024 if (dtype
== detail_display
1025 || dtype
== sequential_display
)
1027 " (hit count: %ld, refcount: %ld)",
1028 pentry
->hitcnt
, pentry
->refcnt
);
1036 static int vty_show_prefix_list(struct vty
*vty
, afi_t afi
, const char *name
,
1037 const char *seq
, enum display_type dtype
,
1040 struct prefix_list
*plist
;
1041 struct prefix_master
*master
;
1043 json_object
*json
= NULL
;
1044 json_object
*json_proto
= NULL
;
1046 master
= prefix_master_get(afi
, 0);
1051 json
= json_object_new_object();
1052 json_proto
= json_object_new_object();
1053 json_object_object_add(json
, frr_protoname
, json_proto
);
1057 seqnum
= (int64_t)atol(seq
);
1060 plist
= prefix_list_lookup(afi
, name
);
1064 "%% Can't find specified prefix-list\n");
1067 vty_show_prefix_entry(vty
, json_proto
, afi
, plist
, master
,
1070 if (dtype
== detail_display
|| dtype
== summary_display
) {
1071 if (master
->recent
&& !uj
)
1073 "Prefix-list with the last deletion/insertion: %s\n",
1074 master
->recent
->name
);
1077 frr_each (plist
, &master
->str
, plist
)
1078 vty_show_prefix_entry(vty
, json_proto
, afi
, plist
,
1079 master
, dtype
, seqnum
);
1082 return vty_json(vty
, json
);
1085 static int vty_show_prefix_list_prefix(struct vty
*vty
, afi_t afi
,
1086 const char *name
, const char *prefix
,
1087 enum display_type type
)
1089 struct prefix_list
*plist
;
1090 struct prefix_list_entry
*pentry
;
1095 plist
= prefix_list_lookup(afi
, name
);
1097 vty_out(vty
, "%% Can't find specified prefix-list\n");
1101 ret
= str2prefix(prefix
, &p
);
1103 vty_out(vty
, "%% prefix is malformed\n");
1107 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1110 if (type
== normal_display
|| type
== first_match_display
)
1111 if (prefix_same(&p
, &pentry
->prefix
))
1114 if (type
== longer_display
) {
1115 if ((p
.family
== pentry
->prefix
.family
)
1116 && (prefix_match(&p
, &pentry
->prefix
)))
1121 vty_out(vty
, " seq %" PRId64
" %s ", pentry
->seq
,
1122 prefix_list_type_str(pentry
));
1125 vty_out(vty
, "any");
1127 struct prefix
*pf
= &pentry
->prefix
;
1129 vty_out(vty
, "%pFX", pf
);
1132 vty_out(vty
, " ge %d", pentry
->ge
);
1134 vty_out(vty
, " le %d", pentry
->le
);
1137 if (type
== normal_display
1138 || type
== first_match_display
)
1139 vty_out(vty
, " (hit count: %ld, refcount: %ld)",
1140 pentry
->hitcnt
, pentry
->refcnt
);
1144 if (type
== first_match_display
)
1151 static int vty_clear_prefix_list(struct vty
*vty
, afi_t afi
, const char *name
,
1154 struct prefix_master
*master
;
1155 struct prefix_list
*plist
;
1156 struct prefix_list_entry
*pentry
;
1160 master
= prefix_master_get(afi
, 0);
1164 if (name
== NULL
&& prefix
== NULL
) {
1165 frr_each (plist
, &master
->str
, plist
)
1166 for (pentry
= plist
->head
; pentry
;
1167 pentry
= pentry
->next
)
1170 plist
= prefix_list_lookup(afi
, name
);
1172 vty_out(vty
, "%% Can't find specified prefix-list\n");
1177 ret
= str2prefix(prefix
, &p
);
1179 vty_out(vty
, "%% prefix is malformed\n");
1184 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1186 if (pentry
->prefix
.family
== p
.family
1187 && prefix_match(&pentry
->prefix
, &p
))
1196 #ifndef VTYSH_EXTRACT_PL
1197 #include "lib/plist_clippy.c"
1200 DEFPY (show_ip_prefix_list
,
1201 show_ip_prefix_list_cmd
,
1202 "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1206 "Name of a prefix list\n"
1207 "sequence number of an entry\n"
1211 enum display_type dtype
= normal_display
;
1213 dtype
= sequential_display
;
1215 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, arg_str
, dtype
,
1219 DEFPY (show_ip_prefix_list_prefix
,
1220 show_ip_prefix_list_prefix_cmd
,
1221 "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]",
1225 "Name of a prefix list\n"
1226 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n"
1227 "Lookup longer prefix\n"
1228 "First matched prefix\n")
1230 enum display_type dtype
= normal_display
;
1232 dtype
= longer_display
;
1234 dtype
= first_match_display
;
1236 return vty_show_prefix_list_prefix(vty
, AFI_IP
, prefix_list
, prefix_str
,
1240 DEFPY (show_ip_prefix_list_summary
,
1241 show_ip_prefix_list_summary_cmd
,
1242 "show ip prefix-list summary [WORD$prefix_list] [json$uj]",
1246 "Summary of prefix lists\n"
1247 "Name of a prefix list\n"
1250 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1251 summary_display
, !!uj
);
1254 DEFPY (show_ip_prefix_list_detail
,
1255 show_ip_prefix_list_detail_cmd
,
1256 "show ip prefix-list detail [WORD$prefix_list] [json$uj]",
1260 "Detail of prefix lists\n"
1261 "Name of a prefix list\n"
1264 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1265 detail_display
, !!uj
);
1268 DEFPY (clear_ip_prefix_list
,
1269 clear_ip_prefix_list_cmd
,
1270 "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]",
1274 "Name of a prefix list\n"
1275 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n")
1277 return vty_clear_prefix_list(vty
, AFI_IP
, prefix_list
, prefix_str
);
1280 DEFPY (show_ipv6_prefix_list
,
1281 show_ipv6_prefix_list_cmd
,
1282 "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1286 "Name of a prefix list\n"
1287 "sequence number of an entry\n"
1291 enum display_type dtype
= normal_display
;
1293 dtype
= sequential_display
;
1295 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, arg_str
, dtype
,
1299 DEFPY (show_ipv6_prefix_list_prefix
,
1300 show_ipv6_prefix_list_prefix_cmd
,
1301 "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]",
1305 "Name of a prefix list\n"
1306 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n"
1307 "Lookup longer prefix\n"
1308 "First matched prefix\n")
1310 enum display_type dtype
= normal_display
;
1312 dtype
= longer_display
;
1314 dtype
= first_match_display
;
1316 return vty_show_prefix_list_prefix(vty
, AFI_IP6
, prefix_list
,
1320 DEFPY (show_ipv6_prefix_list_summary
,
1321 show_ipv6_prefix_list_summary_cmd
,
1322 "show ipv6 prefix-list summary [WORD$prefix-list] [json$uj]",
1326 "Summary of prefix lists\n"
1327 "Name of a prefix list\n"
1330 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1331 summary_display
, !!uj
);
1334 DEFPY (show_ipv6_prefix_list_detail
,
1335 show_ipv6_prefix_list_detail_cmd
,
1336 "show ipv6 prefix-list detail [WORD$prefix-list] [json$uj]",
1340 "Detail of prefix lists\n"
1341 "Name of a prefix list\n"
1344 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1345 detail_display
, !!uj
);
1348 DEFPY (clear_ipv6_prefix_list
,
1349 clear_ipv6_prefix_list_cmd
,
1350 "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]",
1354 "Name of a prefix list\n"
1355 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n")
1357 return vty_clear_prefix_list(vty
, AFI_IP6
, prefix_list
, prefix_str
);
1360 DEFPY (debug_prefix_list_match
,
1361 debug_prefix_list_match_cmd
,
1362 "debug prefix-list WORD$prefix-list match <A.B.C.D/M|X:X::X:X/M>"
1363 " [address-mode$addr_mode]",
1365 "Prefix-list test access\n"
1366 "Name of a prefix list\n"
1367 "Test prefix for prefix list result\n"
1368 "Prefix to test in ip prefix-list\n"
1369 "Prefix to test in ipv6 prefix-list\n"
1370 "Use address matching mode (PIM RP)\n")
1372 struct prefix_list
*plist
;
1373 const struct prefix_list_entry
*entry
= NULL
;
1374 enum prefix_list_type ret
;
1376 plist
= prefix_list_lookup(family2afi(match
->family
), prefix_list
);
1378 vty_out(vty
, "%% no prefix list named %s for AFI %s\n",
1379 prefix_list
, afi2str(family2afi(match
->family
)));
1383 ret
= prefix_list_apply_ext(plist
, &entry
, match
, !!addr_mode
);
1385 vty_out(vty
, "%s prefix list %s yields %s for %pFX, ",
1386 afi2str(family2afi(match
->family
)), prefix_list
,
1387 ret
== PREFIX_DENY
? "DENY" : "PERMIT", match
);
1390 vty_out(vty
, "no match found\n");
1392 vty_out(vty
, "matching entry #%"PRId64
": %pFX", entry
->seq
,
1395 vty_out(vty
, " ge %d", entry
->ge
);
1397 vty_out(vty
, " le %d", entry
->le
);
1401 /* allow using this in scripts for quick prefix-list member tests */
1402 return (ret
== PREFIX_PERMIT
) ? CMD_SUCCESS
: CMD_WARNING
;
1405 struct stream
*prefix_bgp_orf_entry(struct stream
*s
, struct prefix_list
*plist
,
1406 uint8_t init_flag
, uint8_t permit_flag
,
1409 struct prefix_list_entry
*pentry
;
1414 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1415 uint8_t flag
= init_flag
;
1416 struct prefix
*p
= &pentry
->prefix
;
1418 flag
|= (pentry
->type
== PREFIX_PERMIT
? permit_flag
1420 stream_putc(s
, flag
);
1421 stream_putl(s
, (uint32_t)pentry
->seq
);
1422 stream_putc(s
, (uint8_t)pentry
->ge
);
1423 stream_putc(s
, (uint8_t)pentry
->le
);
1424 stream_put_prefix(s
, p
);
1430 int prefix_bgp_orf_set(char *name
, afi_t afi
, struct orf_prefix
*orfp
,
1431 int permit
, int set
)
1433 struct prefix_list
*plist
;
1434 struct prefix_list_entry
*pentry
;
1436 /* ge and le value check */
1437 if (orfp
->ge
&& orfp
->ge
< orfp
->p
.prefixlen
)
1438 return CMD_WARNING_CONFIG_FAILED
;
1439 if (orfp
->le
&& orfp
->le
< orfp
->p
.prefixlen
)
1440 return CMD_WARNING_CONFIG_FAILED
;
1441 if (orfp
->le
&& orfp
->ge
> orfp
->le
)
1442 return CMD_WARNING_CONFIG_FAILED
;
1444 if (orfp
->ge
&& orfp
->le
== (afi
== AFI_IP
? 32 : 128))
1447 plist
= prefix_list_get(afi
, 1, name
);
1449 return CMD_WARNING_CONFIG_FAILED
;
1451 apply_mask(&orfp
->p
);
1454 pentry
= prefix_list_entry_make(
1455 &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1456 orfp
->seq
, orfp
->le
, orfp
->ge
, false);
1458 if (prefix_entry_dup_check(plist
, pentry
)) {
1459 prefix_list_entry_free(pentry
);
1460 return CMD_WARNING_CONFIG_FAILED
;
1463 prefix_list_entry_add(plist
, pentry
);
1465 pentry
= prefix_list_entry_lookup(
1466 plist
, &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1467 orfp
->seq
, orfp
->le
, orfp
->ge
);
1470 return CMD_WARNING_CONFIG_FAILED
;
1472 prefix_list_entry_delete(plist
, pentry
, 1);
1478 void prefix_bgp_orf_remove_all(afi_t afi
, char *name
)
1480 struct prefix_list
*plist
;
1482 plist
= prefix_bgp_orf_lookup(afi
, name
);
1484 prefix_list_delete(plist
);
1487 /* return prefix count */
1488 int prefix_bgp_show_prefix_list(struct vty
*vty
, afi_t afi
, char *name
,
1491 struct prefix_list
*plist
;
1492 struct prefix_list_entry
*pentry
;
1493 json_object
*json
= NULL
;
1494 json_object
*json_prefix
= NULL
;
1495 json_object
*json_list
= NULL
;
1497 plist
= prefix_bgp_orf_lookup(afi
, name
);
1502 return plist
->count
;
1505 json
= json_object_new_object();
1506 json_prefix
= json_object_new_object();
1507 json_list
= json_object_new_object();
1509 json_object_int_add(json_prefix
, "prefixListCounter",
1511 json_object_string_add(json_prefix
, "prefixListName",
1514 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1515 struct prefix
*p
= &pentry
->prefix
;
1518 snprintf(buf_a
, sizeof(buf_a
), "%pFX", p
);
1520 json_object_int_add(json_list
, "seq", pentry
->seq
);
1521 json_object_string_add(json_list
, "seqPrefixListType",
1522 prefix_list_type_str(pentry
));
1525 json_object_int_add(json_list
, "ge",
1528 json_object_int_add(json_list
, "le",
1531 json_object_object_add(json_prefix
, buf_a
, json_list
);
1534 json_object_object_add(json
, "ipPrefixList",
1537 json_object_object_add(json
, "ipv6PrefixList",
1540 vty_json(vty
, json
);
1542 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
1543 afi
== AFI_IP
? "" : "v6", plist
->name
, plist
->count
);
1545 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1546 struct prefix
*p
= &pentry
->prefix
;
1548 vty_out(vty
, " seq %" PRId64
" %s %pFX", pentry
->seq
,
1549 prefix_list_type_str(pentry
), p
);
1552 vty_out(vty
, " ge %d", pentry
->ge
);
1554 vty_out(vty
, " le %d", pentry
->le
);
1559 return plist
->count
;
1562 static void prefix_list_reset_afi(afi_t afi
, int orf
)
1564 struct prefix_list
*plist
;
1565 struct prefix_master
*master
;
1567 master
= prefix_master_get(afi
, orf
);
1571 while ((plist
= plist_pop(&master
->str
)))
1572 prefix_list_delete(plist
);
1574 master
->recent
= NULL
;
1577 /* Prefix-list node. */
1578 static struct cmd_node prefix_node
= {
1579 .name
= "ipv4 prefix list",
1580 .node
= PREFIX_NODE
,
1584 static void plist_autocomplete_afi(afi_t afi
, vector comps
,
1585 struct cmd_token
*token
)
1587 struct prefix_list
*plist
;
1588 struct prefix_master
*master
;
1590 master
= prefix_master_get(afi
, 0);
1594 frr_each (plist
, &master
->str
, plist
)
1595 vector_set(comps
, XSTRDUP(MTYPE_COMPLETION
, plist
->name
));
1598 static void plist_autocomplete(vector comps
, struct cmd_token
*token
)
1600 plist_autocomplete_afi(AFI_IP
, comps
, token
);
1601 plist_autocomplete_afi(AFI_IP6
, comps
, token
);
1604 static const struct cmd_variable_handler plist_var_handlers
[] = {
1605 {/* "prefix-list WORD" */
1606 .varname
= "prefix_list",
1607 .completions
= plist_autocomplete
},
1608 {.tokenname
= "PREFIXLIST_NAME",
1609 .completions
= plist_autocomplete
},
1610 {.completions
= NULL
}};
1613 static void prefix_list_init_ipv4(void)
1615 install_node(&prefix_node
);
1617 install_element(VIEW_NODE
, &show_ip_prefix_list_cmd
);
1618 install_element(VIEW_NODE
, &show_ip_prefix_list_prefix_cmd
);
1619 install_element(VIEW_NODE
, &show_ip_prefix_list_summary_cmd
);
1620 install_element(VIEW_NODE
, &show_ip_prefix_list_detail_cmd
);
1622 install_element(ENABLE_NODE
, &clear_ip_prefix_list_cmd
);
1625 /* Prefix-list node. */
1626 static struct cmd_node prefix_ipv6_node
= {
1627 .name
= "ipv6 prefix list",
1628 .node
= PREFIX_IPV6_NODE
,
1632 static void prefix_list_init_ipv6(void)
1634 install_node(&prefix_ipv6_node
);
1636 install_element(VIEW_NODE
, &show_ipv6_prefix_list_cmd
);
1637 install_element(VIEW_NODE
, &show_ipv6_prefix_list_prefix_cmd
);
1638 install_element(VIEW_NODE
, &show_ipv6_prefix_list_summary_cmd
);
1639 install_element(VIEW_NODE
, &show_ipv6_prefix_list_detail_cmd
);
1640 install_element(VIEW_NODE
, &debug_prefix_list_match_cmd
);
1642 install_element(ENABLE_NODE
, &clear_ipv6_prefix_list_cmd
);
1645 void prefix_list_init(void)
1647 plist_init(&prefix_master_ipv4
.str
);
1648 plist_init(&prefix_master_orf_v4
.str
);
1649 plist_init(&prefix_master_ipv6
.str
);
1650 plist_init(&prefix_master_orf_v6
.str
);
1652 cmd_variable_handler_register(plist_var_handlers
);
1654 prefix_list_init_ipv4();
1655 prefix_list_init_ipv6();
1658 void prefix_list_reset(void)
1660 prefix_list_reset_afi(AFI_IP
, 0);
1661 prefix_list_reset_afi(AFI_IP6
, 0);
1662 prefix_list_reset_afi(AFI_IP
, 1);
1663 prefix_list_reset_afi(AFI_IP6
, 1);