tinyalloc.nc

无线通信的主要编程软件,是无线通信工作人员的必备工具,关天相关教程我会在后续传上.

// $Id: TinyAlloc.nc,v 1.2 2003/10/07 21:46:23 idgay Exp $

/*									tab:4
 * "Copyright (c) 2000-2003 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."
 *
 * Copyright (c) 2002-2003 Intel Corporation
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE     
 * file. If you do not find these files, copies can be found by writing to
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, 
 * 94704.  Attention:  Intel License Inquiry.
 */
/*
 * Authors:		Sam Madden, Phil Levis
 * Modification History:  10/6/2002 SRM -- added freeBytes
 *
 */

/*
 * TINY_ALLOC is a simple, handle-based compacting memory manager.  It
 * allocates bytes from a fixed size frame and returns handles
 * (pointers to pointers) into that frame.  Because it components handles,
 * TINY_ALLOC can move memory around in the frame without changing all
 * the external references.  Moving memory is a good thing because it
 * allows frame compacting and tends to reduce wasted space.  Handles
 * can be accessed via a double dereference (**), and a single
 * dereference can be used wherever a pointer is needed, but if a
 * single dereference is to be stored, the handle must be locked first
 * as otherwise TINY_ALLOC may move the handle and make the reference
 * invalid.
 *
 * Example:
 *
 * Handle foo; // A handle to 20 allocated bytes
 * (*foo)[12] // The 12th byte of foo
 * **foo      // The 0th byte of foo
 *
 * Like all good TinyOS components, TINY_ALLOC is split phase with
 * respect to allocation and compaction.  Allocation/reallocation
 * completion is signalled via a TINY_ALLOC_COMPLETE signal and
 * compaction via a TINY_ALLOC_COMPACT_COMPLETE signal.  All other
 * operations complete and return in a single phase. Note that
 * compaction may be triggered automatically from allocation; in this
 * case a COMPACT_COMPLETE event is not generated.
 *
 * Handles are laid out in the frame as follows:
 *
 *  [LOCKED][SIZE][user data] 
 *
 * Where: 
 *   LOCKED     : a single bit indicating if the handle is locked 
 *   SIZE       : 7 bits representing the size of the handle 
 *   user data  : user-requested number of bytes (**h) points to
 *               [user data], not [LOCKED].
 *
 * Calling TOS_COMMAND(TINY_ALLOC_SIZE(h)) returns the size of [user
 * data] (note that the internal function size() returns the size of
 * the entire handle, including the header byte.)
 * 
 */

/**
 * @author Sam Madden
 * @author Phil Levis
 */
   
   


module TinyAlloc {
  provides {
    interface StdControl;
    interface MemAlloc;
    command void allocDebug();
  }
  uses {
    interface Leds;
  }
}


