percpu: replace pcpu_realloc() with pcpu_mem_alloc() and pcpu_mem_free()
[linux-2.6.git] / mm / percpu.c
1 /*
2  * linux/mm/percpu.c - percpu memory allocator
3  *
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
10  * areas.  Percpu areas are allocated in chunks in vmalloc area.  Each
11  * chunk is consisted of num_possible_cpus() units and the first chunk
12  * is used for static percpu variables in the kernel image (special
13  * boot time alloc/init handling necessary as these areas need to be
14  * brought up before allocation services are running).  Unit grows as
15  * necessary and all units grow or shrink in unison.  When a chunk is
16  * filled up, another chunk is allocated.  ie. in vmalloc area
17  *
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,
25  * c1:u1, c1:u2 and c1:u3.  Percpu access can be done by configuring
26  * percpu base registers UNIT_SIZE apart.
27  *
28  * There are usually many small percpu allocations many of them as
29  * small as 4 bytes.  The allocator organizes chunks into lists
30  * according to free size and tries to allocate from the fullest one.
31  * Each chunk keeps the maximum contiguous area size hint which is
32  * guaranteed to be eqaul to or larger than the maximum contiguous
33  * area in the chunk.  This helps the allocator not to iterate the
34  * chunk maps unnecessarily.
35  *
36  * Allocation state in each chunk is kept using an array of integers
37  * on chunk->map.  A positive value in the map represents a free
38  * region and negative allocated.  Allocation inside a chunk is done
39  * by scanning this map sequentially and serving the first matching
40  * entry.  This is mostly copied from the percpu_modalloc() allocator.
41  * Chunks are also linked into a rb tree to ease address to chunk
42  * mapping during free.
43  *
44  * To use this allocator, arch code should do the followings.
45  *
46  * - define CONFIG_HAVE_DYNAMIC_PER_CPU_AREA
47  *
48  * - define __addr_to_pcpu_ptr() and __pcpu_ptr_to_addr() to translate
49  *   regular address to percpu pointer and back
50  *
51  * - use pcpu_setup_first_chunk() during percpu area initialization to
52  *   setup the first chunk containing the kernel static percpu area
53  */
54
55 #include <linux/bitmap.h>
56 #include <linux/bootmem.h>
57 #include <linux/list.h>
58 #include <linux/mm.h>
59 #include <linux/module.h>
60 #include <linux/mutex.h>
61 #include <linux/percpu.h>
62 #include <linux/pfn.h>
63 #include <linux/rbtree.h>
64 #include <linux/slab.h>
65 #include <linux/vmalloc.h>
66
67 #include <asm/cacheflush.h>
68 #include <asm/tlbflush.h>
69
70 #define PCPU_SLOT_BASE_SHIFT            5       /* 1-31 shares the same slot */
71 #define PCPU_DFL_MAP_ALLOC              16      /* start a map with 16 ents */
72
73 struct pcpu_chunk {
74         struct list_head        list;           /* linked to pcpu_slot lists */
75         struct rb_node          rb_node;        /* key is chunk->vm->addr */
76         int                     free_size;      /* free bytes in the chunk */
77         int                     contig_hint;    /* max contiguous size hint */
78         struct vm_struct        *vm;            /* mapped vmalloc region */
79         int                     map_used;       /* # of map entries used */
80         int                     map_alloc;      /* # of map entries allocated */
81         int                     *map;           /* allocation map */
82         bool                    immutable;      /* no [de]population allowed */
83         struct page             **page;         /* points to page array */
84         struct page             *page_ar[];     /* #cpus * UNIT_PAGES */
85 };
86
87 static int pcpu_unit_pages __read_mostly;
88 static int pcpu_unit_size __read_mostly;
89 static int pcpu_chunk_size __read_mostly;
90 static int pcpu_nr_slots __read_mostly;
91 static size_t pcpu_chunk_struct_size __read_mostly;
92
93 /* the address of the first chunk which starts with the kernel static area */
94 void *pcpu_base_addr __read_mostly;
95 EXPORT_SYMBOL_GPL(pcpu_base_addr);
96
97 /* optional reserved chunk, only accessible for reserved allocations */
98 static struct pcpu_chunk *pcpu_reserved_chunk;
99 /* offset limit of the reserved chunk */
100 static int pcpu_reserved_chunk_limit;
101
102 /*
103  * One mutex to rule them all.
104  *
105  * The following mutex is grabbed in the outermost public alloc/free
106  * interface functions and released only when the operation is
107  * complete.  As such, every function in this file other than the
108  * outermost functions are called under pcpu_mutex.
109  *
110  * It can easily be switched to use spinlock such that only the area
111  * allocation and page population commit are protected with it doing
112  * actual [de]allocation without holding any lock.  However, given
113  * what this allocator does, I think it's better to let them run
114  * sequentially.
115  */
116 static DEFINE_MUTEX(pcpu_mutex);
117
118 static struct list_head *pcpu_slot __read_mostly; /* chunk list slots */
119 static struct rb_root pcpu_addr_root = RB_ROOT; /* chunks by address */
120
121 static int __pcpu_size_to_slot(int size)
122 {
123         int highbit = fls(size);        /* size is in bytes */
124         return max(highbit - PCPU_SLOT_BASE_SHIFT + 2, 1);
125 }
126
127 static int pcpu_size_to_slot(int size)
128 {
129         if (size == pcpu_unit_size)
130                 return pcpu_nr_slots - 1;
131         return __pcpu_size_to_slot(size);
132 }
133
134 static int pcpu_chunk_slot(const struct pcpu_chunk *chunk)
135 {
136         if (chunk->free_size < sizeof(int) || chunk->contig_hint < sizeof(int))
137                 return 0;
138
139         return pcpu_size_to_slot(chunk->free_size);
140 }
141
142 static int pcpu_page_idx(unsigned int cpu, int page_idx)
143 {
144         return cpu * pcpu_unit_pages + page_idx;
145 }
146
147 static struct page **pcpu_chunk_pagep(struct pcpu_chunk *chunk,
148                                       unsigned int cpu, int page_idx)
149 {
150         return &chunk->page[pcpu_page_idx(cpu, page_idx)];
151 }
152
153 static unsigned long pcpu_chunk_addr(struct pcpu_chunk *chunk,
154                                      unsigned int cpu, int page_idx)
155 {
156         return (unsigned long)chunk->vm->addr +
157                 (pcpu_page_idx(cpu, page_idx) << PAGE_SHIFT);
158 }
159
160 static bool pcpu_chunk_page_occupied(struct pcpu_chunk *chunk,
161                                      int page_idx)
162 {
163         return *pcpu_chunk_pagep(chunk, 0, page_idx) != NULL;
164 }
165
166 /**
167  * pcpu_mem_alloc - allocate memory
168  * @size: bytes to allocate
169  *
170  * Allocate @size bytes.  If @size is smaller than PAGE_SIZE,
171  * kzalloc() is used; otherwise, vmalloc() is used.  The returned
172  * memory is always zeroed.
173  *
174  * RETURNS:
175  * Pointer to the allocated area on success, NULL on failure.
176  */
177 static void *pcpu_mem_alloc(size_t size)
178 {
179         if (size <= PAGE_SIZE)
180                 return kzalloc(size, GFP_KERNEL);
181         else {
182                 void *ptr = vmalloc(size);
183                 if (ptr)
184                         memset(ptr, 0, size);
185                 return ptr;
186         }
187 }
188
189 /**
190  * pcpu_mem_free - free memory
191  * @ptr: memory to free
192  * @size: size of the area
193  *
194  * Free @ptr.  @ptr should have been allocated using pcpu_mem_alloc().
195  */
196 static void pcpu_mem_free(void *ptr, size_t size)
197 {
198         if (size <= PAGE_SIZE)
199                 kfree(ptr);
200         else
201                 vfree(ptr);
202 }
203
204 /**
205  * pcpu_chunk_relocate - put chunk in the appropriate chunk slot
206  * @chunk: chunk of interest
207  * @oslot: the previous slot it was on
208  *
209  * This function is called after an allocation or free changed @chunk.
210  * New slot according to the changed state is determined and @chunk is
211  * moved to the slot.  Note that the reserved chunk is never put on
212  * chunk slots.
213  */
214 static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot)
215 {
216         int nslot = pcpu_chunk_slot(chunk);
217
218         if (chunk != pcpu_reserved_chunk && oslot != nslot) {
219                 if (oslot < nslot)
220                         list_move(&chunk->list, &pcpu_slot[nslot]);
221                 else
222                         list_move_tail(&chunk->list, &pcpu_slot[nslot]);
223         }
224 }
225
226 static struct rb_node **pcpu_chunk_rb_search(void *addr,
227                                              struct rb_node **parentp)
228 {
229         struct rb_node **p = &pcpu_addr_root.rb_node;
230         struct rb_node *parent = NULL;
231         struct pcpu_chunk *chunk;
232
233         while (*p) {
234                 parent = *p;
235                 chunk = rb_entry(parent, struct pcpu_chunk, rb_node);
236
237                 if (addr < chunk->vm->addr)
238                         p = &(*p)->rb_left;
239                 else if (addr > chunk->vm->addr)
240                         p = &(*p)->rb_right;
241                 else
242                         break;
243         }
244
245         if (parentp)
246                 *parentp = parent;
247         return p;
248 }
249
250 /**
251  * pcpu_chunk_addr_search - search for chunk containing specified address
252  * @addr: address to search for
253  *
254  * Look for chunk which might contain @addr.  More specifically, it
255  * searchs for the chunk with the highest start address which isn't
256  * beyond @addr.
257  *
258  * RETURNS:
259  * The address of the found chunk.
260  */
261 static struct pcpu_chunk *pcpu_chunk_addr_search(void *addr)
262 {
263         struct rb_node *n, *parent;
264         struct pcpu_chunk *chunk;
265
266         /* is it in the reserved chunk? */
267         if (pcpu_reserved_chunk) {
268                 void *start = pcpu_reserved_chunk->vm->addr;
269
270                 if (addr >= start && addr < start + pcpu_reserved_chunk_limit)
271                         return pcpu_reserved_chunk;
272         }
273
274         /* nah... search the regular ones */
275         n = *pcpu_chunk_rb_search(addr, &parent);
276         if (!n) {
277                 /* no exactly matching chunk, the parent is the closest */
278                 n = parent;
279                 BUG_ON(!n);
280         }
281         chunk = rb_entry(n, struct pcpu_chunk, rb_node);
282
283         if (addr < chunk->vm->addr) {
284                 /* the parent was the next one, look for the previous one */
285                 n = rb_prev(n);
286                 BUG_ON(!n);
287                 chunk = rb_entry(n, struct pcpu_chunk, rb_node);
288         }
289
290         return chunk;
291 }
292
293 /**
294  * pcpu_chunk_addr_insert - insert chunk into address rb tree
295  * @new: chunk to insert
296  *
297  * Insert @new into address rb tree.
298  */
299 static void pcpu_chunk_addr_insert(struct pcpu_chunk *new)
300 {
301         struct rb_node **p, *parent;
302
303         p = pcpu_chunk_rb_search(new->vm->addr, &parent);
304         BUG_ON(*p);
305         rb_link_node(&new->rb_node, parent, p);
306         rb_insert_color(&new->rb_node, &pcpu_addr_root);
307 }
308
309 /**
310  * pcpu_split_block - split a map block
311  * @chunk: chunk of interest
312  * @i: index of map block to split
313  * @head: head size in bytes (can be 0)
314  * @tail: tail size in bytes (can be 0)
315  *
316  * Split the @i'th map block into two or three blocks.  If @head is
317  * non-zero, @head bytes block is inserted before block @i moving it
318  * to @i+1 and reducing its size by @head bytes.
319  *
320  * If @tail is non-zero, the target block, which can be @i or @i+1
321  * depending on @head, is reduced by @tail bytes and @tail byte block
322  * is inserted after the target block.
323  *
324  * RETURNS:
325  * 0 on success, -errno on failure.
326  */
327 static int pcpu_split_block(struct pcpu_chunk *chunk, int i, int head, int tail)
328 {
329         int nr_extra = !!head + !!tail;
330         int target = chunk->map_used + nr_extra;
331
332         /* reallocation required? */
333         if (chunk->map_alloc < target) {
334                 int new_alloc;
335                 int *new;
336                 size_t size;
337
338                 new_alloc = PCPU_DFL_MAP_ALLOC;
339                 while (new_alloc < target)
340                         new_alloc *= 2;
341
342                 new = pcpu_mem_alloc(new_alloc * sizeof(new[0]));
343                 if (!new)
344                         return -ENOMEM;
345
346                 size = chunk->map_alloc * sizeof(chunk->map[0]);
347                 memcpy(new, chunk->map, size);
348
349                 /*
350                  * map_alloc < PCPU_DFL_MAP_ALLOC indicates that the
351                  * chunk is one of the first chunks and still using
352                  * static map.
353                  */
354                 if (chunk->map_alloc >= PCPU_DFL_MAP_ALLOC)
355                         pcpu_mem_free(chunk->map, size);
356
357                 chunk->map_alloc = new_alloc;
358                 chunk->map = new;
359         }
360
361         /* insert a new subblock */
362         memmove(&chunk->map[i + nr_extra], &chunk->map[i],
363                 sizeof(chunk->map[0]) * (chunk->map_used - i));
364         chunk->map_used += nr_extra;
365
366         if (head) {
367                 chunk->map[i + 1] = chunk->map[i] - head;
368                 chunk->map[i++] = head;
369         }
370         if (tail) {
371                 chunk->map[i++] -= tail;
372                 chunk->map[i] = tail;
373         }
374         return 0;
375 }
376
377 /**
378  * pcpu_alloc_area - allocate area from a pcpu_chunk
379  * @chunk: chunk of interest
380  * @size: wanted size in bytes
381  * @align: wanted align
382  *
383  * Try to allocate @size bytes area aligned at @align from @chunk.
384  * Note that this function only allocates the offset.  It doesn't
385  * populate or map the area.
386  *
387  * RETURNS:
388  * Allocated offset in @chunk on success, -errno on failure.
389  */
390 static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
391 {
392         int oslot = pcpu_chunk_slot(chunk);
393         int max_contig = 0;
394         int i, off;
395
396         for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++])) {
397                 bool is_last = i + 1 == chunk->map_used;
398                 int head, tail;
399
400                 /* extra for alignment requirement */
401                 head = ALIGN(off, align) - off;
402                 BUG_ON(i == 0 && head != 0);
403
404                 if (chunk->map[i] < 0)
405                         continue;
406                 if (chunk->map[i] < head + size) {
407                         max_contig = max(chunk->map[i], max_contig);
408                         continue;
409                 }
410
411                 /*
412                  * If head is small or the previous block is free,
413                  * merge'em.  Note that 'small' is defined as smaller
414                  * than sizeof(int), which is very small but isn't too
415                  * uncommon for percpu allocations.
416                  */
417                 if (head && (head < sizeof(int) || chunk->map[i - 1] > 0)) {
418                         if (chunk->map[i - 1] > 0)
419                                 chunk->map[i - 1] += head;
420                         else {
421                                 chunk->map[i - 1] -= head;
422                                 chunk->free_size -= head;
423                         }
424                         chunk->map[i] -= head;
425                         off += head;
426                         head = 0;
427                 }
428
429                 /* if tail is small, just keep it around */
430                 tail = chunk->map[i] - head - size;
431                 if (tail < sizeof(int))
432                         tail = 0;
433
434                 /* split if warranted */
435                 if (head || tail) {
436                         if (pcpu_split_block(chunk, i, head, tail))
437                                 return -ENOMEM;
438                         if (head) {
439                                 i++;
440                                 off += head;
441                                 max_contig = max(chunk->map[i - 1], max_contig);
442                         }
443                         if (tail)
444                                 max_contig = max(chunk->map[i + 1], max_contig);
445                 }
446
447                 /* update hint and mark allocated */
448                 if (is_last)
449                         chunk->contig_hint = max_contig; /* fully scanned */
450                 else
451                         chunk->contig_hint = max(chunk->contig_hint,
452                                                  max_contig);
453
454                 chunk->free_size -= chunk->map[i];
455                 chunk->map[i] = -chunk->map[i];
456
457                 pcpu_chunk_relocate(chunk, oslot);
458                 return off;
459         }
460
461         chunk->contig_hint = max_contig;        /* fully scanned */
462         pcpu_chunk_relocate(chunk, oslot);
463
464         /*
465          * Tell the upper layer that this chunk has no area left.
466          * Note that this is not an error condition but a notification
467          * to upper layer that it needs to look at other chunks.
468          * -ENOSPC is chosen as it isn't used in memory subsystem and
469          * matches the meaning in a way.
470          */
471         return -ENOSPC;
472 }
473
474 /**
475  * pcpu_free_area - free area to a pcpu_chunk
476  * @chunk: chunk of interest
477  * @freeme: offset of area to free
478  *
479  * Free area starting from @freeme to @chunk.  Note that this function
480  * only modifies the allocation map.  It doesn't depopulate or unmap
481  * the area.
482  */
483 static void pcpu_free_area(struct pcpu_chunk *chunk, int freeme)
484 {
485         int oslot = pcpu_chunk_slot(chunk);
486         int i, off;
487
488         for (i = 0, off = 0; i < chunk->map_used; off += abs(chunk->map[i++]))
489                 if (off == freeme)
490                         break;
491         BUG_ON(off != freeme);
492         BUG_ON(chunk->map[i] > 0);
493
494         chunk->map[i] = -chunk->map[i];
495         chunk->free_size += chunk->map[i];
496
497         /* merge with previous? */
498         if (i > 0 && chunk->map[i - 1] >= 0) {
499                 chunk->map[i - 1] += chunk->map[i];
500                 chunk->map_used--;
501                 memmove(&chunk->map[i], &chunk->map[i + 1],
502                         (chunk->map_used - i) * sizeof(chunk->map[0]));
503                 i--;
504         }
505         /* merge with next? */
506         if (i + 1 < chunk->map_used && chunk->map[i + 1] >= 0) {
507                 chunk->map[i] += chunk->map[i + 1];
508                 chunk->map_used--;
509                 memmove(&chunk->map[i + 1], &chunk->map[i + 2],
510                         (chunk->map_used - (i + 1)) * sizeof(chunk->map[0]));
511         }
512
513         chunk->contig_hint = max(chunk->map[i], chunk->contig_hint);
514         pcpu_chunk_relocate(chunk, oslot);
515 }
516
517 /**
518  * pcpu_unmap - unmap pages out of a pcpu_chunk
519  * @chunk: chunk of interest
520  * @page_start: page index of the first page to unmap
521  * @page_end: page index of the last page to unmap + 1
522  * @flush: whether to flush cache and tlb or not
523  *
524  * For each cpu, unmap pages [@page_start,@page_end) out of @chunk.
525  * If @flush is true, vcache is flushed before unmapping and tlb
526  * after.
527  */
528 static void pcpu_unmap(struct pcpu_chunk *chunk, int page_start, int page_end,
529                        bool flush)
530 {
531         unsigned int last = num_possible_cpus() - 1;
532         unsigned int cpu;
533
534         /* unmap must not be done on immutable chunk */
535         WARN_ON(chunk->immutable);
536
537         /*
538          * Each flushing trial can be very expensive, issue flush on
539          * the whole region at once rather than doing it for each cpu.
540          * This could be an overkill but is more scalable.
541          */
542         if (flush)
543                 flush_cache_vunmap(pcpu_chunk_addr(chunk, 0, page_start),
544                                    pcpu_chunk_addr(chunk, last, page_end));
545
546         for_each_possible_cpu(cpu)
547                 unmap_kernel_range_noflush(
548                                 pcpu_chunk_addr(chunk, cpu, page_start),
549                                 (page_end - page_start) << PAGE_SHIFT);
550
551         /* ditto as flush_cache_vunmap() */
552         if (flush)
553                 flush_tlb_kernel_range(pcpu_chunk_addr(chunk, 0, page_start),
554                                        pcpu_chunk_addr(chunk, last, page_end));
555 }
556
557 /**
558  * pcpu_depopulate_chunk - depopulate and unmap an area of a pcpu_chunk
559  * @chunk: chunk to depopulate
560  * @off: offset to the area to depopulate
561  * @size: size of the area to depopulate in bytes
562  * @flush: whether to flush cache and tlb or not
563  *
564  * For each cpu, depopulate and unmap pages [@page_start,@page_end)
565  * from @chunk.  If @flush is true, vcache is flushed before unmapping
566  * and tlb after.
567  */
568 static void pcpu_depopulate_chunk(struct pcpu_chunk *chunk, int off, int size,
569                                   bool flush)
570 {
571         int page_start = PFN_DOWN(off);
572         int page_end = PFN_UP(off + size);
573         int unmap_start = -1;
574         int uninitialized_var(unmap_end);
575         unsigned int cpu;
576         int i;
577
578         for (i = page_start; i < page_end; i++) {
579                 for_each_possible_cpu(cpu) {
580                         struct page **pagep = pcpu_chunk_pagep(chunk, cpu, i);
581
582                         if (!*pagep)
583                                 continue;
584
585                         __free_page(*pagep);
586
587                         /*
588                          * If it's partial depopulation, it might get
589                          * populated or depopulated again.  Mark the
590                          * page gone.
591                          */
592                         *pagep = NULL;
593
594                         unmap_start = unmap_start < 0 ? i : unmap_start;
595                         unmap_end = i + 1;
596                 }
597         }
598
599         if (unmap_start >= 0)
600                 pcpu_unmap(chunk, unmap_start, unmap_end, flush);
601 }
602
603 /**
604  * pcpu_map - map pages into a pcpu_chunk
605  * @chunk: chunk of interest
606  * @page_start: page index of the first page to map
607  * @page_end: page index of the last page to map + 1
608  *
609  * For each cpu, map pages [@page_start,@page_end) into @chunk.
610  * vcache is flushed afterwards.
611  */
612 static int pcpu_map(struct pcpu_chunk *chunk, int page_start, int page_end)
613 {
614         unsigned int last = num_possible_cpus() - 1;
615         unsigned int cpu;
616         int err;
617
618         /* map must not be done on immutable chunk */
619         WARN_ON(chunk->immutable);
620
621         for_each_possible_cpu(cpu) {
622                 err = map_kernel_range_noflush(
623                                 pcpu_chunk_addr(chunk, cpu, page_start),
624                                 (page_end - page_start) << PAGE_SHIFT,
625                                 PAGE_KERNEL,
626                                 pcpu_chunk_pagep(chunk, cpu, page_start));
627                 if (err < 0)
628                         return err;
629         }
630
631         /* flush at once, please read comments in pcpu_unmap() */
632         flush_cache_vmap(pcpu_chunk_addr(chunk, 0, page_start),
633                          pcpu_chunk_addr(chunk, last, page_end));
634         return 0;
635 }
636
637 /**
638  * pcpu_populate_chunk - populate and map an area of a pcpu_chunk
639  * @chunk: chunk of interest
640  * @off: offset to the area to populate
641  * @size: size of the area to populate in bytes
642  *
643  * For each cpu, populate and map pages [@page_start,@page_end) into
644  * @chunk.  The area is cleared on return.
645  */
646 static int pcpu_populate_chunk(struct pcpu_chunk *chunk, int off, int size)
647 {
648         const gfp_t alloc_mask = GFP_KERNEL | __GFP_HIGHMEM | __GFP_COLD;
649         int page_start = PFN_DOWN(off);
650         int page_end = PFN_UP(off + size);
651         int map_start = -1;
652         int uninitialized_var(map_end);
653         unsigned int cpu;
654         int i;
655
656         for (i = page_start; i < page_end; i++) {
657                 if (pcpu_chunk_page_occupied(chunk, i)) {
658                         if (map_start >= 0) {
659                                 if (pcpu_map(chunk, map_start, map_end))
660                                         goto err;
661                                 map_start = -1;
662                         }
663                         continue;
664                 }
665
666                 map_start = map_start < 0 ? i : map_start;
667                 map_end = i + 1;
668
669                 for_each_possible_cpu(cpu) {
670                         struct page **pagep = pcpu_chunk_pagep(chunk, cpu, i);
671
672                         *pagep = alloc_pages_node(cpu_to_node(cpu),
673                                                   alloc_mask, 0);
674                         if (!*pagep)
675                                 goto err;
676                 }
677         }
678
679         if (map_start >= 0 && pcpu_map(chunk, map_start, map_end))
680                 goto err;
681
682         for_each_possible_cpu(cpu)
683                 memset(chunk->vm->addr + cpu * pcpu_unit_size + off, 0,
684                        size);
685
686         return 0;
687 err:
688         /* likely under heavy memory pressure, give memory back */
689         pcpu_depopulate_chunk(chunk, off, size, true);
690         return -ENOMEM;
691 }
692
693 static void free_pcpu_chunk(struct pcpu_chunk *chunk)
694 {
695         if (!chunk)
696                 return;
697         if (chunk->vm)
698                 free_vm_area(chunk->vm);
699         pcpu_mem_free(chunk->map, chunk->map_alloc * sizeof(chunk->map[0]));
700         kfree(chunk);
701 }
702
703 static struct pcpu_chunk *alloc_pcpu_chunk(void)
704 {
705         struct pcpu_chunk *chunk;
706
707         chunk = kzalloc(pcpu_chunk_struct_size, GFP_KERNEL);
708         if (!chunk)
709                 return NULL;
710
711         chunk->map = pcpu_mem_alloc(PCPU_DFL_MAP_ALLOC * sizeof(chunk->map[0]));
712         chunk->map_alloc = PCPU_DFL_MAP_ALLOC;
713         chunk->map[chunk->map_used++] = pcpu_unit_size;
714         chunk->page = chunk->page_ar;
715
716         chunk->vm = get_vm_area(pcpu_chunk_size, GFP_KERNEL);
717         if (!chunk->vm) {
718                 free_pcpu_chunk(chunk);
719                 return NULL;
720         }
721
722         INIT_LIST_HEAD(&chunk->list);
723         chunk->free_size = pcpu_unit_size;
724         chunk->contig_hint = pcpu_unit_size;
725
726         return chunk;
727 }
728
729 /**
730  * pcpu_alloc - the percpu allocator
731  * @size: size of area to allocate in bytes
732  * @align: alignment of area (max PAGE_SIZE)
733  * @reserved: allocate from the reserved chunk if available
734  *
735  * Allocate percpu area of @size bytes aligned at @align.  Might
736  * sleep.  Might trigger writeouts.
737  *
738  * RETURNS:
739  * Percpu pointer to the allocated area on success, NULL on failure.
740  */
741 static void *pcpu_alloc(size_t size, size_t align, bool reserved)
742 {
743         void *ptr = NULL;
744         struct pcpu_chunk *chunk;
745         int slot, off;
746
747         if (unlikely(!size || size > PCPU_MIN_UNIT_SIZE || align > PAGE_SIZE)) {
748                 WARN(true, "illegal size (%zu) or align (%zu) for "
749                      "percpu allocation\n", size, align);
750                 return NULL;
751         }
752
753         mutex_lock(&pcpu_mutex);
754
755         /* serve reserved allocations from the reserved chunk if available */
756         if (reserved && pcpu_reserved_chunk) {
757                 chunk = pcpu_reserved_chunk;
758                 if (size > chunk->contig_hint)
759                         goto out_unlock;
760                 off = pcpu_alloc_area(chunk, size, align);
761                 if (off >= 0)
762                         goto area_found;
763                 goto out_unlock;
764         }
765
766         /* search through normal chunks */
767         for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) {
768                 list_for_each_entry(chunk, &pcpu_slot[slot], list) {
769                         if (size > chunk->contig_hint)
770                                 continue;
771                         off = pcpu_alloc_area(chunk, size, align);
772                         if (off >= 0)
773                                 goto area_found;
774                         if (off != -ENOSPC)
775                                 goto out_unlock;
776                 }
777         }
778
779         /* hmmm... no space left, create a new chunk */
780         chunk = alloc_pcpu_chunk();
781         if (!chunk)
782                 goto out_unlock;
783         pcpu_chunk_relocate(chunk, -1);
784         pcpu_chunk_addr_insert(chunk);
785
786         off = pcpu_alloc_area(chunk, size, align);
787         if (off < 0)
788                 goto out_unlock;
789
790 area_found:
791         /* populate, map and clear the area */
792         if (pcpu_populate_chunk(chunk, off, size)) {
793                 pcpu_free_area(chunk, off);
794                 goto out_unlock;
795         }
796
797         ptr = __addr_to_pcpu_ptr(chunk->vm->addr + off);
798 out_unlock:
799         mutex_unlock(&pcpu_mutex);
800         return ptr;
801 }
802
803 /**
804  * __alloc_percpu - allocate dynamic percpu area
805  * @size: size of area to allocate in bytes
806  * @align: alignment of area (max PAGE_SIZE)
807  *
808  * Allocate percpu area of @size bytes aligned at @align.  Might
809  * sleep.  Might trigger writeouts.
810  *
811  * RETURNS:
812  * Percpu pointer to the allocated area on success, NULL on failure.
813  */
814 void *__alloc_percpu(size_t size, size_t align)
815 {
816         return pcpu_alloc(size, align, false);
817 }
818 EXPORT_SYMBOL_GPL(__alloc_percpu);
819
820 /**
821  * __alloc_reserved_percpu - allocate reserved percpu area
822  * @size: size of area to allocate in bytes
823  * @align: alignment of area (max PAGE_SIZE)
824  *
825  * Allocate percpu area of @size bytes aligned at @align from reserved
826  * percpu area if arch has set it up; otherwise, allocation is served
827  * from the same dynamic area.  Might sleep.  Might trigger writeouts.
828  *
829  * RETURNS:
830  * Percpu pointer to the allocated area on success, NULL on failure.
831  */
832 void *__alloc_reserved_percpu(size_t size, size_t align)
833 {
834         return pcpu_alloc(size, align, true);
835 }
836
837 static void pcpu_kill_chunk(struct pcpu_chunk *chunk)
838 {
839         WARN_ON(chunk->immutable);
840         pcpu_depopulate_chunk(chunk, 0, pcpu_unit_size, false);
841         list_del(&chunk->list);
842         rb_erase(&chunk->rb_node, &pcpu_addr_root);
843         free_pcpu_chunk(chunk);
844 }
845
846 /**
847  * free_percpu - free percpu area
848  * @ptr: pointer to area to free
849  *
850  * Free percpu area @ptr.  Might sleep.
851  */
852 void free_percpu(void *ptr)
853 {
854         void *addr = __pcpu_ptr_to_addr(ptr);
855         struct pcpu_chunk *chunk;
856         int off;
857
858         if (!ptr)
859                 return;
860
861         mutex_lock(&pcpu_mutex);
862
863         chunk = pcpu_chunk_addr_search(addr);
864         off = addr - chunk->vm->addr;
865
866         pcpu_free_area(chunk, off);
867
868         /* the chunk became fully free, kill one if there are other free ones */
869         if (chunk->free_size == pcpu_unit_size) {
870                 struct pcpu_chunk *pos;
871
872                 list_for_each_entry(pos,
873                                     &pcpu_slot[pcpu_chunk_slot(chunk)], list)
874                         if (pos != chunk) {
875                                 pcpu_kill_chunk(pos);
876                                 break;
877                         }
878         }
879
880         mutex_unlock(&pcpu_mutex);
881 }
882 EXPORT_SYMBOL_GPL(free_percpu);
883
884 /**
885  * pcpu_setup_first_chunk - initialize the first percpu chunk
886  * @get_page_fn: callback to fetch page pointer
887  * @static_size: the size of static percpu area in bytes
888  * @reserved_size: the size of reserved percpu area in bytes
889  * @unit_size: unit size in bytes, must be multiple of PAGE_SIZE, -1 for auto
890  * @dyn_size: free size for dynamic allocation in bytes, -1 for auto
891  * @base_addr: mapped address, NULL for auto
892  * @populate_pte_fn: callback to allocate pagetable, NULL if unnecessary
893  *
894  * Initialize the first percpu chunk which contains the kernel static
895  * perpcu area.  This function is to be called from arch percpu area
896  * setup path.  The first two parameters are mandatory.  The rest are
897  * optional.
898  *
899  * @get_page_fn() should return pointer to percpu page given cpu
900  * number and page number.  It should at least return enough pages to
901  * cover the static area.  The returned pages for static area should
902  * have been initialized with valid data.  If @unit_size is specified,
903  * it can also return pages after the static area.  NULL return
904  * indicates end of pages for the cpu.  Note that @get_page_fn() must
905  * return the same number of pages for all cpus.
906  *
907  * @reserved_size, if non-zero, specifies the amount of bytes to
908  * reserve after the static area in the first chunk.  This reserves
909  * the first chunk such that it's available only through reserved
910  * percpu allocation.  This is primarily used to serve module percpu
911  * static areas on architectures where the addressing model has
912  * limited offset range for symbol relocations to guarantee module
913  * percpu symbols fall inside the relocatable range.
914  *
915  * @unit_size, if non-negative, specifies unit size and must be
916  * aligned to PAGE_SIZE and equal to or larger than @static_size +
917  * @reserved_size + @dyn_size.
918  *
919  * @dyn_size, if non-negative, limits the number of bytes available
920  * for dynamic allocation in the first chunk.  Specifying non-negative
921  * value make percpu leave alone the area beyond @static_size +
922  * @reserved_size + @dyn_size.
923  *
924  * Non-null @base_addr means that the caller already allocated virtual
925  * region for the first chunk and mapped it.  percpu must not mess
926  * with the chunk.  Note that @base_addr with 0 @unit_size or non-NULL
927  * @populate_pte_fn doesn't make any sense.
928  *
929  * @populate_pte_fn is used to populate the pagetable.  NULL means the
930  * caller already populated the pagetable.
931  *
932  * If the first chunk ends up with both reserved and dynamic areas, it
933  * is served by two chunks - one to serve the core static and reserved
934  * areas and the other for the dynamic area.  They share the same vm
935  * and page map but uses different area allocation map to stay away
936  * from each other.  The latter chunk is circulated in the chunk slots
937  * and available for dynamic allocation like any other chunks.
938  *
939  * RETURNS:
940  * The determined pcpu_unit_size which can be used to initialize
941  * percpu access.
942  */
943 size_t __init pcpu_setup_first_chunk(pcpu_get_page_fn_t get_page_fn,
944                                      size_t static_size, size_t reserved_size,
945                                      ssize_t unit_size, ssize_t dyn_size,
946                                      void *base_addr,
947                                      pcpu_populate_pte_fn_t populate_pte_fn)
948 {
949         static struct vm_struct first_vm;
950         static int smap[2], dmap[2];
951         struct pcpu_chunk *schunk, *dchunk = NULL;
952         unsigned int cpu;
953         int nr_pages;
954         int err, i;
955
956         /* santiy checks */
957         BUILD_BUG_ON(ARRAY_SIZE(smap) >= PCPU_DFL_MAP_ALLOC ||
958                      ARRAY_SIZE(dmap) >= PCPU_DFL_MAP_ALLOC);
959         BUG_ON(!static_size);
960         if (unit_size >= 0) {
961                 BUG_ON(unit_size < static_size + reserved_size +
962                                    (dyn_size >= 0 ? dyn_size : 0));
963                 BUG_ON(unit_size & ~PAGE_MASK);
964         } else {
965                 BUG_ON(dyn_size >= 0);
966                 BUG_ON(base_addr);
967         }
968         BUG_ON(base_addr && populate_pte_fn);
969
970         if (unit_size >= 0)
971                 pcpu_unit_pages = unit_size >> PAGE_SHIFT;
972         else
973                 pcpu_unit_pages = max_t(int, PCPU_MIN_UNIT_SIZE >> PAGE_SHIFT,
974                                         PFN_UP(static_size + reserved_size));
975
976         pcpu_unit_size = pcpu_unit_pages << PAGE_SHIFT;
977         pcpu_chunk_size = num_possible_cpus() * pcpu_unit_size;
978         pcpu_chunk_struct_size = sizeof(struct pcpu_chunk)
979                 + num_possible_cpus() * pcpu_unit_pages * sizeof(struct page *);
980
981         if (dyn_size < 0)
982                 dyn_size = pcpu_unit_size - static_size - reserved_size;
983
984         /*
985          * Allocate chunk slots.  The additional last slot is for
986          * empty chunks.
987          */
988         pcpu_nr_slots = __pcpu_size_to_slot(pcpu_unit_size) + 2;
989         pcpu_slot = alloc_bootmem(pcpu_nr_slots * sizeof(pcpu_slot[0]));
990         for (i = 0; i < pcpu_nr_slots; i++)
991                 INIT_LIST_HEAD(&pcpu_slot[i]);
992
993         /*
994          * Initialize static chunk.  If reserved_size is zero, the
995          * static chunk covers static area + dynamic allocation area
996          * in the first chunk.  If reserved_size is not zero, it
997          * covers static area + reserved area (mostly used for module
998          * static percpu allocation).
999          */
1000         schunk = alloc_bootmem(pcpu_chunk_struct_size);
1001         INIT_LIST_HEAD(&schunk->list);
1002         schunk->vm = &first_vm;
1003         schunk->map = smap;
1004         schunk->map_alloc = ARRAY_SIZE(smap);
1005         schunk->page = schunk->page_ar;
1006
1007         if (reserved_size) {
1008                 schunk->free_size = reserved_size;
1009                 pcpu_reserved_chunk = schunk;   /* not for dynamic alloc */
1010         } else {
1011                 schunk->free_size = dyn_size;
1012                 dyn_size = 0;                   /* dynamic area covered */
1013         }
1014         schunk->contig_hint = schunk->free_size;
1015
1016         schunk->map[schunk->map_used++] = -static_size;
1017         if (schunk->free_size)
1018                 schunk->map[schunk->map_used++] = schunk->free_size;
1019
1020         pcpu_reserved_chunk_limit = static_size + schunk->free_size;
1021
1022         /* init dynamic chunk if necessary */
1023         if (dyn_size) {
1024                 dchunk = alloc_bootmem(sizeof(struct pcpu_chunk));
1025                 INIT_LIST_HEAD(&dchunk->list);
1026                 dchunk->vm = &first_vm;
1027                 dchunk->map = dmap;
1028                 dchunk->map_alloc = ARRAY_SIZE(dmap);
1029                 dchunk->page = schunk->page_ar; /* share page map with schunk */
1030
1031                 dchunk->contig_hint = dchunk->free_size = dyn_size;
1032                 dchunk->map[dchunk->map_used++] = -pcpu_reserved_chunk_limit;
1033                 dchunk->map[dchunk->map_used++] = dchunk->free_size;
1034         }
1035
1036         /* allocate vm address */
1037         first_vm.flags = VM_ALLOC;
1038         first_vm.size = pcpu_chunk_size;
1039
1040         if (!base_addr)
1041                 vm_area_register_early(&first_vm, PAGE_SIZE);
1042         else {
1043                 /*
1044                  * Pages already mapped.  No need to remap into
1045                  * vmalloc area.  In this case the first chunks can't
1046                  * be mapped or unmapped by percpu and are marked
1047                  * immutable.
1048                  */
1049                 first_vm.addr = base_addr;
1050                 schunk->immutable = true;
1051                 if (dchunk)
1052                         dchunk->immutable = true;
1053         }
1054
1055         /* assign pages */
1056         nr_pages = -1;
1057         for_each_possible_cpu(cpu) {
1058                 for (i = 0; i < pcpu_unit_pages; i++) {
1059                         struct page *page = get_page_fn(cpu, i);
1060
1061                         if (!page)
1062                                 break;
1063                         *pcpu_chunk_pagep(schunk, cpu, i) = page;
1064                 }
1065
1066                 BUG_ON(i < PFN_UP(static_size));
1067
1068                 if (nr_pages < 0)
1069                         nr_pages = i;
1070                 else
1071                         BUG_ON(nr_pages != i);
1072         }
1073
1074         /* map them */
1075         if (populate_pte_fn) {
1076                 for_each_possible_cpu(cpu)
1077                         for (i = 0; i < nr_pages; i++)
1078                                 populate_pte_fn(pcpu_chunk_addr(schunk,
1079                                                                 cpu, i));
1080
1081                 err = pcpu_map(schunk, 0, nr_pages);
1082                 if (err)
1083                         panic("failed to setup static percpu area, err=%d\n",
1084                               err);
1085         }
1086
1087         /* link the first chunk in */
1088         if (!dchunk) {
1089                 pcpu_chunk_relocate(schunk, -1);
1090                 pcpu_chunk_addr_insert(schunk);
1091         } else {
1092                 pcpu_chunk_relocate(dchunk, -1);
1093                 pcpu_chunk_addr_insert(dchunk);
1094         }
1095
1096         /* we're done */
1097         pcpu_base_addr = (void *)pcpu_chunk_addr(schunk, 0, 0);
1098         return pcpu_unit_size;
1099 }