Skip to contentSkip to conversation

f2fs: get the right gc victim section when section has several segments

PATCH Superseded Jack Qiu 2 participants 2 messages Jun 16, 2020 – Jun 17, 2020 F2FS file system

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Jack Qiu

author
#0 lore raw

PATCH 1/1 f2fs: get the right gc victim section when section has several segments

Assume each section has 4 segment:

     .___________________________.
     |_Segment0_|_..._|_Segment3_|
     .                          .
     .                  .
     .__________.
     |_section0_|

Segment 0~2 has 0 valid block, segment 3 has 512 valid blocks. It will fail if we want to gc section0 in this scenes, because all 4 segments in section0 is not dirty.
So we should use dirty section bitmap instead of dirty segment bitmap to get right victim section.

---
 fs/f2fs/gc.c      | 41 +++++++++++++++++++++++----------------
 fs/f2fs/segment.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++-
 fs/f2fs/segment.h |  6 +++++-
 3 files changed, 78 insertions(+), 18 deletions(-)
fs/f2fs/gc.c +25 -16
index 5b95d5a146eb..0fc5cc41a310 100644
@@ -21,6 +21,11 @@
 #include "gc.h"
 #include <trace/events/f2fs.h>
 
+#define DIRTY_UNIT_MAP(p)	(((p)->ofs_unit > 1) ? \
+				((p)->dirty_secmap) : ((p)->dirty_segmap))
+static unsigned int count_bits(const unsigned long *addr,
+				unsigned int offset, unsigned int len);
+
 static int gc_thread_func(void *data)
 {
 	struct f2fs_sb_info *sbi = data;
@@ -192,9 +197,15 @@ static void select_policy(struct f2fs_sb_info *sbi, int gc_type,
 		p->ofs_unit = 1;
 	} else {
 		p->gc_mode = select_gc_type(sbi, gc_type);
-		p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
-		p->max_search = dirty_i->nr_dirty[DIRTY];
 		p->ofs_unit = sbi->segs_per_sec;
+		if (p->ofs_unit > 1) {
+			p->dirty_segmap = dirty_i->dirty_secmap;
+			p->max_search = count_bits(p->dirty_secmap,
+						0, MAIN_SECS(sbi));
+		} else {
+			p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
+			p->max_search = dirty_i->nr_dirty[DIRTY];
+		}
 	}
 
 	/*
@@ -365,10 +376,14 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 	}
 
 	while (1) {
-		unsigned long cost;
-		unsigned int segno;
-
-		segno = find_next_bit(p.dirty_segmap, last_segment, p.offset);
+		unsigned long cost, *dirty_bitmap;
+		unsigned int unit_no, segno;
+
+		dirty_bitmap = DIRTY_UNIT_MAP(&p);
+		unit_no = find_next_bit(dirty_bitmap,
+				last_segment / p.ofs_unit,
+				p.offset / p.ofs_unit);
+		segno = unit_no * p.ofs_unit;
 		if (segno >= last_segment) {
 			if (sm->last_victim[p.gc_mode]) {
 				last_segment =
@@ -381,14 +396,7 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 		}
 
 		p.offset = segno + p.ofs_unit;
-		if (p.ofs_unit > 1) {
-			p.offset -= segno % p.ofs_unit;
-			nsearched += count_bits(p.dirty_segmap,
-						p.offset - p.ofs_unit,
-						p.ofs_unit);
-		} else {
-			nsearched++;
-		}
+		nsearched++;
 
 #ifdef CONFIG_F2FS_CHECK_FS
 		/*
@@ -421,9 +429,10 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 next:
 		if (nsearched >= p.max_search) {
 			if (!sm->last_victim[p.gc_mode] && segno <= last_victim)
-				sm->last_victim[p.gc_mode] = last_victim + 1;
+				sm->last_victim[p.gc_mode] =
+					last_victim + p.ofs_unit;
 			else
-				sm->last_victim[p.gc_mode] = segno + 1;
+				sm->last_victim[p.gc_mode] = segno + p.ofs_unit;
 			sm->last_victim[p.gc_mode] %=
 				(MAIN_SECS(sbi) * sbi->segs_per_sec);
 			break;
fs/f2fs/segment.c +48 -1

97 lines not on this page · raw message

fs/f2fs/segment.h +5 -1
index cba16cca5189..5037c4f54be2 100644
@@ -166,7 +166,10 @@ enum {
 struct victim_sel_policy {
 	int alloc_mode;			/* LFS or SSR */
 	int gc_mode;			/* GC_CB or GC_GREEDY */
-	unsigned long *dirty_segmap;	/* dirty segment bitmap */
+	union {
+		unsigned long *dirty_segmap;	/* dirty segment bitmap */
+		unsigned long *dirty_secmap;	/* dirty section bitmap */
+	};
 	unsigned int max_search;	/* maximum # of segments to search */
 	unsigned int offset;		/* last scanned bitmap offset */
 	unsigned int ofs_unit;		/* bitmap search unit */
@@ -266,6 +269,7 @@ enum dirty_type {
 struct dirty_seglist_info {
 	const struct victim_selection *v_ops;	/* victim selction operation */
 	unsigned long *dirty_segmap[NR_DIRTY_TYPE];
+	unsigned long *dirty_secmap;
 	struct mutex seglist_lock;		/* lock for segment bitmaps */
 	int nr_dirty[NR_DIRTY_TYPE];		/* # of dirty segments */
 	unsigned long *victim_secmap;		/* background GC victims */

--
2.17.1

_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

#1 lore raw
Quoted 8 lines · Jack Qiu

Assume each section has 4 segment:

     .___________________________.
     |_Segment0_|_..._|_Segment3_|
     .                          .
     .                  .
     .__________.
     |_section0_|
Quoted 5 lines

Segment 0~2 has 0 valid block, segment 3 has 512 valid blocks. It will fail if we want to gc section0 in this scenes, because all 4 segments in section0 is not dirty.
So we should use dirty section bitmap instead of dirty segment bitmap to get right victim section.

Nice catch.

Quoted 103 lines
---
 fs/f2fs/gc.c      | 41 +++++++++++++++++++++++----------------
 fs/f2fs/segment.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++-
 fs/f2fs/segment.h |  6 +++++-
 3 files changed, 78 insertions(+), 18 deletions(-)
fs/f2fs/gc.c +25 -16
index 5b95d5a146eb..0fc5cc41a310 100644
@@ -21,6 +21,11 @@
 #include "gc.h"
 #include <trace/events/f2fs.h>
 
+#define DIRTY_UNIT_MAP(p)	(((p)->ofs_unit > 1) ? \
+				((p)->dirty_secmap) : ((p)->dirty_segmap))
+static unsigned int count_bits(const unsigned long *addr,
+				unsigned int offset, unsigned int len);
+
 static int gc_thread_func(void *data)
 {
 	struct f2fs_sb_info *sbi = data;
@@ -192,9 +197,15 @@ static void select_policy(struct f2fs_sb_info *sbi, int gc_type,
 		p->ofs_unit = 1;
 	} else {
 		p->gc_mode = select_gc_type(sbi, gc_type);
-		p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
-		p->max_search = dirty_i->nr_dirty[DIRTY];
 		p->ofs_unit = sbi->segs_per_sec;
+		if (p->ofs_unit > 1) {
+			p->dirty_segmap = dirty_i->dirty_secmap;
+			p->max_search = count_bits(p->dirty_secmap,
+						0, MAIN_SECS(sbi));
+		} else {
+			p->dirty_segmap = dirty_i->dirty_segmap[DIRTY];
+			p->max_search = dirty_i->nr_dirty[DIRTY];
+		}
 	}
 
 	/*
@@ -365,10 +376,14 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 	}
 
 	while (1) {
-		unsigned long cost;
-		unsigned int segno;
-
-		segno = find_next_bit(p.dirty_segmap, last_segment, p.offset);
+		unsigned long cost, *dirty_bitmap;
+		unsigned int unit_no, segno;
+
+		dirty_bitmap = DIRTY_UNIT_MAP(&p);
+		unit_no = find_next_bit(dirty_bitmap,
+				last_segment / p.ofs_unit,
+				p.offset / p.ofs_unit);
+		segno = unit_no * p.ofs_unit;
 		if (segno >= last_segment) {
 			if (sm->last_victim[p.gc_mode]) {
 				last_segment =
@@ -381,14 +396,7 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 		}
 
 		p.offset = segno + p.ofs_unit;
-		if (p.ofs_unit > 1) {
-			p.offset -= segno % p.ofs_unit;
-			nsearched += count_bits(p.dirty_segmap,
-						p.offset - p.ofs_unit,
-						p.ofs_unit);
-		} else {
-			nsearched++;
-		}
+		nsearched++;
 
 #ifdef CONFIG_F2FS_CHECK_FS
 		/*
@@ -421,9 +429,10 @@ static int get_victim_by_default(struct f2fs_sb_info *sbi,
 next:
 		if (nsearched >= p.max_search) {
 			if (!sm->last_victim[p.gc_mode] && segno <= last_victim)
-				sm->last_victim[p.gc_mode] = last_victim + 1;
+				sm->last_victim[p.gc_mode] =
+					last_victim + p.ofs_unit;
 			else
-				sm->last_victim[p.gc_mode] = segno + 1;
+				sm->last_victim[p.gc_mode] = segno + p.ofs_unit;
 			sm->last_victim[p.gc_mode] %=
 				(MAIN_SECS(sbi) * sbi->segs_per_sec);
 			break;
fs/f2fs/segment.c +1 -0
index 196f31503511..60bd70a68447 100644
@@ -778,6 +778,7 @@ static void __locate_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno,
 		enum dirty_type dirty_type)
 {
 	struct dirty_seglist_info *dirty_i = DIRTY_I(sbi);
+	unsigned short valid_blocks;
 
 	/* need not be added */
 	if (IS_CURSEG(sbi, segno))

fs/f2fs/segment.c static void __locate_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno, · line 800

Quoted 4 lines
fs/f2fs/segment.c +1 -0
@@ -796,6 +797,16 @@ static void __locate_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno,
 		}
 		if (!test_and_set_bit(segno, dirty_i->dirty_segmap[t]))
 			dirty_i->nr_dirty[t]++;
+
if (__is_large_section()) {
	unsigned short valid_blocks = get_valid_blocks(sbi, segno, true);
	unsigned int secno = GET_SEC_FROM_SEG(sbi, segno);

	f2fs_bug_on(sbi, unlikely(...));

	if (IS_CURSEC(sbi, secno))
		set_bit(secno, dirty_i->dirty_secmap);
}

fs/f2fs/segment.c static void __locate_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno, · line 803

Quoted 3 lines
fs/f2fs/segment.c +3 -0
+		valid_blocks = get_valid_blocks(sbi, segno, true);
+		if (valid_blocks == 0 || valid_blocks == sbi->blocks_per_seg *
+				sbi->segs_per_sec) {

should be replaced w/ BLKS_PER_SEC(sbi)

Quoted 20 lines
fs/f2fs/segment.c +7 -0
+			f2fs_bug_on(sbi, 1);
+		} else {
+			if (!IS_CURSEC(sbi, GET_SEC_FROM_SEG(sbi, segno)))
+				set_bit(GET_SEC_FROM_SEG(sbi, segno),
+						dirty_i->dirty_secmap);
+		}
 	}
 }
 
