Hi,
This patch set implements the tracking of live blocks in segments. This
information is crucial in implementing better GC policies, because
now the policies can make informed decisions about which segments have
the biggest number of reclaimable blocks.
The difficulty in tracking live blocks is the fact, that any block can
belong to any number of snapshots and snapshots can be deleted and
created at any time. A block belongs to a snapshot, if the checkpoint
number lies between de_start and de_end of the block. So if a new
snapshot is created, all the reclaimable blocks belonging to it are no
longer reclaimable and therefore the live block counter of the
corresponding segment must be incremented. Conversely if a snapshot is
removed, all the reclaimable blocks belonging to it should really be
counted as reclaimable again and the counter must be decremented. But if
one block belongs to two or more snapshots the counter must only be
incremented once for the first and decremented once for the last
snapshot.
To achieve this I used the de_rsv field of nilfs_dat_entry to store one
of the snapshot numbers. Every time a snapshot is created/removed the
whole DAT-File is scanned and de_rsv is updated if the snapshot number
is between de_start and de_end. But one block can belong to an
arbitrary number of snapshots. Here I use the fact, that the
snapshot list is organized as a sorted linked list. So by knowing the
previous and the next snapshot number it is possible to
reliably determine, if a block is reclaimable or belongs to another
snapshot.
It is of course unacceptable to update the whole DAT-File to create one
snapshot. So only reclaimable blocks are updated. But this leads to
certain situations, where the counters won't be accurate. The userspace
GC should be capable of compensating and correcting the inaccurate
values.
Another problem is the protection period in the userspace GC. The kernel
doesn't know anything about the userspace protection period, and it is
therefore not reflected in the number of live blocks in a segment. For
example if the GC policy chooses a segment that seems to have a lot of
reclaimable blocks, it could turn out, that all of those blocks are
still protected by the protection period.
To overcome this problem I added an additional field to su_lastdec to
the segment usage information. Whenever the number of live blocks in a
segment is adjusted su_lastdec is set to the current timestamp. If the
number of live blocks was adjusted within the protection period, then
the userspace GC policy can recognize it and choose a different segment.
Compatibility Issues:
1. su_nblocks is reused to represent the number of live blocks
old nilfs-utils would break the file system.
2. the vd_pad field of nilfs_vdesc was not initialized to 0
so old nilfs-utils could send arbitrary flags to the kernel
Benchmark Results:
The benchmark replays NFS-Traces to simulate a real file system load.
The file system is filled up to 20% capacity and then the NFS-Traces are
replayed. In parallel every 5 minutes random checkpoints are turned into
snapshots. After 15 minutes the snapshot is turned back into a
checkpoint.
Greedy-Policy-Runtime: 6221.712s
Cost-Benefit-Policy-Runtime: 6874.840s
Timestamp-Policy-Runtime: 13179.626s
Best regards,
Andreas Rohner
---
Andreas Rohner (6):
nilfs2: add helper function to go through all entries of meta data
file
nilfs2: add new timestamp to seg usage and function to change
su_nblocks
nilfs2: scan dat entries at snapshot creation/deletion time
nilfs2: add ioctl() to clean snapshot flags from dat entries
nilfs2: add counting of live blocks for blocks that are overwritten
nilfs2: add counting of live blocks for deleted files
fs/nilfs2/alloc.c | 121 +++++++++++++++++++++++++
fs/nilfs2/alloc.h | 6 ++
fs/nilfs2/bmap.c | 8 +-
fs/nilfs2/bmap.h | 2 +-
fs/nilfs2/btree.c | 3 +-
fs/nilfs2/cpfile.c | 7 ++
fs/nilfs2/dat.c | 225 +++++++++++++++++++++++++++++++++++++++++++++-
fs/nilfs2/dat.h | 32 ++++++-
fs/nilfs2/direct.c | 3 +-
fs/nilfs2/inode.c | 2 +
fs/nilfs2/ioctl.c | 109 +++++++++++++++++++++-
fs/nilfs2/mdt.c | 5 +-
fs/nilfs2/page.h | 6 +-
fs/nilfs2/segbuf.c | 25 ++++++
fs/nilfs2/segbuf.h | 4 +
fs/nilfs2/segment.c | 69 ++++++++++++--
fs/nilfs2/sufile.c | 86 +++++++++++++++++-
fs/nilfs2/sufile.h | 18 ++++
include/linux/nilfs2_fs.h | 65 +++++++++++++-
19 files changed, 772 insertions(+), 24 deletions(-)
--
1.9.0
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
