Author: korli Date: 2010-06-28 23:38:37 +0200 (Mon, 28 Jun 2010) New Revision: 37295 Changeset: http://dev.haiku-os.org/changeset/37295/haiku Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.h haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp haiku/trunk/src/add-ons/kernel/file_systems/ext2/Jamfile haiku/trunk/src/add-ons/kernel/file_systems/ext2/Volume.h haiku/trunk/src/add-ons/kernel/file_systems/ext2/ext2.h haiku/trunk/src/add-ons/kernel/file_systems/ext2/kernel_interface.cpp Log: Patch from Janito Ferreira Filho with fixes by myself: Ext3 Indexed Directory Lookup (as part of GSOC). Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp 2010-06-28 20:43:37 UTC (rev 37294) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp 2010-06-28 21:38:37 UTC (rev 37295) @@ -8,6 +8,7 @@ #include <string.h> +#include "HTree.h" #include "Inode.h" @@ -35,8 +36,10 @@ status_t DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id) { - if (fOffset + sizeof(ext2_dir_entry) >= fInode->Size()) + if (fOffset + sizeof(ext2_dir_entry) >= fInode->Size()) { + TRACE("DirectoryIterator::GetNext() out of entries\n"); return B_ENTRY_NOT_FOUND; + } ext2_dir_entry entry; @@ -54,6 +57,7 @@ break; fOffset += entry.Length(); + TRACE("DirectoryIterator::GetNext() skipping entry\n"); } TRACE("offset %Ld: entry ino %lu, length %u, name length %u, type %u\n", Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h 2010-06-28 20:43:37 UTC (rev 37294) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h 2010-06-28 21:38:37 UTC (rev 37295) @@ -14,18 +14,18 @@ class DirectoryIterator { public: DirectoryIterator(Inode* inode); - ~DirectoryIterator(); + virtual ~DirectoryIterator(); - status_t GetNext(char* name, size_t* _nameLength, ino_t* id); + virtual status_t GetNext(char* name, size_t* _nameLength, ino_t* id); - status_t Rewind(); + virtual status_t Rewind(); private: DirectoryIterator(const DirectoryIterator&); DirectoryIterator &operator=(const DirectoryIterator&); // no implementation -private: +protected: Inode* fInode; off_t fOffset; }; Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,376 @@ +/* + * 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 "HTree.h" + +#include <new> +#include <string.h> + +#include "HTreeEntryIterator.h" +#include "Inode.h" +#include "Volume.h" + + +//#define TRACE_EXT2 +#ifdef TRACE_EXT2 +# define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) +#else +# define TRACE(x...) ; +#endif + + +bool +HTreeRoot::IsValid() const +{ + if (reserved != 0) + return false; + if (hash_version != HTREE_HASH_LEGACY + && hash_version != HTREE_HASH_HALF_MD4 + && hash_version != HTREE_HASH_TEA) + return false; + if (root_info_length != 8) + return false; + if (indirection_levels > 1) + return false; + + // TODO: Maybe we should check the false directory entries too? + + return true; +} + + +HTree::HTree(Volume* volume, Inode* directory) + : + fDirectory(directory), + fRootEntry(NULL) +{ + fBlockSize = volume->BlockSize(); + fIndexed = volume->IndexedDirectories() + && (directory->Flags() & EXT2_INODE_INDEXED) != 0; + + ext2_super_block superBlock = volume->SuperBlock(); + fHashSeed[0] = superBlock.HashSeed(0); + fHashSeed[1] = superBlock.HashSeed(1); + fHashSeed[2] = superBlock.HashSeed(2); + fHashSeed[3] = superBlock.HashSeed(3); + + TRACE("HTree::HTree() %lx %lx %lx %lx\n", fHashSeed[0], + fHashSeed[1], fHashSeed[2], fHashSeed[3]); + + if (fHashSeed[0] == 0 && fHashSeed[1] == 0 && fHashSeed[2] == 0 + && fHashSeed[3] == 0) { + fHashSeed[0] = 0x67452301; + fHashSeed[1] = 0xefcdab89; + fHashSeed[2] = 0x98badcfe; + fHashSeed[3] = 0x10325476; + } +} + + +HTree::~HTree() +{ +} + + +status_t +HTree::Lookup(const char* name, DirectoryIterator** iterator) +{ + if (!fIndexed || (name[0] == '.' + && (name[1] == '\0' || (name[1] == '.' && name[2] == '0')))) { + // No HTree support or looking for trivial directories + // TODO: Does these directories get hashed? + *iterator = new(std::nothrow) DirectoryIterator(fDirectory); + + if (*iterator == NULL) + return B_NO_MEMORY; + return B_OK; + } + + HTreeRoot root; + size_t length = sizeof(root); + + status_t status = fDirectory->ReadAt(0, (uint8*)&root, &length); + if (status < B_OK) + return status; + + if (length != sizeof(root) || !root.IsValid()) { + // Fallback to linear search + *iterator = new(std::nothrow) DirectoryIterator(fDirectory); + if (*iterator == NULL) + return B_NO_MEMORY; + + return B_OK; + } + + uint32 hash = _Hash(name, root.hash_version); + + off_t start = (off_t)root.root_info_length + + 2 * (sizeof(HTreeFakeDirEntry) + 4); + + fRootEntry = new(std::nothrow) HTreeEntryIterator(start, fDirectory); + if (fRootEntry == NULL) + return B_NO_MEMORY; + + fRootDeleter.SetTo(fRootEntry); + status = fRootEntry->Init(); + if (status != B_OK) + return status; + + return fRootEntry->Lookup(hash, (uint32)root.indirection_levels, iterator); +} + + +uint32 +HTree::_Hash(const char* name, uint8 version) +{ + uint32 hash; + + switch (version) { + case HTREE_HASH_LEGACY: + hash = _HashLegacy(name); + break; + case HTREE_HASH_HALF_MD4: + hash = _HashHalfMD4(name); + break; + case HTREE_HASH_TEA: + hash = _HashTEA(name); + break; + default: + panic("Hash verification succeeded but then failed?"); + hash = 0; + }; + + TRACE("Filename hash: %u\n", hash); + + return hash & ~1; +} + + +uint32 +HTree::_HashLegacy(const char* name) +{ + uint32 hash = 0x12a3fe2d; + uint32 previous = 0x37abe8f9; + + for (; *name != '\0'; ++name) { + uint32 next = previous + (hash ^ (*name * 7152373)); + + if ((next & 0x80000000) != 0) + next -= 0x7fffffff; + + previous = hash; + hash = next; + } + + return hash; +} + + +/*inline*/ uint32 +HTree::_MD4F(uint32 x, uint32 y, uint32 z) +{ + return z ^ (x & (y ^ z)); +} + + +/*inline*/ uint32 +HTree::_MD4G(uint32 x, uint32 y, uint32 z) +{ + return (x & y) + ((x ^ y) & z); +} + + +/*inline*/ uint32 +HTree::_MD4H(uint32 x, uint32 y, uint32 z) +{ + return x ^ y ^ z; +} + + +/*inline*/ void +HTree::_MD4RotateVars(uint32& a, uint32& b, uint32& c, uint32& d) +{ + uint32 oldD = d; + d = c; + c = b; + b = a; + a = oldD; +} + + +void +HTree::_HalfMD4Transform(uint32 buffer[4], uint32 blocks[8]) +{ + uint32 a, b, c, d; + + a = buffer[0]; + b = buffer[1]; + c = buffer[2]; + d = buffer[3]; + + // Round 1 + uint32 shifts[4] = { 3, 7, 11, 19 }; + + for (int i = 0; i < 8; ++i) { + a += _MD4F(b, c, d) + blocks[i]; + uint32 shift = shifts[i % 4]; + a = (a << shift) | (a >> (32 - shift)); + + _MD4RotateVars(a, b, c, d); + } + + // Round 2 + shifts[1] = 5; + shifts[2] = 9; + shifts[3] = 13; + + for (int j = 0; j < 2; ++j) { + for (int i = j; i < 4; i += 2) { + a += _MD4G(b, c, d) + blocks[i] + 013240474631UL; + uint32 shift = shifts[i / 2]; + a = (a << shift) | (a >> (32 - shift)); + + _MD4RotateVars(a, b, c, d); + } + } + + // Round 3 + shifts[1] = 9; + shifts[2] = 11; + shifts[3] = 15; + + for (int i = 0; i < 4; ++i) { + a += _MD4H(b, c, d) + blocks[3 - i] + 015666365641UL; + uint32 shift = shifts[i*2]; + a = (a << shift) | (a >> (32 - shift)); + + _MD4RotateVars(a, b, c, d); + + a += _MD4H(b, c, d) + blocks[7 - i] + 015666365641UL; + shift = shifts[i*2 + 1]; + a = (a << shift) | (a >> (32 - shift)); + + _MD4RotateVars(a, b, c, d); + } + + buffer[0] += a; + buffer[1] += b; + buffer[2] += c; + buffer[3] += d; +} + + +uint32 +HTree::_HashHalfMD4(const char* name) +{ + uint32 buffer[4]; + + buffer[0] = fHashSeed[0]; + buffer[1] = fHashSeed[1]; + buffer[2] = fHashSeed[2]; + buffer[3] = fHashSeed[3]; + + for (int length = strlen(name); length > 0; length -= 32) { + uint32 blocks[8]; + + _PrepareBlocksForHash(name, length, blocks, 8); + _HalfMD4Transform(buffer, blocks); + + name += 32; + } + + return buffer[1]; +} + + +void +HTree::_TEATransform(uint32 buffer[4], uint32 blocks[4]) +{ + uint32 x, y; + x = buffer[0]; + y = buffer[1]; + + uint32 a, b, c, d; + a = blocks[0]; + b = blocks[1]; + c = blocks[2]; + d = blocks[3]; + + uint32 sum = 0; + + for (int i = 16; i > 0; --i) { + sum += 0x9E3779B9; + x += ((y << 4) + a) ^ (y + sum) ^ ((y >> 5) + b); + y += ((x << 4) + c) ^ (x + sum) ^ ((x >> 5) + d); + } + + buffer[0] += x; + buffer[1] += y; +} + + +uint32 +HTree::_HashTEA(const char* name) +{ + uint32 buffer[4]; + + buffer[0] = fHashSeed[0]; + buffer[1] = fHashSeed[1]; + buffer[2] = fHashSeed[2]; + buffer[3] = fHashSeed[3]; + + for (int length = strlen(name); length > 0; length -= 16) { + uint32 blocks[4]; + + _PrepareBlocksForHash(name, length, blocks, 4); + TRACE("_HashTEA %lx %lx %lx\n", blocks[0], blocks[1], blocks[2]); + _TEATransform(buffer, blocks); + + name += 16; + } + + return buffer[0]; +} + + +void +HTree::_PrepareBlocksForHash(const char* string, int length, uint32* blocks, + int numBlocks) +{ + uint32 padding = (uint32)length; + padding = (padding << 8) | padding; + padding = (padding << 16) | padding; + + int numBytes = numBlocks * 4; + if (length > numBytes) + length = numBytes; + + int completeIterations = length / 4; + + for (int i = 0; i < completeIterations; ++i) { + uint32 value = 0 | *(string++); + value = (value << 8) | *(string++); + value = (value << 8) | *(string++); + value = (value << 8) | *(string++); + blocks[i] = value; + } + + if (completeIterations < numBlocks) { + int remainingBytes = length % 4; + + uint32 value = padding; + for (int i = 0; i < remainingBytes; ++i) + value = (value << 8) + *(string++); + + blocks[completeIterations] = value; + + for (int i = completeIterations + 1; i < numBlocks; ++i) + blocks[i] = padding; + } +} Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.h =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.h (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.h 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,134 @@ +/* + * Copyright 2010, Haiku Inc. All rights reserved. + * This file may be used under the terms of the MIT License. + * + * Authors: + * Janito V. Ferreira Filho + */ +#ifndef HTREE_H +#define HTREE_H + + +#include <AutoDeleter.h> + +#include "ext2.h" +#include "DirectoryIterator.h" +#include "HTreeEntryIterator.h" +#include "Inode.h" + + +#define HTREE_HASH_LEGACY 0 +#define HTREE_HASH_HALF_MD4 1 +#define HTREE_HASH_TEA 2 + + +struct JournalRevokeHeader; + + +struct HTreeFakeDirEntry { + uint32 inode_num; + uint16 entry_length; + uint8 name_length; + uint8 file_type; + char file_name[0]; + + uint32 Inode() + { return B_LENDIAN_TO_HOST_INT32(inode_num); } +} _PACKED; + +struct HTreeCountLimit { + uint16 limit; + uint16 count; + + uint16 Limit() const + { return B_LENDIAN_TO_HOST_INT32(limit); } + uint16 Count() const + { return B_LENDIAN_TO_HOST_INT32(count); } +} _PACKED; + +struct HTreeEntry { + uint32 hash; + uint32 block; + + uint32 Hash() const + { return B_LENDIAN_TO_HOST_INT32(hash); } + uint32 Block() const + { return B_LENDIAN_TO_HOST_INT32(block); } +} _PACKED; + +struct HTreeRoot { + HTreeFakeDirEntry dot; + char dot_entry_name[4]; + HTreeFakeDirEntry dotdot; + char dotdot_entry_name[4]; + + uint32 reserved; + uint8 hash_version; + uint8 root_info_length; + uint8 indirection_levels; + uint8 flags; + + bool IsValid() const; + // Implemented in HTree.cpp +} _PACKED; + +struct HTreeIndirectNode { + HTreeFakeDirEntry fake_entry; + HTreeEntry entries[0]; +} _PACKED; + + +/*! Hash implementations: + * References: + * Main reference: Linux htree patch: + * http://thunk.org/tytso/linux/ext3-dxdir/patch-ext3-dxdir-2.5.40 + * Original MD4 hash: (Modified version used) + * http://tools.ietf.org/html/rfc1320 + * TEA Wikipedia article: (Modified version used) + * http://en.wikipedia.org/Tiny_Encryption_Algorithm + */ + + +class HTree { +public: + HTree(Volume* volume, Inode* directory); + ~HTree(); + + status_t Lookup(const char* name, + DirectoryIterator** directory); + +private: + status_t _LookupInNode(uint32 hash, off_t& firstEntry, + off_t& lastEntry, + uint32 remainingIndirects); + + uint32 _Hash(const char* name, uint8 version); + + uint32 _HashLegacy(const char* name); + + inline uint32 _MD4F(uint32 x, uint32 y, uint32 z); + inline uint32 _MD4G(uint32 x, uint32 y, uint32 z); + inline uint32 _MD4H(uint32 x, uint32 y, uint32 z); + inline void _MD4RotateVars(uint32& a, uint32& b, + uint32& c, uint32& d); + void _HalfMD4Transform(uint32 buffer[4], + uint32 blocks[8]); + uint32 _HashHalfMD4(const char* name); + + void _TEATransform(uint32 buffer[4], + uint32 blocks[4]); + uint32 _HashTEA(const char* name); + + void _PrepareBlocksForHash(const char* string, + int length, uint32* blocks, int numBlocks); + + bool fIndexed; + uint32 fBlockSize; + Inode* fDirectory; + uint32 fHashSeed[4]; + HTreeEntryIterator* fRootEntry; + ObjectDeleter<HTreeEntryIterator> fRootDeleter; +}; + +#endif // HTREE_H + Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,220 @@ +/* + * 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 "HTree.h" +#include "IndexedDirectoryIterator.h" +#include "Inode.h" + + +//#define TRACE_EXT2 +#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) + : + fHasCollision(false), + fDirectory(directory), + fOffset(offset), + fParent(NULL), + fChild(NULL) +{ + fBlockSize = fDirectory->GetVolume()->BlockSize(); +} + + +HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize, + Inode* directory, HTreeEntryIterator* parent, bool hasCollision) + : + fHasCollision(hasCollision), + fBlockSize(blockSize), + fDirectory(directory), + fOffset(block * blockSize + sizeof(HTreeFakeDirEntry)), + fParent(parent), + fChild(NULL) +{ + TRACE("HTreeEntryIterator::HTreeEntryIterator() block %ld offset %Lx\n", + block, fOffset); +} + + +status_t +HTreeEntryIterator::Init() +{ + size_t length = sizeof(HTreeCountLimit); + HTreeCountLimit countLimit; + + status_t status = fDirectory->ReadAt(fOffset, (uint8*)&countLimit, + &length); + + if (status != B_OK) + return status; + + if (length != sizeof(HTreeCountLimit)) { + ERROR("HTreeEntryIterator::Init() bad length %ld fOffset 0x%Lx\n", + length, fOffset); + fCount = fLimit = 0; + return B_ERROR; + } + + fCount = countLimit.Count(); + fLimit = countLimit.Limit(); + + if (fCount >= fLimit) { + ERROR("HTreeEntryIterator::Init() bad fCount %d fOffset 0x%Lx\n", + fCount, fOffset); + fCount = fLimit = 0; + return B_ERROR; + } + + if (fParent != NULL && + fLimit != ((fBlockSize - sizeof(HTreeFakeDirEntry)) + / sizeof(HTreeEntry)) ) { + ERROR("HTreeEntryIterator::Init() bad fLimit %d should be %ld " + "fOffset 0x%Lx\n", fLimit, (fBlockSize - sizeof(HTreeFakeDirEntry)) + / sizeof(HTreeEntry), fOffset); + fCount = fLimit = 0; + return B_ERROR; + } + + TRACE("HTreeEntryIterator::Init() count 0x%x limit 0x%x\n", fCount, + fLimit); + + fMaxOffset = fOffset + (fCount - 1) * sizeof(HTreeEntry); + + return B_OK; +} + + +HTreeEntryIterator::~HTreeEntryIterator() +{ +} + + +status_t +HTreeEntryIterator::Lookup(uint32 hash, int indirections, + DirectoryIterator** directoryIterator) +{ + off_t start = fOffset + sizeof(HTreeEntry); + off_t end = fMaxOffset; + off_t middle = start; + size_t entrySize = sizeof(HTreeEntry); + HTreeEntry entry; + + while (start <= end) { + middle = (end - start) / 2; + middle -= middle % entrySize; // Alignment + middle += start; + + TRACE("HTreeEntryIterator::Lookup() %d 0x%Lx 0x%Lx 0x%Lx\n", + indirections, start, end, middle); + + status_t status = fDirectory->ReadAt(middle, (uint8*)&entry, + &entrySize); + + TRACE("HTreeEntryIterator::Lookup() %lx %lx\n", hash, entry.Hash()); + + if (status != B_OK) + return status; + else if (entrySize != sizeof(entry)) { + // Fallback to linear search + *directoryIterator = new(std::nothrow) + DirectoryIterator(fDirectory); + + if (*directoryIterator == NULL) + return B_NO_MEMORY; + + return B_OK; + } + + if (hash >= entry.Hash()) + start = middle + entrySize; + else + end = middle - entrySize; + } + + status_t status = fDirectory->ReadAt(start - entrySize, (uint8*)&entry, + &entrySize); + if (status != B_OK) + return status; + + if (indirections == 0) { + *directoryIterator = new(std::nothrow) + IndexedDirectoryIterator(entry.Block() * fBlockSize, fBlockSize, + fDirectory, this); + + if (*directoryIterator == NULL) + return B_NO_MEMORY; + + return B_OK; + } + + delete fChild; + + fChild = new(std::nothrow) HTreeEntryIterator(entry.Block(), fBlockSize, + fDirectory, this, entry.Hash() & 1 == 1); + + if (fChild == NULL) + return B_NO_MEMORY; + fChildDeleter.SetTo(fChild); + + status = fChild->Init(); + if (status != B_OK) + return status; + + return fChild->Lookup(hash, indirections - 1, directoryIterator); +} + + +status_t +HTreeEntryIterator::GetNext(off_t& childOffset) +{ + size_t entrySize = sizeof(HTreeEntry); + fOffset += entrySize; + bool firstEntry = fOffset >= fMaxOffset; + + if (firstEntry) { + if (fParent == NULL) + return B_ENTRY_NOT_FOUND; + + status_t status = fParent->GetNext(fOffset); + if (status != B_OK) + return status; + + status = Init(); + if (status != B_OK) + return status; + + fHasCollision = fParent->HasCollision(); + } + + HTreeEntry entry; + status_t status = fDirectory->ReadAt(fOffset, (uint8*)&entry, &entrySize); + if (status != B_OK) + return status; + else if (entrySize != sizeof(entry)) { + // Weird error, try to skip it + return GetNext(childOffset); + } + + if (!firstEntry) + fHasCollision = (entry.Hash() & 1) == 1; + + childOffset = entry.Block() * fBlockSize; + + return B_OK; +} Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,50 @@ +/* + * Copyright 2010, Haiku Inc. All rights reserved. + * This file may be used under the terms of the MIT License. + * + * Authors: + * Janito V. Ferreira Filho + */ +#ifndef HTREE_ENTRY_ITERATOR_H +#define HTREE_ENTRY_ITERATOR_H + + +#include <AutoDeleter.h> + +#include "DirectoryIterator.h" + + +class HTreeEntryIterator { +public: + HTreeEntryIterator(off_t offset, + Inode* directory); + ~HTreeEntryIterator(); + + status_t Init(); + + status_t Lookup(uint32 hash, int indirections, + DirectoryIterator** iterator); + bool HasCollision() { return fHasCollision; } + + status_t GetNext(off_t& offset); +private: + HTreeEntryIterator(uint32 block, + uint32 blockSize, Inode* directory, + HTreeEntryIterator* parent, + bool hasCollision); + +private: + bool fHasCollision; + uint16 fLimit, fCount; + + uint32 fBlockSize; + Inode* fDirectory; + off_t fOffset; + off_t fMaxOffset; + + HTreeEntryIterator* fParent; + HTreeEntryIterator* fChild; + ObjectDeleter<HTreeEntryIterator> fChildDeleter; +}; + +#endif // HTREE_ENTRY_ITERATOR_H Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,75 @@ +/* + * 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 "IndexedDirectoryIterator.h" + +#include "ext2.h" +#include "HTree.h" +#include "HTreeEntryIterator.h" +#include "Inode.h" + + +//#define TRACE_EXT2 +#ifdef TRACE_EXT2 +# define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) +#else +# define TRACE(x...) ; +#endif + + +IndexedDirectoryIterator::IndexedDirectoryIterator(off_t start, + uint32 blockSize, Inode* directory, HTreeEntryIterator* parent) + : + DirectoryIterator(directory), + fIndexing(true), + + fParent(parent), + fMaxOffset(start + blockSize), + fBlockSize(blockSize), + fMaxAttempts(0) +{ + fOffset = start; +} + + +IndexedDirectoryIterator::~IndexedDirectoryIterator() +{ +} + + +status_t +IndexedDirectoryIterator::GetNext(char* name, size_t* nameLength, ino_t* id) +{ + if (fIndexing && fOffset + sizeof(HTreeFakeDirEntry) >= fMaxOffset) { + TRACE("IndexedDirectoryIterator::GetNext() calling next block\n"); + status_t status = fParent->GetNext(fOffset); + if (status != B_OK) + return status; + + if (fMaxAttempts++ > 4) + return B_ERROR; + + fMaxOffset = fOffset + fBlockSize; + } + + return DirectoryIterator::GetNext(name, nameLength, id); +} + + +status_t +IndexedDirectoryIterator::Rewind() +{ + // The only way to rewind it is too loose indexing + + fOffset = 0; + fMaxOffset = fInode->Size(); + fIndexing = false; + + return B_OK; +} Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h (rev 0) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h 2010-06-28 21:38:37 UTC (rev 37295) @@ -0,0 +1,36 @@ +/* + * Copyright 2010, Haiku Inc. All rights reserved. + * This file may be used under the terms of the MIT License. + * + * Authors: + * Janito V. Ferreira Filho + */ +#ifndef INDEXED_DIRECTORY_ITERATOR_H +#define INDEXED_DIRECTORY_ITERATOR_H + + +#include "DirectoryIterator.h" + + +class HTreeEntryIterator; + +class IndexedDirectoryIterator : public DirectoryIterator { +public: + IndexedDirectoryIterator(off_t start, + uint32 blockSize, Inode* directory, + HTreeEntryIterator* parent); + virtual ~IndexedDirectoryIterator(); + + status_t GetNext(char* name, size_t* nameLength, + ino_t* id); + + status_t Rewind(); +private: + bool fIndexing; + HTreeEntryIterator* fParent; + off_t fMaxOffset; + uint32 fBlockSize; + uint32 fMaxAttempts; +}; + +#endif // INDEXED_DIRECTORY_ITERATOR_H Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp =================================================================== --- haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp 2010-06-28 20:43:37 UTC (rev 37294) +++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp 2010-06-28 21:38:37 UTC (rev 37295) @@ -202,10 +202,13 @@ size_t length = *_length; // set/check boundaries for pos/length - if (pos < 0) + if (pos < 0) { + TRACE("inode %Ld: ReadAt failed(pos %Ld, length %lu)\n", ID(), pos, length); return B_BAD_VALUE; [... truncated: 154 lines follow ...]