1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
<!DOCTYPE html>
<html>
<head>
<title>Drop-in Heap</title>
<link rel="stylesheet" href="/style.css">
</head>
<body>
<div class="page-body-border"><div class="page-body">
<h1 class="page-body-top">Drop-in Heap</h1>
<div class="page-body-content">
<table class="page-body-buttons" style="width: 20%; margin: 0px;">
<tr><td><div class="link-button-border"><a class="link-button" href="/">Home</a></div></td></tr>
<tr><td><div class="link-button-border"><a class="link-button" href="https://git.jonsantmyer.com/diheap/">Git repository</a></div></td></tr>
<tr><td><div class="link-button-border"><a class="link-button" href="https://git.jonsantmyer.com/diheap/snapshot/diheap-1.0.tar.gz">Download (1.0 tar.gz)</a></div></td></tr>
<tr><td><div class="link-button-border"><a class="link-button" href="https://git.jonsantmyer.com/diheap/snapshot/diheap-1.0.zip">Download (1.0 zip)</a></div></td></tr>
</table>
<h3>Purpose</h3>
<p>
diheap was designed for the Modit Operating System. Therefore, it was created with the assumption that the linked libraries have direct access to memory and has no other dynamic allocation scheme.
Because of these constraints, the heap has an initial capacity as defined by the user through the "heap_create" function. To expand the heap, the user has to allocate the memory following it's bounds.
</p>
<h3>Design</h3>
<p>
A vast majority of the technical descriptions of how the heap works are in the header file. see <a href="https://git.jonsantmyer.com/diheap/tree/heap.h">heap.h</a> for more details.
</p><p>
diheap is a thread-unsafe double linked-list bucket heap allocator. It was written to allow for respectably fast variable size object allocations without external memory regions.
The heap information is stored in a single heap struct, which is created through heap_create.
</p><p>
When heap_create is called, the library creates a struct called a "crate", which stores the buckets used for heap allocation. Each crate is 4KiB in size, and can store an arbitrary ammount of buckets.
When the crate is out of buckets, another crate is appended to the last allocation and is linked to the previous crate.
</p><p>
Buckets act as both a pointer to allocated memory and a node in a doubly linked list.
Buckets store their neighbors, the address, size, and if the bucket is occupied.
The elements buckets store allows for checking the status of an arbitrary ammount of neighbors from any point in the linked list.
Buckets that don't have a memory address assigned to them are added to a free list, which lets the heap allocate more memory for itself.
When the freelist is drained, a new crate is created at the end of the address space and the new buckets are added to the freelist.
</p>
<h3>API</h3>
<p>diheap is designed to "drop in" to any project. I designed the interface to be independent of the system and operate without many quality of life features like dynamic memory and reference counting.</p>
<//heap_create>
<p class="text-inset"><font color="green">int</font> heap_create(<font color="green">struct</font> heap <font color="red">*</font>heap, <font color="green">uintptr_t</font> at, <font color="green">size_t</font> len);</p>
<p>Populates the heap with the initial crate and bucket lists. Fills the fields in the provided heap object with the bucket lists and usage information.</p>
<p class="text-inset">heap</p><p style="display:inline-block;">Pointer to object defined at compile time.</p><br/>
<p class="text-inset">at</p><p style="display:inline-block;">Address allocated for heap to operate in</p><br/>
<p class="text-inset">len</p><p style="display:inline-block">Size of memory allocated for heap to operate in. Must be larger than MODIT_HEAP_CRATE_SIZE</p><br/>
<p class="text-inset">return</p><p style="display:inline-block">Success code. Anything that is not zero should be treated as an error code.</p><br/><br/><br/>
<//heap_resize>
<p class="text-inset"><font color="green">void</font> heap_resize(<font color="green">struct</font> heap <font color="red">*</font>heap, <font color="green">size_t</font> newlen);</p>
<p>Marks the space appended by newlen as usable inside of the passed heap.</p>
<p class="text-inset">heap</p><p style="display:inline-block;">Pointer to heap object in which to resize.</p><br/>
<p class="text-inset">newlen</p><p style="display:inline-block">Size of memory appended to the heap allocation space. Because the heap cannot be relocated, this is the only way to expand it.</p><br/><br/><br/>
<//heap_alloc>
<p class="text-inset"><font color="green">void</font> <font color="red">*</font>heap_alloc(<font color="green">struct</font> heap <font color="red">*</font>heap, <font color="green">size_t</font> size);</p>
<p>Looks for and assigns the best fitting empty block in heap memory. If the block is too large, the heap splits the block into a perfectly sized bucket and a spare bucket. The heap returns the perfectly sized bucket if possible.</p>
<p class="text-inset">heap</p><p style="display:inline-block;">Pointer to heap object in which to make the allocation</p><br/>
<p class="text-inset">size</p><p style="display:inline-block">Size of memory allocated in heap.</p><br/>
<p class="text-inset">return</p><p style="display:inline-block">Pointer to memory assigned by heap. If the heap has run out of memory, function returns <font color="purple">NULL</font></p><br/><br/><br/>
<//heap_free>
<p class="text-inset"><font color="green">void</font> heap_free(<font color="green">struct</font> heap <font color="red">*</font>heap, <font color="green">void</font> <font color="red">*</font>ptr);</p>
<p>Looks for the bucket corresponding to the passed pointer and clears the taken flag bit. When two buckets are adjacent and free, they are merged.</p>
<p class="text-inset">heap</p><p style="display:inline-block;">Pointer to heap object in which to make the allocation</p><br/>
<p class="text-inset">size</p><p style="display:inline-block">Size of memory allocated in heap.</p><br/>
<p class="text-inset">return</p><p style="display:inline-block">Pointer to memory assigned by heap. If the heap has run out of memory, function returns <font color="purple">NULL</font></p>
<h3>Building</h3>
<p>diheap can be built as either a static or linked library</p>
<p class="text-inset">NOTE: build instructions are written assuming linux with gcc</p>
<br/>
<p style="display:inline-block;">diheap is built using a makefile following GNU Make specifications. To build the library, simply call<p class="text-inset">make</p></p>
<p>By default, the makefile builds a shared library without debugging symbols. This can be changed with the following build flags:</p>
<p class="text-inset">SHARED</p><p style="display:inline-block"> Defines if the makefile should build a shared library.</p><p class="text-inset">default: 1</p><br/>
<p class="text-inset">STATIC</p><p style="display:inline-block"> Defines if the makefile should build a static library.</p><p class="text-inset">default: 0</p><br/>
<p class="text-inset">TEST</p><p style="display:inline-block"> Forces the makefile to build a shared library and test program. Said program automatically runs.</p><p class="text-inset">default: 0</p>
</div>
<p class="text-inset">
LICENSE: MIT (c) 2021 Jon Santmyer (jon@jonsantmyer.com)
</p>
</div>
</body>
</html>
|
