Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

Hi Jaegeuk,

On 2017/3/2 3:35, Jaegeuk Kim wrote:
> Hi Chao,
> 
> BTW, we need to add a shrinker for this as well, right?

Hmm...do we really have to?

As at most we will have 3900 NAT blocks, so
a. free_nid_bitmap: 3900 * 57 = ~217 KB
b. nat_block_bitmap:3900 / 8 = ~487 BYTE
c. free_nid_count:  3900 * 2 = ~7 KB

Thanks,

> 
> Thanks,
> 
> On 02/23, Chao Yu wrote:
>> In scenario of intensively node allocation, free nids will be ran out
>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>> in worse case, if NAT blocks does not be cached in memory, it generates
>> IOs which slows down our foreground operations.
>>
>> In order to speed up node allocation, in this patch we introduce a new
>> free_nid_bitmap array, so there is an bitmap table for each NAT block,
>> Once the NAT block is loaded, related bitmap cache will be switched on,
>> and bitmap will be set during traversing nat entries in NAT block, later
>> we can query and update nid usage status in memory completely.
>>
>> With such implementation, I expect performance of node allocation can be
>> improved in the long-term after filesystem image is mounted.
>>
>> Signed-off-by: Chao Yu 
>> ---
>>  fs/f2fs/debug.c |   2 +
>>  fs/f2fs/f2fs.h  |   2 +
>>  fs/f2fs/node.c  | 109 
>> ++--
>>  include/linux/f2fs_fs.h |   1 +
>>  4 files changed, 111 insertions(+), 3 deletions(-)
>>
>> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
>> index 015ad2b73a92..a77df377e2e8 100644
>> --- a/fs/f2fs/debug.c
>> +++ b/fs/f2fs/debug.c
>> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>>  si->base_mem += sizeof(struct f2fs_nm_info);
>>  si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>>  si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
>> +si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
>> +si->base_mem += NM_I(sbi)->nat_blocks / 8;
>>  
>>  get_cache:
>>  si->cache_mem = 0;
>> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
>> index 1c9f0cc8f027..6a48e649bfef 100644
>> --- a/fs/f2fs/f2fs.h
>> +++ b/fs/f2fs/f2fs.h
>> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>>  unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>>  spinlock_t nid_list_lock;   /* protect nid lists ops */
>>  struct mutex build_lock;/* lock for build free nids */
>> +unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
>> +unsigned char *nat_block_bitmap;
>>  
>>  /* for checkpoint */
>>  char *nat_bitmap;   /* NAT bitmap pointer */
>> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
>> index b63bdb85ad66..f0f036c2d2fc 100644
>> --- a/fs/f2fs/node.c
>> +++ b/fs/f2fs/node.c
>> @@ -1821,14 +1821,32 @@ static void remove_free_nid(struct f2fs_sb_info 
>> *sbi, nid_t nid)
>>  kmem_cache_free(free_nid_slab, i);
>>  }
>>  
>> +void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid, bool set)
>> +{
>> +struct f2fs_nm_info *nm_i = NM_I(sbi);
>> +unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
>> +unsigned int nid_ofs = nid - START_NID(nid);
>> +
>> +if (!test_bit_le(nat_ofs, nm_i->nat_block_bitmap))
>> +return;
>> +
>> +if (set)
>> +set_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
>> +else
>> +clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
>> +}
>> +
>>  static void scan_nat_page(struct f2fs_sb_info *sbi,
>>  struct page *nat_page, nid_t start_nid)
>>  {
>>  struct f2fs_nm_info *nm_i = NM_I(sbi);
>>  struct f2fs_nat_block *nat_blk = page_address(nat_page);
>>  block_t blk_addr;
>> +unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
>>  int i;
>>  
>> +set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
>> +
>>  i = start_nid % NAT_ENTRY_PER_BLOCK;
>>  
>>  for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
>> @@ -1840,7 +1858,51 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>>  f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>>  if (blk_addr == NULL_ADDR)
>>  add_free_nid(sbi, start_nid, true);
>> +update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
>> +}
>> +}
>> +
>> +static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
>> +{
>> +struct f2fs_nm_info *nm_i = NM_I(sbi);
>> +struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
>> +struct f2fs_journal *journal = curseg->journal;
>> +unsigned int i, idx;
>> +unsigned int target = FREE_NID_PAGES * NAT_ENTRY_PER_BLOCK;
>> +
>> +down_read(_i->nat_tree_lock);
>> +
>> +for (i = 0; i < nm_i->nat_blocks; i++) {
>> +if (!test_bit_le(i, nm_i->nat_block_bitmap))
>> +continue;
>> +for (idx = 0; idx < NAT_ENTRY_PER_BLOCK; idx++) {
>> +nid_t nid;
>> +
>> +if (!test_bit_le(idx, 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

Hi Jaegeuk,

On 2017/3/2 3:35, Jaegeuk Kim wrote:
> Hi Chao,
> 
> BTW, we need to add a shrinker for this as well, right?

Hmm...do we really have to?

As at most we will have 3900 NAT blocks, so
a. free_nid_bitmap: 3900 * 57 = ~217 KB
b. nat_block_bitmap:3900 / 8 = ~487 BYTE
c. free_nid_count:  3900 * 2 = ~7 KB

Thanks,

> 
> Thanks,
> 
> On 02/23, Chao Yu wrote:
>> In scenario of intensively node allocation, free nids will be ran out
>> soon, then it needs to stop to load free nids by traversing NAT blocks,
>> in worse case, if NAT blocks does not be cached in memory, it generates
>> IOs which slows down our foreground operations.
>>
>> In order to speed up node allocation, in this patch we introduce a new
>> free_nid_bitmap array, so there is an bitmap table for each NAT block,
>> Once the NAT block is loaded, related bitmap cache will be switched on,
>> and bitmap will be set during traversing nat entries in NAT block, later
>> we can query and update nid usage status in memory completely.
>>
>> With such implementation, I expect performance of node allocation can be
>> improved in the long-term after filesystem image is mounted.
>>
>> Signed-off-by: Chao Yu 
>> ---
>>  fs/f2fs/debug.c |   2 +
>>  fs/f2fs/f2fs.h  |   2 +
>>  fs/f2fs/node.c  | 109 
>> ++--
>>  include/linux/f2fs_fs.h |   1 +
>>  4 files changed, 111 insertions(+), 3 deletions(-)
>>
>> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
>> index 015ad2b73a92..a77df377e2e8 100644
>> --- a/fs/f2fs/debug.c
>> +++ b/fs/f2fs/debug.c
>> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>>  si->base_mem += sizeof(struct f2fs_nm_info);
>>  si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>>  si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
>> +si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
>> +si->base_mem += NM_I(sbi)->nat_blocks / 8;
>>  
>>  get_cache:
>>  si->cache_mem = 0;
>> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
>> index 1c9f0cc8f027..6a48e649bfef 100644
>> --- a/fs/f2fs/f2fs.h
>> +++ b/fs/f2fs/f2fs.h
>> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>>  unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>>  spinlock_t nid_list_lock;   /* protect nid lists ops */
>>  struct mutex build_lock;/* lock for build free nids */
>> +unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
>> +unsigned char *nat_block_bitmap;
>>  
>>  /* for checkpoint */
>>  char *nat_bitmap;   /* NAT bitmap pointer */
>> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
>> index b63bdb85ad66..f0f036c2d2fc 100644
>> --- a/fs/f2fs/node.c
>> +++ b/fs/f2fs/node.c
>> @@ -1821,14 +1821,32 @@ static void remove_free_nid(struct f2fs_sb_info 
>> *sbi, nid_t nid)
>>  kmem_cache_free(free_nid_slab, i);
>>  }
>>  
>> +void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid, bool set)
>> +{
>> +struct f2fs_nm_info *nm_i = NM_I(sbi);
>> +unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
>> +unsigned int nid_ofs = nid - START_NID(nid);
>> +
>> +if (!test_bit_le(nat_ofs, nm_i->nat_block_bitmap))
>> +return;
>> +
>> +if (set)
>> +set_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
>> +else
>> +clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
>> +}
>> +
>>  static void scan_nat_page(struct f2fs_sb_info *sbi,
>>  struct page *nat_page, nid_t start_nid)
>>  {
>>  struct f2fs_nm_info *nm_i = NM_I(sbi);
>>  struct f2fs_nat_block *nat_blk = page_address(nat_page);
>>  block_t blk_addr;
>> +unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
>>  int i;
>>  
>> +set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
>> +
>>  i = start_nid % NAT_ENTRY_PER_BLOCK;
>>  
>>  for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
>> @@ -1840,7 +1858,51 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>>  f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>>  if (blk_addr == NULL_ADDR)
>>  add_free_nid(sbi, start_nid, true);
>> +update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
>> +}
>> +}
>> +
>> +static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
>> +{
>> +struct f2fs_nm_info *nm_i = NM_I(sbi);
>> +struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
>> +struct f2fs_journal *journal = curseg->journal;
>> +unsigned int i, idx;
>> +unsigned int target = FREE_NID_PAGES * NAT_ENTRY_PER_BLOCK;
>> +
>> +down_read(_i->nat_tree_lock);
>> +
>> +for (i = 0; i < nm_i->nat_blocks; i++) {
>> +if (!test_bit_le(i, nm_i->nat_block_bitmap))
>> +continue;
>> +for (idx = 0; idx < NAT_ENTRY_PER_BLOCK; idx++) {
>> +nid_t nid;
>> +
>> +if (!test_bit_le(idx, 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

Hi Chao,

BTW, we need to add a shrinker for this as well, right?

Thanks,

On 02/23, Chao Yu wrote:
> In scenario of intensively node allocation, free nids will be ran out
> soon, then it needs to stop to load free nids by traversing NAT blocks,
> in worse case, if NAT blocks does not be cached in memory, it generates
> IOs which slows down our foreground operations.
> 
> In order to speed up node allocation, in this patch we introduce a new
> free_nid_bitmap array, so there is an bitmap table for each NAT block,
> Once the NAT block is loaded, related bitmap cache will be switched on,
> and bitmap will be set during traversing nat entries in NAT block, later
> we can query and update nid usage status in memory completely.
> 
> With such implementation, I expect performance of node allocation can be
> improved in the long-term after filesystem image is mounted.
> 
> Signed-off-by: Chao Yu 
> ---
>  fs/f2fs/debug.c |   2 +
>  fs/f2fs/f2fs.h  |   2 +
>  fs/f2fs/node.c  | 109 
> ++--
>  include/linux/f2fs_fs.h |   1 +
>  4 files changed, 111 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
> index 015ad2b73a92..a77df377e2e8 100644
> --- a/fs/f2fs/debug.c
> +++ b/fs/f2fs/debug.c
> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>   si->base_mem += sizeof(struct f2fs_nm_info);
>   si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>   si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
> + si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
> + si->base_mem += NM_I(sbi)->nat_blocks / 8;
>  
>  get_cache:
>   si->cache_mem = 0;
> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
> index 1c9f0cc8f027..6a48e649bfef 100644
> --- a/fs/f2fs/f2fs.h
> +++ b/fs/f2fs/f2fs.h
> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>   unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>   spinlock_t nid_list_lock;   /* protect nid lists ops */
>   struct mutex build_lock;/* lock for build free nids */
> + unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
> + unsigned char *nat_block_bitmap;
>  
>   /* for checkpoint */
>   char *nat_bitmap;   /* NAT bitmap pointer */
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index b63bdb85ad66..f0f036c2d2fc 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -1821,14 +1821,32 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, 
> nid_t nid)
>   kmem_cache_free(free_nid_slab, i);
>  }
>  
> +void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid, bool set)
> +{
> + struct f2fs_nm_info *nm_i = NM_I(sbi);
> + unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
> + unsigned int nid_ofs = nid - START_NID(nid);
> +
> + if (!test_bit_le(nat_ofs, nm_i->nat_block_bitmap))
> + return;
> +
> + if (set)
> + set_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
> + else
> + clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
> +}
> +
>  static void scan_nat_page(struct f2fs_sb_info *sbi,
>   struct page *nat_page, nid_t start_nid)
>  {
>   struct f2fs_nm_info *nm_i = NM_I(sbi);
>   struct f2fs_nat_block *nat_blk = page_address(nat_page);
>   block_t blk_addr;
> + unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
>   int i;
>  
> + set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
> +
>   i = start_nid % NAT_ENTRY_PER_BLOCK;
>  
>   for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> @@ -1840,7 +1858,51 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>   if (blk_addr == NULL_ADDR)
>   add_free_nid(sbi, start_nid, true);
> + update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> + }
> +}
> +
> +static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
> +{
> + struct f2fs_nm_info *nm_i = NM_I(sbi);
> + struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
> + struct f2fs_journal *journal = curseg->journal;
> + unsigned int i, idx;
> + unsigned int target = FREE_NID_PAGES * NAT_ENTRY_PER_BLOCK;
> +
> + down_read(_i->nat_tree_lock);
> +
> + for (i = 0; i < nm_i->nat_blocks; i++) {
> + if (!test_bit_le(i, nm_i->nat_block_bitmap))
> + continue;
> + for (idx = 0; idx < NAT_ENTRY_PER_BLOCK; idx++) {
> + nid_t nid;
> +
> + if (!test_bit_le(idx, nm_i->free_nid_bitmap[i]))
> + continue;
> +
> + nid = i * NAT_ENTRY_PER_BLOCK + idx;
> + add_free_nid(sbi, nid, true);
> +
> + if (nm_i->nid_cnt[FREE_NID_LIST] >= target)
> + goto out;
> + }
> + }
> +out:
> 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

Hi Chao,

BTW, we need to add a shrinker for this as well, right?

Thanks,

On 02/23, Chao Yu wrote:
> In scenario of intensively node allocation, free nids will be ran out
> soon, then it needs to stop to load free nids by traversing NAT blocks,
> in worse case, if NAT blocks does not be cached in memory, it generates
> IOs which slows down our foreground operations.
> 
> In order to speed up node allocation, in this patch we introduce a new
> free_nid_bitmap array, so there is an bitmap table for each NAT block,
> Once the NAT block is loaded, related bitmap cache will be switched on,
> and bitmap will be set during traversing nat entries in NAT block, later
> we can query and update nid usage status in memory completely.
> 
> With such implementation, I expect performance of node allocation can be
> improved in the long-term after filesystem image is mounted.
> 
> Signed-off-by: Chao Yu 
> ---
>  fs/f2fs/debug.c |   2 +
>  fs/f2fs/f2fs.h  |   2 +
>  fs/f2fs/node.c  | 109 
> ++--
>  include/linux/f2fs_fs.h |   1 +
>  4 files changed, 111 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
> index 015ad2b73a92..a77df377e2e8 100644
> --- a/fs/f2fs/debug.c
> +++ b/fs/f2fs/debug.c
> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>   si->base_mem += sizeof(struct f2fs_nm_info);
>   si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>   si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
> + si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
> + si->base_mem += NM_I(sbi)->nat_blocks / 8;
>  
>  get_cache:
>   si->cache_mem = 0;
> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
> index 1c9f0cc8f027..6a48e649bfef 100644
> --- a/fs/f2fs/f2fs.h
> +++ b/fs/f2fs/f2fs.h
> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>   unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>   spinlock_t nid_list_lock;   /* protect nid lists ops */
>   struct mutex build_lock;/* lock for build free nids */
> + unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
> + unsigned char *nat_block_bitmap;
>  
>   /* for checkpoint */
>   char *nat_bitmap;   /* NAT bitmap pointer */
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index b63bdb85ad66..f0f036c2d2fc 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -1821,14 +1821,32 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, 
> nid_t nid)
>   kmem_cache_free(free_nid_slab, i);
>  }
>  
> +void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid, bool set)
> +{
> + struct f2fs_nm_info *nm_i = NM_I(sbi);
> + unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
> + unsigned int nid_ofs = nid - START_NID(nid);
> +
> + if (!test_bit_le(nat_ofs, nm_i->nat_block_bitmap))
> + return;
> +
> + if (set)
> + set_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
> + else
> + clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
> +}
> +
>  static void scan_nat_page(struct f2fs_sb_info *sbi,
>   struct page *nat_page, nid_t start_nid)
>  {
>   struct f2fs_nm_info *nm_i = NM_I(sbi);
>   struct f2fs_nat_block *nat_blk = page_address(nat_page);
>   block_t blk_addr;
> + unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
>   int i;
>  
> + set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
> +
>   i = start_nid % NAT_ENTRY_PER_BLOCK;
>  
>   for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> @@ -1840,7 +1858,51 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>   if (blk_addr == NULL_ADDR)
>   add_free_nid(sbi, start_nid, true);
> + update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> + }
> +}
> +
> +static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
> +{
> + struct f2fs_nm_info *nm_i = NM_I(sbi);
> + struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
> + struct f2fs_journal *journal = curseg->journal;
> + unsigned int i, idx;
> + unsigned int target = FREE_NID_PAGES * NAT_ENTRY_PER_BLOCK;
> +
> + down_read(_i->nat_tree_lock);
> +
> + for (i = 0; i < nm_i->nat_blocks; i++) {
> + if (!test_bit_le(i, nm_i->nat_block_bitmap))
> + continue;
> + for (idx = 0; idx < NAT_ENTRY_PER_BLOCK; idx++) {
> + nid_t nid;
> +
> + if (!test_bit_le(idx, nm_i->free_nid_bitmap[i]))
> + continue;
> +
> + nid = i * NAT_ENTRY_PER_BLOCK + idx;
> + add_free_nid(sbi, nid, true);
> +
> + if (nm_i->nid_cnt[FREE_NID_LIST] >= target)
> + goto out;
> + }
> + }
> +out:
> + 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

On 02/27, Chao Yu wrote:
> On 2017/2/26 3:02, Jaegeuk Kim wrote:
> > On 02/25, Chao Yu wrote:
> >> Hi Jaegeuk,
> >>
> >> I added below diff code into this patch in order to fix incorrectly nid 
> >> status
> >> updating to reduce large latency of generic/251 in fstest, could you help 
> >> to
> >> review code below?
> > 
> > Understand the problem, and how about this?
> > 
> > diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> > index 52db02396878..83b305689913 100644
> > --- a/fs/f2fs/node.c
> > +++ b/fs/f2fs/node.c
> > @@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct 
> > f2fs_sb_info *sbi,
> > radix_tree_delete(_i->free_nid_root, i->nid);
> >  }
> >  
> > -static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> > +static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> >  {
> > struct f2fs_nm_info *nm_i = NM_I(sbi);
> > struct free_nid *i;
> > @@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> >  
> > /* 0 nid should not be used */
> > if (unlikely(nid == 0))
> > -   return 0;
> > +   return false;
> >  
> > if (build) {
> > /* do not add allocated nids */
> > ne = __lookup_nat_cache(nm_i, nid);
> > if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
> > nat_get_blkaddr(ne) != NULL_ADDR))
> > -   return 0;
> > +   return false;
> > }
> >  
> > i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
> > @@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> >  
> > if (radix_tree_preload(GFP_NOFS)) {
> > kmem_cache_free(free_nid_slab, i);
> > -   return 0;
> > +   return false;
> 
> If there is no memory, actually current free nid is still available, we need 
> to
> return true (or other value -1?), then caller can set free_nid_bitmap 
> correctly.
> 
> > }
> >  
> > spin_lock(_i->nid_list_lock);
> > @@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> > radix_tree_preload_end();
> > if (err) {
> > kmem_cache_free(free_nid_slab, i);
> > -   return 0;
> > +   return false;
> 
> ditto.

Yup, applied.

Thanks,

> 
> Thanks,
> 
> > }
> > -   return 1;
> > +   return true;
> >  }
> >  
> >  static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
> > @@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
> > i = start_nid % NAT_ENTRY_PER_BLOCK;
> >  
> > for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> > +   bool freed = false;
> >  
> > if (unlikely(start_nid >= nm_i->max_nid))
> > break;
> > @@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
> > blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
> > f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
> > if (blk_addr == NULL_ADDR)
> > -   add_free_nid(sbi, start_nid, true);
> > -   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> > +   freed = add_free_nid(sbi, start_nid, true);
> > +   update_free_nid_bitmap(sbi, start_nid, freed);
> > }
> >  }
> >  
> > 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

