The paper I followed in the early days of the driver (before the
official reference was published) referred to record values as "data",
so some of my oldest code uses that name as well. This is inconsistent,
and not very clear because the word "data" shows up everywhere. Reword
all instances of this I can identify.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Gilgamesh reports via email that the following iozone benchmark is
failing:
./iozone -a -i 0 -r 1M -n 1g -g 1g -f /mnt/apfs/test
I've tried this myself on a small (3 GiB) filesystem, and it is the
commit after the unlink that fails, complaining about the main free
queue being full:
APFS (800010g): free queue has too many nodes (348 > 347) (apfs_free_queue_insert_nocache:849)
The problem is that random writes to a big file create a lot of extents,
and when the file is deleted they all get dumped to the main free queue
as separate records. The queue gets full and the commit fails.
Stop forcing file deletion to happen in a single transaction. Instead,
set up a workqueue whenever an orphan inode gets evicted, and leave the
cleanup for another time. Also allow the cleanup to execute only
partially (deleting the first extents like the official driver) and
reschedule itself (again via inode eviction).
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
When a query fails with ENODATA, the caller may still need to work with
the result (for instance to insert something in that location), but it
should never be confused for an actual valid record. Some changes I'm
working on trigger this problem regularly for apfs_query_found_extent(),
making it check stale records and report success. I need that function
to be reliable, so always clear the key and value lengths from queries
on failure.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
In pretty much all containers I've encountered so far, every objects has
a single block. There is an annoying exception though: containers with a
size between ~6.7 TiB and ~7.8 TiB have a multiblock spaceman. I have no
simple way to deal with this because my transactions currently handle
ephemeral objects very roughly, ignoring all the cpm metadata and just
updating each block in the expected header location.
Instead of trying to hack this in somehow, start doing the right thing
as explained in the official reference and keep all ephemeral objects in
memory at all times. So, when the first transaction starts, go through
the cpm metadata and read each object along with its size and oid. When
a new object gets created (or an old one gets deleted), all changes
happen in memory. On commit time, checksums are updated and all objects
get written to disk, but nothing neads to be read.
So this is all much cleaner, and I took this opportunity to support
multiple cpm blocks as well.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Running generic/013 for a few minutes still leaves the filesystem in a
corrupted state, with a missing inode record. This is another regression
caused by my big rework of the node split logic. When a single-record
node is needed but the parent update fails with -EAGAIN,
apfs_create_single_rec_node() leaves the query pointing to the aborted
new node. The refresh does not change this, so the inode record ends up
abandoned in this ghost node.
In then end all of this is caused by the weird way I originally designed
the query struct, which forces me to always keep a more or less valid
leaf query instead of just nuking the whole thing and starting over. I'd
like to change this eventually, but for now just adjust the cleanup for
apfs_create_single_rec_node().
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I'm encountering some rare failures in generic/075. The problem happens
when a node split is triggered by inserting a record into the first
position. The parent needs to get updated of course, but we've lost the
reference to it after the split, so the filesystem becomes corrupted.
The reality is that this stuff has always been too hacky, and new corner
cases keep popping up. Stop trying to guess which queries need to know
and might have forgotten their ancestors: just restart the whole btree
operation after any split, refreshing the query with a simple rerun.
This has to be the safest possible approach, and I don't expect it to
hurt performance, since node splits should never be a bottleneck.
Big changes are needed to get it to work though, because the b-tree must
be in a consistent state whenever the query gets refreshed. There are
two different considerations here. First, no split can take place unless
the parent has enough room to index the new child node; otherwise the
parent split would trigger a query refresh while half the child's
records are orphaned. To sum up, every cascade of node splits must
happen from root to leaf.
The second consideration is that, even if a node has enough room, no
updates related to the actual requested operation (the leaf record
insertion/deletion/replacement) can take place at any level until all
splits are done. A different policy would mean that a query refresh
might become necessary halfway through the operation, and so the leaf
record could be found to be unexpectedly missing, or covered by the
wrong index key.
So at a given level: the split, if needed, always comes first, followed
by the function call for parent updates, and only then the node gets
modified. After a split an EAGAIN error gets thrown, which then bubbles
back up to the leaf (either through the splits themselves, or through
the parent update calls), so only a single split can happen for the
whole b-tree on each refresh iteration - always at the highest possible
level in the split cascade that would have been triggered before this
patch. The btree, of course, remains valid on EAGAIN, and the leaf
records remain the same.
Inside apfs_node_split() itself, no changes to the old node can be done
until the new one is safely inserted in the b-tree. If that triggers a
split at a higher level, then the new node must be properly cleaned up
(making use of the recent changes to apfs_delete_node()) and, as usual,
EAGAIN must get bubbled up.
A similar cleanup needs to be take place in the one other function that
creates non-root nodes: apfs_create_single_rec_node(). The new
single-record node must be repeatedly destroyed until the parent manages
to index it without any splits.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Implement apfs_query_root() and use it to simplify two functions. It
will get reused further in the following patch, including inside node.c,
so don't make it static.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Currently node insertions/deletions are attempted immediately and they
return -ENOSPC when there is no room, letting the caller know that the
node needs to get split. But in future patches I'll need to reorder the
operations so that the node only gets updated after all the ancestors.
The previous patches already ensured that apfs_node_replace() will never
erroneously report lack of space, no matter how fragmented the node may
be. This was already true of apfs_node_insert(). So from now on we can
safely run space checks ahead of time with only the node metadata, use
that to decide if a split is needed, and only update the records after
all that is done.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Some changes I'm working on will require being able to delete nodes that
have not yet been indexed in a btree. This cannot be done with the
current version of apfs_delete_node(), because it handles the parent
node modifications itself. So from now on, let the caller handle that if
it's necessary. This is also more symmetrical with apfs_create_node(),
as would be expected.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I've been working on making some very needed changes to how node splits
work. The plan is to always rerun queries after a split, to keep the
query chain valid. One problem I've encountered while implementing this
is that the search key is not really preserved by apfs_update_inode().
We have a pointer to it, but it was allocated in the stack of some other
function, so the data is just noise.
I've always thought it was silly to allocate both a query and a key
before a lookup. Instead, turn the search key into a field within the
query structure, and copy it to the children as the query gets run. This
will ensure that the key remains available for future reruns.
One thing to note is that, while this simplifies most callers a little
bit, some of them still allocate a key in the stack and later copy it to
the query. I didn't want to make any big changes and risk introducing
bugs at this point, since I'm busy with other stuff.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I just noticed that df throws a "No data available" error if it's used
while a snapshot is mounted. The problem happens while gathering the
total number of used blocks: to iterate through the existing volume
superblocks, this requires working with the container omap, which we
otherwise only do for snapshots during mount. apfs_omap_lookup_block()
is written with the idea that snapshots will only call it for the volume
omap, and so it uses the snapshot xid to get the wanted (old) version of
the object. But for used space calculations we actually want the latest,
and in fact the container omap doesn't even have the old versions of the
volumes, so the call fails.
Reimplement apfs_omap_lookup_block() as a wrapper around a new
apfs_omap_lookup_block_with_xid() that uses the current snapshot
transaction, and use this to implement apfs_omap_lookup_newest_block()
to be used in this situation.
By the way, there was no output on dmesg when I discovered this bug.
That's no good, so add a new error message in here.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I was reading the list of deprecated interfaces at [0] and it mentions
that the use of BUG() and BUG_ON() is discouraged in the kernel, and
that we should be prepared to fail gracefully even for impossible
situations.
I definitely agree with this: so far I've used BUG_ON() to implement
ASSERT(), but in practice I always turn that into a WARN_ON() while
debugging. Just leave it as WARN_ON() permanently.
I also use BUG() in apfs_query_storage() to mark an impossible query
tree flag. I can't imagine how this would ever be reached, but still
keep going and return an invalid storage type. This way the error can
get reported later, after calling either apfs_create_node() or
apfs_read_node(), which have been modified to fail gracefully and
complain with apfs_alert() in this situation. I also considered putting
an assertion in apfs_query_storage(), but that would require reordering
apfs.h and it seems unnecessarily messy.
Warnings should not be abused either, because of the panic_on_warn
option. Replace our one call to WARN_ON(), inside apfs_btree_replace(),
with another apfs_alert(). This function was already failing gracefully.
[0]: https://docs.kernel.org/process/deprecated.html#zero-length-and-one-element-arrays
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Some code that wasn't originally written by me has a style that differs
slightly from the rest of the module. Since I've been refactoring
compress.c quite a lot lately, I have made the inconsistencies more
visible, so I think it's a good time to switch everything to the typical
kernel style.
For this purpose I'm running checkpatch.pl for the first time in years,
and it has detected a handful of other issues that I introduced myself.
Fix most of the issues now, but I prefer to leave the zero-length array
stuff for a separate patch.
For the record, at the moment I'm choosing to ignore style inconsistency
in the compression libraries, even in libzbitmap which I wrote myself. I
prefer to keep them as close to upstream as possible.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
The driver is much closer to being usable, so I might start getting
subtler bug reports soon. To make them easier to handle, put error
messages all over the place. I should have done this from the beginning,
but I guess I didn't fully understand the need back then.
From now my general policy will be to use apfs_warn() for user errors or
unsupported features; apfs_err() for things that are probably corruption
or io errors; and apfs_alert() for things that are most likely bugs.
These last two should be rare, so the same error/alert will be thrown by
several layers in the callstack to provide as much information as
possible. Be careful and don't flood the console on normal situations.
Also, make messages with a log level lower than warning output their
function name and line number, which I think will help debugging more
than the actual messages.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Add suport for reads from sealed volumes. The main differences are that
catalog index nodes are bigger, and that file extents are kept in a
separate tree.
Writes could in theory be supported as well, as we do in our internal
tool. It would probably be a bit too hacky though, so I'll wait to see
if anybody asks for it.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Define an in-memory omap structure to be shared by all mounts of the
same volume, including both the current transaction and the snapshots.
The on-disk omap is already shared by all of them, so this will make for
saner code.
The patch fixes two existing issues. One is a regression introduced by
39878b3753be ("Preserve omap records in snapshots"), which was causing
regular failures in generic/013 of xfstests. The problem was with the
hacky way in which I told apart container and volume omaps, by setting
sbi->s_vsb_raw to NULL before calling apfs_map_volume_super(); it seems
that the dentry cache or something needs this to be set at all times.
Now that the "latest_snap" field has been moved from the sbi to the omap
struct, we no longer need to handle containers and volumes differently:
container omaps are the same as volume omaps without snapshots.
The other issue is that snapshot mounts only read the location of the
omap root once (on mount), but subsequent writes to the volume will free
this original block and potentially allocate it for something else. I've
never seen this in practice yet, but I would expect the snapshot mount
to start complaining about filesystem corruption. Now that the omap root
node is shared by all mounts of the volume, this problem should be gone.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
In order to test the creation and preservation of snapshots, it's
important that we can actually check the contents ourselves. Add a new
'snap' mount option to specify the label of the wanted snapshot.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
With the previous patch in place we can now take snapshots, but they
become immediately corrupted when a new transaction begins and changes
the omap records. This happens even if file contents aren't modified,
so it becomes impossible to test this new functionality at all.
So, always preserve omap records that belong to a snapshot. For this
check, the disk layout provides om_most_recent_snap in the object map;
add a matching s_latest_snap field to the in-memory superblock structure
to make it easier to work with.
Bigger changes are needed in apfs_omap_lookup_block(), because we need
to work with an omap record's xid, which has so far mostly been ignored.
Replace apfs_bno_from_query() with a new apfs_omap_map_from_query()
which doesn't discard so much valuable metadata. This change also allows
us to start preserving the flags in the omap record, which may also be
important.
Another problem in apfs_omap_lookup_block() is that we need a way to
tell apart volume omaps from the container omap, which won't be affected
by snapshots. This is all a little hacky, and it would be much cleaner
if I had an in-memory omap struct to pass around instead of the root
nodes. I should look into that in the future.
With this patch in place, my fsck reports no corruption after a single
snapshot is created and the volume is unmounted.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I'm trying to build with "-W" for the first time, and it reports that
apfs_free_query() doesn't use the 'sb' parameter. Get rid of it.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
I've been trying to document functions in kernel-doc style since the
beginning, but I had never actually run the kernel-doc script. Fix two
issues with function parameters that were changed without updating the
comments. Also stop documenting multiple arguments in one line, which
doesn't seem to be allowed.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Get rid of the reference counting for in-memory nodes, which is just a
hacky way to avoid accidentally freeing root nodes that are remembered
by the superblock structure. Instead, never delete the root nodes as
part of apfs_free_query() and let the caller decide how to deal with
them.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Add a 'data' field to in-memory objects and point it to the buffer
head's 'b_data'; from now on, always access the data through this field
instead of the bh. To make sure I remembered to clean up all instances,
rename the buffer head in the object from 'bh' to 'o_bh'.
The point is to allow nodes to work with a data block that exists only
in memory, and the next patch will take advantage of this to improve
apfs_node_split(). Since objects that are not nodes will not need this
feature, only adjust the cleanup done in apfs_node_release() for now,
though maybe object cleanups should all be done in one place.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
There are two places in the code where I've neglected to check the
return value of apfs_alloc_query(). One is in apfs_btree_query(): this
was one of the first things I implemented years ago, so the mistake was
just inexperience. The second is in apfs_query_set_before_first(), a
more recent addition: I probably copied the code from apfs_btree_query()
withut a proper review.
Anyway, this would cause npd if apfs_alloc_query() failed, so add the
proper checks and cleanups.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
Profiling a full-disk rsync shows that the driver spends around 25% of
the time inside apfs_omap_lookup_block(). So, implement a simple cache
of recently needed mappings and use that for lookups when possible. The
number of slots in the cache (128) wasn't given much consideration, so
fine-tuning would be good in the future.
Signed-off-by: Ernesto A. Fernández <ernesto@corellium.com>
