wl.c 55 KB

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