ipdispatchp.nc

tinyos-2.x.rar

/*
 * "Copyright (c) 2008 The Regents of the University  of California.
 * All rights reserved."
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice, the following
 * two paragraphs and the author appear in all copies of this software.
 *
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 */

/*
 * This file has the potential to be rather confusing, here are a few
 * notes about what is happening.  There are several state machines in
 * this file.  Together, they take care of packet forwarding and
 * sending (which is accomplished by injecting new packets into the
 * outgoing queue.)
 *
 * Messages enter from two places: either from the bottom (from the
 * radio), or from the top (from the application).  Messages also
 * leave from two places: either out over the radio, or up to an
 * application.
 *
 *
 *    IP.send          ---- - --->   IP.recvfrom
 *                         \ /
 *                          X
 *                         / \
 *    IEEE154.receive  ---- - --->   IEEE154.send
 *
 *
 *  All of the queueing is done on the output; when each message
 *  arrives, it is dispatched all the way to an output queue.
 *
 *  There are four paths through the system, so here they are:
 *
 *  IP.send -> IP.recvfrom       :  local delivery: not implemented
 *  IP.send -> IEEE154.send      :  enqueue fragments on radio queue
 *  IEEE154.receive -> IP.recv   :  deliver to this mote : reassemble and deliver
 *  IEEE154.receive -> IEEE154.send : forwarding : enqueue fragments
 *
 *  the IP receive queue
 *   data structures:  
 *      recon_cache: holds state about packets which are to be consumed 
 *               by this mote, and have fragments pending.
 *
 *  radio send queue
 *   data structures:
 *      send_info_t: packet metadata for a single packet flow through 
 *                   the mote (could either come from a forwarded stream 
 *                   or a local send.    
 *      send_entry_t: the actual queue items, pointing to a fragment  
 *                   and the packet metadata (send_info_t)
 *
 *  extra forwarding structures:
 *    forward_cache: used to match up incoming fragments with their flow metadata,
 *               stored in a send_info_t.
 *    fragment pool: 
 */
#include <6lowpan.h>
#include <lib6lowpan.h>
#include <ip.h>
#include <in_cksum.h>
#include <ip_malloc.h>
#include "IPDispatch.h"
#include "table.h"
#include "PrintfUART.h"

/*
 * Provides IP layer reception to applications on motes.
 *
 * @author Stephen Dawson-Haggerty <[e-mail]>
 */

