Index: src/add-ons/kernel/file_systems/ext2/InodeJournal.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/InodeJournal.h (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/InodeJournal.h (revision 0)
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef INODEJOURNAL_H
+#define INODEJOURNAL_H
+
+
+#include "Inode.h"
+#include "Journal.h"
+
+
+class InodeJournal : public Journal {
+public:
+                       InodeJournal(Inode* inode);
+                       ~InodeJournal();
+
+           status_t    InitCheck();
+
+           status_t    MapBlock(uint32 logical, uint32& physical);
+private:
+           Inode*      fInode;
+           status_t    fInitStatus;
+};
+
+#endif // INODEJOURNAL_H
Index: src/add-ons/kernel/file_systems/ext2/InodeAllocator.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/InodeAllocator.cpp (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/InodeAllocator.cpp (revision 0)
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "InodeAllocator.h"
+
+#include <util/AutoLock.h>
+
+#include "BitmapBlock.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
+
+
+InodeAllocator::InodeAllocator(Volume* volume)
+   :
+   fVolume(volume)
+{
+   mutex_init(&fLock, "ext2 inode allocator");
+}
+
+
+InodeAllocator::~InodeAllocator()
+{
+   mutex_destroy(&fLock);
+}
+
+
+/*virtual*/ status_t
+InodeAllocator::New(Transaction& transaction, Inode* parent, int32 mode,
+   ino_t& id)
+{
+   // Apply allocation policy
+   uint32 preferredBlockGroup = parent->ID()
+       / parent->GetVolume()->InodesPerGroup();
+
+   return _Allocate(transaction, preferredBlockGroup, id);
+}
+
+
+status_t
+InodeAllocator::_Allocate(Transaction& transaction, uint32 preferredBlockGroup,
+   ino_t& id)
+{
+   MutexLocker lock(fLock);
+
+   uint32 blockGroup = preferredBlockGroup;
+   uint32 lastBlockGroup = fVolume->NumGroups() - 1;
+
+   for (int i = 0; i < 2; ++i) {
+       for (; blockGroup < lastBlockGroup; ++blockGroup) {
+           ext2_block_group* group;
+
+           status_t status = fVolume->GetBlockGroup(blockGroup, &group);
+           if (status != B_OK)
+               return status;
+
+           if (group->FreeInodes() != 0) {
+               return _MarkInBitmap(transaction, group->InodeBitmap(),
+                   blockGroup, fVolume->InodesPerGroup(), id);
+           }
+       }
+
+       if (i == 0) {
+           ext2_block_group* group;
+
+           status_t status = fVolume->GetBlockGroup(blockGroup, &group);
+           if (status != B_OK)
+               return status;
+
+           if (group->FreeInodes() != 0) {
+               return _MarkInBitmap(transaction, group->InodeBitmap(),
+                   blockGroup, fVolume->NumInodes()
+                       - blockGroup * fVolume->InodesPerGroup(), id);
+           }
+       }
+
+       blockGroup = 0;
+       lastBlockGroup = preferredBlockGroup;
+   }
+
+   return B_DEVICE_FULL;
+}
+
+
+status_t
+InodeAllocator::_MarkInBitmap(Transaction& transaction, uint32 bitmapBlock,
+   uint32 blockGroup, uint32 numInodes, ino_t& id)
+{
+   BitmapBlock inodeBitmap(fVolume, numInodes);
+
+   if (!inodeBitmap.SetToWritable(transaction, bitmapBlock)) {
+       TRACE("Unable to open inode bitmap (block number: %lu) for block group "
+           "%lu\n", bitmapBlock, blockGroup);
+       return B_IO_ERROR;
+   }
+
+   uint32 pos = 0;
+   inodeBitmap.FindNextUnmarked(pos);
+
+   if (pos == inodeBitmap.NumBits()) {
+       TRACE("Even though the block group %lu indicates there are free "
+           "inodes, no unmarked bit was found in the inode bitmap at block "
+           "%lu.", blockGroup, bitmapBlock);
+       return B_ERROR;
+   }
+
+   inodeBitmap.Mark(pos, true);
+   id = pos + blockGroup * fVolume->InodesPerGroup();
+
+   return B_OK;
+}

Property changes on: src/add-ons/kernel/file_systems/ext2/InodeAllocator.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/BlockAllocator.h   (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/BlockAllocator.h   (revision 0)
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef BLOCKALLOCATOR_H
+#define BLOCKALLOCATOR_H
+
+#include <lock.h>
+
+#include "Transaction.h"
+
+
+class AllocationBlockGroup;
+class Inode;
+class Volume;
+
+
+class BlockAllocator {
+public:
+                       BlockAllocator(Volume* volume);
+                       ~BlockAllocator();
+
+           status_t    Initialize();
+
+           status_t    AllocateBlocks(Transaction& transaction,
+                           uint32 minimum, uint32 maximum, uint32& blockGroup,
+                           uint32& start, uint32& length);
+           status_t    Allocate(Transaction& transaction, Inode* inode,
+                           off_t numBlocks, uint32 minimum, uint32& start,
+                           uint32& length);
+           status_t    Free(Transaction& transaction, uint32 start,
+                           uint32 length);
+
+           uint32      FreeBlocks();
+
+protected:
+   static  status_t    _Initialize(BlockAllocator* allocator);
+
+
+           Volume*     fVolume;
+           mutex       fLock;
+
+           AllocationBlockGroup* fGroups;
+           uint32      fBlocksPerGroup;
+           uint32      fNumBlocks;
+           uint32      fNumGroups;
+           uint32      fFirstBlock;
+};
+
+#endif // BLOCKALLOCATOR_H

Property changes on: src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp (working copy)
@@ -11,6 +11,7 @@

 #include <new>

+#include "CachedBlock.h"
 #include "HTree.h"
 #include "IndexedDirectoryIterator.h"
 #include "Inode.h"
@@ -27,81 +28,92 @@

 HTreeEntryIterator::HTreeEntryIterator(off_t offset, Inode* directory)
    :
+   fDirectory(directory),
+   fVolume(directory->GetVolume()),
    fHasCollision(false),
-   fDirectory(directory),
-   fOffset(offset),
+   fBlockSize(directory->GetVolume()->BlockSize()),
    fParent(NULL),
    fChild(NULL)
 {
-   fBlockSize = fDirectory->GetVolume()->BlockSize();
+   fInitStatus = fDirectory->FindBlock(offset, fBlockNum);
+
+   if (fInitStatus == B_OK) {
+       fFirstEntry = offset % fBlockSize / sizeof(HTreeEntry);
+       fCurrentEntry = fFirstEntry;
+   }
+
+   TRACE("HTreeEntryIterator::HTreeEntryIterator() block %lu entry no. %lu\n",
+       fBlockNum, (uint32)fCurrentEntry);
 }


 HTreeEntryIterator::HTreeEntryIterator(uint32 block, uint32 blockSize,
    Inode* directory, HTreeEntryIterator* parent, bool hasCollision)
    :
+   fDirectory(directory),
+   fVolume(directory->GetVolume()),
    fHasCollision(hasCollision),
+   fFirstEntry(1),
+   fCurrentEntry(1),
    fBlockSize(blockSize),
-   fDirectory(directory),
-   fOffset(block * blockSize + sizeof(HTreeFakeDirEntry)),
+   fBlockNum(block),
    fParent(parent),
    fChild(NULL)
 {
-   TRACE("HTreeEntryIterator::HTreeEntryIterator() block %ld offset %Lx\n",
-       block, fOffset);
+   // fCurrentEntry is initialized to 1 to skip the fake directory entry
+   fInitStatus = B_OK;
+
+   TRACE("HTreeEntryIterator::HTreeEntryIterator() block %lu\n", block);
 }


 status_t
 HTreeEntryIterator::Init()
 {
-   size_t length = sizeof(HTreeCountLimit);
-   HTreeCountLimit countLimit;
+   TRACE("HTreeEntryIterator::Init() first entry: %lu\n",
+       (uint32)fFirstEntry);

-   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);
+   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_ERROR;
+       return B_IO_ERROR;
    }
-
-   fCount = countLimit.Count();
-   fLimit = countLimit.Limit();

+   HTreeCountLimit* countLimit = (HTreeCountLimit*)(
+       &((HTreeEntry*)block)[fFirstEntry]);
+
+   fCount = countLimit->Count();
+   fLimit = countLimit->Limit();
+
    if (fCount >= fLimit) {
-       ERROR("HTreeEntryIterator::Init() bad fCount %d fOffset 0x%Lx\n",
-           fCount, fOffset);
+       ERROR("HTreeEntryIterator::Init() bad fCount %lu\n", (uint32)fCount);
        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);
+   if (fLimit != fBlockSize / sizeof(HTreeEntry) - fFirstEntry) {
+       ERROR("HTreeEntryIterator::Init() bad fLimit %lu should be %lu "
+           "at block %lu\n", (uint32)fLimit, fBlockSize / sizeof(HTreeEntry)
+               - fFirstEntry, fBlockNum);
        fCount = fLimit = 0;
        return B_ERROR;
-   }
+   }

-   TRACE("HTreeEntryIterator::Init() count 0x%x limit 0x%x\n", fCount,
-       fLimit);
+   TRACE("HTreeEntryIterator::Init() count %lu limit %lu\n",
+       (uint32)fCount, (uint32)fLimit);

-   fMaxOffset = fOffset + (fCount - 1) * sizeof(HTreeEntry);
-
    return B_OK;
 }


 HTreeEntryIterator::~HTreeEntryIterator()
 {
+   delete fChild;
 }


@@ -109,68 +121,77 @@
 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;
+   TRACE("HTreeEntryIterator::Lookup()\n");
+   CachedBlock cached(fVolume);
+   const uint8* block = cached.SetTo(fBlockNum);
+   if (block == NULL) {
+       ERROR("Failed to read htree entry block.\n");
+       // Fallback to linear search
+       *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: %lu\n",
+       (uint32)fCurrentEntry);
+   TRACE("HTreeEntryIterator::Lookup() indirections: %d s:%p m:%p e:%p\n",
+       indirections, start, middle, end);
+
    while (start <= end) {
-       middle = (end - start) / 2;
-       middle -= middle % entrySize; // Alignment
-       middle += start;
+       middle = (HTreeEntry*)((end - start) / 2
+           + 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() indirections: %d s:%p m:%p e:%p\n",
+           indirections, start, middle, end);

-       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;
+       TRACE("HTreeEntryIterator::Lookup() %lx %lx\n", hash, middle->Hash());
+
+       if (hash >= middle->Hash())
+           start = middle + 1;
        else
-           end = middle - entrySize;
+           end = middle - 1;
    }

-   status_t status = fDirectory->ReadAt(start - entrySize, (uint8*)&entry,
-       &entrySize);
-   if (status != B_OK)
-       return status;
-
+   --start;
+
+   fCurrentEntry = ((uint8*)start - block) / sizeof(HTreeEntry);
+
    if (indirections == 0) {
+       TRACE("HTreeEntryIterator::Lookup(): Creating an indexed directory "
+           "iterator starting at block: %lu, hash: 0x%lX\n", start->Block(),
+           start->Hash());
        *directoryIterator = new(std::nothrow)
-           IndexedDirectoryIterator(entry.Block() * fBlockSize, fBlockSize,
-           fDirectory, this);
-
+           IndexedDirectoryIterator(start->Block() * fBlockSize, fDirectory,
+               this);
+
        if (*directoryIterator == NULL)
            return B_NO_MEMORY;

        return B_OK;
    }

+   TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator "
+       "starting at block: %lu, hash: 0x%lX\n", start->Block(), start->Hash());
+   uint32 blockNum;
+   status_t status = fDirectory->FindBlock(start->Block() * fBlockSize,
+       blockNum);
+   if (status != B_OK)
+       return status;
+
    delete fChild;

-   fChild = new(std::nothrow) HTreeEntryIterator(entry.Block(), fBlockSize,
-       fDirectory, this, entry.Hash() & 1 == 1);
-
+   fChild = new(std::nothrow) HTreeEntryIterator(blockNum, fBlockSize,
+       fDirectory, this, start->Hash() & 1 == 1);
    if (fChild == NULL)
        return B_NO_MEMORY;
-   fChildDeleter.SetTo(fChild);

    status = fChild->Init();
    if (status != B_OK)
@@ -181,40 +202,62 @@


 status_t
-HTreeEntryIterator::GetNext(off_t& childOffset)
+HTreeEntryIterator::GetNext(uint32& childBlock)
 {
-   size_t entrySize = sizeof(HTreeEntry);
-   fOffset += entrySize;
-   bool firstEntry = fOffset >= fMaxOffset;
-
-   if (firstEntry) {
-       if (fParent == NULL)
+   fCurrentEntry++;
+   TRACE("HTreeEntryIterator::GetNext(): current entry: %lu\n",
+       (uint32)fCurrentEntry);
+   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;
+       }

-       status_t status = fParent->GetNext(fOffset);
+       uint32 logicalBlock;
+       status_t status = fParent->GetNext(logicalBlock);
        if (status != B_OK)
            return status;

+       TRACE("HTreeEntryIterator::GetNext(): moving to next block: %lu\n",
+           logicalBlock);
+
+       status = fDirectory->FindBlock(logicalBlock * fBlockSize, fBlockNum);
+       if (status != B_OK)
+           return status;
+
+       fFirstEntry = 1; // Skip fake directory entry
+       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;

-   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);
-   }
+   TRACE("HTreeEntryIterator::GetNext(): next block: %lu\n",
+       entry->Block());
+
+   childBlock = entry->Block();

-   if (!firstEntry)
-       fHasCollision = (entry.Hash() & 1) == 1;
-
-   childOffset = entry.Block() * fBlockSize;
-
    return B_OK;
 }
