falloc

package
v0.0.0-...-d7e0ad7 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 17, 2014 License: Apache-2.0, BSD-3-Clause, BSD-3-Clause Imports: 6 Imported by: 0

README

This is a goinstall-able mirror of modified code already published at:
https://git.nic.cz/redmine/projects/gofileutil/repository/show/falloc

Install: $go get github.com/cznic/fileutil/falloc
Godocs: http://gopkgdoc.appspot.com/pkg/github.com/cznic/fileutil/falloc

Documentation

Overview

WIP: Package falloc provides allocation/deallocation of space within a file/store (WIP, unstable API).

Overall structure:

File == n blocks.
Block == n atoms.
Atom == 16 bytes.

x6..x0 == least significant 7 bytes of a 64 bit integer, highest (7th) byte is 0 and is not stored in the file.

Block first byte

Aka block type tag.

------------------------------------------------------------------------------

0xFF: Free atom (free block of size 1).

+------++---------++---------++------+
|  0   ||  1...7  || 8...14  ||  15  |
+------++---------++---------++------+
| 0xFF || p6...p0 || n6...n0 || 0xFF |
+------++---------++---------++------+

Link to the previous free block (atom addressed) is p6...p0, next dtto in n6...n0. Doubly linked lists of "compatible" free blocks allows for free space reclaiming and merging. "Compatible" == of size at least some K. Heads of all such lists are organized per K or intervals of Ks elsewhere.

------------------------------------------------------------------------------

0xFE: Free block, size == s6...s0 atoms.

+------++---------++---------++---------++--
|  +0  ||  1...7  || 8...14  || 15...21 || 22...16*size-1
+------++---------++---------++---------++--
| 0xFE || p6...p0 || n6...n0 || s6...s0 || ...
+------++---------++---------++---------++--

Prev and next links as in the 0xFF first byte case. End of this block - see "Block last byte": 0xFE bellow. Data between == undefined.

------------------------------------------------------------------------------

0xFD: Relocated block.

+------++---------++-----------++------+
|  0   ||  1...7  ||  8...14   ||  15  |
+------++---------++-----------++------+
| 0xFD || r6...r0 || undefined || 0x00 | // == used block
+------++---------++-----------++------+

Relocation link is r6..r0 == atom address. Relocations MUST NOT chain and MUST point to a "content" block, i.e. one with the first byte in 0x00...0xFC.

Relocated block allows to permanently assign a handle/file pointer ("atom" address) to some content and resize the content anytime afterwards w/o having to update all the possible existing references to the original handle.

------------------------------------------------------------------------------

0xFC: Used long block.

+------++---------++--------------------++---------+---+
|  0   ||  1...2  ||      3...N+2       ||         |   |
+------++---------++--------------------++---------+---+
| 0xFC || n1...n0 || N bytes of content || padding | Z |
+------++---------++--------------------++---------+---+

This block type is used for content of length in N == 238...61680 bytes. N is encoded as a 2 byte unsigned integer n1..n0 in network byte order. Values bellow 238 are reserved, those content lengths are to be carried by the 0x00..0xFB block types.

  1. n in 0x00EE...0xF0F0 is used for content under the same rules as in the 0x01..0xED type.

  2. If the last byte of the content is not the last byte of an atom then the last byte of the block is 0x00.

  3. If the last byte of the content IS the last byte of an atom:

    3.1 If the last byte of content is in 0x00..0xFD then everything is OK.

    3.2 If the last byte of content is 0xFE or 0xFF then the escape via n > 0xF0F0 MUST be used AND the block's last byte is 0x00 or 0x01, meaning value 0xFE and 0xFF respectively.

  4. n in 0xF0F1...0xFFFF is like the escaped 0xEE..0xFB block. N == 13 + 16(n - 0xF0F1).

Discussion of the padding and Z fields - see the 0x01..0xED block type.

------------------------------------------------------------------------------

0xEE...0xFB: Used escaped short block.

+---++----------------------++---+
| 0 ||        1...N-1       ||   |
+---++----------------------++---+
| X || N-1 bytes of content || Z |
+---++----------------------++---+

N == 15 + 16(X - 0xEE). Z is the content last byte encoded as follows.

case Z == 0x00: The last byte of content is 0xFE

case Z == 0x01: The last byte of content is 0xFF

------------------------------------------------------------------------------

0x01...0xED: Used short block.

+---++--------------------++---------+---+
| 0 ||        1...N       ||         |   |
+---++--------------------++---------+---+
| N || N bytes of content || padding | Z |
+---++--------------------++---------+---+

This block type is used for content of length in 1...237 bytes. The value of the "padding" field, if of non zero length, is undefined.

If the last byte of content is the last byte of an atom (== its file byte offset & 0xF == 0xF) then such last byte MUST be in 0x00...0xFD.

If the last byte of content is the last byte of an atom AND the last byte of content is 0xFE or 0xFF then the short escape block type (0xEE...0xFB) MUST be used.

If the last byte of content is not the last byte of an atom, then the last byte of such block, i.e. the Z field, which is also a last byte of some atom, MUST be 0x00 (i.e. the used block marker). Other "tail" values are reserved.

