1/*- 2 * Copyright (c) 2013, 2015 Antti Kantee. All rights reserved. 3 * Copyright (c) 1983, 1993 4 * The Regents of the University of California. 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. Neither the name of the University nor the names of its contributors 15 * may be used to endorse or promote products derived from this software 16 * without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31/* 32 * malloc.c (Caltech) 2/21/82 33 * Chris Kingsley, kingsley@cit-20. 34 * 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 * Modified for bmk by Antti Kantee over 30 years later. 42 */ 43 44#include <bmk-core/core.h> 45#include <bmk-core/null.h> 46#include <bmk-core/string.h> 47#include <bmk-core/memalloc.h> 48#include <bmk-core/platform.h> 49#include <bmk-core/pgalloc.h> 50#include <bmk-core/printf.h> 51#include <bmk-core/queue.h> 52 53#include <bmk-pcpu/pcpu.h> 54 55/* 56 * Header goes right before the allocated space and holds 57 * information about the allocation. Notably, we support 58 * max 4gig alignment. If you need more, use some other 59 * allocator than malloc. 60 */ 61struct memalloc_hdr { 62 uint32_t mh_alignpad; /* padding for alignment */ 63 uint16_t mh_magic; /* magic number */ 64 uint8_t mh_index; /* bucket # */ 65 uint8_t mh_who; /* who allocated */ 66}; 67bmk_ctassert(sizeof(struct memalloc_hdr) == 8); 68 69struct memalloc_freeblk { 70 LIST_ENTRY(memalloc_freeblk) entries; 71}; 72LIST_HEAD(freebucket, memalloc_freeblk); 73 74#define MAGIC 0xef /* magic # on accounting info */ 75#define UNMAGIC 0x1221 /* magic # != MAGIC */ 76#define UNMAGIC2 0x2442 /* magic # != MAGIC/UNMAGIC */ 77 78#define MINSHIFT 5 79#define LOCALBUCKETS (BMK_PCPU_PAGE_SHIFT - MINSHIFT) 80#define MINALIGN 16 81static struct freebucket freebuckets[LOCALBUCKETS]; 82 83/* 84 * nmalloc[i] is the difference between the number of mallocs and frees 85 * for a given block size. 86 */ 87static unsigned nmalloc[LOCALBUCKETS]; 88 89/* not multicore */ 90#define malloc_lock() 91#define malloc_unlock() 92 93static void * 94morecore(int bucket) 95{ 96 void *rv; 97 uint8_t *p; 98 unsigned long sz; /* size of desired block */ 99 unsigned long nblks; /* how many blocks we get */ 100 101 sz = 1<<(bucket+MINSHIFT); 102 nblks = BMK_PCPU_PAGE_SIZE / sz; 103 bmk_assert(nblks > 1); 104 105 if ((p = rv = bmk_pgalloc_one()) == NULL) 106 return NULL; 107 108 /* 109 * Add new memory allocated to that on 110 * free list for this hash bucket. Return one block. 111 */ 112 while (--nblks) { 113 struct memalloc_freeblk *frb; 114 115 p += sz; 116 frb = (void *)p; 117 LIST_INSERT_HEAD(&freebuckets[bucket], frb, entries); 118 } 119 return rv; 120} 121 122void 123bmk_memalloc_init(void) 124{ 125 unsigned i; 126 127 bmk_assert(BMK_PCPU_PAGE_SIZE > 0); 128 for (i = 0; i < LOCALBUCKETS; i++) { 129 LIST_INIT(&freebuckets[i]); 130 } 131} 132 133static void * 134bucketalloc(unsigned bucket) 135{ 136 struct memalloc_freeblk *frb; 137 138 malloc_lock(); 139 140 /* 141 * If nothing in hash bucket right now, 142 * request more memory from the system. 143 */ 144 if ((frb = LIST_FIRST(&freebuckets[bucket])) == NULL) { 145 if ((frb = morecore(bucket)) == NULL) { 146 malloc_unlock(); 147 return NULL; 148 } 149 } else { 150 LIST_REMOVE(frb, entries); 151 } 152 153 nmalloc[bucket]++; 154 malloc_unlock(); 155 156 return frb; 157} 158 159void * 160bmk_memalloc(unsigned long nbytes, unsigned long align, enum bmk_memwho who) 161{ 162 struct memalloc_hdr *hdr; 163 void *rv; 164 unsigned long allocbytes; 165 unsigned bucket; 166 unsigned long alignpad; 167 168 if (align & (align-1)) 169 return NULL; 170 if (align < MINALIGN) 171 align = MINALIGN; 172 bmk_assert(align <= (1UL<<31)); 173 174 /* need at least this many bytes plus header to satisfy alignment */ 175 allocbytes = nbytes + ((sizeof(*hdr) + (align-1)) & ~(align-1)); 176 177 /* 178 * Convert amount of memory requested into closest block size 179 * stored in hash buckets which satisfies request. 180 * Account for space used per block for accounting. 181 */ 182 if (allocbytes < 1<<MINSHIFT) { 183 bucket = 0; 184 } else { 185 bucket = 8*sizeof(allocbytes) 186 - __builtin_clzl(allocbytes>>MINSHIFT); 187 if ((allocbytes & (allocbytes-1)) == 0) 188 bucket--; 189 } 190 191 /* handle with page allocator? */ 192 if (bucket >= LOCALBUCKETS) { 193 hdr = bmk_pgalloc(bucket+MINSHIFT - BMK_PCPU_PAGE_SHIFT); 194 } else { 195 hdr = bucketalloc(bucket); 196 } 197 if (hdr == NULL) 198 return NULL; 199 200 /* align op before returned memory */ 201 rv = (void *)(((unsigned long)(hdr+1) + align - 1) & ~(align - 1)); 202 alignpad = (unsigned long)rv - (unsigned long)hdr; 203 204#ifdef MEMALLOC_TESTING 205 bmk_memset(hdr, MAGIC, alignpad); 206#endif 207 208 hdr = ((struct memalloc_hdr *)rv)-1; 209 hdr->mh_magic = MAGIC; 210 hdr->mh_index = bucket; 211 hdr->mh_alignpad = alignpad; 212 hdr->mh_who = who; 213 214 return rv; 215} 216 217void * 218bmk_xmalloc_bmk(unsigned long howmuch) 219{ 220 void *rv; 221 222 rv = bmk_memalloc(howmuch, 0, BMK_MEMWHO_WIREDBMK); 223 if (rv == NULL) 224 bmk_platform_halt("xmalloc failed"); 225 return rv; 226} 227 228void * 229bmk_memcalloc(unsigned long n, unsigned long size, enum bmk_memwho who) 230{ 231 void *v; 232 unsigned long tot = n * size; 233 234 if (size != 0 && tot / size != n) 235 return NULL; 236 237 if ((v = bmk_memalloc(tot, MINALIGN, who)) != NULL) { 238 bmk_memset(v, 0, tot); 239 } 240 return v; 241} 242 243void 244bmk_memfree(void *cp, enum bmk_memwho who) 245{ 246 struct memalloc_hdr *hdr; 247 struct memalloc_freeblk *frb; 248 unsigned long alignpad; 249 unsigned int index; 250 void *origp; 251 252 if (cp == NULL) 253 return; 254 hdr = ((struct memalloc_hdr *)cp)-1; 255 if (hdr->mh_magic != MAGIC) { 256#ifdef MEMALLOC_TESTING 257 bmk_assert(0); 258#else 259 bmk_printf("bmk_memfree: invalid pointer %p\n", cp); 260 return; 261#endif 262 } 263 if (hdr->mh_who != who) { 264 bmk_printf("bmk_memfree: mismatch %d vs. %d for %p", 265 hdr->mh_who, who, cp); 266 bmk_platform_halt("bmk_memalloc error"); 267 } 268 269 index = hdr->mh_index; 270 alignpad = hdr->mh_alignpad; 271 272 origp = (unsigned char *)cp - alignpad; 273 274#ifdef MEMALLOC_TESTING 275 { 276 unsigned long i; 277 278 for (i = 0; 279 (unsigned char *)origp + i < (unsigned char *)hdr; 280 i++) { 281 bmk_assert(*((unsigned char *)origp + i) == MAGIC); 282 283 } 284 } 285#endif 286 287 if (index >= LOCALBUCKETS) { 288 bmk_pgfree(origp, (index+MINSHIFT) - BMK_PCPU_PAGE_SHIFT); 289 } else { 290 malloc_lock(); 291 frb = origp; 292 LIST_INSERT_HEAD(&freebuckets[index], frb, entries); 293 nmalloc[index]--; 294 malloc_unlock(); 295 } 296} 297 298/* 299 * Don't do any of "storage compaction" nonsense, "just" the three modes: 300 * + cp == NULL ==> malloc 301 * + nbytes == 0 ==> free 302 * + else ==> realloc 303 * 304 * Also, assume that realloc() is always called from POSIX compat code, 305 * because nobody sane would use realloc() 306 */ 307void * 308bmk_memrealloc_user(void *cp, unsigned long nbytes) 309{ 310 struct memalloc_hdr *hdr; 311 unsigned long size; 312 unsigned long alignpad; 313 void *np; 314 315 if (cp == NULL) 316 return bmk_memalloc(nbytes, MINALIGN, BMK_MEMWHO_USER); 317 318 if (nbytes == 0) { 319 bmk_memfree(cp, BMK_MEMWHO_USER); 320 return NULL; 321 } 322 323 hdr = ((struct memalloc_hdr *)cp)-1; 324 size = hdr->mh_index; 325 alignpad = hdr->mh_alignpad; 326 327 /* don't bother "compacting". don't like it? don't use realloc! */ 328 if (((1<<(size+MINSHIFT)) - alignpad) >= nbytes) 329 return cp; 330 331 /* we're gonna need a bigger bucket */ 332 np = bmk_memalloc(nbytes, 8, BMK_MEMWHO_USER); 333 if (np == NULL) 334 return NULL; 335 336 bmk_memcpy(np, cp, (1<<(size+MINSHIFT)) - alignpad); 337 bmk_memfree(cp, BMK_MEMWHO_USER); 338 return np; 339} 340 341/* 342 * mstats - print out statistics about malloc 343 * 344 * Prints two lines of numbers, one showing the length of the free list 345 * for each size category, the second showing the number of mallocs - 346 * frees for each size category. 347 */ 348void 349bmk_memalloc_printstats(void) 350{ 351 struct memalloc_freeblk *frb; 352 unsigned long totfree = 0, totused = 0; 353 unsigned int i, j; 354 355 bmk_printf("Memory allocation statistics\n"); 356 bmk_printf("size:\t"); 357 for (i = 0; i < LOCALBUCKETS; i++) { 358 bmk_printf("%8d", 1<<(i+MINSHIFT)); 359 } 360 bmk_printf("\nfree:\t"); 361 for (i = 0; i < LOCALBUCKETS; i++) { 362 j = 0; 363 LIST_FOREACH(frb, &freebuckets[i], entries) { 364 j++; 365 } 366 bmk_printf("%8d", j); 367 totfree += j * (1 << (i + MINSHIFT)); 368 } 369 bmk_printf("\nused:\t"); 370 for (i = 0; i < LOCALBUCKETS; i++) { 371 bmk_printf("%8d", nmalloc[i]); 372 totused += nmalloc[i] * (1 << (i + MINSHIFT)); 373 } 374 bmk_printf("\n\tTotal in use: %lukB, total free in buckets: %lukB\n", 375 totused/1024, totfree/1024); 376} 377 378 379/* 380 * The rest of this file contains unit tests. 381 */ 382 383#ifdef MEMALLOC_TESTING 384 385#define TEST_SMALL_MINALLOC 0 386#define TEST_SMALL_MAXALLOC (128) 387 388#define TEST_LARGE_MINALLOC 0 389#define TEST_LARGE_MAXALLOC (64*1024) 390 391#define TEST_MINALIGN 1 392#define TEST_MAXALIGN 16 393 394#define NALLOC 1024 395#define NRING 16 396 397static unsigned randstate; 398 399static unsigned 400myrand(void) 401{ 402 403 return (randstate = randstate * 1103515245 + 12345) % (0x80000000L); 404} 405 406static void * 407testalloc(unsigned long min, unsigned long max) 408{ 409 void *v, *nv; 410 unsigned int size1, size2, align; 411 412 /* doesn't give an even bucket distribution, but ... */ 413 size1 = myrand() % ((max-min)+1) + min; 414 align = myrand() % ((TEST_MAXALIGN-TEST_MINALIGN)+1) + TEST_MINALIGN; 415 416 v = bmk_memalloc(size1, 1<<align, BMK_MEMWHO_USER); 417 if (!v) 418 return NULL; 419 bmk_assert(((uintptr_t)v & (align-1)) == 0); 420 bmk_memset(v, UNMAGIC, size1); 421 422 size2 = myrand() % ((max-min)+1) + min; 423 nv = bmk_memrealloc_user(v, size2); 424 if (nv) { 425 bmk_memset(nv, UNMAGIC2, size2); 426 return nv; 427 } 428 429 return size2 ? v : NULL; 430} 431 432/* XXX: no prototype */ 433void bmk_memalloc_test(void); 434void 435bmk_memalloc_test(void) 436{ 437 unsigned long min = TEST_LARGE_MINALLOC; 438 unsigned long max = TEST_LARGE_MAXALLOC; 439 void **rings; /* yay! */ 440 void **ring_alloc, **ring_free; /* yay! */ 441 int i, n; 442 443 randstate = (unsigned)bmk_platform_cpu_clock_epochoffset(); 444 445 rings = bmk_memalloc(NALLOC * NRING * sizeof(void *), 446 0, BMK_MEMWHO_USER); 447 /* so we can free() immediately without stress */ 448 bmk_memset(rings, 0, NALLOC * NRING * sizeof(void *)); 449 450 for (n = 0;; n = (n+1) % NRING) { 451 if (n == 0) { 452 bmk_memalloc_printstats(); 453 if (max == TEST_SMALL_MAXALLOC) { 454 min = TEST_LARGE_MINALLOC; 455 max = TEST_LARGE_MAXALLOC; 456 } else { 457 min = TEST_SMALL_MINALLOC; 458 max = TEST_SMALL_MAXALLOC; 459 } 460 } 461 462 ring_alloc = &rings[n * NALLOC]; 463 ring_free = &rings[((n + NRING/2) % NRING) * NALLOC]; 464 for (i = 0; i < NALLOC; i++) { 465 ring_alloc[i] = testalloc(min, max); 466 bmk_memfree(ring_free[i], BMK_MEMWHO_USER); 467 } 468 } 469} 470#endif /* MEMALLOC_TESTING */ 471