Revision 18c8241a

View differences:

Makefile
2 2
# (c) 1998 Martin Mares <mj@ucw.cz>
3 3

  
4 4
TOPDIR=$(shell pwd)
5
CPPFLAGS=-I$(TOPDIR)
6
CFLAGS=-O2 -Wall -W -Wstrict-prototypes -Wno-unused -Wno-parentheses $(CPPFLAGS)
5
CPPFLAGS=-I$(TOPDIR)/sysdep/linux -I$(TOPDIR)
6
OPT=-O2
7
DEBUG=-g#gdb
8
CFLAGS=$(OPT) $(DEBUG) -Wall -W -Wstrict-prototypes -Wno-unused -Wno-parentheses
7 9

  
8 10
PROTOCOLS=
9
DIRS=sysdep/linux nest $(PROTOCOLS) lib
11
DIRS=nest $(PROTOCOLS) lib sysdep/linux sysdep/unix
10 12
ARCHS=$(join $(addsuffix /,$(DIRS)),$(subst /,_,$(addsuffix .a,$(DIRS))))
11 13

  
12 14
export
......
27 29
	set -e ; for a in $(DIRS) ; do $(MAKE) -C $$a dep ; done
28 30

  
29 31
clean:
30
	rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend`
32
	rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend -or -name .#*`
31 33
	rm -f bird .dep
TODO
1 1
Core
2 2
~~~~
3
- route validation
4 3
- fake multipath?
5 4
- config file: symbolic constants?
6 5
- counters (according to SNMP MIB?)
7 6
- generation of subnet mask ICMP's for v6?
8
- debugging dumps and protocol tracing!
9 7
- unaligned accesses?
8
- neighbor cache: local broadcast address?
9
- ipv4: recognize site scope addresses?
10
- ifdef out some debugging code?
11
- better memory allocators
12
- precedence of all packets (incl. TCP)
13
- default preferences of protocols: prefer BGP over OSPF/RIP external routes?
14
- all internal tables are in host order
10 15

  
16
- filter: logging of dropped routes (?)
17
- limitation of memory consumption: per-process and total (?)
18
- alloca
19
- adding of route: clear all bits not covered by masklen
20
- switch: generate default route only if at least one BGP connection exists
11 21

  
12
RIP
13
~~~
14
- RIP: export-only and import-only mode?
15
- drop RIPv1 (Historic protocol)?
16

  
17
OSPF
18
~~~~
19

  
20
Almquist & Kastenholz                                         [Page 111]
21
RFC 1716          Towards Requirements for IP Routers      November 1994
22
- route recalculation timing + flap dampening
22 23

  
24
- reconfiguration without restart of all protocols?
25
- change of interface address: ??? (down and up?)
26
- "generate default route" switch for all IGP's
23 27

  
24
7.2.2.2  Specific Issues
28
- running protocol on an interface:
29
	- interface is not required to exist
30
	- can specify a wildcard pattern or an interface list
25 31

  
26
         Virtual Links
32
- timers - one-shot and periodic, resolution 1 sec, randomized
33
- re-configuration: restart of routing protocols (shutdown mode)
34
- route: originating AS
27 35

  
28
              There is a minor error in the specification that can cause
29
              routing loops when all of the following conditions are
30
              simultaneously true:
36
- Check incoming packets and log errors!!
31 37

  
32
              (1)  A virtual link is configured through a transit area,
33 38

  
34
              (2)  Two separate paths exist, each having the same
35
                   endpoints, but one utilizing only non-virtual
36
                   backbone links, and the other using links in the
37
                   transit area, and
39
RIP
40
~~~
41
	- RIP: export-only and import-only mode?
42
	- drop RIPv1 (Historic protocol)?
43
	- Route Tag
44
	- limit routing table xfer (frequency, only to neighbors)
45
	- multicast on/off
46
	- remember routes for all neighbors?
38 47

  
39
              (3)  The latter path is part of the (underlying physical
40
                   representation of the) configured virtual link,
41
                   routing loops may occur.
48
OSPF
49
~~~~
50
	- Dijkstra: use Fibonacci heaps?
51
	- point-to-point interface with address: advertise as stub network
52
	- static routes: stub networks?
53
	- modes: PtP, PtP-unnumbered, Broadcast, NBMA, point-to-multipoint
54
	- importing of device routes for networks where we don't run OSPF
55
	- tie breaking for equal type 2 ext metrics by using internal (type 1) metric
56
	- SPF tree recalc timing (per-area timers?)
57
	- aggregation: specify network list for each area
58
	- stub area: either no external routes or only default route
59
	- automatic generation of external route tags (RFC1403)
42 60

  
43
              To prevent this, an implementation of OSPF SHOULD invoke
44
              the calculation in Section 16.3 of [ROUTE:1] whenever any
