Contiki-NG
nbr-table.c
1 /*
2  * Copyright (c) 2013, Swedish Institute of Computer Science
3  * Copyright (c) 2010, Vrije Universiteit Brussel
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution.
14  * 3. Neither the name of the Institute nor the names of its contributors
15  * may be used to endorse or promote products derived from this software
16  * without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28  * SUCH DAMAGE.
29  *
30  *
31  * Authors: Simon Duquennoy <simonduq@sics.se>
32  * Joris Borms <joris.borms@vub.ac.be>
33  */
34 
35 #include "contiki.h"
36 
37 #include <stddef.h>
38 #include <string.h>
39 #include "lib/memb.h"
40 #include "lib/list.h"
41 #include "net/nbr-table.h"
42 
43 #define DEBUG 0
44 #if DEBUG
45 #include <stdio.h>
46 #include "sys/ctimer.h"
47 static void handle_periodic_timer(void *ptr);
48 static struct ctimer periodic_timer;
49 static uint8_t initialized = 0;
50 static void print_table();
51 #define PRINTF(...) printf(__VA_ARGS__)
52 #else
53 #define PRINTF(...)
54 #endif
55 
56 /* This is the callback function that will be called when there is a
57  * nbr-policy active
58  **/
59 #ifdef NBR_TABLE_FIND_REMOVABLE
60 const linkaddr_t *NBR_TABLE_FIND_REMOVABLE(nbr_table_reason_t reason, void *data);
61 #endif /* NBR_TABLE_FIND_REMOVABLE */
62 
63 
64 /* List of link-layer addresses of the neighbors, used as key in the tables */
65 typedef struct nbr_table_key {
66  struct nbr_table_key *next;
67  linkaddr_t lladdr;
68 } nbr_table_key_t;
69 
70 /* For each neighbor, a map of the tables that use the neighbor.
71  * As we are using uint8_t, we have a maximum of 8 tables in the system */
72 static uint8_t used_map[NBR_TABLE_MAX_NEIGHBORS];
73 /* For each neighbor, a map of the tables that lock the neighbor */
74 static uint8_t locked_map[NBR_TABLE_MAX_NEIGHBORS];
75 /* The maximum number of tables */
76 #define MAX_NUM_TABLES 8
77 /* A list of pointers to tables in use */
78 static struct nbr_table *all_tables[MAX_NUM_TABLES];
79 /* The current number of tables */
80 static unsigned num_tables;
81 
82 /* The neighbor address table */
83 MEMB(neighbor_addr_mem, nbr_table_key_t, NBR_TABLE_MAX_NEIGHBORS);
84 LIST(nbr_table_keys);
85 
86 /*---------------------------------------------------------------------------*/
87 /* Get a key from a neighbor index */
88 static nbr_table_key_t *
89 key_from_index(int index)
90 {
91  return index != -1 ? &((nbr_table_key_t *)neighbor_addr_mem.mem)[index] : NULL;
92 }
93 /*---------------------------------------------------------------------------*/
94 /* Get an item from its neighbor index */
95 static nbr_table_item_t *
96 item_from_index(nbr_table_t *table, int index)
97 {
98  return table != NULL && index != -1 ? (char *)table->data + index * table->item_size : NULL;
99 }
100 /*---------------------------------------------------------------------------*/
101 /* Get the neighbor index of an item */
102 static int
103 index_from_key(nbr_table_key_t *key)
104 {
105  return key != NULL ? key - (nbr_table_key_t *)neighbor_addr_mem.mem : -1;
106 }
107 /*---------------------------------------------------------------------------*/
108 /* Get the neighbor index of an item */
109 static int
110 index_from_item(nbr_table_t *table, const nbr_table_item_t *item)
111 {
112  return table != NULL && item != NULL ? ((int)((char *)item - (char *)table->data)) / table->item_size : -1;
113 }
114 /*---------------------------------------------------------------------------*/
115 /* Get an item from its key */
116 static nbr_table_item_t *
117 item_from_key(nbr_table_t *table, nbr_table_key_t *key)
118 {
119  return item_from_index(table, index_from_key(key));
120 }
121 /*---------------------------------------------------------------------------*/
122 /* Get the key af an item */
123 static nbr_table_key_t *
124 key_from_item(nbr_table_t *table, const nbr_table_item_t *item)
125 {
126  return key_from_index(index_from_item(table, item));
127 }
128 /*---------------------------------------------------------------------------*/
129 /* Get the index of a neighbor from its link-layer address */
130 static int
131 index_from_lladdr(const linkaddr_t *lladdr)
132 {
133  nbr_table_key_t *key;
134  /* Allow lladdr-free insertion, useful e.g. for IPv6 ND.
135  * Only one such entry is possible at a time, indexed by linkaddr_null. */
136  if(lladdr == NULL) {
137  lladdr = &linkaddr_null;
138  }
139  key = list_head(nbr_table_keys);
140  while(key != NULL) {
141  if(lladdr && linkaddr_cmp(lladdr, &key->lladdr)) {
142  return index_from_key(key);
143  }
144  key = list_item_next(key);
145  }
146  return -1;
147 }
148 /*---------------------------------------------------------------------------*/
149 /* Get bit from "used" or "locked" bitmap */
150 static int
151 nbr_get_bit(uint8_t *bitmap, nbr_table_t *table, nbr_table_item_t *item)
152 {
153  int item_index = index_from_item(table, item);
154  if(table != NULL && item_index != -1) {
155  return (bitmap[item_index] & (1 << table->index)) != 0;
156  } else {
157  return 0;
158  }
159  return 0;
160 }
161 /*---------------------------------------------------------------------------*/
162 /* Set bit in "used" or "locked" bitmap */
163 static int
164 nbr_set_bit(uint8_t *bitmap, nbr_table_t *table, nbr_table_item_t *item, int value)
165 {
166  int item_index = index_from_item(table, item);
167 
168  if(table != NULL && item_index != -1) {
169  if(value) {
170  bitmap[item_index] |= 1 << table->index;
171  } else {
172  bitmap[item_index] &= ~(1 << table->index);
173  }
174  return 1;
175  } else {
176  return 0;
177  }
178  return 0;
179 }
180 /*---------------------------------------------------------------------------*/
181 static void
182 remove_key(nbr_table_key_t *least_used_key)
183 {
184  int i;
185  for(i = 0; i < MAX_NUM_TABLES; i++) {
186  if(all_tables[i] != NULL && all_tables[i]->callback != NULL) {
187  /* Call table callback for each table that uses this item */
188  nbr_table_item_t *removed_item = item_from_key(all_tables[i], least_used_key);
189  if(nbr_get_bit(used_map, all_tables[i], removed_item) == 1) {
190  all_tables[i]->callback(removed_item);
191  }
192  }
193  }
194  /* Empty used map */
195  used_map[index_from_key(least_used_key)] = 0;
196  /* Remove neighbor from list */
197  list_remove(nbr_table_keys, least_used_key);
198 }
199 /*---------------------------------------------------------------------------*/
200 static nbr_table_key_t *
201 nbr_table_allocate(nbr_table_reason_t reason, void *data)
202 {
203  nbr_table_key_t *key;
204  int least_used_count = 0;
205  nbr_table_key_t *least_used_key = NULL;
206 
207  key = memb_alloc(&neighbor_addr_mem);
208  if(key != NULL) {
209  return key;
210  } else {
211 #ifdef NBR_TABLE_FIND_REMOVABLE
212  const linkaddr_t *lladdr;
213  lladdr = NBR_TABLE_FIND_REMOVABLE(reason, data);
214  if(lladdr == NULL) {
215  /* Nothing found that can be deleted - return NULL to indicate failure */
216  PRINTF("*** Not removing entry to allocate new\n");
217  return NULL;
218  } else {
219  /* used least_used_key to indicate what is the least useful entry */
220  int index;
221  int locked = 0;
222  if((index = index_from_lladdr(lladdr)) != -1) {
223  least_used_key = key_from_index(index);
224  locked = locked_map[index];
225  }
226  /* Allow delete of locked item? */
227  if(least_used_key != NULL && locked) {
228  PRINTF("Deleting locked item!\n");
229  locked_map[index] = 0;
230  }
231  }
232 #endif /* NBR_TABLE_FIND_REMOVABLE */
233 
234  if(least_used_key == NULL) {
235  /* No more space, try to free a neighbor.
236  * The replacement policy is the following: remove neighbor that is:
237  * (1) not locked
238  * (2) used by fewest tables
239  * (3) oldest (the list is ordered by insertion time)
240  * */
241  /* Get item from first key */
242  key = list_head(nbr_table_keys);
243  while(key != NULL) {
244  int item_index = index_from_key(key);
245  int locked = locked_map[item_index];
246  /* Never delete a locked item */
247  if(!locked) {
248  int used = used_map[item_index];
249  int used_count = 0;
250  /* Count how many tables are using this item */
251  while(used != 0) {
252  if((used & 1) == 1) {
253  used_count++;
254  }
255  used >>= 1;
256  }
257  /* Find least used item */
258  if(least_used_key == NULL || used_count < least_used_count) {
259  least_used_key = key;
260  least_used_count = used_count;
261  if(used_count == 0) { /* We won't find any least used item */
262  break;
263  }
264  }
265  }
266  key = list_item_next(key);
267  }
268  }
269 
270  if(least_used_key == NULL) {
271  /* We haven't found any unlocked item, allocation fails */
272  return NULL;
273  } else {
274  /* Reuse least used item */
275  remove_key(least_used_key);
276  return least_used_key;
277  }
278  }
279 }
280 /*---------------------------------------------------------------------------*/
281 /* Register a new neighbor table. To be used at initialization by modules
282  * using a neighbor table */
283 int
284 nbr_table_register(nbr_table_t *table, nbr_table_callback *callback)
285 {
286 #if DEBUG
287  if(!initialized) {
288  initialized = 1;
289  /* schedule a debug printout per minute */
290  ctimer_set(&periodic_timer, CLOCK_SECOND * 60, handle_periodic_timer, NULL);
291  }
292 #endif
293 
294  if(nbr_table_is_registered(table)) {
295  /* Table already registered, just update callback */
296  table->callback = callback;
297  return 1;
298  }
299 
300  if(num_tables < MAX_NUM_TABLES) {
301  table->index = num_tables++;
302  table->callback = callback;
303  all_tables[table->index] = table;
304  return 1;
305  } else {
306  /* Maximum number of tables exceeded */
307  return 0;
308  }
309 }
310 /*---------------------------------------------------------------------------*/
311 /* Test whether a specified table has been registered or not */
312 int
313 nbr_table_is_registered(nbr_table_t *table)
314 {
315  if(table != NULL && table->index >= 0 && table->index < MAX_NUM_TABLES
316  && all_tables[table->index] == table) {
317  return 1;
318  }
319  return 0;
320 }
321 /*---------------------------------------------------------------------------*/
322 /* Returns the first item of the current table */
323 nbr_table_item_t *
324 nbr_table_head(nbr_table_t *table)
325 {
326  /* Get item from first key */
327  nbr_table_item_t *item = item_from_key(table, list_head(nbr_table_keys));
328  /* Item is the first neighbor, now check is it is in the current table */
329  if(nbr_get_bit(used_map, table, item)) {
330  return item;
331  } else {
332  return nbr_table_next(table, item);
333  }
334 }
335 /*---------------------------------------------------------------------------*/
336 /* Iterates over the current table */
337 nbr_table_item_t *
338 nbr_table_next(nbr_table_t *table, nbr_table_item_t *item)
339 {
340  do {
341  void *key = key_from_item(table, item);
342  key = list_item_next(key);
343  /* Loop until the next item is in the current table */
344  item = item_from_key(table, key);
345  } while(item && !nbr_get_bit(used_map, table, item));
346  return item;
347 }
348 /*---------------------------------------------------------------------------*/
349 /* Add a neighbor indexed with its link-layer address */
350 nbr_table_item_t *
351 nbr_table_add_lladdr(nbr_table_t *table, const linkaddr_t *lladdr, nbr_table_reason_t reason, void *data)
352 {
353  int index;
354  nbr_table_item_t *item;
355  nbr_table_key_t *key;
356 
357  /* Allow lladdr-free insertion, useful e.g. for IPv6 ND.
358  * Only one such entry is possible at a time, indexed by linkaddr_null. */
359  if(lladdr == NULL) {
360  lladdr = &linkaddr_null;
361  }
362 
363  if((index = index_from_lladdr(lladdr)) == -1) {
364  /* Neighbor not yet in table, let's try to allocate one */
365  key = nbr_table_allocate(reason, data);
366 
367  /* No space available for new entry */
368  if(key == NULL) {
369  return NULL;
370  }
371 
372  /* Add neighbor to list */
373  list_add(nbr_table_keys, key);
374 
375  /* Get index from newly allocated neighbor */
376  index = index_from_key(key);
377 
378  /* Set link-layer address */
379  linkaddr_copy(&key->lladdr, lladdr);
380  }
381 
382  /* Get item in the current table */
383  item = item_from_index(table, index);
384 
385  /* Initialize item data and set "used" bit */
386  memset(item, 0, table->item_size);
387  nbr_set_bit(used_map, table, item, 1);
388 
389 #if DEBUG
390  print_table();
391 #endif
392  return item;
393 }
394 /*---------------------------------------------------------------------------*/
395 /* Get an item from its link-layer address */
396 void *
397 nbr_table_get_from_lladdr(nbr_table_t *table, const linkaddr_t *lladdr)
398 {
399  void *item = item_from_index(table, index_from_lladdr(lladdr));
400  return nbr_get_bit(used_map, table, item) ? item : NULL;
401 }
402 /*---------------------------------------------------------------------------*/
403 /* Removes a neighbor from the current table (unset "used" bit) */
404 int
405 nbr_table_remove(nbr_table_t *table, void *item)
406 {
407  int ret = nbr_set_bit(used_map, table, item, 0);
408  nbr_set_bit(locked_map, table, item, 0);
409  return ret;
410 }
411 /*---------------------------------------------------------------------------*/
412 /* Lock a neighbor for the current table (set "locked" bit) */
413 int
414 nbr_table_lock(nbr_table_t *table, void *item)
415 {
416 #if DEBUG
417  int i = index_from_item(table, item);
418  PRINTF("*** Lock %d\n", i);
419 #endif
420  return nbr_set_bit(locked_map, table, item, 1);
421 }
422 /*---------------------------------------------------------------------------*/
423 /* Release the lock on a neighbor for the current table (unset "locked" bit) */
424 int
425 nbr_table_unlock(nbr_table_t *table, void *item)
426 {
427 #if DEBUG
428  int i = index_from_item(table, item);
429  PRINTF("*** Unlock %d\n", i);
430 #endif
431  return nbr_set_bit(locked_map, table, item, 0);
432 }
433 /*---------------------------------------------------------------------------*/
434 /* Get link-layer address of an item */
435 linkaddr_t *
436 nbr_table_get_lladdr(nbr_table_t *table, const void *item)
437 {
438  nbr_table_key_t *key = key_from_item(table, item);
439  return key != NULL ? &key->lladdr : NULL;
440 }
441 /*---------------------------------------------------------------------------*/
442 #if DEBUG
443 static void
444 print_table()
445 {
446  int i, j;
447  /* Printout all neighbors and which tables they are used in */
448  PRINTF("NBR TABLE:\n");
449  for(i = 0; i < NBR_TABLE_MAX_NEIGHBORS; i++) {
450  if(used_map[i] > 0) {
451  PRINTF(" %02d %02d",i , key_from_index(i)->lladdr.u8[LINKADDR_SIZE - 1]);
452  for(j = 0; j < num_tables; j++) {
453  PRINTF(" [%d:%d]", (used_map[i] & (1 << j)) != 0,
454  (locked_map[i] & (1 << j)) != 0);
455  }
456  PRINTF("\n");
457  }
458  }
459 }
460 /*---------------------------------------------------------------------------*/
461 static void
462 handle_periodic_timer(void *ptr)
463 {
464  print_table();
465  ctimer_reset(&periodic_timer);
466 }
467 #endif
void ctimer_reset(struct ctimer *c)
Reset a callback timer with the same interval as was previously set.
Definition: ctimer.c:125
const linkaddr_t linkaddr_null
The null link-layer address.
#define CLOCK_SECOND
A second, measured in system clock time.
Definition: clock.h:82
Header file for the callback timer
Linked list manipulation routines.
void * list_head(list_t list)
Get a pointer to the first element of a list.
Definition: list.c:82
void ctimer_set(struct ctimer *c, clock_time_t t, void(*f)(void *), void *ptr)
Set a callback timer.
Definition: ctimer.c:99
Memory block allocation routines.
void linkaddr_copy(linkaddr_t *dest, const linkaddr_t *src)
Copy a link-layer address.
Definition: linkaddr.c:63
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:142
int linkaddr_cmp(const linkaddr_t *addr1, const linkaddr_t *addr2)
Compare two link-layer addresses.
Definition: linkaddr.c:69
#define LIST(name)
Declare a linked list.
Definition: list.h:88
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition: memb.c:59
void list_remove(list_t list, void *item)
Remove a specific element from a list.
Definition: list.c:237
void * list_item_next(void *item)
Get the next item following this item.
Definition: list.c:322
#define MEMB(name, structure, num)
Declare a memory block.
Definition: memb.h:89