Logo AND Algorithmique Numérique Distribuée

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