~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/jffs2/build.c

Version: ~ [ linux-5.3-rc4 ] ~ [ linux-5.2.8 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.66 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.138 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.189 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.189 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.71 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp