src/xbt/mmalloc/mfree.c

   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 /* Copyright (c) 2010. The SimGrid Team.
   8  * All rights reserved.                                                     */
   9
  10 /* This program is free software; you can redistribute it and/or modify it
  11  * under the terms of the license (GNU LGPL) which comes with this package. */
  12
  13 #include "mmprivate.h"
  14 #include "xbt/ex.h"
  15
  16 /* Return memory to the heap.
  17    Like `mfree' but don't call a mfree_hook if there is one.  */
  18
  19 /* Return memory to the heap.  */
  20 void mfree(struct mdesc *mdp, void *ptr)
  21 {
  22   int type;
  23   size_t block, frag_nb;
  24   register size_t i;
  25   struct list *prev, *next;
  26   int it;
  27
  28   if (ptr == NULL)
  29     return;
  30
  31   block = BLOCK(ptr);
  32
  33   if ((char *) ptr < (char *) mdp->heapbase || block > mdp->heapsize) {
  34     fprintf(stderr,"Ouch, this pointer is not mine. I refuse to free it. I refuse it to death!!\n");
  35     abort();
  36   }
  37
  38
  39   type = mdp->heapinfo[block].type;
  40
  41   switch (type) {
  42   case -1: /* Already free */
  43     UNLOCK(mdp);
  44     THROWF(system_error, 0, "Asked to free a fragment in a block that is already free. I'm puzzled\n");
  45     break;
  46
  47   case 0:
  48     /* Get as many statistics as early as we can.  */
  49     mdp -> heapstats.chunks_used--;
  50     mdp -> heapstats.bytes_used -=
  51       mdp -> heapinfo[block].busy_block.size * BLOCKSIZE;
  52     mdp -> heapstats.bytes_free +=
  53       mdp -> heapinfo[block].busy_block.size * BLOCKSIZE;
  54
  55     /* Find the free cluster previous to this one in the free list.
  56        Start searching at the last block referenced; this may benefit
  57        programs with locality of allocation.  */
  58     i = mdp->heapindex;
  59     if (i > block) {
  60       while (i > block) {
  61         i = mdp->heapinfo[i].free_block.prev;
  62       }
  63     } else {
  64       do {
  65         i = mdp->heapinfo[i].free_block.next;
  66       }
  67       while ((i != 0) && (i < block));
  68       i = mdp->heapinfo[i].free_block.prev;
  69     }
  70
  71     /* Determine how to link this block into the free list.  */
  72     if (block == i + mdp->heapinfo[i].free_block.size) {
  73
  74       /* Coalesce this block with its predecessor.  */
  75       mdp->heapinfo[i].free_block.size += mdp->heapinfo[block].busy_block.size;
  76       /* Mark all my ex-blocks as free */
  77       for (it=0; it<mdp->heapinfo[block].busy_block.size; it++) {
  78         if (mdp->heapinfo[block+it].type <0) {
  79           fprintf(stderr,"Internal Error: Asked to free a block already marked as free (block=%lu it=%d type=%lu). Please report this bug.\n",
  80                   (unsigned long)block,it,(unsigned long)mdp->heapinfo[block].type);
  81           abort();
  82         }
  83         mdp->heapinfo[block+it].type = -1;
  84       }
  85
  86       block = i;
  87     } else {
  88       //fprintf(stderr,"Free block %d to %d (as a new chunck)\n",block,block+mdp->heapinfo[block].busy_block.size);
  89       /* Really link this block back into the free list.  */
  90       mdp->heapinfo[block].free_block.size = mdp->heapinfo[block].busy_block.size;
  91       mdp->heapinfo[block].free_block.next = mdp->heapinfo[i].free_block.next;
  92       mdp->heapinfo[block].free_block.prev = i;
  93       mdp->heapinfo[i].free_block.next = block;
  94       mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.prev = block;
  95       mdp -> heapstats.chunks_free++;
  96       /* Mark all my ex-blocks as free */
  97       for (it=0; it<mdp->heapinfo[block].free_block.size; it++) {
  98         if (mdp->heapinfo[block+it].type <0) {
  99           fprintf(stderr,"Internal error: Asked to free a block already marked as free (block=%lu it=%d/%lu type=%lu). Please report this bug.\n",
 100                   (unsigned long)block,it,(unsigned long)mdp->heapinfo[block].free_block.size,(unsigned long)mdp->heapinfo[block].type);
 101           abort();
 102         }
 103         mdp->heapinfo[block+it].type = -1;
 104       }
 105     }
 106
 107     /* Now that the block is linked in, see if we can coalesce it
 108        with its successor (by deleting its successor from the list
 109        and adding in its size).  */
 110     if (block + mdp->heapinfo[block].free_block.size ==
 111         mdp->heapinfo[block].free_block.next) {
 112       mdp->heapinfo[block].free_block.size
 113         += mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.size;
 114       mdp->heapinfo[block].free_block.next
 115         = mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.next;
 116       mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.prev = block;
 117       mdp -> heapstats.chunks_free--;
 118     }
 119
 120     /* Now see if we can return stuff to the system.  */
 121     /*    blocks = mdp -> heapinfo[block].free.size;
 122           if (blocks >= FINAL_FREE_BLOCKS && block + blocks == mdp -> heaplimit
 123           && mdp -> morecore (mdp, 0) == ADDRESS (block + blocks))
 124           {
 125           register size_t bytes = blocks * BLOCKSIZE;
 126           mdp -> heaplimit -= blocks;
 127           mdp -> morecore (mdp, -bytes);
 128           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 129           = mdp -> heapinfo[block].free.next;
 130           mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 131           = mdp -> heapinfo[block].free.prev;
 132           block = mdp -> heapinfo[block].free.prev;
 133           mdp -> heapstats.chunks_free--;
 134           mdp -> heapstats.bytes_free -= bytes;
 135           } */
 136
 137     /* Set the next search to begin at this block.
 138        This is probably important to the trick where realloc returns the block to
 139        the system before reasking for the same block with a bigger size.  */
 140     mdp->heapindex = block;
 141     break;
 142
 143   default:
 144     /* Do some of the statistics.  */
 145     mdp -> heapstats.chunks_used--;
 146     mdp -> heapstats.bytes_used -= 1 << type;
 147     mdp -> heapstats.chunks_free++;
 148     mdp -> heapstats.bytes_free += 1 << type;
 149
 150     /* Get the address of the first free fragment in this block.  */
 151     prev = (struct list *)
 152       ((char *) ADDRESS(block) +
 153        (mdp->heapinfo[block].busy_frag.first << type));
 154
 155     frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type;
 156
 157     if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){
 158       UNLOCK(mdp);
 159       THROWF(system_error, 0, "Asked to free a fragment that is already free. I'm puzzled\n");
 160     }
 161
 162     /* Set size used in the fragment to -1 */
 163     mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1;
 164
 165     if (mdp->heapinfo[block].busy_frag.nfree ==
 166         (BLOCKSIZE >> type) - 1) {
 167       /* If all fragments of this block are free, remove them
 168          from the fragment list and free the whole block.  */
 169       next = prev;
 170       for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) {
 171         next = next->next;
 172       }
 173       prev->prev->next = next;
 174       if (next != NULL) {
 175         next->prev = prev->prev;
 176       }
 177       /* pretend that this block is used and free it so that it gets properly coalesced with adjacent free blocks */
 178       mdp->heapinfo[block].type = 0;
 179       mdp->heapinfo[block].busy_block.size = 1;
 180       mdp->heapinfo[block].busy_block.busy_size = 0;
 181
 182       /* Keep the statistics accurate.  */
 183       mdp -> heapstats.chunks_used++;
 184       mdp -> heapstats.bytes_used += BLOCKSIZE;
 185       mdp -> heapstats.chunks_free -= BLOCKSIZE >> type;
 186       mdp -> heapstats.bytes_free -= BLOCKSIZE;
 187
 188       mfree((void *) mdp, (void *) ADDRESS(block));
 189     } else if (mdp->heapinfo[block].busy_frag.nfree != 0) {
 190       /* If some fragments of this block are free, link this
 191          fragment into the fragment list after the first free
 192          fragment of this block. */
 193       next = (struct list *) ptr;
 194       next->next = prev->next;
 195       next->prev = prev;
 196       prev->next = next;
 197       if (next->next != NULL) {
 198         next->next->prev = next;
 199       }
 200       ++mdp->heapinfo[block].busy_frag.nfree;
 201     } else {
 202       /* No fragments of this block were free before the one we just released,
 203        * so link this fragment into the fragment list and announce that
 204        it is the first free fragment of this block. */
 205       prev = (struct list *) ptr;
 206       mdp->heapinfo[block].busy_frag.nfree = 1;
 207       mdp->heapinfo[block].busy_frag.first = frag_nb;
 208       prev->next = mdp->fraghead[type].next;
 209       prev->prev = &mdp->fraghead[type];
 210       prev->prev->next = prev;
 211       if (prev->next != NULL) {
 212         prev->next->prev = prev;
 213       }
 214     }
 215     break;
 216   }
 217 }