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"
34 #include "plist_int.h"
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");
41 /* not currently changeable, code assumes bytes further down */
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) */
50 struct pltrie_table
*next_table
;
51 struct prefix_list_entry
*final_chain
;
54 struct prefix_list_entry
*up_chain
;
58 struct pltrie_entry entries
[PLC_LEN
];
61 /* List of struct prefix_list. */
62 struct prefix_list_list
{
63 struct prefix_list
*head
;
64 struct prefix_list
*tail
;
67 /* Master structure of prefix_list. */
68 struct prefix_master
{
69 /* List of prefix_list which name is string. */
70 struct prefix_list_list str
;
72 /* The latest update. */
73 struct prefix_list
*recent
;
75 /* Hook function which is executed when new prefix_list is added. */
76 void (*add_hook
)(struct prefix_list
*);
78 /* Hook function which is executed when prefix_list is deleted. */
79 void (*delete_hook
)(struct prefix_list
*);
81 /* number of bytes that have a trie level */
85 /* Static structure of IPv4 prefix_list's master. */
86 static struct prefix_master prefix_master_ipv4
= {
87 {NULL
, NULL
}, NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
90 /* Static structure of IPv6 prefix-list's master. */
91 static struct prefix_master prefix_master_ipv6
= {
92 {NULL
, NULL
}, NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
95 /* Static structure of BGP ORF prefix_list's master. */
96 static struct prefix_master prefix_master_orf_v4
= {
97 {NULL
, NULL
}, NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
100 /* Static structure of BGP ORF prefix_list's master. */
101 static struct prefix_master prefix_master_orf_v6
= {
102 {NULL
, NULL
}, NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
105 static struct prefix_master
*prefix_master_get(afi_t afi
, int orf
)
108 return orf
? &prefix_master_orf_v4
: &prefix_master_ipv4
;
110 return orf
? &prefix_master_orf_v6
: &prefix_master_ipv6
;
114 const char *prefix_list_name(struct prefix_list
*plist
)
119 afi_t
prefix_list_afi(struct prefix_list
*plist
)
121 if (plist
->master
== &prefix_master_ipv4
122 || plist
->master
== &prefix_master_orf_v4
)
127 /* Lookup prefix_list from list of prefix_list by name. */
128 static struct prefix_list
*prefix_list_lookup_do(afi_t afi
, int orf
,
131 struct prefix_list
*plist
;
132 struct prefix_master
*master
;
137 master
= prefix_master_get(afi
, orf
);
141 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
142 if (strcmp(plist
->name
, name
) == 0)
148 struct prefix_list
*prefix_list_lookup(afi_t afi
, const char *name
)
150 return prefix_list_lookup_do(afi
, 0, name
);
153 struct prefix_list
*prefix_bgp_orf_lookup(afi_t afi
, const char *name
)
155 return prefix_list_lookup_do(afi
, 1, name
);
158 static struct prefix_list
*prefix_list_new(void)
160 struct prefix_list
*new;
162 new = XCALLOC(MTYPE_PREFIX_LIST
, sizeof(struct prefix_list
));
166 static void prefix_list_free(struct prefix_list
*plist
)
168 XFREE(MTYPE_PREFIX_LIST
, plist
);
171 struct prefix_list_entry
*prefix_list_entry_new(void)
173 struct prefix_list_entry
*new;
175 new = XCALLOC(MTYPE_PREFIX_LIST_ENTRY
,
176 sizeof(struct prefix_list_entry
));
180 void prefix_list_entry_free(struct prefix_list_entry
*pentry
)
182 XFREE(MTYPE_PREFIX_LIST_ENTRY
, pentry
);
185 /* Insert new prefix list to list of prefix_list. Each prefix_list
186 is sorted by the name. */
187 static struct prefix_list
*prefix_list_insert(afi_t afi
, int orf
,
190 struct prefix_list
*plist
;
191 struct prefix_list
*point
;
192 struct prefix_list_list
*list
;
193 struct prefix_master
*master
;
195 master
= prefix_master_get(afi
, orf
);
199 /* Allocate new prefix_list and copy given name. */
200 plist
= prefix_list_new();
201 plist
->name
= XSTRDUP(MTYPE_MPREFIX_LIST_STR
, name
);
202 plist
->master
= master
;
204 XCALLOC(MTYPE_PREFIX_LIST_TRIE
, sizeof(struct pltrie_table
));
206 /* Set prefix_list to string list. */
209 /* Set point to insertion point. */
210 for (point
= list
->head
; point
; point
= point
->next
)
211 if (strcmp(point
->name
, name
) >= 0)
214 /* In case of this is the first element of master. */
215 if (list
->head
== NULL
) {
216 list
->head
= list
->tail
= plist
;
220 /* In case of insertion is made at the tail of access_list. */
222 plist
->prev
= list
->tail
;
223 list
->tail
->next
= plist
;
228 /* In case of insertion is made at the head of access_list. */
229 if (point
== list
->head
) {
230 plist
->next
= list
->head
;
231 list
->head
->prev
= plist
;
236 /* Insertion is made at middle of the access_list. */
238 plist
->prev
= point
->prev
;
241 point
->prev
->next
= plist
;
247 struct prefix_list
*prefix_list_get(afi_t afi
, int orf
, const char *name
)
249 struct prefix_list
*plist
;
251 plist
= prefix_list_lookup_do(afi
, orf
, name
);
254 plist
= prefix_list_insert(afi
, orf
, name
);
258 static void prefix_list_trie_del(struct prefix_list
*plist
,
259 struct prefix_list_entry
*pentry
);
261 /* Delete prefix-list from prefix_list_master and free it. */
262 void prefix_list_delete(struct prefix_list
*plist
)
264 struct prefix_list_list
*list
;
265 struct prefix_master
*master
;
266 struct prefix_list_entry
*pentry
;
267 struct prefix_list_entry
*next
;
269 /* If prefix-list contain prefix_list_entry free all of it. */
270 for (pentry
= plist
->head
; pentry
; pentry
= next
) {
271 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
272 RMAP_EVENT_PLIST_DELETED
);
274 prefix_list_trie_del(plist
, pentry
);
275 prefix_list_entry_free(pentry
);
279 master
= plist
->master
;
284 plist
->next
->prev
= plist
->prev
;
286 list
->tail
= plist
->prev
;
289 plist
->prev
->next
= plist
->next
;
291 list
->head
= plist
->next
;
293 XFREE(MTYPE_TMP
, plist
->desc
);
295 /* Make sure master's recent changed prefix-list information is
297 master
->recent
= NULL
;
299 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_DELETED
);
301 if (master
->delete_hook
)
302 (*master
->delete_hook
)(plist
);
304 XFREE(MTYPE_MPREFIX_LIST_STR
, plist
->name
);
306 XFREE(MTYPE_PREFIX_LIST_TRIE
, plist
->trie
);
308 prefix_list_free(plist
);
311 static struct prefix_list_entry
*
312 prefix_list_entry_make(struct prefix
*prefix
, enum prefix_list_type type
,
313 int64_t seq
, int le
, int ge
, bool any
)
315 struct prefix_list_entry
*pentry
;
317 pentry
= prefix_list_entry_new();
322 prefix_copy(&pentry
->prefix
, prefix
);
331 /* Add hook function. */
332 void prefix_list_add_hook(void (*func
)(struct prefix_list
*plist
))
334 prefix_master_ipv4
.add_hook
= func
;
335 prefix_master_ipv6
.add_hook
= func
;
338 /* Delete hook function. */
339 void prefix_list_delete_hook(void (*func
)(struct prefix_list
*plist
))
341 prefix_master_ipv4
.delete_hook
= func
;
342 prefix_master_ipv6
.delete_hook
= func
;
345 /* Calculate new sequential number. */
346 int64_t prefix_new_seq_get(struct prefix_list
*plist
)
350 struct prefix_list_entry
*pentry
;
354 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
355 if (maxseq
< pentry
->seq
)
356 maxseq
= pentry
->seq
;
359 newseq
= ((maxseq
/ 5) * 5) + 5;
361 return (newseq
> UINT_MAX
) ? UINT_MAX
: newseq
;
364 /* Return prefix list entry which has same seq number. */
365 static struct prefix_list_entry
*prefix_seq_check(struct prefix_list
*plist
,
368 struct prefix_list_entry
*pentry
;
370 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
371 if (pentry
->seq
== seq
)
376 struct prefix_list_entry
*
377 prefix_list_entry_lookup(struct prefix_list
*plist
, struct prefix
*prefix
,
378 enum prefix_list_type type
, int64_t seq
,
381 struct prefix_list_entry
*pentry
;
383 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
384 if (prefix_same(&pentry
->prefix
, prefix
)
385 && pentry
->type
== type
) {
386 if (seq
>= 0 && pentry
->seq
!= seq
)
389 if (pentry
->le
!= le
)
391 if (pentry
->ge
!= ge
)
400 static void trie_walk_affected(size_t validbits
, struct pltrie_table
*table
,
401 uint8_t byte
, struct prefix_list_entry
*object
,
402 void (*fn
)(struct prefix_list_entry
*object
,
403 struct prefix_list_entry
**updptr
))
408 if (validbits
> PLC_BITS
) {
409 fn(object
, &table
->entries
[byte
].final_chain
);
413 mask
= (1 << (8 - validbits
)) - 1;
414 for (bwalk
= byte
& ~mask
; bwalk
<= byte
+ mask
; bwalk
++) {
415 fn(object
, &table
->entries
[bwalk
].up_chain
);
419 static void trie_uninstall_fn(struct prefix_list_entry
*object
,
420 struct prefix_list_entry
**updptr
)
422 for (; *updptr
; updptr
= &(*updptr
)->next_best
)
423 if (*updptr
== object
) {
424 *updptr
= object
->next_best
;
429 static int trie_table_empty(struct pltrie_table
*table
)
432 for (i
= 0; i
< PLC_LEN
; i
++)
433 if (table
->entries
[i
].next_table
|| table
->entries
[i
].up_chain
)
438 static void prefix_list_trie_del(struct prefix_list
*plist
,
439 struct prefix_list_entry
*pentry
)
441 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
442 uint8_t *bytes
= pentry
->prefix
.u
.val
;
443 size_t validbits
= pentry
->prefix
.prefixlen
;
444 struct pltrie_table
*table
, **tables
[PLC_MAXLEVEL
];
447 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
448 uint8_t byte
= bytes
[depth
];
449 assert(table
->entries
[byte
].next_table
);
451 tables
[depth
+ 1] = &table
->entries
[byte
].next_table
;
452 table
= table
->entries
[byte
].next_table
;
454 validbits
-= PLC_BITS
;
457 trie_walk_affected(validbits
, table
, bytes
[depth
], pentry
,
460 for (; depth
> 0; depth
--)
461 if (trie_table_empty(*tables
[depth
])) {
462 XFREE(MTYPE_PREFIX_LIST_TRIE
, *tables
[depth
]);
467 void prefix_list_entry_delete(struct prefix_list
*plist
,
468 struct prefix_list_entry
*pentry
,
471 if (plist
== NULL
|| pentry
== NULL
)
474 prefix_list_trie_del(plist
, pentry
);
477 pentry
->prev
->next
= pentry
->next
;
479 plist
->head
= pentry
->next
;
481 pentry
->next
->prev
= pentry
->prev
;
483 plist
->tail
= pentry
->prev
;
485 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
486 RMAP_EVENT_PLIST_DELETED
);
487 prefix_list_entry_free(pentry
);
492 route_map_notify_dependencies(plist
->name
,
493 RMAP_EVENT_PLIST_DELETED
);
494 if (plist
->master
->delete_hook
)
495 (*plist
->master
->delete_hook
)(plist
);
497 if (plist
->head
== NULL
&& plist
->tail
== NULL
498 && plist
->desc
== NULL
)
499 prefix_list_delete(plist
);
501 plist
->master
->recent
= plist
;
505 static void trie_install_fn(struct prefix_list_entry
*object
,
506 struct prefix_list_entry
**updptr
)
509 if (*updptr
== object
)
511 if ((*updptr
)->prefix
.prefixlen
< object
->prefix
.prefixlen
)
513 if ((*updptr
)->prefix
.prefixlen
== object
->prefix
.prefixlen
514 && (*updptr
)->seq
> object
->seq
)
516 updptr
= &(*updptr
)->next_best
;
519 if (!object
->next_best
)
520 object
->next_best
= *updptr
;
522 assert(object
->next_best
== *updptr
|| !*updptr
);
527 static void prefix_list_trie_add(struct prefix_list
*plist
,
528 struct prefix_list_entry
*pentry
)
530 size_t depth
= plist
->master
->trie_depth
;
531 uint8_t *bytes
= pentry
->prefix
.u
.val
;
532 size_t validbits
= pentry
->prefix
.prefixlen
;
533 struct pltrie_table
*table
;
536 while (validbits
> PLC_BITS
&& depth
> 1) {
537 if (!table
->entries
[*bytes
].next_table
)
538 table
->entries
[*bytes
].next_table
=
539 XCALLOC(MTYPE_PREFIX_LIST_TRIE
,
540 sizeof(struct pltrie_table
));
541 table
= table
->entries
[*bytes
].next_table
;
544 validbits
-= PLC_BITS
;
547 trie_walk_affected(validbits
, table
, *bytes
, pentry
, trie_install_fn
);
550 static void prefix_list_entry_add(struct prefix_list
*plist
,
551 struct prefix_list_entry
*pentry
)
553 struct prefix_list_entry
*replace
;
554 struct prefix_list_entry
*point
;
556 /* Automatic asignment of seq no. */
557 if (pentry
->seq
== -1)
558 pentry
->seq
= prefix_new_seq_get(plist
);
560 if (plist
->tail
&& pentry
->seq
> plist
->tail
->seq
)
563 /* Is there any same seq prefix list entry? */
564 replace
= prefix_seq_check(plist
, pentry
->seq
);
566 prefix_list_entry_delete(plist
, replace
, 0);
568 /* Check insert point. */
569 for (point
= plist
->head
; point
; point
= point
->next
)
570 if (point
->seq
>= pentry
->seq
)
574 /* In case of this is the first element of the list. */
575 pentry
->next
= point
;
579 point
->prev
->next
= pentry
;
581 plist
->head
= pentry
;
583 pentry
->prev
= point
->prev
;
584 point
->prev
= pentry
;
587 plist
->tail
->next
= pentry
;
589 plist
->head
= pentry
;
591 pentry
->prev
= plist
->tail
;
592 plist
->tail
= pentry
;
595 prefix_list_trie_add(plist
, pentry
);
597 /* Increment count. */
600 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
601 RMAP_EVENT_PLIST_ADDED
);
603 /* Run hook function. */
604 if (plist
->master
->add_hook
)
605 (*plist
->master
->add_hook
)(plist
);
607 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_ADDED
);
608 plist
->master
->recent
= plist
;
612 * Prefix list entry update start procedure:
613 * Remove entry from previosly installed master list, tries and notify
616 * \param[in] ple prefix list entry.
618 void prefix_list_entry_update_start(struct prefix_list_entry
*ple
)
620 struct prefix_list
*pl
= ple
->pl
;
622 /* Not installed, nothing to do. */
626 prefix_list_trie_del(pl
, ple
);
628 /* List manipulation: shameless copy from `prefix_list_entry_delete`. */
630 ple
->prev
->next
= ple
->next
;
632 pl
->head
= ple
->next
;
634 ple
->next
->prev
= ple
->prev
;
636 pl
->tail
= ple
->prev
;
638 route_map_notify_pentry_dependencies(pl
->name
, ple
,
639 RMAP_EVENT_PLIST_DELETED
);
642 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_DELETED
);
643 if (pl
->master
->delete_hook
)
644 (*pl
->master
->delete_hook
)(pl
);
646 if (pl
->head
|| pl
->tail
|| pl
->desc
)
647 pl
->master
->recent
= pl
;
649 ple
->next_best
= NULL
;
650 ple
->installed
= false;
654 * Prefix list entry update finish procedure:
655 * Add entry back master list, to the trie, notify observers and call master
658 * \param[in] ple prefix list entry.
660 void prefix_list_entry_update_finish(struct prefix_list_entry
*ple
)
662 struct prefix_list
*pl
= ple
->pl
;
663 struct prefix_list_entry
*point
;
665 /* Already installed, nothing to do. */
670 * Check if the entry is installable:
671 * We can only install entry if at least the prefix is provided (IPv4
674 if (ple
->prefix
.family
!= AF_INET
&& ple
->prefix
.family
!= AF_INET6
)
677 /* List manipulation: shameless copy from `prefix_list_entry_add`. */
678 if (pl
->tail
&& ple
->seq
> pl
->tail
->seq
)
681 /* Check insert point. */
682 for (point
= pl
->head
; point
; point
= point
->next
)
683 if (point
->seq
>= ple
->seq
)
687 /* In case of this is the first element of the list. */
692 point
->prev
->next
= ple
;
696 ple
->prev
= point
->prev
;
700 pl
->tail
->next
= ple
;
704 ple
->prev
= pl
->tail
;
708 prefix_list_trie_add(pl
, ple
);
711 route_map_notify_pentry_dependencies(pl
->name
, ple
,
712 RMAP_EVENT_PLIST_ADDED
);
714 /* Run hook function. */
715 if (pl
->master
->add_hook
)
716 (*pl
->master
->add_hook
)(pl
);
718 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_ADDED
);
719 pl
->master
->recent
= pl
;
721 ple
->installed
= true;
725 * Same as `prefix_list_entry_delete` but without `free()`ing the list if its
728 * \param[in] ple prefix list entry.
730 void prefix_list_entry_delete2(struct prefix_list_entry
*ple
)
732 /* Does the boiler plate list removal and entry removal notification. */
733 prefix_list_entry_update_start(ple
);
735 /* Effective `free()` memory. */
736 prefix_list_entry_free(ple
);
739 /* Return string of prefix_list_type. */
740 static const char *prefix_list_type_str(struct prefix_list_entry
*pentry
)
742 switch (pentry
->type
) {
752 static int prefix_list_entry_match(struct prefix_list_entry
*pentry
,
753 const struct prefix
*p
, bool address_mode
)
757 if (pentry
->prefix
.family
!= p
->family
)
760 ret
= prefix_match(&pentry
->prefix
, p
);
767 /* In case of le nor ge is specified, exact match is performed. */
768 if (!pentry
->le
&& !pentry
->ge
) {
769 if (pentry
->prefix
.prefixlen
!= p
->prefixlen
)
773 if (p
->prefixlen
> pentry
->le
)
777 if (p
->prefixlen
< pentry
->ge
)
783 enum prefix_list_type
prefix_list_apply_ext(
784 struct prefix_list
*plist
,
785 const struct prefix_list_entry
**which
,
786 union prefixconstptr object
,
789 struct prefix_list_entry
*pentry
, *pbest
= NULL
;
791 const struct prefix
*p
= object
.p
;
792 const uint8_t *byte
= p
->u
.val
;
794 size_t validbits
= p
->prefixlen
;
795 struct pltrie_table
*table
;
803 if (plist
->count
== 0) {
806 return PREFIX_PERMIT
;
809 depth
= plist
->master
->trie_depth
;
812 for (pentry
= table
->entries
[*byte
].up_chain
; pentry
;
813 pentry
= pentry
->next_best
) {
814 if (pbest
&& pbest
->seq
< pentry
->seq
)
816 if (prefix_list_entry_match(pentry
, p
, address_mode
))
820 if (validbits
<= PLC_BITS
)
822 validbits
-= PLC_BITS
;
825 if (!table
->entries
[*byte
].next_table
)
828 table
= table
->entries
[*byte
].next_table
;
833 for (pentry
= table
->entries
[*byte
].final_chain
; pentry
;
834 pentry
= pentry
->next_best
) {
835 if (pbest
&& pbest
->seq
< pentry
->seq
)
837 if (prefix_list_entry_match(pentry
, p
, address_mode
))
857 static void __attribute__((unused
)) prefix_list_print(struct prefix_list
*plist
)
859 struct prefix_list_entry
*pentry
;
864 printf("ip prefix-list %s: %d entries\n", plist
->name
, plist
->count
);
866 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
868 printf("any %s\n", prefix_list_type_str(pentry
));
874 printf(" seq %lld %s %pFX", (long long)pentry
->seq
,
875 prefix_list_type_str(pentry
), p
);
877 printf(" ge %d", pentry
->ge
);
879 printf(" le %d", pentry
->le
);
885 /* Return 1 when plist already include pentry policy. */
886 static struct prefix_list_entry
*
887 prefix_entry_dup_check(struct prefix_list
*plist
, struct prefix_list_entry
*new)
889 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
890 uint8_t byte
, *bytes
= new->prefix
.u
.val
;
891 size_t validbits
= new->prefix
.prefixlen
;
892 struct pltrie_table
*table
;
893 struct prefix_list_entry
*pentry
;
897 seq
= prefix_new_seq_get(plist
);
902 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
904 if (!table
->entries
[byte
].next_table
)
907 table
= table
->entries
[byte
].next_table
;
908 validbits
-= PLC_BITS
;
912 if (validbits
> PLC_BITS
)
913 pentry
= table
->entries
[byte
].final_chain
;
915 pentry
= table
->entries
[byte
].up_chain
;
917 for (; pentry
; pentry
= pentry
->next_best
) {
918 if (prefix_same(&pentry
->prefix
, &new->prefix
)
919 && pentry
->type
== new->type
&& pentry
->le
== new->le
920 && pentry
->ge
== new->ge
&& pentry
->seq
!= seq
)
935 static void vty_show_prefix_entry(struct vty
*vty
, json_object
*json
, afi_t afi
,
936 struct prefix_list
*plist
,
937 struct prefix_master
*master
,
938 enum display_type dtype
, int seqnum
)
940 struct prefix_list_entry
*pentry
;
941 json_object
*json_pl
= NULL
;
943 /* Print the name of the protocol */
945 json_pl
= json_object_new_object();
946 json_object_object_add(json
, plist
->name
, json_pl
);
948 vty_out(vty
, "%s: ", frr_protoname
);
950 if (dtype
== normal_display
) {
952 json_object_string_add(json_pl
, "addressFamily",
954 json_object_int_add(json_pl
, "entries", plist
->count
);
956 json_object_string_add(json_pl
, "description",
959 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
960 afi
== AFI_IP
? "" : "v6", plist
->name
,
963 vty_out(vty
, " Description: %s\n",
966 } else if (dtype
== summary_display
|| dtype
== detail_display
) {
968 json_object_string_add(json_pl
, "addressFamily",
971 json_object_string_add(json_pl
, "description",
973 json_object_int_add(json_pl
, "count", plist
->count
);
974 json_object_int_add(json_pl
, "rangeEntries",
976 json_object_int_add(json_pl
, "sequenceStart",
977 plist
->head
? plist
->head
->seq
: 0);
978 json_object_int_add(json_pl
, "sequenceEnd",
979 plist
->tail
? plist
->tail
->seq
: 0);
981 vty_out(vty
, "ip%s prefix-list %s:\n",
982 afi
== AFI_IP
? "" : "v6", plist
->name
);
985 vty_out(vty
, " Description: %s\n",
989 " count: %d, range entries: %d, sequences: %" PRId64
991 plist
->count
, plist
->rangecount
,
992 plist
->head
? plist
->head
->seq
: 0,
993 plist
->tail
? plist
->tail
->seq
: 0);
997 if (dtype
!= summary_display
) {
998 json_object
*json_entries
= NULL
;
1001 json_entries
= json_object_new_array();
1002 json_object_object_add(json_pl
, "entries",
1006 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1007 if (dtype
== sequential_display
1008 && pentry
->seq
!= seqnum
)
1012 json_object
*json_entry
;
1014 json_entry
= json_object_new_object();
1015 json_object_array_add(json_entries
, json_entry
);
1017 json_object_int_add(json_entry
,
1020 json_object_string_add(
1022 prefix_list_type_str(pentry
));
1023 json_object_string_addf(json_entry
, "prefix",
1028 json_object_int_add(
1030 "minimumPrefixLength",
1033 json_object_int_add(
1035 "maximumPrefixLength",
1038 if (dtype
== detail_display
1039 || dtype
== sequential_display
) {
1040 json_object_int_add(json_entry
,
1043 json_object_int_add(json_entry
,
1050 vty_out(vty
, "seq %" PRId64
" ", pentry
->seq
);
1053 prefix_list_type_str(pentry
));
1056 vty_out(vty
, "any");
1058 struct prefix
*p
= &pentry
->prefix
;
1060 vty_out(vty
, "%pFX", p
);
1063 vty_out(vty
, " ge %d",
1066 vty_out(vty
, " le %d",
1070 if (dtype
== detail_display
1071 || dtype
== sequential_display
)
1073 " (hit count: %ld, refcount: %ld)",
1074 pentry
->hitcnt
, pentry
->refcnt
);
1082 static int vty_show_prefix_list(struct vty
*vty
, afi_t afi
, const char *name
,
1083 const char *seq
, enum display_type dtype
,
1086 struct prefix_list
*plist
;
1087 struct prefix_master
*master
;
1089 json_object
*json
= NULL
;
1090 json_object
*json_proto
= NULL
;
1092 master
= prefix_master_get(afi
, 0);
1097 json
= json_object_new_object();
1098 json_proto
= json_object_new_object();
1099 json_object_object_add(json
, frr_protoname
, json_proto
);
1103 seqnum
= (int64_t)atol(seq
);
1106 plist
= prefix_list_lookup(afi
, name
);
1110 "%% Can't find specified prefix-list\n");
1113 vty_show_prefix_entry(vty
, json_proto
, afi
, plist
, master
,
1116 if (dtype
== detail_display
|| dtype
== summary_display
) {
1117 if (master
->recent
&& !uj
)
1119 "Prefix-list with the last deletion/insertion: %s\n",
1120 master
->recent
->name
);
1123 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1124 vty_show_prefix_entry(vty
, json_proto
, afi
, plist
,
1125 master
, dtype
, seqnum
);
1128 return vty_json(vty
, json
);
1131 static int vty_show_prefix_list_prefix(struct vty
*vty
, afi_t afi
,
1132 const char *name
, const char *prefix
,
1133 enum display_type type
)
1135 struct prefix_list
*plist
;
1136 struct prefix_list_entry
*pentry
;
1141 plist
= prefix_list_lookup(afi
, name
);
1143 vty_out(vty
, "%% Can't find specified prefix-list\n");
1147 ret
= str2prefix(prefix
, &p
);
1149 vty_out(vty
, "%% prefix is malformed\n");
1153 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1156 if (type
== normal_display
|| type
== first_match_display
)
1157 if (prefix_same(&p
, &pentry
->prefix
))
1160 if (type
== longer_display
) {
1161 if ((p
.family
== pentry
->prefix
.family
)
1162 && (prefix_match(&p
, &pentry
->prefix
)))
1167 vty_out(vty
, " seq %" PRId64
" %s ", pentry
->seq
,
1168 prefix_list_type_str(pentry
));
1171 vty_out(vty
, "any");
1173 struct prefix
*pf
= &pentry
->prefix
;
1175 vty_out(vty
, "%pFX", pf
);
1178 vty_out(vty
, " ge %d", pentry
->ge
);
1180 vty_out(vty
, " le %d", pentry
->le
);
1183 if (type
== normal_display
1184 || type
== first_match_display
)
1185 vty_out(vty
, " (hit count: %ld, refcount: %ld)",
1186 pentry
->hitcnt
, pentry
->refcnt
);
1190 if (type
== first_match_display
)
1197 static int vty_clear_prefix_list(struct vty
*vty
, afi_t afi
, const char *name
,
1200 struct prefix_master
*master
;
1201 struct prefix_list
*plist
;
1202 struct prefix_list_entry
*pentry
;
1206 master
= prefix_master_get(afi
, 0);
1210 if (name
== NULL
&& prefix
== NULL
) {
1211 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1212 for (pentry
= plist
->head
; pentry
;
1213 pentry
= pentry
->next
)
1216 plist
= prefix_list_lookup(afi
, name
);
1218 vty_out(vty
, "%% Can't find specified prefix-list\n");
1223 ret
= str2prefix(prefix
, &p
);
1225 vty_out(vty
, "%% prefix is malformed\n");
1230 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1232 if (pentry
->prefix
.family
== p
.family
1233 && prefix_match(&pentry
->prefix
, &p
))
1242 #ifndef VTYSH_EXTRACT_PL
1243 #include "lib/plist_clippy.c"
1246 DEFPY (show_ip_prefix_list
,
1247 show_ip_prefix_list_cmd
,
1248 "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1252 "Name of a prefix list\n"
1253 "sequence number of an entry\n"
1257 enum display_type dtype
= normal_display
;
1259 dtype
= sequential_display
;
1261 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, arg_str
, dtype
,
1265 DEFPY (show_ip_prefix_list_prefix
,
1266 show_ip_prefix_list_prefix_cmd
,
1267 "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]",
1271 "Name of a prefix list\n"
1272 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n"
1273 "Lookup longer prefix\n"
1274 "First matched prefix\n")
1276 enum display_type dtype
= normal_display
;
1278 dtype
= longer_display
;
1280 dtype
= first_match_display
;
1282 return vty_show_prefix_list_prefix(vty
, AFI_IP
, prefix_list
, prefix_str
,
1286 DEFPY (show_ip_prefix_list_summary
,
1287 show_ip_prefix_list_summary_cmd
,
1288 "show ip prefix-list summary [WORD$prefix_list] [json$uj]",
1292 "Summary of prefix lists\n"
1293 "Name of a prefix list\n"
1296 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1297 summary_display
, !!uj
);
1300 DEFPY (show_ip_prefix_list_detail
,
1301 show_ip_prefix_list_detail_cmd
,
1302 "show ip prefix-list detail [WORD$prefix_list] [json$uj]",
1306 "Detail of prefix lists\n"
1307 "Name of a prefix list\n"
1310 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1311 detail_display
, !!uj
);
1314 DEFPY (clear_ip_prefix_list
,
1315 clear_ip_prefix_list_cmd
,
1316 "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]",
1320 "Name of a prefix list\n"
1321 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n")
1323 return vty_clear_prefix_list(vty
, AFI_IP
, prefix_list
, prefix_str
);
1326 DEFPY (show_ipv6_prefix_list
,
1327 show_ipv6_prefix_list_cmd
,
1328 "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]] [json$uj]",
1332 "Name of a prefix list\n"
1333 "sequence number of an entry\n"
1337 enum display_type dtype
= normal_display
;
1339 dtype
= sequential_display
;
1341 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, arg_str
, dtype
,
1345 DEFPY (show_ipv6_prefix_list_prefix
,
1346 show_ipv6_prefix_list_prefix_cmd
,
1347 "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]",
1351 "Name of a prefix list\n"
1352 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n"
1353 "Lookup longer prefix\n"
1354 "First matched prefix\n")
1356 enum display_type dtype
= normal_display
;
1358 dtype
= longer_display
;
1360 dtype
= first_match_display
;
1362 return vty_show_prefix_list_prefix(vty
, AFI_IP6
, prefix_list
,
1366 DEFPY (show_ipv6_prefix_list_summary
,
1367 show_ipv6_prefix_list_summary_cmd
,
1368 "show ipv6 prefix-list summary [WORD$prefix-list] [json$uj]",
1372 "Summary of prefix lists\n"
1373 "Name of a prefix list\n"
1376 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1377 summary_display
, !!uj
);
1380 DEFPY (show_ipv6_prefix_list_detail
,
1381 show_ipv6_prefix_list_detail_cmd
,
1382 "show ipv6 prefix-list detail [WORD$prefix-list] [json$uj]",
1386 "Detail of prefix lists\n"
1387 "Name of a prefix list\n"
1390 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1391 detail_display
, !!uj
);
1394 DEFPY (clear_ipv6_prefix_list
,
1395 clear_ipv6_prefix_list_cmd
,
1396 "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]",
1400 "Name of a prefix list\n"
1401 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n")
1403 return vty_clear_prefix_list(vty
, AFI_IP6
, prefix_list
, prefix_str
);
1406 DEFPY (debug_prefix_list_match
,
1407 debug_prefix_list_match_cmd
,
1408 "debug prefix-list WORD$prefix-list match <A.B.C.D/M|X:X::X:X/M>"
1409 " [address-mode$addr_mode]",
1411 "Prefix-list test access\n"
1412 "Name of a prefix list\n"
1413 "Test prefix for prefix list result\n"
1414 "Prefix to test in ip prefix-list\n"
1415 "Prefix to test in ipv6 prefix-list\n"
1416 "Use address matching mode (PIM RP)\n")
1418 struct prefix_list
*plist
;
1419 const struct prefix_list_entry
*entry
= NULL
;
1420 enum prefix_list_type ret
;
1422 plist
= prefix_list_lookup(family2afi(match
->family
), prefix_list
);
1424 vty_out(vty
, "%% no prefix list named %s for AFI %s\n",
1425 prefix_list
, afi2str(family2afi(match
->family
)));
1429 ret
= prefix_list_apply_ext(plist
, &entry
, match
, !!addr_mode
);
1431 vty_out(vty
, "%s prefix list %s yields %s for %pFX, ",
1432 afi2str(family2afi(match
->family
)), prefix_list
,
1433 ret
== PREFIX_DENY
? "DENY" : "PERMIT", match
);
1436 vty_out(vty
, "no match found\n");
1438 vty_out(vty
, "matching entry #%"PRId64
": %pFX", entry
->seq
,
1441 vty_out(vty
, " ge %d", entry
->ge
);
1443 vty_out(vty
, " le %d", entry
->le
);
1447 /* allow using this in scripts for quick prefix-list member tests */
1448 return (ret
== PREFIX_PERMIT
) ? CMD_SUCCESS
: CMD_WARNING
;
1451 struct stream
*prefix_bgp_orf_entry(struct stream
*s
, struct prefix_list
*plist
,
1452 uint8_t init_flag
, uint8_t permit_flag
,
1455 struct prefix_list_entry
*pentry
;
1460 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1461 uint8_t flag
= init_flag
;
1462 struct prefix
*p
= &pentry
->prefix
;
1464 flag
|= (pentry
->type
== PREFIX_PERMIT
? permit_flag
1466 stream_putc(s
, flag
);
1467 stream_putl(s
, (uint32_t)pentry
->seq
);
1468 stream_putc(s
, (uint8_t)pentry
->ge
);
1469 stream_putc(s
, (uint8_t)pentry
->le
);
1470 stream_put_prefix(s
, p
);
1476 int prefix_bgp_orf_set(char *name
, afi_t afi
, struct orf_prefix
*orfp
,
1477 int permit
, int set
)
1479 struct prefix_list
*plist
;
1480 struct prefix_list_entry
*pentry
;
1482 /* ge and le value check */
1483 if (orfp
->ge
&& orfp
->ge
< orfp
->p
.prefixlen
)
1484 return CMD_WARNING_CONFIG_FAILED
;
1485 if (orfp
->le
&& orfp
->le
< orfp
->p
.prefixlen
)
1486 return CMD_WARNING_CONFIG_FAILED
;
1487 if (orfp
->le
&& orfp
->ge
> orfp
->le
)
1488 return CMD_WARNING_CONFIG_FAILED
;
1490 if (orfp
->ge
&& orfp
->le
== (afi
== AFI_IP
? 32 : 128))
1493 plist
= prefix_list_get(afi
, 1, name
);
1495 return CMD_WARNING_CONFIG_FAILED
;
1497 apply_mask(&orfp
->p
);
1500 pentry
= prefix_list_entry_make(
1501 &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1502 orfp
->seq
, orfp
->le
, orfp
->ge
, false);
1504 if (prefix_entry_dup_check(plist
, pentry
)) {
1505 prefix_list_entry_free(pentry
);
1506 return CMD_WARNING_CONFIG_FAILED
;
1509 prefix_list_entry_add(plist
, pentry
);
1511 pentry
= prefix_list_entry_lookup(
1512 plist
, &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1513 orfp
->seq
, orfp
->le
, orfp
->ge
);
1516 return CMD_WARNING_CONFIG_FAILED
;
1518 prefix_list_entry_delete(plist
, pentry
, 1);
1524 void prefix_bgp_orf_remove_all(afi_t afi
, char *name
)
1526 struct prefix_list
*plist
;
1528 plist
= prefix_bgp_orf_lookup(afi
, name
);
1530 prefix_list_delete(plist
);
1533 /* return prefix count */
1534 int prefix_bgp_show_prefix_list(struct vty
*vty
, afi_t afi
, char *name
,
1537 struct prefix_list
*plist
;
1538 struct prefix_list_entry
*pentry
;
1539 json_object
*json
= NULL
;
1540 json_object
*json_prefix
= NULL
;
1541 json_object
*json_list
= NULL
;
1543 plist
= prefix_bgp_orf_lookup(afi
, name
);
1548 return plist
->count
;
1551 json
= json_object_new_object();
1552 json_prefix
= json_object_new_object();
1553 json_list
= json_object_new_object();
1555 json_object_int_add(json_prefix
, "prefixListCounter",
1557 json_object_string_add(json_prefix
, "prefixListName",
1560 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1561 struct prefix
*p
= &pentry
->prefix
;
1564 snprintf(buf_a
, sizeof(buf_a
), "%pFX", p
);
1566 json_object_int_add(json_list
, "seq", pentry
->seq
);
1567 json_object_string_add(json_list
, "seqPrefixListType",
1568 prefix_list_type_str(pentry
));
1571 json_object_int_add(json_list
, "ge",
1574 json_object_int_add(json_list
, "le",
1577 json_object_object_add(json_prefix
, buf_a
, json_list
);
1580 json_object_object_add(json
, "ipPrefixList",
1583 json_object_object_add(json
, "ipv6PrefixList",
1586 vty_json(vty
, json
);
1588 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
1589 afi
== AFI_IP
? "" : "v6", plist
->name
, plist
->count
);
1591 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1592 struct prefix
*p
= &pentry
->prefix
;
1594 vty_out(vty
, " seq %" PRId64
" %s %pFX", pentry
->seq
,
1595 prefix_list_type_str(pentry
), p
);
1598 vty_out(vty
, " ge %d", pentry
->ge
);
1600 vty_out(vty
, " le %d", pentry
->le
);
1605 return plist
->count
;
1608 static void prefix_list_reset_afi(afi_t afi
, int orf
)
1610 struct prefix_list
*plist
;
1611 struct prefix_list
*next
;
1612 struct prefix_master
*master
;
1614 master
= prefix_master_get(afi
, orf
);
1618 for (plist
= master
->str
.head
; plist
; plist
= next
) {
1620 prefix_list_delete(plist
);
1623 assert(master
->str
.head
== NULL
);
1624 assert(master
->str
.tail
== NULL
);
1626 master
->recent
= NULL
;
1629 /* Prefix-list node. */
1630 static struct cmd_node prefix_node
= {
1631 .name
= "ipv4 prefix list",
1632 .node
= PREFIX_NODE
,
1636 static void plist_autocomplete_afi(afi_t afi
, vector comps
,
1637 struct cmd_token
*token
)
1639 struct prefix_list
*plist
;
1640 struct prefix_master
*master
;
1642 master
= prefix_master_get(afi
, 0);
1646 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1647 vector_set(comps
, XSTRDUP(MTYPE_COMPLETION
, plist
->name
));
1650 static void plist_autocomplete(vector comps
, struct cmd_token
*token
)
1652 plist_autocomplete_afi(AFI_IP
, comps
, token
);
1653 plist_autocomplete_afi(AFI_IP6
, comps
, token
);
1656 static const struct cmd_variable_handler plist_var_handlers
[] = {
1657 {/* "prefix-list WORD" */
1658 .varname
= "prefix_list",
1659 .completions
= plist_autocomplete
},
1660 {.tokenname
= "PREFIXLIST_NAME",
1661 .completions
= plist_autocomplete
},
1662 {.completions
= NULL
}};
1665 static void prefix_list_init_ipv4(void)
1667 install_node(&prefix_node
);
1669 install_element(VIEW_NODE
, &show_ip_prefix_list_cmd
);
1670 install_element(VIEW_NODE
, &show_ip_prefix_list_prefix_cmd
);
1671 install_element(VIEW_NODE
, &show_ip_prefix_list_summary_cmd
);
1672 install_element(VIEW_NODE
, &show_ip_prefix_list_detail_cmd
);
1674 install_element(ENABLE_NODE
, &clear_ip_prefix_list_cmd
);
1677 /* Prefix-list node. */
1678 static struct cmd_node prefix_ipv6_node
= {
1679 .name
= "ipv6 prefix list",
1680 .node
= PREFIX_IPV6_NODE
,
1684 static void prefix_list_init_ipv6(void)
1686 install_node(&prefix_ipv6_node
);
1688 install_element(VIEW_NODE
, &show_ipv6_prefix_list_cmd
);
1689 install_element(VIEW_NODE
, &show_ipv6_prefix_list_prefix_cmd
);
1690 install_element(VIEW_NODE
, &show_ipv6_prefix_list_summary_cmd
);
1691 install_element(VIEW_NODE
, &show_ipv6_prefix_list_detail_cmd
);
1692 install_element(VIEW_NODE
, &debug_prefix_list_match_cmd
);
1694 install_element(ENABLE_NODE
, &clear_ipv6_prefix_list_cmd
);
1697 void prefix_list_init(void)
1699 cmd_variable_handler_register(plist_var_handlers
);
1701 prefix_list_init_ipv4();
1702 prefix_list_init_ipv6();
1705 void prefix_list_reset(void)
1707 prefix_list_reset_afi(AFI_IP
, 0);
1708 prefix_list_reset_afi(AFI_IP6
, 0);
1709 prefix_list_reset_afi(AFI_IP
, 1);
1710 prefix_list_reset_afi(AFI_IP6
, 1);