1 // SPDX-License-Identifier: GPL-2.0-only
5  * kmalloc/kfree interface.  Uses for this includes on-device special
8  * It is safe to use the allocator in NMI handlers and other special
21  * On architectures that don't have NMI-safe cmpxchg implementation,
26  * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org>
40 	return chunk->end_addr - chunk->start_addr + 1;  in chunk_size()
51 			return -EBUSY;  in set_bits_ll()
66 			return -EBUSY;  in clear_bits_ll()
74  * bitmap_set_ll - set the specified number of bits at the specified position
75  * @map: pointer to a bitmap
76  * @start: a bit position in @map
79  * Set @nr bits start from @start in @map lock-lessly. Several users
84 static int bitmap_set_ll(unsigned long *map, int start, int nr)  in bitmap_set_ll()  argument
86 	unsigned long *p = map + BIT_WORD(start);  in bitmap_set_ll()
88 	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);  in bitmap_set_ll()
91 	while (nr - bits_to_set >= 0) {  in bitmap_set_ll()
94 		nr -= bits_to_set;  in bitmap_set_ll()
109  * bitmap_clear_ll - clear the specified number of bits at the specified position
110  * @map: pointer to a bitmap
111  * @start: a bit position in @map
114  * Clear @nr bits start from @start in @map lock-lessly. Several users
119 static int bitmap_clear_ll(unsigned long *map, int start, int nr)  in bitmap_clear_ll()  argument
121 	unsigned long *p = map + BIT_WORD(start);  in bitmap_clear_ll()
123 	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);  in bitmap_clear_ll()
126 	while (nr - bits_to_clear >= 0) {  in bitmap_clear_ll()
129 		nr -= bits_to_clear;  in bitmap_clear_ll()
144  * gen_pool_create - create a new special memory pool
146  * @nid: node id of the node the pool structure should be allocated on, or -1
157 		spin_lock_init(&pool->lock);  in gen_pool_create()
158 		INIT_LIST_HEAD(&pool->chunks);  in gen_pool_create()
159 		pool->min_alloc_order = min_alloc_order;  in gen_pool_create()
160 		pool->algo = gen_pool_first_fit;  in gen_pool_create()
161 		pool->data = NULL;  in gen_pool_create()
162 		pool->name = NULL;  in gen_pool_create()
169  * gen_pool_add_owner- add a new chunk of special memory to the pool
175  *       allocated on, or -1
180  * Returns 0 on success or a -ve errno on failure.
186 	int nbits = size >> pool->min_alloc_order;  in gen_pool_add_owner()
192 		return -ENOMEM;  in gen_pool_add_owner()
194 	chunk->phys_addr = phys;  in gen_pool_add_owner()
195 	chunk->start_addr = virt;  in gen_pool_add_owner()
196 	chunk->end_addr = virt + size - 1;  in gen_pool_add_owner()
197 	chunk->owner = owner;  in gen_pool_add_owner()
198 	atomic_long_set(&chunk->avail, size);  in gen_pool_add_owner()
200 	spin_lock(&pool->lock);  in gen_pool_add_owner()
201 	list_add_rcu(&chunk->next_chunk, &pool->chunks);  in gen_pool_add_owner()
202 	spin_unlock(&pool->lock);  in gen_pool_add_owner()
209  * gen_pool_virt_to_phys - return the physical address of memory
213  * Returns the physical address on success, or -1 on error.
218 	phys_addr_t paddr = -1;  in gen_pool_virt_to_phys()
221 	list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {  in gen_pool_virt_to_phys()
222 		if (addr >= chunk->start_addr && addr <= chunk->end_addr) {  in gen_pool_virt_to_phys()
223 			paddr = chunk->phys_addr + (addr - chunk->start_addr);  in gen_pool_virt_to_phys()
234  * gen_pool_destroy - destroy a special memory pool
244 	int order = pool->min_alloc_order;  in gen_pool_destroy()
247 	list_for_each_safe(_chunk, _next_chunk, &pool->chunks) {  in gen_pool_destroy()
249 		list_del(&chunk->next_chunk);  in gen_pool_destroy()
252 		bit = find_next_bit(chunk->bits, end_bit, 0);  in gen_pool_destroy()
257 	kfree_const(pool->name);  in gen_pool_destroy()
263  * gen_pool_alloc_algo_owner - allocate special memory from the pool
271  * Uses the pool allocation function (with first-fit algorithm by default).
273  * NMI-safe cmpxchg implementation.
280 	int order = pool->min_alloc_order;  in gen_pool_alloc_algo_owner()
293 	nbits = (size + (1UL << order) - 1) >> order;  in gen_pool_alloc_algo_owner()
295 	list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {  in gen_pool_alloc_algo_owner()
296 		if (size > atomic_long_read(&chunk->avail))  in gen_pool_alloc_algo_owner()
302 		start_bit = algo(chunk->bits, end_bit, start_bit,  in gen_pool_alloc_algo_owner()
303 				 nbits, data, pool, chunk->start_addr);  in gen_pool_alloc_algo_owner()
306 		remain = bitmap_set_ll(chunk->bits, start_bit, nbits);  in gen_pool_alloc_algo_owner()
308 			remain = bitmap_clear_ll(chunk->bits, start_bit,  in gen_pool_alloc_algo_owner()
309 						 nbits - remain);  in gen_pool_alloc_algo_owner()
314 		addr = chunk->start_addr + ((unsigned long)start_bit << order);  in gen_pool_alloc_algo_owner()
316 		atomic_long_sub(size, &chunk->avail);  in gen_pool_alloc_algo_owner()
318 			*owner = chunk->owner;  in gen_pool_alloc_algo_owner()
327  * gen_pool_dma_alloc - allocate special memory from the pool for DMA usage
330  * @dma: dma-view physical address return value.  Use %NULL if unneeded.
333  * Uses the pool allocation function (with first-fit algorithm by default).
335  * NMI-safe cmpxchg implementation.
339 void *gen_pool_dma_alloc(struct gen_pool *pool, size_t size, dma_addr_t *dma)  in gen_pool_dma_alloc()  argument
341 	return gen_pool_dma_alloc_algo(pool, size, dma, pool->algo, pool->data);  in gen_pool_dma_alloc()
346  * gen_pool_dma_alloc_algo - allocate special memory from the pool for DMA
350  * @dma: DMA-view physical address return value. Use %NULL if unneeded.
356  * architectures without NMI-safe cmpxchg implementation.
361 		dma_addr_t *dma, genpool_algo_t algo, void *data)  in gen_pool_dma_alloc_algo()  argument
372 	if (dma)  in gen_pool_dma_alloc_algo()
373 		*dma = gen_pool_virt_to_phys(pool, vaddr);  in gen_pool_dma_alloc_algo()
380  * gen_pool_dma_alloc_align - allocate special memory from the pool for DMA
384  * @dma: DMA-view physical address return value. Use %NULL if unneeded.
389  * without NMI-safe cmpxchg implementation.
394 		dma_addr_t *dma, int align)  in gen_pool_dma_alloc_align()  argument
398 	return gen_pool_dma_alloc_algo(pool, size, dma,  in gen_pool_dma_alloc_align()
404  * gen_pool_dma_zalloc - allocate special zeroed memory from the pool for
405  * DMA usage
408  * @dma: dma-view physical address return value.  Use %NULL if unneeded.
411  * Uses the pool allocation function (with first-fit algorithm by default).
413  * NMI-safe cmpxchg implementation.
417 void *gen_pool_dma_zalloc(struct gen_pool *pool, size_t size, dma_addr_t *dma)  in gen_pool_dma_zalloc()  argument
419 	return gen_pool_dma_zalloc_algo(pool, size, dma, pool->algo, pool->data);  in gen_pool_dma_zalloc()
424  * gen_pool_dma_zalloc_algo - allocate special zeroed memory from the pool for
425  * DMA usage with the given pool algorithm
428  * @dma: DMA-view physical address return value. Use %NULL if unneeded.
434  * architectures without NMI-safe cmpxchg implementation.
439 		dma_addr_t *dma, genpool_algo_t algo, void *data)  in gen_pool_dma_zalloc_algo()  argument
441 	void *vaddr = gen_pool_dma_alloc_algo(pool, size, dma, algo, data);  in gen_pool_dma_zalloc_algo()
451  * gen_pool_dma_zalloc_align - allocate special zeroed memory from the pool for
452  * DMA usage with the given alignment
455  * @dma: DMA-view physical address return value. Use %NULL if unneeded.
460  * architectures without NMI-safe cmpxchg implementation.
465 		dma_addr_t *dma, int align)  in gen_pool_dma_zalloc_align()  argument
469 	return gen_pool_dma_zalloc_algo(pool, size, dma,  in gen_pool_dma_zalloc_align()
475  * gen_pool_free_owner - free allocated special memory back to the pool
483  * NMI-safe cmpxchg implementation.
489 	int order = pool->min_alloc_order;  in gen_pool_free_owner()
499 	nbits = (size + (1UL << order) - 1) >> order;  in gen_pool_free_owner()
501 	list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk) {  in gen_pool_free_owner()
502 		if (addr >= chunk->start_addr && addr <= chunk->end_addr) {  in gen_pool_free_owner()
503 			BUG_ON(addr + size - 1 > chunk->end_addr);  in gen_pool_free_owner()
504 			start_bit = (addr - chunk->start_addr) >> order;  in gen_pool_free_owner()
505 			remain = bitmap_clear_ll(chunk->bits, start_bit, nbits);  in gen_pool_free_owner()
508 			atomic_long_add(size, &chunk->avail);  in gen_pool_free_owner()
510 				*owner = chunk->owner;  in gen_pool_free_owner()
521  * gen_pool_for_each_chunk - call func for every chunk of generic memory pool
536 	list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk)  in gen_pool_for_each_chunk()
543  * gen_pool_has_addr - checks if an address falls within the range of a pool
555 	unsigned long end = start + size - 1;  in gen_pool_has_addr()
559 	list_for_each_entry_rcu(chunk, &(pool)->chunks, next_chunk) {  in gen_pool_has_addr()
560 		if (start >= chunk->start_addr && start <= chunk->end_addr) {  in gen_pool_has_addr()
561 			if (end <= chunk->end_addr) {  in gen_pool_has_addr()
573  * gen_pool_avail - get available free space of the pool
584 	list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)  in gen_pool_avail()
585 		avail += atomic_long_read(&chunk->avail);  in gen_pool_avail()
592  * gen_pool_size - get size in bytes of memory managed by the pool
603 	list_for_each_entry_rcu(chunk, &pool->chunks, next_chunk)  in gen_pool_size()
611  * gen_pool_set_algo - set the allocation algorithm
624 	pool->algo = algo;  in gen_pool_set_algo()
625 	if (!pool->algo)  in gen_pool_set_algo()
626 		pool->algo = gen_pool_first_fit;  in gen_pool_set_algo()
628 	pool->data = data;  in gen_pool_set_algo()
635  * gen_pool_first_fit - find the first available region
637  * @map: The address to base the search on
641  * @data: additional data - unused
644 unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,  in gen_pool_first_fit()  argument
648 	return bitmap_find_next_zero_area(map, size, start, nr, 0);  in gen_pool_first_fit()
653  * gen_pool_first_fit_align - find the first available region
655  * @map: The address to base the search on
662 unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size,  in gen_pool_first_fit_align()  argument
671 	order = pool->min_alloc_order;  in gen_pool_first_fit_align()
672 	align_mask = ((alignment->align + (1UL << order) - 1) >> order) - 1;  in gen_pool_first_fit_align()
673 	align_off = (start_addr & (alignment->align - 1)) >> order;  in gen_pool_first_fit_align()
675 	return bitmap_find_next_zero_area_off(map, size, start, nr,  in gen_pool_first_fit_align()
681  * gen_pool_fixed_alloc - reserve a specific region
682  * @map: The address to base the search on
689 unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size,  in gen_pool_fixed_alloc()  argument
699 	order = pool->min_alloc_order;  in gen_pool_fixed_alloc()
700 	offset_bit = fixed_data->offset >> order;  in gen_pool_fixed_alloc()
701 	if (WARN_ON(fixed_data->offset & ((1UL << order) - 1)))  in gen_pool_fixed_alloc()
704 	start_bit = bitmap_find_next_zero_area(map, size,  in gen_pool_fixed_alloc()
713  * gen_pool_first_fit_order_align - find the first available region
716  * @map: The address to base the search on
720  * @data: additional data - unused
723 unsigned long gen_pool_first_fit_order_align(unsigned long *map,  in gen_pool_first_fit_order_align()  argument
728 	unsigned long align_mask = roundup_pow_of_two(nr) - 1;  in gen_pool_first_fit_order_align()
730 	return bitmap_find_next_zero_area(map, size, start, nr, align_mask);  in gen_pool_first_fit_order_align()
735  * gen_pool_best_fit - find the best fitting region of memory
737  * @map: The address to base the search on
741  * @data: additional data - unused
747 unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,  in gen_pool_best_fit()  argument
755 	index = bitmap_find_next_zero_area(map, size, start, nr, 0);  in gen_pool_best_fit()
758 		int next_bit = find_next_bit(map, size, index + nr);  in gen_pool_best_fit()
759 		if ((next_bit - index) < len) {  in gen_pool_best_fit()
760 			len = next_bit - index;  in gen_pool_best_fit()
765 		index = bitmap_find_next_zero_area(map, size,  in gen_pool_best_fit()
783 	if (!data && !(*p)->name)  in devm_gen_pool_match()
786 	if (!data || !(*p)->name)  in devm_gen_pool_match()
789 	return !strcmp((*p)->name, data);  in devm_gen_pool_match()
793  * gen_pool_get - Obtain the gen_pool (if any) for a device
812  * devm_gen_pool_create - managed gen_pool_create
830 		return ERR_PTR(-EINVAL);  in devm_gen_pool_create()
835 			return ERR_PTR(-ENOMEM);  in devm_gen_pool_create()
847 	pool->name = pool_name;  in devm_gen_pool_create()
857 	return ERR_PTR(-ENOMEM);  in devm_gen_pool_create()
863  * of_gen_pool_get - find a pool by phandle property
893 			name = np_pool->name;  in of_gen_pool_get()
896 		pool = gen_pool_get(&pdev->dev, name);  in of_gen_pool_get()