1474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* 2474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * 4474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Use of this source code is governed by a BSD-style license 5474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * that can be found in the LICENSE file in the root of the source 6474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * tree. An additional intellectual property rights grant can be found 7474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * in the file PATENTS. All contributing project authors may 8474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * be found in the AUTHORS file in the root of the source tree. 9474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org */ 10474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 12474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* This code is in the public domain. 13474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** Version: 1.1 Author: Walt Karas 14474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 15474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 168b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 178b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#define VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 18474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 19474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef __uClinux__ 20474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org# include <lddk.h> 21474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 22474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 23474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include "heapmm.h" 24474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 25474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define U(BASE) HMM_UNIQUE(BASE) 26474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 27474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Mask of high bit of variable of size_bau type. */ 28474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define HIGH_BIT_BAU_SIZE \ 296fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((U(size_bau)) ~ (((U(size_bau)) ~ (U(size_bau)) 0) >> 1)) 30474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 31474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Add a given number of AAUs to pointer. */ 32474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AAUS_FORWARD(PTR, AAU_OFFSET) \ 336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (((char *) (PTR)) + ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT))) 34474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 35474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Subtract a given number of AAUs from pointer. */ 36474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AAUS_BACKWARD(PTR, AAU_OFFSET) \ 376fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (((char *) (PTR)) - ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT))) 38474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 39474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Add a given number of BAUs to a pointer. */ 40474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define BAUS_FORWARD(PTR, BAU_OFFSET) \ 416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AAUS_FORWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) 42474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 43474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Subtract a given number of BAUs to a pointer. */ 44474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define BAUS_BACKWARD(PTR, BAU_OFFSET) \ 456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AAUS_BACKWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) 46474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgtypedef struct head_struct { 486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Sizes in Block Alignment Units. */ 496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org HMM_UNIQUE(size_bau) previous_block_size, block_size; 50474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 51474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orghead_record; 52474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgtypedef struct ptr_struct { 546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org struct ptr_struct *self, *prev, *next; 55474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 56474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgptr_record; 57474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 58474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Divide and round up any fraction to the next whole number. */ 59474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define DIV_ROUND_UP(NUMER, DENOM) (((NUMER) + (DENOM) - 1) / (DENOM)) 60474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 61474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Number of AAUs in a block head. */ 62474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define HEAD_AAUS DIV_ROUND_UP(sizeof(head_record), HMM_ADDR_ALIGN_UNIT) 63474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 64474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Number of AAUs in a block pointer record. */ 65474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define PTR_RECORD_AAUS DIV_ROUND_UP(sizeof(ptr_record), HMM_ADDR_ALIGN_UNIT) 66474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 67474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Number of BAUs in a dummy end record (at end of chunk). */ 68474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define DUMMY_END_BLOCK_BAUS DIV_ROUND_UP(HEAD_AAUS, HMM_BLOCK_ALIGN_UNIT) 69474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 70474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Minimum number of BAUs in a block (allowing room for the pointer record. */ 71474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define MIN_BLOCK_BAUS \ 726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org DIV_ROUND_UP(HEAD_AAUS + PTR_RECORD_AAUS, HMM_BLOCK_ALIGN_UNIT) 73474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 74474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Return number of BAUs in block (masking off high bit containing block 75474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** status). */ 76474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define BLOCK_BAUS(HEAD_PTR) \ 776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (((head_record *) (HEAD_PTR))->block_size & ~HIGH_BIT_BAU_SIZE) 78474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 79474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Return number of BAUs in previous block (masking off high bit containing 80474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** block status). */ 81474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define PREV_BLOCK_BAUS(HEAD_PTR) \ 826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (((head_record *) (HEAD_PTR))->previous_block_size & ~HIGH_BIT_BAU_SIZE) 83474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 84474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Set number of BAUs in previous block, preserving high bit containing 85474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** block status. */ 86474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define SET_PREV_BLOCK_BAUS(HEAD_PTR, N_BAUS) \ 876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h_ptr->previous_block_size &= HIGH_BIT_BAU_SIZE; \ 896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h_ptr->previous_block_size |= (N_BAUS); } 90474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 91474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Convert pointer to pointer record of block to pointer to block's head 92474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** record. */ 93474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define PTR_REC_TO_HEAD(PTR_REC_PTR) \ 946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((head_record *) AAUS_BACKWARD(PTR_REC_PTR, HEAD_AAUS)) 95474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 96474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Convert pointer to block head to pointer to block's pointer record. */ 97474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define HEAD_TO_PTR_REC(HEAD_PTR) \ 986fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((ptr_record *) AAUS_FORWARD(HEAD_PTR, HEAD_AAUS)) 99474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 100474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Returns non-zero if block is allocated. */ 101474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define IS_BLOCK_ALLOCATED(HEAD_PTR) \ 1026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (((((head_record *) (HEAD_PTR))->block_size | \ 1036fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((head_record *) (HEAD_PTR))->previous_block_size) & \ 1046fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org HIGH_BIT_BAU_SIZE) == 0) 105474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 106474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define MARK_BLOCK_ALLOCATED(HEAD_PTR) \ 1076fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 1086fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h_ptr->block_size &= ~HIGH_BIT_BAU_SIZE; \ 1096fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h_ptr->previous_block_size &= ~HIGH_BIT_BAU_SIZE; } 110474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 111474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Mark a block as free when it is not the first block in a bin (and 112474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** therefore not a node in the AVL tree). */ 113474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(HEAD_PTR) \ 1146fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 1156fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org h_ptr->block_size |= HIGH_BIT_BAU_SIZE; } 116474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 117474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Prototypes for internal functions implemented in one file and called in 118474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** another. 119474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 120474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 121474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgvoid U(into_free_collection)(U(descriptor) *desc, head_record *head_ptr); 122474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 123474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgvoid U(out_of_free_collection)(U(descriptor) *desc, head_record *head_ptr); 124474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 125474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgvoid *U(alloc_from_bin)( 1266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org U(descriptor) *desc, ptr_record *bin_front_ptr, U(size_bau) n_baus); 127474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 128474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 129474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 130474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Simply contains a reference to the HMM_AUDIT_FAIL macro and a 131474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** dummy return. */ 132474eb7536515fb785e925cc9375d22817c416851hclam@chromium.orgint U(audit_block_fail_dummy_return)(void); 133474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 134474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 135474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Auditing a block consists of checking that the size in its head 136474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** matches the previous block size in the head of the next block. */ 137474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AUDIT_BLOCK_AS_EXPR(HEAD_PTR) \ 1386fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ((BLOCK_BAUS(HEAD_PTR) == \ 1396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org PREV_BLOCK_BAUS(BAUS_FORWARD(HEAD_PTR, BLOCK_BAUS(HEAD_PTR)))) ? \ 1406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 0 : U(audit_block_fail_dummy_return)()) 141474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 142474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AUDIT_BLOCK(HEAD_PTR) \ 1436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org { void *h_ptr = (HEAD_PTR); AUDIT_BLOCK_AS_EXPR(h_ptr); } 144474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 145474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 146474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 147474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* Interface to AVL tree generic package instantiation. */ 148474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 149474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AVL_UNIQUE(BASE) U(avl_ ## BASE) 150474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 151474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AVL_HANDLE ptr_record * 152474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 153474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AVL_KEY U(size_bau) 154474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 155474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#define AVL_MAX_DEPTH 64 156474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 157474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include "cavl_if.h" 158474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 1598b26fe55f3e4daa2311dbd2d95e8ac2b4e080685johannkoenig@chromium.org#endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 160