| blob | 456d7e6e29c2683bd2fc4724b7980cb81171bfff |
1 /*
2 * JFFS -- Journaling Flash File System, Linux implementation.
3 *
4 * Copyright (C) 1999, 2000 Axis Communications, Inc.
5 *
6 * Created by Finn Hakansson <finn@axis.com>.
7 *
8 * This is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * $Id: intrep.c,v 1.102 2001/09/23 23:28:36 dwmw2 Exp $
14 *
15 * Ported to Linux 2.3.x and MTD:
16 * Copyright (C) 2000 Alexander Larsson (alex@cendio.se), Cendio Systems AB
17 *
18 */
20 /* This file contains the code for the internal structure of the
21 Journaling Flash File System, JFFS. */
23 /*
24 * Todo list:
25 *
26 * memcpy_to_flash() and memcpy_from_flash() functions.
27 *
28 * Implementation of hard links.
29 *
30 * Organize the source code in a better way. Against the VFS we could
31 * have jffs_ext.c, and against the block device jffs_int.c.
32 * A better file-internal organization too.
33 *
34 * A better checksum algorithm.
35 *
36 * Consider endianness stuff. ntohl() etc.
37 *
38 * Are we handling the atime, mtime, ctime members of the inode right?
39 *
40 * Remove some duplicated code. Take a look at jffs_write_node() and
41 * jffs_rewrite_data() for instance.
42 *
43 * Implement more meaning of the nlink member in various data structures.
44 * nlink could be used in conjunction with hard links for instance.
45 *
46 * Better memory management. Allocate data structures in larger chunks
47 * if possible.
48 *
49 * If too much meta data is stored, a garbage collect should be issued.
50 * We have experienced problems with too much meta data with for instance
51 * log files.
52 *
53 * Improve the calls to jffs_ioctl(). We would like to retrieve more
54 * information to be able to debug (or to supervise) JFFS during run-time.
55 *
56 */
58 #include <linux/config.h>
59 #include <linux/types.h>
60 #include <linux/slab.h>
61 #include <linux/jffs.h>
62 #include <linux/fs.h>
63 #include <linux/stat.h>
64 #include <linux/pagemap.h>
65 #include <asm/semaphore.h>
66 #include <asm/byteorder.h>
67 #include <linux/smp_lock.h>
68 #include <linux/time.h>
69 #include <linux/ctype.h>
76 #if defined(JFFS_MEMORY_DEBUG) && JFFS_MEMORY_DEBUG
84 #endif
95 /* Is there enough space on the flash? */
97 {
104 }
111 }
112 }
113 }
115 #if CONFIG_JFFS_FS_VERBOSE > 0
116 static __u8
118 {
120 __u8 ret;
127 }
130 }
132 static void
134 {
144 }
148 }
151 }
152 }
154 /* Print empty space */
158 }
161 }
162 }
168 }
171 }
172 }
175 }
176 }
178 /* Print the contents of a node. */
179 static void
181 {
197 }
199 #endif
201 /* Print the contents of a raw inode. */
202 static void
204 {
234 }
236 #define flash_safe_acquire(arg)
237 #define flash_safe_release(arg)
240 static int
243 {
253 }
255 }
258 static __u32
260 {
262 __u32 ret;
269 }
272 }
275 static int
278 {
288 }
290 }
293 static int
296 {
307 }
308 /* Not implemented writev. Repeatedly use write - on the not so
309 unreasonable assumption that the mtd driver doesn't care how
310 many write cycles we use. */
320 }
321 /* If res is non-zero, retlen_a is undefined, but we don't
322 care because in that case it's not going to be
323 returned anyway.
324 */
327 }
329 }
332 static int
335 {
339 /* fill up pattern */
344 /* write as many 64-byte chunks as we can */
350 }
352 /* and the rest */
358 }
361 static void
363 {
369 }
372 static int
375 {
378 wait_queue_head_t wait_q;
392 /* FIXME: Use TASK_INTERRUPTIBLE and deal with being interrupted */
405 }
413 }
415 /* This routine calculates checksums in JFFS. */
416 static __u32
418 {
423 }
426 }
429 static int
431 {
437 /* Allocate read buffer */
442 }
443 /* Loop until checksum done */
445 /* Get amount of data to read */
448 else
451 /* Perform flash read */
455 /* Compute checksum */
459 /* Update pointer and size */
462 }
464 /* Free read buffer */
467 /* Return result */
471 }
474 {
475 // down(&fmc->wlock);
476 }
479 {
480 // up(&fmc->wlock);
481 }
484 /* Create and initialize a new struct jffs_file. */
488 {
492 GFP_KERNEL))) {
495 }
496 no_jffs_file++;
505 }
508 /* Build a control block for the file system. */
511 {
521 }
529 }
535 }
540 fail_fminit:
542 fail_hash:
546 fail_control:
550 }
553 /* Clean up all data structures associated with the file system. */
554 void
556 {
562 }
569 }
571 /* Free all files and nodes. */
577 }
582 }
585 /* This function adds a virtual root node to the in-RAM representation.
586 Called by jffs_build_fs(). */
587 static int
589 {
597 GFP_KERNEL))) {
599 }
600 no_jffs_file++;
603 no_jffs_file--;
605 }
619 }
622 /* This is where the file system is built and initialized. */
623 int
625 {
633 }
638 /* scan_flash() wants us to try once more. A flipping
639 bits sector was detect in the middle of the scan flash.
640 Clean up old allocated memory before going in.
641 */
647 }
653 }
656 }
657 }
659 /* Add a virtual root node if no one exists. */
663 }
664 }
672 }
676 }
678 /* Remove deleted nodes. */
682 }
683 /* Remove redundant nodes. (We are not interested in the
684 return value in this case.) */
686 /* Try to build a tree from all the nodes. */
690 }
691 /* Compute the sizes of all files in the filesystem. Adjust if
692 necessary. */
696 }
705 jffs_build_fs_fail:
711 /*
712 This checks for sectors that were being erased in their previous
713 lifetimes and for some reason or the other (power fail etc.),
714 the erase cycles never completed.
715 As the flash array would have reverted back to read status,
716 these sectors are detected by the symptom of the "flipping bits",
717 i.e. bits being read back differently from the same location in
718 flash if read multiple times.
719 The only solution to this is to re-erase the entire
720 sector.
721 Unfortunately detecting "flipping bits" is not a simple exercise
722 as a bit may be read back at 1 or 0 depending on the alignment
723 of the stars in the universe.
724 The level of confidence is in direct proportion to the number of
725 scans done. By power fail testing I (Vipin) have been able to
726 proove that reading twice is not enough.
727 Maybe 4 times? Change NUM_REREADS to a higher number if you want
728 a (even) higher degree of confidence in your mount process.
729 A higher number would of course slow down your mount.
730 */
735 usually set to kernel page size */
744 __u32 offset;
749 /* Allocate read buffers */
758 }
760 CHECK_NEXT:
775 /* buffers MUST match, double word for word! */
778 ){
779 /* flipping bits detected, time to erase sector */
780 /* This will help us log some statistics etc. */
788 /* calculate start of present sector */
792 offset));
805 offset));
806 /* skip ahead to the next sector */
810 }
811 }
812 }
813 }
815 }
817 returnBack:
821 D2(printk("check_partly_erased_sector():Done checking all sectors till offset 0x%x for flipping bits.\n",
830 /* Scan the whole flash memory in order to find all nodes in the
831 file systems. */
832 static int
834 {
839 __u32 checksum;
840 __u8 tmp_accurate;
841 __u16 tmp_chksum;
842 __u32 deleted_file;
844 loff_t start;
845 loff_t test_start;
849 __u32 offset;
851 __u32 free_chunk_size1;
852 __u32 free_chunk_size2;
857 free blocks found. This is NOT allowed
858 by the current jffs design.
859 */
861 of how much free space was rejected and
862 marked dirty
863 */
870 /*
871 check and make sure that any sector does not suffer
872 from the "partly erased, bit flipping syndrome" (TM Vipin :)
873 If so, offending sectors will be erased.
874 */
879 }
881 /* Allocate read buffer */
886 }
888 /* Start the scan. */
892 /* Remember the position from where we started this scan. */
897 /* We have found 0xffffffff at this position. We have to
898 scan the rest of the flash till the end or till
899 something else than 0xffffffff is found.
900 Keep going till we do not find JFFS_EMPTY_BITMASK
901 anymore */
917 JFFS_EMPTY_BITMASK)
919 }
922 else
924 }
929 /* If some free space ends in the middle of a sector,
930 treat it as dirty rather than clean.
931 This is to handle the case where one thread
932 allocated space for a node, but didn't get to
933 actually _write_ it before power was lost, leaving
934 a gap in the log. Shifting all node writes into
935 a single kernel thread will fix the original problem.
936 */
938 /* If there was free space in previous
939 sectors, don't mark that dirty too -
940 only from the beginning of this sector
941 (or from start)
942 */
948 /* free space started in the previous sector! */
953 /*
954 Count it in if we are still under NUMFREEALLOWED *and* it is
955 at least 1 erase sector in length. This will keep us from
956 picking any little ole' space as "free".
957 */
966 /* below, space from "start" to "pos" will be marked dirty. */
969 /* Being in here means that we have found at least an entire
970 erase sector size of free space ending on a sector boundary.
971 Keep track of free spaces accepted.
972 */
973 num_free_space++;
975 num_free_spc_not_accp++;
981 }
983 }
991 /* "Flipping bits" detected. This means that our scan for them
992 did not catch this offset. See check_partly_erased_sectors() for
993 more info.
994 */
1001 /* calculate start of present sector */
1005 offset));
1017 }
1022 }
1024 /* Being in here means that we have found free space that ends on an erase sector
1025 boundary.
1026 Count it in if we are still under NUMFREEALLOWED *and* it is at least 1 erase
1027 sector in length. This will keep us from picking any little ole' space as "free".
1028 */
1031 /* We really don't do anything to mark space as free, except *not*
1032 mark it dirty and just advance the "pos" location pointer.
1033 It will automatically be picked up as free space.
1034 */
1035 num_free_space++;
1039 num_free_spc_not_accp++;
1045 /* Mark this space as dirty. We already have our free space. */
1050 }
1052 }
1057 }
1061 /* We have found 0x00000000 at this position. Scan as far
1062 as possible to find out how much is dirty. */
1075 /* We have probably found a new raw inode. */
1079 bad_inode:
1080 /* We're f*cked. This is not solved yet. We have
1081 to scan for the magic pattern. */
1083 "bad inode: "
1092 /* handle these in the main switch() loop */
1097 }
1098 }
1100 cont_scan:
1101 /* First, mark as dirty the region
1102 which really does contain crap. */
1105 NULL);
1110 /* We have found the beginning of an inode. Create a
1111 node for it unless there already is one available. */
1114 /* Free read buffer */
1117 /* Release the flash device */
1121 }
1123 }
1125 /* Read the next raw inode. */
1130 /* When we compute the checksum for the inode, we never
1131 count the 'accurate' or the 'checksum' fields. */
1147 "checksum = %u, "
1153 /* Reuse this unused struct jffs_node. */
1155 }
1157 /* Check the raw inode read so far. Start with the
1158 maximum length of the filename. */
1163 }
1171 }
1173 /* The node's data segment should not exceed a
1174 certain length. */
1180 }
1184 /* This shouldn't be necessary because a node that
1185 violates the flash boundaries shouldn't be written
1186 in the first place. */
1189 }
1191 /* Read the name. */
1202 "checksum = %u, "
1207 /* Reuse this unused struct jffs_node. */
1209 }
1212 }
1213 }
1215 /* Read the data, if it exists, in order to be sure it
1216 matches the checksum. */
1220 }
1225 /* Reuse this unused struct jffs_node. */
1227 }
1233 "checksum = %u, "
1238 /* Reuse this unused struct jffs_node. */
1240 }
1241 }
1243 check_node:
1245 /* Remember the highest inode number in the whole file
1246 system. This information will be used when assigning
1247 new files new inode numbers. */
1250 }
1257 /* Compute the offset to the actual data in the
1258 on-flash node. */
1259 node->fm_offset
1265 node);
1271 /* Free read buffer */
1274 /* Release the flash device */
1278 }
1284 }
1289 GFP_KERNEL);
1295 /* Release the flash device */
1298 /* Free read buffer */
1302 }
1307 }
1310 }
1316 /* Reuse this unused struct jffs_node. */
1317 }
1318 }
1323 }
1326 /* Free read buffer */
1332 }
1334 /* Return happy */
1338 /* This is to trap the "free size accounting screwed error. */
1350 Mounting this screwed up f/s will screw us up anyway.
1351 */
1352 }
1358 /* Insert any kind of node into the file system. Take care of data
1359 insertions and deletions. Also remove redundant information. The
1360 memory allocated for the `name' is regarded as "given away" in the
1361 caller's perspective. */
1362 int
1366 {
1375 /* If there doesn't exist an associated jffs_file, then
1376 create, initialize and insert one into the file system. */
1380 }
1383 }
1391 /* Now insert the node at the correct position into the file's
1392 version list. */
1394 /* This is the first node. */
1407 }
1410 /* Insert at the end of the list. I.e. this node is the
1411 newest one so far. */
1425 }
1427 /* Insert at the bottom of the list. */
1434 }
1435 }
1439 /* Search for the insertion position starting from
1440 the tail (newest node). */
1449 }
1451 }
1454 }
1455 }
1456 }
1458 /* Deletion is irreversible. If any 'deleted' node is ever
1459 written, the file is deleted */
1463 /* Perhaps update the name. */
1468 }
1470 GFP_KERNEL))) {
1472 }
1479 }
1486 }
1487 /* Once upon a time, we would call jffs_possibly_delete_file()
1488 here. That causes an oops if someone's still got the file
1489 open, so now we only do it in jffs_delete_inode()
1490 -- dwmw2
1491 */
1494 }
1501 }
1507 /* Unlink a jffs_node from the version list it is in. */
1511 {
1516 }
1521 }
1522 }
1525 /* Unlink a jffs_node from the range list it is in. */
1528 {
1531 }
1534 }
1537 }
1540 }
1541 }
1544 /* Function used by jffs_remove_redundant_nodes() below. This function
1545 classifies what kind of information a node adds to a file. */
1548 {
1553 }
1556 }
1558 }
1561 /* Remove redundant nodes from a file. Mark the on-flash memory
1562 as dirty. */
1563 static int
1565 {
1569 __u8 newest_type;
1570 __u8 mod_type;
1575 }
1577 /* What does the `newest_node' modify? */
1583 newest_type));
1585 /* Traverse the file's nodes and determine which of them that are
1586 superfluous. Yeah, this might look very complex at first
1587 glance but it is actually very simple. */
1593 && (mod_type
1597 /* Yes, this node is redundant. Remove it. */
1599 "Removing node: ino: %u, version: %u, "
1601 mod_type));
1606 }
1609 }
1610 }
1613 }
1616 /* Insert a file into the hash table. */
1617 static int
1619 {
1626 }
1629 /* Insert a file into the file system tree. */
1630 int
1632 {
1645 }
1651 }
1652 }
1657 }
1661 }
1664 /* Remove a file from the hash table. */
1665 static int
1667 {
1673 }
1676 /* Just remove the file from the parent's children. Don't free
1677 any memory. */
1678 int
1680 {
1686 }
1690 }
1693 }
1695 }
1698 /* Find a file with its inode number. */
1701 {
1715 );
1717 }
1720 );
1722 }
1725 /* Find a file in a directory. We are comparing the names. */
1728 {
1738 }
1739 }
1743 }
1749 }
1754 }
1755 });
1758 }
1761 /* Write a raw inode that takes up a certain amount of space in the flash
1762 memory. At the end of the flash device, there is often space that is
1763 impossible to use. At these times we want to mark this space as not
1764 used. In the cases when the amount of space is greater or equal than
1765 a struct jffs_raw_inode, we write a "dummy node" that takes up this
1766 space. The space after the raw inode, if it exists, is left as it is.
1767 Since this space after the raw inode contains JFFS_EMPTY_BITMASK bytes,
1768 we can compute the checksum of it; we don't have to manipulate it any
1769 further.
1771 If the space left on the device is less than the size of a struct
1772 jffs_raw_inode, this space is filled with JFFS_DIRTY_BITMASK bytes.
1773 No raw inode is written this time. */
1774 static int
1776 {
1791 raw_inode.chksum
1802 }
1803 }
1808 }
1812 }
1815 /* Write a raw inode, possibly its name and possibly some data. */
1816 int
1822 {
1828 __u32 pos;
1839 /* If this node isn't something that will eventually let
1840 GC free even more space, then don't allow it unless
1841 there's at least max_chunk_size space still available
1842 */
1847 /* Fire the retrorockets and shoot the fruiton torpedoes, sir! */
1852 });
1857 });
1862 total_size));
1866 retry:
1871 /* Deadlocks suck. */
1877 }
1879 /* First try to allocate some flash memory. */
1883 /* Just out of space. GC and try again */
1887 total_size));
1889 }
1896 }
1899 }
1907 }
1910 /* The jffs_fm struct that we got is not good enough.
1911 Make that space dirty and try again */
1919 }
1921 }
1927 });
1931 /* Increment the version number here. We can't let the caller
1932 set it beforehand, because we might have had to do GC on a node
1933 of this file - and we'd end up reusing version numbers.
1934 */
1937 D1(printk (KERN_NOTICE "jffs_write_node(): setting version of %s to %d\n", f->name, raw_inode->version));
1939 /* if the file was deleted, set the deleted bit in the raw inode */
1942 }
1944 /* Compute the checksum for the data and name chunks. */
1948 /* The checksum is calculated without the chksum and accurate
1949 fields so set them to zero first. */
1960 /* The actual raw JFFS node */
1965 /* Get name and size if there is one */
1969 iovec_cnt++;
1973 /* Add some extra padding if necessary */
1977 iovec_cnt++;
1978 }
1979 }
1981 /* Get data and size if there is any */
1985 iovec_cnt++;
1986 /* No need to pad this because we're not actually putting
1987 anything after it.
1988 */
1989 }
1998 }
2008 /* Read data from the node and write it to the buffer. 'node_offset'
2009 is how much we have read from this particular node before and which
2010 shouldn't be read again. 'max_size' is how much space there is in
2011 the buffer. */
2012 static int
2015 {
2019 __u32 r;
2033 }
2036 /* Read data from the file's nodes. Write the data to the buffer
2037 'buf'. 'read_offset' tells how much data we should skip. */
2038 int
2040 __u32 size)
2041 {
2054 }
2056 /* First find the node to read data from. */
2063 }
2066 }
2067 }
2069 /* "Cats are living proof that not everything in nature
2070 has to be useful."
2071 - Garrison Keilor ('97) */
2073 /* Fill the buffer. */
2077 /* This node does not refer to real data. */
2081 }
2083 node_offset,
2086 }
2090 }
2093 }
2096 /* Used for traversing all nodes in the hash table. */
2097 int
2099 {
2107 /* We need a reference to the next file in the
2108 list because `func' might remove the current
2109 file `f'. */
2115 }
2116 }
2119 }
2122 /* Free all nodes associated with a file. */
2123 static int
2125 {
2137 }
2139 }
2142 /* Free a file and its name. */
2143 static int
2145 {
2152 }
2154 no_jffs_file--;
2156 }
2158 static long
2160 {
2162 }
2164 /* See if a file is deleted. If so, mark that file's nodes as obsolete. */
2165 int
2167 {
2176 });
2179 /* First try to remove all older versions. Commence with
2180 the oldest node. */
2184 }
2187 }
2188 }
2189 /* Unlink the file from the filesystem. */
2192 }
2196 }
2198 }
2201 /* Used in conjunction with jffs_foreach_file() to count the number
2202 of files in the file system. */
2203 int
2205 {
2207 }
2210 /* Build up a file's range list from scratch by going through the
2211 version list. */
2212 static int
2214 {
2222 }
2224 }
2227 /* Remove an amount of data from a file. If this amount of data is
2228 zero, that could mean that a node should be split in two parts.
2229 We remove or change the appropriate nodes in the lists.
2231 Starting offset of area to be removed is node->data_offset,
2232 and the length of the area is in node->removed_size. */
2233 static int
2235 {
2247 /* A simple append; nothing to remove or no node to split. */
2249 }
2251 /* Find the node where we should begin the removal. */
2255 }
2256 }
2258 /* If there's no data in the file there's no data to
2259 remove either. */
2261 }
2264 /* XXX: Not implemented yet. */
2267 }
2269 /* See if the node has to be split into two parts. */
2271 /* Do the split. */
2279 }
2294 }
2297 }
2303 }
2306 }
2307 /* A very interesting can of worms. */
2315 }
2318 }
2320 /* No. No need to split the node. Just remove
2321 the end of the node. */
2327 }
2328 }
2330 /* Remove as many nodes as necessary. */
2342 }
2347 }
2354 }
2355 }
2357 /* Adjust the following nodes' information about offsets etc. */
2361 }
2364 /* It's possible that the removed_size is in fact
2365 * greater than the amount of data we actually thought
2366 * were present in the first place - some of the nodes
2367 * which this node originally obsoleted may already have
2368 * been deleted from the flash by subsequent garbage
2369 * collection.
2370 *
2371 * If this is the case, don't let f->size go negative.
2372 * Bad things would happen :)
2373 */
2377 }
2383 /* Insert some data into a file. Prior to the call to this function,
2384 jffs_delete_data should be called. */
2385 static int
2387 {
2392 /* Find the position where we should insert data. */
2393 retry:
2395 /* A simple append. This is the most common operation. */
2400 }
2405 }
2406 }
2408 /* Trying to insert data into the middle of the file. This
2409 means no problem because jffs_delete_data() has already
2410 prepared the range list for us. */
2413 /* Find the correct place for the insertion and then insert
2414 the node. */
2422 }
2425 }
2429 }
2433 "Couldn't find a place to insert "
2436 });
2437 }
2439 /* Adjust later nodes' offsets etc. */
2444 }
2446 }
2448 /* Okay. This is tricky. This means that we want to insert
2449 data at a place that is beyond the limits of the file as
2450 it is constructed right now. This is actually a common
2451 event that for instance could occur during the mounting
2452 of the file system if a large file have been truncated,
2453 rewritten and then only partially garbage collected. */
2457 /* We need a place holder for the data that is missing in
2458 front of this insertion. This "virtual node" will not
2459 be associated with any space on the flash device. */
2463 }
2479 /* Are there any data at all in the file yet? */
2481 virtual_node->data_offset
2484 virtual_node->data_size
2488 }
2494 }
2499 /* Insert this virtual node in the version list as well. */
2505 virtual_node->version_prev
2507 }
2510 }
2513 }
2514 }
2518 /* Make a new try to insert the node. */
2520 }
2524 }
2527 /* A new node (with data) has been added to the file and now the range
2528 list has to be modified. */
2529 static int
2531 {
2539 /* data_offset == X */
2540 /* data_size == 0 */
2541 /* remove_size == 0 */
2542 }
2544 /* data_offset == X */
2545 /* data_size == 0 */
2546 /* remove_size != 0 */
2549 }
2550 }
2551 }
2553 /* data_offset == X */
2554 /* data_size != 0 */
2555 /* remove_size == Y */
2558 }
2561 }
2562 }
2564 }
2566 /* Print the contents of a file. */
2567 #if 0
2568 int
2570 {
2588 });
2606 }
2609 void
2611 {
2623 }
2624 }
2625 }
2628 void
2630 {
2637 }
2642 }
2654 }
2655 }
2658 }
2661 #if defined(JFFS_MEMORY_DEBUG) && JFFS_MEMORY_DEBUG
2662 void
2664 {
2677 }
2678 #endif
2681 /* Rewrite `size' bytes, and begin at `node'. */
2682 static int
2684 {
2690 __u32 pos;
2691 __u32 pos_dchksum;
2692 __u32 total_name_size;
2693 __u32 total_data_size;
2694 __u32 total_size;
2700 /* Create and initialize the new node. */
2705 }
2716 retry:
2726 }
2728 /* The jffs_fm struct that we got is not big enough. */
2729 /* This should never happen, because we deal with this case
2730 in jffs_garbage_collect_next().*/
2731 printk(KERN_WARNING "jffs_rewrite_data(): Allocated node is too small (%d bytes of %d)\n", fm->size, total_size);
2737 }
2743 }
2746 /* Initialize the raw inode. */
2789 }
2792 /* Write the name to the flash memory. */
2806 }
2809 }
2811 /* Write the data. */
2820 }
2830 "jffs_read_data() "
2833 }
2840 "Write error during rewrite. "
2843 }
2848 }
2851 }
2858 /* Add the checksum. */
2870 }
2872 /* Now make the file system aware of the newly written node. */
2881 /* jffs_garbage_collect_next implements one step in the garbage collect
2882 process and is often called multiple times at each occasion of a
2883 garbage collect. */
2885 static int
2887 {
2892 __u32 size;
2893 __u32 data_size;
2894 __u32 total_name_size;
2895 __u32 extra_available;
2896 __u32 space_needed;
2900 /* Get the oldest node in the flash. */
2909 });
2911 /* Find its corresponding file too. */
2916 "No file to garbage collect! "
2918 /* FIXME: Free the offending node and recover. */
2921 }
2923 /* We always write out the name. Theoretically, we don't need
2924 to, but for now it's easier - because otherwise we'd have
2925 to keep track of how many times the current name exists on
2926 the flash and make sure it never reaches zero.
2928 The current approach means that would be possible to cause
2929 the GC to end up eating its tail by writing lots of nodes
2930 with no name for it to garbage-collect. Hence the change in
2931 inode.c to write names with _every_ node.
2933 It sucks, but it _should_ work.
2934 */
2942 /* Compute how many data it's possible to rewrite at the moment. */
2945 /* And from that, the total size of the chunk we want to write */
2949 /* If that's more than max_chunk_size, reduce it accordingly */
2954 }
2956 /* If we're asking to take up more space than free_chunk_size1
2957 but we _could_ fit in it, shrink accordingly.
2958 */
2963 /* The space left is too small to be of any
2964 use really. */
2971 "jffs_garbage_collect_next: "
2972 "Failed to allocate `dirty' "
2976 }
2981 }
2989 }
2992 /* Calculate the amount of space needed to hold the nodes
2993 which are remaining in the tail */
2996 /* From that, calculate how much 'extra' space we can use to
2997 increase the size of the node we're writing from the size
2998 of the node we're obsoleting
2999 */
3001 /* If we've gone below min_free_size for some reason,
3002 don't fuck up. This is why we have
3003 min_free_size > sector_size. Whinge about it though,
3004 just so I can convince myself my maths is right.
3005 */
3012 }
3014 /* Check that we don't use up any more 'extra' space than
3015 what's available */
3029 };
3044 }
3046 jffs_garbage_collect_next_end:
3052 /* If an obsolete node is partly going to be erased due to garbage
3053 collection, the part that isn't going to be erased must be filled
3054 with zeroes so that the scan of the flash will work smoothly next
3055 time. (The data in the file could for instance be a JFFS image
3056 which could cause enormous confusion during a scan of the flash
3057 device if we didn't do this.)
3058 There are two phases in this procedure: First, the clearing of
3059 the name and data parts of the node. Second, possibly also clearing
3060 a part of the raw inode as well. If the box is power cycled during
3061 the first phase, only the checksum of this node-to-be-cleared-at-
3062 the-end will be wrong. If the box is power cycled during, or after,
3063 the clearing of the raw inode, the information like the length of
3064 the name and data parts are zeroed. The next time the box is
3065 powered up, the scanning algorithm manages this faulty data too
3066 because:
3068 - The checksum is invalid and thus the raw inode must be discarded
3069 in any case.
3070 - If the lengths of the data part or the name part are zeroed, the
3071 scanning just continues after the raw inode. But after the inode
3072 the scanning procedure just finds zeroes which is the same as
3073 dirt.
3075 So, in the end, this could never fail. :-) Even if it does fail,
3076 the scanning algorithm should manage that too. */
3078 static int
3080 {
3083 __u32 zero_offset;
3084 __u32 zero_size;
3085 __u32 zero_offset_data;
3086 __u32 zero_size_data;
3092 }
3094 /* Where and how much shall we clear? */
3098 /* Do we have to clear the raw_inode explicitly? */
3102 }
3104 /* First, clear the name and data fields. */
3111 /* Should we clear a part of the raw inode? */
3113 /* I guess it is ok to clear the raw inode in this order. */
3116 cutting_raw_inode);
3118 }
3123 /* Try to erase as much as possible of the dirt in the flash memory. */
3124 static long
3126 {
3130 __u32 offset;
3140 }
3145 }
3151 }
3155 /* Now, let's try to do the erase. */
3161 /* XXX: Here we should allocate this area as dirty
3162 with jffs_fmalloced or something similar. Now
3163 we just report the error. */
3165 }
3167 #if 0
3168 /* Check if the erased sectors really got erased. */
3169 {
3170 __u32 pos;
3171 __u32 end;
3188 }
3189 }
3195 }
3197 /* XXX: Here we should allocate the memory
3198 with jffs_fmalloced() in order to prevent
3199 JFFS from using this area accidentally. */
3201 }
3202 }
3203 #endif
3205 /* Update the flash memory data structures. */
3209 }
3212 /* There are different criteria that should trigger a garbage collect:
3214 1. There is too much dirt in the memory.
3215 2. The free space is becoming small.
3216 3. There are many versions of a node.
3218 The garbage collect should always be done in a manner that guarantees
3219 that future garbage collects cannot be locked. E.g. Rewritten chunks
3220 should not be too large (span more than one sector in the flash memory
3221 for exemple). Of course there is a limit on how intelligent this garbage
3222 collection can be. */
3225 static int
3227 {
3232 D2(printk("***jffs_garbage_collect_now(): fmc->dirty_size = %u, fmc->free_size = 0x%x\n, fcs1=0x%x, fcs2=0x%x",
3236 // down(&fmc->gclock);
3238 /* If it is possible to garbage collect, do so. */
3250 }
3255 /* Argh */
3259 }
3262 /* Actually, we _may_ have been able to free some,
3263 * if there are many overlapping nodes which aren't
3264 * actually marked dirty because they still have
3265 * some valid data in each.
3266 */
3269 }
3271 /* Let's dare to make a garbage collect. */
3274 "has gone seriously wrong "
3277 }
3281 }
3283 gc_end:
3284 // up(&fmc->gclock);
3290 });
3299 /* Determine if it is reasonable to start garbage collection.
3300 We start a gc pass if either:
3301 - The number of free bytes < MIN_FREE_BYTES && at least one
3302 block is dirty, OR
3303 - The number of dirty bytes > MAX_DIRTY_BYTES
3304 */
3306 {
3310 /* If there's not enough dirty space to free a block, there's no point. */
3314 }
3315 #if 1
3316 /* If there is too much RAM used by the various structures, GC */
3317 if (jffs_get_node_inuse() > (c->fmc->used_size/c->fmc->max_chunk_size * 5 + jffs_get_file_count() * 2 + 50)) {
3318 /* FIXME: Provide proof that this test can be satisfied. We
3319 don't want a filesystem doing endless GC just because this
3320 condition cannot ever be false.
3321 */
3324 }
3325 #endif
3326 /* If there are fewer free bytes than the threshold, GC */
3330 }
3331 /* If there are more dirty bytes than the threshold, GC */
3335 }
3336 /* FIXME: What about the "There are many versions of a node" condition? */
3339 }
3343 {
3344 /* NOTE: We rely on the fact that we have the BKL here.
3345 * Otherwise, the gc_task could go away between the check
3346 * and the wake_up_process()
3347 */
3350 }
3353 /* Kernel threads take (void *) as arguments. Thus we pass
3354 the jffs_control data as a (void *) and then cast it. */
3355 int
3357 {
3371 siginitsetinv (¤t->blocked, sigmask(SIGHUP) | sigmask(SIGKILL) | sigmask(SIGSTOP) | sigmask(SIGCONT));
3379 /* See if we need to start gc. If we don't, go to sleep.
3381 Current implementation is a BAD THING(tm). If we try
3382 to unmount the FS, the unmount operation will sleep waiting
3383 for this thread to exit. We need to arrange to send it a
3384 sig before the umount process sleeps.
3385 */
3391 on immediately - we're a low priority
3392 background task. */
3394 /* Put_super will send a SIGKILL and then wait on the sem.
3395 */
3397 siginfo_t info;
3418 }
3419 }
3434 }
3440 /* Argh. Might as well commit suicide. */
3443 // panic()
3445 }
3447 /* Let's dare to make a garbage collect. */
3450 "has gone seriously wrong "
3452 }
3454 gc_end: