nilfs2: extend SUFILE on-disk format to enable counting of live blocks

This patch extends the nilfs_segment_usage structure with two extra
fields. This changes the on-disk format of the SUFILE, but the nilfs2
metadata files are flexible enough, so that there are no compatibility
issues. The extension is fully backwards compatible. Nevertheless a
feature compatibility flag was added to indicate the on-disk format
change.

The new field su_nlive_blks is used to track the number of live blocks
in the corresponding segment. Its value should always be smaller than
su_nblocks, which contains the total number of blocks in the segment.

The field su_nlive_lastmod is necessary because of the protection period
used by the GC. It is a timestamp, which contains the last time
su_nlive_blks was modified. For example if a file is deleted, its
blocks are subtracted from su_nlive_blks and are therefore considered to
be reclaimable by the kernel. But the GC additionally protects them with
the protection period. So while su_nilve_blks contains the number of
potentially reclaimable blocks, the actual number depends on the
protection period. To enable GC policies to effectively choose or prefer
segments with unprotected blocks, the timestamp in su_nlive_lastmod is
necessary.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: add function to modify su_nlive_blks

This patch adds a function to modify the su_nlive_blks field of the
nilfs_segment_usage structure in the SUFILE. By using positive or
negative integers, it is possible to add and substract any value from
the su_nlive_blks field.

The use of a modification cache is optional and by passing a NULL
pointer the value will be added or subtracted directly. Otherwise it is
necessary to call nilfs_sufile_flush_nlive_blks() at some point to make
the modifications persistent.

The modification cache is useful, because it allows for small values,
like simple increments and decrements, to be added up before writing
them to the SUFILE.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: add simple tracking of block deletions and updates

This patch adds simple tracking of block deletions and updates for
all files except the DAT- and the SUFILE-Metadatafiles. It uses the
fact, that for every block, NILFS2 keeps an entry in the DAT-File
and stores the checkpoint where it was created and deleted or
overwritten. So whenever a block is deleted or overwritten
nilfs_dat_commit_end() is called to update the DAT-Entry. At this
point this patch simply decrements the su_nlive_blks field of the
corresponding segment. The value of su_nlive_blks is set at segment
creation time.

The blocks of the DAT-File cannot be counted this way, because it
does not contain any entries about itself, so the function
nilfs_dat_commit_end() is not called when its blocks are deleted or
overwritten.

The SUFILE cannot be counted this way, because it would lead to a
deadlock. When nilfs_dat_commit_end() is called, the bmap->b_sem is
held by code way up the call chain. To decrement the SUFILE entry
the same semaphore has to be aquired. So if the DAT-Entry belongs to
the SUFILE both semaphores are the same and a deadlock will occur.
But it works for any other file. So by excluding the SUFILE from
being counted by the extra parameter count_blocks a deadlock can be
avoided.

With the above changes the code does not pass the lock dependency
checks of the kernel, because all the locks have the same class and
the order in which the locks are taken is different. Usually it is:

1. down_write(&NILFS_MDT(sufile)->mi_sem);
2. down_write(&bmap->b_sem);

Now it can also be reversed, which leads to failed checks:

1. down_write(&bmap->b_sem); /* lock of a file other than SUFILE */
2. down_write(&NILFS_MDT(sufile)->mi_sem);

But this is safe as long as the first lock down_write(&bmap->b_sem)
doesn't belong to the SUFILE.

It is also possible, that two bmap->b_sem locks have to be taken at
the same time:

1. down_write(&bmap->b_sem); /* lock of a file other than SUFILE */
2. down_write(&bmap->b_sem); /* lock of SUFILE */

Since bmap->b_sem of normal files and the bmap->b_sem of the
SUFILE have the same lock class, the above behavior would also lead
to a warning.

Because of this, it is necessary to introduce two new lock classes
for the SUFILE. So the bmap->b_sem of the SUFILE gets its own lock
class and the NILFS_MDT(sufile)->mi_sem as well.

A new feature compatibility flag
NILFS_FEATURE_COMPAT_TRACK_LIVE_BLKS was added, so that the new
features introduced by this patch can be enabled or disabled at any
time.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: use modification cache to improve performance

This patch adds a small cache to accumulate the small decrements of
the number of live blocks in a segment usage entry. If for example a
large file is deleted, the segment usage entry has to be updated for
every single block. But for every decrement, a MDT write lock has to
be aquired, which blocks the entire SUFILE and effectively turns
this lock into a global lock for the whole file system.

The cache tries to ameliorate this situation by adding up the
decrements and increments for a given number of segments and
applying the changes all at once. Because the changes are
accumulated in memory and not immediately written to the SUFILE, the
afore mentioned lock only needs to be aquired, if the cache is full
or at the end of the respective operation.

To effectively get the pointer to the modification cache from the
high level operations down to the update of the individual blocks in
nilfs_dat_commit_end(), a new pointer b_private was added to struct
nilfs_bmap.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: add additional flags for nilfs_vdesc

