NAME

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

SYNOPSIS

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

remove the seghdr/segnxt debugging tags

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 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: jcohen@genezzo.com

For more information, please visit the Genezzo homepage at http://www.genezzo.com

cpanm Genezzo

perl -MCPAN -e shell
install Genezzo