123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660 |
- /*
- * Copyright (c) 2018, Chips&Media
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- * 1. Redistributions of source code must retain the above copyright notice, this
- * list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright notice,
- * this list of conditions and the following disclaimer in the documentation
- * and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
- * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include "mm.h"
- #ifdef MM_DEBUG
- #ifdef _MSC_VER
- #define DPRINT(_fmt, ...) printf(_fmt, __VA_ARGS__)
- #else
- #define DPRINT(_fmt, ...) printf(_fmt, args...)
- #endif
- #else
- #define DPRINT(_fmt, ...)
- #endif
- #define P_ALLOC(_x) malloc(_x)
- #define P_FREE(_x) free(_x)
- #define ASSERT(_exp) if (!(_exp)) { printf("ASSERT at %s:%d\n", __FILE__, __LINE__); while(1); }
- #define HEIGHT(_tree) (_tree==NULL ? -1 : _tree->height)
- #define MAX(_a, _b) (_a >= _b ? _a : _b)
- typedef enum {
- LEFT,
- RIGHT
- } rotation_dir_t;
- typedef struct avl_node_data_struct {
- int key;
- page_t* page;
- } avl_node_data_t;
- static avl_node_t*
- make_avl_node(
- vmem_key_t key,
- page_t* page
- )
- {
- avl_node_t* node = (avl_node_t*)P_ALLOC(sizeof(avl_node_t));
- if (node != NULL)
- {
- node->key = key;
- node->page = page;
- node->height = 0;
- node->left = NULL;
- node->right = NULL;
- }
- return node;
- }
- static int
- get_balance_factor(
- avl_node_t* tree
- )
- {
- int factor = 0;
- if (tree) {
- factor = HEIGHT(tree->right) - HEIGHT(tree->left);
- }
- return factor;
- }
- /*
- * Left Rotation
- *
- * A B
- * \ / \
- * B => A C
- * / \ \
- * D C D
- *
- */
- static avl_node_t*
- rotation_left(
- avl_node_t* tree
- )
- {
- avl_node_t* rchild;
- avl_node_t* lchild;
- if (tree == NULL) return NULL;
- rchild = tree->right;
- if (rchild == NULL) {
- return tree;
- }
- lchild = rchild->left;
- rchild->left = tree;
- tree->right = lchild;
- tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- rchild->height = MAX(HEIGHT(rchild->left), HEIGHT(rchild->right)) + 1;
- return rchild;
- }
- /*
- * Reft Rotation
- *
- * A B
- * \ / \
- * B => D A
- * / \ /
- * D C C
- *
- */
- static avl_node_t*
- rotation_right(
- avl_node_t* tree
- )
- {
- avl_node_t* rchild;
- avl_node_t* lchild;
- if (tree == NULL) return NULL;
- lchild = tree->left;
- if (lchild == NULL) return NULL;
- rchild = lchild->right;
- lchild->right = tree;
- tree->left = rchild;
- tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- lchild->height = MAX(HEIGHT(lchild->left), HEIGHT(lchild->right)) + 1;
- return lchild;
- }
- static avl_node_t*
- do_balance(
- avl_node_t* tree
- )
- {
- int bfactor = 0, child_bfactor; /* balancing factor */
- bfactor = get_balance_factor(tree);
- if (bfactor >= 2) {
- child_bfactor = get_balance_factor(tree->right);
- if (child_bfactor == 1 || child_bfactor == 0) {
- tree = rotation_left(tree);
- } else if (child_bfactor == -1) {
- tree->right = rotation_right(tree->right);
- tree = rotation_left(tree);
- } else {
- fprintf(stderr, "invalid balancing factor: %d\n", child_bfactor);
- ASSERT(0);
- return NULL;
- }
- } else if (bfactor <= -2) {
- child_bfactor = get_balance_factor(tree->left);
- if (child_bfactor == -1 || child_bfactor == 0) {
- tree = rotation_right(tree);
- } else if (child_bfactor == 1) {
- tree->left = rotation_left(tree->left);
- tree = rotation_right(tree);
- } else {
- fprintf(stderr, "invalid balancing factor: %d\n", child_bfactor);
- ASSERT(0);
- return NULL;
- }
- }
- return tree;
- }
- static avl_node_t*
- unlink_end_node(
- avl_node_t* tree,
- int dir,
- avl_node_t** found_node
- )
- {
- *found_node = NULL;
- if (tree == NULL) return NULL;
- if (dir == LEFT) {
- if (tree->left == NULL) {
- *found_node = tree;
- return NULL;
- }
- } else {
- if (tree->right == NULL) {
- *found_node = tree;
- return NULL;
- }
- }
- if (dir == LEFT) {
- tree->left = unlink_end_node(tree->left, LEFT, found_node);
- if (tree->left == NULL) {
- tree->left = (*found_node)->right;
- (*found_node)->left = NULL;
- (*found_node)->right = NULL;
- }
- } else {
- tree->right = unlink_end_node(tree->right, RIGHT, found_node);
- if (tree->right == NULL) {
- tree->right = (*found_node)->left;
- (*found_node)->left = NULL;
- (*found_node)->right = NULL;
- }
- }
- tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- return do_balance(tree);
- }
- static avl_node_t*
- avltree_insert(
- avl_node_t* tree,
- vmem_key_t key,
- page_t* page
- )
- {
- if (tree == NULL) {
- tree = make_avl_node(key, page);
- } else {
- if (key >= tree->key) {
- tree->right = avltree_insert(tree->right, key, page);
- } else {
- tree->left = avltree_insert(tree->left, key, page);
- }
- }
- tree = do_balance(tree);
- tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- return tree;
- }
- static avl_node_t*
- do_unlink(
- avl_node_t* tree
- )
- {
- avl_node_t* node;
- avl_node_t* end_node;
- node = unlink_end_node(tree->right, LEFT, &end_node);
- if (node) {
- tree->right = node;
- } else {
- node = unlink_end_node(tree->left, RIGHT, &end_node);
- if (node) tree->left = node;
- }
- if (node == NULL) {
- node = tree->right ? tree->right : tree->left;
- end_node = node;
- }
- if (end_node) {
- end_node->left = (tree->left != end_node) ? tree->left : end_node->left;
- end_node->right = (tree->right != end_node) ? tree->right : end_node->right;
- end_node->height = MAX(HEIGHT(end_node->left), HEIGHT(end_node->right)) + 1;
- }
- tree = end_node;
- return tree;
- }
- static avl_node_t*
- avltree_remove(
- avl_node_t* tree,
- avl_node_t** found_node,
- vmem_key_t key
- )
- {
- *found_node = NULL;
- if (tree == NULL) {
- DPRINT("failed to find key %d\n", (int)key);
- return NULL;
- }
- if (key == tree->key) {
- *found_node = tree;
- tree = do_unlink(tree);
- } else if (key > tree->key) {
- tree->right = avltree_remove(tree->right, found_node, key);
- } else {
- tree->left = avltree_remove(tree->left, found_node, key);
- }
- if (tree) tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- tree = do_balance(tree);
- return tree;
- }
- void
- avltree_free(
- avl_node_t* tree
- )
- {
- if (tree == NULL) return;
- if (tree->left == NULL && tree->right == NULL) {
- P_FREE(tree);
- return;
- }
- avltree_free(tree->left);
- tree->left = NULL;
- avltree_free(tree->right);
- tree->right = NULL;
- P_FREE(tree);
- }
- static avl_node_t*
- remove_approx_value(
- avl_node_t* tree,
- avl_node_t** found,
- vmem_key_t key
- )
- {
- *found = NULL;
- if (tree == NULL) {
- return NULL;
- }
- if (key == tree->key) {
- *found = tree;
- tree = do_unlink(tree);
- } else if (key > tree->key) {
- tree->right = remove_approx_value(tree->right, found, key);
- } else {
- tree->left = remove_approx_value(tree->left, found, key);
- if (*found == NULL) {
- *found = tree;
- tree = do_unlink(tree);
- }
- }
- if (tree) tree->height = MAX(HEIGHT(tree->left), HEIGHT(tree->right)) + 1;
- tree = do_balance(tree);
- return tree;
- }
- static void
- set_blocks_free(
- jpeg_mm_t *mm,
- int pageno,
- int npages
- )
- {
- int last_pageno = pageno + npages - 1;
- int i;
- page_t* page;
- page_t* last_page;
- ASSERT(npages);
- if (last_pageno >= mm->num_pages) {
- DPRINT("set_blocks_free: invalid last page number: %d\n", last_pageno);
- ASSERT(0);
- return;
- }
- for (i=pageno; i<=last_pageno; i++) {
- mm->page_list[i].used = 0;
- mm->page_list[i].alloc_pages = 0;
- mm->page_list[i].first_pageno = -1;
- }
- page = &mm->page_list[pageno];
- page->alloc_pages = npages;
- last_page = &mm->page_list[last_pageno];
- last_page->first_pageno = pageno;
- mm->free_tree = avltree_insert(mm->free_tree, MAKE_KEY(npages, pageno), page);
- }
- static void
- set_blocks_alloc(
- jpeg_mm_t *mm,
- int pageno,
- int npages
- )
- {
- int last_pageno = pageno + npages - 1;
- int i;
- page_t* page;
- page_t* last_page;
- if (last_pageno >= mm->num_pages) {
- DPRINT("set_blocks_free: invalid last page number: %d\n", last_pageno);
- ASSERT(0);
- return;
- }
- for (i=pageno; i<=last_pageno; i++) {
- mm->page_list[i].used = 1;
- mm->page_list[i].alloc_pages = 0;
- mm->page_list[i].first_pageno = -1;
- }
- page = &mm->page_list[pageno];
- page->alloc_pages = npages;
- last_page = &mm->page_list[last_pageno];
- last_page->first_pageno = pageno;
- mm->alloc_tree = avltree_insert(mm->alloc_tree, MAKE_KEY(page->addr, 0), page);
- }
- int
- jmem_init(
- jpeg_mm_t* mm,
- unsigned long addr,
- unsigned long size
- )
- {
- int i;
- mm->base_addr = (addr+(VMEM_PAGE_SIZE-1))&~(VMEM_PAGE_SIZE-1);
- mm->mem_size = size&~VMEM_PAGE_SIZE;
- mm->num_pages = mm->mem_size/VMEM_PAGE_SIZE;
- mm->page_list = (page_t*)P_ALLOC(mm->num_pages*sizeof(page_t));
- mm->free_tree = NULL;
- mm->alloc_tree = NULL;
- mm->free_page_count = mm->num_pages;
- mm->alloc_page_count = 0;
- for (i=0; i<mm->num_pages; i++) {
- mm->page_list[i].pageno = i;
- mm->page_list[i].addr = mm->base_addr + i*VMEM_PAGE_SIZE;
- mm->page_list[i].alloc_pages = 0;
- mm->page_list[i].used = 0;
- mm->page_list[i].first_pageno = -1;
- }
- set_blocks_free(mm, 0, mm->num_pages);
- return 0;
- }
- int
- jmem_exit(
- jpeg_mm_t* mm
- )
- {
- if (mm == NULL) {
- DPRINT("vmem_exit: invalid handle\n");
- return -1;
- }
- if (mm->free_tree) {
- avltree_free(mm->free_tree);
- mm->free_tree = NULL;
- }
- if (mm->alloc_tree) {
- avltree_free(mm->alloc_tree);
- mm->alloc_tree = NULL;
- }
- if (mm->page_list) {
- P_FREE(mm->page_list);
- mm->page_list = NULL;
- }
- return 0;
- }
- unsigned long
- jmem_alloc(
- jpeg_mm_t* mm,
- int size,
- unsigned long pid
- )
- {
- avl_node_t* node;
- page_t* free_page;
- int npages, free_size;
- int alloc_pageno;
- unsigned long ptr;
- if (mm == NULL) {
- printf("%s:%d: invalid handle\n", __FUNCTION__, __LINE__);
- return (unsigned long)-1;
- }
- if (size <= 0) return (unsigned long)-1;
- npages = (size + VMEM_PAGE_SIZE -1)/VMEM_PAGE_SIZE;
- mm->free_tree = remove_approx_value(mm->free_tree, &node, MAKE_KEY(npages, 0));
- if (node == NULL) {
- printf("%s:%d: Not found node?\n", __FUNCTION__, __LINE__);
- return (unsigned long)-1;
- }
- free_page = node->page;
- free_size = KEY_TO_VALUE(node->key);
- alloc_pageno = free_page->pageno;
- set_blocks_alloc(mm, alloc_pageno, npages);
- if (npages != free_size) {
- int free_pageno = alloc_pageno + npages;
- set_blocks_free(mm, free_pageno, (free_size-npages));
- }
- P_FREE(node);
- ptr = mm->page_list[alloc_pageno].addr;
- mm->alloc_page_count += npages;
- mm->free_page_count -= npages;
- return ptr;
- }
- int
- jmem_free(
- jpeg_mm_t* mm,
- unsigned long ptr,
- unsigned long pid
- )
- {
- unsigned long addr;
- avl_node_t* found;
- page_t* page;
- int pageno, prev_free_pageno, next_free_pageno;
- int prev_size, next_size;
- int merge_page_no, merge_page_size, free_page_size;
- if (mm == NULL) {
- DPRINT("vmem_free: invalid handle\n");
- return -1;
- }
- addr = ptr;
- mm->alloc_tree = avltree_remove(mm->alloc_tree, &found, MAKE_KEY(addr, 0));
- if (found == NULL) {
- DPRINT("vmem_free: 0x%08x not found\n", addr);
- return -1;
- }
- /* find previous free block */
- page = found->page;
- pageno = page->pageno;
- free_page_size = page->alloc_pages;
- prev_free_pageno = pageno-1;
- prev_size = -1;
- if (prev_free_pageno >= 0) {
- if (mm->page_list[prev_free_pageno].used == 0) {
- prev_free_pageno = mm->page_list[prev_free_pageno].first_pageno;
- prev_size = mm->page_list[prev_free_pageno].alloc_pages;
- }
- }
- /* find next free block */
- next_free_pageno = pageno + page->alloc_pages;
- next_free_pageno = (next_free_pageno == mm->num_pages) ? -1 : next_free_pageno;
- next_size = -1;
- if (next_free_pageno >= 0) {
- if (mm->page_list[next_free_pageno].used == 0) {
- next_size = mm->page_list[next_free_pageno].alloc_pages;
- }
- }
- P_FREE(found);
- /* merge */
- merge_page_no = page->pageno;
- merge_page_size = page->alloc_pages;
- if (prev_size >= 0) {
- mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(prev_size, prev_free_pageno));
- if (found == NULL) {
- ASSERT(0);
- return -1;
- }
- merge_page_no = found->page->pageno;
- merge_page_size += found->page->alloc_pages;
- P_FREE(found);
- }
- if (next_size >= 0) {
- mm->free_tree = avltree_remove(mm->free_tree, &found, MAKE_KEY(next_size, next_free_pageno));
- if (found == NULL) {
- ASSERT(0);
- return -1;
- }
- merge_page_size += found->page->alloc_pages;
- P_FREE(found);
- }
- page->alloc_pages = 0;
- page->first_pageno = -1;
- set_blocks_free(mm, merge_page_no, merge_page_size);
- mm->alloc_page_count -= free_page_size;
- mm->free_page_count += free_page_size;
- DPRINT("FREE: total(%d) alloc(%d) free(%d)\n", mm->num_pages, mm->alloc_page_count, mm->free_page_count);
- return 0;
- }
- int
- jmem_get_info(
- jpeg_mm_t* mm,
- jmem_info_t* info
- )
- {
- if (mm == NULL) {
- DPRINT("vmem_get_info: invalid handle\n");
- return -1;
- }
- if (info == NULL) {
- return -1;
- }
- info->total_pages = mm->num_pages;
- info->alloc_pages = mm->alloc_page_count;
- info->free_pages = mm->free_page_count;
- info->page_size = VMEM_PAGE_SIZE;
- return 0;
- }
|