mm.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661
  1. // SPDX-License-Identifier: LGPL-2.1 OR BSD-3-Clause
  2. /*
  3. * Copyright (c) 2018, Chips&Media
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions are met:
  8. *
  9. * 1. Redistributions of source code must retain the above copyright notice, this
  10. * list of conditions and the following disclaimer.
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  16. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
  19. * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  21. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  22. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  24. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include "mm.h"
  29. #ifdef MM_DEBUG
  30. #ifdef _MSC_VER
  31. #define DPRINT(_fmt, ...) printf(_fmt, __VA_ARGS__)
  32. #else
  33. #define DPRINT(_fmt, ...) printf(_fmt, args...)
  34. #endif
  35. #else
  36. #define DPRINT(_fmt, ...)
  37. #endif
  38. #define P_ALLOC(_x) malloc(_x)
  39. #define P_FREE(_x) free(_x)
  40. #define ASSERT(_exp) if (!(_exp)) { printf("ASSERT at %s:%d\n", __FILE__, __LINE__); while(1); }
  41. #define HEIGHT(_tree) (_tree==NULL ? -1 : _tree->height)
  42. #define MAX(_a, _b) (_a >= _b ? _a : _b)
  43. typedef enum {
  44. LEFT,
  45. RIGHT
  46. } rotation_dir_t;
  47. typedef struct avl_node_data_struct {
  48. int key;
  49. page_t* page;
  50. } avl_node_data_t;
  51. static avl_node_t*
  52. make_avl_node(
  53. vmem_key_t key,
  54. page_t* page
  55. )
  56. {
  57. avl_node_t* node = (avl_node_t*)P_ALLOC(sizeof(avl_node_t));
  58. if (node != NULL)
  59. {
  60. node->key = key;
  61. node->page = page;
  62. node->height = 0;
  63. node->left = NULL;
  64. node->right = NULL;
  65. }
  66. return node;
  67. }
  68. static int
  69. get_balance_factor(
  70. avl_node_t* tree
  71. )
  72. {
  73. int factor = 0;
  74. if (tree) {
  75. factor = HEIGHT(tree->right) - HEIGHT(tree->left);
  76. }
  77. return factor;
  78. }
  79. /*
  80. * Left Rotation
  81. *
  82. * A B
  83. * \ / \
  84. * B => A C
  85. * / \ \
  86. * D C D
  87. *
  88. */
  89. static avl_node_t*
  90. rotation_left(
  91. avl_node_t* tree
  92. )
  93. {
  94. avl_node_t* rchild;
  95. avl_node_t* lchild;
  96. if (tree == NULL) return NULL;
  97. rchild = tree->right;
  98. if (rchild == NULL) {
  99. return tree;
  100. }
  101. lchild = rchild->left;
  102. rchild->left = tree;
  103. tree->right = lchild;
  104. tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  105. rchild->height = MAX(HEIGHT(rchild->left), HEIGHT(rchild->right)) + 1;
  106. return rchild;
  107. }
  108. /*
  109. * Reft Rotation
  110. *
  111. * A B
  112. * \ / \
  113. * B => D A
  114. * / \ /
  115. * D C C
  116. *
  117. */
  118. static avl_node_t*
  119. rotation_right(
  120. avl_node_t* tree
  121. )
  122. {
  123. avl_node_t* rchild;
  124. avl_node_t* lchild;
  125. if (tree == NULL) return NULL;
  126. lchild = tree->left;
  127. if (lchild == NULL) return NULL;
  128. rchild = lchild->right;
  129. lchild->right = tree;
  130. tree->left = rchild;
  131. tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  132. lchild->height = MAX(HEIGHT(lchild->left), HEIGHT(lchild->right)) + 1;
  133. return lchild;
  134. }
  135. static avl_node_t*
  136. do_balance(
  137. avl_node_t* tree
  138. )
  139. {
  140. int bfactor = 0, child_bfactor; /* balancing factor */
  141. bfactor = get_balance_factor(tree);
  142. if (bfactor >= 2) {
  143. child_bfactor = get_balance_factor(tree->right);
  144. if (child_bfactor == 1 || child_bfactor == 0) {
  145. tree = rotation_left(tree);
  146. } else if (child_bfactor == -1) {
  147. tree->right = rotation_right(tree->right);
  148. tree = rotation_left(tree);
  149. } else {
  150. fprintf(stderr, "invalid balancing factor: %d\n", child_bfactor);
  151. ASSERT(0);
  152. return NULL;
  153. }
  154. } else if (bfactor <= -2) {
  155. child_bfactor = get_balance_factor(tree->left);
  156. if (child_bfactor == -1 || child_bfactor == 0) {
  157. tree = rotation_right(tree);
  158. } else if (child_bfactor == 1) {
  159. tree->left = rotation_left(tree->left);
  160. tree = rotation_right(tree);
  161. } else {
  162. fprintf(stderr, "invalid balancing factor: %d\n", child_bfactor);
  163. ASSERT(0);
  164. return NULL;
  165. }
  166. }
  167. return tree;
  168. }
  169. static avl_node_t*
  170. unlink_end_node(
  171. avl_node_t* tree,
  172. int dir,
  173. avl_node_t** found_node
  174. )
  175. {
  176. *found_node = NULL;
  177. if (tree == NULL) return NULL;
  178. if (dir == LEFT) {
  179. if (tree->left == NULL) {
  180. *found_node = tree;
  181. return NULL;
  182. }
  183. } else {
  184. if (tree->right == NULL) {
  185. *found_node = tree;
  186. return NULL;
  187. }
  188. }
  189. if (dir == LEFT) {
  190. tree->left = unlink_end_node(tree->left, LEFT, found_node);
  191. if (tree->left == NULL) {
  192. tree->left = (*found_node)->right;
  193. (*found_node)->left = NULL;
  194. (*found_node)->right = NULL;
  195. }
  196. } else {
  197. tree->right = unlink_end_node(tree->right, RIGHT, found_node);
  198. if (tree->right == NULL) {
  199. tree->right = (*found_node)->left;
  200. (*found_node)->left = NULL;
  201. (*found_node)->right = NULL;
  202. }
  203. }
  204. tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  205. return do_balance(tree);
  206. }
  207. static avl_node_t*
  208. avltree_insert(
  209. avl_node_t* tree,
  210. vmem_key_t key,
  211. page_t* page
  212. )
  213. {
  214. if (tree == NULL) {
  215. tree = make_avl_node(key, page);
  216. } else {
  217. if (key >= tree->key) {
  218. tree->right = avltree_insert(tree->right, key, page);
  219. } else {
  220. tree->left = avltree_insert(tree->left, key, page);
  221. }
  222. }
  223. tree = do_balance(tree);
  224. tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  225. return tree;
  226. }
  227. static avl_node_t*
  228. do_unlink(
  229. avl_node_t* tree
  230. )
  231. {
  232. avl_node_t* node;
  233. avl_node_t* end_node;
  234. node = unlink_end_node(tree->right, LEFT, &end_node);
  235. if (node) {
  236. tree->right = node;
  237. } else {
  238. node = unlink_end_node(tree->left, RIGHT, &end_node);
  239. if (node) tree->left = node;
  240. }
  241. if (node == NULL) {
  242. node = tree->right ? tree->right : tree->left;
  243. end_node = node;
  244. }
  245. if (end_node) {
  246. end_node->left = (tree->left != end_node) ? tree->left : end_node->left;
  247. end_node->right = (tree->right != end_node) ? tree->right : end_node->right;
  248. end_node->height = MAX(HEIGHT(end_node->left), HEIGHT(end_node->right)) + 1;
  249. }
  250. tree = end_node;
  251. return tree;
  252. }
  253. static avl_node_t*
  254. avltree_remove(
  255. avl_node_t* tree,
  256. avl_node_t** found_node,
  257. vmem_key_t key
  258. )
  259. {
  260. *found_node = NULL;
  261. if (tree == NULL) {
  262. DPRINT("failed to find key %d\n", (int)key);
  263. return NULL;
  264. }
  265. if (key == tree->key) {
  266. *found_node = tree;
  267. tree = do_unlink(tree);
  268. } else if (key > tree->key) {
  269. tree->right = avltree_remove(tree->right, found_node, key);
  270. } else {
  271. tree->left = avltree_remove(tree->left, found_node, key);
  272. }
  273. if (tree) tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  274. tree = do_balance(tree);
  275. return tree;
  276. }
  277. void
  278. avltree_free(
  279. avl_node_t* tree
  280. )
  281. {
  282. if (tree == NULL) return;
  283. if (tree->left == NULL && tree->right == NULL) {
  284. P_FREE(tree);
  285. return;
  286. }
  287. avltree_free(tree->left);
  288. tree->left = NULL;
  289. avltree_free(tree->right);
  290. tree->right = NULL;
  291. P_FREE(tree);
  292. }
  293. static avl_node_t*
  294. remove_approx_value(
  295. avl_node_t* tree,
  296. avl_node_t** found,
  297. vmem_key_t key
  298. )
  299. {
  300. *found = NULL;
  301. if (tree == NULL) {
  302. return NULL;
  303. }
  304. if (key == tree->key) {
  305. *found = tree;
  306. tree = do_unlink(tree);
  307. } else if (key > tree->key) {
  308. tree->right = remove_approx_value(tree->right, found, key);
  309. } else {
  310. tree->left = remove_approx_value(tree->left, found, key);
  311. if (*found == NULL) {
  312. *found = tree;
  313. tree = do_unlink(tree);
  314. }
  315. }
  316. if (tree) tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
  317. tree = do_balance(tree);
  318. return tree;
  319. }
  320. static void
  321. set_blocks_free(
  322. jpeg_mm_t *mm,
  323. int pageno,
  324. int npages
  325. )
  326. {
  327. int last_pageno = pageno + npages - 1;
  328. int i;
  329. page_t* page;
  330. page_t* last_page;
  331. ASSERT(npages);
  332. if (last_pageno >= mm->num_pages) {
  333. DPRINT("set_blocks_free: invalid last page number: %d\n", last_pageno);
  334. ASSERT(0);
  335. return;
  336. }
  337. for (i=pageno; i<=last_pageno; i++) {
  338. mm->page_list[i].used = 0;
  339. mm->page_list[i].alloc_pages = 0;
  340. mm->page_list[i].first_pageno = -1;
  341. }
  342. page = &mm->page_list[pageno];
  343. page->alloc_pages = npages;
  344. last_page = &mm->page_list[last_pageno];
  345. last_page->first_pageno = pageno;
  346. mm->free_tree = avltree_insert(mm->free_tree, MAKE_KEY(npages, pageno), page);
  347. }
  348. static void
  349. set_blocks_alloc(
  350. jpeg_mm_t *mm,
  351. int pageno,
  352. int npages
  353. )
  354. {
  355. int last_pageno = pageno + npages - 1;
  356. int i;
  357. page_t* page;
  358. page_t* last_page;
  359. if (last_pageno >= mm->num_pages) {
  360. DPRINT("set_blocks_free: invalid last page number: %d\n", last_pageno);
  361. ASSERT(0);
  362. return;
  363. }
  364. for (i=pageno; i<=last_pageno; i++) {
  365. mm->page_list[i].used = 1;
  366. mm->page_list[i].alloc_pages = 0;
  367. mm->page_list[i].first_pageno = -1;
  368. }
  369. page = &mm->page_list[pageno];
  370. page->alloc_pages = npages;
  371. last_page = &mm->page_list[last_pageno];
  372. last_page->first_pageno = pageno;
  373. mm->alloc_tree = avltree_insert(mm->alloc_tree, MAKE_KEY(page->addr, 0), page);
  374. }
  375. int
  376. jmem_init(
  377. jpeg_mm_t* mm,
  378. unsigned long addr,
  379. unsigned long size
  380. )
  381. {
  382. int i;
  383. mm->base_addr = (addr+(VMEM_PAGE_SIZE-1))&~(VMEM_PAGE_SIZE-1);
  384. mm->mem_size = size&~VMEM_PAGE_SIZE;
  385. mm->num_pages = mm->mem_size/VMEM_PAGE_SIZE;
  386. mm->page_list = (page_t*)P_ALLOC(mm->num_pages*sizeof(page_t));
  387. mm->free_tree = NULL;
  388. mm->alloc_tree = NULL;
  389. mm->free_page_count = mm->num_pages;
  390. mm->alloc_page_count = 0;
  391. for (i=0; i<mm->num_pages; i++) {
  392. mm->page_list[i].pageno = i;
  393. mm->page_list[i].addr = mm->base_addr + i*VMEM_PAGE_SIZE;
  394. mm->page_list[i].alloc_pages = 0;
  395. mm->page_list[i].used = 0;
  396. mm->page_list[i].first_pageno = -1;
  397. }
  398. set_blocks_free(mm, 0, mm->num_pages);
  399. return 0;
  400. }
  401. int
  402. jmem_exit(
  403. jpeg_mm_t* mm
  404. )
  405. {
  406. if (mm == NULL) {
  407. DPRINT("vmem_exit: invalid handle\n");
  408. return -1;
  409. }
  410. if (mm->free_tree) {
  411. avltree_free(mm->free_tree);
  412. mm->free_tree = NULL;
  413. }
  414. if (mm->alloc_tree) {
  415. avltree_free(mm->alloc_tree);
  416. mm->alloc_tree = NULL;
  417. }
  418. if (mm->page_list) {
  419. P_FREE(mm->page_list);
  420. mm->page_list = NULL;
  421. }
  422. return 0;
  423. }
  424. unsigned long
  425. jmem_alloc(
  426. jpeg_mm_t* mm,
  427. int size,
  428. unsigned long pid
  429. )
  430. {
  431. avl_node_t* node;
  432. page_t* free_page;
  433. int npages, free_size;
  434. int alloc_pageno;
  435. unsigned long ptr;
  436. if (mm == NULL) {
  437. printf("%s:%d: invalid handle\n", __FUNCTION__, __LINE__);
  438. return (unsigned long)-1;
  439. }
  440. if (size <= 0) return (unsigned long)-1;
  441. npages = (size + VMEM_PAGE_SIZE -1)/VMEM_PAGE_SIZE;
  442. mm->free_tree = remove_approx_value(mm->free_tree, &node, MAKE_KEY(npages, 0));
  443. if (node == NULL) {
  444. printf("%s:%d: Not found node?\n", __FUNCTION__, __LINE__);
  445. return (unsigned long)-1;
  446. }
  447. free_page = node->page;
  448. free_size = KEY_TO_VALUE(node->key);
  449. alloc_pageno = free_page->pageno;
  450. set_blocks_alloc(mm, alloc_pageno, npages);
  451. if (npages != free_size) {
  452. int free_pageno = alloc_pageno + npages;
  453. set_blocks_free(mm, free_pageno, (free_size-npages));
  454. }
  455. P_FREE(node);
  456. ptr = mm->page_list[alloc_pageno].addr;
  457. mm->alloc_page_count += npages;
  458. mm->free_page_count -= npages;
  459. return ptr;
  460. }
  461. int
  462. jmem_free(
  463. jpeg_mm_t* mm,
  464. unsigned long ptr,
  465. unsigned long pid
  466. )
  467. {
  468. unsigned long addr;
  469. avl_node_t* found;
  470. page_t* page;
  471. int pageno, prev_free_pageno, next_free_pageno;
  472. int prev_size, next_size;
  473. int merge_page_no, merge_page_size, free_page_size;
  474. if (mm == NULL) {
  475. DPRINT("vmem_free: invalid handle\n");
  476. return -1;
  477. }
  478. addr = ptr;
  479. mm->alloc_tree = avltree_remove(mm->alloc_tree, &found, MAKE_KEY(addr, 0));
  480. if (found == NULL) {
  481. DPRINT("vmem_free: 0x%08x not found\n", addr);
  482. return -1;
  483. }
  484. /* find previous free block */
  485. page = found->page;
  486. pageno = page->pageno;
  487. free_page_size = page->alloc_pages;
  488. prev_free_pageno = pageno-1;
  489. prev_size = -1;
  490. if (prev_free_pageno >= 0) {
  491. if (mm->page_list[prev_free_pageno].used == 0) {
  492. prev_free_pageno = mm->page_list[prev_free_pageno].first_pageno;
  493. prev_size = mm->page_list[prev_free_pageno].alloc_pages;
  494. }
  495. }
  496. /* find next free block */
  497. next_free_pageno = pageno + page->alloc_pages;
  498. next_free_pageno = (next_free_pageno == mm->num_pages) ? -1 : next_free_pageno;
  499. next_size = -1;
  500. if (next_free_pageno >= 0) {
  501. if (mm->page_list[next_free_pageno].used == 0) {
  502. next_size = mm->page_list[next_free_pageno].alloc_pages;
  503. }
  504. }
  505. P_FREE(found);
  506. /* merge */
  507. merge_page_no = page->pageno;
  508. merge_page_size = page->alloc_pages;
  509. if (prev_size >= 0) {
  510. mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(prev_size, prev_free_pageno));
  511. if (found == NULL) {
  512. ASSERT(0);
  513. return -1;
  514. }
  515. merge_page_no = found->page->pageno;
  516. merge_page_size += found->page->alloc_pages;
  517. P_FREE(found);
  518. }
  519. if (next_size >= 0) {
  520. mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(next_size, next_free_pageno));
  521. if (found == NULL) {
  522. ASSERT(0);
  523. return -1;
  524. }
  525. merge_page_size += found->page->alloc_pages;
  526. P_FREE(found);
  527. }
  528. page->alloc_pages = 0;
  529. page->first_pageno = -1;
  530. set_blocks_free(mm, merge_page_no, merge_page_size);
  531. mm->alloc_page_count -= free_page_size;
  532. mm->free_page_count += free_page_size;
  533. DPRINT("FREE: total(%d) alloc(%d) free(%d)\n", mm->num_pages, mm->alloc_page_count, mm->free_page_count);
  534. return 0;
  535. }
  536. int
  537. jmem_get_info(
  538. jpeg_mm_t* mm,
  539. jmem_info_t* info
  540. )
  541. {
  542. if (mm == NULL) {
  543. DPRINT("vmem_get_info: invalid handle\n");
  544. return -1;
  545. }
  546. if (info == NULL) {
  547. return -1;
  548. }
  549. info->total_pages = mm->num_pages;
  550. info->alloc_pages = mm->alloc_page_count;
  551. info->free_pages = mm->free_page_count;
  552. info->page_size = VMEM_PAGE_SIZE;
  553. return 0;
  554. }