percpu.c 60.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
/*
 * linux/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 in vmalloc area.  Each
11 12 13 14 15 16 17
 * 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.  ie. in
 * vmalloc area
18 19 20 21 22 23 24 25
 *
 *  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,
26 27 28 29
 * 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.
30
 *
31 32
 * There are usually many small percpu allocations many of them being
 * as small as 4 bytes.  The allocator organizes chunks into lists
33 34 35 36 37 38 39 40 41 42 43
 * 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 eqaul 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.
44 45
 * Chunks can be determined from the address using the index field
 * in the page struct. The index field contains a pointer to the chunk.
46 47 48
 *
 * To use this allocator, arch code should do the followings.
 *
49
 * - drop CONFIG_HAVE_LEGACY_PER_CPU_AREA
50 51
 *
 * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate
52 53
 *   regular address to percpu pointer and back if they need to be
 *   different from the default
54
 *
55 56
 * - use pcpu_setup_first_chunk() during percpu area initialization to
 *   setup the first chunk containing the kernel static percpu area
57 58 59 60
 */

#include <linux/bitmap.h>
#include <linux/bootmem.h>
61
#include <linux/err.h>
62
#include <linux/list.h>
63
#include <linux/log2.h>
64 65 66 67 68 69
#include <linux/mm.h>
#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/percpu.h>
#include <linux/pfn.h>
#include <linux/slab.h>
70
#include <linux/spinlock.h>
71
#include <linux/vmalloc.h>
72
#include <linux/workqueue.h>
73 74

#include <asm/cacheflush.h>
75
#include <asm/sections.h>
76 77 78 79 80
#include <asm/tlbflush.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 */

81 82 83 84 85 86 87 88 89 90 91 92
/* default addr <-> pcpu_ptr mapping, override in asm/percpu.h if necessary */
#ifndef __addr_to_pcpu_ptr
#define __addr_to_pcpu_ptr(addr)					\
	(void *)((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 *)((unsigned long)(ptr) + (unsigned long)pcpu_base_addr	\
		 - (unsigned long)__per_cpu_start)
#endif

93 94 95 96
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 */
T
Tejun Heo 已提交
97
	void			*base_addr;	/* base address of this chunk */
98 99 100
	int			map_used;	/* # of map entries used */
	int			map_alloc;	/* # of map entries allocated */
	int			*map;		/* allocation map */
101
	struct vm_struct	**vms;		/* mapped vmalloc regions */
102
	bool			immutable;	/* no [de]population allowed */
T
Tejun Heo 已提交
103
	unsigned long		populated[];	/* populated bitmap */
104 105
};

106 107
static int pcpu_unit_pages __read_mostly;
static int pcpu_unit_size __read_mostly;
108
static int pcpu_nr_units __read_mostly;
109
static int pcpu_atom_size __read_mostly;
110 111
static int pcpu_nr_slots __read_mostly;
static size_t pcpu_chunk_struct_size __read_mostly;
112

113 114 115 116
/* cpus with the lowest and highest unit numbers */
static unsigned int pcpu_first_unit_cpu __read_mostly;
static unsigned int pcpu_last_unit_cpu __read_mostly;

117
/* the address of the first chunk which starts with the kernel static area */
118
void *pcpu_base_addr __read_mostly;
119 120
EXPORT_SYMBOL_GPL(pcpu_base_addr);

T
Tejun Heo 已提交
121 122
static const int *pcpu_unit_map __read_mostly;		/* cpu -> unit */
const unsigned long *pcpu_unit_offsets __read_mostly;	/* cpu -> unit offset */
123

124 125 126 127 128
/* 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;

129 130 131 132 133 134 135 136 137 138 139 140 141 142
/*
 * 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.
 */
143 144 145
static struct pcpu_chunk *pcpu_reserved_chunk;
static int pcpu_reserved_chunk_limit;

146
/*
147 148 149
 * Synchronization rules.
 *
 * There are two locks - pcpu_alloc_mutex and pcpu_lock.  The former
T
Tejun Heo 已提交
150 151 152
 * 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.
153 154 155 156 157 158 159 160 161 162 163 164 165
 *
 * 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.
 *
 * 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.
166
 */
167 168
static DEFINE_MUTEX(pcpu_alloc_mutex);	/* protects whole alloc and reclaim */
static DEFINE_SPINLOCK(pcpu_lock);	/* protects index data structures */
169

170
static struct list_head *pcpu_slot __read_mostly; /* chunk list slots */
171

172 173 174 175
/* 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);

176
static int __pcpu_size_to_slot(int size)
177
{
T
Tejun Heo 已提交
178
	int highbit = fls(size);	/* size is in bytes */
179 180 181
	return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
}

182 183 184 185 186 187 188
static int pcpu_size_to_slot(int size)
{
	if (size == pcpu_unit_size)
		return pcpu_nr_slots - 1;
	return __pcpu_size_to_slot(size);
}

189 190 191 192 193 194 195 196 197 198
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);
}

static int pcpu_page_idx(unsigned int cpu, int page_idx)
{
199
	return pcpu_unit_map[cpu] * pcpu_unit_pages + page_idx;
200 201 202 203 204
}

static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
				     unsigned int cpu, int page_idx)
{
T
Tejun Heo 已提交
205
	return (unsigned long)chunk->base_addr + pcpu_unit_offsets[cpu] +
T
Tejun Heo 已提交
206
		(page_idx << PAGE_SHIFT);
207 208
}

T
Tejun Heo 已提交
209 210
static struct page *pcpu_chunk_page(struct pcpu_chunk *chunk,
				    unsigned int cpu, int page_idx)
211
{
T
Tejun Heo 已提交
212 213
	/* must not be used on pre-mapped chunk */
	WARN_ON(chunk->immutable);
214

T
Tejun Heo 已提交
215
	return vmalloc_to_page((void *)pcpu_chunk_addr(chunk, cpu, page_idx));
216 217
}

218 219 220 221 222 223 224 225 226 227 228 229
/* 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;
}

T
Tejun Heo 已提交
230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
static void 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 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 betwen @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)))

258
/**
259 260
 * pcpu_mem_alloc - allocate memory
 * @size: bytes to allocate
261
 *
262 263 264
 * Allocate @size bytes.  If @size is smaller than PAGE_SIZE,
 * kzalloc() is used; otherwise, vmalloc() is used.  The returned
 * memory is always zeroed.
265
 *
266 267 268
 * CONTEXT:
 * Does GFP_KERNEL allocation.
 *
269
 * RETURNS:
270
 * Pointer to the allocated area on success, NULL on failure.
271
 */
272
static void *pcpu_mem_alloc(size_t size)
273
{
274 275 276 277 278 279 280 281 282
	if (size <= PAGE_SIZE)
		return kzalloc(size, GFP_KERNEL);
	else {
		void *ptr = vmalloc(size);
		if (ptr)
			memset(ptr, 0, size);
		return ptr;
	}
}
283

284 285 286 287 288 289 290 291 292
/**
 * pcpu_mem_free - free memory
 * @ptr: memory to free
 * @size: size of the area
 *
 * Free @ptr.  @ptr should have been allocated using pcpu_mem_alloc().
 */
static void pcpu_mem_free(void *ptr, size_t size)
{
293
	if (size <= PAGE_SIZE)
294
		kfree(ptr);
295
	else
296
		vfree(ptr);
297 298 299 300 301 302 303 304 305
}

/**
 * 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
306 307
 * moved to the slot.  Note that the reserved chunk is never put on
 * chunk slots.
308 309 310
 *
 * CONTEXT:
 * pcpu_lock.
311 312 313 314 315
 */
static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
{
	int nslot = pcpu_chunk_slot(chunk);

316
	if (chunk != pcpu_reserved_chunk && oslot != nslot) {
317 318 319 320 321 322 323 324
		if (oslot < nslot)
			list_move(&chunk->list, &pcpu_slot[nslot]);
		else
			list_move_tail(&chunk->list, &pcpu_slot[nslot]);
	}
}

/**
325 326
 * pcpu_chunk_addr_search - determine chunk containing specified address
 * @addr: address for which the chunk needs to be determined.
327
 *
328 329 330 331 332
 * RETURNS:
 * The address of the found chunk.
 */
static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
{
T
Tejun Heo 已提交
333
	void *first_start = pcpu_first_chunk->base_addr;
334

335
	/* is it in the first chunk? */
336
	if (addr >= first_start && addr < first_start + pcpu_unit_size) {
337 338
		/* is it in the reserved area? */
		if (addr < first_start + pcpu_reserved_chunk_limit)
339
			return pcpu_reserved_chunk;
340
		return pcpu_first_chunk;
341 342
	}

343 344 345 346 347 348 349
	/*
	 * The address is relative to unit0 which might be unused and
	 * thus unmapped.  Offset the address to the unit space of the
	 * current processor before looking it up in the vmalloc
	 * space.  Note that any possible cpu id can be used here, so
	 * there's no need to worry about preemption or cpu hotplug.
	 */
350
	addr += pcpu_unit_offsets[raw_smp_processor_id()];
351
	return pcpu_get_page_chunk(vmalloc_to_page(addr));
352 353
}

354 355 356 357 358 359 360 361
/**
 * pcpu_extend_area_map - extend area map for allocation
 * @chunk: target chunk
 *
 * Extend area map of @chunk so that it can accomodate an allocation.
 * A single allocation can split an area into three areas, so this
 * function makes sure that @chunk->map has at least two extra slots.
 *
362 363 364 365
 * CONTEXT:
 * pcpu_alloc_mutex, pcpu_lock.  pcpu_lock is released and reacquired
 * if area map is extended.
 *
366 367 368 369 370 371 372 373 374 375 376 377 378
 * RETURNS:
 * 0 if noop, 1 if successfully extended, -errno on failure.
 */
