Contiki 2.6
|
00001 /* XXX todo: add timeout so that hops_from_sink is reset to MAX 00002 after a while. */ 00003 00004 /* XXX todo: use a ctimer to drive peridodic transmission: the current 00005 way does not work if a queuebuf cannot be allocated. */ 00006 00007 /** 00008 * \addtogroup rudolph2 00009 * @{ 00010 */ 00011 00012 /* 00013 * Copyright (c) 2007, Swedish Institute of Computer Science. 00014 * All rights reserved. 00015 * 00016 * Redistribution and use in source and binary forms, with or without 00017 * modification, are permitted provided that the following conditions 00018 * are met: 00019 * 1. Redistributions of source code must retain the above copyright 00020 * notice, this list of conditions and the following disclaimer. 00021 * 2. Redistributions in binary form must reproduce the above copyright 00022 * notice, this list of conditions and the following disclaimer in the 00023 * documentation and/or other materials provided with the distribution. 00024 * 3. Neither the name of the Institute nor the names of its contributors 00025 * may be used to endorse or promote products derived from this software 00026 * without specific prior written permission. 00027 * 00028 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 00029 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00030 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00031 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 00032 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00033 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00034 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00035 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00036 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00037 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00038 * SUCH DAMAGE. 00039 * 00040 * This file is part of the Contiki operating system. 00041 * 00042 * $Id: rudolph2.c,v 1.7 2009/03/12 21:58:21 adamdunkels Exp $ 00043 */ 00044 00045 /** 00046 * \file 00047 * Rudolph2: a simple block data flooding protocol 00048 * \author 00049 * Adam Dunkels <adam@sics.se> 00050 */ 00051 00052 #include <stdio.h> 00053 #include <stddef.h> /* for offsetof */ 00054 00055 #include "net/rime.h" 00056 #include "net/rime/polite.h" 00057 #include "net/rime/rudolph2.h" 00058 #include "cfs/cfs.h" 00059 00060 #define SEND_INTERVAL CLOCK_SECOND / 2 00061 #define STEADY_INTERVAL CLOCK_SECOND * 16 00062 #define RESEND_INTERVAL SEND_INTERVAL * 4 00063 #define NACK_TIMEOUT CLOCK_SECOND / 4 00064 00065 struct rudolph2_hdr { 00066 uint8_t type; 00067 uint8_t hops_from_base; 00068 uint16_t version; 00069 uint16_t chunk; 00070 }; 00071 00072 #define POLITE_HEADER 1 00073 00074 #define HOPS_MAX 64 00075 00076 enum { 00077 TYPE_DATA, 00078 TYPE_NACK, 00079 }; 00080 00081 #define FLAG_LAST_SENT 0x01 00082 #define FLAG_LAST_RECEIVED 0x02 00083 #define FLAG_IS_STOPPED 0x04 00084 00085 #define DEBUG 0 00086 #if DEBUG 00087 #include <stdio.h> 00088 #define PRINTF(...) printf(__VA_ARGS__) 00089 #else 00090 #define PRINTF(...) 00091 #endif 00092 00093 #define LT(a, b) ((signed short)((a) - (b)) < 0) 00094 00095 /*---------------------------------------------------------------------------*/ 00096 static int 00097 read_data(struct rudolph2_conn *c, uint8_t *dataptr, int chunk) 00098 { 00099 int len = 0; 00100 00101 if(c->cb->read_chunk) { 00102 len = c->cb->read_chunk(c, chunk * RUDOLPH2_DATASIZE, 00103 dataptr, RUDOLPH2_DATASIZE); 00104 } 00105 return len; 00106 } 00107 /*---------------------------------------------------------------------------*/ 00108 static int 00109 format_data(struct rudolph2_conn *c, int chunk) 00110 { 00111 struct rudolph2_hdr *hdr; 00112 int len; 00113 00114 packetbuf_clear(); 00115 hdr = packetbuf_dataptr(); 00116 hdr->type = TYPE_DATA; 00117 hdr->hops_from_base = c->hops_from_base; 00118 hdr->version = c->version; 00119 hdr->chunk = chunk; 00120 len = read_data(c, (uint8_t *)hdr + sizeof(struct rudolph2_hdr), chunk); 00121 packetbuf_set_datalen(sizeof(struct rudolph2_hdr) + len); 00122 00123 return len; 00124 } 00125 /*---------------------------------------------------------------------------*/ 00126 static void 00127 write_data(struct rudolph2_conn *c, int chunk, uint8_t *data, int datalen) 00128 { 00129 /* xxx Don't write any data if the application has been stopped. */ 00130 if(c->flags & FLAG_IS_STOPPED) { 00131 return; 00132 } 00133 00134 if(chunk == 0) { 00135 c->cb->write_chunk(c, 0, RUDOLPH2_FLAG_NEWFILE, data, 0); 00136 } 00137 00138 PRINTF("%d.%d: get %d bytes\n", 00139 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00140 datalen); 00141 00142 00143 if(datalen < RUDOLPH2_DATASIZE) { 00144 PRINTF("%d.%d: get %d bytes, file complete\n", 00145 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00146 datalen); 00147 c->cb->write_chunk(c, chunk * RUDOLPH2_DATASIZE, 00148 RUDOLPH2_FLAG_LASTCHUNK, data, datalen); 00149 } else { 00150 c->cb->write_chunk(c, chunk * RUDOLPH2_DATASIZE, 00151 RUDOLPH2_FLAG_NONE, data, datalen); 00152 } 00153 } 00154 /*---------------------------------------------------------------------------*/ 00155 static int 00156 send_data(struct rudolph2_conn *c, clock_time_t interval) 00157 { 00158 int len; 00159 00160 len = format_data(c, c->snd_nxt); 00161 polite_send(&c->c, interval, POLITE_HEADER); 00162 PRINTF("%d.%d: send_data chunk %d, rcv_nxt %d\n", 00163 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00164 c->snd_nxt, c->rcv_nxt); 00165 00166 return len; 00167 } 00168 /*---------------------------------------------------------------------------*/ 00169 static void 00170 send_nack(struct rudolph2_conn *c) 00171 { 00172 struct rudolph2_hdr *hdr; 00173 packetbuf_clear(); 00174 packetbuf_hdralloc(sizeof(struct rudolph2_hdr)); 00175 hdr = packetbuf_hdrptr(); 00176 00177 hdr->hops_from_base = c->hops_from_base; 00178 hdr->type = TYPE_NACK; 00179 hdr->version = c->version; 00180 hdr->chunk = c->rcv_nxt; 00181 00182 PRINTF("%d.%d: Sending nack for %d\n", 00183 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00184 hdr->chunk); 00185 polite_send(&c->c, NACK_TIMEOUT, POLITE_HEADER); 00186 } 00187 /*---------------------------------------------------------------------------*/ 00188 #if 0 /* Function below not currently used in the code */ 00189 static void 00190 send_next(struct rudolph2_conn *c) 00191 { 00192 int len; 00193 clock_time_t interval; 00194 00195 if(c->flags & FLAG_LAST_SENT) { 00196 interval = STEADY_INTERVAL; 00197 } else { 00198 interval = SEND_INTERVAL; 00199 } 00200 00201 len = send_data(c, interval); 00202 00203 if(len < RUDOLPH2_DATASIZE) { 00204 c->flags |= FLAG_LAST_SENT; 00205 } else { 00206 c->flags &= ~FLAG_LAST_SENT; 00207 } 00208 00209 if(c->nacks == 0 && 00210 len == RUDOLPH2_DATASIZE && 00211 c->snd_nxt + 1 < c->rcv_nxt) { 00212 c->snd_nxt++; 00213 } 00214 c->nacks = 0; 00215 } 00216 #endif /* 0 */ 00217 /*---------------------------------------------------------------------------*/ 00218 static void 00219 sent(struct polite_conn *polite) 00220 { 00221 /* struct rudolph2_conn *c = (struct rudolph2_conn *)polite; 00222 00223 if((c->flags & FLAG_IS_STOPPED) == 0 && 00224 (c->flags & FLAG_LAST_RECEIVED)) { 00225 if(c->snd_nxt < c->rcv_nxt) { 00226 send_next(c); 00227 } else { 00228 send_data(c, STEADY_INTERVAL); 00229 } 00230 }*/ 00231 00232 } 00233 /*---------------------------------------------------------------------------*/ 00234 static void 00235 dropped(struct polite_conn *polite) 00236 { 00237 /* struct rudolph2_conn *c = (struct rudolph2_conn *)polite; 00238 if((c->flags & FLAG_IS_STOPPED) == 0 && 00239 (c->flags & FLAG_LAST_RECEIVED)) { 00240 if(c->snd_nxt + 1 < c->rcv_nxt) { 00241 send_data(c, SEND_INTERVAL); 00242 } else { 00243 send_data(c, STEADY_INTERVAL); 00244 } 00245 }*/ 00246 } 00247 /*---------------------------------------------------------------------------*/ 00248 static void 00249 timed_send(void *ptr) 00250 { 00251 struct rudolph2_conn *c = (struct rudolph2_conn *)ptr; 00252 clock_time_t interval; 00253 int len; 00254 00255 if((c->flags & FLAG_IS_STOPPED) == 0 && 00256 (c->flags & FLAG_LAST_RECEIVED)) { 00257 /* if(c->snd_nxt + 1 < c->rcv_nxt) { 00258 interval = SEND_INTERVAL; 00259 } else { 00260 interval = STEADY_INTERVAL; 00261 }*/ 00262 /* send_data(c, interval);*/ 00263 00264 if(c->flags & FLAG_LAST_SENT) { 00265 interval = STEADY_INTERVAL; 00266 } else { 00267 interval = SEND_INTERVAL; 00268 } 00269 00270 00271 len = send_data(c, interval); 00272 00273 if(len < RUDOLPH2_DATASIZE) { 00274 c->flags |= FLAG_LAST_SENT; 00275 } else { 00276 c->flags &= ~FLAG_LAST_SENT; 00277 } 00278 00279 if(c->nacks == 0 && 00280 len == RUDOLPH2_DATASIZE && 00281 c->snd_nxt + 1 < c->rcv_nxt) { 00282 c->snd_nxt++; 00283 } 00284 c->nacks = 0; 00285 ctimer_set(&c->t, interval, timed_send, c); 00286 } 00287 } 00288 /*---------------------------------------------------------------------------*/ 00289 static void 00290 recv(struct polite_conn *polite) 00291 { 00292 struct rudolph2_conn *c = (struct rudolph2_conn *)polite; 00293 struct rudolph2_hdr *hdr = packetbuf_dataptr(); 00294 00295 /* Only accept NACKs from nodes that are farther away from the base 00296 than us. */ 00297 00298 if(hdr->type == TYPE_NACK && hdr->hops_from_base > c->hops_from_base) { 00299 c->nacks++; 00300 PRINTF("%d.%d: Got NACK for %d:%d (%d:%d)\n", 00301 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00302 hdr->version, hdr->chunk, 00303 c->version, c->rcv_nxt); 00304 if(hdr->version == c->version) { 00305 if(hdr->chunk < c->rcv_nxt) { 00306 c->snd_nxt = hdr->chunk; 00307 send_data(c, SEND_INTERVAL); 00308 } 00309 } else if(LT(hdr->version, c->version)) { 00310 c->snd_nxt = 0; 00311 send_data(c, SEND_INTERVAL); 00312 } 00313 } else if(hdr->type == TYPE_DATA) { 00314 if(hdr->hops_from_base < c->hops_from_base) { 00315 /* Only accept data from nodes that are closer to the base than 00316 us. */ 00317 c->hops_from_base = hdr->hops_from_base + 1; 00318 if(LT(c->version, hdr->version)) { 00319 PRINTF("%d.%d: rudolph2 new version %d, chunk %d\n", 00320 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00321 hdr->version, hdr->chunk); 00322 c->version = hdr->version; 00323 c->snd_nxt = c->rcv_nxt = 0; 00324 c->flags &= ~FLAG_LAST_RECEIVED; 00325 c->flags &= ~FLAG_LAST_SENT; 00326 if(hdr->chunk != 0) { 00327 send_nack(c); 00328 } else { 00329 packetbuf_hdrreduce(sizeof(struct rudolph2_hdr)); 00330 write_data(c, 0, packetbuf_dataptr(), packetbuf_totlen()); 00331 } 00332 } else if(hdr->version == c->version) { 00333 PRINTF("%d.%d: got chunk %d snd_nxt %d rcv_nxt %d\n", 00334 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00335 hdr->chunk, c->snd_nxt, c->rcv_nxt); 00336 00337 if(hdr->chunk == c->rcv_nxt) { 00338 int len; 00339 packetbuf_hdrreduce(sizeof(struct rudolph2_hdr)); 00340 PRINTF("%d.%d: received chunk %d len %d\n", 00341 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00342 hdr->chunk, packetbuf_totlen()); 00343 len = packetbuf_totlen(); 00344 write_data(c, hdr->chunk, packetbuf_dataptr(), packetbuf_totlen()); 00345 c->rcv_nxt++; 00346 if(len < RUDOLPH2_DATASIZE) { 00347 c->flags |= FLAG_LAST_RECEIVED; 00348 send_data(c, RESEND_INTERVAL); 00349 ctimer_set(&c->t, RESEND_INTERVAL, timed_send, c); 00350 } 00351 } else if(hdr->chunk > c->rcv_nxt) { 00352 PRINTF("%d.%d: received chunk %d > %d, sending NACK\n", 00353 rimeaddr_node_addr.u8[0], rimeaddr_node_addr.u8[1], 00354 hdr->chunk, c->rcv_nxt); 00355 send_nack(c); 00356 } else if(hdr->chunk < c->rcv_nxt) { 00357 /* Ignore packets with a lower chunk number */ 00358 } 00359 } 00360 } 00361 } 00362 } 00363 /*---------------------------------------------------------------------------*/ 00364 static const struct polite_callbacks polite = { recv, sent, dropped }; 00365 /*---------------------------------------------------------------------------*/ 00366 void 00367 rudolph2_open(struct rudolph2_conn *c, uint16_t channel, 00368 const struct rudolph2_callbacks *cb) 00369 { 00370 polite_open(&c->c, channel, &polite); 00371 c->cb = cb; 00372 c->version = 0; 00373 c->hops_from_base = HOPS_MAX; 00374 } 00375 /*---------------------------------------------------------------------------*/ 00376 void 00377 rudolph2_close(struct rudolph2_conn *c) 00378 { 00379 polite_close(&c->c); 00380 } 00381 /*---------------------------------------------------------------------------*/ 00382 void 00383 rudolph2_send(struct rudolph2_conn *c, clock_time_t send_interval) 00384 { 00385 int len; 00386 00387 c->hops_from_base = 0; 00388 c->version++; 00389 c->snd_nxt = 0; 00390 len = RUDOLPH2_DATASIZE; 00391 packetbuf_clear(); 00392 for(c->rcv_nxt = 0; len == RUDOLPH2_DATASIZE; c->rcv_nxt++) { 00393 len = read_data(c, packetbuf_dataptr(), c->rcv_nxt); 00394 } 00395 c->flags = FLAG_LAST_RECEIVED; 00396 /* printf("Highest chunk %d\n", c->rcv_nxt);*/ 00397 send_data(c, SEND_INTERVAL); 00398 ctimer_set(&c->t, SEND_INTERVAL, timed_send, c); 00399 } 00400 /*---------------------------------------------------------------------------*/ 00401 void 00402 rudolph2_stop(struct rudolph2_conn *c) 00403 { 00404 polite_cancel(&c->c); 00405 c->flags |= FLAG_IS_STOPPED; 00406 } 00407 /*---------------------------------------------------------------------------*/ 00408 /** @} */