commit.c 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736
  1. /*
  2. * This file is part of UBIFS.
  3. *
  4. * Copyright (C) 2006-2008 Nokia Corporation.
  5. *
  6. * This program is free software; you can redistribute it and/or modify it
  7. * under the terms of the GNU General Public License version 2 as published by
  8. * the Free Software Foundation.
  9. *
  10. * This program is distributed in the hope that it will be useful, but WITHOUT
  11. * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12. * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
  13. * more details.
  14. *
  15. * You should have received a copy of the GNU General Public License along with
  16. * this program; if not, write to the Free Software Foundation, Inc., 51
  17. * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18. *
  19. * Authors: Adrian Hunter
  20. * Artem Bityutskiy (Битюцкий Артём)
  21. */
  22. /*
  23. * This file implements functions that manage the running of the commit process.
  24. * Each affected module has its own functions to accomplish their part in the
  25. * commit and those functions are called here.
  26. *
  27. * The commit is the process whereby all updates to the index and LEB properties
  28. * are written out together and the journal becomes empty. This keeps the
  29. * file system consistent - at all times the state can be recreated by reading
  30. * the index and LEB properties and then replaying the journal.
  31. *
  32. * The commit is split into two parts named "commit start" and "commit end".
  33. * During commit start, the commit process has exclusive access to the journal
  34. * by holding the commit semaphore down for writing. As few I/O operations as
  35. * possible are performed during commit start, instead the nodes that are to be
  36. * written are merely identified. During commit end, the commit semaphore is no
  37. * longer held and the journal is again in operation, allowing users to continue
  38. * to use the file system while the bulk of the commit I/O is performed. The
  39. * purpose of this two-step approach is to prevent the commit from causing any
  40. * latency blips. Note that in any case, the commit does not prevent lookups
  41. * (as permitted by the TNC mutex), or access to VFS data structures e.g. page
  42. * cache.
  43. */
  44. #include <linux/freezer.h>
  45. #include <linux/kthread.h>
  46. #include <linux/slab.h>
  47. #include "ubifs.h"
  48. /*
  49. * nothing_to_commit - check if there is nothing to commit.
  50. * @c: UBIFS file-system description object
  51. *
  52. * This is a helper function which checks if there is anything to commit. It is
  53. * used as an optimization to avoid starting the commit if it is not really
  54. * necessary. Indeed, the commit operation always assumes flash I/O (e.g.,
  55. * writing the commit start node to the log), and it is better to avoid doing
  56. * this unnecessarily. E.g., 'ubifs_sync_fs()' runs the commit, but if there is
  57. * nothing to commit, it is more optimal to avoid any flash I/O.
  58. *
  59. * This function has to be called with @c->commit_sem locked for writing -
  60. * this function does not take LPT/TNC locks because the @c->commit_sem
  61. * guarantees that we have exclusive access to the TNC and LPT data structures.
  62. *
  63. * This function returns %1 if there is nothing to commit and %0 otherwise.
  64. */
  65. static int nothing_to_commit(struct ubifs_info *c)
  66. {
  67. /*
  68. * During mounting or remounting from R/O mode to R/W mode we may
  69. * commit for various recovery-related reasons.
  70. */
  71. if (c->mounting || c->remounting_rw)
  72. return 0;
  73. /*
  74. * If the root TNC node is dirty, we definitely have something to
  75. * commit.
  76. */
  77. if (c->zroot.znode && ubifs_zn_dirty(c->zroot.znode))
  78. return 0;
  79. /*
  80. * Even though the TNC is clean, the LPT tree may have dirty nodes. For
  81. * example, this may happen if the budgeting subsystem invoked GC to
  82. * make some free space, and the GC found an LEB with only dirty and
  83. * free space. In this case GC would just change the lprops of this
  84. * LEB (by turning all space into free space) and unmap it.
  85. */
  86. if (c->nroot && test_bit(DIRTY_CNODE, &c->nroot->flags))
  87. return 0;
  88. ubifs_assert(atomic_long_read(&c->dirty_zn_cnt) == 0);
  89. ubifs_assert(c->dirty_pn_cnt == 0);
  90. ubifs_assert(c->dirty_nn_cnt == 0);
  91. return 1;
  92. }
  93. /**
  94. * do_commit - commit the journal.
  95. * @c: UBIFS file-system description object
  96. *
  97. * This function implements UBIFS commit. It has to be called with commit lock
  98. * locked. Returns zero in case of success and a negative error code in case of
  99. * failure.
  100. */
  101. static int do_commit(struct ubifs_info *c)
  102. {
  103. int err, new_ltail_lnum, old_ltail_lnum, i;
  104. struct ubifs_zbranch zroot;
  105. struct ubifs_lp_stats lst;
  106. dbg_cmt("start");
  107. ubifs_assert(!c->ro_media && !c->ro_mount);
  108. if (c->ro_error) {
  109. err = -EROFS;
  110. goto out_up;
  111. }
  112. if (nothing_to_commit(c)) {
  113. up_write(&c->commit_sem);
  114. err = 0;
  115. goto out_cancel;
  116. }
  117. /* Sync all write buffers (necessary for recovery) */
  118. for (i = 0; i < c->jhead_cnt; i++) {
  119. err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
  120. if (err)
  121. goto out_up;
  122. }
  123. c->cmt_no += 1;
  124. err = ubifs_gc_start_commit(c);
  125. if (err)
  126. goto out_up;
  127. err = dbg_check_lprops(c);
  128. if (err)
  129. goto out_up;
  130. err = ubifs_log_start_commit(c, &new_ltail_lnum);
  131. if (err)
  132. goto out_up;
  133. err = ubifs_tnc_start_commit(c, &zroot);
  134. if (err)
  135. goto out_up;
  136. err = ubifs_lpt_start_commit(c);
  137. if (err)
  138. goto out_up;
  139. err = ubifs_orphan_start_commit(c);
  140. if (err)
  141. goto out_up;
  142. ubifs_get_lp_stats(c, &lst);
  143. up_write(&c->commit_sem);
  144. err = ubifs_tnc_end_commit(c);
  145. if (err)
  146. goto out;
  147. err = ubifs_lpt_end_commit(c);
  148. if (err)
  149. goto out;
  150. err = ubifs_orphan_end_commit(c);
  151. if (err)
  152. goto out;
  153. old_ltail_lnum = c->ltail_lnum;
  154. err = ubifs_log_end_commit(c, new_ltail_lnum);
  155. if (err)
  156. goto out;
  157. err = dbg_check_old_index(c, &zroot);
  158. if (err)
  159. goto out;
  160. c->mst_node->cmt_no = cpu_to_le64(c->cmt_no);
  161. c->mst_node->log_lnum = cpu_to_le32(new_ltail_lnum);
  162. c->mst_node->root_lnum = cpu_to_le32(zroot.lnum);
  163. c->mst_node->root_offs = cpu_to_le32(zroot.offs);
  164. c->mst_node->root_len = cpu_to_le32(zroot.len);
  165. c->mst_node->ihead_lnum = cpu_to_le32(c->ihead_lnum);
  166. c->mst_node->ihead_offs = cpu_to_le32(c->ihead_offs);
  167. c->mst_node->index_size = cpu_to_le64(c->bi.old_idx_sz);
  168. c->mst_node->lpt_lnum = cpu_to_le32(c->lpt_lnum);
  169. c->mst_node->lpt_offs = cpu_to_le32(c->lpt_offs);
  170. c->mst_node->nhead_lnum = cpu_to_le32(c->nhead_lnum);
  171. c->mst_node->nhead_offs = cpu_to_le32(c->nhead_offs);
  172. c->mst_node->ltab_lnum = cpu_to_le32(c->ltab_lnum);
  173. c->mst_node->ltab_offs = cpu_to_le32(c->ltab_offs);
  174. c->mst_node->lsave_lnum = cpu_to_le32(c->lsave_lnum);
  175. c->mst_node->lsave_offs = cpu_to_le32(c->lsave_offs);
  176. c->mst_node->lscan_lnum = cpu_to_le32(c->lscan_lnum);
  177. c->mst_node->empty_lebs = cpu_to_le32(lst.empty_lebs);
  178. c->mst_node->idx_lebs = cpu_to_le32(lst.idx_lebs);
  179. c->mst_node->total_free = cpu_to_le64(lst.total_free);
  180. c->mst_node->total_dirty = cpu_to_le64(lst.total_dirty);
  181. c->mst_node->total_used = cpu_to_le64(lst.total_used);
  182. c->mst_node->total_dead = cpu_to_le64(lst.total_dead);
  183. c->mst_node->total_dark = cpu_to_le64(lst.total_dark);
  184. if (c->no_orphs)
  185. c->mst_node->flags |= cpu_to_le32(UBIFS_MST_NO_ORPHS);
  186. else
  187. c->mst_node->flags &= ~cpu_to_le32(UBIFS_MST_NO_ORPHS);
  188. err = ubifs_write_master(c);
  189. if (err)
  190. goto out;
  191. err = ubifs_log_post_commit(c, old_ltail_lnum);
  192. if (err)
  193. goto out;
  194. err = ubifs_gc_end_commit(c);
  195. if (err)
  196. goto out;
  197. err = ubifs_lpt_post_commit(c);
  198. if (err)
  199. goto out;
  200. out_cancel:
  201. spin_lock(&c->cs_lock);
  202. c->cmt_state = COMMIT_RESTING;
  203. wake_up(&c->cmt_wq);
  204. dbg_cmt("commit end");
  205. spin_unlock(&c->cs_lock);
  206. return 0;
  207. out_up:
  208. up_write(&c->commit_sem);
  209. out:
  210. ubifs_err("commit failed, error %d", err);
  211. spin_lock(&c->cs_lock);
  212. c->cmt_state = COMMIT_BROKEN;
  213. wake_up(&c->cmt_wq);
  214. spin_unlock(&c->cs_lock);
  215. ubifs_ro_mode(c, err);
  216. return err;
  217. }
  218. /**
  219. * run_bg_commit - run background commit if it is needed.
  220. * @c: UBIFS file-system description object
  221. *
  222. * This function runs background commit if it is needed. Returns zero in case
  223. * of success and a negative error code in case of failure.
  224. */
  225. static int run_bg_commit(struct ubifs_info *c)
  226. {
  227. spin_lock(&c->cs_lock);
  228. /*
  229. * Run background commit only if background commit was requested or if
  230. * commit is required.
  231. */
  232. if (c->cmt_state != COMMIT_BACKGROUND &&
  233. c->cmt_state != COMMIT_REQUIRED)
  234. goto out;
  235. spin_unlock(&c->cs_lock);
  236. down_write(&c->commit_sem);
  237. spin_lock(&c->cs_lock);
  238. if (c->cmt_state == COMMIT_REQUIRED)
  239. c->cmt_state = COMMIT_RUNNING_REQUIRED;
  240. else if (c->cmt_state == COMMIT_BACKGROUND)
  241. c->cmt_state = COMMIT_RUNNING_BACKGROUND;
  242. else
  243. goto out_cmt_unlock;
  244. spin_unlock(&c->cs_lock);
  245. return do_commit(c);
  246. out_cmt_unlock:
  247. up_write(&c->commit_sem);
  248. out:
  249. spin_unlock(&c->cs_lock);
  250. return 0;
  251. }
  252. /**
  253. * ubifs_bg_thread - UBIFS background thread function.
  254. * @info: points to the file-system description object
  255. *
  256. * This function implements various file-system background activities:
  257. * o when a write-buffer timer expires it synchronizes the appropriate
  258. * write-buffer;
  259. * o when the journal is about to be full, it starts in-advance commit.
  260. *
  261. * Note, other stuff like background garbage collection may be added here in
  262. * future.
  263. */
  264. int ubifs_bg_thread(void *info)
  265. {
  266. int err;
  267. struct ubifs_info *c = info;
  268. ubifs_msg("background thread \"%s\" started, PID %d",
  269. c->bgt_name, current->pid);
  270. set_freezable();
  271. while (1) {
  272. if (kthread_should_stop())
  273. break;
  274. if (try_to_freeze())
  275. continue;
  276. set_current_state(TASK_INTERRUPTIBLE);
  277. /* Check if there is something to do */
  278. if (!c->need_bgt) {
  279. /*
  280. * Nothing prevents us from going sleep now and
  281. * be never woken up and block the task which
  282. * could wait in 'kthread_stop()' forever.
  283. */
  284. if (kthread_should_stop())
  285. break;
  286. schedule();
  287. continue;
  288. } else
  289. __set_current_state(TASK_RUNNING);
  290. c->need_bgt = 0;
  291. err = ubifs_bg_wbufs_sync(c);
  292. if (err)
  293. ubifs_ro_mode(c, err);
  294. run_bg_commit(c);
  295. cond_resched();
  296. }
  297. ubifs_msg("background thread \"%s\" stops", c->bgt_name);
  298. return 0;
  299. }
  300. /**
  301. * ubifs_commit_required - set commit state to "required".
  302. * @c: UBIFS file-system description object
  303. *
  304. * This function is called if a commit is required but cannot be done from the
  305. * calling function, so it is just flagged instead.
  306. */
  307. void ubifs_commit_required(struct ubifs_info *c)
  308. {
  309. spin_lock(&c->cs_lock);
  310. switch (c->cmt_state) {
  311. case COMMIT_RESTING:
  312. case COMMIT_BACKGROUND:
  313. dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
  314. dbg_cstate(COMMIT_REQUIRED));
  315. c->cmt_state = COMMIT_REQUIRED;
  316. break;
  317. case COMMIT_RUNNING_BACKGROUND:
  318. dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
  319. dbg_cstate(COMMIT_RUNNING_REQUIRED));
  320. c->cmt_state = COMMIT_RUNNING_REQUIRED;
  321. break;
  322. case COMMIT_REQUIRED:
  323. case COMMIT_RUNNING_REQUIRED:
  324. case COMMIT_BROKEN:
  325. break;
  326. }
  327. spin_unlock(&c->cs_lock);
  328. }
  329. /**
  330. * ubifs_request_bg_commit - notify the background thread to do a commit.
  331. * @c: UBIFS file-system description object
  332. *
  333. * This function is called if the journal is full enough to make a commit
  334. * worthwhile, so background thread is kicked to start it.
  335. */
  336. void ubifs_request_bg_commit(struct ubifs_info *c)
  337. {
  338. spin_lock(&c->cs_lock);
  339. if (c->cmt_state == COMMIT_RESTING) {
  340. dbg_cmt("old: %s, new: %s", dbg_cstate(c->cmt_state),
  341. dbg_cstate(COMMIT_BACKGROUND));
  342. c->cmt_state = COMMIT_BACKGROUND;
  343. spin_unlock(&c->cs_lock);
  344. ubifs_wake_up_bgt(c);
  345. } else
  346. spin_unlock(&c->cs_lock);
  347. }
  348. /**
  349. * wait_for_commit - wait for commit.
  350. * @c: UBIFS file-system description object
  351. *
  352. * This function sleeps until the commit operation is no longer running.
  353. */
  354. static int wait_for_commit(struct ubifs_info *c)
  355. {
  356. dbg_cmt("pid %d goes sleep", current->pid);
  357. /*
  358. * The following sleeps if the condition is false, and will be woken
  359. * when the commit ends. It is possible, although very unlikely, that we
  360. * will wake up and see the subsequent commit running, rather than the
  361. * one we were waiting for, and go back to sleep. However, we will be
  362. * woken again, so there is no danger of sleeping forever.
  363. */
  364. wait_event(c->cmt_wq, c->cmt_state != COMMIT_RUNNING_BACKGROUND &&
  365. c->cmt_state != COMMIT_RUNNING_REQUIRED);
  366. dbg_cmt("commit finished, pid %d woke up", current->pid);
  367. return 0;
  368. }
  369. /**
  370. * ubifs_run_commit - run or wait for commit.
  371. * @c: UBIFS file-system description object
  372. *
  373. * This function runs commit and returns zero in case of success and a negative
  374. * error code in case of failure.
  375. */
  376. int ubifs_run_commit(struct ubifs_info *c)
  377. {
  378. int err = 0;
  379. spin_lock(&c->cs_lock);
  380. if (c->cmt_state == COMMIT_BROKEN) {
  381. err = -EROFS;
  382. goto out;
  383. }
  384. if (c->cmt_state == COMMIT_RUNNING_BACKGROUND)
  385. /*
  386. * We set the commit state to 'running required' to indicate
  387. * that we want it to complete as quickly as possible.
  388. */
  389. c->cmt_state = COMMIT_RUNNING_REQUIRED;
  390. if (c->cmt_state == COMMIT_RUNNING_REQUIRED) {
  391. spin_unlock(&c->cs_lock);
  392. return wait_for_commit(c);
  393. }
  394. spin_unlock(&c->cs_lock);
  395. /* Ok, the commit is indeed needed */
  396. down_write(&c->commit_sem);
  397. spin_lock(&c->cs_lock);
  398. /*
  399. * Since we unlocked 'c->cs_lock', the state may have changed, so
  400. * re-check it.
  401. */
  402. if (c->cmt_state == COMMIT_BROKEN) {
  403. err = -EROFS;
  404. goto out_cmt_unlock;
  405. }
  406. if (c->cmt_state == COMMIT_RUNNING_BACKGROUND)
  407. c->cmt_state = COMMIT_RUNNING_REQUIRED;
  408. if (c->cmt_state == COMMIT_RUNNING_REQUIRED) {
  409. up_write(&c->commit_sem);
  410. spin_unlock(&c->cs_lock);
  411. return wait_for_commit(c);
  412. }
  413. c->cmt_state = COMMIT_RUNNING_REQUIRED;
  414. spin_unlock(&c->cs_lock);
  415. err = do_commit(c);
  416. return err;
  417. out_cmt_unlock:
  418. up_write(&c->commit_sem);
  419. out:
  420. spin_unlock(&c->cs_lock);
  421. return err;
  422. }
  423. /**
  424. * ubifs_gc_should_commit - determine if it is time for GC to run commit.
  425. * @c: UBIFS file-system description object
  426. *
  427. * This function is called by garbage collection to determine if commit should
  428. * be run. If commit state is @COMMIT_BACKGROUND, which means that the journal
  429. * is full enough to start commit, this function returns true. It is not
  430. * absolutely necessary to commit yet, but it feels like this should be better
  431. * then to keep doing GC. This function returns %1 if GC has to initiate commit
  432. * and %0 if not.
  433. */
  434. int ubifs_gc_should_commit(struct ubifs_info *c)
  435. {
  436. int ret = 0;
  437. spin_lock(&c->cs_lock);
  438. if (c->cmt_state == COMMIT_BACKGROUND) {
  439. dbg_cmt("commit required now");
  440. c->cmt_state = COMMIT_REQUIRED;
  441. } else
  442. dbg_cmt("commit not requested");
  443. if (c->cmt_state == COMMIT_REQUIRED)
  444. ret = 1;
  445. spin_unlock(&c->cs_lock);
  446. return ret;
  447. }
  448. /*
  449. * Everything below is related to debugging.
  450. */
  451. /**
  452. * struct idx_node - hold index nodes during index tree traversal.
  453. * @list: list
  454. * @iip: index in parent (slot number of this indexing node in the parent
  455. * indexing node)
  456. * @upper_key: all keys in this indexing node have to be less or equivalent to
  457. * this key
  458. * @idx: index node (8-byte aligned because all node structures must be 8-byte
  459. * aligned)
  460. */
  461. struct idx_node {
  462. struct list_head list;
  463. int iip;
  464. union ubifs_key upper_key;
  465. struct ubifs_idx_node idx __aligned(8);
  466. };
  467. /**
  468. * dbg_old_index_check_init - get information for the next old index check.
  469. * @c: UBIFS file-system description object
  470. * @zroot: root of the index
  471. *
  472. * This function records information about the index that will be needed for the
  473. * next old index check i.e. 'dbg_check_old_index()'.
  474. *
  475. * This function returns %0 on success and a negative error code on failure.
  476. */
  477. int dbg_old_index_check_init(struct ubifs_info *c, struct ubifs_zbranch *zroot)
  478. {
  479. struct ubifs_idx_node *idx;
  480. int lnum, offs, len, err = 0;
  481. struct ubifs_debug_info *d = c->dbg;
  482. d->old_zroot = *zroot;
  483. lnum = d->old_zroot.lnum;
  484. offs = d->old_zroot.offs;
  485. len = d->old_zroot.len;
  486. idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);
  487. if (!idx)
  488. return -ENOMEM;
  489. err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
  490. if (err)
  491. goto out;
  492. d->old_zroot_level = le16_to_cpu(idx->level);
  493. d->old_zroot_sqnum = le64_to_cpu(idx->ch.sqnum);
  494. out:
  495. kfree(idx);
  496. return err;
  497. }
  498. /**
  499. * dbg_check_old_index - check the old copy of the index.
  500. * @c: UBIFS file-system description object
  501. * @zroot: root of the new index
  502. *
  503. * In order to be able to recover from an unclean unmount, a complete copy of
  504. * the index must exist on flash. This is the "old" index. The commit process
  505. * must write the "new" index to flash without overwriting or destroying any
  506. * part of the old index. This function is run at commit end in order to check
  507. * that the old index does indeed exist completely intact.
  508. *
  509. * This function returns %0 on success and a negative error code on failure.
  510. */
  511. int dbg_check_old_index(struct ubifs_info *c, struct ubifs_zbranch *zroot)
  512. {
  513. int lnum, offs, len, err = 0, uninitialized_var(last_level), child_cnt;
  514. int first = 1, iip;
  515. struct ubifs_debug_info *d = c->dbg;
  516. union ubifs_key uninitialized_var(lower_key), upper_key, l_key, u_key;
  517. unsigned long long uninitialized_var(last_sqnum);
  518. struct ubifs_idx_node *idx;
  519. struct list_head list;
  520. struct idx_node *i;
  521. size_t sz;
  522. if (!dbg_is_chk_index(c))
  523. return 0;
  524. INIT_LIST_HEAD(&list);
  525. sz = sizeof(struct idx_node) + ubifs_idx_node_sz(c, c->fanout) -
  526. UBIFS_IDX_NODE_SZ;
  527. /* Start at the old zroot */
  528. lnum = d->old_zroot.lnum;
  529. offs = d->old_zroot.offs;
  530. len = d->old_zroot.len;
  531. iip = 0;
  532. /*
  533. * Traverse the index tree preorder depth-first i.e. do a node and then
  534. * its subtrees from left to right.
  535. */
  536. while (1) {
  537. struct ubifs_branch *br;
  538. /* Get the next index node */
  539. i = kmalloc(sz, GFP_NOFS);
  540. if (!i) {
  541. err = -ENOMEM;
  542. goto out_free;
  543. }
  544. i->iip = iip;
  545. /* Keep the index nodes on our path in a linked list */
  546. list_add_tail(&i->list, &list);
  547. /* Read the index node */
  548. idx = &i->idx;
  549. err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);
  550. if (err)
  551. goto out_free;
  552. /* Validate index node */
  553. child_cnt = le16_to_cpu(idx->child_cnt);
  554. if (child_cnt < 1 || child_cnt > c->fanout) {
  555. err = 1;
  556. goto out_dump;
  557. }
  558. if (first) {
  559. first = 0;
  560. /* Check root level and sqnum */
  561. if (le16_to_cpu(idx->level) != d->old_zroot_level) {
  562. err = 2;
  563. goto out_dump;
  564. }
  565. if (le64_to_cpu(idx->ch.sqnum) != d->old_zroot_sqnum) {
  566. err = 3;
  567. goto out_dump;
  568. }
  569. /* Set last values as though root had a parent */
  570. last_level = le16_to_cpu(idx->level) + 1;
  571. last_sqnum = le64_to_cpu(idx->ch.sqnum) + 1;
  572. key_read(c, ubifs_idx_key(c, idx), &lower_key);
  573. highest_ino_key(c, &upper_key, INUM_WATERMARK);
  574. }
  575. key_copy(c, &upper_key, &i->upper_key);
  576. if (le16_to_cpu(idx->level) != last_level - 1) {
  577. err = 3;
  578. goto out_dump;
  579. }
  580. /*
  581. * The index is always written bottom up hence a child's sqnum
  582. * is always less than the parents.
  583. */
  584. if (le64_to_cpu(idx->ch.sqnum) >= last_sqnum) {
  585. err = 4;
  586. goto out_dump;
  587. }
  588. /* Check key range */
  589. key_read(c, ubifs_idx_key(c, idx), &l_key);
  590. br = ubifs_idx_branch(c, idx, child_cnt - 1);
  591. key_read(c, &br->key, &u_key);
  592. if (keys_cmp(c, &lower_key, &l_key) > 0) {
  593. err = 5;
  594. goto out_dump;
  595. }
  596. if (keys_cmp(c, &upper_key, &u_key) < 0) {
  597. err = 6;
  598. goto out_dump;
  599. }
  600. if (keys_cmp(c, &upper_key, &u_key) == 0)
  601. if (!is_hash_key(c, &u_key)) {
  602. err = 7;
  603. goto out_dump;
  604. }
  605. /* Go to next index node */
  606. if (le16_to_cpu(idx->level) == 0) {
  607. /* At the bottom, so go up until can go right */
  608. while (1) {
  609. /* Drop the bottom of the list */
  610. list_del(&i->list);
  611. kfree(i);
  612. /* No more list means we are done */
  613. if (list_empty(&list))
  614. goto out;
  615. /* Look at the new bottom */
  616. i = list_entry(list.prev, struct idx_node,
  617. list);
  618. idx = &i->idx;
  619. /* Can we go right */
  620. if (iip + 1 < le16_to_cpu(idx->child_cnt)) {
  621. iip = iip + 1;
  622. break;
  623. } else
  624. /* Nope, so go up again */
  625. iip = i->iip;
  626. }
  627. } else
  628. /* Go down left */
  629. iip = 0;
  630. /*
  631. * We have the parent in 'idx' and now we set up for reading the
  632. * child pointed to by slot 'iip'.
  633. */
  634. last_level = le16_to_cpu(idx->level);
  635. last_sqnum = le64_to_cpu(idx->ch.sqnum);
  636. br = ubifs_idx_branch(c, idx, iip);
  637. lnum = le32_to_cpu(br->lnum);
  638. offs = le32_to_cpu(br->offs);
  639. len = le32_to_cpu(br->len);
  640. key_read(c, &br->key, &lower_key);
  641. if (iip + 1 < le16_to_cpu(idx->child_cnt)) {
  642. br = ubifs_idx_branch(c, idx, iip + 1);
  643. key_read(c, &br->key, &upper_key);
  644. } else
  645. key_copy(c, &i->upper_key, &upper_key);
  646. }
  647. out:
  648. err = dbg_old_index_check_init(c, zroot);
  649. if (err)
  650. goto out_free;
  651. return 0;
  652. out_dump:
  653. ubifs_err("dumping index node (iip=%d)", i->iip);
  654. ubifs_dump_node(c, idx);
  655. list_del(&i->list);
  656. kfree(i);
  657. if (!list_empty(&list)) {
  658. i = list_entry(list.prev, struct idx_node, list);
  659. ubifs_err("dumping parent index node");
  660. ubifs_dump_node(c, &i->idx);
  661. }
  662. out_free:
  663. while (!list_empty(&list)) {
  664. i = list_entry(list.next, struct idx_node, list);
  665. list_del(&i->list);
  666. kfree(i);
  667. }
  668. ubifs_err("failed, error %d", err);
  669. if (err > 0)
  670. err = -EINVAL;
  671. return err;
  672. }