1/*	$NetBSD: free.c,v 1.1.1.1 2016/01/13 21:42:18 christos Exp $	*/
2
3/* Free a block of memory allocated by `malloc'.
4   Copyright 1990, 1991, 1992, 1994 Free Software Foundation, Inc.
5		  Written May 1989 by Mike Haertel.
6
7This library is free software; you can redistribute it and/or
8modify it under the terms of the GNU Library General Public License as
9published by the Free Software Foundation; either version 2 of the
10License, or (at your option) any later version.
11
12This library is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15Library General Public License for more details.
16
17You should have received a copy of the GNU Library General Public
18License along with this library; see the file COPYING.LIB.  If
19not, write to the Free Software Foundation, Inc., 675 Mass Ave,
20Cambridge, 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#ifndef	_MALLOC_INTERNAL
26#define _MALLOC_INTERNAL
27#include <malloc.h>
28#endif
29
30/* Debugging hook for free.  */
31void (*__free_hook) __P ((__ptr_t __ptr));
32
33/* List of blocks allocated by memalign.  */
34struct alignlist *_aligned_blocks = NULL;
35
36/* Return memory to the heap.
37   Like `free' but don't call a __free_hook if there is one.  */
38void
39_free_internal (ptr)
40     __ptr_t ptr;
41{
42  int type;
43  __malloc_size_t block, blocks;
44  register __malloc_size_t i;
45  struct list *prev, *next;
46
47  block = BLOCK (ptr);
48
49  type = _heapinfo[block].busy.type;
50  switch (type)
51    {
52    case 0:
53      /* Get as many statistics as early as we can.  */
54      --_chunks_used;
55      _bytes_used -= _heapinfo[block].busy.info.size * BLOCKSIZE;
56      _bytes_free += _heapinfo[block].busy.info.size * BLOCKSIZE;
57
58      /* Find the free cluster previous to this one in the free list.
59	 Start searching at the last block referenced; this may benefit
60	 programs with locality of allocation.  */
61      i = _heapindex;
62      if (i > block)
63	while (i > block)
64	  i = _heapinfo[i].free.prev;
65      else
66	{
67	  do
68	    i = _heapinfo[i].free.next;
69	  while (i > 0 && i < block);
70	  i = _heapinfo[i].free.prev;
71	}
72
73      /* Determine how to link this block into the free list.  */
74      if (block == i + _heapinfo[i].free.size)
75	{
76	  /* Coalesce this block with its predecessor.  */
77	  _heapinfo[i].free.size += _heapinfo[block].busy.info.size;
78	  block = i;
79	}
80      else
81	{
82	  /* Really link this block back into the free list.  */
83	  _heapinfo[block].free.size = _heapinfo[block].busy.info.size;
84	  _heapinfo[block].free.next = _heapinfo[i].free.next;
85	  _heapinfo[block].free.prev = i;
86	  _heapinfo[i].free.next = block;
87	  _heapinfo[_heapinfo[block].free.next].free.prev = block;
88	  ++_chunks_free;
89	}
90
91      /* Now that the block is linked in, see if we can coalesce it
92	 with its successor (by deleting its successor from the list
93	 and adding in its size).  */
94      if (block + _heapinfo[block].free.size == _heapinfo[block].free.next)
95	{
96	  _heapinfo[block].free.size
97	    += _heapinfo[_heapinfo[block].free.next].free.size;
98	  _heapinfo[block].free.next
99	    = _heapinfo[_heapinfo[block].free.next].free.next;
100	  _heapinfo[_heapinfo[block].free.next].free.prev = block;
101	  --_chunks_free;
102	}
103
104      /* Now see if we can return stuff to the system.  */
105      blocks = _heapinfo[block].free.size;
106      if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit
107	  && (*__morecore) (0) == ADDRESS (block + blocks))
108	{
109	  register __malloc_size_t bytes = blocks * BLOCKSIZE;
110	  _heaplimit -= blocks;
111	  (*__morecore) (-bytes);
112	  _heapinfo[_heapinfo[block].free.prev].free.next
113	    = _heapinfo[block].free.next;
114	  _heapinfo[_heapinfo[block].free.next].free.prev
115	    = _heapinfo[block].free.prev;
116	  block = _heapinfo[block].free.prev;
117	  --_chunks_free;
118	  _bytes_free -= bytes;
119	}
120
121      /* Set the next search to begin at this block.  */
122      _heapindex = block;
123      break;
124
125    default:
126      /* Do some of the statistics.  */
127      --_chunks_used;
128      _bytes_used -= 1 << type;
129      ++_chunks_free;
130      _bytes_free += 1 << type;
131
132      /* Get the address of the first free fragment in this block.  */
133      prev = (struct list *) ((char *) ADDRESS (block) +
134			   (_heapinfo[block].busy.info.frag.first << type));
135
136      if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1)
137	{
138	  /* If all fragments of this block are free, remove them
139	     from the fragment list and free the whole block.  */
140	  next = prev;
141	  for (i = 1; i < (__malloc_size_t) (BLOCKSIZE >> type); ++i)
142	    next = next->next;
143	  prev->prev->next = next;
144	  if (next != NULL)
145	    next->prev = prev->prev;
146	  _heapinfo[block].busy.type = 0;
147	  _heapinfo[block].busy.info.size = 1;
148
149	  /* Keep the statistics accurate.  */
150	  ++_chunks_used;
151	  _bytes_used += BLOCKSIZE;
152	  _chunks_free -= BLOCKSIZE >> type;
153	  _bytes_free -= BLOCKSIZE;
154
155	  free (ADDRESS (block));
156	}
157      else if (_heapinfo[block].busy.info.frag.nfree != 0)
158	{
159	  /* If some fragments of this block are free, link this
160	     fragment into the fragment list after the first free
161	     fragment of this block. */
162	  next = (struct list *) ptr;
163	  next->next = prev->next;
164	  next->prev = prev;
165	  prev->next = next;
166	  if (next->next != NULL)
167	    next->next->prev = next;
168	  ++_heapinfo[block].busy.info.frag.nfree;
169	}
170      else
171	{
172	  /* No fragments of this block are free, so link this
173	     fragment into the fragment list and announce that
174	     it is the first free fragment of this block. */
175	  prev = (struct list *) ptr;
176	  _heapinfo[block].busy.info.frag.nfree = 1;
177	  _heapinfo[block].busy.info.frag.first = (unsigned long int)
178	    ((unsigned long int) ((char *) ptr - (char *) NULL)
179	     % BLOCKSIZE >> type);
180	  prev->next = _fraghead[type].next;
181	  prev->prev = &_fraghead[type];
182	  prev->prev->next = prev;
183	  if (prev->next != NULL)
184	    prev->next->prev = prev;
185	}
186      break;
187    }
188}
189
190/* Return memory to the heap.  */
191void
192free (ptr)
193     __ptr_t ptr;
194{
195  register struct alignlist *l;
196
197  if (ptr == NULL)
198    return;
199
200  for (l = _aligned_blocks; l != NULL; l = l->next)
201    if (l->aligned == ptr)
202      {
203	l->aligned = NULL;	/* Mark the slot in the list as free.  */
204	ptr = l->exact;
205	break;
206      }
207
208  if (__free_hook != NULL)
209    (*__free_hook) (ptr);
210  else
211    _free_internal (ptr);
212}
213