[PATCH v3] f2fs: combine nat_bits and free_nid_bitmap cache

[Chao Yu]

Both nat_bits cache and free_nid_bitmap cache provide same functionality
as a intermediate cache between free nid cache and disk, but with
different granularity of indicating free nid range, and different
persistence policy. nat_bits cache provides better persistence ability,
and free_nid_bitmap provides better granularity.

In this patch we combine advantage of both caches, so finally policy of
the intermediate cache would be:
- init: load free nid status from nat_bits into free_nid_bitmap
- lookup: scan free_nid_bitmap before load NAT blocks
- update: update free_nid_bitmap in real-time
- persistence: udpate and persist nat_bits in checkpoint

Signed-off-by: Chao Yu 
Signed-off-by: Jaegeuk Kim 
---
 fs/f2fs/node.c | 125 ++---
 1 file changed, 47 insertions(+), 78 deletions(-)

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 4b441cadd2ba..0a1ea59c9d31 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -332,9 +332,6 @@ static void set_node_addr(struct f2fs_sb_info *sbi, struct 
node_info *ni,
set_nat_flag(e, IS_CHECKPOINTED, false);
__set_nat_cache_dirty(nm_i, e);
 
-   if (enabled_nat_bits(sbi, NULL) && new_blkaddr == NEW_ADDR)
-   clear_bit_le(NAT_BLOCK_OFFSET(ni->nid), nm_i->empty_nat_bits);
-
/* update fsync_mark if its inode nat entry is still alive */
if (ni->nid != ni->ino)
e = __lookup_nat_cache(nm_i, ni->ino);
@@ -1818,7 +1815,7 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, 
nid_t nid)
 }
 
 void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
-   bool set, bool build)
+   bool set, bool build, bool locked)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
@@ -1832,12 +1829,14 @@ void update_free_nid_bitmap(struct f2fs_sb_info *sbi, 
nid_t nid,
else
__clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
 
-   spin_lock(_i->free_nid_lock);
+   if (!locked)
+   spin_lock(_i->free_nid_lock);
if (set)
nm_i->free_nid_count[nat_ofs]++;
else if (!build)
nm_i->free_nid_count[nat_ofs]--;
-   spin_unlock(_i->free_nid_lock);
+   if (!locked)
+   spin_unlock(_i->free_nid_lock);
 }
 
 static void scan_nat_page(struct f2fs_sb_info *sbi,
@@ -1866,7 +1865,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
if (blk_addr == NULL_ADDR)
freed = add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, freed, true);
+   update_free_nid_bitmap(sbi, start_nid, freed, true, false);
}
 }
 
@@ -1914,58 +1913,6 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
up_read(_i->nat_tree_lock);
 }
 
-static int scan_nat_bits(struct f2fs_sb_info *sbi)
-{
-   struct f2fs_nm_info *nm_i = NM_I(sbi);
-   struct page *page;
-   unsigned int i = 0;
-   nid_t nid;
-
-   if (!enabled_nat_bits(sbi, NULL))
-   return -EAGAIN;
-
-   down_read(_i->nat_tree_lock);
-check_empty:
-   i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
-   if (i >= nm_i->nat_blocks) {
-   i = 0;
-   goto check_partial;
-   }
-
-   for (nid = i * NAT_ENTRY_PER_BLOCK; nid < (i + 1) * NAT_ENTRY_PER_BLOCK;
-   nid++) {
-   if (unlikely(nid >= nm_i->max_nid))
-   break;
-   add_free_nid(sbi, nid, true);
-   }
-
-   if (nm_i->nid_cnt[FREE_NID_LIST] >= MAX_FREE_NIDS)
-   goto out;
-   i++;
-   goto check_empty;
-
-check_partial:
-   i = find_next_zero_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
-   if (i >= nm_i->nat_blocks) {
-   disable_nat_bits(sbi, true);
-   up_read(_i->nat_tree_lock);
-   return -EINVAL;
-   }
-
-   nid = i * NAT_ENTRY_PER_BLOCK;
-   page = get_current_nat_page(sbi, nid);
-   scan_nat_page(sbi, page, nid);
-   f2fs_put_page(page, 1);
-
-   if (nm_i->nid_cnt[FREE_NID_LIST] < MAX_FREE_NIDS) {
-   i++;
-   goto check_partial;
-   }
-out:
-   up_read(_i->nat_tree_lock);
-   return 0;
-}
-
 static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
@@ -1987,21 +1934,6 @@ static void __build_free_nids(struct f2fs_sb_info *sbi, 
bool sync, bool mount)
 
