build.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright (C) 2001-2003 Red Hat, Inc.
  5. *
  6. * Created by David Woodhouse <dwmw2@infradead.org>
  7. *
  8. * For licensing information, see the file 'LICENCE' in this directory.
  9. *
  10. * $Id: build.c,v 1.1.1.1 2007/06/12 07:27:13 eyryu Exp $
  11. *
  12. */
  13. #include <linux/kernel.h>
  14. #include <linux/sched.h>
  15. #include <linux/slab.h>
  16. #include <linux/vmalloc.h>
  17. #include <linux/mtd/mtd.h>
  18. #include "nodelist.h"
  19. static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *,
  20. struct jffs2_inode_cache *, struct jffs2_full_dirent **);
  21. static inline struct jffs2_inode_cache *
  22. first_inode_chain(int *i, struct jffs2_sb_info *c)
  23. {
  24. for (; *i < INOCACHE_HASHSIZE; (*i)++) {
  25. if (c->inocache_list[*i])
  26. return c->inocache_list[*i];
  27. }
  28. return NULL;
  29. }
  30. static inline struct jffs2_inode_cache *
  31. next_inode(int *i, struct jffs2_inode_cache *ic, struct jffs2_sb_info *c)
  32. {
  33. /* More in this chain? */
  34. if (ic->next)
  35. return ic->next;
  36. (*i)++;
  37. return first_inode_chain(i, c);
  38. }
  39. #define for_each_inode(i, c, ic) \
  40. for (i = 0, ic = first_inode_chain(&i, (c)); \
  41. ic; \
  42. ic = next_inode(&i, ic, (c)))
  43. static void jffs2_build_inode_pass1(struct jffs2_sb_info *c,
  44. struct jffs2_inode_cache *ic)
  45. {
  46. struct jffs2_full_dirent *fd;
  47. dbg_fsbuild("building directory inode #%u\n", ic->ino);
  48. /* For each child, increase nlink */
  49. for(fd = ic->scan_dents; fd; fd = fd->next) {
  50. struct jffs2_inode_cache *child_ic;
  51. if (!fd->ino)
  52. continue;
  53. /* we can get high latency here with huge directories */
  54. child_ic = jffs2_get_ino_cache(c, fd->ino);
  55. if (!child_ic) {
  56. dbg_fsbuild("child \"%s\" (ino #%u) of dir ino #%u doesn't exist!\n",
  57. fd->name, fd->ino, ic->ino);
  58. jffs2_mark_node_obsolete(c, fd->raw);
  59. continue;
  60. }
  61. if (child_ic->nlink++ && fd->type == DT_DIR) {
  62. JFFS2_ERROR("child dir \"%s\" (ino #%u) of dir ino #%u appears to be a hard link\n",
  63. fd->name, fd->ino, ic->ino);
  64. /* TODO: What do we do about it? */
  65. }
  66. dbg_fsbuild("increased nlink for child \"%s\" (ino #%u)\n", fd->name, fd->ino);
  67. /* Can't free scan_dents so far. We might need them in pass 2 */
  68. }
  69. }
  70. /* Scan plan:
  71. - Scan physical nodes. Build map of inodes/dirents. Allocate inocaches as we go
  72. - Scan directory tree from top down, setting nlink in inocaches
  73. - Scan inocaches for inodes with nlink==0
  74. */
  75. static int jffs2_build_filesystem(struct jffs2_sb_info *c)
  76. {
  77. int ret;
  78. int i;
  79. struct jffs2_inode_cache *ic;
  80. struct jffs2_full_dirent *fd;
  81. struct jffs2_full_dirent *dead_fds = NULL;
  82. dbg_fsbuild("build FS data structures\n");
  83. /* First, scan the medium and build all the inode caches with
  84. lists of physical nodes */
  85. c->flags |= JFFS2_SB_FLAG_SCANNING;
  86. ret = jffs2_scan_medium(c);
  87. c->flags &= ~JFFS2_SB_FLAG_SCANNING;
  88. if (ret)
  89. goto exit;
  90. dbg_fsbuild("scanned flash completely\n");
  91. jffs2_dbg_dump_block_lists_nolock(c);
  92. dbg_fsbuild("pass 1 starting\n");
  93. c->flags |= JFFS2_SB_FLAG_BUILDING;
  94. /* Now scan the directory tree, increasing nlink according to every dirent found. */
  95. for_each_inode(i, c, ic) {
  96. if (ic->scan_dents) {
  97. jffs2_build_inode_pass1(c, ic);
  98. cond_resched();
  99. }
  100. }
  101. dbg_fsbuild("pass 1 complete\n");
  102. /* Next, scan for inodes with nlink == 0 and remove them. If
  103. they were directories, then decrement the nlink of their
  104. children too, and repeat the scan. As that's going to be
  105. a fairly uncommon occurrence, it's not so evil to do it this
  106. way. Recursion bad. */
  107. dbg_fsbuild("pass 2 starting\n");
  108. for_each_inode(i, c, ic) {
  109. if (ic->nlink)
  110. continue;
  111. jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
  112. cond_resched();
  113. }
  114. dbg_fsbuild("pass 2a starting\n");
  115. while (dead_fds) {
  116. fd = dead_fds;
  117. dead_fds = fd->next;
  118. ic = jffs2_get_ino_cache(c, fd->ino);
  119. if (ic)
  120. jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
  121. jffs2_free_full_dirent(fd);
  122. }
  123. dbg_fsbuild("pass 2a complete\n");
  124. dbg_fsbuild("freeing temporary data structures\n");
  125. /* Finally, we can scan again and free the dirent structs */
  126. for_each_inode(i, c, ic) {
  127. while(ic->scan_dents) {
  128. fd = ic->scan_dents;
  129. ic->scan_dents = fd->next;
  130. jffs2_free_full_dirent(fd);
  131. }
  132. ic->scan_dents = NULL;
  133. cond_resched();
  134. }
  135. jffs2_build_xattr_subsystem(c);
  136. c->flags &= ~JFFS2_SB_FLAG_BUILDING;
  137. dbg_fsbuild("FS build complete\n");
  138. /* Rotate the lists by some number to ensure wear levelling */
  139. jffs2_rotate_lists(c);
  140. ret = 0;
  141. exit:
  142. if (ret) {
  143. for_each_inode(i, c, ic) {
  144. while(ic->scan_dents) {
  145. fd = ic->scan_dents;
  146. ic->scan_dents = fd->next;
  147. jffs2_free_full_dirent(fd);
  148. }
  149. }
  150. jffs2_clear_xattr_subsystem(c);
  151. }
  152. return ret;
  153. }
  154. static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *c,
  155. struct jffs2_inode_cache *ic,
  156. struct jffs2_full_dirent **dead_fds)
  157. {
  158. struct jffs2_raw_node_ref *raw;
  159. struct jffs2_full_dirent *fd;
  160. dbg_fsbuild("removing ino #%u with nlink == zero.\n", ic->ino);
  161. raw = ic->nodes;
  162. while (raw != (void *)ic) {
  163. struct jffs2_raw_node_ref *next = raw->next_in_ino;
  164. dbg_fsbuild("obsoleting node at 0x%08x\n", ref_offset(raw));
  165. jffs2_mark_node_obsolete(c, raw);
  166. raw = next;
  167. }
  168. if (ic->scan_dents) {
  169. int whinged = 0;
  170. dbg_fsbuild("inode #%u was a directory which may have children...\n", ic->ino);
  171. while(ic->scan_dents) {
  172. struct jffs2_inode_cache *child_ic;
  173. fd = ic->scan_dents;
  174. ic->scan_dents = fd->next;
  175. if (!fd->ino) {
  176. /* It's a deletion dirent. Ignore it */
  177. dbg_fsbuild("child \"%s\" is a deletion dirent, skipping...\n", fd->name);
  178. jffs2_free_full_dirent(fd);
  179. continue;
  180. }
  181. if (!whinged)
  182. whinged = 1;
  183. dbg_fsbuild("removing child \"%s\", ino #%u\n", fd->name, fd->ino);
  184. child_ic = jffs2_get_ino_cache(c, fd->ino);
  185. if (!child_ic) {
  186. dbg_fsbuild("cannot remove child \"%s\", ino #%u, because it doesn't exist\n",
  187. fd->name, fd->ino);
  188. jffs2_free_full_dirent(fd);
  189. continue;
  190. }
  191. /* Reduce nlink of the child. If it's now zero, stick it on the
  192. dead_fds list to be cleaned up later. Else just free the fd */
  193. child_ic->nlink--;
  194. if (!child_ic->nlink) {
  195. dbg_fsbuild("inode #%u (\"%s\") has now got zero nlink, adding to dead_fds list.\n",
  196. fd->ino, fd->name);
  197. fd->next = *dead_fds;
  198. *dead_fds = fd;
  199. } else {
  200. dbg_fsbuild("inode #%u (\"%s\") has now got nlink %d. Ignoring.\n",
  201. fd->ino, fd->name, child_ic->nlink);
  202. jffs2_free_full_dirent(fd);
  203. }
  204. }
  205. }
  206. /*
  207. We don't delete the inocache from the hash list and free it yet.
  208. The erase code will do that, when all the nodes are completely gone.
  209. */
  210. }
  211. static void jffs2_calc_trigger_levels(struct jffs2_sb_info *c)
  212. {
  213. uint32_t size;
  214. /* Deletion should almost _always_ be allowed. We're fairly
  215. buggered once we stop allowing people to delete stuff
  216. because there's not enough free space... */
  217. c->resv_blocks_deletion = 2;
  218. /* Be conservative about how much space we need before we allow writes.
  219. On top of that which is required for deletia, require an extra 2%
  220. of the medium to be available, for overhead caused by nodes being
  221. split across blocks, etc. */
  222. size = c->flash_size / 50; /* 2% of flash size */
  223. size += c->nr_blocks * 100; /* And 100 bytes per eraseblock */
  224. size += c->sector_size - 1; /* ... and round up */
  225. c->resv_blocks_write = c->resv_blocks_deletion + (size / c->sector_size);
  226. /* When do we let the GC thread run in the background */
  227. c->resv_blocks_gctrigger = c->resv_blocks_write + 1;
  228. /* When do we allow garbage collection to merge nodes to make
  229. long-term progress at the expense of short-term space exhaustion? */
  230. c->resv_blocks_gcmerge = c->resv_blocks_deletion + 1;
  231. /* When do we allow garbage collection to eat from bad blocks rather
  232. than actually making progress? */
  233. c->resv_blocks_gcbad = 0;//c->resv_blocks_deletion + 2;
  234. /* If there's less than this amount of dirty space, don't bother
  235. trying to GC to make more space. It'll be a fruitless task */
  236. c->nospc_dirty_size = c->sector_size + (c->flash_size / 100);
  237. dbg_fsbuild("JFFS2 trigger levels (size %d KiB, block size %d KiB, %d blocks)\n",
  238. c->flash_size / 1024, c->sector_size / 1024, c->nr_blocks);
  239. dbg_fsbuild("Blocks required to allow deletion: %d (%d KiB)\n",
  240. c->resv_blocks_deletion, c->resv_blocks_deletion*c->sector_size/1024);
  241. dbg_fsbuild("Blocks required to allow writes: %d (%d KiB)\n",
  242. c->resv_blocks_write, c->resv_blocks_write*c->sector_size/1024);
  243. dbg_fsbuild("Blocks required to quiesce GC thread: %d (%d KiB)\n",
  244. c->resv_blocks_gctrigger, c->resv_blocks_gctrigger*c->sector_size/1024);
  245. dbg_fsbuild("Blocks required to allow GC merges: %d (%d KiB)\n",
  246. c->resv_blocks_gcmerge, c->resv_blocks_gcmerge*c->sector_size/1024);
  247. dbg_fsbuild("Blocks required to GC bad blocks: %d (%d KiB)\n",
  248. c->resv_blocks_gcbad, c->resv_blocks_gcbad*c->sector_size/1024);
  249. dbg_fsbuild("Amount of dirty space required to GC: %d bytes\n",
  250. c->nospc_dirty_size);
  251. }
  252. int jffs2_do_mount_fs(struct jffs2_sb_info *c)
  253. {
  254. int ret;
  255. int i;
  256. int size;
  257. c->free_size = c->flash_size;
  258. c->nr_blocks = c->flash_size / c->sector_size;
  259. size = sizeof(struct jffs2_eraseblock) * c->nr_blocks;
  260. #ifndef __ECOS
  261. if (jffs2_blocks_use_vmalloc(c))
  262. c->blocks = vmalloc(size);
  263. else
  264. #endif
  265. c->blocks = kmalloc(size, GFP_KERNEL);
  266. if (!c->blocks)
  267. return -ENOMEM;
  268. memset(c->blocks, 0, size);
  269. for (i=0; i<c->nr_blocks; i++) {
  270. INIT_LIST_HEAD(&c->blocks[i].list);
  271. c->blocks[i].offset = i * c->sector_size;
  272. c->blocks[i].free_size = c->sector_size;
  273. }
  274. INIT_LIST_HEAD(&c->clean_list);
  275. INIT_LIST_HEAD(&c->very_dirty_list);
  276. INIT_LIST_HEAD(&c->dirty_list);
  277. INIT_LIST_HEAD(&c->erasable_list);
  278. INIT_LIST_HEAD(&c->erasing_list);
  279. INIT_LIST_HEAD(&c->erase_pending_list);
  280. INIT_LIST_HEAD(&c->erasable_pending_wbuf_list);
  281. INIT_LIST_HEAD(&c->erase_complete_list);
  282. INIT_LIST_HEAD(&c->free_list);
  283. INIT_LIST_HEAD(&c->bad_list);
  284. INIT_LIST_HEAD(&c->bad_used_list);
  285. c->highest_ino = 1;
  286. c->summary = NULL;
  287. ret = jffs2_sum_init(c);
  288. if (ret)
  289. goto out_free;
  290. if (jffs2_build_filesystem(c)) {
  291. dbg_fsbuild("build_fs failed\n");
  292. jffs2_free_ino_caches(c);
  293. jffs2_free_raw_node_refs(c);
  294. ret = -EIO;
  295. goto out_free;
  296. }
  297. jffs2_calc_trigger_levels(c);
  298. return 0;
  299. out_free:
  300. #ifndef __ECOS
  301. if (jffs2_blocks_use_vmalloc(c))
  302. vfree(c->blocks);
  303. else
  304. #endif
  305. kfree(c->blocks);
  306. return ret;
  307. }