/*
 * Conversion table for small slabs sizes / 8 to the index in the
 * kmalloc array. This is necessary for slabs < 192 since we have non power
 * of two cache sizes there. The size of larger slabs can be determined using
 * fls.
 * 通过size_index_elem求出8的倍数后，继续查找kmem_cache的index；
 * 从这里可以直观看到用户申请不同size内存对应的kmem_cache的index
 */
static s8 size_index[24] = {
    3,    /* 8 */
    4,    /* 16 */
    5,    /* 24 */
    5,    /* 32 */
    6,    /* 40 */
    6,    /* 48 */
    6,    /* 56 */
    6,    /* 64 */
    1,    /* 72 */
    1,    /* 80 */
    1,    /* 88 */
    1,    /* 96 */
    7,    /* 104 */
    7,    /* 112 */
    7,    /* 120 */
    7,    /* 128 */
    2,    /* 136 */
    2,    /* 144 */
    2,    /* 152 */
    2,    /* 160 */
    2,    /* 168 */
    2,    /* 176 */
    2,    /* 184 */
    2    /* 192 */
};
/*
8字节对齐，也就是8的多少倍?
*/
static inline int size_index_elem(size_t bytes)
{
    return (bytes - 1) / 8;
}

/*
 * Find the kmem_cache structure that serves a given size of
 * allocation
 */
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
    int index;

    if (unlikely(size > KMALLOC_MAX_SIZE)) {
        WARN_ON_ONCE(!(flags & __GFP_NOWARN));
        return NULL;
    }
    /*如果用户申请的size小于192byte*/
    if (size <= 192) {
        if (!size)
            return ZERO_SIZE_PTR;

        index = size_index[size_index_elem(size)];
    } else
    /*如果用户申请的size大于192byte*/
        index = fls(size - 1);

#ifdef CONFIG_ZONE_DMA
    if (unlikely((flags & GFP_DMA)))
        return kmalloc_dma_caches[index];

#endif
    return kmalloc_caches[index];
}

/*
 * kmalloc_info[] is to make slub_debug=,kmalloc-xx option work at boot time.
 * kmalloc_index() supports up to 2^26=64MB, so the final entry of the table is
 * kmalloc-67108864.
 */
static struct {
    const char *name;
    unsigned long size;
} const kmalloc_info[] __initconst = {
    {NULL,                      0},        {"kmalloc-96",             96},
    {"kmalloc-192",           192},        {"kmalloc-8",               8},
    {"kmalloc-16",             16},        {"kmalloc-32",             32},
    {"kmalloc-64",             64},        {"kmalloc-128",           128},
    {"kmalloc-256",           256},        {"kmalloc-512",           512},
    {"kmalloc-1024",         1024},        {"kmalloc-2048",         2048},
    {"kmalloc-4096",         4096},        {"kmalloc-8192",         8192},
    {"kmalloc-16384",       16384},        {"kmalloc-32768",       32768},
    {"kmalloc-65536",       65536},        {"kmalloc-131072",     131072},
    {"kmalloc-262144",     262144},        {"kmalloc-524288",     524288},
    {"kmalloc-1048576",   1048576},        {"kmalloc-2097152",   2097152},
    {"kmalloc-4194304",   4194304},        {"kmalloc-8388608",   8388608},
    {"kmalloc-16777216", 16777216},        {"kmalloc-33554432", 33554432},
    {"kmalloc-67108864", 67108864}
};

/*
 * fls = Find Last Set in word
 * @result: [1-32]
 * fls(1) = 1, fls(0x80000000) = 32, fls(0) = 0
 */
static inline __attribute__ ((const)) int fls(unsigned long x)
{
    if (__builtin_constant_p(x))
           return constant_fls(x);

    return 32 - clz(x);
}

/*
 * Count the number of zeros, starting from MSB
 * Helper for fls( ) friends
 * This is a pure count, so (1-32) or (0-31) doesn't apply
 * It could be 0 to 32, based on num of 0's in there
 * clz(0x8000_0000) = 0, clz(0xFFFF_FFFF)=0, clz(0) = 32, clz(1) = 31
 */