45
              part of the path to the destination is a virtual link (the
46
              specification only says this is necessary when the first
47
              hop is a virtual link).
48 61

  
49 62
BGP
50 63
~~~
51
- BGP:
52 64
	- in, local, out RIB
53 65
	- maxsize=4096
54 66
	- BGP identifier aka router id
55
	- removal of loops
67
	- detection of loops
56 68
	- aggregation, ATOMIC_AGGREGATE
57 69
	- communities
58 70
	- confederations
......
71 83
	- expected neighbor AS
72 84
	- hold time
73 85
	- idle timer after error: initial value, exponential growth, maximum value
74

  
75
- address testing macros (ALL_ZEROS)
76
- all internal tables are in network order (?)
77
- logging of errors and debug dumps
78
- filter: logging of dropped routes (?)
79
- limitation of memory consumption: per-process and total
80
- alloca
81
- precedence of all packets (incl. TCP)
82
- adding of route: clear all bits not covered by masklen
83
- switch: generate default route only if at least one BGP connection exists
84

  
85
- route update: new, change, remove
86
- route recalculation timing
87

  
88
- CONFIG_TOS
89
- CONFIG_MULTIPATH
90

  
91
- reconfiguration without restart of all protocols?
92
- change of interface address: ??? (down and up?)
93
- "generate default route" switch for all IGP's
94

  
95
- RIPv2:
96
	- Route Tag
97
	- limit routing table xfer (frequency, only to neighbors)
98
	- multicast on/off
99
	- remember routes for all neighbors?
100

  
101
- BGP:
102 86
	- import of IGP routes (use external route tags from OSPF)
103

  
104
- Interface:
105
	- RIP metric
106
	- multicast capability flag
107
	- MTU
108
	- OSPF metrics (per-TOS)
109

  
110
- running protocol on an interface:
111
	- interface is not required to exist
112
	- can specify a wildcard pattern or an interface list
113

  
114
- preferences:
115
	- directly connected
116
	- static
117
	- OSPF internal, OSPF ext type 1 (comparable metrics), OSPF inter-area
118
	- RIP
119
	- BGP
120
	- OSPF ext type 2
121
	- sink
122

  
123
- lib:
124
	- MD5
125

  
126
- OSPF:
127
	- Dijkstra: use Fibonacci heaps?
128
	- point-to-point interface with address: advertise as stub network
129
	- static routes: stub networks?
130
	- modes: PtP, PtP-unnumbered, Broadcast, NBMA, point-to-multipoint
131
	- importing of device routes for networks where we don't run OSPF
132
	- tie breaking for equal type 2 ext metrics by using internal (type 1) metric
133
	- SPF tree recalc timing (per-area timers?)
134
	- aggregation: specify network list for each area
135
	- stub area: either no external routes or only default route
136
	- automatic generation of external route tags (RFC1403) -- what about
137
	  using the same rule for RIPv2? [shared code?]
138

  
139
- timers - one-shot and periodic, resolution 1 sec, randomized
140
- re-configuration: restart of routing protocols (shutdown mode)
141
- route: originating AS
142

  
143
- Check incoming packets and log errors!!
lib/Makefile
1
OBJS=lists.o
1
OBJS=lists.o bitops.o resource.o xmalloc.o mempool.o slab.o md5.o
2

  
3
ifdef IPV6
4
OBJS += ipv6.o
5
else
6
OBJS += ipv4.o
7
endif
2 8

  
3 9
include $(TOPDIR)/Rules
lib/birdlib.h
13 13

  
14 14
#define OFFSETOF(s, i) ((unsigned int)&((s *)0)->i)
15 15
#define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i)))
16
#define ALIGN(s, a) (((s)+a-1)&~(a-1))
17

  
18
/* Functions which don't return */
19

  
20
#define NORET __attribute__((noreturn))
16 21

  
17 22
/* Logging and dying */
18 23

  
19 24
void log(char *msg, ...);
20
void die(char *msg, ...);
25
void die(char *msg, ...) NORET;
21 26

  
22 27
#define L_DEBUG "\001"			/* Debugging messages */
23 28
#define L_INFO "\002"			/* Informational messages */
24 29
#define L_WARN "\003"			/* Warnings */
25 30
#define L_ERR "\004"			/* Errors */
26 31
#define L_AUTH "\005"			/* Authorization failed etc. */
32
#define L_FATAL "\006"			/* Fatal errors */
33

  
34
void log_init(char *);			/* Initialize logging to given file (NULL=stderr, ""=syslog) */
35
void log_init_debug(char *);		/* Initialize debug dump to given file (NULL=stderr, ""=off) */
36

  
37
void debug(char *msg, ...);		/* Printf to debug output */
27 38

  
28 39
/* Debugging */
29 40

  
lib/bitops.c
1
/*
2
 *	BIRD Library -- Generic Bit Operations
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
#include "nest/bird.h"
10
#include "bitops.h"
11

  
12
u32
13
u32_mkmask(unsigned n)
14
{
15
  return n ? ~((1 << (32 - n)) - 1) : 0;
16
}
17

  
18
int
19
u32_masklen(u32 x)
20
{
21
  int l = 0;
22
  u32 n = ~x;
23

  
24
  if (n & (n+1)) return -1;
25
  if (x & 0x0000ffff) { x &= 0x0000ffff; l += 16; }
26
  if (x & 0x00ff00ff) { x &= 0x00ff00ff; l += 8; }
27
  if (x & 0x0f0f0f0f) { x &= 0x0f0f0f0f; l += 4; }
28
  if (x & 0x33333333) { x &= 0x33333333; l += 2; }
29
  if (x & 0x55555555) l++;
30
  if (x & 0xaaaaaaaa) l++;
31
  return l;
32
}
lib/bitops.h
1
/*
2
 *	BIRD Library -- Generic Bit Operations
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
/*
10
 *	Bit mask operations:
11
 *
12
 *	u32_mkmask	Make bit mask consisting of <n> consecutive ones
13
 *			from the left and the rest filled with zeroes.
14
 *			E.g., u32_mkmask(5) = 0xf8000000.
15
 *	u32_masklen	Inverse operation to u32_mkmask, -1 if not a bitmask.
16
 */
