Root/lib/genalloc.c

1/*
2 * Basic general purpose allocator for managing special purpose
3 * memory, for example, memory that is not managed by the regular
4 * kmalloc/kfree interface. Uses for this includes on-device special
5 * memory, uncached memory etc.
6 *
7 * It is safe to use the allocator in NMI handlers and other special
8 * unblockable contexts that could otherwise deadlock on locks. This
9 * is implemented by using atomic operations and retries on any
10 * conflicts. The disadvantage is that there may be livelocks in
11 * extreme cases. For better scalability, one allocator can be used
12 * for each CPU.
13 *
14 * The lockless operation only works if there is enough memory
15 * available. If new memory is added to the pool a lock has to be
16 * still taken. So any user relying on locklessness has to ensure
17 * that sufficient memory is preallocated.
18 *
19 * The basic atomic operation of this allocator is cmpxchg on long.
20 * On architectures that don't have NMI-safe cmpxchg implementation,
21 * the allocator can NOT be used in NMI handler. So code uses the
22 * allocator in NMI handler should depend on
23 * CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG.
24 *
25 * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
26 *
27 * This source code is licensed under the GNU General Public License,
28 * Version 2. See the file COPYING for more details.
29 */
30
31#include <linux/slab.h>
32#include <linux/export.h>
33#include <linux/bitmap.h>
34#include <linux/rculist.h>
35#include <linux/interrupt.h>
36#include <linux/genalloc.h>
37#include <linux/of_address.h>
38#include <linux/of_device.h>
39
40static inline size_t chunk_size(const struct gen_pool_chunk *chunk)
41{
42    return chunk->end_addr - chunk->start_addr + 1;
43}
44
45static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set)
46{
47    unsigned long val, nval;
48
49    nval = *addr;
50    do {
51        val = nval;
52        if (val & mask_to_set)
53            return -EBUSY;
54        cpu_relax();
55    } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val);
56
57    return 0;
58}
59
60static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear)
61{
62    unsigned long val, nval;
63
64    nval = *addr;
65    do {
66        val = nval;
67        if ((val & mask_to_clear) != mask_to_clear)
68            return -EBUSY;
69        cpu_relax();
70    } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val);
71
72    return 0;
73}
74
75/*
76 * bitmap_set_ll - set the specified number of bits at the specified position
77 * @map: pointer to a bitmap
78 * @start: a bit position in @map
79 * @nr: number of bits to set
80 *
81 * Set @nr bits start from @start in @map lock-lessly. Several users
82 * can set/clear the same bitmap simultaneously without lock. If two
83 * users set the same bit, one user will return remain bits, otherwise
84 * return 0.
85 */
86static int bitmap_set_ll(unsigned long *map, int start, int nr)
87{
88    unsigned long *p = map + BIT_WORD(start);
89    const int size = start + nr;
90    int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
91    unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
92
93    while (nr - bits_to_set >= 0) {
94        if (set_bits_ll(p, mask_to_set))
95            return nr;
96        nr -= bits_to_set;
97        bits_to_set = BITS_PER_LONG;
98        mask_to_set = ~0UL;
99        p++;
100    }
101    if (nr) {
102        mask_to_set &= BITMAP_LAST_WORD_MASK(size);
103        if (set_bits_ll(p, mask_to_set))
104            return nr;
105    }
106
107    return 0;
108}
109
110/*
111 * bitmap_clear_ll - clear the specified number of bits at the specified position
112 * @map: pointer to a bitmap
113 * @start: a bit position in @map
114 * @nr: number of bits to set
115 *
116 * Clear @nr bits start from @start in @map lock-lessly. Several users
117 * can set/clear the same bitmap simultaneously without lock. If two
118 * users clear the same bit, one user will return remain bits,
119 * otherwise return 0.
120 */
121static int bitmap_clear_ll(unsigned long *map, int start, int nr)
122{
123    unsigned long *p = map + BIT_WORD(start);
124    const int size = start + nr;
125    int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
126    unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
127
128    while (nr - bits_to_clear >= 0) {
129        if (clear_bits_ll(p, mask_to_clear))
130            return nr;
131        nr -= bits_to_clear;
132        bits_to_clear = BITS_PER_LONG;
133        mask_to_clear = ~0UL;
134        p++;
135    }
136    if (nr) {
137        mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
138        if (clear_bits_ll(p, mask_to_clear))
139            return nr;
140    }
141
142    return 0;
143}
144
145/**
146 * gen_pool_create - create a new special memory pool
147 * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents
148 * @nid: node id of the node the pool structure should be allocated on, or -1
149 *
150 * Create a new special memory pool that can be used to manage special purpose
151 * memory not managed by the regular kmalloc/kfree interface.
152 */
153struct gen_pool *gen_pool_create(int min_alloc_order, int nid)
154{
155    struct gen_pool *pool;
156
157    pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid);
158    if (pool != NULL) {
159        spin_lock_init(&pool->lock);
160        INIT_LIST_HEAD(&pool->chunks);
161        pool->min_alloc_order = min_alloc_order;
162        pool->algo = gen_pool_first_fit;
163        pool->data = NULL;
164    }
165    return pool;
166}
167EXPORT_SYMBOL(gen_pool_create);
168
169/**
170 * gen_pool_add_virt - add a new chunk of special memory to the pool
171 * @pool: pool to add new memory chunk to
172 * @virt: virtual starting address of memory chunk to add to pool
173 * @phys: physical starting address of memory chunk to add to pool
174 * @size: size in bytes of the memory chunk to add to pool
175 * @nid: node id of the node the chunk structure and bitmap should be
176 * allocated on, or -1
177 *
178 * Add a new chunk of special memory to the specified pool.
179 *
180 * Returns 0 on success or a -ve errno on failure.
181 */
182int gen_pool_add_virt(struct gen_pool *pool, unsigned long virt, phys_addr_t phys,
183         size_t size, int nid)
184{
185    struct gen_pool_chunk *chunk;
186    int nbits = size >> pool->min_alloc_order;
187    int nbytes = sizeof(struct gen_pool_chunk) +
188                BITS_TO_LONGS(nbits) * sizeof(long);
189
190    chunk = kzalloc_node(nbytes, GFP_KERNEL, nid);
191    if (unlikely(chunk == NULL))
192        return -ENOMEM;
193
194    chunk->phys_addr = phys;
195    chunk->start_addr = virt;
196    chunk->end_addr = virt + size - 1;
197    atomic_set(&chunk->avail, size);
198
199    spin_lock(&pool->lock);
200    list_add_rcu(&chunk->next_chunk, &pool->chunks);
201    spin_unlock(&pool->lock);
202
203    return 0;
204}
205EXPORT_SYMBOL(gen_pool_add_virt);
206
207/**
208 * gen_pool_virt_to_phys - return the physical address of memory
209 * @pool: pool to allocate from
210 * @addr: starting address of memory
211 *
212 * Returns the physical address on success, or -1 on error.
213 */
214phys_addr_t gen_pool_virt_to_phys(struct gen_pool *pool, unsigned long addr)
215{
216    struct gen_pool_chunk *chunk;
217    phys_addr_t paddr = -1;
218
219    rcu_read_lock();
220    list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
221        if (addr >= chunk->start_addr && addr <= chunk->end_addr) {
222            paddr = chunk->phys_addr + (addr - chunk->start_addr);
223            break;
224        }
225    }
226    rcu_read_unlock();
227
228    return paddr;
229}
230EXPORT_SYMBOL(gen_pool_virt_to_phys);
231
232/**
233 * gen_pool_destroy - destroy a special memory pool
234 * @pool: pool to destroy
235 *
236 * Destroy the specified special memory pool. Verifies that there are no
237 * outstanding allocations.
238 */
239void gen_pool_destroy(struct gen_pool *pool)
240{
241    struct list_head *_chunk, *_next_chunk;
242    struct gen_pool_chunk *chunk;
243    int order = pool->min_alloc_order;
244    int bit, end_bit;
245
246    list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {
247        chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk);
248        list_del(&chunk->next_chunk);
249
250        end_bit = chunk_size(chunk) >> order;
251        bit = find_next_bit(chunk->bits, end_bit, 0);
252        BUG_ON(bit < end_bit);
253
254        kfree(chunk);
255    }
256    kfree(pool);
257    return;
258}
259EXPORT_SYMBOL(gen_pool_destroy);
260
261/**
262 * gen_pool_alloc - allocate special memory from the pool
263 * @pool: pool to allocate from
264 * @size: number of bytes to allocate from the pool
265 *
266 * Allocate the requested number of bytes from the specified pool.
267 * Uses the pool allocation function (with first-fit algorithm by default).
268 * Can not be used in NMI handler on architectures without
269 * NMI-safe cmpxchg implementation.
270 */
271unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
272{
273    struct gen_pool_chunk *chunk;
274    unsigned long addr = 0;
275    int order = pool->min_alloc_order;
276    int nbits, start_bit = 0, end_bit, remain;
277
278#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
279    BUG_ON(in_nmi());
280#endif
281
282    if (size == 0)
283        return 0;
284
285    nbits = (size + (1UL << order) - 1) >> order;
286    rcu_read_lock();
287    list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
288        if (size > atomic_read(&chunk->avail))
289            continue;
290
291        end_bit = chunk_size(chunk) >> order;
292retry:
293        start_bit = pool->algo(chunk->bits, end_bit, start_bit, nbits,
294                pool->data);
295        if (start_bit >= end_bit)
296            continue;
297        remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
298        if (remain) {
299            remain = bitmap_clear_ll(chunk->bits, start_bit,
300                         nbits - remain);
301            BUG_ON(remain);
302            goto retry;
303        }
304
305        addr = chunk->start_addr + ((unsigned long)start_bit << order);
306        size = nbits << order;
307        atomic_sub(size, &chunk->avail);
308        break;
309    }
310    rcu_read_unlock();
311    return addr;
312}
313EXPORT_SYMBOL(gen_pool_alloc);
314
315/**
316 * gen_pool_dma_alloc - allocate special memory from the pool for DMA usage
317 * @pool: pool to allocate from
318 * @size: number of bytes to allocate from the pool
319 * @dma: dma-view physical address
320 *
321 * Allocate the requested number of bytes from the specified pool.
322 * Uses the pool allocation function (with first-fit algorithm by default).
323 * Can not be used in NMI handler on architectures without
324 * NMI-safe cmpxchg implementation.
325 */
326void *gen_pool_dma_alloc(struct gen_pool *pool, size_t size, dma_addr_t *dma)
327{
328    unsigned long vaddr;
329
330    if (!pool)
331        return NULL;
332
333    vaddr = gen_pool_alloc(pool, size);
334    if (!vaddr)
335        return NULL;
336
337    *dma = gen_pool_virt_to_phys(pool, vaddr);
338
339    return (void *)vaddr;
340}
341EXPORT_SYMBOL(gen_pool_dma_alloc);
342
343/**
344 * gen_pool_free - free allocated special memory back to the pool
345 * @pool: pool to free to
346 * @addr: starting address of memory to free back to pool
347 * @size: size in bytes of memory to free
348 *
349 * Free previously allocated special memory back to the specified
350 * pool. Can not be used in NMI handler on architectures without
351 * NMI-safe cmpxchg implementation.
352 */
353void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size)
354{
355    struct gen_pool_chunk *chunk;
356    int order = pool->min_alloc_order;
357    int start_bit, nbits, remain;
358
359#ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
360    BUG_ON(in_nmi());
361#endif
362
363    nbits = (size + (1UL << order) - 1) >> order;
364    rcu_read_lock();
365    list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {
366        if (addr >= chunk->start_addr && addr <= chunk->end_addr) {
367            BUG_ON(addr + size - 1 > chunk->end_addr);
368            start_bit = (addr - chunk->start_addr) >> order;
369            remain = bitmap_clear_ll(chunk->bits, start_bit, nbits);
370            BUG_ON(remain);
371            size = nbits << order;
372            atomic_add(size, &chunk->avail);
373            rcu_read_unlock();
374            return;
375        }
376    }
377    rcu_read_unlock();
378    BUG();
379}
380EXPORT_SYMBOL(gen_pool_free);
381
382/**
383 * gen_pool_for_each_chunk - call func for every chunk of generic memory pool
384 * @pool: the generic memory pool
385 * @func: func to call
386 * @data: additional data used by @func
387 *
388 * Call @func for every chunk of generic memory pool. The @func is
389 * called with rcu_read_lock held.
390 */
391void gen_pool_for_each_chunk(struct gen_pool *pool,
392    void (*func)(struct gen_pool *pool, struct gen_pool_chunk *chunk, void *data),
393    void *data)
394{
395    struct gen_pool_chunk *chunk;
396
397    rcu_read_lock();
398    list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk)
399        func(pool, chunk, data);
400    rcu_read_unlock();
401}
402EXPORT_SYMBOL(gen_pool_for_each_chunk);
403
404/**
405 * gen_pool_avail - get available free space of the pool
406 * @pool: pool to get available free space
407 *
408 * Return available free space of the specified pool.
409 */
410size_t gen_pool_avail(struct gen_pool *pool)
411{
412    struct gen_pool_chunk *chunk;
413    size_t avail = 0;
414
415    rcu_read_lock();
416    list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
417        avail += atomic_read(&chunk->avail);
418    rcu_read_unlock();
419    return avail;
420}
421EXPORT_SYMBOL_GPL(gen_pool_avail);
422
423/**
424 * gen_pool_size - get size in bytes of memory managed by the pool
425 * @pool: pool to get size
426 *
427 * Return size in bytes of memory managed by the pool.
428 */
429size_t gen_pool_size(struct gen_pool *pool)
430{
431    struct gen_pool_chunk *chunk;
432    size_t size = 0;
433
434    rcu_read_lock();
435    list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)
436        size += chunk_size(chunk);
437    rcu_read_unlock();
438    return size;
439}
440EXPORT_SYMBOL_GPL(gen_pool_size);
441
442/**
443 * gen_pool_set_algo - set the allocation algorithm
444 * @pool: pool to change allocation algorithm
445 * @algo: custom algorithm function
446 * @data: additional data used by @algo
447 *
448 * Call @algo for each memory allocation in the pool.
449 * If @algo is NULL use gen_pool_first_fit as default
450 * memory allocation function.
451 */
452void gen_pool_set_algo(struct gen_pool *pool, genpool_algo_t algo, void *data)
453{
454    rcu_read_lock();
455
456    pool->algo = algo;
457    if (!pool->algo)
458        pool->algo = gen_pool_first_fit;
459
460    pool->data = data;
461
462    rcu_read_unlock();
463}
464EXPORT_SYMBOL(gen_pool_set_algo);
465
466/**
467 * gen_pool_first_fit - find the first available region
468 * of memory matching the size requirement (no alignment constraint)
469 * @map: The address to base the search on
470 * @size: The bitmap size in bits
471 * @start: The bitnumber to start searching at
472 * @nr: The number of zeroed bits we're looking for
473 * @data: additional data - unused
474 */
475unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
476        unsigned long start, unsigned int nr, void *data)
477{
478    return bitmap_find_next_zero_area(map, size, start, nr, 0);
479}
480EXPORT_SYMBOL(gen_pool_first_fit);
481
482/**
483 * gen_pool_best_fit - find the best fitting region of memory
484 * macthing the size requirement (no alignment constraint)
485 * @map: The address to base the search on
486 * @size: The bitmap size in bits
487 * @start: The bitnumber to start searching at
488 * @nr: The number of zeroed bits we're looking for
489 * @data: additional data - unused
490 *
491 * Iterate over the bitmap to find the smallest free region
492 * which we can allocate the memory.
493 */
494unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
495        unsigned long start, unsigned int nr, void *data)
496{
497    unsigned long start_bit = size;
498    unsigned long len = size + 1;
499    unsigned long index;
500
501    index = bitmap_find_next_zero_area(map, size, start, nr, 0);
502
503    while (index < size) {
504        int next_bit = find_next_bit(map, size, index + nr);
505        if ((next_bit - index) < len) {
506            len = next_bit - index;
507            start_bit = index;
508            if (len == nr)
509                return start_bit;
510        }
511        index = bitmap_find_next_zero_area(map, size,
512                           next_bit + 1, nr, 0);
513    }
514
515    return start_bit;
516}
517EXPORT_SYMBOL(gen_pool_best_fit);
518
519static void devm_gen_pool_release(struct device *dev, void *res)
520{
521    gen_pool_destroy(*(struct gen_pool **)res);
522}
523
524/**
525 * devm_gen_pool_create - managed gen_pool_create
526 * @dev: device that provides the gen_pool
527 * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents
528 * @nid: node id of the node the pool structure should be allocated on, or -1
529 *
530 * Create a new special memory pool that can be used to manage special purpose
531 * memory not managed by the regular kmalloc/kfree interface. The pool will be
532 * automatically destroyed by the device management code.
533 */
534struct gen_pool *devm_gen_pool_create(struct device *dev, int min_alloc_order,
535        int nid)
536{
537    struct gen_pool **ptr, *pool;
538
539    ptr = devres_alloc(devm_gen_pool_release, sizeof(*ptr), GFP_KERNEL);
540
541    pool = gen_pool_create(min_alloc_order, nid);
542    if (pool) {
543        *ptr = pool;
544        devres_add(dev, ptr);
545    } else {
546        devres_free(ptr);
547    }
548
549    return pool;
550}
551
552/**
553 * dev_get_gen_pool - Obtain the gen_pool (if any) for a device
554 * @dev: device to retrieve the gen_pool from
555 *
556 * Returns the gen_pool for the device if one is present, or NULL.
557 */
558struct gen_pool *dev_get_gen_pool(struct device *dev)
559{
560    struct gen_pool **p = devres_find(dev, devm_gen_pool_release, NULL,
561                    NULL);
562
563    if (!p)
564        return NULL;
565    return *p;
566}
567EXPORT_SYMBOL_GPL(dev_get_gen_pool);
568
569#ifdef CONFIG_OF
570/**
571 * of_get_named_gen_pool - find a pool by phandle property
572 * @np: device node
573 * @propname: property name containing phandle(s)
574 * @index: index into the phandle array
575 *
576 * Returns the pool that contains the chunk starting at the physical
577 * address of the device tree node pointed at by the phandle property,
578 * or NULL if not found.
579 */
580struct gen_pool *of_get_named_gen_pool(struct device_node *np,
581    const char *propname, int index)
582{
583    struct platform_device *pdev;
584    struct device_node *np_pool;
585
586    np_pool = of_parse_phandle(np, propname, index);
587    if (!np_pool)
588        return NULL;
589    pdev = of_find_device_by_node(np_pool);
590    if (!pdev)
591        return NULL;
592    return dev_get_gen_pool(&pdev->dev);
593}
594EXPORT_SYMBOL_GPL(of_get_named_gen_pool);
595#endif /* CONFIG_OF */
596

Archive Download this file



interactive