@@ -803,6 +814,7 @@ static void __remove_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno,
 		enum dirty_type dirty_type)
 {
 	struct dirty_seglist_info *dirty_i = DIRTY_I(sbi);
+	unsigned short valid_blocks;
 
 	if (test_and_clear_bit(segno, dirty_i->dirty_segmap[dirty_type]))
 		dirty_i->nr_dirty[dirty_type]--;
@@ -814,13 +826,23 @@ static void __remove_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno,
 		if (test_and_clear_bit(segno, dirty_i->dirty_segmap[t]))
 			dirty_i->nr_dirty[t]--;

fs/f2fs/segment.c static void __remove_dirty_segment(struct f2fs_sb_info *sbi, unsigned int segno, · line 836

Quoted 10 lines
fs/f2fs/segment.c +2 -1
 
-		if (get_valid_blocks(sbi, segno, true) == 0) {
+		valid_blocks = get_valid_blocks(sbi, segno, true);
+		if (valid_blocks == 0) {
 			clear_bit(GET_SEC_FROM_SEG(sbi, segno),
 						dirty_i->victim_secmap);
 #ifdef CONFIG_F2FS_CHECK_FS
 			clear_bit(segno, SIT_I(sbi)->invalid_segmap);
 #endif
 		}

Ditto, could you clean up below codes as above?

if (__is_large_section()) {
	if ( == 0 || == BLKS_PER_SEC) {
		clear_bit();
		return;
	}

	if (!IS_CURSEC)
		set_bit();
}
Quoted 21 lines
fs/f2fs/segment.c +14 -0
+		if (valid_blocks == 0 || valid_blocks == sbi->blocks_per_seg *
+				sbi->segs_per_sec) {
+			clear_bit(GET_SEC_FROM_SEG(sbi, segno),
+					dirty_i->dirty_secmap);
+		} else {
+			if (!IS_CURSEC(sbi, GET_SEC_FROM_SEG(sbi, segno)))
+				set_bit(GET_SEC_FROM_SEG(sbi, segno),
+						dirty_i->dirty_secmap);
+		}
 	}
 }
 
@@ -4313,6 +4335,22 @@ static void init_dirty_segmap(struct f2fs_sb_info *sbi)
 		__locate_dirty_segment(sbi, segno, DIRTY);
 		mutex_unlock(&dirty_i->seglist_lock);
 	}
