JFFS3 & deletion dirents RFC

JFFS3 & deletion dirents RFC

[Artem B. Bityuckiy]

Hello, I've found some time to share my old Idea concerning the JFFS2 
deleted/deletion dirent processing and the similar in JFFS3.


Brief problem description
~~~~~~~~~~~~~~~~~~~~~~~~

JFFS2 removes direntries by means of writing deletion direntries. Deletion 
dirents are the same nodes as deleted dirents but with the target inode 
number 0. Deletion dirents refer deleted ones by means of name.

Example:

1. Before the deletion we have a dirent named "kaka" with the target inode 
"1980"

-----------
| kaka    |
-----------
| 1980    |
-----------

2. After the deletion we have 2 dirents - older, "kaka" with the target 
inode "1980" (deleted dirent) and newer, "kaka" with the target inode 0.

-----------
| kaka    |
-----------       <-- deleted dirent
| 1980    |
-----------

-----------
| kaka    |
-----------       <-- deletion dirent
| 0       |
-----------

It is possible that there are several instances of the deleted dirent on 
flash (due to GC) or there are previous versions of the deleted dirent 
present (due to dirent updates). E.g.:


-----------
| kaka    |
-----------       <-- an old (and obsolete) "kaka" node
| 1980    |
-----------
| 95      |<-- version
-----------

-----------
| kaka    |
-----------       <-- deleted dirent
| 1980    |
-----------
| 100     |
-----------

-----------
| kaka    |
-----------       <-- deletion dirent
| 0       |
-----------
| 304     |
-----------


There are 2 major drawback of such design:

1. GC of deletion dirents becomes slow and complicated. Before we may 
remove a deletion dirent, we have to make sure there are no instances of 
the deleted dirent on flash exist. Since the in-core data structures do 
not contain dirents' names, JFFS2 has nothing to do except to *physically* 
read all the obsolete dirent nodes belonging to the deletion dirent's 
inode and compare names. Reads involve CRC checking. This may be very slow 
(look at jffs2_garbage_collect_deletion_dirent()).

2. During mount we need to read dirents' names and check their CRCs.
Furthermore, we need to calculate the inodes' nlinks for which reason we 
need to locate all the deleted dirents, comparing them by name. This is 
rather slow.


Proposed JFFS3 approach
~~~~~~~~~~~~~~~~~~~~~~

I propose to refer deleted dirents by their versions.

-----------
| kaka    |
-----------       <-- deleted dirent
| 1980    |
-----------
| 100     |<-- version
-----------

-----------
| 0       |
-----------       <-- deletion dirent
| 100     |
-----------

Here the deletion dirent specifies the deleted dirent by its version 
number (100). The name is unneeded in the deletion dirent. Since there may 
be more then one instance of the deleted dirent, I offer to write a 
deletion dirent for each instance:

1. Whenever a dirent is updated, i.e. newer node is written, we may write 
a deletion node for its previous instance at once.

2. Whenever a dirent is GCed, its version number is preserved, so we will 
have two dirents with equivalent versions. In this case we don't need to 
write any additional deletion dirent.

Additionally, we introduce the "version" field to the "struct 
jffs2_raw_node_ref" structure. In this case, the 
jffs2_garbage_collect_deletion_dirent() function will work as follows:

exist = 0;
for (each_node_ref) {
	if (cur_ref->version == deleted_version) {
		exist += 1;
		break;
	}
}

if (exist) {
	/* Move the deletion dirent as it still refers
	 * an existing deleted dirent's node */
} else {
	/* Mark the deletion dirent obsolete and do
	 * not move it to the new block */
}

The mount process must also be faster.

The drawback is that we need to increase the size of in-core node_ref  
objects. But it seems for me as not so bad thing because we're going to 
introduce an in-core memory shrink mechanism to JFFS3 (ICP, ...).

Opinions?

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

Re: JFFS3 & deletion dirents RFC

[Jared Hulbert]

Forgive me if my ignorance is obvious...
Are there any implications to non-dirent nodes?  Shouldn't this speed
up the GC, mount time for any node?  If not then the version field for
non-dirent nodes is utterly wasted, right?  If the version field is
wasted for all non-dirent nodes (in other words, most nodes) then it
seems like a bad idea to add a WORD or DWORD to each node. If there is
a way to make version field only apply to dirent nodes then it would
be much better, of course that sounds ugly without even thinking it
through too far.

Re: JFFS3 & deletion dirents RFC

[Artem B. Bityuckiy]

Jared Hulbert wrote:
> Forgive me if my ignorance is obvious...
> Are there any implications to non-dirent nodes?
No, in data nodes versions play another and very important role. 
Basically, they help to distinguish between valid and obsolete data when 
the data nodes' data ranges overlap.

> Shouldn't this speed
> up the GC, mount time for any node?  If not then the version field for
> non-dirent nodes is utterly wasted, right?  If the version field is
> wasted for all non-dirent nodes (in other words, most nodes) then it
> seems like a bad idea to add a WORD or DWORD to each node. If there is
> a way to make version field only apply to dirent nodes then it would
> be much better, of course that sounds ugly without even thinking it
> through too far.

We can't get rid of version in data nodes.

Example:

data node A has data that covers file's range 0-100
data node B has data that covers file's range 10-110

How can we detect from which node should we fetch data of the 10-100 
range? JFFS2 uses version for this reason.

Dirents' versions play another role.

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

Re: JFFS3 & deletion dirents RFC

[Jared Hulbert]

> We can't get rid of version in data nodes.

I'm not suggesting we get rid of 'version' in the actual nodes.

As I understand this adding 'version' to struct jffs2_raw_node_ref
increases the RAM usage by N*(X+Y) where:
  N is the size of the version field
  X is the number of direnties
  Y is the number of data nodes

It seems there "ought" to be a way to only increase RAM size by N*X. 
I'm assuming Y>>X so this could be a big factor for RAM usage.

Am I missing something?

 ,Jared

Re: JFFS3 & deletion dirents RFC

[Artem B. Bityuckiy]

On Thu, 2005-03-24 at 14:01 -0800, Jared Hulbert wrote:
> > We can't get rid of version in data nodes.
> 
> I'm not suggesting we get rid of 'version' in the actual nodes.
> 
> As I understand this adding 'version' to struct jffs2_raw_node_ref
> increases the RAM usage by N*(X+Y) where:
>   N is the size of the version field
>   X is the number of direnties
>   Y is the number of data nodes
> 
> It seems there "ought" to be a way to only increase RAM size by N*X. 
> I'm assuming Y>>X so this could be a big factor for RAM usage.
> 
> Am I missing something?
> 
>  ,Jared
Ok, now I understand you. Yes, good point, thanks. Frankly, I bear in
mind 2 more things which I didn't publish:

1. We will have some memory "reap" or "shrink" mechanism in JFFS3
(possibly with the ICP help), this is why I so bravely increase the
node_ref's size.
2. I strongly suspect that the version field well be very useful for
other purposes as well, even in the inode node (AKA data node)
node_refs. This is why I don't afraid to add version to node_refs of all
node types.

So, I still need to design more precisely that "shrink" mechanism and to
prove other usage of (node_ref)->version.