Contiki-NG
tsch-schedule.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2014, SICS Swedish ICT.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the Institute nor the names of its contributors
14  * may be used to endorse or promote products derived from this software
15  * without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * This file is part of the Contiki operating system.
30  *
31  */
32 
33 /**
34  * \file
35  * IEEE 802.15.4 TSCH MAC schedule manager.
36  * \author
37  * Simon Duquennoy <simonduq@sics.se>
38  * Beshr Al Nahas <beshr@sics.se>
39  */
40 
41 /**
42  * \addtogroup tsch
43  * @{
44 */
45 
46 #include "contiki.h"
47 #include "dev/leds.h"
48 #include "lib/memb.h"
49 #include "net/nbr-table.h"
50 #include "net/packetbuf.h"
51 #include "net/queuebuf.h"
52 #include "net/mac/tsch/tsch.h"
54 #include "sys/process.h"
55 #include "sys/rtimer.h"
56 #include <string.h>
57 
58 /* Log configuration */
59 #include "sys/log.h"
60 #define LOG_MODULE "TSCH Sched"
61 #define LOG_LEVEL LOG_LEVEL_MAC
62 
63 /* Pre-allocated space for links */
64 MEMB(link_memb, struct tsch_link, TSCH_SCHEDULE_MAX_LINKS);
65 /* Pre-allocated space for slotframes */
66 MEMB(slotframe_memb, struct tsch_slotframe, TSCH_SCHEDULE_MAX_SLOTFRAMES);
67 /* List of slotframes (each slotframe holds its own list of links) */
68 LIST(slotframe_list);
69 
70 /* Adds and returns a slotframe (NULL if failure) */
71 struct tsch_slotframe *
72 tsch_schedule_add_slotframe(uint16_t handle, uint16_t size)
73 {
74  if(size == 0) {
75  return NULL;
76  }
77 
79  /* A slotframe with this handle already exists */
80  return NULL;
81  }
82 
83  if(tsch_get_lock()) {
84  struct tsch_slotframe *sf = memb_alloc(&slotframe_memb);
85  if(sf != NULL) {
86  /* Initialize the slotframe */
87  sf->handle = handle;
88  TSCH_ASN_DIVISOR_INIT(sf->size, size);
89  LIST_STRUCT_INIT(sf, links_list);
90  /* Add the slotframe to the global list */
91  list_add(slotframe_list, sf);
92  }
93  LOG_INFO("add_slotframe %u %u\n",
94  handle, size);
96  return sf;
97  }
98  return NULL;
99 }
100 /*---------------------------------------------------------------------------*/
101 /* Removes all slotframes, resulting in an empty schedule */
102 int
104 {
105  struct tsch_slotframe *sf;
106  while((sf = list_head(slotframe_list))) {
107  if(tsch_schedule_remove_slotframe(sf) == 0) {
108  return 0;
109  }
110  }
111  return 1;
112 }
113 /*---------------------------------------------------------------------------*/
114 /* Removes a slotframe Return 1 if success, 0 if failure */
115 int
117 {
118  if(slotframe != NULL) {
119  /* Remove all links belonging to this slotframe */
120  struct tsch_link *l;
121  while((l = list_head(slotframe->links_list))) {
122  tsch_schedule_remove_link(slotframe, l);
123  }
124 
125  /* Now that the slotframe has no links, remove it. */
126  if(tsch_get_lock()) {
127  LOG_INFO("remove slotframe %u %u\n", slotframe->handle, slotframe->size.val);
128  memb_free(&slotframe_memb, slotframe);
129  list_remove(slotframe_list, slotframe);
131  return 1;
132  }
133  }
134  return 0;
135 }
136 /*---------------------------------------------------------------------------*/
137 /* Looks for a slotframe from a handle */
138 struct tsch_slotframe *
140 {
141  if(!tsch_is_locked()) {
142  struct tsch_slotframe *sf = list_head(slotframe_list);
143  while(sf != NULL) {
144  if(sf->handle == handle) {
145  return sf;
146  }
147  sf = list_item_next(sf);
148  }
149  }
150  return NULL;
151 }
152 /*---------------------------------------------------------------------------*/
153 /* Looks for a link from a handle */
154 struct tsch_link *
156 {
157  if(!tsch_is_locked()) {
158  struct tsch_slotframe *sf = list_head(slotframe_list);
159  while(sf != NULL) {
160  struct tsch_link *l = list_head(sf->links_list);
161  /* Loop over all items. Assume there is max one link per timeslot */
162  while(l != NULL) {
163  if(l->handle == handle) {
164  return l;
165  }
166  l = list_item_next(l);
167  }
168  sf = list_item_next(sf);
169  }
170  }
171  return NULL;
172 }
173 /*---------------------------------------------------------------------------*/
174 /* Adds a link to a slotframe, return a pointer to it (NULL if failure) */
175 struct tsch_link *
177  uint8_t link_options, enum link_type link_type, const linkaddr_t *address,
178  uint16_t timeslot, uint16_t channel_offset)
179 {
180  struct tsch_link *l = NULL;
181  if(slotframe != NULL) {
182  /* We currently support only one link per timeslot in a given slotframe. */
183 
184  /* Validation of specified timeslot and channel_offset */
185  if(timeslot > (slotframe->size.val - 1)) {
186  LOG_ERR("! add_link invalid timeslot: %u\n", timeslot);
187  return NULL;
188  } else if(channel_offset > 15) {
189  LOG_ERR("! add_link invalid channel_offset: %u\n", channel_offset);
190  return NULL;
191  }
192 
193  /* Start with removing the link currently installed at this timeslot (needed
194  * to keep neighbor state in sync with link options etc.) */
195  tsch_schedule_remove_link_by_timeslot(slotframe, timeslot);
196  if(!tsch_get_lock()) {
197  LOG_ERR("! add_link memb_alloc couldn't take lock\n");
198  } else {
199  l = memb_alloc(&link_memb);
200  if(l == NULL) {
201  LOG_ERR("! add_link memb_alloc failed\n");
203  } else {
204  static int current_link_handle = 0;
205  struct tsch_neighbor *n;
206  /* Add the link to the slotframe */
207  list_add(slotframe->links_list, l);
208  /* Initialize link */
209  l->handle = current_link_handle++;
210  l->link_options = link_options;
211  l->link_type = link_type;
212  l->slotframe_handle = slotframe->handle;
213  l->timeslot = timeslot;
214  l->channel_offset = channel_offset;
215  l->data = NULL;
216  if(address == NULL) {
217  address = &linkaddr_null;
218  }
219  linkaddr_copy(&l->addr, address);
220 
221  LOG_INFO("add_link %u %u %u %u %u ",
222  slotframe->handle, link_options, link_type, timeslot, channel_offset);
223  LOG_INFO_LLADDR(address);
224  LOG_INFO_("\n");
225  /* Release the lock before we update the neighbor (will take the lock) */
227 
228  if(l->link_options & LINK_OPTION_TX) {
229  n = tsch_queue_add_nbr(&l->addr);
230  /* We have a tx link to this neighbor, update counters */
231  if(n != NULL) {
232  n->tx_links_count++;
233  if(!(l->link_options & LINK_OPTION_SHARED)) {
234  n->dedicated_tx_links_count++;
235  }
236  }
237  }
238  }
239  }
240  }
241  return l;
242 }
243 /*---------------------------------------------------------------------------*/
244 /* Removes a link from slotframe. Return 1 if success, 0 if failure */
245 int
247 {
248  if(slotframe != NULL && l != NULL && l->slotframe_handle == slotframe->handle) {
249  if(tsch_get_lock()) {
250  uint8_t link_options;
251  linkaddr_t addr;
252 
253  /* Save link option and addr in local variables as we need them
254  * after freeing the link */
255  link_options = l->link_options;
256  linkaddr_copy(&addr, &l->addr);
257 
258  /* The link to be removed is scheduled as next, set it to NULL
259  * to abort the next link operation */
260  if(l == current_link) {
261  current_link = NULL;
262  }
263  LOG_INFO("remove_link %u %u %u %u ",
264  slotframe->handle, l->link_options, l->timeslot, l->channel_offset);
265  LOG_INFO_LLADDR(&l->addr);
266  LOG_INFO_("\n");
267 
268  list_remove(slotframe->links_list, l);
269  memb_free(&link_memb, l);
270 
271  /* Release the lock before we update the neighbor (will take the lock) */
273 
274  /* This was a tx link to this neighbor, update counters */
275  if(link_options & LINK_OPTION_TX) {
276  struct tsch_neighbor *n = tsch_queue_add_nbr(&addr);
277  if(n != NULL) {
278  n->tx_links_count--;
279  if(!(link_options & LINK_OPTION_SHARED)) {
280  n->dedicated_tx_links_count--;
281  }
282  }
283  }
284 
285  return 1;
286  } else {
287  LOG_ERR("! remove_link memb_alloc couldn't take lock\n");
288  }
289  }
290  return 0;
291 }
292 /*---------------------------------------------------------------------------*/
293 /* Removes a link from slotframe and timeslot. Return a 1 if success, 0 if failure */
294 int
295 tsch_schedule_remove_link_by_timeslot(struct tsch_slotframe *slotframe, uint16_t timeslot)
296 {
297  return slotframe != NULL &&
298  tsch_schedule_remove_link(slotframe, tsch_schedule_get_link_by_timeslot(slotframe, timeslot));
299 }
300 /*---------------------------------------------------------------------------*/
301 /* Looks within a slotframe for a link with a given timeslot */
302 struct tsch_link *
303 tsch_schedule_get_link_by_timeslot(struct tsch_slotframe *slotframe, uint16_t timeslot)
304 {
305  if(!tsch_is_locked()) {
306  if(slotframe != NULL) {
307  struct tsch_link *l = list_head(slotframe->links_list);
308  /* Loop over all items. Assume there is max one link per timeslot */
309  while(l != NULL) {
310  if(l->timeslot == timeslot) {
311  return l;
312  }
313  l = list_item_next(l);
314  }
315  return l;
316  }
317  }
318  return NULL;
319 }
320 /*---------------------------------------------------------------------------*/
321 /* Returns the next active link after a given ASN, and a backup link (for the same ASN, with Rx flag) */
322 struct tsch_link *
323 tsch_schedule_get_next_active_link(struct tsch_asn_t *asn, uint16_t *time_offset,
324  struct tsch_link **backup_link)
325 {
326  uint16_t time_to_curr_best = 0;
327  struct tsch_link *curr_best = NULL;
328  struct tsch_link *curr_backup = NULL; /* Keep a back link in case the current link
329  turns out useless when the time comes. For instance, for a Tx-only link, if there is
330  no outgoing packet in queue. In that case, run the backup link instead. The backup link
331  must have Rx flag set. */
332  if(!tsch_is_locked()) {
333  struct tsch_slotframe *sf = list_head(slotframe_list);
334  /* For each slotframe, look for the earliest occurring link */
335  while(sf != NULL) {
336  /* Get timeslot from ASN, given the slotframe length */
337  uint16_t timeslot = TSCH_ASN_MOD(*asn, sf->size);
338  struct tsch_link *l = list_head(sf->links_list);
339  while(l != NULL) {
340  uint16_t time_to_timeslot =
341  l->timeslot > timeslot ?
342  l->timeslot - timeslot :
343  sf->size.val + l->timeslot - timeslot;
344  if(curr_best == NULL || time_to_timeslot < time_to_curr_best) {
345  time_to_curr_best = time_to_timeslot;
346  curr_best = l;
347  curr_backup = NULL;
348  } else if(time_to_timeslot == time_to_curr_best) {
349  struct tsch_link *new_best = NULL;
350  /* Two links are overlapping, we need to select one of them.
351  * By standard: prioritize Tx links first, second by lowest handle */
352  if((curr_best->link_options & LINK_OPTION_TX) == (l->link_options & LINK_OPTION_TX)) {
353  /* Both or neither links have Tx, select the one with lowest handle */
354  if(l->slotframe_handle < curr_best->slotframe_handle) {
355  new_best = l;
356  }
357  } else {
358  /* Select the link that has the Tx option */
359  if(l->link_options & LINK_OPTION_TX) {
360  new_best = l;
361  }
362  }
363 
364  /* Maintain backup_link */
365  if(curr_backup == NULL) {
366  /* Check if 'l' best can be used as backup */
367  if(new_best != l && (l->link_options & LINK_OPTION_RX)) { /* Does 'l' have Rx flag? */
368  curr_backup = l;
369  }
370  /* Check if curr_best can be used as backup */
371  if(new_best != curr_best && (curr_best->link_options & LINK_OPTION_RX)) { /* Does curr_best have Rx flag? */
372  curr_backup = curr_best;
373  }
374  }
375 
376  /* Maintain curr_best */
377  if(new_best != NULL) {
378  curr_best = new_best;
379  }
380  }
381 
382  l = list_item_next(l);
383  }
384  sf = list_item_next(sf);
385  }
386  if(time_offset != NULL) {
387  *time_offset = time_to_curr_best;
388  }
389  }
390  if(backup_link != NULL) {
391  *backup_link = curr_backup;
392  }
393  return curr_best;
394 }
395 /*---------------------------------------------------------------------------*/
396 /* Module initialization, call only once at startup. Returns 1 is success, 0 if failure. */
397 int
399 {
400  if(tsch_get_lock()) {
401  memb_init(&link_memb);
402  memb_init(&slotframe_memb);
403  list_init(slotframe_list);
405  return 1;
406  } else {
407  return 0;
408  }
409 }
410 /*---------------------------------------------------------------------------*/
411 /* Create a 6TiSCH minimal schedule */
412 void
414 {
415  struct tsch_slotframe *sf_min;
416  /* First, empty current schedule */
418  /* Build 6TiSCH minimal schedule.
419  * We pick a slotframe length of TSCH_SCHEDULE_DEFAULT_LENGTH */
420  sf_min = tsch_schedule_add_slotframe(0, TSCH_SCHEDULE_DEFAULT_LENGTH);
421  /* Add a single Tx|Rx|Shared slot using broadcast address (i.e. usable for unicast and broadcast).
422  * We set the link type to advertising, which is not compliant with 6TiSCH minimal schedule
423  * but is required according to 802.15.4e if also used for EB transmission.
424  * Timeslot: 0, channel offset: 0. */
425  tsch_schedule_add_link(sf_min,
426  (LINK_OPTION_RX | LINK_OPTION_TX | LINK_OPTION_SHARED | LINK_OPTION_TIME_KEEPING),
427  LINK_TYPE_ADVERTISING, &tsch_broadcast_address,
428  0, 0);
429 }
430 /*---------------------------------------------------------------------------*/
431 struct tsch_slotframe *
433 {
434  return list_head(slotframe_list);
435 }
436 /*---------------------------------------------------------------------------*/
437 struct tsch_slotframe *
439 {
440  return list_item_next(sf);
441 }
442 /*---------------------------------------------------------------------------*/
443 /* Prints out the current schedule (all slotframes and links) */
444 void
446 {
447  if(!tsch_is_locked()) {
448  struct tsch_slotframe *sf = list_head(slotframe_list);
449 
450  LOG_PRINT("----- start slotframe list -----\n");
451 
452  while(sf != NULL) {
453  struct tsch_link *l = list_head(sf->links_list);
454 
455  LOG_PRINT("Slotframe Handle %u, size %u\n", sf->handle, sf->size.val);
456 
457  while(l != NULL) {
458  LOG_PRINT("* Link Options %02x, type %u, timeslot %u, channel offset %u, address %u\n",
459  l->link_options, l->link_type, l->timeslot, l->channel_offset, l->addr.u8[7]);
460  l = list_item_next(l);
461  }
462 
463  sf = list_item_next(sf);
464  }
465 
466  LOG_PRINT("----- end slotframe list -----\n");
467  }
468 }
469 /*---------------------------------------------------------------------------*/
470 /** @} */
#define TSCH_ASN_DIVISOR_INIT(div, val_)
Initialize a struct asn_divisor_t.
Definition: tsch-asn.h:86
#define LIST_STRUCT_INIT(struct_ptr, name)
Initialize a linked list that is part of a structure.
Definition: list.h:124
struct tsch_slotframe * tsch_schedule_slotframe_next(struct tsch_slotframe *sf)
Access the next item in the list of slotframes.
static uip_ds6_addr_t * addr
Pointer to a nbr cache entry.
Definition: uip-nd6.c:115
int tsch_schedule_init(void)
Module initialization, call only once at init.
int tsch_get_lock(void)
Takes the TSCH lock.
void tsch_release_lock(void)
Releases the TSCH lock.
TSCH neighbor information.
Definition: tsch-types.h:109
802.15.4e slotframe (contains links)
Definition: tsch-types.h:84
struct tsch_slotframe * tsch_schedule_add_slotframe(uint16_t handle, uint16_t size)
Creates and adds a new slotframe.
Definition: tsch-schedule.c:72
struct tsch_link * tsch_schedule_get_link_by_timeslot(struct tsch_slotframe *slotframe, uint16_t timeslot)
Looks within a slotframe for a link with a given timeslot.
const linkaddr_t linkaddr_null
The null link-layer address.
struct tsch_slotframe * tsch_schedule_get_slotframe_by_handle(uint16_t handle)
Looks up a slotframe by handle.
struct tsch_neighbor * tsch_queue_add_nbr(const linkaddr_t *addr)
Add a TSCH neighbor queue.
Definition: tsch-queue.c:80
Header file for the Packet queue buffer management
struct tsch_link * tsch_schedule_get_next_active_link(struct tsch_asn_t *asn, uint16_t *time_offset, struct tsch_link **backup_link)
Returns the next active link after a given ASN, and a backup link (for the same ASN, with Rx flag)
void tsch_schedule_print(void)
Prints out the current schedule (all slotframes and links)
void * list_head(list_t list)
Get a pointer to the first element of a list.
Definition: list.c:82
Header file for the real-time timer module.
#define TSCH_ASN_MOD(asn, div)
Returns the result (16 bits) of a modulo operation on ASN, with divisor being a struct asn_divisor_t...
Definition: tsch-asn.h:93
int tsch_schedule_remove_link_by_timeslot(struct tsch_slotframe *slotframe, uint16_t timeslot)
Removes a link from a slotframe and timeslot.
Header file for the Contiki process interface.
Main API declarations for TSCH.
int tsch_schedule_remove_link(struct tsch_slotframe *slotframe, struct tsch_link *l)
Removes a link.
struct tsch_link * tsch_schedule_add_link(struct tsch_slotframe *slotframe, uint8_t link_options, enum link_type link_type, const linkaddr_t *address, uint16_t timeslot, uint16_t channel_offset)
Adds a link to a slotframe.
802.15.4 frame creation and parsing functions
Memory block allocation routines.
int tsch_is_locked(void)
Checks if the TSCH lock is set.
struct tsch_slotframe * tsch_schedule_slotframe_head(void)
Access the first item in the list of slotframes.
link_type
802.15.4e link types.
Definition: tsch-types.h:54
void linkaddr_copy(linkaddr_t *dest, const linkaddr_t *src)
Copy a link-layer address.
Definition: linkaddr.c:63
int tsch_schedule_remove_slotframe(struct tsch_slotframe *slotframe)
Removes a slotframe.
void list_add(list_t list, void *item)
Add an item at the end of a list.
Definition: list.c:142
void list_init(list_t list)
Initialize a list.
Definition: list.c:65
#define LIST(name)
Declare a linked list.
Definition: list.h:88
int tsch_schedule_remove_all_slotframes(void)
Removes all slotframes, resulting in an empty schedule.
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
Definition: memb.c:59
struct tsch_link * tsch_schedule_get_link_by_handle(uint16_t handle)
Looks for a link from a handle.
Header file for the Packet buffer (packetbuf) management
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
Definition: memb.c:52
char memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
Definition: memb.c:79
Header file for the logging system
Header file for the LED HAL.
The ASN is an absolute slot number over 5 bytes.
Definition: tsch-asn.h:48
void list_remove(list_t list, void *item)
Remove a specific element from a list.
Definition: list.c:237
void tsch_schedule_create_minimal(void)
Create a 6tisch minimal schedule with length TSCH_SCHEDULE_DEFAULT_LENGTH.
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