Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Do not store any metadata where the user (was) legitimate to write
[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
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   int it;
26
27   mmalloc_paranoia(mdp);
28 //  fprintf(stderr,"free(%p)\n",ptr);
29
30   if (ptr == NULL)
31     return;
32
33   block = BLOCK(ptr);
34
35   if ((char *) ptr < (char *) mdp->heapbase || block > mdp->heapsize) {
36     fprintf(stderr,"Ouch, this pointer is not mine. I refuse to free it. I refuse it to death!!\n");
37     abort();
38   }
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     frag_nb = RESIDUAL(ptr, BLOCKSIZE) >> type;
152
153     if( mdp->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){
154       UNLOCK(mdp);
155       THROWF(system_error, 0, "Asked to free a fragment that is already free. I'm puzzled\n");
156     }
157
158     /* Set size used in the fragment to -1 */
159     mdp->heapinfo[block].busy_frag.frag_size[frag_nb] = -1;
160
161 //    fprintf(stderr,"nfree:%zu capa:%d\n", mdp->heapinfo[block].busy_frag.nfree,(BLOCKSIZE >> type));
162     if (mdp->heapinfo[block].busy_frag.nfree ==
163         (BLOCKSIZE >> type) - 1) {
164       /* If all fragments of this block are free, remove this block from its swag and free the whole block.  */
165       xbt_swag_remove(&mdp->heapinfo[block],&mdp->fraghead[type]);
166
167       /* pretend that this block is used and free it so that it gets properly coalesced with adjacent free blocks */
168       mdp->heapinfo[block].type = 0;
169       mdp->heapinfo[block].busy_block.size = 1;
170       mdp->heapinfo[block].busy_block.busy_size = 0;
171       
172       /* Keep the statistics accurate.  */
173       mdp -> heapstats.chunks_used++;
174       mdp -> heapstats.bytes_used += BLOCKSIZE;
175       mdp -> heapstats.chunks_free -= BLOCKSIZE >> type;
176       mdp -> heapstats.bytes_free -= BLOCKSIZE;
177       
178       mfree((void *) mdp, (void *) ADDRESS(block));
179     } else if (mdp->heapinfo[block].busy_frag.nfree != 0) {
180       /* If some fragments of this block are free, you know what? I'm already happy. */
181       ++mdp->heapinfo[block].busy_frag.nfree;
182     } else {
183       /* No fragments of this block were free before the one we just released,
184        * so add this block to the swag and announce that
185        it is the first free fragment of this block. */
186       mdp->heapinfo[block].busy_frag.nfree = 1;
187       mdp->heapinfo[block].freehook.prev = NULL;
188       mdp->heapinfo[block].freehook.next = NULL;
189
190       xbt_swag_insert(&mdp->heapinfo[block],&mdp->fraghead[type]);
191     }
192     break;
193   }
194 }