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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
//----------------------------------------------------------------
// Statically-allocated memory manager
//
// by Eli Bendersky (eliben@gmail.com)
//
// This code is in the public domain.
//----------------------------------------------------------------
#include "memmgr.h"
typedef ulong Align;
union mem_header_union
{
struct
{
// Pointer to the next block in the free list
//
union mem_header_union* next;
// Size of the block (in quantas of sizeof(mem_header_t))
//
ulong size;
} s;
// Used to align headers in memory to a boundary
//
Align align_dummy;
};
typedef union mem_header_union mem_header_t;
// Initial empty list
//
static mem_header_t base;
// Start of free list
//
static mem_header_t* freep = 0;
// Static pool for new allocations
//
static byte pool[POOL_SIZE] = {0};
static ulong pool_free_pos = 0;
void memmgr_init()
{
base.s.next = 0;
base.s.size = 0;
freep = 0;
pool_free_pos = 0;
}
static mem_header_t* get_mem_from_pool(ulong nquantas)
{
ulong total_req_size;
mem_header_t* h;
if (nquantas < MIN_POOL_ALLOC_QUANTAS)
nquantas = MIN_POOL_ALLOC_QUANTAS;
total_req_size = nquantas * sizeof(mem_header_t);
if (pool_free_pos + total_req_size <= POOL_SIZE)
{
h = (mem_header_t*) (pool + pool_free_pos);
h->s.size = nquantas;
memmgr_free((void*) (h + 1));
pool_free_pos += total_req_size;
}
else
{
return 0;
}
return freep;
}
// Allocations are done in 'quantas' of header size.
// The search for a free block of adequate size begins at the point 'freep'
// where the last block was found.
// If a too-big block is found, it is split and the tail is returned (this
// way the header of the original needs only to have its size adjusted).
// The pointer returned to the user points to the free space within the block,
// which begins one quanta after the header.
//
void* memmgr_alloc(ulong nbytes)
{
mem_header_t* p;
mem_header_t* prevp;
// Calculate how many quantas are required: we need enough to house all
// the requested bytes, plus the header. The -1 and +1 are there to make sure
// that if nbytes is a multiple of nquantas, we don't allocate too much
//
ulong nquantas = (nbytes + sizeof(mem_header_t) - 1) / sizeof(mem_header_t) + 1;
// First alloc call, and no free list yet ? Use 'base' for an initial
// denegerate block of size 0, which points to itself
//
if ((prevp = freep) == 0)
{
base.s.next = freep = prevp = &base;
base.s.size = 0;
}
for (p = prevp->s.next; ; prevp = p, p = p->s.next)
{
// big enough ?
if (p->s.size >= nquantas)
{
// exactly ?
if (p->s.size == nquantas)
{
// just eliminate this block from the free list by pointing
// its prev's next to its next
//
prevp->s.next = p->s.next;
}
else // too big
{
p->s.size -= nquantas;
p += p->s.size;
p->s.size = nquantas;
}
freep = prevp;
return (void*) (p + 1);
}
// Reached end of free list ?
// Try to allocate the block from the pool. If that succeeds,
// get_mem_from_pool adds the new block to the free list and
// it will be found in the following iterations. If the call
// to get_mem_from_pool doesn't succeed, we've run out of
// memory
//
else if (p == freep)
{
if ((p = get_mem_from_pool(nquantas)) == 0)
{
#ifdef DEBUG_MEMMGR_FATAL
printf("!! Memory allocation failed !!\n");
#endif
return 0;
}
}
}
}
// Scans the free list, starting at freep, looking the the place to insert the
// free block. This is either between two existing blocks or at the end of the
// list. In any case, if the block being freed is adjacent to either neighbor,
// the adjacent blocks are combined.
//
void memmgr_free(void* ap)
{
mem_header_t* block;
mem_header_t* p;
// acquire pointer to block header
block = ((mem_header_t*) ap) - 1;
// Find the correct place to place the block in (the free list is sorted by
// address, increasing order)
//
for (p = freep; !(block > p && block < p->s.next); p = p->s.next)
{
// Since the free list is circular, there is one link where a
// higher-addressed block points to a lower-addressed block.
// This condition checks if the block should be actually
// inserted between them
//
if (p >= p->s.next && (block > p || block < p->s.next))
break;
}
// Try to combine with the higher neighbor
//
if (block + block->s.size == p->s.next)
{
block->s.size += p->s.next->s.size;
block->s.next = p->s.next->s.next;
}
else
{
block->s.next = p->s.next;
}
// Try to combine with the lower neighbor
//
if (p + p->s.size == block)
{
p->s.size += block->s.size;
p->s.next = block->s.next;
}
else
{
p->s.next = block;
}
freep = p;
}
|