------------------------------------------------------------------------------

0x00: Used empty block.

+------++-----------++------+
|  0   ||  1...14   ||  15  |
+------++-----------++------+
| 0x00 || undefined || 0x00 | // == used block, other "tail" values reserved.
+------++-----------++------+

All of the rules for 0x01..0xED applies. Depicted only for its different semantics (e.g. an allocated [existing] string but with length of zero).

==============================================================================

Block last byte

------------------------------------------------------------------------------

0xFF: Free atom. Layout - see "Block first byte": FF.

------------------------------------------------------------------------------

0xFE: Free block, size n atoms. Preceding 7 bytes == size (s6...s0) of the free block in atoms, network byte order

  --++---------++------+
    || -8...-2 ||  -1  |
  --++---------++------+
... || s6...s0 || 0xFE | <- block's last byte
  --++---------++------+

Layout at start of this block - see "Block first byte": FE.

------------------------------------------------------------------------------

0x00...0xFD: Used (non free) block.

==============================================================================

Free lists table

The free lists table content is stored in the standard layout of a used block.

A table item is a 7 byte size field followed by a 7 byte atom address field (both in network byte order), thus every item is 14 contiguous bytes. The item's address field is pointing to a free block. The size field determines the minimal size (in atoms) of free blocks on that list.

The free list table is n above items, thus the content has 14n bytes. Note that the largest block content is 61680 bytes and as there are 14 bytes per table item, so the table is limited to at most 4405 entries.

Items in the table do not have to be sorted according to their size field values.

No two items can have the same value of the size field.

When freeing blocks, the block MUST be linked into an item list with the highest possible size field, which is less or equal to the number of atoms in the new free block.

When freeing a block, the block MUST be first merged with any adjacent free blocks (thus possibly creating a bigger free block) using information derived from the adjacent blocks first and last bytes. Such merged free blocks MUST be removed from their original doubly linked lists. Afterwards the new bigger free block is put to the free list table in the appropriate item.

Items with address field == 0 are legal. Such item is a placeholder for a empty list of free blocks of the item's size.

Items with size field == 0 are legal. Such item is a placeholder, used e.g. to avoid further reallocations/redirecting of the free lists table.

The largest possible allocation request (for content length 61680 bytes) is 0xF10 (3856) atoms. All free blocks of this or bigger size are presumably put into a single table item with the size 3856. It may be useful to additionally have a free lists table item which links free blocks of some bigger size (say 1M+) and then use the OS sparse file support (if present) to save the physical space used by such free blocks.

Smaller (<3856 atoms) free blocks can be organized exactly (every distinct size has its table item) or the sizes can run using other schema like e.g. "1, 2, 4, 8, ..." (powers of 2) or "1, 2, 3, 5, 8, 13, ..." (the Fibonacci sequence) or they may be fine tuned to a specific usage pattern.

==============================================================================

Header

The first block of a file (atom address == file offset == 0) is the file header. The header block has the standard layout of a used short non escaped block.

Special conditions apply: The header block and its content MUST be like this:

+------+---------+---------+------+
|  0   |  1...7  | 8...14  |  15  |
+------+---------+---------+------+
| 0x0F | m6...m0 | f6...f0 | FLTT |
+------+---------+---------+------+

m6..m0 is a "magic" value 0xF1C1A1FE51B1E.

f6...f0 is the atom address of the free lists table (discussed elsewhere). If f6...f0 == 0x00 the there is no free lists table (yet).

FLTT describes the type of the Free List Table. Currently defined values:

------------------------------------------------------------------------------

FLTT == 0: Free List Table is fixed at atom address 2. It has a fixed size for 3856 entries for free list of size 1..3855 atoms and the last is for the list of free block >= 3856 atoms.

Index

Constants

View Source
const (
	INVALID_HANDLE = Handle(-1)
)

Variables

This section is empty.

Functions

This section is empty.

Types

type EBadRequest

type EBadRequest struct {
	Name string
	Size int
}

EBadRequest is an error produced for invalid operation, e.g. for data of more than maximum allowed.

func (*EBadRequest) Error

func (e *EBadRequest) Error() string

type EClose

type EClose struct {
	Name string
	Err  error
}

EClose is a file/store close error.

func (*EClose) Error

func (e *EClose) Error() string

type ECorrupted

type ECorrupted struct {
	Name string
	Ofs  int64
}

ECorrupted is a file/store format error.

func (*ECorrupted) Error

func (e *ECorrupted) Error() string

type ECreate

type ECreate struct {
	Name string
	Err  error
}

ECreate is a file/store create error.

func (*ECreate) Error

func (e *ECreate) Error() string

type EFreeList

type EFreeList struct {
	Name  string
	Size  int64
	Block int64
}

EFreeList is a file/store format error.

func (*EFreeList) Error

func (e *EFreeList) Error() string

type EHandle

type EHandle struct {
	Name   string
	Handle Handle
}

EHandle is an error type reported for invalid Handles.

func (EHandle) Error

func (e EHandle) Error() string