if (nm_i->nid_cnt[FREE_NID_LIST])
return;
-
-   /* try to find free nids with nat_bits */
-   if (!scan_nat_bits(sbi) && 

[PATCH v3] f2fs: combine nat_bits and free_nid_bitmap cache

[Chao Yu]

Both nat_bits cache and free_nid_bitmap cache provide same functionality
as a intermediate cache between free nid cache and disk, but with
different granularity of indicating free nid range, and different
persistence policy. nat_bits cache provides better persistence ability,
and free_nid_bitmap provides better granularity.

In this patch we combine advantage of both caches, so finally policy of
the intermediate cache would be:
- init: load free nid status from nat_bits into free_nid_bitmap
- lookup: scan free_nid_bitmap before load NAT blocks
- update: update free_nid_bitmap in real-time
- persistence: udpate and persist nat_bits in checkpoint

Signed-off-by: Chao Yu 
Signed-off-by: Jaegeuk Kim 
---
 fs/f2fs/node.c | 125 ++---
 1 file changed, 47 insertions(+), 78 deletions(-)

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 4b441cadd2ba..0a1ea59c9d31 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -332,9 +332,6 @@ static void set_node_addr(struct f2fs_sb_info *sbi, struct 
node_info *ni,
set_nat_flag(e, IS_CHECKPOINTED, false);
__set_nat_cache_dirty(nm_i, e);
 
-   if (enabled_nat_bits(sbi, NULL) && new_blkaddr == NEW_ADDR)
-   clear_bit_le(NAT_BLOCK_OFFSET(ni->nid), nm_i->empty_nat_bits);
-
/* update fsync_mark if its inode nat entry is still alive */
if (ni->nid != ni->ino)
e = __lookup_nat_cache(nm_i, ni->ino);
@@ -1818,7 +1815,7 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, 
nid_t nid)
 }
 
 void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
-   bool set, bool build)
+   bool set, bool build, bool locked)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
@@ -1832,12 +1829,14 @@ void update_free_nid_bitmap(struct f2fs_sb_info *sbi, 
nid_t nid,
else
__clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
 
-   spin_lock(_i->free_nid_lock);
+   if (!locked)
+   spin_lock(_i->free_nid_lock);
if (set)
nm_i->free_nid_count[nat_ofs]++;
else if (!build)
nm_i->free_nid_count[nat_ofs]--;
-   spin_unlock(_i->free_nid_lock);
+   if (!locked)
+   spin_unlock(_i->free_nid_lock);
 }
 
 static void scan_nat_page(struct f2fs_sb_info *sbi,
@@ -1866,7 +1865,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
if (blk_addr == NULL_ADDR)
freed = add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, freed, true);
+   update_free_nid_bitmap(sbi, start_nid, freed, true, false);
}
 }
 
@@ -1914,58 +1913,6 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
up_read(_i->nat_tree_lock);
 }
 
-static int scan_nat_bits(struct f2fs_sb_info *sbi)
-{
-   struct f2fs_nm_info *nm_i = NM_I(sbi);
-   struct page *page;
-   unsigned int i = 0;
-   nid_t nid;
-
-   if (!enabled_nat_bits(sbi, NULL))
-   return -EAGAIN;
-
-   down_read(_i->nat_tree_lock);
-check_empty:
-   i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
-   if (i >= nm_i->nat_blocks) {
-   i = 0;
-   goto check_partial;
-   }
-
-   for (nid = i * NAT_ENTRY_PER_BLOCK; nid < (i + 1) * NAT_ENTRY_PER_BLOCK;
-   nid++) {
-   if (unlikely(nid >= nm_i->max_nid))
-   break;
-   add_free_nid(sbi, nid, true);
-   }
-
-   if (nm_i->nid_cnt[FREE_NID_LIST] >= MAX_FREE_NIDS)
-   goto out;
-   i++;
-   goto check_empty;
-
-check_partial:
-   i = find_next_zero_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
-   if (i >= nm_i->nat_blocks) {
-   disable_nat_bits(sbi, true);
-   up_read(_i->nat_tree_lock);
-   return -EINVAL;
-   }
-
-   nid = i * NAT_ENTRY_PER_BLOCK;
-   page = get_current_nat_page(sbi, nid);
-   scan_nat_page(sbi, page, nid);
-   f2fs_put_page(page, 1);
-
-   if (nm_i->nid_cnt[FREE_NID_LIST] < MAX_FREE_NIDS) {
-   i++;
-   goto check_partial;
-   }
-out:
-   up_read(_i->nat_tree_lock);
-   return 0;
-}
-
 static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
@@ -1987,21 +1934,6 @@ static void __build_free_nids(struct f2fs_sb_info *sbi, 
bool sync, bool mount)
 
if (nm_i->nid_cnt[FREE_NID_LIST])
return;
-
-   /* try to find free nids with nat_bits */
-   if (!scan_nat_bits(sbi) && nm_i->nid_cnt[FREE_NID_LIST])
-   return;
-