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     mdp->heapindex = block;
 139     break;
 140
 141   default:
 142     /* Do some of the statistics.  */
 143     mdp -> heapstats.chunks_used--;
 144     mdp -> heapstats.bytes_used -= 1 << type;
 145     mdp -> heapstats.chunks_free++;
 146     mdp -> heapstats.bytes_free += 1 << type;
 147
 148     /* Get the address of the first free fragment in this block.  */
 149     prev = (struct list *)
 150       ((char *) ADDRESS(block) +
 151        (mdp->heapinfo[block].busy_frag.first << type));
 152
 153     frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type;
 154
 155     if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){
 156       UNLOCK(mdp);
 157       THROWF(system_error, 0, "Asked to free a fragment that is already free. I'm puzzled\n");
 158     }
 159
 160     /* Set size used in the fragment to -1 */
 161     mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1;
 162
 163     if (mdp->heapinfo[block].busy_frag.nfree ==
 164         (BLOCKSIZE >> type) - 1) {
 165       /* If all fragments of this block are free, remove them
 166          from the fragment list and free the whole block.  */
 167       next = prev;
 168       for (i = 1; i < (size_t) (BLOCKSIZE >> type); ++i) {
 169         next = next->next;
 170       }
 171       prev->prev->next = next;
 172       if (next != NULL) {
 173         next->prev = prev->prev;
 174       }
 175       /* pretend that this block is used and free it so that it gets properly coalesced with adjacent free blocks */
 176       mdp->heapinfo[block].type = 0;
 177       mdp->heapinfo[block].busy_block.size = 1;
 178       mdp->heapinfo[block].busy_block.busy_size = 0;
 179
 180       /* Keep the statistics accurate.  */
 181       mdp -> heapstats.chunks_used++;
 182       mdp -> heapstats.bytes_used += BLOCKSIZE;
 183       mdp -> heapstats.chunks_free -= BLOCKSIZE >> type;
 184       mdp -> heapstats.bytes_free -= BLOCKSIZE;
 185
 186       mfree((void *) mdp, (void *) ADDRESS(block));
 187     } else if (mdp->heapinfo[block].busy_frag.nfree != 0) {
 188       /* If some fragments of this block are free, link this
 189          fragment into the fragment list after the first free
 190          fragment of this block. */
 191       next = (struct list *) ptr;
 192       next->next = prev->next;
 193       next->prev = prev;
 194       prev->next = next;
 195       if (next->next != NULL) {
 196         next->next->prev = next;
 197       }
 198       ++mdp->heapinfo[block].busy_frag.nfree;
 199     } else {
 200       /* No fragments of this block were free before the one we just released,
 201        * so link this fragment into the fragment list and announce that
 202        it is the first free fragment of this block. */
 203       prev = (struct list *) ptr;
 204       mdp->heapinfo[block].busy_frag.nfree = 1;
 205       mdp->heapinfo[block].busy_frag.first = frag_nb;
 206       prev->next = mdp->fraghead[type].next;
 207       prev->prev = &mdp->fraghead[type];
 208       prev->prev->next = prev;
 209       if (prev->next != NULL) {
 210         prev->next->prev = prev;
 211       }
 212     }
 213     break;
 214   }
 215 }