* Copyright 2010, Haiku Inc. All rights reserved.
* This file may be used under the terms of the MIT License.
*
* Authors:
* Janito V. Ferreira Filho
*/
#include "HTreeEntryIterator.h"
#include <new>
#include "CachedBlock.h"
#include "CRCTable.h"
#include "HTree.h"
#include "Inode.h"
#ifdef TRACE_EXT2
# define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
#else
# define TRACE(x...) ;
#endif
#define ERROR(x...) dprintf("\33[34mext2:\33[0m " x)
HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory)
:
fDirectory(directory),
fVolume(directory->GetVolume()),
fHasCollision(false),
fLimit(0),
fCount(0),
fBlockSize(directory->GetVolume()->BlockSize()),
fParent(NULL),
fChild(NULL)
{
fInitStatus = fDirectory->FindBlock(offset, fBlockNum);
if (fInitStatus == B_OK) {
fFirstEntry = offset / sizeof(HTreeEntry);
fCurrentEntry = fFirstEntry;
}
TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %" B_PRIu64 ", "
"entry no. %u, parent: %p\n", this, fBlockNum, fCurrentEntry,
fParent);
}
HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize,
Inode* directory, HTreeEntryIterator* parent, bool hasCollision)
:
fDirectory(directory),
fVolume(directory->GetVolume()),
fHasCollision(hasCollision),
fLimit(0),
fCount(0),
fFirstEntry(1),
fCurrentEntry(1),
fBlockSize(blockSize),
fBlockNum(block),
fParent(parent),
fChild(NULL)
{
fInitStatus = B_OK;
TRACE("HTreeEntryIterator::HTreeEntryIterator(): created %p, block %"
B_PRIu32 ", parent: %p\n", this, block, fParent);
}
status_t
HTreeEntryIterator::Init()
{
TRACE("HTreeEntryIterator::Init() first entry: %u\n",
fFirstEntry);
if (fInitStatus != B_OK)
return fInitStatus;
CachedBlock cached(fVolume);
const uint8* block = cached.SetTo(fBlockNum);
if (block == NULL) {
ERROR("Failed to read htree entry block.\n");
fCount = fLimit = 0;
return B_IO_ERROR;
}
HTreeCountLimit* countLimit = (HTreeCountLimit*)(
&((HTreeEntry*)block)[fFirstEntry]);
fCount = countLimit->Count();
fLimit = countLimit->Limit();
if (fCount > fLimit) {
ERROR("HTreeEntryIterator::Init() bad fCount %u (fLimit %u)\n",
fCount, fLimit);
fCount = fLimit = 0;
return B_ERROR;
}
uint32 maxSize = fBlockSize;
if (fVolume->HasMetaGroupChecksumFeature())
maxSize -= sizeof(ext2_htree_tail);
if (fLimit != maxSize / sizeof(HTreeEntry) - fFirstEntry) {
ERROR("HTreeEntryIterator::Init() bad fLimit %u should be %" B_PRIu32
" at block %" B_PRIu64 "\n", fLimit,
(uint32)(maxSize / sizeof(HTreeEntry) - fFirstEntry), fBlockNum);
fCount = fLimit = 0;
return B_ERROR;
}
TRACE("HTreeEntryIterator::Init() count %u limit %u\n",
fCount, fLimit);
return B_OK;
}
HTreeEntryIterator::~HTreeEntryIterator()
{
TRACE("HTreeEntryIterator::~HTreeEntryIterator(): %p, parent: %p\n", this,
fParent);
delete fParent;
TRACE("HTreeEntryIterator::~HTreeEntryIterator(): Deleted the parent\n");
}
status_t
HTreeEntryIterator::Lookup(uint32 hash, int indirections,
DirectoryIterator** directoryIterator, bool& detachRoot)
{
TRACE("HTreeEntryIterator::Lookup()\n");
if (fCount == 0)
return B_ENTRY_NOT_FOUND;
CachedBlock cached(fVolume);
const uint8* block = cached.SetTo(fBlockNum);
if (block == NULL) {
ERROR("Failed to read htree entry block.\n");
*directoryIterator = new(std::nothrow)
DirectoryIterator(fDirectory);
if (*directoryIterator == NULL)
return B_NO_MEMORY;
return B_OK;
}
HTreeEntry* start = (HTreeEntry*)block + fCurrentEntry + 1;
HTreeEntry* end = (HTreeEntry*)block + fCount + fFirstEntry - 1;
HTreeEntry* middle = start;
TRACE("HTreeEntryIterator::Lookup() current entry: %u\n",
fCurrentEntry);
TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
indirections, start, middle, end);
while (start <= end) {
middle = (HTreeEntry*)((end - start) / 2
+ start);
TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
indirections, start, middle, end);
TRACE("HTreeEntryIterator::Lookup() %" B_PRIx32 " %" B_PRIx32 "\n",
hash, middle->Hash());
if (hash >= middle->Hash())
start = middle + 1;
else
end = middle - 1;
}
--start;
fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry);
if (indirections == 0) {
TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory "
"iterator starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32
"\n", start->Block(), start->Hash());
*directoryIterator = new(std::nothrow)
DirectoryIterator(fDirectory, start->Block() * fBlockSize, this);
if (*directoryIterator == NULL)
return B_NO_MEMORY;
detachRoot = true;
return B_OK;
}
TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator "
"starting at block: %" B_PRIu32 ", hash: 0x%" B_PRIx32 "\n",
start->Block(), start->Hash());
fsblock_t blockNum;
status_t status = fDirectory->FindBlock(start->Block() * fBlockSize,
blockNum);
if (status != B_OK)
return status;
delete fChild;
fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize,
fDirectory, this, (start->Hash() & 1) == 1);
if (fChild == NULL)
return B_NO_MEMORY;
status = fChild->Init();
if (status != B_OK)
return status;
return fChild->Lookup(hash, indirections - 1, directoryIterator,
detachRoot);
}
status_t
HTreeEntryIterator::GetNext(uint32& childBlock)
{
fCurrentEntry++;
TRACE("HTreeEntryIterator::GetNext(): current entry: %u count: %u, "
"limit: %u\n", fCurrentEntry, fCount, fLimit);
bool endOfBlock = fCurrentEntry >= (fCount + fFirstEntry);
if (endOfBlock) {
TRACE("HTreeEntryIterator::GetNext(): end of entries in the block\n");
if (fParent == NULL) {
TRACE("HTreeEntryIterator::GetNext(): block was the root block\n");
return B_ENTRY_NOT_FOUND;
}
uint32 logicalBlock;
status_t status = fParent->GetNext(logicalBlock);
if (status != B_OK)
return status;
TRACE("HTreeEntryIterator::GetNext(): moving to next block: %" B_PRIx32
"\n", logicalBlock);
status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum);
if (status != B_OK)
return status;
fFirstEntry = 1;
fCurrentEntry = 1;
status = Init();
if (status != B_OK)
return status;
fHasCollision = fParent->HasCollision();
}
CachedBlock cached(fVolume);
const uint8* block = cached.SetTo(fBlockNum);
if (block == NULL)
return B_IO_ERROR;
HTreeEntry* entry = &((HTreeEntry*)block)[fCurrentEntry];
if (!endOfBlock)
fHasCollision = (entry[fCurrentEntry].Hash() & 1) == 1;
TRACE("HTreeEntryIterator::GetNext(): next block: %" B_PRIu32 "\n",
entry->Block());
childBlock = entry->Block();
return B_OK;
}
uint32
HTreeEntryIterator::BlocksNeededForNewEntry()
{
TRACE("HTreeEntryIterator::BlocksNeededForNewEntry(): block num: %"
B_PRIu64 ", volume: %p\n", fBlockNum, fVolume);
CachedBlock cached(fVolume);
const uint8* blockData = cached.SetTo(fBlockNum);
const HTreeEntry* entries = (const HTreeEntry*)blockData;
const HTreeCountLimit* countLimit =
(const HTreeCountLimit*)&entries[fFirstEntry];
uint32 newBlocks = 0;
if (countLimit->IsFull()) {
newBlocks++;
if (fParent != NULL)
newBlocks += fParent->BlocksNeededForNewEntry();
else {
HTreeRoot* root = (HTreeRoot*)entries;
if (root->indirection_levels == 1) {
return B_DEVICE_FULL;
}
newBlocks++;
}
}
return newBlocks;
}
status_t
HTreeEntryIterator::InsertEntry(Transaction& transaction, uint32 hash,
off_t blockNum, off_t newBlocksPos, bool hasCollision)
{
TRACE("HTreeEntryIterator::InsertEntry(): block num: %" B_PRIu64 "\n",
fBlockNum);
CachedBlock cached(fVolume);
uint8* blockData = cached.SetToWritable(transaction, fBlockNum);
if (blockData == NULL)
return B_IO_ERROR;
HTreeEntry* entries = (HTreeEntry*)blockData;
HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry];
uint16 count = countLimit->Count();
if (count == countLimit->Limit()) {
TRACE("HTreeEntryIterator::InsertEntry(): Splitting the node\n");
panic("Splitting a HTree node required, but isn't yet fully "
"supported\n");
fsblock_t physicalBlock;
status_t status = fDirectory->FindBlock(newBlocksPos, physicalBlock);
if (status != B_OK)
return status;
CachedBlock secondCached(fVolume);
uint8* secondBlockData = secondCached.SetToWritable(transaction,
physicalBlock);
if (secondBlockData == NULL)
return B_IO_ERROR;
uint32 maxSize = fBlockSize;
if (fVolume->HasMetaGroupChecksumFeature())
maxSize -= sizeof(ext2_dir_entry_tail);
HTreeFakeDirEntry* fakeEntry = (HTreeFakeDirEntry*)secondBlockData;
fakeEntry->inode_id = 0;
fakeEntry->SetEntryLength(fBlockSize);
fakeEntry->name_length = 0;
fakeEntry->file_type = 0;
HTreeEntry* secondBlockEntries = (HTreeEntry*)secondBlockData;
memmove(&entries[fFirstEntry + count / 2], &secondBlockEntries[1],
(count - count / 2) * sizeof(HTreeEntry));
_SetHTreeEntryChecksum(secondBlockData);
}
TRACE("HTreeEntryIterator::InsertEntry(): Inserting node. Count: %u, "
"current entry: %u\n", count, fCurrentEntry);
if (count > 0) {
TRACE("HTreeEntryIterator::InsertEntry(): memmove(%u, %u, %u)\n",
fCurrentEntry + 2, fCurrentEntry + 1, count + fFirstEntry
- fCurrentEntry - 1);
memmove(&entries[fCurrentEntry + 2], &entries[fCurrentEntry + 1],
(count + fFirstEntry - fCurrentEntry - 1) * sizeof(HTreeEntry));
}
if (fCurrentEntry == fFirstEntry) {
entries[fCurrentEntry + 1].SetHash(hash);
} else {
uint32 oldHash = entries[fCurrentEntry].Hash();
entries[fCurrentEntry].SetHash(hasCollision ? oldHash | 1 : oldHash & ~1);
entries[fCurrentEntry + 1].SetHash((oldHash & 1) == 0 ? hash & ~1
: hash | 1);
}
entries[fCurrentEntry + 1].SetBlock(blockNum);
fCount = count + 1;
countLimit->SetCount(fCount);
_SetHTreeEntryChecksum(blockData);
return B_OK;
}
ext2_htree_tail*
HTreeEntryIterator::_HTreeEntryTail(uint8* block) const
{
HTreeEntry* entries = (HTreeEntry*)block;
HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[fFirstEntry];
uint16 limit = countLimit->Limit();
return (ext2_htree_tail*)(&entries[fFirstEntry + limit]);
}
uint32
HTreeEntryIterator::_Checksum(uint8* block) const
{
uint32 number = fDirectory->ID();
uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(),
(uint8*)&number, sizeof(number));
uint32 gen = fDirectory->Node().generation;
checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen));
checksum = calculate_crc32c(checksum, block,
(fFirstEntry + fCount) * sizeof(HTreeEntry));
ext2_htree_tail dummy = {};
checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy));
return checksum;
}
void
HTreeEntryIterator::_SetHTreeEntryChecksum(uint8* block)
{
if (fVolume->HasMetaGroupChecksumFeature()) {
ext2_htree_tail* tail = _HTreeEntryTail(block);
tail->reserved = 0;
tail->checksum = _Checksum(block);
}
}
