summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTerje Bergstrom <tbergstrom@nvidia.com>2014-06-27 08:23:40 -0400
committerDan Willemsen <dwillemsen@nvidia.com>2015-03-18 15:12:08 -0400
commit4c021b1dfbb5e422d82370087f0813997e864f00 (patch)
tree836bda5e770c039c27787e8dae62debae45804ee
parentcc6ccd2e3fc1b097465e093a6294748113ab2cc7 (diff)
gpu: nvgpu: Replace allocator with bitmap alloc
Replace gk20a allocator with Linux bitmap allocator. Change-Id: Iba5e28f68ab5cf19e2c033005efd7f9da6e4a5b6 Signed-off-by: Terje Bergstrom <tbergstrom@nvidia.com> Reviewed-on: http://git-master/r/554184
Diffstat
-rw-r--r--drivers/gpu/nvgpu/gk20a/gk20a_allocator.c732
-rw-r--r--drivers/gpu/nvgpu/gk20a/gk20a_allocator.h25
2 files changed, 23 insertions, 734 deletions
diff --git a/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c
index 8ad3c63f..b404799f 100644
--- a/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c
+++ b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.c
@@ -18,627 +18,6 @@
18 18
19#include "gk20a_allocator.h" 19#include "gk20a_allocator.h"
20 20
21static inline void link_block_list(struct gk20a_allocator *allocator,
22 struct gk20a_alloc_block *block,
23 struct gk20a_alloc_block *prev,
24 struct rb_node *rb_parent);
25static inline void link_block_rb(struct gk20a_allocator *allocator,
26 struct gk20a_alloc_block *block,
27 struct rb_node **rb_link,
28 struct rb_node *rb_parent);
29static void link_block(struct gk20a_allocator *allocator,
30 struct gk20a_alloc_block *block,
31 struct gk20a_alloc_block *prev, struct rb_node **rb_link,
32 struct rb_node *rb_parent);
33static void insert_block(struct gk20a_allocator *allocator,
34 struct gk20a_alloc_block *block);
35
36static void unlink_block(struct gk20a_allocator *allocator,
37 struct gk20a_alloc_block *block,
38 struct gk20a_alloc_block *prev);
39static struct gk20a_alloc_block *unlink_blocks(
40 struct gk20a_allocator *allocator,
41 struct gk20a_alloc_block *block,
42 struct gk20a_alloc_block *prev, u32 end);
43
44static struct gk20a_alloc_block *find_block(
45 struct gk20a_allocator *allocator, u32 addr);
46static struct gk20a_alloc_block *find_block_prev(
47 struct gk20a_allocator *allocator, u32 addr,
48 struct gk20a_alloc_block **pprev);
49static struct gk20a_alloc_block *find_block_prepare(
50 struct gk20a_allocator *allocator, u32 addr,
51 struct gk20a_alloc_block **pprev, struct rb_node ***rb_link,
52 struct rb_node **rb_parent);
53
54static void update_free_addr_cache(struct gk20a_allocator *allocator,
55 struct gk20a_alloc_block *block,
56 u32 addr, u32 len, bool free);
57static int find_free_area(struct gk20a_allocator *allocator,
58 u32 *addr, u32 len);
59
60static void adjust_block(struct gk20a_alloc_block *block,
61 u32 start, u32 end,
62 struct gk20a_alloc_block *insert);
63static struct gk20a_alloc_block *merge_block(
64 struct gk20a_allocator *allocator,
65 struct gk20a_alloc_block *block, u32 addr, u32 end);
66static int split_block(struct gk20a_allocator *allocator,
67 struct gk20a_alloc_block *block,
68 u32 addr, int new_below);
69
70static int block_alloc_single_locked(struct gk20a_allocator *allocator,
71 u32 *addr, u32 len);
72static int block_free_locked(struct gk20a_allocator *allocator,
73 u32 addr, u32 len);
74
75/* link a block into allocator block list */
76static inline void link_block_list(struct gk20a_allocator *allocator,
77 struct gk20a_alloc_block *block,
78 struct gk20a_alloc_block *prev,
79 struct rb_node *rb_parent)
80{
81 struct gk20a_alloc_block *next;
82
83 block->prev = prev;
84 if (prev) {
85 next = prev->next;
86 prev->next = block;
87 } else {
88 allocator->block_first = block;
89 if (rb_parent)
90 next = rb_entry(rb_parent,
91 struct gk20a_alloc_block, rb);
92 else
93 next = NULL;
94 }
95 block->next = next;
96 if (next)
97 next->prev = block;
98}
99
100/* link a block into allocator rb tree */
101static inline void link_block_rb(struct gk20a_allocator *allocator,
102 struct gk20a_alloc_block *block, struct rb_node **rb_link,
103 struct rb_node *rb_parent)
104{
105 rb_link_node(&block->rb, rb_parent, rb_link);
106 rb_insert_color(&block->rb, &allocator->rb_root);
107}
108
109/* add a block to allocator with known location */
110static void link_block(struct gk20a_allocator *allocator,
111 struct gk20a_alloc_block *block,
112 struct gk20a_alloc_block *prev, struct rb_node **rb_link,
113 struct rb_node *rb_parent)
114{
115 struct gk20a_alloc_block *next;
116
117 link_block_list(allocator, block, prev, rb_parent);
118 link_block_rb(allocator, block, rb_link, rb_parent);
119 allocator->block_count++;
120
121 next = block->next;
122 allocator_dbg(allocator, "link new block %d:%d between block %d:%d and block %d:%d",
123 block->start, block->end,
124 prev ? prev->start : -1, prev ? prev->end : -1,
125 next ? next->start : -1, next ? next->end : -1);
126}
127
128/* add a block to allocator */
129static void insert_block(struct gk20a_allocator *allocator,
130 struct gk20a_alloc_block *block)
131{
132 struct gk20a_alloc_block *prev;
133 struct rb_node **rb_link, *rb_parent;
134
135 find_block_prepare(allocator, block->start,
136 &prev, &rb_link, &rb_parent);
137 link_block(allocator, block, prev, rb_link, rb_parent);
138}
139
140/* remove a block from allocator */
141static void unlink_block(struct gk20a_allocator *allocator,
142 struct gk20a_alloc_block *block,
143 struct gk20a_alloc_block *prev)
144{
145 struct gk20a_alloc_block *next = block->next;
146
147 allocator_dbg(allocator, "unlink block %d:%d between block %d:%d and block %d:%d",
148 block->start, block->end,
149 prev ? prev->start : -1, prev ? prev->end : -1,
150 next ? next->start : -1, next ? next->end : -1);
151
152 BUG_ON(block->start < allocator->base);
153 BUG_ON(block->end > allocator->limit);
154
155 if (prev)
156 prev->next = next;
157 else
158 allocator->block_first = next;
159
160 if (next)
161 next->prev = prev;
162 rb_erase(&block->rb, &allocator->rb_root);
163 if (allocator->block_recent == block)
164 allocator->block_recent = prev;
165
166 allocator->block_count--;
167}
168
169/* remove a list of blocks from allocator. the list can contain both
170 regular blocks and non-contiguous blocks. skip all non-contiguous
171 blocks, remove regular blocks into a separate list, return list head */
172static struct gk20a_alloc_block *
173unlink_blocks(struct gk20a_allocator *allocator,
174 struct gk20a_alloc_block *block,
175 struct gk20a_alloc_block *prev,
176 u32 end)
177{
178 struct gk20a_alloc_block **insertion_point;
179 struct gk20a_alloc_block *last_unfreed_block = prev;
180 struct gk20a_alloc_block *last_freed_block = NULL;
181 struct gk20a_alloc_block *first_freed_block = NULL;
182
183 insertion_point = (prev ? &prev->next : &allocator->block_first);
184 *insertion_point = NULL;
185
186 do {
187 if (!block->nc_block) {
188 allocator_dbg(allocator, "unlink block %d:%d",
189 block->start, block->end);
190 if (last_freed_block)
191 last_freed_block->next = block;
192 block->prev = last_freed_block;
193 rb_erase(&block->rb, &allocator->rb_root);
194 last_freed_block = block;
195 allocator->block_count--;
196 if (!first_freed_block)
197 first_freed_block = block;
198 } else {
199 allocator_dbg(allocator, "skip nc block %d:%d",
200 block->start, block->end);
201 if (!*insertion_point)
202 *insertion_point = block;
203 if (last_unfreed_block)
204 last_unfreed_block->next = block;
205 block->prev = last_unfreed_block;
206 last_unfreed_block = block;
207 }
208 block = block->next;
209 } while (block && block->start < end);
210
211 if (!*insertion_point)
212 *insertion_point = block;
213
214 if (block)
215 block->prev = last_unfreed_block;
216 if (last_unfreed_block)
217 last_unfreed_block->next = block;
218 if (last_freed_block)
219 last_freed_block->next = NULL;
220
221 allocator->block_recent = NULL;
222
223 return first_freed_block;
224}
225
226/* Look up the first block which satisfies addr < block->end,
227 NULL if none */
228static struct gk20a_alloc_block *
229find_block(struct gk20a_allocator *allocator, u32 addr)
230{
231 struct gk20a_alloc_block *block = allocator->block_recent;
232
233 if (!(block && block->end > addr && block->start <= addr)) {
234 struct rb_node *rb_node;
235
236 rb_node = allocator->rb_root.rb_node;
237 block = NULL;
238
239 while (rb_node) {
240 struct gk20a_alloc_block *block_tmp;
241
242 block_tmp = rb_entry(rb_node,
243 struct gk20a_alloc_block, rb);
244
245 if (block_tmp->end > addr) {
246 block = block_tmp;
247 if (block_tmp->start <= addr)
248 break;
249 rb_node = rb_node->rb_left;
250 } else
251 rb_node = rb_node->rb_right;
252 if (block)
253 allocator->block_recent = block;
254 }
255 }
256 return block;
257}
258
259/* Same as find_block, but also return a pointer to the previous block */
260static struct gk20a_alloc_block *
261find_block_prev(struct gk20a_allocator *allocator, u32 addr,
262 struct gk20a_alloc_block **pprev)
263{
264 struct gk20a_alloc_block *block = NULL, *prev = NULL;
265 struct rb_node *rb_node;
266 if (!allocator)
267 goto out;
268
269 block = allocator->block_first;
270
271 rb_node = allocator->rb_root.rb_node;
272
273 while (rb_node) {
274 struct gk20a_alloc_block *block_tmp;
275 block_tmp = rb_entry(rb_node, struct gk20a_alloc_block, rb);
276
277 if (addr < block_tmp->end)
278 rb_node = rb_node->rb_left;
279 else {
280 prev = block_tmp;
281 if (!prev->next || addr < prev->next->end)
282 break;
283 rb_node = rb_node->rb_right;
284 }
285 }
286
287out:
288 *pprev = prev;
289 return prev ? prev->next : block;
290}
291
292/* Same as find_block, but also return a pointer to the previous block
293 and return rb_node to prepare for rbtree insertion */
294static struct gk20a_alloc_block *
295find_block_prepare(struct gk20a_allocator *allocator, u32 addr,
296 struct gk20a_alloc_block **pprev, struct rb_node ***rb_link,
297 struct rb_node **rb_parent)
298{
299 struct gk20a_alloc_block *block;
300 struct rb_node **__rb_link, *__rb_parent, *rb_prev;
301
302 __rb_link = &allocator->rb_root.rb_node;
303 rb_prev = __rb_parent = NULL;
304 block = NULL;
305
306 while (*__rb_link) {
307 struct gk20a_alloc_block *block_tmp;
308
309 __rb_parent = *__rb_link;
310 block_tmp = rb_entry(__rb_parent,
311 struct gk20a_alloc_block, rb);
312
313 if (block_tmp->end > addr) {
314 block = block_tmp;
315 if (block_tmp->start <= addr)
316 break;
317 __rb_link = &__rb_parent->rb_left;
318 } else {
319 rb_prev = __rb_parent;
320 __rb_link = &__rb_parent->rb_right;
321 }
322 }
323
324 *pprev = NULL;
325 if (rb_prev)
326 *pprev = rb_entry(rb_prev, struct gk20a_alloc_block, rb);
327 *rb_link = __rb_link;
328 *rb_parent = __rb_parent;
329 return block;
330}
331
332/* update first_free_addr/last_free_addr based on new free addr
333 called when free block(s) and allocate block(s) */
334static void update_free_addr_cache(struct gk20a_allocator *allocator,
335 struct gk20a_alloc_block *next,
336 u32 addr, u32 len, bool free)
337{
338 /* update from block free */
339 if (free) {
340 if (allocator->first_free_addr > addr)
341 allocator->first_free_addr = addr;
342 } else { /* update from block alloc */
343 if (allocator->last_free_addr < addr + len)
344 allocator->last_free_addr = addr + len;
345 if (allocator->first_free_addr == addr) {
346 if (!next || next->start > addr + len)
347 allocator->first_free_addr = addr + len;
348 else
349 allocator->first_free_addr = next->end;
350 }
351 }
352
353 if (allocator->first_free_addr > allocator->last_free_addr)
354 allocator->first_free_addr = allocator->last_free_addr;
355}
356
357/* find a free address range for a fixed len */
358static int find_free_area(struct gk20a_allocator *allocator,
359 u32 *addr, u32 len)
360{
361 struct gk20a_alloc_block *block;
362 u32 start_addr, search_base, search_limit;
363
364 /* fixed addr allocation */
365 /* note: constraints for fixed are handled by caller */
366 if (*addr) {
367 block = find_block(allocator, *addr);
368 if (allocator->limit - len >= *addr &&
369 (!block || *addr + len <= block->start)) {
370 update_free_addr_cache(allocator, block,
371 *addr, len, false);
372 return 0;
373 } else
374 return -ENOMEM;
375 }
376
377 if (!allocator->constraint.enable) {
378 search_base = allocator->base;
379 search_limit = allocator->limit;
380 } else {
381 start_addr = *addr = allocator->constraint.base;
382 search_base = allocator->constraint.base;
383 search_limit = allocator->constraint.limit;
384 }
385
386 /* cached_hole_size has max free space up to last_free_addr */
387 if (len > allocator->cached_hole_size)
388 start_addr = *addr = allocator->last_free_addr;
389 else {
390 start_addr = *addr = allocator->base;
391 allocator->cached_hole_size = 0;
392 }
393
394 allocator_dbg(allocator, "start search addr : %d", start_addr);
395
396full_search:
397 for (block = find_block(allocator, *addr);; block = block->next) {
398 if (search_limit - len < *addr) {
399 /* start a new search in case we missed any hole */
400 if (start_addr != search_base) {
401 start_addr = *addr = search_base;
402 allocator->cached_hole_size = 0;
403 allocator_dbg(allocator, "start a new search from base");
404 goto full_search;
405 }
406 return -ENOMEM;
407 }
408 if (!block || *addr + len <= block->start) {
409 update_free_addr_cache(allocator, block,
410 *addr, len, false);
411 allocator_dbg(allocator, "free space from %d, len %d",
412 *addr, len);
413 allocator_dbg(allocator, "next free addr: %d",
414 allocator->last_free_addr);
415 return 0;
416 }
417 if (*addr + allocator->cached_hole_size < block->start)
418 allocator->cached_hole_size = block->start - *addr;
419 *addr = block->end;
420 }
421}
422
423/* expand/shrink a block with new start and new end
424 split_block function provides insert block for shrink */
425static void adjust_block(struct gk20a_alloc_block *block,
426 u32 start, u32 end, struct gk20a_alloc_block *insert)
427{
428 struct gk20a_allocator *allocator = block->allocator;
429
430 allocator_dbg(allocator, "curr block %d:%d, new start %d, new end %d",
431 block->start, block->end, start, end);
432
433 /* expand */
434 if (!insert) {
435 if (start == block->end) {
436 struct gk20a_alloc_block *next = block->next;
437
438 if (next && end == next->start) {
439 /* ....AAAA.... */
440 /* PPPP....NNNN */
441 /* PPPPPPPPPPPP */
442 unlink_block(allocator, next, block);
443 block->end = next->end;
444 kmem_cache_free(allocator->block_cache, next);
445 } else {
446 /* ....AAAA.... */
447 /* PPPP........ */
448 /* PPPPPPPP.... */
449 block->end = end;
450 }
451 }
452
453 if (end == block->start) {
454 /* ....AAAA.... */
455 /* ........NNNN */
456 /* PP..NNNNNNNN ....NNNNNNNN */
457 block->start = start;
458 }
459 } else { /* shrink */
460 /* BBBBBBBB -> BBBBIIII OR BBBBBBBB -> IIIIBBBB */
461 block->start = start;
462 block->end = end;
463 insert_block(allocator, insert);
464 }
465}
466
467/* given a range [addr, end], merge it with blocks before or after or both
468 if they can be combined into a contiguous block */
469static struct gk20a_alloc_block *
470merge_block(struct gk20a_allocator *allocator,
471 struct gk20a_alloc_block *prev, u32 addr, u32 end)
472{
473 struct gk20a_alloc_block *next;
474
475 if (prev)
476 next = prev->next;
477 else
478 next = allocator->block_first;
479
480 allocator_dbg(allocator, "curr block %d:%d", addr, end);
481 if (prev)
482 allocator_dbg(allocator, "prev block %d:%d",
483 prev->start, prev->end);
484 if (next)
485 allocator_dbg(allocator, "next block %d:%d",
486 next->start, next->end);
487
488 /* don't merge with non-contiguous allocation block */
489 if (prev && prev->end == addr && !prev->nc_block) {
490 adjust_block(prev, addr, end, NULL);
491 return prev;
492 }
493
494 /* don't merge with non-contiguous allocation block */
495 if (next && end == next->start && !next->nc_block) {
496 adjust_block(next, addr, end, NULL);
497 return next;
498 }
499
500 return NULL;
501}
502
503/* split a block based on addr. addr must be within (start, end).
504 if new_below == 1, link new block before adjusted current block */
505static int split_block(struct gk20a_allocator *allocator,
506 struct gk20a_alloc_block *block, u32 addr, int new_below)
507{
508 struct gk20a_alloc_block *new_block;
509
510 allocator_dbg(allocator, "start %d, split %d, end %d, new_below %d",
511 block->start, addr, block->end, new_below);
512
513 BUG_ON(!(addr > block->start && addr < block->end));
514
515 new_block = kmem_cache_alloc(allocator->block_cache, GFP_KERNEL);
516 if (!new_block)
517 return -ENOMEM;
518
519 *new_block = *block;
520
521 if (new_below)
522 new_block->end = addr;
523 else
524 new_block->start = addr;
525
526 if (new_below)
527 adjust_block(block, addr, block->end, new_block);
528 else
529 adjust_block(block, block->start, addr, new_block);
530
531 return 0;
532}
533
534/* free a list of blocks */
535static void free_blocks(struct gk20a_allocator *allocator,
536 struct gk20a_alloc_block *block)
537{
538 struct gk20a_alloc_block *curr_block;
539 while (block) {
540 curr_block = block;
541 block = block->next;
542 kmem_cache_free(allocator->block_cache, curr_block);
543 }
544}
545
546/* called with rw_sema acquired */
547static int block_alloc_single_locked(struct gk20a_allocator *allocator,
548 u32 *addr_req, u32 len)
549{
550 struct gk20a_alloc_block *block, *prev;
551 struct rb_node **rb_link, *rb_parent;
552 u32 addr = *addr_req;
553 int err;
554
555 *addr_req = ~0;
556
557 err = find_free_area(allocator, &addr, len);
558 if (err)
559 return err;
560
561 find_block_prepare(allocator, addr, &prev, &rb_link, &rb_parent);
562
563 /* merge requested free space with existing block(s)
564 if they can be combined into one contiguous block */
565 block = merge_block(allocator, prev, addr, addr + len);
566 if (block) {
567 *addr_req = addr;
568 return 0;
569 }
570
571 /* create a new block if cannot merge */
572 block = kmem_cache_zalloc(allocator->block_cache, GFP_KERNEL);
573 if (!block)
574 return -ENOMEM;
575
576 block->allocator = allocator;
577 block->start = addr;
578 block->end = addr + len;
579
580 link_block(allocator, block, prev, rb_link, rb_parent);
581
582 *addr_req = addr;
583
584 return 0;
585}
586
587/* called with rw_sema acquired */
588static int block_free_locked(struct gk20a_allocator *allocator,
589 u32 addr, u32 len)
590{
591 struct gk20a_alloc_block *block, *prev, *last;
592 u32 end;
593 int err;
594
595 /* no block has block->end > addr, already free */
596 block = find_block_prev(allocator, addr, &prev);
597 if (!block)
598 return 0;
599
600 allocator_dbg(allocator, "first block in free range %d:%d",
601 block->start, block->end);
602
603 end = addr + len;
604 /* not in any block, already free */
605 if (block->start >= end)
606 return 0;
607
608 /* don't touch nc_block in range free */
609 if (addr > block->start && !block->nc_block) {
610 int err = split_block(allocator, block, addr, 0);
611 if (err)
612 return err;
613 prev = block;
614 }
615
616 last = find_block(allocator, end);
617 if (last && end > last->start && !last->nc_block) {
618
619 allocator_dbg(allocator, "last block in free range %d:%d",
620 last->start, last->end);
621
622 err = split_block(allocator, last, end, 1);
623 if (err)
624 return err;
625 }
626
627 block = prev ? prev->next : allocator->block_first;
628
629 allocator_dbg(allocator, "first block for free %d:%d",
630 block->start, block->end);
631
632 /* remove blocks between [addr, addr + len) from rb tree
633 and put them in a list */
634 block = unlink_blocks(allocator, block, prev, end);
635 free_blocks(allocator, block);
636
637 update_free_addr_cache(allocator, NULL, addr, len, true);
638
639 return 0;
640}
641
642/* init allocator struct */ 21/* init allocator struct */
643int gk20a_allocator_init(struct gk20a_allocator *allocator, 22int gk20a_allocator_init(struct gk20a_allocator *allocator,
644 const char *name, u32 start, u32 len, u32 align) 23 const char *name, u32 start, u32 len, u32 align)
@@ -647,26 +26,19 @@ int gk20a_allocator_init(struct gk20a_allocator *allocator,
647 26
648 strncpy(allocator->name, name, 32); 27 strncpy(allocator->name, name, 32);
649 28
650 allocator->block_cache =
651 kmem_cache_create(allocator->name,
652 sizeof(struct gk20a_alloc_block), 0,
653 SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
654 if (!allocator->block_cache)
655 return -ENOMEM;
656
657 allocator->rb_root = RB_ROOT;
658
659 allocator->base = start; 29 allocator->base = start;
660 allocator->limit = start + len - 1; 30 allocator->limit = start + len - 1;
661 allocator->align = align; 31 allocator->align = align;
662 32
33 allocator->bitmap = kzalloc(BITS_TO_LONGS(len) * sizeof(long),
34 GFP_KERNEL);
35 if (!allocator->bitmap)
36 return -ENOMEM;
37
663 allocator_dbg(allocator, "%s : base %d, limit %d, align %d", 38 allocator_dbg(allocator, "%s : base %d, limit %d, align %d",
664 allocator->name, allocator->base, 39 allocator->name, allocator->base,
665 allocator->limit, allocator->align); 40 allocator->limit, allocator->align);
666 41
667 allocator->first_free_addr = allocator->last_free_addr = start;
668 allocator->cached_hole_size = len;
669
670 init_rwsem(&allocator->rw_sema); 42 init_rwsem(&allocator->rw_sema);
671 43
672 allocator->alloc = gk20a_allocator_block_alloc; 44 allocator->alloc = gk20a_allocator_block_alloc;
@@ -678,26 +50,9 @@ int gk20a_allocator_init(struct gk20a_allocator *allocator,
678/* destroy allocator, free all remaining blocks if any */ 50/* destroy allocator, free all remaining blocks if any */
679void gk20a_allocator_destroy(struct gk20a_allocator *allocator) 51void gk20a_allocator_destroy(struct gk20a_allocator *allocator)
680{ 52{
681 struct gk20a_alloc_block *block, *next;
682 u32 free_count = 0;
683
684 down_write(&allocator->rw_sema); 53 down_write(&allocator->rw_sema);
685 54
686 for (block = allocator->block_first; block; ) { 55 kfree(allocator->bitmap);
687 allocator_dbg(allocator, "free remaining block %d:%d",
688 block->start, block->end);
689 next = block->next;
690 kmem_cache_free(allocator->block_cache, block);
691 free_count++;
692 block = next;
693 }
694
695 up_write(&allocator->rw_sema);
696
697 /* block_count doesn't match real number of blocks */
698 BUG_ON(free_count != allocator->block_count);
699
700 kmem_cache_destroy(allocator->block_cache);
701 56
702 memset(allocator, 0, sizeof(struct gk20a_allocator)); 57 memset(allocator, 0, sizeof(struct gk20a_allocator));
703} 58}
@@ -712,23 +67,14 @@ void gk20a_allocator_destroy(struct gk20a_allocator *allocator)
712int gk20a_allocator_block_alloc(struct gk20a_allocator *allocator, 67int gk20a_allocator_block_alloc(struct gk20a_allocator *allocator,
713 u32 *addr, u32 len) 68 u32 *addr, u32 len)
714{ 69{
715 int ret; 70 unsigned long _addr;
716#if defined(ALLOCATOR_DEBUG)
717 struct gk20a_alloc_block *block;
718 bool should_fail = false;
719#endif
720 71
721 allocator_dbg(allocator, "[in] addr %d, len %d", *addr, len); 72 allocator_dbg(allocator, "[in] addr %d, len %d", *addr, len);
722 73
723 if ((*addr != 0 && *addr < allocator->base) || /* check addr range */ 74 if ((*addr != 0 && *addr < allocator->base) || /* check addr range */
724 *addr + len > allocator->limit || /* check addr range */ 75 *addr + len > allocator->limit || /* check addr range */
725 *addr & (allocator->align - 1) || /* check addr alignment */ 76 *addr & (allocator->align - 1) || /* check addr alignment */
726 len == 0) /* check len */ 77 len == 0) /* check len */
727 return -EINVAL;
728
729 if (allocator->constraint.enable &&
730 (*addr + len > allocator->constraint.limit ||
731 *addr > allocator->constraint.base))
732 return -EINVAL; 78 return -EINVAL;
733 79
734 len = ALIGN(len, allocator->align); 80 len = ALIGN(len, allocator->align);
@@ -737,52 +83,29 @@ int gk20a_allocator_block_alloc(struct gk20a_allocator *allocator,
737 83
738 down_write(&allocator->rw_sema); 84 down_write(&allocator->rw_sema);
739 85
740#if defined(ALLOCATOR_DEBUG) 86 _addr = bitmap_find_next_zero_area(allocator->bitmap,
741 if (*addr) { 87 allocator->limit - allocator->base + 1,
742 for (block = allocator->block_first; 88 *addr ? (*addr - allocator->base) : 0,
743 block; block = block->next) { 89 len,
744 if (block->end > *addr && block->start < *addr + len) { 90 allocator->align - 1);
745 should_fail = true; 91 if ((_addr > allocator->limit - allocator->base + 1) ||
746 break; 92 (*addr && *addr != (_addr + allocator->base)))
747 } 93 return -ENOMEM;
748 }
749 }
750#endif
751
752 ret = block_alloc_single_locked(allocator, addr, len);
753 94
754#if defined(ALLOCATOR_DEBUG) 95 bitmap_set(allocator->bitmap, _addr, len);
755 if (!ret) { 96 *addr = allocator->base + _addr;
756 bool allocated = false;
757 BUG_ON(should_fail);
758 BUG_ON(*addr < allocator->base);
759 BUG_ON(*addr + len > allocator->limit);
760 for (block = allocator->block_first;
761 block; block = block->next) {
762 if (!block->nc_block &&
763 block->start <= *addr &&
764 block->end >= *addr + len) {
765 allocated = true;
766 break;
767 }
768 }
769 BUG_ON(!allocated);
770 }
771#endif
772 97
773 up_write(&allocator->rw_sema); 98 up_write(&allocator->rw_sema);
774 99
775 allocator_dbg(allocator, "[out] addr %d, len %d", *addr, len); 100 allocator_dbg(allocator, "[out] addr %d, len %d", *addr, len);
776 101
777 return ret; 102 return 0;
778} 103}
779 104
780/* free all blocks between start and end */ 105/* free all blocks between start and end */
781int gk20a_allocator_block_free(struct gk20a_allocator *allocator, 106int gk20a_allocator_block_free(struct gk20a_allocator *allocator,
782 u32 addr, u32 len) 107 u32 addr, u32 len)
783{ 108{
784 int ret;
785
786 allocator_dbg(allocator, "[in] addr %d, len %d", addr, len); 109 allocator_dbg(allocator, "[in] addr %d, len %d", addr, len);
787 110
788 if (addr + len > allocator->limit || /* check addr range */ 111 if (addr + len > allocator->limit || /* check addr range */
@@ -795,23 +118,10 @@ int gk20a_allocator_block_free(struct gk20a_allocator *allocator,
795 return -EINVAL; 118 return -EINVAL;
796 119
797 down_write(&allocator->rw_sema); 120 down_write(&allocator->rw_sema);
798 121 bitmap_clear(allocator->bitmap, addr - allocator->base, len);
799 ret = block_free_locked(allocator, addr, len);
800
801#if defined(ALLOCATOR_DEBUG)
802 if (!ret) {
803 struct gk20a_alloc_block *block;
804 for (block = allocator->block_first;
805 block; block = block->next) {
806 if (!block->nc_block)
807 BUG_ON(block->start >= addr &&
808 block->end <= addr + len);
809 }
810 }
811#endif
812 up_write(&allocator->rw_sema); 122 up_write(&allocator->rw_sema);
813 123
814 allocator_dbg(allocator, "[out] addr %d, len %d", addr, len); 124 allocator_dbg(allocator, "[out] addr %d, len %d", addr, len);
815 125
816 return ret; 126 return 0;
817} 127}
diff --git a/drivers/gpu/nvgpu/gk20a/gk20a_allocator.h b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.h
index 5621800e..154f953a 100644
--- a/drivers/gpu/nvgpu/gk20a/gk20a_allocator.h
+++ b/drivers/gpu/nvgpu/gk20a/gk20a_allocator.h
@@ -33,6 +33,8 @@ struct gk20a_allocator {
33 u32 limit; /* max value = limit - 1 */ 33 u32 limit; /* max value = limit - 1 */
34 u32 align; /* alignment size, power of 2 */ 34 u32 align; /* alignment size, power of 2 */
35 35
36 unsigned long *bitmap; /* bitmap */
37
36 struct gk20a_alloc_block *block_first; /* first block in list */ 38 struct gk20a_alloc_block *block_first; /* first block in list */
37 struct gk20a_alloc_block *block_recent; /* last visited block */ 39 struct gk20a_alloc_block *block_recent; /* last visited block */
38 40
@@ -62,29 +64,6 @@ struct gk20a_allocator {
62 64
63}; 65};
64 66
65/* a block of linear space range [start, end) */
66struct gk20a_alloc_block {
67 struct gk20a_allocator *allocator; /* parent allocator */
68 struct rb_node rb; /* rb tree node */
69
70 u32 start; /* linear space range
71 [start, end) */
72 u32 end;
73
74 void *priv; /* backing structure for this
75 linear space block
76 page table, comp tag, etc */
77
78 struct gk20a_alloc_block *prev; /* prev block with lower address */
79 struct gk20a_alloc_block *next; /* next block with higher address */
80
81 bool nc_block;
82 struct gk20a_alloc_block *nc_prev; /* prev block for
83 non-contiguous allocation */
84 struct gk20a_alloc_block *nc_next; /* next block for
85 non-contiguous allocation */
86};
87
88int gk20a_allocator_init(struct gk20a_allocator *allocator, 67int gk20a_allocator_init(struct gk20a_allocator *allocator,
89 const char *name, u32 base, u32 size, u32 align); 68 const char *name, u32 base, u32 size, u32 align);
90void gk20a_allocator_destroy(struct gk20a_allocator *allocator); 69void gk20a_allocator_destroy(struct gk20a_allocator *allocator);
generated by cgit v1.2.2 (git 2.25.0) at 2024-07-16 07:30:06 -0400