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