memory.c

#include "memory.h"

/*****************************************************************************
 *
 *              Simple SRAM Dynamic Memory Allocation 
 *
 *****************************************************************************
 * FileName:        sralloc.c
 * Dependencies:    
 * Processor:       PIC18F with CAN
 * Compiler:       	C18 02.20.00 or higher
 * Linker:          MPLINK 03.40.00 or higher
 * Company:         Microchip Technology Incorporated
 *
 * Software License Agreement
 *
 * The software supplied herewith by Microchip Technology Incorporated
 * (the "Company") is intended and supplied to you, the Company's
 * customer, for use solely and exclusively with products manufactured
 * by the Company. 
 *
 * The software is owned by the Company and/or its supplier, and is 
 * protected under applicable copyright laws. All rights are reserved. 
 * Any use in violation of the foregoing restrictions may subject the 
 * user to criminal sanctions under applicable laws, as well as to 
 * civil liability for the breach of the terms and conditions of this 
 * license.
 *
 * THIS SOFTWARE IS PROVIDED IN AN "AS IS" CONDITION. NO WARRANTIES, 
 * WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING, BUT NOT LIMITED 
 * TO, IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 
 * PARTICULAR PURPOSE APPLY TO THIS SOFTWARE. THE COMPANY SHALL NOT, 
 * IN ANY CIRCUMSTANCES, BE LIABLE FOR SPECIAL, INCIDENTAL OR 
 * CONSEQUENTIAL DAMAGES, FOR ANY REASON WHATSOEVER.
 *
 *
 * This is a simple dynamic memory allocation module. The following are the 
 * supported services:
 *
 * unsigned char * NEAR SRAMalloc(NEAR unsigned char nBytes) 
 * void SRAMfree(unsigned char * NEAR pSRAM)
 * void SRAMInitHeap(void)
 *
 * This version of the dynamic memory allocation limits the segment size
 * to 126 bytes. This is specifically designed such to enable better
 * performance by limiting pointer manipulation.
 *
 *
 * How it works:
 * The model is based on a simple form of a linked list. A block of memory
 * refered to as the dynamic heap is split into segments. Each segment 
 * has a single byte header that references the next segment in the list
 * as well as indicating whether the segment is allocated. Consiquently 
 * the reference implicitly identifies the length of the segment. 
 *
 * This method also enables the possibility of allowing a large number
 * of memory allocations. The maximum is limited by the defined heap size.
 *
 * SRAMalloc() is used to split or merge segments to be allocated.
 * SRAMfree() is used to release segments.
 * 
 * Example:
 *	----------
 *	|  0x7F  |	0x200   Header Seg1
 *	|        |
 *	|        |
 *	|        |
 *	|        | 
 *	|        |
 *	|        |
 *	|  0x89  |  0x27F	Header Seg2 (allocated)
 *	|        |
 *	|        |
 *	|  0x77  |  0x288	Header Seg3
 *	|        |
 *	|        |
 *	|        |
 *	|        |
 *	|        |
 *	|        |
 *	|        |
 *	|  0x00  |	0x2FF 	Tail
 *	----------
 *
 *	
 *	Bit 7	Bit 6 	Bit 5	Bit 4	Bit 3	Bit 2	Bit 1	Bit 0
 *	
 *	Alloc	------------- reference to next Header --------------
 *
 *	
 * Recomendations:
 * Although this model will allow dynamic allocation down to a single byte,
 * doing so sacrifices performance. With more segments within the heap, more
 * time is required to attempt to allocate memory. Plus every segment requires 
 * a header byte; therefore, smaller segments require more memory. There is 
 * also the possibility of fragmentation, which could ultimately doom an 
 * application by reducing the largest allocatable block of memory. Thus the 
 * recomendation is to allocate at least 8 bytes of memory.  
 *
 *	
 *
 * Author               Date        Version 	Comment
 *~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 * Ross Fosler			05/25/03	v1.03		...	First release
 * 
 *****************************************************************************/






