1 /* Memory allocator `malloc'.
2 Copyright 1990, 1991, 1992 Free Software Foundation
4 Written May 1989 by Mike Haertel.
5 Heavily modified Mar 1992 by Fred Fish for mmap'c version.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Library General Public License as
9 published by the Free Software Foundation; either version 2 of the
10 License, or (at your option) any later version.
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Library General Public License for more details.
17 You should have received a copy of the GNU Library General Public
18 License along with the GNU C Library; see the file COPYING.LIB. If
19 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
20 Cambridge, MA 02139, USA.
22 The author may be reached (Email) at the address mike@ai.mit.edu,
23 or (US mail) as Mike Haertel c/o Free Software Foundation. */
27 /* Prototypes for local functions */
29 static int initialize
PARAMS ((struct mdesc
*));
30 static PTR morecore
PARAMS ((struct mdesc
*, size_t));
31 static PTR align
PARAMS ((struct mdesc
*, size_t));
33 /* Aligned allocation. */
41 unsigned long int adj
;
43 result
= mdp
-> morecore (mdp
, size
);
44 adj
= RESIDUAL (result
, BLOCKSIZE
);
47 adj
= BLOCKSIZE
- adj
;
48 (void) mdp
-> morecore (mdp
, adj
);
49 result
= (char *) result
+ adj
;
54 /* Set everything up and remember that we have. */
60 mdp
-> heapsize
= HEAP
/ BLOCKSIZE
;
61 mdp
-> heapinfo
= (malloc_info
*)
62 align (mdp
, mdp
-> heapsize
* sizeof (malloc_info
));
63 if (mdp
-> heapinfo
== NULL
)
67 memset ((PTR
)mdp
-> heapinfo
, 0, mdp
-> heapsize
* sizeof (malloc_info
));
68 mdp
-> heapinfo
[0].free
.size
= 0;
69 mdp
-> heapinfo
[0].free
.next
= mdp
-> heapinfo
[0].free
.prev
= 0;
71 mdp
-> heapbase
= (char *) mdp
-> heapinfo
;
72 mdp
-> flags
|= MMALLOC_INITIALIZED
;
76 /* Get neatly aligned memory, initializing or
77 growing the heap info table as necessary. */
85 malloc_info
*newinfo
, *oldinfo
;
88 result
= align (mdp
, size
);
94 /* Check if we need to grow the info table. */
95 if ((size_t) BLOCK ((char *) result
+ size
) > mdp
-> heapsize
)
97 newsize
= mdp
-> heapsize
;
98 while ((size_t) BLOCK ((char *) result
+ size
) > newsize
)
102 newinfo
= (malloc_info
*) align (mdp
, newsize
* sizeof (malloc_info
));
105 mdp
-> morecore (mdp
, -size
);
108 memset ((PTR
)newinfo
, 0, newsize
* sizeof (malloc_info
));
109 memcpy ((PTR
)newinfo
, (PTR
)mdp
-> heapinfo
,
110 mdp
-> heapsize
* sizeof (malloc_info
));
111 oldinfo
= mdp
-> heapinfo
;
112 newinfo
[BLOCK (oldinfo
)].busy
.type
= 0;
113 newinfo
[BLOCK (oldinfo
)].busy
.info
.size
114 = BLOCKIFY (mdp
-> heapsize
* sizeof (malloc_info
));
115 mdp
-> heapinfo
= newinfo
;
116 __mmalloc_free (mdp
, (PTR
)oldinfo
);
117 mdp
-> heapsize
= newsize
;
120 mdp
-> heaplimit
= BLOCK ((char *) result
+ size
);
124 /* Allocate memory from the heap. */
133 size_t block
, blocks
, lastblocks
, start
;
143 mdp
= MD_TO_MDP (md
);
145 if (mdp
-> mmalloc_hook
!= NULL
)
147 return ((*mdp
-> mmalloc_hook
) (md
, size
));
150 if (!(mdp
-> flags
& MMALLOC_INITIALIZED
))
152 if (!initialize (mdp
))
158 if (size
< sizeof (struct list
))
160 size
= sizeof (struct list
);
163 /* Determine the allocation policy based on the request size. */
164 if (size
<= BLOCKSIZE
/ 2)
166 /* Small allocation to receive a fragment of a block.
167 Determine the logarithm to base two of the fragment size. */
170 while ((size
/= 2) != 0)
175 /* Look in the fragment lists for a
176 free fragment of the desired size. */
177 next
= mdp
-> fraghead
[log
].next
;
180 /* There are free fragments of this size.
181 Pop a fragment out of the fragment list and return it.
182 Update the block's nfree and first counters. */
184 next
-> prev
-> next
= next
-> next
;
185 if (next
-> next
!= NULL
)
187 next
-> next
-> prev
= next
-> prev
;
189 block
= BLOCK (result
);
190 if (--mdp
-> heapinfo
[block
].busy
.info
.frag
.nfree
!= 0)
192 mdp
-> heapinfo
[block
].busy
.info
.frag
.first
=
193 RESIDUAL (next
-> next
, BLOCKSIZE
) >> log
;
196 /* Update the statistics. */
197 mdp
-> heapstats
.chunks_used
++;
198 mdp
-> heapstats
.bytes_used
+= 1 << log
;
199 mdp
-> heapstats
.chunks_free
--;
200 mdp
-> heapstats
.bytes_free
-= 1 << log
;
204 /* No free fragments of the desired size, so get a new block
205 and break it into fragments, returning the first. */
206 result
= mmalloc (md
, BLOCKSIZE
);
212 /* Link all fragments but the first into the free list. */
213 for (i
= 1; i
< (size_t) (BLOCKSIZE
>> log
); ++i
)
215 next
= (struct list
*) ((char *) result
+ (i
<< log
));
216 next
-> next
= mdp
-> fraghead
[log
].next
;
217 next
-> prev
= &mdp
-> fraghead
[log
];
218 next
-> prev
-> next
= next
;
219 if (next
-> next
!= NULL
)
221 next
-> next
-> prev
= next
;
225 /* Initialize the nfree and first counters for this block. */
226 block
= BLOCK (result
);
227 mdp
-> heapinfo
[block
].busy
.type
= log
;
228 mdp
-> heapinfo
[block
].busy
.info
.frag
.nfree
= i
- 1;
229 mdp
-> heapinfo
[block
].busy
.info
.frag
.first
= i
- 1;
231 mdp
-> heapstats
.chunks_free
+= (BLOCKSIZE
>> log
) - 1;
232 mdp
-> heapstats
.bytes_free
+= BLOCKSIZE
- (1 << log
);
233 mdp
-> heapstats
.bytes_used
-= BLOCKSIZE
- (1 << log
);
238 /* Large allocation to receive one or more blocks.
239 Search the free list in a circle starting at the last place visited.
240 If we loop completely around without finding a large enough
241 space we will have to get more memory from the system. */
242 blocks
= BLOCKIFY(size
);
243 start
= block
= MALLOC_SEARCH_START
;
244 while (mdp
-> heapinfo
[block
].free
.size
< blocks
)
246 block
= mdp
-> heapinfo
[block
].free
.next
;
249 /* Need to get more from the system. Check to see if
250 the new core will be contiguous with the final free
251 block; if so we don't need to get as much. */
252 block
= mdp
-> heapinfo
[0].free
.prev
;
253 lastblocks
= mdp
-> heapinfo
[block
].free
.size
;
254 if (mdp
-> heaplimit
!= 0 &&
255 block
+ lastblocks
== mdp
-> heaplimit
&&
256 mdp
-> morecore (mdp
, 0) == ADDRESS(block
+ lastblocks
) &&
257 (morecore (mdp
, (blocks
- lastblocks
) * BLOCKSIZE
)) != NULL
)
259 mdp
-> heapinfo
[block
].free
.size
= blocks
;
260 mdp
-> heapstats
.bytes_free
+=
261 (blocks
- lastblocks
) * BLOCKSIZE
;
264 result
= morecore(mdp
, blocks
* BLOCKSIZE
);
269 block
= BLOCK (result
);
270 mdp
-> heapinfo
[block
].busy
.type
= 0;
271 mdp
-> heapinfo
[block
].busy
.info
.size
= blocks
;
272 mdp
-> heapstats
.chunks_used
++;
273 mdp
-> heapstats
.bytes_used
+= blocks
* BLOCKSIZE
;
278 /* At this point we have found a suitable free list entry.
279 Figure out how to remove what we need from the list. */
280 result
= ADDRESS(block
);
281 if (mdp
-> heapinfo
[block
].free
.size
> blocks
)
283 /* The block we found has a bit left over,
284 so relink the tail end back into the free list. */
285 mdp
-> heapinfo
[block
+ blocks
].free
.size
286 = mdp
-> heapinfo
[block
].free
.size
- blocks
;
287 mdp
-> heapinfo
[block
+ blocks
].free
.next
288 = mdp
-> heapinfo
[block
].free
.next
;
289 mdp
-> heapinfo
[block
+ blocks
].free
.prev
290 = mdp
-> heapinfo
[block
].free
.prev
;
291 mdp
-> heapinfo
[mdp
-> heapinfo
[block
].free
.prev
].free
.next
292 = mdp
-> heapinfo
[mdp
-> heapinfo
[block
].free
.next
].free
.prev
293 = mdp
-> heapindex
= block
+ blocks
;
297 /* The block exactly matches our requirements,
298 so just remove it from the list. */
299 mdp
-> heapinfo
[mdp
-> heapinfo
[block
].free
.next
].free
.prev
300 = mdp
-> heapinfo
[block
].free
.prev
;
301 mdp
-> heapinfo
[mdp
-> heapinfo
[block
].free
.prev
].free
.next
302 = mdp
-> heapindex
= mdp
-> heapinfo
[block
].free
.next
;
303 mdp
-> heapstats
.chunks_free
--;
306 mdp
-> heapinfo
[block
].busy
.type
= 0;
307 mdp
-> heapinfo
[block
].busy
.info
.size
= blocks
;
308 mdp
-> heapstats
.chunks_used
++;
309 mdp
-> heapstats
.bytes_used
+= blocks
* BLOCKSIZE
;
310 mdp
-> heapstats
.bytes_free
-= blocks
* BLOCKSIZE
;
316 /* When using this package, provide a version of malloc/realloc/free built
317 on top of it, so that if we use the default sbrk() region we will not
318 collide with another malloc package trying to do the same thing, if
319 the application contains any "hidden" calls to malloc/realloc/free (such
320 as inside a system library). */
326 return (mmalloc ((void *) NULL
, size
));
This page took 0.036775 seconds and 4 git commands to generate.