//                                        Ruler
//       1         2         3         4         5         6         7         8
//345678901234567890123456789012345678901234567890123456789012345678901234567890

    /********************************************************************/
    /*                                                                  */
    /*   The standard layout.                                           */
    /*                                                                  */
    /*   The standard layout for 'cpp' files in this code is as         */
    /*   follows:                                                       */
    /*                                                                  */
    /*      1. Include files.                                           */
    /*      2. Constants local to the class.                            */
    /*      3. Data structures local to the class.                      */
    /*      4. Data initializations.                                    */
    /*      5. Static functions.                                        */
    /*      6. Class functions.                                         */
    /*                                                                  */
    /*   The constructor is typically the first function, class         */
    /*   member functions appear in alphabetical order with the         */
    /*   destructor appearing at the end of the file.  Any section      */
    /*   or function this is not required is simply omitted.            */
    /*                                                                  */
    /********************************************************************/

#include "InterfacePCH.hpp"

#include "Assembly.hpp"
#include "Prefetch.hpp"
#include "Spinlock.hpp"
#include "ZoneHeap.hpp"

    /********************************************************************/
    /*                                                                  */
    /*   Constants local to the class.                                  */
    /*                                                                  */
    /*   The constants supplied here try to make the layout of the      */
    /*   the caches easier to understand and update.                    */
    /*                                                                  */
    /********************************************************************/

CONST SBIT32 AlignmentMask			  = (sizeof(double)-1);
CONST SBIT32 FindCacheSize			  = 2048;
CONST SBIT32 FindCacheThreshold		  = 0;
CONST SBIT32 FindSize				  = 1024;
CONST SBIT32 Stride1				  = 1024;
CONST SBIT32 Stride2				  = 1024;
CONST SBIT32 ZonePageSize			  = 4096;

    /********************************************************************/
    /*                                                                  */
    /*   The description of the heap.                                   */
    /*                                                                  */
    /*   A heap is a collection of fixed sized allocation caches.       */
    /*   An allocation cache consists of an allocation size, the        */
    /*   number of pre-built allocations to cache, a chunk size and     */
    /*   a parent page size which is sub-divided to create elements     */
    /*   for this cache.  A heap consists of two arrays of caches.      */
    /*   Each of these arrays has a stride (i.e. 'Stride1' and          */
    /*   'Stride2') which is typically the smallest common factor of    */
    /*   all the allocation sizes in the array.                         */
    /*                                                                  */
    /********************************************************************/

STATIC ROCKALL::CACHE_DETAILS Caches1[] =
	{
	    //
	    //   Bucket   Size Of   Bucket   Parent
	    //    Size     Cache    Chunks  Page Size
		//
		{     4096,        8,    65536,    65536 },
		{ 0,0,0,0 }
	};

STATIC ROCKALL::CACHE_DETAILS Caches2[] =
	{
	    //
	    //   Bucket   Size Of   Bucket   Parent
	    //    Size     Cache    Chunks  Page Size
		//
		{     5120,        4,    65536,    65536 },
		{     6144,        4,    65536,    65536 },
		{     7168,        4,    65536,    65536 },
		{     8192,        8,    65536,    65536 },
		{     9216,        0,    65536,    65536 },
		{    10240,        0,    65536,    65536 },
		{    12288,        0,    65536,    65536 },
		{    16384,        2,    65536,    65536 },
		{    21504,        0,    65536,    65536 },
		{    32768,        0,    65536,    65536 },

		{    65536,        0,    65536,    65536 },
		{    65536,        0,    65536,    65536 },
		{ 0,0,0,0 }
	};

    /********************************************************************/
    /*                                                                  */
    /*   The description bit vectors.                                   */
    /*                                                                  */
    /*   All heaps keep track of allocations using bit vectors.  An     */
    /*   allocation requires 2 bits to keep track of its state.  The    */
    /*   following array supplies the size of the available bit         */
    /*   vectors measured in 32 bit words.                              */
    /*                                                                  */
    /********************************************************************/