/*********************************************************************
 * Segment header data type
 ********************************************************************/
typedef union _SALLOC
{
	unsigned char byte;
	struct _BITS
	{
		unsigned count:7;
		unsigned alloc:1;	
	}bits;
}SALLOC;





/*********************************************************************
 * Reserve the memory heap
 ********************************************************************/
#pragma	udata	_SRAM_ALLOC_HEAP
unsigned char _uDynamicHeap[MAX_HEAP_SIZE];


/*********************************************************************
 * Set the memory type
 ********************************************************************/
#if defined(NEAR_MODEL)
#pragma		udata access	_SRAM_ALLOC
#else
#pragma		udata _SRAM_ALLOC
#endif



/*********************************************************************
 * Private function declarations
 ********************************************************************/
NEAR unsigned char _SRAMmerge(SALLOC * NEAR pSegA);




/*********************************************************************
 * Function:        unsigned char * SRAMalloc(unsigned char length)
 *
 * PreCondition:    A memory block must be allocated in the linker, 
 *					and	the memory headers and tail must already be 
 *					set via the	function SRAMInitHeap().
 *
 * Input:        	unsigned char nBytes - Number of bytes to allocate.	
 *                  
 * Output:         	unsigned char * - A pointer to the requested block
 *					of memory.
 *
 * Side Effects:    
 *
 * Overview:        This functions allocates a chunk of memory from
 *					the heap. The maximum segment size for this 
 *					version is 126 bytes. If the heap does not have
 *					an available segment of sufficient size it will
 *					attempt to create a segment; otherwise a NULL 
 *					pointer is returned. If allocation is succeessful
 *					then a pointer to the requested block is returned.
 *
 * Note:            The calling function must maintain the pointer
 *					to correctly free memory at runtime.
 ********************************************************************/
unsigned char * NEAR SRAMalloc(NEAR unsigned char nBytes)
{
	SALLOC * NEAR pHeap;
	SALLOC * NEAR temp;
	NEAR SALLOC segHeader;
	NEAR unsigned char segLen;
	
	// Do not allow allocation above the max minus one bytes
	if (nBytes > (_MAX_SEGMENT_SIZE - 1)) return (0);
	
	// Init the pointer to the heap
	pHeap = (SALLOC *)_uDynamicHeap;
	
	while (1)
	{
		// Get the header of the segment
		segHeader = *pHeap;
		
		// Extract the segment length from the segment
		segLen = segHeader.bits.count - 1;

		// A null segment indicates the end of the table
		if (segHeader.byte == 0) return (0);
				
		// If this segment is not allocated then attempt to allocate it
		if (!(segHeader.bits.alloc))
		{
			// If the free segment is too small then attempt to merge
			if (nBytes > segLen)
			{
				// If the merge fails them move on to the next segment
				if (!(_SRAMmerge(pHeap))) pHeap += segHeader.bits.count;	
			}
			else
		
			// If the segment length matches the request then allocate the
			// header and return the pointer
			if (nBytes == segLen)
			{
				// Allocate the segment
				(*pHeap).bits.alloc = 1;  
					
				// Return the pointer to the caller
				return ((unsigned char *)(pHeap + 1));
			}
	
			// Else create a new segment
			else 
			{
				// Reset the header to point to a new segment
				(*pHeap).byte = nBytes + 0x81;
	
				// Remember the pointer to the first segment
				temp = pHeap + 1;
	
				// Point to the new segment
				pHeap += (nBytes + 1);
	
				// Insert the header for the new segment
				(*pHeap).byte = segLen - nBytes;  
					
				// Return the pointer to the user
				return ((unsigned char *) temp);
			}			
		}

		// else set the pointer to the next segment header in the heap
		else 
		{
			pHeap += segHeader.bits.count;
		}
	}
}