+
+
+status_t
+HTreeEntryIterator::InsertEntry(uint32 hash, uint32 block, bool hasCollision)
+{
+   return B_OK;
+}
Index: src/add-ons/kernel/file_systems/ext2/Inode.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Inode.h    (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/Inode.h    (working copy)
@@ -12,7 +12,7 @@
 #include "Volume.h"


-class Inode {
+class Inode : public TransactionListener {
 public:
                        Inode(Volume* volume, ino_t id);
                        ~Inode();
@@ -22,7 +22,11 @@
            ino_t       ID() const { return fID; }

            rw_lock*    Lock() { return &fLock; }
+           void        WriteLockInTransaction(Transaction& transaction);

+           status_t    UpdateNodeFromDisk();
+           status_t    WriteBack(Transaction& transaction);
+
            bool        IsDirectory() const
                            { return S_ISDIR(Mode()); }
            bool        IsFile() const
@@ -32,44 +36,101 @@

            status_t    CheckPermissions(int accessMode) const;

-           mode_t      Mode() const { return fNode->Mode(); }
-           int32       Flags() const { return fNode->Flags(); }
+           mode_t      Mode() const { return fNode.Mode(); }
+           int32       Flags() const { return fNode.Flags(); }

-           off_t       Size() const { return fNode->Size(); }
+           off_t       Size() const { return fNode.Size(); }
            time_t      ModificationTime() const
-                           { return fNode->ModificationTime(); }
+                           { return fNode.ModificationTime(); }
            time_t      CreationTime() const
-                           { return fNode->CreationTime(); }
+                           { return fNode.CreationTime(); }
            time_t      AccessTime() const
-                           { return fNode->AccessTime(); }
+                           { return fNode.AccessTime(); }

            //::Volume* _Volume() const { return fVolume; }
            Volume*     GetVolume() const { return fVolume; }

            status_t    FindBlock(off_t offset, uint32& block);
            status_t    ReadAt(off_t pos, uint8 *buffer, size_t *length);
+           status_t    WriteAt(Transaction& transaction, off_t pos, uint8* buffer, size_t* length);
+           status_t    FillGapWithZeros(off_t start, off_t end);

+           status_t    Resize(Transaction& transaction, off_t size);
+
            status_t    AttributeBlockReadAt(off_t pos, uint8 *buffer,
                            size_t *length);

-           ext2_inode& Node() { return *fNode; }
+           ext2_inode& Node() { return fNode; }

+   static  status_t    Create(Transaction& transaction, Inode* parent,
+                           const char* name, int32 mode, int openMode,
+                           uint32 type, bool* _created = NULL,
+                           ino_t* _id = NULL, Inode** _inode = NULL,
+                           fs_vnode_ops* vnodeOps = NULL,
+                           uint32 publishFlags = 0);
+
            void*       FileCache() const { return fCache; }
            void*       Map() const { return fMap; }
+           status_t    DisableFileCache();
+           bool        IsFileCacheDisabled() const { return !fCached; }

+protected:
+   virtual void        TransactionDone(bool success);
+   virtual void        RemovedFromTransaction();
+
+
 private:
+                       Inode(Volume* volume);
                        Inode(const Inode&);
                        Inode &operator=(const Inode&);
                            // no implementation

-private:
-   rw_lock             fLock;
-   ::Volume*           fVolume;
-   ino_t               fID;
-   void*               fCache;
-   void*               fMap;
-   ext2_inode*         fNode;
-   ext2_xattr_header*  fAttributesBlock;
+           status_t    _EnlargeDataStream(Transaction& transaction,
+                           off_t size);
+           status_t    _ShrinkDataStream(Transaction& transaction, off_t size);
+
+           status_t    _FreeDirectBlocks(Transaction& transaction,
+                           uint32* block, uint32* maxPos);
+           status_t    _FreeIndirectBlock(Transaction& transaction,
+                           uint32* indirectBlock, uint32* maxIndirectPos);
+           status_t    _FreeDoubleIndirectBlock(Transaction& transaction,
+                           uint32* doubleIndirectBlock,
+                           uint32* maxDoubleIndirectPos);
+           status_t    _FreeTripleIndirectBlock(Transaction& transaction,
+                           uint32* tripleIndirectBlock,
+                           uint32* maxTripleIndirectPos);
+
+           status_t    _GetBlockFromAllocation(Transaction& transaction,
+                           uint32& blocksNeeded, uint32& allocated,
+                           uint32& allocatedPos, uint32& block);
+           void        _MapBlocksInIndirectBlock(uint32* block,
+                           uint32* maxPos, uint32 increment, uint32& length,
+                           uint32& rangePos);
+           status_t    _MapBlocksInDoubleIndirectBlock(
+                           Transaction& transaction,
+                           uint32* doubleIndirectBlock,
+                           uint32* maxDoubleIndirectPos, uint32* indirectBlock,
+                           uint32* maxIndirectPos, uint32 increment,
+                           uint32& blocksNeeded, uint32& allocated,
+                           uint32& allocatedPos, uint32& length,
+                           uint32& rangePos);
+           status_t    _MapBlocksInDataStream(Transaction& transaction,
+                           uint32 mapPos, uint32 rangePos, uint32 length,
+                           uint32 preferredBlockGroup);
+
+
+           rw_lock     fLock;
+           ::Volume*   fVolume;
+           ino_t       fID;
+           void*       fCache;
+           void*       fMap;
+           bool        fCached;
+           ext2_inode  fNode;
+           uint32      fNodeSize;
+               // Inodes have a varible size, but the important
+               // information is always the same size (except in ext4)
+           ext2_xattr_header* fAttributesBlock;
+           status_t    fInitStatus;
 };

 #endif // INODE_H
Index: src/add-ons/kernel/file_systems/ext2/Volume.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Volume.cpp (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/Volume.cpp (working copy)
@@ -20,7 +20,10 @@

 #include <util/AutoLock.h>

+#include "CachedBlock.h"
 #include "Inode.h"
+#include "InodeJournal.h"
+#include "NoJournal.h"


 //#define TRACE_EXT2
@@ -199,7 +202,7 @@
    // TODO: check some more values!
    if (Magic() != (uint32)EXT2_SUPER_BLOCK_MAGIC)
        return false;
-
+
    return true;
 }

@@ -210,6 +213,9 @@
 Volume::Volume(fs_volume* volume)
    :
    fFSVolume(volume),
+   fBlockAllocator(this),
+   fInodeAllocator(this),
+   fJournalInode(NULL),
    fFlags(0),
    fGroupBlocks(NULL),
    fRootNode(NULL)
@@ -220,6 +226,7 @@

 Volume::~Volume()
 {
+   TRACE("Volume destructor.\n");
    if (fGroupBlocks != NULL) {
        uint32 blockCount = (fNumGroups + fGroupsPerBlock - 1)
            / fGroupsPerBlock;
@@ -252,8 +259,14 @@
 status_t
 Volume::Mount(const char* deviceName, uint32 flags)
 {
-   flags |= B_MOUNT_READ_ONLY;
+   // flags |= B_MOUNT_READ_ONLY;
        // we only support read-only for now
+
+   if ((flags & B_MOUNT_READ_ONLY) != 0) {
+       TRACE("Volume::Mount(): Read only\n");
+   } else {
+       TRACE("Volume::Mount(): Read write\n");
+   }

    DeviceOpener opener(deviceName, (flags & B_MOUNT_READ_ONLY) != 0
        ? O_RDONLY : O_RDWR);
@@ -278,10 +291,17 @@
    fBlockSize = 1UL << fSuperBlock.BlockShift();
    fFirstDataBlock = fSuperBlock.FirstDataBlock();

+   fFreeBlocks = fSuperBlock.FreeBlocks();
+   fFreeInodes = fSuperBlock.FreeInodes();
+
+   uint32 numBlocks = fSuperBlock.NumBlocks() - fFirstDataBlock;
+   uint32 blocksPerGroup = fSuperBlock.BlocksPerGroup();
+   fNumGroups = numBlocks / blocksPerGroup;
+   if (numBlocks % blocksPerGroup != 0)
+       fNumGroups++;
+
+   fGroupsPerBlock = fBlockSize / sizeof(ext2_block_group);
    fNumInodes = fSuperBlock.NumInodes();
-   fNumGroups = (fSuperBlock.NumBlocks() - fFirstDataBlock - 1)
-       / fSuperBlock.BlocksPerGroup() + 1;
-   fGroupsPerBlock = fBlockSize / sizeof(ext2_block_group);

    TRACE("block size %ld, num groups %ld, groups per block %ld, first %lu\n",
        fBlockSize, fNumGroups, fGroupsPerBlock, fFirstDataBlock);
@@ -309,7 +329,55 @@
    fBlockCache = opener.InitCache(NumBlocks(), fBlockSize);
    if (fBlockCache == NULL)
        return B_ERROR;
+
+   TRACE("Volume::Mount(): Initialized block cache: %p\n", fBlockCache);

+   // initialize journal
+   if ((fSuperBlock.CompatibleFeatures() & EXT2_FEATURE_HAS_JOURNAL) != 0) {
+       // TODO: There should be a mount option to ignore the existent journal
+       if (fSuperBlock.JournalInode() != 0) {
+           fJournalInode = new(std::nothrow) Inode(this,
+               fSuperBlock.JournalInode());
+
+           if (fJournalInode == NULL)
+               return B_NO_MEMORY;
+
+           TRACE("Opening an on disk, inode mapped journal.\n");
+           fJournal = new(std::nothrow) InodeJournal(fJournalInode);
+       } else {
+           // TODO: external journal
+           TRACE("Can not open an external journal.\n");
+           return B_NOT_SUPPORTED;
+       }
+   } else {
+       TRACE("Opening a fake journal (NoJournal).\n");
+       fJournal = new(std::nothrow) NoJournal(this);
+   }
+
+   if (fJournal == NULL) {
+       TRACE("No memory to create the journal\n");
+       return B_NO_MEMORY;
+   }
+
+   status = fJournal->InitCheck();
+   if (status != B_OK)
+       return status;
+
+   // TODO: Only recover if asked to
+   status = fJournal->Recover();
+   if (status != B_OK)
+       return status;
+
+   status = fJournal->StartLog();
+   if (status != B_OK)
+       return status;
+
+   // Initialize allocators
+   status = fBlockAllocator.Initialize();
+   if (status != B_OK)
+       return status;
+
+   // ready
    status = get_vnode(fFSVolume, EXT2_ROOT_NODE, (void**)&fRootNode);
    if (status != B_OK) {
        TRACE("could not create root node: get_vnode() failed!\n");
@@ -342,11 +410,22 @@
 status_t
 Volume::Unmount()
 {
+   TRACE("Volume::Unmount()\n");
+
+   status_t status = fJournal->Deinit();
+
+   delete fJournal;
+   delete fJournalInode;
+
+   TRACE("Volume::Unmount(): Putting root node\n");
    put_vnode(fFSVolume, RootNode()->ID());
+   TRACE("Volume::Unmount(): Deleting the block cache\n");
    block_cache_delete(fBlockCache, !IsReadOnly());
+   TRACE("Volume::Unmount(): Closing device\n");
    close(fDevice);

-   return B_OK;
+   TRACE("Volume::Unmount(): Done\n");
+   return status;
 }


@@ -443,6 +522,122 @@
 }


+status_t
+Volume::AllocateInode(Transaction& transaction, Inode* parent, int32 mode,
+   ino_t& id)
+{
+   if (IsReadOnly())
+       return B_READ_ONLY_DEVICE;
+
+   status_t status = fInodeAllocator.New(transaction, parent, mode, id);
+   if (status == B_OK)
+       --fFreeInodes;
+
+   return status;
+}
+
+
+status_t
+Volume::AllocateBlocks(Transaction& transaction, uint32 minimum, uint32 maximum,
+   uint32& blockGroup, uint32& start, uint32& length)
+{
+   TRACE("Volume::AllocateBlocks()\n");
+   if (IsReadOnly())
+       return B_READ_ONLY_DEVICE;
+
+   TRACE("Volume::AllocateBlocks(): Calling the block allocator\n");
+
+   status_t status = fBlockAllocator.AllocateBlocks(transaction, minimum,
+       maximum, blockGroup, start, length);
+   if (status != B_OK)
+       return status;
+
+   TRACE("Volume::AllocateBlocks(): Allocated %lu blocks\n", length);
+
+   fFreeBlocks -= length;
+
+   return WriteSuperBlock(transaction);
+}
+
+
+status_t
+Volume::FreeBlocks(Transaction& transaction, uint32 start, uint32 length)
+{
+   if (IsReadOnly())
+       return B_READ_ONLY_DEVICE;
+
+   status_t status = fBlockAllocator.Free(transaction, start, length);
+   if (status != B_OK)
+       return status;
+
+   fFreeBlocks += length;
+
+   return WriteSuperBlock(transaction);
+}
+
+
+status_t
+Volume::LoadSuperBlock()
+{
+   CachedBlock cached(this);
+   const uint8* block = cached.SetTo(fFirstDataBlock);
+
+   if (block == NULL)
+       return B_IO_ERROR;
+
+   if (fFirstDataBlock == 0)
+       memcpy(&fSuperBlock, block + 1024, sizeof(fSuperBlock));
+   else
+       memcpy(&fSuperBlock, block, sizeof(fSuperBlock));
+
+   fFreeBlocks = fSuperBlock.FreeBlocks();
+   fFreeInodes = fSuperBlock.FreeInodes();
+
+   return B_OK;
+}
+
+
+status_t
+Volume::WriteSuperBlock(Transaction& transaction)
+{
+   TRACE("Volume::WriteSuperBlock()\n");
+   fSuperBlock.SetFreeBlocks(fFreeBlocks);
+   fSuperBlock.SetFreeInodes(fFreeInodes);
+   // TODO: Rest of fields that can be modified
+
+   CachedBlock cached(this);
+   uint8* block = cached.SetToWritable(transaction, fFirstDataBlock);
+
+   if (block == NULL)
+       return B_IO_ERROR;
+
+   if (fFirstDataBlock == 0)
+       memcpy(block + 1024, &fSuperBlock, sizeof(fSuperBlock));
+   else
+       memcpy(block, &fSuperBlock, sizeof(fSuperBlock));
+
+   TRACE("Volume::WriteSuperBlock(): Done\n");
+
+   return B_OK;
+}
+
+
+status_t
+Volume::FlushDevice()
+{
+   TRACE("Volume::FlushDevice()\n");
+   return block_cache_sync(fBlockCache);
+}
+
+
+status_t
+Volume::Sync()
+{
+   TRACE("Volume::Sync()\n");
+   return fJournal->FlushLogAndBlocks();
+}
+
+
 // #pragma mark - Disk scanning and initialization


@@ -460,3 +655,18 @@
        ? B_OK : B_NOT_SUPPORTED;
 }

+
+void
+Volume::TransactionDone(bool success)
+{
+   status_t status = LoadSuperBlock();
+   if (status != B_OK)
+       panic("Failed to relead ext2 superblock.\n");
+}
+
+
+void
+Volume::RemovedFromTransaction()
+{
+   // TODO: Does it make a difference?
+}
Index: src/add-ons/kernel/file_systems/ext2/Journal.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Journal.cpp    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/Journal.cpp    (revision 0)
@@ -0,0 +1,1254 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "Journal.h"
+
+#include <new>
+#include <string.h>
+#include <unistd.h>
+
+#include <fs_cache.h>
+
+#include "CachedBlock.h"
+#include "HashRevokeManager.h"
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+class LogEntry : public DoublyLinkedListLinkImpl<LogEntry> {
+public:
+                           LogEntry(Journal* journal, uint32 logStart,
+                               uint32 length);
+                           ~LogEntry();
+
+           uint32          Start() const { return fStart; }
+           uint32          CommitID() const { return fCommitID; }
+
+           Journal*        GetJournal() { return fJournal; }
+
+private:
+           Journal*        fJournal;
+           uint32          fStart;
+           uint32          fCommitID;
+};
+
+
+LogEntry::LogEntry(Journal* journal, uint32 logStart, uint32 commitID)
+   :
+   fJournal(journal),
+   fStart(logStart),
+   fCommitID(commitID)
+{
+}
+
+
+LogEntry::~LogEntry()
+{
+}
+
+
+/*void
+add_to_iovec(iovec* vecs, int32& index, int32 max, const void* address,
+   size_t size)
+{
+   if (index > 0 && (addr_t)vecs[index - 1].iov_base
+       + vecs[index - 1].iov_len == (addr_t)address) {
+       // the iovec can be combined with the previous one
+       vecs[index - 1].iov_len += size;
+       return;
+   }
+
+   if (index == max)
+       panic("no more space for iovecs!");
+
+   // start a new iovec
+   vecs[index].iov_base = const_cast<void*>(address);
+   vecs[index].iov_len = size;
+   index++;
+}*/
+
+
+void
+JournalHeader::MakeDescriptor(uint32 sequence)
+{
+   this->magic = B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
+   this->sequence = B_HOST_TO_BENDIAN_INT32(sequence);
+   this->block_type = B_HOST_TO_BENDIAN_INT32(JOURNAL_DESCRIPTOR_BLOCK);
+}
+
+
+void
+JournalHeader::MakeCommit(uint32 sequence)
+{
+   this->magic = B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
+   this->sequence = B_HOST_TO_BENDIAN_INT32(sequence);
+   this->block_type = B_HOST_TO_BENDIAN_INT32(JOURNAL_COMMIT_BLOCK);
+}
+
+
+Journal::Journal(Volume* fsVolume, Volume* jVolume)
+   :
+   fJournalVolume(jVolume),
+   fJournalBlockCache(jVolume->BlockCache()),
+   fFilesystemVolume(fsVolume),
+   fFilesystemBlockCache(fsVolume->BlockCache()),
+   fRevokeManager(NULL),
+   fInitStatus(B_OK),
+   fBlockSize(sizeof(JournalSuperBlock)),
+   fFirstCommitID(0),
+   fFirstCacheCommitID(0),
+   fFirstLogBlock(1),
+   fLogSize(0),
+   fVersion(0),
+   fLogStart(0),
+   fLogEnd(0),
+   fFreeBlocks(0),
+   fMaxTransactionSize(0),
+   fCurrentCommitID(0),
+   fHasSubTransaction(false),
+   fSeparateSubTransactions(false),
+   fUnwrittenTransactions(0),
+   fTransactionID(0)
+{
+   recursive_lock_init(&fLock, "ext2 journal");
+   mutex_init(&fLogEntriesLock, "ext2 journal log entries");
+
+   HashRevokeManager* revokeManager = new(std::nothrow) HashRevokeManager;
+   TRACE("Journal::Journal(): Allocated a hash revoke manager at %p\n",
+       revokeManager);
+
+   if (revokeManager == NULL)
+       fInitStatus = B_NO_MEMORY;
+   else {
+       fInitStatus = revokeManager->Init();
+
+       if (fInitStatus == B_OK) {
+           fRevokeManager = revokeManager;
+           fInitStatus = _LoadSuperBlock();
+       }
+   }
+}
+
+
+Journal::Journal()
+   :
+   fJournalVolume(NULL),
+   fJournalBlockCache(NULL),
+   fFilesystemVolume(NULL),
+   fFilesystemBlockCache(NULL),
+   fRevokeManager(NULL),
+   fInitStatus(B_OK),
+   fBlockSize(sizeof(JournalSuperBlock)),
+   fFirstCommitID(0),
+   fFirstCacheCommitID(0),
+   fFirstLogBlock(1),
+   fLogSize(0),
+   fVersion(0),
+   fLogStart(0),
+   fLogEnd(0),
+   fFreeBlocks(0),
+   fMaxTransactionSize(0),
+   fCurrentCommitID(0),
+   fHasSubTransaction(false),
+   fSeparateSubTransactions(false),
+   fUnwrittenTransactions(0),
+   fTransactionID(0)
+{
+   recursive_lock_init(&fLock, "ext2 journal");
+   mutex_init(&fLogEntriesLock, "ext2 journal log entries");
+}
+
+
+Journal::~Journal()
+{
+   TRACE("Journal destructor.\n");
+
+   TRACE("Journal::~Journal(): Attempting to delete revoke manager at %p\n",
+       fRevokeManager);
+   delete fRevokeManager;
+
+   recursive_lock_destroy(&fLock);
+   mutex_destroy(&fLogEntriesLock);
+}
+
+
+status_t
+Journal::InitCheck()
+{
+   return fInitStatus;
+}
+
+
+status_t
+Journal::Deinit()
+{
+   return FlushLogAndBlocks();
+}
+
+
+/*virtual*/ status_t
+Journal::StartLog()
+{
+   fLogStart = fFirstLogBlock;
+   fLogEnd = fFirstLogBlock;
+   fFreeBlocks = 0;
+
+   fCurrentCommitID = fFirstCommitID;
+   //fNextCommitID = fFirstCommitID;
+
+   return _SaveSuperBlock();
+}
+
+
+status_t
+Journal::RestartLog()
+{
+   fFirstCommitID = 1;
+
+   return B_OK;
+}
+
+
+/*virtual*/ status_t
+Journal::Lock(Transaction* owner, bool separateSubTransactions)
+{
+   TRACE("Journal::Lock()\n");
+   status_t status = recursive_lock_lock(&fLock);
+   if (status != B_OK)
+       return status;
+
+   TRACE("Journal::Lock(): Aquired lock\n");
+
+   if (!fSeparateSubTransactions && recursive_lock_get_recursion(&fLock) > 1) {
+       // reuse current transaction
+       TRACE("Journal::Lock(): Reusing current transaction\n");
+       return B_OK;
+   }
+
+   if(separateSubTransactions)
+       fSeparateSubTransactions = true;
+
+   if (owner != NULL)
+       owner->SetParent(fOwner);
+
+   fOwner = owner;
+
+   if (fOwner != NULL) {
+       if (fUnwrittenTransactions > 0) {
+           // start a sub transaction
+           TRACE("Journal::Lock(): Starting sub transaction\n");
+           cache_start_sub_transaction(fFilesystemBlockCache, fTransactionID);
+           fHasSubTransaction = true;
+       } else {
+           TRACE("Journal::Lock(): Starting new transaction\n");
+           fTransactionID = cache_start_transaction(fFilesystemBlockCache);
+       }
+
+       if (fTransactionID < B_OK) {
+           recursive_lock_unlock(&fLock);
+           return fTransactionID;
+       }
+
+       cache_add_transaction_listener(fFilesystemBlockCache, fTransactionID,
+           TRANSACTION_IDLE, _TransactionIdle, this);
+   }
+
+   return B_OK;
+}
+
+
+/*virtual*/ status_t
+Journal::Unlock(Transaction* owner, bool success)
+{
+   TRACE("Journal::Unlock()\n");
+   if (fSeparateSubTransactions
+       || recursive_lock_get_recursion(&fLock) == 1) {
+       // we only end the transaction if we unlock it
+       TRACE("Journal::Unlock(): Last lock holder\n");
+       if (owner != NULL) {
+           TRACE("Journal::Unlock(): Calling _TransactionDone\n");
+           status_t status = _TransactionDone(success);
+           if (status != B_OK)
+               return status;
+
+           bool separateSubTransactions = fSeparateSubTransactions;
+           fSeparateSubTransactions = true;
+           owner->NotifyListeners(success);
+           fSeparateSubTransactions = separateSubTransactions;
+
+           fOwner = owner->Parent();
+       } else
+           fOwner = NULL;
+
+       if (fSeparateSubTransactions
+           && recursive_lock_get_recursion(&fLock) == 1)
+           fSeparateSubTransactions = false;
+   } else
+       owner->MoveListenersTo(fOwner);
+
+   recursive_lock_unlock(&fLock);
+   return B_OK;
+}
+
+
+status_t
+Journal::MapBlock(uint32 logical, uint32& physical)
+{
+   TRACE("Journal::MapBlock()\n");
+   physical = logical;
+
+   return B_OK;
+}
+
+
+inline uint32
+Journal::FreeLogBlocks() const
+{
+   TRACE("Journal::FreeLogBlocks(): start: %lu, end: %lu, size: %lu\n",
+       fLogStart, fLogEnd, fLogSize);
+   return fLogStart <= fLogEnd
+       ? fLogSize - fLogEnd + fLogStart - 1
+       : fLogStart - fLogEnd;
+}
+
+
+status_t
+Journal::FlushLogAndBlocks()
+{
+   return _FlushLog(true, true);
+}
+
+
+int32
+Journal::TransactionID() const
+{
+   return fTransactionID;
+}
+
+
+status_t
+Journal::_WritePartialTransactionToLog(JournalHeader* descriptorBlock,
+   bool detached, uint8** _escapedData, uint32 &logBlock, off_t& blockNumber,
+   long& cookie, ArrayDeleter<uint8>& escapedDataDeleter, uint32& blockCount,
+   bool& finished)
+{
+   TRACE("Journal::_WritePartialTransactionToLog()\n");
+
+   uint32 descriptorBlockPos = logBlock;
+   uint8* escapedData = *_escapedData;
+
+   JournalBlockTag* tag = (JournalBlockTag*)descriptorBlock->data;
+   JournalBlockTag* lastTag = (JournalBlockTag*)((uint8*)descriptorBlock
+       + fBlockSize - sizeof(JournalHeader));
+
+   finished = false;
+   status_t status = B_OK;
+
+   while (tag < lastTag && status == B_OK) {
+       tag->SetBlockNumber(blockNumber);
+       tag->SetFlags(0);
+
+       CachedBlock data(fFilesystemVolume);
+       const JournalHeader* blockData = (JournalHeader*)data.SetTo(
+           blockNumber);
+       if (blockData == NULL) {
+           panic("Got a NULL pointer while iterating through transaction "
+               "blocks.\n");
+           return B_ERROR;
+       }
+
+       void* finalData;
+
+       if (blockData->CheckMagic()) {
+           // The journaled block starts with the magic value
+           // We must remove it to prevent confusion
+           TRACE("Journal::_WritePartialTransactionToLog(): Block starts with "
+               "magic number. Escaping it\n");
+           tag->SetEscapedFlag();
+
+           if (escapedData == NULL) {
+               TRACE("Journal::_WritePartialTransactionToLog(): Allocating "
+                   "space for escaped block (%lu)\n", fBlockSize);
+               escapedData = new(std::nothrow) uint8[fBlockSize];
+               if (escapedData == NULL) {
+                   TRACE("Journal::_WritePartialTransactionToLof(): Failed to "
+                       "allocate buffer for escaped data block\n");
+                   return B_NO_MEMORY;
+               }
+               escapedDataDeleter.SetTo(escapedData);
+               *_escapedData = escapedData;
+
+               ((int32*)escapedData)[0] = 0; // Remove magic
+           }
+
+           memcpy(escapedData + 4, blockData->data, fBlockSize - 4);
+           finalData = escapedData;
+       } else
+           finalData = (void*)blockData;
+
+       // TODO: use iovecs?
+
+       logBlock = _WrapAroundLog(logBlock + 1);
+
+       uint32 physicalBlock;
+       status = MapBlock(logBlock, physicalBlock);
+       if (status != B_OK)
+           return status;
+
+       off_t logOffset = physicalBlock * fBlockSize;
+
+       TRACE("Journal::_WritePartialTransactionToLog(): Writing from memory: "
+           "%p, to disk: %ld\n", finalData, (long)logOffset);
+       size_t written = write_pos(fJournalVolume->Device(), logOffset,
+           finalData, fBlockSize);
+       if (written != fBlockSize) {
+           TRACE("Failed to write journal block.\n");
+           return B_IO_ERROR;
+       }
+
+       TRACE("Journal::_WritePartialTransactionToLog(): Wrote a journal block "
+           "at: %lu\n", logBlock);
+
+       blockCount++;
+       tag++;
+
+       status = cache_next_block_in_transaction(fFilesystemBlockCache,
+           fTransactionID, detached, &cookie, &blockNumber, NULL, NULL);
+   }
+
+   finished = status == B_OK;
+
+   // Write descriptor block
+   --tag;
+   tag->SetLastTagFlag();
+
+   uint32 physicalBlock;
+   status = MapBlock(descriptorBlockPos, physicalBlock);
+   if (status != B_OK)
+       return status;
+
+   off_t descriptorBlockOffset = physicalBlock * fBlockSize;
+
+   TRACE("Journal::_WriteTansactionToLog(): Writing to: %ld\n",
+       (long)descriptorBlockOffset);
+   size_t written = write_pos(fJournalVolume->Device(),
+       descriptorBlockOffset, descriptorBlock, fBlockSize);
+   if (written != fBlockSize) {
+       TRACE("Failed to write journal descriptor block.\n");
+       return B_IO_ERROR;
+   }
+
+   blockCount++;
+   logBlock = _WrapAroundLog(logBlock + 1);
+
+   return B_OK;
+}
+
+
+status_t
+Journal::_WriteTransactionToLog()
+{
+   TRACE("Journal::_WriteTransactionToLog()\n");
+   // Transaction enters the Flush state
+   bool detached = false;
+   TRACE("Journal::_WriteTransactionToLog(): Attempting to get transaction "
+       "size\n");
+   size_t size = _FullTransactionSize();
+   TRACE("Journal::_WriteTransactionToLog(): transaction size: %lu\n", size);
+
+   if (size > fMaxTransactionSize) {
+       TRACE("Journal::_WriteTransactionToLog(): not enough free space "
+           "for the transaction. Attempting to free some space.\n");
+       size = _MainTransactionSize();
+       TRACE("Journal::_WriteTransactionToLog(): main transaction size: %lu\n",
+           size);
+
+       if(fHasSubTransaction && size < fMaxTransactionSize) {
+           TRACE("Journal::_WriteTransactionToLog(): transaction doesn't fit, "
+               "but it can be separated\n");
+           detached = true;
+       } else {
+           // Error: transaction can't fit in log
+           panic("transaction too large (size: %lu, max size: %lu, log size: "
+               "%lu)\n", size, fMaxTransactionSize, fLogSize);
+           return B_BUFFER_OVERFLOW;
+       }
+   }
+
+   TRACE("Journal::_WriteTransactionToLog(): free log blocks: %lu\n",
+       FreeLogBlocks());
+   if (size > FreeLogBlocks()) {
+       TRACE("Journal::_WriteTransactionToLog(): Syncing block cache\n");
+       cache_sync_transaction(fFilesystemBlockCache, fTransactionID);
+
+       if (size > FreeLogBlocks()) {
+           panic("Transaction fits, but sync didn't result in enough"
+               "free space.\n\tGot %ld when at least %ld was expected.",
+               (long)FreeLogBlocks(), (long)size);
+       }
+   }
+
+   TRACE("Journal::_WriteTransactionToLog(): finished managing space for "
+       "the transaction\n");
+
+   fHasSubTransaction = false;
+
+   // Prepare Descriptor block
+   TRACE("Journal::_WriteTransactionToLog(): attempting to allocate space for "
+       "the descriptor block, block size %lu\n", fBlockSize);
+   JournalHeader* descriptorBlock =
+       (JournalHeader*)new(std::nothrow) uint8[fBlockSize];
+   if (descriptorBlock == NULL) {
+       TRACE("Journal::_WriteTransactionToLog(): Failed to allocate a buffer "
+           "for the descriptor block\n");
+       return B_NO_MEMORY;
+   }
+   ArrayDeleter<uint8> descriptorBlockDeleter((uint8*)descriptorBlock);
+
+   descriptorBlock->MakeDescriptor(fCurrentCommitID);
+
+   // Prepare Commit block
+   TRACE("Journal::_WriteTransactionToLog(): attempting to allocate space for "
+       "the commit block, block size %lu\n", fBlockSize);
+   JournalHeader* commitBlock =
+       (JournalHeader*)new(std::nothrow) uint8[fBlockSize];
+   if (descriptorBlock == NULL) {
+       TRACE("Journal::_WriteTransactionToLog(): Failed to allocate a buffer "
+           "for the commit block\n");
+       return B_NO_MEMORY;
+   }
+   ArrayDeleter<uint8> commitBlockDeleter((uint8*)commitBlock);
+
+   commitBlock->MakeCommit(fCurrentCommitID + 1);
+   memset(commitBlock->data, 0, fBlockSize - sizeof(JournalHeader));
+       // TODO: This probably isn't necessary
+
+   uint8* escapedData = NULL;
+   ArrayDeleter<uint8> escapedDataDeleter;
+
+   off_t blockNumber;
+   long cookie = 0;
+
+   status_t status = cache_next_block_in_transaction(fFilesystemBlockCache,
+       fTransactionID, detached, &cookie, &blockNumber, NULL, NULL);
+   if (status != B_OK) {
+       TRACE("Journal::_WriteTransactionToLog(): Transaction has no blocks to
+           write\n");
+       return B_OK;
+   }
+
+   uint32 blockCount = 0;
+
+   uint32 logBlock = _WrapAroundLog(fLogEnd);
+
+   bool finished = false;
+
+   status = _WritePartialTransactionToLog(descriptorBlock, detached,
+       &escapedData, logBlock, blockNumber, cookie, escapedDataDeleter,
+       blockCount, finished);
+   if (!finished && status != B_OK)
+       return status;
+
+   uint32 commitBlockPos = logBlock;
+
+   while (!finished) {
+       descriptorBlock->IncrementSequence();
+
+       status = _WritePartialTransactionToLog(descriptorBlock, detached,
+           &escapedData, logBlock, blockNumber, cookie, escapedDataDeleter,
+           blockCount, finished);
+       if (!finished && status != B_OK)
+           return status;
+
+       // It is okay to write the commit blocks of the partial transactions
+       // as long as the commit block of the first partial transaction isn't
+       // written. When it recovery reaches where the first commit should be
+       // and doesn't find it, it considers it found the end of the log.
+
+       uint32 physicalBlock;
+       status = MapBlock(logBlock, physicalBlock);
+       if (status != B_OK)
+           return status;
+
+       off_t logOffset = physicalBlock * fBlockSize;
+
+       TRACE("Journal::_WritaTransactionToLog(): Writting commit block to "
+           "%ld\n", (long)logOffset);
+       off_t written = write_pos(fJournalVolume->Device(), logOffset,
+           commitBlock, fBlockSize);
+       if (written != fBlockSize) {
+           TRACE("Failed to write journal commit block.\n");
+           return B_IO_ERROR;
+       }
+
+       commitBlock->IncrementSequence();
+       blockCount++;
+
+       logBlock = _WrapAroundLog(logBlock + 1);
+   }
+
+   // Transaction will enter the Commit state
+   uint32 physicalBlock;
+   status = MapBlock(commitBlockPos, physicalBlock);
+   if (status != B_OK)
+       return status;
+
+   off_t logOffset = physicalBlock * fBlockSize;
+
+   TRACE("Journal::_WriteTansactionToLog(): Writing to: %ld\n",
+       (long)logOffset);
+   off_t written = write_pos(fJournalVolume->Device(), logOffset, commitBlock,
+       fBlockSize);
+   if (written != fBlockSize) {
+       TRACE("Failed to write journal commit block.\n");
+       return B_IO_ERROR;
+   }
+
+   blockCount++;
+   fLogEnd = _WrapAroundLog(fLogEnd + blockCount);
+
+   status = _SaveSuperBlock();
+
+   // Transaction will enter Finished state
+   LogEntry *logEntry = new LogEntry(this, fLogEnd, fCurrentCommitID++);
+   TRACE("Journal::_WriteTransactionToLog(): Allocating log entry at %p\n", logEntry);
+   if (logEntry == NULL) {
+       panic("no memory to allocate log entries!");
+       return B_NO_MEMORY;
+   }
+
+   mutex_lock(&fLogEntriesLock);
+   fLogEntries.Add(logEntry);
+   mutex_unlock(&fLogEntriesLock);
+
+   if (detached) {
+       fTransactionID = cache_detach_sub_transaction(fFilesystemBlockCache,
+           fTransactionID, _TransactionWritten, logEntry);
+       fUnwrittenTransactions = 1;
+
+       if (status == B_OK && _FullTransactionSize() > fLogSize) {
+           // If the transaction is too large after writing, there is no way to
+           // recover, so let this transaction fail.
+           dprintf("transaction too large (%d blocks, log size %d)!\n",
+               (int)_FullTransactionSize(), (int)fLogSize);
+           return B_BUFFER_OVERFLOW;
+       }
+   } else {
+       cache_end_transaction(fFilesystemBlockCache, fTransactionID,
+           _TransactionWritten, logEntry);
+       fUnwrittenTransactions = 0;
+   }
+
+   return B_OK;
+}
+
+
+status_t
+Journal::_SaveSuperBlock()
+{
+   TRACE("Journal::_SaveSuperBlock()\n");
+   uint32 physicalBlock;
+   status_t status = MapBlock(0, physicalBlock);
+   if (status != B_OK)
+       return status;
+
+   off_t superblockPos = physicalBlock * fBlockSize;
+
+   JournalSuperBlock superblock;
+   size_t bytesRead = read_pos(fJournalVolume->Device(), superblockPos,
+       &superblock, sizeof(superblock));
+
+   if (bytesRead != sizeof(superblock))
+       return B_IO_ERROR;
+
+   superblock.SetFirstCommitID(fFirstCommitID);
+   superblock.SetLogStart(fLogStart);
+
+   TRACE("Journal::SaveSuperBlock(): Write to %ld\n", (long)superblockPos);
+   size_t bytesWritten = write_pos(fJournalVolume->Device(), superblockPos,
+       &superblock, sizeof(superblock));
+
+   if (bytesWritten != sizeof(superblock))
+       return B_IO_ERROR;
+
+   TRACE("Journal::_SaveSuperBlock(): Done\n");
+
+   return B_OK;
+}
+
+
+status_t
+Journal::_LoadSuperBlock()
+{
+   TRACE("Journal::_LoadSuperBlock()\n");
+   uint32 superblockPos;
+
+   status_t status = MapBlock(0, superblockPos);
+   if (status != B_OK)
+       return status;
+
+   TRACE("Journal::_LoadSuperBlock(): super block physical block: %lu\n",
+       superblockPos);
+
+   JournalSuperBlock superblock;
+   size_t bytesRead = read_pos(fJournalVolume->Device(), superblockPos
+       * fJournalVolume->BlockSize(), &superblock, sizeof(superblock));
+
+   if (bytesRead != sizeof(superblock)) {
+       TRACE("Journal::_LoadSuperBlock(): failed to read superblock\n");
+       return B_IO_ERROR;
+   }
+
+   if (!superblock.header.CheckMagic()) {
+       TRACE("Journal::_LoadSuperBlock(): Invalid superblock magic %lX\n",
+           superblock.header.Magic());
+       return B_BAD_VALUE;
+   }
+
+   if (superblock.header.BlockType() == JOURNAL_SUPERBLOCK_V1) {
+       TRACE("Journal::_LoadSuperBlock(): Journal superblock version 1\n");
+       fVersion = 1;
+   } else if (superblock.header.BlockType() == JOURNAL_SUPERBLOCK_V2) {
+       TRACE("Journal::_LoadSuperBlock(): Journal superblock version 2\n");
+       fVersion = 2;
+   } else {
+       TRACE("Journal::_LoadSuperBlock(): Invalid superblock version\n");
+       return B_BAD_VALUE;
+   }
+
+   if (fVersion >= 2) {
+       status = _CheckFeatures(&superblock);
+
+       if (status != B_OK) {
+           TRACE("Journal::_LoadSuperBlock(): Unsupported features\n");
+           return status;
+       }
+   }
+
+   fBlockSize = superblock.BlockSize();
+   fFirstCommitID = superblock.FirstCommitID();
+   fFirstLogBlock = superblock.FirstLogBlock();
+   fLogStart = superblock.LogStart();
+   fLogSize = superblock.NumBlocks();
+
+   uint32 descriptorTags = (fBlockSize - sizeof(JournalHeader))
+       / sizeof(JournalBlockTag);
+       // Maximum tags per descriptor block
+   uint32 maxDescriptors = (fLogSize - 1) / (descriptorTags + 2);
+       // Maximum number of full journal transactions
+   fMaxTransactionSize = maxDescriptors * descriptorTags;
+   fMaxTransactionSize += (fLogSize - 1) - fMaxTransactionSize - 2;
+       // Maximum size of a "logical" transaction
+       // TODO: Why is "superblock.MaxTransactionBlocks();" zero?
+   //fFirstCacheCommitID = fFirstCommitID - fTransactionID /*+ 1*/;
+
+   TRACE("Journal::_LoadSuperBlock(): block size: %lu, first commit id: %lu, "
+       "first log block: %lu, log start: %lu, log size: %lu, max transaction "
+       "size: %lu\n", fBlockSize, fFirstCommitID, fFirstLogBlock, fLogStart,
+       fLogSize, fMaxTransactionSize);
+
+   return B_OK;
+}
+
+
+status_t
+Journal::_CheckFeatures(JournalSuperBlock* superblock)
+{
+   if ((superblock->ReadOnlyCompatibleFeatures()
+           & ~JOURNAL_KNOWN_READ_ONLY_COMPATIBLE_FEATURES) != 0
+       || (superblock->IncompatibleFeatures()
+           & ~JOURNAL_KNOWN_INCOMPATIBLE_FEATURES) != 0)
+       return B_NOT_SUPPORTED;
+
+   return B_OK;
+}
+
+
+uint32
+Journal::_CountTags(JournalHeader* descriptorBlock)
+{
+   uint32 count = 0;
+
+   JournalBlockTag* tags = (JournalBlockTag*)descriptorBlock->data;
+       // Skip the header
+   JournalBlockTag* lastTag = (JournalBlockTag*)
+       (descriptorBlock + fBlockSize - sizeof(JournalBlockTag));
+
+   while (tags < lastTag && (tags->Flags() & JOURNAL_FLAG_LAST_TAG) == 0) {
+       if ((tags->Flags() & JOURNAL_FLAG_SAME_UUID) == 0) {
+           // sizeof(UUID) = 16 = 2*sizeof(JournalBlockTag)
+           tags += 2;  // Skip new UUID
+       }
+
+       TRACE("Journal::_CountTags(): Tag block: %lu\n", tags->BlockNumber());
+
+       tags++; // Go to next tag
+       count++;
+   }
+
+   TRACE("Journal::_CountTags(): counted tags: %lu\n", count);
+
+   return count;
+}
+
+
+/*virtual*/ status_t
+Journal::Recover()
+{
+   TRACE("Journal::Recover()\n");
+   if (fLogStart == 0) // Journal was cleanly unmounted
+       return B_OK;
+
+   TRACE("Journal::Recover(): Journal needs recovery\n");
+
+   uint32 lastCommitID;
+
+   status_t status = _RecoverPassScan(lastCommitID);
+   if (status != B_OK)
+       return status;
+
+   status = _RecoverPassRevoke(lastCommitID);
+   if (status != B_OK)
+       return status;
+
+   return _RecoverPassReplay(lastCommitID);
+}
+
+
+// First pass: Find the end of the log
+status_t
+Journal::_RecoverPassScan(uint32& lastCommitID)
+{
+   TRACE("Journal Recover: 1st Pass: Scan\n");
+
+   CachedBlock cached(fJournalVolume);
+   JournalHeader* header;
+   uint32 nextCommitID = fFirstCommitID;
+   uint32 nextBlock = fLogStart;
+   uint32 nextBlockPos;
+
+   status_t status = MapBlock(nextBlock, nextBlockPos);
+   if (status != B_OK)
+       return status;
+
+   header = (JournalHeader*)cached.SetTo(nextBlockPos);
+
+   while (header->CheckMagic() && header->Sequence() == nextCommitID) {
+       uint32 blockType = header->BlockType();
+
+       if (blockType == JOURNAL_DESCRIPTOR_BLOCK)
+           nextBlock += nextBlock - 1;
+       else if (blockType == JOURNAL_COMMIT_BLOCK)
+           nextCommitID++;
+       else if (blockType != JOURNAL_REVOKE_BLOCK) {
+               // TODO: Warn that we found an unrecognized block
+           break;
+       } // If blockType == JOURNAL_REVOKE_BLOCK we just skip it
+
+       nextBlock = _WrapAroundLog(nextBlock + 1);
+
+       status = MapBlock(nextBlock, nextBlockPos);
+       if (status != B_OK)
+           return status;
+
+       header = (JournalHeader*)cached.SetTo(nextBlockPos);
+   }
+
+   TRACE("Journal Recovery pass scan: Last detected transaction ID: %lu\n",
+       nextCommitID);
+
+   lastCommitID = nextCommitID;
+   return B_OK;
+}
+
+
+// Second pass: Collect all revoked blocks
+status_t
+Journal::_RecoverPassRevoke(uint32 lastCommitID)
+{
+   TRACE("Journal Recover: 2nd Pass: Revoke\n");
+
+   CachedBlock cached(fJournalVolume);
+   JournalHeader* header;
+   uint32 nextCommitID = fFirstCommitID;
+   uint32 nextBlock = fLogStart;
+   uint32 nextBlockPos;
+
+   status_t status = MapBlock(nextBlock, nextBlockPos);
+   if (status != B_OK)
+       return status;
+
+   header = (JournalHeader*)cached.SetTo(nextBlockPos);
+
+   while (nextCommitID < lastCommitID) {
+       if (!header->CheckMagic() || header->Sequence() != nextCommitID) {
+           // Somehow the log is different than the expexted
+           return B_ERROR;
+       }
+
+       uint32 blockType = header->BlockType();
+
+       if (blockType == JOURNAL_DESCRIPTOR_BLOCK)
+           nextBlock += _CountTags(header) - 1;
+       else if (blockType == JOURNAL_COMMIT_BLOCK)
+           nextCommitID++;
+       else if (blockType == JOURNAL_REVOKE_BLOCK) {
+           TRACE("Journal::_RecoverPassRevoke(): Found a revoke block\n");
+           status = fRevokeManager->ScanRevokeBlock(
+               (JournalRevokeHeader*)header, nextCommitID);
+
+           if (status != B_OK)
+               return status;
+       } else {
+               // TODO: Warn that we found an unrecognized block
+           break;
+       }
+
+       nextBlock = _WrapAroundLog(nextBlock + 1);
+
+       status = MapBlock(nextBlock, nextBlockPos);
+       if (status != B_OK)
+           return status;
+
+       header = (JournalHeader*)cached.SetTo(nextBlockPos);
+   }
+
+   if (nextCommitID != lastCommitID) {
+       // Possibly because of some sort of IO error
+       TRACE("Journal::_RecoverPassRevoke(): Incompatible commit IDs\n");
+       return B_ERROR;
+   }
+
+   TRACE("Journal recovery pass revoke: Revoked blocks: %lu\n",
+       fRevokeManager->NumRevokes());
+
+   return B_OK;
+}
+
+
+// Third pass: Replay log
+status_t
+Journal::_RecoverPassReplay(uint32 lastCommitID)
+{
+   TRACE("Journal Recover: 3rd Pass: Replay\n");
+
+   uint32 nextCommitID = fFirstCommitID;
+   uint32 nextBlock = fLogStart;
+   uint32 nextBlockPos;
+
+   status_t status = MapBlock(nextBlock, nextBlockPos);
+   if (status != B_OK)
+       return status;
+
+   CachedBlock cached(fJournalVolume);
+   JournalHeader* header = (JournalHeader*)cached.SetTo(nextBlockPos);
+
+   int count = 0;
+
+   uint8* data = new(std::nothrow) uint8[fBlockSize];
+   if (data == NULL) {
+       TRACE("Journal::_RecoverPassReplay(): Failed to allocate memory for "
+           "data\n");
+       return B_NO_MEMORY;
+   }
+
+   ArrayDeleter<uint8> dataDeleter(data);
+
+   while (nextCommitID < lastCommitID) {
+       if (!header->CheckMagic() || header->Sequence() != nextCommitID) {
+           // Somehow the log is different than the expexted
+           TRACE("Journal::_RecoverPassReplay(): Wierd problem with block\n");
+           return B_ERROR;
+       }
+
+       uint32 blockType = header->BlockType();
+
+       if (blockType == JOURNAL_DESCRIPTOR_BLOCK) {
+           JournalBlockTag* last_tag = (JournalBlockTag*)((uint8*)header
+               + fBlockSize - sizeof(JournalBlockTag));
+
+           for (JournalBlockTag* tag = (JournalBlockTag*)header->data;
+               tag <= last_tag; ++tag) {
+               nextBlock = _WrapAroundLog(nextBlock + 1);
+
+               status = MapBlock(nextBlock, nextBlockPos);
+               if (status != B_OK)
+                   return status;
+
+               if (!fRevokeManager->Lookup(tag->BlockNumber(),
+                       nextCommitID)) {
+                   // Block isn't revoked
+                   size_t read = read_pos(fJournalVolume->Device(),
+                       nextBlockPos * fBlockSize, data, fBlockSize);
+                   if (read != fBlockSize)
+                       return B_IO_ERROR;
+
+                   if ((tag->Flags() & JOURNAL_FLAG_ESCAPED) != 0) {
+                       // Block is escaped
+                       ((int32*)data)[0]
+                           = B_HOST_TO_BENDIAN_INT32(JOURNAL_MAGIC);
+                   }
+
+                   TRACE("Journal::_RevoverPassReplay(): Write to %lu\n",
+                       tag->BlockNumber() * fBlockSize);
+                   size_t written = write_pos(fFilesystemVolume->Device(),
+                       tag->BlockNumber() * fBlockSize, data, fBlockSize);
+
+                   if (written != fBlockSize)
+                       return B_IO_ERROR;
+
+                   ++count;
+               }
+
+               if ((tag->Flags() & JOURNAL_FLAG_LAST_TAG) != 0)
+                   break;
+               if ((tag->Flags() & JOURNAL_FLAG_SAME_UUID) == 0) {
+                   // TODO: Check new UUID with file system UUID
+                   tag += 2;
+                       // sizeof(JournalBlockTag) = 8
+                       // sizeof(UUID) = 16
+               }
+           }
+       }
+       else if (blockType == JOURNAL_COMMIT_BLOCK)
+           nextCommitID++;
+       else if (blockType != JOURNAL_REVOKE_BLOCK) {
+               // TODO: Warn that we found an unrecognized block
+           break;
+       } // If blockType == JOURNAL_REVOKE_BLOCK we just skip it
+
+       nextBlock = _WrapAroundLog(nextBlock + 1);
+
+       status = MapBlock(nextBlock, nextBlockPos);
+       if (status != B_OK)
+           return status;
+
+       header = (JournalHeader*)cached.SetTo(nextBlockPos);
+   }
+
+   if (nextCommitID != lastCommitID) {
+       // Possibly because of some sort of IO error
+       return B_ERROR;
+   }
+
+   TRACE("Journal recovery pass replay: Replayed blocks: %u\n", count);
+
+   return B_OK;
+}
+
+
+status_t
+Journal::_FlushLog(bool canWait, bool flushBlocks)
+{
+   TRACE("Journal::_FlushLog()\n");
+   status_t status = canWait ? recursive_lock_lock(&fLock)
+       : recursive_lock_trylock(&fLock);
+   if (status != B_OK)
+       return status;
+
+   TRACE("Journal::_FlushLog(): Acquired fLock, recursion: %ld\n",
+       recursive_lock_get_recursion(&fLock));
+
+   if (recursive_lock_get_recursion(&fLock) > 1) {
+       // Called from inside a transaction
+       recursive_lock_unlock(&fLock);
+       TRACE("Journal::_FlushLog(): Called from a transaction. Leaving...\n");
+       return B_OK;
+   }
+
+   if (fUnwrittenTransactions != 0 && _FullTransactionSize() != 0) {
+       status = _WriteTransactionToLog();
+       if (status < B_OK)
+           panic("Failed flushing transaction: %s\n", strerror(status));
+   }
+
+   TRACE("Journal::_FlushLog(): Attempting to flush journal volume at %p\n",
+       fJournalVolume);
+
+   // TODO: Not sure this is correct. Need to review...
+   status = fJournalVolume->FlushDevice();
+   if (status != B_OK)
+       return status;
+
+   TRACE("Journal::_FlushLog(): Flushed journal volume\n");
+
+   if (flushBlocks) {
+       TRACE("Journal::_FlushLog(): Attempting to flush file system volume "
+           "at %p\n", fFilesystemVolume);
+       status = fFilesystemVolume->FlushDevice();
+       if (status == B_OK)
+           TRACE("Journal::_FlushLog(): Flushed file system volume\n");
+   }
+
+   TRACE("Journal::_FlushLog(): Finished. Releasing lock\n");
+
+   recursive_lock_unlock(&fLock);
+
+   TRACE("Journal::_FlushLog(): Done, final status: %s\n", strerror(status));
+   return status;
+}
+
+
+inline uint32
+Journal::_WrapAroundLog(uint32 block)
+{
+   TRACE("Journal::_WrapAroundLog()\n");
+   if (block >= fLogSize)
+       return block - fLogSize + fFirstLogBlock;
+   else
+       return block;
+}
+
+
+size_t
+Journal::_CurrentTransactionSize() const
+{
+   TRACE("Journal::_CurrentTransactionSize(): transaction %ld\n",
+       fTransactionID);
+
+   size_t count;
+
+   if (fHasSubTransaction) {
+       count = cache_blocks_in_sub_transaction(fFilesystemBlockCache,
+           fTransactionID);
+
+       TRACE("\tSub transaction size: %ld\n", count);
+   } else {
+       count =  cache_blocks_in_transaction(fFilesystemBlockCache,
+           fTransactionID);
+
+       TRACE("\tTransaction size: %ld\n", count);
+   }
+
+   return count;
+}
+
+
+size_t
+Journal::_FullTransactionSize() const
+{
+   TRACE("Journal::_FullTransactionSize(): transaction %ld\n", fTransactionID);
+   TRACE("\tFile sytem block cache: %p\n", fFilesystemBlockCache);
+
+   size_t count = cache_blocks_in_transaction(fFilesystemBlockCache,
+        fTransactionID);
+
+   TRACE("\tFull transaction size: %ld\n", count);
+
+   return count;
+}
+
+
+size_t
+Journal::_MainTransactionSize() const
+{
+   TRACE("Journal::_MainTransactionSize(): transaction %ld\n", fTransactionID);
+
+   size_t count =  cache_blocks_in_main_transaction(fFilesystemBlockCache,
+       fTransactionID);
+
+   TRACE("\tMain transaction size: %ld\n", count);
+
+   return count;
+}
+
+
+status_t
+Journal::_TransactionDone(bool success)
+{
+   if (!success) {
+       if (fHasSubTransaction) {
+           TRACE("Journal::_TransactionDone(): transaction %ld failed, "
+               "aborting subtransaction\n", fTransactionID);
+           cache_abort_sub_transaction(fFilesystemBlockCache, fTransactionID);
+           // parent is unaffected
+       } else {
+           TRACE("Journal::_TransactionDone(): transaction %ld failed,"
+               " aborting\n", fTransactionID);
+           cache_abort_transaction(fFilesystemBlockCache, fTransactionID);
+           fUnwrittenTransactions = 0;
+       }
+
+       return B_OK;
+   }
+
+   // If possible, delay flushing the transaction
+   uint32 size = _FullTransactionSize();
+   TRACE("Journal::_TransactionDone(): full transaction size: %lu, max "
+       "transaction size: %lu, free log blocks: %lu\n", size,
+       fMaxTransactionSize, FreeLogBlocks());
+   if (fMaxTransactionSize > 0 && size < fMaxTransactionSize) {
+       TRACE("Journal::_TransactionDone(): delaying flush of transaction "
+           "%ld\n", fTransactionID);
+
+       // Make sure the transaction fits in the log
+       if (size < FreeLogBlocks())
+           cache_sync_transaction(fFilesystemBlockCache, fTransactionID);
+
+       fUnwrittenTransactions++;
+       return B_OK;
+   }
+
+   return _WriteTransactionToLog();
+}
+
+
+/*static*/ void
+Journal::_TransactionWritten(int32 transactionID, int32 event, void* _logEntry)
+{
+   LogEntry* logEntry = (LogEntry*)_logEntry;
+
+   TRACE("Journal::_TransactionWritten(): Transaction %ld checkpointed\n",
+       transactionID);
+
+   Journal* journal = logEntry->GetJournal();
+
+   TRACE("Journal::_TransactionWritten(): log entry: %p, journal: %p\n",
+       logEntry, journal);
+   TRACE("Journal::_TransactionWritten(): log entries: %p\n",
+       &journal->fLogEntries);
+
+   mutex_lock(&journal->fLogEntriesLock);
+
+   TRACE("Journal::_TransactionWritten(): first log entry: %p\n",
+       journal->fLogEntries.First());
+   if (logEntry == journal->fLogEntries.First()) {
+       TRACE("Journal::_TransactionWritten(): Moving start of log to %lu\n",
+           logEntry->Start());
+       journal->fLogStart = logEntry->Start();
+       journal->fFirstCommitID = logEntry->CommitID();
+       TRACE("Journal::_TransactionWritten(): Setting commit ID to %lu\n",
+           logEntry->CommitID());
+
+       if (journal->_SaveSuperBlock() != B_OK)
+           panic("ext2: Failed to write journal superblock\n");
+   }
+
+   TRACE("Journal::_TransactionWritten(): Removing log entry\n");
+   journal->fLogEntries.Remove(logEntry);
+
+   TRACE("Journal::_TransactionWritten(): Unlocking entries list\n");
+   mutex_unlock(&journal->fLogEntriesLock);
+
+   TRACE("Journal::_TransactionWritten(): Deleting log entry at %p\n", logEntry);
+   delete logEntry;
+}
+
+
+/*static*/ void
+Journal::_TransactionIdle(int32 transactionID, int32 event, void* _journal)
+{
+   Journal* journal = (Journal*)_journal;
+   journal->_FlushLog(false, false);
+}

Property changes on: src/add-ons/kernel/file_systems/ext2/Journal.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/NoJournal.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/NoJournal.h    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/NoJournal.h    (revision 0)
@@ -0,0 +1,34 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef NOJOURNAL_H
+#define NOJOURNAL_H
+
+
+#include "Journal.h"
+
+
+class NoJournal : public Journal {
+public:
+                       NoJournal(Volume* volume);
+                       ~NoJournal();
+
+           status_t    InitCheck();
+           status_t    Recover();
+           status_t    StartLog();
+
+           status_t    Lock(Transaction* owner, bool separateSubTransactions);
+           status_t    Unlock(Transaction* owner, bool success);
+
+private:
+           status_t    _WriteTransactionToLog();
+
+   static  void        _TransactionWritten(int32 transactionID,
+                           int32 event, void* param);
+};
+
+#endif // NOJOURNAL_H
Index: src/add-ons/kernel/file_systems/ext2/HTree.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HTree.h    (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/HTree.h    (working copy)
@@ -9,8 +9,6 @@
 #define HTREE_H


-#include <AutoDeleter.h>
-
 #include "ext2.h"
 #include "DirectoryIterator.h"
 #include "HTreeEntryIterator.h"
@@ -94,6 +92,9 @@
                                HTree(Volume* volume, Inode* directory);
                                ~HTree();

+           status_t            PrepareForHash();
+           uint32              Hash(const char* name, uint8 length);
+
            status_t            Lookup(const char* name,
                                    DirectoryIterator** directory);

@@ -102,9 +103,7 @@
                                    off_t& lastEntry,
                                    uint32 remainingIndirects);

-           uint32              _Hash(const char* name, uint8 version);
-
-           uint32              _HashLegacy(const char* name);
+           uint32              _HashLegacy(const char* name, uint8 length);

    inline  uint32              _MD4F(uint32 x, uint32 y, uint32 z);
    inline  uint32              _MD4G(uint32 x, uint32 y, uint32 z);
@@ -113,11 +112,11 @@
                                    uint32& c, uint32& d);
            void                _HalfMD4Transform(uint32 buffer[4],
                                    uint32 blocks[8]);
-           uint32              _HashHalfMD4(const char* name);
+           uint32              _HashHalfMD4(const char* name, uint8 length);

            void                _TEATransform(uint32 buffer[4],
                                    uint32 blocks[4]);
-           uint32              _HashTEA(const char* name);
+           uint32              _HashTEA(const char* name, uint8 length);

            void                _PrepareBlocksForHash(const char* string,
                                    int length, uint32* blocks, int numBlocks);
@@ -127,7 +126,7 @@
            Inode*              fDirectory;
            uint32              fHashSeed[4];
            HTreeEntryIterator* fRootEntry;
-           ObjectDeleter<HTreeEntryIterator> fRootDeleter;
+           uint8               fHashVersion;
 };

 #endif // HTREE_H

Property changes on: src/add-ons/kernel/file_systems/ext2/HTree.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp   (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp   (working copy)
@@ -9,12 +9,19 @@

 #include "IndexedDirectoryIterator.h"

+#include <string.h>
+
+#include <util/VectorSet.h>
+
+#include "CachedBlock.h"
 #include "ext2.h"
 #include "HTree.h"
 #include "HTreeEntryIterator.h"
 #include "Inode.h"


+//#define COLLISION_TEST
+
 //#define TRACE_EXT2
 #ifdef TRACE_EXT2
 #  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
@@ -23,18 +30,32 @@
 #endif


+struct HashedEntry
+{
+   uint8*  position;
+   uint32  hash;
+
+   bool    operator<(const HashedEntry& other) const
+   {
+       return hash <= other.hash;
+   }
+
+   bool    operator>(const HashedEntry& other) const
+   {
+       return hash >= other.hash;
+   }
+};
+
+
 IndexedDirectoryIterator::IndexedDirectoryIterator(off_t start,
-   uint32 blockSize, Inode* directory, HTreeEntryIterator* parent)
+   Inode* directory, HTreeEntryIterator* parent)
    :
-   DirectoryIterator(directory),
+   DirectoryIterator(directory, start),
    fIndexing(true),
-
    fParent(parent),
-   fMaxOffset(start + blockSize),
-   fBlockSize(blockSize),
    fMaxAttempts(0)
 {
-   fOffset = start;
+   fPreviousBlock = fLogicalBlock;
 }


@@ -46,16 +67,36 @@
 status_t
 IndexedDirectoryIterator::GetNext(char* name, size_t* nameLength, ino_t* id)
 {
-   if (fIndexing && fOffset + sizeof(HTreeFakeDirEntry) >= fMaxOffset) {
+   TRACE("IndexedDirectoryIterator::GetNext(): name: %p, name length: %p = %ld,"
+       " id: %p\n", name , nameLength, *nameLength, id);
+   TRACE("IndexedDirectoryIterator::GetNext(): logical block: %lu, previous "
+       "block: %lu\n", fLogicalBlock, fPreviousBlock);
+   if (fIndexing)
+       TRACE("IndexedDirectoryIterator::GetNext(): Indexing\n");
+
+   if (fIndexing && fLogicalBlock != fPreviousBlock) {
        TRACE("IndexedDirectoryIterator::GetNext() calling next block\n");
-       status_t status = fParent->GetNext(fOffset);
+
+       if (!fParent->HasCollision()) {
+           TRACE("IndexedDirectoryIterator::GetNext(): next block doesn't "
+               "contain collisions from previous block\n");
+#ifndef COLLISION_TEST
+           return B_ENTRY_NOT_FOUND;
+#endif
+       }
+
+       fDisplacement = 0;
+       status_t status = fParent->GetNext(fLogicalBlock);
        if (status != B_OK)
            return status;

-       if (fMaxAttempts++ > 4)
-           return B_ERROR;
+       fPreviousBlock = fLogicalBlock;
+       status = fInode->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock);
+       if (status != B_OK)
+           return status;

-       fMaxOffset = fOffset + fBlockSize;
+       /*if (fMaxAttempts++ > 4)
+           return B_ERROR;*/
    }

    return DirectoryIterator::GetNext(name, nameLength, id);
@@ -67,9 +108,185 @@
 {
    // The only way to rewind it is too loose indexing

-   fOffset = 0;
-   fMaxOffset = fInode->Size();
+   fLogicalBlock = 0;
+   fPreviousBlock = 0;
+   fDisplacement = 0;
    fIndexing = false;

-   return B_OK;
+   return fInode->FindBlock(fLogicalBlock, fPhysicalBlock);
 }
+
+
+status_t
+IndexedDirectoryIterator::AddEntry(Transaction& transaction, const char* name,
+   size_t _nameLength, ino_t id)
+{
+   uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH
+       : _nameLength;
+   uint16 pos = 0;
+   uint16 newLength = 0;
+
+   if (_AllocateBestEntryInBlock(nameLength, pos, newLength) == B_OK) {
+       CachedBlock cached(fInode->GetVolume());
+       uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
+
+       ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos];
+       uint16 previousLength = dirEntry->Length();
+       dirEntry->SetLength(newLength);
+
+       dirEntry = (ext2_dir_entry*)&block[pos + newLength];
+       dirEntry->SetLength(previousLength - newLength);
+       dirEntry->name_length = nameLength;
+       dirEntry->SetInodeID(id);
+       memcpy(dirEntry->name, name, nameLength);
+
+       return B_OK;
+   }
+
+   // Block is full, split required
+   // Add another block to the directory file
+   uint32 lastBlock = (fInode->Size() + 1) / fBlockSize;
+
+   status_t status = fInode->Resize(transaction, (lastBlock + 2) * fBlockSize);
+   if (status != B_OK)
+       return status;
+
+   // Allocate a buffer for the entries in the block
+   uint8* buffer = new(std::nothrow) uint8[fBlockSize];
+   if (buffer == NULL)
+       return B_NO_MEMORY;
+   ArrayDeleter<uint8> bufferDeleter(buffer);
+
+   // Prepare block to hold the first half of the entries
+   CachedBlock cachedFirst(fInode->GetVolume());
+   uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock);
+   if (firstBlock == NULL)
+       return B_IO_ERROR;
+
+   // Save all entries in the buffer
+   memcpy(buffer, firstBlock, fBlockSize);
+
+   // Prepare block to hold the second half of the entries
+   fDisplacement = 0;
+   fLogicalBlock = lastBlock + 1;
+
+   status = fInode->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock);
+   if (status != B_OK)
+       return status;
+
+   CachedBlock cachedSecond(fInode->GetVolume());
+   uint8* secondBlock = cachedSecond.SetToWritable(transaction,
+       fPhysicalBlock);
+   if (secondBlock == NULL)
+       return B_IO_ERROR;
+
+   // Sort entries
+   VectorSet<HashedEntry> entrySet;
+
+   HTree htree(fInode->GetVolume(), fInode);
+   status = htree.PrepareForHash();
+   if (status != B_OK)
+       return B_OK;
+
+   HashedEntry entry;
+
+   uint32 displacement = 0;
+   ext2_dir_entry* dirEntry;
+
+   while (displacement < fBlockSize) {
+       entry.position = &firstBlock[displacement];
+       dirEntry = (ext2_dir_entry*)entry.position;
+
+       entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length);
+
+       status = entrySet.Insert(entry);
+       if (status != B_OK)
+           return status;
+
+       displacement += dirEntry->Length();
+   }
+
+   // Prepare the new entry to be included as well
+   ext2_dir_entry newEntry;
+
+   newLength = (uint16)nameLength;
+   if (newLength % 4 != 0)
+       newLength += 4 - newLength % 4;
+
+   newEntry.name_length = nameLength;
+   newEntry.SetLength(newLength);
+   newEntry.SetInodeID(id);
+   memcpy(newEntry.name, name, nameLength);
+
+   entry.position = (uint8*)&newEntry;
+   entry.hash = htree.Hash(name, nameLength);
+
+   entrySet.Insert(entry);
+
+   // Move first half of entries to the first block
+   VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin();
+   int32 median = entrySet.Count() / 2;
+   displacement = 0;
+
+   for (int32 i = 0; i < median; ++i) {
+       dirEntry = (ext2_dir_entry*)(*iterator).position;
+
+       memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length());
+
+       displacement += dirEntry->Length();
+       iterator++;
+   }
+
+   // Save the hash to store in the parent
+   iterator--;
+   uint32 medianHash = (*iterator).hash;
+   iterator++;
+   bool collision = false;
+
+   while ((*iterator).hash == medianHash) {
+       // Keep collisions on the same block
+       // This isn't the ideal solution, but it is a rare occurance
+       dirEntry = (ext2_dir_entry*)(*iterator).position;
+
+       if (displacement + dirEntry->Length() > fBlockSize) {
+           // Doesn't fit on the block
+           --iterator;
+           dirEntry = (ext2_dir_entry*)(*iterator).position;
+           ++iterator;
+
+           collision = true;
+           break;
+       }
+
+       memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length());
+
+       displacement += dirEntry->Length();
+       iterator++;
+   }
+
+   // Update last entry in the block
+   uint16 oldLength = dirEntry->Length();
+   dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength];
+   dirEntry->SetLength(fBlockSize - displacement + oldLength);
+
+   // Move the second half of the entries to the second block
+   VectorSet<HashedEntry>::Iterator end = entrySet.End();
+   displacement = 0;
+
+   while (iterator != end) {
+       dirEntry = (ext2_dir_entry*)(*iterator).position;
+
+       memcpy(&secondBlock[displacement], dirEntry, dirEntry->Length());
+
+       displacement += dirEntry->Length();
+       iterator++;
+   }
+
+   // Update last entry in the block
+   oldLength = dirEntry->Length();
+   dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength];
+   dirEntry->SetLength(fBlockSize - displacement + oldLength);
+
+   // Update parent
+   return fParent->InsertEntry(medianHash, fLogicalBlock, collision);
+}
Index: src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h    (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h    (working copy)
@@ -8,7 +8,9 @@

 #include <SupportDefs.h>

+#include "Transaction.h"

+
 class Inode;

 class DirectoryIterator {
@@ -16,18 +18,35 @@
                        DirectoryIterator(Inode* inode);
    virtual             ~DirectoryIterator();

+   virtual status_t    InitCheck();
+
    virtual status_t    GetNext(char* name, size_t* _nameLength, ino_t* id);

    virtual status_t    Rewind();

+   virtual status_t    AddEntry(Transaction& transaction, const char* name,
+                           size_t nameLength, ino_t id);
+
 private:
                        DirectoryIterator(const DirectoryIterator&);
                        DirectoryIterator &operator=(const DirectoryIterator&);
                            // no implementation

+
 protected:
+                       DirectoryIterator(Inode* inode, off_t offset);
+
+           status_t    _AllocateBestEntryInBlock(uint8 nameLength, uint16& pos,
+                           uint16& newLength);
+
+
    Inode*              fInode;
-   off_t               fOffset;
+   uint32              fBlockSize;
+   uint32              fLogicalBlock;
+   uint32              fPhysicalBlock;
+   uint32              fDisplacement;
+   status_t            fInitStatus;
 };

 #endif // DIRECTORY_ITERATOR_H
+
Index: src/add-ons/kernel/file_systems/ext2/RevokeManager.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/RevokeManager.cpp  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/RevokeManager.cpp  (revision 0)
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "RevokeManager.h"
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+RevokeManager::RevokeManager()
+   :
+   fRevokeCount(0)
+{
+}
+
+
+RevokeManager::~RevokeManager()
+{
+}
+
+
+status_t
+RevokeManager::ScanRevokeBlock(JournalRevokeHeader* revokeBlock, uint32 commitID)
+{
+   TRACE("RevokeManager::ScanRevokeBlock(): Commit ID: %lu\n", commitID);
+   int count = revokeBlock->NumBytes() >> 3;
+
+   for (int i = 0; i < count; ++i) {
+       TRACE("RevokeManager::ScanRevokeBlock(): Found a revoke block: %lu\n",
+           revokeBlock->RevokeBlock(i));
+       status_t status = Insert(revokeBlock->RevokeBlock(i), commitID);
+
+       if (status != B_OK) {
+           TRACE("RevokeManager::ScanRevokeBlock(): Error inserting\n");
+           return status;
+       }
+   }
+
+   return B_OK;
+}
+

Property changes on: src/add-ons/kernel/file_systems/ext2/RevokeManager.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/Jamfile
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Jamfile    (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/Jamfile    (working copy)
@@ -7,6 +7,7 @@
 }

 #UsePrivateHeaders [ FDirName kernel disk_device_manager ] ;
+UsePrivateHeaders [ FDirName kernel util ] ;
 UsePrivateHeaders shared storage ;
 UsePrivateKernelHeaders ;

@@ -18,6 +19,15 @@
    IndexedDirectoryIterator.cpp
    HTree.cpp
    HTreeEntryIterator.cpp
+   RevokeManager.cpp
+   HashRevokeManager.cpp
+   Journal.cpp
+   NoJournal.cpp
+   InodeJournal.cpp
+   Transaction.cpp
+   BitmapBlock.cpp
+   BlockAllocator.cpp
+   InodeAllocator.cpp

    kernel_interface.cpp
 ;
Index: src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp    (revision 0)
@@ -0,0 +1,639 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "BitmapBlock.h"
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+BitmapBlock::BitmapBlock(Volume* volume, uint32 numBits)
+   :
+   CachedBlock(volume),
+   fData(NULL),
+   fReadOnlyData(NULL),
+   fNumBits(numBits)
+{
+   TRACE("BitmapBlock::BitmapBlock(): num bits: %lu\n", fNumBits);
+}
+
+
+BitmapBlock::~BitmapBlock()
+{
+}
+
+
+/*virtual*/ bool
+BitmapBlock::SetTo(uint32 block)
+{
+   fData = NULL;
+   fReadOnlyData = (uint32*)CachedBlock::SetTo(block);
+
+   return fReadOnlyData != NULL;
+}
+
+
+/*virtual*/ bool
+BitmapBlock::SetToWritable(Transaction& transaction, uint32 block, bool empty)
+{
+   fReadOnlyData = NULL;
+   fData = (uint32*)CachedBlock::SetToWritable(transaction, block, empty);
+
+   return fData != NULL;
+}
+
+
+/*virtual*/ bool
+BitmapBlock::CheckUnmarked(uint32 start, uint32 length)
+{
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return false;
+
+   if (start + length > fNumBits)
+       return false;
+
+   uint32 startIndex = start >> 5;
+   uint32 startBit = start & 0x1F;
+   uint32 remainingBits = (length - startBit) & 0x1F;
+
+   uint32 iterations;
+
+   if (length < 32) {
+       if (startBit + length < 32) {
+           uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
+
+           uint32 mask = (1 << startBit + length) - 1;
+           mask &= ~((1 << startBit) - 1);
+
+           return (bits & mask) == 0;
+       } else
+           iterations = 0;
+   } else
+       iterations = (length - 32 + startBit) >> 5;
+
+   uint32 index = startIndex;
+   uint32 mask = 0;
+
+   if (startBit != 0) {
+       mask = ~((1 << startBit) - 1);
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+
+       if ((bits & mask) != 0)
+           return false;
+
+       index += 1;
+   }
+
+   for (; iterations > 0; --iterations) {
+       if (data[index++] != 0)
+           return false;
+   }
+
+   if (remainingBits != 0) {
+       mask = (1 << remainingBits + 1) - 1;
+
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+       if ((bits & mask) != 0)
+           return false;
+   }
+
+   return true;
+}
+
+
+/*virtual*/ bool
+BitmapBlock::CheckMarked(uint32 start, uint32 length)
+{
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return false;
+
+   if (start + length > fNumBits)
+       return false;
+
+   uint32 startIndex = start >> 5;
+   uint32 startBit = start & 0x1F;
+   uint32 remainingBits = (length - startBit) & 0x1F;
+
+   uint32 iterations;
+
+   if (length < 32) {
+       if (startBit + length < 32) {
+           uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
+
+           uint32 mask = (1 << startBit + length) - 1;
+           mask &= ~((1 << startBit) - 1);
+
+           return (bits & mask) != 0;
+       } else
+           iterations = 0;
+   } else
+       iterations = (length - 32 + startBit) >> 5;
+
+   uint32 index = startIndex;
+   uint32 mask = 0;
+
+   if (startBit != 0) {
+       mask = ~((1 << startBit) - 1);
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+
+       if ((bits & mask) != mask)
+           return false;
+
+       index += 1;
+   }
+
+   mask = 0xFFFFFFFF;
+   for (; iterations > 0; --iterations) {
+       if (data[index++] != mask)
+           return false;
+   }
+
+   if (remainingBits != 0) {
+       mask = (1 << remainingBits + 1) - 1;
+       uint32 bits = B_HOST_TO_LENDIAN_INT32(data[index]);
+
+       if ((bits & mask) != mask)
+           return false;
+   }
+
+   return true;
+}
+
+
+/*virtual*/ bool
+BitmapBlock::Mark(uint32 start, uint32 length, bool force)
+{
+   if (fData == NULL || start + length > fNumBits)
+       return false;
+
+   uint32 startIndex = start >> 5;
+   uint32 startBit = start & 0x1F;
+   uint32 remainingBits = (length - 32 + startBit) & 0x1F;
+
+   uint32 iterations;
+
+   if (length < 32) {
+       if (startBit + length < 32) {
+           uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
+
+           uint32 mask = (1 << startBit + length) - 1;
+           mask &= ~((1 << startBit) - 1);
+
+           if ((bits & mask) != 0)
+               return false;
+
+           bits |= mask;
+
+           fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
+
+           return true;
+       } else
+           iterations = 0;
+   } else
+       iterations = (length - 32 + startBit) >> 5;
+
+   uint32 index = startIndex;
+   uint32 mask = 0;
+
+   TRACE("BitmapBlock::Mark(): start: %lu, length: %lu, startIndex: %lu, "
+       "startBit: %lu, iterations: %lu, remainingBits: %lu\n", start, length,
+       startIndex, startBit, iterations, remainingBits);
+
+   if (startBit != 0) {
+       mask = ~((1 << startBit) - 1);
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+
+       TRACE("BitmapBlock::Mark(): mask: %lX, bits: %lX\n", mask, bits);
+
+       if (!force && (bits & mask) != 0)
+           return false;
+
+       bits |= mask;
+       fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+
+       index += 1;
+   }
+
+   mask = 0xFFFFFFFF;
+   for (; iterations > 0; --iterations) {
+       if (!force && fData[index] != 0)
+           return false;
+       fData[index++] |= mask;
+   }
+
+   if (remainingBits != 0) {
+       mask = (1 << remainingBits) - 1;
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+       TRACE("BitmapBlock::(): marking remaining %lu bits: %lX, mask: %lX\n",
+           remainingBits, bits, mask);
+
+       if (!force && (bits & mask) != 0)
+           return false;
+
+       bits |= mask;
+       fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+   }
+
+   return true;
+}
+
+
+/*virtual*/ bool
+BitmapBlock::Unmark(uint32 start, uint32 length, bool force)
+{
+   if (fData == NULL || start + length > fNumBits)
+       return false;
+
+   uint32 startIndex = start >> 5;
+   uint32 startBit = start & 0x1F;
+   uint32 remainingBits = (length - 32 + startBit) & 0x1F;
+
+   uint32 iterations;
+
+   if (length < 32) {
+       if (startBit + length < 32) {
+           uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
+
+           uint32 mask = (1 << startBit + length) - 1;
+           mask &= ~((1 << startBit) - 1);
+
+           if ((bits & mask) != mask)
+               return false;
+
+           bits &= ~mask;
+
+           fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
+
+           return true;
+       } else
+           iterations = 0;
+   } else
+       iterations = (length - 32 + startBit) >> 5;
+
+   uint32 index = startIndex;
+   uint32 mask = 0;
+
+   if (startBit != 0) {
+       mask = ~((1 << startBit) - 1);
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+
+       if (!force && (bits & mask) != mask)
+           return false;
+
+       bits &= ~mask;
+       fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+
+       index += 1;
+   }
+
+   mask = 0xFFFFFFFF;
+   for (; iterations > 0; --iterations) {
+       if (!force && fData[index] != mask)
+           return false;
+       fData[index++] = 0;
+   }
+
+   if (remainingBits != 0) {
+       mask = (1 << remainingBits) - 1;
+       uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+
+       if (!force && (bits & mask) != mask)
+           return false;
+
+       bits &= ~mask;
+       fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+   }
+
+   return true;
+}
+
+
+void
+BitmapBlock::FindNextMarked(uint32& pos)
+{
+   TRACE("BitmapBlock::FindNextMarked(): pos: %lu\n", pos);
+
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return;
+
+   if (pos >= fNumBits) {
+       pos = fNumBits;
+       return;
+   }
+
+   uint32 index = pos >> 5;
+   uint32 bit = pos & 0x1F;
+
+   uint32 mask = (1 << bit) - 1;
+   uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+
+   TRACE("BitmapBlock::FindNextMarked(): index: %lu, bit: %lu, mask: %lX, "
+       "bits: %lX\n", index, bit, mask, bits);
+
+   bits = bits & ~mask;
+
+   if (bits == 0) {
+       // Find an block of 32 bits that has a marked bit
+       uint32 maxIndex = fNumBits >> 5;
+       TRACE("BitmapBlock::FindNextMarked(): max index: %lu\n", maxIndex);
+
+       do {
+           index++;
+       } while (index < maxIndex && data[index] == 0);
+
+       if (index >= maxIndex) {
+           // Not found
+           TRACE("BitmapBlock::FindNextMarked(): reached end of block, num "
+               "bits: %lu\n", fNumBits);
+           pos = fNumBits;
+           return;
+       }
+
+       bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+       bit = 0;
+   }
+
+   for (; bit < 32; ++bit) {
+       // Find the marked bit
+       if ((bits >> bit & 1) != 0) {
+           pos = index << 5 | bit;
+           TRACE("BitmapBlock::FindNextMarked(): found bit: %lu\n", pos);
+           return;
+       }
+   }
+
+   panic("Couldn't find marked bit inside an int32 which is different than "
+       "zero!?\n");
+}
+
+
+void
+BitmapBlock::FindNextUnmarked(uint32& pos)
+{
+   TRACE("BitmapBlock::FindNextUnmarked(): pos: %lu\n", pos);
+
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return;
+
+   if (pos >= fNumBits) {
+       pos = fNumBits;
+       return;
+   }
+
+   uint32 index = pos >> 5;
+   uint32 bit = pos & 0x1F;
+
+   uint32 mask = (1 << bit) - 1;
+   uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+
+   TRACE("BitmapBlock::FindNextUnmarked(): index: %lu, bit: %lu, mask: %lX, "
+       "bits: %lX\n", index, bit, mask, bits);
+
+   bits &= ~mask;
+
+   if (bits == ~mask) {
+       // Find an block of 32 bits that has a unmarked bit
+       uint32 maxIndex = fNumBits >> 5;
+       TRACE("BitmapBlock::FindNextUnmarked(): max index: %lu\n", maxIndex);
+
+       do {
+           index++;
+       } while (index < maxIndex && data[index] == 0xFFFFFFFF);
+
+       if (index >= maxIndex) {
+           // Not found
+           TRACE("BitmapBlock::FindNextUnmarked(): reached end of block, num "
+               "bits: %lu\n", fNumBits);
+           pos = fNumBits;
+           return;
+       }
+
+       bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+       bit = 0;
+   }
+
+   for (; bit < 32; ++bit) {
+       // Find the unmarked bit
+       if ((bits >> bit & 1) == 0) {
+           pos = index << 5 | bit;
+           TRACE("BitmapBlock::FindNextUnmarked(): found bit: %lu\n", pos);
+           return;
+       }
+   }
+
+   panic("Couldn't find unmarked bit inside an int32 whith value zero!?\n");
+}
+
+
+void
+BitmapBlock::FindPreviousMarked(uint32& pos)
+{
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return;
+
+   if (pos >= fNumBits)
+       pos = fNumBits;
+
+   if (pos == 0)
+       return;
+
+   uint32 index = pos >> 5;
+   uint32 bit = pos & 0x1F;
+
+   uint32 mask = (1 << bit + 1) - 1;
+   uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+   bits = bits & mask;
+
+   if (bits == 0) {
+       // Find an block of 32 bits that has a marked bit
+       do { index--; }
+           while (data[index] == 0 && index >= 0);
+
+       bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+       if (bits == 0) {
+           // Not found
+           pos = 0;
+           return;
+       }
+
+       bit = 31;
+   }
+
+   for (; bit >= 0; --bit) {
+       // Find the unmarked bit
+       if ((bits >> bit & 1) == 0) {
+           pos = index << 5 | bit;
+           return;
+       }
+   }
+
+   panic("Couldn't find marked bit inside an int32 whith value different than "
+       "zero!?\n");
+}
+
+
+void
+BitmapBlock::FindLargestUnmarkedRange(uint32& start, uint32& length)
+{
+   const uint32* data = fData == NULL ? fReadOnlyData : fData;
+   if (data == NULL)
+       return;
+
+   uint32 wordSpan = length >> 5;
+   uint32 lastIndex = fNumBits >> 5;
+   uint32 startIndex = 0;
+   uint32 index = 0;
+   uint32 bits = B_LENDIAN_TO_HOST_INT32(data[0]);
+
+   TRACE("BitmapBlock::FindLargestUnmarkedRange(): word span: %lu, last "
+       "index: %lu, start index: %lu, index: %lu, bits: %lX, start: %lu, "
+       "length: %lu\n", wordSpan, lastIndex, startIndex, index, bits, start,
+       length);
+
+   if (wordSpan == 0) {
+       uint32 startPos = 0;
+       uint32 endPos = 0;
+
+       while (endPos < fNumBits) {
+           FindNextUnmarked(startPos);
+           endPos = startPos;
+
+           if (startPos != fNumBits) {
+               FindNextMarked(endPos);
+
+               uint32 newLength = endPos - startPos;
+
+               if (newLength > length) {
+                   start = startPos;
+                   length = newLength;
+                   TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
+                       "larger length %lu starting at %lu\n", length, start);
+               }
+
+               startPos = endPos;
+
+               if (newLength >= 32)
+                   break;
+           }
+       }
+
+       if (endPos >= fNumBits)
+           return;
+
+       wordSpan = length >> 5;
+       startIndex = startPos >> 5;
+       index = (endPos >> 5) + 1;
+       bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+   }
+
+   for (; index < lastIndex; ++index) {
+       bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+
+       if (bits != 0) {
+           // Contains marked bits
+           if (index - startIndex >= wordSpan) {
+               uint32 newLength = index - startIndex - 1 << 5;
+               uint32 newStart = startIndex + 1 << 5;
+
+               uint32 startBits =
+                   B_LENDIAN_TO_HOST_INT32(data[startIndex]);
+
+               for (int32 bit = 31; bit >= 0; --bit) {
+                   if ((startBits >> bit & 1) != 0)
+                       break;
+
+                   ++newLength;
+                   --newStart;
+               }
+
+               for (int32 bit = 0; bit < 32; ++bit) {
+                   if ((bits >> bit & 1) != 0)
+                       break;
+
+                   ++newLength;
+               }
+
+               if (newLength > length) {
+                   start = newStart;
+                   length = newLength;
+                   wordSpan = length >> 5;
+
+                   TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
+                       "larger length %lu starting at %lu; word span: "
+                       "%lu\n", length, start, wordSpan);
+               }
+           }
+
+           startIndex = index;
+       }
+   }
+
+   --index;
+
+   if (index - startIndex >= wordSpan) {
+       uint32 newLength = index - startIndex << 5;
+       uint32 newStart = startIndex + 1 << 5;
+
+       TRACE("BitmapBlock::FindLargestUnmarkedRange(): Possibly found a "
+           "larger range. index: %lu, start index: %lu, word span: %lu, "
+           "new length: %lu, new start: %lu\n", index, startIndex, wordSpan,
+           newLength, newStart);
+
+       if (newStart != 0) {
+           uint32 startBits = B_LENDIAN_TO_HOST_INT32(data[startIndex]);
+
+           TRACE("BitmapBlock::FindLargestUnmarkedRange(): start bits: %lu\n",
+               startBits);
+
+           for (int32 bit = 31; bit >= 0; --bit) {
+               if ((startBits >> bit & 1) != 0)
+                   break;
+
+               ++newLength;
+               --newStart;
+           }
+
+           TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new start "
+               "to %lu and new length to %lu\n", newStart, newLength);
+       }
+
+       for (int32 bit = 0; bit < 32; ++bit) {
+           if ((bits >> bit & 1) == 0)
+               break;
+
+           ++newLength;
+       }
+
+       TRACE("BitmapBlock::FindLargestUnmarkedRange(): updated new length to "
+           "%lu\n", newLength);
+
+       if (newLength > length) {
+           start = newStart;
+           length = newLength;
+           TRACE("BitmapBlock::FindLargestUnmarkedRange(): Found "
+               "largest length %lu starting at %lu\n", length, start);
+       }
+   }
+}
+
+
+uint32
+BitmapBlock::NumBits() const
+{
+   return fNumBits;
+}

