[binutils.git] / mmalloc / mmalloc.c

/* Memory allocator `malloc'.
   Copyright 1990, 1991, 1992 Free Software Foundation

   Written May 1989 by Mike Haertel.
   Heavily modified Mar 1992 by Fred Fish for mmap'd version.

The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with the GNU C Library; see the file COPYING.LIB.  If
not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.

   The author may be reached (Email) at the address [email protected],
   or (US mail) as Mike Haertel c/o Free Software Foundation. */

#include <string.h>	/* Prototypes for memcpy, memmove, memset, etc */

#include "mmprivate.h"

/* Prototypes for local functions */

static int initialize PARAMS ((struct mdesc *));
static PTR morecore PARAMS ((struct mdesc *, size_t));
static PTR align PARAMS ((struct mdesc *, size_t));

/* Aligned allocation.  */

static PTR
align (mdp, size)
  struct mdesc *mdp;
  size_t size;
{
  PTR result;
  unsigned long int adj;

  result = mdp -> morecore (mdp, size);
  adj = RESIDUAL (result, BLOCKSIZE);
  if (adj != 0)
    {
      adj = BLOCKSIZE - adj;
      mdp -> morecore (mdp, adj);
      result = (char *) result + adj;
    }
  return (result);
}

/* Set everything up and remember that we have.  */

