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