No free space left for GC

No free space left for GC

[Thomas Gleixner]

Hi David ! 

You wanted to know, why free_size got that low. 

I just copied stuff to an empty partition, until it got full. 
But instead of returning with "not enough space" it keeps garbage 
collection until really no more space is left. 
One of the problems is, that we have at lot of blocks on the dirty list,
with less than 2*sizeof(struct jffs2_raw_inode) left. At scan time we
put these blocks on the clean_list. We must do this in normal operation
too. It's total crap to gc blocks with 4 byte dirty space ! 
The total sum of dirty space is 32K, when we start gc. The most dirty 
block has 1.2k dirty space. Many blocks have less than 512 bytes dirty,
which is the pagesize on my device. This is a result of padding, when we
flush wbuf. The dirty space on blocks with more than 512 byte dirty
space is 12048 Byte, which is less than 1 block. 

The real weird thing is, that we write to the device (from gc) until the
last block is used and we run into an endless loop, where no more space
is left for garbage collection. This happens, because we increase dirty
size during gc instead of decreasing it. Once we are there we cannot
mount the filesystem again, without running in that endless gc loop.

I changed nodemgmt.c so that blocks with less than 2*sizeof(struct
jffs2_raw_inode) dirty space are moved to clean_list. But the gc effect
was still the same. 

Now I noticed that we don't move blocks to the dirty list anymore,
neither on mount (pass1) nor during gc or write. The reason is that
mark_node_obsolete checks if the dirty_size == ref_totlen. Due to the
fact, that we have blocks with some dirty space in the clean list, these
blocks stay there until they are very dirty, which may never happen. I
changed this by checking used space against sector_size -
2*sizeof(struct jffs2_raw_inode). Result is better but not good.
I tried the same procedure on a larger partition (56MB, previous one was
8MB). There I was running in trouble again. I had enough dirty space in
the clean_list, that the check in jffs2_reserve_space c->dirty_size <
c->sector_size never lead to -ENOSPC. I added a check, which is done,
when dirty_size is less than blocksneeded * sector_size. It checks if
the dirty_size in the dirty_lists is > c->sector_size. If not it returns
-ENOSPC too. Same as above.

In both cases, we end up with 3 empty blocks and we can't even remove a
file from the filesystem.

The strange thing is, that the dirty_size is not always correct. When I
filled the filesystem complete, df tells me:
/dev/mtdblock1	8192	8164	28	100%	/mnt/data
The last dirty information from the log was dirty_space = 0x3e0c
After umount and mount I have suddenly dirty_space = 0xcfe8, which is
the real dirty size. The good thing on this is, that the endless gc on a
100% full filesystem stops. The bad thing is that we have only 3 blocks
left and I can't remove a file anymore. Have to add some more checks on
monday.

If we are at the point of a 100% full filesystem and the dirty space is
splitted into small pieces, we add for each gc'd block one or two blocks
to the dirty list and the block, we have written to ends up sometimes on
the dirty list too. Maybe we have to add a check, where we calc the
average dirty space per block on dirty_list. If this is less than a
defined threshold, we return ENOSPC and stop garbage collection instead
of screwing up the filesystem at least. It should always be possible to
delete a file.

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de

Massive file corruption

[Joakim Tjernlund]

Hi again

For the second time there has been massive file corrution on one of our
boards.

In /bin there was 3 files that had been corrupted, the first 4K was all zeroes.
In /usr/bin, a ls gave me lots of Input/Output error and a load of CRC
errors in dmesg.

After reboot, ls in /usr/bin did not report Input/Output errors but there
was more corrupted files in there, with the first 4K zeroed.

Before this happened there was a lot of file I/O. ftp files to board, unpack them with rpm
delete old files etc.

No errors was reported during boot by JFFS2. Using the stable branch from ~3-4 months ago.

Any ideas?

            Jocke 

Re: No free space left for GC

[Thomas Gleixner]

Some more information:

I tried to trigger GC instead of flushing the writebuffer. In principle
it works. But when do we stop GC again ? I decided to do it, when the
replacement node is written complete. Fine, if we hit a small file. If
it's rather large, we dirty a lot of space and trigger GC again, if we
are near the GC_TRESHHOLD. So we spend a lot of time in GC and increase
the erasecycles unneccecary. This depends really on the application and
on the filesizes on the filesystem. Padding can make a block dirty too,
but we get rid of the padding during GC, and can produce another
padding, when we run into wbuf_timeout. 

