云鉴权>> hisho>> 返回
项目作者： SourenP

项目描述 ：
Memory allocators written in C for learning purposes.
高级语言： C
项目地址: git://github.com/SourenP/hisho.git
创建时间： 2020-05-29T19:08:33Z
项目社区：https://github.com/SourenP/hisho
开源协议：
下载


Hisho

Memory allocators written in C for learning purposes.

Run

  1. make
  2. ./hisho_test
  3. make clean

Implementations

Buddy Allocator

  • Code: src/hisho_buddy.h src/hisho_buddy.c
  • Description:
    • A buddy memory allocator
    • Implemented using an array of doubly linked lists, each representing a level
    • On free, if a block’s buddy is also free, a block and its buddy will merge into a free block twice their size.
    • Each block has an overhead of 16 bytes for its header.
    • Written with the help of resources listed in #Resources.
  • Pros:
    • Farily simple implementation
    • Avoids external fragmentation
    • Freeing memory is fast
    • Memory blocks are word aligned
  • Cons:
    • 16 byte overhead due to header size
    • Internal fragmentation due to:
      • All block sizes being a power of 2
    • Fixed memory size set at compile time (#4)

  • Usage:

    1.   // alloc
    2.   char str[] = "hisho";
    3.   char *p = (char *)hisho_buddy__alloc(sizeof(str));
    4.   memcpy(p, str, sizeof(str));
    6.   // free
    7.   hisho_buddy__free(p);
  • Debug:
    1.   // Print blocks, by their size, in all free lists.
    2.   hisho_buddy__print_free_lists(stdout);
    1.   Level 0:
    2.   Level 1: 512
    3.   Level 2: 256
    4.   Level 3: 128
    5.   Level 4: 64
  • Todo
    • #2 Block size index can be optimized
    • #3 Block free index can be optimized
    • #4 Support setting the buddy allocator size at runtime

Dynamic memory allocator with ‘first fit’ strategy

  • Code: src/hisho_ff.h src/hisho_ff.c
  • Description:
    • A storage allocator implemented with a linked list that allocates blocks using the ‘first fit’ strategy.
    • Each block has an overhead of 16 bytes for its header.
    • On free a block will coalesce with the next block if it’s unused, but not the previous block.
    • All block sizes are a multiple of the block header size for alignment purposes.
    • Written with the help of resources listed in #Resources.
  • Pros:
    • Simple implementation
    • Avoids external fragmentation to a certain degree
    • Memory blocks are word aligned
  • Cons:
    • 16 byte overhead due to header size (todo)
    • Internal fragmentation due to:
      • block sizes being a miltiple of the header size
    • External fragmentation due to:
      • simplicity of first fit strategy
      • coalescing only occuring with next block (todo)
    • Fixed memory expansion size set at compile time (todo)

  • Usage:

    1.   // alloc
    2.   char str[] = "hisho";
    3.   char *p = (char *)hisho_ff__alloc(sizeof(str));
    4.   memcpy(p, str, sizeof(str));
    6.   // free
    7.   hisho_ff__free(p);

  • Debug:

    1.   // Print a table of all blocks and their properties
    2.   hisho_ff__print_blocks(stdout);
    4.   // Print stats about the allocator
    5.   hisho_ff__print_stats(stdout);
    1.   Blocks
    2.           Header          Units           Size            Used            Next            Chars
    3.           0x1059bc420     0               0               1               0x1092e6000
    4.           0x1092e6000     1               16              1               0x1092e6030     hisho
    5.           0x1092e6030     1020            16320           0               0x0
    7.   Stats
    8.           Header U        Buffer U        Free U          Total U         Total S
    9.           2               1               1020            1023            16368
  • Todo
    • Add functionality to coalese with prev block
    • Reduce size of header to sizeof(size_t) instead of 2*sizeof(size_t)
      • Encode is_used into u_size‘s first bit
    • Allow option to initalize allocator in order to set parameters like expansion size.

Static memory allocator with stack

  • Code: src/hisho_s.h src/hisho_s.c
  • Description:
    • A rudimentary storage allocator that uses a LIFO queue (stack) to manage memory.
    • Free calls must be made in opposite order to the alloc calls.
    • Memory is fixed in size and stored in a static variable (data segment of virtual address space of program).
    • Written with the help of resources listed in #Resources.
  • Pros:
    • Very simple implementation
    • No fragmentation since data stored sequentially
  • Cons:
    • Fixed size that must be set at compile time
    • Can only free last allocation
    • Wastes unused memory space

  • Usage:

    1.   // alloc
    2.   char str[] = "hisho";
    3.   char *p = hisho_s__alloc(sizeof(str));
    4.   memcpy(p, str, sizeof(str));
    6.   // free
    7.   hisho_s__free(p);
  • Debug:
    1.   // Print memory and head pointer
    2.   hisho_s__print();
    1.   [hisho       ]
    2.   [     ^      ]

Resources

Namesake

“hishoghutyun” (հիշողություն) means “memory” in Armenian. Hisho is short for that :)