[haiku-commits] r39886 - haiku/trunk/src/add-ons/kernel/file_systems/ext2
- From: korli@xxxxxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Sat, 18 Dec 2010 17:26:40 +0100 (CET)
Author: korli
Date: 2010-12-18 17:26:39 +0100 (Sat, 18 Dec 2010)
New Revision: 39886
Changeset: http://dev.haiku-os.org/changeset/39886
Added:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.h
Removed:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h
Modified:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/InodeAllocator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/InodeAllocator.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/InodeJournal.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/InodeJournal.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Jamfile
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Journal.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Journal.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Volume.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Volume.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/ext2.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/kernel_interface.cpp
Log:
* added fsblock_t and fileblock_t definitions, used them when needed.
* validate fBlockShift in superblock.
* Volume::AllocateBlocks() now uses an absolute fsblock instead of a blockgroup
related fsblock.
* AllocationBlockGroup now provides absolute fsblock values.
* added support for extents feature: ExtentStream class is the equivalent for
DataStream class for extent operations.
The extent tree implementation is very basic, should work for normal
growing/shrinking
operations, but not for sparse files. When enlarging a file and extent tree
is full,
the root is moved in a new block and a new level is added on top. Extents can
usually
be extended when adjacent blocks are allocated. Shrinking happens by removing
leafs
one after another.
* removed empty IndexedDirectoryIterator.*
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
2010-12-18 16:26:39 UTC (rev 39886)
@@ -39,7 +39,7 @@
status_t ScanFreeRanges();
bool IsFull() const;
- status_t Allocate(Transaction& transaction,
uint32 start,
+ status_t Allocate(Transaction& transaction,
fsblock_t start,
uint32 length);
status_t Free(Transaction& transaction, uint32
start,
uint32 length);
@@ -48,9 +48,9 @@
uint32 NumBits() const;
uint32 FreeBits() const;
- uint32 Start() const;
+ fsblock_t Start() const;
- uint32 LargestStart() const;
+ fsblock_t LargestStart() const;
uint32 LargestLength() const;
// TransactionListener implementation
@@ -70,9 +70,9 @@
mutex fTransactionLock;
int32 fCurrentTransaction;
- uint32 fStart;
+ fsblock_t fStart;
uint32 fNumBits;
- off_t fBitmapBlock;
+ fsblock_t fBitmapBlock;
uint32 fFreeBits;
uint32 fFirstFree;
@@ -122,6 +122,7 @@
fVolume = volume;
fBlockGroup = blockGroup;
fNumBits = numBits;
+ fStart = blockGroup * numBits + fVolume->FirstDataBlock();
status_t status = fVolume->GetBlockGroup(blockGroup, &fGroupDescriptor);
if (status != B_OK)
@@ -187,13 +188,17 @@
status_t
-AllocationBlockGroup::Allocate(Transaction& transaction, uint32 start,
+AllocationBlockGroup::Allocate(Transaction& transaction, fsblock_t _start,
uint32 length)
{
+ uint32 start = _start - fStart;
TRACE("AllocationBlockGroup::Allocate(%ld,%ld)\n", start, length);
+ if (length == 0)
+ return B_OK;
+
uint32 end = start + length;
if (end > fNumBits)
- return B_BAD_DATA;
+ return B_BAD_VALUE;
_LockInTransaction(transaction);
@@ -263,9 +268,8 @@
return B_OK;
uint32 end = start + length;
-
if (end > fNumBits)
- return B_BAD_DATA;
+ return B_BAD_VALUE;
_LockInTransaction(transaction);
@@ -342,17 +346,17 @@
}
-uint32
+fsblock_t
AllocationBlockGroup::Start() const
{
return fStart;
}
-uint32
+fsblock_t
AllocationBlockGroup::LargestStart() const
{
- return fLargestStart;
+ return fStart + fLargestStart;
}
@@ -457,7 +461,7 @@
fNumBlocks = fVolume->NumBlocks();
TRACE("BlockAllocator::Initialize(): blocks per group: %lu, block
groups: "
- "%lu, first block: %lu, num blocks: %lu\n", fBlocksPerGroup,
+ "%lu, first block: %llu, num blocks: %llu\n", fBlocksPerGroup,
fNumGroups, fFirstBlock, fNumBlocks);
fGroups = new(std::nothrow) AllocationBlockGroup[fNumGroups];
@@ -486,7 +490,7 @@
status_t
BlockAllocator::AllocateBlocks(Transaction& transaction, uint32 minimum,
- uint32 maximum, uint32& blockGroup, off_t& start, uint32& length)
+ uint32 maximum, uint32& blockGroup, fsblock_t& start, uint32& length)
{
TRACE("BlockAllocator::AllocateBlocks()\n");
MutexLocker lock(fLock);
@@ -496,7 +500,7 @@
"max: %lu, block group: %lu, start: %llu, num groups: %lu\n",
transaction.ID(), minimum, maximum, blockGroup, start,
fNumGroups);
- off_t bestStart = 0;
+ fsblock_t bestStart = 0;
uint32 bestLength = 0;
uint32 bestGroup = 0;
@@ -567,10 +571,12 @@
status_t
BlockAllocator::Allocate(Transaction& transaction, Inode* inode,
- off_t numBlocks, uint32 minimum, off_t& start, uint32& allocated)
+ off_t numBlocks, uint32 minimum, fsblock_t& start, uint32& allocated)
{
if (numBlocks <= 0)
return B_ERROR;
+ if (start > fNumBlocks)
+ return B_BAD_VALUE;
uint32 group = inode->ID() / fVolume->InodesPerGroup();
uint32 preferred = 0;
@@ -644,28 +650,32 @@
status_t
-BlockAllocator::Free(Transaction& transaction, off_t start, uint32 length)
+BlockAllocator::Free(Transaction& transaction, fsblock_t start, uint32 length)
{
TRACE("BlockAllocator::Free(%llu, %lu)\n", start, length);
MutexLocker lock(fLock);
if (start <= fFirstBlock) {
panic("Trying to free superblock!\n");
- return B_BAD_DATA;
+ return B_BAD_VALUE;
}
if (length == 0)
return B_OK;
+ if (start > fNumBlocks || length > fNumBlocks)
+ return B_BAD_VALUE;
- TRACE("BlockAllocator::Free(): first block: %lu, blocks per group:
%lu\n",
+ TRACE("BlockAllocator::Free(): first block: %llu, blocks per group:
%lu\n",
fFirstBlock, fBlocksPerGroup);
start -= fFirstBlock;
off_t end = start + length - 1;
uint32 group = start / fBlocksPerGroup;
- if (group >= fNumGroups)
- panic("BlockAllocator::Free() group %ld too big (fNumGroups
%ld)\n", group, fNumGroups);
+ if (group >= fNumGroups) {
+ panic("BlockAllocator::Free() group %ld too big (fNumGroups
%ld)\n",
+ group, fNumGroups);
+ }
uint32 lastGroup = end / fBlocksPerGroup;
start = start % fBlocksPerGroup;
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.h
2010-12-18 16:26:39 UTC (rev 39886)
@@ -8,8 +8,10 @@
#ifndef BLOCKALLOCATOR_H
#define BLOCKALLOCATOR_H
+
#include <lock.h>
+#include "ext2.h"
#include "Transaction.h"
@@ -27,11 +29,11 @@
status_t AllocateBlocks(Transaction& transaction,
uint32 minimum, uint32
maximum, uint32& blockGroup,
- off_t& start, uint32&
length);
+ fsblock_t& start,
uint32& length);
status_t Allocate(Transaction& transaction,
Inode* inode,
- off_t numBlocks, uint32
minimum, off_t& start,
+ off_t numBlocks, uint32
minimum, fsblock_t& start,
uint32& length);
- status_t Free(Transaction& transaction, off_t
start,
+ status_t Free(Transaction& transaction,
fsblock_t start,
uint32 length);
uint32 FreeBlocks();
@@ -45,9 +47,9 @@
AllocationBlockGroup* fGroups;
uint32 fBlocksPerGroup;
- uint32 fNumBlocks;
+ fsblock_t fNumBlocks;
uint32 fNumGroups;
- uint32 fFirstBlock;
+ fsblock_t fFirstBlock;
};
#endif // BLOCKALLOCATOR_H
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.cpp
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.cpp
2010-12-18 16:26:39 UTC (rev 39886)
@@ -53,7 +53,7 @@
status_t
-DataStream::FindBlock(off_t offset, off_t& block, uint32 *_count)
+DataStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
{
uint32 index = offset >> fVolume->BlockShift();
@@ -377,8 +377,7 @@
if (fAllocated == 0) {
uint32 blockGroup = (fAllocatedPos - fFirstBlock)
/ fVolume->BlocksPerGroup();
- fAllocatedPos %= fVolume->BlocksPerGroup();
-
+
status_t status = fVolume->AllocateBlocks(transaction, 1,
fWaiting,
blockGroup, fAllocatedPos, fAllocated);
if (status != B_OK) {
@@ -387,7 +386,6 @@
}
fWaiting -= fAllocated;
- fAllocatedPos += fVolume->BlocksPerGroup() * blockGroup +
fFirstBlock;
TRACE("DataStream::_GetBlock(): newAllocated: %lu, newpos:
%llu,"
"newwaiting: %lu\n", fAllocated, fAllocatedPos,
fWaiting);
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.h
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DataStream.h
2010-12-18 16:26:39 UTC (rev 39886)
@@ -8,6 +8,7 @@
#ifndef DATASTREAM_H
#define DATASTREAM_H
+
#include "ext2.h"
#include "Transaction.h"
@@ -22,7 +23,7 @@
off_t size);
~DataStream();
- status_t FindBlock(off_t offset, off_t& block,
+ status_t FindBlock(off_t offset, fsblock_t& block,
uint32 *_count = NULL);
status_t Enlarge(Transaction& transaction, off_t&
numBlocks);
status_t Shrink(Transaction& transaction, off_t&
numBlocks);
@@ -82,7 +83,7 @@
uint32 fFirstBlock;
uint32 fAllocated;
- off_t fAllocatedPos;
+ fsblock_t fAllocatedPos;
uint32 fWaiting;
uint32 fFreeStart;
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.cpp
2010-12-18 16:26:39 UTC (rev 39886)
@@ -517,7 +517,7 @@
return B_NO_MEMORY;
ArrayDeleter<uint8> bufferDeleter(buffer);
- off_t firstPhysicalBlock = 0;
+ fsblock_t firstPhysicalBlock = 0;
// Prepare block to hold the first half of the entries and fill the
buffer
CachedBlock cachedFirst(fVolume);
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/DirectoryIterator.h
2010-12-18 16:26:39 UTC (rev 39886)
@@ -6,6 +6,8 @@
#define DIRECTORY_ITERATOR_H
+#include "ext2.h"
+
#include <SupportDefs.h>
#include "Transaction.h"
@@ -69,7 +71,7 @@
uint32 fNumBlocks;
uint32 fLogicalBlock;
- off_t fPhysicalBlock;
+ fsblock_t fPhysicalBlock;
uint32 fDisplacement;
uint32 fPreviousDisplacement;
Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.cpp
(rev 0)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.cpp
2010-12-18 16:26:39 UTC (rev 39886)
@@ -0,0 +1,510 @@
+/*
+ * Copyright 2001-2010, Haiku Inc. All rights reserved.
+ * This file may be used under the terms of the MIT License.
+ *
+ * Authors:
+ * Jérôme Duval
+ */
+
+
+#include "ExtentStream.h"
+
+#include <string.h>
+
+#include "CachedBlock.h"
+#include "Volume.h"
+
+
+#undef ASSERT
+//#define TRACE_EXT2
+#ifdef TRACE_EXT2
+# define TRACE(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x)
+# define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x
"\n"); }
+#else
+# define TRACE(x...) ;
+# define ASSERT(x) ;
+#endif
+#define ERROR(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x)
+
+
+ExtentStream::ExtentStream(Volume* volume, ext2_extent_stream* stream,
+ off_t size)
+ :
+ fVolume(volume),
+ fStream(stream),
+ fFirstBlock(volume->FirstDataBlock()),
+ fAllocatedPos(fFirstBlock),
+ fSize(size)
+{
+ fNumBlocks = size == 0 ? 0 : ((size - 1) >> fVolume->BlockShift()) + 1;
+}
+
+
+ExtentStream::~ExtentStream()
+{
+}
+
+
+status_t
+ExtentStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
+{
+ fileblock_t index = offset >> fVolume->BlockShift();
+ TRACE("FindBlock(%lld, %lld)\n", offset, index);
+
+ if (offset >= fSize) {
+ TRACE("FindBlock: offset larger than inode size\n");
+ return B_ENTRY_NOT_FOUND;
+ }
+
+ ext2_extent_stream *stream = fStream;
+ if (!stream->extent_header.IsValid())
+ panic("ExtentStream::FindBlock() invalid header\n");
+
+ CachedBlock cached(fVolume);
+ while (stream->extent_header.Depth() != 0) {
+ TRACE("FindBlock() depth %d\n",
+ stream->extent_header.Depth());
+ int32 i = 1;
+ while (i < stream->extent_header.NumEntries()
+ && stream->extent_index[i].LogicalBlock() <= index) {
+ i++;
+ }
+ TRACE("FindBlock() getting index %ld at %lld\n", i - 1,
+ stream->extent_index[i - 1].PhysicalBlock());
+ stream = (ext2_extent_stream *)cached.SetTo(
+ stream->extent_index[i - 1].PhysicalBlock());
+ if (!stream->extent_header.IsValid())
+ panic("ExtentStream::FindBlock() invalid header\n");
+ }
+
+ for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
+ if (stream->extent_entries[i].LogicalBlock() > index) {
+ // sparse block
+ TRACE("FindBlock() sparse block index %lld at %ld\n",
index,
+ stream->extent_entries[i].LogicalBlock());
+ block = 0xffffffff;
+ return B_OK;
+ }
+ fileblock_t diff = index -
stream->extent_entries[i].LogicalBlock();
+ if (diff < stream->extent_entries[i].Length()) {
+ block = stream->extent_entries[i].PhysicalBlock() +
diff;
+ if (_count)
+ *_count = stream->extent_entries[i].Length() -
diff;
+ TRACE("FindBlock(offset %lld): %lld %ld\n", offset,
+ block, _count != NULL ? *_count : 1);
+ return B_OK;
+ }
+ }
+
+ return B_ERROR;
+}
+
+
+status_t
+ExtentStream::Enlarge(Transaction& transaction, off_t& numBlocks)
+{
+ TRACE("Enlarge(): current size: %llu, target size: %llu\n",
+ fNumBlocks, numBlocks);
+
+ off_t targetBlocks = numBlocks;
+ numBlocks = targetBlocks - fNumBlocks;
+ uint32 allocated = 0;
+
+ while (fNumBlocks < targetBlocks) {
+ // allocate new blocks
+ uint32 blockGroup = (fAllocatedPos - fFirstBlock)
+ / fVolume->BlocksPerGroup();
+
+ if (allocated == 0) {
+ status_t status = fVolume->AllocateBlocks(transaction,
1,
+ targetBlocks - fNumBlocks, blockGroup,
fAllocatedPos,
+ allocated);
+ if (status != B_OK) {
+ ERROR("Enlarge(): AllocateBlocks() failed()\n");
+ return status;
+ }
+ }
+
+ ASSERT(_CheckBlock(fStream, fAllocatedPos) == B_OK);
+
+ ext2_extent_stream *stream = fStream;
+ fsblock_t path[stream->extent_header.Depth()];
+
+ // search for the leaf
+ CachedBlock cached(fVolume);
+ int32 level = -1;
+ for (; stream->extent_header.Depth() != 0;) {
+ if (stream->extent_header.NumEntries() == 0)
+ panic("stream->extent_header.NumEntries() ==
0\n");
+ int32 lastIndex = stream->extent_header.NumEntries() -
1;
+ TRACE("Enlarge() depth %d\n",
stream->extent_header.Depth());
+ TRACE("Enlarge() getting index %ld at %lld\n",
lastIndex,
+
stream->extent_index[lastIndex].PhysicalBlock());
+ path[++level] =
stream->extent_index[lastIndex].PhysicalBlock();
+ stream = (ext2_extent_stream
*)cached.SetTo(path[level]);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ }
+
+ // check if the new extent is adjacent
+ if (stream->extent_header.NumEntries() > 0) {
+ ext2_extent_entry &last = stream->extent_entries[
+ stream->extent_header.NumEntries() - 1];
+ TRACE("Enlarge() last %lld allocatedPos %lld\n",
+ last.PhysicalBlock() + last.Length(),
fAllocatedPos);
+ if (last.PhysicalBlock() + last.Length() ==
fAllocatedPos
+ && (last.Length() + allocated) <= 0xffff) {
+ if (stream != fStream) {
+ stream = (ext2_extent_stream
*)cached.SetToWritable(
+ transaction,
cached.BlockNumber());
+ if (stream == NULL)
+ return B_IO_ERROR;
+ }
+
stream->extent_entries[stream->extent_header.NumEntries() - 1]
+ .SetLength(last.Length() + allocated);
+ fNumBlocks += allocated;
+ allocated = 0;
+ TRACE("Enlarge() entry extended\n");
+ continue;
+ }
+ }
+
+ if (stream->extent_header.NumEntries()
+ >= stream->extent_header.MaxEntries()) {
+ TRACE("Enlarge() adding leaf and indexes at depth %d
level %ld\n",
+ stream->extent_header.Depth(), level);
+ // try to add a leaf and indexes
+ while (--level >= 0) {
+ stream = (ext2_extent_stream
*)cached.SetTo(path[level]);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ if (stream->extent_header.NumEntries()
+ < stream->extent_header.MaxEntries()) {
+ break;
+ }
+ TRACE("Enlarge() going up from level %ld\n",
level);
+ }
+
+ if (level < 0 && fStream->extent_header.NumEntries()
+ >= fStream->extent_header.MaxEntries())
{
+ TRACE("Enlarge() add a level, increment root
depth\n");
+ fsblock_t newBlock =
fStream->extent_index[0].PhysicalBlock();
+ uint32 _allocated;
+ status_t status =
fVolume->AllocateBlocks(transaction, 1, 1,
+ blockGroup, newBlock, _allocated);
+ if (status != B_OK) {
+ ERROR("Enlarge() AllocateBlocks()
failed()\n");
+ return status;
+ }
+ ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
+ TRACE("Enlarge() move root to block %lld\n",
newBlock);
+ numBlocks++;
+ stream = (ext2_extent_stream
*)cached.SetToWritable(
+ transaction, newBlock);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ ASSERT(fStream->extent_header.IsValid());
+ memcpy(stream, fStream,
sizeof(ext2_extent_stream));
+
fStream->extent_header.SetDepth(stream->extent_header.Depth()
+ + 1);
+ TRACE("Enlarge() new root depth %d\n",
+ fStream->extent_header.Depth());
+ fStream->extent_header.SetNumEntries(1);
+ fStream->extent_index[0].SetLogicalBlock(0);
+
fStream->extent_index[0].SetPhysicalBlock(newBlock);
+
stream->extent_header.SetMaxEntries((fVolume->BlockSize()
+ - sizeof(ext2_extent_header)) /
sizeof(ext2_extent_index));
+ ASSERT(stream->extent_header.IsValid());
+
+ ASSERT(Check());
+ continue;
+ }
+
+ if (level < 0)
+ stream = fStream;
+
+ uint16 depth = stream->extent_header.Depth();
+ while (depth > 1) {
+ TRACE("Enlarge() adding an index block at depth
%d\n", depth);
+ fsblock_t newBlock = path[level];
+ uint32 _allocated;
+ status_t status =
fVolume->AllocateBlocks(transaction, 1, 1,
+ blockGroup, newBlock, _allocated);
+ if (status != B_OK) {
+ ERROR("Enlarge(): AllocateBlocks()
failed()\n");
+ return status;
+ }
+ ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
+ numBlocks++;
+ int32 index =
stream->extent_header.NumEntries();
+
stream->extent_index[index].SetLogicalBlock(fNumBlocks);
+
stream->extent_index[index].SetPhysicalBlock(newBlock);
+ stream->extent_header.SetNumEntries(index + 1);
+ path[level++] = newBlock;
+
+ depth = stream->extent_header.Depth() - 1;
+ TRACE("Enlarge() init index block %lld at depth
%d\n",
+ newBlock, depth);
+ stream = (ext2_extent_stream
*)cached.SetToWritable(
+ transaction, newBlock);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ stream->extent_header.magic = EXT2_EXTENT_MAGIC;
+ stream->extent_header.SetNumEntries(0);
+
stream->extent_header.SetMaxEntries((fVolume->BlockSize()
+ - sizeof(ext2_extent_header)) /
sizeof(ext2_extent_index));
+ stream->extent_header.SetDepth(depth);
+ stream->extent_header.SetGeneration(0);
+
+ ASSERT(Check());
+ }
+
+ TRACE("Enlarge() depth %d level %ld\n",
+ stream->extent_header.Depth(), level);
+
+ if (stream->extent_header.Depth() == 1) {
+ TRACE("Enlarge() adding an entry block at depth
%d level %ld\n",
+ depth, level);
+ fsblock_t newBlock;
+ if (level >= 0)
+ newBlock = path[level];
+ else
+ newBlock =
fStream->extent_index[0].PhysicalBlock();
+ uint32 _allocated;
+ status_t status =
fVolume->AllocateBlocks(transaction, 1, 1,
+ blockGroup, newBlock, _allocated);
+ if (status != B_OK) {
+ ERROR("Enlarge(): AllocateBlocks()
failed()\n");
+ return status;
+ }
+
+ ASSERT(_CheckBlock(fStream, newBlock) == B_OK);
+ numBlocks++;
+ int32 index =
stream->extent_header.NumEntries();
+
stream->extent_index[index].SetLogicalBlock(fNumBlocks);
+
stream->extent_index[index].SetPhysicalBlock(newBlock);
+ stream->extent_header.SetNumEntries(index + 1);
+
+ TRACE("Enlarge() init entry block %lld at depth
%d\n",
+ newBlock, depth);
+ stream = (ext2_extent_stream
*)cached.SetToWritable(
+ transaction, newBlock);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ stream->extent_header.magic = EXT2_EXTENT_MAGIC;
+ stream->extent_header.SetNumEntries(0);
+
stream->extent_header.SetMaxEntries((fVolume->BlockSize()
+ - sizeof(ext2_extent_header)) /
sizeof(ext2_extent_entry));
+ stream->extent_header.SetDepth(0);
+ stream->extent_header.SetGeneration(0);
+ ASSERT(Check());
+ }
+ }
+
+ // add a new entry
+ TRACE("Enlarge() add entry %lld\n", fAllocatedPos);
+ if (stream != fStream) {
+ stream = (ext2_extent_stream *)cached.SetToWritable(
+ transaction, cached.BlockNumber());
+ if (stream == NULL)
+ return B_IO_ERROR;
+ }
+ int32 index = stream->extent_header.NumEntries();
+ stream->extent_entries[index].SetLogicalBlock(fNumBlocks);
+ stream->extent_entries[index].SetLength(allocated);
+ stream->extent_entries[index].SetPhysicalBlock(fAllocatedPos);
+ stream->extent_header.SetNumEntries(index + 1);
+ TRACE("Enlarge() entry added at index %ld\n", index);
+ ASSERT(stream->extent_header.IsValid());
+
+ fNumBlocks += allocated;
+ allocated = 0;
+ }
+
+ return B_OK;
+}
+
+
+status_t
+ExtentStream::Shrink(Transaction& transaction, off_t& numBlocks)
+{
+ TRACE("DataStream::Shrink(): current size: %llu, target size: %llu\n",
+ fNumBlocks, numBlocks);
+
+ off_t targetBlocks = numBlocks;
+ numBlocks = fNumBlocks - targetBlocks;
+
+ while (targetBlocks < fNumBlocks) {
+ ext2_extent_stream *stream = fStream;
+ fsblock_t path[stream->extent_header.Depth()];
+
+ // search for the leaf
+ CachedBlock cached(fVolume);
+ int32 level = -1;
+ for (; stream->extent_header.Depth() != 0;) {
+ if (stream->extent_header.NumEntries() == 0)
+ panic("stream->extent_header.NumEntries() ==
0\n");
+ int32 lastIndex = stream->extent_header.NumEntries() -
1;
+ TRACE("Shrink() depth %d\n",
stream->extent_header.Depth());
+ TRACE("Shrink() getting index %ld at %lld\n", lastIndex,
+
stream->extent_index[lastIndex].PhysicalBlock());
+ path[++level] =
stream->extent_index[lastIndex].PhysicalBlock();
+ stream = (ext2_extent_stream
*)cached.SetToWritable(transaction,
+ path[level]);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ if (!stream->extent_header.IsValid())
+ panic("Shrink() invalid header\n");
+ }
+
+ int32 index = stream->extent_header.NumEntries() - 1;
+ status_t status = B_OK;
+ while (index >= 0 && targetBlocks < fNumBlocks) {
+ ext2_extent_entry &last = stream->extent_entries[index];
+ if (last.LogicalBlock() + last.Length() < targetBlocks)
{
+ status = B_BAD_DATA;
+ break;
+ }
+ uint16 length = min_c(last.Length(), fNumBlocks -
targetBlocks);
+ fsblock_t block = last.PhysicalBlock() + last.Length()
- length;
+ TRACE("Shrink() free block %lld length %d\n", block,
length);
+ status = fVolume->FreeBlocks(transaction, block,
length);
+ if (status != B_OK)
+ break;
+ fNumBlocks -= length;
+ stream->extent_entries[index].SetLength(last.Length() -
length);
+ TRACE("Shrink() new length for %ld: %d\n", index,
last.Length());
+ if (last.Length() != 0)
+ break;
+ index--;
+ TRACE("Shrink() next index: %ld\n", index);
+ }
+ TRACE("Shrink() new entry count: %ld\n", index + 1);
+ stream->extent_header.SetNumEntries(index + 1);
+ ASSERT(Check());
+
+ if (status != B_OK)
+ return status;
+
+ while (stream != fStream && stream->extent_header.NumEntries()
== 0) {
+ TRACE("Shrink() empty leaf at depth %d\n",
+ stream->extent_header.Depth());
+ level--;
+ if (level >= 0) {
+ stream = (ext2_extent_stream
*)cached.SetToWritable(
+ transaction, path[level]);
+ if (stream == NULL)
+ return B_IO_ERROR;
+ } else
+ stream = fStream;
+ if (!stream->extent_header.IsValid())
+ panic("Shrink() invalid header\n");
+ uint16 index = stream->extent_header.NumEntries() - 1;
+ ext2_extent_index &last = stream->extent_index[index];
+ if (last.PhysicalBlock() != path[level + 1])
+ panic("Shrink() last.PhysicalBlock() !=
path[level + 1]\n");
+ status = fVolume->FreeBlocks(transaction,
last.PhysicalBlock(), 1);
+ if (status != B_OK)
+ return status;
+ numBlocks++;
+ stream->extent_header.SetNumEntries(index);
+ TRACE("Shrink() new entry count: %d\n", index);
+ }
+ if (stream == fStream && stream->extent_header.NumEntries() ==
0)
+ stream->extent_header.SetDepth(0);
+
+ ASSERT(Check());
+ }
+
+ return B_OK;
+}
+
+
+void
+ExtentStream::Init()
+{
+ fStream->extent_header.magic = EXT2_EXTENT_MAGIC;
+ fStream->extent_header.SetNumEntries(0);
+ fStream->extent_header.SetMaxEntries(4);
+ fStream->extent_header.SetDepth(0);
+ fStream->extent_header.SetGeneration(0);
+}
+
+
+status_t
+ExtentStream::_Check(ext2_extent_stream *stream, fileblock_t &block)
+{
+ if (!stream->extent_header.IsValid()) {
+ panic("_Check() invalid header\n");
+ return B_BAD_VALUE;
+ }
+ if (stream->extent_header.Depth() == 0) {
+ for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
+ ext2_extent_entry &entry = stream->extent_entries[i];
+ if (entry.LogicalBlock() < block) {
+ panic("_Check() entry %ld %lld %ld\n", i, block,
+ entry.LogicalBlock());
+ return B_BAD_VALUE;
+ }
+ block = entry.LogicalBlock() + entry.Length();
+ }
+ return B_OK;
+ }
+
+ CachedBlock cached(fVolume);
+ for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
+ ext2_extent_index &index = stream->extent_index[i];
+ if (index.LogicalBlock() < block) {
+ panic("_Check() index %ld %lld %ld\n", i, block,
+ index.LogicalBlock());
+ return B_BAD_VALUE;
+ }
+ ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
+ index.PhysicalBlock());
+ if (child->extent_header.Depth() !=
(stream->extent_header.Depth() - 1)
+ || _Check(child, block) != B_OK)
+ return B_BAD_VALUE;
+ }
+ return B_OK;
+}
+
+
+bool
+ExtentStream::Check()
+{
+ fileblock_t block = 0;
+ return _Check(fStream, block) == B_OK;
+}
+
+
+status_t
+ExtentStream::_CheckBlock(ext2_extent_stream *stream, fsblock_t block)
+{
+ if (stream->extent_header.Depth() == 0) {
+ for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
+ ext2_extent_entry &entry = stream->extent_entries[i];
+ if (entry.PhysicalBlock() <= block
+ && (entry.PhysicalBlock() + entry.Length()) >
block) {
+ panic("_CheckBlock() entry %ld %lld %lld %d\n",
i, block,
+ entry.PhysicalBlock(), entry.Length());
+ return B_BAD_VALUE;
+ }
+ }
+ return B_OK;
+ }
+
+ CachedBlock cached(fVolume);
+ for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) {
+ ext2_extent_index &index = stream->extent_index[i];
+ if (index.PhysicalBlock() == block) {
+ panic("_CheckBlock() index %ld %lld\n", i, block);
+ return B_BAD_VALUE;
+ }
+ ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo(
+ index.PhysicalBlock());
+ if (child->extent_header.Depth() !=
(stream->extent_header.Depth() - 1)
+ || _CheckBlock(child, block) != B_OK)
+ return B_BAD_VALUE;
+ }
+ return B_OK;
+}
Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.h
(rev 0)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/ExtentStream.h
2010-12-18 16:26:39 UTC (rev 39886)
@@ -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:
+ * Jérôme Duval
+ */
+#ifndef EXTENTSTREAM_H
+#define EXTENTSTREAM_H
+
+#include "ext2.h"
+#include "Transaction.h"
+
+
+class Volume;
+
+
+class ExtentStream
+{
+public:
+ ExtentStream(Volume* volume,
ext2_extent_stream* stream,
+ off_t size);
+ ~ExtentStream();
+
+ status_t FindBlock(off_t offset, fsblock_t& block,
+ uint32 *_count = NULL);
+ status_t Enlarge(Transaction& transaction, off_t&
numBlocks);
+ status_t Shrink(Transaction& transaction, off_t&
numBlocks);
+ void Init();
+
+ bool Check();
+
+private:
+ status_t _Check(ext2_extent_stream *stream, fileblock_t
&block);
+ status_t _CheckBlock(ext2_extent_stream *stream,
fsblock_t block);
+
+ Volume* fVolume;
+ ext2_extent_stream* fStream;
+ fsblock_t fFirstBlock;
+
+ fsblock_t fAllocatedPos;
+
+ off_t fNumBlocks;
+ off_t fSize;
+};
+
+#endif // EXTENTSTREAM_H
+
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp 2010-12-17
23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTree.cpp 2010-12-18
16:26:39 UTC (rev 39886)
@@ -84,7 +84,7 @@
status_t
HTree::PrepareForHash()
{
- off_t blockNum;
+ fsblock_t blockNum;
status_t status = fDirectory->FindBlock(0, blockNum);
if (status != B_OK)
return status;
@@ -115,7 +115,7 @@
return _FallbackToLinearIteration(iterator);
}
- off_t blockNum;
+ fsblock_t blockNum;
status_t status = fDirectory->FindBlock(0, blockNum);
if (status != B_OK)
return _FallbackToLinearIteration(iterator);
Modified:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
2010-12-18 16:26:39 UTC (rev 39886)
@@ -189,7 +189,7 @@
TRACE("HTreeEntryIterator::Lookup(): Creating a HTree entry iterator "
"starting at block: %lu, hash: 0x%lX\n", start->Block(),
start->Hash());
- off_t blockNum;
+ fsblock_t blockNum;
status_t status = fDirectory->FindBlock(start->Block() * fBlockSize,
blockNum);
if (status != B_OK)
@@ -322,7 +322,7 @@
panic("Splitting a HTree node required, but isn't yet fully "
"supported\n");
- off_t physicalBlock;
+ fsblock_t physicalBlock;
status_t status = fDirectory->FindBlock(newBlocksPos,
physicalBlock);
if (status != B_OK)
return status;
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
2010-12-17 23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
2010-12-18 16:26:39 UTC (rev 39886)
@@ -53,7 +53,7 @@
uint16 fCurrentEntry;
uint32 fBlockSize;
- off_t fBlockNum;
+ fsblock_t fBlockNum;
HTreeEntryIterator* fParent;
HTreeEntryIterator* fChild;
Modified: haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp 2010-12-17
23:17:21 UTC (rev 39885)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/Inode.cpp 2010-12-18
16:26:39 UTC (rev 39886)
@@ -13,6 +13,7 @@
#include "CachedBlock.h"
#include "DataStream.h"
#include "DirectoryIterator.h"
+#include "ExtentStream.h"
#include "HTree.h"
#include "Utility.h"
@@ -224,8 +225,12 @@
status_t
-Inode::FindBlock(off_t offset, off_t& block, uint32 *_count)
+Inode::FindBlock(off_t offset, fsblock_t& block, uint32 *_count)
{
+ if (Flags() & EXT2_INODE_EXTENTS) {
+ ExtentStream stream(fVolume, &fNode.extent_stream, Size());
+ return stream.FindBlock(offset, block, _count);
+ }
DataStream stream(fVolume, &fNode.stream, Size());
return stream.FindBlock(offset, block, _count);
}
@@ -407,9 +412,14 @@
if (status != B_OK)
return status;
- off_t blockNum;
- DataStream stream(fVolume, &fNode.stream, Size());
- status = stream.FindBlock(0, blockNum);
+ fsblock_t blockNum;
+ if (Flags() & EXT2_INODE_EXTENTS) {
+ ExtentStream stream(fVolume, &fNode.extent_stream, Size());
+ status = stream.FindBlock(0, blockNum);
+ } else {
+ DataStream stream(fVolume, &fNode.stream, Size());
+ status = stream.FindBlock(0, blockNum);
+ }
if (status != B_OK)
return status;
@@ -613,6 +623,14 @@
inode->SetAccessTime(×pec);
inode->SetCreationTime(×pec);
inode->SetModificationTime(×pec);
+ node.SetFlags(parent->Flags() & EXT2_INODE_INHERITED);
+ if (volume->HasExtentsFeature()
[... truncated: 563 lines follow ...]
Other related posts:
- » [haiku-commits] r39886 - haiku/trunk/src/add-ons/kernel/file_systems/ext2 - korli
