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 } 682