Revision 094d2bdb nest/rt-attr.c

View differences:

nest/rt-attr.c
58 58

  
59 59
static slab *rta_slab;
60 60
static slab *mpnh_slab;
61
static slab *rte_src_slab;
62

  
63
/* rte source ID bitmap */
64
static u32 *src_ids;
65
static u32 src_id_size, src_id_used, src_id_pos;
66
#define SRC_ID_SIZE_DEF 4
67

  
68
/* rte source hash */
69
static struct rte_src **src_table;
70
static u32 src_hash_order, src_hash_size, src_hash_count;
71
#define SRC_HASH_ORDER_DEF 6
72
#define SRC_HASH_ORDER_MAX 18
73
#define SRC_HASH_ORDER_MIN 10
61 74

  
62 75
struct protocol *attr_class_to_protocol[EAP_MAX];
63 76

  
77

  
78
static void
79
rte_src_init(void)
80
{
81
  rte_src_slab = sl_new(rta_pool, sizeof(struct rte_src));
82

  
83
  src_id_pos = 0;
84
  src_id_size = SRC_ID_SIZE_DEF;
85
  src_ids = mb_allocz(rta_pool, src_id_size * sizeof(u32));
86

  
87
 /* ID 0 is reserved */
88
  src_ids[0] = 1;
89
  src_id_used = 1;
90

  
91
  src_hash_count = 0;
92
  src_hash_order = SRC_HASH_ORDER_DEF;
93
  src_hash_size = 1 << src_hash_order;
94
  src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
95
}
96

  
97
static inline int u32_cto(unsigned int x) { return ffs(~x) - 1; }
98

  
99
static inline u32
100
rte_src_alloc_id(void)
101
{
102
  int i, j;
103
  for (i = src_id_pos; i < src_id_size; i++)
104
    if (src_ids[i] != 0xffffffff)
105
      goto found;
106

  
107
  /* If we are at least 7/8 full, expand */
108
  if (src_id_used > (src_id_size * 28))
109
    {
110
      src_id_size *= 2;
111
      src_ids = mb_realloc(rta_pool, src_ids, src_id_size * sizeof(u32));
112
      bzero(src_ids + i, (src_id_size - i) * sizeof(u32));
113
      goto found;
114
    }
115

  
116
  for (i = 0; i < src_id_pos; i++)
117
    if (src_ids[i] != 0xffffffff)
118
      goto found;
119

  
120
  ASSERT(0);
121

  
122
 found:
123
  ASSERT(i < 0x8000000);
124

  
125
  src_id_pos = i;
126
  j = u32_cto(src_ids[i]);
127

  
128
  src_ids[i] |= (1 << j);
129
  src_id_used++;
130
  return 32 * i + j;
131
}
132

  
133
static inline void
134
rte_src_free_id(u32 id)
135
{
136
  int i = id / 32;
137
  int j = id % 32;
138

  
139
  ASSERT((i < src_id_size) && (src_ids[i] & (1 << j)));
140
  src_ids[i] &= ~(1 << j);
141
  src_id_used--;
142
}
143

  
144
static inline u32 rte_src_hash(struct proto *p, u32 x, u32 order)
145
{ return (x * 2902958171u) >> (32 - order); }
146

  
147
static void
148
rte_src_rehash(int step)
149
{
150
  struct rte_src **old_tab, *src, *src_next;
151
  u32 old_size, hash, i;
152

  
153
  old_tab = src_table;
154
  old_size = src_hash_size;
155

  
156
  src_hash_order += step;
157
  src_hash_size = 1 << src_hash_order;
158
  src_table = mb_allocz(rta_pool, src_hash_size * sizeof(struct rte_src *));
159
  
160
  for (i = 0; i < old_size; i++)
161
    for (src = old_tab[i]; src; src = src_next)
162
      {
163
	src_next = src->next;
164
	hash = rte_src_hash(src->proto, src->private_id, src_hash_order);
165
	src->next = src_table[hash];
166
	src_table[hash] = src;
167
      }
168

  
169
  mb_free(old_tab);
170
}
171

  
172
struct rte_src *
173
rt_find_source(struct proto *p, u32 id)
174
{
175
  struct rte_src *src;
176
  u32 hash = rte_src_hash(p, id, src_hash_order);
177

  
178
  for (src = src_table[hash]; src; src = src->next)
179
    if ((src->proto == p) && (src->private_id == id))
180
      return src;
181

  
182
  return NULL;
183
}
184

  
185
struct rte_src *
186
rt_get_source(struct proto *p, u32 id)
187
{
188
  struct rte_src *src;
189
  u32 hash = rte_src_hash(p, id, src_hash_order);
190

  
191
  for (src = src_table[hash]; src; src = src->next)
192
    if ((src->proto == p) && (src->private_id == id))
193
      return src;
194

  
195
  src = sl_alloc(rte_src_slab);
196
  src->proto = p;
197
  src->private_id = id;
198
  src->global_id = rte_src_alloc_id();
199
  src->uc = 0;
200

  
201
  src->next = src_table[hash];
202
  src_table[hash] = src;
203

  
204
  src_hash_count++;
205
  if ((src_hash_count > src_hash_size) && (src_hash_order < SRC_HASH_ORDER_MAX))
206
    rte_src_rehash(1);
207

  
208
  return src;
209
}
210

  
211
static inline void
212
rt_remove_source(struct rte_src **sp)
213
{
214
  struct rte_src *src = *sp;
215

  
216
  *sp = src->next;
217
  rte_src_free_id(src->global_id);
218
  sl_free(rte_src_slab, src);
219
  src_hash_count--;
220
}
221

  
222
void
223
rt_prune_sources(void)
224
{
225
  struct rte_src **sp;
226
  int i;
227
  
228
  for (i = 0; i < src_hash_size; i++)
229
    {
230
      sp = &src_table[i];
231
      while (*sp)
232
	{
233
	  if ((*sp)->uc == 0)
234
	    rt_remove_source(sp);
235
	  else
236
	    sp = &(*sp)->next;
237
	}
238
    }
239

  
240
  while ((src_hash_count < (src_hash_size / 4)) && (src_hash_order > SRC_HASH_ORDER_MIN))
241
    rte_src_rehash(-1);
242
}
243

  
244

  
245
/*
246
 *	Multipath Next Hop
247
 */
