fredag 3 februari 2012

w6d4: Workings and growing header list

Memory layout and algorithm
memory layout:
- header list grows from top of stack and downwards
- objects grow from bottom of stack and upwards

- lock type: unlocked = 0, locked = 1, weak = 2
- pointer to memory block
- size of memory block

free memory block:
- 4 bytes at N-4: header address, points back to this block
- 4 bytes at N-8: next free memory block.

- alias of header, opaque type. means the header block cannot be compacted!

header list:
- insert new at the first free location

- keep bitmap (64 bytes) to narrow down the search of first free header
- 64*8=512 bits, initially 8 headers per bit = 4096 entries.
- bitmap scaled to number of objects, when limit reached, double and scale down (b0=b0*b1, b2=b2*b3, ...).

Current issues
Header is mapped 1:1 with handle. There must be header for each block in the free list (for identity when merging with previous block).  Which means that between compacts, header list will always grow, since there are by definition never any unused handles.

This means that in the current setup, the header list will never be fully compacted.

Inga kommentarer:

Skicka en kommentar