static int pcpu_extend_area_map(struct pcpu_chunk *chunk)
{
	int new_alloc;
	int *new;
	size_t size;

	/* has enough? */
	if (chunk->map_alloc >= chunk->map_used + 2)
		return 0;

379 380
	spin_unlock_irq(&pcpu_lock);

381 382 383 384 385
	new_alloc = PCPU_DFL_MAP_ALLOC;
	while (new_alloc < chunk->map_used + 2)
		new_alloc *= 2;

	new = pcpu_mem_alloc(new_alloc * sizeof(new[0]));
386 387
	if (!new) {
		spin_lock_irq(&pcpu_lock);
388
		return -ENOMEM;
389 390 391 392 393 394 395 396 397
	}

	/*
	 * Acquire pcpu_lock and switch to new area map.  Only free
	 * could have happened inbetween, so map_used couldn't have
	 * grown.
	 */
	spin_lock_irq(&pcpu_lock);
	BUG_ON(new_alloc < chunk->map_used + 2);
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413

	size = chunk->map_alloc * sizeof(chunk->map[0]);
	memcpy(new, chunk->map, size);

	/*
	 * map_alloc < PCPU_DFL_MAP_ALLOC indicates that the chunk is
	 * one of the first chunks and still using static map.
	 */
	if (chunk->map_alloc >= PCPU_DFL_MAP_ALLOC)
		pcpu_mem_free(chunk->map, size);

	chunk->map_alloc = new_alloc;
	chunk->map = new;
	return 0;
}

414 415 416 417
/**
 * pcpu_split_block - split a map block
 * @chunk: chunk of interest
 * @i: index of map block to split
T
Tejun Heo 已提交
418 419
 * @head: head size in bytes (can be 0)
 * @tail: tail size in bytes (can be 0)
420 421 422 423 424 425 426 427 428
 *
 * 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.
 *
429
 * @chunk->map must have enough free slots to accomodate the split.
430 431 432
 *
 * CONTEXT:
 * pcpu_lock.
433
 */
434 435
static void pcpu_split_block(struct pcpu_chunk *chunk, int i,
			     int head, int tail)
436 437
{
	int nr_extra = !!head + !!tail;
438

439
	BUG_ON(chunk->map_alloc < chunk->map_used + nr_extra);
440

441
	/* insert new subblocks */
442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458
	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
T
Tejun Heo 已提交
459
 * @size: wanted size in bytes
460 461 462 463 464 465
 * @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.
 *
466 467
 * @chunk->map must have at least two free slots.
 *
468 469 470
 * CONTEXT:
 * pcpu_lock.
 *
471
 * RETURNS:
472 473
 * Allocated offset in @chunk on success, -1 if no matching area is
 * found.
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520
 */
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;
		}

		/*
		 * If head is small or the previous block is free,
		 * merge'em.  Note that 'small' is defined as smaller
		 * than sizeof(int), which is very small but isn't too
		 * uncommon for percpu allocations.
		 */
		if (head && (head < sizeof(int) || chunk->map[i - 1] > 0)) {
			if (chunk->map[i - 1] > 0)
				chunk->map[i - 1] += head;
			else {
				chunk->map[i - 1] -= head;
				chunk->free_size -= head;
			}
			chunk->map[i] -= head;
			off += head;
			head = 0;
		}

		/* if tail is small, just keep it around */
		tail = chunk->map[i] - head - size;
		if (tail < sizeof(int))
			tail = 0;

		/* split if warranted */
		if (head || tail) {
521
			pcpu_split_block(chunk, i, head, tail);
522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547
			if (head) {
				i++;
				off += head;
				max_contig = max(chunk->map[i - 1], max_contig);
			}
			if (tail)
				max_contig = max(chunk->map[i + 1], max_contig);
		}

		/* update hint and mark allocated */
		if (is_last)
			chunk->contig_hint = max_contig; /* fully scanned */
		else
			chunk->contig_hint = max(chunk->contig_hint,
						 max_contig);

		chunk->free_size -= chunk->map[i];
		chunk->map[i] = -chunk->map[i];

		pcpu_chunk_relocate(chunk, oslot);
		return off;
	}

	chunk->contig_hint = max_contig;	/* fully scanned */
	pcpu_chunk_relocate(chunk, oslot);

548 549
	/* tell the upper layer that this chunk has no matching area */
	return -1;
550 551 552 553 554 555 556 557 558 559
}

/**
 * pcpu_free_area - free area to a pcpu_chunk
 * @chunk: chunk of interest
 * @freeme: offset of area to free
 *
 * Free area starting from @freeme to @chunk.  Note that this function
 * only modifies the allocation map.  It doesn't depopulate or unmap
 * the area.
560 561 562
 *
 * CONTEXT:
 * pcpu_lock.
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
 */
static void pcpu_free_area(struct pcpu_chunk *chunk, int freeme)
{
	int oslot = pcpu_chunk_slot(chunk);
	int i, off;

	for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++]))
		if (off == freeme)
			break;
	BUG_ON(off != freeme);
	BUG_ON(chunk->map[i] > 0);

	chunk->map[i] = -chunk->map[i];
	chunk->free_size += chunk->map[i];

	/* merge with previous? */
	if (i > 0 && chunk->map[i - 1] >= 0) {
		chunk->map[i - 1] += chunk->map[i];
		chunk->map_used--;
		memmove(&chunk->map[i], &chunk->map[i + 1],
			(chunk->map_used - i) * sizeof(chunk->map[0]));
		i--;
	}
	/* merge with next? */
	if (i + 1 < chunk->map_used && chunk->map[i + 1] >= 0) {
		chunk->map[i] += chunk->map[i + 1];
		chunk->map_used--;
		memmove(&chunk->map[i + 1], &chunk->map[i + 2],
			(chunk->map_used - (i + 1)) * sizeof(chunk->map[0]));
	}

	chunk->contig_hint = max(chunk->map[i], chunk->contig_hint);
	pcpu_chunk_relocate(chunk, oslot);
}

/**
T
Tejun Heo 已提交
599
 * pcpu_get_pages_and_bitmap - get temp pages array and bitmap
600
 * @chunk: chunk of interest
T
Tejun Heo 已提交
601 602
 * @bitmapp: output parameter for bitmap
 * @may_alloc: may allocate the array
603
 *
T
Tejun Heo 已提交
604 605 606 607 608 609 610 611 612 613 614 615
 * Returns pointer to array of pointers to struct page and bitmap,
 * both of which can be indexed with pcpu_page_idx().  The returned
 * array is cleared to zero and *@bitmapp is copied from
 * @chunk->populated.  Note that there is only one array and bitmap
 * and access exclusion is the caller's responsibility.
 *
 * CONTEXT:
 * pcpu_alloc_mutex and does GFP_KERNEL allocation if @may_alloc.
 * Otherwise, don't care.
 *
 * RETURNS:
 * Pointer to temp pages array on success, NULL on failure.
616
 */
T
Tejun Heo 已提交
617 618 619
static struct page **pcpu_get_pages_and_bitmap(struct pcpu_chunk *chunk,
					       unsigned long **bitmapp,
					       bool may_alloc)
620
{
T
Tejun Heo 已提交
621 622
	static struct page **pages;
	static unsigned long *bitmap;
623
	size_t pages_size = pcpu_nr_units * pcpu_unit_pages * sizeof(pages[0]);
T
Tejun Heo 已提交
624 625 626 627 628 629 630 631 632 633 634
	size_t bitmap_size = BITS_TO_LONGS(pcpu_unit_pages) *
			     sizeof(unsigned long);

	if (!pages || !bitmap) {
		if (may_alloc && !pages)
			pages = pcpu_mem_alloc(pages_size);
		if (may_alloc && !bitmap)
			bitmap = pcpu_mem_alloc(bitmap_size);
		if (!pages || !bitmap)
			return NULL;
	}
635

T
Tejun Heo 已提交
636 637
	memset(pages, 0, pages_size);
	bitmap_copy(bitmap, chunk->populated, pcpu_unit_pages);
638

T
Tejun Heo 已提交
639 640 641
	*bitmapp = bitmap;
	return pages;
}
642

T
Tejun Heo 已提交
643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668
/**
 * pcpu_free_pages - free pages which were allocated for @chunk
 * @chunk: chunk pages were allocated for
 * @pages: array of pages to be freed, indexed by pcpu_page_idx()
 * @populated: populated bitmap
 * @page_start: page index of the first page to be freed
 * @page_end: page index of the last page to be freed + 1
 *
 * Free pages [@page_start and @page_end) in @pages for all units.
 * The pages were allocated for @chunk.
 */
static void pcpu_free_pages(struct pcpu_chunk *chunk,
			    struct page **pages, unsigned long *populated,
			    int page_start, int page_end)
{
	unsigned int cpu;
	int i;

	for_each_possible_cpu(cpu) {
		for (i = page_start; i < page_end; i++) {
			struct page *page = pages[pcpu_page_idx(cpu, i)];

			if (page)
				__free_page(page);
		}
	}
669 670 671
}

/**
T
Tejun Heo 已提交
672 673 674 675 676 677 678 679 680 681
 * pcpu_alloc_pages - allocates pages for @chunk
 * @chunk: target chunk
 * @pages: array to put the allocated pages into, indexed by pcpu_page_idx()
 * @populated: populated bitmap
 * @page_start: page index of the first page to be allocated
 * @page_end: page index of the last page to be allocated + 1
 *
 * Allocate pages [@page_start,@page_end) into @pages for all units.
 * The allocation is for @chunk.  Percpu core doesn't care about the
 * content of @pages and will pass it verbatim to pcpu_map_pages().
682
 */
T
Tejun Heo 已提交
683 684 685
static int pcpu_alloc_pages(struct pcpu_chunk *chunk,
			    struct page **pages, unsigned long *populated,
			    int page_start, int page_end)
686
{
T
Tejun Heo 已提交
687
	const gfp_t gfp = GFP_KERNEL | __GFP_HIGHMEM | __GFP_COLD;
688 689 690
	unsigned int cpu;
	int i;

T
Tejun Heo 已提交
691 692 693 694 695 696 697 698 699 700 701 702 703 704
	for_each_possible_cpu(cpu) {
		for (i = page_start; i < page_end; i++) {
			struct page **pagep = &pages[pcpu_page_idx(cpu, i)];

			*pagep = alloc_pages_node(cpu_to_node(cpu), gfp, 0);
			if (!*pagep) {
				pcpu_free_pages(chunk, pages, populated,
						page_start, page_end);
				return -ENOMEM;
			}
		}
	}
	return 0;
}
705

