From af8568a8700b83f4d1946b7075fa3eac96d1d5b6 Mon Sep 17 00:00:00 2001 From: Maria Matejka Date: Wed, 16 Mar 2022 10:22:49 +0100 Subject: Minor fix: f_val literals should always have named struct fields --- nest/a-path.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'nest/a-path.c') diff --git a/nest/a-path.c b/nest/a-path.c index 2e34a3d1..badbc911 100644 --- a/nest/a-path.c +++ b/nest/a-path.c @@ -591,7 +591,7 @@ as_path_match_set(const struct adata *path, const struct f_tree *set) p += 2; for (i=0; i Date: Thu, 31 Mar 2022 19:09:38 +0200 Subject: Splitting route data structures out to lib --- conf/cf-lex.l | 2 +- conf/conf.c | 2 +- conf/confbase.Y | 2 +- filter/data.c | 2 +- filter/f-util.c | 2 +- filter/filter.c | 2 +- filter/filter.h | 2 +- lib/event_test.c | 2 +- lib/route.h | 332 +++++++++++++++++++++++++ nest/a-path.c | 2 +- nest/a-path_test.c | 2 +- nest/a-set.c | 2 +- nest/a-set_test.c | 2 +- nest/attrs.h | 2 +- nest/cmds.c | 2 +- nest/proto.c | 2 +- nest/protocol.h | 2 +- nest/route.h | 639 ------------------------------------------------- nest/rt-attr.c | 21 +- nest/rt-dev.c | 2 +- nest/rt-fib.c | 2 +- nest/rt-show.c | 2 +- nest/rt-table.c | 2 +- nest/rt.h | 343 ++++++++++++++++++++++++++ proto/babel/babel.h | 2 +- proto/bfd/bfd.h | 2 +- proto/bgp/attrs.c | 2 +- proto/bgp/bgp.c | 2 +- proto/bgp/bgp.h | 2 +- proto/bgp/packets.c | 2 +- proto/mrt/mrt.h | 2 +- proto/ospf/ospf.h | 2 +- proto/perf/perf.c | 2 +- proto/pipe/pipe.c | 2 +- proto/radv/radv.h | 2 +- proto/rip/rip.h | 2 +- proto/rpki/rpki.h | 2 +- proto/static/static.c | 2 +- proto/static/static.h | 2 +- sysdep/bsd/krt-sock.c | 2 +- sysdep/linux/netlink.c | 2 +- sysdep/unix/krt.c | 2 +- sysdep/unix/main.c | 2 +- test/bt-utils.c | 2 +- 44 files changed, 716 insertions(+), 699 deletions(-) create mode 100644 lib/route.h delete mode 100644 nest/route.h create mode 100644 nest/rt.h (limited to 'nest/a-path.c') diff --git a/conf/cf-lex.l b/conf/cf-lex.l index b9457a83..75e1ceeb 100644 --- a/conf/cf-lex.l +++ b/conf/cf-lex.l @@ -42,7 +42,7 @@ #define PARSER 1 #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "filter/filter.h" #include "filter/f-inst.h" diff --git a/conf/conf.c b/conf/conf.c index a2b01667..0230053b 100644 --- a/conf/conf.c +++ b/conf/conf.c @@ -46,7 +46,7 @@ #undef LOCAL_DEBUG #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "lib/resource.h" diff --git a/conf/confbase.Y b/conf/confbase.Y index 753df325..3fdacb12 100644 --- a/conf/confbase.Y +++ b/conf/confbase.Y @@ -18,7 +18,7 @@ CF_HDR #include "lib/string.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/bfd.h" #include "nest/cli.h" #include "filter/filter.h" diff --git a/filter/data.c b/filter/data.c index feb8c8bb..87ef4ff1 100644 --- a/filter/data.c +++ b/filter/data.c @@ -16,7 +16,7 @@ #include "lib/unaligned.h" #include "lib/net.h" #include "lib/ip.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "nest/attrs.h" diff --git a/filter/f-util.c b/filter/f-util.c index 79cf3452..83ae01f6 100644 --- a/filter/f-util.c +++ b/filter/f-util.c @@ -13,7 +13,7 @@ #include "filter/f-inst.h" #include "lib/idm.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #define P(a,b) ((a<<8) | b) diff --git a/filter/filter.c b/filter/filter.c index 7004b96d..31ae79fe 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -35,7 +35,7 @@ #include "lib/ip.h" #include "lib/net.h" #include "lib/flowspec.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "nest/attrs.h" diff --git a/filter/filter.h b/filter/filter.h index e9c9d917..8ce6c1e0 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -13,7 +13,7 @@ #include "lib/resource.h" #include "lib/ip.h" #include "lib/macro.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" /* Possible return values of filter execution */ diff --git a/lib/event_test.c b/lib/event_test.c index e1fbea8f..e14d0b95 100644 --- a/lib/event_test.c +++ b/lib/event_test.c @@ -15,7 +15,7 @@ #include "nest/locks.h" #include "sysdep/unix/unix.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #define MAX_NUM 4 diff --git a/lib/route.h b/lib/route.h new file mode 100644 index 00000000..47355abc --- /dev/null +++ b/lib/route.h @@ -0,0 +1,332 @@ +/* + * BIRD Internet Routing Daemon -- Routing data structures + * + * (c) 1998--2000 Martin Mares + * (c) 2022 Maria Matejka + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_LIB_ROUTE_H_ +#define _BIRD_LIB_ROUTE_H_ + +struct network; +struct proto; +struct cli; + +typedef struct rte { + struct rte *next; + struct network *net; /* Network this RTE belongs to */ + struct rte_src *src; /* Route source that created the route */ + struct channel *sender; /* Channel used to send the route to the routing table */ + struct rta *attrs; /* Attributes of this route */ + u32 id; /* Table specific route id */ + byte flags; /* Flags (REF_...) */ + byte pflags; /* Protocol-specific flags */ + btime lastmod; /* Last modified */ +} rte; + +#define REF_COW 1 /* Copy this rte on write */ +#define REF_FILTERED 2 /* Route is rejected by import filter */ +#define REF_STALE 4 /* Route is stale in a refresh cycle */ +#define REF_DISCARD 8 /* Route is scheduled for discard */ +#define REF_MODIFY 16 /* Route is scheduled for modify */ + +/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */ +static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); } + +/* Route just has REF_FILTERED flag */ +static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); } + +struct rte_src { + struct rte_src *next; /* Hash chain */ + struct proto *proto; /* Protocol the source is based on */ + u32 private_id; /* Private ID, assigned by the protocol */ + u32 global_id; /* Globally unique ID of the source */ + unsigned uc; /* Use count */ +}; + + +struct rte_src *rt_find_source(struct proto *p, u32 id); +struct rte_src *rt_get_source(struct proto *p, u32 id); +static inline void rt_lock_source(struct rte_src *src) { src->uc++; } +static inline void rt_unlock_source(struct rte_src *src) { src->uc--; } +void rt_prune_sources(void); + +/* + * Route Attributes + * + * Beware: All standard BGP attributes must be represented here instead + * of making them local to the route. This is needed to ensure proper + * construction of BGP route attribute lists. + */ + +/* Nexthop structure */ +struct nexthop { + ip_addr gw; /* Next hop */ + struct iface *iface; /* Outgoing interface */ + struct nexthop *next; + byte flags; + byte weight; + byte labels_orig; /* Number of labels before hostentry was applied */ + byte labels; /* Number of all labels */ + u32 label[0]; +}; + +#define RNF_ONLINK 0x1 /* Gateway is onlink regardless of IP ranges */ + + +typedef struct rta { + struct rta *next, **pprev; /* Hash chain */ + u32 uc; /* Use count */ + u32 hash_key; /* Hash over important fields */ + struct ea_list *eattrs; /* Extended Attribute chain */ + struct hostentry *hostentry; /* Hostentry for recursive next-hops */ + ip_addr from; /* Advertising router */ + u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */ + u16 cached:1; /* Are attributes cached? */ + u16 source:7; /* Route source (RTS_...) */ + u16 scope:4; /* Route scope (SCOPE_... -- see ip.h) */ + u16 dest:4; /* Route destination type (RTD_...) */ + word pref; + struct nexthop nh; /* Next hop */ +} rta; + +#define RTS_STATIC 1 /* Normal static route */ +#define RTS_INHERIT 2 /* Route inherited from kernel */ +#define RTS_DEVICE 3 /* Device route */ +#define RTS_STATIC_DEVICE 4 /* Static device route */ +#define RTS_REDIRECT 5 /* Learned via redirect */ +#define RTS_RIP 6 /* RIP route */ +#define RTS_OSPF 7 /* OSPF route */ +#define RTS_OSPF_IA 8 /* OSPF inter-area route */ +#define RTS_OSPF_EXT1 9 /* OSPF external route type 1 */ +#define RTS_OSPF_EXT2 10 /* OSPF external route type 2 */ +#define RTS_BGP 11 /* BGP route */ +#define RTS_PIPE 12 /* Inter-table wormhole */ +#define RTS_BABEL 13 /* Babel route */ +#define RTS_RPKI 14 /* Route Origin Authorization */ +#define RTS_PERF 15 /* Perf checker */ +#define RTS_MAX 16 + +#define RTD_NONE 0 /* Undefined next hop */ +#define RTD_UNICAST 1 /* Next hop is neighbor router */ +#define RTD_BLACKHOLE 2 /* Silently drop packets */ +#define RTD_UNREACHABLE 3 /* Reject as unreachable */ +#define RTD_PROHIBIT 4 /* Administratively prohibited */ +#define RTD_MAX 5 + +#define IGP_METRIC_UNKNOWN 0x80000000 /* Default igp_metric used when no other + protocol-specific metric is availabe */ + + +extern const char * rta_dest_names[RTD_MAX]; + +static inline const char *rta_dest_name(uint n) +{ return (n < RTD_MAX) ? rta_dest_names[n] : "???"; } + +/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */ +static inline int rte_is_reachable(rte *r) +{ return r->attrs->dest == RTD_UNICAST; } + + +/* + * Extended Route Attributes + */ + +typedef struct eattr { + word id; /* EA_CODE(PROTOCOL_..., protocol-dependent ID) */ + byte flags; /* Protocol-dependent flags */ + byte type:5; /* Attribute type */ + byte originated:1; /* The attribute has originated locally */ + byte fresh:1; /* An uncached attribute (e.g. modified in export filter) */ + byte undef:1; /* Explicitly undefined */ + + union bval u; +} eattr; + + +#define EA_CODE(proto,id) (((proto) << 8) | (id)) +#define EA_ID(ea) ((ea) & 0xff) +#define EA_PROTO(ea) ((ea) >> 8) +#define EA_CUSTOM(id) ((id) | EA_CUSTOM_BIT) +#define EA_IS_CUSTOM(ea) ((ea) & EA_CUSTOM_BIT) +#define EA_CUSTOM_ID(ea) ((ea) & ~EA_CUSTOM_BIT) + +const char *ea_custom_name(uint ea); + +#define EA_GEN_IGP_METRIC EA_CODE(PROTOCOL_NONE, 0) + +#define EA_CODE_MASK 0xffff +#define EA_CUSTOM_BIT 0x8000 +#define EA_ALLOW_UNDEF 0x10000 /* ea_find: allow EAF_TYPE_UNDEF */ +#define EA_BIT(n) ((n) << 24) /* Used in bitfield accessors */ +#define EA_BIT_GET(ea) ((ea) >> 24) + +typedef struct adata { + uint length; /* Length of data */ + byte data[0]; +} adata; + +extern const adata null_adata; /* adata of length 0 */ + +static inline struct adata * +lp_alloc_adata(struct linpool *pool, uint len) +{ + struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len); + ad->length = len; + return ad; +} + +static inline int adata_same(const struct adata *a, const struct adata *b) +{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); } + + +typedef struct ea_list { + struct ea_list *next; /* In case we have an override list */ + byte flags; /* Flags: EALF_... */ + byte rfu; + word count; /* Number of attributes */ + eattr attrs[0]; /* Attribute definitions themselves */ +} ea_list; + +#define EALF_SORTED 1 /* Attributes are sorted by code */ +#define EALF_BISECT 2 /* Use interval bisection for searching */ +#define EALF_CACHED 4 /* Attributes belonging to cached rta */ + +struct ea_walk_state { + ea_list *eattrs; /* Ccurrent ea_list, initially set by caller */ + eattr *ea; /* Current eattr, initially NULL */ + u32 visited[4]; /* Bitfield, limiting max to 128 */ +}; + +eattr *ea_find(ea_list *, unsigned ea); +eattr *ea_walk(struct ea_walk_state *s, uint id, uint max); + +/** + * ea_get_int - fetch an integer attribute + * @e: attribute list + * @id: attribute ID + * @def: default value + * + * This function is a shortcut for retrieving a value of an integer attribute + * by calling ea_find() to find the attribute, extracting its value or returning + * a provided default if no such attribute is present. + */ +static inline u32 +ea_get_int(ea_list *e, unsigned id, u32 def) +{ + eattr *a = ea_find(e, id); + return a ? a->u.data : def; +} + +void ea_dump(ea_list *); +void ea_sort(ea_list *); /* Sort entries in all sub-lists */ +unsigned ea_scan(ea_list *); /* How many bytes do we need for merged ea_list */ +void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */ +int ea_same(ea_list *x, ea_list *y); /* Test whether two ea_lists are identical */ +uint ea_hash(ea_list *e); /* Calculate 16-bit hash value */ +ea_list *ea_append(ea_list *to, ea_list *what); +void ea_format_bitfield(const struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max); + +#define ea_normalize(ea) do { \ + if (ea->next) { \ + ea_list *t = alloca(ea_scan(ea)); \ + ea_merge(ea, t); \ + ea = t; \ + } \ + ea_sort(ea); \ + if (ea->count == 0) \ + ea = NULL; \ +} while(0) \ + +struct ea_one_attr_list { + ea_list l; + eattr a; +}; + +static inline eattr * +ea_set_attr(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, union bval val) +{ + struct ea_one_attr_list *ea = lp_alloc(pool, sizeof(*ea)); + *ea = (struct ea_one_attr_list) { + .l.flags = EALF_SORTED, + .l.count = 1, + .l.next = *to, + + .a.id = id, + .a.type = type, + .a.flags = flags, + }; + + ea->a.u = val; + *to = &ea->l; + + return &ea->a; +} + +static inline void +ea_unset_attr(ea_list **to, struct linpool *pool, _Bool local, uint code) +{ + struct ea_one_attr_list *ea = lp_alloc(pool, sizeof(*ea)); + *ea = (struct ea_one_attr_list) { + .l.flags = EALF_SORTED, + .l.count = 1, + .l.next = *to, + .a.id = code, + .a.fresh = local, + .a.originated = local, + .a.undef = 1, + }; + + *to = &ea->l; +} + +static inline void +ea_set_attr_u32(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, u32 data) +{ + union bval bv = { .data = data }; + ea_set_attr(to, pool, id, flags, type, bv); +} + +static inline void +ea_set_attr_data(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, void *data, uint len) +{ + struct adata *a = lp_alloc_adata(pool, len); + memcpy(a->data, data, len); + union bval bv = { .ptr = a, }; + ea_set_attr(to, pool, id, flags, type, bv); +} + + +#define NEXTHOP_MAX_SIZE (sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK) + +static inline size_t nexthop_size(const struct nexthop *nh) +{ return sizeof(struct nexthop) + sizeof(u32)*nh->labels; } +int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath nexthops */ +static inline int nexthop_same(struct nexthop *x, struct nexthop *y) +{ return (x == y) || nexthop__same(x, y); } +struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp); +struct nexthop *nexthop_sort(struct nexthop *x); +static inline void nexthop_link(struct rta *a, struct nexthop *from) +{ memcpy(&a->nh, from, nexthop_size(from)); } +void nexthop_insert(struct nexthop **n, struct nexthop *y); +int nexthop_is_sorted(struct nexthop *x); + +void rta_init(void); +static inline size_t rta_size(const rta *a) { return sizeof(rta) + sizeof(u32)*a->nh.labels; } +#define RTA_MAX_SIZE (sizeof(rta) + sizeof(u32)*MPLS_MAX_LABEL_STACK) +rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */ +static inline int rta_is_cached(rta *r) { return r->cached; } +static inline rta *rta_clone(rta *r) { r->uc++; return r; } +void rta__free(rta *r); +static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); } +rta *rta_do_cow(rta *o, linpool *lp); +static inline rta * rta_cow(rta *r, linpool *lp) { return rta_is_cached(r) ? rta_do_cow(r, lp) : r; } +void rta_dump(rta *); +void rta_dump_all(void); +void rta_show(struct cli *, rta *); + +u32 rt_get_igp_metric(rte *rt); + +#endif diff --git a/nest/a-path.c b/nest/a-path.c index badbc911..64504c93 100644 --- a/nest/a-path.c +++ b/nest/a-path.c @@ -8,7 +8,7 @@ */ #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "lib/resource.h" #include "lib/unaligned.h" diff --git a/nest/a-path_test.c b/nest/a-path_test.c index e007a450..a6b4d3d8 100644 --- a/nest/a-path_test.c +++ b/nest/a-path_test.c @@ -9,7 +9,7 @@ #include "test/birdtest.h" #include "test/bt-utils.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "lib/resource.h" diff --git a/nest/a-set.c b/nest/a-set.c index 71fbac94..93f6431e 100644 --- a/nest/a-set.c +++ b/nest/a-set.c @@ -10,7 +10,7 @@ #include #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "lib/resource.h" #include "lib/string.h" diff --git a/nest/a-set_test.c b/nest/a-set_test.c index 904e6764..daa6ab74 100644 --- a/nest/a-set_test.c +++ b/nest/a-set_test.c @@ -10,7 +10,7 @@ #include "test/bt-utils.h" #include "lib/net.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "lib/resource.h" diff --git a/nest/attrs.h b/nest/attrs.h index ef2b95e6..e0595846 100644 --- a/nest/attrs.h +++ b/nest/attrs.h @@ -11,7 +11,7 @@ #include #include "lib/unaligned.h" -#include "nest/route.h" +#include "lib/route.h" /* a-path.c */ diff --git a/nest/cmds.c b/nest/cmds.c index 8481bf96..3e59cb6f 100644 --- a/nest/cmds.c +++ b/nest/cmds.c @@ -8,7 +8,7 @@ #include "nest/bird.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "conf/conf.h" #include "nest/cmds.h" diff --git a/nest/proto.c b/nest/proto.c index c6bda73b..95c319db 100644 --- a/nest/proto.c +++ b/nest/proto.c @@ -16,7 +16,7 @@ #include "lib/timer.h" #include "lib/string.h" #include "conf/conf.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/iface.h" #include "nest/cli.h" #include "filter/filter.h" diff --git a/nest/protocol.h b/nest/protocol.h index d0810a8f..7fb08992 100644 --- a/nest/protocol.h +++ b/nest/protocol.h @@ -12,7 +12,7 @@ #include "lib/lists.h" #include "lib/resource.h" #include "lib/event.h" -#include "nest/route.h" +#include "nest/rt.h" #include "conf/conf.h" struct iface; diff --git a/nest/route.h b/nest/route.h deleted file mode 100644 index c6d30148..00000000 --- a/nest/route.h +++ /dev/null @@ -1,639 +0,0 @@ -/* - * BIRD Internet Routing Daemon -- Routing Table - * - * (c) 1998--2000 Martin Mares - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#ifndef _BIRD_ROUTE_H_ -#define _BIRD_ROUTE_H_ - -#include "lib/lists.h" -#include "lib/bitmap.h" -#include "lib/resource.h" -#include "lib/net.h" -#include "lib/type.h" -#include "lib/fib.h" - -struct ea_list; -struct protocol; -struct proto; -struct rte_src; -struct symbol; -struct timer; -struct filter; -struct f_trie; -struct f_trie_walk_state; -struct cli; - -/* - * Master Routing Tables. Generally speaking, each of them contains a FIB - * with each entry pointing to a list of route entries representing routes - * to given network (with the selected one at the head). - * - * Each of the RTE's contains variable data (the preference and protocol-dependent - * metrics) and a pointer to a route attribute block common for many routes). - * - * It's guaranteed that there is at most one RTE for every (prefix,proto) pair. - */ - -struct rtable_config { - node n; - char *name; - struct rtable *table; - struct proto_config *krt_attached; /* Kernel syncer attached to this table */ - uint addr_type; /* Type of address data stored in table (NET_*) */ - int gc_max_ops; /* Maximum number of operations before GC is run */ - int gc_min_time; /* Minimum time between two consecutive GC runs */ - byte sorted; /* Routes of network are sorted according to rte_better() */ - byte internal; /* Internal table of a protocol */ - byte trie_used; /* Rtable has attached trie */ - btime min_settle_time; /* Minimum settle time for notifications */ - btime max_settle_time; /* Maximum settle time for notifications */ -}; - -typedef struct rtable { - resource r; - node n; /* Node in list of all tables */ - pool *rp; /* Resource pool to allocate everything from, including itself */ - struct fib fib; - struct f_trie *trie; /* Trie of prefixes defined in fib */ - char *name; /* Name of this table */ - list channels; /* List of attached channels (struct channel) */ - uint addr_type; /* Type of address data stored in table (NET_*) */ - int pipe_busy; /* Pipe loop detection */ - int use_count; /* Number of protocols using this table */ - u32 rt_count; /* Number of routes in the table */ - - byte internal; /* Internal table of a protocol */ - - struct hmap id_map; - struct hostcache *hostcache; - struct rtable_config *config; /* Configuration of this table */ - struct config *deleted; /* Table doesn't exist in current configuration, - * delete as soon as use_count becomes 0 and remove - * obstacle from this routing table. - */ - struct event *rt_event; /* Routing table event */ - btime last_rt_change; /* Last time when route changed */ - btime base_settle_time; /* Start time of rtable settling interval */ - btime gc_time; /* Time of last GC */ - int gc_counter; /* Number of operations since last GC */ - byte prune_state; /* Table prune state, 1 -> scheduled, 2-> running */ - byte prune_trie; /* Prune prefix trie during next table prune */ - byte hcu_scheduled; /* Hostcache update is scheduled */ - byte nhu_state; /* Next Hop Update state */ - struct fib_iterator prune_fit; /* Rtable prune FIB iterator */ - struct fib_iterator nhu_fit; /* Next Hop Update FIB iterator */ - struct f_trie *trie_new; /* New prefix trie defined during pruning */ - struct f_trie *trie_old; /* Old prefix trie waiting to be freed */ - u32 trie_lock_count; /* Prefix trie locked by walks */ - u32 trie_old_lock_count; /* Old prefix trie locked by walks */ - - list subscribers; /* Subscribers for notifications */ - struct timer *settle_timer; /* Settle time for notifications */ - list flowspec_links; /* List of flowspec links, src for NET_IPx and dst for NET_FLOWx */ - struct f_trie *flowspec_trie; /* Trie for evaluation of flowspec notifications */ -} rtable; - -struct rt_subscription { - node n; - rtable *tab; - void (*hook)(struct rt_subscription *b); - void *data; -}; - -struct rt_flowspec_link { - node n; - rtable *src; - rtable *dst; - u32 uc; -}; - -#define NHU_CLEAN 0 -#define NHU_SCHEDULED 1 -#define NHU_RUNNING 2 -#define NHU_DIRTY 3 - -typedef struct network { - struct rte *routes; /* Available routes for this network */ - struct fib_node n; /* FIB flags reserved for kernel syncer */ -} net; - -struct hostcache { - slab *slab; /* Slab holding all hostentries */ - struct hostentry **hash_table; /* Hash table for hostentries */ - unsigned hash_order, hash_shift; - unsigned hash_max, hash_min; - unsigned hash_items; - linpool *lp; /* Linpool for trie */ - struct f_trie *trie; /* Trie of prefixes that might affect hostentries */ - list hostentries; /* List of all hostentries */ - byte update_hostcache; -}; - -struct hostentry { - node ln; - ip_addr addr; /* IP address of host, part of key */ - ip_addr link; /* (link-local) IP address of host, used as gw - if host is directly attached */ - struct rtable *tab; /* Dependent table, part of key */ - struct hostentry *next; /* Next in hash chain */ - unsigned hash_key; /* Hash key */ - unsigned uc; /* Use count */ - struct rta *src; /* Source rta entry */ - byte dest; /* Chosen route destination type (RTD_...) */ - byte nexthop_linkable; /* Nexthop list is completely non-device */ - u32 igp_metric; /* Chosen route IGP metric */ -}; - -typedef struct rte { - struct rte *next; - net *net; /* Network this RTE belongs to */ - struct rte_src *src; /* Route source that created the route */ - struct channel *sender; /* Channel used to send the route to the routing table */ - struct rta *attrs; /* Attributes of this route */ - u32 id; /* Table specific route id */ - byte flags; /* Flags (REF_...) */ - byte pflags; /* Protocol-specific flags */ - btime lastmod; /* Last modified */ -} rte; - -#define REF_COW 1 /* Copy this rte on write */ -#define REF_FILTERED 2 /* Route is rejected by import filter */ -#define REF_STALE 4 /* Route is stale in a refresh cycle */ -#define REF_DISCARD 8 /* Route is scheduled for discard */ -#define REF_MODIFY 16 /* Route is scheduled for modify */ - -/* Route is valid for propagation (may depend on other flags in the future), accepts NULL */ -static inline int rte_is_valid(rte *r) { return r && !(r->flags & REF_FILTERED); } - -/* Route just has REF_FILTERED flag */ -static inline int rte_is_filtered(rte *r) { return !!(r->flags & REF_FILTERED); } - - -/* Types of route announcement, also used as flags */ -#define RA_UNDEF 0 /* Undefined RA type */ -#define RA_OPTIMAL 1 /* Announcement of optimal route change */ -#define RA_ACCEPTED 2 /* Announcement of first accepted route */ -#define RA_ANY 3 /* Announcement of any route change */ -#define RA_MERGED 4 /* Announcement of optimal route merged with next ones */ - -/* Return value of preexport() callback */ -#define RIC_ACCEPT 1 /* Accepted by protocol */ -#define RIC_PROCESS 0 /* Process it through import filter */ -#define RIC_REJECT -1 /* Rejected by protocol */ -#define RIC_DROP -2 /* Silently dropped by protocol */ - -extern list routing_tables; -struct config; - -void rt_init(void); -void rt_preconfig(struct config *); -void rt_commit(struct config *new, struct config *old); -void rt_lock_table(rtable *); -void rt_unlock_table(rtable *); -struct f_trie * rt_lock_trie(rtable *tab); -void rt_unlock_trie(rtable *tab, struct f_trie *trie); -void rt_subscribe(rtable *tab, struct rt_subscription *s); -void rt_unsubscribe(struct rt_subscription *s); -void rt_flowspec_link(rtable *src, rtable *dst); -void rt_flowspec_unlink(rtable *src, rtable *dst); -rtable *rt_setup(pool *, struct rtable_config *); -static inline void rt_shutdown(rtable *r) { rfree(r->rp); } - -static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *) fib_find(&tab->fib, addr); } -static inline net *net_find_valid(rtable *tab, const net_addr *addr) -{ net *n = net_find(tab, addr); return (n && rte_is_valid(n->routes)) ? n : NULL; } -static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); } -net *net_get(rtable *tab, const net_addr *addr); -net *net_route(rtable *tab, const net_addr *n); -int net_roa_check(rtable *tab, const net_addr *n, u32 asn); -rte *rte_find(net *net, struct rte_src *src); -rte *rte_get_temp(struct rta *, struct rte_src *src); -void rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src); -/* rte_update() moved to protocol.h to avoid dependency conflicts */ -int rt_examine(rtable *t, net_addr *a, struct proto *p, const struct filter *filter); -rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent); -void rt_refresh_begin(rtable *t, struct channel *c); -void rt_refresh_end(rtable *t, struct channel *c); -void rt_modify_stale(rtable *t, struct channel *c); -void rt_schedule_prune(rtable *t); -void rte_dump(rte *); -void rte_free(rte *); -rte *rte_do_cow(rte *); -static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; } -rte *rte_cow_rta(rte *r, linpool *lp); -void rt_dump(rtable *); -void rt_dump_all(void); -int rt_feed_channel(struct channel *c); -void rt_feed_channel_abort(struct channel *c); -int rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src); -int rt_reload_channel(struct channel *c); -void rt_reload_channel_abort(struct channel *c); -void rt_prune_sync(rtable *t, int all); -int rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old, rte **old_exported, int refeed); -struct rtable_config *rt_new_table(struct symbol *s, uint addr_type); - -static inline int rt_is_ip(rtable *tab) -{ return (tab->addr_type == NET_IP4) || (tab->addr_type == NET_IP6); } - -static inline int rt_is_vpn(rtable *tab) -{ return (tab->addr_type == NET_VPN4) || (tab->addr_type == NET_VPN6); } - -static inline int rt_is_roa(rtable *tab) -{ return (tab->addr_type == NET_ROA4) || (tab->addr_type == NET_ROA6); } - -static inline int rt_is_flow(rtable *tab) -{ return (tab->addr_type == NET_FLOW4) || (tab->addr_type == NET_FLOW6); } - - -/* Default limit for ECMP next hops, defined in sysdep code */ -extern const int rt_default_ecmp; - -struct rt_show_data_rtable { - node n; - rtable *table; - struct channel *export_channel; -}; - -struct rt_show_data { - net_addr *addr; - list tables; - struct rt_show_data_rtable *tab; /* Iterator over table list */ - struct rt_show_data_rtable *last_table; /* Last table in output */ - struct fib_iterator fit; /* Iterator over networks in table */ - struct f_trie_walk_state *walk_state; /* Iterator over networks in trie */ - struct f_trie *walk_lock; /* Locked trie for walking */ - int verbose, tables_defined_by; - const struct filter *filter; - struct proto *show_protocol; - struct proto *export_protocol; - struct channel *export_channel; - struct config *running_on_config; - struct krt_proto *kernel; - int export_mode, addr_mode, primary_only, filtered, stats; - - int table_open; /* Iteration (fit) is open */ - int trie_walk; /* Current table is iterated using trie */ - int net_counter, rt_counter, show_counter, table_counter; - int net_counter_last, rt_counter_last, show_counter_last; -}; - -void rt_show(struct rt_show_data *); -struct rt_show_data_rtable * rt_show_add_table(struct rt_show_data *d, rtable *t); - -/* Value of table definition mode in struct rt_show_data */ -#define RSD_TDB_DEFAULT 0 /* no table specified */ -#define RSD_TDB_INDIRECT 0 /* show route ... protocol P ... */ -#define RSD_TDB_ALL RSD_TDB_SET /* show route ... table all ... */ -#define RSD_TDB_DIRECT RSD_TDB_SET | RSD_TDB_NMN /* show route ... table X table Y ... */ - -#define RSD_TDB_SET 0x1 /* internal: show empty tables */ -#define RSD_TDB_NMN 0x2 /* internal: need matching net */ - -/* Value of addr_mode */ -#define RSD_ADDR_EQUAL 1 /* Exact query - show route */ -#define RSD_ADDR_FOR 2 /* Longest prefix match - show route for */ -#define RSD_ADDR_IN 3 /* Interval query - show route in */ - -/* Value of export_mode in struct rt_show_data */ -#define RSEM_NONE 0 /* Export mode not used */ -#define RSEM_PREEXPORT 1 /* Routes ready for export, before filtering */ -#define RSEM_EXPORT 2 /* Routes accepted by export filter */ -#define RSEM_NOEXPORT 3 /* Routes rejected by export filter */ -#define RSEM_EXPORTED 4 /* Routes marked in export map */ - -/* - * Route Attributes - * - * Beware: All standard BGP attributes must be represented here instead - * of making them local to the route. This is needed to ensure proper - * construction of BGP route attribute lists. - */ - -/* Nexthop structure */ -struct nexthop { - ip_addr gw; /* Next hop */ - struct iface *iface; /* Outgoing interface */ - struct nexthop *next; - byte flags; - byte weight; - byte labels_orig; /* Number of labels before hostentry was applied */ - byte labels; /* Number of all labels */ - u32 label[0]; -}; - -#define RNF_ONLINK 0x1 /* Gateway is onlink regardless of IP ranges */ - - -struct rte_src { - struct rte_src *next; /* Hash chain */ - struct proto *proto; /* Protocol the source is based on */ - u32 private_id; /* Private ID, assigned by the protocol */ - u32 global_id; /* Globally unique ID of the source */ - unsigned uc; /* Use count */ -}; - - -typedef struct rta { - struct rta *next, **pprev; /* Hash chain */ - u32 uc; /* Use count */ - u32 hash_key; /* Hash over important fields */ - struct ea_list *eattrs; /* Extended Attribute chain */ - struct hostentry *hostentry; /* Hostentry for recursive next-hops */ - ip_addr from; /* Advertising router */ - u32 igp_metric; /* IGP metric to next hop (for iBGP routes) */ - u16 cached:1; /* Are attributes cached? */ - u16 source:7; /* Route source (RTS_...) */ - u16 scope:4; /* Route scope (SCOPE_... -- see ip.h) */ - u16 dest:4; /* Route destination type (RTD_...) */ - word pref; - struct nexthop nh; /* Next hop */ -} rta; - -#define RTS_STATIC 1 /* Normal static route */ -#define RTS_INHERIT 2 /* Route inherited from kernel */ -#define RTS_DEVICE 3 /* Device route */ -#define RTS_STATIC_DEVICE 4 /* Static device route */ -#define RTS_REDIRECT 5 /* Learned via redirect */ -#define RTS_RIP 6 /* RIP route */ -#define RTS_OSPF 7 /* OSPF route */ -#define RTS_OSPF_IA 8 /* OSPF inter-area route */ -#define RTS_OSPF_EXT1 9 /* OSPF external route type 1 */ -#define RTS_OSPF_EXT2 10 /* OSPF external route type 2 */ -#define RTS_BGP 11 /* BGP route */ -#define RTS_PIPE 12 /* Inter-table wormhole */ -#define RTS_BABEL 13 /* Babel route */ -#define RTS_RPKI 14 /* Route Origin Authorization */ -#define RTS_PERF 15 /* Perf checker */ -#define RTS_MAX 16 - -#define RTD_NONE 0 /* Undefined next hop */ -#define RTD_UNICAST 1 /* Next hop is neighbor router */ -#define RTD_BLACKHOLE 2 /* Silently drop packets */ -#define RTD_UNREACHABLE 3 /* Reject as unreachable */ -#define RTD_PROHIBIT 4 /* Administratively prohibited */ -#define RTD_MAX 5 - -#define IGP_METRIC_UNKNOWN 0x80000000 /* Default igp_metric used when no other - protocol-specific metric is availabe */ - - -extern const char * rta_dest_names[RTD_MAX]; - -static inline const char *rta_dest_name(uint n) -{ return (n < RTD_MAX) ? rta_dest_names[n] : "???"; } - -/* Route has regular, reachable nexthop (i.e. not RTD_UNREACHABLE and like) */ -static inline int rte_is_reachable(rte *r) -{ return r->attrs->dest == RTD_UNICAST; } - - -/* - * Extended Route Attributes - */ - -typedef struct eattr { - word id; /* EA_CODE(PROTOCOL_..., protocol-dependent ID) */ - byte flags; /* Protocol-dependent flags */ - byte type:5; /* Attribute type */ - byte originated:1; /* The attribute has originated locally */ - byte fresh:1; /* An uncached attribute (e.g. modified in export filter) */ - byte undef:1; /* Explicitly undefined */ - - union bval u; -} eattr; - - -#define EA_CODE(proto,id) (((proto) << 8) | (id)) -#define EA_ID(ea) ((ea) & 0xff) -#define EA_PROTO(ea) ((ea) >> 8) -#define EA_CUSTOM(id) ((id) | EA_CUSTOM_BIT) -#define EA_IS_CUSTOM(ea) ((ea) & EA_CUSTOM_BIT) -#define EA_CUSTOM_ID(ea) ((ea) & ~EA_CUSTOM_BIT) - -const char *ea_custom_name(uint ea); - -#define EA_GEN_IGP_METRIC EA_CODE(PROTOCOL_NONE, 0) - -#define EA_CODE_MASK 0xffff -#define EA_CUSTOM_BIT 0x8000 -#define EA_ALLOW_UNDEF 0x10000 /* ea_find: allow EAF_TYPE_UNDEF */ -#define EA_BIT(n) ((n) << 24) /* Used in bitfield accessors */ -#define EA_BIT_GET(ea) ((ea) >> 24) - -typedef struct adata { - uint length; /* Length of data */ - byte data[0]; -} adata; - -extern const adata null_adata; /* adata of length 0 */ - -static inline struct adata * -lp_alloc_adata(struct linpool *pool, uint len) -{ - struct adata *ad = lp_alloc(pool, sizeof(struct adata) + len); - ad->length = len; - return ad; -} - -static inline int adata_same(const struct adata *a, const struct adata *b) -{ return (a->length == b->length && !memcmp(a->data, b->data, a->length)); } - - -typedef struct ea_list { - struct ea_list *next; /* In case we have an override list */ - byte flags; /* Flags: EALF_... */ - byte rfu; - word count; /* Number of attributes */ - eattr attrs[0]; /* Attribute definitions themselves */ -} ea_list; - -#define EALF_SORTED 1 /* Attributes are sorted by code */ -#define EALF_BISECT 2 /* Use interval bisection for searching */ -#define EALF_CACHED 4 /* Attributes belonging to cached rta */ - -struct rte_src *rt_find_source(struct proto *p, u32 id); -struct rte_src *rt_get_source(struct proto *p, u32 id); -static inline void rt_lock_source(struct rte_src *src) { src->uc++; } -static inline void rt_unlock_source(struct rte_src *src) { src->uc--; } -void rt_prune_sources(void); - -struct ea_walk_state { - ea_list *eattrs; /* Ccurrent ea_list, initially set by caller */ - eattr *ea; /* Current eattr, initially NULL */ - u32 visited[4]; /* Bitfield, limiting max to 128 */ -}; - -eattr *ea_find(ea_list *, unsigned ea); -eattr *ea_walk(struct ea_walk_state *s, uint id, uint max); -u32 ea_get_int(ea_list *, unsigned ea, u32 def); -void ea_dump(ea_list *); -void ea_sort(ea_list *); /* Sort entries in all sub-lists */ -unsigned ea_scan(ea_list *); /* How many bytes do we need for merged ea_list */ -void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */ -int ea_same(ea_list *x, ea_list *y); /* Test whether two ea_lists are identical */ -uint ea_hash(ea_list *e); /* Calculate 16-bit hash value */ -ea_list *ea_append(ea_list *to, ea_list *what); -void ea_format_bitfield(const struct eattr *a, byte *buf, int bufsize, const char **names, int min, int max); - -#define ea_normalize(ea) do { \ - if (ea->next) { \ - ea_list *t = alloca(ea_scan(ea)); \ - ea_merge(ea, t); \ - ea = t; \ - } \ - ea_sort(ea); \ - if (ea->count == 0) \ - ea = NULL; \ -} while(0) \ - -struct ea_one_attr_list { - ea_list l; - eattr a; -}; - -static inline eattr * -ea_set_attr(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, union bval val) -{ - struct ea_one_attr_list *ea = lp_alloc(pool, sizeof(*ea)); - *ea = (struct ea_one_attr_list) { - .l.flags = EALF_SORTED, - .l.count = 1, - .l.next = *to, - - .a.id = id, - .a.type = type, - .a.flags = flags, - }; - - ea->a.u = val; - *to = &ea->l; - - return &ea->a; -} - -static inline void -ea_unset_attr(ea_list **to, struct linpool *pool, _Bool local, uint code) -{ - struct ea_one_attr_list *ea = lp_alloc(pool, sizeof(*ea)); - *ea = (struct ea_one_attr_list) { - .l.flags = EALF_SORTED, - .l.count = 1, - .l.next = *to, - .a.id = code, - .a.fresh = local, - .a.originated = local, - .a.undef = 1, - }; - - *to = &ea->l; -} - -static inline void -ea_set_attr_u32(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, u32 data) -{ - union bval bv = { .data = data }; - ea_set_attr(to, pool, id, flags, type, bv); -} - -static inline void -ea_set_attr_data(ea_list **to, struct linpool *pool, uint id, uint flags, uint type, void *data, uint len) -{ - struct adata *a = lp_alloc_adata(pool, len); - memcpy(a->data, data, len); - union bval bv = { .ptr = a, }; - ea_set_attr(to, pool, id, flags, type, bv); -} - - -#define NEXTHOP_MAX_SIZE (sizeof(struct nexthop) + sizeof(u32)*MPLS_MAX_LABEL_STACK) - -static inline size_t nexthop_size(const struct nexthop *nh) -{ return sizeof(struct nexthop) + sizeof(u32)*nh->labels; } -int nexthop__same(struct nexthop *x, struct nexthop *y); /* Compare multipath nexthops */ -static inline int nexthop_same(struct nexthop *x, struct nexthop *y) -{ return (x == y) || nexthop__same(x, y); } -struct nexthop *nexthop_merge(struct nexthop *x, struct nexthop *y, int rx, int ry, int max, linpool *lp); -struct nexthop *nexthop_sort(struct nexthop *x); -static inline void nexthop_link(struct rta *a, struct nexthop *from) -{ memcpy(&a->nh, from, nexthop_size(from)); } -void nexthop_insert(struct nexthop **n, struct nexthop *y); -int nexthop_is_sorted(struct nexthop *x); - -void rta_init(void); -static inline size_t rta_size(const rta *a) { return sizeof(rta) + sizeof(u32)*a->nh.labels; } -#define RTA_MAX_SIZE (sizeof(rta) + sizeof(u32)*MPLS_MAX_LABEL_STACK) -rta *rta_lookup(rta *); /* Get rta equivalent to this one, uc++ */ -static inline int rta_is_cached(rta *r) { return r->cached; } -static inline rta *rta_clone(rta *r) { r->uc++; return r; } -void rta__free(rta *r); -static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); } -rta *rta_do_cow(rta *o, linpool *lp); -static inline rta * rta_cow(rta *r, linpool *lp) { return rta_is_cached(r) ? rta_do_cow(r, lp) : r; } -void rta_dump(rta *); -void rta_dump_all(void); -void rta_show(struct cli *, rta *); - -u32 rt_get_igp_metric(rte *rt); -struct hostentry * rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep); -void rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls); - -static inline void -rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr gw, ip_addr ll, mpls_label_stack *mls) -{ - rta_apply_hostentry(a, rt_get_hostentry(tab, gw, ll, dep), mls); -} - -/* - * rta_set_recursive_next_hop() acquires hostentry from hostcache and fills - * rta->hostentry field. New hostentry has zero use count. Cached rta locks its - * hostentry (increases its use count), uncached rta does not lock it. Hostentry - * with zero use count is removed asynchronously during host cache update, - * therefore it is safe to hold such hostentry temorarily. Hostentry holds a - * lock for a 'source' rta, mainly to share multipath nexthops. - * - * There is no need to hold a lock for hostentry->dep table, because that table - * contains routes responsible for that hostentry, and therefore is non-empty if - * given hostentry has non-zero use count. If the hostentry has zero use count, - * the entry is removed before dep is referenced. - * - * The protocol responsible for routes with recursive next hops should hold a - * lock for a 'source' table governing that routes (argument tab to - * rta_set_recursive_next_hop()), because its routes reference hostentries - * (through rta) related to the governing table. When all such routes are - * removed, rtas are immediately removed achieving zero uc. Then the 'source' - * table lock could be immediately released, although hostentries may still - * exist - they will be freed together with the 'source' table. - */ - -static inline void rt_lock_hostentry(struct hostentry *he) { if (he) he->uc++; } -static inline void rt_unlock_hostentry(struct hostentry *he) { if (he) he->uc--; } - -int rt_flowspec_check(rtable *tab_ip, rtable *tab_flow, const net_addr *n, rta *a, int interior); - - -/* - * Default protocol preferences - */ - -#define DEF_PREF_DIRECT 240 /* Directly connected */ -#define DEF_PREF_STATIC 200 /* Static route */ -#define DEF_PREF_OSPF 150 /* OSPF intra-area, inter-area and type 1 external routes */ -#define DEF_PREF_BABEL 130 /* Babel */ -#define DEF_PREF_RIP 120 /* RIP */ -#define DEF_PREF_BGP 100 /* BGP */ -#define DEF_PREF_RPKI 100 /* RPKI */ -#define DEF_PREF_INHERITED 10 /* Routes inherited from other routing daemons */ - -/* - * Route Origin Authorization - */ - -#define ROA_UNKNOWN 0 -#define ROA_VALID 1 -#define ROA_INVALID 2 - -#endif diff --git a/nest/rt-attr.c b/nest/rt-attr.c index de45dfa1..8f4319c5 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -45,7 +45,7 @@ */ #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "nest/cli.h" @@ -529,25 +529,6 @@ ea_walk(struct ea_walk_state *s, uint id, uint max) return NULL; } -/** - * ea_get_int - fetch an integer attribute - * @e: attribute list - * @id: attribute ID - * @def: default value - * - * This function is a shortcut for retrieving a value of an integer attribute - * by calling ea_find() to find the attribute, extracting its value or returning - * a provided default if no such attribute is present. - */ -u32 -ea_get_int(ea_list *e, unsigned id, u32 def) -{ - eattr *a = ea_find(e, id); - if (!a) - return def; - return a->u.data; -} - static inline void ea_do_sort(ea_list *e) { diff --git a/nest/rt-dev.c b/nest/rt-dev.c index 05e64fc3..82533321 100644 --- a/nest/rt-dev.c +++ b/nest/rt-dev.c @@ -18,7 +18,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/rt-dev.h" #include "conf/conf.h" #include "lib/resource.h" diff --git a/nest/rt-fib.c b/nest/rt-fib.c index 43e3039d..801561da 100644 --- a/nest/rt-fib.c +++ b/nest/rt-fib.c @@ -55,7 +55,7 @@ #undef LOCAL_DEBUG #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "lib/string.h" /* diff --git a/nest/rt-show.c b/nest/rt-show.c index 19877966..464e5f1b 100644 --- a/nest/rt-show.c +++ b/nest/rt-show.c @@ -10,7 +10,7 @@ #undef LOCAL_DEBUG #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/cli.h" #include "nest/iface.h" diff --git a/nest/rt-table.c b/nest/rt-table.c index fbfdb1e6..031e462b 100644 --- a/nest/rt-table.c +++ b/nest/rt-table.c @@ -91,7 +91,7 @@ #undef LOCAL_DEBUG #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "lib/resource.h" diff --git a/nest/rt.h b/nest/rt.h new file mode 100644 index 00000000..7451a261 --- /dev/null +++ b/nest/rt.h @@ -0,0 +1,343 @@ +/* + * BIRD Internet Routing Daemon -- Routing Table + * + * (c) 1998--2000 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_NEST_RT_H_ +#define _BIRD_NEST_RT_H_ + +#include "lib/lists.h" +#include "lib/bitmap.h" +#include "lib/resource.h" +#include "lib/net.h" +#include "lib/type.h" +#include "lib/fib.h" +#include "lib/route.h" + +struct ea_list; +struct protocol; +struct proto; +struct rte_src; +struct symbol; +struct timer; +struct filter; +struct f_trie; +struct f_trie_walk_state; +struct cli; + +/* + * Master Routing Tables. Generally speaking, each of them contains a FIB + * with each entry pointing to a list of route entries representing routes + * to given network (with the selected one at the head). + * + * Each of the RTE's contains variable data (the preference and protocol-dependent + * metrics) and a pointer to a route attribute block common for many routes). + * + * It's guaranteed that there is at most one RTE for every (prefix,proto) pair. + */ + +struct rtable_config { + node n; + char *name; + struct rtable *table; + struct proto_config *krt_attached; /* Kernel syncer attached to this table */ + uint addr_type; /* Type of address data stored in table (NET_*) */ + int gc_max_ops; /* Maximum number of operations before GC is run */ + int gc_min_time; /* Minimum time between two consecutive GC runs */ + byte sorted; /* Routes of network are sorted according to rte_better() */ + byte internal; /* Internal table of a protocol */ + byte trie_used; /* Rtable has attached trie */ + btime min_settle_time; /* Minimum settle time for notifications */ + btime max_settle_time; /* Maximum settle time for notifications */ +}; + +typedef struct rtable { + resource r; + node n; /* Node in list of all tables */ + pool *rp; /* Resource pool to allocate everything from, including itself */ + struct fib fib; + struct f_trie *trie; /* Trie of prefixes defined in fib */ + char *name; /* Name of this table */ + list channels; /* List of attached channels (struct channel) */ + uint addr_type; /* Type of address data stored in table (NET_*) */ + int pipe_busy; /* Pipe loop detection */ + int use_count; /* Number of protocols using this table */ + u32 rt_count; /* Number of routes in the table */ + + byte internal; /* Internal table of a protocol */ + + struct hmap id_map; + struct hostcache *hostcache; + struct rtable_config *config; /* Configuration of this table */ + struct config *deleted; /* Table doesn't exist in current configuration, + * delete as soon as use_count becomes 0 and remove + * obstacle from this routing table. + */ + struct event *rt_event; /* Routing table event */ + btime last_rt_change; /* Last time when route changed */ + btime base_settle_time; /* Start time of rtable settling interval */ + btime gc_time; /* Time of last GC */ + int gc_counter; /* Number of operations since last GC */ + byte prune_state; /* Table prune state, 1 -> scheduled, 2-> running */ + byte prune_trie; /* Prune prefix trie during next table prune */ + byte hcu_scheduled; /* Hostcache update is scheduled */ + byte nhu_state; /* Next Hop Update state */ + struct fib_iterator prune_fit; /* Rtable prune FIB iterator */ + struct fib_iterator nhu_fit; /* Next Hop Update FIB iterator */ + struct f_trie *trie_new; /* New prefix trie defined during pruning */ + struct f_trie *trie_old; /* Old prefix trie waiting to be freed */ + u32 trie_lock_count; /* Prefix trie locked by walks */ + u32 trie_old_lock_count; /* Old prefix trie locked by walks */ + + list subscribers; /* Subscribers for notifications */ + struct timer *settle_timer; /* Settle time for notifications */ + list flowspec_links; /* List of flowspec links, src for NET_IPx and dst for NET_FLOWx */ + struct f_trie *flowspec_trie; /* Trie for evaluation of flowspec notifications */ +} rtable; + +struct rt_subscription { + node n; + rtable *tab; + void (*hook)(struct rt_subscription *b); + void *data; +}; + +struct rt_flowspec_link { + node n; + rtable *src; + rtable *dst; + u32 uc; +}; + +#define NHU_CLEAN 0 +#define NHU_SCHEDULED 1 +#define NHU_RUNNING 2 +#define NHU_DIRTY 3 + +typedef struct network { + struct rte *routes; /* Available routes for this network */ + struct fib_node n; /* FIB flags reserved for kernel syncer */ +} net; + +struct hostcache { + slab *slab; /* Slab holding all hostentries */ + struct hostentry **hash_table; /* Hash table for hostentries */ + unsigned hash_order, hash_shift; + unsigned hash_max, hash_min; + unsigned hash_items; + linpool *lp; /* Linpool for trie */ + struct f_trie *trie; /* Trie of prefixes that might affect hostentries */ + list hostentries; /* List of all hostentries */ + byte update_hostcache; +}; + +struct hostentry { + node ln; + ip_addr addr; /* IP address of host, part of key */ + ip_addr link; /* (link-local) IP address of host, used as gw + if host is directly attached */ + struct rtable *tab; /* Dependent table, part of key */ + struct hostentry *next; /* Next in hash chain */ + unsigned hash_key; /* Hash key */ + unsigned uc; /* Use count */ + struct rta *src; /* Source rta entry */ + byte dest; /* Chosen route destination type (RTD_...) */ + byte nexthop_linkable; /* Nexthop list is completely non-device */ + u32 igp_metric; /* Chosen route IGP metric */ +}; + +/* Types of route announcement, also used as flags */ +#define RA_UNDEF 0 /* Undefined RA type */ +#define RA_OPTIMAL 1 /* Announcement of optimal route change */ +#define RA_ACCEPTED 2 /* Announcement of first accepted route */ +#define RA_ANY 3 /* Announcement of any route change */ +#define RA_MERGED 4 /* Announcement of optimal route merged with next ones */ + +/* Return value of preexport() callback */ +#define RIC_ACCEPT 1 /* Accepted by protocol */ +#define RIC_PROCESS 0 /* Process it through import filter */ +#define RIC_REJECT -1 /* Rejected by protocol */ +#define RIC_DROP -2 /* Silently dropped by protocol */ + +extern list routing_tables; +struct config; + +void rt_init(void); +void rt_preconfig(struct config *); +void rt_commit(struct config *new, struct config *old); +void rt_lock_table(rtable *); +void rt_unlock_table(rtable *); +struct f_trie * rt_lock_trie(rtable *tab); +void rt_unlock_trie(rtable *tab, struct f_trie *trie); +void rt_subscribe(rtable *tab, struct rt_subscription *s); +void rt_unsubscribe(struct rt_subscription *s); +void rt_flowspec_link(rtable *src, rtable *dst); +void rt_flowspec_unlink(rtable *src, rtable *dst); +rtable *rt_setup(pool *, struct rtable_config *); +static inline void rt_shutdown(rtable *r) { rfree(r->rp); } + +static inline net *net_find(rtable *tab, const net_addr *addr) { return (net *) fib_find(&tab->fib, addr); } +static inline net *net_find_valid(rtable *tab, const net_addr *addr) +{ net *n = net_find(tab, addr); return (n && rte_is_valid(n->routes)) ? n : NULL; } +static inline net *net_get(rtable *tab, const net_addr *addr) { return (net *) fib_get(&tab->fib, addr); } +net *net_get(rtable *tab, const net_addr *addr); +net *net_route(rtable *tab, const net_addr *n); +rte *rte_find(net *net, struct rte_src *src); +rte *rte_get_temp(struct rta *, struct rte_src *src); +void rte_update2(struct channel *c, const net_addr *n, rte *new, struct rte_src *src); +/* rte_update() moved to protocol.h to avoid dependency conflicts */ +int rt_examine(rtable *t, net_addr *a, struct proto *p, const struct filter *filter); +rte *rt_export_merged(struct channel *c, net *net, rte **rt_free, linpool *pool, int silent); +void rt_refresh_begin(rtable *t, struct channel *c); +void rt_refresh_end(rtable *t, struct channel *c); +void rt_modify_stale(rtable *t, struct channel *c); +void rt_schedule_prune(rtable *t); +void rte_dump(rte *); +void rte_free(rte *); +rte *rte_do_cow(rte *); +static inline rte * rte_cow(rte *r) { return (r->flags & REF_COW) ? rte_do_cow(r) : r; } +rte *rte_cow_rta(rte *r, linpool *lp); +void rt_dump(rtable *); +void rt_dump_all(void); +int rt_feed_channel(struct channel *c); +void rt_feed_channel_abort(struct channel *c); +int rte_update_in(struct channel *c, const net_addr *n, rte *new, struct rte_src *src); +int rt_reload_channel(struct channel *c); +void rt_reload_channel_abort(struct channel *c); +void rt_prune_sync(rtable *t, int all); +int rte_update_out(struct channel *c, const net_addr *n, rte *new, rte *old, rte **old_exported, int refeed); +struct rtable_config *rt_new_table(struct symbol *s, uint addr_type); + +static inline int rt_is_ip(rtable *tab) +{ return (tab->addr_type == NET_IP4) || (tab->addr_type == NET_IP6); } + +static inline int rt_is_vpn(rtable *tab) +{ return (tab->addr_type == NET_VPN4) || (tab->addr_type == NET_VPN6); } + +static inline int rt_is_roa(rtable *tab) +{ return (tab->addr_type == NET_ROA4) || (tab->addr_type == NET_ROA6); } + +static inline int rt_is_flow(rtable *tab) +{ return (tab->addr_type == NET_FLOW4) || (tab->addr_type == NET_FLOW6); } + + +/* Default limit for ECMP next hops, defined in sysdep code */ +extern const int rt_default_ecmp; + +struct rt_show_data_rtable { + node n; + rtable *table; + struct channel *export_channel; +}; + +struct rt_show_data { + net_addr *addr; + list tables; + struct rt_show_data_rtable *tab; /* Iterator over table list */ + struct rt_show_data_rtable *last_table; /* Last table in output */ + struct fib_iterator fit; /* Iterator over networks in table */ + struct f_trie_walk_state *walk_state; /* Iterator over networks in trie */ + struct f_trie *walk_lock; /* Locked trie for walking */ + int verbose, tables_defined_by; + const struct filter *filter; + struct proto *show_protocol; + struct proto *export_protocol; + struct channel *export_channel; + struct config *running_on_config; + struct krt_proto *kernel; + int export_mode, addr_mode, primary_only, filtered, stats; + + int table_open; /* Iteration (fit) is open */ + int trie_walk; /* Current table is iterated using trie */ + int net_counter, rt_counter, show_counter, table_counter; + int net_counter_last, rt_counter_last, show_counter_last; +}; + +void rt_show(struct rt_show_data *); +struct rt_show_data_rtable * rt_show_add_table(struct rt_show_data *d, rtable *t); + +/* Value of table definition mode in struct rt_show_data */ +#define RSD_TDB_DEFAULT 0 /* no table specified */ +#define RSD_TDB_INDIRECT 0 /* show route ... protocol P ... */ +#define RSD_TDB_ALL RSD_TDB_SET /* show route ... table all ... */ +#define RSD_TDB_DIRECT RSD_TDB_SET | RSD_TDB_NMN /* show route ... table X table Y ... */ + +#define RSD_TDB_SET 0x1 /* internal: show empty tables */ +#define RSD_TDB_NMN 0x2 /* internal: need matching net */ + +/* Value of addr_mode */ +#define RSD_ADDR_EQUAL 1 /* Exact query - show route */ +#define RSD_ADDR_FOR 2 /* Longest prefix match - show route for */ +#define RSD_ADDR_IN 3 /* Interval query - show route in */ + +/* Value of export_mode in struct rt_show_data */ +#define RSEM_NONE 0 /* Export mode not used */ +#define RSEM_PREEXPORT 1 /* Routes ready for export, before filtering */ +#define RSEM_EXPORT 2 /* Routes accepted by export filter */ +#define RSEM_NOEXPORT 3 /* Routes rejected by export filter */ +#define RSEM_EXPORTED 4 /* Routes marked in export map */ + +struct hostentry * rt_get_hostentry(rtable *tab, ip_addr a, ip_addr ll, rtable *dep); +void rta_apply_hostentry(rta *a, struct hostentry *he, mpls_label_stack *mls); + +static inline void +rta_set_recursive_next_hop(rtable *dep, rta *a, rtable *tab, ip_addr gw, ip_addr ll, mpls_label_stack *mls) +{ + rta_apply_hostentry(a, rt_get_hostentry(tab, gw, ll, dep), mls); +} + +/* + * rta_set_recursive_next_hop() acquires hostentry from hostcache and fills + * rta->hostentry field. New hostentry has zero use count. Cached rta locks its + * hostentry (increases its use count), uncached rta does not lock it. Hostentry + * with zero use count is removed asynchronously during host cache update, + * therefore it is safe to hold such hostentry temorarily. Hostentry holds a + * lock for a 'source' rta, mainly to share multipath nexthops. + * + * There is no need to hold a lock for hostentry->dep table, because that table + * contains routes responsible for that hostentry, and therefore is non-empty if + * given hostentry has non-zero use count. If the hostentry has zero use count, + * the entry is removed before dep is referenced. + * + * The protocol responsible for routes with recursive next hops should hold a + * lock for a 'source' table governing that routes (argument tab to + * rta_set_recursive_next_hop()), because its routes reference hostentries + * (through rta) related to the governing table. When all such routes are + * removed, rtas are immediately removed achieving zero uc. Then the 'source' + * table lock could be immediately released, although hostentries may still + * exist - they will be freed together with the 'source' table. + */ + +static inline void rt_lock_hostentry(struct hostentry *he) { if (he) he->uc++; } +static inline void rt_unlock_hostentry(struct hostentry *he) { if (he) he->uc--; } + +int rt_flowspec_check(rtable *tab_ip, rtable *tab_flow, const net_addr *n, rta *a, int interior); + + +/* + * Default protocol preferences + */ + +#define DEF_PREF_DIRECT 240 /* Directly connected */ +#define DEF_PREF_STATIC 200 /* Static route */ +#define DEF_PREF_OSPF 150 /* OSPF intra-area, inter-area and type 1 external routes */ +#define DEF_PREF_BABEL 130 /* Babel */ +#define DEF_PREF_RIP 120 /* RIP */ +#define DEF_PREF_BGP 100 /* BGP */ +#define DEF_PREF_RPKI 100 /* RPKI */ +#define DEF_PREF_INHERITED 10 /* Routes inherited from other routing daemons */ + +/* + * Route Origin Authorization + */ + +#define ROA_UNKNOWN 0 +#define ROA_VALID 1 +#define ROA_INVALID 2 + +int net_roa_check(rtable *tab, const net_addr *n, u32 asn); + +#endif diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 8b6da3c8..00814641 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -16,7 +16,7 @@ #include "nest/bird.h" #include "nest/cli.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/locks.h" #include "nest/password.h" diff --git a/proto/bfd/bfd.h b/proto/bfd/bfd.h index 91fdaa60..bbccd0b8 100644 --- a/proto/bfd/bfd.h +++ b/proto/bfd/bfd.h @@ -13,7 +13,7 @@ #include "nest/cli.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/password.h" #include "conf/conf.h" #include "lib/hash.h" diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c index 1bae942d..3265cb5e 100644 --- a/proto/bgp/attrs.c +++ b/proto/bgp/attrs.c @@ -15,7 +15,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "conf/conf.h" #include "lib/resource.h" diff --git a/proto/bgp/bgp.c b/proto/bgp/bgp.c index 8c97f7b3..aec78a45 100644 --- a/proto/bgp/bgp.c +++ b/proto/bgp/bgp.c @@ -114,7 +114,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "nest/locks.h" #include "conf/conf.h" diff --git a/proto/bgp/bgp.h b/proto/bgp/bgp.h index 6f209595..d09a5c8f 100644 --- a/proto/bgp/bgp.h +++ b/proto/bgp/bgp.h @@ -14,7 +14,7 @@ #include #include #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/bfd.h" //#include "lib/lists.h" #include "lib/hash.h" diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c index a805cdf0..5def0f27 100644 --- a/proto/bgp/packets.c +++ b/proto/bgp/packets.c @@ -15,7 +15,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/attrs.h" #include "proto/mrt/mrt.h" #include "conf/conf.h" diff --git a/proto/mrt/mrt.h b/proto/mrt/mrt.h index 4ff94c12..3b83aa39 100644 --- a/proto/mrt/mrt.h +++ b/proto/mrt/mrt.h @@ -13,7 +13,7 @@ #include "nest/bird.h" #include "nest/protocol.h" #include "lib/lists.h" -#include "nest/route.h" +#include "nest/rt.h" #include "lib/event.h" #include "lib/hash.h" diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index 3e704ae8..3d0d57d9 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -22,7 +22,7 @@ #include "lib/resource.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "nest/locks.h" #include "nest/bfd.h" diff --git a/proto/perf/perf.c b/proto/perf/perf.c index 5d228045..dde7e473 100644 --- a/proto/perf/perf.c +++ b/proto/perf/perf.c @@ -18,7 +18,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "conf/conf.h" #include "filter/filter.h" diff --git a/proto/pipe/pipe.c b/proto/pipe/pipe.c index c3457135..483ece67 100644 --- a/proto/pipe/pipe.c +++ b/proto/pipe/pipe.c @@ -35,7 +35,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "conf/conf.h" #include "filter/filter.h" diff --git a/proto/radv/radv.h b/proto/radv/radv.h index 14d40f8a..5cca3aca 100644 --- a/proto/radv/radv.h +++ b/proto/radv/radv.h @@ -19,7 +19,7 @@ #include "lib/resource.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "nest/locks.h" #include "conf/conf.h" diff --git a/proto/rip/rip.h b/proto/rip/rip.h index f8713c4a..a6fa3326 100644 --- a/proto/rip/rip.h +++ b/proto/rip/rip.h @@ -16,7 +16,7 @@ #include "nest/cli.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/password.h" #include "nest/locks.h" #include "nest/bfd.h" diff --git a/proto/rpki/rpki.h b/proto/rpki/rpki.h index 8a5c38fd..26fbb46e 100644 --- a/proto/rpki/rpki.h +++ b/proto/rpki/rpki.h @@ -13,7 +13,7 @@ #define _BIRD_RPKI_H_ #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "lib/socket.h" #include "lib/ip.h" diff --git a/proto/static/static.c b/proto/static/static.c index cd31afd3..3a0d9257 100644 --- a/proto/static/static.c +++ b/proto/static/static.c @@ -38,7 +38,7 @@ #include "nest/bird.h" #include "nest/iface.h" #include "nest/protocol.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/cli.h" #include "conf/conf.h" #include "filter/filter.h" diff --git a/proto/static/static.h b/proto/static/static.h index fc91f71c..d99f7ebd 100644 --- a/proto/static/static.h +++ b/proto/static/static.h @@ -9,7 +9,7 @@ #ifndef _BIRD_STATIC_H_ #define _BIRD_STATIC_H_ -#include "nest/route.h" +#include "nest/rt.h" #include "nest/bfd.h" #include "lib/buffer.h" diff --git a/sysdep/bsd/krt-sock.c b/sysdep/bsd/krt-sock.c index 3b1d2299..cd449d11 100644 --- a/sysdep/bsd/krt-sock.c +++ b/sysdep/bsd/krt-sock.c @@ -25,7 +25,7 @@ #include "nest/bird.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "sysdep/unix/unix.h" diff --git a/sysdep/linux/netlink.c b/sysdep/linux/netlink.c index eb4be711..a37692d6 100644 --- a/sysdep/linux/netlink.c +++ b/sysdep/linux/netlink.c @@ -17,7 +17,7 @@ #undef LOCAL_DEBUG #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "lib/alloca.h" diff --git a/sysdep/unix/krt.c b/sysdep/unix/krt.c index bfd69b73..671e91fe 100644 --- a/sysdep/unix/krt.c +++ b/sysdep/unix/krt.c @@ -53,7 +53,7 @@ #include "nest/bird.h" #include "nest/iface.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "filter/filter.h" #include "conf/conf.h" diff --git a/sysdep/unix/main.c b/sysdep/unix/main.c index 71749324..9bb37e5d 100644 --- a/sysdep/unix/main.c +++ b/sysdep/unix/main.c @@ -30,7 +30,7 @@ #include "lib/event.h" #include "lib/timer.h" #include "lib/string.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" #include "nest/cli.h" diff --git a/test/bt-utils.c b/test/bt-utils.c index 8496e185..ce9a49d7 100644 --- a/test/bt-utils.c +++ b/test/bt-utils.c @@ -14,7 +14,7 @@ #include "test/bt-utils.h" #include "nest/bird.h" -#include "nest/route.h" +#include "nest/rt.h" #include "nest/protocol.h" #include "sysdep/unix/unix.h" -- cgit v1.2.3 From 3fb70b26faca6788aa0bdf1d558414f9f777c6cd Mon Sep 17 00:00:00 2001 From: Maria Matejka Date: Thu, 31 Mar 2022 19:22:07 +0200 Subject: Complex route attributes are data structures, shall be in lib also --- filter/data.c | 2 +- filter/filter.c | 2 +- filter/filter.h | 2 +- lib/Makefile | 4 +- lib/a-path.c | 905 ++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/a-path_test.c | 206 ++++++++++++ lib/a-set.c | 695 ++++++++++++++++++++++++++++++++++++++++ lib/a-set_test.c | 240 ++++++++++++++ lib/attrs.h | 230 +++++++++++++ nest/Makefile | 4 +- nest/a-path.c | 905 ---------------------------------------------------- nest/a-path_test.c | 206 ------------ nest/a-set.c | 695 ---------------------------------------- nest/a-set_test.c | 240 -------------- nest/attrs.h | 230 ------------- nest/rt-attr.c | 2 +- proto/bgp/attrs.c | 2 +- proto/bgp/packets.c | 2 +- 18 files changed, 2286 insertions(+), 2286 deletions(-) create mode 100644 lib/a-path.c create mode 100644 lib/a-path_test.c create mode 100644 lib/a-set.c create mode 100644 lib/a-set_test.c create mode 100644 lib/attrs.h delete mode 100644 nest/a-path.c delete mode 100644 nest/a-path_test.c delete mode 100644 nest/a-set.c delete mode 100644 nest/a-set_test.c delete mode 100644 nest/attrs.h (limited to 'nest/a-path.c') diff --git a/filter/data.c b/filter/data.c index 87ef4ff1..381448fa 100644 --- a/filter/data.c +++ b/filter/data.c @@ -19,7 +19,7 @@ #include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "filter/filter.h" #include "filter/f-inst.h" diff --git a/filter/filter.c b/filter/filter.c index 31ae79fe..8f946f5b 100644 --- a/filter/filter.c +++ b/filter/filter.c @@ -38,7 +38,7 @@ #include "nest/rt.h" #include "nest/protocol.h" #include "nest/iface.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "filter/filter.h" #include "filter/f-inst.h" diff --git a/filter/filter.h b/filter/filter.h index 8ce6c1e0..385f1179 100644 --- a/filter/filter.h +++ b/filter/filter.h @@ -14,7 +14,7 @@ #include "lib/ip.h" #include "lib/macro.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" /* Possible return values of filter execution */ enum filter_return { diff --git a/lib/Makefile b/lib/Makefile index 812f721c..853e0a22 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -1,7 +1,7 @@ -src := bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c +src := a-path.c a-set.c bitmap.c bitops.c blake2s.c blake2b.c checksum.c event.c flowspec.c idm.c ip.c lists.c mac.c md5.c mempool.c net.c patmatch.c printf.c resource.c sha1.c sha256.c sha512.c slab.c slists.c strtoul.c tbf.c timer.c xmalloc.c obj := $(src-o-files) $(all-daemon) -tests_src := bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c +tests_src := a-set_test.c a-path_test.c bitmap_test.c heap_test.c buffer_test.c event_test.c flowspec_test.c bitops_test.c patmatch_test.c fletcher16_test.c slist_test.c checksum_test.c lists_test.c mac_test.c ip_test.c hash_test.c printf_test.c slab_test.c tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/lib/a-path.c b/lib/a-path.c new file mode 100644 index 00000000..0eca8475 --- /dev/null +++ b/lib/a-path.c @@ -0,0 +1,905 @@ +/* + * BIRD -- Path Operations + * + * (c) 2000 Martin Mares + * (c) 2000 Pavel Machek + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/unaligned.h" +#include "lib/string.h" +#include "filter/data.h" + +// static inline void put_as(byte *data, u32 as) { put_u32(data, as); } +// static inline u32 get_as(byte *data) { return get_u32(data); } + +#define put_as put_u32 +#define get_as get_u32 +#define BS 4 /* Default block size of ASN (autonomous system number) */ + +#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) + +int +as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen) +{ + byte *pos = data; + char *err_dsc = NULL; + uint err_val = 0; + + while (len) + { + if (len < 2) + BAD("segment framing error", 0); + + /* Process one AS path segment */ + uint type = pos[0]; + uint slen = 2 + bs * pos[1]; + + if (len < slen) + BAD("segment framing error", len); + + switch (type) + { + case AS_PATH_SET: + if (!sets) + BAD("AS_SET segment", type); + break; + + case AS_PATH_SEQUENCE: + break; + + case AS_PATH_CONFED_SEQUENCE: + if (!confed) + BAD("AS_CONFED_SEQUENCE segment", type); + break; + + case AS_PATH_CONFED_SET: + if (!sets || !confed) + BAD("AS_CONFED_SET segment", type); + break; + + default: + BAD("unknown segment", type); + } + + if (pos[1] == 0) + BAD("zero-length segment", type); + + pos += slen; + len -= slen; + } + + return 1; + +bad: + if (err) + if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) + err[0] = 0; + + return 0; +} + +int +as_path_16to32(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u32(dst, get_u16(src)); + src += 2; + dst += 4; + } + } + + return dst - dst0; +} + +int +as_path_32to16(byte *dst, const byte *src, uint len) +{ + byte *dst0 = dst; + const byte *end = src + len; + uint i, n; + + while (src < end) + { + n = src[1]; + *dst++ = *src++; + *dst++ = *src++; + + for (i = 0; i < n; i++) + { + put_u16(dst, get_u32(src)); + src += 4; + dst += 2; + } + } + + return dst - dst0; +} + +int +as_path_contains_as4(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint i, n; + + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + if (get_as(pos) > 0xFFFF) + return 1; + + pos += BS; + } + } + + return 0; +} + +int +as_path_contains_confed(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint slen = 2 + BS * pos[1]; + + if ((type == AS_PATH_CONFED_SEQUENCE) || + (type == AS_PATH_CONFED_SET)) + return 1; + + pos += slen; + } + + return 0; +} + +struct adata * +as_path_strip_confed(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + const byte *src = path->data; + const byte *end = src + path->length; + byte *dst = res->data; + + while (src < end) + { + uint type = src[0]; + uint slen = 2 + BS * src[1]; + + /* Copy regular segments */ + if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE)) + { + memcpy(dst, src, slen); + dst += slen; + } + + src += slen; + } + + /* Fix the result length */ + res->length = dst - res->data; + + return res; +} + +struct adata * +as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as) +{ + struct adata *np; + const byte *pos = op->data; + uint len = op->length; + + if (len && (pos[0] == seq) && (pos[1] < 255)) + { + /* Starting with matching segment => just prepend the AS number */ + np = lp_alloc_adata(pool, len + BS); + np->data[0] = seq; + np->data[1] = pos[1] + 1; + put_as(np->data + 2, as); + + uint dlen = BS * pos[1]; + memcpy(np->data + 2 + BS, pos + 2, dlen); + ADVANCE(pos, len, 2 + dlen); + } + else + { + /* Create a new path segment */ + np = lp_alloc_adata(pool, len + 2 + BS); + np->data[0] = seq; + np->data[1] = 1; + put_as(np->data + 2, as); + } + + if (len) + { + byte *dst = np->data + 2 + BS * np->data[1]; + + memcpy(dst, pos, len); + } + + return np; +} + + +struct adata * +as_path_to_old(struct linpool *pool, const struct adata *path) +{ + struct adata *res = lp_alloc_adata(pool, path->length); + byte *pos = res->data; + byte *end = pos + res->length; + uint i, n; + u32 as; + + /* Copy the whole path */ + memcpy(res->data, path->data, path->length); + + /* Replace 32-bit AS numbers with AS_TRANS */ + while (pos < end) + { + n = pos[1]; + pos += 2; + + for (i = 0; i < n; i++) + { + as = get_as(pos); + if (as > 0xFFFF) + put_as(pos, AS_TRANS); + + pos += BS; + } + } + + return res; +} + +/* + * Cut the path to the length @num, measured to the usual path metric. Note that + * AS_CONFED_* segments have zero length and must be added if they are on edge. + */ +struct adata * +as_path_cut(struct linpool *pool, const struct adata *path, uint num) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_cut: Invalid path segment"); + } + + /* Cannot add whole segment, so try partial one and finish */ + if (num < n) + { + const byte *nend = pos; + if (num) + nend += 2 + BS * num; + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = nend - (const byte *) path->data; + memcpy(res->data, path->data, res->length); + + if (num) + { + byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data); + dpos[1] = num; + } + + return res; + } + + num -= n; + pos += 2 + BS * l; + } + + struct adata *res = lp_alloc_adata(pool, path->length); + res->length = path->length; + memcpy(res->data, path->data, res->length); + return res; +} + +/* + * Merge (concatenate) paths @p1 and @p2 and return the result. + * In contrast to other as_path_* functions, @p1 and @p2 may be reused. + */ +const struct adata * +as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2) +{ + if (p1->length == 0) + return p2; + + if (p2->length == 0) + return p1; + + struct adata *res = lp_alloc_adata(pool, p1->length + p2->length); + memcpy(res->data, p1->data, p1->length); + memcpy(res->data + p1->length, p2->data, p2->length); + + return res; +} + +void +as_path_format(const struct adata *path, byte *bb, uint size) +{ + buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf; + const byte *pos = path->data; + const byte *end = pos + path->length; + const char *ops, *cls; + + b->pos[0] = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: ops = "{"; cls = "}"; break; + case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break; + case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break; + case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break; + default: bug("Invalid path segment"); + } + + if (ops) + buffer_puts(b, ops); + + while (len--) + { + buffer_print(b, len ? "%u " : "%u", get_as(pos)); + pos += BS; + } + + if (cls) + buffer_puts(b, cls); + + if (pos < end) + buffer_puts(b, " "); + } + + /* Handle overflow */ + if (b->pos == b->end) + strcpy(b->end - 12, "..."); +} + +int +as_path_getlen(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + uint res = 0; + + while (pos < end) + { + uint t = pos[0]; + uint l = pos[1]; + uint n = 0; + + switch (t) + { + case AS_PATH_SET: n = 1; break; + case AS_PATH_SEQUENCE: n = l; break; + case AS_PATH_CONFED_SEQUENCE: n = 0; break; + case AS_PATH_CONFED_SET: n = 0; break; + default: bug("as_path_getlen: Invalid path segment"); + } + + res += n; + pos += 2 + BS * l; + } + + return res; +} + +int +as_path_get_last(const struct adata *path, u32 *orig_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + int found = 0; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + found = 0; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + found = 1; + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + if (found) + *orig_as = val; + return found; +} + +u32 +as_path_get_last_nonaggregated(const struct adata *path) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + u32 val = 0; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + if (!len) + continue; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + return val; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + val = get_as(pos + BS * (len - 1)); + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return val; +} + +int +as_path_get_first(const struct adata *path, u32 *last_as) +{ + const u8 *p = path->data; + + if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) + return 0; + + *last_as = get_as(p+2); + return 1; +} + +int +as_path_get_first_regular(const struct adata *path, u32 *last_as) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + return 0; + + case AS_PATH_SEQUENCE: + if (len == 0) + return 0; + + *last_as = get_as(pos); + return 1; + + case AS_PATH_CONFED_SEQUENCE: + case AS_PATH_CONFED_SET: + break; + + default: + bug("Invalid path segment"); + } + + pos += BS * len; + } + + return 0; +} + +int +as_path_contains(const struct adata *path, u32 as, int min) +{ + const u8 *p = path->data; + const u8 *q = p+path->length; + int num = 0; + int i, n; + + while (pdata; + const u8 *q = p+path->length; + int i, n; + + while (plength; + const u8 *p = path->data; + const u8 *q = path->data + len; + u8 *d, *d2; + int i, bt, sn, dn; + u8 buf[len]; + + d = buf; + while (p 0) + { + /* Nonempty block, set block header and advance */ + d[0] = bt; + d[1] = dn; + d = d2; + } + } + + uint nl = d - buf; + if (nl == path->length) + return path; + + struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); + res->length = nl; + memcpy(res->data, buf, nl); + + return res; +} + + +struct pm_pos +{ + u8 set; + u8 mark; + union + { + const char *sp; + u32 asn; + } val; +}; + +static int +parse_path(const struct adata *path, struct pm_pos *pp) +{ + const byte *pos = path->data; + const byte *end = pos + path->length; + struct pm_pos *op = pp; + uint i; + + while (pos < end) + { + uint type = pos[0]; + uint len = pos[1]; + pos += 2; + + switch (type) + { + case AS_PATH_SET: + case AS_PATH_CONFED_SET: + pp->set = 1; + pp->mark = 0; + pp->val.sp = pos - 1; + pp++; + + pos += BS * len; + break; + + case AS_PATH_SEQUENCE: + case AS_PATH_CONFED_SEQUENCE: + for (i = 0; i < len; i++) + { + pp->set = 0; + pp->mark = 0; + pp->val.asn = get_as(pos); + pp++; + + pos += BS; + } + break; + + default: + bug("Invalid path segment"); + } + } + + return pp - op; +} + +static int +pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2) +{ + u32 gas; + if (! pos->set) + return ((pos->val.asn >= asn) && (pos->val.asn <= asn2)); + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + gas = get_as(p + i * BS); + + if ((gas >= asn) && (gas <= asn2)) + return 1; + } + + return 0; +} + +static int +pm_match_set(const struct pm_pos *pos, const struct f_tree *set) +{ + struct f_val asn = { .type = T_INT }; + + if (! pos->set) + { + asn.val.i = pos->val.asn; + return !!find_tree(set, &asn); + } + + const u8 *p = pos->val.sp; + int len = *p++; + int i; + + for (i = 0; i < len; i++) + { + asn.val.i = get_as(p + i * BS); + if (find_tree(set, &asn)) + return 1; + } + + return 0; +} + +static inline int +pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2) +{ + return ((mask->kind == PM_QUESTION) || + ((mask->kind != PM_ASN_SET) ? + pm_match_val(pos, asn, asn2) : + pm_match_set(pos, mask->set))); +} + +static void +pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh) +{ + int j = *i; + + if (pos[j].set) + do { pos[j].mark = 1; j++; } + while ((j < plen) && pos[j].set); + else + j++; + + pos[j].mark = 1; + + /* Update low, high based on first and last marked pos */ + int l = pos[*i].set ? *i : j; + + *nl = (*nl < 0) ? l : MIN(*nl, l); + *nh = MAX(*nh, j); + *i = j; +} + +/* AS path matching is nontrivial. Because AS path can + * contain sets, it is not a plain wildcard matching. A set + * in an AS path is interpreted as it might represent any + * sequence of AS numbers from that set (possibly with + * repetitions). So it is also a kind of a pattern, + * more complicated than a path mask. + * + * The algorithm for AS path matching is a variant + * of nondeterministic finite state machine, where + * positions in AS path are states, and items in + * path mask are input for that finite state machine. + * During execution of the algorithm we maintain a set + * of marked states - a state is marked if it can be + * reached by any walk through NFSM with regard to + * currently processed part of input. When we process + * next part of mask, we advance each marked state. + * We start with marked first position, when we + * run out of marked positions, we reject. When + * we process the whole mask, we accept if final position + * (auxiliary position after last real position in AS path) + * is marked. + */ +int +as_path_match(const struct adata *path, const struct f_path_mask *mask) +{ + struct pm_pos pos[2048 + 1]; + int plen = parse_path(path, pos); + int l, h, i, nh, nl, last, loop; + u32 val = 0; + u32 val2 = 0; + + /* l and h are bound of interval of positions where + are marked states */ + + pos[plen].set = 0; + pos[plen].mark = 0; + + l = h = loop = 0; + pos[0].mark = 1; + + for (uint m=0; m < mask->len; m++) + { + /* We remove this mark to not step after pos[plen] */ + pos[plen].mark = 0; + + switch (mask->item[m].kind) + { + case PM_ASTERISK: + for (i = l; i <= plen; i++) + pos[i].mark = 1; + h = plen; + break; + + case PM_LOOP: + loop = 1; + break; + + case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ + val2 = val = mask->item[m].asn; + goto step; + case PM_ASN_EXPR: + bug("Expressions should be evaluated on AS path mask construction."); + case PM_ASN_RANGE: + val = mask->item[m].from; + val2 = mask->item[m].to; + goto step; + case PM_QUESTION: + case PM_ASN_SET: + step: + nh = nl = -1; + last = plen; + for (i = h; i >= l; i--) + if (pos[i].mark) + { + pos[i].mark = 0; + int j = i; + + match: + if (pm_match(pos + j, &mask->item[m], val, val2)) + { + pm_mark(pos, &j, plen, &nl, &nh); + if (loop && (j < last)) + goto match; + } + + last = i; + } + + if (nh < 0) + return 0; + + h = nh; + l = nl; + loop = 0; + break; + } + } + + return pos[plen].mark; +} diff --git a/lib/a-path_test.c b/lib/a-path_test.c new file mode 100644 index 00000000..38f77642 --- /dev/null +++ b/lib/a-path_test.c @@ -0,0 +1,206 @@ +/* + * BIRD -- Path Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define TESTS_NUM 30 +#define AS_PATH_LENGTH 1000 + +#if AS_PATH_LENGTH > AS_PATH_MAXLEN +#warning "AS_PATH_LENGTH should be <= AS_PATH_MAXLEN" +#endif + +static int +t_as_path_match(void) +{ + int round; + for (round = 0; round < TESTS_NUM; round++) + { + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + u32 first_prepended, last_prepended; + first_prepended = last_prepended = 0; + + struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item)); + mask->len = AS_PATH_LENGTH; + for (int i = AS_PATH_LENGTH - 1; i >= 0; i--) + { + u32 val = bt_random(); + as_path = as_path_prepend(tmp_linpool, as_path, val); + bt_debug("Prepending ASN: %10u \n", val); + + if (i == 0) + last_prepended = val; + if (i == AS_PATH_LENGTH-1) + first_prepended = val; + + mask->item[i].kind = PM_ASN; + mask->item[i].asn = val; + } + + bt_assert_msg(as_path_match(as_path, mask), "Mask should match with AS path"); + + u32 asn; + + bt_assert(as_path_get_first(as_path, &asn)); + bt_assert_msg(asn == last_prepended, "as_path_get_first() should return the last prepended ASN"); + + bt_assert(as_path_get_last(as_path, &asn)); + bt_assert_msg(asn == first_prepended, "as_path_get_last() should return the first prepended ASN"); + + tmp_flush(); + } + + return 1; +} + +static int +t_path_format(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + uint i; + for (i = 4294967285; i <= 4294967294; i++) + { + as_path = as_path_prepend(tmp_linpool, as_path, i); + bt_debug("Prepending ASN: %10u \n", i); + } + +#define BUFFER_SIZE 120 + byte buf[BUFFER_SIZE] = {}; + + as_path_format(&empty_as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + + as_path_format(as_path, buf, BUFFER_SIZE); + bt_assert_msg(strcmp(buf, "4294967294 4294967293 4294967292 4294967291 4294967290 4294967289 4294967288 4294967287 4294967286 4294967285") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); + +#define SMALL_BUFFER_SIZE 25 + byte buf2[SMALL_BUFFER_SIZE] = {}; + as_path_format(as_path, buf2, SMALL_BUFFER_SIZE); + bt_assert_msg(strcmp(buf2, "4294967294 42...") == 0, "Small Buffer(%zu): '%s'", strlen(buf2), buf2); + + tmp_flush(); + + return 1; +} + +static int +count_asn_in_array(const u32 *array, u32 asn) +{ + int counts_of_contains = 0; + int u; + for (u = 0; u < AS_PATH_LENGTH; u++) + if (array[u] == asn) + counts_of_contains++; + return counts_of_contains; +} + +static int +t_path_include(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; + + u32 as_nums[AS_PATH_LENGTH] = {}; + int i; + for (i = 0; i < AS_PATH_LENGTH; i++) + { + u32 val = bt_random(); + as_nums[i] = val; + as_path = as_path_prepend(tmp_linpool, as_path, val); + } + + for (i = 0; i < AS_PATH_LENGTH; i++) + { + int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); + bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); + + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); + bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); + } + + for (i = 0; i < 10000; i++) + { + u32 test_val = bt_random(); + int counts_of_contains = count_asn_in_array(as_nums, test_val); + int result = as_path_contains(as_path, test_val, (counts_of_contains == 0 ? 1 : counts_of_contains)); + + if (counts_of_contains) + bt_assert_msg(result, "As path should contain %d-times the number %u", counts_of_contains, test_val); + else + bt_assert_msg(result == 0, "As path should not contain the number %u", test_val); + } + + tmp_flush(); + + return 1; +} + +#if 0 +static int +t_as_path_converting(void) +{ + struct adata empty_as_path = {}; + struct adata *as_path = &empty_as_path; +#define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10 + + int i; + for (i = 0; i < AS_PATH_LENGTH_FOR_CONVERTING_TEST; i++) + as_path = as_path_prepend(tmp_linpool, as_path, i); + + bt_debug("data length: %u \n", as_path->length); + + byte buffer[100] = {}; + int used_size = as_path_convert_to_new(as_path, buffer, AS_PATH_LENGTH_FOR_CONVERTING_TEST-1); + bt_debug("as_path_convert_to_new: len %d \n%s\n", used_size, buffer); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\039\030\030\030\030\030\030\030\039\030\030\030\030\030\030\030\038\030\030\030\030\030\030" + "\030\037\030\030\030\030\030\030\030\036\030\030\030\030", + 38)); + + bzero(buffer, sizeof(buffer)); + int new_used; + used_size = as_path_convert_to_old(as_path, buffer, &new_used); + bt_debug("as_path_convert_to_old: len %d, new_used: %d \n", used_size, new_used); + for (i = 0; i < used_size; i++) + { + bt_debug("\\03%d", buffer[i]); + } + bt_debug("\n"); + bt_assert(memcmp(buffer, + "\032\0310\030\039\030\038\030\037\030\036\030\035\030\034\030\033\030\032\030\031\030\030", + 22)); + + return 1; +} +#endif + +int +main(int argc, char *argv[]) +{ + bt_init(argc, argv); + + bt_test_suite(t_as_path_match, "Testing AS path matching and some a-path utilities."); + bt_test_suite(t_path_format, "Testing formating as path into byte buffer"); + bt_test_suite(t_path_include, "Testing including a AS number in AS path"); + // bt_test_suite(t_as_path_converting, "Testing as_path_convert_to_*() output constancy"); + + return bt_exit_value(); +} diff --git a/lib/a-set.c b/lib/a-set.c new file mode 100644 index 00000000..8ede9b83 --- /dev/null +++ b/lib/a-set.c @@ -0,0 +1,695 @@ +/* + * BIRD -- Set/Community-list Operations + * + * (c) 2000 Martin Mares + * (c) 2000 Pavel Machek + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include + +#include "nest/bird.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" +#include "lib/string.h" + +/** + * int_set_format - format an &set for printing + * @set: set attribute to be formatted + * @way: style of format (0 for router ID list, 1 for community list) + * @from: starting position in set + * @buf: destination buffer + * @size: size of buffer + * + * This function takes a set attribute and formats it. @way specifies + * the style of format (router ID / community). @from argument can be + * used to specify the first printed value for the purpose of printing + * untruncated sets even with smaller buffers. If the output fits in + * the buffer, 0 is returned, otherwise the position of the first not + * printed item is returned. This value can be used as @from argument + * in subsequent calls. If truncated output suffices, -1 can be + * instead used as @from, in that case " ..." is eventually added at + * the buffer to indicate truncation. + */ +int +int_set_format(const struct adata *set, int way, int from, byte *buf, uint size) +{ + u32 *z = (u32 *) set->data; + byte *end = buf + size - 24; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i++) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + if (way) + buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); + else + buf += bsprintf(buf, "%R", z[i]); + } + *buf = 0; + return 0; +} + +int +ec_format(byte *buf, u64 ec) +{ + u32 type, key, val; + char tbuf[16]; + const char *kind; + + type = ec >> 48; + kind = ec_subtype_str(type & 0xf0ff); + + if (!kind) { + bsprintf(tbuf, "unknown 0x%x", type); + kind = tbuf; + } + + switch (ec >> 56) + { + /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ + case 0x00: + case 0x40: + key = (ec >> 32) & 0xFFFF; + val = ec; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* RFC 4360 3.2. IPv4 Address Specific Extended Community */ + case 0x01: + case 0x41: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %R, %u)", kind, key, val); + + /* RFC 5668 4-Octet AS Specific BGP Extended Community */ + case 0x02: + case 0x42: + key = ec >> 16; + val = ec & 0xFFFF; + return bsprintf(buf, "(%s, %u, %u)", kind, key, val); + + /* Generic format for unknown kinds of extended communities */ + default: + key = ec >> 32; + val = ec; + return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); + } + +} + +int +ec_set_format(const struct adata *set, int from, byte *buf, uint size) +{ + u32 *z = int_set_get_data(set); + byte *end = buf + size - 64; + int from2 = MAX(from, 0); + int to = int_set_get_size(set); + int i; + + for (i = from2; i < to; i += 2) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, " ..."); + else + *buf = 0; + return i; + } + + if (i > from2) + *buf++ = ' '; + + buf += ec_format(buf, ec_get(z, i)); + } + *buf = 0; + return 0; +} + +int +lc_format(byte *buf, lcomm lc) +{ + return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); +} + +int +lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize) +{ + u32 *d = (u32 *) set->data; + byte *end = buf + bufsize - 64; + int from2 = MAX(from, 0); + int to = set->length / 4; + int i; + + for (i = from2; i < to; i += 3) + { + if (buf > end) + { + if (from < 0) + strcpy(buf, "..."); + else + buf[-1] = 0; + return i; + } + + buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); + *buf++ = ' '; + } + + if (i != from2) + buf--; + + *buf = 0; + return 0; +} + +int +int_set_contains(const struct adata *list, u32 val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (*l++ == val) + return 1; + + return 0; +} + +int +ec_set_contains(const struct adata *list, u64 val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (l[i] == eh && l[i+1] == el) + return 1; + + return 0; +} + +int +lc_set_contains(const struct adata *list, lcomm val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i += 3) + if (lc_match(l, i, val)) + return 1; + + return 0; +} + +const struct adata * +int_set_prepend(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data + 4, list->data, list->length); + + * (u32 *) res->data = val; + + return res; +} + +const struct adata * +int_set_add(struct linpool *pool, const struct adata *list, u32 val) +{ + struct adata *res; + int len; + + if (int_set_contains(list, val)) + return list; + + len = list ? list->length : 0; + res = lp_alloc(pool, sizeof(struct adata) + len + 4); + res->length = len + 4; + + if (list) + memcpy(res->data, list->data, list->length); + + * (u32 *) (res->data + len) = val; + + return res; +} + +const struct adata * +ec_set_add(struct linpool *pool, const struct adata *list, u64 val) +{ + if (ec_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); + res->length = olen + 8; + + if (list) + memcpy(res->data, list->data, list->length); + + u32 *l = (u32 *) (res->data + olen); + l[0] = ec_hi(val); + l[1] = ec_lo(val); + + return res; +} + +const struct adata * +lc_set_add(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (lc_set_contains(list, val)) + return list; + + int olen = list ? list->length : 0; + struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); + res->length = olen + LCOMM_LENGTH; + + if (list) + memcpy(res->data, list->data, list->length); + + lc_put((u32 *) (res->data + olen), val); + + return res; +} + +const struct adata * +int_set_del(struct linpool *pool, const struct adata *list, u32 val) +{ + if (!int_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 4); + res->length = list->length - 4; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i = 0; i < len; i++) + if (l[i] != val) + *k++ = l[i]; + + return res; +} + +const struct adata * +ec_set_del(struct linpool *pool, const struct adata *list, u64 val) +{ + if (!ec_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - 8); + res->length = list->length - 8; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + u32 eh = ec_hi(val); + u32 el = ec_lo(val); + int i; + + for (i=0; i < len; i += 2) + if (! (l[i] == eh && l[i+1] == el)) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + return res; +} + +const struct adata * +lc_set_del(struct linpool *pool, const struct adata *list, lcomm val) +{ + if (!lc_set_contains(list, val)) + return list; + + struct adata *res; + res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH); + res->length = list->length - LCOMM_LENGTH; + + u32 *l = int_set_get_data(list); + u32 *k = int_set_get_data(res); + int len = int_set_get_size(list); + int i; + + for (i=0; i < len; i += 3) + if (! lc_match(l, i, val)) + k = lc_copy(k, l+i); + + return res; +} + +const struct adata * +int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i++) + if (!int_set_contains(l1, l[i])) + *k++ = l[i]; + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 2) + if (!ec_set_contains(l1, ec_get(l, i))) + { + *k++ = l[i]; + *k++ = l[i+1]; + } + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + +const struct adata * +lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) +{ + if (!l1) + return l2; + if (!l2) + return l1; + + struct adata *res; + int len = int_set_get_size(l2); + u32 *l = int_set_get_data(l2); + u32 tmp[len]; + u32 *k = tmp; + int i; + + for (i = 0; i < len; i += 3) + if (!lc_set_contains(l1, lc_get(l, i))) + k = lc_copy(k, l+i); + + if (k == tmp) + return l1; + + len = (k - tmp) * 4; + res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); + res->length = l1->length + len; + memcpy(res->data, l1->data, l1->length); + memcpy(res->data + l1->length, tmp, len); + return res; +} + + +struct adata * +ec_set_del_nontrans(struct linpool *pool, const struct adata *set) +{ + adata *res = lp_alloc_adata(pool, set->length); + u32 *src = int_set_get_data(set); + u32 *dst = int_set_get_data(res); + int len = int_set_get_size(set); + int i; + + /* Remove non-transitive communities (EC_TBIT set) */ + for (i = 0; i < len; i += 2) + { + if (src[i] & EC_TBIT) + continue; + + *dst++ = src[i]; + *dst++ = src[i+1]; + } + + res->length = ((byte *) dst) - res->data; + + return res; +} + +static int +int_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; +} + +struct adata * +int_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 4, 4, int_set_cmp); + return dst; +} + +int +int_set_min(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) > 0) + *val = *l; + + return 1; +} + +int +int_set_max(const struct adata *list, u32 *val) +{ + if (!list) + return 0; + + u32 *l = (u32 *) list->data; + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + *val = *l++; + for (i = 1; i < len; i++, l++) + if (int_set_cmp(val, l) < 0) + *val = *l; + + return 1; +} + + +static int +ec_set_cmp(const void *X, const void *Y) +{ + u64 x = ec_get(X, 0); + u64 y = ec_get(Y, 0); + return (x < y) ? -1 : (x > y) ? 1 : 0; +} + +struct adata * +ec_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / 8, 8, ec_set_cmp); + return dst; +} + +void +ec_set_sort_x(struct adata *set) +{ + /* Sort in place */ + qsort(set->data, set->length / 8, 8, ec_set_cmp); +} + +int +ec_set_min(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) > 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + +int +ec_set_max(const struct adata *list, u64 *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 2; + for (i = 2; i < len; i += 2, l += 2) + if (ec_set_cmp(res, l) < 0) + res = l; + + *val = ec_generic(res[0], res[1]); + return 1; +} + + +static int +lc_set_cmp(const void *X, const void *Y) +{ + const u32 *x = X, *y = Y; + if (x[0] != y[0]) + return (x[0] > y[0]) ? 1 : -1; + if (x[1] != y[1]) + return (x[1] > y[1]) ? 1 : -1; + if (x[2] != y[2]) + return (x[2] > y[2]) ? 1 : -1; + return 0; +} + +struct adata * +lc_set_sort(struct linpool *pool, const struct adata *src) +{ + struct adata *dst = lp_alloc_adata(pool, src->length); + memcpy(dst->data, src->data, src->length); + qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); + return dst; +} + +int +lc_set_min(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) > 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} + +int +lc_set_max(const struct adata *list, lcomm *val) +{ + if (!list) + return 0; + + u32 *l = int_set_get_data(list); + int len = int_set_get_size(list); + int i; + + if (len < 1) + return 0; + + u32 *res = l; l += 3; + for (i = 3; i < len; i += 3, l += 3) + if (lc_set_cmp(res, l) < 0) + res = l; + + *val = (lcomm) { res[0], res[1], res[2] }; + return 1; +} diff --git a/lib/a-set_test.c b/lib/a-set_test.c new file mode 100644 index 00000000..3280031f --- /dev/null +++ b/lib/a-set_test.c @@ -0,0 +1,240 @@ +/* + * BIRD -- Set/Community-list Operations Tests + * + * (c) 2015 CZ.NIC z.s.p.o. + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "test/birdtest.h" +#include "test/bt-utils.h" + +#include "lib/net.h" +#include "nest/rt.h" +#include "lib/attrs.h" +#include "lib/resource.h" + +#define SET_SIZE 10 +static const struct adata *set_sequence; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_same; /* <0; SET_SIZE) */ +static const struct adata *set_sequence_higher; /* + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_ATTRS_H_ +#define _BIRD_ATTRS_H_ + +#include +#include "lib/unaligned.h" +#include "lib/route.h" + + +/* a-path.c */ + +#define AS_PATH_SET 1 /* Types of path segments */ +#define AS_PATH_SEQUENCE 2 +#define AS_PATH_CONFED_SEQUENCE 3 +#define AS_PATH_CONFED_SET 4 + +#define AS_PATH_MAXLEN 10000 + +#define AS_TRANS 23456 +/* AS_TRANS is used when we need to store 32bit ASN larger than 0xFFFF + * to 16bit slot (like in 16bit AS_PATH). See RFC 4893 for details + */ + +struct f_tree; + +int as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen); +int as_path_16to32(byte *dst, const byte *src, uint len); +int as_path_32to16(byte *dst, const byte *src, uint len); +int as_path_contains_as4(const struct adata *path); +int as_path_contains_confed(const struct adata *path); +struct adata *as_path_strip_confed(struct linpool *pool, const struct adata *op); +struct adata *as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as); +struct adata *as_path_to_old(struct linpool *pool, const struct adata *path); +struct adata *as_path_cut(struct linpool *pool, const struct adata *path, uint num); +const struct adata *as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2); +void as_path_format(const struct adata *path, byte *buf, uint size); +int as_path_getlen(const struct adata *path); +int as_path_getlen_int(const struct adata *path, int bs); +int as_path_get_first(const struct adata *path, u32 *orig_as); +int as_path_get_first_regular(const struct adata *path, u32 *last_as); +int as_path_get_last(const struct adata *path, u32 *last_as); +u32 as_path_get_last_nonaggregated(const struct adata *path); +int as_path_contains(const struct adata *path, u32 as, int min); +int as_path_match_set(const struct adata *path, const struct f_tree *set); +const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos); + +static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as) +{ return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); } + + +#define PM_ASN 0 +#define PM_QUESTION 1 +#define PM_ASTERISK 2 +#define PM_ASN_EXPR 3 +#define PM_ASN_RANGE 4 +#define PM_ASN_SET 5 +#define PM_LOOP 6 + +struct f_path_mask_item { + union { + u32 asn; /* PM_ASN */ + const struct f_line *expr; /* PM_ASN_EXPR */ + const struct f_tree *set; /* PM_ASN_SET */ + struct { /* PM_ASN_RANGE */ + u32 from; + u32 to; + }; + }; + int kind; +}; + +struct f_path_mask { + uint len; + struct f_path_mask_item item[0]; +}; + +int as_path_match(const struct adata *path, const struct f_path_mask *mask); + + +/* Counterparts to appropriate as_path_* functions */ + +static inline int +aggregator_16to32(byte *dst, const byte *src) +{ + put_u32(dst, get_u16(src)); + memcpy(dst+4, src+2, 4); + return 8; +} + +static inline int +aggregator_32to16(byte *dst, const byte *src) +{ + put_u16(dst, get_u32(src)); + memcpy(dst+2, src+4, 4); + return 6; +} + +static inline int +aggregator_contains_as4(const struct adata *a) +{ + return get_u32(a->data) > 0xFFFF; +} + +static inline struct adata * +aggregator_to_old(struct linpool *pool, const struct adata *a) +{ + struct adata *d = lp_alloc_adata(pool, 8); + put_u32(d->data, AS_TRANS); + memcpy(d->data + 4, a->data + 4, 4); + return d; +} + + +/* a-set.c */ + + +/* Extended Community subtypes (kinds) */ +enum ec_subtype { + EC_RT = 0x0002, + EC_RO = 0x0003, + EC_GENERIC = 0xFFFF, +}; + +static inline const char *ec_subtype_str(const enum ec_subtype ecs) { + switch (ecs) { + case EC_RT: return "rt"; + case EC_RO: return "ro"; + default: return NULL; + } +} + +/* Transitive bit (for first u32 half of EC) */ +#define EC_TBIT 0x40000000 + +#define ECOMM_LENGTH 8 + +static inline int int_set_get_size(const struct adata *list) +{ return list->length / 4; } + +static inline int ec_set_get_size(const struct adata *list) +{ return list->length / 8; } + +static inline int lc_set_get_size(const struct adata *list) +{ return list->length / 12; } + +static inline u32 *int_set_get_data(const struct adata *list) +{ return (u32 *) list->data; } + +static inline u32 ec_hi(u64 ec) { return ec >> 32; } +static inline u32 ec_lo(u64 ec) { return ec; } +static inline u64 ec_get(const u32 *l, int i) +{ return (((u64) l[i]) << 32) | l[i+1]; } + +/* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ +static inline u64 ec_as2(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0000) << 48) | (key << 32) | val; } + +/* RFC 5668 4-Octet AS Specific BGP Extended Community */ +static inline u64 ec_as4(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0200) << 48) | (key << 16) | val; } + +/* RFC 4360 3.2. IPv4 Address Specific Extended Community */ +static inline u64 ec_ip4(enum ec_subtype kind, u64 key, u64 val) +{ return (((u64) kind | 0x0100) << 48) | (key << 16) | val; } + +static inline u64 ec_generic(u64 key, u64 val) +{ return (key << 32) | val; } + +/* Large community value */ +typedef struct lcomm { + u32 asn; + u32 ldp1; + u32 ldp2; +} lcomm; + +#define LCOMM_LENGTH 12 + +static inline lcomm lc_get(const u32 *l, int i) +{ return (lcomm) { l[i], l[i+1], l[i+2] }; } + +static inline void lc_put(u32 *l, lcomm v) +{ l[0] = v.asn; l[1] = v.ldp1; l[2] = v.ldp2; } + +static inline int lc_match(const u32 *l, int i, lcomm v) +{ return (l[i] == v.asn && l[i+1] == v.ldp1 && l[i+2] == v.ldp2); } + +static inline u32 *lc_copy(u32 *dst, const u32 *src) +{ memcpy(dst, src, LCOMM_LENGTH); return dst + 3; } + + +int int_set_format(const struct adata *set, int way, int from, byte *buf, uint size); +int ec_format(byte *buf, u64 ec); +int ec_set_format(const struct adata *set, int from, byte *buf, uint size); +int lc_format(byte *buf, lcomm lc); +int lc_set_format(const struct adata *set, int from, byte *buf, uint size); +int int_set_contains(const struct adata *list, u32 val); +int ec_set_contains(const struct adata *list, u64 val); +int lc_set_contains(const struct adata *list, lcomm val); +const struct adata *int_set_prepend(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *int_set_add(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *ec_set_add(struct linpool *pool, const struct adata *list, u64 val); +const struct adata *lc_set_add(struct linpool *pool, const struct adata *list, lcomm val); +const struct adata *int_set_del(struct linpool *pool, const struct adata *list, u32 val); +const struct adata *ec_set_del(struct linpool *pool, const struct adata *list, u64 val); +const struct adata *lc_set_del(struct linpool *pool, const struct adata *list, lcomm val); +const struct adata *int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); +const struct adata *ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); +const struct adata *lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); + +struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set); +struct adata *int_set_sort(struct linpool *pool, const struct adata *src); +struct adata *ec_set_sort(struct linpool *pool, const struct adata *src); +struct adata *lc_set_sort(struct linpool *pool, const struct adata *src); +int int_set_min(const struct adata *list, u32 *val); +int ec_set_min(const struct adata *list, u64 *val); +int lc_set_min(const struct adata *list, lcomm *val); +int int_set_max(const struct adata *list, u32 *val); +int ec_set_max(const struct adata *list, u64 *val); +int lc_set_max(const struct adata *list, lcomm *val); + +void ec_set_sort_x(struct adata *set); /* Sort in place */ + +#endif diff --git a/nest/Makefile b/nest/Makefile index 7d451ba4..c0765530 100644 --- a/nest/Makefile +++ b/nest/Makefile @@ -1,4 +1,4 @@ -src := a-path.c a-set.c cli.c cmds.c iface.c locks.c neighbor.c password.c proto.c proto-build.c rt-attr.c rt-dev.c rt-fib.c rt-show.c rt-table.c +src := cli.c cmds.c iface.c locks.c neighbor.c password.c proto.c proto-build.c rt-attr.c rt-dev.c rt-fib.c rt-show.c rt-table.c obj := $(src-o-files) $(all-daemon) $(cf-local) @@ -8,6 +8,6 @@ $(proto-build-c): $(lastword $(MAKEFILE_LIST)) $(E)echo GEN $@ $(Q)echo "$(patsubst %,void %(void); ,$(PROTO_BUILD)) void protos_build_gen(void) { $(patsubst %, %(); ,$(PROTO_BUILD))}" > $@ -tests_src := a-set_test.c a-path_test.c +tests_src := tests_targets := $(tests_targets) $(tests-target-files) tests_objs := $(tests_objs) $(src-o-files) diff --git a/nest/a-path.c b/nest/a-path.c deleted file mode 100644 index 64504c93..00000000 --- a/nest/a-path.c +++ /dev/null @@ -1,905 +0,0 @@ -/* - * BIRD -- Path Operations - * - * (c) 2000 Martin Mares - * (c) 2000 Pavel Machek - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include "nest/bird.h" -#include "nest/rt.h" -#include "nest/attrs.h" -#include "lib/resource.h" -#include "lib/unaligned.h" -#include "lib/string.h" -#include "filter/data.h" - -// static inline void put_as(byte *data, u32 as) { put_u32(data, as); } -// static inline u32 get_as(byte *data) { return get_u32(data); } - -#define put_as put_u32 -#define get_as get_u32 -#define BS 4 /* Default block size of ASN (autonomous system number) */ - -#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; }) - -int -as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen) -{ - byte *pos = data; - char *err_dsc = NULL; - uint err_val = 0; - - while (len) - { - if (len < 2) - BAD("segment framing error", 0); - - /* Process one AS path segment */ - uint type = pos[0]; - uint slen = 2 + bs * pos[1]; - - if (len < slen) - BAD("segment framing error", len); - - switch (type) - { - case AS_PATH_SET: - if (!sets) - BAD("AS_SET segment", type); - break; - - case AS_PATH_SEQUENCE: - break; - - case AS_PATH_CONFED_SEQUENCE: - if (!confed) - BAD("AS_CONFED_SEQUENCE segment", type); - break; - - case AS_PATH_CONFED_SET: - if (!sets || !confed) - BAD("AS_CONFED_SET segment", type); - break; - - default: - BAD("unknown segment", type); - } - - if (pos[1] == 0) - BAD("zero-length segment", type); - - pos += slen; - len -= slen; - } - - return 1; - -bad: - if (err) - if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0) - err[0] = 0; - - return 0; -} - -int -as_path_16to32(byte *dst, const byte *src, uint len) -{ - byte *dst0 = dst; - const byte *end = src + len; - uint i, n; - - while (src < end) - { - n = src[1]; - *dst++ = *src++; - *dst++ = *src++; - - for (i = 0; i < n; i++) - { - put_u32(dst, get_u16(src)); - src += 2; - dst += 4; - } - } - - return dst - dst0; -} - -int -as_path_32to16(byte *dst, const byte *src, uint len) -{ - byte *dst0 = dst; - const byte *end = src + len; - uint i, n; - - while (src < end) - { - n = src[1]; - *dst++ = *src++; - *dst++ = *src++; - - for (i = 0; i < n; i++) - { - put_u16(dst, get_u32(src)); - src += 4; - dst += 2; - } - } - - return dst - dst0; -} - -int -as_path_contains_as4(const struct adata *path) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - uint i, n; - - while (pos < end) - { - n = pos[1]; - pos += 2; - - for (i = 0; i < n; i++) - { - if (get_as(pos) > 0xFFFF) - return 1; - - pos += BS; - } - } - - return 0; -} - -int -as_path_contains_confed(const struct adata *path) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - - while (pos < end) - { - uint type = pos[0]; - uint slen = 2 + BS * pos[1]; - - if ((type == AS_PATH_CONFED_SEQUENCE) || - (type == AS_PATH_CONFED_SET)) - return 1; - - pos += slen; - } - - return 0; -} - -struct adata * -as_path_strip_confed(struct linpool *pool, const struct adata *path) -{ - struct adata *res = lp_alloc_adata(pool, path->length); - const byte *src = path->data; - const byte *end = src + path->length; - byte *dst = res->data; - - while (src < end) - { - uint type = src[0]; - uint slen = 2 + BS * src[1]; - - /* Copy regular segments */ - if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE)) - { - memcpy(dst, src, slen); - dst += slen; - } - - src += slen; - } - - /* Fix the result length */ - res->length = dst - res->data; - - return res; -} - -struct adata * -as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as) -{ - struct adata *np; - const byte *pos = op->data; - uint len = op->length; - - if (len && (pos[0] == seq) && (pos[1] < 255)) - { - /* Starting with matching segment => just prepend the AS number */ - np = lp_alloc_adata(pool, len + BS); - np->data[0] = seq; - np->data[1] = pos[1] + 1; - put_as(np->data + 2, as); - - uint dlen = BS * pos[1]; - memcpy(np->data + 2 + BS, pos + 2, dlen); - ADVANCE(pos, len, 2 + dlen); - } - else - { - /* Create a new path segment */ - np = lp_alloc_adata(pool, len + 2 + BS); - np->data[0] = seq; - np->data[1] = 1; - put_as(np->data + 2, as); - } - - if (len) - { - byte *dst = np->data + 2 + BS * np->data[1]; - - memcpy(dst, pos, len); - } - - return np; -} - - -struct adata * -as_path_to_old(struct linpool *pool, const struct adata *path) -{ - struct adata *res = lp_alloc_adata(pool, path->length); - byte *pos = res->data; - byte *end = pos + res->length; - uint i, n; - u32 as; - - /* Copy the whole path */ - memcpy(res->data, path->data, path->length); - - /* Replace 32-bit AS numbers with AS_TRANS */ - while (pos < end) - { - n = pos[1]; - pos += 2; - - for (i = 0; i < n; i++) - { - as = get_as(pos); - if (as > 0xFFFF) - put_as(pos, AS_TRANS); - - pos += BS; - } - } - - return res; -} - -/* - * Cut the path to the length @num, measured to the usual path metric. Note that - * AS_CONFED_* segments have zero length and must be added if they are on edge. - */ -struct adata * -as_path_cut(struct linpool *pool, const struct adata *path, uint num) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - - while (pos < end) - { - uint t = pos[0]; - uint l = pos[1]; - uint n = 0; - - switch (t) - { - case AS_PATH_SET: n = 1; break; - case AS_PATH_SEQUENCE: n = l; break; - case AS_PATH_CONFED_SEQUENCE: n = 0; break; - case AS_PATH_CONFED_SET: n = 0; break; - default: bug("as_path_cut: Invalid path segment"); - } - - /* Cannot add whole segment, so try partial one and finish */ - if (num < n) - { - const byte *nend = pos; - if (num) - nend += 2 + BS * num; - - struct adata *res = lp_alloc_adata(pool, path->length); - res->length = nend - (const byte *) path->data; - memcpy(res->data, path->data, res->length); - - if (num) - { - byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data); - dpos[1] = num; - } - - return res; - } - - num -= n; - pos += 2 + BS * l; - } - - struct adata *res = lp_alloc_adata(pool, path->length); - res->length = path->length; - memcpy(res->data, path->data, res->length); - return res; -} - -/* - * Merge (concatenate) paths @p1 and @p2 and return the result. - * In contrast to other as_path_* functions, @p1 and @p2 may be reused. - */ -const struct adata * -as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2) -{ - if (p1->length == 0) - return p2; - - if (p2->length == 0) - return p1; - - struct adata *res = lp_alloc_adata(pool, p1->length + p2->length); - memcpy(res->data, p1->data, p1->length); - memcpy(res->data + p1->length, p2->data, p2->length); - - return res; -} - -void -as_path_format(const struct adata *path, byte *bb, uint size) -{ - buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf; - const byte *pos = path->data; - const byte *end = pos + path->length; - const char *ops, *cls; - - b->pos[0] = 0; - - while (pos < end) - { - uint type = pos[0]; - uint len = pos[1]; - pos += 2; - - switch (type) - { - case AS_PATH_SET: ops = "{"; cls = "}"; break; - case AS_PATH_SEQUENCE: ops = NULL; cls = NULL; break; - case AS_PATH_CONFED_SEQUENCE: ops = "("; cls = ")"; break; - case AS_PATH_CONFED_SET: ops = "({"; cls = "})"; break; - default: bug("Invalid path segment"); - } - - if (ops) - buffer_puts(b, ops); - - while (len--) - { - buffer_print(b, len ? "%u " : "%u", get_as(pos)); - pos += BS; - } - - if (cls) - buffer_puts(b, cls); - - if (pos < end) - buffer_puts(b, " "); - } - - /* Handle overflow */ - if (b->pos == b->end) - strcpy(b->end - 12, "..."); -} - -int -as_path_getlen(const struct adata *path) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - uint res = 0; - - while (pos < end) - { - uint t = pos[0]; - uint l = pos[1]; - uint n = 0; - - switch (t) - { - case AS_PATH_SET: n = 1; break; - case AS_PATH_SEQUENCE: n = l; break; - case AS_PATH_CONFED_SEQUENCE: n = 0; break; - case AS_PATH_CONFED_SET: n = 0; break; - default: bug("as_path_getlen: Invalid path segment"); - } - - res += n; - pos += 2 + BS * l; - } - - return res; -} - -int -as_path_get_last(const struct adata *path, u32 *orig_as) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - int found = 0; - u32 val = 0; - - while (pos < end) - { - uint type = pos[0]; - uint len = pos[1]; - pos += 2; - - if (!len) - continue; - - switch (type) - { - case AS_PATH_SET: - case AS_PATH_CONFED_SET: - found = 0; - break; - - case AS_PATH_SEQUENCE: - case AS_PATH_CONFED_SEQUENCE: - val = get_as(pos + BS * (len - 1)); - found = 1; - break; - - default: - bug("Invalid path segment"); - } - - pos += BS * len; - } - - if (found) - *orig_as = val; - return found; -} - -u32 -as_path_get_last_nonaggregated(const struct adata *path) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - u32 val = 0; - - while (pos < end) - { - uint type = pos[0]; - uint len = pos[1]; - pos += 2; - - if (!len) - continue; - - switch (type) - { - case AS_PATH_SET: - case AS_PATH_CONFED_SET: - return val; - - case AS_PATH_SEQUENCE: - case AS_PATH_CONFED_SEQUENCE: - val = get_as(pos + BS * (len - 1)); - break; - - default: - bug("Invalid path segment"); - } - - pos += BS * len; - } - - return val; -} - -int -as_path_get_first(const struct adata *path, u32 *last_as) -{ - const u8 *p = path->data; - - if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0)) - return 0; - - *last_as = get_as(p+2); - return 1; -} - -int -as_path_get_first_regular(const struct adata *path, u32 *last_as) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - - while (pos < end) - { - uint type = pos[0]; - uint len = pos[1]; - pos += 2; - - switch (type) - { - case AS_PATH_SET: - return 0; - - case AS_PATH_SEQUENCE: - if (len == 0) - return 0; - - *last_as = get_as(pos); - return 1; - - case AS_PATH_CONFED_SEQUENCE: - case AS_PATH_CONFED_SET: - break; - - default: - bug("Invalid path segment"); - } - - pos += BS * len; - } - - return 0; -} - -int -as_path_contains(const struct adata *path, u32 as, int min) -{ - const u8 *p = path->data; - const u8 *q = p+path->length; - int num = 0; - int i, n; - - while (pdata; - const u8 *q = p+path->length; - int i, n; - - while (plength; - const u8 *p = path->data; - const u8 *q = path->data + len; - u8 *d, *d2; - int i, bt, sn, dn; - u8 buf[len]; - - d = buf; - while (p 0) - { - /* Nonempty block, set block header and advance */ - d[0] = bt; - d[1] = dn; - d = d2; - } - } - - uint nl = d - buf; - if (nl == path->length) - return path; - - struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl); - res->length = nl; - memcpy(res->data, buf, nl); - - return res; -} - - -struct pm_pos -{ - u8 set; - u8 mark; - union - { - const char *sp; - u32 asn; - } val; -}; - -static int -parse_path(const struct adata *path, struct pm_pos *pp) -{ - const byte *pos = path->data; - const byte *end = pos + path->length; - struct pm_pos *op = pp; - uint i; - - while (pos < end) - { - uint type = pos[0]; - uint len = pos[1]; - pos += 2; - - switch (type) - { - case AS_PATH_SET: - case AS_PATH_CONFED_SET: - pp->set = 1; - pp->mark = 0; - pp->val.sp = pos - 1; - pp++; - - pos += BS * len; - break; - - case AS_PATH_SEQUENCE: - case AS_PATH_CONFED_SEQUENCE: - for (i = 0; i < len; i++) - { - pp->set = 0; - pp->mark = 0; - pp->val.asn = get_as(pos); - pp++; - - pos += BS; - } - break; - - default: - bug("Invalid path segment"); - } - } - - return pp - op; -} - -static int -pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2) -{ - u32 gas; - if (! pos->set) - return ((pos->val.asn >= asn) && (pos->val.asn <= asn2)); - - const u8 *p = pos->val.sp; - int len = *p++; - int i; - - for (i = 0; i < len; i++) - { - gas = get_as(p + i * BS); - - if ((gas >= asn) && (gas <= asn2)) - return 1; - } - - return 0; -} - -static int -pm_match_set(const struct pm_pos *pos, const struct f_tree *set) -{ - struct f_val asn = { .type = T_INT }; - - if (! pos->set) - { - asn.val.i = pos->val.asn; - return !!find_tree(set, &asn); - } - - const u8 *p = pos->val.sp; - int len = *p++; - int i; - - for (i = 0; i < len; i++) - { - asn.val.i = get_as(p + i * BS); - if (find_tree(set, &asn)) - return 1; - } - - return 0; -} - -static inline int -pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2) -{ - return ((mask->kind == PM_QUESTION) || - ((mask->kind != PM_ASN_SET) ? - pm_match_val(pos, asn, asn2) : - pm_match_set(pos, mask->set))); -} - -static void -pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh) -{ - int j = *i; - - if (pos[j].set) - do { pos[j].mark = 1; j++; } - while ((j < plen) && pos[j].set); - else - j++; - - pos[j].mark = 1; - - /* Update low, high based on first and last marked pos */ - int l = pos[*i].set ? *i : j; - - *nl = (*nl < 0) ? l : MIN(*nl, l); - *nh = MAX(*nh, j); - *i = j; -} - -/* AS path matching is nontrivial. Because AS path can - * contain sets, it is not a plain wildcard matching. A set - * in an AS path is interpreted as it might represent any - * sequence of AS numbers from that set (possibly with - * repetitions). So it is also a kind of a pattern, - * more complicated than a path mask. - * - * The algorithm for AS path matching is a variant - * of nondeterministic finite state machine, where - * positions in AS path are states, and items in - * path mask are input for that finite state machine. - * During execution of the algorithm we maintain a set - * of marked states - a state is marked if it can be - * reached by any walk through NFSM with regard to - * currently processed part of input. When we process - * next part of mask, we advance each marked state. - * We start with marked first position, when we - * run out of marked positions, we reject. When - * we process the whole mask, we accept if final position - * (auxiliary position after last real position in AS path) - * is marked. - */ -int -as_path_match(const struct adata *path, const struct f_path_mask *mask) -{ - struct pm_pos pos[2048 + 1]; - int plen = parse_path(path, pos); - int l, h, i, nh, nl, last, loop; - u32 val = 0; - u32 val2 = 0; - - /* l and h are bound of interval of positions where - are marked states */ - - pos[plen].set = 0; - pos[plen].mark = 0; - - l = h = loop = 0; - pos[0].mark = 1; - - for (uint m=0; m < mask->len; m++) - { - /* We remove this mark to not step after pos[plen] */ - pos[plen].mark = 0; - - switch (mask->item[m].kind) - { - case PM_ASTERISK: - for (i = l; i <= plen; i++) - pos[i].mark = 1; - h = plen; - break; - - case PM_LOOP: - loop = 1; - break; - - case PM_ASN: /* Define single ASN as ASN..ASN - very narrow interval */ - val2 = val = mask->item[m].asn; - goto step; - case PM_ASN_EXPR: - bug("Expressions should be evaluated on AS path mask construction."); - case PM_ASN_RANGE: - val = mask->item[m].from; - val2 = mask->item[m].to; - goto step; - case PM_QUESTION: - case PM_ASN_SET: - step: - nh = nl = -1; - last = plen; - for (i = h; i >= l; i--) - if (pos[i].mark) - { - pos[i].mark = 0; - int j = i; - - match: - if (pm_match(pos + j, &mask->item[m], val, val2)) - { - pm_mark(pos, &j, plen, &nl, &nh); - if (loop && (j < last)) - goto match; - } - - last = i; - } - - if (nh < 0) - return 0; - - h = nh; - l = nl; - loop = 0; - break; - } - } - - return pos[plen].mark; -} diff --git a/nest/a-path_test.c b/nest/a-path_test.c deleted file mode 100644 index a6b4d3d8..00000000 --- a/nest/a-path_test.c +++ /dev/null @@ -1,206 +0,0 @@ -/* - * BIRD -- Path Operations Tests - * - * (c) 2015 CZ.NIC z.s.p.o. - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include "test/birdtest.h" -#include "test/bt-utils.h" - -#include "nest/rt.h" -#include "nest/attrs.h" -#include "lib/resource.h" - -#define TESTS_NUM 30 -#define AS_PATH_LENGTH 1000 - -#if AS_PATH_LENGTH > AS_PATH_MAXLEN -#warning "AS_PATH_LENGTH should be <= AS_PATH_MAXLEN" -#endif - -static int -t_as_path_match(void) -{ - int round; - for (round = 0; round < TESTS_NUM; round++) - { - struct adata empty_as_path = {}; - struct adata *as_path = &empty_as_path; - u32 first_prepended, last_prepended; - first_prepended = last_prepended = 0; - - struct f_path_mask *mask = alloca(sizeof(struct f_path_mask) + AS_PATH_LENGTH * sizeof(struct f_path_mask_item)); - mask->len = AS_PATH_LENGTH; - for (int i = AS_PATH_LENGTH - 1; i >= 0; i--) - { - u32 val = bt_random(); - as_path = as_path_prepend(tmp_linpool, as_path, val); - bt_debug("Prepending ASN: %10u \n", val); - - if (i == 0) - last_prepended = val; - if (i == AS_PATH_LENGTH-1) - first_prepended = val; - - mask->item[i].kind = PM_ASN; - mask->item[i].asn = val; - } - - bt_assert_msg(as_path_match(as_path, mask), "Mask should match with AS path"); - - u32 asn; - - bt_assert(as_path_get_first(as_path, &asn)); - bt_assert_msg(asn == last_prepended, "as_path_get_first() should return the last prepended ASN"); - - bt_assert(as_path_get_last(as_path, &asn)); - bt_assert_msg(asn == first_prepended, "as_path_get_last() should return the first prepended ASN"); - - tmp_flush(); - } - - return 1; -} - -static int -t_path_format(void) -{ - struct adata empty_as_path = {}; - struct adata *as_path = &empty_as_path; - - uint i; - for (i = 4294967285; i <= 4294967294; i++) - { - as_path = as_path_prepend(tmp_linpool, as_path, i); - bt_debug("Prepending ASN: %10u \n", i); - } - -#define BUFFER_SIZE 120 - byte buf[BUFFER_SIZE] = {}; - - as_path_format(&empty_as_path, buf, BUFFER_SIZE); - bt_assert_msg(strcmp(buf, "") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); - - as_path_format(as_path, buf, BUFFER_SIZE); - bt_assert_msg(strcmp(buf, "4294967294 4294967293 4294967292 4294967291 4294967290 4294967289 4294967288 4294967287 4294967286 4294967285") == 0, "Buffer(%zu): '%s'", strlen(buf), buf); - -#define SMALL_BUFFER_SIZE 25 - byte buf2[SMALL_BUFFER_SIZE] = {}; - as_path_format(as_path, buf2, SMALL_BUFFER_SIZE); - bt_assert_msg(strcmp(buf2, "4294967294 42...") == 0, "Small Buffer(%zu): '%s'", strlen(buf2), buf2); - - tmp_flush(); - - return 1; -} - -static int -count_asn_in_array(const u32 *array, u32 asn) -{ - int counts_of_contains = 0; - int u; - for (u = 0; u < AS_PATH_LENGTH; u++) - if (array[u] == asn) - counts_of_contains++; - return counts_of_contains; -} - -static int -t_path_include(void) -{ - struct adata empty_as_path = {}; - struct adata *as_path = &empty_as_path; - - u32 as_nums[AS_PATH_LENGTH] = {}; - int i; - for (i = 0; i < AS_PATH_LENGTH; i++) - { - u32 val = bt_random(); - as_nums[i] = val; - as_path = as_path_prepend(tmp_linpool, as_path, val); - } - - for (i = 0; i < AS_PATH_LENGTH; i++) - { - int counts_of_contains = count_asn_in_array(as_nums, as_nums[i]); - bt_assert_msg(as_path_contains(as_path, as_nums[i], counts_of_contains), "AS Path should contains %d-times number %d", counts_of_contains, as_nums[i]); - - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 0) != NULL); - bt_assert(as_path_filter(tmp_linpool, as_path, NULL, as_nums[i], 1) != NULL); - } - - for (i = 0; i < 10000; i++) - { - u32 test_val = bt_random(); - int counts_of_contains = count_asn_in_array(as_nums, test_val); - int result = as_path_contains(as_path, test_val, (counts_of_contains == 0 ? 1 : counts_of_contains)); - - if (counts_of_contains) - bt_assert_msg(result, "As path should contain %d-times the number %u", counts_of_contains, test_val); - else - bt_assert_msg(result == 0, "As path should not contain the number %u", test_val); - } - - tmp_flush(); - - return 1; -} - -#if 0 -static int -t_as_path_converting(void) -{ - struct adata empty_as_path = {}; - struct adata *as_path = &empty_as_path; -#define AS_PATH_LENGTH_FOR_CONVERTING_TEST 10 - - int i; - for (i = 0; i < AS_PATH_LENGTH_FOR_CONVERTING_TEST; i++) - as_path = as_path_prepend(tmp_linpool, as_path, i); - - bt_debug("data length: %u \n", as_path->length); - - byte buffer[100] = {}; - int used_size = as_path_convert_to_new(as_path, buffer, AS_PATH_LENGTH_FOR_CONVERTING_TEST-1); - bt_debug("as_path_convert_to_new: len %d \n%s\n", used_size, buffer); - for (i = 0; i < used_size; i++) - { - bt_debug("\\03%d", buffer[i]); - } - bt_debug("\n"); - bt_assert(memcmp(buffer, - "\032\039\030\030\030\030\030\030\030\039\030\030\030\030\030\030\030\038\030\030\030\030\030\030" - "\030\037\030\030\030\030\030\030\030\036\030\030\030\030", - 38)); - - bzero(buffer, sizeof(buffer)); - int new_used; - used_size = as_path_convert_to_old(as_path, buffer, &new_used); - bt_debug("as_path_convert_to_old: len %d, new_used: %d \n", used_size, new_used); - for (i = 0; i < used_size; i++) - { - bt_debug("\\03%d", buffer[i]); - } - bt_debug("\n"); - bt_assert(memcmp(buffer, - "\032\0310\030\039\030\038\030\037\030\036\030\035\030\034\030\033\030\032\030\031\030\030", - 22)); - - return 1; -} -#endif - -int -main(int argc, char *argv[]) -{ - bt_init(argc, argv); - - bt_test_suite(t_as_path_match, "Testing AS path matching and some a-path utilities."); - bt_test_suite(t_path_format, "Testing formating as path into byte buffer"); - bt_test_suite(t_path_include, "Testing including a AS number in AS path"); - // bt_test_suite(t_as_path_converting, "Testing as_path_convert_to_*() output constancy"); - - return bt_exit_value(); -} diff --git a/nest/a-set.c b/nest/a-set.c deleted file mode 100644 index 93f6431e..00000000 --- a/nest/a-set.c +++ /dev/null @@ -1,695 +0,0 @@ -/* - * BIRD -- Set/Community-list Operations - * - * (c) 2000 Martin Mares - * (c) 2000 Pavel Machek - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include - -#include "nest/bird.h" -#include "nest/rt.h" -#include "nest/attrs.h" -#include "lib/resource.h" -#include "lib/string.h" - -/** - * int_set_format - format an &set for printing - * @set: set attribute to be formatted - * @way: style of format (0 for router ID list, 1 for community list) - * @from: starting position in set - * @buf: destination buffer - * @size: size of buffer - * - * This function takes a set attribute and formats it. @way specifies - * the style of format (router ID / community). @from argument can be - * used to specify the first printed value for the purpose of printing - * untruncated sets even with smaller buffers. If the output fits in - * the buffer, 0 is returned, otherwise the position of the first not - * printed item is returned. This value can be used as @from argument - * in subsequent calls. If truncated output suffices, -1 can be - * instead used as @from, in that case " ..." is eventually added at - * the buffer to indicate truncation. - */ -int -int_set_format(const struct adata *set, int way, int from, byte *buf, uint size) -{ - u32 *z = (u32 *) set->data; - byte *end = buf + size - 24; - int from2 = MAX(from, 0); - int to = set->length / 4; - int i; - - for (i = from2; i < to; i++) - { - if (buf > end) - { - if (from < 0) - strcpy(buf, " ..."); - else - *buf = 0; - return i; - } - - if (i > from2) - *buf++ = ' '; - - if (way) - buf += bsprintf(buf, "(%d,%d)", z[i] >> 16, z[i] & 0xffff); - else - buf += bsprintf(buf, "%R", z[i]); - } - *buf = 0; - return 0; -} - -int -ec_format(byte *buf, u64 ec) -{ - u32 type, key, val; - char tbuf[16]; - const char *kind; - - type = ec >> 48; - kind = ec_subtype_str(type & 0xf0ff); - - if (!kind) { - bsprintf(tbuf, "unknown 0x%x", type); - kind = tbuf; - } - - switch (ec >> 56) - { - /* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ - case 0x00: - case 0x40: - key = (ec >> 32) & 0xFFFF; - val = ec; - return bsprintf(buf, "(%s, %u, %u)", kind, key, val); - - /* RFC 4360 3.2. IPv4 Address Specific Extended Community */ - case 0x01: - case 0x41: - key = ec >> 16; - val = ec & 0xFFFF; - return bsprintf(buf, "(%s, %R, %u)", kind, key, val); - - /* RFC 5668 4-Octet AS Specific BGP Extended Community */ - case 0x02: - case 0x42: - key = ec >> 16; - val = ec & 0xFFFF; - return bsprintf(buf, "(%s, %u, %u)", kind, key, val); - - /* Generic format for unknown kinds of extended communities */ - default: - key = ec >> 32; - val = ec; - return bsprintf(buf, "(generic, 0x%x, 0x%x)", key, val); - } - -} - -int -ec_set_format(const struct adata *set, int from, byte *buf, uint size) -{ - u32 *z = int_set_get_data(set); - byte *end = buf + size - 64; - int from2 = MAX(from, 0); - int to = int_set_get_size(set); - int i; - - for (i = from2; i < to; i += 2) - { - if (buf > end) - { - if (from < 0) - strcpy(buf, " ..."); - else - *buf = 0; - return i; - } - - if (i > from2) - *buf++ = ' '; - - buf += ec_format(buf, ec_get(z, i)); - } - *buf = 0; - return 0; -} - -int -lc_format(byte *buf, lcomm lc) -{ - return bsprintf(buf, "(%u, %u, %u)", lc.asn, lc.ldp1, lc.ldp2); -} - -int -lc_set_format(const struct adata *set, int from, byte *buf, uint bufsize) -{ - u32 *d = (u32 *) set->data; - byte *end = buf + bufsize - 64; - int from2 = MAX(from, 0); - int to = set->length / 4; - int i; - - for (i = from2; i < to; i += 3) - { - if (buf > end) - { - if (from < 0) - strcpy(buf, "..."); - else - buf[-1] = 0; - return i; - } - - buf += bsprintf(buf, "(%u, %u, %u)", d[i], d[i+1], d[i+2]); - *buf++ = ' '; - } - - if (i != from2) - buf--; - - *buf = 0; - return 0; -} - -int -int_set_contains(const struct adata *list, u32 val) -{ - if (!list) - return 0; - - u32 *l = (u32 *) list->data; - int len = int_set_get_size(list); - int i; - - for (i = 0; i < len; i++) - if (*l++ == val) - return 1; - - return 0; -} - -int -ec_set_contains(const struct adata *list, u64 val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - u32 eh = ec_hi(val); - u32 el = ec_lo(val); - int i; - - for (i=0; i < len; i += 2) - if (l[i] == eh && l[i+1] == el) - return 1; - - return 0; -} - -int -lc_set_contains(const struct adata *list, lcomm val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - for (i = 0; i < len; i += 3) - if (lc_match(l, i, val)) - return 1; - - return 0; -} - -const struct adata * -int_set_prepend(struct linpool *pool, const struct adata *list, u32 val) -{ - struct adata *res; - int len; - - if (int_set_contains(list, val)) - return list; - - len = list ? list->length : 0; - res = lp_alloc(pool, sizeof(struct adata) + len + 4); - res->length = len + 4; - - if (list) - memcpy(res->data + 4, list->data, list->length); - - * (u32 *) res->data = val; - - return res; -} - -const struct adata * -int_set_add(struct linpool *pool, const struct adata *list, u32 val) -{ - struct adata *res; - int len; - - if (int_set_contains(list, val)) - return list; - - len = list ? list->length : 0; - res = lp_alloc(pool, sizeof(struct adata) + len + 4); - res->length = len + 4; - - if (list) - memcpy(res->data, list->data, list->length); - - * (u32 *) (res->data + len) = val; - - return res; -} - -const struct adata * -ec_set_add(struct linpool *pool, const struct adata *list, u64 val) -{ - if (ec_set_contains(list, val)) - return list; - - int olen = list ? list->length : 0; - struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + 8); - res->length = olen + 8; - - if (list) - memcpy(res->data, list->data, list->length); - - u32 *l = (u32 *) (res->data + olen); - l[0] = ec_hi(val); - l[1] = ec_lo(val); - - return res; -} - -const struct adata * -lc_set_add(struct linpool *pool, const struct adata *list, lcomm val) -{ - if (lc_set_contains(list, val)) - return list; - - int olen = list ? list->length : 0; - struct adata *res = lp_alloc(pool, sizeof(struct adata) + olen + LCOMM_LENGTH); - res->length = olen + LCOMM_LENGTH; - - if (list) - memcpy(res->data, list->data, list->length); - - lc_put((u32 *) (res->data + olen), val); - - return res; -} - -const struct adata * -int_set_del(struct linpool *pool, const struct adata *list, u32 val) -{ - if (!int_set_contains(list, val)) - return list; - - struct adata *res; - res = lp_alloc(pool, sizeof(struct adata) + list->length - 4); - res->length = list->length - 4; - - u32 *l = int_set_get_data(list); - u32 *k = int_set_get_data(res); - int len = int_set_get_size(list); - int i; - - for (i = 0; i < len; i++) - if (l[i] != val) - *k++ = l[i]; - - return res; -} - -const struct adata * -ec_set_del(struct linpool *pool, const struct adata *list, u64 val) -{ - if (!ec_set_contains(list, val)) - return list; - - struct adata *res; - res = lp_alloc(pool, sizeof(struct adata) + list->length - 8); - res->length = list->length - 8; - - u32 *l = int_set_get_data(list); - u32 *k = int_set_get_data(res); - int len = int_set_get_size(list); - u32 eh = ec_hi(val); - u32 el = ec_lo(val); - int i; - - for (i=0; i < len; i += 2) - if (! (l[i] == eh && l[i+1] == el)) - { - *k++ = l[i]; - *k++ = l[i+1]; - } - - return res; -} - -const struct adata * -lc_set_del(struct linpool *pool, const struct adata *list, lcomm val) -{ - if (!lc_set_contains(list, val)) - return list; - - struct adata *res; - res = lp_alloc(pool, sizeof(struct adata) + list->length - LCOMM_LENGTH); - res->length = list->length - LCOMM_LENGTH; - - u32 *l = int_set_get_data(list); - u32 *k = int_set_get_data(res); - int len = int_set_get_size(list); - int i; - - for (i=0; i < len; i += 3) - if (! lc_match(l, i, val)) - k = lc_copy(k, l+i); - - return res; -} - -const struct adata * -int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) -{ - if (!l1) - return l2; - if (!l2) - return l1; - - struct adata *res; - int len = int_set_get_size(l2); - u32 *l = int_set_get_data(l2); - u32 tmp[len]; - u32 *k = tmp; - int i; - - for (i = 0; i < len; i++) - if (!int_set_contains(l1, l[i])) - *k++ = l[i]; - - if (k == tmp) - return l1; - - len = (k - tmp) * 4; - res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); - res->length = l1->length + len; - memcpy(res->data, l1->data, l1->length); - memcpy(res->data + l1->length, tmp, len); - return res; -} - -const struct adata * -ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) -{ - if (!l1) - return l2; - if (!l2) - return l1; - - struct adata *res; - int len = int_set_get_size(l2); - u32 *l = int_set_get_data(l2); - u32 tmp[len]; - u32 *k = tmp; - int i; - - for (i = 0; i < len; i += 2) - if (!ec_set_contains(l1, ec_get(l, i))) - { - *k++ = l[i]; - *k++ = l[i+1]; - } - - if (k == tmp) - return l1; - - len = (k - tmp) * 4; - res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); - res->length = l1->length + len; - memcpy(res->data, l1->data, l1->length); - memcpy(res->data + l1->length, tmp, len); - return res; -} - -const struct adata * -lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2) -{ - if (!l1) - return l2; - if (!l2) - return l1; - - struct adata *res; - int len = int_set_get_size(l2); - u32 *l = int_set_get_data(l2); - u32 tmp[len]; - u32 *k = tmp; - int i; - - for (i = 0; i < len; i += 3) - if (!lc_set_contains(l1, lc_get(l, i))) - k = lc_copy(k, l+i); - - if (k == tmp) - return l1; - - len = (k - tmp) * 4; - res = lp_alloc(pool, sizeof(struct adata) + l1->length + len); - res->length = l1->length + len; - memcpy(res->data, l1->data, l1->length); - memcpy(res->data + l1->length, tmp, len); - return res; -} - - -struct adata * -ec_set_del_nontrans(struct linpool *pool, const struct adata *set) -{ - adata *res = lp_alloc_adata(pool, set->length); - u32 *src = int_set_get_data(set); - u32 *dst = int_set_get_data(res); - int len = int_set_get_size(set); - int i; - - /* Remove non-transitive communities (EC_TBIT set) */ - for (i = 0; i < len; i += 2) - { - if (src[i] & EC_TBIT) - continue; - - *dst++ = src[i]; - *dst++ = src[i+1]; - } - - res->length = ((byte *) dst) - res->data; - - return res; -} - -static int -int_set_cmp(const void *X, const void *Y) -{ - const u32 *x = X, *y = Y; - return (*x < *y) ? -1 : (*x > *y) ? 1 : 0; -} - -struct adata * -int_set_sort(struct linpool *pool, const struct adata *src) -{ - struct adata *dst = lp_alloc_adata(pool, src->length); - memcpy(dst->data, src->data, src->length); - qsort(dst->data, dst->length / 4, 4, int_set_cmp); - return dst; -} - -int -int_set_min(const struct adata *list, u32 *val) -{ - if (!list) - return 0; - - u32 *l = (u32 *) list->data; - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - *val = *l++; - for (i = 1; i < len; i++, l++) - if (int_set_cmp(val, l) > 0) - *val = *l; - - return 1; -} - -int -int_set_max(const struct adata *list, u32 *val) -{ - if (!list) - return 0; - - u32 *l = (u32 *) list->data; - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - *val = *l++; - for (i = 1; i < len; i++, l++) - if (int_set_cmp(val, l) < 0) - *val = *l; - - return 1; -} - - -static int -ec_set_cmp(const void *X, const void *Y) -{ - u64 x = ec_get(X, 0); - u64 y = ec_get(Y, 0); - return (x < y) ? -1 : (x > y) ? 1 : 0; -} - -struct adata * -ec_set_sort(struct linpool *pool, const struct adata *src) -{ - struct adata *dst = lp_alloc_adata(pool, src->length); - memcpy(dst->data, src->data, src->length); - qsort(dst->data, dst->length / 8, 8, ec_set_cmp); - return dst; -} - -void -ec_set_sort_x(struct adata *set) -{ - /* Sort in place */ - qsort(set->data, set->length / 8, 8, ec_set_cmp); -} - -int -ec_set_min(const struct adata *list, u64 *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 2; - for (i = 2; i < len; i += 2, l += 2) - if (ec_set_cmp(res, l) > 0) - res = l; - - *val = ec_generic(res[0], res[1]); - return 1; -} - -int -ec_set_max(const struct adata *list, u64 *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 2; - for (i = 2; i < len; i += 2, l += 2) - if (ec_set_cmp(res, l) < 0) - res = l; - - *val = ec_generic(res[0], res[1]); - return 1; -} - - -static int -lc_set_cmp(const void *X, const void *Y) -{ - const u32 *x = X, *y = Y; - if (x[0] != y[0]) - return (x[0] > y[0]) ? 1 : -1; - if (x[1] != y[1]) - return (x[1] > y[1]) ? 1 : -1; - if (x[2] != y[2]) - return (x[2] > y[2]) ? 1 : -1; - return 0; -} - -struct adata * -lc_set_sort(struct linpool *pool, const struct adata *src) -{ - struct adata *dst = lp_alloc_adata(pool, src->length); - memcpy(dst->data, src->data, src->length); - qsort(dst->data, dst->length / LCOMM_LENGTH, LCOMM_LENGTH, lc_set_cmp); - return dst; -} - -int -lc_set_min(const struct adata *list, lcomm *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 3; - for (i = 3; i < len; i += 3, l += 3) - if (lc_set_cmp(res, l) > 0) - res = l; - - *val = (lcomm) { res[0], res[1], res[2] }; - return 1; -} - -int -lc_set_max(const struct adata *list, lcomm *val) -{ - if (!list) - return 0; - - u32 *l = int_set_get_data(list); - int len = int_set_get_size(list); - int i; - - if (len < 1) - return 0; - - u32 *res = l; l += 3; - for (i = 3; i < len; i += 3, l += 3) - if (lc_set_cmp(res, l) < 0) - res = l; - - *val = (lcomm) { res[0], res[1], res[2] }; - return 1; -} diff --git a/nest/a-set_test.c b/nest/a-set_test.c deleted file mode 100644 index daa6ab74..00000000 --- a/nest/a-set_test.c +++ /dev/null @@ -1,240 +0,0 @@ -/* - * BIRD -- Set/Community-list Operations Tests - * - * (c) 2015 CZ.NIC z.s.p.o. - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#include "test/birdtest.h" -#include "test/bt-utils.h" - -#include "lib/net.h" -#include "nest/rt.h" -#include "nest/attrs.h" -#include "lib/resource.h" - -#define SET_SIZE 10 -static const struct adata *set_sequence; /* <0; SET_SIZE) */ -static const struct adata *set_sequence_same; /* <0; SET_SIZE) */ -static const struct adata *set_sequence_higher; /* - * - * Can be freely distributed and used under the terms of the GNU GPL. - */ - -#ifndef _BIRD_ATTRS_H_ -#define _BIRD_ATTRS_H_ - -#include -#include "lib/unaligned.h" -#include "lib/route.h" - - -/* a-path.c */ - -#define AS_PATH_SET 1 /* Types of path segments */ -#define AS_PATH_SEQUENCE 2 -#define AS_PATH_CONFED_SEQUENCE 3 -#define AS_PATH_CONFED_SET 4 - -#define AS_PATH_MAXLEN 10000 - -#define AS_TRANS 23456 -/* AS_TRANS is used when we need to store 32bit ASN larger than 0xFFFF - * to 16bit slot (like in 16bit AS_PATH). See RFC 4893 for details - */ - -struct f_tree; - -int as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen); -int as_path_16to32(byte *dst, const byte *src, uint len); -int as_path_32to16(byte *dst, const byte *src, uint len); -int as_path_contains_as4(const struct adata *path); -int as_path_contains_confed(const struct adata *path); -struct adata *as_path_strip_confed(struct linpool *pool, const struct adata *op); -struct adata *as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as); -struct adata *as_path_to_old(struct linpool *pool, const struct adata *path); -struct adata *as_path_cut(struct linpool *pool, const struct adata *path, uint num); -const struct adata *as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2); -void as_path_format(const struct adata *path, byte *buf, uint size); -int as_path_getlen(const struct adata *path); -int as_path_getlen_int(const struct adata *path, int bs); -int as_path_get_first(const struct adata *path, u32 *orig_as); -int as_path_get_first_regular(const struct adata *path, u32 *last_as); -int as_path_get_last(const struct adata *path, u32 *last_as); -u32 as_path_get_last_nonaggregated(const struct adata *path); -int as_path_contains(const struct adata *path, u32 as, int min); -int as_path_match_set(const struct adata *path, const struct f_tree *set); -const struct adata *as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos); - -static inline struct adata *as_path_prepend(struct linpool *pool, const struct adata *path, u32 as) -{ return as_path_prepend2(pool, path, AS_PATH_SEQUENCE, as); } - - -#define PM_ASN 0 -#define PM_QUESTION 1 -#define PM_ASTERISK 2 -#define PM_ASN_EXPR 3 -#define PM_ASN_RANGE 4 -#define PM_ASN_SET 5 -#define PM_LOOP 6 - -struct f_path_mask_item { - union { - u32 asn; /* PM_ASN */ - const struct f_line *expr; /* PM_ASN_EXPR */ - const struct f_tree *set; /* PM_ASN_SET */ - struct { /* PM_ASN_RANGE */ - u32 from; - u32 to; - }; - }; - int kind; -}; - -struct f_path_mask { - uint len; - struct f_path_mask_item item[0]; -}; - -int as_path_match(const struct adata *path, const struct f_path_mask *mask); - - -/* Counterparts to appropriate as_path_* functions */ - -static inline int -aggregator_16to32(byte *dst, const byte *src) -{ - put_u32(dst, get_u16(src)); - memcpy(dst+4, src+2, 4); - return 8; -} - -static inline int -aggregator_32to16(byte *dst, const byte *src) -{ - put_u16(dst, get_u32(src)); - memcpy(dst+2, src+4, 4); - return 6; -} - -static inline int -aggregator_contains_as4(const struct adata *a) -{ - return get_u32(a->data) > 0xFFFF; -} - -static inline struct adata * -aggregator_to_old(struct linpool *pool, const struct adata *a) -{ - struct adata *d = lp_alloc_adata(pool, 8); - put_u32(d->data, AS_TRANS); - memcpy(d->data + 4, a->data + 4, 4); - return d; -} - - -/* a-set.c */ - - -/* Extended Community subtypes (kinds) */ -enum ec_subtype { - EC_RT = 0x0002, - EC_RO = 0x0003, - EC_GENERIC = 0xFFFF, -}; - -static inline const char *ec_subtype_str(const enum ec_subtype ecs) { - switch (ecs) { - case EC_RT: return "rt"; - case EC_RO: return "ro"; - default: return NULL; - } -} - -/* Transitive bit (for first u32 half of EC) */ -#define EC_TBIT 0x40000000 - -#define ECOMM_LENGTH 8 - -static inline int int_set_get_size(const struct adata *list) -{ return list->length / 4; } - -static inline int ec_set_get_size(const struct adata *list) -{ return list->length / 8; } - -static inline int lc_set_get_size(const struct adata *list) -{ return list->length / 12; } - -static inline u32 *int_set_get_data(const struct adata *list) -{ return (u32 *) list->data; } - -static inline u32 ec_hi(u64 ec) { return ec >> 32; } -static inline u32 ec_lo(u64 ec) { return ec; } -static inline u64 ec_get(const u32 *l, int i) -{ return (((u64) l[i]) << 32) | l[i+1]; } - -/* RFC 4360 3.1. Two-Octet AS Specific Extended Community */ -static inline u64 ec_as2(enum ec_subtype kind, u64 key, u64 val) -{ return (((u64) kind | 0x0000) << 48) | (key << 32) | val; } - -/* RFC 5668 4-Octet AS Specific BGP Extended Community */ -static inline u64 ec_as4(enum ec_subtype kind, u64 key, u64 val) -{ return (((u64) kind | 0x0200) << 48) | (key << 16) | val; } - -/* RFC 4360 3.2. IPv4 Address Specific Extended Community */ -static inline u64 ec_ip4(enum ec_subtype kind, u64 key, u64 val) -{ return (((u64) kind | 0x0100) << 48) | (key << 16) | val; } - -static inline u64 ec_generic(u64 key, u64 val) -{ return (key << 32) | val; } - -/* Large community value */ -typedef struct lcomm { - u32 asn; - u32 ldp1; - u32 ldp2; -} lcomm; - -#define LCOMM_LENGTH 12 - -static inline lcomm lc_get(const u32 *l, int i) -{ return (lcomm) { l[i], l[i+1], l[i+2] }; } - -static inline void lc_put(u32 *l, lcomm v) -{ l[0] = v.asn; l[1] = v.ldp1; l[2] = v.ldp2; } - -static inline int lc_match(const u32 *l, int i, lcomm v) -{ return (l[i] == v.asn && l[i+1] == v.ldp1 && l[i+2] == v.ldp2); } - -static inline u32 *lc_copy(u32 *dst, const u32 *src) -{ memcpy(dst, src, LCOMM_LENGTH); return dst + 3; } - - -int int_set_format(const struct adata *set, int way, int from, byte *buf, uint size); -int ec_format(byte *buf, u64 ec); -int ec_set_format(const struct adata *set, int from, byte *buf, uint size); -int lc_format(byte *buf, lcomm lc); -int lc_set_format(const struct adata *set, int from, byte *buf, uint size); -int int_set_contains(const struct adata *list, u32 val); -int ec_set_contains(const struct adata *list, u64 val); -int lc_set_contains(const struct adata *list, lcomm val); -const struct adata *int_set_prepend(struct linpool *pool, const struct adata *list, u32 val); -const struct adata *int_set_add(struct linpool *pool, const struct adata *list, u32 val); -const struct adata *ec_set_add(struct linpool *pool, const struct adata *list, u64 val); -const struct adata *lc_set_add(struct linpool *pool, const struct adata *list, lcomm val); -const struct adata *int_set_del(struct linpool *pool, const struct adata *list, u32 val); -const struct adata *ec_set_del(struct linpool *pool, const struct adata *list, u64 val); -const struct adata *lc_set_del(struct linpool *pool, const struct adata *list, lcomm val); -const struct adata *int_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); -const struct adata *ec_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); -const struct adata *lc_set_union(struct linpool *pool, const struct adata *l1, const struct adata *l2); - -struct adata *ec_set_del_nontrans(struct linpool *pool, const struct adata *set); -struct adata *int_set_sort(struct linpool *pool, const struct adata *src); -struct adata *ec_set_sort(struct linpool *pool, const struct adata *src); -struct adata *lc_set_sort(struct linpool *pool, const struct adata *src); -int int_set_min(const struct adata *list, u32 *val); -int ec_set_min(const struct adata *list, u64 *val); -int lc_set_min(const struct adata *list, lcomm *val); -int int_set_max(const struct adata *list, u32 *val); -int ec_set_max(const struct adata *list, u64 *val); -int lc_set_max(const struct adata *list, lcomm *val); - -void ec_set_sort_x(struct adata *set); /* Sort in place */ - -#endif diff --git a/nest/rt-attr.c b/nest/rt-attr.c index 8f4319c5..2fa9b673 100644 --- a/nest/rt-attr.c +++ b/nest/rt-attr.c @@ -49,7 +49,7 @@ #include "nest/protocol.h" #include "nest/iface.h" #include "nest/cli.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "lib/alloca.h" #include "lib/hash.h" #include "lib/idm.h" diff --git a/proto/bgp/attrs.c b/proto/bgp/attrs.c index 3265cb5e..2c0d011f 100644 --- a/proto/bgp/attrs.c +++ b/proto/bgp/attrs.c @@ -16,7 +16,7 @@ #include "nest/iface.h" #include "nest/protocol.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "conf/conf.h" #include "lib/resource.h" #include "lib/string.h" diff --git a/proto/bgp/packets.c b/proto/bgp/packets.c index 5def0f27..8eeae490 100644 --- a/proto/bgp/packets.c +++ b/proto/bgp/packets.c @@ -16,7 +16,7 @@ #include "nest/iface.h" #include "nest/protocol.h" #include "nest/rt.h" -#include "nest/attrs.h" +#include "lib/attrs.h" #include "proto/mrt/mrt.h" #include "conf/conf.h" #include "lib/unaligned.h" -- cgit v1.2.3