On 02/27, Chao Yu wrote:
> On 2017/2/26 3:02, Jaegeuk Kim wrote:
> > On 02/25, Chao Yu wrote:
> >> Hi Jaegeuk,
> >>
> >> I added below diff code into this patch in order to fix incorrectly nid 
> >> status
> >> updating to reduce large latency of generic/251 in fstest, could you help 
> >> to
> >> review code below?
> > 
> > Understand the problem, and how about this?
> > 
> > diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> > index 52db02396878..83b305689913 100644
> > --- a/fs/f2fs/node.c
> > +++ b/fs/f2fs/node.c
> > @@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct 
> > f2fs_sb_info *sbi,
> > radix_tree_delete(_i->free_nid_root, i->nid);
> >  }
> >  
> > -static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> > +static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> >  {
> > struct f2fs_nm_info *nm_i = NM_I(sbi);
> > struct free_nid *i;
> > @@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> >  
> > /* 0 nid should not be used */
> > if (unlikely(nid == 0))
> > -   return 0;
> > +   return false;
> >  
> > if (build) {
> > /* do not add allocated nids */
> > ne = __lookup_nat_cache(nm_i, nid);
> > if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
> > nat_get_blkaddr(ne) != NULL_ADDR))
> > -   return 0;
> > +   return false;
> > }
> >  
> > i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
> > @@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> >  
> > if (radix_tree_preload(GFP_NOFS)) {
> > kmem_cache_free(free_nid_slab, i);
> > -   return 0;
> > +   return false;
> 
> If there is no memory, actually current free nid is still available, we need 
> to
> return true (or other value -1?), then caller can set free_nid_bitmap 
> correctly.
> 
> > }
> >  
> > spin_lock(_i->nid_list_lock);
> > @@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> > nid_t nid, bool build)
> > radix_tree_preload_end();
> > if (err) {
> > kmem_cache_free(free_nid_slab, i);
> > -   return 0;
> > +   return false;
> 
> ditto.

Yup, applied.

Thanks,

> 
> Thanks,
> 
> > }
> > -   return 1;
> > +   return true;
> >  }
> >  
> >  static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
> > @@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
> > i = start_nid % NAT_ENTRY_PER_BLOCK;
> >  
> > for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> > +   bool freed = false;
> >  
> > if (unlikely(start_nid >= nm_i->max_nid))
> > break;
> > @@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
> > blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
> > f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
> > if (blk_addr == NULL_ADDR)
> > -   add_free_nid(sbi, start_nid, true);
> > -   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> > +   freed = add_free_nid(sbi, start_nid, true);
> > +   update_free_nid_bitmap(sbi, start_nid, freed);
> > }
> >  }
> >  
> > 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

