| 1 | /* Memory allocator `malloc'. |
| 2 | Copyright 1990, 1991, 1992 Free Software Foundation |
| 3 | |
| 4 | Written May 1989 by Mike Haertel. |
| 5 | Heavily modified Mar 1992 by Fred Fish for mmap'c version. |
| 6 | |
| 7 | The GNU C Library is free software; you can redistribute it and/or |
| 8 | modify it under the terms of the GNU Library General Public License as |
| 9 | published by the Free Software Foundation; either version 2 of the |
| 10 | License, or (at your option) any later version. |
| 11 | |
| 12 | The GNU C Library is distributed in the hope that it will be useful, |
| 13 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 15 | Library General Public License for more details. |
| 16 | |
| 17 | You should have received a copy of the GNU Library General Public |
| 18 | License along with the GNU C Library; see the file COPYING.LIB. If |
| 19 | not, write to the Free Software Foundation, Inc., 675 Mass Ave, |
| 20 | Cambridge, MA 02139, USA. |
| 21 | |
| 22 | The author may be reached (Email) at the address mike@ai.mit.edu, |
| 23 | or (US mail) as Mike Haertel c/o Free Software Foundation. */ |
| 24 | |
| 25 | #include "mmalloc.h" |
| 26 | |
| 27 | /* Prototypes for local functions */ |
| 28 | |
| 29 | static int initialize PARAMS ((struct mdesc *)); |
| 30 | static PTR morecore PARAMS ((struct mdesc *, size_t)); |
| 31 | static PTR align PARAMS ((struct mdesc *, size_t)); |
| 32 | |
| 33 | /* Aligned allocation. */ |
| 34 | |
| 35 | static PTR |
| 36 | align (mdp, size) |
| 37 | struct mdesc *mdp; |
| 38 | size_t size; |
| 39 | { |
| 40 | PTR result; |
| 41 | unsigned long int adj; |
| 42 | |
| 43 | result = mdp -> morecore (mdp, size); |
| 44 | adj = RESIDUAL (result, BLOCKSIZE); |
| 45 | if (adj != 0) |
| 46 | { |
| 47 | adj = BLOCKSIZE - adj; |
| 48 | (void) mdp -> morecore (mdp, adj); |
| 49 | result = (char *) result + adj; |
| 50 | } |
| 51 | return (result); |
| 52 | } |
| 53 | |
| 54 | /* Set everything up and remember that we have. */ |
| 55 | |
| 56 | static int |
| 57 | initialize (mdp) |
| 58 | struct mdesc *mdp; |
| 59 | { |
| 60 | mdp -> heapsize = HEAP / BLOCKSIZE; |
| 61 | mdp -> heapinfo = (malloc_info *) |
| 62 | align (mdp, mdp -> heapsize * sizeof (malloc_info)); |
| 63 | if (mdp -> heapinfo == NULL) |
| 64 | { |
| 65 | return (0); |
| 66 | } |
| 67 | memset ((PTR)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info)); |
| 68 | mdp -> heapinfo[0].free.size = 0; |
| 69 | mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0; |
| 70 | mdp -> heapindex = 0; |
| 71 | mdp -> heapbase = (char *) mdp -> heapinfo; |
| 72 | mdp -> flags |= MMALLOC_INITIALIZED; |
| 73 | return (1); |
| 74 | } |
| 75 | |
| 76 | /* Get neatly aligned memory, initializing or |
| 77 | growing the heap info table as necessary. */ |
| 78 | |
| 79 | static PTR |
| 80 | morecore (mdp, size) |
| 81 | struct mdesc *mdp; |
| 82 | size_t size; |
| 83 | { |
| 84 | PTR result; |
| 85 | malloc_info *newinfo, *oldinfo; |
| 86 | size_t newsize; |
| 87 | |
| 88 | result = align (mdp, size); |
| 89 | if (result == NULL) |
| 90 | { |
| 91 | return (NULL); |
| 92 | } |
| 93 | |
| 94 | /* Check if we need to grow the info table. */ |
| 95 | if ((size_t) BLOCK ((char *) result + size) > mdp -> heapsize) |
| 96 | { |
| 97 | newsize = mdp -> heapsize; |
| 98 | while ((size_t) BLOCK ((char *) result + size) > newsize) |
| 99 | { |
| 100 | newsize *= 2; |
| 101 | } |
| 102 | newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info)); |
| 103 | if (newinfo == NULL) |
| 104 | { |
| 105 | mdp -> morecore (mdp, -size); |
| 106 | return (NULL); |
| 107 | } |
| 108 | memset ((PTR)newinfo, 0, newsize * sizeof (malloc_info)); |
| 109 | memcpy ((PTR)newinfo, (PTR)mdp -> heapinfo, |
| 110 | mdp -> heapsize * sizeof (malloc_info)); |
| 111 | oldinfo = mdp -> heapinfo; |
| 112 | newinfo[BLOCK (oldinfo)].busy.type = 0; |
| 113 | newinfo[BLOCK (oldinfo)].busy.info.size |
| 114 | = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info)); |
| 115 | mdp -> heapinfo = newinfo; |
| 116 | __mmalloc_free (mdp, (PTR)oldinfo); |
| 117 | mdp -> heapsize = newsize; |
| 118 | } |
| 119 | |
| 120 | mdp -> heaplimit = BLOCK ((char *) result + size); |
| 121 | return (result); |
| 122 | } |
| 123 | |
| 124 | /* Allocate memory from the heap. */ |
| 125 | |
| 126 | PTR |
| 127 | mmalloc (md, size) |
| 128 | PTR md; |
| 129 | size_t size; |
| 130 | { |
| 131 | struct mdesc *mdp; |
| 132 | PTR result; |
| 133 | size_t block, blocks, lastblocks, start; |
| 134 | register size_t i; |
| 135 | struct list *next; |
| 136 | register size_t log; |
| 137 | |
| 138 | if (size == 0) |
| 139 | { |
| 140 | return (NULL); |
| 141 | } |
| 142 | |
| 143 | mdp = MD_TO_MDP (md); |
| 144 | |
| 145 | if (mdp -> mmalloc_hook != NULL) |
| 146 | { |
| 147 | return ((*mdp -> mmalloc_hook) (md, size)); |
| 148 | } |
| 149 | |
| 150 | if (!(mdp -> flags & MMALLOC_INITIALIZED)) |
| 151 | { |
| 152 | if (!initialize (mdp)) |
| 153 | { |
| 154 | return (NULL); |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | if (size < sizeof (struct list)) |
| 159 | { |
| 160 | size = sizeof (struct list); |
| 161 | } |
| 162 | |
| 163 | /* Determine the allocation policy based on the request size. */ |
| 164 | if (size <= BLOCKSIZE / 2) |
| 165 | { |
| 166 | /* Small allocation to receive a fragment of a block. |
| 167 | Determine the logarithm to base two of the fragment size. */ |
| 168 | log = 1; |
| 169 | --size; |
| 170 | while ((size /= 2) != 0) |
| 171 | { |
| 172 | ++log; |
| 173 | } |
| 174 | |
| 175 | /* Look in the fragment lists for a |
| 176 | free fragment of the desired size. */ |
| 177 | next = mdp -> fraghead[log].next; |
| 178 | if (next != NULL) |
| 179 | { |
| 180 | /* There are free fragments of this size. |
| 181 | Pop a fragment out of the fragment list and return it. |
| 182 | Update the block's nfree and first counters. */ |
| 183 | result = (PTR) next; |
| 184 | next -> prev -> next = next -> next; |
| 185 | if (next -> next != NULL) |
| 186 | { |
| 187 | next -> next -> prev = next -> prev; |
| 188 | } |
| 189 | block = BLOCK (result); |
| 190 | if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0) |
| 191 | { |
| 192 | mdp -> heapinfo[block].busy.info.frag.first = |
| 193 | RESIDUAL (next -> next, BLOCKSIZE) >> log; |
| 194 | } |
| 195 | |
| 196 | /* Update the statistics. */ |
| 197 | mdp -> heapstats.chunks_used++; |
| 198 | mdp -> heapstats.bytes_used += 1 << log; |
| 199 | mdp -> heapstats.chunks_free--; |
| 200 | mdp -> heapstats.bytes_free -= 1 << log; |
| 201 | } |
| 202 | else |
| 203 | { |
| 204 | /* No free fragments of the desired size, so get a new block |
| 205 | and break it into fragments, returning the first. */ |
| 206 | result = mmalloc (md, BLOCKSIZE); |
| 207 | if (result == NULL) |
| 208 | { |
| 209 | return (NULL); |
| 210 | } |
| 211 | |
| 212 | /* Link all fragments but the first into the free list. */ |
| 213 | for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i) |
| 214 | { |
| 215 | next = (struct list *) ((char *) result + (i << log)); |
| 216 | next -> next = mdp -> fraghead[log].next; |
| 217 | next -> prev = &mdp -> fraghead[log]; |
| 218 | next -> prev -> next = next; |
| 219 | if (next -> next != NULL) |
| 220 | { |
| 221 | next -> next -> prev = next; |
| 222 | } |
| 223 | } |
| 224 | |
| 225 | /* Initialize the nfree and first counters for this block. */ |
| 226 | block = BLOCK (result); |
| 227 | mdp -> heapinfo[block].busy.type = log; |
| 228 | mdp -> heapinfo[block].busy.info.frag.nfree = i - 1; |
| 229 | mdp -> heapinfo[block].busy.info.frag.first = i - 1; |
| 230 | |
| 231 | mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1; |
| 232 | mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log); |
| 233 | mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log); |
| 234 | } |
| 235 | } |
| 236 | else |
| 237 | { |
| 238 | /* Large allocation to receive one or more blocks. |
| 239 | Search the free list in a circle starting at the last place visited. |
| 240 | If we loop completely around without finding a large enough |
| 241 | space we will have to get more memory from the system. */ |
| 242 | blocks = BLOCKIFY(size); |
| 243 | start = block = MALLOC_SEARCH_START; |
| 244 | while (mdp -> heapinfo[block].free.size < blocks) |
| 245 | { |
| 246 | block = mdp -> heapinfo[block].free.next; |
| 247 | if (block == start) |
| 248 | { |
| 249 | /* Need to get more from the system. Check to see if |
| 250 | the new core will be contiguous with the final free |
| 251 | block; if so we don't need to get as much. */ |
| 252 | block = mdp -> heapinfo[0].free.prev; |
| 253 | lastblocks = mdp -> heapinfo[block].free.size; |
| 254 | if (mdp -> heaplimit != 0 && |
| 255 | block + lastblocks == mdp -> heaplimit && |
| 256 | mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) && |
| 257 | (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL) |
| 258 | { |
| 259 | mdp -> heapinfo[block].free.size = blocks; |
| 260 | mdp -> heapstats.bytes_free += |
| 261 | (blocks - lastblocks) * BLOCKSIZE; |
| 262 | continue; |
| 263 | } |
| 264 | result = morecore(mdp, blocks * BLOCKSIZE); |
| 265 | if (result == NULL) |
| 266 | { |
| 267 | return (NULL); |
| 268 | } |
| 269 | block = BLOCK (result); |
| 270 | mdp -> heapinfo[block].busy.type = 0; |
| 271 | mdp -> heapinfo[block].busy.info.size = blocks; |
| 272 | mdp -> heapstats.chunks_used++; |
| 273 | mdp -> heapstats.bytes_used += blocks * BLOCKSIZE; |
| 274 | return (result); |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | /* At this point we have found a suitable free list entry. |
| 279 | Figure out how to remove what we need from the list. */ |
| 280 | result = ADDRESS(block); |
| 281 | if (mdp -> heapinfo[block].free.size > blocks) |
| 282 | { |
| 283 | /* The block we found has a bit left over, |
| 284 | so relink the tail end back into the free list. */ |
| 285 | mdp -> heapinfo[block + blocks].free.size |
| 286 | = mdp -> heapinfo[block].free.size - blocks; |
| 287 | mdp -> heapinfo[block + blocks].free.next |
| 288 | = mdp -> heapinfo[block].free.next; |
| 289 | mdp -> heapinfo[block + blocks].free.prev |
| 290 | = mdp -> heapinfo[block].free.prev; |
| 291 | mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next |
| 292 | = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev |
| 293 | = mdp -> heapindex = block + blocks; |
| 294 | } |
| 295 | else |
| 296 | { |
| 297 | /* The block exactly matches our requirements, |
| 298 | so just remove it from the list. */ |
| 299 | mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev |
| 300 | = mdp -> heapinfo[block].free.prev; |
| 301 | mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next |
| 302 | = mdp -> heapindex = mdp -> heapinfo[block].free.next; |
| 303 | mdp -> heapstats.chunks_free--; |
| 304 | } |
| 305 | |
| 306 | mdp -> heapinfo[block].busy.type = 0; |
| 307 | mdp -> heapinfo[block].busy.info.size = blocks; |
| 308 | mdp -> heapstats.chunks_used++; |
| 309 | mdp -> heapstats.bytes_used += blocks * BLOCKSIZE; |
| 310 | mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE; |
| 311 | } |
| 312 | |
| 313 | return (result); |
| 314 | } |
| 315 | |
| 316 | /* When using this package, provide a version of malloc/realloc/free built |
| 317 | on top of it, so that if we use the default sbrk() region we will not |
| 318 | collide with another malloc package trying to do the same thing, if |
| 319 | the application contains any "hidden" calls to malloc/realloc/free (such |
| 320 | as inside a system library). */ |
| 321 | |
| 322 | PTR |
| 323 | malloc (size) |
| 324 | size_t size; |
| 325 | { |
| 326 | return (mmalloc ((void *) NULL, size)); |
| 327 | } |