2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright © 2001-2007 Red Hat, Inc.
6 * Created by David Woodhouse <dwmw2@infradead.org>
8 * For licensing information, see the file 'LICENCE' in this directory.
12 #include <linux/kernel.h>
13 #include <linux/sched.h>
14 #include <linux/slab.h>
15 #include <linux/vmalloc.h>
16 #include <linux/mtd/mtd.h>
19 static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info
*,
20 struct jffs2_inode_cache
*, struct jffs2_full_dirent
**);
22 static inline struct jffs2_inode_cache
*
23 first_inode_chain(int *i
, struct jffs2_sb_info
*c
)
25 for (; *i
< INOCACHE_HASHSIZE
; (*i
)++) {
26 if (c
->inocache_list
[*i
])
27 return c
->inocache_list
[*i
];
32 static inline struct jffs2_inode_cache
*
33 next_inode(int *i
, struct jffs2_inode_cache
*ic
, struct jffs2_sb_info
*c
)
35 /* More in this chain? */
39 return first_inode_chain(i
, c
);
42 #define for_each_inode(i, c, ic) \
43 for (i = 0, ic = first_inode_chain(&i, (c)); \
45 ic = next_inode(&i, ic, (c)))
48 static void jffs2_build_inode_pass1(struct jffs2_sb_info
*c
,
49 struct jffs2_inode_cache
*ic
)
51 struct jffs2_full_dirent
*fd
;
53 dbg_fsbuild("building directory inode #%u\n", ic
->ino
);
55 /* For each child, increase nlink */
56 for(fd
= ic
->scan_dents
; fd
; fd
= fd
->next
) {
57 struct jffs2_inode_cache
*child_ic
;
61 /* we can get high latency here with huge directories */
63 child_ic
= jffs2_get_ino_cache(c
, fd
->ino
);
65 dbg_fsbuild("child \"%s\" (ino #%u) of dir ino #%u doesn't exist!\n",
66 fd
->name
, fd
->ino
, ic
->ino
);
67 jffs2_mark_node_obsolete(c
, fd
->raw
);
71 if (child_ic
->nlink
++ && fd
->type
== DT_DIR
) {
72 JFFS2_ERROR("child dir \"%s\" (ino #%u) of dir ino #%u appears to be a hard link\n",
73 fd
->name
, fd
->ino
, ic
->ino
);
74 /* TODO: What do we do about it? */
76 dbg_fsbuild("increased nlink for child \"%s\" (ino #%u)\n", fd
->name
, fd
->ino
);
77 /* Can't free scan_dents so far. We might need them in pass 2 */
82 - Scan physical nodes. Build map of inodes/dirents. Allocate inocaches as we go
83 - Scan directory tree from top down, setting nlink in inocaches
84 - Scan inocaches for inodes with nlink==0
86 static int jffs2_build_filesystem(struct jffs2_sb_info
*c
)
90 struct jffs2_inode_cache
*ic
;
91 struct jffs2_full_dirent
*fd
;
92 struct jffs2_full_dirent
*dead_fds
= NULL
;
94 dbg_fsbuild("build FS data structures\n");
96 /* First, scan the medium and build all the inode caches with
97 lists of physical nodes */
99 c
->flags
|= JFFS2_SB_FLAG_SCANNING
;
100 ret
= jffs2_scan_medium(c
);
101 c
->flags
&= ~JFFS2_SB_FLAG_SCANNING
;
105 dbg_fsbuild("scanned flash completely\n");
106 jffs2_dbg_dump_block_lists_nolock(c
);
108 if (c
->flags
& (1 << 7)) {
109 printk("%s(): unlocking the mtd device... ", __func__
);
111 c
->mtd
->unlock(c
->mtd
, 0, c
->mtd
->size
);
114 printk("%s(): erasing all blocks after the end marker... ", __func__
);
115 jffs2_erase_pending_blocks(c
, -1);
119 dbg_fsbuild("pass 1 starting\n");
120 c
->flags
|= JFFS2_SB_FLAG_BUILDING
;
121 /* Now scan the directory tree, increasing nlink according to every dirent found. */
122 for_each_inode(i
, c
, ic
) {
123 if (ic
->scan_dents
) {
124 jffs2_build_inode_pass1(c
, ic
);
129 dbg_fsbuild("pass 1 complete\n");
131 /* Next, scan for inodes with nlink == 0 and remove them. If
132 they were directories, then decrement the nlink of their
133 children too, and repeat the scan. As that's going to be
134 a fairly uncommon occurrence, it's not so evil to do it this
135 way. Recursion bad. */
136 dbg_fsbuild("pass 2 starting\n");
138 for_each_inode(i
, c
, ic
) {
142 jffs2_build_remove_unlinked_inode(c
, ic
, &dead_fds
);
146 dbg_fsbuild("pass 2a starting\n");
152 ic
= jffs2_get_ino_cache(c
, fd
->ino
);
155 jffs2_build_remove_unlinked_inode(c
, ic
, &dead_fds
);
156 jffs2_free_full_dirent(fd
);
159 dbg_fsbuild("pass 2a complete\n");
160 dbg_fsbuild("freeing temporary data structures\n");
162 /* Finally, we can scan again and free the dirent structs */
163 for_each_inode(i
, c
, ic
) {
164 while(ic
->scan_dents
) {
166 ic
->scan_dents
= fd
->next
;
167 jffs2_free_full_dirent(fd
);
169 ic
->scan_dents
= NULL
;
172 jffs2_build_xattr_subsystem(c
);
173 c
->flags
&= ~JFFS2_SB_FLAG_BUILDING
;
175 dbg_fsbuild("FS build complete\n");
177 /* Rotate the lists by some number to ensure wear levelling */
178 jffs2_rotate_lists(c
);
184 for_each_inode(i
, c
, ic
) {
185 while(ic
->scan_dents
) {
187 ic
->scan_dents
= fd
->next
;
188 jffs2_free_full_dirent(fd
);
191 jffs2_clear_xattr_subsystem(c
);
197 static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info
*c
,
198 struct jffs2_inode_cache
*ic
,
199 struct jffs2_full_dirent
**dead_fds
)
201 struct jffs2_raw_node_ref
*raw
;
202 struct jffs2_full_dirent
*fd
;
204 dbg_fsbuild("removing ino #%u with nlink == zero.\n", ic
->ino
);
207 while (raw
!= (void *)ic
) {
208 struct jffs2_raw_node_ref
*next
= raw
->next_in_ino
;
209 dbg_fsbuild("obsoleting node at 0x%08x\n", ref_offset(raw
));
210 jffs2_mark_node_obsolete(c
, raw
);
214 if (ic
->scan_dents
) {
216 dbg_fsbuild("inode #%u was a directory which may have children...\n", ic
->ino
);
218 while(ic
->scan_dents
) {
219 struct jffs2_inode_cache
*child_ic
;
222 ic
->scan_dents
= fd
->next
;
225 /* It's a deletion dirent. Ignore it */
226 dbg_fsbuild("child \"%s\" is a deletion dirent, skipping...\n", fd
->name
);
227 jffs2_free_full_dirent(fd
);
233 dbg_fsbuild("removing child \"%s\", ino #%u\n", fd
->name
, fd
->ino
);
235 child_ic
= jffs2_get_ino_cache(c
, fd
->ino
);
237 dbg_fsbuild("cannot remove child \"%s\", ino #%u, because it doesn't exist\n",
239 jffs2_free_full_dirent(fd
);
243 /* Reduce nlink of the child. If it's now zero, stick it on the
244 dead_fds list to be cleaned up later. Else just free the fd */
248 if (!child_ic
->nlink
) {
249 dbg_fsbuild("inode #%u (\"%s\") has now got zero nlink, adding to dead_fds list.\n",
251 fd
->next
= *dead_fds
;
254 dbg_fsbuild("inode #%u (\"%s\") has now got nlink %d. Ignoring.\n",
255 fd
->ino
, fd
->name
, child_ic
->nlink
);
256 jffs2_free_full_dirent(fd
);
262 We don't delete the inocache from the hash list and free it yet.
263 The erase code will do that, when all the nodes are completely gone.
267 static void jffs2_calc_trigger_levels(struct jffs2_sb_info
*c
)
271 /* Deletion should almost _always_ be allowed. We're fairly
272 buggered once we stop allowing people to delete stuff
273 because there's not enough free space... */
274 c
->resv_blocks_deletion
= 2;
276 /* Be conservative about how much space we need before we allow writes.
277 On top of that which is required for deletia, require an extra 2%
278 of the medium to be available, for overhead caused by nodes being
279 split across blocks, etc. */
281 size
= c
->flash_size
/ 50; /* 2% of flash size */
282 size
+= c
->nr_blocks
* 100; /* And 100 bytes per eraseblock */
283 size
+= c
->sector_size
- 1; /* ... and round up */
285 c
->resv_blocks_write
= c
->resv_blocks_deletion
+ (size
/ c
->sector_size
);
287 /* When do we let the GC thread run in the background */
289 c
->resv_blocks_gctrigger
= c
->resv_blocks_write
+ 1;
291 /* When do we allow garbage collection to merge nodes to make
292 long-term progress at the expense of short-term space exhaustion? */
293 c
->resv_blocks_gcmerge
= c
->resv_blocks_deletion
+ 1;
295 /* When do we allow garbage collection to eat from bad blocks rather
296 than actually making progress? */
297 c
->resv_blocks_gcbad
= 0;//c->resv_blocks_deletion + 2;
299 /* If there's less than this amount of dirty space, don't bother
300 trying to GC to make more space. It'll be a fruitless task */
301 c
->nospc_dirty_size
= c
->sector_size
+ (c
->flash_size
/ 100);
303 dbg_fsbuild("JFFS2 trigger levels (size %d KiB, block size %d KiB, %d blocks)\n",
304 c
->flash_size
/ 1024, c
->sector_size
/ 1024, c
->nr_blocks
);
305 dbg_fsbuild("Blocks required to allow deletion: %d (%d KiB)\n",
306 c
->resv_blocks_deletion
, c
->resv_blocks_deletion
*c
->sector_size
/1024);
307 dbg_fsbuild("Blocks required to allow writes: %d (%d KiB)\n",
308 c
->resv_blocks_write
, c
->resv_blocks_write
*c
->sector_size
/1024);
309 dbg_fsbuild("Blocks required to quiesce GC thread: %d (%d KiB)\n",
310 c
->resv_blocks_gctrigger
, c
->resv_blocks_gctrigger
*c
->sector_size
/1024);
311 dbg_fsbuild("Blocks required to allow GC merges: %d (%d KiB)\n",
312 c
->resv_blocks_gcmerge
, c
->resv_blocks_gcmerge
*c
->sector_size
/1024);
313 dbg_fsbuild("Blocks required to GC bad blocks: %d (%d KiB)\n",
314 c
->resv_blocks_gcbad
, c
->resv_blocks_gcbad
*c
->sector_size
/1024);
315 dbg_fsbuild("Amount of dirty space required to GC: %d bytes\n",
316 c
->nospc_dirty_size
);
319 int jffs2_do_mount_fs(struct jffs2_sb_info
*c
)
325 c
->free_size
= c
->flash_size
;
326 c
->nr_blocks
= c
->flash_size
/ c
->sector_size
;
327 size
= sizeof(struct jffs2_eraseblock
) * c
->nr_blocks
;
329 if (jffs2_blocks_use_vmalloc(c
))
330 c
->blocks
= vmalloc(size
);
333 c
->blocks
= kmalloc(size
, GFP_KERNEL
);
337 memset(c
->blocks
, 0, size
);
338 for (i
=0; i
<c
->nr_blocks
; i
++) {
339 INIT_LIST_HEAD(&c
->blocks
[i
].list
);
340 c
->blocks
[i
].offset
= i
* c
->sector_size
;
341 c
->blocks
[i
].free_size
= c
->sector_size
;
344 INIT_LIST_HEAD(&c
->clean_list
);
345 INIT_LIST_HEAD(&c
->very_dirty_list
);
346 INIT_LIST_HEAD(&c
->dirty_list
);
347 INIT_LIST_HEAD(&c
->erasable_list
);
348 INIT_LIST_HEAD(&c
->erasing_list
);
349 INIT_LIST_HEAD(&c
->erase_pending_list
);
350 INIT_LIST_HEAD(&c
->erasable_pending_wbuf_list
);
351 INIT_LIST_HEAD(&c
->erase_complete_list
);
352 INIT_LIST_HEAD(&c
->free_list
);
353 INIT_LIST_HEAD(&c
->bad_list
);
354 INIT_LIST_HEAD(&c
->bad_used_list
);
358 ret
= jffs2_sum_init(c
);
362 if (jffs2_build_filesystem(c
)) {
363 dbg_fsbuild("build_fs failed\n");
364 jffs2_free_ino_caches(c
);
365 jffs2_free_raw_node_refs(c
);
370 jffs2_calc_trigger_levels(c
);
376 if (jffs2_blocks_use_vmalloc(c
))