static inline __attribute__ ((const)) int clz(unsigned int x)
{
    unsigned int res;

    __asm__ __volatile__(
    "    norm.f  %0, %1        \n"
    "    mov.n   %0, 0        \n"
    "    add.p   %0, %0, 1    \n"
    : "=r"(res)
    : "r"(x)
    : "cc");

    return res;
}

static __always_inline void *
slab_alloc(struct kmem_cache *cachep, gfp_t flags, unsigned long caller)
{
    unsigned long save_flags;
    void *objp;

    flags &= gfp_allowed_mask;
    cachep = slab_pre_alloc_hook(cachep, flags);
    if (unlikely(!cachep))
        return NULL;

    cache_alloc_debugcheck_before(cachep, flags);
    /*保存flag寄存器的状态，然后关中断，避免被中断切换进程*/
    local_irq_save(save_flags);
    /*得到了返回值*/
    objp = __do_cache_alloc(cachep, flags);
    /*重新打开中断*/
    local_irq_restore(save_flags);
    objp = cache_alloc_debugcheck_after(cachep, flags, objp, caller);
    prefetchw(objp);

    if (unlikely(flags & __GFP_ZERO) && objp)
        memset(objp, 0, cachep->object_size);

    slab_post_alloc_hook(cachep, flags, 1, &objp);
    return objp;
}

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)
{
    void *objp;
    struct array_cache *ac;

    check_irq_off();
    /*先看array_cache缓存是不是还有*/
    ac = cpu_cache_get(cachep);
    if (likely(ac->avail)) {
        ac->touched = 1;
        objp = ac->entry[--ac->avail];

        STATS_INC_ALLOCHIT(cachep);
        goto out;
    }

    STATS_INC_ALLOCMISS(cachep);
    /*array_cache缓存没了再重新寻找可用的object*/
    objp = cache_alloc_refill(cachep, flags);
    /*
     * the 'ac' may be updated by cache_alloc_refill(),
     * and kmemleak_erase() requires its correct value.
     */
    ac = cpu_cache_get(cachep);

out:
    /*
     * To avoid a false negative, if an object that is in one of the
     * per-CPU caches is leaked, we need to make sure kmemleak doesn't
     * treat the array pointers as a reference to the object.
     */
    if (objp)
        kmemleak_erase(&ac->entry[ac->avail]);
    return objp;
}

/*
 * struct array_cache
 *
 * Purpose:
 * - LIFO ordering, to hand out cache-warm objects from _alloc
 * - reduce the number of linked list operations
 * - reduce spinlock operations
 *
 * The limit is stored in the per-cpu structure to reduce the data cache
 * footprint.
 * 给每个cpu设置的对象缓存池
 */
struct array_cache {
    unsigned int avail;/*缓存池中可用的object数量*/
    unsigned int limit;/*最大object数量*/
    unsigned int batchcount;/*要从 slab_list 转移进本地高速缓存对象的数量，或从本地高速缓存中转移出去的 obj 数量*/
    unsigned int touched;/*从缓存池移除对象时设置为1，否则设置为0*/
    void *entry[];    /* 保存释放的object实例指针
             * Must have this definition in here for the proper
             * alignment of array_cache. Also simplifies accessing
             * the entries.
             */
};

