3 files changed, 168 insertions, 2 deletions

diff --git a/fs/ubifs/debug.c b/fs/ubifs/debug.c
index c2a68baa782f..c664f10aec6c 100644
--- a/fs/ubifs/debug.c
+++ b/fs/ubifs/debug.c
@@ -2239,6 +2239,162 @@ out_free:
         return err;
 }
 
+/**
+ * dbg_check_data_nodes_order - check that list of data nodes is sorted.
+ * @c: UBIFS file-system description object
+ * @head: the list of nodes ('struct ubifs_scan_node' objects)
+ *
+ * This function returns zero if the list of data nodes is sorted correctly,
+ * and %-EINVAL if not.
+ */
+int dbg_check_data_nodes_order(struct ubifs_info *c, struct list_head *head)
+{
+        struct list_head *cur;
+        struct ubifs_scan_node *sa, *sb;
+
+        if (!(ubifs_chk_flags & UBIFS_CHK_GEN))
+                return 0;
+
+        for (cur = head->next; cur->next != head; cur = cur->next) {
+                ino_t inuma, inumb;
+                uint32_t blka, blkb;
+
+                cond_resched();
+                sa = container_of(cur, struct ubifs_scan_node, list);
+                sb = container_of(cur->next, struct ubifs_scan_node, list);
+
+                if (sa->type != UBIFS_DATA_NODE) {
+                        ubifs_err("bad node type %d", sa->type);
+                        dbg_dump_node(c, sa->node);
+                        return -EINVAL;
+                }
+                if (sb->type != UBIFS_DATA_NODE) {
+                        ubifs_err("bad node type %d", sb->type);
+                        dbg_dump_node(c, sb->node);
+                        return -EINVAL;
+                }
+
+                inuma = key_inum(c, &sa->key);
+                inumb = key_inum(c, &sb->key);
+
+                if (inuma < inumb)
+                        continue;
+                if (inuma > inumb) {
+                        ubifs_err("larger inum %lu goes before inum %lu",
+                                  (unsigned long)inuma, (unsigned long)inumb);
+                        goto error_dump;
+                }
+
+                blka = key_block(c, &sa->key);
+                blkb = key_block(c, &sb->key);
+
+                if (blka > blkb) {
+                        ubifs_err("larger block %u goes before %u", blka, blkb);
+                        goto error_dump;
+                }
+                if (blka == blkb) {
+                        ubifs_err("two data nodes for the same block");
+                        goto error_dump;
+                }
+        }
+
+        return 0;
+
+error_dump:
+        dbg_dump_node(c, sa->node);
+        dbg_dump_node(c, sb->node);
+        return -EINVAL;
+}
+
+/**
+ * dbg_check_nondata_nodes_order - check that list of data nodes is sorted.
+ * @c: UBIFS file-system description object
+ * @head: the list of nodes ('struct ubifs_scan_node' objects)
+ *
+ * This function returns zero if the list of non-data nodes is sorted correctly,
+ * and %-EINVAL if not.
+ */
+int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head)
+{
+        struct list_head *cur;
+        struct ubifs_scan_node *sa, *sb;
+
+        if (!(ubifs_chk_flags & UBIFS_CHK_GEN))
+                return 0;
+
+        for (cur = head->next; cur->next != head; cur = cur->next) {
+                ino_t inuma, inumb;
+                uint32_t hasha, hashb;
+
+                cond_resched();
+                sa = container_of(cur, struct ubifs_scan_node, list);
+                sb = container_of(cur->next, struct ubifs_scan_node, list);
+
+                if (sa->type != UBIFS_INO_NODE && sa->type != UBIFS_DENT_NODE &&
+                    sa->type != UBIFS_XENT_NODE) {
+                        ubifs_err("bad node type %d", sa->type);
+                        dbg_dump_node(c, sa->node);
+                        return -EINVAL;
+                }
+                if (sa->type != UBIFS_INO_NODE && sa->type != UBIFS_DENT_NODE &&
+                    sa->type != UBIFS_XENT_NODE) {
+                        ubifs_err("bad node type %d", sb->type);
+                        dbg_dump_node(c, sb->node);
+                        return -EINVAL;
+                }
+
+                if (sa->type != UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) {
+                        ubifs_err("non-inode node goes before inode node");
+                        goto error_dump;
+                }
+
+                if (sa->type == UBIFS_INO_NODE && sb->type != UBIFS_INO_NODE)
+                        continue;
+
+                if (sa->type == UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) {
+                        /* Inode nodes are sorted in descending size order */
+                        if (sa->len < sb->len) {
+                                ubifs_err("smaller inode node goes first");
+                                goto error_dump;
+                        }
+                        continue;
+                }
+
+                /*
+                 * This is either a dentry or xentry, which should be sorted in
+                 * ascending (parent ino, hash) order.
+                 */
+                inuma = key_inum(c, &sa->key);
+                inumb = key_inum(c, &sb->key);
+
+                if (inuma < inumb)
+                        continue;
+                if (inuma > inumb) {
+                        ubifs_err("larger inum %lu goes before inum %lu",
+                                  (unsigned long)inuma, (unsigned long)inumb);
+                        goto error_dump;
+                }
+
+                hasha = key_block(c, &sa->key);
+                hashb = key_block(c, &sb->key);
+
+                if (hasha > hashb) {
+                        ubifs_err("larger hash %u goes before %u", hasha, hashb);
+                        goto error_dump;
+                }
+        }
+
+        return 0;
+
+error_dump:
+        ubifs_msg("dumping first node");
+        dbg_dump_node(c, sa->node);
+        ubifs_msg("dumping second node");
+        dbg_dump_node(c, sb->node);
+        return -EINVAL;
+        return 0;
+}
+
 static int invocation_cnt;
 
 int dbg_force_in_the_gaps(void)
diff --git a/fs/ubifs/debug.h b/fs/ubifs/debug.h
index 29d960101ea6..69ebe4729151 100644
--- a/fs/ubifs/debug.h
+++ b/fs/ubifs/debug.h
@@ -324,6 +324,8 @@ int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,
                         int row, int col);
 int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode,
                          loff_t size);
+int dbg_check_data_nodes_order(struct ubifs_info *c, struct list_head *head);
+int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head);
 
 /* Force the use of in-the-gaps method for testing */
 
@@ -465,6 +467,8 @@ void dbg_debugfs_exit_fs(struct ubifs_info *c);
 #define dbg_check_lprops(c)                        0
 #define dbg_check_lpt_nodes(c, cnode, row, col)    0
 #define dbg_check_inode_size(c, inode, size)       0
+#define dbg_check_data_nodes_order(c, head)        0
+#define dbg_check_nondata_nodes_order(c, head)     0
 #define dbg_force_in_the_gaps_enabled              0
 #define dbg_force_in_the_gaps()                    0
 #define dbg_failure_mode                           0
diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 4fc31ca0e3b1..396f24a30af9 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -242,14 +242,13 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
                       struct list_head *nondata, int *min)
 {
+        int err;
         struct ubifs_scan_node *snod, *tmp;
 
         *min = INT_MAX;