+
+	segno = 0;
+	mutex_lock(&dirty_i->seglist_lock);
+	while (1) {
+		if (segno >= MAIN_SECS(sbi))

fs/f2fs/segment.c static void init_dirty_segmap(struct f2fs_sb_info *sbi) · line 4352

Quoted 10 lines
fs/f2fs/segment.c +10 -0
+			break;
+		valid_blocks = get_valid_blocks(sbi, segno, true);
+		if (!(valid_blocks == 0 || valid_blocks == sbi->blocks_per_seg *
+						sbi->segs_per_sec)) {
+			if (!IS_CURSEC(sbi, GET_SEC_FROM_SEG(sbi, segno)))
+				set_bit(GET_SEC_FROM_SEG(sbi, segno),
+						dirty_i->dirty_secmap);
+		}
+		segno += sbi->segs_per_sec;
+	}

blks_per_sec = BLKS_PER_SEC(sbi);

for (segno = 0; segno < MAIN_SECS(sbi); segno += sbi->segs_per_sec) {
	valid_blocks = get_valid_blocks(sbi, segno, true);
	secno = GET_SEC_FROM_SEG(sbi, segno);

	if (!valid_blocks || valid_blocks == blks_per_sec))
		continue;
	if (IS_CURSEC(sbi, secno)
		continue;
	set_bit(secno, dirty_i->dirty_secmap);
}

