Statistics
| Branch: | Revision:

iof-bird-daemon / nest / route.h @ 62aa008a

History | View | Annotate | Download (7.71 KB)

1
/*
2
 *        BIRD Internet Routing Daemon -- Routing Table
3
 *
4
 *        (c) 1998 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#ifndef _BIRD_ROUTE_H_
10
#define _BIRD_ROUTE_H_
11

    
12
#include "lib/resource.h"
13

    
14
/*
15
 *        Generic data structure for storing network prefixes. Also used
16
 *        for the master routing table. Currently implemented as a hash 
17
 *        table.
18
 *
19
 *        Available operations:
20
 *                - insertion of new entry
21
 *                - deletion of entry
22
 *                - searching for entry by network prefix
23
 */
24

    
25
struct fib_node {
26
  ip_addr prefix;                        /* In host order */
27
  byte pxlen;
28
  byte flags;                                /* ??? define them ??? */
29
  byte pad0, pad1;                        /* ??? use ??? */
30
  struct fib_node *next;                /* Next in hash chain */
31
};
32

    
33
struct fib {
34
  pool *fib_pool;                        /* Pool holding all our data */
35
  slab *fib_slab;                        /* Slab holding all fib nodes */
36
  struct fib_node **hash_table;                /* Node hash table */
37
  unsigned int hash_size;                /* Number of hash table entries (a power of two) */
38
  unsigned int hash_mask;                /* hash_size - 1 */
39
  unsigned int entries;                        /* Number of entries */
40
  unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */
41
  void (*init)(struct fib_node *);        /* Constructor */
42
};
43

    
44
void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *));
45
void *fib_find(struct fib *, ip_addr *, int);        /* Find or return NULL if doesn't exist */
46
void *fib_get(struct fib *, ip_addr *, int);         /* Find or create new if nonexistent */
47
void fib_delete(struct fib *, void *);        /* Remove fib entry */
48
void fib_free(struct fib *);                /* Destroy the fib */
49

    
50
#define FIB_WALK(fib, z, op) do {                                \
51
        struct fib_node *z, **ff = (fib)->hash_table;                \
52
        unsigned int count = (fib)->hash_size;                        \
53
        while (count--)                                                \
54
          for(z = *ff++; z; z=z->next)                                \
55
            {                                                        \
56
              op;                                                \
57
            }                                                        \
58
        } while (0)
59

    
60
/*
61
 *        Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen
62
 *        along with pointer to protocol-specific data.
63
 *
64
 *        The primary goal of this cache is to quickly validate all incoming
65
 *        packets if their have been sent by our neighbors and to notify
66
 *        protocols about lost neighbors when an interface goes down.
67
 */
68

    
69
typedef struct neighbor {
70
  ip_addr addr;                                /* Address of the neighbor */
71
  struct next *next;                        /* Next in hashed chain */
72
  struct next *sibling;                        /* Next in per-device chain */
73
  struct proto *proto;                        /* Protocol this belongs to */
74
  void *data;                                /* Protocol-specific data */
75
} neighbor;
76

    
77
neighbor *neigh_find(ip_addr *);        /* NULL if not a neighbor */
78

    
79
/*
80
 *        Master Routing Tables. Generally speaking, each of them is a list
81
 *        of FIB (one per TOS) with each entry pointing to a list of route entries
82
 *        representing routes to given network.
83
 *        Each of the RTE's contains variable data (the preference and protocol-dependent
84
 *        metrics) and a pointer to a route attribute block common for many routes).
85
 */
86

    
87
typedef struct rtable {
88
  struct rtable *sibling;                /* Our sibling for different TOS */
89
  byte tos;                                /* TOS for this table */
90
  struct fib fib;
91
  char *name;                                /* Name of this table */
92
  /* FIXME: Data for kernel synchronization */
93
} rtable;
94

    
95
typedef struct network {
96
  struct fib_node n;
97
  struct rte *routes;                        /* Available routes for this network */
98
  struct network *next;                        /* Next in Recalc Chain */
99
} net;
100

    
101
typedef struct rte {
102
  struct rte *next;
103
  struct rtattr *attrs;
104
  byte flags;                                /* Flags (REF_...) */
105
  byte pflags;                                /* Protocol-specific flags */
106
  word pref;                                /* Route preference */
107
  u32 lastmod;                                /* Last modified (time) */
108
  union {                                /* Protocol-dependent data (metrics etc.) */
109
#ifdef CONFIG_STATIC
110
    struct {
111
    } stat;
112
#endif
113
#ifdef CONFIG_RIP
114
    struct {
115
      byte metric;                        /* RIP metric */
116
      u16 tag;                                /* External route tag */
117
    } rip;
118
#endif
119
#ifdef CONFIG_OSPF
120
    struct {
121
      u32 metric1, metric2;                /* OSPF Type 1 and Type 2 metrics */
122
      u32 tag;                                /* External route tag */
123
    } ospf;
124
#endif
125
#ifdef CONFIG_BGP
126
    struct {
127
    } bgp;
128
#endif
129
  } u;
130
} rte;
131

    
132
#define REF_CHOSEN 1                        /* Currently chosen route */
133

    
134
/*
135
 *        Route Attributes
136
 *
137
 *        Beware: All standard BGP attributes must be represented here instead
138
 *        of making them local to the route. This is needed to ensure proper
139
 *        construction of BGP route attribute lists.
140
 */
