Merge branch 'topic/omap' into for-linus
[linux-2.6-block.git] / mm / mempool.c
1 /*
2  *  linux/mm/mempool.c
3  *
4  *  memory buffer pool support. Such pools are mostly used
5  *  for guaranteed, deadlock-free memory allocations during
6  *  extreme VM load.
7  *
8  *  started by Ingo Molnar, Copyright (C) 2001
9  *  debugging by David Rientjes, Copyright (C) 2015
10  */
11
12 #include <linux/mm.h>
13 #include <linux/slab.h>
14 #include <linux/highmem.h>
15 #include <linux/kasan.h>
16 #include <linux/kmemleak.h>
17 #include <linux/export.h>
18 #include <linux/mempool.h>
19 #include <linux/blkdev.h>
20 #include <linux/writeback.h>
21 #include "slab.h"
22
23 #if defined(CONFIG_DEBUG_SLAB) || defined(CONFIG_SLUB_DEBUG_ON)
24 static void poison_error(mempool_t *pool, void *element, size_t size,
25                          size_t byte)
26 {
27         const int nr = pool->curr_nr;
28         const int start = max_t(int, byte - (BITS_PER_LONG / 8), 0);
29         const int end = min_t(int, byte + (BITS_PER_LONG / 8), size);
30         int i;
31
32         pr_err("BUG: mempool element poison mismatch\n");
33         pr_err("Mempool %p size %zu\n", pool, size);
34         pr_err(" nr=%d @ %p: %s0x", nr, element, start > 0 ? "... " : "");
35         for (i = start; i < end; i++)
36                 pr_cont("%x ", *(u8 *)(element + i));
37         pr_cont("%s\n", end < size ? "..." : "");
38         dump_stack();
39 }
40
41 static void __check_element(mempool_t *pool, void *element, size_t size)
42 {
43         u8 *obj = element;
44         size_t i;
45
46         for (i = 0; i < size; i++) {
47                 u8 exp = (i < size - 1) ? POISON_FREE : POISON_END;
48
49                 if (obj[i] != exp) {
50                         poison_error(pool, element, size, i);
51                         return;
52                 }
53         }
54         memset(obj, POISON_INUSE, size);
55 }
56
57 static void check_element(mempool_t *pool, void *element)
58 {
59         /* Mempools backed by slab allocator */
60         if (pool->free == mempool_free_slab || pool->free == mempool_kfree)
61                 __check_element(pool, element, ksize(element));
62
63         /* Mempools backed by page allocator */
64         if (pool->free == mempool_free_pages) {
65                 int order = (int)(long)pool->pool_data;
66                 void *addr = kmap_atomic((struct page *)element);
67
68                 __check_element(pool, addr, 1UL << (PAGE_SHIFT + order));
69                 kunmap_atomic(addr);
70         }
71 }
72
73 static void __poison_element(void *element, size_t size)
74 {
75         u8 *obj = element;
76
77         memset(obj, POISON_FREE, size - 1);
78         obj[size - 1] = POISON_END;
79 }
80
81 static void poison_element(mempool_t *pool, void *element)
82 {
83         /* Mempools backed by slab allocator */
84         if (pool->alloc == mempool_alloc_slab || pool->alloc == mempool_kmalloc)
85                 __poison_element(element, ksize(element));
86
87         /* Mempools backed by page allocator */
88         if (pool->alloc == mempool_alloc_pages) {
89                 int order = (int)(long)pool->pool_data;
90                 void *addr = kmap_atomic((struct page *)element);
91
92                 __poison_element(addr, 1UL << (PAGE_SHIFT + order));
93                 kunmap_atomic(addr);
94         }
95 }
96 #else /* CONFIG_DEBUG_SLAB || CONFIG_SLUB_DEBUG_ON */
97 static inline void check_element(mempool_t *pool, void *element)
98 {
99 }
100 static inline void poison_element(mempool_t *pool, void *element)
101 {
102 }
103 #endif /* CONFIG_DEBUG_SLAB || CONFIG_SLUB_DEBUG_ON */
104
105 static void kasan_poison_element(mempool_t *pool, void *element)
106 {
107         if (pool->alloc == mempool_alloc_slab)
108                 kasan_slab_free(pool->pool_data, element);
109         if (pool->alloc == mempool_kmalloc)
110                 kasan_kfree(element);
111         if (pool->alloc == mempool_alloc_pages)
112                 kasan_free_pages(element, (unsigned long)pool->pool_data);
113 }
114
115 static void kasan_unpoison_element(mempool_t *pool, void *element)
116 {
117         if (pool->alloc == mempool_alloc_slab)
118                 kasan_slab_alloc(pool->pool_data, element);
119         if (pool->alloc == mempool_kmalloc)
120                 kasan_krealloc(element, (size_t)pool->pool_data);
121         if (pool->alloc == mempool_alloc_pages)
122                 kasan_alloc_pages(element, (unsigned long)pool->pool_data);
123 }
124
125 static void add_element(mempool_t *pool, void *element)
126 {
127         BUG_ON(pool->curr_nr >= pool->min_nr);
128         poison_element(pool, element);
129         kasan_poison_element(pool, element);
130         pool->elements[pool->curr_nr++] = element;
131 }
132
133 static void *remove_element(mempool_t *pool)
134 {
135         void *element = pool->elements[--pool->curr_nr];
136
137         BUG_ON(pool->curr_nr < 0);
138         check_element(pool, element);
139         kasan_unpoison_element(pool, element);
140         return element;
141 }
142
143 /**
144  * mempool_destroy - deallocate a memory pool
145  * @pool:      pointer to the memory pool which was allocated via
146  *             mempool_create().
147  *
148  * Free all reserved elements in @pool and @pool itself.  This function
149  * only sleeps if the free_fn() function sleeps.
150  */
151 void mempool_destroy(mempool_t *pool)
152 {
153         while (pool->curr_nr) {
154                 void *element = remove_element(pool);
155                 pool->free(element, pool->pool_data);
156         }
157         kfree(pool->elements);
158         kfree(pool);
159 }
160 EXPORT_SYMBOL(mempool_destroy);
161
162 /**
163  * mempool_create - create a memory pool
164  * @min_nr:    the minimum number of elements guaranteed to be
165  *             allocated for this pool.
166  * @alloc_fn:  user-defined element-allocation function.
167  * @free_fn:   user-defined element-freeing function.
168  * @pool_data: optional private data available to the user-defined functions.
169  *
170  * this function creates and allocates a guaranteed size, preallocated
171  * memory pool. The pool can be used from the mempool_alloc() and mempool_free()
172  * functions. This function might sleep. Both the alloc_fn() and the free_fn()
173  * functions might sleep - as long as the mempool_alloc() function is not called
174  * from IRQ contexts.
175  */
176 mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
177                                 mempool_free_t *free_fn, void *pool_data)
178 {
179         return mempool_create_node(min_nr,alloc_fn,free_fn, pool_data,
180                                    GFP_KERNEL, NUMA_NO_NODE);
181 }
182 EXPORT_SYMBOL(mempool_create);
183
184 mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
185                                mempool_free_t *free_fn, void *pool_data,
186                                gfp_t gfp_mask, int node_id)
187 {
188         mempool_t *pool;
189         pool = kzalloc_node(sizeof(*pool), gfp_mask, node_id);
190         if (!pool)
191                 return NULL;
192         pool->elements = kmalloc_node(min_nr * sizeof(void *),
193                                       gfp_mask, node_id);
194         if (!pool->elements) {
195                 kfree(pool);
196                 return NULL;
197         }
198         spin_lock_init(&pool->lock);
199         pool->min_nr = min_nr;
200         pool->pool_data = pool_data;
201         init_waitqueue_head(&pool->wait);
202         pool->alloc = alloc_fn;
203         pool->free = free_fn;
204
205         /*
206          * First pre-allocate the guaranteed number of buffers.
207          */
208         while (pool->curr_nr < pool->min_nr) {
209                 void *element;
210
211                 element = pool->alloc(gfp_mask, pool->pool_data);
212                 if (unlikely(!element)) {
213                         mempool_destroy(pool);
214                         return NULL;
215                 }
216                 add_element(pool, element);
217         }
218         return pool;
219 }
220 EXPORT_SYMBOL(mempool_create_node);
221
222 /**
223  * mempool_resize - resize an existing memory pool
224  * @pool:       pointer to the memory pool which was allocated via
225  *              mempool_create().
226  * @new_min_nr: the new minimum number of elements guaranteed to be
227  *              allocated for this pool.
228  *
229  * This function shrinks/grows the pool. In the case of growing,
230  * it cannot be guaranteed that the pool will be grown to the new
231  * size immediately, but new mempool_free() calls will refill it.
232  * This function may sleep.
233  *
234  * Note, the caller must guarantee that no mempool_destroy is called
235  * while this function is running. mempool_alloc() & mempool_free()
236  * might be called (eg. from IRQ contexts) while this function executes.
237  */
238 int mempool_resize(mempool_t *pool, int new_min_nr)
239 {
240         void *element;
241         void **new_elements;
242         unsigned long flags;
243
244         BUG_ON(new_min_nr <= 0);
245         might_sleep();
246
247         spin_lock_irqsave(&pool->lock, flags);
248         if (new_min_nr <= pool->min_nr) {
249                 while (new_min_nr < pool->curr_nr) {
250                         element = remove_element(pool);
251                         spin_unlock_irqrestore(&pool->lock, flags);
252                         pool->free(element, pool->pool_data);
253                         spin_lock_irqsave(&pool->lock, flags);
254                 }
255                 pool->min_nr = new_min_nr;
256                 goto out_unlock;
257         }
258         spin_unlock_irqrestore(&pool->lock, flags);
259
260         /* Grow the pool */
261         new_elements = kmalloc_array(new_min_nr, sizeof(*new_elements),
262                                      GFP_KERNEL);
263         if (!new_elements)
264                 return -ENOMEM;
265
266         spin_lock_irqsave(&pool->lock, flags);
267         if (unlikely(new_min_nr <= pool->min_nr)) {
268                 /* Raced, other resize will do our work */
269                 spin_unlock_irqrestore(&pool->lock, flags);
270                 kfree(new_elements);
271                 goto out;
272         }
273         memcpy(new_elements, pool->elements,
274                         pool->curr_nr * sizeof(*new_elements));
275         kfree(pool->elements);
276         pool->elements = new_elements;
277         pool->min_nr = new_min_nr;
278
279         while (pool->curr_nr < pool->min_nr) {
280                 spin_unlock_irqrestore(&pool->lock, flags);
281                 element = pool->alloc(GFP_KERNEL, pool->pool_data);
282                 if (!element)
283                         goto out;
284                 spin_lock_irqsave(&pool->lock, flags);
285                 if (pool->curr_nr < pool->min_nr) {
286                         add_element(pool, element);
287                 } else {
288                         spin_unlock_irqrestore(&pool->lock, flags);
289                         pool->free(element, pool->pool_data);   /* Raced */
290                         goto out;
291                 }
292         }
293 out_unlock:
294         spin_unlock_irqrestore(&pool->lock, flags);
295 out:
296         return 0;
297 }
298 EXPORT_SYMBOL(mempool_resize);
299
300 /**
301  * mempool_alloc - allocate an element from a specific memory pool
302  * @pool:      pointer to the memory pool which was allocated via
303  *             mempool_create().
304  * @gfp_mask:  the usual allocation bitmask.
305  *
306  * this function only sleeps if the alloc_fn() function sleeps or
307  * returns NULL. Note that due to preallocation, this function
308  * *never* fails when called from process contexts. (it might
309  * fail if called from an IRQ context.)
310  * Note: using __GFP_ZERO is not supported.
311  */
312 void * mempool_alloc(mempool_t *pool, gfp_t gfp_mask)
313 {
314         void *element;
315         unsigned long flags;
316         wait_queue_t wait;
317         gfp_t gfp_temp;
318
319         VM_WARN_ON_ONCE(gfp_mask & __GFP_ZERO);
320         might_sleep_if(gfp_mask & __GFP_WAIT);
321
322         gfp_mask |= __GFP_NOMEMALLOC;   /* don't allocate emergency reserves */
323         gfp_mask |= __GFP_NORETRY;      /* don't loop in __alloc_pages */
324         gfp_mask |= __GFP_NOWARN;       /* failures are OK */
325
326         gfp_temp = gfp_mask & ~(__GFP_WAIT|__GFP_IO);
327
328 repeat_alloc:
329
330         element = pool->alloc(gfp_temp, pool->pool_data);
331         if (likely(element != NULL))
332                 return element;
333
334         spin_lock_irqsave(&pool->lock, flags);
335         if (likely(pool->curr_nr)) {
336                 element = remove_element(pool);
337                 spin_unlock_irqrestore(&pool->lock, flags);
338                 /* paired with rmb in mempool_free(), read comment there */
339                 smp_wmb();
340                 /*
341                  * Update the allocation stack trace as this is more useful
342                  * for debugging.
343                  */
344                 kmemleak_update_trace(element);
345                 return element;
346         }
347
348         /*
349          * We use gfp mask w/o __GFP_WAIT or IO for the first round.  If
350          * alloc failed with that and @pool was empty, retry immediately.
351          */
352         if (gfp_temp != gfp_mask) {
353                 spin_unlock_irqrestore(&pool->lock, flags);
354                 gfp_temp = gfp_mask;
355                 goto repeat_alloc;
356         }
357
358         /* We must not sleep if !__GFP_WAIT */
359         if (!(gfp_mask & __GFP_WAIT)) {
360                 spin_unlock_irqrestore(&pool->lock, flags);
361                 return NULL;
362         }
363
364         /* Let's wait for someone else to return an element to @pool */
365         init_wait(&wait);
366         prepare_to_wait(&pool->wait, &wait, TASK_UNINTERRUPTIBLE);
367
368         spin_unlock_irqrestore(&pool->lock, flags);
369
370         /*
371          * FIXME: this should be io_schedule().  The timeout is there as a
372          * workaround for some DM problems in 2.6.18.
373          */
374         io_schedule_timeout(5*HZ);
375
376         finish_wait(&pool->wait, &wait);
377         goto repeat_alloc;
378 }
379 EXPORT_SYMBOL(mempool_alloc);
380
381 /**
382  * mempool_free - return an element to the pool.
383  * @element:   pool element pointer.
384  * @pool:      pointer to the memory pool which was allocated via
385  *             mempool_create().
386  *
387  * this function only sleeps if the free_fn() function sleeps.
388  */
389 void mempool_free(void *element, mempool_t *pool)
390 {
391         unsigned long flags;
392
393         if (unlikely(element == NULL))
394                 return;
395
396         /*
397          * Paired with the wmb in mempool_alloc().  The preceding read is
398          * for @element and the following @pool->curr_nr.  This ensures
399          * that the visible value of @pool->curr_nr is from after the
400          * allocation of @element.  This is necessary for fringe cases
401          * where @element was passed to this task without going through
402          * barriers.
403          *
404          * For example, assume @p is %NULL at the beginning and one task
405          * performs "p = mempool_alloc(...);" while another task is doing
406          * "while (!p) cpu_relax(); mempool_free(p, ...);".  This function
407          * may end up using curr_nr value which is from before allocation
408          * of @p without the following rmb.
409          */
410         smp_rmb();
411
412         /*
413          * For correctness, we need a test which is guaranteed to trigger
414          * if curr_nr + #allocated == min_nr.  Testing curr_nr < min_nr
415          * without locking achieves that and refilling as soon as possible
416          * is desirable.
417          *
418          * Because curr_nr visible here is always a value after the
419          * allocation of @element, any task which decremented curr_nr below
420          * min_nr is guaranteed to see curr_nr < min_nr unless curr_nr gets
421          * incremented to min_nr afterwards.  If curr_nr gets incremented
422          * to min_nr after the allocation of @element, the elements
423          * allocated after that are subject to the same guarantee.
424          *
425          * Waiters happen iff curr_nr is 0 and the above guarantee also
426          * ensures that there will be frees which return elements to the
427          * pool waking up the waiters.
428          */
429         if (unlikely(pool->curr_nr < pool->min_nr)) {
430                 spin_lock_irqsave(&pool->lock, flags);
431                 if (likely(pool->curr_nr < pool->min_nr)) {
432                         add_element(pool, element);
433                         spin_unlock_irqrestore(&pool->lock, flags);
434                         wake_up(&pool->wait);
435                         return;
436                 }
437                 spin_unlock_irqrestore(&pool->lock, flags);
438         }
439         pool->free(element, pool->pool_data);
440 }
441 EXPORT_SYMBOL(mempool_free);
442
443 /*
444  * A commonly used alloc and free fn.
445  */
446 void *mempool_alloc_slab(gfp_t gfp_mask, void *pool_data)
447 {
448         struct kmem_cache *mem = pool_data;
449         VM_BUG_ON(mem->ctor);
450         return kmem_cache_alloc(mem, gfp_mask);
451 }
452 EXPORT_SYMBOL(mempool_alloc_slab);
453
454 void mempool_free_slab(void *element, void *pool_data)
455 {
456         struct kmem_cache *mem = pool_data;
457         kmem_cache_free(mem, element);
458 }
459 EXPORT_SYMBOL(mempool_free_slab);
460
461 /*
462  * A commonly used alloc and free fn that kmalloc/kfrees the amount of memory
463  * specified by pool_data
464  */
465 void *mempool_kmalloc(gfp_t gfp_mask, void *pool_data)
466 {
467         size_t size = (size_t)pool_data;
468         return kmalloc(size, gfp_mask);
469 }
470 EXPORT_SYMBOL(mempool_kmalloc);
471
472 void mempool_kfree(void *element, void *pool_data)
473 {
474         kfree(element);
475 }
476 EXPORT_SYMBOL(mempool_kfree);
477
478 /*
479  * A simple mempool-backed page allocator that allocates pages
480  * of the order specified by pool_data.
481  */
482 void *mempool_alloc_pages(gfp_t gfp_mask, void *pool_data)
483 {
484         int order = (int)(long)pool_data;
485         return alloc_pages(gfp_mask, order);
486 }
487 EXPORT_SYMBOL(mempool_alloc_pages);
488
489 void mempool_free_pages(void *element, void *pool_data)
490 {
491         int order = (int)(long)pool_data;
492         __free_pages(element, order);
493 }
494 EXPORT_SYMBOL(mempool_free_pages);