Algorithm Challenge

[tantrikwizard]

I'm doing a performance sweep and working on a new heap allocator. The design goal with this implementation is to be non-blocking and multi-threaded.

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__

This heap manager comes into play after paging is enabled but maybe adapted for a non-paged heap. The problem arises when multiple threads hit it, single threaded it works fine. There's a couple bugs (or a single bug that manifests itself in a couple ways). In one case a linked list item will refer to itself so gets stuck in a perpetual loop. In another case there seems to be an alignment issue where the magic values dont match up properly. Such a trivial block of code shouldn't take more than a couple hours to nail down but this one has got me perplexed. (When a process is created the _FreePartitions member is setup with {0xDeadBeef, NULL, 0xffffffff-sizeof(TPartitionInfo), 0xDeadBeef}) It then divides up memory as requested and merges adjacent partitions during a free. Any help or suggestions are appreciated.

[xvedejas]

Suggestion: don't use goto's. If you figure out a different way to do the same thing your code may become clearer, and likely easier to fix/change/understand/reuse/etc. Using goto's probably won't give you a performance increase your compiler can't already give you in most situations. Also, you may be eaten by raptors.

There's my suggestion. Hope it was constructive.

[tantrikwizard]

There's my suggestion. Hope it was constructive.

I don't like gotos either but in some cases its better than creating flags or extra variables just to avoid the goto. Just depends on how and where its used. Some of this could be rewritten to avoid gotos and probably will be once the bug is figured out. Thanks for the help.

[JamesM]

There's my suggestion. Hope it was constructive.

I don't like gotos either but in some cases its better than creating flags or extra variables just to avoid the goto. Just depends on how and where its used. Some of this could be rewritten to avoid gotos and probably will be once the bug is figured out. Thanks for the help.

There is never a valid reason for using gotos.

Watch out!...

[NickJohnson]

There is never a valid reason for using gotos.

Of course there are good reasons to use gotos, even if they are few and far between. Pretty much the best example is error handling, which is usually quite repetitive but is not easily wrapped in another function due to scoping. The C++/Java/C# people replaced this use with the try/throw/catch statement so they wouldn't be attacked by velociraptors while using gotos correctly.

Seriously, how is

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;
    }
}

different than

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;
}

?

Obviously these examples are too short to show the benefits of goto error handling, but in a large function, it can be *very* useful.

[fronty]

Tell me your compiler if it managed to compile your second example.

[JamesM]

There is never a valid reason for using gotos.

Of course there are good reasons to use gotos, even if they are few and far between. Pretty much the best example is error handling, which is usually quite repetitive but is not easily wrapped in another function due to scoping. The C++/Java/C# people replaced this use with the try/throw/catch statement so they wouldn't be attacked by velociraptors while using gotos correctly.

Seriously, how is

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;
    }
}

different than

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;
}

?

Obviously these examples are too short to show the benefits of goto error handling, but in a large function, it can be *very* useful.

Gotos are bad because they can jump through lexical scoping blocks with abandon. While the effects of this are mitigated in C by not having the ability to use RAII design patterns, they are not in C++ where destructors can be bypassed, causing horrible state leaks.

While they are mitigated in C, the practice of jumping out of the standard control flow not only causes compilers headaches and kills optimisations but is more likely to cause memory leaks (forgotten free()s, etc).

[raghuk]

The C++/Java/C# people replaced this use with the try/throw/catch statement so they wouldn't be attacked by velociraptors while using gotos correctly.

try-catch is not same as goto. In case of Java, you can have a n-level deep call stack and throw an exception from n-th level and have the first method catch it *after* finally blocks all the way up in the call stack are invoked. And these finally blocks themselves may cause other exceptions.

I can't think of a sane way of achieving that with gotos.

[tantrikwizard]

<snip>...but is more likely to cause memory leaks (forgotten free()s, etc).

Right, the main reason to avoid gotos in c++ is ensure temporaries and objects get deleted properly. It's not a big deal (other than possibly borking the optimizer) if there are no temps or objects instantiated on the stack. On the other hand, often the extra code required to avoid the goto can hurt performance and increase memory requirements. Complex flow control to avoid gotos often requires additional variables which means additional assignments and comparisons. I'm not fond of gotos, however, depending on the circumstances they're preferable to creating additional variables, assignments, comparisons and additional flow control. This allocator is one of those situations IMO. It has to be fast and must correct for concurrency issues.

Lets not get into the discussion of gotos (or at least created a separate thread for it), the pros and cons have been discussed a million times. Every developer is aware of them and has differing POV of when to use them or not.

[JamesM]

The additional flow control only exists at the source level; the compiler can generally optimise a lot away. Flow control constructs used as intended are easier for the compiler to optimise away than control constructs with an extra path added.

I still maintain that there is never, ever a valid reason for using "goto". And yes, I have seen the linux source. It's peppered with them, and is almost unreadable in places.

[AndrewAPrice]

I still maintain that there is never, ever a valid reason for using "goto".

Even if one is programming in BASIC?

[qw]

I still maintain that there is never, ever a valid reason for using "goto".

Even if one is programming in BASIC?

So the conclusion is that there is never, ever a valid reason for programming in BASIC

[AndrewAPrice]

I still maintain that there is never, ever a valid reason for using "goto".

Even if one is programming in BASIC?

So the conclusion is that there is never, ever a valid reason for programming in BASIC

If Combuster read that, he might tell you to run off and play with Calvin.

[gravaera]

Listen: any properly designed system NEVER has to use gotos. Ever. Any competent programmer can think in such purely logical terms that such erratic logic as jumping from one point to another doesn't even come to mind while programming. It has never even been an issue for me. Everything is a flow of logic. The reason why we have procedures and functions, i.e. blocks of code that can be repeated and factored out into one block of related code is so that we can jump to that bit of code by using the proper, standard calling convention.

The example you gave above could easily have been done by factoring out the error portion into a function. And it would have looked nicer too. Not only that, but using comparing operands and then a jump statement (via a goto) kind of messes up the compiler's mojo.

You know, there are so many people whom I believe, if I were to give a compiler life for one day, would get bludgeoned or shot. Design it properly. Take the extra time. It's worth it.

[NickJohnson]

Yes, but what about this snippet from my kernel (and the only instance of gotos therein, btw):

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;
}

The goto'd piece of code removes three potentially copy pasted pieces, takes less space/time/code than a small extra function, is quite obvious in terms of its purpose, and can't mess up state because it immediately panics anyway. This is really the only instance I can think of where gotos make more sense. The code is for an optimized bitmap that I use for frame allocation, if you want to know.