Commit | Line | Data |
---|---|---|
90269d47 AM |
1 | /* ==== malloc.c ============================================================ |
2 | * Copyright (c) 1983 Regents of the University of California. | |
3 | * Copyright (c) 1993 by Chris Provenzano, proven@mit.edu | |
4 | * All rights reserved. | |
5 | * | |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions | |
8 | * are met: | |
9 | * 1. Redistributions of source code must retain the above copyright | |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * 2. Redistributions in binary form must reproduce the above copyright | |
12 | * notice, this list of conditions and the following disclaimer in the | |
13 | * documentation and/or other materials provided with the distribution. | |
14 | * 3. All advertising materials mentioning features or use of this software | |
15 | * must display the following acknowledgement: | |
16 | * This product includes software developed by the University of | |
17 | * California, Berkeley and its contributors. | |
18 | * 4. Neither the name of the University nor the names of its contributors | |
19 | * may be used to endorse or promote products derived from this software | |
20 | * without specific prior written permission. | |
21 | * | |
22 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
23 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
24 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
25 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
26 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
27 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
28 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
29 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
30 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
31 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
32 | * SUCH DAMAGE. | |
33 | * | |
34 | * Description : Malloc functions. | |
35 | * This is a very fast storage allocator. It allocates blocks of a small | |
36 | * number of different sizes, and keeps free lists of each size. Blocks that | |
37 | * don't exactly fit are passed up to the next larger size. In this | |
38 | * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. | |
39 | * This is designed for use in a virtual memory environment. | |
40 | * | |
41 | * 0.00 82/02/21 Chris Kingsley kingsley@cit-20 | |
42 | * | |
43 | * 1.00 93/11/06 proven | |
44 | * -Modified BSD libc malloc to be threadsafe. | |
45 | * | |
46 | */ | |
47 | ||
48 | #if defined(LIBC_SCCS) && !defined(lint) | |
49 | /*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/ | |
56a62443 | 50 | static char *rcsid = "$Id: malloc.c,v 1.2 1993/11/15 10:06:09 proven Exp $"; |
90269d47 AM |
51 | #endif /* LIBC_SCCS and not lint */ |
52 | ||
90269d47 AM |
53 | #include <pthread.h> |
54 | #include <sys/types.h> | |
55 | #include <string.h> | |
56 | #include <pthread/posix.h> | |
57 | ||
58 | /* | |
59 | * The overhead on a block is at least 4 bytes. When free, this space | |
60 | * contains a pointer to the next free block, and the bottom two bits must | |
61 | * be zero. When in use, the first byte is set to MAGIC, and the second | |
62 | * byte is the size index. The remaining bytes are for alignment. | |
63 | * If range checking is enabled then a second word holds the size of the | |
64 | * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). | |
65 | * The order of elements is critical: ov_magic must overlay the low order | |
66 | * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. | |
67 | */ | |
68 | union overhead { | |
69 | union overhead *ov_next; /* when free */ | |
70 | struct { | |
71 | u_char ovu_magic; /* magic number */ | |
72 | u_char ovu_index; /* bucket # */ | |
73 | #ifdef RCHECK | |
74 | u_short ovu_rmagic; /* range magic number */ | |
75 | u_int ovu_size; /* actual block size */ | |
76 | #endif | |
77 | } ovu; | |
78 | #define ov_magic ovu.ovu_magic | |
79 | #define ov_index ovu.ovu_index | |
80 | #define ov_rmagic ovu.ovu_rmagic | |
81 | #define ov_size ovu.ovu_size | |
82 | }; | |
83 | ||
84 | #define MAGIC 0xef /* magic # on accounting info */ | |
85 | #define RMAGIC 0x5555 /* magic # on range info */ | |
86 | ||
87 | #ifdef RCHECK | |
88 | #define RSLOP sizeof (u_short) | |
89 | #else | |
90 | #define RSLOP 0 | |
91 | #endif | |
92 | ||
93 | /* | |
94 | * nextf[i] is the pointer to the next free block of size 2^(i+3). The | |
95 | * smallest allocatable block is 8 bytes. The overhead information | |
96 | * precedes the data area returned to the user. | |
97 | */ | |
98 | #define NBUCKETS 30 | |
99 | static union overhead *nextf[NBUCKETS]; | |
100 | extern char *sbrk(); | |
101 | ||
102 | static int pagesz; /* page size */ | |
103 | static int pagebucket; /* page size bucket */ | |
104 | static semaphore malloc_lock = SEMAPHORE_CLEAR; | |
105 | ||
106 | #if defined(DEBUG) || defined(RCHECK) | |
107 | #define ASSERT(p) if (!(p)) botch("p") | |
108 | #include <stdio.h> | |
109 | static | |
110 | botch(s) | |
111 | char *s; | |
112 | { | |
113 | fprintf(stderr, "\r\nassertion botched: %s\r\n", s); | |
114 | (void) fflush(stderr); /* just in case user buffered it */ | |
115 | abort(); | |
116 | } | |
117 | #else | |
118 | #define ASSERT(p) | |
119 | #endif | |
120 | ||
121 | /* ========================================================================== | |
122 | * morecore() | |
123 | * | |
124 | * Allocate more memory to the indicated bucket | |
125 | */ | |
126 | static inline void morecore(int bucket) | |
127 | { | |
128 | register union overhead *op; | |
129 | register int sz; /* size of desired block */ | |
130 | int amt; /* amount to allocate */ | |
131 | int nblks; /* how many blocks we get */ | |
132 | ||
133 | /* | |
134 | * sbrk_size <= 0 only for big, FLUFFY, requests (about | |
135 | * 2^30 bytes on a VAX, I think) or for a negative arg. | |
136 | */ | |
137 | sz = 1 << (bucket + 3); | |
138 | #ifdef DEBUG | |
139 | ASSERT(sz > 0); | |
140 | #else | |
141 | if (sz <= 0) | |
142 | return; | |
143 | #endif | |
144 | if (sz < pagesz) { | |
145 | amt = pagesz; | |
146 | nblks = amt / sz; | |
147 | } else { | |
148 | amt = sz + pagesz; | |
149 | nblks = 1; | |
150 | } | |
151 | op = (union overhead *)sbrk(amt); | |
152 | /* no more room! */ | |
153 | if ((int)op == -1) | |
154 | return; | |
155 | /* | |
156 | * Add new memory allocated to that on | |
157 | * free list for this hash bucket. | |
158 | */ | |
159 | nextf[bucket] = op; | |
160 | while (--nblks > 0) { | |
161 | op->ov_next = (union overhead *)((caddr_t)op + sz); | |
162 | op = (union overhead *)((caddr_t)op + sz); | |
163 | } | |
164 | } | |
165 | ||
166 | /* ========================================================================== | |
167 | * malloc() | |
168 | */ | |
169 | void *malloc(size_t nbytes) | |
170 | { | |
171 | union overhead *op; | |
172 | unsigned int amt; | |
173 | int bucket, n; | |
174 | semaphore *lock; | |
175 | ||
176 | lock = &malloc_lock; | |
177 | while(SEMAPHORE_TEST_AND_SET(lock)) { | |
178 | pthread_yield(); | |
179 | } | |
180 | /* | |
181 | * First time malloc is called, setup page size and | |
182 | * align break pointer so all data will be page aligned. | |
183 | */ | |
184 | if (pagesz == 0) { | |
185 | pagesz = n = getpagesize(); | |
186 | op = (union overhead *)sbrk(0); | |
187 | n = n - sizeof (*op) - ((int)op & (n - 1)); | |
188 | if (n < 0) | |
189 | n += pagesz; | |
190 | if (n) { | |
191 | if (sbrk(n) == (char *)-1) | |
192 | return (NULL); | |
193 | } | |
194 | bucket = 0; | |
195 | amt = 8; | |
196 | while (pagesz > amt) { | |
197 | amt <<= 1; | |
198 | bucket++; | |
199 | } | |
200 | pagebucket = bucket; | |
201 | } | |
202 | /* | |
203 | * Convert amount of memory requested into closest block size | |
204 | * stored in hash buckets which satisfies request. | |
205 | * Account for space used per block for accounting. | |
206 | */ | |
207 | if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { | |
208 | #ifndef RCHECK | |
209 | amt = 8; /* size of first bucket */ | |
210 | bucket = 0; | |
211 | #else | |
212 | amt = 16; /* size of first bucket */ | |
213 | bucket = 1; | |
214 | #endif | |
215 | n = -(sizeof (*op) + RSLOP); | |
216 | } else { | |
217 | amt = pagesz; | |
218 | bucket = pagebucket; | |
219 | } | |
220 | while (nbytes > amt + n) { | |
221 | amt <<= 1; | |
222 | if (amt == 0) { | |
223 | SEMAPHORE_RESET(lock); | |
224 | return (NULL); | |
225 | } | |
226 | bucket++; | |
227 | } | |
228 | /* | |
229 | * If nothing in hash bucket right now, | |
230 | * request more memory from the system. | |
231 | */ | |
232 | if ((op = nextf[bucket]) == NULL) { | |
233 | morecore(bucket); | |
234 | if ((op = nextf[bucket]) == NULL) { | |
235 | SEMAPHORE_RESET(lock); | |
236 | return (NULL); | |
237 | } | |
238 | } | |
239 | /* remove from linked list */ | |
240 | nextf[bucket] = op->ov_next; | |
241 | op->ov_magic = MAGIC; | |
242 | op->ov_index = bucket; | |
243 | #ifdef RCHECK | |
244 | /* | |
245 | * Record allocated size of block and | |
246 | * bound space with magic numbers. | |
247 | */ | |
248 | op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); | |
249 | op->ov_rmagic = RMAGIC; | |
250 | *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; | |
251 | #endif | |
252 | SEMAPHORE_RESET(lock); | |
253 | return ((char *)(op + 1)); | |
254 | } | |
255 | ||
256 | /* ========================================================================== | |
257 | * free() | |
258 | */ | |
259 | void free(void *cp) | |
260 | { | |
261 | union overhead *op; | |
262 | semaphore *lock; | |
263 | int size; | |
264 | ||
265 | lock = &malloc_lock; | |
266 | while(SEMAPHORE_TEST_AND_SET(lock)) { | |
267 | pthread_yield(); | |
268 | } | |
269 | if (cp == NULL) { | |
270 | SEMAPHORE_RESET(lock); | |
271 | return; | |
272 | } | |
273 | op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); | |
274 | #ifdef DEBUG | |
275 | ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ | |
276 | #else | |
277 | if (op->ov_magic != MAGIC) { | |
278 | SEMAPHORE_RESET(lock); | |
279 | return; /* sanity */ | |
280 | } | |
281 | #endif | |
282 | #ifdef RCHECK | |
283 | ASSERT(op->ov_rmagic == RMAGIC); | |
284 | ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); | |
285 | #endif | |
286 | size = op->ov_index; | |
287 | ASSERT(size < NBUCKETS); | |
288 | op->ov_next = nextf[size]; /* also clobbers ov_magic */ | |
289 | nextf[size] = op; | |
290 | ||
291 | SEMAPHORE_RESET(lock); | |
292 | } | |
293 | ||
294 | /* ========================================================================== | |
295 | * realloc() | |
296 | * | |
297 | * Storage compaction is no longer supported, fix program and try again. | |
298 | */ | |
299 | void *realloc(void *cp, size_t nbytes) | |
300 | { | |
301 | u_int onb; | |
302 | int i; | |
303 | semaphore *lock; | |
304 | union overhead *op; | |
305 | char *res; | |
306 | ||
307 | if (cp == NULL) | |
308 | return (malloc(nbytes)); | |
309 | op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); | |
310 | ||
311 | if (op->ov_magic == MAGIC) { | |
312 | i = op->ov_index; | |
313 | } else { | |
314 | /* | |
315 | * This will cause old programs using storage compaction feature of | |
316 | * realloc to break in a pseudo resonable way that is easy to debug. | |
317 | * Returning a malloced buffer without the copy may cause | |
318 | * indeterministic behavior. | |
319 | */ | |
320 | return(NULL); | |
321 | } | |
322 | ||
323 | lock = &malloc_lock; | |
324 | while(SEMAPHORE_TEST_AND_SET(lock)) { | |
325 | pthread_yield(); | |
326 | } | |
327 | onb = 1 << (i + 3); | |
328 | if (onb < pagesz) | |
329 | onb -= sizeof (*op) + RSLOP; | |
330 | else | |
331 | onb += pagesz - sizeof (*op) - RSLOP; | |
332 | ||
333 | /* avoid the copy if same size block */ | |
334 | if (i) { | |
335 | i = 1 << (i + 2); | |
336 | if (i < pagesz) | |
337 | i -= sizeof (*op) + RSLOP; | |
338 | else | |
339 | i += pagesz - sizeof (*op) - RSLOP; | |
340 | } | |
341 | ||
342 | if (nbytes <= onb && nbytes > i) { | |
343 | #ifdef RCHECK | |
344 | op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); | |
345 | *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; | |
346 | #endif | |
347 | SEMAPHORE_RESET(lock); | |
348 | return(cp); | |
349 | } | |
350 | SEMAPHORE_RESET(lock); | |
351 | ||
352 | if ((res = malloc(nbytes)) == NULL) { | |
353 | free(cp); | |
354 | return (NULL); | |
355 | } | |
356 | ||
357 | bcopy(cp, res, (nbytes < onb) ? nbytes : onb); | |
358 | free(cp); | |
359 | ||
360 | return (res); | |
361 | } | |
362 |