STATIC int NewPageSizes[] = { 2,0 };

    /********************************************************************/
    /*                                                                  */
    /*   Static data structures.                                        */
    /*                                                                  */
    /*   The static data structures are initialized and prepared for    */
    /*   use here.                                                      */
    /*                                                                  */
    /********************************************************************/

STATIC PREFETCH Prefetch;

    /********************************************************************/
    /*                                                                  */
    /*   Class constructor.                                             */
    /*                                                                  */
    /*   The overall structure and layout of the heap is controlled     */
    /*   by the various constants and calls made in this function.      */
    /*   There is a significant amount of flexibility available to      */
    /*   a heap which can lead to them having dramatically different    */
    /*   properties.                                                    */
    /*                                                                  */
    /********************************************************************/

ZONE_HEAP::ZONE_HEAP
		( 
		int							  MaxFreeSpace,
		bool						  Recycle,
		bool						  SingleImage,
		bool						  ThreadSafe 
		) :
		//
		//   Call the constructors for the contained classes.
		//
		ROCKALL
			(
			Caches1,
			Caches2,
			FindCacheSize,
			FindCacheThreshold,
			FindSize,
			MaxFreeSpace,
			NewPageSizes,
			Recycle,
			SingleImage,
			Stride1,
			Stride2,
			ThreadSafe
			)
	{
	AUTO ZONE NewZone = { NULL,NULL };

	//
	//   Setup the heap structures.
	//
	MaxSize = ZonePageSize;
	ThreadLocks = ThreadSafe;
	Zone = NewZone;
	}

    /********************************************************************/
    /*                                                                  */
    /*   Delete all allocations.                                        */
    /*                                                                  */
    /*   Delete all the heap allocations and return all the space       */
    /*   back to the operating system.                                  */
    /*                                                                  */
    /********************************************************************/

void ZONE_HEAP::DeleteAll( bool Recycle )
    {
	AUTO ZONE Update = { NULL,NULL };

	//
	//   Delete all outstanding allocations.
	//
	ROCKALL::DeleteAll( Recycle );

	//
	//   Delete the stale zone pointers.
	//
	WriteZone( & Update );
	}

    /********************************************************************/
    /*                                                                  */
    /*   Multiple memory allocations.                                   */
    /*                                                                  */
    /*   We allocate by advancing a pinter down an array.  This         */
    /*   is very fast but means that it can not be deleted except       */
    /*   by destroying the entire heap.                                 */
    /*                                                                  */
    /********************************************************************/

bool ZONE_HEAP::MultipleNew
		( 
		int							  *Actual,
		void						  *Array[],
		int							  Requested,
		int							  Size,
		int							  *Space,
		bool						  Zero
		)
    {
	//
	//   We simply call 'New' to create each element
	//   for a zone heap.
	//
	for ( (*Actual)=0;(*Actual) < Requested;(*Actual) ++ )
		{
		REGISTER VOID **Current = & Array[ (*Actual) ];

		//
		//   Create an allocation.
		//
		(*Current) = (ZONE_HEAP::New( Size,Space,Zero ));

		//
		//   Exit if there is no more space.
		//
		if ( (*Current) == NULL )
			{ return false; }
		}

	return true;
	}

    /********************************************************************/
    /*                                                                  */
    /*   Memory allocation.                                             */
    /*                                                                  */
    /*   We allocate by advancing a pinter down an array.  This         */
    /*   is very fast but means that it can not be deleted except       */
    /*   by destroying the entire heap.                                 */
    /*                                                                  */
    /********************************************************************/