/*********************************************************************
 * Function:        void SRAMfree(unsigned char * pSRAM)
 *
 * PreCondition:  	The pointer must have been returned from a 
 *					previously allocation via SRAMalloc().  
 *
 * Input:        	unsigned char * pSRAM - pointer to the allocated 	
 *                  
 * Output:         	void
 *
 * Side Effects:    
 *
 * Overview:       	This function de-allocates a previously allocated
 *					segment of memory. 
 *
 * Note:            The pointer must be a valid pointer returned from
 *					SRAMalloc(); otherwise, the segment may not be 
 *					successfully de-allocated, and the heap may be 
 *					corrupted.
 ********************************************************************/
void SRAMfree(unsigned char * NEAR pSRAM)
{	
	// Release the segment
	(*(SALLOC *)(pSRAM - 1)).bits.alloc = 0;
}



/*********************************************************************
 * Function:        void SRAMInitHeap(void)
 *
 * PreCondition:    
 *
 * Input:  			void      	
 *                  
 * Output:         	void
 *
 * Side Effects:    
 *
 * Overview:      	This function initializes the dynamic heap. It 
 *					inserts segment headers to maximize segment space.
 *
 * Note:            This function must be called at least one time. 
 *					And it could be called more times to reset the 
 *					heap.
 ********************************************************************/
void SRAMInitHeap(void)
{
	unsigned char * NEAR pHeap;
	NEAR unsigned int count;
	
	pHeap = _uDynamicHeap;
	count = _MAX_HEAP_SIZE;

	while (1)
	{
		if (count > _MAX_SEGMENT_SIZE)
		{
			*pHeap = _MAX_SEGMENT_SIZE;
			pHeap += _MAX_SEGMENT_SIZE;
			count = count - _MAX_SEGMENT_SIZE;
		}
		else
		{
			*pHeap = count;
			*(pHeap + count) = 0;
			return;
		}
	}
}




/*********************************************************************
 * Function:        unsigned char _SRAMmerge(SALLOC * NEAR pSegA)
 *
 * PreCondition:    
 *
 * Input:      		SALLOC * NEAR pSegA - pointer to the first segment.  	
 *                  
 * Output:         	usnigned char - returns the length of the 
 *					merged segment or zero if failed to merge.
 *
 * Side Effects:    
 *
 * Overview:        This function tries to merge adjacent segments
 *					that have not been allocated. The largest possible
 *					segment is merged if possible.
 *
 * Note:            
 ********************************************************************/
NEAR unsigned char _SRAMmerge(SALLOC * NEAR pSegA)
{
	SALLOC * NEAR pSegB;
	NEAR SALLOC uSegA, uSegB, uSum;
	

	// Init the pointer to the heap
	pSegB = pSegA + (*pSegA).byte;
		
	// Extract the headers for faster processing
	uSegA = *pSegA;
	uSegB = *pSegB;
	
	// Quit if the tail has been found
	if (uSegB.byte == 0) return (0);
	
	// If either segment is allocated then do not merge
	if (uSegA.bits.alloc || uSegB.bits.alloc) return (0);
		
	// If the first segment is max then nothing to merge
	if (uSegA.bits.count == _MAX_SEGMENT_SIZE) return (0);
		
	// Get the sum of the two segments		
	uSum.byte = uSegA.byte + uSegB.byte;	
		
		
	// If the sum of the two segments are > than the largest segment
	// then create a new segment equal to the max segment size and
	// point to the next segments			
	if ((uSum.byte) > _MAX_SEGMENT_SIZE)
	{
		(*pSegA).byte = _MAX_SEGMENT_SIZE;
		pSegA += _MAX_SEGMENT_SIZE; //(*pSeg1).byte;  
		pSegB += uSegB.byte; //(*pSeg2).byte ;   
		(*pSegA).byte = pSegB - pSegA;
		
		return (_MAX_SEGMENT_SIZE);
	}
	// Else combine the two segments into one segment and
	// do not adjust the pointers to the next segment
	else
	{
		return ((*pSegA).byte = uSum.byte);
	}
}