From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755935AbdKCKbD (ORCPT ); Fri, 3 Nov 2017 06:31:03 -0400 Received: from mailout4.samsung.com ([203.254.224.34]:28955 "EHLO mailout4.samsung.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751899AbdKCKbA (ORCPT ); Fri, 3 Nov 2017 06:31:00 -0400 DKIM-Filter: OpenDKIM Filter v2.11.0 mailout4.samsung.com 20171103103059epoutp04926dd9695b73be0c490cd973becc060a~zjMCfemYh1968019680epoutp04a X-AuditID: b6c32a47-cefff7000000102c-9c-59fc45627209 From: Fan Li To: "'Chao Yu'" , "'Chao Yu'" , "'Jaegeuk Kim'" Cc: linux-kernel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net In-reply-to: Subject: RE: [f2fs-dev] [PATCH RESEND] f2fs: modify the procedure of scan free nid Date: Fri, 03 Nov 2017 18:29:53 +0800 Message-id: <001a01d3548e$d3b06b80$7b114280$@samsung.com> MIME-version: 1.0 Content-type: text/plain; charset="windows-1252" Content-transfer-encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Content-language: en-us Thread-index: AQHNCRDEDl/3jHXXdAzqyFOLd9pIvwNJkTllAb34+LSi5rsz4A== X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFupnleLIzCtJLcpLzFFi42LZdljTXDfJ9U+kQf91dovTU88yWTxZP4vZ 4tIid4vLu+awWUx9vJbVgdWj5chbVo9NqzrZPHYv+Mzk8XmTXABLFJdNSmpOZllqkb5dAlfG +2W7mAqu+VccmPeUrYHxoV0XIyeHhICJxIu2tYwgtpDADkaJ/2dtuxi5gOzvjBJ7N/5khCnq mTCbDSKxm1HiyofJrBDOK0aJXxfXMoFUsQmoS2yZ2Q1miwikSrzd1cfcxcjBwSzgIbHrWClI mFPATuL92kXMILawQIjEllld7CA2i4CqxJbF91lBbF4BS4m2B1ugbEGJH5PvsYDYzAIGEjOm HGaCsOUlNq95ywxxnILEjrOvGSHi4hKTHjxkhzjBSaJnyWtmkDslBI6wSbxq+ADV4CJxcvN9 JghbWOLV8S3sELa0xLNVG6E+Xsco8fmMBUTzdkaJeR8/QjVYA23+xQ6xjU+i4/BfdpAnJQR4 JTrahCBKPCTWfLwKNcdRovXcbmhgHWSUaNj0gG0Co/wsJM/NQvLcLCTPzULy0AJGllWMYqkF xbnpqcVGBcZ6xYm5xaV56XrJ+bmbGMHJRMt9B+O2cz6HGAU4GJV4eDdM+B0pxJpYVlyZe4hR goNZSYQ31OpPpBBvSmJlVWpRfnxRaU5q8SFGaQ4WJXHeum3XIoQE0hNLUrNTUwtSi2CyTByc Ug2MUz7/0mJpKzsh7sT8RtTk6cO2acxLrrU3hvgWfO/s7HL4fyE2dEHe/YqZNk+2bFaeIGTS wROXOvHz7banNrOucq9yN8gX01H2uJXZbO1/avnfzJn3zZjv7fkWW9rooJstmyNgUPuuzUP4 wsQDCz91fGdUM3i7dt3qV2Fp27dI3s5KDlm38o62EktxRqKhFnNRcSIA98LlICIDAAA= X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrGLMWRmVeSWpSXmKPExsVy+t9jAd1E1z+RBpf36lmcnnqWyeLJ+lnM FpcWuVtc3jWHzWLq47WsDqweLUfesnpsWtXJ5rF7wWcmj8+b5AJYorhsUlJzMstSi/TtErgy 3i/bxVRwzb/iwLynbA2MD+26GDk5JARMJHomzGbrYuTiEBLYySjx7XU3K4TzilHi7sfZ7CBV bALqEltmdjOB2CICqRK7Z30D6uDgYBbwkNh1rBSi/jCjxPvH+1lBajgF7CTer13EDGILC4RI PFt0kg3EZhFQldiy+D5YDa+ApUTbgy1QtqDEj8n3WCBm6kncv6gFEmYWkJfYvOYtM8ShChI7 zr5mhIiLS0x68JAd4hwniZ4lr5knMArOQjJpFsKkWUgmzULSvYCRZRWjZGpBcW56brFRgVFe arlecWJucWleul5yfu4mRmDobzus1b+D8fGS+EOMAhyMSjy8HJN/RwqxJpYVV+YeYpTgYFYS 4Q21+hMpxJuSWFmVWpQfX1Sak1p8iFGag0VJnJc//1ikkEB6YklqdmpqQWoRTJaJg1OqgXH7 /2vrLhf2rBWceLLxbvWzecvtV3Bves31U9tAvFa15q7cpdiDzsH5i4IKxNcoxwXvkUreb1Jl 8PfLslWZ3UYzlX2Ug9/o/L8lcPpHz5yKi1y7F7Uxp0uxHhQo3dQqIKvYvSRo+/1TkR2nPjV+ s3NV0ebZIfahuI+nx/QfS+9VxZcdCr6/NiuxFGckGmoxFxUnAgBglf/PeQIAAA== X-CMS-MailID: 20171103103057epcas2p310df982803e333d505821bbbd84d0331 X-Msg-Generator: CA CMS-TYPE: 102P X-CMS-RootMailID: 20171103073249epcas1p4a6e7f7875d21ec575efd593c3b5bd970 X-RootMTR: 20171103073249epcas1p4a6e7f7875d21ec575efd593c3b5bd970 References: <001101d35475$f33d8b40$d9b8a1c0$@samsung.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org > -----Original Message----- > From: Chao Yu [mailto:yuchao0@huawei.com] > Sent: Friday, November 03, 2017 4:54 PM > To: Fan Li; 'Chao Yu'; 'Jaegeuk Kim' > Cc: linux-kernel@vger.kernel.org; linux-f2fs-devel@lists.sourceforge.net > Subject: Re: [f2fs-dev] [PATCH RESEND] f2fs: modify the procedure of scan free nid > > On 2017/11/3 15:31, Fan Li wrote: > > In current version, we preserve 8 pages of nat blocks as free nids, we > > build bitmaps for it and use them to allocate nids until its number > > drops below NAT_ENTRY_PER_BLOCK. > > > > After that, we have a problem, scan_free_nid_bits will scan the same > > 8 pages trying to find more free nids, but in most cases the free nids > > in these bitmaps are already in free list, scan them won't get us any > > new nids. > > Further more, after scan_free_nid_bits, the scan is over if > > nid_cnt[FREE_NID] != 0. > > It causes that we scan the same pages over and over again, and no new > > free nids are found until nid_cnt[FREE_NID]==0. While the scanned > > pages increase, the problem grows worse. > > > > This patch mark the range where new free nids could exist and keep > > scan for free nids until nid_cnt[FREE_NID] >= NAT_ENTRY_PER_BLOCK. > > The new vairable first_scan_block marks the start of the range, it's > > initialized with NEW_ADDR, which means all free nids before > > next_scan_nid are already in free list; and use next_scan_nid as the > > end of the range since all free nids which are scanned in > > scan_free_nid_bits must be smaller next_scan_nid. > > Think over again, IMO, we can add an variable for stating total count of free nids in bitamp, if there is no free nid, just skipping scanning all > existed bitmap. > > And if there is only few free nid scattered in bitmap, the cost will be limited because we will skip scanning nm_i::free_nid_bitmap if > nm_i::free_nid_count is zero. Once we find one free nid, let's skip out. > > Since there shouldn't be very heavy overhead for CPU during traveling nm_i::nat_block_bitmap, I expect below change could be more > simple for maintaining and being with the same effect. > > How do you think? > I think if you need this to work, check total_bitmap_free_nid may not be sufficient enough. The problem this patch presents is that even all the free nids are already in the free list, we still scan all the pages. The scan proceeds once free nid count is below NAT_ENTRY_PER_BLOCK. So in most cases, there are still free nids in the bitmap during the scan, and current codes will check every one of them to see if they are actually in free list. If only check total_bitmap_free_nid == 0 won't take this overhead away. I considered a lot of ways to fix this problem before I submit this patch, One of my idea is quite similar to yours, but I use "if (total_bitmap_free_nid == nm_i->nid_cnt[FREE_NID])" to decide whether skip or not. If you insist, I can submit this simpler one instead, but some follow upgrade would be unavailable, for example, use smaller granularity for tracking last-scanned-position that we talked about. I know sometimes I can be obsessed with the performance, I usually choose the faster way over simpler ones. If you think it's too much, please tell me, I'm sure we can find some middle ground. Thank you > diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h index cb3f10bc8723..238d95e89dec 100644 > --- a/fs/f2fs/f2fs.h > +++ b/fs/f2fs/f2fs.h > @@ -729,6 +729,7 @@ struct f2fs_nm_info { > unsigned char (*free_nid_bitmap)[NAT_ENTRY_BITMAP_SIZE]; > unsigned char *nat_block_bitmap; > unsigned short *free_nid_count; /* free nid count of NAT block */ > + unsigned int total_bitmap_free_nid; /* total free nid count in bitmap */ > > /* for checkpoint */ > char *nat_bitmap; /* NAT bitmap pointer */ > diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c index fef5c68886b1..e4861908a396 100644 > --- a/fs/f2fs/node.c > +++ b/fs/f2fs/node.c > @@ -1911,10 +1911,13 @@ static 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]); > > - if (set) > + if (set) { > nm_i->free_nid_count[nat_ofs]++; > - else if (!build) > + nm_i->total_bitmap_free_nid++; > + } else if (!build) { > nm_i->free_nid_count[nat_ofs]--; > + nm_i->total_bitmap_free_nid--; > + } > } > > static void scan_nat_page(struct f2fs_sb_info *sbi, @@ -1958,6 +1961,9 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi) > > down_read(&nm_i->nat_tree_lock); > > + if (!nm_i->total_bitmap_free_nid) > + goto out; > + > for (i = 0; i < nm_i->nat_blocks; i++) { > if (!test_bit_le(i, nm_i->nat_block_bitmap)) > continue; > @@ -1972,7 +1978,7 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi) > nid = i * NAT_ENTRY_PER_BLOCK + idx; > add_free_nid(sbi, nid, true); > > - if (nm_i->nid_cnt[FREE_NID] >= MAX_FREE_NIDS) > + if (nm_i->nid_cnt[FREE_NID]) > goto out; > } > } > > Thanks, > > > > > Signed-off-by: Fan li > > --- > > fs/f2fs/f2fs.h | 1 + > > fs/f2fs/node.c | 42 +++++++++++++++++++++++++++++++++++------- > > 2 files changed, 36 insertions(+), 7 deletions(-) > > > > diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h index e0ef31c..ae1cf91 > > 100644 > > --- a/fs/f2fs/f2fs.h > > +++ b/fs/f2fs/f2fs.h > > @@ -705,6 +705,7 @@ struct f2fs_nm_info { > > nid_t max_nid; /* maximum possible node ids */ > > nid_t available_nids; /* # of available node ids */ > > nid_t next_scan_nid; /* the next nid to be scanned */ > > + block_t first_scan_block; /* the first NAT block to be scanned */ > > unsigned int ram_thresh; /* control the memory footprint */ > > unsigned int ra_nid_pages; /* # of nid pages to be readaheaded */ > > unsigned int dirty_nats_ratio; /* control dirty nats ratio threshold */ > > diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c index 3d0d1be..f921e0c > > 100644 > > --- a/fs/f2fs/node.c > > +++ b/fs/f2fs/node.c > > @@ -1812,7 +1812,7 @@ 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, *e; > > struct nat_entry *ne; > > - int err = -EINVAL; > > + int need_free = 1; > > bool ret = false; > > > > /* 0 nid should not be used */ > > @@ -1863,13 +1863,25 @@ static bool add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build) > > } > > } > > ret = true; > > - err = __insert_free_nid(sbi, i, FREE_NID); > > + need_free = __insert_free_nid(sbi, i, FREE_NID); > > err_out: > > spin_unlock(&nm_i->nid_list_lock); > > radix_tree_preload_end(); > > err: > > - if (err) > > + if (need_free) > > kmem_cache_free(free_nid_slab, i); > > + /* > > + * For nid that should be free but not in the free > > + * structure, update the scan range in hope of adding > > + * it in the next scan. > > + */ > > + if (!ret || need_free < 0) { > > + block_t tmp_block = NAT_BLOCK_OFFSET(nid); > > + > > + if (tmp_block < nm_i->first_scan_block) > > + nm_i->first_scan_block = tmp_block; > > + } > > + > > return ret; > > } > > > > @@ -1950,10 +1962,17 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi) > > struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA); > > struct f2fs_journal *journal = curseg->journal; > > unsigned int i, idx; > > + unsigned int max_blocks = NAT_BLOCK_OFFSET(nm_i->next_scan_nid); > > > > - down_read(&nm_i->nat_tree_lock); > > + /* every free nid in blocks scanned previously is in the free list */ > > + if (nm_i->first_scan_block == NEW_ADDR) > > + return; > > > > - for (i = 0; i < nm_i->nat_blocks; i++) { > > + if (max_blocks == 0) > > + max_blocks = nm_i->nat_blocks; > > + > > + down_read(&nm_i->nat_tree_lock); > > + for (i = nm_i->first_scan_block; i < max_blocks; i++) { > > if (!test_bit_le(i, nm_i->nat_block_bitmap)) > > continue; > > if (!nm_i->free_nid_count[i]) > > @@ -1967,10 +1986,13 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi) > > nid = i * NAT_ENTRY_PER_BLOCK + idx; > > add_free_nid(sbi, nid, true); > > > > - if (nm_i->nid_cnt[FREE_NID] >= MAX_FREE_NIDS) > > + if (nm_i->nid_cnt[FREE_NID] >= MAX_FREE_NIDS) { > > + nm_i->first_scan_block = i; > > goto out; > > + } > > } > > } > > + nm_i->first_scan_block = NEW_ADDR; > > out: > > down_read(&curseg->journal_rwsem); > > for (i = 0; i < nats_in_cursum(journal); i++) { @@ -2010,7 +2032,7 > > @@ static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount) > > /* try to find free nids in free_nid_bitmap */ > > scan_free_nid_bits(sbi); > > > > - if (nm_i->nid_cnt[FREE_NID]) > > + if (nm_i->nid_cnt[FREE_NID] >= NAT_ENTRY_PER_BLOCK) > > return; > > } > > > > @@ -2163,6 +2185,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink) > > struct f2fs_nm_info *nm_i = NM_I(sbi); > > struct free_nid *i, *next; > > int nr = nr_shrink; > > + nid_t min_nid = nm_i->max_nid; > > > > if (nm_i->nid_cnt[FREE_NID] <= MAX_FREE_NIDS) > > return 0; > > @@ -2176,11 +2199,15 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink) > > nm_i->nid_cnt[FREE_NID] <= MAX_FREE_NIDS) > > break; > > > > + if (i->nid < min_nid) > > + min_nid = i->nid; > > __remove_free_nid(sbi, i, FREE_NID); > > kmem_cache_free(free_nid_slab, i); > > nr_shrink--; > > } > > spin_unlock(&nm_i->nid_list_lock); > > + if (min_nid != nm_i->max_nid) > > + nm_i->first_scan_block = NAT_BLOCK_OFFSET(min_nid); > > mutex_unlock(&nm_i->build_lock); > > > > return nr - nr_shrink; > > @@ -2674,6 +2701,7 @@ static int init_node_manager(struct f2fs_sb_info *sbi) > > init_rwsem(&nm_i->nat_tree_lock); > > > > nm_i->next_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid); > > + nm_i->first_scan_block = NEW_ADDR; > > nm_i->bitmap_size = __bitmap_size(sbi, NAT_BITMAP); > > version_bitmap = __bitmap_ptr(sbi, NAT_BITMAP); > > if (!version_bitmap) > > >