Commit | Line | Data |
---|---|---|
f14f75b8 JS |
1 | /* |
2 | * Basic general purpose allocator for managing special purpose memory | |
3 | * not managed by the regular kmalloc/kfree interface. | |
4 | * Uses for this includes on-device special memory, uncached memory | |
5 | * etc. | |
6 | * | |
f14f75b8 JS |
7 | * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org> |
8 | * | |
9 | * This source code is licensed under the GNU General Public License, | |
10 | * Version 2. See the file COPYING for more details. | |
11 | */ | |
12 | ||
13 | #include <linux/module.h> | |
f14f75b8 JS |
14 | #include <linux/genalloc.h> |
15 | ||
f14f75b8 | 16 | |
929f9727 DN |
17 | /* |
18 | * Create a new special memory pool. | |
19 | * | |
20 | * @min_alloc_order: log base 2 of number of bytes each bitmap bit represents | |
21 | * @nid: node id of the node the pool structure should be allocated on, or -1 | |
22 | */ | |
23 | struct gen_pool *gen_pool_create(int min_alloc_order, int nid) | |
f14f75b8 | 24 | { |
929f9727 | 25 | struct gen_pool *pool; |
f14f75b8 | 26 | |
929f9727 DN |
27 | pool = kmalloc_node(sizeof(struct gen_pool), GFP_KERNEL, nid); |
28 | if (pool != NULL) { | |
29 | rwlock_init(&pool->lock); | |
30 | INIT_LIST_HEAD(&pool->chunks); | |
31 | pool->min_alloc_order = min_alloc_order; | |
32 | } | |
33 | return pool; | |
f14f75b8 JS |
34 | } |
35 | EXPORT_SYMBOL(gen_pool_create); | |
36 | ||
37 | ||
38 | /* | |
929f9727 DN |
39 | * Add a new chunk of memory to the specified pool. |
40 | * | |
41 | * @pool: pool to add new memory chunk to | |
42 | * @addr: starting address of memory chunk to add to pool | |
43 | * @size: size in bytes of the memory chunk to add to pool | |
44 | * @nid: node id of the node the chunk structure and bitmap should be | |
45 | * allocated on, or -1 | |
f14f75b8 | 46 | */ |
929f9727 DN |
47 | int gen_pool_add(struct gen_pool *pool, unsigned long addr, size_t size, |
48 | int nid) | |
f14f75b8 | 49 | { |
929f9727 DN |
50 | struct gen_pool_chunk *chunk; |
51 | int nbits = size >> pool->min_alloc_order; | |
52 | int nbytes = sizeof(struct gen_pool_chunk) + | |
53 | (nbits + BITS_PER_BYTE - 1) / BITS_PER_BYTE; | |
f14f75b8 | 54 | |
929f9727 DN |
55 | chunk = kmalloc_node(nbytes, GFP_KERNEL, nid); |
56 | if (unlikely(chunk == NULL)) | |
57 | return -1; | |
f14f75b8 | 58 | |
929f9727 DN |
59 | memset(chunk, 0, nbytes); |
60 | spin_lock_init(&chunk->lock); | |
61 | chunk->start_addr = addr; | |
62 | chunk->end_addr = addr + size; | |
f14f75b8 | 63 | |
929f9727 DN |
64 | write_lock(&pool->lock); |
65 | list_add(&chunk->next_chunk, &pool->chunks); | |
66 | write_unlock(&pool->lock); | |
67 | ||
68 | return 0; | |
f14f75b8 | 69 | } |
929f9727 | 70 | EXPORT_SYMBOL(gen_pool_add); |
f14f75b8 JS |
71 | |
72 | ||
322acc96 SW |
73 | /* |
74 | * Destroy a memory pool. Verifies that there are no outstanding allocations. | |
75 | * | |
76 | * @pool: pool to destroy | |
77 | */ | |
78 | void gen_pool_destroy(struct gen_pool *pool) | |
79 | { | |
80 | struct list_head *_chunk, *_next_chunk; | |
81 | struct gen_pool_chunk *chunk; | |
82 | int order = pool->min_alloc_order; | |
83 | int bit, end_bit; | |
84 | ||
85 | ||
86 | write_lock(&pool->lock); | |
87 | list_for_each_safe(_chunk, _next_chunk, &pool->chunks) { | |
88 | chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk); | |
89 | list_del(&chunk->next_chunk); | |
90 | ||
91 | end_bit = (chunk->end_addr - chunk->start_addr) >> order; | |
92 | bit = find_next_bit(chunk->bits, end_bit, 0); | |
93 | BUG_ON(bit < end_bit); | |
94 | ||
95 | kfree(chunk); | |
96 | } | |
97 | kfree(pool); | |
98 | return; | |
99 | } | |
100 | EXPORT_SYMBOL(gen_pool_destroy); | |
101 | ||
102 | ||
f14f75b8 | 103 | /* |
929f9727 DN |
104 | * Allocate the requested number of bytes from the specified pool. |
105 | * Uses a first-fit algorithm. | |
106 | * | |
107 | * @pool: pool to allocate from | |
108 | * @size: number of bytes to allocate from the pool | |
f14f75b8 | 109 | */ |
929f9727 | 110 | unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size) |
f14f75b8 | 111 | { |
929f9727 DN |
112 | struct list_head *_chunk; |
113 | struct gen_pool_chunk *chunk; | |
114 | unsigned long addr, flags; | |
115 | int order = pool->min_alloc_order; | |
116 | int nbits, bit, start_bit, end_bit; | |
f14f75b8 | 117 | |
929f9727 DN |
118 | if (size == 0) |
119 | return 0; | |
f14f75b8 | 120 | |
929f9727 DN |
121 | nbits = (size + (1UL << order) - 1) >> order; |
122 | ||
123 | read_lock(&pool->lock); | |
124 | list_for_each(_chunk, &pool->chunks) { | |
125 | chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk); | |
126 | ||
127 | end_bit = (chunk->end_addr - chunk->start_addr) >> order; | |
128 | end_bit -= nbits + 1; | |
129 | ||
130 | spin_lock_irqsave(&chunk->lock, flags); | |
131 | bit = -1; | |
132 | while (bit + 1 < end_bit) { | |
133 | bit = find_next_zero_bit(chunk->bits, end_bit, bit + 1); | |
134 | if (bit >= end_bit) | |
135 | break; | |
136 | ||
137 | start_bit = bit; | |
138 | if (nbits > 1) { | |
139 | bit = find_next_bit(chunk->bits, bit + nbits, | |
140 | bit + 1); | |
141 | if (bit - start_bit < nbits) | |
142 | continue; | |
143 | } | |
144 | ||
145 | addr = chunk->start_addr + | |
146 | ((unsigned long)start_bit << order); | |
147 | while (nbits--) | |
148 | __set_bit(start_bit++, &chunk->bits); | |
149 | spin_unlock_irqrestore(&chunk->lock, flags); | |
150 | read_unlock(&pool->lock); | |
151 | return addr; | |
f14f75b8 | 152 | } |
929f9727 DN |
153 | spin_unlock_irqrestore(&chunk->lock, flags); |
154 | } | |
155 | read_unlock(&pool->lock); | |
156 | return 0; | |
157 | } | |
158 | EXPORT_SYMBOL(gen_pool_alloc); | |
f14f75b8 | 159 | |
f14f75b8 | 160 | |
929f9727 DN |
161 | /* |
162 | * Free the specified memory back to the specified pool. | |
163 | * | |
164 | * @pool: pool to free to | |
165 | * @addr: starting address of memory to free back to pool | |
166 | * @size: size in bytes of memory to free | |
167 | */ | |
168 | void gen_pool_free(struct gen_pool *pool, unsigned long addr, size_t size) | |
169 | { | |
170 | struct list_head *_chunk; | |
171 | struct gen_pool_chunk *chunk; | |
172 | unsigned long flags; | |
173 | int order = pool->min_alloc_order; | |
174 | int bit, nbits; | |
175 | ||
176 | nbits = (size + (1UL << order) - 1) >> order; | |
177 | ||
178 | read_lock(&pool->lock); | |
179 | list_for_each(_chunk, &pool->chunks) { | |
180 | chunk = list_entry(_chunk, struct gen_pool_chunk, next_chunk); | |
181 | ||
182 | if (addr >= chunk->start_addr && addr < chunk->end_addr) { | |
183 | BUG_ON(addr + size > chunk->end_addr); | |
184 | spin_lock_irqsave(&chunk->lock, flags); | |
185 | bit = (addr - chunk->start_addr) >> order; | |
186 | while (nbits--) | |
187 | __clear_bit(bit++, &chunk->bits); | |
188 | spin_unlock_irqrestore(&chunk->lock, flags); | |
f14f75b8 JS |
189 | break; |
190 | } | |
f14f75b8 | 191 | } |
929f9727 DN |
192 | BUG_ON(nbits > 0); |
193 | read_unlock(&pool->lock); | |
f14f75b8 JS |
194 | } |
195 | EXPORT_SYMBOL(gen_pool_free); |