implementation {
  enum {
    FRAME_SIZE = 256,
    FREE_SIZE  = FRAME_SIZE >> 3,
    MAX_SIZE   = 32765,
    HEADER_SIZE = 2,
    MAX_HANDLES = 20
  };

  uint8_t mFrame[FRAME_SIZE];  //the heap
  uint8_t mFree[FREE_SIZE];    //free bit map
  int8_t mAllocing;                    //are we allocating?
  int8_t mCompacting;                  //are we compacting?
  int16_t mSize;                       //how many bytes are we allocing?
  int16_t mLast;                       //where were we in the last task invocation
  Handle *mHandle;                   //handle we are allocating
  int8_t **mTmpHandle;                 //temporary handle for realloc
  Handle mOldHandle;                 //old user handle for realloc
  int8_t *mHandles[MAX_HANDLES];       //handles we know about
  int8_t mReallocing;                  //are we mReallocing
  int8_t mCompacted;                   //already mCompacted this allocation
  int8_t mNeedFree;                    //looking for free bits in current byte?
  int16_t mContig;                     //mContig bytes seen so far 
  int16_t mStartByte;                  //start of free section (in bytes)
  uint16_t mFreeBytes;

  /* DEBUGGING FIELDS */
  //  int8_t buf[512];
  //int16_t cur;
  //int16_t len;

  void doAlloc(int16_t startByte, int16_t endByte);
  void shiftUp(Handle handle, int bytes);
  int16_t start_offset(int8_t *ptr);
  void setFreeBits(int16_t startByte, int16_t endByte, int8_t on);
  void remapAddr(int8_t *oldAddr, int8_t *newAddr);
  int8_t isValid(Handle h);
  int16_t getSize(int8_t *p);
  int8_t isLocked(int8_t *ptr);
  int8_t finish_realloc(Handle *handle, int8_t success);
  Handle getH(int8_t *p);
  int16_t getNewHandleIdx();
  void markHandleFree(Handle hand);

  static inline Handle ToHandle(int8_t* ptr) {return (Handle)(&ptr);}
  static inline int8_t* deref(Handle h) {return (int8_t*)(*h);}
  
  task void compactTask();
  task void allocTask();
  task void reallocDone();

  command result_t MemAlloc.compact() {
    if (!mCompacting && !mAllocing) {
      post compactTask();
    }
    return SUCCESS;
  }

  command result_t StdControl.init()   {
    int16_t i;
    mAllocing = 0;
    mReallocing = 0;
    for (i = 0; i < FREE_SIZE >> 4; i++) {
      ((int32_t *)mFree)[i] = 0;
    }
    for (i = 0; i < MAX_HANDLES; i++) {
      mHandles[i] = 0;
    }
    mFreeBytes = FRAME_SIZE;
    return SUCCESS;
  }

  command result_t StdControl.start() {
    return SUCCESS;
  }

  command result_t StdControl.stop() {
    return SUCCESS;
  }

  command result_t MemAlloc.allocate(HandlePtr handlePtr, int16_t size) {
    if (size > MAX_SIZE || mAllocing) {

      return FAIL;
    }
    mAllocing = 1;
    mSize = size + HEADER_SIZE; //need extra bytes for header info
    mHandle = handlePtr;
    mCompacted = 0;
    mNeedFree = 0;
    mContig = 0;
    mLast = 0;
    mStartByte = 0;
    mFreeBytes -= mSize;
    post allocTask();
    return SUCCESS;
  }
  
  task void allocTask() {
    int16_t endByte;
    int16_t i, j;
    
    i = mLast++;
    if (i == FREE_SIZE) {
      if (mCompacted) { //try to compact if can't allocate
	//already mCompacted -- signal failure
	mAllocing = 0;
	if (mReallocing) {
	  finish_realloc(mHandle, 0);
	}
	else {
	  signal MemAlloc.allocComplete(mHandle, FAIL);
	}
      }
      else {
	mCompacted = 1;
	//CLR_RED_LED_PIN();
	//try compacting
	post compactTask();
      }
      return;
    }

    if (mNeedFree && mFree[i] != 0xFF) { //some free space
      mStartByte = i << 3;
      for (j = 0; j < 8; j++) {
	if (mFree[i] & (1 << j)) {
	  if (mContig >= mSize) { //is enough free space
	    //alloc it and return
	    endByte = mStartByte + mSize;
	    doAlloc(mStartByte, endByte);
	    return;
	  }
	  else {
	    mStartByte += (mContig + 1);
	    mContig = 0;
	  }
	}
	else {
	  mContig++;
	}
      }

      if (mContig >= mSize) {
	endByte = mStartByte + mSize;
	doAlloc(mStartByte,endByte);
	//alloc it and return
	return;
      }
      else {
	//some free space at end of byte, but need more
	mNeedFree = 0;
      }
    }
    else if (mNeedFree == 0) { //mNeedFree sez there are free bits
      //in the current byte, and we should scan to find them on
      //the next pass
      if (mFree[i] == 0) {
	mContig += 8;
      }
      else {
	for (j = 0; j < 8; j++) {
	  if ((mFree[i] & (1 << j)) == 0) {
	    mContig++;
	  }
	  else {
	    break;
	  }
	}
      }
      if (mContig >= mSize) {
	endByte = mStartByte + mSize;
	doAlloc(mStartByte, endByte);
	//alloc it and return
	return;
      }
      else if (mFree[i] != 0) {
	mContig = 0;  //didn't find the needed amount of space
	mNeedFree = 1;
	mLast--; //retry this byte
      }
    }
    post allocTask();
  }

  void doAlloc(int16_t startByte, int16_t endByte) {
    int16_t newIdx = getNewHandleIdx();
    if (newIdx == -1) {
      mAllocing = 0;
      signal MemAlloc.allocComplete(mHandle, FAIL); //signal failure
      return;
    }
    
    
    *(int16_t *)(&mFrame[startByte]) = (endByte - startByte) & 0x7FFF;
    
    //WARNING -- not going through standard accessors
    
    mHandles[newIdx] = (int8_t *)((&mFrame[startByte]) + HEADER_SIZE);
    *mHandle = &mHandles[newIdx];
    
    //mark bits
    setFreeBits(startByte,endByte, 1);
    
    mAllocing = 0;
    if (mReallocing) {
      finish_realloc(mHandle,1);
    }
    else {
      signal MemAlloc.allocComplete(mHandle, SUCCESS);
    }
  }

  task void compactTask() {
    int16_t i;
    uint8_t c;
    int8_t *p;
    int8_t endFree = 0;
    
    if (mCompacting == 0) {
      mContig = 0;
      mLast = 0;
      mCompacting = 1;
      mStartByte = 0;
    }
    c = mFree[mLast++];
    if (mLast == FREE_SIZE)
      goto done_compact;
    
    //call Leds.yellowToggle();
    //process:  scan forward in free bitmap, looking for runs of free space
    //at end of run, move bytes up
    
    if (c == 0) {  //byte not used at all
      mContig += 8;
    }
    else {
      if (c != 0xFF){ //byte not fully used
	for (i = 0; i < 8; i++) {
	  if ((c & (1 << i)) == 0) {
	    mContig++;
	    endFree = 1; //endFree sez the last bit of this byte was free
	  }
	  else if (mContig == 0) { //bit not free, no compaction to do
	    mStartByte++;
	    endFree = 0;
	  }
	  else {  //bit not free, but need to compact
	    endFree = 0;
	    break;
	  }
	}
      }

      if (mContig > 0 && !endFree) { //need to compact?
	p = (int8_t *)&(mFrame[mStartByte + mContig + HEADER_SIZE]); //get the handle
	if (!isLocked(p)) {
	  Handle h = getH(p);

	  if (h == NULL) {
	    dbg(DBG_USR1, "BAD NEWS -- INVALID HANDLE START IN COMPACT.\n");
	    goto done_compact;
	  } 
	  dbg(DBG_USR1,"compacting, from %d, %d bytes\n", mStartByte + mContig + HEADER_SIZE, mContig);
	  shiftUp((Handle)h, mContig);
	  mStartByte += (getSize(*h) >> 3) << 3;
	} else {
	  //printf ("SOMETHING LOCKED, at %d", VAR(startByte) +
	  //VAR(mContig) + 1);
	  mStartByte += ((getSize(p) + mContig) >> 3) << 3;
	  //make sure we don't retry the same byte again if this
	  //handle is locked note that this can lead to holes of fewer
	  //than 8 bytes at the end of allocations which occupy fewer
	  //than 8 bytes