Virtual array

Data Structures
struct	m0_varr_path_element
struct	m0_varr_cursor
struct	m0_varr

Macros
#define	m0_varr_iter(arr, type, idx, obj, start, end, inc)
#define	m0_varr_enditer   } } )
#define	m0_varr_for(arr, type, idx, obj)
#define	m0_varr_endfor   m0_varr_enditer; })

Enumerations
enum	m0_varr_tree_char { M0_VA_TNODE_NR = 64, M0_VA_TNODEPTR_SIZE = sizeof(void *), M0_VA_TNODE_NR_SHIFT = 6, M0_VA_DEPTH_MAX = 16 }

Functions
	M0_BASSERT (M0_VA_TNODE_NR==M0_BITS(M0_VA_TNODE_NR_SHIFT))
M0_INTERNAL int	m0_varr_init (struct m0_varr *arr, uint64_t nr, size_t size, size_t bufsize)
M0_INTERNAL void	m0_varr_fini (struct m0_varr *arr)
M0_INTERNAL void *	m0_varr_ele_get (struct m0_varr *arr, uint64_t index)
M0_INTERNAL uint64_t	m0_varr_size (const struct m0_varr *arr)
M0_INTERNAL int	m0_varr_cursor_init (struct m0_varr_cursor *cursor, const struct m0_varr *arr, uint32_t depth)
M0_INTERNAL void *	m0_varr_cursor_get (struct m0_varr_cursor *cursor)
M0_INTERNAL int	m0_varr_cursor_next (struct m0_varr_cursor *cursor)
M0_INTERNAL int	m0_varr_cursor_move (struct m0_varr_cursor *cursor, uint64_t inc)

Detailed Description

A virtual array represents a data structure which can be used at places where big contiguous memory allocations are not possible.

Virtual array can be used for big arrays or pointers which would potentially hold large memory areas. Virtual array library provides interface for read, write, and iterate over an array.

Using such structures can be especially helpful in kernel where contiguity of pages is not guaranteed, and any memory allocation growing beyond page size can essentially fail. Current implementation supports both user-space as well as kernel versions.

The structure of virtual array is kept something similar to a block map from an on-disk inode with multiple indirections.

Using pointer arithmetic on virtual array is strongly discouraged since it does not guarantee contiguity of buffers.

A virtual array uses a radix-tree like structure whose height is dependent on number of objects to be accommodated in the array.

Following example illustrates the usage of various interfaces that are provided by virtual array library.

Consider an array consisting of OBJ_NR number of objects, of the type unsigned long. Library leaves it to its user what shall be the size of a buffer holding objects. Following example uses M0_0VEC_ALIGN as buffer size.

struct m0_varr varr;

enum {
        OBJ_NR = 10203040,
};

rc = m0_varr_init(&varr, OBJ_NR, sizeof(unsigned long), M0_0VEC_ALIGN);

m0_varr_iter(&varr, unsigned long, id, obj, 0, m0_varr_size(&varr), 1) {
     *obj = id;
} m0_varr_enditer;

m0_varr_iter(&varr, unsigned long, id, obj, 0, m0_varr_size(&varr), 1) {
        ptr = m0_varr_ele_get(&varr, id);
        M0_ASSERT(*ptr == *obj);
} m0_varr_enditer;

m0_varr_fini(&varr);

Macro Definition Documentation

m0_varr_endfor

#define m0_varr_endfor   m0_varr_enditer; })

Definition at line 264 of file varr.h.

m0_varr_enditer

#define m0_varr_enditer   } } )

Definition at line 256 of file varr.h.

m0_varr_for

#define m0_varr_for	(		arr,
			type,
			idx,
			obj
	)

Value:

