fs/jffs2/build.c

0001 /*
0002  * JFFS2 -- Journalling Flash File System, Version 2.
0003  *
0004  * Copyright © 2001-2007 Red Hat, Inc.
0005  * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
0006  *
0007  * Created by David Woodhouse <dwmw2@infradead.org>
0008  *
0009  * For licensing information, see the file 'LICENCE' in this directory.
0010  *
0011  */
0012
0013 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0014
0015 #include <linux/kernel.h>
0016 #include <linux/sched.h>
0017 #include <linux/slab.h>
0018 #include <linux/vmalloc.h>
0019 #include <linux/mtd/mtd.h>
0020 #include <linux/mm.h> /* kvfree() */
0021 #include "nodelist.h"
0022
0023 static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *,
0024         struct jffs2_inode_cache *, struct jffs2_full_dirent **);
0025
0026 static inline struct jffs2_inode_cache *
0027 first_inode_chain(int *i, struct jffs2_sb_info *c)
0028 {
0029     for (; *i < c->inocache_hashsize; (*i)++) {
0030         if (c->inocache_list[*i])
0031             return c->inocache_list[*i];
0032     }
0033     return NULL;
0034 }
0035
0036 static inline struct jffs2_inode_cache *
0037 next_inode(int *i, struct jffs2_inode_cache *ic, struct jffs2_sb_info *c)
0038 {
0039     /* More in this chain? */
0040     if (ic->next)
0041         return ic->next;
0042     (*i)++;
0043     return first_inode_chain(i, c);
0044 }
0045
0046 #define for_each_inode(i, c, ic)            \
0047     for (i = 0, ic = first_inode_chain(&i, (c));    \
0048          ic;                    \
0049          ic = next_inode(&i, ic, (c)))
0050
0051
0052 static void jffs2_build_inode_pass1(struct jffs2_sb_info *c,
0053                     struct jffs2_inode_cache *ic,
0054                     int *dir_hardlinks)
0055 {
0056     struct jffs2_full_dirent *fd;
0057
0058     dbg_fsbuild("building directory inode #%u\n", ic->ino);
0059
0060     /* For each child, increase nlink */
0061     for(fd = ic->scan_dents; fd; fd = fd->next) {
0062         struct jffs2_inode_cache *child_ic;
0063         if (!fd->ino)
0064             continue;
0065
0066         /* we can get high latency here with huge directories */
0067
0068         child_ic = jffs2_get_ino_cache(c, fd->ino);
0069         if (!child_ic) {
0070             dbg_fsbuild("child \"%s\" (ino #%u) of dir ino #%u doesn't exist!\n",
0071                   fd->name, fd->ino, ic->ino);
0072             jffs2_mark_node_obsolete(c, fd->raw);
0073             /* Clear the ic/raw union so it doesn't cause problems later. */
0074             fd->ic = NULL;
0075             continue;
0076         }
0077
0078         /* From this point, fd->raw is no longer used so we can set fd->ic */
0079         fd->ic = child_ic;
0080         child_ic->pino_nlink++;
0081         /* If we appear (at this stage) to have hard-linked directories,
0082          * set a flag to trigger a scan later */
0083         if (fd->type == DT_DIR) {
0084             child_ic->flags |= INO_FLAGS_IS_DIR;
0085             if (child_ic->pino_nlink > 1)
0086                 *dir_hardlinks = 1;
0087         }
0088
0089         dbg_fsbuild("increased nlink for child \"%s\" (ino #%u)\n", fd->name, fd->ino);
0090         /* Can't free scan_dents so far. We might need them in pass 2 */
0091     }
0092 }
0093
0094 /* Scan plan:
0095  - Scan physical nodes. Build map of inodes/dirents. Allocate inocaches as we go
0096  - Scan directory tree from top down, setting nlink in inocaches
0097  - Scan inocaches for inodes with nlink==0
0098 */
0099 static int jffs2_build_filesystem(struct jffs2_sb_info *c)
0100 {
0101     int ret, i, dir_hardlinks = 0;
0102     struct jffs2_inode_cache *ic;
0103     struct jffs2_full_dirent *fd;
0104     struct jffs2_full_dirent *dead_fds = NULL;
0105
0106     dbg_fsbuild("build FS data structures\n");
0107
0108     /* First, scan the medium and build all the inode caches with
0109        lists of physical nodes */
0110
0111     c->flags |= JFFS2_SB_FLAG_SCANNING;
0112     ret = jffs2_scan_medium(c);
0113     c->flags &= ~JFFS2_SB_FLAG_SCANNING;
0114     if (ret)
0115         goto exit;
0116
0117     dbg_fsbuild("scanned flash completely\n");
0118     jffs2_dbg_dump_block_lists_nolock(c);
0119
0120     dbg_fsbuild("pass 1 starting\n");
0121     c->flags |= JFFS2_SB_FLAG_BUILDING;
0122     /* Now scan the directory tree, increasing nlink according to every dirent found. */
0123     for_each_inode(i, c, ic) {
0124         if (ic->scan_dents) {
0125             jffs2_build_inode_pass1(c, ic, &dir_hardlinks);
0126             cond_resched();
0127         }
0128     }
0129
0130     dbg_fsbuild("pass 1 complete\n");
0131
0132     /* Next, scan for inodes with nlink == 0 and remove them. If
0133        they were directories, then decrement the nlink of their
0134        children too, and repeat the scan. As that's going to be
0135        a fairly uncommon occurrence, it's not so evil to do it this
0136        way. Recursion bad. */
0137     dbg_fsbuild("pass 2 starting\n");
0138
0139     for_each_inode(i, c, ic) {
0140         if (ic->pino_nlink)
0141             continue;
0142
0143         jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
0144         cond_resched();
0145     }
0146
0147     dbg_fsbuild("pass 2a starting\n");
0148
0149     while (dead_fds) {
0150         fd = dead_fds;
0151         dead_fds = fd->next;
0152
0153         ic = jffs2_get_ino_cache(c, fd->ino);
0154
0155         if (ic)
0156             jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
0157         jffs2_free_full_dirent(fd);
0158     }
0159
0160     dbg_fsbuild("pass 2a complete\n");
0161
0162     if (dir_hardlinks) {
0163         /* If we detected directory hardlinks earlier, *hopefully*
0164          * they are gone now because some of the links were from
0165          * dead directories which still had some old dirents lying
0166          * around and not yet garbage-collected, but which have
0167          * been discarded above. So clear the pino_nlink field
0168          * in each directory, so that the final scan below can
0169          * print appropriate warnings. */
0170         for_each_inode(i, c, ic) {
0171             if (ic->flags & INO_FLAGS_IS_DIR)
0172                 ic->pino_nlink = 0;
0173         }
0174     }
0175     dbg_fsbuild("freeing temporary data structures\n");
0176
0177     /* Finally, we can scan again and free the dirent structs */
0178     for_each_inode(i, c, ic) {
0179         while(ic->scan_dents) {
0180             fd = ic->scan_dents;
0181             ic->scan_dents = fd->next;
0182             /* We do use the pino_nlink field to count nlink of
0183              * directories during fs build, so set it to the
0184              * parent ino# now. Now that there's hopefully only
0185              * one. */
0186             if (fd->type == DT_DIR) {
0187                 if (!fd->ic) {
0188                     /* We'll have complained about it and marked the coresponding
0189                        raw node obsolete already. Just skip it. */
0190                     continue;
0191                 }
0192
0193                 /* We *have* to have set this in jffs2_build_inode_pass1() */
0194                 BUG_ON(!(fd->ic->flags & INO_FLAGS_IS_DIR));
0195
0196                 /* We clear ic->pino_nlink ∀ directories' ic *only* if dir_hardlinks
0197                  * is set. Otherwise, we know this should never trigger anyway, so
0198                  * we don't do the check. And ic->pino_nlink still contains the nlink
0199                  * value (which is 1). */
0200                 if (dir_hardlinks && fd->ic->pino_nlink) {
0201                     JFFS2_ERROR("child dir \"%s\" (ino #%u) of dir ino #%u is also hard linked from dir ino #%u\n",
0202                             fd->name, fd->ino, ic->ino, fd->ic->pino_nlink);
0203                     /* Should we unlink it from its previous parent? */
0204                 }
0205
0206                 /* For directories, ic->pino_nlink holds that parent inode # */
0207                 fd->ic->pino_nlink = ic->ino;
0208             }
0209             jffs2_free_full_dirent(fd);
0210         }
0211         ic->scan_dents = NULL;
0212         cond_resched();
0213     }
0214     jffs2_build_xattr_subsystem(c);
0215     c->flags &= ~JFFS2_SB_FLAG_BUILDING;
0216
0217     dbg_fsbuild("FS build complete\n");
0218
0219     /* Rotate the lists by some number to ensure wear levelling */
0220     jffs2_rotate_lists(c);
0221
0222     ret = 0;
0223
0224 exit:
0225     if (ret) {
0226         for_each_inode(i, c, ic) {
0227             while(ic->scan_dents) {
0228                 fd = ic->scan_dents;
0229                 ic->scan_dents = fd->next;
0230                 jffs2_free_full_dirent(fd);
0231             }
0232         }
0233         jffs2_clear_xattr_subsystem(c);
0234     }
0235
0236     return ret;
0237 }
0238
0239 static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *c,
0240                     struct jffs2_inode_cache *ic,
0241                     struct jffs2_full_dirent **dead_fds)
0242 {
0243     struct jffs2_raw_node_ref *raw;
0244     struct jffs2_full_dirent *fd;
0245
0246     dbg_fsbuild("removing ino #%u with nlink == zero.\n", ic->ino);
0247
0248     raw = ic->nodes;
0249     while (raw != (void *)ic) {
0250         struct jffs2_raw_node_ref *next = raw->next_in_ino;
0251         dbg_fsbuild("obsoleting node at 0x%08x\n", ref_offset(raw));
0252         jffs2_mark_node_obsolete(c, raw);
0253         raw = next;
0254     }
0255
0256     if (ic->scan_dents) {
0257         int whinged = 0;
0258         dbg_fsbuild("inode #%u was a directory which may have children...\n", ic->ino);
0259
0260         while(ic->scan_dents) {
0261             struct jffs2_inode_cache *child_ic;
0262
0263             fd = ic->scan_dents;
0264             ic->scan_dents = fd->next;
0265
0266             if (!fd->ino) {
0267                 /* It's a deletion dirent. Ignore it */
0268                 dbg_fsbuild("child \"%s\" is a deletion dirent, skipping...\n", fd->name);
0269                 jffs2_free_full_dirent(fd);
0270                 continue;
0271             }
0272             if (!whinged)
0273                 whinged = 1;
0274
0275             dbg_fsbuild("removing child \"%s\", ino #%u\n", fd->name, fd->ino);
0276
0277             child_ic = jffs2_get_ino_cache(c, fd->ino);
0278             if (!child_ic) {
0279                 dbg_fsbuild("cannot remove child \"%s\", ino #%u, because it doesn't exist\n",
0280                         fd->name, fd->ino);
0281                 jffs2_free_full_dirent(fd);
0282                 continue;
0283             }
0284
0285             /* Reduce nlink of the child. If it's now zero, stick it on the
0286                dead_fds list to be cleaned up later. Else just free the fd */
0287             child_ic->pino_nlink--;
0288
0289             if (!child_ic->pino_nlink) {
0290                 dbg_fsbuild("inode #%u (\"%s\") now has no links; adding to dead_fds list.\n",
0291                       fd->ino, fd->name);
0292                 fd->next = *dead_fds;
0293                 *dead_fds = fd;
0294             } else {
0295                 dbg_fsbuild("inode #%u (\"%s\") has now got nlink %d. Ignoring.\n",
0296                       fd->ino, fd->name, child_ic->pino_nlink);
0297                 jffs2_free_full_dirent(fd);
0298             }
0299         }
0300     }
0301
0302     /*
0303        We don't delete the inocache from the hash list and free it yet.
0304        The erase code will do that, when all the nodes are completely gone.
0305     */
0306 }
0307
0308 static void jffs2_calc_trigger_levels(struct jffs2_sb_info *c)
0309 {
0310     uint32_t size;
0311
0312     /* Deletion should almost _always_ be allowed. We're fairly
0313        buggered once we stop allowing people to delete stuff
0314        because there's not enough free space... */
0315     c->resv_blocks_deletion = 2;
0316
0317     /* Be conservative about how much space we need before we allow writes.
0318        On top of that which is required for deletia, require an extra 2%
0319        of the medium to be available, for overhead caused by nodes being
0320        split across blocks, etc. */
0321
0322     size = c->flash_size / 50; /* 2% of flash size */
0323     size += c->nr_blocks * 100; /* And 100 bytes per eraseblock */
0324     size += c->sector_size - 1; /* ... and round up */
0325
0326     c->resv_blocks_write = c->resv_blocks_deletion + (size / c->sector_size);
0327
0328     /* When do we let the GC thread run in the background */
0329
0330     c->resv_blocks_gctrigger = c->resv_blocks_write + 1;
0331
0332     /* When do we allow garbage collection to merge nodes to make
0333        long-term progress at the expense of short-term space exhaustion? */
0334     c->resv_blocks_gcmerge = c->resv_blocks_deletion + 1;
0335
0336     /* When do we allow garbage collection to eat from bad blocks rather
0337        than actually making progress? */
0338     c->resv_blocks_gcbad = 0;//c->resv_blocks_deletion + 2;
0339
0340     /* What number of 'very dirty' eraseblocks do we allow before we
0341        trigger the GC thread even if we don't _need_ the space. When we
0342        can't mark nodes obsolete on the medium, the old dirty nodes cause
0343        performance problems because we have to inspect and discard them. */
0344     c->vdirty_blocks_gctrigger = c->resv_blocks_gctrigger;
0345     if (jffs2_can_mark_obsolete(c))
0346         c->vdirty_blocks_gctrigger *= 10;
0347
0348     /* If there's less than this amount of dirty space, don't bother
0349        trying to GC to make more space. It'll be a fruitless task */
0350     c->nospc_dirty_size = c->sector_size + (c->flash_size / 100);
0351
0352     dbg_fsbuild("trigger levels (size %d KiB, block size %d KiB, %d blocks)\n",
0353             c->flash_size / 1024, c->sector_size / 1024, c->nr_blocks);
0354     dbg_fsbuild("Blocks required to allow deletion:    %d (%d KiB)\n",
0355           c->resv_blocks_deletion, c->resv_blocks_deletion*c->sector_size/1024);
0356     dbg_fsbuild("Blocks required to allow writes:      %d (%d KiB)\n",
0357           c->resv_blocks_write, c->resv_blocks_write*c->sector_size/1024);
0358     dbg_fsbuild("Blocks required to quiesce GC thread: %d (%d KiB)\n",
0359           c->resv_blocks_gctrigger, c->resv_blocks_gctrigger*c->sector_size/1024);
0360     dbg_fsbuild("Blocks required to allow GC merges:   %d (%d KiB)\n",
0361           c->resv_blocks_gcmerge, c->resv_blocks_gcmerge*c->sector_size/1024);
0362     dbg_fsbuild("Blocks required to GC bad blocks:     %d (%d KiB)\n",
0363           c->resv_blocks_gcbad, c->resv_blocks_gcbad*c->sector_size/1024);
0364     dbg_fsbuild("Amount of dirty space required to GC: %d bytes\n",
0365           c->nospc_dirty_size);
0366     dbg_fsbuild("Very dirty blocks before GC triggered: %d\n",
0367           c->vdirty_blocks_gctrigger);
0368 }
0369
0370 int jffs2_do_mount_fs(struct jffs2_sb_info *c)
0371 {
0372     int ret;
0373     int i;
0374     int size;
0375
0376     c->free_size = c->flash_size;
0377     c->nr_blocks = c->flash_size / c->sector_size;
0378     size = sizeof(struct jffs2_eraseblock) * c->nr_blocks;
0379 #ifndef __ECOS
0380     if (jffs2_blocks_use_vmalloc(c))
0381         c->blocks = vzalloc(size);
0382     else
0383 #endif
0384         c->blocks = kzalloc(size, GFP_KERNEL);
0385     if (!c->blocks)
0386         return -ENOMEM;
0387
0388     for (i=0; i<c->nr_blocks; i++) {
0389         INIT_LIST_HEAD(&c->blocks[i].list);
0390         c->blocks[i].offset = i * c->sector_size;
0391         c->blocks[i].free_size = c->sector_size;
0392     }
0393
0394     INIT_LIST_HEAD(&c->clean_list);
0395     INIT_LIST_HEAD(&c->very_dirty_list);
0396     INIT_LIST_HEAD(&c->dirty_list);
0397     INIT_LIST_HEAD(&c->erasable_list);
0398     INIT_LIST_HEAD(&c->erasing_list);
0399     INIT_LIST_HEAD(&c->erase_checking_list);
0400     INIT_LIST_HEAD(&c->erase_pending_list);
0401     INIT_LIST_HEAD(&c->erasable_pending_wbuf_list);
0402     INIT_LIST_HEAD(&c->erase_complete_list);
0403     INIT_LIST_HEAD(&c->free_list);
0404     INIT_LIST_HEAD(&c->bad_list);
0405     INIT_LIST_HEAD(&c->bad_used_list);
0406     c->highest_ino = 1;
0407     c->summary = NULL;
0408
0409     ret = jffs2_sum_init(c);
0410     if (ret)
0411         goto out_free;
0412
0413     if (jffs2_build_filesystem(c)) {
0414         dbg_fsbuild("build_fs failed\n");
0415         jffs2_free_ino_caches(c);
0416         jffs2_free_raw_node_refs(c);
0417         ret = -EIO;
0418         goto out_sum_exit;
0419     }
0420
0421     jffs2_calc_trigger_levels(c);
0422
0423     return 0;
0424
0425  out_sum_exit:
0426     jffs2_sum_exit(c);
0427  out_free:
0428     kvfree(c->blocks);
0429
0430     return ret;
0431 }