lpt.c 58 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * This file is part of UBIFS.
  4. *
  5. * Copyright (C) 2006-2008 Nokia Corporation.
  6. *
  7. * Authors: Adrian Hunter
  8. * Artem Bityutskiy (Битюцкий Артём)
  9. */
  10. /*
  11. * This file implements the LEB properties tree (LPT) area. The LPT area
  12. * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
  13. * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
  14. * between the log and the orphan area.
  15. *
  16. * The LPT area is like a miniature self-contained file system. It is required
  17. * that it never runs out of space, is fast to access and update, and scales
  18. * logarithmically. The LEB properties tree is implemented as a wandering tree
  19. * much like the TNC, and the LPT area has its own garbage collection.
  20. *
  21. * The LPT has two slightly different forms called the "small model" and the
  22. * "big model". The small model is used when the entire LEB properties table
  23. * can be written into a single eraseblock. In that case, garbage collection
  24. * consists of just writing the whole table, which therefore makes all other
  25. * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
  26. * selected for garbage collection, which consists of marking the clean nodes in
  27. * that LEB as dirty, and then only the dirty nodes are written out. Also, in
  28. * the case of the big model, a table of LEB numbers is saved so that the entire
  29. * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
  30. * mounted.
  31. */
  32. #include "ubifs.h"
  33. #ifndef __UBOOT__
  34. #include <log.h>
  35. #include <dm/devres.h>
  36. #include <linux/crc16.h>
  37. #include <linux/math64.h>
  38. #include <linux/slab.h>
  39. #else
  40. #include <linux/compat.h>
  41. #include <linux/err.h>
  42. #include <ubi_uboot.h>
  43. #include "crc16.h"
  44. #endif
  45. /**
  46. * do_calc_lpt_geom - calculate sizes for the LPT area.
  47. * @c: the UBIFS file-system description object
  48. *
  49. * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
  50. * properties of the flash and whether LPT is "big" (c->big_lpt).
  51. */
  52. static void do_calc_lpt_geom(struct ubifs_info *c)
  53. {
  54. int i, n, bits, per_leb_wastage, max_pnode_cnt;
  55. long long sz, tot_wastage;
  56. n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;
  57. max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
  58. c->lpt_hght = 1;
  59. n = UBIFS_LPT_FANOUT;
  60. while (n < max_pnode_cnt) {
  61. c->lpt_hght += 1;
  62. n <<= UBIFS_LPT_FANOUT_SHIFT;
  63. }
  64. c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
  65. n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT);
  66. c->nnode_cnt = n;
  67. for (i = 1; i < c->lpt_hght; i++) {
  68. n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
  69. c->nnode_cnt += n;
  70. }
  71. c->space_bits = fls(c->leb_size) - 3;
  72. c->lpt_lnum_bits = fls(c->lpt_lebs);
  73. c->lpt_offs_bits = fls(c->leb_size - 1);
  74. c->lpt_spc_bits = fls(c->leb_size);
  75. n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);
  76. c->pcnt_bits = fls(n - 1);
  77. c->lnum_bits = fls(c->max_leb_cnt - 1);
  78. bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  79. (c->big_lpt ? c->pcnt_bits : 0) +
  80. (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
  81. c->pnode_sz = (bits + 7) / 8;
  82. bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  83. (c->big_lpt ? c->pcnt_bits : 0) +
  84. (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
  85. c->nnode_sz = (bits + 7) / 8;
  86. bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  87. c->lpt_lebs * c->lpt_spc_bits * 2;
  88. c->ltab_sz = (bits + 7) / 8;
  89. bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  90. c->lnum_bits * c->lsave_cnt;
  91. c->lsave_sz = (bits + 7) / 8;
  92. /* Calculate the minimum LPT size */
  93. c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
  94. c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
  95. c->lpt_sz += c->ltab_sz;
  96. if (c->big_lpt)
  97. c->lpt_sz += c->lsave_sz;
  98. /* Add wastage */
  99. sz = c->lpt_sz;
  100. per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
  101. sz += per_leb_wastage;
  102. tot_wastage = per_leb_wastage;
  103. while (sz > c->leb_size) {
  104. sz += per_leb_wastage;
  105. sz -= c->leb_size;
  106. tot_wastage += per_leb_wastage;
  107. }
  108. tot_wastage += ALIGN(sz, c->min_io_size) - sz;
  109. c->lpt_sz += tot_wastage;
  110. }
  111. /**
  112. * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
  113. * @c: the UBIFS file-system description object
  114. *
  115. * This function returns %0 on success and a negative error code on failure.
  116. */
  117. int ubifs_calc_lpt_geom(struct ubifs_info *c)
  118. {
  119. int lebs_needed;
  120. long long sz;
  121. do_calc_lpt_geom(c);
  122. /* Verify that lpt_lebs is big enough */
  123. sz = c->lpt_sz * 2; /* Must have at least 2 times the size */
  124. lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
  125. if (lebs_needed > c->lpt_lebs) {
  126. ubifs_err(c, "too few LPT LEBs");
  127. return -EINVAL;
  128. }
  129. /* Verify that ltab fits in a single LEB (since ltab is a single node */
  130. if (c->ltab_sz > c->leb_size) {
  131. ubifs_err(c, "LPT ltab too big");
  132. return -EINVAL;
  133. }
  134. c->check_lpt_free = c->big_lpt;
  135. return 0;
  136. }
  137. /**
  138. * calc_dflt_lpt_geom - calculate default LPT geometry.
  139. * @c: the UBIFS file-system description object
  140. * @main_lebs: number of main area LEBs is passed and returned here
  141. * @big_lpt: whether the LPT area is "big" is returned here
  142. *
  143. * The size of the LPT area depends on parameters that themselves are dependent
  144. * on the size of the LPT area. This function, successively recalculates the LPT
  145. * area geometry until the parameters and resultant geometry are consistent.
  146. *
  147. * This function returns %0 on success and a negative error code on failure.
  148. */
  149. static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs,
  150. int *big_lpt)
  151. {
  152. int i, lebs_needed;
  153. long long sz;
  154. /* Start by assuming the minimum number of LPT LEBs */
  155. c->lpt_lebs = UBIFS_MIN_LPT_LEBS;
  156. c->main_lebs = *main_lebs - c->lpt_lebs;
  157. if (c->main_lebs <= 0)
  158. return -EINVAL;
  159. /* And assume we will use the small LPT model */
  160. c->big_lpt = 0;
  161. /*
  162. * Calculate the geometry based on assumptions above and then see if it
  163. * makes sense
  164. */
  165. do_calc_lpt_geom(c);
  166. /* Small LPT model must have lpt_sz < leb_size */
  167. if (c->lpt_sz > c->leb_size) {
  168. /* Nope, so try again using big LPT model */
  169. c->big_lpt = 1;
  170. do_calc_lpt_geom(c);
  171. }
  172. /* Now check there are enough LPT LEBs */
  173. for (i = 0; i < 64 ; i++) {
  174. sz = c->lpt_sz * 4; /* Allow 4 times the size */
  175. lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
  176. if (lebs_needed > c->lpt_lebs) {
  177. /* Not enough LPT LEBs so try again with more */
  178. c->lpt_lebs = lebs_needed;
  179. c->main_lebs = *main_lebs - c->lpt_lebs;
  180. if (c->main_lebs <= 0)
  181. return -EINVAL;
  182. do_calc_lpt_geom(c);
  183. continue;
  184. }
  185. if (c->ltab_sz > c->leb_size) {
  186. ubifs_err(c, "LPT ltab too big");
  187. return -EINVAL;
  188. }
  189. *main_lebs = c->main_lebs;
  190. *big_lpt = c->big_lpt;
  191. return 0;
  192. }
  193. return -EINVAL;
  194. }
  195. /**
  196. * pack_bits - pack bit fields end-to-end.
  197. * @addr: address at which to pack (passed and next address returned)
  198. * @pos: bit position at which to pack (passed and next position returned)
  199. * @val: value to pack
  200. * @nrbits: number of bits of value to pack (1-32)
  201. */
  202. static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits)
  203. {
  204. uint8_t *p = *addr;
  205. int b = *pos;
  206. ubifs_assert(nrbits > 0);
  207. ubifs_assert(nrbits <= 32);
  208. ubifs_assert(*pos >= 0);
  209. ubifs_assert(*pos < 8);
  210. ubifs_assert((val >> nrbits) == 0 || nrbits == 32);
  211. if (b) {
  212. *p |= ((uint8_t)val) << b;
  213. nrbits += b;
  214. if (nrbits > 8) {
  215. *++p = (uint8_t)(val >>= (8 - b));
  216. if (nrbits > 16) {
  217. *++p = (uint8_t)(val >>= 8);
  218. if (nrbits > 24) {
  219. *++p = (uint8_t)(val >>= 8);
  220. if (nrbits > 32)
  221. *++p = (uint8_t)(val >>= 8);
  222. }
  223. }
  224. }
  225. } else {
  226. *p = (uint8_t)val;
  227. if (nrbits > 8) {
  228. *++p = (uint8_t)(val >>= 8);
  229. if (nrbits > 16) {
  230. *++p = (uint8_t)(val >>= 8);
  231. if (nrbits > 24)
  232. *++p = (uint8_t)(val >>= 8);
  233. }
  234. }
  235. }
  236. b = nrbits & 7;
  237. if (b == 0)
  238. p++;
  239. *addr = p;
  240. *pos = b;
  241. }
  242. /**
  243. * ubifs_unpack_bits - unpack bit fields.
  244. * @addr: address at which to unpack (passed and next address returned)
  245. * @pos: bit position at which to unpack (passed and next position returned)
  246. * @nrbits: number of bits of value to unpack (1-32)
  247. *
  248. * This functions returns the value unpacked.
  249. */
  250. uint32_t ubifs_unpack_bits(uint8_t **addr, int *pos, int nrbits)
  251. {
  252. const int k = 32 - nrbits;
  253. uint8_t *p = *addr;
  254. int b = *pos;
  255. uint32_t uninitialized_var(val);
  256. const int bytes = (nrbits + b + 7) >> 3;
  257. ubifs_assert(nrbits > 0);
  258. ubifs_assert(nrbits <= 32);
  259. ubifs_assert(*pos >= 0);
  260. ubifs_assert(*pos < 8);
  261. if (b) {
  262. switch (bytes) {
  263. case 2:
  264. val = p[1];
  265. break;
  266. case 3:
  267. val = p[1] | ((uint32_t)p[2] << 8);
  268. break;
  269. case 4:
  270. val = p[1] | ((uint32_t)p[2] << 8) |
  271. ((uint32_t)p[3] << 16);
  272. break;
  273. case 5:
  274. val = p[1] | ((uint32_t)p[2] << 8) |
  275. ((uint32_t)p[3] << 16) |
  276. ((uint32_t)p[4] << 24);
  277. }
  278. val <<= (8 - b);
  279. val |= *p >> b;
  280. nrbits += b;
  281. } else {
  282. switch (bytes) {
  283. case 1:
  284. val = p[0];
  285. break;
  286. case 2:
  287. val = p[0] | ((uint32_t)p[1] << 8);
  288. break;
  289. case 3:
  290. val = p[0] | ((uint32_t)p[1] << 8) |
  291. ((uint32_t)p[2] << 16);
  292. break;
  293. case 4:
  294. val = p[0] | ((uint32_t)p[1] << 8) |
  295. ((uint32_t)p[2] << 16) |
  296. ((uint32_t)p[3] << 24);
  297. break;
  298. }
  299. }
  300. val <<= k;
  301. val >>= k;
  302. b = nrbits & 7;
  303. p += nrbits >> 3;
  304. *addr = p;
  305. *pos = b;
  306. ubifs_assert((val >> nrbits) == 0 || nrbits - b == 32);
  307. return val;
  308. }
  309. /**
  310. * ubifs_pack_pnode - pack all the bit fields of a pnode.
  311. * @c: UBIFS file-system description object
  312. * @buf: buffer into which to pack
  313. * @pnode: pnode to pack
  314. */
  315. void ubifs_pack_pnode(struct ubifs_info *c, void *buf,
  316. struct ubifs_pnode *pnode)
  317. {
  318. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  319. int i, pos = 0;
  320. uint16_t crc;
  321. pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);
  322. if (c->big_lpt)
  323. pack_bits(&addr, &pos, pnode->num, c->pcnt_bits);
  324. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  325. pack_bits(&addr, &pos, pnode->lprops[i].free >> 3,
  326. c->space_bits);
  327. pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3,
  328. c->space_bits);
  329. if (pnode->lprops[i].flags & LPROPS_INDEX)
  330. pack_bits(&addr, &pos, 1, 1);
  331. else
  332. pack_bits(&addr, &pos, 0, 1);
  333. }
  334. crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
  335. c->pnode_sz - UBIFS_LPT_CRC_BYTES);
  336. addr = buf;
  337. pos = 0;
  338. pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
  339. }
  340. /**
  341. * ubifs_pack_nnode - pack all the bit fields of a nnode.
  342. * @c: UBIFS file-system description object
  343. * @buf: buffer into which to pack
  344. * @nnode: nnode to pack
  345. */
  346. void ubifs_pack_nnode(struct ubifs_info *c, void *buf,
  347. struct ubifs_nnode *nnode)
  348. {
  349. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  350. int i, pos = 0;
  351. uint16_t crc;
  352. pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);
  353. if (c->big_lpt)
  354. pack_bits(&addr, &pos, nnode->num, c->pcnt_bits);
  355. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  356. int lnum = nnode->nbranch[i].lnum;
  357. if (lnum == 0)
  358. lnum = c->lpt_last + 1;
  359. pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);
  360. pack_bits(&addr, &pos, nnode->nbranch[i].offs,
  361. c->lpt_offs_bits);
  362. }
  363. crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
  364. c->nnode_sz - UBIFS_LPT_CRC_BYTES);
  365. addr = buf;
  366. pos = 0;
  367. pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
  368. }
  369. /**
  370. * ubifs_pack_ltab - pack the LPT's own lprops table.
  371. * @c: UBIFS file-system description object
  372. * @buf: buffer into which to pack
  373. * @ltab: LPT's own lprops table to pack
  374. */
  375. void ubifs_pack_ltab(struct ubifs_info *c, void *buf,
  376. struct ubifs_lpt_lprops *ltab)
  377. {
  378. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  379. int i, pos = 0;
  380. uint16_t crc;
  381. pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);
  382. for (i = 0; i < c->lpt_lebs; i++) {
  383. pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits);
  384. pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits);
  385. }
  386. crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
  387. c->ltab_sz - UBIFS_LPT_CRC_BYTES);
  388. addr = buf;
  389. pos = 0;
  390. pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
  391. }
  392. /**
  393. * ubifs_pack_lsave - pack the LPT's save table.
  394. * @c: UBIFS file-system description object
  395. * @buf: buffer into which to pack
  396. * @lsave: LPT's save table to pack
  397. */
  398. void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave)
  399. {
  400. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  401. int i, pos = 0;
  402. uint16_t crc;
  403. pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);
  404. for (i = 0; i < c->lsave_cnt; i++)
  405. pack_bits(&addr, &pos, lsave[i], c->lnum_bits);
  406. crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
  407. c->lsave_sz - UBIFS_LPT_CRC_BYTES);
  408. addr = buf;
  409. pos = 0;
  410. pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
  411. }
  412. /**
  413. * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
  414. * @c: UBIFS file-system description object
  415. * @lnum: LEB number to which to add dirty space
  416. * @dirty: amount of dirty space to add
  417. */
  418. void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)
  419. {
  420. if (!dirty || !lnum)
  421. return;
  422. dbg_lp("LEB %d add %d to %d",
  423. lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);
  424. ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
  425. c->ltab[lnum - c->lpt_first].dirty += dirty;
  426. }
  427. /**
  428. * set_ltab - set LPT LEB properties.
  429. * @c: UBIFS file-system description object
  430. * @lnum: LEB number
  431. * @free: amount of free space
  432. * @dirty: amount of dirty space
  433. */
  434. static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
  435. {
  436. dbg_lp("LEB %d free %d dirty %d to %d %d",
  437. lnum, c->ltab[lnum - c->lpt_first].free,
  438. c->ltab[lnum - c->lpt_first].dirty, free, dirty);
  439. ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
  440. c->ltab[lnum - c->lpt_first].free = free;
  441. c->ltab[lnum - c->lpt_first].dirty = dirty;
  442. }
  443. /**
  444. * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
  445. * @c: UBIFS file-system description object
  446. * @nnode: nnode for which to add dirt
  447. */
  448. void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)
  449. {
  450. struct ubifs_nnode *np = nnode->parent;
  451. if (np)
  452. ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,
  453. c->nnode_sz);
  454. else {
  455. ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);
  456. if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
  457. c->lpt_drty_flgs |= LTAB_DIRTY;
  458. ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
  459. }
  460. }
  461. }
  462. /**
  463. * add_pnode_dirt - add dirty space to LPT LEB properties.
  464. * @c: UBIFS file-system description object
  465. * @pnode: pnode for which to add dirt
  466. */
  467. static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
  468. {
  469. ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
  470. c->pnode_sz);
  471. }
  472. /**
  473. * calc_nnode_num - calculate nnode number.
  474. * @row: the row in the tree (root is zero)
  475. * @col: the column in the row (leftmost is zero)
  476. *
  477. * The nnode number is a number that uniquely identifies a nnode and can be used
  478. * easily to traverse the tree from the root to that nnode.
  479. *
  480. * This function calculates and returns the nnode number for the nnode at @row
  481. * and @col.
  482. */
  483. static int calc_nnode_num(int row, int col)
  484. {
  485. int num, bits;
  486. num = 1;
  487. while (row--) {
  488. bits = (col & (UBIFS_LPT_FANOUT - 1));
  489. col >>= UBIFS_LPT_FANOUT_SHIFT;
  490. num <<= UBIFS_LPT_FANOUT_SHIFT;
  491. num |= bits;
  492. }
  493. return num;
  494. }
  495. /**
  496. * calc_nnode_num_from_parent - calculate nnode number.
  497. * @c: UBIFS file-system description object
  498. * @parent: parent nnode
  499. * @iip: index in parent
  500. *
  501. * The nnode number is a number that uniquely identifies a nnode and can be used
  502. * easily to traverse the tree from the root to that nnode.
  503. *
  504. * This function calculates and returns the nnode number based on the parent's
  505. * nnode number and the index in parent.
  506. */
  507. static int calc_nnode_num_from_parent(const struct ubifs_info *c,
  508. struct ubifs_nnode *parent, int iip)
  509. {
  510. int num, shft;
  511. if (!parent)
  512. return 1;
  513. shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;
  514. num = parent->num ^ (1 << shft);
  515. num |= (UBIFS_LPT_FANOUT + iip) << shft;
  516. return num;
  517. }
  518. /**
  519. * calc_pnode_num_from_parent - calculate pnode number.
  520. * @c: UBIFS file-system description object
  521. * @parent: parent nnode
  522. * @iip: index in parent
  523. *
  524. * The pnode number is a number that uniquely identifies a pnode and can be used
  525. * easily to traverse the tree from the root to that pnode.
  526. *
  527. * This function calculates and returns the pnode number based on the parent's
  528. * nnode number and the index in parent.
  529. */
  530. static int calc_pnode_num_from_parent(const struct ubifs_info *c,
  531. struct ubifs_nnode *parent, int iip)
  532. {
  533. int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;
  534. for (i = 0; i < n; i++) {
  535. num <<= UBIFS_LPT_FANOUT_SHIFT;
  536. num |= pnum & (UBIFS_LPT_FANOUT - 1);
  537. pnum >>= UBIFS_LPT_FANOUT_SHIFT;
  538. }
  539. num <<= UBIFS_LPT_FANOUT_SHIFT;
  540. num |= iip;
  541. return num;
  542. }
  543. /**
  544. * ubifs_create_dflt_lpt - create default LPT.
  545. * @c: UBIFS file-system description object
  546. * @main_lebs: number of main area LEBs is passed and returned here
  547. * @lpt_first: LEB number of first LPT LEB
  548. * @lpt_lebs: number of LEBs for LPT is passed and returned here
  549. * @big_lpt: use big LPT model is passed and returned here
  550. *
  551. * This function returns %0 on success and a negative error code on failure.
  552. */
  553. int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first,
  554. int *lpt_lebs, int *big_lpt)
  555. {
  556. int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row;
  557. int blnum, boffs, bsz, bcnt;
  558. struct ubifs_pnode *pnode = NULL;
  559. struct ubifs_nnode *nnode = NULL;
  560. void *buf = NULL, *p;
  561. struct ubifs_lpt_lprops *ltab = NULL;
  562. int *lsave = NULL;
  563. err = calc_dflt_lpt_geom(c, main_lebs, big_lpt);
  564. if (err)
  565. return err;
  566. *lpt_lebs = c->lpt_lebs;
  567. /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */
  568. c->lpt_first = lpt_first;
  569. /* Needed by 'set_ltab()' */
  570. c->lpt_last = lpt_first + c->lpt_lebs - 1;
  571. /* Needed by 'ubifs_pack_lsave()' */
  572. c->main_first = c->leb_cnt - *main_lebs;
  573. lsave = kmalloc(sizeof(int) * c->lsave_cnt, GFP_KERNEL);
  574. pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);
  575. nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);
  576. buf = vmalloc(c->leb_size);
  577. ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
  578. if (!pnode || !nnode || !buf || !ltab || !lsave) {
  579. err = -ENOMEM;
  580. goto out;
  581. }
  582. ubifs_assert(!c->ltab);
  583. c->ltab = ltab; /* Needed by set_ltab */
  584. /* Initialize LPT's own lprops */
  585. for (i = 0; i < c->lpt_lebs; i++) {
  586. ltab[i].free = c->leb_size;
  587. ltab[i].dirty = 0;
  588. ltab[i].tgc = 0;
  589. ltab[i].cmt = 0;
  590. }
  591. lnum = lpt_first;
  592. p = buf;
  593. /* Number of leaf nodes (pnodes) */
  594. cnt = c->pnode_cnt;
  595. /*
  596. * The first pnode contains the LEB properties for the LEBs that contain
  597. * the root inode node and the root index node of the index tree.
  598. */
  599. node_sz = ALIGN(ubifs_idx_node_sz(c, 1), 8);
  600. iopos = ALIGN(node_sz, c->min_io_size);
  601. pnode->lprops[0].free = c->leb_size - iopos;
  602. pnode->lprops[0].dirty = iopos - node_sz;
  603. pnode->lprops[0].flags = LPROPS_INDEX;
  604. node_sz = UBIFS_INO_NODE_SZ;
  605. iopos = ALIGN(node_sz, c->min_io_size);
  606. pnode->lprops[1].free = c->leb_size - iopos;
  607. pnode->lprops[1].dirty = iopos - node_sz;
  608. for (i = 2; i < UBIFS_LPT_FANOUT; i++)
  609. pnode->lprops[i].free = c->leb_size;
  610. /* Add first pnode */
  611. ubifs_pack_pnode(c, p, pnode);
  612. p += c->pnode_sz;
  613. len = c->pnode_sz;
  614. pnode->num += 1;
  615. /* Reset pnode values for remaining pnodes */
  616. pnode->lprops[0].free = c->leb_size;
  617. pnode->lprops[0].dirty = 0;
  618. pnode->lprops[0].flags = 0;
  619. pnode->lprops[1].free = c->leb_size;
  620. pnode->lprops[1].dirty = 0;
  621. /*
  622. * To calculate the internal node branches, we keep information about
  623. * the level below.
  624. */
  625. blnum = lnum; /* LEB number of level below */
  626. boffs = 0; /* Offset of level below */
  627. bcnt = cnt; /* Number of nodes in level below */
  628. bsz = c->pnode_sz; /* Size of nodes in level below */
  629. /* Add all remaining pnodes */
  630. for (i = 1; i < cnt; i++) {
  631. if (len + c->pnode_sz > c->leb_size) {
  632. alen = ALIGN(len, c->min_io_size);
  633. set_ltab(c, lnum, c->leb_size - alen, alen - len);
  634. memset(p, 0xff, alen - len);
  635. err = ubifs_leb_change(c, lnum++, buf, alen);
  636. if (err)
  637. goto out;
  638. p = buf;
  639. len = 0;
  640. }
  641. ubifs_pack_pnode(c, p, pnode);
  642. p += c->pnode_sz;
  643. len += c->pnode_sz;
  644. /*
  645. * pnodes are simply numbered left to right starting at zero,
  646. * which means the pnode number can be used easily to traverse
  647. * down the tree to the corresponding pnode.
  648. */
  649. pnode->num += 1;
  650. }
  651. row = 0;
  652. for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT)
  653. row += 1;
  654. /* Add all nnodes, one level at a time */
  655. while (1) {
  656. /* Number of internal nodes (nnodes) at next level */
  657. cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);
  658. for (i = 0; i < cnt; i++) {
  659. if (len + c->nnode_sz > c->leb_size) {
  660. alen = ALIGN(len, c->min_io_size);
  661. set_ltab(c, lnum, c->leb_size - alen,
  662. alen - len);
  663. memset(p, 0xff, alen - len);
  664. err = ubifs_leb_change(c, lnum++, buf, alen);
  665. if (err)
  666. goto out;
  667. p = buf;
  668. len = 0;
  669. }
  670. /* Only 1 nnode at this level, so it is the root */
  671. if (cnt == 1) {
  672. c->lpt_lnum = lnum;
  673. c->lpt_offs = len;
  674. }
  675. /* Set branches to the level below */
  676. for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
  677. if (bcnt) {
  678. if (boffs + bsz > c->leb_size) {
  679. blnum += 1;
  680. boffs = 0;
  681. }
  682. nnode->nbranch[j].lnum = blnum;
  683. nnode->nbranch[j].offs = boffs;
  684. boffs += bsz;
  685. bcnt--;
  686. } else {
  687. nnode->nbranch[j].lnum = 0;
  688. nnode->nbranch[j].offs = 0;
  689. }
  690. }
  691. nnode->num = calc_nnode_num(row, i);
  692. ubifs_pack_nnode(c, p, nnode);
  693. p += c->nnode_sz;
  694. len += c->nnode_sz;
  695. }
  696. /* Only 1 nnode at this level, so it is the root */
  697. if (cnt == 1)
  698. break;
  699. /* Update the information about the level below */
  700. bcnt = cnt;
  701. bsz = c->nnode_sz;
  702. row -= 1;
  703. }
  704. if (*big_lpt) {
  705. /* Need to add LPT's save table */
  706. if (len + c->lsave_sz > c->leb_size) {
  707. alen = ALIGN(len, c->min_io_size);
  708. set_ltab(c, lnum, c->leb_size - alen, alen - len);
  709. memset(p, 0xff, alen - len);
  710. err = ubifs_leb_change(c, lnum++, buf, alen);
  711. if (err)
  712. goto out;
  713. p = buf;
  714. len = 0;
  715. }
  716. c->lsave_lnum = lnum;
  717. c->lsave_offs = len;
  718. for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++)
  719. lsave[i] = c->main_first + i;
  720. for (; i < c->lsave_cnt; i++)
  721. lsave[i] = c->main_first;
  722. ubifs_pack_lsave(c, p, lsave);
  723. p += c->lsave_sz;
  724. len += c->lsave_sz;
  725. }
  726. /* Need to add LPT's own LEB properties table */
  727. if (len + c->ltab_sz > c->leb_size) {
  728. alen = ALIGN(len, c->min_io_size);
  729. set_ltab(c, lnum, c->leb_size - alen, alen - len);
  730. memset(p, 0xff, alen - len);
  731. err = ubifs_leb_change(c, lnum++, buf, alen);
  732. if (err)
  733. goto out;
  734. p = buf;
  735. len = 0;
  736. }
  737. c->ltab_lnum = lnum;
  738. c->ltab_offs = len;
  739. /* Update ltab before packing it */
  740. len += c->ltab_sz;
  741. alen = ALIGN(len, c->min_io_size);
  742. set_ltab(c, lnum, c->leb_size - alen, alen - len);
  743. ubifs_pack_ltab(c, p, ltab);
  744. p += c->ltab_sz;
  745. /* Write remaining buffer */
  746. memset(p, 0xff, alen - len);
  747. err = ubifs_leb_change(c, lnum, buf, alen);
  748. if (err)
  749. goto out;
  750. c->nhead_lnum = lnum;
  751. c->nhead_offs = ALIGN(len, c->min_io_size);
  752. dbg_lp("space_bits %d", c->space_bits);
  753. dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
  754. dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
  755. dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
  756. dbg_lp("pcnt_bits %d", c->pcnt_bits);
  757. dbg_lp("lnum_bits %d", c->lnum_bits);
  758. dbg_lp("pnode_sz %d", c->pnode_sz);
  759. dbg_lp("nnode_sz %d", c->nnode_sz);
  760. dbg_lp("ltab_sz %d", c->ltab_sz);
  761. dbg_lp("lsave_sz %d", c->lsave_sz);
  762. dbg_lp("lsave_cnt %d", c->lsave_cnt);
  763. dbg_lp("lpt_hght %d", c->lpt_hght);
  764. dbg_lp("big_lpt %d", c->big_lpt);
  765. dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
  766. dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
  767. dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
  768. if (c->big_lpt)
  769. dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
  770. out:
  771. c->ltab = NULL;
  772. kfree(lsave);
  773. vfree(ltab);
  774. vfree(buf);
  775. kfree(nnode);
  776. kfree(pnode);
  777. return err;
  778. }
  779. /**
  780. * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
  781. * @c: UBIFS file-system description object
  782. * @pnode: pnode
  783. *
  784. * When a pnode is loaded into memory, the LEB properties it contains are added,
  785. * by this function, to the LEB category lists and heaps.
  786. */
  787. static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
  788. {
  789. int i;
  790. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  791. int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
  792. int lnum = pnode->lprops[i].lnum;
  793. if (!lnum)
  794. return;
  795. ubifs_add_to_cat(c, &pnode->lprops[i], cat);
  796. }
  797. }
  798. /**
  799. * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
  800. * @c: UBIFS file-system description object
  801. * @old_pnode: pnode copied
  802. * @new_pnode: pnode copy
  803. *
  804. * During commit it is sometimes necessary to copy a pnode
  805. * (see dirty_cow_pnode). When that happens, references in
  806. * category lists and heaps must be replaced. This function does that.
  807. */
  808. static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
  809. struct ubifs_pnode *new_pnode)
  810. {
  811. int i;
  812. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  813. if (!new_pnode->lprops[i].lnum)
  814. return;
  815. ubifs_replace_cat(c, &old_pnode->lprops[i],
  816. &new_pnode->lprops[i]);
  817. }
  818. }
  819. /**
  820. * check_lpt_crc - check LPT node crc is correct.
  821. * @c: UBIFS file-system description object
  822. * @buf: buffer containing node
  823. * @len: length of node
  824. *
  825. * This function returns %0 on success and a negative error code on failure.
  826. */
  827. static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len)
  828. {
  829. int pos = 0;
  830. uint8_t *addr = buf;
  831. uint16_t crc, calc_crc;
  832. crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
  833. calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
  834. len - UBIFS_LPT_CRC_BYTES);
  835. if (crc != calc_crc) {
  836. ubifs_err(c, "invalid crc in LPT node: crc %hx calc %hx",
  837. crc, calc_crc);
  838. dump_stack();
  839. return -EINVAL;
  840. }
  841. return 0;
  842. }
  843. /**
  844. * check_lpt_type - check LPT node type is correct.
  845. * @c: UBIFS file-system description object
  846. * @addr: address of type bit field is passed and returned updated here
  847. * @pos: position of type bit field is passed and returned updated here
  848. * @type: expected type
  849. *
  850. * This function returns %0 on success and a negative error code on failure.
  851. */
  852. static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr,
  853. int *pos, int type)
  854. {
  855. int node_type;
  856. node_type = ubifs_unpack_bits(addr, pos, UBIFS_LPT_TYPE_BITS);
  857. if (node_type != type) {
  858. ubifs_err(c, "invalid type (%d) in LPT node type %d",
  859. node_type, type);
  860. dump_stack();
  861. return -EINVAL;
  862. }
  863. return 0;
  864. }
  865. /**
  866. * unpack_pnode - unpack a pnode.
  867. * @c: UBIFS file-system description object
  868. * @buf: buffer containing packed pnode to unpack
  869. * @pnode: pnode structure to fill
  870. *
  871. * This function returns %0 on success and a negative error code on failure.
  872. */
  873. static int unpack_pnode(const struct ubifs_info *c, void *buf,
  874. struct ubifs_pnode *pnode)
  875. {
  876. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  877. int i, pos = 0, err;
  878. err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE);
  879. if (err)
  880. return err;
  881. if (c->big_lpt)
  882. pnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
  883. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  884. struct ubifs_lprops * const lprops = &pnode->lprops[i];
  885. lprops->free = ubifs_unpack_bits(&addr, &pos, c->space_bits);
  886. lprops->free <<= 3;
  887. lprops->dirty = ubifs_unpack_bits(&addr, &pos, c->space_bits);
  888. lprops->dirty <<= 3;
  889. if (ubifs_unpack_bits(&addr, &pos, 1))
  890. lprops->flags = LPROPS_INDEX;
  891. else
  892. lprops->flags = 0;
  893. lprops->flags |= ubifs_categorize_lprops(c, lprops);
  894. }
  895. err = check_lpt_crc(c, buf, c->pnode_sz);
  896. return err;
  897. }
  898. /**
  899. * ubifs_unpack_nnode - unpack a nnode.
  900. * @c: UBIFS file-system description object
  901. * @buf: buffer containing packed nnode to unpack
  902. * @nnode: nnode structure to fill
  903. *
  904. * This function returns %0 on success and a negative error code on failure.
  905. */
  906. int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
  907. struct ubifs_nnode *nnode)
  908. {
  909. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  910. int i, pos = 0, err;
  911. err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE);
  912. if (err)
  913. return err;
  914. if (c->big_lpt)
  915. nnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
  916. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  917. int lnum;
  918. lnum = ubifs_unpack_bits(&addr, &pos, c->lpt_lnum_bits) +
  919. c->lpt_first;
  920. if (lnum == c->lpt_last + 1)
  921. lnum = 0;
  922. nnode->nbranch[i].lnum = lnum;
  923. nnode->nbranch[i].offs = ubifs_unpack_bits(&addr, &pos,
  924. c->lpt_offs_bits);
  925. }
  926. err = check_lpt_crc(c, buf, c->nnode_sz);
  927. return err;
  928. }
  929. /**
  930. * unpack_ltab - unpack the LPT's own lprops table.
  931. * @c: UBIFS file-system description object
  932. * @buf: buffer from which to unpack
  933. *
  934. * This function returns %0 on success and a negative error code on failure.
  935. */
  936. static int unpack_ltab(const struct ubifs_info *c, void *buf)
  937. {
  938. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  939. int i, pos = 0, err;
  940. err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB);
  941. if (err)
  942. return err;
  943. for (i = 0; i < c->lpt_lebs; i++) {
  944. int free = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
  945. int dirty = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
  946. if (free < 0 || free > c->leb_size || dirty < 0 ||
  947. dirty > c->leb_size || free + dirty > c->leb_size)
  948. return -EINVAL;
  949. c->ltab[i].free = free;
  950. c->ltab[i].dirty = dirty;
  951. c->ltab[i].tgc = 0;
  952. c->ltab[i].cmt = 0;
  953. }
  954. err = check_lpt_crc(c, buf, c->ltab_sz);
  955. return err;
  956. }
  957. #ifndef __UBOOT__
  958. /**
  959. * unpack_lsave - unpack the LPT's save table.
  960. * @c: UBIFS file-system description object
  961. * @buf: buffer from which to unpack
  962. *
  963. * This function returns %0 on success and a negative error code on failure.
  964. */
  965. static int unpack_lsave(const struct ubifs_info *c, void *buf)
  966. {
  967. uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
  968. int i, pos = 0, err;
  969. err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE);
  970. if (err)
  971. return err;
  972. for (i = 0; i < c->lsave_cnt; i++) {
  973. int lnum = ubifs_unpack_bits(&addr, &pos, c->lnum_bits);
  974. if (lnum < c->main_first || lnum >= c->leb_cnt)
  975. return -EINVAL;
  976. c->lsave[i] = lnum;
  977. }
  978. err = check_lpt_crc(c, buf, c->lsave_sz);
  979. return err;
  980. }
  981. #endif
  982. /**
  983. * validate_nnode - validate a nnode.
  984. * @c: UBIFS file-system description object
  985. * @nnode: nnode to validate
  986. * @parent: parent nnode (or NULL for the root nnode)
  987. * @iip: index in parent
  988. *
  989. * This function returns %0 on success and a negative error code on failure.
  990. */
  991. static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
  992. struct ubifs_nnode *parent, int iip)
  993. {
  994. int i, lvl, max_offs;
  995. if (c->big_lpt) {
  996. int num = calc_nnode_num_from_parent(c, parent, iip);
  997. if (nnode->num != num)
  998. return -EINVAL;
  999. }
  1000. lvl = parent ? parent->level - 1 : c->lpt_hght;
  1001. if (lvl < 1)
  1002. return -EINVAL;
  1003. if (lvl == 1)
  1004. max_offs = c->leb_size - c->pnode_sz;
  1005. else
  1006. max_offs = c->leb_size - c->nnode_sz;
  1007. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1008. int lnum = nnode->nbranch[i].lnum;
  1009. int offs = nnode->nbranch[i].offs;
  1010. if (lnum == 0) {
  1011. if (offs != 0)
  1012. return -EINVAL;
  1013. continue;
  1014. }
  1015. if (lnum < c->lpt_first || lnum > c->lpt_last)
  1016. return -EINVAL;
  1017. if (offs < 0 || offs > max_offs)
  1018. return -EINVAL;
  1019. }
  1020. return 0;
  1021. }
  1022. /**
  1023. * validate_pnode - validate a pnode.
  1024. * @c: UBIFS file-system description object
  1025. * @pnode: pnode to validate
  1026. * @parent: parent nnode
  1027. * @iip: index in parent
  1028. *
  1029. * This function returns %0 on success and a negative error code on failure.
  1030. */
  1031. static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
  1032. struct ubifs_nnode *parent, int iip)
  1033. {
  1034. int i;
  1035. if (c->big_lpt) {
  1036. int num = calc_pnode_num_from_parent(c, parent, iip);
  1037. if (pnode->num != num)
  1038. return -EINVAL;
  1039. }
  1040. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1041. int free = pnode->lprops[i].free;
  1042. int dirty = pnode->lprops[i].dirty;
  1043. if (free < 0 || free > c->leb_size || free % c->min_io_size ||
  1044. (free & 7))
  1045. return -EINVAL;
  1046. if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
  1047. return -EINVAL;
  1048. if (dirty + free > c->leb_size)
  1049. return -EINVAL;
  1050. }
  1051. return 0;
  1052. }
  1053. /**
  1054. * set_pnode_lnum - set LEB numbers on a pnode.
  1055. * @c: UBIFS file-system description object
  1056. * @pnode: pnode to update
  1057. *
  1058. * This function calculates the LEB numbers for the LEB properties it contains
  1059. * based on the pnode number.
  1060. */
  1061. static void set_pnode_lnum(const struct ubifs_info *c,
  1062. struct ubifs_pnode *pnode)
  1063. {
  1064. int i, lnum;
  1065. lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
  1066. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1067. if (lnum >= c->leb_cnt)
  1068. return;
  1069. pnode->lprops[i].lnum = lnum++;
  1070. }
  1071. }
  1072. /**
  1073. * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
  1074. * @c: UBIFS file-system description object
  1075. * @parent: parent nnode (or NULL for the root)
  1076. * @iip: index in parent
  1077. *
  1078. * This function returns %0 on success and a negative error code on failure.
  1079. */
  1080. int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
  1081. {
  1082. struct ubifs_nbranch *branch = NULL;
  1083. struct ubifs_nnode *nnode = NULL;
  1084. void *buf = c->lpt_nod_buf;
  1085. int err, lnum, offs;
  1086. if (parent) {
  1087. branch = &parent->nbranch[iip];
  1088. lnum = branch->lnum;
  1089. offs = branch->offs;
  1090. } else {
  1091. lnum = c->lpt_lnum;
  1092. offs = c->lpt_offs;
  1093. }
  1094. nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
  1095. if (!nnode) {
  1096. err = -ENOMEM;
  1097. goto out;
  1098. }
  1099. if (lnum == 0) {
  1100. /*
  1101. * This nnode was not written which just means that the LEB
  1102. * properties in the subtree below it describe empty LEBs. We
  1103. * make the nnode as though we had read it, which in fact means
  1104. * doing almost nothing.
  1105. */
  1106. if (c->big_lpt)
  1107. nnode->num = calc_nnode_num_from_parent(c, parent, iip);
  1108. } else {
  1109. err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1);
  1110. if (err)
  1111. goto out;
  1112. err = ubifs_unpack_nnode(c, buf, nnode);
  1113. if (err)
  1114. goto out;
  1115. }
  1116. err = validate_nnode(c, nnode, parent, iip);
  1117. if (err)
  1118. goto out;
  1119. if (!c->big_lpt)
  1120. nnode->num = calc_nnode_num_from_parent(c, parent, iip);
  1121. if (parent) {
  1122. branch->nnode = nnode;
  1123. nnode->level = parent->level - 1;
  1124. } else {
  1125. c->nroot = nnode;
  1126. nnode->level = c->lpt_hght;
  1127. }
  1128. nnode->parent = parent;
  1129. nnode->iip = iip;
  1130. return 0;
  1131. out:
  1132. ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs);
  1133. dump_stack();
  1134. kfree(nnode);
  1135. return err;
  1136. }
  1137. /**
  1138. * read_pnode - read a pnode from flash and link it to the tree in memory.
  1139. * @c: UBIFS file-system description object
  1140. * @parent: parent nnode
  1141. * @iip: index in parent
  1142. *
  1143. * This function returns %0 on success and a negative error code on failure.
  1144. */
  1145. static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
  1146. {
  1147. struct ubifs_nbranch *branch;
  1148. struct ubifs_pnode *pnode = NULL;
  1149. void *buf = c->lpt_nod_buf;
  1150. int err, lnum, offs;
  1151. branch = &parent->nbranch[iip];
  1152. lnum = branch->lnum;
  1153. offs = branch->offs;
  1154. pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
  1155. if (!pnode)
  1156. return -ENOMEM;
  1157. if (lnum == 0) {
  1158. /*
  1159. * This pnode was not written which just means that the LEB
  1160. * properties in it describe empty LEBs. We make the pnode as
  1161. * though we had read it.
  1162. */
  1163. int i;
  1164. if (c->big_lpt)
  1165. pnode->num = calc_pnode_num_from_parent(c, parent, iip);
  1166. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1167. struct ubifs_lprops * const lprops = &pnode->lprops[i];
  1168. lprops->free = c->leb_size;
  1169. lprops->flags = ubifs_categorize_lprops(c, lprops);
  1170. }
  1171. } else {
  1172. err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1);
  1173. if (err)
  1174. goto out;
  1175. err = unpack_pnode(c, buf, pnode);
  1176. if (err)
  1177. goto out;
  1178. }
  1179. err = validate_pnode(c, pnode, parent, iip);
  1180. if (err)
  1181. goto out;
  1182. if (!c->big_lpt)
  1183. pnode->num = calc_pnode_num_from_parent(c, parent, iip);
  1184. branch->pnode = pnode;
  1185. pnode->parent = parent;
  1186. pnode->iip = iip;
  1187. set_pnode_lnum(c, pnode);
  1188. c->pnodes_have += 1;
  1189. return 0;
  1190. out:
  1191. ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs);
  1192. ubifs_dump_pnode(c, pnode, parent, iip);
  1193. dump_stack();
  1194. ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
  1195. kfree(pnode);
  1196. return err;
  1197. }
  1198. /**
  1199. * read_ltab - read LPT's own lprops table.
  1200. * @c: UBIFS file-system description object
  1201. *
  1202. * This function returns %0 on success and a negative error code on failure.
  1203. */
  1204. static int read_ltab(struct ubifs_info *c)
  1205. {
  1206. int err;
  1207. void *buf;
  1208. buf = vmalloc(c->ltab_sz);
  1209. if (!buf)
  1210. return -ENOMEM;
  1211. err = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1);
  1212. if (err)
  1213. goto out;
  1214. err = unpack_ltab(c, buf);
  1215. out:
  1216. vfree(buf);
  1217. return err;
  1218. }
  1219. #ifndef __UBOOT__
  1220. /**
  1221. * read_lsave - read LPT's save table.
  1222. * @c: UBIFS file-system description object
  1223. *
  1224. * This function returns %0 on success and a negative error code on failure.
  1225. */
  1226. static int read_lsave(struct ubifs_info *c)
  1227. {
  1228. int err, i;
  1229. void *buf;
  1230. buf = vmalloc(c->lsave_sz);
  1231. if (!buf)
  1232. return -ENOMEM;
  1233. err = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs,
  1234. c->lsave_sz, 1);
  1235. if (err)
  1236. goto out;
  1237. err = unpack_lsave(c, buf);
  1238. if (err)
  1239. goto out;
  1240. for (i = 0; i < c->lsave_cnt; i++) {
  1241. int lnum = c->lsave[i];
  1242. struct ubifs_lprops *lprops;
  1243. /*
  1244. * Due to automatic resizing, the values in the lsave table
  1245. * could be beyond the volume size - just ignore them.
  1246. */
  1247. if (lnum >= c->leb_cnt)
  1248. continue;
  1249. lprops = ubifs_lpt_lookup(c, lnum);
  1250. if (IS_ERR(lprops)) {
  1251. err = PTR_ERR(lprops);
  1252. goto out;
  1253. }
  1254. }
  1255. out:
  1256. vfree(buf);
  1257. return err;
  1258. }
  1259. #endif
  1260. /**
  1261. * ubifs_get_nnode - get a nnode.
  1262. * @c: UBIFS file-system description object
  1263. * @parent: parent nnode (or NULL for the root)
  1264. * @iip: index in parent
  1265. *
  1266. * This function returns a pointer to the nnode on success or a negative error
  1267. * code on failure.
  1268. */
  1269. struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
  1270. struct ubifs_nnode *parent, int iip)
  1271. {
  1272. struct ubifs_nbranch *branch;
  1273. struct ubifs_nnode *nnode;
  1274. int err;
  1275. branch = &parent->nbranch[iip];
  1276. nnode = branch->nnode;
  1277. if (nnode)
  1278. return nnode;
  1279. err = ubifs_read_nnode(c, parent, iip);
  1280. if (err)
  1281. return ERR_PTR(err);
  1282. return branch->nnode;
  1283. }
  1284. /**
  1285. * ubifs_get_pnode - get a pnode.
  1286. * @c: UBIFS file-system description object
  1287. * @parent: parent nnode
  1288. * @iip: index in parent
  1289. *
  1290. * This function returns a pointer to the pnode on success or a negative error
  1291. * code on failure.
  1292. */
  1293. struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
  1294. struct ubifs_nnode *parent, int iip)
  1295. {
  1296. struct ubifs_nbranch *branch;
  1297. struct ubifs_pnode *pnode;
  1298. int err;
  1299. branch = &parent->nbranch[iip];
  1300. pnode = branch->pnode;
  1301. if (pnode)
  1302. return pnode;
  1303. err = read_pnode(c, parent, iip);
  1304. if (err)
  1305. return ERR_PTR(err);
  1306. update_cats(c, branch->pnode);
  1307. return branch->pnode;
  1308. }
  1309. /**
  1310. * ubifs_lpt_lookup - lookup LEB properties in the LPT.
  1311. * @c: UBIFS file-system description object
  1312. * @lnum: LEB number to lookup
  1313. *
  1314. * This function returns a pointer to the LEB properties on success or a
  1315. * negative error code on failure.
  1316. */
  1317. struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
  1318. {
  1319. int err, i, h, iip, shft;
  1320. struct ubifs_nnode *nnode;
  1321. struct ubifs_pnode *pnode;
  1322. if (!c->nroot) {
  1323. err = ubifs_read_nnode(c, NULL, 0);
  1324. if (err)
  1325. return ERR_PTR(err);
  1326. }
  1327. nnode = c->nroot;
  1328. i = lnum - c->main_first;
  1329. shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
  1330. for (h = 1; h < c->lpt_hght; h++) {
  1331. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1332. shft -= UBIFS_LPT_FANOUT_SHIFT;
  1333. nnode = ubifs_get_nnode(c, nnode, iip);
  1334. if (IS_ERR(nnode))
  1335. return ERR_CAST(nnode);
  1336. }
  1337. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1338. pnode = ubifs_get_pnode(c, nnode, iip);
  1339. if (IS_ERR(pnode))
  1340. return ERR_CAST(pnode);
  1341. iip = (i & (UBIFS_LPT_FANOUT - 1));
  1342. dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
  1343. pnode->lprops[iip].free, pnode->lprops[iip].dirty,
  1344. pnode->lprops[iip].flags);
  1345. return &pnode->lprops[iip];
  1346. }
  1347. /**
  1348. * dirty_cow_nnode - ensure a nnode is not being committed.
  1349. * @c: UBIFS file-system description object
  1350. * @nnode: nnode to check
  1351. *
  1352. * Returns dirtied nnode on success or negative error code on failure.
  1353. */
  1354. static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
  1355. struct ubifs_nnode *nnode)
  1356. {
  1357. struct ubifs_nnode *n;
  1358. int i;
  1359. if (!test_bit(COW_CNODE, &nnode->flags)) {
  1360. /* nnode is not being committed */
  1361. if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
  1362. c->dirty_nn_cnt += 1;
  1363. ubifs_add_nnode_dirt(c, nnode);
  1364. }
  1365. return nnode;
  1366. }
  1367. /* nnode is being committed, so copy it */
  1368. n = kmalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
  1369. if (unlikely(!n))
  1370. return ERR_PTR(-ENOMEM);
  1371. memcpy(n, nnode, sizeof(struct ubifs_nnode));
  1372. n->cnext = NULL;
  1373. __set_bit(DIRTY_CNODE, &n->flags);
  1374. __clear_bit(COW_CNODE, &n->flags);
  1375. /* The children now have new parent */
  1376. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1377. struct ubifs_nbranch *branch = &n->nbranch[i];
  1378. if (branch->cnode)
  1379. branch->cnode->parent = n;
  1380. }
  1381. ubifs_assert(!test_bit(OBSOLETE_CNODE, &nnode->flags));
  1382. __set_bit(OBSOLETE_CNODE, &nnode->flags);
  1383. c->dirty_nn_cnt += 1;
  1384. ubifs_add_nnode_dirt(c, nnode);
  1385. if (nnode->parent)
  1386. nnode->parent->nbranch[n->iip].nnode = n;
  1387. else
  1388. c->nroot = n;
  1389. return n;
  1390. }
  1391. /**
  1392. * dirty_cow_pnode - ensure a pnode is not being committed.
  1393. * @c: UBIFS file-system description object
  1394. * @pnode: pnode to check
  1395. *
  1396. * Returns dirtied pnode on success or negative error code on failure.
  1397. */
  1398. static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
  1399. struct ubifs_pnode *pnode)
  1400. {
  1401. struct ubifs_pnode *p;
  1402. if (!test_bit(COW_CNODE, &pnode->flags)) {
  1403. /* pnode is not being committed */
  1404. if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
  1405. c->dirty_pn_cnt += 1;
  1406. add_pnode_dirt(c, pnode);
  1407. }
  1408. return pnode;
  1409. }
  1410. /* pnode is being committed, so copy it */
  1411. p = kmalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
  1412. if (unlikely(!p))
  1413. return ERR_PTR(-ENOMEM);
  1414. memcpy(p, pnode, sizeof(struct ubifs_pnode));
  1415. p->cnext = NULL;
  1416. __set_bit(DIRTY_CNODE, &p->flags);
  1417. __clear_bit(COW_CNODE, &p->flags);
  1418. replace_cats(c, pnode, p);
  1419. ubifs_assert(!test_bit(OBSOLETE_CNODE, &pnode->flags));
  1420. __set_bit(OBSOLETE_CNODE, &pnode->flags);
  1421. c->dirty_pn_cnt += 1;
  1422. add_pnode_dirt(c, pnode);
  1423. pnode->parent->nbranch[p->iip].pnode = p;
  1424. return p;
  1425. }
  1426. /**
  1427. * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
  1428. * @c: UBIFS file-system description object
  1429. * @lnum: LEB number to lookup
  1430. *
  1431. * This function returns a pointer to the LEB properties on success or a
  1432. * negative error code on failure.
  1433. */
  1434. struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
  1435. {
  1436. int err, i, h, iip, shft;
  1437. struct ubifs_nnode *nnode;
  1438. struct ubifs_pnode *pnode;
  1439. if (!c->nroot) {
  1440. err = ubifs_read_nnode(c, NULL, 0);
  1441. if (err)
  1442. return ERR_PTR(err);
  1443. }
  1444. nnode = c->nroot;
  1445. nnode = dirty_cow_nnode(c, nnode);
  1446. if (IS_ERR(nnode))
  1447. return ERR_CAST(nnode);
  1448. i = lnum - c->main_first;
  1449. shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
  1450. for (h = 1; h < c->lpt_hght; h++) {
  1451. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1452. shft -= UBIFS_LPT_FANOUT_SHIFT;
  1453. nnode = ubifs_get_nnode(c, nnode, iip);
  1454. if (IS_ERR(nnode))
  1455. return ERR_CAST(nnode);
  1456. nnode = dirty_cow_nnode(c, nnode);
  1457. if (IS_ERR(nnode))
  1458. return ERR_CAST(nnode);
  1459. }
  1460. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1461. pnode = ubifs_get_pnode(c, nnode, iip);
  1462. if (IS_ERR(pnode))
  1463. return ERR_CAST(pnode);
  1464. pnode = dirty_cow_pnode(c, pnode);
  1465. if (IS_ERR(pnode))
  1466. return ERR_CAST(pnode);
  1467. iip = (i & (UBIFS_LPT_FANOUT - 1));
  1468. dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
  1469. pnode->lprops[iip].free, pnode->lprops[iip].dirty,
  1470. pnode->lprops[iip].flags);
  1471. ubifs_assert(test_bit(DIRTY_CNODE, &pnode->flags));
  1472. return &pnode->lprops[iip];
  1473. }
  1474. /**
  1475. * lpt_init_rd - initialize the LPT for reading.
  1476. * @c: UBIFS file-system description object
  1477. *
  1478. * This function returns %0 on success and a negative error code on failure.
  1479. */
  1480. static int lpt_init_rd(struct ubifs_info *c)
  1481. {
  1482. int err, i;
  1483. c->ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
  1484. if (!c->ltab)
  1485. return -ENOMEM;
  1486. i = max_t(int, c->nnode_sz, c->pnode_sz);
  1487. c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
  1488. if (!c->lpt_nod_buf)
  1489. return -ENOMEM;
  1490. for (i = 0; i < LPROPS_HEAP_CNT; i++) {
  1491. c->lpt_heap[i].arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ,
  1492. GFP_KERNEL);
  1493. if (!c->lpt_heap[i].arr)
  1494. return -ENOMEM;
  1495. c->lpt_heap[i].cnt = 0;
  1496. c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
  1497. }
  1498. c->dirty_idx.arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ, GFP_KERNEL);
  1499. if (!c->dirty_idx.arr)
  1500. return -ENOMEM;
  1501. c->dirty_idx.cnt = 0;
  1502. c->dirty_idx.max_cnt = LPT_HEAP_SZ;
  1503. err = read_ltab(c);
  1504. if (err)
  1505. return err;
  1506. dbg_lp("space_bits %d", c->space_bits);
  1507. dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
  1508. dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
  1509. dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
  1510. dbg_lp("pcnt_bits %d", c->pcnt_bits);
  1511. dbg_lp("lnum_bits %d", c->lnum_bits);
  1512. dbg_lp("pnode_sz %d", c->pnode_sz);
  1513. dbg_lp("nnode_sz %d", c->nnode_sz);
  1514. dbg_lp("ltab_sz %d", c->ltab_sz);
  1515. dbg_lp("lsave_sz %d", c->lsave_sz);
  1516. dbg_lp("lsave_cnt %d", c->lsave_cnt);
  1517. dbg_lp("lpt_hght %d", c->lpt_hght);
  1518. dbg_lp("big_lpt %d", c->big_lpt);
  1519. dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
  1520. dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
  1521. dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
  1522. if (c->big_lpt)
  1523. dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
  1524. return 0;
  1525. }
  1526. #ifndef __UBOOT__
  1527. /**
  1528. * lpt_init_wr - initialize the LPT for writing.
  1529. * @c: UBIFS file-system description object
  1530. *
  1531. * 'lpt_init_rd()' must have been called already.
  1532. *
  1533. * This function returns %0 on success and a negative error code on failure.
  1534. */
  1535. static int lpt_init_wr(struct ubifs_info *c)
  1536. {
  1537. int err, i;
  1538. c->ltab_cmt = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
  1539. if (!c->ltab_cmt)
  1540. return -ENOMEM;
  1541. c->lpt_buf = vmalloc(c->leb_size);
  1542. if (!c->lpt_buf)
  1543. return -ENOMEM;
  1544. if (c->big_lpt) {
  1545. c->lsave = kmalloc(sizeof(int) * c->lsave_cnt, GFP_NOFS);
  1546. if (!c->lsave)
  1547. return -ENOMEM;
  1548. err = read_lsave(c);
  1549. if (err)
  1550. return err;
  1551. }
  1552. for (i = 0; i < c->lpt_lebs; i++)
  1553. if (c->ltab[i].free == c->leb_size) {
  1554. err = ubifs_leb_unmap(c, i + c->lpt_first);
  1555. if (err)
  1556. return err;
  1557. }
  1558. return 0;
  1559. }
  1560. #endif
  1561. /**
  1562. * ubifs_lpt_init - initialize the LPT.
  1563. * @c: UBIFS file-system description object
  1564. * @rd: whether to initialize lpt for reading
  1565. * @wr: whether to initialize lpt for writing
  1566. *
  1567. * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
  1568. * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
  1569. * true.
  1570. *
  1571. * This function returns %0 on success and a negative error code on failure.
  1572. */
  1573. int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
  1574. {
  1575. int err;
  1576. if (rd) {
  1577. err = lpt_init_rd(c);
  1578. if (err)
  1579. goto out_err;
  1580. }
  1581. #ifndef __UBOOT__
  1582. if (wr) {
  1583. err = lpt_init_wr(c);
  1584. if (err)
  1585. goto out_err;
  1586. }
  1587. #endif
  1588. return 0;
  1589. out_err:
  1590. #ifndef __UBOOT__
  1591. if (wr)
  1592. ubifs_lpt_free(c, 1);
  1593. #endif
  1594. if (rd)
  1595. ubifs_lpt_free(c, 0);
  1596. return err;
  1597. }
  1598. /**
  1599. * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
  1600. * @nnode: where to keep a nnode
  1601. * @pnode: where to keep a pnode
  1602. * @cnode: where to keep a cnode
  1603. * @in_tree: is the node in the tree in memory
  1604. * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
  1605. * the tree
  1606. * @ptr.pnode: ditto for pnode
  1607. * @ptr.cnode: ditto for cnode
  1608. */
  1609. struct lpt_scan_node {
  1610. union {
  1611. struct ubifs_nnode nnode;
  1612. struct ubifs_pnode pnode;
  1613. struct ubifs_cnode cnode;
  1614. };
  1615. int in_tree;
  1616. union {
  1617. struct ubifs_nnode *nnode;
  1618. struct ubifs_pnode *pnode;
  1619. struct ubifs_cnode *cnode;
  1620. } ptr;
  1621. };
  1622. /**
  1623. * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
  1624. * @c: the UBIFS file-system description object
  1625. * @path: where to put the nnode
  1626. * @parent: parent of the nnode
  1627. * @iip: index in parent of the nnode
  1628. *
  1629. * This function returns a pointer to the nnode on success or a negative error
  1630. * code on failure.
  1631. */
  1632. static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,
  1633. struct lpt_scan_node *path,
  1634. struct ubifs_nnode *parent, int iip)
  1635. {
  1636. struct ubifs_nbranch *branch;
  1637. struct ubifs_nnode *nnode;
  1638. void *buf = c->lpt_nod_buf;
  1639. int err;
  1640. branch = &parent->nbranch[iip];
  1641. nnode = branch->nnode;
  1642. if (nnode) {
  1643. path->in_tree = 1;
  1644. path->ptr.nnode = nnode;
  1645. return nnode;
  1646. }
  1647. nnode = &path->nnode;
  1648. path->in_tree = 0;
  1649. path->ptr.nnode = nnode;
  1650. memset(nnode, 0, sizeof(struct ubifs_nnode));
  1651. if (branch->lnum == 0) {
  1652. /*
  1653. * This nnode was not written which just means that the LEB
  1654. * properties in the subtree below it describe empty LEBs. We
  1655. * make the nnode as though we had read it, which in fact means
  1656. * doing almost nothing.
  1657. */
  1658. if (c->big_lpt)
  1659. nnode->num = calc_nnode_num_from_parent(c, parent, iip);
  1660. } else {
  1661. err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
  1662. c->nnode_sz, 1);
  1663. if (err)
  1664. return ERR_PTR(err);
  1665. err = ubifs_unpack_nnode(c, buf, nnode);
  1666. if (err)
  1667. return ERR_PTR(err);
  1668. }
  1669. err = validate_nnode(c, nnode, parent, iip);
  1670. if (err)
  1671. return ERR_PTR(err);
  1672. if (!c->big_lpt)
  1673. nnode->num = calc_nnode_num_from_parent(c, parent, iip);
  1674. nnode->level = parent->level - 1;
  1675. nnode->parent = parent;
  1676. nnode->iip = iip;
  1677. return nnode;
  1678. }
  1679. /**
  1680. * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
  1681. * @c: the UBIFS file-system description object
  1682. * @path: where to put the pnode
  1683. * @parent: parent of the pnode
  1684. * @iip: index in parent of the pnode
  1685. *
  1686. * This function returns a pointer to the pnode on success or a negative error
  1687. * code on failure.
  1688. */
  1689. static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,
  1690. struct lpt_scan_node *path,
  1691. struct ubifs_nnode *parent, int iip)
  1692. {
  1693. struct ubifs_nbranch *branch;
  1694. struct ubifs_pnode *pnode;
  1695. void *buf = c->lpt_nod_buf;
  1696. int err;
  1697. branch = &parent->nbranch[iip];
  1698. pnode = branch->pnode;
  1699. if (pnode) {
  1700. path->in_tree = 1;
  1701. path->ptr.pnode = pnode;
  1702. return pnode;
  1703. }
  1704. pnode = &path->pnode;
  1705. path->in_tree = 0;
  1706. path->ptr.pnode = pnode;
  1707. memset(pnode, 0, sizeof(struct ubifs_pnode));
  1708. if (branch->lnum == 0) {
  1709. /*
  1710. * This pnode was not written which just means that the LEB
  1711. * properties in it describe empty LEBs. We make the pnode as
  1712. * though we had read it.
  1713. */
  1714. int i;
  1715. if (c->big_lpt)
  1716. pnode->num = calc_pnode_num_from_parent(c, parent, iip);
  1717. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1718. struct ubifs_lprops * const lprops = &pnode->lprops[i];
  1719. lprops->free = c->leb_size;
  1720. lprops->flags = ubifs_categorize_lprops(c, lprops);
  1721. }
  1722. } else {
  1723. ubifs_assert(branch->lnum >= c->lpt_first &&
  1724. branch->lnum <= c->lpt_last);
  1725. ubifs_assert(branch->offs >= 0 && branch->offs < c->leb_size);
  1726. err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
  1727. c->pnode_sz, 1);
  1728. if (err)
  1729. return ERR_PTR(err);
  1730. err = unpack_pnode(c, buf, pnode);
  1731. if (err)
  1732. return ERR_PTR(err);
  1733. }
  1734. err = validate_pnode(c, pnode, parent, iip);
  1735. if (err)
  1736. return ERR_PTR(err);
  1737. if (!c->big_lpt)
  1738. pnode->num = calc_pnode_num_from_parent(c, parent, iip);
  1739. pnode->parent = parent;
  1740. pnode->iip = iip;
  1741. set_pnode_lnum(c, pnode);
  1742. return pnode;
  1743. }
  1744. /**
  1745. * ubifs_lpt_scan_nolock - scan the LPT.
  1746. * @c: the UBIFS file-system description object
  1747. * @start_lnum: LEB number from which to start scanning
  1748. * @end_lnum: LEB number at which to stop scanning
  1749. * @scan_cb: callback function called for each lprops
  1750. * @data: data to be passed to the callback function
  1751. *
  1752. * This function returns %0 on success and a negative error code on failure.
  1753. */
  1754. int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,
  1755. ubifs_lpt_scan_callback scan_cb, void *data)
  1756. {
  1757. int err = 0, i, h, iip, shft;
  1758. struct ubifs_nnode *nnode;
  1759. struct ubifs_pnode *pnode;
  1760. struct lpt_scan_node *path;
  1761. if (start_lnum == -1) {
  1762. start_lnum = end_lnum + 1;
  1763. if (start_lnum >= c->leb_cnt)
  1764. start_lnum = c->main_first;
  1765. }
  1766. ubifs_assert(start_lnum >= c->main_first && start_lnum < c->leb_cnt);
  1767. ubifs_assert(end_lnum >= c->main_first && end_lnum < c->leb_cnt);
  1768. if (!c->nroot) {
  1769. err = ubifs_read_nnode(c, NULL, 0);
  1770. if (err)
  1771. return err;
  1772. }
  1773. path = kmalloc(sizeof(struct lpt_scan_node) * (c->lpt_hght + 1),
  1774. GFP_NOFS);
  1775. if (!path)
  1776. return -ENOMEM;
  1777. path[0].ptr.nnode = c->nroot;
  1778. path[0].in_tree = 1;
  1779. again:
  1780. /* Descend to the pnode containing start_lnum */
  1781. nnode = c->nroot;
  1782. i = start_lnum - c->main_first;
  1783. shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
  1784. for (h = 1; h < c->lpt_hght; h++) {
  1785. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1786. shft -= UBIFS_LPT_FANOUT_SHIFT;
  1787. nnode = scan_get_nnode(c, path + h, nnode, iip);
  1788. if (IS_ERR(nnode)) {
  1789. err = PTR_ERR(nnode);
  1790. goto out;
  1791. }
  1792. }
  1793. iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
  1794. pnode = scan_get_pnode(c, path + h, nnode, iip);
  1795. if (IS_ERR(pnode)) {
  1796. err = PTR_ERR(pnode);
  1797. goto out;
  1798. }
  1799. iip = (i & (UBIFS_LPT_FANOUT - 1));
  1800. /* Loop for each lprops */
  1801. while (1) {
  1802. struct ubifs_lprops *lprops = &pnode->lprops[iip];
  1803. int ret, lnum = lprops->lnum;
  1804. ret = scan_cb(c, lprops, path[h].in_tree, data);
  1805. if (ret < 0) {
  1806. err = ret;
  1807. goto out;
  1808. }
  1809. if (ret & LPT_SCAN_ADD) {
  1810. /* Add all the nodes in path to the tree in memory */
  1811. for (h = 1; h < c->lpt_hght; h++) {
  1812. const size_t sz = sizeof(struct ubifs_nnode);
  1813. struct ubifs_nnode *parent;
  1814. if (path[h].in_tree)
  1815. continue;
  1816. nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS);
  1817. if (!nnode) {
  1818. err = -ENOMEM;
  1819. goto out;
  1820. }
  1821. parent = nnode->parent;
  1822. parent->nbranch[nnode->iip].nnode = nnode;
  1823. path[h].ptr.nnode = nnode;
  1824. path[h].in_tree = 1;
  1825. path[h + 1].cnode.parent = nnode;
  1826. }
  1827. if (path[h].in_tree)
  1828. ubifs_ensure_cat(c, lprops);
  1829. else {
  1830. const size_t sz = sizeof(struct ubifs_pnode);
  1831. struct ubifs_nnode *parent;
  1832. pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS);
  1833. if (!pnode) {
  1834. err = -ENOMEM;
  1835. goto out;
  1836. }
  1837. parent = pnode->parent;
  1838. parent->nbranch[pnode->iip].pnode = pnode;
  1839. path[h].ptr.pnode = pnode;
  1840. path[h].in_tree = 1;
  1841. update_cats(c, pnode);
  1842. c->pnodes_have += 1;
  1843. }
  1844. err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)
  1845. c->nroot, 0, 0);
  1846. if (err)
  1847. goto out;
  1848. err = dbg_check_cats(c);
  1849. if (err)
  1850. goto out;
  1851. }
  1852. if (ret & LPT_SCAN_STOP) {
  1853. err = 0;
  1854. break;
  1855. }
  1856. /* Get the next lprops */
  1857. if (lnum == end_lnum) {
  1858. /*
  1859. * We got to the end without finding what we were
  1860. * looking for
  1861. */
  1862. err = -ENOSPC;
  1863. goto out;
  1864. }
  1865. if (lnum + 1 >= c->leb_cnt) {
  1866. /* Wrap-around to the beginning */
  1867. start_lnum = c->main_first;
  1868. goto again;
  1869. }
  1870. if (iip + 1 < UBIFS_LPT_FANOUT) {
  1871. /* Next lprops is in the same pnode */
  1872. iip += 1;
  1873. continue;
  1874. }
  1875. /* We need to get the next pnode. Go up until we can go right */
  1876. iip = pnode->iip;
  1877. while (1) {
  1878. h -= 1;
  1879. ubifs_assert(h >= 0);
  1880. nnode = path[h].ptr.nnode;
  1881. if (iip + 1 < UBIFS_LPT_FANOUT)
  1882. break;
  1883. iip = nnode->iip;
  1884. }
  1885. /* Go right */
  1886. iip += 1;
  1887. /* Descend to the pnode */
  1888. h += 1;
  1889. for (; h < c->lpt_hght; h++) {
  1890. nnode = scan_get_nnode(c, path + h, nnode, iip);
  1891. if (IS_ERR(nnode)) {
  1892. err = PTR_ERR(nnode);
  1893. goto out;
  1894. }
  1895. iip = 0;
  1896. }
  1897. pnode = scan_get_pnode(c, path + h, nnode, iip);
  1898. if (IS_ERR(pnode)) {
  1899. err = PTR_ERR(pnode);
  1900. goto out;
  1901. }
  1902. iip = 0;
  1903. }
  1904. out:
  1905. kfree(path);
  1906. return err;
  1907. }
  1908. /**
  1909. * dbg_chk_pnode - check a pnode.
  1910. * @c: the UBIFS file-system description object
  1911. * @pnode: pnode to check
  1912. * @col: pnode column
  1913. *
  1914. * This function returns %0 on success and a negative error code on failure.
  1915. */
  1916. static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,
  1917. int col)
  1918. {
  1919. int i;
  1920. if (pnode->num != col) {
  1921. ubifs_err(c, "pnode num %d expected %d parent num %d iip %d",
  1922. pnode->num, col, pnode->parent->num, pnode->iip);
  1923. return -EINVAL;
  1924. }
  1925. for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  1926. struct ubifs_lprops *lp, *lprops = &pnode->lprops[i];
  1927. int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i +
  1928. c->main_first;
  1929. int found, cat = lprops->flags & LPROPS_CAT_MASK;
  1930. struct ubifs_lpt_heap *heap;
  1931. struct list_head *list = NULL;
  1932. if (lnum >= c->leb_cnt)
  1933. continue;
  1934. if (lprops->lnum != lnum) {
  1935. ubifs_err(c, "bad LEB number %d expected %d",
  1936. lprops->lnum, lnum);
  1937. return -EINVAL;
  1938. }
  1939. if (lprops->flags & LPROPS_TAKEN) {
  1940. if (cat != LPROPS_UNCAT) {
  1941. ubifs_err(c, "LEB %d taken but not uncat %d",
  1942. lprops->lnum, cat);
  1943. return -EINVAL;
  1944. }
  1945. continue;
  1946. }
  1947. if (lprops->flags & LPROPS_INDEX) {
  1948. switch (cat) {
  1949. case LPROPS_UNCAT:
  1950. case LPROPS_DIRTY_IDX:
  1951. case LPROPS_FRDI_IDX:
  1952. break;
  1953. default:
  1954. ubifs_err(c, "LEB %d index but cat %d",
  1955. lprops->lnum, cat);
  1956. return -EINVAL;
  1957. }
  1958. } else {
  1959. switch (cat) {
  1960. case LPROPS_UNCAT:
  1961. case LPROPS_DIRTY:
  1962. case LPROPS_FREE:
  1963. case LPROPS_EMPTY:
  1964. case LPROPS_FREEABLE:
  1965. break;
  1966. default:
  1967. ubifs_err(c, "LEB %d not index but cat %d",
  1968. lprops->lnum, cat);
  1969. return -EINVAL;
  1970. }
  1971. }
  1972. switch (cat) {
  1973. case LPROPS_UNCAT:
  1974. list = &c->uncat_list;
  1975. break;
  1976. case LPROPS_EMPTY:
  1977. list = &c->empty_list;
  1978. break;
  1979. case LPROPS_FREEABLE:
  1980. list = &c->freeable_list;
  1981. break;
  1982. case LPROPS_FRDI_IDX:
  1983. list = &c->frdi_idx_list;
  1984. break;
  1985. }
  1986. found = 0;
  1987. switch (cat) {
  1988. case LPROPS_DIRTY:
  1989. case LPROPS_DIRTY_IDX:
  1990. case LPROPS_FREE:
  1991. heap = &c->lpt_heap[cat - 1];
  1992. if (lprops->hpos < heap->cnt &&
  1993. heap->arr[lprops->hpos] == lprops)
  1994. found = 1;
  1995. break;
  1996. case LPROPS_UNCAT:
  1997. case LPROPS_EMPTY:
  1998. case LPROPS_FREEABLE:
  1999. case LPROPS_FRDI_IDX:
  2000. list_for_each_entry(lp, list, list)
  2001. if (lprops == lp) {
  2002. found = 1;
  2003. break;
  2004. }
  2005. break;
  2006. }
  2007. if (!found) {
  2008. ubifs_err(c, "LEB %d cat %d not found in cat heap/list",
  2009. lprops->lnum, cat);
  2010. return -EINVAL;
  2011. }
  2012. switch (cat) {
  2013. case LPROPS_EMPTY:
  2014. if (lprops->free != c->leb_size) {
  2015. ubifs_err(c, "LEB %d cat %d free %d dirty %d",
  2016. lprops->lnum, cat, lprops->free,
  2017. lprops->dirty);
  2018. return -EINVAL;
  2019. }
  2020. break;
  2021. case LPROPS_FREEABLE:
  2022. case LPROPS_FRDI_IDX:
  2023. if (lprops->free + lprops->dirty != c->leb_size) {
  2024. ubifs_err(c, "LEB %d cat %d free %d dirty %d",
  2025. lprops->lnum, cat, lprops->free,
  2026. lprops->dirty);
  2027. return -EINVAL;
  2028. }
  2029. break;
  2030. }
  2031. }
  2032. return 0;
  2033. }
  2034. /**
  2035. * dbg_check_lpt_nodes - check nnodes and pnodes.
  2036. * @c: the UBIFS file-system description object
  2037. * @cnode: next cnode (nnode or pnode) to check
  2038. * @row: row of cnode (root is zero)
  2039. * @col: column of cnode (leftmost is zero)
  2040. *
  2041. * This function returns %0 on success and a negative error code on failure.
  2042. */
  2043. int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,
  2044. int row, int col)
  2045. {
  2046. struct ubifs_nnode *nnode, *nn;
  2047. struct ubifs_cnode *cn;
  2048. int num, iip = 0, err;
  2049. if (!dbg_is_chk_lprops(c))
  2050. return 0;
  2051. while (cnode) {
  2052. ubifs_assert(row >= 0);
  2053. nnode = cnode->parent;
  2054. if (cnode->level) {
  2055. /* cnode is a nnode */
  2056. num = calc_nnode_num(row, col);
  2057. if (cnode->num != num) {
  2058. ubifs_err(c, "nnode num %d expected %d parent num %d iip %d",
  2059. cnode->num, num,
  2060. (nnode ? nnode->num : 0), cnode->iip);
  2061. return -EINVAL;
  2062. }
  2063. nn = (struct ubifs_nnode *)cnode;
  2064. while (iip < UBIFS_LPT_FANOUT) {
  2065. cn = nn->nbranch[iip].cnode;
  2066. if (cn) {
  2067. /* Go down */
  2068. row += 1;
  2069. col <<= UBIFS_LPT_FANOUT_SHIFT;
  2070. col += iip;
  2071. iip = 0;
  2072. cnode = cn;
  2073. break;
  2074. }
  2075. /* Go right */
  2076. iip += 1;
  2077. }
  2078. if (iip < UBIFS_LPT_FANOUT)
  2079. continue;
  2080. } else {
  2081. struct ubifs_pnode *pnode;
  2082. /* cnode is a pnode */
  2083. pnode = (struct ubifs_pnode *)cnode;
  2084. err = dbg_chk_pnode(c, pnode, col);
  2085. if (err)
  2086. return err;
  2087. }
  2088. /* Go up and to the right */
  2089. row -= 1;
  2090. col >>= UBIFS_LPT_FANOUT_SHIFT;
  2091. iip = cnode->iip + 1;
  2092. cnode = (struct ubifs_cnode *)nnode;
  2093. }
  2094. return 0;
  2095. }