54#include "lib/random.h"
57#include "net/nbr-table.h"
62#define LOG_MODULE "TSCH Queue"
63#define LOG_LEVEL LOG_LEVEL_MAC
66#if (TSCH_QUEUE_NUM_PER_NEIGHBOR & (TSCH_QUEUE_NUM_PER_NEIGHBOR - 1)) != 0
67#error TSCH_QUEUE_NUM_PER_NEIGHBOR must be power of two
89 n = (
struct tsch_neighbor *)nbr_table_add_lladdr(tsch_neighbors,
addr, NBR_TABLE_REASON_MAC, NULL);
94 nbr_table_lock(tsch_neighbors, n);
124 while(curr_nbr != NULL) {
125 if(curr_nbr->is_time_source) {
128 curr_nbr = (
struct tsch_neighbor *)nbr_table_next(tsch_neighbors, curr_nbr);
137 return nbr_table_get_lladdr(tsch_neighbors, n);
145 if(!tsch_is_coordinator) {
149 if(new_addr != NULL) {
152 if(new_time_src == NULL) {
157 if(new_time_src != old_time_src) {
158 LOG_INFO(
"update time source: ");
165 if(new_time_src != NULL) {
166 new_time_src->is_time_source = 1;
174 if(old_time_src != NULL) {
175 old_time_src->is_time_source = 0;
178 tsch_stats_reset_neighbor_stats();
180#ifdef TSCH_CALLBACK_NEW_TIME_SOURCE
181 TSCH_CALLBACK_NEW_TIME_SOURCE(old_time_src, new_time_src);
200 LOG_WARN(
"! flushing packet\n");
202 mac_call_sent_callback(p->sent, p->ptr, p->ret, p->transmissions);
219 tsch_queue_flush_nbr_queue(n);
222 nbr_table_remove(tsch_neighbors, n);
230 mac_callback_t sent,
void *ptr)
233 int16_t put_index = -1;
236#ifdef TSCH_CALLBACK_PACKET_READY
238 if(TSCH_CALLBACK_PACKET_READY() < 0) {
240 LOG_DBG(
"tsch_queue_add_packet(): rejected by the scheduler\n");
249 if(put_index != -1) {
253 p->qb = queuebuf_new_from_packetbuf();
258 p->transmissions = 0;
259 p->max_transmissions = max_transmissions;
261 n->tx_array[put_index] = p;
263 LOG_DBG(
"packet is added put_index %u, packet %p\n",
273 LOG_ERR(
"! add packet failed: %u %p %d %p %p\n",
tsch_is_locked(), n, put_index, p, p ? p->qb : NULL);
302 if(get_index != -1) {
303 return n->tx_array[get_index];
317 queuebuf_free(p->qb);
330 tsch_queue_flush_nbr_queue(n);
338 struct tsch_link *link, uint8_t mac_tx_status)
341 int is_shared_link = link->link_options & LINK_OPTION_SHARED;
342 int is_unicast = !n->is_broadcast;
359 if(p->transmissions >= p->max_transmissions) {
388 tsch_queue_flush_nbr_queue(n);
407 if(!n->is_broadcast && !n->is_time_source && !n->tx_links_count
409 tsch_queue_remove_nbr(n);
428 int is_shared_link = link != NULL && link->link_options & LINK_OPTION_SHARED;
431 if(get_index != -1 &&
434#if TSCH_WITH_LINK_SELECTOR
435 int packet_attr_slotframe = queuebuf_attr(n->tx_array[get_index]->qb, PACKETBUF_ATTR_TSCH_SLOTFRAME);
436 int packet_attr_timeslot = queuebuf_attr(n->tx_array[get_index]->qb, PACKETBUF_ATTR_TSCH_TIMESLOT);
437 if(packet_attr_slotframe != 0xffff && packet_attr_slotframe != link->slotframe_handle) {
440 if(packet_attr_timeslot != 0xffff && packet_attr_timeslot != link->timeslot) {
444 return n->tx_array[get_index];
469 while(curr_nbr != NULL) {
470 if(!curr_nbr->is_broadcast && curr_nbr->tx_links_count == 0) {
480 curr_nbr = (
struct tsch_neighbor *)nbr_table_next(tsch_neighbors, curr_nbr);
490 return n->backoff_window == 0;
497 n->backoff_window = 0;
498 n->backoff_exponent = TSCH_MAC_MIN_BE;
506 n->backoff_exponent = MIN(n->backoff_exponent + 1, TSCH_MAC_MAX_BE);
510 n->backoff_window = (
random_rand() >> 6) % (1ul << n->backoff_exponent);
513 if(n->backoff_window < UINT16_MAX) {
523 int is_broadcast =
linkaddr_cmp(dest_addr, &tsch_broadcast_address);
526 if(n->backoff_window != 0
527 && ((n->tx_links_count == 0 && is_broadcast)
531 n = (
struct tsch_neighbor *)nbr_table_next(tsch_neighbors, n);
540 nbr_table_register(tsch_neighbors, NULL);
unsigned short random_rand(void)
Generates a new random number using the cc2538 RNG.
bool linkaddr_cmp(const linkaddr_t *addr1, const linkaddr_t *addr2)
Compare two link-layer addresses.
int memb_free(struct memb *m, void *ptr)
Deallocate a memory block from a memory block previously declared with MEMB().
size_t memb_numfree(struct memb *m)
Count free memory blocks.
void * memb_alloc(struct memb *m)
Allocate a memory block from a block of memory declared with MEMB().
void memb_init(struct memb *m)
Initialize a memory block that was declared with MEMB().
#define MEMB(name, structure, num)
Declare a memory block.
struct tsch_packet * tsch_queue_get_packet_for_dest_addr(const linkaddr_t *addr, struct tsch_link *link)
Returns the first packet that can be sent to a given address on a given link.
struct tsch_neighbor * tsch_queue_get_nbr(const linkaddr_t *addr)
Get a TSCH neighbor.
void tsch_queue_free_unused_neighbors(void)
Deallocate all neighbors with empty queue.
struct tsch_neighbor * tsch_queue_get_time_source(void)
Get the TSCH time source (we currently assume there is only one)
void tsch_queue_update_all_backoff_windows(const linkaddr_t *dest_addr)
Decrement backoff window for the queue(s) able to Tx to a given address.
void tsch_queue_free_packet(struct tsch_packet *p)
Free a packet.
int tsch_queue_global_packet_count(void)
Returns the number of packets currently in all TSCH queues.
struct tsch_packet * tsch_queue_get_packet_for_nbr(const struct tsch_neighbor *n, struct tsch_link *link)
Returns the first packet that can be sent from a queue on a given link.
int tsch_queue_update_time_source(const linkaddr_t *new_addr)
Update TSCH time source.
struct tsch_packet * tsch_queue_add_packet(const linkaddr_t *addr, uint8_t max_transmissions, mac_callback_t sent, void *ptr)
Add packet to neighbor queue.
int tsch_queue_backoff_expired(const struct tsch_neighbor *n)
Is the neighbor backoff timer expired?
int tsch_queue_nbr_packet_count(const struct tsch_neighbor *n)
Returns the number of packets currently a given neighbor queue (by pointer)
int tsch_get_lock(void)
Takes the TSCH lock.
void tsch_set_ka_timeout(uint32_t timeout)
Set the desynchronization timeout after which a node sends a unicasst keep-alive (KA) to its time sou...
void tsch_release_lock(void)
Releases the TSCH lock.
void tsch_queue_reset(void)
Reset neighbor queues module.
int tsch_queue_packet_sent(struct tsch_neighbor *n, struct tsch_packet *p, struct tsch_link *link, uint8_t mac_tx_status)
Updates neighbor queue state after a transmission.
struct tsch_neighbor * tsch_queue_add_nbr(const linkaddr_t *addr)
Add a TSCH neighbor queue.
void tsch_queue_init(void)
Initialize TSCH queue module.
struct tsch_packet * tsch_queue_get_unicast_packet_for_any(struct tsch_neighbor **n, struct tsch_link *link)
Gets the head packet of any neighbor queue with zero backoff counter.
void tsch_queue_free_packets_to(const linkaddr_t *addr)
Flush packets to a specific address.
struct tsch_packet * tsch_queue_remove_packet_from_queue(struct tsch_neighbor *n)
Remove first packet from a neighbor queue.
int tsch_is_locked(void)
Checks if the TSCH lock is set.
int tsch_queue_is_empty(const struct tsch_neighbor *n)
Is the neighbor queue empty?
void tsch_queue_backoff_inc(struct tsch_neighbor *n)
Increment backoff exponent of a given neighbor queue, pick a new window.
linkaddr_t * tsch_queue_get_nbr_address(const struct tsch_neighbor *n)
Get the address of a neighbor.
void tsch_queue_backoff_reset(struct tsch_neighbor *n)
Reset neighbor backoff.
Linked list manipulation routines.
Header file for the logging system.
@ MAC_TX_DEFERRED
The MAC layer transmission could not be performed because of an error.
@ MAC_TX_OK
The MAC layer transmission was OK.
@ MAC_TX_ERR
The MAC layer transmission could not be performed because of a fatal error.
Memory block allocation routines.
Header file for the Packet queue buffer management.
int ringbufindex_peek_get(const struct ringbufindex *r)
Return the index of the first element which will be removed if calling ringbufindex_get.
void ringbufindex_init(struct ringbufindex *r, uint8_t size)
Initialize a ring buffer.
int ringbufindex_put(struct ringbufindex *r)
Put one element to the ring buffer.
int ringbufindex_get(struct ringbufindex *r)
Remove the first element and return its index.
int ringbufindex_peek_put(const struct ringbufindex *r)
Check if there is space to put an element.
static int ringbufindex_elements(const struct ringbufindex *r)
Return the number of elements currently in the ring buffer.
static int ringbufindex_empty(const struct ringbufindex *r)
Is the ring buffer empty?
An IEEE 802.15.4-2015 TSCH link (also called cell or slot)
TSCH neighbor information.
Main API declarations for TSCH.
static uip_ds6_addr_t * addr
Pointer to a nbr cache entry.