orphan.c 24 KB

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