From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755154AbdKCHc6 (ORCPT ); Fri, 3 Nov 2017 03:32:58 -0400 Received: from mailout4.samsung.com ([203.254.224.34]:39100 "EHLO mailout4.samsung.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754754AbdKCHcw (ORCPT ); Fri, 3 Nov 2017 03:32:52 -0400 DKIM-Filter: OpenDKIM Filter v2.11.0 mailout4.samsung.com 20171103073250epoutp04e769f2438e93e7b09a7b133183fd0926~zgwfvfET12251222512epoutp04n X-AuditID: b6c32a36-33dff70000001039-6f-59fc1ba175ce From: Fan Li To: "'Chao Yu'" , "'Jaegeuk Kim'" Cc: linux-kernel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net Subject: [f2fs-dev] [PATCH RESEND] f2fs: modify the procedure of scan free nid Date: Fri, 03 Nov 2017 15:31:12 +0800 Message-id: <001101d35475$f33d8b40$d9b8a1c0$@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: AdNUdZD/b/c4XLefR4WKJ3CmHlLCJw== X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrCIsWRmVeSWpSXmKPExsWy7bCmge5C6T+RBjeOG1ucnnqWyeLJ+lnM FpcWuVtc3jWHzYHFY9OqTjaP3Qs+M3l83iQXwBzFZZOSmpNZllqkb5fAldG86BR7wX2disPr 3RoYO1S6GDk5JARMJG40bmUGsYUEdjBKXGgyhrC/M0pMXSkMU/P4fycTRHw3o8TVU/ZdjFxA 9itGieVvnjOCJNgE1CW2zOwGKxIRcJY48mEFSxcjBwezgIfErmOlIGFhgQCJwzNfgu1iEVCV OHZhERuIzStgKdH5q4cRwhaU+DH5HguIzSxgIDFjymEmCFteYvOat8wQ9yhI7Dj7mhEiLi4x 6cFDdoi1ehJLrj1mAblNQmAGm8TRKztYIRpcJA7fO8UOYQtLvDq+hR3kNgkBaYlLR20hwusY JT6fsYDo3c4oMe/jRyaIhDXQ4l/sEMv4JN597WGF6OWV6GgTgijxkFjz8SojhO0o0XpuNysk rGIlntzvZZrAKDcLyWuzkLw2C8lrs5C8s4CRZRWjWGpBcW56arFhgZFecWJucWleul5yfu4m RnBa0DLbwbjonM8hRgEORiUe3g0TfkcKsSaWFVfmHmKU4GBWEuF9HAMU4k1JrKxKLcqPLyrN SS0+xCjNwaIkziu6/lqEkEB6YklqdmpqQWoRTJaJg1OqgdFMMZdFf1vNbY07+1hEfp7g+dBV x/H8c5T8Cd971yQXSiSdWFFsdNZs+fdyhjPHpzbxipfp7NAwmX+0eV+oY9kNjec/BdVuHn1z TYKjd/vmJa+MGzOq2w0iVVdwzl7VaHozT3nt2/t7sjPOuNoKpzkHv15m0M8emZe/xOLd/a08 dznVKgwLXyqxFGckGmoxFxUnAgBcqweDBwMAAA== X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrELMWRmVeSWpSXmKPExsVy+t9jAd2F0n8iDT7ul7Q4PfUsk8WT9bOY LS4tcre4vGsOmwOLx6ZVnWweuxd8ZvL4vEkugDmKyyYlNSezLLVI3y6BK6N50Sn2gvs6FYfX uzUwdqh0MXJySAiYSDz+38nUxcjFISSwk1Hi/451jBDOK0aJX/OeM4JUsQmoS2yZ2c0EYosI OEsc+bCCpYuRg4NZwENi17FSkLCwgJ9Ew+yzzCA2i4CqxLELi9hAbF4BS4nOXz2MELagxI/J 96Ba9STuX9QCCTMLyEtsXvOWGeIeBYkdZ18zQsTFJSY9eMgOsVVPYsm1xywTGPlnIZk0C2HS LCSTZiHpXsDIsopRMrWgODc9t9iowDAvtVyvODG3uDQvXS85P3cTIzBktx3W6tvBeH9J/CFG AQ5GJR5ejsm/I4VYE8uKK3MPMUpwMCuJ8D6OAQrxpiRWVqUW5ccXleakFh9ilOZgURLnvZ13 LFJIID2xJDU7NbUgtQgmy8TBKdXAyJyqtVD9ZF158deivZYeP8z+XXLolbvg+iWpOHQVk7bb 9pzWbf+ZHq6tynA97N1ltmap2sJ9bTz9vfv/3ZXjvNHsqnnwndWLa1vKlsvfEoj4n3LIVjms 0Hpa4r3/WfJamh+yZ3gZrTj6X++codmbG2/n3c6v8T/8SyVwjZHq9t05c1UMb59tV2Ipzkg0 1GIuKk4EAFnDGUZVAgAA X-CMS-MailID: 20171103073249epcas1p4a6e7f7875d21ec575efd593c3b5bd970 X-Msg-Generator: CA CMS-TYPE: 101P X-CMS-RootMailID: 20171103073249epcas1p4a6e7f7875d21ec575efd593c3b5bd970 X-RootMTR: 20171103073249epcas1p4a6e7f7875d21ec575efd593c3b5bd970 References: Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. 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) -- 2.7.4