Lines Matching +full:ubi +full:- +full:volume +full:-
1 // SPDX-License-Identifier: GPL-2.0-or-later
9 * UBI wear-leveling sub-system.
11 * This sub-system is responsible for wear-leveling. It works in terms of
13 * eraseblocks, volumes, etc. From this sub-system's perspective all physical
14 * eraseblocks are of two types - used and free. Used physical eraseblocks are
21 * When physical eraseblocks are returned to the WL sub-system by means of the
23 * done asynchronously in context of the per-UBI device background thread,
24 * which is also managed by the WL sub-system.
26 * The wear-leveling is ensured by means of moving the contents of used
30 * If the WL sub-system fails to erase a physical eraseblock, it marks it as
33 * This sub-system is also responsible for scrubbing. If a bit-flip is detected
35 * as moving it for wear-leveling reasons.
37 * As it was said, for the UBI sub-system all physical eraseblocks are either
38 * "free" or "used". Free eraseblock are kept in the @wl->free RB-tree, while
39 * used eraseblocks are kept in @wl->used, @wl->erroneous, or @wl->scrub
40 * RB-trees, as well as (temporarily) in the @wl->pq queue.
42 * When the WL sub-system returns a physical eraseblock, the physical
44 * the physical eraseblock is not directly moved from the @wl->free tree to the
45 * @wl->used tree. There is a protection queue in between where this
46 * physical eraseblock is temporarily stored (@wl->pq).
63 * used. The former state corresponds to the @wl->free tree. The latter state
64 * is split up on several sub-states:
65 * o the WL movement is allowed (@wl->used tree);
66 * o the WL movement is disallowed (@wl->erroneous) because the PEB is
67 * erroneous - e.g., there was a read error;
68 * o the WL movement is temporarily prohibited (@wl->pq queue);
69 * o scrubbing is needed (@wl->scrub tree).
71 * Depending on the sub-state, wear-leveling entries of the used physical
74 * Note, in this implementation, we keep a small in-RAM object for each physical
77 * re-work this sub-system and make it more scalable.
79 * At the moment this sub-system does not utilize the sequence number, which
85 * room for future re-works of the WL sub-system.
92 #include "ubi.h"
95 /* Number of physical eraseblocks reserved for wear-leveling purposes */
100 * exceeded, the WL sub-system starts moving data from used physical
107 * When a physical eraseblock is moved, the WL sub-system has to pick the target
113 * counter of the free physical eraseblock to pick. Namely, the WL sub-system
121 * switch to read-only mode.
125 static int self_check_ec(struct ubi_device *ubi, int pnum, int ec);
126 static int self_check_in_wl_tree(const struct ubi_device *ubi,
128 static int self_check_in_pq(const struct ubi_device *ubi,
132 * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
133 * @e: the wear-leveling entry to add
137 * the @ubi->used and @ubi->free RB-trees.
143 p = &root->rb_node;
150 if (e->ec < e1->ec)
151 p = &(*p)->rb_left;
152 else if (e->ec > e1->ec)
153 p = &(*p)->rb_right;
155 ubi_assert(e->pnum != e1->pnum);
156 if (e->pnum < e1->pnum)
157 p = &(*p)->rb_left;
159 p = &(*p)->rb_right;
163 rb_link_node(&e->u.rb, parent, p);
164 rb_insert_color(&e->u.rb, root);
168 * wl_entry_destroy - destroy a wear-leveling entry.
169 * @ubi: UBI device description object
170 * @e: the wear-leveling entry to add
175 static void wl_entry_destroy(struct ubi_device *ubi, struct ubi_wl_entry *e)
177 ubi->lookuptbl[e->pnum] = NULL;
182 * do_work - do one pending work.
183 * @ubi: UBI device description object
190 static int do_work(struct ubi_device *ubi, int *executed)
198 * @ubi->work_sem is used to synchronize with the workers. Workers take
203 down_read(&ubi->work_sem);
204 spin_lock(&ubi->wl_lock);
205 if (list_empty(&ubi->works)) {
206 spin_unlock(&ubi->wl_lock);
207 up_read(&ubi->work_sem);
215 wrk = list_entry(ubi->works.next, struct ubi_work, list);
216 list_del(&wrk->list);
217 ubi->works_count -= 1;
218 ubi_assert(ubi->works_count >= 0);
219 spin_unlock(&ubi->wl_lock);
226 err = wrk->func(ubi, wrk, 0);
228 ubi_err(ubi, "work failed with error code %d", err);
229 up_read(&ubi->work_sem);
235 * in_wl_tree - check if wear-leveling entry is present in a WL RB-tree.
236 * @e: the wear-leveling entry to check
239 * This function returns non-zero if @e is in the @root RB-tree and zero if it
246 p = root->rb_node;
252 if (e->pnum == e1->pnum) {
257 if (e->ec < e1->ec)
258 p = p->rb_left;
259 else if (e->ec > e1->ec)
260 p = p->rb_right;
262 ubi_assert(e->pnum != e1->pnum);
263 if (e->pnum < e1->pnum)
264 p = p->rb_left;
266 p = p->rb_right;
274 * in_pq - check if a wear-leveling entry is present in the protection queue.
275 * @ubi: UBI device description object
276 * @e: the wear-leveling entry to check
278 * This function returns non-zero if @e is in the protection queue and zero
281 static inline int in_pq(const struct ubi_device *ubi, struct ubi_wl_entry *e)
287 list_for_each_entry(p, &ubi->pq[i], u.list)
295 * prot_queue_add - add physical eraseblock to the protection queue.
296 * @ubi: UBI device description object
299 * This function adds @e to the tail of the protection queue @ubi->pq, where
301 * temporarily protected from the wear-leveling worker. Note, @wl->lock has to
304 static void prot_queue_add(struct ubi_device *ubi, struct ubi_wl_entry *e)
306 int pq_tail = ubi->pq_head - 1;
309 pq_tail = UBI_PROT_QUEUE_LEN - 1;
311 list_add_tail(&e->u.list, &ubi->pq[pq_tail]);
312 dbg_wl("added PEB %d EC %d to the protection queue", e->pnum, e->ec);
316 * find_wl_entry - find wear-leveling entry closest to certain erase counter.
317 * @ubi: UBI device description object
318 * @root: the RB-tree where to look for
325 static struct ubi_wl_entry *find_wl_entry(struct ubi_device *ubi,
334 max = e->ec + diff;
336 p = root->rb_node;
341 if (e1->ec >= max) {
344 p = p->rb_left;
346 p = p->rb_right;
355 * find_mean_wl_entry - find wear-leveling entry with medium erase counter.
356 * @ubi: UBI device description object
357 * @root: the RB-tree where to look for
363 static struct ubi_wl_entry *find_mean_wl_entry(struct ubi_device *ubi,
371 if (last->ec - first->ec < WL_FREE_MAX_DIFF) {
372 e = rb_entry(root->rb_node, struct ubi_wl_entry, u.rb);
380 e = may_reserve_for_fm(ubi, e, root);
382 e = find_wl_entry(ubi, root, WL_FREE_MAX_DIFF/2, 0);
388 * wl_get_wle - get a mean wl entry to be used by ubi_wl_get_peb() or
390 * @ubi: UBI device description object
395 static struct ubi_wl_entry *wl_get_wle(struct ubi_device *ubi)
399 e = find_mean_wl_entry(ubi, &ubi->free);
401 ubi_err(ubi, "no free eraseblocks");
405 self_check_in_wl_tree(ubi, e, &ubi->free);
411 rb_erase(&e->u.rb, &ubi->free);
412 ubi->free_count--;
413 dbg_wl("PEB %d EC %d", e->pnum, e->ec);
419 * prot_queue_del - remove a physical eraseblock from the protection queue.
420 * @ubi: UBI device description object
424 * in case of success and %-ENODEV if the PEB was not found.
426 static int prot_queue_del(struct ubi_device *ubi, int pnum)
430 e = ubi->lookuptbl[pnum];
432 return -ENODEV;
434 if (self_check_in_pq(ubi, e))
435 return -ENODEV;
437 list_del(&e->u.list);
438 dbg_wl("deleted PEB %d from the protection queue", e->pnum);
443 * ubi_sync_erase - synchronously erase a physical eraseblock.
444 * @ubi: UBI device description object
451 int ubi_sync_erase(struct ubi_device *ubi, struct ubi_wl_entry *e, int torture)
455 unsigned long long ec = e->ec;
457 dbg_wl("erase PEB %d, old EC %llu", e->pnum, ec);
459 err = self_check_ec(ubi, e->pnum, e->ec);
461 return -EINVAL;
463 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_NOFS);
465 return -ENOMEM;
467 err = ubi_io_sync_erase(ubi, e->pnum, torture);
474 * Erase counter overflow. Upgrade UBI and use 64-bit
477 ubi_err(ubi, "erase counter overflow at PEB %d, EC %llu",
478 e->pnum, ec);
479 err = -EINVAL;
483 dbg_wl("erased PEB %d, new EC %llu", e->pnum, ec);
485 ec_hdr->ec = cpu_to_be64(ec);
487 err = ubi_io_write_ec_hdr(ubi, e->pnum, ec_hdr);
491 e->ec = ec;
492 spin_lock(&ubi->wl_lock);
493 if (e->ec > ubi->max_ec)
494 ubi->max_ec = e->ec;
495 spin_unlock(&ubi->wl_lock);
503 * serve_prot_queue - check if it is time to stop protecting PEBs.
504 * @ubi: UBI device description object
510 static void serve_prot_queue(struct ubi_device *ubi)
521 spin_lock(&ubi->wl_lock);
522 list_for_each_entry_safe(e, tmp, &ubi->pq[ubi->pq_head], u.list) {
524 e->pnum, e->ec);
526 list_del(&e->u.list);
527 wl_tree_add(e, &ubi->used);
533 spin_unlock(&ubi->wl_lock);
539 ubi->pq_head += 1;
540 if (ubi->pq_head == UBI_PROT_QUEUE_LEN)
541 ubi->pq_head = 0;
542 ubi_assert(ubi->pq_head >= 0 && ubi->pq_head < UBI_PROT_QUEUE_LEN);
543 spin_unlock(&ubi->wl_lock);
547 * __schedule_ubi_work - schedule a work.
548 * @ubi: UBI device description object
552 * list. Can only be used if ubi->work_sem is already held in read mode!
554 static void __schedule_ubi_work(struct ubi_device *ubi, struct ubi_work *wrk)
556 spin_lock(&ubi->wl_lock);
557 list_add_tail(&wrk->list, &ubi->works);
558 ubi_assert(ubi->works_count >= 0);
559 ubi->works_count += 1;
560 if (ubi->thread_enabled && !ubi_dbg_is_bgt_disabled(ubi))
561 wake_up_process(ubi->bgt_thread);
562 spin_unlock(&ubi->wl_lock);
566 * schedule_ubi_work - schedule a work.
567 * @ubi: UBI device description object
573 static void schedule_ubi_work(struct ubi_device *ubi, struct ubi_work *wrk)
575 down_read(&ubi->work_sem);
576 __schedule_ubi_work(ubi, wrk);
577 up_read(&ubi->work_sem);
580 static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
584 * schedule_erase - schedule an erase work.
585 * @ubi: UBI device description object
587 * @vol_id: the volume ID that last used this PEB
592 * This function returns zero in case of success and a %-ENOMEM in case of
595 static int schedule_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
603 e->pnum, e->ec, torture);
607 return -ENOMEM;
609 wl_wrk->func = &erase_worker;
610 wl_wrk->e = e;
611 wl_wrk->vol_id = vol_id;
612 wl_wrk->lnum = lnum;
613 wl_wrk->torture = torture;
616 __schedule_ubi_work(ubi, wl_wrk);
618 schedule_ubi_work(ubi, wl_wrk);
622 static int __erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk);
624 * do_sync_erase - run the erase worker synchronously.
625 * @ubi: UBI device description object
627 * @vol_id: the volume ID that last used this PEB
632 static int do_sync_erase(struct ubi_device *ubi, struct ubi_wl_entry *e,
637 dbg_wl("sync erase of PEB %i", e->pnum);
644 return __erase_worker(ubi, &wl_wrk);
647 static int ensure_wear_leveling(struct ubi_device *ubi, int nested);
649 * wear_leveling_worker - wear-leveling worker function.
650 * @ubi: UBI device description object
652 * @shutdown: non-zero if the worker has to free memory and exit
653 * because the WL-subsystem is shutting down
659 static int wear_leveling_worker(struct ubi_device *ubi, struct ubi_work *wrk,
663 int erase = 0, keep = 0, vol_id = -1, lnum = -1;
673 vidb = ubi_alloc_vid_buf(ubi, GFP_NOFS);
675 return -ENOMEM;
679 down_read(&ubi->fm_eba_sem);
680 mutex_lock(&ubi->move_mutex);
681 spin_lock(&ubi->wl_lock);
682 ubi_assert(!ubi->move_from && !ubi->move_to);
683 ubi_assert(!ubi->move_to_put);
686 if (!next_peb_for_wl(ubi, true) ||
688 if (!ubi->free.rb_node ||
690 (!ubi->used.rb_node && !ubi->scrub.rb_node)) {
693 * the queue to be erased. Cancel movement - it will be
698 * @ubi->used tree later and the wear-leveling will be
702 !ubi->free.rb_node, !ubi->used.rb_node);
707 e1 = find_anchor_wl_entry(&ubi->used);
708 if (e1 && ubi->fm_anchor &&
709 (ubi->fm_anchor->ec - e1->ec >= UBI_WL_THRESHOLD)) {
710 ubi->fm_do_produce_anchor = 1;
716 wl_tree_add(ubi->fm_anchor, &ubi->free);
717 ubi->fm_anchor = NULL;
718 ubi->free_count++;
721 if (ubi->fm_do_produce_anchor) {
724 e2 = get_peb_for_wl(ubi);
728 self_check_in_wl_tree(ubi, e1, &ubi->used);
729 rb_erase(&e1->u.rb, &ubi->used);
730 dbg_wl("anchor-move PEB %d to PEB %d", e1->pnum, e2->pnum);
731 ubi->fm_do_produce_anchor = 0;
732 } else if (!ubi->scrub.rb_node) {
734 if (!ubi->scrub.rb_node) {
737 * Now pick the least worn-out used physical eraseblock and a
738 * highly worn-out free physical eraseblock. If the erase
739 * counters differ much enough, start wear-leveling.
741 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, u.rb);
742 e2 = get_peb_for_wl(ubi);
746 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD)) {
748 e1->ec, e2->ec);
751 wl_tree_add(e2, &ubi->free);
752 ubi->free_count++;
755 self_check_in_wl_tree(ubi, e1, &ubi->used);
756 rb_erase(&e1->u.rb, &ubi->used);
758 e1->pnum, e1->ec, e2->pnum, e2->ec);
762 e1 = rb_entry(rb_first(&ubi->scrub), struct ubi_wl_entry, u.rb);
763 e2 = get_peb_for_wl(ubi);
767 self_check_in_wl_tree(ubi, e1, &ubi->scrub);
768 rb_erase(&e1->u.rb, &ubi->scrub);
769 dbg_wl("scrub PEB %d to PEB %d", e1->pnum, e2->pnum);
772 ubi->move_from = e1;
773 ubi->move_to = e2;
774 spin_unlock(&ubi->wl_lock);
777 * Now we are going to copy physical eraseblock @e1->pnum to @e2->pnum.
779 * eraseblock (@e1) belongs to. We have to read the volume identifier
787 err = ubi_io_read_vid_hdr(ubi, e1->pnum, vidb, 0);
792 * We are trying to move PEB without a VID header. UBI
801 dbg_wl("PEB %d has no VID header", e1->pnum);
806 * The same situation as %UBI_IO_FF, but bit-flips were
810 dbg_wl("PEB %d has no VID header but has bit-flips",
811 e1->pnum);
814 } else if (ubi->fast_attach && err == UBI_IO_BAD_HDR_EBADMSG) {
821 e1->pnum);
826 ubi_err(ubi, "error %d while reading VID header from PEB %d",
827 err, e1->pnum);
831 vol_id = be32_to_cpu(vid_hdr->vol_id);
832 lnum = be32_to_cpu(vid_hdr->lnum);
834 err = ubi_eba_copy_leb(ubi, e1->pnum, e2->pnum, vidb);
838 * The LEB has not been moved because the volume is
841 * wear-leveling movement again, so put it to the
852 * be put back into ubi->scrub list.
853 * 2. Non-scrub type PEB will be put back into ubi->used
863 * Target PEB had bit-flips or write error - torture it.
876 * put this PEB to the @ubi->erroneous list to prevent
877 * UBI from trying to move it over and over again.
879 if (ubi->erroneous_peb_count > ubi->max_erroneous) {
880 ubi_err(ubi, "too many erroneous eraseblocks (%d)",
881 ubi->erroneous_peb_count);
897 ubi_msg(ubi, "scrubbed PEB %d (LEB %d:%d), data moved to PEB %d",
898 e1->pnum, vol_id, lnum, e2->pnum);
901 spin_lock(&ubi->wl_lock);
902 if (!ubi->move_to_put) {
903 wl_tree_add(e2, &ubi->used);
906 ubi->move_from = ubi->move_to = NULL;
907 ubi->move_to_put = ubi->wl_scheduled = 0;
908 spin_unlock(&ubi->wl_lock);
910 err = do_sync_erase(ubi, e1, vol_id, lnum, 0);
913 spin_lock(&ubi->wl_lock);
914 wl_entry_destroy(ubi, e2);
915 spin_unlock(&ubi->wl_lock);
926 e2->pnum, vol_id, lnum);
927 err = do_sync_erase(ubi, e2, vol_id, lnum, 0);
933 mutex_unlock(&ubi->move_mutex);
934 up_read(&ubi->fm_eba_sem);
943 if (vol_id != -1)
945 e1->pnum, vol_id, lnum, e2->pnum, err);
948 e1->pnum, e2->pnum, err);
949 spin_lock(&ubi->wl_lock);
951 prot_queue_add(ubi, e1);
953 wl_tree_add(e1, &ubi->erroneous);
954 ubi->erroneous_peb_count += 1;
956 wl_tree_add(e1, &ubi->scrub);
958 wl_tree_add(e1, &ubi->used);
960 wl_tree_add(e2, &ubi->free);
961 ubi->free_count++;
964 ubi_assert(!ubi->move_to_put);
965 ubi->move_from = ubi->move_to = NULL;
966 ubi->wl_scheduled = 0;
967 spin_unlock(&ubi->wl_lock);
971 ensure_wear_leveling(ubi, 1);
973 err = do_sync_erase(ubi, e2, vol_id, lnum, torture);
979 err = do_sync_erase(ubi, e1, vol_id, lnum, 1);
984 mutex_unlock(&ubi->move_mutex);
985 up_read(&ubi->fm_eba_sem);
989 if (vol_id != -1)
990 ubi_err(ubi, "error %d while moving PEB %d to PEB %d",
991 err, e1->pnum, e2->pnum);
993 ubi_err(ubi, "error %d while moving PEB %d (LEB %d:%d) to PEB %d",
994 err, e1->pnum, vol_id, lnum, e2->pnum);
995 spin_lock(&ubi->wl_lock);
996 ubi->move_from = ubi->move_to = NULL;
997 ubi->move_to_put = ubi->wl_scheduled = 0;
998 wl_entry_destroy(ubi, e1);
999 wl_entry_destroy(ubi, e2);
1000 spin_unlock(&ubi->wl_lock);
1005 ubi_ro_mode(ubi);
1006 mutex_unlock(&ubi->move_mutex);
1007 up_read(&ubi->fm_eba_sem);
1009 return err < 0 ? err : -EIO;
1012 ubi->wl_scheduled = 0;
1013 spin_unlock(&ubi->wl_lock);
1014 mutex_unlock(&ubi->move_mutex);
1015 up_read(&ubi->fm_eba_sem);
1021 * ensure_wear_leveling - schedule wear-leveling if it is needed.
1022 * @ubi: UBI device description object
1023 * @nested: set to non-zero if this function is called from UBI worker
1025 * This function checks if it is time to start wear-leveling and schedules it
1029 static int ensure_wear_leveling(struct ubi_device *ubi, int nested)
1034 spin_lock(&ubi->wl_lock);
1035 if (ubi->wl_scheduled)
1036 /* Wear-leveling is already in the work queue */
1040 * If the ubi->scrub tree is not empty, scrubbing is needed, and the
1043 if (!ubi->scrub.rb_node) {
1045 if (!need_wear_leveling(ubi))
1051 if (!ubi->used.rb_node || !ubi->free.rb_node)
1052 /* No physical eraseblocks - no deal */
1056 * We schedule wear-leveling only if the difference between the
1061 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, u.rb);
1062 e2 = find_wl_entry(ubi, &ubi->free, WL_FREE_MAX_DIFF, 0);
1064 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD))
1067 dbg_wl("schedule wear-leveling");
1071 ubi->wl_scheduled = 1;
1072 spin_unlock(&ubi->wl_lock);
1076 err = -ENOMEM;
1080 wrk->func = &wear_leveling_worker;
1082 __schedule_ubi_work(ubi, wrk);
1084 schedule_ubi_work(ubi, wrk);
1088 spin_lock(&ubi->wl_lock);
1089 ubi->wl_scheduled = 0;
1091 spin_unlock(&ubi->wl_lock);
1096 * __erase_worker - physical eraseblock erase worker function.
1097 * @ubi: UBI device description object
1105 static int __erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk)
1107 struct ubi_wl_entry *e = wl_wrk->e;
1108 int pnum = e->pnum;
1109 int vol_id = wl_wrk->vol_id;
1110 int lnum = wl_wrk->lnum;
1114 pnum, e->ec, wl_wrk->vol_id, wl_wrk->lnum);
1116 err = ubi_sync_erase(ubi, e, wl_wrk->torture);
1118 spin_lock(&ubi->wl_lock);
1120 if (!ubi->fm_disabled && !ubi->fm_anchor &&
1121 e->pnum < UBI_FM_MAX_START) {
1126 ubi->fm_anchor = e;
1127 ubi->fm_do_produce_anchor = 0;
1129 wl_tree_add(e, &ubi->free);
1130 ubi->free_count++;
1133 spin_unlock(&ubi->wl_lock);
1139 serve_prot_queue(ubi);
1141 /* And take care about wear-leveling */
1142 err = ensure_wear_leveling(ubi, 1);
1146 ubi_err(ubi, "failed to erase PEB %d, error %d", pnum, err);
1148 if (err == -EINTR || err == -ENOMEM || err == -EAGAIN ||
1149 err == -EBUSY) {
1152 /* Re-schedule the LEB for erasure */
1153 err1 = schedule_erase(ubi, e, vol_id, lnum, 0, true);
1155 spin_lock(&ubi->wl_lock);
1156 wl_entry_destroy(ubi, e);
1157 spin_unlock(&ubi->wl_lock);
1164 spin_lock(&ubi->wl_lock);
1165 wl_entry_destroy(ubi, e);
1166 spin_unlock(&ubi->wl_lock);
1167 if (err != -EIO)
1169 * If this is not %-EIO, we have no idea what to do. Scheduling
1175 /* It is %-EIO, the PEB went bad */
1177 if (!ubi->bad_allowed) {
1178 ubi_err(ubi, "bad physical eraseblock %d detected", pnum);
1182 spin_lock(&ubi->volumes_lock);
1183 if (ubi->beb_rsvd_pebs == 0) {
1184 if (ubi->avail_pebs == 0) {
1185 spin_unlock(&ubi->volumes_lock);
1186 ubi_err(ubi, "no reserved/available physical eraseblocks");
1189 ubi->avail_pebs -= 1;
1192 spin_unlock(&ubi->volumes_lock);
1194 ubi_msg(ubi, "mark PEB %d as bad", pnum);
1195 err = ubi_io_mark_bad(ubi, pnum);
1199 spin_lock(&ubi->volumes_lock);
1200 if (ubi->beb_rsvd_pebs > 0) {
1206 ubi->avail_pebs += 1;
1209 ubi->beb_rsvd_pebs -= 1;
1211 ubi->bad_peb_count += 1;
1212 ubi->good_peb_count -= 1;
1213 ubi_calculate_reserved(ubi);
1215 ubi_warn(ubi, "no PEBs in the reserved pool, used an available PEB");
1216 else if (ubi->beb_rsvd_pebs)
1217 ubi_msg(ubi, "%d PEBs left in the reserve",
1218 ubi->beb_rsvd_pebs);
1220 ubi_warn(ubi, "last PEB from the reserve was used");
1221 spin_unlock(&ubi->volumes_lock);
1227 spin_lock(&ubi->volumes_lock);
1228 ubi->avail_pebs += 1;
1229 spin_unlock(&ubi->volumes_lock);
1231 ubi_ro_mode(ubi);
1235 static int erase_worker(struct ubi_device *ubi, struct ubi_work *wl_wrk,
1241 struct ubi_wl_entry *e = wl_wrk->e;
1243 dbg_wl("cancel erasure of PEB %d EC %d", e->pnum, e->ec);
1245 wl_entry_destroy(ubi, e);
1249 ret = __erase_worker(ubi, wl_wrk);
1255 * ubi_wl_put_peb - return a PEB to the wear-leveling sub-system.
1256 * @ubi: UBI device description object
1257 * @vol_id: the volume ID that last used this PEB
1267 int ubi_wl_put_peb(struct ubi_device *ubi, int vol_id, int lnum,
1275 ubi_assert(pnum < ubi->peb_count);
1277 down_read(&ubi->fm_protect);
1280 spin_lock(&ubi->wl_lock);
1281 e = ubi->lookuptbl[pnum];
1287 * ubi_wl_put_peb) will set ubi ro_mode at the same time,
1290 spin_unlock(&ubi->wl_lock);
1291 up_read(&ubi->fm_protect);
1294 if (e == ubi->move_from) {
1298 * wear-leveling worker.
1301 spin_unlock(&ubi->wl_lock);
1303 /* Wait for the WL worker by taking the @ubi->move_mutex */
1304 mutex_lock(&ubi->move_mutex);
1305 mutex_unlock(&ubi->move_mutex);
1307 } else if (e == ubi->move_to) {
1311 * sub-system already re-mapped the LEB in 'ubi_eba_copy_leb()'
1312 * but the WL sub-system has not put the PEB to the "used" tree
1318 ubi_assert(!ubi->move_to_put);
1319 ubi->move_to_put = 1;
1320 spin_unlock(&ubi->wl_lock);
1321 up_read(&ubi->fm_protect);
1324 if (in_wl_tree(e, &ubi->used)) {
1325 self_check_in_wl_tree(ubi, e, &ubi->used);
1326 rb_erase(&e->u.rb, &ubi->used);
1327 } else if (in_wl_tree(e, &ubi->scrub)) {
1328 self_check_in_wl_tree(ubi, e, &ubi->scrub);
1329 rb_erase(&e->u.rb, &ubi->scrub);
1330 } else if (in_wl_tree(e, &ubi->erroneous)) {
1331 self_check_in_wl_tree(ubi, e, &ubi->erroneous);
1332 rb_erase(&e->u.rb, &ubi->erroneous);
1333 ubi->erroneous_peb_count -= 1;
1334 ubi_assert(ubi->erroneous_peb_count >= 0);
1338 err = prot_queue_del(ubi, e->pnum);
1340 ubi_err(ubi, "PEB %d not found", pnum);
1341 ubi_ro_mode(ubi);
1342 spin_unlock(&ubi->wl_lock);
1343 up_read(&ubi->fm_protect);
1348 spin_unlock(&ubi->wl_lock);
1350 err = schedule_erase(ubi, e, vol_id, lnum, torture, false);
1352 spin_lock(&ubi->wl_lock);
1353 wl_tree_add(e, &ubi->used);
1354 spin_unlock(&ubi->wl_lock);
1357 up_read(&ubi->fm_protect);
1362 * ubi_wl_scrub_peb - schedule a physical eraseblock for scrubbing.
1363 * @ubi: UBI device description object
1366 * If a bit-flip in a physical eraseblock is detected, this physical eraseblock
1371 int ubi_wl_scrub_peb(struct ubi_device *ubi, int pnum)
1375 ubi_msg(ubi, "schedule PEB %d for scrubbing", pnum);
1378 spin_lock(&ubi->wl_lock);
1379 e = ubi->lookuptbl[pnum];
1380 if (e == ubi->move_from || in_wl_tree(e, &ubi->scrub) ||
1381 in_wl_tree(e, &ubi->erroneous)) {
1382 spin_unlock(&ubi->wl_lock);
1386 if (e == ubi->move_to) {
1393 spin_unlock(&ubi->wl_lock);
1399 if (in_wl_tree(e, &ubi->used)) {
1400 self_check_in_wl_tree(ubi, e, &ubi->used);
1401 rb_erase(&e->u.rb, &ubi->used);
1405 err = prot_queue_del(ubi, e->pnum);
1407 ubi_err(ubi, "PEB %d not found", pnum);
1408 ubi_ro_mode(ubi);
1409 spin_unlock(&ubi->wl_lock);
1414 wl_tree_add(e, &ubi->scrub);
1415 spin_unlock(&ubi->wl_lock);
1418 * Technically scrubbing is the same as wear-leveling, so it is done
1421 return ensure_wear_leveling(ubi, 0);
1425 * ubi_wl_flush - flush all pending works.
1426 * @ubi: UBI device description object
1427 * @vol_id: the volume id to flush for
1430 * This function executes all pending works for a particular volume id /
1432 * acts as a wildcard for all of the corresponding volume numbers or logical
1436 int ubi_wl_flush(struct ubi_device *ubi, int vol_id, int lnum)
1446 vol_id, lnum, ubi->works_count);
1452 down_read(&ubi->work_sem);
1453 spin_lock(&ubi->wl_lock);
1454 list_for_each_entry_safe(wrk, tmp, &ubi->works, list) {
1455 if ((vol_id == UBI_ALL || wrk->vol_id == vol_id) &&
1456 (lnum == UBI_ALL || wrk->lnum == lnum)) {
1457 list_del(&wrk->list);
1458 ubi->works_count -= 1;
1459 ubi_assert(ubi->works_count >= 0);
1460 spin_unlock(&ubi->wl_lock);
1462 err = wrk->func(ubi, wrk, 0);
1464 up_read(&ubi->work_sem);
1468 spin_lock(&ubi->wl_lock);
1473 spin_unlock(&ubi->wl_lock);
1474 up_read(&ubi->work_sem);
1481 down_write(&ubi->work_sem);
1482 up_write(&ubi->work_sem);
1487 static bool scrub_possible(struct ubi_device *ubi, struct ubi_wl_entry *e)
1489 if (in_wl_tree(e, &ubi->scrub))
1491 else if (in_wl_tree(e, &ubi->erroneous))
1493 else if (ubi->move_from == e)
1495 else if (ubi->move_to == e)
1502 * ubi_bitflip_check - Check an eraseblock for bitflips and scrub it if needed.
1503 * @ubi: UBI device description object
1514 * %ENOENT, PEB is no longer used by UBI
1520 int ubi_bitflip_check(struct ubi_device *ubi, int pnum, int force)
1525 if (pnum < 0 || pnum >= ubi->peb_count) {
1526 err = -EINVAL;
1534 down_write(&ubi->work_sem);
1540 spin_lock(&ubi->wl_lock);
1541 e = ubi->lookuptbl[pnum];
1543 spin_unlock(&ubi->wl_lock);
1544 err = -ENOENT;
1551 if (!scrub_possible(ubi, e)) {
1552 spin_unlock(&ubi->wl_lock);
1553 err = -EBUSY;
1556 spin_unlock(&ubi->wl_lock);
1559 mutex_lock(&ubi->buf_mutex);
1560 err = ubi_io_read(ubi, ubi->peb_buf, pnum, 0, ubi->peb_size);
1561 mutex_unlock(&ubi->buf_mutex);
1568 spin_lock(&ubi->wl_lock);
1571 * Recheck. We released wl_lock, UBI might have killed the
1574 e = ubi->lookuptbl[pnum];
1576 spin_unlock(&ubi->wl_lock);
1577 err = -ENOENT;
1582 * Need to re-check state
1584 if (!scrub_possible(ubi, e)) {
1585 spin_unlock(&ubi->wl_lock);
1586 err = -EBUSY;
1590 if (in_pq(ubi, e)) {
1591 prot_queue_del(ubi, e->pnum);
1592 wl_tree_add(e, &ubi->scrub);
1593 spin_unlock(&ubi->wl_lock);
1595 err = ensure_wear_leveling(ubi, 1);
1596 } else if (in_wl_tree(e, &ubi->used)) {
1597 rb_erase(&e->u.rb, &ubi->used);
1598 wl_tree_add(e, &ubi->scrub);
1599 spin_unlock(&ubi->wl_lock);
1601 err = ensure_wear_leveling(ubi, 1);
1602 } else if (in_wl_tree(e, &ubi->free)) {
1603 rb_erase(&e->u.rb, &ubi->free);
1604 ubi->free_count--;
1605 spin_unlock(&ubi->wl_lock);
1611 err = schedule_erase(ubi, e, UBI_UNKNOWN, UBI_UNKNOWN,
1614 spin_unlock(&ubi->wl_lock);
1615 err = -EAGAIN;
1619 err = -EUCLEAN;
1625 up_write(&ubi->work_sem);
1632 * tree_destroy - destroy an RB-tree.
1633 * @ubi: UBI device description object
1636 static void tree_destroy(struct ubi_device *ubi, struct rb_root *root)
1641 rb = root->rb_node;
1643 if (rb->rb_left)
1644 rb = rb->rb_left;
1645 else if (rb->rb_right)
1646 rb = rb->rb_right;
1652 if (rb->rb_left == &e->u.rb)
1653 rb->rb_left = NULL;
1655 rb->rb_right = NULL;
1658 wl_entry_destroy(ubi, e);
1664 * ubi_thread - UBI background thread.
1665 * @u: the UBI device description object pointer
1670 struct ubi_device *ubi = u;
1672 ubi_msg(ubi, "background thread \"%s\" started, PID %d",
1673 ubi->bgt_name, task_pid_nr(current));
1685 spin_lock(&ubi->wl_lock);
1686 if (list_empty(&ubi->works) || ubi->ro_mode ||
1687 !ubi->thread_enabled || ubi_dbg_is_bgt_disabled(ubi)) {
1689 spin_unlock(&ubi->wl_lock);
1706 spin_unlock(&ubi->wl_lock);
1708 err = do_work(ubi, NULL);
1710 ubi_err(ubi, "%s: work failed with error code %d",
1711 ubi->bgt_name, err);
1715 * switch to read-only mode.
1717 ubi_msg(ubi, "%s: %d consecutive failures",
1718 ubi->bgt_name, WL_MAX_FAILURES);
1719 ubi_ro_mode(ubi);
1720 ubi->thread_enabled = 0;
1729 dbg_wl("background thread \"%s\" is killed", ubi->bgt_name);
1730 ubi->thread_enabled = 0;
1735 * shutdown_work - shutdown all pending works.
1736 * @ubi: UBI device description object
1738 static void shutdown_work(struct ubi_device *ubi)
1740 while (!list_empty(&ubi->works)) {
1743 wrk = list_entry(ubi->works.next, struct ubi_work, list);
1744 list_del(&wrk->list);
1745 wrk->func(ubi, wrk, 1);
1746 ubi->works_count -= 1;
1747 ubi_assert(ubi->works_count >= 0);
1752 * erase_aeb - erase a PEB given in UBI attach info PEB
1753 * @ubi: UBI device description object
1754 * @aeb: UBI attach info PEB
1757 static int erase_aeb(struct ubi_device *ubi, struct ubi_ainf_peb *aeb, bool sync)
1764 return -ENOMEM;
1766 e->pnum = aeb->pnum;
1767 e->ec = aeb->ec;
1768 ubi->lookuptbl[e->pnum] = e;
1771 err = ubi_sync_erase(ubi, e, false);
1775 wl_tree_add(e, &ubi->free);
1776 ubi->free_count++;
1778 err = schedule_erase(ubi, e, aeb->vol_id, aeb->lnum, 0, false);
1786 wl_entry_destroy(ubi, e);
1792 * ubi_wl_init - initialize the WL sub-system using attaching information.
1793 * @ubi: UBI device description object
1799 int ubi_wl_init(struct ubi_device *ubi, struct ubi_attach_info *ai)
1807 ubi->used = ubi->erroneous = ubi->free = ubi->scrub = RB_ROOT;
1808 spin_lock_init(&ubi->wl_lock);
1809 mutex_init(&ubi->move_mutex);
1810 init_rwsem(&ubi->work_sem);
1811 ubi->max_ec = ai->max_ec;
1812 INIT_LIST_HEAD(&ubi->works);
1814 sprintf(ubi->bgt_name, UBI_BGT_NAME_PATTERN, ubi->ubi_num);
1816 err = -ENOMEM;
1817 ubi->lookuptbl = kcalloc(ubi->peb_count, sizeof(void *), GFP_KERNEL);
1818 if (!ubi->lookuptbl)
1822 INIT_LIST_HEAD(&ubi->pq[i]);
1823 ubi->pq_head = 0;
1825 ubi->free_count = 0;
1826 list_for_each_entry_safe(aeb, tmp, &ai->erase, u.list) {
1829 err = erase_aeb(ubi, aeb, false);
1836 list_for_each_entry(aeb, &ai->free, u.list) {
1841 err = -ENOMEM;
1845 e->pnum = aeb->pnum;
1846 e->ec = aeb->ec;
1847 ubi_assert(e->ec >= 0);
1849 wl_tree_add(e, &ubi->free);
1850 ubi->free_count++;
1852 ubi->lookuptbl[e->pnum] = e;
1857 ubi_rb_for_each_entry(rb1, av, &ai->volumes, rb) {
1858 ubi_rb_for_each_entry(rb2, aeb, &av->root, u.rb) {
1863 err = -ENOMEM;
1867 e->pnum = aeb->pnum;
1868 e->ec = aeb->ec;
1869 ubi->lookuptbl[e->pnum] = e;
1871 if (!aeb->scrub) {
1873 e->pnum, e->ec);
1874 wl_tree_add(e, &ubi->used);
1877 e->pnum, e->ec);
1878 wl_tree_add(e, &ubi->scrub);
1885 list_for_each_entry(aeb, &ai->fastmap, u.list) {
1888 e = ubi_find_fm_block(ubi, aeb->pnum);
1891 ubi_assert(!ubi->lookuptbl[e->pnum]);
1892 ubi->lookuptbl[e->pnum] = e;
1902 if (ubi->lookuptbl[aeb->pnum])
1914 if (aeb->vol_id == UBI_FM_SB_VOLUME_ID)
1917 err = erase_aeb(ubi, aeb, sync);
1927 ubi_assert(ubi->good_peb_count == found_pebs);
1930 ubi_fastmap_init(ubi, &reserved_pebs);
1932 if (ubi->avail_pebs < reserved_pebs) {
1933 ubi_err(ubi, "no enough physical eraseblocks (%d, need %d)",
1934 ubi->avail_pebs, reserved_pebs);
1935 if (ubi->corr_peb_count)
1936 ubi_err(ubi, "%d PEBs are corrupted and not used",
1937 ubi->corr_peb_count);
1938 err = -ENOSPC;
1941 ubi->avail_pebs -= reserved_pebs;
1942 ubi->rsvd_pebs += reserved_pebs;
1944 /* Schedule wear-leveling if needed */
1945 err = ensure_wear_leveling(ubi, 0);
1950 if (!ubi->ro_mode && !ubi->fm_disabled)
1951 ubi_ensure_anchor_pebs(ubi);
1956 shutdown_work(ubi);
1957 tree_destroy(ubi, &ubi->used);
1958 tree_destroy(ubi, &ubi->free);
1959 tree_destroy(ubi, &ubi->scrub);
1960 kfree(ubi->lookuptbl);
1965 * protection_queue_destroy - destroy the protection queue.
1966 * @ubi: UBI device description object
1968 static void protection_queue_destroy(struct ubi_device *ubi)
1974 list_for_each_entry_safe(e, tmp, &ubi->pq[i], u.list) {
1975 list_del(&e->u.list);
1976 wl_entry_destroy(ubi, e);
1982 * ubi_wl_close - close the wear-leveling sub-system.
1983 * @ubi: UBI device description object
1985 void ubi_wl_close(struct ubi_device *ubi)
1987 dbg_wl("close the WL sub-system");
1988 ubi_fastmap_close(ubi);
1989 shutdown_work(ubi);
1990 protection_queue_destroy(ubi);
1991 tree_destroy(ubi, &ubi->used);
1992 tree_destroy(ubi, &ubi->erroneous);
1993 tree_destroy(ubi, &ubi->free);
1994 tree_destroy(ubi, &ubi->scrub);
1995 kfree(ubi->lookuptbl);
1999 * self_check_ec - make sure that the erase counter of a PEB is correct.
2000 * @ubi: UBI device description object
2008 static int self_check_ec(struct ubi_device *ubi, int pnum, int ec)
2014 if (!ubi_dbg_chk_gen(ubi))
2017 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_NOFS);
2019 return -ENOMEM;
2021 err = ubi_io_read_ec_hdr(ubi, pnum, ec_hdr, 0);
2028 read_ec = be64_to_cpu(ec_hdr->ec);
2029 if (ec != read_ec && read_ec - ec > 1) {
2030 ubi_err(ubi, "self-check failed for PEB %d", pnum);
2031 ubi_err(ubi, "read EC is %lld, should be %d", read_ec, ec);
2043 * self_check_in_wl_tree - check that wear-leveling entry is in WL RB-tree.
2044 * @ubi: UBI device description object
2045 * @e: the wear-leveling entry to check
2048 * This function returns zero if @e is in the @root RB-tree and %-EINVAL if it
2051 static int self_check_in_wl_tree(const struct ubi_device *ubi,
2054 if (!ubi_dbg_chk_gen(ubi))
2060 ubi_err(ubi, "self-check failed for PEB %d, EC %d, RB-tree %p ",
2061 e->pnum, e->ec, root);
2063 return -EINVAL;
2067 * self_check_in_pq - check if wear-leveling entry is in the protection
2069 * @ubi: UBI device description object
2070 * @e: the wear-leveling entry to check
2072 * This function returns zero if @e is in @ubi->pq and %-EINVAL if it is not.
2074 static int self_check_in_pq(const struct ubi_device *ubi,
2077 if (!ubi_dbg_chk_gen(ubi))
2080 if (in_pq(ubi, e))
2083 ubi_err(ubi, "self-check failed for PEB %d, EC %d, Protect queue",
2084 e->pnum, e->ec);
2086 return -EINVAL;
2089 static struct ubi_wl_entry *get_peb_for_wl(struct ubi_device *ubi)
2093 e = find_wl_entry(ubi, &ubi->free, WL_FREE_MAX_DIFF, 0);
2094 self_check_in_wl_tree(ubi, e, &ubi->free);
2095 ubi->free_count--;
2096 ubi_assert(ubi->free_count >= 0);
2097 rb_erase(&e->u.rb, &ubi->free);
2103 * produce_free_peb - produce a free physical eraseblock.
2104 * @ubi: UBI device description object
2111 static int produce_free_peb(struct ubi_device *ubi)
2115 while (!ubi->free.rb_node && ubi->works_count) {
2116 spin_unlock(&ubi->wl_lock);
2119 err = do_work(ubi, NULL);
2121 spin_lock(&ubi->wl_lock);
2130 * ubi_wl_get_peb - get a physical eraseblock.
2131 * @ubi: UBI device description object
2135 * Returns with ubi->fm_eba_sem held in read mode!
2137 int ubi_wl_get_peb(struct ubi_device *ubi)
2143 down_read(&ubi->fm_eba_sem);
2144 spin_lock(&ubi->wl_lock);
2145 if (!ubi->free.rb_node) {
2146 if (ubi->works_count == 0) {
2147 ubi_err(ubi, "no free eraseblocks");
2148 ubi_assert(list_empty(&ubi->works));
2149 spin_unlock(&ubi->wl_lock);
2150 return -ENOSPC;
2153 err = produce_free_peb(ubi);
2155 spin_unlock(&ubi->wl_lock);
2158 spin_unlock(&ubi->wl_lock);
2159 up_read(&ubi->fm_eba_sem);
2163 e = wl_get_wle(ubi);
2164 prot_queue_add(ubi, e);
2165 spin_unlock(&ubi->wl_lock);
2167 err = ubi_self_check_all_ff(ubi, e->pnum, ubi->vid_hdr_aloffset,
2168 ubi->peb_size - ubi->vid_hdr_aloffset);
2170 ubi_err(ubi, "new PEB %d does not contain all 0xFF bytes", e->pnum);
2174 return e->pnum;
2177 #include "fastmap-wl.c"