aboutsummaryrefslogtreecommitdiffstats
path: root/drivers/mtd/ubi/scan.c
diff options
context:
space:
mode:
Diffstat (limited to 'drivers/mtd/ubi/scan.c')
-rw-r--r--drivers/mtd/ubi/scan.c1368
1 files changed, 1368 insertions, 0 deletions
diff --git a/drivers/mtd/ubi/scan.c b/drivers/mtd/ubi/scan.c
new file mode 100644
index 000000000000..473f3200b868
--- /dev/null
+++ b/drivers/mtd/ubi/scan.c
@@ -0,0 +1,1368 @@
1/*
2 * Copyright (c) International Business Machines Corp., 2006
3 *
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.
8 *
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.
13 *
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
17 *
18 * Author: Artem Bityutskiy (Битюцкий Артём)
19 */
20
21/*
22 * UBI scanning unit.
23 *
24 * This unit is responsible for scanning the flash media, checking UBI
25 * headers and providing complete information about the UBI flash image.
26 *
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.
31 *
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.
37 *
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.
41 */
42
43#include <linux/err.h>
44#include <linux/crc32.h>
45#include "ubi.h"
46
47#ifdef CONFIG_MTD_UBI_DEBUG_PARANOID
48static int paranoid_check_si(const struct ubi_device *ubi,
49 struct ubi_scan_info *si);
50#else
51#define paranoid_check_si(ubi, si) 0
52#endif
53
54/* Temporary variables used during scanning */
55static struct ubi_ec_hdr *ech;
56static struct ubi_vid_hdr *vidh;
57
58int ubi_scan_add_to_list(struct ubi_scan_info *si, int pnum, int ec,
59 struct list_head *list)
60{
61 struct ubi_scan_leb *seb;
62
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);
71 else
72 BUG();
73
74 seb = kmalloc(sizeof(struct ubi_scan_leb), GFP_KERNEL);
75 if (!seb)
76 return -ENOMEM;
77
78 seb->pnum = pnum;
79 seb->ec = ec;
80 list_add_tail(&seb->u.list, list);
81 return 0;
82}
83
84/**
85 * commit_to_mean_value - commit intermediate results to the final mean erase
86 * counter value.
87 * @si: scanning information
88 *
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.
96 */
97static void commit_to_mean_value(struct ubi_scan_info *si)
98{
99 si->ec_sum /= si->ec_count;
100 if (si->ec_sum % si->ec_count >= si->ec_count / 2)
101 si->mean_ec += 1;
102 si->mean_ec += si->ec_sum;
103}
104
105/**
106 * validate_vid_hdr - check that volume identifier header is correct and
107 * consistent.
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
111 *
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.
114 *
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.
119 */
120static int validate_vid_hdr(const struct ubi_vid_hdr *vid_hdr,
121 const struct ubi_scan_volume *sv, int pnum)
122{
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);
127
128 if (sv->leb_count != 0) {
129 int sv_vol_type;
130
131 /*
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.
135 */
136
137 if (vol_id != sv->vol_id) {
138 dbg_err("inconsistent vol_id");
139 goto bad;
140 }
141
142 if (sv->vol_type == UBI_STATIC_VOLUME)
143 sv_vol_type = UBI_VID_STATIC;
144 else
145 sv_vol_type = UBI_VID_DYNAMIC;
146
147 if (vol_type != sv_vol_type) {
148 dbg_err("inconsistent vol_type");
149 goto bad;
150 }
151
152 if (used_ebs != sv->used_ebs) {
153 dbg_err("inconsistent used_ebs");
154 goto bad;
155 }
156
157 if (data_pad != sv->data_pad) {
158 dbg_err("inconsistent data_pad");
159 goto bad;
160 }
161 }
162
163 return 0;
164
165bad:
166 ubi_err("inconsistent VID header at PEB %d", pnum);
167 ubi_dbg_dump_vid_hdr(vid_hdr);
168 ubi_dbg_dump_sv(sv);
169 return -EINVAL;
170}
171
172/**
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
178 *
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.
184 */
185static struct ubi_scan_volume *add_volume(struct ubi_scan_info *si, int vol_id,
186 int pnum,
187 const struct ubi_vid_hdr *vid_hdr)
188{
189 struct ubi_scan_volume *sv;
190 struct rb_node **p = &si->volumes.rb_node, *parent = NULL;
191
192 ubi_assert(vol_id == ubi32_to_cpu(vid_hdr->vol_id));
193
194 /* Walk the volume RB-tree to look if this volume is already present */
195 while (*p) {
196 parent = *p;
197 sv = rb_entry(parent, struct ubi_scan_volume, rb);
198
199 if (vol_id == sv->vol_id)
200 return sv;
201
202 if (vol_id > sv->vol_id)
203 p = &(*p)->rb_left;
204 else
205 p = &(*p)->rb_right;
206 }
207
208 /* The volume is absent - add it */
209 sv = kmalloc(sizeof(struct ubi_scan_volume), GFP_KERNEL);
210 if (!sv)
211 return ERR_PTR(-ENOMEM);
212
213 sv->highest_lnum = sv->leb_count = 0;
214 si->max_sqnum = 0;
215 sv->vol_id = vol_id;
216 sv->root = RB_ROOT;
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
221 : UBI_STATIC_VOLUME;
222 if (vol_id > si->highest_vol_id)
223 si->highest_vol_id = vol_id;
224
225 rb_link_node(&sv->rb, parent, p);
226 rb_insert_color(&sv->rb, &si->volumes);
227 si->vols_found += 1;
228 dbg_bld("added volume %d", vol_id);
229 return sv;
230}
231
232/**
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
237 * compare
238 * @vid_hdr: volume identifier header of the second logical eraseblock
239 *
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
243 * bits:
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.
251 */
252static 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)
255{
256 void *buf;
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);
261
262 if (seb->sqnum == 0 && sqnum2 == 0) {
263 long long abs, v1 = seb->leb_ver, v2 = ubi32_to_cpu(vid_hdr->leb_ver);
264
265 /*
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.
270 *
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.
277 *
278 * FIXME: but this is anyway obsolete and will be removed at
279 * some point.
280 */
281
282 dbg_bld("using old crappy leb_ver stuff");
283
284 abs = v1 - v2;
285 if (abs < 0)
286 abs = -abs;
287
288 if (abs < 0x7FFFFFFF)
289 /* Non-overflow situation */
290 second_is_newer = (v2 > v1);
291 else
292 second_is_newer = (v2 < v1);
293 } else
294 /* Obviously the LEB with lower sequence counter is older */
295 second_is_newer = sqnum2 > seb->sqnum;
296
297 /*
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.
302 *
303 * FIXME: this may be optimized so that we wouldn't read twice.
304 */
305
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",
310 pnum);
311 return 1;
312 }
313 } else {
314 pnum = seb->pnum;
315
316 vidh = ubi_zalloc_vid_hdr(ubi);
317 if (!vidh)
318 return -ENOMEM;
319
320 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0);
321 if (err) {
322 if (err == UBI_IO_BITFLIPS)
323 bitflips = 1;
324 else {
325 dbg_err("VID of PEB %d header is bad, but it "
326 "was OK earlier", pnum);
327 if (err > 0)
328 err = -EIO;
329
330 goto out_free_vidh;
331 }
332 }
333
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",
337 pnum);
338 err = bitflips << 1;
339 goto out_free_vidh;
340 }
341
342 vid_hdr = vidh;
343 }
344
345 /* Read the data of the copy and check the CRC */
346
347 len = ubi32_to_cpu(vid_hdr->data_size);
348 buf = kmalloc(len, GFP_KERNEL);
349 if (!buf) {
350 err = -ENOMEM;
351 goto out_free_vidh;
352 }
353
354 err = ubi_io_read_data(ubi, buf, pnum, 0, len);
355 if (err && err != UBI_IO_BITFLIPS)
356 goto out_free_buf;
357
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);
363 corrupted = 1;
364 bitflips = 0;
365 second_is_newer = !second_is_newer;
366 } else {
367 dbg_bld("PEB %d CRC is OK", pnum);
368 bitflips = !!err;
369 }
370
371 kfree(buf);
372 ubi_free_vid_hdr(ubi, vidh);
373
374 if (second_is_newer)
375 dbg_bld("second PEB %d is newer, copy_flag is set", pnum);
376 else
377 dbg_bld("first PEB %d is newer, copy_flag is set", pnum);
378
379 return second_is_newer | (bitflips << 1) | (corrupted << 2);
380
381out_free_buf:
382 kfree(buf);
383out_free_vidh:
384 ubi_free_vid_hdr(ubi, vidh);
385 ubi_assert(err < 0);
386 return err;
387}
388
389/**
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
395 * @ec: erase counter
396 * @vid_hdr: the volume identifier header
397 * @bitflips: if bit-flips were detected when this physical eraseblock was read
398 *
399 * This function returns zero in case of success and a negative error code in
400 * case of failure.
401 */
402int 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,
404 int bitflips)
405{
406 int err, vol_id, lnum;
407 uint32_t leb_ver;
408 unsigned long long sqnum;
409 struct ubi_scan_volume *sv;
410 struct ubi_scan_leb *seb;
411 struct rb_node **p, *parent = NULL;
412
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);
417
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);
420
421 sv = add_volume(si, vol_id, pnum, vid_hdr);
422 if (IS_ERR(sv) < 0)
423 return PTR_ERR(sv);
424
425 /*
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.
428 */
429 p = &sv->root.rb_node;
430 while (*p) {
431 int cmp_res;
432
433 parent = *p;
434 seb = rb_entry(parent, struct ubi_scan_leb, u.rb);
435 if (lnum != seb->lnum) {
436 if (lnum < seb->lnum)
437 p = &(*p)->rb_left;
438 else
439 p = &(*p)->rb_right;
440 continue;
441 }
442
443 /*
444 * There is already a physical eraseblock describing the same
445 * logical eraseblock present.
446 */
447
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);
451
452 /*
453 * Make sure that the logical eraseblocks have different
454 * versions. Otherwise the image is bad.
455 */
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);
460 return -EINVAL;
461 }
462
463 /*
464 * Make sure that the logical eraseblocks have different
465 * sequence numbers. Otherwise the image is bad.
466 *
467 * FIXME: remove 'sqnum != 0' check when leb_ver is removed.
468 */
469 if (seb->sqnum == sqnum && sqnum != 0) {
470 ubi_err("two LEBs with same sequence number %llu",
471 sqnum);
472 ubi_dbg_dump_seb(seb, 0);
473 ubi_dbg_dump_vid_hdr(vid_hdr);
474 return -EINVAL;
475 }
476
477 /*
478 * Now we have to drop the older one and preserve the newer
479 * one.
480 */
481 cmp_res = compare_lebs(ubi, seb, pnum, vid_hdr);
482 if (cmp_res < 0)
483 return cmp_res;
484
485 if (cmp_res & 1) {
486 /*
487 * This logical eraseblock is newer then the one
488 * found earlier.
489 */
490 err = validate_vid_hdr(vid_hdr, sv, pnum);
491 if (err)
492 return err;
493
494 if (cmp_res & 4)
495 err = ubi_scan_add_to_list(si, seb->pnum,
496 seb->ec, &si->corr);
497 else
498 err = ubi_scan_add_to_list(si, seb->pnum,
499 seb->ec, &si->erase);
500 if (err)
501 return err;
502
503 seb->ec = ec;
504 seb->pnum = pnum;
505 seb->scrub = ((cmp_res & 2) || bitflips);
506 seb->sqnum = sqnum;
507 seb->leb_ver = leb_ver;
508
509 if (sv->highest_lnum == lnum)
510 sv->last_data_size =
511 ubi32_to_cpu(vid_hdr->data_size);
512
513 return 0;
514 } else {
515 /*
516 * This logical eraseblock is older then the one found
517 * previously.
518 */
519 if (cmp_res & 4)
520 return ubi_scan_add_to_list(si, pnum, ec,
521 &si->corr);
522 else
523 return ubi_scan_add_to_list(si, pnum, ec,
524 &si->erase);
525 }
526 }
527
528 /*
529 * We've met this logical eraseblock for the first time, add it to the
530 * scanning information.
531 */
532
533 err = validate_vid_hdr(vid_hdr, sv, pnum);
534 if (err)
535 return err;
536
537 seb = kmalloc(sizeof(struct ubi_scan_leb), GFP_KERNEL);
538 if (!seb)
539 return -ENOMEM;
540
541 seb->ec = ec;
542 seb->pnum = pnum;
543 seb->lnum = lnum;
544 seb->sqnum = sqnum;
545 seb->scrub = bitflips;
546 seb->leb_ver = leb_ver;
547
548 if (sv->highest_lnum <= lnum) {
549 sv->highest_lnum = lnum;
550 sv->last_data_size = ubi32_to_cpu(vid_hdr->data_size);
551 }
552
553 if (si->max_sqnum < sqnum)
554 si->max_sqnum = sqnum;
555
556 sv->leb_count += 1;
557 rb_link_node(&seb->u.rb, parent, p);
558 rb_insert_color(&seb->u.rb, &sv->root);
559 return 0;
560}
561
562/**
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
567 *
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.
570 */
571struct ubi_scan_volume *ubi_scan_find_sv(const struct ubi_scan_info *si,
572 int vol_id)
573{
574 struct ubi_scan_volume *sv;
575 struct rb_node *p = si->volumes.rb_node;
576
577 while (p) {
578 sv = rb_entry(p, struct ubi_scan_volume, rb);
579
580 if (vol_id == sv->vol_id)
581 return sv;
582
583 if (vol_id > sv->vol_id)
584 p = p->rb_left;
585 else
586 p = p->rb_right;
587 }
588
589 return NULL;
590}
591
592/**
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
597 *
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.
600 */
601struct ubi_scan_leb *ubi_scan_find_seb(const struct ubi_scan_volume *sv,
602 int lnum)
603{
604 struct ubi_scan_leb *seb;
605 struct rb_node *p = sv->root.rb_node;
606
607 while (p) {
608 seb = rb_entry(p, struct ubi_scan_leb, u.rb);
609
610 if (lnum == seb->lnum)
611 return seb;
612
613 if (lnum > seb->lnum)
614 p = p->rb_left;
615 else
616 p = p->rb_right;
617 }
618
619 return NULL;
620}
621
622/**
623 * ubi_scan_rm_volume - delete scanning information about a volume.
624 * @si: scanning information
625 * @sv: the volume scanning information to delete
626 */
627void ubi_scan_rm_volume(struct ubi_scan_info *si, struct ubi_scan_volume *sv)
628{
629 struct rb_node *rb;
630 struct ubi_scan_leb *seb;
631
632 dbg_bld("remove scanning information about volume %d", sv->vol_id);
633
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);
638 }
639
640 rb_erase(&sv->rb, &si->volumes);
641 kfree(sv);
642 si->vols_found -= 1;
643}
644
645/**
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)
651 *
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
656 * of failure.
657 */
658int ubi_scan_erase_peb(const struct ubi_device *ubi,
659 const struct ubi_scan_info *si, int pnum, int ec)
660{
661 int err;
662 struct ubi_ec_hdr *ec_hdr;
663
664 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
665 if (!ec_hdr)
666 return -ENOMEM;
667
668 if ((long long)ec >= UBI_MAX_ERASECOUNTER) {
669 /*
670 * Erase counter overflow. Upgrade UBI and use 64-bit
671 * erase counters internally.
672 */
673 ubi_err("erase counter overflow at PEB %d, EC %d", pnum, ec);
674 return -EINVAL;
675 }
676
677 ec_hdr->ec = cpu_to_ubi64(ec);
678
679 err = ubi_io_sync_erase(ubi, pnum, 0);
680 if (err < 0)
681 goto out_free;
682
683 err = ubi_io_write_ec_hdr(ubi, pnum, ec_hdr);
684
685out_free:
686 kfree(ec_hdr);
687 return err;
688}
689
690/**
691 * ubi_scan_get_free_peb - get a free physical eraseblock.
692 * @ubi: UBI device description object
693 * @si: scanning information
694 *
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.
699 *
700 * This function returns scanning physical eraseblock information in case of
701 * success and an error code in case of failure.
702 */
703struct ubi_scan_leb *ubi_scan_get_free_peb(const struct ubi_device *ubi,
704 struct ubi_scan_info *si)
705{
706 int err = 0, i;
707 struct ubi_scan_leb *seb;
708
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);
713 return seb;
714 }
715
716 for (i = 0; i < 2; i++) {
717 struct list_head *head;
718 struct ubi_scan_leb *tmp_seb;
719
720 if (i == 0)
721 head = &si->erase;
722 else
723 head = &si->corr;
724
725 /*
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.
730 */
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;
734
735 err = ubi_scan_erase_peb(ubi, si, seb->pnum, seb->ec+1);
736 if (err)
737 continue;
738
739 seb->ec += 1;
740 list_del(&seb->u.list);
741 dbg_bld("return PEB %d, EC %d", seb->pnum, seb->ec);
742 return seb;
743 }
744 }
745
746 ubi_err("no eraseblocks found");
747 return ERR_PTR(-ENOSPC);
748}
749
750/**
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
756 *
757 * This function returns a zero if the physical eraseblock was succesfully
758 * handled and a negative error code in case of failure.
759 */
760static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si, int pnum)
761{
762 long long ec;
763 int err, bitflips = 0, vol_id, ec_corr = 0;
764
765 dbg_bld("scan PEB %d", pnum);
766
767 /* Skip bad physical eraseblocks */
768 err = ubi_io_is_bad(ubi, pnum);
769 if (err < 0)
770 return err;
771 else if (err) {
772 /*
773 * FIXME: this is actually duty of the I/O unit to initialize
774 * this, but MTD does not provide enough information.
775 */
776 si->bad_peb_count += 1;
777 return 0;
778 }
779
780 err = ubi_io_read_ec_hdr(ubi, pnum, ech, 0);
781 if (err < 0)
782 return err;
783 else if (err == UBI_IO_BITFLIPS)
784 bitflips = 1;
785 else if (err == UBI_IO_PEB_EMPTY)
786 return ubi_scan_add_to_list(si, pnum, UBI_SCAN_UNKNOWN_EC,
787 &si->erase);
788 else if (err == UBI_IO_BAD_EC_HDR) {
789 /*
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.
793 */
794 ec_corr = 1;
795 ec = UBI_SCAN_UNKNOWN_EC;
796 bitflips = 1;
797 }
798
799 si->is_empty = 0;
800
801 if (!ec_corr) {
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);
806 return -EINVAL;
807 }
808
809 ec = ubi64_to_cpu(ech->ec);
810 if (ec > UBI_MAX_ERASECOUNTER) {
811 /*
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
816 * internally.
817 */
818 ubi_err("erase counter overflow, max is %d",
819 UBI_MAX_ERASECOUNTER);
820 ubi_dbg_dump_ec_hdr(ech);
821 return -EINVAL;
822 }
823 }
824
825 /* OK, we've done with the EC header, let's look at the VID header */
826
827 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0);
828 if (err < 0)
829 return err;
830 else if (err == UBI_IO_BITFLIPS)
831 bitflips = 1;
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);
836 if (err)
837 return err;
838 goto adjust_mean_ec;
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);
842 if (err)
843 return err;
844 goto adjust_mean_ec;
845 }
846
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);
850
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);
857 if (err)
858 return err;
859 break;
860
861 case UBI_COMPAT_RO:
862 ubi_msg("read-only compatible internal volume %d:%d"
863 " found, switch to read-only mode",
864 vol_id, lnum);
865 ubi->ro_mode = 1;
866 break;
867
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);
872 if (err)
873 return err;
874 si->alien_peb_count += 1;
875 return 0;
876
877 case UBI_COMPAT_REJECT:
878 ubi_err("incompatible internal volume %d:%d found",
879 vol_id, lnum);
880 return -EINVAL;
881 }
882 }
883
884 /* Both UBI headers seem to be fine */
885 err = ubi_scan_add_used(ubi, si, pnum, ec, vidh, bitflips);
886 if (err)
887 return err;
888
889adjust_mean_ec:
890 if (!ec_corr) {
891 if (si->ec_sum + ec < ec) {
892 commit_to_mean_value(si);
893 si->ec_sum = 0;
894 si->ec_count = 0;
895 } else {
896 si->ec_sum += ec;
897 si->ec_count += 1;
898 }
899
900 if (ec > si->max_ec)
901 si->max_ec = ec;
902 if (ec < si->min_ec)
903 si->min_ec = ec;
904 }
905
906 return 0;
907}
908
909/**
910 * ubi_scan - scan an MTD device.
911 * @ubi: UBI device description object
912 *
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.
915 */
916struct ubi_scan_info *ubi_scan(struct ubi_device *ubi)
917{
918 int err, pnum;
919 struct rb_node *rb1, *rb2;
920 struct ubi_scan_volume *sv;
921 struct ubi_scan_leb *seb;
922 struct ubi_scan_info *si;
923
924 si = kzalloc(sizeof(struct ubi_scan_info), GFP_KERNEL);
925 if (!si)
926 return ERR_PTR(-ENOMEM);
927
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;
933 si->is_empty = 1;
934
935 err = -ENOMEM;
936 ech = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL);
937 if (!ech)
938 goto out_si;
939
940 vidh = ubi_zalloc_vid_hdr(ubi);
941 if (!vidh)
942 goto out_ech;
943
944 for (pnum = 0; pnum < ubi->peb_count; pnum++) {
945 cond_resched();
946
947 dbg_msg("process PEB %d", pnum);
948 err = process_eb(ubi, si, pnum);
949 if (err < 0)
950 goto out_vidh;
951 }
952
953 dbg_msg("scanning is finished");
954
955 /* Finish mean erase counter calculations */
956 if (si->ec_count)
957 commit_to_mean_value(si);
958
959 if (si->is_empty)
960 ubi_msg("empty MTD device detected");
961
962 /*
963 * In case of unknown erase counter we use the mean erase counter
964 * value.
965 */
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;
970 }
971
972 list_for_each_entry(seb, &si->free, u.list) {
973 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
974 seb->ec = si->mean_ec;
975 }
976
977 list_for_each_entry(seb, &si->corr, u.list)
978 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
979 seb->ec = si->mean_ec;
980
981 list_for_each_entry(seb, &si->erase, u.list)
982 if (seb->ec == UBI_SCAN_UNKNOWN_EC)
983 seb->ec = si->mean_ec;
984
985 err = paranoid_check_si(ubi, si);
986 if (err) {
987 if (err > 0)
988 err = -EINVAL;
989 goto out_vidh;
990 }
991
992 ubi_free_vid_hdr(ubi, vidh);
993 kfree(ech);
994
995 return si;
996
997out_vidh:
998 ubi_free_vid_hdr(ubi, vidh);
999out_ech:
1000 kfree(ech);
1001out_si:
1002 ubi_scan_destroy_si(si);
1003 return ERR_PTR(err);
1004}
1005
1006/**
1007 * destroy_sv - free the scanning volume information
1008 * @sv: scanning volume information
1009 *
1010 * This function destroys the volume RB-tree (@sv->root) and the scanning
1011 * volume information.
1012 */
1013static void destroy_sv(struct ubi_scan_volume *sv)
1014{
1015 struct ubi_scan_leb *seb;
1016 struct rb_node *this = sv->root.rb_node;
1017
1018 while (this) {
1019 if (this->rb_left)
1020 this = this->rb_left;
1021 else if (this->rb_right)
1022 this = this->rb_right;
1023 else {
1024 seb = rb_entry(this, struct ubi_scan_leb, u.rb);
1025 this = rb_parent(this);
1026 if (this) {
1027 if (this->rb_left == &seb->u.rb)
1028 this->rb_left = NULL;
1029 else
1030 this->rb_right = NULL;
1031 }
1032
1033 kfree(seb);
1034 }
1035 }
1036 kfree(sv);
1037}
1038
1039/**
1040 * ubi_scan_destroy_si - destroy scanning information.
1041 * @si: scanning information
1042 */
1043void ubi_scan_destroy_si(struct ubi_scan_info *si)
1044{
1045 struct ubi_scan_leb *seb, *seb_tmp;
1046 struct ubi_scan_volume *sv;
1047 struct rb_node *rb;
1048
1049 list_for_each_entry_safe(seb, seb_tmp, &si->alien, u.list) {
1050 list_del(&seb->u.list);
1051 kfree(seb);
1052 }
1053 list_for_each_entry_safe(seb, seb_tmp, &si->erase, u.list) {
1054 list_del(&seb->u.list);
1055 kfree(seb);
1056 }
1057 list_for_each_entry_safe(seb, seb_tmp, &si->corr, u.list) {
1058 list_del(&seb->u.list);
1059 kfree(seb);
1060 }
1061 list_for_each_entry_safe(seb, seb_tmp, &si->free, u.list) {
1062 list_del(&seb->u.list);
1063 kfree(seb);
1064 }
1065
1066 /* Destroy the volume RB-tree */
1067 rb = si->volumes.rb_node;
1068 while (rb) {
1069 if (rb->rb_left)
1070 rb = rb->rb_left;
1071 else if (rb->rb_right)
1072 rb = rb->rb_right;
1073 else {
1074 sv = rb_entry(rb, struct ubi_scan_volume, rb);
1075
1076 rb = rb_parent(rb);
1077 if (rb) {
1078 if (rb->rb_left == &sv->rb)
1079 rb->rb_left = NULL;
1080 else
1081 rb->rb_right = NULL;
1082 }
1083
1084 destroy_sv(sv);
1085 }
1086 }
1087
1088 kfree(si);
1089}
1090
1091#ifdef CONFIG_MTD_UBI_DEBUG_PARANOID
1092
1093/**
1094 * paranoid_check_si - check if the scanning information is correct and
1095 * consistent.
1096 * @ubi: UBI device description object
1097 * @si: scanning information
1098 *
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.
1101 */
1102static int paranoid_check_si(const struct ubi_device *ubi,
1103 struct ubi_scan_info *si)
1104{
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;
1109 uint8_t *buf;
1110
1111 /*
1112 * At first, check that scanning information is ok.
1113 */
1114 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) {
1115 int leb_count = 0;
1116
1117 cond_resched();
1118
1119 vols_found += 1;
1120
1121 if (si->is_empty) {
1122 ubi_err("bad is_empty flag");
1123 goto bad_sv;
1124 }
1125
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");
1130 goto bad_sv;
1131 }
1132
1133 if (sv->vol_id >= UBI_MAX_VOLUMES &&
1134 sv->vol_id < UBI_INTERNAL_VOL_START) {
1135 ubi_err("bad vol_id");
1136 goto bad_sv;
1137 }
1138
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);
1142 goto out;
1143 }
1144
1145 if (sv->vol_type != UBI_DYNAMIC_VOLUME &&
1146 sv->vol_type != UBI_STATIC_VOLUME) {
1147 ubi_err("bad vol_type");
1148 goto bad_sv;
1149 }
1150
1151 if (sv->data_pad > ubi->leb_size / 2) {
1152 ubi_err("bad data_pad");
1153 goto bad_sv;
1154 }
1155
1156 last_seb = NULL;
1157 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) {
1158 cond_resched();
1159
1160 last_seb = seb;
1161 leb_count += 1;
1162
1163 if (seb->pnum < 0 || seb->ec < 0) {
1164 ubi_err("negative values");
1165 goto bad_seb;
1166 }
1167
1168 if (seb->ec < si->min_ec) {
1169 ubi_err("bad si->min_ec (%d), %d found",
1170 si->min_ec, seb->ec);
1171 goto bad_seb;
1172 }
1173
1174 if (seb->ec > si->max_ec) {
1175 ubi_err("bad si->max_ec (%d), %d found",
1176 si->max_ec, seb->ec);
1177 goto bad_seb;
1178 }
1179
1180 if (seb->pnum >= ubi->peb_count) {
1181 ubi_err("too high PEB number %d, total PEBs %d",
1182 seb->pnum, ubi->peb_count);
1183 goto bad_seb;
1184 }
1185
1186 if (sv->vol_type == UBI_STATIC_VOLUME) {
1187 if (seb->lnum >= sv->used_ebs) {
1188 ubi_err("bad lnum or used_ebs");
1189 goto bad_seb;
1190 }
1191 } else {
1192 if (sv->used_ebs != 0) {
1193 ubi_err("non-zero used_ebs");
1194 goto bad_seb;
1195 }
1196 }
1197
1198 if (seb->lnum > sv->highest_lnum) {
1199 ubi_err("incorrect highest_lnum or lnum");
1200 goto bad_seb;
1201 }
1202 }
1203
1204 if (sv->leb_count != leb_count) {
1205 ubi_err("bad leb_count, %d objects in the tree",
1206 leb_count);
1207 goto bad_sv;
1208 }
1209
1210 if (!last_seb)
1211 continue;
1212
1213 seb = last_seb;
1214
1215 if (seb->lnum != sv->highest_lnum) {
1216 ubi_err("bad highest_lnum");
1217 goto bad_seb;
1218 }
1219 }
1220
1221 if (vols_found != si->vols_found) {
1222 ubi_err("bad si->vols_found %d, should be %d",
1223 si->vols_found, vols_found);
1224 goto out;
1225 }
1226
1227 /* Check that scanning information is correct */
1228 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) {
1229 last_seb = NULL;
1230 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) {
1231 int vol_type;
1232
1233 cond_resched();
1234
1235 last_seb = seb;
1236
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);
1240 if (err > 0)
1241 err = -EIO;
1242 return err;
1243 }
1244
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");
1249 goto bad_vid_hdr;
1250 }
1251
1252 if (seb->sqnum != ubi64_to_cpu(vidh->sqnum)) {
1253 ubi_err("bad sqnum %llu", seb->sqnum);
1254 goto bad_vid_hdr;
1255 }
1256
1257 if (sv->vol_id != ubi32_to_cpu(vidh->vol_id)) {
1258 ubi_err("bad vol_id %d", sv->vol_id);
1259 goto bad_vid_hdr;
1260 }
1261
1262 if (sv->compat != vidh->compat) {
1263 ubi_err("bad compat %d", vidh->compat);
1264 goto bad_vid_hdr;
1265 }
1266
1267 if (seb->lnum != ubi32_to_cpu(vidh->lnum)) {
1268 ubi_err("bad lnum %d", seb->lnum);
1269 goto bad_vid_hdr;
1270 }
1271
1272 if (sv->used_ebs != ubi32_to_cpu(vidh->used_ebs)) {
1273 ubi_err("bad used_ebs %d", sv->used_ebs);
1274 goto bad_vid_hdr;
1275 }
1276
1277 if (sv->data_pad != ubi32_to_cpu(vidh->data_pad)) {
1278 ubi_err("bad data_pad %d", sv->data_pad);
1279 goto bad_vid_hdr;
1280 }
1281
1282 if (seb->leb_ver != ubi32_to_cpu(vidh->leb_ver)) {
1283 ubi_err("bad leb_ver %u", seb->leb_ver);
1284 goto bad_vid_hdr;
1285 }
1286 }
1287
1288 if (!last_seb)
1289 continue;
1290
1291 if (sv->highest_lnum != ubi32_to_cpu(vidh->lnum)) {
1292 ubi_err("bad highest_lnum %d", sv->highest_lnum);
1293 goto bad_vid_hdr;
1294 }
1295
1296 if (sv->last_data_size != ubi32_to_cpu(vidh->data_size)) {
1297 ubi_err("bad last_data_size %d", sv->last_data_size);
1298 goto bad_vid_hdr;
1299 }
1300 }
1301
1302 /*
1303 * Make sure that all the physical eraseblocks are in one of the lists
1304 * or trees.
1305 */
1306 buf = kmalloc(ubi->peb_count, GFP_KERNEL);
1307 if (!buf)
1308 return -ENOMEM;
1309
1310 memset(buf, 1, ubi->peb_count);
1311 for (pnum = 0; pnum < ubi->peb_count; pnum++) {
1312 err = ubi_io_is_bad(ubi, pnum);
1313 if (err < 0)
1314 return err;
1315 else if (err)
1316 buf[pnum] = 0;
1317 }
1318
1319 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb)
1320 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb)
1321 buf[seb->pnum] = 0;
1322
1323 list_for_each_entry(seb, &si->free, u.list)
1324 buf[seb->pnum] = 0;
1325
1326 list_for_each_entry(seb, &si->corr, u.list)
1327 buf[seb->pnum] = 0;
1328
1329 list_for_each_entry(seb, &si->erase, u.list)
1330 buf[seb->pnum] = 0;
1331
1332 list_for_each_entry(seb, &si->alien, u.list)
1333 buf[seb->pnum] = 0;
1334
1335 err = 0;
1336 for (pnum = 0; pnum < ubi->peb_count; pnum++)
1337 if (buf[pnum]) {
1338 ubi_err("PEB %d is not referred", pnum);
1339 err = 1;
1340 }
1341
1342 kfree(buf);
1343 if (err)
1344 goto out;
1345 return 0;
1346
1347bad_seb:
1348 ubi_err("bad scanning information about LEB %d", seb->lnum);
1349 ubi_dbg_dump_seb(seb, 0);
1350 ubi_dbg_dump_sv(sv);
1351 goto out;
1352
1353bad_sv:
1354 ubi_err("bad scanning information about volume %d", sv->vol_id);
1355 ubi_dbg_dump_sv(sv);
1356 goto out;
1357
1358bad_vid_hdr:
1359 ubi_err("bad scanning information about volume %d", sv->vol_id);
1360 ubi_dbg_dump_sv(sv);
1361 ubi_dbg_dump_vid_hdr(vidh);
1362
1363out:
1364 ubi_dbg_dump_stack();
1365 return 1;
1366}
1367
1368#endif /* CONFIG_MTD_UBI_DEBUG_PARANOID */
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-03 04:37:14 -0500