bfs: Reduce potential for garbage value ingestion

* Pointed out by clang static analysis. These are
later read while not being completely validated.

Change-Id: I4546526535d6e011aee40c74136f992962ab8cff
Reviewed-on: https://review.haiku-os.org/c/haiku/+/7159
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

bfs: build fix.

I built only the bootloader for sparc when testing, so some code was
disabled because it's guarded by _BOOT_MODE.

Confirmed that the generated assembler is not larger than before (the
disassembly file is the same size, but for some reason functions were in
a different order, making it difficult to compare more closely)

bfs: fix misaligned access

The BFS on-disk data is not aligned. Reading it to memory and trying to
access fields directly does not work on sparc. memcpy the data to an
aligned variable before handling it with its native size.

gcc knows how to access unaligned data, but we need to tell it when to do
so. This is done with the "packed" attribute, but it works only on
structs. So we have to wrap the values in a struct.

Thanks to C++ features, we can make the struct
relatively transparent by having an assigment operator (for writes) and
a cast operator (for read access), so there is no need to access the
value inside the struct with ".value" everywhere. The rest of the code
is then largely unchanged (except for use in printf statements and other
vararg functions, where the implicit casting can't work).

gcc takes care of performing the access in the correct way on platforms
that need it (old ARM, sparc) and can still optimize things on other
architectures where specific code is not needed for unaligned access.

Fixes #9255

Change-Id: I3bf62590dee059ad32b1845bdc4eace165b73203
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2363
Reviewed-by: Adrien Destugues <pulkomandy@gmail.com>

bfs: Return B_NAME_TOO_LONG from BPlusTree::Find

This patch makes "UnitTester BNode" pass.

Several tests which attempt to create or access a directory entry that
exceeds the maximum length assume that B_NAME_TOO_LONG status will be
returned, since that is what BeOS does. When constructing a BNode with
a path like "/tmp/some really long filename larger than 256
characters...", the vfs eventually calls bfs_lookup() which calls
BPlusTree::Find(). In the case of a really long entry, Find() returns
B_BAD_VALUE.

This patch just changes BPlusTree::Find to return the more specific
error that matches BeOS.

Additionally this patch fixes some assertions in NodeTest. BeOS seems
to have been missing some error checking code in the initialization of
BNode, specifically with BNode(Directory*, const char*) and the
equivalent SetTo method. If you provide an empty string for the child
entry name to either of those, B_OK will be returned. But either way
you initialize the object, when you try to use it, like with
BNode::GetAttrInfo(), you'll get B_BAD_VALUE.

This just changes any assertions for this situation to expect
B_ENTRY_NOT_FOUND, which is the actual initialization error Haiku
sets.

This and the change to bfs resolves many assertions the following
storage tests:
* TestCaller BFile::Init Test 1
* TestCaller BFile::Init Test 2
* TestCaller BNode::Init Test1
* TestCaller BNode::Init Test2
* TestCaller BSymLink::Init Test 1
* TestCaller BSymLink::Init Test 2

Change-Id: I8598352aa341ffcab9f7bc3e6740ae1cb3dbab8c
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2490
Reviewed-by: waddlesplash <waddlesplash@gmail.com>

BFS: Fixed readdir() again.

* We still need to return B_BUFFER_OVERFLOW if the passed in buffer was
smaller than INODE_FILE_NAME_LENGTH, as that's what must be expected
from the caller.

BFS: Fixed maximum index key length.

* The maximum key length of the B+tree, and the one BFS uses are now
separated. This allows to stay BeOS compatible to only put a maximum
of 255 bytes into the index, but also to handle the already existing
larger keys (we did allow 256 bytes) without issue.
* TreeIterator::Traverse() now always cuts off string keys at the
maximum buffer length, and only reports a B_BUFFER_OVERFLOW for the
fixed length types.
* This fixes the important part of #13254.

Fix GCC 5 maybe-uninitialized warnings.

Signed-off-by: Adrien Destugues <pulkomandy@pulkomandy.tk>

Fixes #12020

BFS: _SplitNode() could overflow the new node.

* When the keys were large enough, a large key entering the node could
overflow the available data in the target node. This caused tree and
memory corruption.
* This fixes bug #6034.

BFS: Fix check of key compare in BPlusTree::_ValidateChildren().

In ba320218245aeb11cb74c37ecf7132d0b9903957 the key comparison was fixed
to use a compatible version. Since then the check can actually return
results other than -1. The check done on the result was too strict
however. The child nodes may never contain keys that are larger than the
keys they are reached by. But the last key of a child node may be equal
to the one in the parent. This change fixes the check to take this
special case into account.

Fixes #11026 and #11289. The issue was unproblematic in so far that it
was only hit during a filesystem check and, since BPlusTree does not
yet attempt to correct corrupted trees, did not result in any actual
actions.

bfs: Use the QueryParserUtils instead of its own copy.

* Ingo copied the methods into a shared location, and then obviously
"forgot" to let BFS use them. As a side note for Ingo: the complete
error GCC reported was "std::fssh_size_t" not defined with the macro
wrapper as code location. The actual problem was a "using std::size_t"
in some C++ header that accidentally got included after the wrapper.
* The shared Query code is not yet used. That'll be done another time.
* Renamed BFS_SHELL define to FS_SHELL, such that QueryParserUtils can be
used in any file system shell, not just the bfs_shell.

bfs: fixed wrong key comparison in validator.

* bplustree_header::DataType() is not compatible with the type constants
compareKeys() expects. Use _CompareKeys() instead.

Lots of B_PRI... insertions to fix errors with DEBUG=1.

BPlusTree: Fix fCurrentKey in backward TreeIterator traversal.

When reaching the next node the current key should be set to the next
valid index within that node (0 for forward and NumKeys() - 1 for
backward). This did not cause any harm as BFS uses forward traversal
only.

BPlusTree: Fix GCC4 false positive of possible unintialized use.

haiku_loader: Reuse BPlusTree implementation of the BFS add-on.

Instead of having an almost exact, albeit read only, duplicate of the
implementation.

BPlusTree: Style cleanup only, no functional change.

Check for and report an error on key buffer overrun.

This usually wasn't a problem as the key buffer is generally large
enough to hold a single value. Still on short buffers or very long
it could have silently overrun before.

Single values are allowed in regular duplicate nodes

Not in duplicate fragments, however. This oversight in hrev44359 made
checkfs incorrectly rebuild valid indices, causing #8762.

Signed-off-by: Axel Dörfler <axeld@pinc-software.de>

64-bit compilation fixes for BFS, add to x86_64 boot image.

A duplicate array with a single value is not allowed

Such arrays could be created by the BFS code between hrev43837 and
hrev43924, and cause the array to not be free'd when the entry is
removed.

The check in _InsertDuplicate() is not changed, as doing an insertion
will actually repair this problem.

Potentially, the code could be modified to handle this state instead,
but since checkfs can fix it, it doesn't seem necessary.

Signed-off-by: Axel Dörfler <axeld@pinc-software.de>

Make sure it isn't part of a transaction upon destruction.

Minor cleanup.

Fixed another bug I introduced with r43837.

* Really the same thing, just for fragment nodes this time.

Don't bail out just because a node couldn't be read.

* Added a new CachedNode::SetTo() variant that actually returns an error code.
* Only bail out if there was an actual I/O error, not already if the offset
was invalid.
* This should help fixing some corruption corner cases.

We must not check the node here.

* The node might not be a normal tree node, so we must not check it before
writing.
* Also, it's always a good idea to check if the function you called didn't
succeed.
* This fixes a crashing bug when running checkfs in some rare circumstances.

Improved debug output.

Minor cleanup.

Fixed the invalid duplicate left over nodes.

* Accidently introduced that bug in r43837; the arrayCount variable was not
being updated after the value got removed.

Fixed misuse of Transaction::Split().

* This would cause "transaction too large" messages, and repairing the index
would actually be thrown away.
* We now properly finish/restart transactions instead which is actually
working.
* Removed the misleading Split() method altogether, as it's not even used
anywhere (not very surprising given that it doesn't do what its name
suggests).

Also report errors when the free list is broken.

* This will cause the whole B+tree to be rewritten in that case, too.
* Added a TODO comment that describes an alternative solution for this.

Implemented repairing index b+trees.

* There are now two passes in case a corrupted index tree has been found.
* The second pass will clear the affected indices at first, and will then walk
over all inodes again to fill them.
* As a side effect, this will also defragment the indices; ie. the same
mechanism could be used for this some day.

Use ID() instead of BlockNumber() for the debug output.

Made the duplicate_array endian safe. Cleanup.

* Renamed the sorted_array to duplicate_array (which was only a typedef
before), and moved it into the BPlusTree.cpp file, as its specific to
that one.
* Utilities.cpp is no longer needed.
* Introduced endian safe getters/setters so that little endian BFS volumes
should now work fine on a big endian architecture.

Implemented BPlusTree::Validate().

* Walks the complete B+tree and checks all nodes for validity
(duplicate/fragment as well), ie. if no key is larger than those of its
parent, and that the left/right links are valid.
* This does not yet support repairing of broken trees, though.

* BPlusTree is now using the TransactionListener mechanism to update its private
fHeader copy on failure.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35492 a95241bf-73f2-0310-859d-f6bbb57e9c96

* CachedNode::SetToWritable() already needs the updated header, so we need to
Unset() the header in Allocate() before calling it. This fixes bug #5410.
* CachedNode::Allocate() does not need to revert its changes; the transaction
will take care of that. However, BPlusTree::fHeader is currently not correctly
maintained if a transaction fails (working on that now).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35490 a95241bf-73f2-0310-859d-f6bbb57e9c96

* BPlusTree no longer caches the header in its own block, instead, it aggregates
a copy of its structure. CachedNode is only used to write to the header, now.
This should cause the block_cache to no longer have any referenced blocks
outside of any I/O.
* Coding style cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35473 a95241bf-73f2-0310-859d-f6bbb57e9c96

Replaced "%Ld" and "%lld" in printf()s by the new B_PRI* macros to avoid
warnings when building with a 64 bit compiler.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34216 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed warnings when compiled with DEBUG=1.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@33550 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed two bugs in BPlusTree::Remove(): it could update the tree iterators
incorrectly in case of duplicates. And also, more importantly, it did not
check if the entry to remove had the same value -- it would happily remove
any entry with the same attribute content. This could only happen in the
reindex case, though, and was the cause of bug #3854.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30616 a95241bf-73f2-0310-859d-f6bbb57e9c96

Calm down debug output a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28148 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Followed Marcus' suggestion and made the array a static const one.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27663 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27627 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved the inode_types into Utilities.h.
* Added a S_EXTENDED_TYPES constant to simplify some checks.
* Simplified the fAllowDuplicates computation in BPlusTree::SetTo().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27625 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Build fix when built with DEBUG defined.
* Forgot to remove the "bfs_block_runs" debugger command on module unload.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26800 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Coding style cleanups, no functional changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26728 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced Chain with the new SinglyLinkedList.
* Renamed openModeToAccess() to open_mode_to_access().
* Cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26718 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Changed the inode write locking to be held as long as the transaction is
running - this fixes several cases where someone could see outdated data
when a transaction had to be reverted (the time between unlocking the inode
and actually reverting the blocks). For that, Inodes can now be put into a
singly linked list.
* Added a TODO in Inode::WriteAt() which explains why it cannot use the above
method: seems that our VFS/VM locking model isn't really that good.
* Fixed a possible deadlock in Attribute::_Truncate() where the inode write
lock was held before starting the transaction.
* Added an InodeReadLocker convenience class, that should be used instead
of ReadLocker - Inode::Lock() only still exists because of the needs of
bfs_io().
* Moved the bfs_io() callback hooks out of the exported module API region,
and removed their bfs_ prefix.
* Added a Volume::IsInitializing() method that should be used rather than
checking if Volume::ID() is >= 0.
* Removed the MultiInodeLocker again, as it's pretty much superfluous now.
* Moved openModeToAccess() to the Utility.h header.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26715 a95241bf-73f2-0310-859d-f6bbb57e9c96

First round of locking fixes:
* Moved locking the data stream out of the BPlusTree methods; this fixes at
least two locations where another thread could have seen outdated/incorrect
data.
* Removed some superfluous code in bfs_rename(): we don't have to revert to the
previous situation, the transaction does this for us automatically.
* Added a simple MultiWriteLocker, even though it's not really necessary anymore
(since we always hold the transaction lock first when we lock more than one
inode at a time).
* Inode::Create() called InodeAllocator::Keep() a bit too early, the file cache
and map wasn't created and assigned yet.
* InodeAllocator now keeps the inode write locked.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26689 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish + mmlr + axeld:
* Fixed a bug that could easily corrupt your disks (yeah, one of those
again): bfs_get_file_map() truncated the last vec incorrectly and
would potentially return a too large file size -- which was later
happily overwritten with file data, but could have belonged to
anything but that file (like inodes, B+trees, etc.).
* Renamed previous round_up() function to key_align().
* Added round_up() template function, and used it where appropriate.
* The latter actually fixed two bugs where the and mask was computed in
32 bit where it should have been in 64 bit.
* Inode::FindBlockRun() should have checked the max indirect size
instead of the direct size - this didn't cause any problems, though.
* White space cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26531 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced BFS's ReadWriteLock implementation with the kernel's rw_lock.
* The BlockAllocator now uses the new mutex_transfer_lock() function instead
of clobbering the mutex directly.
* Removed Lock.h - it's no longer needed.
* Minor white space cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26317 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed the home-brewn locking classes in BFS besides the read/write lock
(for now).
* Inode::fSmallDataLock is now a recursive_lock, Journal::fLock is now
a recursive_lock, too, Journal::fEntriesLock is now a mutex, as is
BPlusTree::fIteratorLock.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26298 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Looks like r24456 was a bit premature: with string attributes, it makes sense
to ignore a trailing null byte, which the code now didn't do anymore.
* This caused bug #2054.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24888 a95241bf-73f2-0310-859d-f6bbb57e9c96

* If two equal keys were compared, the check for the key end was
incorrect; only the length of the key matters, not if they are null
terminated. It would still return the correct value, though, it would
just access one byte beyond the buffer (which didn't really matter
in this specific case).
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24456 a95241bf-73f2-0310-859d-f6bbb57e9c96

* _SeekDown() now checks if it has already reached the maximum tree
depth, and will bail out if it hasn't reached the leaf level then.
* This should at least avoid the crash of bug #1911; there is not much
more I can do about that.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24411 a95241bf-73f2-0310-859d-f6bbb57e9c96

Patch by Vasilis Kaoutsis to fix some warnings, thanks!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24203 a95241bf-73f2-0310-859d-f6bbb57e9c96

* When shrinking the stream size after a node had been removed, its
parent node could temporarily get invalid (ie. CheckNode() would
fail).
* Since shrinking the stream was done in edge cases only, anyway, we
will no longer do that which works around the problem. This fixes
bug #1716.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23656 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed warnings when building the bfs_shell.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23462 a95241bf-73f2-0310-859d-f6bbb57e9c96

* bfs_{read|write}_pages() now only try to lock - this fixes a possible
deadlock whenever someone without a lock (like the page_writer()) is calling
this function.
* Added a new ReadWriteLock::TryLock() method.
* Renamed bfs_read_vnode() and bfs_release_vnode() to bfs_get_vnode() and
bfs_put_vnode() just like those functions are called in fs_interface.h.
* Fixed a warning in BPlusTree::_SplitNode().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22372 a95241bf-73f2-0310-859d-f6bbb57e9c96

Changes in BPlusTree::_SplitNode():
* Added check for invalid keyIndex parameter.
* Removed superfluous break condition in the second loop.
* Increment "out" in the second loop only when we have processed a key
that will end up in the node. Thus, after the loop, the variable will
contain the numbers of keys to be copied/moved, not that number + 1.
Adjusted later use of "out" accordingly, save in one place where it
was used incorrectly, which resulted in one key length and value to
many to be copied, thus occasionally causing a page fault (bug #1363).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22195 a95241bf-73f2-0310-859d-f6bbb57e9c96

axeld + bonefish:
Fixed off-by-one error in the b+ tree code splitting a node, which could
result in a read beyond the block bounds thus causing a page fault. Was
nicely reproducible when unzipping big archives. Now bug #1003 seems to
be fixed for real.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21671 a95241bf-73f2-0310-859d-f6bbb57e9c96

replaced uint32 by addr_t where it applies to please gcc on x86_64


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21422 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a memory leak in _SplitNode() spotted by Stefano - thanks!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21200 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed unused code when USER is defined - the fs_shell no longer does this, but
provides a kernel emulation layer.
* Renamed all private BPlusTree methods to have the '_' prefix.
* Removed useless set_sem_owner() from Lock.h - all semaphores created in the kernel
always belong to the system team automatically.
* Some cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21054 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Prepared the BFS sources to be used with the new FS shell:
- Moved all inclusions of system headers into a new
system_dependencies.h header, which conditionally either includes
these or the FS shell headers.
- Fixed compiler warnings related to printf-like functions (int32 is
int, not long on non-BeOS platforms).
* Build a new bfs_shell. Compiles and links, but does nothing ATM.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20860 a95241bf-73f2-0310-859d-f6bbb57e9c96

Porting r18992 to the R5 version of BFS (and therefore, bfs_shell used to build the
Haiku image) revealed a problem with that change:
* If the root node only contained a single entry it was freed instead of just making
it a leaf node - that could produce an invalid b+tree (could only happen with
attribute or index trees, as directories always contain '.' and '..').


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19006 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a stupid bug found by accident:
* When removing the last key from a leaf node, the node wasn't freed, but just
emptied, and thus the whole tree structure would never combast.
* This could also cause a bug in the TreeIterator: if the last entry was not
in the last node, every second readdir() after the last one would return
the last entry again. I only found this because that happens to be what
Tracker does (which would run in an endless loop while scanning the directory
then).
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@18992 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Imported PPC big endian fixes into Haiku's BFS.
* Fixed another issue in BPlusTree::RemoveKey().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@17558 a95241bf-73f2-0310-859d-f6bbb57e9c96

added error tracing to help on bug #106


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@16498 a95241bf-73f2-0310-859d-f6bbb57e9c96

Better debug output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@16017 a95241bf-73f2-0310-859d-f6bbb57e9c96

Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15871 a95241bf-73f2-0310-859d-f6bbb57e9c96

A couple of endian fixes, inspired by Ingo - there might be some more left, though,
it's untested yet.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15693 a95241bf-73f2-0310-859d-f6bbb57e9c96

Slightly improved debug output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15656 a95241bf-73f2-0310-859d-f6bbb57e9c96

We now use the kernel's Stack class instead of our own copy.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14417 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a very stupid bug I introduced in r10056 (the Haiku-only switch):
CachedNode::Allocate() could return the wrong offset for the new node when
taken from the free node pool (it accidently returned the offset for the
next free node...).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14084 a95241bf-73f2-0310-859d-f6bbb57e9c96

Made CachedNode::SetTo[Header]() return a const node/header. Made some other methods
that were supposed to be const const as well.
Found one bug this way: in one case, a duplicate node might not have been part of a
transaction (and thus, was not written back). This bug only affected the Haiku version
of BFS, though.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14083 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed two bugs in BPlusTree::RemoveDuplicate():
- if the left duplicate node of a removed node was the last node, the "array" variable
still pointed to the old node when the loop was reentered which could lead to a tree
corruption.
- if the value to be removed could not be found in the fragment it should have been in,
the method still returned B_OK instead of B_ENTRY_NOT_FOUND.
Small cleanup, updated/improved comments.
Changed bplustree_node::FragmentsUsed() from int32 to uint32. Moved the calculation
of the maximal number of fragments in a node to the new bplustree_node::MaxFragments()
method.
If a bplustree_header is not valid, BPlusTree::SetTo() will now dump the header when
compiled with DEBUG defined.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14063 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a bug I introduced when porting BFS to Haiku: when the file size of a BPlusTree
could be shrinked (because the last node was freed), the free node pointer of the
header was still accidently set to that node.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14040 a95241bf-73f2-0310-859d-f6bbb57e9c96

If allocating a new node fails, the bplustree_header::maximum_size field is now
reseted to its old value.
BPlusTree::SetTo() is now less strict about maximum_size vs. inode size differences;
it will now print a warning and set the maximum_size to the inode size, even though
the tree might be corrupted (reading should always be as compatible and forgiving
as possible).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13946 a95241bf-73f2-0310-859d-f6bbb57e9c96

Extended the node checker a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13944 a95241bf-73f2-0310-859d-f6bbb57e9c96

SeekDown() now prints out an error message when failing in a certain way (instead
of just using the RETURN_ERROR() macro).
Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13878 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed warnings: possibly uninitialized variable, missing friend classifier (struct/class).


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@11558 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed debug build.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@10196 a95241bf-73f2-0310-859d-f6bbb57e9c96

Big update while moving over completely to the Haiku kernel:
- Ported over BFS to the new cache API
- Inode no longer inherits from CachedBlock, and therefore, no longer
keeps the whole inode block in memory. It now has a copy of the bfs_inode
structure in memory instead. This has a number of advantages but also some
disadvantages, so it might be reverted later, even if it's unlikely.
- Added a NodeGetter class that can be used whenever the real block needs
to be accessed (ie. for attributes)
- Changed *transaction to &transaction where possible
- Removed support for KEEP_WRONG_DIRENT_RECLEN
- Removed support for uncached file access since that's no longer needed
- Fixed some endian issues in bfs_write_stat()
- Removed the install BFS rules, since they don't make any sense anymore
(unless you are running Haiku ;-))

Note, logged streams are not supported anymore right now. Also, the
transaction code is pretty simple and slow - it will be improved later
on. Attribute code is pretty much untested in the new environment.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@10053 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed oddly indented comment.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7681 a95241bf-73f2-0310-859d-f6bbb57e9c96

It's now <util/kernel_cpp.h> rather than <kernel_cpp.h>.
Forgot to commit that...


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7442 a95241bf-73f2-0310-859d-f6bbb57e9c96

Some minor style changes.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@6417 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added _PACKED to the on-disk structures.
Switched to kernel_cpp.h/cpp.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@6287 a95241bf-73f2-0310-859d-f6bbb57e9c96

Bunches of changes to make mwcc like the code. I also coded an _atomic_set() and _atomic_test_and_set() for PowerPC. Of course, there's already one in the kernel tree, but mine's better. :P Now builds (and works, after a fashion) on R5 PowerPC.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@5280 a95241bf-73f2-0310-859d-f6bbb57e9c96

The file system is now almost endian-aware.
Used lazy unreadable conversion: ==, !=, == 0, != 0 are endian-safe
and don't need byte swapping.
If the platform endian differs from the one selected at compile time,
it will mount all volumes read-only for now.
Uncomment BFS_BIG_ENDIAN_ONLY in the Jamfile to build the big endian
version under x86.
No matter on what platform, the compilation defaults to build BFS as
little endian file system (see bfs_endian.h for details).


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@4715 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added B_SSIZE_T_TYPE, B_SIZE_T_TYPE, B_OFF_T_TYPE to compareKeys().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@4713 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added a little more debug output in BPlusTree::Find().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3393 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed all warnings that appeared with DEBUG=1 set.
Also fixed missing return codes in BufferPool::ReleaseBuffer() and Journal::WriteLogEntry().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2845 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed some warnings, and some minor style issues.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2836 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added more checks in the BPlusTree implementation if DEBUG is defined.
The correctness of max_number_of_levels is now checked in Find().
Added a class NodeChecker which checks the integrity of the specified node
when the object is destructed (via new method bplustree_node::CheckIntegrity());
now used in Remove() and Insert().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2169 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed the bug in the query code: B_MIME_STRING_TYPE was not correctly
translated into B_STRING_TYPE for the key comparison (it was translated
but not saved under the new type).
compareKeys() will now return -1 if it didn't know the type to compare.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2121 a95241bf-73f2-0310-859d-f6bbb57e9c96

Removed the usage of Inode::Name() in the debug output.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2080 a95241bf-73f2-0310-859d-f6bbb57e9c96

Switched from Inode::IsDirectory() to Inode::IsContainer() where necessary.
Now makes use of the changed Inode::Create() logic.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2031 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed the wrong maintainance of the max_number_of_levels field in the
B+tree's header.
Some style cleanups.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@1870 a95241bf-73f2-0310-859d-f6bbb57e9c96

Initial revision


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@639 a95241bf-73f2-0310-859d-f6bbb57e9c96

BFS: _SplitNode() could overflow the new node.

* When the keys were large enough, a large key entering the node could
overflow the available data in the target node. This caused tree and
memory corruption.
* This fixes bug #6034.

BFS: Fix check of key compare in BPlusTree::_ValidateChildren().

In ba320218245aeb11cb74c37ecf7132d0b9903957 the key comparison was fixed
to use a compatible version. Since then the check can actually return
results other than -1. The check done on the result was too strict
however. The child nodes may never contain keys that are larger than the
keys they are reached by. But the last key of a child node may be equal
to the one in the parent. This change fixes the check to take this
special case into account.

Fixes #11026 and #11289. The issue was unproblematic in so far that it
was only hit during a filesystem check and, since BPlusTree does not
yet attempt to correct corrupted trees, did not result in any actual
actions.

bfs: Use the QueryParserUtils instead of its own copy.

* Ingo copied the methods into a shared location, and then obviously
"forgot" to let BFS use them. As a side note for Ingo: the complete
error GCC reported was "std::fssh_size_t" not defined with the macro
wrapper as code location. The actual problem was a "using std::size_t"
in some C++ header that accidentally got included after the wrapper.
* The shared Query code is not yet used. That'll be done another time.
* Renamed BFS_SHELL define to FS_SHELL, such that QueryParserUtils can be
used in any file system shell, not just the bfs_shell.

bfs: fixed wrong key comparison in validator.

* bplustree_header::DataType() is not compatible with the type constants
compareKeys() expects. Use _CompareKeys() instead.

Lots of B_PRI... insertions to fix errors with DEBUG=1.

BPlusTree: Fix fCurrentKey in backward TreeIterator traversal.

When reaching the next node the current key should be set to the next
valid index within that node (0 for forward and NumKeys() - 1 for
backward). This did not cause any harm as BFS uses forward traversal
only.

BPlusTree: Fix GCC4 false positive of possible unintialized use.

haiku_loader: Reuse BPlusTree implementation of the BFS add-on.

Instead of having an almost exact, albeit read only, duplicate of the
implementation.

BPlusTree: Style cleanup only, no functional change.

Check for and report an error on key buffer overrun.

This usually wasn't a problem as the key buffer is generally large
enough to hold a single value. Still on short buffers or very long
it could have silently overrun before.

Single values are allowed in regular duplicate nodes

Not in duplicate fragments, however. This oversight in hrev44359 made
checkfs incorrectly rebuild valid indices, causing #8762.

Signed-off-by: Axel Dörfler <axeld@pinc-software.de>

64-bit compilation fixes for BFS, add to x86_64 boot image.

A duplicate array with a single value is not allowed

Such arrays could be created by the BFS code between hrev43837 and
hrev43924, and cause the array to not be free'd when the entry is
removed.

The check in _InsertDuplicate() is not changed, as doing an insertion
will actually repair this problem.

Potentially, the code could be modified to handle this state instead,
but since checkfs can fix it, it doesn't seem necessary.

Signed-off-by: Axel Dörfler <axeld@pinc-software.de>

Make sure it isn't part of a transaction upon destruction.

Minor cleanup.

Fixed another bug I introduced with r43837.

* Really the same thing, just for fragment nodes this time.

Don't bail out just because a node couldn't be read.

* Added a new CachedNode::SetTo() variant that actually returns an error code.
* Only bail out if there was an actual I/O error, not already if the offset
was invalid.
* This should help fixing some corruption corner cases.

We must not check the node here.

* The node might not be a normal tree node, so we must not check it before
writing.
* Also, it's always a good idea to check if the function you called didn't
succeed.
* This fixes a crashing bug when running checkfs in some rare circumstances.

Improved debug output.

Minor cleanup.

Fixed the invalid duplicate left over nodes.

* Accidently introduced that bug in r43837; the arrayCount variable was not
being updated after the value got removed.

Fixed misuse of Transaction::Split().

* This would cause "transaction too large" messages, and repairing the index
would actually be thrown away.
* We now properly finish/restart transactions instead which is actually
working.
* Removed the misleading Split() method altogether, as it's not even used
anywhere (not very surprising given that it doesn't do what its name
suggests).

Also report errors when the free list is broken.

* This will cause the whole B+tree to be rewritten in that case, too.
* Added a TODO comment that describes an alternative solution for this.

Implemented repairing index b+trees.

* There are now two passes in case a corrupted index tree has been found.
* The second pass will clear the affected indices at first, and will then walk
over all inodes again to fill them.
* As a side effect, this will also defragment the indices; ie. the same
mechanism could be used for this some day.

Use ID() instead of BlockNumber() for the debug output.

Made the duplicate_array endian safe. Cleanup.

* Renamed the sorted_array to duplicate_array (which was only a typedef
before), and moved it into the BPlusTree.cpp file, as its specific to
that one.
* Utilities.cpp is no longer needed.
* Introduced endian safe getters/setters so that little endian BFS volumes
should now work fine on a big endian architecture.

Implemented BPlusTree::Validate().

* Walks the complete B+tree and checks all nodes for validity
(duplicate/fragment as well), ie. if no key is larger than those of its
parent, and that the left/right links are valid.
* This does not yet support repairing of broken trees, though.

* BPlusTree is now using the TransactionListener mechanism to update its private
fHeader copy on failure.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35492 a95241bf-73f2-0310-859d-f6bbb57e9c96

* CachedNode::SetToWritable() already needs the updated header, so we need to
Unset() the header in Allocate() before calling it. This fixes bug #5410.
* CachedNode::Allocate() does not need to revert its changes; the transaction
will take care of that. However, BPlusTree::fHeader is currently not correctly
maintained if a transaction fails (working on that now).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35490 a95241bf-73f2-0310-859d-f6bbb57e9c96

* BPlusTree no longer caches the header in its own block, instead, it aggregates
a copy of its structure. CachedNode is only used to write to the header, now.
This should cause the block_cache to no longer have any referenced blocks
outside of any I/O.
* Coding style cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@35473 a95241bf-73f2-0310-859d-f6bbb57e9c96

Replaced "%Ld" and "%lld" in printf()s by the new B_PRI* macros to avoid
warnings when building with a 64 bit compiler.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@34216 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed warnings when compiled with DEBUG=1.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@33550 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Fixed two bugs in BPlusTree::Remove(): it could update the tree iterators
incorrectly in case of duplicates. And also, more importantly, it did not
check if the entry to remove had the same value -- it would happily remove
any entry with the same attribute content. This could only happen in the
reindex case, though, and was the cause of bug #3854.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@30616 a95241bf-73f2-0310-859d-f6bbb57e9c96

Calm down debug output a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@28148 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Followed Marcus' suggestion and made the array a static const one.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27663 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27627 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Moved the inode_types into Utilities.h.
* Added a S_EXTENDED_TYPES constant to simplify some checks.
* Simplified the fAllowDuplicates computation in BPlusTree::SetTo().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@27625 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Build fix when built with DEBUG defined.
* Forgot to remove the "bfs_block_runs" debugger command on module unload.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26800 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Coding style cleanups, no functional changes.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26728 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced Chain with the new SinglyLinkedList.
* Renamed openModeToAccess() to open_mode_to_access().
* Cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26718 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Changed the inode write locking to be held as long as the transaction is
running - this fixes several cases where someone could see outdated data
when a transaction had to be reverted (the time between unlocking the inode
and actually reverting the blocks). For that, Inodes can now be put into a
singly linked list.
* Added a TODO in Inode::WriteAt() which explains why it cannot use the above
method: seems that our VFS/VM locking model isn't really that good.
* Fixed a possible deadlock in Attribute::_Truncate() where the inode write
lock was held before starting the transaction.
* Added an InodeReadLocker convenience class, that should be used instead
of ReadLocker - Inode::Lock() only still exists because of the needs of
bfs_io().
* Moved the bfs_io() callback hooks out of the exported module API region,
and removed their bfs_ prefix.
* Added a Volume::IsInitializing() method that should be used rather than
checking if Volume::ID() is >= 0.
* Removed the MultiInodeLocker again, as it's pretty much superfluous now.
* Moved openModeToAccess() to the Utility.h header.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26715 a95241bf-73f2-0310-859d-f6bbb57e9c96

First round of locking fixes:
* Moved locking the data stream out of the BPlusTree methods; this fixes at
least two locations where another thread could have seen outdated/incorrect
data.
* Removed some superfluous code in bfs_rename(): we don't have to revert to the
previous situation, the transaction does this for us automatically.
* Added a simple MultiWriteLocker, even though it's not really necessary anymore
(since we always hold the transaction lock first when we lock more than one
inode at a time).
* Inode::Create() called InodeAllocator::Keep() a bit too early, the file cache
and map wasn't created and assigned yet.
* InodeAllocator now keeps the inode write locked.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26689 a95241bf-73f2-0310-859d-f6bbb57e9c96

bonefish + mmlr + axeld:
* Fixed a bug that could easily corrupt your disks (yeah, one of those
again): bfs_get_file_map() truncated the last vec incorrectly and
would potentially return a too large file size -- which was later
happily overwritten with file data, but could have belonged to
anything but that file (like inodes, B+trees, etc.).
* Renamed previous round_up() function to key_align().
* Added round_up() template function, and used it where appropriate.
* The latter actually fixed two bugs where the and mask was computed in
32 bit where it should have been in 64 bit.
* Inode::FindBlockRun() should have checked the max indirect size
instead of the direct size - this didn't cause any problems, though.
* White space cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26531 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Replaced BFS's ReadWriteLock implementation with the kernel's rw_lock.
* The BlockAllocator now uses the new mutex_transfer_lock() function instead
of clobbering the mutex directly.
* Removed Lock.h - it's no longer needed.
* Minor white space cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26317 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed the home-brewn locking classes in BFS besides the read/write lock
(for now).
* Inode::fSmallDataLock is now a recursive_lock, Journal::fLock is now
a recursive_lock, too, Journal::fEntriesLock is now a mutex, as is
BPlusTree::fIteratorLock.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@26298 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Looks like r24456 was a bit premature: with string attributes, it makes sense
to ignore a trailing null byte, which the code now didn't do anymore.
* This caused bug #2054.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24888 a95241bf-73f2-0310-859d-f6bbb57e9c96

* If two equal keys were compared, the check for the key end was
incorrect; only the length of the key matters, not if they are null
terminated. It would still return the correct value, though, it would
just access one byte beyond the buffer (which didn't really matter
in this specific case).
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24456 a95241bf-73f2-0310-859d-f6bbb57e9c96

* _SeekDown() now checks if it has already reached the maximum tree
depth, and will bail out if it hasn't reached the leaf level then.
* This should at least avoid the crash of bug #1911; there is not much
more I can do about that.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24411 a95241bf-73f2-0310-859d-f6bbb57e9c96

Patch by Vasilis Kaoutsis to fix some warnings, thanks!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@24203 a95241bf-73f2-0310-859d-f6bbb57e9c96

* When shrinking the stream size after a node had been removed, its
parent node could temporarily get invalid (ie. CheckNode() would
fail).
* Since shrinking the stream was done in edge cases only, anyway, we
will no longer do that which works around the problem. This fixes
bug #1716.
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23656 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed warnings when building the bfs_shell.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@23462 a95241bf-73f2-0310-859d-f6bbb57e9c96

* bfs_{read|write}_pages() now only try to lock - this fixes a possible
deadlock whenever someone without a lock (like the page_writer()) is calling
this function.
* Added a new ReadWriteLock::TryLock() method.
* Renamed bfs_read_vnode() and bfs_release_vnode() to bfs_get_vnode() and
bfs_put_vnode() just like those functions are called in fs_interface.h.
* Fixed a warning in BPlusTree::_SplitNode().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22372 a95241bf-73f2-0310-859d-f6bbb57e9c96

Changes in BPlusTree::_SplitNode():
* Added check for invalid keyIndex parameter.
* Removed superfluous break condition in the second loop.
* Increment "out" in the second loop only when we have processed a key
that will end up in the node. Thus, after the loop, the variable will
contain the numbers of keys to be copied/moved, not that number + 1.
Adjusted later use of "out" accordingly, save in one place where it
was used incorrectly, which resulted in one key length and value to
many to be copied, thus occasionally causing a page fault (bug #1363).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@22195 a95241bf-73f2-0310-859d-f6bbb57e9c96

axeld + bonefish:
Fixed off-by-one error in the b+ tree code splitting a node, which could
result in a read beyond the block bounds thus causing a page fault. Was
nicely reproducible when unzipping big archives. Now bug #1003 seems to
be fixed for real.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21671 a95241bf-73f2-0310-859d-f6bbb57e9c96

replaced uint32 by addr_t where it applies to please gcc on x86_64


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21422 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a memory leak in _SplitNode() spotted by Stefano - thanks!


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21200 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Removed unused code when USER is defined - the fs_shell no longer does this, but
provides a kernel emulation layer.
* Renamed all private BPlusTree methods to have the '_' prefix.
* Removed useless set_sem_owner() from Lock.h - all semaphores created in the kernel
always belong to the system team automatically.
* Some cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@21054 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Prepared the BFS sources to be used with the new FS shell:
- Moved all inclusions of system headers into a new
system_dependencies.h header, which conditionally either includes
these or the FS shell headers.
- Fixed compiler warnings related to printf-like functions (int32 is
int, not long on non-BeOS platforms).
* Build a new bfs_shell. Compiles and links, but does nothing ATM.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@20860 a95241bf-73f2-0310-859d-f6bbb57e9c96

Porting r18992 to the R5 version of BFS (and therefore, bfs_shell used to build the
Haiku image) revealed a problem with that change:
* If the root node only contained a single entry it was freed instead of just making
it a leaf node - that could produce an invalid b+tree (could only happen with
attribute or index trees, as directories always contain '.' and '..').


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@19006 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a stupid bug found by accident:
* When removing the last key from a leaf node, the node wasn't freed, but just
emptied, and thus the whole tree structure would never combast.
* This could also cause a bug in the TreeIterator: if the last entry was not
in the last node, every second readdir() after the last one would return
the last entry again. I only found this because that happens to be what
Tracker does (which would run in an endless loop while scanning the directory
then).
* Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@18992 a95241bf-73f2-0310-859d-f6bbb57e9c96

* Imported PPC big endian fixes into Haiku's BFS.
* Fixed another issue in BPlusTree::RemoveKey().


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@17558 a95241bf-73f2-0310-859d-f6bbb57e9c96

added error tracing to help on bug #106


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@16498 a95241bf-73f2-0310-859d-f6bbb57e9c96

Better debug output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@16017 a95241bf-73f2-0310-859d-f6bbb57e9c96

Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15871 a95241bf-73f2-0310-859d-f6bbb57e9c96

A couple of endian fixes, inspired by Ingo - there might be some more left, though,
it's untested yet.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15693 a95241bf-73f2-0310-859d-f6bbb57e9c96

Slightly improved debug output.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@15656 a95241bf-73f2-0310-859d-f6bbb57e9c96

We now use the kernel's Stack class instead of our own copy.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14417 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a very stupid bug I introduced in r10056 (the Haiku-only switch):
CachedNode::Allocate() could return the wrong offset for the new node when
taken from the free node pool (it accidently returned the offset for the
next free node...).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14084 a95241bf-73f2-0310-859d-f6bbb57e9c96

Made CachedNode::SetTo[Header]() return a const node/header. Made some other methods
that were supposed to be const const as well.
Found one bug this way: in one case, a duplicate node might not have been part of a
transaction (and thus, was not written back). This bug only affected the Haiku version
of BFS, though.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14083 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed two bugs in BPlusTree::RemoveDuplicate():
- if the left duplicate node of a removed node was the last node, the "array" variable
still pointed to the old node when the loop was reentered which could lead to a tree
corruption.
- if the value to be removed could not be found in the fragment it should have been in,
the method still returned B_OK instead of B_ENTRY_NOT_FOUND.
Small cleanup, updated/improved comments.
Changed bplustree_node::FragmentsUsed() from int32 to uint32. Moved the calculation
of the maximal number of fragments in a node to the new bplustree_node::MaxFragments()
method.
If a bplustree_header is not valid, BPlusTree::SetTo() will now dump the header when
compiled with DEBUG defined.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14063 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed a bug I introduced when porting BFS to Haiku: when the file size of a BPlusTree
could be shrinked (because the last node was freed), the free node pointer of the
header was still accidently set to that node.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@14040 a95241bf-73f2-0310-859d-f6bbb57e9c96

If allocating a new node fails, the bplustree_header::maximum_size field is now
reseted to its old value.
BPlusTree::SetTo() is now less strict about maximum_size vs. inode size differences;
it will now print a warning and set the maximum_size to the inode size, even though
the tree might be corrupted (reading should always be as compatible and forgiving
as possible).


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13946 a95241bf-73f2-0310-859d-f6bbb57e9c96

Extended the node checker a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13944 a95241bf-73f2-0310-859d-f6bbb57e9c96

SeekDown() now prints out an error message when failing in a certain way (instead
of just using the RETURN_ERROR() macro).
Minor cleanup.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13878 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed warnings: possibly uninitialized variable, missing friend classifier (struct/class).


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@11558 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed debug build.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@10196 a95241bf-73f2-0310-859d-f6bbb57e9c96

Big update while moving over completely to the Haiku kernel:
- Ported over BFS to the new cache API
- Inode no longer inherits from CachedBlock, and therefore, no longer
keeps the whole inode block in memory. It now has a copy of the bfs_inode
structure in memory instead. This has a number of advantages but also some
disadvantages, so it might be reverted later, even if it's unlikely.
- Added a NodeGetter class that can be used whenever the real block needs
to be accessed (ie. for attributes)
- Changed *transaction to &transaction where possible
- Removed support for KEEP_WRONG_DIRENT_RECLEN
- Removed support for uncached file access since that's no longer needed
- Fixed some endian issues in bfs_write_stat()
- Removed the install BFS rules, since they don't make any sense anymore
(unless you are running Haiku ;-))

Note, logged streams are not supported anymore right now. Also, the
transaction code is pretty simple and slow - it will be improved later
on. Attribute code is pretty much untested in the new environment.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@10053 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed oddly indented comment.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7681 a95241bf-73f2-0310-859d-f6bbb57e9c96

It's now <util/kernel_cpp.h> rather than <kernel_cpp.h>.
Forgot to commit that...


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@7442 a95241bf-73f2-0310-859d-f6bbb57e9c96

Some minor style changes.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@6417 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added _PACKED to the on-disk structures.
Switched to kernel_cpp.h/cpp.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@6287 a95241bf-73f2-0310-859d-f6bbb57e9c96

Bunches of changes to make mwcc like the code. I also coded an _atomic_set() and _atomic_test_and_set() for PowerPC. Of course, there's already one in the kernel tree, but mine's better. :P Now builds (and works, after a fashion) on R5 PowerPC.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@5280 a95241bf-73f2-0310-859d-f6bbb57e9c96

The file system is now almost endian-aware.
Used lazy unreadable conversion: ==, !=, == 0, != 0 are endian-safe
and don't need byte swapping.
If the platform endian differs from the one selected at compile time,
it will mount all volumes read-only for now.
Uncomment BFS_BIG_ENDIAN_ONLY in the Jamfile to build the big endian
version under x86.
No matter on what platform, the compilation defaults to build BFS as
little endian file system (see bfs_endian.h for details).


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@4715 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added B_SSIZE_T_TYPE, B_SIZE_T_TYPE, B_OFF_T_TYPE to compareKeys().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@4713 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added a little more debug output in BPlusTree::Find().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@3393 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed all warnings that appeared with DEBUG=1 set.
Also fixed missing return codes in BufferPool::ReleaseBuffer() and Journal::WriteLogEntry().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2845 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed some warnings, and some minor style issues.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2836 a95241bf-73f2-0310-859d-f6bbb57e9c96

Added more checks in the BPlusTree implementation if DEBUG is defined.
The correctness of max_number_of_levels is now checked in Find().
Added a class NodeChecker which checks the integrity of the specified node
when the object is destructed (via new method bplustree_node::CheckIntegrity());
now used in Remove() and Insert().


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2169 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed the bug in the query code: B_MIME_STRING_TYPE was not correctly
translated into B_STRING_TYPE for the key comparison (it was translated
but not saved under the new type).
compareKeys() will now return -1 if it didn't know the type to compare.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2121 a95241bf-73f2-0310-859d-f6bbb57e9c96

Removed the usage of Inode::Name() in the debug output.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2080 a95241bf-73f2-0310-859d-f6bbb57e9c96

Switched from Inode::IsDirectory() to Inode::IsContainer() where necessary.
Now makes use of the changed Inode::Create() logic.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@2031 a95241bf-73f2-0310-859d-f6bbb57e9c96

Fixed the wrong maintainance of the max_number_of_levels field in the
B+tree's header.
Some style cleanups.


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@1870 a95241bf-73f2-0310-859d-f6bbb57e9c96

Initial revision


git-svn-id: file:///srv/svn/repos/haiku/trunk/current@639 a95241bf-73f2-0310-859d-f6bbb57e9c96