Genezzo::SpaceMan::SMExtent.pm - Extent Space Management
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, firstname.lastname@example.org
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 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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: email@example.com
For more information, please visit the Genezzo homepage at http://www.genezzo.com