← Back to branch summary

~galfy/helenos/bird-port-mainline

« back to all changes in this revision

Viewing changes to uspace/lib/libc/generic/malloc.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
uspace/lib/libc/generic/malloc.c
 
1
/*
 
2
 * Copyright (c) 2009 Martin Decky
 
3
 * Copyright (c) 2009 Petr Tuma
 
4
 * All rights reserved.
 
5
 *
 
6
 * Redistribution and use in source and binary forms, with or without
 
7
 * modification, are permitted provided that the following conditions
 
8
 * are met:
 
9
 *
 
10
 * - Redistributions of source code must retain the above copyright
 
11
 *   notice, this list of conditions and the following disclaimer.
 
12
 * - Redistributions in binary form must reproduce the above copyright
 
13
 *   notice, this list of conditions and the following disclaimer in the
 
14
 *   documentation and/or other materials provided with the distribution.
 
15
 * - The name of the author may not be used to endorse or promote products
 
16
 *   derived from this software without specific prior written permission.
 
17
 *
 
18
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 
19
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
20
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
21
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 
22
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
23
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
24
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
25
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
26
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
27
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
28
 */
 
29
 
 
30
/** @addtogroup libc
 
31
 * @{
 
32
 */
 
33
/** @file
 
34
 */
 
35
 
 
36
#include <malloc.h>
 
37
#include <bool.h>
 
38
#include <as.h>
 
39
#include <align.h>
 
40
#include <macros.h>
 
41
#include <assert.h>
 
42
#include <errno.h>
 
43
#include <bitops.h>
 
44
#include <mem.h>
 
45
#include <adt/gcdlcm.h>
 
46
 
 
47
/* Magic used in heap headers. */
 
48
#define HEAP_BLOCK_HEAD_MAGIC  0xBEEF0101
 
49
 
 
50
/* Magic used in heap footers. */
 
51
#define HEAP_BLOCK_FOOT_MAGIC  0xBEEF0202
 
52
 
 
53
/** Allocation alignment (this also covers the alignment of fields
 
54
    in the heap header and footer) */
 
55
#define BASE_ALIGN  16
 
56
 
 
57
/**
 
58
 * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures
 
59
 */
 
60
#define MAX_HEAP_SIZE  (sizeof(uintptr_t) << 28)
 
61
 
 
62
/**
 
63
 *
 
64
 */
 
65
#define STRUCT_OVERHEAD  (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
 
66
 
 
67
/**
 
68
 * Calculate real size of a heap block (with header and footer)
 
69
 */
 
70
#define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)
 
71
 
 
72
/**
 
73
 * Calculate net size of a heap block (without header and footer)
 
74
 */
 
75
#define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)
 
76
 
 
77
 
 
78
/** Header of a heap block
 
79
 *
 
80
 */
 
81
typedef struct {
 
82
        /* Size of the block (including header and footer) */
 
83
        size_t size;
 
84
        
 
85
        /* Indication of a free block */
 
86
        bool free;
 
87
        
 
88
        /* A magic value to detect overwrite of heap header */
 
89
        uint32_t magic;
 
90
} heap_block_head_t;
 
91
 
 
92
/** Footer of a heap block
 
93
 *
 
94
 */
 
95
typedef struct {
 
96
        /* Size of the block (including header and footer) */
 
97
        size_t size;
 
98
        
 
99
        /* A magic value to detect overwrite of heap footer */
 
100
        uint32_t magic;
 
101
} heap_block_foot_t;
 
102
 
 
103
/** Linker heap symbol */
 
104
extern char _heap;
 
105
 
 
106
/** Address of heap start */
 
107
static void *heap_start = 0;
 
108
 
 
109
/** Address of heap end */
 
110
static void *heap_end = 0;
 
111
 
 
112
/** Maximum heap size */
 
113
static size_t max_heap_size = (size_t) -1;
 
114
 
 
115
/** Current number of pages of heap area */
 
116
static size_t heap_pages = 0;
 
117
 
 
118
/** Initialize a heap block
 
119
 *
 
120
 * Fills in the structures related to a heap block.
 
121
 *
 
122
 * @param addr Address of the block.
 
123
 * @param size Size of the block including the header and the footer.
 
124
 * @param free Indication of a free block.
 
125
 *
 
126
 */
 
