/* * mm/percpu.c - percpu memory allocator * * Copyright (C) 2009 SUSE Linux Products GmbH * Copyright (C) 2009 Tejun Heo <tj@kernel.org> * * This file is released under the GPLv2. * * This is percpu allocator which can handle both static and dynamic * areas. Percpu areas are allocated in chunks. Each chunk is * consisted of boot-time determined number of units and the first * chunk is used for static percpu variables in the kernel image * (special boot time alloc/init handling necessary as these areas * need to be brought up before allocation services are running). * Unit grows as necessary and all units grow or shrink in unison. * When a chunk is filled up, another chunk is allocated. * * c0 c1 c2 * ------------------- ------------------- ------------ * | u0 | u1 | u2 | u3 | | u0 | u1 | u2 | u3 | | u0 | u1 | u * ------------------- ...... ------------------- .... ------------ * * Allocation is done in offset-size areas of single unit space. Ie, * an area of 512 bytes at 6k in c1 occupies 512 bytes at 6k of c1:u0, * c1:u1, c1:u2 and c1:u3. On UMA, units corresponds directly to * cpus. On NUMA, the mapping can be non-linear and even sparse. * Percpu access can be done by configuring percpu base registers * according to cpu to unit mapping and pcpu_unit_size. * * There are usually many small percpu allocations many of them being * as small as 4 bytes. The allocator organizes chunks into lists * according to free size and tries to allocate from the fullest one. * Each chunk keeps the maximum contiguous area size hint which is * guaranteed to be equal to or larger than the maximum contiguous * area in the chunk. This helps the allocator not to iterate the * chunk maps unnecessarily. * * Allocation state in each chunk is kept using an array of integers * on chunk->map. A positive value in the map represents a free * region and negative allocated. Allocation inside a chunk is done * by scanning this map sequentially and serving the first matching * entry. This is mostly copied from the percpu_modalloc() allocator. * Chunks can be determined from the address using the index field * in the page struct. The index field contains a pointer to the chunk. * * To use this allocator, arch code should do the following: * * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate * regular address to percpu pointer and back if they need to be * different from the default * * - use pcpu_setup_first_chunk() during percpu area initialization to * setup the first chunk containing the kernel static percpu area */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #include <linux/bitmap.h>#include <linux/bootmem.h>#include <linux/err.h>#include <linux/list.h>#include <linux/log2.h>#include <linux/mm.h>#include <linux/module.h>#include <linux/mutex.h>#include <linux/percpu.h>#include <linux/pfn.h>#include <linux/slab.h>#include <linux/spinlock.h>#include <linux/vmalloc.h>#include <linux/workqueue.h>#include <linux/kmemleak.h> #include <asm/cacheflush.h>#include <asm/sections.h>#include <asm/tlbflush.h>#include <asm/io.h> #define CREATE_TRACE_POINTS#include <trace/events/percpu.h> #include "percpu-internal.h" #define PCPU_SLOT_BASE_SHIFT 5 /* 1-31 shares the same slot */#define PCPU_DFL_MAP_ALLOC 16 /* start a map with 16 ents */#define PCPU_ATOMIC_MAP_MARGIN_LOW 32#define PCPU_ATOMIC_MAP_MARGIN_HIGH 64#define PCPU_EMPTY_POP_PAGES_LOW 2#define PCPU_EMPTY_POP_PAGES_HIGH 4 #ifdef CONFIG_SMP/* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */#ifndef __addr_to_pcpu_ptr#define __addr_to_pcpu_ptr(addr) \ (void __percpu *)((unsigned long)(addr) - \ (unsigned long)pcpu_base_addr + \ (unsigned long)__per_cpu_start)#endif#ifndef __pcpu_ptr_to_addr#define __pcpu_ptr_to_addr(ptr) \ (void __force *)((unsigned long)(ptr) + \ (unsigned long)pcpu_base_addr - \ (unsigned long)__per_cpu_start)#endif#else /* CONFIG_SMP *//* on UP, it's always identity mapped */#define __addr_to_pcpu_ptr(addr) (void __percpu *)(addr)#define __pcpu_ptr_to_addr(ptr) (void __force *)(ptr)#endif /* CONFIG_SMP */ static int pcpu_unit_pages __ro_after_init;static int pcpu_unit_size __ro_after_init;static int pcpu_nr_units __ro_after_init;static int pcpu_atom_size __ro_after_init;int pcpu_nr_slots __ro_after_init;static size_t pcpu_chunk_struct_size __ro_after_init; /* cpus with the lowest and highest unit addresses */static unsigned int pcpu_low_unit_cpu __ro_after_init;static unsigned int pcpu_high_unit_cpu __ro_after_init; /* the address of the first chunk which starts with the kernel static area */void *pcpu_base_addr __ro_after_init;EXPORT_SYMBOL_GPL(pcpu_base_addr); static const int *pcpu_unit_map __ro_after_init; /* cpu -> unit */const unsigned long *pcpu_unit_offsets __ro_after_init; /* cpu -> unit offset */ /* group information, used for vm allocation */static int pcpu_nr_groups __ro_after_init;static const unsigned long *pcpu_group_offsets __ro_after_init;static const size_t *pcpu_group_sizes __ro_after_init; /* * The first chunk which always exists. Note that unlike other * chunks, this one can be allocated and mapped in several different * ways and thus often doesn't live in the vmalloc area. */struct pcpu_chunk *pcpu_first_chunk __ro_after_init; /* * Optional reserved chunk. This chunk reserves part of the first * chunk and serves it for reserved allocations. The amount of * reserved offset is in pcpu_reserved_chunk_limit. When reserved * area doesn't exist, the following variables contain NULL and 0 * respectively. */struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init;static int pcpu_reserved_chunk_limit __ro_after_init; DEFINE_SPINLOCK(pcpu_lock); /* all internal data structures */static DEFINE_MUTEX(pcpu_alloc_mutex); /* chunk create/destroy, [de]pop, map ext */ struct list_head *pcpu_slot __ro_after_init; /* chunk list slots */ /* chunks which need their map areas extended, protected by pcpu_lock */static LIST_HEAD(pcpu_map_extend_chunks); /* * The number of empty populated pages, protected by pcpu_lock. The * reserved chunk doesn't contribute to the count. */static int pcpu_nr_empty_pop_pages; /* * Balance work is used to populate or destroy chunks asynchronously. We * try to keep the number of populated free pages between * PCPU_EMPTY_POP_PAGES_LOW and HIGH for atomic allocations and at most one * empty chunk. */static void pcpu_balance_workfn(struct work_struct *work);static DECLARE_WORK(pcpu_balance_work, pcpu_balance_workfn);static bool pcpu_async_enabled __read_mostly;static bool pcpu_atomic_alloc_failed; static void pcpu_schedule_balance_work(void){ if (pcpu_async_enabled) schedule_work(&pcpu_balance_work);} static bool pcpu_addr_in_first_chunk(void *addr){ void *first_start = pcpu_first_chunk->base_addr; return addr >= first_start && addr < first_start + pcpu_unit_size;} static bool pcpu_addr_in_reserved_chunk(void *addr){ void *first_start = pcpu_first_chunk->base_addr; return addr >= first_start && addr < first_start + pcpu_reserved_chunk_limit;} static int __pcpu_size_to_slot(int size){ int highbit = fls(size); /* size is in bytes */ return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);} static int pcpu_size_to_slot(int size){ if (size == pcpu_unit_size) return pcpu_nr_slots - 1; return __pcpu_size_to_slot(size);} static int pcpu_chunk_slot(const struct pcpu_chunk *chunk){ if (chunk->free_size < sizeof(int) || chunk->contig_hint < sizeof(int)) return 0; return pcpu_size_to_slot(chunk->free_size);} /* set the pointer to a chunk in a page struct */static void pcpu_set_page_chunk(struct page *page, struct pcpu_chunk *pcpu){ page->index = (unsigned long)pcpu;} /* obtain pointer to a chunk from a page struct */static struct pcpu_chunk *pcpu_get_page_chunk(struct page *page){ return (struct pcpu_chunk *)page->index;} static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx){ return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;} static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk, unsigned int cpu, int page_idx){ return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] + (page_idx << PAGE_SHIFT);} static void __maybe_unused pcpu_next_unpop(struct pcpu_chunk *chunk, int *rs, int *re, int end){ *rs = find_next_zero_bit(chunk->populated, end, *rs); *re = find_next_bit(chunk->populated, end, *rs + 1);} static void __maybe_unused pcpu_next_pop(struct pcpu_chunk *chunk, int *rs, int *re, int end){ *rs = find_next_bit(chunk->populated, end, *rs); *re = find_next_zero_bit(chunk->populated, end, *rs + 1);} /* * (Un)populated page region iterators. Iterate over (un)populated * page regions between @start and @end in @chunk. @rs and @re should * be integer variables and will be set to start and end page index of * the current region. */#define pcpu_for_each_unpop_region(chunk, rs, re, start, end) \ for ((rs) = (start), pcpu_next_unpop((chunk), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, pcpu_next_unpop((chunk), &(rs), &(re), (end))) #define pcpu_for_each_pop_region(chunk, rs, re, start, end) \ for ((rs) = (start), pcpu_next_pop((chunk), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, pcpu_next_pop((chunk), &(rs), &(re), (end))) /** * pcpu_mem_zalloc - allocate memory * @size: bytes to allocate * * Allocate @size bytes. If @size is smaller than PAGE_SIZE, * kzalloc() is used; otherwise, vzalloc() is used. The returned * memory is always zeroed. * * CONTEXT: * Does GFP_KERNEL allocation. * * RETURNS: * Pointer to the allocated area on success, NULL on failure. */static void *pcpu_mem_zalloc(size_t size){ if (WARN_ON_ONCE(!slab_is_available())) return NULL; if (size <= PAGE_SIZE) return kzalloc(size, GFP_KERNEL); else return vzalloc(size);} /** * pcpu_mem_free - free memory * @ptr: memory to free * * Free @ptr. @ptr should have been allocated using pcpu_mem_zalloc(). */static void pcpu_mem_free(void *ptr){ kvfree(ptr);} /** * pcpu_count_occupied_pages - count the number of pages an area occupies * @chunk: chunk of interest * @i: index of the area in question * * Count the number of pages chunk's @i'th area occupies. When the area's * start and/or end address isn't aligned to page boundary, the straddled * page is included in the count iff the rest of the page is free. */static int pcpu_count_occupied_pages(struct pcpu_chunk *chunk, int i){ int off = chunk->map[i] & ~1; int end = chunk->map[i + 1] & ~1; if (!PAGE_ALIGNED(off) && i > 0) { int prev = chunk->map[i - 1]; if (!(prev & 1) && prev <= round_down(off, PAGE_SIZE)) off = round_down(off, PAGE_SIZE); } if (!PAGE_ALIGNED(end) && i + 1 < chunk->map_used) { int next = chunk->map[i + 1]; int nend = chunk->map[i + 2] & ~1; if (!(next & 1) && nend >= round_up(end, PAGE_SIZE)) end = round_up(end, PAGE_SIZE); } return max_t(int, PFN_DOWN(end) - PFN_UP(off), 0);} /** * pcpu_chunk_relocate - put chunk in the appropriate chunk slot * @chunk: chunk of interest * @oslot: the previous slot it was on * * This function is called after an allocation or free changed @chunk. * New slot according to the changed state is determined and @chunk is * moved to the slot. Note that the reserved chunk is never put on * chunk slots. * * CONTEXT: * pcpu_lock. */static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot){ int nslot = pcpu_chunk_slot(chunk); if (chunk != pcpu_reserved_chunk && oslot != nslot) { if (oslot < nslot) list_move(&chunk->list, &pcpu_slot[nslot]); else list_move_tail(&chunk->list, &pcpu_slot[nslot]); }} /** * pcpu_need_to_extend - determine whether chunk area map needs to be extended * @chunk: chunk of interest * @is_atomic: the allocation context * * Determine whether area map of @chunk needs to be extended. If * @is_atomic, only the amount necessary for a new allocation is * considered; however, async extension is scheduled if the left amount is * low. If !@is_atomic, it aims for more empty space. Combined, this * ensures that the map is likely to have enough available space to * accomodate atomic allocations which can't extend maps directly. * * CONTEXT: * pcpu_lock. * * RETURNS: * New target map allocation length if extension is necessary, 0 * otherwise. */static int pcpu_need_to_extend(struct pcpu_chunk *chunk, bool is_atomic){ int margin, new_alloc; lockdep_assert_held(&pcpu_lock); if (is_atomic) { margin = 3; if (chunk->map_alloc < chunk->map_used + PCPU_ATOMIC_MAP_MARGIN_LOW) { if (list_empty(&chunk->map_extend_list)) { list_add_tail(&chunk->map_extend_list, &pcpu_map_extend_chunks); pcpu_schedule_balance_work(); } } } else { margin = PCPU_ATOMIC_MAP_MARGIN_HIGH; } if (chunk->map_alloc >= chunk->map_used + margin) return 0; new_alloc = PCPU_DFL_MAP_ALLOC; while (new_alloc < chunk->map_used + margin) new_alloc *= 2; return new_alloc;} /** * pcpu_extend_area_map - extend area map of a chunk * @chunk: chunk of interest * @new_alloc: new target allocation length of the area map * * Extend area map of @chunk to have @new_alloc entries. * * CONTEXT: * Does GFP_KERNEL allocation. Grabs and releases pcpu_lock. * * RETURNS: * 0 on success, -errno on failure. */static int pcpu_extend_area_map(struct pcpu_chunk *chunk, int new_alloc){ int *old = NULL, *new = NULL; size_t old_size = 0, new_size = new_alloc * sizeof(new[0]); unsigned long flags; lockdep_assert_held(&pcpu_alloc_mutex); new = pcpu_mem_zalloc(new_size); if (!new) return -ENOMEM; /* acquire pcpu_lock and switch to new area map */ spin_lock_irqsave(&pcpu_lock, flags); if (new_alloc <= chunk->map_alloc) goto out_unlock; old_size = chunk->map_alloc * sizeof(chunk->map[0]); old = chunk->map; memcpy(new, old, old_size); chunk->map_alloc = new_alloc; chunk->map = new; new = NULL; out_unlock: spin_unlock_irqrestore(&pcpu_lock, flags); /* * pcpu_mem_free() might end up calling vfree() which uses * IRQ-unsafe lock and thus can't be called under pcpu_lock. */ pcpu_mem_free(old); pcpu_mem_free(new); return 0;} /** * pcpu_fit_in_area - try to fit the requested allocation in a candidate area * @chunk: chunk the candidate area belongs to * @off: the offset to the start of the candidate area * @this_size: the size of the candidate area * @size: the size of the target allocation * @align: the alignment of the target allocation * @pop_only: only allocate from already populated region * * We're trying to allocate @size bytes aligned at @align. @chunk's area * at @off sized @this_size is a candidate. This function determines * whether the target allocation fits in the candidate area and returns the * number of bytes to pad after @off. If the target area doesn't fit, -1 * is returned. * * If @pop_only is %true, this function only considers the already * populated part of the candidate area. */static int pcpu_fit_in_area(struct pcpu_chunk *chunk, int off, int this_size, int size, int align, bool pop_only){ int cand_off = off; while (true) { int head = ALIGN(cand_off, align) - off; int page_start, page_end, rs, re; if (this_size < head + size) return -1; if (!pop_only) return head; Lines 1–500 of 2341. Load more
/* * mm/percpu.c - percpu memory allocator * * Copyright (C) 2009 SUSE Linux Products GmbH * Copyright (C) 2009 Tejun Heo <tj@kernel.org> * * This file is released under the GPLv2. * * This is percpu allocator which can handle both static and dynamic * areas. Percpu areas are allocated in chunks. Each chunk is * consisted of boot-time determined number of units and the first * chunk is used for static percpu variables in the kernel image * (special boot time alloc/init handling necessary as these areas * need to be brought up before allocation services are running). * Unit grows as necessary and all units grow or shrink in unison. * When a chunk is filled up, another chunk is allocated. * * c0 c1 c2 * ------------------- ------------------- ------------ * | u0 | u1 | u2 | u3 | | u0 | u1 | u2 | u3 | | u0 | u1 | u * ------------------- ...... ------------------- .... ------------ * * Allocation is done in offset-size areas of single unit space. Ie, * an area of 512 bytes at 6k in c1 occupies 512 bytes at 6k of c1:u0, * c1:u1, c1:u2 and c1:u3. On UMA, units corresponds directly to * cpus. On NUMA, the mapping can be non-linear and even sparse. * Percpu access can be done by configuring percpu base registers * according to cpu to unit mapping and pcpu_unit_size. * * There are usually many small percpu allocations many of them being * as small as 4 bytes. The allocator organizes chunks into lists * according to free size and tries to allocate from the fullest one. * Each chunk keeps the maximum contiguous area size hint which is * guaranteed to be equal to or larger than the maximum contiguous * area in the chunk. This helps the allocator not to iterate the * chunk maps unnecessarily. * * Allocation state in each chunk is kept using an array of integers * on chunk->map. A positive value in the map represents a free * region and negative allocated. Allocation inside a chunk is done * by scanning this map sequentially and serving the first matching * entry. This is mostly copied from the percpu_modalloc() allocator. * Chunks can be determined from the address using the index field * in the page struct. The index field contains a pointer to the chunk. * * To use this allocator, arch code should do the following: * * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate * regular address to percpu pointer and back if they need to be * different from the default * * - use pcpu_setup_first_chunk() during percpu area initialization to * setup the first chunk containing the kernel static percpu area */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #include <linux/bitmap.h> #include <linux/bootmem.h> #include <linux/err.h> #include <linux/list.h> #include <linux/log2.h> #include <linux/mm.h> #include <linux/module.h> #include <linux/mutex.h> #include <linux/percpu.h> #include <linux/pfn.h> #include <linux/slab.h> #include <linux/spinlock.h> #include <linux/vmalloc.h> #include <linux/workqueue.h> #include <linux/kmemleak.h> #include <asm/cacheflush.h> #include <asm/sections.h> #include <asm/tlbflush.h> #include <asm/io.h> #define CREATE_TRACE_POINTS #include <trace/events/percpu.h> #include "percpu-internal.h" #define PCPU_SLOT_BASE_SHIFT 5 /* 1-31 shares the same slot */ #define PCPU_DFL_MAP_ALLOC 16 /* start a map with 16 ents */ #define PCPU_ATOMIC_MAP_MARGIN_LOW 32 #define PCPU_ATOMIC_MAP_MARGIN_HIGH 64 #define PCPU_EMPTY_POP_PAGES_LOW 2 #define PCPU_EMPTY_POP_PAGES_HIGH 4 #ifdef CONFIG_SMP /* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */ #ifndef __addr_to_pcpu_ptr #define __addr_to_pcpu_ptr(addr) \ (void __percpu *)((unsigned long)(addr) - \ (unsigned long)pcpu_base_addr + \ (unsigned long)__per_cpu_start) #endif #ifndef __pcpu_ptr_to_addr #define __pcpu_ptr_to_addr(ptr) \ (void __force *)((unsigned long)(ptr) + \ (unsigned long)pcpu_base_addr - \ (unsigned long)__per_cpu_start) #endif #else /* CONFIG_SMP */ /* on UP, it's always identity mapped */ #define __addr_to_pcpu_ptr(addr) (void __percpu *)(addr) #define __pcpu_ptr_to_addr(ptr) (void __force *)(ptr) #endif /* CONFIG_SMP */ static int pcpu_unit_pages __ro_after_init; static int pcpu_unit_size __ro_after_init; static int pcpu_nr_units __ro_after_init; static int pcpu_atom_size __ro_after_init; int pcpu_nr_slots __ro_after_init; static size_t pcpu_chunk_struct_size __ro_after_init; /* cpus with the lowest and highest unit addresses */ static unsigned int pcpu_low_unit_cpu __ro_after_init; static unsigned int pcpu_high_unit_cpu __ro_after_init; /* the address of the first chunk which starts with the kernel static area */ void *pcpu_base_addr __ro_after_init; EXPORT_SYMBOL_GPL(pcpu_base_addr); static const int *pcpu_unit_map __ro_after_init; /* cpu -> unit */ const unsigned long *pcpu_unit_offsets __ro_after_init; /* cpu -> unit offset */ /* group information, used for vm allocation */ static int pcpu_nr_groups __ro_after_init; static const unsigned long *pcpu_group_offsets __ro_after_init; static const size_t *pcpu_group_sizes __ro_after_init; /* * The first chunk which always exists. Note that unlike other * chunks, this one can be allocated and mapped in several different * ways and thus often doesn't live in the vmalloc area. */ struct pcpu_chunk *pcpu_first_chunk __ro_after_init; /* * Optional reserved chunk. This chunk reserves part of the first * chunk and serves it for reserved allocations. The amount of * reserved offset is in pcpu_reserved_chunk_limit. When reserved * area doesn't exist, the following variables contain NULL and 0 * respectively. */ struct pcpu_chunk *pcpu_reserved_chunk __ro_after_init; static int pcpu_reserved_chunk_limit __ro_after_init; DEFINE_SPINLOCK(pcpu_lock); /* all internal data structures */ static DEFINE_MUTEX(pcpu_alloc_mutex); /* chunk create/destroy, [de]pop, map ext */ struct list_head *pcpu_slot __ro_after_init; /* chunk list slots */ /* chunks which need their map areas extended, protected by pcpu_lock */ static LIST_HEAD(pcpu_map_extend_chunks); /* * The number of empty populated pages, protected by pcpu_lock. The * reserved chunk doesn't contribute to the count. */ static int pcpu_nr_empty_pop_pages; /* * Balance work is used to populate or destroy chunks asynchronously. We * try to keep the number of populated free pages between * PCPU_EMPTY_POP_PAGES_LOW and HIGH for atomic allocations and at most one * empty chunk. */ static void pcpu_balance_workfn(struct work_struct *work); static DECLARE_WORK(pcpu_balance_work, pcpu_balance_workfn); static bool pcpu_async_enabled __read_mostly; static bool pcpu_atomic_alloc_failed; static void pcpu_schedule_balance_work(void) { if (pcpu_async_enabled) schedule_work(&pcpu_balance_work); } static bool pcpu_addr_in_first_chunk(void *addr) { void *first_start = pcpu_first_chunk->base_addr; return addr >= first_start && addr < first_start + pcpu_unit_size; } static bool pcpu_addr_in_reserved_chunk(void *addr) { void *first_start = pcpu_first_chunk->base_addr; return addr >= first_start && addr < first_start + pcpu_reserved_chunk_limit; } static int __pcpu_size_to_slot(int size) { int highbit = fls(size); /* size is in bytes */ return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1); } static int pcpu_size_to_slot(int size) { if (size == pcpu_unit_size) return pcpu_nr_slots - 1; return __pcpu_size_to_slot(size); } static int pcpu_chunk_slot(const struct pcpu_chunk *chunk) { if (chunk->free_size < sizeof(int) || chunk->contig_hint < sizeof(int)) return 0; return pcpu_size_to_slot(chunk->free_size); } /* set the pointer to a chunk in a page struct */ static void pcpu_set_page_chunk(struct page *page, struct pcpu_chunk *pcpu) { page->index = (unsigned long)pcpu; } /* obtain pointer to a chunk from a page struct */ static struct pcpu_chunk *pcpu_get_page_chunk(struct page *page) { return (struct pcpu_chunk *)page->index; } static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx) { return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx; } static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk, unsigned int cpu, int page_idx) { return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] + (page_idx << PAGE_SHIFT); } static void __maybe_unused pcpu_next_unpop(struct pcpu_chunk *chunk, int *rs, int *re, int end) { *rs = find_next_zero_bit(chunk->populated, end, *rs); *re = find_next_bit(chunk->populated, end, *rs + 1); } static void __maybe_unused pcpu_next_pop(struct pcpu_chunk *chunk, int *rs, int *re, int end) { *rs = find_next_bit(chunk->populated, end, *rs); *re = find_next_zero_bit(chunk->populated, end, *rs + 1); } /* * (Un)populated page region iterators. Iterate over (un)populated * page regions between @start and @end in @chunk. @rs and @re should * be integer variables and will be set to start and end page index of * the current region. */ #define pcpu_for_each_unpop_region(chunk, rs, re, start, end) \ for ((rs) = (start), pcpu_next_unpop((chunk), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, pcpu_next_unpop((chunk), &(rs), &(re), (end))) #define pcpu_for_each_pop_region(chunk, rs, re, start, end) \ for ((rs) = (start), pcpu_next_pop((chunk), &(rs), &(re), (end)); \ (rs) < (re); \ (rs) = (re) + 1, pcpu_next_pop((chunk), &(rs), &(re), (end))) /** * pcpu_mem_zalloc - allocate memory * @size: bytes to allocate * * Allocate @size bytes. If @size is smaller than PAGE_SIZE, * kzalloc() is used; otherwise, vzalloc() is used. The returned * memory is always zeroed. * * CONTEXT: * Does GFP_KERNEL allocation. * * RETURNS: * Pointer to the allocated area on success, NULL on failure. */ static void *pcpu_mem_zalloc(size_t size) { if (WARN_ON_ONCE(!slab_is_available())) return NULL; if (size <= PAGE_SIZE) return kzalloc(size, GFP_KERNEL); else return vzalloc(size); } /** * pcpu_mem_free - free memory * @ptr: memory to free * * Free @ptr. @ptr should have been allocated using pcpu_mem_zalloc(). */ static void pcpu_mem_free(void *ptr) { kvfree(ptr); } /** * pcpu_count_occupied_pages - count the number of pages an area occupies * @chunk: chunk of interest * @i: index of the area in question * * Count the number of pages chunk's @i'th area occupies. When the area's * start and/or end address isn't aligned to page boundary, the straddled * page is included in the count iff the rest of the page is free. */ static int pcpu_count_occupied_pages(struct pcpu_chunk *chunk, int i) { int off = chunk->map[i] & ~1; int end = chunk->map[i + 1] & ~1; if (!PAGE_ALIGNED(off) && i > 0) { int prev = chunk->map[i - 1]; if (!(prev & 1) && prev <= round_down(off, PAGE_SIZE)) off = round_down(off, PAGE_SIZE); } if (!PAGE_ALIGNED(end) && i + 1 < chunk->map_used) { int next = chunk->map[i + 1]; int nend = chunk->map[i + 2] & ~1; if (!(next & 1) && nend >= round_up(end, PAGE_SIZE)) end = round_up(end, PAGE_SIZE); } return max_t(int, PFN_DOWN(end) - PFN_UP(off), 0); } /** * pcpu_chunk_relocate - put chunk in the appropriate chunk slot * @chunk: chunk of interest * @oslot: the previous slot it was on * * This function is called after an allocation or free changed @chunk. * New slot according to the changed state is determined and @chunk is * moved to the slot. Note that the reserved chunk is never put on * chunk slots. * * CONTEXT: * pcpu_lock. */ static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot) { int nslot = pcpu_chunk_slot(chunk); if (chunk != pcpu_reserved_chunk && oslot != nslot) { if (oslot < nslot) list_move(&chunk->list, &pcpu_slot[nslot]); else list_move_tail(&chunk->list, &pcpu_slot[nslot]); } } /** * pcpu_need_to_extend - determine whether chunk area map needs to be extended * @chunk: chunk of interest * @is_atomic: the allocation context * * Determine whether area map of @chunk needs to be extended. If * @is_atomic, only the amount necessary for a new allocation is * considered; however, async extension is scheduled if the left amount is * low. If !@is_atomic, it aims for more empty space. Combined, this * ensures that the map is likely to have enough available space to * accomodate atomic allocations which can't extend maps directly. * * CONTEXT: * pcpu_lock. * * RETURNS: * New target map allocation length if extension is necessary, 0 * otherwise. */ static int pcpu_need_to_extend(struct pcpu_chunk *chunk, bool is_atomic) { int margin, new_alloc; lockdep_assert_held(&pcpu_lock); if (is_atomic) { margin = 3; if (chunk->map_alloc < chunk->map_used + PCPU_ATOMIC_MAP_MARGIN_LOW) { if (list_empty(&chunk->map_extend_list)) { list_add_tail(&chunk->map_extend_list, &pcpu_map_extend_chunks); pcpu_schedule_balance_work(); } } } else { margin = PCPU_ATOMIC_MAP_MARGIN_HIGH; } if (chunk->map_alloc >= chunk->map_used + margin) return 0; new_alloc = PCPU_DFL_MAP_ALLOC; while (new_alloc < chunk->map_used + margin) new_alloc *= 2; return new_alloc; } /** * pcpu_extend_area_map - extend area map of a chunk * @chunk: chunk of interest * @new_alloc: new target allocation length of the area map * * Extend area map of @chunk to have @new_alloc entries. * * CONTEXT: * Does GFP_KERNEL allocation. Grabs and releases pcpu_lock. * * RETURNS: * 0 on success, -errno on failure. */ static int pcpu_extend_area_map(struct pcpu_chunk *chunk, int new_alloc) { int *old = NULL, *new = NULL; size_t old_size = 0, new_size = new_alloc * sizeof(new[0]); unsigned long flags; lockdep_assert_held(&pcpu_alloc_mutex); new = pcpu_mem_zalloc(new_size); if (!new) return -ENOMEM; /* acquire pcpu_lock and switch to new area map */ spin_lock_irqsave(&pcpu_lock, flags); if (new_alloc <= chunk->map_alloc) goto out_unlock; old_size = chunk->map_alloc * sizeof(chunk->map[0]); old = chunk->map; memcpy(new, old, old_size); chunk->map_alloc = new_alloc; chunk->map = new; new = NULL; out_unlock: spin_unlock_irqrestore(&pcpu_lock, flags); /* * pcpu_mem_free() might end up calling vfree() which uses * IRQ-unsafe lock and thus can't be called under pcpu_lock. */ pcpu_mem_free(old); pcpu_mem_free(new); return 0; } /** * pcpu_fit_in_area - try to fit the requested allocation in a candidate area * @chunk: chunk the candidate area belongs to * @off: the offset to the start of the candidate area * @this_size: the size of the candidate area * @size: the size of the target allocation * @align: the alignment of the target allocation * @pop_only: only allocate from already populated region * * We're trying to allocate @size bytes aligned at @align. @chunk's area * at @off sized @this_size is a candidate. This function determines * whether the target allocation fits in the candidate area and returns the * number of bytes to pad after @off. If the target area doesn't fit, -1 * is returned. * * If @pop_only is %true, this function only considers the already * populated part of the candidate area. */ static int pcpu_fit_in_area(struct pcpu_chunk *chunk, int off, int this_size, int size, int align, bool pop_only) { int cand_off = off; while (true) { int head = ALIGN(cand_off, align) - off; int page_start, page_end, rs, re; if (this_size < head + size) return -1; if (!pop_only) return head;