Move ID allocator to a separate file and use it also in OSPF

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);