program

malloc

Algorithms

The main properties of the algorithms are:

  • For large (>= 512 bytes) requests, it is a pure best-fit allocator,
    with ties normally decided via FIFO (i.e. least recently used).
  • For small (<= 64 bytes by default) requests, it is a caching
    allocator, that maintains pools of quickly recycled chunks.
  • In between, and for combinations of large and small requests, it does
    the best it can trying to meet both goals at once.
  • For very large requests (>= 128KB by default), it relies on system
    memory mapping facilities, if supported.

Test

  • test code

    // gcc -o t t.c
#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0])

void test(size_t require)
{
    char* p = malloc(require);
    char* q = malloc(1);
    size_t size = malloc_usable_size(p);
    printf("memory require %lu, allocated %lu, address %p, next address %p, dis %ld\n",
            require, size, p, q, q-p);
    free(p);
    free(q);
}

int main()
{
    int fast_bin[] = {1, 2, 4, 8, 20, 24};
    int small_bin[] = {25, 30, 40, 41, 50, 60, 64, 70, 72, 73};
    int large_bin[] = {1024, 128*1024, 135*1024, 256*1024, 512*1024, 1024*1024};
    int i=0;
    printf("-----------Fast bin: memory pool-------------\n");
    for (i=0;i<ARRAY_SIZE(fast_bin);i++) {
        test(fast_bin[i]);
    }
    printf("-----------Samll bin-------------\n");
    for (i=0;i<ARRAY_SIZE(small_bin);i++) {
        test(small_bin[i]);
    }
    printf("-----------Large bin-------------\n");
    for (i=0;i<ARRAY_SIZE(large_bin);i++) {
        test(large_bin[i]);
    }
    return 0;
}

  • test

    dennis@dennis:~/tt$ ./t
-----------Fast bin-------------
memory require 1, allocated 24, address 0x6ea010, next address 0x6ea030, dis 32
memory require 2, allocated 24, address 0x6ea030, next address 0x6ea010, dis -32
memory require 4, allocated 24, address 0x6ea010, next address 0x6ea030, dis 32
memory require 8, allocated 24, address 0x6ea030, next address 0x6ea010, dis -32
memory require 20, allocated 24, address 0x6ea010, next address 0x6ea030, dis 32
memory require 24, allocated 24, address 0x6ea030, next address 0x6ea010, dis -32
-----------Samll bin-------------
memory require 25, allocated 40, address 0x6ea050, next address 0x6ea010, dis -64
memory require 30, allocated 40, address 0x6ea050, next address 0x6ea010, dis -64
memory require 40, allocated 40, address 0x6ea050, next address 0x6ea010, dis -64
memory require 41, allocated 56, address 0x6ea080, next address 0x6ea010, dis -112
memory require 50, allocated 56, address 0x6ea080, next address 0x6ea010, dis -112
memory require 60, allocated 72, address 0x6ea0c0, next address 0x6ea010, dis -176
memory require 64, allocated 72, address 0x6ea0c0, next address 0x6ea010, dis -176
memory require 70, allocated 72, address 0x6ea0c0, next address 0x6ea010, dis -176
memory require 72, allocated 72, address 0x6ea0c0, next address 0x6ea010, dis -176
memory require 73, allocated 88, address 0x6ea110, next address 0x6ea010, dis -256
-----------Large bin-------------
memory require 1024, allocated 1032, address 0x6ea010, next address 0x6ea420, dis 1040
memory require 102400, allocated 102408, address 0x6ea010, next address 0x703020, dis 102416
memory require 131072, allocated 131080, address 0x6ea010, next address 0x70a020, dis 131088
memory require 262144, allocated 266224, address 0x7f0fc1283010, next address 0x6ea010, dis -139705634623488
memory require 524288, allocated 528368, address 0x7f0fc1243010, next address 0x6ea010, dis -139705634361344
memory require 1048576, allocated 1052656, address 0x7f0fc11c3010, next address 0x6ea010, dis -139705633837056

When require memory size less than 24, use fastbin to allocate memory;
When require size large than 24, use smallbin

Reference