fd.c File Reference

#include "lib/trace.h"
#include "fd/fd.h"
#include "fd/fd_internal.h"
#include "conf/walk.h"
#include "conf/obj.h"
#include "conf/obj_ops.h"
#include "conf/dir.h"
#include "conf/diter.h"
#include "conf/confc.h"
#include "pool/pool_machine.h"
#include "pool/pool.h"
#include "fid/fid.h"
#include "lib/errno.h"
#include "lib/memory.h"
#include "lib/arith.h"
#include "lib/hash.h"

Include dependency graph for fd.c:

Go to the source code of this file.

Data Structures
struct	pv_subtree_info

Macros
#define	M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_FD
#define	pv_for(pv, level, obj, rc)
#define	pv_endfor   } if (rc >= 0) m0_conf_diter_fini(&__it); })

Functions
static uint64_t	parity_group_size (const struct m0_pdclust_attr *la_attr)
static uint64_t	fault_tolerant_idx_get (uint64_t idx, uint64_t *children_nr, uint64_t depth)
static int	symm_tree_attr_get (const struct m0_conf_pver *pv, uint32_t *depth, uint64_t *children_nr)
static bool	fd_tile_invariant (const struct m0_fd_tile *tile)
static int	tolerance_check (const struct m0_conf_pver *pv, uint64_t *children_nr, uint32_t first_level, uint32_t *failure_level)
static void	uniform_distribute (uint64_t **units, uint64_t level, uint64_t parent_nr, uint64_t child_nr)
static uint64_t	units_calc (uint64_t **units, uint64_t level, uint64_t parent_nr, uint64_t child_nr, uint64_t tol)
static uint64_t	pool_width_calc (uint64_t *children_nr, uint64_t depth)
static void	permuted_tgt_get (struct m0_pdclust_instance *pi, uint64_t omega, uint64_t *rel_vidx, uint64_t *tgt_idx)
static void	inverse_permuted_idx_get (struct m0_pdclust_instance *pi, uint64_t omega, uint64_t perm_idx, uint64_t *rel_idx)
static struct m0_fd_perm_cache *	cache_get (struct m0_pdclust_instance *pi, struct m0_fd_tree_node *node)
static void	fd_permute (struct m0_fd_perm_cache *cache, struct m0_uint128 *seed, struct m0_fid *gfid, uint64_t omega)
static void	cache_info_update (struct m0_fd_cache_info *cache_info, uint64_t cnt)
static bool	is_cache_valid (const struct m0_fd_perm_cache *cache, uint64_t omega, const struct m0_fid *gfid)
static uint64_t	tree2pv_level_conv (uint64_t level, uint64_t tree_depth)
static bool	is_objv (const struct m0_conf_obj *obj, const struct m0_conf_obj_type *type)
static bool	is_objv_site (const struct m0_conf_obj *obj)
static bool	is_objv_rack (const struct m0_conf_obj *obj)
static bool	is_objv_encl (const struct m0_conf_obj *obj)
static bool	is_objv_ctrl (const struct m0_conf_obj *obj)
static bool	is_objv_disk (const struct m0_conf_obj *obj)
M0_INTERNAL int	m0_fd__tile_init (struct m0_fd_tile *tile, const struct m0_pdclust_attr *la_attr, uint64_t *children, uint64_t depth)
static int	objs_of_level_count (struct m0_conf_obj *obj, void *arg)
static int	min_children_get (struct m0_conf_obj *obj, void *arg)
M0_INTERNAL int	m0_fd_tolerance_check (struct m0_conf_pver *pv, uint32_t *failure_level)
M0_INTERNAL int	m0_fd_tile_build (const struct m0_conf_pver *pv, struct m0_pool_version *pool_ver, uint32_t *failure_level)
M0_INTERNAL void	m0_fd__tile_populate (struct m0_fd_tile *tile)
M0_INTERNAL void	m0_fd_src_to_tgt (const struct m0_fd_tile *tile, const struct m0_pdclust_src_addr *src, struct m0_pdclust_tgt_addr *tgt)
M0_INTERNAL void	m0_fd_tgt_to_src (const struct m0_fd_tile *tile, const struct m0_pdclust_tgt_addr *tgt, struct m0_pdclust_src_addr *src)
M0_INTERNAL void	m0_fd_tile_destroy (struct m0_fd_tile *tile)
M0_INTERNAL int	m0_fd_tree_build (const struct m0_conf_pver *pv, struct m0_fd_tree *tree)
M0_INTERNAL int	m0_fd__tree_level_populate (const struct m0_conf_pver *pv, struct m0_fd_tree *tree, uint32_t level)
M0_INTERNAL int	m0_fd__perm_cache_build (struct m0_fd_tree *tree)
M0_INTERNAL int	m0_fd_perm_cache_init (struct m0_fd_perm_cache *cache, uint64_t len)
M0_INTERNAL void	m0_fd_tree_destroy (struct m0_fd_tree *tree)
M0_INTERNAL void	m0_fd__perm_cache_destroy (struct m0_fd_tree *tree)
M0_INTERNAL void	m0_fd_perm_cache_fini (struct m0_fd_perm_cache *cache)
static struct m0_pool_version *	pool_ver_get (const struct m0_pdclust_instance *pd_instance)
M0_INTERNAL void	m0_fd_fwd_map (struct m0_pdclust_instance *pi, const struct m0_pdclust_src_addr *src, struct m0_pdclust_tgt_addr *tgt)
M0_INTERNAL void	m0_fd_bwd_map (struct m0_pdclust_instance *pi, const struct m0_pdclust_tgt_addr *tgt, struct m0_pdclust_src_addr *src)

