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