Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
model-checker : need to switch between raw heap and std heap to remove ignore region
[simgrid.git] / 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 #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   int type;
24   size_t block, frag_nb;
25   register size_t i;
26   int it;
27
28   mmalloc_paranoia(mdp);
29 //  fprintf(stderr,"free(%p)\n",ptr);
30
31   if (ptr == NULL)
32     return;
33
34   block = BLOCK(ptr);
35
36   if ((char *) ptr < (char *) mdp->heapbase || block > mdp->heapsize) {
37     fprintf(stderr,"Ouch, this pointer is not mine. I refuse to free it. I refuse it to death!!\n");
38     abort();
39   }
40
41   type = mdp->heapinfo[block].type;
42
43   switch (type) {
44   case -1: /* Already free */
45     UNLOCK(mdp);
46     THROWF(system_error, 0, "Asked to free a fragment in a block that is already free. I'm puzzled\n");
47     break;
48     
49   case 0:
50     /* Get as many statistics as early as we can.  */
51     mdp -> heapstats.chunks_used--;
52     mdp -> heapstats.bytes_used -=
53       mdp -> heapinfo[block].busy_block.size * BLOCKSIZE;
54     mdp -> heapstats.bytes_free +=
55       mdp -> heapinfo[block].busy_block.size * BLOCKSIZE;
56
57     if(MC_is_active()){
58       if(mdp->heapinfo[block].busy_block.ignore == 1)
59         MC_remove_ignore_heap(ptr, mdp -> heapinfo[block].busy_block.busy_size);
60     }
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,"Internal Error: Asked to free a block already marked as free (block=%lu it=%d type=%lu). Please report this bug.\n",
87                   (unsigned long)block,it,(unsigned long)mdp->heapinfo[block].type);
88           abort();
89         }
90         mdp->heapinfo[block+it].type = -1;
91         mdp->heapinfo[block+it].busy_block.ignore = 0;
92     
93       }
94
95       block = i;
96     } else {
97       //fprintf(stderr,"Free block %d to %d (as a new chunck)\n",block,block+mdp->heapinfo[block].busy_block.size);
98       /* Really link this block back into the free list.  */
99       mdp->heapinfo[block].free_block.size = mdp->heapinfo[block].busy_block.size;
100       mdp->heapinfo[block].free_block.next = mdp->heapinfo[i].free_block.next;
101       mdp->heapinfo[block].free_block.prev = i;
102       mdp->heapinfo[i].free_block.next = block;
103       mdp->heapinfo[mdp->heapinfo[block].free_block.next].free_block.prev = block;
104       mdp -> heapstats.chunks_free++;
105       /* Mark all my ex-blocks as free */
106       for (it=0; it<mdp->heapinfo[block].free_block.size; it++) {
107         if (mdp->heapinfo[block+it].type <0) {
108           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",
109                   (unsigned long)block,it,(unsigned long)mdp->heapinfo[block].free_block.size,(unsigned long)mdp->heapinfo[block].type);
110           abort();
111         }
112         mdp->heapinfo[block+it].type = -1;
113         mdp->heapinfo[block+it].busy_block.ignore = 0;
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     /*    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
147     /* Set the next search to begin at this block.  
148        This is probably important to the trick where realloc returns the block to 
149        the system before reasking for the same block with a bigger size.  */
150     mdp->heapindex = block;
151     break;
152
153   default:
154     /* Do some of the statistics.  */
155     mdp -> heapstats.chunks_used--;
156     mdp -> heapstats.bytes_used -= 1 << type;
157     mdp -> heapstats.chunks_free++;
158     mdp -> heapstats.bytes_free += 1 << type;
159
160     frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type;
161
162     if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){
163       UNLOCK(mdp);
164       THROWF(system_error, 0, "Asked to free a fragment that is already free. I'm puzzled\n");
165     }
166
167     if(MC_is_active()){
168       if(mdp->heapinfo[block].busy_frag.ignore[frag_nb] == 1)
169         MC_remove_ignore_heap(ptr, mdp->heapinfo[block].busy_frag.frag_size[frag_nb]);
170     }
171     /* Set size used in the fragment to -1 */
172     mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1;
173     mdp->heapinfo[block].busy_frag.ignore[frag_nb] = 0;
174     
175 //    fprintf(stderr,"nfree:%zu capa:%d\n", mdp->heapinfo[block].busy_frag.nfree,(BLOCKSIZE >> type));
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 = 0;
183       mdp->heapinfo[block].busy_block.size = 1;
184       mdp->heapinfo[block].busy_block.busy_size = 0;
185       mdp->heapinfo[block].busy_block.ignore = 0;
186             
187       /* Keep the statistics accurate.  */
188       mdp -> heapstats.chunks_used++;
189       mdp -> heapstats.bytes_used += BLOCKSIZE;
190       mdp -> heapstats.chunks_free -= BLOCKSIZE >> type;
191       mdp -> heapstats.bytes_free -= BLOCKSIZE;
192       
193       mfree((void *) mdp, (void *) ADDRESS(block));
194     } else if (mdp->heapinfo[block].busy_frag.nfree != 0) {
195       /* If some fragments of this block are free, you know what? I'm already happy. */
196       ++mdp->heapinfo[block].busy_frag.nfree;
197     } else {
198       /* No fragments of this block were free before the one we just released,
199        * so add this block to the swag and announce that
200        it is the first free fragment of this block. */
201       mdp->heapinfo[block].busy_frag.nfree = 1;
202       mdp->heapinfo[block].freehook.prev = NULL;
203       mdp->heapinfo[block].freehook.next = NULL;
204
205       xbt_swag_insert(&mdp->heapinfo[block],&mdp->fraghead[type]);
206     }
207     break;
208   }
209 }
210