drivers/mtd/ubi/wl.c

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