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 "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     THROW("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     THROW("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,
  86                   "Internal Error: Asked to free a block already marked as free (block=%zu it=%d type=%d). "
  87                   "Please report this bug.\n",
  88                   block, it, mdp->heapinfo[block].type);
  89           abort();
  90         }
  91         mdp->heapinfo[block+it].type = MMALLOC_TYPE_FREE;
  92       }
  93
  94       block = i;
  95     } else {
  96       /* Really link this block back into the free list.  */
  97       mdp->heapinfo[block].free_block.size = mdp->heapinfo[block].busy_block.size;
  98       mdp->heapinfo[block].free_block.next = mdp->heapinfo[i].free_block.next;
  99       mdp->heapinfo[block].free_block.prev = i;
 100       mdp->heapinfo[i].free_block.next = block;
 101       mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.prev = block;
 102       mdp -> heapstats.chunks_free++;
 103       /* Mark all my ex-blocks as free */
 104       for (it=0; it<mdp->heapinfo[block].free_block.size; it++) {
 105         if (mdp->heapinfo[block+it].type <0) {
 106           fprintf(stderr,
 107                   "Internal error: Asked to free a block already marked as free (block=%zu it=%d/%zu type=%d). "
 108                   "Please report this bug.\n",
 109                   block, it, mdp->heapinfo[block].free_block.size, mdp->heapinfo[block].type);
 110           abort();
 111         }
 112         mdp->heapinfo[block+it].type = MMALLOC_TYPE_FREE;
 113       }
 114     }
 115
 116     /* Now that the block is linked in, see if we can coalesce it
 117        with its successor (by deleting its successor from the list
 118        and adding in its size).  */
 119     if (block + mdp->heapinfo[block].free_block.size ==
 120         mdp->heapinfo[block].free_block.next) {
 121       mdp->heapinfo[block].free_block.size
 122         += mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.size;
 123       mdp->heapinfo[block].free_block.next
 124         = mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.next;
 125       mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.prev = block;
 126       mdp -> heapstats.chunks_free--;
 127     }
 128
 129     /* Now see if we can return stuff to the system.  */
 130 #if 0
 131           blocks = mdp -> heapinfo[block].free.size;
 132           if (blocks >= FINAL_FREE_BLOCKS && block + blocks == mdp -> heaplimit
 133           && mdp -> morecore (mdp, 0) == ADDRESS (block + blocks))
 134           {
 135           register size_t bytes = blocks * BLOCKSIZE;
 136           mdp -> heaplimit -= blocks;
 137           mdp -> morecore (mdp, -bytes);
 138           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 139           = mdp -> heapinfo[block].free.next;
 140           mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 141           = mdp -> heapinfo[block].free.prev;
 142           block = mdp -> heapinfo[block].free.prev;
 143           mdp -> heapstats.chunks_free--;
 144           mdp -> heapstats.bytes_free -= bytes;
 145           }
 146 #endif
 147
 148     /* Set the next search to begin at this block.
 149        This is probably important to the trick where realloc returns the block to
 150        the system before reasking for the same block with a bigger size.  */
 151     mdp->heapindex = block;
 152     break;
 153
 154   default:
 155     if (type < 0) {
 156       fprintf(stderr, "Unknown mmalloc block type.\n");
 157       abort();
 158     }
 159
 160     /* Do some of the statistics.  */
 161     mdp -> heapstats.chunks_used--;
 162     mdp -> heapstats.bytes_used -= 1 << type;
 163     mdp -> heapstats.chunks_free++;
 164     mdp -> heapstats.bytes_free += 1 << type;
 165
 166     frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type;
 167
 168     if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){
 169       UNLOCK(mdp);
 170       THROW("Asked to free a fragment that is already free. I'm puzzled\n");
 171     }
 172
 173     if (MC_is_active() && mdp->heapinfo[block].busy_frag.ignore[frag_nb] > 0)
 174       MC_unignore_heap(ptr, mdp->heapinfo[block].busy_frag.frag_size[frag_nb]);
 175
 176     /* Set size used in the fragment to -1 */
 177     mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1;
 178     mdp->heapinfo[block].busy_frag.ignore[frag_nb] = 0;
 179
 180     if (mdp->heapinfo[block].busy_frag.nfree ==
 181         (BLOCKSIZE >> type) - 1) {
 182       /* If all fragments of this block are free, remove this block from its swag and free the whole block.  */
 183       xbt_swag_remove(&mdp->heapinfo[block],&mdp->fraghead[type]);
 184
 185       /* pretend that this block is used and free it so that it gets properly coalesced with adjacent free blocks */
 186       mdp->heapinfo[block].type = MMALLOC_TYPE_UNFRAGMENTED;
 187       mdp->heapinfo[block].busy_block.size = 1;
 188       mdp->heapinfo[block].busy_block.busy_size = 0;
 189
 190       /* Keep the statistics accurate.  */
 191       mdp -> heapstats.chunks_used++;
 192       mdp -> heapstats.bytes_used += BLOCKSIZE;
 193       mdp -> heapstats.chunks_free -= BLOCKSIZE >> type;
 194       mdp -> heapstats.bytes_free -= BLOCKSIZE;
 195
 196       mfree(mdp, ADDRESS(block));
 197     } else if (mdp->heapinfo[block].busy_frag.nfree != 0) {
 198       /* If some fragments of this block are free, you know what? I'm already happy. */
 199       ++mdp->heapinfo[block].busy_frag.nfree;
 200     } else {
 201       /* No fragments of this block were free before the one we just released,
 202        * so add this block to the swag and announce that
 203        it is the first free fragment of this block. */
 204       mdp->heapinfo[block].busy_frag.nfree = 1;
 205       mdp->heapinfo[block].freehook.prev = NULL;
 206       mdp->heapinfo[block].freehook.next = NULL;
 207
 208       xbt_swag_insert(&mdp->heapinfo[block],&mdp->fraghead[type]);
 209     }
 210     break;
 211   }
 212 }