summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/Modules4
-rw-r--r--lib/idm.c76
-rw-r--r--lib/idm.h25
-rw-r--r--nest/route.h1
-rw-r--r--nest/rt-attr.c64
-rw-r--r--nest/rt-fib.c1
-rw-r--r--proto/ospf/ospf.c2
-rw-r--r--proto/ospf/ospf.h4
-rw-r--r--proto/ospf/rt.c3
-rw-r--r--proto/ospf/rt.h1
-rw-r--r--proto/ospf/topology.c16
11 files changed, 126 insertions, 71 deletions
diff --git a/lib/Modules b/lib/Modules
index 21830875..6b9b4b0f 100644
--- a/lib/Modules
+++ b/lib/Modules
@@ -7,8 +7,10 @@ sha1.h
birdlib.h
bitops.c
bitops.h
-ip.h
+idm.c
+idm.h
ip.c
+ip.h
lists.c
lists.h
md5.c
diff --git a/lib/idm.c b/lib/idm.c
new file mode 100644
index 00000000..16d0e855
--- /dev/null
+++ b/lib/idm.c
@@ -0,0 +1,76 @@
+/*
+ * BIRD Library -- ID Map
+ *
+ * (c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org>
+ * (c) 2013--2015 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include <stdlib.h>
+
+#include "nest/bird.h"
+#include "lib/idm.h"
+#include "lib/resource.h"
+#include "lib/string.h"
+
+
+void
+idm_init(struct idm *m, pool *p, uint size)
+{
+ m->pos = 0;
+ m->used = 1;
+ m->size = size;
+ m->data = mb_allocz(p, m->size * sizeof(u32));
+
+ /* ID 0 is reserved */
+ m->data[0] = 1;
+}
+
+static inline int u32_cto(uint x) { return ffs(~x) - 1; }
+
+u32
+idm_alloc(struct idm *m)
+{
+ uint i, j;
+
+ for (i = m->pos; i < m->size; i++)
+ if (m->data[i] != 0xffffffff)
+ goto found;
+
+ /* If we are at least 7/8 full, expand */
+ if (m->used > (m->size * 28))
+ {
+ m->size *= 2;
+ m->data = mb_realloc(m->data, m->size * sizeof(u32));
+ memset(m->data + i, 0, (m->size - i) * sizeof(u32));
+ goto found;
+ }
+
+ for (i = 0; i < m->pos; i++)
+ if (m->data[i] != 0xffffffff)
+ goto found;
+
+ ASSERT(0);
+
+ found:
+ ASSERT(i < 0x8000000);
+
+ m->pos = i;
+ j = u32_cto(m->data[i]);
+
+ m->data[i] |= (1 << j);
+ m->used++;
+ return 32 * i + j;
+}
+
+void
+idm_free(struct idm *m, u32 id)
+{
+ uint i = id / 32;
+ uint j = id % 32;
+
+ ASSERT((i < m->size) && (m->data[i] & (1 << j)));
+ m->data[i] &= ~(1 << j);
+ m->used--;
+}
diff --git a/lib/idm.h b/lib/idm.h
new file mode 100644
index 00000000..e3380cce
--- /dev/null
+++ b/lib/idm.h
@@ -0,0 +1,25 @@
+/*
+ * BIRD Library -- ID Map
+ *
+ * (c) 2013--2015 Ondrej Zajicek <santiago@crfreenet.org>
+ * (c) 2013--2015 CZ.NIC z.s.p.o.
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#ifndef _BIRD_IDM_H_
+#define _BIRD_IDM_H_
+
+struct idm
+{
+ u32 *data;
+ u32 pos;
+ u32 used;
+ u32 size;
+};
+
+void idm_init(struct idm *m, pool *p, uint size);
+u32 idm_alloc(struct idm *m);
+void idm_free(struct idm *m, u32 id);
+
+#endif
diff --git a/nest/route.h b/nest/route.h
index fbafe293..3a8788a7 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -36,7 +36,6 @@ struct fib_node {
struct fib_node *next; /* Next in hash chain */
struct fib_iterator *readers; /* List of readers of this node */
byte flags; /* User-defined, will be removed */
- u32 uid; /* Unique ID based on hash, will be removed */
net_addr addr[0];
};
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index d100c537..0637867b 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -52,6 +52,7 @@
#include "nest/attrs.h"
#include "lib/alloca.h"
#include "lib/hash.h"
+#include "lib/idm.h"
#include "lib/resource.h"
#include "lib/string.h"
@@ -61,9 +62,7 @@ static slab *rta_slab;
static slab *mpnh_slab;
static slab *rte_src_slab;
-/* rte source ID bitmap */
-static u32 *src_ids;
-static u32 src_id_size, src_id_used, src_id_pos;
+static struct idm src_ids;
#define SRC_ID_INIT_SIZE 4
/* rte source hash */
@@ -87,64 +86,11 @@ rte_src_init(void)
{
rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
- src_id_pos = 0;
- src_id_size = SRC_ID_INIT_SIZE;
- src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32));
-
- /* ID 0 is reserved */
- src_ids[0] = 1;
- src_id_used = 1;
+ idm_init(&src_ids, rta_pool, SRC_ID_INIT_SIZE);
HASH_INIT(src_hash, rta_pool, RSH_INIT_ORDER);
}
-static inline int u32_cto(uint x) { return ffs(~x) - 1; }
-
-static inline u32
-rte_src_alloc_id(void)
-{
- int i, j;
- for (i = src_id_pos; i < src_id_size; i++)
- if (src_ids[i] != 0xffffffff)
- goto found;
-
- /* If we are at least 7/8 full, expand */
- if (src_id_used > (src_id_size * 28))
- {
- src_id_size *= 2;
- src_ids = mb_realloc(src_ids, src_id_size * sizeof(u32));
- bzero(src_ids + i, (src_id_size - i) * sizeof(u32));
- goto found;
- }
-
- for (i = 0; i < src_id_pos; i++)
- if (src_ids[i] != 0xffffffff)
- goto found;
-
- ASSERT(0);
-
- found:
- ASSERT(i < 0x8000000);
-
- src_id_pos = i;
- j = u32_cto(src_ids[i]);
-
- src_ids[i] |= (1 << j);
- src_id_used++;
- return 32 * i + j;
-}
-
-static inline void
-rte_src_free_id(u32 id)
-{
- int i = id / 32;
- int j = id % 32;
-
- ASSERT((i < src_id_size) && (src_ids[i] & (1 << j)));
- src_ids[i] &= ~(1 << j);
- src_id_used--;
-}
-
HASH_DEFINE_REHASH_FN(RSH, struct rte_src)
@@ -165,7 +111,7 @@ rt_get_source(struct proto *p, u32 id)
src = sl_alloc(rte_src_slab);
src->proto = p;
src->private_id = id;
- src->global_id = rte_src_alloc_id();
+ src->global_id = idm_alloc(&src_ids);
src->uc = 0;
HASH_INSERT2(src_hash, RSH, rta_pool, src);
@@ -181,7 +127,7 @@ rt_prune_sources(void)
if (src->uc == 0)
{
HASH_DO_REMOVE(src_hash, RSH, sp);
- rte_src_free_id(src->global_id);
+ idm_free(&src_ids, src->global_id);
sl_free(rte_src_slab, src);
}
}
diff --git a/nest/rt-fib.c b/nest/rt-fib.c
index c83ae171..a47ece08 100644
--- a/nest/rt-fib.c
+++ b/nest/rt-fib.c
@@ -253,7 +253,6 @@ fib_get(struct fib *f, const net_addr *a)
struct fib_node *e = fib_user_to_node(f, b);
e->readers = NULL;
e->flags = 0;
- e->uid = 0;
fib_insert(f, a, e);
memset(b, 0, f->node_offset);
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index 4ffb187d..1c128794 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -240,6 +240,8 @@ ospf_start(struct proto *P)
init_list(&(p->area_list));
fib_init(&p->rtf, P->pool, p->ospf2 ? NET_IP4 : NET_IP6,
sizeof(ort), OFFSETOF(ort, fn), 0, NULL);
+ if (ospf_is_v3(p))
+ idm_init(&p->idm, P->pool, 16);
p->areano = 0;
p->gr = ospf_top_new(p, P->pool);
s_init_list(&(p->lsal));
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index b1e02b24..3d70df7b 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -14,7 +14,7 @@
#include "nest/bird.h"
#include "lib/checksum.h"
-#include "lib/ip.h"
+#include "lib/idm.h"
#include "lib/lists.h"
#include "lib/slists.h"
#include "lib/socket.h"
@@ -79,7 +79,6 @@
#define OSPF_VLINK_ID_OFFSET 0x80000000
-
struct ospf_config
{
struct proto_config c;
@@ -215,6 +214,7 @@ struct ospf_proto
int areano; /* Number of area I belong to */
int padj; /* Number of neighbors in Exchange or Loading state */
struct fib rtf; /* Routing table */
+ struct idm idm; /* OSPFv3 LSA ID map */
byte ospf2; /* OSPF v2 or v3 */
byte rfc1583; /* RFC1583 compatibility */
byte stub_router; /* Do not forward transit traffic */
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 707e376c..21a3e300 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -2005,6 +2005,9 @@ again1:
/* Remove unused rt entry, some special entries are persistent */
if (!nf->n.type && !nf->external_rte && !nf->area_net)
{
+ if (nf->lsa_id)
+ idm_free(&p->idm, nf->lsa_id);
+
FIB_ITERATE_PUT(&fit);
fib_delete(fib, nf);
goto again1;
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
index 80243c9a..959d12e9 100644
--- a/proto/ospf/rt.h
+++ b/proto/ospf/rt.h
@@ -81,6 +81,7 @@ typedef struct ort
orta n;
u32 old_metric1, old_metric2, old_tag, old_rid;
rta *old_rta;
+ u32 lsa_id;
u8 external_rte;
u8 area_net;
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 59e76019..89bf87c7 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -513,8 +513,7 @@ ospf_update_lsadb(struct ospf_proto *p)
}
}
-
-static inline u32
+static u32
ort_to_lsaid(struct ospf_proto *p, ort *nf)
{
/*
@@ -542,14 +541,17 @@ ort_to_lsaid(struct ospf_proto *p, ort *nf)
* network appeared, we choose a different way.
*
* In OSPFv3, it is simpler. There is not a requirement for membership of the
- * result in the input network, so we just use a hash-based unique ID of a
- * routing table entry for a route that originated given LSA. For ext-LSA, it
- * is an imported route in the nest's routing table (p->table). For summary-LSA,
- * it is a 'source' route in the protocol internal routing table (p->rtf).
+ * result in the input network, so we just allocate a unique ID from ID map
+ * and store it in nf->lsa_id for further reference.
*/
if (ospf_is_v3(p))
- return nf->fn.uid;
+ {
+ if (!nf->lsa_id)
+ nf->lsa_id = idm_alloc(&p->idm);
+
+ return nf->lsa_id;
+ }
net_addr_ip4 *net = (void *) nf->fn.addr;
u32 id = ip4_to_u32(net->prefix);
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 21:39:27 +0000