Contiki 2.6
|
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 /*---------------------------------------------------------------------------*/