1/*
2 * Copyright 2010, Haiku Inc. All rights reserved.
3 * This file may be used under the terms of the MIT License.
4 *
5 * Authors:
6 *		Janito V. Ferreira Filho
7 */
8
9
10#include "HTreeEntryIterator.h"
11
12#include <new>
13
14#include "CachedBlock.h"
15#include "HTree.h"
16#include "Inode.h"
17
18
19//#define TRACE_EXT2
20#ifdef TRACE_EXT2
21#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
22#else
23#	define TRACE(x...) ;
24#endif
25#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
26
27
28HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory)
29	:
30	fDirectory(directory),
31	fVolume(directory->GetVolume()),
32	fHasCollision(false),
33	fBlockSize(directory->GetVolume()->BlockSize()),
34	fParent(NULL),
35	fChild(NULL)
36{
37	fInitStatus = fDirectory->FindBlock(offset, fBlockNum);
38
39	if (fInitStatus == B_OK) {
40		fFirstEntry = offset % fBlockSize / sizeof(HTreeEntry);
41		fCurrentEntry = fFirstEntry;
42	}
43
44	TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %llu, "
45		"entry no. %lu, parent: %p\n", this, fBlockNum, (uint32)fCurrentEntry,
46		fParent);
47}
48
49
50HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize,
51	Inode* directory, HTreeEntryIterator* parent, bool hasCollision)
52	:
53	fDirectory(directory),
54	fVolume(directory->GetVolume()),
55	fHasCollision(hasCollision),
56	fFirstEntry(1),
57	fCurrentEntry(1),
58	fBlockSize(blockSize),
59	fBlockNum(block),
60	fParent(parent),
61	fChild(NULL)
62{
63	// fCurrentEntry is initialized to 1 to skip the fake directory entry
64	fInitStatus = B_OK;
65
66	TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %lu, "
67		"parent: %p\n", this, block, fParent);
68}
69
70
71status_t
72HTreeEntryIterator::Init()
73{
74	TRACE("HTreeEntryIterator::Init() first entry: %lu\n",
75		(uint32)fFirstEntry);
76
77	if (fInitStatus != B_OK)
78		return fInitStatus;
79
80	CachedBlock cached(fVolume);
81	const uint8* block = cached.SetTo(fBlockNum);
82	if (block == NULL) {
83		ERROR("Failed to read htree entry block.\n");
84		fCount = fLimit = 0;
85		return B_IO_ERROR;
86	}
87
88	HTreeCountLimit* countLimit = (HTreeCountLimit*)(
89		&((HTreeEntry*)block)[fFirstEntry]);
90
91	fCount = countLimit->Count();
92	fLimit = countLimit->Limit();
93
94	if (fCount > fLimit) {
95		ERROR("HTreeEntryIterator::Init() bad fCount %u (fLimit %u)\n",
96			fCount, fLimit);
97		fCount = fLimit = 0;
98		return B_ERROR;
99	}
100
101	if (fLimit != fBlockSize / sizeof(HTreeEntry) - fFirstEntry) {
102		ERROR("HTreeEntryIterator::Init() bad fLimit %lu should be %lu "
103			"at block %llu\n", (uint32)fLimit, fBlockSize / sizeof(HTreeEntry)
104				- fFirstEntry, fBlockNum);
105		fCount = fLimit = 0;
106		return B_ERROR;
107	}
108
109	TRACE("HTreeEntryIterator::Init() count %lu limit %lu\n",
110		(uint32)fCount, (uint32)fLimit);
111
112	return B_OK;
113}
114
115
116HTreeEntryIterator::~HTreeEntryIterator()
117{
118	TRACE("HTreeEntryIterator::~HTreeEntryIterator(): %p, parent: %p\n", this,
119		fParent);
120	delete fParent;
121	TRACE("HTreeEntryIterator::~HTreeEntryIterator(): Deleted the parent\n");
122}
123
124
125status_t
126HTreeEntryIterator::Lookup(uint32 hash, int indirections,
127	DirectoryIterator** directoryIterator, bool& detachRoot)
128{
129	TRACE("HTreeEntryIterator::Lookup()\n");
130
131	if (fCount == 0)
132		return B_ENTRY_NOT_FOUND;
133
134	CachedBlock cached(fVolume);
135	const uint8* block = cached.SetTo(fBlockNum);
136	if (block == NULL) {
137		ERROR("Failed to read htree entry block.\n");
138		// Fallback to linear search
139		*directoryIterator = new(std::nothrow)
140			DirectoryIterator(fDirectory);
141
142		if (*directoryIterator == NULL)
143			return B_NO_MEMORY;
144
145		return B_OK;
146	}
147
148	HTreeEntry* start = (HTreeEntry*)block + fCurrentEntry + 1;
149	HTreeEntry* end = (HTreeEntry*)block + fCount + fFirstEntry - 1;
150	HTreeEntry* middle = start;
151
152	TRACE("HTreeEntryIterator::Lookup() current entry: %lu\n",
153		(uint32)fCurrentEntry);
154	TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
155		indirections, start, middle, end);
156
157	while (start <= end) {
158		middle = (HTreeEntry*)((end - start) / 2
159			+ start);
160
161		TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
162			indirections, start, middle, end);
163
164		TRACE("HTreeEntryIterator::Lookup() %lx %lx\n", hash, middle->Hash());
165
166		if (hash >= middle->Hash())
167			start = middle + 1;
168		else
169			end = middle - 1;
170	}
171
172	--start;
173
174	fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry);
175
176	if (indirections == 0) {
177		TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory "
178			"iterator starting at block: %lu, hash: 0x%lX\n", start->Block(),
179			start->Hash());
180		*directoryIterator = new(std::nothrow)
181			DirectoryIterator(fDirectory, start->Block() * fBlockSize, this);
182
183		if (*directoryIterator == NULL)
184			return B_NO_MEMORY;
185
186		detachRoot = true;
187		return B_OK;
188	}
189
190	TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator "
191		"starting at block: %lu, hash: 0x%lX\n", start->Block(), start->Hash());
192	fsblock_t blockNum;
193	status_t status = fDirectory->FindBlock(start->Block() * fBlockSize,
194		blockNum);
195	if (status != B_OK)
196		return status;
197
198	delete fChild;
199
200	fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize,
201		fDirectory, this, (start->Hash() & 1) == 1);
202	if (fChild == NULL)
203		return B_NO_MEMORY;
204
205	status = fChild->Init();
206	if (status != B_OK)
207		return status;
208
209	return fChild->Lookup(hash, indirections - 1, directoryIterator,
210		detachRoot);
211}
212
213
214status_t
215HTreeEntryIterator::GetNext(uint32& childBlock)
216{
217	fCurrentEntry++;
218	TRACE("HTreeEntryIterator::GetNext(): current entry: %lu count: %lu, "
219		"limit: %lu\n", (uint32)fCurrentEntry, (uint32)fCount, (uint32)fLimit);
220	bool endOfBlock = fCurrentEntry >= (fCount + fFirstEntry);
221
222	if (endOfBlock) {
223		TRACE("HTreeEntryIterator::GetNext(): end of entries in the block\n");
224		if (fParent == NULL) {
225			TRACE("HTreeEntryIterator::GetNext(): block was the root block\n");
226			return B_ENTRY_NOT_FOUND;
227		}
228
229		uint32 logicalBlock;
230		status_t status = fParent->GetNext(logicalBlock);
231		if (status != B_OK)
232			return status;
233
234		TRACE("HTreeEntryIterator::GetNext(): moving to next block: %lu\n",
235			logicalBlock);
236
237		status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum);
238		if (status != B_OK)
239			return status;
240
241		fFirstEntry = 1; // Skip fake directory entry
242		fCurrentEntry = 1;
243		status = Init();
244		if (status != B_OK)
245			return status;
246
247		fHasCollision = fParent->HasCollision();
248	}
249
250	CachedBlock cached(fVolume);
251	const uint8* block = cached.SetTo(fBlockNum);
252	if (block == NULL)
253		return B_IO_ERROR;
254
255	HTreeEntry* entry = &((HTreeEntry*)block)[fCurrentEntry];
256
257	if (!endOfBlock)
258		fHasCollision = (entry[fCurrentEntry].Hash() & 1) == 1;
259
260	TRACE("HTreeEntryIterator::GetNext(): next block: %lu\n",
261		entry->Block());
262
263	childBlock = entry->Block();
264
265	return B_OK;
266}
267
268
269uint32
270HTreeEntryIterator::BlocksNeededForNewEntry()
271{
272	TRACE("HTreeEntryIterator::BlocksNeededForNewEntry(): block num: %llu, "
273		"volume: %p\n", fBlockNum, fVolume);
274	CachedBlock cached(fVolume);
275
276	const uint8* blockData = cached.SetTo(fBlockNum);
277	const HTreeEntry* entries = (const HTreeEntry*)blockData;
278	const HTreeCountLimit* countLimit =
279		(const HTreeCountLimit*)&entries[fFirstEntry];
280
281	uint32 newBlocks = 0;
282	if (countLimit->IsFull()) {
283		newBlocks++;
284
285		if (fParent != NULL)
286			newBlocks += fParent->BlocksNeededForNewEntry();
287		else {
288			// Need a new level
289			HTreeRoot* root = (HTreeRoot*)entries;
290
291			if (root->indirection_levels == 1) {
292				// Maximum supported indirection levels reached
293				return B_DEVICE_FULL;
294			}
295
296			newBlocks++;
297		}
298	}
299
300	return newBlocks;
301}
302
303
304status_t
305HTreeEntryIterator::InsertEntry(Transaction& transaction, uint32 hash,
306	off_t blockNum, off_t newBlocksPos, bool hasCollision)
307{
308	TRACE("HTreeEntryIterator::InsertEntry(): block num: %llu\n", fBlockNum);
309	CachedBlock cached(fVolume);
310
311	uint8* blockData = cached.SetToWritable(transaction, fBlockNum);
312	if (blockData == NULL)
313		return B_IO_ERROR;
314
315	HTreeEntry* entries = (HTreeEntry*)blockData;
316
317	HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry];
318	uint16 count = countLimit->Count();
319
320	if (count == countLimit->Limit()) {
321		TRACE("HTreeEntryIterator::InsertEntry(): Splitting the node\n");
322		panic("Splitting a HTree node required, but isn't yet fully "
323			"supported\n");
324
325		fsblock_t physicalBlock;
326		status_t status = fDirectory->FindBlock(newBlocksPos, physicalBlock);
327		if (status != B_OK)
328			return status;
329
330		CachedBlock secondCached(fVolume);
331		uint8* secondBlockData = secondCached.SetToWritable(transaction,
332			physicalBlock);
333		if (secondBlockData == NULL)
334			return B_IO_ERROR;
335
336		HTreeFakeDirEntry* fakeEntry = (HTreeFakeDirEntry*)secondBlockData;
337		fakeEntry->inode_id = 0; // ?
338		fakeEntry->SetEntryLength(fBlockSize);
339		fakeEntry->name_length = 0;
340		fakeEntry->file_type = 0; // ?
341
342		HTreeEntry* secondBlockEntries = (HTreeEntry*)secondBlockData;
343		memmove(&entries[fFirstEntry + count / 2], &secondBlockEntries[1],
344			(count - count / 2) * sizeof(HTreeEntry));
345	}
346
347	TRACE("HTreeEntryIterator::InsertEntry(): Inserting node. Count: %u, "
348		"current entry: %u\n", count, fCurrentEntry);
349
350	if (count > 0) {
351		TRACE("HTreeEntryIterator::InsertEntry(): memmove(%u, %u, %u)\n",
352			fCurrentEntry + 2, fCurrentEntry + 1, count + fFirstEntry
353				- fCurrentEntry - 1);
354		memmove(&entries[fCurrentEntry + 2], &entries[fCurrentEntry + 1],
355			(count + fFirstEntry - fCurrentEntry - 1) * sizeof(HTreeEntry));
356	}
357
358	uint32 oldHash = entries[fCurrentEntry].Hash();
359	entries[fCurrentEntry].SetHash(hasCollision ? oldHash | 1 : oldHash & ~1);
360	entries[fCurrentEntry + 1].SetHash((oldHash & 1) == 0 ? hash & ~1
361		: hash | 1);
362	entries[fCurrentEntry + 1].SetBlock(blockNum);
363
364	countLimit->SetCount(count + 1);
365
366	return B_OK;
367}
368