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