This patch adds support for additional bit-flags to the
nilfs_vdesc structure used by the GC to communicate block
information from userspace. The field vd_flags cannot be used for
this purpose, because it does not support bit-flags, and changing
that would break backwards compatibility. Therefore the padding
field is renamed to vd_blk_flags to contain more flags.

Unfortunately older versions of the userspace tools do not
initialize the padding field to zero. So it is necessary to signal
to the kernel if the new vd_blk_flags field contains usable flags
or just random data. Since the vd_period field is only used in
userspace, and is guaranteed to contain a value that is > 0
(NILFS_CNO_MIN == 1), it can be used to give the kernel a hint. So
if the userspace tools set vd_period.p_start to 0, the
vd_blk_flags field will be interpreted.

To make the flags available for later stages of the GC process,
they are mapped to corresponding buffer_head flags.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: improve accuracy and correct for invalid GC values

This patch improves the accuracy of the su_nlive_blks segment
usage field by also counting the blocks of the DAT-File. A block in
the DAT-File is considered reclaimable as soon as it is overwritten.
There is no need to consider protection periods, snapshots or
checkpoints. So whenever a block is overwritten during segment
construction, the segment usage information of the segment at the
previous location of the block is decremented. To get the previous
location of the block the b_blocknr field of the buffer_head
structure is used.

SUFILE blocks are counted in a similar way, but if the GC reads a
block into a GC inode, that already is in the cache, then there are
two versions of the block. If this happens both versions will be
counted, which can lead to small seemingly random incorrect values.
But it is better to accept these small inaccuracies than to not
count the SUFILE at all. These inaccuracies do not occur for the
DAT-File, because it does not need a GC inode.

Additionally the blocks that belong to a GC inode are rechecked if
they are reclaimable. If so the corresponding counter is
decremented. The blocks were already checked in userspace, but
without the proper locking. It is furthermore possible, that blocks
become reclaimable during the cleaning process. For example by
deleting checkpoints. To improve the performance of these extra
checks, flags from userspace are used to determine reclaimability.
If a block belongs to a snapshot it cannot be reclaimable and if
it is within the protection period it must be counted as
reclaimable.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: scan dat entries at snapshot creation/deletion time

To accurately count the number of live blocks in a segment, it is
important to take snapshots into account, because snapshots can
protect reclaimable blocks from being cleaned.

This patch uses the previously reserved de_rsv (renamed to de_ss)
field of the nilfs_dat_entry structure to store one of the snapshots
the corresponding block belongs to. One block can belong to many
snapshots, but there is no need to know all of them. It suffices to
know, that it belongs to one or more snapshots.

If however the snapshot stored in the de_ss field is deleted,
we need to check if the block belongs to any other snapshot. When a
snapshot is created it is stored in a sorted linked list and when it
is deleted the previous and next elements of this list are known.
Because the list is sorted we only have to check the block against the
previous and the next element to determine if it is reclaimable or
not.

For example if the current snapshot (in de_ss) is being removed
and neither the previous nor the next snapshot is in the range of
de_start to de_end, then it is guaranteed that the block doesn't
belong to any other snapshot and is reclaimable. On the other hand
if lets say the previous snapshot is in the range of de_start to
de_end, simply set de_ss to the previous snapshot and the block is
not reclaimable.

If a block is reclaimable, de_ss is set to the special value
NILFS_ENTRY_DEC, indicating that the corresponding SUFILE entry was
decremented and does not need to be decremented again in the future.
If a block on the other hand is not reclaimable, de_ss is set either
to a snapshot number or to NILFS_ENTRY_INC.

To implement this every DAT entry is scanned at snapshot
creation/deletion time and updated if needed. To avoid too many
update operations only potentially reclaimable blocks are ever
updated. For example if there are some deleted files and the
checkpoint to which these files belong is turned into a snapshot,
then su_nlive_blks is incremented for these blocks, which reverses
the decrement that happen when the files were deleted. If after
some time this snapshot is deleted, su_nlive_blks is decremented
again to reverse the previous increment.

It is important to note, that the GC effectively resets the segment
usage information by collecting blocks from different locations and
moving them to a new segment. Therefore the flags NILFS_ENTRY_INC and
NILFS_ENTRY_DEC have to be updated accordingly.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>
nilfs2: add ioctl() to update snapshot flags of DAT-Entries

A normal GC operation entails the moving of blocks to a new segment,
whereby the block number in de_blocknr and the value of de_ss are
updated.

By using NILFS_IOCTL_SET_SUINFO the GC can set the su_nlive_blks field
to any value, without moving any blocks. While in this case the
de_blocknr does not have to be updated the de_ss field may still be
invalidated if it contains the NILFS_ENTRY_DEC flag. NILFS_ENTRY_DEC
means, that the corresponding value in su_nlive_blks for this entry
was already decremented and does not have to be decremented again. But
NILFS_IOCTL_SET_SUINFO effectivly incremented the value, so the flags
have to be updated to reflect this change.

To update these flags, this patch introduces a new ioctl
NILFS_IOCTL_SET_INC_FLAGS, which can be used to flip the de_ss value
from NILFS_ENTRY_DEC to NILFS_ENTRY_INC.

Signed-off-by: Andreas Rohner <andreas.rohner@gmx.net>