| 1 | /* Free a block of memory allocated by `mmalloc'. |
| 2 | Copyright 1990, 1991, 1992 Free Software Foundation |
| 3 | |
| 4 | Written May 1989 by Mike Haertel. |
| 5 | Heavily modified Mar 1992 by Fred Fish. (fnf@cygnus.com) |
| 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 "mmprivate.h" |
| 26 | |
| 27 | /* Return memory to the heap. |
| 28 | Like `mfree' but don't call a mfree_hook if there is one. */ |
| 29 | |
| 30 | void |
| 31 | __mmalloc_free (mdp, ptr) |
| 32 | struct mdesc *mdp; |
| 33 | PTR ptr; |
| 34 | { |
| 35 | int type; |
| 36 | size_t block, blocks; |
| 37 | register size_t i; |
| 38 | struct list *prev, *next; |
| 39 | |
| 40 | block = BLOCK (ptr); |
| 41 | |
| 42 | type = mdp -> heapinfo[block].busy.type; |
| 43 | switch (type) |
| 44 | { |
| 45 | case 0: |
| 46 | /* Get as many statistics as early as we can. */ |
| 47 | mdp -> heapstats.chunks_used--; |
| 48 | mdp -> heapstats.bytes_used -= |
| 49 | mdp -> heapinfo[block].busy.info.size * BLOCKSIZE; |
| 50 | mdp -> heapstats.bytes_free += |
| 51 | mdp -> heapinfo[block].busy.info.size * BLOCKSIZE; |
| 52 | |
| 53 | /* Find the free cluster previous to this one in the free list. |
| 54 | Start searching at the last block referenced; this may benefit |
| 55 | programs with locality of allocation. */ |
| 56 | i = mdp -> heapindex; |
| 57 | if (i > block) |
| 58 | { |
| 59 | while (i > block) |
| 60 | { |
| 61 | i = mdp -> heapinfo[i].free.prev; |
| 62 | } |
| 63 | } |
| 64 | else |
| 65 | { |
| 66 | do |
| 67 | { |
| 68 | i = mdp -> heapinfo[i].free.next; |
| 69 | } |
| 70 | while ((i != 0) && (i < block)); |
| 71 | i = mdp -> heapinfo[i].free.prev; |
| 72 | } |
| 73 | |
| 74 | /* Determine how to link this block into the free list. */ |
| 75 | if (block == i + mdp -> heapinfo[i].free.size) |
| 76 | { |
| 77 | /* Coalesce this block with its predecessor. */ |
| 78 | mdp -> heapinfo[i].free.size += |
| 79 | mdp -> heapinfo[block].busy.info.size; |
| 80 | block = i; |
| 81 | } |
| 82 | else |
| 83 | { |
| 84 | /* Really link this block back into the free list. */ |
| 85 | mdp -> heapinfo[block].free.size = |
| 86 | mdp -> heapinfo[block].busy.info.size; |
| 87 | mdp -> heapinfo[block].free.next = mdp -> heapinfo[i].free.next; |
| 88 | mdp -> heapinfo[block].free.prev = i; |
| 89 | mdp -> heapinfo[i].free.next = block; |
| 90 | mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev = block; |
| 91 | mdp -> heapstats.chunks_free++; |
| 92 | } |
| 93 | |
| 94 | /* Now that the block is linked in, see if we can coalesce it |
| 95 | with its successor (by deleting its successor from the list |
| 96 | and adding in its size). */ |
| 97 | if (block + mdp -> heapinfo[block].free.size == |
| 98 | mdp -> heapinfo[block].free.next) |
| 99 | { |
| 100 | mdp -> heapinfo[block].free.size |
| 101 | += mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.size; |
| 102 | mdp -> heapinfo[block].free.next |
| 103 | = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.next; |
| 104 | mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev = block; |
| 105 | mdp -> heapstats.chunks_free--; |
| 106 | } |
| 107 | |
| 108 | /* Now see if we can return stuff to the system. */ |
| 109 | blocks = mdp -> heapinfo[block].free.size; |
| 110 | if (blocks >= FINAL_FREE_BLOCKS && block + blocks == mdp -> heaplimit |
| 111 | && mdp -> morecore (mdp, 0) == ADDRESS (block + blocks)) |
| 112 | { |
| 113 | register size_t bytes = blocks * BLOCKSIZE; |
| 114 | mdp -> heaplimit -= blocks; |
| 115 | mdp -> morecore (mdp, -bytes); |
| 116 | mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next |
| 117 | = mdp -> heapinfo[block].free.next; |
| 118 | mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev |
| 119 | = mdp -> heapinfo[block].free.prev; |
| 120 | block = mdp -> heapinfo[block].free.prev; |
| 121 | mdp -> heapstats.chunks_free--; |
| 122 | mdp -> heapstats.bytes_free -= bytes; |
| 123 | } |
| 124 | |
| 125 | /* Set the next search to begin at this block. */ |
| 126 | mdp -> heapindex = block; |
| 127 | break; |
| 128 | |
| 129 | default: |
| 130 | /* Do some of the statistics. */ |
| 131 | mdp -> heapstats.chunks_used--; |
| 132 | mdp -> heapstats.bytes_used -= 1 << type; |
| 133 | mdp -> heapstats.chunks_free++; |
| 134 | mdp -> heapstats.bytes_free += 1 << type; |
| 135 | |
| 136 | /* Get the address of the first free fragment in this block. */ |
| 137 | prev = (struct list *) |
| 138 | ((char *) ADDRESS(block) + |
| 139 | (mdp -> heapinfo[block].busy.info.frag.first << type)); |
| 140 | |
| 141 | if (mdp -> heapinfo[block].busy.info.frag.nfree == |
| 142 | (BLOCKSIZE >> type) - 1) |
| 143 | { |
| 144 | /* If all fragments of this block are free, remove them |
| 145 | from the fragment list and free the whole block. */ |
| 146 | next = prev; |
| 147 | for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) |
| 148 | { |
| 149 | next = next -> next; |
| 150 | } |
| 151 | prev -> prev -> next = next; |
| 152 | if (next != NULL) |
| 153 | { |
| 154 | next -> prev = prev -> prev; |
| 155 | } |
| 156 | mdp -> heapinfo[block].busy.type = 0; |
| 157 | mdp -> heapinfo[block].busy.info.size = 1; |
| 158 | |
| 159 | /* Keep the statistics accurate. */ |
| 160 | mdp -> heapstats.chunks_used++; |
| 161 | mdp -> heapstats.bytes_used += BLOCKSIZE; |
| 162 | mdp -> heapstats.chunks_free -= BLOCKSIZE >> type; |
| 163 | mdp -> heapstats.bytes_free -= BLOCKSIZE; |
| 164 | |
| 165 | mfree ((PTR) mdp, (PTR) ADDRESS(block)); |
| 166 | } |
| 167 | else if (mdp -> heapinfo[block].busy.info.frag.nfree != 0) |
| 168 | { |
| 169 | /* If some fragments of this block are free, link this |
| 170 | fragment into the fragment list after the first free |
| 171 | fragment of this block. */ |
| 172 | next = (struct list *) ptr; |
| 173 | next -> next = prev -> next; |
| 174 | next -> prev = prev; |
| 175 | prev -> next = next; |
| 176 | if (next -> next != NULL) |
| 177 | { |
| 178 | next -> next -> prev = next; |
| 179 | } |
| 180 | ++mdp -> heapinfo[block].busy.info.frag.nfree; |
| 181 | } |
| 182 | else |
| 183 | { |
| 184 | /* No fragments of this block are free, so link this |
| 185 | fragment into the fragment list and announce that |
| 186 | it is the first free fragment of this block. */ |
| 187 | prev = (struct list *) ptr; |
| 188 | mdp -> heapinfo[block].busy.info.frag.nfree = 1; |
| 189 | mdp -> heapinfo[block].busy.info.frag.first = |
| 190 | RESIDUAL (ptr, BLOCKSIZE) >> type; |
| 191 | prev -> next = mdp -> fraghead[type].next; |
| 192 | prev -> prev = &mdp -> fraghead[type]; |
| 193 | prev -> prev -> next = prev; |
| 194 | if (prev -> next != NULL) |
| 195 | { |
| 196 | prev -> next -> prev = prev; |
| 197 | } |
| 198 | } |
| 199 | break; |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | /* Return memory to the heap. */ |
| 204 | |
| 205 | void |
| 206 | mfree (md, ptr) |
| 207 | PTR md; |
| 208 | PTR ptr; |
| 209 | { |
| 210 | struct mdesc *mdp; |
| 211 | register struct alignlist *l; |
| 212 | |
| 213 | if (ptr != NULL) |
| 214 | { |
| 215 | mdp = MD_TO_MDP (md); |
| 216 | for (l = mdp -> aligned_blocks; l != NULL; l = l -> next) |
| 217 | { |
| 218 | if (l -> aligned == ptr) |
| 219 | { |
| 220 | l -> aligned = NULL; /* Mark the slot in the list as free. */ |
| 221 | ptr = l -> exact; |
| 222 | break; |
| 223 | } |
| 224 | } |
| 225 | if (mdp -> mfree_hook != NULL) |
| 226 | { |
| 227 | (*mdp -> mfree_hook) (md, ptr); |
| 228 | } |
| 229 | else |
| 230 | { |
| 231 | __mmalloc_free (mdp, ptr); |
| 232 | } |
| 233 | } |
| 234 | } |
| 235 | |
| 236 | /* When using this package, provide a version of malloc/realloc/free built |
| 237 | on top of it, so that if we use the default sbrk() region we will not |
| 238 | collide with another malloc package trying to do the same thing, if |
| 239 | the application contains any "hidden" calls to malloc/realloc/free (such |
| 240 | as inside a system library). */ |
| 241 | |
| 242 | void |
| 243 | free (ptr) |
| 244 | PTR ptr; |
| 245 | { |
| 246 | mfree ((PTR) NULL, ptr); |
| 247 | } |