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.90 2004/12/08 17:59:20 dwmw2 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 /* Put a new tmp_dnode_info into the list, keeping the list in
  59    order of increasing version
  60 */
  61 static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct jffs2_tmp_dnode_info **list)
  62 {
  63         struct jffs2_tmp_dnode_info **prev = list;
  64
  65         while ((*prev) && (*prev)->version < tn->version) {
  66                 prev = &((*prev)->next);
  67         }
  68         tn->next = (*prev);
  69         *prev = tn;
  70 }
  71
  72 static void jffs2_free_tmp_dnode_info_list(struct jffs2_tmp_dnode_info *tn)
  73 {
  74         struct jffs2_tmp_dnode_info *next;
  75
  76         while (tn) {
  77                 next = tn;
  78                 tn = tn->next;
  79                 jffs2_free_full_dnode(next->fn);
  80                 jffs2_free_tmp_dnode_info(next);
  81         }
  82 }
  83
  84 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
  85 {
  86         struct jffs2_full_dirent *next;
  87
  88         while (fd) {
  89                 next = fd->next;
  90                 jffs2_free_full_dirent(fd);
  91                 fd = next;
  92         }
  93 }
  94
  95 /* Returns first valid node after 'ref'. May return 'ref' */
  96 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
  97 {
  98         while (ref && ref->next_in_ino) {
  99                 if (!ref_obsolete(ref))
 100                         return ref;
 101                 D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref)));
 102                 ref = ref->next_in_ino;
 103         }
 104         return NULL;
 105 }
 106
 107 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
 108    with this ino, returning the former in order of version */
 109
 110 int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
 111                           struct jffs2_tmp_dnode_info **tnp, struct jffs2_full_dirent **fdp,
 112                           uint32_t *highest_version, uint32_t *latest_mctime,
 113                           uint32_t *mctime_ver)
 114 {
 115         struct jffs2_raw_node_ref *ref, *valid_ref;
 116         struct jffs2_tmp_dnode_info *tn, *ret_tn = NULL;
 117         struct jffs2_full_dirent *fd, *ret_fd = NULL;
 118         union jffs2_node_union node;
 119         size_t retlen;
 120         int err;
 121
 122         *mctime_ver = 0;
 123
 124         D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino));
 125
 126         spin_lock(&c->erase_completion_lock);
 127
 128         valid_ref = jffs2_first_valid_node(f->inocache->nodes);
 129
 130         if (!valid_ref)
 131                 printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino);
 132
 133         while (valid_ref) {
 134                 /* We can hold a pointer to a non-obsolete node without the spinlock,
 135                    but _obsolete_ nodes may disappear at any time, if the block
 136                    they're in gets erased. So if we mark 'ref' obsolete while we're
 137                    not holding the lock, it can go away immediately. For that reason,
 138                    we find the next valid node first, before processing 'ref'.
 139                 */
 140                 ref = valid_ref;
 141                 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
 142                 spin_unlock(&c->erase_completion_lock);
 143
 144                 cond_resched();
 145
 146                 /* FIXME: point() */
 147                 err = jffs2_flash_read(c, (ref_offset(ref)),
 148                                        min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)),
 149                                        &retlen, (void *)&node);
 150                 if (err) {
 151                         printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref));
 152                         goto free_out;
 153                 }
 154
 155
 156                         /* Check we've managed to read at least the common node header */
 157                 if (retlen < min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node.u))) {
 158                         printk(KERN_WARNING "short read in get_inode_nodes()\n");
 159                         err = -EIO;
 160                         goto free_out;
 161                 }
 162
 163                 switch (je16_to_cpu(node.u.nodetype)) {
 164                 case JFFS2_NODETYPE_DIRENT:
 165                         D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref)));
 166                         if (ref_flags(ref) == REF_UNCHECKED) {
 167                                 printk(KERN_WARNING "BUG: Dirent node at 0x%08x never got checked? How?\n", ref_offset(ref));
 168                                 BUG();
 169                         }
 170                         if (retlen < sizeof(node.d)) {
 171                                 printk(KERN_WARNING "short read in get_inode_nodes()\n");
 172                                 err = -EIO;
 173                                 goto free_out;
 174                         }
 175                         /* sanity check */
 176                         if (PAD((node.d.nsize + sizeof (node.d))) != PAD(je32_to_cpu (node.d.totlen))) {
 177                                 printk(KERN_NOTICE "jffs2_get_inode_nodes(): Illegal nsize in node at 0x%08x: nsize 0x%02x, totlen %04x\n",
 178                                        ref_offset(ref), node.d.nsize, je32_to_cpu(node.d.totlen));
 179                                 jffs2_mark_node_obsolete(c, ref);
 180                                 spin_lock(&c->erase_completion_lock);
 181                                 continue;
 182                         }
 183                         if (je32_to_cpu(node.d.version) > *highest_version)
 184                                 *highest_version = je32_to_cpu(node.d.version);
 185                         if (ref_obsolete(ref)) {
 186                                 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
 187                                 printk(KERN_ERR "Dirent node at 0x%08x became obsolete while we weren't looking\n",
 188                                        ref_offset(ref));
 189                                 BUG();
 190                         }
 191
 192                         fd = jffs2_alloc_full_dirent(node.d.nsize+1);
 193                         if (!fd) {
 194                                 err = -ENOMEM;
 195                                 goto free_out;
 196                         }
 197                         fd->raw = ref;
 198                         fd->version = je32_to_cpu(node.d.version);
 199                         fd->ino = je32_to_cpu(node.d.ino);
 200                         fd->type = node.d.type;
 201
 202                         /* Pick out the mctime of the latest dirent */
 203                         if(fd->version > *mctime_ver) {
 204                                 *mctime_ver = fd->version;
 205                                 *latest_mctime = je32_to_cpu(node.d.mctime);
 206                         }
 207
 208                         /* memcpy as much of the name as possible from the raw
 209                            dirent we've already read from the flash
 210                         */
 211                         if (retlen > sizeof(struct jffs2_raw_dirent))
 212                                 memcpy(&fd->name[0], &node.d.name[0], min_t(uint32_t, node.d.nsize, (retlen-sizeof(struct jffs2_raw_dirent))));
 213
 214                         /* Do we need to copy any more of the name directly
 215                            from the flash?
 216                         */
 217                         if (node.d.nsize + sizeof(struct jffs2_raw_dirent) > retlen) {
 218                                 /* FIXME: point() */
 219                                 int already = retlen - sizeof(struct jffs2_raw_dirent);
 220
 221                                 err = jffs2_flash_read(c, (ref_offset(ref)) + retlen,
 222                                                    node.d.nsize - already, &retlen, &fd->name[already]);
 223                                 if (!err && retlen != node.d.nsize - already)
 224                                         err = -EIO;
 225
 226                                 if (err) {
 227                                         printk(KERN_WARNING "Read remainder of name in jffs2_get_inode_nodes(): error %d\n", err);
 228                                         jffs2_free_full_dirent(fd);
 229                                         goto free_out;
 230                                 }
 231                         }
 232                         fd->nhash = full_name_hash(fd->name, node.d.nsize);
 233                         fd->next = NULL;
 234                         fd->name[node.d.nsize] = '\0';
 235                                 /* Wheee. We now have a complete jffs2_full_dirent structure, with
 236                                    the name in it and everything. Link it into the list
 237                                 */
 238                         D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino));
 239                         jffs2_add_fd_to_list(c, fd, &ret_fd);
 240                         break;
 241
 242                 case JFFS2_NODETYPE_INODE:
 243                         D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref)));
 244                         if (retlen < sizeof(node.i)) {
 245                                 printk(KERN_WARNING "read too short for dnode\n");
 246                                 err = -EIO;
 247                                 goto free_out;
 248                         }
 249                         if (je32_to_cpu(node.i.version) > *highest_version)
 250                                 *highest_version = je32_to_cpu(node.i.version);
 251                         D1(printk(KERN_DEBUG "version %d, highest_version now %d\n", je32_to_cpu(node.i.version), *highest_version));
 252
 253                         if (ref_obsolete(ref)) {
 254                                 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
 255                                 printk(KERN_ERR "Inode node at 0x%08x became obsolete while we weren't looking\n",
 256                                        ref_offset(ref));
 257                                 BUG();
 258                         }
 259
 260                         /* If we've never checked the CRCs on this node, check them now. */
 261                         if (ref_flags(ref) == REF_UNCHECKED) {
 262                                 uint32_t crc, len;
 263                                 struct jffs2_eraseblock *jeb;
 264
 265                                 crc = crc32(0, &node, sizeof(node.i)-8);
 266                                 if (crc != je32_to_cpu(node.i.node_crc)) {
 267                                         printk(KERN_NOTICE "jffs2_get_inode_nodes(): CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
 268                                                ref_offset(ref), je32_to_cpu(node.i.node_crc), crc);
 269                                         jffs2_mark_node_obsolete(c, ref);
 270                                         spin_lock(&c->erase_completion_lock);
 271                                         continue;
 272                                 }
 273
 274                                 /* sanity checks */
 275                                 if ( je32_to_cpu(node.i.offset) > je32_to_cpu(node.i.isize) ||
 276                                      PAD(je32_to_cpu(node.i.csize) + sizeof (node.i)) != PAD(je32_to_cpu(node.i.totlen))) {
 277                                         printk(KERN_NOTICE "jffs2_get_inode_nodes(): Inode corrupted at 0x%08x, totlen %d, #ino  %d, version %d, isize %d, csize %d, dsize %d \n",
 278                                                 ref_offset(ref),  je32_to_cpu(node.i.totlen),  je32_to_cpu(node.i.ino),
 279                                                 je32_to_cpu(node.i.version),  je32_to_cpu(node.i.isize),
 280                                                 je32_to_cpu(node.i.csize), je32_to_cpu(node.i.dsize));
 281                                         jffs2_mark_node_obsolete(c, ref);
 282                                         spin_lock(&c->erase_completion_lock);
 283                                         continue;
 284                                 }
 285
 286                                 if (node.i.compr != JFFS2_COMPR_ZERO && je32_to_cpu(node.i.csize)) {
 287                                         unsigned char *buf=NULL;
 288                                         uint32_t pointed = 0;
 289 #ifndef __ECOS
 290                                         if (c->mtd->point) {
 291                                                 err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize),
 292                                                                      &retlen, &buf);
 293                                                 if (!err && retlen < je32_to_cpu(node.i.csize)) {
 294                                                         D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", retlen));
 295                                                         c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize));
 296                                                 } else if (err){
 297                                                         D1(printk(KERN_DEBUG "MTD point failed %d\n", err));
 298                                                 } else
 299                                                         pointed = 1; /* succefully pointed to device */
 300                                         }
 301 #endif
 302                                         if(!pointed){
 303                                                 buf = kmalloc(je32_to_cpu(node.i.csize), GFP_KERNEL);
 304                                                 if (!buf)
 305                                                         return -ENOMEM;
 306
 307                                                 err = jffs2_flash_read(c, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize),
 308                                                                        &retlen, buf);
 309                                                 if (!err && retlen != je32_to_cpu(node.i.csize))
 310                                                         err = -EIO;
 311                                                 if (err) {
 312                                                         kfree(buf);
 313                                                         return err;
 314                                                 }
 315                                         }
 316                                         crc = crc32(0, buf, je32_to_cpu(node.i.csize));
 317                                         if(!pointed)
 318                                                 kfree(buf);
 319 #ifndef __ECOS
 320                                         else
 321                                                 c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize));
 322 #endif
 323
 324                                         if (crc != je32_to_cpu(node.i.data_crc)) {
 325                                                 printk(KERN_NOTICE "jffs2_get_inode_nodes(): Data CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n",
 326                                                        ref_offset(ref), je32_to_cpu(node.i.data_crc), crc);
 327                                                 jffs2_mark_node_obsolete(c, ref);
 328                                                 spin_lock(&c->erase_completion_lock);
 329                                                 continue;
 330                                         }
 331
 332                                 }
 333
 334                                 /* Mark the node as having been checked and fix the accounting accordingly */
 335                                 spin_lock(&c->erase_completion_lock);
 336                                 jeb = &c->blocks[ref->flash_offset / c->sector_size];
 337                                 len = ref_totlen(c, jeb, ref);
 338
 339                                 jeb->used_size += len;
 340                                 jeb->unchecked_size -= len;
 341                                 c->used_size += len;
 342                                 c->unchecked_size -= len;
 343
 344                                 /* If node covers at least a whole page, or if it starts at the
 345                                    beginning of a page and runs to the end of the file, or if
 346                                    it's a hole node, mark it REF_PRISTINE, else REF_NORMAL.
 347
 348                                    If it's actually overlapped, it'll get made NORMAL (or OBSOLETE)
 349                                    when the overlapping node(s) get added to the tree anyway.
 350                                 */
 351                                 if ((je32_to_cpu(node.i.dsize) >= PAGE_CACHE_SIZE) ||
 352                                     ( ((je32_to_cpu(node.i.offset)&(PAGE_CACHE_SIZE-1))==0) &&
 353                                       (je32_to_cpu(node.i.dsize)+je32_to_cpu(node.i.offset) ==  je32_to_cpu(node.i.isize)))) {
 354                                         D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_PRISTINE\n", ref_offset(ref)));
 355                                         ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
 356                                 } else {
 357                                         D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_NORMAL\n", ref_offset(ref)));
 358                                         ref->flash_offset = ref_offset(ref) | REF_NORMAL;
 359                                 }
 360                                 spin_unlock(&c->erase_completion_lock);
 361                         }
 362
 363                         tn = jffs2_alloc_tmp_dnode_info();
 364                         if (!tn) {
 365                                 D1(printk(KERN_DEBUG "alloc tn failed\n"));
 366                                 err = -ENOMEM;
 367                                 goto free_out;
 368                         }
 369
 370                         tn->fn = jffs2_alloc_full_dnode();
 371                         if (!tn->fn) {
 372                                 D1(printk(KERN_DEBUG "alloc fn failed\n"));
 373                                 err = -ENOMEM;
 374                                 jffs2_free_tmp_dnode_info(tn);
 375                                 goto free_out;
 376                         }
 377                         tn->version = je32_to_cpu(node.i.version);
 378                         tn->fn->ofs = je32_to_cpu(node.i.offset);
 379                         /* There was a bug where we wrote hole nodes out with
 380                            csize/dsize swapped. Deal with it */
 381                         if (node.i.compr == JFFS2_COMPR_ZERO && !je32_to_cpu(node.i.dsize) && je32_to_cpu(node.i.csize))
 382                                 tn->fn->size = je32_to_cpu(node.i.csize);
 383                         else // normal case...
 384                                 tn->fn->size = je32_to_cpu(node.i.dsize);
 385                         tn->fn->raw = ref;
 386                         D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %04x, dsize %04x\n",
 387                                   ref_offset(ref), je32_to_cpu(node.i.version),
 388                                   je32_to_cpu(node.i.offset), je32_to_cpu(node.i.dsize)));
 389                         jffs2_add_tn_to_list(tn, &ret_tn);
 390                         break;
 391
 392                 default:
 393                         if (ref_flags(ref) == REF_UNCHECKED) {
 394                                 struct jffs2_eraseblock *jeb;
 395                                 uint32_t len;
 396
 397                                 printk(KERN_ERR "Eep. Unknown node type %04x at %08x was marked REF_UNCHECKED\n",
 398                                        je16_to_cpu(node.u.nodetype), ref_offset(ref));
 399
 400                                 /* Mark the node as having been checked and fix the accounting accordingly */
 401                                 spin_lock(&c->erase_completion_lock);
 402                                 jeb = &c->blocks[ref->flash_offset / c->sector_size];
 403                                 len = ref_totlen(c, jeb, ref);
 404
 405                                 jeb->used_size += len;
 406                                 jeb->unchecked_size -= len;
 407                                 c->used_size += len;
 408                                 c->unchecked_size -= len;
 409
 410                                 mark_ref_normal(ref);
 411                                 spin_unlock(&c->erase_completion_lock);
 412                         }
 413                         node.u.nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(node.u.nodetype));
 414                         if (crc32(0, &node, sizeof(struct jffs2_unknown_node)-4) != je32_to_cpu(node.u.hdr_crc)) {
 415                                 /* Hmmm. This should have been caught at scan time. */
 416                                 printk(KERN_ERR "Node header CRC failed at %08x. But it must have been OK earlier.\n",
 417                                        ref_offset(ref));
 418                                 printk(KERN_ERR "Node was: { %04x, %04x, %08x, %08x }\n",
 419                                        je16_to_cpu(node.u.magic), je16_to_cpu(node.u.nodetype), je32_to_cpu(node.u.totlen),
 420                                        je32_to_cpu(node.u.hdr_crc));
 421                                 jffs2_mark_node_obsolete(c, ref);
 422                         } else switch(je16_to_cpu(node.u.nodetype) & JFFS2_COMPAT_MASK) {
 423                         case JFFS2_FEATURE_INCOMPAT:
 424                                 printk(KERN_NOTICE "Unknown INCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
 425                                 /* EEP */
 426                                 BUG();
 427                                 break;
 428                         case JFFS2_FEATURE_ROCOMPAT:
 429                                 printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
 430                                 if (!(c->flags & JFFS2_SB_FLAG_RO))
 431                                         BUG();
 432                                 break;
 433                         case JFFS2_FEATURE_RWCOMPAT_COPY:
 434                                 printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
 435                                 break;
 436                         case JFFS2_FEATURE_RWCOMPAT_DELETE:
 437                                 printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref));
 438                                 jffs2_mark_node_obsolete(c, ref);
 439                                 break;
 440                         }
 441
 442                 }
 443                 spin_lock(&c->erase_completion_lock);
 444
 445         }
 446         spin_unlock(&c->erase_completion_lock);
 447         *tnp = ret_tn;
 448         *fdp = ret_fd;
 449
 450         return 0;
 451
 452  free_out:
 453         jffs2_free_tmp_dnode_info_list(ret_tn);
 454         jffs2_free_full_dirent_list(ret_fd);
 455         return err;
 456 }
 457
 458 void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state)
 459 {
 460         spin_lock(&c->inocache_lock);
 461         ic->state = state;
 462         wake_up(&c->inocache_wq);
 463         spin_unlock(&c->inocache_lock);
 464 }
 465
 466 /* During mount, this needs no locking. During normal operation, its
 467    callers want to do other stuff while still holding the inocache_lock.
 468    Rather than introducing special case get_ino_cache functions or
 469    callbacks, we just let the caller do the locking itself. */
 470
 471 struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino)
 472 {
 473         struct jffs2_inode_cache *ret;
 474
 475         D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino));
 476
 477         ret = c->inocache_list[ino % INOCACHE_HASHSIZE];
 478         while (ret && ret->ino < ino) {
 479                 ret = ret->next;
 480         }
 481
 482         if (ret && ret->ino != ino)
 483                 ret = NULL;
 484
 485         D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino));
 486         return ret;
 487 }
 488
 489 void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new)
 490 {
 491         struct jffs2_inode_cache **prev;
 492         D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino));
 493         spin_lock(&c->inocache_lock);
 494
 495         prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE];
 496
 497         while ((*prev) && (*prev)->ino < new->ino) {
 498                 prev = &(*prev)->next;
 499         }
 500         new->next = *prev;
 501         *prev = new;
 502
 503         spin_unlock(&c->inocache_lock);
 504 }
 505
 506 void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old)
 507 {
 508         struct jffs2_inode_cache **prev;
 509         D2(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino));
 510         spin_lock(&c->inocache_lock);
 511
 512         prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE];
 513
 514         while ((*prev) && (*prev)->ino < old->ino) {
 515                 prev = &(*prev)->next;
 516         }
 517         if ((*prev) == old) {
 518                 *prev = old->next;
 519         }
 520
 521         spin_unlock(&c->inocache_lock);
 522 }
 523
 524 void jffs2_free_ino_caches(struct jffs2_sb_info *c)
 525 {
 526         int i;
 527         struct jffs2_inode_cache *this, *next;
 528
 529         for (i=0; i<INOCACHE_HASHSIZE; i++) {
 530                 this = c->inocache_list[i];
 531                 while (this) {
 532                         next = this->next;
 533                         D2(printk(KERN_DEBUG "jffs2_free_ino_caches: Freeing ino #%u at %p\n", this->ino, this));
 534                         jffs2_free_inode_cache(this);
 535                         this = next;
 536                 }
 537                 c->inocache_list[i] = NULL;
 538         }
 539 }
 540
 541 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
 542 {
 543         int i;
 544         struct jffs2_raw_node_ref *this, *next;
 545
 546         for (i=0; i<c->nr_blocks; i++) {
 547                 this = c->blocks[i].first_node;
 548                 while(this) {
 549                         next = this->next_phys;
 550                         jffs2_free_raw_node_ref(this);
 551                         this = next;
 552                 }
 553                 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
 554         }
 555 }
 556
 557 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
 558 {
 559         /* The common case in lookup is that there will be a node
 560            which precisely matches. So we go looking for that first */
 561         struct rb_node *next;
 562         struct jffs2_node_frag *prev = NULL;
 563         struct jffs2_node_frag *frag = NULL;
 564
 565         D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
 566
 567         next = fragtree->rb_node;
 568
 569         while(next) {
 570                 frag = rb_entry(next, struct jffs2_node_frag, rb);
 571
 572                 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
 573                           frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
 574                 if (frag->ofs + frag->size <= offset) {
 575                         D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
 576                                   frag->ofs, frag->ofs+frag->size));
 577                         /* Remember the closest smaller match on the way down */
 578                         if (!prev || frag->ofs > prev->ofs)
 579                                 prev = frag;
 580                         next = frag->rb.rb_right;
 581                 } else if (frag->ofs > offset) {
 582                         D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
 583                                   frag->ofs, frag->ofs+frag->size));
 584                         next = frag->rb.rb_left;
 585                 } else {
 586                         D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
 587                                   frag->ofs, frag->ofs+frag->size));
 588                         return frag;
 589                 }
 590         }
 591
 592         /* Exact match not found. Go back up looking at each parent,
 593            and return the closest smaller one */
 594
 595         if (prev)
 596                 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
 597                           prev->ofs, prev->ofs+prev->size));
 598         else
 599                 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
 600
 601         return prev;
 602 }
 603
 604 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
 605    they're killed. */
 606 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
 607 {
 608         struct jffs2_node_frag *frag;
 609         struct jffs2_node_frag *parent;
 610
 611         if (!root->rb_node)
 612                 return;
 613
 614         frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
 615
 616         while(frag) {
 617                 if (frag->rb.rb_left) {
 618                         D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
 619                                   frag, frag->ofs, frag->ofs+frag->size));
 620                         frag = frag_left(frag);
 621                         continue;
 622                 }
 623                 if (frag->rb.rb_right) {
 624                         D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
 625                                   frag, frag->ofs, frag->ofs+frag->size));
 626                         frag = frag_right(frag);
 627                         continue;
 628                 }
 629
 630                 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
 631                           frag->ofs, frag->ofs+frag->size, frag->node,
 632                           frag->node?frag->node->frags:0));
 633
 634                 if (frag->node && !(--frag->node->frags)) {
 635                         /* Not a hole, and it's the final remaining frag
 636                            of this node. Free the node */
 637                         if (c)
 638                                 jffs2_mark_node_obsolete(c, frag->node->raw);
 639
 640                         jffs2_free_full_dnode(frag->node);
 641                 }
 642                 parent = frag_parent(frag);
 643                 if (parent) {
 644                         if (frag_left(parent) == frag)
 645                                 parent->rb.rb_left = NULL;
 646                         else
 647                                 parent->rb.rb_right = NULL;
 648                 }
 649
 650                 jffs2_free_node_frag(frag);
 651                 frag = parent;
 652
 653                 cond_resched();
 654         }
 655 }
 656
 657 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
 658 {
 659         struct rb_node *parent = &base->rb;
 660         struct rb_node **link = &parent;
 661
 662         D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
 663                   newfrag->ofs, newfrag->ofs+newfrag->size, base));
 664
 665         while (*link) {
 666                 parent = *link;
 667                 base = rb_entry(parent, struct jffs2_node_frag, rb);
 668
 669                 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
 670                 if (newfrag->ofs > base->ofs)
 671                         link = &base->rb.rb_right;
 672                 else if (newfrag->ofs < base->ofs)
 673                         link = &base->rb.rb_left;
 674                 else {
 675                         printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
 676                         BUG();
 677                 }
 678         }
 679
 680         rb_link_node(&newfrag->rb, &base->rb, link);
 681 }