sys/kern/kern_kmalloc.c

   1 /*
   2  * KERN_KMALLOC.C       - Kernel memory allocator
   3  *
   4  * Copyright (c) 2021 The DragonFly Project, All rights reserved.
   5  *
   6  * This code is derived from software contributed to The DragonFly Project
   7  * by Matthew Dillon <dillon@backplane.com>
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  * 3. Neither the name of The DragonFly Project nor the names of its
  20  *    contributors may be used to endorse or promote products derived
  21  *    from this software without specific, prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  27  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  31  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  32  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  33  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 /*
  38  * This module implements the kmalloc_obj allocator.  This is a type-stable
  39  * allocator that uses the same base structures (e.g. malloc_type) plus
  40  * some extensions to efficiently implement single-type zones.
  41  *
  42  * All memory management is zone based.  When a zone is destroyed, all of
  43  * its memory is returned to the system with no fragmentation.
  44  *
  45  * A mini-slab allocator hangs directly off the zone structure (malloc_type).
  46  * Since the object zones are single-size-only, the slab allocator is very
  47  * simple and currently utilizes just two per-zone/per-cpu slabs (active and
  48  * alternate) before kicking up to the per-zone cache.  Beyond that we just
  49  * have the per-cpu globaldata-based 'free slab' cache to avoid unnecessary
  50  * kernel_map mappings and unmappings.
  51  *
  52  * The advantage of this that zones don't stomp over each other and cause
  53  * excessive fragmentation in the slabs.  For example, when you umount a
  54  * large tmpfs filesystem, most of its memory (all of its kmalloc_obj memory)
  55  * is returned to the system.
  56  */
  57
  58 #include "opt_vm.h"
  59
  60 #include <sys/param.h>
  61 #include <sys/systm.h>
  62 #include <sys/kernel.h>
  63 #include <sys/slaballoc.h>
  64 #include <sys/mbuf.h>
  65 #include <sys/vmmeter.h>
  66 #include <sys/spinlock.h>
  67 #include <sys/lock.h>
  68 #include <sys/thread.h>
  69 #include <sys/globaldata.h>
  70 #include <sys/sysctl.h>
  71 #include <sys/ktr.h>
  72 #include <sys/malloc.h>
  73
  74 #include <vm/vm.h>
  75 #include <vm/vm_param.h>
  76 #include <vm/vm_kern.h>
  77 #include <vm/vm_extern.h>
  78 #include <vm/vm_object.h>
  79 #include <vm/pmap.h>
  80 #include <vm/vm_map.h>
  81 #include <vm/vm_page.h>
  82 #include <vm/vm_pageout.h>
  83
  84 #include <machine/cpu.h>
  85
  86 #include <sys/spinlock2.h>
  87 #include <sys/thread2.h>
  88 #include <sys/exislock2.h>
  89 #include <vm/vm_page2.h>
  90
  91 #define MEMORY_STRING   "ptr=%p type=%p size=%lu flags=%04x"
  92 #define MEMORY_ARGS     void *ptr, void *type, unsigned long size, int flags
  93
  94 #if !defined(KTR_MEMORY)
  95 #define KTR_MEMORY      KTR_ALL
  96 #endif
  97 KTR_INFO_MASTER(mem_obj);
  98 KTR_INFO(KTR_MEMORY, mem_obj, malloc_beg, 0, "kmalloc_obj begin");
  99 KTR_INFO(KTR_MEMORY, mem_obj, malloc_end, 1, MEMORY_STRING, MEMORY_ARGS);
 100 #if 0
 101 KTR_INFO(KTR_MEMORY, mem_obj, free_zero, 2, MEMORY_STRING, MEMORY_ARGS);
 102 KTR_INFO(KTR_MEMORY, mem_obj, free_ovsz, 3, MEMORY_STRING, MEMORY_ARGS);
 103 KTR_INFO(KTR_MEMORY, mem_obj, free_ovsz_delayed, 4, MEMORY_STRING, MEMORY_ARGS);
 104 KTR_INFO(KTR_MEMORY, mem_obj, free_chunk, 5, MEMORY_STRING, MEMORY_ARGS);
 105 KTR_INFO(KTR_MEMORY, mem_obj, free_request, 6, MEMORY_STRING, MEMORY_ARGS);
 106 KTR_INFO(KTR_MEMORY, mem_obj, free_rem_beg, 7, MEMORY_STRING, MEMORY_ARGS);
 107 KTR_INFO(KTR_MEMORY, mem_obj, free_rem_end, 8, MEMORY_STRING, MEMORY_ARGS);
 108 #endif
 109 KTR_INFO(KTR_MEMORY, mem_obj, free_beg, 9, "kfree_obj begin");
 110 KTR_INFO(KTR_MEMORY, mem_obj, free_end, 10, "kfree_obj end");
 111
 112 #define logmemory(name, ptr, type, size, flags)                         \
 113         KTR_LOG(mem_obj_ ## name, ptr, type, size, flags)
 114 #define logmemory_quick(name)                                           \
 115         KTR_LOG(mem_obj_ ## name)
 116
 117 __read_frequently static int KMGDMaxFreeSlabs = KMGD_MAXFREESLABS;
 118 SYSCTL_INT(_kern, OID_AUTO, kzone_cache, CTLFLAG_RW, &KMGDMaxFreeSlabs, 0, "");
 119 __read_frequently static int kzone_debug;
 120 SYSCTL_INT(_kern, OID_AUTO, kzone_debug, CTLFLAG_RW, &kzone_debug, 0, "");
 121
 122 __read_frequently struct kmalloc_slab kslab_dummy;
 123
 124 static void malloc_slab_destroy(struct malloc_type *type,
 125                         struct kmalloc_slab **slabp);
 126
 127 /*
 128  * Cache a chain of slabs onto their respective cpu slab caches.  Any slabs
 129  * which we cannot cache will be returned.
 130  *
 131  * free_slabs        - Current structure may only be accessed by current cpu
 132  * remote_free_slabs - Only atomic swap operations are allowed.
 133  * free_count        - Only atomic operations are allowed.
 134  *
 135  * If the count is sufficient to cache the entire list, NULL is returned.
 136  * Otherwise the portion that was not cached is returned.
 137  */
 138 static __noinline
 139 struct kmalloc_slab *
 140 gslab_cache(struct kmalloc_slab *slab)
 141 {
 142         struct kmalloc_slab *save;
 143         struct kmalloc_slab *next;
 144         struct kmalloc_slab *res;
 145         struct kmalloc_slab **resp;
 146         struct kmalloc_slab **slabp;
 147         globaldata_t rgd;
 148         size_t count;
 149         int cpuid;
 150
 151         res = NULL;
 152         resp = &res;
 153         KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 154
 155         /*
 156          * Given the slab list, get the cpuid and clip off as many matching
 157          * elements as fits in the cache.
 158          */
 159         while (slab) {
 160                 cpuid = slab->orig_cpuid;
 161                 rgd = globaldata_find(cpuid);
 162
 163                 KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 164                 /*
 165                  * Doesn't fit in cache, put on return list.
 166                  */
 167                 if (rgd->gd_kmslab.free_count >= KMGDMaxFreeSlabs) {
 168                         *resp = slab;
 169                         resp = &slab->next;
 170                         slab = slab->next;
 171                         continue;
 172                 }
 173
 174                 /*
 175                  * Collect.  We aren't required to match-up the original cpu
 176                  * with the disposal cpu, but its a good idea to retain
 177                  * memory locality.
 178                  *
 179                  * The slabs we collect are going into the global cache,
 180                  * remove the type association.
 181                  */
 182                 KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 183                 slabp = &slab->next;
 184                 count = 1;
 185                 slab->type = NULL;
 186
 187                 while ((next = *slabp) != NULL &&
 188                        next->orig_cpuid == cpuid &&
 189                        rgd->gd_kmslab.free_count + count < KMGDMaxFreeSlabs)
 190                 {
 191                         KKASSERT(((uintptr_t)next & KMALLOC_SLAB_MASK) == 0);
 192                         next->type = NULL;
 193                         ++count;
 194                         slabp = &next->next;
 195                 }
 196
 197                 /*
 198                  * Safety, unhook before next, next is not included in the
 199                  * list starting with slab that is being pre-pended
 200                  * to remote_free_slabs.
 201                  */
 202                 *slabp = NULL;
 203
 204                 /*
 205                  * Now atomically pre-pend slab...*slabp to remote_free_slabs.
 206                  * Pump the count first (its ok if the actual chain length
 207                  * races the count update).
 208                  *
 209                  * NOTE: In the loop, (save) is updated by fcmpset.
 210                  */
 211                 atomic_add_long(&rgd->gd_kmslab.free_count, count);
 212                 save = rgd->gd_kmslab.remote_free_slabs;
 213                 for (;;) {
 214                         KKASSERT(((uintptr_t)save & KMALLOC_SLAB_MASK) == 0);
 215                         *slabp = save;  /* end of slab list chain to... */
 216                         cpu_ccfence();
 217                         if (atomic_fcmpset_ptr(
 218                                 &rgd->gd_kmslab.remote_free_slabs,
 219                                 &save, slab))
 220                         {
 221                                 break;
 222                         }
 223                 }
 224
 225                 /*
 226                  * Setup for next loop
 227                  */
 228                 slab = next;
 229         }
 230
 231         /*
 232          * Terminate the result list and return it
 233          */
 234         *resp = NULL;
 235
 236         return res;
 237 }
 238
 239 /*
 240  * May only be called on current cpu.  Pull a free slab from the
 241  * pcpu cache.  If we run out, move any slabs that have built-up
 242  * from remote cpus.
 243  *
 244  * We are only allowed to swap the remote_free_slabs head, we cannot
 245  * manipulate any next pointers while structures are sitting on that list.
 246  */
 247 static __inline
 248 struct kmalloc_slab *
 249 gslab_alloc(globaldata_t gd)
 250 {
 251         struct kmalloc_slab *slab;
 252
 253         slab = gd->gd_kmslab.free_slabs;
 254         if (slab == NULL) {
 255                 slab = atomic_swap_ptr(
 256                         (volatile void **)&gd->gd_kmslab.remote_free_slabs,
 257                         NULL);
 258                 KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 259         }
 260         if (slab) {
 261                 gd->gd_kmslab.free_slabs = slab->next;
 262                 slab->next = NULL;
 263                 atomic_add_long(&gd->gd_kmslab.free_count, -1);
 264                 KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 265         }
 266         return slab;
 267 }
 268
 269 void
 270 malloc_mgt_init(struct malloc_type *type __unused,
 271                 struct kmalloc_mgt *mgt, size_t size)
 272 {
 273         size_t offset;
 274         size_t count;
 275
 276         bzero(mgt, sizeof(*mgt));
 277         spin_init(&mgt->spin, "kmmgt");
 278
 279         /*
 280          * Allows us to avoid a conditional.  The dummy slabs are empty
 281          * and have no objects.
 282          */
 283         mgt->active = &kslab_dummy;
 284         mgt->alternate = &kslab_dummy;
 285         mgt->empty_tailp = &mgt->empty;
 286
 287         /*
 288          * Figure out the count by taking into account the size of the fobjs[]
 289          * array by adding it to the object size.
 290          */
 291         offset = offsetof(struct kmalloc_slab, fobjs[0]);
 292         offset = __VM_CACHELINE_ALIGN(offset);
 293         count = (KMALLOC_SLAB_SIZE - offset) / (size + sizeof(void *));
 294
 295         /*
 296          * However, the fobj[] array itself must be aligned, so we might
 297          * have to reduce the count by 1.  (We can do this becaues 'size'
 298          * is already aligned as well).
 299          */
 300         offset = offsetof(struct kmalloc_slab, fobjs[count]);
 301         offset = __VM_CACHELINE_ALIGN(offset);
 302
 303         if (offset + size * count > KMALLOC_SLAB_SIZE) {
 304                 --count;
 305                 offset = offsetof(struct kmalloc_slab, fobjs[count]);
 306                 offset = __VM_CACHELINE_ALIGN(offset);
 307                 KKASSERT (offset + size * count <= KMALLOC_SLAB_SIZE);
 308         }
 309
 310         mgt->slab_offset = offset;
 311         mgt->slab_count  = count;
 312 }
 313
 314 void
 315 malloc_mgt_relocate(struct kmalloc_mgt *src, struct kmalloc_mgt *dst)
 316 {
 317         struct kmalloc_slab **slabp;
 318
 319         spin_init(&dst->spin, "kmmgt");
 320         slabp = &dst->empty;
 321
 322         while (*slabp) {
 323                 slabp = &(*slabp)->next;
 324         }
 325         dst->empty_tailp = slabp;
 326 }
 327
 328 void
 329 malloc_mgt_uninit(struct malloc_type *type, struct kmalloc_mgt *mgt)
 330 {
 331         if (mgt->active != &kslab_dummy)
 332                 malloc_slab_destroy(type, &mgt->active);
 333         mgt->active = NULL;
 334
 335         if (mgt->alternate != &kslab_dummy)
 336                 malloc_slab_destroy(type, &mgt->alternate);
 337         mgt->alternate = NULL;
 338
 339         malloc_slab_destroy(type, &mgt->partial);
 340         malloc_slab_destroy(type, &mgt->full);
 341         malloc_slab_destroy(type, &mgt->empty);
 342         mgt->npartial = 0;
 343         mgt->nfull = 0;
 344         mgt->nempty = 0;
 345         mgt->empty_tailp = &mgt->empty;
 346
 347         spin_uninit(&mgt->spin);
 348 }
 349
 350 /*
 351  * Destroy a list of slabs.  Attempt to cache the slabs on the specified
 352  * (possibly remote) cpu.  This allows slabs that were operating on a
 353  * particular cpu to be disposed of back to that same cpu.
 354  */
 355 static void
 356 malloc_slab_destroy(struct malloc_type *type, struct kmalloc_slab **slabp)
 357 {
 358         struct kmalloc_slab *slab;
 359         struct kmalloc_slab *base;
 360         struct kmalloc_slab **basep;
 361         size_t delta;
 362
 363         if (*slabp == NULL)
 364                 return;
 365
 366         /*
 367          * Collect all slabs that can actually be destroyed, complain
 368          * about the rest.
 369          */
 370         base = NULL;
 371         basep = &base;
 372         while ((slab = *slabp) != NULL) {
 373                 KKASSERT(((uintptr_t)slab & KMALLOC_SLAB_MASK) == 0);
 374
 375                 delta = slab->findex - slab->aindex;
 376                 if (delta == slab->ncount) {
 377                         *slabp = slab->next;    /* unlink */
 378                         *basep = slab;          /* link into base list */
 379                         basep = &slab->next;
 380                 } else {
 381                         kprintf("%s: slab %p %zd objects "
 382                                 "were still allocated\n",
 383                                 type->ks_shortdesc, slab,
 384                                 slab->ncount - delta);
 385                         /* leave link intact and iterate */
 386                         slabp = &slab->next;
 387                 }
 388         }
 389
 390         /*
 391          * Terminate the base list of slabs that can be destroyed,
 392          * then cache as many of them as possible.
 393          */
 394         *basep = NULL;
 395         if (base == NULL)
 396                 return;
 397         base = gslab_cache(base);
 398
 399         /*
 400          * Destroy the remainder
 401          */
 402         while ((slab = base) != NULL) {
 403                 base = slab->next;
 404                 slab->next = (void *)(uintptr_t)-1;
 405                 kmem_slab_free(slab, KMALLOC_SLAB_SIZE);
 406         }
 407 }
 408
 409 /*
 410  * Poll a limited number of slabs on the empty list and move them
 411  * to the appropriate full or partial list.  Slabs left on the empty
 412  * list or rotated to the tail.
 413  *
 414  * If gcache is non-zero this function will try to place full slabs into
 415  * the globaldata cache, if it isn't already too full.
 416  *
 417  * The mgt is spin-locked
 418  *
 419  * Returns non-zero if the ggm updates possibly made slabs available for
 420  * allocation.
 421  */
 422 static int
 423 malloc_mgt_poll_empty_locked(struct kmalloc_mgt *ggm, int count)
 424 {
 425         struct kmalloc_slab *marker;
 426         struct kmalloc_slab *slab;
 427         size_t delta;
 428         int got_something;
 429
 430         if (ggm->empty == NULL)
 431                 return 0;
 432
 433         got_something = 0;
 434         marker = ggm->empty;
 435
 436         while (count-- && (slab = ggm->empty) != NULL) {
 437                 /*
 438                  * Unlink from empty
 439                  */
 440                 ggm->empty = slab->next;
 441                 slab->next = NULL;
 442                 --ggm->nempty;
 443                 if (ggm->empty_tailp == &slab->next)
 444                         ggm->empty_tailp = &ggm->empty;
 445
 446                 /*
 447                  * Check partial, full, and empty.  We rotate
 448                  * empty entries to the end of the empty list.
 449                  *
 450                  * NOTE: For a fully-freeable slab we also have
 451                  *       to check xindex.
 452                  */
 453                 delta = slab->findex - slab->aindex;
 454                 if (delta == slab->ncount) {
 455                         /*
 456                          * Stuff into the full list.  This requires setting
 457                          * the exis sequence number via exis_terminate().
 458                          */
 459                         KKASSERT(slab->next == NULL);
 460                         exis_terminate(&slab->exis);
 461                         slab->next = ggm->full;
 462                         ggm->full = slab;
 463                         got_something = 1;
 464                         ++ggm->nfull;
 465                 } else if (delta) {
 466                         /*
 467                          * Partially full
 468                          */
 469                         KKASSERT(slab->next == NULL);
 470                         slab->next = ggm->partial;
 471                         ggm->partial = slab;
 472                         got_something = 1;
 473                         ++ggm->npartial;
 474                 } else {
 475                         /*
 476                          * Empty
 477                          */
 478                         KKASSERT(slab->next == NULL);
 479                         *ggm->empty_tailp = slab;
 480                         ggm->empty_tailp = &slab->next;
 481                         ++ggm->nempty;
 482                         if (ggm->empty == marker)
 483                                 break;
 484                 }
 485         }
 486         return got_something;
 487 }
 488
 489 /*
 490  * Called once a second with the zone interlocked against destruction.
 491  *
 492  * Returns non-zero to tell the caller to iterate to the next type,
 493  * else the caller should stay on the current type.
 494  */
 495 int
 496 malloc_mgt_poll(struct malloc_type *type)
 497 {
 498         struct kmalloc_mgt *ggm;
 499         struct kmalloc_slab *slab;
 500         struct kmalloc_slab **slabp;
 501         struct kmalloc_slab *base;
 502         struct kmalloc_slab **basep;
 503         size_t delta;
 504         int donext;
 505         int count;
 506         int retired;
 507
 508         if ((type->ks_flags & KSF_OBJSIZE) == 0)
 509                 return 1;
 510
 511         /*
 512          * Check the partial, full, and empty lists for full freeable slabs
 513          * in excess of desired caching count.
 514          */
 515         ggm = &type->ks_mgt;
 516         spin_lock(&ggm->spin);
 517
 518         /*
 519          * Move empty slabs to partial or full as appropriate.  We
 520          * don't bother checking partial slabs to see if they are full
 521          * for now.
 522          */
 523         malloc_mgt_poll_empty_locked(ggm, 16);
 524
 525         /*
 526          * Ok, cleanout some of the full mags from the full list
 527          */
 528         base = NULL;
 529         basep = &base;
 530         count = ggm->nfull;
 531         retired = 0;
 532         cpu_ccfence();
 533
 534         if (count > KMALLOC_MAXFREEMAGS) {
 535                 slabp = &ggm->full;
 536                 count -= KMALLOC_MAXFREEMAGS;
 537                 if (count > 16)
 538                         count = 16;
 539
 540                 while (count && (slab = *slabp) != NULL) {
 541                         delta = slab->findex - slab->aindex;
 542                         if (delta == slab->ncount &&
 543                             slab->xindex == slab->findex &&
 544                             exis_freeable(&slab->exis))
 545                         {
 546                                 /*
 547                                  * (1) No allocated entries in the structure,
 548                                  *     this should always be the case from the
 549                                  *     full list.
 550                                  *
 551                                  * (2) kfree_obj() has fully completed.  Just
 552                                  *     checking findex is not sufficient since
 553                                  *     it is incremented to reserve the slot
 554                                  *     before the element is loaded into it.
 555                                  *
 556                                  * (3) The slab has been on the full list for
 557                                  *     a sufficient number of EXIS
 558                                  *     pseudo_ticks, for type-safety.
 559                                  */
 560                                 *slabp = slab->next;
 561                                 *basep = slab;
 562                                 basep = &slab->next;
 563                                 --ggm->nfull;
 564                                 if (++retired == 4)
 565                                         break;
 566                         } else {
 567                                 slabp = &slab->next;
 568                         }
 569                         --count;
 570                 }
 571                 *basep = NULL;  /* terminate the retirement list */
 572                 donext = (*slabp == NULL);
 573         } else {
 574                 donext = 1;
 575         }
 576         spin_unlock(&ggm->spin);
 577
 578         /*
 579          * Clean out any slabs that we couldn't stow in the globaldata cache.
 580          */
 581         if (retired) {
 582                 if (kzone_debug) {
 583                         kprintf("kmalloc_poll: %s retire %d\n",
 584                                 type->ks_shortdesc, retired);
 585                 }
 586                 base = gslab_cache(base);
 587                 while ((slab = base) != NULL) {
 588                         base = base->next;
 589                         slab->next = NULL;
 590                         kmem_slab_free(slab, KMALLOC_SLAB_SIZE);
 591                 }
 592         }
 593
 594         return donext;
 595 }
 596
 597 /*
 598  * Optional bitmap double-free check.  This is typically turned on by
 599  * default for safety (sys/_malloc.h)
 600  */
 601 #ifdef KMALLOC_CHECK_DOUBLE_FREE
 602
 603 static __inline void
 604 bmap_set(struct kmalloc_slab *slab, void *obj)
 605 {
 606         uint64_t *ptr;
 607         uint64_t mask;
 608         size_t i = (((uintptr_t)obj & KMALLOC_SLAB_MASK) - slab->offset) /
 609                    slab->objsize;
 610
 611         ptr = &slab->bmap[i >> 6];
 612         mask = (uint64_t)1U << (i & 63);
 613         KKASSERT(i < slab->ncount && (*ptr & mask) == 0);
 614         atomic_set_64(ptr, mask);
 615 }
 616
 617 static __inline void
 618 bmap_clr(struct kmalloc_slab *slab, void *obj)
 619 {
 620         uint64_t *ptr;
 621         uint64_t mask;
 622         size_t i = (((uintptr_t)obj & KMALLOC_SLAB_MASK) - slab->offset) /
 623                    slab->objsize;
 624
 625         ptr = &slab->bmap[i >> 6];
 626         mask = (uint64_t)1U << (i & 63);
 627         KKASSERT(i < slab->ncount && (*ptr & mask) != 0);
 628         atomic_clear_64(ptr, mask);
 629 }
 630
 631 #endif
 632
 633 /*
 634  * Cleanup a mgt structure.
 635  *
 636  * Always called from the current cpu, so we can manipulate the various
 637  * lists freely.
 638  *
 639  * WARNING: findex can race, fobjs[n] is updated after findex is incremented,
 640  *          and 'full'
 641  */
 642 #if 0
 643 static void
 644 mgt_cleanup(struct kmalloc_mgt *mgt)
 645 {
 646 #if 0
 647         struct kmalloc_slab **slabp;
 648         struct kmalloc_slab *slab;
 649         size_t delta;
 650         size_t total;
 651 #endif
 652 }
 653 #endif
 654
 655 #ifdef SLAB_DEBUG
 656 void *
 657 _kmalloc_obj_debug(unsigned long size, struct malloc_type *type, int flags,
 658               const char *file, int line)
 659 #else
 660 void *
 661 _kmalloc_obj(unsigned long size, struct malloc_type *type, int flags)
 662 #endif
 663 {
 664         struct kmalloc_slab *slab;
 665         struct kmalloc_use *use;
 666         struct kmalloc_mgt *mgt;
 667         struct kmalloc_mgt *ggm;
 668         globaldata_t gd;
 669         void *obj;
 670         size_t delta;
 671
 672         /*
 673          * Check limits
 674          */
 675         while (__predict_false(type->ks_loosememuse >= type->ks_limit)) {
 676                 long ttl;
 677                 int n;
 678
 679                 for (n = ttl = 0; n < ncpus; ++n)
 680                         ttl += type->ks_use[n].memuse;
 681                 type->ks_loosememuse = ttl;     /* not MP synchronized */
 682                 if ((ssize_t)ttl < 0)           /* deal with occassional race */
 683                         ttl = 0;
 684                 if (ttl >= type->ks_limit) {
 685                         if (flags & M_NULLOK)
 686                                 return(NULL);
 687                         panic("%s: malloc limit exceeded", type->ks_shortdesc);
 688                 }
 689         }
 690
 691         /*
 692          * Setup
 693          */
 694         crit_enter();
 695         logmemory_quick(malloc_beg);
 696         KKASSERT(size == type->ks_objsize);
 697         gd = mycpu;
 698         use = &type->ks_use[gd->gd_cpuid];
 699
 700 retry:
 701         /*
 702          * Check active
 703          *
 704          * NOTE: obj can be NULL if racing a _kfree_obj().
 705          */
 706         mgt = &use->mgt;
 707         slab = mgt->active;                     /* Might be dummy */
 708         delta = slab->findex - slab->aindex;
 709         if (__predict_true(delta != 0)) {       /* Cannot be dummy */
 710                 size_t i;
 711
 712                 i = slab->aindex % slab->ncount;
 713                 obj = slab->fobjs[i];
 714                 if (__predict_true(obj != NULL)) {
 715                         slab->fobjs[i] = NULL;
 716                         ++slab->aindex;
 717 #ifdef KMALLOC_CHECK_DOUBLE_FREE
 718                         bmap_set(slab, obj);
 719 #endif
 720                         goto found;
 721                 }
 722         }
 723
 724         /*
 725          * Check alternate.  If we find something, swap it with
 726          * the active.
 727          *
 728          * NOTE: It is possible for exhausted slabs to recover entries
 729          *       via _kfree_obj(), so we just keep swapping until both
 730          *       are empty.
 731          *
 732          * NOTE: obj can be NULL if racing a _kfree_obj().
 733          */
 734         slab = mgt->alternate;                  /* Might be dummy */
 735         delta = slab->findex - slab->aindex;
 736         if (__predict_true(delta != 0)) {       /* Cannot be dummy */
 737                 size_t i;
 738
 739                 mgt->alternate = mgt->active;
 740                 mgt->active = slab;
 741                 i = slab->aindex % slab->ncount;
 742                 obj = slab->fobjs[i];
 743                 if (__predict_true(obj != NULL)) {
 744                         slab->fobjs[i] = NULL;
 745                         ++slab->aindex;
 746 #ifdef KMALLOC_CHECK_DOUBLE_FREE
 747                         bmap_set(slab, obj);
 748 #endif
 749                         goto found;
 750                 }
 751         }
 752
 753         /*
 754          * Rotate a slab from the global mgt into the pcpu mgt.
 755          *
 756          *      G(partial, full) -> active -> alternate -> G(empty)
 757          *
 758          * We try to exhaust partials first to reduce fragmentation, then
 759          * dig into the fulls.
 760          */
 761         ggm = &type->ks_mgt;
 762         spin_lock(&ggm->spin);
 763
 764 rerotate:
 765         if (ggm->partial) {
 766                 slab = mgt->alternate;          /* Might be dummy */
 767                 mgt->alternate = mgt->active;   /* Might be dummy */
 768                 mgt->active = ggm->partial;
 769                 ggm->partial = ggm->partial->next;
 770                 mgt->active->next = NULL;
 771                 --ggm->npartial;
 772                 if (slab != &kslab_dummy) {
 773                         KKASSERT(slab->next == NULL);
 774                         *ggm->empty_tailp = slab;
 775                         ggm->empty_tailp = &slab->next;
 776                         ++ggm->nempty;
 777                 }
 778                 spin_unlock(&ggm->spin);
 779                 goto retry;
 780         }
 781
 782         if (ggm->full) {
 783                 slab = mgt->alternate;          /* Might be dummy */
 784                 mgt->alternate = mgt->active;   /* Might be dummy */
 785                 mgt->active = ggm->full;
 786                 ggm->full = ggm->full->next;
 787                 mgt->active->next = NULL;
 788                 --ggm->nfull;
 789                 exis_setlive(&mgt->active->exis);
 790                 if (slab != &kslab_dummy) {
 791                         KKASSERT(slab->next == NULL);
 792                         *ggm->empty_tailp = slab;
 793                         ggm->empty_tailp = &slab->next;
 794                         ++ggm->nempty;
 795                 }
 796                 spin_unlock(&ggm->spin);
 797                 goto retry;
 798         }
 799
 800         /*
 801          * We couldn't find anything, scan a limited number of empty entries
 802          * looking for something with objects.  This will also free excess
 803          * full lists that meet requirements.
 804          */
 805         if (malloc_mgt_poll_empty_locked(ggm, 16))
 806                 goto rerotate;
 807
 808         /*
 809          * Absolutely nothing is available, allocate a new slab and
 810          * rotate it in.
 811          *
 812          * Try to get a slab from the global pcpu slab cache (very cheap).
 813          * If that fails, allocate a new slab (very expensive).
 814          */
 815         spin_unlock(&ggm->spin);
 816
 817         if (gd->gd_kmslab.free_count == 0 || (slab = gslab_alloc(gd)) == NULL) {
 818                 slab = kmem_slab_alloc(KMALLOC_SLAB_SIZE, KMALLOC_SLAB_SIZE,
 819                                        M_WAITOK);
 820         }
 821
 822         bzero(slab, sizeof(*slab));
 823         KKASSERT(offsetof(struct kmalloc_slab, fobjs[use->mgt.slab_count]) <=
 824                  use->mgt.slab_offset);
 825
 826         obj = (char *)slab + use->mgt.slab_offset;
 827         slab->type = type;
 828         slab->orig_cpuid = gd->gd_cpuid;
 829         slab->ncount = use->mgt.slab_count;
 830         slab->offset = use->mgt.slab_offset;
 831         slab->objsize = type->ks_objsize;
 832         slab->aindex = 0;
 833         slab->findex = slab->ncount;
 834         slab->xindex = slab->ncount;
 835         for (delta = 0; delta < slab->ncount; ++delta) {
 836                 slab->fobjs[delta] = obj;
 837                 obj = (char *)obj + type->ks_objsize;
 838         }
 839
 840         /*
 841          * Sanity check, assert that the last byte of last object is still
 842          * in the slab.
 843          */
 844 #if 0
 845         KKASSERT(((((uintptr_t)obj - 1) ^ (uintptr_t)slab) &
 846                   ~KMALLOC_SLAB_MASK) == 0);
 847 #endif
 848         KASSERT(((((uintptr_t)obj - 1) ^ (uintptr_t)slab) &
 849                   ~KMALLOC_SLAB_MASK) == 0, ("SLAB %p ncount %zd objsize %zd obj=%p\n", slab, slab->ncount, slab->objsize, obj));
 850         slab->magic = KMALLOC_SLAB_MAGIC;
 851         spin_init(&slab->spin, "kmslb");
 852
 853         /*
 854          * Rotate it in, then retry.
 855          *
 856          *      (NEW)slab -> active -> alternate -> G(empty)
 857          */
 858         spin_lock(&ggm->spin);
 859         if (mgt->alternate != &kslab_dummy) {
 860                 struct kmalloc_slab *slab_tmp;
 861
 862                 slab_tmp = mgt->alternate;
 863                 slab_tmp->next = NULL;
 864                 *ggm->empty_tailp = slab_tmp;
 865                 ggm->empty_tailp = &slab_tmp->next;
 866                 ++ggm->nempty;
 867         }
 868         mgt->alternate = mgt->active;           /* Might be dummy */
 869         mgt->active = slab;
 870         spin_unlock(&ggm->spin);
 871
 872         goto retry;
 873
 874         /*
 875          * Found object, adjust statistics and return
 876          */
 877 found:
 878         ++use->inuse;
 879         ++use->calls;
 880         use->memuse += size;
 881         use->loosememuse += size;
 882         if (__predict_false(use->loosememuse >= KMALLOC_LOOSE_SIZE)) {
 883             /* not MP synchronized */
 884             type->ks_loosememuse += use->loosememuse;
 885             use->loosememuse = 0;
 886         }
 887
 888         /*
 889          * Handle remaining flags.  M_ZERO is typically not set because
 890          * the inline macro deals with zeroing for constant sizes.
 891          */
 892         if (__predict_false(flags & M_ZERO))
 893             bzero(obj, size);
 894
 895         crit_exit();
 896         logmemory(malloc_end, NULL, type, size, flags);
 897
 898         return(obj);
 899 }
 900
 901 /*
 902  * Free a type-stable object.  We have the base structure and can
 903  * calculate the slab, but from this direction we don't know which
 904  * mgt structure or list the slab might be on.
 905  */
 906 void
 907 _kfree_obj(void *obj, struct malloc_type *type)
 908 {
 909         struct kmalloc_slab *slab;
 910         struct kmalloc_use *use;
 911         globaldata_t gd;
 912         size_t  delta;
 913         size_t  i;
 914
 915         logmemory_quick(free_beg);
 916         gd = mycpu;
 917
 918         /*
 919          * Calculate the slab from the pointer
 920          */
 921         slab = (void *)((uintptr_t)obj & ~KMALLOC_SLAB_MASK);
 922         delta = slab->findex - slab->aindex;
 923         KKASSERT(slab->magic == KMALLOC_SLAB_MAGIC && delta != slab->ncount);
 924
 925         /*
 926          * We can only safely adjust the statistics for the current cpu.
 927          * Don't try to track down the original cpu.  The statistics will
 928          * be collected and fixed up by vmstat -m  (etc).
 929          */
 930         use = &slab->type->ks_use[gd->gd_cpuid];
 931         --use->inuse;
 932         use->memuse -= slab->objsize;
 933
 934         /*
 935          * There MUST be free space in the slab since we are returning
 936          * the obj to the same slab it was allocated from.
 937          */
 938         i = atomic_fetchadd_long(&slab->findex, 1);
 939         i = i % slab->ncount;
 940         if (slab->fobjs[i] != NULL) {
 941                 kprintf("_kfree_obj failure %zd/%zd/%zd\n",
 942                         slab->aindex, slab->findex, slab->ncount);
 943         }
 944 #ifdef KMALLOC_CHECK_DOUBLE_FREE
 945         bmap_clr(slab, obj);
 946 #endif
 947         KKASSERT(slab->fobjs[i] == NULL);
 948         slab->fobjs[i] = obj;
 949         atomic_add_long(&slab->xindex, 1);      /* synchronizer */
 950
 951         logmemory_quick(free_end);
 952 }