127
static void block_init(void *addr, size_t size, bool free)
 
128
{
 
129
        /* Calculate the position of the header and the footer */
 
130
        heap_block_head_t *head = (heap_block_head_t *) addr;
 
131
        heap_block_foot_t *foot =
 
132
            (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t));
 
133
        
 
134
        head->size = size;
 
135
        head->free = free;
 
136
        head->magic = HEAP_BLOCK_HEAD_MAGIC;
 
137
        
 
138
        foot->size = size;
 
139
        foot->magic = HEAP_BLOCK_FOOT_MAGIC;
 
140
}
 
141
 
 
142
/** Check a heap block
 
143
 *
 
144
 * Verifies that the structures related to a heap block still contain
 
145
 * the magic constants. This helps detect heap corruption early on.
 
146
 *
 
147
 * @param addr Address of the block.
 
148
 *
 
149
 */
 
150
static void block_check(void *addr)
 
151
{
 
152
        heap_block_head_t *head = (heap_block_head_t *) addr;
 
153
        
 
154
        assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
 
155
        
 
156
        heap_block_foot_t *foot =
 
157
            (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t));
 
158
        
 
159
        assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
 
160
        assert(head->size == foot->size);
 
161
}
 
162
 
 
163
static bool grow_heap(size_t size)
 
164
{
 
165
        if (size == 0)
 
166
                return false;
 
167
        
 
168
        size_t heap_size = (size_t) (heap_end - heap_start);
 
169
        
 
170
        if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size))
 
171
                return false;
 
172
        
 
173
        size_t pages = (size - 1) / PAGE_SIZE + 1;
 
174
        
 
175
        if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0)
 
176
            == EOK) {
 
177
                void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) +
 
178
                    (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN);
 
179
                block_init(heap_end, end - heap_end, true);
 
180
                heap_pages += pages;
 
181
                heap_end = end;
 
182
                return true;
 
183
        }
 
184
        
 
185
        return false;
 
186
}
 
187
 
 
188
static void shrink_heap(void)
 
189
{
 
190
        // TODO
 
191
}
 
192
 
 
193
/** Initialize the heap allocator
 
194
 *
 
195
 * Finds how much physical memory we have and creates
 
196
 * the heap management structures that mark the whole
 
197
 * physical memory as a single free block.
 
198
 *
 
199
 */
 
200
void __heap_init(void)
 
201
{
 
202
        if (as_area_create((void *) &_heap, PAGE_SIZE,
 
203
            AS_AREA_WRITE | AS_AREA_READ)) {
 
204
                heap_pages = 1;
 
205
                heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN);
 
206
                heap_end =
 
207
                    (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN);
 
208
                
 
209
                /* Make the entire area one large block. */
 
210
                block_init(heap_start, heap_end - heap_start, true);
 
211
        }
 
212
}
 
213
 
 
214
uintptr_t get_max_heap_addr(void)
 
215
{
 
216
        if (max_heap_size == (size_t) -1)
 
217
                max_heap_size =
 
218
                    max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE);
 
219
        
 
220
        return ((uintptr_t) heap_start + max_heap_size);
 
221
}
 
222
 
 
223
static void split_mark(heap_block_head_t *cur, const size_t size)
 
224
{
 
225
        assert(cur->size >= size);
 
226
        
 
227
        /* See if we should split the block. */
 
228
        size_t split_limit = GROSS_SIZE(size);
 
229
        
 
230
        if (cur->size > split_limit) {
 
231
                /* Block big enough -> split. */
 
232
                void *next = ((void *) cur) + size;
 
233
                block_init(next, cur->size - size, true);
 
234
                block_init(cur, size, false);
 
235
        } else {
 
236
                /* Block too small -> use as is. */
 
237
                cur->free = false;
 
238
        }
 
239
}
 
240
 
 
241
/** Allocate a memory block
 
242
 *
 
243
 * @param size  The size of the block to allocate.
 
244
 * @param align Memory address alignment.
 
245
 *
 
246
 * @return the address of the block or NULL when not enough memory.
 
247
 *
 
248
 */
 
249
static void *malloc_internal(const size_t size, const size_t align)
 
