ra.c

Lido PXA270平台开发板的最新BSP,包括源代码

/* -*- c-file-style: "img" -*-
<module>
* Name         : ra.c
* Title        : Resource Allocator
* Author       : Marcus Shawcroft
* Created      : 14 May 2003
*
* Copyright    : 2003 by Imagination Technologies Limited.
*                All rights reserved.  No part of this software, either
*                material or conceptual may be copied or distributed,
*                transmitted, transcribed, stored in a retrieval system
*                or translated into any human or computer language in any
*                form by any means, electronic, mechanical, manual or
*                other-wise, or disclosed to third parties without the
*                express written permission of Imagination Technologies
*                Limited, Unit 8, HomePark Industrial Estate,
*                King's Langley, Hertfordshire, WD4 8LZ, U.K.
*
* Description :
*
* Implements generic resource allocation. The resource
* allocator was originally intended to manage address spaces in
* practice the resource allocator is generic and can manages arbitrary
* sets of integers.
*
* Resources are allocated from arenas. Arena's can be created with an
* initial span of resources. Further resources spans can be added to
* arenas. A call back mechanism allows an arena to request further
* resource spans on demand.
*
* Each arena maintains an ordered list of resource segments each
* described by a boundary tag. Each boundary tag describes a segment
* of resources which are either 'free', available for allocation, or
* 'busy' currently allocated. Adjacent 'free' segments are always
* coallesced to avoid fragmentation.
*
* For allocation, all 'free' segments are kept on lists of 'free'
* segments in a table index by log2(segment size). ie Each table index
* n holds 'free' segments in the size range 2**(n-1) -> 2**n.
*
* Allocation policy is based on an *almost* best fit
* stratedy. Choosing any segment from the appropriate table entry
* guarantees that we choose a segment which is with a power of 2 of
* the size we are allocating.
*
* Allocated segments are inserted into a self scaling hash table which
* maps the base resource of the span to the relevant boundary
* tag. This allows the code to get back to the bounary tag without
* exporting explicit boundary tag references through the API.
*
* Each arena has an associated quantum size, all allocations from the
* arena are made in multiples of the basic quantum.
*
* On resource exhaustion in an arena, a callback if provided will be
* used to request further resources. Resouces spans allocated by the
* callback mechanism are delimited by special boundary tag markers of
* zero span, 'span' markers. Span markers are never coallesced. Span
* markers are used to detect when an imported span is completely free
* and can be deallocated by the callback mechanism.
* Version	  : $Revision: 1.15 $
* Modifications	: 
* $Log: ra.c $
*
</module>
*/

/* Issues:
 * - flags, flags are passed into the resource allocator but are not currently used.
 * - determination, of import size, is currently braindead.
 * - debug code should be moved out to own module and #ifdef'd
 */

#include "pvr_debug.h"
#include "img_defs.h"
#include "services.h"
#include "hash.h"
#include "pool.h"
#include "ra.h"
#include "hostfunc.h"

/* The initial, and minimum size of the live address -> boundary tag
   structure hash table. The value 64 is a fairly arbitrary
   choice. The hash table resizes on demand so the value choosen is
   not critical. */
#define MINIMUM_HASH_SIZE (64)

/* boundary tags, used to describe a resource segment */
struct _BT_
{
	enum bt_type
	{
		btt_span,				/* span markers */
		btt_free,				/* free resource segment */
		btt_live				/* allocated resource segment */
	} type;

	/* The base resource and extent of this segment */
	IMG_UINTPTR_T base;
	IMG_SIZE_T uSize;

	/* doubly linked ordered list of all segments within the arena */
	struct _BT_ *pNextSegment;
	struct _BT_ *pPrevSegment;
	/* doubly linked un-ordered list of free segments. */
	struct _BT_ *pNextFree;
	struct _BT_ *pPrevFree;
	/* a user reference associated with this span, user references are
	 * currently only provided in the callback mechanism */
	void *pRef;
};
typedef struct _BT_ BT;

/* resource allocator does not keep static data, instead all state information
   is kept in the ra_state structure. */
struct _RA_STATE_
{
	/* pool of struct arena's */
	POOL *pArenaPool;

    /* pool of BT's */
	POOL *pBTPool;

	HASH_STATE *pHashState;
};

/* resource allocation arena */
struct _RA_ARENA_
{
	/* arena name for diagnostics output */
	char *name;

