net/ip/contiki/mac/csma.c - third_party/github/zephyrproject-rtos/zephyr - Git at Google

 /*
  * Copyright (c) 2010, Swedish Institute of Computer Science.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the Institute nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
  * This file is part of the Contiki operating system.
  *
  */

 /**
  * \file
  *         A Carrier Sense Multiple Access (CSMA) MAC layer
  * \author
  *         Adam Dunkels <adam@sics.se>
  */

 #include <net/l2_buf.h>

 #include "contiki/mac/csma.h"
 #include "contiki/packetbuf.h"
 #include "contiki/queuebuf.h"

 #include "sys/ctimer.h"
 #include "sys/clock.h"

 #include "lib/random.h"

 #include "contiki/netstack.h"

 #include "lib/list.h"
 #include "lib/memb.h"

 #include <string.h>

 #include <stdio.h>

 #if UIP_LOGGING
 #include <stdio.h>
 void uip_log(char *msg);
 #define UIP_LOG(m) uip_log(m)
 #else
 #define UIP_LOG(m)
 #endif

 #ifdef CONFIG_NETWORK_IP_STACK_DEBUG_15_4_MAC
 #define DEBUG 1
 #endif
 #include "contiki/ip/uip-debug.h"

 #if UIP_LOGGING
 #include <stdio.h>
 void uip_log(char *msg);
 #define UIP_LOG(m) uip_log(m)
 #else
 #define UIP_LOG(m)
 #endif

 #ifndef CSMA_MAX_BACKOFF_EXPONENT
 #ifdef CSMA_CONF_MAX_BACKOFF_EXPONENT
 #define CSMA_MAX_BACKOFF_EXPONENT CSMA_CONF_MAX_BACKOFF_EXPONENT
 #else
 #define CSMA_MAX_BACKOFF_EXPONENT 3
 #endif /* CSMA_CONF_MAX_BACKOFF_EXPONENT */
 #endif /* CSMA_MAX_BACKOFF_EXPONENT */

 #ifndef CSMA_MAX_MAC_TRANSMISSIONS
 #ifdef CSMA_CONF_MAX_MAC_TRANSMISSIONS
 #define CSMA_MAX_MAC_TRANSMISSIONS CSMA_CONF_MAX_MAC_TRANSMISSIONS
 #else
 #define CSMA_MAX_MAC_TRANSMISSIONS 3
 #endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS */
 #endif /* CSMA_MAX_MAC_TRANSMISSIONS */

 #if CSMA_MAX_MAC_TRANSMISSIONS < 1
 #error CSMA_CONF_MAX_MAC_TRANSMISSIONS must be at least 1.
 #error Change CSMA_CONF_MAX_MAC_TRANSMISSIONS in contiki-conf.h or in your Makefile.
 #endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS < 1 */

 /* Packet metadata */
 struct qbuf_metadata {
   mac_callback_t sent;
   void *cptr;
   uint8_t max_transmissions;
 };

 /* Every neighbor has its own packet queue */
 struct neighbor_queue {
   struct neighbor_queue *next;
   linkaddr_t addr;
   struct ctimer transmit_timer;
   uint8_t transmissions;
   uint8_t collisions, deferrals;
   LIST_STRUCT(queued_packet_list);
 };

 /* The maximum number of co-existing neighbor queues */
 #ifdef CSMA_CONF_MAX_NEIGHBOR_QUEUES
 #define CSMA_MAX_NEIGHBOR_QUEUES CSMA_CONF_MAX_NEIGHBOR_QUEUES
 #else
 #define CSMA_MAX_NEIGHBOR_QUEUES 2
 #endif /* CSMA_CONF_MAX_NEIGHBOR_QUEUES */

 /* The maximum number of pending packet per neighbor */
 #ifdef CSMA_CONF_MAX_PACKET_PER_NEIGHBOR
 #define CSMA_MAX_PACKET_PER_NEIGHBOR CSMA_CONF_MAX_PACKET_PER_NEIGHBOR
 #else
 #define CSMA_MAX_PACKET_PER_NEIGHBOR MAX_QUEUED_PACKETS
 #endif /* CSMA_CONF_MAX_PACKET_PER_NEIGHBOR */

 #define MAX_QUEUED_PACKETS QUEUEBUF_NUM
 MEMB(neighbor_memb, struct neighbor_queue, CSMA_MAX_NEIGHBOR_QUEUES);
 MEMB(packet_memb, struct rdc_buf_list, MAX_QUEUED_PACKETS);
 MEMB(metadata_memb, struct qbuf_metadata, MAX_QUEUED_PACKETS);

 static void packet_sent(struct net_buf *buf, void *ptr, int status, int num_transmissions);
 static void transmit_packet_list(struct net_buf *buf, void *ptr);

 /*---------------------------------------------------------------------------*/
 static struct neighbor_queue *
 neighbor_queue_from_addr(struct net_buf *buf, const linkaddr_t *addr)
 {
   struct neighbor_queue *n = list_head(uip_neighbor_list(buf));
   while(n != NULL) {
     if(linkaddr_cmp(&n->addr, addr)) {
       return n;
     }
     n = list_item_next(n);
   }
   return NULL;
 }
 /*---------------------------------------------------------------------------*/
 static clock_time_t
 default_timebase(void)
 {
   clock_time_t time;
   /* The retransmission time must be proportional to the channel
      check interval of the underlying radio duty cycling layer. */
   time = NETSTACK_RDC.channel_check_interval();

   /* If the radio duty cycle has no channel check interval (i.e., it
      does not turn the radio off), we make the retransmission time
      proportional to the configured MAC channel check rate. */
   if(time == 0) {
     time = CLOCK_SECOND / NETSTACK_RDC_CHANNEL_CHECK_RATE;
   }
   return time;
 }
 /*---------------------------------------------------------------------------*/
 static void
 free_packet(struct net_buf *buf, struct neighbor_queue *n, struct rdc_buf_list *p)
 {
   if(p != NULL) {
     /* Remove packet from list and deallocate */
     list_remove(n->queued_packet_list, p);

     queuebuf_free(p->buf);
     memb_free(&metadata_memb, p->ptr);
     memb_free(&packet_memb, p);
     PRINTF("csma: free_queued_packet, queue length %d, free packets %d\n",
            list_length(n->queued_packet_list), memb_numfree(&packet_memb));
     if(list_head(n->queued_packet_list) != NULL) {
       /* There is a next packet. We reset current tx information */
       n->transmissions = 0;
       n->collisions = 0;
       n->deferrals = 0;
       transmit_packet_list(buf, n);
     } else {
       /* This was the last packet in the queue, we free the neighbor */
       list_remove(uip_neighbor_list(buf), n);
       memb_free(&neighbor_memb, n);
     }
   }
 }
 /*---------------------------------------------------------------------------*/
 static void
 transmit_packet_list(struct net_buf *buf, void *ptr)
 {
   struct neighbor_queue *n = ptr;
   if(n) {
     struct rdc_buf_list *q = list_head(n->queued_packet_list);
     if(q != NULL) {
       PRINTF("csma: preparing number %d %p, queue len %d\n", n->transmissions, q,
           list_length(n->queued_packet_list));
       /* Send packets in the neighbor's list */
       NETSTACK_RDC.send_list(buf, packet_sent, n, q);
     }
   }
 }
 /*---------------------------------------------------------------------------*/
 static void
 packet_sent(struct net_buf *buf, void *ptr, int status, int num_transmissions)
 {
   struct neighbor_queue *n;
   struct rdc_buf_list *q;
   struct qbuf_metadata *metadata;
   clock_time_t time = 0;
   mac_callback_t sent;
   void *cptr;
   int num_tx;
   int backoff_exponent;
   int backoff_transmissions;

   n = ptr;
   if(n == NULL) {
     return;
   }
   switch(status) {
   case MAC_TX_OK:
   case MAC_TX_NOACK:
     n->transmissions += num_transmissions;
     break;
   case MAC_TX_COLLISION:
     n->collisions += num_transmissions;
     n->transmissions += num_transmissions;
     break;
   case MAC_TX_DEFERRED:
     n->deferrals += num_transmissions;
     break;
   }

   /* Find out what packet this callback refers to */
   for(q = list_head(n->queued_packet_list);
       q != NULL; q = list_item_next(q)) {
     if(queuebuf_attr(q->buf, PACKETBUF_ATTR_MAC_SEQNO) ==
        packetbuf_attr(buf, PACKETBUF_ATTR_MAC_SEQNO)) {
       break;
     }
   }

   if(q != NULL) {
     metadata = (struct qbuf_metadata *)q->ptr;

     if(metadata != NULL) {
       sent = metadata->sent;
       cptr = metadata->cptr;
       num_tx = n->transmissions;
       if(status == MAC_TX_COLLISION ||
          status == MAC_TX_NOACK) {

         /* If the transmission was not performed because of a
            collision or noack, we must retransmit the packet. */

         switch(status) {
         case MAC_TX_COLLISION:
           PRINTF("csma: rexmit collision %d transmission %d\n",
 		 n->collisions, n->transmissions);
           break;
         case MAC_TX_NOACK:
           PRINTF("csma: rexmit noack %d\n", n->transmissions);
           break;
         default:
           PRINTF("csma: rexmit err %d, %d\n", status, n->transmissions);
         }

         /* The retransmission time must be proportional to the channel
            check interval of the underlying radio duty cycling layer. */
         time = default_timebase();

         /* The retransmission time uses a truncated exponential backoff
          * so that the interval between the transmissions increase with
          * each retransmit. */
         backoff_exponent = num_tx;

         /* Truncate the exponent if needed. */
         if(backoff_exponent > CSMA_MAX_BACKOFF_EXPONENT) {
           backoff_exponent = CSMA_MAX_BACKOFF_EXPONENT;
         }

         /* Proceed to exponentiation. */
         backoff_transmissions = 1 << backoff_exponent;

         /* Pick a time for next transmission, within the interval:
          * [time, time + 2^backoff_exponent * time[ */
         time = time + (random_rand() % (backoff_transmissions * time));

         if(n->transmissions < metadata->max_transmissions) {
           PRINTF("csma: retransmitting with time %lu %p\n", time, q);
           ctimer_set(buf, &n->transmit_timer, time,
                      transmit_packet_list, n);
           /* This is needed to correctly attribute energy that we spent
              transmitting this packet. */
           queuebuf_update_attr_from_packetbuf(buf, q->buf);
         } else {
           PRINTF("csma: drop with status %d after %d transmissions, %d collisions\n",
                  status, n->transmissions, n->collisions);
           free_packet(buf, n, q);
           mac_call_sent_callback(buf, sent, cptr, status, num_tx);
         }
       } else {
         if(status == MAC_TX_OK) {
           PRINTF("csma: rexmit ok %d\n", n->transmissions);
         } else {
           PRINTF("csma: rexmit failed %d: %d\n", n->transmissions, status);
         }
         free_packet(buf, n, q);
         mac_call_sent_callback(buf, sent, cptr, status, num_tx);
       }
     } else {
       PRINTF("csma: no metadata\n");
     }
   } else {
     PRINTF("csma: seqno %d not found\n", packetbuf_attr(buf, PACKETBUF_ATTR_MAC_SEQNO));
   }
 }
 /*---------------------------------------------------------------------------*/
 static uint8_t
 send_packet(struct net_buf *buf, mac_callback_t sent, bool last_fragment, void *ptr)
 {
   struct rdc_buf_list *q;
   struct neighbor_queue *n;
   static uint8_t initialized = 0;
   static uint16_t seqno;
   const linkaddr_t *addr = packetbuf_addr(buf, PACKETBUF_ADDR_RECEIVER);

   if (!buf) {
     UIP_LOG("csma: send_packet(): net_buf is NULL, cannot send packet");
     return 0;
   }

   if(!initialized) {
     initialized = 1;
     /* Initialize the sequence number to a random value as per 802.15.4. */
     seqno = random_rand();
   }

   if(seqno == 0) {
     /* PACKETBUF_ATTR_MAC_SEQNO cannot be zero, due to a pecuilarity
        in framer-802154.c. */
     seqno++;
   }
   packetbuf_set_attr(buf, PACKETBUF_ATTR_MAC_SEQNO, seqno++);

   /* Look for the neighbor entry */
   n = neighbor_queue_from_addr(buf, addr);
   if(n == NULL) {
     /* Allocate a new neighbor entry */
     n = memb_alloc(&neighbor_memb);
     if(n != NULL) {
       /* Init neighbor entry */
       linkaddr_copy(&n->addr, addr);
       n->transmissions = 0;
       n->collisions = 0;
       n->deferrals = 0;
       /* Init packet list for this neighbor */
       LIST_STRUCT_INIT(n, queued_packet_list);
       /* Add neighbor to the list */
       list_add(uip_neighbor_list(buf), n);
     }
   }

   if(n != NULL) {
     /* Add packet to the neighbor's queue */
     if(list_length(n->queued_packet_list) < CSMA_MAX_PACKET_PER_NEIGHBOR) {
       q = memb_alloc(&packet_memb);
       if(q != NULL) {
         q->ptr = memb_alloc(&metadata_memb);
         if(q->ptr != NULL) {
           q->buf = queuebuf_new_from_packetbuf(buf);
           if(q->buf != NULL) {
             struct qbuf_metadata *metadata = (struct qbuf_metadata *)q->ptr;
             /* Neighbor and packet successfully allocated */
             if(packetbuf_attr(buf, PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS) == 0) {
               /* Use default configuration for max transmissions */
               metadata->max_transmissions = CSMA_MAX_MAC_TRANSMISSIONS;
             } else {
               metadata->max_transmissions =
                 packetbuf_attr(buf, PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS);
             }
             metadata->sent = sent;
             metadata->cptr = ptr;

             if(packetbuf_attr(buf, PACKETBUF_ATTR_PACKET_TYPE) ==
                PACKETBUF_ATTR_PACKET_TYPE_ACK) {
               list_push(n->queued_packet_list, q);
             } else {
               list_add(n->queued_packet_list, q);
             }

             PRINTF("csma: send_packet, queue length %d, free packets %d\n",
                    list_length(n->queued_packet_list), memb_numfree(&packet_memb));
             /* if received packet is last fragment/only one packet start sending
              * packets in list, do not start any timer.*/
             if (last_fragment) {
                transmit_packet_list(buf, n);
             }
             return 1;
           }
           memb_free(&metadata_memb, q->ptr);
           PRINTF("csma: could not allocate queuebuf, dropping packet\n");
         }
         memb_free(&packet_memb, q);
         PRINTF("csma: could not allocate queuebuf, dropping packet\n");
       }
       /* The packet allocation failed. Remove and free neighbor entry if empty. */
       if(list_length(n->queued_packet_list) == 0) {
         list_remove(uip_neighbor_list(buf), n);
         memb_free(&neighbor_memb, n);
       }
     } else {
       PRINTF("csma: Neighbor queue full\n");
     }
     PRINTF("csma: could not allocate packet, dropping packet\n");
   } else {
     PRINTF("csma: could not allocate neighbor, dropping packet\n");
   }
   mac_call_sent_callback(buf, sent, ptr, MAC_TX_ERR, 1);
   return 0;
 }
 /*---------------------------------------------------------------------------*/
 static uint8_t
 input_packet(struct net_buf *buf)
 {
   return NETSTACK_LLSEC.input(buf);
 }
 /*---------------------------------------------------------------------------*/
 static int
 on(void)
 {
   return NETSTACK_RDC.on();
 }
 /*---------------------------------------------------------------------------*/
 static int
 off(int keep_radio_on)
 {
   return NETSTACK_RDC.off(keep_radio_on);
 }
 /*---------------------------------------------------------------------------*/
 static unsigned short
 channel_check_interval(void)
 {
   if(NETSTACK_RDC.channel_check_interval) {
     return NETSTACK_RDC.channel_check_interval();
   }
   return 0;
 }
 /*---------------------------------------------------------------------------*/
 static void
 init(void)
 {
   queuebuf_init();

   memb_init(&packet_memb);
   memb_init(&metadata_memb);
   memb_init(&neighbor_memb);
 }
 /*---------------------------------------------------------------------------*/
 const struct mac_driver csma_driver = {
   "CSMA",
   init,
   send_packet,
   input_packet,
   on,
   off,
   channel_check_interval,
 };
 /*---------------------------------------------------------------------------*/
	/*
	* Copyright (c) 2010, Swedish Institute of Computer Science.
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of the Institute nor the names of its contributors
	* may be used to endorse or promote products derived from this software
	* without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	* SUCH DAMAGE.
	*
	* This file is part of the Contiki operating system.
	*
	*/

	/**
	* \file
	* A Carrier Sense Multiple Access (CSMA) MAC layer
	* \author
	* Adam Dunkels <adam@sics.se>
	*/

	#include <net/l2_buf.h>

	#include "contiki/mac/csma.h"
	#include "contiki/packetbuf.h"
	#include "contiki/queuebuf.h"

	#include "sys/ctimer.h"
	#include "sys/clock.h"

	#include "lib/random.h"

	#include "contiki/netstack.h"

	#include "lib/list.h"
	#include "lib/memb.h"

	#include <string.h>

	#include <stdio.h>

	#if UIP_LOGGING
	#include <stdio.h>
	void uip_log(char *msg);
	#define UIP_LOG(m) uip_log(m)
	#else
	#define UIP_LOG(m)
	#endif

	#ifdef CONFIG_NETWORK_IP_STACK_DEBUG_15_4_MAC
	#define DEBUG 1
	#endif
	#include "contiki/ip/uip-debug.h"

	#if UIP_LOGGING
	#include <stdio.h>
	void uip_log(char *msg);
	#define UIP_LOG(m) uip_log(m)
	#else
	#define UIP_LOG(m)
	#endif

	#ifndef CSMA_MAX_BACKOFF_EXPONENT
	#ifdef CSMA_CONF_MAX_BACKOFF_EXPONENT
	#define CSMA_MAX_BACKOFF_EXPONENT CSMA_CONF_MAX_BACKOFF_EXPONENT
	#else
	#define CSMA_MAX_BACKOFF_EXPONENT 3
	#endif /* CSMA_CONF_MAX_BACKOFF_EXPONENT */
	#endif /* CSMA_MAX_BACKOFF_EXPONENT */

	#ifndef CSMA_MAX_MAC_TRANSMISSIONS
	#ifdef CSMA_CONF_MAX_MAC_TRANSMISSIONS
	#define CSMA_MAX_MAC_TRANSMISSIONS CSMA_CONF_MAX_MAC_TRANSMISSIONS
	#else
	#define CSMA_MAX_MAC_TRANSMISSIONS 3
	#endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS */
	#endif /* CSMA_MAX_MAC_TRANSMISSIONS */

	#if CSMA_MAX_MAC_TRANSMISSIONS < 1
	#error CSMA_CONF_MAX_MAC_TRANSMISSIONS must be at least 1.
	#error Change CSMA_CONF_MAX_MAC_TRANSMISSIONS in contiki-conf.h or in your Makefile.
	#endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS < 1 */

	/* Packet metadata */
	struct qbuf_metadata {
	mac_callback_t sent;
	void *cptr;
	uint8_t max_transmissions;
	};

	/* Every neighbor has its own packet queue */
	struct neighbor_queue {
	struct neighbor_queue *next;
	linkaddr_t addr;
	struct ctimer transmit_timer;
	uint8_t transmissions;
	uint8_t collisions, deferrals;
	LIST_STRUCT(queued_packet_list);
	};

	/* The maximum number of co-existing neighbor queues */
	#ifdef CSMA_CONF_MAX_NEIGHBOR_QUEUES
	#define CSMA_MAX_NEIGHBOR_QUEUES CSMA_CONF_MAX_NEIGHBOR_QUEUES
	#else
	#define CSMA_MAX_NEIGHBOR_QUEUES 2
	#endif /* CSMA_CONF_MAX_NEIGHBOR_QUEUES */

	/* The maximum number of pending packet per neighbor */
	#ifdef CSMA_CONF_MAX_PACKET_PER_NEIGHBOR
	#define CSMA_MAX_PACKET_PER_NEIGHBOR CSMA_CONF_MAX_PACKET_PER_NEIGHBOR
	#else
	#define CSMA_MAX_PACKET_PER_NEIGHBOR MAX_QUEUED_PACKETS
	#endif /* CSMA_CONF_MAX_PACKET_PER_NEIGHBOR */

	#define MAX_QUEUED_PACKETS QUEUEBUF_NUM
	MEMB(neighbor_memb, struct neighbor_queue, CSMA_MAX_NEIGHBOR_QUEUES);
	MEMB(packet_memb, struct rdc_buf_list, MAX_QUEUED_PACKETS);
	MEMB(metadata_memb, struct qbuf_metadata, MAX_QUEUED_PACKETS);

	static void packet_sent(struct net_buf buf, void ptr, int status, int num_transmissions);
	static void transmit_packet_list(struct net_buf buf, void ptr);

	/---------------------------------------------------------------------------/
	static struct neighbor_queue *
	neighbor_queue_from_addr(struct net_buf buf, const linkaddr_t addr)
	{
	struct neighbor_queue *n = list_head(uip_neighbor_list(buf));
	while(n != NULL) {
	if(linkaddr_cmp(&n->addr, addr)) {
	return n;
	}
	n = list_item_next(n);
	}
	return NULL;
	}
	/---------------------------------------------------------------------------/
	static clock_time_t
	default_timebase(void)
	{
	clock_time_t time;
	/* The retransmission time must be proportional to the channel
	check interval of the underlying radio duty cycling layer. */
	time = NETSTACK_RDC.channel_check_interval();

	/* If the radio duty cycle has no channel check interval (i.e., it
	does not turn the radio off), we make the retransmission time
	proportional to the configured MAC channel check rate. */
	if(time == 0) {
	time = CLOCK_SECOND / NETSTACK_RDC_CHANNEL_CHECK_RATE;
	}
	return time;
	}
	/---------------------------------------------------------------------------/
	static void
	free_packet(struct net_buf buf, struct neighbor_queue n, struct rdc_buf_list *p)
	{
	if(p != NULL) {
	/* Remove packet from list and deallocate */
	list_remove(n->queued_packet_list, p);

	queuebuf_free(p->buf);
	memb_free(&metadata_memb, p->ptr);
	memb_free(&packet_memb, p);
	PRINTF("csma: free_queued_packet, queue length %d, free packets %d\n",
	list_length(n->queued_packet_list), memb_numfree(&packet_memb));
	if(list_head(n->queued_packet_list) != NULL) {
	/* There is a next packet. We reset current tx information */
	n->transmissions = 0;
	n->collisions = 0;
	n->deferrals = 0;
	transmit_packet_list(buf, n);
	} else {
	/* This was the last packet in the queue, we free the neighbor */
	list_remove(uip_neighbor_list(buf), n);
	memb_free(&neighbor_memb, n);
	}
	}
	}
	/---------------------------------------------------------------------------/
	static void
	transmit_packet_list(struct net_buf buf, void ptr)
	{
	struct neighbor_queue *n = ptr;
	if(n) {
	struct rdc_buf_list *q = list_head(n->queued_packet_list);
	if(q != NULL) {
	PRINTF("csma: preparing number %d %p, queue len %d\n", n->transmissions, q,
	list_length(n->queued_packet_list));
	/* Send packets in the neighbor's list */
	NETSTACK_RDC.send_list(buf, packet_sent, n, q);
	}
	}
	}
	/---------------------------------------------------------------------------/
	static void
	packet_sent(struct net_buf buf, void ptr, int status, int num_transmissions)
	{
	struct neighbor_queue *n;
	struct rdc_buf_list *q;
	struct qbuf_metadata *metadata;
	clock_time_t time = 0;
	mac_callback_t sent;
	void *cptr;
	int num_tx;
	int backoff_exponent;
	int backoff_transmissions;

	n = ptr;
	if(n == NULL) {
	return;
	}
	switch(status) {
	case MAC_TX_OK:
	case MAC_TX_NOACK:
	n->transmissions += num_transmissions;
	break;
	case MAC_TX_COLLISION:
	n->collisions += num_transmissions;
	n->transmissions += num_transmissions;
	break;
	case MAC_TX_DEFERRED:
	n->deferrals += num_transmissions;
	break;
	}

	/* Find out what packet this callback refers to */
	for(q = list_head(n->queued_packet_list);
	q != NULL; q = list_item_next(q)) {
	if(queuebuf_attr(q->buf, PACKETBUF_ATTR_MAC_SEQNO) ==
	packetbuf_attr(buf, PACKETBUF_ATTR_MAC_SEQNO)) {
	break;
	}
	}

	if(q != NULL) {
	metadata = (struct qbuf_metadata *)q->ptr;

	if(metadata != NULL) {
	sent = metadata->sent;
	cptr = metadata->cptr;
	num_tx = n->transmissions;
	if(status == MAC_TX_COLLISION \|\|
	status == MAC_TX_NOACK) {

	/* If the transmission was not performed because of a
	collision or noack, we must retransmit the packet. */

	switch(status) {
	case MAC_TX_COLLISION:
	PRINTF("csma: rexmit collision %d transmission %d\n",
	n->collisions, n->transmissions);
	break;
	case MAC_TX_NOACK:
	PRINTF("csma: rexmit noack %d\n", n->transmissions);
	break;
	default:
	PRINTF("csma: rexmit err %d, %d\n", status, n->transmissions);
	}

	/* The retransmission time must be proportional to the channel
	check interval of the underlying radio duty cycling layer. */
	time = default_timebase();

	/* The retransmission time uses a truncated exponential backoff
	* so that the interval between the transmissions increase with
	* each retransmit. */
	backoff_exponent = num_tx;

	/* Truncate the exponent if needed. */
	if(backoff_exponent > CSMA_MAX_BACKOFF_EXPONENT) {
	backoff_exponent = CSMA_MAX_BACKOFF_EXPONENT;
	}

	/* Proceed to exponentiation. */
	backoff_transmissions = 1 << backoff_exponent;

	/* Pick a time for next transmission, within the interval:
	* [time, time + 2^backoff_exponent * time[ */
	time = time + (random_rand() % (backoff_transmissions * time));

	if(n->transmissions < metadata->max_transmissions) {
	PRINTF("csma: retransmitting with time %lu %p\n", time, q);
	ctimer_set(buf, &n->transmit_timer, time,
	transmit_packet_list, n);
	/* This is needed to correctly attribute energy that we spent
	transmitting this packet. */
	queuebuf_update_attr_from_packetbuf(buf, q->buf);
	} else {
	PRINTF("csma: drop with status %d after %d transmissions, %d collisions\n",
	status, n->transmissions, n->collisions);
	free_packet(buf, n, q);
	mac_call_sent_callback(buf, sent, cptr, status, num_tx);
	}
	} else {
	if(status == MAC_TX_OK) {
	PRINTF("csma: rexmit ok %d\n", n->transmissions);
	} else {
	PRINTF("csma: rexmit failed %d: %d\n", n->transmissions, status);
	}
	free_packet(buf, n, q);
	mac_call_sent_callback(buf, sent, cptr, status, num_tx);
	}
	} else {
	PRINTF("csma: no metadata\n");
	}
	} else {
	PRINTF("csma: seqno %d not found\n", packetbuf_attr(buf, PACKETBUF_ATTR_MAC_SEQNO));
	}
	}
	/---------------------------------------------------------------------------/
	static uint8_t
	send_packet(struct net_buf buf, mac_callback_t sent, bool last_fragment, void ptr)
	{
	struct rdc_buf_list *q;
	struct neighbor_queue *n;
	static uint8_t initialized = 0;
	static uint16_t seqno;
	const linkaddr_t *addr = packetbuf_addr(buf, PACKETBUF_ADDR_RECEIVER);

	if (!buf) {
	UIP_LOG("csma: send_packet(): net_buf is NULL, cannot send packet");
	return 0;
	}

	if(!initialized) {
	initialized = 1;
	/* Initialize the sequence number to a random value as per 802.15.4. */
	seqno = random_rand();
	}

	if(seqno == 0) {
	/* PACKETBUF_ATTR_MAC_SEQNO cannot be zero, due to a pecuilarity
	in framer-802154.c. */
	seqno++;
	}
	packetbuf_set_attr(buf, PACKETBUF_ATTR_MAC_SEQNO, seqno++);

	/* Look for the neighbor entry */
	n = neighbor_queue_from_addr(buf, addr);
	if(n == NULL) {
	/* Allocate a new neighbor entry */
	n = memb_alloc(&neighbor_memb);
	if(n != NULL) {
	/* Init neighbor entry */
	linkaddr_copy(&n->addr, addr);
	n->transmissions = 0;
	n->collisions = 0;
	n->deferrals = 0;
	/* Init packet list for this neighbor */
	LIST_STRUCT_INIT(n, queued_packet_list);
	/* Add neighbor to the list */
	list_add(uip_neighbor_list(buf), n);
	}
	}

	if(n != NULL) {
	/* Add packet to the neighbor's queue */
	if(list_length(n->queued_packet_list) < CSMA_MAX_PACKET_PER_NEIGHBOR) {
	q = memb_alloc(&packet_memb);
	if(q != NULL) {
	q->ptr = memb_alloc(&metadata_memb);
	if(q->ptr != NULL) {
	q->buf = queuebuf_new_from_packetbuf(buf);
	if(q->buf != NULL) {
	struct qbuf_metadata metadata = (struct qbuf_metadata )q->ptr;
	/* Neighbor and packet successfully allocated */
	if(packetbuf_attr(buf, PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS) == 0) {
	/* Use default configuration for max transmissions */
	metadata->max_transmissions = CSMA_MAX_MAC_TRANSMISSIONS;
	} else {
	metadata->max_transmissions =
	packetbuf_attr(buf, PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS);
	}
	metadata->sent = sent;
	metadata->cptr = ptr;

	if(packetbuf_attr(buf, PACKETBUF_ATTR_PACKET_TYPE) ==
	PACKETBUF_ATTR_PACKET_TYPE_ACK) {
	list_push(n->queued_packet_list, q);
	} else {
	list_add(n->queued_packet_list, q);
	}

	PRINTF("csma: send_packet, queue length %d, free packets %d\n",
	list_length(n->queued_packet_list), memb_numfree(&packet_memb));
	/* if received packet is last fragment/only one packet start sending
	* packets in list, do not start any timer.*/
	if (last_fragment) {
	transmit_packet_list(buf, n);
	}
	return 1;
	}
	memb_free(&metadata_memb, q->ptr);
	PRINTF("csma: could not allocate queuebuf, dropping packet\n");
	}
	memb_free(&packet_memb, q);
	PRINTF("csma: could not allocate queuebuf, dropping packet\n");
	}
	/* The packet allocation failed. Remove and free neighbor entry if empty. */
	if(list_length(n->queued_packet_list) == 0) {
	list_remove(uip_neighbor_list(buf), n);
	memb_free(&neighbor_memb, n);
	}
	} else {
	PRINTF("csma: Neighbor queue full\n");
	}
	PRINTF("csma: could not allocate packet, dropping packet\n");
	} else {
	PRINTF("csma: could not allocate neighbor, dropping packet\n");
	}
	mac_call_sent_callback(buf, sent, ptr, MAC_TX_ERR, 1);
	return 0;
	}
	/---------------------------------------------------------------------------/
	static uint8_t
	input_packet(struct net_buf *buf)
	{
	return NETSTACK_LLSEC.input(buf);
	}
	/---------------------------------------------------------------------------/
	static int
	on(void)
	{
	return NETSTACK_RDC.on();
	}
	/---------------------------------------------------------------------------/
	static int
	off(int keep_radio_on)
	{
	return NETSTACK_RDC.off(keep_radio_on);
	}
	/---------------------------------------------------------------------------/
	static unsigned short
	channel_check_interval(void)
	{
	if(NETSTACK_RDC.channel_check_interval) {
	return NETSTACK_RDC.channel_check_interval();
	}
	return 0;
	}
	/---------------------------------------------------------------------------/
	static void
	init(void)
	{
	queuebuf_init();

	memb_init(&packet_memb);
	memb_init(&metadata_memb);
	memb_init(&neighbor_memb);
	}
	/---------------------------------------------------------------------------/
	const struct mac_driver csma_driver = {
	"CSMA",
	init,
	send_packet,
	input_packet,
	on,
	off,
	channel_check_interval,
	};
	/---------------------------------------------------------------------------/