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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
/* malloc.c - C standard library routine.
Copyright (c) 1989, 1993 Michael J. Haertel
You may redistribute this library under the terms of the
GNU Library General Public License (version 2 or any later
version) as published by the Free Software Foundation.
THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED
WARRANTY. IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR
WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS
SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "malloc.h"
/* How to really get more memory. */
void *(*__morecore)(long) = __default_morecore_init;
/* Pointer to the base of the first block. */
char *_heapbase;
/* Block information table. */
union info *_heapinfo;
/* Number of info entries. */
static int heapsize;
/* Search index in the info table. */
int _heapindex;
/* Limit of valid info table indices. */
int _heaplimit;
/* Count of large blocks allocated for each fragment size. */
int _fragblocks[BLOCKLOG];
/* Free lists for each fragment size. */
struct list _fraghead[BLOCKLOG];
/* Are we experienced? */
static int initialized;
/* Aligned allocation. */
static void *
align(size_t size)
{
void *result;
unsigned int adj;
result = (*__morecore)(size);
adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE;
if (adj != 0) {
(*__morecore)(adj = BLOCKSIZE - adj);
result = (char *) result + adj;
}
return result;
}
/* Set everything up and remember that we have. */
static int
initialize(void)
{
heapsize = HEAP / BLOCKSIZE;
_heapinfo = align(heapsize * sizeof (union info));
if (!_heapinfo)
return 0;
memset(_heapinfo, 0, heapsize * sizeof (union info));
_heapinfo[0].free.size = 0;
_heapinfo[0].free.next = _heapinfo[0].free.prev = 0;
_heapindex = 0;
_heapbase = (char *) _heapinfo;
initialized = 1;
return 1;
}
/* Get neatly aligned memory, initializing or growing the
heap info table as necessary. */
static void *
morecore(size_t size)
{
void *result;
union info *newinfo, *oldinfo;
int newsize;
result = align(size);
if (!result)
return NULL;
/* Check if we need to grow the info table. */
if (BLOCK((char *) result + size) > heapsize) {
newsize = heapsize;
while (BLOCK((char *) result + size) > newsize)
newsize *= 2;
newinfo = align(newsize * sizeof (union info));
if (!newinfo) {
(*__morecore)(-size);
return NULL;
}
memset(newinfo, 0, newsize * sizeof (union info));
memcpy(newinfo, _heapinfo, heapsize * sizeof (union info));
oldinfo = _heapinfo;
newinfo[BLOCK(oldinfo)].busy.type = 0;
newinfo[BLOCK(oldinfo)].busy.info.size
= BLOCKIFY(heapsize * sizeof (union info));
_heapinfo = newinfo;
#if 0
free(oldinfo);
#else
_free_internal (oldinfo);
#endif
heapsize = newsize;
}
_heaplimit = BLOCK((char *) result + size);
return result;
}
/* Allocate memory from the heap. */
void *
malloc (size_t size)
{
void *result;
int log, block, blocks, i, lastblocks, start;
struct list *next;
if (!initialized && !initialize())
return NULL;
/* Some programs will call malloc (0). We let them pass. */
#if 0
if (size == 0)
return NULL;
#endif
if (size < sizeof (struct list))
size = sizeof (struct list);
/* Determine the allocation policy based on the request size. */
if (size <= BLOCKSIZE / 2) {
/* Small allocation to receive a fragment of a block. Determine
the logarithm to base two of the fragment size. */
--size;
for (log = 1; (size >>= 1) != 0; ++log)
;
/* Look in the fragment lists for a free fragment of the
desired size. */
if ((next = _fraghead[log].next) != 0) {
/* There are free fragments of this size. Pop a fragment
out of the fragment list and return it. Update the block's
nfree and first counters. */
result = next;
next->prev->next = next->next;
if (next->next)
next->next->prev = next->prev;
block = BLOCK(result);
if (--_heapinfo[block].busy.info.frag.nfree)
_heapinfo[block].busy.info.frag.first
= (unsigned int) ((char *) next->next - (char *) NULL)
% BLOCKSIZE >> log;
} else {
/* No free fragments of the desired size, so get a new block
and break it into fragments, returning the first. */
result = malloc(BLOCKSIZE);
if (!result)
return NULL;
++_fragblocks[log];
/* Link all fragments but the first into the free list. */
next = (struct list *) ((char *) result + (1 << log));
next->next = 0;
next->prev = &_fraghead[log];
_fraghead[log].next = next;
for (i = 2; i < BLOCKSIZE >> log; ++i) {
next = (struct list *) ((char *) result + (i << log));
next->next = _fraghead[log].next;
next->prev = &_fraghead[log];
next->prev->next = next;
next->next->prev = next;
}
/* Initialize the nfree and first counters for this block. */
block = BLOCK(result);
_heapinfo[block].busy.type = log;
_heapinfo[block].busy.info.frag.nfree = i - 1;
_heapinfo[block].busy.info.frag.first = i - 1;
}
} else {
/* Large allocation to receive one or more blocks. Search
the free list in a circle starting at the last place visited.
If we loop completely around without finding a large enough
space we will have to get more memory from the system. */
blocks = BLOCKIFY(size);
start = block = _heapindex;
while (_heapinfo[block].free.size < blocks) {
block = _heapinfo[block].free.next;
if (block == start) {
/* Need to get more from the system. Check to see if
the new core will be contiguous with the final free
block; if so we don't need to get as much. */
block = _heapinfo[0].free.prev;
lastblocks = _heapinfo[block].free.size;
if (_heaplimit && block + lastblocks == _heaplimit
&& (*__morecore)(0) == ADDRESS(block + lastblocks)
&& morecore((blocks - lastblocks) * BLOCKSIZE)) {
/* Note that morecore() can change the location of
the final block if it moves the info table and the
old one gets coalesced into the final block. */
block = _heapinfo[0].free.prev;
_heapinfo[block].free.size += blocks - lastblocks;
continue;
}
result = morecore(blocks * BLOCKSIZE);
if (!result)
return NULL;
block = BLOCK(result);
_heapinfo[block].busy.type = 0;
_heapinfo[block].busy.info.size = blocks;
return result;
}
}
/* At this point we have found a suitable free list entry.
Figure out how to remove what we need from the list. */
result = ADDRESS(block);
if (_heapinfo[block].free.size > blocks) {
/* The block we found has a bit left over, so relink the
tail end back into the free list. */
_heapinfo[block + blocks].free.size
= _heapinfo[block].free.size - blocks;
_heapinfo[block + blocks].free.next
= _heapinfo[block].free.next;
_heapinfo[block + blocks].free.prev
= _heapinfo[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next
= _heapinfo[_heapinfo[block].free.next].free.prev
= _heapindex = block + blocks;
} else {
/* The block exactly matches our requirements, so
just remove it from the list. */
_heapinfo[_heapinfo[block].free.next].free.prev
= _heapinfo[block].free.prev;
_heapinfo[_heapinfo[block].free.prev].free.next
= _heapindex = _heapinfo[block].free.next;
}
_heapinfo[block].busy.type = 0;
_heapinfo[block].busy.info.size = blocks;
}
return result;
}
|