	/* allocations within this arena are quantum sized */
	IMG_UINT32 uQuantum;

	/* import interface, if provided */
	IMG_BOOL (*pImportAlloc)(void *,
                             IMG_SIZE_T uSize,
                             IMG_SIZE_T *pActualSize,
                             void **pRef,
                             IMG_UINT32 uFlags,
                             IMG_UINTPTR_T *pBase);
	void (*pImportFree) (void *,
                         IMG_UINTPTR_T,
                         void *pRef);

    /* arbitrary handle provided by arena owner to be passed into the
     * import alloc and free hooks */
	void *pImportHandle;

	/* head of list of free boundary tags for indexed by log2 of the
	   boundary tag size */
#define FREE_TABLE_LIMIT 32
  
	/* power-of-two table of free lists */
	BT *aHeadFree [FREE_TABLE_LIMIT];

	/* resource ordered segment list */
	BT *pHeadSegment;
	BT *pTailSegment;

	/* segment address to boundary tag hash table */
	HASH_TABLE *pSegmentHash;

	/* pointer back to ra_state structure */
	RA_STATE *pState;
	
#ifdef RA_STATS
	RA_STATISTICS sStatistics;
#endif
};

void
RA_Dump (RA_ARENA *pArena);

#ifdef RA_STATS
void
RA_Stats (RA_ARENA *pArena);
#endif

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _RequestAllocFail

	PURPOSE:    Default callback allocator used if no callback is
  	            specified, always fails to allocate further resources to the
	            arena.
	
	PARAMETERS:	In:  _h - callback handle
	            In:  _uSize - requested allocation size
	            Out: _pActualSize - actual allocation size
	            In:  _pRef - user reference
	            In:  _uflags - allocation flags
	            In:  _pBase - receives allocated base
	            
	RETURNS:	IMG_FALSE, this function always fails to allocate.
</function>
-----------------------------------------------------------------------------*/
static IMG_BOOL
_RequestAllocFail (void *_h,
                  IMG_SIZE_T _uSize,
                  IMG_SIZE_T *_pActualSize, 
				  void **_pRef,
                  IMG_UINT32 _uFlags,
                  IMG_UINTPTR_T *_pBase)
{
	UNREFERENCED_PARAMETER (_h);
	UNREFERENCED_PARAMETER (_uSize);
	UNREFERENCED_PARAMETER (_pActualSize);
	UNREFERENCED_PARAMETER (_pRef);
	UNREFERENCED_PARAMETER (_uFlags);
	UNREFERENCED_PARAMETER (_pBase);

	return IMG_FALSE;
}

