[haiku-commits] r37295 - haiku/trunk/src/add-ons/kernel/file_systems/ext2

  • From: korli@xxxxxxxxxxxxxxxx
  • To: haiku-commits@xxxxxxxxxxxxx
  • Date: Mon, 28 Jun 2010 23:38:38 +0200 (CEST)

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 ...]

Other related posts:

  • » [haiku-commits] r37295 - haiku/trunk/src/add-ons/kernel/file_systems/ext2 - korli