JFFS2 node versioning problem?

JFFS2 node versioning problem?

[Dmitry Bazhenov]

Hello everybody!

I was just thinking about hypothetical situation with JFFS2 wich possibly 
could be met in the reality. What happens when the highest node version of a 
certain inode exceeds the maximum value?

I think this can be a point where the inode can be broken. If there are two 
data nodes which have overlapped regions and more recent node has a lesser 
value then the other node has, then, when the partition is dismounted and 
mounted again the more recent inode is treated as an older one and could be 
obsoleted. Even if it is not obsoleted, its data become superseeded by data 
from the least recent node as the last one has a higher version number.

--
Regards,
Dmitry

Re: JFFS2 node versioning problem?

[Artem B. Bityutskiy]

Dmitry Bazhenov wrote:
> Hello everybody!
> 
> I was just thinking about hypothetical situation with JFFS2 wich possibly 
> could be met in the reality. What happens when the highest node version of a 
> certain inode exceeds the maximum value?
> 
> I think this can be a point where the inode can be broken. If there are two 
> data nodes which have overlapped regions and more recent node has a lesser 
> value then the other node has, then, when the partition is dismounted and 
> mounted again the more recent inode is treated as an older one and could be 
> obsoleted. Even if it is not obsoleted, its data become superseeded by data 
> from the least recent node as the last one has a higher version number.
> 
Can it happen with a real-life flash device? If it can, we have to 
switch to 64-bit versions.

-- 
Best Regards,
Artem B. Bityutskiy,
St.-Petersburg, Russia.

Re: JFFS2 node versioning problem?

[Dmitry Bazhenov]

On Wednesday 03 May 2006 16:02, Artem B. Bityutskiy wrote:
> Can it happen with a real-life flash device? If it can, we have to 
> switch to 64-bit versions.

I think it can happen. I can imagine at least one scenario where such 
situation can occur. Of course, in normal circumstances it is hardly possible 
but in the case of a powerfail it can be.
	1. Assume, upon a call to jffs2_commit_write() function the
	f->highest_version has the maximum value.
	2. jffs2_commit_write() increments f->highest_version which becomes 0.
	3. jffs2_commit_write() invokes jffs2_write_dnode() with version=0.

	5. Powerfail before obsoleting least recent overlapping nodes.

	6. After reset, the scan process finds two(if were only one node for the
	commited page before) valid nodes wich refer to the same region. It places
	the least recent node which has the maximum version number at the end of
	the node list.
	7. When jffs2_read_inode() function is invoked, the node with the biggest
	version number is added last, thus, obsoleting all overlapping nodes.
	The most recent inode is obsoleted as well. --> Bug.

As a workaround I suggest to obsolete previous nodes before writing the new 
one. In case of powerfail there will be holes in data which can be easily 
recognized during inode reading.

--
Regards,
Dmitry

Re: JFFS2 node versioning problem?

[Dmitry Bazhenov]

On Wednesday 03 May 2006 16:02, Artem B. Bityutskiy wrote:
> Can it happen with a real-life flash device? If it can, we have to 
> switch to 64-bit versions.

But it can't happen on unmount since in normal circumstance all previous nodes 
are obsoleted after the new node has been written. Sorry, my mistake. So, no 
need for 64-bit versions.

--
Regards,
Dmitry

Re: JFFS2 node versioning problem?

[Artem B. Bityutskiy]

Dmitry Bazhenov wrote:
> But it can't happen on unmount since in normal circumstance all previous nodes 
> are obsoleted after the new node has been written. Sorry, my mistake. So, no 
> need for 64-bit versions.

No, in case of version oveflow there will be nasty things, but the idea 
is that we expect that it never overflows because flash should die first.

-- 
Best Regards,
Artem B. Bityutskiy,
St.-Petersburg, Russia.

Re: JFFS2 node versioning problem?

[Artem B. Bityutskiy]

Dmitry Bazhenov wrote:
> I think it can happen. I can imagine at least one scenario where such 
> situation can occur. Of course, in normal circumstances it is hardly possible 
> but in the case of a powerfail it can be.
> 	1. Assume, upon a call to jffs2_commit_write() function the
> 	f->highest_version has the maximum value.
> 	2. jffs2_commit_write() increments f->highest_version which becomes 0.
> 	3. jffs2_commit_write() invokes jffs2_write_dnode() with version=0.

I meant, whether it can happen with a real-life flash device taking into 
account it's limited lifetime. Bear in mind, each eraseblock has limited 
resource. I guess for huge flashes this may be the case, but JFFS2 is 
not usable on them anyway. I'm too lazy to look at digits.

-- 
Best Regards,
Artem B. Bityutskiy,
St.-Petersburg, Russia.

Re: JFFS2 node versioning problem?

[Dmitry Bazhenov]