T
Tejun Heo 已提交
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720
/**
 * pcpu_pre_unmap_flush - flush cache prior to unmapping
 * @chunk: chunk the regions to be flushed belongs to
 * @page_start: page index of the first page to be flushed
 * @page_end: page index of the last page to be flushed + 1
 *
 * Pages in [@page_start,@page_end) of @chunk are about to be
 * unmapped.  Flush cache.  As each flushing trial can be very
 * expensive, issue flush on the whole region at once rather than
 * doing it for each cpu.  This could be an overkill but is more
 * scalable.
 */
static void pcpu_pre_unmap_flush(struct pcpu_chunk *chunk,
				 int page_start, int page_end)
{
721 722 723
	flush_cache_vunmap(
		pcpu_chunk_addr(chunk, pcpu_first_unit_cpu, page_start),
		pcpu_chunk_addr(chunk, pcpu_last_unit_cpu, page_end));
T
Tejun Heo 已提交
724 725 726 727 728 729
}

static void __pcpu_unmap_pages(unsigned long addr, int nr_pages)
{
	unmap_kernel_range_noflush(addr, nr_pages << PAGE_SHIFT);
}
730

T
Tejun Heo 已提交
731 732
/**
 * pcpu_unmap_pages - unmap pages out of a pcpu_chunk
733
 * @chunk: chunk of interest
T
Tejun Heo 已提交
734 735
 * @pages: pages array which can be used to pass information to free
 * @populated: populated bitmap
736 737 738 739
 * @page_start: page index of the first page to unmap
 * @page_end: page index of the last page to unmap + 1
 *
 * For each cpu, unmap pages [@page_start,@page_end) out of @chunk.
T
Tejun Heo 已提交
740 741 742 743
 * Corresponding elements in @pages were cleared by the caller and can
 * be used to carry information to pcpu_free_pages() which will be
 * called after all unmaps are finished.  The caller should call
 * proper pre/post flush functions.
744
 */
T
Tejun Heo 已提交
745 746 747
static void pcpu_unmap_pages(struct pcpu_chunk *chunk,
			     struct page **pages, unsigned long *populated,
			     int page_start, int page_end)
748 749
{
	unsigned int cpu;
T
Tejun Heo 已提交
750
	int i;
751

T
Tejun Heo 已提交
752 753 754
	for_each_possible_cpu(cpu) {
		for (i = page_start; i < page_end; i++) {
			struct page *page;
755

T
Tejun Heo 已提交
756 757 758
			page = pcpu_chunk_page(chunk, cpu, i);
			WARN_ON(!page);
			pages[pcpu_page_idx(cpu, i)] = page;
759
		}
T
Tejun Heo 已提交
760 761
		__pcpu_unmap_pages(pcpu_chunk_addr(chunk, cpu, page_start),
				   page_end - page_start);
762 763
	}

T
Tejun Heo 已提交
764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783
	for (i = page_start; i < page_end; i++)
		__clear_bit(i, populated);
}

/**
 * pcpu_post_unmap_tlb_flush - flush TLB after unmapping
 * @chunk: pcpu_chunk the regions to be flushed belong to
 * @page_start: page index of the first page to be flushed
 * @page_end: page index of the last page to be flushed + 1
 *
 * Pages [@page_start,@page_end) of @chunk have been unmapped.  Flush
 * TLB for the regions.  This can be skipped if the area is to be
 * returned to vmalloc as vmalloc will handle TLB flushing lazily.
 *
 * As with pcpu_pre_unmap_flush(), TLB flushing also is done at once
 * for the whole region.
 */
static void pcpu_post_unmap_tlb_flush(struct pcpu_chunk *chunk,
				      int page_start, int page_end)
{
784 785 786
	flush_tlb_kernel_range(
		pcpu_chunk_addr(chunk, pcpu_first_unit_cpu, page_start),
		pcpu_chunk_addr(chunk, pcpu_last_unit_cpu, page_end));
787 788
}

789 790 791 792 793
static int __pcpu_map_pages(unsigned long addr, struct page **pages,
			    int nr_pages)
{
	return map_kernel_range_noflush(addr, nr_pages << PAGE_SHIFT,
					PAGE_KERNEL, pages);
794 795 796
}

/**
T
Tejun Heo 已提交
797
 * pcpu_map_pages - map pages into a pcpu_chunk
798
 * @chunk: chunk of interest
T
Tejun Heo 已提交
799 800
 * @pages: pages array containing pages to be mapped
 * @populated: populated bitmap
801 802 803
 * @page_start: page index of the first page to map
 * @page_end: page index of the last page to map + 1
 *
T
Tejun Heo 已提交
804 805 806 807 808 809 810
 * For each cpu, map pages [@page_start,@page_end) into @chunk.  The
 * caller is responsible for calling pcpu_post_map_flush() after all
 * mappings are complete.
 *
 * This function is responsible for setting corresponding bits in
 * @chunk->populated bitmap and whatever is necessary for reverse
 * lookup (addr -> chunk).
811
 */
T
Tejun Heo 已提交
812 813 814
static int pcpu_map_pages(struct pcpu_chunk *chunk,
			  struct page **pages, unsigned long *populated,
			  int page_start, int page_end)
815
{
T
Tejun Heo 已提交
816 817
	unsigned int cpu, tcpu;
	int i, err;
818

819
	for_each_possible_cpu(cpu) {
820
		err = __pcpu_map_pages(pcpu_chunk_addr(chunk, cpu, page_start),
T
Tejun Heo 已提交
821
				       &pages[pcpu_page_idx(cpu, page_start)],
822
				       page_end - page_start);
823
		if (err < 0)
T
Tejun Heo 已提交
824
			goto err;
825 826
	}

T
Tejun Heo 已提交
827 828 829 830 831 832
	/* mapping successful, link chunk and mark populated */
	for (i = page_start; i < page_end; i++) {
		for_each_possible_cpu(cpu)
			pcpu_set_page_chunk(pages[pcpu_page_idx(cpu, i)],
					    chunk);
		__set_bit(i, populated);
833 834 835
	}

	return 0;
T
Tejun Heo 已提交
836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861

err:
	for_each_possible_cpu(tcpu) {
		if (tcpu == cpu)
			break;
		__pcpu_unmap_pages(pcpu_chunk_addr(chunk, tcpu, page_start),
				   page_end - page_start);
	}
	return err;
}

/**
 * pcpu_post_map_flush - flush cache after mapping
 * @chunk: pcpu_chunk the regions to be flushed belong to
 * @page_start: page index of the first page to be flushed
 * @page_end: page index of the last page to be flushed + 1
 *
 * Pages [@page_start,@page_end) of @chunk have been mapped.  Flush
 * cache.
 *
 * As with pcpu_pre_unmap_flush(), TLB flushing also is done at once
 * for the whole region.
 */
static void pcpu_post_map_flush(struct pcpu_chunk *chunk,
				int page_start, int page_end)
{
862 863 864
	flush_cache_vmap(
		pcpu_chunk_addr(chunk, pcpu_first_unit_cpu, page_start),
		pcpu_chunk_addr(chunk, pcpu_last_unit_cpu, page_end));
865 866
}

867 868 869 870
/**
 * pcpu_depopulate_chunk - depopulate and unmap an area of a pcpu_chunk
 * @chunk: chunk to depopulate
 * @off: offset to the area to depopulate
T
Tejun Heo 已提交
871
 * @size: size of the area to depopulate in bytes
872 873 874 875 876
 * @flush: whether to flush cache and tlb or not
 *
 * For each cpu, depopulate and unmap pages [@page_start,@page_end)
 * from @chunk.  If @flush is true, vcache is flushed before unmapping
 * and tlb after.
877 878 879
 *
 * CONTEXT:
 * pcpu_alloc_mutex.
880
 */
T
Tejun Heo 已提交
881
static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk, int off, int size)
882 883 884
{
	int page_start = PFN_DOWN(off);
	int page_end = PFN_UP(off + size);
T
Tejun Heo 已提交
885 886 887 888 889 890 891 892 893 894
	struct page **pages;
	unsigned long *populated;
	int rs, re;

	/* quick path, check whether it's empty already */
	pcpu_for_each_unpop_region(chunk, rs, re, page_start, page_end) {
		if (rs == page_start && re == page_end)
			return;
		break;
	}
895

T
Tejun Heo 已提交
896 897
	/* immutable chunks can't be depopulated */
	WARN_ON(chunk->immutable);
898

T
Tejun Heo 已提交
899 900 901 902 903 904 905
	/*
	 * If control reaches here, there must have been at least one
	 * successful population attempt so the temp pages array must
	 * be available now.
	 */
	pages = pcpu_get_pages_and_bitmap(chunk, &populated, false);
	BUG_ON(!pages);
906

T
Tejun Heo 已提交
907 908
	/* unmap and free */
	pcpu_pre_unmap_flush(chunk, page_start, page_end);
909

T
Tejun Heo 已提交
910 911
	pcpu_for_each_pop_region(chunk, rs, re, page_start, page_end)
		pcpu_unmap_pages(chunk, pages, populated, rs, re);
912

T
Tejun Heo 已提交
913 914 915 916
	/* no need to flush tlb, vmalloc will handle it lazily */

	pcpu_for_each_pop_region(chunk, rs, re, page_start, page_end)
		pcpu_free_pages(chunk, pages, populated, rs, re);
917

T
Tejun Heo 已提交
918 919
	/* commit new bitmap */
	bitmap_copy(chunk->populated, populated, pcpu_unit_pages);
920 921 922 923 924 925
}

/**
 * pcpu_populate_chunk - populate and map an area of a pcpu_chunk
 * @chunk: chunk of interest
 * @off: offset to the area to populate
T
Tejun Heo 已提交
926
 * @size: size of the area to populate in bytes
927 928 929
 *
 * For each cpu, populate and map pages [@page_start,@page_end) into
 * @chunk.  The area is cleared on return.
930 931 932
 *
 * CONTEXT:
 * pcpu_alloc_mutex, does GFP_KERNEL allocation.
933 934 935 936 937
 */
