diff options
Diffstat (limited to 'drivers/gpu/nvgpu')
-rw-r--r-- | drivers/gpu/nvgpu/common/mm/buddy_allocator.c | 127 | ||||
-rw-r--r-- | drivers/gpu/nvgpu/common/mm/buddy_allocator_priv.h | 25 |
2 files changed, 62 insertions, 90 deletions
diff --git a/drivers/gpu/nvgpu/common/mm/buddy_allocator.c b/drivers/gpu/nvgpu/common/mm/buddy_allocator.c index 36095710..44e8edb2 100644 --- a/drivers/gpu/nvgpu/common/mm/buddy_allocator.c +++ b/drivers/gpu/nvgpu/common/mm/buddy_allocator.c | |||
@@ -244,7 +244,7 @@ cleanup: | |||
244 | static void nvgpu_buddy_allocator_destroy(struct nvgpu_allocator *__a) | 244 | static void nvgpu_buddy_allocator_destroy(struct nvgpu_allocator *__a) |
245 | { | 245 | { |
246 | int i; | 246 | int i; |
247 | struct rb_node *node; | 247 | struct nvgpu_rbtree_node *node = NULL; |
248 | struct nvgpu_buddy *bud; | 248 | struct nvgpu_buddy *bud; |
249 | struct nvgpu_fixed_alloc *falloc; | 249 | struct nvgpu_fixed_alloc *falloc; |
250 | struct nvgpu_buddy_allocator *a = __a->priv; | 250 | struct nvgpu_buddy_allocator *a = __a->priv; |
@@ -256,22 +256,28 @@ static void nvgpu_buddy_allocator_destroy(struct nvgpu_allocator *__a) | |||
256 | /* | 256 | /* |
257 | * Free the fixed allocs first. | 257 | * Free the fixed allocs first. |
258 | */ | 258 | */ |
259 | while ((node = rb_first(&a->fixed_allocs)) != NULL) { | 259 | nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs); |
260 | falloc = container_of(node, | 260 | while (node) { |
261 | struct nvgpu_fixed_alloc, alloced_entry); | 261 | falloc = nvgpu_fixed_alloc_from_rbtree_node(node); |
262 | 262 | ||
263 | rb_erase(node, &a->fixed_allocs); | 263 | nvgpu_rbtree_unlink(node, &a->fixed_allocs); |
264 | __balloc_do_free_fixed(a, falloc); | 264 | __balloc_do_free_fixed(a, falloc); |
265 | |||
266 | nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs); | ||
265 | } | 267 | } |
266 | 268 | ||
267 | /* | 269 | /* |
268 | * And now free all outstanding allocations. | 270 | * And now free all outstanding allocations. |
269 | */ | 271 | */ |
270 | while ((node = rb_first(&a->alloced_buddies)) != NULL) { | 272 | nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies); |
271 | bud = container_of(node, struct nvgpu_buddy, alloced_entry); | 273 | while (node) { |
274 | bud = nvgpu_buddy_from_rbtree_node(node); | ||
275 | |||
272 | balloc_free_buddy(a, bud->start); | 276 | balloc_free_buddy(a, bud->start); |
273 | balloc_blist_add(a, bud); | 277 | balloc_blist_add(a, bud); |
274 | balloc_coalesce(a, bud); | 278 | balloc_coalesce(a, bud); |
279 | |||
280 | nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies); | ||
275 | } | 281 | } |
276 | 282 | ||
277 | /* | 283 | /* |
@@ -409,24 +415,10 @@ static int balloc_split_buddy(struct nvgpu_buddy_allocator *a, | |||
409 | static void balloc_alloc_buddy(struct nvgpu_buddy_allocator *a, | 415 | static void balloc_alloc_buddy(struct nvgpu_buddy_allocator *a, |
410 | struct nvgpu_buddy *b) | 416 | struct nvgpu_buddy *b) |
411 | { | 417 | { |
412 | struct rb_node **new = &(a->alloced_buddies.rb_node); | 418 | b->alloced_entry.key_start = b->start; |
413 | struct rb_node *parent = NULL; | 419 | b->alloced_entry.key_end = b->end; |
414 | |||
415 | while (*new) { | ||
416 | struct nvgpu_buddy *bud = container_of(*new, struct nvgpu_buddy, | ||
417 | alloced_entry); | ||
418 | |||
419 | parent = *new; | ||
420 | if (b->start < bud->start) | ||
421 | new = &((*new)->rb_left); | ||
422 | else if (b->start > bud->start) | ||
423 | new = &((*new)->rb_right); | ||
424 | else | ||
425 | BUG_ON("Duplicate entries in allocated list!\n"); | ||
426 | } | ||
427 | 420 | ||
428 | rb_link_node(&b->alloced_entry, parent, new); | 421 | nvgpu_rbtree_insert(&b->alloced_entry, &a->alloced_buddies); |
429 | rb_insert_color(&b->alloced_entry, &a->alloced_buddies); | ||
430 | 422 | ||
431 | buddy_set_alloced(b); | 423 | buddy_set_alloced(b); |
432 | a->buddy_list_alloced[b->order]++; | 424 | a->buddy_list_alloced[b->order]++; |
@@ -441,24 +433,16 @@ static void balloc_alloc_buddy(struct nvgpu_buddy_allocator *a, | |||
441 | static struct nvgpu_buddy *balloc_free_buddy(struct nvgpu_buddy_allocator *a, | 433 | static struct nvgpu_buddy *balloc_free_buddy(struct nvgpu_buddy_allocator *a, |
442 | u64 addr) | 434 | u64 addr) |
443 | { | 435 | { |
444 | struct rb_node *node = a->alloced_buddies.rb_node; | 436 | struct nvgpu_rbtree_node *node = NULL; |
445 | struct nvgpu_buddy *bud; | 437 | struct nvgpu_buddy *bud; |
446 | 438 | ||
447 | while (node) { | 439 | nvgpu_rbtree_search(addr, &node, a->alloced_buddies); |
448 | bud = container_of(node, struct nvgpu_buddy, alloced_entry); | ||
449 | |||
450 | if (addr < bud->start) | ||
451 | node = node->rb_left; | ||
452 | else if (addr > bud->start) | ||
453 | node = node->rb_right; | ||
454 | else | ||
455 | break; | ||
456 | } | ||
457 | |||
458 | if (!node) | 440 | if (!node) |
459 | return NULL; | 441 | return NULL; |
460 | 442 | ||
461 | rb_erase(node, &a->alloced_buddies); | 443 | bud = nvgpu_buddy_from_rbtree_node(node); |
444 | |||
445 | nvgpu_rbtree_unlink(node, &a->alloced_buddies); | ||
462 | buddy_clr_alloced(bud); | 446 | buddy_clr_alloced(bud); |
463 | a->buddy_list_alloced[bud->order]--; | 447 | a->buddy_list_alloced[bud->order]--; |
464 | 448 | ||
@@ -539,24 +523,24 @@ static u64 __balloc_do_alloc(struct nvgpu_buddy_allocator *a, | |||
539 | static int balloc_is_range_free(struct nvgpu_buddy_allocator *a, | 523 | static int balloc_is_range_free(struct nvgpu_buddy_allocator *a, |
540 | u64 base, u64 end) | 524 | u64 base, u64 end) |
541 | { | 525 | { |
542 | struct rb_node *node; | 526 | struct nvgpu_rbtree_node *node = NULL; |
543 | struct nvgpu_buddy *bud; | 527 | struct nvgpu_buddy *bud; |
544 | 528 | ||
545 | node = rb_first(&a->alloced_buddies); | 529 | nvgpu_rbtree_enum_start(0, &node, a->alloced_buddies); |
546 | if (!node) | 530 | if (!node) |
547 | return 1; /* No allocs yet. */ | 531 | return 1; /* No allocs yet. */ |
548 | 532 | ||
549 | bud = container_of(node, struct nvgpu_buddy, alloced_entry); | 533 | bud = nvgpu_buddy_from_rbtree_node(node); |
550 | 534 | ||
551 | while (bud->start < end) { | 535 | while (bud->start < end) { |
552 | if ((bud->start > base && bud->start < end) || | 536 | if ((bud->start > base && bud->start < end) || |
553 | (bud->end > base && bud->end < end)) | 537 | (bud->end > base && bud->end < end)) |
554 | return 0; | 538 | return 0; |
555 | 539 | ||
556 | node = rb_next(node); | 540 | nvgpu_rbtree_enum_next(&node, node); |
557 | if (!node) | 541 | if (!node) |
558 | break; | 542 | break; |
559 | bud = container_of(node, struct nvgpu_buddy, alloced_entry); | 543 | bud = nvgpu_buddy_from_rbtree_node(node); |
560 | } | 544 | } |
561 | 545 | ||
562 | return 1; | 546 | return 1; |
@@ -565,27 +549,10 @@ static int balloc_is_range_free(struct nvgpu_buddy_allocator *a, | |||
565 | static void balloc_alloc_fixed(struct nvgpu_buddy_allocator *a, | 549 | static void balloc_alloc_fixed(struct nvgpu_buddy_allocator *a, |
566 | struct nvgpu_fixed_alloc *f) | 550 | struct nvgpu_fixed_alloc *f) |
567 | { | 551 | { |
568 | struct rb_node **new = &(a->fixed_allocs.rb_node); | 552 | f->alloced_entry.key_start = f->start; |
569 | struct rb_node *parent = NULL; | 553 | f->alloced_entry.key_end = f->end; |
570 | 554 | ||
571 | while (*new) { | 555 | nvgpu_rbtree_insert(&f->alloced_entry, &a->fixed_allocs); |
572 | struct nvgpu_fixed_alloc *falloc = | ||
573 | container_of(*new, struct nvgpu_fixed_alloc, | ||
574 | alloced_entry); | ||
575 | |||
576 | BUG_ON(!virt_addr_valid(falloc)); | ||
577 | |||
578 | parent = *new; | ||
579 | if (f->start < falloc->start) | ||
580 | new = &((*new)->rb_left); | ||
581 | else if (f->start > falloc->start) | ||
582 | new = &((*new)->rb_right); | ||
583 | else | ||
584 | BUG_ON("Duplicate entries in allocated list!\n"); | ||
585 | } | ||
586 | |||
587 | rb_link_node(&f->alloced_entry, parent, new); | ||
588 | rb_insert_color(&f->alloced_entry, &a->fixed_allocs); | ||
589 | } | 556 | } |
590 | 557 | ||
591 | /* | 558 | /* |
@@ -597,25 +564,16 @@ static void balloc_alloc_fixed(struct nvgpu_buddy_allocator *a, | |||
597 | static struct nvgpu_fixed_alloc *balloc_free_fixed( | 564 | static struct nvgpu_fixed_alloc *balloc_free_fixed( |
598 | struct nvgpu_buddy_allocator *a, u64 addr) | 565 | struct nvgpu_buddy_allocator *a, u64 addr) |
599 | { | 566 | { |
600 | struct rb_node *node = a->fixed_allocs.rb_node; | ||
601 | struct nvgpu_fixed_alloc *falloc; | 567 | struct nvgpu_fixed_alloc *falloc; |
568 | struct nvgpu_rbtree_node *node = NULL; | ||
602 | 569 | ||
603 | while (node) { | 570 | nvgpu_rbtree_search(addr, &node, a->fixed_allocs); |
604 | falloc = container_of(node, | ||
605 | struct nvgpu_fixed_alloc, alloced_entry); | ||
606 | |||
607 | if (addr < falloc->start) | ||
608 | node = node->rb_left; | ||
609 | else if (addr > falloc->start) | ||
610 | node = node->rb_right; | ||
611 | else | ||
612 | break; | ||
613 | } | ||
614 | |||
615 | if (!node) | 571 | if (!node) |
616 | return NULL; | 572 | return NULL; |
617 | 573 | ||
618 | rb_erase(node, &a->fixed_allocs); | 574 | falloc = nvgpu_fixed_alloc_from_rbtree_node(node); |
575 | |||
576 | nvgpu_rbtree_unlink(node, &a->fixed_allocs); | ||
619 | 577 | ||
620 | return falloc; | 578 | return falloc; |
621 | } | 579 | } |
@@ -1137,7 +1095,7 @@ static void nvgpu_buddy_print_stats(struct nvgpu_allocator *__a, | |||
1137 | struct seq_file *s, int lock) | 1095 | struct seq_file *s, int lock) |
1138 | { | 1096 | { |
1139 | int i = 0; | 1097 | int i = 0; |
1140 | struct rb_node *node; | 1098 | struct nvgpu_rbtree_node *node = NULL; |
1141 | struct nvgpu_fixed_alloc *falloc; | 1099 | struct nvgpu_fixed_alloc *falloc; |
1142 | struct nvgpu_alloc_carveout *tmp; | 1100 | struct nvgpu_alloc_carveout *tmp; |
1143 | struct nvgpu_buddy_allocator *a = __a->priv; | 1101 | struct nvgpu_buddy_allocator *a = __a->priv; |
@@ -1183,14 +1141,15 @@ static void nvgpu_buddy_print_stats(struct nvgpu_allocator *__a, | |||
1183 | 1141 | ||
1184 | __alloc_pstat(s, __a, "\n"); | 1142 | __alloc_pstat(s, __a, "\n"); |
1185 | 1143 | ||
1186 | for (node = rb_first(&a->fixed_allocs), i = 1; | 1144 | nvgpu_rbtree_enum_start(0, &node, a->fixed_allocs); |
1187 | node != NULL; | 1145 | i = 1; |
1188 | node = rb_next(node)) { | 1146 | while (node) { |
1189 | falloc = container_of(node, | 1147 | falloc = nvgpu_fixed_alloc_from_rbtree_node(node); |
1190 | struct nvgpu_fixed_alloc, alloced_entry); | ||
1191 | 1148 | ||
1192 | __alloc_pstat(s, __a, "Fixed alloc (%d): [0x%llx -> 0x%llx]\n", | 1149 | __alloc_pstat(s, __a, "Fixed alloc (%d): [0x%llx -> 0x%llx]\n", |
1193 | i, falloc->start, falloc->end); | 1150 | i, falloc->start, falloc->end); |
1151 | |||
1152 | nvgpu_rbtree_enum_next(&node, a->fixed_allocs); | ||
1194 | } | 1153 | } |
1195 | 1154 | ||
1196 | __alloc_pstat(s, __a, "\n"); | 1155 | __alloc_pstat(s, __a, "\n"); |
@@ -1317,8 +1276,8 @@ int __nvgpu_buddy_allocator_init(struct gk20a *g, struct nvgpu_allocator *__a, | |||
1317 | goto fail; | 1276 | goto fail; |
1318 | } | 1277 | } |
1319 | 1278 | ||
1320 | a->alloced_buddies = RB_ROOT; | 1279 | a->alloced_buddies = NULL; |
1321 | a->fixed_allocs = RB_ROOT; | 1280 | a->fixed_allocs = NULL; |
1322 | nvgpu_init_list_node(&a->co_list); | 1281 | nvgpu_init_list_node(&a->co_list); |
1323 | err = balloc_init_lists(a); | 1282 | err = balloc_init_lists(a); |
1324 | if (err) | 1283 | if (err) |
diff --git a/drivers/gpu/nvgpu/common/mm/buddy_allocator_priv.h b/drivers/gpu/nvgpu/common/mm/buddy_allocator_priv.h index 549ab3d1..5c0b31c9 100644 --- a/drivers/gpu/nvgpu/common/mm/buddy_allocator_priv.h +++ b/drivers/gpu/nvgpu/common/mm/buddy_allocator_priv.h | |||
@@ -17,8 +17,7 @@ | |||
17 | #ifndef BUDDY_ALLOCATOR_PRIV_H | 17 | #ifndef BUDDY_ALLOCATOR_PRIV_H |
18 | #define BUDDY_ALLOCATOR_PRIV_H | 18 | #define BUDDY_ALLOCATOR_PRIV_H |
19 | 19 | ||
20 | #include <linux/rbtree.h> | 20 | #include <nvgpu/rbtree.h> |
21 | |||
22 | #include <nvgpu/list.h> | 21 | #include <nvgpu/list.h> |
23 | 22 | ||
24 | struct nvgpu_kmem_cache; | 23 | struct nvgpu_kmem_cache; |
@@ -35,7 +34,7 @@ struct nvgpu_buddy { | |||
35 | struct nvgpu_buddy *right; /* Higher address sub-node. */ | 34 | struct nvgpu_buddy *right; /* Higher address sub-node. */ |
36 | 35 | ||
37 | struct nvgpu_list_node buddy_entry; /* List entry for various lists. */ | 36 | struct nvgpu_list_node buddy_entry; /* List entry for various lists. */ |
38 | struct rb_node alloced_entry; /* RB tree of allocations. */ | 37 | struct nvgpu_rbtree_node alloced_entry; /* RB tree of allocations. */ |
39 | 38 | ||
40 | u64 start; /* Start address of this buddy. */ | 39 | u64 start; /* Start address of this buddy. */ |
41 | u64 end; /* End address of this buddy. */ | 40 | u64 end; /* End address of this buddy. */ |
@@ -62,6 +61,13 @@ nvgpu_buddy_from_buddy_entry(struct nvgpu_list_node *node) | |||
62 | ((uintptr_t)node - offsetof(struct nvgpu_buddy, buddy_entry)); | 61 | ((uintptr_t)node - offsetof(struct nvgpu_buddy, buddy_entry)); |
63 | }; | 62 | }; |
64 | 63 | ||
64 | static inline struct nvgpu_buddy * | ||
65 | nvgpu_buddy_from_rbtree_node(struct nvgpu_rbtree_node *node) | ||
66 | { | ||
67 | return (struct nvgpu_buddy *) | ||
68 | ((uintptr_t)node - offsetof(struct nvgpu_buddy, alloced_entry)); | ||
69 | }; | ||
70 | |||
65 | #define __buddy_flag_ops(flag, flag_up) \ | 71 | #define __buddy_flag_ops(flag, flag_up) \ |
66 | static inline int buddy_is_ ## flag(struct nvgpu_buddy *b) \ | 72 | static inline int buddy_is_ ## flag(struct nvgpu_buddy *b) \ |
67 | { \ | 73 | { \ |
@@ -98,12 +104,19 @@ __buddy_flag_ops(in_list, IN_LIST); | |||
98 | */ | 104 | */ |
99 | struct nvgpu_fixed_alloc { | 105 | struct nvgpu_fixed_alloc { |
100 | struct nvgpu_list_node buddies; /* List of buddies. */ | 106 | struct nvgpu_list_node buddies; /* List of buddies. */ |
101 | struct rb_node alloced_entry; /* RB tree of fixed allocations. */ | 107 | struct nvgpu_rbtree_node alloced_entry; /* RB tree of fixed allocations. */ |
102 | 108 | ||
103 | u64 start; /* Start of fixed block. */ | 109 | u64 start; /* Start of fixed block. */ |
104 | u64 end; /* End address. */ | 110 | u64 end; /* End address. */ |
105 | }; | 111 | }; |
106 | 112 | ||
113 | static inline struct nvgpu_fixed_alloc * | ||
114 | nvgpu_fixed_alloc_from_rbtree_node(struct nvgpu_rbtree_node *node) | ||
115 | { | ||
116 | return (struct nvgpu_fixed_alloc *) | ||
117 | ((uintptr_t)node - offsetof(struct nvgpu_fixed_alloc, alloced_entry)); | ||
118 | }; | ||
119 | |||
107 | /* | 120 | /* |
108 | * GPU buddy allocator for the various GPU address spaces. Each addressable unit | 121 | * GPU buddy allocator for the various GPU address spaces. Each addressable unit |
109 | * doesn't have to correspond to a byte. In some cases each unit is a more | 122 | * doesn't have to correspond to a byte. In some cases each unit is a more |
@@ -130,8 +143,8 @@ struct nvgpu_buddy_allocator { | |||
130 | u64 blks; /* Count of blks in the space. */ | 143 | u64 blks; /* Count of blks in the space. */ |
131 | u64 max_order; /* Specific maximum order. */ | 144 | u64 max_order; /* Specific maximum order. */ |
132 | 145 | ||
133 | struct rb_root alloced_buddies; /* Outstanding allocations. */ | 146 | struct nvgpu_rbtree_node *alloced_buddies; /* Outstanding allocations. */ |
134 | struct rb_root fixed_allocs; /* Outstanding fixed allocations. */ | 147 | struct nvgpu_rbtree_node *fixed_allocs; /* Outstanding fixed allocations. */ |
135 | 148 | ||
136 | struct nvgpu_list_node co_list; | 149 | struct nvgpu_list_node co_list; |
137 | 150 | ||