1 /* 2 * KERN_SLABALLOC.C - Kernel SLAB memory allocator 3 * 4 * Copyright (c) 2003,2004,2010-2019 The DragonFly Project. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The DragonFly Project 8 * by Matthew Dillon <dillon@backplane.com> 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in 18 * the documentation and/or other materials provided with the 19 * distribution. 20 * 3. Neither the name of The DragonFly Project nor the names of its 21 * contributors may be used to endorse or promote products derived 22 * from this software without specific, prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 25 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 28 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 29 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 32 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 33 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 34 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 * 37 * This module implements a slab allocator drop-in replacement for the 38 * kernel malloc(). 39 * 40 * A slab allocator reserves a ZONE for each chunk size, then lays the 41 * chunks out in an array within the zone. Allocation and deallocation 42 * is nearly instantanious, and fragmentation/overhead losses are limited 43 * to a fixed worst-case amount. 44 * 45 * The downside of this slab implementation is in the chunk size 46 * multiplied by the number of zones. ~80 zones * 128K = 10MB of VM per cpu. 47 * In a kernel implementation all this memory will be physical so 48 * the zone size is adjusted downward on machines with less physical 49 * memory. The upside is that overhead is bounded... this is the *worst* 50 * case overhead. 51 * 52 * Slab management is done on a per-cpu basis and no locking or mutexes 53 * are required, only a critical section. When one cpu frees memory 54 * belonging to another cpu's slab manager an asynchronous IPI message 55 * will be queued to execute the operation. In addition, both the 56 * high level slab allocator and the low level zone allocator optimize 57 * M_ZERO requests, and the slab allocator does not have to pre initialize 58 * the linked list of chunks. 59 * 60 * XXX Balancing is needed between cpus. Balance will be handled through 61 * asynchronous IPIs primarily by reassigning the z_Cpu ownership of chunks. 62 * 63 * XXX If we have to allocate a new zone and M_USE_RESERVE is set, use of 64 * the new zone should be restricted to M_USE_RESERVE requests only. 65 * 66 * Alloc Size Chunking Number of zones 67 * 0-127 8 16 68 * 128-255 16 8 69 * 256-511 32 8 70 * 512-1023 64 8 71 * 1024-2047 128 8 72 * 2048-4095 256 8 73 * 4096-8191 512 8 74 * 8192-16383 1024 8 75 * 16384-32767 2048 8 76 * (if PAGE_SIZE is 4K the maximum zone allocation is 16383) 77 * 78 * Allocations >= ZoneLimit go directly to kmem. 79 * (n * PAGE_SIZE, n > 2) allocations go directly to kmem. 80 * 81 * Alignment properties: 82 * - All power-of-2 sized allocations are power-of-2 aligned. 83 * - Allocations with M_POWEROF2 are power-of-2 aligned on the nearest 84 * power-of-2 round up of 'size'. 85 * - Non-power-of-2 sized allocations are zone chunk size aligned (see the 86 * above table 'Chunking' column). 87 * 88 * API REQUIREMENTS AND SIDE EFFECTS 89 * 90 * To operate as a drop-in replacement to the FreeBSD-4.x malloc() we 91 * have remained compatible with the following API requirements: 92 * 93 * + malloc(0) is allowed and returns non-NULL (ahc driver) 94 * + ability to allocate arbitrarily large chunks of memory 95 */ 96 97 #include "opt_vm.h" 98 99 #include <sys/param.h> 100 #include <sys/systm.h> 101 #include <sys/kernel.h> 102 #include <sys/slaballoc.h> 103 #include <sys/mbuf.h> 104 #include <sys/vmmeter.h> 105 #include <sys/lock.h> 106 #include <sys/thread.h> 107 #include <sys/globaldata.h> 108 #include <sys/sysctl.h> 109 #include <sys/ktr.h> 110 #include <sys/malloc.h> 111 112 #include <vm/vm.h> 113 #include <vm/vm_param.h> 114 #include <vm/vm_kern.h> 115 #include <vm/vm_extern.h> 116 #include <vm/vm_object.h> 117 #include <vm/pmap.h> 118 #include <vm/vm_map.h> 119 #include <vm/vm_page.h> 120 #include <vm/vm_pageout.h> 121 122 #include <machine/cpu.h> 123 124 #include <sys/thread2.h> 125 #include <vm/vm_page2.h> 126 127 #if (__VM_CACHELINE_SIZE == 32) 128 #define CAN_CACHEALIGN(sz) ((sz) >= 256) 129 #elif (__VM_CACHELINE_SIZE == 64) 130 #define CAN_CACHEALIGN(sz) ((sz) >= 512) 131 #elif (__VM_CACHELINE_SIZE == 128) 132 #define CAN_CACHEALIGN(sz) ((sz) >= 1024) 133 #else 134 #error "unsupported cacheline size" 135 #endif 136 137 #define btokup(z) (&pmap_kvtom((vm_offset_t)(z))->ku_pagecnt) 138 139 #define MEMORY_STRING "ptr=%p type=%p size=%lu flags=%04x" 140 #define MEMORY_ARGS void *ptr, void *type, unsigned long size, int flags 141 142 #if !defined(KTR_MEMORY) 143 #define KTR_MEMORY KTR_ALL 144 #endif 145 KTR_INFO_MASTER(memory); 146 KTR_INFO(KTR_MEMORY, memory, malloc_beg, 0, "malloc begin"); 147 KTR_INFO(KTR_MEMORY, memory, malloc_end, 1, MEMORY_STRING, MEMORY_ARGS); 148 KTR_INFO(KTR_MEMORY, memory, free_zero, 2, MEMORY_STRING, MEMORY_ARGS); 149 KTR_INFO(KTR_MEMORY, memory, free_ovsz, 3, MEMORY_STRING, MEMORY_ARGS); 150 KTR_INFO(KTR_MEMORY, memory, free_ovsz_delayed, 4, MEMORY_STRING, MEMORY_ARGS); 151 KTR_INFO(KTR_MEMORY, memory, free_chunk, 5, MEMORY_STRING, MEMORY_ARGS); 152 KTR_INFO(KTR_MEMORY, memory, free_request, 6, MEMORY_STRING, MEMORY_ARGS); 153 KTR_INFO(KTR_MEMORY, memory, free_rem_beg, 7, MEMORY_STRING, MEMORY_ARGS); 154 KTR_INFO(KTR_MEMORY, memory, free_rem_end, 8, MEMORY_STRING, MEMORY_ARGS); 155 KTR_INFO(KTR_MEMORY, memory, free_beg, 9, "free begin"); 156 KTR_INFO(KTR_MEMORY, memory, free_end, 10, "free end"); 157 158 #define logmemory(name, ptr, type, size, flags) \ 159 KTR_LOG(memory_ ## name, ptr, type, size, flags) 160 #define logmemory_quick(name) \ 161 KTR_LOG(memory_ ## name) 162 163 /* 164 * Fixed globals (not per-cpu) 165 */ 166 static int ZoneSize; 167 static int ZoneLimit; 168 static int ZonePageCount; 169 static uintptr_t ZoneMask; 170 static int ZoneBigAlloc; /* in KB */ 171 static int ZoneGenAlloc; /* in KB */ 172 struct malloc_type *kmemstatistics; /* exported to vmstat */ 173 #ifdef INVARIANTS 174 static int32_t weirdary[16]; 175 #endif 176 177 static void *kmem_slab_alloc(vm_size_t bytes, vm_offset_t align, int flags); 178 static void kmem_slab_free(void *ptr, vm_size_t bytes); 179 180 #if defined(INVARIANTS) 181 static void chunk_mark_allocated(SLZone *z, void *chunk); 182 static void chunk_mark_free(SLZone *z, void *chunk); 183 #else 184 #define chunk_mark_allocated(z, chunk) 185 #define chunk_mark_free(z, chunk) 186 #endif 187 188 /* 189 * Misc constants. Note that allocations that are exact multiples of 190 * PAGE_SIZE, or exceed the zone limit, fall through to the kmem module. 191 */ 192 #define ZONE_RELS_THRESH 32 /* threshold number of zones */ 193 194 #ifdef INVARIANTS 195 /* 196 * The WEIRD_ADDR is used as known text to copy into free objects to 197 * try to create deterministic failure cases if the data is accessed after 198 * free. 199 */ 200 #define WEIRD_ADDR 0xdeadc0de 201 #endif 202 #define ZERO_LENGTH_PTR ((void *)-8) 203 204 /* 205 * Misc global malloc buckets 206 */ 207 208 MALLOC_DEFINE(M_CACHE, "cache", "Various Dynamically allocated caches"); 209 MALLOC_DEFINE(M_DEVBUF, "devbuf", "device driver memory"); 210 MALLOC_DEFINE(M_TEMP, "temp", "misc temporary data buffers"); 211 MALLOC_DEFINE(M_DRM, "m_drm", "DRM memory allocations"); 212 213 MALLOC_DEFINE(M_IP6OPT, "ip6opt", "IPv6 options"); 214 MALLOC_DEFINE(M_IP6NDP, "ip6ndp", "IPv6 Neighbor Discovery"); 215 216 /* 217 * Initialize the slab memory allocator. We have to choose a zone size based 218 * on available physical memory. We choose a zone side which is approximately 219 * 1/1024th of our memory, so if we have 128MB of ram we have a zone size of 220 * 128K. The zone size is limited to the bounds set in slaballoc.h 221 * (typically 32K min, 128K max). 222 */ 223 static void kmeminit(void *dummy); 224 225 char *ZeroPage; 226 227 SYSINIT(kmem, SI_BOOT1_ALLOCATOR, SI_ORDER_FIRST, kmeminit, NULL); 228 229 #ifdef INVARIANTS 230 /* 231 * If enabled any memory allocated without M_ZERO is initialized to -1. 232 */ 233 static int use_malloc_pattern; 234 SYSCTL_INT(_debug, OID_AUTO, use_malloc_pattern, CTLFLAG_RW, 235 &use_malloc_pattern, 0, 236 "Initialize memory to -1 if M_ZERO not specified"); 237 #endif 238 239 static int ZoneRelsThresh = ZONE_RELS_THRESH; 240 SYSCTL_INT(_kern, OID_AUTO, zone_big_alloc, CTLFLAG_RD, &ZoneBigAlloc, 0, ""); 241 SYSCTL_INT(_kern, OID_AUTO, zone_gen_alloc, CTLFLAG_RD, &ZoneGenAlloc, 0, ""); 242 SYSCTL_INT(_kern, OID_AUTO, zone_cache, CTLFLAG_RW, &ZoneRelsThresh, 0, ""); 243 static long SlabsAllocated; 244 static long SlabsFreed; 245 SYSCTL_LONG(_kern, OID_AUTO, slabs_allocated, CTLFLAG_RD, 246 &SlabsAllocated, 0, ""); 247 SYSCTL_LONG(_kern, OID_AUTO, slabs_freed, CTLFLAG_RD, 248 &SlabsFreed, 0, ""); 249 static int SlabFreeToTail; 250 SYSCTL_INT(_kern, OID_AUTO, slab_freetotail, CTLFLAG_RW, 251 &SlabFreeToTail, 0, ""); 252 253 static struct spinlock kmemstat_spin = 254 SPINLOCK_INITIALIZER(&kmemstat_spin, "malinit"); 255 256 /* 257 * Returns the kernel memory size limit for the purposes of initializing 258 * various subsystem caches. The smaller of available memory and the KVM 259 * memory space is returned. 260 * 261 * The size in megabytes is returned. 262 */ 263 size_t 264 kmem_lim_size(void) 265 { 266 size_t limsize; 267 268 limsize = (size_t)vmstats.v_page_count * PAGE_SIZE; 269 if (limsize > KvaSize) 270 limsize = KvaSize; 271 return (limsize / (1024 * 1024)); 272 } 273 274 static void 275 kmeminit(void *dummy) 276 { 277 size_t limsize; 278 int usesize; 279 #ifdef INVARIANTS 280 int i; 281 #endif 282 283 limsize = kmem_lim_size(); 284 usesize = (int)(limsize * 1024); /* convert to KB */ 285 286 /* 287 * If the machine has a large KVM space and more than 8G of ram, 288 * double the zone release threshold to reduce SMP invalidations. 289 * If more than 16G of ram, do it again. 290 * 291 * The BIOS eats a little ram so add some slop. We want 8G worth of 292 * memory sticks to trigger the first adjustment. 293 */ 294 if (ZoneRelsThresh == ZONE_RELS_THRESH) { 295 if (limsize >= 7 * 1024) 296 ZoneRelsThresh *= 2; 297 if (limsize >= 15 * 1024) 298 ZoneRelsThresh *= 2; 299 } 300 301 /* 302 * Calculate the zone size. This typically calculates to 303 * ZALLOC_MAX_ZONE_SIZE 304 */ 305 ZoneSize = ZALLOC_MIN_ZONE_SIZE; 306 while (ZoneSize < ZALLOC_MAX_ZONE_SIZE && (ZoneSize << 1) < usesize) 307 ZoneSize <<= 1; 308 ZoneLimit = ZoneSize / 4; 309 if (ZoneLimit > ZALLOC_ZONE_LIMIT) 310 ZoneLimit = ZALLOC_ZONE_LIMIT; 311 ZoneMask = ~(uintptr_t)(ZoneSize - 1); 312 ZonePageCount = ZoneSize / PAGE_SIZE; 313 314 #ifdef INVARIANTS 315 for (i = 0; i < NELEM(weirdary); ++i) 316 weirdary[i] = WEIRD_ADDR; 317 #endif 318 319 ZeroPage = kmem_slab_alloc(PAGE_SIZE, PAGE_SIZE, M_WAITOK|M_ZERO); 320 321 if (bootverbose) 322 kprintf("Slab ZoneSize set to %dKB\n", ZoneSize / 1024); 323 } 324 325 /* 326 * (low level) Initialize slab-related elements in the globaldata structure. 327 * 328 * Occurs after kmeminit(). 329 */ 330 void 331 slab_gdinit(globaldata_t gd) 332 { 333 SLGlobalData *slgd; 334 int i; 335 336 slgd = &gd->gd_slab; 337 for (i = 0; i < NZONES; ++i) 338 TAILQ_INIT(&slgd->ZoneAry[i]); 339 TAILQ_INIT(&slgd->FreeZones); 340 TAILQ_INIT(&slgd->FreeOvZones); 341 } 342 343 /* 344 * Initialize a malloc type tracking structure. 345 */ 346 void 347 malloc_init(void *data) 348 { 349 struct malloc_type *type = data; 350 struct kmalloc_use *use; 351 size_t limsize; 352 353 if (type->ks_magic != M_MAGIC) 354 panic("malloc type lacks magic"); 355 356 if (type->ks_limit != 0) 357 return; 358 359 if (vmstats.v_page_count == 0) 360 panic("malloc_init not allowed before vm init"); 361 362 limsize = kmem_lim_size() * (1024 * 1024); 363 type->ks_limit = limsize / 10; 364 365 if (ncpus == 1) 366 use = &type->ks_use0; 367 else 368 use = kmalloc(ncpus * sizeof(*use), M_TEMP, M_WAITOK | M_ZERO); 369 370 spin_lock(&kmemstat_spin); 371 type->ks_next = kmemstatistics; 372 type->ks_use = use; 373 kmemstatistics = type; 374 spin_unlock(&kmemstat_spin); 375 } 376 377 void 378 malloc_uninit(void *data) 379 { 380 struct malloc_type *type = data; 381 struct malloc_type *t; 382 #ifdef INVARIANTS 383 int i; 384 long ttl; 385 #endif 386 387 if (type->ks_magic != M_MAGIC) 388 panic("malloc type lacks magic"); 389 390 if (vmstats.v_page_count == 0) 391 panic("malloc_uninit not allowed before vm init"); 392 393 if (type->ks_limit == 0) 394 panic("malloc_uninit on uninitialized type"); 395 396 /* Make sure that all pending kfree()s are finished. */ 397 lwkt_synchronize_ipiqs("muninit"); 398 399 #ifdef INVARIANTS 400 /* 401 * memuse is only correct in aggregation. Due to memory being allocated 402 * on one cpu and freed on another individual array entries may be 403 * negative or positive (canceling each other out). 404 */ 405 for (i = ttl = 0; i < ncpus; ++i) 406 ttl += type->ks_use[i].memuse; 407 if (ttl) { 408 kprintf("malloc_uninit: %ld bytes of '%s' still allocated on cpu %d\n", 409 ttl, type->ks_shortdesc, i); 410 } 411 #endif 412 spin_lock(&kmemstat_spin); 413 if (type == kmemstatistics) { 414 kmemstatistics = type->ks_next; 415 } else { 416 for (t = kmemstatistics; t->ks_next != NULL; t = t->ks_next) { 417 if (t->ks_next == type) { 418 t->ks_next = type->ks_next; 419 break; 420 } 421 } 422 } 423 type->ks_next = NULL; 424 type->ks_limit = 0; 425 spin_unlock(&kmemstat_spin); 426 427 if (type->ks_use != &type->ks_use0) { 428 kfree(type->ks_use, M_TEMP); 429 type->ks_use = NULL; 430 } 431 } 432 433 /* 434 * Reinitialize all installed malloc regions after ncpus has been 435 * determined. type->ks_use0 is initially set to &type->ks_use0, 436 * this function will dynamically allocate it as appropriate for ncpus. 437 */ 438 void 439 malloc_reinit_ncpus(void) 440 { 441 struct malloc_type *t; 442 struct kmalloc_use *use; 443 444 /* 445 * If only one cpu we can leave ks_use set to ks_use0 446 */ 447 if (ncpus <= 1) 448 return; 449 450 /* 451 * Expand ks_use for all kmalloc blocks 452 */ 453 for (t = kmemstatistics; t; t = t->ks_next) { 454 KKASSERT(t->ks_use == &t->ks_use0); 455 t->ks_use = kmalloc(sizeof(*use) * ncpus, M_TEMP, M_WAITOK|M_ZERO); 456 t->ks_use[0] = t->ks_use0; 457 } 458 } 459 460 /* 461 * Increase the kmalloc pool limit for the specified pool. No changes 462 * are the made if the pool would shrink. 463 */ 464 void 465 kmalloc_raise_limit(struct malloc_type *type, size_t bytes) 466 { 467 KKASSERT(type->ks_limit != 0); 468 if (bytes == 0) 469 bytes = KvaSize; 470 if (type->ks_limit < bytes) 471 type->ks_limit = bytes; 472 } 473 474 void 475 kmalloc_set_unlimited(struct malloc_type *type) 476 { 477 type->ks_limit = kmem_lim_size() * (1024 * 1024); 478 } 479 480 /* 481 * Dynamically create a malloc pool. This function is a NOP if *typep is 482 * already non-NULL. 483 */ 484 void 485 kmalloc_create(struct malloc_type **typep, const char *descr) 486 { 487 struct malloc_type *type; 488 489 if (*typep == NULL) { 490 type = kmalloc(sizeof(*type), M_TEMP, M_WAITOK | M_ZERO); 491 type->ks_magic = M_MAGIC; 492 type->ks_shortdesc = descr; 493 malloc_init(type); 494 *typep = type; 495 } 496 } 497 498 /* 499 * Destroy a dynamically created malloc pool. This function is a NOP if 500 * the pool has already been destroyed. 501 */ 502 void 503 kmalloc_destroy(struct malloc_type **typep) 504 { 505 if (*typep != NULL) { 506 malloc_uninit(*typep); 507 kfree(*typep, M_TEMP); 508 *typep = NULL; 509 } 510 } 511 512 /* 513 * Calculate the zone index for the allocation request size and set the 514 * allocation request size to that particular zone's chunk size. 515 */ 516 static __inline int 517 zoneindex(unsigned long *bytes, unsigned long *align) 518 { 519 unsigned int n = (unsigned int)*bytes; /* unsigned for shift opt */ 520 521 if (n < 128) { 522 *bytes = n = (n + 7) & ~7; 523 *align = 8; 524 return(n / 8 - 1); /* 8 byte chunks, 16 zones */ 525 } 526 if (n < 256) { 527 *bytes = n = (n + 15) & ~15; 528 *align = 16; 529 return(n / 16 + 7); 530 } 531 if (n < 8192) { 532 if (n < 512) { 533 *bytes = n = (n + 31) & ~31; 534 *align = 32; 535 return(n / 32 + 15); 536 } 537 if (n < 1024) { 538 *bytes = n = (n + 63) & ~63; 539 *align = 64; 540 return(n / 64 + 23); 541 } 542 if (n < 2048) { 543 *bytes = n = (n + 127) & ~127; 544 *align = 128; 545 return(n / 128 + 31); 546 } 547 if (n < 4096) { 548 *bytes = n = (n + 255) & ~255; 549 *align = 256; 550 return(n / 256 + 39); 551 } 552 *bytes = n = (n + 511) & ~511; 553 *align = 512; 554 return(n / 512 + 47); 555 } 556 #if ZALLOC_ZONE_LIMIT > 8192 557 if (n < 16384) { 558 *bytes = n = (n + 1023) & ~1023; 559 *align = 1024; 560 return(n / 1024 + 55); 561 } 562 #endif 563 #if ZALLOC_ZONE_LIMIT > 16384 564 if (n < 32768) { 565 *bytes = n = (n + 2047) & ~2047; 566 *align = 2048; 567 return(n / 2048 + 63); 568 } 569 #endif 570 panic("Unexpected byte count %d", n); 571 return(0); 572 } 573 574 static __inline void 575 clean_zone_rchunks(SLZone *z) 576 { 577 SLChunk *bchunk; 578 579 while ((bchunk = z->z_RChunks) != NULL) { 580 cpu_ccfence(); 581 if (atomic_cmpset_ptr(&z->z_RChunks, bchunk, NULL)) { 582 *z->z_LChunksp = bchunk; 583 while (bchunk) { 584 chunk_mark_free(z, bchunk); 585 z->z_LChunksp = &bchunk->c_Next; 586 bchunk = bchunk->c_Next; 587 ++z->z_NFree; 588 } 589 break; 590 } 591 /* retry */ 592 } 593 } 594 595 /* 596 * If the zone becomes totally free and is not the only zone listed for a 597 * chunk size we move it to the FreeZones list. We always leave at least 598 * one zone per chunk size listed, even if it is freeable. 599 * 600 * Do not move the zone if there is an IPI in_flight (z_RCount != 0), 601 * otherwise MP races can result in our free_remote code accessing a 602 * destroyed zone. The remote end interlocks z_RCount with z_RChunks 603 * so one has to test both z_NFree and z_RCount. 604 * 605 * Since this code can be called from an IPI callback, do *NOT* try to mess 606 * with kernel_map here. Hysteresis will be performed at kmalloc() time. 607 */ 608 static __inline SLZone * 609 check_zone_free(SLGlobalData *slgd, SLZone *z) 610 { 611 SLZone *znext; 612 613 znext = TAILQ_NEXT(z, z_Entry); 614 if (z->z_NFree == z->z_NMax && z->z_RCount == 0 && 615 (TAILQ_FIRST(&slgd->ZoneAry[z->z_ZoneIndex]) != z || znext)) { 616 int *kup; 617 618 TAILQ_REMOVE(&slgd->ZoneAry[z->z_ZoneIndex], z, z_Entry); 619 620 z->z_Magic = -1; 621 TAILQ_INSERT_HEAD(&slgd->FreeZones, z, z_Entry); 622 ++slgd->NFreeZones; 623 kup = btokup(z); 624 *kup = 0; 625 } 626 return znext; 627 } 628 629 #ifdef SLAB_DEBUG 630 /* 631 * Used to debug memory corruption issues. Record up to (typically 32) 632 * allocation sources for this zone (for a particular chunk size). 633 */ 634 635 static void 636 slab_record_source(SLZone *z, const char *file, int line) 637 { 638 int i; 639 int b = line & (SLAB_DEBUG_ENTRIES - 1); 640 641 i = b; 642 do { 643 if (z->z_Sources[i].file == file && z->z_Sources[i].line == line) 644 return; 645 if (z->z_Sources[i].file == NULL) 646 break; 647 i = (i + 1) & (SLAB_DEBUG_ENTRIES - 1); 648 } while (i != b); 649 z->z_Sources[i].file = file; 650 z->z_Sources[i].line = line; 651 } 652 653 #endif 654 655 static __inline unsigned long 656 powerof2_size(unsigned long size) 657 { 658 int i; 659 660 if (size == 0 || powerof2(size)) 661 return size; 662 663 i = flsl(size); 664 return (1UL << i); 665 } 666 667 /* 668 * kmalloc() (SLAB ALLOCATOR) 669 * 670 * Allocate memory via the slab allocator. If the request is too large, 671 * or if it page-aligned beyond a certain size, we fall back to the 672 * KMEM subsystem. A SLAB tracking descriptor must be specified, use 673 * &SlabMisc if you don't care. 674 * 675 * M_RNOWAIT - don't block. 676 * M_NULLOK - return NULL instead of blocking. 677 * M_ZERO - zero the returned memory. 678 * M_USE_RESERVE - allow greater drawdown of the free list 679 * M_USE_INTERRUPT_RESERVE - allow the freelist to be exhausted 680 * M_POWEROF2 - roundup size to the nearest power of 2 681 * 682 * MPSAFE 683 */ 684 685 /* don't let kmalloc macro mess up function declaration */ 686 #undef kmalloc 687 688 #ifdef SLAB_DEBUG 689 void * 690 kmalloc_debug(unsigned long size, struct malloc_type *type, int flags, 691 const char *file, int line) 692 #else 693 void * 694 kmalloc(unsigned long size, struct malloc_type *type, int flags) 695 #endif 696 { 697 SLZone *z; 698 SLChunk *chunk; 699 SLGlobalData *slgd; 700 struct globaldata *gd; 701 unsigned long align; 702 int zi; 703 #ifdef INVARIANTS 704 int i; 705 #endif 706 707 logmemory_quick(malloc_beg); 708 gd = mycpu; 709 slgd = &gd->gd_slab; 710 711 /* 712 * XXX silly to have this in the critical path. 713 */ 714 KKASSERT(type->ks_limit != 0); 715 ++type->ks_use[gd->gd_cpuid].calls; 716 717 /* 718 * Flagged for cache-alignment 719 */ 720 if (flags & M_CACHEALIGN) { 721 if (size < __VM_CACHELINE_SIZE) 722 size = __VM_CACHELINE_SIZE; 723 else if (!CAN_CACHEALIGN(size)) 724 flags |= M_POWEROF2; 725 } 726 727 /* 728 * Flagged to force nearest power-of-2 (higher or same) 729 */ 730 if (flags & M_POWEROF2) 731 size = powerof2_size(size); 732 733 /* 734 * Handle the case where the limit is reached. Panic if we can't return 735 * NULL. The original malloc code looped, but this tended to 736 * simply deadlock the computer. 737 * 738 * ks_loosememuse is an up-only limit that is NOT MP-synchronized, used 739 * to determine if a more complete limit check should be done. The 740 * actual memory use is tracked via ks_use[cpu].memuse. 741 */ 742 while (type->ks_loosememuse >= type->ks_limit) { 743 int i; 744 long ttl; 745 746 for (i = ttl = 0; i < ncpus; ++i) 747 ttl += type->ks_use[i].memuse; 748 type->ks_loosememuse = ttl; /* not MP synchronized */ 749 if ((ssize_t)ttl < 0) /* deal with occassional race */ 750 ttl = 0; 751 if (ttl >= type->ks_limit) { 752 if (flags & M_NULLOK) { 753 logmemory(malloc_end, NULL, type, size, flags); 754 return(NULL); 755 } 756 panic("%s: malloc limit exceeded", type->ks_shortdesc); 757 } 758 } 759 760 /* 761 * Handle the degenerate size == 0 case. Yes, this does happen. 762 * Return a special pointer. This is to maintain compatibility with 763 * the original malloc implementation. Certain devices, such as the 764 * adaptec driver, not only allocate 0 bytes, they check for NULL and 765 * also realloc() later on. Joy. 766 */ 767 if (size == 0) { 768 logmemory(malloc_end, ZERO_LENGTH_PTR, type, size, flags); 769 return(ZERO_LENGTH_PTR); 770 } 771 772 /* 773 * Handle hysteresis from prior frees here in malloc(). We cannot 774 * safely manipulate the kernel_map in free() due to free() possibly 775 * being called via an IPI message or from sensitive interrupt code. 776 * 777 * NOTE: ku_pagecnt must be cleared before we free the slab or we 778 * might race another cpu allocating the kva and setting 779 * ku_pagecnt. 780 */ 781 while (slgd->NFreeZones > ZoneRelsThresh && (flags & M_RNOWAIT) == 0) { 782 crit_enter(); 783 if (slgd->NFreeZones > ZoneRelsThresh) { /* crit sect race */ 784 int *kup; 785 786 z = TAILQ_LAST(&slgd->FreeZones, SLZoneList); 787 KKASSERT(z != NULL); 788 TAILQ_REMOVE(&slgd->FreeZones, z, z_Entry); 789 --slgd->NFreeZones; 790 kup = btokup(z); 791 *kup = 0; 792 kmem_slab_free(z, ZoneSize); /* may block */ 793 atomic_add_int(&ZoneGenAlloc, -ZoneSize / 1024); 794 } 795 crit_exit(); 796 } 797 798 /* 799 * XXX handle oversized frees that were queued from kfree(). 800 */ 801 while (TAILQ_FIRST(&slgd->FreeOvZones) && (flags & M_RNOWAIT) == 0) { 802 crit_enter(); 803 if ((z = TAILQ_LAST(&slgd->FreeOvZones, SLZoneList)) != NULL) { 804 vm_size_t tsize; 805 806 KKASSERT(z->z_Magic == ZALLOC_OVSZ_MAGIC); 807 TAILQ_REMOVE(&slgd->FreeOvZones, z, z_Entry); 808 tsize = z->z_ChunkSize; 809 kmem_slab_free(z, tsize); /* may block */ 810 atomic_add_int(&ZoneBigAlloc, -(int)tsize / 1024); 811 } 812 crit_exit(); 813 } 814 815 /* 816 * Handle large allocations directly. There should not be very many of 817 * these so performance is not a big issue. 818 * 819 * The backend allocator is pretty nasty on a SMP system. Use the 820 * slab allocator for one and two page-sized chunks even though we lose 821 * some efficiency. XXX maybe fix mmio and the elf loader instead. 822 */ 823 if (size >= ZoneLimit || ((size & PAGE_MASK) == 0 && size > PAGE_SIZE*2)) { 824 int *kup; 825 826 size = round_page(size); 827 chunk = kmem_slab_alloc(size, PAGE_SIZE, flags); 828 if (chunk == NULL) { 829 logmemory(malloc_end, NULL, type, size, flags); 830 return(NULL); 831 } 832 atomic_add_int(&ZoneBigAlloc, (int)size / 1024); 833 flags &= ~M_ZERO; /* result already zero'd if M_ZERO was set */ 834 flags |= M_PASSIVE_ZERO; 835 kup = btokup(chunk); 836 *kup = size / PAGE_SIZE; 837 crit_enter(); 838 goto done; 839 } 840 841 /* 842 * Attempt to allocate out of an existing zone. First try the free list, 843 * then allocate out of unallocated space. If we find a good zone move 844 * it to the head of the list so later allocations find it quickly 845 * (we might have thousands of zones in the list). 846 * 847 * Note: zoneindex() will panic of size is too large. 848 */ 849 zi = zoneindex(&size, &align); 850 KKASSERT(zi < NZONES); 851 crit_enter(); 852 853 if ((z = TAILQ_LAST(&slgd->ZoneAry[zi], SLZoneList)) != NULL) { 854 /* 855 * Locate a chunk - we have to have at least one. If this is the 856 * last chunk go ahead and do the work to retrieve chunks freed 857 * from remote cpus, and if the zone is still empty move it off 858 * the ZoneAry. 859 */ 860 if (--z->z_NFree <= 0) { 861 KKASSERT(z->z_NFree == 0); 862 863 /* 864 * WARNING! This code competes with other cpus. It is ok 865 * for us to not drain RChunks here but we might as well, and 866 * it is ok if more accumulate after we're done. 867 * 868 * Set RSignal before pulling rchunks off, indicating that we 869 * will be moving ourselves off of the ZoneAry. Remote ends will 870 * read RSignal before putting rchunks on thus interlocking 871 * their IPI signaling. 872 */ 873 if (z->z_RChunks == NULL) 874 atomic_swap_int(&z->z_RSignal, 1); 875 876 clean_zone_rchunks(z); 877 878 /* 879 * Remove from the zone list if no free chunks remain. 880 * Clear RSignal 881 */ 882 if (z->z_NFree == 0) { 883 TAILQ_REMOVE(&slgd->ZoneAry[zi], z, z_Entry); 884 } else { 885 z->z_RSignal = 0; 886 } 887 } 888 889 /* 890 * Fast path, we have chunks available in z_LChunks. 891 */ 892 chunk = z->z_LChunks; 893 if (chunk) { 894 chunk_mark_allocated(z, chunk); 895 z->z_LChunks = chunk->c_Next; 896 if (z->z_LChunks == NULL) 897 z->z_LChunksp = &z->z_LChunks; 898 #ifdef SLAB_DEBUG 899 slab_record_source(z, file, line); 900 #endif 901 goto done; 902 } 903 904 /* 905 * No chunks are available in LChunks, the free chunk MUST be 906 * in the never-before-used memory area, controlled by UIndex. 907 * 908 * The consequences are very serious if our zone got corrupted so 909 * we use an explicit panic rather than a KASSERT. 910 */ 911 if (z->z_UIndex + 1 != z->z_NMax) 912 ++z->z_UIndex; 913 else 914 z->z_UIndex = 0; 915 916 if (z->z_UIndex == z->z_UEndIndex) 917 panic("slaballoc: corrupted zone"); 918 919 chunk = (SLChunk *)(z->z_BasePtr + z->z_UIndex * size); 920 if ((z->z_Flags & SLZF_UNOTZEROD) == 0) { 921 flags &= ~M_ZERO; 922 flags |= M_PASSIVE_ZERO; 923 } 924 chunk_mark_allocated(z, chunk); 925 #ifdef SLAB_DEBUG 926 slab_record_source(z, file, line); 927 #endif 928 goto done; 929 } 930 931 /* 932 * If all zones are exhausted we need to allocate a new zone for this 933 * index. Use M_ZERO to take advantage of pre-zerod pages. Also see 934 * UAlloc use above in regards to M_ZERO. Note that when we are reusing 935 * a zone from the FreeZones list UAlloc'd data will not be zero'd, and 936 * we do not pre-zero it because we do not want to mess up the L1 cache. 937 * 938 * At least one subsystem, the tty code (see CROUND) expects power-of-2 939 * allocations to be power-of-2 aligned. We maintain compatibility by 940 * adjusting the base offset below. 941 */ 942 { 943 int off; 944 int *kup; 945 946 if ((z = TAILQ_FIRST(&slgd->FreeZones)) != NULL) { 947 TAILQ_REMOVE(&slgd->FreeZones, z, z_Entry); 948 --slgd->NFreeZones; 949 bzero(z, sizeof(SLZone)); 950 z->z_Flags |= SLZF_UNOTZEROD; 951 } else { 952 z = kmem_slab_alloc(ZoneSize, ZoneSize, flags|M_ZERO); 953 if (z == NULL) 954 goto fail; 955 atomic_add_int(&ZoneGenAlloc, ZoneSize / 1024); 956 } 957 958 /* 959 * How big is the base structure? 960 */ 961 #if defined(INVARIANTS) 962 /* 963 * Make room for z_Bitmap. An exact calculation is somewhat more 964 * complicated so don't make an exact calculation. 965 */ 966 off = offsetof(SLZone, z_Bitmap[(ZoneSize / size + 31) / 32]); 967 bzero(z->z_Bitmap, (ZoneSize / size + 31) / 8); 968 #else 969 off = sizeof(SLZone); 970 #endif 971 972 /* 973 * Guarentee power-of-2 alignment for power-of-2-sized chunks. 974 * Otherwise properly align the data according to the chunk size. 975 */ 976 if (powerof2(size)) 977 align = size; 978 off = roundup2(off, align); 979 980 z->z_Magic = ZALLOC_SLAB_MAGIC; 981 z->z_ZoneIndex = zi; 982 z->z_NMax = (ZoneSize - off) / size; 983 z->z_NFree = z->z_NMax - 1; 984 z->z_BasePtr = (char *)z + off; 985 z->z_UIndex = z->z_UEndIndex = slgd->JunkIndex % z->z_NMax; 986 z->z_ChunkSize = size; 987 z->z_CpuGd = gd; 988 z->z_Cpu = gd->gd_cpuid; 989 z->z_LChunksp = &z->z_LChunks; 990 #ifdef SLAB_DEBUG 991 bcopy(z->z_Sources, z->z_AltSources, sizeof(z->z_Sources)); 992 bzero(z->z_Sources, sizeof(z->z_Sources)); 993 #endif 994 chunk = (SLChunk *)(z->z_BasePtr + z->z_UIndex * size); 995 TAILQ_INSERT_HEAD(&slgd->ZoneAry[zi], z, z_Entry); 996 if ((z->z_Flags & SLZF_UNOTZEROD) == 0) { 997 flags &= ~M_ZERO; /* already zero'd */ 998 flags |= M_PASSIVE_ZERO; 999 } 1000 kup = btokup(z); 1001 *kup = -(z->z_Cpu + 1); /* -1 to -(N+1) */ 1002 chunk_mark_allocated(z, chunk); 1003 #ifdef SLAB_DEBUG 1004 slab_record_source(z, file, line); 1005 #endif 1006 1007 /* 1008 * Slide the base index for initial allocations out of the next 1009 * zone we create so we do not over-weight the lower part of the 1010 * cpu memory caches. 1011 */ 1012 slgd->JunkIndex = (slgd->JunkIndex + ZALLOC_SLAB_SLIDE) 1013 & (ZALLOC_MAX_ZONE_SIZE - 1); 1014 } 1015 1016 done: 1017 ++type->ks_use[gd->gd_cpuid].inuse; 1018 type->ks_use[gd->gd_cpuid].memuse += size; 1019 type->ks_use[gd->gd_cpuid].loosememuse += size; 1020 if (type->ks_use[gd->gd_cpuid].loosememuse >= ZoneSize) { 1021 /* not MP synchronized */ 1022 type->ks_loosememuse += type->ks_use[gd->gd_cpuid].loosememuse; 1023 type->ks_use[gd->gd_cpuid].loosememuse = 0; 1024 } 1025 crit_exit(); 1026 1027 if (flags & M_ZERO) 1028 bzero(chunk, size); 1029 #ifdef INVARIANTS 1030 else if ((flags & (M_ZERO|M_PASSIVE_ZERO)) == 0) { 1031 if (use_malloc_pattern) { 1032 for (i = 0; i < size; i += sizeof(int)) { 1033 *(int *)((char *)chunk + i) = -1; 1034 } 1035 } 1036 chunk->c_Next = (void *)-1; /* avoid accidental double-free check */ 1037 } 1038 #endif 1039 logmemory(malloc_end, chunk, type, size, flags); 1040 return(chunk); 1041 fail: 1042 crit_exit(); 1043 logmemory(malloc_end, NULL, type, size, flags); 1044 return(NULL); 1045 } 1046 1047 /* 1048 * kernel realloc. (SLAB ALLOCATOR) (MP SAFE) 1049 * 1050 * Generally speaking this routine is not called very often and we do 1051 * not attempt to optimize it beyond reusing the same pointer if the 1052 * new size fits within the chunking of the old pointer's zone. 1053 */ 1054 #ifdef SLAB_DEBUG 1055 void * 1056 krealloc_debug(void *ptr, unsigned long size, 1057 struct malloc_type *type, int flags, 1058 const char *file, int line) 1059 #else 1060 void * 1061 krealloc(void *ptr, unsigned long size, struct malloc_type *type, int flags) 1062 #endif 1063 { 1064 unsigned long osize; 1065 unsigned long align; 1066 SLZone *z; 1067 void *nptr; 1068 int *kup; 1069 1070 KKASSERT((flags & M_ZERO) == 0); /* not supported */ 1071 1072 if (ptr == NULL || ptr == ZERO_LENGTH_PTR) 1073 return(kmalloc_debug(size, type, flags, file, line)); 1074 if (size == 0) { 1075 kfree(ptr, type); 1076 return(NULL); 1077 } 1078 1079 /* 1080 * Handle oversized allocations. XXX we really should require that a 1081 * size be passed to free() instead of this nonsense. 1082 */ 1083 kup = btokup(ptr); 1084 if (*kup > 0) { 1085 osize = *kup << PAGE_SHIFT; 1086 if (osize == round_page(size)) 1087 return(ptr); 1088 if ((nptr = kmalloc_debug(size, type, flags, file, line)) == NULL) 1089 return(NULL); 1090 bcopy(ptr, nptr, min(size, osize)); 1091 kfree(ptr, type); 1092 return(nptr); 1093 } 1094 1095 /* 1096 * Get the original allocation's zone. If the new request winds up 1097 * using the same chunk size we do not have to do anything. 1098 */ 1099 z = (SLZone *)((uintptr_t)ptr & ZoneMask); 1100 kup = btokup(z); 1101 KKASSERT(*kup < 0); 1102 KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC); 1103 1104 /* 1105 * Allocate memory for the new request size. Note that zoneindex has 1106 * already adjusted the request size to the appropriate chunk size, which 1107 * should optimize our bcopy(). Then copy and return the new pointer. 1108 * 1109 * Resizing a non-power-of-2 allocation to a power-of-2 size does not 1110 * necessary align the result. 1111 * 1112 * We can only zoneindex (to align size to the chunk size) if the new 1113 * size is not too large. 1114 */ 1115 if (size < ZoneLimit) { 1116 zoneindex(&size, &align); 1117 if (z->z_ChunkSize == size) 1118 return(ptr); 1119 } 1120 if ((nptr = kmalloc_debug(size, type, flags, file, line)) == NULL) 1121 return(NULL); 1122 bcopy(ptr, nptr, min(size, z->z_ChunkSize)); 1123 kfree(ptr, type); 1124 return(nptr); 1125 } 1126 1127 /* 1128 * Return the kmalloc limit for this type, in bytes. 1129 */ 1130 long 1131 kmalloc_limit(struct malloc_type *type) 1132 { 1133 KKASSERT(type->ks_limit != 0); 1134 return(type->ks_limit); 1135 } 1136 1137 /* 1138 * Allocate a copy of the specified string. 1139 * 1140 * (MP SAFE) (MAY BLOCK) 1141 */ 1142 #ifdef SLAB_DEBUG 1143 char * 1144 kstrdup_debug(const char *str, struct malloc_type *type, 1145 const char *file, int line) 1146 #else 1147 char * 1148 kstrdup(const char *str, struct malloc_type *type) 1149 #endif 1150 { 1151 int zlen; /* length inclusive of terminating NUL */ 1152 char *nstr; 1153 1154 if (str == NULL) 1155 return(NULL); 1156 zlen = strlen(str) + 1; 1157 nstr = kmalloc_debug(zlen, type, M_WAITOK, file, line); 1158 bcopy(str, nstr, zlen); 1159 return(nstr); 1160 } 1161 1162 #ifdef SLAB_DEBUG 1163 char * 1164 kstrndup_debug(const char *str, size_t maxlen, struct malloc_type *type, 1165 const char *file, int line) 1166 #else 1167 char * 1168 kstrndup(const char *str, size_t maxlen, struct malloc_type *type) 1169 #endif 1170 { 1171 int zlen; /* length inclusive of terminating NUL */ 1172 char *nstr; 1173 1174 if (str == NULL) 1175 return(NULL); 1176 zlen = strnlen(str, maxlen) + 1; 1177 nstr = kmalloc_debug(zlen, type, M_WAITOK, file, line); 1178 bcopy(str, nstr, zlen); 1179 nstr[zlen - 1] = '\0'; 1180 return(nstr); 1181 } 1182 1183 /* 1184 * Notify our cpu that a remote cpu has freed some chunks in a zone that 1185 * we own. RCount will be bumped so the memory should be good, but validate 1186 * that it really is. 1187 */ 1188 static void 1189 kfree_remote(void *ptr) 1190 { 1191 SLGlobalData *slgd; 1192 SLZone *z; 1193 int nfree; 1194 int *kup; 1195 1196 slgd = &mycpu->gd_slab; 1197 z = ptr; 1198 kup = btokup(z); 1199 KKASSERT(*kup == -((int)mycpuid + 1)); 1200 KKASSERT(z->z_RCount > 0); 1201 atomic_subtract_int(&z->z_RCount, 1); 1202 1203 logmemory(free_rem_beg, z, NULL, 0L, 0); 1204 KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC); 1205 KKASSERT(z->z_Cpu == mycpu->gd_cpuid); 1206 nfree = z->z_NFree; 1207 1208 /* 1209 * Indicate that we will no longer be off of the ZoneAry by 1210 * clearing RSignal. 1211 */ 1212 if (z->z_RChunks) 1213 z->z_RSignal = 0; 1214 1215 /* 1216 * Atomically extract the bchunks list and then process it back 1217 * into the lchunks list. We want to append our bchunks to the 1218 * lchunks list and not prepend since we likely do not have 1219 * cache mastership of the related data (not that it helps since 1220 * we are using c_Next). 1221 */ 1222 clean_zone_rchunks(z); 1223 if (z->z_NFree && nfree == 0) { 1224 TAILQ_INSERT_HEAD(&slgd->ZoneAry[z->z_ZoneIndex], z, z_Entry); 1225 } 1226 1227 check_zone_free(slgd, z); 1228 logmemory(free_rem_end, z, NULL, 0L, 0); 1229 } 1230 1231 /* 1232 * free (SLAB ALLOCATOR) 1233 * 1234 * Free a memory block previously allocated by malloc. 1235 * 1236 * Note: We do not attempt to update ks_loosememuse as MP races could 1237 * prevent us from checking memory limits in malloc. YYY we may 1238 * consider updating ks_cpu.loosememuse. 1239 * 1240 * MPSAFE 1241 */ 1242 void 1243 kfree(void *ptr, struct malloc_type *type) 1244 { 1245 SLZone *z; 1246 SLChunk *chunk; 1247 SLGlobalData *slgd; 1248 struct globaldata *gd; 1249 int *kup; 1250 unsigned long size; 1251 SLChunk *bchunk; 1252 int rsignal; 1253 1254 logmemory_quick(free_beg); 1255 gd = mycpu; 1256 slgd = &gd->gd_slab; 1257 1258 if (ptr == NULL) 1259 panic("trying to free NULL pointer"); 1260 1261 /* 1262 * Handle special 0-byte allocations 1263 */ 1264 if (ptr == ZERO_LENGTH_PTR) { 1265 logmemory(free_zero, ptr, type, -1UL, 0); 1266 logmemory_quick(free_end); 1267 return; 1268 } 1269 1270 /* 1271 * Panic on bad malloc type 1272 */ 1273 if (type->ks_magic != M_MAGIC) 1274 panic("free: malloc type lacks magic"); 1275 1276 /* 1277 * Handle oversized allocations. XXX we really should require that a 1278 * size be passed to free() instead of this nonsense. 1279 * 1280 * This code is never called via an ipi. 1281 */ 1282 kup = btokup(ptr); 1283 if (*kup > 0) { 1284 size = *kup << PAGE_SHIFT; 1285 *kup = 0; 1286 #ifdef INVARIANTS 1287 KKASSERT(sizeof(weirdary) <= size); 1288 bcopy(weirdary, ptr, sizeof(weirdary)); 1289 #endif 1290 /* 1291 * NOTE: For oversized allocations we do not record the 1292 * originating cpu. It gets freed on the cpu calling 1293 * kfree(). The statistics are in aggregate. 1294 * 1295 * note: XXX we have still inherited the interrupts-can't-block 1296 * assumption. An interrupt thread does not bump 1297 * gd_intr_nesting_level so check TDF_INTTHREAD. This is 1298 * primarily until we can fix softupdate's assumptions about free(). 1299 */ 1300 crit_enter(); 1301 --type->ks_use[gd->gd_cpuid].inuse; 1302 type->ks_use[gd->gd_cpuid].memuse -= size; 1303 if (mycpu->gd_intr_nesting_level || 1304 (gd->gd_curthread->td_flags & TDF_INTTHREAD)) { 1305 logmemory(free_ovsz_delayed, ptr, type, size, 0); 1306 z = (SLZone *)ptr; 1307 z->z_Magic = ZALLOC_OVSZ_MAGIC; 1308 z->z_ChunkSize = size; 1309 1310 TAILQ_INSERT_HEAD(&slgd->FreeOvZones, z, z_Entry); 1311 crit_exit(); 1312 } else { 1313 crit_exit(); 1314 logmemory(free_ovsz, ptr, type, size, 0); 1315 kmem_slab_free(ptr, size); /* may block */ 1316 atomic_add_int(&ZoneBigAlloc, -(int)size / 1024); 1317 } 1318 logmemory_quick(free_end); 1319 return; 1320 } 1321 1322 /* 1323 * Zone case. Figure out the zone based on the fact that it is 1324 * ZoneSize aligned. 1325 */ 1326 z = (SLZone *)((uintptr_t)ptr & ZoneMask); 1327 kup = btokup(z); 1328 KKASSERT(*kup < 0); 1329 KKASSERT(z->z_Magic == ZALLOC_SLAB_MAGIC); 1330 1331 /* 1332 * If we do not own the zone then use atomic ops to free to the 1333 * remote cpu linked list and notify the target zone using a 1334 * passive message. 1335 * 1336 * The target zone cannot be deallocated while we own a chunk of it, 1337 * so the zone header's storage is stable until the very moment 1338 * we adjust z_RChunks. After that we cannot safely dereference (z). 1339 * 1340 * (no critical section needed) 1341 */ 1342 if (z->z_CpuGd != gd) { 1343 /* 1344 * Making these adjustments now allow us to avoid passing (type) 1345 * to the remote cpu. Note that inuse/memuse is being 1346 * adjusted on OUR cpu, not the zone cpu, but it should all still 1347 * sum up properly and cancel out. 1348 */ 1349 crit_enter(); 1350 --type->ks_use[gd->gd_cpuid].inuse; 1351 type->ks_use[gd->gd_cpuid].memuse -= z->z_ChunkSize; 1352 crit_exit(); 1353 1354 /* 1355 * WARNING! This code competes with other cpus. Once we 1356 * successfully link the chunk to RChunks the remote 1357 * cpu can rip z's storage out from under us. 1358 * 1359 * Bumping RCount prevents z's storage from getting 1360 * ripped out. 1361 */ 1362 rsignal = z->z_RSignal; 1363 cpu_lfence(); 1364 if (rsignal) 1365 atomic_add_int(&z->z_RCount, 1); 1366 1367 chunk = ptr; 1368 for (;;) { 1369 bchunk = z->z_RChunks; 1370 cpu_ccfence(); 1371 chunk->c_Next = bchunk; 1372 cpu_sfence(); 1373 1374 if (atomic_cmpset_ptr(&z->z_RChunks, bchunk, chunk)) 1375 break; 1376 } 1377 1378 /* 1379 * We have to signal the remote cpu if our actions will cause 1380 * the remote zone to be placed back on ZoneAry so it can 1381 * move the zone back on. 1382 * 1383 * We only need to deal with NULL->non-NULL RChunk transitions 1384 * and only if z_RSignal is set. We interlock by reading rsignal 1385 * before adding our chunk to RChunks. This should result in 1386 * virtually no IPI traffic. 1387 * 1388 * We can use a passive IPI to reduce overhead even further. 1389 */ 1390 if (bchunk == NULL && rsignal) { 1391 logmemory(free_request, ptr, type, 1392 (unsigned long)z->z_ChunkSize, 0); 1393 lwkt_send_ipiq_passive(z->z_CpuGd, kfree_remote, z); 1394 /* z can get ripped out from under us from this point on */ 1395 } else if (rsignal) { 1396 atomic_subtract_int(&z->z_RCount, 1); 1397 /* z can get ripped out from under us from this point on */ 1398 } 1399 logmemory_quick(free_end); 1400 return; 1401 } 1402 1403 /* 1404 * kfree locally 1405 */ 1406 logmemory(free_chunk, ptr, type, (unsigned long)z->z_ChunkSize, 0); 1407 1408 crit_enter(); 1409 chunk = ptr; 1410 chunk_mark_free(z, chunk); 1411 1412 /* 1413 * Put weird data into the memory to detect modifications after freeing, 1414 * illegal pointer use after freeing (we should fault on the odd address), 1415 * and so forth. XXX needs more work, see the old malloc code. 1416 */ 1417 #ifdef INVARIANTS 1418 if (z->z_ChunkSize < sizeof(weirdary)) 1419 bcopy(weirdary, chunk, z->z_ChunkSize); 1420 else 1421 bcopy(weirdary, chunk, sizeof(weirdary)); 1422 #endif 1423 1424 /* 1425 * Add this free non-zero'd chunk to a linked list for reuse. Add 1426 * to the front of the linked list so it is more likely to be 1427 * reallocated, since it is already in our L1 cache. 1428 */ 1429 #ifdef INVARIANTS 1430 if ((vm_offset_t)chunk < KvaStart || (vm_offset_t)chunk >= KvaEnd) 1431 panic("BADFREE %p", chunk); 1432 #endif 1433 chunk->c_Next = z->z_LChunks; 1434 z->z_LChunks = chunk; 1435 if (chunk->c_Next == NULL) 1436 z->z_LChunksp = &chunk->c_Next; 1437 1438 #ifdef INVARIANTS 1439 if (chunk->c_Next && (vm_offset_t)chunk->c_Next < KvaStart) 1440 panic("BADFREE2"); 1441 #endif 1442 1443 /* 1444 * Bump the number of free chunks. If it becomes non-zero the zone 1445 * must be added back onto the appropriate list. A fully allocated 1446 * zone that sees its first free is considered 'mature' and is placed 1447 * at the head, giving the system time to potentially free the remaining 1448 * entries even while other allocations are going on and making the zone 1449 * freeable. 1450 */ 1451 if (z->z_NFree++ == 0) { 1452 if (SlabFreeToTail) 1453 TAILQ_INSERT_TAIL(&slgd->ZoneAry[z->z_ZoneIndex], z, z_Entry); 1454 else 1455 TAILQ_INSERT_HEAD(&slgd->ZoneAry[z->z_ZoneIndex], z, z_Entry); 1456 } 1457 1458 --type->ks_use[gd->gd_cpuid].inuse; 1459 type->ks_use[gd->gd_cpuid].memuse -= z->z_ChunkSize; 1460 1461 check_zone_free(slgd, z); 1462 logmemory_quick(free_end); 1463 crit_exit(); 1464 } 1465 1466 /* 1467 * Cleanup slabs which are hanging around due to RChunks or which are wholely 1468 * free and can be moved to the free list if not moved by other means. 1469 * 1470 * Called once every 10 seconds on all cpus. 1471 */ 1472 void 1473 slab_cleanup(void) 1474 { 1475 SLGlobalData *slgd = &mycpu->gd_slab; 1476 SLZone *z; 1477 int i; 1478 1479 crit_enter(); 1480 for (i = 0; i < NZONES; ++i) { 1481 if ((z = TAILQ_FIRST(&slgd->ZoneAry[i])) == NULL) 1482 continue; 1483 1484 /* 1485 * Scan zones. 1486 */ 1487 while (z) { 1488 /* 1489 * Shift all RChunks to the end of the LChunks list. This is 1490 * an O(1) operation. 1491 * 1492 * Then free the zone if possible. 1493 */ 1494 clean_zone_rchunks(z); 1495 z = check_zone_free(slgd, z); 1496 } 1497 } 1498 crit_exit(); 1499 } 1500 1501 #if defined(INVARIANTS) 1502 1503 /* 1504 * Helper routines for sanity checks 1505 */ 1506 static void 1507 chunk_mark_allocated(SLZone *z, void *chunk) 1508 { 1509 int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize; 1510 uint32_t *bitptr; 1511 1512 KKASSERT((((intptr_t)chunk ^ (intptr_t)z) & ZoneMask) == 0); 1513 KASSERT(bitdex >= 0 && bitdex < z->z_NMax, 1514 ("memory chunk %p bit index %d is illegal", chunk, bitdex)); 1515 bitptr = &z->z_Bitmap[bitdex >> 5]; 1516 bitdex &= 31; 1517 KASSERT((*bitptr & (1 << bitdex)) == 0, 1518 ("memory chunk %p is already allocated!", chunk)); 1519 *bitptr |= 1 << bitdex; 1520 } 1521 1522 static void 1523 chunk_mark_free(SLZone *z, void *chunk) 1524 { 1525 int bitdex = ((char *)chunk - (char *)z->z_BasePtr) / z->z_ChunkSize; 1526 uint32_t *bitptr; 1527 1528 KKASSERT((((intptr_t)chunk ^ (intptr_t)z) & ZoneMask) == 0); 1529 KASSERT(bitdex >= 0 && bitdex < z->z_NMax, 1530 ("memory chunk %p bit index %d is illegal!", chunk, bitdex)); 1531 bitptr = &z->z_Bitmap[bitdex >> 5]; 1532 bitdex &= 31; 1533 KASSERT((*bitptr & (1 << bitdex)) != 0, 1534 ("memory chunk %p is already free!", chunk)); 1535 *bitptr &= ~(1 << bitdex); 1536 } 1537 1538 #endif 1539 1540 /* 1541 * kmem_slab_alloc() 1542 * 1543 * Directly allocate and wire kernel memory in PAGE_SIZE chunks with the 1544 * specified alignment. M_* flags are expected in the flags field. 1545 * 1546 * Alignment must be a multiple of PAGE_SIZE. 1547 * 1548 * NOTE! XXX For the moment we use vm_map_entry_reserve/release(), 1549 * but when we move zalloc() over to use this function as its backend 1550 * we will have to switch to kreserve/krelease and call reserve(0) 1551 * after the new space is made available. 1552 * 1553 * Interrupt code which has preempted other code is not allowed to 1554 * use PQ_CACHE pages. However, if an interrupt thread is run 1555 * non-preemptively or blocks and then runs non-preemptively, then 1556 * it is free to use PQ_CACHE pages. <--- may not apply any longer XXX 1557 */ 1558 static void * 1559 kmem_slab_alloc(vm_size_t size, vm_offset_t align, int flags) 1560 { 1561 vm_size_t i; 1562 vm_offset_t addr; 1563 int count, vmflags, base_vmflags; 1564 vm_page_t mbase = NULL; 1565 vm_page_t m; 1566 thread_t td; 1567 1568 size = round_page(size); 1569 addr = vm_map_min(&kernel_map); 1570 1571 count = vm_map_entry_reserve(MAP_RESERVE_COUNT); 1572 crit_enter(); 1573 vm_map_lock(&kernel_map); 1574 if (vm_map_findspace(&kernel_map, addr, size, align, 0, &addr)) { 1575 vm_map_unlock(&kernel_map); 1576 if ((flags & M_NULLOK) == 0) 1577 panic("kmem_slab_alloc(): kernel_map ran out of space!"); 1578 vm_map_entry_release(count); 1579 crit_exit(); 1580 return(NULL); 1581 } 1582 1583 /* 1584 * kernel_object maps 1:1 to kernel_map. 1585 */ 1586 vm_object_hold(&kernel_object); 1587 vm_object_reference_locked(&kernel_object); 1588 vm_map_insert(&kernel_map, &count, 1589 &kernel_object, NULL, 1590 addr, NULL, 1591 addr, addr + size, 1592 VM_MAPTYPE_NORMAL, 1593 VM_SUBSYS_KMALLOC, 1594 VM_PROT_ALL, VM_PROT_ALL, 0); 1595 vm_object_drop(&kernel_object); 1596 vm_map_set_wired_quick(&kernel_map, addr, size, &count); 1597 vm_map_unlock(&kernel_map); 1598 1599 td = curthread; 1600 1601 base_vmflags = 0; 1602 if (flags & M_ZERO) 1603 base_vmflags |= VM_ALLOC_ZERO; 1604 if (flags & M_USE_RESERVE) 1605 base_vmflags |= VM_ALLOC_SYSTEM; 1606 if (flags & M_USE_INTERRUPT_RESERVE) 1607 base_vmflags |= VM_ALLOC_INTERRUPT; 1608 if ((flags & (M_RNOWAIT|M_WAITOK)) == 0) { 1609 panic("kmem_slab_alloc: bad flags %08x (%p)", 1610 flags, ((int **)&size)[-1]); 1611 } 1612 1613 /* 1614 * Allocate the pages. Do not map them yet. VM_ALLOC_NORMAL can only 1615 * be set if we are not preempting. 1616 * 1617 * VM_ALLOC_SYSTEM is automatically set if we are preempting and 1618 * M_WAITOK was specified as an alternative (i.e. M_USE_RESERVE is 1619 * implied in this case), though I'm not sure if we really need to 1620 * do that. 1621 */ 1622 vmflags = base_vmflags; 1623 if (flags & M_WAITOK) { 1624 if (td->td_preempted) 1625 vmflags |= VM_ALLOC_SYSTEM; 1626 else 1627 vmflags |= VM_ALLOC_NORMAL; 1628 } 1629 1630 vm_object_hold(&kernel_object); 1631 for (i = 0; i < size; i += PAGE_SIZE) { 1632 m = vm_page_alloc(&kernel_object, OFF_TO_IDX(addr + i), vmflags); 1633 if (i == 0) 1634 mbase = m; 1635 1636 /* 1637 * If the allocation failed we either return NULL or we retry. 1638 * 1639 * If M_WAITOK is specified we wait for more memory and retry. 1640 * If M_WAITOK is specified from a preemption we yield instead of 1641 * wait. Livelock will not occur because the interrupt thread 1642 * will not be preempting anyone the second time around after the 1643 * yield. 1644 */ 1645 if (m == NULL) { 1646 if (flags & M_WAITOK) { 1647 if (td->td_preempted) { 1648 lwkt_switch(); 1649 } else { 1650 vm_wait(0); 1651 } 1652 i -= PAGE_SIZE; /* retry */ 1653 continue; 1654 } 1655 break; 1656 } 1657 } 1658 1659 /* 1660 * Check and deal with an allocation failure 1661 */ 1662 if (i != size) { 1663 while (i != 0) { 1664 i -= PAGE_SIZE; 1665 m = vm_page_lookup(&kernel_object, OFF_TO_IDX(addr + i)); 1666 /* page should already be busy */ 1667 vm_page_free(m); 1668 } 1669 vm_map_lock(&kernel_map); 1670 vm_map_delete(&kernel_map, addr, addr + size, &count); 1671 vm_map_unlock(&kernel_map); 1672 vm_object_drop(&kernel_object); 1673 1674 vm_map_entry_release(count); 1675 crit_exit(); 1676 return(NULL); 1677 } 1678 1679 /* 1680 * Success! 1681 * 1682 * NOTE: The VM pages are still busied. mbase points to the first one 1683 * but we have to iterate via vm_page_next() 1684 */ 1685 vm_object_drop(&kernel_object); 1686 crit_exit(); 1687 1688 /* 1689 * Enter the pages into the pmap and deal with M_ZERO. 1690 */ 1691 m = mbase; 1692 i = 0; 1693 1694 while (i < size) { 1695 /* 1696 * page should already be busy 1697 */ 1698 m->valid = VM_PAGE_BITS_ALL; 1699 vm_page_wire(m); 1700 pmap_enter(&kernel_pmap, addr + i, m, 1701 VM_PROT_ALL | VM_PROT_NOSYNC, 1, NULL); 1702 if (flags & M_ZERO) 1703 pagezero((char *)addr + i); 1704 KKASSERT(m->flags & (PG_WRITEABLE | PG_MAPPED)); 1705 vm_page_flag_set(m, PG_REFERENCED); 1706 vm_page_wakeup(m); 1707 1708 i += PAGE_SIZE; 1709 vm_object_hold(&kernel_object); 1710 m = vm_page_next(m); 1711 vm_object_drop(&kernel_object); 1712 } 1713 smp_invltlb(); 1714 vm_map_entry_release(count); 1715 atomic_add_long(&SlabsAllocated, 1); 1716 return((void *)addr); 1717 } 1718 1719 /* 1720 * kmem_slab_free() 1721 */ 1722 static void 1723 kmem_slab_free(void *ptr, vm_size_t size) 1724 { 1725 crit_enter(); 1726 vm_map_remove(&kernel_map, (vm_offset_t)ptr, (vm_offset_t)ptr + size); 1727 atomic_add_long(&SlabsFreed, 1); 1728 crit_exit(); 1729 } 1730