module IPDispatchP {
  provides {
    interface SplitControl;
    // interface for protocols not requiring special hand-holding
    interface IP[uint8_t nxt_hdr];

    interface Statistics<ip_statistics_t>;

    // IPv6 Extension headers are very useful, but somewhat tricky to
    // handle in a pretty way.  This is my attempt.

    // for inspecting/modifying extension headers on incomming packets
    interface IPExtensions;

  }
  uses {
    interface Boot;
    interface SplitControl as RadioControl;

    interface ReadLqi;
    interface Packet;

    interface Ieee154Send;
    interface Ieee154Packet;
    interface Receive as Ieee154Receive;

    interface PacketLink;

    // outgoing fragments
    interface Pool<message_t> as FragPool;
    interface Pool<send_info_t> as SendInfoPool;
    interface Pool<send_entry_t> as SendEntryPool;
    interface Queue<send_entry_t *> as SendQueue;

    interface Timer<TMilli> as ExpireTimer;

    interface IPRouting;
    interface ICMP;

    interface LowPowerListening;

    interface Leds;
    
    interface IPAddress;

    interface InternalIPExtension;
  }
} implementation {
  
#ifdef PRINTFUART_ENABLED
#undef dbg
#define dbg(X, fmt, args...)  printfUART(fmt, ## args)
#endif

  enum {
    S_RUNNING,
    S_STOPPED,
    S_STOPPING,
  };
  uint8_t state = S_STOPPED;
  bool radioBusy;
  uint8_t current_local_label = 0;
  ip_statistics_t stats;

  // this in theory could be arbitrarily large; however, it needs to
  // be large enough to hold all active reconstructions, and any tags
  // which we are dropping.  It's important to keep dropped tags
  // around for a while, or else there are pathological situations
  // where you continually allocate buffers for packets which will
  // never complete.

  ////////////////////////////////////////
  //
  //

  table_t recon_cache, forward_cache;


  // table of packets we are currently receiving fragments from, that
  // are destined to us
  reconstruct_t recon_data[N_RECONSTRUCTIONS];

  // table of fragmented flows who are going through us, so we must
  // remember the next hop.
  forward_entry_t forward_data[N_FORWARD_ENT];

  //
  //
  ////////////////////////////////////////

  task void sendTask();

  void reconstruct_clear(void *ent) {
    reconstruct_t *recon = (reconstruct_t *)ent;
    ip_memclr((uint8_t *)&recon->metadata, sizeof(struct ip_metadata));
    recon->timeout = T_UNUSED;
    recon->buf = NULL;
  }

  void forward_clear(void *ent) {
    forward_entry_t *fwd = (forward_entry_t *)ent;
    fwd->timeout = T_UNUSED;
  }

  int forward_unused(void *ent) {
    forward_entry_t *fwd = (forward_entry_t *)ent;
    if (fwd->timeout == T_UNUSED) 
      return 1;
    return 0;
  }

  uint16_t forward_lookup_tag;
  uint16_t forward_lookup_src;
  int forward_lookup(void *ent) {
    forward_entry_t *fwd = (forward_entry_t *)ent;
    if (fwd->timeout > T_UNUSED && 
        fwd->l2_src == forward_lookup_src &&
        fwd->old_tag == forward_lookup_tag) {
      fwd->timeout = T_ACTIVE;
      return 1;
    }
    return 0;
  }
  

  send_info_t *getSendInfo() {
    send_info_t *ret = call SendInfoPool.get();
    if (ret == NULL) return ret;
    ret->refcount = 1;
    ret->failed = FALSE;
    ret->frags_sent = 0;
    return ret;
  }
#define SENDINFO_INCR(X) ((X)->refcount)++
#define SENDINFO_DECR(X) if (--((X)->refcount) == 0) call SendInfoPool.put(X)

  command error_t SplitControl.start() {
    return call RadioControl.start();
  }

  command error_t SplitControl.stop() {
    if (!radioBusy) {
      state = S_STOPPED;
      return call RadioControl.stop();
    } else {
      // if there's a packet in the radio, wait for it to exit before
      // stopping
      state = S_STOPPING;
      return SUCCESS;
    }
  }

  event void RadioControl.startDone(error_t error) {
#ifdef LPL_SLEEP_INTERVAL
    call LowPowerListening.setLocalWakeupInterval(LPL_SLEEP_INTERVAL);
#endif
    if (error == SUCCESS) {
      call ICMP.sendSolicitations();
      state = S_RUNNING;
    }
    signal SplitControl.startDone(error);
  }

  event void RadioControl.stopDone(error_t error) {
    signal SplitControl.stopDone(error);
  }

  event void Boot.booted() {
    call Statistics.clear();

    ip_malloc_init();

    table_init(&recon_cache, recon_data, sizeof(reconstruct_t), N_RECONSTRUCTIONS);
    table_init(&forward_cache, forward_data, sizeof(forward_entry_t), N_FORWARD_ENT);

    table_map(&recon_cache, reconstruct_clear);
    table_map(&forward_cache, forward_clear);

    radioBusy = FALSE;

    call ExpireTimer.startPeriodic(FRAG_EXPIRE_TIME);

    call SplitControl.start();
    return;
  }

  /*
   *  Receive-side code.
   */ 

  /*
   * Logic which must process every received IP datagram.
   *
   *  Each IP packet may be consumed and/or forwarded.
   */
  void signalDone(reconstruct_t *recon) {
    struct ip6_hdr *iph = (struct ip6_hdr *)recon->buf;

    signal IP.recv[recon->nxt_hdr](iph, recon->transport_hdr, &recon->metadata);
    ip_free(recon->buf);
    recon->timeout = T_UNUSED;
    recon->buf = NULL;
  }

  /*
   * Bulletproof recovery logic is very important to make sure we
   * don't get wedged with no free buffers.
   * 
   * The table is managed as follows:
   *  - unused entries are marked T_UNUSED
   *  - entries which 
   *     o have a buffer allocated
   *     o have had a fragment reception before we fired
   *     are marked T_ACTIVE
   *  - entries which have not had a fragment reception during the last timer period
   *     and were active are marked T_ZOMBIE
   *  - zombie receptions are deleted: their buffer is freed and table entry marked unused.
   *  - when a fragment is dropped, it is entered into the table as T_FAILED1.
   *     no buffer is allocated
   *  - when the timer fires, T_FAILED1 entries are aged to T_FAILED2.
   * - T_FAILED2 entries are deleted.  Incomming fragments with tags
   *     that are marked either FAILED1 or FAILED2 are dropped; this
   *     prevents us from allocating a buffer for a packet which we
   *     have already dropped fragments from.
   *
   */ 
  void reconstruct_age(void *elt) {
    reconstruct_t *recon = (reconstruct_t *)elt;
    switch (recon->timeout) {
    case T_ACTIVE:
      recon->timeout = T_ZOMBIE; break; // age existing receptions
    case T_FAILED1:
      recon->timeout = T_FAILED2; break; // age existing receptions
    case T_ZOMBIE:
    case T_FAILED2:
      // deallocate the space for reconstruction
      if (recon->buf != NULL) {
        ip_free(recon->buf);
      }
      recon->timeout = T_UNUSED;
      recon->buf = NULL;
      break;
    }
  }

  void forward_age(void *elt) {
    forward_entry_t *fwd = (forward_entry_t *)elt;
    switch (fwd->timeout) {
    case T_ACTIVE:
      fwd->timeout = T_ZOMBIE; break; // age existing receptions
    case T_FAILED1:
      fwd->timeout = T_FAILED2; break; // age existing receptions
    case T_ZOMBIE:
    case T_FAILED2:
      fwd->s_info->failed = TRUE;
      SENDINFO_DECR(fwd->s_info);
      fwd->timeout = T_UNUSED;
      break;
    }
  }

  void ip_print_heap() {
#ifdef PRINTFUART_ENABLED
    bndrt_t *cur = (bndrt_t *)heap;
    while (((uint8_t *)cur)  - heap < IP_MALLOC_HEAP_SIZE) {
      //printfUART ("heap region start: 0x%x length: %i used: %i\n", 
                  //cur, (*cur & IP_MALLOC_LEN), (*cur & IP_MALLOC_INUSE) >> 15);
      cur = (bndrt_t *)(((uint8_t *)cur) + ((*cur) & IP_MALLOC_LEN));
    }
#endif
  }

  event void ExpireTimer.fired() {