diff options
Diffstat (limited to 'drivers/gpu/nvgpu/common/mm/bitmap_allocator.c')
-rw-r--r-- | drivers/gpu/nvgpu/common/mm/bitmap_allocator.c | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/drivers/gpu/nvgpu/common/mm/bitmap_allocator.c b/drivers/gpu/nvgpu/common/mm/bitmap_allocator.c new file mode 100644 index 00000000..6f267c85 --- /dev/null +++ b/drivers/gpu/nvgpu/common/mm/bitmap_allocator.c | |||
@@ -0,0 +1,443 @@ | |||
1 | /* | ||
2 | * Copyright (c) 2016, NVIDIA CORPORATION. All rights reserved. | ||
3 | * | ||
4 | * This program is free software; you can redistribute it and/or modify it | ||
5 | * under the terms and conditions of the GNU General Public License, | ||
6 | * version 2, as published by the Free Software Foundation. | ||
7 | * | ||
8 | * This program is distributed in the hope it will be useful, but WITHOUT | ||
9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | ||
10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for | ||
11 | * more details. | ||
12 | * | ||
13 | * You should have received a copy of the GNU General Public License | ||
14 | * along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
15 | */ | ||
16 | |||
17 | #include <linux/kernel.h> | ||
18 | #include <linux/slab.h> | ||
19 | #include <linux/bitops.h> | ||
20 | |||
21 | #include <nvgpu/allocator.h> | ||
22 | |||
23 | #include "bitmap_allocator_priv.h" | ||
24 | |||
25 | static struct kmem_cache *meta_data_cache; /* slab cache for meta data. */ | ||
26 | static DEFINE_MUTEX(meta_data_cache_lock); | ||
27 | |||
28 | static u64 nvgpu_bitmap_alloc_length(struct nvgpu_allocator *a) | ||
29 | { | ||
30 | struct nvgpu_bitmap_allocator *ba = a->priv; | ||
31 | |||
32 | return ba->length; | ||
33 | } | ||
34 | |||
35 | static u64 nvgpu_bitmap_alloc_base(struct nvgpu_allocator *a) | ||
36 | { | ||
37 | struct nvgpu_bitmap_allocator *ba = a->priv; | ||
38 | |||
39 | return ba->base; | ||
40 | } | ||
41 | |||
42 | static int nvgpu_bitmap_alloc_inited(struct nvgpu_allocator *a) | ||
43 | { | ||
44 | struct nvgpu_bitmap_allocator *ba = a->priv; | ||
45 | int inited = ba->inited; | ||
46 | |||
47 | rmb(); | ||
48 | return inited; | ||
49 | } | ||
50 | |||
51 | static u64 nvgpu_bitmap_alloc_end(struct nvgpu_allocator *a) | ||
52 | { | ||
53 | struct nvgpu_bitmap_allocator *ba = a->priv; | ||
54 | |||
55 | return ba->base + ba->length; | ||
56 | } | ||
57 | |||
58 | static u64 nvgpu_bitmap_alloc_fixed(struct nvgpu_allocator *__a, | ||
59 | u64 base, u64 len) | ||
60 | { | ||
61 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
62 | u64 blks, offs, ret; | ||
63 | |||
64 | /* Compute the bit offset and make sure it's aligned to a block. */ | ||
65 | offs = base >> a->blk_shift; | ||
66 | if (offs * a->blk_size != base) | ||
67 | return 0; | ||
68 | |||
69 | offs -= a->bit_offs; | ||
70 | |||
71 | blks = len >> a->blk_shift; | ||
72 | if (blks * a->blk_size != len) | ||
73 | blks++; | ||
74 | |||
75 | alloc_lock(__a); | ||
76 | |||
77 | /* Check if the space requested is already occupied. */ | ||
78 | ret = bitmap_find_next_zero_area(a->bitmap, a->num_bits, offs, blks, 0); | ||
79 | if (ret != offs) | ||
80 | goto fail; | ||
81 | |||
82 | bitmap_set(a->bitmap, offs, blks); | ||
83 | |||
84 | a->bytes_alloced += blks * a->blk_size; | ||
85 | a->nr_fixed_allocs++; | ||
86 | alloc_unlock(__a); | ||
87 | |||
88 | alloc_dbg(__a, "Alloc-fixed 0x%-10llx 0x%-5llx [bits=0x%llx (%llu)]\n", | ||
89 | base, len, blks, blks); | ||
90 | return base; | ||
91 | |||
92 | fail: | ||
93 | alloc_unlock(__a); | ||
94 | alloc_dbg(__a, "Alloc-fixed failed! (0x%llx)\n", base); | ||
95 | return 0; | ||
96 | } | ||
97 | |||
98 | /* | ||
99 | * Two possibilities for this function: either we are freeing a fixed allocation | ||
100 | * or we are freeing a regular alloc but with GPU_ALLOC_NO_ALLOC_PAGE defined. | ||
101 | * | ||
102 | * Note: this function won't do much error checking. Thus you could really | ||
103 | * confuse the allocator if you misuse this function. | ||
104 | */ | ||
105 | static void nvgpu_bitmap_free_fixed(struct nvgpu_allocator *__a, | ||
106 | u64 base, u64 len) | ||
107 | { | ||
108 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
109 | u64 blks, offs; | ||
110 | |||
111 | offs = base >> a->blk_shift; | ||
112 | if (WARN_ON(offs * a->blk_size != base)) | ||
113 | return; | ||
114 | |||
115 | offs -= a->bit_offs; | ||
116 | |||
117 | blks = len >> a->blk_shift; | ||
118 | if (blks * a->blk_size != len) | ||
119 | blks++; | ||
120 | |||
121 | alloc_lock(__a); | ||
122 | bitmap_clear(a->bitmap, offs, blks); | ||
123 | a->bytes_freed += blks * a->blk_size; | ||
124 | alloc_unlock(__a); | ||
125 | |||
126 | alloc_dbg(__a, "Free-fixed 0x%-10llx 0x%-5llx [bits=0x%llx (%llu)]\n", | ||
127 | base, len, blks, blks); | ||
128 | } | ||
129 | |||
130 | /* | ||
131 | * Add the passed alloc to the tree of stored allocations. | ||
132 | */ | ||
133 | static void insert_alloc_metadata(struct nvgpu_bitmap_allocator *a, | ||
134 | struct nvgpu_bitmap_alloc *alloc) | ||
135 | { | ||
136 | struct rb_node **new = &a->allocs.rb_node; | ||
137 | struct rb_node *parent = NULL; | ||
138 | struct nvgpu_bitmap_alloc *tmp; | ||
139 | |||
140 | while (*new) { | ||
141 | tmp = container_of(*new, struct nvgpu_bitmap_alloc, | ||
142 | alloc_entry); | ||
143 | |||
144 | parent = *new; | ||
145 | if (alloc->base < tmp->base) | ||
146 | new = &((*new)->rb_left); | ||
147 | else if (alloc->base > tmp->base) | ||
148 | new = &((*new)->rb_right); | ||
149 | else { | ||
150 | WARN_ON("Duplicate entries in RB alloc tree!\n"); | ||
151 | return; | ||
152 | } | ||
153 | } | ||
154 | |||
155 | rb_link_node(&alloc->alloc_entry, parent, new); | ||
156 | rb_insert_color(&alloc->alloc_entry, &a->allocs); | ||
157 | } | ||
158 | |||
159 | /* | ||
160 | * Find and remove meta-data from the outstanding allocations. | ||
161 | */ | ||
162 | static struct nvgpu_bitmap_alloc *find_alloc_metadata( | ||
163 | struct nvgpu_bitmap_allocator *a, u64 addr) | ||
164 | { | ||
165 | struct rb_node *node = a->allocs.rb_node; | ||
166 | struct nvgpu_bitmap_alloc *alloc; | ||
167 | |||
168 | while (node) { | ||
169 | alloc = container_of(node, struct nvgpu_bitmap_alloc, | ||
170 | alloc_entry); | ||
171 | |||
172 | if (addr < alloc->base) | ||
173 | node = node->rb_left; | ||
174 | else if (addr > alloc->base) | ||
175 | node = node->rb_right; | ||
176 | else | ||
177 | break; | ||
178 | } | ||
179 | |||
180 | if (!node) | ||
181 | return NULL; | ||
182 | |||
183 | rb_erase(node, &a->allocs); | ||
184 | |||
185 | return alloc; | ||
186 | } | ||
187 | |||
188 | /* | ||
189 | * Tree of alloc meta data stores the address of the alloc not the bit offset. | ||
190 | */ | ||
191 | static int __nvgpu_bitmap_store_alloc(struct nvgpu_bitmap_allocator *a, | ||
192 | u64 addr, u64 len) | ||
193 | { | ||
194 | struct nvgpu_bitmap_alloc *alloc = | ||
195 | kmem_cache_alloc(meta_data_cache, GFP_KERNEL); | ||
196 | |||
197 | if (!alloc) | ||
198 | return -ENOMEM; | ||
199 | |||
200 | alloc->base = addr; | ||
201 | alloc->length = len; | ||
202 | |||
203 | insert_alloc_metadata(a, alloc); | ||
204 | |||
205 | return 0; | ||
206 | } | ||
207 | |||
208 | /* | ||
209 | * @len is in bytes. This routine will figure out the right number of bits to | ||
210 | * actually allocate. The return is the address in bytes as well. | ||
211 | */ | ||
212 | static u64 nvgpu_bitmap_alloc(struct nvgpu_allocator *__a, u64 len) | ||
213 | { | ||
214 | u64 blks, addr; | ||
215 | unsigned long offs, adjusted_offs, limit; | ||
216 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
217 | |||
218 | blks = len >> a->blk_shift; | ||
219 | |||
220 | if (blks * a->blk_size != len) | ||
221 | blks++; | ||
222 | |||
223 | alloc_lock(__a); | ||
224 | |||
225 | /* | ||
226 | * First look from next_blk and onwards... | ||
227 | */ | ||
228 | offs = bitmap_find_next_zero_area(a->bitmap, a->num_bits, | ||
229 | a->next_blk, blks, 0); | ||
230 | if (offs >= a->num_bits) { | ||
231 | /* | ||
232 | * If that didn't work try the remaining area. Since there can | ||
233 | * be available space that spans across a->next_blk we need to | ||
234 | * search up to the first set bit after that. | ||
235 | */ | ||
236 | limit = find_next_bit(a->bitmap, a->num_bits, a->next_blk); | ||
237 | offs = bitmap_find_next_zero_area(a->bitmap, limit, | ||
238 | 0, blks, 0); | ||
239 | if (offs >= a->next_blk) | ||
240 | goto fail; | ||
241 | } | ||
242 | |||
243 | bitmap_set(a->bitmap, offs, blks); | ||
244 | a->next_blk = offs + blks; | ||
245 | |||
246 | adjusted_offs = offs + a->bit_offs; | ||
247 | addr = ((u64)adjusted_offs) * a->blk_size; | ||
248 | |||
249 | /* | ||
250 | * Only do meta-data storage if we are allowed to allocate storage for | ||
251 | * that meta-data. The issue with using kmalloc() and friends is that | ||
252 | * in latency and success critical paths an alloc_page() call can either | ||
253 | * sleep for potentially a long time or, assuming GFP_ATOMIC, fail. | ||
254 | * Since we might not want either of these possibilities assume that the | ||
255 | * caller will keep what data it needs around to successfully free this | ||
256 | * allocation. | ||
257 | */ | ||
258 | if (!(a->flags & GPU_ALLOC_NO_ALLOC_PAGE) && | ||
259 | __nvgpu_bitmap_store_alloc(a, addr, blks * a->blk_size)) | ||
260 | goto fail_reset_bitmap; | ||
261 | |||
262 | alloc_dbg(__a, "Alloc 0x%-10llx 0x%-5llx [bits=0x%llx (%llu)]\n", | ||
263 | addr, len, blks, blks); | ||
264 | |||
265 | a->nr_allocs++; | ||
266 | a->bytes_alloced += (blks * a->blk_size); | ||
267 | alloc_unlock(__a); | ||
268 | |||
269 | return addr; | ||
270 | |||
271 | fail_reset_bitmap: | ||
272 | bitmap_clear(a->bitmap, offs, blks); | ||
273 | fail: | ||
274 | a->next_blk = 0; | ||
275 | alloc_unlock(__a); | ||
276 | alloc_dbg(__a, "Alloc failed!\n"); | ||
277 | return 0; | ||
278 | } | ||
279 | |||
280 | static void nvgpu_bitmap_free(struct nvgpu_allocator *__a, u64 addr) | ||
281 | { | ||
282 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
283 | struct nvgpu_bitmap_alloc *alloc = NULL; | ||
284 | u64 offs, adjusted_offs, blks; | ||
285 | |||
286 | alloc_lock(__a); | ||
287 | |||
288 | if (a->flags & GPU_ALLOC_NO_ALLOC_PAGE) { | ||
289 | WARN(1, "Using wrong free for NO_ALLOC_PAGE bitmap allocator"); | ||
290 | goto done; | ||
291 | } | ||
292 | |||
293 | alloc = find_alloc_metadata(a, addr); | ||
294 | if (!alloc) | ||
295 | goto done; | ||
296 | |||
297 | /* | ||
298 | * Address comes from adjusted offset (i.e the bit offset with | ||
299 | * a->bit_offs added. So start with that and then work out the real | ||
300 | * offs into the bitmap. | ||
301 | */ | ||
302 | adjusted_offs = addr >> a->blk_shift; | ||
303 | offs = adjusted_offs - a->bit_offs; | ||
304 | blks = alloc->length >> a->blk_shift; | ||
305 | |||
306 | bitmap_clear(a->bitmap, offs, blks); | ||
307 | alloc_dbg(__a, "Free 0x%-10llx\n", addr); | ||
308 | |||
309 | a->bytes_freed += alloc->length; | ||
310 | |||
311 | done: | ||
312 | kfree(alloc); | ||
313 | alloc_unlock(__a); | ||
314 | } | ||
315 | |||
316 | static void nvgpu_bitmap_alloc_destroy(struct nvgpu_allocator *__a) | ||
317 | { | ||
318 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
319 | struct nvgpu_bitmap_alloc *alloc; | ||
320 | struct rb_node *node; | ||
321 | |||
322 | /* | ||
323 | * Kill any outstanding allocations. | ||
324 | */ | ||
325 | while ((node = rb_first(&a->allocs)) != NULL) { | ||
326 | alloc = container_of(node, struct nvgpu_bitmap_alloc, | ||
327 | alloc_entry); | ||
328 | |||
329 | rb_erase(node, &a->allocs); | ||
330 | kfree(alloc); | ||
331 | } | ||
332 | |||
333 | kfree(a->bitmap); | ||
334 | kfree(a); | ||
335 | } | ||
336 | |||
337 | static void nvgpu_bitmap_print_stats(struct nvgpu_allocator *__a, | ||
338 | struct seq_file *s, int lock) | ||
339 | { | ||
340 | struct nvgpu_bitmap_allocator *a = bitmap_allocator(__a); | ||
341 | |||
342 | __alloc_pstat(s, __a, "Bitmap allocator params:\n"); | ||
343 | __alloc_pstat(s, __a, " start = 0x%llx\n", a->base); | ||
344 | __alloc_pstat(s, __a, " end = 0x%llx\n", a->base + a->length); | ||
345 | __alloc_pstat(s, __a, " blks = 0x%llx\n", a->num_bits); | ||
346 | |||
347 | /* Actual stats. */ | ||
348 | __alloc_pstat(s, __a, "Stats:\n"); | ||
349 | __alloc_pstat(s, __a, " Number allocs = 0x%llx\n", a->nr_allocs); | ||
350 | __alloc_pstat(s, __a, " Number fixed = 0x%llx\n", a->nr_fixed_allocs); | ||
351 | __alloc_pstat(s, __a, " Bytes alloced = 0x%llx\n", a->bytes_alloced); | ||
352 | __alloc_pstat(s, __a, " Bytes freed = 0x%llx\n", a->bytes_freed); | ||
353 | __alloc_pstat(s, __a, " Outstanding = 0x%llx\n", | ||
354 | a->bytes_alloced - a->bytes_freed); | ||
355 | } | ||
356 | |||
357 | static const struct nvgpu_allocator_ops bitmap_ops = { | ||
358 | .alloc = nvgpu_bitmap_alloc, | ||
359 | .free = nvgpu_bitmap_free, | ||
360 | |||
361 | .alloc_fixed = nvgpu_bitmap_alloc_fixed, | ||
362 | .free_fixed = nvgpu_bitmap_free_fixed, | ||
363 | |||
364 | .base = nvgpu_bitmap_alloc_base, | ||
365 | .length = nvgpu_bitmap_alloc_length, | ||
366 | .end = nvgpu_bitmap_alloc_end, | ||
367 | .inited = nvgpu_bitmap_alloc_inited, | ||
368 | |||
369 | .fini = nvgpu_bitmap_alloc_destroy, | ||
370 | |||
371 | .print_stats = nvgpu_bitmap_print_stats, | ||
372 | }; | ||
373 | |||
374 | |||
375 | int nvgpu_bitmap_allocator_init(struct gk20a *g, struct nvgpu_allocator *__a, | ||
376 | const char *name, u64 base, u64 length, | ||
377 | u64 blk_size, u64 flags) | ||
378 | { | ||
379 | int err; | ||
380 | struct nvgpu_bitmap_allocator *a; | ||
381 | |||
382 | mutex_lock(&meta_data_cache_lock); | ||
383 | if (!meta_data_cache) | ||
384 | meta_data_cache = KMEM_CACHE(nvgpu_bitmap_alloc, 0); | ||
385 | mutex_unlock(&meta_data_cache_lock); | ||
386 | |||
387 | if (!meta_data_cache) | ||
388 | return -ENOMEM; | ||
389 | |||
390 | if (WARN_ON(blk_size & (blk_size - 1))) | ||
391 | return -EINVAL; | ||
392 | |||
393 | /* | ||
394 | * blk_size must be a power-of-2; base length also need to be aligned | ||
395 | * to blk_size. | ||
396 | */ | ||
397 | if (blk_size & (blk_size - 1) || | ||
398 | base & (blk_size - 1) || length & (blk_size - 1)) | ||
399 | return -EINVAL; | ||
400 | |||
401 | if (base == 0) { | ||
402 | base = blk_size; | ||
403 | length -= blk_size; | ||
404 | } | ||
405 | |||
406 | a = kzalloc(sizeof(struct nvgpu_bitmap_allocator), GFP_KERNEL); | ||
407 | if (!a) | ||
408 | return -ENOMEM; | ||
409 | |||
410 | err = __nvgpu_alloc_common_init(__a, name, a, false, &bitmap_ops); | ||
411 | if (err) | ||
412 | goto fail; | ||
413 | |||
414 | a->base = base; | ||
415 | a->length = length; | ||
416 | a->blk_size = blk_size; | ||
417 | a->blk_shift = __ffs(a->blk_size); | ||
418 | a->num_bits = length >> a->blk_shift; | ||
419 | a->bit_offs = a->base >> a->blk_shift; | ||
420 | a->flags = flags; | ||
421 | |||
422 | a->bitmap = kcalloc(BITS_TO_LONGS(a->num_bits), sizeof(*a->bitmap), | ||
423 | GFP_KERNEL); | ||
424 | if (!a->bitmap) | ||
425 | goto fail; | ||
426 | |||
427 | wmb(); | ||
428 | a->inited = true; | ||
429 | |||
430 | nvgpu_init_alloc_debug(g, __a); | ||
431 | alloc_dbg(__a, "New allocator: type bitmap\n"); | ||
432 | alloc_dbg(__a, " base 0x%llx\n", a->base); | ||
433 | alloc_dbg(__a, " bit_offs 0x%llx\n", a->bit_offs); | ||
434 | alloc_dbg(__a, " size 0x%llx\n", a->length); | ||
435 | alloc_dbg(__a, " blk_size 0x%llx\n", a->blk_size); | ||
436 | alloc_dbg(__a, " flags 0x%llx\n", a->flags); | ||
437 | |||
438 | return 0; | ||
439 | |||
440 | fail: | ||
441 | kfree(a); | ||
442 | return err; | ||
443 | } | ||