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 number. */
70 struct prefix_list_list num
;
72 /* List of prefix_list which name is string. */
73 struct prefix_list_list str
;
75 /* Whether sequential number is used. */
78 /* The latest update. */
79 struct prefix_list
*recent
;
81 /* Hook function which is executed when new prefix_list is added. */
82 void (*add_hook
)(struct prefix_list
*);
84 /* Hook function which is executed when prefix_list is deleted. */
85 void (*delete_hook
)(struct prefix_list
*);
87 /* number of bytes that have a trie level */
91 /* Static structure of IPv4 prefix_list's master. */
92 static struct prefix_master prefix_master_ipv4
= {
93 {NULL
, NULL
}, {NULL
, NULL
}, 1, NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
96 /* Static structure of IPv6 prefix-list's master. */
97 static struct prefix_master prefix_master_ipv6
= {
98 {NULL
, NULL
}, {NULL
, NULL
}, 1, NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
101 /* Static structure of BGP ORF prefix_list's master. */
102 static struct prefix_master prefix_master_orf_v4
= {
103 {NULL
, NULL
}, {NULL
, NULL
}, 1, NULL
, NULL
, NULL
, PLC_MAXLEVELV4
,
106 /* Static structure of BGP ORF prefix_list's master. */
107 static struct prefix_master prefix_master_orf_v6
= {
108 {NULL
, NULL
}, {NULL
, NULL
}, 1, NULL
, NULL
, NULL
, PLC_MAXLEVELV6
,
111 static struct prefix_master
*prefix_master_get(afi_t afi
, int orf
)
114 return orf
? &prefix_master_orf_v4
: &prefix_master_ipv4
;
116 return orf
? &prefix_master_orf_v6
: &prefix_master_ipv6
;
120 const char *prefix_list_name(struct prefix_list
*plist
)
125 afi_t
prefix_list_afi(struct prefix_list
*plist
)
127 if (plist
->master
== &prefix_master_ipv4
128 || plist
->master
== &prefix_master_orf_v4
)
133 /* Lookup prefix_list from list of prefix_list by name. */
134 static struct prefix_list
*prefix_list_lookup_do(afi_t afi
, int orf
,
137 struct prefix_list
*plist
;
138 struct prefix_master
*master
;
143 master
= prefix_master_get(afi
, orf
);
147 for (plist
= master
->num
.head
; plist
; plist
= plist
->next
)
148 if (strcmp(plist
->name
, name
) == 0)
151 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
152 if (strcmp(plist
->name
, name
) == 0)
158 struct prefix_list
*prefix_list_lookup(afi_t afi
, const char *name
)
160 return prefix_list_lookup_do(afi
, 0, name
);
163 struct prefix_list
*prefix_bgp_orf_lookup(afi_t afi
, const char *name
)
165 return prefix_list_lookup_do(afi
, 1, name
);
168 static struct prefix_list
*prefix_list_new(void)
170 struct prefix_list
*new;
172 new = XCALLOC(MTYPE_PREFIX_LIST
, sizeof(struct prefix_list
));
176 static void prefix_list_free(struct prefix_list
*plist
)
178 XFREE(MTYPE_PREFIX_LIST
, plist
);
181 struct prefix_list_entry
*prefix_list_entry_new(void)
183 struct prefix_list_entry
*new;
185 new = XCALLOC(MTYPE_PREFIX_LIST_ENTRY
,
186 sizeof(struct prefix_list_entry
));
190 void prefix_list_entry_free(struct prefix_list_entry
*pentry
)
192 XFREE(MTYPE_PREFIX_LIST_ENTRY
, pentry
);
195 /* Insert new prefix list to list of prefix_list. Each prefix_list
196 is sorted by the name. */
197 static struct prefix_list
*prefix_list_insert(afi_t afi
, int orf
,
202 struct prefix_list
*plist
;
203 struct prefix_list
*point
;
204 struct prefix_list_list
*list
;
205 struct prefix_master
*master
;
207 master
= prefix_master_get(afi
, orf
);
211 /* Allocate new prefix_list and copy given name. */
212 plist
= prefix_list_new();
213 plist
->name
= XSTRDUP(MTYPE_MPREFIX_LIST_STR
, name
);
214 plist
->master
= master
;
216 XCALLOC(MTYPE_PREFIX_LIST_TRIE
, sizeof(struct pltrie_table
));
218 /* If name is made by all digit character. We treat it as
220 for (number
= 0, i
= 0; i
< strlen(name
); i
++) {
221 if (isdigit((unsigned char)name
[i
]))
222 number
= (number
* 10) + (name
[i
] - '0');
227 /* In case of name is all digit character */
228 if (i
== strlen(name
)) {
229 plist
->type
= PREFIX_TYPE_NUMBER
;
231 /* Set prefix_list to number list. */
234 for (point
= list
->head
; point
; point
= point
->next
)
235 if (atol(point
->name
) >= number
)
238 plist
->type
= PREFIX_TYPE_STRING
;
240 /* Set prefix_list to string list. */
243 /* Set point to insertion point. */
244 for (point
= list
->head
; point
; point
= point
->next
)
245 if (strcmp(point
->name
, name
) >= 0)
249 /* In case of this is the first element of master. */
250 if (list
->head
== NULL
) {
251 list
->head
= list
->tail
= plist
;
255 /* In case of insertion is made at the tail of access_list. */
257 plist
->prev
= list
->tail
;
258 list
->tail
->next
= plist
;
263 /* In case of insertion is made at the head of access_list. */
264 if (point
== list
->head
) {
265 plist
->next
= list
->head
;
266 list
->head
->prev
= plist
;
271 /* Insertion is made at middle of the access_list. */
273 plist
->prev
= point
->prev
;
276 point
->prev
->next
= plist
;
282 struct prefix_list
*prefix_list_get(afi_t afi
, int orf
, const char *name
)
284 struct prefix_list
*plist
;
286 plist
= prefix_list_lookup_do(afi
, orf
, name
);
289 plist
= prefix_list_insert(afi
, orf
, name
);
293 static void prefix_list_trie_del(struct prefix_list
*plist
,
294 struct prefix_list_entry
*pentry
);
296 /* Delete prefix-list from prefix_list_master and free it. */
297 void prefix_list_delete(struct prefix_list
*plist
)
299 struct prefix_list_list
*list
;
300 struct prefix_master
*master
;
301 struct prefix_list_entry
*pentry
;
302 struct prefix_list_entry
*next
;
304 /* If prefix-list contain prefix_list_entry free all of it. */
305 for (pentry
= plist
->head
; pentry
; pentry
= next
) {
306 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
307 RMAP_EVENT_PLIST_DELETED
);
309 prefix_list_trie_del(plist
, pentry
);
310 prefix_list_entry_free(pentry
);
314 master
= plist
->master
;
316 if (plist
->type
== PREFIX_TYPE_NUMBER
)
322 plist
->next
->prev
= plist
->prev
;
324 list
->tail
= plist
->prev
;
327 plist
->prev
->next
= plist
->next
;
329 list
->head
= plist
->next
;
331 XFREE(MTYPE_TMP
, plist
->desc
);
333 /* Make sure master's recent changed prefix-list information is
335 master
->recent
= NULL
;
337 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_DELETED
);
339 if (master
->delete_hook
)
340 (*master
->delete_hook
)(plist
);
342 XFREE(MTYPE_MPREFIX_LIST_STR
, plist
->name
);
344 XFREE(MTYPE_PREFIX_LIST_TRIE
, plist
->trie
);
346 prefix_list_free(plist
);
349 static struct prefix_list_entry
*
350 prefix_list_entry_make(struct prefix
*prefix
, enum prefix_list_type type
,
351 int64_t seq
, int le
, int ge
, bool any
)
353 struct prefix_list_entry
*pentry
;
355 pentry
= prefix_list_entry_new();
360 prefix_copy(&pentry
->prefix
, prefix
);
369 /* Add hook function. */
370 void prefix_list_add_hook(void (*func
)(struct prefix_list
*plist
))
372 prefix_master_ipv4
.add_hook
= func
;
373 prefix_master_ipv6
.add_hook
= func
;
376 /* Delete hook function. */
377 void prefix_list_delete_hook(void (*func
)(struct prefix_list
*plist
))
379 prefix_master_ipv4
.delete_hook
= func
;
380 prefix_master_ipv6
.delete_hook
= func
;
383 /* Calculate new sequential number. */
384 int64_t prefix_new_seq_get(struct prefix_list
*plist
)
388 struct prefix_list_entry
*pentry
;
392 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
393 if (maxseq
< pentry
->seq
)
394 maxseq
= pentry
->seq
;
397 newseq
= ((maxseq
/ 5) * 5) + 5;
399 return (newseq
> UINT_MAX
) ? UINT_MAX
: newseq
;
402 /* Return prefix list entry which has same seq number. */
403 static struct prefix_list_entry
*prefix_seq_check(struct prefix_list
*plist
,
406 struct prefix_list_entry
*pentry
;
408 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
409 if (pentry
->seq
== seq
)
414 struct prefix_list_entry
*
415 prefix_list_entry_lookup(struct prefix_list
*plist
, struct prefix
*prefix
,
416 enum prefix_list_type type
, int64_t seq
,
419 struct prefix_list_entry
*pentry
;
421 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
)
422 if (prefix_same(&pentry
->prefix
, prefix
)
423 && pentry
->type
== type
) {
424 if (seq
>= 0 && pentry
->seq
!= seq
)
427 if (pentry
->le
!= le
)
429 if (pentry
->ge
!= ge
)
438 static void trie_walk_affected(size_t validbits
, struct pltrie_table
*table
,
439 uint8_t byte
, struct prefix_list_entry
*object
,
440 void (*fn
)(struct prefix_list_entry
*object
,
441 struct prefix_list_entry
**updptr
))
446 if (validbits
> PLC_BITS
) {
447 fn(object
, &table
->entries
[byte
].final_chain
);
451 mask
= (1 << (8 - validbits
)) - 1;
452 for (bwalk
= byte
& ~mask
; bwalk
<= byte
+ mask
; bwalk
++) {
453 fn(object
, &table
->entries
[bwalk
].up_chain
);
457 static void trie_uninstall_fn(struct prefix_list_entry
*object
,
458 struct prefix_list_entry
**updptr
)
460 for (; *updptr
; updptr
= &(*updptr
)->next_best
)
461 if (*updptr
== object
) {
462 *updptr
= object
->next_best
;
467 static int trie_table_empty(struct pltrie_table
*table
)
470 for (i
= 0; i
< PLC_LEN
; i
++)
471 if (table
->entries
[i
].next_table
|| table
->entries
[i
].up_chain
)
476 static void prefix_list_trie_del(struct prefix_list
*plist
,
477 struct prefix_list_entry
*pentry
)
479 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
480 uint8_t *bytes
= pentry
->prefix
.u
.val
;
481 size_t validbits
= pentry
->prefix
.prefixlen
;
482 struct pltrie_table
*table
, **tables
[PLC_MAXLEVEL
];
485 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
486 uint8_t byte
= bytes
[depth
];
487 assert(table
->entries
[byte
].next_table
);
489 tables
[depth
+ 1] = &table
->entries
[byte
].next_table
;
490 table
= table
->entries
[byte
].next_table
;
492 validbits
-= PLC_BITS
;
495 trie_walk_affected(validbits
, table
, bytes
[depth
], pentry
,
498 for (; depth
> 0; depth
--)
499 if (trie_table_empty(*tables
[depth
])) {
500 XFREE(MTYPE_PREFIX_LIST_TRIE
, *tables
[depth
]);
505 void prefix_list_entry_delete(struct prefix_list
*plist
,
506 struct prefix_list_entry
*pentry
,
509 if (plist
== NULL
|| pentry
== NULL
)
512 prefix_list_trie_del(plist
, pentry
);
515 pentry
->prev
->next
= pentry
->next
;
517 plist
->head
= pentry
->next
;
519 pentry
->next
->prev
= pentry
->prev
;
521 plist
->tail
= pentry
->prev
;
523 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
524 RMAP_EVENT_PLIST_DELETED
);
525 prefix_list_entry_free(pentry
);
530 route_map_notify_dependencies(plist
->name
,
531 RMAP_EVENT_PLIST_DELETED
);
532 if (plist
->master
->delete_hook
)
533 (*plist
->master
->delete_hook
)(plist
);
535 if (plist
->head
== NULL
&& plist
->tail
== NULL
536 && plist
->desc
== NULL
)
537 prefix_list_delete(plist
);
539 plist
->master
->recent
= plist
;
543 static void trie_install_fn(struct prefix_list_entry
*object
,
544 struct prefix_list_entry
**updptr
)
547 if (*updptr
== object
)
549 if ((*updptr
)->prefix
.prefixlen
< object
->prefix
.prefixlen
)
551 if ((*updptr
)->prefix
.prefixlen
== object
->prefix
.prefixlen
552 && (*updptr
)->seq
> object
->seq
)
554 updptr
= &(*updptr
)->next_best
;
557 if (!object
->next_best
)
558 object
->next_best
= *updptr
;
560 assert(object
->next_best
== *updptr
|| !*updptr
);
565 static void prefix_list_trie_add(struct prefix_list
*plist
,
566 struct prefix_list_entry
*pentry
)
568 size_t depth
= plist
->master
->trie_depth
;
569 uint8_t *bytes
= pentry
->prefix
.u
.val
;
570 size_t validbits
= pentry
->prefix
.prefixlen
;
571 struct pltrie_table
*table
;
574 while (validbits
> PLC_BITS
&& depth
> 1) {
575 if (!table
->entries
[*bytes
].next_table
)
576 table
->entries
[*bytes
].next_table
=
577 XCALLOC(MTYPE_PREFIX_LIST_TRIE
,
578 sizeof(struct pltrie_table
));
579 table
= table
->entries
[*bytes
].next_table
;
582 validbits
-= PLC_BITS
;
585 trie_walk_affected(validbits
, table
, *bytes
, pentry
, trie_install_fn
);
588 static void prefix_list_entry_add(struct prefix_list
*plist
,
589 struct prefix_list_entry
*pentry
)
591 struct prefix_list_entry
*replace
;
592 struct prefix_list_entry
*point
;
594 /* Automatic asignment of seq no. */
595 if (pentry
->seq
== -1)
596 pentry
->seq
= prefix_new_seq_get(plist
);
598 if (plist
->tail
&& pentry
->seq
> plist
->tail
->seq
)
601 /* Is there any same seq prefix list entry? */
602 replace
= prefix_seq_check(plist
, pentry
->seq
);
604 prefix_list_entry_delete(plist
, replace
, 0);
606 /* Check insert point. */
607 for (point
= plist
->head
; point
; point
= point
->next
)
608 if (point
->seq
>= pentry
->seq
)
612 /* In case of this is the first element of the list. */
613 pentry
->next
= point
;
617 point
->prev
->next
= pentry
;
619 plist
->head
= pentry
;
621 pentry
->prev
= point
->prev
;
622 point
->prev
= pentry
;
625 plist
->tail
->next
= pentry
;
627 plist
->head
= pentry
;
629 pentry
->prev
= plist
->tail
;
630 plist
->tail
= pentry
;
633 prefix_list_trie_add(plist
, pentry
);
635 /* Increment count. */
638 route_map_notify_pentry_dependencies(plist
->name
, pentry
,
639 RMAP_EVENT_PLIST_ADDED
);
641 /* Run hook function. */
642 if (plist
->master
->add_hook
)
643 (*plist
->master
->add_hook
)(plist
);
645 route_map_notify_dependencies(plist
->name
, RMAP_EVENT_PLIST_ADDED
);
646 plist
->master
->recent
= plist
;
650 * Prefix list entry update start procedure:
651 * Remove entry from previosly installed master list, tries and notify
654 * \param[in] ple prefix list entry.
656 void prefix_list_entry_update_start(struct prefix_list_entry
*ple
)
658 struct prefix_list
*pl
= ple
->pl
;
660 /* Not installed, nothing to do. */
664 prefix_list_trie_del(pl
, ple
);
666 /* List manipulation: shameless copy from `prefix_list_entry_delete`. */
668 ple
->prev
->next
= ple
->next
;
670 pl
->head
= ple
->next
;
672 ple
->next
->prev
= ple
->prev
;
674 pl
->tail
= ple
->prev
;
676 route_map_notify_pentry_dependencies(pl
->name
, ple
,
677 RMAP_EVENT_PLIST_DELETED
);
680 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_DELETED
);
681 if (pl
->master
->delete_hook
)
682 (*pl
->master
->delete_hook
)(pl
);
684 if (pl
->head
|| pl
->tail
|| pl
->desc
)
685 pl
->master
->recent
= pl
;
687 ple
->installed
= false;
691 * Prefix list entry update finish procedure:
692 * Add entry back master list, to the trie, notify observers and call master
695 * \param[in] ple prefix list entry.
697 void prefix_list_entry_update_finish(struct prefix_list_entry
*ple
)
699 struct prefix_list
*pl
= ple
->pl
;
700 struct prefix_list_entry
*point
;
702 /* Already installed, nothing to do. */
707 * Check if the entry is installable:
708 * We can only install entry if at least the prefix is provided (IPv4
711 if (ple
->prefix
.family
!= AF_INET
&& ple
->prefix
.family
!= AF_INET6
)
714 /* List manipulation: shameless copy from `prefix_list_entry_add`. */
715 if (pl
->tail
&& ple
->seq
> pl
->tail
->seq
)
718 /* Check insert point. */
719 for (point
= pl
->head
; point
; point
= point
->next
)
720 if (point
->seq
>= ple
->seq
)
724 /* In case of this is the first element of the list. */
729 point
->prev
->next
= ple
;
733 ple
->prev
= point
->prev
;
737 pl
->tail
->next
= ple
;
741 ple
->prev
= pl
->tail
;
745 prefix_list_trie_add(pl
, ple
);
748 route_map_notify_pentry_dependencies(pl
->name
, ple
,
749 RMAP_EVENT_PLIST_ADDED
);
751 /* Run hook function. */
752 if (pl
->master
->add_hook
)
753 (*pl
->master
->add_hook
)(pl
);
755 route_map_notify_dependencies(pl
->name
, RMAP_EVENT_PLIST_ADDED
);
756 pl
->master
->recent
= pl
;
758 ple
->installed
= true;
762 * Same as `prefix_list_entry_delete` but without `free()`ing the list if its
765 * \param[in] ple prefix list entry.
767 void prefix_list_entry_delete2(struct prefix_list_entry
*ple
)
769 /* Does the boiler plate list removal and entry removal notification. */
770 prefix_list_entry_update_start(ple
);
772 /* Effective `free()` memory. */
773 prefix_list_entry_free(ple
);
776 /* Return string of prefix_list_type. */
777 static const char *prefix_list_type_str(struct prefix_list_entry
*pentry
)
779 switch (pentry
->type
) {
789 static int prefix_list_entry_match(struct prefix_list_entry
*pentry
,
790 const struct prefix
*p
)
794 if (pentry
->prefix
.family
!= p
->family
)
797 ret
= prefix_match(&pentry
->prefix
, p
);
801 /* In case of le nor ge is specified, exact match is performed. */
802 if (!pentry
->le
&& !pentry
->ge
) {
803 if (pentry
->prefix
.prefixlen
!= p
->prefixlen
)
807 if (p
->prefixlen
> pentry
->le
)
811 if (p
->prefixlen
< pentry
->ge
)
817 enum prefix_list_type
prefix_list_apply_which_prefix(
818 struct prefix_list
*plist
,
819 const struct prefix
**which
,
822 struct prefix_list_entry
*pentry
, *pbest
= NULL
;
824 const struct prefix
*p
= (const struct prefix
*)object
;
825 const uint8_t *byte
= p
->u
.val
;
827 size_t validbits
= p
->prefixlen
;
828 struct pltrie_table
*table
;
836 if (plist
->count
== 0) {
839 return PREFIX_PERMIT
;
842 depth
= plist
->master
->trie_depth
;
845 for (pentry
= table
->entries
[*byte
].up_chain
; pentry
;
846 pentry
= pentry
->next_best
) {
847 if (pbest
&& pbest
->seq
< pentry
->seq
)
849 if (prefix_list_entry_match(pentry
, p
))
853 if (validbits
<= PLC_BITS
)
855 validbits
-= PLC_BITS
;
858 if (!table
->entries
[*byte
].next_table
)
861 table
= table
->entries
[*byte
].next_table
;
866 for (pentry
= table
->entries
[*byte
].final_chain
; pentry
;
867 pentry
= pentry
->next_best
) {
868 if (pbest
&& pbest
->seq
< pentry
->seq
)
870 if (prefix_list_entry_match(pentry
, p
))
878 *which
= &pbest
->prefix
;
890 static void __attribute__((unused
)) prefix_list_print(struct prefix_list
*plist
)
892 struct prefix_list_entry
*pentry
;
897 printf("ip prefix-list %s: %d entries\n", plist
->name
, plist
->count
);
899 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
901 printf("any %s\n", prefix_list_type_str(pentry
));
908 printf(" seq %lld %s %s/%d", (long long)pentry
->seq
,
909 prefix_list_type_str(pentry
),
910 inet_ntop(p
->family
, p
->u
.val
, buf
, BUFSIZ
),
913 printf(" ge %d", pentry
->ge
);
915 printf(" le %d", pentry
->le
);
921 /* Retrun 1 when plist already include pentry policy. */
922 static struct prefix_list_entry
*
923 prefix_entry_dup_check(struct prefix_list
*plist
, struct prefix_list_entry
*new)
925 size_t depth
, maxdepth
= plist
->master
->trie_depth
;
926 uint8_t byte
, *bytes
= new->prefix
.u
.val
;
927 size_t validbits
= new->prefix
.prefixlen
;
928 struct pltrie_table
*table
;
929 struct prefix_list_entry
*pentry
;
933 seq
= prefix_new_seq_get(plist
);
938 for (depth
= 0; validbits
> PLC_BITS
&& depth
< maxdepth
- 1; depth
++) {
940 if (!table
->entries
[byte
].next_table
)
943 table
= table
->entries
[byte
].next_table
;
944 validbits
-= PLC_BITS
;
948 if (validbits
> PLC_BITS
)
949 pentry
= table
->entries
[byte
].final_chain
;
951 pentry
= table
->entries
[byte
].up_chain
;
953 for (; pentry
; pentry
= pentry
->next_best
) {
954 if (prefix_same(&pentry
->prefix
, &new->prefix
)
955 && pentry
->type
== new->type
&& pentry
->le
== new->le
956 && pentry
->ge
== new->ge
&& pentry
->seq
!= seq
)
971 static void vty_show_prefix_entry(struct vty
*vty
, afi_t afi
,
972 struct prefix_list
*plist
,
973 struct prefix_master
*master
,
974 enum display_type dtype
, int seqnum
)
976 struct prefix_list_entry
*pentry
;
978 /* Print the name of the protocol */
979 vty_out(vty
, "%s: ", frr_protoname
);
981 if (dtype
== normal_display
) {
982 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
983 afi
== AFI_IP
? "" : "v6", plist
->name
, plist
->count
);
985 vty_out(vty
, " Description: %s\n", plist
->desc
);
986 } else if (dtype
== summary_display
|| dtype
== detail_display
) {
987 vty_out(vty
, "ip%s prefix-list %s:\n",
988 afi
== AFI_IP
? "" : "v6", plist
->name
);
991 vty_out(vty
, " Description: %s\n", plist
->desc
);
994 " count: %d, range entries: %d, sequences: %" PRId64
" - %" PRId64
"\n",
995 plist
->count
, plist
->rangecount
,
996 plist
->head
? plist
->head
->seq
: 0,
997 plist
->tail
? plist
->tail
->seq
: 0);
1000 if (dtype
!= summary_display
) {
1001 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1002 if (dtype
== sequential_display
1003 && pentry
->seq
!= seqnum
)
1009 vty_out(vty
, "seq %" PRId64
" ", pentry
->seq
);
1011 vty_out(vty
, "%s ", prefix_list_type_str(pentry
));
1014 vty_out(vty
, "any");
1016 struct prefix
*p
= &pentry
->prefix
;
1019 vty_out(vty
, "%s/%d",
1020 inet_ntop(p
->family
, p
->u
.val
, buf
,
1025 vty_out(vty
, " ge %d", pentry
->ge
);
1027 vty_out(vty
, " le %d", pentry
->le
);
1030 if (dtype
== detail_display
1031 || dtype
== sequential_display
)
1032 vty_out(vty
, " (hit count: %ld, refcount: %ld)",
1033 pentry
->hitcnt
, pentry
->refcnt
);
1040 static int vty_show_prefix_list(struct vty
*vty
, afi_t afi
, const char *name
,
1041 const char *seq
, enum display_type dtype
)
1043 struct prefix_list
*plist
;
1044 struct prefix_master
*master
;
1047 master
= prefix_master_get(afi
, 0);
1052 seqnum
= (int64_t)atol(seq
);
1055 plist
= prefix_list_lookup(afi
, name
);
1057 vty_out(vty
, "%% Can't find specified prefix-list\n");
1060 vty_show_prefix_entry(vty
, afi
, plist
, master
, dtype
, seqnum
);
1062 if (dtype
== detail_display
|| dtype
== summary_display
) {
1065 "Prefix-list with the last deletion/insertion: %s\n",
1066 master
->recent
->name
);
1069 for (plist
= master
->num
.head
; plist
; plist
= plist
->next
)
1070 vty_show_prefix_entry(vty
, afi
, plist
, master
, dtype
,
1073 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1074 vty_show_prefix_entry(vty
, afi
, plist
, master
, dtype
,
1081 static int vty_show_prefix_list_prefix(struct vty
*vty
, afi_t afi
,
1082 const char *name
, const char *prefix
,
1083 enum display_type type
)
1085 struct prefix_list
*plist
;
1086 struct prefix_list_entry
*pentry
;
1091 plist
= prefix_list_lookup(afi
, name
);
1093 vty_out(vty
, "%% Can't find specified prefix-list\n");
1097 ret
= str2prefix(prefix
, &p
);
1099 vty_out(vty
, "%% prefix is malformed\n");
1103 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1106 if (type
== normal_display
|| type
== first_match_display
)
1107 if (prefix_same(&p
, &pentry
->prefix
))
1110 if (type
== longer_display
) {
1111 if ((p
.family
== pentry
->prefix
.family
)
1112 && (prefix_match(&p
, &pentry
->prefix
)))
1117 vty_out(vty
, " seq %" PRId64
" %s ", pentry
->seq
,
1118 prefix_list_type_str(pentry
));
1121 vty_out(vty
, "any");
1123 struct prefix
*pf
= &pentry
->prefix
;
1126 vty_out(vty
, "%s/%d",
1127 inet_ntop(pf
->family
, pf
->u
.val
, buf
,
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 for (plist
= master
->num
.head
; plist
; plist
= plist
->next
)
1166 for (pentry
= plist
->head
; pentry
;
1167 pentry
= pentry
->next
)
1170 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1171 for (pentry
= plist
->head
; pentry
;
1172 pentry
= pentry
->next
)
1175 plist
= prefix_list_lookup(afi
, name
);
1177 vty_out(vty
, "%% Can't find specified prefix-list\n");
1182 ret
= str2prefix(prefix
, &p
);
1184 vty_out(vty
, "%% prefix is malformed\n");
1189 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1191 if (pentry
->prefix
.family
== p
.family
1192 && prefix_match(&pentry
->prefix
, &p
))
1201 #ifndef VTYSH_EXTRACT_PL
1202 #include "lib/plist_clippy.c"
1205 DEFPY (ip_prefix_list_sequence_number
,
1206 ip_prefix_list_sequence_number_cmd
,
1207 "[no] ip prefix-list sequence-number",
1211 "Include/exclude sequence numbers in NVGEN\n")
1213 prefix_master_ipv4
.seqnum
= no
? false : true;
1218 DEFPY (show_ip_prefix_list
,
1219 show_ip_prefix_list_cmd
,
1220 "show ip prefix-list [WORD [seq$dseq (1-4294967295)$arg]]",
1224 "Name of a prefix list\n"
1225 "sequence number of an entry\n"
1226 "Sequence number\n")
1228 enum display_type dtype
= normal_display
;
1230 dtype
= sequential_display
;
1232 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, arg_str
, dtype
);
1235 DEFPY (show_ip_prefix_list_prefix
,
1236 show_ip_prefix_list_prefix_cmd
,
1237 "show ip prefix-list WORD A.B.C.D/M$prefix [longer$dl|first-match$dfm]",
1241 "Name of a prefix list\n"
1242 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n"
1243 "Lookup longer prefix\n"
1244 "First matched prefix\n")
1246 enum display_type dtype
= normal_display
;
1248 dtype
= longer_display
;
1250 dtype
= first_match_display
;
1252 return vty_show_prefix_list_prefix(vty
, AFI_IP
, prefix_list
, prefix_str
,
1256 DEFPY (show_ip_prefix_list_summary
,
1257 show_ip_prefix_list_summary_cmd
,
1258 "show ip prefix-list summary [WORD$prefix_list]",
1262 "Summary of prefix lists\n"
1263 "Name of a prefix list\n")
1265 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1269 DEFPY (show_ip_prefix_list_detail
,
1270 show_ip_prefix_list_detail_cmd
,
1271 "show ip prefix-list detail [WORD$prefix_list]",
1275 "Detail of prefix lists\n"
1276 "Name of a prefix list\n")
1278 return vty_show_prefix_list(vty
, AFI_IP
, prefix_list
, NULL
,
1282 DEFPY (clear_ip_prefix_list
,
1283 clear_ip_prefix_list_cmd
,
1284 "clear ip prefix-list [WORD [A.B.C.D/M$prefix]]",
1288 "Name of a prefix list\n"
1289 "IP prefix <network>/<length>, e.g., 35.0.0.0/8\n")
1291 return vty_clear_prefix_list(vty
, AFI_IP
, prefix_list
, prefix_str
);
1294 DEFPY (ipv6_prefix_list_sequence_number
,
1295 ipv6_prefix_list_sequence_number_cmd
,
1296 "[no] ipv6 prefix-list sequence-number",
1300 "Include/exclude sequence numbers in NVGEN\n")
1302 prefix_master_ipv6
.seqnum
= no
? false : true;
1306 DEFPY (show_ipv6_prefix_list
,
1307 show_ipv6_prefix_list_cmd
,
1308 "show ipv6 prefix-list [WORD [seq$dseq (1-4294967295)$arg]]",
1312 "Name of a prefix list\n"
1313 "sequence number of an entry\n"
1314 "Sequence number\n")
1316 enum display_type dtype
= normal_display
;
1318 dtype
= sequential_display
;
1320 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, arg_str
, dtype
);
1323 DEFPY (show_ipv6_prefix_list_prefix
,
1324 show_ipv6_prefix_list_prefix_cmd
,
1325 "show ipv6 prefix-list WORD X:X::X:X/M$prefix [longer$dl|first-match$dfm]",
1329 "Name of a prefix list\n"
1330 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n"
1331 "Lookup longer prefix\n"
1332 "First matched prefix\n")
1334 enum display_type dtype
= normal_display
;
1336 dtype
= longer_display
;
1338 dtype
= first_match_display
;
1340 return vty_show_prefix_list_prefix(vty
, AFI_IP6
, prefix_list
,
1344 DEFPY (show_ipv6_prefix_list_summary
,
1345 show_ipv6_prefix_list_summary_cmd
,
1346 "show ipv6 prefix-list summary [WORD$prefix-list]",
1350 "Summary of prefix lists\n"
1351 "Name of a prefix list\n")
1353 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1357 DEFPY (show_ipv6_prefix_list_detail
,
1358 show_ipv6_prefix_list_detail_cmd
,
1359 "show ipv6 prefix-list detail [WORD$prefix-list]",
1363 "Detail of prefix lists\n"
1364 "Name of a prefix list\n")
1366 return vty_show_prefix_list(vty
, AFI_IP6
, prefix_list
, NULL
,
1370 DEFPY (clear_ipv6_prefix_list
,
1371 clear_ipv6_prefix_list_cmd
,
1372 "clear ipv6 prefix-list [WORD [X:X::X:X/M$prefix]]",
1376 "Name of a prefix list\n"
1377 "IPv6 prefix <network>/<length>, e.g., 3ffe::/16\n")
1379 return vty_clear_prefix_list(vty
, AFI_IP6
, prefix_list
, prefix_str
);
1382 struct stream
*prefix_bgp_orf_entry(struct stream
*s
, struct prefix_list
*plist
,
1383 uint8_t init_flag
, uint8_t permit_flag
,
1386 struct prefix_list_entry
*pentry
;
1391 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1392 uint8_t flag
= init_flag
;
1393 struct prefix
*p
= &pentry
->prefix
;
1395 flag
|= (pentry
->type
== PREFIX_PERMIT
? permit_flag
1397 stream_putc(s
, flag
);
1398 stream_putl(s
, (uint32_t)pentry
->seq
);
1399 stream_putc(s
, (uint8_t)pentry
->ge
);
1400 stream_putc(s
, (uint8_t)pentry
->le
);
1401 stream_put_prefix(s
, p
);
1407 int prefix_bgp_orf_set(char *name
, afi_t afi
, struct orf_prefix
*orfp
,
1408 int permit
, int set
)
1410 struct prefix_list
*plist
;
1411 struct prefix_list_entry
*pentry
;
1413 /* ge and le value check */
1414 if (orfp
->ge
&& orfp
->ge
<= orfp
->p
.prefixlen
)
1415 return CMD_WARNING_CONFIG_FAILED
;
1416 if (orfp
->le
&& orfp
->le
<= orfp
->p
.prefixlen
)
1417 return CMD_WARNING_CONFIG_FAILED
;
1418 if (orfp
->le
&& orfp
->ge
> orfp
->le
)
1419 return CMD_WARNING_CONFIG_FAILED
;
1421 if (orfp
->ge
&& orfp
->le
== (afi
== AFI_IP
? 32 : 128))
1424 plist
= prefix_list_get(afi
, 1, name
);
1426 return CMD_WARNING_CONFIG_FAILED
;
1428 apply_mask(&orfp
->p
);
1431 pentry
= prefix_list_entry_make(
1432 &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1433 orfp
->seq
, orfp
->le
, orfp
->ge
, false);
1435 if (prefix_entry_dup_check(plist
, pentry
)) {
1436 prefix_list_entry_free(pentry
);
1437 return CMD_WARNING_CONFIG_FAILED
;
1440 prefix_list_entry_add(plist
, pentry
);
1442 pentry
= prefix_list_entry_lookup(
1443 plist
, &orfp
->p
, (permit
? PREFIX_PERMIT
: PREFIX_DENY
),
1444 orfp
->seq
, orfp
->le
, orfp
->ge
);
1447 return CMD_WARNING_CONFIG_FAILED
;
1449 prefix_list_entry_delete(plist
, pentry
, 1);
1455 void prefix_bgp_orf_remove_all(afi_t afi
, char *name
)
1457 struct prefix_list
*plist
;
1459 plist
= prefix_bgp_orf_lookup(afi
, name
);
1461 prefix_list_delete(plist
);
1464 /* return prefix count */
1465 int prefix_bgp_show_prefix_list(struct vty
*vty
, afi_t afi
, char *name
,
1468 struct prefix_list
*plist
;
1469 struct prefix_list_entry
*pentry
;
1470 json_object
*json
= NULL
;
1471 json_object
*json_prefix
= NULL
;
1472 json_object
*json_list
= NULL
;
1474 plist
= prefix_bgp_orf_lookup(afi
, name
);
1479 return plist
->count
;
1482 json
= json_object_new_object();
1483 json_prefix
= json_object_new_object();
1484 json_list
= json_object_new_object();
1486 json_object_int_add(json_prefix
, "prefixListCounter",
1488 json_object_string_add(json_prefix
, "prefixListName",
1491 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1492 struct prefix
*p
= &pentry
->prefix
;
1496 snprintf(buf_a
, sizeof(buf_a
), "%s/%d",
1497 inet_ntop(p
->family
, p
->u
.val
, buf_b
, BUFSIZ
),
1500 json_object_int_add(json_list
, "seq", pentry
->seq
);
1501 json_object_string_add(json_list
, "seqPrefixListType",
1502 prefix_list_type_str(pentry
));
1505 json_object_int_add(json_list
, "ge",
1508 json_object_int_add(json_list
, "le",
1511 json_object_object_add(json_prefix
, buf_a
, json_list
);
1514 json_object_object_add(json
, "ipPrefixList",
1517 json_object_object_add(json
, "ipv6PrefixList",
1520 vty_out(vty
, "%s\n", json_object_to_json_string_ext(
1521 json
, JSON_C_TO_STRING_PRETTY
));
1522 json_object_free(json
);
1524 vty_out(vty
, "ip%s prefix-list %s: %d entries\n",
1525 afi
== AFI_IP
? "" : "v6", plist
->name
, plist
->count
);
1527 for (pentry
= plist
->head
; pentry
; pentry
= pentry
->next
) {
1528 struct prefix
*p
= &pentry
->prefix
;
1531 vty_out(vty
, " seq %" PRId64
" %s %s/%d",
1533 prefix_list_type_str(pentry
),
1534 inet_ntop(p
->family
, p
->u
.val
, buf
, BUFSIZ
),
1538 vty_out(vty
, " ge %d", pentry
->ge
);
1540 vty_out(vty
, " le %d", pentry
->le
);
1545 return plist
->count
;
1548 static void prefix_list_reset_afi(afi_t afi
, int orf
)
1550 struct prefix_list
*plist
;
1551 struct prefix_list
*next
;
1552 struct prefix_master
*master
;
1554 master
= prefix_master_get(afi
, orf
);
1558 for (plist
= master
->num
.head
; plist
; plist
= next
) {
1560 prefix_list_delete(plist
);
1562 for (plist
= master
->str
.head
; plist
; plist
= next
) {
1564 prefix_list_delete(plist
);
1567 assert(master
->num
.head
== NULL
);
1568 assert(master
->num
.tail
== NULL
);
1570 assert(master
->str
.head
== NULL
);
1571 assert(master
->str
.tail
== NULL
);
1573 master
->seqnum
= true;
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 for (plist
= master
->str
.head
; plist
; plist
= plist
->next
)
1595 vector_set(comps
, XSTRDUP(MTYPE_COMPLETION
, plist
->name
));
1596 for (plist
= master
->num
.head
; plist
; plist
= plist
->next
)
1597 vector_set(comps
, XSTRDUP(MTYPE_COMPLETION
, plist
->name
));
1600 static void plist_autocomplete(vector comps
, struct cmd_token
*token
)
1602 plist_autocomplete_afi(AFI_IP
, comps
, token
);
1603 plist_autocomplete_afi(AFI_IP6
, comps
, token
);
1606 static const struct cmd_variable_handler plist_var_handlers
[] = {
1607 {/* "prefix-list WORD" */
1608 .varname
= "prefix_list",
1609 .completions
= plist_autocomplete
},
1610 {.completions
= NULL
}};
1613 static void prefix_list_init_ipv4(void)
1615 install_node(&prefix_node
);
1617 install_element(CONFIG_NODE
, &ip_prefix_list_sequence_number_cmd
);
1619 install_element(VIEW_NODE
, &show_ip_prefix_list_cmd
);
1620 install_element(VIEW_NODE
, &show_ip_prefix_list_prefix_cmd
);
1621 install_element(VIEW_NODE
, &show_ip_prefix_list_summary_cmd
);
1622 install_element(VIEW_NODE
, &show_ip_prefix_list_detail_cmd
);
1624 install_element(ENABLE_NODE
, &clear_ip_prefix_list_cmd
);
1627 /* Prefix-list node. */
1628 static struct cmd_node prefix_ipv6_node
= {
1629 .name
= "ipv6 prefix list",
1630 .node
= PREFIX_IPV6_NODE
,
1634 static void prefix_list_init_ipv6(void)
1636 install_node(&prefix_ipv6_node
);
1638 install_element(CONFIG_NODE
, &ipv6_prefix_list_sequence_number_cmd
);
1640 install_element(VIEW_NODE
, &show_ipv6_prefix_list_cmd
);
1641 install_element(VIEW_NODE
, &show_ipv6_prefix_list_prefix_cmd
);
1642 install_element(VIEW_NODE
, &show_ipv6_prefix_list_summary_cmd
);
1643 install_element(VIEW_NODE
, &show_ipv6_prefix_list_detail_cmd
);
1645 install_element(ENABLE_NODE
, &clear_ipv6_prefix_list_cmd
);
1648 void prefix_list_init(void)
1650 cmd_variable_handler_register(plist_var_handlers
);
1652 prefix_list_init_ipv4();
1653 prefix_list_init_ipv6();
1656 void prefix_list_reset(void)
1658 prefix_list_reset_afi(AFI_IP
, 0);
1659 prefix_list_reset_afi(AFI_IP6
, 0);
1660 prefix_list_reset_afi(AFI_IP
, 1);
1661 prefix_list_reset_afi(AFI_IP6
, 1);