static int pcpu_populate_chunk(struct pcpu_chunk *chunk, int off, int size)
{
	int page_start = PFN_DOWN(off);
	int page_end = PFN_UP(off + size);
T
Tejun Heo 已提交
938 939 940
	int free_end = page_start, unmap_end = page_start;
	struct page **pages;
	unsigned long *populated;
941
	unsigned int cpu;
T
Tejun Heo 已提交
942
	int rs, re, rc;
943

T
Tejun Heo 已提交
944 945 946 947 948 949
	/* quick path, check whether all pages are already there */
	pcpu_for_each_pop_region(chunk, rs, re, page_start, page_end) {
		if (rs == page_start && re == page_end)
			goto clear;
		break;
	}
950

T
Tejun Heo 已提交
951 952
	/* need to allocate and map pages, this chunk can't be immutable */
	WARN_ON(chunk->immutable);
953

T
Tejun Heo 已提交
954 955 956
	pages = pcpu_get_pages_and_bitmap(chunk, &populated, true);
	if (!pages)
		return -ENOMEM;
957

T
Tejun Heo 已提交
958 959 960 961 962 963
	/* alloc and map */
	pcpu_for_each_unpop_region(chunk, rs, re, page_start, page_end) {
		rc = pcpu_alloc_pages(chunk, pages, populated, rs, re);
		if (rc)
			goto err_free;
		free_end = re;
964 965
	}

T
Tejun Heo 已提交
966 967 968 969 970 971 972
	pcpu_for_each_unpop_region(chunk, rs, re, page_start, page_end) {
		rc = pcpu_map_pages(chunk, pages, populated, rs, re);
		if (rc)
			goto err_unmap;
		unmap_end = re;
	}
	pcpu_post_map_flush(chunk, page_start, page_end);
973

T
Tejun Heo 已提交
974 975 976
	/* commit new bitmap */
	bitmap_copy(chunk->populated, populated, pcpu_unit_pages);
clear:
977
	for_each_possible_cpu(cpu)
978
		memset((void *)pcpu_chunk_addr(chunk, cpu, 0) + off, 0, size);
979
	return 0;
T
Tejun Heo 已提交
980 981 982 983 984 985 986 987 988 989

err_unmap:
	pcpu_pre_unmap_flush(chunk, page_start, unmap_end);
	pcpu_for_each_unpop_region(chunk, rs, re, page_start, unmap_end)
		pcpu_unmap_pages(chunk, pages, populated, rs, re);
	pcpu_post_unmap_tlb_flush(chunk, page_start, unmap_end);
err_free:
	pcpu_for_each_unpop_region(chunk, rs, re, page_start, free_end)
		pcpu_free_pages(chunk, pages, populated, rs, re);
	return rc;
990 991 992 993 994 995
}

static void free_pcpu_chunk(struct pcpu_chunk *chunk)
{
	if (!chunk)
		return;
996 997
	if (chunk->vms)
		pcpu_free_vm_areas(chunk->vms, pcpu_nr_groups);
998
	pcpu_mem_free(chunk->map, chunk->map_alloc * sizeof(chunk->map[0]));
999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
	kfree(chunk);
}

static struct pcpu_chunk *alloc_pcpu_chunk(void)
{
	struct pcpu_chunk *chunk;

	chunk = kzalloc(pcpu_chunk_struct_size, GFP_KERNEL);
	if (!chunk)
		return NULL;

1010
	chunk->map = pcpu_mem_alloc(PCPU_DFL_MAP_ALLOC * sizeof(chunk->map[0]));
1011 1012 1013
	chunk->map_alloc = PCPU_DFL_MAP_ALLOC;
	chunk->map[chunk->map_used++] = pcpu_unit_size;

1014 1015 1016 1017
	chunk->vms = pcpu_get_vm_areas(pcpu_group_offsets, pcpu_group_sizes,
				       pcpu_nr_groups, pcpu_atom_size,
				       GFP_KERNEL);
	if (!chunk->vms) {
1018 1019 1020 1021 1022 1023 1024
		free_pcpu_chunk(chunk);
		return NULL;
	}

	INIT_LIST_HEAD(&chunk->list);
	chunk->free_size = pcpu_unit_size;
	chunk->contig_hint = pcpu_unit_size;
1025
	chunk->base_addr = chunk->vms[0]->addr - pcpu_group_offsets[0];
1026 1027 1028 1029 1030

	return chunk;
}

/**
1031
 * pcpu_alloc - the percpu allocator
T
Tejun Heo 已提交
1032
 * @size: size of area to allocate in bytes
1033
 * @align: alignment of area (max PAGE_SIZE)
1034
 * @reserved: allocate from the reserved chunk if available
1035
 *
1036 1037 1038 1039
 * Allocate percpu area of @size bytes aligned at @align.
 *
 * CONTEXT:
 * Does GFP_KERNEL allocation.
1040 1041 1042 1043
 *
 * RETURNS:
 * Percpu pointer to the allocated area on success, NULL on failure.
 */
1044
static void *pcpu_alloc(size_t size, size_t align, bool reserved)
1045
{
1046
	static int warn_limit = 10;
1047
	struct pcpu_chunk *chunk;
1048
	const char *err;
1049 1050
	int slot, off;

1051
	if (unlikely(!size || size > PCPU_MIN_UNIT_SIZE || align > PAGE_SIZE)) {
1052 1053 1054 1055 1056
		WARN(true, "illegal size (%zu) or align (%zu) for "
		     "percpu allocation\n", size, align);
		return NULL;
	}

1057 1058
	mutex_lock(&pcpu_alloc_mutex);
	spin_lock_irq(&pcpu_lock);
1059

1060 1061 1062
	/* serve reserved allocations from the reserved chunk if available */
	if (reserved && pcpu_reserved_chunk) {
		chunk = pcpu_reserved_chunk;
1063
		if (size > chunk->contig_hint ||
1064 1065
		    pcpu_extend_area_map(chunk) < 0) {
			err = "failed to extend area map of reserved chunk";
1066
			goto fail_unlock;
1067
		}
1068 1069 1070
		off = pcpu_alloc_area(chunk, size, align);
		if (off >= 0)
			goto area_found;
1071
		err = "alloc from reserved chunk failed";
1072
		goto fail_unlock;
1073 1074
	}

1075
restart:
1076
	/* search through normal chunks */
1077 1078 1079 1080
	for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) {
		list_for_each_entry(chunk, &pcpu_slot[slot], list) {
			if (size > chunk->contig_hint)
				continue;
1081 1082 1083 1084 1085 1086 1087

			switch (pcpu_extend_area_map(chunk)) {
			case 0:
				break;
			case 1:
				goto restart;	/* pcpu_lock dropped, restart */
			default:
1088
				err = "failed to extend area map";
1089 1090 1091
				goto fail_unlock;
			}

1092 1093 1094 1095 1096 1097 1098
			off = pcpu_alloc_area(chunk, size, align);
			if (off >= 0)
				goto area_found;
		}
	}

	/* hmmm... no space left, create a new chunk */
1099 1100
	spin_unlock_irq(&pcpu_lock);

1101
	chunk = alloc_pcpu_chunk();
1102 1103
	if (!chunk) {
		err = "failed to allocate new chunk";
1104
		goto fail_unlock_mutex;
1105
	}
1106 1107

	spin_lock_irq(&pcpu_lock);
1108
	pcpu_chunk_relocate(chunk, -1);
1109
	goto restart;
1110 1111

area_found:
1112 1113
	spin_unlock_irq(&pcpu_lock);

1114 1115
	/* populate, map and clear the area */
	if (pcpu_populate_chunk(chunk, off, size)) {
1116
		spin_lock_irq(&pcpu_lock);
1117
		pcpu_free_area(chunk, off);
1118
		err = "failed to populate";
1119
		goto fail_unlock;
1120 1121
	}

1122 1123
	mutex_unlock(&pcpu_alloc_mutex);

T
Tejun Heo 已提交
1124 1125
	/* return address relative to base address */
	return __addr_to_pcpu_ptr(chunk->base_addr + off);
1126 1127 1128 1129 1130

fail_unlock:
	spin_unlock_irq(&pcpu_lock);
fail_unlock_mutex:
	mutex_unlock(&pcpu_alloc_mutex);
1131 1132 1133 1134 1135 1136 1137
	if (warn_limit) {
		pr_warning("PERCPU: allocation failed, size=%zu align=%zu, "
			   "%s\n", size, align, err);
		dump_stack();
		if (!--warn_limit)
			pr_info("PERCPU: limit reached, disable warning\n");
	}
1138
	return NULL;
1139
}
1140 1141 1142 1143 1144 1145 1146 1147 1148

/**
 * __alloc_percpu - allocate dynamic percpu area
 * @size: size of area to allocate in bytes
 * @align: alignment of area (max PAGE_SIZE)
 *
 * Allocate percpu area of @size bytes aligned at @align.  Might
 * sleep.  Might trigger writeouts.
 *
1149 1150 1151
 * CONTEXT:
 * Does GFP_KERNEL allocation.
 *
1152 1153 1154 1155 1156 1157 1158
 * RETURNS:
 * Percpu pointer to the allocated area on success, NULL on failure.
 */
void *__alloc_percpu(size_t size, size_t align)
{
	return pcpu_alloc(size, align, false);
}
1159 1160
EXPORT_SYMBOL_GPL(__alloc_percpu);

1161 1162 1163 1164 1165 1166 1167 1168 1169
/**
 * __alloc_reserved_percpu - allocate reserved percpu area
 * @size: size of area to allocate in bytes
 * @align: alignment of area (max PAGE_SIZE)
 *
 * Allocate percpu area of @size bytes aligned at @align from reserved
 * percpu area if arch has set it up; otherwise, allocation is served
 * from the same dynamic area.  Might sleep.  Might trigger writeouts.
 *
1170 1171 1172
 * CONTEXT:
 * Does GFP_KERNEL allocation.
 *
1173 1174 1175 1176 1177 1178 1179 1180
 * RETURNS:
 * Percpu pointer to the allocated area on success, NULL on failure.
 */
