WebSVN – HelenOS – Diff – /trunk/uspace/lib/libc/generic/malloc.c


/*
 * Copyright (c) 2009 Martin Decky
 * Copyright (c) 2009 Petr Tuma
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup libc
 * @{
 */
/** @file
 */
 
#include <malloc.h>
#include <bool.h>
#include <as.h>
#include <align.h>
#include <macros.h>
#include <assert.h>
#include <errno.h>
#include <bitops.h>
#include <mem.h>
#include <adt/gcdlcm.h>
 
/* Magic used in heap headers. */
#define HEAP_BLOCK_HEAD_MAGIC  0xBEEF0101
 
/* Magic used in heap footers. */
#define HEAP_BLOCK_FOOT_MAGIC  0xBEEF0202
 
/** Allocation alignment (this also covers the alignment of fields
    in the heap header and footer) */
#define BASE_ALIGN  16
 
/**
 * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures
 */
#define MAX_HEAP_SIZE  (sizeof(uintptr_t) << 28)
 
/**
 *
 */
#define STRUCT_OVERHEAD  (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
 
/**
 * Calculate real size of a heap block (with header and footer)
 */
#define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)
 
/**
 * Calculate net size of a heap block (without header and footer)
 */
#define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)
 
 
/** Header of a heap block
 *
 */
typedef struct {
    /* Size of the block (including header and footer) */
    size_t size;
   
    /* Indication of a free block */
    bool free;
   
    /* A magic value to detect overwrite of heap header */
    uint32_t magic;
} heap_block_head_t;
 
/** Footer of a heap block
 *
 */
typedef struct {
    /* Size of the block (including header and footer) */
    size_t size;
   
    /* A magic value to detect overwrite of heap footer */
    uint32_t magic;
} heap_block_foot_t;
 
/** Linker heap symbol */
extern char _heap;
 
/** Address of heap start */
static void *heap_start = 0;
 
/** Address of heap end */
static void *heap_end = 0;
 
/** Maximum heap size */
static size_t max_heap_size = (size_t) -1;
 
/** Current number of pages of heap area */
static size_t heap_pages = 0;
 
/** Initialize a heap block
 *
 * Fills in the structures related to a heap block.
 *
 * @param addr Address of the block.
 * @param size Size of the block including the header and the footer.
 * @param free Indication of a free block.
 *
 */
static void block_init(void *addr, size_t size, bool free)
{
    /* Calculate the position of the header and the footer */
    heap_block_head_t *head = (heap_block_head_t *) addr;
    heap_block_foot_t *foot =
        (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t));
   
    head->size = size;
    head->free = free;
    head->magic = HEAP_BLOCK_HEAD_MAGIC;
   
    foot->size = size;
    foot->magic = HEAP_BLOCK_FOOT_MAGIC;
}
 
/** Check a heap block
 *
 * Verifies that the structures related to a heap block still contain
 * the magic constants. This helps detect heap corruption early on.
 *
 * @param addr Address of the block.
 *
 */
static void block_check(void *addr)
{
    heap_block_head_t *head = (heap_block_head_t *) addr;
   
    assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
   
    heap_block_foot_t *foot =
        (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t));
   
    assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
    assert(head->size == foot->size);
}
 
static bool grow_heap(size_t size)
{
    if (size == 0)
        return false;
   
    size_t heap_size = (size_t) (heap_end - heap_start);
   
    if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size))
        return false;
   
    size_t pages = (size - 1) / PAGE_SIZE + 1;
   
    if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0)
        == EOK) {
        void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) +
            (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN);
        block_init(heap_end, end - heap_end, true);
        heap_pages += pages;
        heap_end = end;
        return true;
    }
   
    return false;
}
 
static void shrink_heap(void)
{
    // TODO
}
 
/** Initialize the heap allocator
 *
 * Finds how much physical memory we have and creates
 * the heap management structures that mark the whole
 * physical memory as a single free block.
 *
 */
void __heap_init(void)
{
    if (as_area_create((void *) &_heap, PAGE_SIZE,
        AS_AREA_WRITE | AS_AREA_READ)) {
        heap_pages = 1;
        heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN);
        heap_end =
            (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN);
       
        /* Make the entire area one large block. */
        block_init(heap_start, heap_end - heap_start, true);
    }
}
 
uintptr_t get_max_heap_addr(void)
{
    if (max_heap_size == (size_t) -1)
        max_heap_size =
            max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE);
   
    return ((uintptr_t) heap_start + max_heap_size);
}
 
static void split_mark(heap_block_head_t *cur, const size_t size)
{
    assert(cur->size >= size);
   
    /* See if we should split the block. */
    size_t split_limit = GROSS_SIZE(size);
   
    if (cur->size > split_limit) {
        /* Block big enough -> split. */
        void *next = ((void *) cur) + size;
        block_init(next, cur->size - size, true);
        block_init(cur, size, false);
    } else {
        /* Block too small -> use as is. */
        cur->free = false;
    }
}
 
/** Allocate a memory block
 *
 * @param size  The size of the block to allocate.
 * @param align Memory address alignment.
 *
 * @return the address of the block or NULL when not enough memory.
 *
 */