({                                                                          \
        struct m0_varr *__arr__ = (arr);                                    \
        m0_varr_iter(__arr__, type, idx, obj, 0, m0_varr_size(__arr__), 1)

Iterates over whole virtual array.

Definition at line 259 of file varr.h.

m0_varr_iter

#define m0_varr_iter	(		arr,
			type,
			idx,
			obj,
			start,
			end,
			inc
	)

Value:

({                                                                     \
        uint64_t              idx   = (start);                         \
        uint64_t              __end = (end);                           \
        uint64_t              __inc = (inc);                           \
        struct m0_varr       *__arr = (arr);                           \
        type                 *obj;                                     \
        int                   __rc;                                    \
        struct m0_varr_cursor __cursor;                                \
								       \
	M0_PRE(idx < __arr->va_nr && __end <= __arr->va_nr);          \
        M0_PRE(ergo(__arr->va_obj_shift > 0,                           \
                    sizeof *obj > M0_BITS(__arr->va_obj_shift - 1) &&  \
                    sizeof *obj <= M0_BITS(__arr->va_obj_shift)));     \
                                                                       \
        __rc = m0_varr_cursor_init(&__cursor, __arr, __arr->va_depth); \
        M0_ASSERT(__rc == 0);                                          \
        m0_varr_cursor_move(&__cursor, idx);                           \
        for (obj = m0_varr_cursor_get(&__cursor); idx < __end;         \
                idx += __inc, m0_varr_cursor_move(&__cursor, __inc),   \
                obj = m0_varr_cursor_get(&__cursor)) {                 \

Iterates over an arbitrary arithmetic progression of indices over the range [start, end).

Definition at line 234 of file varr.h.

Enumeration Type Documentation

m0_varr_tree_char

enum m0_varr_tree_char

Enumerator
M0_VA_TNODE_NR	Number of nodes which originate from root of radix tree.
M0_VA_TNODEPTR_SIZE	Size of pointer to a tree node.
M0_VA_TNODE_NR_SHIFT	Log (M0_VA_TNODE_NR) to base 2.
M0_VA_DEPTH_MAX	Maximum allowable depth of a tree.

Definition at line 86 of file varr.h.

Function Documentation

M0_BASSERT()

M0_BASSERT

(

M0_VA_TNODE_NR

= =M0_BITS(M0_VA_TNODE_NR_SHIFT)

)

m0_varr_cursor_get()

M0_INTERNAL void* m0_varr_cursor_get

(

struct m0_varr_cursor *

cursor

)

Returns a pointer corresponding to the current location of a cursor.

Precondition

m0_varr_cursor_init()

Definition at line 316 of file varr.c.

Here is the caller graph for this function:

m0_varr_cursor_init()

M0_INTERNAL int m0_varr_cursor_init	(	struct m0_varr_cursor *	cursor,
		const struct m0_varr *	arr,
		uint32_t	depth
	)

Initializes a cursor to the address of the first node at given depth.

Parameters

arr	[in] An array to which a cursor gets associated.
depth	[in] Depth to which cursor is initialized.
cursor	[out]

Return values

0	On success.
-EINVAL	On failure.

Precondition

arr != NULL

depth <= arr->va_depth

Definition at line 263 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_cursor_move()

M0_INTERNAL int m0_varr_cursor_move	(	struct m0_varr_cursor *	cursor,
		uint64_t	inc
	)

Moves the cursor location by 'inc', along the same level as m0_varr_cursor::vc_depth.

Return values

1	On success.
0	On completion of all nodes at level m0_varr_cursor::vc_depth.

Precondition

m0_varr_cursor_init()

Definition at line 327 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_cursor_next()

M0_INTERNAL int m0_varr_cursor_next

(

struct m0_varr_cursor *

cursor

)

Moves cursor to the next node at the same level as m0_varr_cursor::vc_depth.

Return values

1	On success.
0	On completion of all nodes at level m0_varr_cursor::vc_depth.

Definition at line 322 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_ele_get()

M0_INTERNAL void* m0_varr_ele_get	(	struct m0_varr *	arr,
		uint64_t	index
	)

Returns address of an object having index as 'index'. Updates an internal cache if required. Since concurrent access to the cache may result in spurious outcome, calls to m0_varr_ele_get() should be protected under a lock.

Precondition

arr != NULL && index < arr->va_nr.

Postcondition

varr_invariant(arr).

Definition at line 505 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_fini()

M0_INTERNAL void m0_varr_fini

(

struct m0_varr *

arr

)

Finalises a virtual array.

Precondition

varr_invariant(arr)

Definition at line 486 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_init()

M0_INTERNAL int m0_varr_init	(	struct m0_varr *	arr,
		uint64_t	nr,
		size_t	size,
		size_t	bufsize
	)

Initialises a virtual array.

Parameters

nr[in]	Length of array.
size[in]	Size of object to be stored in array.
bufsize[in]	Size of each buffer which stores the objects.

Return values

0	On success.
-ENOMEM	On failure.

Precondition

arr != NULL && nr > 0.

Postcondition

varr_invariant(arr).

Definition at line 114 of file varr.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_varr_size()

M0_INTERNAL uint64_t m0_varr_size

(

const struct m0_varr *

arr

)

Returns the number of elements stored in an array.

Definition at line 567 of file varr.c.

Here is the caller graph for this function: