[haiku-commits] r37478 - in haiku/trunk/src/tests/system/kernel/file_corruption: . fs fs/userland
- From: ingo_weinhold@xxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Mon, 12 Jul 2010 15:21:43 +0200 (CEST)
Author: bonefish
Date: 2010-07-12 15:21:42 +0200 (Mon, 12 Jul 2010)
New Revision: 37478
Changeset: http://dev.haiku-os.org/changeset/37478
Added:
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Transaction.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Transaction.h
Modified:
haiku/trunk/src/tests/system/kernel/file_corruption/checksumfs.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Block.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Directory.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Directory.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Jamfile
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Node.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Node.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Volume.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/Volume.h
haiku/trunk/src/tests/system/kernel/file_corruption/fs/checksumfs.cpp
haiku/trunk/src/tests/system/kernel/file_corruption/fs/userland/Jamfile
Log:
* Added Transaction class which wraps a block cache transaction and performs
all other operations required to roll back a transaction. Transactions are
fully serialized -- due to limitations of our block cache and also to keep
things simple.
* Use a transaction for all write operations.
* Implemented the directory entry management code (a simple tree algorithm).
* Finished/implemented the FS hooks for directory entry lookup, directory
iteration, creation, and removal.
* Added non-persistent support for node access times.
* Set the user and group IDs on node creation.
* Added permission checks to several FS hooks.
* BlockAllocator::_Free(): The number of freed blocks was subtracted from
fFreeBlocks instead of added.
Modified: haiku/trunk/src/tests/system/kernel/file_corruption/checksumfs.h
===================================================================
--- haiku/trunk/src/tests/system/kernel/file_corruption/checksumfs.h
2010-07-12 11:51:41 UTC (rev 37477)
+++ haiku/trunk/src/tests/system/kernel/file_corruption/checksumfs.h
2010-07-12 13:21:42 UTC (rev 37478)
@@ -56,9 +56,17 @@
} _PACKED;
+static const uint32 kCheckSumFSMaxDirEntryTreeDepth = 24;
+
+struct checksumfs_dir_entry_tree {
+ uint16 depth;
+} _PACKED;
+
+
struct checksumfs_dir_entry_block {
uint16 entryCount;
- uint16 nameEnds[0]; // end (in-block) offsets of the names,
+ uint16 nameEnds[0]; // end offsets of the names (relative
to the
+ // start of the
first name),
// e.g.
nameEnds[0] == length of first name
// char names[]; // string of all (unterminated)
names,
// directly
follows the nameEnds array
Modified: haiku/trunk/src/tests/system/kernel/file_corruption/fs/Block.h
===================================================================
--- haiku/trunk/src/tests/system/kernel/file_corruption/fs/Block.h
2010-07-12 11:51:41 UTC (rev 37477)
+++ haiku/trunk/src/tests/system/kernel/file_corruption/fs/Block.h
2010-07-12 13:21:42 UTC (rev 37478)
@@ -8,6 +8,7 @@
#include <fs_cache.h>
+#include "Transaction.h"
#include "Volume.h"
@@ -25,30 +26,64 @@
Put();
}
+ void TransferFrom(Block& other)
+ {
+ Put();
+
+ fVolume = other.fVolume;
+ fData = other.fData;
+ fIndex = other.fIndex;
+ fWritable = other.fWritable;
+
+ other.fVolume = NULL;
+ other.fData = NULL;
+ }
+
bool GetReadable(Volume* volume, uint64 blockIndex)
{
Put();
return _Init(volume, blockIndex,
- block_cache_get(volume->BlockCache(), blockIndex));
+ block_cache_get(volume->BlockCache(), blockIndex),
false);
}
- bool GetWritable(Volume* volume, uint64 blockIndex)
+ bool GetWritable(Volume* volume, uint64 blockIndex,
+ Transaction& transaction)
{
Put();
return _Init(volume, blockIndex,
- block_cache_get_writable(volume->BlockCache(),
blockIndex, -1));
+ block_cache_get_writable(volume->BlockCache(),
blockIndex,
+ transaction.ID()),
+ true);
}
- bool GetZero(Volume* volume, uint64 blockIndex)
+ bool GetZero(Volume* volume, uint64 blockIndex, Transaction&
transaction)
{
Put();
return _Init(volume, blockIndex,
- block_cache_get_empty(volume->BlockCache(), blockIndex,
-1));
+ block_cache_get_empty(volume->BlockCache(), blockIndex,
+ transaction.ID()),
+ true);
}
+ status_t MakeWritable(Transaction& transaction)
+ {
+ if (fVolume == NULL)
+ return B_BAD_VALUE;
+ if (fWritable)
+ return B_OK;
+
+ status_t error =
block_cache_make_writable(fVolume->BlockCache(),
+ fIndex, transaction.ID());
+ if (error != B_OK)
+ return error;
+
+ fWritable = true;
+ return B_OK;
+ }
+
void Put()
{
if (fVolume != NULL) {
@@ -78,7 +113,8 @@
}
private:
- bool _Init(Volume* volume, uint64 blockIndex, const void* data)
+ bool _Init(Volume* volume, uint64 blockIndex, const void* data,
+ bool writable)
{
if (data == NULL)
return false;
@@ -86,6 +122,7 @@
fVolume = volume;
fData = const_cast<void*>(data);
fIndex = blockIndex;
+ fWritable = writable;
return true;
}
@@ -95,6 +132,7 @@
Volume* fVolume;
void* fData;
uint64 fIndex;
+ bool fWritable;
};
Modified:
haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.cpp
===================================================================
--- haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.cpp
2010-07-12 11:51:41 UTC (rev 37477)
+++ haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.cpp
2010-07-12 13:21:42 UTC (rev 37478)
@@ -77,7 +77,7 @@
status_t
-BlockAllocator::Initialize()
+BlockAllocator::Initialize(Transaction& transaction)
{
status_t error = Init(kCheckSumFSSuperBlockOffset / B_PAGE_SIZE + 1,
fTotalBlocks);
@@ -93,7 +93,7 @@
// clear the block bitmap
for (uint64 i = 0; i < fBitmapBlockCount; i++) {
Block block;
- if (!block.GetZero(fVolume, fBitmapBlock + i))
+ if (!block.GetZero(fVolume, fBitmapBlock + i, transaction))
return B_ERROR;
}
@@ -102,8 +102,10 @@
uint32 partialBitmapBlock = fTotalBlocks % kBlocksPerBitmapBlock;
if (partialBitmapBlock != 0) {
Block block;
- if (!block.GetZero(fVolume, fBitmapBlock + fBitmapBlockCount -
1))
+ if (!block.GetZero(fVolume, fBitmapBlock + fBitmapBlockCount -
1,
+ transaction)) {
return B_ERROR;
+ }
// set full uint32s
uint32* bits = (uint32*)block.Data();
@@ -121,7 +123,7 @@
uint32 partialGroup = fTotalBlocks % kBlocksPerGroup;
for (uint64 i = 0; i < fAllocationGroupCount; i++) {
Block block;
- if (!block.GetZero(fVolume, fAllocationGroupBlock + i))
+ if (!block.GetZero(fVolume, fAllocationGroupBlock + i,
transaction))
return B_ERROR;
uint16* counts = (uint16*)block.Data();
@@ -143,7 +145,7 @@
}
// mark all blocks we already use used
- error = AllocateExactly(0, fBitmapBlock + fBitmapBlockCount);
+ error = AllocateExactly(0, fBitmapBlock + fBitmapBlockCount,
transaction);
if (error != B_OK)
return error;
@@ -159,8 +161,8 @@
status_t
-BlockAllocator::Allocate(uint64 baseHint, uint64 count, uint64& _allocatedBase,
- uint64& _allocatedCount)
+BlockAllocator::Allocate(uint64 baseHint, uint64 count,
+ Transaction& transaction, uint64& _allocatedBase, uint64&
_allocatedCount)
{
MutexLocker locker(fLock);
dprintf("BlockAllocator::Allocate(%llu, %llu)\n", baseHint, count);
@@ -172,29 +174,32 @@
baseHint = 0;
// search from base hint to end
- status_t error = _Allocate(baseHint, fTotalBlocks, count,
&_allocatedBase,
- _allocatedCount);
+ status_t error = _Allocate(baseHint, fTotalBlocks, count, transaction,
+ &_allocatedBase, _allocatedCount);
if (error == B_OK || baseHint == 0)
return error;
// search from 0 to hint
- return _Allocate(0, baseHint, count, &_allocatedBase, _allocatedCount);
+ return _Allocate(0, baseHint, count, transaction, &_allocatedBase,
+ _allocatedCount);
}
status_t
-BlockAllocator::AllocateExactly(uint64 base, uint64 count)
+BlockAllocator::AllocateExactly(uint64 base, uint64 count,
+ Transaction& transaction)
{
MutexLocker locker(fLock);
dprintf("BlockAllocator::AllocateExactly(%llu, %llu)\n", base, count);
uint64 allocated;
- status_t error = _Allocate(base, fTotalBlocks, count, NULL, allocated);
+ status_t error = _Allocate(base, fTotalBlocks, count, transaction, NULL,
+ allocated);
if (error != B_OK)
return error;
if (allocated < count) {
- _Free(base, allocated);
+ _Free(base, allocated, transaction);
return B_BUSY;
}
@@ -203,14 +208,23 @@
status_t
-BlockAllocator::Free(uint64 base, uint64 count)
+BlockAllocator::Free(uint64 base, uint64 count, Transaction& transaction)
{
MutexLocker locker(fLock);
- return _Free(base, count);
+ return _Free(base, count, transaction);
}
+void
+BlockAllocator::ResetFreeBlocks(uint64 count)
+{
+ MutexLocker locker(fLock);
+
+ fFreeBlocks = count;
+}
+
+
/*! Allocates contiguous blocks.
Might allocate fewer block than requested. If no block could be
allocated
@@ -231,7 +245,7 @@
*/
status_t
BlockAllocator::_Allocate(uint64 base, uint64 searchEnd, uint64 count,
- uint64* _allocatedBase, uint64& _allocatedCount)
+ Transaction& transaction, uint64* _allocatedBase, uint64&
_allocatedCount)
{
ASSERT(base <= fTotalBlocks);
ASSERT(searchEnd <= fTotalBlocks);
@@ -249,7 +263,7 @@
uint32 allocated;
status_t error = _AllocateInGroup(base, searchEnd,
toAllocate,
- _allocatedBase, allocated);
+ transaction, _allocatedBase, allocated);
if (error == B_OK) {
fFreeBlocks -= toAllocate;
@@ -281,8 +295,8 @@
while (remaining > 0 && base < searchEnd) {
uint64 toAllocate = std::min(remaining, kBlocksPerGroup -
groupOffset);
uint32 allocated;
- status_t error = _AllocateInGroup(base, searchEnd, toAllocate,
NULL,
- allocated);
+ status_t error = _AllocateInGroup(base, searchEnd, toAllocate,
+ transaction, NULL, allocated);
if (error != B_OK)
break;
@@ -327,7 +341,7 @@
*/
status_t
BlockAllocator::_AllocateInGroup(uint64 base, uint64 searchEnd, uint32 count,
- uint64* _allocatedBase, uint32& _allocatedCount)
+ Transaction& transaction, uint64* _allocatedBase, uint32&
_allocatedCount)
{
dprintf("BlockAllocator::_AllocateInGroup(%llu, %lu)\n", base, count);
ASSERT(count <= kBlocksPerGroup);
@@ -338,7 +352,7 @@
Block block;
if (!block.GetWritable(fVolume,
- fAllocationGroupBlock + base / kBlocksPerGroup)) {
+ fAllocationGroupBlock + base / kBlocksPerGroup,
transaction)) {
return B_ERROR;
}
@@ -354,8 +368,8 @@
if (inBlockOffset != 0) {
if (counts[blockIndex] < kBlocksPerBitmapBlock) {
uint32 allocated;
- if (_AllocateInBitmapBlock(base, count,
_allocatedBase,
- allocated) == B_OK) {
+ if (_AllocateInBitmapBlock(base, count,
transaction,
+ _allocatedBase, allocated) ==
B_OK) {
if (inBlockOffset + allocated <
kBlocksPerBitmapBlock
|| allocated == remaining) {
_allocatedCount = allocated;
@@ -407,7 +421,7 @@
kBlocksPerBitmapBlock - inBlockOffset);
uint32 allocated;
- status_t error = _AllocateInBitmapBlock(base, toAllocate,
+ status_t error = _AllocateInBitmapBlock(base, toAllocate,
transaction,
_allocatedBase, allocated);
if (error != B_OK)
break;
@@ -453,7 +467,7 @@
*/
status_t
BlockAllocator::_AllocateInBitmapBlock(uint64 base, uint32 count,
- uint64* _allocatedBase, uint32& _allocatedCount)
+ Transaction& transaction, uint64* _allocatedBase, uint32&
_allocatedCount)
{
dprintf("BlockAllocator::_AllocateInBitmapBlock(%llu, %lu)\n", base, count);
ASSERT(count <= kBlocksPerBitmapBlock);
@@ -461,7 +475,7 @@
Block block;
if (!block.GetWritable(fVolume,
- fBitmapBlock + base / kBlocksPerBitmapBlock)) {
+ fBitmapBlock + base / kBlocksPerBitmapBlock,
transaction)) {
return B_ERROR;
}
@@ -546,7 +560,7 @@
status_t
-BlockAllocator::_Free(uint64 base, uint64 count)
+BlockAllocator::_Free(uint64 base, uint64 count, Transaction& transaction)
{
if (count == 0)
return B_OK;
@@ -561,11 +575,11 @@
while (remaining > 0) {
uint64 toFree = std::min(remaining, kBlocksPerGroup -
groupOffset);
- status_t error = _FreeInGroup(base, toFree);
+ status_t error = _FreeInGroup(base, toFree, transaction);
if (error != B_OK)
return error;
- fFreeBlocks -= toFree;
+ fFreeBlocks += toFree;
remaining -= toFree;
base += toFree;
groupOffset = 0;
@@ -576,7 +590,8 @@
status_t
-BlockAllocator::_FreeInGroup(uint64 base, uint32 count)
+BlockAllocator::_FreeInGroup(uint64 base, uint32 count,
+ Transaction& transaction)
{
if (count == 0)
return B_OK;
@@ -587,7 +602,7 @@
Block block;
if (!block.GetWritable(fVolume,
- fAllocationGroupBlock + base / kBlocksPerGroup)) {
+ fAllocationGroupBlock + base / kBlocksPerGroup,
transaction)) {
return B_ERROR;
}
@@ -604,7 +619,7 @@
if (counts[blockIndex] + toFree > kBlocksPerBitmapBlock)
return B_BAD_VALUE;
- status_t error = _FreeInBitmapBlock(base, toFree);
+ status_t error = _FreeInBitmapBlock(base, toFree, transaction);
if (error != B_OK)
return error;
@@ -620,7 +635,8 @@
status_t
-BlockAllocator::_FreeInBitmapBlock(uint64 base, uint32 count)
+BlockAllocator::_FreeInBitmapBlock(uint64 base, uint32 count,
+ Transaction& transaction)
{
dprintf("BlockAllocator::_FreeInBitmapBlock(%llu, %lu)\n", base, count);
ASSERT(count <= kBlocksPerBitmapBlock);
@@ -628,7 +644,7 @@
Block block;
if (!block.GetWritable(fVolume,
- fBitmapBlock + base / kBlocksPerBitmapBlock)) {
+ fBitmapBlock + base / kBlocksPerBitmapBlock,
transaction)) {
return B_ERROR;
}
Modified:
haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.h
===================================================================
--- haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.h
2010-07-12 11:51:41 UTC (rev 37477)
+++ haiku/trunk/src/tests/system/kernel/file_corruption/fs/BlockAllocator.h
2010-07-12 13:21:42 UTC (rev 37478)
@@ -9,6 +9,7 @@
#include <lock.h>
+struct Transaction;
struct Volume;
@@ -22,29 +23,40 @@
uint64 FreeBlocks() const
{ return fFreeBlocks; }
status_t Init(uint64
blockBitmap, uint64 freeBlocks);
- status_t Initialize();
+ status_t Initialize(Transaction&
transaction);
status_t Allocate(uint64
baseHint, uint64 count,
+
Transaction& transaction,
uint64&
_allocatedBase,
uint64&
_allocatedCount);
status_t AllocateExactly(uint64
base,
- uint64
count);
- status_t Free(uint64 base,
uint64 count);
+ uint64
count, Transaction& transaction);
+ status_t Free(uint64 base,
uint64 count,
+
Transaction& transaction);
+ void ResetFreeBlocks(uint64
count);
+ //
interface for Transaction only
+
private:
status_t _Allocate(uint64 base,
uint64 searchEnd,
- uint64
count, uint64* _allocatedBase,
+ uint64
count, Transaction& transaction,
+ uint64*
_allocatedBase,
uint64&
_allocatedCount);
status_t _AllocateInGroup(uint64
base, uint64 searchEnd,
- uint32
count, uint64* _allocatedBase,
+ uint32
count, Transaction& transaction,
+ uint64*
_allocatedBase,
uint32&
_allocatedCount);
status_t
_AllocateInBitmapBlock(uint64 base,
- uint32
count, uint64* _allocatedBase,
+ uint32
count, Transaction& transaction,
+ uint64*
_allocatedBase,
uint32&
_allocatedCount);
- status_t _Free(uint64 base,
uint64 count);
- status_t _FreeInGroup(uint64
base, uint32 count);
- status_t
_FreeInBitmapBlock(uint64 base, uint32 count);
+ status_t _Free(uint64 base,
uint64 count,
+
Transaction& transaction);
+ status_t _FreeInGroup(uint64
base, uint32 count,
+
Transaction& transaction);
+ status_t
_FreeInBitmapBlock(uint64 base, uint32 count,
+
Transaction& transaction);
private:
mutex fLock;
@@ -60,9 +72,10 @@
class AllocatedBlock {
public:
- AllocatedBlock(BlockAllocator* allocator)
+ AllocatedBlock(BlockAllocator* allocator, Transaction& transaction)
:
fAllocator(allocator),
+ fTransaction(transaction),
fIndex(0)
{
}
@@ -70,7 +83,7 @@
~AllocatedBlock()
{
if (fIndex > 0)
- fAllocator->Free(fIndex, 1);
+ fAllocator->Free(fIndex, 1, fTransaction);
}
uint64 Index() const
@@ -81,7 +94,8 @@
status_t Allocate(uint64 baseHint = 0)
{
uint64 allocatedBlocks;
- status_t error = fAllocator->Allocate(0, 1, fIndex,
allocatedBlocks);
+ status_t error = fAllocator->Allocate(0, 1, fTransaction,
fIndex,
+ allocatedBlocks);
if (error != B_OK)
fIndex = 0;
return error;
@@ -96,6 +110,7 @@
private:
BlockAllocator* fAllocator;
+ Transaction& fTransaction;
uint64 fIndex;
};
Modified: haiku/trunk/src/tests/system/kernel/file_corruption/fs/Directory.cpp
===================================================================
--- haiku/trunk/src/tests/system/kernel/file_corruption/fs/Directory.cpp
2010-07-12 11:51:41 UTC (rev 37477)
+++ haiku/trunk/src/tests/system/kernel/file_corruption/fs/Directory.cpp
2010-07-12 13:21:42 UTC (rev 37478)
@@ -6,7 +6,1434 @@
#include "Directory.h"
+#include <algorithm>
+#include <new>
+#include <AutoDeleter.h>
+
+#include "Block.h"
+#include "BlockAllocator.h"
+#include "DebugSupport.h"
+
+
+class DirEntryBlock {
+public:
+ DirEntryBlock();
+ DirEntryBlock(
+
checksumfs_dir_entry_block* entryBlock,
+ size_t
entryBlockSize);
+
+ void
SetTo(checksumfs_dir_entry_block* entryBlock,
+ size_t
entryBlockSize);
+
+ inline int32 EntryCount() const;
+ inline size_t BytesUsedFor(int32 entryCount)
const;
+ inline size_t BytesUsed() const;
+ inline size_t FreeSpace() const;
+
+ inline uint64 BlockIndexAt(int32 index) const;
+ const char* NameAt(int32 index,
size_t& _nameLength) const;
+
+ int32
FindInsertionIndex(const char* name,
+ size_t
nameLength, bool& _exactMatch) const;
+
+ int32 FindSplitIndex(int32
index,
+ size_t
bytesNeeded) const;
+
+ void InsertEntry(int32
index, const char* name,
+ size_t
nameLength, uint64 blockIndex);
+ void ReplaceEntryName(int32
index, const char* name,
+ size_t
nameLength);
+ void RemoveEntry(int32
index);
+
+ void SplitBlock(int32
splitIndex,
+
DirEntryBlock& other);
+
+ bool Check() const;
+
+private:
+ checksumfs_dir_entry_block* fBlock;
+ size_t fBlockSize;
+};
+
+
+class DirEntryTree {
+public:
+
DirEntryTree(Directory* directory);
+
+ status_t LookupEntry(const char*
name,
+ uint64&
_blockIndex);
+ status_t LookupNextEntry(const
char* name,
+ char*
foundName, size_t& _foundNameLength,
+ uint64&
_blockIndex);
+
+ status_t InsertEntry(const char*
name, uint64 blockIndex,
+
Transaction& transaction);
+ status_t RemoveEntry(const char*
name,
+
Transaction& transaction);
+
+ bool Check();
+
+private:
+ struct LevelInfo {
+ Block block;
+ DirEntryBlock entryBlock;
+ int32 index;
+ bool exactMatch;
+ };
+
+private:
+ status_t _InitReadOnly();
+ status_t
_InitWritable(Transaction& transaction);
+ status_t _InitCommon();
+
+ status_t
_UpdateOrInsertKey(LevelInfo* infos,
+ int32
level, const char* name,
+ size_t
nameLength, uint64 blockIndex,
+ bool
insertKey, Transaction& transaction);
+
+ status_t
_InsertEntryIncrementDepth(LevelInfo* infos,
+
Transaction& transaction);
+ status_t
_InsertEntrySplitBlock(int32 level,
+
LevelInfo& info, size_t needed,
+
Transaction& transaction, Block& newBlock,
+ int32&
_splitIndex);
+
+ bool _Check(int32 level,
uint64 blockIndex,
+ const
char* key, size_t keyLength,
+
DirEntryBlock& entryBlock);
+
+ inline uint16 _Depth() const { return
fTree->depth; }
+
+private:
+ Directory* fDirectory;
+ Block fRootBlock;
+ checksumfs_dir_entry_tree* fTree;
+ checksumfs_dir_entry_block* fRootEntryBlock;
+ size_t fRootEntryBlockSize;
+};
+
+
+// #pragma mark -
+
+
+static int
+compare_names(const char* a, size_t lengthA, const char* b, size_t lengthB)
+{
+ int cmp = strncmp(a, b, std::min(lengthA, lengthB));
+ if (cmp != 0)
+ return cmp;
+
+ return (int)lengthA - (int)lengthB;
+ // assumes we don't overflow 31 bits
+}
+
+
+// #pragma mark - DirEntryBlock
+
+
+DirEntryBlock::DirEntryBlock()
+ :
+ fBlock(NULL),
+ fBlockSize(0)
+{
+}
+
+
+DirEntryBlock::DirEntryBlock(checksumfs_dir_entry_block* entryBlock,
+ size_t entryBlockSize)
+ :
+ fBlock(entryBlock),
+ fBlockSize(entryBlockSize)
+{
+}
+
+
+void
+DirEntryBlock::SetTo(checksumfs_dir_entry_block* entryBlock,
+ size_t entryBlockSize)
+{
+ fBlock = entryBlock;
+ fBlockSize = entryBlockSize;
+}
+
+
+int32
+DirEntryBlock::EntryCount() const
+{
+ return fBlock->entryCount;
+}
+
+
+size_t
+DirEntryBlock::BytesUsedFor(int32 entryCount) const
+{
+ if (entryCount == 0)
+ return sizeof(*fBlock);
+ return sizeof(*fBlock) + 10 * entryCount
+ + fBlock->nameEnds[entryCount - 1];
+}
+
+
+size_t
+DirEntryBlock::BytesUsed() const
+{
+ return BytesUsedFor(EntryCount());
+}
+
+
+size_t
+DirEntryBlock::FreeSpace() const
+{
+ return fBlockSize - BytesUsed();
+}
+
+
+uint64
+DirEntryBlock::BlockIndexAt(int32 index) const
+{
+ uint64* blockIndices
+ = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
+ return blockIndices[-index];
+}
+
+
+const char*
+DirEntryBlock::NameAt(int32 index, size_t& _nameLength) const
+{
+ int32 entryCount = EntryCount();
+ if (index < 0 || index >= entryCount)
+ return NULL;
+
+ uint32 nameOffset = index > 0 ? fBlock->nameEnds[index - 1] : 0;
+ _nameLength = fBlock->nameEnds[index] - nameOffset;
+ return (const char*)(fBlock->nameEnds + entryCount) + nameOffset;
+}
+
+
+int32
+DirEntryBlock::FindInsertionIndex(const char* name, size_t nameLength,
+ bool& _exactMatch) const
+{
+ int32 entryCount = EntryCount();
+ if (entryCount == 0) {
+ _exactMatch = false;
+ return 0;
+ }
+
+ const char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+ uint32 nameOffset = 0;
+
+ int32 index = 0;
+ int cmp = -1;
+
+ // TODO: Binary search!
+ for (; index < entryCount; index++) {
+ const char* entryName = entryNames + nameOffset;
+ size_t entryNameLength = fBlock->nameEnds[index] - nameOffset;
+
+ cmp = compare_names(entryName, entryNameLength, name,
nameLength);
+ if (cmp >= 0)
+ break;
+
+ nameOffset += entryNameLength;
+ }
+
+ _exactMatch = cmp == 0;
+ return index;
+}
+
+
+/*! Finds a good split index for an insertion of \a bytesNeeded bytes at
+ index \a index.
+*/
+int32
+DirEntryBlock::FindSplitIndex(int32 index, size_t bytesNeeded) const
+{
+ size_t splitSize = (BytesUsed() + bytesNeeded) / 2;
+
+ int32 entryCount = EntryCount();
+ for (int32 i = 0; i < entryCount; i++) {
+ size_t bytesUsed = BytesUsedFor(i + 1);
+ if (i == index)
+ bytesUsed += bytesNeeded;
+ if (bytesUsed > splitSize)
+ return i;
+ }
+
+ // This should never happen.
+ return entryCount;
+}
+
+
+void
+DirEntryBlock::InsertEntry(int32 index, const char* name, size_t nameLength,
+ uint64 blockIndex)
+{
+ uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
+ int32 entryCount = fBlock->entryCount;
+ char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+
+ uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
+ uint32 lastNameEnd = entryCount == 0
+ ? 0 : fBlock->nameEnds[entryCount - 1];
+
+ if (index < entryCount) {
+ // make room in the block indices array
+ memmove(&blockIndices[-entryCount], &blockIndices[1 -
entryCount],
+ 8 * (entryCount - index));
+
+ // make room in the name array -- we also move 2 bytes more for
the
+ // new entry in the nameEnds array
+ memmove(entryNames + nameOffset + nameLength + 2,
+ entryNames + nameOffset, lastNameEnd - nameOffset);
+
+ // move the names < index by 2 bytes
+ if (index > 0)
+ memmove(entryNames + 2, entryNames, nameOffset);
+
+ // move and update the nameEnds entries > index
+ for (int32 i = entryCount; i > index; i--)
+ fBlock->nameEnds[i] = fBlock->nameEnds[i - 1] +
nameLength;
+ } else if (entryCount > 0) {
+ // the nameEnds array grows -- move all names
+ memmove(entryNames + 2, entryNames, lastNameEnd);
+ }
+
+ // we have made room -- insert the entry
+ entryNames += 2;
+ memcpy(entryNames + nameOffset, name, nameLength);
+ fBlock->nameEnds[index] = nameOffset + nameLength;
+ blockIndices[-index] = blockIndex;
+ fBlock->entryCount++;
+ASSERT(Check());
+}
+
+
+void
+DirEntryBlock::ReplaceEntryName(int32 index, const char* name,
+ size_t nameLength)
+{
+ int32 entryCount = fBlock->entryCount;
+ char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+
+ ASSERT(index >= 0 && index < entryCount);
+
+ uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
+ uint32 oldNameLength = fBlock->nameEnds[index] - nameOffset;
+ uint32 lastNameEnd = fBlock->nameEnds[entryCount - 1];
+
+ if (oldNameLength != nameLength) {
+ int32 lengthDiff = (int32)nameLength - (int32)oldNameLength;
+
+ ASSERT(lengthDiff <= (int32)FreeSpace());
+
+ // move names after the changing name
+ if (index + 1 < entryCount) {
+ memmove(entryNames + nameOffset + nameLength,
+ entryNames + nameOffset + oldNameLength,
+ lastNameEnd - nameOffset - oldNameLength);
+ }
+
+ // update the name ends
+ for (int32 i = index; i < entryCount; i++)
+ fBlock->nameEnds[i] = (int32)fBlock->nameEnds[i] +
lengthDiff;
+ }
+
+ // copy the name
+ memcpy(entryNames + nameOffset, name, nameLength);
+ASSERT(Check());
+}
+
+
+void
+DirEntryBlock::RemoveEntry(int32 index)
+{
+ ASSERT(index >= 0 && index < EntryCount());
+
+ int32 entryCount = EntryCount();
+ if (entryCount == 1) {
+ // simple case -- removing the last entry
+ fBlock->entryCount = 0;
+ return;
+ }
+
+ uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
+ char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+
+ uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
+ uint32 nameEnd = fBlock->nameEnds[index];
+ uint32 lastNameEnd = entryCount == 0
+ ? 0 : fBlock->nameEnds[entryCount - 1];
+
+ if (index < entryCount - 1) {
+ uint32 nameLength = nameEnd - nameOffset;
+
+ // remove the element from the block indices array
+ memmove(&blockIndices[-entryCount + 2],
&blockIndices[-entryCount + 1],
+ 8 * (entryCount - index - 1));
+
+ // move and update the nameEnds entries > index
+ for (int32 i = index + 1; i < entryCount; i++)
+ fBlock->nameEnds[i - 1] = fBlock->nameEnds[i] -
nameLength;
+
+ // move the names < index by 2 bytes
+ if (index > 0)
+ memmove(entryNames - 2, entryNames, nameOffset);
+
+ // move the names > index
+ memmove(entryNames - 2 + nameOffset, entryNames + nameEnd,
+ lastNameEnd - nameEnd);
+ } else {
+ // the nameEnds array shrinks -- move all names
+ memmove(entryNames - 2, entryNames, nameOffset);
+ }
+
+ // we have removed the entry
+ fBlock->entryCount--;
+ASSERT(Check());
+}
+
+
+/*! Moves all entries beyond \a splitIndex (inclusively) to the empty block
+ \a other.
+*/
+void
+DirEntryBlock::SplitBlock(int32 splitIndex, DirEntryBlock& other)
+{
+ ASSERT(other.EntryCount() == 0);
+ ASSERT(splitIndex <= EntryCount());
+
+ int32 entryCount = EntryCount();
+ if (splitIndex == entryCount)
+ return;
+ int32 otherEntryCount = entryCount - splitIndex;
+
+ // copy block indices
+ uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize);
+ uint64* otherBlockIndices
+ = (uint64*)((uint8*)other.fBlock + other.fBlockSize);
+ // note: both point after the last entry, unlike in other
methods
+ memcpy(otherBlockIndices - otherEntryCount, blockIndices - entryCount,
+ 8 * otherEntryCount);
+
+ // copy the name end offsets
+ uint32 namesOffset = splitIndex > 0
+ ? fBlock->nameEnds[splitIndex - 1] : 0;
+ for (int32 i = splitIndex; i < entryCount; i++) {
+ other.fBlock->nameEnds[i - splitIndex] = fBlock->nameEnds[i]
+ - namesOffset;
+ }
+
+ // copy the names
+ char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+ char* otherEntryNames
+ = (char*)(other.fBlock->nameEnds + otherEntryCount);
+ memcpy(otherEntryNames, entryNames + namesOffset,
+ fBlock->nameEnds[entryCount - 1] - namesOffset);
+
+ // the name ends array shrinks -- move the names
+ if (splitIndex > 0) {
+ char* newEntryNames = (char*)(fBlock->nameEnds + splitIndex);
+ memmove(newEntryNames, entryNames, namesOffset);
+ }
+
+ // update the entry counts
+ fBlock->entryCount = splitIndex;
+ other.fBlock->entryCount = otherEntryCount;
+ASSERT(Check());
+ASSERT(other.Check());
+}
+
+
+bool
+DirEntryBlock::Check() const
+{
+ int32 entryCount = EntryCount();
+ if (entryCount == 0)
+ return true;
+
+ // Check size: Both name ends and block index arrays must fit and we
need
+ // at least one byte per name.
+ size_t size = sizeof(*fBlock) + entryCount * 10;
+ if (size + entryCount > fBlockSize) {
+ ERROR("Invalid dir entry block: entry count %d requires minimum
size "
+ "of %" B_PRIuSIZE " + %d bytes, but block size is %"
B_PRIuSIZE
+ "\n", (int)entryCount, size, (int)entryCount,
fBlockSize);
+ return false;
+ }
+
+ // check the name ends and block indices arrays and the names
+ const char* entryNames = (char*)(fBlock->nameEnds + entryCount);
+ const uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
+ const char* previousName = NULL;
+ uint16 previousNameLength = 0;
+ uint16 previousEnd = 0;
+
+ for (int32 i = 0; i < entryCount; i++) {
+ // check name end
+ uint16 nameEnd = fBlock->nameEnds[i];
+ if (nameEnd <= previousEnd || nameEnd > fBlockSize - size) {
+ ERROR("Invalid dir entry block: name end offset of
entry %" B_PRId32
+ ": %u, previous: %u\n", i, nameEnd,
previousEnd);
+ return false;
+ }
+
[... truncated: 2278 lines follow ...]
Other related posts:
- » [haiku-commits] r37478 - in haiku/trunk/src/tests/system/kernel/file_corruption: . fs fs/userland - ingo_weinhold