The 0xc4 request is sizeof(jffs2_raw_inode) + JFFS2_MIN_DATA_LEN). This
happens rather often, that it doesn't fit anymore in the block. So we
put this block on the dirty list and raised an endless gc cycle. These
blocks should be put into the clean list.

Then we have a lot of blocks with 4 bytes unused space. These blocks
should definitly always end on the clean list. 

We could put the blocks, which have more than 4 bytes dirty space on the
dirty list at mount time. When a block gets full and has less than 256
byte dirty space, we put it on the clean list to inhibit endless gc
loops on a nearly 100% full filesystem. 

On a 8MB partition I have an average dirty size of 20 bytes in 490
blocks. Not too bad. And more acceptable than loosing 48K, if one 16K
block dies. I have already 2 bad blocks there. So I accept 10k penalty
for having 96K usable flashspace. For NOR this should be no problem as
the sectorsizes are usually 64K - 128K.

On a 64MB partition I ended up with an average dirty size of 14 byte in
3200 blocks, which is a total of 58k. A lot of space, but better than
screwing up if we get near 100%. The 0xc4 request, which does not fit
into the remaining free space hits us too often to ignore it. Better to
have 58k less disk space than no chance to repair my full filesystem
other than erasing it.

The new decision function for gc and reserve_space takes only those
blocks into account, which are on the dirty and very dirty list. The
dirty space in the clean_list is ignored. This is neccecary to avoid
endless GC loops. 

Any suggestions ?

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de

Re: No free space left for GC

[Thomas Gleixner]

[-- Attachment #1: Type: text/plain, Size: 302 bytes --]

Forgot to attach a diff :)

Last try brought average dirty_space 11 bytes in 492 Blocks in
clean_list. I think we can live with that

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de

[-- Attachment #2: cvs.diff --]
[-- Type: text/plain, Size: 10031 bytes --]

? cvs.diff
Index: fs/jffs2/background.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/background.c,v
retrieving revision 1.30
diff -u -r1.30 background.c
--- fs/jffs2/background.c	5 Aug 2002 14:46:47 -0000	1.30
+++ fs/jffs2/background.c	19 Aug 2002 22:30:39 -0000
@@ -155,18 +155,11 @@
 static int thread_should_wake(struct jffs2_sb_info *c)
 {
 	uint32_t gcnodeofs = 0;
-	int ret;
+	int ret = 0;
 
-	/* Don't count any progress we've already made through the gcblock
-	   as dirty space, for the purposes of this calculation */
-	if (c->gcblock && c->gcblock->gc_node)
-		gcnodeofs = c->gcblock->gc_node->flash_offset & ~3 & (c->sector_size-1);
-
-	if (c->nr_free_blocks + c->nr_erasing_blocks < JFFS2_RESERVED_BLOCKS_GCTRIGGER &&
-	    (c->dirty_size - gcnodeofs) > c->sector_size)
+	if (c->nr_free_blocks + c->nr_erasing_blocks < JFFS2_RESERVED_BLOCKS_GCTRIGGER && 
+		!jffs2_gc_checkspace (c, JFFS2_RESERVED_BLOCKS_BASE))
 		ret = 1;
-	else 
-		ret = 0;
 
 	D1(printk(KERN_DEBUG "thread_should_wake(): nr_free_blocks %d, nr_erasing_blocks %d, dirty_size 0x%x (mod 0x%x): %s\n", 
 		  c->nr_free_blocks, c->nr_erasing_blocks, c->dirty_size,
Index: fs/jffs2/build.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/build.c,v
retrieving revision 1.36
diff -u -r1.36 build.c
--- fs/jffs2/build.c	7 Aug 2002 18:37:32 -0000	1.36
+++ fs/jffs2/build.c	19 Aug 2002 22:30:40 -0000
@@ -43,6 +43,7 @@
 		return ret;
 
 	D1(printk(KERN_DEBUG "Scanned flash completely\n"));
+	D1(jffs2_dump_block_lists(c));
 	/* Now build the data map for each inode, marking obsoleted nodes
 	   as such, and also increase nlink of any children. */
 	for_each_inode(i, c, ic) {
@@ -54,7 +55,8 @@
 		}
 	}
 	D1(printk(KERN_DEBUG "Pass 1 complete\n"));
-
+	D1(jffs2_dump_block_lists(c));
+	
 	/* Next, scan for inodes with nlink == 0 and remove them. If
 	   they were directories, then decrement the nlink of their
 	   children too, and repeat the scan. As that's going to be
@@ -75,6 +77,7 @@
 		   and furthermore that it had children and their nlink has now
 		   gone to zero too. So we have to restart the scan. */
 		} 
+		D1(jffs2_dump_block_lists(c));
 	} while(ret == -EAGAIN);
 	
 	D1(printk(KERN_DEBUG "Pass 2 complete\n"));
@@ -99,6 +102,7 @@
 		kfree(scan);
 	}
 	D1(printk(KERN_DEBUG "Pass 3 complete\n"));
