lpt.c 58 KB

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