fs/jffs/intrep.c

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