void *__alloc_reserved_percpu(size_t size, size_t align)
{
	return pcpu_alloc(size, align, true);
}

1181 1182 1183 1184 1185
/**
 * pcpu_reclaim - reclaim fully free chunks, workqueue function
 * @work: unused
 *
 * Reclaim all fully free chunks except for the first one.
1186 1187 1188
 *
 * CONTEXT:
 * workqueue context.
1189 1190
 */
static void pcpu_reclaim(struct work_struct *work)
1191
{
1192 1193 1194 1195
	LIST_HEAD(todo);
	struct list_head *head = &pcpu_slot[pcpu_nr_slots - 1];
	struct pcpu_chunk *chunk, *next;

1196 1197
	mutex_lock(&pcpu_alloc_mutex);
	spin_lock_irq(&pcpu_lock);
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208

	list_for_each_entry_safe(chunk, next, head, list) {
		WARN_ON(chunk->immutable);

		/* spare the first one */
		if (chunk == list_first_entry(head, struct pcpu_chunk, list))
			continue;

		list_move(&chunk->list, &todo);
	}

1209
	spin_unlock_irq(&pcpu_lock);
1210 1211

	list_for_each_entry_safe(chunk, next, &todo, list) {
T
Tejun Heo 已提交
1212
		pcpu_depopulate_chunk(chunk, 0, pcpu_unit_size);
1213 1214
		free_pcpu_chunk(chunk);
	}
T
Tejun Heo 已提交
1215 1216

	mutex_unlock(&pcpu_alloc_mutex);
1217 1218 1219 1220 1221 1222
}

/**
 * free_percpu - free percpu area
 * @ptr: pointer to area to free
 *
1223 1224 1225 1226
 * Free percpu area @ptr.
 *
 * CONTEXT:
 * Can be called from atomic context.
1227 1228 1229 1230 1231
 */
void free_percpu(void *ptr)
{
	void *addr = __pcpu_ptr_to_addr(ptr);
	struct pcpu_chunk *chunk;
1232
	unsigned long flags;
1233 1234 1235 1236 1237
	int off;

	if (!ptr)
		return;

1238
	spin_lock_irqsave(&pcpu_lock, flags);
1239 1240

	chunk = pcpu_chunk_addr_search(addr);
T
Tejun Heo 已提交
1241
	off = addr - chunk->base_addr;
1242 1243 1244

	pcpu_free_area(chunk, off);

1245
	/* if there are more than one fully free chunks, wake up grim reaper */
1246 1247 1248
	if (chunk->free_size == pcpu_unit_size) {
		struct pcpu_chunk *pos;

1249
		list_for_each_entry(pos, &pcpu_slot[pcpu_nr_slots - 1], list)
1250
			if (pos != chunk) {
1251
				schedule_work(&pcpu_reclaim_work);
1252 1253 1254 1255
				break;
			}
	}

1256
	spin_unlock_irqrestore(&pcpu_lock, flags);
1257 1258 1259
}
EXPORT_SYMBOL_GPL(free_percpu);

1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273
static inline size_t pcpu_calc_fc_sizes(size_t static_size,
					size_t reserved_size,
					ssize_t *dyn_sizep)
{
	size_t size_sum;

	size_sum = PFN_ALIGN(static_size + reserved_size +
			     (*dyn_sizep >= 0 ? *dyn_sizep : 0));
	if (*dyn_sizep != 0)
		*dyn_sizep = size_sum - static_size - reserved_size;

	return size_sum;
}

1274
/**
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330
 * pcpu_alloc_alloc_info - allocate percpu allocation info
 * @nr_groups: the number of groups
 * @nr_units: the number of units
 *
 * Allocate ai which is large enough for @nr_groups groups containing
 * @nr_units units.  The returned ai's groups[0].cpu_map points to the
 * cpu_map array which is long enough for @nr_units and filled with
 * NR_CPUS.  It's the caller's responsibility to initialize cpu_map
 * pointer of other groups.
 *
 * RETURNS:
 * Pointer to the allocated pcpu_alloc_info on success, NULL on
 * failure.
 */
struct pcpu_alloc_info * __init pcpu_alloc_alloc_info(int nr_groups,
						      int nr_units)
{
	struct pcpu_alloc_info *ai;
	size_t base_size, ai_size;
	void *ptr;
	int unit;

	base_size = ALIGN(sizeof(*ai) + nr_groups * sizeof(ai->groups[0]),
			  __alignof__(ai->groups[0].cpu_map[0]));
	ai_size = base_size + nr_units * sizeof(ai->groups[0].cpu_map[0]);

	ptr = alloc_bootmem_nopanic(PFN_ALIGN(ai_size));
	if (!ptr)
		return NULL;
	ai = ptr;
	ptr += base_size;

	ai->groups[0].cpu_map = ptr;

	for (unit = 0; unit < nr_units; unit++)
		ai->groups[0].cpu_map[unit] = NR_CPUS;

	ai->nr_groups = nr_groups;
	ai->__ai_size = PFN_ALIGN(ai_size);

	return ai;
}

/**
 * pcpu_free_alloc_info - free percpu allocation info
 * @ai: pcpu_alloc_info to free
 *
 * Free @ai which was allocated by pcpu_alloc_alloc_info().
 */
void __init pcpu_free_alloc_info(struct pcpu_alloc_info *ai)
{
	free_bootmem(__pa(ai), ai->__ai_size);
}

/**
 * pcpu_build_alloc_info - build alloc_info considering distances between CPUs
1331
 * @reserved_size: the size of reserved percpu area in bytes
1332
 * @dyn_size: free size for dynamic allocation in bytes, -1 for auto
1333 1334
 * @atom_size: allocation atom size
 * @cpu_distance_fn: callback to determine distance between cpus, optional
1335
 *
1336 1337 1338
 * This function determines grouping of units, their mappings to cpus
 * and other parameters considering needed percpu size, allocation
 * atom size and distances between CPUs.
1339
 *
1340 1341 1342 1343 1344
 * Groups are always mutliples of atom size and CPUs which are of
 * LOCAL_DISTANCE both ways are grouped together and share space for
 * units in the same group.  The returned configuration is guaranteed
 * to have CPUs on different nodes on different groups and >=75% usage
 * of allocated virtual address space.
1345 1346
 *
 * RETURNS:
1347 1348
 * On success, pointer to the new allocation_info is returned.  On
 * failure, ERR_PTR value is returned.
1349
 */
1350 1351 1352 1353
struct pcpu_alloc_info * __init pcpu_build_alloc_info(
				size_t reserved_size, ssize_t dyn_size,
				size_t atom_size,
				pcpu_fc_cpu_distance_fn_t cpu_distance_fn)
1354 1355 1356 1357
{
	static int group_map[NR_CPUS] __initdata;
	static int group_cnt[NR_CPUS] __initdata;
	const size_t static_size = __per_cpu_end - __per_cpu_start;
1358
	int group_cnt_max = 0, nr_groups = 1, nr_units = 0;
1359 1360
	size_t size_sum, min_unit_size, alloc_size;
	int upa, max_upa, uninitialized_var(best_upa);	/* units_per_alloc */
1361
	int last_allocs, group, unit;
1362
	unsigned int cpu, tcpu;
1363 1364
	struct pcpu_alloc_info *ai;
	unsigned int *cpu_map;
1365

1366 1367 1368 1369
	/* this function may be called multiple times */
	memset(group_map, 0, sizeof(group_map));
	memset(group_cnt, 0, sizeof(group_map));

1370 1371
	/*
	 * Determine min_unit_size, alloc_size and max_upa such that
1372
	 * alloc_size is multiple of atom_size and is the smallest
1373 1374 1375
	 * which can accomodate 4k aligned segments which are equal to
	 * or larger than min_unit_size.
	 */
1376
	size_sum = pcpu_calc_fc_sizes(static_size, reserved_size, &dyn_size);
1377 1378
	min_unit_size = max_t(size_t, size_sum, PCPU_MIN_UNIT_SIZE);

1379
	alloc_size = roundup(min_unit_size, atom_size);
1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391
	upa = alloc_size / min_unit_size;
	while (alloc_size % upa || ((alloc_size / upa) & ~PAGE_MASK))
		upa--;
	max_upa = upa;

	/* group cpus according to their proximity */
	for_each_possible_cpu(cpu) {
		group = 0;
	next_group:
		for_each_possible_cpu(tcpu) {
			if (cpu == tcpu)
				break;
1392
			if (group_map[tcpu] == group && cpu_distance_fn &&
1393 1394 1395
			    (cpu_distance_fn(cpu, tcpu) > LOCAL_DISTANCE ||
			     cpu_distance_fn(tcpu, cpu) > LOCAL_DISTANCE)) {
				group++;
1396
				nr_groups = max(nr_groups, group + 1);
1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416
				goto next_group;
			}
		}
		group_map[cpu] = group;
		group_cnt[group]++;
		group_cnt_max = max(group_cnt_max, group_cnt[group]);
	}

	/*
	 * Expand unit size until address space usage goes over 75%
	 * and then as much as possible without using more address
	 * space.
	 */
	last_allocs = INT_MAX;
	for (upa = max_upa; upa; upa--) {
		int allocs = 0, wasted = 0;

		if (alloc_size % upa || ((alloc_size / upa) & ~PAGE_MASK))
			continue;

1417
		for (group = 0; group < nr_groups; group++) {
1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436
			int this_allocs = DIV_ROUND_UP(group_cnt[group], upa);
			allocs += this_allocs;
			wasted += this_allocs * upa - group_cnt[group];
		}

		/*
		 * Don't accept if wastage is over 25%.  The
		 * greater-than comparison ensures upa==1 always
		 * passes the following check.
		 */
		if (wasted > num_possible_cpus() / 3)
			continue;

		/* and then don't consume more memory */
		if (allocs > last_allocs)
			break;
		last_allocs = allocs;
		best_upa = upa;
	}
1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468
	upa = best_upa;

	/* allocate and fill alloc_info */
	for (group = 0; group < nr_groups; group++)
		nr_units += roundup(group_cnt[group], upa);

	ai = pcpu_alloc_alloc_info(nr_groups, nr_units);
	if (!ai)
		return ERR_PTR(-ENOMEM);
	cpu_map = ai->groups[0].cpu_map;

	for (group = 0; group < nr_groups; group++) {
		ai->groups[group].cpu_map = cpu_map;
		cpu_map += roundup(group_cnt[group], upa);
	}

	ai->static_size = static_size;
	ai->reserved_size = reserved_size;
	ai->dyn_size = dyn_size;
	ai->unit_size = alloc_size / upa;
	ai->atom_size = atom_size;
	ai->alloc_size = alloc_size;

	for (group = 0, unit = 0; group_cnt[group]; group++) {
		struct pcpu_group_info *gi = &ai->groups[group];

		/*
		 * Initialize base_offset as if all groups are located
		 * back-to-back.  The caller should update this to
		 * reflect actual allocation.
		 */
		gi->base_offset = unit * ai->unit_size;
1469 1470 1471

		for_each_possible_cpu(cpu)
			if (group_map[cpu] == group)
1472 1473 1474
				gi->cpu_map[gi->nr_units++] = cpu;
		gi->nr_units = roundup(gi->nr_units, upa);
		unit += gi->nr_units;
1475
	}
1476
	BUG_ON(unit != nr_units);
1477

1478
	return ai;
1479 1480
}