void *ZONE_HEAP::New( int Size,int *Space,bool Zero )
    {
	//
	//   We would really hope that nobody would ask
	//   for a negative amount of memory but just to
	//   be sure we verify that this is not the case.
	//
	if ( Size >= 0 )
		{
		AUTO SBIT32 NewSize = ((Size + AlignmentMask) & ~AlignmentMask);
		AUTO ZONE Original;
		AUTO ZONE Update;

		//
		//   We would hope to create the allocation on the
		//   first try but there is a possibility that it
		//   may take serveral tries.
		do
			{
			//
			//   Extract a copy of the current zone pointers
			//   into local variables.
			//
			Original = Zone;
			Update = Original;

			//
			//   We need to ensure that there is enough space 
			//   in the zone for the current allocation.
			//
			if 
					( 
					(Update.Start == NULL)
						||
					((Update.Start += NewSize) > Update.End)
					)
				{
				//
				//   We do not have enough space.  If the size
				//   seems reasonable then get a new block from
				//   Rockall.  If not just pass the request along 
				//   to Rockall.
				//
				if ( NewSize <= (MaxSize / 2) )
					{
					STATIC SPINLOCK Spinlock;

					//
					//   We need to create a new zone page
					//   so claim a lock.
					//
					Spinlock.ClaimLock();

					//
					//   We may find that the zone has
					//   already been updated.  If so
					//   just exit.
					//
					if ( Update.End == Zone.End )
						{
						//
						//   Try to allocate a new zone
						//   block.
						//
						Update.Start = ((CHAR*) ROCKALL::New( MaxSize ));

						//
						//   Verify we were able to create
						//   a new zone page.
						//
						if ( Update.Start != NULL )
							{ Update.End = (Update.Start + MaxSize); }
						else
							{ Update.End = NULL; }

						//
						//   Update the zone.
						//
						WriteZone( & Update );
						}

					//
					//   Release the lock.
					//
					Spinlock.ReleaseLock();

					//
					//   If we were unable to get more
					//   space then exit.
					//
					if ( Update.Start == NULL )
						{ return NULL; }
					}
				else
					{ return (ROCKALL::New( Size,Space,Zero )); }
				}
			}
		while ( ! UpdateZone( & Original,& Update ) );

		//
		//   Prefetch the first cache line of  
		//   the allocation if we are running
		//   a Pentium III or better.
		//
		Prefetch.L1( ((CHAR*) Original.Start),1 );

		//
		//   If the caller wants to know the real 
		//   size them we supply it.
		//
		if ( Space != NULL )
			{ (*Space) = NewSize; }

		//
		//   If we need to zero the allocation
		//   we do it here.
		//
		if ( Zero )
			{ ZeroMemory( Original.Start,NewSize ); }

		//
		//   Exit and return the address.
		//
		return (Original.Start);
		}
	else
		{ return NULL; }
	}

    /********************************************************************/
    /*                                                                  */
    /*   Update the zone.                                               */
    /*                                                                  */
    /*   Ww update the zone when we do an allocation.  We do this       */
    /*   atomically if there are multiple threads.                      */
    /*                                                                  */
    /********************************************************************/

bool ZONE_HEAP::UpdateZone( ZONE *Original,ZONE *Update )
    {
	//
	//   Do we need to allow for multiple threads.  If 
	//   so we need to do the update atomically.  If 
	//   not then a simple assignment is fine.
	//
	if ( ThreadLocks )
		{
		REGISTER SBIT64 FinalValue =
			(
			ASSEMBLY::AtomicCompareExchange64
				(
				((SBIT64*) & Zone),
				(*((SBIT64*) Update)),
				(*((SBIT64*) Original))
				) 
			);

		return (FinalValue == (*((SBIT64*) Original)));
		}
	else
		{
		Zone = (*Update);

		return True;
		}
	}

    /********************************************************************/
    /*                                                                  */
    /*   Class destructor.                                              */
    /*                                                                  */
    /*   Destory the heap.                                              */
    /*                                                                  */
    /********************************************************************/

ZONE_HEAP::~ZONE_HEAP( VOID )
	{ /* void */ }