141

    
142
struct rtattr {
143
  struct rtattr *next, *prev;                /* Hash chain */
144
  struct rtattr *garbage;                /* Garbage collector chain */
145
  struct proto *proto;                        /* Protocol instance */
146
  unsigned uc;                                /* Use count */
147
  byte source;                                /* Route source (RTS_...) */
148
  byte scope;                                /* Route scope (SCOPE_... -- see ip.h) */
149
  byte cast;                                /* Casting type (RTC_...) */
150
  byte dest;                                /* Route destination type (RTD_...) */
151
  byte tos;                                /* TOS of this route */
152
  byte flags;                                /* Route flags (RTF_...) */
153
  ip_addr gw;                                /* Next hop */
154
  ip_addr from;                                /* Advertising router */
155
  struct iface *iface;                        /* Outgoing interface */
156
  struct ea_list *attrs;                /* Extended Attribute chain */
157
  union {                                /* Protocol-specific data */
158
  } u;
159
} rta;
160

    
161
#define RTS_STATIC 1                        /* Normal static route */
162
#define RTS_INHERIT 2                        /* Route inherited from kernel */
163
#define RTS_DEVICE 3                        /* Device route */
164
#define RTS_STATIC_DEVICE 4                /* Static device route */
165
#define RTS_REDIRECT 5                        /* Learned via redirect */
166
#define RTS_RIP 6                        /* RIP route */
167
#define RTS_RIP_EXT 7                        /* RIP external route */
168
#define RTS_OSPF 8                        /* OSPF route */
169
#define RTS_OSPF_EXT 9                        /* OSPF external route */
170
#define RTS_OSPF_IA 10                        /* OSPF inter-area route */
171
#define RTS_OSPF_BOUNDARY 11                /* OSPF route to boundary router (???) */
172
#define RTS_BGP 12                        /* BGP route */
173

    
174
#define RTC_UNICAST 0
175
#define RTC_BROADCAST 1
176
#define RTC_MULTICAST 2
177
#define RTC_ANYCAST 3                        /* IPv6 Anycast */
178

    
179
#define RTD_ROUTER 0                        /* Next hop is neighbor router */
180
#define RTD_DEVICE 1                        /* Points to device */
181
#define RTD_BLACKHOLE 2                        /* Silently drop packets */
182
#define RTD_UNREACHABLE 3                /* Reject as unreachable */
183
#define RTD_PROHIBIT 4                        /* Administratively prohibited */
184

    
185
#define RTF_EXTERIOR 1                        /* Learned via exterior protocol */
186
#define RTF_TAGGED 2                        /* Tagged external route learned via IGP */
187

    
188
/*
189
 *        Extended Route Attributes
190
 */
191

    
192
typedef struct eattr {
193
  byte protocol;                        /* Protocol ID (EAP_...) */
194
  byte flags;                                /* Attribute flags (EAF_...) */
195
  byte id;                                /* Protocol-dependent ID */
196
  byte rfu;                                /* ??? */
197
  union {
198
    u32 data;
199
    struct adata *ptr;                        /* Attribute data elsewhere */
200
  } u;
201
} eattr;
202

    
203
#define EAP_GENERIC 0                        /* Generic attributes */
204
#define EAP_BGP 1                        /* BGP attributes */
205

    
206
#define EAF_OPTIONAL 0x80                /* Refer to BGP specs for full meaning */
207
#define EAF_TRANSITIVE 0x40
208
#define EAF_PARTIAL 0x20
209
#define EAF_EXTENDED_LENGTH 0x10        /* Not used by us, internal to BGP */
210
#define EAF_LONGWORD 0x01                /* Embedded value [Not a BGP flag!] */
211

    
212
struct adata {
213
  unsigned int length;
214
  byte data[0];
215
};
216

    
217
typedef struct ea_list {
218
  struct ea_list *next;                        /* In case we have an override list */
219
  byte sorted;                                /* `Really sorted' flag (???) */
220
  byte rfu;
221
  word nattrs;                                /* Number of attributes */
222
  eattr attrs[0];                        /* Attribute definitions themselves */
223
} ea_list;
224

    
225
eattr *ea_find(ea_list *, unsigned protocol, unsigned id);
226

    
227
#define EA_LIST_NEW(p, alloc, n) do {                                \
228
        unsigned cnt = n;                                               \
229
        p = alloc(sizeof(ea_list) + cnt*sizeof(eattr));                \
230
        memset(p, 0, sizeof(ea_list));                                \
231
        p->nattrs = cnt;                                        \
232
} while(0)
233

    
234
/*
235
 *        Default protocol preferences
236
 */
237

    
238
#define DEF_PREF_DIRECT                    240        /* Directly connected */
239
#define DEF_PREF_STATIC                200        /* Static route */
240
#define DEF_PREF_OSPF_INTERNAL        150        /* OSPF intra-area, inter-area and type 1 external routes */
241
#define DEF_PREF_RIP                120        /* RIP */
242
#define DEF_PREF_BGP                100        /* BGP */
243
#define DEF_PREF_OSPF_EXTERNAL        80        /* OSPF external routes */
244
#define DEF_PREF_RIP_EXTERNAL        70        /* RIP external routes */
245
#define DEF_PREF_SINK                10        /* Sink route */
246

    
247
#endif