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 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 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 * 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 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 * 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 * 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 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 * 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