Revision 74c838a8

View differences:

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