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