1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
24 * Copyright (c) 2015, Joyent, Inc. All rights reserved.
25 */
26
27 #include "lint.h"
28 #include "thr_uberdata.h"
29 #include <sys/syscall.h>
30
31 extern long __systemcall6(sysret_t *, int, ...);
32
33 /*
34 * This is a small and simple power of two memory allocator that is
35 * used internally by libc. Allocations are fast and memory is never
36 * returned to the system, except for allocations of 64 Kbytes and larger,
37 * which are simply mmap()ed and munmap()ed as needed. Smaller allocations
38 * (minimum size is 64 bytes) are obtained from mmap() of 64K chunks
39 * broken up into unit allocations and maintained on free lists.
40 * The interface requires the caller to keep track of the size of an
41 * allocated block and to pass that size back when freeing a block.
42 *
43 * This allocator is called during initialization, from code called
44 * from the dynamic linker, so it must not call anything that might
45 * re-invoke the dynamic linker to resolve a symbol. That is,
46 * it must only call functions that are wholly private to libc.
47 *
48 * Also, this allocator must be unique across all link maps
49 * because pointers returned by lmalloc() are stored in the
50 * thread structure, which is constant across all link maps.
51 *
52 * Memory blocks returned by lmalloc() are initialized to zero.
53 */
54
55 #define MINSIZE 64 /* (1 << MINSHIFT) */
56 #define MINSHIFT 6
57 #define CHUNKSIZE (64 * 1024)
58
59 /*
60 * bucketnum allocation size
61 * 0 64
62 * 1 128
63 * 2 256
64 * 3 512
65 * 4 1024
66 * 5 2048
67 * 6 4096
68 * 7 8192
69 * 8 16384
70 * 9 32768
71 */
72
73 /*
74 * See "thr_uberdata.h" for the definition of bucket_t.
75 * The 10 (NBUCKETS) buckets are allocated in uberdata.
76 */
77
78 /*
79 * Performance hack:
80 *
81 * On the very first lmalloc(), before any memory has been allocated,
82 * mmap() a 24K block of memory and carve out six 2K chunks, each
83 * of which is subdivided for the initial allocations from buckets
84 * 0, 1, 2, 3, 4 and 5, giving them initial numbers of elements
85 * 32, 16, 8, 4, 2 and 1, respectively. The remaining 12K is cut
86 * into one 4K buffer for bucket 6 and one 8K buffer for bucket 7.
87 *
88 * This results in almost all simple single-threaded processes,
89 * such as those employed in the kenbus test suite, having to
90 * allocate only this one 24K block during their lifetimes.
91 */
92
93 #define SUBCHUNKSIZE 2048
94 #define BASE_SIZE (24 * 1024)
95
96 static void
initial_allocation(bucket_t * bp)97 initial_allocation(bucket_t *bp) /* &__uberdata.bucket[0] */
98 {
99 sysret_t rval;
100 void *ptr;
101 size_t size;
102 size_t n;
103 int bucketnum;
104 void *base;
105
106 /*
107 * We do this seemingly obtuse call to __systemcall6(SYS_mmap)
108 * instead of simply calling mmap() directly because, if the
109 * mmap() system call fails, we must make sure that __cerror()
110 * is not called, because that would call ___errno()
111 * which would dereference curthread and, because we are very
112 * early in libc initialization, curthread is NULL and we would
113 * draw a hard-to-debug SIGSEGV core dump, or worse.
114 * We opt to give a thread panic message instead.
115 */
116 if (__systemcall6(&rval, SYS_mmap, CHUNKSIZE, BASE_SIZE,
117 PROT_READ | PROT_WRITE | PROT_EXEC,
118 _MAP_NEW | MAP_PRIVATE | MAP_ANON | MAP_ALIGN, -1L, (off_t)0) != 0)
119 thr_panic("initial allocation failed; swap space exhausted?");
120 base = (void *)rval.sys_rval1;
121
122 for (bucketnum = 0; bucketnum < 6; bucketnum++, bp++) {
123 size = (size_t)MINSIZE << bucketnum;
124 n = SUBCHUNKSIZE / size;
125 ptr = (void *)((caddr_t)base + bucketnum * SUBCHUNKSIZE);
126
127 ASSERT(bp->free_list == NULL);
128 bp->free_list = ptr;
129 while (--n != 0) {
130 void *next = (void *)((caddr_t)ptr + size);
131 *(void **)ptr = next;
132 ptr = next;
133 }
134 *(void **)ptr = NULL;
135 }
136
137 ptr = (void *)((caddr_t)base + bucketnum * SUBCHUNKSIZE);
138 ASSERT(bp->free_list == NULL);
139 bp->free_list = ptr;
140
141 ptr = (void *)((caddr_t)ptr + 2 * SUBCHUNKSIZE);
142 bp++;
143 ASSERT(bp->free_list == NULL);
144 bp->free_list = ptr;
145
146 ASSERT(((caddr_t)ptr - (caddr_t)base + 4 * SUBCHUNKSIZE) == BASE_SIZE);
147 }
148
149 /*
150 * This highbit code is the same as the code in fls_impl().
151 * We inline it here for speed.
152 */
153 static int
getbucketnum(size_t size)154 getbucketnum(size_t size)
155 {
156 int highbit = 1;
157
158 if (size-- <= MINSIZE)
159 return (0);
160
161 #ifdef _LP64
162 if (size & 0xffffffff00000000ul)
163 highbit += 32, size >>= 32;
164 #endif
165 if (size & 0xffff0000)
166 highbit += 16, size >>= 16;
167 if (size & 0xff00)
168 highbit += 8, size >>= 8;
169 if (size & 0xf0)
170 highbit += 4, size >>= 4;
171 if (size & 0xc)
172 highbit += 2, size >>= 2;
173 if (size & 0x2)
174 highbit += 1;
175
176 ASSERT(highbit > MINSHIFT);
177 return (highbit - MINSHIFT);
178 }
179
180 void *
lmalloc(size_t size)181 lmalloc(size_t size)
182 {
183 int bucketnum = getbucketnum(size);
184 ulwp_t *self;
185 uberdata_t *udp;
186 bucket_t *bp;
187 void *ptr;
188
189 /*
190 * ulwp_t structures must be allocated from a rwx mapping since it
191 * is a normal data object _and_ it contains instructions that are
192 * executed for user-land DTrace tracing with the fasttrap provider.
193 */
194 int prot = PROT_READ | PROT_WRITE | PROT_EXEC;
195
196 /* round size up to the proper power of 2 */
197 size = (size_t)MINSIZE << bucketnum;
198
199 if (bucketnum >= NBUCKETS) {
200 /* mmap() allocates memory already set to zero */
201 ptr = mmap((void *)CHUNKSIZE, size, prot,
202 MAP_PRIVATE|MAP_ANON|MAP_ALIGN, -1, (off_t)0);
203 if (ptr == MAP_FAILED)
204 ptr = NULL;
205 return (ptr);
206 }
207
208 if ((self = __curthread()) == NULL)
209 udp = &__uberdata;
210 else
211 udp = self->ul_uberdata;
212
213 if (udp->bucket_init == 0) {
214 ASSERT(udp->nthreads == 0);
215 initial_allocation(udp->bucket);
216 udp->bucket_init = 1;
217 }
218
219 bp = &udp->bucket[bucketnum];
220 if (self != NULL)
221 lmutex_lock(&bp->bucket_lock);
222
223 if ((ptr = bp->free_list) == NULL) {
224 size_t bsize;
225 size_t n;
226
227 /*
228 * Double the number of chunks mmap()ed each time,
229 * in case of large numbers of allocations.
230 */
231 if (bp->chunks == 0)
232 bp->chunks = 1;
233 else
234 bp->chunks <<= 1;
235 for (;;) {
236 bsize = CHUNKSIZE * bp->chunks;
237 n = bsize / size;
238 ptr = mmap((void *)CHUNKSIZE, bsize, prot,
239 MAP_PRIVATE|MAP_ANON|MAP_ALIGN, -1, (off_t)0);
240 if (ptr != MAP_FAILED)
241 break;
242 /* try a smaller chunk allocation */
243 if ((bp->chunks >>= 1) == 0) {
244 if (self != NULL)
245 lmutex_unlock(&bp->bucket_lock);
246 return (NULL);
247 }
248 }
249 bp->free_list = ptr;
250 while (--n != 0) {
251 void *next = (void *)((caddr_t)ptr + size);
252 *(void **)ptr = next;
253 ptr = next;
254 }
255 *(void **)ptr = NULL;
256 ptr = bp->free_list;
257 }
258 bp->free_list = *(void **)ptr;
259 if (self != NULL)
260 lmutex_unlock(&bp->bucket_lock);
261 /*
262 * We maintain the free list already zeroed except for the pointer
263 * stored at the head of the block (mmap() allocates memory already
264 * set to zero), so all we have to do is zero out the pointer.
265 */
266 *(void **)ptr = NULL;
267 return (ptr);
268 }
269
270 void
lfree(void * ptr,size_t size)271 lfree(void *ptr, size_t size)
272 {
273 int bucketnum = getbucketnum(size);
274 ulwp_t *self;
275 bucket_t *bp;
276
277 /* round size up to the proper power of 2 */
278 size = (size_t)MINSIZE << bucketnum;
279
280 if (bucketnum >= NBUCKETS) {
281 /* see comment below */
282 if (((uintptr_t)ptr & (CHUNKSIZE - 1)) != 0)
283 goto bad;
284 (void) munmap(ptr, size);
285 return;
286 }
287
288 /*
289 * If the low order bits are not all zero as expected, then panic.
290 * This can be caused by an application calling, for example,
291 * pthread_attr_destroy() without having first called
292 * pthread_attr_init() (thereby passing uninitialized data
293 * to pthread_attr_destroy() who then calls lfree() with
294 * the uninitialized data).
295 */
296 if (((uintptr_t)ptr & (size - 1)) != 0)
297 goto bad;
298
299 /*
300 * Zeroing the memory here saves time later when reallocating it.
301 */
302 (void) memset(ptr, 0, size);
303
304 if ((self = __curthread()) == NULL)
305 bp = &__uberdata.bucket[bucketnum];
306 else {
307 bp = &self->ul_uberdata->bucket[bucketnum];
308 lmutex_lock(&bp->bucket_lock);
309 }
310 *(void **)ptr = bp->free_list;
311 bp->free_list = ptr;
312 if (self != NULL)
313 lmutex_unlock(&bp->bucket_lock);
314 return;
315
316 bad:
317 thr_panic("lfree() called with a misaligned pointer");
318 }
319
320 /*
321 * The following functions can be used internally to libc
322 * to make memory allocations in the style of malloc()/free()
323 * (where the size of the allocation is not remembered by the caller)
324 * but which are safe to use within critical sections, that is,
325 * sections of code bounded by enter_critical()/exit_critical(),
326 * lmutex_lock()/lmutex_unlock() or lrw_rdlock()/lrw_wrlock()/lrw_unlock().
327 *
328 * These functions must never be used to allocate memory that is
329 * passed out of libc, for example by strdup(), because it is a
330 * fatal error to free() an object allocated by libc_malloc().
331 * Such objects can only be freed by calling libc_free().
332 */
333
334 #ifdef _LP64
335 #define ALIGNMENT 16
336 #else
337 #define ALIGNMENT 8
338 #endif
339
340 typedef union {
341 size_t private_size;
342 char private_align[ALIGNMENT];
343 } private_header_t;
344
345 void *
libc_malloc(size_t size)346 libc_malloc(size_t size)
347 {
348 private_header_t *ptr;
349
350 size = (size_t)MINSIZE << getbucketnum(size + sizeof (*ptr));
351 if ((ptr = lmalloc(size)) == NULL)
352 return (NULL);
353 ptr->private_size = size;
354 return (ptr + 1);
355 }
356
357 void *
libc_realloc(void * old,size_t size)358 libc_realloc(void *old, size_t size)
359 {
360 private_header_t *ptr;
361 void *new;
362
363 size = (size_t)MINSIZE << getbucketnum(size + sizeof (*ptr));
364 if ((ptr = lmalloc(size)) == NULL)
365 return (NULL);
366 ptr->private_size = size;
367 new = ptr + 1;
368 if (old != NULL) {
369 ptr = (private_header_t *)old - 1;
370 if (size >= ptr->private_size)
371 size = ptr->private_size;
372 (void) memcpy(new, old, size - sizeof (*ptr));
373 lfree(ptr, ptr->private_size);
374 }
375 return (new);
376 }
377
378 void
libc_free(void * p)379 libc_free(void *p)
380 {
381 private_header_t *ptr;
382
383 if (p) {
384 ptr = (private_header_t *)p - 1;
385 lfree(ptr, ptr->private_size);
386 }
387 }
388
389 char *
libc_strdup(const char * s1)390 libc_strdup(const char *s1)
391 {
392 char *s2 = libc_malloc(strlen(s1) + 1);
393
394 if (s2)
395 (void) strcpy(s2, s1);
396 return (s2);
397 }
398