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