blob: 3bb810a72006cd65e345e16fd124b61e029964db [file] [log] [blame]
Tejun Heofbf59bc2009-02-20 16:29:08 +09001/*
Tejun Heo88999a82010-04-09 18:57:01 +09002 * mm/percpu.c - percpu memory allocator
Tejun Heofbf59bc2009-02-20 16:29:08 +09003 *
4 * Copyright (C) 2009 SUSE Linux Products GmbH
5 * Copyright (C) 2009 Tejun Heo <tj@kernel.org>
6 *
7 * This file is released under the GPLv2.
8 *
9 * This is percpu allocator which can handle both static and dynamic
Tejun Heo88999a82010-04-09 18:57:01 +090010 * areas. Percpu areas are allocated in chunks. Each chunk is
11 * consisted of boot-time determined number of units and the first
12 * chunk is used for static percpu variables in the kernel image
Tejun Heo2f39e632009-07-04 08:11:00 +090013 * (special boot time alloc/init handling necessary as these areas
14 * need to be brought up before allocation services are running).
15 * Unit grows as necessary and all units grow or shrink in unison.
Tejun Heo88999a82010-04-09 18:57:01 +090016 * When a chunk is filled up, another chunk is allocated.
Tejun Heofbf59bc2009-02-20 16:29:08 +090017 *
18 * c0 c1 c2
19 * ------------------- ------------------- ------------
20 * | u0 | u1 | u2 | u3 | | u0 | u1 | u2 | u3 | | u0 | u1 | u
21 * ------------------- ...... ------------------- .... ------------
22 *
23 * Allocation is done in offset-size areas of single unit space. Ie,
24 * an area of 512 bytes at 6k in c1 occupies 512 bytes at 6k of c1:u0,
Tejun Heo2f39e632009-07-04 08:11:00 +090025 * c1:u1, c1:u2 and c1:u3. On UMA, units corresponds directly to
26 * cpus. On NUMA, the mapping can be non-linear and even sparse.
27 * Percpu access can be done by configuring percpu base registers
28 * according to cpu to unit mapping and pcpu_unit_size.
Tejun Heofbf59bc2009-02-20 16:29:08 +090029 *
Tejun Heo2f39e632009-07-04 08:11:00 +090030 * There are usually many small percpu allocations many of them being
31 * as small as 4 bytes. The allocator organizes chunks into lists
Tejun Heofbf59bc2009-02-20 16:29:08 +090032 * according to free size and tries to allocate from the fullest one.
33 * Each chunk keeps the maximum contiguous area size hint which is
Namhyung Kim47858792010-08-11 11:24:10 +090034 * guaranteed to be equal to or larger than the maximum contiguous
Tejun Heofbf59bc2009-02-20 16:29:08 +090035 * area in the chunk. This helps the allocator not to iterate the
36 * chunk maps unnecessarily.
37 *
38 * Allocation state in each chunk is kept using an array of integers
39 * on chunk->map. A positive value in the map represents a free
40 * region and negative allocated. Allocation inside a chunk is done
41 * by scanning this map sequentially and serving the first matching
42 * entry. This is mostly copied from the percpu_modalloc() allocator.
Christoph Lametere1b9aa32009-04-02 13:21:44 +090043 * Chunks can be determined from the address using the index field
44 * in the page struct. The index field contains a pointer to the chunk.
Tejun Heofbf59bc2009-02-20 16:29:08 +090045 *
46 * To use this allocator, arch code should do the followings.
47 *
Tejun Heofbf59bc2009-02-20 16:29:08 +090048 * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate
Tejun Heoe0100982009-03-10 16:27:48 +090049 * regular address to percpu pointer and back if they need to be
50 * different from the default
Tejun Heofbf59bc2009-02-20 16:29:08 +090051 *
Tejun Heo8d408b42009-02-24 11:57:21 +090052 * - use pcpu_setup_first_chunk() during percpu area initialization to
53 * setup the first chunk containing the kernel static percpu area
Tejun Heofbf59bc2009-02-20 16:29:08 +090054 */
55
56#include <linux/bitmap.h>
57#include <linux/bootmem.h>
Tejun Heofd1e8a12009-08-14 15:00:51 +090058#include <linux/err.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090059#include <linux/list.h>
Tejun Heoa530b792009-07-04 08:11:00 +090060#include <linux/log2.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090061#include <linux/mm.h>
62#include <linux/module.h>
63#include <linux/mutex.h>
64#include <linux/percpu.h>
65#include <linux/pfn.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090066#include <linux/slab.h>
Tejun Heoccea34b2009-03-07 00:44:13 +090067#include <linux/spinlock.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090068#include <linux/vmalloc.h>
Tejun Heoa56dbdd2009-03-07 00:44:11 +090069#include <linux/workqueue.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090070
71#include <asm/cacheflush.h>
Tejun Heoe0100982009-03-10 16:27:48 +090072#include <asm/sections.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090073#include <asm/tlbflush.h>
Vivek Goyal3b034b02009-11-24 15:50:03 +090074#include <asm/io.h>
Tejun Heofbf59bc2009-02-20 16:29:08 +090075
Tejun Heofbf59bc2009-02-20 16:29:08 +090076#define PCPU_SLOT_BASE_SHIFT 5 /* 1-31 shares the same slot */
77#define PCPU_DFL_MAP_ALLOC 16 /* start a map with 16 ents */
78
Tejun Heobbddff02010-09-03 18:22:48 +020079#ifdef CONFIG_SMP
Tejun Heoe0100982009-03-10 16:27:48 +090080/* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */
81#ifndef __addr_to_pcpu_ptr
82#define __addr_to_pcpu_ptr(addr) \
Tejun Heo43cf38e2010-02-02 14:38:57 +090083 (void __percpu *)((unsigned long)(addr) - \
84 (unsigned long)pcpu_base_addr + \
85 (unsigned long)__per_cpu_start)
Tejun Heoe0100982009-03-10 16:27:48 +090086#endif
87#ifndef __pcpu_ptr_to_addr
88#define __pcpu_ptr_to_addr(ptr) \
Tejun Heo43cf38e2010-02-02 14:38:57 +090089 (void __force *)((unsigned long)(ptr) + \
90 (unsigned long)pcpu_base_addr - \
91 (unsigned long)__per_cpu_start)
Tejun Heoe0100982009-03-10 16:27:48 +090092#endif
Tejun Heobbddff02010-09-03 18:22:48 +020093#else /* CONFIG_SMP */
94/* on UP, it's always identity mapped */
95#define __addr_to_pcpu_ptr(addr) (void __percpu *)(addr)
96#define __pcpu_ptr_to_addr(ptr) (void __force *)(ptr)
97#endif /* CONFIG_SMP */
Tejun Heoe0100982009-03-10 16:27:48 +090098
Tejun Heofbf59bc2009-02-20 16:29:08 +090099struct pcpu_chunk {
100 struct list_head list; /* linked to pcpu_slot lists */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900101 int free_size; /* free bytes in the chunk */
102 int contig_hint; /* max contiguous size hint */
Tejun Heobba174f2009-08-14 15:00:51 +0900103 void *base_addr; /* base address of this chunk */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900104 int map_used; /* # of map entries used */
105 int map_alloc; /* # of map entries allocated */
106 int *map; /* allocation map */
Tejun Heo88999a82010-04-09 18:57:01 +0900107 void *data; /* chunk data */
Tejun Heo8d408b42009-02-24 11:57:21 +0900108 bool immutable; /* no [de]population allowed */
Tejun Heoce3141a2009-07-04 08:11:00 +0900109 unsigned long populated[]; /* populated bitmap */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900110};
111
Tejun Heo40150d32009-02-24 12:32:28 +0900112static int pcpu_unit_pages __read_mostly;
113static int pcpu_unit_size __read_mostly;
Tejun Heo2f39e632009-07-04 08:11:00 +0900114static int pcpu_nr_units __read_mostly;
Tejun Heo65632972009-08-14 15:00:52 +0900115static int pcpu_atom_size __read_mostly;
Tejun Heo40150d32009-02-24 12:32:28 +0900116static int pcpu_nr_slots __read_mostly;
117static size_t pcpu_chunk_struct_size __read_mostly;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900118
Tejun Heoa855b842011-11-18 10:55:35 -0800119/* cpus with the lowest and highest unit addresses */
120static unsigned int pcpu_low_unit_cpu __read_mostly;
121static unsigned int pcpu_high_unit_cpu __read_mostly;
Tejun Heo2f39e632009-07-04 08:11:00 +0900122
Tejun Heofbf59bc2009-02-20 16:29:08 +0900123/* the address of the first chunk which starts with the kernel static area */
Tejun Heo40150d32009-02-24 12:32:28 +0900124void *pcpu_base_addr __read_mostly;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900125EXPORT_SYMBOL_GPL(pcpu_base_addr);
126
Tejun Heofb435d52009-08-14 15:00:51 +0900127static const int *pcpu_unit_map __read_mostly; /* cpu -> unit */
128const unsigned long *pcpu_unit_offsets __read_mostly; /* cpu -> unit offset */
Tejun Heo2f39e632009-07-04 08:11:00 +0900129
Tejun Heo65632972009-08-14 15:00:52 +0900130/* group information, used for vm allocation */
131static int pcpu_nr_groups __read_mostly;
132static const unsigned long *pcpu_group_offsets __read_mostly;
133static const size_t *pcpu_group_sizes __read_mostly;
134
Tejun Heoae9e6bc92009-04-02 13:19:54 +0900135/*
136 * The first chunk which always exists. Note that unlike other
137 * chunks, this one can be allocated and mapped in several different
138 * ways and thus often doesn't live in the vmalloc area.
139 */
140static struct pcpu_chunk *pcpu_first_chunk;
141
142/*
143 * Optional reserved chunk. This chunk reserves part of the first
144 * chunk and serves it for reserved allocations. The amount of
145 * reserved offset is in pcpu_reserved_chunk_limit. When reserved
146 * area doesn't exist, the following variables contain NULL and 0
147 * respectively.
148 */
Tejun Heoedcb4632009-03-06 14:33:59 +0900149static struct pcpu_chunk *pcpu_reserved_chunk;
Tejun Heoedcb4632009-03-06 14:33:59 +0900150static int pcpu_reserved_chunk_limit;
151
Tejun Heofbf59bc2009-02-20 16:29:08 +0900152/*
Tejun Heoccea34b2009-03-07 00:44:13 +0900153 * Synchronization rules.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900154 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900155 * There are two locks - pcpu_alloc_mutex and pcpu_lock. The former
Tejun Heoce3141a2009-07-04 08:11:00 +0900156 * protects allocation/reclaim paths, chunks, populated bitmap and
157 * vmalloc mapping. The latter is a spinlock and protects the index
158 * data structures - chunk slots, chunks and area maps in chunks.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900159 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900160 * During allocation, pcpu_alloc_mutex is kept locked all the time and
161 * pcpu_lock is grabbed and released as necessary. All actual memory
Jiri Kosina403a91b2009-10-29 00:25:59 +0900162 * allocations are done using GFP_KERNEL with pcpu_lock released. In
163 * general, percpu memory can't be allocated with irq off but
164 * irqsave/restore are still used in alloc path so that it can be used
165 * from early init path - sched_init() specifically.
Tejun Heoccea34b2009-03-07 00:44:13 +0900166 *
167 * Free path accesses and alters only the index data structures, so it
168 * can be safely called from atomic context. When memory needs to be
169 * returned to the system, free path schedules reclaim_work which
170 * grabs both pcpu_alloc_mutex and pcpu_lock, unlinks chunks to be
171 * reclaimed, release both locks and frees the chunks. Note that it's
172 * necessary to grab both locks to remove a chunk from circulation as
173 * allocation path might be referencing the chunk with only
174 * pcpu_alloc_mutex locked.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900175 */
Tejun Heoccea34b2009-03-07 00:44:13 +0900176static DEFINE_MUTEX(pcpu_alloc_mutex); /* protects whole alloc and reclaim */
177static DEFINE_SPINLOCK(pcpu_lock); /* protects index data structures */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900178
Tejun Heo40150d32009-02-24 12:32:28 +0900179static struct list_head *pcpu_slot __read_mostly; /* chunk list slots */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900180
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900181/* reclaim work to release fully free chunks, scheduled from free path */
182static void pcpu_reclaim(struct work_struct *work);
183static DECLARE_WORK(pcpu_reclaim_work, pcpu_reclaim);
184
Tejun Heo020ec652010-04-09 18:57:00 +0900185static bool pcpu_addr_in_first_chunk(void *addr)
186{
187 void *first_start = pcpu_first_chunk->base_addr;
188
189 return addr >= first_start && addr < first_start + pcpu_unit_size;
190}
191
192static bool pcpu_addr_in_reserved_chunk(void *addr)
193{
194 void *first_start = pcpu_first_chunk->base_addr;
195
196 return addr >= first_start &&
197 addr < first_start + pcpu_reserved_chunk_limit;
198}
199
Tejun Heod9b55ee2009-02-24 11:57:21 +0900200static int __pcpu_size_to_slot(int size)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900201{
Tejun Heocae3aeb2009-02-21 16:56:23 +0900202 int highbit = fls(size); /* size is in bytes */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900203 return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
204}
205
Tejun Heod9b55ee2009-02-24 11:57:21 +0900206static int pcpu_size_to_slot(int size)
207{
208 if (size == pcpu_unit_size)
209 return pcpu_nr_slots - 1;
210 return __pcpu_size_to_slot(size);
211}
212
Tejun Heofbf59bc2009-02-20 16:29:08 +0900213static int pcpu_chunk_slot(const struct pcpu_chunk *chunk)
214{
215 if (chunk->free_size < sizeof(int) || chunk->contig_hint < sizeof(int))
216 return 0;
217
218 return pcpu_size_to_slot(chunk->free_size);
219}
220
Tejun Heo88999a82010-04-09 18:57:01 +0900221/* set the pointer to a chunk in a page struct */
222static void pcpu_set_page_chunk(struct page *page, struct pcpu_chunk *pcpu)
223{
224 page->index = (unsigned long)pcpu;
225}
226
227/* obtain pointer to a chunk from a page struct */
228static struct pcpu_chunk *pcpu_get_page_chunk(struct page *page)
229{
230 return (struct pcpu_chunk *)page->index;
231}
232
233static int __maybe_unused pcpu_page_idx(unsigned int cpu, int page_idx)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900234{
Tejun Heo2f39e632009-07-04 08:11:00 +0900235 return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900236}
237
Tejun Heo9983b6f02010-06-18 11:44:31 +0200238static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
239 unsigned int cpu, int page_idx)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900240{
Tejun Heobba174f2009-08-14 15:00:51 +0900241 return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] +
Tejun Heofb435d52009-08-14 15:00:51 +0900242 (page_idx << PAGE_SHIFT);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900243}
244
Tejun Heo88999a82010-04-09 18:57:01 +0900245static void __maybe_unused pcpu_next_unpop(struct pcpu_chunk *chunk,
246 int *rs, int *re, int end)
Tejun Heoce3141a2009-07-04 08:11:00 +0900247{
248 *rs = find_next_zero_bit(chunk->populated, end, *rs);
249 *re = find_next_bit(chunk->populated, end, *rs + 1);
250}
251
Tejun Heo88999a82010-04-09 18:57:01 +0900252static void __maybe_unused pcpu_next_pop(struct pcpu_chunk *chunk,
253 int *rs, int *re, int end)
Tejun Heoce3141a2009-07-04 08:11:00 +0900254{
255 *rs = find_next_bit(chunk->populated, end, *rs);
256 *re = find_next_zero_bit(chunk->populated, end, *rs + 1);
257}
258
259/*
260 * (Un)populated page region iterators. Iterate over (un)populated
Uwe Kleine-Königb5950762010-11-01 15:38:34 -0400261 * page regions between @start and @end in @chunk. @rs and @re should
Tejun Heoce3141a2009-07-04 08:11:00 +0900262 * be integer variables and will be set to start and end page index of
263 * the current region.
264 */
265#define pcpu_for_each_unpop_region(chunk, rs, re, start, end) \
266 for ((rs) = (start), pcpu_next_unpop((chunk), &(rs), &(re), (end)); \
267 (rs) < (re); \
268 (rs) = (re) + 1, pcpu_next_unpop((chunk), &(rs), &(re), (end)))
269
270#define pcpu_for_each_pop_region(chunk, rs, re, start, end) \
271 for ((rs) = (start), pcpu_next_pop((chunk), &(rs), &(re), (end)); \
272 (rs) < (re); \
273 (rs) = (re) + 1, pcpu_next_pop((chunk), &(rs), &(re), (end)))
274
Tejun Heofbf59bc2009-02-20 16:29:08 +0900275/**
Bob Liu90459ce02011-08-04 11:02:33 +0200276 * pcpu_mem_zalloc - allocate memory
Tejun Heo1880d932009-03-07 00:44:09 +0900277 * @size: bytes to allocate
Tejun Heofbf59bc2009-02-20 16:29:08 +0900278 *
Tejun Heo1880d932009-03-07 00:44:09 +0900279 * Allocate @size bytes. If @size is smaller than PAGE_SIZE,
Bob Liu90459ce02011-08-04 11:02:33 +0200280 * kzalloc() is used; otherwise, vzalloc() is used. The returned
Tejun Heo1880d932009-03-07 00:44:09 +0900281 * memory is always zeroed.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900282 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900283 * CONTEXT:
284 * Does GFP_KERNEL allocation.
285 *
Tejun Heofbf59bc2009-02-20 16:29:08 +0900286 * RETURNS:
Tejun Heo1880d932009-03-07 00:44:09 +0900287 * Pointer to the allocated area on success, NULL on failure.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900288 */
Bob Liu90459ce02011-08-04 11:02:33 +0200289static void *pcpu_mem_zalloc(size_t size)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900290{
Tejun Heo099a19d2010-06-27 18:50:00 +0200291 if (WARN_ON_ONCE(!slab_is_available()))
292 return NULL;
293
Tejun Heofbf59bc2009-02-20 16:29:08 +0900294 if (size <= PAGE_SIZE)
Tejun Heo1880d932009-03-07 00:44:09 +0900295 return kzalloc(size, GFP_KERNEL);
Jesper Juhl7af4c092010-10-30 15:56:54 +0200296 else
297 return vzalloc(size);
Tejun Heo1880d932009-03-07 00:44:09 +0900298}
Tejun Heofbf59bc2009-02-20 16:29:08 +0900299
Tejun Heo1880d932009-03-07 00:44:09 +0900300/**
301 * pcpu_mem_free - free memory
302 * @ptr: memory to free
303 * @size: size of the area
304 *
Bob Liu90459ce02011-08-04 11:02:33 +0200305 * Free @ptr. @ptr should have been allocated using pcpu_mem_zalloc().
Tejun Heo1880d932009-03-07 00:44:09 +0900306 */
307static void pcpu_mem_free(void *ptr, size_t size)
308{
309 if (size <= PAGE_SIZE)
310 kfree(ptr);
311 else
312 vfree(ptr);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900313}
314
315/**
316 * pcpu_chunk_relocate - put chunk in the appropriate chunk slot
317 * @chunk: chunk of interest
318 * @oslot: the previous slot it was on
319 *
320 * This function is called after an allocation or free changed @chunk.
321 * New slot according to the changed state is determined and @chunk is
Tejun Heoedcb4632009-03-06 14:33:59 +0900322 * moved to the slot. Note that the reserved chunk is never put on
323 * chunk slots.
Tejun Heoccea34b2009-03-07 00:44:13 +0900324 *
325 * CONTEXT:
326 * pcpu_lock.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900327 */
328static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
329{
330 int nslot = pcpu_chunk_slot(chunk);
331
Tejun Heoedcb4632009-03-06 14:33:59 +0900332 if (chunk != pcpu_reserved_chunk && oslot != nslot) {
Tejun Heofbf59bc2009-02-20 16:29:08 +0900333 if (oslot < nslot)
334 list_move(&chunk->list, &pcpu_slot[nslot]);
335 else
336 list_move_tail(&chunk->list, &pcpu_slot[nslot]);
337 }
338}
339
Tejun Heofbf59bc2009-02-20 16:29:08 +0900340/**
Tejun Heo833af842009-11-11 15:35:18 +0900341 * pcpu_need_to_extend - determine whether chunk area map needs to be extended
342 * @chunk: chunk of interest
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900343 *
Tejun Heo833af842009-11-11 15:35:18 +0900344 * Determine whether area map of @chunk needs to be extended to
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300345 * accommodate a new allocation.
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900346 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900347 * CONTEXT:
Tejun Heo833af842009-11-11 15:35:18 +0900348 * pcpu_lock.
Tejun Heoccea34b2009-03-07 00:44:13 +0900349 *
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900350 * RETURNS:
Tejun Heo833af842009-11-11 15:35:18 +0900351 * New target map allocation length if extension is necessary, 0
352 * otherwise.
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900353 */
Tejun Heo833af842009-11-11 15:35:18 +0900354static int pcpu_need_to_extend(struct pcpu_chunk *chunk)
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900355{
356 int new_alloc;
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900357
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900358 if (chunk->map_alloc >= chunk->map_used + 2)
359 return 0;
360
361 new_alloc = PCPU_DFL_MAP_ALLOC;
362 while (new_alloc < chunk->map_used + 2)
363 new_alloc *= 2;
364
Tejun Heo833af842009-11-11 15:35:18 +0900365 return new_alloc;
366}
367
368/**
369 * pcpu_extend_area_map - extend area map of a chunk
370 * @chunk: chunk of interest
371 * @new_alloc: new target allocation length of the area map
372 *
373 * Extend area map of @chunk to have @new_alloc entries.
374 *
375 * CONTEXT:
376 * Does GFP_KERNEL allocation. Grabs and releases pcpu_lock.
377 *
378 * RETURNS:
379 * 0 on success, -errno on failure.
380 */
381static int pcpu_extend_area_map(struct pcpu_chunk *chunk, int new_alloc)
382{
383 int *old = NULL, *new = NULL;
384 size_t old_size = 0, new_size = new_alloc * sizeof(new[0]);
385 unsigned long flags;
386
Bob Liu90459ce02011-08-04 11:02:33 +0200387 new = pcpu_mem_zalloc(new_size);
Tejun Heo833af842009-11-11 15:35:18 +0900388 if (!new)
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900389 return -ENOMEM;
Tejun Heoccea34b2009-03-07 00:44:13 +0900390
Tejun Heo833af842009-11-11 15:35:18 +0900391 /* acquire pcpu_lock and switch to new area map */
392 spin_lock_irqsave(&pcpu_lock, flags);
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900393
Tejun Heo833af842009-11-11 15:35:18 +0900394 if (new_alloc <= chunk->map_alloc)
395 goto out_unlock;
396
397 old_size = chunk->map_alloc * sizeof(chunk->map[0]);
Huang Shijiea002d142010-08-08 14:39:07 +0200398 old = chunk->map;
399
400 memcpy(new, old, old_size);
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900401
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900402 chunk->map_alloc = new_alloc;
403 chunk->map = new;
Tejun Heo833af842009-11-11 15:35:18 +0900404 new = NULL;
405
406out_unlock:
407 spin_unlock_irqrestore(&pcpu_lock, flags);
408
409 /*
410 * pcpu_mem_free() might end up calling vfree() which uses
411 * IRQ-unsafe lock and thus can't be called under pcpu_lock.
412 */
413 pcpu_mem_free(old, old_size);
414 pcpu_mem_free(new, new_size);
415
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900416 return 0;
417}
418
419/**
Tejun Heofbf59bc2009-02-20 16:29:08 +0900420 * pcpu_split_block - split a map block
421 * @chunk: chunk of interest
422 * @i: index of map block to split
Tejun Heocae3aeb2009-02-21 16:56:23 +0900423 * @head: head size in bytes (can be 0)
424 * @tail: tail size in bytes (can be 0)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900425 *
426 * Split the @i'th map block into two or three blocks. If @head is
427 * non-zero, @head bytes block is inserted before block @i moving it
428 * to @i+1 and reducing its size by @head bytes.
429 *
430 * If @tail is non-zero, the target block, which can be @i or @i+1
431 * depending on @head, is reduced by @tail bytes and @tail byte block
432 * is inserted after the target block.
433 *
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300434 * @chunk->map must have enough free slots to accommodate the split.
Tejun Heoccea34b2009-03-07 00:44:13 +0900435 *
436 * CONTEXT:
437 * pcpu_lock.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900438 */
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900439static void pcpu_split_block(struct pcpu_chunk *chunk, int i,
440 int head, int tail)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900441{
442 int nr_extra = !!head + !!tail;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900443
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900444 BUG_ON(chunk->map_alloc < chunk->map_used + nr_extra);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900445
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900446 /* insert new subblocks */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900447 memmove(&chunk->map[i + nr_extra], &chunk->map[i],
448 sizeof(chunk->map[0]) * (chunk->map_used - i));
449 chunk->map_used += nr_extra;
450
451 if (head) {
452 chunk->map[i + 1] = chunk->map[i] - head;
453 chunk->map[i++] = head;
454 }
455 if (tail) {
456 chunk->map[i++] -= tail;
457 chunk->map[i] = tail;
458 }
Tejun Heofbf59bc2009-02-20 16:29:08 +0900459}
460
461/**
462 * pcpu_alloc_area - allocate area from a pcpu_chunk
463 * @chunk: chunk of interest
Tejun Heocae3aeb2009-02-21 16:56:23 +0900464 * @size: wanted size in bytes
Tejun Heofbf59bc2009-02-20 16:29:08 +0900465 * @align: wanted align
466 *
467 * Try to allocate @size bytes area aligned at @align from @chunk.
468 * Note that this function only allocates the offset. It doesn't
469 * populate or map the area.
470 *
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900471 * @chunk->map must have at least two free slots.
472 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900473 * CONTEXT:
474 * pcpu_lock.
475 *
Tejun Heofbf59bc2009-02-20 16:29:08 +0900476 * RETURNS:
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900477 * Allocated offset in @chunk on success, -1 if no matching area is
478 * found.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900479 */
480static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
481{
482 int oslot = pcpu_chunk_slot(chunk);
483 int max_contig = 0;
484 int i, off;
485
Tejun Heofbf59bc2009-02-20 16:29:08 +0900486 for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++])) {
487 bool is_last = i + 1 == chunk->map_used;
488 int head, tail;
489
490 /* extra for alignment requirement */
491 head = ALIGN(off, align) - off;
492 BUG_ON(i == 0 && head != 0);
493
494 if (chunk->map[i] < 0)
495 continue;
496 if (chunk->map[i] < head + size) {
497 max_contig = max(chunk->map[i], max_contig);
498 continue;
499 }
500
501 /*
502 * If head is small or the previous block is free,
503 * merge'em. Note that 'small' is defined as smaller
504 * than sizeof(int), which is very small but isn't too
505 * uncommon for percpu allocations.
506 */
507 if (head && (head < sizeof(int) || chunk->map[i - 1] > 0)) {
508 if (chunk->map[i - 1] > 0)
509 chunk->map[i - 1] += head;
510 else {
511 chunk->map[i - 1] -= head;
512 chunk->free_size -= head;
513 }
514 chunk->map[i] -= head;
515 off += head;
516 head = 0;
517 }
518
519 /* if tail is small, just keep it around */
520 tail = chunk->map[i] - head - size;
521 if (tail < sizeof(int))
522 tail = 0;
523
524 /* split if warranted */
525 if (head || tail) {
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900526 pcpu_split_block(chunk, i, head, tail);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900527 if (head) {
528 i++;
529 off += head;
530 max_contig = max(chunk->map[i - 1], max_contig);
531 }
532 if (tail)
533 max_contig = max(chunk->map[i + 1], max_contig);
534 }
535
536 /* update hint and mark allocated */
537 if (is_last)
538 chunk->contig_hint = max_contig; /* fully scanned */
539 else
540 chunk->contig_hint = max(chunk->contig_hint,
541 max_contig);
542
543 chunk->free_size -= chunk->map[i];
544 chunk->map[i] = -chunk->map[i];
545
546 pcpu_chunk_relocate(chunk, oslot);
547 return off;
548 }
549
550 chunk->contig_hint = max_contig; /* fully scanned */
551 pcpu_chunk_relocate(chunk, oslot);
552
Tejun Heo9f7dcf22009-03-07 00:44:09 +0900553 /* tell the upper layer that this chunk has no matching area */
554 return -1;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900555}
556
557/**
558 * pcpu_free_area - free area to a pcpu_chunk
559 * @chunk: chunk of interest
560 * @freeme: offset of area to free
561 *
562 * Free area starting from @freeme to @chunk. Note that this function
563 * only modifies the allocation map. It doesn't depopulate or unmap
564 * the area.
Tejun Heoccea34b2009-03-07 00:44:13 +0900565 *
566 * CONTEXT:
567 * pcpu_lock.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900568 */
569static void pcpu_free_area(struct pcpu_chunk *chunk, int freeme)
570{
571 int oslot = pcpu_chunk_slot(chunk);
572 int i, off;
573
574 for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++]))
575 if (off == freeme)
576 break;
577 BUG_ON(off != freeme);
578 BUG_ON(chunk->map[i] > 0);
579
580 chunk->map[i] = -chunk->map[i];
581 chunk->free_size += chunk->map[i];
582
583 /* merge with previous? */
584 if (i > 0 && chunk->map[i - 1] >= 0) {
585 chunk->map[i - 1] += chunk->map[i];
586 chunk->map_used--;
587 memmove(&chunk->map[i], &chunk->map[i + 1],
588 (chunk->map_used - i) * sizeof(chunk->map[0]));
589 i--;
590 }
591 /* merge with next? */
592 if (i + 1 < chunk->map_used && chunk->map[i + 1] >= 0) {
593 chunk->map[i] += chunk->map[i + 1];
594 chunk->map_used--;
595 memmove(&chunk->map[i + 1], &chunk->map[i + 2],
596 (chunk->map_used - (i + 1)) * sizeof(chunk->map[0]));
597 }
598
599 chunk->contig_hint = max(chunk->map[i], chunk->contig_hint);
600 pcpu_chunk_relocate(chunk, oslot);
601}
602
Tejun Heo60810892010-04-09 18:57:01 +0900603static struct pcpu_chunk *pcpu_alloc_chunk(void)
604{
605 struct pcpu_chunk *chunk;
606
Bob Liu90459ce02011-08-04 11:02:33 +0200607 chunk = pcpu_mem_zalloc(pcpu_chunk_struct_size);
Tejun Heo60810892010-04-09 18:57:01 +0900608 if (!chunk)
609 return NULL;
610
Bob Liu90459ce02011-08-04 11:02:33 +0200611 chunk->map = pcpu_mem_zalloc(PCPU_DFL_MAP_ALLOC *
612 sizeof(chunk->map[0]));
Tejun Heo60810892010-04-09 18:57:01 +0900613 if (!chunk->map) {
614 kfree(chunk);
615 return NULL;
616 }
617
618 chunk->map_alloc = PCPU_DFL_MAP_ALLOC;
619 chunk->map[chunk->map_used++] = pcpu_unit_size;
620
621 INIT_LIST_HEAD(&chunk->list);
622 chunk->free_size = pcpu_unit_size;
623 chunk->contig_hint = pcpu_unit_size;
624
625 return chunk;
626}
627
628static void pcpu_free_chunk(struct pcpu_chunk *chunk)
629{
630 if (!chunk)
631 return;
632 pcpu_mem_free(chunk->map, chunk->map_alloc * sizeof(chunk->map[0]));
633 kfree(chunk);
634}
635
Tejun Heo9f645532010-04-09 18:57:01 +0900636/*
637 * Chunk management implementation.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900638 *
Tejun Heo9f645532010-04-09 18:57:01 +0900639 * To allow different implementations, chunk alloc/free and
640 * [de]population are implemented in a separate file which is pulled
641 * into this file and compiled together. The following functions
642 * should be implemented.
Tejun Heoce3141a2009-07-04 08:11:00 +0900643 *
Tejun Heo9f645532010-04-09 18:57:01 +0900644 * pcpu_populate_chunk - populate the specified range of a chunk
645 * pcpu_depopulate_chunk - depopulate the specified range of a chunk
646 * pcpu_create_chunk - create a new chunk
647 * pcpu_destroy_chunk - destroy a chunk, always preceded by full depop
648 * pcpu_addr_to_page - translate address to physical address
649 * pcpu_verify_alloc_info - check alloc_info is acceptable during init
Tejun Heofbf59bc2009-02-20 16:29:08 +0900650 */
Tejun Heo9f645532010-04-09 18:57:01 +0900651static int pcpu_populate_chunk(struct pcpu_chunk *chunk, int off, int size);
652static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk, int off, int size);
653static struct pcpu_chunk *pcpu_create_chunk(void);
654static void pcpu_destroy_chunk(struct pcpu_chunk *chunk);
655static struct page *pcpu_addr_to_page(void *addr);
656static int __init pcpu_verify_alloc_info(const struct pcpu_alloc_info *ai);
Tejun Heoce3141a2009-07-04 08:11:00 +0900657
Tejun Heob0c97782010-04-09 18:57:01 +0900658#ifdef CONFIG_NEED_PER_CPU_KM
659#include "percpu-km.c"
660#else
Tejun Heo9f645532010-04-09 18:57:01 +0900661#include "percpu-vm.c"
Tejun Heob0c97782010-04-09 18:57:01 +0900662#endif
Tejun Heofbf59bc2009-02-20 16:29:08 +0900663
664/**
Tejun Heo88999a82010-04-09 18:57:01 +0900665 * pcpu_chunk_addr_search - determine chunk containing specified address
666 * @addr: address for which the chunk needs to be determined.
667 *
668 * RETURNS:
669 * The address of the found chunk.
670 */
671static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
672{
673 /* is it in the first chunk? */
674 if (pcpu_addr_in_first_chunk(addr)) {
675 /* is it in the reserved area? */
676 if (pcpu_addr_in_reserved_chunk(addr))
677 return pcpu_reserved_chunk;
678 return pcpu_first_chunk;
679 }
680
681 /*
682 * The address is relative to unit0 which might be unused and
683 * thus unmapped. Offset the address to the unit space of the
684 * current processor before looking it up in the vmalloc
685 * space. Note that any possible cpu id can be used here, so
686 * there's no need to worry about preemption or cpu hotplug.
687 */
688 addr += pcpu_unit_offsets[raw_smp_processor_id()];
Tejun Heo9f645532010-04-09 18:57:01 +0900689 return pcpu_get_page_chunk(pcpu_addr_to_page(addr));
Tejun Heo88999a82010-04-09 18:57:01 +0900690}
691
692/**
Tejun Heoedcb4632009-03-06 14:33:59 +0900693 * pcpu_alloc - the percpu allocator
Tejun Heocae3aeb2009-02-21 16:56:23 +0900694 * @size: size of area to allocate in bytes
Tejun Heofbf59bc2009-02-20 16:29:08 +0900695 * @align: alignment of area (max PAGE_SIZE)
Tejun Heoedcb4632009-03-06 14:33:59 +0900696 * @reserved: allocate from the reserved chunk if available
Tejun Heofbf59bc2009-02-20 16:29:08 +0900697 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900698 * Allocate percpu area of @size bytes aligned at @align.
699 *
700 * CONTEXT:
701 * Does GFP_KERNEL allocation.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900702 *
703 * RETURNS:
704 * Percpu pointer to the allocated area on success, NULL on failure.
705 */
Tejun Heo43cf38e2010-02-02 14:38:57 +0900706static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900707{
Tejun Heof2badb02009-09-29 09:17:58 +0900708 static int warn_limit = 10;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900709 struct pcpu_chunk *chunk;
Tejun Heof2badb02009-09-29 09:17:58 +0900710 const char *err;
Tejun Heo833af842009-11-11 15:35:18 +0900711 int slot, off, new_alloc;
Jiri Kosina403a91b2009-10-29 00:25:59 +0900712 unsigned long flags;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900713
Tejun Heo8d408b42009-02-24 11:57:21 +0900714 if (unlikely(!size || size > PCPU_MIN_UNIT_SIZE || align > PAGE_SIZE)) {
Tejun Heofbf59bc2009-02-20 16:29:08 +0900715 WARN(true, "illegal size (%zu) or align (%zu) for "
716 "percpu allocation\n", size, align);
717 return NULL;
718 }
719
Tejun Heoccea34b2009-03-07 00:44:13 +0900720 mutex_lock(&pcpu_alloc_mutex);
Jiri Kosina403a91b2009-10-29 00:25:59 +0900721 spin_lock_irqsave(&pcpu_lock, flags);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900722
Tejun Heoedcb4632009-03-06 14:33:59 +0900723 /* serve reserved allocations from the reserved chunk if available */
724 if (reserved && pcpu_reserved_chunk) {
725 chunk = pcpu_reserved_chunk;
Tejun Heo833af842009-11-11 15:35:18 +0900726
727 if (size > chunk->contig_hint) {
728 err = "alloc from reserved chunk failed";
Tejun Heoccea34b2009-03-07 00:44:13 +0900729 goto fail_unlock;
Tejun Heof2badb02009-09-29 09:17:58 +0900730 }
Tejun Heo833af842009-11-11 15:35:18 +0900731
732 while ((new_alloc = pcpu_need_to_extend(chunk))) {
733 spin_unlock_irqrestore(&pcpu_lock, flags);
734 if (pcpu_extend_area_map(chunk, new_alloc) < 0) {
735 err = "failed to extend area map of reserved chunk";
736 goto fail_unlock_mutex;
737 }
738 spin_lock_irqsave(&pcpu_lock, flags);
739 }
740
Tejun Heoedcb4632009-03-06 14:33:59 +0900741 off = pcpu_alloc_area(chunk, size, align);
742 if (off >= 0)
743 goto area_found;
Tejun Heo833af842009-11-11 15:35:18 +0900744
Tejun Heof2badb02009-09-29 09:17:58 +0900745 err = "alloc from reserved chunk failed";
Tejun Heoccea34b2009-03-07 00:44:13 +0900746 goto fail_unlock;
Tejun Heoedcb4632009-03-06 14:33:59 +0900747 }
748
Tejun Heoccea34b2009-03-07 00:44:13 +0900749restart:
Tejun Heoedcb4632009-03-06 14:33:59 +0900750 /* search through normal chunks */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900751 for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) {
752 list_for_each_entry(chunk, &pcpu_slot[slot], list) {
753 if (size > chunk->contig_hint)
754 continue;
Tejun Heoccea34b2009-03-07 00:44:13 +0900755
Tejun Heo833af842009-11-11 15:35:18 +0900756 new_alloc = pcpu_need_to_extend(chunk);
757 if (new_alloc) {
758 spin_unlock_irqrestore(&pcpu_lock, flags);
759 if (pcpu_extend_area_map(chunk,
760 new_alloc) < 0) {
761 err = "failed to extend area map";
762 goto fail_unlock_mutex;
763 }
764 spin_lock_irqsave(&pcpu_lock, flags);
765 /*
766 * pcpu_lock has been dropped, need to
767 * restart cpu_slot list walking.
768 */
769 goto restart;
Tejun Heoccea34b2009-03-07 00:44:13 +0900770 }
771
Tejun Heofbf59bc2009-02-20 16:29:08 +0900772 off = pcpu_alloc_area(chunk, size, align);
773 if (off >= 0)
774 goto area_found;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900775 }
776 }
777
778 /* hmmm... no space left, create a new chunk */
Jiri Kosina403a91b2009-10-29 00:25:59 +0900779 spin_unlock_irqrestore(&pcpu_lock, flags);
Tejun Heoccea34b2009-03-07 00:44:13 +0900780
Tejun Heo60810892010-04-09 18:57:01 +0900781 chunk = pcpu_create_chunk();
Tejun Heof2badb02009-09-29 09:17:58 +0900782 if (!chunk) {
783 err = "failed to allocate new chunk";
Tejun Heoccea34b2009-03-07 00:44:13 +0900784 goto fail_unlock_mutex;
Tejun Heof2badb02009-09-29 09:17:58 +0900785 }
Tejun Heoccea34b2009-03-07 00:44:13 +0900786
Jiri Kosina403a91b2009-10-29 00:25:59 +0900787 spin_lock_irqsave(&pcpu_lock, flags);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900788 pcpu_chunk_relocate(chunk, -1);
Tejun Heoccea34b2009-03-07 00:44:13 +0900789 goto restart;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900790
791area_found:
Jiri Kosina403a91b2009-10-29 00:25:59 +0900792 spin_unlock_irqrestore(&pcpu_lock, flags);
Tejun Heoccea34b2009-03-07 00:44:13 +0900793
Tejun Heofbf59bc2009-02-20 16:29:08 +0900794 /* populate, map and clear the area */
795 if (pcpu_populate_chunk(chunk, off, size)) {
Jiri Kosina403a91b2009-10-29 00:25:59 +0900796 spin_lock_irqsave(&pcpu_lock, flags);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900797 pcpu_free_area(chunk, off);
Tejun Heof2badb02009-09-29 09:17:58 +0900798 err = "failed to populate";
Tejun Heoccea34b2009-03-07 00:44:13 +0900799 goto fail_unlock;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900800 }
801
Tejun Heoccea34b2009-03-07 00:44:13 +0900802 mutex_unlock(&pcpu_alloc_mutex);
803
Tejun Heobba174f2009-08-14 15:00:51 +0900804 /* return address relative to base address */
805 return __addr_to_pcpu_ptr(chunk->base_addr + off);
Tejun Heoccea34b2009-03-07 00:44:13 +0900806
807fail_unlock:
Jiri Kosina403a91b2009-10-29 00:25:59 +0900808 spin_unlock_irqrestore(&pcpu_lock, flags);
Tejun Heoccea34b2009-03-07 00:44:13 +0900809fail_unlock_mutex:
810 mutex_unlock(&pcpu_alloc_mutex);
Tejun Heof2badb02009-09-29 09:17:58 +0900811 if (warn_limit) {
812 pr_warning("PERCPU: allocation failed, size=%zu align=%zu, "
813 "%s\n", size, align, err);
814 dump_stack();
815 if (!--warn_limit)
816 pr_info("PERCPU: limit reached, disable warning\n");
817 }
Tejun Heoccea34b2009-03-07 00:44:13 +0900818 return NULL;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900819}
Tejun Heoedcb4632009-03-06 14:33:59 +0900820
821/**
822 * __alloc_percpu - allocate dynamic percpu area
823 * @size: size of area to allocate in bytes
824 * @align: alignment of area (max PAGE_SIZE)
825 *
Tejun Heo9329ba92010-09-10 11:01:56 +0200826 * Allocate zero-filled percpu area of @size bytes aligned at @align.
827 * Might sleep. Might trigger writeouts.
Tejun Heoedcb4632009-03-06 14:33:59 +0900828 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900829 * CONTEXT:
830 * Does GFP_KERNEL allocation.
831 *
Tejun Heoedcb4632009-03-06 14:33:59 +0900832 * RETURNS:
833 * Percpu pointer to the allocated area on success, NULL on failure.
834 */
Tejun Heo43cf38e2010-02-02 14:38:57 +0900835void __percpu *__alloc_percpu(size_t size, size_t align)
Tejun Heoedcb4632009-03-06 14:33:59 +0900836{
837 return pcpu_alloc(size, align, false);
838}
Tejun Heofbf59bc2009-02-20 16:29:08 +0900839EXPORT_SYMBOL_GPL(__alloc_percpu);
840
Tejun Heoedcb4632009-03-06 14:33:59 +0900841/**
842 * __alloc_reserved_percpu - allocate reserved percpu area
843 * @size: size of area to allocate in bytes
844 * @align: alignment of area (max PAGE_SIZE)
845 *
Tejun Heo9329ba92010-09-10 11:01:56 +0200846 * Allocate zero-filled percpu area of @size bytes aligned at @align
847 * from reserved percpu area if arch has set it up; otherwise,
848 * allocation is served from the same dynamic area. Might sleep.
849 * Might trigger writeouts.
Tejun Heoedcb4632009-03-06 14:33:59 +0900850 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900851 * CONTEXT:
852 * Does GFP_KERNEL allocation.
853 *
Tejun Heoedcb4632009-03-06 14:33:59 +0900854 * RETURNS:
855 * Percpu pointer to the allocated area on success, NULL on failure.
856 */
Tejun Heo43cf38e2010-02-02 14:38:57 +0900857void __percpu *__alloc_reserved_percpu(size_t size, size_t align)
Tejun Heoedcb4632009-03-06 14:33:59 +0900858{
859 return pcpu_alloc(size, align, true);
860}
861
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900862/**
863 * pcpu_reclaim - reclaim fully free chunks, workqueue function
864 * @work: unused
865 *
866 * Reclaim all fully free chunks except for the first one.
Tejun Heoccea34b2009-03-07 00:44:13 +0900867 *
868 * CONTEXT:
869 * workqueue context.
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900870 */
871static void pcpu_reclaim(struct work_struct *work)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900872{
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900873 LIST_HEAD(todo);
874 struct list_head *head = &pcpu_slot[pcpu_nr_slots - 1];
875 struct pcpu_chunk *chunk, *next;
876
Tejun Heoccea34b2009-03-07 00:44:13 +0900877 mutex_lock(&pcpu_alloc_mutex);
878 spin_lock_irq(&pcpu_lock);
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900879
880 list_for_each_entry_safe(chunk, next, head, list) {
881 WARN_ON(chunk->immutable);
882
883 /* spare the first one */
884 if (chunk == list_first_entry(head, struct pcpu_chunk, list))
885 continue;
886
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900887 list_move(&chunk->list, &todo);
888 }
889
Tejun Heoccea34b2009-03-07 00:44:13 +0900890 spin_unlock_irq(&pcpu_lock);
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900891
892 list_for_each_entry_safe(chunk, next, &todo, list) {
Tejun Heoce3141a2009-07-04 08:11:00 +0900893 pcpu_depopulate_chunk(chunk, 0, pcpu_unit_size);
Tejun Heo60810892010-04-09 18:57:01 +0900894 pcpu_destroy_chunk(chunk);
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900895 }
Tejun Heo971f3912009-08-14 15:00:49 +0900896
897 mutex_unlock(&pcpu_alloc_mutex);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900898}
899
900/**
901 * free_percpu - free percpu area
902 * @ptr: pointer to area to free
903 *
Tejun Heoccea34b2009-03-07 00:44:13 +0900904 * Free percpu area @ptr.
905 *
906 * CONTEXT:
907 * Can be called from atomic context.
Tejun Heofbf59bc2009-02-20 16:29:08 +0900908 */
Tejun Heo43cf38e2010-02-02 14:38:57 +0900909void free_percpu(void __percpu *ptr)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900910{
Andrew Morton129182e2010-01-08 14:42:39 -0800911 void *addr;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900912 struct pcpu_chunk *chunk;
Tejun Heoccea34b2009-03-07 00:44:13 +0900913 unsigned long flags;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900914 int off;
915
916 if (!ptr)
917 return;
918
Andrew Morton129182e2010-01-08 14:42:39 -0800919 addr = __pcpu_ptr_to_addr(ptr);
920
Tejun Heoccea34b2009-03-07 00:44:13 +0900921 spin_lock_irqsave(&pcpu_lock, flags);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900922
923 chunk = pcpu_chunk_addr_search(addr);
Tejun Heobba174f2009-08-14 15:00:51 +0900924 off = addr - chunk->base_addr;
Tejun Heofbf59bc2009-02-20 16:29:08 +0900925
926 pcpu_free_area(chunk, off);
927
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900928 /* if there are more than one fully free chunks, wake up grim reaper */
Tejun Heofbf59bc2009-02-20 16:29:08 +0900929 if (chunk->free_size == pcpu_unit_size) {
930 struct pcpu_chunk *pos;
931
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900932 list_for_each_entry(pos, &pcpu_slot[pcpu_nr_slots - 1], list)
Tejun Heofbf59bc2009-02-20 16:29:08 +0900933 if (pos != chunk) {
Tejun Heoa56dbdd2009-03-07 00:44:11 +0900934 schedule_work(&pcpu_reclaim_work);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900935 break;
936 }
937 }
938
Tejun Heoccea34b2009-03-07 00:44:13 +0900939 spin_unlock_irqrestore(&pcpu_lock, flags);
Tejun Heofbf59bc2009-02-20 16:29:08 +0900940}
941EXPORT_SYMBOL_GPL(free_percpu);
942
Vivek Goyal3b034b02009-11-24 15:50:03 +0900943/**
Tejun Heo10fad5e2010-03-10 18:57:54 +0900944 * is_kernel_percpu_address - test whether address is from static percpu area
945 * @addr: address to test
946 *
947 * Test whether @addr belongs to in-kernel static percpu area. Module
948 * static percpu areas are not considered. For those, use
949 * is_module_percpu_address().
950 *
951 * RETURNS:
952 * %true if @addr is from in-kernel static percpu area, %false otherwise.
953 */
954bool is_kernel_percpu_address(unsigned long addr)
955{
Tejun Heobbddff02010-09-03 18:22:48 +0200956#ifdef CONFIG_SMP
Tejun Heo10fad5e2010-03-10 18:57:54 +0900957 const size_t static_size = __per_cpu_end - __per_cpu_start;
958 void __percpu *base = __addr_to_pcpu_ptr(pcpu_base_addr);
959 unsigned int cpu;
960
961 for_each_possible_cpu(cpu) {
962 void *start = per_cpu_ptr(base, cpu);
963
964 if ((void *)addr >= start && (void *)addr < start + static_size)
965 return true;
966 }
Tejun Heobbddff02010-09-03 18:22:48 +0200967#endif
968 /* on UP, can't distinguish from other static vars, always false */
Tejun Heo10fad5e2010-03-10 18:57:54 +0900969 return false;
970}
971
972/**
Vivek Goyal3b034b02009-11-24 15:50:03 +0900973 * per_cpu_ptr_to_phys - convert translated percpu address to physical address
974 * @addr: the address to be converted to physical address
975 *
976 * Given @addr which is dereferenceable address obtained via one of
977 * percpu access macros, this function translates it into its physical
978 * address. The caller is responsible for ensuring @addr stays valid
979 * until this function finishes.
980 *
Dave Young67589c72011-11-23 08:20:53 -0800981 * percpu allocator has special setup for the first chunk, which currently
982 * supports either embedding in linear address space or vmalloc mapping,
983 * and, from the second one, the backing allocator (currently either vm or
984 * km) provides translation.
985 *
986 * The addr can be tranlated simply without checking if it falls into the
987 * first chunk. But the current code reflects better how percpu allocator
988 * actually works, and the verification can discover both bugs in percpu
989 * allocator itself and per_cpu_ptr_to_phys() callers. So we keep current
990 * code.
991 *
Vivek Goyal3b034b02009-11-24 15:50:03 +0900992 * RETURNS:
993 * The physical address for @addr.
994 */
995phys_addr_t per_cpu_ptr_to_phys(void *addr)
996{
Tejun Heo9983b6f02010-06-18 11:44:31 +0200997 void __percpu *base = __addr_to_pcpu_ptr(pcpu_base_addr);
998 bool in_first_chunk = false;
Tejun Heoa855b842011-11-18 10:55:35 -0800999 unsigned long first_low, first_high;
Tejun Heo9983b6f02010-06-18 11:44:31 +02001000 unsigned int cpu;
1001
1002 /*
Tejun Heoa855b842011-11-18 10:55:35 -08001003 * The following test on unit_low/high isn't strictly
Tejun Heo9983b6f02010-06-18 11:44:31 +02001004 * necessary but will speed up lookups of addresses which
1005 * aren't in the first chunk.
1006 */
Tejun Heoa855b842011-11-18 10:55:35 -08001007 first_low = pcpu_chunk_addr(pcpu_first_chunk, pcpu_low_unit_cpu, 0);
1008 first_high = pcpu_chunk_addr(pcpu_first_chunk, pcpu_high_unit_cpu,
1009 pcpu_unit_pages);
1010 if ((unsigned long)addr >= first_low &&
1011 (unsigned long)addr < first_high) {
Tejun Heo9983b6f02010-06-18 11:44:31 +02001012 for_each_possible_cpu(cpu) {
1013 void *start = per_cpu_ptr(base, cpu);
1014
1015 if (addr >= start && addr < start + pcpu_unit_size) {
1016 in_first_chunk = true;
1017 break;
1018 }
1019 }
1020 }
1021
1022 if (in_first_chunk) {
David Howellseac522e2011-03-28 12:53:29 +01001023 if (!is_vmalloc_addr(addr))
Tejun Heo020ec652010-04-09 18:57:00 +09001024 return __pa(addr);
1025 else
1026 return page_to_phys(vmalloc_to_page(addr));
1027 } else
Tejun Heo9f645532010-04-09 18:57:01 +09001028 return page_to_phys(pcpu_addr_to_page(addr));
Vivek Goyal3b034b02009-11-24 15:50:03 +09001029}
1030
Tejun Heofbf59bc2009-02-20 16:29:08 +09001031/**
Tejun Heofd1e8a12009-08-14 15:00:51 +09001032 * pcpu_alloc_alloc_info - allocate percpu allocation info
1033 * @nr_groups: the number of groups
1034 * @nr_units: the number of units
Tejun Heo033e48f2009-08-14 15:00:51 +09001035 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001036 * Allocate ai which is large enough for @nr_groups groups containing
1037 * @nr_units units. The returned ai's groups[0].cpu_map points to the
1038 * cpu_map array which is long enough for @nr_units and filled with
1039 * NR_CPUS. It's the caller's responsibility to initialize cpu_map
1040 * pointer of other groups.
Tejun Heo033e48f2009-08-14 15:00:51 +09001041 *
1042 * RETURNS:
Tejun Heofd1e8a12009-08-14 15:00:51 +09001043 * Pointer to the allocated pcpu_alloc_info on success, NULL on
1044 * failure.
Tejun Heo033e48f2009-08-14 15:00:51 +09001045 */
Tejun Heofd1e8a12009-08-14 15:00:51 +09001046struct pcpu_alloc_info * __init pcpu_alloc_alloc_info(int nr_groups,
1047 int nr_units)
1048{
1049 struct pcpu_alloc_info *ai;
1050 size_t base_size, ai_size;
1051 void *ptr;
1052 int unit;
1053
1054 base_size = ALIGN(sizeof(*ai) + nr_groups * sizeof(ai->groups[0]),
1055 __alignof__(ai->groups[0].cpu_map[0]));
1056 ai_size = base_size + nr_units * sizeof(ai->groups[0].cpu_map[0]);
1057
1058 ptr = alloc_bootmem_nopanic(PFN_ALIGN(ai_size));
1059 if (!ptr)
1060 return NULL;
1061 ai = ptr;
1062 ptr += base_size;
1063
1064 ai->groups[0].cpu_map = ptr;
1065
1066 for (unit = 0; unit < nr_units; unit++)
1067 ai->groups[0].cpu_map[unit] = NR_CPUS;
1068
1069 ai->nr_groups = nr_groups;
1070 ai->__ai_size = PFN_ALIGN(ai_size);
1071
1072 return ai;
1073}
1074
1075/**
1076 * pcpu_free_alloc_info - free percpu allocation info
1077 * @ai: pcpu_alloc_info to free
1078 *
1079 * Free @ai which was allocated by pcpu_alloc_alloc_info().
1080 */
1081void __init pcpu_free_alloc_info(struct pcpu_alloc_info *ai)
1082{
1083 free_bootmem(__pa(ai), ai->__ai_size);
1084}
1085
1086/**
Tejun Heofd1e8a12009-08-14 15:00:51 +09001087 * pcpu_dump_alloc_info - print out information about pcpu_alloc_info
1088 * @lvl: loglevel
1089 * @ai: allocation info to dump
1090 *
1091 * Print out information about @ai using loglevel @lvl.
1092 */
1093static void pcpu_dump_alloc_info(const char *lvl,
1094 const struct pcpu_alloc_info *ai)
Tejun Heo033e48f2009-08-14 15:00:51 +09001095{
Tejun Heofd1e8a12009-08-14 15:00:51 +09001096 int group_width = 1, cpu_width = 1, width;
Tejun Heo033e48f2009-08-14 15:00:51 +09001097 char empty_str[] = "--------";
Tejun Heofd1e8a12009-08-14 15:00:51 +09001098 int alloc = 0, alloc_end = 0;
1099 int group, v;
1100 int upa, apl; /* units per alloc, allocs per line */
Tejun Heo033e48f2009-08-14 15:00:51 +09001101
Tejun Heofd1e8a12009-08-14 15:00:51 +09001102 v = ai->nr_groups;
Tejun Heo033e48f2009-08-14 15:00:51 +09001103 while (v /= 10)
Tejun Heofd1e8a12009-08-14 15:00:51 +09001104 group_width++;
Tejun Heo033e48f2009-08-14 15:00:51 +09001105
Tejun Heofd1e8a12009-08-14 15:00:51 +09001106 v = num_possible_cpus();
1107 while (v /= 10)
1108 cpu_width++;
1109 empty_str[min_t(int, cpu_width, sizeof(empty_str) - 1)] = '\0';
Tejun Heo033e48f2009-08-14 15:00:51 +09001110
Tejun Heofd1e8a12009-08-14 15:00:51 +09001111 upa = ai->alloc_size / ai->unit_size;
1112 width = upa * (cpu_width + 1) + group_width + 3;
1113 apl = rounddown_pow_of_two(max(60 / width, 1));
Tejun Heo033e48f2009-08-14 15:00:51 +09001114
Tejun Heofd1e8a12009-08-14 15:00:51 +09001115 printk("%spcpu-alloc: s%zu r%zu d%zu u%zu alloc=%zu*%zu",
1116 lvl, ai->static_size, ai->reserved_size, ai->dyn_size,
1117 ai->unit_size, ai->alloc_size / ai->atom_size, ai->atom_size);
1118
1119 for (group = 0; group < ai->nr_groups; group++) {
1120 const struct pcpu_group_info *gi = &ai->groups[group];
1121 int unit = 0, unit_end = 0;
1122
1123 BUG_ON(gi->nr_units % upa);
1124 for (alloc_end += gi->nr_units / upa;
1125 alloc < alloc_end; alloc++) {
1126 if (!(alloc % apl)) {
Tejun Heo033e48f2009-08-14 15:00:51 +09001127 printk("\n");
Tejun Heofd1e8a12009-08-14 15:00:51 +09001128 printk("%spcpu-alloc: ", lvl);
1129 }
1130 printk("[%0*d] ", group_width, group);
1131
1132 for (unit_end += upa; unit < unit_end; unit++)
1133 if (gi->cpu_map[unit] != NR_CPUS)
1134 printk("%0*d ", cpu_width,
1135 gi->cpu_map[unit]);
1136 else
1137 printk("%s ", empty_str);
Tejun Heo033e48f2009-08-14 15:00:51 +09001138 }
Tejun Heo033e48f2009-08-14 15:00:51 +09001139 }
1140 printk("\n");
1141}
Tejun Heo033e48f2009-08-14 15:00:51 +09001142
Tejun Heofbf59bc2009-02-20 16:29:08 +09001143/**
Tejun Heo8d408b42009-02-24 11:57:21 +09001144 * pcpu_setup_first_chunk - initialize the first percpu chunk
Tejun Heofd1e8a12009-08-14 15:00:51 +09001145 * @ai: pcpu_alloc_info describing how to percpu area is shaped
Tejun Heo38a6be52009-07-04 08:10:59 +09001146 * @base_addr: mapped address
Tejun Heofbf59bc2009-02-20 16:29:08 +09001147 *
Tejun Heo8d408b42009-02-24 11:57:21 +09001148 * Initialize the first percpu chunk which contains the kernel static
1149 * perpcu area. This function is to be called from arch percpu area
Tejun Heo38a6be52009-07-04 08:10:59 +09001150 * setup path.
Tejun Heo8d408b42009-02-24 11:57:21 +09001151 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001152 * @ai contains all information necessary to initialize the first
1153 * chunk and prime the dynamic percpu allocator.
Tejun Heo8d408b42009-02-24 11:57:21 +09001154 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001155 * @ai->static_size is the size of static percpu area.
1156 *
1157 * @ai->reserved_size, if non-zero, specifies the amount of bytes to
Tejun Heoedcb4632009-03-06 14:33:59 +09001158 * reserve after the static area in the first chunk. This reserves
1159 * the first chunk such that it's available only through reserved
1160 * percpu allocation. This is primarily used to serve module percpu
1161 * static areas on architectures where the addressing model has
1162 * limited offset range for symbol relocations to guarantee module
1163 * percpu symbols fall inside the relocatable range.
1164 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001165 * @ai->dyn_size determines the number of bytes available for dynamic
1166 * allocation in the first chunk. The area between @ai->static_size +
1167 * @ai->reserved_size + @ai->dyn_size and @ai->unit_size is unused.
Tejun Heo6074d5b2009-03-10 16:27:48 +09001168 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001169 * @ai->unit_size specifies unit size and must be aligned to PAGE_SIZE
1170 * and equal to or larger than @ai->static_size + @ai->reserved_size +
1171 * @ai->dyn_size.
Tejun Heo8d408b42009-02-24 11:57:21 +09001172 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001173 * @ai->atom_size is the allocation atom size and used as alignment
1174 * for vm areas.
Tejun Heo8d408b42009-02-24 11:57:21 +09001175 *
Tejun Heofd1e8a12009-08-14 15:00:51 +09001176 * @ai->alloc_size is the allocation size and always multiple of
1177 * @ai->atom_size. This is larger than @ai->atom_size if
1178 * @ai->unit_size is larger than @ai->atom_size.
1179 *
1180 * @ai->nr_groups and @ai->groups describe virtual memory layout of
1181 * percpu areas. Units which should be colocated are put into the
1182 * same group. Dynamic VM areas will be allocated according to these
1183 * groupings. If @ai->nr_groups is zero, a single group containing
1184 * all units is assumed.
Tejun Heo8d408b42009-02-24 11:57:21 +09001185 *
Tejun Heo38a6be52009-07-04 08:10:59 +09001186 * The caller should have mapped the first chunk at @base_addr and
1187 * copied static data to each unit.
Tejun Heofbf59bc2009-02-20 16:29:08 +09001188 *
Tejun Heoedcb4632009-03-06 14:33:59 +09001189 * If the first chunk ends up with both reserved and dynamic areas, it
1190 * is served by two chunks - one to serve the core static and reserved
1191 * areas and the other for the dynamic area. They share the same vm
1192 * and page map but uses different area allocation map to stay away
1193 * from each other. The latter chunk is circulated in the chunk slots
1194 * and available for dynamic allocation like any other chunks.
1195 *
Tejun Heofbf59bc2009-02-20 16:29:08 +09001196 * RETURNS:
Tejun Heofb435d52009-08-14 15:00:51 +09001197 * 0 on success, -errno on failure.
Tejun Heofbf59bc2009-02-20 16:29:08 +09001198 */
Tejun Heofb435d52009-08-14 15:00:51 +09001199int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
1200 void *base_addr)
Tejun Heofbf59bc2009-02-20 16:29:08 +09001201{
Tejun Heo635b75f2009-09-24 09:43:11 +09001202 static char cpus_buf[4096] __initdata;
Tejun Heo099a19d2010-06-27 18:50:00 +02001203 static int smap[PERCPU_DYNAMIC_EARLY_SLOTS] __initdata;
1204 static int dmap[PERCPU_DYNAMIC_EARLY_SLOTS] __initdata;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001205 size_t dyn_size = ai->dyn_size;
1206 size_t size_sum = ai->static_size + ai->reserved_size + dyn_size;
Tejun Heoedcb4632009-03-06 14:33:59 +09001207 struct pcpu_chunk *schunk, *dchunk = NULL;
Tejun Heo65632972009-08-14 15:00:52 +09001208 unsigned long *group_offsets;
1209 size_t *group_sizes;
Tejun Heofb435d52009-08-14 15:00:51 +09001210 unsigned long *unit_off;
Tejun Heofbf59bc2009-02-20 16:29:08 +09001211 unsigned int cpu;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001212 int *unit_map;
1213 int group, unit, i;
Tejun Heofbf59bc2009-02-20 16:29:08 +09001214
Tejun Heo635b75f2009-09-24 09:43:11 +09001215 cpumask_scnprintf(cpus_buf, sizeof(cpus_buf), cpu_possible_mask);
1216
1217#define PCPU_SETUP_BUG_ON(cond) do { \
1218 if (unlikely(cond)) { \
1219 pr_emerg("PERCPU: failed to initialize, %s", #cond); \
1220 pr_emerg("PERCPU: cpu_possible_mask=%s\n", cpus_buf); \
1221 pcpu_dump_alloc_info(KERN_EMERG, ai); \
1222 BUG(); \
1223 } \
1224} while (0)
1225
Tejun Heo2f39e632009-07-04 08:11:00 +09001226 /* sanity checks */
Tejun Heo635b75f2009-09-24 09:43:11 +09001227 PCPU_SETUP_BUG_ON(ai->nr_groups <= 0);
Tejun Heobbddff02010-09-03 18:22:48 +02001228#ifdef CONFIG_SMP
Tejun Heo635b75f2009-09-24 09:43:11 +09001229 PCPU_SETUP_BUG_ON(!ai->static_size);
Tejun Heo0415b00d12011-03-24 18:50:09 +01001230 PCPU_SETUP_BUG_ON((unsigned long)__per_cpu_start & ~PAGE_MASK);
Tejun Heobbddff02010-09-03 18:22:48 +02001231#endif
Tejun Heo635b75f2009-09-24 09:43:11 +09001232 PCPU_SETUP_BUG_ON(!base_addr);
Tejun Heo0415b00d12011-03-24 18:50:09 +01001233 PCPU_SETUP_BUG_ON((unsigned long)base_addr & ~PAGE_MASK);
Tejun Heo635b75f2009-09-24 09:43:11 +09001234 PCPU_SETUP_BUG_ON(ai->unit_size < size_sum);
1235 PCPU_SETUP_BUG_ON(ai->unit_size & ~PAGE_MASK);
1236 PCPU_SETUP_BUG_ON(ai->unit_size < PCPU_MIN_UNIT_SIZE);
Tejun Heo099a19d2010-06-27 18:50:00 +02001237 PCPU_SETUP_BUG_ON(ai->dyn_size < PERCPU_DYNAMIC_EARLY_SIZE);
Tejun Heo9f645532010-04-09 18:57:01 +09001238 PCPU_SETUP_BUG_ON(pcpu_verify_alloc_info(ai) < 0);
Tejun Heo8d408b42009-02-24 11:57:21 +09001239
Tejun Heo65632972009-08-14 15:00:52 +09001240 /* process group information and build config tables accordingly */
1241 group_offsets = alloc_bootmem(ai->nr_groups * sizeof(group_offsets[0]));
1242 group_sizes = alloc_bootmem(ai->nr_groups * sizeof(group_sizes[0]));
Tejun Heofd1e8a12009-08-14 15:00:51 +09001243 unit_map = alloc_bootmem(nr_cpu_ids * sizeof(unit_map[0]));
Tejun Heofb435d52009-08-14 15:00:51 +09001244 unit_off = alloc_bootmem(nr_cpu_ids * sizeof(unit_off[0]));
Tejun Heo2f39e632009-07-04 08:11:00 +09001245
Tejun Heofd1e8a12009-08-14 15:00:51 +09001246 for (cpu = 0; cpu < nr_cpu_ids; cpu++)
Tejun Heoffe0d5a2009-09-29 09:17:56 +09001247 unit_map[cpu] = UINT_MAX;
Tejun Heoa855b842011-11-18 10:55:35 -08001248
1249 pcpu_low_unit_cpu = NR_CPUS;
1250 pcpu_high_unit_cpu = NR_CPUS;
Tejun Heo2f39e632009-07-04 08:11:00 +09001251
Tejun Heofd1e8a12009-08-14 15:00:51 +09001252 for (group = 0, unit = 0; group < ai->nr_groups; group++, unit += i) {
1253 const struct pcpu_group_info *gi = &ai->groups[group];
Tejun Heo2f39e632009-07-04 08:11:00 +09001254
Tejun Heo65632972009-08-14 15:00:52 +09001255 group_offsets[group] = gi->base_offset;
1256 group_sizes[group] = gi->nr_units * ai->unit_size;
1257
Tejun Heofd1e8a12009-08-14 15:00:51 +09001258 for (i = 0; i < gi->nr_units; i++) {
1259 cpu = gi->cpu_map[i];
1260 if (cpu == NR_CPUS)
1261 continue;
1262
Tejun Heo635b75f2009-09-24 09:43:11 +09001263 PCPU_SETUP_BUG_ON(cpu > nr_cpu_ids);
1264 PCPU_SETUP_BUG_ON(!cpu_possible(cpu));
1265 PCPU_SETUP_BUG_ON(unit_map[cpu] != UINT_MAX);
Tejun Heofd1e8a12009-08-14 15:00:51 +09001266
1267 unit_map[cpu] = unit + i;
Tejun Heofb435d52009-08-14 15:00:51 +09001268 unit_off[cpu] = gi->base_offset + i * ai->unit_size;
1269
Tejun Heoa855b842011-11-18 10:55:35 -08001270 /* determine low/high unit_cpu */
1271 if (pcpu_low_unit_cpu == NR_CPUS ||
1272 unit_off[cpu] < unit_off[pcpu_low_unit_cpu])
1273 pcpu_low_unit_cpu = cpu;
1274 if (pcpu_high_unit_cpu == NR_CPUS ||
1275 unit_off[cpu] > unit_off[pcpu_high_unit_cpu])
1276 pcpu_high_unit_cpu = cpu;
Tejun Heo2f39e632009-07-04 08:11:00 +09001277 }
Tejun Heo2f39e632009-07-04 08:11:00 +09001278 }
Tejun Heofd1e8a12009-08-14 15:00:51 +09001279 pcpu_nr_units = unit;
1280
1281 for_each_possible_cpu(cpu)
Tejun Heo635b75f2009-09-24 09:43:11 +09001282 PCPU_SETUP_BUG_ON(unit_map[cpu] == UINT_MAX);
1283
1284 /* we're done parsing the input, undefine BUG macro and dump config */
1285#undef PCPU_SETUP_BUG_ON
Tejun Heobcbea792010-12-22 14:19:14 +01001286 pcpu_dump_alloc_info(KERN_DEBUG, ai);
Tejun Heofd1e8a12009-08-14 15:00:51 +09001287
Tejun Heo65632972009-08-14 15:00:52 +09001288 pcpu_nr_groups = ai->nr_groups;
1289 pcpu_group_offsets = group_offsets;
1290 pcpu_group_sizes = group_sizes;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001291 pcpu_unit_map = unit_map;
Tejun Heofb435d52009-08-14 15:00:51 +09001292 pcpu_unit_offsets = unit_off;
Tejun Heo2f39e632009-07-04 08:11:00 +09001293
1294 /* determine basic parameters */
Tejun Heofd1e8a12009-08-14 15:00:51 +09001295 pcpu_unit_pages = ai->unit_size >> PAGE_SHIFT;
Tejun Heod9b55ee2009-02-24 11:57:21 +09001296 pcpu_unit_size = pcpu_unit_pages << PAGE_SHIFT;
Tejun Heo65632972009-08-14 15:00:52 +09001297 pcpu_atom_size = ai->atom_size;
Tejun Heoce3141a2009-07-04 08:11:00 +09001298 pcpu_chunk_struct_size = sizeof(struct pcpu_chunk) +
1299 BITS_TO_LONGS(pcpu_unit_pages) * sizeof(unsigned long);
Tejun Heocafe8812009-03-06 14:33:59 +09001300
Tejun Heod9b55ee2009-02-24 11:57:21 +09001301 /*
1302 * Allocate chunk slots. The additional last slot is for
1303 * empty chunks.
1304 */
1305 pcpu_nr_slots = __pcpu_size_to_slot(pcpu_unit_size) + 2;
Tejun Heofbf59bc2009-02-20 16:29:08 +09001306 pcpu_slot = alloc_bootmem(pcpu_nr_slots * sizeof(pcpu_slot[0]));
1307 for (i = 0; i < pcpu_nr_slots; i++)
1308 INIT_LIST_HEAD(&pcpu_slot[i]);
1309
Tejun Heoedcb4632009-03-06 14:33:59 +09001310 /*
1311 * Initialize static chunk. If reserved_size is zero, the
1312 * static chunk covers static area + dynamic allocation area
1313 * in the first chunk. If reserved_size is not zero, it
1314 * covers static area + reserved area (mostly used for module
1315 * static percpu allocation).
1316 */
Tejun Heo2441d152009-03-06 14:33:59 +09001317 schunk = alloc_bootmem(pcpu_chunk_struct_size);
1318 INIT_LIST_HEAD(&schunk->list);
Tejun Heobba174f2009-08-14 15:00:51 +09001319 schunk->base_addr = base_addr;
Tejun Heo61ace7f2009-03-06 14:33:59 +09001320 schunk->map = smap;
1321 schunk->map_alloc = ARRAY_SIZE(smap);
Tejun Heo38a6be52009-07-04 08:10:59 +09001322 schunk->immutable = true;
Tejun Heoce3141a2009-07-04 08:11:00 +09001323 bitmap_fill(schunk->populated, pcpu_unit_pages);
Tejun Heoedcb4632009-03-06 14:33:59 +09001324
Tejun Heofd1e8a12009-08-14 15:00:51 +09001325 if (ai->reserved_size) {
1326 schunk->free_size = ai->reserved_size;
Tejun Heoae9e6bc92009-04-02 13:19:54 +09001327 pcpu_reserved_chunk = schunk;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001328 pcpu_reserved_chunk_limit = ai->static_size + ai->reserved_size;
Tejun Heoedcb4632009-03-06 14:33:59 +09001329 } else {
1330 schunk->free_size = dyn_size;
1331 dyn_size = 0; /* dynamic area covered */
1332 }
Tejun Heo2441d152009-03-06 14:33:59 +09001333 schunk->contig_hint = schunk->free_size;
Tejun Heofbf59bc2009-02-20 16:29:08 +09001334
Tejun Heofd1e8a12009-08-14 15:00:51 +09001335 schunk->map[schunk->map_used++] = -ai->static_size;
Tejun Heo61ace7f2009-03-06 14:33:59 +09001336 if (schunk->free_size)
1337 schunk->map[schunk->map_used++] = schunk->free_size;
1338
Tejun Heoedcb4632009-03-06 14:33:59 +09001339 /* init dynamic chunk if necessary */
1340 if (dyn_size) {
Tejun Heoce3141a2009-07-04 08:11:00 +09001341 dchunk = alloc_bootmem(pcpu_chunk_struct_size);
Tejun Heoedcb4632009-03-06 14:33:59 +09001342 INIT_LIST_HEAD(&dchunk->list);
Tejun Heobba174f2009-08-14 15:00:51 +09001343 dchunk->base_addr = base_addr;
Tejun Heoedcb4632009-03-06 14:33:59 +09001344 dchunk->map = dmap;
1345 dchunk->map_alloc = ARRAY_SIZE(dmap);
Tejun Heo38a6be52009-07-04 08:10:59 +09001346 dchunk->immutable = true;
Tejun Heoce3141a2009-07-04 08:11:00 +09001347 bitmap_fill(dchunk->populated, pcpu_unit_pages);
Tejun Heoedcb4632009-03-06 14:33:59 +09001348
1349 dchunk->contig_hint = dchunk->free_size = dyn_size;
1350 dchunk->map[dchunk->map_used++] = -pcpu_reserved_chunk_limit;
1351 dchunk->map[dchunk->map_used++] = dchunk->free_size;
1352 }
1353
Tejun Heo2441d152009-03-06 14:33:59 +09001354 /* link the first chunk in */
Tejun Heoae9e6bc92009-04-02 13:19:54 +09001355 pcpu_first_chunk = dchunk ?: schunk;
1356 pcpu_chunk_relocate(pcpu_first_chunk, -1);
Tejun Heofbf59bc2009-02-20 16:29:08 +09001357
1358 /* we're done */
Tejun Heobba174f2009-08-14 15:00:51 +09001359 pcpu_base_addr = base_addr;
Tejun Heofb435d52009-08-14 15:00:51 +09001360 return 0;
Tejun Heofbf59bc2009-02-20 16:29:08 +09001361}
Tejun Heo66c3a752009-03-10 16:27:48 +09001362
Tejun Heobbddff02010-09-03 18:22:48 +02001363#ifdef CONFIG_SMP
1364
Tejun Heof58dc012009-08-14 15:00:50 +09001365const char *pcpu_fc_names[PCPU_FC_NR] __initdata = {
1366 [PCPU_FC_AUTO] = "auto",
1367 [PCPU_FC_EMBED] = "embed",
1368 [PCPU_FC_PAGE] = "page",
Tejun Heof58dc012009-08-14 15:00:50 +09001369};
Tejun Heo66c3a752009-03-10 16:27:48 +09001370
Tejun Heof58dc012009-08-14 15:00:50 +09001371enum pcpu_fc pcpu_chosen_fc __initdata = PCPU_FC_AUTO;
1372
1373static int __init percpu_alloc_setup(char *str)
Tejun Heo66c3a752009-03-10 16:27:48 +09001374{
Tejun Heof58dc012009-08-14 15:00:50 +09001375 if (0)
1376 /* nada */;
1377#ifdef CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK
1378 else if (!strcmp(str, "embed"))
1379 pcpu_chosen_fc = PCPU_FC_EMBED;
1380#endif
1381#ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
1382 else if (!strcmp(str, "page"))
1383 pcpu_chosen_fc = PCPU_FC_PAGE;
1384#endif
Tejun Heof58dc012009-08-14 15:00:50 +09001385 else
1386 pr_warning("PERCPU: unknown allocator %s specified\n", str);
Tejun Heo66c3a752009-03-10 16:27:48 +09001387
Tejun Heof58dc012009-08-14 15:00:50 +09001388 return 0;
Tejun Heo66c3a752009-03-10 16:27:48 +09001389}
Tejun Heof58dc012009-08-14 15:00:50 +09001390early_param("percpu_alloc", percpu_alloc_setup);
Tejun Heo66c3a752009-03-10 16:27:48 +09001391
Tejun Heo3c9a0242010-09-09 18:00:15 +02001392/*
1393 * pcpu_embed_first_chunk() is used by the generic percpu setup.
1394 * Build it if needed by the arch config or the generic setup is going
1395 * to be used.
1396 */
Tejun Heo08fc4582009-08-14 15:00:49 +09001397#if defined(CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK) || \
1398 !defined(CONFIG_HAVE_SETUP_PER_CPU_AREA)
Tejun Heo3c9a0242010-09-09 18:00:15 +02001399#define BUILD_EMBED_FIRST_CHUNK
1400#endif
1401
1402/* build pcpu_page_first_chunk() iff needed by the arch config */
1403#if defined(CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK)
1404#define BUILD_PAGE_FIRST_CHUNK
1405#endif
1406
1407/* pcpu_build_alloc_info() is used by both embed and page first chunk */
1408#if defined(BUILD_EMBED_FIRST_CHUNK) || defined(BUILD_PAGE_FIRST_CHUNK)
1409/**
Tejun Heofbf59bc2009-02-20 16:29:08 +09001410 * pcpu_build_alloc_info - build alloc_info considering distances between CPUs
1411 * @reserved_size: the size of reserved percpu area in bytes
1412 * @dyn_size: minimum free size for dynamic allocation in bytes
1413 * @atom_size: allocation atom size
1414 * @cpu_distance_fn: callback to determine distance between cpus, optional
1415 *
1416 * This function determines grouping of units, their mappings to cpus
1417 * and other parameters considering needed percpu size, allocation
1418 * atom size and distances between CPUs.
1419 *
1420 * Groups are always mutliples of atom size and CPUs which are of
1421 * LOCAL_DISTANCE both ways are grouped together and share space for
1422 * units in the same group. The returned configuration is guaranteed
1423 * to have CPUs on different nodes on different groups and >=75% usage
1424 * of allocated virtual address space.
1425 *
1426 * RETURNS:
1427 * On success, pointer to the new allocation_info is returned. On
1428 * failure, ERR_PTR value is returned.
1429 */
1430static struct pcpu_alloc_info * __init pcpu_build_alloc_info(
1431 size_t reserved_size, size_t dyn_size,
1432 size_t atom_size,
1433 pcpu_fc_cpu_distance_fn_t cpu_distance_fn)
1434{
1435 static int group_map[NR_CPUS] __initdata;
1436 static int group_cnt[NR_CPUS] __initdata;
1437 const size_t static_size = __per_cpu_end - __per_cpu_start;
1438 int nr_groups = 1, nr_units = 0;
1439 size_t size_sum, min_unit_size, alloc_size;
1440 int upa, max_upa, uninitialized_var(best_upa); /* units_per_alloc */
1441 int last_allocs, group, unit;
1442 unsigned int cpu, tcpu;
1443 struct pcpu_alloc_info *ai;
1444 unsigned int *cpu_map;
1445
1446 /* this function may be called multiple times */
1447 memset(group_map, 0, sizeof(group_map));
1448 memset(group_cnt, 0, sizeof(group_cnt));
1449
1450 /* calculate size_sum and ensure dyn_size is enough for early alloc */
1451 size_sum = PFN_ALIGN(static_size + reserved_size +
1452 max_t(size_t, dyn_size, PERCPU_DYNAMIC_EARLY_SIZE));
1453 dyn_size = size_sum - static_size - reserved_size;
1454
1455 /*
1456 * Determine min_unit_size, alloc_size and max_upa such that
1457 * alloc_size is multiple of atom_size and is the smallest
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001458 * which can accommodate 4k aligned segments which are equal to
Tejun Heofbf59bc2009-02-20 16:29:08 +09001459 * or larger than min_unit_size.
1460 */
1461 min_unit_size = max_t(size_t, size_sum, PCPU_MIN_UNIT_SIZE);
1462
1463 alloc_size = roundup(min_unit_size, atom_size);
1464 upa = alloc_size / min_unit_size;
1465 while (alloc_size % upa || ((alloc_size / upa) & ~PAGE_MASK))
1466 upa--;
1467 max_upa = upa;
1468
1469 /* group cpus according to their proximity */
1470 for_each_possible_cpu(cpu) {
1471 group = 0;
1472 next_group:
1473 for_each_possible_cpu(tcpu) {
1474 if (cpu == tcpu)
1475 break;
1476 if (group_map[tcpu] == group && cpu_distance_fn &&
1477 (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
1478 cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
1479 group++;
1480 nr_groups = max(nr_groups, group + 1);
1481 goto next_group;
1482 }
1483 }
1484 group_map[cpu] = group;
1485 group_cnt[group]++;
1486 }
1487
1488 /*
1489 * Expand unit size until address space usage goes over 75%
1490 * and then as much as possible without using more address
1491 * space.
1492 */
1493 last_allocs = INT_MAX;
1494 for (upa = max_upa; upa; upa--) {
1495 int allocs = 0, wasted = 0;
1496
1497 if (alloc_size % upa || ((alloc_size / upa) & ~PAGE_MASK))
1498 continue;
1499
1500 for (group = 0; group < nr_groups; group++) {
1501 int this_allocs = DIV_ROUND_UP(group_cnt[group], upa);
1502 allocs += this_allocs;
1503 wasted += this_allocs * upa - group_cnt[group];
1504 }
1505
1506 /*
1507 * Don't accept if wastage is over 1/3. The
1508 * greater-than comparison ensures upa==1 always
1509 * passes the following check.
1510 */
1511 if (wasted > num_possible_cpus() / 3)
1512 continue;
1513
1514 /* and then don't consume more memory */
1515 if (allocs > last_allocs)
1516 break;
1517 last_allocs = allocs;
1518 best_upa = upa;
1519 }
1520 upa = best_upa;
1521
1522 /* allocate and fill alloc_info */
1523 for (group = 0; group < nr_groups; group++)
1524 nr_units += roundup(group_cnt[group], upa);
1525
1526 ai = pcpu_alloc_alloc_info(nr_groups, nr_units);
1527 if (!ai)
1528 return ERR_PTR(-ENOMEM);
1529 cpu_map = ai->groups[0].cpu_map;
1530
1531 for (group = 0; group < nr_groups; group++) {
1532 ai->groups[group].cpu_map = cpu_map;
1533 cpu_map += roundup(group_cnt[group], upa);
1534 }
1535
1536 ai->static_size = static_size;
1537 ai->reserved_size = reserved_size;
1538 ai->dyn_size = dyn_size;
1539 ai->unit_size = alloc_size / upa;
1540 ai->atom_size = atom_size;
1541 ai->alloc_size = alloc_size;
1542
1543 for (group = 0, unit = 0; group_cnt[group]; group++) {
1544 struct pcpu_group_info *gi = &ai->groups[group];
1545
1546 /*
1547 * Initialize base_offset as if all groups are located
1548 * back-to-back. The caller should update this to
1549 * reflect actual allocation.
1550 */
1551 gi->base_offset = unit * ai->unit_size;
1552
1553 for_each_possible_cpu(cpu)
1554 if (group_map[cpu] == group)
1555 gi->cpu_map[gi->nr_units++] = cpu;
1556 gi->nr_units = roundup(gi->nr_units, upa);
1557 unit += gi->nr_units;
1558 }
1559 BUG_ON(unit != nr_units);
1560
1561 return ai;
1562}
Tejun Heo3c9a0242010-09-09 18:00:15 +02001563#endif /* BUILD_EMBED_FIRST_CHUNK || BUILD_PAGE_FIRST_CHUNK */
Tejun Heofbf59bc2009-02-20 16:29:08 +09001564
Tejun Heo3c9a0242010-09-09 18:00:15 +02001565#if defined(BUILD_EMBED_FIRST_CHUNK)
Tejun Heo66c3a752009-03-10 16:27:48 +09001566/**
1567 * pcpu_embed_first_chunk - embed the first percpu chunk into bootmem
Tejun Heo66c3a752009-03-10 16:27:48 +09001568 * @reserved_size: the size of reserved percpu area in bytes
Tejun Heo4ba6ce22010-06-27 18:49:59 +02001569 * @dyn_size: minimum free size for dynamic allocation in bytes
Tejun Heoc8826dd2009-08-14 15:00:52 +09001570 * @atom_size: allocation atom size
1571 * @cpu_distance_fn: callback to determine distance between cpus, optional
1572 * @alloc_fn: function to allocate percpu page
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001573 * @free_fn: function to free percpu page
Tejun Heo66c3a752009-03-10 16:27:48 +09001574 *
1575 * This is a helper to ease setting up embedded first percpu chunk and
1576 * can be called where pcpu_setup_first_chunk() is expected.
1577 *
1578 * If this function is used to setup the first chunk, it is allocated
Tejun Heoc8826dd2009-08-14 15:00:52 +09001579 * by calling @alloc_fn and used as-is without being mapped into
1580 * vmalloc area. Allocations are always whole multiples of @atom_size
1581 * aligned to @atom_size.
1582 *
1583 * This enables the first chunk to piggy back on the linear physical
1584 * mapping which often uses larger page size. Please note that this
1585 * can result in very sparse cpu->unit mapping on NUMA machines thus
1586 * requiring large vmalloc address space. Don't use this allocator if
1587 * vmalloc space is not orders of magnitude larger than distances
1588 * between node memory addresses (ie. 32bit NUMA machines).
Tejun Heo66c3a752009-03-10 16:27:48 +09001589 *
Tejun Heo4ba6ce22010-06-27 18:49:59 +02001590 * @dyn_size specifies the minimum dynamic area size.
Tejun Heo66c3a752009-03-10 16:27:48 +09001591 *
1592 * If the needed size is smaller than the minimum or specified unit
Tejun Heoc8826dd2009-08-14 15:00:52 +09001593 * size, the leftover is returned using @free_fn.
Tejun Heo66c3a752009-03-10 16:27:48 +09001594 *
1595 * RETURNS:
Tejun Heofb435d52009-08-14 15:00:51 +09001596 * 0 on success, -errno on failure.
Tejun Heo66c3a752009-03-10 16:27:48 +09001597 */
Tejun Heo4ba6ce22010-06-27 18:49:59 +02001598int __init pcpu_embed_first_chunk(size_t reserved_size, size_t dyn_size,
Tejun Heoc8826dd2009-08-14 15:00:52 +09001599 size_t atom_size,
1600 pcpu_fc_cpu_distance_fn_t cpu_distance_fn,
1601 pcpu_fc_alloc_fn_t alloc_fn,
1602 pcpu_fc_free_fn_t free_fn)
Tejun Heo66c3a752009-03-10 16:27:48 +09001603{
Tejun Heoc8826dd2009-08-14 15:00:52 +09001604 void *base = (void *)ULONG_MAX;
1605 void **areas = NULL;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001606 struct pcpu_alloc_info *ai;
Tejun Heo6ea529a2009-09-24 18:46:01 +09001607 size_t size_sum, areas_size, max_distance;
Tejun Heoc8826dd2009-08-14 15:00:52 +09001608 int group, i, rc;
Tejun Heo66c3a752009-03-10 16:27:48 +09001609
Tejun Heoc8826dd2009-08-14 15:00:52 +09001610 ai = pcpu_build_alloc_info(reserved_size, dyn_size, atom_size,
1611 cpu_distance_fn);
Tejun Heofd1e8a12009-08-14 15:00:51 +09001612 if (IS_ERR(ai))
1613 return PTR_ERR(ai);
Tejun Heo66c3a752009-03-10 16:27:48 +09001614
Tejun Heofd1e8a12009-08-14 15:00:51 +09001615 size_sum = ai->static_size + ai->reserved_size + ai->dyn_size;
Tejun Heoc8826dd2009-08-14 15:00:52 +09001616 areas_size = PFN_ALIGN(ai->nr_groups * sizeof(void *));
Tejun Heo66c3a752009-03-10 16:27:48 +09001617
Tejun Heoc8826dd2009-08-14 15:00:52 +09001618 areas = alloc_bootmem_nopanic(areas_size);
1619 if (!areas) {
Tejun Heofb435d52009-08-14 15:00:51 +09001620 rc = -ENOMEM;
Tejun Heoc8826dd2009-08-14 15:00:52 +09001621 goto out_free;
Tejun Heofa8a7092009-06-22 11:56:24 +09001622 }
Tejun Heo66c3a752009-03-10 16:27:48 +09001623
Tejun Heoc8826dd2009-08-14 15:00:52 +09001624 /* allocate, copy and determine base address */
1625 for (group = 0; group < ai->nr_groups; group++) {
1626 struct pcpu_group_info *gi = &ai->groups[group];
1627 unsigned int cpu = NR_CPUS;
1628 void *ptr;
Tejun Heo66c3a752009-03-10 16:27:48 +09001629
Tejun Heoc8826dd2009-08-14 15:00:52 +09001630 for (i = 0; i < gi->nr_units && cpu == NR_CPUS; i++)
1631 cpu = gi->cpu_map[i];
1632 BUG_ON(cpu == NR_CPUS);
1633
1634 /* allocate space for the whole group */
1635 ptr = alloc_fn(cpu, gi->nr_units * ai->unit_size, atom_size);
1636 if (!ptr) {
1637 rc = -ENOMEM;
1638 goto out_free_areas;
1639 }
1640 areas[group] = ptr;
1641
1642 base = min(ptr, base);
1643
1644 for (i = 0; i < gi->nr_units; i++, ptr += ai->unit_size) {
1645 if (gi->cpu_map[i] == NR_CPUS) {
1646 /* unused unit, free whole */
1647 free_fn(ptr, ai->unit_size);
1648 continue;
1649 }
1650 /* copy and return the unused part */
1651 memcpy(ptr, __per_cpu_load, ai->static_size);
1652 free_fn(ptr + size_sum, ai->unit_size - size_sum);
1653 }
Tejun Heo66c3a752009-03-10 16:27:48 +09001654 }
1655
Tejun Heoc8826dd2009-08-14 15:00:52 +09001656 /* base address is now known, determine group base offsets */
Tejun Heo6ea529a2009-09-24 18:46:01 +09001657 max_distance = 0;
1658 for (group = 0; group < ai->nr_groups; group++) {
Tejun Heoc8826dd2009-08-14 15:00:52 +09001659 ai->groups[group].base_offset = areas[group] - base;
Tejun Heo1a0c3292009-10-04 09:31:05 +09001660 max_distance = max_t(size_t, max_distance,
1661 ai->groups[group].base_offset);
Tejun Heo6ea529a2009-09-24 18:46:01 +09001662 }
1663 max_distance += ai->unit_size;
1664
1665 /* warn if maximum distance is further than 75% of vmalloc space */
1666 if (max_distance > (VMALLOC_END - VMALLOC_START) * 3 / 4) {
Tejun Heo1a0c3292009-10-04 09:31:05 +09001667 pr_warning("PERCPU: max_distance=0x%zx too large for vmalloc "
Mike Frysinger787e5b02011-03-23 08:23:52 +01001668 "space 0x%lx\n", max_distance,
1669 (unsigned long)(VMALLOC_END - VMALLOC_START));
Tejun Heo6ea529a2009-09-24 18:46:01 +09001670#ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
1671 /* and fail if we have fallback */
1672 rc = -EINVAL;
1673 goto out_free;
1674#endif
1675 }
Tejun Heoc8826dd2009-08-14 15:00:52 +09001676
Tejun Heo004018e2009-08-14 15:00:49 +09001677 pr_info("PERCPU: Embedded %zu pages/cpu @%p s%zu r%zu d%zu u%zu\n",
Tejun Heofd1e8a12009-08-14 15:00:51 +09001678 PFN_DOWN(size_sum), base, ai->static_size, ai->reserved_size,
1679 ai->dyn_size, ai->unit_size);
Tejun Heo66c3a752009-03-10 16:27:48 +09001680
Tejun Heofb435d52009-08-14 15:00:51 +09001681 rc = pcpu_setup_first_chunk(ai, base);
Tejun Heoc8826dd2009-08-14 15:00:52 +09001682 goto out_free;
1683
1684out_free_areas:
1685 for (group = 0; group < ai->nr_groups; group++)
1686 free_fn(areas[group],
1687 ai->groups[group].nr_units * ai->unit_size);
1688out_free:
Tejun Heofd1e8a12009-08-14 15:00:51 +09001689 pcpu_free_alloc_info(ai);
Tejun Heoc8826dd2009-08-14 15:00:52 +09001690 if (areas)
1691 free_bootmem(__pa(areas), areas_size);
Tejun Heofb435d52009-08-14 15:00:51 +09001692 return rc;
Tejun Heod4b95f82009-07-04 08:10:59 +09001693}
Tejun Heo3c9a0242010-09-09 18:00:15 +02001694#endif /* BUILD_EMBED_FIRST_CHUNK */
Tejun Heod4b95f82009-07-04 08:10:59 +09001695
Tejun Heo3c9a0242010-09-09 18:00:15 +02001696#ifdef BUILD_PAGE_FIRST_CHUNK
Tejun Heod4b95f82009-07-04 08:10:59 +09001697/**
Tejun Heo00ae4062009-08-14 15:00:49 +09001698 * pcpu_page_first_chunk - map the first chunk using PAGE_SIZE pages
Tejun Heod4b95f82009-07-04 08:10:59 +09001699 * @reserved_size: the size of reserved percpu area in bytes
1700 * @alloc_fn: function to allocate percpu page, always called with PAGE_SIZE
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001701 * @free_fn: function to free percpu page, always called with PAGE_SIZE
Tejun Heod4b95f82009-07-04 08:10:59 +09001702 * @populate_pte_fn: function to populate pte
1703 *
Tejun Heo00ae4062009-08-14 15:00:49 +09001704 * This is a helper to ease setting up page-remapped first percpu
1705 * chunk and can be called where pcpu_setup_first_chunk() is expected.
Tejun Heod4b95f82009-07-04 08:10:59 +09001706 *
1707 * This is the basic allocator. Static percpu area is allocated
1708 * page-by-page into vmalloc area.
1709 *
1710 * RETURNS:
Tejun Heofb435d52009-08-14 15:00:51 +09001711 * 0 on success, -errno on failure.
Tejun Heod4b95f82009-07-04 08:10:59 +09001712 */
Tejun Heofb435d52009-08-14 15:00:51 +09001713int __init pcpu_page_first_chunk(size_t reserved_size,
1714 pcpu_fc_alloc_fn_t alloc_fn,
1715 pcpu_fc_free_fn_t free_fn,
1716 pcpu_fc_populate_pte_fn_t populate_pte_fn)
Tejun Heod4b95f82009-07-04 08:10:59 +09001717{
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001718 static struct vm_struct vm;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001719 struct pcpu_alloc_info *ai;
Tejun Heo00ae4062009-08-14 15:00:49 +09001720 char psize_str[16];
Tejun Heoce3141a2009-07-04 08:11:00 +09001721 int unit_pages;
Tejun Heod4b95f82009-07-04 08:10:59 +09001722 size_t pages_size;
Tejun Heoce3141a2009-07-04 08:11:00 +09001723 struct page **pages;
Tejun Heofb435d52009-08-14 15:00:51 +09001724 int unit, i, j, rc;
Tejun Heod4b95f82009-07-04 08:10:59 +09001725
Tejun Heo00ae4062009-08-14 15:00:49 +09001726 snprintf(psize_str, sizeof(psize_str), "%luK", PAGE_SIZE >> 10);
1727
Tejun Heo4ba6ce22010-06-27 18:49:59 +02001728 ai = pcpu_build_alloc_info(reserved_size, 0, PAGE_SIZE, NULL);
Tejun Heofd1e8a12009-08-14 15:00:51 +09001729 if (IS_ERR(ai))
1730 return PTR_ERR(ai);
1731 BUG_ON(ai->nr_groups != 1);
1732 BUG_ON(ai->groups[0].nr_units != num_possible_cpus());
1733
1734 unit_pages = ai->unit_size >> PAGE_SHIFT;
Tejun Heod4b95f82009-07-04 08:10:59 +09001735
1736 /* unaligned allocations can't be freed, round up to page size */
Tejun Heofd1e8a12009-08-14 15:00:51 +09001737 pages_size = PFN_ALIGN(unit_pages * num_possible_cpus() *
1738 sizeof(pages[0]));
Tejun Heoce3141a2009-07-04 08:11:00 +09001739 pages = alloc_bootmem(pages_size);
Tejun Heod4b95f82009-07-04 08:10:59 +09001740
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001741 /* allocate pages */
Tejun Heod4b95f82009-07-04 08:10:59 +09001742 j = 0;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001743 for (unit = 0; unit < num_possible_cpus(); unit++)
Tejun Heoce3141a2009-07-04 08:11:00 +09001744 for (i = 0; i < unit_pages; i++) {
Tejun Heofd1e8a12009-08-14 15:00:51 +09001745 unsigned int cpu = ai->groups[0].cpu_map[unit];
Tejun Heod4b95f82009-07-04 08:10:59 +09001746 void *ptr;
1747
Tejun Heo3cbc8562009-08-14 15:00:50 +09001748 ptr = alloc_fn(cpu, PAGE_SIZE, PAGE_SIZE);
Tejun Heod4b95f82009-07-04 08:10:59 +09001749 if (!ptr) {
Tejun Heo00ae4062009-08-14 15:00:49 +09001750 pr_warning("PERCPU: failed to allocate %s page "
1751 "for cpu%u\n", psize_str, cpu);
Tejun Heod4b95f82009-07-04 08:10:59 +09001752 goto enomem;
1753 }
Tejun Heoce3141a2009-07-04 08:11:00 +09001754 pages[j++] = virt_to_page(ptr);
Tejun Heod4b95f82009-07-04 08:10:59 +09001755 }
1756
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001757 /* allocate vm area, map the pages and copy static data */
1758 vm.flags = VM_ALLOC;
Tejun Heofd1e8a12009-08-14 15:00:51 +09001759 vm.size = num_possible_cpus() * ai->unit_size;
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001760 vm_area_register_early(&vm, PAGE_SIZE);
1761
Tejun Heofd1e8a12009-08-14 15:00:51 +09001762 for (unit = 0; unit < num_possible_cpus(); unit++) {
Tejun Heo1d9d3252009-08-14 15:00:50 +09001763 unsigned long unit_addr =
Tejun Heofd1e8a12009-08-14 15:00:51 +09001764 (unsigned long)vm.addr + unit * ai->unit_size;
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001765
Tejun Heoce3141a2009-07-04 08:11:00 +09001766 for (i = 0; i < unit_pages; i++)
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001767 populate_pte_fn(unit_addr + (i << PAGE_SHIFT));
1768
1769 /* pte already populated, the following shouldn't fail */
Tejun Heofb435d52009-08-14 15:00:51 +09001770 rc = __pcpu_map_pages(unit_addr, &pages[unit * unit_pages],
1771 unit_pages);
1772 if (rc < 0)
1773 panic("failed to map percpu area, err=%d\n", rc);
Tejun Heo8f05a6a2009-07-04 08:10:59 +09001774
1775 /*
1776 * FIXME: Archs with virtual cache should flush local
1777 * cache for the linear mapping here - something
1778 * equivalent to flush_cache_vmap() on the local cpu.
1779 * flush_cache_vmap() can't be used as most supporting
1780 * data structures are not set up yet.
1781 */
1782
1783 /* copy static data */
Tejun Heofd1e8a12009-08-14 15:00:51 +09001784 memcpy((void *)unit_addr, __per_cpu_load, ai->static_size);
Tejun Heo66c3a752009-03-10 16:27:48 +09001785 }
1786
1787 /* we're ready, commit */
Tejun Heo1d9d3252009-08-14 15:00:50 +09001788 pr_info("PERCPU: %d %s pages/cpu @%p s%zu r%zu d%zu\n",
Tejun Heofd1e8a12009-08-14 15:00:51 +09001789 unit_pages, psize_str, vm.addr, ai->static_size,
1790 ai->reserved_size, ai->dyn_size);
Tejun Heo66c3a752009-03-10 16:27:48 +09001791
Tejun Heofb435d52009-08-14 15:00:51 +09001792 rc = pcpu_setup_first_chunk(ai, vm.addr);
Tejun Heod4b95f82009-07-04 08:10:59 +09001793 goto out_free_ar;
1794
1795enomem:
1796 while (--j >= 0)
Tejun Heoce3141a2009-07-04 08:11:00 +09001797 free_fn(page_address(pages[j]), PAGE_SIZE);
Tejun Heofb435d52009-08-14 15:00:51 +09001798 rc = -ENOMEM;
Tejun Heod4b95f82009-07-04 08:10:59 +09001799out_free_ar:
Tejun Heoce3141a2009-07-04 08:11:00 +09001800 free_bootmem(__pa(pages), pages_size);
Tejun Heofd1e8a12009-08-14 15:00:51 +09001801 pcpu_free_alloc_info(ai);
Tejun Heofb435d52009-08-14 15:00:51 +09001802 return rc;
Tejun Heo66c3a752009-03-10 16:27:48 +09001803}
Tejun Heo3c9a0242010-09-09 18:00:15 +02001804#endif /* BUILD_PAGE_FIRST_CHUNK */
Tejun Heod4b95f82009-07-04 08:10:59 +09001805
Tejun Heobbddff02010-09-03 18:22:48 +02001806#ifndef CONFIG_HAVE_SETUP_PER_CPU_AREA
Tejun Heo8c4bfc62009-07-04 08:10:59 +09001807/*
Tejun Heobbddff02010-09-03 18:22:48 +02001808 * Generic SMP percpu area setup.
Tejun Heoe74e3962009-03-30 19:07:44 +09001809 *
1810 * The embedding helper is used because its behavior closely resembles
1811 * the original non-dynamic generic percpu area setup. This is
1812 * important because many archs have addressing restrictions and might
1813 * fail if the percpu area is located far away from the previous
1814 * location. As an added bonus, in non-NUMA cases, embedding is
1815 * generally a good idea TLB-wise because percpu area can piggy back
1816 * on the physical linear memory mapping which uses large page
1817 * mappings on applicable archs.
1818 */
Tejun Heoe74e3962009-03-30 19:07:44 +09001819unsigned long __per_cpu_offset[NR_CPUS] __read_mostly;
1820EXPORT_SYMBOL(__per_cpu_offset);
1821
Tejun Heoc8826dd2009-08-14 15:00:52 +09001822static void * __init pcpu_dfl_fc_alloc(unsigned int cpu, size_t size,
1823 size_t align)
1824{
1825 return __alloc_bootmem_nopanic(size, align, __pa(MAX_DMA_ADDRESS));
1826}
1827
1828static void __init pcpu_dfl_fc_free(void *ptr, size_t size)
1829{
1830 free_bootmem(__pa(ptr), size);
1831}
1832
Tejun Heoe74e3962009-03-30 19:07:44 +09001833void __init setup_per_cpu_areas(void)
1834{
Tejun Heoe74e3962009-03-30 19:07:44 +09001835 unsigned long delta;
1836 unsigned int cpu;
Tejun Heofb435d52009-08-14 15:00:51 +09001837 int rc;
Tejun Heoe74e3962009-03-30 19:07:44 +09001838
1839 /*
1840 * Always reserve area for module percpu variables. That's
1841 * what the legacy allocator did.
1842 */
Tejun Heofb435d52009-08-14 15:00:51 +09001843 rc = pcpu_embed_first_chunk(PERCPU_MODULE_RESERVE,
Tejun Heoc8826dd2009-08-14 15:00:52 +09001844 PERCPU_DYNAMIC_RESERVE, PAGE_SIZE, NULL,
1845 pcpu_dfl_fc_alloc, pcpu_dfl_fc_free);
Tejun Heofb435d52009-08-14 15:00:51 +09001846 if (rc < 0)
Tejun Heobbddff02010-09-03 18:22:48 +02001847 panic("Failed to initialize percpu areas.");
Tejun Heoe74e3962009-03-30 19:07:44 +09001848
1849 delta = (unsigned long)pcpu_base_addr - (unsigned long)__per_cpu_start;
1850 for_each_possible_cpu(cpu)
Tejun Heofb435d52009-08-14 15:00:51 +09001851 __per_cpu_offset[cpu] = delta + pcpu_unit_offsets[cpu];
Tejun Heoe74e3962009-03-30 19:07:44 +09001852}
Tejun Heobbddff02010-09-03 18:22:48 +02001853#endif /* CONFIG_HAVE_SETUP_PER_CPU_AREA */
1854
1855#else /* CONFIG_SMP */
1856
1857/*
1858 * UP percpu area setup.
1859 *
1860 * UP always uses km-based percpu allocator with identity mapping.
1861 * Static percpu variables are indistinguishable from the usual static
1862 * variables and don't require any special preparation.
1863 */
1864void __init setup_per_cpu_areas(void)
1865{
1866 const size_t unit_size =
1867 roundup_pow_of_two(max_t(size_t, PCPU_MIN_UNIT_SIZE,
1868 PERCPU_DYNAMIC_RESERVE));
1869 struct pcpu_alloc_info *ai;
1870 void *fc;
1871
1872 ai = pcpu_alloc_alloc_info(1, 1);
1873 fc = __alloc_bootmem(unit_size, PAGE_SIZE, __pa(MAX_DMA_ADDRESS));
1874 if (!ai || !fc)
1875 panic("Failed to allocate memory for percpu areas.");
1876
1877 ai->dyn_size = unit_size;
1878 ai->unit_size = unit_size;
1879 ai->atom_size = unit_size;
1880 ai->alloc_size = unit_size;
1881 ai->groups[0].nr_units = 1;
1882 ai->groups[0].cpu_map[0] = 0;
1883
1884 if (pcpu_setup_first_chunk(ai, fc) < 0)
1885 panic("Failed to initialize percpu areas.");
1886}
1887
1888#endif /* CONFIG_SMP */
Tejun Heo099a19d2010-06-27 18:50:00 +02001889
1890/*
1891 * First and reserved chunks are initialized with temporary allocation
1892 * map in initdata so that they can be used before slab is online.
1893 * This function is called after slab is brought up and replaces those
1894 * with properly allocated maps.
1895 */
1896void __init percpu_init_late(void)
1897{
1898 struct pcpu_chunk *target_chunks[] =
1899 { pcpu_first_chunk, pcpu_reserved_chunk, NULL };
1900 struct pcpu_chunk *chunk;
1901 unsigned long flags;
1902 int i;
1903
1904 for (i = 0; (chunk = target_chunks[i]); i++) {
1905 int *map;
1906 const size_t size = PERCPU_DYNAMIC_EARLY_SLOTS * sizeof(map[0]);
1907
1908 BUILD_BUG_ON(size > PAGE_SIZE);
1909
Bob Liu90459ce02011-08-04 11:02:33 +02001910 map = pcpu_mem_zalloc(size);
Tejun Heo099a19d2010-06-27 18:50:00 +02001911 BUG_ON(!map);
1912
1913 spin_lock_irqsave(&pcpu_lock, flags);
1914 memcpy(map, chunk->map, size);
1915 chunk->map = map;
1916 spin_unlock_irqrestore(&pcpu_lock, flags);
1917 }
1918}