SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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.93 2005/02/27 23:01:32 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 && (f->inocache->ino != 1))
 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         D1(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         /* Free it now unless it's in READING or CLEARING state, which
 522            are the transitions upon read_inode() and clear_inode(). The
 523            rest of the time we know nobody else is looking at it, and
 524            if it's held by read_inode() or clear_inode() they'll free it
 525            for themselves. */
 526         if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING)
 527                 jffs2_free_inode_cache(old);
 528
 529         spin_unlock(&c->inocache_lock);
 530 }
 531
 532 void jffs2_free_ino_caches(struct jffs2_sb_info *c)
 533 {
 534         int i;
 535         struct jffs2_inode_cache *this, *next;
 536
 537         for (i=0; i<INOCACHE_HASHSIZE; i++) {
 538                 this = c->inocache_list[i];
 539                 while (this) {
 540                         next = this->next;
 541                         jffs2_free_inode_cache(this);
 542                         this = next;
 543                 }
 544                 c->inocache_list[i] = NULL;
 545         }
 546 }
 547
 548 void jffs2_free_raw_node_refs(struct jffs2_sb_info *c)
 549 {
 550         int i;
 551         struct jffs2_raw_node_ref *this, *next;
 552
 553         for (i=0; i<c->nr_blocks; i++) {
 554                 this = c->blocks[i].first_node;
 555                 while(this) {
 556                         next = this->next_phys;
 557                         jffs2_free_raw_node_ref(this);
 558                         this = next;
 559                 }
 560                 c->blocks[i].first_node = c->blocks[i].last_node = NULL;
 561         }
 562 }
 563
 564 struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset)
 565 {
 566         /* The common case in lookup is that there will be a node
 567            which precisely matches. So we go looking for that first */
 568         struct rb_node *next;
 569         struct jffs2_node_frag *prev = NULL;
 570         struct jffs2_node_frag *frag = NULL;
 571
 572         D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset));
 573
 574         next = fragtree->rb_node;
 575
 576         while(next) {
 577                 frag = rb_entry(next, struct jffs2_node_frag, rb);
 578
 579                 D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n",
 580                           frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right));
 581                 if (frag->ofs + frag->size <= offset) {
 582                         D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n",
 583                                   frag->ofs, frag->ofs+frag->size));
 584                         /* Remember the closest smaller match on the way down */
 585                         if (!prev || frag->ofs > prev->ofs)
 586                                 prev = frag;
 587                         next = frag->rb.rb_right;
 588                 } else if (frag->ofs > offset) {
 589                         D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n",
 590                                   frag->ofs, frag->ofs+frag->size));
 591                         next = frag->rb.rb_left;
 592                 } else {
 593                         D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n",
 594                                   frag->ofs, frag->ofs+frag->size));
 595                         return frag;
 596                 }
 597         }
 598
 599         /* Exact match not found. Go back up looking at each parent,
 600            and return the closest smaller one */
 601
 602         if (prev)
 603                 D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n",
 604                           prev->ofs, prev->ofs+prev->size));
 605         else
 606                 D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n"));
 607
 608         return prev;
 609 }
 610
 611 /* Pass 'c' argument to indicate that nodes should be marked obsolete as
 612    they're killed. */
 613 void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c)
 614 {
 615         struct jffs2_node_frag *frag;
 616         struct jffs2_node_frag *parent;
 617
 618         if (!root->rb_node)
 619                 return;
 620
 621         frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb));
 622
 623         while(frag) {
 624                 if (frag->rb.rb_left) {
 625                         D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n",
 626                                   frag, frag->ofs, frag->ofs+frag->size));
 627                         frag = frag_left(frag);
 628                         continue;
 629                 }
 630                 if (frag->rb.rb_right) {
 631                         D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n",
 632                                   frag, frag->ofs, frag->ofs+frag->size));
 633                         frag = frag_right(frag);
 634                         continue;
 635                 }
 636
 637                 D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n",
 638                           frag->ofs, frag->ofs+frag->size, frag->node,
 639                           frag->node?frag->node->frags:0));
 640
 641                 if (frag->node && !(--frag->node->frags)) {
 642                         /* Not a hole, and it's the final remaining frag
 643                            of this node. Free the node */
 644                         if (c)
 645                                 jffs2_mark_node_obsolete(c, frag->node->raw);
 646
 647                         jffs2_free_full_dnode(frag->node);
 648                 }
 649                 parent = frag_parent(frag);
 650                 if (parent) {
 651                         if (frag_left(parent) == frag)
 652                                 parent->rb.rb_left = NULL;
 653                         else
 654                                 parent->rb.rb_right = NULL;
 655                 }
 656
 657                 jffs2_free_node_frag(frag);
 658                 frag = parent;
 659
 660                 cond_resched();
 661         }
 662 }
 663
 664 void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base)
 665 {
 666         struct rb_node *parent = &base->rb;
 667         struct rb_node **link = &parent;
 668
 669         D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag,
 670                   newfrag->ofs, newfrag->ofs+newfrag->size, base));
 671
 672         while (*link) {
 673                 parent = *link;
 674                 base = rb_entry(parent, struct jffs2_node_frag, rb);
 675
 676                 D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs));
 677                 if (newfrag->ofs > base->ofs)
 678                         link = &base->rb.rb_right;
 679                 else if (newfrag->ofs < base->ofs)
 680                         link = &base->rb.rb_left;
 681                 else {
 682                         printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base);
 683                         BUG();
 684                 }
 685         }
 686
 687         rb_link_node(&newfrag->rb, &base->rb, link);
 688 }