On 2017/2/26 3:02, Jaegeuk Kim wrote:
> On 02/25, Chao Yu wrote:
>> Hi Jaegeuk,
>>
>> I added below diff code into this patch in order to fix incorrectly nid 
>> status
>> updating to reduce large latency of generic/251 in fstest, could you help to
>> review code below?
> 
> Understand the problem, and how about this?
> 
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index 52db02396878..83b305689913 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct f2fs_sb_info 
> *sbi,
>   radix_tree_delete(_i->free_nid_root, i->nid);
>  }
>  
> -static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> +static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
>  {
>   struct f2fs_nm_info *nm_i = NM_I(sbi);
>   struct free_nid *i;
> @@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> nid_t nid, bool build)
>  
>   /* 0 nid should not be used */
>   if (unlikely(nid == 0))
> - return 0;
> + return false;
>  
>   if (build) {
>   /* do not add allocated nids */
>   ne = __lookup_nat_cache(nm_i, nid);
>   if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
>   nat_get_blkaddr(ne) != NULL_ADDR))
> - return 0;
> + return false;
>   }
>  
>   i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
> @@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
> nid, bool build)
>  
>   if (radix_tree_preload(GFP_NOFS)) {
>   kmem_cache_free(free_nid_slab, i);
> - return 0;
> + return false;

If there is no memory, actually current free nid is still available, we need to
return true (or other value -1?), then caller can set free_nid_bitmap correctly.

>   }
>  
>   spin_lock(_i->nid_list_lock);
> @@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
> nid, bool build)
>   radix_tree_preload_end();
>   if (err) {
>   kmem_cache_free(free_nid_slab, i);
> - return 0;
> + return false;

ditto.

Thanks,

>   }
> - return 1;
> + return true;
>  }
>  
>  static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
> @@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   i = start_nid % NAT_ENTRY_PER_BLOCK;
>  
>   for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> + bool freed = false;
>  
>   if (unlikely(start_nid >= nm_i->max_nid))
>   break;
> @@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
>   f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>   if (blk_addr == NULL_ADDR)
> - add_free_nid(sbi, start_nid, true);
> - update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> + freed = add_free_nid(sbi, start_nid, true);
> + update_free_nid_bitmap(sbi, start_nid, freed);
>   }
>  }
>  
> 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