17

  
18
u32 u32_mkmask(unsigned);
19
int u32_masklen(u32);
lib/ip.h
15 15
#include "ipv6.h"
16 16
#endif
17 17

  
18
/*
19
 *	ip_classify() returns either a negative number for invalid addresses
20
 *	or scope OR'ed together with address type.
21
 */
22

  
23
#define IADDR_INVALID		-1
24
#define IADDR_SCOPE_MASK       	0xfff
25
#define IADDR_HOST		0x1000
26
#define IADDR_BROADCAST		0x2000
27
#define IADDR_MULTICAST		0x4000
28

  
29
/*
30
 *	Address scope
31
 */
32

  
33
#define SCOPE_HOST 0
34
#define SCOPE_LINK 1
35
#define SCOPE_SITE 2
36
#define SCOPE_UNIVERSE 3
37

  
18 38
#endif
lib/ipv4.c
1
/*
2
 *	BIRD Library -- IPv4 Address Manipulation Functions
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
#include "nest/bird.h"
10
#include "lib/ip.h"
11

  
12
int
13
ipv4_classify(u32 a)
14
{
15
  u32 b = a >> 24U;
16

  
17
  if (b && b <= 0xdf)
18
    {
19
      if (b == 0x7f)
20
	return IADDR_HOST | SCOPE_HOST;
21
      else
22
	return IADDR_HOST | SCOPE_UNIVERSE;
23
    }
24
  if (b >= 0xe0 && b <= 0xef)
25
    return IADDR_MULTICAST | SCOPE_UNIVERSE;
26
  if (a == 0xffffffff)
27
    return IADDR_BROADCAST | SCOPE_LINK;
28
  return IADDR_INVALID;
29
}
lib/ipv4.h
11 11

  
12 12
#include <netinet/in.h>
13 13

  
14
#include "lib/bitops.h"
15

  
16
#ifdef DEBUG
17

  
18
/*
19
 *	Use the structural representation when you want to make sure
20
 *	nobody unauthorized attempts to handle ip_addr as number.
21
 */
