Lines Matching +full:sub +full:- +full:system
4 * SPDX-License-Identifier: GPL-2.0+
10 * UBI wear-leveling sub-system.
12 * This sub-system is responsible for wear-leveling. It works in terms of
14 * eraseblocks, volumes, etc. From this sub-system's perspective all physical
15 * eraseblocks are of two types - used and free. Used physical eraseblocks are
22 * When physical eraseblocks are returned to the WL sub-system by means of the
24 * done asynchronously in context of the per-UBI device background thread,
25 * which is also managed by the WL sub-system.
27 * The wear-leveling is ensured by means of moving the contents of used
31 * If the WL sub-system fails to erase a physical eraseblock, it marks it as
34 * This sub-system is also responsible for scrubbing. If a bit-flip is detected
36 * as moving it for wear-leveling reasons.
38 * As it was said, for the UBI sub-system all physical eraseblocks are either
39 * "free" or "used". Free eraseblock are kept in the @wl->free RB-tree, while
40 * used eraseblocks are kept in @wl->used, @wl->erroneous, or @wl->scrub
41 * RB-trees, as well as (temporarily) in the @wl->pq queue.
43 * When the WL sub-system returns a physical eraseblock, the physical
45 * the physical eraseblock is not directly moved from the @wl->free tree to the
46 * @wl->used tree. There is a protection queue in between where this
47 * physical eraseblock is temporarily stored (@wl->pq).
64 * used. The former state corresponds to the @wl->free tree. The latter state
65 * is split up on several sub-states:
66 * o the WL movement is allowed (@wl->used tree);
67 * o the WL movement is disallowed (@wl->erroneous) because the PEB is
68 * erroneous - e.g., there was a read error;
69 * o the WL movement is temporarily prohibited (@wl->pq queue);
70 * o scrubbing is needed (@wl->scrub tree).
72 * Depending on the sub-state, wear-leveling entries of the used physical
75 * Note, in this implementation, we keep a small in-RAM object for each physical
78 * re-work this sub-system and make it more scalable.
80 * At the moment this sub-system does not utilize the sequence number, which
86 * room for future re-works of the WL sub-system.
101 /* Number of physical eraseblocks reserved for wear-leveling purposes */
106 * exceeded, the WL sub-system starts moving data from used physical
113 * When a physical eraseblock is moved, the WL sub-system has to pick the target
119 * counter of the free physical eraseblock to pick. Namely, the WL sub-system
127 * switch to read-only mode.
138 * wl_tree_add - add a wear-leveling entry to a WL RB-tree.
139 * @e: the wear-leveling entry to add
143 * the @ubi->used and @ubi->free RB-trees.
149 p = &root->rb_node; in wl_tree_add()
156 if (e->ec < e1->ec) in wl_tree_add()
157 p = &(*p)->rb_left; in wl_tree_add()
158 else if (e->ec > e1->ec) in wl_tree_add()
159 p = &(*p)->rb_right; in wl_tree_add()
161 ubi_assert(e->pnum != e1->pnum); in wl_tree_add()
162 if (e->pnum < e1->pnum) in wl_tree_add()
163 p = &(*p)->rb_left; in wl_tree_add()
165 p = &(*p)->rb_right; in wl_tree_add()
169 rb_link_node(&e->u.rb, parent, p); in wl_tree_add()
170 rb_insert_color(&e->u.rb, root); in wl_tree_add()
174 * wl_tree_destroy - destroy a wear-leveling entry.
176 * @e: the wear-leveling entry to add
183 ubi->lookuptbl[e->pnum] = NULL; in wl_entry_destroy()
188 * do_work - do one pending work.
202 * @ubi->work_sem is used to synchronize with the workers. Workers take in do_work()
207 down_read(&ubi->work_sem); in do_work()
208 spin_lock(&ubi->wl_lock); in do_work()
209 if (list_empty(&ubi->works)) { in do_work()
210 spin_unlock(&ubi->wl_lock); in do_work()
211 up_read(&ubi->work_sem); in do_work()
215 wrk = list_entry(ubi->works.next, struct ubi_work, list); in do_work()
216 list_del(&wrk->list); in do_work()
217 ubi->works_count -= 1; in do_work()
218 ubi_assert(ubi->works_count >= 0); in do_work()
219 spin_unlock(&ubi->wl_lock); in do_work()
226 err = wrk->func(ubi, wrk, 0); in do_work()
229 up_read(&ubi->work_sem); in do_work()
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; in in_wl_tree()
252 if (e->pnum == e1->pnum) { in in_wl_tree()
257 if (e->ec < e1->ec) in in_wl_tree()
258 p = p->rb_left; in in_wl_tree()
259 else if (e->ec > e1->ec) in in_wl_tree()
260 p = p->rb_right; in in_wl_tree()
262 ubi_assert(e->pnum != e1->pnum); in in_wl_tree()
263 if (e->pnum < e1->pnum) in in_wl_tree()
264 p = p->rb_left; in in_wl_tree()
266 p = p->rb_right; in in_wl_tree()
274 * prot_queue_add - add physical eraseblock to the protection queue.
278 * This function adds @e to the tail of the protection queue @ubi->pq, where
280 * temporarily protected from the wear-leveling worker. Note, @wl->lock has to
285 int pq_tail = ubi->pq_head - 1; in prot_queue_add()
288 pq_tail = UBI_PROT_QUEUE_LEN - 1; in prot_queue_add()
290 list_add_tail(&e->u.list, &ubi->pq[pq_tail]); in prot_queue_add()
291 dbg_wl("added PEB %d EC %d to the protection queue", e->pnum, e->ec); in prot_queue_add()
295 * find_wl_entry - find wear-leveling entry closest to certain erase counter.
297 * @root: the RB-tree where to look for
311 max = e->ec + diff; in find_wl_entry()
313 p = root->rb_node; in find_wl_entry()
318 if (e1->ec >= max) in find_wl_entry()
319 p = p->rb_left; in find_wl_entry()
321 p = p->rb_right; in find_wl_entry()
330 if (prev_e && !ubi->fm_disabled && in find_wl_entry()
331 !ubi->fm && e->pnum < UBI_FM_MAX_START) in find_wl_entry()
338 * find_mean_wl_entry - find wear-leveling entry with medium erase counter.
340 * @root: the RB-tree where to look for
354 if (last->ec - first->ec < WL_FREE_MAX_DIFF) { in find_mean_wl_entry()
355 e = rb_entry(root->rb_node, struct ubi_wl_entry, u.rb); in find_mean_wl_entry()
368 * wl_get_wle - get a mean wl entry to be used by ubi_wl_get_peb() or
379 e = find_mean_wl_entry(ubi, &ubi->free); in wl_get_wle()
385 self_check_in_wl_tree(ubi, e, &ubi->free); in wl_get_wle()
391 rb_erase(&e->u.rb, &ubi->free); in wl_get_wle()
392 ubi->free_count--; in wl_get_wle()
393 dbg_wl("PEB %d EC %d", e->pnum, e->ec); in wl_get_wle()
399 * prot_queue_del - remove a physical eraseblock from the protection queue.
404 * in case of success and %-ENODEV if the PEB was not found.
410 e = ubi->lookuptbl[pnum]; in prot_queue_del()
412 return -ENODEV; in prot_queue_del()
415 return -ENODEV; in prot_queue_del()
417 list_del(&e->u.list); in prot_queue_del()
418 dbg_wl("deleted PEB %d from the protection queue", e->pnum); in prot_queue_del()
423 * sync_erase - synchronously erase a physical eraseblock.
436 unsigned long long ec = e->ec; in sync_erase()
438 dbg_wl("erase PEB %d, old EC %llu", e->pnum, ec); in sync_erase()
440 err = self_check_ec(ubi, e->pnum, e->ec); in sync_erase()
442 return -EINVAL; in sync_erase()
444 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_NOFS); in sync_erase()
446 return -ENOMEM; in sync_erase()
448 err = ubi_io_sync_erase(ubi, e->pnum, torture); in sync_erase()
455 * Erase counter overflow. Upgrade UBI and use 64-bit in sync_erase()
459 e->pnum, ec); in sync_erase()
460 err = -EINVAL; in sync_erase()
464 dbg_wl("erased PEB %d, new EC %llu", e->pnum, ec); in sync_erase()
466 ec_hdr->ec = cpu_to_be64(ec); in sync_erase()
468 err = ubi_io_write_ec_hdr(ubi, e->pnum, ec_hdr); in sync_erase()
472 e->ec = ec; in sync_erase()
473 spin_lock(&ubi->wl_lock); in sync_erase()
474 if (e->ec > ubi->max_ec) in sync_erase()
475 ubi->max_ec = e->ec; in sync_erase()
476 spin_unlock(&ubi->wl_lock); in sync_erase()
484 * serve_prot_queue - check if it is time to stop protecting PEBs.
502 spin_lock(&ubi->wl_lock); in serve_prot_queue()
503 list_for_each_entry_safe(e, tmp, &ubi->pq[ubi->pq_head], u.list) { in serve_prot_queue()
505 e->pnum, e->ec); in serve_prot_queue()
507 list_del(&e->u.list); in serve_prot_queue()
508 wl_tree_add(e, &ubi->used); in serve_prot_queue()
514 spin_unlock(&ubi->wl_lock); in serve_prot_queue()
520 ubi->pq_head += 1; in serve_prot_queue()
521 if (ubi->pq_head == UBI_PROT_QUEUE_LEN) in serve_prot_queue()
522 ubi->pq_head = 0; in serve_prot_queue()
523 ubi_assert(ubi->pq_head >= 0 && ubi->pq_head < UBI_PROT_QUEUE_LEN); in serve_prot_queue()
524 spin_unlock(&ubi->wl_lock); in serve_prot_queue()
532 if (list_empty(&ubi->works) || ubi->ro_mode || in ubi_do_worker()
533 !ubi->thread_enabled || ubi_dbg_is_bgt_disabled(ubi)) in ubi_do_worker()
536 spin_lock(&ubi->wl_lock); in ubi_do_worker()
537 while (!list_empty(&ubi->works)) { in ubi_do_worker()
542 spin_unlock(&ubi->wl_lock); in ubi_do_worker()
544 spin_lock(&ubi->wl_lock); in ubi_do_worker()
547 ubi->bgt_name, err); in ubi_do_worker()
550 spin_unlock(&ubi->wl_lock); in ubi_do_worker()
555 * __schedule_ubi_work - schedule a work.
560 * list. Can only be used if ubi->work_sem is already held in read mode!
564 spin_lock(&ubi->wl_lock); in __schedule_ubi_work()
565 list_add_tail(&wrk->list, &ubi->works); in __schedule_ubi_work()
566 ubi_assert(ubi->works_count >= 0); in __schedule_ubi_work()
567 ubi->works_count += 1; in __schedule_ubi_work()
569 if (ubi->thread_enabled && !ubi_dbg_is_bgt_disabled(ubi)) in __schedule_ubi_work()
570 wake_up_process(ubi->bgt_thread); in __schedule_ubi_work()
572 spin_unlock(&ubi->wl_lock); in __schedule_ubi_work()
576 * schedule_ubi_work - schedule a work.
585 down_read(&ubi->work_sem); in schedule_ubi_work()
587 up_read(&ubi->work_sem); in schedule_ubi_work()
594 * schedule_erase - schedule an erase work.
601 * This function returns zero in case of success and a %-ENOMEM in case of
612 e->pnum, e->ec, torture); in schedule_erase()
616 return -ENOMEM; in schedule_erase()
618 wl_wrk->func = &erase_worker; in schedule_erase()
619 wl_wrk->e = e; in schedule_erase()
620 wl_wrk->vol_id = vol_id; in schedule_erase()
621 wl_wrk->lnum = lnum; in schedule_erase()
622 wl_wrk->torture = torture; in schedule_erase()
633 * do_sync_erase - run the erase worker synchronously.
646 dbg_wl("sync erase of PEB %i", e->pnum); in do_sync_erase()
650 return -ENOMEM; in do_sync_erase()
652 wl_wrk->e = e; in do_sync_erase()
653 wl_wrk->vol_id = vol_id; in do_sync_erase()
654 wl_wrk->lnum = lnum; in do_sync_erase()
655 wl_wrk->torture = torture; in do_sync_erase()
661 * wear_leveling_worker - wear-leveling worker function.
664 * @shutdown: non-zero if the worker has to free memory and exit
665 * because the WL-subsystem is shutting down
675 int vol_id = -1, lnum = -1;
677 int anchor = wrk->anchor;
688 return -ENOMEM;
690 mutex_lock(&ubi->move_mutex);
691 spin_lock(&ubi->wl_lock);
692 ubi_assert(!ubi->move_from && !ubi->move_to);
693 ubi_assert(!ubi->move_to_put);
695 if (!ubi->free.rb_node ||
696 (!ubi->used.rb_node && !ubi->scrub.rb_node)) {
699 * the queue to be erased. Cancel movement - it will be
704 * @ubi->used tree later and the wear-leveling will be
708 !ubi->free.rb_node, !ubi->used.rb_node);
715 anchor = !anchor_pebs_avalible(&ubi->free);
718 e1 = find_anchor_wl_entry(&ubi->used);
725 self_check_in_wl_tree(ubi, e1, &ubi->used);
726 rb_erase(&e1->u.rb, &ubi->used);
727 dbg_wl("anchor-move PEB %d to PEB %d", e1->pnum, e2->pnum);
728 } else if (!ubi->scrub.rb_node) {
730 if (!ubi->scrub.rb_node) {
733 * Now pick the least worn-out used physical eraseblock and a
734 * highly worn-out free physical eraseblock. If the erase
735 * counters differ much enough, start wear-leveling.
737 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, u.rb);
742 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD)) {
744 e1->ec, e2->ec);
747 wl_tree_add(e2, &ubi->free);
748 ubi->free_count++;
751 self_check_in_wl_tree(ubi, e1, &ubi->used);
752 rb_erase(&e1->u.rb, &ubi->used);
754 e1->pnum, e1->ec, e2->pnum, e2->ec);
758 e1 = rb_entry(rb_first(&ubi->scrub), struct ubi_wl_entry, u.rb);
763 self_check_in_wl_tree(ubi, e1, &ubi->scrub);
764 rb_erase(&e1->u.rb, &ubi->scrub);
765 dbg_wl("scrub PEB %d to PEB %d", e1->pnum, e2->pnum);
768 ubi->move_from = e1;
769 ubi->move_to = e2;
770 spin_unlock(&ubi->wl_lock);
773 * Now we are going to copy physical eraseblock @e1->pnum to @e2->pnum.
783 err = ubi_io_read_vid_hdr(ubi, e1->pnum, vid_hdr, 0);
796 dbg_wl("PEB %d has no VID header", e1->pnum);
801 * The same situation as %UBI_IO_FF, but bit-flips were
805 dbg_wl("PEB %d has no VID header but has bit-flips",
806 e1->pnum);
812 err, e1->pnum);
816 vol_id = be32_to_cpu(vid_hdr->vol_id);
817 lnum = be32_to_cpu(vid_hdr->lnum);
819 err = ubi_eba_copy_leb(ubi, e1->pnum, e2->pnum, vid_hdr);
826 * wear-leveling movement again, so put it to the
839 * Target PEB had bit-flips or write error - torture it.
851 * put this PEB to the @ubi->erroneous list to prevent
854 if (ubi->erroneous_peb_count > ubi->max_erroneous) {
856 ubi->erroneous_peb_count);
872 e1->pnum, vol_id, lnum, e2->pnum);
875 spin_lock(&ubi->wl_lock);
876 if (!ubi->move_to_put) {
877 wl_tree_add(e2, &ubi->used);
880 ubi->move_from = ubi->move_to = NULL;
881 ubi->move_to_put = ubi->wl_scheduled = 0;
882 spin_unlock(&ubi->wl_lock);
897 e2->pnum, vol_id, lnum);
904 mutex_unlock(&ubi->move_mutex);
913 if (vol_id != -1)
915 e1->pnum, vol_id, lnum, e2->pnum, err);
918 e1->pnum, e2->pnum, err);
919 spin_lock(&ubi->wl_lock);
923 wl_tree_add(e1, &ubi->erroneous);
924 ubi->erroneous_peb_count += 1;
926 wl_tree_add(e1, &ubi->scrub);
928 wl_tree_add(e1, &ubi->used);
929 ubi_assert(!ubi->move_to_put);
930 ubi->move_from = ubi->move_to = NULL;
931 ubi->wl_scheduled = 0;
932 spin_unlock(&ubi->wl_lock);
939 mutex_unlock(&ubi->move_mutex);
943 if (vol_id != -1)
945 err, e1->pnum, e2->pnum);
948 err, e1->pnum, vol_id, lnum, e2->pnum);
949 spin_lock(&ubi->wl_lock);
950 ubi->move_from = ubi->move_to = NULL;
951 ubi->move_to_put = ubi->wl_scheduled = 0;
952 spin_unlock(&ubi->wl_lock);
960 mutex_unlock(&ubi->move_mutex);
962 return err < 0 ? err : -EIO;
965 ubi->wl_scheduled = 0;
966 spin_unlock(&ubi->wl_lock);
967 mutex_unlock(&ubi->move_mutex);
973 * ensure_wear_leveling - schedule wear-leveling if it is needed.
975 * @nested: set to non-zero if this function is called from UBI worker
977 * This function checks if it is time to start wear-leveling and schedules it
988 spin_lock(&ubi->wl_lock);
989 if (ubi->wl_scheduled)
990 /* Wear-leveling is already in the work queue */
994 * If the ubi->scrub tree is not empty, scrubbing is needed, and the
997 if (!ubi->scrub.rb_node) {
998 if (!ubi->used.rb_node || !ubi->free.rb_node)
999 /* No physical eraseblocks - no deal */
1003 * We schedule wear-leveling only if the difference between the
1008 e1 = rb_entry(rb_first(&ubi->used), struct ubi_wl_entry, u.rb);
1009 e2 = find_wl_entry(ubi, &ubi->free, WL_FREE_MAX_DIFF);
1011 if (!(e2->ec - e1->ec >= UBI_WL_THRESHOLD))
1013 dbg_wl("schedule wear-leveling");
1017 ubi->wl_scheduled = 1;
1018 spin_unlock(&ubi->wl_lock);
1022 err = -ENOMEM;
1026 wrk->anchor = 0;
1027 wrk->func = &wear_leveling_worker;
1042 spin_lock(&ubi->wl_lock);
1043 ubi->wl_scheduled = 0;
1045 spin_unlock(&ubi->wl_lock);
1050 * erase_worker - physical eraseblock erase worker function.
1053 * @shutdown: non-zero if the worker has to free memory and exit
1054 * because the WL sub-system is shutting down
1064 struct ubi_wl_entry *e = wl_wrk->e;
1065 int pnum = e->pnum;
1066 int vol_id = wl_wrk->vol_id;
1067 int lnum = wl_wrk->lnum;
1071 dbg_wl("cancel erasure of PEB %d EC %d", pnum, e->ec);
1078 pnum, e->ec, wl_wrk->vol_id, wl_wrk->lnum);
1080 err = sync_erase(ubi, e, wl_wrk->torture);
1085 spin_lock(&ubi->wl_lock);
1086 wl_tree_add(e, &ubi->free);
1087 ubi->free_count++;
1088 spin_unlock(&ubi->wl_lock);
1096 /* And take care about wear-leveling */
1104 if (err == -EINTR || err == -ENOMEM || err == -EAGAIN ||
1105 err == -EBUSY) {
1108 /* Re-schedule the LEB for erasure */
1118 if (err != -EIO)
1120 * If this is not %-EIO, we have no idea what to do. Scheduling
1126 /* It is %-EIO, the PEB went bad */
1128 if (!ubi->bad_allowed) {
1133 spin_lock(&ubi->volumes_lock);
1134 if (ubi->beb_rsvd_pebs == 0) {
1135 if (ubi->avail_pebs == 0) {
1136 spin_unlock(&ubi->volumes_lock);
1140 ubi->avail_pebs -= 1;
1143 spin_unlock(&ubi->volumes_lock);
1150 spin_lock(&ubi->volumes_lock);
1151 if (ubi->beb_rsvd_pebs > 0) {
1157 ubi->avail_pebs += 1;
1160 ubi->beb_rsvd_pebs -= 1;
1162 ubi->bad_peb_count += 1;
1163 ubi->good_peb_count -= 1;
1167 else if (ubi->beb_rsvd_pebs)
1169 ubi->beb_rsvd_pebs);
1172 spin_unlock(&ubi->volumes_lock);
1178 spin_lock(&ubi->volumes_lock);
1179 ubi->avail_pebs += 1;
1180 spin_unlock(&ubi->volumes_lock);
1187 * ubi_wl_put_peb - return a PEB to the wear-leveling sub-system.
1207 ubi_assert(pnum < ubi->peb_count);
1209 down_read(&ubi->fm_protect);
1212 spin_lock(&ubi->wl_lock);
1213 e = ubi->lookuptbl[pnum];
1214 if (e == ubi->move_from) {
1218 * wear-leveling worker.
1221 spin_unlock(&ubi->wl_lock);
1223 /* Wait for the WL worker by taking the @ubi->move_mutex */
1224 mutex_lock(&ubi->move_mutex);
1225 mutex_unlock(&ubi->move_mutex);
1227 } else if (e == ubi->move_to) {
1231 * sub-system already re-mapped the LEB in 'ubi_eba_copy_leb()'
1232 * but the WL sub-system has not put the PEB to the "used" tree
1238 ubi_assert(!ubi->move_to_put);
1239 ubi->move_to_put = 1;
1240 spin_unlock(&ubi->wl_lock);
1241 up_read(&ubi->fm_protect);
1244 if (in_wl_tree(e, &ubi->used)) {
1245 self_check_in_wl_tree(ubi, e, &ubi->used);
1246 rb_erase(&e->u.rb, &ubi->used);
1247 } else if (in_wl_tree(e, &ubi->scrub)) {
1248 self_check_in_wl_tree(ubi, e, &ubi->scrub);
1249 rb_erase(&e->u.rb, &ubi->scrub);
1250 } else if (in_wl_tree(e, &ubi->erroneous)) {
1251 self_check_in_wl_tree(ubi, e, &ubi->erroneous);
1252 rb_erase(&e->u.rb, &ubi->erroneous);
1253 ubi->erroneous_peb_count -= 1;
1254 ubi_assert(ubi->erroneous_peb_count >= 0);
1258 err = prot_queue_del(ubi, e->pnum);
1262 spin_unlock(&ubi->wl_lock);
1263 up_read(&ubi->fm_protect);
1268 spin_unlock(&ubi->wl_lock);
1272 spin_lock(&ubi->wl_lock);
1273 wl_tree_add(e, &ubi->used);
1274 spin_unlock(&ubi->wl_lock);
1277 up_read(&ubi->fm_protect);
1282 * ubi_wl_scrub_peb - schedule a physical eraseblock for scrubbing.
1286 * If a bit-flip in a physical eraseblock is detected, this physical eraseblock
1298 spin_lock(&ubi->wl_lock);
1299 e = ubi->lookuptbl[pnum];
1300 if (e == ubi->move_from || in_wl_tree(e, &ubi->scrub) ||
1301 in_wl_tree(e, &ubi->erroneous)) {
1302 spin_unlock(&ubi->wl_lock);
1306 if (e == ubi->move_to) {
1313 spin_unlock(&ubi->wl_lock);
1319 if (in_wl_tree(e, &ubi->used)) {
1320 self_check_in_wl_tree(ubi, e, &ubi->used);
1321 rb_erase(&e->u.rb, &ubi->used);
1325 err = prot_queue_del(ubi, e->pnum);
1329 spin_unlock(&ubi->wl_lock);
1334 wl_tree_add(e, &ubi->scrub);
1335 spin_unlock(&ubi->wl_lock);
1338 * Technically scrubbing is the same as wear-leveling, so it is done
1345 * ubi_wl_flush - flush all pending works.
1366 vol_id, lnum, ubi->works_count);
1372 down_read(&ubi->work_sem);
1373 spin_lock(&ubi->wl_lock);
1374 list_for_each_entry_safe(wrk, tmp, &ubi->works, list) {
1375 if ((vol_id == UBI_ALL || wrk->vol_id == vol_id) &&
1376 (lnum == UBI_ALL || wrk->lnum == lnum)) {
1377 list_del(&wrk->list);
1378 ubi->works_count -= 1;
1379 ubi_assert(ubi->works_count >= 0);
1380 spin_unlock(&ubi->wl_lock);
1382 err = wrk->func(ubi, wrk, 0);
1384 up_read(&ubi->work_sem);
1388 spin_lock(&ubi->wl_lock);
1393 spin_unlock(&ubi->wl_lock);
1394 up_read(&ubi->work_sem);
1401 down_write(&ubi->work_sem);
1402 up_write(&ubi->work_sem);
1408 * tree_destroy - destroy an RB-tree.
1417 rb = root->rb_node;
1419 if (rb->rb_left)
1420 rb = rb->rb_left;
1421 else if (rb->rb_right)
1422 rb = rb->rb_right;
1428 if (rb->rb_left == &e->u.rb)
1429 rb->rb_left = NULL;
1431 rb->rb_right = NULL;
1440 * ubi_thread - UBI background thread.
1449 ubi->bgt_name, task_pid_nr(current));
1461 spin_lock(&ubi->wl_lock);
1462 if (list_empty(&ubi->works) || ubi->ro_mode ||
1463 !ubi->thread_enabled || ubi_dbg_is_bgt_disabled(ubi)) {
1465 spin_unlock(&ubi->wl_lock);
1469 spin_unlock(&ubi->wl_lock);
1474 ubi->bgt_name, err);
1478 * switch to read-only mode.
1481 ubi->bgt_name, WL_MAX_FAILURES);
1483 ubi->thread_enabled = 0;
1492 dbg_wl("background thread \"%s\" is killed", ubi->bgt_name);
1497 * shutdown_work - shutdown all pending works.
1504 flush_work(&ubi->fm_work);
1506 /* in U-Boot, we have all work done */
1509 while (!list_empty(&ubi->works)) {
1512 wrk = list_entry(ubi->works.next, struct ubi_work, list);
1513 list_del(&wrk->list);
1514 wrk->func(ubi, wrk, 1);
1515 ubi->works_count -= 1;
1516 ubi_assert(ubi->works_count >= 0);
1521 * ubi_wl_init - initialize the WL sub-system using attaching information.
1536 ubi->used = ubi->erroneous = ubi->free = ubi->scrub = RB_ROOT;
1537 spin_lock_init(&ubi->wl_lock);
1538 mutex_init(&ubi->move_mutex);
1539 init_rwsem(&ubi->work_sem);
1540 ubi->max_ec = ai->max_ec;
1541 INIT_LIST_HEAD(&ubi->works);
1543 sprintf(ubi->bgt_name, UBI_BGT_NAME_PATTERN, ubi->ubi_num);
1545 err = -ENOMEM;
1546 ubi->lookuptbl = kzalloc(ubi->peb_count * sizeof(void *), GFP_KERNEL);
1547 if (!ubi->lookuptbl)
1551 INIT_LIST_HEAD(&ubi->pq[i]);
1552 ubi->pq_head = 0;
1554 ubi->free_count = 0;
1555 list_for_each_entry_safe(aeb, tmp, &ai->erase, u.list) {
1562 e->pnum = aeb->pnum;
1563 e->ec = aeb->ec;
1564 ubi->lookuptbl[e->pnum] = e;
1565 if (schedule_erase(ubi, e, aeb->vol_id, aeb->lnum, 0)) {
1573 list_for_each_entry(aeb, &ai->free, u.list) {
1580 e->pnum = aeb->pnum;
1581 e->ec = aeb->ec;
1582 ubi_assert(e->ec >= 0);
1584 wl_tree_add(e, &ubi->free);
1585 ubi->free_count++;
1587 ubi->lookuptbl[e->pnum] = e;
1592 ubi_rb_for_each_entry(rb1, av, &ai->volumes, rb) {
1593 ubi_rb_for_each_entry(rb2, aeb, &av->root, u.rb) {
1600 e->pnum = aeb->pnum;
1601 e->ec = aeb->ec;
1602 ubi->lookuptbl[e->pnum] = e;
1604 if (!aeb->scrub) {
1606 e->pnum, e->ec);
1607 wl_tree_add(e, &ubi->used);
1610 e->pnum, e->ec);
1611 wl_tree_add(e, &ubi->scrub);
1620 if (ubi->fm) {
1621 ubi_assert(ubi->good_peb_count ==
1622 found_pebs + ubi->fm->used_blocks);
1624 for (i = 0; i < ubi->fm->used_blocks; i++) {
1625 e = ubi->fm->e[i];
1626 ubi->lookuptbl[e->pnum] = e;
1630 ubi_assert(ubi->good_peb_count == found_pebs);
1635 if (ubi->avail_pebs < reserved_pebs) {
1637 ubi->avail_pebs, reserved_pebs);
1638 if (ubi->corr_peb_count)
1640 ubi->corr_peb_count);
1643 ubi->avail_pebs -= reserved_pebs;
1644 ubi->rsvd_pebs += reserved_pebs;
1646 /* Schedule wear-leveling if needed */
1655 tree_destroy(ubi, &ubi->used);
1656 tree_destroy(ubi, &ubi->free);
1657 tree_destroy(ubi, &ubi->scrub);
1658 kfree(ubi->lookuptbl);
1663 * protection_queue_destroy - destroy the protection queue.
1672 list_for_each_entry_safe(e, tmp, &ubi->pq[i], u.list) {
1673 list_del(&e->u.list);
1680 * ubi_wl_close - close the wear-leveling sub-system.
1685 dbg_wl("close the WL sub-system");
1689 tree_destroy(ubi, &ubi->used);
1690 tree_destroy(ubi, &ubi->erroneous);
1691 tree_destroy(ubi, &ubi->free);
1692 tree_destroy(ubi, &ubi->scrub);
1693 kfree(ubi->lookuptbl);
1697 * self_check_ec - make sure that the erase counter of a PEB is correct.
1715 ec_hdr = kzalloc(ubi->ec_hdr_alsize, GFP_NOFS);
1717 return -ENOMEM;
1726 read_ec = be64_to_cpu(ec_hdr->ec);
1727 if (ec != read_ec && read_ec - ec > 1) {
1728 ubi_err(ubi, "self-check failed for PEB %d", pnum);
1741 * self_check_in_wl_tree - check that wear-leveling entry is in WL RB-tree.
1743 * @e: the wear-leveling entry to check
1746 * This function returns zero if @e is in the @root RB-tree and %-EINVAL if it
1758 ubi_err(ubi, "self-check failed for PEB %d, EC %d, RB-tree %p ",
1759 e->pnum, e->ec, root);
1761 return -EINVAL;
1765 * self_check_in_pq - check if wear-leveling entry is in the protection
1768 * @e: the wear-leveling entry to check
1770 * This function returns zero if @e is in @ubi->pq and %-EINVAL if it is not.
1782 list_for_each_entry(p, &ubi->pq[i], u.list)
1786 ubi_err(ubi, "self-check failed for PEB %d, EC %d, Protect queue",
1787 e->pnum, e->ec);
1789 return -EINVAL;
1796 e = find_wl_entry(ubi, &ubi->free, WL_FREE_MAX_DIFF);
1797 self_check_in_wl_tree(ubi, e, &ubi->free);
1798 ubi->free_count--;
1799 ubi_assert(ubi->free_count >= 0);
1800 rb_erase(&e->u.rb, &ubi->free);
1806 * produce_free_peb - produce a free physical eraseblock.
1818 while (!ubi->free.rb_node && ubi->works_count) {
1819 spin_unlock(&ubi->wl_lock);
1824 spin_lock(&ubi->wl_lock);
1833 * ubi_wl_get_peb - get a physical eraseblock.
1838 * Returns with ubi->fm_eba_sem held in read mode!
1846 down_read(&ubi->fm_eba_sem);
1847 spin_lock(&ubi->wl_lock);
1848 if (!ubi->free.rb_node) {
1849 if (ubi->works_count == 0) {
1851 ubi_assert(list_empty(&ubi->works));
1852 spin_unlock(&ubi->wl_lock);
1853 return -ENOSPC;
1858 spin_unlock(&ubi->wl_lock);
1861 spin_unlock(&ubi->wl_lock);
1862 up_read(&ubi->fm_eba_sem);
1868 spin_unlock(&ubi->wl_lock);
1870 err = ubi_self_check_all_ff(ubi, e->pnum, ubi->vid_hdr_aloffset,
1871 ubi->peb_size - ubi->vid_hdr_aloffset);
1873 ubi_err(ubi, "new PEB %d does not contain all 0xFF bytes", e->pnum);
1877 return e->pnum;
1880 #include "fastmap-wl.c"