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>

Fix a few more miscellaneous (harmless) Clang warnings.

BFS: CachedNode initialize members

Fixes CID 609586: Uninitialized members (UNINIT_CTOR)

Non-static class member "fWritable" is not initialized in this
constructor nor in any functions that it calls.

Also initialize fOffset and fBlockNumber to 0 for good measure.

BFS: Made bplustree_header::CheckNode() use const node.

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.

BPlusTree.h: Remove invalid forward declaration.

That forward declaration was actually a backward declaration, as
system_dependencies.h already included Stack.

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

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

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.

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.

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.

Minor whitespace cleanup.

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

* 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 some off_t's in on-disk structure definitions by fixed-size int64. I
couldn't bring myself to replace the types everywhere they are used, though.


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

* Don't use Inode::Remove() when the inode could not be opened, because it
actually relies on that.
* Instead, _RemoveInvalidNode() now manipulates the parent tree manually.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@31774 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

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

* 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

* 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

* 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

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

Extended the node checker a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13944 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

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

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 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

Added a BPlusTree::Remove() inline method for strings.
Style cleanups.


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

Added private non-implemented copy constructor and assignment operators
for many classes for the sake of completeness.
Added a Transaction::IsStarted() method to not let it look like as if the
transaction is started more than once.
Changes made after suggestions from Mike Nordell, again :-)


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

Initial revision


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

BFS: Made bplustree_header::CheckNode() use const node.

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.

BPlusTree.h: Remove invalid forward declaration.

That forward declaration was actually a backward declaration, as
system_dependencies.h already included Stack.

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

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

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.

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.

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.

Minor whitespace cleanup.

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

* 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 some off_t's in on-disk structure definitions by fixed-size int64. I
couldn't bring myself to replace the types everywhere they are used, though.


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

* Don't use Inode::Remove() when the inode could not be opened, because it
actually relies on that.
* Instead, _RemoveInvalidNode() now manipulates the parent tree manually.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@31774 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

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

* 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

* 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

* 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

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

Extended the node checker a bit.


git-svn-id: file:///srv/svn/repos/haiku/haiku/trunk@13944 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

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

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 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

Added a BPlusTree::Remove() inline method for strings.
Style cleanups.


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

Added private non-implemented copy constructor and assignment operators
for many classes for the sake of completeness.
Added a Transaction::IsStarted() method to not let it look like as if the
transaction is started more than once.
Changes made after suggestions from Mike Nordell, again :-)


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

Initial revision


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