summaryrefslogtreecommitdiff
path: root/libc/stdlib/malloc-930716/malloc.c
blob: 2467da41ce219dc1a884c01c038c808a784a8608 (plain)
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
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
/* 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. */

#define _GNU_SOURCE
#include <features.h>
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "malloc.h"

#ifdef __UCLIBC_HAS_THREADS__
#include <pthread.h>
pthread_mutex_t __malloclock = PTHREAD_MUTEX_INITIALIZER;
# define LOCK	pthread_mutex_lock(&__malloclock)
# define UNLOCK	pthread_mutex_unlock(&__malloclock);
#else
# define LOCK
# define UNLOCK
#endif


/* Stuff that is shared across .o files */

/* Pointer to the base of the first block. */
char *_heapbase;
/* Block information table. */
union info *_heapinfo;
/* Search index in the info table. */
size_t _heapindex;
/* Limit of valid info table indices. */
size_t _heaplimit;
/* List of blocks allocated with memalign or valloc */
struct alignlist *_aligned_blocks;

    

/* Stuff that is local to this .o file only */

/* How to really get more memory. */
static void * __morecore(long size);
/* Number of info entries. */
static size_t heapsize;
/* Count of large blocks allocated for each fragment size. */
static size_t _fragblocks[BLOCKLOG];
/* Free lists for each fragment size. */
static struct list _fraghead[BLOCKLOG];
/* Are we experienced? */
static int initialized;


/* Aligned allocation.
 * Called within the lock in initialize() and morecore(), 
 * so no explicit locking needed... */
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. 
 * Called within the lock in malloc(), so no
 * explicit locking needed... */
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. 
 * Called within a lock in malloc() and free(), 
 * so no explicit locking needed... */
static void * morecore(size_t size)
{
    void *result;
    union info *newinfo, *oldinfo;
    size_t 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;
	__free_unlocked(oldinfo);
	heapsize = newsize;
    }

    _heaplimit = BLOCK((char *) result + size);
    return result;
}

/* Note that morecore has to take a signed argument so
   that negative values can return memory to the system. */
static void * __morecore(long size)
{
    void *result;

    result = sbrk(size);
    if (result == (void *) -1)
	return NULL;
    return result;
}

/* Allocate memory from the heap. */
void * malloc (size_t size)
{
    void * ptr;
    LOCK;
    ptr = __malloc_unlocked(size);
    UNLOCK;
    return(ptr);
}

void * __malloc_unlocked (size_t size)
{
    void *result;
    size_t log, block, blocks, i, lastblocks, start;
    struct list *next;

    /* Some programs will call malloc (0).  Lets be strict and return NULL */
    if (size == 0)
	return NULL;

    if (size < sizeof (struct list))
	size = sizeof (struct list);

    if (!initialized && !initialize()) {
	return NULL;
    }

    /* 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_unlocked(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;
}

/* Return memory to the heap. */
void free(void *ptr)
{
    struct alignlist *l;

    if (ptr == NULL)
	return;

    LOCK;
    for (l = _aligned_blocks; l != NULL; l = l->next) {
	if (l->aligned == ptr) {
	    /* Mark the block as free */
	    l->aligned = NULL;
	    ptr = l->exact;
	    break;
	}
    }

    __free_unlocked(ptr);
    UNLOCK;
}

void __free_unlocked(void *ptr)
{
    int block, blocks, i, type;
    struct list *prev, *next;

    if (ptr == NULL)
	return;


    block = BLOCK(ptr);

    switch (type = _heapinfo[block].busy.type) {
	case 0:
	    /* Find the free cluster previous to this one in the free list.
	       Start searching at the last block referenced; this may benefit
	       programs with locality of allocation. */
	    i = _heapindex;
	    if (i > block)
		while (i > block)
		    i = _heapinfo[i].free.prev;
	    else {
		do
		    i = _heapinfo[i].free.next;
		while (i > 0 && i < block);
		i = _heapinfo[i].free.prev;
	    }

	    /* Determine how to link this block into the free list. */
	    if (block == i + _heapinfo[i].free.size) {
		/* Coalesce this block with its predecessor. */
		_heapinfo[i].free.size += _heapinfo[block].busy.info.size;
		block = i;
	    } else {
		/* Really link this block back into the free list. */
		_heapinfo[block].free.size = _heapinfo[block].busy.info.size;
		_heapinfo[block].free.next = _heapinfo[i].free.next;
		_heapinfo[block].free.prev = i;
		_heapinfo[i].free.next = block;
		_heapinfo[_heapinfo[block].free.next].free.prev = block;
	    }

	    /* Now that the block is linked in, see if we can coalesce it
	       with its successor (by deleting its successor from the list
	       and adding in its size). */
	    if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) {
		_heapinfo[block].free.size
		    += _heapinfo[_heapinfo[block].free.next].free.size;
		_heapinfo[block].free.next
		    = _heapinfo[_heapinfo[block].free.next].free.next;
		_heapinfo[_heapinfo[block].free.next].free.prev = block;
	    }

	    /* Now see if we can return stuff to the system. */
	    blocks = _heapinfo[block].free.size;
	    if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
		    && __morecore(0) == ADDRESS(block + blocks)) {
		_heaplimit -= blocks;
		__morecore(-blocks * BLOCKSIZE);
		_heapinfo[_heapinfo[block].free.prev].free.next
		    = _heapinfo[block].free.next;
		_heapinfo[_heapinfo[block].free.next].free.prev
		    = _heapinfo[block].free.prev;
		block = _heapinfo[block].free.prev;
	    }

	    /* Set the next search to begin at this block. */
	    _heapindex = block;
	    break;

	default:
	    /* Get the address of the first free fragment in this block. */
	    prev = (struct list *) ((char *) ADDRESS(block)
		    + (_heapinfo[block].busy.info.frag.first
			<< type));

	    if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1
		    && _fragblocks[type] > 1) {
		/* If all fragments of this block are free, remove them
		   from the fragment list and free the whole block. */
		--_fragblocks[type];
		for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i)
		    next = next->next;
		prev->prev->next = next;
		if (next)
		    next->prev = prev->prev;
		_heapinfo[block].busy.type = 0;
		_heapinfo[block].busy.info.size = 1;
		__free_unlocked(ADDRESS(block));
	    } else if (_heapinfo[block].busy.info.frag.nfree) {
		/* If some fragments of this block are free, link this fragment
		   into the fragment list after the first free fragment of
		   this block. */
		next = ptr;
		next->next = prev->next;
		next->prev = prev;
		prev->next = next;
		if (next->next)
		    next->next->prev = next;
		++_heapinfo[block].busy.info.frag.nfree;
	    } else {
		/* No fragments of this block are free, so link this fragment
		   into the fragment list and announce that it is the first
		   free fragment of this block. */
		prev = (struct list *) ptr;
		_heapinfo[block].busy.info.frag.nfree = 1;
		_heapinfo[block].busy.info.frag.first
		    = (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE
		    >> type;
		prev->next = _fraghead[type].next;
		prev->prev = &_fraghead[type];
		prev->prev->next = prev;
		if (prev->next)
		    prev->next->prev = prev;
	    }
	    break;
    }
}