Back to home page

OSCL-LXR

 
 

    


0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * This file is part of UBIFS.
0004  *
0005  * Copyright (C) 2006-2008 Nokia Corporation.
0006  *
0007  * Authors: Adrian Hunter
0008  *          Artem Bityutskiy (Битюцкий Артём)
0009  */
0010 
0011 /*
0012  * This file implements functions that manage the running of the commit process.
0013  * Each affected module has its own functions to accomplish their part in the
0014  * commit and those functions are called here.
0015  *
0016  * The commit is the process whereby all updates to the index and LEB properties
0017  * are written out together and the journal becomes empty. This keeps the
0018  * file system consistent - at all times the state can be recreated by reading
0019  * the index and LEB properties and then replaying the journal.
0020  *
0021  * The commit is split into two parts named "commit start" and "commit end".
0022  * During commit start, the commit process has exclusive access to the journal
0023  * by holding the commit semaphore down for writing. As few I/O operations as
0024  * possible are performed during commit start, instead the nodes that are to be
0025  * written are merely identified. During commit end, the commit semaphore is no
0026  * longer held and the journal is again in operation, allowing users to continue
0027  * to use the file system while the bulk of the commit I/O is performed. The
0028  * purpose of this two-step approach is to prevent the commit from causing any
0029  * latency blips. Note that in any case, the commit does not prevent lookups
0030  * (as permitted by the TNC mutex), or access to VFS data structures e.g. page
0031  * cache.
0032  */
0033 
0034 #include <linux/freezer.h>
0035 #include <linux/kthread.h>
0036 #include <linux/slab.h>
0037 #include "ubifs.h"
0038 
0039 /*
0040  * nothing_to_commit - check if there is nothing to commit.
0041  * @c: UBIFS file-system description object
0042  *
0043  * This is a helper function which checks if there is anything to commit. It is
0044  * used as an optimization to avoid starting the commit if it is not really
0045  * necessary. Indeed, the commit operation always assumes flash I/O (e.g.,
0046  * writing the commit start node to the log), and it is better to avoid doing
0047  * this unnecessarily. E.g., 'ubifs_sync_fs()' runs the commit, but if there is
0048  * nothing to commit, it is more optimal to avoid any flash I/O.
0049  *
0050  * This function has to be called with @c->commit_sem locked for writing -
0051  * this function does not take LPT/TNC locks because the @c->commit_sem
0052  * guarantees that we have exclusive access to the TNC and LPT data structures.
0053  *
0054  * This function returns %1 if there is nothing to commit and %0 otherwise.
0055  */
0056 static int nothing_to_commit(struct ubifs_info *c)
0057 {
0058     /*
0059      * During mounting or remounting from R/O mode to R/W mode we may
0060      * commit for various recovery-related reasons.
0061      */
0062     if (c->mounting || c->remounting_rw)
0063         return 0;
0064 
0065     /*
0066      * If the root TNC node is dirty, we definitely have something to
0067      * commit.
0068      */
0069     if (c->zroot.znode && ubifs_zn_dirty(c->zroot.znode))
0070         return 0;
0071 
0072     /*
0073      * Even though the TNC is clean, the LPT tree may have dirty nodes. For
0074      * example, this may happen if the budgeting subsystem invoked GC to
0075      * make some free space, and the GC found an LEB with only dirty and
0076      * free space. In this case GC would just change the lprops of this
0077      * LEB (by turning all space into free space) and unmap it.
0078      */
0079     if (c->nroot && test_bit(DIRTY_CNODE, &c->nroot->flags))
0080         return 0;
0081 
0082     ubifs_assert(c, atomic_long_read(&c->dirty_zn_cnt) == 0);
0083     ubifs_assert(c, c->dirty_pn_cnt == 0);
0084     ubifs_assert(c, c->dirty_nn_cnt == 0);
0085 
0086     return 1;
0087 }
0088 
0089 /**
0090  * do_commit - commit the journal.
0091  * @c: UBIFS file-system description object
0092  *
0093  * This function implements UBIFS commit. It has to be called with commit lock
0094  * locked. Returns zero in case of success and a negative error code in case of
0095  * failure.
0096  */
0097 static int do_commit(struct ubifs_info *c)
0098 {
0099     int err, new_ltail_lnum, old_ltail_lnum, i;
0100     struct ubifs_zbranch zroot;
0101     struct ubifs_lp_stats lst;
0102 
0103     dbg_cmt("start");
0104     ubifs_assert(c, !c->ro_media && !c->ro_mount);
0105 
0106     if (c->ro_error) {
0107         err = -EROFS;
0108         goto out_up;
0109     }
0110 
0111     if (nothing_to_commit(c)) {
0112         up_write(&c->commit_sem);
0113         err = 0;
0114         goto out_cancel;
0115     }
0116 
0117     /* Sync all write buffers (necessary for recovery) */
0118     for (i = 0; i < c->jhead_cnt; i++) {
0119         err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
0120         if (err)
0121             goto out_up;
0122     }
0123 
0124     c->cmt_no += 1;
0125     err = ubifs_gc_start_commit(c);
0126     if (err)
0127         goto out_up;
0128     err = dbg_check_lprops(c);
0129     if (err)
0130         goto out_up;
0131     err = ubifs_log_start_commit(c, &new_ltail_lnum);
0132     if (err)
0133         goto out_up;
0134     err = ubifs_tnc_start_commit(c, &zroot);
0135     if (err)
0136         goto out_up;
0137     err = ubifs_lpt_start_commit(c);
0138     if (err)
0139         goto out_up;
0140     err = ubifs_orphan_start_commit(c);
0141     if (err)
0142         goto out_up;
0143 
0144     ubifs_get_lp_stats(c, &lst);
0145 
0146     up_write(&c->commit_sem);
0147 
0148     err = ubifs_tnc_end_commit(c);
0149     if (err)
0150         goto out;
0151     err = ubifs_lpt_end_commit(c);
0152     if (err)
0153         goto out;
0154     err = ubifs_orphan_end_commit(c);
0155     if (err)
0156         goto out;
0157     err = dbg_check_old_index(c, &zroot);
0158     if (err)
0159         goto out;
0160 
0161     c->mst_node->cmt_no      = cpu_to_le64(c->cmt_no);
0162     c->mst_node->log_lnum    = cpu_to_le32(new_ltail_lnum);
0163     c->mst_node->root_lnum   = cpu_to_le32(zroot.lnum);
0164     c->mst_node->root_offs   = cpu_to_le32(zroot.offs);
0165     c->mst_node->root_len    = cpu_to_le32(zroot.len);
0166     c->mst_node->ihead_lnum  = cpu_to_le32(c->ihead_lnum);
0167     c->mst_node->ihead_offs  = cpu_to_le32(c->ihead_offs);
0168     c->mst_node->index_size  = cpu_to_le64(c->bi.old_idx_sz);
0169     c->mst_node->lpt_lnum    = cpu_to_le32(c->lpt_lnum);
0170     c->mst_node->lpt_offs    = cpu_to_le32(c->lpt_offs);
0171     c->mst_node->nhead_lnum  = cpu_to_le32(c->nhead_lnum);
0172     c->mst_node->nhead_offs  = cpu_to_le32(c->nhead_offs);
0173     c->mst_node->ltab_lnum   = cpu_to_le32(c->ltab_lnum);
0174     c->mst_node->ltab_offs   = cpu_to_le32(c->ltab_offs);
0175     c->mst_node->lsave_lnum  = cpu_to_le32(c->lsave_lnum);
0176     c->mst_node->lsave_offs  = cpu_to_le32(c->lsave_offs);
0177     c->mst_node->lscan_lnum  = cpu_to_le32(c->lscan_lnum);
0178     c->mst_node->empty_lebs  = cpu_to_le32(lst.empty_lebs);
0179     c->mst_node->idx_lebs    = cpu_to_le32(lst.idx_lebs);
0180     c->mst_node->total_free  = cpu_to_le64(lst.total_free);
0181     c->mst_node->total_dirty = cpu_to_le64(lst.total_dirty);
0182     c->mst_node->total_used  = cpu_to_le64(lst.total_used);
0183     c->mst_node->total_dead  = cpu_to_le64(lst.total_dead);
0184     c->mst_node->total_dark  = cpu_to_le64(lst.total_dark);
0185     if (c->no_orphs)
0186         c->mst_node->flags |= cpu_to_le32(UBIFS_MST_NO_ORPHS);
0187     else
0188         c->mst_node->flags &= ~cpu_to_le32(UBIFS_MST_NO_ORPHS);
0189 
0190     old_ltail_lnum = c->ltail_lnum;
0191     err = ubifs_log_end_commit(c, new_ltail_lnum);
0192     if (err)
0193         goto out;
0194 
0195     err = ubifs_log_post_commit(c, old_ltail_lnum);
0196     if (err)
0197         goto out;
0198     err = ubifs_gc_end_commit(c);
0199     if (err)
0200         goto out;
0201     err = ubifs_lpt_post_commit(c);
0202     if (err)
0203         goto out;
0204 
0205 out_cancel:
0206     spin_lock(&c->cs_lock);
0207     c->cmt_state = COMMIT_RESTING;
0208     wake_up(&c->cmt_wq);
0209     dbg_cmt("commit end");
0210     spin_unlock(&c->cs_lock);
0211     return 0;
0212 
0213 out_up:
0214     up_write(&c->commit_sem);
0215 out:
0216     ubifs_err(c, "commit failed, error %d", err);
0217     spin_lock(&c->cs_lock);
0218     c->cmt_state = COMMIT_BROKEN;
0219     wake_up(&c->cmt_wq);
0220     spin_unlock(&c->cs_lock);
0221     ubifs_ro_mode(c, err);
0222     return err;
0223 }
0224 
0225 /**
0226  * run_bg_commit - run background commit if it is needed.
0227  * @c: UBIFS file-system description object
0228  *
0229  * This function runs background commit if it is needed. Returns zero in case
0230  * of success and a negative error code in case of failure.
0231  */
0232 static int run_bg_commit(struct ubifs_info *c)
0233 {
0234     spin_lock(&c->cs_lock);
0235     /*
0236      * Run background commit only if background commit was requested or if
0237      * commit is required.
0238      */
0239     if (c->cmt_state != COMMIT_BACKGROUND &&
0240         c->cmt_state != COMMIT_REQUIRED)
0241         goto out;
0242     spin_unlock(&c->cs_lock);
0243 
0244     down_write(&c->commit_sem);
0245     spin_lock(&c->cs_lock);
0246     if (c->cmt_state == COMMIT_REQUIRED)
0247         c->cmt_state = COMMIT_RUNNING_REQUIRED;
0248     else if (c->cmt_state == COMMIT_BACKGROUND)
0249         c->cmt_state = COMMIT_RUNNING_BACKGROUND;
0250     else
0251         goto out_cmt_unlock;
0252     spin_unlock(&c->cs_lock);
0253 
0254     return do_commit(c);
0255 
0256 out_cmt_unlock:
0257     up_write(&c->commit_sem);
0258 out:
0259     spin_unlock(&c->cs_lock);
0260     return 0;
0261 }
0262 
0263 /**
0264  * ubifs_bg_thread - UBIFS background thread function.
0265  * @info: points to the file-system description object
0266  *
0267  * This function implements various file-system background activities:
0268  * o when a write-buffer timer expires it synchronizes the appropriate
0269  *   write-buffer;
0270  * o when the journal is about to be full, it starts in-advance commit.
0271  *
0272  * Note, other stuff like background garbage collection may be added here in
0273  * future.
0274  */
0275 int ubifs_bg_thread(void *info)
0276 {
0277     int err;
0278     struct ubifs_info *c = info;
0279 
0280     ubifs_msg(c, "background thread \"%s\" started, PID %d",
0281           c->bgt_name, current->pid);
0282     set_freezable();
0283 
0284     while (1) {
0285         if (kthread_should_stop())
0286             break;
0287 
0288         if (try_to_freeze())
0289             continue;
0290 
0291         set_current_state(TASK_INTERRUPTIBLE);
0292         /* Check if there is something to do */
0293         if (!c->need_bgt) {
0294             /*
0295              * Nothing prevents us from going sleep now and
0296              * be never woken up and block the task which
0297              * could wait in 'kthread_stop()' forever.
0298              */
0299             if (kthread_should_stop())
0300                 break;
0301             schedule();
0302             continue;
0303         } else
0304             __set_current_state(TASK_RUNNING);
0305 
0306         c->need_bgt = 0;
0307         err = ubifs_bg_wbufs_sync(c);
0308         if (err)
0309             ubifs_ro_mode(c, err);
0310 
0311         run_bg_commit(c);
0312         cond_resched();
0313     }
0314 
0315     ubifs_msg(c, "background thread \"%s\" stops", c->bgt_name);
0316     return 0;
0317 }
0318 
0319 /**
0320  * ubifs_commit_required - set commit state to "required".
0321  * @c: UBIFS file-system description object
0322  *
0323  * This function is called if a commit is required but cannot be done from the
0324  * calling function, so it is just flagged instead.
0325  */
0326 void ubifs_commit_required(struct ubifs_info *c)
0327 {
0328     spin_lock(&c->cs_lock);
0329     switch (c->cmt_state) {
0330     case COMMIT_RESTING:
0331     case COMMIT_BACKGROUND:
0332         dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
0333             dbg_cstate(COMMIT_REQUIRED));
0334         c->cmt_state = COMMIT_REQUIRED;
0335         break;
0336     case COMMIT_RUNNING_BACKGROUND:
0337         dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
0338             dbg_cstate(COMMIT_RUNNING_REQUIRED));
0339         c->cmt_state = COMMIT_RUNNING_REQUIRED;
0340         break;
0341     case COMMIT_REQUIRED:
0342     case COMMIT_RUNNING_REQUIRED:
0343     case COMMIT_BROKEN:
0344         break;
0345     }
0346     spin_unlock(&c->cs_lock);
0347 }
0348 
0349 /**
0350  * ubifs_request_bg_commit - notify the background thread to do a commit.
0351  * @c: UBIFS file-system description object
0352  *
0353  * This function is called if the journal is full enough to make a commit
0354  * worthwhile, so background thread is kicked to start it.
0355  */
0356 void ubifs_request_bg_commit(struct ubifs_info *c)
0357 {
0358     spin_lock(&c->cs_lock);
0359     if (c->cmt_state == COMMIT_RESTING) {
0360         dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
0361             dbg_cstate(COMMIT_BACKGROUND));
0362         c->cmt_state = COMMIT_BACKGROUND;
0363         spin_unlock(&c->cs_lock);
0364         ubifs_wake_up_bgt(c);
0365     } else
0366         spin_unlock(&c->cs_lock);
0367 }
0368 
0369 /**
0370  * wait_for_commit - wait for commit.
0371  * @c: UBIFS file-system description object
0372  *
0373  * This function sleeps until the commit operation is no longer running.
0374  */
0375 static int wait_for_commit(struct ubifs_info *c)
0376 {
0377     dbg_cmt("pid %d goes sleep", current->pid);
0378 
0379     /*
0380      * The following sleeps if the condition is false, and will be woken
0381      * when the commit ends. It is possible, although very unlikely, that we
0382      * will wake up and see the subsequent commit running, rather than the
0383      * one we were waiting for, and go back to sleep.  However, we will be
0384      * woken again, so there is no danger of sleeping forever.
0385      */
0386     wait_event(c->cmt_wq, c->cmt_state != COMMIT_RUNNING_BACKGROUND &&
0387                   c->cmt_state != COMMIT_RUNNING_REQUIRED);
0388     dbg_cmt("commit finished, pid %d woke up", current->pid);
0389     return 0;
0390 }
0391 
0392 /**
0393  * ubifs_run_commit - run or wait for commit.
0394  * @c: UBIFS file-system description object
0395  *
0396  * This function runs commit and returns zero in case of success and a negative
0397  * error code in case of failure.
0398  */
0399 int ubifs_run_commit(struct ubifs_info *c)
0400 {
0401     int err = 0;
0402 
0403     spin_lock(&c->cs_lock);
0404     if (c->cmt_state == COMMIT_BROKEN) {
0405         err = -EROFS;
0406         goto out;
0407     }
0408 
0409     if (c->cmt_state == COMMIT_RUNNING_BACKGROUND)
0410         /*
0411          * We set the commit state to 'running required' to indicate
0412          * that we want it to complete as quickly as possible.
0413          */
0414         c->cmt_state = COMMIT_RUNNING_REQUIRED;
0415 
0416     if (c->cmt_state == COMMIT_RUNNING_REQUIRED) {
0417         spin_unlock(&c->cs_lock);
0418         return wait_for_commit(c);
0419     }
0420     spin_unlock(&c->cs_lock);
0421 
0422     /* Ok, the commit is indeed needed */
0423 
0424     down_write(&c->commit_sem);
0425     spin_lock(&c->cs_lock);
0426     /*
0427      * Since we unlocked 'c->cs_lock', the state may have changed, so
0428      * re-check it.
0429      */
0430     if (c->cmt_state == COMMIT_BROKEN) {
0431         err = -EROFS;
0432         goto out_cmt_unlock;
0433     }
0434 
0435     if (c->cmt_state == COMMIT_RUNNING_BACKGROUND)
0436         c->cmt_state = COMMIT_RUNNING_REQUIRED;
0437 
0438     if (c->cmt_state == COMMIT_RUNNING_REQUIRED) {
0439         up_write(&c->commit_sem);
0440         spin_unlock(&c->cs_lock);
0441         return wait_for_commit(c);
0442     }
0443     c->cmt_state = COMMIT_RUNNING_REQUIRED;
0444     spin_unlock(&c->cs_lock);
0445 
0446     err = do_commit(c);
0447     return err;
0448 
0449 out_cmt_unlock:
0450     up_write(&c->commit_sem);
0451 out:
0452     spin_unlock(&c->cs_lock);
0453     return err;
0454 }
0455 
0456 /**
0457  * ubifs_gc_should_commit - determine if it is time for GC to run commit.
0458  * @c: UBIFS file-system description object
0459  *
0460  * This function is called by garbage collection to determine if commit should
0461  * be run. If commit state is @COMMIT_BACKGROUND, which means that the journal
0462  * is full enough to start commit, this function returns true. It is not
0463  * absolutely necessary to commit yet, but it feels like this should be better
0464  * then to keep doing GC. This function returns %1 if GC has to initiate commit
0465  * and %0 if not.
0466  */
0467 int ubifs_gc_should_commit(struct ubifs_info *c)
0468 {
0469     int ret = 0;
0470 
0471     spin_lock(&c->cs_lock);
0472     if (c->cmt_state == COMMIT_BACKGROUND) {
0473         dbg_cmt("commit required now");
0474         c->cmt_state = COMMIT_REQUIRED;
0475     } else
0476         dbg_cmt("commit not requested");
0477     if (c->cmt_state == COMMIT_REQUIRED)
0478         ret = 1;
0479     spin_unlock(&c->cs_lock);
0480     return ret;
0481 }
0482 
0483 /*
0484  * Everything below is related to debugging.
0485  */
0486 
0487 /**
0488  * struct idx_node - hold index nodes during index tree traversal.
0489  * @list: list
0490  * @iip: index in parent (slot number of this indexing node in the parent
0491  *       indexing node)
0492  * @upper_key: all keys in this indexing node have to be less or equivalent to
0493  *             this key
0494  * @idx: index node (8-byte aligned because all node structures must be 8-byte
0495  *       aligned)
0496  */
0497 struct idx_node {
0498     struct list_head list;
0499     int iip;
0500     union ubifs_key upper_key;
0501     struct ubifs_idx_node idx __aligned(8);
0502 };
0503 
0504 /**
0505  * dbg_old_index_check_init - get information for the next old index check.
0506  * @c: UBIFS file-system description object
0507  * @zroot: root of the index
0508  *
0509  * This function records information about the index that will be needed for the
0510  * next old index check i.e. 'dbg_check_old_index()'.
0511  *
0512  * This function returns %0 on success and a negative error code on failure.
0513  */
0514 int dbg_old_index_check_init(struct ubifs_info *c, struct ubifs_zbranch *zroot)
0515 {
0516     struct ubifs_idx_node *idx;
0517     int lnum, offs, len, err = 0;
0518     struct ubifs_debug_info *d = c->dbg;
0519 
0520     d->old_zroot = *zroot;
0521     lnum = d->old_zroot.lnum;
0522     offs = d->old_zroot.offs;
0523     len = d->old_zroot.len;
0524 
0525     idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
0526     if (!idx)
0527         return -ENOMEM;
0528 
0529     err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
0530     if (err)
0531         goto out;
0532 
0533     d->old_zroot_level = le16_to_cpu(idx->level);
0534     d->old_zroot_sqnum = le64_to_cpu(idx->ch.sqnum);
0535 out:
0536     kfree(idx);
0537     return err;
0538 }
0539 
0540 /**
0541  * dbg_check_old_index - check the old copy of the index.
0542  * @c: UBIFS file-system description object
0543  * @zroot: root of the new index
0544  *
0545  * In order to be able to recover from an unclean unmount, a complete copy of
0546  * the index must exist on flash. This is the "old" index. The commit process
0547  * must write the "new" index to flash without overwriting or destroying any
0548  * part of the old index. This function is run at commit end in order to check
0549  * that the old index does indeed exist completely intact.
0550  *
0551  * This function returns %0 on success and a negative error code on failure.
0552  */
0553 int dbg_check_old_index(struct ubifs_info *c, struct ubifs_zbranch *zroot)
0554 {
0555     int lnum, offs, len, err = 0, last_level, child_cnt;
0556     int first = 1, iip;
0557     struct ubifs_debug_info *d = c->dbg;
0558     union ubifs_key lower_key, upper_key, l_key, u_key;
0559     unsigned long long last_sqnum;
0560     struct ubifs_idx_node *idx;
0561     struct list_head list;
0562     struct idx_node *i;
0563     size_t sz;
0564 
0565     if (!dbg_is_chk_index(c))
0566         return 0;
0567 
0568     INIT_LIST_HEAD(&list);
0569 
0570     sz = sizeof(struct idx_node) + ubifs_idx_node_sz(c, c->fanout) -
0571          UBIFS_IDX_NODE_SZ;
0572 
0573     /* Start at the old zroot */
0574     lnum = d->old_zroot.lnum;
0575     offs = d->old_zroot.offs;
0576     len = d->old_zroot.len;
0577     iip = 0;
0578 
0579     /*
0580      * Traverse the index tree preorder depth-first i.e. do a node and then
0581      * its subtrees from left to right.
0582      */
0583     while (1) {
0584         struct ubifs_branch *br;
0585 
0586         /* Get the next index node */
0587         i = kmalloc(sz, GFP_NOFS);
0588         if (!i) {
0589             err = -ENOMEM;
0590             goto out_free;
0591         }
0592         i->iip = iip;
0593         /* Keep the index nodes on our path in a linked list */
0594         list_add_tail(&i->list, &list);
0595         /* Read the index node */
0596         idx = &i->idx;
0597         err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
0598         if (err)
0599             goto out_free;
0600         /* Validate index node */
0601         child_cnt = le16_to_cpu(idx->child_cnt);
0602         if (child_cnt < 1 || child_cnt > c->fanout) {
0603             err = 1;
0604             goto out_dump;
0605         }
0606         if (first) {
0607             first = 0;
0608             /* Check root level and sqnum */
0609             if (le16_to_cpu(idx->level) != d->old_zroot_level) {
0610                 err = 2;
0611                 goto out_dump;
0612             }
0613             if (le64_to_cpu(idx->ch.sqnum) != d->old_zroot_sqnum) {
0614                 err = 3;
0615                 goto out_dump;
0616             }
0617             /* Set last values as though root had a parent */
0618             last_level = le16_to_cpu(idx->level) + 1;
0619             last_sqnum = le64_to_cpu(idx->ch.sqnum) + 1;
0620             key_read(c, ubifs_idx_key(c, idx), &lower_key);
0621             highest_ino_key(c, &upper_key, INUM_WATERMARK);
0622         }
0623         key_copy(c, &upper_key, &i->upper_key);
0624         if (le16_to_cpu(idx->level) != last_level - 1) {
0625             err = 3;
0626             goto out_dump;
0627         }
0628         /*
0629          * The index is always written bottom up hence a child's sqnum
0630          * is always less than the parents.
0631          */
0632         if (le64_to_cpu(idx->ch.sqnum) >= last_sqnum) {
0633             err = 4;
0634             goto out_dump;
0635         }
0636         /* Check key range */
0637         key_read(c, ubifs_idx_key(c, idx), &l_key);
0638         br = ubifs_idx_branch(c, idx, child_cnt - 1);
0639         key_read(c, &br->key, &u_key);
0640         if (keys_cmp(c, &lower_key, &l_key) > 0) {
0641             err = 5;
0642             goto out_dump;
0643         }
0644         if (keys_cmp(c, &upper_key, &u_key) < 0) {
0645             err = 6;
0646             goto out_dump;
0647         }
0648         if (keys_cmp(c, &upper_key, &u_key) == 0)
0649             if (!is_hash_key(c, &u_key)) {
0650                 err = 7;
0651                 goto out_dump;
0652             }
0653         /* Go to next index node */
0654         if (le16_to_cpu(idx->level) == 0) {
0655             /* At the bottom, so go up until can go right */
0656             while (1) {
0657                 /* Drop the bottom of the list */
0658                 list_del(&i->list);
0659                 kfree(i);
0660                 /* No more list means we are done */
0661                 if (list_empty(&list))
0662                     goto out;
0663                 /* Look at the new bottom */
0664                 i = list_entry(list.prev, struct idx_node,
0665                            list);
0666                 idx = &i->idx;
0667                 /* Can we go right */
0668                 if (iip + 1 < le16_to_cpu(idx->child_cnt)) {
0669                     iip = iip + 1;
0670                     break;
0671                 } else
0672                     /* Nope, so go up again */
0673                     iip = i->iip;
0674             }
0675         } else
0676             /* Go down left */
0677             iip = 0;
0678         /*
0679          * We have the parent in 'idx' and now we set up for reading the
0680          * child pointed to by slot 'iip'.
0681          */
0682         last_level = le16_to_cpu(idx->level);
0683         last_sqnum = le64_to_cpu(idx->ch.sqnum);
0684         br = ubifs_idx_branch(c, idx, iip);
0685         lnum = le32_to_cpu(br->lnum);
0686         offs = le32_to_cpu(br->offs);
0687         len = le32_to_cpu(br->len);
0688         key_read(c, &br->key, &lower_key);
0689         if (iip + 1 < le16_to_cpu(idx->child_cnt)) {
0690             br = ubifs_idx_branch(c, idx, iip + 1);
0691             key_read(c, &br->key, &upper_key);
0692         } else
0693             key_copy(c, &i->upper_key, &upper_key);
0694     }
0695 out:
0696     err = dbg_old_index_check_init(c, zroot);
0697     if (err)
0698         goto out_free;
0699 
0700     return 0;
0701 
0702 out_dump:
0703     ubifs_err(c, "dumping index node (iip=%d)", i->iip);
0704     ubifs_dump_node(c, idx, ubifs_idx_node_sz(c, c->fanout));
0705     list_del(&i->list);
0706     kfree(i);
0707     if (!list_empty(&list)) {
0708         i = list_entry(list.prev, struct idx_node, list);
0709         ubifs_err(c, "dumping parent index node");
0710         ubifs_dump_node(c, &i->idx, ubifs_idx_node_sz(c, c->fanout));
0711     }
0712 out_free:
0713     while (!list_empty(&list)) {
0714         i = list_entry(list.next, struct idx_node, list);
0715         list_del(&i->list);
0716         kfree(i);
0717     }
0718     ubifs_err(c, "failed, error %d", err);
0719     if (err > 0)
0720         err = -EINVAL;
0721     return err;
0722 }