orphan.c 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316
  1. /*
  2. * This file is part of UBIFS.
  3. *
  4. * Copyright (C) 2006-2008 Nokia Corporation.
  5. *
  6. * This program is free software; you can redistribute it and/or modify it
  7. * under the terms of the GNU General Public License version 2 as published by
  8. * the Free Software Foundation.
  9. *
  10. * This program is distributed in the hope that it will be useful, but WITHOUT
  11. * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12. * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
  13. * more details.
  14. *
  15. * You should have received a copy of the GNU General Public License along with
  16. * this program; if not, write to the Free Software Foundation, Inc., 51
  17. * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18. *
  19. * Author: Adrian Hunter
  20. */
  21. #include "ubifs.h"
  22. /*
  23. * An orphan is an inode number whose inode node has been committed to the index
  24. * with a link count of zero. That happens when an open file is deleted
  25. * (unlinked) and then a commit is run. In the normal course of events the inode
  26. * would be deleted when the file is closed. However in the case of an unclean
  27. * unmount, orphans need to be accounted for. After an unclean unmount, the
  28. * orphans' inodes must be deleted which means either scanning the entire index
  29. * looking for them, or keeping a list on flash somewhere. This unit implements
  30. * the latter approach.
  31. *
  32. * The orphan area is a fixed number of LEBs situated between the LPT area and
  33. * the main area. The number of orphan area LEBs is specified when the file
  34. * system is created. The minimum number is 1. The size of the orphan area
  35. * should be so that it can hold the maximum number of orphans that are expected
  36. * to ever exist at one time.
  37. *
  38. * The number of orphans that can fit in a LEB is:
  39. *
  40. * (c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64)
  41. *
  42. * For example: a 15872 byte LEB can fit 1980 orphans so 1 LEB may be enough.
  43. *
  44. * Orphans are accumulated in a rb-tree. When an inode's link count drops to
  45. * zero, the inode number is added to the rb-tree. It is removed from the tree
  46. * when the inode is deleted. Any new orphans that are in the orphan tree when
  47. * the commit is run, are written to the orphan area in 1 or more orphan nodes.
  48. * If the orphan area is full, it is consolidated to make space. There is
  49. * always enough space because validation prevents the user from creating more
  50. * than the maximum number of orphans allowed.
  51. */
  52. /**
  53. * tot_avail_orphs - calculate total space.
  54. * @c: UBIFS file-system description object
  55. *
  56. * This function returns the number of orphans that can be written in half
  57. * the total space. That leaves half the space for adding new orphans.
  58. */
  59. static int tot_avail_orphs(struct ubifs_info *c)
  60. {
  61. int avail_lebs, avail;
  62. avail_lebs = c->orph_lebs;
  63. avail = avail_lebs *
  64. ((c->leb_size - UBIFS_ORPH_NODE_SZ) / sizeof(__le64));
  65. return avail / 2;
  66. }
  67. /**
  68. * ubifs_clear_orphans - erase all LEBs used for orphans.
  69. * @c: UBIFS file-system description object
  70. *
  71. * If recovery is not required, then the orphans from the previous session
  72. * are not needed. This function locates the LEBs used to record
  73. * orphans, and un-maps them.
  74. */
  75. int ubifs_clear_orphans(struct ubifs_info *c)
  76. {
  77. int lnum, err;
  78. for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
  79. err = ubifs_leb_unmap(c, lnum);
  80. if (err)
  81. return err;
  82. }
  83. c->ohead_lnum = c->orph_first;
  84. c->ohead_offs = 0;
  85. return 0;
  86. }
  87. /**
  88. * insert_dead_orphan - insert an orphan.
  89. * @c: UBIFS file-system description object
  90. * @inum: orphan inode number
  91. *
  92. * This function is a helper to the 'do_kill_orphans()' function. The orphan
  93. * must be kept until the next commit, so it is added to the rb-tree and the
  94. * deletion list.
  95. */
  96. static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
  97. {
  98. struct ubifs_orphan *orphan, *o;
  99. struct rb_node **p, *parent = NULL;
  100. orphan = kzalloc(sizeof(struct ubifs_orphan), GFP_KERNEL);
  101. if (!orphan)
  102. return -ENOMEM;
  103. orphan->inum = inum;
  104. p = &c->orph_tree.rb_node;
  105. while (*p) {
  106. parent = *p;
  107. o = rb_entry(parent, struct ubifs_orphan, rb);
  108. if (inum < o->inum)
  109. p = &(*p)->rb_left;
  110. else if (inum > o->inum)
  111. p = &(*p)->rb_right;
  112. else {
  113. /* Already added - no problem */
  114. kfree(orphan);
  115. return 0;
  116. }
  117. }
  118. c->tot_orphans += 1;
  119. rb_link_node(&orphan->rb, parent, p);
  120. rb_insert_color(&orphan->rb, &c->orph_tree);
  121. list_add_tail(&orphan->list, &c->orph_list);
  122. orphan->dnext = c->orph_dnext;
  123. c->orph_dnext = orphan;
  124. dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
  125. c->new_orphans, c->tot_orphans);
  126. return 0;
  127. }
  128. /**
  129. * do_kill_orphans - remove orphan inodes from the index.
  130. * @c: UBIFS file-system description object
  131. * @sleb: scanned LEB
  132. * @last_cmt_no: cmt_no of last orphan node read is passed and returned here
  133. * @outofdate: whether the LEB is out of date is returned here
  134. * @last_flagged: whether the end orphan node is encountered
  135. *
  136. * This function is a helper to the 'kill_orphans()' function. It goes through
  137. * every orphan node in a LEB and for every inode number recorded, removes
  138. * all keys for that inode from the TNC.
  139. */
  140. static int do_kill_orphans(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
  141. unsigned long long *last_cmt_no, int *outofdate,
  142. int *last_flagged)
  143. {
  144. struct ubifs_scan_node *snod;
  145. struct ubifs_orph_node *orph;
  146. unsigned long long cmt_no;
  147. ino_t inum;
  148. int i, n, err, first = 1;
  149. list_for_each_entry(snod, &sleb->nodes, list) {
  150. if (snod->type != UBIFS_ORPH_NODE) {
  151. ubifs_err("invalid node type %d in orphan area at "
  152. "%d:%d", snod->type, sleb->lnum, snod->offs);
  153. dbg_dump_node(c, snod->node);
  154. return -EINVAL;
  155. }
  156. orph = snod->node;
  157. /* Check commit number */
  158. cmt_no = le64_to_cpu(orph->cmt_no) & LLONG_MAX;
  159. /*
  160. * The commit number on the master node may be less, because
  161. * of a failed commit. If there are several failed commits in a
  162. * row, the commit number written on orphan nodes will continue
  163. * to increase (because the commit number is adjusted here) even
  164. * though the commit number on the master node stays the same
  165. * because the master node has not been re-written.
  166. */
  167. if (cmt_no > c->cmt_no)
  168. c->cmt_no = cmt_no;
  169. if (cmt_no < *last_cmt_no && *last_flagged) {
  170. /*
  171. * The last orphan node had a higher commit number and
  172. * was flagged as the last written for that commit
  173. * number. That makes this orphan node, out of date.
  174. */
  175. if (!first) {
  176. ubifs_err("out of order commit number %llu in "
  177. "orphan node at %d:%d",
  178. cmt_no, sleb->lnum, snod->offs);
  179. dbg_dump_node(c, snod->node);
  180. return -EINVAL;
  181. }
  182. dbg_rcvry("out of date LEB %d", sleb->lnum);
  183. *outofdate = 1;
  184. return 0;
  185. }
  186. if (first)
  187. first = 0;
  188. n = (le32_to_cpu(orph->ch.len) - UBIFS_ORPH_NODE_SZ) >> 3;
  189. for (i = 0; i < n; i++) {
  190. inum = le64_to_cpu(orph->inos[i]);
  191. dbg_rcvry("deleting orphaned inode %lu",
  192. (unsigned long)inum);
  193. err = ubifs_tnc_remove_ino(c, inum);
  194. if (err)
  195. return err;
  196. err = insert_dead_orphan(c, inum);
  197. if (err)
  198. return err;
  199. }
  200. *last_cmt_no = cmt_no;
  201. if (le64_to_cpu(orph->cmt_no) & (1ULL << 63)) {
  202. dbg_rcvry("last orph node for commit %llu at %d:%d",
  203. cmt_no, sleb->lnum, snod->offs);
  204. *last_flagged = 1;
  205. } else
  206. *last_flagged = 0;
  207. }
  208. return 0;
  209. }
  210. /**
  211. * kill_orphans - remove all orphan inodes from the index.
  212. * @c: UBIFS file-system description object
  213. *
  214. * If recovery is required, then orphan inodes recorded during the previous
  215. * session (which ended with an unclean unmount) must be deleted from the index.
  216. * This is done by updating the TNC, but since the index is not updated until
  217. * the next commit, the LEBs where the orphan information is recorded are not
  218. * erased until the next commit.
  219. */
  220. static int kill_orphans(struct ubifs_info *c)
  221. {
  222. unsigned long long last_cmt_no = 0;
  223. int lnum, err = 0, outofdate = 0, last_flagged = 0;
  224. c->ohead_lnum = c->orph_first;
  225. c->ohead_offs = 0;
  226. /* Check no-orphans flag and skip this if no orphans */
  227. if (c->no_orphs) {
  228. dbg_rcvry("no orphans");
  229. return 0;
  230. }
  231. /*
  232. * Orph nodes always start at c->orph_first and are written to each
  233. * successive LEB in turn. Generally unused LEBs will have been unmapped
  234. * but may contain out of date orphan nodes if the unmap didn't go
  235. * through. In addition, the last orphan node written for each commit is
  236. * marked (top bit of orph->cmt_no is set to 1). It is possible that
  237. * there are orphan nodes from the next commit (i.e. the commit did not
  238. * complete successfully). In that case, no orphans will have been lost
  239. * due to the way that orphans are written, and any orphans added will
  240. * be valid orphans anyway and so can be deleted.
  241. */
  242. for (lnum = c->orph_first; lnum <= c->orph_last; lnum++) {
  243. struct ubifs_scan_leb *sleb;
  244. dbg_rcvry("LEB %d", lnum);
  245. sleb = ubifs_scan(c, lnum, 0, c->sbuf);
  246. if (IS_ERR(sleb)) {
  247. sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, 0);
  248. if (IS_ERR(sleb)) {
  249. err = PTR_ERR(sleb);
  250. break;
  251. }
  252. }
  253. err = do_kill_orphans(c, sleb, &last_cmt_no, &outofdate,
  254. &last_flagged);
  255. if (err || outofdate) {
  256. ubifs_scan_destroy(sleb);
  257. break;
  258. }
  259. if (sleb->endpt) {
  260. c->ohead_lnum = lnum;
  261. c->ohead_offs = sleb->endpt;
  262. }
  263. ubifs_scan_destroy(sleb);
  264. }
  265. return err;
  266. }
  267. /**
  268. * ubifs_mount_orphans - delete orphan inodes and erase LEBs that recorded them.
  269. * @c: UBIFS file-system description object
  270. * @unclean: indicates recovery from unclean unmount
  271. * @read_only: indicates read only mount
  272. *
  273. * This function is called when mounting to erase orphans from the previous
  274. * session. If UBIFS was not unmounted cleanly, then the inodes recorded as
  275. * orphans are deleted.
  276. */
  277. int ubifs_mount_orphans(struct ubifs_info *c, int unclean, int read_only)
  278. {
  279. int err = 0;
  280. c->max_orphans = tot_avail_orphs(c);
  281. if (!read_only) {
  282. c->orph_buf = vmalloc(c->leb_size);
  283. if (!c->orph_buf)
  284. return -ENOMEM;
  285. }
  286. if (unclean)
  287. err = kill_orphans(c);
  288. else if (!read_only)
  289. err = ubifs_clear_orphans(c);
  290. return err;
  291. }