orphan.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * This file is part of UBIFS.
  4. *
  5. * Copyright (C) 2006-2008 Nokia Corporation.
  6. *
  7. * Author: Adrian Hunter
  8. */
  9. #include <log.h>
  10. #include <dm/devres.h>
  11. #include <linux/err.h>
  12. #include "ubifs.h"
  13. /*
  14. * An orphan is an inode number whose inode node has been committed to the index
  15. * with a link count of zero. That happens when an open file is deleted
  16. * (unlinked) and then a commit is run. In the normal course of events the inode
  17. * would be deleted when the file is closed. However in the case of an unclean
  18. * unmount, orphans need to be accounted for. After an unclean unmount, the
  19. * orphans' inodes must be deleted which means either scanning the entire index
  20. * looking for them, or keeping a list on flash somewhere. This unit implements
  21. * the latter approach.
  22. *
  23. * The orphan area is a fixed number of LEBs situated between the LPT area and
  24. * the main area. The number of orphan area LEBs is specified when the file
  25. * system is created. The minimum number is 1. The size of the orphan area
  26. * should be so that it can hold the maximum number of orphans that are expected
  27. * to ever exist at one time.
  28. *
  29. * The number of orphans that can fit in a LEB is:
  30. *
  31. * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
  32. *
  33. * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough.
  34. *
  35. * Orphans are accumulated in a rb-tree. When an inode's link count drops to
  36. * zero, the inode number is added to the rb-tree. It is removed from the tree
  37. * when the inode is deleted. Any new orphans that are in the orphan tree when
  38. * the commit is run, are written to the orphan area in 1 or more orphan nodes.
  39. * If the orphan area is full, it is consolidated to make space. There is
  40. * always enough space because validation prevents the user from creating more
  41. * than the maximum number of orphans allowed.
  42. */
  43. static int dbg_check_orphans(struct ubifs_info *c);
  44. /**
  45. * ubifs_add_orphan - add an orphan.
  46. * @c: UBIFS file-system description object
  47. * @inum: orphan inode number
  48. *
  49. * Add an orphan. This function is called when an inodes link count drops to
  50. * zero.
  51. */
  52. int ubifs_add_orphan(struct ubifs_info *c, ino_t inum)
  53. {
  54. struct ubifs_orphan *orphan, *o;
  55. struct rb_node **p, *parent = NULL;
  56. orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_NOFS);
  57. if (!orphan)
  58. return -ENOMEM;
  59. orphan->inum = inum;
  60. orphan->new = 1;
  61. spin_lock(&c->orphan_lock);
  62. if (c->tot_orphans >= c->max_orphans) {
  63. spin_unlock(&c->orphan_lock);
  64. kfree(orphan);
  65. return -ENFILE;
  66. }
  67. p = &c->orph_tree.rb_node;
  68. while (*p) {
  69. parent = *p;
  70. o = rb_entry(parent, struct ubifs_orphan, rb);
  71. if (inum < o->inum)
  72. p = &(*p)->rb_left;
  73. else if (inum > o->inum)
  74. p = &(*p)->rb_right;
  75. else {
  76. ubifs_err(c, "orphaned twice");
  77. spin_unlock(&c->orphan_lock);
  78. kfree(orphan);
  79. return 0;
  80. }
  81. }
  82. c->tot_orphans += 1;
  83. c->new_orphans += 1;
  84. rb_link_node(&orphan->rb, parent, p);
  85. rb_insert_color(&orphan->rb, &c->orph_tree);
  86. list_add_tail(&orphan->list, &c->orph_list);
  87. list_add_tail(&orphan->new_list, &c->orph_new);
  88. spin_unlock(&c->orphan_lock);
  89. dbg_gen("ino %lu", (unsigned long)inum);
  90. return 0;
  91. }
  92. /**
  93. * ubifs_delete_orphan - delete an orphan.
  94. * @c: UBIFS file-system description object
  95. * @inum: orphan inode number
  96. *
  97. * Delete an orphan. This function is called when an inode is deleted.
  98. */
  99. void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
  100. {
  101. struct ubifs_orphan *o;
  102. struct rb_node *p;
  103. spin_lock(&c->orphan_lock);
  104. p = c->orph_tree.rb_node;
  105. while (p) {
  106. o = rb_entry(p, struct ubifs_orphan, rb);
  107. if (inum < o->inum)
  108. p = p->rb_left;
  109. else if (inum > o->inum)
  110. p = p->rb_right;
  111. else {
  112. if (o->del) {
  113. spin_unlock(&c->orphan_lock);
  114. dbg_gen("deleted twice ino %lu",
  115. (unsigned long)inum);
  116. return;
  117. }
  118. if (o->cmt) {
  119. o->del = 1;
  120. o->dnext = c->orph_dnext;
  121. c->orph_dnext = o;
  122. spin_unlock(&c->orphan_lock);
  123. dbg_gen("delete later ino %lu",
  124. (unsigned long)inum);
  125. return;
  126. }
  127. rb_erase(p, &c->orph_tree);
  128. list_del(&o->list);
  129. c->tot_orphans -= 1;
  130. if (o->new) {
  131. list_del(&o->new_list);
  132. c->new_orphans -= 1;
  133. }
  134. spin_unlock(&c->orphan_lock);
  135. kfree(o);
  136. dbg_gen("inum %lu", (unsigned long)inum);
  137. return;
  138. }
  139. }
  140. spin_unlock(&c->orphan_lock);
  141. ubifs_err(c, "missing orphan ino %lu", (unsigned long)inum);
  142. dump_stack();
  143. }
  144. /**
  145. * ubifs_orphan_start_commit - start commit of orphans.
  146. * @c: UBIFS file-system description object
  147. *
  148. * Start commit of orphans.
  149. */
  150. int ubifs_orphan_start_commit(struct ubifs_info *c)
  151. {
  152. struct ubifs_orphan *orphan, **last;
  153. spin_lock(&c->orphan_lock);
  154. last = &c->orph_cnext;
  155. list_for_each_entry(orphan, &c->orph_new, new_list) {
  156. ubifs_assert(orphan->new);
  157. ubifs_assert(!orphan->cmt);
  158. orphan->new = 0;
  159. orphan->cmt = 1;
  160. *last = orphan;
  161. last = &orphan->cnext;
  162. }
  163. *last = NULL;
  164. c->cmt_orphans = c->new_orphans;
  165. c->new_orphans = 0;
  166. dbg_cmt("%d orphans to commit", c->cmt_orphans);
  167. INIT_LIST_HEAD(&c->orph_new);
  168. if (c->tot_orphans == 0)
  169. c->no_orphs = 1;
  170. else
  171. c->no_orphs = 0;
  172. spin_unlock(&c->orphan_lock);
  173. return 0;
  174. }
  175. /**
  176. * avail_orphs - calculate available space.
  177. * @c: UBIFS file-system description object
  178. *
  179. * This function returns the number of orphans that can be written in the
  180. * available space.
  181. */
  182. static int avail_orphs(struct ubifs_info *c)
  183. {
  184. int avail_lebs, avail, gap;
  185. avail_lebs = c->orph_lebs - (c->ohead_lnum - c->orph_first) - 1;
  186. avail = avail_lebs *
  187. ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
  188. gap = c->leb_size - c->ohead_offs;
  189. if (gap >= UBIFS_ORPH_NODE_SZ + sizeof(__le64))
  190. avail += (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
  191. return avail;
  192. }
  193. /**
  194. * tot_avail_orphs - calculate total space.
  195. * @c: UBIFS file-system description object
  196. *
  197. * This function returns the number of orphans that can be written in half
  198. * the total space. That leaves half the space for adding new orphans.
  199. */
  200. static int tot_avail_orphs(struct ubifs_info *c)
  201. {
  202. int avail_lebs, avail;
  203. avail_lebs = c->orph_lebs;
  204. avail = avail_lebs *
  205. ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
  206. return avail / 2;
  207. }
  208. /**
  209. * do_write_orph_node - write a node to the orphan head.
  210. * @c: UBIFS file-system description object
  211. * @len: length of node
  212. * @atomic: write atomically
  213. *
  214. * This function writes a node to the orphan head from the orphan buffer. If
  215. * %atomic is not zero, then the write is done atomically. On success, %0 is
  216. * returned, otherwise a negative error code is returned.
  217. */
  218. static int do_write_orph_node(struct ubifs_info *c, int len, int atomic)
  219. {
  220. int err = 0;
  221. if (atomic) {
  222. ubifs_assert(c->ohead_offs == 0);
  223. ubifs_prepare_node(c, c->orph_buf, len, 1);
  224. len = ALIGN(len, c->min_io_size);
  225. err = ubifs_leb_change(c, c->ohead_lnum, c->orph_buf, len);
  226. } else {
  227. if (c->ohead_offs == 0) {
  228. /* Ensure LEB has been unmapped */
  229. err = ubifs_leb_unmap(c, c->ohead_lnum);
  230. if (err)
  231. return err;
  232. }
  233. err = ubifs_write_node(c, c->orph_buf, len, c->ohead_lnum,
  234. c->ohead_offs);
  235. }
  236. return err;
  237. }
  238. /**
  239. * write_orph_node - write an orphan node.
  240. * @c: UBIFS file-system description object
  241. * @atomic: write atomically
  242. *
  243. * This function builds an orphan node from the cnext list and writes it to the
  244. * orphan head. On success, %0 is returned, otherwise a negative error code
  245. * is returned.
  246. */
  247. static int write_orph_node(struct ubifs_info *c, int atomic)
  248. {
  249. struct ubifs_orphan *orphan, *cnext;
  250. struct ubifs_orph_node *orph;
  251. int gap, err, len, cnt, i;
  252. ubifs_assert(c->cmt_orphans > 0);
  253. gap = c->leb_size - c->ohead_offs;
  254. if (gap < UBIFS_ORPH_NODE_SZ + sizeof(__le64)) {
  255. c->ohead_lnum += 1;
  256. c->ohead_offs = 0;
  257. gap = c->leb_size;
  258. if (c->ohead_lnum > c->orph_last) {
  259. /*
  260. * We limit the number of orphans so that this should
  261. * never happen.
  262. */
  263. ubifs_err(c, "out of space in orphan area");
  264. return -EINVAL;
  265. }
  266. }
  267. cnt = (gap - UBIFS_ORPH_NODE_SZ) / sizeof(__le64);
  268. if (cnt > c->cmt_orphans)
  269. cnt = c->cmt_orphans;
  270. len = UBIFS_ORPH_NODE_SZ + cnt * sizeof(__le64);
  271. ubifs_assert(c->orph_buf);
  272. orph = c->orph_buf;
  273. orph->ch.node_type = UBIFS_ORPH_NODE;
  274. spin_lock(&c->orphan_lock);
  275. cnext = c->orph_cnext;
  276. for (i = 0; i < cnt; i++) {
  277. orphan = cnext;
  278. ubifs_assert(orphan->cmt);
  279. orph->inos[i] = cpu_to_le64(orphan->inum);
  280. orphan->cmt = 0;
  281. cnext = orphan->cnext;
  282. orphan->cnext = NULL;
  283. }
  284. c->orph_cnext = cnext;
  285. c->cmt_orphans -= cnt;
  286. spin_unlock(&c->orphan_lock);
  287. if (c->cmt_orphans)
  288. orph->cmt_no = cpu_to_le64(c->cmt_no);
  289. else
  290. /* Mark the last node of the commit */
  291. orph->cmt_no = cpu_to_le64((c->cmt_no) | (1ULL << 63));
  292. ubifs_assert(c->ohead_offs + len <= c->leb_size);
  293. ubifs_assert(c->ohead_lnum >= c->orph_first);
  294. ubifs_assert(c->ohead_lnum <= c->orph_last);
  295. err = do_write_orph_node(c, len, atomic);
  296. c->ohead_offs += ALIGN(len, c->min_io_size);
  297. c->ohead_offs = ALIGN(c->ohead_offs, 8);
  298. return err;
  299. }
  300. /**
  301. * write_orph_nodes - write orphan nodes until there are no more to commit.
  302. * @c: UBIFS file-system description object
  303. * @atomic: write atomically
  304. *
  305. * This function writes orphan nodes for all the orphans to commit. On success,
  306. * %0 is returned, otherwise a negative error code is returned.
  307. */
  308. static int write_orph_nodes(struct ubifs_info *c, int atomic)
  309. {
  310. int err;
  311. while (c->cmt_orphans > 0) {
  312. err = write_orph_node(c, atomic);
  313. if (err)
  314. return err;
  315. }
  316. if (atomic) {
  317. int lnum;
  318. /* Unmap any unused LEBs after consolidation */
  319. for (lnum = c->ohead_lnum + 1; lnum <= c->orph_last; lnum++) {
  320. err = ubifs_leb_unmap(c, lnum);
  321. if (err)
  322. return err;
  323. }
  324. }
  325. return 0;
  326. }
  327. /**
  328. * consolidate - consolidate the orphan area.
  329. * @c: UBIFS file-system description object
  330. *
  331. * This function enables consolidation by putting all the orphans into the list
  332. * to commit. The list is in the order that the orphans were added, and the
  333. * LEBs are written atomically in order, so at no time can orphans be lost by
  334. * an unclean unmount.
  335. *
  336. * This function returns %0 on success and a negative error code on failure.
  337. */
  338. static int consolidate(struct ubifs_info *c)
  339. {
  340. int tot_avail = tot_avail_orphs(c), err = 0;
  341. spin_lock(&c->orphan_lock);
  342. dbg_cmt("there is space for %d orphans and there are %d",
  343. tot_avail, c->tot_orphans);
  344. if (c->tot_orphans - c->new_orphans <= tot_avail) {
  345. struct ubifs_orphan *orphan, **last;
  346. int cnt = 0;
  347. /* Change the cnext list to include all non-new orphans */
  348. last = &c->orph_cnext;
  349. list_for_each_entry(orphan, &c->orph_list, list) {
  350. if (orphan->new)
  351. continue;
  352. orphan->cmt = 1;
  353. *last = orphan;
  354. last = &orphan->cnext;
  355. cnt += 1;
  356. }
  357. *last = NULL;
  358. ubifs_assert(cnt == c->tot_orphans - c->new_orphans);
  359. c->cmt_orphans = cnt;
  360. c->ohead_lnum = c->orph_first;
  361. c->ohead_offs = 0;
  362. } else {
  363. /*
  364. * We limit the number of orphans so that this should
  365. * never happen.
  366. */
  367. ubifs_err(c, "out of space in orphan area");
  368. err = -EINVAL;
  369. }
  370. spin_unlock(&c->orphan_lock);
  371. return err;
  372. }
  373. /**
  374. * commit_orphans - commit orphans.
  375. * @c: UBIFS file-system description object
  376. *
  377. * This function commits orphans to flash. On success, %0 is returned,
  378. * otherwise a negative error code is returned.
  379. */
  380. static int commit_orphans(struct ubifs_info *c)
  381. {
  382. int avail, atomic = 0, err;
  383. ubifs_assert(c->cmt_orphans > 0);
  384. avail = avail_orphs(c);
  385. if (avail < c->cmt_orphans) {
  386. /* Not enough space to write new orphans, so consolidate */
  387. err = consolidate(c);
  388. if (err)
  389. return err;
  390. atomic = 1;
  391. }
  392. err = write_orph_nodes(c, atomic);
  393. return err;
  394. }
  395. /**
  396. * erase_deleted - erase the orphans marked for deletion.
  397. * @c: UBIFS file-system description object
  398. *
  399. * During commit, the orphans being committed cannot be deleted, so they are
  400. * marked for deletion and deleted by this function. Also, the recovery
  401. * adds killed orphans to the deletion list, and therefore they are deleted
  402. * here too.
  403. */
  404. static void erase_deleted(struct ubifs_info *c)
  405. {
  406. struct ubifs_orphan *orphan, *dnext;
  407. spin_lock(&c->orphan_lock);
  408. dnext = c->orph_dnext;
  409. while (dnext) {
  410. orphan = dnext;
  411. dnext = orphan->dnext;
  412. ubifs_assert(!orphan->new);
  413. ubifs_assert(orphan->del);
  414. rb_erase(&orphan->rb, &c->orph_tree);
  415. list_del(&orphan->list);
  416. c->tot_orphans -= 1;
  417. dbg_gen("deleting orphan ino %lu", (unsigned long)orphan->inum);
  418. kfree(orphan);
  419. }
  420. c->orph_dnext = NULL;
  421. spin_unlock(&c->orphan_lock);
  422. }
  423. /**
  424. * ubifs_orphan_end_commit - end commit of orphans.
  425. * @c: UBIFS file-system description object
  426. *
  427. * End commit of orphans.
  428. */
  429. int ubifs_orphan_end_commit(struct ubifs_info *c)
  430. {
  431. int err;
  432. if (c->cmt_orphans != 0) {
  433. err = commit_orphans(c);
  434. if (err)
  435. return err;
  436. }
  437. erase_deleted(c);
  438. err = dbg_check_orphans(c);
  439. return err;
  440. }
  441. /**
  442. * ubifs_clear_orphans - erase all LEBs used for orphans.
  443. * @c: UBIFS file-system description object
  444. *
  445. * If recovery is not required, then the orphans from the previous session
  446. * are not needed. This function locates the LEBs used to record
  447. * orphans, and un-maps them.
  448. */
  449. int ubifs_clear_orphans(struct ubifs_info *c)
  450. {
  451. int lnum, err;
  452. for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
  453. err = ubifs_leb_unmap(c, lnum);
  454. if (err)
  455. return err;
  456. }
  457. c->ohead_lnum = c->orph_first;
  458. c->ohead_offs = 0;
  459. return 0;
  460. }
  461. /**
  462. * insert_dead_orphan - insert an orphan.
  463. * @c: UBIFS file-system description object
  464. * @inum: orphan inode number
  465. *
  466. * This function is a helper to the 'do_kill_orphans()' function. The orphan
  467. * must be kept until the next commit, so it is added to the rb-tree and the
  468. * deletion list.
  469. */
  470. static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
  471. {
  472. struct ubifs_orphan *orphan, *o;
  473. struct rb_node **p, *parent = NULL;
  474. orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL);
  475. if (!orphan)
  476. return -ENOMEM;
  477. orphan->inum = inum;
  478. p = &c->orph_tree.rb_node;
  479. while (*p) {
  480. parent = *p;
  481. o = rb_entry(parent, struct ubifs_orphan, rb);
  482. if (inum < o->inum)
  483. p = &(*p)->rb_left;
  484. else if (inum > o->inum)
  485. p = &(*p)->rb_right;
  486. else {
  487. /* Already added - no problem */
  488. kfree(orphan);
  489. return 0;
  490. }
  491. }
  492. c->tot_orphans += 1;
  493. rb_link_node(&orphan->rb, parent, p);
  494. rb_insert_color(&orphan->rb, &c->orph_tree);
  495. list_add_tail(&orphan->list, &c->orph_list);
  496. orphan->del = 1;
  497. orphan->dnext = c->orph_dnext;
  498. c->orph_dnext = orphan;
  499. dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
  500. c->new_orphans, c->tot_orphans);
  501. return 0;
  502. }
  503. /**
  504. * do_kill_orphans - remove orphan inodes from the index.
  505. * @c: UBIFS file-system description object
  506. * @sleb: scanned LEB
  507. * @last_cmt_no: cmt_no of last orphan node read is passed and returned here
  508. * @outofdate: whether the LEB is out of date is returned here
  509. * @last_flagged: whether the end orphan node is encountered
  510. *
  511. * This function is a helper to the 'kill_orphans()' function. It goes through
  512. * every orphan node in a LEB and for every inode number recorded, removes
  513. * all keys for that inode from the TNC.
  514. */
  515. static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  516. unsigned long long *last_cmt_no, int *outofdate,
  517. int *last_flagged)
  518. {
  519. struct ubifs_scan_node *snod;
  520. struct ubifs_orph_node *orph;
  521. unsigned long long cmt_no;
  522. ino_t inum;
  523. int i, n, err, first = 1;
  524. list_for_each_entry(snod, &sleb->nodes, list) {
  525. if (snod->type != UBIFS_ORPH_NODE) {
  526. ubifs_err(c, "invalid node type %d in orphan area at %d:%d",
  527. snod->type, sleb->lnum, snod->offs);
  528. ubifs_dump_node(c, snod->node);
  529. return -EINVAL;
  530. }
  531. orph = snod->node;
  532. /* Check commit number */
  533. cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX;
  534. /*
  535. * The commit number on the master node may be less, because
  536. * of a failed commit. If there are several failed commits in a
  537. * row, the commit number written on orphan nodes will continue
  538. * to increase (because the commit number is adjusted here) even
  539. * though the commit number on the master node stays the same
  540. * because the master node has not been re-written.
  541. */
  542. if (cmt_no > c->cmt_no)
  543. c->cmt_no = cmt_no;
  544. if (cmt_no < *last_cmt_no && *last_flagged) {
  545. /*
  546. * The last orphan node had a higher commit number and
  547. * was flagged as the last written for that commit
  548. * number. That makes this orphan node, out of date.
  549. */
  550. if (!first) {
  551. ubifs_err(c, "out of order commit number %llu in orphan node at %d:%d",
  552. cmt_no, sleb->lnum, snod->offs);
  553. ubifs_dump_node(c, snod->node);
  554. return -EINVAL;
  555. }
  556. dbg_rcvry("out of date LEB %d", sleb->lnum);
  557. *outofdate = 1;
  558. return 0;
  559. }
  560. if (first)
  561. first = 0;
  562. n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
  563. for (i = 0; i < n; i++) {
  564. inum = le64_to_cpu(orph->inos[i]);
  565. dbg_rcvry("deleting orphaned inode %lu",
  566. (unsigned long)inum);
  567. err = ubifs_tnc_remove_ino(c, inum);
  568. if (err)
  569. return err;
  570. err = insert_dead_orphan(c, inum);
  571. if (err)
  572. return err;
  573. }
  574. *last_cmt_no = cmt_no;
  575. if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) {
  576. dbg_rcvry("last orph node for commit %llu at %d:%d",
  577. cmt_no, sleb->lnum, snod->offs);
  578. *last_flagged = 1;
  579. } else
  580. *last_flagged = 0;
  581. }
  582. return 0;
  583. }
  584. /**
  585. * kill_orphans - remove all orphan inodes from the index.
  586. * @c: UBIFS file-system description object
  587. *
  588. * If recovery is required, then orphan inodes recorded during the previous
  589. * session (which ended with an unclean unmount) must be deleted from the index.
  590. * This is done by updating the TNC, but since the index is not updated until
  591. * the next commit, the LEBs where the orphan information is recorded are not
  592. * erased until the next commit.
  593. */
  594. static int kill_orphans(struct ubifs_info *c)
  595. {
  596. unsigned long long last_cmt_no = 0;
  597. int lnum, err = 0, outofdate = 0, last_flagged = 0;
  598. c->ohead_lnum = c->orph_first;
  599. c->ohead_offs = 0;
  600. /* Check no-orphans flag and skip this if no orphans */
  601. if (c->no_orphs) {
  602. dbg_rcvry("no orphans");
  603. return 0;
  604. }
  605. /*
  606. * Orph nodes always start at c->orph_first and are written to each
  607. * successive LEB in turn. Generally unused LEBs will have been unmapped
  608. * but may contain out of date orphan nodes if the unmap didn't go
  609. * through. In addition, the last orphan node written for each commit is
  610. * marked (top bit of orph->cmt_no is set to 1). It is possible that
  611. * there are orphan nodes from the next commit (i.e. the commit did not
  612. * complete successfully). In that case, no orphans will have been lost
  613. * due to the way that orphans are written, and any orphans added will
  614. * be valid orphans anyway and so can be deleted.
  615. */
  616. for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
  617. struct ubifs_scan_leb *sleb;
  618. dbg_rcvry("LEB %d", lnum);
  619. sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1);
  620. if (IS_ERR(sleb)) {
  621. if (PTR_ERR(sleb) == -EUCLEAN)
  622. sleb = ubifs_recover_leb(c, lnum, 0,
  623. c->sbuf, -1);
  624. if (IS_ERR(sleb)) {
  625. err = PTR_ERR(sleb);
  626. break;
  627. }
  628. }
  629. err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate,
  630. &last_flagged);
  631. if (err || outofdate) {
  632. ubifs_scan_destroy(sleb);
  633. break;
  634. }
  635. if (sleb->endpt) {
  636. c->ohead_lnum = lnum;
  637. c->ohead_offs = sleb->endpt;
  638. }
  639. ubifs_scan_destroy(sleb);
  640. }
  641. return err;
  642. }
  643. /**
  644. * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them.
  645. * @c: UBIFS file-system description object
  646. * @unclean: indicates recovery from unclean unmount
  647. * @read_only: indicates read only mount
  648. *
  649. * This function is called when mounting to erase orphans from the previous
  650. * session. If UBIFS was not unmounted cleanly, then the inodes recorded as
  651. * orphans are deleted.
  652. */
  653. int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only)
  654. {
  655. int err = 0;
  656. c->max_orphans = tot_avail_orphs(c);
  657. if (!read_only) {
  658. c->orph_buf = vmalloc(c->leb_size);
  659. if (!c->orph_buf)
  660. return -ENOMEM;
  661. }
  662. if (unclean)
  663. err = kill_orphans(c);
  664. else if (!read_only)
  665. err = ubifs_clear_orphans(c);
  666. return err;
  667. }
  668. /*
  669. * Everything below is related to debugging.
  670. */
  671. struct check_orphan {
  672. struct rb_node rb;
  673. ino_t inum;
  674. };
  675. struct check_info {
  676. unsigned long last_ino;
  677. unsigned long tot_inos;
  678. unsigned long missing;
  679. unsigned long long leaf_cnt;
  680. struct ubifs_ino_node *node;
  681. struct rb_root root;
  682. };
  683. static int dbg_find_orphan(struct ubifs_info *c, ino_t inum)
  684. {
  685. struct ubifs_orphan *o;
  686. struct rb_node *p;
  687. spin_lock(&c->orphan_lock);
  688. p = c->orph_tree.rb_node;
  689. while (p) {
  690. o = rb_entry(p, struct ubifs_orphan, rb);
  691. if (inum < o->inum)
  692. p = p->rb_left;
  693. else if (inum > o->inum)
  694. p = p->rb_right;
  695. else {
  696. spin_unlock(&c->orphan_lock);
  697. return 1;
  698. }
  699. }
  700. spin_unlock(&c->orphan_lock);
  701. return 0;
  702. }
  703. static int dbg_ins_check_orphan(struct rb_root *root, ino_t inum)
  704. {
  705. struct check_orphan *orphan, *o;
  706. struct rb_node **p, *parent = NULL;
  707. orphan = kzalloc(sizeof(struct check_orphan), GFP_NOFS);
  708. if (!orphan)
  709. return -ENOMEM;
  710. orphan->inum = inum;
  711. p = &root->rb_node;
  712. while (*p) {
  713. parent = *p;
  714. o = rb_entry(parent, struct check_orphan, rb);
  715. if (inum < o->inum)
  716. p = &(*p)->rb_left;
  717. else if (inum > o->inum)
  718. p = &(*p)->rb_right;
  719. else {
  720. kfree(orphan);
  721. return 0;
  722. }
  723. }
  724. rb_link_node(&orphan->rb, parent, p);
  725. rb_insert_color(&orphan->rb, root);
  726. return 0;
  727. }
  728. static int dbg_find_check_orphan(struct rb_root *root, ino_t inum)
  729. {
  730. struct check_orphan *o;
  731. struct rb_node *p;
  732. p = root->rb_node;
  733. while (p) {
  734. o = rb_entry(p, struct check_orphan, rb);
  735. if (inum < o->inum)
  736. p = p->rb_left;
  737. else if (inum > o->inum)
  738. p = p->rb_right;
  739. else
  740. return 1;
  741. }
  742. return 0;
  743. }
  744. static void dbg_free_check_tree(struct rb_root *root)
  745. {
  746. struct check_orphan *o, *n;
  747. rbtree_postorder_for_each_entry_safe(o, n, root, rb)
  748. kfree(o);
  749. }
  750. static int dbg_orphan_check(struct ubifs_info *c, struct ubifs_zbranch *zbr,
  751. void *priv)
  752. {
  753. struct check_info *ci = priv;
  754. ino_t inum;
  755. int err;
  756. inum = key_inum(c, &zbr->key);
  757. if (inum != ci->last_ino) {
  758. /* Lowest node type is the inode node, so it comes first */
  759. if (key_type(c, &zbr->key) != UBIFS_INO_KEY)
  760. ubifs_err(c, "found orphan node ino %lu, type %d",
  761. (unsigned long)inum, key_type(c, &zbr->key));
  762. ci->last_ino = inum;
  763. ci->tot_inos += 1;
  764. err = ubifs_tnc_read_node(c, zbr, ci->node);
  765. if (err) {
  766. ubifs_err(c, "node read failed, error %d", err);
  767. return err;
  768. }
  769. if (ci->node->nlink == 0)
  770. /* Must be recorded as an orphan */
  771. if (!dbg_find_check_orphan(&ci->root, inum) &&
  772. !dbg_find_orphan(c, inum)) {
  773. ubifs_err(c, "missing orphan, ino %lu",
  774. (unsigned long)inum);
  775. ci->missing += 1;
  776. }
  777. }
  778. ci->leaf_cnt += 1;
  779. return 0;
  780. }
  781. static int dbg_read_orphans(struct check_info *ci, struct ubifs_scan_leb *sleb)
  782. {
  783. struct ubifs_scan_node *snod;
  784. struct ubifs_orph_node *orph;
  785. ino_t inum;
  786. int i, n, err;
  787. list_for_each_entry(snod, &sleb->nodes, list) {
  788. cond_resched();
  789. if (snod->type != UBIFS_ORPH_NODE)
  790. continue;
  791. orph = snod->node;
  792. n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
  793. for (i = 0; i < n; i++) {
  794. inum = le64_to_cpu(orph->inos[i]);
  795. err = dbg_ins_check_orphan(&ci->root, inum);
  796. if (err)
  797. return err;
  798. }
  799. }
  800. return 0;
  801. }
  802. static int dbg_scan_orphans(struct ubifs_info *c, struct check_info *ci)
  803. {
  804. int lnum, err = 0;
  805. void *buf;
  806. /* Check no-orphans flag and skip this if no orphans */
  807. if (c->no_orphs)
  808. return 0;
  809. buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
  810. if (!buf) {
  811. ubifs_err(c, "cannot allocate memory to check orphans");
  812. return 0;
  813. }
  814. for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
  815. struct ubifs_scan_leb *sleb;
  816. sleb = ubifs_scan(c, lnum, 0, buf, 0);
  817. if (IS_ERR(sleb)) {
  818. err = PTR_ERR(sleb);
  819. break;
  820. }
  821. err = dbg_read_orphans(ci, sleb);
  822. ubifs_scan_destroy(sleb);
  823. if (err)
  824. break;
  825. }
  826. vfree(buf);
  827. return err;
  828. }
  829. static int dbg_check_orphans(struct ubifs_info *c)
  830. {
  831. struct check_info ci;
  832. int err;
  833. if (!dbg_is_chk_orph(c))
  834. return 0;
  835. ci.last_ino = 0;
  836. ci.tot_inos = 0;
  837. ci.missing = 0;
  838. ci.leaf_cnt = 0;
  839. ci.root = RB_ROOT;
  840. ci.node = kmalloc(UBIFS_MAX_INO_NODE_SZ, GFP_NOFS);
  841. if (!ci.node) {
  842. ubifs_err(c, "out of memory");
  843. return -ENOMEM;
  844. }
  845. err = dbg_scan_orphans(c, &ci);
  846. if (err)
  847. goto out;
  848. err = dbg_walk_index(c, &dbg_orphan_check, NULL, &ci);
  849. if (err) {
  850. ubifs_err(c, "cannot scan TNC, error %d", err);
  851. goto out;
  852. }
  853. if (ci.missing) {
  854. ubifs_err(c, "%lu missing orphan(s)", ci.missing);
  855. err = -EINVAL;
  856. goto out;
  857. }
  858. dbg_cmt("last inode number is %lu", ci.last_ino);
  859. dbg_cmt("total number of inodes is %lu", ci.tot_inos);
  860. dbg_cmt("total number of leaf nodes is %llu", ci.leaf_cnt);
  861. out:
  862. dbg_free_check_tree(&ci.root);
  863. kfree(ci.node);
  864. return err;
  865. }