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 dbg_bld("using old crappy leb_ver stuff"); 267 268 abs = v1 - v2; 269 if (abs < 0) 270 abs = -abs; 271 272 if (abs < 0x7FFFFFFF) 273 /* Non-overflow situation */ 274 second_is_newer = (v2 > v1); 275 else 276 second_is_newer = (v2 < v1); 277 } else 278 /* Obviously the LEB with lower sequence counter is older */ 279 second_is_newer = sqnum2 > seb->sqnum; 280 281 282 if (second_is_newer) { 283 if (!vid_hdr->copy_flag) { 284 /* It is not a copy, so it is newer */ 285 dbg_bld("second PEB %d is newer, copy_flag is unset", 286 pnum); 287 return 1; 288 } 289 } else { 290 pnum = seb->pnum; 291 292 vidh = ubi_zalloc_vid_hdr(ubi); 293 if (!vidh) 294 return -ENOMEM; 295 296 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0); 297 if (err) { 298 if (err == UBI_IO_BITFLIPS) 299 bitflips = 1; 300 else { 301 dbg_err("VID of PEB %d header is bad, but it " 302 "was OK earlier", pnum); 303 if (err > 0) 304 err = -EIO; 305 306 goto out_free_vidh; 307 } 308 } 309 310 if (!vidh->copy_flag) { 311 /* It is not a copy, so it is newer */ 312 dbg_bld("first PEB %d is newer, copy_flag is unset", 313 pnum); 314 err = bitflips << 1; 315 goto out_free_vidh; 316 } 317 318 vid_hdr = vidh; 319 } 320 321 /* Read the data of the copy and check the CRC */ 322 323 len = ubi32_to_cpu(vid_hdr->data_size); 324 buf = kmalloc(len, GFP_KERNEL); 325 if (!buf) { 326 err = -ENOMEM; 327 goto out_free_vidh; 328 } 329 330 err = ubi_io_read_data(ubi, buf, pnum, 0, len); 331 if (err && err != UBI_IO_BITFLIPS) 332 goto out_free_buf; 333 334 data_crc = ubi32_to_cpu(vid_hdr->data_crc); 335 crc = crc32(UBI_CRC32_INIT, buf, len); 336 if (crc != data_crc) { 337 dbg_bld("PEB %d CRC error: calculated %#08x, must be %#08x", 338 pnum, crc, data_crc); 339 corrupted = 1; 340 bitflips = 0; 341 second_is_newer = !second_is_newer; 342 } else { 343 dbg_bld("PEB %d CRC is OK", pnum); 344 bitflips = !!err; 345 } 346 347 kfree(buf); 348 ubi_free_vid_hdr(ubi, vidh); 349 350 if (second_is_newer) 351 dbg_bld("second PEB %d is newer, copy_flag is set", pnum); 352 else 353 dbg_bld("first PEB %d is newer, copy_flag is set", pnum); 354 355 return second_is_newer | (bitflips << 1) | (corrupted << 2); 356 357out_free_buf: 358 kfree(buf); 359out_free_vidh: 360 ubi_free_vid_hdr(ubi, vidh); 361 ubi_assert(err < 0); 362 return err; 363} 364 365/** 366 * ubi_scan_add_used - add information about a physical eraseblock to the 367 * scanning information. 368 * @ubi: UBI device description object 369 * @si: scanning information 370 * @pnum: the physical eraseblock number 371 * @ec: erase counter 372 * @vid_hdr: the volume identifier header 373 * @bitflips: if bit-flips were detected when this physical eraseblock was read 374 * 375 * This function returns zero in case of success and a negative error code in 376 * case of failure. 377 */ 378int ubi_scan_add_used(const struct ubi_device *ubi, struct ubi_scan_info *si, 379 int pnum, int ec, const struct ubi_vid_hdr *vid_hdr, 380 int bitflips) 381{ 382 int err, vol_id, lnum; 383 uint32_t leb_ver; 384 unsigned long long sqnum; 385 struct ubi_scan_volume *sv; 386 struct ubi_scan_leb *seb; 387 struct rb_node **p, *parent = NULL; 388 389 vol_id = ubi32_to_cpu(vid_hdr->vol_id); 390 lnum = ubi32_to_cpu(vid_hdr->lnum); 391 sqnum = ubi64_to_cpu(vid_hdr->sqnum); 392 leb_ver = ubi32_to_cpu(vid_hdr->leb_ver); 393 394 dbg_bld("PEB %d, LEB %d:%d, EC %d, sqnum %llu, ver %u, bitflips %d", 395 pnum, vol_id, lnum, ec, sqnum, leb_ver, bitflips); 396 397 sv = add_volume(si, vol_id, pnum, vid_hdr); 398 if (IS_ERR(sv) < 0) 399 return PTR_ERR(sv); 400 401 /* 402 * Walk the RB-tree of logical eraseblocks of volume @vol_id to look 403 * if this is the first instance of this logical eraseblock or not. 404 */ 405 p = &sv->root.rb_node; 406 while (*p) { 407 int cmp_res; 408 409 parent = *p; 410 seb = rb_entry(parent, struct ubi_scan_leb, u.rb); 411 if (lnum != seb->lnum) { 412 if (lnum < seb->lnum) 413 p = &(*p)->rb_left; 414 else 415 p = &(*p)->rb_right; 416 continue; 417 } 418 419 /* 420 * There is already a physical eraseblock describing the same 421 * logical eraseblock present. 422 */ 423 424 dbg_bld("this LEB already exists: PEB %d, sqnum %llu, " 425 "LEB ver %u, EC %d", seb->pnum, seb->sqnum, 426 seb->leb_ver, seb->ec); 427 428 /* 429 * Make sure that the logical eraseblocks have different 430 * versions. Otherwise the image is bad. 431 */ 432 if (seb->leb_ver == leb_ver && leb_ver != 0) { 433 ubi_err("two LEBs with same version %u", leb_ver); 434 ubi_dbg_dump_seb(seb, 0); 435 ubi_dbg_dump_vid_hdr(vid_hdr); 436 return -EINVAL; 437 } 438 439 if (seb->sqnum == sqnum && sqnum != 0) { 440 ubi_err("two LEBs with same sequence number %llu", 441 sqnum); 442 ubi_dbg_dump_seb(seb, 0); 443 ubi_dbg_dump_vid_hdr(vid_hdr); 444 return -EINVAL; 445 } 446 447 /* 448 * Now we have to drop the older one and preserve the newer 449 * one. 450 */ 451 cmp_res = compare_lebs(ubi, seb, pnum, vid_hdr); 452 if (cmp_res < 0) 453 return cmp_res; 454 455 if (cmp_res & 1) { 456 /* 457 * This logical eraseblock is newer then the one 458 * found earlier. 459 */ 460 err = validate_vid_hdr(vid_hdr, sv, pnum); 461 if (err) 462 return err; 463 464 if (cmp_res & 4) 465 err = ubi_scan_add_to_list(si, seb->pnum, 466 seb->ec, &si->corr); 467 else 468 err = ubi_scan_add_to_list(si, seb->pnum, 469 seb->ec, &si->erase); 470 if (err) 471 return err; 472 473 seb->ec = ec; 474 seb->pnum = pnum; 475 seb->scrub = ((cmp_res & 2) || bitflips); 476 seb->sqnum = sqnum; 477 seb->leb_ver = leb_ver; 478 479 if (sv->highest_lnum == lnum) 480 sv->last_data_size = 481 ubi32_to_cpu(vid_hdr->data_size); 482 483 return 0; 484 } else { 485 /* 486 * This logical eraseblock is older then the one found 487 * previously. 488 */ 489 if (cmp_res & 4) 490 return ubi_scan_add_to_list(si, pnum, ec, 491 &si->corr); 492 else 493 return ubi_scan_add_to_list(si, pnum, ec, 494 &si->erase); 495 } 496 } 497 498 /* 499 * We've met this logical eraseblock for the first time, add it to the 500 * scanning information. 501 */ 502 503 err = validate_vid_hdr(vid_hdr, sv, pnum); 504 if (err) 505 return err; 506 507 seb = kmalloc(sizeof(struct ubi_scan_leb), GFP_KERNEL); 508 if (!seb) 509 return -ENOMEM; 510 511 seb->ec = ec; 512 seb->pnum = pnum; 513 seb->lnum = lnum; 514 seb->sqnum = sqnum; 515 seb->scrub = bitflips; 516 seb->leb_ver = leb_ver; 517 518 if (sv->highest_lnum <= lnum) { 519 sv->highest_lnum = lnum; 520 sv->last_data_size = ubi32_to_cpu(vid_hdr->data_size); 521 } 522 523 if (si->max_sqnum < sqnum) 524 si->max_sqnum = sqnum; 525 526 sv->leb_count += 1; 527 rb_link_node(&seb->u.rb, parent, p); 528 rb_insert_color(&seb->u.rb, &sv->root); 529 return 0; 530} 531 532/** 533 * ubi_scan_find_sv - find information about a particular volume in the 534 * scanning information. 535 * @si: scanning information 536 * @vol_id: the requested volume ID 537 * 538 * This function returns a pointer to the volume description or %NULL if there 539 * are no data about this volume in the scanning information. 540 */ 541struct ubi_scan_volume *ubi_scan_find_sv(const struct ubi_scan_info *si, 542 int vol_id) 543{ 544 struct ubi_scan_volume *sv; 545 struct rb_node *p = si->volumes.rb_node; 546 547 while (p) { 548 sv = rb_entry(p, struct ubi_scan_volume, rb); 549 550 if (vol_id == sv->vol_id) 551 return sv; 552 553 if (vol_id > sv->vol_id) 554 p = p->rb_left; 555 else 556 p = p->rb_right; 557 } 558 559 return NULL; 560} 561 562/** 563 * ubi_scan_find_seb - find information about a particular logical 564 * eraseblock in the volume scanning information. 565 * @sv: a pointer to the volume scanning information 566 * @lnum: the requested logical eraseblock 567 * 568 * This function returns a pointer to the scanning logical eraseblock or %NULL 569 * if there are no data about it in the scanning volume information. 570 */ 571struct ubi_scan_leb *ubi_scan_find_seb(const struct ubi_scan_volume *sv, 572 int lnum) 573{ 574 struct ubi_scan_leb *seb; 575 struct rb_node *p = sv->root.rb_node; 576 577 while (p) { 578 seb = rb_entry(p, struct ubi_scan_leb, u.rb); 579 580 if (lnum == seb->lnum) 581 return seb; 582 583 if (lnum > seb->lnum) 584 p = p->rb_left; 585 else 586 p = p->rb_right; 587 } 588 589 return NULL; 590} 591 592/** 593 * ubi_scan_rm_volume - delete scanning information about a volume. 594 * @si: scanning information 595 * @sv: the volume scanning information to delete 596 */ 597void ubi_scan_rm_volume(struct ubi_scan_info *si, struct ubi_scan_volume *sv) 598{ 599 struct rb_node *rb; 600 struct ubi_scan_leb *seb; 601 602 dbg_bld("remove scanning information about volume %d", sv->vol_id); 603 604 while ((rb = rb_first(&sv->root))) { 605 seb = rb_entry(rb, struct ubi_scan_leb, u.rb); 606 rb_erase(&seb->u.rb, &sv->root); 607 list_add_tail(&seb->u.list, &si->erase); 608 } 609 610 rb_erase(&sv->rb, &si->volumes); 611 kfree(sv); 612 si->vols_found -= 1; 613} 614 615/** 616 * ubi_scan_erase_peb - erase a physical eraseblock. 617 * @ubi: UBI device description object 618 * @si: scanning information 619 * @pnum: physical eraseblock number to erase; 620 * @ec: erase counter value to write (%UBI_SCAN_UNKNOWN_EC if it is unknown) 621 * 622 * This function erases physical eraseblock 'pnum', and writes the erase 623 * counter header to it. This function should only be used on UBI device 624 * initialization stages, when the EBA unit had not been yet initialized. This 625 * function returns zero in case of success and a negative error code in case 626 * of failure. 627 */ 628int ubi_scan_erase_peb(const struct ubi_device *ubi, 629 const struct ubi_scan_info *si, int pnum, int ec) 630{ 631 int err; 632 struct ubi_ec_hdr *ec_hdr; 633 634 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL); 635 if (!ec_hdr) 636 return -ENOMEM; 637 638 if ((long long)ec >= UBI_MAX_ERASECOUNTER) { 639 /* 640 * Erase counter overflow. Upgrade UBI and use 64-bit 641 * erase counters internally. 642 */ 643 ubi_err("erase counter overflow at PEB %d, EC %d", pnum, ec); 644 return -EINVAL; 645 } 646 647 ec_hdr->ec = cpu_to_ubi64(ec); 648 649 err = ubi_io_sync_erase(ubi, pnum, 0); 650 if (err < 0) 651 goto out_free; 652 653 err = ubi_io_write_ec_hdr(ubi, pnum, ec_hdr); 654 655out_free: 656 kfree(ec_hdr); 657 return err; 658} 659 660/** 661 * ubi_scan_get_free_peb - get a free physical eraseblock. 662 * @ubi: UBI device description object 663 * @si: scanning information 664 * 665 * This function returns a free physical eraseblock. It is supposed to be 666 * called on the UBI initialization stages when the wear-leveling unit is not 667 * initialized yet. This function picks a physical eraseblocks from one of the 668 * lists, writes the EC header if it is needed, and removes it from the list. 669 * 670 * This function returns scanning physical eraseblock information in case of 671 * success and an error code in case of failure. 672 */ 673struct ubi_scan_leb *ubi_scan_get_free_peb(const struct ubi_device *ubi, 674 struct ubi_scan_info *si) 675{ 676 int err = 0, i; 677 struct ubi_scan_leb *seb; 678 679 if (!list_empty(&si->free)) { 680 seb = list_entry(si->free.next, struct ubi_scan_leb, u.list); 681 list_del(&seb->u.list); 682 dbg_bld("return free PEB %d, EC %d", seb->pnum, seb->ec); 683 return seb; 684 } 685 686 for (i = 0; i < 2; i++) { 687 struct list_head *head; 688 struct ubi_scan_leb *tmp_seb; 689 690 if (i == 0) 691 head = &si->erase; 692 else 693 head = &si->corr; 694 695 /* 696 * We try to erase the first physical eraseblock from the @head 697 * list and pick it if we succeed, or try to erase the 698 * next one if not. And so forth. We don't want to take care 699 * about bad eraseblocks here - they'll be handled later. 700 */ 701 list_for_each_entry_safe(seb, tmp_seb, head, u.list) { 702 if (seb->ec == UBI_SCAN_UNKNOWN_EC) 703 seb->ec = si->mean_ec; 704 705 err = ubi_scan_erase_peb(ubi, si, seb->pnum, seb->ec+1); 706 if (err) 707 continue; 708 709 seb->ec += 1; 710 list_del(&seb->u.list); 711 dbg_bld("return PEB %d, EC %d", seb->pnum, seb->ec); 712 return seb; 713 } 714 } 715 716 ubi_err("no eraseblocks found"); 717 return ERR_PTR(-ENOSPC); 718} 719 720/** 721 * process_eb - read UBI headers, check them and add corresponding data 722 * to the scanning information. 723 * @ubi: UBI device description object 724 * @si: scanning information 725 * @pnum: the physical eraseblock number 726 * 727 * This function returns a zero if the physical eraseblock was succesfully 728 * handled and a negative error code in case of failure. 729 */ 730static int process_eb(struct ubi_device *ubi, struct ubi_scan_info *si, int pnum) 731{ 732 long long ec; 733 int err, bitflips = 0, vol_id, ec_corr = 0; 734 735 dbg_bld("scan PEB %d", pnum); 736 737 /* Skip bad physical eraseblocks */ 738 err = ubi_io_is_bad(ubi, pnum); 739 if (err < 0) 740 return err; 741 else if (err) { 742 si->bad_peb_count += 1; 743 return 0; 744 } 745 746 err = ubi_io_read_ec_hdr(ubi, pnum, ech, 0); 747 if (err < 0) 748 return err; 749 else if (err == UBI_IO_BITFLIPS) 750 bitflips = 1; 751 else if (err == UBI_IO_PEB_EMPTY) 752 return ubi_scan_add_to_list(si, pnum, UBI_SCAN_UNKNOWN_EC, 753 &si->erase); 754 else if (err == UBI_IO_BAD_EC_HDR) { 755 /* 756 * We have to also look at the VID header, possibly it is not 757 * corrupted. Set %bitflips flag in order to make this PEB be 758 * moved and EC be re-created. 759 */ 760 ec_corr = 1; 761 ec = UBI_SCAN_UNKNOWN_EC; 762 bitflips = 1; 763 } 764 765 si->is_empty = 0; 766 767 if (!ec_corr) { 768 /* Make sure UBI version is OK */ 769 if (ech->version != UBI_VERSION) { 770 ubi_err("this UBI version is %d, image version is %d", 771 UBI_VERSION, (int)ech->version); 772 return -EINVAL; 773 } 774 775 ec = ubi64_to_cpu(ech->ec); 776 if (ec > UBI_MAX_ERASECOUNTER) { 777 /* 778 * Erase counter overflow. The EC headers have 64 bits 779 * reserved, but we anyway make use of only 31 bit 780 * values, as this seems to be enough for any existing 781 * flash. Upgrade UBI and use 64-bit erase counters 782 * internally. 783 */ 784 ubi_err("erase counter overflow, max is %d", 785 UBI_MAX_ERASECOUNTER); 786 ubi_dbg_dump_ec_hdr(ech); 787 return -EINVAL; 788 } 789 } 790 791 /* OK, we've done with the EC header, let's look at the VID header */ 792 793 err = ubi_io_read_vid_hdr(ubi, pnum, vidh, 0); 794 if (err < 0) 795 return err; 796 else if (err == UBI_IO_BITFLIPS) 797 bitflips = 1; 798 else if (err == UBI_IO_BAD_VID_HDR || 799 (err == UBI_IO_PEB_FREE && ec_corr)) { 800 /* VID header is corrupted */ 801 err = ubi_scan_add_to_list(si, pnum, ec, &si->corr); 802 if (err) 803 return err; 804 goto adjust_mean_ec; 805 } else if (err == UBI_IO_PEB_FREE) { 806 /* No VID header - the physical eraseblock is free */ 807 err = ubi_scan_add_to_list(si, pnum, ec, &si->free); 808 if (err) 809 return err; 810 goto adjust_mean_ec; 811 } 812 813 vol_id = ubi32_to_cpu(vidh->vol_id); 814 if (vol_id > UBI_MAX_VOLUMES && vol_id != UBI_LAYOUT_VOL_ID) { 815 int lnum = ubi32_to_cpu(vidh->lnum); 816 817 /* Unsupported internal volume */ 818 switch (vidh->compat) { 819 case UBI_COMPAT_DELETE: 820 ubi_msg("\"delete\" compatible internal volume %d:%d" 821 " found, remove it", vol_id, lnum); 822 err = ubi_scan_add_to_list(si, pnum, ec, &si->corr); 823 if (err) 824 return err; 825 break; 826 827 case UBI_COMPAT_RO: 828 ubi_msg("read-only compatible internal volume %d:%d" 829 " found, switch to read-only mode", 830 vol_id, lnum); 831 ubi->ro_mode = 1; 832 break; 833 834 case UBI_COMPAT_PRESERVE: 835 ubi_msg("\"preserve\" compatible internal volume %d:%d" 836 " found", vol_id, lnum); 837 err = ubi_scan_add_to_list(si, pnum, ec, &si->alien); 838 if (err) 839 return err; 840 si->alien_peb_count += 1; 841 return 0; 842 843 case UBI_COMPAT_REJECT: 844 ubi_err("incompatible internal volume %d:%d found", 845 vol_id, lnum); 846 return -EINVAL; 847 } 848 } 849 850 /* Both UBI headers seem to be fine */ 851 err = ubi_scan_add_used(ubi, si, pnum, ec, vidh, bitflips); 852 if (err) 853 return err; 854 855adjust_mean_ec: 856 if (!ec_corr) { 857 if (si->ec_sum + ec < ec) { 858 commit_to_mean_value(si); 859 si->ec_sum = 0; 860 si->ec_count = 0; 861 } else { 862 si->ec_sum += ec; 863 si->ec_count += 1; 864 } 865 866 if (ec > si->max_ec) 867 si->max_ec = ec; 868 if (ec < si->min_ec) 869 si->min_ec = ec; 870 } 871 872 return 0; 873} 874 875/** 876 * ubi_scan - scan an MTD device. 877 * @ubi: UBI device description object 878 * 879 * This function does full scanning of an MTD device and returns complete 880 * information about it. In case of failure, an error code is returned. 881 */ 882struct ubi_scan_info *ubi_scan(struct ubi_device *ubi) 883{ 884 int err, pnum; 885 struct rb_node *rb1, *rb2; 886 struct ubi_scan_volume *sv; 887 struct ubi_scan_leb *seb; 888 struct ubi_scan_info *si; 889 890 si = kzalloc(sizeof(struct ubi_scan_info), GFP_KERNEL); 891 if (!si) 892 return ERR_PTR(-ENOMEM); 893 894 INIT_LIST_HEAD(&si->corr); 895 INIT_LIST_HEAD(&si->free); 896 INIT_LIST_HEAD(&si->erase); 897 INIT_LIST_HEAD(&si->alien); 898 si->volumes = RB_ROOT; 899 si->is_empty = 1; 900 901 err = -ENOMEM; 902 ech = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL); 903 if (!ech) 904 goto out_si; 905 906 vidh = ubi_zalloc_vid_hdr(ubi); 907 if (!vidh) 908 goto out_ech; 909 910 for (pnum = 0; pnum < ubi->peb_count; pnum++) { 911 cond_resched(); 912 913 dbg_msg("process PEB %d", pnum); 914 err = process_eb(ubi, si, pnum); 915 if (err < 0) 916 goto out_vidh; 917 } 918 919 dbg_msg("scanning is finished"); 920 921 /* Finish mean erase counter calculations */ 922 if (si->ec_count) 923 commit_to_mean_value(si); 924 925 if (si->is_empty) 926 ubi_msg("empty MTD device detected"); 927 928 /* 929 * In case of unknown erase counter we use the mean erase counter 930 * value. 931 */ 932 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) { 933 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) 934 if (seb->ec == UBI_SCAN_UNKNOWN_EC) 935 seb->ec = si->mean_ec; 936 } 937 938 list_for_each_entry(seb, &si->free, u.list) { 939 if (seb->ec == UBI_SCAN_UNKNOWN_EC) 940 seb->ec = si->mean_ec; 941 } 942 943 list_for_each_entry(seb, &si->corr, u.list) 944 if (seb->ec == UBI_SCAN_UNKNOWN_EC) 945 seb->ec = si->mean_ec; 946 947 list_for_each_entry(seb, &si->erase, u.list) 948 if (seb->ec == UBI_SCAN_UNKNOWN_EC) 949 seb->ec = si->mean_ec; 950 951 err = paranoid_check_si(ubi, si); 952 if (err) { 953 if (err > 0) 954 err = -EINVAL; 955 goto out_vidh; 956 } 957 958 ubi_free_vid_hdr(ubi, vidh); 959 kfree(ech); 960 961 return si; 962 963out_vidh: 964 ubi_free_vid_hdr(ubi, vidh); 965out_ech: 966 kfree(ech); 967out_si: 968 ubi_scan_destroy_si(si); 969 return ERR_PTR(err); 970} 971 972/** 973 * destroy_sv - free the scanning volume information 974 * @sv: scanning volume information 975 * 976 * This function destroys the volume RB-tree (@sv->root) and the scanning 977 * volume information. 978 */ 979static void destroy_sv(struct ubi_scan_volume *sv) 980{ 981 struct ubi_scan_leb *seb; 982 struct rb_node *this = sv->root.rb_node; 983 984 while (this) { 985 if (this->rb_left) 986 this = this->rb_left; 987 else if (this->rb_right) 988 this = this->rb_right; 989 else { 990 seb = rb_entry(this, struct ubi_scan_leb, u.rb); 991 this = rb_parent(this); 992 if (this) { 993 if (this->rb_left == &seb->u.rb) 994 this->rb_left = NULL; 995 else 996 this->rb_right = NULL; 997 } 998 999 kfree(seb); 1000 } 1001 } 1002 kfree(sv); 1003} 1004 1005/** 1006 * ubi_scan_destroy_si - destroy scanning information. 1007 * @si: scanning information 1008 */ 1009void ubi_scan_destroy_si(struct ubi_scan_info *si) 1010{ 1011 struct ubi_scan_leb *seb, *seb_tmp; 1012 struct ubi_scan_volume *sv; 1013 struct rb_node *rb; 1014 1015 list_for_each_entry_safe(seb, seb_tmp, &si->alien, u.list) { 1016 list_del(&seb->u.list); 1017 kfree(seb); 1018 } 1019 list_for_each_entry_safe(seb, seb_tmp, &si->erase, u.list) { 1020 list_del(&seb->u.list); 1021 kfree(seb); 1022 } 1023 list_for_each_entry_safe(seb, seb_tmp, &si->corr, u.list) { 1024 list_del(&seb->u.list); 1025 kfree(seb); 1026 } 1027 list_for_each_entry_safe(seb, seb_tmp, &si->free, u.list) { 1028 list_del(&seb->u.list); 1029 kfree(seb); 1030 } 1031 1032 /* Destroy the volume RB-tree */ 1033 rb = si->volumes.rb_node; 1034 while (rb) { 1035 if (rb->rb_left) 1036 rb = rb->rb_left; 1037 else if (rb->rb_right) 1038 rb = rb->rb_right; 1039 else { 1040 sv = rb_entry(rb, struct ubi_scan_volume, rb); 1041 1042 rb = rb_parent(rb); 1043 if (rb) { 1044 if (rb->rb_left == &sv->rb) 1045 rb->rb_left = NULL; 1046 else 1047 rb->rb_right = NULL; 1048 } 1049 1050 destroy_sv(sv); 1051 } 1052 } 1053 1054 kfree(si); 1055} 1056 1057#ifdef CONFIG_MTD_UBI_DEBUG_PARANOID 1058 1059/** 1060 * paranoid_check_si - check if the scanning information is correct and 1061 * consistent. 1062 * @ubi: UBI device description object 1063 * @si: scanning information 1064 * 1065 * This function returns zero if the scanning information is all right, %1 if 1066 * not and a negative error code if an error occurred. 1067 */ 1068static int paranoid_check_si(const struct ubi_device *ubi, 1069 struct ubi_scan_info *si) 1070{ 1071 int pnum, err, vols_found = 0; 1072 struct rb_node *rb1, *rb2; 1073 struct ubi_scan_volume *sv; 1074 struct ubi_scan_leb *seb, *last_seb; 1075 uint8_t *buf; 1076 1077 /* 1078 * At first, check that scanning information is ok. 1079 */ 1080 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) { 1081 int leb_count = 0; 1082 1083 cond_resched(); 1084 1085 vols_found += 1; 1086 1087 if (si->is_empty) { 1088 ubi_err("bad is_empty flag"); 1089 goto bad_sv; 1090 } 1091 1092 if (sv->vol_id < 0 || sv->highest_lnum < 0 || 1093 sv->leb_count < 0 || sv->vol_type < 0 || sv->used_ebs < 0 || 1094 sv->data_pad < 0 || sv->last_data_size < 0) { 1095 ubi_err("negative values"); 1096 goto bad_sv; 1097 } 1098 1099 if (sv->vol_id >= UBI_MAX_VOLUMES && 1100 sv->vol_id < UBI_INTERNAL_VOL_START) { 1101 ubi_err("bad vol_id"); 1102 goto bad_sv; 1103 } 1104 1105 if (sv->vol_id > si->highest_vol_id) { 1106 ubi_err("highest_vol_id is %d, but vol_id %d is there", 1107 si->highest_vol_id, sv->vol_id); 1108 goto out; 1109 } 1110 1111 if (sv->vol_type != UBI_DYNAMIC_VOLUME && 1112 sv->vol_type != UBI_STATIC_VOLUME) { 1113 ubi_err("bad vol_type"); 1114 goto bad_sv; 1115 } 1116 1117 if (sv->data_pad > ubi->leb_size / 2) { 1118 ubi_err("bad data_pad"); 1119 goto bad_sv; 1120 } 1121 1122 last_seb = NULL; 1123 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) { 1124 cond_resched(); 1125 1126 last_seb = seb; 1127 leb_count += 1; 1128 1129 if (seb->pnum < 0 || seb->ec < 0) { 1130 ubi_err("negative values"); 1131 goto bad_seb; 1132 } 1133 1134 if (seb->ec < si->min_ec) { 1135 ubi_err("bad si->min_ec (%d), %d found", 1136 si->min_ec, seb->ec); 1137 goto bad_seb; 1138 } 1139 1140 if (seb->ec > si->max_ec) { 1141 ubi_err("bad si->max_ec (%d), %d found", 1142 si->max_ec, seb->ec); 1143 goto bad_seb; 1144 } 1145 1146 if (seb->pnum >= ubi->peb_count) { 1147 ubi_err("too high PEB number %d, total PEBs %d", 1148 seb->pnum, ubi->peb_count); 1149 goto bad_seb; 1150 } 1151 1152 if (sv->vol_type == UBI_STATIC_VOLUME) { 1153 if (seb->lnum >= sv->used_ebs) { 1154 ubi_err("bad lnum or used_ebs"); 1155 goto bad_seb; 1156 } 1157 } else { 1158 if (sv->used_ebs != 0) { 1159 ubi_err("non-zero used_ebs"); 1160 goto bad_seb; 1161 } 1162 } 1163 1164 if (seb->lnum > sv->highest_lnum) { 1165 ubi_err("incorrect highest_lnum or lnum"); 1166 goto bad_seb; 1167 } 1168 } 1169 1170 if (sv->leb_count != leb_count) { 1171 ubi_err("bad leb_count, %d objects in the tree", 1172 leb_count); 1173 goto bad_sv; 1174 } 1175 1176 if (!last_seb) 1177 continue; 1178 1179 seb = last_seb; 1180 1181 if (seb->lnum != sv->highest_lnum) { 1182 ubi_err("bad highest_lnum"); 1183 goto bad_seb; 1184 } 1185 } 1186 1187 if (vols_found != si->vols_found) { 1188 ubi_err("bad si->vols_found %d, should be %d", 1189 si->vols_found, vols_found); 1190 goto out; 1191 } 1192 1193 /* Check that scanning information is correct */ 1194 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) { 1195 last_seb = NULL; 1196 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) { 1197 int vol_type; 1198 1199 cond_resched(); 1200 1201 last_seb = seb; 1202 1203 err = ubi_io_read_vid_hdr(ubi, seb->pnum, vidh, 1); 1204 if (err && err != UBI_IO_BITFLIPS) { 1205 ubi_err("VID header is not OK (%d)", err); 1206 if (err > 0) 1207 err = -EIO; 1208 return err; 1209 } 1210 1211 vol_type = vidh->vol_type == UBI_VID_DYNAMIC ? 1212 UBI_DYNAMIC_VOLUME : UBI_STATIC_VOLUME; 1213 if (sv->vol_type != vol_type) { 1214 ubi_err("bad vol_type"); 1215 goto bad_vid_hdr; 1216 } 1217 1218 if (seb->sqnum != ubi64_to_cpu(vidh->sqnum)) { 1219 ubi_err("bad sqnum %llu", seb->sqnum); 1220 goto bad_vid_hdr; 1221 } 1222 1223 if (sv->vol_id != ubi32_to_cpu(vidh->vol_id)) { 1224 ubi_err("bad vol_id %d", sv->vol_id); 1225 goto bad_vid_hdr; 1226 } 1227 1228 if (sv->compat != vidh->compat) { 1229 ubi_err("bad compat %d", vidh->compat); 1230 goto bad_vid_hdr; 1231 } 1232 1233 if (seb->lnum != ubi32_to_cpu(vidh->lnum)) { 1234 ubi_err("bad lnum %d", seb->lnum); 1235 goto bad_vid_hdr; 1236 } 1237 1238 if (sv->used_ebs != ubi32_to_cpu(vidh->used_ebs)) { 1239 ubi_err("bad used_ebs %d", sv->used_ebs); 1240 goto bad_vid_hdr; 1241 } 1242 1243 if (sv->data_pad != ubi32_to_cpu(vidh->data_pad)) { 1244 ubi_err("bad data_pad %d", sv->data_pad); 1245 goto bad_vid_hdr; 1246 } 1247 1248 if (seb->leb_ver != ubi32_to_cpu(vidh->leb_ver)) { 1249 ubi_err("bad leb_ver %u", seb->leb_ver); 1250 goto bad_vid_hdr; 1251 } 1252 } 1253 1254 if (!last_seb) 1255 continue; 1256 1257 if (sv->highest_lnum != ubi32_to_cpu(vidh->lnum)) { 1258 ubi_err("bad highest_lnum %d", sv->highest_lnum); 1259 goto bad_vid_hdr; 1260 } 1261 1262 if (sv->last_data_size != ubi32_to_cpu(vidh->data_size)) { 1263 ubi_err("bad last_data_size %d", sv->last_data_size); 1264 goto bad_vid_hdr; 1265 } 1266 } 1267 1268 /* 1269 * Make sure that all the physical eraseblocks are in one of the lists 1270 * or trees. 1271 */ 1272 buf = kmalloc(ubi->peb_count, GFP_KERNEL); 1273 if (!buf) 1274 return -ENOMEM; 1275 1276 memset(buf, 1, ubi->peb_count); 1277 for (pnum = 0; pnum < ubi->peb_count; pnum++) { 1278 err = ubi_io_is_bad(ubi, pnum); 1279 if (err < 0) 1280 return err; 1281 else if (err) 1282 buf[pnum] = 0; 1283 } 1284 1285 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) 1286 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) 1287 buf[seb->pnum] = 0; 1288 1289 list_for_each_entry(seb, &si->free, u.list) 1290 buf[seb->pnum] = 0; 1291 1292 list_for_each_entry(seb, &si->corr, u.list) 1293 buf[seb->pnum] = 0; 1294 1295 list_for_each_entry(seb, &si->erase, u.list) 1296 buf[seb->pnum] = 0; 1297 1298 list_for_each_entry(seb, &si->alien, u.list) 1299 buf[seb->pnum] = 0; 1300 1301 err = 0; 1302 for (pnum = 0; pnum < ubi->peb_count; pnum++) 1303 if (buf[pnum]) { 1304 ubi_err("PEB %d is not referred", pnum); 1305 err = 1; 1306 } 1307 1308 kfree(buf); 1309 if (err) 1310 goto out; 1311 return 0; 1312 1313bad_seb: 1314 ubi_err("bad scanning information about LEB %d", seb->lnum); 1315 ubi_dbg_dump_seb(seb, 0); 1316 ubi_dbg_dump_sv(sv); 1317 goto out; 1318 1319bad_sv: 1320 ubi_err("bad scanning information about volume %d", sv->vol_id); 1321 ubi_dbg_dump_sv(sv); 1322 goto out; 1323 1324bad_vid_hdr: 1325 ubi_err("bad scanning information about volume %d", sv->vol_id); 1326 ubi_dbg_dump_sv(sv); 1327 ubi_dbg_dump_vid_hdr(vidh); 1328 1329out: 1330 ubi_dbg_dump_stack(); 1331 return 1; 1332} 1333 1334#endif /* CONFIG_MTD_UBI_DEBUG_PARANOID */ 1335