On 2017/2/26 3:02, Jaegeuk Kim wrote:
> On 02/25, Chao Yu wrote:
>> Hi Jaegeuk,
>>
>> I added below diff code into this patch in order to fix incorrectly nid 
>> status
>> updating to reduce large latency of generic/251 in fstest, could you help to
>> review code below?
> 
> Understand the problem, and how about this?
> 
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index 52db02396878..83b305689913 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct f2fs_sb_info 
> *sbi,
>   radix_tree_delete(_i->free_nid_root, i->nid);
>  }
>  
> -static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
> +static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
>  {
>   struct f2fs_nm_info *nm_i = NM_I(sbi);
>   struct free_nid *i;
> @@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, 
> nid_t nid, bool build)
>  
>   /* 0 nid should not be used */
>   if (unlikely(nid == 0))
> - return 0;
> + return false;
>  
>   if (build) {
>   /* do not add allocated nids */
>   ne = __lookup_nat_cache(nm_i, nid);
>   if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
>   nat_get_blkaddr(ne) != NULL_ADDR))
> - return 0;
> + return false;
>   }
>  
>   i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
> @@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
> nid, bool build)
>  
>   if (radix_tree_preload(GFP_NOFS)) {
>   kmem_cache_free(free_nid_slab, i);
> - return 0;
> + return false;

If there is no memory, actually current free nid is still available, we need to
return true (or other value -1?), then caller can set free_nid_bitmap correctly.

>   }
>  
>   spin_lock(_i->nid_list_lock);
> @@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
> nid, bool build)
>   radix_tree_preload_end();
>   if (err) {
>   kmem_cache_free(free_nid_slab, i);
> - return 0;
> + return false;

ditto.

Thanks,

>   }
> - return 1;
> + return true;
>  }
>  
>  static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
> @@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   i = start_nid % NAT_ENTRY_PER_BLOCK;
>  
>   for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
> + bool freed = false;
>  
>   if (unlikely(start_nid >= nm_i->max_nid))
>   break;
> @@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>   blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
>   f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>   if (blk_addr == NULL_ADDR)
> - add_free_nid(sbi, start_nid, true);
> - update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
> + freed = add_free_nid(sbi, start_nid, true);
> + update_free_nid_bitmap(sbi, start_nid, freed);
>   }
>  }
>  
> 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

