src/xbt/mmalloc/mfree.c

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