1481 1482 1483 1484 1485 1486 1487 1488 1489
/**
 * pcpu_dump_alloc_info - print out information about pcpu_alloc_info
 * @lvl: loglevel
 * @ai: allocation info to dump
 *
 * Print out information about @ai using loglevel @lvl.
 */
static void pcpu_dump_alloc_info(const char *lvl,
				 const struct pcpu_alloc_info *ai)
1490
{
1491
	int group_width = 1, cpu_width = 1, width;
1492
	char empty_str[] = "--------";
1493 1494 1495 1496 1497 1498 1499
	int alloc = 0, alloc_end = 0;
	int group, v;
	int upa, apl;	/* units per alloc, allocs per line */

	v = ai->nr_groups;
	while (v /= 10)
		group_width++;
1500

1501
	v = num_possible_cpus();
1502
	while (v /= 10)
1503 1504
		cpu_width++;
	empty_str[min_t(int, cpu_width, sizeof(empty_str) - 1)] = '\0';
1505

1506 1507 1508
	upa = ai->alloc_size / ai->unit_size;
	width = upa * (cpu_width + 1) + group_width + 3;
	apl = rounddown_pow_of_two(max(60 / width, 1));
1509

1510 1511 1512
	printk("%spcpu-alloc: s%zu r%zu d%zu u%zu alloc=%zu*%zu",
	       lvl, ai->static_size, ai->reserved_size, ai->dyn_size,
	       ai->unit_size, ai->alloc_size / ai->atom_size, ai->atom_size);
1513

1514 1515 1516 1517 1518 1519 1520 1521
	for (group = 0; group < ai->nr_groups; group++) {
		const struct pcpu_group_info *gi = &ai->groups[group];
		int unit = 0, unit_end = 0;

		BUG_ON(gi->nr_units % upa);
		for (alloc_end += gi->nr_units / upa;
		     alloc < alloc_end; alloc++) {
			if (!(alloc % apl)) {
1522
				printk("\n");
1523 1524 1525 1526 1527 1528 1529 1530 1531 1532
				printk("%spcpu-alloc: ", lvl);
			}
			printk("[%0*d] ", group_width, group);

			for (unit_end += upa; unit < unit_end; unit++)
				if (gi->cpu_map[unit] != NR_CPUS)
					printk("%0*d ", cpu_width,
					       gi->cpu_map[unit]);
				else
					printk("%s ", empty_str);
1533 1534 1535 1536 1537
		}
	}
	printk("\n");
}

1538
/**
1539
 * pcpu_setup_first_chunk - initialize the first percpu chunk
1540
 * @ai: pcpu_alloc_info describing how to percpu area is shaped
1541
 * @base_addr: mapped address
1542 1543 1544
 *
 * Initialize the first percpu chunk which contains the kernel static
 * perpcu area.  This function is to be called from arch percpu area
1545
 * setup path.
1546
 *
1547 1548 1549 1550 1551 1552
 * @ai contains all information necessary to initialize the first
 * chunk and prime the dynamic percpu allocator.
 *
 * @ai->static_size is the size of static percpu area.
 *
 * @ai->reserved_size, if non-zero, specifies the amount of bytes to
1553 1554 1555 1556 1557 1558 1559
 * reserve after the static area in the first chunk.  This reserves
 * the first chunk such that it's available only through reserved
 * percpu allocation.  This is primarily used to serve module percpu
 * static areas on architectures where the addressing model has
 * limited offset range for symbol relocations to guarantee module
 * percpu symbols fall inside the relocatable range.
 *
1560 1561 1562
 * @ai->dyn_size determines the number of bytes available for dynamic
 * allocation in the first chunk.  The area between @ai->static_size +
 * @ai->reserved_size + @ai->dyn_size and @ai->unit_size is unused.
1563
 *
1564 1565 1566
 * @ai->unit_size specifies unit size and must be aligned to PAGE_SIZE
 * and equal to or larger than @ai->static_size + @ai->reserved_size +
 * @ai->dyn_size.
1567
 *
1568 1569
 * @ai->atom_size is the allocation atom size and used as alignment
 * for vm areas.
1570
 *
1571 1572 1573 1574 1575 1576 1577 1578 1579
 * @ai->alloc_size is the allocation size and always multiple of
 * @ai->atom_size.  This is larger than @ai->atom_size if
 * @ai->unit_size is larger than @ai->atom_size.
 *
 * @ai->nr_groups and @ai->groups describe virtual memory layout of
 * percpu areas.  Units which should be colocated are put into the
 * same group.  Dynamic VM areas will be allocated according to these
 * groupings.  If @ai->nr_groups is zero, a single group containing
 * all units is assumed.
1580
 *
1581 1582
 * The caller should have mapped the first chunk at @base_addr and
 * copied static data to each unit.
1583
 *
1584 1585 1586 1587 1588 1589 1590
 * If the first chunk ends up with both reserved and dynamic areas, it
 * is served by two chunks - one to serve the core static and reserved
 * areas and the other for the dynamic area.  They share the same vm
 * and page map but uses different area allocation map to stay away
 * from each other.  The latter chunk is circulated in the chunk slots
 * and available for dynamic allocation like any other chunks.
 *
1591
 * RETURNS:
T
Tejun Heo 已提交
1592
 * 0 on success, -errno on failure.
1593
 */
T
Tejun Heo 已提交
1594 1595
int __init pcpu_setup_first_chunk(const struct pcpu_alloc_info *ai,
				  void *base_addr)
