lpt.c 62 KB

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