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