1596
{
1597
	static char cpus_buf[4096] __initdata;
1598
	static int smap[2], dmap[2];
1599 1600
	size_t dyn_size = ai->dyn_size;
	size_t size_sum = ai->static_size + ai->reserved_size + dyn_size;
1601
	struct pcpu_chunk *schunk, *dchunk = NULL;
1602 1603
	unsigned long *group_offsets;
	size_t *group_sizes;
T
Tejun Heo 已提交
1604
	unsigned long *unit_off;
1605
	unsigned int cpu;
1606 1607
	int *unit_map;
	int group, unit, i;
1608

1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619
	cpumask_scnprintf(cpus_buf, sizeof(cpus_buf), cpu_possible_mask);

#define PCPU_SETUP_BUG_ON(cond)	do {					\
	if (unlikely(cond)) {						\
		pr_emerg("PERCPU: failed to initialize, %s", #cond);	\
		pr_emerg("PERCPU: cpu_possible_mask=%s\n", cpus_buf);	\
		pcpu_dump_alloc_info(KERN_EMERG, ai);			\
		BUG();							\
	}								\
} while (0)

1620
	/* sanity checks */
1621 1622
	BUILD_BUG_ON(ARRAY_SIZE(smap) >= PCPU_DFL_MAP_ALLOC ||
		     ARRAY_SIZE(dmap) >= PCPU_DFL_MAP_ALLOC);
1623 1624 1625 1626 1627 1628
	PCPU_SETUP_BUG_ON(ai->nr_groups <= 0);
	PCPU_SETUP_BUG_ON(!ai->static_size);
	PCPU_SETUP_BUG_ON(!base_addr);
	PCPU_SETUP_BUG_ON(ai->unit_size < size_sum);
	PCPU_SETUP_BUG_ON(ai->unit_size & ~PAGE_MASK);
	PCPU_SETUP_BUG_ON(ai->unit_size < PCPU_MIN_UNIT_SIZE);
1629

1630 1631 1632
	/* process group information and build config tables accordingly */
	group_offsets = alloc_bootmem(ai->nr_groups * sizeof(group_offsets[0]));
	group_sizes = alloc_bootmem(ai->nr_groups * sizeof(group_sizes[0]));
1633
	unit_map = alloc_bootmem(nr_cpu_ids * sizeof(unit_map[0]));
T
Tejun Heo 已提交
1634
	unit_off = alloc_bootmem(nr_cpu_ids * sizeof(unit_off[0]));
1635

1636
	for (cpu = 0; cpu < nr_cpu_ids; cpu++)
1637
		unit_map[cpu] = UINT_MAX;
1638
	pcpu_first_unit_cpu = NR_CPUS;
1639

1640 1641
	for (group = 0, unit = 0; group < ai->nr_groups; group++, unit += i) {
		const struct pcpu_group_info *gi = &ai->groups[group];
1642

1643 1644 1645
		group_offsets[group] = gi->base_offset;
		group_sizes[group] = gi->nr_units * ai->unit_size;

1646 1647 1648 1649
		for (i = 0; i < gi->nr_units; i++) {
			cpu = gi->cpu_map[i];
			if (cpu == NR_CPUS)
				continue;
1650

1651 1652 1653
			PCPU_SETUP_BUG_ON(cpu > nr_cpu_ids);
			PCPU_SETUP_BUG_ON(!cpu_possible(cpu));
			PCPU_SETUP_BUG_ON(unit_map[cpu] != UINT_MAX);
1654

1655
			unit_map[cpu] = unit + i;
T
Tejun Heo 已提交
1656 1657
			unit_off[cpu] = gi->base_offset + i * ai->unit_size;

1658 1659 1660
			if (pcpu_first_unit_cpu == NR_CPUS)
				pcpu_first_unit_cpu = cpu;
		}
1661
	}
1662 1663 1664 1665
	pcpu_last_unit_cpu = cpu;
	pcpu_nr_units = unit;

	for_each_possible_cpu(cpu)
1666 1667 1668 1669 1670
		PCPU_SETUP_BUG_ON(unit_map[cpu] == UINT_MAX);

	/* we're done parsing the input, undefine BUG macro and dump config */
#undef PCPU_SETUP_BUG_ON
	pcpu_dump_alloc_info(KERN_INFO, ai);
1671

1672 1673 1674
	pcpu_nr_groups = ai->nr_groups;
	pcpu_group_offsets = group_offsets;
	pcpu_group_sizes = group_sizes;
1675
	pcpu_unit_map = unit_map;
T
Tejun Heo 已提交
1676
	pcpu_unit_offsets = unit_off;
1677 1678

	/* determine basic parameters */
1679
	pcpu_unit_pages = ai->unit_size >> PAGE_SHIFT;
1680
	pcpu_unit_size = pcpu_unit_pages << PAGE_SHIFT;
1681
	pcpu_atom_size = ai->atom_size;
T
Tejun Heo 已提交
1682 1683
	pcpu_chunk_struct_size = sizeof(struct pcpu_chunk) +
		BITS_TO_LONGS(pcpu_unit_pages) * sizeof(unsigned long);
1684

1685 1686 1687 1688 1689
	/*
	 * Allocate chunk slots.  The additional last slot is for
	 * empty chunks.
	 */
	pcpu_nr_slots = __pcpu_size_to_slot(pcpu_unit_size) + 2;
1690 1691 1692 1693
	pcpu_slot = alloc_bootmem(pcpu_nr_slots * sizeof(pcpu_slot[0]));
	for (i = 0; i < pcpu_nr_slots; i++)
		INIT_LIST_HEAD(&pcpu_slot[i]);

1694 1695 1696 1697 1698 1699 1700
	/*
	 * Initialize static chunk.  If reserved_size is zero, the
	 * static chunk covers static area + dynamic allocation area
	 * in the first chunk.  If reserved_size is not zero, it
	 * covers static area + reserved area (mostly used for module
	 * static percpu allocation).
	 */
1701 1702
	schunk = alloc_bootmem(pcpu_chunk_struct_size);
	INIT_LIST_HEAD(&schunk->list);
T
Tejun Heo 已提交
1703
	schunk->base_addr = base_addr;
1704 1705
	schunk->map = smap;
	schunk->map_alloc = ARRAY_SIZE(smap);
1706
	schunk->immutable = true;
T
Tejun Heo 已提交
1707
	bitmap_fill(schunk->populated, pcpu_unit_pages);
1708

1709 1710
	if (ai->reserved_size) {
		schunk->free_size = ai->reserved_size;
1711
		pcpu_reserved_chunk = schunk;
1712
		pcpu_reserved_chunk_limit = ai->static_size + ai->reserved_size;
1713 1714 1715 1716
	} else {
		schunk->free_size = dyn_size;
		dyn_size = 0;			/* dynamic area covered */
	}
1717
	schunk->contig_hint = schunk->free_size;
1718

1719
	schunk->map[schunk->map_used++] = -ai->static_size;
1720 1721 1722
	if (schunk->free_size)
		schunk->map[schunk->map_used++] = schunk->free_size;

1723 1724
	/* init dynamic chunk if necessary */
	if (dyn_size) {
T
Tejun Heo 已提交
1725
		dchunk = alloc_bootmem(pcpu_chunk_struct_size);
1726
		INIT_LIST_HEAD(&dchunk->list);
T
Tejun Heo 已提交
1727
		dchunk->base_addr = base_addr;
1728 1729
		dchunk->map = dmap;
		dchunk->map_alloc = ARRAY_SIZE(dmap);
1730
		dchunk->immutable = true;
T
Tejun Heo 已提交
1731
		bitmap_fill(dchunk->populated, pcpu_unit_pages);
1732 1733 1734 1735 1736 1737

		dchunk->contig_hint = dchunk->free_size = dyn_size;
		dchunk->map[dchunk->map_used++] = -pcpu_reserved_chunk_limit;
		dchunk->map[dchunk->map_used++] = dchunk->free_size;
	}

1738
	/* link the first chunk in */
1739 1740
	pcpu_first_chunk = dchunk ?: schunk;
	pcpu_chunk_relocate(pcpu_first_chunk, -1);
1741 1742

	/* we're done */
T
Tejun Heo 已提交
1743
	pcpu_base_addr = base_addr;
T
Tejun Heo 已提交
1744
	return 0;
1745
}
1746

1747 1748 1749 1750 1751
const char *pcpu_fc_names[PCPU_FC_NR] __initdata = {
	[PCPU_FC_AUTO]	= "auto",
	[PCPU_FC_EMBED]	= "embed",
	[PCPU_FC_PAGE]	= "page",
};
1752

1753
enum pcpu_fc pcpu_chosen_fc __initdata = PCPU_FC_AUTO;
1754

1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768
static int __init percpu_alloc_setup(char *str)
{
	if (0)
		/* nada */;
#ifdef CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK
	else if (!strcmp(str, "embed"))
		pcpu_chosen_fc = PCPU_FC_EMBED;
#endif
#ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
	else if (!strcmp(str, "page"))
		pcpu_chosen_fc = PCPU_FC_PAGE;
#endif
	else
		pr_warning("PERCPU: unknown allocator %s specified\n", str);
1769

1770
	return 0;
1771
}
1772
early_param("percpu_alloc", percpu_alloc_setup);
1773

1774 1775
#if defined(CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK) || \
	!defined(CONFIG_HAVE_SETUP_PER_CPU_AREA)
1776 1777 1778 1779
/**
 * pcpu_embed_first_chunk - embed the first percpu chunk into bootmem
 * @reserved_size: the size of reserved percpu area in bytes
 * @dyn_size: free size for dynamic allocation in bytes, -1 for auto
1780 1781 1782 1783
 * @atom_size: allocation atom size
 * @cpu_distance_fn: callback to determine distance between cpus, optional
 * @alloc_fn: function to allocate percpu page
 * @free_fn: funtion to free percpu page
1784 1785 1786 1787 1788
 *
 * This is a helper to ease setting up embedded first percpu chunk and
 * can be called where pcpu_setup_first_chunk() is expected.
 *
 * If this function is used to setup the first chunk, it is allocated
1789 1790 1791 1792 1793 1794 1795 1796 1797 1798
 * by calling @alloc_fn and used as-is without being mapped into
 * vmalloc area.  Allocations are always whole multiples of @atom_size
 * aligned to @atom_size.
 *
 * This enables the first chunk to piggy back on the linear physical
 * mapping which often uses larger page size.  Please note that this
 * can result in very sparse cpu->unit mapping on NUMA machines thus
 * requiring large vmalloc address space.  Don't use this allocator if
 * vmalloc space is not orders of magnitude larger than distances
 * between node memory addresses (ie. 32bit NUMA machines).
1799 1800
 *
 * When @dyn_size is positive, dynamic area might be larger than
1801 1802 1803
 * specified to fill page alignment.  When @dyn_size is auto,
 * @dyn_size is just big enough to fill page alignment after static
 * and reserved areas.
1804 1805
 *
 * If the needed size is smaller than the minimum or specified unit
1806
 * size, the leftover is returned using @free_fn.
1807 1808
 *
 * RETURNS:
T
Tejun Heo 已提交
1809
 * 0 on success, -errno on failure.
1810
 */
1811 1812 1813 1814 1815
int __init pcpu_embed_first_chunk(size_t reserved_size, ssize_t dyn_size,
				  size_t atom_size,
				  pcpu_fc_cpu_distance_fn_t cpu_distance_fn,
				  pcpu_fc_alloc_fn_t alloc_fn,
				  pcpu_fc_free_fn_t free_fn)
