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         struct list_head *tmp;
1705
1706         D3(printk("jffs_find_file(): ino: %u\n", ino));
1707
1708         for (tmp = c->hash[i].next; tmp != &c->hash[i]; tmp = tmp->next) {
1709                 f = list_entry(tmp, struct jffs_file, hash);
1710                 if (ino != f->ino)
1711                         continue;
1712                 D3(printk("jffs_find_file(): Found file with ino "
1713                                "%u. (name: \"%s\")\n",
1714                                ino, (f->name ? f->name : ""));
1715                 );
1716                 return f;
1717         }
1718         D3(printk("jffs_find_file(): Didn't find file "
1719                          "with ino %u.\n", ino);
1720         );
1721         return NULL;
1722 }
1723
1724
1725 /* Find a file in a directory.  We are comparing the names.  */
1726 struct jffs_file *
1727 jffs_find_child(struct jffs_file *dir, const char *name, int len)
1728 {
1729         struct jffs_file *f;
1730
1731         D3(printk("jffs_find_child()\n"));
1732
1733         for (f = dir->children; f; f = f->sibling_next) {
1734                 if (!f->deleted && f->name
1735                     && !strncmp(f->name, name, len)
1736                     && f->name[len] == '\0') {
1737                         break;
1738                 }
1739         }
1740
1741         D3(if (f) {
1742                 printk("jffs_find_child(): Found \"%s\".\n", f->name);
1743         }
1744         else {
1745                 char *copy = (char *) kmalloc(len + 1, GFP_KERNEL);
1746                 if (copy) {
1747                         memcpy(copy, name, len);
1748                         copy[len] = '\0';
1749                 }
1750                 printk("jffs_find_child(): Didn't find the file \"%s\".\n",
1751                        (copy ? copy : ""));
1752                 if (copy) {
1753                         kfree(copy);
1754                 }
1755         });
1756
1757         return f;
1758 }
1759
1760
1761 /* Write a raw inode that takes up a certain amount of space in the flash
1762    memory.  At the end of the flash device, there is often space that is
1763    impossible to use.  At these times we want to mark this space as not
1764    used.  In the cases when the amount of space is greater or equal than
1765    a struct jffs_raw_inode, we write a "dummy node" that takes up this
1766    space.  The space after the raw inode, if it exists, is left as it is.
1767    Since this space after the raw inode contains JFFS_EMPTY_BITMASK bytes,
1768    we can compute the checksum of it; we don't have to manipulate it any
1769    further.
1770
1771    If the space left on the device is less than the size of a struct
1772    jffs_raw_inode, this space is filled with JFFS_DIRTY_BITMASK bytes.
1773    No raw inode is written this time.  */
1774 static int
1775 jffs_write_dummy_node(struct jffs_control *c, struct jffs_fm *dirty_fm)
1776 {
1777         struct jffs_fmcontrol *fmc = c->fmc;
1778         int err;
1779
1780         D1(printk("jffs_write_dummy_node(): dirty_fm->offset = 0x%08x, "
1781                   "dirty_fm->size = %u\n",
1782                   dirty_fm->offset, dirty_fm->size));
1783
1784         if (dirty_fm->size >= sizeof(struct jffs_raw_inode)) {
1785                 struct jffs_raw_inode raw_inode;
1786                 memset(&raw_inode, 0, sizeof(struct jffs_raw_inode));
1787                 raw_inode.magic = JFFS_MAGIC_BITMASK;
1788                 raw_inode.dsize = dirty_fm->size
1789                                   - sizeof(struct jffs_raw_inode);
1790                 raw_inode.dchksum = raw_inode.dsize * 0xff;
1791                 raw_inode.chksum
1792                 = jffs_checksum(&raw_inode, sizeof(struct jffs_raw_inode));
1793
1794                 if ((err = flash_safe_write(fmc->mtd,
1795                                             dirty_fm->offset,
1796                                             (u_char *)&raw_inode,
1797                                             sizeof(struct jffs_raw_inode)))
1798                     < 0) {
1799                         printk(KERN_ERR "JFFS: jffs_write_dummy_node: "
1800                                "flash_safe_write failed!\n");
1801                         return err;
1802                 }
1803         }
1804         else {
1805                 flash_safe_acquire(fmc->mtd);
1806                 flash_memset(fmc->mtd, dirty_fm->offset, 0, dirty_fm->size);
1807                 flash_safe_release(fmc->mtd);
1808         }
1809
1810         D3(printk("jffs_write_dummy_node(): Leaving...\n"));
1811         return 0;
1812 }
1813
1814
1815 /* Write a raw inode, possibly its name and possibly some data.  */
1816 int
1817 jffs_write_node(struct jffs_control *c, struct jffs_node *node,
1818                 struct jffs_raw_inode *raw_inode,
1819                 const char *name, const unsigned char *data,
1820                 int recoverable,
1821                 struct jffs_file *f)
1822 {
1823         struct jffs_fmcontrol *fmc = c->fmc;
1824         struct jffs_fm *fm;
1825         struct kvec node_iovec[4];
1826         unsigned long iovec_cnt;
1827
1828         __u32 pos;
1829         int err;
1830         __u32 slack = 0;
1831
1832         __u32 total_name_size = raw_inode->nsize
1833                                 + JFFS_GET_PAD_BYTES(raw_inode->nsize);
1834         __u32 total_data_size = raw_inode->dsize
1835                                 + JFFS_GET_PAD_BYTES(raw_inode->dsize);
1836         __u32 total_size = sizeof(struct jffs_raw_inode)
1837                            + total_name_size + total_data_size;
1838
1839         /* If this node isn't something that will eventually let
1840            GC free even more space, then don't allow it unless
1841            there's at least max_chunk_size space still available
1842         */
1843         if (!recoverable)
1844                 slack = fmc->max_chunk_size;
1845
1846
1847         /* Fire the retrorockets and shoot the fruiton torpedoes, sir!  */
1848
1849         ASSERT(if (!node) {
1850                 printk("jffs_write_node(): node == NULL\n");
1851                 return -EINVAL;
1852         });
1853         ASSERT(if (raw_inode && raw_inode->nsize && !name) {
1854                 printk("*** jffs_write_node(): nsize = %u but name == NULL\n",
1855                        raw_inode->nsize);
1856                 return -EINVAL;
1857         });
1858
1859         D1(printk("jffs_write_node(): filename = \"%s\", ino = %u, "
1860                   "total_size = %u\n",
1861                   (name ? name : ""), raw_inode->ino,
1862                   total_size));
1863
1864         jffs_fm_write_lock(fmc);
1865
1866 retry:
1867         fm = NULL;
1868         err = 0;
1869         while (!fm) {
1870
1871                 /* Deadlocks suck. */
1872                 while(fmc->free_size < fmc->min_free_size + total_size + slack) {
1873                         jffs_fm_write_unlock(fmc);
1874                         if (!JFFS_ENOUGH_SPACE(c, total_size + slack))
1875                                 return -ENOSPC;
1876                         jffs_fm_write_lock(fmc);
1877                 }
1878
1879                 /* First try to allocate some flash memory.  */
1880                 err = jffs_fmalloc(fmc, total_size, node, &fm);
1881
1882                 if (err == -ENOSPC) {
1883                         /* Just out of space. GC and try again */
1884                         if (fmc->dirty_size < fmc->sector_size) {
1885                                 D(printk("jffs_write_node(): jffs_fmalloc(0x%p, %u) "
1886                                          "failed, no dirty space to GC\n", fmc,
1887                                          total_size));
1888                                 return err;
1889                         }
1890
1891                         D1(printk(KERN_INFO "jffs_write_node(): Calling jffs_garbage_collect_now()\n"));
1892                         jffs_fm_write_unlock(fmc);
1893                         if ((err = jffs_garbage_collect_now(c))) {
1894                                 D(printk("jffs_write_node(): jffs_garbage_collect_now() failed\n"));
1895                                 return err;
1896                         }
1897                         jffs_fm_write_lock(fmc);
1898                         continue;
1899                 }
1900
1901                 if (err < 0) {
1902                         jffs_fm_write_unlock(fmc);
1903
1904                         D(printk("jffs_write_node(): jffs_fmalloc(0x%p, %u) "
1905                                  "failed!\n", fmc, total_size));
1906                         return err;
1907                 }
1908
1909                 if (!fm->nodes) {
1910                         /* The jffs_fm struct that we got is not good enough.
1911                            Make that space dirty and try again  */
1912                         if ((err = jffs_write_dummy_node(c, fm)) < 0) {
1913                                 kfree(fm);
1914                                 DJM(no_jffs_fm--);
1915                                 jffs_fm_write_unlock(fmc);
1916                                 D(printk("jffs_write_node(): "
1917                                          "jffs_write_dummy_node(): Failed!\n"));
1918                                 return err;
1919                         }
1920                         fm = NULL;
1921                 }
1922         } /* while(!fm) */
1923         node->fm = fm;
1924
1925         ASSERT(if (fm->nodes == 0) {
1926                 printk(KERN_ERR "jffs_write_node(): fm->nodes == 0\n");
1927         });
1928
1929         pos = node->fm->offset;
1930
1931         /* Increment the version number here. We can't let the caller
1932            set it beforehand, because we might have had to do GC on a node
1933            of this file - and we'd end up reusing version numbers.
1934         */
1935         if (f) {
1936                 raw_inode->version = f->highest_version + 1;
1937                 D1(printk (KERN_NOTICE "jffs_write_node(): setting version of %s to %d\n", f->name, raw_inode->version));
1938
1939                 /* if the file was deleted, set the deleted bit in the raw inode */
1940                 if (f->deleted)
1941                         raw_inode->deleted = 1;
1942         }
1943
1944         /* Compute the checksum for the data and name chunks.  */
1945         raw_inode->dchksum = jffs_checksum(data, raw_inode->dsize);
1946         raw_inode->nchksum = jffs_checksum(name, raw_inode->nsize);
1947
1948         /* The checksum is calculated without the chksum and accurate
1949            fields so set them to zero first.  */
1950         raw_inode->accurate = 0;
1951         raw_inode->chksum = 0;
1952         raw_inode->chksum = jffs_checksum(raw_inode,
1953                                           sizeof(struct jffs_raw_inode));
1954         raw_inode->accurate = 0xff;
1955
1956         D3(printk("jffs_write_node(): About to write this raw inode to the "
1957                   "flash at pos 0x%lx:\n", (long)pos));
1958         D3(jffs_print_raw_inode(raw_inode));
1959
1960         /* The actual raw JFFS node */
1961         node_iovec[0].iov_base = (void *) raw_inode;
1962         node_iovec[0].iov_len = (size_t) sizeof(struct jffs_raw_inode);
1963         iovec_cnt = 1;
1964
1965         /* Get name and size if there is one */
1966         if (raw_inode->nsize) {
1967                 node_iovec[iovec_cnt].iov_base = (void *) name;
1968                 node_iovec[iovec_cnt].iov_len = (size_t) raw_inode->nsize;
1969                 iovec_cnt++;
1970
1971                 if (JFFS_GET_PAD_BYTES(raw_inode->nsize)) {
1972                         static char allff[3]={255,255,255};
1973                         /* Add some extra padding if necessary */
1974                         node_iovec[iovec_cnt].iov_base = allff;
1975                         node_iovec[iovec_cnt].iov_len =
1976                                 JFFS_GET_PAD_BYTES(raw_inode->nsize);
1977                         iovec_cnt++;
1978                 }
1979         }
1980
1981         /* Get data and size if there is any */
1982         if (raw_inode->dsize) {
1983                 node_iovec[iovec_cnt].iov_base = (void *) data;
1984                 node_iovec[iovec_cnt].iov_len = (size_t) raw_inode->dsize;
1985                 iovec_cnt++;
1986                 /* No need to pad this because we're not actually putting
1987                    anything after it.
1988                 */
1989         }
1990
1991         if ((err = flash_safe_writev(fmc->mtd, node_iovec, iovec_cnt,
1992                                     pos)) < 0) {
1993                 jffs_fmfree_partly(fmc, fm, 0);
1994                 jffs_fm_write_unlock(fmc);
1995                 printk(KERN_ERR "JFFS: jffs_write_node: Failed to write, "
1996                        "requested %i, wrote %i\n", total_size, err);
1997                 goto retry;
1998         }
1999         if (raw_inode->deleted)
2000                 f->deleted = 1;
2001
2002         jffs_fm_write_unlock(fmc);
2003         D3(printk("jffs_write_node(): Leaving...\n"));
2004         return raw_inode->dsize;
2005 } /* jffs_write_node()  */
2006
2007
2008 /* Read data from the node and write it to the buffer.  'node_offset'
2009    is how much we have read from this particular node before and which
2010    shouldn't be read again.  'max_size' is how much space there is in
2011    the buffer.  */
2012 static int
2013 jffs_get_node_data(struct jffs_file *f, struct jffs_node *node,
2014                    unsigned char *buf,__u32 node_offset, __u32 max_size)
2015 {
2016         struct jffs_fmcontrol *fmc = f->c->fmc;
2017         __u32 pos = node->fm->offset + node->fm_offset + node_offset;
2018         __u32 avail = node->data_size - node_offset;
2019         __u32 r;
2020
2021         D2(printk("  jffs_get_node_data(): file: \"%s\", ino: %u, "
2022                   "version: %u, node_offset: %u\n",
2023                   f->name, node->ino, node->version, node_offset));
2024
2025         r = min(avail, max_size);
2026         D3(printk(KERN_NOTICE "jffs_get_node_data\n"));
2027         flash_safe_read(fmc->mtd, pos, buf, r);
2028
2029         D3(printk("  jffs_get_node_data(): Read %u byte%s.\n",
2030                   r, (r == 1 ? "" : "s")));
2031
2032         return r;
2033 }
2034
2035
2036 /* Read data from the file's nodes.  Write the data to the buffer
2037    'buf'.  'read_offset' tells how much data we should skip.  */
2038 int
2039 jffs_read_data(struct jffs_file *f, unsigned char *buf, __u32 read_offset,
2040                __u32 size)
2041 {
2042         struct jffs_node *node;
2043         __u32 read_data = 0; /* Total amount of read data.  */
2044         __u32 node_offset = 0;
2045         __u32 pos = 0; /* Number of bytes traversed.  */
2046
2047         D2(printk("jffs_read_data(): file = \"%s\", read_offset = %d, "
2048                   "size = %u\n",
2049                   (f->name ? f->name : ""), read_offset, size));
2050
2051         if (read_offset >= f->size) {
2052                 D(printk("  f->size: %d\n", f->size));
2053                 return 0;
2054         }
2055
2056         /* First find the node to read data from.  */
2057         node = f->range_head;
2058         while (pos <= read_offset) {
2059                 node_offset = read_offset - pos;
2060                 if (node_offset >= node->data_size) {
2061                         pos += node->data_size;
2062                         node = node->range_next;
2063                 }
2064                 else {
2065                         break;
2066                 }
2067         }
2068
2069         /* "Cats are living proof that not everything in nature
2070            has to be useful."
2071            - Garrison Keilor ('97)  */
2072
2073         /* Fill the buffer.  */
2074         while (node && (read_data < size)) {
2075                 int r;
2076                 if (!node->fm) {
2077                         /* This node does not refer to real data.  */
2078                         r = min(size - read_data,
2079                                      node->data_size - node_offset);
2080                         memset(&buf[read_data], 0, r);
2081                 }
2082                 else if ((r = jffs_get_node_data(f, node, &buf[read_data],
2083                                                  node_offset,
2084                                                  size - read_data)) < 0) {
2085                         return r;
2086                 }
2087                 read_data += r;
2088                 node_offset = 0;
2089                 node = node->range_next;
2090         }
2091         D3(printk("  jffs_read_data(): Read %u bytes.\n", read_data));
2092         return read_data;
2093 }
2094
2095
2096 /* Used for traversing all nodes in the hash table.  */
2097 int
2098 jffs_foreach_file(struct jffs_control *c, int (*func)(struct jffs_file *))
2099 {
2100         int pos;
2101         int r;
2102         int result = 0;
2103
2104         for (pos = 0; pos < c->hash_len; pos++) {
2105                 struct list_head *p, *next;
2106                 for (p = c->hash[pos].next; p != &c->hash[pos]; p = next) {
2107                         /* We need a reference to the next file in the
2108                            list because `func' might remove the current
2109                            file `f'.  */
2110                         next = p->next;
2111                         r = func(list_entry(p, struct jffs_file, hash));
2112                         if (r < 0)
2113                                 return r;
2114                         result += r;
2115                 }
2116         }
2117
2118         return result;
2119 }
2120
2121
2122 /* Free all nodes associated with a file.  */
2123 static int
2124 jffs_free_node_list(struct jffs_file *f)
2125 {
2126         struct jffs_node *node;
2127         struct jffs_node *p;
2128
2129         D3(printk("jffs_free_node_list(): f #%u, \"%s\"\n",
2130                   f->ino, (f->name ? f->name : "")));
2131         node = f->version_head;
2132         while (node) {
2133                 p = node;
2134                 node = node->version_next;
2135                 jffs_free_node(p);
2136                 DJM(no_jffs_node--);
2137         }
2138         return 0;
2139 }
2140
2141
2142 /* Free a file and its name.  */
2143 static int
2144 jffs_free_file(struct jffs_file *f)
2145 {
2146         D3(printk("jffs_free_file: f #%u, \"%s\"\n",
2147                   f->ino, (f->name ? f->name : "")));
2148
2149         if (f->name) {
2150                 kfree(f->name);
2151                 DJM(no_name--);
2152         }
2153         kfree(f);
2154         no_jffs_file--;
2155         return 0;
2156 }
2157
2158 static long
2159 jffs_get_file_count(void)
2160 {
2161         return no_jffs_file;
2162 }
2163
2164 /* See if a file is deleted. If so, mark that file's nodes as obsolete.  */
2165 int
2166 jffs_possibly_delete_file(struct jffs_file *f)
2167 {
2168         struct jffs_node *n;
2169
2170         D3(printk("jffs_possibly_delete_file(): ino: %u\n",
2171                   f->ino));
2172
2173         ASSERT(if (!f) {
2174                 printk(KERN_ERR "jffs_possibly_delete_file(): f == NULL\n");
2175                 return -1;
2176         });
2177
2178         if (f->deleted) {
2179                 /* First try to remove all older versions.  Commence with
2180                    the oldest node.  */
2181                 for (n = f->version_head; n; n = n->version_next) {
2182                         if (!n->fm) {
2183                                 continue;
2184                         }
2185                         if (jffs_fmfree(f->c->fmc, n->fm, n) < 0) {
2186                                 break;
2187                         }
2188                 }
2189                 /* Unlink the file from the filesystem.  */
2190                 if (!f->c->building_fs) {
2191                         jffs_unlink_file_from_tree(f);
2192                 }
2193                 jffs_unlink_file_from_hash(f);
2194                 jffs_free_node_list(f);
2195                 jffs_free_file(f);
2196         }
2197         return 0;
2198 }
2199
2200
2201 /* Used in conjunction with jffs_foreach_file() to count the number
2202    of files in the file system.  */
2203 int
2204 jffs_file_count(struct jffs_file *f)
2205 {
2206         return 1;
2207 }
2208
2209
2210 /* Build up a file's range list from scratch by going through the
2211    version list.  */
2212 static int
2213 jffs_build_file(struct jffs_file *f)
2214 {
2215         struct jffs_node *n;
2216
2217         D3(printk("jffs_build_file(): ino: %u, name: \"%s\"\n",
2218                   f->ino, (f->name ? f->name : "")));
2219
2220         for (n = f->version_head; n; n = n->version_next) {
2221                 jffs_update_file(f, n);
2222         }
2223         return 0;
2224 }
2225
2226
2227 /* Remove an amount of data from a file. If this amount of data is
2228    zero, that could mean that a node should be split in two parts.
2229    We remove or change the appropriate nodes in the lists.
2230
2231    Starting offset of area to be removed is node->data_offset,
2232    and the length of the area is in node->removed_size.   */
2233 static int
2234 jffs_delete_data(struct jffs_file *f, struct jffs_node *node)
2235 {
2236         struct jffs_node *n;
2237         __u32 offset = node->data_offset;
2238         __u32 remove_size = node->removed_size;
2239
2240         D3(printk("jffs_delete_data(): offset = %u, remove_size = %u\n",
2241                   offset, remove_size));
2242
2243         if (remove_size == 0
2244             && f->range_tail
2245             && f->range_tail->data_offset + f->range_tail->data_size
2246                == offset) {
2247                 /* A simple append; nothing to remove or no node to split.  */
2248                 return 0;
2249         }
2250
2251         /* Find the node where we should begin the removal.  */
2252         for (n = f->range_head; n; n = n->range_next) {
2253                 if (n->data_offset + n->data_size > offset) {
2254                         break;
2255                 }
2256         }
2257         if (!n) {
2258                 /* If there's no data in the file there's no data to
2259                    remove either.  */
2260                 return 0;
2261         }
2262
2263         if (n->data_offset > offset) {
2264                 /* XXX: Not implemented yet.  */
2265                 printk(KERN_WARNING "JFFS: An unexpected situation "
2266                        "occurred in jffs_delete_data.\n");
2267         }
2268         else if (n->data_offset < offset) {
2269                 /* See if the node has to be split into two parts.  */
2270                 if (n->data_offset + n->data_size > offset + remove_size) {
2271                         /* Do the split.  */
2272                         struct jffs_node *new_node;
2273                         D3(printk("jffs_delete_data(): Split node with "
2274                                   "version number %u.\n", n->version));
2275
2276                         if (!(new_node = jffs_alloc_node())) {
2277                                 D(printk("jffs_delete_data(): -ENOMEM\n"));
2278                                 return -ENOMEM;
2279                         }
2280                         DJM(no_jffs_node++);
2281
2282                         new_node->ino = n->ino;
2283                         new_node->version = n->version;
2284                         new_node->data_offset = offset;
2285                         new_node->data_size = n->data_size - (remove_size + (offset - n->data_offset));
2286                         new_node->fm_offset = n->fm_offset + (remove_size + (offset - n->data_offset));
2287                         new_node->name_size = n->name_size;
2288                         new_node->fm = n->fm;
2289                         new_node->version_prev = n;
2290                         new_node->version_next = n->version_next;
2291                         if (new_node->version_next) {
2292                                 new_node->version_next->version_prev
2293                                 = new_node;
2294                         }
2295                         else {
2296                                 f->version_tail = new_node;
2297                         }
2298                         n->version_next = new_node;
2299                         new_node->range_prev = n;
2300                         new_node->range_next = n->range_next;
2301                         if (new_node->range_next) {
2302                                 new_node->range_next->range_prev = new_node;
2303                         }
2304                         else {
2305                                 f->range_tail = new_node;
2306                         }
2307                         /* A very interesting can of worms.  */
2308                         n->range_next = new_node;
2309                         n->data_size = offset - n->data_offset;
2310                         if (new_node->fm)
2311                                 jffs_add_node(new_node);
2312                         else {
2313                                 D1(printk(KERN_WARNING "jffs_delete_data(): Splitting an empty node (file hold).\n!"));
2314                                 D1(printk(KERN_WARNING "FIXME: Did dwmw2 do the right thing here?\n"));
2315                         }
2316                         n = new_node->range_next;
2317                         remove_size = 0;
2318                 }
2319                 else {
2320                         /* No.  No need to split the node.  Just remove
2321                            the end of the node.  */
2322                         int r = min(n->data_offset + n->data_size
2323                                          - offset, remove_size);
2324                         n->data_size -= r;
2325                         remove_size -= r;
2326                         n = n->range_next;
2327                 }
2328         }
2329
2330         /* Remove as many nodes as necessary.  */
2331         while (n && remove_size) {
2332                 if (n->data_size <= remove_size) {
2333                         struct jffs_node *p = n;
2334                         remove_size -= n->data_size;
2335                         n = n->range_next;
2336                         D3(printk("jffs_delete_data(): Removing node: "
2337                                   "ino: %u, version: %u%s\n",
2338                                   p->ino, p->version,
2339                                   (p->fm ? "" : " (virtual)")));
2340                         if (p->fm) {
2341                                 jffs_fmfree(f->c->fmc, p->fm, p);
2342                         }
2343                         jffs_unlink_node_from_range_list(f, p);
2344                         jffs_unlink_node_from_version_list(f, p);
2345                         jffs_free_node(p);
2346                         DJM(no_jffs_node--);
2347                 }
2348                 else {
2349                         n->data_size -= remove_size;
2350                         n->fm_offset += remove_size;
2351                         n->data_offset -= (node->removed_size - remove_size);
2352                         n = n->range_next;
2353                         break;
2354                 }
2355         }
2356
2357         /* Adjust the following nodes' information about offsets etc.  */
2358         while (n && node->removed_size) {
2359                 n->data_offset -= node->removed_size;
2360                 n = n->range_next;
2361         }
2362
2363         if (node->removed_size > (f->size - node->data_offset)) {
2364                 /* It's possible that the removed_size is in fact
2365                  * greater than the amount of data we actually thought
2366                  * were present in the first place - some of the nodes
2367                  * which this node originally obsoleted may already have
2368                  * been deleted from the flash by subsequent garbage
2369                  * collection.
2370                  *
2371                  * If this is the case, don't let f->size go negative.
2372                  * Bad things would happen :)
2373                  */
2374                 f->size = node->data_offset;
2375         } else {
2376                 f->size -= node->removed_size;
2377         }
2378         D3(printk("jffs_delete_data(): f->size = %d\n", f->size));
2379         return 0;
2380 } /* jffs_delete_data()  */
2381
2382
2383 /* Insert some data into a file.  Prior to the call to this function,
2384    jffs_delete_data should be called.  */
2385 static int
2386 jffs_insert_data(struct jffs_file *f, struct jffs_node *node)
2387 {
2388         D3(printk("jffs_insert_data(): node->data_offset = %u, "
2389                   "node->data_size = %u, f->size = %u\n",
2390                   node->data_offset, node->data_size, f->size));
2391
2392         /* Find the position where we should insert data.  */
2393         retry:
2394         if (node->data_offset == f->size) {
2395                 /* A simple append.  This is the most common operation.  */
2396                 node->range_next = NULL;
2397                 node->range_prev = f->range_tail;
2398                 if (node->range_prev) {
2399                         node->range_prev->range_next = node;
2400                 }
2401                 f->range_tail = node;
2402                 f->size += node->data_size;
2403                 if (!f->range_head) {
2404                         f->range_head = node;
2405                 }
2406         }
2407         else if (node->data_offset < f->size) {
2408                 /* Trying to insert data into the middle of the file.  This
2409                    means no problem because jffs_delete_data() has already
2410                    prepared the range list for us.  */
2411                 struct jffs_node *n;
2412
2413                 /* Find the correct place for the insertion and then insert
2414                    the node.  */
2415                 for (n = f->range_head; n; n = n->range_next) {
2416                         D2(printk("Cool stuff's happening!\n"));
2417
2418                         if (n->data_offset == node->data_offset) {
2419                                 node->range_prev = n->range_prev;
2420                                 if (node->range_prev) {
2421                                         node->range_prev->range_next = node;
2422                                 }
2423                                 else {
2424                                         f->range_head = node;
2425                                 }
2426                                 node->range_next = n;
2427                                 n->range_prev = node;
2428                                 break;
2429                         }
2430                         ASSERT(else if (n->data_offset + n->data_size >
2431                                         node->data_offset) {
2432                                 printk(KERN_ERR "jffs_insert_data(): "
2433                                        "Couldn't find a place to insert "
2434                                        "the data!\n");
2435                                 return -1;
2436                         });
2437                 }
2438
2439                 /* Adjust later nodes' offsets etc.  */
2440                 n = node->range_next;
2441                 while (n) {
2442                         n->data_offset += node->data_size;
2443                         n = n->range_next;
2444                 }
2445                 f->size += node->data_size;
2446         }
2447         else if (node->data_offset > f->size) {
2448                 /* Okay.  This is tricky.  This means that we want to insert
2449                    data at a place that is beyond the limits of the file as
2450                    it is constructed right now.  This is actually a common
2451                    event that for instance could occur during the mounting
2452                    of the file system if a large file have been truncated,
2453                    rewritten and then only partially garbage collected.  */
2454
2455                 struct jffs_node *n;
2456
2457                 /* We need a place holder for the data that is missing in
2458                    front of this insertion.  This "virtual node" will not
2459                    be associated with any space on the flash device.  */
2460                 struct jffs_node *virtual_node;
2461                 if (!(virtual_node = jffs_alloc_node())) {
2462                         return -ENOMEM;
2463                 }
2464
2465                 D(printk("jffs_insert_data: Inserting a virtual node.\n"));
2466                 D(printk("  node->data_offset = %u\n", node->data_offset));
2467                 D(printk("  f->size = %u\n", f->size));
2468
2469                 virtual_node->ino = node->ino;
2470                 virtual_node->version = node->version;
2471                 virtual_node->removed_size = 0;
2472                 virtual_node->fm_offset = 0;
2473                 virtual_node->name_size = 0;
2474                 virtual_node->fm = NULL; /* This is a virtual data holder.  */
2475                 virtual_node->version_prev = NULL;
2476                 virtual_node->version_next = NULL;
2477                 virtual_node->range_next = NULL;
2478
2479                 /* Are there any data at all in the file yet?  */
2480                 if (f->range_head) {
2481                         virtual_node->data_offset
2482                         = f->range_tail->data_offset
2483                           + f->range_tail->data_size;
2484                         virtual_node->data_size
2485                         = node->data_offset - virtual_node->data_offset;
2486                         virtual_node->range_prev = f->range_tail;
2487                         f->range_tail->range_next = virtual_node;
2488                 }
2489                 else {
2490                         virtual_node->data_offset = 0;
2491                         virtual_node->data_size = node->data_offset;
2492                         virtual_node->range_prev = NULL;
2493                         f->range_head = virtual_node;
2494                 }
2495
2496                 f->range_tail = virtual_node;
2497                 f->size += virtual_node->data_size;
2498
2499                 /* Insert this virtual node in the version list as well.  */
2500                 for (n = f->version_head; n ; n = n->version_next) {
2501                         if (n->version == virtual_node->version) {
2502                                 virtual_node->version_prev = n->version_prev;
2503                                 n->version_prev = virtual_node;
2504                                 if (virtual_node->version_prev) {
2505                                         virtual_node->version_prev
2506                                         ->version_next = virtual_node;
2507                                 }
2508                                 else {
2509                                         f->version_head = virtual_node;
2510                                 }
2511                                 virtual_node->version_next = n;
2512                                 break;
2513                         }
2514                 }
2515
2516                 D(jffs_print_node(virtual_node));
2517
2518                 /* Make a new try to insert the node.  */
2519                 goto retry;
2520         }
2521
2522         D3(printk("jffs_insert_data(): f->size = %d\n", f->size));
2523         return 0;
2524 }
2525
2526
2527 /* A new node (with data) has been added to the file and now the range
2528    list has to be modified.  */
2529 static int
2530 jffs_update_file(struct jffs_file *f, struct jffs_node *node)
2531 {
2532         int err;
2533
2534         D3(printk("jffs_update_file(): ino: %u, version: %u\n",
2535                   f->ino, node->version));
2536
2537         if (node->data_size == 0) {
2538                 if (node->removed_size == 0) {
2539                         /* data_offset == X  */
2540                         /* data_size == 0  */
2541                         /* remove_size == 0  */
2542                 }
2543                 else {
2544                         /* data_offset == X  */
2545                         /* data_size == 0  */
2546                         /* remove_size != 0  */
2547                         if ((err = jffs_delete_data(f, node)) < 0) {
2548                                 return err;
2549                         }
2550                 }
2551         }
2552         else {
2553                 /* data_offset == X  */
2554                 /* data_size != 0  */
2555                 /* remove_size == Y  */
2556                 if ((err = jffs_delete_data(f, node)) < 0) {
2557                         return err;
2558                 }
2559                 if ((err = jffs_insert_data(f, node)) < 0) {
2560                         return err;
2561                 }
2562         }
2563         return 0;
2564 }
2565
2566 /* Print the contents of a file.  */
2567 #if 0
2568 int
2569 jffs_print_file(struct jffs_file *f)
2570 {
2571         D(int i);
2572         D(printk("jffs_file: 0x%p\n", f));
2573         D(printk("{\n"));
2574         D(printk("        0x%08x, /* ino  */\n", f->ino));
2575         D(printk("        0x%08x, /* pino  */\n", f->pino));
2576         D(printk("        0x%08x, /* mode  */\n", f->mode));
2577         D(printk("        0x%04x,     /* uid  */\n", f->uid));
2578         D(printk("        0x%04x,     /* gid  */\n", f->gid));
2579         D(printk("        0x%08x, /* atime  */\n", f->atime));
2580         D(printk("        0x%08x, /* mtime  */\n", f->mtime));
2581         D(printk("        0x%08x, /* ctime  */\n", f->ctime));
2582         D(printk("        0x%02x,       /* nsize  */\n", f->nsize));
2583         D(printk("        0x%02x,       /* nlink  */\n", f->nlink));
2584         D(printk("        0x%02x,       /* deleted  */\n", f->deleted));
2585         D(printk("        \"%s\", ", (f->name ? f->name : "")));
2586         D(for (i = strlen(f->name ? f->name : ""); i < 8; ++i) {
2587                 printk(" ");
2588         });
2589         D(printk("/* name  */\n"));
2590         D(printk("        0x%08x, /* size  */\n", f->size));
2591         D(printk("        0x%08x, /* highest_version  */\n",
2592                  f->highest_version));
2593         D(printk("        0x%p, /* c  */\n", f->c));
2594         D(printk("        0x%p, /* parent  */\n", f->parent));
2595         D(printk("        0x%p, /* children  */\n", f->children));
2596         D(printk("        0x%p, /* sibling_prev  */\n", f->sibling_prev));
2597         D(printk("        0x%p, /* sibling_next  */\n", f->sibling_next));
2598         D(printk("        0x%p, /* hash_prev  */\n", f->hash.prev));
2599         D(printk("        0x%p, /* hash_next  */\n", f->hash.next));
2600         D(printk("        0x%p, /* range_head  */\n", f->range_head));
2601         D(printk("        0x%p, /* range_tail  */\n", f->range_tail));
2602         D(printk("        0x%p, /* version_head  */\n", f->version_head));
2603         D(printk("        0x%p, /* version_tail  */\n", f->version_tail));
2604         D(printk("}\n"));
2605         return 0;
2606 }
2607 #endif  /*  0  */
2608
2609 void
2610 jffs_print_hash_table(struct jffs_control *c)
2611 {
2612         int i;
2613
2614         printk("JFFS: Dumping the file system's hash table...\n");
2615         for (i = 0; i < c->hash_len; i++) {
2616                 struct list_head *p;
2617                 for (p = c->hash[i].next; p != &c->hash[i]; p = p->next) {
2618                         struct jffs_file *f=list_entry(p,struct jffs_file,hash);
2619                         printk("*** c->hash[%u]: \"%s\" "
2620                                "(ino: %u, pino: %u)\n",
2621                                i, (f->name ? f->name : ""),
2622                                f->ino, f->pino);
2623                 }
2624         }
2625 }
2626
2627
2628 void
2629 jffs_print_tree(struct jffs_file *first_file, int indent)
2630 {
2631         struct jffs_file *f;
2632         char *space;
2633         int dir;
2634
2635         if (!first_file) {
2636                 return;
2637         }
2638
2639         if (!(space = (char *) kmalloc(indent + 1, GFP_KERNEL))) {
2640                 printk("jffs_print_tree(): Out of memory!\n");
2641                 return;
2642         }
2643
2644         memset(space, ' ', indent);
2645         space[indent] = '\0';
2646
2647         for (f = first_file; f; f = f->sibling_next) {
2648                 dir = S_ISDIR(f->mode);
2649                 printk("%s%s%s (ino: %u, highest_version: %u, size: %u)\n",
2650                        space, (f->name ? f->name : ""), (dir ? "/" : ""),
2651                        f->ino, f->highest_version, f->size);
2652                 if (dir) {
2653                         jffs_print_tree(f->children, indent + 2);
2654                 }
2655         }
2656
2657         kfree(space);
2658 }
2659
2660
2661 #if defined(JFFS_MEMORY_DEBUG) && JFFS_MEMORY_DEBUG
2662 void
2663 jffs_print_memory_allocation_statistics(void)
2664 {
2665         static long printout;
2666         printk("________ Memory printout #%ld ________\n", ++printout);
2667         printk("no_jffs_file = %ld\n", no_jffs_file);
2668         printk("no_jffs_node = %ld\n", no_jffs_node);
2669         printk("no_jffs_control = %ld\n", no_jffs_control);
2670         printk("no_jffs_raw_inode = %ld\n", no_jffs_raw_inode);
2671         printk("no_jffs_node_ref = %ld\n", no_jffs_node_ref);
2672         printk("no_jffs_fm = %ld\n", no_jffs_fm);
2673         printk("no_jffs_fmcontrol = %ld\n", no_jffs_fmcontrol);
2674         printk("no_hash = %ld\n", no_hash);
2675         printk("no_name = %ld\n", no_name);
2676         printk("\n");
2677 }
2678 #endif
2679
2680
2681 /* Rewrite `size' bytes, and begin at `node'.  */
2682 static int
2683 jffs_rewrite_data(struct jffs_file *f, struct jffs_node *node, __u32 size)
2684 {
2685         struct jffs_control *c = f->c;
2686         struct jffs_fmcontrol *fmc = c->fmc;
2687         struct jffs_raw_inode raw_inode;
2688         struct jffs_node *new_node;
2689         struct jffs_fm *fm;
2690         __u32 pos;
2691         __u32 pos_dchksum;
2692         __u32 total_name_size;
2693         __u32 total_data_size;
2694         __u32 total_size;
2695         int err;
2696
2697         D1(printk("***jffs_rewrite_data(): node: %u, name: \"%s\", size: %u\n",
2698                   f->ino, (f->name ? f->name : "(null)"), size));
2699
2700         /* Create and initialize the new node.  */
2701         if (!(new_node = jffs_alloc_node())) {
2702                 D(printk("jffs_rewrite_data(): "
2703                          "Failed to allocate node.\n"));
2704                 return -ENOMEM;
2705         }
2706         DJM(no_jffs_node++);
2707         new_node->data_offset = node->data_offset;
2708         new_node->removed_size = size;
2709         total_name_size = JFFS_PAD(f->nsize);
2710         total_data_size = JFFS_PAD(size);
2711         total_size = sizeof(struct jffs_raw_inode)
2712                      + total_name_size + total_data_size;
2713         new_node->fm_offset = sizeof(struct jffs_raw_inode)
2714                               + total_name_size;
2715
2716 retry:
2717         jffs_fm_write_lock(fmc);
2718         err = 0;
2719
2720         if ((err = jffs_fmalloc(fmc, total_size, new_node, &fm)) < 0) {
2721                 DJM(no_jffs_node--);
2722                 jffs_fm_write_unlock(fmc);
2723                 D(printk("jffs_rewrite_data(): Failed to allocate fm.\n"));
2724                 jffs_free_node(new_node);
2725                 return err;
2726         }
2727         else if (!fm->nodes) {
2728                 /* The jffs_fm struct that we got is not big enough.  */
2729                 /* This should never happen, because we deal with this case
2730                    in jffs_garbage_collect_next().*/
2731                 printk(KERN_WARNING "jffs_rewrite_data(): Allocated node is too small (%d bytes of %d)\n", fm->size, total_size);
2732                 if ((err = jffs_write_dummy_node(c, fm)) < 0) {
2733                         D(printk("jffs_rewrite_data(): "
2734                                  "jffs_write_dummy_node() Failed!\n"));
2735                 } else {
2736                         err = -ENOSPC;
2737                 }
2738                 DJM(no_jffs_fm--);
2739                 jffs_fm_write_unlock(fmc);
2740                 kfree(fm);
2741
2742                 return err;
2743         }
2744         new_node->fm = fm;
2745
2746         /* Initialize the raw inode.  */
2747         raw_inode.magic = JFFS_MAGIC_BITMASK;
2748         raw_inode.ino = f->ino;
2749         raw_inode.pino = f->pino;
2750         raw_inode.version = f->highest_version + 1;
2751         raw_inode.mode = f->mode;
2752         raw_inode.uid = f->uid;
2753         raw_inode.gid = f->gid;
2754         raw_inode.atime = f->atime;
2755         raw_inode.mtime = f->mtime;
2756         raw_inode.ctime = f->ctime;
2757         raw_inode.offset = node->data_offset;
2758         raw_inode.dsize = size;
2759         raw_inode.rsize = size;
2760         raw_inode.nsize = f->nsize;
2761         raw_inode.nlink = f->nlink;
2762         raw_inode.spare = 0;
2763         raw_inode.rename = 0;
2764         raw_inode.deleted = f->deleted;
2765         raw_inode.accurate = 0xff;
2766         raw_inode.dchksum = 0;
2767         raw_inode.nchksum = 0;
2768
2769         pos = new_node->fm->offset;
2770         pos_dchksum = pos +JFFS_RAW_INODE_DCHKSUM_OFFSET;
2771
2772         D3(printk("jffs_rewrite_data(): Writing this raw inode "
2773                   "to pos 0x%ul.\n", pos));
2774         D3(jffs_print_raw_inode(&raw_inode));
2775
2776         if ((err = flash_safe_write(fmc->mtd, pos,
2777                                     (u_char *) &raw_inode,
2778                                     sizeof(struct jffs_raw_inode)
2779                                     - sizeof(__u32)
2780                                     - sizeof(__u16) - sizeof(__u16))) < 0) {
2781                 jffs_fmfree_partly(fmc, fm,
2782                                    total_name_size + total_data_size);
2783                 jffs_fm_write_unlock(fmc);
2784                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Write error during "
2785                         "rewrite. (raw inode)\n");
2786                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Now retrying "
2787                         "rewrite. (raw inode)\n");
2788                 goto retry;
2789         }
2790         pos += sizeof(struct jffs_raw_inode);
2791
2792         /* Write the name to the flash memory.  */
2793         if (f->nsize) {
2794                 D3(printk("jffs_rewrite_data(): Writing name \"%s\" to "
2795                           "pos 0x%ul.\n", f->name, (unsigned int) pos));
2796                 if ((err = flash_safe_write(fmc->mtd, pos,
2797                                             (u_char *)f->name,
2798                                             f->nsize)) < 0) {
2799                         jffs_fmfree_partly(fmc, fm, total_data_size);
2800                         jffs_fm_write_unlock(fmc);
2801                         printk(KERN_ERR "JFFS: jffs_rewrite_data: Write "
2802                                 "error during rewrite. (name)\n");
2803                         printk(KERN_ERR "JFFS: jffs_rewrite_data: Now retrying "
2804                                 "rewrite. (name)\n");
2805                         goto retry;
2806                 }
2807                 pos += total_name_size;
2808                 raw_inode.nchksum = jffs_checksum(f->name, f->nsize);
2809         }
2810
2811         /* Write the data.  */
2812         if (size) {
2813                 int r;
2814                 unsigned char *page;
2815                 __u32 offset = node->data_offset;
2816
2817                 if (!(page = (unsigned char *)__get_free_page(GFP_KERNEL))) {
2818                         jffs_fmfree_partly(fmc, fm, 0);
2819                         return -1;
2820                 }
2821
2822                 while (size) {
2823                         __u32 s = min(size, (__u32)PAGE_SIZE);
2824                         if ((r = jffs_read_data(f, (char *)page,
2825                                                 offset, s)) < s) {
2826                                 free_page((unsigned long)page);
2827                                 jffs_fmfree_partly(fmc, fm, 0);
2828                                 jffs_fm_write_unlock(fmc);
2829                                 printk(KERN_ERR "JFFS: jffs_rewrite_data: "
2830                                          "jffs_read_data() "
2831                                          "failed! (r = %d)\n", r);
2832                                 return -1;
2833                         }
2834                         if ((err = flash_safe_write(fmc->mtd,
2835                                                     pos, page, r)) < 0) {
2836                                 free_page((unsigned long)page);
2837                                 jffs_fmfree_partly(fmc, fm, 0);
2838                                 jffs_fm_write_unlock(fmc);
2839                                 printk(KERN_ERR "JFFS: jffs_rewrite_data: "
2840                                        "Write error during rewrite. "
2841                                        "(data)\n");
2842                                 goto retry;
2843                         }
2844                         pos += r;
2845                         size -= r;
2846                         offset += r;
2847                         raw_inode.dchksum += jffs_checksum(page, r);
2848                 }
2849
2850                 free_page((unsigned long)page);
2851         }
2852
2853         raw_inode.accurate = 0;
2854         raw_inode.chksum = jffs_checksum(&raw_inode,
2855                                          sizeof(struct jffs_raw_inode)
2856                                          - sizeof(__u16));
2857
2858         /* Add the checksum.  */
2859         if ((err
2860              = flash_safe_write(fmc->mtd, pos_dchksum,
2861                                 &((u_char *)
2862                                 &raw_inode)[JFFS_RAW_INODE_DCHKSUM_OFFSET],
2863                                 sizeof(__u32) + sizeof(__u16)
2864                                 + sizeof(__u16))) < 0) {
2865                 jffs_fmfree_partly(fmc, fm, 0);
2866                 jffs_fm_write_unlock(fmc);
2867                 printk(KERN_ERR "JFFS: jffs_rewrite_data: Write error during "
2868                        "rewrite. (checksum)\n");
2869                 goto retry;
2870         }
2871
2872         /* Now make the file system aware of the newly written node.  */
2873         jffs_insert_node(c, f, &raw_inode, f->name, new_node);
2874         jffs_fm_write_unlock(fmc);
2875
2876         D3(printk("jffs_rewrite_data(): Leaving...\n"));
2877         return 0;
2878 } /* jffs_rewrite_data()  */
2879
2880
2881 /* jffs_garbage_collect_next implements one step in the garbage collect
2882    process and is often called multiple times at each occasion of a
2883    garbage collect.  */
2884
2885 static int
2886 jffs_garbage_collect_next(struct jffs_control *c)
2887 {
2888         struct jffs_fmcontrol *fmc = c->fmc;
2889         struct jffs_node *node;
2890         struct jffs_file *f;
2891         int err = 0;
2892         __u32 size;
2893         __u32 data_size;
2894         __u32 total_name_size;
2895         __u32 extra_available;
2896         __u32 space_needed;
2897         __u32 free_chunk_size1 = jffs_free_size1(fmc);
2898         D2(__u32 free_chunk_size2 = jffs_free_size2(fmc));
2899
2900         /* Get the oldest node in the flash.  */
2901         node = jffs_get_oldest_node(fmc);
2902         ASSERT(if (!node) {
2903                 printk(KERN_ERR "JFFS: jffs_garbage_collect_next: "
2904                        "No oldest node found!\n");
2905                 err = -1;
2906                 goto jffs_garbage_collect_next_end;
2907
2908
2909         });
2910
2911         /* Find its corresponding file too.  */
2912         f = jffs_find_file(c, node->ino);
2913
2914         if (!f) {
2915           printk (KERN_ERR "JFFS: jffs_garbage_collect_next: "
2916                   "No file to garbage collect! "
2917                   "(ino = 0x%08x)\n", node->ino);
2918           /* FIXME: Free the offending node and recover. */
2919           err = -1;
2920           goto jffs_garbage_collect_next_end;
2921         }
2922
2923         /* We always write out the name. Theoretically, we don't need
2924            to, but for now it's easier - because otherwise we'd have
2925            to keep track of how many times the current name exists on
2926            the flash and make sure it never reaches zero.
2927
2928            The current approach means that would be possible to cause
2929            the GC to end up eating its tail by writing lots of nodes
2930            with no name for it to garbage-collect. Hence the change in
2931            inode.c to write names with _every_ node.
2932
2933            It sucks, but it _should_ work.
2934         */
2935         total_name_size = JFFS_PAD(f->nsize);
2936
2937         D1(printk("jffs_garbage_collect_next(): \"%s\", "
2938                   "ino: %u, version: %u, location 0x%x, dsize %u\n",
2939                   (f->name ? f->name : ""), node->ino, node->version,
2940                   node->fm->offset, node->data_size));
2941
2942         /* Compute how many data it's possible to rewrite at the moment.  */
2943         data_size = f->size - node->data_offset;
2944
2945         /* And from that, the total size of the chunk we want to write */
2946         size = sizeof(struct jffs_raw_inode) + total_name_size
2947                + data_size + JFFS_GET_PAD_BYTES(data_size);
2948
2949         /* If that's more than max_chunk_size, reduce it accordingly */
2950         if (size > fmc->max_chunk_size) {
2951                 size = fmc->max_chunk_size;
2952                 data_size = size - sizeof(struct jffs_raw_inode)
2953                             - total_name_size;
2954         }
2955
2956         /* If we're asking to take up more space than free_chunk_size1
2957            but we _could_ fit in it, shrink accordingly.
2958         */
2959         if (size > free_chunk_size1) {
2960
2961                 if (free_chunk_size1 <
2962                     (sizeof(struct jffs_raw_inode) + total_name_size + BLOCK_SIZE)){
2963                         /* The space left is too small to be of any
2964                            use really.  */
2965                         struct jffs_fm *dirty_fm
2966                         = jffs_fmalloced(fmc,
2967                                          fmc->tail->offset + fmc->tail->size,
2968                                          free_chunk_size1, NULL);
2969                         if (!dirty_fm) {
2970                                 printk(KERN_ERR "JFFS: "
2971                                        "jffs_garbage_collect_next: "
2972                                        "Failed to allocate `dirty' "
2973                                        "flash memory!\n");
2974                                 err = -1;
2975                                 goto jffs_garbage_collect_next_end;
2976                         }
2977                         D1(printk("Dirtying end of flash - too small\n"));
2978                         jffs_write_dummy_node(c, dirty_fm);
2979                         err = 0;
2980                         goto jffs_garbage_collect_next_end;
2981                 }
2982                 D1(printk("Reducing size of new node from %d to %d to avoid "
2983                           " exceeding free_chunk_size1\n",
2984                           size, free_chunk_size1));
2985
2986                 size = free_chunk_size1;
2987                 data_size = size - sizeof(struct jffs_raw_inode)
2988                             - total_name_size;
2989         }
2990
2991
2992         /* Calculate the amount of space needed to hold the nodes
2993            which are remaining in the tail */
2994         space_needed = fmc->min_free_size - (node->fm->offset % fmc->sector_size);
2995
2996         /* From that, calculate how much 'extra' space we can use to
2997            increase the size of the node we're writing from the size
2998            of the node we're obsoleting
2999         */
3000         if (space_needed > fmc->free_size) {
3001                 /* If we've gone below min_free_size for some reason,
3002                    don't fuck up. This is why we have
3003                    min_free_size > sector_size. Whinge about it though,
3004                    just so I can convince myself my maths is right.
3005                 */
3006                 D1(printk(KERN_WARNING "jffs_garbage_collect_next(): "
3007                           "space_needed %d exceeded free_size %d\n",
3008                           space_needed, fmc->free_size));
3009                 extra_available = 0;
3010         } else {
3011                 extra_available = fmc->free_size - space_needed;
3012         }
3013
3014         /* Check that we don't use up any more 'extra' space than
3015            what's available */
3016         if (size > JFFS_PAD(node->data_size) + total_name_size +
3017             sizeof(struct jffs_raw_inode) + extra_available) {
3018                 D1(printk("Reducing size of new node from %d to %ld to avoid "
3019                        "catching our tail\n", size,
3020                           (long) (JFFS_PAD(node->data_size) + JFFS_PAD(node->name_size) +
3021                           sizeof(struct jffs_raw_inode) + extra_available)));
3022                 D1(printk("space_needed = %d, extra_available = %d\n",
3023                           space_needed, extra_available));
3024
3025                 size = JFFS_PAD(node->data_size) + total_name_size +
3026                   sizeof(struct jffs_raw_inode) + extra_available;
3027                 data_size = size - sizeof(struct jffs_raw_inode)
3028                         - total_name_size;
3029         };
3030
3031         D2(printk("  total_name_size: %u\n", total_name_size));
3032         D2(printk("  data_size: %u\n", data_size));
3033         D2(printk("  size: %u\n", size));
3034         D2(printk("  f->nsize: %u\n", f->nsize));
3035         D2(printk("  f->size: %u\n", f->size));
3036         D2(printk("  node->data_offset: %u\n", node->data_offset));
3037         D2(printk("  free_chunk_size1: %u\n", free_chunk_size1));
3038         D2(printk("  free_chunk_size2: %u\n", free_chunk_size2));
3039         D2(printk("  node->fm->offset: 0x%08x\n", node->fm->offset));
3040
3041         if ((err = jffs_rewrite_data(f, node, data_size))) {
3042                 printk(KERN_WARNING "jffs_rewrite_data() failed: %d\n", err);
3043                 return err;
3044         }
3045
3046 jffs_garbage_collect_next_end:
3047         D3(printk("jffs_garbage_collect_next: Leaving...\n"));
3048         return err;
3049 } /* jffs_garbage_collect_next */
3050
3051
3052 /* If an obsolete node is partly going to be erased due to garbage
3053    collection, the part that isn't going to be erased must be filled
3054    with zeroes so that the scan of the flash will work smoothly next
3055    time.  (The data in the file could for instance be a JFFS image
3056    which could cause enormous confusion during a scan of the flash
3057    device if we didn't do this.)
3058      There are two phases in this procedure: First, the clearing of
3059    the name and data parts of the node. Second, possibly also clearing
3060    a part of the raw inode as well.  If the box is power cycled during
3061    the first phase, only the checksum of this node-to-be-cleared-at-
3062    the-end will be wrong.  If the box is power cycled during, or after,
3063    the clearing of the raw inode, the information like the length of
3064    the name and data parts are zeroed.  The next time the box is
3065    powered up, the scanning algorithm manages this faulty data too
3066    because:
3067
3068    - The checksum is invalid and thus the raw inode must be discarded
3069      in any case.
3070    - If the lengths of the data part or the name part are zeroed, the
3071      scanning just continues after the raw inode.  But after the inode
3072      the scanning procedure just finds zeroes which is the same as
3073      dirt.
3074
3075    So, in the end, this could never fail. :-)  Even if it does fail,
3076    the scanning algorithm should manage that too.  */
3077
3078 static int
3079 jffs_clear_end_of_node(struct jffs_control *c, __u32 erase_size)
3080 {
3081         struct jffs_fm *fm;
3082         struct jffs_fmcontrol *fmc = c->fmc;
3083         __u32 zero_offset;
3084         __u32 zero_size;
3085         __u32 zero_offset_data;
3086         __u32 zero_size_data;
3087         __u32 cutting_raw_inode = 0;
3088
3089         if (!(fm = jffs_cut_node(fmc, erase_size))) {
3090                 D3(printk("jffs_clear_end_of_node(): fm == NULL\n"));
3091                 return 0;
3092         }
3093
3094         /* Where and how much shall we clear?  */
3095         zero_offset = fmc->head->offset + erase_size;
3096         zero_size = fm->offset + fm->size - zero_offset;
3097
3098         /* Do we have to clear the raw_inode explicitly?  */
3099         if (fm->size - zero_size < sizeof(struct jffs_raw_inode)) {
3100                 cutting_raw_inode = sizeof(struct jffs_raw_inode)
3101                                     - (fm->size - zero_size);
3102         }
3103
3104         /* First, clear the name and data fields.  */
3105         zero_offset_data = zero_offset + cutting_raw_inode;
3106         zero_size_data = zero_size - cutting_raw_inode;
3107         flash_safe_acquire(fmc->mtd);
3108         flash_memset(fmc->mtd, zero_offset_data, 0, zero_size_data);
3109         flash_safe_release(fmc->mtd);
3110
3111         /* Should we clear a part of the raw inode?  */
3112         if (cutting_raw_inode) {
3113                 /* I guess it is ok to clear the raw inode in this order.  */
3114                 flash_safe_acquire(fmc->mtd);
3115                 flash_memset(fmc->mtd, zero_offset, 0,
3116                              cutting_raw_inode);
3117                 flash_safe_release(fmc->mtd);
3118         }
3119
3120         return 0;
3121 } /* jffs_clear_end_of_node()  */
3122
3123 /* Try to erase as much as possible of the dirt in the flash memory.  */
3124 static long
3125 jffs_try_to_erase(struct jffs_control *c)
3126 {
3127         struct jffs_fmcontrol *fmc = c->fmc;
3128         long erase_size;
3129         int err;
3130         __u32 offset;
3131
3132         D3(printk("jffs_try_to_erase()\n"));
3133
3134         erase_size = jffs_erasable_size(fmc);
3135
3136         D2(printk("jffs_try_to_erase(): erase_size = %ld\n", erase_size));
3137
3138         if (erase_size == 0) {
3139                 return 0;
3140         }
3141         else if (erase_size < 0) {
3142                 printk(KERN_ERR "JFFS: jffs_try_to_erase: "
3143                        "jffs_erasable_size returned %ld.\n", erase_size);
3144                 return erase_size;
3145         }
3146
3147         if ((err = jffs_clear_end_of_node(c, erase_size)) < 0) {
3148                 printk(KERN_ERR "JFFS: jffs_try_to_erase: "
3149                        "Clearing of node failed.\n");
3150                 return err;
3151         }
3152
3153         offset = fmc->head->offset;
3154
3155         /* Now, let's try to do the erase.  */
3156         if ((err = flash_erase_region(fmc->mtd,
3157                                       offset, erase_size)) < 0) {
3158                 printk(KERN_ERR "JFFS: Erase of flash failed. "
3159                        "offset = %u, erase_size = %ld\n",
3160                        offset, erase_size);
3161                 /* XXX: Here we should allocate this area as dirty
3162                    with jffs_fmalloced or something similar.  Now
3163                    we just report the error.  */
3164                 return err;
3165         }
3166
3167 #if 0
3168         /* Check if the erased sectors really got erased.  */
3169         {
3170                 __u32 pos;
3171                 __u32 end;
3172
3173                 pos = (__u32)flash_get_direct_pointer(to_kdev_t(c->sb->s_dev), offset);
3174                 end = pos + erase_size;
3175
3176                 D2(printk("JFFS: Checking erased sector(s)...\n"));
3177
3178                 flash_safe_acquire(fmc->mtd);
3179
3180                 for (; pos < end; pos += 4) {
3181                         if (*(__u32 *)pos != JFFS_EMPTY_BITMASK) {
3182                                 printk("JFFS: Erase failed! pos = 0x%lx\n",
3183                                        (long)pos);
3184                                 jffs_hexdump(fmc->mtd, pos,
3185                                              jffs_min(256, end - pos));
3186                                 err = -1;
3187                                 break;
3188                         }
3189                 }
3190
3191                 flash_safe_release(fmc->mtd);
3192
3193                 if (!err) {
3194                         D2(printk("JFFS: Erase succeeded.\n"));
3195                 }
3196                 else {
3197                         /* XXX: Here we should allocate the memory
3198                            with jffs_fmalloced() in order to prevent
3199                            JFFS from using this area accidentally.  */
3200                         return err;
3201                 }
3202         }
3203 #endif
3204
3205         /* Update the flash memory data structures.  */
3206         jffs_sync_erase(fmc, erase_size);
3207
3208         return erase_size;
3209 }
3210
3211
3212 /* There are different criteria that should trigger a garbage collect:
3213
3214    1. There is too much dirt in the memory.
3215    2. The free space is becoming small.
3216    3. There are many versions of a node.
3217
3218    The garbage collect should always be done in a manner that guarantees
3219    that future garbage collects cannot be locked.  E.g. Rewritten chunks
3220    should not be too large (span more than one sector in the flash memory
3221    for exemple).  Of course there is a limit on how intelligent this garbage
3222    collection can be.  */
3223
3224
3225 static int
3226 jffs_garbage_collect_now(struct jffs_control *c)
3227 {
3228         struct jffs_fmcontrol *fmc = c->fmc;
3229         long erased = 0;
3230         int result = 0;
3231         D1(int i = 1);
3232         D2(printk("***jffs_garbage_collect_now(): fmc->dirty_size = %u, fmc->free_size = 0x%x\n, fcs1=0x%x, fcs2=0x%x",
3233                   fmc->dirty_size, fmc->free_size, jffs_free_size1(fmc), jffs_free_size2(fmc)));
3234         D2(jffs_print_fmcontrol(fmc));
3235
3236         //      down(&fmc->gclock);
3237
3238         /* If it is possible to garbage collect, do so.  */
3239
3240         while (erased == 0) {
3241                 D1(printk("***jffs_garbage_collect_now(): round #%u, "
3242                           "fmc->dirty_size = %u\n", i++, fmc->dirty_size));
3243                 D2(jffs_print_fmcontrol(fmc));
3244
3245                 if ((erased = jffs_try_to_erase(c)) < 0) {
3246                         printk(KERN_WARNING "JFFS: Error in "
3247                                "garbage collector.\n");
3248                         result = erased;
3249                         goto gc_end;
3250                 }
3251                 if (erased)
3252                         break;
3253
3254                 if (fmc->free_size == 0) {
3255                         /* Argh */
3256                         printk(KERN_ERR "jffs_garbage_collect_now(): free_size == 0. This is BAD.\n");
3257                         result = -ENOSPC;
3258                         break;
3259                 }
3260
3261                 if (fmc->dirty_size < fmc->sector_size) {
3262                         /* Actually, we _may_ have been able to free some,
3263                          * if there are many overlapping nodes which aren't
3264                          * actually marked dirty because they still have
3265                          * some valid data in each.
3266                          */
3267                         result = -ENOSPC;
3268                         break;
3269                 }
3270
3271                 /* Let's dare to make a garbage collect.  */
3272                 if ((result = jffs_garbage_collect_next(c)) < 0) {
3273                         printk(KERN_ERR "JFFS: Something "
3274                                "has gone seriously wrong "
3275                                "with a garbage collect.\n");
3276                         goto gc_end;
3277                 }
3278
3279                 D1(printk("   jffs_garbage_collect_now(): erased: %ld\n", erased));
3280                 DJM(jffs_print_memory_allocation_statistics());
3281         }
3282
3283 gc_end:
3284         //      up(&fmc->gclock);
3285
3286         D3(printk("   jffs_garbage_collect_now(): Leaving...\n"));
3287         D1(if (erased) {
3288                 printk("jffs_g_c_now(): erased = %ld\n", erased);
3289                 jffs_print_fmcontrol(fmc);
3290         });
3291
3292         if (!erased && !result)
3293                 return -ENOSPC;
3294
3295         return result;
3296 } /* jffs_garbage_collect_now() */
3297
3298
3299 /* Determine if it is reasonable to start garbage collection.
3300    We start a gc pass if either:
3301    - The number of free bytes < MIN_FREE_BYTES && at least one
3302      block is dirty, OR
3303    - The number of dirty bytes > MAX_DIRTY_BYTES
3304 */
3305 static inline int thread_should_wake (struct jffs_control *c)
3306 {
3307         D1(printk (KERN_NOTICE "thread_should_wake(): free=%d, dirty=%d, blocksize=%d.\n",
3308                    c->fmc->free_size, c->fmc->dirty_size, c->fmc->sector_size));
3309
3310         /* If there's not enough dirty space to free a block, there's no point. */
3311         if (c->fmc->dirty_size < c->fmc->sector_size) {
3312                 D2(printk(KERN_NOTICE "thread_should_wake(): Not waking. Insufficient dirty space\n"));
3313                 return 0;
3314         }
3315 #if 1
3316         /* If there is too much RAM used by the various structures, GC */
3317         if (jffs_get_node_inuse() > (c->fmc->used_size/c->fmc->max_chunk_size * 5 + jffs_get_file_count() * 2 + 50)) {
3318                 /* FIXME: Provide proof that this test can be satisfied. We
3319                    don't want a filesystem doing endless GC just because this
3320                    condition cannot ever be false.
3321                 */
3322                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to number of nodes\n"));
3323                 return 1;
3324         }
3325 #endif
3326         /* If there are fewer free bytes than the threshold, GC */
3327         if (c->fmc->free_size < c->gc_minfree_threshold) {
3328                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to insufficent free space\n"));
3329                 return 1;
3330         }
3331         /* If there are more dirty bytes than the threshold, GC */
3332         if (c->fmc->dirty_size > c->gc_maxdirty_threshold) {
3333                 D2(printk(KERN_NOTICE "thread_should_wake(): Waking due to excessive dirty space\n"));
3334                 return 1;
3335         }
3336         /* FIXME: What about the "There are many versions of a node" condition? */
3337
3338         return 0;
3339 }
3340
3341
3342 void jffs_garbage_collect_trigger(struct jffs_control *c)
3343 {
3344         /* NOTE: We rely on the fact that we have the BKL here.
3345          * Otherwise, the gc_task could go away between the check
3346          * and the wake_up_process()
3347          */
3348         if (c->gc_task && thread_should_wake(c))
3349                 send_sig(SIGHUP, c->gc_task, 1);
3350 }
3351
3352
3353 /* Kernel threads  take (void *) as arguments.   Thus we pass
3354    the jffs_control data as a (void *) and then cast it. */
3355 int
3356 jffs_garbage_collect_thread(void *ptr)
3357 {
3358         struct jffs_control *c = (struct jffs_control *) ptr;
3359         struct jffs_fmcontrol *fmc = c->fmc;
3360         long erased;
3361         int result = 0;
3362         D1(int i = 1);
3363
3364         daemonize("jffs_gcd");
3365
3366         c->gc_task = current;
3367
3368         lock_kernel();
3369         init_completion(&c->gc_thread_comp); /* barrier */
3370         spin_lock_irq(&current->sighand->siglock);
3371         siginitsetinv (&current->blocked, sigmask(SIGHUP) | sigmask(SIGKILL) | sigmask(SIGSTOP) | sigmask(SIGCONT));
3372         recalc_sigpending();
3373         spin_unlock_irq(&current->sighand->siglock);
3374
3375         D1(printk (KERN_NOTICE "jffs_garbage_collect_thread(): Starting infinite loop.\n"));
3376
3377         for (;;) {
3378
3379                 /* See if we need to start gc.  If we don't, go to sleep.
3380
3381                    Current implementation is a BAD THING(tm).  If we try
3382                    to unmount the FS, the unmount operation will sleep waiting
3383                    for this thread to exit.  We need to arrange to send it a
3384                    sig before the umount process sleeps.
3385                 */
3386
3387                 if (!thread_should_wake(c))
3388                         set_current_state (TASK_INTERRUPTIBLE);
3389
3390                 schedule(); /* Yes, we do this even if we want to go
3391                                        on immediately - we're a low priority
3392                                        background task. */
3393
3394                 /* Put_super will send a SIGKILL and then wait on the sem.
3395                  */
3396                 while (signal_pending(current)) {
3397                         siginfo_t info;
3398                         unsigned long signr = 0;
3399
3400                         spin_lock_irq(&current->sighand->siglock);
3401                         signr = dequeue_signal(current, &current->blocked, &info);
3402                         spin_unlock_irq(&current->sighand->siglock);
3403
3404                         switch(signr) {
3405                         case SIGSTOP:
3406                                 D1(printk("jffs_garbage_collect_thread(): SIGSTOP received.\n"));
3407                                 set_current_state(TASK_STOPPED);
3408                                 schedule();
3409                                 break;
3410
3411                         case SIGKILL:
3412                                 D1(printk("jffs_garbage_collect_thread(): SIGKILL received.\n"));
3413                                 c->gc_task = NULL;
3414                                 complete_and_exit(&c->gc_thread_comp, 0);
3415                         }
3416                 }
3417
3418
3419                 D1(printk (KERN_NOTICE "jffs_garbage_collect_thread(): collecting.\n"));
3420
3421                 D3(printk (KERN_NOTICE "g_c_thread(): down biglock\n"));
3422                 down(&fmc->biglock);
3423
3424                 D1(printk("***jffs_garbage_collect_thread(): round #%u, "
3425                           "fmc->dirty_size = %u\n", i++, fmc->dirty_size));
3426                 D2(jffs_print_fmcontrol(fmc));
3427
3428                 if ((erased = jffs_try_to_erase(c)) < 0) {
3429                         printk(KERN_WARNING "JFFS: Error in "
3430                                "garbage collector: %ld.\n", erased);
3431                 }
3432
3433                 if (erased)
3434                         goto gc_end;
3435
3436                 if (fmc->free_size == 0) {
3437                         /* Argh. Might as well commit suicide. */
3438                         printk(KERN_ERR "jffs_garbage_collect_thread(): free_size == 0. This is BAD.\n");
3439                         send_sig(SIGQUIT, c->gc_task, 1);
3440                         // panic()
3441                         goto gc_end;
3442                 }
3443
3444                 /* Let's dare to make a garbage collect.  */
3445                 if ((result = jffs_garbage_collect_next(c)) < 0) {
3446                         printk(KERN_ERR "JFFS: Something "
3447                                "has gone seriously wrong "
3448                                "with a garbage collect: %d\n", result);
3449                 }
3450
3451         gc_end:
3452                 D3(printk (KERN_NOTICE "g_c_thread(): up biglock\n"));
3453                 up(&fmc->biglock);
3454         } /* for (;;) */
3455 } /* jffs_garbage_collect_thread() */