[haiku-commits] r38573 - haiku/trunk/src/add-ons/kernel/file_systems/ext2
- From: korli@xxxxxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Wed, 8 Sep 2010 01:25:42 +0200 (CEST)
Author: korli
Date: 2010-09-08 01:25:42 +0200 (Wed, 08 Sep 2010)
New Revision: 38573
Changeset: http://dev.haiku-os.org/changeset/38573
Added:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
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/HashRevokeManager.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HashRevokeManager.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/Journal.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Journal.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/NoJournal.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/NoJournal.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/RevokeManager.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/RevokeManager.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Transaction.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Transaction.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/Utility.h
Modified:
haiku/trunk/src/add-ons/kernel/file_systems/ext2/CachedBlock.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/HTree.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/HTreeEntryIterator.h
haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.cpp
haiku/trunk/src/add-ons/kernel/file_systems/ext2/IndexedDirectoryIterator.h
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/Jamfile
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:
Patch from Janito Ferreira Filho (aka jjvf): this is the result of his GSoC
assignment "Implement ext2/3 Read and Write Support for Haiku".
* Tested and checked most features and fs operations, while passing
successfully the Linux fsck. Though the implementation still needs more testing
and is to be used with
caution, it's better in my mind to have the code committed now given the size
of the patch.
* Code style isn't extensively checked but is mostly OK. Code review is welcome.
Some notes from Janito:
* Sparse files aren't supported and hard links aren't supported. Write
attributes methods aren't activated nor tested.
* Journaling needs more testing to make sure it behaves in a compatible way to
Ext3, and support for the different modes hasn't been implemented (due to the
block
and file cache incompatibility). Correct revoke management is also lacking, as
is proper management of the superblock state and copies and block group copies.
* The code is partly based and inspired by the BFS implementation. Author
information might need to be fixed.
I'd like to congratulate and thank Janito for his hard work to bring the
implementation to the current state. I hope he'll keep on maintaining it and
become a regular
contributor/committer.
Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
(rev 0)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.cpp
2010-09-07 23:25:42 UTC (rev 38573)
@@ -0,0 +1,664 @@
+/*
+ * 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)
+{
+ TRACE("BitmapBlock::Unmark(%lu, %lu, %c)\n", start, length,
+ force ? 't' : 'f');
+
+ if (fData == NULL || start + length > fNumBits)
+ return false;
+
+ uint32 startIndex = start >> 5;
+ uint32 startBit = start & 0x1F;
+ uint32 remainingBits = (length - 32 + startBit) & 0x1F;
+
+ TRACE("BitmapBlock::Unmark(): start index: %lu, start bit: %lu,
remaining "
+ "bits: %lu)\n", startIndex, startBit, remainingBits);
+ uint32 iterations;
+
+ if (length < 32) {
+ if (startBit + length < 32) {
+ uint32 bits =
B_LENDIAN_TO_HOST_INT32(fData[startIndex]);
+ TRACE("BitmapBlock::Unmark(): bits: %lx\n", bits);
+
+ uint32 mask = (1 << (startBit + length)) - 1;
+ mask &= ~((1 << startBit) - 1);
+
+ TRACE("BitmapBlock::Unmark(): mask: %lx\n", mask);
+
+ if ((bits & mask) != mask)
+ return false;
+
+ bits &= ~mask;
+
+ TRACE("BitmapBlock::Unmark(): updated bits: %lx\n",
bits);
+ fData[startIndex] = B_HOST_TO_LENDIAN_INT32(bits);
+
+ return true;
+ } else
+ iterations = 0;
+ } else
+ iterations = (length - 32 + startBit) >> 5;
+
+ TRACE("BitmapBlock::Unmark(): iterations: %lu\n", iterations);
+ uint32 index = startIndex;
+ uint32 mask = 0;
+
+ if (startBit != 0) {
+ mask = ~((1 << startBit) - 1);
+ uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+
+ TRACE("BitmapBlock::Unmark(): mask: %lx, bits: %lx\n", mask,
bits);
+
+ if (!force && (bits & mask) != mask)
+ return false;
+
+ bits &= ~mask;
+ fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+
+ TRACE("BitmapBlock::Unmark(): updated bits: %lx\n", bits);
+ index += 1;
+ }
+
+ mask = 0xFFFFFFFF;
+ for (; iterations > 0; --iterations) {
+ if (!force && fData[index] != mask)
+ return false;
+ fData[index++] = 0;
+ }
+
+ TRACE("BitmapBlock::Unmark(): Finished iterations\n");
+
+ if (remainingBits != 0) {
+ mask = (1 << remainingBits) - 1;
+ uint32 bits = B_LENDIAN_TO_HOST_INT32(fData[index]);
+
+ TRACE("BitmapBlock::Unmark(): mask: %lx, bits: %lx\n", mask,
bits);
+
+ if (!force && (bits & mask) != mask)
+ return false;
+
+ bits &= ~mask;
+ fData[index] = B_HOST_TO_LENDIAN_INT32(bits);
+
+ TRACE("BitmapBlock::Unmark(): updated bits: %lx\n", 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 a 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)
+{
+ TRACE("BitmapBlock::FindPreviousMarked(%lu)\n", 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;
+ int32 bit = pos & 0x1F;
+
+ uint32 mask = (1 << (bit + 1)) - 1;
+ uint32 bits = B_LENDIAN_TO_HOST_INT32(data[index]);
+ bits = bits & mask;
+
+ TRACE("BitmapBlock::FindPreviousMarked(): index: %lu, bit: %lu\n",
index,
+ bit);
+
+ 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;
+}
Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
(rev 0)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/BitmapBlock.h
2010-09-07 23:25:42 UTC (rev 38573)
@@ -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
Added: haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
===================================================================
--- haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
(rev 0)
+++ haiku/trunk/src/add-ons/kernel/file_systems/ext2/BlockAllocator.cpp
2010-09-07 23:25:42 UTC (rev 38573)
@@ -0,0 +1,714 @@
+/*
+ * 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* volume, 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);
+ void _LockInTransaction(Transaction&
transaction);
+
+
+ Volume* fVolume;
+ uint32 fBlockGroup;
+ ext2_block_group* fGroupDescriptor;
+
+ mutex fLock;
+ mutex fTransactionLock;
+ int32 fCurrentTransaction;
+
+ uint32 fStart;
+ uint32 fNumBits;
+ uint32 fBitmapBlock;
+
+ uint32 fFreeBits;
+ uint32 fFirstFree;
+ uint32 fLargestStart;
+ uint32 fLargestLength;
+
+ uint32 fPreviousFreeBits;
+ uint32 fPreviousFirstFree;
+ uint32 fPreviousLargestStart;
+ uint32 fPreviousLargestLength;
+};
+
+
+AllocationBlockGroup::AllocationBlockGroup()
+ :
+ fVolume(NULL),
+ fBlockGroup(0),
+ fGroupDescriptor(NULL),
+ fStart(0),
+ fNumBits(0),
+ fBitmapBlock(0),
+ fFreeBits(0),
+ fFirstFree(0),
+ fLargestStart(0),
+ fLargestLength(0),
+ fPreviousFreeBits(0),
+ fPreviousFirstFree(0),
+ fPreviousLargestStart(0),
+ fPreviousLargestLength(0)
+{
+ mutex_init(&fLock, "ext2 allocation block group");
+ mutex_init(&fTransactionLock, "ext2 allocation block group
transaction");
+}
+
+
+AllocationBlockGroup::~AllocationBlockGroup()
+{
+ mutex_destroy(&fLock);
+ mutex_destroy(&fTransactionLock);
+}
+
+
+status_t
+AllocationBlockGroup::Initialize(Volume* volume, uint32 blockGroup,
+ uint32 numBits)
+{
+ fVolume = volume;
+ fBlockGroup = blockGroup;
+ fNumBits = numBits;
+
+ status_t status = fVolume->GetBlockGroup(blockGroup, &fGroupDescriptor);
+ if (status != B_OK)
+ return status;
+
+ fBitmapBlock = fGroupDescriptor->BlockBitmap();
+
+ status = ScanFreeRanges();
+
+ if (fGroupDescriptor->FreeBlocks() != fFreeBits) {
+ TRACE("AllocationBlockGroup::Initialize(): Mismatch between
counted "
+ "free blocks (%lu) and what is set on the group
descriptor "
+ "(%lu)\n", fFreeBits,
(uint32)fGroupDescriptor->FreeBlocks());
+ return B_BAD_DATA;
+ }
+
+ 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 > fNumBits)
+ return B_BAD_DATA;
+
+ _LockInTransaction(transaction);
+
+ 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;
+ }
+
+ fFreeBits -= length;
+ fGroupDescriptor->SetFreeBlocks((uint16)fFreeBits);
+ fVolume->WriteBlockGroup(transaction, fBlockGroup);
+
+ 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)
+{
+ TRACE("AllocationBlockGroup::Free(): start: %lu, length %lu\n", start,
+ length);
+
+ if (length == 0)
+ return B_OK;
+
+ uint32 end = start + length;
+
+ if (end > fNumBits)
+ return B_BAD_DATA;
+
+ _LockInTransaction(transaction);
+
+ 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;
+ }
+
+ TRACE("AllocationGroup::Free(): Unmarked bits in bitmap\n");
+
+ if (fFirstFree > start)
+ fFirstFree = start;
+
+ if (start + length == fLargestStart) {
+ fLargestStart = start;
[... truncated: 9216 lines follow ...]
Other related posts:
- » [haiku-commits] r38573 - haiku/trunk/src/add-ons/kernel/file_systems/ext2 - korli
