during flush_nat_entries, we do:
1) gang_lookup a radix tree, find all the dirty nat_entry_set;
2) sort nat_entry_set by nat_entry_set->entry_cnt, in order to
write to journal as much as possible to avoid unnessary IO.
This patch optimize the look_up & sort algorithm by introducing an array:
f2fs_nm_info->dirty_set[NAT_ENTRY_PER_BLOCK+1];
(struct list_head dirty_set[NAT_ENTRY_PER_BLOCK + 1])
dirty_set[1] links all nat_entry_set whose entry_cnt is 1
dirty_set[2] links all nat_entry_set whose entry_cnt is 2
......
dirty_set[N] links all nat_entry_set whose entry_cnt is N
as one NAT block has NAT_ENTRY_PER_BLOCK entries at MOST, so there should NOT
be one nat_entry_set whose entry_cnt is larger than NAT_ENTRY_PER_BLOCK.
So it is enough for f2fs_nm_info->dirty_set to link all nat_entry_sets in
system.
Update:
we update nat_entry_set in real-time, e.g originally
nat_entry_set->entry_cnt is
1, and licked by dirty_set[1]; then call __set_nat_cache_dirty to increase
nat_entry'sentry_cnt, we move this nat_entry_set ot dirty_set[2]'s tail, no
need to compare.
Flush:
when flush dirty nat_entry_set, we just flush nat_entry_set from
f2fs_nm_info->dirty_set[0] to f2fs_nm_info->dirty_set[NAT_ENTRY_PER_BLOCK],
where
gang_lookup and sort can be avoid.
footprint of this algorithm: sizeof(struct list_head)*NAT_ENTRY_PER_BLOCK
= 8*455 = 3.6k bytes
Signed-off-by: Hou Pengyang <houpengy...@huawei.com>
---
fs/f2fs/f2fs.h | 2 ++
fs/f2fs/node.c | 56 ++++++++++++++++++++++----------------------------------
2 files changed, 24 insertions(+), 34 deletions(-)
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 093d68a..88a96bb 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -628,6 +628,8 @@ struct f2fs_nm_info {
/* for checkpoint */
char *nat_bitmap; /* NAT bitmap pointer */
+ /* list dirty_set whose */
+ struct list_head dirty_set[NAT_ENTRY_PER_BLOCK + 1]; /* for */
unsigned int nat_bits_blocks; /* # of nat bits blocks */
unsigned char *nat_bits; /* NAT bits blocks */
diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index d22db8c..340c33d 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -174,13 +174,14 @@ static void __set_nat_cache_dirty(struct f2fs_nm_info
*nm_i,
list_move_tail(&ne->list, &head->entry_list);
nm_i->dirty_nat_cnt++;
head->entry_cnt++;
+ list_move_tail(&head->set_list, &(nm_i->dirty_set[head->entry_cnt]));
set_nat_flag(ne, IS_DIRTY, true);
}
static void __clear_nat_cache_dirty(struct f2fs_nm_info *nm_i,
struct nat_entry_set *set, struct nat_entry *ne)
{
- list_move_tail(&ne->list, &nm_i->nat_entries);
+ list_move_tail(&ne->list, &nm_i->nat_entries); /* to be shrinked */
set_nat_flag(ne, IS_DIRTY, false);
set->entry_cnt--;
nm_i->dirty_nat_cnt--;
@@ -2340,24 +2341,6 @@ static void remove_nats_in_journal(struct f2fs_sb_info
*sbi)
up_write(&curseg->journal_rwsem);
}
-static void __adjust_nat_entry_set(struct nat_entry_set *nes,
- struct list_head *head, int max)
-{
- struct nat_entry_set *cur;
-
- if (nes->entry_cnt >= max)
- goto add_out;
-
- list_for_each_entry(cur, head, set_list) {
- if (cur->entry_cnt >= nes->entry_cnt) {
- list_add(&nes->set_list, cur->set_list.prev);
- return;
- }
- }
-add_out:
- list_add_tail(&nes->set_list, head);
-}
-
static void __update_nat_bits(struct f2fs_sb_info *sbi, nid_t start_nid,
struct page *page)
{
@@ -2460,9 +2443,11 @@ static void __flush_nat_entry_set(struct f2fs_sb_info
*sbi,
/* Allow dirty nats by node block allocation in write_begin */
if (!set->entry_cnt) {
+ list_del(&set->set_list);
radix_tree_delete(&NM_I(sbi)->nat_set_root, set->set);
kmem_cache_free(nat_entry_set_slab, set);
- }
+ } else
+ f2fs_bug_on(sbi, 1);
