commit.c 20 KB

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