lpt.c 59 KB

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