[gclist] The infamous mark and don't sweep algorithm.

[Charles Fiterman]

All storage items are contained in a series of arenas taken
from the operating system by something like sbrk. Each item
is prefaced by a word containing its length and a bit saying
whether it is free or not. The sense of this bit can reverse.

Allocation proceeds by looking at the item at the scan pointer.

While the scan pointer is not off the end
	If it is used
		bump the scan pointer
		continue
	else
		If it is big enough 
			take what you need from the front
			mark it used
			bump the scan pointer 
			return the area.
		else
			if the next item is free
				consolidate
				go to big enugh test.
			else
				Mark it used !?!
				continue the scan.

That suprising step, Mark an area used just because it was too small
for the current allocation has the following result. When the scan
pointer reaches the end of the heap everything is marked used.

By reversing the sense of the used bit everything becomes free. 

Now the mark step runs marking objects used by flipping that bit.

Reset the scan pointer to the beginning and continue.

What are the advantages? First minamum overhead, each object has only
its length as overhead. On small systems without paging this is a big
plus. There is no sweep phase. If most objects are free after the mark
phase the allocator will run fairly fast. 

Overhead may be reduced further by having each object point to a 
descriptor which has the ojects length as well as the location of
its pointers. The descriptor pointer has its low order bit used as
the free indicator.