On 02/25, Chao Yu wrote:
> Hi Jaegeuk,
> 
> I added below diff code into this patch in order to fix incorrectly nid status
> updating to reduce large latency of generic/251 in fstest, could you help to
> review code below?

Understand the problem, and how about this?

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 52db02396878..83b305689913 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct f2fs_sb_info 
*sbi,
radix_tree_delete(_i->free_nid_root, i->nid);
 }
 
-static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
+static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
struct free_nid *i;
@@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
 
/* 0 nid should not be used */
if (unlikely(nid == 0))
-   return 0;
+   return false;
 
if (build) {
/* do not add allocated nids */
ne = __lookup_nat_cache(nm_i, nid);
if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
nat_get_blkaddr(ne) != NULL_ADDR))
-   return 0;
+   return false;
}
 
i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
@@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
 
if (radix_tree_preload(GFP_NOFS)) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return false;
}
 
spin_lock(_i->nid_list_lock);
@@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
radix_tree_preload_end();
if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return false;
}
-   return 1;
+   return true;
 }
 
 static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
@@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
i = start_nid % NAT_ENTRY_PER_BLOCK;
 
for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+   bool freed = false;
 
if (unlikely(start_nid >= nm_i->max_nid))
break;
@@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
if (blk_addr == NULL_ADDR)
-   add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
+   freed = add_free_nid(sbi, start_nid, true);
+   update_free_nid_bitmap(sbi, start_nid, freed);
}
 }
 