static void *malloc_internal(const size_t size, const size_t align)
{
    if (align == 0)
        return NULL;
   
    size_t falign = lcm(align, BASE_ALIGN);
    size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
   
    bool grown = false;
    void *result;
   
loop:
    result = NULL;
    heap_block_head_t *cur = (heap_block_head_t *) heap_start;
   
    while ((result == NULL) && ((void *) cur < heap_end)) {
        block_check(cur);
       
        /* Try to find a block that is free and large enough. */
        if ((cur->free) && (cur->size >= real_size)) {
            /* We have found a suitable block.
               Check for alignment properties. */
            void *addr = ((void *) cur) + sizeof(heap_block_head_t);
            void *aligned = (void *) ALIGN_UP(addr, falign);
           
            if (addr == aligned) {
                /* Exact block start including alignment. */
                split_mark(cur, real_size);
                result = addr;
            } else {
                /* Block start has to be aligned */
 
                size_t excess = (size_t) (aligned - addr);
               
                if (cur->size >= real_size + excess) {
                    /* The current block is large enought to fit
                       data in including alignment */
                    if ((void *) cur > heap_start) {
                        /* There is a block before the current block.
                           This previous block can be enlarged to compensate
 
                           for the alignment excess */
                        heap_block_foot_t *prev_foot =
                            ((void *) cur) - sizeof(heap_block_foot_t);
                       
                        heap_block_head_t *prev_head =
                            (heap_block_head_t *) (((void *) cur) - prev_foot->size);
                       
                        block_check(prev_head);
                       
                        size_t reduced_size = cur->size - excess;
                        heap_block_head_t *next_head = ((void *) cur) + excess;
                       
                        if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
                            /* The previous block is not free and there is enought
                               space to fill in a new free block between the previous
                               and current block */
                            block_init(cur, excess, true);
                        } else {
                            /* The previous block is free (thus there is no need to
                               induce additional fragmentation to the heap) or the
                               excess is small, thus just enlarge the previous block */
                            block_init(prev_head, prev_head->size + excess, prev_head->free);
                        }
                       
                        block_init(next_head, reduced_size, true);
                        split_mark(next_head, real_size);
                        result = aligned;
                        cur = next_head;
                    } else {
                        /* The current block is the first block on the heap.
                           We have to make sure that the alignment excess
                           is large enought to fit a new free block just
                           before the current block */
                        while (excess < STRUCT_OVERHEAD) {
                            aligned += falign;
                            excess += falign;
                        }
                       
                        /* Check for current block size again */
                        if (cur->size >= real_size + excess) {
                            size_t reduced_size = cur->size - excess;
                            cur = (heap_block_head_t *) (heap_start + excess);
                           
                            block_init(heap_start, excess, true);
                            block_init(cur, reduced_size, true);
                            split_mark(cur, real_size);
                            result = aligned;
                        }
                    }
                }
            }
        }
       
        /* Advance to the next block. */
        cur = (heap_block_head_t *) (((void *) cur) + cur->size);
    }
   
    if ((result == NULL) && (!grown)) {
        if (grow_heap(real_size)) {
            grown = true;
            goto loop;
        }
    }
   
    return result;
}
 
void *malloc(const size_t size)
{
    return malloc_internal(size, BASE_ALIGN);
}
 
void *memalign(const size_t align, const size_t size)
{
    if (align == 0)
        return NULL;
   
    size_t palign =
        1 << (fnzb(max(sizeof(void *), align) - 1) + 1);
   
    return malloc_internal(size, palign);
}
 
void *realloc(const void *addr, const size_t size)
{
    if (addr == NULL)
        return malloc(size);
   
    /* Calculate the position of the header. */
    heap_block_head_t *head =
        (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
   
    assert((void *) head >= heap_start);
    assert((void *) head < heap_end);
   
    block_check(head);
    assert(!head->free);
   
    void *ptr = NULL;
    size_t real_size = GROSS_SIZE(size);
    size_t orig_size = head->size;
   
    if (orig_size > real_size) {
        /* Shrink */
        if (orig_size - real_size >= STRUCT_OVERHEAD) {
            /* Split the original block to a full block
               and a tailing free block */
            block_init((void *) head, real_size, false);
            block_init((void *) head + real_size,
                orig_size - real_size, true);
            shrink_heap();
        }
       
        ptr = ((void *) head) + sizeof(heap_block_head_t);
    } else {
        /* Look at the next block. If it is free and the size is
           sufficient then merge the two. */
        heap_block_head_t *next_head =
            (heap_block_head_t *) (((void *) head) + head->size);
       
        if (((void *) next_head < heap_end)
            && (head->size + next_head->size >= real_size)) {
            block_check(next_head);
            block_init(head, head->size + next_head->size, false);
            split_mark(head, size);
           
            ptr = ((void *) head) + sizeof(heap_block_head_t);
        } else {
            ptr = malloc(size);
            if (ptr != NULL) {
                memcpy(ptr, addr, NET_SIZE(orig_size));
                free(addr);
            }
        }
    }
   
    return ptr;
}
 
/** Free a memory block
 *
 * @param addr The address of the block.
 */
void free(const void *addr)
{
    /* Calculate the position of the header. */
    heap_block_head_t *head
        = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
   
    assert((void *) head >= heap_start);
    assert((void *) head < heap_end);
   
    block_check(head);
    assert(!head->free);
   
    /* Mark the block itself as free. */
    head->free = true;
   
    /* Look at the next block. If it is free, merge the two. */
    heap_block_head_t *next_head
        = (heap_block_head_t *) (((void *) head) + head->size);
   
    if ((void *) next_head < heap_end) {
        block_check(next_head);
        if (next_head->free)
            block_init(head, head->size + next_head->size, true);
    }
   
    /* Look at the previous block. If it is free, merge the two. */
    if ((void *) head > heap_start) {
        heap_block_foot_t *prev_foot =
            (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
       
        heap_block_head_t *prev_head =
            (heap_block_head_t *) (((void *) head) - prev_foot->size);
       
        block_check(prev_head);
       
        if (prev_head->free)
            block_init(prev_head, prev_head->size + head->size, true);
    }
   
    shrink_heap();
}
 
/** @}
 */
 

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

Subversion Repositories HelenOS

(root)/trunk/uspace/lib/libc/generic/malloc.c – Rev 4600 → 4606