OSDev.org

Code: Select all

//partitionalloc.h
#pragma once
#if !defined(__PART_ALLOC_H_INCLUDED__)
#define __PART_ALLOC_H_INCLUDED__
class PartitionAllocator{
public:
#pragma pack(push, 1)
	typedef struct TPartitionInfo{
		ui32 Magic1;
		TPartitionInfo * Next;
		ui32 Size;
		ui32 Magic2;
	}TPartitionInfo;
#pragma pack(pop)

	static const ui32 PartitionMagic = 0xDeadBeef;

	typedef TPartitionInfo * PartitionInfo;

	PartitionInfo _FreePartitions;
	PartitionInfo _UsedPartitions;

	PartitionAllocator() : _FreePartitions(NULL), _UsedPartitions(NULL){}
	void * Alloc(size_t size){
		if (!size) return NULL;
		ui32 iActualSize = size + sizeof(TPartitionInfo);
Retry1:
		for (PartitionInfo pFreePartition =  _FreePartitions ; pFreePartition ; pFreePartition = pFreePartition->Next){
			assert(pFreePartition->Magic1 == PartitionMagic && pFreePartition->Magic2 == PartitionMagic);
			ui32 iFreePartitionSize = pFreePartition->Size;
			if (iFreePartitionSize > iActualSize){
				if ((ui32)iFreePartitionSize != InterlockedCompareExchange((ui32*)&pFreePartition->Size, (iFreePartitionSize-iActualSize), iFreePartitionSize)) continue;
				PartitionInfo pRet = (PartitionInfo)((ui32)pFreePartition + sizeof(TPartitionInfo) + (iFreePartitionSize-iActualSize));
				pRet->Magic1 = pRet->Magic2 = PartitionMagic;
				pRet->Size = size;
				for(;;){
					pRet->Next = _UsedPartitions;
					if ((ui32)pRet->Next != InterlockedCompareExchange((ui32*)&_UsedPartitions, (ui32)pRet, (ui32)pRet->Next)) goto Retry1;
					return ++pRet;
				}
			}
		}
		return NULL;
	}

	void Free(void*addr){
		if (!addr) return;
		ui32 iSize;
		PartitionInfo FreeMe = (PartitionInfo)addr;
		FreeMe--;
		assert(FreeMe->Magic1 == PartitionMagic && FreeMe->Magic2 == PartitionMagic);
		//first remove this item from the _UsedPartitions list
Retry1:
		if ((ui32)FreeMe != InterlockedCompareExchange((ui32*)&_UsedPartitions, (ui32)FreeMe->Next, (ui32)FreeMe)) { //if its not the 1st item then iterate 
			for (PartitionInfo pUsedPartition = _UsedPartitions ; pUsedPartition ; pUsedPartition = pUsedPartition->Next){
				assert(pUsedPartition->Magic1 == PartitionMagic && pUsedPartition->Magic2 == PartitionMagic);
				if (pUsedPartition->Next && pUsedPartition->Next==FreeMe){
					if ((ui32)FreeMe->Next != InterlockedCompareExchange((ui32*)&pUsedPartition->Next, (ui32)FreeMe->Next, (ui32)FreeMe)) goto Retry1;
				}
			}
		}
		//now push FreeMe on the _FreePartitions merging blocks if needed
		PartitionInfo PartitionAfterFreeMe = (PartitionInfo)((ui32)FreeMe + FreeMe->Size + sizeof(TPartitionInfo));
Retry2:
		for (PartitionInfo pFreePartition = _FreePartitions ; pFreePartition ; pFreePartition = pFreePartition->Next){
			assert(pFreePartition->Magic1 == PartitionMagic && pFreePartition->Magic2 == PartitionMagic);
			if (pFreePartition->Next == PartitionAfterFreeMe){
				assert(PartitionAfterFreeMe->Magic1 == PartitionMagic && PartitionAfterFreeMe->Magic2 == PartitionMagic);
				//merge FreeMe and PartitionAfterFreeMe by modifying FreeMe to include PartitionAfterFreeMe and destroy PartitionAfterFreeMe
				iSize = FreeMe->Size; //save this in case it must revert
				FreeMe->Size += PartitionAfterFreeMe->Size + sizeof(TPartitionInfo);
				FreeMe->Next = PartitionAfterFreeMe->Next;
				if ((ui32)PartitionAfterFreeMe != InterlockedCompareExchange((ui32*)&pFreePartition->Next, (ui32)FreeMe, (ui32)PartitionAfterFreeMe)){ 
					//pFreePartition was modified (PartitionAfterFreeMe was probably acquired) revert the size modification and retry
					FreeMe->Size = iSize; 
					goto Retry2;
				}
			}
			if ((ui32)pFreePartition + pFreePartition->Size + sizeof(TPartitionInfo) == (ui32)FreeMe){
				//merge blocks where FreeMe is at the end of pFreePartition
				//do so by expanding pFreePartition
				iSize = FreeMe->Size + pFreePartition->Size + sizeof(TPartitionInfo);
				ui32 iCurrentSize = pFreePartition->Size;
				if (iCurrentSize != (ui32)InterlockedCompareExchange((ui32*)&pFreePartition->Size, iSize, iCurrentSize)) goto Retry2;
				return;
			}else if (!pFreePartition->Next){  //end of list, add here
				if (NULL != InterlockedCompareExchange((ui32*)&pFreePartition->Next, (ui32)FreeMe, NULL)) goto Retry2;
				break;
			}
		}
	}
};
#endif//__PART_ALLOC_H_INCLUDED__

Code: Select all

int main() {
    char *buf;
    try {
        buf = new char[100];
        if (!buf) throw(1);
    }
    catch (int n) {
        cout << "error " << n << endl;
        return n;
    }
}

Code: Select all

int main() {
    char *buf = malloc(sizeof(char) * 100)
    int error;
    if (!buf) {
        error = 1;
        goto fail;
    }
    return 0;

    error:
    printf("error %d\n", error);
    return error;
}

Code: Select all

uint32_t pool_alloc(pool_t *pool) {
	uint32_t p, w, b;	// pool, word, bit

	// Find suitable pool
	for (p = 0; pool[p].total == 0; p++) 
		if (pool[p].setup != 0x4224) goto full;
	if (pool[p].setup != 0x4224) goto full;

	// Find suitable word within pool
	for (w = pool[p].first / 32; w < pool[p].upper / 32; w++)
		if (pool[p].word[w] != 0xFFFFFFFF) break;

	// Find open bit within word
	for (b = 0; pool[p].word[w] & (0x1 << b); b++);
	if (b == 32) goto full;

	pool[p].word[w] |= (0x1 << b);
	pool[p].total --;
	if (pool[p].first == ((w << 5) | b)) pool[p].first++;
	return ((p << 10) | ((w << 5) | b));

	full:
	printk("%x\n", pool_query(pool));
	panic("pool allocator full");
	return 0;
}