-- 
2.11.0

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Jaegeuk Kim]

On 02/25, Chao Yu wrote:
> Hi Jaegeuk,
> 
> I added below diff code into this patch in order to fix incorrectly nid status
> updating to reduce large latency of generic/251 in fstest, could you help to
> review code below?

Understand the problem, and how about this?

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 52db02396878..83b305689913 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1765,7 +1765,7 @@ static void __remove_nid_from_list(struct f2fs_sb_info 
*sbi,
radix_tree_delete(_i->free_nid_root, i->nid);
 }
 
-static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
+static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 {
struct f2fs_nm_info *nm_i = NM_I(sbi);
struct free_nid *i;
@@ -1774,14 +1774,14 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
 
/* 0 nid should not be used */
if (unlikely(nid == 0))
-   return 0;
+   return false;
 
if (build) {
/* do not add allocated nids */
ne = __lookup_nat_cache(nm_i, nid);
if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
nat_get_blkaddr(ne) != NULL_ADDR))
-   return 0;
+   return false;
}
 
i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
@@ -1790,7 +1790,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
 
if (radix_tree_preload(GFP_NOFS)) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return false;
}
 
spin_lock(_i->nid_list_lock);
@@ -1799,9 +1799,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t 
nid, bool build)
radix_tree_preload_end();
if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return false;
}
-   return 1;
+   return true;
 }
 
 static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