250
{
 
251
        if (align == 0)
 
252
                return NULL;
 
253
        
 
254
        size_t falign = lcm(align, BASE_ALIGN);
 
255
        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
 
256
        
 
257
        bool grown = false;
 
258
        void *result;
 
259
        
 
260
loop:
 
261
        result = NULL;
 
262
        heap_block_head_t *cur = (heap_block_head_t *) heap_start;
 
263
        
 
264
        while ((result == NULL) && ((void *) cur < heap_end)) {
 
265
                block_check(cur);
 
266
                
 
267
                /* Try to find a block that is free and large enough. */
 
268
                if ((cur->free) && (cur->size >= real_size)) {
 
269
                        /* We have found a suitable block.
 
270
                           Check for alignment properties. */
 
271
                        void *addr = ((void *) cur) + sizeof(heap_block_head_t);
 
272
                        void *aligned = (void *) ALIGN_UP(addr, falign);
 
273
                        
 
274
                        if (addr == aligned) {
 
275
                                /* Exact block start including alignment. */
 
276
                                split_mark(cur, real_size);
 
277
                                result = addr;
 
278
                        } else {
 
279
                                /* Block start has to be aligned */
 
280
                                size_t excess = (size_t) (aligned - addr);
 
281
                                
 
282
                                if (cur->size >= real_size + excess) {
 
283
                                        /* The current block is large enough to fit
 
284
                                           data in including alignment */
 
285
                                        if ((void *) cur > heap_start) {
 
286
                                                /* There is a block before the current block.
 
287
                                                   This previous block can be enlarged to compensate
 
288
                                                   for the alignment excess */
 
289
                                                heap_block_foot_t *prev_foot =
 
290
                                                    ((void *) cur) - sizeof(heap_block_foot_t);
 
291
                                                
 
292
                                                heap_block_head_t *prev_head =
 
293
                                                    (heap_block_head_t *) (((void *) cur) - prev_foot->size);
 
294
                                                
 
295
                                                block_check(prev_head);
 
296
                                                
 
297
                                                size_t reduced_size = cur->size - excess;
 
298
                                                heap_block_head_t *next_head = ((void *) cur) + excess;
 
299
                                                
 
300
                                                if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
 
301
                                                        /* The previous block is not free and there is enough
 
302
                                                           space to fill in a new free block between the previous
 
303
                                                           and current block */
 
304
                                                        block_init(cur, excess, true);
 
305
                                                } else {
 
306
                                                        /* The previous block is free (thus there is no need to
 
307
                                                           induce additional fragmentation to the heap) or the
 
308
                                                           excess is small, thus just enlarge the previous block */
 
309
                                                        block_init(prev_head, prev_head->size + excess, prev_head->free);
 
310
                                                }
 
311
                                                
 
312
                                                block_init(next_head, reduced_size, true);
 
313
                                                split_mark(next_head, real_size);
 
314
                                                result = aligned;
 
315
                                                cur = next_head;
 
316
                                        } else {
 
317
                                                /* The current block is the first block on the heap.
 
318
                                                   We have to make sure that the alignment excess
 
319
                                                   is large enough to fit a new free block just
 
320
                                                   before the current block */
 
321
                                                while (excess < STRUCT_OVERHEAD) {
 
322
                                                        aligned += falign;
 
323
                                                        excess += falign;
 
324
                                                }
 
325
                                                
 
326
                                                /* Check for current block size again */
 
327
                                                if (cur->size >= real_size + excess) {
 
328
                                                        size_t reduced_size = cur->size - excess;
 
329
                                                        cur = (heap_block_head_t *) (heap_start + excess);
 
330
                                                        
 
331
                                                        block_init(heap_start, excess, true);
 
332
                                                        block_init(cur, reduced_size, true);
 
333
                                                        split_mark(cur, real_size);
 
334
                                                        result = aligned;
 
335
                                                }
 
336
                                        }
 
337
                                }
 
338
                        }
 
339
                }
 
340
                
 
341
                /* Advance to the next block. */
 
342
                cur = (heap_block_head_t *) (((void *) cur) + cur->size);
 
343
        }
 
344
        
 
345
        if ((result == NULL) && (!grown)) {
 
346
                if (grow_heap(real_size)) {
 
347
                        grown = true;
 
348
                        goto loop;
 
349
                }
 
350
        }
 
351
        
 
352
        return result;
 
353
}
 
354
 
 
355
void *malloc(const size_t size)
 
