Revision 74c838a8
| lib/Modules | ||
|---|---|---|
| 7 | 7 |
birdlib.h |
| 8 | 8 |
bitops.c |
| 9 | 9 |
bitops.h |
| 10 |
ip.h |
|
| 10 |
idm.c |
|
| 11 |
idm.h |
|
| 11 | 12 |
ip.c |
| 13 |
ip.h |
|
| 12 | 14 |
lists.c |
| 13 | 15 |
lists.h |
| 14 | 16 |
md5.c |
| lib/idm.c | ||
|---|---|---|
| 1 |
/* |
|
| 2 |
* BIRD Library -- ID Map |
|
| 3 |
* |
|
| 4 |
* (c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org> |
|
| 5 |
* (c) 2013--2015 CZ.NIC z.s.p.o. |
|
| 6 |
* |
|
| 7 |
* Can be freely distributed and used under the terms of the GNU GPL. |
|
| 8 |
*/ |
|
| 9 |
|
|
| 10 |
#include <stdlib.h> |
|
| 11 |
|
|
| 12 |
#include "nest/bird.h" |
|
| 13 |
#include "lib/idm.h" |
|
| 14 |
#include "lib/resource.h" |
|
| 15 |
#include "lib/string.h" |
|
| 16 |
|
|
| 17 |
|
|
| 18 |
void |
|
| 19 |
idm_init(struct idm *m, pool *p, uint size) |
|
| 20 |
{
|
|
| 21 |
m->pos = 0; |
|
| 22 |
m->used = 1; |
|
| 23 |
m->size = size; |
|
| 24 |
m->data = mb_allocz(p, m->size * sizeof(u32)); |
|
| 25 |
|
|
| 26 |
/* ID 0 is reserved */ |
|
| 27 |
m->data[0] = 1; |
|
| 28 |
} |
|
| 29 |
|
|
| 30 |
static inline int u32_cto(uint x) { return ffs(~x) - 1; }
|
|
| 31 |
|
|
| 32 |
u32 |
|
| 33 |
idm_alloc(struct idm *m) |
|
| 34 |
{
|
|
| 35 |
uint i, j; |
|
| 36 |
|
|
| 37 |
for (i = m->pos; i < m->size; i++) |
|
| 38 |
if (m->data[i] != 0xffffffff) |
|
| 39 |
goto found; |
|
| 40 |
|
|
| 41 |
/* If we are at least 7/8 full, expand */ |
|
| 42 |
if (m->used > (m->size * 28)) |
|
| 43 |
{
|
|
| 44 |
m->size *= 2; |
|
| 45 |
m->data = mb_realloc(m->data, m->size * sizeof(u32)); |
|
| 46 |
memset(m->data + i, 0, (m->size - i) * sizeof(u32)); |
|
| 47 |
goto found; |
|
| 48 |
} |
|
| 49 |
|
|
| 50 |
for (i = 0; i < m->pos; i++) |
|
| 51 |
if (m->data[i] != 0xffffffff) |
|
| 52 |
goto found; |
|
| 53 |
|
|
| 54 |
ASSERT(0); |
|
| 55 |
|
|
| 56 |
found: |
|
| 57 |
ASSERT(i < 0x8000000); |
|
| 58 |
|
|
| 59 |
m->pos = i; |
|
| 60 |
j = u32_cto(m->data[i]); |
|
| 61 |
|
|
| 62 |
m->data[i] |= (1 << j); |
|
| 63 |
m->used++; |
|
| 64 |
return 32 * i + j; |
|
| 65 |
} |
|
| 66 |
|
|
| 67 |
void |
|
| 68 |
idm_free(struct idm *m, u32 id) |
|
| 69 |
{
|
|
| 70 |
uint i = id / 32; |
|
| 71 |
uint j = id % 32; |
|
| 72 |
|
|
| 73 |
ASSERT((i < m->size) && (m->data[i] & (1 << j))); |
|
| 74 |
m->data[i] &= ~(1 << j); |
|
| 75 |
m->used--; |
|
| 76 |
} |
|
| lib/idm.h | ||
|---|---|---|
| 1 |
/* |
|
| 2 |
* BIRD Library -- ID Map |
|
| 3 |
* |
|
| 4 |
* (c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org> |
|
| 5 |
* (c) 2013--2015 CZ.NIC z.s.p.o. |
|
| 6 |
* |
|
| 7 |
* Can be freely distributed and used under the terms of the GNU GPL. |
|
| 8 |
*/ |
|
| 9 |
|
|
| 10 |
#ifndef _BIRD_IDM_H_ |
|
| 11 |
#define _BIRD_IDM_H_ |
|
| 12 |
|
|
| 13 |
struct idm |
|
| 14 |
{
|
|
| 15 |
u32 *data; |
|
| 16 |
u32 pos; |
|
| 17 |
u32 used; |
|
| 18 |
u32 size; |
|
| 19 |
}; |
|
| 20 |
|
|
| 21 |
void idm_init(struct idm *m, pool *p, uint size); |
|
| 22 |
u32 idm_alloc(struct idm *m); |
|
| 23 |
void idm_free(struct idm *m, u32 id); |
|
| 24 |
|
|
| 25 |
#endif |
|
| nest/route.h | ||
|---|---|---|
| 36 | 36 |
struct fib_node *next; /* Next in hash chain */ |
| 37 | 37 |
struct fib_iterator *readers; /* List of readers of this node */ |
| 38 | 38 |
byte flags; /* User-defined, will be removed */ |
| 39 |
u32 uid; /* Unique ID based on hash, will be removed */ |
|
| 40 | 39 |
net_addr addr[0]; |
| 41 | 40 |
}; |
| 42 | 41 |
|
| nest/rt-attr.c | ||
|---|---|---|
| 52 | 52 |
#include "nest/attrs.h" |
| 53 | 53 |
#include "lib/alloca.h" |
| 54 | 54 |
#include "lib/hash.h" |
| 55 |
#include "lib/idm.h" |
|
| 55 | 56 |
#include "lib/resource.h" |
| 56 | 57 |
#include "lib/string.h" |
| 57 | 58 |
|
| ... | ... | |
| 61 | 62 |
static slab *mpnh_slab; |
| 62 | 63 |
static slab *rte_src_slab; |
| 63 | 64 |
|
| 64 |
/* rte source ID bitmap */ |
|
| 65 |
static u32 *src_ids; |
|
| 66 |
static u32 src_id_size, src_id_used, src_id_pos; |
|
| 65 |
static struct idm src_ids; |
|
| 67 | 66 |
#define SRC_ID_INIT_SIZE 4 |
| 68 | 67 |
|
| 69 | 68 |
/* rte source hash */ |
| ... | ... | |
| 87 | 86 |
{
|
| 88 | 87 |
rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src)); |
| 89 | 88 |
|
| 90 |
src_id_pos = 0; |
|
| 91 |
src_id_size = SRC_ID_INIT_SIZE; |
|
| 92 |
src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32)); |
|
| 93 |
|
|
| 94 |
/* ID 0 is reserved */ |
|
| 95 |
src_ids[0] = 1; |
|
| 96 |
src_id_used = 1; |
|
| 89 |
idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE); |
|
| 97 | 90 |
|
| 98 | 91 |
HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER); |
| 99 | 92 |
} |
| 100 | 93 |
|
| 101 |
static inline int u32_cto(uint x) { return ffs(~x) - 1; }
|
|
| 102 |
|
|
| 103 |
static inline u32 |
|
| 104 |
rte_src_alloc_id(void) |
|
| 105 |
{
|
|
| 106 |
int i, j; |
|
| 107 |
for (i = src_id_pos; i < src_id_size; i++) |
|
| 108 |
if (src_ids[i] != 0xffffffff) |
|
| 109 |
goto found; |
|
| 110 |
|
|
| 111 |
/* If we are at least 7/8 full, expand */ |
|
| 112 |
if (src_id_used > (src_id_size * 28)) |
|
| 113 |
{
|
|
| 114 |
src_id_size *= 2; |
|
| 115 |
src_ids = mb_realloc(src_ids, src_id_size * sizeof(u32)); |
|
| 116 |
bzero(src_ids + i, (src_id_size - i) * sizeof(u32)); |
|
| 117 |
goto found; |
|
| 118 |
} |
|
| 119 |
|
|
| 120 |
for (i = 0; i < src_id_pos; i++) |
|
| 121 |
if (src_ids[i] != 0xffffffff) |
|
| 122 |
goto found; |
|
| 123 |
|
|
| 124 |
ASSERT(0); |
|
| 125 |
|
|
| 126 |
found: |
|
| 127 |
ASSERT(i < 0x8000000); |
|
| 128 |
|
|
| 129 |
src_id_pos = i; |
|
| 130 |
j = u32_cto(src_ids[i]); |
|
| 131 |
|
|
| 132 |
src_ids[i] |= (1 << j); |
|
| 133 |
src_id_used++; |
|
| 134 |
return 32 * i + j; |
|
| 135 |
} |
|
| 136 |
|
|
| 137 |
static inline void |
|
| 138 |
rte_src_free_id(u32 id) |
|
| 139 |
{
|
|
| 140 |
int i = id / 32; |
|
| 141 |
int j = id % 32; |
|
| 142 |
|
|
| 143 |
ASSERT((i < src_id_size) && (src_ids[i] & (1 << j))); |
|
| 144 |
src_ids[i] &= ~(1 << j); |
|
| 145 |
src_id_used--; |
|
| 146 |
} |
|
| 147 |
|
|
| 148 | 94 |
|
| 149 | 95 |
HASH_DEFINE_REHASH_FN(RSH, struct rte_src) |
| 150 | 96 |
|
| ... | ... | |
| 165 | 111 |
src = sl_alloc(rte_src_slab); |
| 166 | 112 |
src->proto = p; |
| 167 | 113 |
src->private_id = id; |
| 168 |
src->global_id = rte_src_alloc_id();
|
|
| 114 |
src->global_id = idm_alloc(&src_ids);
|
|
| 169 | 115 |
src->uc = 0; |
| 170 | 116 |
|
| 171 | 117 |
HASH_INSERT2(src_hash, RSH, rta_pool, src); |
| ... | ... | |
| 181 | 127 |
if (src->uc == 0) |
| 182 | 128 |
{
|
| 183 | 129 |
HASH_DO_REMOVE(src_hash, RSH, sp); |
| 184 |
rte_src_free_id(src->global_id);
|
|
| 130 |
idm_free(&src_ids, src->global_id);
|
|
| 185 | 131 |
sl_free(rte_src_slab, src); |
| 186 | 132 |
} |
| 187 | 133 |
} |
| nest/rt-fib.c | ||
|---|---|---|
| 253 | 253 |
struct fib_node *e = fib_user_to_node(f, b); |
| 254 | 254 |
e->readers = NULL; |
| 255 | 255 |
e->flags = 0; |
| 256 |
e->uid = 0; |
|
| 257 | 256 |
fib_insert(f, a, e); |
| 258 | 257 |
|
| 259 | 258 |
memset(b, 0, f->node_offset); |
| proto/ospf/ospf.c | ||
|---|---|---|
| 240 | 240 |
init_list(&(p->area_list)); |
| 241 | 241 |
fib_init(&p->rtf, P->pool, p->ospf2 ? NET_IP4 : NET_IP6, |
| 242 | 242 |
sizeof(ort), OFFSETOF(ort, fn), 0, NULL); |
| 243 |
if (ospf_is_v3(p)) |
|
| 244 |
idm_init(&p->idm, P->pool, 16); |
|
| 243 | 245 |
p->areano = 0; |
| 244 | 246 |
p->gr = ospf_top_new(p, P->pool); |
| 245 | 247 |
s_init_list(&(p->lsal)); |
| proto/ospf/ospf.h | ||
|---|---|---|
| 14 | 14 |
#include "nest/bird.h" |
| 15 | 15 |
|
| 16 | 16 |
#include "lib/checksum.h" |
| 17 |
#include "lib/ip.h"
|
|
| 17 |
#include "lib/idm.h"
|
|
| 18 | 18 |
#include "lib/lists.h" |
| 19 | 19 |
#include "lib/slists.h" |
| 20 | 20 |
#include "lib/socket.h" |
| ... | ... | |
| 79 | 79 |
|
| 80 | 80 |
#define OSPF_VLINK_ID_OFFSET 0x80000000 |
| 81 | 81 |
|
| 82 |
|
|
| 83 | 82 |
struct ospf_config |
| 84 | 83 |
{
|
| 85 | 84 |
struct proto_config c; |
| ... | ... | |
| 215 | 214 |
int areano; /* Number of area I belong to */ |
| 216 | 215 |
int padj; /* Number of neighbors in Exchange or Loading state */ |
| 217 | 216 |
struct fib rtf; /* Routing table */ |
| 217 |
struct idm idm; /* OSPFv3 LSA ID map */ |
|
| 218 | 218 |
byte ospf2; /* OSPF v2 or v3 */ |
| 219 | 219 |
byte rfc1583; /* RFC1583 compatibility */ |
| 220 | 220 |
byte stub_router; /* Do not forward transit traffic */ |
| proto/ospf/rt.c | ||
|---|---|---|
| 2005 | 2005 |
/* Remove unused rt entry, some special entries are persistent */ |
| 2006 | 2006 |
if (!nf->n.type && !nf->external_rte && !nf->area_net) |
| 2007 | 2007 |
{
|
| 2008 |
if (nf->lsa_id) |
|
| 2009 |
idm_free(&p->idm, nf->lsa_id); |
|
| 2010 |
|
|
| 2008 | 2011 |
FIB_ITERATE_PUT(&fit); |
| 2009 | 2012 |
fib_delete(fib, nf); |
| 2010 | 2013 |
goto again1; |
| proto/ospf/rt.h | ||
|---|---|---|
| 81 | 81 |
orta n; |
| 82 | 82 |
u32 old_metric1, old_metric2, old_tag, old_rid; |
| 83 | 83 |
rta *old_rta; |
| 84 |
u32 lsa_id; |
|
| 84 | 85 |
u8 external_rte; |
| 85 | 86 |
u8 area_net; |
| 86 | 87 |
|
| proto/ospf/topology.c | ||
|---|---|---|
| 513 | 513 |
} |
| 514 | 514 |
} |
| 515 | 515 |
|
| 516 |
|
|
| 517 |
static inline u32 |
|
| 516 |
static u32 |
|
| 518 | 517 |
ort_to_lsaid(struct ospf_proto *p, ort *nf) |
| 519 | 518 |
{
|
| 520 | 519 |
/* |
| ... | ... | |
| 542 | 541 |
* network appeared, we choose a different way. |
| 543 | 542 |
* |
| 544 | 543 |
* In OSPFv3, it is simpler. There is not a requirement for membership of the |
| 545 |
* result in the input network, so we just use a hash-based unique ID of a |
|
| 546 |
* routing table entry for a route that originated given LSA. For ext-LSA, it |
|
| 547 |
* is an imported route in the nest's routing table (p->table). For summary-LSA, |
|
| 548 |
* it is a 'source' route in the protocol internal routing table (p->rtf). |
|
| 544 |
* result in the input network, so we just allocate a unique ID from ID map |
|
| 545 |
* and store it in nf->lsa_id for further reference. |
|
| 549 | 546 |
*/ |
| 550 | 547 |
|
| 551 | 548 |
if (ospf_is_v3(p)) |
| 552 |
return nf->fn.uid; |
|
| 549 |
{
|
|
| 550 |
if (!nf->lsa_id) |
|
| 551 |
nf->lsa_id = idm_alloc(&p->idm); |
|
| 552 |
|
|
| 553 |
return nf->lsa_id; |
|
| 554 |
} |
|
| 553 | 555 |
|
| 554 | 556 |
net_addr_ip4 *net = (void *) nf->fn.addr; |
| 555 | 557 |
u32 id = ip4_to_u32(net->prefix); |
Also available in: Unified diff