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 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
14 #include <linux/kernel.h>
15 #include <linux/sched.h>
16 #include <linux/slab.h>
18 #include <linux/crc32.h>
19 #include <linux/pagemap.h>
20 #include <linux/mtd/mtd.h>
21 #include <linux/compiler.h>
25 * Check the data CRC of the node.
27 * Returns: 0 if the data CRC is correct;
29 * error code if an error occurred.
31 static int check_node_data(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
33 struct jffs2_raw_node_ref *ref = tn->fn->raw;
34 int err = 0, pointed = 0;
35 struct jffs2_eraseblock *jeb;
36 unsigned char *buffer;
37 uint32_t crc, ofs, len;
40 BUG_ON(tn->csize == 0);
42 /* Calculate how many bytes were already checked */
43 ofs = ref_offset(ref) + sizeof(struct jffs2_raw_inode);
46 if (jffs2_is_writebuffered(c)) {
47 int adj = ofs % c->wbuf_pagesize;
49 adj = c->wbuf_pagesize - adj;
51 if (adj >= tn->csize) {
52 dbg_readinode("no need to check node at %#08x, data length %u, data starts at %#08x - it has already been checked.\n",
53 ref_offset(ref), tn->csize, ofs);
61 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",
62 ref_offset(ref), tn->csize, tn->partial_crc, tn->data_crc, ofs - len, ofs, len);
65 /* TODO: instead, incapsulate point() stuff to jffs2_flash_read(),
66 * adding and jffs2_flash_read_end() interface. */
67 err = mtd_point(c->mtd, ofs, len, &retlen, (void **)&buffer, NULL);
68 if (!err && retlen < len) {
69 JFFS2_WARNING("MTD point returned len too short: %zu instead of %u.\n", retlen, tn->csize);
70 mtd_unpoint(c->mtd, ofs, retlen);
72 if (err != -EOPNOTSUPP)
73 JFFS2_WARNING("MTD point failed: error code %d.\n", err);
75 pointed = 1; /* succefully pointed to device */
79 buffer = kmalloc(len, GFP_KERNEL);
80 if (unlikely(!buffer))
83 /* TODO: this is very frequent pattern, make it a separate
85 err = jffs2_flash_read(c, ofs, len, &retlen, buffer);
87 JFFS2_ERROR("can not read %d bytes from 0x%08x, error code: %d.\n", len, ofs, err);
92 JFFS2_ERROR("short read at %#08x: %zd instead of %d.\n", ofs, retlen, len);
98 /* Continue calculating CRC */
99 crc = crc32(tn->partial_crc, buffer, len);
104 mtd_unpoint(c->mtd, ofs, len);
107 if (crc != tn->data_crc) {
108 JFFS2_NOTICE("wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x.\n",
109 ref_offset(ref), tn->data_crc, crc);
114 jeb = &c->blocks[ref->flash_offset / c->sector_size];
115 len = ref_totlen(c, jeb, ref);
116 /* If it should be REF_NORMAL, it'll get marked as such when
117 we build the fragtree, shortly. No need to worry about GC
118 moving it while it's marked REF_PRISTINE -- GC won't happen
119 till we've finished checking every inode anyway. */
120 ref->flash_offset |= REF_PRISTINE;
122 * Mark the node as having been checked and fix the
123 * accounting accordingly.
125 spin_lock(&c->erase_completion_lock);
126 jeb->used_size += len;
127 jeb->unchecked_size -= len;
129 c->unchecked_size -= len;
130 jffs2_dbg_acct_paranoia_check_nolock(c, jeb);
131 spin_unlock(&c->erase_completion_lock);
140 mtd_unpoint(c->mtd, ofs, len);
146 * Helper function for jffs2_add_older_frag_to_fragtree().
148 * Checks the node if we are in the checking stage.
150 static int check_tn_node(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
154 BUG_ON(ref_obsolete(tn->fn->raw));
156 /* We only check the data CRC of unchecked nodes */
157 if (ref_flags(tn->fn->raw) != REF_UNCHECKED)
160 dbg_readinode("check node %#04x-%#04x, phys offs %#08x\n",
161 tn->fn->ofs, tn->fn->ofs + tn->fn->size, ref_offset(tn->fn->raw));
163 ret = check_node_data(c, tn);
164 if (unlikely(ret < 0)) {
165 JFFS2_ERROR("check_node_data() returned error: %d.\n",
167 } else if (unlikely(ret > 0)) {
168 dbg_readinode("CRC error, mark it obsolete.\n");
169 jffs2_mark_node_obsolete(c, tn->fn->raw);
175 static struct jffs2_tmp_dnode_info *jffs2_lookup_tn(struct rb_root *tn_root, uint32_t offset)
177 struct rb_node *next;
178 struct jffs2_tmp_dnode_info *tn = NULL;
180 dbg_readinode("root %p, offset %d\n", tn_root, offset);
182 next = tn_root->rb_node;
185 tn = rb_entry(next, struct jffs2_tmp_dnode_info, rb);
187 if (tn->fn->ofs < offset)
188 next = tn->rb.rb_right;
189 else if (tn->fn->ofs >= offset)
190 next = tn->rb.rb_left;
199 static void jffs2_kill_tn(struct jffs2_sb_info *c, struct jffs2_tmp_dnode_info *tn)
201 jffs2_mark_node_obsolete(c, tn->fn->raw);
202 jffs2_free_full_dnode(tn->fn);
203 jffs2_free_tmp_dnode_info(tn);
206 * This function is used when we read an inode. Data nodes arrive in
207 * arbitrary order -- they may be older or newer than the nodes which
208 * are already in the tree. Where overlaps occur, the older node can
209 * be discarded as long as the newer passes the CRC check. We don't
210 * bother to keep track of holes in this rbtree, and neither do we deal
211 * with frags -- we can have multiple entries starting at the same
212 * offset, and the one with the smallest length will come first in the
215 * Returns 0 if the node was handled (including marking it obsolete)
216 * < 0 an if error occurred
218 static int jffs2_add_tn_to_tree(struct jffs2_sb_info *c,
219 struct jffs2_readinode_info *rii,
220 struct jffs2_tmp_dnode_info *tn)
222 uint32_t fn_end = tn->fn->ofs + tn->fn->size;
223 struct jffs2_tmp_dnode_info *this, *ptn;
225 dbg_readinode("insert fragment %#04x-%#04x, ver %u at %08x\n", tn->fn->ofs, fn_end, tn->version, ref_offset(tn->fn->raw));
227 /* If a node has zero dsize, we only have to keep if it if it might be the
228 node with highest version -- i.e. the one which will end up as f->metadata.
229 Note that such nodes won't be REF_UNCHECKED since there are no data to
233 if (rii->mdata_tn->version < tn->version) {
234 /* We had a candidate mdata node already */
235 dbg_readinode("kill old mdata with ver %d\n", rii->mdata_tn->version);
236 jffs2_kill_tn(c, rii->mdata_tn);
238 dbg_readinode("kill new mdata with ver %d (older than existing %d\n",
239 tn->version, rii->mdata_tn->version);
240 jffs2_kill_tn(c, tn);
245 dbg_readinode("keep new mdata with ver %d\n", tn->version);
249 /* Find the earliest node which _may_ be relevant to this one */
250 this = jffs2_lookup_tn(&rii->tn_root, tn->fn->ofs);
252 /* If the node is coincident with another at a lower address,
253 back up until the other node is found. It may be relevant */
254 while (this->overlapped) {
258 * We killed a node which set the overlapped
259 * flags during the scan. Fix it up.
261 this->overlapped = 0;
266 dbg_readinode("'this' found %#04x-%#04x (%s)\n", this->fn->ofs, this->fn->ofs + this->fn->size, this->fn ? "data" : "hole");
270 if (this->fn->ofs > fn_end)
272 dbg_readinode("Ponder this ver %d, 0x%x-0x%x\n",
273 this->version, this->fn->ofs, this->fn->size);
275 if (this->version == tn->version) {
276 /* Version number collision means REF_PRISTINE GC. Accept either of them
277 as long as the CRC is correct. Check the one we have already... */
278 if (!check_tn_node(c, this)) {
279 /* The one we already had was OK. Keep it and throw away the new one */
280 dbg_readinode("Like old node. Throw away new\n");
281 jffs2_kill_tn(c, tn);
284 /* Who cares if the new one is good; keep it for now anyway. */
285 dbg_readinode("Like new node. Throw away old\n");
286 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
287 jffs2_kill_tn(c, this);
288 /* Same overlapping from in front and behind */
292 if (this->version < tn->version &&
293 this->fn->ofs >= tn->fn->ofs &&
294 this->fn->ofs + this->fn->size <= fn_end) {
295 /* New node entirely overlaps 'this' */
296 if (check_tn_node(c, tn)) {
297 dbg_readinode("new node bad CRC\n");
298 jffs2_kill_tn(c, tn);
301 /* ... and is good. Kill 'this' and any subsequent nodes which are also overlapped */
302 while (this && this->fn->ofs + this->fn->size <= fn_end) {
303 struct jffs2_tmp_dnode_info *next = tn_next(this);
304 if (this->version < tn->version) {
305 tn_erase(this, &rii->tn_root);
306 dbg_readinode("Kill overlapped ver %d, 0x%x-0x%x\n",
307 this->version, this->fn->ofs,
308 this->fn->ofs+this->fn->size);
309 jffs2_kill_tn(c, this);
313 dbg_readinode("Done killing overlapped nodes\n");
316 if (this->version > tn->version &&
317 this->fn->ofs <= tn->fn->ofs &&
318 this->fn->ofs+this->fn->size >= fn_end) {
319 /* New node entirely overlapped by 'this' */
320 if (!check_tn_node(c, this)) {
321 dbg_readinode("Good CRC on old node. Kill new\n");
322 jffs2_kill_tn(c, tn);
325 /* ... but 'this' was bad. Replace it... */
326 dbg_readinode("Bad CRC on old overlapping node. Kill it\n");
327 tn_erase(this, &rii->tn_root);
328 jffs2_kill_tn(c, this);
332 this = tn_next(this);
335 /* We neither completely obsoleted nor were completely
336 obsoleted by an earlier node. Insert into the tree */
338 struct rb_node *parent;
339 struct rb_node **link = &rii->tn_root.rb_node;
340 struct jffs2_tmp_dnode_info *insert_point = NULL;
344 insert_point = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
345 if (tn->fn->ofs > insert_point->fn->ofs)
346 link = &insert_point->rb.rb_right;
347 else if (tn->fn->ofs < insert_point->fn->ofs ||
348 tn->fn->size < insert_point->fn->size)
349 link = &insert_point->rb.rb_left;
351 link = &insert_point->rb.rb_right;
353 rb_link_node(&tn->rb, &insert_point->rb, link);
354 rb_insert_color(&tn->rb, &rii->tn_root);
357 /* If there's anything behind that overlaps us, note it */
361 if (this->fn->ofs + this->fn->size > tn->fn->ofs) {
362 dbg_readinode("Node is overlapped by %p (v %d, 0x%x-0x%x)\n",
363 this, this->version, this->fn->ofs,
364 this->fn->ofs+this->fn->size);
368 if (!this->overlapped)
374 * We killed a node which set the overlapped
375 * flags during the scan. Fix it up.
377 this->overlapped = 0;
384 /* If the new node overlaps anything ahead, note it */
386 while (this && this->fn->ofs < fn_end) {
387 this->overlapped = 1;
388 dbg_readinode("Node ver %d, 0x%x-0x%x is overlapped\n",
389 this->version, this->fn->ofs,
390 this->fn->ofs+this->fn->size);
391 this = tn_next(this);
396 /* Trivial function to remove the last node in the tree. Which by definition
397 has no right-hand child — so can be removed just by making its left-hand
398 child (if any) take its place under its parent. Since this is only done
399 when we're consuming the whole tree, there's no need to use rb_erase()
400 and let it worry about adjusting colours and balancing the tree. That
401 would just be a waste of time. */
402 static void eat_last(struct rb_root *root, struct rb_node *node)
404 struct rb_node *parent = rb_parent(node);
405 struct rb_node **link;
408 BUG_ON(node->rb_right);
411 link = &root->rb_node;
412 else if (node == parent->rb_left)
413 link = &parent->rb_left;
415 link = &parent->rb_right;
417 *link = node->rb_left;
419 node->rb_left->__rb_parent_color = node->__rb_parent_color;
422 /* We put the version tree in reverse order, so we can use the same eat_last()
423 function that we use to consume the tmpnode tree (tn_root). */
424 static void ver_insert(struct rb_root *ver_root, struct jffs2_tmp_dnode_info *tn)
426 struct rb_node **link = &ver_root->rb_node;
427 struct rb_node *parent = NULL;
428 struct jffs2_tmp_dnode_info *this_tn;
432 this_tn = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
434 if (tn->version > this_tn->version)
435 link = &parent->rb_left;
437 link = &parent->rb_right;
439 dbg_readinode("Link new node at %p (root is %p)\n", link, ver_root);
440 rb_link_node(&tn->rb, parent, link);
441 rb_insert_color(&tn->rb, ver_root);
444 /* Build final, normal fragtree from tn tree. It doesn't matter which order
445 we add nodes to the real fragtree, as long as they don't overlap. And
446 having thrown away the majority of overlapped nodes as we went, there
447 really shouldn't be many sets of nodes which do overlap. If we start at
448 the end, we can use the overlap markers -- we can just eat nodes which
449 aren't overlapped, and when we encounter nodes which _do_ overlap we
450 sort them all into a temporary tree in version order before replaying them. */
451 static int jffs2_build_inode_fragtree(struct jffs2_sb_info *c,
452 struct jffs2_inode_info *f,
453 struct jffs2_readinode_info *rii)
455 struct jffs2_tmp_dnode_info *pen, *last, *this;
456 struct rb_root ver_root = RB_ROOT;
457 uint32_t high_ver = 0;
460 dbg_readinode("potential mdata is ver %d at %p\n", rii->mdata_tn->version, rii->mdata_tn);
461 high_ver = rii->mdata_tn->version;
462 rii->latest_ref = rii->mdata_tn->fn->raw;
464 #ifdef JFFS2_DBG_READINODE_MESSAGES
465 this = tn_last(&rii->tn_root);
467 dbg_readinode("tn %p ver %d range 0x%x-0x%x ov %d\n", this, this->version, this->fn->ofs,
468 this->fn->ofs+this->fn->size, this->overlapped);
469 this = tn_prev(this);
472 pen = tn_last(&rii->tn_root);
473 while ((last = pen)) {
476 eat_last(&rii->tn_root, &last->rb);
477 ver_insert(&ver_root, last);
479 if (unlikely(last->overlapped)) {
483 * We killed a node which set the overlapped
484 * flags during the scan. Fix it up.
486 last->overlapped = 0;
489 /* Now we have a bunch of nodes in reverse version
490 order, in the tree at ver_root. Most of the time,
491 there'll actually be only one node in the 'tree',
493 this = tn_last(&ver_root);
496 struct jffs2_tmp_dnode_info *vers_next;
498 vers_next = tn_prev(this);
499 eat_last(&ver_root, &this->rb);
500 if (check_tn_node(c, this)) {
501 dbg_readinode("node ver %d, 0x%x-0x%x failed CRC\n",
502 this->version, this->fn->ofs,
503 this->fn->ofs+this->fn->size);
504 jffs2_kill_tn(c, this);
506 if (this->version > high_ver) {
507 /* Note that this is different from the other
508 highest_version, because this one is only
509 counting _valid_ nodes which could give the
510 latest inode metadata */
511 high_ver = this->version;
512 rii->latest_ref = this->fn->raw;
514 dbg_readinode("Add %p (v %d, 0x%x-0x%x, ov %d) to fragtree\n",
515 this, this->version, this->fn->ofs,
516 this->fn->ofs+this->fn->size, this->overlapped);
518 ret = jffs2_add_full_dnode_to_inode(c, f, this->fn);
520 /* Free the nodes in vers_root; let the caller
521 deal with the rest */
522 JFFS2_ERROR("Add node to tree failed %d\n", ret);
524 vers_next = tn_prev(this);
525 if (check_tn_node(c, this))
526 jffs2_mark_node_obsolete(c, this->fn->raw);
527 jffs2_free_full_dnode(this->fn);
528 jffs2_free_tmp_dnode_info(this);
532 eat_last(&ver_root, &vers_next->rb);
536 jffs2_free_tmp_dnode_info(this);
544 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
546 struct rb_node *this;
547 struct jffs2_tmp_dnode_info *tn;
549 this = list->rb_node;
551 /* Now at bottom of tree */
554 this = this->rb_left;
555 else if (this->rb_right)
556 this = this->rb_right;
558 tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
559 jffs2_free_full_dnode(tn->fn);
560 jffs2_free_tmp_dnode_info(tn);
562 this = rb_parent(this);
566 if (this->rb_left == &tn->rb)
567 this->rb_left = NULL;
568 else if (this->rb_right == &tn->rb)
569 this->rb_right = NULL;
576 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
578 struct jffs2_full_dirent *next;
582 jffs2_free_full_dirent(fd);
587 /* Returns first valid node after 'ref'. May return 'ref' */
588 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
590 while (ref && ref->next_in_ino) {
591 if (!ref_obsolete(ref))
593 dbg_noderef("node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref));
594 ref = ref->next_in_ino;
600 * Helper function for jffs2_get_inode_nodes().
601 * It is called every time an directory entry node is found.
603 * Returns: 0 on success;
604 * negative error code on failure.
606 static inline int read_direntry(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
607 struct jffs2_raw_dirent *rd, size_t read,
608 struct jffs2_readinode_info *rii)
610 struct jffs2_full_dirent *fd;
613 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
614 BUG_ON(ref_obsolete(ref));
616 crc = crc32(0, rd, sizeof(*rd) - 8);
617 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
618 JFFS2_NOTICE("header CRC failed on dirent node at %#08x: read %#08x, calculated %#08x\n",
619 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
620 jffs2_mark_node_obsolete(c, ref);
624 /* If we've never checked the CRCs on this node, check them now */
625 if (ref_flags(ref) == REF_UNCHECKED) {
626 struct jffs2_eraseblock *jeb;
630 if (unlikely(PAD((rd->nsize + sizeof(*rd))) != PAD(je32_to_cpu(rd->totlen)))) {
631 JFFS2_ERROR("illegal nsize in node at %#08x: nsize %#02x, totlen %#04x\n",
632 ref_offset(ref), rd->nsize, je32_to_cpu(rd->totlen));
633 jffs2_mark_node_obsolete(c, ref);
637 jeb = &c->blocks[ref->flash_offset / c->sector_size];
638 len = ref_totlen(c, jeb, ref);
640 spin_lock(&c->erase_completion_lock);
641 jeb->used_size += len;
642 jeb->unchecked_size -= len;
644 c->unchecked_size -= len;
645 ref->flash_offset = ref_offset(ref) | dirent_node_state(rd);
646 spin_unlock(&c->erase_completion_lock);
649 fd = jffs2_alloc_full_dirent(rd->nsize + 1);
654 fd->version = je32_to_cpu(rd->version);
655 fd->ino = je32_to_cpu(rd->ino);
658 if (fd->version > rii->highest_version)
659 rii->highest_version = fd->version;
661 /* Pick out the mctime of the latest dirent */
662 if(fd->version > rii->mctime_ver && je32_to_cpu(rd->mctime)) {
663 rii->mctime_ver = fd->version;
664 rii->latest_mctime = je32_to_cpu(rd->mctime);
668 * Copy as much of the name as possible from the raw
669 * dirent we've already read from the flash.
671 if (read > sizeof(*rd))
672 memcpy(&fd->name[0], &rd->name[0],
673 min_t(uint32_t, rd->nsize, (read - sizeof(*rd)) ));
675 /* Do we need to copy any more of the name directly from the flash? */
676 if (rd->nsize + sizeof(*rd) > read) {
679 int already = read - sizeof(*rd);
681 err = jffs2_flash_read(c, (ref_offset(ref)) + read,
682 rd->nsize - already, &read, &fd->name[already]);
683 if (unlikely(read != rd->nsize - already) && likely(!err))
687 JFFS2_ERROR("read remainder of name: error %d\n", err);
688 jffs2_free_full_dirent(fd);
693 fd->nhash = full_name_hash(fd->name, rd->nsize);
695 fd->name[rd->nsize] = '\0';
698 * Wheee. We now have a complete jffs2_full_dirent structure, with
699 * the name in it and everything. Link it into the list
701 jffs2_add_fd_to_list(c, fd, &rii->fds);
707 * Helper function for jffs2_get_inode_nodes().
708 * It is called every time an inode node is found.
710 * Returns: 0 on success (possibly after marking a bad node obsolete);
711 * negative error code on failure.
713 static inline int read_dnode(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
714 struct jffs2_raw_inode *rd, int rdlen,
715 struct jffs2_readinode_info *rii)
717 struct jffs2_tmp_dnode_info *tn;
722 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
723 BUG_ON(ref_obsolete(ref));
725 crc = crc32(0, rd, sizeof(*rd) - 8);
726 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
727 JFFS2_NOTICE("node CRC failed on dnode at %#08x: read %#08x, calculated %#08x\n",
728 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
729 jffs2_mark_node_obsolete(c, ref);
733 tn = jffs2_alloc_tmp_dnode_info();
735 JFFS2_ERROR("failed to allocate tn (%zu bytes).\n", sizeof(*tn));
740 csize = je32_to_cpu(rd->csize);
742 /* If we've never checked the CRCs on this node, check them now */
743 if (ref_flags(ref) == REF_UNCHECKED) {
746 if (unlikely(je32_to_cpu(rd->offset) > je32_to_cpu(rd->isize)) ||
747 unlikely(PAD(je32_to_cpu(rd->csize) + sizeof(*rd)) != PAD(je32_to_cpu(rd->totlen)))) {
748 JFFS2_WARNING("inode node header CRC is corrupted at %#08x\n", ref_offset(ref));
749 jffs2_dbg_dump_node(c, ref_offset(ref));
750 jffs2_mark_node_obsolete(c, ref);
754 if (jffs2_is_writebuffered(c) && csize != 0) {
755 /* At this point we are supposed to check the data CRC
756 * of our unchecked node. But thus far, we do not
757 * know whether the node is valid or obsolete. To
758 * figure this out, we need to walk all the nodes of
759 * the inode and build the inode fragtree. We don't
760 * want to spend time checking data of nodes which may
761 * later be found to be obsolete. So we put off the full
762 * data CRC checking until we have read all the inode
763 * nodes and have started building the fragtree.
765 * The fragtree is being built starting with nodes
766 * having the highest version number, so we'll be able
767 * to detect whether a node is valid (i.e., it is not
768 * overlapped by a node with higher version) or not.
769 * And we'll be able to check only those nodes, which
772 * Of course, this optimization only makes sense in case
773 * of NAND flashes (or other flashes with
774 * !jffs2_can_mark_obsolete()), since on NOR flashes
775 * nodes are marked obsolete physically.
777 * Since NAND flashes (or other flashes with
778 * jffs2_is_writebuffered(c)) are anyway read by
779 * fractions of c->wbuf_pagesize, and we have just read
780 * the node header, it is likely that the starting part
781 * of the node data is also read when we read the
782 * header. So we don't mind to check the CRC of the
783 * starting part of the data of the node now, and check
784 * the second part later (in jffs2_check_node_data()).
785 * Of course, we will not need to re-read and re-check
786 * the NAND page which we have just read. This is why we
787 * read the whole NAND page at jffs2_get_inode_nodes(),
788 * while we needed only the node header.
792 /* 'buf' will point to the start of data */
793 buf = (unsigned char *)rd + sizeof(*rd);
794 /* len will be the read data length */
795 len = min_t(uint32_t, rdlen - sizeof(*rd), csize);
796 tn->partial_crc = crc32(0, buf, len);
798 dbg_readinode("Calculates CRC (%#08x) for %d bytes, csize %d\n", tn->partial_crc, len, csize);
800 /* If we actually calculated the whole data CRC
801 * and it is wrong, drop the node. */
802 if (len >= csize && unlikely(tn->partial_crc != je32_to_cpu(rd->data_crc))) {
803 JFFS2_NOTICE("wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x.\n",
804 ref_offset(ref), tn->partial_crc, je32_to_cpu(rd->data_crc));
805 jffs2_mark_node_obsolete(c, ref);
809 } else if (csize == 0) {
811 * We checked the header CRC. If the node has no data, adjust
812 * the space accounting now. For other nodes this will be done
813 * later either when the node is marked obsolete or when its
816 struct jffs2_eraseblock *jeb;
818 dbg_readinode("the node has no data.\n");
819 jeb = &c->blocks[ref->flash_offset / c->sector_size];
820 len = ref_totlen(c, jeb, ref);
822 spin_lock(&c->erase_completion_lock);
823 jeb->used_size += len;
824 jeb->unchecked_size -= len;
826 c->unchecked_size -= len;
827 ref->flash_offset = ref_offset(ref) | REF_NORMAL;
828 spin_unlock(&c->erase_completion_lock);
832 tn->fn = jffs2_alloc_full_dnode();
834 JFFS2_ERROR("alloc fn failed\n");
839 tn->version = je32_to_cpu(rd->version);
840 tn->fn->ofs = je32_to_cpu(rd->offset);
841 tn->data_crc = je32_to_cpu(rd->data_crc);
846 if (tn->version > rii->highest_version)
847 rii->highest_version = tn->version;
849 /* There was a bug where we wrote hole nodes out with
850 csize/dsize swapped. Deal with it */
851 if (rd->compr == JFFS2_COMPR_ZERO && !je32_to_cpu(rd->dsize) && csize)
852 tn->fn->size = csize;
853 else // normal case...
854 tn->fn->size = je32_to_cpu(rd->dsize);
856 dbg_readinode2("dnode @%08x: ver %u, offset %#04x, dsize %#04x, csize %#04x\n",
857 ref_offset(ref), je32_to_cpu(rd->version),
858 je32_to_cpu(rd->offset), je32_to_cpu(rd->dsize), csize);
860 ret = jffs2_add_tn_to_tree(c, rii, tn);
863 jffs2_free_full_dnode(tn->fn);
865 jffs2_free_tmp_dnode_info(tn);
868 #ifdef JFFS2_DBG_READINODE2_MESSAGES
869 dbg_readinode2("After adding ver %d:\n", je32_to_cpu(rd->version));
870 tn = tn_first(&rii->tn_root);
872 dbg_readinode2("%p: v %d r 0x%x-0x%x ov %d\n",
873 tn, tn->version, tn->fn->ofs,
874 tn->fn->ofs+tn->fn->size, tn->overlapped);
882 * Helper function for jffs2_get_inode_nodes().
883 * It is called every time an unknown node is found.
885 * Returns: 0 on success;
886 * negative error code on failure.
888 static inline int read_unknown(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref, struct jffs2_unknown_node *un)
890 /* We don't mark unknown nodes as REF_UNCHECKED */
891 if (ref_flags(ref) == REF_UNCHECKED) {
892 JFFS2_ERROR("REF_UNCHECKED but unknown node at %#08x\n",
894 JFFS2_ERROR("Node is {%04x,%04x,%08x,%08x}. Please report this error.\n",
895 je16_to_cpu(un->magic), je16_to_cpu(un->nodetype),
896 je32_to_cpu(un->totlen), je32_to_cpu(un->hdr_crc));
897 jffs2_mark_node_obsolete(c, ref);
901 un->nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(un->nodetype));
903 switch(je16_to_cpu(un->nodetype) & JFFS2_COMPAT_MASK) {
905 case JFFS2_FEATURE_INCOMPAT:
906 JFFS2_ERROR("unknown INCOMPAT nodetype %#04X at %#08x\n",
907 je16_to_cpu(un->nodetype), ref_offset(ref));
912 case JFFS2_FEATURE_ROCOMPAT:
913 JFFS2_ERROR("unknown ROCOMPAT nodetype %#04X at %#08x\n",
914 je16_to_cpu(un->nodetype), ref_offset(ref));
915 BUG_ON(!(c->flags & JFFS2_SB_FLAG_RO));
918 case JFFS2_FEATURE_RWCOMPAT_COPY:
919 JFFS2_NOTICE("unknown RWCOMPAT_COPY nodetype %#04X at %#08x\n",
920 je16_to_cpu(un->nodetype), ref_offset(ref));
923 case JFFS2_FEATURE_RWCOMPAT_DELETE:
924 JFFS2_NOTICE("unknown RWCOMPAT_DELETE nodetype %#04X at %#08x\n",
925 je16_to_cpu(un->nodetype), ref_offset(ref));
926 jffs2_mark_node_obsolete(c, ref);
934 * Helper function for jffs2_get_inode_nodes().
935 * The function detects whether more data should be read and reads it if yes.
937 * Returns: 0 on success;
938 * negative error code on failure.
940 static int read_more(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
941 int needed_len, int *rdlen, unsigned char *buf)
943 int err, to_read = needed_len - *rdlen;
947 if (jffs2_is_writebuffered(c)) {
948 int rem = to_read % c->wbuf_pagesize;
951 to_read += c->wbuf_pagesize - rem;
954 /* We need to read more data */
955 offs = ref_offset(ref) + *rdlen;
957 dbg_readinode("read more %d bytes\n", to_read);
959 err = jffs2_flash_read(c, offs, to_read, &retlen, buf + *rdlen);
961 JFFS2_ERROR("can not read %d bytes from 0x%08x, "
962 "error code: %d.\n", to_read, offs, err);
966 if (retlen < to_read) {
967 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n",
968 offs, retlen, to_read);
976 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
977 with this ino. Perform a preliminary ordering on data nodes, throwing away
978 those which are completely obsoleted by newer ones. The naïve approach we
979 use to take of just returning them _all_ in version order will cause us to
980 run out of memory in certain degenerate cases. */
981 static int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
982 struct jffs2_readinode_info *rii)
984 struct jffs2_raw_node_ref *ref, *valid_ref;
985 unsigned char *buf = NULL;
986 union jffs2_node_union *node;
992 dbg_readinode("ino #%u\n", f->inocache->ino);
994 /* FIXME: in case of NOR and available ->point() this
995 * needs to be fixed. */
996 len = sizeof(union jffs2_node_union) + c->wbuf_pagesize;
997 buf = kmalloc(len, GFP_KERNEL);
1001 spin_lock(&c->erase_completion_lock);
1002 valid_ref = jffs2_first_valid_node(f->inocache->nodes);
1003 if (!valid_ref && f->inocache->ino != 1)
1004 JFFS2_WARNING("Eep. No valid nodes for ino #%u.\n", f->inocache->ino);
1006 /* We can hold a pointer to a non-obsolete node without the spinlock,
1007 but _obsolete_ nodes may disappear at any time, if the block
1008 they're in gets erased. So if we mark 'ref' obsolete while we're
1009 not holding the lock, it can go away immediately. For that reason,
1010 we find the next valid node first, before processing 'ref'.
1013 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
1014 spin_unlock(&c->erase_completion_lock);
1019 * At this point we don't know the type of the node we're going
1020 * to read, so we do not know the size of its header. In order
1021 * to minimize the amount of flash IO we assume the header is
1022 * of size = JFFS2_MIN_NODE_HEADER.
1024 len = JFFS2_MIN_NODE_HEADER;
1025 if (jffs2_is_writebuffered(c)) {
1029 * We are about to read JFFS2_MIN_NODE_HEADER bytes,
1030 * but this flash has some minimal I/O unit. It is
1031 * possible that we'll need to read more soon, so read
1032 * up to the next min. I/O unit, in order not to
1033 * re-read the same min. I/O unit twice.
1035 end = ref_offset(ref) + len;
1036 rem = end % c->wbuf_pagesize;
1038 end += c->wbuf_pagesize - rem;
1039 len = end - ref_offset(ref);
1042 dbg_readinode("read %d bytes at %#08x(%d).\n", len, ref_offset(ref), ref_flags(ref));
1044 /* FIXME: point() */
1045 err = jffs2_flash_read(c, ref_offset(ref), len, &retlen, buf);
1047 JFFS2_ERROR("can not read %d bytes from 0x%08x, error code: %d.\n", len, ref_offset(ref), err);
1052 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n", ref_offset(ref), retlen, len);
1057 node = (union jffs2_node_union *)buf;
1059 /* No need to mask in the valid bit; it shouldn't be invalid */
1060 if (je32_to_cpu(node->u.hdr_crc) != crc32(0, node, sizeof(node->u)-4)) {
1061 JFFS2_NOTICE("Node header CRC failed at %#08x. {%04x,%04x,%08x,%08x}\n",
1062 ref_offset(ref), je16_to_cpu(node->u.magic),
1063 je16_to_cpu(node->u.nodetype),
1064 je32_to_cpu(node->u.totlen),
1065 je32_to_cpu(node->u.hdr_crc));
1066 jffs2_dbg_dump_node(c, ref_offset(ref));
1067 jffs2_mark_node_obsolete(c, ref);
1070 if (je16_to_cpu(node->u.magic) != JFFS2_MAGIC_BITMASK) {
1071 /* Not a JFFS2 node, whinge and move on */
1072 JFFS2_NOTICE("Wrong magic bitmask 0x%04x in node header at %#08x.\n",
1073 je16_to_cpu(node->u.magic), ref_offset(ref));
1074 jffs2_mark_node_obsolete(c, ref);
1078 switch (je16_to_cpu(node->u.nodetype)) {
1080 case JFFS2_NODETYPE_DIRENT:
1082 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_dirent) &&
1083 len < sizeof(struct jffs2_raw_dirent)) {
1084 err = read_more(c, ref, sizeof(struct jffs2_raw_dirent), &len, buf);
1089 err = read_direntry(c, ref, &node->d, retlen, rii);
1095 case JFFS2_NODETYPE_INODE:
1097 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_inode) &&
1098 len < sizeof(struct jffs2_raw_inode)) {
1099 err = read_more(c, ref, sizeof(struct jffs2_raw_inode), &len, buf);
1104 err = read_dnode(c, ref, &node->i, len, rii);
1111 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_unknown_node) &&
1112 len < sizeof(struct jffs2_unknown_node)) {
1113 err = read_more(c, ref, sizeof(struct jffs2_unknown_node), &len, buf);
1118 err = read_unknown(c, ref, &node->u);
1124 spin_lock(&c->erase_completion_lock);
1127 spin_unlock(&c->erase_completion_lock);
1130 f->highest_version = rii->highest_version;
1132 dbg_readinode("nodes of inode #%u were read, the highest version is %u, latest_mctime %u, mctime_ver %u.\n",
1133 f->inocache->ino, rii->highest_version, rii->latest_mctime,
1138 jffs2_free_tmp_dnode_info_list(&rii->tn_root);
1139 jffs2_free_full_dirent_list(rii->fds);
1145 static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
1146 struct jffs2_inode_info *f,
1147 struct jffs2_raw_inode *latest_node)
1149 struct jffs2_readinode_info rii;
1150 uint32_t crc, new_size;
1154 dbg_readinode("ino #%u pino/nlink is %d\n", f->inocache->ino,
1155 f->inocache->pino_nlink);
1157 memset(&rii, 0, sizeof(rii));
1159 /* Grab all nodes relevant to this ino */
1160 ret = jffs2_get_inode_nodes(c, f, &rii);
1163 JFFS2_ERROR("cannot read nodes for ino %u, returned error is %d\n", f->inocache->ino, ret);
1164 if (f->inocache->state == INO_STATE_READING)
1165 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1169 ret = jffs2_build_inode_fragtree(c, f, &rii);
1171 JFFS2_ERROR("Failed to build final fragtree for inode #%u: error %d\n",
1172 f->inocache->ino, ret);
1173 if (f->inocache->state == INO_STATE_READING)
1174 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1175 jffs2_free_tmp_dnode_info_list(&rii.tn_root);
1176 /* FIXME: We could at least crc-check them all */
1178 jffs2_free_full_dnode(rii.mdata_tn->fn);
1179 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1180 rii.mdata_tn = NULL;
1186 if (rii.mdata_tn->fn->raw == rii.latest_ref) {
1187 f->metadata = rii.mdata_tn->fn;
1188 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1190 jffs2_kill_tn(c, rii.mdata_tn);
1192 rii.mdata_tn = NULL;
1197 jffs2_dbg_fragtree_paranoia_check_nolock(f);
1199 if (unlikely(!rii.latest_ref)) {
1200 /* No data nodes for this inode. */
1201 if (f->inocache->ino != 1) {
1202 JFFS2_WARNING("no data nodes found for ino #%u\n", f->inocache->ino);
1204 if (f->inocache->state == INO_STATE_READING)
1205 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1208 JFFS2_NOTICE("but it has children so we fake some modes for it\n");
1210 latest_node->mode = cpu_to_jemode(S_IFDIR|S_IRUGO|S_IWUSR|S_IXUGO);
1211 latest_node->version = cpu_to_je32(0);
1212 latest_node->atime = latest_node->ctime = latest_node->mtime = cpu_to_je32(0);
1213 latest_node->isize = cpu_to_je32(0);
1214 latest_node->gid = cpu_to_je16(0);
1215 latest_node->uid = cpu_to_je16(0);
1216 if (f->inocache->state == INO_STATE_READING)
1217 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1221 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref), sizeof(*latest_node), &retlen, (void *)latest_node);
1222 if (ret || retlen != sizeof(*latest_node)) {
1223 JFFS2_ERROR("failed to read from flash: error %d, %zd of %zd bytes read\n",
1224 ret, retlen, sizeof(*latest_node));
1225 /* FIXME: If this fails, there seems to be a memory leak. Find it. */
1226 mutex_unlock(&f->sem);
1227 jffs2_do_clear_inode(c, f);
1228 return ret?ret:-EIO;
1231 crc = crc32(0, latest_node, sizeof(*latest_node)-8);
1232 if (crc != je32_to_cpu(latest_node->node_crc)) {
1233 JFFS2_ERROR("CRC failed for read_inode of inode %u at physical location 0x%x\n",
1234 f->inocache->ino, ref_offset(rii.latest_ref));
1235 mutex_unlock(&f->sem);
1236 jffs2_do_clear_inode(c, f);
1240 switch(jemode_to_cpu(latest_node->mode) & S_IFMT) {
1242 if (rii.mctime_ver > je32_to_cpu(latest_node->version)) {
1243 /* The times in the latest_node are actually older than
1244 mctime in the latest dirent. Cheat. */
1245 latest_node->ctime = latest_node->mtime = cpu_to_je32(rii.latest_mctime);
1251 /* If it was a regular file, truncate it to the latest node's isize */
1252 new_size = jffs2_truncate_fragtree(c, &f->fragtree, je32_to_cpu(latest_node->isize));
1253 if (new_size != je32_to_cpu(latest_node->isize)) {
1254 JFFS2_WARNING("Truncating ino #%u to %d bytes failed because it only had %d bytes to start with!\n",
1255 f->inocache->ino, je32_to_cpu(latest_node->isize), new_size);
1256 latest_node->isize = cpu_to_je32(new_size);
1261 /* Hack to work around broken isize in old symlink code.
1262 Remove this when dwmw2 comes to his senses and stops
1263 symlinks from being an entirely gratuitous special
1265 if (!je32_to_cpu(latest_node->isize))
1266 latest_node->isize = latest_node->dsize;
1268 if (f->inocache->state != INO_STATE_CHECKING) {
1269 /* Symlink's inode data is the target path. Read it and
1270 * keep in RAM to facilitate quick follow symlink
1272 uint32_t csize = je32_to_cpu(latest_node->csize);
1273 if (csize > JFFS2_MAX_NAME_LEN) {
1274 mutex_unlock(&f->sem);
1275 jffs2_do_clear_inode(c, f);
1276 return -ENAMETOOLONG;
1278 f->target = kmalloc(csize + 1, GFP_KERNEL);
1280 JFFS2_ERROR("can't allocate %u bytes of memory for the symlink target path cache\n", csize);
1281 mutex_unlock(&f->sem);
1282 jffs2_do_clear_inode(c, f);
1286 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref) + sizeof(*latest_node),
1287 csize, &retlen, (char *)f->target);
1289 if (ret || retlen != csize) {
1290 if (retlen != csize)
1294 mutex_unlock(&f->sem);
1295 jffs2_do_clear_inode(c, f);
1299 f->target[csize] = '\0';
1300 dbg_readinode("symlink's target '%s' cached\n", f->target);
1303 /* fall through... */
1307 /* Certain inode types should have only one data node, and it's
1308 kept as the metadata node */
1310 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o had metadata node\n",
1311 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1312 mutex_unlock(&f->sem);
1313 jffs2_do_clear_inode(c, f);
1316 if (!frag_first(&f->fragtree)) {
1317 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o has no fragments\n",
1318 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1319 mutex_unlock(&f->sem);
1320 jffs2_do_clear_inode(c, f);
1323 /* ASSERT: f->fraglist != NULL */
1324 if (frag_next(frag_first(&f->fragtree))) {
1325 JFFS2_ERROR("Argh. Special inode #%u with mode 0x%x had more than one node\n",
1326 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1327 /* FIXME: Deal with it - check crc32, check for duplicate node, check times and discard the older one */
1328 mutex_unlock(&f->sem);
1329 jffs2_do_clear_inode(c, f);
1332 /* OK. We're happy */
1333 f->metadata = frag_first(&f->fragtree)->node;
1334 jffs2_free_node_frag(frag_first(&f->fragtree));
1335 f->fragtree = RB_ROOT;
1338 if (f->inocache->state == INO_STATE_READING)
1339 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1344 /* Scan the list of all nodes present for this ino, build map of versions, etc. */
1345 int jffs2_do_read_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
1346 uint32_t ino, struct jffs2_raw_inode *latest_node)
1348 dbg_readinode("read inode #%u\n", ino);
1351 spin_lock(&c->inocache_lock);
1352 f->inocache = jffs2_get_ino_cache(c, ino);
1355 /* Check its state. We may need to wait before we can use it */
1356 switch(f->inocache->state) {
1357 case INO_STATE_UNCHECKED:
1358 case INO_STATE_CHECKEDABSENT:
1359 f->inocache->state = INO_STATE_READING;
1362 case INO_STATE_CHECKING:
1364 /* If it's in either of these states, we need
1365 to wait for whoever's got it to finish and
1367 dbg_readinode("waiting for ino #%u in state %d\n", ino, f->inocache->state);
1368 sleep_on_spinunlock(&c->inocache_wq, &c->inocache_lock);
1369 goto retry_inocache;
1371 case INO_STATE_READING:
1372 case INO_STATE_PRESENT:
1373 /* Eep. This should never happen. It can
1374 happen if Linux calls read_inode() again
1375 before clear_inode() has finished though. */
1376 JFFS2_ERROR("Eep. Trying to read_inode #%u when it's already in state %d!\n", ino, f->inocache->state);
1377 /* Fail. That's probably better than allowing it to succeed */
1385 spin_unlock(&c->inocache_lock);
1387 if (!f->inocache && ino == 1) {
1388 /* Special case - no root inode on medium */
1389 f->inocache = jffs2_alloc_inode_cache();
1391 JFFS2_ERROR("cannot allocate inocache for root inode\n");
1394 dbg_readinode("creating inocache for root inode\n");
1395 memset(f->inocache, 0, sizeof(struct jffs2_inode_cache));
1396 f->inocache->ino = f->inocache->pino_nlink = 1;
1397 f->inocache->nodes = (struct jffs2_raw_node_ref *)f->inocache;
1398 f->inocache->state = INO_STATE_READING;
1399 jffs2_add_ino_cache(c, f->inocache);
1402 JFFS2_ERROR("requestied to read an nonexistent ino %u\n", ino);
1406 return jffs2_do_read_inode_internal(c, f, latest_node);
1409 int jffs2_do_crccheck_inode(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic)
1411 struct jffs2_raw_inode n;
1412 struct jffs2_inode_info *f = kzalloc(sizeof(*f), GFP_KERNEL);
1418 mutex_init(&f->sem);
1419 mutex_lock(&f->sem);
1422 ret = jffs2_do_read_inode_internal(c, f, &n);
1424 mutex_unlock(&f->sem);
1425 jffs2_do_clear_inode(c, f);
1427 jffs2_xattr_do_crccheck_inode(c, ic);
1432 void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
1434 struct jffs2_full_dirent *fd, *fds;
1437 jffs2_xattr_delete_inode(c, f->inocache);
1438 mutex_lock(&f->sem);
1439 deleted = f->inocache && !f->inocache->pino_nlink;
1441 if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
1442 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CLEARING);
1446 jffs2_mark_node_obsolete(c, f->metadata->raw);
1447 jffs2_free_full_dnode(f->metadata);
1450 jffs2_kill_fragtree(&f->fragtree, deleted?c:NULL);
1461 jffs2_free_full_dirent(fd);
1464 if (f->inocache && f->inocache->state != INO_STATE_CHECKING) {
1465 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1466 if (f->inocache->nodes == (void *)f->inocache)
1467 jffs2_del_ino_cache(c, f->inocache);
1470 mutex_unlock(&f->sem);