lpt.c 58 KB

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