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 * Authors: Artem Bityutskiy (���������������� ����������), Thomas Gleixner 19 */ 20 21 22#include <linux/slab.h> 23#include <linux/crc32.h> 24#include <linux/freezer.h> 25#include <linux/kthread.h> 26#include "ubi.h" 27 28/* Number of physical eraseblocks reserved for wear-leveling purposes */ 29#define WL_RESERVED_PEBS 1 30 31/* 32 * How many erase cycles are short term, unknown, and long term physical 33 * eraseblocks protected. 34 */ 35#define ST_PROTECTION 16 36#define U_PROTECTION 10 37#define LT_PROTECTION 4 38 39/* 40 * Maximum difference between two erase counters. If this threshold is 41 * exceeded, the WL unit starts moving data from used physical eraseblocks with 42 * low erase counter to free physical eraseblocks with high erase counter. 43 */ 44#define UBI_WL_THRESHOLD CONFIG_MTD_UBI_WL_THRESHOLD 45 46/* 47 * When a physical eraseblock is moved, the WL unit has to pick the target 48 * physical eraseblock to move to. The simplest way would be just to pick the 49 * one with the highest erase counter. But in certain workloads this could lead 50 * to an unlimited wear of one or few physical eraseblock. Indeed, imagine a 51 * situation when the picked physical eraseblock is constantly erased after the 52 * data is written to it. So, we have a constant which limits the highest erase 53 * counter of the free physical eraseblock to pick. Namely, the WL unit does 54 * not pick eraseblocks with erase counter greater then the lowest erase 55 * counter plus %WL_FREE_MAX_DIFF. 56 */ 57#define WL_FREE_MAX_DIFF (2*UBI_WL_THRESHOLD) 58 59/* 60 * Maximum number of consecutive background thread failures which is enough to 61 * switch to read-only mode. 62 */ 63#define WL_MAX_FAILURES 32 64 65/** 66 * struct ubi_wl_entry - wear-leveling entry. 67 * @rb: link in the corresponding RB-tree 68 * @ec: erase counter 69 * @pnum: physical eraseblock number 70 * 71 * Each physical eraseblock has a corresponding &struct wl_entry object which 72 * may be kept in different RB-trees. 73 */ 74struct ubi_wl_entry { 75 struct rb_node rb; 76 int ec; 77 int pnum; 78}; 79 80/** 81 * struct ubi_wl_prot_entry - PEB protection entry. 82 * @rb_pnum: link in the @wl->prot.pnum RB-tree 83 * @rb_aec: link in the @wl->prot.aec RB-tree 84 * @abs_ec: the absolute erase counter value when the protection ends 85 * @e: the wear-leveling entry of the physical eraseblock under protection 86 * 87 * When the WL unit returns a physical eraseblock, the physical eraseblock is 88 * protected from being moved for some "time". For this reason, the physical 89 * eraseblock is not directly moved from the @wl->free tree to the @wl->used 90 * tree. There is one more tree in between where this physical eraseblock is 91 * temporarily stored (@wl->prot). 92 * 93 * All this protection stuff is needed because: 94 * o we don't want to move physical eraseblocks just after we have given them 95 * to the user; instead, we first want to let users fill them up with data; 96 * 97 * o there is a chance that the user will put the physical eraseblock very 98 * soon, so it makes sense not to move it for some time, but wait; this is 99 * especially important in case of "short term" physical eraseblocks. 100 * 101 * Physical eraseblocks stay protected only for limited time. But the "time" is 102 * measured in erase cycles in this case. This is implemented with help of the 103 * absolute erase counter (@wl->abs_ec). When it reaches certain value, the 104 * physical eraseblocks are moved from the protection trees (@wl->prot.*) to 105 * the @wl->used tree. 106 * 107 * Protected physical eraseblocks are searched by physical eraseblock number 108 * (when they are put) and by the absolute erase counter (to check if it is 109 * time to move them to the @wl->used tree). So there are actually 2 RB-trees 110 * storing the protected physical eraseblocks: @wl->prot.pnum and 111 * @wl->prot.aec. They are referred to as the "protection" trees. The 112 * first one is indexed by the physical eraseblock number. The second one is 113 * indexed by the absolute erase counter. Both trees store 114 * &struct ubi_wl_prot_entry objects. 115 * 116 * Each physical eraseblock has 2 main states: free and used. The former state 117 * corresponds to the @wl->free tree. The latter state is split up on several 118 * sub-states: 119 * o the WL movement is allowed (@wl->used tree); 120 * o the WL movement is temporarily prohibited (@wl->prot.pnum and 121 * @wl->prot.aec trees); 122 * o scrubbing is needed (@wl->scrub tree). 123 * 124 * Depending on the sub-state, wear-leveling entries of the used physical 125 * eraseblocks may be kept in one of those trees. 126 */ 127struct ubi_wl_prot_entry { 128 struct rb_node rb_pnum; 129 struct rb_node rb_aec; 130 unsigned long long abs_ec; 131 struct ubi_wl_entry *e; 132}; 133 134/** 135 * struct ubi_work - UBI work description data structure. 136 * @list: a link in the list of pending works 137 * @func: worker function 138 * @priv: private data of the worker function 139 * 140 * @e: physical eraseblock to erase 141 * @torture: if the physical eraseblock has to be tortured 142 * 143 * The @func pointer points to the worker function. If the @cancel argument is 144 * not zero, the worker has to free the resources and exit immediately. The 145 * worker has to return zero in case of success and a negative error code in 146 * case of failure. 147 */ 148struct ubi_work { 149 struct list_head list; 150 int (*func)(struct ubi_device *ubi, struct ubi_work *wrk, int cancel); 151 /* The below fields are only relevant to erasure works */ 152 struct ubi_wl_entry *e; 153 int torture; 154}; 155 156#ifdef CONFIG_MTD_UBI_DEBUG_PARANOID 157static int paranoid_check_ec(const struct ubi_device *ubi, int pnum, int ec); 158static int paranoid_check_in_wl_tree(struct ubi_wl_entry *e, 159 struct rb_root *root); 160#else 161#define paranoid_check_ec(ubi, pnum, ec) 0 162#define paranoid_check_in_wl_tree(e, root) 163#endif 164 165/* Slab cache for wear-leveling entries */ 166static struct kmem_cache *wl_entries_slab; 167 168/** 169 * tree_empty - a helper function to check if an RB-tree is empty. 170 * @root: the root of the tree 171 * 172 * This function returns non-zero if the RB-tree is empty and zero if not. 173 */ 174static inline int tree_empty(struct rb_root *root) 175{ 176 return root->rb_node == NULL; 177} 178 179/** 180 * wl_tree_add - add a wear-leveling entry to a WL RB-tree. 181 * @e: the wear-leveling entry to add 182 * @root: the root of the tree 183 * 184 * Note, we use (erase counter, physical eraseblock number) pairs as keys in 185 * the @ubi->used and @ubi->free RB-trees. 186 */ 187static void wl_tree_add(struct ubi_wl_entry *e, struct rb_root *root) 188{ 189 struct rb_node **p, *parent = NULL; 190 191 p = &root->rb_node; 192 while (*p) { 193 struct ubi_wl_entry *e1; 194 195 parent = *p; 196 e1 = rb_entry(parent, struct ubi_wl_entry, rb); 197 198 if (e->ec < e1->ec) 199 p = &(*p)->rb_left; 200 else if (e->ec > e1->ec) 201 p = &(*p)->rb_right; 202 else { 203 ubi_assert(e->pnum != e1->pnum); 204 if (e->pnum < e1->pnum) 205 p = &(*p)->rb_left; 206 else 207 p = &(*p)->rb_right; 208 } 209 } 210 211 rb_link_node(&e->rb, parent, p); 212 rb_insert_color(&e->rb, root); 213} 214 215 216/* 217 * Helper functions to add and delete wear-leveling entries from different 218 * trees. 219 */ 220 221static void free_tree_add(struct ubi_device *ubi, struct ubi_wl_entry *e) 222{ 223 wl_tree_add(e, &ubi->free); 224} 225static inline void used_tree_add(struct ubi_device *ubi, 226 struct ubi_wl_entry *e) 227{ 228 wl_tree_add(e, &ubi->used); 229} 230static inline void scrub_tree_add(struct ubi_device *ubi, 231 struct ubi_wl_entry *e) 232{ 233 wl_tree_add(e, &ubi->scrub); 234} 235static inline void free_tree_del(struct ubi_device *ubi, 236 struct ubi_wl_entry *e) 237{ 238 paranoid_check_in_wl_tree(e, &ubi->free); 239 rb_erase(&e->rb, &ubi->free); 240} 241static inline void used_tree_del(struct ubi_device *ubi, 242 struct ubi_wl_entry *e) 243{ 244 paranoid_check_in_wl_tree(e, &ubi->used); 245 rb_erase(&e->rb, &ubi->used); 246} 247static inline void scrub_tree_del(struct ubi_device *ubi, 248 struct ubi_wl_entry *e) 249{ 250 paranoid_check_in_wl_tree(e, &ubi->scrub); 251 rb_erase(&e->rb, &ubi->scrub); 252} 253 254/** 255 * do_work - do one pending work. 256 * @ubi: UBI device description object 257 * 258 * This function returns zero in case of success and a negative error code in 259 * case of failure. 260 */ 261static int do_work(struct ubi_device *ubi) 262{ 263 int err; 264 struct ubi_work *wrk; 265 266 spin_lock(&ubi->wl_lock); 267 268 if (list_empty(&ubi->works)) { 269 spin_unlock(&ubi->wl_lock); 270 return 0; 271 } 272 273 wrk = list_entry(ubi->works.next, struct ubi_work, list); 274 list_del(&wrk->list); 275 spin_unlock(&ubi->wl_lock); 276 277 /* 278 * Call the worker function. Do not touch the work structure 279 * after this call as it will have been freed or reused by that 280 * time by the worker function. 281 */ 282 err = wrk->func(ubi, wrk, 0); 283 if (err) 284 ubi_err("work failed with error code %d", err); 285 286 spin_lock(&ubi->wl_lock); 287 ubi->works_count -= 1; 288 ubi_assert(ubi->works_count >= 0); 289 spin_unlock(&ubi->wl_lock); 290 return err; 291} 292 293/** 294 * produce_free_peb - produce a free physical eraseblock. 295 * @ubi: UBI device description object 296 * 297 * This function tries to make a free PEB by means of synchronous execution of 298 * pending works. This may be needed if, for example the background thread is 299 * disabled. Returns zero in case of success and a negative error code in case 300 * of failure. 301 */ 302static int produce_free_peb(struct ubi_device *ubi) 303{ 304 int err; 305 306 spin_lock(&ubi->wl_lock); 307 while (tree_empty(&ubi->free)) { 308 spin_unlock(&ubi->wl_lock); 309 310 dbg_wl("do one work synchronously"); 311 err = do_work(ubi); 312 if (err) 313 return err; 314 315 spin_lock(&ubi->wl_lock); 316 } 317 spin_unlock(&ubi->wl_lock); 318 319 return 0; 320} 321 322/** 323 * in_wl_tree - check if wear-leveling entry is present in a WL RB-tree. 324 * @e: the wear-leveling entry to check 325 * @root: the root of the tree 326 * 327 * This function returns non-zero if @e is in the @root RB-tree and zero if it 328 * is not. 329 */ 330static int in_wl_tree(struct ubi_wl_entry *e, struct rb_root *root) 331{ 332 struct rb_node *p; 333 334 p = root->rb_node; 335 while (p) { 336 struct ubi_wl_entry *e1; 337 338 e1 = rb_entry(p, struct ubi_wl_entry, rb); 339 340 if (e->pnum == e1->pnum) { 341 ubi_assert(e == e1); 342 return 1; 343 } 344 345 if (e->ec < e1->ec) 346 p = p->rb_left; 347 else if (e->ec > e1->ec) 348 p = p->rb_right; 349 else { 350 ubi_assert(e->pnum != e1->pnum); 351 if (e->pnum < e1->pnum) 352 p = p->rb_left; 353 else 354 p = p->rb_right; 355 } 356 } 357 358 return 0; 359} 360 361/** 362 * prot_tree_add - add physical eraseblock to protection trees. 363 * @ubi: UBI device description object 364 * @e: the physical eraseblock to add 365 * @pe: protection entry object to use 366 * @abs_ec: absolute erase counter value when this physical eraseblock has 367 * to be removed from the protection trees. 368 * 369 * @wl->lock has to be locked. 370 */ 371static void prot_tree_add(struct ubi_device *ubi, struct ubi_wl_entry *e, 372 struct ubi_wl_prot_entry *pe, int abs_ec) 373{ 374 struct rb_node **p, *parent = NULL; 375 struct ubi_wl_prot_entry *pe1; 376 377 pe->e = e; 378 pe->abs_ec = ubi->abs_ec + abs_ec; 379 380 p = &ubi->prot.pnum.rb_node; 381 while (*p) { 382 parent = *p; 383 pe1 = rb_entry(parent, struct ubi_wl_prot_entry, rb_pnum); 384 385 if (e->pnum < pe1->e->pnum) 386 p = &(*p)->rb_left; 387 else 388 p = &(*p)->rb_right; 389 } 390 rb_link_node(&pe->rb_pnum, parent, p); 391 rb_insert_color(&pe->rb_pnum, &ubi->prot.pnum); 392 393 p = &ubi->prot.aec.rb_node; 394 parent = NULL; 395 while (*p) { 396 parent = *p; 397 pe1 = rb_entry(parent, struct ubi_wl_prot_entry, rb_aec); 398 399 if (pe->abs_ec < pe1->abs_ec) 400 p = &(*p)->rb_left; 401 else 402 p = &(*p)->rb_right; 403 } 404 rb_link_node(&pe->rb_aec, parent, p); 405 rb_insert_color(&pe->rb_aec, &ubi->prot.aec); 406} 407 408/** 409 * find_wl_entry - find wear-leveling entry closest to certain erase counter. 410 * @root: the RB-tree where to look for 411 * @max: highest possible erase counter 412 * 413 * This function looks for a wear leveling entry with erase counter closest to 414 * @max and less then @max. 415 */ 416static struct ubi_wl_entry *find_wl_entry(struct rb_root *root, int max) 417{ 418 struct rb_node *p; 419 struct ubi_wl_entry *e; 420 421 e = rb_entry(rb_first(root), struct ubi_wl_entry, rb); 422 max += e->ec; 423 424 p = root->rb_node; 425 while (p) { 426 struct ubi_wl_entry *e1; 427 428 e1 = rb_entry(p, struct ubi_wl_entry, rb); 429 if (e1->ec >= max) 430 p = p->rb_left; 431 else { 432 p = p->rb_right; 433 e = e1; 434 } 435 } 436 437 return e; 438} 439 440/** 441 * ubi_wl_get_peb - get a physical eraseblock. 442 * @ubi: UBI device description object 443 * @dtype: type of data which will be stored in this physical eraseblock 444 * 445 * This function returns a physical eraseblock in case of success and a 446 * negative error code in case of failure. Might sleep. 447 */ 448int ubi_wl_get_peb(struct ubi_device *ubi, int dtype) 449{ 450 int err, protect, medium_ec; 451 struct ubi_wl_entry *e, *first, *last; 452 struct ubi_wl_prot_entry *pe; 453 454 ubi_assert(dtype == UBI_LONGTERM || dtype == UBI_SHORTTERM || 455 dtype == UBI_UNKNOWN); 456 457 pe = kmalloc(sizeof(struct ubi_wl_prot_entry), GFP_KERNEL); 458 if (!pe) 459 return -ENOMEM; 460 461retry: 462 spin_lock(&ubi->wl_lock); 463 if (tree_empty(&ubi->free)) { 464 if (ubi->works_count == 0) { 465 ubi_assert(list_empty(&ubi->works)); 466 ubi_err("no free eraseblocks"); 467 spin_unlock(&ubi->wl_lock); 468 kfree(pe); 469 return -ENOSPC; 470 } 471 spin_unlock(&ubi->wl_lock); 472 473 err = produce_free_peb(ubi); 474 if (err < 0) { 475 kfree(pe); 476 return err; 477 } 478 goto retry; 479 } 480 481 switch (dtype) { 482 case UBI_LONGTERM: 483 /* 484 * For long term data we pick a physical eraseblock 485 * with high erase counter. But the highest erase 486 * counter we can pick is bounded by the the lowest 487 * erase counter plus %WL_FREE_MAX_DIFF. 488 */ 489 e = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF); 490 protect = LT_PROTECTION; 491 break; 492 case UBI_UNKNOWN: 493 /* 494 * For unknown data we pick a physical eraseblock with 495 * medium erase counter. But we by no means can pick a 496 * physical eraseblock with erase counter greater or 497 * equivalent than the lowest erase counter plus 498 * %WL_FREE_MAX_DIFF. 499 */ 500 first = rb_entry(rb_first(&ubi->free), 501 struct ubi_wl_entry, rb); 502 last = rb_entry(rb_last(&ubi->free), 503 struct ubi_wl_entry, rb); 504 505 if (last->ec - first->ec < WL_FREE_MAX_DIFF) 506 e = rb_entry(ubi->free.rb_node, 507 struct ubi_wl_entry, rb); 508 else { 509 medium_ec = (first->ec + WL_FREE_MAX_DIFF)/2; 510 e = find_wl_entry(&ubi->free, medium_ec); 511 } 512 protect = U_PROTECTION; 513 break; 514 case UBI_SHORTTERM: 515 /* 516 * For short term data we pick a physical eraseblock 517 * with the lowest erase counter as we expect it will 518 * be erased soon. 519 */ 520 e = rb_entry(rb_first(&ubi->free), 521 struct ubi_wl_entry, rb); 522 protect = ST_PROTECTION; 523 break; 524 default: 525 protect = 0; 526 e = NULL; 527 BUG(); 528 } 529 530 /* 531 * Move the physical eraseblock to the protection trees where it will 532 * be protected from being moved for some time. 533 */ 534 free_tree_del(ubi, e); 535 prot_tree_add(ubi, e, pe, protect); 536 537 dbg_wl("PEB %d EC %d, protection %d", e->pnum, e->ec, protect); 538 spin_unlock(&ubi->wl_lock); 539 540 return e->pnum; 541} 542 543/** 544 * prot_tree_del - remove a physical eraseblock from the protection trees 545 * @ubi: UBI device description object 546 * @pnum: the physical eraseblock to remove 547 */ 548static void prot_tree_del(struct ubi_device *ubi, int pnum) 549{ 550 struct rb_node *p; 551 struct ubi_wl_prot_entry *pe = NULL; 552 553 p = ubi->prot.pnum.rb_node; 554 while (p) { 555 556 pe = rb_entry(p, struct ubi_wl_prot_entry, rb_pnum); 557 558 if (pnum == pe->e->pnum) 559 break; 560 561 if (pnum < pe->e->pnum) 562 p = p->rb_left; 563 else 564 p = p->rb_right; 565 } 566 567 ubi_assert(pe->e->pnum == pnum); 568 rb_erase(&pe->rb_aec, &ubi->prot.aec); 569 rb_erase(&pe->rb_pnum, &ubi->prot.pnum); 570 kfree(pe); 571} 572 573/** 574 * sync_erase - synchronously erase a physical eraseblock. 575 * @ubi: UBI device description object 576 * @e: the the physical eraseblock to erase 577 * @torture: if the physical eraseblock has to be tortured 578 * 579 * This function returns zero in case of success and a negative error code in 580 * case of failure. 581 */ 582static int sync_erase(struct ubi_device *ubi, struct ubi_wl_entry *e, int torture) 583{ 584 int err; 585 struct ubi_ec_hdr *ec_hdr; 586 unsigned long long ec = e->ec; 587 588 dbg_wl("erase PEB %d, old EC %llu", e->pnum, ec); 589 590 err = paranoid_check_ec(ubi, e->pnum, e->ec); 591 if (err > 0) 592 return -EINVAL; 593 594 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL); 595 if (!ec_hdr) 596 return -ENOMEM; 597 598 err = ubi_io_sync_erase(ubi, e->pnum, torture); 599 if (err < 0) 600 goto out_free; 601 602 ec += err; 603 if (ec > UBI_MAX_ERASECOUNTER) { 604 /* 605 * Erase counter overflow. Upgrade UBI and use 64-bit 606 * erase counters internally. 607 */ 608 ubi_err("erase counter overflow at PEB %d, EC %llu", 609 e->pnum, ec); 610 err = -EINVAL; 611 goto out_free; 612 } 613 614 dbg_wl("erased PEB %d, new EC %llu", e->pnum, ec); 615 616 ec_hdr->ec = cpu_to_ubi64(ec); 617 618 err = ubi_io_write_ec_hdr(ubi, e->pnum, ec_hdr); 619 if (err) 620 goto out_free; 621 622 e->ec = ec; 623 spin_lock(&ubi->wl_lock); 624 if (e->ec > ubi->max_ec) 625 ubi->max_ec = e->ec; 626 spin_unlock(&ubi->wl_lock); 627 628out_free: 629 kfree(ec_hdr); 630 return err; 631} 632 633/** 634 * check_protection_over - check if it is time to stop protecting some 635 * physical eraseblocks. 636 * @ubi: UBI device description object 637 * 638 * This function is called after each erase operation, when the absolute erase 639 * counter is incremented, to check if some physical eraseblock have not to be 640 * protected any longer. These physical eraseblocks are moved from the 641 * protection trees to the used tree. 642 */ 643static void check_protection_over(struct ubi_device *ubi) 644{ 645 struct ubi_wl_prot_entry *pe; 646 647 /* 648 * There may be several protected physical eraseblock to remove, 649 * process them all. 650 */ 651 while (1) { 652 spin_lock(&ubi->wl_lock); 653 if (tree_empty(&ubi->prot.aec)) { 654 spin_unlock(&ubi->wl_lock); 655 break; 656 } 657 658 pe = rb_entry(rb_first(&ubi->prot.aec), 659 struct ubi_wl_prot_entry, rb_aec); 660 661 if (pe->abs_ec > ubi->abs_ec) { 662 spin_unlock(&ubi->wl_lock); 663 break; 664 } 665 666 dbg_wl("PEB %d protection over, abs_ec %llu, PEB abs_ec %llu", 667 pe->e->pnum, ubi->abs_ec, pe->abs_ec); 668 rb_erase(&pe->rb_aec, &ubi->prot.aec); 669 rb_erase(&pe->rb_pnum, &ubi->prot.pnum); 670 used_tree_add(ubi, pe->e); 671 spin_unlock(&ubi->wl_lock); 672 673 kfree(pe); 674 cond_resched(); 675 } 676} 677 678/** 679 * schedule_ubi_work - schedule a work. 680 * @ubi: UBI device description object 681 * @wrk: the work to schedule 682 * 683 * This function enqueues a work defined by @wrk to the tail of the pending 684 * works list. 685 */ 686static void schedule_ubi_work(struct ubi_device *ubi, struct ubi_work *wrk) 687{ 688 spin_lock(&ubi->wl_lock); 689 list_add_tail(&wrk->list, &ubi->works); 690 ubi_assert(ubi->works_count >= 0); 691 ubi->works_count += 1; 692 if (ubi->thread_enabled) 693 wake_up_process(ubi->bgt_thread); 694 spin_unlock(&ubi->wl_lock); 695} 696 697static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk, 698 int cancel); 699 700/** 701 * schedule_erase - schedule an erase work. 702 * @ubi: UBI device description object 703 * @e: the WL entry of the physical eraseblock to erase 704 * @torture: if the physical eraseblock has to be tortured 705 * 706 * This function returns zero in case of success and a %-ENOMEM in case of 707 * failure. 708 */ 709static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e, 710 int torture) 711{ 712 struct ubi_work *wl_wrk; 713 714 dbg_wl("schedule erasure of PEB %d, EC %d, torture %d", 715 e->pnum, e->ec, torture); 716 717 wl_wrk = kmalloc(sizeof(struct ubi_work), GFP_KERNEL); 718 if (!wl_wrk) 719 return -ENOMEM; 720 721 wl_wrk->func = &erase_worker; 722 wl_wrk->e = e; 723 wl_wrk->torture = torture; 724 725 schedule_ubi_work(ubi, wl_wrk); 726 return 0; 727} 728 729/** 730 * wear_leveling_worker - wear-leveling worker function. 731 * @ubi: UBI device description object 732 * @wrk: the work object 733 * @cancel: non-zero if the worker has to free memory and exit 734 * 735 * This function copies a more worn out physical eraseblock to a less worn out 736 * one. Returns zero in case of success and a negative error code in case of 737 * failure. 738 */ 739static int wear_leveling_worker(struct ubi_device *ubi, struct ubi_work *wrk, 740 int cancel) 741{ 742 int err, put = 0; 743 struct ubi_wl_entry *e1, *e2; 744 struct ubi_vid_hdr *vid_hdr; 745 746 kfree(wrk); 747 748 if (cancel) 749 return 0; 750 751 vid_hdr = ubi_zalloc_vid_hdr(ubi); 752 if (!vid_hdr) 753 return -ENOMEM; 754 755 spin_lock(&ubi->wl_lock); 756 757 /* 758 * Only one WL worker at a time is supported at this implementation, so 759 * make sure a PEB is not being moved already. 760 */ 761 if (ubi->move_to || tree_empty(&ubi->free) || 762 (tree_empty(&ubi->used) && tree_empty(&ubi->scrub))) { 763 /* 764 * Only one WL worker at a time is supported at this 765 * implementation, so if a LEB is already being moved, cancel. 766 * 767 * No free physical eraseblocks? Well, we cancel wear-leveling 768 * then. It will be triggered again when a free physical 769 * eraseblock appears. 770 * 771 * No used physical eraseblocks? They must be temporarily 772 * protected from being moved. They will be moved to the 773 * @ubi->used tree later and the wear-leveling will be 774 * triggered again. 775 */ 776 dbg_wl("cancel WL, a list is empty: free %d, used %d", 777 tree_empty(&ubi->free), tree_empty(&ubi->used)); 778 ubi->wl_scheduled = 0; 779 spin_unlock(&ubi->wl_lock); 780 ubi_free_vid_hdr(ubi, vid_hdr); 781 return 0; 782 } 783 784 if (tree_empty(&ubi->scrub)) { 785 /* 786 * Now pick the least worn-out used physical eraseblock and a 787 * highly worn-out free physical eraseblock. If the erase 788 * counters differ much enough, start wear-leveling. 789 */ 790 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, rb); 791 e2 = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF); 792 793 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD)) { 794 dbg_wl("no WL needed: min used EC %d, max free EC %d", 795 e1->ec, e2->ec); 796 ubi->wl_scheduled = 0; 797 spin_unlock(&ubi->wl_lock); 798 ubi_free_vid_hdr(ubi, vid_hdr); 799 return 0; 800 } 801 used_tree_del(ubi, e1); 802 dbg_wl("move PEB %d EC %d to PEB %d EC %d", 803 e1->pnum, e1->ec, e2->pnum, e2->ec); 804 } else { 805 e1 = rb_entry(rb_first(&ubi->scrub), struct ubi_wl_entry, rb); 806 e2 = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF); 807 scrub_tree_del(ubi, e1); 808 dbg_wl("scrub PEB %d to PEB %d", e1->pnum, e2->pnum); 809 } 810 811 free_tree_del(ubi, e2); 812 ubi_assert(!ubi->move_from && !ubi->move_to); 813 ubi_assert(!ubi->move_to_put && !ubi->move_from_put); 814 ubi->move_from = e1; 815 ubi->move_to = e2; 816 spin_unlock(&ubi->wl_lock); 817 818 /* 819 * Now we are going to copy physical eraseblock @e1->pnum to @e2->pnum. 820 * We so far do not know which logical eraseblock our physical 821 * eraseblock (@e1) belongs to. We have to read the volume identifier 822 * header first. 823 */ 824 825 err = ubi_io_read_vid_hdr(ubi, e1->pnum, vid_hdr, 0); 826 if (err && err != UBI_IO_BITFLIPS) { 827 if (err == UBI_IO_PEB_FREE) { 828 /* 829 * We are trying to move PEB without a VID header. UBI 830 * always write VID headers shortly after the PEB was 831 * given, so we have a situation when it did not have 832 * chance to write it down because it was preempted. 833 * Just re-schedule the work, so that next time it will 834 * likely have the VID header in place. 835 */ 836 dbg_wl("PEB %d has no VID header", e1->pnum); 837 err = 0; 838 } else { 839 ubi_err("error %d while reading VID header from PEB %d", 840 err, e1->pnum); 841 if (err > 0) 842 err = -EIO; 843 } 844 goto error; 845 } 846 847 err = ubi_eba_copy_leb(ubi, e1->pnum, e2->pnum, vid_hdr); 848 if (err) { 849 if (err == UBI_IO_BITFLIPS) 850 err = 0; 851 goto error; 852 } 853 854 ubi_free_vid_hdr(ubi, vid_hdr); 855 spin_lock(&ubi->wl_lock); 856 if (!ubi->move_to_put) 857 used_tree_add(ubi, e2); 858 else 859 put = 1; 860 ubi->move_from = ubi->move_to = NULL; 861 ubi->move_from_put = ubi->move_to_put = 0; 862 ubi->wl_scheduled = 0; 863 spin_unlock(&ubi->wl_lock); 864 865 if (put) { 866 /* 867 * Well, the target PEB was put meanwhile, schedule it for 868 * erasure. 869 */ 870 dbg_wl("PEB %d was put meanwhile, erase", e2->pnum); 871 err = schedule_erase(ubi, e2, 0); 872 if (err) { 873 kmem_cache_free(wl_entries_slab, e2); 874 ubi_ro_mode(ubi); 875 } 876 } 877 878 err = schedule_erase(ubi, e1, 0); 879 if (err) { 880 kmem_cache_free(wl_entries_slab, e1); 881 ubi_ro_mode(ubi); 882 } 883 884 dbg_wl("done"); 885 return err; 886 887 /* 888 * Some error occurred. @e1 was not changed, so return it back. @e2 889 * might be changed, schedule it for erasure. 890 */ 891error: 892 if (err) 893 dbg_wl("error %d occurred, cancel operation", err); 894 ubi_assert(err <= 0); 895 896 ubi_free_vid_hdr(ubi, vid_hdr); 897 spin_lock(&ubi->wl_lock); 898 ubi->wl_scheduled = 0; 899 if (ubi->move_from_put) 900 put = 1; 901 else 902 used_tree_add(ubi, e1); 903 ubi->move_from = ubi->move_to = NULL; 904 ubi->move_from_put = ubi->move_to_put = 0; 905 spin_unlock(&ubi->wl_lock); 906 907 if (put) { 908 /* 909 * Well, the target PEB was put meanwhile, schedule it for 910 * erasure. 911 */ 912 dbg_wl("PEB %d was put meanwhile, erase", e1->pnum); 913 err = schedule_erase(ubi, e1, 0); 914 if (err) { 915 kmem_cache_free(wl_entries_slab, e1); 916 ubi_ro_mode(ubi); 917 } 918 } 919 920 err = schedule_erase(ubi, e2, 0); 921 if (err) { 922 kmem_cache_free(wl_entries_slab, e2); 923 ubi_ro_mode(ubi); 924 } 925 926 yield(); 927 return err; 928} 929 930/** 931 * ensure_wear_leveling - schedule wear-leveling if it is needed. 932 * @ubi: UBI device description object 933 * 934 * This function checks if it is time to start wear-leveling and schedules it 935 * if yes. This function returns zero in case of success and a negative error 936 * code in case of failure. 937 */ 938static int ensure_wear_leveling(struct ubi_device *ubi) 939{ 940 int err = 0; 941 struct ubi_wl_entry *e1; 942 struct ubi_wl_entry *e2; 943 struct ubi_work *wrk; 944 945 spin_lock(&ubi->wl_lock); 946 if (ubi->wl_scheduled) 947 /* Wear-leveling is already in the work queue */ 948 goto out_unlock; 949 950 /* 951 * If the ubi->scrub tree is not empty, scrubbing is needed, and the 952 * the WL worker has to be scheduled anyway. 953 */ 954 if (tree_empty(&ubi->scrub)) { 955 if (tree_empty(&ubi->used) || tree_empty(&ubi->free)) 956 /* No physical eraseblocks - no deal */ 957 goto out_unlock; 958 959 /* 960 * We schedule wear-leveling only if the difference between the 961 * lowest erase counter of used physical eraseblocks and a high 962 * erase counter of free physical eraseblocks is greater then 963 * %UBI_WL_THRESHOLD. 964 */ 965 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, rb); 966 e2 = find_wl_entry(&ubi->free, WL_FREE_MAX_DIFF); 967 968 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD)) 969 goto out_unlock; 970 dbg_wl("schedule wear-leveling"); 971 } else 972 dbg_wl("schedule scrubbing"); 973 974 ubi->wl_scheduled = 1; 975 spin_unlock(&ubi->wl_lock); 976 977 wrk = kmalloc(sizeof(struct ubi_work), GFP_KERNEL); 978 if (!wrk) { 979 err = -ENOMEM; 980 goto out_cancel; 981 } 982 983 wrk->func = &wear_leveling_worker; 984 schedule_ubi_work(ubi, wrk); 985 return err; 986 987out_cancel: 988 spin_lock(&ubi->wl_lock); 989 ubi->wl_scheduled = 0; 990out_unlock: 991 spin_unlock(&ubi->wl_lock); 992 return err; 993} 994 995/** 996 * erase_worker - physical eraseblock erase worker function. 997 * @ubi: UBI device description object 998 * @wl_wrk: the work object 999 * @cancel: non-zero if the worker has to free memory and exit 1000 * 1001 * This function erases a physical eraseblock and perform torture testing if 1002 * needed. It also takes care about marking the physical eraseblock bad if 1003 * needed. Returns zero in case of success and a negative error code in case of 1004 * failure. 1005 */ 1006static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk, 1007 int cancel) 1008{ 1009 int err; 1010 struct ubi_wl_entry *e = wl_wrk->e; 1011 int pnum = e->pnum; 1012 1013 if (cancel) { 1014 dbg_wl("cancel erasure of PEB %d EC %d", pnum, e->ec); 1015 kfree(wl_wrk); 1016 kmem_cache_free(wl_entries_slab, e); 1017 return 0; 1018 } 1019 1020 dbg_wl("erase PEB %d EC %d", pnum, e->ec); 1021 1022 err = sync_erase(ubi, e, wl_wrk->torture); 1023 if (!err) { 1024 /* Fine, we've erased it successfully */ 1025 kfree(wl_wrk); 1026 1027 spin_lock(&ubi->wl_lock); 1028 ubi->abs_ec += 1; 1029 free_tree_add(ubi, e); 1030 spin_unlock(&ubi->wl_lock); 1031 1032 /* 1033 * One more erase operation has happened, take care about protected 1034 * physical eraseblocks. 1035 */ 1036 check_protection_over(ubi); 1037 1038 /* And take care about wear-leveling */ 1039 err = ensure_wear_leveling(ubi); 1040 return err; 1041 } 1042 1043 kfree(wl_wrk); 1044 kmem_cache_free(wl_entries_slab, e); 1045 1046 if (err != -EIO) { 1047 /* 1048 * If this is not %-EIO, we have no idea what to do. Scheduling 1049 * this physical eraseblock for erasure again would cause 1050 * errors again and again. Well, lets switch to RO mode. 1051 */ 1052 ubi_ro_mode(ubi); 1053 return err; 1054 } 1055 1056 /* It is %-EIO, the PEB went bad */ 1057 1058 if (!ubi->bad_allowed) { 1059 ubi_err("bad physical eraseblock %d detected", pnum); 1060 ubi_ro_mode(ubi); 1061 err = -EIO; 1062 } else { 1063 int need; 1064 1065 spin_lock(&ubi->volumes_lock); 1066 need = ubi->beb_rsvd_level - ubi->beb_rsvd_pebs + 1; 1067 if (need > 0) { 1068 need = ubi->avail_pebs >= need ? need : ubi->avail_pebs; 1069 ubi->avail_pebs -= need; 1070 ubi->rsvd_pebs += need; 1071 ubi->beb_rsvd_pebs += need; 1072 if (need > 0) 1073 ubi_msg("reserve more %d PEBs", need); 1074 } 1075 1076 if (ubi->beb_rsvd_pebs == 0) { 1077 spin_unlock(&ubi->volumes_lock); 1078 ubi_err("no reserved physical eraseblocks"); 1079 ubi_ro_mode(ubi); 1080 return -EIO; 1081 } 1082 1083 spin_unlock(&ubi->volumes_lock); 1084 ubi_msg("mark PEB %d as bad", pnum); 1085 1086 err = ubi_io_mark_bad(ubi, pnum); 1087 if (err) { 1088 ubi_ro_mode(ubi); 1089 return err; 1090 } 1091 1092 spin_lock(&ubi->volumes_lock); 1093 ubi->beb_rsvd_pebs -= 1; 1094 ubi->bad_peb_count += 1; 1095 ubi->good_peb_count -= 1; 1096 ubi_calculate_reserved(ubi); 1097 if (ubi->beb_rsvd_pebs == 0) 1098 ubi_warn("last PEB from the reserved pool was used"); 1099 spin_unlock(&ubi->volumes_lock); 1100 } 1101 1102 return err; 1103} 1104 1105/** 1106 * ubi_wl_put_peb - return a physical eraseblock to the wear-leveling 1107 * unit. 1108 * @ubi: UBI device description object 1109 * @pnum: physical eraseblock to return 1110 * @torture: if this physical eraseblock has to be tortured 1111 * 1112 * This function is called to return physical eraseblock @pnum to the pool of 1113 * free physical eraseblocks. The @torture flag has to be set if an I/O error 1114 * occurred to this @pnum and it has to be tested. This function returns zero 1115 * in case of success and a negative error code in case of failure. 1116 */ 1117int ubi_wl_put_peb(struct ubi_device *ubi, int pnum, int torture) 1118{ 1119 int err; 1120 struct ubi_wl_entry *e; 1121 1122 dbg_wl("PEB %d", pnum); 1123 ubi_assert(pnum >= 0); 1124 ubi_assert(pnum < ubi->peb_count); 1125 1126 spin_lock(&ubi->wl_lock); 1127 1128 e = ubi->lookuptbl[pnum]; 1129 if (e == ubi->move_from) { 1130 /* 1131 * User is putting the physical eraseblock which was selected to 1132 * be moved. It will be scheduled for erasure in the 1133 * wear-leveling worker. 1134 */ 1135 dbg_wl("PEB %d is being moved", pnum); 1136 ubi_assert(!ubi->move_from_put); 1137 ubi->move_from_put = 1; 1138 spin_unlock(&ubi->wl_lock); 1139 return 0; 1140 } else if (e == ubi->move_to) { 1141 /* 1142 * User is putting the physical eraseblock which was selected 1143 * as the target the data is moved to. It may happen if the EBA 1144 * unit already re-mapped the LEB but the WL unit did has not 1145 * put the PEB to the "used" tree. 1146 */ 1147 dbg_wl("PEB %d is the target of data moving", pnum); 1148 ubi_assert(!ubi->move_to_put); 1149 ubi->move_to_put = 1; 1150 spin_unlock(&ubi->wl_lock); 1151 return 0; 1152 } else { 1153 if (in_wl_tree(e, &ubi->used)) 1154 used_tree_del(ubi, e); 1155 else if (in_wl_tree(e, &ubi->scrub)) 1156 scrub_tree_del(ubi, e); 1157 else 1158 prot_tree_del(ubi, e->pnum); 1159 } 1160 spin_unlock(&ubi->wl_lock); 1161 1162 err = schedule_erase(ubi, e, torture); 1163 if (err) { 1164 spin_lock(&ubi->wl_lock); 1165 used_tree_add(ubi, e); 1166 spin_unlock(&ubi->wl_lock); 1167 } 1168 1169 return err; 1170} 1171 1172/** 1173 * ubi_wl_scrub_peb - schedule a physical eraseblock for scrubbing. 1174 * @ubi: UBI device description object 1175 * @pnum: the physical eraseblock to schedule 1176 * 1177 * If a bit-flip in a physical eraseblock is detected, this physical eraseblock 1178 * needs scrubbing. This function schedules a physical eraseblock for 1179 * scrubbing which is done in background. This function returns zero in case of 1180 * success and a negative error code in case of failure. 1181 */ 1182int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum) 1183{ 1184 struct ubi_wl_entry *e; 1185 1186 ubi_msg("schedule PEB %d for scrubbing", pnum); 1187 1188retry: 1189 spin_lock(&ubi->wl_lock); 1190 e = ubi->lookuptbl[pnum]; 1191 if (e == ubi->move_from || in_wl_tree(e, &ubi->scrub)) { 1192 spin_unlock(&ubi->wl_lock); 1193 return 0; 1194 } 1195 1196 if (e == ubi->move_to) { 1197 /* 1198 * This physical eraseblock was used to move data to. The data 1199 * was moved but the PEB was not yet inserted to the proper 1200 * tree. We should just wait a little and let the WL worker 1201 * proceed. 1202 */ 1203 spin_unlock(&ubi->wl_lock); 1204 dbg_wl("the PEB %d is not in proper tree, retry", pnum); 1205 yield(); 1206 goto retry; 1207 } 1208 1209 if (in_wl_tree(e, &ubi->used)) 1210 used_tree_del(ubi, e); 1211 else 1212 prot_tree_del(ubi, pnum); 1213 1214 scrub_tree_add(ubi, e); 1215 spin_unlock(&ubi->wl_lock); 1216 1217 /* 1218 * Technically scrubbing is the same as wear-leveling, so it is done 1219 * by the WL worker. 1220 */ 1221 return ensure_wear_leveling(ubi); 1222} 1223 1224/** 1225 * ubi_wl_flush - flush all pending works. 1226 * @ubi: UBI device description object 1227 * 1228 * This function returns zero in case of success and a negative error code in 1229 * case of failure. 1230 */ 1231int ubi_wl_flush(struct ubi_device *ubi) 1232{ 1233 int err, pending_count; 1234 1235 pending_count = ubi->works_count; 1236 1237 dbg_wl("flush (%d pending works)", pending_count); 1238 1239 /* 1240 * Erase while the pending works queue is not empty, but not more then 1241 * the number of currently pending works. 1242 */ 1243 while (pending_count-- > 0) { 1244 err = do_work(ubi); 1245 if (err) 1246 return err; 1247 } 1248 1249 return 0; 1250} 1251 1252/** 1253 * tree_destroy - destroy an RB-tree. 1254 * @root: the root of the tree to destroy 1255 */ 1256static void tree_destroy(struct rb_root *root) 1257{ 1258 struct rb_node *rb; 1259 struct ubi_wl_entry *e; 1260 1261 rb = root->rb_node; 1262 while (rb) { 1263 if (rb->rb_left) 1264 rb = rb->rb_left; 1265 else if (rb->rb_right) 1266 rb = rb->rb_right; 1267 else { 1268 e = rb_entry(rb, struct ubi_wl_entry, rb); 1269 1270 rb = rb_parent(rb); 1271 if (rb) { 1272 if (rb->rb_left == &e->rb) 1273 rb->rb_left = NULL; 1274 else 1275 rb->rb_right = NULL; 1276 } 1277 1278 kmem_cache_free(wl_entries_slab, e); 1279 } 1280 } 1281} 1282 1283/** 1284 * ubi_thread - UBI background thread. 1285 * @u: the UBI device description object pointer 1286 */ 1287static int ubi_thread(void *u) 1288{ 1289 int failures = 0; 1290 struct ubi_device *ubi = u; 1291 1292 ubi_msg("background thread \"%s\" started, PID %d", 1293 ubi->bgt_name, current->pid); 1294 1295 for (;;) { 1296 int err; 1297 1298 if (kthread_should_stop()) 1299 goto out; 1300 1301 if (try_to_freeze()) 1302 continue; 1303 1304 spin_lock(&ubi->wl_lock); 1305 if (list_empty(&ubi->works) || ubi->ro_mode || 1306 !ubi->thread_enabled) { 1307 set_current_state(TASK_INTERRUPTIBLE); 1308 spin_unlock(&ubi->wl_lock); 1309 schedule(); 1310 continue; 1311 } 1312 spin_unlock(&ubi->wl_lock); 1313 1314 err = do_work(ubi); 1315 if (err) { 1316 ubi_err("%s: work failed with error code %d", 1317 ubi->bgt_name, err); 1318 if (failures++ > WL_MAX_FAILURES) { 1319 /* 1320 * Too many failures, disable the thread and 1321 * switch to read-only mode. 1322 */ 1323 ubi_msg("%s: %d consecutive failures", 1324 ubi->bgt_name, WL_MAX_FAILURES); 1325 ubi_ro_mode(ubi); 1326 break; 1327 } 1328 } else 1329 failures = 0; 1330 1331 cond_resched(); 1332 } 1333 1334out: 1335 dbg_wl("background thread \"%s\" is killed", ubi->bgt_name); 1336 return 0; 1337} 1338 1339/** 1340 * cancel_pending - cancel all pending works. 1341 * @ubi: UBI device description object 1342 */ 1343static void cancel_pending(struct ubi_device *ubi) 1344{ 1345 while (!list_empty(&ubi->works)) { 1346 struct ubi_work *wrk; 1347 1348 wrk = list_entry(ubi->works.next, struct ubi_work, list); 1349 list_del(&wrk->list); 1350 wrk->func(ubi, wrk, 1); 1351 ubi->works_count -= 1; 1352 ubi_assert(ubi->works_count >= 0); 1353 } 1354} 1355 1356/** 1357 * ubi_wl_init_scan - initialize the wear-leveling unit using scanning 1358 * information. 1359 * @ubi: UBI device description object 1360 * @si: scanning information 1361 * 1362 * This function returns zero in case of success, and a negative error code in 1363 * case of failure. 1364 */ 1365int ubi_wl_init_scan(struct ubi_device *ubi, struct ubi_scan_info *si) 1366{ 1367 int err; 1368 struct rb_node *rb1, *rb2; 1369 struct ubi_scan_volume *sv; 1370 struct ubi_scan_leb *seb, *tmp; 1371 struct ubi_wl_entry *e; 1372 1373 1374 ubi->used = ubi->free = ubi->scrub = RB_ROOT; 1375 ubi->prot.pnum = ubi->prot.aec = RB_ROOT; 1376 spin_lock_init(&ubi->wl_lock); 1377 ubi->max_ec = si->max_ec; 1378 INIT_LIST_HEAD(&ubi->works); 1379 1380 sprintf(ubi->bgt_name, UBI_BGT_NAME_PATTERN, ubi->ubi_num); 1381 1382 ubi->bgt_thread = kthread_create(ubi_thread, ubi, ubi->bgt_name); 1383 if (IS_ERR(ubi->bgt_thread)) { 1384 err = PTR_ERR(ubi->bgt_thread); 1385 ubi_err("cannot spawn \"%s\", error %d", ubi->bgt_name, 1386 err); 1387 return err; 1388 } 1389 1390 if (ubi_devices_cnt == 0) { 1391 wl_entries_slab = kmem_cache_create("ubi_wl_entry_slab", 1392 sizeof(struct ubi_wl_entry), 1393 0, 0, NULL, NULL); 1394 if (!wl_entries_slab) 1395 return -ENOMEM; 1396 } 1397 1398 err = -ENOMEM; 1399 ubi->lookuptbl = kzalloc(ubi->peb_count * sizeof(void *), GFP_KERNEL); 1400 if (!ubi->lookuptbl) 1401 goto out_free; 1402 1403 list_for_each_entry_safe(seb, tmp, &si->erase, u.list) { 1404 cond_resched(); 1405 1406 e = kmem_cache_alloc(wl_entries_slab, GFP_KERNEL); 1407 if (!e) 1408 goto out_free; 1409 1410 e->pnum = seb->pnum; 1411 e->ec = seb->ec; 1412 ubi->lookuptbl[e->pnum] = e; 1413 if (schedule_erase(ubi, e, 0)) { 1414 kmem_cache_free(wl_entries_slab, e); 1415 goto out_free; 1416 } 1417 } 1418 1419 list_for_each_entry(seb, &si->free, u.list) { 1420 cond_resched(); 1421 1422 e = kmem_cache_alloc(wl_entries_slab, GFP_KERNEL); 1423 if (!e) 1424 goto out_free; 1425 1426 e->pnum = seb->pnum; 1427 e->ec = seb->ec; 1428 ubi_assert(e->ec >= 0); 1429 free_tree_add(ubi, e); 1430 ubi->lookuptbl[e->pnum] = e; 1431 } 1432 1433 list_for_each_entry(seb, &si->corr, u.list) { 1434 cond_resched(); 1435 1436 e = kmem_cache_alloc(wl_entries_slab, GFP_KERNEL); 1437 if (!e) 1438 goto out_free; 1439 1440 e->pnum = seb->pnum; 1441 e->ec = seb->ec; 1442 ubi->lookuptbl[e->pnum] = e; 1443 if (schedule_erase(ubi, e, 0)) { 1444 kmem_cache_free(wl_entries_slab, e); 1445 goto out_free; 1446 } 1447 } 1448 1449 ubi_rb_for_each_entry(rb1, sv, &si->volumes, rb) { 1450 ubi_rb_for_each_entry(rb2, seb, &sv->root, u.rb) { 1451 cond_resched(); 1452 1453 e = kmem_cache_alloc(wl_entries_slab, GFP_KERNEL); 1454 if (!e) 1455 goto out_free; 1456 1457 e->pnum = seb->pnum; 1458 e->ec = seb->ec; 1459 ubi->lookuptbl[e->pnum] = e; 1460 if (!seb->scrub) { 1461 dbg_wl("add PEB %d EC %d to the used tree", 1462 e->pnum, e->ec); 1463 used_tree_add(ubi, e); 1464 } else { 1465 dbg_wl("add PEB %d EC %d to the scrub tree", 1466 e->pnum, e->ec); 1467 scrub_tree_add(ubi, e); 1468 } 1469 } 1470 } 1471 1472 if (WL_RESERVED_PEBS > ubi->avail_pebs) { 1473 ubi_err("no enough physical eraseblocks (%d, need %d)", 1474 ubi->avail_pebs, WL_RESERVED_PEBS); 1475 goto out_free; 1476 } 1477 ubi->avail_pebs -= WL_RESERVED_PEBS; 1478 ubi->rsvd_pebs += WL_RESERVED_PEBS; 1479 1480 /* Schedule wear-leveling if needed */ 1481 err = ensure_wear_leveling(ubi); 1482 if (err) 1483 goto out_free; 1484 1485 return 0; 1486 1487out_free: 1488 cancel_pending(ubi); 1489 tree_destroy(&ubi->used); 1490 tree_destroy(&ubi->free); 1491 tree_destroy(&ubi->scrub); 1492 kfree(ubi->lookuptbl); 1493 if (ubi_devices_cnt == 0) 1494 kmem_cache_destroy(wl_entries_slab); 1495 return err; 1496} 1497 1498/** 1499 * protection_trees_destroy - destroy the protection RB-trees. 1500 * @ubi: UBI device description object 1501 */ 1502static void protection_trees_destroy(struct ubi_device *ubi) 1503{ 1504 struct rb_node *rb; 1505 struct ubi_wl_prot_entry *pe; 1506 1507 rb = ubi->prot.aec.rb_node; 1508 while (rb) { 1509 if (rb->rb_left) 1510 rb = rb->rb_left; 1511 else if (rb->rb_right) 1512 rb = rb->rb_right; 1513 else { 1514 pe = rb_entry(rb, struct ubi_wl_prot_entry, rb_aec); 1515 1516 rb = rb_parent(rb); 1517 if (rb) { 1518 if (rb->rb_left == &pe->rb_aec) 1519 rb->rb_left = NULL; 1520 else 1521 rb->rb_right = NULL; 1522 } 1523 1524 kmem_cache_free(wl_entries_slab, pe->e); 1525 kfree(pe); 1526 } 1527 } 1528} 1529 1530/** 1531 * ubi_wl_close - close the wear-leveling unit. 1532 * @ubi: UBI device description object 1533 */ 1534void ubi_wl_close(struct ubi_device *ubi) 1535{ 1536 dbg_wl("disable \"%s\"", ubi->bgt_name); 1537 if (ubi->bgt_thread) 1538 kthread_stop(ubi->bgt_thread); 1539 1540 dbg_wl("close the UBI wear-leveling unit"); 1541 1542 cancel_pending(ubi); 1543 protection_trees_destroy(ubi); 1544 tree_destroy(&ubi->used); 1545 tree_destroy(&ubi->free); 1546 tree_destroy(&ubi->scrub); 1547 kfree(ubi->lookuptbl); 1548 if (ubi_devices_cnt == 1) 1549 kmem_cache_destroy(wl_entries_slab); 1550} 1551 1552#ifdef CONFIG_MTD_UBI_DEBUG_PARANOID 1553 1554/** 1555 * paranoid_check_ec - make sure that the erase counter of a physical eraseblock 1556 * is correct. 1557 * @ubi: UBI device description object 1558 * @pnum: the physical eraseblock number to check 1559 * @ec: the erase counter to check 1560 * 1561 * This function returns zero if the erase counter of physical eraseblock @pnum 1562 * is equivalent to @ec, %1 if not, and a negative error code if an error 1563 * occurred. 1564 */ 1565static int paranoid_check_ec(const struct ubi_device *ubi, int pnum, int ec) 1566{ 1567 int err; 1568 long long read_ec; 1569 struct ubi_ec_hdr *ec_hdr; 1570 1571 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_KERNEL); 1572 if (!ec_hdr) 1573 return -ENOMEM; 1574 1575 err = ubi_io_read_ec_hdr(ubi, pnum, ec_hdr, 0); 1576 if (err && err != UBI_IO_BITFLIPS) { 1577 /* The header does not have to exist */ 1578 err = 0; 1579 goto out_free; 1580 } 1581 1582 read_ec = ubi64_to_cpu(ec_hdr->ec); 1583 if (ec != read_ec) { 1584 ubi_err("paranoid check failed for PEB %d", pnum); 1585 ubi_err("read EC is %lld, should be %d", read_ec, ec); 1586 ubi_dbg_dump_stack(); 1587 err = 1; 1588 } else 1589 err = 0; 1590 1591out_free: 1592 kfree(ec_hdr); 1593 return err; 1594} 1595 1596/** 1597 * paranoid_check_in_wl_tree - make sure that a wear-leveling entry is present 1598 * in a WL RB-tree. 1599 * @e: the wear-leveling entry to check 1600 * @root: the root of the tree 1601 * 1602 * This function returns zero if @e is in the @root RB-tree and %1 if it 1603 * is not. 1604 */ 1605static int paranoid_check_in_wl_tree(struct ubi_wl_entry *e, 1606 struct rb_root *root) 1607{ 1608 if (in_wl_tree(e, root)) 1609 return 0; 1610 1611 ubi_err("paranoid check failed for PEB %d, EC %d, RB-tree %p ", 1612 e->pnum, e->ec, root); 1613 ubi_dbg_dump_stack(); 1614 return 1; 1615} 1616 1617#endif /* CONFIG_MTD_UBI_DEBUG_PARANOID */ 1618