2. VPP源码分析（内存管理之抽象数据结构）

1.2. 抽象数据结构

1.2.1. vector

CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
Many CLIB data structures (e.g. hash, heap, pool) are vectors with various different headers.

The memory layout looks like this:

                  user header (aligned to uword boundary)
                  vector length: number of elements
 user's pointer-> vector element #0
                  vector element #1
                  ...

vector结构经常和user定义的header结合

Many macros have _a variants supporting alignment of vector data and _h variants supporting non zero length vector headers.
The _ha variants support both

1.2.2. bitmap

Set and get bits with indexes.Lots of them. Implemented as a uword vector.
typedef uword clib_bitmap_t;

uword *bitmap = 0;
clib_bitmap_alloc(bitmap, 100);     //Allocate bitmap for 100 bits
clib_bitmap_validate(bitmap, 200); //Make room for 201 bits
clib_bitmap_set(bitmap, 33, 1);
clib_bitmap_get(bitmap, 33);

uword a = clib_bitmap_get_multiple(bitmap, 3, 10); //Get bits from 3 to 12 included
uword clib_bitmap_first_set(uword *ai);
uword clib_bitmap_first_clear(uword *ai);
uword clib_bitmap_next_set(uword *ai, uword i);
uword clib_bitmap_next_clear(uword *ai, uword i);
uword clib_bitmap_count_set_bits(uword *ai);

1.2.3. pool

Fixed sized element allocator. Based on a vec and a bitmap.

• free_bitmap：Bitmap of indices of free objects.
• free_indices：Vector of free indices. One element for each set bit in bitmap.

The following fields are set for fixed-size, preallocated pools

• max_elts：Maximum size of the pool, in elements
• mmap_base, mmap_size：mmap segment info: base + length
  

T *pool = 0;
T *e;
pool_get(pool, e);
//pool_get_aligned(pool, e, 4);

//Query if element is free
pool_is_free(pool,e);
pool_is_free_index(pool, e – pool);

//Unalloc element
pool_put(pool,e);

//Free the whole pool
pool_free(pool);

// Allocated element count
pool_elts(pool);

1.2.4. heap

Variable element size allocator. 和pool类似只不过pool中的每个元素是定长的而heap中的元素是变长的。
pool和heap是建立在vec和bitmap上的两种高级数据结构，而mheap是实现这些数据结构的最基础的内存管理单元，这里不要混淆了。

• elts：Vector of used and free elements.
• small_free_elt_free_index：For elt_bytes < sizeof (u32) we need some extra space per elt to store free list index.
• free_elts：Vector of free indices of elts array.
• free_lists：Indices of free elts indexed by size bin.
• used_elt_bitmap：Used for validattion/debugging.
• head, tail：First and last element of doubly linked chain of elements.
• elt_bytes：Number of bytes in a help element.

T *heap = 0;
T *e;

//Allocate 4xT.
U32 handle;
u32 offset = heap_alloc(heap, 4, handle);

//Allocated heap[offset] – heap[offset + 4]
//Object size
heap_size(heap, handle);

//Deallocate
heap_dealloc(heap, handle);

Rarely used (pools are faster). Still efficient.
To be used if you need variably sized allocations.
e.g. classifier

1.3. 内存管理的目的

提高cache命中率！！！