fs/jffs2/nodelist.c

   1 /*
   2  * JFFS2 -- Journalling Flash File System, Version 2.
   3  *
   4  * Copyright (C) 2001-2003 Red Hat, Inc.
   5  *
   6  * Created by David Woodhouse <dwmw2@infradead.org>
   7  *
   8  * For licensing information, see the file 'LICENCE' in this directory.
   9  *
  10  * $Id: nodelist.c,v 1.100 2005/07/22 10:32:08 dedekind Exp $
  11  *
  12  */
  13
  14 #include <linux/kernel.h>
  15 #include <linux/sched.h>
  16 #include <linux/fs.h>
  17 #include <linux/mtd/mtd.h>
  18 #include <linux/rbtree.h>
  19 #include <linux/crc32.h>
  20 #include <linux/slab.h>
  21 #include <linux/pagemap.h>
  22 #include "nodelist.h"
  23
  24 void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list)
  25 {
  26         struct jffs2_full_dirent **prev = list;
  27         D1(printk(KERN_DEBUG "jffs2_add_fd_to_list( %p, %p (->%p))\n", new, list, *list));
  28
  29         while ((*prev) && (*prev)->nhash <= new->nhash) {
  30                 if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) {
  31                         /* Duplicate. Free one */
  32                         if (new->version < (*prev)->version) {
  33                                 D1(printk(KERN_DEBUG "Eep! Marking new dirent node obsolete\n"));
  34                                 D1(printk(KERN_DEBUG "New dirent is \"%s\"->ino #%u. Old is \"%s\"->ino #%u\n", new->name, new->ino, (*prev)->name, (*prev)->ino));
  35                                 jffs2_mark_node_obsolete(c, new->raw);
  36                                 jffs2_free_full_dirent(new);
  37                         } else {
  38                                 D1(printk(KERN_DEBUG "Marking old dirent node (ino #%u) obsolete\n", (*prev)->ino));
  39                                 new->next = (*prev)->next;
  40                                 jffs2_mark_node_obsolete(c, ((*prev)->raw));
  41                                 jffs2_free_full_dirent(*prev);
  42                                 *prev = new;
  43                         }
  44                         goto out;
  45                 }
  46                 prev = &((*prev)->next);
  47         }
  48         new->next = *prev;
  49         *prev = new;
  50
  51  out:
  52         D2(while(*list) {
  53                 printk(KERN_DEBUG "Dirent \"%s\" (hash 0x%08x, ino #%u\n", (*list)->name, (*list)->nhash, (*list)->ino);
  54                 list = &(*list)->next;
  55         });
  56 }
  57
  58 /*
  59  * Put a new tmp_dnode_info into the temporaty RB-tree, keeping the list in
  60  * order of increasing version.
  61  */
  62 static void jffs2_add_tn_to_tree(struct jffs2_tmp_dnode_info *tn, struct rb_root *list)
  63 {
  64         struct rb_node **p = &list->rb_node;
  65         struct rb_node * parent = NULL;
  66         struct jffs2_tmp_dnode_info *this;
  67
  68         while (*p) {
  69                 parent = *p;
  70                 this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
  71
  72                 /* There may actually be a collision here, but it doesn't
  73                    actually matter. As long as the two nodes with the same
  74                    version are together, it's all fine. */
  75                 if (tn->version < this->version)
  76                         p = &(*p)->rb_left;
  77                 else
  78                         p = &(*p)->rb_right;
  79         }
  80
  81         rb_link_node(&tn->rb, parent, p);
  82         rb_insert_color(&tn->rb, list);
  83 }
  84
  85 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
  86 {
  87         struct rb_node *this;
  88         struct jffs2_tmp_dnode_info *tn;
  89
  90         this = list->rb_node;
  91
  92         /* Now at bottom of tree */
  93         while (this) {
  94                 if (this->rb_left)
  95                         this = this->rb_left;
  96                 else if (this->rb_right)
  97                         this = this->rb_right;
  98                 else {
  99                         tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
 100                         jffs2_free_full_dnode(tn->fn);
 101                         jffs2_free_tmp_dnode_info(tn);
 102
 103                         this = this->rb_parent;
 104                         if (!this)
 105                                 break;
 106
 107                         if (this->rb_left == &tn->rb)
 108                                 this->rb_left = NULL;
 109                         else if (this->rb_right == &tn->rb)
 110                                 this->rb_right = NULL;
 111                         else BUG();
 112                 }
 113         }
 114         list->rb_node = NULL;
 115 }
 116
 117 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
 118 {
 119         struct jffs2_full_dirent *next;
 120
 121         while (fd) {
 122                 next = fd->next;
 123                 jffs2_free_full_dirent(fd);
 124                 fd = next;
 125         }
 126 }
 127
 128 /* Returns first valid node after 'ref'. May return 'ref' */
 129 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
 130 {
 131         while (ref && ref->next_in_ino) {
 132                 if (!ref_obsolete(ref))
 133                         return ref;
 134                 D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref)));
 135                 ref = ref->next_in_ino;
 136         }
 137         return NULL;
 138 }
 139
 140 /*
 141  * Helper function for jffs2_get_inode_nodes().
 142  * It is called every time an directory entry node is found.
 143  *
 144  * Returns: 0 on succes;
 145  *          1 if the node should be marked obsolete;
 146  *          negative error code on failure.
 147  */
 148 static inline int
 149 read_direntry(struct jffs2_sb_info *c,
 150               struct jffs2_raw_node_ref *ref,
 151               struct jffs2_raw_dirent *rd,
 152               uint32_t read,
 153               struct jffs2_full_dirent **fdp,
 154               int32_t *latest_mctime,
 155               uint32_t *mctime_ver)
 156 {
 157         struct jffs2_full_dirent *fd;
 158
 159         /* The direntry nodes are checked during the flash scanning */
 160         BUG_ON(ref_flags(ref) == REF_UNCHECKED);
 161         /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
 162         BUG_ON(ref_obsolete(ref));
 163
 164         /* Sanity check */
 165         if (unlikely(PAD((rd->nsize + sizeof(*rd))) != PAD(je32_to_cpu(rd->totlen)))) {
 166                 printk(KERN_ERR "Error! Illegal nsize in node at %#08x: nsize %#02x, totlen %#04x\n",
 167                        ref_offset(ref), rd->nsize, je32_to_cpu(rd->totlen));
 168                 return 1;
 169         }
 170
 171         fd = jffs2_alloc_full_dirent(rd->nsize + 1);
 172         if (unlikely(!fd))
 173                 return -ENOMEM;
 174
 175         fd->raw = ref;
 176         fd->version = je32_to_cpu(rd->version);
 177         fd->ino = je32_to_cpu(rd->ino);
 178         fd->type = rd->type;
 179
 180         /* Pick out the mctime of the latest dirent */
 181         if(fd->version > *mctime_ver) {
 182                 *mctime_ver = fd->version;
 183                 *latest_mctime = je32_to_cpu(rd->mctime);
 184         }
 185
 186         /*
 187          * Copy as much of the name as possible from the raw
 188          * dirent we've already read from the flash.
 189          */
 190         if (read > sizeof(*rd))
 191                 memcpy(&fd->name[0], &rd->name[0],
 192                        min_t(uint32_t, rd->nsize, (read - sizeof(*rd)) ));
 193
 194         /* Do we need to copy any more of the name directly from the flash? */
 195         if (rd->nsize + sizeof(*rd) > read) {
 196                 /* FIXME: point() */
 197                 int err;
 198                 int already = read - sizeof(*rd);
 199
 200                 err = jffs2_flash_read(c, (ref_offset(ref)) + read,
 201                                 rd->nsize - already, &read, &fd->name[already]);
 202                 if (unlikely(read != rd->nsize - already) && likely(!err))
 203                         return -EIO;
 204
 205                 if (unlikely(err)) {
 206                         printk(KERN_WARNING "Read remainder of name: error %d\n", err);
 207                         jffs2_free_full_dirent(fd);
 208                         return -EIO;
 209                 }
 210         }
 211
 212         fd->nhash = full_name_hash(fd->name, rd->nsize);
 213         fd->next = NULL;
 214         fd->name[rd->nsize] = '\0';
 215
 216         /*
 217          * Wheee. We now have a complete jffs2_full_dirent structure, with
 218          * the name in it and everything. Link it into the list
 219          */
 220         D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino));
 221
 222         jffs2_add_fd_to_list(c, fd, fdp);
 223
 224         return 0;
 225 }
 226
 227 /*
 228  * Helper function for jffs2_get_inode_nodes().
 229  * It is called every time an inode node is found.
 230  *
 231  * Returns: 0 on succes;
 232  *          1 if the node should be marked obsolete;
 233  *          negative error code on failure.
 234  */
 235 static inline int
 236 read_dnode(struct jffs2_sb_info *c,
 237            struct jffs2_raw_node_ref *ref,
 238            struct jffs2_raw_inode *rd,
 239            uint32_t read,
 240            struct rb_root *tnp,
 241            int32_t *latest_mctime,
 242            uint32_t *mctime_ver)
 243 {
 244         struct jffs2_eraseblock *jeb;
 245         struct jffs2_tmp_dnode_info *tn;
 246
 247         /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
 248         BUG_ON(ref_obsolete(ref));
 249
 250         /* If we've never checked the CRCs on this node, check them now */
 251         if (ref_flags(ref) == REF_UNCHECKED) {
 252                 uint32_t crc, len;
 253
 254                 crc = crc32(0, rd, sizeof(*rd) - 8);
 255                 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
 256                         printk(KERN_WARNING "Header CRC failed on node at %#08x: read %#08x, calculated %#08x\n",
 257                                         ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
 258                         return 1;
 259                 }
 260
 261                 /* Sanity checks */
 262                 if (unlikely(je32_to_cpu(rd->offset) > je32_to_cpu(rd->isize)) ||
 263                     unlikely(PAD(je32_to_cpu(rd->csize) + sizeof(*rd)) != PAD(je32_to_cpu(rd->totlen)))) {
 264                         printk(KERN_WARNING "Inode corrupted at %#08x, totlen %d, #ino  %d, version %d, "
 265                                 "isize %d, csize %d, dsize %d \n",
 266                                 ref_offset(ref),  je32_to_cpu(rd->totlen),  je32_to_cpu(rd->ino),
 267                                 je32_to_cpu(rd->version),  je32_to_cpu(rd->isize),
 268                                 je32_to_cpu(rd->csize), je32_to_cpu(rd->dsize));
 269                         return 1;
 270                 }
 271
 272                 if (rd->compr != JFFS2_COMPR_ZERO && je32_to_cpu(rd->csize)) {
 273                         unsigned char *buf = NULL;
 274                         uint32_t pointed = 0;
 275                         int err;
 276 #ifndef __ECOS
 277                         if (c->mtd->point) {
 278                                 err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize),
 279                                                      &read, &buf);
 280                                 if (unlikely(read < je32_to_cpu(rd->csize)) && likely(!err)) {
 281                                         D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", read));
 282                                         c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(*rd),
 283                                                         je32_to_cpu(rd->csize));
 284                                 } else if (unlikely(err)){
 285                                         D1(printk(KERN_DEBUG "MTD point failed %d\n", err));
 286                                 } else
 287                                         pointed = 1; /* succefully pointed to device */
 288                         }
 289 #endif
 290                         if(!pointed){
 291                                 buf = kmalloc(je32_to_cpu(rd->csize), GFP_KERNEL);
 292                                 if (!buf)
 293                                         return -ENOMEM;
 294
 295                                 err = jffs2_flash_read(c, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize),
 296                                                         &read, buf);
 297                                 if (unlikely(read != je32_to_cpu(rd->csize)) && likely(!err))
 298                                         err = -EIO;
 299                                 if (err) {
 300                                         kfree(buf);
 301                                         return err;
 302                                 }
 303                         }
 304                         crc = crc32(0, buf, je32_to_cpu(rd->csize));
 305                         if(!pointed)
 306                                 kfree(buf);
 307 #ifndef __ECOS
 308                         else
 309                                 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(*rd), je32_to_cpu(rd->csize));
 310 #endif
 311
 312                         if (crc != je32_to_cpu(rd->data_crc)) {
 313                                 printk(KERN_NOTICE "Data CRC failed on node at %#08x: read %#08x, calculated %#08x\n",
 314                                        ref_offset(ref), je32_to_cpu(rd->data_crc), crc);
 315                                 return 1;
 316                         }
 317
 318                 }
 319
 320                 /* Mark the node as having been checked and fix the accounting accordingly */
 321                 jeb = &c->blocks[ref->flash_offset / c->sector_size];
 322                 len = ref_totlen(c, jeb, ref);
 323
 324                 spin_lock(&c->erase_completion_lock);
 325                 jeb->used_size += len;
 326                 jeb->unchecked_size -= len;
 327                 c->used_size += len;
 328                 c->unchecked_size -= len;
 329
 330                 /* If node covers at least a whole page, or if it starts at the
 331                    beginning of a page and runs to the end of the file, or if
 332                    it's a hole node, mark it REF_PRISTINE, else REF_NORMAL.
 333
 334                    If it's actually overlapped, it'll get made NORMAL (or OBSOLETE)
 335                    when the overlapping node(s) get added to the tree anyway.
 336                 */
 337                 if ((je32_to_cpu(rd->dsize) >= PAGE_CACHE_SIZE) ||
 338                     ( ((je32_to_cpu(rd->offset) & (PAGE_CACHE_SIZE-1))==0) &&
 339                       (je32_to_cpu(rd->dsize) + je32_to_cpu(rd->offset) == je32_to_cpu(rd->isize)))) {
 340                         D1(printk(KERN_DEBUG "Marking node at %#08x REF_PRISTINE\n", ref_offset(ref)));
 341                         ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
 342                 } else {
 343                         D1(printk(KERN_DEBUG "Marking node at %#08x REF_NORMAL\n", ref_offset(ref)));
 344                         ref->flash_offset = ref_offset(ref) | REF_NORMAL;
 345                 }
 346                 spin_unlock(&c->erase_completion_lock);
 347         }
 348
 349         tn = jffs2_alloc_tmp_dnode_info();
 350         if (!tn) {
 351                 D1(printk(KERN_DEBUG "alloc tn failed\n"));
 352                 return -ENOMEM;
 353         }
 354
 355         tn->fn = jffs2_alloc_full_dnode();
 356         if (!tn->fn) {
 357                 D1(printk(KERN_DEBUG "alloc fn failed\n"));
 358                 jffs2_free_tmp_dnode_info(tn);
 359                 return -ENOMEM;
 360         }
 361
 362         tn->version = je32_to_cpu(rd->version);
 363         tn->fn->ofs = je32_to_cpu(rd->offset);
 364         tn->fn->raw = ref;
 365
 366         /* There was a bug where we wrote hole nodes out with
 367            csize/dsize swapped. Deal with it */
 368         if (rd->compr == JFFS2_COMPR_ZERO && !je32_to_cpu(rd->dsize) && je32_to_cpu(rd->csize))
 369                 tn->fn->size = je32_to_cpu(rd->csize);
 370         else // normal case...
 371                 tn->fn->size = je32_to_cpu(rd->dsize);
 372
 373         D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %#04x, dsize %#04x\n",
 374                   ref_offset(ref), je32_to_cpu(rd->version),
 375                   je32_to_cpu(rd->offset), je32_to_cpu(rd->dsize)));
 376
 377         jffs2_add_tn_to_tree(tn, tnp);
 378
 379         return 0;
 380 }
 381
 382 /*
 383  * Helper function for jffs2_get_inode_nodes().
 384  * It is called every time an unknown node is found.
 385  *
 386  * Returns: 0 on succes;
 387  *          1 if the node should be marked obsolete;
 388  *          negative error code on failure.
 389  */
 390 static inline int
 391 read_unknown(struct jffs2_sb_info *c,
 392              struct jffs2_raw_node_ref *ref,
 393              struct jffs2_unknown_node *un,
 394              uint32_t read)
 395 {
 396         /* We don't mark unknown nodes as REF_UNCHECKED */
 397         BUG_ON(ref_flags(ref) == REF_UNCHECKED);
 398
 399         un->nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(un->nodetype));
 400
 401         if (crc32(0, un, sizeof(struct jffs2_unknown_node) - 4) != je32_to_cpu(un->hdr_crc)) {
 402
 403                 /* Hmmm. This should have been caught at scan time. */
 404                 printk(KERN_WARNING "Warning! Node header CRC failed at %#08x. "
 405                                 "But it must have been OK earlier.\n", ref_offset(ref));
 406                 D1(printk(KERN_DEBUG "Node was: { %#04x, %#04x, %#08x, %#08x }\n",
 407                         je16_to_cpu(un->magic), je16_to_cpu(un->nodetype),
 408                         je32_to_cpu(un->totlen), je32_to_cpu(un->hdr_crc)));
 409                 return 1;
 410         } else {
 411                 switch(je16_to_cpu(un->nodetype) & JFFS2_COMPAT_MASK) {
 412
 413                 case JFFS2_FEATURE_INCOMPAT:
 414                         printk(KERN_NOTICE "Unknown INCOMPAT nodetype %#04X at %#08x\n",
 415                                         je16_to_cpu(un->nodetype), ref_offset(ref));
 416                         /* EEP */
 417                         BUG();
 418                         break;
 419
 420                 case JFFS2_FEATURE_ROCOMPAT:
 421                         printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %#04X at %#08x\n",
 422                                         je16_to_cpu(un->nodetype), ref_offset(ref));
 423                         BUG_ON(!(c->flags & JFFS2_SB_FLAG_RO));
 424                         break;
 425
 426                 case JFFS2_FEATURE_RWCOMPAT_COPY:
 427                         printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %#04X at %#08x\n",
 428                                         je16_to_cpu(un->nodetype), ref_offset(ref));
 429                         break;
 430
 431                 case JFFS2_FEATURE_RWCOMPAT_DELETE:
 432                         printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %#04X at %#08x\n",
 433                                         je16_to_cpu(un->nodetype), ref_offset(ref));
 434                         return 1;
 435                 }
 436         }
 437
 438         return 0;
 439 }
 440
 441 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
 442    with this ino, returning the former in order of version */
 443
 444 int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 445                           struct rb_root *tnp, struct jffs2_full_dirent **fdp,
 446                           uint32_t *highest_version, uint32_t *latest_mctime,
 447                           uint32_t *mctime_ver)
 448 {
 449         struct jffs2_raw_node_ref *ref, *valid_ref;
 450         struct rb_root ret_tn = RB_ROOT;
 451         struct jffs2_full_dirent *ret_fd = NULL;
 452         union jffs2_node_union node;
 453         size_t retlen;
 454         int err;
 455
 456         *mctime_ver = 0;
 457
 458         D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino));
 459
 460         spin_lock(&c->erase_completion_lock);
 461
 462         valid_ref = jffs2_first_valid_node(f->inocache->nodes);
 463
 464         if (!valid_ref && (f->inocache->ino != 1))
 465                 printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino);
 466
 467         while (valid_ref) {
 468                 /* We can hold a pointer to a non-obsolete node without the spinlock,
 469                    but _obsolete_ nodes may disappear at any time, if the block
 470                    they're in gets erased. So if we mark 'ref' obsolete while we're
 471                    not holding the lock, it can go away immediately. For that reason,
 472                    we find the next valid node first, before processing 'ref'.
 473                 */
 474                 ref = valid_ref;
 475                 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
 476                 spin_unlock(&c->erase_completion_lock);
 477
 478                 cond_resched();
 479
 480                 /* FIXME: point() */
 481                 err = jffs2_flash_read(c, (ref_offset(ref)),
 482                                        min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)),
 483                                        &retlen, (void *)&node);
 484                 if (err) {
 485                         printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref));
 486                         goto free_out;
 487                 }
 488
 489                 switch (je16_to_cpu(node.u.nodetype)) {
 490
 491                 case JFFS2_NODETYPE_DIRENT:
 492                         D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref)));
 493
 494                         if (retlen < sizeof(node.d)) {
 495                                 printk(KERN_WARNING "Warning! Short read dirent at %#08x\n", ref_offset(ref));
 496                                 err = -EIO;
 497                                 goto free_out;
 498                         }
 499
 500                         err = read_direntry(c, ref, &node.d, retlen, &ret_fd, latest_mctime, mctime_ver);
 501                         if (err == 1) {
 502                                 jffs2_mark_node_obsolete(c, ref);
 503                                 break;
 504                         } else if (unlikely(err))
 505                                 goto free_out;
 506
 507                         if (je32_to_cpu(node.d.version) > *highest_version)
 508                                 *highest_version = je32_to_cpu(node.d.version);
 509
 510                         break;
 511
 512                 case JFFS2_NODETYPE_INODE:
 513                         D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref)));
 514
 515                         if (retlen < sizeof(node.i)) {
 516                                 printk(KERN_WARNING "Warning! Short read dnode at %#08x\n", ref_offset(ref));
 517                                 err = -EIO;
 518                                 goto free_out;
 519                         }
 520
 521                         err = read_dnode(c, ref, &node.i, retlen, &ret_tn, latest_mctime, mctime_ver);
 522                         if (err == 1) {
 523                                 jffs2_mark_node_obsolete(c, ref);
 524                                 break;
 525                         } else if (unlikely(err))
 526                                 goto free_out;
 527
 528                         if (je32_to_cpu(node.i.version) > *highest_version)
 529                                 *highest_version = je32_to_cpu(node.i.version);
 530
 531                         D1(printk(KERN_DEBUG "version %d, highest_version now %d\n",
 532                                         je32_to_cpu(node.i.version), *highest_version));
 533
 534                         break;
 535
 536                 default:
 537                         /* Check we've managed to read at least the common node header */
 538                         if (retlen < sizeof(struct jffs2_unknown_node)) {
 539                                 printk(KERN_WARNING "Warning! Short read unknown node at %#08x\n",
 540                                                 ref_offset(ref));
 541                                 return -EIO;
 542                         }
 543
 544                         err = read_unknown(c, ref, &node.u, retlen);
 545                         if (err == 1) {
 546                                 jffs2_mark_node_obsolete(c, ref);
 547                                 break;
 548                         } else if (unlikely(err))
 549                                 goto free_out;
 550
 551                 }
 552                 spin_lock(&c->erase_completion_lock);
 553
 554         }
 555         spin_unlock(&c->erase_completion_lock);
 556         *tnp = ret_tn;
 557         *fdp = ret_fd;
 558
 559         return 0;
 560
 561  free_out:
 562         jffs2_free_tmp_dnode_info_list(&ret_tn);
 563         jffs2_free_full_dirent_list(ret_fd);
 564         return err;
 565 }
 566
 567 void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state)
 568 {
 569         spin_lock(&c->inocache_lock);
 570         ic->state = state;
 571         wake_up(&c->inocache_wq);
 572         spin_unlock(&c->inocache_lock);
 573 }
 574
 575 /* During mount, this needs no locking. During normal operation, its
 576    callers want to do other stuff while still holding the inocache_lock.
 577    Rather than introducing special case get_ino_cache functions or
 578    callbacks, we just let the caller do the locking itself. */
 579
 580 struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
 581 {
 582         struct jffs2_inode_cache *ret;
 583
 584         D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino));
 585
 586         ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
 587         while (ret && ret->ino < ino) {
 588                 ret = ret->next;
 589         }
 590
 591         if (ret && ret->ino != ino)
 592                 ret = NULL;
 593
 594         D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino));
 595         return ret;
 596 }
 597
 598 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
 599 {
 600         struct jffs2_inode_cache **prev;
 601
 602         spin_lock(&c->inocache_lock);
 603         if (!new->ino)
 604                 new->ino = ++c->highest_ino;
 605
 606         D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
 607
 608         prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
 609
 610         while ((*prev) && (*prev)->ino < new->ino) {
 611                 prev = &(*prev)->next;
 612         }
 613         new->next = *prev;
 614         *prev = new;
 615
 616         spin_unlock(&c->inocache_lock);
 617 }
 618
 619 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
 620 {
 621         struct jffs2_inode_cache **prev;
 622         D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
 623         spin_lock(&c->inocache_lock);
 624
 625         prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
 626
 627         while ((*prev) && (*prev)->ino < old->ino) {
 628                 prev = &(*prev)->next;
 629         }
 630         if ((*prev) == old) {
 631                 *prev = old->next;
 632         }
 633
 634         /* Free it now unless it's in READING or CLEARING state, which
 635            are the transitions upon read_inode() and clear_inode(). The
 636            rest of the time we know nobody else is looking at it, and
 637            if it's held by read_inode() or clear_inode() they'll free it
 638            for themselves. */
 639         if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
 640                 jffs2_free_inode_cache(old);
 641
 642         spin_unlock(&c->inocache_lock);
 643 }
 644
 645 void jffs2_free_ino_caches(struct jffs2_sb_info *c)
 646 {
 647         int i;
 648         struct jffs2_inode_cache *this, *next;
 649
 650         for (i=0; i<INOCACHE_HASHSIZE; i++) {
 651                 this = c->inocache_list[i];
 652                 while (this) {
 653                         next = this->next;
 654                         jffs2_free_inode_cache(this);
 655                         this = next;
 656                 }
 657                 c->inocache_list[i] = NULL;
 658         }
 659 }
 660
 661 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
 662 {
 663         int i;
 664         struct jffs2_raw_node_ref *this, *next;
 665
 666         for (i=0; i<c->nr_blocks; i++) {
 667                 this = c->blocks[i].first_node;
 668                 while(this) {
 669                         next = this->next_phys;
 670                         jffs2_free_raw_node_ref(this);
 671                         this = next;
 672                 }
 673                 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
 674         }
 675 }
 676
 677 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
 678 {
 679         /* The common case in lookup is that there will be a node
 680            which precisely matches. So we go looking for that first */
 681         struct rb_node *next;
 682         struct jffs2_node_frag *prev = NULL;
 683         struct jffs2_node_frag *frag = NULL;
 684
 685         D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
 686
 687         next = fragtree->rb_node;
 688
 689         while(next) {
 690                 frag = rb_entry(next, struct jffs2_node_frag, rb);
 691
 692                 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
 693                           frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
 694                 if (frag->ofs + frag->size <= offset) {
 695                         D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
 696                                   frag->ofs, frag->ofs+frag->size));
 697                         /* Remember the closest smaller match on the way down */
 698                         if (!prev || frag->ofs > prev->ofs)
 699                                 prev = frag;
 700                         next = frag->rb.rb_right;
 701                 } else if (frag->ofs > offset) {
 702                         D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
 703                                   frag->ofs, frag->ofs+frag->size));
 704                         next = frag->rb.rb_left;
 705                 } else {
 706                         D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
 707                                   frag->ofs, frag->ofs+frag->size));
 708                         return frag;
 709                 }
 710         }
 711
 712         /* Exact match not found. Go back up looking at each parent,
 713            and return the closest smaller one */
 714
 715         if (prev)
 716                 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
 717                           prev->ofs, prev->ofs+prev->size));
 718         else
 719                 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
 720
 721         return prev;
 722 }
 723
 724 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
 725    they're killed. */
 726 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
 727 {
 728         struct jffs2_node_frag *frag;
 729         struct jffs2_node_frag *parent;
 730
 731         if (!root->rb_node)
 732                 return;
 733
 734         frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
 735
 736         while(frag) {
 737                 if (frag->rb.rb_left) {
 738                         D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
 739                                   frag, frag->ofs, frag->ofs+frag->size));
 740                         frag = frag_left(frag);
 741                         continue;
 742                 }
 743                 if (frag->rb.rb_right) {
 744                         D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
 745                                   frag, frag->ofs, frag->ofs+frag->size));
 746                         frag = frag_right(frag);
 747                         continue;
 748                 }
 749
 750                 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
 751                           frag->ofs, frag->ofs+frag->size, frag->node,
 752                           frag->node?frag->node->frags:0));
 753
 754                 if (frag->node && !(--frag->node->frags)) {
 755                         /* Not a hole, and it's the final remaining frag
 756                            of this node. Free the node */
 757                         if (c)
 758                                 jffs2_mark_node_obsolete(c, frag->node->raw);
 759
 760                         jffs2_free_full_dnode(frag->node);
 761                 }
 762                 parent = frag_parent(frag);
 763                 if (parent) {
 764                         if (frag_left(parent) == frag)
 765                                 parent->rb.rb_left = NULL;
 766                         else
 767                                 parent->rb.rb_right = NULL;
 768                 }
 769
 770                 jffs2_free_node_frag(frag);
 771                 frag = parent;
 772
 773                 cond_resched();
 774         }
 775 }
 776
 777 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
 778 {
 779         struct rb_node *parent = &base->rb;
 780         struct rb_node **link = &parent;
 781
 782         D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
 783                   newfrag->ofs, newfrag->ofs+newfrag->size, base));
 784
 785         while (*link) {
 786                 parent = *link;
 787                 base = rb_entry(parent, struct jffs2_node_frag, rb);
 788
 789                 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
 790                 if (newfrag->ofs > base->ofs)
 791                         link = &base->rb.rb_right;
 792                 else if (newfrag->ofs < base->ofs)
 793                         link = &base->rb.rb_left;
 794                 else {
 795                         printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
 796                         BUG();
 797                 }
 798         }
 799
 800         rb_link_node(&newfrag->rb, &base->rb, link);
 801 }