22

  
14 23
typedef struct ipv4_addr {
15 24
  u32 addr;
16 25
} ip_addr;
......
18 27
#define _I(x) (x).addr
19 28
#define _MI(x) ((struct ip_addr) { x })
20 29

  
30
#else
31

  
32
typedef u32 ip_addr;
33

  
34
#define _I(x) (x)
35
#define _MI(x) (x)
36

  
37
#endif
38

  
21 39
#define IPA_NONE (_MI(0))
22 40

  
23 41
#define ipa_equal(x,y) (_I(x) == _I(y))
42
#define ipa_nonzero(x) _I(x)
24 43
#define ipa_and(x,y) _MI(_I(x) & _I(y))
25 44
#define ipa_or(x,y) _MI(_I(x) | _I(y))
26 45
#define ipa_not(x) _MI(~_I(x))
27
#define ipa_mkmask(x) _MI(ipv4_mkmask(x))
28
#define ipa_mklen(x) ipv4_mklen(_I(x))
46
#define ipa_mkmask(x) _MI(u32_mkmask(x))
47
#define ipa_mklen(x) u32_masklen(_I(x))
48
#define ipa_hash(x) ipv4_hash(_I(x))
49
#define ipa_hton(x) x = _MI(htonl(_I(x)))
50
#define ipa_ntoh(x) x = _MI(ntohl(_I(x)))
51
#define ipa_classify(x) ipv4_classify(_I(x))
29 52

  
30 53
unsigned ipv4_mklen(u32);
31 54
u32 ipv4_mkmask(unsigned);
55
int ipv4_classify(u32);
32 56

  
33
/* ??? htonl and ntohl ??? */
57
/* FIXME: Is this hash function uniformly distributed over standard routing tables? */
58
static inline unsigned ipv4_hash(u32 a)
59
{
60
  return a ^ (a >> 16) ^ (a >> 24);
61
}
34 62

  
35 63
#endif
lib/ipv6.c
1
/*
2
 *	BIRD Library -- IPv6 Address Manipulation Functions
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
#include "nest/bird.h"
10
#include "lib/ip.h"
11

  
12
#error "Ought to implement these."
lib/ipv6.h
25 25
#define IPA_NONE _MI(0,0,0,0)
26 26

  
27 27
#define ipa_equal(x,y) (!memcmp(&(x),&(y),sizeof(ip_addr)))
28
#define ipa_nonzero(x) (_I0(a) || _I1(a) || _I2(a) || _I3(a))
28 29
#define ipa_and(a,b) _MI(_I0(a) & _I0(b), \
29 30
			 _I1(a) & _I1(b), \
30 31
			 _I2(a) & _I2(b), \
......
34 35
			_I2(a) | _I2(b), \
35 36
			_I3(a) | _I3(b))
36 37
#define ipa_not(a) _MI(~_I0(a),~_I1(a),~_I2(a),~_I3(a))
37

  
38 38
#define ipa_mkmask(x) ipv6_mkmask(x)
39
#define ipa_mklen(x) ipv6_mklen(x)
39
#define ipa_mklen(x) ipv6_mklen(&(x))
40
#define ipa_hash(x) ipv6_hash(&(x))
41
#define ipa_hton(x) ipv6_hton(&(x))
42
#define ipa_ntoh(x) ipv6_ntoh(&(x))
43
#define ipa_classify(x) ipv6_classify(&(x))
40 44

  
41 45
ip_addr ipv6_mkmask(unsigned);
42
unsigned ipv6_mklen(ip_addr);
46
unsigned ipv6_mklen(ip_addr *);
47
int ipv6_classify(ip_addr *);
48
void ipv6_hton(ip_addr *);
49
void ipv6_ntoh(ip_addr *);
50

  
51
/* FIXME: Is this hash function uniformly distributed over standard routing tables? */
52
static inline unsigned ipv6_hash(ip_addr *a)
53
{
54
  u32 x = _I0(*a) ^ _I1(*a) ^ _I2(*a) ^ _I3(*a);
55
  return x ^ (x >> 16) ^ (x >> 8);
56
}
43 57

  
44 58
#endif
lib/lists.c
16 16
{
17 17
  node *z = l->tail;
18 18

  
19
  n->next = (node *) &l->tail;
19
  n->next = (node *) &l->null;
20 20
  n->prev = z;
21 21
  z->next = n;
22 22
  l->tail = n;
lib/lists.h
33 33

  
34 34
#ifndef _BIRD_LISTS_C_
35 35
#define LIST_INLINE extern inline
36
#include <lib/lists.c>
36
#include "lib/lists.c"
37 37
#undef LIST_INLINE
38 38
#else
39 39
#define LIST_INLINE
lib/md5.c
1
/*
2
 * This code implements the MD5 message-digest algorithm.
3
 * The algorithm is due to Ron Rivest.  This code was
4
 * written by Colin Plumb in 1993, no copyright is claimed.
5
 * This code is in the public domain; do with it what you wish.
6
 *
7
 * Equivalent code is available from RSA Data Security, Inc.
8
 * This code has been tested against that, and is equivalent,
9
 * except that you don't need to include two pages of legalese
10
 * with every copy.
11
 *
12
 * To compute the message digest of a chunk of bytes, declare an
13
 * MD5Context structure, pass it to MD5Init, call MD5Update as
14
 * needed on buffers full of bytes, and then call MD5Final, which
15
 * will fill a supplied 16-byte array with the digest.
16
 */
17

  
18
/*
19
 * Adapted for BIRD by Martin Mares <mj@atrey.karlin.mff.cuni.cz>
20
 */
21

  
22
#include <string.h>		/* for memcpy() */
23
#include "nest/bird.h"
24
#include "md5.h"
25

  
26
#ifdef CPU_LITTLE_ENDIAN
27
#define byteReverse(buf, len)	/* Nothing */
28
#else
29
void byteReverse(unsigned char *buf, unsigned longs);
30

  
31
/*
32
 * Note: this code is harmless on little-endian machines.
33
 */
34
void byteReverse(unsigned char *buf, unsigned longs)
35
{
36
    u32 t;
37
    do {
38
	t = (u32) ((unsigned) buf[3] << 8 | buf[2]) << 16 |
39
	    ((unsigned) buf[1] << 8 | buf[0]);
40
	*(u32 *) buf = t;
41
	buf += 4;
42
    } while (--longs);
43
}
44
#endif
45

  
46
/*
47
 * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
48
 * initialization constants.
49
 */
50
void MD5Init(struct MD5Context *ctx)
51
{
52
    ctx->buf[0] = 0x67452301;
53
    ctx->buf[1] = 0xefcdab89;
54
    ctx->buf[2] = 0x98badcfe;
55
    ctx->buf[3] = 0x10325476;
56

  
57
    ctx->bits[0] = 0;
58
    ctx->bits[1] = 0;
59
}
60

  
61
/*
62
 * Update context to reflect the concatenation of another buffer full
63
 * of bytes.
64
 */
65
void MD5Update(struct MD5Context *ctx, unsigned char const *buf, unsigned len)
66
{
67
    u32 t;
68

  
69
    /* Update bitcount */
70

  
71
    t = ctx->bits[0];
72
    if ((ctx->bits[0] = t + ((u32) len << 3)) < t)
73
	ctx->bits[1]++;		/* Carry from low to high */
74
    ctx->bits[1] += len >> 29;
75

  
76
    t = (t >> 3) & 0x3f;	/* Bytes already in shsInfo->data */
77

  
78
    /* Handle any leading odd-sized chunks */
79

  
80
    if (t) {
81
	unsigned char *p = (unsigned char *) ctx->in + t;
82

  
83
	t = 64 - t;
84
	if (len < t) {
85
	    memcpy(p, buf, len);
86
	    return;
87
	}
88
	memcpy(p, buf, t);
89
	byteReverse(ctx->in, 16);
90
	MD5Transform(ctx->buf, (u32 *) ctx->in);
91
	buf += t;
92
	len -= t;
93
    }
94
    /* Process data in 64-byte chunks */
95

  
96
    while (len >= 64) {
97
	memcpy(ctx->in, buf, 64);
98
	byteReverse(ctx->in, 16);
99
	MD5Transform(ctx->buf, (u32 *) ctx->in);
100
	buf += 64;
101
	len -= 64;
102
    }
103

  
104
    /* Handle any remaining bytes of data. */
105

  
106
    memcpy(ctx->in, buf, len);
107
}
108

  
109
/*
110
 * Final wrapup - pad to 64-byte boundary with the bit pattern 
111
 * 1 0* (64-bit count of bits processed, MSB-first)
112
 */
113
void MD5Final(unsigned char digest[16], struct MD5Context *ctx)
114
{
115
    unsigned count;
116
    unsigned char *p;
117

  
118
    /* Compute number of bytes mod 64 */
119
    count = (ctx->bits[0] >> 3) & 0x3F;
120

  
121
    /* Set the first char of padding to 0x80.  This is safe since there is
122
       always at least one byte free */
123
    p = ctx->in + count;
124
    *p++ = 0x80;
125

  
126
    /* Bytes of padding needed to make 64 bytes */
127
    count = 64 - 1 - count;
128

  
129
    /* Pad out to 56 mod 64 */
130
    if (count < 8) {
131
	/* Two lots of padding:  Pad the first block to 64 bytes */
132
	memset(p, 0, count);
133
	byteReverse(ctx->in, 16);
134
	MD5Transform(ctx->buf, (u32 *) ctx->in);
135

  
136
	/* Now fill the next block with 56 bytes */
137
	memset(ctx->in, 0, 56);
138
    } else {
139
	/* Pad block to 56 bytes */
140
	memset(p, 0, count - 8);
141
    }
142
    byteReverse(ctx->in, 14);
143

  
144
    /* Append length in bits and transform */
145
    ((u32 *) ctx->in)[14] = ctx->bits[0];
146
    ((u32 *) ctx->in)[15] = ctx->bits[1];
147

  
148
    MD5Transform(ctx->buf, (u32 *) ctx->in);
149
    byteReverse((unsigned char *) ctx->buf, 4);
150
    memcpy(digest, ctx->buf, 16);
151
    memset((char *) ctx, 0, sizeof(ctx));	/* In case it's sensitive */
152
}
153

  
154
/* The four core functions - F1 is optimized somewhat */
155

  
156
/* #define F1(x, y, z) (x & y | ~x & z) */
157
#define F1(x, y, z) (z ^ (x & (y ^ z)))
158
#define F2(x, y, z) F1(z, x, y)
159
#define F3(x, y, z) (x ^ y ^ z)
160
#define F4(x, y, z) (y ^ (x | ~z))
161

  
162
/* This is the central step in the MD5 algorithm. */
163
#define MD5STEP(f, w, x, y, z, data, s) \
164
	( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
165

  
166
/*
167
 * The core of the MD5 algorithm, this alters an existing MD5 hash to
168
 * reflect the addition of 16 longwords of new data.  MD5Update blocks
169
 * the data and converts bytes into longwords for this routine.
170
 */
171
void MD5Transform(u32 buf[4], u32 const in[16])
172
{
173
    register u32 a, b, c, d;
174

  
175
    a = buf[0];
176
    b = buf[1];
177
    c = buf[2];
178
    d = buf[3];
179

  
180
    MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
181
    MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
182
    MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
183
    MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
184
    MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
185
    MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
186
    MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
187
    MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
188
    MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
189
    MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
190
    MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
191
    MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
192
    MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
193
    MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
194
    MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
195
    MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
196

  
197
    MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
198
    MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
199
    MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
200
    MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
201
    MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
202
    MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
203
    MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
204
    MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
205
    MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
206
    MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
207
    MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
208
    MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
209
    MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
210
    MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
211
    MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
212
    MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
213

  
214
    MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
215
    MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
216
    MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
217
    MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
218
    MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
219
    MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
220
    MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
221
    MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
222
    MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
223
    MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
224
    MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
225
    MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
226
    MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
227
    MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
228
    MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
229
    MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
230

  
231
    MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
232
    MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
233
    MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
234
    MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
235
    MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
236
    MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
237
    MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
238
    MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
239
    MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
240
    MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
241
    MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
242
    MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
243
    MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
244
    MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
245
    MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
246
    MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
247

  
248
    buf[0] += a;
249
    buf[1] += b;
250
    buf[2] += c;
251
    buf[3] += d;
252
}
lib/md5.h
1
#ifndef MD5_H
2
#define MD5_H
3

  
4
struct MD5Context {
5
	u32 buf[4];
6
	u32 bits[2];
7
	unsigned char in[64];
8
};
9

  
10
void MD5Init(struct MD5Context *context);
11
void MD5Update(struct MD5Context *context, unsigned char const *buf,
12
	       unsigned len);
13
void MD5Final(unsigned char digest[16], struct MD5Context *context);
14
void MD5Transform(u32 buf[4], u32 const in[16]);
15

  
16
#endif /* !MD5_H */
lib/mempool.c
1
/*
2
 *	BIRD Resource Manager -- Memory Pools
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
#include <stdlib.h>
10
#include <string.h>
11

  
12
#include "nest/bird.h"
13
#include "lib/resource.h"
14

  
15
struct mp_chunk {
16
  struct mp_chunk *next;
17
  byte data[0];
18
};
19

  
20
struct mempool {
21
  resource r;
22
  byte *ptr, *end;
23
  struct mp_chunk *first, **plast;
24
  unsigned chunk_size, threshold, total;
25
};
26

  
27
void mp_free(resource *);
28
void mp_dump(resource *);
29

  
30
struct resclass mp_class = {
31
  "MemPool",
32
  sizeof(struct mempool),
33
  mp_free,
34
  mp_dump
35
};
36

  
37
mempool
38
*mp_new(pool *p, unsigned blk)
39
{
40
  mempool *m = ralloc(p, &mp_class);
41
  m->ptr = m->end = NULL;
42
  m->first = NULL;
43
  m->plast = &m->first;
44
  m->chunk_size = blk;
45
  m->threshold = 3*blk/4;
46
  m->total = 0;
47
  return m;
48
}
49

  
50
void *
51
mp_alloc(mempool *m, unsigned size)
52
{
53
  byte *a = (byte *) ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
54
  byte *e = a + size;
55

  
56
  if (e <= m->end)
57
    {
58
      m->ptr = e;
59
      return a;
60
    }
61
  else
62
    {
63
      struct mp_chunk *c;
64
      if (size >= m->threshold)
65
	{
66
	  c = xmalloc(sizeof(struct mp_chunk) + size);
67
	  m->total += size;
68
	}
69
      else
70
	{
71
	  c = xmalloc(sizeof(struct mp_chunk) + m->chunk_size);
72
	  m->ptr = c->data + size;
73
	  m->end = c->data + m->chunk_size;
74
	  m->total += m->chunk_size;
75
	}
76
      *m->plast = c;
77
      m->plast = &c->next;
78
      c->next = NULL;
79
      return c->data;
80
    }
81
}
82

  
83
void *
84
mp_allocu(mempool *m, unsigned size)
85
{
86
  byte *a = m->ptr;
87
  byte *e = a + size;
88

  
89
  if (e <= m->end)
90
    {
91
      m->ptr = e;
92
      return a;
93
    }
94
  return mp_alloc(m, size);
95
}
96

  
97
void *
98
mp_allocz(mempool *m, unsigned size)
99
{
100
  void *z = mp_alloc(m, size);
101

  
102
  bzero(z, size);
103
  return z;
104
}
105

  
106
void
107
mp_free(resource *r)
108
{
109
  mempool *m = (mempool *) r;
110
  struct mp_chunk *c, *d;
111

  
112
  for(d=m->first; d; d = c)
113
    {
114
      c = d->next;
115
      xfree(d);
116
    }
117
}
118

  
119
void
120
mp_dump(resource *r)
121
{
122
  mempool *m = (mempool *) r;
123
  struct mp_chunk *c;
124
  int cnt;
125

  
126
  for(cnt=0, c=m->first; c; c=c->next, cnt++)
127
    ;
128
  debug("(chunk=%d threshold=%d count=%d total=%d)\n",
129
	m->chunk_size,
130
	m->threshold,
131
	cnt,
132
	m->total);
133
}
lib/resource.c
1
/*
2
 *	BIRD Resource Manager
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
#include <stdio.h>
10
#include <stdlib.h>
11

  
12
#include "nest/bird.h"
13
#include "lib/resource.h"
14

  
15
struct pool {
16
  resource r;
17
  list inside;
18
};
19

  
20
void pool_dump(resource *);
21
void pool_free(resource *);
22

  
23
static struct resclass pool_class = {
24
  "Pool",
25
  sizeof(pool),
26
  pool_free,
27
  pool_dump
28
};
29

  
30
pool root_pool;
31

  
32
static int indent;
33

  
34
pool *
35
rp_new(pool *p)
36
{
37
  pool *z = ralloc(p, &pool_class);
38
  init_list(&z->inside);
39
  return z;
40
}
41

  
42
void
43
pool_free(resource *P)
44
{
45
  pool *p = (pool *) P;
46
  resource *r, *rr;
47

  
48
  r = HEAD(p->inside);
49
  while (rr = (resource *) r->n.next)
50
    {
51
      r->class->free(r);
52
      xfree(r);
53
      r = rr;
54
    }
55
}
56

  
57
void
58
pool_dump(resource *P)
59
{
60
  pool *p = (pool *) P;
61
  resource *r;
62

  
63
  debug("\n");
64
  indent += 3;
65
  WALK_LIST(r, p->inside)
66
    rdump(r);
67
  indent -= 3;
68
}
69

  
70
void
71
rfree(void *res)
72
{
73
  resource *r = res;
74

  
75
  if (r)
76
    {
77
      if (r->n.next)
78
	rem_node(&r->n);
79
      r->class->free(r);
80
      xfree(r);
81
    }
82
}
83

  
84
void
85
rdump(void *res)
86
{
87
  char x[16];
88
  resource *r = res;
89

  
90
  sprintf(x, "%%%ds%%08x ", indent);
91
  debug(x, "", (int) r);
92
  if (r)
93
    {
94
      debug("%-6s", r->class->name);
95
      r->class->dump(r);
96
    }
97
  else
98
    debug("NULL\n");
99
}
100

  
101
void *
102
ralloc(pool *p, struct resclass *c)
103
{
104
  resource *r = xmalloc(c->size);
105

  
106
  r->class = c;
107
  add_tail(&p->inside, &r->n);
108
  return r;
109
}
110

  
111
void
112
resource_init(void)
113
{
114
  root_pool.r.class = &pool_class;
115
  init_list(&root_pool.inside);
116
}
117

  
118
/*
119
 *	Memory blocks.
120
 */
121

  
122
struct mblock {
123
  resource r;
124
  unsigned size;
125
  byte data[0];
126
};
127

  
128
void mbl_free(resource *r)
129
{
130
}
131

  
132
void mbl_debug(resource *r)
133
{
134
  struct mblock *m = (struct mblock *) r;
135

  
136
  debug("(size=%d)\n", m->size);
137
}
138

  
139
struct resclass mb_class = {
140
  "Memory",
141
  0,
142
  mbl_free,
143
  mbl_debug,
144
};
145

  
146
void *
147
mb_alloc(pool *p, unsigned size)
148
{
149
  struct mblock *b = xmalloc(sizeof(struct mblock) + size);
150

  
151
  b->r.class = &mb_class;
152
  add_tail(&p->inside, &b->r.n);
153
  b->size = size;
154
  return b->data;
155
}
156

  
157
void
158
mb_free(void *m)
159
{
160
  struct mblock *b = SKIP_BACK(struct mblock, data, m);
161
  rfree(b);
162
}
lib/resource.h
14 14
/* Resource */
15 15

  
16 16
typedef struct resource {
17
	node n;				/* Inside resource pool */
18
	struct resclass *class;		/* Resource class */
17
  node n;				/* Inside resource pool */
18
  struct resclass *class;		/* Resource class */
19 19
} resource;
20 20

  
21 21
/* Resource class */
22 22

  
23 23
struct resclass {
24
	char *name;			/* Resource class name */
25
	unsigned size;			/* Standard size of single resource */
26
	void (*free)(resource *);	/* Freeing function */
27
	void (*dump)(resource *);	/* Dump to debug output */
24
  char *name;				/* Resource class name */
25
  unsigned size;			/* Standard size of single resource */
26
  void (*free)(resource *);		/* Freeing function */
27
  void (*dump)(resource *);		/* Dump to debug output */
28 28
};
29 29

  
30 30
/* Generic resource manipulation */
31 31

  
32 32
typedef struct pool pool;
33 33

  
34
void resource_init(void);
34 35
pool *rp_new(pool *);			/* Create new pool */
35
void rp_init(pool *);			/* Initialize static pool */
36
void rp_empty(pool *);			/* Free everything in the pool */
36
void rp_free(pool *);			/* Free everything in the pool */
37 37
void rfree(void *);			/* Free single resource */
38 38
void rdump(void *);			/* Dump to debug output */
39 39

  
40
void ralloc(pool *, struct resclass *);
40
void *ralloc(pool *, struct resclass *);
41

  
42
extern pool root_pool;
41 43

  
42 44
/* Normal memory blocks */
43 45

  
44 46
void *mb_alloc(pool *, unsigned size);
45
void *mb_free(void *);
47
void mb_free(void *);
46 48

  
47 49
/* Memory pools with linear allocation */
48 50

  
49 51
typedef struct mempool mempool;
50 52

  
51 53
mempool *mp_new(pool *, unsigned blk);
52
void mp_trim(pool *);				/* Free unused memory */
53 54
void *mp_alloc(mempool *, unsigned size);	/* Aligned */
54 55
void *mp_allocu(mempool *, unsigned size);	/* Unaligned */
55 56
void *mp_allocz(mempool *, unsigned size);	/* With clear */
lib/slab.c
1
/*
2
 *	BIRD Resource Manager -- SLABs
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
#include <stdlib.h>
10
#include <string.h>
11

  
12
#include "nest/bird.h"
13
#include "lib/resource.h"
14

  
15
/*
16
 *	These are only fake, soon to change...
17
 */
18

  
19
struct sl_obj {
20
  node n;
21
  byte data[0];
22
};
23

  
24
struct slab {
25
  resource r;
26
  unsigned size;
27
  list objs;
28
};
29

  
30
void slab_free(resource *r);
31
void slab_dump(resource *r);
32

  
33
struct resclass sl_class = {
34
  "Slab",
35
  sizeof(struct slab),
36
  slab_free,
37
  slab_dump
38
};
39

  
40
slab *
41
sl_new(pool *p, unsigned size)
42
{
43
  slab *s = ralloc(p, &sl_class);
44
  s->size = size;
45
  init_list(&s->objs);
46
  return s;
47
}
48

  
49
void *
50
sl_alloc(slab *s)
51
{
52
  struct sl_obj *o = xmalloc(sizeof(struct sl_obj) + s->size);
53

  
54
  add_tail(&s->objs, &o->n);
55
  return o->data;
56
}
57

  
58
void
59
sl_free(slab *s, void *oo)
60
{
61
  struct sl_obj *o = SKIP_BACK(struct sl_obj, data, oo);
62

  
63
  rem_node(&o->n);
64
  xfree(o);
65
}
66

  
67
void
68
slab_free(resource *r)
69
{
70
  slab *s = (slab *) r;
71
  struct sl_obj *o, *p;
72

  
73
  for(o = HEAD(s->objs); p = (struct sl_obj *) o->n.next; o = p)
74
    xfree(o);
75
}
76

  
77
void
78
slab_dump(resource *r)
79
{
80
  slab *s = (slab *) r;
81
  int cnt = 0;
82
  struct sl_obj *o;
83

  
84
  WALK_LIST(o, s->objs)
85
    cnt++;
86
  debug("(%d objects per %d bytes)\n", cnt, s->size);
87
}
lib/xmalloc.c
1
/*
2
 *	BIRD Library -- malloc() With Checking
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
#include <stdlib.h>
10

  
11
#include "nest/bird.h"
12
#include "lib/resource.h"
13

  
14
void *
15
xmalloc(unsigned size)
16
{
17
  void *p = malloc(size);
18
  if (p)
19
    return p;
20
  die("Unable to allocate %d bytes of memory", size);
21
}
sysdep/config.h
47 47
#define CONFIG_BGP
48 48
#define CONFIG_OSPF
49 49

  
50
/* Autodetected system features */
51

  
52
#define HAVE_SYSLOG
53

  
50 54
#endif

Also available in: Unified diff