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
SEE ALSO
perl(1).
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 USAAddress bug reports and comments to: jcohen@genezzo.com
For more information, please visit the Genezzo homepage at http://www.genezzo.com