1816
{
1817 1818
	void *base = (void *)ULONG_MAX;
	void **areas = NULL;
1819
	struct pcpu_alloc_info *ai;
1820
	size_t size_sum, areas_size, max_distance;
1821
	int group, i, rc;
1822

1823 1824
	ai = pcpu_build_alloc_info(reserved_size, dyn_size, atom_size,
				   cpu_distance_fn);
1825 1826
	if (IS_ERR(ai))
		return PTR_ERR(ai);
1827

1828
	size_sum = ai->static_size + ai->reserved_size + ai->dyn_size;
1829
	areas_size = PFN_ALIGN(ai->nr_groups * sizeof(void *));
1830

1831 1832
	areas = alloc_bootmem_nopanic(areas_size);
	if (!areas) {
T
Tejun Heo 已提交
1833
		rc = -ENOMEM;
1834
		goto out_free;
1835
	}
1836

1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853
	/* allocate, copy and determine base address */
	for (group = 0; group < ai->nr_groups; group++) {
		struct pcpu_group_info *gi = &ai->groups[group];
		unsigned int cpu = NR_CPUS;
		void *ptr;

		for (i = 0; i < gi->nr_units && cpu == NR_CPUS; i++)
			cpu = gi->cpu_map[i];
		BUG_ON(cpu == NR_CPUS);

		/* allocate space for the whole group */
		ptr = alloc_fn(cpu, gi->nr_units * ai->unit_size, atom_size);
		if (!ptr) {
			rc = -ENOMEM;
			goto out_free_areas;
		}
		areas[group] = ptr;
1854

1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866
		base = min(ptr, base);

		for (i = 0; i < gi->nr_units; i++, ptr += ai->unit_size) {
			if (gi->cpu_map[i] == NR_CPUS) {
				/* unused unit, free whole */
				free_fn(ptr, ai->unit_size);
				continue;
			}
			/* copy and return the unused part */
			memcpy(ptr, __per_cpu_load, ai->static_size);
			free_fn(ptr + size_sum, ai->unit_size - size_sum);
		}
1867
	}
1868

1869
	/* base address is now known, determine group base offsets */
1870 1871
	max_distance = 0;
	for (group = 0; group < ai->nr_groups; group++) {
1872
		ai->groups[group].base_offset = areas[group] - base;
1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887
		max_distance = max(max_distance, ai->groups[group].base_offset);
	}
	max_distance += ai->unit_size;

	/* warn if maximum distance is further than 75% of vmalloc space */
	if (max_distance > (VMALLOC_END - VMALLOC_START) * 3 / 4) {
		pr_warning("PERCPU: max_distance=0x%lx too large for vmalloc "
			   "space 0x%lx\n",
			   max_distance, VMALLOC_END - VMALLOC_START);
#ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
		/* and fail if we have fallback */
		rc = -EINVAL;
		goto out_free;
#endif
	}
1888

T
Tejun Heo 已提交
1889
	pr_info("PERCPU: Embedded %zu pages/cpu @%p s%zu r%zu d%zu u%zu\n",
1890 1891
		PFN_DOWN(size_sum), base, ai->static_size, ai->reserved_size,
		ai->dyn_size, ai->unit_size);
1892

T
Tejun Heo 已提交
1893
	rc = pcpu_setup_first_chunk(ai, base);
1894 1895 1896 1897 1898 1899 1900
	goto out_free;

out_free_areas:
	for (group = 0; group < ai->nr_groups; group++)
		free_fn(areas[group],
			ai->groups[group].nr_units * ai->unit_size);
out_free:
1901
	pcpu_free_alloc_info(ai);
1902 1903
	if (areas)
		free_bootmem(__pa(areas), areas_size);
T
Tejun Heo 已提交
1904
	return rc;
1905
}
1906 1907
#endif /* CONFIG_NEED_PER_CPU_EMBED_FIRST_CHUNK ||
	  !CONFIG_HAVE_SETUP_PER_CPU_AREA */
1908

1909
#ifdef CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK
1910
/**
1911
 * pcpu_page_first_chunk - map the first chunk using PAGE_SIZE pages
1912 1913 1914 1915 1916
 * @reserved_size: the size of reserved percpu area in bytes
 * @alloc_fn: function to allocate percpu page, always called with PAGE_SIZE
 * @free_fn: funtion to free percpu page, always called with PAGE_SIZE
 * @populate_pte_fn: function to populate pte
 *
1917 1918
 * This is a helper to ease setting up page-remapped first percpu
 * chunk and can be called where pcpu_setup_first_chunk() is expected.
1919 1920 1921 1922 1923
 *
 * This is the basic allocator.  Static percpu area is allocated
 * page-by-page into vmalloc area.
 *
 * RETURNS:
T
Tejun Heo 已提交
1924
 * 0 on success, -errno on failure.
1925
 */
T
Tejun Heo 已提交
1926 1927 1928 1929
int __init pcpu_page_first_chunk(size_t reserved_size,
				 pcpu_fc_alloc_fn_t alloc_fn,
				 pcpu_fc_free_fn_t free_fn,
				 pcpu_fc_populate_pte_fn_t populate_pte_fn)
1930
{
1931
	static struct vm_struct vm;
1932
	struct pcpu_alloc_info *ai;
1933
	char psize_str[16];
T
Tejun Heo 已提交
1934
	int unit_pages;
1935
	size_t pages_size;
T
Tejun Heo 已提交
1936
	struct page **pages;
T
Tejun Heo 已提交
1937
	int unit, i, j, rc;
1938

1939 1940
	snprintf(psize_str, sizeof(psize_str), "%luK", PAGE_SIZE >> 10);

1941 1942 1943 1944 1945 1946 1947
	ai = pcpu_build_alloc_info(reserved_size, -1, PAGE_SIZE, NULL);
	if (IS_ERR(ai))
		return PTR_ERR(ai);
	BUG_ON(ai->nr_groups != 1);
	BUG_ON(ai->groups[0].nr_units != num_possible_cpus());

	unit_pages = ai->unit_size >> PAGE_SHIFT;
1948 1949

	/* unaligned allocations can't be freed, round up to page size */
1950 1951
	pages_size = PFN_ALIGN(unit_pages * num_possible_cpus() *
			       sizeof(pages[0]));
T
Tejun Heo 已提交
1952
	pages = alloc_bootmem(pages_size);
1953

1954
	/* allocate pages */
1955
	j = 0;
1956
	for (unit = 0; unit < num_possible_cpus(); unit++)
T
Tejun Heo 已提交
1957
		for (i = 0; i < unit_pages; i++) {
1958
			unsigned int cpu = ai->groups[0].cpu_map[unit];
1959 1960
			void *ptr;

1961
			ptr = alloc_fn(cpu, PAGE_SIZE, PAGE_SIZE);
1962
			if (!ptr) {
1963 1964
				pr_warning("PERCPU: failed to allocate %s page "
					   "for cpu%u\n", psize_str, cpu);
1965 1966
				goto enomem;
			}
T
Tejun Heo 已提交
1967
			pages[j++] = virt_to_page(ptr);
1968 1969
		}

1970 1971
	/* allocate vm area, map the pages and copy static data */
	vm.flags = VM_ALLOC;
1972
	vm.size = num_possible_cpus() * ai->unit_size;
1973 1974
	vm_area_register_early(&vm, PAGE_SIZE);

1975
	for (unit = 0; unit < num_possible_cpus(); unit++) {
1976
		unsigned long unit_addr =
1977
			(unsigned long)vm.addr + unit * ai->unit_size;
1978

T
Tejun Heo 已提交
1979
		for (i = 0; i < unit_pages; i++)
1980 1981 1982
			populate_pte_fn(unit_addr + (i << PAGE_SHIFT));

		/* pte already populated, the following shouldn't fail */
T
Tejun Heo 已提交
1983 1984 1985 1986
		rc = __pcpu_map_pages(unit_addr, &pages[unit * unit_pages],
				      unit_pages);
		if (rc < 0)
			panic("failed to map percpu area, err=%d\n", rc);
1987

1988 1989 1990 1991 1992 1993 1994 1995 1996
		/*
		 * FIXME: Archs with virtual cache should flush local
		 * cache for the linear mapping here - something
		 * equivalent to flush_cache_vmap() on the local cpu.
		 * flush_cache_vmap() can't be used as most supporting
		 * data structures are not set up yet.
		 */

		/* copy static data */
1997
		memcpy((void *)unit_addr, __per_cpu_load, ai->static_size);
1998 1999 2000
	}

	/* we're ready, commit */
2001
	pr_info("PERCPU: %d %s pages/cpu @%p s%zu r%zu d%zu\n",
2002 2003
		unit_pages, psize_str, vm.addr, ai->static_size,
		ai->reserved_size, ai->dyn_size);
2004

T
Tejun Heo 已提交
2005
	rc = pcpu_setup_first_chunk(ai, vm.addr);
2006 2007 2008 2009
	goto out_free_ar;

enomem:
	while (--j >= 0)
T
Tejun Heo 已提交
2010
		free_fn(page_address(pages[j]), PAGE_SIZE);
T
Tejun Heo 已提交
2011
	rc = -ENOMEM;
2012
out_free_ar:
T
Tejun Heo 已提交
2013
	free_bootmem(__pa(pages), pages_size);
2014
	pcpu_free_alloc_info(ai);
T
Tejun Heo 已提交
2015
	return rc;
2016
}
2017
#endif /* CONFIG_NEED_PER_CPU_PAGE_FIRST_CHUNK */
2018

2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034
/*
 * Generic percpu area setup.
 *
 * The embedding helper is used because its behavior closely resembles
 * the original non-dynamic generic percpu area setup.  This is
 * important because many archs have addressing restrictions and might
 * fail if the percpu area is located far away from the previous
 * location.  As an added bonus, in non-NUMA cases, embedding is
 * generally a good idea TLB-wise because percpu area can piggy back
 * on the physical linear memory mapping which uses large page
 * mappings on applicable archs.
 */
#ifndef CONFIG_HAVE_SETUP_PER_CPU_AREA
unsigned long __per_cpu_offset[NR_CPUS] __read_mostly;
EXPORT_SYMBOL(__per_cpu_offset);

2035 2036 2037 2038 2039
static void * __init pcpu_dfl_fc_alloc(unsigned int cpu, size_t size,
				       size_t align)
{
	return __alloc_bootmem_nopanic(size, align, __pa(MAX_DMA_ADDRESS));
}
2040

2041 2042 2043 2044 2045
static void __init pcpu_dfl_fc_free(void *ptr, size_t size)
{
	free_bootmem(__pa(ptr), size);
}

2046 2047 2048 2049
void __init setup_per_cpu_areas(void)
{
	unsigned long delta;
	unsigned int cpu;
T
Tejun Heo 已提交
2050
	int rc;
2051 2052 2053 2054 2055

	/*
	 * Always reserve area for module percpu variables.  That's
	 * what the legacy allocator did.
	 */
T
Tejun Heo 已提交
2056
	rc = pcpu_embed_first_chunk(PERCPU_MODULE_RESERVE,
2057 2058
				    PERCPU_DYNAMIC_RESERVE, PAGE_SIZE, NULL,
				    pcpu_dfl_fc_alloc, pcpu_dfl_fc_free);
T
Tejun Heo 已提交
2059
	if (rc < 0)
2060 2061 2062 2063
		panic("Failed to initialized percpu areas.");

	delta = (unsigned long)pcpu_base_addr - (unsigned long)__per_cpu_start;
	for_each_possible_cpu(cpu)
T
Tejun Heo 已提交
2064
		__per_cpu_offset[cpu] = delta + pcpu_unit_offsets[cpu];
2065
}
2066
#endif /* CONFIG_HAVE_SETUP_PER_CPU_AREA */