First draft of a dynamic memory allocator
[gpxe.git] / src / core / malloc.c
1 /*
2  * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17  */
18
19 #include <stdint.h>
20 #include <string.h>
21 #include <io.h>
22 #include <gpxe/list.h>
23 #include <gpxe/malloc.h>
24
25 /** @file
26  *
27  * Memory allocation
28  *
29  */
30
31 /** A free block of memory */
32 struct free_block {
33         /** List of free blocks */
34         struct list_head list;
35         /** Size of this block */
36         size_t size;
37 };
38
39 /** List of free memory blocks */
40 static LIST_HEAD ( free_blocks );
41
42 /**
43  * Round size up to a memory allocation block size
44  *
45  * @v requested         Requested size
46  * @ret obtained        Obtained size
47  *
48  * The requested size is rounded up to the minimum allocation block
49  * size (the size of a struct @c free_block) and then rounded up to
50  * the nearest power of two.
51  */
52 static size_t block_size ( size_t requested ) {
53         size_t obtained = 1;
54
55         while ( ( obtained < sizeof ( struct free_block ) ) ||
56                 ( obtained < requested ) ) {
57                 obtained <<= 1;
58         }
59         return obtained;
60 }
61
62 /**
63  * Allocate memory
64  *
65  * @v size              Requested size
66  * @ret ptr             Allocated memory
67  *
68  * gmalloc() will always allocate memory in power-of-two sized blocks,
69  * aligned to the corresponding power-of-two boundary.  For example, a
70  * request for 1500 bytes will return a 2048-byte block aligned to a
71  * 2048-byte boundary.
72  *
73  * The alignment applies to the physical address, not the virtual
74  * address.  The pointer value returned by gmalloc() therefore has no
75  * alignment guarantees, except as provided for by the
76  * virtual-to-physical mapping.  (In a PXE environment, this mapping
77  * is guaranteed to be a multiple of 16 bytes.)
78  *
79  * Unlike traditional malloc(), the caller must remember the size of
80  * the allocated block and pass the size to gfree().  This is done in
81  * order to allow efficient allocation of power-of-two sized and
82  * aligned blocks.
83  */
84 void * gmalloc ( size_t size ) {
85         struct free_block *block;
86         struct free_block *buddy;
87
88         /* Round up block size to power of two */
89         size = block_size ( size );
90
91         /* Find the best available block */
92         list_for_each_entry ( block, &free_blocks, list ) {
93                 if ( block->size == size ) {
94                         list_del ( &block->list );
95                         memset ( block, 0, size );
96                         return block;
97                 }
98                 while ( block->size > size ) {
99                         block->size >>= 1;
100                         buddy = ( ( ( void * ) block ) + block->size );
101                         buddy->size = block->size;
102                         list_add ( &buddy->list, &block->list );
103                 }
104         }
105
106         /* Nothing available */
107         return NULL;
108 }
109
110 /**
111  * Free memory
112  *
113  * @v ptr               Allocated memory
114  * @v size              Originally requested size
115  *
116  * Frees memory originally allocated by gmalloc().
117  *
118  * Calling gfree() with a NULL @c ptr is explicitly allowed, and
119  * defined to have no effect.  Code such as
120  *
121  * @code
122  *
123  * if ( ! my_ptr )
124  *     gfree ( my_ptr, my_size )
125  *
126  * @endcode
127  *
128  * is perfectly valid, but should be avoided as unnecessary bloat.
129  */
130 void gfree ( void *ptr, size_t size ) {
131         struct free_block *freed_block = ptr;
132         struct free_block *block;
133         
134         /* Cope with gfree(NULL,x) */
135         if ( ! ptr )
136                 return;
137
138         /* Round up block size to power of two */
139         size = block_size ( size );
140         freed_block->size = size;
141
142         /* Merge back into free list */
143         list_for_each_entry ( block, &free_blocks, list ) {
144                 if ( ( ( virt_to_phys ( block ) ^
145                          virt_to_phys ( freed_block ) ) == size ) &&
146                      ( block->size == size ) ) {
147                         list_del ( &block->list );
148                         size <<= 1;
149                         if ( block < freed_block )
150                                 freed_block = block;
151                         freed_block->size = size;
152                 } else if ( block->size > size ) {
153                         break;
154                 }
155         }
156         list_add_tail ( &freed_block->list, &block->list );
157 }
158
159 /**
160  * Add memory to allocation pool
161  *
162  * @v start             Start address
163  * @v len               Length
164  *
165  * Adds a block of memory to the allocation pool.  This is a one-way
166  * operation; there is no way to reclaim this memory.
167  *
168  * There are no alignment requirements on either start or len.
169  */
170 void gmpopulate ( void *start, size_t len ) {
171         size_t frag_len;
172
173         /* Split region into power-of-two sized and aligned blocks,
174          * and feed them to gfree().
175          */
176         while ( len ) {
177                 frag_len = 1;
178                 /* Find maximum allowed alignment for this address */
179                 while ( ( virt_to_phys ( start ) & frag_len ) == 0 ) { 
180                         frag_len <<= 1;
181                 }
182                 /* Find maximum block size that fits in remaining space */
183                 while ( frag_len > len ) {
184                         frag_len >>= 1;
185                 }
186                 /* Skip blocks that are too small */
187                 if ( frag_len >= sizeof ( struct free_block ) )
188                         gfree ( start, frag_len );
189                 start += frag_len;
190                 len -= frag_len;
191         }
192 }
193
194 #if 0
195 #include <vsprintf.h>
196 /**
197  * Dump free block list
198  *
199  */
200 void gdumpfree ( void ) {
201         struct free_block *block;
202
203         printf ( "Free block list:\n" );
204         list_for_each_entry ( block, &free_blocks, list ) {
205                 printf ( "[%p,%p] (size %zx)\n", block,
206                          ( ( ( void * ) block ) + block->size ), block->size );
207         }
208 }
209 #endif