356
{
 
357
        return malloc_internal(size, BASE_ALIGN);
 
358
}
 
359
 
 
360
void *memalign(const size_t align, const size_t size)
 
361
{
 
362
        if (align == 0)
 
363
                return NULL;
 
364
        
 
365
        size_t palign =
 
366
            1 << (fnzb(max(sizeof(void *), align) - 1) + 1);
 
367
        
 
368
        return malloc_internal(size, palign);
 
369
}
 
370
 
 
371
void *realloc(const void *addr, const size_t size)
 
372
{
 
373
        if (addr == NULL)
 
374
                return malloc(size);
 
375
        
 
376
        /* Calculate the position of the header. */
 
377
        heap_block_head_t *head =
 
378
            (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
 
379
        
 
380
        assert((void *) head >= heap_start);
 
381
        assert((void *) head < heap_end);
 
382
        
 
383
        block_check(head);
 
384
        assert(!head->free);
 
385
        
 
386
        void *ptr = NULL;
 
387
        size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN));
 
388
        size_t orig_size = head->size;
 
389
        
 
390
        if (orig_size > real_size) {
 
391
                /* Shrink */
 
392
                if (orig_size - real_size >= STRUCT_OVERHEAD) {
 
393
                        /* Split the original block to a full block
 
394
                           and a tailing free block */
 
395
                        block_init((void *) head, real_size, false);
 
396
                        block_init((void *) head + real_size,
 
397
                            orig_size - real_size, true);
 
398
                        shrink_heap();
 
399
                }
 
400
                
 
401
                ptr = ((void *) head) + sizeof(heap_block_head_t);
 
402
        } else {
 
403
                /* Look at the next block. If it is free and the size is
 
404
                   sufficient then merge the two. */
 
405
                heap_block_head_t *next_head =
 
406
                    (heap_block_head_t *) (((void *) head) + head->size);
 
407
                
 
408
                if (((void *) next_head < heap_end) &&
 
409
                    (head->size + next_head->size >= real_size) &&
 
410
                    (next_head->free)) {
 
411
                        block_check(next_head);
 
412
                        block_init(head, head->size + next_head->size, false);
 
413
                        split_mark(head, real_size);
 
414
                        
 
415
                        ptr = ((void *) head) + sizeof(heap_block_head_t);
 
416
                } else {
 
417
                        ptr = malloc(size);
 
418
                        if (ptr != NULL) {
 
419
                                memcpy(ptr, addr, NET_SIZE(orig_size));
 
420
                                free(addr);
 
421
                        }
 
422
                }
 
423
        }
 
424
        
 
425
        return ptr;
 
426
}
 
427
 
 
428
/** Free a memory block
 
429
 *
 
430
 * @param addr The address of the block.
 
431
 */
 
432
void free(const void *addr)
 
433
{
 
434
        /* Calculate the position of the header. */
 
435
        heap_block_head_t *head
 
436
            = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
 
437
        
 
438
        assert((void *) head >= heap_start);
 
439
        assert((void *) head < heap_end);
 
440
        
 
441
        block_check(head);
 
442
        assert(!head->free);
 
443
        
 
444
        /* Mark the block itself as free. */
 
445
        head->free = true;
 
446
        
 
447
        /* Look at the next block. If it is free, merge the two. */
 
448
        heap_block_head_t *next_head
 
449
            = (heap_block_head_t *) (((void *) head) + head->size);
 
450
        
 
451
        if ((void *) next_head < heap_end) {
 
452
                block_check(next_head);
 
453
                if (next_head->free)
 
454
                        block_init(head, head->size + next_head->size, true);
 
455
        }
 
456
        
 
457
        /* Look at the previous block. If it is free, merge the two. */
 
458
        if ((void *) head > heap_start) {
 
459
                heap_block_foot_t *prev_foot =
 
460
                    (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
 
461
                
 
462
                heap_block_head_t *prev_head =
 
463
                    (heap_block_head_t *) (((void *) head) - prev_foot->size);
 
464
                
 
465
                block_check(prev_head);
 
466
                
 
467
                if (prev_head->free)
 
468
                        block_init(prev_head, prev_head->size + head->size, true);
 
469
        }
 
470
        
 
471
        shrink_heap();
 
472
}
 
473
 
 
474
/** @}
 
475
 */