type EHeader

type EHeader struct {
	Name     string
	Header   []byte
	Expected []byte
}

EHeader is a file/store format error.

func (*EHeader) Error

func (e *EHeader) Error() string

type ENullHandle

type ENullHandle string

ENullHandle is a file/store access error via a null handle.

func (ENullHandle) Error

func (e ENullHandle) Error() string

type EOpen

type EOpen struct {
	Name string
	Err  error
}

EOpen is a file/store open error.

func (*EOpen) Error

func (e *EOpen) Error() string

type ERead

type ERead struct {
	Name string
	Ofs  int64
	Err  error
}

ERead is a file/store read error.

func (*ERead) Error

func (e *ERead) Error() string

type ESize

type ESize struct {
	Name string
	Size int64
}

ESize is a file/store size error.

func (*ESize) Error

func (e *ESize) Error() string

type EWrite

type EWrite struct {
	Name string
	Ofs  int64
	Err  error
}

EWrite is a file/store write error.

func (*EWrite) Error

func (e *EWrite) Error() string

type File

type File struct {
	// contains filtered or unexported fields
}

File is a file/store with space allocation/deallocation support.

func New

func New(store storage.Accessor) (f *File, err error)

New returns a new File backed by store or an error if any. Any existing data in store are discarded.

func Open

func Open(store storage.Accessor) (f *File, err error)

Open returns a new File backed by store or an error if any. Store already has to be in a valid format.

func (*File) Accessor

func (f *File) Accessor() storage.Accessor

Accessor returns the File's underlying Accessor.

func (*File) Alloc

func (f *File) Alloc(b []byte) (handle Handle, err error)

Alloc stores b in a newly allocated space and returns its handle and an error if any.

func (*File) Close

func (f *File) Close() (err error)

Close closes f and returns an error if any.

func (*File) Free

func (f *File) Free(handle Handle) (err error)

Free frees space associated with handle and returns an error if any. Passing an invalid handle to Free or reusing handle afterwards will probably corrupt the database or provide invalid data on Read. It's like corrupting memory via passing an invalid pointer to C.free() or reusing that pointer.

func (*File) Lock

func (f *File) Lock()

Lock locks f for writing. If the lock is already locked for reading or writing, Lock blocks until the lock is available. To ensure that the lock eventually becomes available, a blocked Lock call excludes new readers from acquiring the lock.

func (*File) LockedAlloc

func (f *File) LockedAlloc(b []byte) (handle Handle, err error)

LockedAlloc wraps Alloc in a Lock/Unlock pair.

func (*File) LockedFree

func (f *File) LockedFree(handle Handle) (err error)

LockedFree wraps Free in a Lock/Unlock pair.

func (*File) LockedRead

func (f *File) LockedRead(handle Handle) (b []byte, err error)

LockedRead wraps Read in a RLock/RUnlock pair.

func (*File) LockedRealloc

func (f *File) LockedRealloc(handle Handle, b []byte, keepHandle bool) (newhandle Handle, err error)

LockedRealloc wraps Realloc in a Lock/Unlock pair.

func (*File) RLock

func (f *File) RLock()

RLock locks f for reading. If the lock is already locked for writing or there is a writer already waiting to release the lock, RLock blocks until the writer has released the lock.

func (*File) RUnlock

func (f *File) RUnlock()

RUnlock undoes a single RLock call; it does not affect other simultaneous readers. It is a run-time error if f is not locked for reading on entry to RUnlock.

func (*File) Read

func (f *File) Read(handle Handle) (b []byte, err error)

Read reads and return the data associated with handle and an error if any. Passing an invalid handle to Read may return invalid data without error. It's like getting garbage via passing an invalid pointer to C.memcopy().

func (*File) Realloc

func (f *File) Realloc(handle Handle, b []byte, keepHandle bool) (newhandle Handle, err error)

Realloc reallocates space associted with handle to acomodate b, returns the newhandle newly associated with b and an error if any. If keepHandle == true then Realloc guarantees newhandle == handle even if the new data are larger then the previous content associated with handle. If !keepHandle && newhandle != handle then reusing handle will probably corrupt the database. The above effects are like corrupting memory/data via passing an invalid pointer to C.realloc().

func (*File) Root

func (f *File) Root() Handle

Root returns the handle of the DB root (top level directory, ...).

func (*File) Unlock

func (f *File) Unlock()

Unlock unlocks f for writing. It is a run-time error if f is not locked for writing on entry to Unlock.

As with Mutexes, a locked RWMutex is not associated with a particular goroutine. One goroutine may RLock (Lock) f and then arrange for another goroutine to RUnlock (Unlock) it.

type Handle

type Handle int64

Handle is a reference to a block in a file/store. Handle is an uint56 wrapped in an in64, i.e. the most significant byte must be always zero.

func (*Handle) Get

func (h *Handle) Get(b []byte)

Get gets the 7 least significant bytes of h from b. The MSB of h is zeroed.

func (Handle) Put

func (h Handle) Put(b []byte)

Put puts the 7 least significant bytes of h into b. The MSB of h should be zero.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL