Subversion Repositories HelenOS

Rev

Rev 4643 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
4600 decky 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 {
4606 decky 279
                /* Block start has to be aligned */
4600 decky 280
                size_t excess = (size_t) (aligned - addr);
281
 
282
                if (cur->size >= real_size + excess) {
4607 jermar 283
                    /* The current block is large enough to fit
4606 decky 284
                       data in including alignment */
4600 decky 285
                    if ((void *) cur > heap_start) {
4606 decky 286
                        /* There is a block before the current block.
287
                           This previous block can be enlarged to compensate
288
                           for the alignment excess */
4600 decky 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;
4606 decky 298
                        heap_block_head_t *next_head = ((void *) cur) + excess;
4600 decky 299
 
4606 decky 300
                        if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
4607 jermar 301
                            /* The previous block is not free and there is enough
4606 decky 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);
4600 decky 314
                        result = aligned;
4606 decky 315
                        cur = next_head;
4600 decky 316
                    } else {
4606 decky 317
                        /* The current block is the first block on the heap.
318
                           We have to make sure that the alignment excess
4607 jermar 319
                           is large enough to fit a new free block just
4606 decky 320
                           before the current block */
4600 decky 321
                        while (excess < STRUCT_OVERHEAD) {
322
                            aligned += falign;
323
                            excess += falign;
324
                        }
325
 
4606 decky 326
                        /* Check for current block size again */
4600 decky 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;
4642 svoboda 387
    size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN));
4600 decky 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
 
4643 jermar 408
        if (((void *) next_head < heap_end) &&
409
            (head->size + next_head->size >= real_size) &&
410
            (next_head->free)) {
4600 decky 411
            block_check(next_head);
412
            block_init(head, head->size + next_head->size, false);
4642 svoboda 413
            split_mark(head, ALIGN_UP(size, BASE_ALIGN));
4600 decky 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
 */