Property changes on: src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/InodeJournal.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/InodeJournal.cpp   (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/InodeJournal.cpp   (revision 0)
@@ -0,0 +1,90 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "InodeJournal.h"
+
+#include <new>
+
+#include <fs_cache.h>
+
+#include "HashRevokeManager.h"
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+InodeJournal::InodeJournal(Inode* inode)
+   :
+   Journal(),
+   fInode(inode)
+{
+   if (inode == NULL)
+       fInitStatus = B_BAD_DATA;
+   else {
+       Volume* volume = inode->GetVolume();
+
+       fFilesystemVolume = volume;
+       fFilesystemBlockCache = volume->BlockCache();
+       fJournalVolume = volume;
+       fJournalBlockCache = volume->BlockCache();
+
+       if (!inode->IsFileCacheDisabled())
+           fInitStatus = inode->DisableFileCache();
+       else
+           fInitStatus = B_OK;
+
+       if (fInitStatus == B_OK) {
+           TRACE("InodeJournal::InodeJournal(): Inode's file cache disabled "
+               "successfully\n");
+           HashRevokeManager* revokeManager = new(std::nothrow)
+               HashRevokeManager;
+           TRACE("InodeJournal::InodeJournal(): Allocated a hash revoke "
+               "manager at %p\n", revokeManager);
+
+           if (revokeManager == NULL) {
+               TRACE("InodeJournal::InodeJournal(): Insufficient memory to "
+                   "create the hash revoke manager\n");
+               fInitStatus = B_NO_MEMORY;
+           } else {
+               fInitStatus = revokeManager->Init();
+
+               if (fInitStatus == B_OK) {
+                   fRevokeManager = revokeManager;
+                   fInitStatus = _LoadSuperBlock();
+               }
+           }
+       }
+   }
+}
+
+
+InodeJournal::~InodeJournal()
+{
+}
+
+
+status_t
+InodeJournal::InitCheck()
+{
+   if (fInitStatus != B_OK)
+       TRACE("InodeJournal: Initialization error\n");
+   return fInitStatus;
+}
+
+
+status_t
+InodeJournal::MapBlock(uint32 logical, uint32& physical)
+{
+   TRACE("InodeJournal::MapBlock()\n");
+   return fInode->FindBlock(logical * fBlockSize, physical);
+}
Index: src/add-ons/kernel/file_systems/ext2/Transaction.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Transaction.h  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/Transaction.h  (revision 0)
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef TRANSACTION_H
+#define TRANSACTION_H
+
+
+#include <util/DoublyLinkedList.h>
+
+
+class Journal;
+class Volume;
+
+
+class TransactionListener
+   : public DoublyLinkedListLinkImpl<TransactionListener> {
+public:
+                               TransactionListener();
+   virtual                     ~TransactionListener();
+
+   virtual void                TransactionDone(bool success) = 0;
+   virtual void                RemovedFromTransaction() = 0;
+};
+
+typedef DoublyLinkedList<TransactionListener> TransactionListeners;
+
+
+class Transaction {
+public:
+                                   Transaction();
+                                   Transaction(Journal* journal);
+                                   ~Transaction();
+
+           status_t                Start(Journal* journal);
+           status_t                Done(bool success = true);
+
+           bool                    IsStarted() const;
+           bool                    HasParent() const;
+
+           status_t                WriteBlocks(off_t blockNumber,
+                                       const uint8* buffer,
+                                       size_t numBlocks = 1);
+
+           void                    Split();
+
+           Volume*                 GetVolume() const;
+           int32                   ID() const;
+
+           void                    AddListener(TransactionListener* listener);
+           void                    RemoveListener(
+                                       TransactionListener* listener);
+
+           void                    NotifyListeners(bool success);
+           void                    MoveListenersTo(Transaction* transaction);
+
+           void                    SetParent(Transaction* transaction);
+           Transaction*            Parent() const;
+private:
+                                   Transaction(const Transaction& other);
+           Transaction&            operator=(const Transaction& other);
+               // no implementation
+
+           Journal*                fJournal;
+           TransactionListeners    fListeners;
+           Transaction*            fParent;
+};
+
+#endif // TRANSACTION_H
Index: src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp (revision 0)
@@ -0,0 +1,661 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "BlockAllocator.h"
+
+#include <util/AutoLock.h>
+
+#include "BitmapBlock.h"
+#include "Inode.h"
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+class AllocationBlockGroup : public TransactionListener {
+public:
+                       AllocationBlockGroup();
+                       ~AllocationBlockGroup();
+
+           status_t    Initialize(Volume* v, uint32 blockGroup,
+                           uint32 numBits);
+
+           status_t    ScanFreeRanges();
+           bool        IsFull() const;
+
+           status_t    Allocate(Transaction& transaction, uint32 start,
+                           uint32 length);
+           status_t    Free(Transaction& transaction, uint32 start,
+                           uint32 length);
+           status_t    FreeAll(Transaction& transaction);
+           status_t    Check(uint32 start, uint32 length);
+
+           uint32      NumBits() const;
+           uint32      FreeBits() const;
+           uint32      Start() const;
+
+           uint32      LargestStart() const;
+           uint32      LargestLength() const;
+
+           // TransactionListener implementation
+           void        TransactionDone(bool success);
+           void        RemovedFromTransaction();
+
+private:
+           void        _AddFreeRange(uint32 start, uint32 length);
+
+
+           Volume*     fVolume;
+
+           uint32      fStart;
+           uint32      fNumBits;
+           uint32      fBitmapBlock;
+
+           uint32      fFreeBits;
+           uint32      fFirstFree;
+           uint32      fLargestStart;
+           uint32      fLargestLength;
+
+           uint32      fPreviousFreeBits;
+           uint32      fPreviousFirstFree;
+           uint32      fPreviousLargestStart;
+           uint32      fPreviousLargestLength;
+};
+
+
+class BlockAllocatorTransactionListener : public TransactionListener {
+public:
+                       BlockAllocatorTransactionListener(
+                           BlockAllocator* allocator, uint32 blocks);
+                       ~BlockAllocatorTransactionListener();
+
+           void        TransactionDone(bool success);
+           void        RemovedFromTransaction();
+private:
+           BlockAllocator* fAllocator;
+           uint32      fBlockAffected;
+};
+
+
+AllocationBlockGroup::AllocationBlockGroup()
+   :
+   fStart(0),
+   fNumBits(0),
+   fBitmapBlock(0),
+   fFreeBits(0),
+   fFirstFree(0),
+   fLargestStart(0),
+   fLargestLength(0),
+   fPreviousFreeBits(0),
+   fPreviousFirstFree(0),
+   fPreviousLargestStart(0),
+   fPreviousLargestLength(0)
+{
+}
+
+
+AllocationBlockGroup::~AllocationBlockGroup()
+{
+}
+
+
+status_t
+AllocationBlockGroup::Initialize(Volume* volume, uint32 blockGroup,
+   uint32 numBits)
+{
+   fVolume = volume;
+   fNumBits = numBits;
+
+   ext2_block_group* group;
+   status_t status = fVolume->GetBlockGroup(blockGroup, &group);
+   if (status != B_OK)
+       return status;
+
+   fBitmapBlock = group->BlockBitmap();
+
+   status = ScanFreeRanges();
+
+   fPreviousFreeBits = fFreeBits;
+   fPreviousFirstFree = fFirstFree;
+   fPreviousLargestStart = fLargestStart;
+   fPreviousLargestLength = fLargestLength;
+
+   return status;
+}
+
+
+status_t
+AllocationBlockGroup::ScanFreeRanges()
+{
+   TRACE("AllocationBlockGroup::ScanFreeRanges()\n");
+   BitmapBlock block(fVolume, fNumBits);
+
+   if (!block.SetTo(fBitmapBlock))
+       return B_ERROR;
+
+   uint32 start = 0;
+   uint32 end = 0;
+
+   while (end < fNumBits) {
+       block.FindNextUnmarked(start);
+       end = start;
+
+       if (start != block.NumBits()) {
+           block.FindNextMarked(end);
+           _AddFreeRange(start, end - start);
+           start = end;
+       }
+   }
+
+   return B_OK;
+}
+
+
+bool
+AllocationBlockGroup::IsFull() const
+{
+   return fFreeBits == 0;
+}
+
+
+status_t
+AllocationBlockGroup::Allocate(Transaction& transaction, uint32 start,
+   uint32 length)
+{
+   TRACE("AllocationBlockGroup::Allocate()\n");
+   uint32 end = start + length;
+   if (end > fLargestLength + fLargestStart)
+       return B_BAD_DATA;
+
+   BitmapBlock block(fVolume, fNumBits);
+
+   if (!block.SetToWritable(transaction, fBitmapBlock))
+       return B_ERROR;
+
+   if (!block.Mark(start, length)) {
+       TRACE("Failed to allocate blocks from %lu to %lu. Some were "
+           "already allocated.\n", start, start + length);
+       return B_ERROR;
+   }
+
+   transaction.AddListener(this);
+
+   fFreeBits -= length;
+
+   if (start == fLargestStart) {
+       if (fFirstFree == fLargestStart)
+           fFirstFree += length;
+
+       fLargestStart += length;
+       fLargestLength -= length;
+   } else if (start + length == fLargestStart + fLargestLength) {
+       fLargestLength -= length;
+   } else if (start < fLargestStart + fLargestLength
+           && start > fLargestStart) {
+       uint32 firstLength = start - fLargestStart;
+       uint32 secondLength = fLargestStart + fLargestLength
+           - (start + length);
+
+       if (firstLength >= secondLength) {
+           fLargestLength = firstLength;
+       } else {
+           fLargestLength = secondLength;
+           fLargestStart = start + length;
+       }
+   } else {
+       // No need to revalidate the largest free range
+       return B_OK;
+   }
+
+   if (fLargestLength < fNumBits / 2)
+       block.FindLargestUnmarkedRange(fLargestStart, fLargestLength);
+
+   return B_OK;
+}
+
+
+status_t
+AllocationBlockGroup::Free(Transaction& transaction, uint32 start,
+   uint32 length)
+{
+   uint32 end = start + length;
+
+   if (end > fLargestLength)
+       return B_BAD_DATA;
+
+   BitmapBlock block(fVolume, fNumBits);
+
+   if (!block.SetToWritable(transaction, fBitmapBlock))
+       return B_ERROR;
+
+   if (!block.Unmark(start, length)) {
+       TRACE("Failed to free blocks from %lu to %lu. Some were "
+           "already freed.\n", start, start + length);
+       return B_ERROR;
+   }
+
+   transaction.AddListener(this);
+
+   if (fFirstFree > start)
+       fFirstFree = start;
+
+   if (start + length == fLargestStart) {
+       fLargestStart = start;
+       fLargestLength += length;
+   } else if (start == fLargestStart + fLargestLength) {
+       fLargestLength += length;
+   } else if (fLargestLength >= fNumBits / 2) {
+       // May have merged with some free blocks, becoming the largest
+       uint32 newEnd = start + length;
+       block.FindNextMarked(newEnd);
+
+       uint32 newStart = start;
+       block.FindPreviousMarked(newStart);
+
+       if (newEnd - newStart > fLargestLength) {
+           fLargestLength = newEnd - newStart;
+           fLargestStart = newStart;
+       }
+   }
+
+   fFreeBits += length;
+
+   return B_OK;
+}
+
+
+status_t
+AllocationBlockGroup::FreeAll(Transaction& transaction)
+{
+   return Free(transaction, 0, fNumBits);
+}
+
+
+uint32
+AllocationBlockGroup::NumBits() const
+{
+   return fNumBits;
+}
+
+
+uint32
+AllocationBlockGroup::FreeBits() const
+{
+   return fFreeBits;
+}
+
+
+uint32
+AllocationBlockGroup::Start() const
+{
+   return fStart;
+}
+
+
+uint32
+AllocationBlockGroup::LargestStart() const
+{
+   return fLargestStart;
+}
+
+
+uint32
+AllocationBlockGroup::LargestLength() const
+{
+   return fLargestLength;
+}
+
+
+void
+AllocationBlockGroup::_AddFreeRange(uint32 start, uint32 length)
+{
+   if (IsFull()) {
+       fFirstFree = start;
+       fLargestStart = start;
+       fLargestLength = length;
+   } else if (length > fLargestLength) {
+       fLargestStart = start;
+       fLargestLength = length;
+   }
+
+   fFreeBits += length;
+}
+
+
+void
+AllocationBlockGroup::TransactionDone(bool success)
+{
+   if (success) {
+       TRACE("AllocationBlockGroup::TransactionDone(): The transaction "
+           "succeeded, discarding previous state\n");
+       fPreviousFreeBits = fFreeBits;
+       fPreviousFirstFree = fFirstFree;
+       fPreviousLargestStart = fLargestStart;
+       fPreviousLargestLength = fLargestLength;
+   } else {
+       TRACE("AllocationBlockGroup::TransactionDone(): The transaction "
+           "failed, restoring to previous state\n");
+       fFreeBits = fPreviousFreeBits;
+       fFirstFree = fPreviousFirstFree;
+       fLargestStart = fPreviousLargestStart;
+       fLargestLength = fPreviousLargestLength;
+   }
+}
+
+
+void
+AllocationBlockGroup::RemovedFromTransaction()
+{
+   // TODO: What to do here?
+}
+
+
+BlockAllocator::BlockAllocator(Volume* volume)
+   :
+   fVolume(volume),
+   fGroups(NULL),
+   fBlocksPerGroup(0),
+   fNumBlocks(0),
+   fNumGroups(0)
+{
+   mutex_init(&fLock, "ext2 block allocator");
+}
+
+
+BlockAllocator::~BlockAllocator()
+{
+   mutex_destroy(&fLock);
+
+   if (fGroups != NULL)
+       delete [] fGroups;
+}
+
+
+status_t
+BlockAllocator::Initialize()
+{
+   fBlocksPerGroup = fVolume->BlocksPerGroup();
+   fNumGroups = fVolume->NumGroups();
+   fFirstBlock = fVolume->FirstDataBlock();
+   fNumBlocks = fVolume->NumBlocks();
+
+   TRACE("BlockAllocator::Initialize(): blocks per group: %lu, block groups: "
+       "%lu, first block: %lu, num blocks: %lu\n", fBlocksPerGroup,
+       fNumGroups, fFirstBlock, fNumBlocks);
+
+   fGroups = new(std::nothrow) AllocationBlockGroup[fNumGroups];
+   if (fGroups == NULL)
+       return B_NO_MEMORY;
+
+   TRACE("BlockAllocator::Initialize(): allocated allocation block groups\n");
+
+   mutex_lock(&fLock);
+       // Released by _Initialize
+
+   thread_id id = -1; // spawn_kernel_thread(
+       // (thread_func)BlockAllocator::_Initialize, "ext2 block allocator",
+       // B_LOW_PRIORITY, this);
+   if (id < B_OK)
+       return _Initialize(this);
+
+   // mutex_transfer_lock(&fLock, id);
+
+   // return resume_thread(id);
+   panic("Failed to fall back to synchronous block allocator"
+       "initialization.\n");
+   return B_ERROR;
+}
+
+
+status_t
+BlockAllocator::AllocateBlocks(Transaction& transaction, uint32 minimum,
+   uint32 maximum, uint32& blockGroup, uint32& start, uint32& length)
+{
+   TRACE("BlockAllocator::AllocateBlocks()\n");
+   MutexLocker lock(fLock);
+   TRACE("BlockAllocator::AllocateBlocks(): Aquired lock\n");
+
+   TRACE("BlockAllocator::AllocateBlocks(): transaction: %ld, min: %lu, "
+       "max: %lu, block group: %lu, start: %lu, num groups: %lu\n",
+       transaction.ID(), minimum, maximum, blockGroup, start, fNumGroups);
+
+   uint32 bestStart = 0;
+   uint32 bestLength = 0;
+   uint32 bestGroup = 0;
+
+   uint32 groupNum = blockGroup;
+
+   AllocationBlockGroup* last = &fGroups[fNumGroups];
+   AllocationBlockGroup* group = &fGroups[blockGroup];
+
+   for (int32 iterations = 0; iterations < 2; iterations++) {
+       for (; group < last; ++group, ++groupNum) {
+           TRACE("BlockAllocator::AllocateBlocks(): Group %lu has largest "
+           "length of %lu\n", groupNum, group->LargestLength());
+
+           if (group->LargestLength() > bestLength) {
+               if (start <= group->LargestStart()) {
+                   bestStart = group->LargestStart();
+                   bestLength = group->LargestLength();
+                   bestGroup = groupNum;
+
+                   TRACE("BlockAllocator::AllocateBlocks(): Found a better "
+                       "range: block group: %lu, %lu-%lu\n", groupNum,
+                       bestStart, bestStart + bestLength);
+
+                   if (bestLength >= maximum)
+                       break;
+               }
+           }
+
+           start = 0;
+       }
+
+       if (bestLength >= maximum)
+           break;
+
+       groupNum = 0;
+
+       group = &fGroups[0];
+       last = &fGroups[blockGroup + 1];
+   }
+
+   if (bestLength < minimum) {
+       TRACE("BlockAllocator::AllocateBlocks(): best range (length %lu) "
+           "doesn't have minimum length of %lu\n", bestLength, minimum);
+       return B_DEVICE_FULL;
+   }
+
+   if (bestLength > maximum)
+       bestLength = maximum;
+
+   TRACE("BlockAllocator::AllocateBlocks(): Selected range: block group %lu, "
+       "%lu-%lu\n", bestGroup, bestStart, bestStart + bestLength);
+
+   status_t status = fGroups[bestGroup].Allocate(transaction, bestStart,
+       bestLength);
+   if (status != B_OK) {
+       TRACE("BlockAllocator::AllocateBlocks(): Failed to allocate %lu blocks "
+           "inside block group %lu.\n", bestLength, bestGroup);
+       return status;
+   }
+
+   start = bestStart;
+   length = bestLength;
+   blockGroup = bestGroup;
+
+   return B_OK;
+}
+
+
+status_t
+BlockAllocator::Allocate(Transaction& transaction, Inode* inode,
+   off_t numBlocks, uint32 minimum, uint32& start, uint32& allocated)
+{
+   if (numBlocks <= 0)
+       return B_ERROR;
+
+   uint32 group = inode->ID() / fVolume->InodesPerGroup();
+   uint32 preferred = 0;
+
+   if (inode->Size() > 0) {
+       // Try to allocate near it's last blocks
+       ext2_data_stream* dataStream = &inode->Node().stream;
+       uint32 numBlocks = inode->Size() / fVolume->BlockSize() + 1;
+       uint32 lastBlock = 0;
+
+       // DANGER! What happens with sparse files?
+       if (numBlocks < EXT2_DIRECT_BLOCKS) {
+           // Only direct blocks
+           lastBlock = dataStream->direct[numBlocks];
+       } else {
+           numBlocks -= EXT2_DIRECT_BLOCKS - 1;
+           uint32 numIndexes = fVolume->BlockSize() / 4;
+               // block size / sizeof(int32)
+           uint32 numIndexes2 = numIndexes * numIndexes;
+           uint32 numIndexes3 = numIndexes2 * numIndexes;
+           uint32 indexesInIndirect = numIndexes;
+           uint32 indexesInDoubleIndirect = indexesInIndirect
+               + numIndexes2;
+           // uint32 indexesInTripleIndirect = indexesInDoubleIndirect
+               // + numIndexes3;
+
+           uint32 doubleIndirectBlock = EXT2_DIRECT_BLOCKS + 1;
+           uint32 indirectBlock = EXT2_DIRECT_BLOCKS;
+
+           CachedBlock cached(fVolume);
+           uint32* indirectData;
+
+           if (numBlocks > indexesInDoubleIndirect) {
+               // Triple indirect blocks
+               indirectData = (uint32*)cached.SetTo(EXT2_DIRECT_BLOCKS + 2);
+               if (indirectData == NULL)
+                   return B_IO_ERROR;
+
+               uint32 index = (numBlocks - indexesInDoubleIndirect)
+                   / numIndexes3;
+               doubleIndirectBlock = indirectData[index];
+           }
+
+           if (numBlocks > indexesInIndirect) {
+               // Double indirect blocks
+               indirectData = (uint32*)cached.SetTo(doubleIndirectBlock);
+               if (indirectData == NULL)
+                   return B_IO_ERROR;
+
+               uint32 index = (numBlocks - indexesInIndirect) / numIndexes2;
+               indirectBlock = indirectData[index];
+           }
+
+           indirectData = (uint32*)cached.SetTo(indirectBlock);
+               if (indirectData == NULL)
+                   return B_IO_ERROR;
+
+           uint32 index = numBlocks / numIndexes;
+           lastBlock = indirectData[index];
+       }
+
+       group = (lastBlock - fFirstBlock) / fBlocksPerGroup;
+       preferred = (lastBlock - fFirstBlock) % fBlocksPerGroup + 1;
+   }
+
+   // TODO: Apply some more policies
+
+   return AllocateBlocks(transaction, minimum, minimum + 8, group, start,
+       allocated);
+}
+
+
+status_t
+BlockAllocator::Free(Transaction& transaction, uint32 start, uint32 length)
+{
+   MutexLocker lock(fLock);
+
+   if (start == 0) {
+       panic("Trying to free superblock!\n");
+       return B_BAD_DATA;
+   }
+
+   if (length == 0)
+       return B_OK;
+
+   uint32 group = (start - fFirstBlock) / fBlocksPerGroup;
+   start = (start - fFirstBlock) % fBlocksPerGroup;
+   uint32 lastGroup = (start + length - fFirstBlock) / fBlocksPerGroup;
+
+   if (group == lastGroup)
+       return fGroups[group].Free(transaction, start, length);
+
+   status_t status = fGroups[group].Free(transaction, start,
+       fGroups[group].NumBits());
+   if (status != B_OK)
+       return status;
+
+   for (++group; group < lastGroup; ++group) {
+       status = fGroups[group].FreeAll(transaction);
+       if (status != B_OK)
+           return status;
+   }
+
+   return fGroups[group].Free(transaction, 0, (start + length - fFirstBlock)
+       % fBlocksPerGroup);
+}
+
+
+/*static*/ status_t
+BlockAllocator::_Initialize(BlockAllocator* allocator)
+{
+   TRACE("BlockAllocator::_Initialize()\n");
+   // fLock is already heald
+   Volume* volume = allocator->fVolume;
+
+   AllocationBlockGroup* groups = allocator->fGroups;
+   uint32 numGroups = allocator->fNumGroups - 1;
+
+   uint32 freeBlocks = 0;
+   TRACE("BlockAllocator::_Initialize(): free blocks: %lu\n", freeBlocks);
+
+   for (uint32 i = 0; i < numGroups; ++i) {
+       status_t status = groups[i].Initialize(volume, i,
+           allocator->fBlocksPerGroup);
+       if (status != B_OK) {
+           mutex_unlock(&allocator->fLock);
+           return status;
+       }
+
+       freeBlocks += groups[i].FreeBits();
+       TRACE("BlockAllocator::_Initialize(): free blocks: %lu\n", freeBlocks);
+   }
+
+   // Last block group may have less blocks
+   status_t status = groups[numGroups].Initialize(volume, numGroups,
+       allocator->fNumBlocks - allocator->fBlocksPerGroup * numGroups
+       - allocator->fFirstBlock);
+   if (status != B_OK) {
+       mutex_unlock(&allocator->fLock);
+       return status;
+   }
+
+   freeBlocks += groups[numGroups].FreeBits();
+
+   TRACE("BlockAllocator::_Initialize(): free blocks: %lu\n", freeBlocks);
+
+   mutex_unlock(&allocator->fLock);
+
+   if (freeBlocks != volume->NumFreeBlocks()) {
+       TRACE("Counted free blocks doesn't match value in the superblock.\n");
+       return B_BAD_DATA;
+   }
+
+   return B_OK;
+}

Property changes on: src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/Inode.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Inode.cpp  (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/Inode.cpp  (working copy)
@@ -8,8 +8,11 @@

 #include <fs_cache.h>
 #include <string.h>
+#include <util/AutoLock.h>

 #include "CachedBlock.h"
+#include "DirectoryIterator.h"
+#include "HTree.h"


 //#define TRACE_EXT2
@@ -26,56 +29,131 @@
    fID(id),
    fCache(NULL),
    fMap(NULL),
-   fNode(NULL),
    fAttributesBlock(NULL)
 {
    rw_lock_init(&fLock, "ext2 inode");

-   uint32 block;
-   if (volume->GetInodeBlock(id, block) == B_OK) {
-       TRACE("inode %Ld at block %lu\n", ID(), block);
-       uint8* inodeBlock = (uint8*)block_cache_get(volume->BlockCache(),
-           block);
-       if (inodeBlock != NULL) {
-           fNode = (ext2_inode*)(inodeBlock + volume->InodeBlockIndex(id)
-               * volume->InodeSize());
+   fInitStatus = UpdateNodeFromDisk();
+   if (fInitStatus == B_OK) {
+       if (Size() == 0 || IsDirectory() || (IsSymLink() && Size() < 60)) {
+           fCached = false;
+       } else {
+           fCache = file_cache_create(fVolume->ID(), ID(), Size());
+           fMap = file_map_create(fVolume->ID(), ID(), Size());
+
+           if (fCache != NULL)
+               fCached = true;
+           else {
+               fCached = false;
+               fInitStatus = B_ERROR;
+           }
        }
+   } else {
+       TRACE("Inode: Failed initialization\n");
+       fCached = false;
    }
-
-   if (fNode != NULL) {
-       // TODO: we don't need a cache for short symlinks
-       fCache = file_cache_create(fVolume->ID(), ID(), Size());
-       fMap = file_map_create(fVolume->ID(), ID(), Size());
-   }
 }


 Inode::~Inode()
 {
-   file_cache_delete(FileCache());
-   file_map_delete(Map());
+   TRACE("Inode destructor\n");

+   if (fCached) {
+       TRACE("Deleting the file cache and file map\n");
+       file_cache_delete(FileCache());
+       file_map_delete(Map());
+   }
+
    if (fAttributesBlock) {
+       TRACE("Returning the attributes block\n");
        uint32 block = B_LENDIAN_TO_HOST_INT32(Node().file_access_control);
        block_cache_put(fVolume->BlockCache(), block);
    }

-   if (fNode != NULL) {
-       uint32 block;
-       if (fVolume->GetInodeBlock(ID(), block) == B_OK)
-           block_cache_put(fVolume->BlockCache(), block);
-   }
+   TRACE("Inode destructor: Done\n");
 }


 status_t
 Inode::InitCheck()
 {
-   return fNode != NULL ? B_OK : B_ERROR;
+   return fInitStatus;
 }


+void
+Inode::WriteLockInTransaction(Transaction& transaction)
+{
+   acquire_vnode(fVolume->FSVolume(), ID());
+
+   rw_lock_write_lock(&fLock);
+
+   transaction.AddListener(this);
+}
+
+
 status_t
+Inode::WriteBack(Transaction& transaction)
+{
+   WriteLocker lock(fLock);
+
+   uint32 inodeBlock;
+
+   status_t status = fVolume->GetInodeBlock(fID, inodeBlock);
+   if (status != B_OK)
+       return status;
+
+   CachedBlock cached(fVolume);
+   uint8* inodeBlockData = cached.SetToWritable(transaction, inodeBlock);
+   if (inodeBlockData == NULL)
+       return B_IO_ERROR;
+
+   memcpy(inodeBlockData +
+           fVolume->InodeBlockIndex(fID) * fVolume->InodeSize(),
+       (uint8*)&fNode, fNodeSize);
+
+   TRACE("Inode::WriteBack() finished\n");
+
+   return B_OK;
+}
+
+
+status_t
+Inode::UpdateNodeFromDisk()
+{
+   uint32 block;
+
+   status_t status = fVolume->GetInodeBlock(fID, block);
+   if (status != B_OK)
+       return status;
+
+   TRACE("inode %Ld at block %lu\n", fID, block);
+
+   CachedBlock cached(fVolume);
+   const uint8* inodeBlock = cached.SetTo(block);
+
+   if (inodeBlock == NULL)
+       return B_IO_ERROR;
+
+   TRACE("Inode size: %lu, inode index: %lu\n", fVolume->InodeSize(),
+       fVolume->InodeBlockIndex(fID));
+   ext2_inode* inode = (ext2_inode*)(inodeBlock
+       + fVolume->InodeBlockIndex(fID) * fVolume->InodeSize());
+
+   fNodeSize = sizeof(ext2_inode) > fVolume->InodeSize()
+       ? fVolume->InodeSize() : sizeof(ext2_inode);
+
+   TRACE("Attempting to copy inode data from %p to %p, ext2_inode "
+       "size: %lu\n", inode, &fNode, fNodeSize);
+
+   memcpy(&fNode, inode, fNodeSize);
+
+   return B_OK;
+}
+
+
+status_t
 Inode::CheckPermissions(int accessMode) const
 {
    uid_t user = geteuid();
@@ -95,9 +173,9 @@

    // shift mode bits, to check directly against accessMode
    mode_t mode = Mode();
-   if (user == (uid_t)fNode->UserID())
+   if (user == (uid_t)fNode.UserID())
        mode >>= 6;
-   else if (group == (gid_t)fNode->GroupID())
+   else if (group == (gid_t)fNode.GroupID())
        mode >>= 3;

    if (accessMode & ~(mode & S_IRWXO))
@@ -114,8 +192,10 @@
    uint32 perIndirectBlock = perBlock * perBlock;
    uint32 index = offset >> fVolume->BlockShift();

-   if (offset >= Size())
+   if (offset >= Size()) {
+       TRACE("FindBlock: offset larger than inode size\n");
        return B_ENTRY_NOT_FOUND;
+   }

    // TODO: we could return the size of the sparse range, as this might be more
    // than just a block
@@ -186,7 +266,7 @@
            }
        }
    } else {
-       // outside of the possible data stream
+       // Outside of the possible data stream
        dprintf("ext2: block outside datastream!\n");
        return B_ERROR;
    }
@@ -203,7 +283,8 @@

    // set/check boundaries for pos/length
    if (pos < 0) {
-       TRACE("inode %Ld: ReadAt failed(pos %Ld, length %lu)\n", ID(), pos, length);
+       TRACE("inode %Ld: ReadAt failed(pos %Ld, length %lu)\n", ID(), pos,
+           length);
        return B_BAD_VALUE;
    }

@@ -218,6 +299,116 @@


 status_t
+Inode::WriteAt(Transaction& transaction, off_t pos, uint8* buffer,
+   size_t* _length)
+{
+   ReadLocker readLocker(fLock);
+
+   if (pos < 0)
+       return B_BAD_DATA;
+
+   readLocker.Unlock();
+
+   WriteLocker writeLocker(fLock);
+
+   size_t length = *_length;
+   off_t end = pos + length;
+   off_t oldSize = Size();
+
+   if (end > oldSize) {
+       status_t status = Resize(transaction, end);
+       if (status != B_OK) {
+           *_length = 0;
+           WriteLockInTransaction(transaction);
+           return status;
+       }
+
+       status = WriteBack(transaction);
+       if (status != B_OK) {
+           *_length = 0;
+           WriteLockInTransaction(transaction);
+           return status;
+       }
+   }
+
+   writeLocker.Unlock();
+
+   if (oldSize < pos)
+       FillGapWithZeros(oldSize, pos);
+
+   if (length == 0) {
+       // Probably just changed the file size with the pos parameter
+       return B_OK;
+   }
+
+   status_t status = file_cache_write(FileCache(), NULL, pos, buffer, _length);
+
+   WriteLockInTransaction(transaction);
+
+   return status;
+}
+
+
+status_t
+Inode::FillGapWithZeros(off_t start, off_t end)
+{
+   while (start < end) {
+       size_t size;
+
+       if (end > start + 1024 * 1024 * 1024)
+           size = 1024 * 1024 * 1024;
+       else
+           size = end - start;
+
+       status_t status = file_cache_write(FileCache(), NULL, start, NULL,
+           &size);
+       if (status != B_OK)
+           return status;
+
+       start += size;
+   }
+
+   return B_OK;
+}
+
+
+status_t
+Inode::Resize(Transaction& transaction, off_t size)
+{
+   TRACE("Inode::Resize() size: %ld\n", (long)size);
+   if (size < 0)
+       return B_BAD_VALUE;
+
+   off_t oldSize = Size();
+
+   if (size == oldSize)
+       return B_OK;
+
+   status_t status;
+   if (size > oldSize) {
+       status = _EnlargeDataStream(transaction, size);
+       if (status != B_OK) {
+           // Restore original size
+           _ShrinkDataStream(transaction, oldSize);
+       }
+   } else
+       status = _ShrinkDataStream(transaction, size);
+
+   TRACE("Inode::Resize(): Updating file map and cache\n");
+
+   if (status != B_OK)
+       return status;
+
+   file_cache_set_size(FileCache(), size);
+   file_map_set_size(Map(), size);
+
+   TRACE("Inode::Resize(): Writing back inode changes. Size: %ld\n", Size());
+
+   return WriteBack(transaction);
+}
+
+
+status_t
 Inode::AttributeBlockReadAt(off_t pos, uint8* buffer, size_t* _length)
 {
    TRACE("Inode::%s(%Ld, , %lu)\n", __FUNCTION__, pos, *_length);
@@ -245,3 +436,702 @@
    *_length = length;
    return B_NO_ERROR;
 }
+
+
+/*static*/ status_t
+Inode::Create(Transaction& transaction, Inode* parent, const char* name,
+   int32 mode, int openMode, uint32 type, bool* _created, ino_t* id,
+   Inode** _inode, fs_vnode_ops* vnodeOps, uint32 publishFlags)
+{
+   if (parent == NULL)
+       return B_BAD_DATA;
+
+   status_t status = parent->CheckPermissions(W_OK);
+   if (status != B_OK)
+       return status;
+
+   DirectoryIterator* entries = NULL;
+   Volume* volume = parent->GetVolume();
+
+   HTree htree(volume, parent);
+   status = htree.Lookup(name, &entries);
+   if (status != B_OK)
+       return status;
+
+   ObjectDeleter<DirectoryIterator> entriesDeleter;
+   entriesDeleter.SetTo(entries);
+
+   status = volume->AllocateInode(transaction, parent, mode, *id);
+   if (status != B_OK)
+       return status;
+
+   size_t nameLength = strlen(name);
+   status = entries->AddEntry(transaction, name, nameLength, *id);
+   if (status != B_OK)
+       return status;
+
+   Inode* inode = new(std::nothrow) Inode(volume, *id);
+   if (inode == NULL)
+       return B_NO_MEMORY;
+
+   ext2_inode& node = inode->Node();
+   node.SetMode(mode);
+   node.SetUserID(geteuid());
+   node.SetGroupID(parent->Node().GroupID());
+   node.SetSize(0);
+   node.SetNumLinks(1);
+   node.SetNumBlocks(volume->BlockSize() / 512);
+
+   time_t creationTime = real_time_clock();
+   node.SetCreationTime(creationTime);
+   node.SetModificationTime(creationTime);
+   node.SetFlags(0);
+
+   inode->WriteBack(transaction);
+
+   return B_OK;
+}
+
+
+status_t
+Inode::DisableFileCache()
+{
+   TRACE("Inode::DisableFileCache()\n");
+
+   if (!fCached)
+       return B_OK;
+
+   file_cache_delete(FileCache());
+   file_map_delete(Map());
+
+   fCached = false;
+
+   return B_OK;
+}
+
+
+void
+Inode::TransactionDone(bool success)
+{
+   if (!success) {
+       // Revert any changes to the inode
+       if (UpdateNodeFromDisk() != B_OK)
+           panic("Failed to reload inode from disk!\n");
+   }
+}
+
+
+void
+Inode::RemovedFromTransaction()
+{
+   rw_lock_write_unlock(&fLock);
+
+   put_vnode(fVolume->FSVolume(), ID());
+}
+
+
+status_t
+Inode::_EnlargeDataStream(Transaction& transaction, off_t size)
+{
+   // TODO: Update fNode.num_blocks
+   if (size < 0)
+       return B_BAD_DATA;
+
+   TRACE("Inode::_EnlargeDataStream()\n");
+
+   uint32 blockSize = fVolume->BlockSize();
+   off_t oldSize = Size();
+   off_t maxSize = oldSize;
+   if (maxSize % blockSize != 0)
+       maxSize += blockSize - maxSize % blockSize;
+
+   if (size <= maxSize) {
+       // No need to allocate more blocks
+       TRACE("Inode::_EnlargeDataStream(): No need to allocate more blocks\n");
+       TRACE("Inode::_EnlargeDataStream(): Setting size to %ld\n", (long)size);
+       fNode.SetSize(size);
+       TRACE("Inode::_EnlargeDataStream(): Size: %ld\n", (long)Size());
+       return B_OK;
+   }
+
+   off_t bytesNeeded = size - maxSize;
+   uint32 blocksNeeded = (bytesNeeded - 1) / blockSize + 1;
+
+   if (blocksNeeded > fVolume->NumFreeBlocks()) {
+       TRACE("Inode::_EnlargeDataStream(): Insufficient free blocks. Needed: "
+           "%lu, available: %lu\n", blocksNeeded,
+           (uint32)fVolume->NumFreeBlocks());
+       return B_DEVICE_FULL;
+   }
+
+   // Discover the last mapped block
+   uint32 pos = 0;
+   off_t lastByte = oldSize == 0 ? 0 : oldSize - 1;
+   if (oldSize != 0) {
+       status_t status = FindBlock(lastByte, pos);
+       if (status != B_OK)
+           return status;
+   }
+
+   uint32 blockGroup = pos / fVolume->BlocksPerGroup();
+   pos %= fVolume->BlocksPerGroup();
+
+   // Allocate the required blocks (currently no preallocation)
+   //  if we fail, it is assumed the transaction fails, and everything is
+   //  reverted
+   while (blocksNeeded > 0) {
+       uint32 length;
+       status_t status = fVolume->AllocateBlocks(transaction, 1, blocksNeeded,
+           blockGroup, pos, length);
+       if (status != B_OK)
+           return status;
+
+       blocksNeeded -= length;
+
+       uint32 numBlocks = lastByte / fVolume->BlockSize() + 1;
+       status = _MapBlocksInDataStream(transaction, numBlocks, pos,
+           length, blockGroup);
+       if (status != B_OK)
+           return status;
+   }
+
+   TRACE("Inode::_EnlargeDataStream(): Setting size to %ld\n", (long)size);
+   fNode.SetSize(size);
+
+   return B_OK;
+}
+
+
+status_t
+Inode::_ShrinkDataStream(Transaction& transaction, off_t size)
+{
+   TRACE("Inode::_ShrinkDataStream()\n");
+
+   if (size < 0)
+       return B_BAD_DATA;
+
+   uint32 blockSize = fVolume->BlockSize();
+   off_t oldSize = Size();
+   off_t lastByte = oldSize == 0 ? 0 : oldSize - 1;
+   off_t minSize = (lastByte / blockSize + 1) * blockSize;
+       // Minimum size that doesn't require freeing blocks
+
+   if (size > minSize) {
+       // No need to allocate more blocks
+       fNode.SetSize(size);
+       return B_OK;
+   }
+
+   // Discover the last mapped block
+   uint32 lastBlock;
+   if (oldSize != 0) {
+       status_t status = FindBlock(lastByte, lastBlock);
+       if (status != B_OK)
+           return status;
+   }
+
+   uint32 freeStart = minSize + 1;
+
+   uint32 indirectsPerBlock = fVolume->BlockSize() / 4; // 32 bits
+   uint32 indirectsPerBlock2 = indirectsPerBlock * indirectsPerBlock;
+
+   uint32 maxDirect = EXT2_DIRECT_BLOCKS;
+   uint32 maxIndirect = maxDirect + indirectsPerBlock;
+   uint32 maxDoubleIndirect = maxDirect + indirectsPerBlock + indirectsPerBlock2;
+
+   ext2_data_stream* dataStream = &fNode.stream;
+
+   status_t status;
+
+   if (freeStart < maxDirect) {
+       uint32 directEnd = lastBlock < maxDirect ? lastBlock + 1 : maxDirect;
+
+       status = _FreeDirectBlocks(transaction, (uint32*)&dataStream[freeStart],
+           (uint32*)&dataStream[directEnd]);
+       if (status != B_OK)
+           return status;
+
+       if (directEnd != maxDirect) {
+           fNode.SetSize(size);
+           return B_OK;
+       }
+   }
+
+   CachedBlock cached(fVolume);
+
+   if (freeStart < maxIndirect && dataStream->Indirect() != 0) {
+       uint32* indirectBlock = (uint32*)cached.SetToWritable(transaction,
+           dataStream->Indirect());
+
+       if (freeStart >= maxDirect)
+           indirectBlock += freeStart - maxDirect;
+
+       uint32* indirectBlockEnd = lastBlock < maxIndirect
+           ? &indirectBlock[lastBlock + 1] : &indirectBlock[maxIndirect];
+
+       status = _FreeIndirectBlock(transaction, indirectBlock,
+           indirectBlockEnd);
+       if (status != B_OK)
+           return status;
+
+       if (freeStart < maxDirect) {
+           status = fVolume->FreeBlocks(transaction, dataStream->Indirect(), 1);
+           if (status != B_OK)
+               return status;
+
+           dataStream->SetIndirect(0);
+       }
+   }
+
+   if (lastBlock < maxIndirect) {
+       fNode.SetSize(size);
+       return B_OK;
+   }
+
+   if (freeStart < maxDoubleIndirect && dataStream->DoubleIndirect() != 0) {
+       uint32* doubleIndirectBlock = (uint32*)cached.SetToWritable(
+           transaction, dataStream->DoubleIndirect());
+
+       if (freeStart >= maxIndirect)
+           doubleIndirectBlock += freeStart - maxIndirect;
+
+       uint32* doubleIndirectBlockEnd = lastBlock < maxDoubleIndirect
+           ? &doubleIndirectBlock[lastBlock + 1]
+           : &doubleIndirectBlock[maxDoubleIndirect];
+
+       status = _FreeDoubleIndirectBlock(transaction, doubleIndirectBlock,
+           doubleIndirectBlockEnd);
+       if (status != B_OK)
+           return status;
+
+       if (freeStart < maxIndirect) {
+           status = fVolume->FreeBlocks(transaction,
+               dataStream->DoubleIndirect(), 1);
+           if (status != B_OK)
+               return status;
+
+           dataStream->SetDoubleIndirect(0);
+       }
+   }
+
+   if (lastBlock < maxDoubleIndirect) {
+       fNode.SetSize(size);
+       return B_OK;
+   }
+
+   if (dataStream->TripleIndirect() != 0) {
+       uint32* tripleIndirectBlock = (uint32*)cached.SetToWritable(
+           transaction, dataStream->TripleIndirect());
+
+       if (freeStart >= maxDoubleIndirect)
+           tripleIndirectBlock += freeStart - maxDoubleIndirect;
+
+       uint32* tripleIndirectBlockEnd = &tripleIndirectBlock[lastBlock + 1];
+
+       status = _FreeTripleIndirectBlock(transaction, tripleIndirectBlock,
+           tripleIndirectBlockEnd);
+       if (status != B_OK)
+           return status;
+
+       if (freeStart < maxDoubleIndirect) {
+           status = fVolume->FreeBlocks(transaction,
+               dataStream->TripleIndirect(), 1);
+           if (status != B_OK)
+               return status;
+
+           dataStream->SetTripleIndirect(0);
+       }
+   }
+
+   fNode.SetSize(size);
+   return B_OK;
+}
+
+
+status_t
+Inode::_FreeDirectBlocks(Transaction& transaction, uint32* block,
+   uint32* maxPos)
+{
+   uint32 start, value, expected;
+
+   value = B_LENDIAN_TO_HOST_INT32(*block);
+   ++block;
+
+   status_t status = B_OK;
+   while (status == B_OK && block < maxPos) {
+       start = value;
+       expected = value;
+
+       while (block < maxPos && expected == value) {
+           value = B_LENDIAN_TO_HOST_INT32(*block);
+           *block = 0;
+
+           expected++;
+           block++;
+       }
+
+       status = fVolume->FreeBlocks(transaction, start, expected - start);
+   }
+
+   return status;
+}
+
+
+status_t
+Inode::_FreeIndirectBlock(Transaction& transaction, uint32* indirectBlock,
+   uint32* maxIndirectPos)
+{
+   // TODO: Ideally, we should group all blocks to be freed to minimize the
+   // number of calls to the block allocator
+
+   CachedBlock cached(fVolume);
+   uint32 *indirectPos = indirectBlock;
+   uint32 *directBlock;
+   uint32 *directMaxPos;
+
+   status_t status = B_OK;
+   while (status == B_OK && indirectPos < maxIndirectPos) {
+       uint32 block = B_LENDIAN_TO_HOST_INT32(*indirectPos);
+       *indirectPos = 0;
+
+       directBlock = (uint32*)cached.SetToWritable(transaction, block);
+       if (directBlock == NULL)
+           return B_IO_ERROR;
+
+       directMaxPos = (uint32*)((uint8*)directBlock + fVolume->BlockSize());
+
+       status = _FreeDirectBlocks(transaction, directBlock, directMaxPos);
+   }
+
+   if (status == B_OK)
+       status = _FreeDirectBlocks(transaction, indirectBlock, maxIndirectPos);
+
+   return status;
+}
+
+
+status_t
+Inode::_FreeDoubleIndirectBlock(Transaction& transaction,
+   uint32* doubleIndirectBlock, uint32* maxDoubleIndirectPos)
+{
+   // TODO: Ideally, we should group all blocks to be freed to minimize the
+   // number of calls to the block allocator
+
+   CachedBlock cached(fVolume);
+   uint32 *doubleIndirectPos = doubleIndirectBlock;
+   uint32 *indirectBlock;
+   uint32 *maxIndirectPos;
+
+   status_t status = B_OK;
+   while (status == B_OK && doubleIndirectPos < maxDoubleIndirectPos) {
+       uint32 block = B_LENDIAN_TO_HOST_INT32(*doubleIndirectPos);
+       *doubleIndirectPos = 0;
+
+       indirectBlock = (uint32*)cached.SetToWritable(transaction, block);
+       if (indirectBlock == NULL)
+           return B_IO_ERROR;
+
+       maxIndirectPos = (uint32*)((uint8*)indirectBlock + fVolume->BlockSize());
+
+       status = _FreeIndirectBlock(transaction, indirectBlock, maxIndirectPos);
+   }
+
+   if (status == B_OK) {
+       status = _FreeDirectBlocks(transaction, doubleIndirectBlock,
+           maxDoubleIndirectPos);
+   }
+
+   return status;
+}
+
+
+status_t
+Inode::_FreeTripleIndirectBlock(Transaction& transaction,
+   uint32* tripleIndirectBlock, uint32* maxTripleIndirectPos)
+{
+   // TODO: Ideally, we should group all blocks to be freed to minimize the
+   // number of calls to the block allocator
+
+   CachedBlock cached(fVolume);
+   uint32 *tripleIndirectPos = tripleIndirectBlock;
+   uint32 *doubleIndirectBlock;
+   uint32 *maxDoubleIndirectPos;
+
+   status_t status = B_OK;
+   while (status == B_OK && tripleIndirectPos < maxTripleIndirectPos) {
+       uint32 block = B_LENDIAN_TO_HOST_INT32(*tripleIndirectPos);
+       *tripleIndirectPos = 0;
+
+       doubleIndirectBlock = (uint32*)cached.SetToWritable(transaction, block);
+       if (doubleIndirectBlock == NULL)
+           return B_IO_ERROR;
+
+       maxDoubleIndirectPos = (uint32*)((uint8*)doubleIndirectBlock
+           + fVolume->BlockSize());
+
+       status = _FreeDoubleIndirectBlock(transaction, doubleIndirectBlock,
+           maxDoubleIndirectPos);
+   }
+
+   if (status == B_OK) {
+       status = _FreeDirectBlocks(transaction, tripleIndirectBlock,
+           maxTripleIndirectPos);
+   }
+
+   return status;
+}
+
+
+status_t
+Inode::_GetBlockFromAllocation(Transaction& transaction, uint32& blocksNeeded,
+   uint32& allocated, uint32& allocatedPos, uint32& block)
+{
+   TRACE("Inode::_GetBlockFromAllocation()\n");
+
+   if (allocated > 0) {
+       if (blocksNeeded == 0)
+           TRACE("Failed to allocate enough blocks\n");
+
+       allocated--;
+       block = allocatedPos++;
+
+       return B_OK;
+   }
+
+   uint32 blockGroup = allocatedPos / fVolume->BlocksPerGroup();
+   allocatedPos %= fVolume->BlocksPerGroup();
+
+   status_t status = fVolume->AllocateBlocks(transaction, 1, blocksNeeded,
+       blockGroup, allocatedPos, allocated);
+
+   allocatedPos += fVolume->BlockSize() * blockGroup;
+
+   return status;
+}
+
+
+void
+Inode::_MapBlocksInIndirectBlock(uint32* block, uint32* maxPos,
+   uint32 increment, uint32& length, uint32& rangePos)
+{
+   uint32 rangeStart = rangePos;
+
+   while (length > 0 && block < maxPos) {
+       *block = B_HOST_TO_LENDIAN_INT32(rangePos);
+
+       rangePos += increment;
+       ++block;
+       --length;
+   }
+
+   TRACE("Inode::_MapBlocksInIndirectBlock(): Mapped %lu-%lu\n", rangeStart,
+       rangePos);
+}
+
+
+status_t
+Inode::_MapBlocksInDoubleIndirectBlock(Transaction& transaction,
+   uint32* doubleIndirectBlock, uint32* maxDoubleIndirectPos,
+   uint32* indirectBlock, uint32* maxIndirectPos, uint32 increment,
+   uint32& blocksNeeded, uint32& allocated, uint32& allocatedPos,
+   uint32& length, uint32& rangePos)
+{
+   _MapBlocksInIndirectBlock(indirectBlock, maxIndirectPos, increment, length,
+       rangePos);
+   ++doubleIndirectBlock;
+
+   CachedBlock cached(fVolume);
+
+   while (length > 0 && doubleIndirectBlock < maxDoubleIndirectPos) {
+       uint32 block = B_LENDIAN_TO_HOST_INT32(*doubleIndirectBlock);
+
+       if (block == 0) {
+           status_t status = _GetBlockFromAllocation(transaction, blocksNeeded,
+               allocated, allocatedPos, block);
+           if (status != B_OK)
+               return status;
+
+           *doubleIndirectBlock = B_HOST_TO_LENDIAN_INT32(block);
+       }
+
+       indirectBlock = (uint32*)cached.SetToWritable(transaction, block);
+       if (indirectBlock == NULL)
+           return B_IO_ERROR;
+
+       maxIndirectPos = (uint32*)((uint8*)indirectBlock
+           + fVolume->BlockSize());
+
+       _MapBlocksInIndirectBlock(indirectBlock, maxIndirectPos, increment,
+           length, rangePos);
+       ++doubleIndirectBlock;
+   }
+
+   return B_OK;
+}
+
+
+status_t
+Inode::_MapBlocksInDataStream(Transaction& transaction, uint32 mapPos,
+   uint32 rangePos, uint32 length, uint32 preferredBlockGroup)
+{
+   TRACE("Inode::_MapBlocksInDataStream(): map pos: %lu, range pos: %lu, "
+       "length: %lu, preferred block group: %lu\n", mapPos, rangePos, length,
+       preferredBlockGroup);
+   if (length == 0)
+       return B_OK;
+
+   uint32 increment = rangePos == 0 ? 0 : 1;
+   uint32 indirectsPerBlock = fVolume->BlockSize() / 4; // 32 bits
+   uint32 indirectsPerBlock2 = indirectsPerBlock * indirectsPerBlock;
+
+   uint32 maxDirect = EXT2_DIRECT_BLOCKS - 1;
+   uint32 maxIndirect = maxDirect + indirectsPerBlock;
+   uint32 maxDoubleIndirect = maxDirect + indirectsPerBlock + indirectsPerBlock2;
+
+   ext2_data_stream* dataStream = &fNode.stream;
+   _MapBlocksInIndirectBlock(&dataStream->direct[mapPos],
+       &dataStream->direct[maxDirect], increment, length, rangePos);
+
+   if (length == 0)
+       return B_OK;
+
+   // Count the number of blocks that need to be allocated
+   uint32 blocksNeeded = 0;
+   uint32 end = mapPos + length;
+
+   off_t size = Size();
+   uint32 numBlocks = size == 0 ? 0 : (size - 1) / fVolume->BlockSize() + 1;
+
+   if (end > numBlocks) {
+       if (dataStream->Indirect() == 0)
+           blocksNeeded++;
+       if (end > maxIndirect) {
+           if (dataStream->DoubleIndirect() == 0)
+               blocksNeeded += 1 + (end - maxIndirect) / indirectsPerBlock;
+           else
+               blocksNeeded += (end - numBlocks) / indirectsPerBlock;
+       }
+       if (end > maxDoubleIndirect) {
+           if (dataStream->TripleIndirect() == 0)
+               blocksNeeded += 1 + (end - maxDoubleIndirect) / indirectsPerBlock2;
+           else
+               blocksNeeded += (end - numBlocks) / indirectsPerBlock2;
+       }
+   }
+
+   // Prepare for block allocation
+   if (fVolume->NumFreeBlocks() < blocksNeeded) {
+       TRACE("Not enough blocks to enlarge data stream\n");
+       return B_DEVICE_FULL;
+   }
+
+   uint32 allocated = 0;
+   uint32 allocatedPos = preferredBlockGroup * fVolume->BlockSize();
+
+   // Prepare blocks
+   uint32* indirectBlock = NULL;
+   uint32* doubleIndirectBlock = NULL;
+   uint32* tripleIndirectBlock = NULL;
+
+   uint32* maxIndirectPos = NULL;
+   uint32* maxDoubleIndirectPos = NULL;
+   uint32* maxTripleIndirectPos = NULL;
+
+   CachedBlock cachedIndirect(fVolume);
+   CachedBlock cachedDoubleIndirect(fVolume);
+   CachedBlock cachedTripleIndirect(fVolume);
+
+   uint32 block = dataStream->Indirect();
+   if (block == 0) {
+       status_t status = _GetBlockFromAllocation(transaction, blocksNeeded,
+           allocated, allocatedPos, block);
+       if (status != B_OK)
+           return status;
+
+       dataStream->SetIndirect(block);
+   }
+   indirectBlock = (uint32*)cachedIndirect.SetToWritable(transaction, block);
+   maxIndirectPos = (uint32*)((uint8*)indirectBlock + fVolume->BlockSize());
+
+   if (end > maxIndirect) {
+       // Reaches double indirect blocks
+       block = dataStream->DoubleIndirect();
+       if (block == 0) {
+           status_t status = _GetBlockFromAllocation(transaction,
+               blocksNeeded, allocated, allocatedPos, block);
+           if (status != B_OK)
+               return status;
+
+           dataStream->SetDoubleIndirect(block);
+       }
+
+       doubleIndirectBlock = (uint32*)cachedDoubleIndirect.SetToWritable(
+           transaction, block);
+       maxDoubleIndirectPos = (uint32*)((uint8*)doubleIndirectBlock
+           + fVolume->BlockSize());
+
+       if (end > maxDoubleIndirect) {
+           // Reaches triple indirect blocks
+           block = dataStream->TripleIndirect();
+           if (block == 0) {
+               status_t status = _GetBlockFromAllocation(transaction,
+                   blocksNeeded, allocated, allocatedPos, block);
+               if (status != B_OK)
+                   return status;
+
+               dataStream->SetTripleIndirect(block);
+           }
+
+           tripleIndirectBlock = (uint32*)cachedTripleIndirect.SetToWritable(
+               transaction, block);
+           maxTripleIndirectPos = (uint32*)((uint8*)tripleIndirectBlock
+               + fVolume->BlockSize());
+       }
+   }
+
+   indirectBlock += mapPos - maxDirect;
+   doubleIndirectBlock += (mapPos - maxIndirect) / indirectsPerBlock;
+   tripleIndirectBlock += (mapPos - maxDoubleIndirect) / indirectsPerBlock2;
+
+   // Perform the mapping
+   status_t status = _MapBlocksInDoubleIndirectBlock(transaction,
+       doubleIndirectBlock, maxDoubleIndirectPos, indirectBlock,
+       maxIndirectPos, increment, blocksNeeded, allocated, allocatedPos,
+       length, rangePos);
+   if (status != B_OK)
+       return status;
+
+   ++tripleIndirectBlock;
+
+   while (length > 0 && tripleIndirectBlock < maxTripleIndirectPos) {
+       uint32 block = B_LENDIAN_TO_HOST_INT32(*tripleIndirectBlock);
+
+       if (block == 0) {
+           status = _GetBlockFromAllocation(transaction, blocksNeeded,
+               allocated, allocatedPos, block);
+           if (status != B_OK)
+               return status;
+
+           *tripleIndirectBlock = B_HOST_TO_LENDIAN_INT32(block);
+       }
+
+       doubleIndirectBlock = (uint32*)cachedDoubleIndirect.SetToWritable(
+           transaction, block);
+       if (doubleIndirectBlock == NULL)
+           return B_IO_ERROR;
+
+       maxDoubleIndirectPos = (uint32*)((uint8*)doubleIndirectBlock
+           + fVolume->BlockSize());
+
+       status_t status = _MapBlocksInDoubleIndirectBlock(transaction,
+           doubleIndirectBlock, maxDoubleIndirectPos, indirectBlock,
+           maxIndirectPos, increment, blocksNeeded, allocated, allocatedPos,
+           length, rangePos);
+       if (status != B_OK)
+           return status;
+
+       ++tripleIndirectBlock;
+   }
+
+   return B_OK;
+}
Index: src/add-ons/kernel/file_systems/ext2/HashRevokeManager.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HashRevokeManager.h    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/HashRevokeManager.h    (revision 0)
@@ -0,0 +1,47 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef HASHREVOKEMANAGER_H
+#define HASHREVOKEMANAGER_H
+
+#include <util/khash.h>
+
+#include "RevokeManager.h"
+
+
+struct RevokeElement {
+   RevokeElement*  next;   // Next in hash
+   uint32          block;
+   uint32          commitID;
+};
+
+
+class HashRevokeManager : public RevokeManager {
+public:
+                       HashRevokeManager();
+   virtual             ~HashRevokeManager();
+
+           status_t    Init();
+
+   virtual status_t    Insert(uint32 block, uint32 commitID);
+   virtual status_t    Remove(uint32 block);
+   virtual bool        Lookup(uint32 block, uint32 commitID);
+
+   static  int         Compare(void* element, const void* key);
+   static  uint32      Hash(void* element, const void* key, uint32 range);
+
+protected:
+           status_t    _ForceInsert(uint32 block, uint32 commitID);
+
+private:
+           hash_table* fHash;
+
+   const   int         kInitialHashSize;
+};
+
+#endif // HASHREVOKEMANAGER_H
+

Property changes on: src/add-ons/kernel/file_systems/ext2/HashRevokeManager.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/kernel_interface.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/kernel_interface.cpp   (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/kernel_interface.cpp   (working copy)
@@ -11,8 +11,11 @@
 #include <AutoDeleter.h>
 #include <fs_cache.h>
 #include <fs_info.h>
+#include <io_requests.h>
+#include <NodeMonitor.h>

 #include "AttributeIterator.h"
+#include "CachedBlock.h"
 #include "DirectoryIterator.h"
 #include "ext2.h"
 #include "HTree.h"
@@ -52,6 +55,29 @@
 }


+//!    ext2_io() callback hook
+static status_t
+iterative_io_get_vecs_hook(void* cookie, io_request* request, off_t offset,
+   size_t size, struct file_io_vec* vecs, size_t* _count)
+{
+   Inode* inode = (Inode*)cookie;
+
+   return file_map_translate(inode->Map(), offset, size, vecs, _count,
+       inode->GetVolume()->BlockSize());
+}
+
+
+//!    ext2_io() callback hook
+static status_t
+iterative_io_finished_hook(void* cookie, io_request* request, status_t status,
+   bool partialTransfer, size_t bytesTransferred)
+{
+   Inode* inode = (Inode*)cookie;
+   rw_lock_read_unlock(inode->Lock());
+   return B_OK;
+}
+
+
 // #pragma mark - Scanning


@@ -116,6 +142,7 @@

    status_t status = volume->Mount(device, flags);
    if (status != B_OK) {
+       TRACE("Failed mounting the volume. Error: %s\n", strerror(status));
        delete volume;
        return status;
    }
@@ -148,7 +175,7 @@
    info->io_size = EXT2_IO_SIZE;
    info->block_size = volume->BlockSize();
    info->total_blocks = volume->NumBlocks();
-   info->free_blocks = volume->FreeBlocks();
+   info->free_blocks = volume->NumFreeBlocks();

    // Volume name
    strlcpy(info->volume_name, volume->Name(), sizeof(info->volume_name));
@@ -253,6 +280,81 @@


 static status_t
+ext2_write_pages(fs_volume* _volume, fs_vnode* _node, void* _cookie,
+   off_t pos, const iovec* vecs, size_t count, size_t* _numBytes)
+{
+   Volume* volume = (Volume*)_volume->private_volume;
+   Inode* inode = (Inode*)_node->private_node;
+
+   if (volume->IsReadOnly())
+       return B_READ_ONLY_DEVICE;
+
+   if (inode->FileCache() == NULL)
+       return B_BAD_VALUE;
+
+   rw_lock_read_lock(inode->Lock());
+
+   uint32 vecIndex = 0;
+   size_t vecOffset = 0;
+   size_t bytesLeft = *_numBytes;
+   status_t status;
+
+   while (true) {
+       file_io_vec fileVecs[8];
+       size_t fileVecCount = 8;
+
+       status = file_map_translate(inode->Map(), pos, bytesLeft, fileVecs,
+           &fileVecCount, 0);
+       if (status != B_OK && status != B_BUFFER_OVERFLOW)
+           break;
+
+       bool bufferOverflow = status == B_BUFFER_OVERFLOW;
+
+       size_t bytes = bytesLeft;
+       status = write_file_io_vec_pages(volume->Device(), fileVecs,
+           fileVecCount, vecs, count, &vecIndex, &vecOffset, &bytes);
+       if (status != B_OK || !bufferOverflow)
+           break;
+
+       pos += bytes;
+       bytesLeft -= bytes;
+   }
+
+   rw_lock_read_unlock(inode->Lock());
+
+   return status;
+}
+
+
+static status_t
+ext2_io(fs_volume* _volume, fs_vnode* _node, void* _cookie, io_request* request)
+{
+   Volume* volume = (Volume*)_volume->private_volume;
+   Inode* inode = (Inode*)_node->private_node;
+
+#ifndef EXT2_SHELL
+   if (io_request_is_write(request) && volume->IsReadOnly()) {
+       notify_io_request(request, B_READ_ONLY_DEVICE);
+       return B_READ_ONLY_DEVICE;
+   }
+#endif
+
+   if (inode->FileCache() == NULL) {
+#ifndef EXT2_SHELL
+       notify_io_request(request, B_BAD_VALUE);
+#endif
+       return B_BAD_VALUE;
+   }
+
+   // We lock the node here and will unlock it in the "finished" hook.
+   rw_lock_read_lock(inode->Lock());
+
+   return do_iterative_fd_io(volume->Device(), request,
+       iterative_io_get_vecs_hook, iterative_io_finished_hook, inode);
+}
+
+
+static status_t
 ext2_get_file_map(fs_volume* _volume, fs_vnode* _node, off_t offset,
    size_t size, struct file_io_vec* vecs, size_t* _count)
 {
@@ -294,7 +396,7 @@
        if (size <= vecs[index - 1].length || offset >= inode->Size()) {
            // We're done!
            *_count = index;
-           TRACE("ext2_get_file_map for inode %ld\n", inode->ID());
+           TRACE("ext2_get_file_map for inode %ld\n", (long)inode->ID());
            return B_OK;
        }
    }
@@ -339,12 +441,72 @@
        if (!strcmp(buffer, name))
            break;
    }
-
+
    return get_vnode(volume->FSVolume(), *_vnodeID, NULL);
 }

