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 *insert_point = NULL, *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 we add a new node it'll be somewhere under here. */
254 /* If the node is coincident with another at a lower address,
255 back up until the other node is found. It may be relevant */
256 while (tn->overlapped)
259 dbg_readinode("'this' found %#04x-%#04x (%s)\n", this->fn->ofs, this->fn->ofs + this->fn->size, this->fn ? "data" : "hole");
262 if (this->fn->ofs > fn_end)
264 dbg_readinode("Ponder this ver %d, 0x%x-0x%x\n",
265 this->version, this->fn->ofs, this->fn->size);
267 if (this->version == tn->version) {
268 /* Version number collision means REF_PRISTINE GC. Accept either of them
269 as long as the CRC is correct. Check the one we have already... */
270 if (!check_tn_node(c, this)) {
271 /* The one we already had was OK. Keep it and throw away the new one */
272 dbg_readinode("Like old node. Throw away new\n");
273 jffs2_kill_tn(c, tn);
276 /* Who cares if the new one is good; keep it for now anyway. */
277 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
278 /* Same overlapping from in front and behind */
279 jffs2_kill_tn(c, this);
280 dbg_readinode("Like new node. Throw away old\n");
284 if (this->version < tn->version &&
285 this->fn->ofs >= tn->fn->ofs &&
286 this->fn->ofs + this->fn->size <= fn_end) {
287 /* New node entirely overlaps 'this' */
288 if (check_tn_node(c, tn)) {
289 dbg_readinode("new node bad CRC\n");
290 jffs2_kill_tn(c, tn);
293 /* ... and is good. Kill 'this'... */
294 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
295 jffs2_kill_tn(c, this);
296 /* ... and any subsequent nodes which are also overlapped */
298 while (this && this->fn->ofs + this->fn->size < fn_end) {
299 struct jffs2_tmp_dnode_info *next = tn_next(this);
300 if (this->version < tn->version) {
301 tn_erase(this, &rii->tn_root);
302 dbg_readinode("Kill overlapped ver %d, 0x%x-0x%x\n",
303 this->version, this->fn->ofs,
304 this->fn->ofs+this->fn->size);
305 jffs2_kill_tn(c, this);
309 dbg_readinode("Done inserting new\n");
312 if (this->version > tn->version &&
313 this->fn->ofs <= tn->fn->ofs &&
314 this->fn->ofs+this->fn->size >= fn_end) {
315 /* New node entirely overlapped by 'this' */
316 if (!check_tn_node(c, this)) {
317 dbg_readinode("Good CRC on old node. Kill new\n");
318 jffs2_kill_tn(c, tn);
321 /* ... but 'this' was bad. Replace it... */
322 tn->overlapped = this->overlapped;
323 rb_replace_node(&this->rb, &tn->rb, &rii->tn_root);
324 dbg_readinode("Bad CRC on old overlapping node. Kill it\n");
325 jffs2_kill_tn(c, this);
328 /* We want to be inserted under the last node which is
329 either at a lower offset _or_ has a smaller range */
330 if (this->fn->ofs < tn->fn->ofs ||
331 (this->fn->ofs == tn->fn->ofs &&
332 this->fn->size <= tn->fn->size))
335 this = tn_next(this);
337 dbg_readinode("insert_point %p, ver %d, 0x%x-0x%x, ov %d\n",
338 insert_point, insert_point->version, insert_point->fn->ofs,
339 insert_point->fn->ofs+insert_point->fn->size,
340 insert_point->overlapped);
341 /* We neither completely obsoleted nor were completely
342 obsoleted by an earlier node. Insert under insert_point */
344 struct rb_node *parent = &insert_point->rb;
345 struct rb_node **link = &parent;
349 insert_point = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
350 if (tn->fn->ofs > insert_point->fn->ofs)
351 link = &insert_point->rb.rb_right;
352 else if (tn->fn->ofs < insert_point->fn->ofs ||
353 tn->fn->size < insert_point->fn->size)
354 link = &insert_point->rb.rb_left;
356 link = &insert_point->rb.rb_right;
358 rb_link_node(&tn->rb, &insert_point->rb, link);
359 rb_insert_color(&tn->rb, &rii->tn_root);
363 /* If there's anything behind that overlaps us, note it */
367 if (this->fn->ofs + this->fn->size > tn->fn->ofs) {
368 dbg_readinode("Node is overlapped by %p (v %d, 0x%x-0x%x)\n",
369 this, this->version, this->fn->ofs,
370 this->fn->ofs+this->fn->size);
374 if (!this->overlapped)
376 this = tn_prev(this);
380 /* If the new node overlaps anything ahead, note it */
382 while (this && this->fn->ofs < fn_end) {
383 this->overlapped = 1;
384 dbg_readinode("Node ver %d, 0x%x-0x%x is overlapped\n",
385 this->version, this->fn->ofs,
386 this->fn->ofs+this->fn->size);
387 this = tn_next(this);
392 /* Trivial function to remove the last node in the tree. Which by definition
393 has no right-hand -- so can be removed just by making its only child (if
394 any) take its place under its parent. */
395 static void eat_last(struct rb_root *root, struct rb_node *node)
397 struct rb_node *parent = rb_parent(node);
398 struct rb_node **link;
401 BUG_ON(node->rb_right);
404 link = &root->rb_node;
405 else if (node == parent->rb_left)
406 link = &parent->rb_left;
408 link = &parent->rb_right;
410 *link = node->rb_left;
411 /* Colour doesn't matter now. Only the parent pointer. */
413 node->rb_left->rb_parent_color = node->rb_parent_color;
416 /* We put this in reverse order, so we can just use eat_last */
417 static void ver_insert(struct rb_root *ver_root, struct jffs2_tmp_dnode_info *tn)
419 struct rb_node **link = &ver_root->rb_node;
420 struct rb_node *parent = NULL;
421 struct jffs2_tmp_dnode_info *this_tn;
425 this_tn = rb_entry(parent, struct jffs2_tmp_dnode_info, rb);
427 if (tn->version > this_tn->version)
428 link = &parent->rb_left;
430 link = &parent->rb_right;
432 dbg_readinode("Link new node at %p (root is %p)\n", link, ver_root);
433 rb_link_node(&tn->rb, parent, link);
434 rb_insert_color(&tn->rb, ver_root);
437 /* Build final, normal fragtree from tn tree. It doesn't matter which order
438 we add nodes to the real fragtree, as long as they don't overlap. And
439 having thrown away the majority of overlapped nodes as we went, there
440 really shouldn't be many sets of nodes which do overlap. If we start at
441 the end, we can use the overlap markers -- we can just eat nodes which
442 aren't overlapped, and when we encounter nodes which _do_ overlap we
443 sort them all into a temporary tree in version order before replaying them. */
444 static int jffs2_build_inode_fragtree(struct jffs2_sb_info *c,
445 struct jffs2_inode_info *f,
446 struct jffs2_readinode_info *rii)
448 struct jffs2_tmp_dnode_info *pen, *last, *this;
449 struct rb_root ver_root = RB_ROOT;
450 uint32_t high_ver = 0;
453 dbg_readinode("potential mdata is ver %d at %p\n", rii->mdata_tn->version, rii->mdata_tn);
454 high_ver = rii->mdata_tn->version;
455 rii->latest_ref = rii->mdata_tn->fn->raw;
457 #ifdef JFFS2_DBG_READINODE_MESSAGES
458 this = tn_last(&rii->tn_root);
460 dbg_readinode("tn %p ver %d range 0x%x-0x%x ov %d\n", this, this->version, this->fn->ofs,
461 this->fn->ofs+this->fn->size, this->overlapped);
462 this = tn_prev(this);
465 pen = tn_last(&rii->tn_root);
466 while ((last = pen)) {
469 eat_last(&rii->tn_root, &last->rb);
470 ver_insert(&ver_root, last);
472 if (unlikely(last->overlapped))
475 /* Now we have a bunch of nodes in reverse version
476 order, in the tree at ver_root. Most of the time,
477 there'll actually be only one node in the 'tree',
479 this = tn_last(&ver_root);
482 struct jffs2_tmp_dnode_info *vers_next;
484 vers_next = tn_prev(this);
485 eat_last(&ver_root, &this->rb);
486 if (check_tn_node(c, this)) {
487 dbg_readinode("node ver %d, 0x%x-0x%x failed CRC\n",
488 this->version, this->fn->ofs,
489 this->fn->ofs+this->fn->size);
490 jffs2_kill_tn(c, this);
492 if (this->version > high_ver) {
493 /* Note that this is different from the other
494 highest_version, because this one is only
495 counting _valid_ nodes which could give the
496 latest inode metadata */
497 high_ver = this->version;
498 rii->latest_ref = this->fn->raw;
500 dbg_readinode("Add %p (v %d, 0x%x-0x%x, ov %d) to fragtree\n",
501 this, this->version, this->fn->ofs,
502 this->fn->ofs+this->fn->size, this->overlapped);
504 ret = jffs2_add_full_dnode_to_inode(c, f, this->fn);
506 /* Free the nodes in vers_root; let the caller
507 deal with the rest */
508 JFFS2_ERROR("Add node to tree failed %d\n", ret);
510 vers_next = tn_prev(this);
511 if (check_tn_node(c, this))
512 jffs2_mark_node_obsolete(c, this->fn->raw);
513 jffs2_free_full_dnode(this->fn);
514 jffs2_free_tmp_dnode_info(this);
518 eat_last(&ver_root, &vers_next->rb);
522 jffs2_free_tmp_dnode_info(this);
530 static void jffs2_free_tmp_dnode_info_list(struct rb_root *list)
532 struct rb_node *this;
533 struct jffs2_tmp_dnode_info *tn;
535 this = list->rb_node;
537 /* Now at bottom of tree */
540 this = this->rb_left;
541 else if (this->rb_right)
542 this = this->rb_right;
544 tn = rb_entry(this, struct jffs2_tmp_dnode_info, rb);
545 jffs2_free_full_dnode(tn->fn);
546 jffs2_free_tmp_dnode_info(tn);
548 this = rb_parent(this);
552 if (this->rb_left == &tn->rb)
553 this->rb_left = NULL;
554 else if (this->rb_right == &tn->rb)
555 this->rb_right = NULL;
559 list->rb_node = NULL;
562 static void jffs2_free_full_dirent_list(struct jffs2_full_dirent *fd)
564 struct jffs2_full_dirent *next;
568 jffs2_free_full_dirent(fd);
573 /* Returns first valid node after 'ref'. May return 'ref' */
574 static struct jffs2_raw_node_ref *jffs2_first_valid_node(struct jffs2_raw_node_ref *ref)
576 while (ref && ref->next_in_ino) {
577 if (!ref_obsolete(ref))
579 dbg_noderef("node at 0x%08x is obsoleted. Ignoring.\n", ref_offset(ref));
580 ref = ref->next_in_ino;
586 * Helper function for jffs2_get_inode_nodes().
587 * It is called every time an directory entry node is found.
589 * Returns: 0 on succes;
590 * 1 if the node should be marked obsolete;
591 * negative error code on failure.
593 static inline int read_direntry(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
594 struct jffs2_raw_dirent *rd, size_t read,
595 struct jffs2_readinode_info *rii)
597 struct jffs2_full_dirent *fd;
600 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
601 BUG_ON(ref_obsolete(ref));
603 crc = crc32(0, rd, sizeof(*rd) - 8);
604 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
605 JFFS2_NOTICE("header CRC failed on dirent node at %#08x: read %#08x, calculated %#08x\n",
606 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
607 jffs2_mark_node_obsolete(c, ref);
611 /* If we've never checked the CRCs on this node, check them now */
612 if (ref_flags(ref) == REF_UNCHECKED) {
613 struct jffs2_eraseblock *jeb;
617 if (unlikely(PAD((rd->nsize + sizeof(*rd))) != PAD(je32_to_cpu(rd->totlen)))) {
618 JFFS2_ERROR("illegal nsize in node at %#08x: nsize %#02x, totlen %#04x\n",
619 ref_offset(ref), rd->nsize, je32_to_cpu(rd->totlen));
620 jffs2_mark_node_obsolete(c, ref);
624 jeb = &c->blocks[ref->flash_offset / c->sector_size];
625 len = ref_totlen(c, jeb, ref);
627 spin_lock(&c->erase_completion_lock);
628 jeb->used_size += len;
629 jeb->unchecked_size -= len;
631 c->unchecked_size -= len;
632 ref->flash_offset = ref_offset(ref) | REF_PRISTINE;
633 spin_unlock(&c->erase_completion_lock);
636 fd = jffs2_alloc_full_dirent(rd->nsize + 1);
641 fd->version = je32_to_cpu(rd->version);
642 fd->ino = je32_to_cpu(rd->ino);
645 if (fd->version > rii->highest_version)
646 rii->highest_version = fd->version;
648 /* Pick out the mctime of the latest dirent */
649 if(fd->version > rii->mctime_ver && je32_to_cpu(rd->mctime)) {
650 rii->mctime_ver = fd->version;
651 rii->latest_mctime = je32_to_cpu(rd->mctime);
655 * Copy as much of the name as possible from the raw
656 * dirent we've already read from the flash.
658 if (read > sizeof(*rd))
659 memcpy(&fd->name[0], &rd->name[0],
660 min_t(uint32_t, rd->nsize, (read - sizeof(*rd)) ));
662 /* Do we need to copy any more of the name directly from the flash? */
663 if (rd->nsize + sizeof(*rd) > read) {
666 int already = read - sizeof(*rd);
668 err = jffs2_flash_read(c, (ref_offset(ref)) + read,
669 rd->nsize - already, &read, &fd->name[already]);
670 if (unlikely(read != rd->nsize - already) && likely(!err))
674 JFFS2_ERROR("read remainder of name: error %d\n", err);
675 jffs2_free_full_dirent(fd);
680 fd->nhash = full_name_hash(fd->name, rd->nsize);
682 fd->name[rd->nsize] = '\0';
685 * Wheee. We now have a complete jffs2_full_dirent structure, with
686 * the name in it and everything. Link it into the list
688 jffs2_add_fd_to_list(c, fd, &rii->fds);
694 * Helper function for jffs2_get_inode_nodes().
695 * It is called every time an inode node is found.
697 * Returns: 0 on success;
698 * 1 if the node should be marked obsolete;
699 * negative error code on failure.
701 static inline int read_dnode(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
702 struct jffs2_raw_inode *rd, int rdlen,
703 struct jffs2_readinode_info *rii)
705 struct jffs2_tmp_dnode_info *tn;
710 /* Obsoleted. This cannot happen, surely? dwmw2 20020308 */
711 BUG_ON(ref_obsolete(ref));
713 crc = crc32(0, rd, sizeof(*rd) - 8);
714 if (unlikely(crc != je32_to_cpu(rd->node_crc))) {
715 JFFS2_NOTICE("node CRC failed on dnode at %#08x: read %#08x, calculated %#08x\n",
716 ref_offset(ref), je32_to_cpu(rd->node_crc), crc);
717 jffs2_mark_node_obsolete(c, ref);
721 tn = jffs2_alloc_tmp_dnode_info();
723 JFFS2_ERROR("failed to allocate tn (%zu bytes).\n", sizeof(*tn));
728 csize = je32_to_cpu(rd->csize);
730 /* If we've never checked the CRCs on this node, check them now */
731 if (ref_flags(ref) == REF_UNCHECKED) {
734 if (unlikely(je32_to_cpu(rd->offset) > je32_to_cpu(rd->isize)) ||
735 unlikely(PAD(je32_to_cpu(rd->csize) + sizeof(*rd)) != PAD(je32_to_cpu(rd->totlen)))) {
736 JFFS2_WARNING("inode node header CRC is corrupted at %#08x\n", ref_offset(ref));
737 jffs2_dbg_dump_node(c, ref_offset(ref));
741 if (jffs2_is_writebuffered(c) && csize != 0) {
742 /* At this point we are supposed to check the data CRC
743 * of our unchecked node. But thus far, we do not
744 * know whether the node is valid or obsolete. To
745 * figure this out, we need to walk all the nodes of
746 * the inode and build the inode fragtree. We don't
747 * want to spend time checking data of nodes which may
748 * later be found to be obsolete. So we put off the full
749 * data CRC checking until we have read all the inode
750 * nodes and have started building the fragtree.
752 * The fragtree is being built starting with nodes
753 * having the highest version number, so we'll be able
754 * to detect whether a node is valid (i.e., it is not
755 * overlapped by a node with higher version) or not.
756 * And we'll be able to check only those nodes, which
759 * Of course, this optimization only makes sense in case
760 * of NAND flashes (or other flashes whith
761 * !jffs2_can_mark_obsolete()), since on NOR flashes
762 * nodes are marked obsolete physically.
764 * Since NAND flashes (or other flashes with
765 * jffs2_is_writebuffered(c)) are anyway read by
766 * fractions of c->wbuf_pagesize, and we have just read
767 * the node header, it is likely that the starting part
768 * of the node data is also read when we read the
769 * header. So we don't mind to check the CRC of the
770 * starting part of the data of the node now, and check
771 * the second part later (in jffs2_check_node_data()).
772 * Of course, we will not need to re-read and re-check
773 * the NAND page which we have just read. This is why we
774 * read the whole NAND page at jffs2_get_inode_nodes(),
775 * while we needed only the node header.
779 /* 'buf' will point to the start of data */
780 buf = (unsigned char *)rd + sizeof(*rd);
781 /* len will be the read data length */
782 len = min_t(uint32_t, rdlen - sizeof(*rd), csize);
783 tn->partial_crc = crc32(0, buf, len);
785 dbg_readinode("Calculates CRC (%#08x) for %d bytes, csize %d\n", tn->partial_crc, len, csize);
787 /* If we actually calculated the whole data CRC
788 * and it is wrong, drop the node. */
789 if (len >= csize && unlikely(tn->partial_crc != je32_to_cpu(rd->data_crc))) {
790 JFFS2_NOTICE("wrong data CRC in data node at 0x%08x: read %#08x, calculated %#08x.\n",
791 ref_offset(ref), tn->partial_crc, je32_to_cpu(rd->data_crc));
795 } else if (csize == 0) {
797 * We checked the header CRC. If the node has no data, adjust
798 * the space accounting now. For other nodes this will be done
799 * later either when the node is marked obsolete or when its
802 struct jffs2_eraseblock *jeb;
804 dbg_readinode("the node has no data.\n");
805 jeb = &c->blocks[ref->flash_offset / c->sector_size];
806 len = ref_totlen(c, jeb, ref);
808 spin_lock(&c->erase_completion_lock);
809 jeb->used_size += len;
810 jeb->unchecked_size -= len;
812 c->unchecked_size -= len;
813 ref->flash_offset = ref_offset(ref) | REF_NORMAL;
814 spin_unlock(&c->erase_completion_lock);
818 tn->fn = jffs2_alloc_full_dnode();
820 JFFS2_ERROR("alloc fn failed\n");
825 tn->version = je32_to_cpu(rd->version);
826 tn->fn->ofs = je32_to_cpu(rd->offset);
827 tn->data_crc = je32_to_cpu(rd->data_crc);
832 if (tn->version > rii->highest_version)
833 rii->highest_version = tn->version;
835 /* There was a bug where we wrote hole nodes out with
836 csize/dsize swapped. Deal with it */
837 if (rd->compr == JFFS2_COMPR_ZERO && !je32_to_cpu(rd->dsize) && csize)
838 tn->fn->size = csize;
839 else // normal case...
840 tn->fn->size = je32_to_cpu(rd->dsize);
842 dbg_readinode("dnode @%08x: ver %u, offset %#04x, dsize %#04x, csize %#04x\n",
843 ref_offset(ref), je32_to_cpu(rd->version), je32_to_cpu(rd->offset), je32_to_cpu(rd->dsize), csize);
845 ret = jffs2_add_tn_to_tree(c, rii, tn);
848 jffs2_free_full_dnode(tn->fn);
850 jffs2_free_tmp_dnode_info(tn);
853 #ifdef JFFS2_DBG_READINODE_MESSAGES
854 dbg_readinode("After adding ver %d:\n", je32_to_cpu(rd->version));
855 tn = tn_first(&rii->tn_root);
857 dbg_readinode("%p: v %d r 0x%x-0x%x ov %d\n",
858 tn, tn->version, tn->fn->ofs,
859 tn->fn->ofs+tn->fn->size, tn->overlapped);
867 * Helper function for jffs2_get_inode_nodes().
868 * It is called every time an unknown node is found.
870 * Returns: 0 on success;
871 * 1 if the node should be marked obsolete;
872 * negative error code on failure.
874 static inline int read_unknown(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref, struct jffs2_unknown_node *un)
876 /* We don't mark unknown nodes as REF_UNCHECKED */
877 if (ref_flags(ref) == REF_UNCHECKED) {
878 JFFS2_ERROR("REF_UNCHECKED but unknown node at %#08x\n",
880 JFFS2_ERROR("Node is {%04x,%04x,%08x,%08x}. Please report this error.\n",
881 je16_to_cpu(un->magic), je16_to_cpu(un->nodetype),
882 je32_to_cpu(un->totlen), je32_to_cpu(un->hdr_crc));
883 jffs2_mark_node_obsolete(c, ref);
887 un->nodetype = cpu_to_je16(JFFS2_NODE_ACCURATE | je16_to_cpu(un->nodetype));
889 switch(je16_to_cpu(un->nodetype) & JFFS2_COMPAT_MASK) {
891 case JFFS2_FEATURE_INCOMPAT:
892 JFFS2_ERROR("unknown INCOMPAT nodetype %#04X at %#08x\n",
893 je16_to_cpu(un->nodetype), ref_offset(ref));
898 case JFFS2_FEATURE_ROCOMPAT:
899 JFFS2_ERROR("unknown ROCOMPAT nodetype %#04X at %#08x\n",
900 je16_to_cpu(un->nodetype), ref_offset(ref));
901 BUG_ON(!(c->flags & JFFS2_SB_FLAG_RO));
904 case JFFS2_FEATURE_RWCOMPAT_COPY:
905 JFFS2_NOTICE("unknown RWCOMPAT_COPY nodetype %#04X at %#08x\n",
906 je16_to_cpu(un->nodetype), ref_offset(ref));
909 case JFFS2_FEATURE_RWCOMPAT_DELETE:
910 JFFS2_NOTICE("unknown RWCOMPAT_DELETE nodetype %#04X at %#08x\n",
911 je16_to_cpu(un->nodetype), ref_offset(ref));
912 jffs2_mark_node_obsolete(c, ref);
920 * Helper function for jffs2_get_inode_nodes().
921 * The function detects whether more data should be read and reads it if yes.
923 * Returns: 0 on succes;
924 * negative error code on failure.
926 static int read_more(struct jffs2_sb_info *c, struct jffs2_raw_node_ref *ref,
927 int needed_len, int *rdlen, unsigned char *buf)
929 int err, to_read = needed_len - *rdlen;
933 if (jffs2_is_writebuffered(c)) {
934 int rem = to_read % c->wbuf_pagesize;
937 to_read += c->wbuf_pagesize - rem;
940 /* We need to read more data */
941 offs = ref_offset(ref) + *rdlen;
943 dbg_readinode("read more %d bytes\n", to_read);
945 err = jffs2_flash_read(c, offs, to_read, &retlen, buf + *rdlen);
947 JFFS2_ERROR("can not read %d bytes from 0x%08x, "
948 "error code: %d.\n", to_read, offs, err);
952 if (retlen < to_read) {
953 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n",
954 offs, retlen, to_read);
962 /* Get tmp_dnode_info and full_dirent for all non-obsolete nodes associated
963 with this ino. Perform a preliminary ordering on data nodes, throwing away
964 those which are completely obsoleted by newer ones. The naïve approach we
965 use to take of just returning them _all_ in version order will cause us to
966 run out of memory in certain degenerate cases. */
967 static int jffs2_get_inode_nodes(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
968 struct jffs2_readinode_info *rii)
970 struct jffs2_raw_node_ref *ref, *valid_ref;
971 unsigned char *buf = NULL;
972 union jffs2_node_union *node;
978 dbg_readinode("ino #%u\n", f->inocache->ino);
980 /* FIXME: in case of NOR and available ->point() this
981 * needs to be fixed. */
982 len = sizeof(union jffs2_node_union) + c->wbuf_pagesize;
983 buf = kmalloc(len, GFP_KERNEL);
987 spin_lock(&c->erase_completion_lock);
988 valid_ref = jffs2_first_valid_node(f->inocache->nodes);
989 if (!valid_ref && f->inocache->ino != 1)
990 JFFS2_WARNING("Eep. No valid nodes for ino #%u.\n", f->inocache->ino);
992 /* We can hold a pointer to a non-obsolete node without the spinlock,
993 but _obsolete_ nodes may disappear at any time, if the block
994 they're in gets erased. So if we mark 'ref' obsolete while we're
995 not holding the lock, it can go away immediately. For that reason,
996 we find the next valid node first, before processing 'ref'.
999 valid_ref = jffs2_first_valid_node(ref->next_in_ino);
1000 spin_unlock(&c->erase_completion_lock);
1005 * At this point we don't know the type of the node we're going
1006 * to read, so we do not know the size of its header. In order
1007 * to minimize the amount of flash IO we assume the header is
1008 * of size = JFFS2_MIN_NODE_HEADER.
1010 len = JFFS2_MIN_NODE_HEADER;
1011 if (jffs2_is_writebuffered(c)) {
1015 * We are about to read JFFS2_MIN_NODE_HEADER bytes,
1016 * but this flash has some minimal I/O unit. It is
1017 * possible that we'll need to read more soon, so read
1018 * up to the next min. I/O unit, in order not to
1019 * re-read the same min. I/O unit twice.
1021 end = ref_offset(ref) + len;
1022 rem = end % c->wbuf_pagesize;
1024 end += c->wbuf_pagesize - rem;
1025 len = end - ref_offset(ref);
1028 dbg_readinode("read %d bytes at %#08x(%d).\n", len, ref_offset(ref), ref_flags(ref));
1030 /* FIXME: point() */
1031 err = jffs2_flash_read(c, ref_offset(ref), len, &retlen, buf);
1033 JFFS2_ERROR("can not read %d bytes from 0x%08x, " "error code: %d.\n", len, ref_offset(ref), err);
1038 JFFS2_ERROR("short read at %#08x: %zu instead of %d.\n", ref_offset(ref), retlen, len);
1043 node = (union jffs2_node_union *)buf;
1045 /* No need to mask in the valid bit; it shouldn't be invalid */
1046 if (je32_to_cpu(node->u.hdr_crc) != crc32(0, node, sizeof(node->u)-4)) {
1047 JFFS2_NOTICE("Node header CRC failed at %#08x. {%04x,%04x,%08x,%08x}\n",
1048 ref_offset(ref), je16_to_cpu(node->u.magic),
1049 je16_to_cpu(node->u.nodetype),
1050 je32_to_cpu(node->u.totlen),
1051 je32_to_cpu(node->u.hdr_crc));
1052 jffs2_dbg_dump_node(c, ref_offset(ref));
1053 jffs2_mark_node_obsolete(c, ref);
1056 if (je16_to_cpu(node->u.magic) != JFFS2_MAGIC_BITMASK) {
1057 /* Not a JFFS2 node, whinge and move on */
1058 JFFS2_NOTICE("Wrong magic bitmask 0x%04x in node header at %#08x.\n",
1059 je16_to_cpu(node->u.magic), ref_offset(ref));
1060 jffs2_mark_node_obsolete(c, ref);
1064 switch (je16_to_cpu(node->u.nodetype)) {
1066 case JFFS2_NODETYPE_DIRENT:
1068 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_dirent)) {
1069 err = read_more(c, ref, sizeof(struct jffs2_raw_dirent), &len, buf);
1074 err = read_direntry(c, ref, &node->d, retlen, rii);
1080 case JFFS2_NODETYPE_INODE:
1082 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_raw_inode)) {
1083 err = read_more(c, ref, sizeof(struct jffs2_raw_inode), &len, buf);
1088 err = read_dnode(c, ref, &node->i, len, rii);
1095 if (JFFS2_MIN_NODE_HEADER < sizeof(struct jffs2_unknown_node)) {
1096 err = read_more(c, ref, sizeof(struct jffs2_unknown_node), &len, buf);
1101 err = read_unknown(c, ref, &node->u);
1103 jffs2_mark_node_obsolete(c, ref);
1105 } else if (unlikely(err))
1110 spin_lock(&c->erase_completion_lock);
1113 spin_unlock(&c->erase_completion_lock);
1116 f->highest_version = rii->highest_version;
1118 dbg_readinode("nodes of inode #%u were read, the highest version is %u, latest_mctime %u, mctime_ver %u.\n",
1119 f->inocache->ino, rii->highest_version, rii->latest_mctime,
1124 jffs2_free_tmp_dnode_info_list(&rii->tn_root);
1125 jffs2_free_full_dirent_list(rii->fds);
1131 static int jffs2_do_read_inode_internal(struct jffs2_sb_info *c,
1132 struct jffs2_inode_info *f,
1133 struct jffs2_raw_inode *latest_node)
1135 struct jffs2_readinode_info rii;
1136 uint32_t crc, new_size;
1140 dbg_readinode("ino #%u nlink is %d\n", f->inocache->ino, f->inocache->nlink);
1142 memset(&rii, 0, sizeof(rii));
1144 /* Grab all nodes relevant to this ino */
1145 ret = jffs2_get_inode_nodes(c, f, &rii);
1148 JFFS2_ERROR("cannot read nodes for ino %u, returned error is %d\n", f->inocache->ino, ret);
1149 if (f->inocache->state == INO_STATE_READING)
1150 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1154 ret = jffs2_build_inode_fragtree(c, f, &rii);
1156 JFFS2_ERROR("Failed to build final fragtree for inode #%u: error %d\n",
1157 f->inocache->ino, ret);
1158 if (f->inocache->state == INO_STATE_READING)
1159 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1160 jffs2_free_tmp_dnode_info_list(&rii.tn_root);
1161 /* FIXME: We could at least crc-check them all */
1163 jffs2_free_full_dnode(rii.mdata_tn->fn);
1164 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1165 rii.mdata_tn = NULL;
1171 if (rii.mdata_tn->fn->raw == rii.latest_ref) {
1172 f->metadata = rii.mdata_tn->fn;
1173 jffs2_free_tmp_dnode_info(rii.mdata_tn);
1175 jffs2_kill_tn(c, rii.mdata_tn);
1177 rii.mdata_tn = NULL;
1182 jffs2_dbg_fragtree_paranoia_check_nolock(f);
1184 if (unlikely(!rii.latest_ref)) {
1185 /* No data nodes for this inode. */
1186 if (f->inocache->ino != 1) {
1187 JFFS2_WARNING("no data nodes found for ino #%u\n", f->inocache->ino);
1189 if (f->inocache->state == INO_STATE_READING)
1190 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1193 JFFS2_NOTICE("but it has children so we fake some modes for it\n");
1195 latest_node->mode = cpu_to_jemode(S_IFDIR|S_IRUGO|S_IWUSR|S_IXUGO);
1196 latest_node->version = cpu_to_je32(0);
1197 latest_node->atime = latest_node->ctime = latest_node->mtime = cpu_to_je32(0);
1198 latest_node->isize = cpu_to_je32(0);
1199 latest_node->gid = cpu_to_je16(0);
1200 latest_node->uid = cpu_to_je16(0);
1201 if (f->inocache->state == INO_STATE_READING)
1202 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1206 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref), sizeof(*latest_node), &retlen, (void *)latest_node);
1207 if (ret || retlen != sizeof(*latest_node)) {
1208 JFFS2_ERROR("failed to read from flash: error %d, %zd of %zd bytes read\n",
1209 ret, retlen, sizeof(*latest_node));
1210 /* FIXME: If this fails, there seems to be a memory leak. Find it. */
1212 jffs2_do_clear_inode(c, f);
1213 return ret?ret:-EIO;
1216 crc = crc32(0, latest_node, sizeof(*latest_node)-8);
1217 if (crc != je32_to_cpu(latest_node->node_crc)) {
1218 JFFS2_ERROR("CRC failed for read_inode of inode %u at physical location 0x%x\n",
1219 f->inocache->ino, ref_offset(rii.latest_ref));
1221 jffs2_do_clear_inode(c, f);
1225 switch(jemode_to_cpu(latest_node->mode) & S_IFMT) {
1227 if (rii.mctime_ver > je32_to_cpu(latest_node->version)) {
1228 /* The times in the latest_node are actually older than
1229 mctime in the latest dirent. Cheat. */
1230 latest_node->ctime = latest_node->mtime = cpu_to_je32(rii.latest_mctime);
1236 /* If it was a regular file, truncate it to the latest node's isize */
1237 new_size = jffs2_truncate_fragtree(c, &f->fragtree, je32_to_cpu(latest_node->isize));
1238 if (new_size != je32_to_cpu(latest_node->isize)) {
1239 JFFS2_WARNING("Truncating ino #%u to %d bytes failed because it only had %d bytes to start with!\n",
1240 f->inocache->ino, je32_to_cpu(latest_node->isize), new_size);
1241 latest_node->isize = cpu_to_je32(new_size);
1246 /* Hack to work around broken isize in old symlink code.
1247 Remove this when dwmw2 comes to his senses and stops
1248 symlinks from being an entirely gratuitous special
1250 if (!je32_to_cpu(latest_node->isize))
1251 latest_node->isize = latest_node->dsize;
1253 if (f->inocache->state != INO_STATE_CHECKING) {
1254 /* Symlink's inode data is the target path. Read it and
1255 * keep in RAM to facilitate quick follow symlink
1257 f->target = kmalloc(je32_to_cpu(latest_node->csize) + 1, GFP_KERNEL);
1259 JFFS2_ERROR("can't allocate %d bytes of memory for the symlink target path cache\n", je32_to_cpu(latest_node->csize));
1261 jffs2_do_clear_inode(c, f);
1265 ret = jffs2_flash_read(c, ref_offset(rii.latest_ref) + sizeof(*latest_node),
1266 je32_to_cpu(latest_node->csize), &retlen, (char *)f->target);
1268 if (ret || retlen != je32_to_cpu(latest_node->csize)) {
1269 if (retlen != je32_to_cpu(latest_node->csize))
1274 jffs2_do_clear_inode(c, f);
1278 f->target[je32_to_cpu(latest_node->csize)] = '\0';
1279 dbg_readinode("symlink's target '%s' cached\n", f->target);
1282 /* fall through... */
1286 /* Certain inode types should have only one data node, and it's
1287 kept as the metadata node */
1289 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o had metadata node\n",
1290 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1292 jffs2_do_clear_inode(c, f);
1295 if (!frag_first(&f->fragtree)) {
1296 JFFS2_ERROR("Argh. Special inode #%u with mode 0%o has no fragments\n",
1297 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1299 jffs2_do_clear_inode(c, f);
1302 /* ASSERT: f->fraglist != NULL */
1303 if (frag_next(frag_first(&f->fragtree))) {
1304 JFFS2_ERROR("Argh. Special inode #%u with mode 0x%x had more than one node\n",
1305 f->inocache->ino, jemode_to_cpu(latest_node->mode));
1306 /* FIXME: Deal with it - check crc32, check for duplicate node, check times and discard the older one */
1308 jffs2_do_clear_inode(c, f);
1311 /* OK. We're happy */
1312 f->metadata = frag_first(&f->fragtree)->node;
1313 jffs2_free_node_frag(frag_first(&f->fragtree));
1314 f->fragtree = RB_ROOT;
1317 if (f->inocache->state == INO_STATE_READING)
1318 jffs2_set_inocache_state(c, f->inocache, INO_STATE_PRESENT);
1323 /* Scan the list of all nodes present for this ino, build map of versions, etc. */
1324 int jffs2_do_read_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f,
1325 uint32_t ino, struct jffs2_raw_inode *latest_node)
1327 dbg_readinode("read inode #%u\n", ino);
1330 spin_lock(&c->inocache_lock);
1331 f->inocache = jffs2_get_ino_cache(c, ino);
1334 /* Check its state. We may need to wait before we can use it */
1335 switch(f->inocache->state) {
1336 case INO_STATE_UNCHECKED:
1337 case INO_STATE_CHECKEDABSENT:
1338 f->inocache->state = INO_STATE_READING;
1341 case INO_STATE_CHECKING:
1343 /* If it's in either of these states, we need
1344 to wait for whoever's got it to finish and
1346 dbg_readinode("waiting for ino #%u in state %d\n", ino, f->inocache->state);
1347 sleep_on_spinunlock(&c->inocache_wq, &c->inocache_lock);
1348 goto retry_inocache;
1350 case INO_STATE_READING:
1351 case INO_STATE_PRESENT:
1352 /* Eep. This should never happen. It can
1353 happen if Linux calls read_inode() again
1354 before clear_inode() has finished though. */
1355 JFFS2_ERROR("Eep. Trying to read_inode #%u when it's already in state %d!\n", ino, f->inocache->state);
1356 /* Fail. That's probably better than allowing it to succeed */
1364 spin_unlock(&c->inocache_lock);
1366 if (!f->inocache && ino == 1) {
1367 /* Special case - no root inode on medium */
1368 f->inocache = jffs2_alloc_inode_cache();
1370 JFFS2_ERROR("cannot allocate inocache for root inode\n");
1373 dbg_readinode("creating inocache for root inode\n");
1374 memset(f->inocache, 0, sizeof(struct jffs2_inode_cache));
1375 f->inocache->ino = f->inocache->nlink = 1;
1376 f->inocache->nodes = (struct jffs2_raw_node_ref *)f->inocache;
1377 f->inocache->state = INO_STATE_READING;
1378 jffs2_add_ino_cache(c, f->inocache);
1381 JFFS2_ERROR("requestied to read an nonexistent ino %u\n", ino);
1385 return jffs2_do_read_inode_internal(c, f, latest_node);
1388 int jffs2_do_crccheck_inode(struct jffs2_sb_info *c, struct jffs2_inode_cache *ic)
1390 struct jffs2_raw_inode n;
1391 struct jffs2_inode_info *f = kzalloc(sizeof(*f), GFP_KERNEL);
1397 init_MUTEX_LOCKED(&f->sem);
1400 ret = jffs2_do_read_inode_internal(c, f, &n);
1403 jffs2_do_clear_inode(c, f);
1409 void jffs2_do_clear_inode(struct jffs2_sb_info *c, struct jffs2_inode_info *f)
1411 struct jffs2_full_dirent *fd, *fds;
1415 jffs2_xattr_delete_inode(c, f->inocache);
1417 deleted = f->inocache && !f->inocache->nlink;
1419 if (f->inocache && f->inocache->state != INO_STATE_CHECKING)
1420 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CLEARING);
1424 jffs2_mark_node_obsolete(c, f->metadata->raw);
1425 jffs2_free_full_dnode(f->metadata);
1428 jffs2_kill_fragtree(&f->fragtree, deleted?c:NULL);
1439 jffs2_free_full_dirent(fd);
1442 if (f->inocache && f->inocache->state != INO_STATE_CHECKING) {
1443 jffs2_set_inocache_state(c, f->inocache, INO_STATE_CHECKEDABSENT);
1444 if (f->inocache->nodes == (void *)f->inocache)
1445 jffs2_del_ino_cache(c, f->inocache);