// Copyright (c) 1994-2009 Nokia Corporation and/or its subsidiary(-ies).
// All rights reserved.
// This component and the accompanying materials are made available
// under the terms of the License "Eclipse Public License v1.0"
// which accompanies this distribution, and is available
// at the URL "http://www.eclipse.org/legal/epl-v10.html".
//
// Initial Contributors:
// Nokia Corporation - initial contribution.
//
// Contributors:
//
// Description:
// kernel\eka\include\heap_hybrid.h
// 
// Uses malloc (aka dlmalloc) written by Doug Lea version 2.8.4
//

#ifndef __HEAP_HYBRID_H__
#define __HEAP_HYBRID_H__

#include <e32cmn.h>

#ifdef __WINS__
#define USE_HYBRID_HEAP 0
#else
#define USE_HYBRID_HEAP 1
#endif

// This stuff is all temporary in order to prevent having to include dla.h from heap_hybrid.h, which causes
// problems due to its definition of size_t (and possibly other types).  This is unfortunate but we cannot
// pollute the namespace with these types or it will cause problems with Open C and other POSIX compatibility
// efforts in Symbian

#define NSMALLBINS        (32U)
#define NTREEBINS         (32U)

#ifndef MALLOC_ALIGNMENT
	#define MALLOC_ALIGNMENT ((TUint)8U)
#endif  /* MALLOC_ALIGNMENT */

#define CHUNK_OVERHEAD      (sizeof(TUint))

typedef unsigned int bindex_t;
typedef unsigned int binmap_t;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_segment msegment;
typedef struct malloc_state* mstate;
typedef struct malloc_tree_chunk* tbinptr;
typedef struct malloc_tree_chunk* tchunkptr;

struct malloc_segment {
  TUint8*        iBase;             /* base address */
  TUint       iSize;             /* allocated size */
};

struct malloc_state {
	binmap_t	 iSmallMap;
	binmap_t	 iTreeMap;
	TUint		 iDvSize;
	TUint		 iTopSize;
	mchunkptr	iDv;
	mchunkptr	iTop;
	TUint		 iTrimCheck;
	mchunkptr	iSmallBins[(NSMALLBINS+1)*2];
	tbinptr		iTreeBins[NTREEBINS];
	msegment	iSeg;
	};

