1 /* 2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 12 /* This code is in the public domain. 13 ** Version: 1.1 Author: Walt Karas 14 */ 15 16 #ifndef VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 17 #define VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 18 19 #ifdef __uClinux__ 20 # include <lddk.h> 21 #endif 22 23 #include "heapmm.h" 24 25 #define U(BASE) HMM_UNIQUE(BASE) 26 27 /* Mask of high bit of variable of size_bau type. */ 28 #define HIGH_BIT_BAU_SIZE \ 29 ((U(size_bau)) ~ (((U(size_bau)) ~ (U(size_bau)) 0) >> 1)) 30 31 /* Add a given number of AAUs to pointer. */ 32 #define AAUS_FORWARD(PTR, AAU_OFFSET) \ 33 (((char *) (PTR)) + ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT))) 34 35 /* Subtract a given number of AAUs from pointer. */ 36 #define AAUS_BACKWARD(PTR, AAU_OFFSET) \ 37 (((char *) (PTR)) - ((AAU_OFFSET) * ((U(size_aau)) HMM_ADDR_ALIGN_UNIT))) 38 39 /* Add a given number of BAUs to a pointer. */ 40 #define BAUS_FORWARD(PTR, BAU_OFFSET) \ 41 AAUS_FORWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) 42 43 /* Subtract a given number of BAUs to a pointer. */ 44 #define BAUS_BACKWARD(PTR, BAU_OFFSET) \ 45 AAUS_BACKWARD((PTR), (BAU_OFFSET) * ((U(size_aau)) HMM_BLOCK_ALIGN_UNIT)) 46 47 typedef struct head_struct { 48 /* Sizes in Block Alignment Units. */ 49 HMM_UNIQUE(size_bau) previous_block_size, block_size; 50 } 51 head_record; 52 53 typedef struct ptr_struct { 54 struct ptr_struct *self, *prev, *next; 55 } 56 ptr_record; 57 58 /* Divide and round up any fraction to the next whole number. */ 59 #define DIV_ROUND_UP(NUMER, DENOM) (((NUMER) + (DENOM) - 1) / (DENOM)) 60 61 /* Number of AAUs in a block head. */ 62 #define HEAD_AAUS DIV_ROUND_UP(sizeof(head_record), HMM_ADDR_ALIGN_UNIT) 63 64 /* Number of AAUs in a block pointer record. */ 65 #define PTR_RECORD_AAUS DIV_ROUND_UP(sizeof(ptr_record), HMM_ADDR_ALIGN_UNIT) 66 67 /* Number of BAUs in a dummy end record (at end of chunk). */ 68 #define DUMMY_END_BLOCK_BAUS DIV_ROUND_UP(HEAD_AAUS, HMM_BLOCK_ALIGN_UNIT) 69 70 /* Minimum number of BAUs in a block (allowing room for the pointer record. */ 71 #define MIN_BLOCK_BAUS \ 72 DIV_ROUND_UP(HEAD_AAUS + PTR_RECORD_AAUS, HMM_BLOCK_ALIGN_UNIT) 73 74 /* Return number of BAUs in block (masking off high bit containing block 75 ** status). */ 76 #define BLOCK_BAUS(HEAD_PTR) \ 77 (((head_record *) (HEAD_PTR))->block_size & ~HIGH_BIT_BAU_SIZE) 78 79 /* Return number of BAUs in previous block (masking off high bit containing 80 ** block status). */ 81 #define PREV_BLOCK_BAUS(HEAD_PTR) \ 82 (((head_record *) (HEAD_PTR))->previous_block_size & ~HIGH_BIT_BAU_SIZE) 83 84 /* Set number of BAUs in previous block, preserving high bit containing 85 ** block status. */ 86 #define SET_PREV_BLOCK_BAUS(HEAD_PTR, N_BAUS) \ 87 { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 88 h_ptr->previous_block_size &= HIGH_BIT_BAU_SIZE; \ 89 h_ptr->previous_block_size |= (N_BAUS); } 90 91 /* Convert pointer to pointer record of block to pointer to block's head 92 ** record. */ 93 #define PTR_REC_TO_HEAD(PTR_REC_PTR) \ 94 ((head_record *) AAUS_BACKWARD(PTR_REC_PTR, HEAD_AAUS)) 95 96 /* Convert pointer to block head to pointer to block's pointer record. */ 97 #define HEAD_TO_PTR_REC(HEAD_PTR) \ 98 ((ptr_record *) AAUS_FORWARD(HEAD_PTR, HEAD_AAUS)) 99 100 /* Returns non-zero if block is allocated. */ 101 #define IS_BLOCK_ALLOCATED(HEAD_PTR) \ 102 (((((head_record *) (HEAD_PTR))->block_size | \ 103 ((head_record *) (HEAD_PTR))->previous_block_size) & \ 104 HIGH_BIT_BAU_SIZE) == 0) 105 106 #define MARK_BLOCK_ALLOCATED(HEAD_PTR) \ 107 { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 108 h_ptr->block_size &= ~HIGH_BIT_BAU_SIZE; \ 109 h_ptr->previous_block_size &= ~HIGH_BIT_BAU_SIZE; } 110 111 /* Mark a block as free when it is not the first block in a bin (and 112 ** therefore not a node in the AVL tree). */ 113 #define MARK_SUCCESSIVE_BLOCK_IN_FREE_BIN(HEAD_PTR) \ 114 { register head_record *h_ptr = (head_record *) (HEAD_PTR); \ 115 h_ptr->block_size |= HIGH_BIT_BAU_SIZE; } 116 117 /* Prototypes for internal functions implemented in one file and called in 118 ** another. 119 */ 120 121 void U(into_free_collection)(U(descriptor) *desc, head_record *head_ptr); 122 123 void U(out_of_free_collection)(U(descriptor) *desc, head_record *head_ptr); 124 125 void *U(alloc_from_bin)( 126 U(descriptor) *desc, ptr_record *bin_front_ptr, U(size_bau) n_baus); 127 128 #ifdef HMM_AUDIT_FAIL 129 130 /* Simply contains a reference to the HMM_AUDIT_FAIL macro and a 131 ** dummy return. */ 132 int U(audit_block_fail_dummy_return)(void); 133 134 135 /* Auditing a block consists of checking that the size in its head 136 ** matches the previous block size in the head of the next block. */ 137 #define AUDIT_BLOCK_AS_EXPR(HEAD_PTR) \ 138 ((BLOCK_BAUS(HEAD_PTR) == \ 139 PREV_BLOCK_BAUS(BAUS_FORWARD(HEAD_PTR, BLOCK_BAUS(HEAD_PTR)))) ? \ 140 0 : U(audit_block_fail_dummy_return)()) 141 142 #define AUDIT_BLOCK(HEAD_PTR) \ 143 { void *h_ptr = (HEAD_PTR); AUDIT_BLOCK_AS_EXPR(h_ptr); } 144 145 #endif 146 147 /* Interface to AVL tree generic package instantiation. */ 148 149 #define AVL_UNIQUE(BASE) U(avl_ ## BASE) 150 151 #define AVL_HANDLE ptr_record * 152 153 #define AVL_KEY U(size_bau) 154 155 #define AVL_MAX_DEPTH 64 156 157 #include "cavl_if.h" 158 159 #endif // VPX_MEM_MEMORY_MANAGER_INCLUDE_HMM_INTRNL_H_ 160