+void
+transaction_written(int32 id, int32, void*)
+{
+   TRACE("transaction_written: %ld\n", id);
+}

 static status_t
+ext2_ioctl(fs_volume* _volume, fs_vnode* _node, void* _cookie, uint32 cmd,
+   void* buffer, size_t bufferLength)
+{
+   TRACE("ioctl: %lu\n", cmd);
+
+   Volume* volume = (Volume*)_volume->private_volume;
+   switch (cmd) {
+       case 56742:
+       {
+           TRACE("ioctl: Test the block allocator\n");
+           // Test the block allocator
+           TRACE("ioctl: Creating transaction\n");
+           Transaction transaction(volume->GetJournal());
+           TRACE("ioctl: Creating cached block\n");
+           CachedBlock cached(volume);
+           uint32 blocksPerGroup = volume->BlocksPerGroup();
+           uint32 blockSize  = volume->BlockSize();
+           uint32 firstBlock = volume->FirstDataBlock();
+           uint32 start = 0;
+           uint32 group = 0;
+           uint32 length;
+
+           TRACE("ioctl: blocks per group: %lu, block size: %lu, "
+               "first block: %lu, start: %lu, group: %lu\n", blocksPerGroup,
+               blockSize, firstBlock, start, group);
+
+           while (volume->AllocateBlocks(transaction, 1, 2048, group, start,
+                   length) == B_OK) {
+               TRACE("ioctl: Allocated blocks in group %lu: %lu-%lu\n", group,
+                   start, start + length);
+               uint32 blockNum = start + group * blocksPerGroup - firstBlock;
+
+               for (uint32 i = 0; i < length; ++i) {
+                   uint8* block = cached.SetToWritable(transaction, blockNum);
+                   memset(block, 0, blockSize);
+                   blockNum++;
+               }
+
+               TRACE("ioctl: Blocks cleared\n");
+
+               transaction.Done();
+               transaction.Start(volume->GetJournal());
+           }
+
+           TRACE("ioctl: Done\n");
+
+           return B_OK;
+       }
+   }
+
+   return B_OK;
+}
+
+
+static status_t
 ext2_read_stat(fs_volume* _volume, fs_vnode* _node, struct stat* stat)
 {
    Inode* inode = (Inode*)_node->private_node;
@@ -371,6 +533,48 @@
 }