Variables
static bool(*	is_obj_at_level [M0_CONF_PVER_HEIGHT])(const struct m0_conf_obj *obj)

Macro Definition Documentation

M0_TRACE_SUBSYSTEM

#define M0_TRACE_SUBSYSTEM   M0_TRACE_SUBSYS_FD

Definition at line 23 of file fd.c.

pv_endfor

#define pv_endfor   } if (rc >= 0) m0_conf_diter_fini(&__it); })

Definition at line 201 of file fd.c.

pv_for

#define pv_for	(		pv,
			level,
			obj,
			rc
	)

Value:

({                                                                         \
        struct m0_confc      *__confc;                                     \
        struct m0_conf_pver  *__pv    = (struct m0_conf_pver *)(pv);       \
        uint64_t              __level = (level);                           \
        struct m0_conf_diter  __it;                                        \
        struct m0_fid conf_path[M0_CONF_PVER_HEIGHT][M0_CONF_PVER_HEIGHT] = { \
                { M0_CONF_PVER_SITEVS_FID },                               \
                { M0_CONF_PVER_SITEVS_FID, M0_CONF_SITEV_RACKVS_FID },     \
                { M0_CONF_PVER_SITEVS_FID, M0_CONF_SITEV_RACKVS_FID,       \
                  M0_CONF_RACKV_ENCLVS_FID },                              \
                { M0_CONF_PVER_SITEVS_FID, M0_CONF_SITEV_RACKVS_FID,       \
                  M0_CONF_RACKV_ENCLVS_FID, M0_CONF_ENCLV_CTRLVS_FID },    \
                { M0_CONF_PVER_SITEVS_FID, M0_CONF_SITEV_RACKVS_FID,       \
                  M0_CONF_RACKV_ENCLVS_FID, M0_CONF_ENCLV_CTRLVS_FID,      \
                  M0_CONF_CTRLV_DRIVEVS_FID },                             \
         };                                                                \
        __confc = (struct m0_confc *)m0_confc_from_obj(&__pv->pv_obj);     \
        M0_ASSERT(__confc != NULL);                                        \
        rc = m0_conf__diter_init(&__it, __confc, &__pv->pv_obj,            \
                                 __level + 1, conf_path[__level]);         \
        while (rc >= 0  &&                                                 \
               (rc = m0_conf_diter_next_sync(&__it,                        \
                                             is_obj_at_level[__level])) != \
                M0_CONF_DIRNEXT) {;}                                       \
        for (obj = m0_conf_diter_result(&__it);                            \
             rc > 0 && (obj = m0_conf_diter_result(&__it));                \
             rc = m0_conf_diter_next_sync(&__it,                           \
                                          is_obj_at_level[__level])) {     \

Definition at line 171 of file fd.c.

Function Documentation

cache_get()

static struct m0_fd_perm_cache * cache_get ( struct m0_pdclust_instance *  pi, struct m0_fd_tree_node *  node  )

static

Returns the permutation cache associated with a node from the pdclust instance.

Definition at line 911 of file fd.c.

Here is the caller graph for this function:

cache_info_update()

static void cache_info_update ( struct m0_fd_cache_info *  cache_info, uint64_t  cnt  )

static

Checks if a given count is present in cache_info, and adds it in case it is absent.

Definition at line 728 of file fd.c.

Here is the caller graph for this function:

fault_tolerant_idx_get()

static uint64_t fault_tolerant_idx_get ( uint64_t  idx, uint64_t *  children_nr, uint64_t  depth  )

static

Maps an index from the base permutation to appropriate target index in a fault tolerant permutation.

Definition at line 522 of file fd.c.

Here is the caller graph for this function:

fd_permute()

static void fd_permute ( struct m0_fd_perm_cache *  cache, struct m0_uint128 *  seed, struct m0_fid *  gfid, uint64_t  omega  )

static

Permutes the permutation cache.

Definition at line 924 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fd_tile_invariant()

static bool fd_tile_invariant ( const struct m0_fd_tile *  tile )

inlinestatic

Definition at line 514 of file fd.c.

Here is the caller graph for this function:

inverse_permuted_idx_get()

static void inverse_permuted_idx_get ( struct m0_pdclust_instance *  pi, uint64_t  omega, uint64_t  perm_idx, uint64_t *  rel_idx  )

static

Returns relative indices from a symmetric tree.

Definition at line 1002 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_cache_valid()

static bool is_cache_valid ( const struct m0_fd_perm_cache *  cache, uint64_t  omega, const struct m0_fid *  gfid  )

static

Definition at line 953 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_objv()

static bool is_objv ( const struct m0_conf_obj *  obj, const struct m0_conf_obj_type *  type  )

static

Definition at line 127 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

is_objv_ctrl()

static bool is_objv_ctrl ( const struct m0_conf_obj *  obj )

static

Definition at line 152 of file fd.c.

Here is the call graph for this function:

is_objv_disk()

static bool is_objv_disk ( const struct m0_conf_obj *  obj )

static

Definition at line 157 of file fd.c.

Here is the call graph for this function:

is_objv_encl()

static bool is_objv_encl ( const struct m0_conf_obj *  obj )

static

Definition at line 147 of file fd.c.

Here is the call graph for this function:

is_objv_rack()

static bool is_objv_rack ( const struct m0_conf_obj *  obj )

static

Definition at line 142 of file fd.c.

Here is the call graph for this function:

is_objv_site()

static bool is_objv_site ( const struct m0_conf_obj *  obj )

static

Definition at line 137 of file fd.c.

Here is the call graph for this function:

m0_fd__perm_cache_build()

M0_INTERNAL int m0_fd__perm_cache_build

(

struct m0_fd_tree *

tree

)

Definition at line 683 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_fd__perm_cache_destroy()

M0_INTERNAL void m0_fd__perm_cache_destroy

(

struct m0_fd_tree *

tree

)

Definition at line 818 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_fd__tile_init()

M0_INTERNAL int m0_fd__tile_init	(	struct m0_fd_tile *	tile,
		const struct m0_pdclust_attr *	la_attr,
		uint64_t *	children_nr,
		uint64_t	depth
	)

Calculates the tile parameters using pdclust layout.

Definition at line 204 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_fd__tile_populate()

M0_INTERNAL void m0_fd__tile_populate

(

struct m0_fd_tile *

tile

)

Populates the tile with appropriate values.

Definition at line 487 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_fd__tree_level_populate()

M0_INTERNAL int m0_fd__tree_level_populate	(	const struct m0_conf_pver *	pv,
		struct m0_fd_tree *	tree,
		uint32_t	level
	)

Allocates and initializes the nodes at a given level, in failure domains tree, using the input pool version.

Definition at line 630 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

min_children_get()

static int min_children_get ( struct m0_conf_obj *  obj, void *  arg  )

static

Definition at line 234 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

objs_of_level_count()

static int objs_of_level_count ( struct m0_conf_obj *  obj, void *  arg  )

static

Definition at line 225 of file fd.c.

Here is the caller graph for this function:

parity_group_size()

static uint64_t parity_group_size ( const struct m0_pdclust_attr *  la_attr )

static

Definition at line 474 of file fd.c.

Here is the caller graph for this function:

permuted_tgt_get()

static void permuted_tgt_get ( struct m0_pdclust_instance *  pi, uint64_t  omega, uint64_t *  rel_vidx, uint64_t *  tgt_idx  )

static

Returns an index of permuted target.

Definition at line 876 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

pool_ver_get()

static struct m0_pool_version* pool_ver_get ( const struct m0_pdclust_instance *  pd_instance )

static

Definition at line 833 of file fd.c.

Here is the caller graph for this function:

pool_width_calc()

static uint64_t pool_width_calc ( uint64_t *  children_nr, uint64_t  depth  )

static

Calculates the pool-width associated with the symmetric tree.

Definition at line 479 of file fd.c.

Here is the caller graph for this function:

symm_tree_attr_get()

static int symm_tree_attr_get ( const struct m0_conf_pver *  pv, uint32_t *  depth, uint64_t *  children_nr  )

static

Fetches the attributes associated with the symmetric tree from a pool version.

Definition at line 298 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

tolerance_check()

static int tolerance_check ( const struct m0_conf_pver *  pv, uint64_t *  children_nr, uint32_t  first_level, uint32_t *  failure_level  )

static

Checks the feasibility of expected tolerance using the attributes of the symmetric tree formed from the pool version.

Definition at line 384 of file fd.c.

Here is the call graph for this function:

Here is the caller graph for this function:

tree2pv_level_conv()

static uint64_t tree2pv_level_conv ( uint64_t  level, uint64_t  tree_depth  )

static

Definition at line 292 of file fd.c.

Here is the caller graph for this function:

uniform_distribute()

static void uniform_distribute ( uint64_t **  units, uint64_t  level, uint64_t  parent_nr, uint64_t  child_nr  )

static

Uniformly distributes units from a parent node to all the children.

Definition at line 436 of file fd.c.

Here is the caller graph for this function:

units_calc()

static uint64_t units_calc ( uint64_t **  units, uint64_t  level, uint64_t  parent_nr, uint64_t  child_nr, uint64_t  tol  )

static

Calculates the sum of the units received by the first 'toll' number of nodes from a level 'level', when nodes are arranged in descending order of units they possess.

Definition at line 457 of file fd.c.

Here is the caller graph for this function:

Variable Documentation

is_obj_at_level

bool(* is_obj_at_level[M0_CONF_PVER_HEIGHT])(const struct m0_conf_obj *obj)

static

Initial value:

= {
        is_objv_site,
        is_objv_rack,
        is_objv_encl,
        is_objv_ctrl,
        is_objv_disk
}

Definition at line 163 of file fd.c.