The 'fix' for sharedmem

	Ok ... so I've been thinking more about bookkeeping in shared memory 
and that pathological case I mentioned just seems more and more 
pathological to me. Here's why:

Fact : Whenever someone free()s memory that either

1) Has already been de-allocated
2) Or was never allocated in the first place

Bad things CAN happen. This will be true in any memory management 
system that allows for explicit free. The reason is ... sometimes the 
free might work! This would be the case when some other part of the 
program allocated some memory and got back just the address now 
attempting to be freed. This sort of bug in client code ALMOST ALWAYS 
causes problems somewhere.

The question is "Can we guarantee the integrity of the memory manager 
even when bad client code is written against it" ? The answer to this 
is yes ... but we might not want to.

First off here's why its yes. We can always keep a list somewhere 
(outside of the area of shared memory where objects are allocated) of 
every piece of memory currently allocated and every time we get a 
'free()' call we check the list to make sure the address being free()d 
is in there.

It turns out the above algorithm would be fairly complex and expensive 
to implement. Incurring significant (although constant) extra costs on 
every malloc() and free().

Shared memory already maintains efficient allocated and free lists. The 
free list is implemented as a splay tree organized on free node sizes. 
It is located on the high end of the shared segment. This is outside of 
the space where memory allocated with malloc() goes.

The allocated list on the other hand is interspersed with memory 
allocated with malloc(). In fact the nodes for the alist are explicitly 
allocated immediately prior to the object itself. This was designed 
precisely for performance so that the bookkeeping for allocated 
addresses could be found in constant time when an address was freed. 
You can get to the anode for an object by simple pointer arithmetic on 
the object's address. This has always meant that a evil extension 
author could corrupt the bookkeeping by doing the same pointer 
arithmetic on addresses he got back from malloc().

Anyhow, an ANode is nothing more than a node in a doubly linked list.

typedef struct anode {
    struct anode* prev;
    struct anode* next;
    size_t size;
    void* pool;
    void(*freefn)(void *);
} ANode;

When memory gets free()'d we want to remove the ANode associated with 
the memory being freed. Right now there is an implicit assumption in 
the code that the memory being free()'d was allocated. So shared_free 
goes right into the process of re-linking the previous and next nodes 
in the list:

    startAddress = anode = address - sizeof(ANode);
    endAddress = address + anode->size;

    /* Delete the anode */

    if(anode->prev != NULL){
       anode->prev->next = anode->next;
       lowerAddress = (void*)anode->prev + anode->prev->size + 
sizeof(ANode);
    } else {
       *ALIST_HEAD = anode->next;
       lowerAddress = BASE_ADDRESS;
    }

    if(anode->next != NULL) {
       anode->next->prev = anode->prev;
       higherAddress = anode->next;
    } else {
       *ALIST_TAIL = anode->prev;
       higherAddress = BASE_ADDRESS+SHARED_SEGMENT;
    }

...

But what if the address was never allocated ? Or one that had already 
been freed ? This is when bad things happen currently. The question is 
how do we tell if that's the case ?

We could tell 99.9999% of the time by checking the following :

1) Is anode->prev not null and inside of shared memory - if no than 
this anode is invalid
1.1) if anode->prev is null than this should be the first allocated 
node in shared memory, thus ALIST_HEAD should point to it. If it 
doesn't than this node has already been freed (or was never allocated 
to begin with)
1.2) if anode->prev is not null than anode->prev->next should == anode. 
If this is not the case than this node cannot be part of the AList 
(meaning it had already been freed or was never allocated to begin with)

Equivalent checks can be done on the subsequent node as well. Here is 
the C code needed to do all the checks :

int isAddressAllocated(void* address){
	int validAddress = 1;
	ANode* anode = address - sizeof(ANode);
	
	if(shared_check(anode)){
		if(anode->prev != NULL) {
			if(!shared_check(anode->prev)) validAddress = 0;
			else if(anode->prev->next != anode) validAddress = 0;
		} else if (*ALIST_HEAD != anode) validAddress = 0;
	
		if(anode->next != NULL) {
			if(!shared_check(anode->next)) validAddress = 0;
			else if(anode->next->prev != anode) validAddress = 0;
		} else if (*ALIST_TAIL != anode) validAddress = 0;	
	} else validAddress = 0;

	return validAddress;	
}
			

So when do these checks not work ?

These checks will fail when someone, somehow re-creates a mini ANode 
list by hand with three nodes in it and tries to free the middle one. 
An evil extension programmer could do this for instance ... but then 
again an evil extension coder could simply wipe out the entire shared 
memory segment if he wanted to.

So my logic in going with the 99.99% fix is as follows. Extension 
programmers could really never exploit this by accident. They would 
have to want to cause memory manager corruption. And even if by some 
wierd random chance a 3 node AList magically appeared out of thin air 
and they accidentally free'd the middle node, its STILL THEIR FAULT 
because they are attempting to free something they never allocated (or 
already freed). So with these fixes it now takes an AMAZING COINCIDENCE 
+ AN EXTENSION CODE BUG to corrupt the memory manager (as opposed to 
before when it just took an extension code bug)

