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