1 /*
2 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
3 * Use is subject to license terms.
4 */
5
6 #pragma ident "%Z%%M% %I% %E% SMI"
7 /*
8 * wizard:/space/4.3reno/usr/src/lib/libc/stdlib/malloc.c
9 * Copyright (c) 1983 Regents of the University of California.
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms are permitted
13 * provided that: (1) source distributions retain this entire copyright
14 * notice and comment, and (2) distributions including binaries display
15 * the following acknowledgement: ``This product includes software
16 * developed by the University of California, Berkeley and its contributors''
17 * in the documentation or other materials provided with the distribution
18 * and in all advertising materials mentioning features or use of this
19 * software. Neither the name of the University nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
23 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
24 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
25 */
26
27 /*
28 * malloc.c (Caltech) 2/21/82
29 * Chris Kingsley, kingsley@cit-20.
30 *
31 * This is a very fast storage allocator. It allocates blocks of a small
32 * number of different sizes, and keeps free lists of each size. Blocks that
33 * don't exactly fit are passed up to the next larger size. In this
34 * implementation, the available sizes are 2^n-4 bytes long (ILP32)
35 * or 2^n-8 bytes long (LP64).
36 */
37
38 /*LINTLIBRARY*/
39 #include <sys/types.h>
40 #include <stdlib.h>
41 #include <unistd.h>
42 #include <string.h>
43 #include <limits.h>
44
45 /*
46 * The overhead on a block is at least 4 bytes. When free, this space
47 * contains a pointer to the next free block, and the bottom two bits must
48 * be zero. When in use, the first byte is set to MAGIC, and the second
49 * byte is the size index. The remaining bytes are for alignment.
50 * The order of elements is critical: ov_magic must overlay the low order
51 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
52 * Overhead is 4 bytes for ILP32, 8 bytes for LP64
53 */
54 union overhead {
55 union overhead *ov_next; /* when free */
56 struct {
57 #if defined(_LITTLE_ENDIAN)
58 uchar_t ovu_magic; /* magic number */
59 uchar_t ovu_index; /* bucket # */
60 uchar_t ovu_pad[sizeof (union overhead *) - 2];
61 #elif defined(_BIG_ENDIAN)
62 uchar_t ovu_pad[sizeof (union overhead *) - 2];
63 uchar_t ovu_index; /* bucket # */
64 uchar_t ovu_magic; /* magic number */
65 #else
66 #error "Endianness is not defined"
67 #endif
68 } ovu;
69 };
70
71 #define ov_magic ovu.ovu_magic
72 #define ov_index ovu.ovu_index
73
74 #define MAGIC 0xef /* magic # on accounting info */
75
76 /*
77 * nextf[i] is the pointer to the next free block of size 2^(i+EXP).
78 * The smallest allocatable block is 8 bytes (ILP32) or 16 bytes (LP64).
79 * The overhead information precedes the data area returned to the user.
80 */
81 #ifdef _LP64
82 #define EXP 4
83 #define NBUCKETS 60
84 #else
85 #define EXP 3
86 #define NBUCKETS 29
87 #endif
88 static union overhead *nextf[NBUCKETS];
89
90 static int pagesz; /* page size */
91 static long sbrk_adjust; /* in case sbrk() does alignment */
92 static int pagebucket; /* page size bucket */
93 static void morecore(int);
94 static int findbucket(union overhead *, int);
95
96 void *
malloc(size_t nbytes)97 malloc(size_t nbytes)
98 {
99 union overhead *op;
100 int bucket;
101 ssize_t n;
102 size_t amt;
103
104 /*
105 * First time malloc is called, setup page size and
106 * align break pointer so all data will be page aligned.
107 */
108 if (pagesz == 0) {
109 pagesz = getpagesize();
110 op = sbrk(0);
111 n = pagesz - sizeof (*op) - ((uintptr_t)op & (pagesz - 1));
112 if (n < 0)
113 n += pagesz;
114 if (n) {
115 if (sbrk(n) == (void *)-1)
116 return (NULL);
117 /*
118 * We were careful to arrange that
119 * sbrk(0) + sizeof (union overhead)
120 * should end up on a page boundary.
121 * If the underlying sbrk() performs alignment
122 * then this is false. We compute the adjustment.
123 */
124 op = sbrk(0);
125 sbrk_adjust = (uintptr_t)(op + 1) & (pagesz - 1);
126 } else {
127 sbrk_adjust = 0;
128 }
129 bucket = 0;
130 amt = (1UL << EXP);
131 while (pagesz > amt) {
132 amt <<= 1;
133 bucket++;
134 }
135 pagebucket = bucket;
136 }
137 /*
138 * Convert amount of memory requested into closest block size
139 * stored in hash buckets which satisfies request.
140 * Account for space used per block for accounting.
141 */
142 if (nbytes <= (n = pagesz - sizeof (*op))) {
143 amt = (1UL << EXP); /* size of first bucket */
144 bucket = 0;
145 n = -(ssize_t)(sizeof (*op));
146 } else {
147 amt = pagesz;
148 bucket = pagebucket;
149 }
150 while (nbytes > amt + n) {
151 amt <<= 1;
152 if (amt == 0)
153 return (NULL);
154 bucket++;
155 }
156 /*
157 * If nothing in hash bucket right now,
158 * request more memory from the system.
159 */
160 if ((op = nextf[bucket]) == NULL) {
161 morecore(bucket);
162 if ((op = nextf[bucket]) == NULL)
163 return (NULL);
164 }
165 /* remove from linked list */
166 nextf[bucket] = op->ov_next;
167 op->ov_magic = MAGIC;
168 op->ov_index = (uchar_t)bucket;
169 return (op + 1);
170 }
171
172 /*
173 * Allocate more memory to the indicated bucket.
174 */
175 static void
morecore(int bucket)176 morecore(int bucket)
177 {
178 union overhead *op;
179 size_t sz; /* size of desired block */
180 ssize_t amt; /* amount to allocate */
181 long nblks; /* how many blocks we get */
182
183 sz = 1UL << (bucket + EXP);
184 if (sz == 0)
185 return;
186 if (sz < pagesz) {
187 amt = pagesz;
188 nblks = amt / sz;
189 } else {
190 amt = sz + pagesz;
191 nblks = 1;
192 }
193 if (amt <= 0)
194 return;
195 if (amt > LONG_MAX) {
196 intptr_t delta;
197 /*
198 * the value required is too big for sbrk() to deal with
199 * in one go, so use sbrk() at most 2 times instead.
200 */
201 op = sbrk(0);
202 delta = LONG_MAX;
203 while (delta > 0) {
204 if (sbrk(delta) == (void *)-1) {
205 if (op != sbrk(0))
206 (void) sbrk(-LONG_MAX);
207 return;
208 }
209 amt -= LONG_MAX;
210 delta = amt;
211 }
212 }
213 else
214 op = sbrk(amt);
215 /* no more room! */
216 if (op == (union overhead *)-1)
217 return;
218 /* LINTED improper alignment */
219 op = (union overhead *)((caddr_t)op - sbrk_adjust);
220 /*
221 * Add new memory allocated to that on
222 * free list for this hash bucket.
223 */
224 nextf[bucket] = op;
225 while (--nblks > 0) {
226 /* LINTED improper alignment */
227 op->ov_next = (union overhead *)((caddr_t)op + sz);
228 /* LINTED improper alignment */
229 op = (union overhead *)((caddr_t)op + sz);
230 }
231 }
232
233 void
free(void * cp)234 free(void *cp)
235 {
236 int size;
237 union overhead *op;
238
239 if (cp == NULL)
240 return;
241 /* LINTED improper alignment */
242 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
243 if (op->ov_magic != MAGIC)
244 return; /* previously freed? */
245 size = op->ov_index;
246 op->ov_next = nextf[size]; /* also clobbers ov_magic */
247 nextf[size] = op;
248 }
249
250 /*
251 * When a program attempts "storage compaction" as mentioned in the
252 * old malloc man page, it realloc's an already freed block. Usually
253 * this is the last block it freed; occasionally it might be farther
254 * back. We have to search all the free lists for the block in order
255 * to determine its bucket: 1st we make one pass thru the lists
256 * checking only the first block in each; if that fails we search
257 * ``realloc_srchlen'' blocks in each list for a match (the variable
258 * is extern so the caller can modify it). If that fails we just copy
259 * however many bytes was given to realloc() and hope it's not huge.
260 */
261 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
262
263 void *
realloc(void * cp,size_t nbytes)264 realloc(void *cp, size_t nbytes)
265 {
266 size_t onb;
267 int i;
268 union overhead *op;
269 char *res;
270 int was_alloced = 0;
271
272 if (cp == NULL)
273 return (malloc(nbytes));
274 /* LINTED improper alignment */
275 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
276 if (op->ov_magic == MAGIC) {
277 was_alloced++;
278 i = op->ov_index;
279 } else {
280 /*
281 * Already free, doing "compaction".
282 *
283 * Search for the old block of memory on the
284 * free list. First, check the most common
285 * case (last element free'd), then (this failing)
286 * the last ``realloc_srchlen'' items free'd.
287 * If all lookups fail, then just malloc() the
288 * space and copy the size of the new space.
289 */
290 if ((i = findbucket(op, 1)) < 0 &&
291 (i = findbucket(op, realloc_srchlen)) < 0) {
292 if ((res = malloc(nbytes)) != NULL)
293 (void) memmove(res, cp, nbytes);
294 return (res);
295 }
296 }
297 onb = 1UL << (i + EXP);
298 if (onb < pagesz)
299 onb -= sizeof (*op);
300 else
301 onb += pagesz - sizeof (*op);
302 /* avoid the copy if same size block */
303 if (was_alloced) {
304 size_t sz = 0;
305 if (i) {
306 sz = 1UL << (i + EXP - 1);
307 if (sz < pagesz)
308 sz -= sizeof (*op);
309 else
310 sz += pagesz - sizeof (*op);
311 }
312 if (nbytes <= onb && nbytes > sz) {
313 return (cp);
314 } else
315 free(cp);
316 }
317 if ((res = malloc(nbytes)) == NULL)
318 return (NULL);
319 if (cp != res) /* common optimization if "compacting" */
320 (void) memmove(res, cp, (nbytes < onb) ? nbytes : onb);
321 return (res);
322 }
323
324 /*
325 * Search ``srchlen'' elements of each free list for a block whose
326 * header starts at ``freep''. If srchlen is -1 search the whole list.
327 * Return bucket number, or -1 if not found.
328 */
329 static int
findbucket(union overhead * freep,int srchlen)330 findbucket(union overhead *freep, int srchlen)
331 {
332 union overhead *p;
333 int i, j;
334
335 for (i = 0; i < NBUCKETS; i++) {
336 j = 0;
337 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
338 if (p == freep)
339 return (i);
340 j++;
341 }
342 }
343 return (-1);
344 }
345