8.11 The GConv Tree

The GConv Tree is important internal GConv data structure which represents the virtual device and is needed for accessing it. Functions for manipulating with it are distributed in a few files, follows description of the most important.

Don't forget to use macros for locking leaves and nodes of the Tree correctly. If you modify leaf or node, you must use macro TC_MODIFY(). If you need to stay it in memory (it means in cache because can't be elsewhere) you must lock the item - use macros TC_LOCK() and TC_UNLOCK(). All these macros work with struct map_cacheitem which unions access to leaf and node structures, use function tc_get_node_or_leaf() or similiar functions.

Function tree_create()

Source in file: tree.c

int tree_create(PROGRESS_PARAM, ERR_PARAM)

This function creates the GConv Tree recursively. The Tree consists of a few small trees to prefer accessing blocks at the beginning, the other important reason is to be independent on amount of disk space - there isn't fixed deep of the Tree, but maximal deep only, therefore number of representable blocks is out of all limits.

There are flags about using of each block in the Tree. But it is hard to do it now when the Tree doesn't exist. This problem is worked around - all blocks are registered in special blocks and these blocks are flagged later by function trt_markall(). The recursive construction is processed by tree_create_subtree() which creates new subtree with specified deep.

Function setf_distribute()

Source in file: flags.c

struct map_cacheitem* setf_distribute(struct map_cacheitem *item, int index, ERR_PARAM)

Returns i-th son of node structure in item

The Tree allows lazy flagging blocks - flags can be marked in a node of the Tree and later can be distributed to leaves if these leaves are requested. Except lazy flagging is also allowed to search for blocks with set requested flag.

This function distributes flags marked in given node to all sons and returns requested son. The functionality differs for node and leaf in requested son.

Function flags_setextent()

Source in file: flags.c

void flags_setextent(struct extent *ex, tflags_t mask, tflags_t state, ERR_PARAM)

Set all flags in mask to their state for blocks in extent ex. The functionality is implemented lazy. Tries to change in nodes only everywhere where is it possible.

Function flags_firstblock()

Source in file: flags.c

block_t flags_firstblock(struct extent *ex, int flag, int state, ERR_PARAM)

Finds out the first block in blocks (from ex) with or without (depending on state) set flag. Returned INVALID_BLOCK if such blocks was not found.

Function flags_firstextent()

Source in file: flags.c

struct extent * flags_firstextent(struct extent *ex, int flag, int state, ERR_PARAM)

This is use of previous function and is very similiar. The task is to find the first maximal non empty subextent of given extent ex with flags set to state.

Function new2real()

Source in file: addr2no.c

int new2real(const struct extent *src, struct extent *dst, ERR_PARAM)

Converts src extent in addressing of the virtual device in destination state to current addressing. This is needed for accessing to exported partitions. It satisfies the longest possible head of given extent, althrough the input is continuous so the output must not. Output in dst

• Use n2r cache

  tries to use n2r cache intended for caching results of this function, this cache is implemented in n2rcache.c, used function n2r_convert(), if address is not found in cache then the result is written to cache (written to address returned by n2r_convert()) before return.

• Search for maximal continuous output

  loops to find maximal continuous head of input extent which is converted to continuous output, for each block is used map_status() which reads information from corresponding leaf in the Tree.

Function map_status()

Source in file: map_status.c

struct map_cacheitem * map_status(block_t pos, struct map_block_status ** bsp, ERR_PARAM)

This function gives information about pos-th block, this info is returned as pointer into cache to structures (see tcache.c for details). If pointer to cache is used after next operation with cache then the structure must be locked, macros TC_LOCK() and TC_UNLOCK().

• Find out in minicache

  minicache is used for very fast access to infos, especially for infos occuring in one leaf, this is "cache of cache". Recommended size of such cache is 4 items (or another very small number). To be sure that items in minicache stay in also in the main cache, items must be locked.

• Find out leaf

  Correspoding leaf is found in loop with using cached operations (see tcache.c). The Tree contains a few smaller trees, at first is found such tree and then loop goes through this tree to find out the leaf. To get next node (on path to leaf) is used function setf_distribute() which also distributes flags, it is needed because the Tree allows to flag extents of blocks and flagging is lazy implemented.

• Update minicache

  update minicache, make used item first or add found item into minicache and also remove one if cache is full.