The above tests cause no visible performance degradation and were easy 
to implement so I'm going with those for now. If anyone wants to try 
the 100% fix and can show it causes no performance degradation ... I 
would be the first to swap out my fix for it :)

Anyone who modifies sharedmem.c should always run the objinst 
performance test (at least) afterwards. I've attached the test times 
both pre and post this fix.

-Dave

Here is the timing information for objinst, a big object allocation 
test, when no protection for double free's are implemented in 
sharedmem.c

% ./compile.sh objinst
objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.590u 0.110s 0:01.06 66.0% 0+0k 0+3io 0pf+0w
perl   : 7.180u 0.020s 0:07.96 90.4% 0+0k 5+0io 0pf+0w
java   : 0.390u 0.090s 0:00.67 71.6% 0+0k 2+0io 0pf+0w
python : 3.170u 0.080s 0:04.67 69.5% 0+0k 43+2io 0pf+0w
ruby   : 3.900u 0.060s 0:04.57 86.6% 0+0k 0+0io 0pf+0w
php    : 4.750u 0.030s 0:05.55 86.1% 0+0k 1+0io 0pf+0w
[ David-Hakims-Computer: /Users/dhakim/Workarea/perftests ]             
           % ./compile.sh objinst
objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.630u 0.080s 0:00.85 83.5% 0+0k 0+1io 0pf+0w
perl   : 7.120u 0.040s 0:07.82 91.5% 0+0k 0+0io 0pf+0w
java   : 0.370u 0.100s 0:00.61 77.0% 0+0k 0+0io 0pf+0w
python : 3.170u 0.040s 0:03.47 92.5% 0+0k 0+0io 0pf+0w
ruby   : 3.790u 0.050s 0:06.26 61.3% 0+0k 0+0io 0pf+0w
php    : 4.670u 0.030s 0:05.25 89.5% 0+0k 0+1io 0pf+0w
[ David-Hakims-Computer: /Users/dhakim/Workarea/perftests ]             
           % ./compile.sh objinst
objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.630u 0.090s 0:00.91 79.1% 0+0k 0+1io 0pf+0w
perl   : 7.210u 0.040s 0:07.78 93.1% 0+0k 0+0io 0pf+0w
java   : 0.320u 0.120s 0:00.67 65.6% 0+0k 0+0io 0pf+0w
python : 3.190u 0.020s 0:03.68 87.2% 0+0k 0+0io 0pf+0w
ruby   : 3.970u 0.050s 0:04.49 89.5% 0+0k 0+0io 0pf+0w
php    : 4.790u 0.020s 0:05.59 86.0% 0+0k 0+0io 0pf+0w

Post 99% fix:

objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.660u 0.110s 0:00.86 89.5% 0+0k 0+1io 0pf+0w
perl   : 7.200u 0.030s 0:07.93 91.1% 0+0k 0+0io 0pf+0w
java   : 0.380u 0.100s 0:00.62 77.4% 0+0k 1+0io 0pf+0w
python : 3.190u 0.050s 0:03.52 92.0% 0+0k 0+2io 0pf+0w
ruby   : 3.960u 0.030s 0:04.65 85.8% 0+0k 0+0io 0pf+0w
php    : 4.770u 0.010s 0:05.44 87.8% 0+0k 1+0io 0pf+0w
[ David-Hakims-Computer: /Users/dhakim/Workarea/perftests ]             
           % ./compile.sh objinst
objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.680u 0.080s 0:00.90 84.4% 0+0k 0+1io 0pf+0w
perl   : 7.220u 0.000s 0:07.95 90.8% 0+0k 0+0io 0pf+0w
java   : 0.330u 0.130s 0:00.70 65.7% 0+0k 0+0io 0pf+0w
python : 3.210u 0.040s 0:03.50 92.8% 0+0k 0+0io 0pf+0w
ruby   : 4.040u 0.030s 0:04.70 86.5% 0+0k 0+0io 0pf+0w
php    : 4.780u 0.030s 0:05.44 88.4% 0+0k 0+0io 0pf+0w
[ David-Hakims-Computer: /Users/dhakim/Workarea/perftests ]             
           % ./compile.sh objinst
objinst.c:95: warning: ANSI C forbids newline in string constant
objinst.moto:98:1: warning: multi-line string literals are deprecated
timing objinst
motoc  : 0.670u 0.090s 0:00.90 84.4% 0+0k 0+1io 0pf+0w
perl   : 7.120u 0.010s 0:08.12 87.8% 0+0k 0+0io 0pf+0w
java   : 0.320u 0.140s 0:00.69 66.6% 0+0k 0+0io 0pf+0w
python : 3.160u 0.040s 0:03.80 84.2% 0+0k 0+2io 0pf+0w
ruby   : 4.070u 0.050s 0:04.70 87.6% 0+0k 0+2io 0pf+0w
php    : 4.640u 0.020s 0:05.76 80.9% 0+0k 0+0io 0pf+0w