src/xbt/mmalloc/mfree.c

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