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