On Wednesday 03 May 2006 18:40, Artem B. Bityutskiy wrote:
> I meant, whether it can happen with a real-life flash device taking into 
> account it's limited lifetime. Bear in mind, each eraseblock has limited 
> resource. I guess for huge flashes this may be the case, but JFFS2 is 
> not usable on them anyway. I'm too lazy to look at digits.

I have made some estimates and agree, that lifetime of an ordinal flash device 
is significantly less than the point where the maximum version value is 
achieved. For example:
	Partition size: 1MB
	Erase block size: 128KB
	Block count: 8
	Average node len: 150b
	Maximum erase count: 100 000
	max_ver_per_blok = (Erase block size) / (Average node len) = 128KB / 150
		= 874
	max_ver_per_erase_cycle = (Block count) * max_ver_per_block = 8 * 874
		= 6990
	max_ver = (Maximum erase count) * max_ver_per_erase_cycle = 699 * 10^6 
		= 0x29AAAAAA

But, how about the guys who make image snapshots? I understand, that it is 
better to copy all information to some place, format the partition and copy 
the informatuib back. But, if someone would want to make an image snapshot of 
a JFFS2 partition in order to restore it somewhen later. In this case version 
numbers retain. And they can be big. However, maybe it is not worth talking 
about it.

--
Regards,
Dmitry

Re: JFFS2 node versioning problem?

[Josh Boyer]

On 5/3/06, Dmitry Bazhenov <atrey@emcraft.com> wrote:
> On Wednesday 03 May 2006 16:02, Artem B. Bityutskiy wrote:
> > Can it happen with a real-life flash device? If it can, we have to
> > switch to 64-bit versions.
>
> I think it can happen. I can imagine at least one scenario where such
> situation can occur. Of course, in normal circumstances it is hardly possible
> but in the case of a powerfail it can be.
>         1. Assume, upon a call to jffs2_commit_write() function the
>         f->highest_version has the maximum value.
>         2. jffs2_commit_write() increments f->highest_version which becomes 0.
>         3. jffs2_commit_write() invokes jffs2_write_dnode() with version=0.
>
>         5. Powerfail before obsoleting least recent overlapping nodes.
>
>         6. After reset, the scan process finds two(if were only one node for the
>         commited page before) valid nodes wich refer to the same region. It places
>         the least recent node which has the maximum version number at the end of
>         the node list.
>         7. When jffs2_read_inode() function is invoked, the node with the biggest
>         version number is added last, thus, obsoleting all overlapping nodes.
>         The most recent inode is obsoleted as well. --> Bug.
>
> As a workaround I suggest to obsolete previous nodes before writing the new
> one. In case of powerfail there will be holes in data which can be easily
> recognized during inode reading.

On NAND flash (and some NOR flash chips), the nodes can't physically
be marked obsolete on the chip.  So JFFS2 has to figure it all out at
scan time for those regardless.

What Artem was asking is if it was physically possible to have a
file/directory with 4294967296 versions to being with.  Take a 1 byte
file as an example.  If that was the only file on the whole device,
and you had that many versions of it you'd have:

68 bytes overhead per version + 1 byte of data per version =
296352743424 bytes required to store.

That's 276 GiB.  Which isn't even sane for JFFS2 anyway.

josh

Re: JFFS2 node versioning problem?

[Josh Boyer]

On 5/3/06, Josh Boyer <jwboyer@gmail.com> wrote:
>
> What Artem was asking is if it was physically possible to have a
> file/directory with 4294967296 versions to being with.  Take a 1 byte
> file as an example.  If that was the only file on the whole device,
> and you had that many versions of it you'd have:
>
> 68 bytes overhead per version + 1 byte of data per version =
> 296352743424 bytes required to store.
>
> That's 276 GiB.  Which isn't even sane for JFFS2 anyway.

Of course, that's the worst possible case and you can run into
situations where not all of those nodes are on flash.

I shouldn't do math before having coffee.

josh

Re: JFFS2 node versioning problem?

[Jörn Engel]

On Wed, 3 May 2006 10:07:22 -0500, Josh Boyer wrote:
> 
> What Artem was asking is if it was physically possible to have a
> file/directory with 4294967296 versions to being with.  Take a 1 byte
> file as an example.  If that was the only file on the whole device,
> and you had that many versions of it you'd have:
> 
> 68 bytes overhead per version + 1 byte of data per version =

68 bytes + 1 byte + 3 bytes padding

> 296352743424 bytes required to store.

309237645312

> That's 276 GiB.  Which isn't even sane for JFFS2 anyway.

Divided by 100k erase cycles:
3.092.376

3MiB is not that insane at all.  Yes, we can theoretically run into
this problem.  But the probability is fairly low.  I'm not too worried
about this.

Jörn

-- 
Measure. Don't tune for speed until you've measured, and even then
don't unless one part of the code overwhelms the rest.
-- Rob Pike