@@ -1851,6 +1851,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
i = start_nid % NAT_ENTRY_PER_BLOCK;
 
for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+   bool freed = false;
 
if (unlikely(start_nid >= nm_i->max_nid))
break;
@@ -1858,8 +1859,8 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
if (blk_addr == NULL_ADDR)
-   add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
+   freed = add_free_nid(sbi, start_nid, true);
+   update_free_nid_bitmap(sbi, start_nid, freed);
}
 }
 
-- 
2.11.0

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

Hi Jaegeuk,

I added below diff code into this patch in order to fix incorrectly nid status
updating to reduce large latency of generic/251 in fstest, could you help to
review code below?

Latency:beforeafter
generic/251 1483s ... 184s

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 52db02396878..d25dcadf901a 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1774,23 +1774,24 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t
nid, bool build)

/* 0 nid should not be used */
if (unlikely(nid == 0))
-   return 0;
+   return 1;

if (build) {
/* do not add allocated nids */
ne = __lookup_nat_cache(nm_i, nid);
if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
nat_get_blkaddr(ne) != NULL_ADDR))
-   return 0;
+   return 1;
}

i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
i->nid = nid;
i->state = NID_NEW;

-   if (radix_tree_preload(GFP_NOFS)) {
+   err = radix_tree_preload(GFP_NOFS);
+   if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return err;
}

spin_lock(_i->nid_list_lock);
@@ -1799,9 +1800,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t
nid, bool build)
radix_tree_preload_end();
if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return err;
}
-   return 1;
+   return 0;
 }

 static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
@@ -1844,7 +1845,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
struct f2fs_nat_block *nat_blk = page_address(nat_page);
block_t blk_addr;
unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
-   int i;
+   int i, ret;

set_bit_le(nat_ofs, nm_i->nat_block_bitmap);

@@ -1857,9 +1858,12 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,

blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
-   if (blk_addr == NULL_ADDR)
-   add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
+   if (blk_addr == NULL_ADDR) {
+   ret = add_free_nid(sbi, start_nid, true);
+   update_free_nid_bitmap(sbi, start_nid, ret <= 0);
+   } else {
+   update_free_nid_bitmap(sbi, start_nid, false);
+   }
}
 }


On 2017/2/23 10:53, Chao Yu wrote:
> In scenario of intensively node allocation, free nids will be ran out
> soon, then it needs to stop to load free nids by traversing NAT blocks,
> in worse case, if NAT blocks does not be cached in memory, it generates
> IOs which slows down our foreground operations.
> 
> In order to speed up node allocation, in this patch we introduce a new
> free_nid_bitmap array, so there is an bitmap table for each NAT block,
> Once the NAT block is loaded, related bitmap cache will be switched on,
> and bitmap will be set during traversing nat entries in NAT block, later
> we can query and update nid usage status in memory completely.
> 
> With such implementation, I expect performance of node allocation can be
> improved in the long-term after filesystem image is mounted.
> 
> Signed-off-by: Chao Yu 
> ---
>  fs/f2fs/debug.c |   2 +
>  fs/f2fs/f2fs.h  |   2 +
>  fs/f2fs/node.c  | 109 
> ++--
>  include/linux/f2fs_fs.h |   1 +
>  4 files changed, 111 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
> index 015ad2b73a92..a77df377e2e8 100644
> --- a/fs/f2fs/debug.c
> +++ b/fs/f2fs/debug.c
> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>   si->base_mem += sizeof(struct f2fs_nm_info);
>   si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>   si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
> + si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
> + si->base_mem += NM_I(sbi)->nat_blocks / 8;
>  
>  get_cache:
>   si->cache_mem = 0;
> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
> index 1c9f0cc8f027..6a48e649bfef 100644
> --- a/fs/f2fs/f2fs.h
> +++ b/fs/f2fs/f2fs.h
> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>   unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>   spinlock_t nid_list_lock;   /* protect nid lists ops */
>   struct mutex build_lock;/* lock for build free nids */
> + unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
> + unsigned char *nat_block_bitmap;
>  
>   /* for checkpoint */
>   char *nat_bitmap;   /* NAT bitmap pointer */
> diff --git a/fs/f2fs/node.c 

