/* * 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 followings. * * - 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 */ #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 PCPU_SLOT_BASE_SHIFT		5	/* 1-31 shares the same slot */#define PCPU_DFL_MAP_ALLOC		16	/* start a map with 16 ents */ #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 */ struct pcpu_chunk {	struct list_head	list;		/* linked to pcpu_slot lists */	int			free_size;	/* free bytes in the chunk */	int			contig_hint;	/* max contiguous size hint */	void			*base_addr;	/* base address of this chunk */	int			map_used;	/* # of map entries used */	int			map_alloc;	/* # of map entries allocated */	int			*map;		/* allocation map */	void			*data;		/* chunk data */	bool			immutable;	/* no [de]population allowed */	unsigned long		populated[];	/* populated bitmap */}; static int pcpu_unit_pages __read_mostly;static int pcpu_unit_size __read_mostly;static int pcpu_nr_units __read_mostly;static int pcpu_atom_size __read_mostly;static int pcpu_nr_slots __read_mostly;static size_t pcpu_chunk_struct_size __read_mostly; /* cpus with the lowest and highest unit addresses */static unsigned int pcpu_low_unit_cpu __read_mostly;static unsigned int pcpu_high_unit_cpu __read_mostly; /* the address of the first chunk which starts with the kernel static area */void *pcpu_base_addr __read_mostly;EXPORT_SYMBOL_GPL(pcpu_base_addr); static const int *pcpu_unit_map __read_mostly;		/* cpu -> unit */const unsigned long *pcpu_unit_offsets __read_mostly;	/* cpu -> unit offset */ /* group information, used for vm allocation */static int pcpu_nr_groups __read_mostly;static const unsigned long *pcpu_group_offsets __read_mostly;static const size_t *pcpu_group_sizes __read_mostly; /* * 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. */static struct pcpu_chunk *pcpu_first_chunk; /* * 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. */static struct pcpu_chunk *pcpu_reserved_chunk;static int pcpu_reserved_chunk_limit; /* * Synchronization rules. * * There are two locks - pcpu_alloc_mutex and pcpu_lock.  The former * protects allocation/reclaim paths, chunks, populated bitmap and * vmalloc mapping.  The latter is a spinlock and protects the index * data structures - chunk slots, chunks and area maps in chunks. * * During allocation, pcpu_alloc_mutex is kept locked all the time and * pcpu_lock is grabbed and released as necessary.  All actual memory * allocations are done using GFP_KERNEL with pcpu_lock released.  In * general, percpu memory can't be allocated with irq off but * irqsave/restore are still used in alloc path so that it can be used * from early init path - sched_init() specifically. * * Free path accesses and alters only the index data structures, so it * can be safely called from atomic context.  When memory needs to be * returned to the system, free path schedules reclaim_work which * grabs both pcpu_alloc_mutex and pcpu_lock, unlinks chunks to be * reclaimed, release both locks and frees the chunks.  Note that it's * necessary to grab both locks to remove a chunk from circulation as * allocation path might be referencing the chunk with only * pcpu_alloc_mutex locked. */static DEFINE_MUTEX(pcpu_alloc_mutex);	/* protects whole alloc and reclaim */static DEFINE_SPINLOCK(pcpu_lock);	/* protects index data structures */ static struct list_head *pcpu_slot __read_mostly; /* chunk list slots */ /* reclaim work to release fully free chunks, scheduled from free path */static void pcpu_reclaim(struct work_struct *work);static DECLARE_WORK(pcpu_reclaim_work, pcpu_reclaim); 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 * @size: size of the area * * Free @ptr.  @ptr should have been allocated using pcpu_mem_zalloc(). */static void pcpu_mem_free(void *ptr, size_t size){	if (size <= PAGE_SIZE)		kfree(ptr);	else		vfree(ptr);} /** * 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 * * Determine whether area map of @chunk needs to be extended to * accommodate a new allocation. * * 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){	int new_alloc; 	if (chunk->map_alloc >= chunk->map_used + 2)		return 0; 	new_alloc = PCPU_DFL_MAP_ALLOC;	while (new_alloc < chunk->map_used + 2)		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; 	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, old_size);	pcpu_mem_free(new, new_size); 	return 0;} /** * pcpu_split_block - split a map block * @chunk: chunk of interest * @i: index of map block to split * @head: head size in bytes (can be 0) * @tail: tail size in bytes (can be 0) * * Split the @i'th map block into two or three blocks.  If @head is * non-zero, @head bytes block is inserted before block @i moving it * to @i+1 and reducing its size by @head bytes. * * If @tail is non-zero, the target block, which can be @i or @i+1 * depending on @head, is reduced by @tail bytes and @tail byte block * is inserted after the target block. * * @chunk->map must have enough free slots to accommodate the split. * * CONTEXT: * pcpu_lock. */static void pcpu_split_block(struct pcpu_chunk *chunk, int i,			     int head, int tail){	int nr_extra = !!head + !!tail; 	BUG_ON(chunk->map_alloc < chunk->map_used + nr_extra); 	/* insert new subblocks */	memmove(&chunk->map[i + nr_extra], &chunk->map[i],		sizeof(chunk->map[0]) * (chunk->map_used - i));	chunk->map_used += nr_extra; 	if (head) {		chunk->map[i + 1] = chunk->map[i] - head;		chunk->map[i++] = head;	}	if (tail) {		chunk->map[i++] -= tail;		chunk->map[i] = tail;	}} /** * pcpu_alloc_area - allocate area from a pcpu_chunk * @chunk: chunk of interest * @size: wanted size in bytes * @align: wanted align * * Try to allocate @size bytes area aligned at @align from @chunk. * Note that this function only allocates the offset.  It doesn't * populate or map the area. * * @chunk->map must have at least two free slots. * * CONTEXT: * pcpu_lock. * * RETURNS: * Allocated offset in @chunk on success, -1 if no matching area is * found. */static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align){	int oslot = pcpu_chunk_slot(chunk);	int max_contig = 0;	int i, off; 	for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++])) {		bool is_last = i + 1 == chunk->map_used;		int head, tail; 		/* extra for alignment requirement */		head = ALIGN(off, align) - off;		BUG_ON(i == 0 && head != 0); 		if (chunk->map[i] < 0)			continue;		if (chunk->map[i] < head + size) {			max_contig = max(chunk->map[i], max_contig);			continue;		}

Lines 1–500 of 1946. Load more