Contiki 2.6

csma.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 2010, Swedish Institute of Computer Science.
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the Institute nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  *
00029  * This file is part of the Contiki operating system.
00030  *
00031  * $Id: csma.c,v 1.27 2011/01/25 14:24:38 adamdunkels Exp $
00032  */
00033 
00034 /**
00035  * \file
00036  *         A Carrier Sense Multiple Access (CSMA) MAC layer
00037  * \author
00038  *         Adam Dunkels <adam@sics.se>
00039  */
00040 
00041 #include "net/mac/csma.h"
00042 #include "net/packetbuf.h"
00043 #include "net/queuebuf.h"
00044 
00045 #include "sys/ctimer.h"
00046 #include "sys/clock.h"
00047 
00048 #include "lib/random.h"
00049 
00050 #include "net/netstack.h"
00051 
00052 #include "lib/list.h"
00053 #include "lib/memb.h"
00054 
00055 #include <string.h>
00056 
00057 #include <stdio.h>
00058 
00059 #define DEBUG 0
00060 #if DEBUG
00061 #include <stdio.h>
00062 #define PRINTF(...) printf(__VA_ARGS__)
00063 #else /* DEBUG */
00064 #define PRINTF(...)
00065 #endif /* DEBUG */
00066 
00067 #ifndef CSMA_MAX_MAC_TRANSMISSIONS
00068 #ifdef CSMA_CONF_MAX_MAC_TRANSMISSIONS
00069 #define CSMA_MAX_MAC_TRANSMISSIONS CSMA_CONF_MAX_MAC_TRANSMISSIONS
00070 #else
00071 #define CSMA_MAX_MAC_TRANSMISSIONS 3
00072 #endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS */
00073 #endif /* CSMA_MAX_MAC_TRANSMISSIONS */
00074 
00075 #if CSMA_MAX_MAC_TRANSMISSIONS < 1
00076 #error CSMA_CONF_MAX_MAC_TRANSMISSIONS must be at least 1.
00077 #error Change CSMA_CONF_MAX_MAC_TRANSMISSIONS in contiki-conf.h or in your Makefile.
00078 #endif /* CSMA_CONF_MAX_MAC_TRANSMISSIONS < 1 */
00079 
00080 /* Packet metadata */
00081 struct qbuf_metadata {
00082   mac_callback_t sent;
00083   void *cptr;
00084   uint8_t max_transmissions;
00085 };
00086 
00087 /* Every neighbor has its own packet queue */
00088 struct neighbor_queue {
00089   struct neighbor_queue *next;
00090   rimeaddr_t addr;
00091   struct ctimer transmit_timer;
00092   uint8_t transmissions;
00093   uint8_t collisions, deferrals;
00094   LIST_STRUCT(queued_packet_list);
00095 };
00096 
00097 /* The maximum number of co-existing neighbor queues */
00098 #ifdef CSMA_CONF_MAX_NEIGHBOR_QUEUES
00099 #define CSMA_MAX_NEIGHBOR_QUEUES CSMA_CONF_MAX_NEIGHBOR_QUEUES
00100 #else
00101 #define CSMA_MAX_NEIGHBOR_QUEUES 2
00102 #endif /* CSMA_CONF_MAX_NEIGHBOR_QUEUES */
00103 
00104 #define MAX_QUEUED_PACKETS QUEUEBUF_NUM
00105 MEMB(neighbor_memb, struct neighbor_queue, CSMA_MAX_NEIGHBOR_QUEUES);
00106 MEMB(packet_memb, struct rdc_buf_list, MAX_QUEUED_PACKETS);
00107 MEMB(metadata_memb, struct qbuf_metadata, MAX_QUEUED_PACKETS);
00108 LIST(neighbor_list);
00109 
00110 static void packet_sent(void *ptr, int status, int num_transmissions);
00111 static void transmit_packet_list(void *ptr);
00112 
00113 /*---------------------------------------------------------------------------*/
00114 static struct
00115 neighbor_queue *neighbor_queue_from_addr(const rimeaddr_t *addr) {
00116   struct neighbor_queue *n = list_head(neighbor_list);
00117   while(n != NULL) {
00118     if(rimeaddr_cmp(&n->addr, addr)) {
00119       return n;
00120     }
00121     n = list_item_next(n);
00122   }
00123   return NULL;
00124 }
00125 /*---------------------------------------------------------------------------*/
00126 static clock_time_t
00127 default_timebase(void)
00128 {
00129   clock_time_t time;
00130   /* The retransmission time must be proportional to the channel
00131      check interval of the underlying radio duty cycling layer. */
00132   time = NETSTACK_RDC.channel_check_interval();
00133 
00134   /* If the radio duty cycle has no channel check interval (i.e., it
00135      does not turn the radio off), we make the retransmission time
00136      proportional to the configured MAC channel check rate. */
00137   if(time == 0) {
00138     time = CLOCK_SECOND / NETSTACK_RDC_CHANNEL_CHECK_RATE;
00139   }
00140   return time;
00141 }
00142 /*---------------------------------------------------------------------------*/
00143 static void
00144 transmit_packet_list(void *ptr)
00145 {
00146   struct neighbor_queue *n = ptr;
00147   if(n) {
00148     struct rdc_buf_list *q = list_head(n->queued_packet_list);
00149     if(q != NULL) {
00150       PRINTF("csma: preparing number %d %p, queue len %d\n", n->transmissions, q,
00151           list_length(n->queued_packet_list));
00152       /* Send packets in the neighbor's list */
00153       NETSTACK_RDC.send_list(packet_sent, n, q);
00154     }
00155   }
00156 }
00157 /*---------------------------------------------------------------------------*/
00158 static void
00159 free_first_packet(struct neighbor_queue *n)
00160 {
00161   struct rdc_buf_list *q = list_head(n->queued_packet_list);
00162   if(q != NULL) {
00163     /* Remove first packet from list and deallocate */
00164     queuebuf_free(q->buf);
00165     list_pop(n->queued_packet_list);
00166     memb_free(&metadata_memb, q->ptr);
00167     memb_free(&packet_memb, q);
00168     PRINTF("csma: free_queued_packet, queue length %d\n",
00169         list_length(n->queued_packet_list));
00170     if(list_head(n->queued_packet_list)) {
00171       /* There is a next packet. We reset current tx information */
00172       n->transmissions = 0;
00173       n->collisions = 0;
00174       n->deferrals = 0;
00175       /* Set a timer for next transmissions */
00176       ctimer_set(&n->transmit_timer, default_timebase(), transmit_packet_list, n);
00177     } else {
00178       /* This was the last packet in the queue, we free the neighbor */
00179       ctimer_stop(&n->transmit_timer);
00180       list_remove(neighbor_list, n);
00181       memb_free(&neighbor_memb, n);
00182     }
00183   }
00184 }
00185 /*---------------------------------------------------------------------------*/
00186 static void
00187 packet_sent(void *ptr, int status, int num_transmissions)
00188 {
00189   struct neighbor_queue *n = ptr;
00190   struct rdc_buf_list *q = list_head(n->queued_packet_list);
00191   struct qbuf_metadata *metadata = (struct qbuf_metadata *)q->ptr;
00192   clock_time_t time = 0;
00193   mac_callback_t sent;
00194   void *cptr;
00195   int num_tx;
00196   int backoff_transmissions;
00197 
00198   switch(status) {
00199   case MAC_TX_OK:
00200   case MAC_TX_NOACK:
00201     n->transmissions++;
00202     break;
00203   case MAC_TX_COLLISION:
00204     n->collisions++;
00205     break;
00206   case MAC_TX_DEFERRED:
00207     n->deferrals++;
00208     break;
00209   }
00210 
00211   sent = metadata->sent;
00212   cptr = metadata->cptr;
00213   num_tx = n->transmissions;
00214 
00215   if(status == MAC_TX_COLLISION ||
00216      status == MAC_TX_NOACK) {
00217 
00218     /* If the transmission was not performed because of a collision or
00219        noack, we must retransmit the packet. */
00220     
00221     switch(status) {
00222     case MAC_TX_COLLISION:
00223       PRINTF("csma: rexmit collision %d\n", n->transmissions);
00224       break;
00225     case MAC_TX_NOACK:
00226       PRINTF("csma: rexmit noack %d\n", n->transmissions);
00227       break;
00228     default:
00229       PRINTF("csma: rexmit err %d, %d\n", status, n->transmissions);
00230     }
00231 
00232     /* The retransmission time must be proportional to the channel
00233        check interval of the underlying radio duty cycling layer. */
00234     time = default_timebase();
00235 
00236     /* The retransmission time uses a linear backoff so that the
00237        interval between the transmissions increase with each
00238        retransmit. */
00239     backoff_transmissions = n->transmissions + 1;
00240 
00241     /* Clamp the number of backoffs so that we don't get a too long
00242        timeout here, since that will delay all packets in the
00243        queue. */
00244     if(backoff_transmissions > 3) {
00245       backoff_transmissions = 3;
00246     }
00247 
00248     time = time + (random_rand() % (backoff_transmissions * time));
00249 
00250     if(n->transmissions < metadata->max_transmissions) {
00251       PRINTF("csma: retransmitting with time %lu %p\n", time, q);
00252       ctimer_set(&n->transmit_timer, time,
00253                  transmit_packet_list, n);
00254       /* This is needed to correctly attribute energy that we spent
00255          transmitting this packet. */
00256       queuebuf_update_attr_from_packetbuf(q->buf);
00257     } else {
00258       PRINTF("csma: drop with status %d after %d transmissions, %d collisions\n",
00259              status, n->transmissions, n->collisions);
00260       free_first_packet(n);
00261       mac_call_sent_callback(sent, cptr, status, num_tx);
00262     }
00263   } else {
00264     if(status == MAC_TX_OK) {
00265       PRINTF("csma: rexmit ok %d\n", n->transmissions);
00266     } else {
00267       PRINTF("csma: rexmit failed %d: %d\n", n->transmissions, status);
00268     }
00269     free_first_packet(n);
00270     mac_call_sent_callback(sent, cptr, status, num_tx);
00271   }
00272 }
00273 /*---------------------------------------------------------------------------*/
00274 static void
00275 send_packet(mac_callback_t sent, void *ptr)
00276 {
00277   struct rdc_buf_list *q;
00278   struct neighbor_queue *n;
00279   static uint16_t seqno;
00280 
00281   packetbuf_set_attr(PACKETBUF_ATTR_MAC_SEQNO, seqno++);
00282   
00283   /* If the packet is a broadcast, do not allocate a queue
00284      entry. Instead, just send it out.  */
00285   if(!rimeaddr_cmp(packetbuf_addr(PACKETBUF_ADDR_RECEIVER),
00286                    &rimeaddr_null)) {
00287     const rimeaddr_t *addr = packetbuf_addr(PACKETBUF_ADDR_RECEIVER);
00288 
00289     /* Look for the neighbor entry */
00290     n = neighbor_queue_from_addr(addr);
00291     if(n == NULL) {
00292       /* Allocate a new neighbor entry */
00293       n = memb_alloc(&neighbor_memb);
00294       if(n != NULL) {
00295         /* Init neighbor entry */
00296         rimeaddr_copy(&n->addr, addr);
00297         n->transmissions = 0;
00298         n->collisions = 0;
00299         n->deferrals = 0;
00300         /* Init packet list for this neighbor */
00301         LIST_STRUCT_INIT(n, queued_packet_list);
00302         /* Add neighbor to the list */
00303         list_add(neighbor_list, n);
00304       }
00305     }
00306 
00307     if(n != NULL) {
00308       /* Add packet to the neighbor's queue */
00309       q = memb_alloc(&packet_memb);
00310       if(q != NULL) {
00311         q->ptr = memb_alloc(&metadata_memb);
00312         if(q->ptr != NULL) {
00313           q->buf = queuebuf_new_from_packetbuf();
00314           if(q->buf != NULL) {
00315             struct qbuf_metadata *metadata = (struct qbuf_metadata *)q->ptr;
00316             /* Neighbor and packet successfully allocated */
00317             if(packetbuf_attr(PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS) == 0) {
00318               /* Use default configuration for max transmissions */
00319               metadata->max_transmissions = CSMA_MAX_MAC_TRANSMISSIONS;
00320             } else {
00321               metadata->max_transmissions =
00322                   packetbuf_attr(PACKETBUF_ATTR_MAX_MAC_TRANSMISSIONS);
00323             }
00324             metadata->sent = sent;
00325             metadata->cptr = ptr;
00326 
00327             if(packetbuf_attr(PACKETBUF_ATTR_PACKET_TYPE) ==
00328                 PACKETBUF_ATTR_PACKET_TYPE_ACK) {
00329               list_push(n->queued_packet_list, q);
00330             } else {
00331               list_add(n->queued_packet_list, q);
00332             }
00333 
00334             /* If q is the first packet in the neighbor's queue, send asap */
00335             if(list_head(n->queued_packet_list) == q) {
00336               ctimer_set(&n->transmit_timer, 0, transmit_packet_list, n);
00337             }
00338             return;
00339           }
00340           memb_free(&metadata_memb, q->ptr);
00341           PRINTF("csma: could not allocate queuebuf, dropping packet\n");
00342         }
00343         memb_free(&packet_memb, q);
00344         PRINTF("csma: could not allocate queuebuf, dropping packet\n");
00345       }
00346       /* The packet allocation failed. Remove and free neighbor entry if empty. */
00347       if(list_length(n->queued_packet_list) == 0) {
00348         list_remove(neighbor_list, n);
00349         memb_free(&neighbor_memb, n);
00350       }
00351       PRINTF("csma: could not allocate packet, dropping packet\n");
00352     } else {
00353       PRINTF("csma: could not allocate neighbor, dropping packet\n");
00354     }
00355     mac_call_sent_callback(sent, ptr, MAC_TX_ERR, 1);
00356   } else {
00357     PRINTF("csma: send broadcast\n");
00358     NETSTACK_RDC.send(sent, ptr);
00359   }
00360 }
00361 /*---------------------------------------------------------------------------*/
00362 static void
00363 input_packet(void)
00364 {
00365   NETSTACK_NETWORK.input();
00366 }
00367 /*---------------------------------------------------------------------------*/
00368 static int
00369 on(void)
00370 {
00371   return NETSTACK_RDC.on();
00372 }
00373 /*---------------------------------------------------------------------------*/
00374 static int
00375 off(int keep_radio_on)
00376 {
00377   return NETSTACK_RDC.off(keep_radio_on);
00378 }
00379 /*---------------------------------------------------------------------------*/
00380 static unsigned short
00381 channel_check_interval(void)
00382 {
00383   if(NETSTACK_RDC.channel_check_interval) {
00384     return NETSTACK_RDC.channel_check_interval();
00385   }
00386   return 0;
00387 }
00388 /*---------------------------------------------------------------------------*/
00389 static void
00390 init(void)
00391 {
00392   memb_init(&packet_memb);
00393   memb_init(&metadata_memb);
00394   memb_init(&neighbor_memb);
00395 }
00396 /*---------------------------------------------------------------------------*/
00397 const struct mac_driver csma_driver = {
00398   "CSMA",
00399   init,
00400   send_packet,
00401   input_packet,
00402   on,
00403   off,
00404   channel_check_interval,
00405 };
00406 /*---------------------------------------------------------------------------*/