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
32 struct HashedEntry
33 {
34 uint8* position;
35 uint32 hash;
36
operator <HashedEntry37 bool operator<(const HashedEntry& other) const
38 {
39 return hash <= other.hash;
40 }
41
operator >HashedEntry42 bool operator>(const HashedEntry& other) const
43 {
44 return hash >= other.hash;
45 }
46 };
47
48
DirectoryIterator(Inode * directory,off_t start,HTreeEntryIterator * parent)49 DirectoryIterator::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
~DirectoryIterator()72 DirectoryIterator::~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
81 status_t
InitCheck()82 DirectoryIterator::InitCheck()
83 {
84 return fInitStatus;
85 }
86
87
88 status_t
Get(char * name,size_t * _nameLength,ino_t * _id)89 DirectoryIterator::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
137 status_t
GetNext(char * name,size_t * _nameLength,ino_t * _id)138 DirectoryIterator::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
150 status_t
Next()151 DirectoryIterator::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
232 status_t
Rewind()233 DirectoryIterator::Rewind()
234 {
235 fDisplacement = 0;
236 fPreviousDisplacement = 0;
237 fLogicalBlock = 0;
238
239 return fDirectory->FindBlock(0, fPhysicalBlock);
240 }
241
242
243 void
Restart()244 DirectoryIterator::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
257 status_t
AddEntry(Transaction & transaction,const char * name,size_t _nameLength,ino_t id,uint8 type)258 DirectoryIterator::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
321 status_t
FindEntry(const char * name,ino_t * _id)322 DirectoryIterator::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
349 status_t
RemoveEntry(Transaction & transaction)350 DirectoryIterator::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
424 status_t
ChangeEntry(Transaction & transaction,ino_t id,uint8 fileType)425 DirectoryIterator::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
446 status_t
_AllocateBestEntryInBlock(uint8 nameLength,uint16 & pos,uint16 & newLength)447 DirectoryIterator::_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
504 status_t
_AddEntry(Transaction & transaction,const char * name,uint8 nameLength,ino_t id,uint8 type,uint16 newLength,uint16 pos,bool hasPrevious)505 DirectoryIterator::_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
544 status_t
_SplitIndexedBlock(Transaction & transaction,const char * name,uint8 nameLength,ino_t id,uint8 type,uint32 newBlocksPos,bool firstSplit)545 DirectoryIterator::_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
810 status_t
_NextBlock()811 DirectoryIterator::_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
834 bool
_CheckDirEntry(const ext2_dir_entry * dirEntry,const uint8 * buffer)835 DirectoryIterator::_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
854 status_t
_CheckBlock(const uint8 * buffer)855 DirectoryIterator::_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
878 ext2_htree_tail*
_HTreeEntryTail(uint8 * block,uint16 offset) const879 DirectoryIterator::_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
890 uint32
_HTreeRootChecksum(uint8 * block,uint16 offset,uint16 count) const891 DirectoryIterator::_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
909 void
_SetHTreeEntryChecksum(uint8 * block,uint16 offset,uint16 count)910 DirectoryIterator::_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
921 uint32
_MaxSize()922 DirectoryIterator::_MaxSize()
923 {
924 uint32 maxSize = fBlockSize;
925 if (fVolume->HasMetaGroupChecksumFeature())
926 maxSize -= sizeof(ext2_dir_entry_tail);
927 return maxSize;
928 }
929
930