+status_t
+ext2_write_stat(fs_volume* _volume, fs_vnode* _node, const struct stat* stat,
+   uint32 mask)
+{
+   TRACE("ext2_write_stat\n");
+   Volume* volume = (Volume*)_volume->private_volume;
+
+   if (volume->IsReadOnly())
+       return B_READ_ONLY_DEVICE;
+
+   Inode* inode = (Inode*)_node->private_node;
+
+   status_t status = inode->CheckPermissions(W_OK);
+   if (status < B_OK)
+       return status;
+
+   TRACE("ext2_write_stat: Starting transaction\n");
+   Transaction transaction(volume->GetJournal());
+   inode->WriteLockInTransaction(transaction);
+
+   if ((mask & B_STAT_SIZE) != 0) {
+       if (inode->IsDirectory())
+           return B_IS_A_DIRECTORY;
+       if (!inode->IsFile())
+           return B_BAD_VALUE;
+
+       TRACE("ext2_write_stat: Old size: %ld, new size: %ld\n", (long)inode->Size(),
+           (long)stat->st_size);
+       if (inode->Size() != stat->st_size) {
+           off_t oldSize = inode->Size();
+
+           status = inode->Resize(transaction, stat->st_size);
+           // if(status != B_OK)
+               transaction.Done(true);
+               return status;
+       }
+   }
+
+   return B_NOT_ALLOWED;
+}
+
+
 static status_t
 ext2_open(fs_volume* _volume, fs_vnode* _node, int openMode, void** _cookie)
 {
@@ -748,8 +952,8 @@

    &ext2_get_file_map,

+   &ext2_ioctl,
    NULL,
-   NULL,
    NULL,   // fs_select
    NULL,   // fs_deselect
    NULL,
@@ -763,7 +967,7 @@

    &ext2_access,
    &ext2_read_stat,
-   NULL,
+   &ext2_write_stat,

    /* file operations */
    NULL,
Index: src/add-ons/kernel/file_systems/ext2/InodeAllocator.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/InodeAllocator.h   (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/InodeAllocator.h   (revision 0)
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef INODEALLOCATOR_H
+#define INODEALLOCATOR_H
+
+#include <lock.h>
+
+#include "Transaction.h"
+
+
+class Inode;
+class Volume;
+
+
+class InodeAllocator {
+public:
+                       InodeAllocator(Volume* volume);
+   virtual             ~InodeAllocator();
+
+   virtual status_t    New(Transaction& transaction, Inode* parent,
+                           int32 mode, ino_t& id);
+
+private:
+           status_t    _Allocate(Transaction& transaction,
+                           uint32 prefferedBlockGroup, ino_t& id);
+           status_t    _MarkInBitmap(Transaction& transaction,
+                           uint32 bitmapBlock, uint32 blockGroup,
+                           uint32 numInodes, ino_t& id);
+
+
+           Volume*     fVolume;
+           mutex       fLock;
+};
+
+#endif // INODEALLOCATOR_H

Property changes on: src/add-ons/kernel/file_systems/ext2/InodeAllocator.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/HTree.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HTree.cpp  (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/HTree.cpp  (working copy)
@@ -7,6 +7,7 @@
  */


+#include "CachedBlock.h"
 #include "HTree.h"

 #include <new>
@@ -17,6 +18,8 @@
 #include "Volume.h"


+//#define COLLISION_TEST
+
 //#define TRACE_EXT2
 #ifdef TRACE_EXT2
 #  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
@@ -75,90 +78,138 @@

 HTree::~HTree()
 {
+   delete fRootEntry;
 }


 status_t
+HTree::PrepareForHash()
+{
+   uint32 blockNum;
+   status_t status = fDirectory->FindBlock(0, blockNum);
+   if (status != B_OK)
+       return status;
+
+   CachedBlock cached(fDirectory->GetVolume());
+   const uint8* block = cached.SetTo(blockNum);
+
+   HTreeRoot* root = (HTreeRoot*)block;
+
+   if (root == NULL)
+       return B_IO_ERROR;
+   if (!root->IsValid())
+       return B_BAD_DATA;
+
+   fHashVersion = root->hash_version;
+
+   return B_OK;
+}
+
+
+status_t
 HTree::Lookup(const char* name, DirectoryIterator** iterator)
 {
+   TRACE("HTree::Lookup()\n");
    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);
+       TRACE("HTree::Lookup(): Falling back to linear iteration\n");

        if (*iterator == NULL)
            return B_NO_MEMORY;
        return B_OK;
    }

-   HTreeRoot root;
-   size_t length = sizeof(root);
+   uint32 blockNum;
+   status_t status = fDirectory->FindBlock(0, blockNum);
+   if (status != B_OK) {
+       *iterator = new(std::nothrow) DirectoryIterator(fDirectory);
+       TRACE("HTree::Lookup(): Failed to read block in diretory\n");
+
+       if (*iterator == NULL)
+           return B_NO_MEMORY;
+       return B_OK;
+   }
+
+   CachedBlock cached(fDirectory->GetVolume());
+   const uint8* block = cached.SetTo(blockNum);
+
+   HTreeRoot* root = (HTreeRoot*)block;

-   status_t status = fDirectory->ReadAt(0, (uint8*)&root, &length);
-   if (status < B_OK)
-       return status;
-
-   if (length != sizeof(root) || !root.IsValid()) {
+   if (root == NULL || !root->IsValid()) {
        // Fallback to linear search
        *iterator = new(std::nothrow) DirectoryIterator(fDirectory);
+       TRACE("HTree::Lookup(): Invalid root node\n");
        if (*iterator == NULL)
            return B_NO_MEMORY;

        return B_OK;
    }
+
+   fHashVersion = root->hash_version;

-   uint32 hash = _Hash(name, root.hash_version);
+   size_t _nameLength = strlen(name);
+   uint8 nameLength = _nameLength >= 256 ? 255 : (uint8)_nameLength;
+
+   uint32 hash = Hash(name, nameLength);

-   off_t start = (off_t)root.root_info_length
+   off_t start = (off_t)root->root_info_length
        + 2 * (sizeof(HTreeFakeDirEntry) + 4);

+   delete fRootEntry;
+
    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);
+   return fRootEntry->Lookup(hash, (uint32)root->indirection_levels, iterator);
 }


 uint32
-HTree::_Hash(const char* name, uint8 version)
+HTree::Hash(const char* name, uint8 length)
 {
    uint32 hash;

-   switch (version) {
+#ifndef COLLISION_TEST
+   switch (fHashVersion) {
        case HTREE_HASH_LEGACY:
-           hash = _HashLegacy(name);
+           hash = _HashLegacy(name, length);
            break;
        case HTREE_HASH_HALF_MD4:
-           hash = _HashHalfMD4(name);
+           hash = _HashHalfMD4(name, length);
            break;
        case HTREE_HASH_TEA:
-           hash = _HashTEA(name);
+           hash = _HashTEA(name, length);
            break;
        default:
            panic("Hash verification succeeded but then failed?");
            hash = 0;
    };
+#else
+   hash = 0;
+#endif

-   TRACE("Filename hash: %u\n", hash);
+   TRACE("HTree::_Hash(): filename hash 0x%lX\n", hash);

    return hash & ~1;
 }


 uint32
-HTree::_HashLegacy(const char* name)
+HTree::_HashLegacy(const char* name, uint8 length)
 {
+   TRACE("HTree::_HashLegacy()\n");
    uint32 hash = 0x12a3fe2d;
    uint32 previous = 0x37abe8f9;

-   for (; *name != '\0'; ++name) {
+   for (; length > 0; --length, ++name) {
        uint32 next = previous + (hash ^ (*name * 7152373));

        if ((next & 0x80000000) != 0)
@@ -168,7 +219,7 @@
        hash = next;
    }

-   return hash;
+   return hash << 1;
 }


@@ -230,8 +281,8 @@
    shifts[2] = 9;
    shifts[3] = 13;

-   for (int j = 0; j < 2; ++j) {
-       for (int i = j; i < 4; i += 2) {
+   for (int j = 1; j >= 0; --j) {
+       for (int i = j; i < 8; i += 2) {
            a += _MD4G(b, c, d) + blocks[i] + 013240474631UL;
            uint32 shift = shifts[i / 2];
            a = (a << shift) | (a >> (32 - shift));
@@ -247,13 +298,13 @@

    for (int i = 0; i < 4; ++i) {
        a += _MD4H(b, c, d) + blocks[3 - i] + 015666365641UL;
-       uint32 shift = shifts[i*2];
+       uint32 shift = shifts[i * 2 % 4];
        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];
+       shift = shifts[(i * 2 + 1) % 4];
        a = (a << shift) | (a >> (32 - shift));

        _MD4RotateVars(a, b, c, d);
@@ -267,8 +318,9 @@


 uint32
-HTree::_HashHalfMD4(const char* name)
+HTree::_HashHalfMD4(const char* name, uint8 length)
 {
+   TRACE("HTree::_HashHalfMD4()\n");
    uint32 buffer[4];

    buffer[0] = fHashSeed[0];
@@ -276,7 +328,7 @@
    buffer[2] = fHashSeed[2];
    buffer[3] = fHashSeed[3];

-   for (int length = strlen(name); length > 0; length -= 32) {
+   for (; length > 0; length -= 32) {
        uint32 blocks[8];

        _PrepareBlocksForHash(name, length, blocks, 8);
@@ -316,8 +368,9 @@


 uint32
-HTree::_HashTEA(const char* name)
+HTree::_HashTEA(const char* name, uint8 length)
 {
+   TRACE("HTree::_HashTEA()\n");
    uint32 buffer[4];

    buffer[0] = fHashSeed[0];
@@ -325,7 +378,7 @@
    buffer[2] = fHashSeed[2];
    buffer[3] = fHashSeed[3];

-   for (int length = strlen(name); length > 0; length -= 16) {
+   for (; length > 0; length -= 16) {
        uint32 blocks[4];

        _PrepareBlocksForHash(name, length, blocks, 4);
@@ -354,7 +407,7 @@
    int completeIterations = length / 4;

    for (int i = 0; i < completeIterations; ++i) {
-       uint32 value = 0 | *(string++);
+       uint32 value = (padding << 8) | *(string++);
        value = (value << 8) | *(string++);
        value = (value << 8) | *(string++);
        value = (value << 8) | *(string++);

Property changes on: src/add-ons/kernel/file_systems/ext2/HTree.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/NoJournal.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/NoJournal.cpp  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/NoJournal.cpp  (revision 0)
@@ -0,0 +1,100 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "NoJournal.h"
+
+#include <string.h>
+
+#include <fs_cache.h>
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+NoJournal::NoJournal(Volume* volume)
+   :
+   Journal()
+{
+   fFilesystemVolume = volume;
+   fFilesystemBlockCache = volume->BlockCache();
+   fJournalVolume = volume;
+   fHasSubTransaction = false;
+   fSeparateSubTransactions = false;
+}
+
+
+NoJournal::~NoJournal()
+{
+}
+
+
+status_t
+NoJournal::InitCheck()
+{
+   return B_OK;
+}
+
+
+status_t
+NoJournal::Recover()
+{
+   return B_OK;
+}
+
+
+status_t
+NoJournal::StartLog()
+{
+   return B_OK;
+}
+
+
+status_t
+NoJournal::Lock(Transaction* owner, bool separateSubTransactions)
+{
+   status_t status = block_cache_sync(fFilesystemBlockCache);
+   TRACE("NoJournal::Lock(): block_cache_sync: %s\n", strerror(status));
+
+   if (status == B_OK)
+       status = Journal::Lock(owner, separateSubTransactions);
+
+   return status;
+}
+
+
+status_t
+NoJournal::Unlock(Transaction* owner, bool success)
+{
+   TRACE("NoJournal::Unlock\n");
+   return Journal::Unlock(owner, success);
+}
+
+
+status_t
+NoJournal::_WriteTransactionToLog()
+{
+   TRACE("NoJournal::_WriteTransactionToLog(): Ending transaction %ld\n",
+       fTransactionID);
+
+   fTransactionID = cache_end_transaction(fFilesystemBlockCache,
+       fTransactionID, _TransactionWritten, NULL);
+
+   return B_OK;
+}
+
+
+/*static*/ void
+NoJournal::_TransactionWritten(int32 transactionID, int32 event, void* param)
+{
+   TRACE("Transaction %ld checkpointed\n", transactionID);
+}
Index: src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h   (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h   (working copy)
@@ -14,6 +14,9 @@
 #include "DirectoryIterator.h"


+class Volume;
+
+
 class HTreeEntryIterator {
 public:
                                HTreeEntryIterator(off_t offset,
@@ -26,7 +29,10 @@
                                    DirectoryIterator** iterator);
            bool                HasCollision() { return fHasCollision; }

-           status_t            GetNext(off_t& offset);
+           status_t            GetNext(uint32& offset);
+
+           status_t            InsertEntry(uint32 hash, uint32 block,
+                                   bool hasCollision);
 private:
                                HTreeEntryIterator(uint32 block,
                                    uint32 blockSize, Inode* directory,
@@ -34,17 +40,20 @@
                                    bool hasCollision);

 private:
+           Inode*              fDirectory;
+           Volume*             fVolume;
+           status_t            fInitStatus;
+
            bool                fHasCollision;
            uint16              fLimit, fCount;
+           uint16              fFirstEntry;
+           uint16              fCurrentEntry;

            uint32              fBlockSize;
-           Inode*              fDirectory;
-           off_t               fOffset;
-           off_t               fMaxOffset;
+           uint32              fBlockNum;

            HTreeEntryIterator* fParent;
            HTreeEntryIterator* fChild;
-           ObjectDeleter<HTreeEntryIterator> fChildDeleter;
 };

 #endif // HTREE_ENTRY_ITERATOR_H
Index: src/add-ons/kernel/file_systems/ext2/Volume.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Volume.h   (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/Volume.h   (working copy)
@@ -9,8 +9,12 @@
 #include <lock.h>

 #include "ext2.h"
+#include "BlockAllocator.h"
+#include "InodeAllocator.h"
+#include "Transaction.h"

 class Inode;
+class Journal;


 enum volume_flags {
@@ -18,7 +22,7 @@
 };


-class Volume {
+class Volume : public TransactionListener {
 public:
                                Volume(fs_volume* volume);
                                ~Volume();
@@ -40,31 +44,61 @@

            uint32              NumInodes() const
                                    { return fNumInodes; }
+           uint32              NumGroups() const
+                                   { return fNumGroups; }
            off_t               NumBlocks() const
                                    { return fSuperBlock.NumBlocks(); }
-           off_t               FreeBlocks() const
-                                   { return fSuperBlock.FreeBlocks(); }
+           off_t               NumFreeBlocks() const
+                                   { return fFreeBlocks; }
+           uint32              FirstDataBlock() const
+                                   { return fFirstDataBlock; }

            uint32              BlockSize() const { return fBlockSize; }
            uint32              BlockShift() const { return fBlockShift; }
+           uint32              BlocksPerGroup() const
+                                   { return fSuperBlock.BlocksPerGroup(); }
            uint32              InodeSize() const
                                    { return fSuperBlock.InodeSize(); }
+           uint32              InodesPerGroup() const
+                                   { return fSuperBlock.InodesPerGroup(); }
            ext2_super_block&   SuperBlock() { return fSuperBlock; }

            status_t            GetInodeBlock(ino_t id, uint32& block);
            uint32              InodeBlockIndex(ino_t id) const;
            status_t            GetBlockGroup(int32 index,
                                    ext2_block_group** _group);
-
+
+           Journal*            GetJournal() { return fJournal; }
+
            bool                IndexedDirectories() const
                                    { return (fSuperBlock.CompatibleFeatures()
                                        & EXT2_FEATURE_DIRECTORY_INDEX) != 0; }

+           status_t            AllocateInode(Transaction& transaction,
+                                   Inode* parent, int32 mode, ino_t& id);
+
+           status_t            AllocateBlocks(Transaction& transaction,
+                                   uint32 minimum, uint32 maximum,
+                                   uint32& blockGroup, uint32& start,
+                                   uint32& length);
+           status_t            FreeBlocks(Transaction& transaction,
+                                   uint32 start, uint32 length);
+
+           status_t            LoadSuperBlock();
+           status_t            WriteSuperBlock(Transaction& transaction);
+
            // cache access
            void*               BlockCache() { return fBlockCache; }

+           status_t            FlushDevice();
+           status_t            Sync();
+
    static  status_t            Identify(int fd, ext2_super_block* superBlock);

+           // TransactionListener functions
+           void                TransactionDone(bool success);
+           void                RemovedFromTransaction();
+
 private:
    static  uint32              _UnsupportedIncompatibleFeatures(
                                    ext2_super_block& superBlock);
@@ -76,12 +110,21 @@
            int                 fDevice;
            ext2_super_block    fSuperBlock;
            char                fName[32];
+
+           BlockAllocator      fBlockAllocator;
+           InodeAllocator      fInodeAllocator;
+           Journal*            fJournal;
+           Inode*              fJournalInode;
+
            uint32              fFlags;
            uint32              fBlockSize;
            uint32              fBlockShift;
            uint32              fFirstDataBlock;
+
            uint32              fNumInodes;
            uint32              fNumGroups;
+           uint32              fFreeBlocks;
+           uint32              fFreeInodes;
            uint32              fGroupsPerBlock;
            ext2_block_group**  fGroupBlocks;
            uint32              fInodesPerBlock;
Index: src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp  (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp  (working copy)
@@ -8,6 +8,7 @@

 #include <string.h>

+#include "CachedBlock.h"
 #include "HTree.h"
 #include "Inode.h"

@@ -23,71 +24,244 @@
 DirectoryIterator::DirectoryIterator(Inode* inode)
    :
    fInode(inode),
-   fOffset(0)
+   fBlockSize(inode->GetVolume()->BlockSize()),
+   fLogicalBlock(0),
+   fDisplacement(0)
 {
+   fInitStatus = fInode->FindBlock(0, fPhysicalBlock);
 }


+DirectoryIterator::DirectoryIterator(Inode* inode, off_t offset)
+   :
+   fInode(inode),
+   fBlockSize(inode->GetVolume()->BlockSize()),
+   fLogicalBlock(offset / fBlockSize),
+   fDisplacement(offset % fBlockSize)
+{
+   fInitStatus = fInode->FindBlock(offset, fPhysicalBlock);
+}
+
+
 DirectoryIterator::~DirectoryIterator()
 {
 }


 status_t
+DirectoryIterator::InitCheck()
+{
+   return fInitStatus;
+}
+
+
+status_t
 DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
 {
-   if (fOffset + sizeof(ext2_dir_entry) >= fInode->Size()) {
+   TRACE("DirectoryIterator::GetNext()\n");
+
+   if (fLogicalBlock * fBlockSize + fDisplacement
+           + ext2_dir_entry::MinimumSize() >= fInode->Size()) {
        TRACE("DirectoryIterator::GetNext() out of entries\n");
        return B_ENTRY_NOT_FOUND;
    }

-   ext2_dir_entry entry;
+   TRACE("DirectoryIterator::GetNext(): Creating cached block\n");

-   while (true) {
-       size_t length = ext2_dir_entry::MinimumSize();
-       status_t status = fInode->ReadAt(fOffset, (uint8*)&entry, &length);
-       if (status != B_OK)
-           return status;
-       if (length < ext2_dir_entry::MinimumSize() || entry.Length() == 0)
+   CachedBlock cached(fInode->GetVolume());
+   ext2_dir_entry* entry;
+
+   const uint8* block = cached.SetTo(fPhysicalBlock);
+   if (block == NULL)
+       return B_IO_ERROR;
+
+   bool gotEntry = false;
+   while (!gotEntry) {
+       TRACE("Checking entry at block %lu, displacement %lu\n", fPhysicalBlock,
+           fDisplacement);
+
+       entry = (ext2_dir_entry*)(block + fDisplacement);
+
+       if (entry->Length() == 0) {
+           TRACE("empty entry.\n");
            return B_ENTRY_NOT_FOUND;
-       if (!entry.IsValid())
+       }
+       if (!entry->IsValid()) {
+           TRACE("invalid entry.\n");
            return B_BAD_DATA;
+       }

-       if (entry.NameLength() != 0)
-           break;
+       if (entry->NameLength() != 0) {
+           // Get name
+           gotEntry = true;

-       fOffset += entry.Length();
+           size_t length = entry->NameLength();
+
+           TRACE("block %lu, displacement %lu: entry ino %lu, length %u, "
+               "name length %lu, type %lu\n", fLogicalBlock, fDisplacement,
+               entry->InodeID(), entry->Length(), (uint32)length,
+               (uint32)entry->FileType());
+
+           if (*_nameLength < length)
+               length = *_nameLength - 1;
+           memcpy(name, entry->name, length);
+           name[length] = '\0';
+
+           *_id = entry->InodeID();
+           *_nameLength = length;
+       }
+
+       fDisplacement += entry->Length();
+
+       if (fDisplacement == fBlockSize) {
+           TRACE("Reached end of block\n");
+
+           fDisplacement = 0;
+           fLogicalBlock++;
+
+           if (fLogicalBlock * fBlockSize + ext2_dir_entry::MinimumSize()
+                   < fInode->Size()) {
+               status_t status = fInode->FindBlock(fLogicalBlock * fBlockSize,
+                   fPhysicalBlock);
+               if (status != B_OK)
+                   return status;
+           } else if (!gotEntry) {
+               TRACE("DirectoryIterator::GetNext() end of directory file\n");
+               return B_ENTRY_NOT_FOUND;
+           }
+
+           if (!gotEntry) {
+               block = cached.SetTo(fPhysicalBlock);
+               if (block == NULL)
+                   return B_IO_ERROR;
+           }
+       } else if (fDisplacement > fBlockSize && !gotEntry) {
+           TRACE("The entry isn't block aligned.\n");
+           // TODO: Is block alignment obligatory?
+           return B_BAD_DATA;
+       }
+
        TRACE("DirectoryIterator::GetNext() skipping entry\n");
    }

-   TRACE("offset %Ld: entry ino %lu, length %u, name length %u, type %u\n",
-       fOffset, entry.InodeID(), entry.Length(), entry.NameLength(),
-       entry.FileType());
+   return B_OK;
+}

-   // read name

-   size_t length = entry.NameLength();
-   status_t status = fInode->ReadAt(fOffset + ext2_dir_entry::MinimumSize(),
-       (uint8*)entry.name, &length);
-   if (status == B_OK) {
-       if (*_nameLength < length)
-           length = *_nameLength - 1;
-       memcpy(name, entry.name, length);
-       name[length] = '\0';
+status_t
+DirectoryIterator::Rewind()
+{
+   fDisplacement = 0;
+   fLogicalBlock = 0;

-       *_id = entry.InodeID();
-       *_nameLength = length;
+   return fInode->FindBlock(0, fPhysicalBlock);
+}

-       fOffset += entry.Length();
+
+status_t
+DirectoryIterator::AddEntry(Transaction& transaction, const char* name,
+   size_t _nameLength, ino_t id)
+{
+   // TODO: Missing file type
+   off_t inodeSize = fInode->Size();
+   uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH
+       : _nameLength;
+
+   uint32 lastBlock = (uint32)inodeSize / fBlockSize;
+   if (inodeSize % fBlockSize != 0)
+       lastBlock++;
+
+   while (fLogicalBlock <= lastBlock) {
+       uint16 pos = 0;
+       uint16 newLength;
+
+       if (_AllocateBestEntryInBlock(nameLength, pos, newLength) == B_OK) {
+           CachedBlock cached(fInode->GetVolume());
+           uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
+
+           ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos];
+           uint16 previousLength = dirEntry->Length();
+           dirEntry->SetLength(newLength);
+
+           dirEntry = (ext2_dir_entry*)&block[pos + newLength];
+           dirEntry->SetLength(previousLength - newLength);
+           dirEntry->name_length = nameLength;
+           dirEntry->SetInodeID(id);
+           memcpy(dirEntry->name, name, nameLength);
+
+           return B_OK;
+       }
+
+       fLogicalBlock++;
+       status_t status = fInode->FindBlock(fLogicalBlock, fPhysicalBlock);
+       if (status != B_OK)
+           return status;
    }

-   return status;
+   status_t status = fInode->Resize(transaction, (lastBlock + 2) * fBlockSize);
+   if (status != B_OK)
+       return status;
+
+   fLogicalBlock = lastBlock + 1;
+   status = fInode->FindBlock(fLogicalBlock, fPhysicalBlock);
+   if (status != B_OK)
+       return status;
+
+   CachedBlock cached(fInode->GetVolume());
+   uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
+
+   ext2_dir_entry* dirEntry = (ext2_dir_entry*)block;
+   dirEntry->SetLength((uint16)fBlockSize);
+   dirEntry->name_length = nameLength;
+   dirEntry->SetInodeID(id);
+   memcpy(dirEntry->name, name, nameLength);
+
+   return B_OK;
 }


 status_t
-DirectoryIterator::Rewind()
+DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos,
+   uint16& newLength)
 {
-   fOffset = 0;
+   CachedBlock cached(fInode->GetVolume());
+   const uint8* block = cached.SetTo(fPhysicalBlock);
+
+   uint16 requiredLength = nameLength + 8;
+   if (requiredLength % 4 != 0)
+       requiredLength += 4 - requiredLength % 4;
+
+   uint16 bestPos = fBlockSize;
+   uint16 bestLength = fBlockSize;
+   ext2_dir_entry* dirEntry;
+
+   while (pos < fBlockSize) {
+       dirEntry = (ext2_dir_entry*)&block[pos];
+
+       uint16 realLength = dirEntry->NameLength() + 8;
+
+       if (realLength % 4 != 0)
+           realLength += 4 - realLength % 4;
+
+       uint16 emptySpace = dirEntry->Length() - realLength;
+       if (emptySpace == requiredLength) {
+           // Found an exact match
+           newLength = realLength;
+
+           return B_OK;
+       } else if (emptySpace > requiredLength && emptySpace < bestLength) {
+           bestPos = pos;
+           bestLength = emptySpace;
+           newLength = realLength;
+       }
+
+       pos += dirEntry->Length();
+   }
+
+   if (bestPos != fBlockSize) {
+       pos = bestPos;
+   } else
+       return B_DEVICE_FULL;
+
    return B_OK;
 }
Index: src/add-ons/kernel/file_systems/ext2/Journal.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Journal.h  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/Journal.h  (revision 0)
@@ -0,0 +1,258 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef JOURNAL_H
+#define JOURNAL_H
+
+
+#define JOURNAL_MAGIC                              0xc03b3998U
+
+#define JOURNAL_DESCRIPTOR_BLOCK                   1
+#define JOURNAL_COMMIT_BLOCK                       2
+#define JOURNAL_SUPERBLOCK_V1                      3
+#define JOURNAL_SUPERBLOCK_V2                      4
+#define JOURNAL_REVOKE_BLOCK                       5
+
+#define JOURNAL_FLAG_ESCAPED                       1
+#define JOURNAL_FLAG_SAME_UUID                     2
+#define JOURNAL_FLAG_DELETED                       4
+#define JOURNAL_FLAG_LAST_TAG                      8
+
+#define JOURNAL_FEATURE_INCOMPATIBLE_REVOKE            1
+
+#define JOURNAL_KNOWN_READ_ONLY_COMPATIBLE_FEATURES    0
+#define JOURNAL_KNOWN_INCOMPATIBLE_FEATURES            \
+   JOURNAL_FEATURE_INCOMPATIBLE_REVOKE
+
+
+#include "Volume.h"
+
+#include <AutoDeleter.h>
+#include <util/DoublyLinkedList.h>
+
+#include "Transaction.h"
+
+
+class RevokeManager;
+
+
+struct JournalHeader {
+   uint32          magic;
+   uint32          block_type;
+   uint32          sequence;
+   char            data[0];
+
+   uint32          Magic()         const
+       { return B_BENDIAN_TO_HOST_INT32(magic); }
+   uint32          BlockType()     const
+       { return B_BENDIAN_TO_HOST_INT32(block_type); }
+   uint32          Sequence()      const
+       { return B_BENDIAN_TO_HOST_INT32(sequence); }
+
+   bool            CheckMagic()    const
+       { return Magic() == JOURNAL_MAGIC; }
+
+   void            IncrementSequence()
+       { sequence = B_HOST_TO_BENDIAN_INT32(Sequence() + 1); }
+   void            DecrementSequence()
+       { sequence = B_HOST_TO_BENDIAN_INT32(Sequence() - 1); }
+   void            MakeDescriptor(uint32 sequence);
+   void            MakeCommit(uint32 sequence);
+} _PACKED;
+
+
+struct JournalBlockTag {
+   uint32          block_number;
+   uint32          flags;
+
+   uint32          BlockNumber()   const
+       { return B_BENDIAN_TO_HOST_INT32(block_number); }
+   uint32          Flags()         const
+       { return B_BENDIAN_TO_HOST_INT32(flags); }
+
+   void            SetBlockNumber(uint32 block)
+       { block_number = B_HOST_TO_BENDIAN_INT32(block); }
+   void            SetFlags(uint32 new_flags)
+       { flags = B_HOST_TO_BENDIAN_INT32(new_flags); }
+   void            SetLastTagFlag()
+       { flags |= B_HOST_TO_BENDIAN_INT32(JOURNAL_FLAG_LAST_TAG); }
+   void            SetEscapedFlag()
+       { flags |= B_HOST_TO_BENDIAN_INT32(JOURNAL_FLAG_ESCAPED); }
+} _PACKED;
+
+
+struct JournalRevokeHeader {
+   JournalHeader   header;
+   uint32          num_bytes;
+
+   uint32          revoke_blocks[0];
+
+   uint32          NumBytes()      const
+       { return B_BENDIAN_TO_HOST_INT32(num_bytes); }
+   uint32          RevokeBlock(int offset) const
+       { return B_BENDIAN_TO_HOST_INT32(revoke_blocks[offset]); }
+} _PACKED;
+
+
+struct JournalSuperBlock {
+   JournalHeader   header;
+
+   uint32          block_size;
+   uint32          num_blocks;
+   uint32          first_log_block;
+
+   uint32          first_commit_id;
+   uint32          log_start;
+
+   uint32          error;
+
+   uint32          compatible_features;
+   uint32          incompatible_features;
+   uint32          read_only_compatible_features;
+
+   uint8           uuid[16];
+
+   uint32          num_users;
+   uint32          dynamic_superblock;
+
+   uint32          max_transaction_blocks;
+   uint32          max_transaction_data;
+
+   uint32          padding[44];
+
+   uint8           user_ids[16*48];
+
+   uint32          BlockSize() const
+       { return B_BENDIAN_TO_HOST_INT32(block_size); }
+   uint32          NumBlocks() const
+       { return B_BENDIAN_TO_HOST_INT32(num_blocks); }
+   uint32          FirstLogBlock() const
+       { return B_BENDIAN_TO_HOST_INT32(first_log_block); }
+   uint32          FirstCommitID() const
+       { return B_BENDIAN_TO_HOST_INT32(first_commit_id); }
+   uint32          LogStart() const
+       { return B_BENDIAN_TO_HOST_INT32(log_start); }
+   uint32          IncompatibleFeatures() const
+       { return B_BENDIAN_TO_HOST_INT32(incompatible_features); }
+   uint32          ReadOnlyCompatibleFeatures() const
+       { return B_BENDIAN_TO_HOST_INT32(read_only_compatible_features); }
+   uint32          MaxTransactionBlocks() const
+       { return B_BENDIAN_TO_HOST_INT32(max_transaction_blocks); }
+   uint32          MaxTransactionData() const
+       { return B_BENDIAN_TO_HOST_INT32(max_transaction_data); }
+
+   void            SetLogStart(uint32 logStart)
+       { log_start = B_HOST_TO_BENDIAN_INT32(logStart); }
+   void            SetFirstCommitID(uint32 firstCommitID)
+       { first_commit_id = B_HOST_TO_BENDIAN_INT32(firstCommitID); }
+} _PACKED;
+
+class LogEntry;
+class Transaction;
+typedef DoublyLinkedList<LogEntry> LogEntryList;
+
+
+class Journal {
+public:
+                               Journal(Volume *fsVolume, Volume *jVolume);
+   virtual                     ~Journal();
+
+   virtual status_t            InitCheck();
+   virtual status_t            Deinit();
+
+   virtual status_t            Recover();
+   virtual status_t            StartLog();
+           status_t            RestartLog();
+
+   virtual status_t            Lock(Transaction* owner,
+                                   bool separateSubTransactions);
+   virtual status_t            Unlock(Transaction* owner, bool success);
+
+   virtual status_t            MapBlock(uint32 logical, uint32& physical);
+   inline  uint32              FreeLogBlocks() const;
+
+           status_t            FlushLogAndBlocks();
+
+           int32               TransactionID() const;
+
+           Volume*             GetFilesystemVolume()
+               { return fFilesystemVolume; }
+protected:
+                               Journal();
+
+           status_t            _WritePartialTransactionToLog(
+                                   JournalHeader* descriptorBlock,
+                                   bool detached, uint8** escapedBlock,
+                                   uint32& logBlock, off_t& blockNumber,
+                                   long& cookie,
+                                   ArrayDeleter<uint8>& escapedDataDeleter,
+                                   uint32& blockCount, bool& finished);
+   virtual status_t            _WriteTransactionToLog();
+
+           status_t            _SaveSuperBlock();
+           status_t            _LoadSuperBlock();
+
+
+           Volume*             fJournalVolume;
+           void*               fJournalBlockCache;
+           Volume*             fFilesystemVolume;
+           void*               fFilesystemBlockCache;
+
+           recursive_lock      fLock;
+           Transaction*        fOwner;
+
+           RevokeManager*      fRevokeManager;
+
+           status_t            fInitStatus;
+           uint32              fBlockSize;
+           uint32              fFirstCommitID;
+           uint32              fFirstCacheCommitID;
+           uint32              fFirstLogBlock;
+           uint32              fLogSize;
+           uint32              fVersion;
+
+           uint32              fLogStart;
+           uint32              fLogEnd;
+           uint32              fFreeBlocks;
+           uint32              fMaxTransactionSize;
+
+           uint32              fCurrentCommitID;
+           //uint32                fNextCommitID;
+
+           LogEntryList        fLogEntries;
+           mutex               fLogEntriesLock;
+           bool                fHasSubTransaction;
+           bool                fSeparateSubTransactions;
+           int32               fUnwrittenTransactions;
+           int32               fTransactionID;
+
+private:
+           status_t            _CheckFeatures(JournalSuperBlock* superblock);
+
+           uint32              _CountTags(JournalHeader *descriptorBlock);
+           status_t            _RecoverPassScan(uint32& lastCommitID);
+           status_t            _RecoverPassRevoke(uint32 lastCommitID);
+           status_t            _RecoverPassReplay(uint32 lastCommitID);
+
+           status_t            _FlushLog(bool canWait, bool flushBlocks);
+
+   inline  uint32              _WrapAroundLog(uint32 block);
+
+           size_t              _CurrentTransactionSize() const;
+           size_t              _FullTransactionSize() const;
+           size_t              _MainTransactionSize() const;
+
+   virtual status_t            _TransactionDone(bool success);
+
+   static  void                _TransactionWritten(int32 transactionID,
+                                   int32 event, void* _logEntry);
+   static  void                _TransactionIdle(int32 transactionID,
+                                   int32 event, void* _journal);
+};
+
+#endif // JOURNAL_H
+

Property changes on: src/add-ons/kernel/file_systems/ext2/Journal.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h (working copy)
@@ -17,7 +17,7 @@
 class IndexedDirectoryIterator : public DirectoryIterator {
 public:
                                IndexedDirectoryIterator(off_t start,
-                                   uint32 blockSize, Inode* directory,
+                                   Inode* directory,
                                    HTreeEntryIterator* parent);
    virtual                     ~IndexedDirectoryIterator();

@@ -25,12 +25,16 @@
                                    ino_t* id);

            status_t            Rewind();
+
+           status_t            AddEntry(Transaction& transaction,
+                                   const char* name, size_t _nameLength,
+                                   ino_t id);
+
 private:
            bool                fIndexing;
            HTreeEntryIterator* fParent;
-           off_t               fMaxOffset;
-           uint32              fBlockSize;
            uint32              fMaxAttempts;
+           uint32              fPreviousBlock;
 };

 #endif // INDEXED_DIRECTORY_ITERATOR_H
Index: src/add-ons/kernel/file_systems/ext2/Transaction.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/Transaction.cpp    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/Transaction.cpp    (revision 0)
@@ -0,0 +1,201 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "Transaction.h"
+
+#include <string.h>
+
+#include <fs_cache.h>
+
+#include "Journal.h"
+
+
+TransactionListener::TransactionListener()
+{
+}
+
+
+TransactionListener::~TransactionListener()
+{
+}
+
+
+Transaction::Transaction()
+   :
+   fJournal(NULL),
+   fParent(NULL)
+{
+}
+
+
+Transaction::Transaction(Journal* journal)
+   :
+   fJournal(NULL),
+   fParent(NULL)
+{
+   Start(journal);
+}
+
+
+Transaction::~Transaction()
+{
+   if (IsStarted())
+       fJournal->Unlock(this, false);
+}
+
+status_t
+Transaction::Start(Journal* journal)
+{
+   if (IsStarted())
+       return B_OK;
+
+   fJournal = journal;
+   if (fJournal == NULL)
+       return B_ERROR;
+
+   status_t status = fJournal->Lock(this, false);
+   if (status != B_OK)
+       fJournal = NULL;
+
+   return status;
+}
+
+
+status_t
+Transaction::Done(bool success)
+{
+   if (!IsStarted())
+       return B_OK;
+
+   status_t status = fJournal->Unlock(this, success);
+
+   if (status == B_OK)
+       fJournal = NULL;
+
+   return status;
+}
+
+
+int32
+Transaction::ID() const
+{
+   if (!IsStarted())
+       return -1;
+
+   return fJournal->TransactionID();
+}
+
+
+bool
+Transaction::IsStarted() const
+{
+   return fJournal != NULL;
+}
+
+
+bool
+Transaction::HasParent() const
+{
+   return fParent != NULL;
+}
+
+
+status_t
+Transaction::WriteBlocks(off_t blockNumber, const uint8* buffer,
+   size_t numBlocks)
+{
+   if (!IsStarted())
+       return B_NO_INIT;
+
+   void* cache = GetVolume()->BlockCache();
+   size_t blockSize = GetVolume()->BlockSize();
+
+   for (size_t i = 0; i < numBlocks; ++i) {
+       void* block = block_cache_get_empty(cache, blockNumber + i, ID());
+       if (block == NULL)
+           return B_ERROR;
+
+       memcpy(block, buffer, blockSize);
+       buffer += blockSize;
+
+       block_cache_put(cache, blockNumber + i);
+   }
+
+   return B_OK;
+}
+
+
+void
+Transaction::Split()
+{
+   cache_start_sub_transaction(fJournal->GetFilesystemVolume()->BlockCache(),
+       ID());
+}
+
+
+Volume*
+Transaction::GetVolume() const
+{
+   if (!IsStarted())
+       return NULL;
+
+   return fJournal->GetFilesystemVolume();
+}
+
+
+void
+Transaction::AddListener(TransactionListener* listener)
+{
+   if (!IsStarted())
+       panic("Transaction is not running!");
+
+   fListeners.Add(listener);
+}
+
+
+void
+Transaction::RemoveListener(TransactionListener* listener)
+{
+   if (!IsStarted())
+       panic("Transaction is not running!");
+
+   fListeners.Remove(listener);
+   listener->RemovedFromTransaction();
+}
+
+
+void
+Transaction::NotifyListeners(bool success)
+{
+   while (TransactionListener* listener = fListeners.RemoveHead()) {
+       listener->TransactionDone(success);
+       listener->RemovedFromTransaction();
+   }
+}
+
+
+void
+Transaction::MoveListenersTo(Transaction* transaction)
+{
+   while (TransactionListener* listener = fListeners.RemoveHead())
+       transaction->fListeners.Add(listener);
+}
+
+
+void
+Transaction::SetParent(Transaction* transaction)
+{
+   fParent = transaction;
+}
+
+
+Transaction*
+Transaction::Parent() const
+{
+   return fParent;
+}
Index: src/add-ons/kernel/file_systems/ext2/ext2.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/ext2.h (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/ext2.h (working copy)
@@ -13,6 +13,8 @@
 #include <KernelExport.h>


+#define TRACE_EXT2
+
 #define EXT2_SUPER_BLOCK_OFFSET    1024

 struct ext2_super_block {
@@ -108,9 +110,16 @@
        { return B_LENDIAN_TO_HOST_INT32(read_only_features); }
    uint32 IncompatibleFeatures() const
        { return B_LENDIAN_TO_HOST_INT32(incompatible_features); }
+   ino_t  JournalInode() const
+       { return B_LENDIAN_TO_HOST_INT32(journal_inode); }
    uint32 HashSeed(uint8 i) const
        { return B_LENDIAN_TO_HOST_INT32(hash_seed[i]); }

+   void SetFreeInodes(uint32 freeInodes)
+       { free_inodes = B_HOST_TO_LENDIAN_INT32(freeInodes); }
+   void SetFreeBlocks(uint32 freeBlocks)
+       { free_blocks = B_HOST_TO_LENDIAN_INT32(freeBlocks); }
+
    bool IsValid();
        // implemented in Volume.cpp
 } _PACKED;
@@ -162,8 +171,16 @@
    uint16  _padding;
    uint32  _reserved[3];

+   uint32 BlockBitmap() const
+       { return B_LENDIAN_TO_HOST_INT32(block_bitmap); }
+   uint32 InodeBitmap() const
+       { return B_LENDIAN_TO_HOST_INT32(inode_bitmap); }
    uint32 InodeTable() const
        { return B_LENDIAN_TO_HOST_INT32(inode_table); }
+   uint16 FreeBlocks() const
+       { return B_LENDIAN_TO_HOST_INT16(free_blocks); }
+   uint16 FreeInodes() const
+       { return B_LENDIAN_TO_HOST_INT16(free_inodes); }
 } _PACKED;

 #define EXT2_DIRECT_BLOCKS         12
@@ -175,6 +192,24 @@
    uint32 indirect;
    uint32 double_indirect;
    uint32 triple_indirect;
+
+   uint32  Direct(int index)   const
+       { return B_LENDIAN_TO_HOST_INT32(direct[index]); }
+   uint32  Indirect()          const
+       { return B_LENDIAN_TO_HOST_INT32(indirect); }
+   uint32  DoubleIndirect()    const
+       { return B_LENDIAN_TO_HOST_INT32(double_indirect); }
+   uint32  TripleIndirect()    const
+       { return B_LENDIAN_TO_HOST_INT32(triple_indirect); }
+
+   void    SetDirect(int index, uint32 value)
+       { direct[index] = B_HOST_TO_LENDIAN_INT32(value); }
+   void    SetIndirect(uint32 value)
+       { indirect = B_HOST_TO_LENDIAN_INT32(value); }
+   void    SetDoubleIndirect(uint32 value)
+       { double_indirect = B_HOST_TO_LENDIAN_INT32(value); }
+   void    SetTripleIndirect(uint32 value)
+       { triple_indirect = B_HOST_TO_LENDIAN_INT32(value); }
 } _PACKED;

 struct ext2_inode {
@@ -214,6 +249,7 @@
    uint16 Mode() const { return B_LENDIAN_TO_HOST_INT16(mode); }
    uint32 Flags() const { return B_LENDIAN_TO_HOST_INT32(flags); }
    uint16 NumLinks() const { return B_LENDIAN_TO_HOST_INT16(num_links); }
+   uint32 NumBlocks() const { return B_LENDIAN_TO_HOST_INT32(num_blocks); }

    time_t AccessTime() const { return B_LENDIAN_TO_HOST_INT32(access_time); }
    time_t CreationTime() const { return B_LENDIAN_TO_HOST_INT32(creation_time); }
@@ -241,6 +277,55 @@
        return B_LENDIAN_TO_HOST_INT16(gid)
            | (B_LENDIAN_TO_HOST_INT16(gid_high) << 16);
    }
+
+   void SetMode(uint16 newMode)
+   {
+       mode = B_LENDIAN_TO_HOST_INT16(newMode);
+   }
+
+   void SetFlags(uint32 newFlags)
+   {
+       flags = B_HOST_TO_LENDIAN_INT32(newFlags);
+   }
+
+   void SetNumLinks(uint16 numLinks)
+   {
+       num_links = B_HOST_TO_LENDIAN_INT16(numLinks);
+   }
+
+   void SetNumBlocks(uint32 numBlocks)
+   {
+       num_blocks = B_HOST_TO_LENDIAN_INT32(numBlocks);
+   }
+
+   void SetCreationTime(time_t creationTime)
+   {
+       creation_time = B_HOST_TO_LENDIAN_INT32(creationTime);
+   }
+
+   void SetModificationTime(time_t modificationTime)
+   {
+       modification_time = B_HOST_TO_LENDIAN_INT32(modificationTime);
+   }
+
+   void SetSize(off_t newSize)
+   {
+       size = B_HOST_TO_LENDIAN_INT32(newSize & 0xFFFFFFFF);
+       if (S_ISREG(Mode()))
+           size_high = B_HOST_TO_LENDIAN_INT32(newSize >> 32);
+   }
+
+   void SetUserID(uint32 newUID)
+   {
+       uid = B_HOST_TO_LENDIAN_INT16(newUID & 0xFFFF);
+       uid_high = B_HOST_TO_LENDIAN_INT16(newUID >> 16);
+   }
+
+   void SetGroupID(uint32 newGID)
+   {
+       gid = B_HOST_TO_LENDIAN_INT16(newGID & 0xFFFF);
+       gid_high = B_HOST_TO_LENDIAN_INT16(newGID >> 16);
+   }
 } _PACKED;

 #define EXT2_SUPER_BLOCK_MAGIC         0xef53
@@ -270,11 +355,26 @@
    uint8   file_type;
    char    name[EXT2_NAME_LENGTH];

-   uint32 InodeID() const { return B_LENDIAN_TO_HOST_INT32(inode_id); }
-   uint16 Length() const { return B_LENDIAN_TO_HOST_INT16(length); }
-   uint8 NameLength() const { return name_length; }
-   uint8 FileType() const { return file_type; }
+   uint32  InodeID() const { return B_LENDIAN_TO_HOST_INT32(inode_id); }
+   uint16  Length() const { return B_LENDIAN_TO_HOST_INT16(length); }
+   uint8   NameLength() const { return name_length; }
+   uint8   FileType() const { return file_type; }

+   void    SetInodeID(uint32 id) { inode_id = B_HOST_TO_LENDIAN_INT32(id); }
+
+   void    SetLength(uint8 nameLength)
+   {
+       name_length = nameLength;
+
+       if (nameLength % 4 == 0) {
+           length = B_HOST_TO_LENDIAN_INT16(
+               (short)(nameLength + MinimumSize()));
+       } else {
+           length = B_HOST_TO_LENDIAN_INT16(
+               (short)(nameLength % 4 + 1 + MinimumSize()));
+       }
+   }
+
    bool IsValid() const
    {
        return Length() > MinimumSize();
Index: src/add-ons/kernel/file_systems/ext2/CachedBlock.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/CachedBlock.h  (revision 37941)
+++ src/add-ons/kernel/file_systems/ext2/CachedBlock.h  (working copy)
@@ -9,32 +9,40 @@

 #include <fs_cache.h>

+#include "Transaction.h"
 #include "Volume.h"


 class CachedBlock {
 public:
-                   CachedBlock(Volume* volume);
-                   CachedBlock(Volume* volume, uint32 block);
-                   ~CachedBlock();
+                           CachedBlock(Volume* volume);
+                           CachedBlock(Volume* volume, uint32 block);
+                           ~CachedBlock();

-           void    Keep();
-           void    Unset();
+           void            Keep();
+           void            Unset();

-   const   uint8*  SetTo(uint32 block);
+           const uint8*    SetTo(uint32 block);
+           uint8*          SetToWritable(Transaction& transaction,
+                               uint32 block, bool empty = false);
+           uint8*          SetToWritableWithoutTransaction(uint32 block,
+                               bool empty = false);

-   const   uint8*  Block() const { return fBlock; }
-           off_t   BlockNumber() const { return fBlockNumber; }
+           const uint8*    Block() const { return fBlock; }
+           off_t           BlockNumber() const { return fBlockNumber; }

 private:
-                   CachedBlock(const CachedBlock &);
-                   CachedBlock &operator=(const CachedBlock &);
-                       // no implementation
+                           CachedBlock(const CachedBlock &);
+                           CachedBlock &operator=(const CachedBlock &);
+                               // no implementation
+
+           uint8*          _SetToWritableEtc(int32 transaction, uint32 block,
+                               bool empty);

 protected:
-   Volume*         fVolume;
-   uint32          fBlockNumber;
-   uint8*          fBlock;
+           Volume*         fVolume;
+           uint32          fBlockNumber;
+           uint8*          fBlock;
 };


@@ -94,4 +102,35 @@
    return fBlock = (uint8 *)block_cache_get(fVolume->BlockCache(), block);
 }

+
+inline uint8*
+CachedBlock::SetToWritable(Transaction& transaction, uint32 block, bool empty)
+{
+   return _SetToWritableEtc(transaction.ID(), block, empty);
+}
+
+
+inline uint8*
+CachedBlock::SetToWritableWithoutTransaction(uint32 block, bool empty)
+{
+   return _SetToWritableEtc((int32)-1, block, empty);
+}
+
+inline uint8*
+CachedBlock::_SetToWritableEtc(int32 transaction, uint32 block, bool empty)
+{
+   Unset();
+   fBlockNumber = block;
+
+   if (empty) {
+       fBlock = (uint8*)block_cache_get_empty(fVolume->BlockCache(),
+           block, transaction);
+   } else {
+       fBlock = (uint8*)block_cache_get_writable(fVolume->BlockCache(),
+           block, transaction);
+   }
+
+   return fBlock;
+}
+
 #endif // CACHED_BLOCK_H
Index: src/add-ons/kernel/file_systems/ext2/HashRevokeManager.cpp
===================================================================
--- src/add-ons/kernel/file_systems/ext2/HashRevokeManager.cpp  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/HashRevokeManager.cpp  (revision 0)
@@ -0,0 +1,158 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+
+#include "HashRevokeManager.h"
+
+#include <new>
+
+
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+#  define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
+#else
+#  define TRACE(x...) ;
+#endif
+
+
+HashRevokeManager::HashRevokeManager()
+   :
+   fHash(NULL),
+   kInitialHashSize(128)
+       // TODO: Benchmark and find an optimal value
+{
+}
+
+
+HashRevokeManager::~HashRevokeManager()
+{
+   if (fHash != NULL)
+       hash_uninit(fHash);
+}
+
+
+status_t
+HashRevokeManager::Init()
+{
+   RevokeElement dummyElement;
+
+   fHash = hash_init(kInitialHashSize, offset_of_member(dummyElement, next),
+       &HashRevokeManager::Compare,
+       &HashRevokeManager::Hash);
+
+   if (fHash == NULL)
+       return B_NO_MEMORY;
+
+   return B_OK;
+}
+
+
+status_t
+HashRevokeManager::Insert(uint32 block, uint32 commitID)
+{
+   RevokeElement* element = (RevokeElement*)hash_lookup(fHash, &block);
+
+   if (element != NULL) {
+       TRACE("HashRevokeManager::Insert(): Already has an element\n");
+       if (element->commitID < commitID) {
+           TRACE("HashRevokeManager::Insert(): Deleting previous element\n");
+           status_t retValue = hash_remove(fHash, element);
+
+           if (retValue != B_OK)
+               return retValue;
+
+           delete element;
+       }
+       else {
+           return B_OK;
+               // We already have a newer version of the block
+       }
+   }
+
+   return _ForceInsert(block, commitID);
+}
+
+
+status_t
+HashRevokeManager::Remove(uint32 block)
+{
+   RevokeElement* element = (RevokeElement*)hash_lookup(fHash, &block);
+
+   if (element == NULL)
+       return B_ERROR; // TODO: Perhaps we should just ignore?
+
+   status_t retValue = hash_remove(fHash, element);
+
+   if (retValue == B_OK)
+       delete element;
+
+   return retValue;
+}
+
+
+bool
+HashRevokeManager::Lookup(uint32 block, uint32 commitID)
+{
+   RevokeElement* element = (RevokeElement*)hash_lookup(fHash, &block);
+
+   if (element == NULL)
+       return false;
+
+   return element->commitID >= commitID;
+}
+
+
+/*static*/ int
+HashRevokeManager::Compare(void* _revoked, const void *_block)
+{
+   RevokeElement* revoked = (RevokeElement*)_revoked;
+   uint32 block = *(uint32*)_block;
+
+   if (revoked->block == block)
+       return 0;
+
+   return (revoked->block > block) ? 1 : -1;
+}
+
+
+/*static*/ uint32
+HashRevokeManager::Hash(void* _revoked, const void* _block, uint32 range)
+{
+   TRACE("HashRevokeManager::Hash(): revoked: %p, block: %p, range: %lu\n",
+       _revoked, _block, range);
+   RevokeElement* revoked = (RevokeElement*)_revoked;
+
+   if (revoked != NULL)
+       return revoked->block % range;
+
+   uint32 block = *(uint32*)_block;
+   return block % range;
+}
+
+
+status_t
+HashRevokeManager::_ForceInsert(uint32 block, uint32 commitID)
+{
+   RevokeElement* element = new(std::nothrow) RevokeElement;
+
+   if (element == NULL)
+       return B_NO_MEMORY;
+
+   element->block = block;
+   element->commitID = commitID;
+
+   status_t retValue = hash_insert_grow(fHash, element);
+
+   if (retValue == B_OK) {
+       fRevokeCount++;
+       TRACE("HashRevokeManager::_ForceInsert(): revoke count: %lu\n",
+           fRevokeCount);
+   }
+
+   return retValue;
+}
+

Property changes on: src/add-ons/kernel/file_systems/ext2/HashRevokeManager.cpp
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/RevokeManager.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/RevokeManager.h    (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/RevokeManager.h    (revision 0)
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef REVOKEMANAGER_H
+#define REVOKEMANAGER_H
+
+#include "Journal.h"
+
+
+struct JournalRevokeHeader;
+
+class RevokeManager {
+public:
+                       RevokeManager();
+   virtual             ~RevokeManager() = 0;
+
+   virtual status_t    Insert(uint32 block, uint32 commitID) = 0;
+   virtual status_t    Remove(uint32 block) = 0;
+   virtual bool        Lookup(uint32 block, uint32 commitID) = 0;
+
+           uint32      NumRevokes() { return fRevokeCount; }
+
+           status_t    ScanRevokeBlock(JournalRevokeHeader* revokeBlock,
+                           uint32 commitID);
+
+protected:
+           uint32      fRevokeCount;
+};
+
+#endif // REVOKEMANAGER_H
+

Property changes on: src/add-ons/kernel/file_systems/ext2/RevokeManager.h
___________________________________________________________________
Added: svn:executable
   + *

Index: src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
===================================================================
--- src/add-ons/kernel/file_systems/ext2/BitmapBlock.h  (revision 0)
+++ src/add-ons/kernel/file_systems/ext2/BitmapBlock.h  (revision 0)
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ *     Janito V. Ferreira Filho
+ */
+#ifndef BITMAPBLOCK_H
+#define BITMAPBLOCK_H
+
+#include "CachedBlock.h"
+
+
+class BitmapBlock : public CachedBlock {
+public:
+                           BitmapBlock(Volume* volume, uint32 numBits);
+                           ~BitmapBlock();
+
+           bool            SetTo(uint32 block);
+           bool            SetToWritable(Transaction& transaction,
+                               uint32 block, bool empty = false);
+
+           bool            CheckMarked(uint32 start, uint32 length);
+           bool            CheckUnmarked(uint32 start, uint32 length);
+
+           bool            Mark(uint32 start, uint32 length,
+                               bool force = false);
+           bool            Unmark(uint32 start, uint32 length,
+                               bool force = false);
+
+           void            FindNextMarked(uint32& pos);
+           void            FindNextUnmarked(uint32& pos);
+
+           void            FindPreviousMarked(uint32& pos);
+
+           void            FindLargestUnmarkedRange(uint32& start,
+                               uint32& length);
+
+           uint32          NumBits() const;
+
+protected:
+           uint32*         fData;
+           const uint32*   fReadOnlyData;
+
+           uint32          fNumBits;
+};
+
+#endif // BITMAPBLOCK_H

Property changes on: src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
___________________________________________________________________
Added: svn:executable
   + *