248

  
64 249
static inline unsigned int
65 250
mpnh_hash(struct mpnh *x)
66 251
{
......
682 867
static inline unsigned int
683 868
rta_hash(rta *a)
684 869
{
685
  return (a->proto->hash_key ^ ipa_hash(a->gw) ^
870
  return (((unsigned) a->src) ^ ipa_hash(a->gw) ^
686 871
	  mpnh_hash(a->nexthops) ^ ea_hash(a->eattrs)) & 0xffff;
687 872
}
688 873

  
689 874
static inline int
690 875
rta_same(rta *x, rta *y)
691 876
{
692
  return (x->proto == y->proto &&
877
  return (x->src == y->src &&
693 878
	  x->source == y->source &&
694 879
	  x->scope == y->scope &&
695 880
	  x->cast == y->cast &&
......
786 971
  r = rta_copy(o);
787 972
  r->hash_key = h;
788 973
  r->aflags = RTAF_CACHED;
974
  rt_lock_source(r->src);
789 975
  rt_lock_hostentry(r->hostentry);
790 976
  rta_insert(r);
791 977

  
......
805 991
    a->next->pprev = a->pprev;
806 992
  a->aflags = 0;		/* Poison the entry */
807 993
  rt_unlock_hostentry(a->hostentry);
994
  rt_unlock_source(a->src);
808 995
  mpnh_free(a->nexthops);
809 996
  ea_free(a->eattrs);
810 997
  sl_free(rta_slab, a);
......
827 1014
  static char *rtd[] = { "", " DEV", " HOLE", " UNREACH", " PROHIBIT" };
828 1015

  
829 1016
  debug("p=%s uc=%d %s %s%s%s h=%04x",
830
	a->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
1017
	a->src->proto->name, a->uc, rts[a->source], ip_scope_text(a->scope), rtc[a->cast],
831 1018
	rtd[a->dest], a->hash_key);
832 1019
  if (!(a->aflags & RTAF_CACHED))
833 1020
    debug(" !CACHED");
......
895 1082
  rta_slab = sl_new(rta_pool, sizeof(rta));
896 1083
  mpnh_slab = sl_new(rta_pool, sizeof(struct mpnh));
897 1084
  rta_alloc_hash();
1085
  rte_src_init();
898 1086
}
899 1087

  
900 1088
/*

Also available in: Unified diff