static int
initialize (mdp)
  struct mdesc *mdp;
{
  mdp -> heapsize = HEAP / BLOCKSIZE;
  mdp -> heapinfo = (malloc_info *) 
    align (mdp, mdp -> heapsize * sizeof (malloc_info));
  if (mdp -> heapinfo == NULL)
    {
      return (0);
    }
  memset ((PTR)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
  mdp -> heapinfo[0].free.size = 0;
  mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
  mdp -> heapindex = 0;
  mdp -> heapbase = (char *) mdp -> heapinfo;
  mdp -> flags |= MMALLOC_INITIALIZED;
  return (1);
}

/* Get neatly aligned memory, initializing or
   growing the heap info table as necessary. */

static PTR
morecore (mdp, size)
  struct mdesc *mdp;
  size_t size;
{
  PTR result;
  malloc_info *newinfo, *oldinfo;
  size_t newsize;

  result = align (mdp, size);
  if (result == NULL)
    {
      return (NULL);
    }

  /* Check if we need to grow the info table.  */
  if ((size_t) BLOCK ((char *) result + size) > mdp -> heapsize)
    {
      newsize = mdp -> heapsize;
      while ((size_t) BLOCK ((char *) result + size) > newsize)
	{
	  newsize *= 2;
	}
      newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
      if (newinfo == NULL)
	{
	  mdp -> morecore (mdp, -size);
	  return (NULL);
	}
      memset ((PTR) newinfo, 0, newsize * sizeof (malloc_info));
      memcpy ((PTR) newinfo, (PTR) mdp -> heapinfo,
	      mdp -> heapsize * sizeof (malloc_info));
      oldinfo = mdp -> heapinfo;
      newinfo[BLOCK (oldinfo)].busy.type = 0;
      newinfo[BLOCK (oldinfo)].busy.info.size
	= BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
      mdp -> heapinfo = newinfo;
      __mmalloc_free (mdp, (PTR)oldinfo);
      mdp -> heapsize = newsize;
    }

  mdp -> heaplimit = BLOCK ((char *) result + size);
  return (result);
}

/* Allocate memory from the heap.  */

PTR
mmalloc (md, size)
  PTR md;
  size_t size;
{
  struct mdesc *mdp;
  PTR result;
  size_t block, blocks, lastblocks, start;
  register size_t i;
  struct list *next;
  register size_t log;

  if (size == 0)
    {
      return (NULL);
    }

  mdp = MD_TO_MDP (md);
      
  if (mdp -> mmalloc_hook != NULL)
    {
      return ((*mdp -> mmalloc_hook) (md, size));
    }

  if (!(mdp -> flags & MMALLOC_INITIALIZED))
    {
      if (!initialize (mdp))
	{
	  return (NULL);
	}
    }

  if (size < sizeof (struct list))
    {
      size = sizeof (struct list);
    }

  /* Determine the allocation policy based on the request size.  */
  if (size <= BLOCKSIZE / 2)
    {
      /* Small allocation to receive a fragment of a block.
	 Determine the logarithm to base two of the fragment size. */
      log = 1;
      --size;
      while ((size /= 2) != 0)
	{
	  ++log;
	}

      /* Look in the fragment lists for a
	 free fragment of the desired size. */
      next = mdp -> fraghead[log].next;
      if (next != NULL)
	{
	  /* There are free fragments of this size.
	     Pop a fragment out of the fragment list and return it.
	     Update the block's nfree and first counters. */
	  result = (PTR) next;
	  next -> prev -> next = next -> next;
	  if (next -> next != NULL)
	    {
	      next -> next -> prev = next -> prev;
	    }
	  block = BLOCK (result);
	  if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
	    {
	      mdp -> heapinfo[block].busy.info.frag.first =
		RESIDUAL (next -> next, BLOCKSIZE) >> log;
	    }

	  /* Update the statistics.  */
	  mdp -> heapstats.chunks_used++;
	  mdp -> heapstats.bytes_used += 1 << log;
	  mdp -> heapstats.chunks_free--;
	  mdp -> heapstats.bytes_free -= 1 << log;
	}
      else
	{
	  /* No free fragments of the desired size, so get a new block
	     and break it into fragments, returning the first.  */
	  result = mmalloc (md, BLOCKSIZE);
	  if (result == NULL)
	    {
	      return (NULL);
	    }

	  /* Link all fragments but the first into the free list.  */
	  for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
	    {
	      next = (struct list *) ((char *) result + (i << log));
	      next -> next = mdp -> fraghead[log].next;
	      next -> prev = &mdp -> fraghead[log];
	      next -> prev -> next = next;
	      if (next -> next != NULL)
		{
		  next -> next -> prev = next;
		}
	    }

	  /* Initialize the nfree and first counters for this block.  */
	  block = BLOCK (result);
	  mdp -> heapinfo[block].busy.type = log;
	  mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
	  mdp -> heapinfo[block].busy.info.frag.first = i - 1;

	  mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
	  mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
 	  mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
	}
    }
  else
    {
      /* Large allocation to receive one or more blocks.
	 Search the free list in a circle starting at the last place visited.
	 If we loop completely around without finding a large enough
	 space we will have to get more memory from the system.  */
      blocks = BLOCKIFY(size);
      start = block = MALLOC_SEARCH_START;
      while (mdp -> heapinfo[block].free.size < blocks)
	{
	  block = mdp -> heapinfo[block].free.next;
	  if (block == start)
	    {
	      /* Need to get more from the system.  Check to see if
		 the new core will be contiguous with the final free
		 block; if so we don't need to get as much.  */
	      block = mdp -> heapinfo[0].free.prev;
	      lastblocks = mdp -> heapinfo[block].free.size;
	      if (mdp -> heaplimit != 0 &&
		  block + lastblocks == mdp -> heaplimit &&
		  mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
		  (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
		{
		  /* Which block we are extending (the `final free
		     block' referred to above) might have changed, if
		     it got combined with a freed info table.  */
		  block = mdp -> heapinfo[0].free.prev;

		  mdp -> heapinfo[block].free.size += (blocks - lastblocks);
		  mdp -> heapstats.bytes_free +=
		      (blocks - lastblocks) * BLOCKSIZE;
		  continue;
		}
	      result = morecore(mdp, blocks * BLOCKSIZE);
	      if (result == NULL)
		{
		  return (NULL);
		}
	      block = BLOCK (result);
	      mdp -> heapinfo[block].busy.type = 0;
	      mdp -> heapinfo[block].busy.info.size = blocks;
	      mdp -> heapstats.chunks_used++;
	      mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
	      return (result);
	    }
	}

      /* At this point we have found a suitable free list entry.
	 Figure out how to remove what we need from the list. */
      result = ADDRESS(block);
      if (mdp -> heapinfo[block].free.size > blocks)
	{
	  /* The block we found has a bit left over,
	     so relink the tail end back into the free list. */
	  mdp -> heapinfo[block + blocks].free.size
	    = mdp -> heapinfo[block].free.size - blocks;
	  mdp -> heapinfo[block + blocks].free.next
	    = mdp -> heapinfo[block].free.next;
	  mdp -> heapinfo[block + blocks].free.prev
	    = mdp -> heapinfo[block].free.prev;
	  mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
	    = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
	      = mdp -> heapindex = block + blocks;
	}
      else
	{
	  /* The block exactly matches our requirements,
	     so just remove it from the list. */
	  mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
	    = mdp -> heapinfo[block].free.prev;
	  mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
	    = mdp -> heapindex = mdp -> heapinfo[block].free.next;
	  mdp -> heapstats.chunks_free--;
	}

      mdp -> heapinfo[block].busy.type = 0;
      mdp -> heapinfo[block].busy.info.size = blocks;
      mdp -> heapstats.chunks_used++;
      mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
      mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
    }

  return (result);
}

/* When using this package, provide a version of malloc/realloc/free built
   on top of it, so that if we use the default sbrk() region we will not
   collide with another malloc package trying to do the same thing, if
   the application contains any "hidden" calls to malloc/realloc/free (such
   as inside a system library). */

PTR
malloc (size)
  size_t size;
{
  PTR result;

  result = mmalloc ((PTR) NULL, size);
  return (result);
}
Commit	Line	Data
c906108c SS	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 [email protected],
	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	}