orphan.c 24 KB

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