static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)
{
    int batchcount;
    struct kmem_cache_node *n;
    struct array_cache *ac, *shared;
    int node;
    void *list = NULL;
    struct page *page;
    /*确保中断已经关闭*/
    check_irq_off();
    node = numa_mem_id();

    ac = cpu_cache_get(cachep);
    batchcount = ac->batchcount;
    if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
        /*
         * If there was little recent activity on this cache, then
         * perform only a partial refill.  Otherwise we could generate
         * refill bouncing.
         */
        batchcount = BATCHREFILL_LIMIT;
    }
    n = get_node(cachep, node);

    BUG_ON(ac->avail > 0 || !n);
    shared = READ_ONCE(n->shared);
    if (!n->free_objects && (!shared || !shared->avail))
        goto direct_grow;

    spin_lock(&n->list_lock);
    shared = READ_ONCE(n->shared);

    /* See if we can refill from the shared array */
    //从全局共享空闲对象中转移空闲对象到本地 CPU 空闲对象链表上
    if (shared && transfer_objects(ac, shared, batchcount)) {
        shared->touched = 1;
        goto alloc_done;
    }

    while (batchcount > 0) {
        /* Get slab alloc is to come from. */
        page = get_first_slab(n, false);//从 slab 中获取空闲 slab
        if (!page)
            goto must_grow;

        check_spinlock_acquired(cachep);
        /*从free slab中获取空闲object，转移到本地CPU空闲object链表上*/
        batchcount = alloc_block(cachep, ac, page, batchcount);
        fixup_slab_list(cachep, n, page, &list);
    }

must_grow:
    n->free_objects -= ac->avail;
alloc_done:
    spin_unlock(&n->list_lock);
    fixup_objfreelist_debug(cachep, &list);

direct_grow:
    if (unlikely(!ac->avail)) {
        /* Check if we can use obj in pfmemalloc slab */
        if (sk_memalloc_socks()) {
            void *obj = cache_alloc_pfmemalloc(cachep, n, flags);

            if (obj)
                return obj;
        }
        /*当slab中都没有空闲object时，就从buddy系统中获取内存*/
        page = cache_grow_begin(cachep, gfp_exact_node(flags), node);

        /*
         * cache_grow_begin() can reenable interrupts,
         * then ac could change.
         */
        ac = cpu_cache_get(cachep);
        if (!ac->avail && page)
            alloc_block(cachep, ac, page, batchcount);
        cache_grow_end(cachep, page);

        if (!ac->avail)
            return NULL;
    }
    ac->touched = 1;

    return ac->entry[--ac->avail];
}

static struct page *get_first_slab(struct kmem_cache_node *n, bool pfmemalloc)
{
    struct page *page;

    page = list_first_entry_or_null(&n->slabs_partial,
            struct page, lru);
    if (!page) {
        n->free_touched = 1;
        page = list_first_entry_or_null(&n->slabs_free,
                struct page, lru);
    }

    if (sk_memalloc_socks())
        return get_valid_first_slab(n, page, pfmemalloc);

    return page;
}

static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
    if (__builtin_constant_p(size)) {
        if (size > KMALLOC_MAX_CACHE_SIZE)
            return kmalloc_large(size, flags);
#ifndef CONFIG_SLOB
        if (!(flags & GFP_DMA)) {
            int index = kmalloc_index(size);

            if (!index)
                return ZERO_SIZE_PTR;

            return kmem_cache_alloc_trace(kmalloc_caches[index],
                    flags, size);
        }
#endif
    }
    return __kmalloc(size, flags);
}

/**
 * __do_kmalloc - allocate memory
 * @size: how many bytes of memory are required.
 * @flags: the type of memory to allocate (see kmalloc).
 * @caller: function caller for debug tracking of the caller
 */
static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
                      unsigned long caller)
{
    struct kmem_cache *cachep;
    void *ret;
    /*根据用户参数找到高速缓存块*/
    cachep = kmalloc_slab(size, flags);
    if (unlikely(ZERO_OR_NULL_PTR(cachep)))
        return cachep;
    /*根据kmem_cache结构体和用户参数找到object，并返回地址*/
    ret = slab_alloc(cachep, flags, caller);

    kasan_kmalloc(cachep, ret, size, flags);
    trace_kmalloc(caller, ret,
              size, cachep->size, flags);

    return ret;
}

https://img2020.cnblogs.com/blog/2052730/202112/2052730-20211221095658911-877821572.png

https://img2020.cnblogs.com/blog/2052730/202112/2052730-20211221162242031-658490447.png