Merge git://git.skbuff.net/gitroot/yoshfuji/linux-2.6.14+advapi-fix/
[linux-2.6] / fs / jffs / intrep.c
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  */
19
20 /* This file contains the code for the internal structure of the
21    Journaling Flash File System, JFFS.  */
22
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  */
57
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>
70
71 #include "intrep.h"
72 #include "jffs_fm.h"
73
74 long no_jffs_node = 0;
75 static long no_jffs_file = 0;
76 #if defined(JFFS_MEMORY_DEBUG) && JFFS_MEMORY_DEBUG
77 long no_jffs_control = 0;
78 long no_jffs_raw_inode = 0;
79 long no_jffs_node_ref = 0;
80 long no_jffs_fm = 0;
81 long no_jffs_fmcontrol = 0;
82 long no_hash = 0;
83 long no_name = 0;
84 #endif
85
86 static int jffs_scan_flash(struct jffs_control *c);
87 static int jffs_update_file(struct jffs_file *f, struct jffs_node *node);
88 static int jffs_build_file(struct jffs_file *f);
89 static int jffs_free_file(struct jffs_file *f);
90 static int jffs_free_node_list(struct jffs_file *f);
91 static int jffs_garbage_collect_now(struct jffs_control *c);
92 static int jffs_insert_file_into_hash(struct jffs_file *f);
93 static int jffs_remove_redundant_nodes(struct jffs_file *f);
94
95 /* Is there enough space on the flash?  */
96 static inline int JFFS_ENOUGH_SPACE(struct jffs_control *c, __u32 space)
97 {
98         struct jffs_fmcontrol *fmc = c->fmc;
99
100         while (1) {
101                 if ((fmc->flash_size - (fmc->used_size + fmc->dirty_size))
102                         >= fmc->min_free_size + space) {
103                         return 1;
104                 }
105                 if (fmc->dirty_size < fmc->sector_size)
106                         return 0;
107
108                 if (jffs_garbage_collect_now(c)) {
109                   D1(printk("JFFS_ENOUGH_SPACE: jffs_garbage_collect_now() failed.\n"));
110                   return 0;
111                 }
112         }
113 }
114
115 #if CONFIG_JFFS_FS_VERBOSE > 0
116 static __u8
117 flash_read_u8(struct mtd_info *mtd, loff_t from)
118 {
119         size_t retlen;
120         __u8 ret;
121         int res;
122
123         res = MTD_READ(mtd, from, 1, &retlen, &ret);
124         if (retlen != 1) {
125                 printk("Didn't read a byte in flash_read_u8(). Returned %d\n", res);
126                 return 0;
127         }
128
129         return ret;
130 }
131
132 static void
133 jffs_hexdump(struct mtd_info *mtd, loff_t pos, int size)
134 {
135         char line[16];
136         int j = 0;
137
138         while (size > 0) {
139                 int i;
140
141                 printk("%ld:", (long) pos);
142                 for (j = 0; j < 16; j++) {
143                         line[j] = flash_read_u8(mtd, pos++);
144                 }
145                 for (i = 0; i < j; i++) {
146                         if (!(i & 1)) {
147                                 printk(" %.2x", line[i] & 0xff);
148                         }
149                         else {
150                                 printk("%.2x", line[i] & 0xff);
151                         }
152                 }
153
154                 /* Print empty space */
155                 for (; i < 16; i++) {
156                         if (!(i & 1)) {
157                                 printk("   ");
158                         }
159                         else {
160                                 printk("  ");
161                         }
162                 }
163                 printk("  ");
164
165                 for (i = 0; i < j; i++) {
166                         if (isgraph(line[i])) {
167                                 printk("%c", line[i]);
168                         }
169                         else {
170                                 printk(".");
171                         }
172                 }
173                 printk("\n");
174                 size -= 16;
175         }
176 }
177
178 /* Print the contents of a node.  */
179 static void
180 jffs_print_node(struct jffs_node *n)
181 {
182         D(printk("jffs_node: 0x%p\n", n));
183         D(printk("{\n"));
184         D(printk("        0x%08x, /* version  */\n", n->version));
185         D(printk("        0x%08x, /* data_offset  */\n", n->data_offset));
186         D(printk("        0x%08x, /* data_size  */\n", n->data_size));
187         D(printk("        0x%08x, /* removed_size  */\n", n->removed_size));
188         D(printk("        0x%08x, /* fm_offset  */\n", n->fm_offset));
189         D(printk("        0x%02x,       /* name_size  */\n", n->name_size));
190         D(printk("        0x%p, /* fm,  fm->offset: %u  */\n",
191                  n->fm, (n->fm ? n->fm->offset : 0)));
192         D(printk("        0x%p, /* version_prev  */\n", n->version_prev));
193         D(printk("        0x%p, /* version_next  */\n", n->version_next));
194         D(printk("        0x%p, /* range_prev  */\n", n->range_prev));
195         D(printk("        0x%p, /* range_next  */\n", n->range_next));
196         D(printk("}\n"));
197 }
198
199 #endif
200
201 /* Print the contents of a raw inode.  */
202 static void
203 jffs_print_raw_inode(struct jffs_raw_inode *raw_inode)
204 {
205         D(printk("jffs_raw_inode: inode number: %u\n", raw_inode->ino));
206         D(printk("{\n"));
207         D(printk("        0x%08x, /* magic  */\n", raw_inode->magic));
208         D(printk("        0x%08x, /* ino  */\n", raw_inode->ino));
209         D(printk("        0x%08x, /* pino  */\n", raw_inode->pino));
210         D(printk("        0x%08x, /* version  */\n", raw_inode->version));
211         D(printk("        0x%08x, /* mode  */\n", raw_inode->mode));
212         D(printk("        0x%04x,     /* uid  */\n", raw_inode->uid));
213         D(printk("        0x%04x,     /* gid  */\n", raw_inode->gid));
214         D(printk("        0x%08x, /* atime  */\n", raw_inode->atime));
215         D(printk("        0x%08x, /* mtime  */\n", raw_inode->mtime));
216         D(printk("        0x%08x, /* ctime  */\n", raw_inode->ctime));
217         D(printk("        0x%08x, /* offset  */\n", raw_inode->offset));
218         D(printk("        0x%08x, /* dsize  */\n", raw_inode->dsize));
219         D(printk("        0x%08x, /* rsize  */\n", raw_inode->rsize));
220         D(printk("        0x%02x,       /* nsize  */\n", raw_inode->nsize));
221         D(printk("        0x%02x,       /* nlink  */\n", raw_inode->nlink));
222         D(printk("        0x%02x,       /* spare  */\n",
223                  raw_inode->spare));
224         D(printk("        %u,          /* rename  */\n",
225                  raw_inode->rename));
226         D(printk("        %u,          /* deleted  */\n",
227                  raw_inode->deleted));
228         D(printk("        0x%02x,       /* accurate  */\n",
229                  raw_inode->accurate));
230         D(printk("        0x%08x, /* dchksum  */\n", raw_inode->dchksum));
231         D(printk("        0x%04x,     /* nchksum  */\n", raw_inode->nchksum));
232         D(printk("        0x%04x,     /* chksum  */\n", raw_inode->chksum));
233         D(printk("}\n"));
234 }
235
236 #define flash_safe_acquire(arg)
237 #define flash_safe_release(arg)
238
239
240 static int
241 flash_safe_read(struct mtd_info *mtd, loff_t from,
242                 u_char *buf, size_t count)
243 {
244         size_t retlen;
245         int res;
246
247         D3(printk(KERN_NOTICE "flash_safe_read(%p, %08x, %p, %08x)\n",
248                   mtd, (unsigned int) from, buf, count));
249
250         res = MTD_READ(mtd, from, count, &retlen, buf);
251         if (retlen != count) {
252                 panic("Didn't read all bytes in flash_safe_read(). Returned %d\n", res);
253         }
254         return res?res:retlen;
255 }
256
257
258 static __u32
259 flash_read_u32(struct mtd_info *mtd, loff_t from)
260 {
261         size_t retlen;
262         __u32 ret;
263         int res;
264
265         res = MTD_READ(mtd, from, 4, &retlen, (unsigned char *)&ret);
266         if (retlen != 4) {
267                 printk("Didn't read all bytes in flash_read_u32(). Returned %d\n", res);
268                 return 0;
269         }
270
271         return ret;
272 }
273
274
275 static int
276 flash_safe_write(struct mtd_info *mtd, loff_t to,
277                  const u_char *buf, size_t count)
278 {
279         size_t retlen;
280         int res;
281
282         D3(printk(KERN_NOTICE "flash_safe_write(%p, %08x, %p, %08x)\n",
283                   mtd, (unsigned int) to, buf, count));
284
285         res = MTD_WRITE(mtd, to, count, &retlen, buf);
286         if (retlen != count) {
287                 printk("Didn't write all bytes in flash_safe_write(). Returned %d\n", res);
288         }
289         return res?res:retlen;
290 }
291
292
293 static int
294 flash_safe_writev(struct mtd_info *mtd, const struct kvec *vecs,
295                         unsigned long iovec_cnt, loff_t to)
296 {
297         size_t retlen, retlen_a;
298         int i;
299         int res;
300
301         D3(printk(KERN_NOTICE "flash_safe_writev(%p, %08x, %p)\n",
302                   mtd, (unsigned int) to, vecs));
303         
304         if (mtd->writev) {
305                 res = MTD_WRITEV(mtd, vecs, iovec_cnt, to, &retlen);
306                 return res ? res : retlen;
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. */
311         res=0;
312         retlen=0;
313
314         for (i=0; !res && i<iovec_cnt; i++) {
315                 res = MTD_WRITE(mtd, to, vecs[i].iov_len, &retlen_a, vecs[i].iov_base);
316                 if (retlen_a != vecs[i].iov_len) {
317                         printk("Didn't write all bytes in flash_safe_writev(). Returned %d\n", res);
318                         if (i != iovec_cnt-1)
319                                 return -EIO;
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                 */
325                 to += retlen_a;
326                 retlen += retlen_a;
327         }
328         return res?res:retlen;
329 }
330
331
332 static int
333 flash_memset(struct mtd_info *mtd, loff_t to,
334              const u_char c, size_t size)
335 {
336         static unsigned char pattern[64];
337         int i;
338
339         /* fill up pattern */
340
341         for(i = 0; i < 64; i++)
342                 pattern[i] = c;
343
344         /* write as many 64-byte chunks as we can */
345
346         while (size >= 64) {
347                 flash_safe_write(mtd, to, pattern, 64);
348                 size -= 64;
349                 to += 64;
350         }
351
352         /* and the rest */
353
354         if(size)
355                 flash_safe_write(mtd, to, pattern, size);
356
357         return size;
358 }
359
360
361 static void
362 intrep_erase_callback(struct erase_info *done)
363 {
364         wait_queue_head_t *wait_q;
365
366         wait_q = (wait_queue_head_t *)done->priv;
367
368         wake_up(wait_q);
369 }
370
371
372 static int
373 flash_erase_region(struct mtd_info *mtd, loff_t start,
374                    size_t size)
375 {
376         struct erase_info *erase;
377         DECLARE_WAITQUEUE(wait, current);
378         wait_queue_head_t wait_q;
379
380         erase = kmalloc(sizeof(struct erase_info), GFP_KERNEL);
381         if (!erase)
382                 return -ENOMEM;
383
384         init_waitqueue_head(&wait_q);
385
386         erase->mtd = mtd;
387         erase->callback = intrep_erase_callback;
388         erase->addr = start;
389         erase->len = size;
390         erase->priv = (u_long)&wait_q;
391
392         /* FIXME: Use TASK_INTERRUPTIBLE and deal with being interrupted */
393         set_current_state(TASK_UNINTERRUPTIBLE);
394         add_wait_queue(&wait_q, &wait);
395
396         if (MTD_ERASE(mtd, erase) < 0) {
397                 set_current_state(TASK_RUNNING);
398                 remove_wait_queue(&wait_q, &wait);
399                 kfree(erase);
400
401                 printk(KERN_WARNING "flash: erase of region [0x%lx, 0x%lx] "
402                        "totally failed\n", (long)start, (long)start + size);
403
404                 return -1;
405         }
406
407         schedule(); /* Wait for flash to finish. */
408         remove_wait_queue(&wait_q, &wait);
409
410         kfree(erase);
411
412         return 0;
413 }
414
415 /* This routine calculates checksums in JFFS.  */
416 static __u32
417 jffs_checksum(const void *data, int size)
418 {
419         __u32 sum = 0;
420         __u8 *ptr = (__u8 *)data;
421         while (size-- > 0) {
422                 sum += *ptr++;
423         }
424         D3(printk(", result: 0x%08x\n", sum));
425         return sum;
426 }
427
428
429 static int
430 jffs_checksum_flash(struct mtd_info *mtd, loff_t start, int size, __u32 *result)
431 {
432         __u32 sum = 0;
433         loff_t ptr = start;
434         __u8 *read_buf;
435         int i, length;
436
437         /* Allocate read buffer */
438         read_buf = (__u8 *) kmalloc (sizeof(__u8) * 4096, GFP_KERNEL);
439         if (!read_buf) {
440                 printk(KERN_NOTICE "kmalloc failed in jffs_checksum_flash()\n");
441                 return -ENOMEM;
442         }
443         /* Loop until checksum done */
444         while (size) {
445                 /* Get amount of data to read */
446                 if (size < 4096)
447                         length = size;
448                 else
449                         length = 4096;
450
451                 /* Perform flash read */
452                 D3(printk(KERN_NOTICE "jffs_checksum_flash\n"));
453                 flash_safe_read(mtd, ptr, &read_buf[0], length);
454
455                 /* Compute checksum */
456                 for (i=0; i < length ; i++)
457                         sum += read_buf[i];
458
459                 /* Update pointer and size */
460                 size -= length;
461                 ptr += length;
462         }
463
464         /* Free read buffer */
465         kfree(read_buf);
466
467         /* Return result */
468         D3(printk("checksum result: 0x%08x\n", sum));
469         *result = sum;
470         return 0;
471 }
472
473 static __inline__ void jffs_fm_write_lock(struct jffs_fmcontrol *fmc)
474 {
475   //    down(&fmc->wlock);
476 }
477
478 static __inline__ void jffs_fm_write_unlock(struct jffs_fmcontrol *fmc)
479 {
480   //    up(&fmc->wlock);
481 }
482
483
484 /* Create and initialize a new struct jffs_file.  */
485 static struct jffs_file *
486 jffs_create_file(struct jffs_control *c,
487                  const struct jffs_raw_inode *raw_inode)
488 {
489         struct jffs_file *f;
490
491         if (!(f = (struct jffs_file *)kmalloc(sizeof(struct jffs_file),
492                                               GFP_KERNEL))) {
493                 D(printk("jffs_create_file(): Failed!\n"));
494                 return NULL;
495         }
496         no_jffs_file++;
497         memset(f, 0, sizeof(struct jffs_file));
498         f->ino = raw_inode->ino;
499         f->pino = raw_inode->pino;
500         f->nlink = raw_inode->nlink;
501         f->deleted = raw_inode->deleted;
502         f->c = c;
503
504         return f;
505 }
506
507
508 /* Build a control block for the file system.  */
509 static struct jffs_control *
510 jffs_create_control(struct super_block *sb)
511 {
512         struct jffs_control *c;
513         register int s = sizeof(struct jffs_control);
514         int i;
515         D(char *t = 0);
516
517         D2(printk("jffs_create_control()\n"));
518
519         if (!(c = (struct jffs_control *)kmalloc(s, GFP_KERNEL))) {
520                 goto fail_control;
521         }
522         DJM(no_jffs_control++);
523         c->root = NULL;
524         c->gc_task = NULL;
525         c->hash_len = JFFS_HASH_SIZE;
526         s = sizeof(struct list_head) * c->hash_len;
527         if (!(c->hash = (struct list_head *)kmalloc(s, GFP_KERNEL))) {
528                 goto fail_hash;
529         }
530         DJM(no_hash++);
531         for (i = 0; i < c->hash_len; i++)
532                 INIT_LIST_HEAD(&c->hash[i]);
533         if (!(c->fmc = jffs_build_begin(c, MINOR(sb->s_dev)))) {
534                 goto fail_fminit;
535         }
536         c->next_ino = JFFS_MIN_INO + 1;
537         c->delete_list = (struct jffs_delete_list *) 0;
538         return c;
539
540 fail_fminit:
541         D(t = "c->fmc");
542 fail_hash:
543         kfree(c);
544         DJM(no_jffs_control--);
545         D(t = t ? t : "c->hash");
546 fail_control:
547         D(t = t ? t : "control");
548         D(printk("jffs_create_control(): Allocation failed: (%s)\n", t));
549         return (struct jffs_control *)0;
550 }
551
552
553 /* Clean up all data structures associated with the file system.  */
554 void
555 jffs_cleanup_control(struct jffs_control *c)
556 {
557         D2(printk("jffs_cleanup_control()\n"));
558
559         if (!c) {
560                 D(printk("jffs_cleanup_control(): c == NULL !!!\n"));
561                 return;
562         }
563
564         while (c->delete_list) {
565                 struct jffs_delete_list *delete_list_element;
566                 delete_list_element = c->delete_list;
567                 c->delete_list = c->delete_list->next;
568                 kfree(delete_list_element);
569         }
570
571         /* Free all files and nodes.  */
572         if (c->hash) {
573                 jffs_foreach_file(c, jffs_free_node_list);
574                 jffs_foreach_file(c, jffs_free_file);
575                 kfree(c->hash);
576                 DJM(no_hash--);
577         }
578         jffs_cleanup_fmcontrol(c->fmc);
579         kfree(c);
580         DJM(no_jffs_control--);
581         D3(printk("jffs_cleanup_control(): Leaving...\n"));
582 }
583
584
585 /* This function adds a virtual root node to the in-RAM representation.
586    Called by jffs_build_fs().  */
587 static int
588 jffs_add_virtual_root(struct jffs_control *c)
589 {
590         struct jffs_file *root;
591         struct jffs_node *node;
592
593         D2(printk("jffs_add_virtual_root(): "
594                   "Creating a virtual root directory.\n"));
595
596         if (!(root = (struct jffs_file *)kmalloc(sizeof(struct jffs_file),
597                                                  GFP_KERNEL))) {
598                 return -ENOMEM;
599         }
600         no_jffs_file++;
601         if (!(node = jffs_alloc_node())) {
602                 kfree(root);
603                 no_jffs_file--;
604                 return -ENOMEM;
605         }
606         DJM(no_jffs_node++);
607         memset(node, 0, sizeof(struct jffs_node));
608         node->ino = JFFS_MIN_INO;
609         memset(root, 0, sizeof(struct jffs_file));
610         root->ino = JFFS_MIN_INO;
611         root->mode = S_IFDIR | S_IRWXU | S_IRGRP
612                      | S_IXGRP | S_IROTH | S_IXOTH;
613         root->atime = root->mtime = root->ctime = get_seconds();
614         root->nlink = 1;
615         root->c = c;
616         root->version_head = root->version_tail = node;
617         jffs_insert_file_into_hash(root);
618         return 0;
619 }
620
621
622 /* This is where the file system is built and initialized.  */
623 int
624 jffs_build_fs(struct super_block *sb)
625 {
626         struct jffs_control *c;
627         int err = 0;
628
629         D2(printk("jffs_build_fs()\n"));
630
631         if (!(c = jffs_create_control(sb))) {
632                 return -ENOMEM;
633         }
634         c->building_fs = 1;
635         c->sb = sb;
636         if ((err = jffs_scan_flash(c)) < 0) {
637                 if(err == -EAGAIN){
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                         */
642                         D1(printk("jffs_build_fs: Cleaning up all control structures,"
643                                   " reallocating them and trying mount again.\n"));
644                         jffs_cleanup_control(c);
645                         if (!(c = jffs_create_control(sb))) {
646                                 return -ENOMEM;
647                         }
648                         c->building_fs = 1;
649                         c->sb = sb;
650
651                         if ((err = jffs_scan_flash(c)) < 0) {
652                                 goto jffs_build_fs_fail;
653                         }                       
654                 }else{
655                         goto jffs_build_fs_fail;
656                 }
657         }
658
659         /* Add a virtual root node if no one exists.  */
660         if (!jffs_find_file(c, JFFS_MIN_INO)) {
661                 if ((err = jffs_add_virtual_root(c)) < 0) {
662                         goto jffs_build_fs_fail;
663                 }
664         }
665
666         while (c->delete_list) {
667                 struct jffs_file *f;
668                 struct jffs_delete_list *delete_list_element;
669
670                 if ((f = jffs_find_file(c, c->delete_list->ino))) {
671                         f->deleted = 1;
672                 }
673                 delete_list_element = c->delete_list;
674                 c->delete_list = c->delete_list->next;
675                 kfree(delete_list_element);
676         }
677
678         /* Remove deleted nodes.  */
679         if ((err = jffs_foreach_file(c, jffs_possibly_delete_file)) < 0) {
680                 printk(KERN_ERR "JFFS: Failed to remove deleted nodes.\n");
681                 goto jffs_build_fs_fail;
682         }
683         /* Remove redundant nodes.  (We are not interested in the
684            return value in this case.)  */
685         jffs_foreach_file(c, jffs_remove_redundant_nodes);
686         /* Try to build a tree from all the nodes.  */
687         if ((err = jffs_foreach_file(c, jffs_insert_file_into_tree)) < 0) {
688                 printk("JFFS: Failed to build tree.\n");
689                 goto jffs_build_fs_fail;
690         }
691         /* Compute the sizes of all files in the filesystem.  Adjust if
692            necessary.  */
693         if ((err = jffs_foreach_file(c, jffs_build_file)) < 0) {
694                 printk("JFFS: Failed to build file system.\n");
695                 goto jffs_build_fs_fail;
696         }
697         sb->s_fs_info = (void *)c;
698         c->building_fs = 0;
699
700         D1(jffs_print_hash_table(c));
701         D1(jffs_print_tree(c->root, 0));
702
703         return 0;
704
705 jffs_build_fs_fail:
706         jffs_cleanup_control(c);
707         return err;
708 } /* jffs_build_fs()  */
709
710
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 */
731 static int check_partly_erased_sectors(struct jffs_fmcontrol *fmc){
732
733 #define NUM_REREADS             4 /* see note above */
734 #define READ_AHEAD_BYTES        4096 /* must be a multiple of 4, 
735                                         usually set to kernel page size */
736
737         __u8 *read_buf1;
738         __u8 *read_buf2;
739
740         int err = 0;
741         int retlen;
742         int i;
743         int cnt;
744         __u32 offset;
745         loff_t pos = 0;
746         loff_t end = fmc->flash_size;
747
748
749         /* Allocate read buffers */
750         read_buf1 = (__u8 *) kmalloc (sizeof(__u8) * READ_AHEAD_BYTES, GFP_KERNEL);
751         if (!read_buf1)
752                 return -ENOMEM;
753
754         read_buf2 = (__u8 *) kmalloc (sizeof(__u8) * READ_AHEAD_BYTES, GFP_KERNEL);
755         if (!read_buf2) {
756                 kfree(read_buf1);
757                 return -ENOMEM;
758         }
759
760  CHECK_NEXT:
761         while(pos < end){
762                 
763                 D1(printk("check_partly_erased_sector():checking sector which contains"
764                           " offset 0x%x for flipping bits..\n", (__u32)pos));
765                 
766                 retlen = flash_safe_read(fmc->mtd, pos,
767                                          &read_buf1[0], READ_AHEAD_BYTES);
768                 retlen &= ~3;
769                 
770                 for(cnt = 0; cnt < NUM_REREADS; cnt++){
771                         (void)flash_safe_read(fmc->mtd, pos,
772                                               &read_buf2[0], READ_AHEAD_BYTES);
773                         
774                         for (i=0 ; i < retlen ; i+=4) {
775                                 /* buffers MUST match, double word for word! */
776                                 if(*((__u32 *) &read_buf1[i]) !=
777                                    *((__u32 *) &read_buf2[i])
778                                    ){
779                                         /* flipping bits detected, time to erase sector */
780                                         /* This will help us log some statistics etc. */
781                                         D1(printk("Flipping bits detected in re-read round:%i of %i\n",
782                                                cnt, NUM_REREADS));
783                                         D1(printk("check_partly_erased_sectors:flipping bits detected"
784                                                   " @offset:0x%x(0x%x!=0x%x)\n",
785                                                   (__u32)pos+i, *((__u32 *) &read_buf1[i]), 
786                                                   *((__u32 *) &read_buf2[i])));
787                                         
788                                         /* calculate start of present sector */
789                                         offset = (((__u32)pos+i)/(__u32)fmc->sector_size) * (__u32)fmc->sector_size;
790                                         
791                                         D1(printk("check_partly_erased_sector():erasing sector starting 0x%x.\n",
792                                                   offset));
793                                         
794                                         if (flash_erase_region(fmc->mtd,
795                                                                offset, fmc->sector_size) < 0) {
796                                                 printk(KERN_ERR "JFFS: Erase of flash failed. "
797                                                        "offset = %u, erase_size = %d\n",
798                                                        offset , fmc->sector_size);
799                                                 
800                                                 err = -EIO;
801                                                 goto returnBack;
802
803                                         }else{
804                                                 D1(printk("JFFS: Erase of flash sector @0x%x successful.\n",
805                                                        offset));
806                                                 /* skip ahead to the next sector */
807                                                 pos = (((__u32)pos+i)/(__u32)fmc->sector_size) * (__u32)fmc->sector_size;
808                                                 pos += fmc->sector_size;
809                                                 goto CHECK_NEXT;
810                                         }
811                                 }
812                         }
813                 }
814                 pos += READ_AHEAD_BYTES;
815         }
816
817  returnBack:
818         kfree(read_buf1);
819         kfree(read_buf2);
820
821         D2(printk("check_partly_erased_sector():Done checking all sectors till offset 0x%x for flipping bits.\n",
822                   (__u32)pos));
823
824         return err;
825
826 }/* end check_partly_erased_sectors() */
827
828
829
830 /* Scan the whole flash memory in order to find all nodes in the
831    file systems.  */
832 static int
833 jffs_scan_flash(struct jffs_control *c)
834 {
835         char name[JFFS_MAX_NAME_LEN + 2];
836         struct jffs_raw_inode raw_inode;
837         struct jffs_node *node = NULL;
838         struct jffs_fmcontrol *fmc = c->fmc;
839         __u32 checksum;
840         __u8 tmp_accurate;
841         __u16 tmp_chksum;
842         __u32 deleted_file;
843         loff_t pos = 0;
844         loff_t start;
845         loff_t test_start;
846         loff_t end = fmc->flash_size;
847         __u8 *read_buf;
848         int i, len, retlen;
849         __u32 offset;
850
851         __u32 free_chunk_size1;
852         __u32 free_chunk_size2;
853
854         
855 #define NUMFREEALLOWED     2        /* 2 chunks of at least erase size space allowed */
856         int num_free_space = 0;       /* Flag err if more than TWO
857                                        free blocks found. This is NOT allowed
858                                        by the current jffs design.
859                                     */
860         int num_free_spc_not_accp = 0; /* For debugging purposed keep count 
861                                         of how much free space was rejected and
862                                         marked dirty
863                                      */
864
865         D1(printk("jffs_scan_flash(): start pos = 0x%lx, end = 0x%lx\n",
866                   (long)pos, (long)end));
867
868         flash_safe_acquire(fmc->mtd);
869
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         */
875         if(check_partly_erased_sectors(fmc) < 0){
876
877                 flash_safe_release(fmc->mtd);
878                 return -EIO; /* bad, bad, bad error. Cannot continue.*/
879         }
880
881         /* Allocate read buffer */
882         read_buf = (__u8 *) kmalloc (sizeof(__u8) * 4096, GFP_KERNEL);
883         if (!read_buf) {
884                 flash_safe_release(fmc->mtd);
885                 return -ENOMEM;
886         }
887                               
888         /* Start the scan.  */
889         while (pos < end) {
890                 deleted_file = 0;
891
892                 /* Remember the position from where we started this scan.  */
893                 start = pos;
894
895                 switch (flash_read_u32(fmc->mtd, pos)) {
896                 case JFFS_EMPTY_BITMASK:
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 */
902
903                         D1(printk("jffs_scan_flash(): 0xffffffff at pos 0x%lx.\n",
904                                   (long)pos));
905
906                         while(pos < end){
907
908                               len = end - pos < 4096 ? end - pos : 4096;
909                               
910                               retlen = flash_safe_read(fmc->mtd, pos,
911                                                  &read_buf[0], len);
912
913                               retlen &= ~3;
914                               
915                               for (i=0 ; i < retlen ; i+=4, pos += 4) {
916                                       if(*((__u32 *) &read_buf[i]) !=
917                                          JFFS_EMPTY_BITMASK)
918                                         break;
919                               }
920                               if (i == retlen)
921                                     continue;
922                               else
923                                     break;
924                         }
925
926                         D1(printk("jffs_scan_flash():0xffffffff ended at pos 0x%lx.\n",
927                                   (long)pos));
928                         
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                         */
937                         if ((__u32) pos % fmc->sector_size) {
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                                 */
943
944                                 test_start = pos & ~(fmc->sector_size-1); /* end of last sector */
945
946                                 if (start < test_start) {
947
948                                         /* free space started in the previous sector! */
949
950                                         if((num_free_space < NUMFREEALLOWED) && 
951                                            ((unsigned int)(test_start - start) >= fmc->sector_size)){
952
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                                                 */
958                                           
959                                                 D1(printk("Reducing end of free space to 0x%x from 0x%x\n",
960                                                           (unsigned int)test_start, (unsigned int)pos));
961
962                                                 D1(printk("Free space accepted: Starting 0x%x for 0x%x bytes\n",
963                                                           (unsigned int) start,
964                                                           (unsigned int)(test_start - start)));
965
966                                                 /* below, space from "start" to "pos" will be marked dirty. */
967                                                 start = test_start; 
968                                                 
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++;
974                                         }else{
975                                                 num_free_spc_not_accp++;
976                                                 D1(printk("Free space (#%i) found but *Not* accepted: Starting"
977                                                           " 0x%x for 0x%x bytes\n",
978                                                           num_free_spc_not_accp, (unsigned int)start, 
979                                                           (unsigned int)((unsigned int)(pos & ~(fmc->sector_size-1)) - (unsigned int)start)));
980                                                 
981                                         }
982                                         
983                                 }
984                                 if((((__u32)(pos - start)) != 0)){
985
986                                         D1(printk("Dirty space: Starting 0x%x for 0x%x bytes\n",
987                                                   (unsigned int) start, (unsigned int) (pos - start)));
988                                         jffs_fmalloced(fmc, (__u32) start,
989                                                        (__u32) (pos - start), NULL);
990                                 }else{
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                                         */
995                                         
996                                         D1(printk("jffs_scan_flash():wants to allocate dirty flash "
997                                                   "space for 0 bytes.\n"));
998                                         D1(printk("jffs_scan_flash(): Flipping bits! We will free "
999                                                   "all allocated memory, erase this sector and remount\n"));
1000
1001                                         /* calculate start of present sector */
1002                                         offset = (((__u32)pos)/(__u32)fmc->sector_size) * (__u32)fmc->sector_size;
1003                                         
1004                                         D1(printk("jffs_scan_flash():erasing sector starting 0x%x.\n",
1005                                                   offset));
1006                                         
1007                                         if (flash_erase_region(fmc->mtd,
1008                                                                offset, fmc->sector_size) < 0) {
1009                                                 printk(KERN_ERR "JFFS: Erase of flash failed. "
1010                                                        "offset = %u, erase_size = %d\n",
1011                                                        offset , fmc->sector_size);
1012
1013                                                 flash_safe_release(fmc->mtd);
1014                                                 kfree(read_buf);
1015                                                 return -1; /* bad, bad, bad! */
1016
1017                                         }
1018                                         flash_safe_release(fmc->mtd);
1019                                         kfree(read_buf);
1020
1021                                         return -EAGAIN; /* erased offending sector. Try mount one more time please. */
1022                                 }
1023                         }else{
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                                  */
1029                                  if((num_free_space < NUMFREEALLOWED) && 
1030                                     ((unsigned int)(pos - start) >= fmc->sector_size)){
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++;
1036                                            D1(printk("Free space accepted: Starting 0x%x for 0x%x bytes\n",
1037                                                      (unsigned int) start, (unsigned int) (pos - start)));
1038                                  }else{
1039                                          num_free_spc_not_accp++;
1040                                          D1(printk("Free space (#%i) found but *Not* accepted: Starting "
1041                                                    "0x%x for 0x%x bytes\n", num_free_spc_not_accp, 
1042                                                    (unsigned int) start, 
1043                                                    (unsigned int) (pos - start)));
1044                                          
1045                                          /* Mark this space as dirty. We already have our free space. */
1046                                          D1(printk("Dirty space: Starting 0x%x for 0x%x bytes\n",
1047                                                    (unsigned int) start, (unsigned int) (pos - start)));
1048                                          jffs_fmalloced(fmc, (__u32) start,
1049                                                         (__u32) (pos - start), NULL);                                      
1050                                  }
1051                                  
1052                         }
1053                         if(num_free_space > NUMFREEALLOWED){
1054                                  printk(KERN_WARNING "jffs_scan_flash(): Found free space "
1055                                         "number %i. Only %i free space is allowed.\n",
1056                                         num_free_space, NUMFREEALLOWED);                              
1057                         }
1058                         continue;
1059
1060                 case JFFS_DIRTY_BITMASK:
1061                         /* We have found 0x00000000 at this position.  Scan as far
1062                            as possible to find out how much is dirty.  */
1063                         D1(printk("jffs_scan_flash(): 0x00000000 at pos 0x%lx.\n",
1064                                   (long)pos));
1065                         for (; pos < end
1066                                && JFFS_DIRTY_BITMASK == flash_read_u32(fmc->mtd, pos);
1067                              pos += 4);
1068                         D1(printk("jffs_scan_flash(): 0x00 ended at "
1069                                   "pos 0x%lx.\n", (long)pos));
1070                         jffs_fmalloced(fmc, (__u32) start,
1071                                        (__u32) (pos - start), NULL);
1072                         continue;
1073
1074                 case JFFS_MAGIC_BITMASK:
1075                         /* We have probably found a new raw inode.  */
1076                         break;
1077
1078                 default:
1079                 bad_inode:
1080                         /* We're f*cked.  This is not solved yet.  We have
1081                            to scan for the magic pattern.  */
1082                         D1(printk("*************** Dirty flash memory or "
1083                                   "bad inode: "
1084                                   "hexdump(pos = 0x%lx, len = 128):\n",
1085                                   (long)pos));
1086                         D1(jffs_hexdump(fmc->mtd, pos, 128));
1087
1088                         for (pos += 4; pos < end; pos += 4) {
1089                                 switch (flash_read_u32(fmc->mtd, pos)) {
1090                                 case JFFS_MAGIC_BITMASK:
1091                                 case JFFS_EMPTY_BITMASK:
1092                                         /* handle these in the main switch() loop */
1093                                         goto cont_scan;
1094
1095                                 default:
1096                                         break;
1097                                 }
1098                         }
1099
1100                         cont_scan:
1101                         /* First, mark as dirty the region
1102                            which really does contain crap. */
1103                         jffs_fmalloced(fmc, (__u32) start,
1104                                        (__u32) (pos - start),
1105                                        NULL);
1106                         
1107                         continue;
1108                 }/* switch */
1109
1110                 /* We have found the beginning of an inode.  Create a
1111                    node for it unless there already is one available.  */
1112                 if (!node) {
1113                         if (!(node = jffs_alloc_node())) {
1114                                 /* Free read buffer */
1115                                 kfree(read_buf);
1116
1117                                 /* Release the flash device */
1118                                 flash_safe_release(fmc->mtd);
1119         
1120                                 return -ENOMEM;
1121                         }
1122                         DJM(no_jffs_node++);
1123                 }
1124
1125                 /* Read the next raw inode.  */
1126
1127                 flash_safe_read(fmc->mtd, pos, (u_char *) &raw_inode,
1128                                 sizeof(struct jffs_raw_inode));
1129
1130                 /* When we compute the checksum for the inode, we never
1131                    count the 'accurate' or the 'checksum' fields.  */
1132                 tmp_accurate = raw_inode.accurate;
1133                 tmp_chksum = raw_inode.chksum;
1134                 raw_inode.accurate = 0;
1135                 raw_inode.chksum = 0;
1136                 checksum = jffs_checksum(&raw_inode,
1137                                          sizeof(struct jffs_raw_inode));
1138                 raw_inode.accurate = tmp_accurate;
1139                 raw_inode.chksum = tmp_chksum;
1140
1141                 D3(printk("*** We have found this raw inode at pos 0x%lx "
1142                           "on the flash:\n", (long)pos));
1143                 D3(jffs_print_raw_inode(&raw_inode));
1144
1145                 if (checksum != raw_inode.chksum) {
1146                         D1(printk("jffs_scan_flash(): Bad checksum: "
1147                                   "checksum = %u, "
1148                                   "raw_inode.chksum = %u\n",
1149                                   checksum, raw_inode.chksum));
1150                         pos += sizeof(struct jffs_raw_inode);
1151                         jffs_fmalloced(fmc, (__u32) start,
1152                                        (__u32) (pos - start), NULL);
1153                         /* Reuse this unused struct jffs_node.  */
1154                         continue;
1155                 }
1156
1157                 /* Check the raw inode read so far.  Start with the
1158                    maximum length of the filename.  */
1159                 if (raw_inode.nsize > JFFS_MAX_NAME_LEN) {
1160                         printk(KERN_WARNING "jffs_scan_flash: Found a "
1161                                "JFFS node with name too large\n");
1162                         goto bad_inode;
1163                 }
1164
1165                 if (raw_inode.rename && raw_inode.dsize != sizeof(__u32)) {
1166                         printk(KERN_WARNING "jffs_scan_flash: Found a "
1167                                "rename node with dsize %u.\n",
1168                                raw_inode.dsize);
1169                         jffs_print_raw_inode(&raw_inode);
1170                         goto bad_inode;
1171                 }
1172
1173                 /* The node's data segment should not exceed a
1174                    certain length.  */
1175                 if (raw_inode.dsize > fmc->max_chunk_size) {
1176                         printk(KERN_WARNING "jffs_scan_flash: Found a "
1177                                "JFFS node with dsize (0x%x) > max_chunk_size (0x%x)\n",
1178                                raw_inode.dsize, fmc->max_chunk_size);
1179                         goto bad_inode;
1180                 }
1181
1182                 pos += sizeof(struct jffs_raw_inode);
1183
1184                 /* This shouldn't be necessary because a node that
1185                    violates the flash boundaries shouldn't be written
1186                    in the first place. */
1187                 if (pos >= end) {
1188                         goto check_node;
1189                 }
1190
1191                 /* Read the name.  */
1192                 *name = 0;
1193                 if (raw_inode.nsize) {
1194                         flash_safe_read(fmc->mtd, pos, name, raw_inode.nsize);
1195                         name[raw_inode.nsize] = '\0';
1196                         pos += raw_inode.nsize
1197                                + JFFS_GET_PAD_BYTES(raw_inode.nsize);
1198                         D3(printk("name == \"%s\"\n", name));
1199                         checksum = jffs_checksum(name, raw_inode.nsize);
1200                         if (checksum != raw_inode.nchksum) {
1201                                 D1(printk("jffs_scan_flash(): Bad checksum: "
1202                                           "checksum = %u, "
1203                                           "raw_inode.nchksum = %u\n",
1204                                           checksum, raw_inode.nchksum));
1205                                 jffs_fmalloced(fmc, (__u32) start,
1206                                                (__u32) (pos - start), NULL);
1207                                 /* Reuse this unused struct jffs_node.  */
1208                                 continue;
1209                         }
1210                         if (pos >= end) {
1211                                 goto check_node;
1212                         }
1213                 }
1214
1215                 /* Read the data, if it exists, in order to be sure it
1216                    matches the checksum.  */
1217                 if (raw_inode.dsize) {
1218                         if (raw_inode.rename) {
1219                                 deleted_file = flash_read_u32(fmc->mtd, pos);
1220                         }
1221                         if (jffs_checksum_flash(fmc->mtd, pos, raw_inode.dsize, &checksum)) {
1222                                 printk("jffs_checksum_flash() failed to calculate a checksum\n");
1223                                 jffs_fmalloced(fmc, (__u32) start,
1224                                                (__u32) (pos - start), NULL);
1225                                 /* Reuse this unused struct jffs_node.  */
1226                                 continue;
1227                         }                               
1228                         pos += raw_inode.dsize
1229                                + JFFS_GET_PAD_BYTES(raw_inode.dsize);
1230
1231                         if (checksum != raw_inode.dchksum) {
1232                                 D1(printk("jffs_scan_flash(): Bad checksum: "
1233                                           "checksum = %u, "
1234                                           "raw_inode.dchksum = %u\n",
1235                                           checksum, raw_inode.dchksum));
1236                                 jffs_fmalloced(fmc, (__u32) start,
1237                                                (__u32) (pos - start), NULL);
1238                                 /* Reuse this unused struct jffs_node.  */
1239                                 continue;
1240                         }
1241                 }
1242
1243                 check_node:
1244
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.  */
1248                 if (c->next_ino <= raw_inode.ino) {
1249                         c->next_ino = raw_inode.ino + 1;
1250                 }
1251
1252                 if (raw_inode.accurate) {
1253                         int err;
1254                         node->data_offset = raw_inode.offset;
1255                         node->data_size = raw_inode.dsize;
1256                         node->removed_size = raw_inode.rsize;
1257                         /* Compute the offset to the actual data in the
1258                            on-flash node.  */
1259                         node->fm_offset
1260                         = sizeof(struct jffs_raw_inode)
1261                           + raw_inode.nsize
1262                           + JFFS_GET_PAD_BYTES(raw_inode.nsize);
1263                         node->fm = jffs_fmalloced(fmc, (__u32) start,
1264                                                   (__u32) (pos - start),
1265                                                   node);
1266                         if (!node->fm) {
1267                                 D(printk("jffs_scan_flash(): !node->fm\n"));
1268                                 jffs_free_node(node);
1269                                 DJM(no_jffs_node--);
1270
1271                                 /* Free read buffer */
1272                                 kfree(read_buf);
1273
1274                                 /* Release the flash device */
1275                                 flash_safe_release(fmc->mtd);
1276
1277                                 return -ENOMEM;
1278                         }
1279                         if ((err = jffs_insert_node(c, NULL, &raw_inode,
1280                                                     name, node)) < 0) {
1281                                 printk("JFFS: Failed to handle raw inode. "
1282                                        "(err = %d)\n", err);
1283                                 break;
1284                         }
1285                         if (raw_inode.rename) {
1286                                 struct jffs_delete_list *dl
1287                                 = (struct jffs_delete_list *)
1288                                   kmalloc(sizeof(struct jffs_delete_list),
1289                                           GFP_KERNEL);
1290                                 if (!dl) {
1291                                         D(printk("jffs_scan_flash: !dl\n"));
1292                                         jffs_free_node(node);
1293                                         DJM(no_jffs_node--);
1294
1295                                         /* Release the flash device */
1296                                         flash_safe_release(fmc->flash_part);
1297
1298                                         /* Free read buffer */
1299                                         kfree(read_buf);
1300
1301                                         return -ENOMEM;
1302                                 }
1303                                 dl->ino = deleted_file;
1304                                 dl->next = c->delete_list;
1305                                 c->delete_list = dl;
1306                                 node->data_size = 0;
1307                         }
1308                         D3(jffs_print_node(node));
1309                         node = NULL; /* Don't free the node!  */
1310                 }
1311                 else {
1312                         jffs_fmalloced(fmc, (__u32) start,
1313                                        (__u32) (pos - start), NULL);
1314                         D3(printk("jffs_scan_flash(): Just found an obsolete "
1315                                   "raw_inode. Continuing the scan...\n"));
1316                         /* Reuse this unused struct jffs_node.  */
1317                 }
1318         }
1319
1320         if (node) {
1321                 jffs_free_node(node);
1322                 DJM(no_jffs_node--);
1323         }
1324         jffs_build_end(fmc);
1325
1326         /* Free read buffer */
1327         kfree(read_buf);
1328
1329         if(!num_free_space){
1330                 printk(KERN_WARNING "jffs_scan_flash(): Did not find even a single "
1331                        "chunk of free space. This is BAD!\n");
1332         }
1333
1334         /* Return happy */
1335         D3(printk("jffs_scan_flash(): Leaving...\n"));
1336         flash_safe_release(fmc->mtd);
1337
1338         /* This is to trap the "free size accounting screwed error. */
1339         free_chunk_size1 = jffs_free_size1(fmc);
1340         free_chunk_size2 = jffs_free_size2(fmc);
1341
1342         if (free_chunk_size1 + free_chunk_size2 != fmc->free_size) {
1343
1344                 printk(KERN_WARNING "jffs_scan_falsh():Free size accounting screwed\n");
1345                 printk(KERN_WARNING "jfffs_scan_flash():free_chunk_size1 == 0x%x, "
1346                        "free_chunk_size2 == 0x%x, fmc->free_size == 0x%x\n", 
1347                        free_chunk_size1, free_chunk_size2, fmc->free_size);
1348
1349                 return -1; /* Do NOT mount f/s so that we can inspect what happened.
1350                               Mounting this  screwed up f/s will screw us up anyway.
1351                             */
1352         }       
1353
1354         return 0; /* as far as we are concerned, we are happy! */
1355 } /* jffs_scan_flash()  */
1356
1357
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
1363 jffs_insert_node(struct jffs_control *c, struct jffs_file *f,
1364                  const struct jffs_raw_inode *raw_inode,
1365                  const char *name, struct jffs_node *node)
1366 {
1367         int update_name = 0;
1368         int insert_into_tree = 0;
1369
1370         D2(printk("jffs_insert_node(): ino = %u, version = %u, "
1371                   "name = \"%s\", deleted = %d\n",
1372                   raw_inode->ino, raw_inode->version,
1373                   ((name && *name) ? name : ""), raw_inode->deleted));
1374
1375         /* If there doesn't exist an associated jffs_file, then
1376            create, initialize and insert one into the file system.  */
1377         if (!f && !(f = jffs_find_file(c, raw_inode->ino))) {
1378                 if (!(f = jffs_create_file(c, raw_inode))) {
1379                         return -ENOMEM;
1380                 }
1381                 jffs_insert_file_into_hash(f);
1382                 insert_into_tree = 1;
1383         }
1384         node->ino = raw_inode->ino;
1385         node->version = raw_inode->version;
1386         node->data_size = raw_inode->dsize;
1387         node->fm_offset = sizeof(struct jffs_raw_inode) + raw_inode->nsize
1388                           + JFFS_GET_PAD_BYTES(raw_inode->nsize);
1389         node->name_size = raw_inode->nsize;
1390
1391         /* Now insert the node at the correct position into the file's
1392            version list.  */
1393         if (!f->version_head) {
1394                 /* This is the first node.  */
1395                 f->version_head = node;
1396                 f->version_tail = node;
1397                 node->version_prev = NULL;
1398                 node->version_next = NULL;
1399                 f->highest_version = node->version;
1400                 update_name = 1;
1401                 f->mode = raw_inode->mode;
1402                 f->uid = raw_inode->uid;
1403                 f->gid = raw_inode->gid;
1404                 f->atime = raw_inode->atime;
1405                 f->mtime = raw_inode->mtime;
1406                 f->ctime = raw_inode->ctime;
1407         }
1408         else if ((f->highest_version < node->version)
1409                  || (node->version == 0)) {
1410                 /* Insert at the end of the list.  I.e. this node is the
1411                    newest one so far.  */
1412                 node->version_prev = f->version_tail;
1413                 node->version_next = NULL;
1414                 f->version_tail->version_next = node;
1415                 f->version_tail = node;
1416                 f->highest_version = node->version;
1417                 update_name = 1;
1418                 f->pino = raw_inode->pino;
1419                 f->mode = raw_inode->mode;
1420                 f->uid = raw_inode->uid;
1421                 f->gid = raw_inode->gid;
1422                 f->atime = raw_inode->atime;
1423                 f->mtime = raw_inode->mtime;
1424                 f->ctime = raw_inode->ctime;
1425         }
1426         else if (f->version_head->version > node->version) {
1427                 /* Insert at the bottom of the list.  */
1428                 node->version_prev = NULL;
1429                 node->version_next = f->version_head;
1430                 f->version_head->version_prev = node;
1431                 f->version_head = node;
1432                 if (!f->name) {
1433                         update_name = 1;
1434                 }
1435         }
1436         else {
1437                 struct jffs_node *n;
1438                 int newer_name = 0;
1439                 /* Search for the insertion position starting from
1440                    the tail (newest node).  */
1441                 for (n = f->version_tail; n; n = n->version_prev) {
1442                         if (n->version < node->version) {
1443                                 node->version_prev = n;
1444                                 node->version_next = n->version_next;
1445                                 node->version_next->version_prev = node;
1446                                 n->version_next = node;
1447                                 if (!newer_name) {
1448                                         update_name = 1;
1449                                 }
1450                                 break;
1451                         }
1452                         if (n->name_size) {
1453                                 newer_name = 1;
1454                         }
1455                 }
1456         }
1457
1458         /* Deletion is irreversible. If any 'deleted' node is ever
1459            written, the file is deleted */
1460         if (raw_inode->deleted)
1461                 f->deleted = raw_inode->deleted;
1462
1463         /* Perhaps update the name.  */
1464         if (raw_inode->nsize && update_name && name && *name && (name != f->name)) {
1465                 if (f->name) {
1466                         kfree(f->name);
1467                         DJM(no_name--);
1468                 }
1469                 if (!(f->name = (char *) kmalloc(raw_inode->nsize + 1,
1470                                                  GFP_KERNEL))) {
1471                         return -ENOMEM;
1472                 }
1473                 DJM(no_name++);
1474                 memcpy(f->name, name, raw_inode->nsize);
1475                 f->name[raw_inode->nsize] = '\0';
1476                 f->nsize = raw_inode->nsize;
1477                 D3(printk("jffs_insert_node(): Updated the name of "
1478                           "the file to \"%s\".\n", name));
1479         }
1480
1481         if (!c->building_fs) {
1482                 D3(printk("jffs_insert_node(): ---------------------------"
1483                           "------------------------------------------- 1\n"));
1484                 if (insert_into_tree) {
1485                         jffs_insert_file_into_tree(f);
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                 */
1492                 if (node->data_size || node->removed_size) {
1493                         jffs_update_file(f, node);
1494                 }
1495                 jffs_remove_redundant_nodes(f);
1496
1497                 jffs_garbage_collect_trigger(c);
1498
1499                 D3(printk("jffs_insert_node(): ---------------------------"
1500                           "------------------------------------------- 2\n"));
1501         }
1502
1503         return 0;
1504 } /* jffs_insert_node()  */
1505
1506
1507 /* Unlink a jffs_node from the version list it is in.  */
1508 static inline void
1509 jffs_unlink_node_from_version_list(struct jffs_file *f,
1510                                    struct jffs_node *node)
1511 {
1512         if (node->version_prev) {
1513                 node->version_prev->version_next = node->version_next;
1514         } else {
1515                 f->version_head = node->version_next;
1516         }
1517         if (node->version_next) {
1518                 node->version_next->version_prev = node->version_prev;
1519         } else {
1520                 f->version_tail = node->version_prev;
1521         }
1522 }
1523
1524
1525 /* Unlink a jffs_node from the range list it is in.  */
1526 static inline void
1527 jffs_unlink_node_from_range_list(struct jffs_file *f, struct jffs_node *node)
1528 {
1529         if (node->range_prev) {
1530                 node->range_prev->range_next = node->range_next;
1531         }
1532         else {
1533                 f->range_head = node->range_next;
1534         }
1535         if (node->range_next) {
1536                 node->range_next->range_prev = node->range_prev;
1537         }
1538         else {
1539                 f->range_tail = node->range_prev;
1540         }
1541 }
1542
1543
1544 /* Function used by jffs_remove_redundant_nodes() below.  This function
1545    classifies what kind of information a node adds to a file.  */
1546 static inline __u8
1547 jffs_classify_node(struct jffs_node *node)
1548 {
1549         __u8 mod_type = JFFS_MODIFY_INODE;
1550
1551         if (node->name_size) {
1552                 mod_type |= JFFS_MODIFY_NAME;
1553         }
1554         if (node->data_size || node->removed_size) {
1555                 mod_type |= JFFS_MODIFY_DATA;
1556         }
1557         return mod_type;
1558 }
1559
1560
1561 /* Remove redundant nodes from a file.  Mark the on-flash memory
1562    as dirty.  */
1563 static int
1564 jffs_remove_redundant_nodes(struct jffs_file *f)
1565 {
1566         struct jffs_node *newest_node;
1567         struct jffs_node *cur;
1568         struct jffs_node *prev;
1569         __u8 newest_type;
1570         __u8 mod_type;
1571         __u8 node_with_name_later = 0;
1572
1573         if (!(newest_node = f->version_tail)) {
1574                 return 0;
1575         }
1576
1577         /* What does the `newest_node' modify?  */
1578         newest_type = jffs_classify_node(newest_node);
1579         node_with_name_later = newest_type & JFFS_MODIFY_NAME;
1580
1581         D3(printk("jffs_remove_redundant_nodes(): ino: %u, name: \"%s\", "
1582                   "newest_type: %u\n", f->ino, (f->name ? f->name : ""),
1583                   newest_type));
1584
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.  */
1588         for (cur = newest_node->version_prev; cur; cur = prev) {
1589                 prev = cur->version_prev;
1590                 mod_type = jffs_classify_node(cur);
1591                 if ((mod_type <= JFFS_MODIFY_INODE)
1592                     || ((newest_type & JFFS_MODIFY_NAME)
1593                         && (mod_type
1594                             <= (JFFS_MODIFY_INODE + JFFS_MODIFY_NAME)))
1595                     || (cur->data_size == 0 && cur->removed_size
1596                         && !cur->version_prev && node_with_name_later)) {
1597                         /* Yes, this node is redundant. Remove it.  */
1598                         D2(printk("jffs_remove_redundant_nodes(): "
1599                                   "Removing node: ino: %u, version: %u, "
1600                                   "mod_type: %u\n", cur->ino, cur->version,
1601                                   mod_type));
1602                         jffs_unlink_node_from_version_list(f, cur);
1603                         jffs_fmfree(f->c->fmc, cur->fm, cur);
1604                         jffs_free_node(cur);
1605                         DJM(no_jffs_node--);
1606                 }
1607                 else {
1608                         node_with_name_later |= (mod_type & JFFS_MODIFY_NAME);
1609                 }
1610         }
1611
1612         return 0;
1613 }
1614
1615
1616 /* Insert a file into the hash table.  */
1617 static int
1618 jffs_insert_file_into_hash(struct jffs_file *f)
1619 {
1620         int i = f->ino % f->c->hash_len;
1621
1622         D3(printk("jffs_insert_file_into_hash(): f->ino: %u\n", f->ino));
1623
1624         list_add(&f->hash, &f->c->hash[i]);
1625         return 0;
1626 }
1627
1628
1629 /* Insert a file into the file system tree.  */
1630 int
1631 jffs_insert_file_into_tree(struct jffs_file *f)
1632 {
1633         struct jffs_file *parent;
1634
1635         D3(printk("jffs_insert_file_into_tree(): name: \"%s\"\n",
1636                   (f->name ? f->name : "")));
1637
1638         if (!(parent = jffs_find_file(f->c, f->pino))) {
1639                 if (f->pino == 0) {
1640                         f->c->root = f;
1641                         f->parent = NULL;
1642                         f->sibling_prev = NULL;
1643                         f->sibling_next = NULL;
1644                         return 0;
1645                 }
1646                 else {
1647                         D1(printk("jffs_insert_file_into_tree(): Found "
1648                                   "inode with no parent and pino == %u\n",
1649                                   f->pino));
1650                         return -1;
1651                 }
1652         }
1653         f->parent = parent;
1654         f->sibling_next = parent->children;
1655         if (f->sibling_next) {
1656                 f->sibling_next->sibling_prev = f;
1657         }
1658         f->sibling_prev = NULL;
1659         parent->children = f;
1660         return 0;
1661 }
1662
1663
1664 /* Remove a file from the hash table.  */
1665 static int
1666 jffs_unlink_file_from_hash(struct jffs_file *f)
1667 {
1668         D3(printk("jffs_unlink_file_from_hash(): f: 0x%p, "
1669                   "ino %u\n", f, f->ino));
1670
1671         list_del(&f->hash);
1672         return 0;
1673 }
1674
1675
1676 /* Just remove the file from the parent's children.  Don't free
1677    any memory.  */
1678 int
1679 jffs_unlink_file_from_tree(struct jffs_file *f)
1680 {
1681         D3(printk("jffs_unlink_file_from_tree(): ino: %d, pino: %d, name: "
1682                   "\"%s\"\n", f->ino, f->pino, (f->name ? f->name : "")));
1683
1684         if (f->sibling_prev) {
1685                 f->sibling_prev->sibling_next = f->sibling_next;
1686         }
1687         else if (f->parent) {
1688                 D3(printk("f->parent=%p\n", f->parent));
1689                 f->parent->children = f->sibling_next;
1690         }
1691         if (f->sibling_next) {
1692                 f->sibling_next->sibling_prev = f->sibling_prev;
1693         }
1694         return 0;
1695 }
1696
1697
1698 /* Find a file with its inode number.  */
1699 struct jffs_file *
1700 jffs_find_file(struct jffs_control *c, __u32 ino)
1701 {
1702         struct jffs_file *f;
1703         int i = ino % c->hash_len;
1704
1705         D3(printk("jffs_find_file(): ino: %u\n", ino));
1706
1707         list_for_each_entry(f, &c->hash[i], hash) {
1708                 if (ino != f->ino)
1709                         continue;
1710                 D3(printk("jffs_find_file(): Found file with ino "
1711                                "%u. (name: \"%s\")\n",
1712                                ino, (f->name ? f->name : ""));
1713                 );
1714                 return f;
1715         }
1716         D3(printk("jffs_find_file(): Didn't find file "
1717                          "with ino %u.\n", ino);
1718         );
1719         return NULL;
1720 }
1721
1722
1723 /* Find a file in a directory.  We are comparing the names.  */
1724 struct jffs_file *
1725 jffs_find_child(struct jffs_file *dir, const char *name, int len)
1726 {
1727         struct jffs_file *f;
1728
1729         D3(printk("jffs_find_child()\n"));
1730
1731         for (f = dir->children; f; f = f->sibling_next) {
1732                 if (!f->deleted && f->name
1733                     && !strncmp(f->name, name, len)
1734                     && f->name[len] == '\0') {
1735                         break;
1736                 }
1737         }
1738
1739         D3(if (f) {
1740                 printk("jffs_find_child(): Found \"%s\".\n", f->name);
1741         }
1742         else {
1743                 char *copy = (char *) kmalloc(len + 1, GFP_KERNEL);
1744                 if (copy) {
1745                         memcpy(copy, name, len);
1746                         copy[len] = '\0';
1747                 }
1748                 printk("jffs_find_child(): Didn't find the file \"%s\".\n",
1749                        (copy ? copy : ""));
1750                 kfree(copy);
1751         });
1752
1753         return f;
1754 }
1755
1756
1757 /* Write a raw inode that takes up a certain amount of space in the flash
1758    memory.  At the end of the flash device, there is often space that is
1759    impossible to use.  At these times we want to mark this space as not
1760    used.  In the cases when the amount of space is greater or equal than
1761    a struct jffs_raw_inode, we write a "dummy node" that takes up this
1762    space.  The space after the raw inode, if it exists, is left as it is.
1763    Since this space after the raw inode contains JFFS_EMPTY_BITMASK bytes,
1764    we can compute the checksum of it; we don't have to manipulate it any
1765    further.
1766
1767    If the space left on the device is less than the size of a struct
1768    jffs_raw_inode, this space is filled with JFFS_DIRTY_BITMASK bytes.
1769    No raw inode is written this time.  */
1770 static int
1771 jffs_write_dummy_node(struct jffs_control *c, struct jffs_fm *dirty_fm)
1772 {
1773         struct jffs_fmcontrol *fmc = c->fmc;
1774         int err;
1775
1776         D1(printk("jffs_write_dummy_node(): dirty_fm->offset = 0x%08x, "
1777                   "dirty_fm->size = %u\n",
1778                   dirty_fm->offset, dirty_fm->size));
1779
1780         if (dirty_fm->size >= sizeof(struct jffs_raw_inode)) {
1781                 struct jffs_raw_inode raw_inode;
1782                 memset(&raw_inode, 0, sizeof(struct jffs_raw_inode));
1783                 raw_inode.magic = JFFS_MAGIC_BITMASK;
1784                 raw_inode.dsize = dirty_fm->size
1785                                   - sizeof(struct jffs_raw_inode);
1786                 raw_inode.dchksum = raw_inode.dsize * 0xff;
1787                 raw_inode.chksum
1788                 = jffs_checksum(&raw_inode, sizeof(struct jffs_raw_inode));
1789
1790                 if ((err = flash_safe_write(fmc->mtd,
1791                                             dirty_fm->offset,
1792                                             (u_char *)&raw_inode,
1793                                             sizeof(struct jffs_raw_inode)))
1794                     < 0) {
1795                         printk(KERN_ERR "JFFS: jffs_write_dummy_node: "
1796                                "flash_safe_write failed!\n");
1797                         return err;
1798                 }
1799         }
1800         else {
1801                 flash_safe_acquire(fmc->mtd);
1802                 flash_memset(fmc->mtd, dirty_fm->offset, 0, dirty_fm->size);
1803                 flash_safe_release(fmc->mtd);
1804         }
1805
1806         D3(printk("jffs_write_dummy_node(): Leaving...\n"));
1807         return 0;
1808 }
1809
1810
1811 /* Write a raw inode, possibly its name and possibly some data.  */
1812 int
1813 jffs_write_node(struct jffs_control *c, struct jffs_node *node,
1814                 struct jffs_raw_inode *raw_inode,
1815                 const char *name, const unsigned char *data,
1816                 int recoverable,
1817                 struct jffs_file *f)
1818 {
1819         struct jffs_fmcontrol *fmc = c->fmc;
1820         struct jffs_fm *fm;
1821         struct kvec node_iovec[4];
1822         unsigned long iovec_cnt;
1823
1824         __u32 pos;
1825         int err;
1826         __u32 slack = 0;
1827
1828         __u32 total_name_size = raw_inode->nsize
1829                                 + JFFS_GET_PAD_BYTES(raw_inode->nsize);
1830         __u32 total_data_size = raw_inode->dsize
1831                                 + JFFS_GET_PAD_BYTES(raw_inode->dsize);
1832         __u32 total_size = sizeof(struct jffs_raw_inode)
1833                            + total_name_size + total_data_size;
1834         
1835         /* If this node isn't something that will eventually let
1836            GC free even more space, then don't allow it unless
1837            there's at least max_chunk_size space still available
1838         */
1839         if (!recoverable)
1840                 slack = fmc->max_chunk_size;
1841                 
1842
1843         /* Fire the retrorockets and shoot the fruiton torpedoes, sir!  */
1844
1845         ASSERT(if (!node) {
1846                 printk("jffs_write_node(): node == NULL\n");
1847                 return -EINVAL;
1848         });
1849         ASSERT(if (raw_inode && raw_inode->nsize && !name) {
1850                 printk("*** jffs_write_node(): nsize = %u but name == NULL\n",
1851                        raw_inode->nsize);
1852                 return -EINVAL;
1853         });
1854
1855         D1(printk("jffs_write_node(): filename = \"%s\", ino = %u, "
1856                   "total_size = %u\n",
1857                   (name ? name : ""), raw_inode->ino,
1858                   total_size));
1859
1860         jffs_fm_write_lock(fmc);
1861
1862 retry:
1863         fm = NULL;
1864         err = 0;
1865         while (!fm) {
1866
1867                 /* Deadlocks suck. */
1868                 while(fmc->free_size < fmc->min_free_size + total_size + slack) {
1869                         jffs_fm_write_unlock(fmc);
1870                         if (!JFFS_ENOUGH_SPACE(c, total_size + slack))
1871                                 return -ENOSPC;
1872                         jffs_fm_write_lock(fmc);
1873                 }
1874
1875                 /* First try to allocate some flash memory.  */
1876                 err = jffs_fmalloc(fmc, total_size, node, &fm);
1877                 
1878                 if (err == -ENOSPC) {
1879                         /* Just out of space. GC and try again */
1880                         if (fmc->dirty_size < fmc->sector_size) {
1881                                 D(printk("jffs_write_node(): jffs_fmalloc(0x%p, %u) "
1882                                          "failed, no dirty space to GC\n", fmc,
1883                                          total_size));
1884                                 return err;
1885                         }
1886                         
1887                         D1(printk(KERN_INFO "jffs_write_node(): Calling jffs_garbage_collect_now()\n"));
1888                         jffs_fm_write_unlock(fmc);
1889                         if ((err = jffs_garbage_collect_now(c))) {
1890                                 D(printk("jffs_write_node(): jffs_garbage_collect_now() failed\n"));
1891                                 return err;
1892                         }
1893                         jffs_fm_write_lock(fmc);
1894                         continue;
1895                 } 
1896
1897                 if (err < 0) {
1898                         jffs_fm_write_unlock(fmc);
1899
1900                         D(printk("jffs_write_node(): jffs_fmalloc(0x%p, %u) "
1901                                  "failed!\n", fmc, total_size));
1902                         return err;
1903                 }
1904
1905                 if (!fm->nodes) {
1906                         /* The jffs_fm struct that we got is not good enough.
1907                            Make that space dirty and try again  */
1908                         if ((err = jffs_write_dummy_node(c, fm)) < 0) {
1909                                 kfree(fm);
1910                                 DJM(no_jffs_fm--);
1911                                 jffs_fm_write_unlock(fmc);
1912                                 D(printk("jffs_write_node(): "
1913                                          "jffs_write_dummy_node(): Failed!\n"));
1914                                 return err;
1915                         }
1916                         fm = NULL;
1917                 }
1918         } /* while(!fm) */
1919         node->fm = fm;
1920
1921         ASSERT(if (fm->nodes == 0) {
1922                 printk(KERN_ERR "jffs_write_node(): fm->nodes == 0\n");
1923         });
1924
1925         pos = node->fm->offset;
1926
1927         /* Increment the version number here. We can't let the caller
1928            set it beforehand, because we might have had to do GC on a node
1929            of this file - and we'd end up reusing version numbers.
1930         */
1931         if (f) {
1932                 raw_inode->version = f->highest_version + 1;
1933                 D1(printk (KERN_NOTICE "jffs_write_node(): setting version of %s to %d\n", f->name, raw_inode->version));
1934
1935                 /* if the file was deleted, set the deleted bit in the raw inode */
1936                 if (f->deleted)
1937                         raw_inode->deleted = 1;
1938         }
1939
1940         /* Compute the checksum for the data and name chunks.  */
1941         raw_inode->dchksum = jffs_checksum(data, raw_inode->dsize);
1942         raw_inode->nchksum = jffs_checksum(name, raw_inode->nsize);
1943
1944         /* The checksum is calculated without the chksum and accurate
1945            fields so set them to zero first.  */
1946         raw_inode->accurate = 0;
1947         raw_inode->chksum = 0;
1948         raw_inode->chksum = jffs_checksum(raw_inode,
1949                                           sizeof(struct jffs_raw_inode));
1950         raw_inode->accurate = 0xff;
1951
1952         D3(printk("jffs_write_node(): About to write this raw inode to the "
1953                   "flash at pos 0x%lx:\n", (long)pos));
1954         D3(jffs_print_raw_inode(raw_inode));
1955
1956         /* The actual raw JFFS node */
1957         node_iovec[0].iov_base = (void *) raw_inode;
1958         node_iovec[0].iov_len = (size_t) sizeof(struct jffs_raw_inode);
1959         iovec_cnt = 1;
1960
1961         /* Get name and size if there is one */
1962         if (raw_inode->nsize) {
1963                 node_iovec[iovec_cnt].iov_base = (void *) name;
1964                 node_iovec[iovec_cnt].iov_len = (size_t) raw_inode->nsize;
1965                 iovec_cnt++;
1966
1967                 if (JFFS_GET_PAD_BYTES(raw_inode->nsize)) {
1968                         static char allff[3]={255,255,255};
1969                         /* Add some extra padding if necessary */
1970                         node_iovec[iovec_cnt].iov_base = allff;
1971                         node_iovec[iovec_cnt].iov_len =
1972                                 JFFS_GET_PAD_BYTES(raw_inode->nsize);
1973                         iovec_cnt++;
1974                 }
1975         }
1976
1977         /* Get data and size if there is any */
1978         if (raw_inode->dsize) {
1979                 node_iovec[iovec_cnt].iov_base = (void *) data;
1980                 node_iovec[iovec_cnt].iov_len = (size_t) raw_inode->dsize;
1981                 iovec_cnt++;
1982                 /* No need to pad this because we're not actually putting
1983                    anything after it.
1984                 */
1985         }
1986
1987         if ((err = flash_safe_writev(fmc->mtd, node_iovec, iovec_cnt,
1988                                     pos)) < 0) {
1989                 jffs_fmfree_partly(fmc, fm, 0);
1990                 jffs_fm_write_unlock(fmc);
1991                 printk(KERN_ERR "JFFS: jffs_write_node: Failed to write, "
1992                        "requested %i, wrote %i\n", total_size, err);
1993                 goto retry;
1994         }
1995         if (raw_inode->deleted)
1996                 f->deleted = 1;
1997
1998         jffs_fm_write_unlock(fmc);
1999         D3(printk("jffs_write_node(): Leaving...\n"));
2000         return raw_inode->dsize;
2001 } /* jffs_write_node()  */
2002
2003
2004 /* Read data from the node and write it to the buffer.  'node_offset'
2005    is how much we have read from this particular node before and which
2006    shouldn't be read again.  'max_size' is how much space there is in
2007    the buffer.  */
2008 static int
2009 jffs_get_node_data(struct jffs_file *f, struct jffs_node *node, 
2010                    unsigned char *buf,__u32 node_offset, __u32 max_size)
2011 {
2012         struct jffs_fmcontrol *fmc = f->c->fmc;
2013         __u32 pos = node->fm->offset + node->fm_offset + node_offset;
2014         __u32 avail = node->data_size - node_offset;
2015         __u32 r;
2016
2017         D2(printk("  jffs_get_node_data(): file: \"%s\", ino: %u, "
2018                   "version: %u, node_offset: %u\n",
2019                   f->name, node->ino, node->version, node_offset));
2020
2021         r = min(avail, max_size);
2022         D3(printk(KERN_NOTICE "jffs_get_node_data\n"));
2023         flash_safe_read(fmc->mtd, pos, buf, r);
2024
2025         D3(printk("  jffs_get_node_data(): Read %u byte%s.\n",
2026                   r, (r == 1 ? "" : "s")));
2027
2028         return r;
2029 }
2030
2031
2032 /* Read data from the file's nodes.  Write the data to the buffer
2033    'buf'.  'read_offset' tells how much data we should skip.  */
2034 int
2035 jffs_read_data(struct jffs_file *f, unsigned char *buf, __u32 read_offset,
2036                __u32 size)
2037 {
2038         struct jffs_node *node;
2039         __u32 read_data = 0; /* Total amount of read data.  */
2040         __u32 node_offset = 0;
2041         __u32 pos = 0; /* Number of bytes traversed.  */
2042
2043         D2(printk("jffs_read_data(): file = \"%s\", read_offset = %d, "
2044                   "size = %u\n",
2045                   (f->name ? f->name : ""), read_offset, size));
2046
2047         if (read_offset >= f->size) {
2048                 D(printk("  f->size: %d\n", f->size));
2049                 return 0;
2050         }
2051
2052         /* First find the node to read data from.  */
2053         node = f->range_head;
2054         while (pos <= read_offset) {
2055                 node_offset = read_offset - pos;
2056                 if (node_offset >= node->data_size) {
2057                         pos += node->data_size;
2058                         node = node->range_next;
2059                 }
2060                 else {
2061                         break;
2062                 }
2063         }
2064
2065         /* "Cats are living proof that not everything in nature
2066            has to be useful."
2067            - Garrison Keilor ('97)  */
2068
2069         /* Fill the buffer.  */
2070         while (node && (read_data < size)) {
2071                 int r;
2072                 if (!node->fm) {
2073                         /* This node does not refer to real data.  */
2074                         r = min(size - read_data,
2075                                      node->data_size - node_offset);
2076                         memset(&buf[read_data], 0, r);
2077                 }
2078                 else if ((r = jffs_get_node_data(f, node, &buf[read_data],
2079                                                  node_offset,
2080                                                  size - read_data)) < 0) {
2081                         return r;
2082                 }
2083                 read_data += r;
2084                 node_offset = 0;
2085                 node = node->range_next;
2086         }
2087         D3(printk("  jffs_read_data(): Read %u bytes.\n", read_data));
2088         return read_data;
2089 }
2090
2091
2092 /* Used for traversing all nodes in the hash table.  */
2093 int
2094 jffs_foreach_file(struct jffs_control *c, int (*func)(struct jffs_file *))
2095 {
2096         int pos;
2097         int r;
2098         int result = 0;
2099
2100         for (pos = 0; pos < c->hash_len; pos++) {
2101                 struct jffs_file *f, *next;
2102
2103                 /* We must do _safe, because 'func' might remove the
2104                    current file 'f' from the list.  */
2105                 list_for_each_entry_safe(f, next, &c->hash[pos], hash) {
2106                         r = func(f);
2107                         if (r < 0)
2108                                 return r;
2109                         result += r;
2110                 }
2111         }
2112
2113         return result;
2114 }
2115
2116
2117 /* Free all nodes associated with a file.  */
2118 static int
2119 jffs_free_node_list(struct jffs_file *f)
2120 {
2121         struct jffs_node *node;
2122         struct jffs_node *p;
2123
2124         D3(printk("jffs_free_node_list(): f #%u, \"%s\"\n",
2125                   f->ino, (f->name ? f->name : "")));
2126         node = f->version_head;
2127         while (node) {
2128                 p = node;
2129                 node = node->version_next;
2130                 jffs_free_node(p);
2131                 DJM(no_jffs_node--);
2132         }
2133         return 0;
2134 }
2135
2136
2137 /* Free a file and its name.  */
2138 static int
2139 jffs_free_file(struct jffs_file *f)
2140 {
2141         D3(printk("jffs_free_file: f #%u, \"%s\"\n",
2142                   f->ino, (f->name ? f->name : "")));
2143
2144         if (f->name) {
2145                 kfree(f->name);
2146                 DJM(no_name--);
2147         }
2148         kfree(f);
2149         no_jffs_file--;
2150         return 0;
2151 }
2152
2153 static long
2154 jffs_get_file_count(void)
2155 {
2156         return no_jffs_file;
2157 }
2158
2159 /* See if a file is deleted. If so, mark that file's nodes as obsolete.  */
2160 int
2161 jffs_possibly_delete_file(struct jffs_file *f)
2162 {
2163         struct jffs_node *n;
2164
2165         D3(printk("jffs_possibly_delete_file(): ino: %u\n",
2166                   f->ino));
2167
2168         ASSERT(if (!f) {
2169                 printk(KERN_ERR "jffs_possibly_delete_file(): f == NULL\n");
2170                 return -1;
2171         });
2172
2173         if (f->deleted) {
2174                 /* First try to remove all older versions.  Commence with
2175                    the oldest node.  */
2176                 for (n = f->version_head; n; n = n->version_next) {
2177                         if (!n->fm) {
2178                                 continue;
2179                         }
2180                         if (jffs_fmfree(f->c->fmc, n->fm, n) < 0) {
2181                                 break;
2182                         }
2183                 }
2184                 /* Unlink the file from the filesystem.  */
2185                 if (!f->c->building_fs) {
2186                         jffs_unlink_file_from_tree(f);
2187                 }
2188                 jffs_unlink_file_from_hash(f);
2189                 jffs_free_node_list(f);
2190                 jffs_free_file(f);
2191         }
2192         return 0;
2193 }
2194
2195
2196 /* Used in conjunction with jffs_foreach_file() to count the number
2197    of files in the file system.  */
2198 int
2199 jffs_file_count(struct jffs_file *f)
2200 {
2201         return 1;
2202 }
2203
2204
2205 /* Build up a file's range list from scratch by going through the
2206    version list.  */
2207 static int
2208 jffs_build_file(struct jffs_file *f)
2209 {
2210         struct jffs_node *n;
2211
2212         D3(printk("jffs_build_file(): ino: %u, name: \"%s\"\n",
2213                   f->ino, (f->name ? f->name : "")));
2214
2215         for (n = f->version_head; n; n = n->version_next) {
2216                 jffs_update_file(f, n);
2217         }
2218         return 0;
2219 }
2220
2221
2222 /* Remove an amount of data from a file. If this amount of data is
2223    zero, that could mean that a node should be split in two parts.
2224    We remove or change the appropriate nodes in the lists.
2225
2226    Starting offset of area to be removed is node->data_offset,
2227    and the length of the area is in node->removed_size.   */
2228 static int
2229 jffs_delete_data(struct jffs_file *f, struct jffs_node *node)
2230 {
2231         struct jffs_node *n;
2232         __u32 offset = node->data_offset;
2233         __u32 remove_size = node->removed_size;
2234
2235         D3(printk("jffs_delete_data(): offset = %u, remove_size = %u\n",
2236                   offset, remove_size));
2237
2238         if (remove_size == 0
2239             && f->range_tail
2240             && f->range_tail->data_offset + f->range_tail->data_size
2241                == offset) {
2242                 /* A simple append; nothing to remove or no node to split.  */
2243                 return 0;
2244         }
2245
2246         /* Find the node where we should begin the removal.  */
2247         for (n = f->range_head; n; n = n->range_next) {
2248                 if (n->data_offset + n->data_size > offset) {
2249                         break;
2250                 }
2251         }
2252         if (!n) {
2253                 /* If there's no data in the file there's no data to
2254                    remove either.  */
2255                 return 0;
2256         }
2257
2258         if (n->data_offset > offset) {
2259                 /* XXX: Not implemented yet.  */
2260                 printk(KERN_WARNING "JFFS: An unexpected situation "
2261                        "occurred in jffs_delete_data.\n");
2262         }
2263         else if (n->data_offset < offset) {
2264                 /* See if the node has to be split into two parts.  */
2265                 if (n->data_offset + n->data_size > offset + remove_size) {
2266                         /* Do the split.  */
2267                         struct jffs_node *new_node;
2268                         D3(printk("jffs_delete_data(): Split node with "
2269                                   "version number %u.\n", n->version));
2270
2271                         if (!(new_node = jffs_alloc_node())) {
2272                                 D(printk("jffs_delete_data(): -ENOMEM\n"));
2273                                 return -ENOMEM;
2274                         }
2275                         DJM(no_jffs_node++);
2276
2277                         new_node->ino = n->ino;
2278                         new_node->version = n->version;
2279                         new_node->data_offset = offset;
2280                         new_node->data_size = n->data_size - (remove_size + (offset - n->data_offset));
2281                         new_node->fm_offset = n->fm_offset + (remove_size + (offset - n->data_offset));
2282                         new_node->name_size = n->name_size;
2283                         new_node->fm = n->fm;
2284                         new_node->version_prev = n;
2285                         new_node->version_next = n->version_next;
2286                         if (new_node->version_next) {
2287                                 new_node->version_next->version_prev
2288                                 = new_node;
2289                         }
2290                         else {
2291                                 f->version_tail = new_node;
2292                         }
2293                         n->version_next = new_node;
2294                         new_node->range_prev = n;
2295                         new_node->range_next = n->range_next;
2296                         if (new_node->range_next) {
2297                                 new_node->range_next->range_prev = new_node;
2298                         }
2299                         else {
2300                                 f->range_tail = new_node;
2301                         }
2302                         /* A very interesting can of worms.  */
2303                         n->range_next = new_node;
2304                         n->data_size = offset - n->data_offset;
2305                         if (new_node->fm)
2306                                 jffs_add_node(new_node);
2307                         else {
2308                                 D1(printk(KERN_WARNING "jffs_delete_data(): Splitting an empty node (file hold).\n!"));
2309                                 D1(printk(KERN_WARNING "FIXME: Did dwmw2 do the right thing here?\n"));
2310                         }
2311                         n = new_node->range_next;
2312                         remove_size = 0;
2313                 }
2314                 else {
2315                         /* No.  No need to split the node.  Just remove
2316                            the end of the node.  */
2317                         int r = min(n->data_offset + n->data_size
2318                                          - offset, remove_size);
2319                         n->data_size -= r;
2320                         remove_size -= r;
2321                         n = n->range_next;
2322                 }
2323         }
2324
2325         /* Remove as many nodes as necessary.  */
2326         while (n && remove_size) {
2327                 if (n->data_size <= remove_size) {
2328                         struct jffs_node *p = n;
2329                         remove_size -= n->data_size;
2330                         n = n->range_next;
2331                         D3(printk("jffs_delete_data(): Removing node: "
2332                                   "ino: %u, version: %u%s\n",
2333                                   p->ino, p->version,
2334                                   (p->fm ? "" : " (virtual)")));
2335                         if (p->fm) {
2336                                 jffs_fmfree(f->c->fmc, p->fm, p);
2337                         }
2338                         jffs_unlink_node_from_range_list(f, p);
2339                         jffs_unlink_node_from_version_list(f, p);
2340                         jffs_free_node(p);
2341                         DJM(no_jffs_node--);
2342                 }
2343                 else {
2344                         n->data_size -= remove_size;
2345                         n->fm_offset += remove_size;
2346                         n->data_offset -= (node->removed_size - remove_size);
2347                         n = n->range_next;
2348                         break;
2349                 }
2350         }
2351
2352         /* Adjust the following nodes' information about offsets etc.  */
2353         while (n && node->removed_size) {
2354                 n->data_offset -= node->removed_size;
2355                 n = n->range_next;
2356         }
2357
2358         if (node->removed_size > (f->size - node->data_offset)) {
2359                 /* It's possible that the removed_size is in fact
2360                  * greater than the amount of data we actually thought
2361                  * were present in the first place - some of the nodes 
2362                  * which this node originally obsoleted may already have
2363                  * been deleted from the flash by subsequent garbage 
2364                  * collection.
2365                  *
2366                  * If this is the case, don't let f->size go negative.
2367                  * Bad things would happen :)
2368                  */
2369                 f->size = node->data_offset;
2370         } else {
2371                 f->size -= node->removed_size;
2372         }
2373         D3(printk("jffs_delete_data(): f->size = %d\n", f->size));
2374         return 0;
2375 } /* jffs_delete_data()  */
2376
2377
2378 /* Insert some data into a file.  Prior to the call to this function,
2379    jffs_delete_data should be called.  */
2380 static int
2381 jffs_insert_data(struct jffs_file *f, struct jffs_node *node)
2382 {
2383         D3(printk("jffs_insert_data(): node->data_offset = %u, "
2384                   "node->data_size = %u, f->size = %u\n",
2385                   node->data_offset, node->data_size, f->size));
2386
2387         /* Find the position where we should insert data.  */
2388         retry:
2389         if (node->data_offset == f->size) {
2390                 /* A simple append.  This is the most common operation.  */
2391                 node->range_next = NULL;
2392                 node->range_prev = f->range_tail;
2393                 if (node->range_prev) {
2394                         node->range_prev->range_next = node;
2395                 }
2396                 f->range_tail = node;
2397                 f->size += node->data_size;
2398                 if (!f->range_head) {
2399                         f->range_head = node;
2400                 }
2401         }
2402         else if (node->data_offset < f->size) {
2403                 /* Trying to insert data into the middle of the file.  This
2404                    means no problem because jffs_delete_data() has already
2405                    prepared the range list for us.  */
2406                 struct jffs_node *n;
2407
2408                 /* Find the correct place for the insertion and then insert
2409                    the node.  */
2410                 for (n = f->range_head; n; n = n->range_next) {
2411                         D2(printk("Cool stuff's happening!\n"));
2412
2413                         if (n->data_offset == node->data_offset) {
2414                                 node->range_prev = n->range_prev;
2415                                 if (node->range_prev) {
2416                                         node->range_prev->range_next = node;
2417                                 }
2418                                 else {
2419                                         f->range_head = node;
2420                                 }
2421                                 node->range_next = n;
2422                                 n->range_prev = node;
2423                                 break;
2424                         }
2425                         ASSERT(else if (n->data_offset + n->data_size >
2426                                         node->data_offset) {
2427                                 printk(KERN_ERR "jffs_insert_data(): "
2428                                        "Couldn't find a place to insert "
2429                                        "the data!\n");
2430                                 return -1;
2431                         });
2432                 }
2433
2434                 /* Adjust later nodes' offsets etc.  */
2435                 n = node->range_next;
2436                 while (n) {
2437                         n->data_offset += node->data_size;
2438                         n = n->range_next;
2439                 }
2440                 f->size += node->data_size;
2441         }
2442         else if (node->data_offset > f->size) {
2443                 /* Okay.  This is tricky.  This means that we want to insert
2444                    data at a place that is beyond the limits of the file as
2445                    it is constructed right now.  This is actually a common
2446                    event that for instance could occur during the mounting
2447                    of the file system if a large file have been truncated,
2448                    rewritten and then only partially garbage collected.  */
2449
2450                 struct jffs_node *n;
2451
2452                 /* We need a place holder for the data that is missing in
2453                    front of this insertion.  This "virtual node" will not
2454                    be associated with any space on the flash device.  */
2455                 struct jffs_node *virtual_node;
2456                 if (!(virtual_node = jffs_alloc_node())) {
2457                         return -ENOMEM;
2458                 }
2459
2460                 D(printk("jffs_insert_data: Inserting a virtual node.\n"));
2461                 D(printk("  node->data_offset = %u\n", node->data_offset));
2462                 D(printk("  f->size = %u\n", f->size));
2463
2464                 virtual_node->ino = node->ino;
2465                 virtual_node->version = node->version;
2466                 virtual_node->removed_size = 0;
2467                 virtual_node->fm_offset = 0;
2468                 virtual_node->name_size = 0;
2469                 virtual_node->fm = NULL; /* This is a virtual data holder.  */
2470                 virtual_node->version_prev = NULL;
2471                 virtual_node->version_next = NULL;
2472                 virtual_node->range_next = NULL;
2473
2474                 /* Are there any data at all in the file yet?  */
2475                 if (f->range_head) {
2476                         virtual_node->data_offset
2477                         = f->range_tail->data_offset
2478                           + f->range_tail->data_size;
2479                         virtual_node->data_size
2480                         = node->data_offset - virtual_node->data_offset;
2481                         virtual_node->range_prev = f->range_tail;
2482                         f->range_tail->range_next = virtual_node;
2483                 }
2484                 else {
2485                         virtual_node->data_offset = 0;
2486                         virtual_node->data_size = node->data_offset;
2487                         virtual_node->range_prev = NULL;
2488                         f->range_head = virtual_node;
2489                 }
2490
2491                 f->range_tail = virtual_node;
2492                 f->size += virtual_node->data_size;
2493
2494                 /* Insert this virtual node in the version list as well.  */
2495                 for (n = f->version_head; n ; n = n->version_next) {
2496                         if (n->version == virtual_node->version) {
2497                                 virtual_node->version_prev = n->version_prev;
2498                                 n->version_prev = virtual_node;
2499                                 if (virtual_node->version_prev) {
2500                                         virtual_node->version_prev
2501                                         ->version_next = virtual_node;
2502                                 }
2503                                 else {
2504                                         f->version_head = virtual_node;
2505                                 }
2506                                 virtual_node->version_next = n;
2507                                 break;
2508                         }
2509                 }
2510
2511                 D(jffs_print_node(virtual_node));
2512
2513                 /* Make a new try to insert the node.  */
2514                 goto retry;
2515         }
2516
2517         D3(printk("jffs_insert_data(): f->size = %d\n", f->size));
2518         return 0;
2519 }
2520
2521
2522 /* A new node (with data) has been added to the file and now the range
2523    list has to be modified.  */
2524 static int
2525 jffs_update_file(struct jffs_file *f, struct jffs_node *node)
2526 {
2527         int err;
2528
2529         D3(printk("jffs_update_file(): ino: %u, version: %u\n",
2530                   f->ino, node->version));
2531
2532         if (node->data_size == 0) {
2533                 if (node->removed_size == 0) {
2534                         /* data_offset == X  */
2535                         /* data_size == 0  */
2536                         /* remove_size == 0  */
2537                 }
2538                 else {
2539                         /* data_offset == X  */
2540                         /* data_size == 0  */
2541                         /* remove_size != 0  */
2542                         if ((err = jffs_delete_data(f, node)) < 0) {
2543                                 return err;
2544                         }
2545                 }
2546         }
2547         else {
2548                 /* data_offset == X  */
2549                 /* data_size != 0  */
2550                 /* remove_size == Y  */
2551                 if ((err = jffs_delete_data(f, node)) < 0) {
2552                         return err;
2553                 }
2554                 if ((err = jffs_insert_data(f, node)) < 0) {
2555                         return err;
2556                 }
2557         }
2558         return 0;
2559 }
2560
2561 /* Print the contents of a file.  */
2562 #if 0
2563 int
2564 jffs_print_file(struct jffs_file *f)
2565 {
2566         D(int i);
2567         D(printk("jffs_file: 0x%p\n", f));
2568         D(printk("{\n"));
2569         D(printk("        0x%08x, /* ino  */\n", f->ino));
2570         D(printk("        0x%08x, /* pino  */\n", f->pino));
2571         D(printk("        0x%08x, /* mode  */\n", f->mode));
2572         D(printk("        0x%04x,     /* uid  */\n", f->uid));
2573         D(printk("        0x%04x,     /* gid  */\n", f->gid));
2574         D(printk("        0x%08x, /* atime  */\n", f->atime));
2575         D(printk("        0x%08x, /* mtime  */\n", f->mtime));
2576         D(printk("        0x%08x, /* ctime  */\n", f->ctime));
2577         D(printk("        0x%02x,       /* nsize  */\n", f->nsize));
2578         D(printk("        0x%02x,       /* nlink  */\n", f->nlink));
2579         D(printk("        0x%02x,       /* deleted  */\n", f->deleted));
2580         D(printk("        \"%s\", ", (f->name ? f->name : "")));
2581         D(for (i = strlen(f->name ? f->name : ""); i < 8; ++i) {
2582                 printk(" ");
2583         });
2584         D(printk("/* name  */\n"));
2585         D(printk("        0x%08x, /* size  */\n", f->size));
2586         D(printk("        0x%08x, /* highest_version  */\n",
2587                  f->highest_version));
2588         D(printk("        0x%p, /* c  */\n", f->c));
2589         D(printk("        0x%p, /* parent  */\n", f->parent));
2590         D(printk("        0x%p, /* children  */\n", f->children));
2591         D(printk("        0x%p, /* sibling_prev  */\n", f->sibling_prev));
2592         D(printk("        0x%p, /* sibling_next  */\n", f->sibling_next));
2593         D(printk("        0x%p, /* hash_prev  */\n", f->hash.prev));
2594         D(printk("        0x%p, /* hash_next  */\n", f->hash.next));
2595         D(printk("        0x%p, /* range_head  */\n", f->range_head));
2596         D(printk("        0x%p, /* range_tail  */\n", f->range_tail));
2597         D(printk("        0x%p, /* version_head  */\n", f->version_head));
2598         D(printk("        0x%p, /* version_tail  */\n", f->version_tail));
2599         D(printk("}\n"));
2600         return 0;
2601 }
2602 #endif  /*  0  */
2603
2604 void
2605 jffs_print_hash_table(struct jffs_control *c)
2606 {
2607         int i;
2608
2609         printk("JFFS: Dumping the file system's hash table...\n");
2610         for (i = 0; i < c->hash_len; i++) {
2611                 struct jffs_file *f;
2612                 list_for_each_entry(f, &c->hash[i], hash) {
2613                         printk("*** c->hash[%u]: \"%s\" "
2614                                "(ino: %u, pino: %u)\n",
2615                                i, (f->name ? f->name : ""),
2616                                f->ino, f->pino);
2617                 }
2618         }
2619 }
2620
2621
2622 void
2623 jffs_print_tree(struct jffs_file *first_file, int indent)
2624 {
2625         struct jffs_file *f;
2626         char *space;
2627         int dir;
2628
2629         if (!first_file) {
2630                 return;
2631         }
2632
2633         if (!(space = (char *) kmalloc(indent + 1, GFP_KERNEL))) {
2634                 printk("jffs_print_tree(): Out of memory!\n");
2635                 return;
2636         }
2637
2638         memset(space, ' ', indent);
2639         space[indent] = '\0';
2640
2641         for (f = first_file; f; f = f->sibling_next) {
2642                 dir = S_ISDIR(f->mode);
2643                 printk("%s%s%s (ino: %u, highest_version: %u, size: %u)\n",
2644                        space, (f->name ? f->name : ""), (dir ? "/" : ""),
2645                        f->ino, f->highest_version, f->size);
2646                 if (dir) {
2647                         jffs_print_tree(f->children, indent + 2);
2648                 }
2649         }
2650
2651         kfree(space);
2652 }
2653
2654
2655 #if defined(JFFS_MEMORY_DEBUG) && JFFS_MEMORY_DEBUG
2656 void
2657 jffs_print_memory_allocation_statistics(void)
2658 {
2659         static long printout;
2660         printk("________ Memory printout #%ld ________\n", ++printout);
2661         printk("no_jffs_file = %ld\n", no_jffs_file);
2662         printk("no_jffs_node = %ld\n", no_jffs_node);
2663         printk("no_jffs_control = %ld\n", no_jffs_control);
2664         printk("no_jffs_raw_inode = %ld\n", no_jffs_raw_inode);
2665         printk("no_jffs_node_ref = %ld\n", no_jffs_node_ref);
2666         printk("no_jffs_fm = %ld\n", no_jffs_fm);
2667         printk("no_jffs_fmcontrol = %ld\n", no_jffs_fmcontrol);
2668         printk("no_hash = %ld\n", no_hash);
2669         printk("no_name = %ld\n", no_name);
2670         printk("\n");
2671 }
2672 #endif
2673
2674
2675 /* Rewrite `size' bytes, and begin at `node'.  */
2676 static int
2677 jffs_rewrite_data(struct jffs_file *f, struct jffs_node *node, __u32 size)
2678 {
2679         struct jffs_control *c = f->c;
2680         struct jffs_fmcontrol *fmc = c->fmc;
2681         struct jffs_raw_inode raw_inode;
2682         struct jffs_node *new_node;
2683         struct jffs_fm *fm;
2684         __u32 pos;
2685         __u32 pos_dchksum;
2686         __u32 total_name_size;
2687         __u32 total_data_size;
2688         __u32 total_size;
2689         int err;
2690
2691         D1(printk("***jffs_rewrite_data(): node: %u, name: \"%s\", size: %u\n",
2692                   f->ino, (f->name ? f->name : "(null)"), size));
2693
2694         /* Create and initialize the new node.  */
2695         if (!(new_node = jffs_alloc_node())) {
2696                 D(printk("jffs_rewrite_data(): "
2697                          "Failed to allocate node.\n"));
2698                 return -ENOMEM;
2699         }
2700         DJM(no_jffs_node++);
2701         new_node->data_offset = node->data_offset;
2702         new_node->removed_size = size;
2703         total_name_size = JFFS_PAD(f->nsize);
2704         total_data_size = JFFS_PAD(size);
2705         total_size = sizeof(struct jffs_raw_inode)
2706                      + total_name_size + total_data_size;
2707         new_node->fm_offset = sizeof(struct jffs_raw_inode)
2708                               + total_name_size;
2709
2710 retry:
2711         jffs_fm_write_lock(fmc);
2712         err = 0;
2713
2714         if ((err = jffs_fmalloc(fmc, total_size, new_node, &fm)) < 0) {
2715                 DJM(no_jffs_node--);
2716                 jffs_fm_write_unlock(fmc);
2717                 D(printk("jffs_rewrite_data(): Failed to allocate fm.\n"));
2718                 jffs_free_node(new_node);
2719                 return err;
2720         }
2721         else if (!fm->nodes) {
2722                 /* The jffs_fm struct that we got is not big enough.  */
2723                 /* This should never happen, because we deal with this case
2724                    in jffs_garbage_collect_next().*/
2725                 printk(KERN_WARNING "jffs_rewrite_data(): Allocated node is too small (%d bytes of %d)\n", fm->size, total_size);
2726                 if ((err = jffs_write_dummy_node(c, fm)) < 0) {
2727                         D(printk("jffs_rewrite_data(): "
2728                                  "jffs_write_dummy_node() Failed!\n"));
2729                 } else {
2730                         err = -ENOSPC;
2731                 }
2732                 DJM(no_jffs_fm--);
2733                 jffs_fm_write_unlock(fmc);
2734                 kfree(fm);
2735                 
2736                 return err;
2737         }
2738         new_node->fm = fm;
2739
2740         /* Initialize the raw inode.  */
2741         raw_inode.magic = JFFS_MAGIC_BITMASK;
2742         raw_inode.ino = f->ino;
2743         raw_inode.pino = f->pino;
2744         raw_inode.version = f->highest_version + 1;
2745         raw_inode.mode = f->mode;
2746         raw_inode.uid = f->uid;
2747         raw_inode.gid = f->gid;
2748         raw_inode.atime = f->atime;
2749         raw_inode.mtime = f->mtime;
2750         raw_inode.ctime = f->ctime;
2751         raw_inode.offset = node->data_offset;
2752         raw_inode.dsize = size;
2753         raw_inode.rsize = size;
2754         raw_inode.nsize = f->nsize;
2755         raw_inode.nlink = f->nlink;
2756         raw_inode.spare = 0;
2757         raw_inode.rename = 0;
2758         raw_inode.deleted = f->deleted;
2759         raw_inode.accurate = 0xff;
2760         raw_inode.dchksum = 0;
2761         raw_inode.nchksum = 0;
2762
2763         pos = new_node->fm->offset;
2764         pos_dchksum = pos +JFFS_RAW_INODE_DCHKSUM_OFFSET;
2765
2766         D3(printk("jffs_rewrite_data(): Writing this raw inode "
2767                   "to pos 0x%ul.\n", pos));
2768         D3(jffs_print_raw_inode(&raw_inode));
2769
2770         if ((err = flash_safe_write(fmc->mtd, pos,
2771                                     (u_char *) &raw_inode,
2772                                     sizeof(struct jffs_raw_inode)
2773                                     - sizeof(__u32)
2774                                     - sizeof(__u16) - sizeof(__u16))) < 0) {
2775                 jffs_fmfree_partly(fmc, fm,
2776                                    total_name_size + total_data_size);
2777                 jffs_fm_write_unlock(fmc);
2778                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Write error during "
2779                         "rewrite. (raw inode)\n");
2780                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Now retrying "
2781                         "rewrite. (raw inode)\n");
2782                 goto retry;
2783         }
2784         pos += sizeof(struct jffs_raw_inode);
2785
2786         /* Write the name to the flash memory.  */
2787         if (f->nsize) {
2788                 D3(printk("jffs_rewrite_data(): Writing name \"%s\" to "
2789                           "pos 0x%ul.\n", f->name, (unsigned int) pos));
2790                 if ((err = flash_safe_write(fmc->mtd, pos,
2791                                             (u_char *)f->name,
2792                                             f->nsize)) < 0) {
2793                         jffs_fmfree_partly(fmc, fm, total_data_size);
2794                         jffs_fm_write_unlock(fmc);
2795                         printk(KERN_ERR "JFFS: jffs_rewrite_data: Write "
2796                                 "error during rewrite. (name)\n");
2797                         printk(KERN_ERR "JFFS: jffs_rewrite_data: Now retrying "
2798                                 "rewrite. (name)\n");
2799                         goto retry;
2800                 }
2801                 pos += total_name_size;
2802                 raw_inode.nchksum = jffs_checksum(f->name, f->nsize);
2803         }
2804
2805         /* Write the data.  */
2806         if (size) {
2807                 int r;
2808                 unsigned char *page;
2809                 __u32 offset = node->data_offset;
2810
2811                 if (!(page = (unsigned char *)__get_free_page(GFP_KERNEL))) {
2812                         jffs_fmfree_partly(fmc, fm, 0);
2813                         return -1;
2814                 }
2815
2816                 while (size) {
2817                         __u32 s = min(size, (__u32)PAGE_SIZE);
2818                         if ((r = jffs_read_data(f, (char *)page,
2819                                                 offset, s)) < s) {
2820                                 free_page((unsigned long)page);
2821                                 jffs_fmfree_partly(fmc, fm, 0);
2822                                 jffs_fm_write_unlock(fmc);
2823                                 printk(KERN_ERR "JFFS: jffs_rewrite_data: "
2824                                          "jffs_read_data() "
2825                                          "failed! (r = %d)\n", r);
2826                                 return -1;
2827                         }
2828                         if ((err = flash_safe_write(fmc->mtd,
2829                                                     pos, page, r)) < 0) {
2830                                 free_page((unsigned long)page);
2831                                 jffs_fmfree_partly(fmc, fm, 0);
2832                                 jffs_fm_write_unlock(fmc);
2833                                 printk(KERN_ERR "JFFS: jffs_rewrite_data: "
2834                                        "Write error during rewrite. "
2835                                        "(data)\n");
2836                                 goto retry;
2837                         }
2838                         pos += r;
2839                         size -= r;
2840                         offset += r;
2841                         raw_inode.dchksum += jffs_checksum(page, r);
2842                 }
2843
2844                 free_page((unsigned long)page);
2845         }
2846
2847         raw_inode.accurate = 0;
2848         raw_inode.chksum = jffs_checksum(&raw_inode,
2849                                          sizeof(struct jffs_raw_inode)
2850                                          - sizeof(__u16));
2851
2852         /* Add the checksum.  */
2853         if ((err
2854              = flash_safe_write(fmc->mtd, pos_dchksum,
2855                                 &((u_char *)
2856                                 &raw_inode)[JFFS_RAW_INODE_DCHKSUM_OFFSET],
2857                                 sizeof(__u32) + sizeof(__u16)
2858                                 + sizeof(__u16))) < 0) {
2859                 jffs_fmfree_partly(fmc, fm, 0);
2860                 jffs_fm_write_unlock(fmc);
2861                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Write error during "
2862                        "rewrite. (checksum)\n");
2863                 goto retry;
2864         }
2865
2866         /* Now make the file system aware of the newly written node.  */
2867         jffs_insert_node(c, f, &raw_inode, f->name, new_node);
2868         jffs_fm_write_unlock(fmc);
2869
2870         D3(printk("jffs_rewrite_data(): Leaving...\n"));
2871         return 0;
2872 } /* jffs_rewrite_data()  */
2873
2874
2875 /* jffs_garbage_collect_next implements one step in the garbage collect
2876    process and is often called multiple times at each occasion of a
2877    garbage collect.  */
2878
2879 static int
2880 jffs_garbage_collect_next(struct jffs_control *c)
2881 {
2882         struct jffs_fmcontrol *fmc = c->fmc;
2883         struct jffs_node *node;
2884         struct jffs_file *f;
2885         int err = 0;
2886         __u32 size;
2887         __u32 data_size;
2888         __u32 total_name_size;
2889         __u32 extra_available;
2890         __u32 space_needed;
2891         __u32 free_chunk_size1 = jffs_free_size1(fmc);
2892         D2(__u32 free_chunk_size2 = jffs_free_size2(fmc));
2893
2894         /* Get the oldest node in the flash.  */
2895         node = jffs_get_oldest_node(fmc);
2896         ASSERT(if (!node) {
2897                 printk(KERN_ERR "JFFS: jffs_garbage_collect_next: "
2898                        "No oldest node found!\n");
2899                 err = -1;
2900                 goto jffs_garbage_collect_next_end;
2901                 
2902
2903         });
2904
2905         /* Find its corresponding file too.  */
2906         f = jffs_find_file(c, node->ino);
2907
2908         if (!f) {
2909           printk (KERN_ERR "JFFS: jffs_garbage_collect_next: "
2910                   "No file to garbage collect! "
2911                   "(ino = 0x%08x)\n", node->ino);
2912           /* FIXME: Free the offending node and recover. */
2913           err = -1;
2914           goto jffs_garbage_collect_next_end;
2915         }
2916
2917         /* We always write out the name. Theoretically, we don't need
2918            to, but for now it's easier - because otherwise we'd have
2919            to keep track of how many times the current name exists on
2920            the flash and make sure it never reaches zero.
2921
2922            The current approach means that would be possible to cause
2923            the GC to end up eating its tail by writing lots of nodes
2924            with no name for it to garbage-collect. Hence the change in
2925            inode.c to write names with _every_ node.
2926
2927            It sucks, but it _should_ work.
2928         */
2929         total_name_size = JFFS_PAD(f->nsize);
2930
2931         D1(printk("jffs_garbage_collect_next(): \"%s\", "
2932                   "ino: %u, version: %u, location 0x%x, dsize %u\n",
2933                   (f->name ? f->name : ""), node->ino, node->version, 
2934                   node->fm->offset, node->data_size));
2935
2936         /* Compute how many data it's possible to rewrite at the moment.  */
2937         data_size = f->size - node->data_offset;
2938
2939         /* And from that, the total size of the chunk we want to write */
2940         size = sizeof(struct jffs_raw_inode) + total_name_size
2941                + data_size + JFFS_GET_PAD_BYTES(data_size);
2942
2943         /* If that's more than max_chunk_size, reduce it accordingly */
2944         if (size > fmc->max_chunk_size) {
2945                 size = fmc->max_chunk_size;
2946                 data_size = size - sizeof(struct jffs_raw_inode)
2947                             - total_name_size;
2948         }
2949
2950         /* If we're asking to take up more space than free_chunk_size1
2951            but we _could_ fit in it, shrink accordingly.
2952         */
2953         if (size > free_chunk_size1) {
2954
2955                 if (free_chunk_size1 <
2956                     (sizeof(struct jffs_raw_inode) + total_name_size + BLOCK_SIZE)){
2957                         /* The space left is too small to be of any
2958                            use really.  */
2959                         struct jffs_fm *dirty_fm
2960                         = jffs_fmalloced(fmc,
2961                                          fmc->tail->offset + fmc->tail->size,
2962                                          free_chunk_size1, NULL);
2963                         if (!dirty_fm) {
2964                                 printk(KERN_ERR "JFFS: "
2965                                        "jffs_garbage_collect_next: "
2966                                        "Failed to allocate `dirty' "
2967                                        "flash memory!\n");
2968                                 err = -1;
2969                                 goto jffs_garbage_collect_next_end;
2970                         }
2971                         D1(printk("Dirtying end of flash - too small\n"));
2972                         jffs_write_dummy_node(c, dirty_fm);
2973                         err = 0;
2974                         goto jffs_garbage_collect_next_end;
2975                 }
2976                 D1(printk("Reducing size of new node from %d to %d to avoid "
2977                           " exceeding free_chunk_size1\n",
2978                           size, free_chunk_size1));
2979
2980                 size = free_chunk_size1;
2981                 data_size = size - sizeof(struct jffs_raw_inode)
2982                             - total_name_size;
2983         }
2984
2985
2986         /* Calculate the amount of space needed to hold the nodes
2987            which are remaining in the tail */
2988         space_needed = fmc->min_free_size - (node->fm->offset % fmc->sector_size);
2989
2990         /* From that, calculate how much 'extra' space we can use to
2991            increase the size of the node we're writing from the size
2992            of the node we're obsoleting
2993         */
2994         if (space_needed > fmc->free_size) {
2995                 /* If we've gone below min_free_size for some reason,
2996                    don't fuck up. This is why we have 
2997                    min_free_size > sector_size. Whinge about it though,
2998                    just so I can convince myself my maths is right.
2999                 */
3000                 D1(printk(KERN_WARNING "jffs_garbage_collect_next(): "
3001                           "space_needed %d exceeded free_size %d\n",
3002                           space_needed, fmc->free_size));
3003                 extra_available = 0;
3004         } else {
3005                 extra_available = fmc->free_size - space_needed;
3006         }
3007
3008         /* Check that we don't use up any more 'extra' space than
3009            what's available */
3010         if (size > JFFS_PAD(node->data_size) + total_name_size + 
3011             sizeof(struct jffs_raw_inode) + extra_available) {
3012                 D1(printk("Reducing size of new node from %d to %ld to avoid "
3013                        "catching our tail\n", size, 
3014                           (long) (JFFS_PAD(node->data_size) + JFFS_PAD(node->name_size) + 
3015                           sizeof(struct jffs_raw_inode) + extra_available)));
3016                 D1(printk("space_needed = %d, extra_available = %d\n", 
3017                           space_needed, extra_available));
3018
3019                 size = JFFS_PAD(node->data_size) + total_name_size + 
3020                   sizeof(struct jffs_raw_inode) + extra_available;
3021                 data_size = size - sizeof(struct jffs_raw_inode)
3022                         - total_name_size;
3023         };
3024
3025         D2(printk("  total_name_size: %u\n", total_name_size));
3026         D2(printk("  data_size: %u\n", data_size));
3027         D2(printk("  size: %u\n", size));
3028         D2(printk("  f->nsize: %u\n", f->nsize));
3029         D2(printk("  f->size: %u\n", f->size));
3030         D2(printk("  node->data_offset: %u\n", node->data_offset));
3031         D2(printk("  free_chunk_size1: %u\n", free_chunk_size1));
3032         D2(printk("  free_chunk_size2: %u\n", free_chunk_size2));
3033         D2(printk("  node->fm->offset: 0x%08x\n", node->fm->offset));
3034
3035         if ((err = jffs_rewrite_data(f, node, data_size))) {
3036                 printk(KERN_WARNING "jffs_rewrite_data() failed: %d\n", err);
3037                 return err;
3038         }
3039           
3040 jffs_garbage_collect_next_end:
3041         D3(printk("jffs_garbage_collect_next: Leaving...\n"));
3042         return err;
3043 } /* jffs_garbage_collect_next */
3044
3045
3046 /* If an obsolete node is partly going to be erased due to garbage
3047    collection, the part that isn't going to be erased must be filled
3048    with zeroes so that the scan of the flash will work smoothly next
3049    time.  (The data in the file could for instance be a JFFS image
3050    which could cause enormous confusion during a scan of the flash
3051    device if we didn't do this.)
3052      There are two phases in this procedure: First, the clearing of
3053    the name and data parts of the node. Second, possibly also clearing
3054    a part of the raw inode as well.  If the box is power cycled during
3055    the first phase, only the checksum of this node-to-be-cleared-at-
3056    the-end will be wrong.  If the box is power cycled during, or after,
3057    the clearing of the raw inode, the information like the length of
3058    the name and data parts are zeroed.  The next time the box is
3059    powered up, the scanning algorithm manages this faulty data too
3060    because:
3061
3062    - The checksum is invalid and thus the raw inode must be discarded
3063      in any case.
3064    - If the lengths of the data part or the name part are zeroed, the
3065      scanning just continues after the raw inode.  But after the inode
3066      the scanning procedure just finds zeroes which is the same as
3067      dirt.
3068
3069    So, in the end, this could never fail. :-)  Even if it does fail,
3070    the scanning algorithm should manage that too.  */
3071
3072 static int
3073 jffs_clear_end_of_node(struct jffs_control *c, __u32 erase_size)
3074 {
3075         struct jffs_fm *fm;
3076         struct jffs_fmcontrol *fmc = c->fmc;
3077         __u32 zero_offset;
3078         __u32 zero_size;
3079         __u32 zero_offset_data;
3080         __u32 zero_size_data;
3081         __u32 cutting_raw_inode = 0;
3082
3083         if (!(fm = jffs_cut_node(fmc, erase_size))) {
3084                 D3(printk("jffs_clear_end_of_node(): fm == NULL\n"));
3085                 return 0;
3086         }
3087
3088         /* Where and how much shall we clear?  */
3089         zero_offset = fmc->head->offset + erase_size;
3090         zero_size = fm->offset + fm->size - zero_offset;
3091
3092         /* Do we have to clear the raw_inode explicitly?  */
3093         if (fm->size - zero_size < sizeof(struct jffs_raw_inode)) {
3094                 cutting_raw_inode = sizeof(struct jffs_raw_inode)
3095                                     - (fm->size - zero_size);
3096         }
3097
3098         /* First, clear the name and data fields.  */
3099         zero_offset_data = zero_offset + cutting_raw_inode;
3100         zero_size_data = zero_size - cutting_raw_inode;
3101         flash_safe_acquire(fmc->mtd);
3102         flash_memset(fmc->mtd, zero_offset_data, 0, zero_size_data);
3103         flash_safe_release(fmc->mtd);
3104
3105         /* Should we clear a part of the raw inode?  */
3106         if (cutting_raw_inode) {
3107                 /* I guess it is ok to clear the raw inode in this order.  */
3108                 flash_safe_acquire(fmc->mtd);
3109                 flash_memset(fmc->mtd, zero_offset, 0,
3110                              cutting_raw_inode);
3111                 flash_safe_release(fmc->mtd);
3112         }
3113
3114         return 0;
3115 } /* jffs_clear_end_of_node()  */
3116
3117 /* Try to erase as much as possible of the dirt in the flash memory.  */
3118 static long
3119 jffs_try_to_erase(struct jffs_control *c)
3120 {
3121         struct jffs_fmcontrol *fmc = c->fmc;
3122         long erase_size;
3123         int err;
3124         __u32 offset;
3125
3126         D3(printk("jffs_try_to_erase()\n"));
3127
3128         erase_size = jffs_erasable_size(fmc);
3129
3130         D2(printk("jffs_try_to_erase(): erase_size = %ld\n", erase_size));
3131
3132         if (erase_size == 0) {
3133                 return 0;
3134         }
3135         else if (erase_size < 0) {
3136                 printk(KERN_ERR "JFFS: jffs_try_to_erase: "
3137                        "jffs_erasable_size returned %ld.\n", erase_size);
3138                 return erase_size;
3139         }
3140
3141         if ((err = jffs_clear_end_of_node(c, erase_size)) < 0) {
3142                 printk(KERN_ERR "JFFS: jffs_try_to_erase: "
3143                        "Clearing of node failed.\n");
3144                 return err;
3145         }
3146
3147         offset = fmc->head->offset;
3148
3149         /* Now, let's try to do the erase.  */
3150         if ((err = flash_erase_region(fmc->mtd,
3151                                       offset, erase_size)) < 0) {
3152                 printk(KERN_ERR "JFFS: Erase of flash failed. "
3153                        "offset = %u, erase_size = %ld\n",
3154                        offset, erase_size);
3155                 /* XXX: Here we should allocate this area as dirty
3156                    with jffs_fmalloced or something similar.  Now
3157                    we just report the error.  */
3158                 return err;
3159         }
3160
3161 #if 0
3162         /* Check if the erased sectors really got erased.  */
3163         {
3164                 __u32 pos;
3165                 __u32 end;
3166
3167                 pos = (__u32)flash_get_direct_pointer(to_kdev_t(c->sb->s_dev), offset);
3168                 end = pos + erase_size;
3169
3170                 D2(printk("JFFS: Checking erased sector(s)...\n"));
3171
3172                 flash_safe_acquire(fmc->mtd);
3173
3174                 for (; pos < end; pos += 4) {
3175                         if (*(__u32 *)pos != JFFS_EMPTY_BITMASK) {
3176                                 printk("JFFS: Erase failed! pos = 0x%lx\n",
3177                                        (long)pos);
3178                                 jffs_hexdump(fmc->mtd, pos,
3179                                              jffs_min(256, end - pos));
3180                                 err = -1;
3181                                 break;
3182                         }
3183                 }
3184
3185                 flash_safe_release(fmc->mtd);
3186
3187                 if (!err) {
3188                         D2(printk("JFFS: Erase succeeded.\n"));
3189                 }
3190                 else {
3191                         /* XXX: Here we should allocate the memory
3192                            with jffs_fmalloced() in order to prevent
3193                            JFFS from using this area accidentally.  */
3194                         return err;
3195                 }
3196         }
3197 #endif
3198
3199         /* Update the flash memory data structures.  */
3200         jffs_sync_erase(fmc, erase_size);
3201
3202         return erase_size;
3203 }
3204
3205
3206 /* There are different criteria that should trigger a garbage collect:
3207
3208    1. There is too much dirt in the memory.
3209    2. The free space is becoming small.
3210    3. There are many versions of a node.
3211
3212    The garbage collect should always be done in a manner that guarantees
3213    that future garbage collects cannot be locked.  E.g. Rewritten chunks
3214    should not be too large (span more than one sector in the flash memory
3215    for exemple).  Of course there is a limit on how intelligent this garbage
3216    collection can be.  */
3217
3218
3219 static int
3220 jffs_garbage_collect_now(struct jffs_control *c)
3221 {
3222         struct jffs_fmcontrol *fmc = c->fmc;
3223         long erased = 0;
3224         int result = 0;
3225         D1(int i = 1);
3226         D2(printk("***jffs_garbage_collect_now(): fmc->dirty_size = %u, fmc->free_size = 0x%x\n, fcs1=0x%x, fcs2=0x%x",
3227                   fmc->dirty_size, fmc->free_size, jffs_free_size1(fmc), jffs_free_size2(fmc)));
3228         D2(jffs_print_fmcontrol(fmc));
3229
3230         //      down(&fmc->gclock);
3231
3232         /* If it is possible to garbage collect, do so.  */
3233         
3234         while (erased == 0) {
3235                 D1(printk("***jffs_garbage_collect_now(): round #%u, "
3236                           "fmc->dirty_size = %u\n", i++, fmc->dirty_size));
3237                 D2(jffs_print_fmcontrol(fmc));
3238
3239                 if ((erased = jffs_try_to_erase(c)) < 0) {
3240                         printk(KERN_WARNING "JFFS: Error in "
3241                                "garbage collector.\n");
3242                         result = erased;
3243                         goto gc_end;
3244                 }
3245                 if (erased)
3246                         break;
3247                 
3248                 if (fmc->free_size == 0) {
3249                         /* Argh */
3250                         printk(KERN_ERR "jffs_garbage_collect_now(): free_size == 0. This is BAD.\n");
3251                         result = -ENOSPC;
3252                         break;
3253                 }
3254
3255                 if (fmc->dirty_size < fmc->sector_size) {
3256                         /* Actually, we _may_ have been able to free some, 
3257                          * if there are many overlapping nodes which aren't
3258                          * actually marked dirty because they still have
3259                          * some valid data in each.
3260                          */
3261                         result = -ENOSPC;
3262                         break;
3263                 }
3264
3265                 /* Let's dare to make a garbage collect.  */
3266                 if ((result = jffs_garbage_collect_next(c)) < 0) {
3267                         printk(KERN_ERR "JFFS: Something "
3268                                "has gone seriously wrong "
3269                                "with a garbage collect.\n");
3270                         goto gc_end;
3271                 }
3272
3273                 D1(printk("   jffs_garbage_collect_now(): erased: %ld\n", erased));
3274                 DJM(jffs_print_memory_allocation_statistics());
3275         }
3276         
3277 gc_end:
3278         //      up(&fmc->gclock);
3279
3280         D3(printk("   jffs_garbage_collect_now(): Leaving...\n"));
3281         D1(if (erased) {
3282                 printk("jffs_g_c_now(): erased = %ld\n", erased);
3283                 jffs_print_fmcontrol(fmc);
3284         });
3285
3286         if (!erased && !result)
3287                 return -ENOSPC;
3288
3289         return result;
3290 } /* jffs_garbage_collect_now() */
3291
3292
3293 /* Determine if it is reasonable to start garbage collection.
3294    We start a gc pass if either:
3295    - The number of free bytes < MIN_FREE_BYTES && at least one
3296      block is dirty, OR
3297    - The number of dirty bytes > MAX_DIRTY_BYTES
3298 */
3299 static inline int thread_should_wake (struct jffs_control *c)
3300 {
3301         D1(printk (KERN_NOTICE "thread_should_wake(): free=%d, dirty=%d, blocksize=%d.\n",
3302                    c->fmc->free_size, c->fmc->dirty_size, c->fmc->sector_size));
3303
3304         /* If there's not enough dirty space to free a block, there's no point. */
3305         if (c->fmc->dirty_size < c->fmc->sector_size) {
3306                 D2(printk(KERN_NOTICE "thread_should_wake(): Not waking. Insufficient dirty space\n"));
3307                 return 0;
3308         }
3309 #if 1
3310         /* If there is too much RAM used by the various structures, GC */
3311         if (jffs_get_node_inuse() > (c->fmc->used_size/c->fmc->max_chunk_size * 5 + jffs_get_file_count() * 2 + 50)) {
3312                 /* FIXME: Provide proof that this test can be satisfied. We
3313                    don't want a filesystem doing endless GC just because this
3314                    condition cannot ever be false.
3315                 */
3316                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to number of nodes\n"));
3317                 return 1;
3318         }
3319 #endif
3320         /* If there are fewer free bytes than the threshold, GC */
3321         if (c->fmc->free_size < c->gc_minfree_threshold) {
3322                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to insufficent free space\n"));
3323                 return 1;
3324         }
3325         /* If there are more dirty bytes than the threshold, GC */
3326         if (c->fmc->dirty_size > c->gc_maxdirty_threshold) {
3327                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to excessive dirty space\n"));
3328                 return 1;
3329         }       
3330         /* FIXME: What about the "There are many versions of a node" condition? */
3331
3332         return 0;
3333 }
3334
3335
3336 void jffs_garbage_collect_trigger(struct jffs_control *c)
3337 {
3338         /* NOTE: We rely on the fact that we have the BKL here.
3339          * Otherwise, the gc_task could go away between the check
3340          * and the wake_up_process()
3341          */
3342         if (c->gc_task && thread_should_wake(c))
3343                 send_sig(SIGHUP, c->gc_task, 1);
3344 }
3345   
3346
3347 /* Kernel threads  take (void *) as arguments.   Thus we pass
3348    the jffs_control data as a (void *) and then cast it. */
3349 int
3350 jffs_garbage_collect_thread(void *ptr)
3351 {
3352         struct jffs_control *c = (struct jffs_control *) ptr;
3353         struct jffs_fmcontrol *fmc = c->fmc;
3354         long erased;
3355         int result = 0;
3356         D1(int i = 1);
3357
3358         daemonize("jffs_gcd");
3359
3360         c->gc_task = current;
3361
3362         lock_kernel();
3363         init_completion(&c->gc_thread_comp); /* barrier */ 
3364         spin_lock_irq(&current->sighand->siglock);
3365         siginitsetinv (&current->blocked, sigmask(SIGHUP) | sigmask(SIGKILL) | sigmask(SIGSTOP) | sigmask(SIGCONT));
3366         recalc_sigpending();
3367         spin_unlock_irq(&current->sighand->siglock);
3368
3369         D1(printk (KERN_NOTICE "jffs_garbage_collect_thread(): Starting infinite loop.\n"));
3370
3371         for (;;) {
3372
3373                 /* See if we need to start gc.  If we don't, go to sleep.
3374                    
3375                    Current implementation is a BAD THING(tm).  If we try 
3376                    to unmount the FS, the unmount operation will sleep waiting
3377                    for this thread to exit.  We need to arrange to send it a
3378                    sig before the umount process sleeps.
3379                 */
3380
3381                 if (!thread_should_wake(c))
3382                         set_current_state (TASK_INTERRUPTIBLE);
3383                 
3384                 schedule(); /* Yes, we do this even if we want to go
3385                                        on immediately - we're a low priority 
3386                                        background task. */
3387
3388                 /* Put_super will send a SIGKILL and then wait on the sem. 
3389                  */
3390                 while (signal_pending(current)) {
3391                         siginfo_t info;
3392                         unsigned long signr = 0;
3393
3394                         if (try_to_freeze())
3395                                 continue;
3396
3397                         spin_lock_irq(&current->sighand->siglock);
3398                         signr = dequeue_signal(current, &current->blocked, &info);
3399                         spin_unlock_irq(&current->sighand->siglock);
3400
3401                         switch(signr) {
3402                         case SIGSTOP:
3403                                 D1(printk("jffs_garbage_collect_thread(): SIGSTOP received.\n"));
3404                                 set_current_state(TASK_STOPPED);
3405                                 schedule();
3406                                 break;
3407
3408                         case SIGKILL:
3409                                 D1(printk("jffs_garbage_collect_thread(): SIGKILL received.\n"));
3410                                 c->gc_task = NULL;
3411                                 complete_and_exit(&c->gc_thread_comp, 0);
3412                         }
3413                 }
3414
3415
3416                 D1(printk (KERN_NOTICE "jffs_garbage_collect_thread(): collecting.\n"));
3417
3418                 D3(printk (KERN_NOTICE "g_c_thread(): down biglock\n"));
3419                 down(&fmc->biglock);
3420                 
3421                 D1(printk("***jffs_garbage_collect_thread(): round #%u, "
3422                           "fmc->dirty_size = %u\n", i++, fmc->dirty_size));
3423                 D2(jffs_print_fmcontrol(fmc));
3424
3425                 if ((erased = jffs_try_to_erase(c)) < 0) {
3426                         printk(KERN_WARNING "JFFS: Error in "
3427                                "garbage collector: %ld.\n", erased);
3428                 }
3429
3430                 if (erased)
3431                         goto gc_end;
3432
3433                 if (fmc->free_size == 0) {
3434                         /* Argh. Might as well commit suicide. */
3435                         printk(KERN_ERR "jffs_garbage_collect_thread(): free_size == 0. This is BAD.\n");
3436                         send_sig(SIGQUIT, c->gc_task, 1);
3437                         // panic()
3438                         goto gc_end;
3439                 }
3440                 
3441                 /* Let's dare to make a garbage collect.  */
3442                 if ((result = jffs_garbage_collect_next(c)) < 0) {
3443                         printk(KERN_ERR "JFFS: Something "
3444                                "has gone seriously wrong "
3445                                "with a garbage collect: %d\n", result);
3446                 }
3447                 
3448         gc_end:
3449                 D3(printk (KERN_NOTICE "g_c_thread(): up biglock\n"));
3450                 up(&fmc->biglock);
3451         } /* for (;;) */
3452 } /* jffs_garbage_collect_thread() */