class RHybridHeap : public RHeap
	{

public:

	struct HeapInfo
		{
	    unsigned iFootprint;
	    unsigned iMaxSize;
	    unsigned iAllocBytes;
	    unsigned iAllocN;
	    unsigned iFreeBytes;
	    unsigned iFreeN;
		};

	struct SHeapCellInfo { RHybridHeap* iHeap; TInt iTotalAlloc;	TInt iTotalAllocSize; TInt iTotalFree; TInt iLevelAlloc; SDebugCell* iStranded; };


	/**
    @internalComponent
    */
	enum TAllocatorType
			{ESlabAllocator, EDougLeaAllocator, EPageAllocator, EFullSlab=0x80, EPartialFullSlab=0x40, EEmptySlab=0x20, ESlabSpare=0x10, ESlabMask=0xf0};


	/**
    @internalComponent
    */
	struct SWalkInfo {
					  /**
	                  Walk function address shall be called
	                  */
		TWalkFunc iFunction;

					  /**
	                  The first parameter for callback function
	                  */
		TAny*        iParam;
					  /**
	                  Pointer to RHybridHeap object
	                  */
		RHybridHeap* iHeap;
		};

	/**
    @internalComponent
    */
	struct SConfig {
					  /**
	                  Required slab configuration ( bit 0=4, bit 1=8 ..
	                  bit 13 = 56)
	                  */
		TUint32 iSlabBits;
					  /**
	                  Delayed slab threshold in bytes (0 = no threshold)
	                  */
		TInt   iDelayedSlabThreshold;
					  /**
	                  2^n is smallest size allocated in paged allocator (14-31 = 16 Kb --> )
	                  */
		TInt   iPagePower;

		};

	/**
	@internalComponent

	This structure is used by test code for configuring the allocators and obtaining information
	from them in order to ensure they are behaving as required.  This is internal test specific
	code and is liable to be changed without warning at any time.  You should under no circumstances
	be using it!
	*/
	struct STestCommand
		{
		TInt	iCommand;			// The test related command to be executed

		union
			{
			SConfig		iConfig;	// Configuration used by test code only
			TAny*		iData;		// Extra supporting data for the test command
			};
		};

	/**
	@internalComponent

	Commands used by test code for configuring the allocators and obtaining information them them
	*/
	enum TTestCommand { EGetConfig, ESetConfig, EHeapMetaData, ETestData };

	virtual TAny* Alloc(TInt aSize);
	virtual void Free(TAny* aPtr);
	virtual TAny* ReAlloc(TAny* aPtr, TInt aSize, TInt aMode=0);
	virtual TInt AllocLen(const TAny* aCell) const;
#ifndef __KERNEL_MODE__	
	virtual TInt Compress();
	virtual void Reset();
	virtual TInt AllocSize(TInt& aTotalAllocSize) const;
	virtual TInt Available(TInt& aBiggestBlock) const;
#endif	
	virtual TInt DebugFunction(TInt aFunc, TAny* a1=NULL, TAny* a2=NULL);
protected:
	virtual TInt Extension_(TUint aExtensionId, TAny*& a0, TAny* a1);

public:
	TAny* operator new(TUint aSize, TAny* aBase) __NO_THROW;
	void operator delete(TAny*, TAny*);
	
private:
	TInt DoCountAllocFree(TInt& aFree);
	TInt DoCheckHeap(SCheckInfo* aInfo);
	void DoMarkStart();
	TUint32 DoMarkEnd(TInt aExpected);
	void DoSetAllocFail(TAllocFail aType, TInt aRate);
	TBool CheckForSimulatedAllocFail();
	void DoSetAllocFail(TAllocFail aType, TInt aRate, TUint aBurst);
	
	void Lock() const;
	void Unlock() const;
	TInt ChunkHandle() const;

	RHybridHeap(TInt aChunkHandle, TInt aOffset, TInt aMinLength, TInt aMaxLength, TInt aGrowBy, TInt aAlign, TBool aSingleThread, TBool aDlOnly, TBool aUseAdjust);	
	RHybridHeap(TInt aMaxLength, TInt aAlign=0, TBool aSingleThread=ETrue);
	RHybridHeap();
	
	void Init(TInt aBitmapSlab, TInt aPagePower);
	inline void InitBins(mstate m);
	inline void InitTop(mstate m, mchunkptr p, TUint psize);
    void* SysAlloc(mstate m, TUint nb);
	int SysTrim(mstate m, TUint pad);
	void* TmallocLarge(mstate m, TUint nb);
	void* TmallocSmall(mstate m, TUint nb);
	/*MACROS converted functions*/
	static inline void UnlinkFirstSmallChunk(mstate M,mchunkptr B,mchunkptr P,bindex_t& I);
	static inline void InsertSmallChunk(mstate M,mchunkptr P, TUint S);
	static inline void InsertChunk(mstate M,mchunkptr P,TUint S);
	static inline void UnlinkLargeChunk(mstate M,tchunkptr X);
	static inline void UnlinkSmallChunk(mstate M, mchunkptr P,TUint S);
	static inline void UnlinkChunk(mstate M, mchunkptr P, TUint S);
	static inline void ComputeTreeIndex(TUint S, bindex_t& I);
	static inline void InsertLargeChunk(mstate M,tchunkptr X,TUint S);
	static inline void ReplaceDv(mstate M, mchunkptr P, TUint S);
	static inline void ComputeBit2idx(binmap_t X,bindex_t& I);

	void DoComputeTreeIndex(TUint S, bindex_t& I);	
	void DoCheckAnyChunk(mstate m, mchunkptr p);
	void DoCheckTopChunk(mstate m, mchunkptr p);
	void DoCheckInuseChunk(mstate m, mchunkptr p);
	void DoCheckFreeChunk(mstate m, mchunkptr p);
	void DoCheckMallocedChunk(mstate m, void* mem, TUint s);
	void DoCheckTree(mstate m, tchunkptr t);
	void DoCheckTreebin(mstate m, bindex_t i);
	void DoCheckSmallbin(mstate m, bindex_t i);
	TInt BinFind(mstate m, mchunkptr x);
	TUint TraverseAndCheck(mstate m);
	void DoCheckMallocState(mstate m);	
	
	TInt GetInfo(struct HeapInfo* i, SWalkInfo* wi=NULL) const;	
	void InitDlMalloc(TUint capacity, int locked);
	void* DlMalloc(TUint);
	void  DlFree(void*);
	void* DlRealloc(void*, TUint, TInt);
	TUint DlInfo(struct HeapInfo* i, SWalkInfo* wi) const;
	void DoCheckCommittedSize(TInt aNPages, mstate aM);	
	
	TAny* ReAllocImpl(TAny* aPtr, TInt aSize, TInt aMode);
	void Construct(TBool aSingleThread, TBool aDLOnly, TBool aUseAdjust, TInt aAlign);
#ifndef __KERNEL_MODE__	
	TInt ConstructLock(TUint32 aMode);
#endif	
	static void Walk(SWalkInfo* aInfo, TAny* aBfr, TInt aLth, TCellType aBfrType, TAllocatorType aAlloctorType);
	static void WalkCheckCell(TAny* aPtr, TCellType aType, TAny* aCell, TInt aLen);
	void* Map(void* p, TInt sz);
	void Unmap(void* p,TInt sz);

private:
	TInt iMinLength;
	TInt iOffset;				// offset of RHeap object from chunk base
	TInt iGrowBy;
	TInt iMinCell;
	TInt iPageSize;

	// Temporarily commented out and exported from RHeap to prevent source breaks from req417-52840.
	// This will be moved with another REQ after submission and subsequent fixing of bad code
	//TInt iNestingLevel;
	TInt iAllocCount;
	// Temporarily commented out.  See comment above regarding req417-52840 source breaks
	//TAllocFail iFailType;
	TInt iFailRate;
	TBool iFailed;
	TInt iFailAllocCount;
	TInt iRand;
	// Temporarily commented out.  See comment above regarding req417-52840 source breaks
	//TAny* iTestData;

	TInt iChunkSize;				
	TInt iHighWaterMark;
	TBool iUseAdjust;
	TBool iDLOnly;

	malloc_state iGlobalMallocState;
	
#ifdef __KERNEL_MODE__
	
	friend class RHeapK;
	
#else
	
	friend class UserHeap;
	friend class HybridHeap;
	friend class TestHybridHeap;
	
private:

	static void TreeRemove(slab* s);
	static void TreeInsert(slab* s,slab** r);

	enum {EOkBits = (1<<(MAXSLABSIZE>>2))-1};
	
	void SlabInit();
	void SlabConfig(unsigned slabbitmap);
	void* SlabAllocate(slabset& allocator);
	void SlabFree(void* p);
	void* AllocNewSlab(slabset& allocator);
	void* AllocNewPage(slabset& allocator);
	void* InitNewSlab(slabset& allocator, slab* s);
	void FreeSlab(slab* s);
	void FreePage(page* p);
	void SlabInfo(struct HeapInfo* i, SWalkInfo* wi) const;
	static void SlabFullInfo(slab* s, struct HeapInfo* i, SWalkInfo* wi);
	static void SlabPartialInfo(slab* s, struct HeapInfo* i, SWalkInfo* wi);
	static void SlabEmptyInfo(slab* s, struct HeapInfo* i, SWalkInfo* wi);
	static void TreeWalk(slab* const* root, void (*f)(slab*, struct HeapInfo*, SWalkInfo*), struct HeapInfo* i, SWalkInfo* wi);

	static void WalkPartialFullSlab(SWalkInfo* aInfo, slab* aSlab, TCellType aBfrType, TInt aLth);
	static void WalkFullSlab(SWalkInfo* aInfo, slab* aSlab, TCellType aBfrType, TInt aLth);
	void DoCheckSlab(slab* aSlab, TAllocatorType aSlabType, TAny* aBfr=NULL);
	void DoCheckSlabTrees();	
	void DoCheckSlabTree(slab** aS, TBool aPartialPage);
	void BuildPartialSlabBitmap(TUint32* aBitmap, slab* aSlab, TAny* aBfr=NULL);
	
	static inline unsigned SlabHeaderFree(unsigned h) 
	{return (h&0x000000ff);}
	static inline unsigned SlabHeaderPagemap(unsigned h) 
	{return (h&0x00000f00)>>8;}
	static inline unsigned SlabHeaderSize(unsigned h) 
	{return (h&0x0003f000)>>12;}
	static inline unsigned SlabHeaderUsedm4(unsigned h) 
	{return (h&0x0ffc0000)>>18;}
	/***paged allocator code***/
	void PagedInit(TInt aPagePower);
	void* PagedAllocate(unsigned size);
	void PagedFree(void* p);	
	void* PagedReallocate(void* p, unsigned size, TInt mode);
	
	bool PagedEncode(unsigned pos, unsigned npage);
	unsigned PagedDecode(unsigned pos) const;
	inline unsigned PagedSize(void* p) const;
	inline bool PagedSetSize(void* p, unsigned size);
	inline void PagedZapSize(void* p, unsigned size);
	inline void* Bitmap2addr(unsigned pos) const;
	void PagedInfo(struct HeapInfo* i, SWalkInfo* wi) const;
	void ResetBitmap();
	TBool CheckBitmap(void* aBfr, TInt aSize, TUint32& aDummy, TInt& aNPages);	
	
private:
	paged_bitmap iPageMap;							// bitmap representing page allocator's pages
	TUint8*		iMemBase;							// bottom of paged/slab memory (chunk base)
	TUint8		iBitMapBuffer[MAXSMALLPAGEBITS>>3];	// buffer for initial page bitmap
	TInt		iSlabThreshold;						// allocations < than this are done by the slab allocator
	TInt		iPageThreshold;						// 2^n is smallest cell size allocated in paged allocator
	TInt		iSlabInitThreshold;					// slab allocator will be used after chunk reaches this size
	TUint32		iSlabConfigBits;					// set of bits that specify which slab sizes to use
	slab*		iPartialPage;						// partial-use page tree
	slab*		iFullSlab;							// full slabs list (so we can find them when walking)
	page*		iSparePage;							// cached, to avoid kernel exec calls for unmapping/remapping
	TUint8		iSizeMap[(MAXSLABSIZE>>2)+1];		// index of slabset indexes based on size class
	slabset		iSlabAlloc[MAXSLABSIZE>>2];			// array of pointers to slabsets

#endif // __KERNEL_MODE__	
};

#define HEAP_ASSERT(x) __ASSERT_DEBUG(x, HEAP_PANIC(ETHeapBadCellAddress))

template <class T> inline T Floor(const T addr, unsigned aln)
{return T((unsigned(addr))&~(aln-1));}
template <class T> inline T Ceiling(T addr, unsigned aln)
{return T((unsigned(addr)+(aln-1))&~(aln-1));}
template <class T> inline unsigned LowBits(T addr, unsigned aln)
{return unsigned(addr)&(aln-1);}
template <class T1, class T2> inline int PtrDiff(const T1* a1, const T2* a2)
{return reinterpret_cast<const unsigned char*>(a1) - reinterpret_cast<const unsigned char*>(a2);}
template <class T> inline T Offset(T addr, unsigned ofs)
{return T(unsigned(addr)+ofs);}

#endif //__HEAP_HYBRID_H__