/* todo: boilterplate */
static IMG_UINT32
log2 (IMG_SIZE_T n)
{
	IMG_UINT32 l = 0;
	n>>=1;
	while (n>0)
    {
		n>>=1;
		l++;
    }
	return l;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _SegmentListInsertAfter

	PURPOSE:    Insert a boundary tag into an arena segment list after a
	            specified boundary tag.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pInsertionPoint - the insertion point.
	            In:  pBT - the boundary tag to insert.
	            
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
static void
_SegmentListInsertAfter (RA_ARENA *pArena,
                         BT *pInsertionPoint, 
                         BT *pBT)
{
	PVR_ASSERT (pArena != IMG_NULL);
	PVR_ASSERT (pInsertionPoint != IMG_NULL);

	pBT->pNextSegment = pInsertionPoint->pNextSegment;
	pBT->pPrevSegment = pInsertionPoint;
	if (pInsertionPoint->pNextSegment == IMG_NULL)
		pArena->pTailSegment = pBT;
	else
		pInsertionPoint->pNextSegment->pPrevSegment = pBT; 
	pInsertionPoint->pNextSegment = pBT;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _SegmentListInsert

	PURPOSE:    Insert a boundary tag into an arena segment list at the
 	            appropriate point.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pBT - the boundary tag to insert.
	            
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
static void
_SegmentListInsert (RA_ARENA *pArena, BT *pBT)
{
	/* insert into the segment chain */
	if (pArena->pHeadSegment == IMG_NULL)
    {
		pArena->pHeadSegment = pArena->pTailSegment = pBT;
		pBT->pNextSegment = pBT->pPrevSegment = IMG_NULL;
    }
	else
    {
		BT *pBTScan;
		pBTScan = pArena->pHeadSegment;
		while (pBTScan->pNextSegment != IMG_NULL 
			   && pBT->base >= pBTScan->pNextSegment->base)
			pBTScan = pBTScan->pNextSegment;
		_SegmentListInsertAfter (pArena, pBTScan, pBT);
    }
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _SegmentListRemove

	PURPOSE:    Remove a boundary tag from an arena segment list.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pBT - the boundary tag to remove.
	            
	RETURNS:	None
</function>
-----------------------------------------------------------------------------*/
static void
_SegmentListRemove (RA_ARENA *pArena, BT *pBT)
{
	if (pBT->pPrevSegment == IMG_NULL)
		pArena->pHeadSegment = pBT->pNextSegment;
	else
		pBT->pPrevSegment->pNextSegment = pBT->pNextSegment;
  
	if (pBT->pNextSegment == IMG_NULL)
		pArena->pTailSegment = pBT->pPrevSegment;
	else
		pBT->pNextSegment->pPrevSegment = pBT->pPrevSegment;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _SegmentSplit

	PURPOSE:    Split a segment into two, maintain the arena segment list. The
	            boundary tag should not be in the free table. Neither the
	            original or the new neighbour bounary tag will be in the free
	            table.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pBT - the boundary tag to split.
	            In:  uSize - the required segment size of boundary tag after
	                 splitting.
	            
	RETURNS:	New neighbour boundary tag.
	
</function>
-----------------------------------------------------------------------------*/
static BT *
_SegmentSplit (RA_ARENA *pArena, BT *pBT, IMG_SIZE_T uSize)
{
	BT *pNeighbour;

	PVR_ASSERT (pArena != IMG_NULL);
	PVR_ASSERT (pArena->pState != IMG_NULL);
	
	pNeighbour = POOL_Alloc (pArena->pState->pBTPool);
	if (pNeighbour==IMG_NULL)
		return IMG_NULL;
  
	pNeighbour->pPrevSegment = pBT;
	pNeighbour->pNextSegment = pBT->pNextSegment;
	if (pBT->pNextSegment == IMG_NULL)
		pArena->pTailSegment = pNeighbour;
	else
		pBT->pNextSegment->pPrevSegment = pNeighbour;
	pBT->pNextSegment = pNeighbour;

	pNeighbour->type = btt_free;
	pNeighbour->uSize = pBT->uSize - uSize;
	pNeighbour->base = pBT->base + uSize;
	pNeighbour->pRef = pBT->pRef;
	pBT->uSize = uSize;
	return pNeighbour;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _FreeListInsert

	PURPOSE:    Insert a boundary tag into an arena free table.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pBT - the boundary tag.
	            
	RETURNS:	None
	
</function>
-----------------------------------------------------------------------------*/
static void
_FreeListInsert (RA_ARENA *pArena, BT *pBT)
{
	IMG_UINT32 uIndex;
	uIndex = log2 (pBT->uSize);
	pBT->type = btt_free;
	pBT->pNextFree = pArena->aHeadFree [uIndex];
	pBT->pPrevFree = IMG_NULL;
	if (pArena->aHeadFree[uIndex] != IMG_NULL)
		pArena->aHeadFree[uIndex]->pPrevFree = pBT;
	pArena->aHeadFree [uIndex] = pBT;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _FreeListRemove

	PURPOSE:    Remove a boundary tag from an arena free table.
	
	PARAMETERS:	In:  pArena - the arena.
	            In:  pBT - the boundary tag.
	            
	RETURNS:	None
	
</function>
-----------------------------------------------------------------------------*/
static void
_FreeListRemove (RA_ARENA *pArena, BT *pBT)
{
	IMG_UINT32 uIndex;
	uIndex = log2 (pBT->uSize);
	if (pBT->pNextFree != IMG_NULL)
		pBT->pNextFree->pPrevFree = pBT->pPrevFree;
	if (pBT->pPrevFree == IMG_NULL)
		pArena->aHeadFree[uIndex] = pBT->pNextFree;
	else
		pBT->pPrevFree->pNextFree = pBT->pNextFree;
}

/*----------------------------------------------------------------------------
<function>
	FUNCTION:   _BuildSpanMarker

	PURPOSE:    Construct a span marker boundary tag.
	
	PARAMETERS:	In:  pArena - arena to contain span marker
	            In:  base - the base of the bounary tag.