Jeffrey Cohen
and 1 contributors

NAME - Extent Space Management


 use Genezzo::SpaceMan::SMExtent;


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...


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.



return the current active block (insert high water mark) for an object.

Advanced: allow multiple active blocks for concurrent usage.


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


count of all blocks associated with the object. Includes allocated, *unused* blocks, plus empty blocks (i.e. blocks with no rows).


check if block is associated with an object


return all of an object's blocks to the freelist


write the contents of block zero to disk. Need to handle case of extent lists spread over multiple blocks.



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


Jeffrey I. Cohen,



Copyright (c) 2006, 2007 Jeffrey I Cohen. All rights reserved.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

Address bug reports and comments to:

For more information, please visit the Genezzo homepage at