Root/fs/jffs2/build.c

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
19static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *,
20        struct jffs2_inode_cache *, struct jffs2_full_dirent **);
21
22static inline struct jffs2_inode_cache *
23first_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
32static inline struct jffs2_inode_cache *
33next_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
48static 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*/
92static 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    if (c->flags & (1 << 7)) {
115        printk("%s(): unlocking the mtd device... ", __func__);
116        if (c->mtd->unlock)
117            c->mtd->unlock(c->mtd, 0, c->mtd->size);
118        printk("done.\n");
119
120        printk("%s(): erasing all blocks after the end marker... ", __func__);
121        jffs2_erase_pending_blocks(c, -1);
122        printk("done.\n");
123    }
124
125    dbg_fsbuild("pass 1 starting\n");
126    c->flags |= JFFS2_SB_FLAG_BUILDING;
127    /* Now scan the directory tree, increasing nlink according to every dirent found. */
128    for_each_inode(i, c, ic) {
129        if (ic->scan_dents) {
130            jffs2_build_inode_pass1(c, ic);
131            cond_resched();
132        }
133    }
134
135    dbg_fsbuild("pass 1 complete\n");
136
137    /* Next, scan for inodes with nlink == 0 and remove them. If
138       they were directories, then decrement the nlink of their
139       children too, and repeat the scan. As that's going to be
140       a fairly uncommon occurrence, it's not so evil to do it this
141       way. Recursion bad. */
142    dbg_fsbuild("pass 2 starting\n");
143
144    for_each_inode(i, c, ic) {
145        if (ic->pino_nlink)
146            continue;
147
148        jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
149        cond_resched();
150    }
151
152    dbg_fsbuild("pass 2a starting\n");
153
154    while (dead_fds) {
155        fd = dead_fds;
156        dead_fds = fd->next;
157
158        ic = jffs2_get_ino_cache(c, fd->ino);
159
160        if (ic)
161            jffs2_build_remove_unlinked_inode(c, ic, &dead_fds);
162        jffs2_free_full_dirent(fd);
163    }
164
165    dbg_fsbuild("pass 2a complete\n");
166    dbg_fsbuild("freeing temporary data structures\n");
167
168    /* Finally, we can scan again and free the dirent structs */
169    for_each_inode(i, c, ic) {
170        while(ic->scan_dents) {
171            fd = ic->scan_dents;
172            ic->scan_dents = fd->next;
173            jffs2_free_full_dirent(fd);
174        }
175        ic->scan_dents = NULL;
176        cond_resched();
177    }
178    jffs2_build_xattr_subsystem(c);
179    c->flags &= ~JFFS2_SB_FLAG_BUILDING;
180
181    dbg_fsbuild("FS build complete\n");
182
183    /* Rotate the lists by some number to ensure wear levelling */
184    jffs2_rotate_lists(c);
185
186    ret = 0;
187
188exit:
189    if (ret) {
190        for_each_inode(i, c, ic) {
191            while(ic->scan_dents) {
192                fd = ic->scan_dents;
193                ic->scan_dents = fd->next;
194                jffs2_free_full_dirent(fd);
195            }
196        }
197        jffs2_clear_xattr_subsystem(c);
198    }
199
200    return ret;
201}
202
203static void jffs2_build_remove_unlinked_inode(struct jffs2_sb_info *c,
204                    struct jffs2_inode_cache *ic,
205                    struct jffs2_full_dirent **dead_fds)
206{
207    struct jffs2_raw_node_ref *raw;
208    struct jffs2_full_dirent *fd;
209
210    dbg_fsbuild("removing ino #%u with nlink == zero.\n", ic->ino);
211
212    raw = ic->nodes;
213    while (raw != (void *)ic) {
214        struct jffs2_raw_node_ref *next = raw->next_in_ino;
215        dbg_fsbuild("obsoleting node at 0x%08x\n", ref_offset(raw));
216        jffs2_mark_node_obsolete(c, raw);
217        raw = next;
218    }
219
220    if (ic->scan_dents) {
221        int whinged = 0;
222        dbg_fsbuild("inode #%u was a directory which may have children...\n", ic->ino);
223
224        while(ic->scan_dents) {
225            struct jffs2_inode_cache *child_ic;
226
227            fd = ic->scan_dents;
228            ic->scan_dents = fd->next;
229
230            if (!fd->ino) {
231                /* It's a deletion dirent. Ignore it */
232                dbg_fsbuild("child \"%s\" is a deletion dirent, skipping...\n", fd->name);
233                jffs2_free_full_dirent(fd);
234                continue;
235            }
236            if (!whinged)
237                whinged = 1;
238
239            dbg_fsbuild("removing child \"%s\", ino #%u\n", fd->name, fd->ino);
240
241            child_ic = jffs2_get_ino_cache(c, fd->ino);
242            if (!child_ic) {
243                dbg_fsbuild("cannot remove child \"%s\", ino #%u, because it doesn't exist\n",
244                        fd->name, fd->ino);
245                jffs2_free_full_dirent(fd);
246                continue;
247            }
248
249            /* Reduce nlink of the child. If it's now zero, stick it on the
250               dead_fds list to be cleaned up later. Else just free the fd */
251
252            if (fd->type == DT_DIR)
253                child_ic->pino_nlink = 0;
254            else
255                child_ic->pino_nlink--;
256
257            if (!child_ic->pino_nlink) {
258                dbg_fsbuild("inode #%u (\"%s\") now has no links; adding to dead_fds list.\n",
259                      fd->ino, fd->name);
260                fd->next = *dead_fds;
261                *dead_fds = fd;
262            } else {
263                dbg_fsbuild("inode #%u (\"%s\") has now got nlink %d. Ignoring.\n",
264                      fd->ino, fd->name, child_ic->pino_nlink);
265                jffs2_free_full_dirent(fd);
266            }
267        }
268    }
269
270    /*
271       We don't delete the inocache from the hash list and free it yet.
272       The erase code will do that, when all the nodes are completely gone.
273    */
274}
275
276static void jffs2_calc_trigger_levels(struct jffs2_sb_info *c)
277{
278    uint32_t size;
279
280    /* Deletion should almost _always_ be allowed. We're fairly
281       buggered once we stop allowing people to delete stuff
282       because there's not enough free space... */
283    c->resv_blocks_deletion = 2;
284
285    /* Be conservative about how much space we need before we allow writes.
286       On top of that which is required for deletia, require an extra 2%
287       of the medium to be available, for overhead caused by nodes being
288       split across blocks, etc. */
289
290    size = c->flash_size / 50; /* 2% of flash size */
291    size += c->nr_blocks * 100; /* And 100 bytes per eraseblock */
292    size += c->sector_size - 1; /* ... and round up */
293
294    c->resv_blocks_write = c->resv_blocks_deletion + (size / c->sector_size);
295
296    /* When do we let the GC thread run in the background */
297
298    c->resv_blocks_gctrigger = c->resv_blocks_write + 1;
299
300    /* When do we allow garbage collection to merge nodes to make
301       long-term progress at the expense of short-term space exhaustion? */
302    c->resv_blocks_gcmerge = c->resv_blocks_deletion + 1;
303
304    /* When do we allow garbage collection to eat from bad blocks rather
305       than actually making progress? */
306    c->resv_blocks_gcbad = 0;//c->resv_blocks_deletion + 2;
307
308    /* What number of 'very dirty' eraseblocks do we allow before we
309       trigger the GC thread even if we don't _need_ the space. When we
310       can't mark nodes obsolete on the medium, the old dirty nodes cause
311       performance problems because we have to inspect and discard them. */
312    c->vdirty_blocks_gctrigger = c->resv_blocks_gctrigger;
313    if (jffs2_can_mark_obsolete(c))
314        c->vdirty_blocks_gctrigger *= 10;
315
316    /* If there's less than this amount of dirty space, don't bother
317       trying to GC to make more space. It'll be a fruitless task */
318    c->nospc_dirty_size = c->sector_size + (c->flash_size / 100);
319
320    dbg_fsbuild("JFFS2 trigger levels (size %d KiB, block size %d KiB, %d blocks)\n",
321          c->flash_size / 1024, c->sector_size / 1024, c->nr_blocks);
322    dbg_fsbuild("Blocks required to allow deletion: %d (%d KiB)\n",
323          c->resv_blocks_deletion, c->resv_blocks_deletion*c->sector_size/1024);
324    dbg_fsbuild("Blocks required to allow writes: %d (%d KiB)\n",
325          c->resv_blocks_write, c->resv_blocks_write*c->sector_size/1024);
326    dbg_fsbuild("Blocks required to quiesce GC thread: %d (%d KiB)\n",
327          c->resv_blocks_gctrigger, c->resv_blocks_gctrigger*c->sector_size/1024);
328    dbg_fsbuild("Blocks required to allow GC merges: %d (%d KiB)\n",
329          c->resv_blocks_gcmerge, c->resv_blocks_gcmerge*c->sector_size/1024);
330    dbg_fsbuild("Blocks required to GC bad blocks: %d (%d KiB)\n",
331          c->resv_blocks_gcbad, c->resv_blocks_gcbad*c->sector_size/1024);
332    dbg_fsbuild("Amount of dirty space required to GC: %d bytes\n",
333          c->nospc_dirty_size);
334    dbg_fsbuild("Very dirty blocks before GC triggered: %d\n",
335          c->vdirty_blocks_gctrigger);
336}
337
338int jffs2_do_mount_fs(struct jffs2_sb_info *c)
339{
340    int ret;
341    int i;
342    int size;
343
344    c->free_size = c->flash_size;
345    c->nr_blocks = c->flash_size / c->sector_size;
346    size = sizeof(struct jffs2_eraseblock) * c->nr_blocks;
347#ifndef __ECOS
348    if (jffs2_blocks_use_vmalloc(c))
349        c->blocks = vmalloc(size);
350    else
351#endif
352        c->blocks = kmalloc(size, GFP_KERNEL);
353    if (!c->blocks)
354        return -ENOMEM;
355
356    memset(c->blocks, 0, size);
357    for (i=0; i<c->nr_blocks; i++) {
358        INIT_LIST_HEAD(&c->blocks[i].list);
359        c->blocks[i].offset = i * c->sector_size;
360        c->blocks[i].free_size = c->sector_size;
361    }
362
363    INIT_LIST_HEAD(&c->clean_list);
364    INIT_LIST_HEAD(&c->very_dirty_list);
365    INIT_LIST_HEAD(&c->dirty_list);
366    INIT_LIST_HEAD(&c->erasable_list);
367    INIT_LIST_HEAD(&c->erasing_list);
368    INIT_LIST_HEAD(&c->erase_checking_list);
369    INIT_LIST_HEAD(&c->erase_pending_list);
370    INIT_LIST_HEAD(&c->erasable_pending_wbuf_list);
371    INIT_LIST_HEAD(&c->erase_complete_list);
372    INIT_LIST_HEAD(&c->free_list);
373    INIT_LIST_HEAD(&c->bad_list);
374    INIT_LIST_HEAD(&c->bad_used_list);
375    c->highest_ino = 1;
376    c->summary = NULL;
377
378    ret = jffs2_sum_init(c);
379    if (ret)
380        goto out_free;
381
382    if (jffs2_build_filesystem(c)) {
383        dbg_fsbuild("build_fs failed\n");
384        jffs2_free_ino_caches(c);
385        jffs2_free_raw_node_refs(c);
386        ret = -EIO;
387        goto out_free;
388    }
389
390    jffs2_calc_trigger_levels(c);
391
392    return 0;
393
394 out_free:
395#ifndef __ECOS
396    if (jffs2_blocks_use_vmalloc(c))
397        vfree(c->blocks);
398    else
399#endif
400        kfree(c->blocks);
401
402    return ret;
403}
404

Archive Download this file



interactive