catalogue

I Configurator for SGI

II First level configurator (malloc_alloc)

III Secondary Configurator

3.1 notes

3.2 space configurator allocate()

3.3 refill(size_t n)

3.4 encapsulate the first and second level configurators

I Configurator for SGI

SGI designed a two-level configurator: 1 When the configuration block exceeds 128 bytes, call the first level configurator, that is, indirectly call malloc() and free(); 2. When the configuration area is less than 128 bytes fast, it is regarded as "too small", and the second level configurator is adopted.

II First level configurator (malloc_alloc)

The first level configurators allocator() and reallocate() of SGI call malloc() and realloc () indirectly. When malloc() and realloc () cannot meet the requirements, use oom instead_ malloc() and oom_realloc(). Here, take allocator() as an example. Realloc () is similar to:

static void * allocate(size_t n)
{
    void *result = malloc(n);
    if(0 == result) result = oom_malloc();//When malloc() cannot be satisfied, use oom instead_ malloc()
    return result;
}

III Secondary Configurator

When the memory space to be configured is less than 128 bytes, the second level configurator is called.

3.1 notes

        1. The most important thing in the second level configurator is the union pointer and the union variable free_list[16], the obj * type variable stored in the array can not only point to the first address of multiple blocks applied from the memory pool, but also the free in the obj consortium_ list_ The link pointer can also store the address pointing to the next block of the same size. Because free_list[n] array has 16 array elements, so each array element points to the block linked list with the size of n*8, and the last array element refers to the block with the size of 128 bytes:

union obj{
    union obj * free_list_link;
    char client_data[1];
};
static obj * volatile free_list[16];

        2. free_ The block address stored in the list [16] array comes from the memory pool. Since the address of the memory pool is limited, two pointers are needed to indicate the front and back addresses of the available memory pool address:

static char *start_free;//Only in chunk_ Changes in alloc()
static char *end_free;//Only in chunk_ Changes in alloc()

Allocate space (2.3)

1. When it is greater than 128 bytes, the first level configurator malloc is called_ alloc().

2. When less than 128 bytes:

• Determine the block element to be used according to the incoming size n:

        

obj * volatile * my_free_list = free_list + FREELIST_INDEX(n);//Freelist when n=90_ Index (n) = 11 to use free_list[11]

• Address pointing to the array element (pointer of obj type):

obj * result = *my_free_list;

• Adjust the 12th array element free_list[11] to store the next block with the size of 12 * 8 bytes:

*my_free_list = result->free_list_link;

• Return the result (the type is obj *. When returning, because the return value type of the function is void *, it is forcibly converted to void *) variable.

3.3 refill(size_t n)

This function is used for allocator() function. When configuring memory, free_ When the element in the list [16] array does not store the address pointing to the block of the corresponding size (the value is NULL), the element will be reassigned to the linked list composed of several blocks of the corresponding size.

• Using chunk_alloc() function takes out several blocks of corresponding size from the memory pool (the number is determined by the specific memory pool size. When the size is enough, 20 blocks of corresponding size are established by default):

char * chunk  = chunk_alloc(n, nobjs);//n represents the number of bytes raised to a multiple of 8; Nobjs indicates the number of blocks actually configured. Since the function is passed by reference, the value of nobjs will be directly modified by the function

• If the number of blocks taken from the memory pool is 1, it is directly passed to the allocate() function for use. Otherwise, adjust free_list array, including new nodes:

obj * result = (obj *)chunk;//This block is returned to the client for use
*my_free_list = next_obj = (obj *)(chunk + n);
//String the nodes of the free list
for(int i = 1; ; i++)
{
    current_obj = next_obj;
    next_obj = (obj *)((char *)next_obj + n);
    if(nobjs - 1 == i){
        current_obj -> free_list_link = 0;
        break;
    } else {
        current_obj -> free_list_link = next_obj;
    }
}

3.4 encapsulate the first and second level configurators

        

template<class T, class Alloc>//Alloc passes in the first or second level Configurator
class simple_alloc{
public:
    static T *allocate(size_t n)
        return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof(T));

    static T * allocate(void)
        return (T*) Alloc::allocate(sizeof(T));
    static void deallocate(T *p, size_t n)
        if(0 != n) Alloc::deallocate(p, n * sizeof(T));
    static void deallocate(T *p)
        if(0 == n) Alloc::deallocate(p, sizeof(T));
};