Message ID | 1281169577-18664-5-git-send-email-dedekind1@gmail.com |
---|---|
State | New, archived |
Headers | show |
Artem Bityutskiy wrote: > From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com> > > Unfortunately, the comparison functions for both data and non-data nodes > ('data_nodes_cmp()' and 'nondata_nodes_cmp()') was screwed. It did not > work for the case when 'inuma == inumb' and 'blka > blkb' or 'hasha > hashb'. Can you explain a bit more. The old logic looks OK to me whereas the new logic would seem to make block 0x80000001 < 0x00000001 ? > > Basically, this means that it did not actually sort the list. This is not > fatal, but this means that GC did not optimize the on-flash layout as we > thought it would. > > This issue was revealed by commit '835cc0c8477fdbc59e0217891d6f11061b1ac4e2' of > Don Mullis: assertions in the comparison functions started triggering. > > This patch fixes the issue. Additionally, it makes the comparison functions > return immediately the elements to compare are actually the same element. > This is just a tiny optimization. > > Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com> > --- > fs/ubifs/gc.c | 34 ++++++++++++++-------------------- > 1 files changed, 14 insertions(+), 20 deletions(-) > > diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c > index d060c62..fbb9272 100644 > --- a/fs/ubifs/gc.c > +++ b/fs/ubifs/gc.c > @@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) > struct ubifs_scan_node *sa, *sb; > > cond_resched(); > + if (a == b) > + return 0; > + > sa = list_entry(a, struct ubifs_scan_node, list); > sb = list_entry(b, struct ubifs_scan_node, list); > ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY); > @@ -133,16 +136,10 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) > inuma = key_inum(c, &sa->key); > inumb = key_inum(c, &sb->key); > > - if (inuma == inumb) { > - unsigned int blka = key_block(c, &sa->key); > - unsigned int blkb = key_block(c, &sb->key); > - > - if (blka <= blkb) > - return -1; > - } else if (inuma <= inumb) > - return -1; > - > - return 1; > + if (inuma == inumb) > + return key_block(c, &sa->key) - key_block(c, &sb->key); > + else > + return inuma - inumb; > } > > /* > @@ -163,6 +160,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) > struct ubifs_scan_node *sa, *sb; > > cond_resched(); > + if (a == b) > + return 0; > + > sa = list_entry(a, struct ubifs_scan_node, list); > sb = list_entry(b, struct ubifs_scan_node, list); > typea = key_type(c, &sa->key); > @@ -183,16 +183,10 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) > inuma = key_inum(c, &sa->key); > inumb = key_inum(c, &sb->key); > > - if (inuma == inumb) { > - uint32_t hasha = key_hash(c, &sa->key); > - uint32_t hashb = key_hash(c, &sb->key); > - > - if (hasha <= hashb) > - return -1; > - } else if (inuma <= inumb) > - return -1; > - > - return 1; > + if (inuma == inumb) > + return key_hash(c, &sa->key) - key_hash(c, &sb->key); > + else > + return inuma - inumb; > } > > /**
On Sat, 2010-08-07 at 15:11 +0300, Adrian Hunter wrote: > Artem Bityutskiy wrote: > > From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com> > > > > Unfortunately, the comparison functions for both data and non-data nodes > > ('data_nodes_cmp()' and 'nondata_nodes_cmp()') was screwed. It did not > > work for the case when 'inuma == inumb' and 'blka > blkb' or 'hasha > hashb'. > > Can you explain a bit more. The old logic looks OK to me whereas the > new logic would seem to make block 0x80000001 < 0x00000001 ? Yes, I need to look once again at this...
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c index d060c62..fbb9272 100644 --- a/fs/ubifs/gc.c +++ b/fs/ubifs/gc.c @@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) struct ubifs_scan_node *sa, *sb; cond_resched(); + if (a == b) + return 0; + sa = list_entry(a, struct ubifs_scan_node, list); sb = list_entry(b, struct ubifs_scan_node, list); ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY); @@ -133,16 +136,10 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) inuma = key_inum(c, &sa->key); inumb = key_inum(c, &sb->key); - if (inuma == inumb) { - unsigned int blka = key_block(c, &sa->key); - unsigned int blkb = key_block(c, &sb->key); - - if (blka <= blkb) - return -1; - } else if (inuma <= inumb) - return -1; - - return 1; + if (inuma == inumb) + return key_block(c, &sa->key) - key_block(c, &sb->key); + else + return inuma - inumb; } /* @@ -163,6 +160,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) struct ubifs_scan_node *sa, *sb; cond_resched(); + if (a == b) + return 0; + sa = list_entry(a, struct ubifs_scan_node, list); sb = list_entry(b, struct ubifs_scan_node, list); typea = key_type(c, &sa->key); @@ -183,16 +183,10 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) inuma = key_inum(c, &sa->key); inumb = key_inum(c, &sb->key); - if (inuma == inumb) { - uint32_t hasha = key_hash(c, &sa->key); - uint32_t hashb = key_hash(c, &sb->key); - - if (hasha <= hashb) - return -1; - } else if (inuma <= inumb) - return -1; - - return 1; + if (inuma == inumb) + return key_hash(c, &sa->key) - key_hash(c, &sb->key); + else + return inuma - inumb; } /**