fs/f2fs/segment.c static int build_dirty_segmap(struct f2fs_sb_info *sbi) · line 4389

Quoted 8 lines
fs/f2fs/segment.c +1 -0
+	mutex_unlock(&dirty_i->seglist_lock);
 }
 
 static int init_victim_secmap(struct f2fs_sb_info *sbi)
@@ -4349,6 +4387,11 @@ static int build_dirty_segmap(struct f2fs_sb_info *sbi)
 			return -ENOMEM;
 	}
 

We only need to allocate/free such memory if one section contains multi segments.

Quoted 24 lines
fs/f2fs/segment.c +9 -0
+	bitmap_size = f2fs_bitmap_size(MAIN_SECS(sbi));
+	dirty_i->dirty_secmap = f2fs_kvzalloc(sbi, bitmap_size, GFP_KERNEL);
+	if (!dirty_i->dirty_secmap)
+		return -ENOMEM;
+
 	init_dirty_segmap(sbi);
 	return init_victim_secmap(sbi);
 }
@@ -4775,6 +4818,10 @@ static void destroy_dirty_segmap(struct f2fs_sb_info *sbi)
 	for (i = 0; i < NR_DIRTY_TYPE; i++)
 		discard_dirty_segmap(sbi, i);
 
+	mutex_lock(&dirty_i->seglist_lock);
+	kvfree(dirty_i->dirty_secmap);
+	mutex_unlock(&dirty_i->seglist_lock);
+
 	destroy_victim_secmap(sbi);
 	SM_I(sbi)->dirty_info = NULL;
 	kvfree(dirty_i);
fs/f2fs/segment.h +0 -0
index cba16cca5189..5037c4f54be2 100644

fs/f2fs/segment.h enum { · line 169

Quoted 4 lines
fs/f2fs/segment.h +0 -1
@@ -166,7 +166,10 @@ enum {
 struct victim_sel_policy {
 	int alloc_mode;			/* LFS or SSR */
 	int gc_mode;			/* GC_CB or GC_GREEDY */
-	unsigned long *dirty_segmap;	/* dirty segment bitmap */

IMO, we don't need to use union, one common bitmap pointer is enough?

unsigned long *dirty_bitmap; /* dirty segment/section bitmap */

fs/f2fs/segment.h enum { · line 173

Quoted 5 lines
fs/f2fs/segment.h +4 -0
+	union {
+		unsigned long *dirty_segmap;	/* dirty segment bitmap */
+		unsigned long *dirty_secmap;	/* dirty section bitmap */
+	};
 	unsigned int max_search;	/* maximum # of segments to search */

/* maximum # of segments/sections to search */

Quoted 15 lines
fs/f2fs/segment.h +1 -1
 	unsigned int offset;		/* last scanned bitmap offset */
 	unsigned int ofs_unit;		/* bitmap search unit */
@@ -266,6 +269,7 @@ enum dirty_type {
 struct dirty_seglist_info {
 	const struct victim_selection *v_ops;	/* victim selction operation */
 	unsigned long *dirty_segmap[NR_DIRTY_TYPE];
+	unsigned long *dirty_secmap;
 	struct mutex seglist_lock;		/* lock for segment bitmaps */
 	int nr_dirty[NR_DIRTY_TYPE];		/* # of dirty segments */
 	unsigned long *victim_secmap;		/* background GC victims */
--

2.17.1

Quoted 6 lines

_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
.

_______________________________________________
Linux-f2fs-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel