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 7 This 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 This 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 this 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 #ifndef _MALLOC_INTERNAL 26 #define _MALLOC_INTERNAL 27 #include <malloc.h> 28 #endif 29 30 /* Debugging hook for free. */ 31 void (*__free_hook) __P ((__ptr_t __ptr)); 32 33 /* List of blocks allocated by memalign. */ 34 struct 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. */ 38 void 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. */ 191 void 192 free (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