summaryrefslogtreecommitdiff
path: root/drivers/frame_sink/encoder/h265/vmm.h (plain)
blob: cb0112e23d92f863ae77406c21e385900d97ef38
1/*
2 * vmm.h
3 *
4 * memory allocator for VPU
5 *
6 * Copyright (C) 2006 - 2013 CHIPS&MEDIA INC.
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
16 * more details.
17 *
18*/
19
20#ifndef __CNM_VIDEO_MEMORY_MANAGEMENT_H__
21#define __CNM_VIDEO_MEMORY_MANAGEMENT_H__
22
23#define VMEM_PAGE_SIZE (16 * 1024)
24#define MAKE_KEY(_a, _b) (((vmem_key_t)_a) << 32 | _b)
25#define KEY_TO_VALUE(_key) (_key >> 32)
26
27#define VMEM_P_ALLOC(_x) vmalloc(_x)
28#define VMEM_P_FREE(_x) vfree(_x)
29
30#define VMEM_ASSERT \
31 pr_info("VMEM_ASSERT at %s:%d\n", __FILE__, __LINE__)
32
33
34#define VMEM_HEIGHT(_tree) (_tree == NULL ? -1 : _tree->height)
35
36#define MAX(_a, _b) (_a >= _b ? _a : _b)
37
38struct avl_node_t;
39#define vmem_key_t unsigned long long
40
41struct vmem_info_t {
42 ulong total_pages;
43 ulong alloc_pages;
44 ulong free_pages;
45 ulong page_size;
46};
47
48struct page_t {
49 s32 pageno;
50 ulong addr;
51 s32 used;
52 s32 alloc_pages;
53 s32 first_pageno;
54};
55
56struct avl_node_t {
57 vmem_key_t key;
58 s32 height;
59 struct page_t *page;
60 struct avl_node_t *left;
61 struct avl_node_t *right;
62};
63
64struct video_mm_t {
65 struct avl_node_t *free_tree;
66 struct avl_node_t *alloc_tree;
67 struct page_t *page_list;
68 s32 num_pages;
69 ulong base_addr;
70 ulong mem_size;
71 s32 free_page_count;
72 s32 alloc_page_count;
73};
74
75enum rotation_dir_t {
76 LEFT,
77 RIGHT
78};
79
80struct avl_node_data_t {
81 s32 key;
82 struct page_t *page;
83};
84
85static struct avl_node_t *make_avl_node(
86 vmem_key_t key,
87 struct page_t *page)
88{
89 struct avl_node_t *node =
90 (struct avl_node_t *)VMEM_P_ALLOC(sizeof(struct avl_node_t));
91 node->key = key;
92 node->page = page;
93 node->height = 0;
94 node->left = NULL;
95 node->right = NULL;
96 return node;
97}
98
99static s32 get_balance_factor(struct avl_node_t *tree)
100{
101 s32 factor = 0;
102 if (tree)
103 factor = VMEM_HEIGHT(tree->right) - VMEM_HEIGHT(tree->left);
104 return factor;
105}
106
107/*
108 * Left Rotation
109 *
110 * A B
111 * \ / \
112 * B => A C
113 * / \ \
114 * D C D
115 *
116 */
117static struct avl_node_t *rotation_left(struct avl_node_t *tree)
118{
119 struct avl_node_t *rchild;
120 struct avl_node_t *lchild;
121
122 if (tree == NULL)
123 return NULL;
124
125 rchild = tree->right;
126 if (rchild == NULL)
127 return tree;
128
129 lchild = rchild->left;
130 rchild->left = tree;
131 tree->right = lchild;
132
133 tree->height =
134 MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
135 rchild->height =
136 MAX(VMEM_HEIGHT(rchild->left), VMEM_HEIGHT(rchild->right)) + 1;
137 return rchild;
138}
139
140
141/*
142 * Reft Rotation
143 *
144 * A B
145 * \ / \
146 * B => D A
147 * / \ /
148 * D C C
149 *
150 */
151static struct avl_node_t *rotation_right(struct avl_node_t *tree)
152{
153 struct avl_node_t *rchild;
154 struct avl_node_t *lchild;
155
156 if (tree == NULL)
157 return NULL;
158
159 lchild = tree->left;
160 if (lchild == NULL)
161 return NULL;
162
163 rchild = lchild->right;
164 lchild->right = tree;
165 tree->left = rchild;
166
167 tree->height =
168 MAX(VMEM_HEIGHT(tree->left),
169 VMEM_HEIGHT(tree->right)) + 1;
170 lchild->height =
171 MAX(VMEM_HEIGHT(lchild->left),
172 VMEM_HEIGHT(lchild->right)) + 1;
173 return lchild;
174}
175
176static struct avl_node_t *do_balance(struct avl_node_t *tree)
177{
178 s32 bfactor = 0, child_bfactor;
179 bfactor = get_balance_factor(tree);
180 if (bfactor >= 2) {
181 child_bfactor = get_balance_factor(tree->right);
182 if (child_bfactor == 1 || child_bfactor == 0) {
183 tree = rotation_left(tree);
184 } else if (child_bfactor == -1) {
185 tree->right = rotation_right(tree->right);
186 tree = rotation_left(tree);
187 } else {
188 pr_info(
189 "invalid balancing factor: %d\n",
190 child_bfactor);
191 VMEM_ASSERT;
192 return NULL;
193 }
194 } else if (bfactor <= -2) {
195 child_bfactor = get_balance_factor(tree->left);
196 if (child_bfactor == -1 || child_bfactor == 0) {
197 tree = rotation_right(tree);
198 } else if (child_bfactor == 1) {
199 tree->left = rotation_left(tree->left);
200 tree = rotation_right(tree);
201 } else {
202 pr_info(
203 "invalid balancing factor: %d\n",
204 child_bfactor);
205 VMEM_ASSERT;
206 return NULL;
207 }
208 }
209 return tree;
210}
211
212static struct avl_node_t *unlink_end_node(
213 struct avl_node_t *tree,
214 s32 dir,
215 struct avl_node_t **found_node)
216{
217 struct avl_node_t *node;
218 *found_node = NULL;
219
220 if (tree == NULL)
221 return NULL;
222
223 if (dir == LEFT) {
224 if (tree->left == NULL) {
225 *found_node = tree;
226 return NULL;
227 }
228 } else {
229 if (tree->right == NULL) {
230 *found_node = tree;
231 return NULL;
232 }
233 }
234
235 if (dir == LEFT) {
236 node = tree->left;
237 tree->left = unlink_end_node(tree->left, LEFT, found_node);
238 if (tree->left == NULL) {
239 tree->left = (*found_node)->right;
240 (*found_node)->left = NULL;
241 (*found_node)->right = NULL;
242 }
243 } else {
244 node = tree->right;
245 tree->right = unlink_end_node(tree->right, RIGHT, found_node);
246 if (tree->right == NULL) {
247 tree->right = (*found_node)->left;
248 (*found_node)->left = NULL;
249 (*found_node)->right = NULL;
250 }
251 }
252 tree->height =
253 MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
254 return do_balance(tree);
255}
256
257
258static struct avl_node_t *avltree_insert(
259 struct avl_node_t *tree,
260 vmem_key_t key,
261 struct page_t *page)
262{
263 if (tree == NULL) {
264 tree = make_avl_node(key, page);
265 } else {
266 if (key >= tree->key)
267 tree->right =
268 avltree_insert(tree->right, key, page);
269 else
270 tree->left =
271 avltree_insert(tree->left, key, page);
272 }
273 tree = do_balance(tree);
274 tree->height =
275 MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
276 return tree;
277}
278
279static struct avl_node_t *do_unlink(struct avl_node_t *tree)
280{
281 struct avl_node_t *node;
282 struct avl_node_t *end_node;
283 node = unlink_end_node(tree->right, LEFT, &end_node);
284 if (node) {
285 tree->right = node;
286 } else {
287 node =
288 unlink_end_node(tree->left, RIGHT, &end_node);
289 if (node)
290 tree->left = node;
291 }
292
293 if (node == NULL) {
294 node = tree->right ? tree->right : tree->left;
295 end_node = node;
296 }
297
298 if (end_node) {
299 end_node->left =
300 (tree->left != end_node) ?
301 tree->left : end_node->left;
302 end_node->right =
303 (tree->right != end_node) ?
304 tree->right : end_node->right;
305 end_node->height =
306 MAX(VMEM_HEIGHT(end_node->left),
307 VMEM_HEIGHT(end_node->right)) + 1;
308 }
309 tree = end_node;
310 return tree;
311}
312
313static struct avl_node_t *avltree_remove(
314 struct avl_node_t *tree,
315 struct avl_node_t **found_node,
316 vmem_key_t key)
317{
318 *found_node = NULL;
319 if (tree == NULL) {
320 pr_info("failed to find key %d\n", (s32)key);
321 return NULL;
322 }
323
324 if (key == tree->key) {
325 *found_node = tree;
326 tree = do_unlink(tree);
327 } else if (key > tree->key) {
328 tree->right =
329 avltree_remove(tree->right, found_node, key);
330 } else {
331 tree->left =
332 avltree_remove(tree->left, found_node, key);
333 }
334
335 if (tree)
336 tree->height =
337 MAX(VMEM_HEIGHT(tree->left),
338 VMEM_HEIGHT(tree->right)) + 1;
339
340 tree = do_balance(tree);
341 return tree;
342}
343
344void avltree_free(struct avl_node_t *tree)
345{
346 if (tree == NULL)
347 return;
348 if (tree->left == NULL && tree->right == NULL) {
349 VMEM_P_FREE(tree);
350 return;
351 }
352
353 avltree_free(tree->left);
354 tree->left = NULL;
355 avltree_free(tree->right);
356 tree->right = NULL;
357 VMEM_P_FREE(tree);
358}
359
360static struct avl_node_t *remove_approx_value(
361 struct avl_node_t *tree,
362 struct avl_node_t **found,
363 vmem_key_t key)
364{
365 *found = NULL;
366 if (tree == NULL)
367 return NULL;
368
369 if (key == tree->key) {
370 *found = tree;
371 tree = do_unlink(tree);
372 } else if (key > tree->key) {
373 tree->right = remove_approx_value(tree->right, found, key);
374 } else {
375 tree->left = remove_approx_value(tree->left, found, key);
376 if (*found == NULL) {
377 *found = tree;
378 tree = do_unlink(tree);
379 }
380 }
381 if (tree)
382 tree->height =
383 MAX(VMEM_HEIGHT(tree->left),
384 VMEM_HEIGHT(tree->right)) + 1;
385 tree = do_balance(tree);
386 return tree;
387}
388
389static void set_blocks_free(
390 struct video_mm_t *mm,
391 s32 pageno,
392 s32 npages)
393{
394 s32 last_pageno = pageno + npages - 1;
395 s32 i;
396 struct page_t *page;
397 struct page_t *last_page;
398
399 if (npages == 0)
400 VMEM_ASSERT;
401
402 if (last_pageno >= mm->num_pages) {
403 pr_info(
404 "set_blocks_free: invalid last page number: %d\n",
405 last_pageno);
406 VMEM_ASSERT;
407 return;
408 }
409
410 for (i = pageno; i <= last_pageno; i++) {
411 mm->page_list[i].used = 0;
412 mm->page_list[i].alloc_pages = 0;
413 mm->page_list[i].first_pageno = -1;
414 }
415
416 page = &mm->page_list[pageno];
417 page->alloc_pages = npages;
418 last_page = &mm->page_list[last_pageno];
419 last_page->first_pageno = pageno;
420 mm->free_tree =
421 avltree_insert(mm->free_tree, MAKE_KEY(npages, pageno), page);
422}
423
424static void set_blocks_alloc(
425 struct video_mm_t *mm,
426 s32 pageno,
427 s32 npages)
428{
429 s32 last_pageno = pageno + npages - 1;
430 s32 i;
431 struct page_t *page;
432 struct page_t *last_page;
433
434 if (last_pageno >= mm->num_pages) {
435 pr_info(
436 "set_blocks_free: invalid last page number: %d\n",
437 last_pageno);
438 VMEM_ASSERT;
439 return;
440 }
441
442 for (i = pageno; i <= last_pageno; i++) {
443 mm->page_list[i].used = 1;
444 mm->page_list[i].alloc_pages = 0;
445 mm->page_list[i].first_pageno = -1;
446 }
447
448 page = &mm->page_list[pageno];
449 page->alloc_pages = npages;
450 last_page = &mm->page_list[last_pageno];
451 last_page->first_pageno = pageno;
452 mm->alloc_tree =
453 avltree_insert(mm->alloc_tree, MAKE_KEY(page->addr, 0), page);
454}
455
456
457s32 vmem_init(struct video_mm_t *mm, ulong addr, ulong size)
458{
459 s32 i;
460
461 if (NULL == mm)
462 return -1;
463
464 mm->base_addr = (addr + (VMEM_PAGE_SIZE - 1))
465 & ~(VMEM_PAGE_SIZE - 1);
466 mm->mem_size = size & ~VMEM_PAGE_SIZE;
467 mm->num_pages = mm->mem_size / VMEM_PAGE_SIZE;
468 mm->free_tree = NULL;
469 mm->alloc_tree = NULL;
470 mm->free_page_count = mm->num_pages;
471 mm->alloc_page_count = 0;
472 mm->page_list =
473 (struct page_t *)VMEM_P_ALLOC(
474 mm->num_pages * sizeof(struct page_t));
475 if (mm->page_list == NULL) {
476 pr_err("%s:%d failed to kmalloc(%ld)\n",
477 __func__, __LINE__,
478 mm->num_pages * sizeof(struct page_t));
479 return -1;
480 }
481
482 for (i = 0; i < mm->num_pages; i++) {
483 mm->page_list[i].pageno = i;
484 mm->page_list[i].addr =
485 mm->base_addr + i * VMEM_PAGE_SIZE;
486 mm->page_list[i].alloc_pages = 0;
487 mm->page_list[i].used = 0;
488 mm->page_list[i].first_pageno = -1;
489 }
490 set_blocks_free(mm, 0, mm->num_pages);
491 return 0;
492}
493
494s32 vmem_exit(struct video_mm_t *mm)
495{
496 if (mm == NULL) {
497 pr_info("vmem_exit: invalid handle\n");
498 return -1;
499 }
500
501 if (mm->free_tree)
502 avltree_free(mm->free_tree);
503 if (mm->alloc_tree)
504 avltree_free(mm->alloc_tree);
505
506 if (mm->page_list) {
507 VMEM_P_FREE(mm->page_list);
508 mm->page_list = NULL;
509 }
510
511 mm->base_addr = 0;
512 mm->mem_size = 0;
513 mm->num_pages = 0;
514 mm->page_list = NULL;
515 mm->free_tree = NULL;
516 mm->alloc_tree = NULL;
517 mm->free_page_count = 0;
518 mm->alloc_page_count = 0;
519 return 0;
520}
521
522ulong vmem_alloc(struct video_mm_t *mm, s32 size, ulong pid)
523{
524 struct avl_node_t *node;
525 struct page_t *free_page;
526 s32 npages, free_size;
527 s32 alloc_pageno;
528 ulong ptr;
529
530 if (mm == NULL) {
531 pr_info("vmem_alloc: invalid handle\n");
532 return -1;
533 }
534
535 if (size <= 0)
536 return -1;
537
538 npages = (size + VMEM_PAGE_SIZE - 1) / VMEM_PAGE_SIZE;
539 mm->free_tree = remove_approx_value(mm->free_tree,
540 &node, MAKE_KEY(npages, 0));
541
542 if (node == NULL)
543 return -1;
544
545 free_page = node->page;
546 free_size = KEY_TO_VALUE(node->key);
547 alloc_pageno = free_page->pageno;
548 set_blocks_alloc(mm, alloc_pageno, npages);
549 if (npages != free_size) {
550 s32 free_pageno = alloc_pageno + npages;
551 set_blocks_free(mm, free_pageno, (free_size-npages));
552 }
553 VMEM_P_FREE(node);
554
555 ptr = mm->page_list[alloc_pageno].addr;
556 mm->alloc_page_count += npages;
557 mm->free_page_count -= npages;
558 return ptr;
559}
560
561s32 vmem_free(struct video_mm_t *mm, ulong ptr, ulong pid)
562{
563 ulong addr;
564 struct avl_node_t *found;
565 struct page_t *page;
566 s32 pageno, prev_free_pageno, next_free_pageno;
567 s32 prev_size, next_size;
568 s32 merge_page_no, merge_page_size, free_page_size;
569
570 if (mm == NULL) {
571 pr_info("vmem_free: invalid handle\n");
572 return -1;
573 }
574
575 addr = ptr;
576 mm->alloc_tree = avltree_remove(mm->alloc_tree, &found,
577 MAKE_KEY(addr, 0));
578
579 if (found == NULL) {
580 pr_info("vmem_free: 0x%08x not found\n", (s32)addr);
581 VMEM_ASSERT;
582 return -1;
583 }
584
585 /* find previous free block */
586 page = found->page;
587 pageno = page->pageno;
588 free_page_size = page->alloc_pages;
589 prev_free_pageno = pageno - 1;
590 prev_size = -1;
591 if (prev_free_pageno >= 0) {
592 if (mm->page_list[prev_free_pageno].used == 0) {
593 prev_free_pageno =
594 mm->page_list[prev_free_pageno].first_pageno;
595 prev_size =
596 mm->page_list[prev_free_pageno].alloc_pages;
597 }
598 }
599
600 /* find next free block */
601 next_free_pageno = pageno + page->alloc_pages;
602 next_free_pageno =
603 (next_free_pageno == mm->num_pages) ? -1 : next_free_pageno;
604 next_size = -1;
605 if (next_free_pageno >= 0) {
606 if (mm->page_list[next_free_pageno].used == 0) {
607 next_size =
608 mm->page_list[next_free_pageno].alloc_pages;
609 }
610 }
611 VMEM_P_FREE(found);
612
613 /* merge */
614 merge_page_no = page->pageno;
615 merge_page_size = page->alloc_pages;
616 if (prev_size >= 0) {
617 mm->free_tree = avltree_remove(mm->free_tree, &found,
618 MAKE_KEY(prev_size, prev_free_pageno));
619 if (found == NULL) {
620 VMEM_ASSERT;
621 return -1;
622 }
623 merge_page_no = found->page->pageno;
624 merge_page_size += found->page->alloc_pages;
625 VMEM_P_FREE(found);
626 }
627 if (next_size >= 0) {
628 mm->free_tree = avltree_remove(mm->free_tree, &found,
629 MAKE_KEY(next_size, next_free_pageno));
630 if (found == NULL) {
631 VMEM_ASSERT;
632 return -1;
633 }
634 merge_page_size += found->page->alloc_pages;
635 VMEM_P_FREE(found);
636 }
637 page->alloc_pages = 0;
638 page->first_pageno = -1;
639 set_blocks_free(mm, merge_page_no, merge_page_size);
640 mm->alloc_page_count -= free_page_size;
641 mm->free_page_count += free_page_size;
642 return 0;
643}
644
645s32 vmem_get_info(struct video_mm_t *mm, struct vmem_info_t *info)
646{
647 if (mm == NULL) {
648 pr_info("vmem_get_info: invalid handle\n");
649 return -1;
650 }
651
652 if (info == NULL)
653 return -1;
654
655 info->total_pages = mm->num_pages;
656 info->alloc_pages = mm->alloc_page_count;
657 info->free_pages = mm->free_page_count;
658 info->page_size = VMEM_PAGE_SIZE;
659 return 0;
660}
661#endif /* __CNM_VIDEO_MEMORY_MANAGEMENT_H__ */
662
generated by cgit at 2024-05-19 00:02:22 (GMT)