1/*
2 * Copyright 2008, Axel D��rfler, axeld@pinc-software.de.
3 * This file may be used under the terms of the MIT License.
4 */
5
6
7#include "DirectoryIterator.h"
8
9#include <string.h>
10
11#include <AutoDeleter.h>
12#include <util/VectorSet.h>
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#	define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); }
24#else
25#	define TRACE(x...) ;
26#	define ASSERT(x) ;
27#endif
28
29
30struct HashedEntry
31{
32	uint8*	position;
33	uint32	hash;
34
35	bool	operator<(const HashedEntry& other)	const
36	{
37		return hash <= other.hash;
38	}
39
40	bool	operator>(const HashedEntry& other)	const
41	{
42		return hash >= other.hash;
43	}
44};
45
46
47DirectoryIterator::DirectoryIterator(Inode* directory, off_t start,
48	HTreeEntryIterator* parent)
49	:
50	fDirectory(directory),
51	fVolume(directory->GetVolume()),
52	fBlockSize(fVolume->BlockSize()),
53	fParent(parent),
54	fNumBlocks(directory->Size() == 0 ? 0
55		: (directory->Size() - 1) / fBlockSize + 1),
56	fLogicalBlock(start / fBlockSize),
57	fDisplacement(start % fBlockSize),
58	fPreviousDisplacement(fDisplacement),
59	fStartLogicalBlock(fLogicalBlock),
60	fStartDisplacement(fDisplacement)
61{
62	TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: "
63		"%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks);
64	fIndexing = parent != NULL;
65	fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock);
66	fStartPhysicalBlock = fPhysicalBlock;
67}
68
69
70DirectoryIterator::~DirectoryIterator()
71{
72	TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this,
73		fParent);
74	delete fParent;
75	TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n");
76}
77
78
79status_t
80DirectoryIterator::InitCheck()
81{
82	return fInitStatus;
83}
84
85
86status_t
87DirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id)
88{
89	TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID());
90	if (_Offset() >= fDirectory->Size()) {
91		TRACE("DirectoryIterator::Get() out of entries\n");
92		return B_ENTRY_NOT_FOUND;
93	}
94
95	CachedBlock cached(fVolume);
96	const uint8* block = cached.SetTo(fPhysicalBlock);
97	if (block == NULL)
98		return B_IO_ERROR;
99
100	ASSERT(_CheckBlock(block));
101
102	TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n",
103		fDisplacement);
104	const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement];
105
106	if (entry->Length() == 0 || entry->InodeID() == 0)
107		return B_BAD_DATA;
108
109	if (entry->NameLength() != 0) {
110		size_t length = entry->NameLength();
111
112		TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %"
113			B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n",
114			fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(),
115			length,	entry->FileType());
116
117		if (*_nameLength > 0) {
118			if (length + 1 > *_nameLength)
119				return B_BUFFER_OVERFLOW;
120
121			memcpy(name, entry->name, length);
122			name[length] = '\0';
123
124			*_nameLength = length;
125		}
126
127		*_id = entry->InodeID();
128	} else
129		*_nameLength = 0;
130
131	return B_OK;
132}
133
134
135status_t
136DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
137{
138	status_t status;
139	while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) {
140		status = Next();
141		if (status != B_OK)
142			return status;
143	}
144	return status;
145}
146
147
148status_t
149DirectoryIterator::Next()
150{
151	TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n",
152		fDirectory->ID());
153
154	if (_Offset() >= fDirectory->Size()) {
155		TRACE("DirectoryIterator::Next() out of entries\n");
156		return B_ENTRY_NOT_FOUND;
157	}
158
159	TRACE("DirectoryIterator::Next(): Creating cached block\n");
160
161	CachedBlock cached(fVolume);
162	ext2_dir_entry* entry;
163
164	TRACE("DirectoryIterator::Next(): Loading cached block\n");
165	const uint8* block = cached.SetTo(fPhysicalBlock);
166	if (block == NULL)
167		return B_IO_ERROR;
168
169	ASSERT(_CheckBlock(block));
170	uint32 maxSize = _MaxSize();
171
172	entry = (ext2_dir_entry*)(block + fDisplacement);
173
174	do {
175		TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32
176			" entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement,
177			entry->InodeID());
178
179		if (entry->Length() != 0) {
180			if (!entry->IsValid()) {
181				TRACE("invalid entry.\n");
182				return B_BAD_DATA;
183			}
184			fPreviousDisplacement = fDisplacement;
185			fDisplacement += entry->Length();
186		} else
187			fDisplacement = maxSize;
188
189		if (fDisplacement == maxSize) {
190			TRACE("Reached end of block\n");
191
192			fDisplacement = 0;
193
194			status_t status = _NextBlock();
195			if (status != B_OK)
196				return status;
197
198			if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize())
199					>= fDirectory->Size()) {
200				TRACE("DirectoryIterator::Next() end of directory file\n");
201				return B_ENTRY_NOT_FOUND;
202			}
203			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
204			if (status != B_OK)
205				return status;
206
207			block = cached.SetTo(fPhysicalBlock);
208			if (block == NULL)
209				return B_IO_ERROR;
210			ASSERT(_CheckBlock(block));
211
212		} else if (fDisplacement > maxSize) {
213			TRACE("The entry isn't block aligned.\n");
214			// TODO: Is block alignment obligatory?
215			return B_BAD_DATA;
216		}
217
218		entry = (ext2_dir_entry*)(block + fDisplacement);
219
220		TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n",
221			entry->Length(), entry->InodeID());
222	} while (entry->Length() == 0 || entry->InodeID() == 0);
223
224	TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n",
225			entry->Length(), entry->NameLength(), entry->name);
226
227	return B_OK;
228}
229
230
231status_t
232DirectoryIterator::Rewind()
233{
234	fDisplacement = 0;
235	fPreviousDisplacement = 0;
236	fLogicalBlock = 0;
237
238	return fDirectory->FindBlock(0, fPhysicalBlock);
239}
240
241
242void
243DirectoryIterator::Restart()
244{
245	TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): "
246		"current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%"
247		B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock,
248		fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock,
249		fStartDisplacement);
250	fLogicalBlock = fStartLogicalBlock;
251	fPhysicalBlock = fStartPhysicalBlock;
252	fDisplacement = fPreviousDisplacement = fStartDisplacement;
253}
254
255
256status_t
257DirectoryIterator::AddEntry(Transaction& transaction, const char* name,
258	size_t _nameLength, ino_t id, uint8 type)
259{
260	TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name);
261
262	uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH
263		: _nameLength;
264
265	status_t status = B_OK;
266	while (status == B_OK) {
267		uint16 pos = 0;
268		uint16 newLength;
269
270		status = _AllocateBestEntryInBlock(nameLength, pos, newLength);
271		if (status == B_OK) {
272			return _AddEntry(transaction, name, nameLength, id, type, newLength,
273				pos);
274		} else if (status != B_DEVICE_FULL)
275			return status;
276
277		fDisplacement = 0;
278		status = _NextBlock();
279		if (status == B_OK)
280			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
281	}
282
283	if (status != B_ENTRY_NOT_FOUND)
284		return status;
285
286	bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories();
287
288	fNumBlocks++;
289
290	if (fIndexing) {
291		TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n");
292		fNumBlocks += fParent->BlocksNeededForNewEntry();
293	} else if (firstSplit) {
294		// Allocate another block (fNumBlocks should become 3)
295		TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n");
296		fNumBlocks++;
297	} else
298		TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n");
299
300	status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize);
301	if (status != B_OK)
302		return status;
303
304	if (firstSplit || fIndexing) {
305		// firstSplit and fIndexing are mutually exclusive
306		return _SplitIndexedBlock(transaction, name, nameLength, id, type,
307			fNumBlocks - 1, firstSplit);
308	}
309
310	fLogicalBlock = fNumBlocks - 1;
311	status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock);
312	if (status != B_OK)
313		return status;
314
315	return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0,
316		false);
317}
318
319
320status_t
321DirectoryIterator::FindEntry(const char* name, ino_t* _id)
322{
323	TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name);
324	char buffer[EXT2_NAME_LENGTH + 1];
325	ino_t id;
326
327	status_t status = B_OK;
328	size_t length = strlen(name);
329	while (status == B_OK) {
330		size_t nameLength = EXT2_NAME_LENGTH;
331		status = Get(buffer, &nameLength, &id);
332		if (status == B_OK) {
333			if (length == nameLength
334				&& strncmp(name, buffer, nameLength) == 0) {
335				if (_id != NULL)
336					*_id = id;
337				return B_OK;
338			}
339		} else if (status != B_BAD_DATA)
340			break;
341		status = Next();
342	}
343
344	return status;
345}
346
347
348status_t
349DirectoryIterator::RemoveEntry(Transaction& transaction)
350{
351	TRACE("DirectoryIterator::RemoveEntry()\n");
352	ext2_dir_entry* previousEntry;
353	ext2_dir_entry* dirEntry;
354	CachedBlock cached(fVolume);
355
356	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
357	uint32 maxSize = _MaxSize();
358
359	if (fDisplacement == 0) {
360		previousEntry = (ext2_dir_entry*)&block[fDisplacement];
361
362		fPreviousDisplacement = fDisplacement;
363		fDisplacement += previousEntry->Length();
364
365		if (fDisplacement == maxSize) {
366			previousEntry->SetInodeID(0);
367			fDisplacement = 0;
368			return B_OK;
369		} else if (fDisplacement > maxSize) {
370			TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to "
371				"block entry.");
372			return B_BAD_DATA;
373		}
374
375		dirEntry = (ext2_dir_entry*)&block[fDisplacement];
376		memcpy(&block[fPreviousDisplacement], &block[fDisplacement],
377			dirEntry->Length());
378
379		previousEntry->SetLength(fDisplacement - fPreviousDisplacement
380			+ previousEntry->Length());
381
382		fDirectory->SetDirEntryChecksum(block);
383
384		ASSERT(_CheckBlock(block));
385
386		return B_OK;
387	}
388
389	TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n",
390		fDisplacement);
391
392	if (fPreviousDisplacement == fDisplacement) {
393		char buffer[EXT2_NAME_LENGTH + 1];
394
395		dirEntry = (ext2_dir_entry*)&block[fDisplacement];
396
397		memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length);
398
399		fDisplacement = 0;
400		status_t status = FindEntry(dirEntry->name);
401		if (status == B_ENTRY_NOT_FOUND)
402			return B_BAD_DATA;
403		if (status != B_OK)
404			return status;
405	}
406
407	previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement];
408	dirEntry = (ext2_dir_entry*)&block[fDisplacement];
409
410	previousEntry->SetLength(previousEntry->Length() + dirEntry->Length());
411
412	memset(&block[fDisplacement], 0,
413		fPreviousDisplacement + previousEntry->Length() - fDisplacement);
414
415	fDirectory->SetDirEntryChecksum(block);
416
417	ASSERT(_CheckBlock(block));
418
419	return B_OK;
420}
421
422
423status_t
424DirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id,
425	uint8 fileType)
426{
427	CachedBlock cached(fVolume);
428
429	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
430	if (block == NULL)
431		return B_IO_ERROR;
432
433	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement];
434	dirEntry->SetInodeID(id);
435	dirEntry->file_type = fileType;
436
437	fDirectory->SetDirEntryChecksum(block);
438
439	ASSERT(_CheckBlock(block));
440
441	return B_OK;
442}
443
444
445status_t
446DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos,
447	uint16& newLength)
448{
449	TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n");
450	CachedBlock cached(fVolume);
451	const uint8* block = cached.SetTo(fPhysicalBlock);
452
453	ASSERT(_CheckBlock(block));
454
455	uint16 requiredLength = EXT2_DIR_REC_LEN(nameLength);
456	uint32 maxSize = _MaxSize();
457
458	uint16 bestPos = maxSize;
459	uint16 bestLength = maxSize;
460	uint16 bestRealLength = maxSize;
461	ext2_dir_entry* dirEntry;
462
463	while (pos < maxSize) {
464		dirEntry = (ext2_dir_entry*)&block[pos];
465		if (!_CheckDirEntry(dirEntry, block)) {
466			TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): invalid "
467				"dirEntry->Length() pos %d\n", pos);
468			return B_BAD_DATA;
469		}
470
471		uint16 realLength = EXT2_DIR_REC_LEN(dirEntry->NameLength());
472		uint16 emptySpace = dirEntry->Length();
473		if (dirEntry->InodeID() != 0)
474			emptySpace -= realLength;
475		if (emptySpace == requiredLength) {
476			// Found an exact match
477			TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an "
478				"exact length match\n");
479			newLength = realLength;
480
481			return B_OK;
482		} else if (emptySpace > requiredLength && emptySpace < bestLength) {
483			bestPos = pos;
484			bestLength = emptySpace;
485			bestRealLength = realLength;
486		}
487
488		pos += dirEntry->Length();
489	}
490
491	if (bestPos == maxSize)
492		return B_DEVICE_FULL;
493
494	TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable "
495		"location: %u\n", bestPos);
496	pos = bestPos;
497	newLength = bestRealLength;
498
499	return B_OK;
500}
501
502
503status_t
504DirectoryIterator::_AddEntry(Transaction& transaction, const char* name,
505	uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos,
506	bool hasPrevious)
507{
508	TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, "
509		"%c)\n", name, nameLength, id, type, newLength, pos,
510		hasPrevious ? 't' : 'f');
511	CachedBlock cached(fVolume);
512
513	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
514	if (block == NULL)
515		return B_IO_ERROR;
516
517	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos];
518
519	if (hasPrevious) {
520		uint16 previousLength = dirEntry->Length();
521		dirEntry->SetLength(newLength);
522
523		dirEntry = (ext2_dir_entry*)&block[pos + newLength];
524		newLength = previousLength - newLength;
525	}
526
527	dirEntry->SetLength(newLength);
528	dirEntry->name_length = nameLength;
529	dirEntry->SetInodeID(id);
530	dirEntry->file_type = type;
531	memcpy(dirEntry->name, name, nameLength);
532
533	fDirectory->SetDirEntryChecksum(block);
534
535	ASSERT(_CheckBlock(block));
536
537	TRACE("DirectoryIterator::_AddEntry(): Done\n");
538
539	return B_OK;
540}
541
542
543status_t
544DirectoryIterator::_SplitIndexedBlock(Transaction& transaction,
545	const char* name, uint8 nameLength, ino_t id, uint8 type,
546	uint32 newBlocksPos, bool firstSplit)
547{
548	// Block is full, split required
549	TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %"
550		B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos,
551		firstSplit ? 't' : 'f');
552
553	// Allocate a buffer for the entries in the block
554	uint8* buffer = new(std::nothrow) uint8[fBlockSize];
555	if (buffer == NULL)
556		return B_NO_MEMORY;
557	ArrayDeleter<uint8> bufferDeleter(buffer);
558
559	fsblock_t firstPhysicalBlock = 0;
560	uint32 maxSize = _MaxSize();
561
562	// Prepare block to hold the first half of the entries and fill the buffer
563	CachedBlock cachedFirst(fVolume);
564
565	if (firstSplit) {
566		// Save all entries to the buffer
567		status_t status = fDirectory->FindBlock(0, firstPhysicalBlock);
568		if (status != B_OK)
569			return status;
570
571		const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock);
572		if (srcBlock == NULL)
573			return B_IO_ERROR;
574
575		memcpy(buffer, srcBlock, fBlockSize);
576
577		status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock);
578		if (status != B_OK)
579			return status;
580	}
581
582	uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock);
583	uint8* secondBlock = NULL;
584	if (firstBlock == NULL)
585		return B_IO_ERROR;
586
587	status_t status;
588
589	if (!firstSplit) {
590		// Save all entries to the buffer
591		memcpy(buffer, firstBlock, fBlockSize);
592	} else {
593		// Initialize the root node
594		fDirectory->Node().SetFlag(EXT2_INODE_INDEXED);
595		HTreeRoot* root;
596
597		secondBlock = cachedFirst.SetToWritable(transaction,
598			firstPhysicalBlock, true);
599		if (secondBlock == NULL)
600			return B_IO_ERROR;
601
602		status = fDirectory->WriteBack(transaction);
603		if (status != B_OK)
604			return status;
605
606		memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4));
607
608		root = (HTreeRoot*)secondBlock;
609
610		HTreeFakeDirEntry* dotdot = &root->dotdot;
611		dotdot->SetEntryLength(maxSize);
612
613		root->hash_version = fVolume->DefaultHashVersion();
614		root->root_info_length = 8;
615		root->indirection_levels = 0;
616
617		root->count_limit->SetLimit((maxSize
618			- ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry));
619		root->count_limit->SetCount(2);
620	}
621
622	// Sort entries
623	VectorSet<HashedEntry> entrySet;
624
625	HTree htree(fVolume, fDirectory);
626	status = htree.PrepareForHash();
627	if (status != B_OK)
628		return status;
629
630	uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0;
631
632	HashedEntry entry;
633	ext2_dir_entry* dirEntry = NULL;
634
635	while (displacement < maxSize) {
636		entry.position = &buffer[displacement];
637		dirEntry = (ext2_dir_entry*)entry.position;
638
639		TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name "
640			"length: %u, entry length: %u\n", entry.position,
641			dirEntry->name_length,
642			dirEntry->Length());
643
644		char cbuffer[256];
645		memcpy(cbuffer, dirEntry->name, dirEntry->name_length);
646		cbuffer[dirEntry->name_length] = '\0';
647		entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length);
648		TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
649			cbuffer, entry.hash);
650
651		status = entrySet.Insert(entry);
652		if (status != B_OK)
653			return status;
654
655		displacement += dirEntry->Length();
656	}
657
658	// Prepare the new entry to be included as well
659	ext2_dir_entry newEntry;
660
661	uint16 newLength = EXT2_DIR_REC_LEN(nameLength);
662
663	newEntry.name_length = nameLength;
664	newEntry.SetLength(newLength);
665	newEntry.SetInodeID(id);
666	newEntry.file_type = type;
667	memcpy(newEntry.name, name, nameLength);
668
669	entry.position = (uint8*)&newEntry;
670	entry.hash = htree.Hash(name, nameLength);
671	TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
672		name, entry.hash);
673
674	entrySet.Insert(entry);
675
676	// Move first half of entries to the first block
677	VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin();
678	int32 median = entrySet.Count() / 2;
679	displacement = 0;
680	TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32
681		", median: %" B_PRId32 "\n", entrySet.Count(), median);
682
683	uint32 previousHash = (*iterator).hash;
684
685	for (int32 i = 0; i < median; ++i) {
686		dirEntry = (ext2_dir_entry*)(*iterator).position;
687		previousHash = (*iterator).hash;
688
689		uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length);
690
691		dirEntry->SetLength((uint16)realLength);
692		memcpy(&firstBlock[displacement], dirEntry, realLength);
693
694		displacement += realLength;
695		iterator++;
696	}
697
698	// Update last entry in the block
699	uint16 oldLength = dirEntry->Length();
700	dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength];
701	dirEntry->SetLength(maxSize - displacement + oldLength);
702
703	fDirectory->SetDirEntryChecksum(firstBlock);
704
705	bool collision = false;
706
707	while (iterator != entrySet.End() && (*iterator).hash == previousHash) {
708		// Keep collisions on the same block
709		TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n");
710
711		// This isn't the ideal solution, but it is a rare occurance
712		dirEntry = (ext2_dir_entry*)(*iterator).position;
713
714		if (displacement + dirEntry->Length() > maxSize) {
715			// Doesn't fit on the block
716			collision = true;
717			break;
718		}
719
720		memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length());
721
722		displacement += dirEntry->Length();
723		iterator++;
724	}
725
726	// Save the hash to store in the parent
727	uint32 medianHash = (*iterator).hash;
728
729	// Update parent
730	if (firstSplit) {
731		TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n");
732		HTreeRoot* root = (HTreeRoot*)secondBlock;
733		HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit;
734		htreeEntry->SetBlock(1);
735
736		++htreeEntry;
737		htreeEntry->SetBlock(2);
738		htreeEntry->SetHash(medianHash);
739
740
741		off_t start = (off_t)root->root_info_length
742			+ 2 * (sizeof(HTreeFakeDirEntry) + 4);
743		_SetHTreeEntryChecksum(secondBlock, start, 2);
744		fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory);
745		if (fParent == NULL)
746			return B_NO_MEMORY;
747
748		fLogicalBlock = 1;
749		status = fDirectory->FindBlock(fLogicalBlock * fBlockSize,
750			fPhysicalBlock);
751
752		fPreviousDisplacement = fDisplacement = 0;
753
754		status = fParent->Init();
755	}
756	else {
757		status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1,
758			newBlocksPos, collision);
759	}
760	if (status != B_OK)
761		return status;
762
763	// Prepare last block to hold the second half of the entries
764	TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf "
765		"block\n");
766	fDisplacement = 0;
767
768	status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock);
769	if (status != B_OK)
770		return status;
771
772	CachedBlock cachedSecond(fVolume);
773	secondBlock = cachedSecond.SetToWritable(transaction,
774		fPhysicalBlock);
775	if (secondBlock == NULL)
776		return B_IO_ERROR;
777
778	// Move the second half of the entries to the second block
779	VectorSet<HashedEntry>::Iterator end = entrySet.End();
780	displacement = 0;
781
782	while (iterator != end) {
783		dirEntry = (ext2_dir_entry*)(*iterator).position;
784
785		uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length);
786
787		dirEntry->SetLength((uint16)realLength);
788		memcpy(&secondBlock[displacement], dirEntry, realLength);
789
790		displacement += realLength;
791		iterator++;
792	}
793
794	// Update last entry in the block
795	oldLength = dirEntry->Length();
796	dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength];
797	dirEntry->SetLength(maxSize - displacement + oldLength);
798
799	fDirectory->SetDirEntryChecksum(secondBlock);
800
801	ASSERT(_CheckBlock(firstBlock));
802	ASSERT(_CheckBlock(secondBlock));
803
804	TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n");
805	return B_OK;
806}
807
808
809status_t
810DirectoryIterator::_NextBlock()
811{
812	TRACE("DirectoryIterator::_NextBlock()\n");
813	if (fIndexing) {
814		TRACE("DirectoryIterator::_NextBlock(): Indexing\n");
815		if (!fParent->HasCollision()) {
816			TRACE("DirectoryIterator::_NextBlock(): next block doesn't "
817				"contain collisions from previous block\n");
818#ifndef COLLISION_TEST
819			return B_ENTRY_NOT_FOUND;
820#endif
821		}
822
823		return fParent->GetNext(fLogicalBlock);
824	}
825
826	if (++fLogicalBlock > fNumBlocks)
827		return B_ENTRY_NOT_FOUND;
828
829	return B_OK;
830}
831
832
833bool
834DirectoryIterator::_CheckDirEntry(const ext2_dir_entry* dirEntry, const uint8* buffer)
835{
836	const char *errmsg = NULL;
837	if (dirEntry->Length() < EXT2_DIR_REC_LEN(1))
838		errmsg = "Length is too small";
839	else if (dirEntry->Length() % 4 != 0)
840		errmsg = "Length is not a multiple of 4";
841	else if (dirEntry->Length() < EXT2_DIR_REC_LEN(dirEntry->NameLength()))
842		errmsg = "Length is too short for the name";
843	else if (((uint8*)dirEntry - buffer) + dirEntry->Length() > fBlockSize)
844		errmsg = "Length is too big for the blocksize";
845
846	TRACE("DirectoryIterator::_CheckDirEntry() %s\n", errmsg);
847	return errmsg == NULL;
848}
849
850
851status_t
852DirectoryIterator::_CheckBlock(const uint8* buffer)
853{
854	uint32 maxSize = fBlockSize;
855	if (fVolume->HasMetaGroupChecksumFeature())
856		maxSize -= sizeof(ext2_dir_entry_tail);
857
858	status_t err = B_OK;
859	uint16 pos = 0;
860	while (pos < maxSize) {
861		const ext2_dir_entry *dirEntry = (const ext2_dir_entry*)&buffer[pos];
862
863		if (!_CheckDirEntry(dirEntry, buffer)) {
864			TRACE("DirectoryIterator::_CheckBlock(): invalid "
865				"dirEntry pos %d\n", pos);
866			err = B_BAD_DATA;
867		}
868
869		pos += dirEntry->Length();
870	}
871	return err;
872}
873
874
875ext2_htree_tail*
876DirectoryIterator::_HTreeEntryTail(uint8* block, uint16 offset) const
877{
878	HTreeEntry* entries = (HTreeEntry*)block;
879	uint16 firstEntry = offset % fBlockSize / sizeof(HTreeEntry);
880	HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[firstEntry];
881	uint16 limit = countLimit->Limit();
882	TRACE("HTreeEntryIterator::_HTreeEntryTail() %p %p\n", block, &entries[firstEntry + limit]);
883	return (ext2_htree_tail*)(&entries[firstEntry + limit]);
884}
885
886
887uint32
888DirectoryIterator::_HTreeRootChecksum(uint8* block, uint16 offset, uint16 count) const
889{
890	uint32 number = fDirectory->ID();
891	uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(),
892		(uint8*)&number, sizeof(number));
893	uint32 gen = fDirectory->Node().generation;
894	checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen));
895	checksum = calculate_crc32c(checksum, block,
896		offset + count * sizeof(HTreeEntry));
897	TRACE("HTreeEntryIterator::_HTreeRootChecksum() size %u\n", offset + count * sizeof(HTreeEntry));
898	ext2_htree_tail dummy;
899	dummy.reserved = 0;
900	checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy));
901	return checksum;
902}
903
904
905void
906DirectoryIterator::_SetHTreeEntryChecksum(uint8* block, uint16 offset, uint16 count)
907{
908	TRACE("DirectoryIterator::_SetHTreeEntryChecksum()\n");
909	if (fVolume->HasMetaGroupChecksumFeature()) {
910		ext2_htree_tail* tail = _HTreeEntryTail(block, offset);
911		tail->reserved = 0x0;
912		tail->checksum = _HTreeRootChecksum(block, offset, count);
913	}
914}
915
916
917uint32
918DirectoryIterator::_MaxSize()
919{
920	uint32 maxSize = fBlockSize;
921	if (fVolume->HasMetaGroupChecksumFeature())
922		maxSize -= sizeof(ext2_dir_entry_tail);
923	return maxSize;
924}
925
926