diff options
Diffstat (limited to 'drivers/gpu/nvgpu/gk20a/gk20a_allocator.c')
-rw-r--r-- | drivers/gpu/nvgpu/gk20a/gk20a_allocator.c | 732 |
1 files changed, 21 insertions, 711 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 | ||
21 | static 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); | ||
25 | static 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); | ||
29 | static 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); | ||
33 | static void insert_block(struct gk20a_allocator *allocator, | ||
34 | struct gk20a_alloc_block *block); | ||
35 | |||
36 | static void unlink_block(struct gk20a_allocator *allocator, | ||
37 | struct gk20a_alloc_block *block, | ||
38 | struct gk20a_alloc_block *prev); | ||
39 | static 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 | |||
44 | static struct gk20a_alloc_block *find_block( | ||
45 | struct gk20a_allocator *allocator, u32 addr); | ||
46 | static struct gk20a_alloc_block *find_block_prev( | ||
47 | struct gk20a_allocator *allocator, u32 addr, | ||
48 | struct gk20a_alloc_block **pprev); | ||
49 | static 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 | |||
54 | static void update_free_addr_cache(struct gk20a_allocator *allocator, | ||
55 | struct gk20a_alloc_block *block, | ||
56 | u32 addr, u32 len, bool free); | ||
57 | static int find_free_area(struct gk20a_allocator *allocator, | ||
58 | u32 *addr, u32 len); | ||
59 | |||
60 | static void adjust_block(struct gk20a_alloc_block *block, | ||
61 | u32 start, u32 end, | ||
62 | struct gk20a_alloc_block *insert); | ||
63 | static struct gk20a_alloc_block *merge_block( | ||
64 | struct gk20a_allocator *allocator, | ||
65 | struct gk20a_alloc_block *block, u32 addr, u32 end); | ||
66 | static int split_block(struct gk20a_allocator *allocator, | ||
67 | struct gk20a_alloc_block *block, | ||
68 | u32 addr, int new_below); | ||
69 | |||
70 | static int block_alloc_single_locked(struct gk20a_allocator *allocator, | ||
71 | u32 *addr, u32 len); | ||
72 | static int block_free_locked(struct gk20a_allocator *allocator, | ||
73 | u32 addr, u32 len); | ||
74 | |||
75 | /* link a block into allocator block list */ | ||
76 | static 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 */ | ||
101 | static 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 */ | ||
110 | static 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 */ | ||
129 | static 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 */ | ||
141 | static 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 */ | ||
172 | static struct gk20a_alloc_block * | ||
173 | unlink_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 */ | ||
228 | static struct gk20a_alloc_block * | ||
229 | find_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 */ | ||
260 | static struct gk20a_alloc_block * | ||
261 | find_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 | |||
287 | out: | ||
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 */ | ||
294 | static struct gk20a_alloc_block * | ||
295 | find_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) */ | ||
334 | static 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 */ | ||
358 | static 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 | |||
396 | full_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 */ | ||
425 | static 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 */ | ||
469 | static struct gk20a_alloc_block * | ||
470 | merge_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 */ | ||
505 | static 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 */ | ||
535 | static 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 */ | ||
547 | static 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 */ | ||
588 | static 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 */ |
643 | int gk20a_allocator_init(struct gk20a_allocator *allocator, | 22 | int 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 */ |
679 | void gk20a_allocator_destroy(struct gk20a_allocator *allocator) | 51 | void 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) | |||
712 | int gk20a_allocator_block_alloc(struct gk20a_allocator *allocator, | 67 | int 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 */ |
781 | int gk20a_allocator_block_free(struct gk20a_allocator *allocator, | 106 | int 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 | } |