Re: [PATCH V2] f2fs: introduce free nid bitmap

[Chao Yu]

Hi Jaegeuk,

I added below diff code into this patch in order to fix incorrectly nid status
updating to reduce large latency of generic/251 in fstest, could you help to
review code below?

Latency:beforeafter
generic/251 1483s ... 184s

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 52db02396878..d25dcadf901a 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1774,23 +1774,24 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t
nid, bool build)

/* 0 nid should not be used */
if (unlikely(nid == 0))
-   return 0;
+   return 1;

if (build) {
/* do not add allocated nids */
ne = __lookup_nat_cache(nm_i, nid);
if (ne && (!get_nat_flag(ne, IS_CHECKPOINTED) ||
nat_get_blkaddr(ne) != NULL_ADDR))
-   return 0;
+   return 1;
}

i = f2fs_kmem_cache_alloc(free_nid_slab, GFP_NOFS);
i->nid = nid;
i->state = NID_NEW;

-   if (radix_tree_preload(GFP_NOFS)) {
+   err = radix_tree_preload(GFP_NOFS);
+   if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return err;
}

spin_lock(_i->nid_list_lock);
@@ -1799,9 +1800,9 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t
nid, bool build)
radix_tree_preload_end();
if (err) {
kmem_cache_free(free_nid_slab, i);
-   return 0;
+   return err;
}
-   return 1;
+   return 0;
 }

 static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
@@ -1844,7 +1845,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
struct f2fs_nat_block *nat_blk = page_address(nat_page);
block_t blk_addr;
unsigned int nat_ofs = NAT_BLOCK_OFFSET(start_nid);
-   int i;
+   int i, ret;

set_bit_le(nat_ofs, nm_i->nat_block_bitmap);

@@ -1857,9 +1858,12 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,

blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
-   if (blk_addr == NULL_ADDR)
-   add_free_nid(sbi, start_nid, true);
-   update_free_nid_bitmap(sbi, start_nid, blk_addr == NULL_ADDR);
+   if (blk_addr == NULL_ADDR) {
+   ret = add_free_nid(sbi, start_nid, true);
+   update_free_nid_bitmap(sbi, start_nid, ret <= 0);
+   } else {
+   update_free_nid_bitmap(sbi, start_nid, false);
+   }
}
 }


On 2017/2/23 10:53, Chao Yu wrote:
> In scenario of intensively node allocation, free nids will be ran out
> soon, then it needs to stop to load free nids by traversing NAT blocks,
> in worse case, if NAT blocks does not be cached in memory, it generates
> IOs which slows down our foreground operations.
> 
> In order to speed up node allocation, in this patch we introduce a new
> free_nid_bitmap array, so there is an bitmap table for each NAT block,
> Once the NAT block is loaded, related bitmap cache will be switched on,
> and bitmap will be set during traversing nat entries in NAT block, later
> we can query and update nid usage status in memory completely.
> 
> With such implementation, I expect performance of node allocation can be
> improved in the long-term after filesystem image is mounted.
> 
> Signed-off-by: Chao Yu 
> ---
>  fs/f2fs/debug.c |   2 +
>  fs/f2fs/f2fs.h  |   2 +
>  fs/f2fs/node.c  | 109 
> ++--
>  include/linux/f2fs_fs.h |   1 +
>  4 files changed, 111 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
> index 015ad2b73a92..a77df377e2e8 100644
> --- a/fs/f2fs/debug.c
> +++ b/fs/f2fs/debug.c
> @@ -194,6 +194,8 @@ static void update_mem_info(struct f2fs_sb_info *sbi)
>   si->base_mem += sizeof(struct f2fs_nm_info);
>   si->base_mem += __bitmap_size(sbi, NAT_BITMAP);
>   si->base_mem += (NM_I(sbi)->nat_bits_blocks << F2FS_BLKSIZE_BITS);
> + si->base_mem += NM_I(sbi)->nat_blocks * NAT_ENTRY_BITMAP_SIZE;
> + si->base_mem += NM_I(sbi)->nat_blocks / 8;
>  
>  get_cache:
>   si->cache_mem = 0;
> diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
> index 1c9f0cc8f027..6a48e649bfef 100644
> --- a/fs/f2fs/f2fs.h
> +++ b/fs/f2fs/f2fs.h
> @@ -556,6 +556,8 @@ struct f2fs_nm_info {
>   unsigned int nid_cnt[MAX_NID_LIST]; /* the number of free node id */
>   spinlock_t nid_list_lock;   /* protect nid lists ops */
>   struct mutex build_lock;/* lock for build free nids */
> + unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE];
> + unsigned char *nat_block_bitmap;
>  
>   /* for checkpoint */
>   char *nat_bitmap;   /* NAT bitmap pointer */
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index