2 * Copyright (c) International Business Machines Corp., 2006
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12 * the GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 * Author: Artem Bityutskiy (Битюцкий Артём)
24 * This unit is responsible for scanning the flash media, checking UBI
25 * headers and providing complete information about the UBI flash image.
27 * The scanning information is reoresented by a &struct ubi_scan_info' object.
28 * Information about found volumes is represented by &struct ubi_scan_volume
29 * objects which are kept in volume RB-tree with root at the @volumes field.
30 * The RB-tree is indexed by the volume ID.
32 * Found logical eraseblocks are represented by &struct ubi_scan_leb objects.
33 * These objects are kept in per-volume RB-trees with the root at the
34 * corresponding &struct ubi_scan_volume object. To put it differently, we keep
35 * an RB-tree of per-volume objects and each of these objects is the root of
36 * RB-tree of per-eraseblock objects.
38 * Corrupted physical eraseblocks are put to the @corr list, free physical
39 * eraseblocks are put to the @free list and the physical eraseblock to be
40 * erased are put to the @erase list.
43 #include <linux/err.h>
44 #include <linux/crc32.h>
47 #ifdef CONFIG_MTD_UBI_DEBUG_PARANOID
48 static int paranoid_check_si(const struct ubi_device *ubi,
49 struct ubi_scan_info *si);
51 #define paranoid_check_si(ubi, si) 0
54 /* Temporary variables used during scanning */
55 static struct ubi_ec_hdr *ech;
56 static struct ubi_vid_hdr *vidh;
58 int ubi_scan_add_to_list(struct ubi_scan_info *si, int pnum, int ec,
59 struct list_head *list)
61 struct ubi_scan_leb *seb;
63 if (list == &si->free)
64 dbg_bld("add to free: PEB %d, EC %d", pnum, ec);
65 else if (list == &si->erase)
66 dbg_bld("add to erase: PEB %d, EC %d", pnum, ec);
67 else if (list == &si->corr)
68 dbg_bld("add to corrupted: PEB %d, EC %d", pnum, ec);
69 else if (list == &si->alien)
70 dbg_bld("add to alien: PEB %d, EC %d", pnum, ec);
74 seb = kmalloc(sizeof(struct ubi_scan_leb), GFP_KERNEL);
80 list_add_tail(&seb->u.list, list);
85 * commit_to_mean_value - commit intermediate results to the final mean erase
87 * @si: scanning information
89 * This is a helper function which calculates partial mean erase counter mean
90 * value and adds it to the resulting mean value. As we can work only in
91 * integer arithmetic and we want to calculate the mean value of erase counter
92 * accurately, we first sum erase counter values in @si->ec_sum variable and
93 * count these components in @si->ec_count. If this temporary @si->ec_sum is
94 * going to overflow, we calculate the partial mean value
95 * (@si->ec_sum/@si->ec_count) and add it to @si->mean_ec.
97 static void commit_to_mean_value(struct ubi_scan_info *si)
99 si->ec_sum /= si->ec_count;
100 if (si->ec_sum % si->ec_count >= si->ec_count / 2)
102 si->mean_ec += si->ec_sum;
106 * validate_vid_hdr - check that volume identifier header is correct and
108 * @vid_hdr: the volume identifier header to check
109 * @sv: information about the volume this logical eraseblock belongs to
110 * @pnum: physical eraseblock number the VID header came from
112 * This function checks that data stored in @vid_hdr is consistent. Returns
113 * non-zero if an inconsistency was found and zero if not.
115 * Note, UBI does sanity check of everything it reads from the flash media.
116 * Most of the checks are done in the I/O unit. Here we check that the
117 * information in the VID header is consistent to the information in other VID
118 * headers of the same volume.
120 static int validate_vid_hdr(const struct ubi_vid_hdr *vid_hdr,
121 const struct ubi_scan_volume *sv, int pnum)
123 int vol_type = vid_hdr->vol_type;
124 int vol_id = ubi32_to_cpu(vid_hdr->vol_id);
125 int used_ebs = ubi32_to_cpu(vid_hdr->used_ebs);
126 int data_pad = ubi32_to_cpu(vid_hdr->data_pad);
128 if (sv->leb_count != 0) {
132 * This is not the first logical eraseblock belonging to this
133 * volume. Ensure that the data in its VID header is consistent
134 * to the data in previous logical eraseblock headers.
137 if (vol_id != sv->vol_id) {
138 dbg_err("inconsistent vol_id");
142 if (sv->vol_type == UBI_STATIC_VOLUME)
143 sv_vol_type = UBI_VID_STATIC;
145 sv_vol_type = UBI_VID_DYNAMIC;
147 if (vol_type != sv_vol_type) {
148 dbg_err("inconsistent vol_type");
152 if (used_ebs != sv->used_ebs) {
153 dbg_err("inconsistent used_ebs");
157 if (data_pad != sv->data_pad) {
158 dbg_err("inconsistent data_pad");
166 ubi_err("inconsistent VID header at PEB %d", pnum);
167 ubi_dbg_dump_vid_hdr(vid_hdr);
173 * add_volume - add volume to the scanning information.
174 * @si: scanning information
175 * @vol_id: ID of the volume to add
176 * @pnum: physical eraseblock number
177 * @vid_hdr: volume identifier header
179 * If the volume corresponding to the @vid_hdr logical eraseblock is already
180 * present in the scanning information, this function does nothing. Otherwise
181 * it adds corresponding volume to the scanning information. Returns a pointer
182 * to the scanning volume object in case of success and a negative error code
183 * in case of failure.
185 static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
187 const struct ubi_vid_hdr *vid_hdr)
189 struct ubi_scan_volume *sv;
190 struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
192 ubi_assert(vol_id == ubi32_to_cpu(vid_hdr->vol_id));
194 /* Walk the volume RB-tree to look if this volume is already present */
197 sv = rb_entry(parent, struct ubi_scan_volume, rb);
199 if (vol_id == sv->vol_id)
202 if (vol_id > sv->vol_id)
208 /* The volume is absent - add it */
209 sv = kmalloc(sizeof(struct ubi_scan_volume), GFP_KERNEL);
211 return ERR_PTR(-ENOMEM);
213 sv->highest_lnum = sv->leb_count = 0;
217 sv->used_ebs = ubi32_to_cpu(vid_hdr->used_ebs);
218 sv->data_pad = ubi32_to_cpu(vid_hdr->data_pad);
219 sv->compat = vid_hdr->compat;
220 sv->vol_type = vid_hdr->vol_type == UBI_VID_DYNAMIC ? UBI_DYNAMIC_VOLUME
222 if (vol_id > si->highest_vol_id)
223 si->highest_vol_id = vol_id;
225 rb_link_node(&sv->rb, parent, p);
226 rb_insert_color(&sv->rb, &si->volumes);
228 dbg_bld("added volume %d", vol_id);
233 * compare_lebs - find out which logical eraseblock is newer.
234 * @ubi: UBI device description object
235 * @seb: first logical eraseblock to compare
236 * @pnum: physical eraseblock number of the second logical eraseblock to
238 * @vid_hdr: volume identifier header of the second logical eraseblock
240 * This function compares 2 copies of a LEB and informs which one is newer. In
241 * case of success this function returns a positive value, in case of failure, a
242 * negative error code is returned. The success return codes use the following
244 * o bit 0 is cleared: the first PEB (described by @seb) is newer then the
245 * second PEB (described by @pnum and @vid_hdr);
246 * o bit 0 is set: the second PEB is newer;
247 * o bit 1 is cleared: no bit-flips were detected in the newer LEB;
248 * o bit 1 is set: bit-flips were detected in the newer LEB;
249 * o bit 2 is cleared: the older LEB is not corrupted;
250 * o bit 2 is set: the older LEB is corrupted.
252 static int compare_lebs(const struct ubi_device *ubi,
253 const struct ubi_scan_leb *seb, int pnum,
254 const struct ubi_vid_hdr *vid_hdr)
257 int len, err, second_is_newer, bitflips = 0, corrupted = 0;
258 uint32_t data_crc, crc;
259 struct ubi_vid_hdr *vidh = NULL;
260 unsigned long long sqnum2 = ubi64_to_cpu(vid_hdr->sqnum);
262 if (seb->sqnum == 0 && sqnum2 == 0) {
263 long long abs, v1 = seb->leb_ver, v2 = ubi32_to_cpu(vid_hdr->leb_ver);
266 * UBI constantly increases the logical eraseblock version
267 * number and it can overflow. Thus, we have to bear in mind
268 * that versions that are close to %0xFFFFFFFF are less then
269 * versions that are close to %0.
271 * The UBI WL unit guarantees that the number of pending tasks
272 * is not greater then %0x7FFFFFFF. So, if the difference
273 * between any two versions is greater or equivalent to
274 * %0x7FFFFFFF, there was an overflow and the logical
275 * eraseblock with lower version is actually newer then the one
276 * with higher version.
278 * FIXME: but this is anyway obsolete and will be removed at
282 dbg_bld("using old crappy leb_ver stuff");
288 if (abs < 0x7FFFFFFF)
289 /* Non-overflow situation */
290 second_is_newer = (v2 > v1);
292 second_is_newer = (v2 < v1);
294 /* Obviously the LEB with lower sequence counter is older */
295 second_is_newer = sqnum2 > seb->sqnum;
298 * Now we know which copy is newer. If the copy flag of the PEB with
299 * newer version is not set, then we just return, otherwise we have to
300 * check data CRC. For the second PEB we already have the VID header,
301 * for the first one - we'll need to re-read it from flash.
303 * FIXME: this may be optimized so that we wouldn't read twice.
306 if (second_is_newer) {
307 if (!vid_hdr->copy_flag) {
308 /* It is not a copy, so it is newer */
309 dbg_bld("second PEB %d is newer, copy_flag is unset",
316 vidh = ubi_zalloc_vid_hdr(ubi);
320 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0);
322 if (err == UBI_IO_BITFLIPS)
325 dbg_err("VID of PEB %d header is bad, but it "
326 "was OK earlier", pnum);
334 if (!vidh->copy_flag) {
335 /* It is not a copy, so it is newer */
336 dbg_bld("first PEB %d is newer, copy_flag is unset",
345 /* Read the data of the copy and check the CRC */
347 len = ubi32_to_cpu(vid_hdr->data_size);
348 buf = kmalloc(len, GFP_KERNEL);
354 err = ubi_io_read_data(ubi, buf, pnum, 0, len);
355 if (err && err != UBI_IO_BITFLIPS)
358 data_crc = ubi32_to_cpu(vid_hdr->data_crc);
359 crc = crc32(UBI_CRC32_INIT, buf, len);
360 if (crc != data_crc) {
361 dbg_bld("PEB %d CRC error: calculated %#08x, must be %#08x",
362 pnum, crc, data_crc);
365 second_is_newer = !second_is_newer;
367 dbg_bld("PEB %d CRC is OK", pnum);
372 ubi_free_vid_hdr(ubi, vidh);
375 dbg_bld("second PEB %d is newer, copy_flag is set", pnum);
377 dbg_bld("first PEB %d is newer, copy_flag is set", pnum);
379 return second_is_newer | (bitflips << 1) | (corrupted << 2);
384 ubi_free_vid_hdr(ubi, vidh);
390 * ubi_scan_add_used - add information about a physical eraseblock to the
391 * scanning information.
392 * @ubi: UBI device description object
393 * @si: scanning information
394 * @pnum: the physical eraseblock number
396 * @vid_hdr: the volume identifier header
397 * @bitflips: if bit-flips were detected when this physical eraseblock was read
399 * This function returns zero in case of success and a negative error code in
402 int ubi_scan_add_used(const struct ubi_device *ubi, struct ubi_scan_info *si,
403 int pnum, int ec, const struct ubi_vid_hdr *vid_hdr,
406 int err, vol_id, lnum;
408 unsigned long long sqnum;
409 struct ubi_scan_volume *sv;
410 struct ubi_scan_leb *seb;
411 struct rb_node **p, *parent = NULL;
413 vol_id = ubi32_to_cpu(vid_hdr->vol_id);
414 lnum = ubi32_to_cpu(vid_hdr->lnum);
415 sqnum = ubi64_to_cpu(vid_hdr->sqnum);
416 leb_ver = ubi32_to_cpu(vid_hdr->leb_ver);
418 dbg_bld("PEB %d, LEB %d:%d, EC %d, sqnum %llu, ver %u, bitflips %d",
419 pnum, vol_id, lnum, ec, sqnum, leb_ver, bitflips);
421 sv = add_volume(si, vol_id, pnum, vid_hdr);
426 * Walk the RB-tree of logical eraseblocks of volume @vol_id to look
427 * if this is the first instance of this logical eraseblock or not.
429 p = &sv->root.rb_node;
434 seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
435 if (lnum != seb->lnum) {
436 if (lnum < seb->lnum)
444 * There is already a physical eraseblock describing the same
445 * logical eraseblock present.
448 dbg_bld("this LEB already exists: PEB %d, sqnum %llu, "
449 "LEB ver %u, EC %d", seb->pnum, seb->sqnum,
450 seb->leb_ver, seb->ec);
453 * Make sure that the logical eraseblocks have different
454 * versions. Otherwise the image is bad.
456 if (seb->leb_ver == leb_ver && leb_ver != 0) {
457 ubi_err("two LEBs with same version %u", leb_ver);
458 ubi_dbg_dump_seb(seb, 0);
459 ubi_dbg_dump_vid_hdr(vid_hdr);
464 * Make sure that the logical eraseblocks have different
465 * sequence numbers. Otherwise the image is bad.
467 * FIXME: remove 'sqnum != 0' check when leb_ver is removed.
469 if (seb->sqnum == sqnum && sqnum != 0) {
470 ubi_err("two LEBs with same sequence number %llu",
472 ubi_dbg_dump_seb(seb, 0);
473 ubi_dbg_dump_vid_hdr(vid_hdr);
478 * Now we have to drop the older one and preserve the newer
481 cmp_res = compare_lebs(ubi, seb, pnum, vid_hdr);
487 * This logical eraseblock is newer then the one
490 err = validate_vid_hdr(vid_hdr, sv, pnum);
495 err = ubi_scan_add_to_list(si, seb->pnum,
498 err = ubi_scan_add_to_list(si, seb->pnum,
499 seb->ec, &si->erase);
505 seb->scrub = ((cmp_res & 2) || bitflips);
507 seb->leb_ver = leb_ver;
509 if (sv->highest_lnum == lnum)
511 ubi32_to_cpu(vid_hdr->data_size);
516 * This logical eraseblock is older then the one found
520 return ubi_scan_add_to_list(si, pnum, ec,
523 return ubi_scan_add_to_list(si, pnum, ec,
529 * We've met this logical eraseblock for the first time, add it to the
530 * scanning information.
533 err = validate_vid_hdr(vid_hdr, sv, pnum);
537 seb = kmalloc(sizeof(struct ubi_scan_leb), GFP_KERNEL);
545 seb->scrub = bitflips;
546 seb->leb_ver = leb_ver;
548 if (sv->highest_lnum <= lnum) {
549 sv->highest_lnum = lnum;
550 sv->last_data_size = ubi32_to_cpu(vid_hdr->data_size);
553 if (si->max_sqnum < sqnum)
554 si->max_sqnum = sqnum;
557 rb_link_node(&seb->u.rb, parent, p);
558 rb_insert_color(&seb->u.rb, &sv->root);
563 * ubi_scan_find_sv - find information about a particular volume in the
564 * scanning information.
565 * @si: scanning information
566 * @vol_id: the requested volume ID
568 * This function returns a pointer to the volume description or %NULL if there
569 * are no data about this volume in the scanning information.
571 struct ubi_scan_volume *ubi_scan_find_sv(const struct ubi_scan_info *si,
574 struct ubi_scan_volume *sv;
575 struct rb_node *p = si->volumes.rb_node;
578 sv = rb_entry(p, struct ubi_scan_volume, rb);
580 if (vol_id == sv->vol_id)
583 if (vol_id > sv->vol_id)
593 * ubi_scan_find_seb - find information about a particular logical
594 * eraseblock in the volume scanning information.
595 * @sv: a pointer to the volume scanning information
596 * @lnum: the requested logical eraseblock
598 * This function returns a pointer to the scanning logical eraseblock or %NULL
599 * if there are no data about it in the scanning volume information.
601 struct ubi_scan_leb *ubi_scan_find_seb(const struct ubi_scan_volume *sv,
604 struct ubi_scan_leb *seb;
605 struct rb_node *p = sv->root.rb_node;
608 seb = rb_entry(p, struct ubi_scan_leb, u.rb);
610 if (lnum == seb->lnum)
613 if (lnum > seb->lnum)
623 * ubi_scan_rm_volume - delete scanning information about a volume.
624 * @si: scanning information
625 * @sv: the volume scanning information to delete
627 void ubi_scan_rm_volume(struct ubi_scan_info *si, struct ubi_scan_volume *sv)
630 struct ubi_scan_leb *seb;
632 dbg_bld("remove scanning information about volume %d", sv->vol_id);
634 while ((rb = rb_first(&sv->root))) {
635 seb = rb_entry(rb, struct ubi_scan_leb, u.rb);
636 rb_erase(&seb->u.rb, &sv->root);
637 list_add_tail(&seb->u.list, &si->erase);
640 rb_erase(&sv->rb, &si->volumes);
646 * ubi_scan_erase_peb - erase a physical eraseblock.
647 * @ubi: UBI device description object
648 * @si: scanning information
649 * @pnum: physical eraseblock number to erase;
650 * @ec: erase counter value to write (%UBI_SCAN_UNKNOWN_EC if it is unknown)
652 * This function erases physical eraseblock 'pnum', and writes the erase
653 * counter header to it. This function should only be used on UBI device
654 * initialization stages, when the EBA unit had not been yet initialized. This
655 * function returns zero in case of success and a negative error code in case
658 int ubi_scan_erase_peb(const struct ubi_device *ubi,
659 const struct ubi_scan_info *si, int pnum, int ec)
662 struct ubi_ec_hdr *ec_hdr;
664 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
668 if ((long long)ec >= UBI_MAX_ERASECOUNTER) {
670 * Erase counter overflow. Upgrade UBI and use 64-bit
671 * erase counters internally.
673 ubi_err("erase counter overflow at PEB %d, EC %d", pnum, ec);
677 ec_hdr->ec = cpu_to_ubi64(ec);
679 err = ubi_io_sync_erase(ubi, pnum, 0);
683 err = ubi_io_write_ec_hdr(ubi, pnum, ec_hdr);
691 * ubi_scan_get_free_peb - get a free physical eraseblock.
692 * @ubi: UBI device description object
693 * @si: scanning information
695 * This function returns a free physical eraseblock. It is supposed to be
696 * called on the UBI initialization stages when the wear-leveling unit is not
697 * initialized yet. This function picks a physical eraseblocks from one of the
698 * lists, writes the EC header if it is needed, and removes it from the list.
700 * This function returns scanning physical eraseblock information in case of
701 * success and an error code in case of failure.
703 struct ubi_scan_leb *ubi_scan_get_free_peb(const struct ubi_device *ubi,
704 struct ubi_scan_info *si)
707 struct ubi_scan_leb *seb;
709 if (!list_empty(&si->free)) {
710 seb = list_entry(si->free.next, struct ubi_scan_leb, u.list);
711 list_del(&seb->u.list);
712 dbg_bld("return free PEB %d, EC %d", seb->pnum, seb->ec);
716 for (i = 0; i < 2; i++) {
717 struct list_head *head;
718 struct ubi_scan_leb *tmp_seb;
726 * We try to erase the first physical eraseblock from the @head
727 * list and pick it if we succeed, or try to erase the
728 * next one if not. And so forth. We don't want to take care
729 * about bad eraseblocks here - they'll be handled later.
731 list_for_each_entry_safe(seb, tmp_seb, head, u.list) {
732 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
733 seb->ec = si->mean_ec;
735 err = ubi_scan_erase_peb(ubi, si, seb->pnum, seb->ec+1);
740 list_del(&seb->u.list);
741 dbg_bld("return PEB %d, EC %d", seb->pnum, seb->ec);
746 ubi_err("no eraseblocks found");
747 return ERR_PTR(-ENOSPC);
751 * process_eb - read UBI headers, check them and add corresponding data
752 * to the scanning information.
753 * @ubi: UBI device description object
754 * @si: scanning information
755 * @pnum: the physical eraseblock number
757 * This function returns a zero if the physical eraseblock was succesfully
758 * handled and a negative error code in case of failure.
760 static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si, int pnum)
763 int err, bitflips = 0, vol_id, ec_corr = 0;
765 dbg_bld("scan PEB %d", pnum);
767 /* Skip bad physical eraseblocks */
768 err = ubi_io_is_bad(ubi, pnum);
773 * FIXME: this is actually duty of the I/O unit to initialize
774 * this, but MTD does not provide enough information.
776 si->bad_peb_count += 1;
780 err = ubi_io_read_ec_hdr(ubi, pnum, ech, 0);
783 else if (err == UBI_IO_BITFLIPS)
785 else if (err == UBI_IO_PEB_EMPTY)
786 return ubi_scan_add_to_list(si, pnum, UBI_SCAN_UNKNOWN_EC,
788 else if (err == UBI_IO_BAD_EC_HDR) {
790 * We have to also look at the VID header, possibly it is not
791 * corrupted. Set %bitflips flag in order to make this PEB be
792 * moved and EC be re-created.
795 ec = UBI_SCAN_UNKNOWN_EC;
802 /* Make sure UBI version is OK */
803 if (ech->version != UBI_VERSION) {
804 ubi_err("this UBI version is %d, image version is %d",
805 UBI_VERSION, (int)ech->version);
809 ec = ubi64_to_cpu(ech->ec);
810 if (ec > UBI_MAX_ERASECOUNTER) {
812 * Erase counter overflow. The EC headers have 64 bits
813 * reserved, but we anyway make use of only 31 bit
814 * values, as this seems to be enough for any existing
815 * flash. Upgrade UBI and use 64-bit erase counters
818 ubi_err("erase counter overflow, max is %d",
819 UBI_MAX_ERASECOUNTER);
820 ubi_dbg_dump_ec_hdr(ech);
825 /* OK, we've done with the EC header, let's look at the VID header */
827 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0);
830 else if (err == UBI_IO_BITFLIPS)
832 else if (err == UBI_IO_BAD_VID_HDR ||
833 (err == UBI_IO_PEB_FREE && ec_corr)) {
834 /* VID header is corrupted */
835 err = ubi_scan_add_to_list(si, pnum, ec, &si->corr);
839 } else if (err == UBI_IO_PEB_FREE) {
840 /* No VID header - the physical eraseblock is free */
841 err = ubi_scan_add_to_list(si, pnum, ec, &si->free);
847 vol_id = ubi32_to_cpu(vidh->vol_id);
848 if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOL_ID) {
849 int lnum = ubi32_to_cpu(vidh->lnum);
851 /* Unsupported internal volume */
852 switch (vidh->compat) {
853 case UBI_COMPAT_DELETE:
854 ubi_msg("\"delete\" compatible internal volume %d:%d"
855 " found, remove it", vol_id, lnum);
856 err = ubi_scan_add_to_list(si, pnum, ec, &si->corr);
862 ubi_msg("read-only compatible internal volume %d:%d"
863 " found, switch to read-only mode",
868 case UBI_COMPAT_PRESERVE:
869 ubi_msg("\"preserve\" compatible internal volume %d:%d"
870 " found", vol_id, lnum);
871 err = ubi_scan_add_to_list(si, pnum, ec, &si->alien);
874 si->alien_peb_count += 1;
877 case UBI_COMPAT_REJECT:
878 ubi_err("incompatible internal volume %d:%d found",
884 /* Both UBI headers seem to be fine */
885 err = ubi_scan_add_used(ubi, si, pnum, ec, vidh, bitflips);
891 if (si->ec_sum + ec < ec) {
892 commit_to_mean_value(si);
910 * ubi_scan - scan an MTD device.
911 * @ubi: UBI device description object
913 * This function does full scanning of an MTD device and returns complete
914 * information about it. In case of failure, an error code is returned.
916 struct ubi_scan_info *ubi_scan(struct ubi_device *ubi)
919 struct rb_node *rb1, *rb2;
920 struct ubi_scan_volume *sv;
921 struct ubi_scan_leb *seb;
922 struct ubi_scan_info *si;
924 si = kzalloc(sizeof(struct ubi_scan_info), GFP_KERNEL);
926 return ERR_PTR(-ENOMEM);
928 INIT_LIST_HEAD(&si->corr);
929 INIT_LIST_HEAD(&si->free);
930 INIT_LIST_HEAD(&si->erase);
931 INIT_LIST_HEAD(&si->alien);
932 si->volumes = RB_ROOT;
936 ech = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
940 vidh = ubi_zalloc_vid_hdr(ubi);
944 for (pnum = 0; pnum < ubi->peb_count; pnum++) {
947 dbg_msg("process PEB %d", pnum);
948 err = process_eb(ubi, si, pnum);
953 dbg_msg("scanning is finished");
955 /* Finish mean erase counter calculations */
957 commit_to_mean_value(si);
960 ubi_msg("empty MTD device detected");
963 * In case of unknown erase counter we use the mean erase counter
966 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) {
967 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb)
968 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
969 seb->ec = si->mean_ec;
972 list_for_each_entry(seb, &si->free, u.list) {
973 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
974 seb->ec = si->mean_ec;
977 list_for_each_entry(seb, &si->corr, u.list)
978 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
979 seb->ec = si->mean_ec;
981 list_for_each_entry(seb, &si->erase, u.list)
982 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
983 seb->ec = si->mean_ec;
985 err = paranoid_check_si(ubi, si);
992 ubi_free_vid_hdr(ubi, vidh);
998 ubi_free_vid_hdr(ubi, vidh);
1002 ubi_scan_destroy_si(si);
1003 return ERR_PTR(err);
1007 * destroy_sv - free the scanning volume information
1008 * @sv: scanning volume information
1010 * This function destroys the volume RB-tree (@sv->root) and the scanning
1011 * volume information.
1013 static void destroy_sv(struct ubi_scan_volume *sv)
1015 struct ubi_scan_leb *seb;
1016 struct rb_node *this = sv->root.rb_node;
1020 this = this->rb_left;
1021 else if (this->rb_right)
1022 this = this->rb_right;
1024 seb = rb_entry(this, struct ubi_scan_leb, u.rb);
1025 this = rb_parent(this);
1027 if (this->rb_left == &seb->u.rb)
1028 this->rb_left = NULL;
1030 this->rb_right = NULL;
1040 * ubi_scan_destroy_si - destroy scanning information.
1041 * @si: scanning information
1043 void ubi_scan_destroy_si(struct ubi_scan_info *si)
1045 struct ubi_scan_leb *seb, *seb_tmp;
1046 struct ubi_scan_volume *sv;
1049 list_for_each_entry_safe(seb, seb_tmp, &si->alien, u.list) {
1050 list_del(&seb->u.list);
1053 list_for_each_entry_safe(seb, seb_tmp, &si->erase, u.list) {
1054 list_del(&seb->u.list);
1057 list_for_each_entry_safe(seb, seb_tmp, &si->corr, u.list) {
1058 list_del(&seb->u.list);
1061 list_for_each_entry_safe(seb, seb_tmp, &si->free, u.list) {
1062 list_del(&seb->u.list);
1066 /* Destroy the volume RB-tree */
1067 rb = si->volumes.rb_node;
1071 else if (rb->rb_right)
1074 sv = rb_entry(rb, struct ubi_scan_volume, rb);
1078 if (rb->rb_left == &sv->rb)
1081 rb->rb_right = NULL;
1091 #ifdef CONFIG_MTD_UBI_DEBUG_PARANOID
1094 * paranoid_check_si - check if the scanning information is correct and
1096 * @ubi: UBI device description object
1097 * @si: scanning information
1099 * This function returns zero if the scanning information is all right, %1 if
1100 * not and a negative error code if an error occurred.
1102 static int paranoid_check_si(const struct ubi_device *ubi,
1103 struct ubi_scan_info *si)
1105 int pnum, err, vols_found = 0;
1106 struct rb_node *rb1, *rb2;
1107 struct ubi_scan_volume *sv;
1108 struct ubi_scan_leb *seb, *last_seb;
1112 * At first, check that scanning information is ok.
1114 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) {
1122 ubi_err("bad is_empty flag");
1126 if (sv->vol_id < 0 || sv->highest_lnum < 0 ||
1127 sv->leb_count < 0 || sv->vol_type < 0 || sv->used_ebs < 0 ||
1128 sv->data_pad < 0 || sv->last_data_size < 0) {
1129 ubi_err("negative values");
1133 if (sv->vol_id >= UBI_MAX_VOLUMES &&
1134 sv->vol_id < UBI_INTERNAL_VOL_START) {
1135 ubi_err("bad vol_id");
1139 if (sv->vol_id > si->highest_vol_id) {
1140 ubi_err("highest_vol_id is %d, but vol_id %d is there",
1141 si->highest_vol_id, sv->vol_id);
1145 if (sv->vol_type != UBI_DYNAMIC_VOLUME &&
1146 sv->vol_type != UBI_STATIC_VOLUME) {
1147 ubi_err("bad vol_type");
1151 if (sv->data_pad > ubi->leb_size / 2) {
1152 ubi_err("bad data_pad");
1157 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) {
1163 if (seb->pnum < 0 || seb->ec < 0) {
1164 ubi_err("negative values");
1168 if (seb->ec < si->min_ec) {
1169 ubi_err("bad si->min_ec (%d), %d found",
1170 si->min_ec, seb->ec);
1174 if (seb->ec > si->max_ec) {
1175 ubi_err("bad si->max_ec (%d), %d found",
1176 si->max_ec, seb->ec);
1180 if (seb->pnum >= ubi->peb_count) {
1181 ubi_err("too high PEB number %d, total PEBs %d",
1182 seb->pnum, ubi->peb_count);
1186 if (sv->vol_type == UBI_STATIC_VOLUME) {
1187 if (seb->lnum >= sv->used_ebs) {
1188 ubi_err("bad lnum or used_ebs");
1192 if (sv->used_ebs != 0) {
1193 ubi_err("non-zero used_ebs");
1198 if (seb->lnum > sv->highest_lnum) {
1199 ubi_err("incorrect highest_lnum or lnum");
1204 if (sv->leb_count != leb_count) {
1205 ubi_err("bad leb_count, %d objects in the tree",
1215 if (seb->lnum != sv->highest_lnum) {
1216 ubi_err("bad highest_lnum");
1221 if (vols_found != si->vols_found) {
1222 ubi_err("bad si->vols_found %d, should be %d",
1223 si->vols_found, vols_found);
1227 /* Check that scanning information is correct */
1228 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) {
1230 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) {
1237 err = ubi_io_read_vid_hdr(ubi, seb->pnum, vidh, 1);
1238 if (err && err != UBI_IO_BITFLIPS) {
1239 ubi_err("VID header is not OK (%d)", err);
1245 vol_type = vidh->vol_type == UBI_VID_DYNAMIC ?
1246 UBI_DYNAMIC_VOLUME : UBI_STATIC_VOLUME;
1247 if (sv->vol_type != vol_type) {
1248 ubi_err("bad vol_type");
1252 if (seb->sqnum != ubi64_to_cpu(vidh->sqnum)) {
1253 ubi_err("bad sqnum %llu", seb->sqnum);
1257 if (sv->vol_id != ubi32_to_cpu(vidh->vol_id)) {
1258 ubi_err("bad vol_id %d", sv->vol_id);
1262 if (sv->compat != vidh->compat) {
1263 ubi_err("bad compat %d", vidh->compat);
1267 if (seb->lnum != ubi32_to_cpu(vidh->lnum)) {
1268 ubi_err("bad lnum %d", seb->lnum);
1272 if (sv->used_ebs != ubi32_to_cpu(vidh->used_ebs)) {
1273 ubi_err("bad used_ebs %d", sv->used_ebs);
1277 if (sv->data_pad != ubi32_to_cpu(vidh->data_pad)) {
1278 ubi_err("bad data_pad %d", sv->data_pad);
1282 if (seb->leb_ver != ubi32_to_cpu(vidh->leb_ver)) {
1283 ubi_err("bad leb_ver %u", seb->leb_ver);
1291 if (sv->highest_lnum != ubi32_to_cpu(vidh->lnum)) {
1292 ubi_err("bad highest_lnum %d", sv->highest_lnum);
1296 if (sv->last_data_size != ubi32_to_cpu(vidh->data_size)) {
1297 ubi_err("bad last_data_size %d", sv->last_data_size);
1303 * Make sure that all the physical eraseblocks are in one of the lists
1306 buf = kmalloc(ubi->peb_count, GFP_KERNEL);
1310 memset(buf, 1, ubi->peb_count);
1311 for (pnum = 0; pnum < ubi->peb_count; pnum++) {
1312 err = ubi_io_is_bad(ubi, pnum);
1321 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb)
1322 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb)
1325 list_for_each_entry(seb, &si->free, u.list)
1328 list_for_each_entry(seb, &si->corr, u.list)
1331 list_for_each_entry(seb, &si->erase, u.list)
1334 list_for_each_entry(seb, &si->alien, u.list)
1338 for (pnum = 0; pnum < ubi->peb_count; pnum++)
1340 ubi_err("PEB %d is not referred", pnum);
1350 ubi_err("bad scanning information about LEB %d", seb->lnum);
1351 ubi_dbg_dump_seb(seb, 0);
1352 ubi_dbg_dump_sv(sv);
1356 ubi_err("bad scanning information about volume %d", sv->vol_id);
1357 ubi_dbg_dump_sv(sv);
1361 ubi_err("bad scanning information about volume %d", sv->vol_id);
1362 ubi_dbg_dump_sv(sv);
1363 ubi_dbg_dump_vid_hdr(vidh);
1366 ubi_dbg_dump_stack();
1370 #endif /* CONFIG_MTD_UBI_DEBUG_PARANOID */