NAME

Genezzo::SpaceMan::SMExtent.pm - Extent Space Management

SYNOPSIS

 use Genezzo::SpaceMan::SMExtent;

DESCRIPTION

Maintain segment headers and extent headers for objects stored in a file with information on space usage. The set of space allocations for an object in a file is called a *segment*. Each segment is composed of *extents*, groups of contiguous blocks.

allocate a new extent:

if have first extent (segment header) create X1A with current blockno, size. else update X1A with new extent info.

in first block of extent: create XHA with empty space usage bitvec create XHP, marked as position zero

if allocate a new block: if 1st block of an extent, goto allocate new extent else could mark prior block as used in XHA...

if free a block: clear bitvec in XHA

if freed all blocks in XHA update X1A

if X1A is too small: need 2 rows. pump out with free space at end.

seghd_allextents: status_flag extent:size:pct_used, extent:size:pct_used, extent:size:pct_used... seghd_next: parent_seghead next_seghead:tot_size:pct_used

tot_size in human_num, eg 10K, 100G, 2P...

leapfrog:

seghd in extent 1, create a seghd in extent 2 when you allocate it. when seghd in extent 1 fills, overflow to seghd in extent 2. When allocate next new extent, update the 2nd seghead, and create a new seghd in the new extent.

x1a: extent:size:pct_used, extent:size:pct_used, ... x1b: parent [child]

parent = self for 1st extent fill in child when allocate 2nd extent... child info tracks additional space usage in segment subhead, and if use "human readable" numbers, can restrict to 4 char fixed size 0-999B, 1K-999K, 1M-999M marker for "subhead full" vs vacancy... x1a: full_flag extent:size:pct_used, extent:size:pct_used, ...

if XHA bitvec is too long: break out over multiple rows, over multiple blocks.

xhd1: parent_xhd bitvec xhd[N]: next_xhd

or maybe -- recursive split

bitvec of blocks or subextents. for extent of < 128 blocks, simple bitvec for each block.

for extent of 256 blocks top bitvec of 2 subextents each subextent has bitvec of 128 blocks

actually, could top out extent size at 1M, use 256 4K blocks per extent

xhd needs to track seghd/subhead info

xhp tracks extent position [0 to N-1] and %used in extent header (ie 0 is 0%, 3 is 30%, 6 is 60%, and 9 is 90+%).

Note that block zero is a very similar to a segment header, though it tracks the lists of extents associated with each object, and it doesn't track percent usage. However, if we have the case of a file which is solely for one object, we could merge a good portion of block zero and the segment header into a combined set of data structures.

FUNCTIONS

currblock: return the current active block (insert high water mark) for an object.
Advanced: allow multiple active blocks for concurrent usage.
nextfreeblock: return the next unused block for an object, which would be one beyond the current block in the current extent if possible, or else it allocates a new extent.
Advanced: allow multiple "next blocks" for concurrent users. Maintain multiple freelists. Use this call as an opportunity to probe extent headers to update the segment header.
firstblock, nextblock: iterate over the set of *used* blocks for an object. Ignores unused blocks in last extent
countblock: count of all blocks associated with the object. Includes allocated, *unused* blocks, plus empty blocks (i.e. blocks with no rows).
hasblock: check if block is associated with an object
freetable: return all of an object's blocks to the freelist
flush: write the contents of block zero to disk. Need to handle case of extent lists spread over multiple blocks.

EXPORT

TODO

need to coalesce adjacent free extents
maintain multiple free lists for performance
better indexing scheme - maybe a btree

AUTHOR

Jeffrey I. Cohen, jcohen@genezzo.com