+	D1(jffs2_dump_block_lists(c));
 
 	/* Rotate the lists by some number to ensure wear levelling */
 	jffs2_rotate_lists(c);
Index: fs/jffs2/gc.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/gc.c,v
retrieving revision 1.78
diff -u -r1.78 gc.c
--- fs/jffs2/gc.c	7 Aug 2002 11:01:14 -0000	1.78
+++ fs/jffs2/gc.c	19 Aug 2002 22:30:42 -0000
@@ -33,6 +33,40 @@
 				       struct jffs2_inode_info *f, struct jffs2_full_dnode *fn,
 				       uint32_t start, uint32_t end);
 
+/* Check, if we have enough dirty space for GC */
+int jffs2_gc_checkspace (struct jffs2_sb_info *c, int blocksneeded)
+{
+	
+	if (c->dirty_size < blocksneeded * c->sector_size) {
+		
+		uint32_t dirty = 0;
+		struct list_head *this;
+		
+		if (!list_empty(&c->very_dirty_list)) {
+			list_for_each(this, &c->very_dirty_list) {
+				struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
+				dirty += jeb->dirty_size;
+			}
+		}
+		if (!list_empty(&c->dirty_list)) {
+			list_for_each(this, &c->dirty_list) {
+				struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
+				dirty += jeb->dirty_size;	
+			}
+		}
+		/* Add dirty size of current gc-block */
+		if (c->gcblock)
+			dirty += c->gcblock->dirty_size;
+					
+		if (dirty < c->sector_size) {
+			D1(printk(KERN_DEBUG "dirty size in dirty_lists 0x%08x < sector size 0x%08x\n", dirty, c->sector_size));
+			return 1;
+		}
+	}
+	/* yep, we can GC */
+	return 0;
+}
+
 /* Called with erase_completion_lock held */
 static struct jffs2_eraseblock *jffs2_find_gc_block(struct jffs2_sb_info *c)
 {
Index: fs/jffs2/nodelist.h
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodelist.h,v
retrieving revision 1.75
diff -u -r1.75 nodelist.h
--- fs/jffs2/nodelist.h	17 Aug 2002 22:28:04 -0000	1.75
+++ fs/jffs2/nodelist.h	19 Aug 2002 22:30:43 -0000
@@ -220,8 +220,9 @@
 /* How much dirty space before it goes on the very_dirty_list */
 #define VERYDIRTY(c, size) ((size) >= ((c)->sector_size / 2))
 
-/* check if unused space is more than sector - 2 * sizeof(struct jffs2_raw_inode) */
-#define ISDIRTY(c, size) ((size) < c->sector_size - (2 * sizeof(struct jffs2_raw_inode)))
+/* check if unused space is more than 256 Byte */
+#define ISDIRTY(c, size) ((size) < c->sector_size - 255) 
+#define MNTISDIRTY(c, size) ((size) < c->sector_size - 4) 
 
 #define PAD(x) (((x)+3)&~3)
 
@@ -299,6 +300,7 @@
 
 /* gc.c */
 int jffs2_garbage_collect_pass(struct jffs2_sb_info *c);
+int jffs2_gc_checkspace (struct jffs2_sb_info *c, int blocksneeded);
 
 /* read.c */
 int jffs2_read_dnode(struct jffs2_sb_info *c, struct jffs2_full_dnode *fd, unsigned char *buf, int ofs, int len);
Index: fs/jffs2/nodemgmt.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/nodemgmt.c,v
retrieving revision 1.71
diff -u -r1.71 nodemgmt.c
--- fs/jffs2/nodemgmt.c	17 Aug 2002 22:32:11 -0000	1.71
+++ fs/jffs2/nodemgmt.c	19 Aug 2002 22:30:44 -0000
@@ -62,32 +62,13 @@
 			int ret;
 
 			up(&c->alloc_sem);
-			if (c->dirty_size < c->sector_size) {
-				D1(printk(KERN_DEBUG "Short on space, but total dirty size 0x%08x < sector size 0x%08x, so -ENOSPC\n", c->dirty_size, c->sector_size));
+			
+			if (jffs2_gc_checkspace(c, blocksneeded)) {
+				D1(printk (KERN_DEBUG "Too little dirty_space for GC, returning -ENOSPC\n"));
 				spin_unlock_bh(&c->erase_completion_lock);
 				return -ENOSPC;
 			}
-			if (c->dirty_size < blocksneeded * c->sector_size) {
-				uint32_t dirty = 0;			
-				struct list_head *this;
-				if (!list_empty(&c->very_dirty_list)) {
-					list_for_each(this, &c->very_dirty_list) {
-						struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
-						dirty += jeb->dirty_size;	
-					}
-				}
-				if (!list_empty(&c->dirty_list)) {
-					list_for_each(this, &c->dirty_list) {
-						struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
-						dirty += jeb->dirty_size;	
-					}
-				}
-				if (dirty < c->sector_size) {
-					D1(printk(KERN_DEBUG "Short on space, but dirty size in dirty_lists 0x%08x < sector size 0x%08x, so -ENOSPC\n", dirty, c->sector_size));
-					spin_unlock_bh(&c->erase_completion_lock);
-					return -ENOSPC;
-				}
-			}
+			
 			D1(printk(KERN_DEBUG "Triggering GC pass. nr_free_blocks %d, nr_erasing_blocks %d, free_size 0x%08x, dirty_size 0x%08x, used_size 0x%08x, erasing_size 0x%08x, bad_size 0x%08x (total 0x%08x of 0x%08x)\n",
 				  c->nr_free_blocks, c->nr_erasing_blocks, c->free_size, c->dirty_size, c->used_size, c->erasing_size, c->bad_size,
 				  c->free_size + c->dirty_size + c->used_size + c->erasing_size + c->bad_size, c->flash_size));
@@ -498,6 +479,8 @@
 #if CONFIG_JFFS2_FS_DEBUG > 0
 void jffs2_dump_block_lists(struct jffs2_sb_info *c)
 {
+
+
 	printk(KERN_DEBUG "jffs2_dump_block_lists:\n");
 	printk(KERN_DEBUG "flash_size: %08x\n", c->flash_size);
 	printk(KERN_DEBUG "used_size: %08x\n", c->used_size);
@@ -522,31 +505,46 @@
 		printk(KERN_DEBUG "clean_list: empty\n");
 	} else {
 		struct list_head *this;
+		int	numblocks = 0;
+		uint32_t dirty = 0;
 
 		list_for_each(this, &c->clean_list) {
 			struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
+			numblocks ++;
+			dirty += jeb->dirty_size;
 			printk(KERN_DEBUG "clean_list: %08x (used %08x, dirty %08x, free %08x)\n", jeb->offset, jeb->used_size, jeb->dirty_size, jeb->free_size);
 		}
+		printk (KERN_DEBUG "Contains %d blocks with total dirty size %u, average dirty size: %u\n", numblocks, dirty, dirty / numblocks);
 	}
 	if (list_empty(&c->very_dirty_list)) {
 		printk(KERN_DEBUG "very_dirty_list: empty\n");
 	} else {
 		struct list_head *this;
+		int	numblocks = 0;
+		uint32_t dirty = 0;
 
 		list_for_each(this, &c->very_dirty_list) {
 			struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
+			numblocks ++;
+			dirty += jeb->dirty_size;
 			printk(KERN_DEBUG "very_dirty_list: %08x (used %08x, dirty %08x, free %08x)\n", jeb->offset, jeb->used_size, jeb->dirty_size, jeb->free_size);
 		}
+		printk (KERN_DEBUG "Contains %d blocks with total dirty size %u, average dirty size: %u\n", numblocks, dirty, dirty / numblocks);
 	}
 	if (list_empty(&c->dirty_list)) {
 		printk(KERN_DEBUG "dirty_list: empty\n");
 	} else {
 		struct list_head *this;
+		int	numblocks = 0;
+		uint32_t dirty = 0;
 
 		list_for_each(this, &c->dirty_list) {
 			struct jffs2_eraseblock *jeb = list_entry(this, struct jffs2_eraseblock, list);
+			numblocks ++;
+			dirty += jeb->dirty_size;
 			printk(KERN_DEBUG "dirty_list: %08x (used %08x, dirty %08x, free %08x)\n", jeb->offset, jeb->used_size, jeb->dirty_size, jeb->free_size);
 		}
+		printk (KERN_DEBUG "Contains %d blocks with total dirty size %u, average dirty size: %u\n", numblocks, dirty, dirty / numblocks);
 	}
 	if (list_empty(&c->erasable_list)) {
 		printk(KERN_DEBUG "erasable_list: empty\n");
Index: fs/jffs2/scan.c
===================================================================
RCS file: /home/cvs/mtd/fs/jffs2/scan.c,v
retrieving revision 1.80
diff -u -r1.80 scan.c
--- fs/jffs2/scan.c	17 Aug 2002 22:29:28 -0000	1.80
+++ fs/jffs2/scan.c	19 Aug 2002 22:30:47 -0000
@@ -420,7 +420,7 @@
 	if (jeb->used_size == PAD(sizeof(struct jffs2_unknown_node)) && 
 	    !jeb->first_node->next_in_ino && !jeb->dirty_size)
 		return BLK_STATE_CLEANMARKER;
-	else if (!ISDIRTY(c, jeb->used_size)) 
+	else if (!MNTISDIRTY(c, jeb->used_size)) 
 		return BLK_STATE_CLEAN;
 	else if (jeb->used_size)
 		return BLK_STATE_PARTDIRTY;

Re: No free space left for GC

[Thomas Gleixner]

On Tue, 2002-08-20 at 04:46, 小明 wrote:
> in our own old nand flash system
> we always keep 1 nand-flash-block for garbage collection in block device
> driver
> (8k/8MB,16k/64MB)
> it never endless gc, but when diskfull,the speed is really slow
> finally we reserved more space(512k) for gc to  make gc faster
> those reversed space is not showed in fs layer
> we report (real size-reserved space) to fs layer
> and we use minix as fs layer
> (we do  bad block management, wear leveling, error correction,
> all in block device driver not in fs layer)
> recently, we need compression , so we try jffs2:)
> i think the design of jffs2 is also better than our old one:)
1. Please keep answers to mailinglist posting on the list. Thanks.

2. The endless gc, which used up all blocks, is fixed now. I will do
some more tests and put a final version into CVS today.

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de

Re: No free space left for GC

[David Woodhouse]

tglx@linutronix.de said:
>  The new decision function for gc and reserve_space takes only those
> blocks into account, which are on the dirty and very dirty list. The
> dirty space in the clean_list is ignored. This is neccecary to avoid
> endless GC loops. 

> Any suggestions ?

<IRC conversation repeated, for the benefit of the peanut gallery>

Nice work, thanks. If this fixes the problem, as I believe it does, please
don't calculate the dirty size in thread_should_wake() -- use c->dirty_size 
and just don't count the wasted space in the end of blocks on the 
clean_list in that; add something like 'wasted_size' to keep track of that
instead.

And read README.Locking again. It's rare that I actually write sensible 
documentation -- make the most of it :)

