1/* 2** Copyright 2004, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3** Distributed under the terms of the Haiku License. 4*/ 5 6 7/** The BlockMap stores offset:address pairs; you can map an offset to a specific address. 8 * It has been designed to contain few and mostly contiguous offset mappings - it is used 9 * by the file cache to keep track about which blocks of the file are already in memory. 10 * The offsets may spread over a very large amount. 11 * 12 * Internally, it stores small and contiguous address arrays of a certain size, and 13 * accesses those using a hash table. Address values of NULL are equal to non existing 14 * mappings; that value cannot be stored. At the current size, each hash entry can 15 * map 60 addresses which corresponds to a file range of 240 kB. 16 * It currently does not do any locking; it assumes a safe environment which you are 17 * responsible for to create when you call its functions. 18 */ 19 20 21#include "BlockMap.h" 22 23#include <KernelExport.h> 24#include <util/kernel_cpp.h> 25 26#include <stdlib.h> 27#include <string.h> 28 29 30//#define TRACE_BLOCK_MAP 31#ifdef TRACE_BLOCK_MAP 32# define TRACE(x) dprintf x 33#else 34# define TRACE(x) 35#endif 36 37 38// ToDo: when we have a better allocator, change the number of addresses to a power of two 39// currently, this structure takes 256 bytes total 40 41struct BlockMap::block_entry { 42 block_entry *next; 43 uint32 used; 44 off_t offset; 45 addr_t address[60]; 46}; 47 48#define BLOCK_ARRAY_SIZE (sizeof(BlockMap::block_entry::address) / sizeof(addr_t)) 49 50static inline off_t 51to_block_entry_offset(off_t offset, uint32 &index) 52{ 53 // ToDo: improve this once we have a power of two array size 54 off_t baseOffset = (offset / BLOCK_ARRAY_SIZE) * BLOCK_ARRAY_SIZE; 55 index = uint32(offset - baseOffset); 56 57 return baseOffset; 58} 59 60 61static int 62block_entry_compare(void *_entry, const void *_offset) 63{ 64 BlockMap::block_entry *entry = (BlockMap::block_entry *)_entry; 65 const off_t *offset = (const off_t *)_offset; 66 67 return entry->offset - *offset; 68} 69 70 71static uint32 72block_entry_hash(void *_entry, const void *_offset, uint32 range) 73{ 74 BlockMap::block_entry *entry = (BlockMap::block_entry *)_entry; 75 const off_t *offset = (const off_t *)_offset; 76 77 if (entry != NULL) 78 return entry->offset % range; 79 80 return *offset % range; 81} 82 83 84// #pragma mark - 85 86 87BlockMap::BlockMap(off_t size) 88 : 89 fSize(size) 90{ 91 fHashTable = hash_init(16, 0, &block_entry_compare, &block_entry_hash); 92} 93 94 95BlockMap::~BlockMap() 96{ 97} 98 99 100/** Checks whether or not the construction of the BlockMap were successful. 101 */ 102 103status_t 104BlockMap::InitCheck() const 105{ 106 return fHashTable != NULL ? B_OK : B_NO_MEMORY; 107} 108 109 110/** Sets the size of the block map - all existing entries beyond this size will be 111 * removed from the map, and their memory is freed. 112 */ 113 114void 115BlockMap::SetSize(off_t size) 116{ 117 TRACE(("BlockMap::SetSize(%Ld)\n", size)); 118 119 if (size >= fSize) { 120 // nothing to do 121 fSize = size; 122 return; 123 } 124 125 // ToDo: remove all mappings beyond the file size 126} 127 128 129/** Upon successful exit which is indicated by a return value of B_OK, the "_entry" 130 * argument points to a block_entry structure containing the data for the given 131 * offset. 132 * The offset must have been normalized to the base offset values of a block entry 133 * already. 134 */ 135 136status_t 137BlockMap::GetBlockEntry(off_t baseOffset, block_entry **_entry) 138{ 139 block_entry *entry = (block_entry *)hash_lookup(fHashTable, &baseOffset); 140 if (entry == NULL) 141 return B_ENTRY_NOT_FOUND; 142 143 *_entry = entry; 144 return B_OK; 145} 146 147 148status_t 149BlockMap::Remove(off_t offset, off_t count) 150{ 151 TRACE(("BlockMap::Remove(offset = %Ld, count = %Ld)\n", offset, count)); 152 153 uint32 index; 154 off_t baseOffset = to_block_entry_offset(offset, index); 155 block_entry *entry; 156 157 while (count > 0) { 158 int32 max = min_c(BLOCK_ARRAY_SIZE, index + count); 159 int32 blocks = max - index; 160 161 if (GetBlockEntry(baseOffset, &entry) == B_OK) { 162 for (int32 i = index; i < max; i++) { 163 if (entry->address[i] != NULL) 164 entry->used--; 165 166 entry->address[i] = NULL; 167 } 168 169 if (entry->used == 0) { 170 // release entry if it's no longer used 171 hash_remove(fHashTable, entry); 172 free(entry); 173 } 174 } 175 176 baseOffset += BLOCK_ARRAY_SIZE; 177 count -= blocks; 178 index = 0; 179 } 180 181 return B_OK; 182} 183 184 185status_t 186BlockMap::Set(off_t offset, addr_t address) 187{ 188 TRACE(("BlockMap::Set(offset = %Ld, address = %08lx)\n", offset, address)); 189 190 uint32 index; 191 off_t baseOffset = to_block_entry_offset(offset, index); 192 193 block_entry *entry; 194 if (GetBlockEntry(baseOffset, &entry) == B_OK) { 195 // the block already exists, we just need to fill in our new address 196 if (entry->address[index] == NULL && address != NULL) 197 entry->used++; 198 else if (entry->address[index] != NULL && address == NULL) 199 entry->used--; 200 201 entry->address[index] = address; 202 return B_OK; 203 } 204 205 // allocate new block and fill it 206 207 entry = (block_entry *)malloc(sizeof(struct block_entry)); 208 if (entry == NULL) 209 return B_NO_MEMORY; 210 211 memset(entry->address, 0, sizeof(entry->address)); 212 213 entry->used = 1; 214 entry->offset = baseOffset; 215 216 hash_insert(fHashTable, entry); 217 218 entry->address[index] = address; 219 return B_OK; 220} 221 222 223status_t 224BlockMap::Get(off_t offset, addr_t &address) 225{ 226 TRACE(("BlockMap::Get(offset = %Ld)\n", offset)); 227 228 uint32 index; 229 off_t baseOffset = to_block_entry_offset(offset, index); 230 231 block_entry *entry; 232 if (GetBlockEntry(baseOffset, &entry) == B_OK 233 && entry->address[index] != NULL) { 234 address = entry->address[index]; 235 return B_OK; 236 } 237 238 return B_ENTRY_NOT_FOUND; 239} 240 241