mmalloc from last version to be included in gdb.
[ocaml-ancient.git] / mmalloc / mmalloc.c
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'd 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., 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, 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 <string.h>     /* Prototypes for memcpy, memmove, memset, etc */
26
27 #include "mmprivate.h"
28
29 /* Prototypes for local functions */
30
31 static int initialize PARAMS ((struct mdesc *));
32 static PTR morecore PARAMS ((struct mdesc *, size_t));
33 static PTR align PARAMS ((struct mdesc *, size_t));
34
35 /* Aligned allocation.  */
36
37 static PTR
38 align (mdp, size)
39   struct mdesc *mdp;
40   size_t size;
41 {
42   PTR result;
43   unsigned long int adj;
44
45   result = mdp -> morecore (mdp, size);
46   adj = RESIDUAL (result, BLOCKSIZE);
47   if (adj != 0)
48     {
49       adj = BLOCKSIZE - adj;
50       mdp -> morecore (mdp, adj);
51       result = (char *) result + adj;
52     }
53   return (result);
54 }
55
56 /* Set everything up and remember that we have.  */
57
58 static int
59 initialize (mdp)
60   struct mdesc *mdp;
61 {
62   mdp -> heapsize = HEAP / BLOCKSIZE;
63   mdp -> heapinfo = (malloc_info *) 
64     align (mdp, mdp -> heapsize * sizeof (malloc_info));
65   if (mdp -> heapinfo == NULL)
66     {
67       return (0);
68     }
69   memset ((PTR)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
70   mdp -> heapinfo[0].free.size = 0;
71   mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
72   mdp -> heapindex = 0;
73   mdp -> heapbase = (char *) mdp -> heapinfo;
74   mdp -> flags |= MMALLOC_INITIALIZED;
75   return (1);
76 }
77
78 /* Get neatly aligned memory, initializing or
79    growing the heap info table as necessary. */
80
81 static PTR
82 morecore (mdp, size)
83   struct mdesc *mdp;
84   size_t size;
85 {
86   PTR result;
87   malloc_info *newinfo, *oldinfo;
88   size_t newsize;
89
90   result = align (mdp, size);
91   if (result == NULL)
92     {
93       return (NULL);
94     }
95
96   /* Check if we need to grow the info table.  */
97   if ((size_t) BLOCK ((char *) result + size) > mdp -> heapsize)
98     {
99       newsize = mdp -> heapsize;
100       while ((size_t) BLOCK ((char *) result + size) > newsize)
101         {
102           newsize *= 2;
103         }
104       newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
105       if (newinfo == NULL)
106         {
107           mdp -> morecore (mdp, -size);
108           return (NULL);
109         }
110       memset ((PTR) newinfo, 0, newsize * sizeof (malloc_info));
111       memcpy ((PTR) newinfo, (PTR) mdp -> heapinfo,
112               mdp -> heapsize * sizeof (malloc_info));
113       oldinfo = mdp -> heapinfo;
114       newinfo[BLOCK (oldinfo)].busy.type = 0;
115       newinfo[BLOCK (oldinfo)].busy.info.size
116         = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
117       mdp -> heapinfo = newinfo;
118       __mmalloc_free (mdp, (PTR)oldinfo);
119       mdp -> heapsize = newsize;
120     }
121
122   mdp -> heaplimit = BLOCK ((char *) result + size);
123   return (result);
124 }
125
126 /* Allocate memory from the heap.  */
127
128 PTR
129 mmalloc (md, size)
130   PTR md;
131   size_t size;
132 {
133   struct mdesc *mdp;
134   PTR result;
135   size_t block, blocks, lastblocks, start;
136   register size_t i;
137   struct list *next;
138   register size_t log;
139
140   if (size == 0)
141     {
142       return (NULL);
143     }
144
145   mdp = MD_TO_MDP (md);
146       
147   if (mdp -> mmalloc_hook != NULL)
148     {
149       return ((*mdp -> mmalloc_hook) (md, size));
150     }
151
152   if (!(mdp -> flags & MMALLOC_INITIALIZED))
153     {
154       if (!initialize (mdp))
155         {
156           return (NULL);
157         }
158     }
159
160   if (size < sizeof (struct list))
161     {
162       size = sizeof (struct list);
163     }
164
165   /* Determine the allocation policy based on the request size.  */
166   if (size <= BLOCKSIZE / 2)
167     {
168       /* Small allocation to receive a fragment of a block.
169          Determine the logarithm to base two of the fragment size. */
170       log = 1;
171       --size;
172       while ((size /= 2) != 0)
173         {
174           ++log;
175         }
176
177       /* Look in the fragment lists for a
178          free fragment of the desired size. */
179       next = mdp -> fraghead[log].next;
180       if (next != NULL)
181         {
182           /* There are free fragments of this size.
183              Pop a fragment out of the fragment list and return it.
184              Update the block's nfree and first counters. */
185           result = (PTR) next;
186           next -> prev -> next = next -> next;
187           if (next -> next != NULL)
188             {
189               next -> next -> prev = next -> prev;
190             }
191           block = BLOCK (result);
192           if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
193             {
194               mdp -> heapinfo[block].busy.info.frag.first =
195                 RESIDUAL (next -> next, BLOCKSIZE) >> log;
196             }
197
198           /* Update the statistics.  */
199           mdp -> heapstats.chunks_used++;
200           mdp -> heapstats.bytes_used += 1 << log;
201           mdp -> heapstats.chunks_free--;
202           mdp -> heapstats.bytes_free -= 1 << log;
203         }
204       else
205         {
206           /* No free fragments of the desired size, so get a new block
207              and break it into fragments, returning the first.  */
208           result = mmalloc (md, BLOCKSIZE);
209           if (result == NULL)
210             {
211               return (NULL);
212             }
213
214           /* Link all fragments but the first into the free list.  */
215           for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
216             {
217               next = (struct list *) ((char *) result + (i << log));
218               next -> next = mdp -> fraghead[log].next;
219               next -> prev = &mdp -> fraghead[log];
220               next -> prev -> next = next;
221               if (next -> next != NULL)
222                 {
223                   next -> next -> prev = next;
224                 }
225             }
226
227           /* Initialize the nfree and first counters for this block.  */
228           block = BLOCK (result);
229           mdp -> heapinfo[block].busy.type = log;
230           mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
231           mdp -> heapinfo[block].busy.info.frag.first = i - 1;
232
233           mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
234           mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
235           mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
236         }
237     }
238   else
239     {
240       /* Large allocation to receive one or more blocks.
241          Search the free list in a circle starting at the last place visited.
242          If we loop completely around without finding a large enough
243          space we will have to get more memory from the system.  */
244       blocks = BLOCKIFY(size);
245       start = block = MALLOC_SEARCH_START;
246       while (mdp -> heapinfo[block].free.size < blocks)
247         {
248           block = mdp -> heapinfo[block].free.next;
249           if (block == start)
250             {
251               /* Need to get more from the system.  Check to see if
252                  the new core will be contiguous with the final free
253                  block; if so we don't need to get as much.  */
254               block = mdp -> heapinfo[0].free.prev;
255               lastblocks = mdp -> heapinfo[block].free.size;
256               if (mdp -> heaplimit != 0 &&
257                   block + lastblocks == mdp -> heaplimit &&
258                   mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
259                   (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
260                 {
261                   /* Which block we are extending (the `final free
262                      block' referred to above) might have changed, if
263                      it got combined with a freed info table.  */
264                   block = mdp -> heapinfo[0].free.prev;
265
266                   mdp -> heapinfo[block].free.size += (blocks - lastblocks);
267                   mdp -> heapstats.bytes_free +=
268                       (blocks - lastblocks) * BLOCKSIZE;
269                   continue;
270                 }
271               result = morecore(mdp, blocks * BLOCKSIZE);
272               if (result == NULL)
273                 {
274                   return (NULL);
275                 }
276               block = BLOCK (result);
277               mdp -> heapinfo[block].busy.type = 0;
278               mdp -> heapinfo[block].busy.info.size = blocks;
279               mdp -> heapstats.chunks_used++;
280               mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
281               return (result);
282             }
283         }
284
285       /* At this point we have found a suitable free list entry.
286          Figure out how to remove what we need from the list. */
287       result = ADDRESS(block);
288       if (mdp -> heapinfo[block].free.size > blocks)
289         {
290           /* The block we found has a bit left over,
291              so relink the tail end back into the free list. */
292           mdp -> heapinfo[block + blocks].free.size
293             = mdp -> heapinfo[block].free.size - blocks;
294           mdp -> heapinfo[block + blocks].free.next
295             = mdp -> heapinfo[block].free.next;
296           mdp -> heapinfo[block + blocks].free.prev
297             = mdp -> heapinfo[block].free.prev;
298           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
299             = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
300               = mdp -> heapindex = block + blocks;
301         }
302       else
303         {
304           /* The block exactly matches our requirements,
305              so just remove it from the list. */
306           mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
307             = mdp -> heapinfo[block].free.prev;
308           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
309             = mdp -> heapindex = mdp -> heapinfo[block].free.next;
310           mdp -> heapstats.chunks_free--;
311         }
312
313       mdp -> heapinfo[block].busy.type = 0;
314       mdp -> heapinfo[block].busy.info.size = blocks;
315       mdp -> heapstats.chunks_used++;
316       mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
317       mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
318     }
319
320   return (result);
321 }
322
323 /* When using this package, provide a version of malloc/realloc/free built
324    on top of it, so that if we use the default sbrk() region we will not
325    collide with another malloc package trying to do the same thing, if
326    the application contains any "hidden" calls to malloc/realloc/free (such
327    as inside a system library). */
328
329 PTR
330 malloc (size)
331   size_t size;
332 {
333   PTR result;
334
335   result = mmalloc ((PTR) NULL, size);
336   return (result);
337 }