--
dwmw2

Re: No free space left for GC

[Thomas Gleixner]

On Tue, 2002-08-20 at 09:59, Thomas Gleixner wrote:
> 2. The endless gc, which used up all blocks, is fixed now. I will do
> some more tests and put a final version into CVS today.
Is there, please try again. 

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de

can i use the cvs code directly in kernel 2.2.19 ?

[小明]

dear all,
another question:
can i use the cvs code directly in kernel 2.2.19 ?
(currently it work fine with kernel 2.4.17)

Re: can i use the cvs code directly in kernel 2.2.19 ?

[Thomas Gleixner]

On Wed, 2002-08-21 at 08:44, 小明 wrote:
> dear all,
> another question:
> can i use the cvs code directly in kernel 2.2.19 ?
> (currently it work fine with kernel 2.4.17)
Look for the inter_module patch in the patches/ directory of CVS.
It's for 2.2.17, but should apply to 2.2.19 too. There are some more
tweaks neccecary. There are 2 mailthreads (june, august 02) about that.
Citation dwmw2:
> I know of nobody else working on a 2.2 backport. Worst case, you 
> should be able to ditch the page-based write code and call
> jffs2_write_file_range() from a jffs2_file_write() which you provide
> instead of generic_file_write().

BTW, did you test latest code in CVS ? Any problems left ?

-- 
Thomas 
____________________________________________________
linutronix - competence in embedded & realtime linux
http://www.linutronix.de
mail: tglx@linutronix.de