From 58ef912c6babf1866193ab04674a5866dd761f13 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 22 Apr 1998 12:58:34 +0000 Subject: First look at data structures. More to come tomorrow... --- nest/Makefile | 3 + nest/bird.h | 24 +++++++ nest/confile.h | 12 ++++ nest/iface.h | 12 ++++ nest/ipv4.h | 20 ++++++ nest/ipv6.h | 21 +++++++ nest/main.c | 23 +++++++ nest/protocol.h | 66 ++++++++++++++++++++ nest/route.h | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 371 insertions(+) create mode 100644 nest/Makefile create mode 100644 nest/bird.h create mode 100644 nest/confile.h create mode 100644 nest/iface.h create mode 100644 nest/ipv4.h create mode 100644 nest/ipv6.h create mode 100644 nest/main.c create mode 100644 nest/protocol.h create mode 100644 nest/route.h (limited to 'nest') diff --git a/nest/Makefile b/nest/Makefile new file mode 100644 index 0000000..d6c0e6e --- /dev/null +++ b/nest/Makefile @@ -0,0 +1,3 @@ +OBJS=main.o + +include $(TOPDIR)/Rules diff --git a/nest/bird.h b/nest/bird.h new file mode 100644 index 0000000..e8c3318 --- /dev/null +++ b/nest/bird.h @@ -0,0 +1,24 @@ +/* + * BIRD Internet Routing Daemon -- Basic Declarations + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_BIRD_H_ +#define _BIRD_BIRD_H_ + +#include +#include + +#ifndef IPV6 +#include +#else +#include +#endif + +extern u32 router_id; /* Our Router ID */ +extern u16 this_as; /* Our Autonomous System Number */ + +#endif diff --git a/nest/confile.h b/nest/confile.h new file mode 100644 index 0000000..1089e76 --- /dev/null +++ b/nest/confile.h @@ -0,0 +1,12 @@ +/* + * BIRD Internet Routing Daemon -- Configuration File + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_CONFILE_H_ +#define _BIRD_CONFILE_H_ + +#endif diff --git a/nest/iface.h b/nest/iface.h new file mode 100644 index 0000000..2d0d757 --- /dev/null +++ b/nest/iface.h @@ -0,0 +1,12 @@ +/* + * BIRD Internet Routing Daemon -- Network Interfaces + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_IFACE_H_ +#define _BIRD_IFACE_H_ + +#endif diff --git a/nest/ipv4.h b/nest/ipv4.h new file mode 100644 index 0000000..7524229 --- /dev/null +++ b/nest/ipv4.h @@ -0,0 +1,20 @@ +/* + * BIRD -- IP Addresses et Cetera for IPv4 + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_IPV4_H_ +#define _BIRD_IPV4_H_ + +#include + +typedef struct ipv4_addr { + u32 addr; +} ip_addr; + +#define ipa_equal(x,y) ((x).addr == (y).addr) + +#endif diff --git a/nest/ipv6.h b/nest/ipv6.h new file mode 100644 index 0000000..5d5e354 --- /dev/null +++ b/nest/ipv6.h @@ -0,0 +1,21 @@ +/* + * BIRD -- IP Addresses et Cetera for IPv6 + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_IPV4_H_ +#define _BIRD_IPV4_H_ + +#include +#include + +typedef struct ipv4_addr { + u32 addr[4]; +} ip_addr; + +#define ipa_equal(x,y) (!memcmp(&(x),&(y),sizeof(ip_addr))) + +#endif diff --git a/nest/main.c b/nest/main.c new file mode 100644 index 0000000..8f60f27 --- /dev/null +++ b/nest/main.c @@ -0,0 +1,23 @@ +/* + * BIRD Internet Routing Daemon + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include +#include + +#include + +int +main(void) +{ + ip_addr x,y; + + x=y; + if (ipa_equal(x,y)) return 1; + + return 0; +} diff --git a/nest/protocol.h b/nest/protocol.h new file mode 100644 index 0000000..adca114 --- /dev/null +++ b/nest/protocol.h @@ -0,0 +1,66 @@ +/* + * BIRD Internet Routing Daemon -- Protocols + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_PROTOCOL_H_ +#define _BIRD_PROTOCOL_H_ + +#include + +/* + * Routing Protocol + */ + +struct protocol { + char *name; + unsigned type; /* ??? List values ??? */ + unsigned debug; /* Default debugging flags */ + + void (*init)(struct protocol *); /* Boot time */ + void (*preconfig)(struct protocol *); /* Just before configuring */ + void (*postconfig)(struct protocol *); /* After configuring */ +}; + +void protos_init(void); +void protos_preconfig(void); +void protos_postconfig(void); + +/* + * Known protocols + */ + +extern struct protocol proto_static; + +/* + * Routing Protocol Instance + */ + +struct proto { + struct proto *next; + struct protocol *proto; /* Protocol */ + char *name; /* Name of this instance */ + unsigned debug; /* Debugging flags */ + pool *pool; /* Local objects */ + unsigned preference; /* Default route preference */ + + void (*if_notify)(struct proto *, struct iface *old, struct iface *new); + void (*rt_notify)(struct proto *, struct rte *old, struct rte *new); + void (*debug)(struct proto *); /* Debugging dump */ + void (*start)(struct proto *); /* Start the instance */ + void (*shutdown)(struct proto *, int time); /* Stop the instance */ + + /* Reconfigure function? */ + /* Interface patterns */ + /* Input/output filters */ + /* Connection to routing tables? */ + + /* Hic sunt protocol-specific data */ +}; + +void *proto_new(struct protocol *, unsigned size); + +#endif diff --git a/nest/route.h b/nest/route.h new file mode 100644 index 0000000..e968e12 --- /dev/null +++ b/nest/route.h @@ -0,0 +1,190 @@ +/* + * BIRD Internet Routing Daemon -- Routing Table + * + * (c) 1998 Martin Mares + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#ifndef _BIRD_ROUTE_H_ +#define _BIRD_ROUTE_H_ + +#include + +/* + * Generic data structure for storing network prefixes. Also used + * for the master routing table. Currently implemented as a radix + * trie. + * + * Available operations: + * - insertion of new entry + * - deletion of entry + * - searching of entry by network prefix + * - searching of entry by IP address (longest match) + */ + +struct fib_node { + ip_addr prefix; /* In host order */ + byte pxlen; + byte flags; /* ??? define them ??? */ + byte pad0, pad1; /* ??? use ??? */ + struct fib_node *left, *right, *up; /* Radix Trie links */ +}; + +struct fib { + slab fib_slab; /* Slab holding all fib nodes */ + struct fib_node root; + void (*init)(struct fib_node *); /* Constructor */ +}; + +void fib_init(struct fib *, pool *, unsigned node_size, void (*init)(struct fib_node *)); +void *fib_find(struct fib *, ip_addr *, int); /* Find or return NULL if doesn't exist */ +void *fib_find_ip(struct fib *, ip_addr *); /* Longest match (always exists) */ +void *fib_get(struct fib *, ip_addr *, int); /* Find or create new if nonexistent */ +void fib_delete(struct fib *); + +/* + * Master Routing Table. Generally speaking, it's a FIB with each entry + * pointing to a list of route entries representing routes to given network. + * Each of the RTE's contains variable data (the preference and protocol-dependent + * metrics) and a pointer to route attribute block common for many routes). + */ + +typedef struct network { + struct fib_node n; + struct rte *routes; /* Available routes for this network */ + struct network *next; /* Next in Recalc Chain */ +} net; + +typedef struct rte { + struct rte *next; + struct rtattr *attrs; + byte flags; /* Flags (REF_...) */ + byte rfu; + word pref; /* Route preference */ + union { /* Protocol-dependent data (metrics etc.) */ +#ifdef CONFIG_STATIC + struct { + } stat; +#endif +#ifdef CONFIG_RIP + struct { + byte metric; /* RIP metric */ + } rip; +#endif +#ifdef CONFIG_OSPF + struct { + u32 metric1, metric2; /* OSPF Type 1 and Type 2 metrics */ + } ospf; +#endif +#ifdef CONFIG_BGP + struct { + } bgp; +#endif + } u; +} rte; + +#define REF_CHOSEN 1 /* Currently chosen route */ + +typedef struct rte rte; + +/* + * 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. + */ + +struct rtattr { + struct rtattr *next, *prev; /* Hash chain */ + struct rtattr *garbage; /* Garbage collector chain */ + struct proto *proto; /* Protocol instance */ + unsigned uc; /* Use count */ + byte source; /* Route source (RTS_...) */ + byte scope; /* Route scope (SCOPE_...) */ + byte cast; /* Casting type (RTC_...) */ + byte dest; /* Route destination type (RTD_...) */ + byte tos; /* TOS of this route */ + byte flags; /* Route flags (RTF_...) */ + word source_as; /* Source AS of this route (0=local) */ + ip_addr gw; /* Next hop */ + struct iface *iface; /* Outgoing interface */ + struct ea_list *attrs; /* Extended Attribute chain */ +} 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_RIP_EXT 7 /* RIP external route */ +#define RTS_OSPF 8 /* OSPF route */ +#define RTS_OSPF_EXT 9 /* OSPF external route */ +#define RTS_OSPF_IA 10 /* OSPF inter-area route */ +#define RTS_OSPF_BOUNDARY 11 /* OSPF route to boundary router */ +#define RTS_BGP 12 /* BGP route */ + +#define SCOPE_HOST 0 /* Address scope */ +#define SCOPE_LINK 0x10 +#define SCOPE_SITE 0x80 +#define SCOPE_UNIVERSE 0xff + +#define RTC_UNICAST 0 +#define RTC_BROADCAST 1 +#define RTC_MULTICAST 2 +#define RTC_ANYCAST 3 /* IPv6 Anycast */ + +#define RTD_ROUTER 0 /* Next hop is neighbor router */ +#define RTD_DEVICE 1 /* Points to device */ +#define RTD_BLACKHOLE 2 /* Silently drop packets */ +#define RTD_UNREACHABLE 3 /* Reject as unreachable */ +#define RTD_PROHIBIT 4 /* Administratively prohibited */ + +/* + * Extended Route Attributes + */ + +typedef struct eattr { + byte protocol; /* Protocol ID (EAP_...) */ + byte flags; /* Attribute flags (EAF_...) */ + byte id; /* Protocol-dependent ID */ + union { + u32 data; + struct adata *ptr; /* Attribute data elsewhere */ + } u; +} eattr; + +#define EAP_GENERIC 0 /* Generic attributes */ +#define EAP_BGP 1 /* BGP attributes */ + +#define EAF_OPTIONAL 0x80 /* Refer to BGP specs for full meaning */ +#define EAF_TRANSITIVE 0x40 +#define EAF_PARTIAL 0x20 +#define EAF_EXTENDED_LENGTH 0x10 /* Not used by us, internal to BGP */ +#define EAF_LONGWORD 0x01 /* Embedded value [Not a BGP flag!] */ + +struct adata { + unsigned int length; + byte data[0]; +}; + +typedef struct ea_list { + struct ea_list *next; /* In case we have an override list */ + byte sorted; /* `Really sorted' flag */ + byte rfu; + word nattrs; /* Number of attributes */ + eattr attrs[0]; /* Attribute definitions themselves */ +} ea_list; + +eattr *ea_find(ea_list *, unsigned protocol, unsigned id); + +#define EA_LIST_NEW(p, alloc, n) do { \ + unsigned cnt = n; \ + p = alloc(sizeof(ea_list) + cnt*sizeof(eattr)); \ + memset(p, sizeof(ea_list)); \ + p->nattrs = cnt; \ +} while(0) + +#endif -- cgit v1.2.3