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 bitsclib_bitmap_validate(bitmap, 200); //Make room for 201 bitsclib_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 includeduword 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 freepool_is_free(pool,e);pool_is_free_index(pool, e – pool);//Unalloc elementpool_put(pool,e);//Free the whole poolpool_free(pool);// Allocated element countpool_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 sizeheap_size(heap, handle);//Deallocateheap_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命中率！！！