jmm.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647
  1. /* SPDX-License-Identifier: LGPL-2.1 OR BSD-3-Clause */
  2. #ifndef __CNM_JPU_MM_H__
  3. #define __CNM_JPU_MM_H__
  4. typedef unsigned long long jmem_key_t;
  5. #define JMEM_PAGE_SIZE (16*1024)
  6. #define MAKE_KEY(_a, _b) (((jmem_key_t)_a)<<32 | _b)
  7. #define KEY_TO_VALUE(_key) (_key>>32)
  8. typedef struct page_struct {
  9. int pageno;
  10. unsigned long addr;
  11. int used;
  12. int alloc_pages;
  13. int first_pageno;
  14. } page_t;
  15. typedef struct avl_node_struct {
  16. jmem_key_t key;
  17. int height;
  18. page_t* page;
  19. struct avl_node_struct* left;
  20. struct avl_node_struct* right;
  21. } avl_node_t;
  22. typedef struct _jpu_mm_struct {
  23. avl_node_t* free_tree;
  24. avl_node_t* alloc_tree;
  25. page_t* page_list;
  26. int num_pages;
  27. unsigned long base_addr;
  28. unsigned long mem_size;
  29. int free_page_count;
  30. int alloc_page_count;
  31. } jpu_mm_t;
  32. #define VMEM_P_ALLOC(_x) kmalloc(_x, GFP_KERNEL)
  33. #define VMEM_P_FREE(_x) kfree(_x)
  34. #define VMEM_ASSERT(_exp) if (!(_exp)) { printk(KERN_INFO "VMEM_ASSERT at %s:%d\n", __FILE__, __LINE__); /*while(1);*/ }
  35. #define VMEM_HEIGHT(_tree) (_tree==NULL ? -1 : _tree->height)
  36. #define MAX(_a, _b) (_a >= _b ? _a : _b)
  37. typedef enum {
  38. LEFT,
  39. RIGHT
  40. } rotation_dir_t;
  41. typedef struct avl_node_data_struct {
  42. int key;
  43. page_t* page;
  44. } avl_node_data_t;
  45. static avl_node_t*
  46. make_avl_node(
  47. jmem_key_t key,
  48. page_t* page
  49. )
  50. {
  51. avl_node_t* node = (avl_node_t*)VMEM_P_ALLOC(sizeof(avl_node_t));
  52. node->key = key;
  53. node->page = page;
  54. node->height = 0;
  55. node->left = NULL;
  56. node->right = NULL;
  57. return node;
  58. }
  59. static int
  60. get_balance_factor(
  61. avl_node_t* tree
  62. )
  63. {
  64. int factor = 0;
  65. if (tree) {
  66. factor = VMEM_HEIGHT(tree->right) - VMEM_HEIGHT(tree->left);
  67. }
  68. return factor;
  69. }
  70. /*
  71. * Left Rotation
  72. *
  73. * A B
  74. * \ / \
  75. * B => A C
  76. * / \ \
  77. * D C D
  78. *
  79. */
  80. static avl_node_t*
  81. rotation_left(
  82. avl_node_t* tree
  83. )
  84. {
  85. avl_node_t* rchild;
  86. avl_node_t* lchild;
  87. if (tree == NULL) return NULL;
  88. rchild = tree->right;
  89. if (rchild == NULL) {
  90. return tree;
  91. }
  92. lchild = rchild->left;
  93. rchild->left = tree;
  94. tree->right = lchild;
  95. tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  96. rchild->height = MAX(VMEM_HEIGHT(rchild->left), VMEM_HEIGHT(rchild->right)) + 1;
  97. return rchild;
  98. }
  99. /*
  100. * Reft Rotation
  101. *
  102. * A B
  103. * \ / \
  104. * B => D A
  105. * / \ /
  106. * D C C
  107. *
  108. */
  109. static avl_node_t*
  110. rotation_right(
  111. avl_node_t* tree
  112. )
  113. {
  114. avl_node_t* rchild;
  115. avl_node_t* lchild;
  116. if (tree == NULL) return NULL;
  117. lchild = tree->left;
  118. if (lchild == NULL) return NULL;
  119. rchild = lchild->right;
  120. lchild->right = tree;
  121. tree->left = rchild;
  122. tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  123. lchild->height = MAX(VMEM_HEIGHT(lchild->left), VMEM_HEIGHT(lchild->right)) + 1;
  124. return lchild;
  125. }
  126. static avl_node_t*
  127. do_balance(
  128. avl_node_t* tree
  129. )
  130. {
  131. int bfactor = 0, child_bfactor; /* balancing factor */
  132. bfactor = get_balance_factor(tree);
  133. if (bfactor >= 2) {
  134. child_bfactor = get_balance_factor(tree->right);
  135. if (child_bfactor == 1 || child_bfactor == 0) {
  136. tree = rotation_left(tree);
  137. } else if (child_bfactor == -1) {
  138. tree->right = rotation_right(tree->right);
  139. tree = rotation_left(tree);
  140. } else {
  141. printk(KERN_INFO "invalid balancing factor: %d\n", child_bfactor);
  142. VMEM_ASSERT(0);
  143. return NULL;
  144. }
  145. } else if (bfactor <= -2) {
  146. child_bfactor = get_balance_factor(tree->left);
  147. if (child_bfactor == -1 || child_bfactor == 0) {
  148. tree = rotation_right(tree);
  149. } else if (child_bfactor == 1) {
  150. tree->left = rotation_left(tree->left);
  151. tree = rotation_right(tree);
  152. } else {
  153. printk(KERN_INFO "invalid balancing factor: %d\n", child_bfactor);
  154. VMEM_ASSERT(0);
  155. return NULL;
  156. }
  157. }
  158. return tree;
  159. }
  160. static avl_node_t*
  161. unlink_end_node(
  162. avl_node_t* tree,
  163. int dir,
  164. avl_node_t** found_node
  165. )
  166. {
  167. avl_node_t* node;
  168. *found_node = NULL;
  169. if (tree == NULL) return NULL;
  170. if (dir == LEFT) {
  171. if (tree->left == NULL) {
  172. *found_node = tree;
  173. return NULL;
  174. }
  175. } else {
  176. if (tree->right == NULL) {
  177. *found_node = tree;
  178. return NULL;
  179. }
  180. }
  181. if (dir == LEFT) {
  182. node = tree->left;
  183. tree->left = unlink_end_node(tree->left, LEFT, found_node);
  184. if (tree->left == NULL) {
  185. tree->left = (*found_node)->right;
  186. (*found_node)->left = NULL;
  187. (*found_node)->right = NULL;
  188. }
  189. } else {
  190. node = tree->right;
  191. tree->right = unlink_end_node(tree->right, RIGHT, found_node);
  192. if (tree->right == NULL) {
  193. tree->right = (*found_node)->left;
  194. (*found_node)->left = NULL;
  195. (*found_node)->right = NULL;
  196. }
  197. }
  198. tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  199. return do_balance(tree);
  200. }
  201. static avl_node_t*
  202. avltree_insert(
  203. avl_node_t* tree,
  204. jmem_key_t key,
  205. page_t* page
  206. )
  207. {
  208. if (tree == NULL) {
  209. tree = make_avl_node(key, page);
  210. } else {
  211. if (key >= tree->key) {
  212. tree->right = avltree_insert(tree->right, key, page);
  213. } else {
  214. tree->left = avltree_insert(tree->left, key, page);
  215. }
  216. }
  217. tree = do_balance(tree);
  218. tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  219. return tree;
  220. }
  221. static avl_node_t*
  222. do_unlink(
  223. avl_node_t* tree
  224. )
  225. {
  226. avl_node_t* node;
  227. avl_node_t* end_node;
  228. node = unlink_end_node(tree->right, LEFT, &end_node);
  229. if (node) {
  230. tree->right = node;
  231. } else {
  232. node = unlink_end_node(tree->left, RIGHT, &end_node);
  233. if (node) tree->left = node;
  234. }
  235. if (node == NULL) {
  236. node = tree->right ? tree->right : tree->left;
  237. end_node = node;
  238. }
  239. if (end_node) {
  240. end_node->left = (tree->left != end_node) ? tree->left : end_node->left;
  241. end_node->right = (tree->right != end_node) ? tree->right : end_node->right;
  242. end_node->height = MAX(VMEM_HEIGHT(end_node->left), VMEM_HEIGHT(end_node->right)) + 1;
  243. }
  244. tree = end_node;
  245. return tree;
  246. }
  247. static avl_node_t*
  248. avltree_remove(
  249. avl_node_t* tree,
  250. avl_node_t** found_node,
  251. jmem_key_t key
  252. )
  253. {
  254. *found_node = NULL;
  255. if (tree == NULL) {
  256. printk(KERN_INFO "failed to find key %d\n", (int)key);
  257. return NULL;
  258. }
  259. if (key == tree->key) {
  260. *found_node = tree;
  261. tree = do_unlink(tree);
  262. } else if (key > tree->key) {
  263. tree->right = avltree_remove(tree->right, found_node, key);
  264. } else {
  265. tree->left = avltree_remove(tree->left, found_node, key);
  266. }
  267. if (tree) tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  268. tree = do_balance(tree);
  269. return tree;
  270. }
  271. void
  272. avltree_free(
  273. avl_node_t* tree
  274. )
  275. {
  276. if (tree == NULL) return;
  277. if (tree->left == NULL && tree->right == NULL) {
  278. VMEM_P_FREE(tree);
  279. return;
  280. }
  281. avltree_free(tree->left);
  282. tree->left = NULL;
  283. avltree_free(tree->right);
  284. tree->right = NULL;
  285. }
  286. static avl_node_t*
  287. remove_approx_value(
  288. avl_node_t* tree,
  289. avl_node_t** found,
  290. jmem_key_t key
  291. )
  292. {
  293. *found = NULL;
  294. if (tree == NULL) {
  295. return NULL;
  296. }
  297. if (key == tree->key) {
  298. *found = tree;
  299. tree = do_unlink(tree);
  300. } else if (key > tree->key) {
  301. tree->right = remove_approx_value(tree->right, found, key);
  302. } else {
  303. tree->left = remove_approx_value(tree->left, found, key);
  304. if (*found == NULL) {
  305. *found = tree;
  306. tree = do_unlink(tree);
  307. }
  308. }
  309. if (tree) tree->height = MAX(VMEM_HEIGHT(tree->left), VMEM_HEIGHT(tree->right)) + 1;
  310. tree = do_balance(tree);
  311. return tree;
  312. }
  313. static void
  314. set_blocks_free(
  315. jpu_mm_t *mm,
  316. int pageno,
  317. int npages
  318. )
  319. {
  320. int last_pageno = pageno + npages - 1;
  321. int i;
  322. page_t* page;
  323. page_t* last_page;
  324. VMEM_ASSERT(npages);
  325. if (last_pageno >= mm->num_pages) {
  326. printk(KERN_INFO "set_blocks_free: invalid last page number: %d\n", last_pageno);
  327. VMEM_ASSERT(0);
  328. return;
  329. }
  330. for (i=pageno; i<=last_pageno; i++) {
  331. mm->page_list[i].used = 0;
  332. mm->page_list[i].alloc_pages = 0;
  333. mm->page_list[i].first_pageno = -1;
  334. }
  335. page = &mm->page_list[pageno];
  336. page->alloc_pages = npages;
  337. last_page = &mm->page_list[last_pageno];
  338. last_page->first_pageno = pageno;
  339. mm->free_tree = avltree_insert(mm->free_tree, MAKE_KEY(npages, pageno), page);
  340. }
  341. static void
  342. set_blocks_alloc(
  343. jpu_mm_t *mm,
  344. int pageno,
  345. int npages
  346. )
  347. {
  348. int last_pageno = pageno + npages - 1;
  349. int i;
  350. page_t* page;
  351. page_t* last_page;
  352. if (last_pageno >= mm->num_pages) {
  353. printk(KERN_INFO "set_blocks_free: invalid last page number: %d\n", last_pageno);
  354. VMEM_ASSERT(0);
  355. return;
  356. }
  357. for (i=pageno; i<=last_pageno; i++) {
  358. mm->page_list[i].used = 1;
  359. mm->page_list[i].alloc_pages = 0;
  360. mm->page_list[i].first_pageno = -1;
  361. }
  362. page = &mm->page_list[pageno];
  363. page->alloc_pages = npages;
  364. last_page = &mm->page_list[last_pageno];
  365. last_page->first_pageno = pageno;
  366. mm->alloc_tree = avltree_insert(mm->alloc_tree, MAKE_KEY(page->addr, 0), page);
  367. }
  368. int
  369. jmem_init(
  370. jpu_mm_t* mm,
  371. unsigned long addr,
  372. unsigned long size
  373. )
  374. {
  375. int i;
  376. mm->base_addr = (addr+(JMEM_PAGE_SIZE-1))&~(JMEM_PAGE_SIZE-1);
  377. mm->mem_size = size&~JMEM_PAGE_SIZE;
  378. mm->num_pages = mm->mem_size/JMEM_PAGE_SIZE;
  379. mm->page_list = (page_t*)VMEM_P_ALLOC(mm->num_pages*sizeof(page_t));
  380. mm->free_tree = NULL;
  381. mm->alloc_tree = NULL;
  382. mm->free_page_count = mm->num_pages;
  383. mm->alloc_page_count = 0;
  384. for (i=0; i<mm->num_pages; i++) {
  385. mm->page_list[i].pageno = i;
  386. mm->page_list[i].addr = mm->base_addr + i*JMEM_PAGE_SIZE;
  387. mm->page_list[i].alloc_pages = 0;
  388. mm->page_list[i].used = 0;
  389. mm->page_list[i].first_pageno = -1;
  390. }
  391. set_blocks_free(mm, 0, mm->num_pages);
  392. return 0;
  393. }
  394. int
  395. jmem_exit(
  396. jpu_mm_t* mm
  397. )
  398. {
  399. if (mm == NULL) {
  400. printk(KERN_INFO "vmem_exit: invalid handle\n");
  401. return -1;
  402. }
  403. if (mm->free_tree) {
  404. avltree_free(mm->free_tree);
  405. }
  406. if (mm->alloc_tree) {
  407. avltree_free(mm->alloc_tree);
  408. }
  409. VMEM_P_FREE(mm->page_list);
  410. mm->base_addr = 0;
  411. mm->mem_size = 0;
  412. mm->num_pages = 0;
  413. mm->page_list = NULL;
  414. mm->free_tree = NULL;
  415. mm->alloc_tree = NULL;
  416. mm->free_page_count = 0;
  417. mm->alloc_page_count = 0;
  418. return 0;
  419. }
  420. unsigned long
  421. jmem_alloc(
  422. jpu_mm_t* mm,
  423. int size,
  424. unsigned long pid
  425. )
  426. {
  427. avl_node_t* node;
  428. page_t* free_page;
  429. int npages, free_size;
  430. int alloc_pageno;
  431. unsigned long ptr;
  432. if (mm == NULL) {
  433. printk(KERN_INFO "vmem_alloc: invalid handle\n");
  434. return -1;
  435. }
  436. if (size <= 0) return -1;
  437. npages = (size + JMEM_PAGE_SIZE -1)/JMEM_PAGE_SIZE;
  438. mm->free_tree = remove_approx_value(mm->free_tree, &node, MAKE_KEY(npages, 0));
  439. if (node == NULL) {
  440. return -1;
  441. }
  442. free_page = node->page;
  443. free_size = KEY_TO_VALUE(node->key);
  444. alloc_pageno = free_page->pageno;
  445. set_blocks_alloc(mm, alloc_pageno, npages);
  446. if (npages != free_size) {
  447. int free_pageno = alloc_pageno + npages;
  448. set_blocks_free(mm, free_pageno, (free_size-npages));
  449. }
  450. VMEM_P_FREE(node);
  451. ptr = mm->page_list[alloc_pageno].addr;
  452. mm->alloc_page_count += npages;
  453. mm->free_page_count -= npages;
  454. return ptr;
  455. }
  456. int
  457. jmem_free(
  458. jpu_mm_t* mm,
  459. unsigned long ptr,
  460. unsigned long pid
  461. )
  462. {
  463. unsigned long addr;
  464. avl_node_t* found;
  465. page_t* page;
  466. int pageno, prev_free_pageno, next_free_pageno;
  467. int prev_size, next_size;
  468. int merge_page_no, merge_page_size, free_page_size;
  469. if (mm == NULL) {
  470. printk(KERN_INFO "vmem_free: invalid handle\n");
  471. return -1;
  472. }
  473. addr = ptr;
  474. mm->alloc_tree = avltree_remove(mm->alloc_tree, &found, MAKE_KEY(addr, 0));
  475. if (found == NULL) {
  476. printk(KERN_INFO "vmem_free: 0x%08x not found\n", (int)addr);
  477. VMEM_ASSERT(0);
  478. return -1;
  479. }
  480. /* find previous free block */
  481. page = found->page;
  482. pageno = page->pageno;
  483. free_page_size = page->alloc_pages;
  484. prev_free_pageno = pageno-1;
  485. prev_size = -1;
  486. if (prev_free_pageno >= 0) {
  487. if (mm->page_list[prev_free_pageno].used == 0) {
  488. prev_free_pageno = mm->page_list[prev_free_pageno].first_pageno;
  489. prev_size = mm->page_list[prev_free_pageno].alloc_pages;
  490. }
  491. }
  492. /* find next free block */
  493. next_free_pageno = pageno + page->alloc_pages;
  494. next_free_pageno = (next_free_pageno == mm->num_pages) ? -1 : next_free_pageno;
  495. next_size = -1;
  496. if (next_free_pageno >= 0) {
  497. if (mm->page_list[next_free_pageno].used == 0) {
  498. next_size = mm->page_list[next_free_pageno].alloc_pages;
  499. }
  500. }
  501. VMEM_P_FREE(found);
  502. /* merge */
  503. merge_page_no = page->pageno;
  504. merge_page_size = page->alloc_pages;
  505. if (prev_size >= 0) {
  506. mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(prev_size, prev_free_pageno));
  507. if (found == NULL) {
  508. VMEM_ASSERT(0);
  509. return -1;
  510. }
  511. merge_page_no = found->page->pageno;
  512. merge_page_size += found->page->alloc_pages;
  513. VMEM_P_FREE(found);
  514. }
  515. if (next_size >= 0) {
  516. mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(next_size, next_free_pageno));
  517. if (found == NULL) {
  518. VMEM_ASSERT(0);
  519. return -1;
  520. }
  521. merge_page_size += found->page->alloc_pages;
  522. VMEM_P_FREE(found);
  523. }
  524. page->alloc_pages = 0;
  525. page->first_pageno = -1;
  526. set_blocks_free(mm, merge_page_no, merge_page_size);
  527. mm->alloc_page_count -= free_page_size;
  528. mm->free_page_count += free_page_size;
  529. return 0;
  530. }
  531. #endif /* __CNM_JPU_MM_H__ */