2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright © 2001-2007 Red Hat, Inc.
6 * Created by David Woodhouse <dwmw2@infradead.org>
8 * For licensing information, see the file 'LICENCE' in this directory.
12 #include <linux/kernel.h>
13 #include <linux/sched.h>
14 #include <linux/slab.h>
16 #include <linux/crc32.h>
17 #include <linux/pagemap.h>
18 #include <linux/mtd/mtd.h>
19 #include <linux/compiler.h>
23 * Check the data CRC of the node.
25 * Returns: 0 if the data CRC is correct;
27 * error code if an error occured.
29 static int check_node_data(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
31 struct jffs2_raw_node_ref *ref = tn->fn->raw;
32 int err = 0, pointed = 0;
33 struct jffs2_eraseblock *jeb;
34 unsigned char *buffer;
35 uint32_t crc, ofs, len;
38 BUG_ON(tn->csize == 0);
40 if (!jffs2_is_writebuffered(c))
43 /* Calculate how many bytes were already checked */
44 ofs = ref_offset(ref) + sizeof(struct jffs2_raw_inode);
45 len = ofs % c->wbuf_pagesize;
47 len = c->wbuf_pagesize - len;
49 if (len >= tn->csize) {
50 dbg_readinode("no need to check node at %#08x, data length %u, data starts at %#08x - it has already been checked.\n",
51 ref_offset(ref), tn->csize, ofs);
56 len = tn->csize - len;
58 dbg_readinode("check node at %#08x, data length %u, partial CRC %#08x, correct CRC %#08x, data starts at %#08x, start checking from %#08x - %u bytes.\n",
59 ref_offset(ref), tn->csize, tn->partial_crc, tn->data_crc, ofs - len, ofs, len);
62 /* TODO: instead, incapsulate point() stuff to jffs2_flash_read(),
63 * adding and jffs2_flash_read_end() interface. */
65 err = c->mtd->point(c->mtd, ofs, len, &retlen, &buffer);
66 if (!err && retlen < tn->csize) {
67 JFFS2_WARNING("MTD point returned len too short: %zu instead of %u.\n", retlen, tn->csize);
68 c->mtd->unpoint(c->mtd, buffer, ofs, len);
70 JFFS2_WARNING("MTD point failed: error code %d.\n", err);
72 pointed = 1; /* succefully pointed to device */
77 buffer = kmalloc(len, GFP_KERNEL);
78 if (unlikely(!buffer))
81 /* TODO: this is very frequent pattern, make it a separate
83 err = jffs2_flash_read(c, ofs, len, &retlen, buffer);
85 JFFS2_ERROR("can not read %d bytes from 0x%08x, error code: %d.\n", len, ofs, err);
90 JFFS2_ERROR("short read at %#08x: %zd instead of %d.\n", ofs, retlen, len);
96 /* Continue calculating CRC */
97 crc = crc32(tn->partial_crc, buffer, len);
102 c->mtd->unpoint(c->mtd, buffer, ofs, len);
105 if (crc != tn->data_crc) {
106 JFFS2_NOTICE("wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x.\n",
107 ofs, tn->data_crc, crc);
112 jeb = &c->blocks[ref->flash_offset / c->sector_size];
113 len = ref_totlen(c, jeb, ref);
114 /* If it should be REF_NORMAL, it'll get marked as such when
115 we build the fragtree, shortly. No need to worry about GC
116 moving it while it's marked REF_PRISTINE -- GC won't happen
117 till we've finished checking every inode anyway. */
118 ref->flash_offset |= REF_PRISTINE;
120 * Mark the node as having been checked and fix the
121 * accounting accordingly.
123 spin_lock(&c->erase_completion_lock);
124 jeb->used_size += len;
125 jeb->unchecked_size -= len;
127 c->unchecked_size -= len;
128 jffs2_dbg_acct_paranoia_check_nolock(c, jeb);
129 spin_unlock(&c->erase_completion_lock);
138 c->mtd->unpoint(c->mtd, buffer, ofs, len);
144 * Helper function for jffs2_add_older_frag_to_fragtree().
146 * Checks the node if we are in the checking stage.
148 static int check_tn_node(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
152 BUG_ON(ref_obsolete(tn->fn->raw));
154 /* We only check the data CRC of unchecked nodes */
155 if (ref_flags(tn->fn->raw) != REF_UNCHECKED)
158 dbg_readinode("check node %#04x-%#04x, phys offs %#08x\n",
159 tn->fn->ofs, tn->fn->ofs + tn->fn->size, ref_offset(tn->fn->raw));
161 ret = check_node_data(c, tn);
162 if (unlikely(ret < 0)) {
163 JFFS2_ERROR("check_node_data() returned error: %d.\n",
165 } else if (unlikely(ret > 0)) {
166 dbg_readinode("CRC error, mark it obsolete.\n");
167 jffs2_mark_node_obsolete(c, tn->fn->raw);
173 static struct jffs2_tmp_dnode_info *jffs2_lookup_tn(struct rb_root *tn_root, uint32_t offset)
175 struct rb_node *next;
176 struct jffs2_tmp_dnode_info *tn = NULL;
178 dbg_readinode("root %p, offset %d\n", tn_root, offset);
180 next = tn_root->rb_node;
183 tn = rb_entry(next, struct jffs2_tmp_dnode_info, rb);
185 if (tn->fn->ofs < offset)
186 next = tn->rb.rb_right;
187 else if (tn->fn->ofs >= offset)
188 next = tn->rb.rb_left;
197 static void jffs2_kill_tn(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
199 jffs2_mark_node_obsolete(c, tn->fn->raw);
200 jffs2_free_full_dnode(tn->fn);
201 jffs2_free_tmp_dnode_info(tn);
204 * This function is used when we read an inode. Data nodes arrive in
205 * arbitrary order -- they may be older or newer than the nodes which
206 * are already in the tree. Where overlaps occur, the older node can
207 * be discarded as long as the newer passes the CRC check. We don't
208 * bother to keep track of holes in this rbtree, and neither do we deal
209 * with frags -- we can have multiple entries starting at the same
210 * offset, and the one with the smallest length will come first in the
213 * Returns 0 if the node was inserted
214 * 1 if the node is obsolete (because we can't mark it so yet)
215 * < 0 an if error occurred
217 static int jffs2_add_tn_to_tree(struct jffs2_sb_info *c,
218 struct jffs2_readinode_info *rii,
219 struct jffs2_tmp_dnode_info *tn)
221 uint32_t fn_end = tn->fn->ofs + tn->fn->size;
222 struct jffs2_tmp_dnode_info *this;
224 dbg_readinode("insert fragment %#04x-%#04x, ver %u\n", tn->fn->ofs, fn_end, tn->version);
226 /* If a node has zero dsize, we only have to keep if it if it might be the
227 node with highest version -- i.e. the one which will end up as f->metadata.
228 Note that such nodes won't be REF_UNCHECKED since there are no data to
232 /* We had a candidate mdata node already */
233 dbg_readinode("kill old mdata with ver %d\n", rii->mdata_tn->version);
234 jffs2_kill_tn(c, rii->mdata_tn);
237 dbg_readinode("keep new mdata with ver %d\n", tn->version);
241 /* Find the earliest node which _may_ be relevant to this one */
242 this = jffs2_lookup_tn(&rii->tn_root, tn->fn->ofs);
244 /* First addition to empty tree. $DEITY how I love the easy cases */
245 rb_link_node(&tn->rb, NULL, &rii->tn_root.rb_node);
246 rb_insert_color(&tn->rb, &rii->tn_root);
247 dbg_readinode("keep new frag\n");
251 /* If the node is coincident with another at a lower address,
252 back up until the other node is found. It may be relevant */
253 while (tn->overlapped)
256 dbg_readinode("'this' found %#04x-%#04x (%s)\n", this->fn->ofs, this->fn->ofs + this->fn->size, this->fn ? "data" : "hole");
259 if (this->fn->ofs > fn_end)
261 dbg_readinode("Ponder this ver %d, 0x%x-0x%x\n",
262 this->version, this->fn->ofs, this->fn->size);
264 if (this->version == tn->version) {
265 /* Version number collision means REF_PRISTINE GC. Accept either of them
266 as long as the CRC is correct. Check the one we have already... */
267 if (!check_tn_node(c, this)) {
268 /* The one we already had was OK. Keep it and throw away the new one */
269 dbg_readinode("Like old node. Throw away new\n");
270 jffs2_kill_tn(c, tn);
273 /* Who cares if the new one is good; keep it for now anyway. */
274 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
275 /* Same overlapping from in front and behind */
276 jffs2_kill_tn(c, this);
277 dbg_readinode("Like new node. Throw away old\n");
281 if (this->version < tn->version &&
282 this->fn->ofs >= tn->fn->ofs &&
283 this->fn->ofs + this->fn->size <= fn_end) {
284 /* New node entirely overlaps 'this' */
285 if (check_tn_node(c, tn)) {
286 dbg_readinode("new node bad CRC\n");
287 jffs2_kill_tn(c, tn);
290 /* ... and is good. Kill 'this'... */
291 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
292 jffs2_kill_tn(c, this);
293 /* ... and any subsequent nodes which are also overlapped */
295 while (this && this->fn->ofs + this->fn->size < fn_end) {
296 struct jffs2_tmp_dnode_info *next = tn_next(this);
297 if (this->version < tn->version) {
298 tn_erase(this, &rii->tn_root);
299 dbg_readinode("Kill overlapped ver %d, 0x%x-0x%x\n",
300 this->version, this->fn->ofs,
301 this->fn->ofs+this->fn->size);
302 jffs2_kill_tn(c, this);
306 dbg_readinode("Done inserting new\n");
309 if (this->version > tn->version &&
310 this->fn->ofs <= tn->fn->ofs &&
311 this->fn->ofs+this->fn->size >= fn_end) {
312 /* New node entirely overlapped by 'this' */
313 if (!check_tn_node(c, this)) {
314 dbg_readinode("Good CRC on old node. Kill new\n");
315 jffs2_kill_tn(c, tn);
318 /* ... but 'this' was bad. Replace it... */
319 tn->overlapped = this->overlapped;
320 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
321 dbg_readinode("Bad CRC on old overlapping node. Kill it\n");
322 jffs2_kill_tn(c, this);
326 this = tn_next(this);
329 /* We neither completely obsoleted nor were completely
330 obsoleted by an earlier node. Insert into the tree */
332 struct rb_node *parent;
333 struct rb_node **link = &rii->tn_root.rb_node;
334 struct jffs2_tmp_dnode_info *insert_point;
338 insert_point = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
339 if (tn->fn->ofs > insert_point->fn->ofs)
340 link = &insert_point->rb.rb_right;
341 else if (tn->fn->ofs < insert_point->fn->ofs ||
342 tn->fn->size < insert_point->fn->size)
343 link = &insert_point->rb.rb_left;
345 link = &insert_point->rb.rb_right;
347 rb_link_node(&tn->rb, &insert_point->rb, link);
348 rb_insert_color(&tn->rb, &rii->tn_root);
352 /* If there's anything behind that overlaps us, note it */
356 if (this->fn->ofs + this->fn->size > tn->fn->ofs) {
357 dbg_readinode("Node is overlapped by %p (v %d, 0x%x-0x%x)\n",
358 this, this->version, this->fn->ofs,
359 this->fn->ofs+this->fn->size);
363 if (!this->overlapped)
365 this = tn_prev(this);
369 /* If the new node overlaps anything ahead, note it */
371 while (this && this->fn->ofs < fn_end) {
372 this->overlapped = 1;
373 dbg_readinode("Node ver %d, 0x%x-0x%x is overlapped\n",
374 this->version, this->fn->ofs,
375 this->fn->ofs+this->fn->size);
376 this = tn_next(this);
381 /* Trivial function to remove the last node in the tree. Which by definition
382 has no right-hand -- so can be removed just by making its only child (if
383 any) take its place under its parent. */
384 static void eat_last(struct rb_root *root, struct rb_node *node)
386 struct rb_node *parent = rb_parent(node);
387 struct rb_node **link;
390 BUG_ON(node->rb_right);
393 link = &root->rb_node;
394 else if (node == parent->rb_left)
395 link = &parent->rb_left;
397 link = &parent->rb_right;
399 *link = node->rb_left;
400 /* Colour doesn't matter now. Only the parent pointer. */
402 node->rb_left->rb_parent_color = node->rb_parent_color;
405 /* We put this in reverse order, so we can just use eat_last */
406 static void ver_insert(struct rb_root *ver_root, struct jffs2_tmp_dnode_info *tn)
408 struct rb_node **link = &ver_root->rb_node;
409 struct rb_node *parent = NULL;
410 struct jffs2_tmp_dnode_info *this_tn;
414 this_tn = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
416 if (tn->version > this_tn->version)
417 link = &parent->rb_left;
419 link = &parent->rb_right;
421 dbg_readinode("Link new node at %p (root is %p)\n", link, ver_root);
422 rb_link_node(&tn->rb, parent, link);
423 rb_insert_color(&tn->rb, ver_root);
426 /* Build final, normal fragtree from tn tree. It doesn't matter which order
427 we add nodes to the real fragtree, as long as they don't overlap. And
428 having thrown away the majority of overlapped nodes as we went, there
429 really shouldn't be many sets of nodes which do overlap. If we start at
430 the end, we can use the overlap markers -- we can just eat nodes which
431 aren't overlapped, and when we encounter nodes which _do_ overlap we
432 sort them all into a temporary tree in version order before replaying them. */
433 static int jffs2_build_inode_fragtree(struct jffs2_sb_info *c,
434 struct jffs2_inode_info *f,
435 struct jffs2_readinode_info *rii)
437 struct jffs2_tmp_dnode_info *pen, *last, *this;
438 struct rb_root ver_root = RB_ROOT;
439 uint32_t high_ver = 0;
442 dbg_readinode("potential mdata is ver %d at %p\n", rii->mdata_tn->version, rii->mdata_tn);
443 high_ver = rii->mdata_tn->version;
444 rii->latest_ref = rii->mdata_tn->fn->raw;
446 #ifdef JFFS2_DBG_READINODE_MESSAGES
447 this = tn_last(&rii->tn_root);
449 dbg_readinode("tn %p ver %d range 0x%x-0x%x ov %d\n", this, this->version, this->fn->ofs,
450 this->fn->ofs+this->fn->size, this->overlapped);
451 this = tn_prev(this);
454 pen = tn_last(&rii->tn_root);
455 while ((last = pen)) {
458 eat_last(&rii->tn_root, &last->rb);
459 ver_insert(&ver_root, last);
461 if (unlikely(last->overlapped))
464 /* Now we have a bunch of nodes in reverse version
465 order, in the tree at ver_root. Most of the time,
466 there'll actually be only one node in the 'tree',
468 this = tn_last(&ver_root);
471 struct jffs2_tmp_dnode_info *vers_next;
473 vers_next = tn_prev(this);
474 eat_last(&ver_root, &this->rb);
475 if (check_tn_node(c, this)) {
476 dbg_readinode("node ver %d, 0x%x-0x%x failed CRC\n",
477 this->version, this->fn->ofs,
478 this->fn->ofs+this->fn->size);
479 jffs2_kill_tn(c, this);
481 if (this->version > high_ver) {
482 /* Note that this is different from the other
483 highest_version, because this one is only
484 counting _valid_ nodes which could give the
485 latest inode metadata */
486 high_ver = this->version;
487 rii->latest_ref = this->fn->raw;
489 dbg_readinode("Add %p (v %d, 0x%x-0x%x, ov %d) to fragtree\n",
490 this, this->version, this->fn->ofs,
491 this->fn->ofs+this->fn->size, this->overlapped);
493 ret = jffs2_add_full_dnode_to_inode(c, f, this->fn);
495 /* Free the nodes in vers_root; let the caller
496 deal with the rest */
497 JFFS2_ERROR("Add node to tree failed %d\n", ret);
499 vers_next = tn_prev(this);
500 if (check_tn_node(c, this))
501 jffs2_mark_node_obsolete(c, this->fn->raw);
502 jffs2_free_full_dnode(this->fn);
503 jffs2_free_tmp_dnode_info(this);
507 eat_last(&ver_root, &vers_next->rb);
511 jffs2_free_tmp_dnode_info(this);
519 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
521 struct rb_node *this;
522 struct jffs2_tmp_dnode_info *tn;
524 this = list->rb_node;
526 /* Now at bottom of tree */
529 this = this->rb_left;
530 else if (this->rb_right)
531 this = this->rb_right;
533 tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
534 jffs2_free_full_dnode(tn->fn);
535 jffs2_free_tmp_dnode_info(tn);
537 this = rb_parent(this);
541 if (this->rb_left == &tn->rb)
542 this->rb_left = NULL;
543 else if (this->rb_right == &tn->rb)
544 this->rb_right = NULL;
548 list->rb_node = NULL;
551 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
553 struct jffs2_full_dirent *next;
557 jffs2_free_full_dirent(fd);
562 /* Returns first valid node after 'ref'. May return 'ref' */
563 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
565 while (ref && ref->next_in_ino) {
566 if (!ref_obsolete(ref))
568 dbg_noderef("node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref));
569 ref = ref->next_in_ino;
575 * Helper function for jffs2_get_inode_nodes().
576 * It is called every time an directory entry node is found.
578 * Returns: 0 on succes;
579 * 1 if the node should be marked obsolete;
580 * negative error code on failure.
582 static inline int read_direntry(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
583 struct jffs2_raw_dirent *rd, size_t read,
584 struct jffs2_readinode_info *rii)
586 struct jffs2_full_dirent *fd;
589 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
590 BUG_ON(ref_obsolete(ref));
592 crc = crc32(0, rd, sizeof(*rd) - 8);
593 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
594 JFFS2_NOTICE("header CRC failed on dirent node at %#08x: read %#08x, calculated %#08x\n",
595 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
596 jffs2_mark_node_obsolete(c, ref);
600 /* If we've never checked the CRCs on this node, check them now */
601 if (ref_flags(ref) == REF_UNCHECKED) {
602 struct jffs2_eraseblock *jeb;
606 if (unlikely(PAD((rd->nsize + sizeof(*rd))) != PAD(je32_to_cpu(rd->totlen)))) {
607 JFFS2_ERROR("illegal nsize in node at %#08x: nsize %#02x, totlen %#04x\n",
608 ref_offset(ref), rd->nsize, je32_to_cpu(rd->totlen));
609 jffs2_mark_node_obsolete(c, ref);
613 jeb = &c->blocks[ref->flash_offset / c->sector_size];
614 len = ref_totlen(c, jeb, ref);
616 spin_lock(&c->erase_completion_lock);
617 jeb->used_size += len;
618 jeb->unchecked_size -= len;
620 c->unchecked_size -= len;
621 ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
622 spin_unlock(&c->erase_completion_lock);
625 fd = jffs2_alloc_full_dirent(rd->nsize + 1);
630 fd->version = je32_to_cpu(rd->version);
631 fd->ino = je32_to_cpu(rd->ino);
634 if (fd->version > rii->highest_version)
635 rii->highest_version = fd->version;
637 /* Pick out the mctime of the latest dirent */
638 if(fd->version > rii->mctime_ver && je32_to_cpu(rd->mctime)) {
639 rii->mctime_ver = fd->version;
640 rii->latest_mctime = je32_to_cpu(rd->mctime);
644 * Copy as much of the name as possible from the raw
645 * dirent we've already read from the flash.
647 if (read > sizeof(*rd))
648 memcpy(&fd->name[0], &rd->name[0],
649 min_t(uint32_t, rd->nsize, (read - sizeof(*rd)) ));
651 /* Do we need to copy any more of the name directly from the flash? */
652 if (rd->nsize + sizeof(*rd) > read) {
655 int already = read - sizeof(*rd);
657 err = jffs2_flash_read(c, (ref_offset(ref)) + read,
658 rd->nsize - already, &read, &fd->name[already]);
659 if (unlikely(read != rd->nsize - already) && likely(!err))
663 JFFS2_ERROR("read remainder of name: error %d\n", err);
664 jffs2_free_full_dirent(fd);
669 fd->nhash = full_name_hash(fd->name, rd->nsize);
671 fd->name[rd->nsize] = '\0';
674 * Wheee. We now have a complete jffs2_full_dirent structure, with
675 * the name in it and everything. Link it into the list
677 jffs2_add_fd_to_list(c, fd, &rii->fds);
683 * Helper function for jffs2_get_inode_nodes().
684 * It is called every time an inode node is found.
686 * Returns: 0 on success;
687 * 1 if the node should be marked obsolete;
688 * negative error code on failure.
690 static inline int read_dnode(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
691 struct jffs2_raw_inode *rd, int rdlen,
692 struct jffs2_readinode_info *rii)
694 struct jffs2_tmp_dnode_info *tn;
699 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
700 BUG_ON(ref_obsolete(ref));
702 crc = crc32(0, rd, sizeof(*rd) - 8);
703 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
704 JFFS2_NOTICE("node CRC failed on dnode at %#08x: read %#08x, calculated %#08x\n",
705 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
706 jffs2_mark_node_obsolete(c, ref);
710 tn = jffs2_alloc_tmp_dnode_info();
712 JFFS2_ERROR("failed to allocate tn (%zu bytes).\n", sizeof(*tn));
717 csize = je32_to_cpu(rd->csize);
719 /* If we've never checked the CRCs on this node, check them now */
720 if (ref_flags(ref) == REF_UNCHECKED) {
723 if (unlikely(je32_to_cpu(rd->offset) > je32_to_cpu(rd->isize)) ||
724 unlikely(PAD(je32_to_cpu(rd->csize) + sizeof(*rd)) != PAD(je32_to_cpu(rd->totlen)))) {
725 JFFS2_WARNING("inode node header CRC is corrupted at %#08x\n", ref_offset(ref));
726 jffs2_dbg_dump_node(c, ref_offset(ref));
730 if (jffs2_is_writebuffered(c) && csize != 0) {
731 /* At this point we are supposed to check the data CRC
732 * of our unchecked node. But thus far, we do not
733 * know whether the node is valid or obsolete. To
734 * figure this out, we need to walk all the nodes of
735 * the inode and build the inode fragtree. We don't
736 * want to spend time checking data of nodes which may
737 * later be found to be obsolete. So we put off the full
738 * data CRC checking until we have read all the inode
739 * nodes and have started building the fragtree.
741 * The fragtree is being built starting with nodes
742 * having the highest version number, so we'll be able
743 * to detect whether a node is valid (i.e., it is not
744 * overlapped by a node with higher version) or not.
745 * And we'll be able to check only those nodes, which
748 * Of course, this optimization only makes sense in case
749 * of NAND flashes (or other flashes whith
750 * !jffs2_can_mark_obsolete()), since on NOR flashes
751 * nodes are marked obsolete physically.
753 * Since NAND flashes (or other flashes with
754 * jffs2_is_writebuffered(c)) are anyway read by
755 * fractions of c->wbuf_pagesize, and we have just read
756 * the node header, it is likely that the starting part
757 * of the node data is also read when we read the
758 * header. So we don't mind to check the CRC of the
759 * starting part of the data of the node now, and check
760 * the second part later (in jffs2_check_node_data()).
761 * Of course, we will not need to re-read and re-check
762 * the NAND page which we have just read. This is why we
763 * read the whole NAND page at jffs2_get_inode_nodes(),
764 * while we needed only the node header.
768 /* 'buf' will point to the start of data */
769 buf = (unsigned char *)rd + sizeof(*rd);
770 /* len will be the read data length */
771 len = min_t(uint32_t, rdlen - sizeof(*rd), csize);
772 tn->partial_crc = crc32(0, buf, len);
774 dbg_readinode("Calculates CRC (%#08x) for %d bytes, csize %d\n", tn->partial_crc, len, csize);
776 /* If we actually calculated the whole data CRC
777 * and it is wrong, drop the node. */
778 if (len >= csize && unlikely(tn->partial_crc != je32_to_cpu(rd->data_crc))) {
779 JFFS2_NOTICE("wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x.\n",
780 ref_offset(ref), tn->partial_crc, je32_to_cpu(rd->data_crc));
784 } else if (csize == 0) {
786 * We checked the header CRC. If the node has no data, adjust
787 * the space accounting now. For other nodes this will be done
788 * later either when the node is marked obsolete or when its
791 struct jffs2_eraseblock *jeb;
793 dbg_readinode("the node has no data.\n");
794 jeb = &c->blocks[ref->flash_offset / c->sector_size];
795 len = ref_totlen(c, jeb, ref);
797 spin_lock(&c->erase_completion_lock);
798 jeb->used_size += len;
799 jeb->unchecked_size -= len;
801 c->unchecked_size -= len;
802 ref->flash_offset = ref_offset(ref) | REF_NORMAL;
803 spin_unlock(&c->erase_completion_lock);
807 tn->fn = jffs2_alloc_full_dnode();
809 JFFS2_ERROR("alloc fn failed\n");
814 tn->version = je32_to_cpu(rd->version);
815 tn->fn->ofs = je32_to_cpu(rd->offset);
816 tn->data_crc = je32_to_cpu(rd->data_crc);
821 if (tn->version > rii->highest_version)
822 rii->highest_version = tn->version;
824 /* There was a bug where we wrote hole nodes out with
825 csize/dsize swapped. Deal with it */
826 if (rd->compr == JFFS2_COMPR_ZERO && !je32_to_cpu(rd->dsize) && csize)
827 tn->fn->size = csize;
828 else // normal case...
829 tn->fn->size = je32_to_cpu(rd->dsize);
831 dbg_readinode("dnode @%08x: ver %u, offset %#04x, dsize %#04x, csize %#04x\n",
832 ref_offset(ref), je32_to_cpu(rd->version), je32_to_cpu(rd->offset), je32_to_cpu(rd->dsize), csize);
834 ret = jffs2_add_tn_to_tree(c, rii, tn);
837 jffs2_free_full_dnode(tn->fn);
839 jffs2_free_tmp_dnode_info(tn);
842 #ifdef JFFS2_DBG_READINODE_MESSAGES
843 dbg_readinode("After adding ver %d:\n", je32_to_cpu(rd->version));
844 tn = tn_first(&rii->tn_root);
846 dbg_readinode("%p: v %d r 0x%x-0x%x ov %d\n",
847 tn, tn->version, tn->fn->ofs,
848 tn->fn->ofs+tn->fn->size, tn->overlapped);
856 * Helper function for jffs2_get_inode_nodes().
857 * It is called every time an unknown node is found.
859 * Returns: 0 on success;
860 * 1 if the node should be marked obsolete;
861 * negative error code on failure.
863 static inline int read_unknown(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref, struct jffs2_unknown_node *un)
865 /* We don't mark unknown nodes as REF_UNCHECKED */
866 if (ref_flags(ref) == REF_UNCHECKED) {
867 JFFS2_ERROR("REF_UNCHECKED but unknown node at %#08x\n",
869 JFFS2_ERROR("Node is {%04x,%04x,%08x,%08x}. Please report this error.\n",
870 je16_to_cpu(un->magic), je16_to_cpu(un->nodetype),
871 je32_to_cpu(un->totlen), je32_to_cpu(un->hdr_crc));
872 jffs2_mark_node_obsolete(c, ref);
876 un->nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(un->nodetype));
878 switch(je16_to_cpu(un->nodetype) & JFFS2_COMPAT_MASK) {
880 case JFFS2_FEATURE_INCOMPAT:
881 JFFS2_ERROR("unknown INCOMPAT nodetype %#04X at %#08x\n",
882 je16_to_cpu(un->nodetype), ref_offset(ref));
887 case JFFS2_FEATURE_ROCOMPAT:
888 JFFS2_ERROR("unknown ROCOMPAT nodetype %#04X at %#08x\n",
889 je16_to_cpu(un->nodetype), ref_offset(ref));
890 BUG_ON(!(c->flags & JFFS2_SB_FLAG_RO));
893 case JFFS2_FEATURE_RWCOMPAT_COPY:
894 JFFS2_NOTICE("unknown RWCOMPAT_COPY nodetype %#04X at %#08x\n",
895 je16_to_cpu(un->nodetype), ref_offset(ref));
898 case JFFS2_FEATURE_RWCOMPAT_DELETE:
899 JFFS2_NOTICE("unknown RWCOMPAT_DELETE nodetype %#04X at %#08x\n",
900 je16_to_cpu(un->nodetype), ref_offset(ref));
901 jffs2_mark_node_obsolete(c, ref);
909 * Helper function for jffs2_get_inode_nodes().
910 * The function detects whether more data should be read and reads it if yes.
912 * Returns: 0 on succes;
913 * negative error code on failure.
915 static int read_more(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
916 int needed_len, int *rdlen, unsigned char *buf)
918 int err, to_read = needed_len - *rdlen;
922 if (jffs2_is_writebuffered(c)) {
923 int rem = to_read % c->wbuf_pagesize;
926 to_read += c->wbuf_pagesize - rem;
929 /* We need to read more data */
930 offs = ref_offset(ref) + *rdlen;
932 dbg_readinode("read more %d bytes\n", to_read);
934 err = jffs2_flash_read(c, offs, to_read, &retlen, buf + *rdlen);
936 JFFS2_ERROR("can not read %d bytes from 0x%08x, "
937 "error code: %d.\n", to_read, offs, err);
941 if (retlen < to_read) {
942 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n",
943 offs, retlen, to_read);
951 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
952 with this ino. Perform a preliminary ordering on data nodes, throwing away
953 those which are completely obsoleted by newer ones. The naïve approach we
954 use to take of just returning them _all_ in version order will cause us to
955 run out of memory in certain degenerate cases. */
956 static int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
957 struct jffs2_readinode_info *rii)
959 struct jffs2_raw_node_ref *ref, *valid_ref;
960 unsigned char *buf = NULL;
961 union jffs2_node_union *node;
967 dbg_readinode("ino #%u\n", f->inocache->ino);
969 /* FIXME: in case of NOR and available ->point() this
970 * needs to be fixed. */
971 len = sizeof(union jffs2_node_union) + c->wbuf_pagesize;
972 buf = kmalloc(len, GFP_KERNEL);
976 spin_lock(&c->erase_completion_lock);
977 valid_ref = jffs2_first_valid_node(f->inocache->nodes);
978 if (!valid_ref && f->inocache->ino != 1)
979 JFFS2_WARNING("Eep. No valid nodes for ino #%u.\n", f->inocache->ino);
981 /* We can hold a pointer to a non-obsolete node without the spinlock,
982 but _obsolete_ nodes may disappear at any time, if the block
983 they're in gets erased. So if we mark 'ref' obsolete while we're
984 not holding the lock, it can go away immediately. For that reason,
985 we find the next valid node first, before processing 'ref'.
988 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
989 spin_unlock(&c->erase_completion_lock);
994 * At this point we don't know the type of the node we're going
995 * to read, so we do not know the size of its header. In order
996 * to minimize the amount of flash IO we assume the header is
997 * of size = JFFS2_MIN_NODE_HEADER.
999 len = JFFS2_MIN_NODE_HEADER;
1000 if (jffs2_is_writebuffered(c)) {
1004 * We are about to read JFFS2_MIN_NODE_HEADER bytes,
1005 * but this flash has some minimal I/O unit. It is
1006 * possible that we'll need to read more soon, so read
1007 * up to the next min. I/O unit, in order not to
1008 * re-read the same min. I/O unit twice.
1010 end = ref_offset(ref) + len;
1011 rem = end % c->wbuf_pagesize;
1013 end += c->wbuf_pagesize - rem;
1014 len = end - ref_offset(ref);
1017 dbg_readinode("read %d bytes at %#08x(%d).\n", len, ref_offset(ref), ref_flags(ref));
1019 /* FIXME: point() */
1020 err = jffs2_flash_read(c, ref_offset(ref), len, &retlen, buf);
1022 JFFS2_ERROR("can not read %d bytes from 0x%08x, " "error code: %d.\n", len, ref_offset(ref), err);
1027 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n", ref_offset(ref), retlen, len);
1032 node = (union jffs2_node_union *)buf;
1034 /* No need to mask in the valid bit; it shouldn't be invalid */
1035 if (je32_to_cpu(node->u.hdr_crc) != crc32(0, node, sizeof(node->u)-4)) {
1036 JFFS2_NOTICE("Node header CRC failed at %#08x. {%04x,%04x,%08x,%08x}\n",
1037 ref_offset(ref), je16_to_cpu(node->u.magic),
1038 je16_to_cpu(node->u.nodetype),
1039 je32_to_cpu(node->u.totlen),
1040 je32_to_cpu(node->u.hdr_crc));
1041 jffs2_dbg_dump_node(c, ref_offset(ref));
1042 jffs2_mark_node_obsolete(c, ref);
1045 if (je16_to_cpu(node->u.magic) != JFFS2_MAGIC_BITMASK) {
1046 /* Not a JFFS2 node, whinge and move on */
1047 JFFS2_NOTICE("Wrong magic bitmask 0x%04x in node header at %#08x.\n",
1048 je16_to_cpu(node->u.magic), ref_offset(ref));
1049 jffs2_mark_node_obsolete(c, ref);
1053 switch (je16_to_cpu(node->u.nodetype)) {
1055 case JFFS2_NODETYPE_DIRENT:
1057 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_dirent)) {
1058 err = read_more(c, ref, sizeof(struct jffs2_raw_dirent), &len, buf);
1063 err = read_direntry(c, ref, &node->d, retlen, rii);
1069 case JFFS2_NODETYPE_INODE:
1071 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_inode)) {
1072 err = read_more(c, ref, sizeof(struct jffs2_raw_inode), &len, buf);
1077 err = read_dnode(c, ref, &node->i, len, rii);
1084 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_unknown_node)) {
1085 err = read_more(c, ref, sizeof(struct jffs2_unknown_node), &len, buf);
1090 err = read_unknown(c, ref, &node->u);
1092 jffs2_mark_node_obsolete(c, ref);
1094 } else if (unlikely(err))
1099 spin_lock(&c->erase_completion_lock);
1102 spin_unlock(&c->erase_completion_lock);
1105 f->highest_version = rii->highest_version;
1107 dbg_readinode("nodes of inode #%u were read, the highest version is %u, latest_mctime %u, mctime_ver %u.\n",
1108 f->inocache->ino, rii->highest_version, rii->latest_mctime,
1113 jffs2_free_tmp_dnode_info_list(&rii->tn_root);
1114 jffs2_free_full_dirent_list(rii->fds);
1120 static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
1121 struct jffs2_inode_info *f,
1122 struct jffs2_raw_inode *latest_node)
1124 struct jffs2_readinode_info rii;
1125 uint32_t crc, new_size;
1129 dbg_readinode("ino #%u nlink is %d\n", f->inocache->ino, f->inocache->nlink);
1131 memset(&rii, 0, sizeof(rii));
1133 /* Grab all nodes relevant to this ino */
1134 ret = jffs2_get_inode_nodes(c, f, &rii);
1137 JFFS2_ERROR("cannot read nodes for ino %u, returned error is %d\n", f->inocache->ino, ret);
1138 if (f->inocache->state == INO_STATE_READING)
1139 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1143 ret = jffs2_build_inode_fragtree(c, f, &rii);
1145 JFFS2_ERROR("Failed to build final fragtree for inode #%u: error %d\n",
1146 f->inocache->ino, ret);
1147 if (f->inocache->state == INO_STATE_READING)
1148 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1149 jffs2_free_tmp_dnode_info_list(&rii.tn_root);
1150 /* FIXME: We could at least crc-check them all */
1152 jffs2_free_full_dnode(rii.mdata_tn->fn);
1153 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1154 rii.mdata_tn = NULL;
1160 if (rii.mdata_tn->fn->raw == rii.latest_ref) {
1161 f->metadata = rii.mdata_tn->fn;
1162 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1164 jffs2_kill_tn(c, rii.mdata_tn);
1166 rii.mdata_tn = NULL;
1171 jffs2_dbg_fragtree_paranoia_check_nolock(f);
1173 if (unlikely(!rii.latest_ref)) {
1174 /* No data nodes for this inode. */
1175 if (f->inocache->ino != 1) {
1176 JFFS2_WARNING("no data nodes found for ino #%u\n", f->inocache->ino);
1178 if (f->inocache->state == INO_STATE_READING)
1179 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1182 JFFS2_NOTICE("but it has children so we fake some modes for it\n");
1184 latest_node->mode = cpu_to_jemode(S_IFDIR|S_IRUGO|S_IWUSR|S_IXUGO);
1185 latest_node->version = cpu_to_je32(0);
1186 latest_node->atime = latest_node->ctime = latest_node->mtime = cpu_to_je32(0);
1187 latest_node->isize = cpu_to_je32(0);
1188 latest_node->gid = cpu_to_je16(0);
1189 latest_node->uid = cpu_to_je16(0);
1190 if (f->inocache->state == INO_STATE_READING)
1191 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1195 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref), sizeof(*latest_node), &retlen, (void *)latest_node);
1196 if (ret || retlen != sizeof(*latest_node)) {
1197 JFFS2_ERROR("failed to read from flash: error %d, %zd of %zd bytes read\n",
1198 ret, retlen, sizeof(*latest_node));
1199 /* FIXME: If this fails, there seems to be a memory leak. Find it. */
1201 jffs2_do_clear_inode(c, f);
1202 return ret?ret:-EIO;
1205 crc = crc32(0, latest_node, sizeof(*latest_node)-8);
1206 if (crc != je32_to_cpu(latest_node->node_crc)) {
1207 JFFS2_ERROR("CRC failed for read_inode of inode %u at physical location 0x%x\n",
1208 f->inocache->ino, ref_offset(rii.latest_ref));
1210 jffs2_do_clear_inode(c, f);
1214 switch(jemode_to_cpu(latest_node->mode) & S_IFMT) {
1216 if (rii.mctime_ver > je32_to_cpu(latest_node->version)) {
1217 /* The times in the latest_node are actually older than
1218 mctime in the latest dirent. Cheat. */
1219 latest_node->ctime = latest_node->mtime = cpu_to_je32(rii.latest_mctime);
1225 /* If it was a regular file, truncate it to the latest node's isize */
1226 new_size = jffs2_truncate_fragtree(c, &f->fragtree, je32_to_cpu(latest_node->isize));
1227 if (new_size != je32_to_cpu(latest_node->isize)) {
1228 JFFS2_WARNING("Truncating ino #%u to %d bytes failed because it only had %d bytes to start with!\n",
1229 f->inocache->ino, je32_to_cpu(latest_node->isize), new_size);
1230 latest_node->isize = cpu_to_je32(new_size);
1235 /* Hack to work around broken isize in old symlink code.
1236 Remove this when dwmw2 comes to his senses and stops
1237 symlinks from being an entirely gratuitous special
1239 if (!je32_to_cpu(latest_node->isize))
1240 latest_node->isize = latest_node->dsize;
1242 if (f->inocache->state != INO_STATE_CHECKING) {
1243 /* Symlink's inode data is the target path. Read it and
1244 * keep in RAM to facilitate quick follow symlink
1246 f->target = kmalloc(je32_to_cpu(latest_node->csize) + 1, GFP_KERNEL);
1248 JFFS2_ERROR("can't allocate %d bytes of memory for the symlink target path cache\n", je32_to_cpu(latest_node->csize));
1250 jffs2_do_clear_inode(c, f);
1254 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref) + sizeof(*latest_node),
1255 je32_to_cpu(latest_node->csize), &retlen, (char *)f->target);
1257 if (ret || retlen != je32_to_cpu(latest_node->csize)) {
1258 if (retlen != je32_to_cpu(latest_node->csize))
1263 jffs2_do_clear_inode(c, f);
1267 f->target[je32_to_cpu(latest_node->csize)] = '\0';
1268 dbg_readinode("symlink's target '%s' cached\n", f->target);
1271 /* fall through... */
1275 /* Certain inode types should have only one data node, and it's
1276 kept as the metadata node */
1278 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o had metadata node\n",
1279 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1281 jffs2_do_clear_inode(c, f);
1284 if (!frag_first(&f->fragtree)) {
1285 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o has no fragments\n",
1286 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1288 jffs2_do_clear_inode(c, f);
1291 /* ASSERT: f->fraglist != NULL */
1292 if (frag_next(frag_first(&f->fragtree))) {
1293 JFFS2_ERROR("Argh. Special inode #%u with mode 0x%x had more than one node\n",
1294 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1295 /* FIXME: Deal with it - check crc32, check for duplicate node, check times and discard the older one */
1297 jffs2_do_clear_inode(c, f);
1300 /* OK. We're happy */
1301 f->metadata = frag_first(&f->fragtree)->node;
1302 jffs2_free_node_frag(frag_first(&f->fragtree));
1303 f->fragtree = RB_ROOT;
1306 if (f->inocache->state == INO_STATE_READING)
1307 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1312 /* Scan the list of all nodes present for this ino, build map of versions, etc. */
1313 int jffs2_do_read_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
1314 uint32_t ino, struct jffs2_raw_inode *latest_node)
1316 dbg_readinode("read inode #%u\n", ino);
1319 spin_lock(&c->inocache_lock);
1320 f->inocache = jffs2_get_ino_cache(c, ino);
1323 /* Check its state. We may need to wait before we can use it */
1324 switch(f->inocache->state) {
1325 case INO_STATE_UNCHECKED:
1326 case INO_STATE_CHECKEDABSENT:
1327 f->inocache->state = INO_STATE_READING;
1330 case INO_STATE_CHECKING:
1332 /* If it's in either of these states, we need
1333 to wait for whoever's got it to finish and
1335 dbg_readinode("waiting for ino #%u in state %d\n", ino, f->inocache->state);
1336 sleep_on_spinunlock(&c->inocache_wq, &c->inocache_lock);
1337 goto retry_inocache;
1339 case INO_STATE_READING:
1340 case INO_STATE_PRESENT:
1341 /* Eep. This should never happen. It can
1342 happen if Linux calls read_inode() again
1343 before clear_inode() has finished though. */
1344 JFFS2_ERROR("Eep. Trying to read_inode #%u when it's already in state %d!\n", ino, f->inocache->state);
1345 /* Fail. That's probably better than allowing it to succeed */
1353 spin_unlock(&c->inocache_lock);
1355 if (!f->inocache && ino == 1) {
1356 /* Special case - no root inode on medium */
1357 f->inocache = jffs2_alloc_inode_cache();
1359 JFFS2_ERROR("cannot allocate inocache for root inode\n");
1362 dbg_readinode("creating inocache for root inode\n");
1363 memset(f->inocache, 0, sizeof(struct jffs2_inode_cache));
1364 f->inocache->ino = f->inocache->nlink = 1;
1365 f->inocache->nodes = (struct jffs2_raw_node_ref *)f->inocache;
1366 f->inocache->state = INO_STATE_READING;
1367 jffs2_add_ino_cache(c, f->inocache);
1370 JFFS2_ERROR("requestied to read an nonexistent ino %u\n", ino);
1374 return jffs2_do_read_inode_internal(c, f, latest_node);
1377 int jffs2_do_crccheck_inode(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic)
1379 struct jffs2_raw_inode n;
1380 struct jffs2_inode_info *f = kzalloc(sizeof(*f), GFP_KERNEL);
1386 init_MUTEX_LOCKED(&f->sem);
1389 ret = jffs2_do_read_inode_internal(c, f, &n);
1392 jffs2_do_clear_inode(c, f);
1398 void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
1400 struct jffs2_full_dirent *fd, *fds;
1404 jffs2_xattr_delete_inode(c, f->inocache);
1406 deleted = f->inocache && !f->inocache->nlink;
1408 if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
1409 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CLEARING);
1413 jffs2_mark_node_obsolete(c, f->metadata->raw);
1414 jffs2_free_full_dnode(f->metadata);
1417 jffs2_kill_fragtree(&f->fragtree, deleted?c:NULL);
1428 jffs2_free_full_dirent(fd);
1431 if (f->inocache && f->inocache->state != INO_STATE_CHECKING) {
1432 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1433 if (f->inocache->nodes == (void *)f->inocache)
1434 jffs2_del_ino_cache(c, f->inocache);