11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * JFFS2 -- Journalling Flash File System, Version 2. 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * Copyright (C) 2001-2003 Red Hat, Inc. 51da177e4SLinus Torvalds * 61da177e4SLinus Torvalds * Created by David Woodhouse <dwmw2@infradead.org> 71da177e4SLinus Torvalds * 81da177e4SLinus Torvalds * For licensing information, see the file 'LICENCE' in this directory. 91da177e4SLinus Torvalds * 109dee7503SDavid Woodhouse * $Id: nodelist.c,v 1.95 2005/07/05 21:03:07 dwmw2 Exp $ 111da177e4SLinus Torvalds * 121da177e4SLinus Torvalds */ 131da177e4SLinus Torvalds 141da177e4SLinus Torvalds #include <linux/kernel.h> 151da177e4SLinus Torvalds #include <linux/sched.h> 161da177e4SLinus Torvalds #include <linux/fs.h> 171da177e4SLinus Torvalds #include <linux/mtd/mtd.h> 181da177e4SLinus Torvalds #include <linux/rbtree.h> 191da177e4SLinus Torvalds #include <linux/crc32.h> 201da177e4SLinus Torvalds #include <linux/slab.h> 211da177e4SLinus Torvalds #include <linux/pagemap.h> 221da177e4SLinus Torvalds #include "nodelist.h" 231da177e4SLinus Torvalds 241da177e4SLinus Torvalds void jffs2_add_fd_to_list(struct jffs2_sb_info *c, struct jffs2_full_dirent *new, struct jffs2_full_dirent **list) 251da177e4SLinus Torvalds { 261da177e4SLinus Torvalds struct jffs2_full_dirent **prev = list; 271da177e4SLinus Torvalds D1(printk(KERN_DEBUG "jffs2_add_fd_to_list( %p, %p (->%p))\n", new, list, *list)); 281da177e4SLinus Torvalds 291da177e4SLinus Torvalds while ((*prev) && (*prev)->nhash <= new->nhash) { 301da177e4SLinus Torvalds if ((*prev)->nhash == new->nhash && !strcmp((*prev)->name, new->name)) { 311da177e4SLinus Torvalds /* Duplicate. Free one */ 321da177e4SLinus Torvalds if (new->version < (*prev)->version) { 331da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Eep! Marking new dirent node obsolete\n")); 341da177e4SLinus Torvalds D1(printk(KERN_DEBUG "New dirent is \"%s\"->ino #%u. Old is \"%s\"->ino #%u\n", new->name, new->ino, (*prev)->name, (*prev)->ino)); 351da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, new->raw); 361da177e4SLinus Torvalds jffs2_free_full_dirent(new); 371da177e4SLinus Torvalds } else { 381da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking old dirent node (ino #%u) obsolete\n", (*prev)->ino)); 391da177e4SLinus Torvalds new->next = (*prev)->next; 401da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ((*prev)->raw)); 411da177e4SLinus Torvalds jffs2_free_full_dirent(*prev); 421da177e4SLinus Torvalds *prev = new; 431da177e4SLinus Torvalds } 441da177e4SLinus Torvalds goto out; 451da177e4SLinus Torvalds } 461da177e4SLinus Torvalds prev = &((*prev)->next); 471da177e4SLinus Torvalds } 481da177e4SLinus Torvalds new->next = *prev; 491da177e4SLinus Torvalds *prev = new; 501da177e4SLinus Torvalds 511da177e4SLinus Torvalds out: 521da177e4SLinus Torvalds D2(while(*list) { 531da177e4SLinus Torvalds printk(KERN_DEBUG "Dirent \"%s\" (hash 0x%08x, ino #%u\n", (*list)->name, (*list)->nhash, (*list)->ino); 541da177e4SLinus Torvalds list = &(*list)->next; 551da177e4SLinus Torvalds }); 561da177e4SLinus Torvalds } 571da177e4SLinus Torvalds 581da177e4SLinus Torvalds /* Put a new tmp_dnode_info into the list, keeping the list in 591da177e4SLinus Torvalds order of increasing version 601da177e4SLinus Torvalds */ 619dee7503SDavid Woodhouse 629dee7503SDavid Woodhouse static void jffs2_add_tn_to_list(struct jffs2_tmp_dnode_info *tn, struct rb_root *list) 631da177e4SLinus Torvalds { 649dee7503SDavid Woodhouse struct rb_node **p = &list->rb_node; 659dee7503SDavid Woodhouse struct rb_node * parent = NULL; 669dee7503SDavid Woodhouse struct jffs2_tmp_dnode_info *this; 671da177e4SLinus Torvalds 689dee7503SDavid Woodhouse while (*p) { 699dee7503SDavid Woodhouse parent = *p; 709dee7503SDavid Woodhouse this = rb_entry(parent, struct jffs2_tmp_dnode_info, rb); 719dee7503SDavid Woodhouse 729dee7503SDavid Woodhouse if (tn->version < this->version) 739dee7503SDavid Woodhouse p = &(*p)->rb_left; 749dee7503SDavid Woodhouse else if (tn->version > this->version) 759dee7503SDavid Woodhouse p = &(*p)->rb_right; 769dee7503SDavid Woodhouse else if (tn < this) 779dee7503SDavid Woodhouse p = &(*p)->rb_left; 789dee7503SDavid Woodhouse else 799dee7503SDavid Woodhouse p = &(*p)->rb_right; 801da177e4SLinus Torvalds } 811da177e4SLinus Torvalds 829dee7503SDavid Woodhouse rb_link_node(&tn->rb, parent, p); 839dee7503SDavid Woodhouse rb_insert_color(&tn->rb, list); 849dee7503SDavid Woodhouse } 859dee7503SDavid Woodhouse 869dee7503SDavid Woodhouse static void jffs2_free_tmp_dnode_info_list(struct rb_root *list) 871da177e4SLinus Torvalds { 889dee7503SDavid Woodhouse struct rb_node *this; 899dee7503SDavid Woodhouse struct jffs2_tmp_dnode_info *tn; 901da177e4SLinus Torvalds 919dee7503SDavid Woodhouse this = list->rb_node; 929dee7503SDavid Woodhouse 939dee7503SDavid Woodhouse /* Now at bottom of tree */ 949dee7503SDavid Woodhouse while (this) { 959dee7503SDavid Woodhouse if (this->rb_left) 969dee7503SDavid Woodhouse this = this->rb_left; 979dee7503SDavid Woodhouse else if (this->rb_right) 989dee7503SDavid Woodhouse this = this->rb_right; 999dee7503SDavid Woodhouse else { 1009dee7503SDavid Woodhouse tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb); 1019dee7503SDavid Woodhouse jffs2_free_full_dnode(tn->fn); 1029dee7503SDavid Woodhouse jffs2_free_tmp_dnode_info(tn); 1039dee7503SDavid Woodhouse 1049dee7503SDavid Woodhouse this = this->rb_parent; 1059dee7503SDavid Woodhouse if (!this) 1069dee7503SDavid Woodhouse break; 1079dee7503SDavid Woodhouse 1089dee7503SDavid Woodhouse if (this->rb_left == &tn->rb) 1099dee7503SDavid Woodhouse this->rb_left = NULL; 1109dee7503SDavid Woodhouse else if (this->rb_right == &tn->rb) 1119dee7503SDavid Woodhouse this->rb_right = NULL; 1129dee7503SDavid Woodhouse else BUG(); 1131da177e4SLinus Torvalds } 1141da177e4SLinus Torvalds } 1159dee7503SDavid Woodhouse list->rb_node = NULL; 1169dee7503SDavid Woodhouse } 1171da177e4SLinus Torvalds 1181da177e4SLinus Torvalds static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd) 1191da177e4SLinus Torvalds { 1201da177e4SLinus Torvalds struct jffs2_full_dirent *next; 1211da177e4SLinus Torvalds 1221da177e4SLinus Torvalds while (fd) { 1231da177e4SLinus Torvalds next = fd->next; 1241da177e4SLinus Torvalds jffs2_free_full_dirent(fd); 1251da177e4SLinus Torvalds fd = next; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds } 1281da177e4SLinus Torvalds 1291da177e4SLinus Torvalds /* Returns first valid node after 'ref'. May return 'ref' */ 1301da177e4SLinus Torvalds static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref) 1311da177e4SLinus Torvalds { 1321da177e4SLinus Torvalds while (ref && ref->next_in_ino) { 1331da177e4SLinus Torvalds if (!ref_obsolete(ref)) 1341da177e4SLinus Torvalds return ref; 1351da177e4SLinus Torvalds D1(printk(KERN_DEBUG "node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref))); 1361da177e4SLinus Torvalds ref = ref->next_in_ino; 1371da177e4SLinus Torvalds } 1381da177e4SLinus Torvalds return NULL; 1391da177e4SLinus Torvalds } 1401da177e4SLinus Torvalds 1411da177e4SLinus Torvalds /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated 1421da177e4SLinus Torvalds with this ino, returning the former in order of version */ 1431da177e4SLinus Torvalds 1441da177e4SLinus Torvalds int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f, 1459dee7503SDavid Woodhouse struct rb_root *tnp, struct jffs2_full_dirent **fdp, 1461da177e4SLinus Torvalds uint32_t *highest_version, uint32_t *latest_mctime, 1471da177e4SLinus Torvalds uint32_t *mctime_ver) 1481da177e4SLinus Torvalds { 1491da177e4SLinus Torvalds struct jffs2_raw_node_ref *ref, *valid_ref; 1509dee7503SDavid Woodhouse struct jffs2_tmp_dnode_info *tn; 1519dee7503SDavid Woodhouse struct rb_root ret_tn = RB_ROOT; 1521da177e4SLinus Torvalds struct jffs2_full_dirent *fd, *ret_fd = NULL; 1531da177e4SLinus Torvalds union jffs2_node_union node; 1541da177e4SLinus Torvalds size_t retlen; 1551da177e4SLinus Torvalds int err; 1561da177e4SLinus Torvalds 1571da177e4SLinus Torvalds *mctime_ver = 0; 1581da177e4SLinus Torvalds 1591da177e4SLinus Torvalds D1(printk(KERN_DEBUG "jffs2_get_inode_nodes(): ino #%u\n", f->inocache->ino)); 1601da177e4SLinus Torvalds 1611da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 1621da177e4SLinus Torvalds 1631da177e4SLinus Torvalds valid_ref = jffs2_first_valid_node(f->inocache->nodes); 1641da177e4SLinus Torvalds 1658fabed4aSTodd Poynor if (!valid_ref && (f->inocache->ino != 1)) 1661da177e4SLinus Torvalds printk(KERN_WARNING "Eep. No valid nodes for ino #%u\n", f->inocache->ino); 1671da177e4SLinus Torvalds 1681da177e4SLinus Torvalds while (valid_ref) { 1691da177e4SLinus Torvalds /* We can hold a pointer to a non-obsolete node without the spinlock, 1701da177e4SLinus Torvalds but _obsolete_ nodes may disappear at any time, if the block 1711da177e4SLinus Torvalds they're in gets erased. So if we mark 'ref' obsolete while we're 1721da177e4SLinus Torvalds not holding the lock, it can go away immediately. For that reason, 1731da177e4SLinus Torvalds we find the next valid node first, before processing 'ref'. 1741da177e4SLinus Torvalds */ 1751da177e4SLinus Torvalds ref = valid_ref; 1761da177e4SLinus Torvalds valid_ref = jffs2_first_valid_node(ref->next_in_ino); 1771da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 1781da177e4SLinus Torvalds 1791da177e4SLinus Torvalds cond_resched(); 1801da177e4SLinus Torvalds 1811da177e4SLinus Torvalds /* FIXME: point() */ 1821da177e4SLinus Torvalds err = jffs2_flash_read(c, (ref_offset(ref)), 1831da177e4SLinus Torvalds min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node)), 1841da177e4SLinus Torvalds &retlen, (void *)&node); 1851da177e4SLinus Torvalds if (err) { 1861da177e4SLinus Torvalds printk(KERN_WARNING "error %d reading node at 0x%08x in get_inode_nodes()\n", err, ref_offset(ref)); 1871da177e4SLinus Torvalds goto free_out; 1881da177e4SLinus Torvalds } 1891da177e4SLinus Torvalds 1901da177e4SLinus Torvalds 1911da177e4SLinus Torvalds /* Check we've managed to read at least the common node header */ 1921da177e4SLinus Torvalds if (retlen < min_t(uint32_t, ref_totlen(c, NULL, ref), sizeof(node.u))) { 1931da177e4SLinus Torvalds printk(KERN_WARNING "short read in get_inode_nodes()\n"); 1941da177e4SLinus Torvalds err = -EIO; 1951da177e4SLinus Torvalds goto free_out; 1961da177e4SLinus Torvalds } 1971da177e4SLinus Torvalds 1981da177e4SLinus Torvalds switch (je16_to_cpu(node.u.nodetype)) { 1991da177e4SLinus Torvalds case JFFS2_NODETYPE_DIRENT: 2001da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Node at %08x (%d) is a dirent node\n", ref_offset(ref), ref_flags(ref))); 2011da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 2021da177e4SLinus Torvalds printk(KERN_WARNING "BUG: Dirent node at 0x%08x never got checked? How?\n", ref_offset(ref)); 2031da177e4SLinus Torvalds BUG(); 2041da177e4SLinus Torvalds } 2051da177e4SLinus Torvalds if (retlen < sizeof(node.d)) { 2061da177e4SLinus Torvalds printk(KERN_WARNING "short read in get_inode_nodes()\n"); 2071da177e4SLinus Torvalds err = -EIO; 2081da177e4SLinus Torvalds goto free_out; 2091da177e4SLinus Torvalds } 2101da177e4SLinus Torvalds /* sanity check */ 2111da177e4SLinus Torvalds if (PAD((node.d.nsize + sizeof (node.d))) != PAD(je32_to_cpu (node.d.totlen))) { 2121da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): Illegal nsize in node at 0x%08x: nsize 0x%02x, totlen %04x\n", 2131da177e4SLinus Torvalds ref_offset(ref), node.d.nsize, je32_to_cpu(node.d.totlen)); 2141da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 2151da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 2161da177e4SLinus Torvalds continue; 2171da177e4SLinus Torvalds } 2181da177e4SLinus Torvalds if (je32_to_cpu(node.d.version) > *highest_version) 2191da177e4SLinus Torvalds *highest_version = je32_to_cpu(node.d.version); 2201da177e4SLinus Torvalds if (ref_obsolete(ref)) { 2211da177e4SLinus Torvalds /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */ 2221da177e4SLinus Torvalds printk(KERN_ERR "Dirent node at 0x%08x became obsolete while we weren't looking\n", 2231da177e4SLinus Torvalds ref_offset(ref)); 2241da177e4SLinus Torvalds BUG(); 2251da177e4SLinus Torvalds } 2261da177e4SLinus Torvalds 2271da177e4SLinus Torvalds fd = jffs2_alloc_full_dirent(node.d.nsize+1); 2281da177e4SLinus Torvalds if (!fd) { 2291da177e4SLinus Torvalds err = -ENOMEM; 2301da177e4SLinus Torvalds goto free_out; 2311da177e4SLinus Torvalds } 2321da177e4SLinus Torvalds fd->raw = ref; 2331da177e4SLinus Torvalds fd->version = je32_to_cpu(node.d.version); 2341da177e4SLinus Torvalds fd->ino = je32_to_cpu(node.d.ino); 2351da177e4SLinus Torvalds fd->type = node.d.type; 2361da177e4SLinus Torvalds 2371da177e4SLinus Torvalds /* Pick out the mctime of the latest dirent */ 2381da177e4SLinus Torvalds if(fd->version > *mctime_ver) { 2391da177e4SLinus Torvalds *mctime_ver = fd->version; 2401da177e4SLinus Torvalds *latest_mctime = je32_to_cpu(node.d.mctime); 2411da177e4SLinus Torvalds } 2421da177e4SLinus Torvalds 2431da177e4SLinus Torvalds /* memcpy as much of the name as possible from the raw 2441da177e4SLinus Torvalds dirent we've already read from the flash 2451da177e4SLinus Torvalds */ 2461da177e4SLinus Torvalds if (retlen > sizeof(struct jffs2_raw_dirent)) 2471da177e4SLinus Torvalds memcpy(&fd->name[0], &node.d.name[0], min_t(uint32_t, node.d.nsize, (retlen-sizeof(struct jffs2_raw_dirent)))); 2481da177e4SLinus Torvalds 2491da177e4SLinus Torvalds /* Do we need to copy any more of the name directly 2501da177e4SLinus Torvalds from the flash? 2511da177e4SLinus Torvalds */ 2521da177e4SLinus Torvalds if (node.d.nsize + sizeof(struct jffs2_raw_dirent) > retlen) { 2531da177e4SLinus Torvalds /* FIXME: point() */ 2541da177e4SLinus Torvalds int already = retlen - sizeof(struct jffs2_raw_dirent); 2551da177e4SLinus Torvalds 2561da177e4SLinus Torvalds err = jffs2_flash_read(c, (ref_offset(ref)) + retlen, 2571da177e4SLinus Torvalds node.d.nsize - already, &retlen, &fd->name[already]); 2581da177e4SLinus Torvalds if (!err && retlen != node.d.nsize - already) 2591da177e4SLinus Torvalds err = -EIO; 2601da177e4SLinus Torvalds 2611da177e4SLinus Torvalds if (err) { 2621da177e4SLinus Torvalds printk(KERN_WARNING "Read remainder of name in jffs2_get_inode_nodes(): error %d\n", err); 2631da177e4SLinus Torvalds jffs2_free_full_dirent(fd); 2641da177e4SLinus Torvalds goto free_out; 2651da177e4SLinus Torvalds } 2661da177e4SLinus Torvalds } 2671da177e4SLinus Torvalds fd->nhash = full_name_hash(fd->name, node.d.nsize); 2681da177e4SLinus Torvalds fd->next = NULL; 2691da177e4SLinus Torvalds fd->name[node.d.nsize] = '\0'; 2701da177e4SLinus Torvalds /* Wheee. We now have a complete jffs2_full_dirent structure, with 2711da177e4SLinus Torvalds the name in it and everything. Link it into the list 2721da177e4SLinus Torvalds */ 2731da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Adding fd \"%s\", ino #%u\n", fd->name, fd->ino)); 2741da177e4SLinus Torvalds jffs2_add_fd_to_list(c, fd, &ret_fd); 2751da177e4SLinus Torvalds break; 2761da177e4SLinus Torvalds 2771da177e4SLinus Torvalds case JFFS2_NODETYPE_INODE: 2781da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Node at %08x (%d) is a data node\n", ref_offset(ref), ref_flags(ref))); 2791da177e4SLinus Torvalds if (retlen < sizeof(node.i)) { 2801da177e4SLinus Torvalds printk(KERN_WARNING "read too short for dnode\n"); 2811da177e4SLinus Torvalds err = -EIO; 2821da177e4SLinus Torvalds goto free_out; 2831da177e4SLinus Torvalds } 2841da177e4SLinus Torvalds if (je32_to_cpu(node.i.version) > *highest_version) 2851da177e4SLinus Torvalds *highest_version = je32_to_cpu(node.i.version); 2861da177e4SLinus Torvalds D1(printk(KERN_DEBUG "version %d, highest_version now %d\n", je32_to_cpu(node.i.version), *highest_version)); 2871da177e4SLinus Torvalds 2881da177e4SLinus Torvalds if (ref_obsolete(ref)) { 2891da177e4SLinus Torvalds /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */ 2901da177e4SLinus Torvalds printk(KERN_ERR "Inode node at 0x%08x became obsolete while we weren't looking\n", 2911da177e4SLinus Torvalds ref_offset(ref)); 2921da177e4SLinus Torvalds BUG(); 2931da177e4SLinus Torvalds } 2941da177e4SLinus Torvalds 2951da177e4SLinus Torvalds /* If we've never checked the CRCs on this node, check them now. */ 2961da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 2971da177e4SLinus Torvalds uint32_t crc, len; 2981da177e4SLinus Torvalds struct jffs2_eraseblock *jeb; 2991da177e4SLinus Torvalds 3001da177e4SLinus Torvalds crc = crc32(0, &node, sizeof(node.i)-8); 3011da177e4SLinus Torvalds if (crc != je32_to_cpu(node.i.node_crc)) { 3021da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n", 3031da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.node_crc), crc); 3041da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 3051da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3061da177e4SLinus Torvalds continue; 3071da177e4SLinus Torvalds } 3081da177e4SLinus Torvalds 3091da177e4SLinus Torvalds /* sanity checks */ 3101da177e4SLinus Torvalds if ( je32_to_cpu(node.i.offset) > je32_to_cpu(node.i.isize) || 3111da177e4SLinus Torvalds PAD(je32_to_cpu(node.i.csize) + sizeof (node.i)) != PAD(je32_to_cpu(node.i.totlen))) { 3121da177e4SLinus Torvalds 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", 3131da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.totlen), je32_to_cpu(node.i.ino), 3141da177e4SLinus Torvalds je32_to_cpu(node.i.version), je32_to_cpu(node.i.isize), 3151da177e4SLinus Torvalds je32_to_cpu(node.i.csize), je32_to_cpu(node.i.dsize)); 3161da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 3171da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3181da177e4SLinus Torvalds continue; 3191da177e4SLinus Torvalds } 3201da177e4SLinus Torvalds 3211da177e4SLinus Torvalds if (node.i.compr != JFFS2_COMPR_ZERO && je32_to_cpu(node.i.csize)) { 3221da177e4SLinus Torvalds unsigned char *buf=NULL; 3231da177e4SLinus Torvalds uint32_t pointed = 0; 3241da177e4SLinus Torvalds #ifndef __ECOS 3251da177e4SLinus Torvalds if (c->mtd->point) { 3261da177e4SLinus Torvalds err = c->mtd->point (c->mtd, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize), 3271da177e4SLinus Torvalds &retlen, &buf); 3281da177e4SLinus Torvalds if (!err && retlen < je32_to_cpu(node.i.csize)) { 3291da177e4SLinus Torvalds D1(printk(KERN_DEBUG "MTD point returned len too short: 0x%zx\n", retlen)); 3301da177e4SLinus Torvalds c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize)); 3311da177e4SLinus Torvalds } else if (err){ 3321da177e4SLinus Torvalds D1(printk(KERN_DEBUG "MTD point failed %d\n", err)); 3331da177e4SLinus Torvalds } else 3341da177e4SLinus Torvalds pointed = 1; /* succefully pointed to device */ 3351da177e4SLinus Torvalds } 3361da177e4SLinus Torvalds #endif 3371da177e4SLinus Torvalds if(!pointed){ 3381da177e4SLinus Torvalds buf = kmalloc(je32_to_cpu(node.i.csize), GFP_KERNEL); 3391da177e4SLinus Torvalds if (!buf) 3401da177e4SLinus Torvalds return -ENOMEM; 3411da177e4SLinus Torvalds 3421da177e4SLinus Torvalds err = jffs2_flash_read(c, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize), 3431da177e4SLinus Torvalds &retlen, buf); 3441da177e4SLinus Torvalds if (!err && retlen != je32_to_cpu(node.i.csize)) 3451da177e4SLinus Torvalds err = -EIO; 3461da177e4SLinus Torvalds if (err) { 3471da177e4SLinus Torvalds kfree(buf); 3481da177e4SLinus Torvalds return err; 3491da177e4SLinus Torvalds } 3501da177e4SLinus Torvalds } 3511da177e4SLinus Torvalds crc = crc32(0, buf, je32_to_cpu(node.i.csize)); 3521da177e4SLinus Torvalds if(!pointed) 3531da177e4SLinus Torvalds kfree(buf); 3541da177e4SLinus Torvalds #ifndef __ECOS 3551da177e4SLinus Torvalds else 3561da177e4SLinus Torvalds c->mtd->unpoint(c->mtd, buf, ref_offset(ref) + sizeof(node.i), je32_to_cpu(node.i.csize)); 3571da177e4SLinus Torvalds #endif 3581da177e4SLinus Torvalds 3591da177e4SLinus Torvalds if (crc != je32_to_cpu(node.i.data_crc)) { 3601da177e4SLinus Torvalds printk(KERN_NOTICE "jffs2_get_inode_nodes(): Data CRC failed on node at 0x%08x: Read 0x%08x, calculated 0x%08x\n", 3611da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.data_crc), crc); 3621da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 3631da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3641da177e4SLinus Torvalds continue; 3651da177e4SLinus Torvalds } 3661da177e4SLinus Torvalds 3671da177e4SLinus Torvalds } 3681da177e4SLinus Torvalds 3691da177e4SLinus Torvalds /* Mark the node as having been checked and fix the accounting accordingly */ 3701da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 3711da177e4SLinus Torvalds jeb = &c->blocks[ref->flash_offset / c->sector_size]; 3721da177e4SLinus Torvalds len = ref_totlen(c, jeb, ref); 3731da177e4SLinus Torvalds 3741da177e4SLinus Torvalds jeb->used_size += len; 3751da177e4SLinus Torvalds jeb->unchecked_size -= len; 3761da177e4SLinus Torvalds c->used_size += len; 3771da177e4SLinus Torvalds c->unchecked_size -= len; 3781da177e4SLinus Torvalds 3791da177e4SLinus Torvalds /* If node covers at least a whole page, or if it starts at the 3801da177e4SLinus Torvalds beginning of a page and runs to the end of the file, or if 3811da177e4SLinus Torvalds it's a hole node, mark it REF_PRISTINE, else REF_NORMAL. 3821da177e4SLinus Torvalds 3831da177e4SLinus Torvalds If it's actually overlapped, it'll get made NORMAL (or OBSOLETE) 3841da177e4SLinus Torvalds when the overlapping node(s) get added to the tree anyway. 3851da177e4SLinus Torvalds */ 3861da177e4SLinus Torvalds if ((je32_to_cpu(node.i.dsize) >= PAGE_CACHE_SIZE) || 3871da177e4SLinus Torvalds ( ((je32_to_cpu(node.i.offset)&(PAGE_CACHE_SIZE-1))==0) && 3881da177e4SLinus Torvalds (je32_to_cpu(node.i.dsize)+je32_to_cpu(node.i.offset) == je32_to_cpu(node.i.isize)))) { 3891da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_PRISTINE\n", ref_offset(ref))); 3901da177e4SLinus Torvalds ref->flash_offset = ref_offset(ref) | REF_PRISTINE; 3911da177e4SLinus Torvalds } else { 3921da177e4SLinus Torvalds D1(printk(KERN_DEBUG "Marking node at 0x%08x REF_NORMAL\n", ref_offset(ref))); 3931da177e4SLinus Torvalds ref->flash_offset = ref_offset(ref) | REF_NORMAL; 3941da177e4SLinus Torvalds } 3951da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 3961da177e4SLinus Torvalds } 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds tn = jffs2_alloc_tmp_dnode_info(); 3991da177e4SLinus Torvalds if (!tn) { 4001da177e4SLinus Torvalds D1(printk(KERN_DEBUG "alloc tn failed\n")); 4011da177e4SLinus Torvalds err = -ENOMEM; 4021da177e4SLinus Torvalds goto free_out; 4031da177e4SLinus Torvalds } 4041da177e4SLinus Torvalds 4051da177e4SLinus Torvalds tn->fn = jffs2_alloc_full_dnode(); 4061da177e4SLinus Torvalds if (!tn->fn) { 4071da177e4SLinus Torvalds D1(printk(KERN_DEBUG "alloc fn failed\n")); 4081da177e4SLinus Torvalds err = -ENOMEM; 4091da177e4SLinus Torvalds jffs2_free_tmp_dnode_info(tn); 4101da177e4SLinus Torvalds goto free_out; 4111da177e4SLinus Torvalds } 4121da177e4SLinus Torvalds tn->version = je32_to_cpu(node.i.version); 4131da177e4SLinus Torvalds tn->fn->ofs = je32_to_cpu(node.i.offset); 4141da177e4SLinus Torvalds /* There was a bug where we wrote hole nodes out with 4151da177e4SLinus Torvalds csize/dsize swapped. Deal with it */ 4161da177e4SLinus Torvalds if (node.i.compr == JFFS2_COMPR_ZERO && !je32_to_cpu(node.i.dsize) && je32_to_cpu(node.i.csize)) 4171da177e4SLinus Torvalds tn->fn->size = je32_to_cpu(node.i.csize); 4181da177e4SLinus Torvalds else // normal case... 4191da177e4SLinus Torvalds tn->fn->size = je32_to_cpu(node.i.dsize); 4201da177e4SLinus Torvalds tn->fn->raw = ref; 4211da177e4SLinus Torvalds D1(printk(KERN_DEBUG "dnode @%08x: ver %u, offset %04x, dsize %04x\n", 4221da177e4SLinus Torvalds ref_offset(ref), je32_to_cpu(node.i.version), 4231da177e4SLinus Torvalds je32_to_cpu(node.i.offset), je32_to_cpu(node.i.dsize))); 4241da177e4SLinus Torvalds jffs2_add_tn_to_list(tn, &ret_tn); 4251da177e4SLinus Torvalds break; 4261da177e4SLinus Torvalds 4271da177e4SLinus Torvalds default: 4281da177e4SLinus Torvalds if (ref_flags(ref) == REF_UNCHECKED) { 4291da177e4SLinus Torvalds struct jffs2_eraseblock *jeb; 4301da177e4SLinus Torvalds uint32_t len; 4311da177e4SLinus Torvalds 4321da177e4SLinus Torvalds printk(KERN_ERR "Eep. Unknown node type %04x at %08x was marked REF_UNCHECKED\n", 4331da177e4SLinus Torvalds je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4341da177e4SLinus Torvalds 4351da177e4SLinus Torvalds /* Mark the node as having been checked and fix the accounting accordingly */ 4361da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 4371da177e4SLinus Torvalds jeb = &c->blocks[ref->flash_offset / c->sector_size]; 4381da177e4SLinus Torvalds len = ref_totlen(c, jeb, ref); 4391da177e4SLinus Torvalds 4401da177e4SLinus Torvalds jeb->used_size += len; 4411da177e4SLinus Torvalds jeb->unchecked_size -= len; 4421da177e4SLinus Torvalds c->used_size += len; 4431da177e4SLinus Torvalds c->unchecked_size -= len; 4441da177e4SLinus Torvalds 4451da177e4SLinus Torvalds mark_ref_normal(ref); 4461da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 4471da177e4SLinus Torvalds } 4481da177e4SLinus Torvalds node.u.nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(node.u.nodetype)); 4491da177e4SLinus Torvalds if (crc32(0, &node, sizeof(struct jffs2_unknown_node)-4) != je32_to_cpu(node.u.hdr_crc)) { 4501da177e4SLinus Torvalds /* Hmmm. This should have been caught at scan time. */ 4511da177e4SLinus Torvalds printk(KERN_ERR "Node header CRC failed at %08x. But it must have been OK earlier.\n", 4521da177e4SLinus Torvalds ref_offset(ref)); 4531da177e4SLinus Torvalds printk(KERN_ERR "Node was: { %04x, %04x, %08x, %08x }\n", 4541da177e4SLinus Torvalds je16_to_cpu(node.u.magic), je16_to_cpu(node.u.nodetype), je32_to_cpu(node.u.totlen), 4551da177e4SLinus Torvalds je32_to_cpu(node.u.hdr_crc)); 4561da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 4571da177e4SLinus Torvalds } else switch(je16_to_cpu(node.u.nodetype) & JFFS2_COMPAT_MASK) { 4581da177e4SLinus Torvalds case JFFS2_FEATURE_INCOMPAT: 4591da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown INCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4601da177e4SLinus Torvalds /* EEP */ 4611da177e4SLinus Torvalds BUG(); 4621da177e4SLinus Torvalds break; 4631da177e4SLinus Torvalds case JFFS2_FEATURE_ROCOMPAT: 4641da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown ROCOMPAT nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4651da177e4SLinus Torvalds if (!(c->flags & JFFS2_SB_FLAG_RO)) 4661da177e4SLinus Torvalds BUG(); 4671da177e4SLinus Torvalds break; 4681da177e4SLinus Torvalds case JFFS2_FEATURE_RWCOMPAT_COPY: 4691da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown RWCOMPAT_COPY nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4701da177e4SLinus Torvalds break; 4711da177e4SLinus Torvalds case JFFS2_FEATURE_RWCOMPAT_DELETE: 4721da177e4SLinus Torvalds printk(KERN_NOTICE "Unknown RWCOMPAT_DELETE nodetype %04X at %08x\n", je16_to_cpu(node.u.nodetype), ref_offset(ref)); 4731da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, ref); 4741da177e4SLinus Torvalds break; 4751da177e4SLinus Torvalds } 4761da177e4SLinus Torvalds 4771da177e4SLinus Torvalds } 4781da177e4SLinus Torvalds spin_lock(&c->erase_completion_lock); 4791da177e4SLinus Torvalds 4801da177e4SLinus Torvalds } 4811da177e4SLinus Torvalds spin_unlock(&c->erase_completion_lock); 4821da177e4SLinus Torvalds *tnp = ret_tn; 4831da177e4SLinus Torvalds *fdp = ret_fd; 4841da177e4SLinus Torvalds 4851da177e4SLinus Torvalds return 0; 4861da177e4SLinus Torvalds 4871da177e4SLinus Torvalds free_out: 4889dee7503SDavid Woodhouse jffs2_free_tmp_dnode_info_list(&ret_tn); 4891da177e4SLinus Torvalds jffs2_free_full_dirent_list(ret_fd); 4901da177e4SLinus Torvalds return err; 4911da177e4SLinus Torvalds } 4921da177e4SLinus Torvalds 4931da177e4SLinus Torvalds void jffs2_set_inocache_state(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic, int state) 4941da177e4SLinus Torvalds { 4951da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 4961da177e4SLinus Torvalds ic->state = state; 4971da177e4SLinus Torvalds wake_up(&c->inocache_wq); 4981da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 4991da177e4SLinus Torvalds } 5001da177e4SLinus Torvalds 5011da177e4SLinus Torvalds /* During mount, this needs no locking. During normal operation, its 5021da177e4SLinus Torvalds callers want to do other stuff while still holding the inocache_lock. 5031da177e4SLinus Torvalds Rather than introducing special case get_ino_cache functions or 5041da177e4SLinus Torvalds callbacks, we just let the caller do the locking itself. */ 5051da177e4SLinus Torvalds 5061da177e4SLinus Torvalds struct jffs2_inode_cache *jffs2_get_ino_cache(struct jffs2_sb_info *c, uint32_t ino) 5071da177e4SLinus Torvalds { 5081da177e4SLinus Torvalds struct jffs2_inode_cache *ret; 5091da177e4SLinus Torvalds 5101da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache(): ino %u\n", ino)); 5111da177e4SLinus Torvalds 5121da177e4SLinus Torvalds ret = c->inocache_list[ino % INOCACHE_HASHSIZE]; 5131da177e4SLinus Torvalds while (ret && ret->ino < ino) { 5141da177e4SLinus Torvalds ret = ret->next; 5151da177e4SLinus Torvalds } 5161da177e4SLinus Torvalds 5171da177e4SLinus Torvalds if (ret && ret->ino != ino) 5181da177e4SLinus Torvalds ret = NULL; 5191da177e4SLinus Torvalds 5201da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_get_ino_cache found %p for ino %u\n", ret, ino)); 5211da177e4SLinus Torvalds return ret; 5221da177e4SLinus Torvalds } 5231da177e4SLinus Torvalds 5241da177e4SLinus Torvalds void jffs2_add_ino_cache (struct jffs2_sb_info *c, struct jffs2_inode_cache *new) 5251da177e4SLinus Torvalds { 5261da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 5277d27c814SThomas Gleixner 5281da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 5297d200960SDavid Woodhouse if (!new->ino) 5307d200960SDavid Woodhouse new->ino = ++c->highest_ino; 5317d200960SDavid Woodhouse 5327d200960SDavid Woodhouse D2(printk(KERN_DEBUG "jffs2_add_ino_cache: Add %p (ino #%u)\n", new, new->ino)); 5331da177e4SLinus Torvalds 5341da177e4SLinus Torvalds prev = &c->inocache_list[new->ino % INOCACHE_HASHSIZE]; 5351da177e4SLinus Torvalds 5361da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < new->ino) { 5371da177e4SLinus Torvalds prev = &(*prev)->next; 5381da177e4SLinus Torvalds } 5391da177e4SLinus Torvalds new->next = *prev; 5401da177e4SLinus Torvalds *prev = new; 5411da177e4SLinus Torvalds 5421da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 5431da177e4SLinus Torvalds } 5441da177e4SLinus Torvalds 5451da177e4SLinus Torvalds void jffs2_del_ino_cache(struct jffs2_sb_info *c, struct jffs2_inode_cache *old) 5461da177e4SLinus Torvalds { 5471da177e4SLinus Torvalds struct jffs2_inode_cache **prev; 54867e345d1SDavid Woodhouse D1(printk(KERN_DEBUG "jffs2_del_ino_cache: Del %p (ino #%u)\n", old, old->ino)); 5491da177e4SLinus Torvalds spin_lock(&c->inocache_lock); 5501da177e4SLinus Torvalds 5511da177e4SLinus Torvalds prev = &c->inocache_list[old->ino % INOCACHE_HASHSIZE]; 5521da177e4SLinus Torvalds 5531da177e4SLinus Torvalds while ((*prev) && (*prev)->ino < old->ino) { 5541da177e4SLinus Torvalds prev = &(*prev)->next; 5551da177e4SLinus Torvalds } 5561da177e4SLinus Torvalds if ((*prev) == old) { 5571da177e4SLinus Torvalds *prev = old->next; 5581da177e4SLinus Torvalds } 5591da177e4SLinus Torvalds 56067e345d1SDavid Woodhouse /* Free it now unless it's in READING or CLEARING state, which 56167e345d1SDavid Woodhouse are the transitions upon read_inode() and clear_inode(). The 56267e345d1SDavid Woodhouse rest of the time we know nobody else is looking at it, and 56367e345d1SDavid Woodhouse if it's held by read_inode() or clear_inode() they'll free it 56467e345d1SDavid Woodhouse for themselves. */ 56567e345d1SDavid Woodhouse if (old->state != INO_STATE_READING && old->state != INO_STATE_CLEARING) 56667e345d1SDavid Woodhouse jffs2_free_inode_cache(old); 56767e345d1SDavid Woodhouse 5681da177e4SLinus Torvalds spin_unlock(&c->inocache_lock); 5691da177e4SLinus Torvalds } 5701da177e4SLinus Torvalds 5711da177e4SLinus Torvalds void jffs2_free_ino_caches(struct jffs2_sb_info *c) 5721da177e4SLinus Torvalds { 5731da177e4SLinus Torvalds int i; 5741da177e4SLinus Torvalds struct jffs2_inode_cache *this, *next; 5751da177e4SLinus Torvalds 5761da177e4SLinus Torvalds for (i=0; i<INOCACHE_HASHSIZE; i++) { 5771da177e4SLinus Torvalds this = c->inocache_list[i]; 5781da177e4SLinus Torvalds while (this) { 5791da177e4SLinus Torvalds next = this->next; 5801da177e4SLinus Torvalds jffs2_free_inode_cache(this); 5811da177e4SLinus Torvalds this = next; 5821da177e4SLinus Torvalds } 5831da177e4SLinus Torvalds c->inocache_list[i] = NULL; 5841da177e4SLinus Torvalds } 5851da177e4SLinus Torvalds } 5861da177e4SLinus Torvalds 5871da177e4SLinus Torvalds void jffs2_free_raw_node_refs(struct jffs2_sb_info *c) 5881da177e4SLinus Torvalds { 5891da177e4SLinus Torvalds int i; 5901da177e4SLinus Torvalds struct jffs2_raw_node_ref *this, *next; 5911da177e4SLinus Torvalds 5921da177e4SLinus Torvalds for (i=0; i<c->nr_blocks; i++) { 5931da177e4SLinus Torvalds this = c->blocks[i].first_node; 5941da177e4SLinus Torvalds while(this) { 5951da177e4SLinus Torvalds next = this->next_phys; 5961da177e4SLinus Torvalds jffs2_free_raw_node_ref(this); 5971da177e4SLinus Torvalds this = next; 5981da177e4SLinus Torvalds } 5991da177e4SLinus Torvalds c->blocks[i].first_node = c->blocks[i].last_node = NULL; 6001da177e4SLinus Torvalds } 6011da177e4SLinus Torvalds } 6021da177e4SLinus Torvalds 6031da177e4SLinus Torvalds struct jffs2_node_frag *jffs2_lookup_node_frag(struct rb_root *fragtree, uint32_t offset) 6041da177e4SLinus Torvalds { 6051da177e4SLinus Torvalds /* The common case in lookup is that there will be a node 6061da177e4SLinus Torvalds which precisely matches. So we go looking for that first */ 6071da177e4SLinus Torvalds struct rb_node *next; 6081da177e4SLinus Torvalds struct jffs2_node_frag *prev = NULL; 6091da177e4SLinus Torvalds struct jffs2_node_frag *frag = NULL; 6101da177e4SLinus Torvalds 6111da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_lookup_node_frag(%p, %d)\n", fragtree, offset)); 6121da177e4SLinus Torvalds 6131da177e4SLinus Torvalds next = fragtree->rb_node; 6141da177e4SLinus Torvalds 6151da177e4SLinus Torvalds while(next) { 6161da177e4SLinus Torvalds frag = rb_entry(next, struct jffs2_node_frag, rb); 6171da177e4SLinus Torvalds 6181da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Considering frag %d-%d (%p). left %p, right %p\n", 6191da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag, frag->rb.rb_left, frag->rb.rb_right)); 6201da177e4SLinus Torvalds if (frag->ofs + frag->size <= offset) { 6211da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag %d-%d, before the region we care about\n", 6221da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 6231da177e4SLinus Torvalds /* Remember the closest smaller match on the way down */ 6241da177e4SLinus Torvalds if (!prev || frag->ofs > prev->ofs) 6251da177e4SLinus Torvalds prev = frag; 6261da177e4SLinus Torvalds next = frag->rb.rb_right; 6271da177e4SLinus Torvalds } else if (frag->ofs > offset) { 6281da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag %d-%d, after the region we care about\n", 6291da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 6301da177e4SLinus Torvalds next = frag->rb.rb_left; 6311da177e4SLinus Torvalds } else { 6321da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning frag %d,%d, matched\n", 6331da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size)); 6341da177e4SLinus Torvalds return frag; 6351da177e4SLinus Torvalds } 6361da177e4SLinus Torvalds } 6371da177e4SLinus Torvalds 6381da177e4SLinus Torvalds /* Exact match not found. Go back up looking at each parent, 6391da177e4SLinus Torvalds and return the closest smaller one */ 6401da177e4SLinus Torvalds 6411da177e4SLinus Torvalds if (prev) 6421da177e4SLinus Torvalds D2(printk(KERN_DEBUG "No match. Returning frag %d,%d, closest previous\n", 6431da177e4SLinus Torvalds prev->ofs, prev->ofs+prev->size)); 6441da177e4SLinus Torvalds else 6451da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Returning NULL, empty fragtree\n")); 6461da177e4SLinus Torvalds 6471da177e4SLinus Torvalds return prev; 6481da177e4SLinus Torvalds } 6491da177e4SLinus Torvalds 6501da177e4SLinus Torvalds /* Pass 'c' argument to indicate that nodes should be marked obsolete as 6511da177e4SLinus Torvalds they're killed. */ 6521da177e4SLinus Torvalds void jffs2_kill_fragtree(struct rb_root *root, struct jffs2_sb_info *c) 6531da177e4SLinus Torvalds { 6541da177e4SLinus Torvalds struct jffs2_node_frag *frag; 6551da177e4SLinus Torvalds struct jffs2_node_frag *parent; 6561da177e4SLinus Torvalds 6571da177e4SLinus Torvalds if (!root->rb_node) 6581da177e4SLinus Torvalds return; 6591da177e4SLinus Torvalds 6601da177e4SLinus Torvalds frag = (rb_entry(root->rb_node, struct jffs2_node_frag, rb)); 6611da177e4SLinus Torvalds 6621da177e4SLinus Torvalds while(frag) { 6631da177e4SLinus Torvalds if (frag->rb.rb_left) { 6641da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going left from frag (%p) %d-%d\n", 6651da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 6661da177e4SLinus Torvalds frag = frag_left(frag); 6671da177e4SLinus Torvalds continue; 6681da177e4SLinus Torvalds } 6691da177e4SLinus Torvalds if (frag->rb.rb_right) { 6701da177e4SLinus Torvalds D2(printk(KERN_DEBUG "Going right from frag (%p) %d-%d\n", 6711da177e4SLinus Torvalds frag, frag->ofs, frag->ofs+frag->size)); 6721da177e4SLinus Torvalds frag = frag_right(frag); 6731da177e4SLinus Torvalds continue; 6741da177e4SLinus Torvalds } 6751da177e4SLinus Torvalds 6761da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_kill_fragtree: frag at 0x%x-0x%x: node %p, frags %d--\n", 6771da177e4SLinus Torvalds frag->ofs, frag->ofs+frag->size, frag->node, 6781da177e4SLinus Torvalds frag->node?frag->node->frags:0)); 6791da177e4SLinus Torvalds 6801da177e4SLinus Torvalds if (frag->node && !(--frag->node->frags)) { 6811da177e4SLinus Torvalds /* Not a hole, and it's the final remaining frag 6821da177e4SLinus Torvalds of this node. Free the node */ 6831da177e4SLinus Torvalds if (c) 6841da177e4SLinus Torvalds jffs2_mark_node_obsolete(c, frag->node->raw); 6851da177e4SLinus Torvalds 6861da177e4SLinus Torvalds jffs2_free_full_dnode(frag->node); 6871da177e4SLinus Torvalds } 6881da177e4SLinus Torvalds parent = frag_parent(frag); 6891da177e4SLinus Torvalds if (parent) { 6901da177e4SLinus Torvalds if (frag_left(parent) == frag) 6911da177e4SLinus Torvalds parent->rb.rb_left = NULL; 6921da177e4SLinus Torvalds else 6931da177e4SLinus Torvalds parent->rb.rb_right = NULL; 6941da177e4SLinus Torvalds } 6951da177e4SLinus Torvalds 6961da177e4SLinus Torvalds jffs2_free_node_frag(frag); 6971da177e4SLinus Torvalds frag = parent; 6981da177e4SLinus Torvalds 6991da177e4SLinus Torvalds cond_resched(); 7001da177e4SLinus Torvalds } 7011da177e4SLinus Torvalds } 7021da177e4SLinus Torvalds 7031da177e4SLinus Torvalds void jffs2_fragtree_insert(struct jffs2_node_frag *newfrag, struct jffs2_node_frag *base) 7041da177e4SLinus Torvalds { 7051da177e4SLinus Torvalds struct rb_node *parent = &base->rb; 7061da177e4SLinus Torvalds struct rb_node **link = &parent; 7071da177e4SLinus Torvalds 7081da177e4SLinus Torvalds D2(printk(KERN_DEBUG "jffs2_fragtree_insert(%p; %d-%d, %p)\n", newfrag, 7091da177e4SLinus Torvalds newfrag->ofs, newfrag->ofs+newfrag->size, base)); 7101da177e4SLinus Torvalds 7111da177e4SLinus Torvalds while (*link) { 7121da177e4SLinus Torvalds parent = *link; 7131da177e4SLinus Torvalds base = rb_entry(parent, struct jffs2_node_frag, rb); 7141da177e4SLinus Torvalds 7151da177e4SLinus Torvalds D2(printk(KERN_DEBUG "fragtree_insert considering frag at 0x%x\n", base->ofs)); 7161da177e4SLinus Torvalds if (newfrag->ofs > base->ofs) 7171da177e4SLinus Torvalds link = &base->rb.rb_right; 7181da177e4SLinus Torvalds else if (newfrag->ofs < base->ofs) 7191da177e4SLinus Torvalds link = &base->rb.rb_left; 7201da177e4SLinus Torvalds else { 7211da177e4SLinus Torvalds printk(KERN_CRIT "Duplicate frag at %08x (%p,%p)\n", newfrag->ofs, newfrag, base); 7221da177e4SLinus Torvalds BUG(); 7231da177e4SLinus Torvalds } 7241da177e4SLinus Torvalds } 7251da177e4SLinus Torvalds 7261da177e4SLinus Torvalds rb_link_node(&newfrag->rb, &base->rb, link); 7271da177e4SLinus Torvalds } 728