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