2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright (C) 2001-2003 Red Hat, Inc.
6 * Created by David Woodhouse <dwmw2@redhat.com>
8 * For licensing information, see the file 'LICENCE' in this directory.
10 * $Id: readinode.c,v 1.107 2003/10/04 08:33:06 dwmw2 Exp $
14 #include <linux/kernel.h>
15 #include <linux/slab.h>
17 #include <linux/crc32.h>
18 #include <linux/pagemap.h>
19 #include <linux/mtd/mtd.h>
20 #include <linux/compiler.h>
23 static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c, struct rb_root *list, struct jffs2_node_frag *newfrag);
25 #if CONFIG_JFFS2_FS_DEBUG >= 1
26 static void jffs2_print_fragtree(struct rb_root *list, int permitbug)
28 struct jffs2_node_frag *this = frag_first(list);
34 printk(KERN_DEBUG "frag %04x-%04x: 0x%08x(%d) on flash (*%p). left (%p), right (%p), parent (%p)\n",
35 this->ofs, this->ofs+this->size, ref_offset(this->node->raw), ref_flags(this->node->raw),
36 this, frag_left(this), frag_right(this), frag_parent(this));
38 printk(KERN_DEBUG "frag %04x-%04x: hole (*%p). left (%p} right (%p), parent (%p)\n", this->ofs,
39 this->ofs+this->size, this, frag_left(this), frag_right(this), frag_parent(this));
40 if (this->ofs != lastofs)
42 lastofs = this->ofs+this->size;
43 this = frag_next(this);
45 if (buggy && !permitbug) {
46 printk(KERN_CRIT "Frag tree got a hole in it\n");
51 void jffs2_print_frag_list(struct jffs2_inode_info *f)
53 jffs2_print_fragtree(&f->fragtree, 0);
56 printk(KERN_DEBUG "metadata at 0x%08x\n", ref_offset(f->metadata->raw));
61 static void jffs2_obsolete_node_frag(struct jffs2_sb_info *c, struct jffs2_node_frag *this)
65 if (!this->node->frags) {
66 /* The node has no valid frags left. It's totally obsoleted */
67 D2(printk(KERN_DEBUG "Marking old node @0x%08x (0x%04x-0x%04x) obsolete\n",
68 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size));
69 jffs2_mark_node_obsolete(c, this->node->raw);
70 jffs2_free_full_dnode(this->node);
72 D2(printk(KERN_DEBUG "Marking old node @0x%08x (0x%04x-0x%04x) REF_NORMAL. frags is %d\n",
73 ref_offset(this->node->raw), this->node->ofs, this->node->ofs+this->node->size,
75 mark_ref_normal(this->node->raw);
79 jffs2_free_node_frag(this);
82 /* Given an inode, probably with existing list of fragments, add the new node
83 * to the fragment list.
85 int jffs2_add_full_dnode_to_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f, struct jffs2_full_dnode *fn)
88 struct jffs2_node_frag *newfrag;
90 D1(printk(KERN_DEBUG "jffs2_add_full_dnode_to_inode(ino #%u, f %p, fn %p)\n", f->inocache->ino, f, fn));
92 newfrag = jffs2_alloc_node_frag();
93 if (unlikely(!newfrag))
96 D2(printk(KERN_DEBUG "adding node %04x-%04x @0x%08x on flash, newfrag *%p\n",
97 fn->ofs, fn->ofs+fn->size, ref_offset(fn->raw), newfrag));
99 if (unlikely(!fn->size)) {
100 jffs2_free_node_frag(newfrag);
104 newfrag->ofs = fn->ofs;
105 newfrag->size = fn->size;
107 newfrag->node->frags = 1;
109 ret = jffs2_add_frag_to_fragtree(c, &f->fragtree, newfrag);
113 /* If we now share a page with other nodes, mark either previous
114 or next node REF_NORMAL, as appropriate. */
115 if (newfrag->ofs & (PAGE_CACHE_SIZE-1)) {
116 struct jffs2_node_frag *prev = frag_prev(newfrag);
118 mark_ref_normal(fn->raw);
119 /* If we don't start at zero there's _always_ a previous */
121 mark_ref_normal(prev->node->raw);
124 if ((newfrag->ofs+newfrag->size) & (PAGE_CACHE_SIZE-1)) {
125 struct jffs2_node_frag *next = frag_next(newfrag);
128 mark_ref_normal(fn->raw);
130 mark_ref_normal(next->node->raw);
133 D2(jffs2_print_frag_list(f));
137 /* Doesn't set inode->i_size */
138 static int jffs2_add_frag_to_fragtree(struct jffs2_sb_info *c, struct rb_root *list, struct jffs2_node_frag *newfrag)
140 struct jffs2_node_frag *this;
143 /* Skip all the nodes which are completed before this one starts */
144 this = jffs2_lookup_node_frag(list, newfrag->node->ofs);
147 D2(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
148 this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this));
149 lastend = this->ofs + this->size;
151 D2(printk(KERN_DEBUG "j_a_f_d_t_f: Lookup gave no frag\n"));
155 /* See if we ran off the end of the list */
156 if (lastend <= newfrag->ofs) {
159 /* Check if 'this' node was on the same page as the new node.
160 If so, both 'this' and the new node get marked REF_NORMAL so
161 the GC can take a look.
163 if ((lastend-1) >> PAGE_CACHE_SHIFT == newfrag->ofs >> PAGE_CACHE_SHIFT) {
165 mark_ref_normal(this->node->raw);
166 mark_ref_normal(newfrag->node->raw);
169 if (lastend < newfrag->node->ofs) {
170 /* ... and we need to put a hole in before the new node */
171 struct jffs2_node_frag *holefrag = jffs2_alloc_node_frag();
173 jffs2_free_node_frag(newfrag);
176 holefrag->ofs = lastend;
177 holefrag->size = newfrag->node->ofs - lastend;
178 holefrag->node = NULL;
180 /* By definition, the 'this' node has no right-hand child,
181 because there are no frags with offset greater than it.
182 So that's where we want to put the hole */
183 D2(printk(KERN_DEBUG "Adding hole frag (%p) on right of node at (%p)\n", holefrag, this));
184 rb_link_node(&holefrag->rb, &this->rb, &this->rb.rb_right);
186 D2(printk(KERN_DEBUG "Adding hole frag (%p) at root of tree\n", holefrag));
187 rb_link_node(&holefrag->rb, NULL, &list->rb_node);
189 rb_insert_color(&holefrag->rb, list);
193 /* By definition, the 'this' node has no right-hand child,
194 because there are no frags with offset greater than it.
195 So that's where we want to put the hole */
196 D2(printk(KERN_DEBUG "Adding new frag (%p) on right of node at (%p)\n", newfrag, this));
197 rb_link_node(&newfrag->rb, &this->rb, &this->rb.rb_right);
199 D2(printk(KERN_DEBUG "Adding new frag (%p) at root of tree\n", newfrag));
200 rb_link_node(&newfrag->rb, NULL, &list->rb_node);
202 rb_insert_color(&newfrag->rb, list);
206 D2(printk(KERN_DEBUG "j_a_f_d_t_f: dealing with frag 0x%04x-0x%04x; phys 0x%08x (*%p)\n",
207 this->ofs, this->ofs+this->size, this->node?(ref_offset(this->node->raw)):0xffffffff, this));
209 /* OK. 'this' is pointing at the first frag that newfrag->ofs at least partially obsoletes,
210 * - i.e. newfrag->ofs < this->ofs+this->size && newfrag->ofs >= this->ofs
212 if (newfrag->ofs > this->ofs) {
213 /* This node isn't completely obsoleted. The start of it remains valid */
215 /* Mark the new node and the partially covered node REF_NORMAL -- let
216 the GC take a look at them */
217 mark_ref_normal(newfrag->node->raw);
219 mark_ref_normal(this->node->raw);
221 if (this->ofs + this->size > newfrag->ofs + newfrag->size) {
222 /* The new node splits 'this' frag into two */
223 struct jffs2_node_frag *newfrag2 = jffs2_alloc_node_frag();
225 jffs2_free_node_frag(newfrag);
228 D2(printk(KERN_DEBUG "split old frag 0x%04x-0x%04x -->", this->ofs, this->ofs+this->size);
230 printk("phys 0x%08x\n", ref_offset(this->node->raw));
235 /* New second frag pointing to this's node */
236 newfrag2->ofs = newfrag->ofs + newfrag->size;
237 newfrag2->size = (this->ofs+this->size) - newfrag2->ofs;
238 newfrag2->node = this->node;
242 /* Adjust size of original 'this' */
243 this->size = newfrag->ofs - this->ofs;
245 /* Now, we know there's no node with offset
246 greater than this->ofs but smaller than
247 newfrag2->ofs or newfrag->ofs, for obvious
248 reasons. So we can do a tree insert from
249 'this' to insert newfrag, and a tree insert
250 from newfrag to insert newfrag2. */
251 jffs2_fragtree_insert(newfrag, this);
252 rb_insert_color(&newfrag->rb, list);
254 jffs2_fragtree_insert(newfrag2, newfrag);
255 rb_insert_color(&newfrag2->rb, list);
259 /* New node just reduces 'this' frag in size, doesn't split it */
260 this->size = newfrag->ofs - this->ofs;
262 /* Again, we know it lives down here in the tree */
263 jffs2_fragtree_insert(newfrag, this);
264 rb_insert_color(&newfrag->rb, list);
266 /* New frag starts at the same point as 'this' used to. Replace
267 it in the tree without doing a delete and insertion */
268 D2(printk(KERN_DEBUG "Inserting newfrag (*%p),%d-%d in before 'this' (*%p),%d-%d\n",
269 newfrag, newfrag->ofs, newfrag->ofs+newfrag->size,
270 this, this->ofs, this->ofs+this->size));
272 rb_replace_node(&this->rb, &newfrag->rb, list);
274 if (newfrag->ofs + newfrag->size >= this->ofs+this->size) {
275 D2(printk(KERN_DEBUG "Obsoleting node frag %p (%x-%x)\n", this, this->ofs, this->ofs+this->size));
276 jffs2_obsolete_node_frag(c, this);
278 this->ofs += newfrag->size;
279 this->size -= newfrag->size;
281 jffs2_fragtree_insert(this, newfrag);
282 rb_insert_color(&this->rb, list);
286 /* OK, now we have newfrag added in the correct place in the tree, but
287 frag_next(newfrag) may be a fragment which is overlapped by it
289 while ((this = frag_next(newfrag)) && newfrag->ofs + newfrag->size >= this->ofs + this->size) {
290 /* 'this' frag is obsoleted completely. */
291 D2(printk(KERN_DEBUG "Obsoleting node frag %p (%x-%x) and removing from tree\n", this, this->ofs, this->ofs+this->size));
292 rb_erase(&this->rb, list);
293 jffs2_obsolete_node_frag(c, this);
295 /* Now we're pointing at the first frag which isn't totally obsoleted by
298 if (!this || newfrag->ofs + newfrag->size == this->ofs) {
301 /* Still some overlap but we don't need to move it in the tree */
302 this->size = (this->ofs + this->size) - (newfrag->ofs + newfrag->size);
303 this->ofs = newfrag->ofs + newfrag->size;
305 /* And mark them REF_NORMAL so the GC takes a look at them */
307 mark_ref_normal(this->node->raw);
308 mark_ref_normal(newfrag->node->raw);
313 void jffs2_truncate_fraglist (struct jffs2_sb_info *c, struct rb_root *list, uint32_t size)
315 struct jffs2_node_frag *frag = jffs2_lookup_node_frag(list, size);
317 D1(printk(KERN_DEBUG "Truncating fraglist to 0x%08x bytes\n", size));
319 /* We know frag->ofs <= size. That's what lookup does for us */
320 if (frag && frag->ofs != size) {
321 if (frag->ofs+frag->size >= size) {
322 D1(printk(KERN_DEBUG "Truncating frag 0x%08x-0x%08x\n", frag->ofs, frag->ofs+frag->size));
323 frag->size = size - frag->ofs;
325 frag = frag_next(frag);
327 while (frag && frag->ofs >= size) {
328 struct jffs2_node_frag *next = frag_next(frag);
330 D1(printk(KERN_DEBUG "Removing frag 0x%08x-0x%08x\n", frag->ofs, frag->ofs+frag->size));
331 frag_erase(frag, list);
332 jffs2_obsolete_node_frag(c, frag);
337 /* Scan the list of all nodes present for this ino, build map of versions, etc. */
339 static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
340 struct jffs2_inode_info *f,
341 struct jffs2_raw_inode *latest_node);
343 int jffs2_do_read_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
344 uint32_t ino, struct jffs2_raw_inode *latest_node)
346 D2(printk(KERN_DEBUG "jffs2_do_read_inode(): getting inocache\n"));
349 spin_lock(&c->inocache_lock);
350 f->inocache = jffs2_get_ino_cache(c, ino);
352 D2(printk(KERN_DEBUG "jffs2_do_read_inode(): Got inocache at %p\n", f->inocache));
355 /* Check its state. We may need to wait before we can use it */
356 switch(f->inocache->state) {
357 case INO_STATE_UNCHECKED:
358 case INO_STATE_CHECKEDABSENT:
359 f->inocache->state = INO_STATE_READING;
362 case INO_STATE_CHECKING:
364 /* If it's in either of these states, we need
365 to wait for whoever's got it to finish and
367 D1(printk(KERN_DEBUG "jffs2_get_ino_cache_read waiting for ino #%u in state %d\n",
368 ino, f->inocache->state));
369 sleep_on_spinunlock(&c->inocache_wq, &c->inocache_lock);
372 case INO_STATE_READING:
373 case INO_STATE_PRESENT:
374 /* Eep. This should never happen. It can
375 happen if Linux calls read_inode() again
376 before clear_inode() has finished though. */
377 printk(KERN_WARNING "Eep. Trying to read_inode #%u when it's already in state %d!\n", ino, f->inocache->state);
378 /* Fail. That's probably better than allowing it to succeed */
386 spin_unlock(&c->inocache_lock);
387 if (!f->inocache && ino == 1) {
388 /* Special case - no root inode on medium */
389 f->inocache = jffs2_alloc_inode_cache();
391 printk(KERN_CRIT "jffs2_do_read_inode(): Cannot allocate inocache for root inode\n");
394 D1(printk(KERN_DEBUG "jffs2_do_read_inode(): Creating inocache for root inode\n"));
395 memset(f->inocache, 0, sizeof(struct jffs2_inode_cache));
396 f->inocache->ino = f->inocache->nlink = 1;
397 f->inocache->nodes = (struct jffs2_raw_node_ref *)f->inocache;
398 f->inocache->state = INO_STATE_READING;
399 jffs2_add_ino_cache(c, f->inocache);
402 printk(KERN_WARNING "jffs2_do_read_inode() on nonexistent ino %u\n", ino);
406 return jffs2_do_read_inode_internal(c, f, latest_node);
409 int jffs2_do_crccheck_inode(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic)
411 struct jffs2_raw_inode n;
412 struct jffs2_inode_info *f = kmalloc(sizeof(*f), GFP_KERNEL);
418 memset(f, 0, sizeof(*f));
419 init_MUTEX_LOCKED(&f->sem);
422 ret = jffs2_do_read_inode_internal(c, f, &n);
425 jffs2_do_clear_inode(c, f);
431 static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
432 struct jffs2_inode_info *f,
433 struct jffs2_raw_inode *latest_node)
435 struct jffs2_tmp_dnode_info *tn_list, *tn;
436 struct jffs2_full_dirent *fd_list;
437 struct jffs2_full_dnode *fn = NULL;
439 uint32_t latest_mctime, mctime_ver;
440 uint32_t mdata_ver = 0;
444 D1(printk(KERN_DEBUG "jffs2_do_read_inode_internal(): ino #%u nlink is %d\n", f->inocache->ino, f->inocache->nlink));
446 /* Grab all nodes relevant to this ino */
447 ret = jffs2_get_inode_nodes(c, f->inocache->ino, f, &tn_list, &fd_list, &f->highest_version, &latest_mctime, &mctime_ver);
450 printk(KERN_CRIT "jffs2_get_inode_nodes() for ino %u returned %d\n", f->inocache->ino, ret);
451 if (f->inocache->state == INO_STATE_READING)
452 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
463 if (tn->version > mdata_ver) {
464 D1(printk(KERN_DEBUG "Obsoleting old metadata at 0x%08x\n", ref_offset(f->metadata->raw)));
465 jffs2_mark_node_obsolete(c, f->metadata->raw);
466 jffs2_free_full_dnode(f->metadata);
471 D1(printk(KERN_DEBUG "Er. New metadata at 0x%08x with ver %d is actually older than previous %d\n",
472 ref_offset(f->metadata->raw), tn->version, mdata_ver));
473 jffs2_mark_node_obsolete(c, fn->raw);
474 jffs2_free_full_dnode(fn);
480 jffs2_add_full_dnode_to_inode(c, f, fn);
482 /* Zero-sized node at end of version list. Just a metadata update */
483 D1(printk(KERN_DEBUG "metadata @%08x: ver %d\n", ref_offset(fn->raw), tn->version));
485 mdata_ver = tn->version;
489 jffs2_free_tmp_dnode_info(tn);
492 /* No data nodes for this inode. */
493 if (f->inocache->ino != 1) {
494 printk(KERN_WARNING "jffs2_do_read_inode(): No data nodes found for ino #%u\n", f->inocache->ino);
496 if (f->inocache->state == INO_STATE_READING)
497 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
500 printk(KERN_WARNING "jffs2_do_read_inode(): But it has children so we fake some modes for it\n");
502 latest_node->mode = cpu_to_jemode(S_IFDIR|S_IRUGO|S_IWUSR|S_IXUGO);
503 latest_node->version = cpu_to_je32(0);
504 latest_node->atime = latest_node->ctime = latest_node->mtime = cpu_to_je32(0);
505 latest_node->isize = cpu_to_je32(0);
506 latest_node->gid = cpu_to_je16(0);
507 latest_node->uid = cpu_to_je16(0);
508 if (f->inocache->state == INO_STATE_READING)
509 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
513 ret = jffs2_flash_read(c, ref_offset(fn->raw), sizeof(*latest_node), &retlen, (void *)latest_node);
514 if (ret || retlen != sizeof(*latest_node)) {
515 printk(KERN_NOTICE "MTD read in jffs2_do_read_inode() failed: Returned %d, %zd of %zd bytes read\n",
516 ret, retlen, sizeof(*latest_node));
517 /* FIXME: If this fails, there seems to be a memory leak. Find it. */
519 jffs2_do_clear_inode(c, f);
523 crc = crc32(0, latest_node, sizeof(*latest_node)-8);
524 if (crc != je32_to_cpu(latest_node->node_crc)) {
525 printk(KERN_NOTICE "CRC failed for read_inode of inode %u at physical location 0x%x\n", f->inocache->ino, ref_offset(fn->raw));
527 jffs2_do_clear_inode(c, f);
531 switch(jemode_to_cpu(latest_node->mode) & S_IFMT) {
533 if (mctime_ver > je32_to_cpu(latest_node->version)) {
534 /* The times in the latest_node are actually older than
535 mctime in the latest dirent. Cheat. */
536 latest_node->ctime = latest_node->mtime = cpu_to_je32(latest_mctime);
542 /* If it was a regular file, truncate it to the latest node's isize */
543 jffs2_truncate_fraglist(c, &f->fragtree, je32_to_cpu(latest_node->isize));
547 /* Hack to work around broken isize in old symlink code.
548 Remove this when dwmw2 comes to his senses and stops
549 symlinks from being an entirely gratuitous special
551 if (!je32_to_cpu(latest_node->isize))
552 latest_node->isize = latest_node->dsize;
553 /* fall through... */
557 /* Certain inode types should have only one data node, and it's
558 kept as the metadata node */
560 printk(KERN_WARNING "Argh. Special inode #%u with mode 0%o had metadata node\n",
561 f->inocache->ino, jemode_to_cpu(latest_node->mode));
563 jffs2_do_clear_inode(c, f);
566 if (!frag_first(&f->fragtree)) {
567 printk(KERN_WARNING "Argh. Special inode #%u with mode 0%o has no fragments\n",
568 f->inocache->ino, jemode_to_cpu(latest_node->mode));
570 jffs2_do_clear_inode(c, f);
573 /* ASSERT: f->fraglist != NULL */
574 if (frag_next(frag_first(&f->fragtree))) {
575 printk(KERN_WARNING "Argh. Special inode #%u with mode 0x%x had more than one node\n",
576 f->inocache->ino, jemode_to_cpu(latest_node->mode));
577 /* FIXME: Deal with it - check crc32, check for duplicate node, check times and discard the older one */
579 jffs2_do_clear_inode(c, f);
582 /* OK. We're happy */
583 f->metadata = frag_first(&f->fragtree)->node;
584 jffs2_free_node_frag(frag_first(&f->fragtree));
585 f->fragtree = RB_ROOT;
588 if (f->inocache->state == INO_STATE_READING)
589 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
594 void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
596 struct jffs2_full_dirent *fd, *fds;
597 /* I don't think we care about the potential race due to reading this
598 without f->sem. It can never get undeleted. */
599 int deleted = f->inocache && !f->inocache->nlink;
601 /* If it's a deleted inode, grab the alloc_sem. This prevents
602 jffs2_garbage_collect_pass() from deciding that it wants to
603 garbage collect one of the nodes we're just about to mark
604 obsolete -- by the time we drop alloc_sem and return, all
605 the nodes are marked obsolete, and jffs2_g_c_pass() won't
606 call iget() for the inode in question.
608 We also used to do this to keep the temporary BUG() in
609 jffs2_mark_node_obsolete() from triggering.
618 jffs2_mark_node_obsolete(c, f->metadata->raw);
619 jffs2_free_full_dnode(f->metadata);
622 jffs2_kill_fragtree(&f->fragtree, deleted?c:NULL);
629 jffs2_free_full_dirent(fd);
632 if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
633 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);