diff options
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | TODO | 145 | ||||
| -rw-r--r-- | lib/Makefile | 8 | ||||
| -rw-r--r-- | lib/birdlib.h | 13 | ||||
| -rw-r--r-- | lib/bitops.c | 32 | ||||
| -rw-r--r-- | lib/bitops.h | 19 | ||||
| -rw-r--r-- | lib/ip.h | 20 | ||||
| -rw-r--r-- | lib/ipv4.c | 29 | ||||
| -rw-r--r-- | lib/ipv4.h | 34 | ||||
| -rw-r--r-- | lib/ipv6.c | 12 | ||||
| -rw-r--r-- | lib/ipv6.h | 20 | ||||
| -rw-r--r-- | lib/lists.c | 2 | ||||
| -rw-r--r-- | lib/lists.h | 2 | ||||
| -rw-r--r-- | lib/md5.c | 252 | ||||
| -rw-r--r-- | lib/md5.h | 16 | ||||
| -rw-r--r-- | lib/mempool.c | 133 | ||||
| -rw-r--r-- | lib/resource.c | 162 | ||||
| -rw-r--r-- | lib/resource.h | 23 | ||||
| -rw-r--r-- | lib/slab.c | 87 | ||||
| -rw-r--r-- | lib/xmalloc.c | 21 | ||||
| -rw-r--r-- | sysdep/config.h | 4 |
21 files changed, 918 insertions, 126 deletions
@@ -2,11 +2,13 @@ # (c) 1998 Martin Mares <mj@ucw.cz> TOPDIR=$(shell pwd) -CPPFLAGS=-I$(TOPDIR) -CFLAGS=-O2 -Wall -W -Wstrict-prototypes -Wno-unused -Wno-parentheses $(CPPFLAGS) +CPPFLAGS=-I$(TOPDIR)/sysdep/linux -I$(TOPDIR) +OPT=-O2 +DEBUG=-g#gdb +CFLAGS=$(OPT) $(DEBUG) -Wall -W -Wstrict-prototypes -Wno-unused -Wno-parentheses PROTOCOLS= -DIRS=sysdep/linux nest $(PROTOCOLS) lib +DIRS=nest $(PROTOCOLS) lib sysdep/linux sysdep/unix ARCHS=$(join $(addsuffix /,$(DIRS)),$(subst /,_,$(addsuffix .a,$(DIRS)))) export @@ -27,5 +29,5 @@ dep: set -e ; for a in $(DIRS) ; do $(MAKE) -C $$a dep ; done clean: - rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend` + rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend -or -name .#*` rm -f bird .dep @@ -1,58 +1,70 @@ Core ~~~~ -- route validation - fake multipath? - config file: symbolic constants? - counters (according to SNMP MIB?) - generation of subnet mask ICMP's for v6? -- debugging dumps and protocol tracing! - unaligned accesses? +- neighbor cache: local broadcast address? +- ipv4: recognize site scope addresses? +- ifdef out some debugging code? +- better memory allocators +- precedence of all packets (incl. TCP) +- default preferences of protocols: prefer BGP over OSPF/RIP external routes? +- all internal tables are in host order +- filter: logging of dropped routes (?) +- limitation of memory consumption: per-process and total (?) +- alloca +- adding of route: clear all bits not covered by masklen +- switch: generate default route only if at least one BGP connection exists -RIP -~~~ -- RIP: export-only and import-only mode? -- drop RIPv1 (Historic protocol)? - -OSPF -~~~~ - -Almquist & Kastenholz [Page 111] -RFC 1716 Towards Requirements for IP Routers November 1994 +- route recalculation timing + flap dampening +- reconfiguration without restart of all protocols? +- change of interface address: ??? (down and up?) +- "generate default route" switch for all IGP's -7.2.2.2 Specific Issues +- running protocol on an interface: + - interface is not required to exist + - can specify a wildcard pattern or an interface list - Virtual Links +- timers - one-shot and periodic, resolution 1 sec, randomized +- re-configuration: restart of routing protocols (shutdown mode) +- route: originating AS - There is a minor error in the specification that can cause - routing loops when all of the following conditions are - simultaneously true: +- Check incoming packets and log errors!! - (1) A virtual link is configured through a transit area, - (2) Two separate paths exist, each having the same - endpoints, but one utilizing only non-virtual - backbone links, and the other using links in the - transit area, and +RIP +~~~ + - RIP: export-only and import-only mode? + - drop RIPv1 (Historic protocol)? + - Route Tag + - limit routing table xfer (frequency, only to neighbors) + - multicast on/off + - remember routes for all neighbors? - (3) The latter path is part of the (underlying physical - representation of the) configured virtual link, - routing loops may occur. +OSPF +~~~~ + - Dijkstra: use Fibonacci heaps? + - point-to-point interface with address: advertise as stub network + - static routes: stub networks? + - modes: PtP, PtP-unnumbered, Broadcast, NBMA, point-to-multipoint + - importing of device routes for networks where we don't run OSPF + - tie breaking for equal type 2 ext metrics by using internal (type 1) metric + - SPF tree recalc timing (per-area timers?) + - aggregation: specify network list for each area + - stub area: either no external routes or only default route + - automatic generation of external route tags (RFC1403) - To prevent this, an implementation of OSPF SHOULD invoke - the calculation in Section 16.3 of [ROUTE:1] whenever any - part of the path to the destination is a virtual link (the - specification only says this is necessary when the first - hop is a virtual link). BGP ~~~ -- BGP: - in, local, out RIB - maxsize=4096 - BGP identifier aka router id - - removal of loops + - detection of loops - aggregation, ATOMIC_AGGREGATE - communities - confederations @@ -71,73 +83,4 @@ BGP - expected neighbor AS - hold time - idle timer after error: initial value, exponential growth, maximum value - -- address testing macros (ALL_ZEROS) -- all internal tables are in network order (?) -- logging of errors and debug dumps -- filter: logging of dropped routes (?) -- limitation of memory consumption: per-process and total -- alloca -- precedence of all packets (incl. TCP) -- adding of route: clear all bits not covered by masklen -- switch: generate default route only if at least one BGP connection exists - -- route update: new, change, remove -- route recalculation timing - -- CONFIG_TOS -- CONFIG_MULTIPATH - -- reconfiguration without restart of all protocols? -- change of interface address: ??? (down and up?) -- "generate default route" switch for all IGP's - -- RIPv2: - - Route Tag - - limit routing table xfer (frequency, only to neighbors) - - multicast on/off - - remember routes for all neighbors? - -- BGP: - import of IGP routes (use external route tags from OSPF) - -- Interface: - - RIP metric - - multicast capability flag - - MTU - - OSPF metrics (per-TOS) - -- running protocol on an interface: - - interface is not required to exist - - can specify a wildcard pattern or an interface list - -- preferences: - - directly connected - - static - - OSPF internal, OSPF ext type 1 (comparable metrics), OSPF inter-area - - RIP - - BGP - - OSPF ext type 2 - - sink - -- lib: - - MD5 - -- OSPF: - - Dijkstra: use Fibonacci heaps? - - point-to-point interface with address: advertise as stub network - - static routes: stub networks? - - modes: PtP, PtP-unnumbered, Broadcast, NBMA, point-to-multipoint - - importing of device routes for networks where we don't run OSPF - - tie breaking for equal type 2 ext metrics by using internal (type 1) metric - - SPF tree recalc timing (per-area timers?) - - aggregation: specify network list for each area - - stub area: either no external routes or only default route - - automatic generation of external route tags (RFC1403) -- what about - using the same rule for RIPv2? [shared code?] - -- timers - one-shot and periodic, resolution 1 sec, randomized -- re-configuration: restart of routing protocols (shutdown mode) -- route: originating AS - -- Check incoming packets and log errors!! diff --git a/lib/Makefile b/lib/Makefile index 214f76af..6eb14e1e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -1,3 +1,9 @@ -OBJS=lists.o +OBJS=lists.o bitops.o resource.o xmalloc.o mempool.o slab.o md5.o + +ifdef IPV6 +OBJS += ipv6.o +else +OBJS += ipv4.o +endif include $(TOPDIR)/Rules diff --git a/lib/birdlib.h b/lib/birdlib.h index eb95585f..5e533b66 100644 --- a/lib/birdlib.h +++ b/lib/birdlib.h @@ -13,17 +13,28 @@ #define OFFSETOF(s, i) ((unsigned int)&((s *)0)->i) #define SKIP_BACK(s, i, p) ((s *)((char *)p - OFFSETOF(s, i))) +#define ALIGN(s, a) (((s)+a-1)&~(a-1)) + +/* Functions which don't return */ + +#define NORET __attribute__((noreturn)) /* Logging and dying */ void log(char *msg, ...); -void die(char *msg, ...); +void die(char *msg, ...) NORET; #define L_DEBUG "\001" /* Debugging messages */ #define L_INFO "\002" /* Informational messages */ #define L_WARN "\003" /* Warnings */ #define L_ERR "\004" /* Errors */ #define L_AUTH "\005" /* Authorization failed etc. */ +#define L_FATAL "\006" /* Fatal errors */ + +void log_init(char *); /* Initialize logging to given file (NULL=stderr, ""=syslog) */ +void log_init_debug(char *); /* Initialize debug dump to given file (NULL=stderr, ""=off) */ + +void debug(char *msg, ...); /* Printf to debug output */ /* Debugging */ diff --git a/lib/bitops.c b/lib/bitops.c new file mode 100644 index 00000000..10bca047 --- /dev/null +++ b/lib/bitops.c @@ -0,0 +1,32 @@ +/* + * BIRD Library -- Generic Bit Operations + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "bitops.h" + +u32 +u32_mkmask(unsigned n) +{ + return n ? ~((1 << (32 - n)) - 1) : 0; +} + +int +u32_masklen(u32 x) +{ + int l = 0; + u32 n = ~x; + + if (n & (n+1)) return -1; + if (x & 0x0000ffff) { x &= 0x0000ffff; l += 16; } + if (x & 0x00ff00ff) { x &= 0x00ff00ff; l += 8; } + if (x & 0x0f0f0f0f) { x &= 0x0f0f0f0f; l += 4; } + if (x & 0x33333333) { x &= 0x33333333; l += 2; } + if (x & 0x55555555) l++; + if (x & 0xaaaaaaaa) l++; + return l; +} diff --git a/lib/bitops.h b/lib/bitops.h new file mode 100644 index 00000000..6bfc95ff --- /dev/null +++ b/lib/bitops.h @@ -0,0 +1,19 @@ +/* + * BIRD Library -- Generic Bit Operations + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +/* + * Bit mask operations: + * + * u32_mkmask Make bit mask consisting of <n> consecutive ones + * from the left and the rest filled with zeroes. + * E.g., u32_mkmask(5) = 0xf8000000. + * u32_masklen Inverse operation to u32_mkmask, -1 if not a bitmask. + */ + +u32 u32_mkmask(unsigned); +int u32_masklen(u32); @@ -15,4 +15,24 @@ #include "ipv6.h" #endif +/* + * ip_classify() returns either a negative number for invalid addresses + * or scope OR'ed together with address type. + */ + +#define IADDR_INVALID -1 +#define IADDR_SCOPE_MASK 0xfff +#define IADDR_HOST 0x1000 +#define IADDR_BROADCAST 0x2000 +#define IADDR_MULTICAST 0x4000 + +/* + * Address scope + */ + +#define SCOPE_HOST 0 +#define SCOPE_LINK 1 +#define SCOPE_SITE 2 +#define SCOPE_UNIVERSE 3 + #endif diff --git a/lib/ipv4.c b/lib/ipv4.c new file mode 100644 index 00000000..52f5b0b2 --- /dev/null +++ b/lib/ipv4.c @@ -0,0 +1,29 @@ +/* + * BIRD Library -- IPv4 Address Manipulation Functions + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "lib/ip.h" + +int +ipv4_classify(u32 a) +{ + u32 b = a >> 24U; + + if (b && b <= 0xdf) + { + if (b == 0x7f) + return IADDR_HOST | SCOPE_HOST; + else + return IADDR_HOST | SCOPE_UNIVERSE; + } + if (b >= 0xe0 && b <= 0xef) + return IADDR_MULTICAST | SCOPE_UNIVERSE; + if (a == 0xffffffff) + return IADDR_BROADCAST | SCOPE_LINK; + return IADDR_INVALID; +} @@ -11,6 +11,15 @@ #include <netinet/in.h> +#include "lib/bitops.h" + +#ifdef DEBUG + +/* + * Use the structural representation when you want to make sure + * nobody unauthorized attempts to handle ip_addr as number. + */ + typedef struct ipv4_addr { u32 addr; } ip_addr; @@ -18,18 +27,37 @@ typedef struct ipv4_addr { #define _I(x) (x).addr #define _MI(x) ((struct ip_addr) { x }) +#else + +typedef u32 ip_addr; + +#define _I(x) (x) +#define _MI(x) (x) + +#endif + #define IPA_NONE (_MI(0)) #define ipa_equal(x,y) (_I(x) == _I(y)) +#define ipa_nonzero(x) _I(x) #define ipa_and(x,y) _MI(_I(x) & _I(y)) #define ipa_or(x,y) _MI(_I(x) | _I(y)) #define ipa_not(x) _MI(~_I(x)) -#define ipa_mkmask(x) _MI(ipv4_mkmask(x)) -#define ipa_mklen(x) ipv4_mklen(_I(x)) +#define ipa_mkmask(x) _MI(u32_mkmask(x)) +#define ipa_mklen(x) u32_masklen(_I(x)) +#define ipa_hash(x) ipv4_hash(_I(x)) +#define ipa_hton(x) x = _MI(htonl(_I(x))) +#define ipa_ntoh(x) x = _MI(ntohl(_I(x))) +#define ipa_classify(x) ipv4_classify(_I(x)) unsigned ipv4_mklen(u32); u32 ipv4_mkmask(unsigned); +int ipv4_classify(u32); -/* ??? htonl and ntohl ??? */ +/* FIXME: Is this hash function uniformly distributed over standard routing tables? */ +static inline unsigned ipv4_hash(u32 a) +{ + return a ^ (a >> 16) ^ (a >> 24); +} #endif diff --git a/lib/ipv6.c b/lib/ipv6.c new file mode 100644 index 00000000..e612af72 --- /dev/null +++ b/lib/ipv6.c @@ -0,0 +1,12 @@ +/* + * BIRD Library -- IPv6 Address Manipulation Functions + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include "nest/bird.h" +#include "lib/ip.h" + +#error "Ought to implement these." @@ -25,6 +25,7 @@ typedef struct ipv4_addr { #define IPA_NONE _MI(0,0,0,0) #define ipa_equal(x,y) (!memcmp(&(x),&(y),sizeof(ip_addr))) +#define ipa_nonzero(x) (_I0(a) || _I1(a) || _I2(a) || _I3(a)) #define ipa_and(a,b) _MI(_I0(a) & _I0(b), \ _I1(a) & _I1(b), \ _I2(a) & _I2(b), \ @@ -34,11 +35,24 @@ typedef struct ipv4_addr { _I2(a) | _I2(b), \ _I3(a) | _I3(b)) #define ipa_not(a) _MI(~_I0(a),~_I1(a),~_I2(a),~_I3(a)) - #define ipa_mkmask(x) ipv6_mkmask(x) -#define ipa_mklen(x) ipv6_mklen(x) +#define ipa_mklen(x) ipv6_mklen(&(x)) +#define ipa_hash(x) ipv6_hash(&(x)) +#define ipa_hton(x) ipv6_hton(&(x)) +#define ipa_ntoh(x) ipv6_ntoh(&(x)) +#define ipa_classify(x) ipv6_classify(&(x)) ip_addr ipv6_mkmask(unsigned); -unsigned ipv6_mklen(ip_addr); +unsigned ipv6_mklen(ip_addr *); +int ipv6_classify(ip_addr *); +void ipv6_hton(ip_addr *); +void ipv6_ntoh(ip_addr *); + +/* FIXME: Is this hash function uniformly distributed over standard routing tables? */ +static inline unsigned ipv6_hash(ip_addr *a) +{ + u32 x = _I0(*a) ^ _I1(*a) ^ _I2(*a) ^ _I3(*a); + return x ^ (x >> 16) ^ (x >> 8); +} #endif diff --git a/lib/lists.c b/lib/lists.c index 55c2b0fd..c14eb4c7 100644 --- a/lib/lists.c +++ b/lib/lists.c @@ -16,7 +16,7 @@ add_tail(list *l, node *n) { node *z = l->tail; - n->next = (node *) &l->tail; + n->next = (node *) &l->null; n->prev = z; z->next = n; l->tail = n; diff --git a/lib/lists.h b/lib/lists.h index acc054d8..3230724f 100644 --- a/lib/lists.h +++ b/lib/lists.h @@ -33,7 +33,7 @@ void insert_node(node *, node *); #ifndef _BIRD_LISTS_C_ #define LIST_INLINE extern inline -#include <lib/lists.c> +#include "lib/lists.c" #undef LIST_INLINE #else #define LIST_INLINE diff --git a/lib/md5.c b/lib/md5.c new file mode 100644 index 00000000..9fec594c --- /dev/null +++ b/lib/md5.c @@ -0,0 +1,252 @@ +/* + * This code implements the MD5 message-digest algorithm. + * The algorithm is due to Ron Rivest. This code was + * written by Colin Plumb in 1993, no copyright is claimed. + * This code is in the public domain; do with it what you wish. + * + * Equivalent code is available from RSA Data Security, Inc. + * This code has been tested against that, and is equivalent, + * except that you don't need to include two pages of legalese + * with every copy. + * + * To compute the message digest of a chunk of bytes, declare an + * MD5Context structure, pass it to MD5Init, call MD5Update as + * needed on buffers full of bytes, and then call MD5Final, which + * will fill a supplied 16-byte array with the digest. + */ + +/* + * Adapted for BIRD by Martin Mares <mj@atrey.karlin.mff.cuni.cz> + */ + +#include <string.h> /* for memcpy() */ +#include "nest/bird.h" +#include "md5.h" + +#ifdef CPU_LITTLE_ENDIAN +#define byteReverse(buf, len) /* Nothing */ +#else +void byteReverse(unsigned char *buf, unsigned longs); + +/* + * Note: this code is harmless on little-endian machines. + */ +void byteReverse(unsigned char *buf, unsigned longs) +{ + u32 t; + do { + t = (u32) ((unsigned) buf[3] << 8 | buf[2]) << 16 | + ((unsigned) buf[1] << 8 | buf[0]); + *(u32 *) buf = t; + buf += 4; + } while (--longs); +} +#endif + +/* + * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious + * initialization constants. + */ +void MD5Init(struct MD5Context *ctx) +{ + ctx->buf[0] = 0x67452301; + ctx->buf[1] = 0xefcdab89; + ctx->buf[2] = 0x98badcfe; + ctx->buf[3] = 0x10325476; + + ctx->bits[0] = 0; + ctx->bits[1] = 0; +} + +/* + * Update context to reflect the concatenation of another buffer full + * of bytes. + */ +void MD5Update(struct MD5Context *ctx, unsigned char const *buf, unsigned len) +{ + u32 t; + + /* Update bitcount */ + + t = ctx->bits[0]; + if ((ctx->bits[0] = t + ((u32) len << 3)) < t) + ctx->bits[1]++; /* Carry from low to high */ + ctx->bits[1] += len >> 29; + + t = (t >> 3) & 0x3f; /* Bytes already in shsInfo->data */ + + /* Handle any leading odd-sized chunks */ + + if (t) { + unsigned char *p = (unsigned char *) ctx->in + t; + + t = 64 - t; + if (len < t) { + memcpy(p, buf, len); + return; + } + memcpy(p, buf, t); + byteReverse(ctx->in, 16); + MD5Transform(ctx->buf, (u32 *) ctx->in); + buf += t; + len -= t; + } + /* Process data in 64-byte chunks */ + + while (len >= 64) { + memcpy(ctx->in, buf, 64); + byteReverse(ctx->in, 16); + MD5Transform(ctx->buf, (u32 *) ctx->in); + buf += 64; + len -= 64; + } + + /* Handle any remaining bytes of data. */ + + memcpy(ctx->in, buf, len); +} + +/* + * Final wrapup - pad to 64-byte boundary with the bit pattern + * 1 0* (64-bit count of bits processed, MSB-first) + */ +void MD5Final(unsigned char digest[16], struct MD5Context *ctx) +{ + unsigned count; + unsigned char *p; + + /* Compute number of bytes mod 64 */ + count = (ctx->bits[0] >> 3) & 0x3F; + + /* Set the first char of padding to 0x80. This is safe since there is + always at least one byte free */ + p = ctx->in + count; + *p++ = 0x80; + + /* Bytes of padding needed to make 64 bytes */ + count = 64 - 1 - count; + + /* Pad out to 56 mod 64 */ + if (count < 8) { + /* Two lots of padding: Pad the first block to 64 bytes */ + memset(p, 0, count); + byteReverse(ctx->in, 16); + MD5Transform(ctx->buf, (u32 *) ctx->in); + + /* Now fill the next block with 56 bytes */ + memset(ctx->in, 0, 56); + } else { + /* Pad block to 56 bytes */ + memset(p, 0, count - 8); + } + byteReverse(ctx->in, 14); + + /* Append length in bits and transform */ + ((u32 *) ctx->in)[14] = ctx->bits[0]; + ((u32 *) ctx->in)[15] = ctx->bits[1]; + + MD5Transform(ctx->buf, (u32 *) ctx->in); + byteReverse((unsigned char *) ctx->buf, 4); + memcpy(digest, ctx->buf, 16); + memset((char *) ctx, 0, sizeof(ctx)); /* In case it's sensitive */ +} + +/* The four core functions - F1 is optimized somewhat */ + +/* #define F1(x, y, z) (x & y | ~x & z) */ +#define F1(x, y, z) (z ^ (x & (y ^ z))) +#define F2(x, y, z) F1(z, x, y) +#define F3(x, y, z) (x ^ y ^ z) +#define F4(x, y, z) (y ^ (x | ~z)) + +/* This is the central step in the MD5 algorithm. */ +#define MD5STEP(f, w, x, y, z, data, s) \ + ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x ) + +/* + * The core of the MD5 algorithm, this alters an existing MD5 hash to + * reflect the addition of 16 longwords of new data. MD5Update blocks + * the data and converts bytes into longwords for this routine. + */ +void MD5Transform(u32 buf[4], u32 const in[16]) +{ + register u32 a, b, c, d; + + a = buf[0]; + b = buf[1]; + c = buf[2]; + d = buf[3]; + + MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7); + MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12); + MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17); + MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22); + MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7); + MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12); + MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17); + MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22); + MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7); + MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12); + MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17); + MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22); + MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7); + MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12); + MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17); + MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22); + + MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5); + MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9); + MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14); + MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20); + MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5); + MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9); + MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14); + MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20); + MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5); + MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9); + MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14); + MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20); + MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5); + MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9); + MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14); + MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20); + + MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4); + MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11); + MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16); + MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23); + MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4); + MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11); + MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16); + MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23); + MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4); + MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11); + MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16); + MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23); + MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4); + MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11); + MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16); + MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23); + + MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6); + MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10); + MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15); + MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21); + MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6); + MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10); + MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15); + MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21); + MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6); + MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10); + MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15); + MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21); + MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6); + MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10); + MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15); + MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21); + + buf[0] += a; + buf[1] += b; + buf[2] += c; + buf[3] += d; +} diff --git a/lib/md5.h b/lib/md5.h new file mode 100644 index 00000000..12586357 --- /dev/null +++ b/lib/md5.h @@ -0,0 +1,16 @@ +#ifndef MD5_H +#define MD5_H + +struct MD5Context { + u32 buf[4]; + u32 bits[2]; + unsigned char in[64]; +}; + +void MD5Init(struct MD5Context *context); +void MD5Update(struct MD5Context *context, unsigned char const *buf, + unsigned len); +void MD5Final(unsigned char digest[16], struct MD5Context *context); +void MD5Transform(u32 buf[4], u32 const in[16]); + +#endif /* !MD5_H */ diff --git a/lib/mempool.c b/lib/mempool.c new file mode 100644 index 00000000..d2f2c092 --- /dev/null +++ b/lib/mempool.c @@ -0,0 +1,133 @@ +/* + * BIRD Resource Manager -- Memory Pools + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdlib.h> +#include <string.h> + +#include "nest/bird.h" +#include "lib/resource.h" + +struct mp_chunk { + struct mp_chunk *next; + byte data[0]; +}; + +struct mempool { + resource r; + byte *ptr, *end; + struct mp_chunk *first, **plast; + unsigned chunk_size, threshold, total; +}; + +void mp_free(resource *); +void mp_dump(resource *); + +struct resclass mp_class = { + "MemPool", + sizeof(struct mempool), + mp_free, + mp_dump +}; + +mempool +*mp_new(pool *p, unsigned blk) +{ + mempool *m = ralloc(p, &mp_class); + m->ptr = m->end = NULL; + m->first = NULL; + m->plast = &m->first; + m->chunk_size = blk; + m->threshold = 3*blk/4; + m->total = 0; + return m; +} + +void * +mp_alloc(mempool *m, unsigned size) +{ + byte *a = (byte *) ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN); + byte *e = a + size; + + if (e <= m->end) + { + m->ptr = e; + return a; + } + else + { + struct mp_chunk *c; + if (size >= m->threshold) + { + c = xmalloc(sizeof(struct mp_chunk) + size); + m->total += size; + } + else + { + c = xmalloc(sizeof(struct mp_chunk) + m->chunk_size); + m->ptr = c->data + size; + m->end = c->data + m->chunk_size; + m->total += m->chunk_size; + } + *m->plast = c; + m->plast = &c->next; + c->next = NULL; + return c->data; + } +} + +void * +mp_allocu(mempool *m, unsigned size) +{ + byte *a = m->ptr; + byte *e = a + size; + + if (e <= m->end) + { + m->ptr = e; + return a; + } + return mp_alloc(m, size); +} + +void * +mp_allocz(mempool *m, unsigned size) +{ + void *z = mp_alloc(m, size); + + bzero(z, size); + return z; +} + +void +mp_free(resource *r) +{ + mempool *m = (mempool *) r; + struct mp_chunk *c, *d; + + for(d=m->first; d; d = c) + { + c = d->next; + xfree(d); + } +} + +void +mp_dump(resource *r) +{ + mempool *m = (mempool *) r; + struct mp_chunk *c; + int cnt; + + for(cnt=0, c=m->first; c; c=c->next, cnt++) + ; + debug("(chunk=%d threshold=%d count=%d total=%d)\n", + m->chunk_size, + m->threshold, + cnt, + m->total); +} diff --git a/lib/resource.c b/lib/resource.c new file mode 100644 index 00000000..2806a90a --- /dev/null +++ b/lib/resource.c @@ -0,0 +1,162 @@ +/* + * BIRD Resource Manager + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "nest/bird.h" +#include "lib/resource.h" + +struct pool { + resource r; + list inside; +}; + +void pool_dump(resource *); +void pool_free(resource *); + +static struct resclass pool_class = { + "Pool", + sizeof(pool), + pool_free, + pool_dump +}; + +pool root_pool; + +static int indent; + +pool * +rp_new(pool *p) +{ + pool *z = ralloc(p, &pool_class); + init_list(&z->inside); + return z; +} + +void +pool_free(resource *P) +{ + pool *p = (pool *) P; + resource *r, *rr; + + r = HEAD(p->inside); + while (rr = (resource *) r->n.next) + { + r->class->free(r); + xfree(r); + r = rr; + } +} + +void +pool_dump(resource *P) +{ + pool *p = (pool *) P; + resource *r; + + debug("\n"); + indent += 3; + WALK_LIST(r, p->inside) + rdump(r); + indent -= 3; +} + +void +rfree(void *res) +{ + resource *r = res; + + if (r) + { + if (r->n.next) + rem_node(&r->n); + r->class->free(r); + xfree(r); + } +} + +void +rdump(void *res) +{ + char x[16]; + resource *r = res; + + sprintf(x, "%%%ds%%08x ", indent); + debug(x, "", (int) r); + if (r) + { + debug("%-6s", r->class->name); + r->class->dump(r); + } + else + debug("NULL\n"); +} + +void * +ralloc(pool *p, struct resclass *c) +{ + resource *r = xmalloc(c->size); + + r->class = c; + add_tail(&p->inside, &r->n); + return r; +} + +void +resource_init(void) +{ + root_pool.r.class = &pool_class; + init_list(&root_pool.inside); +} + +/* + * Memory blocks. + */ + +struct mblock { + resource r; + unsigned size; + byte data[0]; +}; + +void mbl_free(resource *r) +{ +} + +void mbl_debug(resource *r) +{ + struct mblock *m = (struct mblock *) r; + + debug("(size=%d)\n", m->size); +} + +struct resclass mb_class = { + "Memory", + 0, + mbl_free, + mbl_debug, +}; + +void * +mb_alloc(pool *p, unsigned size) +{ + struct mblock *b = xmalloc(sizeof(struct mblock) + size); + + b->r.class = &mb_class; + add_tail(&p->inside, &b->r.n); + b->size = size; + return b->data; +} + +void +mb_free(void *m) +{ + struct mblock *b = SKIP_BACK(struct mblock, data, m); + rfree(b); +} diff --git a/lib/resource.h b/lib/resource.h index eabc963d..03c083a5 100644 --- a/lib/resource.h +++ b/lib/resource.h @@ -14,42 +14,43 @@ /* Resource */ typedef struct resource { - node n; /* Inside resource pool */ - struct resclass *class; /* Resource class */ + node n; /* Inside resource pool */ + struct resclass *class; /* Resource class */ } resource; /* Resource class */ struct resclass { - char *name; /* Resource class name */ - unsigned size; /* Standard size of single resource */ - void (*free)(resource *); /* Freeing function */ - void (*dump)(resource *); /* Dump to debug output */ + char *name; /* Resource class name */ + unsigned size; /* Standard size of single resource */ + void (*free)(resource *); /* Freeing function */ + void (*dump)(resource *); /* Dump to debug output */ }; /* Generic resource manipulation */ typedef struct pool pool; +void resource_init(void); pool *rp_new(pool *); /* Create new pool */ -void rp_init(pool *); /* Initialize static pool */ -void rp_empty(pool *); /* Free everything in the pool */ +void rp_free(pool *); /* Free everything in the pool */ void rfree(void *); /* Free single resource */ void rdump(void *); /* Dump to debug output */ -void ralloc(pool *, struct resclass *); +void *ralloc(pool *, struct resclass *); + +extern pool root_pool; /* Normal memory blocks */ void *mb_alloc(pool *, unsigned size); -void *mb_free(void *); +void mb_free(void *); /* Memory pools with linear allocation */ typedef struct mempool mempool; mempool *mp_new(pool *, unsigned blk); -void mp_trim(pool *); /* Free unused memory */ void *mp_alloc(mempool *, unsigned size); /* Aligned */ void *mp_allocu(mempool *, unsigned size); /* Unaligned */ void *mp_allocz(mempool *, unsigned size); /* With clear */ diff --git a/lib/slab.c b/lib/slab.c new file mode 100644 index 00000000..e71c7de2 --- /dev/null +++ b/lib/slab.c @@ -0,0 +1,87 @@ +/* + * BIRD Resource Manager -- SLABs + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdlib.h> +#include <string.h> + +#include "nest/bird.h" +#include "lib/resource.h" + +/* + * These are only fake, soon to change... + */ + +struct sl_obj { + node n; + byte data[0]; +}; + +struct slab { + resource r; + unsigned size; + list objs; +}; + +void slab_free(resource *r); +void slab_dump(resource *r); + +struct resclass sl_class = { + "Slab", + sizeof(struct slab), + slab_free, + slab_dump +}; + +slab * +sl_new(pool *p, unsigned size) +{ + slab *s = ralloc(p, &sl_class); + s->size = size; + init_list(&s->objs); + return s; +} + +void * +sl_alloc(slab *s) +{ + struct sl_obj *o = xmalloc(sizeof(struct sl_obj) + s->size); + + add_tail(&s->objs, &o->n); + return o->data; +} + +void +sl_free(slab *s, void *oo) +{ + struct sl_obj *o = SKIP_BACK(struct sl_obj, data, oo); + + rem_node(&o->n); + xfree(o); +} + +void +slab_free(resource *r) +{ + slab *s = (slab *) r; + struct sl_obj *o, *p; + + for(o = HEAD(s->objs); p = (struct sl_obj *) o->n.next; o = p) + xfree(o); +} + +void +slab_dump(resource *r) +{ + slab *s = (slab *) r; + int cnt = 0; + struct sl_obj *o; + + WALK_LIST(o, s->objs) + cnt++; + debug("(%d objects per %d bytes)\n", cnt, s->size); +} diff --git a/lib/xmalloc.c b/lib/xmalloc.c new file mode 100644 index 00000000..c1ce7ea3 --- /dev/null +++ b/lib/xmalloc.c @@ -0,0 +1,21 @@ +/* + * BIRD Library -- malloc() With Checking + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include <stdlib.h> + +#include "nest/bird.h" +#include "lib/resource.h" + +void * +xmalloc(unsigned size) +{ + void *p = malloc(size); + if (p) + return p; + die("Unable to allocate %d bytes of memory", size); +} diff --git a/sysdep/config.h b/sysdep/config.h index a17f4d14..c9c13936 100644 --- a/sysdep/config.h +++ b/sysdep/config.h @@ -47,4 +47,8 @@ typedef u16 word; #define CONFIG_BGP #define CONFIG_OSPF +/* Autodetected system features */ + +#define HAVE_SYSLOG + #endif |