mm.c 15 KB

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