2437 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * This file is part of UBIFS.4 *5 * Copyright (C) 2006-2008 Nokia Corporation.6 *7 * Authors: Adrian Hunter8 * Artem Bityutskiy (Битюцкий Артём)9 */10 11/*12 * This file implements the LEB properties tree (LPT) area. The LPT area13 * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and14 * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits15 * between the log and the orphan area.16 *17 * The LPT area is like a miniature self-contained file system. It is required18 * that it never runs out of space, is fast to access and update, and scales19 * logarithmically. The LEB properties tree is implemented as a wandering tree20 * much like the TNC, and the LPT area has its own garbage collection.21 *22 * The LPT has two slightly different forms called the "small model" and the23 * "big model". The small model is used when the entire LEB properties table24 * can be written into a single eraseblock. In that case, garbage collection25 * consists of just writing the whole table, which therefore makes all other26 * eraseblocks reusable. In the case of the big model, dirty eraseblocks are27 * selected for garbage collection, which consists of marking the clean nodes in28 * that LEB as dirty, and then only the dirty nodes are written out. Also, in29 * the case of the big model, a table of LEB numbers is saved so that the entire30 * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first31 * mounted.32 */33 34#include "ubifs.h"35#include <linux/crc16.h>36#include <linux/math64.h>37#include <linux/slab.h>38 39/**40 * do_calc_lpt_geom - calculate sizes for the LPT area.41 * @c: the UBIFS file-system description object42 *43 * Calculate the sizes of LPT bit fields, nodes, and tree, based on the44 * properties of the flash and whether LPT is "big" (c->big_lpt).45 */46static void do_calc_lpt_geom(struct ubifs_info *c)47{48 int i, n, bits, per_leb_wastage, max_pnode_cnt;49 long long sz, tot_wastage;50 51 n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;52 max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);53 54 c->lpt_hght = 1;55 n = UBIFS_LPT_FANOUT;56 while (n < max_pnode_cnt) {57 c->lpt_hght += 1;58 n <<= UBIFS_LPT_FANOUT_SHIFT;59 }60 61 c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);62 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 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 75 n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);76 c->pcnt_bits = fls(n - 1);77 78 c->lnum_bits = fls(c->max_leb_cnt - 1);79 80 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +81 (c->big_lpt ? c->pcnt_bits : 0) +82 (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;83 c->pnode_sz = (bits + 7) / 8;84 85 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +86 (c->big_lpt ? c->pcnt_bits : 0) +87 (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;88 c->nnode_sz = (bits + 7) / 8;89 90 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +91 c->lpt_lebs * c->lpt_spc_bits * 2;92 c->ltab_sz = (bits + 7) / 8;93 94 bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +95 c->lnum_bits * c->lsave_cnt;96 c->lsave_sz = (bits + 7) / 8;97 98 /* Calculate the minimum LPT size */99 c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;100 c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;101 c->lpt_sz += c->ltab_sz;102 if (c->big_lpt)103 c->lpt_sz += c->lsave_sz;104 105 /* Add wastage */106 sz = c->lpt_sz;107 per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);108 sz += per_leb_wastage;109 tot_wastage = per_leb_wastage;110 while (sz > c->leb_size) {111 sz += per_leb_wastage;112 sz -= c->leb_size;113 tot_wastage += per_leb_wastage;114 }115 tot_wastage += ALIGN(sz, c->min_io_size) - sz;116 c->lpt_sz += tot_wastage;117}118 119/**120 * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.121 * @c: the UBIFS file-system description object122 *123 * This function returns %0 on success and a negative error code on failure.124 */125int ubifs_calc_lpt_geom(struct ubifs_info *c)126{127 int lebs_needed;128 long long sz;129 130 do_calc_lpt_geom(c);131 132 /* Verify that lpt_lebs is big enough */133 sz = c->lpt_sz * 2; /* Must have at least 2 times the size */134 lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);135 if (lebs_needed > c->lpt_lebs) {136 ubifs_err(c, "too few LPT LEBs");137 return -EINVAL;138 }139 140 /* Verify that ltab fits in a single LEB (since ltab is a single node */141 if (c->ltab_sz > c->leb_size) {142 ubifs_err(c, "LPT ltab too big");143 return -EINVAL;144 }145 146 c->check_lpt_free = c->big_lpt;147 return 0;148}149 150/**151 * calc_dflt_lpt_geom - calculate default LPT geometry.152 * @c: the UBIFS file-system description object153 * @main_lebs: number of main area LEBs is passed and returned here154 * @big_lpt: whether the LPT area is "big" is returned here155 *156 * The size of the LPT area depends on parameters that themselves are dependent157 * on the size of the LPT area. This function, successively recalculates the LPT158 * area geometry until the parameters and resultant geometry are consistent.159 *160 * This function returns %0 on success and a negative error code on failure.161 */162static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs,163 int *big_lpt)164{165 int i, lebs_needed;166 long long sz;167 168 /* Start by assuming the minimum number of LPT LEBs */169 c->lpt_lebs = UBIFS_MIN_LPT_LEBS;170 c->main_lebs = *main_lebs - c->lpt_lebs;171 if (c->main_lebs <= 0)172 return -EINVAL;173 174 /* And assume we will use the small LPT model */175 c->big_lpt = 0;176 177 /*178 * Calculate the geometry based on assumptions above and then see if it179 * makes sense180 */181 do_calc_lpt_geom(c);182 183 /* Small LPT model must have lpt_sz < leb_size */184 if (c->lpt_sz > c->leb_size) {185 /* Nope, so try again using big LPT model */186 c->big_lpt = 1;187 do_calc_lpt_geom(c);188 }189 190 /* Now check there are enough LPT LEBs */191 for (i = 0; i < 64 ; i++) {192 sz = c->lpt_sz * 4; /* Allow 4 times the size */193 lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);194 if (lebs_needed > c->lpt_lebs) {195 /* Not enough LPT LEBs so try again with more */196 c->lpt_lebs = lebs_needed;197 c->main_lebs = *main_lebs - c->lpt_lebs;198 if (c->main_lebs <= 0)199 return -EINVAL;200 do_calc_lpt_geom(c);201 continue;202 }203 if (c->ltab_sz > c->leb_size) {204 ubifs_err(c, "LPT ltab too big");205 return -EINVAL;206 }207 *main_lebs = c->main_lebs;208 *big_lpt = c->big_lpt;209 return 0;210 }211 return -EINVAL;212}213 214/**215 * pack_bits - pack bit fields end-to-end.216 * @c: UBIFS file-system description object217 * @addr: address at which to pack (passed and next address returned)218 * @pos: bit position at which to pack (passed and next position returned)219 * @val: value to pack220 * @nrbits: number of bits of value to pack (1-32)221 */222static void pack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, uint32_t val, int nrbits)223{224 uint8_t *p = *addr;225 int b = *pos;226 227 ubifs_assert(c, nrbits > 0);228 ubifs_assert(c, nrbits <= 32);229 ubifs_assert(c, *pos >= 0);230 ubifs_assert(c, *pos < 8);231 ubifs_assert(c, (val >> nrbits) == 0 || nrbits == 32);232 if (b) {233 *p |= ((uint8_t)val) << b;234 nrbits += b;235 if (nrbits > 8) {236 *++p = (uint8_t)(val >>= (8 - b));237 if (nrbits > 16) {238 *++p = (uint8_t)(val >>= 8);239 if (nrbits > 24) {240 *++p = (uint8_t)(val >>= 8);241 if (nrbits > 32)242 *++p = (uint8_t)(val >>= 8);243 }244 }245 }246 } else {247 *p = (uint8_t)val;248 if (nrbits > 8) {249 *++p = (uint8_t)(val >>= 8);250 if (nrbits > 16) {251 *++p = (uint8_t)(val >>= 8);252 if (nrbits > 24)253 *++p = (uint8_t)(val >>= 8);254 }255 }256 }257 b = nrbits & 7;258 if (b == 0)259 p++;260 *addr = p;261 *pos = b;262}263 264/**265 * ubifs_unpack_bits - unpack bit fields.266 * @c: UBIFS file-system description object267 * @addr: address at which to unpack (passed and next address returned)268 * @pos: bit position at which to unpack (passed and next position returned)269 * @nrbits: number of bits of value to unpack (1-32)270 *271 * This functions returns the value unpacked.272 */273uint32_t ubifs_unpack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, int nrbits)274{275 const int k = 32 - nrbits;276 uint8_t *p = *addr;277 int b = *pos;278 uint32_t val;279 const int bytes = (nrbits + b + 7) >> 3;280 281 ubifs_assert(c, nrbits > 0);282 ubifs_assert(c, nrbits <= 32);283 ubifs_assert(c, *pos >= 0);284 ubifs_assert(c, *pos < 8);285 if (b) {286 switch (bytes) {287 case 2:288 val = p[1];289 break;290 case 3:291 val = p[1] | ((uint32_t)p[2] << 8);292 break;293 case 4:294 val = p[1] | ((uint32_t)p[2] << 8) |295 ((uint32_t)p[3] << 16);296 break;297 case 5:298 val = p[1] | ((uint32_t)p[2] << 8) |299 ((uint32_t)p[3] << 16) |300 ((uint32_t)p[4] << 24);301 }302 val <<= (8 - b);303 val |= *p >> b;304 nrbits += b;305 } else {306 switch (bytes) {307 case 1:308 val = p[0];309 break;310 case 2:311 val = p[0] | ((uint32_t)p[1] << 8);312 break;313 case 3:314 val = p[0] | ((uint32_t)p[1] << 8) |315 ((uint32_t)p[2] << 16);316 break;317 case 4:318 val = p[0] | ((uint32_t)p[1] << 8) |319 ((uint32_t)p[2] << 16) |320 ((uint32_t)p[3] << 24);321 break;322 }323 }324 val <<= k;325 val >>= k;326 b = nrbits & 7;327 p += nrbits >> 3;328 *addr = p;329 *pos = b;330 ubifs_assert(c, (val >> nrbits) == 0 || nrbits - b == 32);331 return val;332}333 334/**335 * ubifs_pack_pnode - pack all the bit fields of a pnode.336 * @c: UBIFS file-system description object337 * @buf: buffer into which to pack338 * @pnode: pnode to pack339 */340void ubifs_pack_pnode(struct ubifs_info *c, void *buf,341 struct ubifs_pnode *pnode)342{343 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;344 int i, pos = 0;345 uint16_t crc;346 347 pack_bits(c, &addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);348 if (c->big_lpt)349 pack_bits(c, &addr, &pos, pnode->num, c->pcnt_bits);350 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {351 pack_bits(c, &addr, &pos, pnode->lprops[i].free >> 3,352 c->space_bits);353 pack_bits(c, &addr, &pos, pnode->lprops[i].dirty >> 3,354 c->space_bits);355 if (pnode->lprops[i].flags & LPROPS_INDEX)356 pack_bits(c, &addr, &pos, 1, 1);357 else358 pack_bits(c, &addr, &pos, 0, 1);359 }360 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,361 c->pnode_sz - UBIFS_LPT_CRC_BYTES);362 addr = buf;363 pos = 0;364 pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);365}366 367/**368 * ubifs_pack_nnode - pack all the bit fields of a nnode.369 * @c: UBIFS file-system description object370 * @buf: buffer into which to pack371 * @nnode: nnode to pack372 */373void ubifs_pack_nnode(struct ubifs_info *c, void *buf,374 struct ubifs_nnode *nnode)375{376 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;377 int i, pos = 0;378 uint16_t crc;379 380 pack_bits(c, &addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);381 if (c->big_lpt)382 pack_bits(c, &addr, &pos, nnode->num, c->pcnt_bits);383 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {384 int lnum = nnode->nbranch[i].lnum;385 386 if (lnum == 0)387 lnum = c->lpt_last + 1;388 pack_bits(c, &addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);389 pack_bits(c, &addr, &pos, nnode->nbranch[i].offs,390 c->lpt_offs_bits);391 }392 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,393 c->nnode_sz - UBIFS_LPT_CRC_BYTES);394 addr = buf;395 pos = 0;396 pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);397}398 399/**400 * ubifs_pack_ltab - pack the LPT's own lprops table.401 * @c: UBIFS file-system description object402 * @buf: buffer into which to pack403 * @ltab: LPT's own lprops table to pack404 */405void ubifs_pack_ltab(struct ubifs_info *c, void *buf,406 struct ubifs_lpt_lprops *ltab)407{408 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;409 int i, pos = 0;410 uint16_t crc;411 412 pack_bits(c, &addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);413 for (i = 0; i < c->lpt_lebs; i++) {414 pack_bits(c, &addr, &pos, ltab[i].free, c->lpt_spc_bits);415 pack_bits(c, &addr, &pos, ltab[i].dirty, c->lpt_spc_bits);416 }417 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,418 c->ltab_sz - UBIFS_LPT_CRC_BYTES);419 addr = buf;420 pos = 0;421 pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);422}423 424/**425 * ubifs_pack_lsave - pack the LPT's save table.426 * @c: UBIFS file-system description object427 * @buf: buffer into which to pack428 * @lsave: LPT's save table to pack429 */430void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave)431{432 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;433 int i, pos = 0;434 uint16_t crc;435 436 pack_bits(c, &addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);437 for (i = 0; i < c->lsave_cnt; i++)438 pack_bits(c, &addr, &pos, lsave[i], c->lnum_bits);439 crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,440 c->lsave_sz - UBIFS_LPT_CRC_BYTES);441 addr = buf;442 pos = 0;443 pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);444}445 446/**447 * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.448 * @c: UBIFS file-system description object449 * @lnum: LEB number to which to add dirty space450 * @dirty: amount of dirty space to add451 */452void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)453{454 if (!dirty || !lnum)455 return;456 dbg_lp("LEB %d add %d to %d",457 lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);458 ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);459 c->ltab[lnum - c->lpt_first].dirty += dirty;460}461 462/**463 * set_ltab - set LPT LEB properties.464 * @c: UBIFS file-system description object465 * @lnum: LEB number466 * @free: amount of free space467 * @dirty: amount of dirty space468 */469static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)470{471 dbg_lp("LEB %d free %d dirty %d to %d %d",472 lnum, c->ltab[lnum - c->lpt_first].free,473 c->ltab[lnum - c->lpt_first].dirty, free, dirty);474 ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);475 c->ltab[lnum - c->lpt_first].free = free;476 c->ltab[lnum - c->lpt_first].dirty = dirty;477}478 479/**480 * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.481 * @c: UBIFS file-system description object482 * @nnode: nnode for which to add dirt483 */484void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)485{486 struct ubifs_nnode *np = nnode->parent;487 488 if (np)489 ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,490 c->nnode_sz);491 else {492 ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);493 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {494 c->lpt_drty_flgs |= LTAB_DIRTY;495 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);496 }497 }498}499 500/**501 * add_pnode_dirt - add dirty space to LPT LEB properties.502 * @c: UBIFS file-system description object503 * @pnode: pnode for which to add dirt504 */505static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)506{507 ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,508 c->pnode_sz);509}510 511/**512 * calc_nnode_num - calculate nnode number.513 * @row: the row in the tree (root is zero)514 * @col: the column in the row (leftmost is zero)515 *516 * The nnode number is a number that uniquely identifies a nnode and can be used517 * easily to traverse the tree from the root to that nnode.518 *519 * This function calculates and returns the nnode number for the nnode at @row520 * and @col.521 */522static int calc_nnode_num(int row, int col)523{524 int num, bits;525 526 num = 1;527 while (row--) {528 bits = (col & (UBIFS_LPT_FANOUT - 1));529 col >>= UBIFS_LPT_FANOUT_SHIFT;530 num <<= UBIFS_LPT_FANOUT_SHIFT;531 num |= bits;532 }533 return num;534}535 536/**537 * calc_nnode_num_from_parent - calculate nnode number.538 * @c: UBIFS file-system description object539 * @parent: parent nnode540 * @iip: index in parent541 *542 * The nnode number is a number that uniquely identifies a nnode and can be used543 * easily to traverse the tree from the root to that nnode.544 *545 * This function calculates and returns the nnode number based on the parent's546 * nnode number and the index in parent.547 */548static int calc_nnode_num_from_parent(const struct ubifs_info *c,549 struct ubifs_nnode *parent, int iip)550{551 int num, shft;552 553 if (!parent)554 return 1;555 shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;556 num = parent->num ^ (1 << shft);557 num |= (UBIFS_LPT_FANOUT + iip) << shft;558 return num;559}560 561/**562 * calc_pnode_num_from_parent - calculate pnode number.563 * @c: UBIFS file-system description object564 * @parent: parent nnode565 * @iip: index in parent566 *567 * The pnode number is a number that uniquely identifies a pnode and can be used568 * easily to traverse the tree from the root to that pnode.569 *570 * This function calculates and returns the pnode number based on the parent's571 * nnode number and the index in parent.572 */573static int calc_pnode_num_from_parent(const struct ubifs_info *c,574 struct ubifs_nnode *parent, int iip)575{576 int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;577 578 for (i = 0; i < n; i++) {579 num <<= UBIFS_LPT_FANOUT_SHIFT;580 num |= pnum & (UBIFS_LPT_FANOUT - 1);581 pnum >>= UBIFS_LPT_FANOUT_SHIFT;582 }583 num <<= UBIFS_LPT_FANOUT_SHIFT;584 num |= iip;585 return num;586}587 588/**589 * ubifs_create_dflt_lpt - create default LPT.590 * @c: UBIFS file-system description object591 * @main_lebs: number of main area LEBs is passed and returned here592 * @lpt_first: LEB number of first LPT LEB593 * @lpt_lebs: number of LEBs for LPT is passed and returned here594 * @big_lpt: use big LPT model is passed and returned here595 * @hash: hash of the LPT is returned here596 *597 * This function returns %0 on success and a negative error code on failure.598 */599int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first,600 int *lpt_lebs, int *big_lpt, u8 *hash)601{602 int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row;603 int blnum, boffs, bsz, bcnt;604 struct ubifs_pnode *pnode = NULL;605 struct ubifs_nnode *nnode = NULL;606 void *buf = NULL, *p;607 struct ubifs_lpt_lprops *ltab = NULL;608 int *lsave = NULL;609 struct shash_desc *desc;610 611 err = calc_dflt_lpt_geom(c, main_lebs, big_lpt);612 if (err)613 return err;614 *lpt_lebs = c->lpt_lebs;615 616 /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */617 c->lpt_first = lpt_first;618 /* Needed by 'set_ltab()' */619 c->lpt_last = lpt_first + c->lpt_lebs - 1;620 /* Needed by 'ubifs_pack_lsave()' */621 c->main_first = c->leb_cnt - *main_lebs;622 623 desc = ubifs_hash_get_desc(c);624 if (IS_ERR(desc))625 return PTR_ERR(desc);626 627 lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_KERNEL);628 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);629 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);630 buf = vmalloc(c->leb_size);631 ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),632 c->lpt_lebs));633 if (!pnode || !nnode || !buf || !ltab || !lsave) {634 err = -ENOMEM;635 goto out;636 }637 638 ubifs_assert(c, !c->ltab);639 c->ltab = ltab; /* Needed by set_ltab */640 641 /* Initialize LPT's own lprops */642 for (i = 0; i < c->lpt_lebs; i++) {643 ltab[i].free = c->leb_size;644 ltab[i].dirty = 0;645 ltab[i].tgc = 0;646 ltab[i].cmt = 0;647 }648 649 lnum = lpt_first;650 p = buf;651 /* Number of leaf nodes (pnodes) */652 cnt = c->pnode_cnt;653 654 /*655 * The first pnode contains the LEB properties for the LEBs that contain656 * the root inode node and the root index node of the index tree.657 */658 node_sz = ALIGN(ubifs_idx_node_sz(c, 1), 8);659 iopos = ALIGN(node_sz, c->min_io_size);660 pnode->lprops[0].free = c->leb_size - iopos;661 pnode->lprops[0].dirty = iopos - node_sz;662 pnode->lprops[0].flags = LPROPS_INDEX;663 664 node_sz = UBIFS_INO_NODE_SZ;665 iopos = ALIGN(node_sz, c->min_io_size);666 pnode->lprops[1].free = c->leb_size - iopos;667 pnode->lprops[1].dirty = iopos - node_sz;668 669 for (i = 2; i < UBIFS_LPT_FANOUT; i++)670 pnode->lprops[i].free = c->leb_size;671 672 /* Add first pnode */673 ubifs_pack_pnode(c, p, pnode);674 err = ubifs_shash_update(c, desc, p, c->pnode_sz);675 if (err)676 goto out;677 678 p += c->pnode_sz;679 len = c->pnode_sz;680 pnode->num += 1;681 682 /* Reset pnode values for remaining pnodes */683 pnode->lprops[0].free = c->leb_size;684 pnode->lprops[0].dirty = 0;685 pnode->lprops[0].flags = 0;686 687 pnode->lprops[1].free = c->leb_size;688 pnode->lprops[1].dirty = 0;689 690 /*691 * To calculate the internal node branches, we keep information about692 * the level below.693 */694 blnum = lnum; /* LEB number of level below */695 boffs = 0; /* Offset of level below */696 bcnt = cnt; /* Number of nodes in level below */697 bsz = c->pnode_sz; /* Size of nodes in level below */698 699 /* Add all remaining pnodes */700 for (i = 1; i < cnt; i++) {701 if (len + c->pnode_sz > c->leb_size) {702 alen = ALIGN(len, c->min_io_size);703 set_ltab(c, lnum, c->leb_size - alen, alen - len);704 memset(p, 0xff, alen - len);705 err = ubifs_leb_change(c, lnum++, buf, alen);706 if (err)707 goto out;708 p = buf;709 len = 0;710 }711 ubifs_pack_pnode(c, p, pnode);712 err = ubifs_shash_update(c, desc, p, c->pnode_sz);713 if (err)714 goto out;715 716 p += c->pnode_sz;717 len += c->pnode_sz;718 /*719 * pnodes are simply numbered left to right starting at zero,720 * which means the pnode number can be used easily to traverse721 * down the tree to the corresponding pnode.722 */723 pnode->num += 1;724 }725 726 row = 0;727 for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT)728 row += 1;729 /* Add all nnodes, one level at a time */730 while (1) {731 /* Number of internal nodes (nnodes) at next level */732 cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);733 for (i = 0; i < cnt; i++) {734 if (len + c->nnode_sz > c->leb_size) {735 alen = ALIGN(len, c->min_io_size);736 set_ltab(c, lnum, c->leb_size - alen,737 alen - len);738 memset(p, 0xff, alen - len);739 err = ubifs_leb_change(c, lnum++, buf, alen);740 if (err)741 goto out;742 p = buf;743 len = 0;744 }745 /* Only 1 nnode at this level, so it is the root */746 if (cnt == 1) {747 c->lpt_lnum = lnum;748 c->lpt_offs = len;749 }750 /* Set branches to the level below */751 for (j = 0; j < UBIFS_LPT_FANOUT; j++) {752 if (bcnt) {753 if (boffs + bsz > c->leb_size) {754 blnum += 1;755 boffs = 0;756 }757 nnode->nbranch[j].lnum = blnum;758 nnode->nbranch[j].offs = boffs;759 boffs += bsz;760 bcnt--;761 } else {762 nnode->nbranch[j].lnum = 0;763 nnode->nbranch[j].offs = 0;764 }765 }766 nnode->num = calc_nnode_num(row, i);767 ubifs_pack_nnode(c, p, nnode);768 p += c->nnode_sz;769 len += c->nnode_sz;770 }771 /* Only 1 nnode at this level, so it is the root */772 if (cnt == 1)773 break;774 /* Update the information about the level below */775 bcnt = cnt;776 bsz = c->nnode_sz;777 row -= 1;778 }779 780 if (*big_lpt) {781 /* Need to add LPT's save table */782 if (len + c->lsave_sz > c->leb_size) {783 alen = ALIGN(len, c->min_io_size);784 set_ltab(c, lnum, c->leb_size - alen, alen - len);785 memset(p, 0xff, alen - len);786 err = ubifs_leb_change(c, lnum++, buf, alen);787 if (err)788 goto out;789 p = buf;790 len = 0;791 }792 793 c->lsave_lnum = lnum;794 c->lsave_offs = len;795 796 for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++)797 lsave[i] = c->main_first + i;798 for (; i < c->lsave_cnt; i++)799 lsave[i] = c->main_first;800 801 ubifs_pack_lsave(c, p, lsave);802 p += c->lsave_sz;803 len += c->lsave_sz;804 }805 806 /* Need to add LPT's own LEB properties table */807 if (len + c->ltab_sz > c->leb_size) {808 alen = ALIGN(len, c->min_io_size);809 set_ltab(c, lnum, c->leb_size - alen, alen - len);810 memset(p, 0xff, alen - len);811 err = ubifs_leb_change(c, lnum++, buf, alen);812 if (err)813 goto out;814 p = buf;815 len = 0;816 }817 818 c->ltab_lnum = lnum;819 c->ltab_offs = len;820 821 /* Update ltab before packing it */822 len += c->ltab_sz;823 alen = ALIGN(len, c->min_io_size);824 set_ltab(c, lnum, c->leb_size - alen, alen - len);825 826 ubifs_pack_ltab(c, p, ltab);827 p += c->ltab_sz;828 829 /* Write remaining buffer */830 memset(p, 0xff, alen - len);831 err = ubifs_leb_change(c, lnum, buf, alen);832 if (err)833 goto out;834 835 err = ubifs_shash_final(c, desc, hash);836 if (err)837 goto out;838 839 c->nhead_lnum = lnum;840 c->nhead_offs = ALIGN(len, c->min_io_size);841 842 dbg_lp("space_bits %d", c->space_bits);843 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);844 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);845 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);846 dbg_lp("pcnt_bits %d", c->pcnt_bits);847 dbg_lp("lnum_bits %d", c->lnum_bits);848 dbg_lp("pnode_sz %d", c->pnode_sz);849 dbg_lp("nnode_sz %d", c->nnode_sz);850 dbg_lp("ltab_sz %d", c->ltab_sz);851 dbg_lp("lsave_sz %d", c->lsave_sz);852 dbg_lp("lsave_cnt %d", c->lsave_cnt);853 dbg_lp("lpt_hght %d", c->lpt_hght);854 dbg_lp("big_lpt %u", c->big_lpt);855 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);856 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);857 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);858 if (c->big_lpt)859 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);860out:861 c->ltab = NULL;862 kfree(desc);863 kfree(lsave);864 vfree(ltab);865 vfree(buf);866 kfree(nnode);867 kfree(pnode);868 return err;869}870 871/**872 * update_cats - add LEB properties of a pnode to LEB category lists and heaps.873 * @c: UBIFS file-system description object874 * @pnode: pnode875 *876 * When a pnode is loaded into memory, the LEB properties it contains are added,877 * by this function, to the LEB category lists and heaps.878 */879static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)880{881 int i;882 883 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {884 int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;885 int lnum = pnode->lprops[i].lnum;886 887 if (!lnum)888 return;889 ubifs_add_to_cat(c, &pnode->lprops[i], cat);890 }891}892 893/**894 * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.895 * @c: UBIFS file-system description object896 * @old_pnode: pnode copied897 * @new_pnode: pnode copy898 *899 * During commit it is sometimes necessary to copy a pnode900 * (see dirty_cow_pnode). When that happens, references in901 * category lists and heaps must be replaced. This function does that.902 */903static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,904 struct ubifs_pnode *new_pnode)905{906 int i;907 908 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {909 if (!new_pnode->lprops[i].lnum)910 return;911 ubifs_replace_cat(c, &old_pnode->lprops[i],912 &new_pnode->lprops[i]);913 }914}915 916/**917 * check_lpt_crc - check LPT node crc is correct.918 * @c: UBIFS file-system description object919 * @buf: buffer containing node920 * @len: length of node921 *922 * This function returns %0 on success and a negative error code on failure.923 */924static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len)925{926 int pos = 0;927 uint8_t *addr = buf;928 uint16_t crc, calc_crc;929 930 crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);931 calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,932 len - UBIFS_LPT_CRC_BYTES);933 if (crc != calc_crc) {934 ubifs_err(c, "invalid crc in LPT node: crc %hx calc %hx",935 crc, calc_crc);936 dump_stack();937 return -EINVAL;938 }939 return 0;940}941 942/**943 * check_lpt_type - check LPT node type is correct.944 * @c: UBIFS file-system description object945 * @addr: address of type bit field is passed and returned updated here946 * @pos: position of type bit field is passed and returned updated here947 * @type: expected type948 *949 * This function returns %0 on success and a negative error code on failure.950 */951static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr,952 int *pos, int type)953{954 int node_type;955 956 node_type = ubifs_unpack_bits(c, addr, pos, UBIFS_LPT_TYPE_BITS);957 if (node_type != type) {958 ubifs_err(c, "invalid type (%d) in LPT node type %d",959 node_type, type);960 dump_stack();961 return -EINVAL;962 }963 return 0;964}965 966/**967 * unpack_pnode - unpack a pnode.968 * @c: UBIFS file-system description object969 * @buf: buffer containing packed pnode to unpack970 * @pnode: pnode structure to fill971 *972 * This function returns %0 on success and a negative error code on failure.973 */974static int unpack_pnode(const struct ubifs_info *c, void *buf,975 struct ubifs_pnode *pnode)976{977 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;978 int i, pos = 0, err;979 980 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE);981 if (err)982 return err;983 if (c->big_lpt)984 pnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);985 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {986 struct ubifs_lprops * const lprops = &pnode->lprops[i];987 988 lprops->free = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);989 lprops->free <<= 3;990 lprops->dirty = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);991 lprops->dirty <<= 3;992 993 if (ubifs_unpack_bits(c, &addr, &pos, 1))994 lprops->flags = LPROPS_INDEX;995 else996 lprops->flags = 0;997 lprops->flags |= ubifs_categorize_lprops(c, lprops);998 }999 err = check_lpt_crc(c, buf, c->pnode_sz);1000 return err;1001}1002 1003/**1004 * ubifs_unpack_nnode - unpack a nnode.1005 * @c: UBIFS file-system description object1006 * @buf: buffer containing packed nnode to unpack1007 * @nnode: nnode structure to fill1008 *1009 * This function returns %0 on success and a negative error code on failure.1010 */1011int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,1012 struct ubifs_nnode *nnode)1013{1014 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;1015 int i, pos = 0, err;1016 1017 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE);1018 if (err)1019 return err;1020 if (c->big_lpt)1021 nnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);1022 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1023 int lnum;1024 1025 lnum = ubifs_unpack_bits(c, &addr, &pos, c->lpt_lnum_bits) +1026 c->lpt_first;1027 if (lnum == c->lpt_last + 1)1028 lnum = 0;1029 nnode->nbranch[i].lnum = lnum;1030 nnode->nbranch[i].offs = ubifs_unpack_bits(c, &addr, &pos,1031 c->lpt_offs_bits);1032 }1033 err = check_lpt_crc(c, buf, c->nnode_sz);1034 return err;1035}1036 1037/**1038 * unpack_ltab - unpack the LPT's own lprops table.1039 * @c: UBIFS file-system description object1040 * @buf: buffer from which to unpack1041 *1042 * This function returns %0 on success and a negative error code on failure.1043 */1044static int unpack_ltab(const struct ubifs_info *c, void *buf)1045{1046 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;1047 int i, pos = 0, err;1048 1049 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB);1050 if (err)1051 return err;1052 for (i = 0; i < c->lpt_lebs; i++) {1053 int free = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);1054 int dirty = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);1055 1056 if (free < 0 || free > c->leb_size || dirty < 0 ||1057 dirty > c->leb_size || free + dirty > c->leb_size)1058 return -EINVAL;1059 1060 c->ltab[i].free = free;1061 c->ltab[i].dirty = dirty;1062 c->ltab[i].tgc = 0;1063 c->ltab[i].cmt = 0;1064 }1065 err = check_lpt_crc(c, buf, c->ltab_sz);1066 return err;1067}1068 1069/**1070 * unpack_lsave - unpack the LPT's save table.1071 * @c: UBIFS file-system description object1072 * @buf: buffer from which to unpack1073 *1074 * This function returns %0 on success and a negative error code on failure.1075 */1076static int unpack_lsave(const struct ubifs_info *c, void *buf)1077{1078 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;1079 int i, pos = 0, err;1080 1081 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE);1082 if (err)1083 return err;1084 for (i = 0; i < c->lsave_cnt; i++) {1085 int lnum = ubifs_unpack_bits(c, &addr, &pos, c->lnum_bits);1086 1087 if (lnum < c->main_first || lnum >= c->leb_cnt)1088 return -EINVAL;1089 c->lsave[i] = lnum;1090 }1091 err = check_lpt_crc(c, buf, c->lsave_sz);1092 return err;1093}1094 1095/**1096 * validate_nnode - validate a nnode.1097 * @c: UBIFS file-system description object1098 * @nnode: nnode to validate1099 * @parent: parent nnode (or NULL for the root nnode)1100 * @iip: index in parent1101 *1102 * This function returns %0 on success and a negative error code on failure.1103 */1104static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,1105 struct ubifs_nnode *parent, int iip)1106{1107 int i, lvl, max_offs;1108 1109 if (c->big_lpt) {1110 int num = calc_nnode_num_from_parent(c, parent, iip);1111 1112 if (nnode->num != num)1113 return -EINVAL;1114 }1115 lvl = parent ? parent->level - 1 : c->lpt_hght;1116 if (lvl < 1)1117 return -EINVAL;1118 if (lvl == 1)1119 max_offs = c->leb_size - c->pnode_sz;1120 else1121 max_offs = c->leb_size - c->nnode_sz;1122 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1123 int lnum = nnode->nbranch[i].lnum;1124 int offs = nnode->nbranch[i].offs;1125 1126 if (lnum == 0) {1127 if (offs != 0)1128 return -EINVAL;1129 continue;1130 }1131 if (lnum < c->lpt_first || lnum > c->lpt_last)1132 return -EINVAL;1133 if (offs < 0 || offs > max_offs)1134 return -EINVAL;1135 }1136 return 0;1137}1138 1139/**1140 * validate_pnode - validate a pnode.1141 * @c: UBIFS file-system description object1142 * @pnode: pnode to validate1143 * @parent: parent nnode1144 * @iip: index in parent1145 *1146 * This function returns %0 on success and a negative error code on failure.1147 */1148static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,1149 struct ubifs_nnode *parent, int iip)1150{1151 int i;1152 1153 if (c->big_lpt) {1154 int num = calc_pnode_num_from_parent(c, parent, iip);1155 1156 if (pnode->num != num)1157 return -EINVAL;1158 }1159 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1160 int free = pnode->lprops[i].free;1161 int dirty = pnode->lprops[i].dirty;1162 1163 if (free < 0 || free > c->leb_size || free % c->min_io_size ||1164 (free & 7))1165 return -EINVAL;1166 if (dirty < 0 || dirty > c->leb_size || (dirty & 7))1167 return -EINVAL;1168 if (dirty + free > c->leb_size)1169 return -EINVAL;1170 }1171 return 0;1172}1173 1174/**1175 * set_pnode_lnum - set LEB numbers on a pnode.1176 * @c: UBIFS file-system description object1177 * @pnode: pnode to update1178 *1179 * This function calculates the LEB numbers for the LEB properties it contains1180 * based on the pnode number.1181 */1182static void set_pnode_lnum(const struct ubifs_info *c,1183 struct ubifs_pnode *pnode)1184{1185 int i, lnum;1186 1187 lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;1188 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1189 if (lnum >= c->leb_cnt)1190 return;1191 pnode->lprops[i].lnum = lnum++;1192 }1193}1194 1195/**1196 * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.1197 * @c: UBIFS file-system description object1198 * @parent: parent nnode (or NULL for the root)1199 * @iip: index in parent1200 *1201 * This function returns %0 on success and a negative error code on failure.1202 */1203int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)1204{1205 struct ubifs_nbranch *branch = NULL;1206 struct ubifs_nnode *nnode = NULL;1207 void *buf = c->lpt_nod_buf;1208 int err, lnum, offs;1209 1210 if (parent) {1211 branch = &parent->nbranch[iip];1212 lnum = branch->lnum;1213 offs = branch->offs;1214 } else {1215 lnum = c->lpt_lnum;1216 offs = c->lpt_offs;1217 }1218 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);1219 if (!nnode) {1220 err = -ENOMEM;1221 goto out;1222 }1223 if (lnum == 0) {1224 /*1225 * This nnode was not written which just means that the LEB1226 * properties in the subtree below it describe empty LEBs. We1227 * make the nnode as though we had read it, which in fact means1228 * doing almost nothing.1229 */1230 if (c->big_lpt)1231 nnode->num = calc_nnode_num_from_parent(c, parent, iip);1232 } else {1233 err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1);1234 if (err)1235 goto out;1236 err = ubifs_unpack_nnode(c, buf, nnode);1237 if (err)1238 goto out;1239 }1240 err = validate_nnode(c, nnode, parent, iip);1241 if (err)1242 goto out;1243 if (!c->big_lpt)1244 nnode->num = calc_nnode_num_from_parent(c, parent, iip);1245 if (parent) {1246 branch->nnode = nnode;1247 nnode->level = parent->level - 1;1248 } else {1249 c->nroot = nnode;1250 nnode->level = c->lpt_hght;1251 }1252 nnode->parent = parent;1253 nnode->iip = iip;1254 return 0;1255 1256out:1257 ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs);1258 dump_stack();1259 kfree(nnode);1260 return err;1261}1262 1263/**1264 * read_pnode - read a pnode from flash and link it to the tree in memory.1265 * @c: UBIFS file-system description object1266 * @parent: parent nnode1267 * @iip: index in parent1268 *1269 * This function returns %0 on success and a negative error code on failure.1270 */1271static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)1272{1273 struct ubifs_nbranch *branch;1274 struct ubifs_pnode *pnode = NULL;1275 void *buf = c->lpt_nod_buf;1276 int err, lnum, offs;1277 1278 branch = &parent->nbranch[iip];1279 lnum = branch->lnum;1280 offs = branch->offs;1281 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);1282 if (!pnode)1283 return -ENOMEM;1284 1285 if (lnum == 0) {1286 /*1287 * This pnode was not written which just means that the LEB1288 * properties in it describe empty LEBs. We make the pnode as1289 * though we had read it.1290 */1291 int i;1292 1293 if (c->big_lpt)1294 pnode->num = calc_pnode_num_from_parent(c, parent, iip);1295 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1296 struct ubifs_lprops * const lprops = &pnode->lprops[i];1297 1298 lprops->free = c->leb_size;1299 lprops->flags = ubifs_categorize_lprops(c, lprops);1300 }1301 } else {1302 err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1);1303 if (err)1304 goto out;1305 err = unpack_pnode(c, buf, pnode);1306 if (err)1307 goto out;1308 }1309 err = validate_pnode(c, pnode, parent, iip);1310 if (err)1311 goto out;1312 if (!c->big_lpt)1313 pnode->num = calc_pnode_num_from_parent(c, parent, iip);1314 branch->pnode = pnode;1315 pnode->parent = parent;1316 pnode->iip = iip;1317 set_pnode_lnum(c, pnode);1318 c->pnodes_have += 1;1319 return 0;1320 1321out:1322 ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs);1323 ubifs_dump_pnode(c, pnode, parent, iip);1324 dump_stack();1325 ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip));1326 kfree(pnode);1327 return err;1328}1329 1330/**1331 * read_ltab - read LPT's own lprops table.1332 * @c: UBIFS file-system description object1333 *1334 * This function returns %0 on success and a negative error code on failure.1335 */1336static int read_ltab(struct ubifs_info *c)1337{1338 int err;1339 void *buf;1340 1341 buf = vmalloc(c->ltab_sz);1342 if (!buf)1343 return -ENOMEM;1344 err = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1);1345 if (err)1346 goto out;1347 err = unpack_ltab(c, buf);1348out:1349 vfree(buf);1350 return err;1351}1352 1353/**1354 * read_lsave - read LPT's save table.1355 * @c: UBIFS file-system description object1356 *1357 * This function returns %0 on success and a negative error code on failure.1358 */1359static int read_lsave(struct ubifs_info *c)1360{1361 int err, i;1362 void *buf;1363 1364 buf = vmalloc(c->lsave_sz);1365 if (!buf)1366 return -ENOMEM;1367 err = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs,1368 c->lsave_sz, 1);1369 if (err)1370 goto out;1371 err = unpack_lsave(c, buf);1372 if (err)1373 goto out;1374 for (i = 0; i < c->lsave_cnt; i++) {1375 int lnum = c->lsave[i];1376 struct ubifs_lprops *lprops;1377 1378 /*1379 * Due to automatic resizing, the values in the lsave table1380 * could be beyond the volume size - just ignore them.1381 */1382 if (lnum >= c->leb_cnt)1383 continue;1384 lprops = ubifs_lpt_lookup(c, lnum);1385 if (IS_ERR(lprops)) {1386 err = PTR_ERR(lprops);1387 goto out;1388 }1389 }1390out:1391 vfree(buf);1392 return err;1393}1394 1395/**1396 * ubifs_get_nnode - get a nnode.1397 * @c: UBIFS file-system description object1398 * @parent: parent nnode (or NULL for the root)1399 * @iip: index in parent1400 *1401 * This function returns a pointer to the nnode on success or a negative error1402 * code on failure.1403 */1404struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,1405 struct ubifs_nnode *parent, int iip)1406{1407 struct ubifs_nbranch *branch;1408 struct ubifs_nnode *nnode;1409 int err;1410 1411 branch = &parent->nbranch[iip];1412 nnode = branch->nnode;1413 if (nnode)1414 return nnode;1415 err = ubifs_read_nnode(c, parent, iip);1416 if (err)1417 return ERR_PTR(err);1418 return branch->nnode;1419}1420 1421/**1422 * ubifs_get_pnode - get a pnode.1423 * @c: UBIFS file-system description object1424 * @parent: parent nnode1425 * @iip: index in parent1426 *1427 * This function returns a pointer to the pnode on success or a negative error1428 * code on failure.1429 */1430struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,1431 struct ubifs_nnode *parent, int iip)1432{1433 struct ubifs_nbranch *branch;1434 struct ubifs_pnode *pnode;1435 int err;1436 1437 branch = &parent->nbranch[iip];1438 pnode = branch->pnode;1439 if (pnode)1440 return pnode;1441 err = read_pnode(c, parent, iip);1442 if (err)1443 return ERR_PTR(err);1444 update_cats(c, branch->pnode);1445 return branch->pnode;1446}1447 1448/**1449 * ubifs_pnode_lookup - lookup a pnode in the LPT.1450 * @c: UBIFS file-system description object1451 * @i: pnode number (0 to (main_lebs - 1) / UBIFS_LPT_FANOUT)1452 *1453 * This function returns a pointer to the pnode on success or a negative1454 * error code on failure.1455 */1456struct ubifs_pnode *ubifs_pnode_lookup(struct ubifs_info *c, int i)1457{1458 int err, h, iip, shft;1459 struct ubifs_nnode *nnode;1460 1461 if (!c->nroot) {1462 err = ubifs_read_nnode(c, NULL, 0);1463 if (err)1464 return ERR_PTR(err);1465 }1466 i <<= UBIFS_LPT_FANOUT_SHIFT;1467 nnode = c->nroot;1468 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;1469 for (h = 1; h < c->lpt_hght; h++) {1470 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));1471 shft -= UBIFS_LPT_FANOUT_SHIFT;1472 nnode = ubifs_get_nnode(c, nnode, iip);1473 if (IS_ERR(nnode))1474 return ERR_CAST(nnode);1475 }1476 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));1477 return ubifs_get_pnode(c, nnode, iip);1478}1479 1480/**1481 * ubifs_lpt_lookup - lookup LEB properties in the LPT.1482 * @c: UBIFS file-system description object1483 * @lnum: LEB number to lookup1484 *1485 * This function returns a pointer to the LEB properties on success or a1486 * negative error code on failure.1487 */1488struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)1489{1490 int i, iip;1491 struct ubifs_pnode *pnode;1492 1493 i = lnum - c->main_first;1494 pnode = ubifs_pnode_lookup(c, i >> UBIFS_LPT_FANOUT_SHIFT);1495 if (IS_ERR(pnode))1496 return ERR_CAST(pnode);1497 iip = (i & (UBIFS_LPT_FANOUT - 1));1498 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,1499 pnode->lprops[iip].free, pnode->lprops[iip].dirty,1500 pnode->lprops[iip].flags);1501 return &pnode->lprops[iip];1502}1503 1504/**1505 * dirty_cow_nnode - ensure a nnode is not being committed.1506 * @c: UBIFS file-system description object1507 * @nnode: nnode to check1508 *1509 * Returns dirtied nnode on success or negative error code on failure.1510 */1511static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,1512 struct ubifs_nnode *nnode)1513{1514 struct ubifs_nnode *n;1515 int i;1516 1517 if (!test_bit(COW_CNODE, &nnode->flags)) {1518 /* nnode is not being committed */1519 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {1520 c->dirty_nn_cnt += 1;1521 ubifs_add_nnode_dirt(c, nnode);1522 }1523 return nnode;1524 }1525 1526 /* nnode is being committed, so copy it */1527 n = kmemdup(nnode, sizeof(struct ubifs_nnode), GFP_NOFS);1528 if (unlikely(!n))1529 return ERR_PTR(-ENOMEM);1530 1531 n->cnext = NULL;1532 __set_bit(DIRTY_CNODE, &n->flags);1533 __clear_bit(COW_CNODE, &n->flags);1534 1535 /* The children now have new parent */1536 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1537 struct ubifs_nbranch *branch = &n->nbranch[i];1538 1539 if (branch->cnode)1540 branch->cnode->parent = n;1541 }1542 1543 ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &nnode->flags));1544 __set_bit(OBSOLETE_CNODE, &nnode->flags);1545 1546 c->dirty_nn_cnt += 1;1547 ubifs_add_nnode_dirt(c, nnode);1548 if (nnode->parent)1549 nnode->parent->nbranch[n->iip].nnode = n;1550 else1551 c->nroot = n;1552 return n;1553}1554 1555/**1556 * dirty_cow_pnode - ensure a pnode is not being committed.1557 * @c: UBIFS file-system description object1558 * @pnode: pnode to check1559 *1560 * Returns dirtied pnode on success or negative error code on failure.1561 */1562static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,1563 struct ubifs_pnode *pnode)1564{1565 struct ubifs_pnode *p;1566 1567 if (!test_bit(COW_CNODE, &pnode->flags)) {1568 /* pnode is not being committed */1569 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {1570 c->dirty_pn_cnt += 1;1571 add_pnode_dirt(c, pnode);1572 }1573 return pnode;1574 }1575 1576 /* pnode is being committed, so copy it */1577 p = kmemdup(pnode, sizeof(struct ubifs_pnode), GFP_NOFS);1578 if (unlikely(!p))1579 return ERR_PTR(-ENOMEM);1580 1581 p->cnext = NULL;1582 __set_bit(DIRTY_CNODE, &p->flags);1583 __clear_bit(COW_CNODE, &p->flags);1584 replace_cats(c, pnode, p);1585 1586 ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &pnode->flags));1587 __set_bit(OBSOLETE_CNODE, &pnode->flags);1588 1589 c->dirty_pn_cnt += 1;1590 add_pnode_dirt(c, pnode);1591 pnode->parent->nbranch[p->iip].pnode = p;1592 return p;1593}1594 1595/**1596 * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.1597 * @c: UBIFS file-system description object1598 * @lnum: LEB number to lookup1599 *1600 * This function returns a pointer to the LEB properties on success or a1601 * negative error code on failure.1602 */1603struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)1604{1605 int err, i, h, iip, shft;1606 struct ubifs_nnode *nnode;1607 struct ubifs_pnode *pnode;1608 1609 if (!c->nroot) {1610 err = ubifs_read_nnode(c, NULL, 0);1611 if (err)1612 return ERR_PTR(err);1613 }1614 nnode = c->nroot;1615 nnode = dirty_cow_nnode(c, nnode);1616 if (IS_ERR(nnode))1617 return ERR_CAST(nnode);1618 i = lnum - c->main_first;1619 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;1620 for (h = 1; h < c->lpt_hght; h++) {1621 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));1622 shft -= UBIFS_LPT_FANOUT_SHIFT;1623 nnode = ubifs_get_nnode(c, nnode, iip);1624 if (IS_ERR(nnode))1625 return ERR_CAST(nnode);1626 nnode = dirty_cow_nnode(c, nnode);1627 if (IS_ERR(nnode))1628 return ERR_CAST(nnode);1629 }1630 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));1631 pnode = ubifs_get_pnode(c, nnode, iip);1632 if (IS_ERR(pnode))1633 return ERR_CAST(pnode);1634 pnode = dirty_cow_pnode(c, pnode);1635 if (IS_ERR(pnode))1636 return ERR_CAST(pnode);1637 iip = (i & (UBIFS_LPT_FANOUT - 1));1638 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,1639 pnode->lprops[iip].free, pnode->lprops[iip].dirty,1640 pnode->lprops[iip].flags);1641 ubifs_assert(c, test_bit(DIRTY_CNODE, &pnode->flags));1642 return &pnode->lprops[iip];1643}1644 1645/**1646 * ubifs_lpt_calc_hash - Calculate hash of the LPT pnodes1647 * @c: UBIFS file-system description object1648 * @hash: the returned hash of the LPT pnodes1649 *1650 * This function iterates over the LPT pnodes and creates a hash over them.1651 * Returns 0 for success or a negative error code otherwise.1652 */1653int ubifs_lpt_calc_hash(struct ubifs_info *c, u8 *hash)1654{1655 struct ubifs_nnode *nnode, *nn;1656 struct ubifs_cnode *cnode;1657 struct shash_desc *desc;1658 int iip = 0, i;1659 int bufsiz = max_t(int, c->nnode_sz, c->pnode_sz);1660 void *buf;1661 int err;1662 1663 if (!ubifs_authenticated(c))1664 return 0;1665 1666 if (!c->nroot) {1667 err = ubifs_read_nnode(c, NULL, 0);1668 if (err)1669 return err;1670 }1671 1672 desc = ubifs_hash_get_desc(c);1673 if (IS_ERR(desc))1674 return PTR_ERR(desc);1675 1676 buf = kmalloc(bufsiz, GFP_NOFS);1677 if (!buf) {1678 err = -ENOMEM;1679 goto out;1680 }1681 1682 cnode = (struct ubifs_cnode *)c->nroot;1683 1684 while (cnode) {1685 nnode = cnode->parent;1686 nn = (struct ubifs_nnode *)cnode;1687 if (cnode->level > 1) {1688 while (iip < UBIFS_LPT_FANOUT) {1689 if (nn->nbranch[iip].lnum == 0) {1690 /* Go right */1691 iip++;1692 continue;1693 }1694 1695 nnode = ubifs_get_nnode(c, nn, iip);1696 if (IS_ERR(nnode)) {1697 err = PTR_ERR(nnode);1698 goto out;1699 }1700 1701 /* Go down */1702 iip = 0;1703 cnode = (struct ubifs_cnode *)nnode;1704 break;1705 }1706 if (iip < UBIFS_LPT_FANOUT)1707 continue;1708 } else {1709 struct ubifs_pnode *pnode;1710 1711 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {1712 if (nn->nbranch[i].lnum == 0)1713 continue;1714 pnode = ubifs_get_pnode(c, nn, i);1715 if (IS_ERR(pnode)) {1716 err = PTR_ERR(pnode);1717 goto out;1718 }1719 1720 ubifs_pack_pnode(c, buf, pnode);1721 err = ubifs_shash_update(c, desc, buf,1722 c->pnode_sz);1723 if (err)1724 goto out;1725 }1726 }1727 /* Go up and to the right */1728 iip = cnode->iip + 1;1729 cnode = (struct ubifs_cnode *)nnode;1730 }1731 1732 err = ubifs_shash_final(c, desc, hash);1733out:1734 kfree(desc);1735 kfree(buf);1736 1737 return err;1738}1739 1740/**1741 * lpt_check_hash - check the hash of the LPT.1742 * @c: UBIFS file-system description object1743 *1744 * This function calculates a hash over all pnodes in the LPT and compares it with1745 * the hash stored in the master node. Returns %0 on success and a negative error1746 * code on failure.1747 */1748static int lpt_check_hash(struct ubifs_info *c)1749{1750 int err;1751 u8 hash[UBIFS_HASH_ARR_SZ];1752 1753 if (!ubifs_authenticated(c))1754 return 0;1755 1756 err = ubifs_lpt_calc_hash(c, hash);1757 if (err)1758 return err;1759 1760 if (ubifs_check_hash(c, c->mst_node->hash_lpt, hash)) {1761 err = -EPERM;1762 ubifs_err(c, "Failed to authenticate LPT");1763 } else {1764 err = 0;1765 }1766 1767 return err;1768}1769 1770/**1771 * lpt_init_rd - initialize the LPT for reading.1772 * @c: UBIFS file-system description object1773 *1774 * This function returns %0 on success and a negative error code on failure.1775 */1776static int lpt_init_rd(struct ubifs_info *c)1777{1778 int err, i;1779 1780 c->ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),1781 c->lpt_lebs));1782 if (!c->ltab)1783 return -ENOMEM;1784 1785 i = max_t(int, c->nnode_sz, c->pnode_sz);1786 c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);1787 if (!c->lpt_nod_buf)1788 return -ENOMEM;1789 1790 for (i = 0; i < LPROPS_HEAP_CNT; i++) {1791 c->lpt_heap[i].arr = kmalloc_array(LPT_HEAP_SZ,1792 sizeof(void *),1793 GFP_KERNEL);1794 if (!c->lpt_heap[i].arr)1795 return -ENOMEM;1796 c->lpt_heap[i].cnt = 0;1797 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;1798 }1799 1800 c->dirty_idx.arr = kmalloc_array(LPT_HEAP_SZ, sizeof(void *),1801 GFP_KERNEL);1802 if (!c->dirty_idx.arr)1803 return -ENOMEM;1804 c->dirty_idx.cnt = 0;1805 c->dirty_idx.max_cnt = LPT_HEAP_SZ;1806 1807 err = read_ltab(c);1808 if (err)1809 return err;1810 1811 err = lpt_check_hash(c);1812 if (err)1813 return err;1814 1815 dbg_lp("space_bits %d", c->space_bits);1816 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);1817 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);1818 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);1819 dbg_lp("pcnt_bits %d", c->pcnt_bits);1820 dbg_lp("lnum_bits %d", c->lnum_bits);1821 dbg_lp("pnode_sz %d", c->pnode_sz);1822 dbg_lp("nnode_sz %d", c->nnode_sz);1823 dbg_lp("ltab_sz %d", c->ltab_sz);1824 dbg_lp("lsave_sz %d", c->lsave_sz);1825 dbg_lp("lsave_cnt %d", c->lsave_cnt);1826 dbg_lp("lpt_hght %d", c->lpt_hght);1827 dbg_lp("big_lpt %u", c->big_lpt);1828 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);1829 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);1830 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);1831 if (c->big_lpt)1832 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);1833 1834 return 0;1835}1836 1837/**1838 * lpt_init_wr - initialize the LPT for writing.1839 * @c: UBIFS file-system description object1840 *1841 * 'lpt_init_rd()' must have been called already.1842 *1843 * This function returns %0 on success and a negative error code on failure.1844 */1845static int lpt_init_wr(struct ubifs_info *c)1846{1847 int err, i;1848 1849 c->ltab_cmt = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),1850 c->lpt_lebs));1851 if (!c->ltab_cmt)1852 return -ENOMEM;1853 1854 c->lpt_buf = vmalloc(c->leb_size);1855 if (!c->lpt_buf)1856 return -ENOMEM;1857 1858 if (c->big_lpt) {1859 c->lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_NOFS);1860 if (!c->lsave)1861 return -ENOMEM;1862 err = read_lsave(c);1863 if (err)1864 return err;1865 }1866 1867 for (i = 0; i < c->lpt_lebs; i++)1868 if (c->ltab[i].free == c->leb_size) {1869 err = ubifs_leb_unmap(c, i + c->lpt_first);1870 if (err)1871 return err;1872 }1873 1874 return 0;1875}1876 1877/**1878 * ubifs_lpt_init - initialize the LPT.1879 * @c: UBIFS file-system description object1880 * @rd: whether to initialize lpt for reading1881 * @wr: whether to initialize lpt for writing1882 *1883 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true1884 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is1885 * true.1886 *1887 * This function returns %0 on success and a negative error code on failure.1888 */1889int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)1890{1891 int err;1892 1893 if (rd) {1894 err = lpt_init_rd(c);1895 if (err)1896 goto out_err;1897 }1898 1899 if (wr) {1900 err = lpt_init_wr(c);1901 if (err)1902 goto out_err;1903 }1904 1905 return 0;1906 1907out_err:1908 if (wr)1909 ubifs_lpt_free(c, 1);1910 if (rd)1911 ubifs_lpt_free(c, 0);1912 return err;1913}1914 1915/**1916 * struct lpt_scan_node - somewhere to put nodes while we scan LPT.1917 * @nnode: where to keep a nnode1918 * @pnode: where to keep a pnode1919 * @cnode: where to keep a cnode1920 * @in_tree: is the node in the tree in memory1921 * @ptr: union of node pointers1922 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in1923 * the tree1924 * @ptr.pnode: ditto for pnode1925 * @ptr.cnode: ditto for cnode1926 */1927struct lpt_scan_node {1928 union {1929 struct ubifs_nnode nnode;1930 struct ubifs_pnode pnode;1931 struct ubifs_cnode cnode;1932 };1933 int in_tree;1934 union {1935 struct ubifs_nnode *nnode;1936 struct ubifs_pnode *pnode;1937 struct ubifs_cnode *cnode;1938 } ptr;1939};1940 1941/**1942 * scan_get_nnode - for the scan, get a nnode from either the tree or flash.1943 * @c: the UBIFS file-system description object1944 * @path: where to put the nnode1945 * @parent: parent of the nnode1946 * @iip: index in parent of the nnode1947 *1948 * This function returns a pointer to the nnode on success or a negative error1949 * code on failure.1950 */1951static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,1952 struct lpt_scan_node *path,1953 struct ubifs_nnode *parent, int iip)1954{1955 struct ubifs_nbranch *branch;1956 struct ubifs_nnode *nnode;1957 void *buf = c->lpt_nod_buf;1958 int err;1959 1960 branch = &parent->nbranch[iip];1961 nnode = branch->nnode;1962 if (nnode) {1963 path->in_tree = 1;1964 path->ptr.nnode = nnode;1965 return nnode;1966 }1967 nnode = &path->nnode;1968 path->in_tree = 0;1969 path->ptr.nnode = nnode;1970 memset(nnode, 0, sizeof(struct ubifs_nnode));1971 if (branch->lnum == 0) {1972 /*1973 * This nnode was not written which just means that the LEB1974 * properties in the subtree below it describe empty LEBs. We1975 * make the nnode as though we had read it, which in fact means1976 * doing almost nothing.1977 */1978 if (c->big_lpt)1979 nnode->num = calc_nnode_num_from_parent(c, parent, iip);1980 } else {1981 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,1982 c->nnode_sz, 1);1983 if (err)1984 return ERR_PTR(err);1985 err = ubifs_unpack_nnode(c, buf, nnode);1986 if (err)1987 return ERR_PTR(err);1988 }1989 err = validate_nnode(c, nnode, parent, iip);1990 if (err)1991 return ERR_PTR(err);1992 if (!c->big_lpt)1993 nnode->num = calc_nnode_num_from_parent(c, parent, iip);1994 nnode->level = parent->level - 1;1995 nnode->parent = parent;1996 nnode->iip = iip;1997 return nnode;1998}1999 2000/**2001 * scan_get_pnode - for the scan, get a pnode from either the tree or flash.2002 * @c: the UBIFS file-system description object2003 * @path: where to put the pnode2004 * @parent: parent of the pnode2005 * @iip: index in parent of the pnode2006 *2007 * This function returns a pointer to the pnode on success or a negative error2008 * code on failure.2009 */2010static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,2011 struct lpt_scan_node *path,2012 struct ubifs_nnode *parent, int iip)2013{2014 struct ubifs_nbranch *branch;2015 struct ubifs_pnode *pnode;2016 void *buf = c->lpt_nod_buf;2017 int err;2018 2019 branch = &parent->nbranch[iip];2020 pnode = branch->pnode;2021 if (pnode) {2022 path->in_tree = 1;2023 path->ptr.pnode = pnode;2024 return pnode;2025 }2026 pnode = &path->pnode;2027 path->in_tree = 0;2028 path->ptr.pnode = pnode;2029 memset(pnode, 0, sizeof(struct ubifs_pnode));2030 if (branch->lnum == 0) {2031 /*2032 * This pnode was not written which just means that the LEB2033 * properties in it describe empty LEBs. We make the pnode as2034 * though we had read it.2035 */2036 int i;2037 2038 if (c->big_lpt)2039 pnode->num = calc_pnode_num_from_parent(c, parent, iip);2040 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {2041 struct ubifs_lprops * const lprops = &pnode->lprops[i];2042 2043 lprops->free = c->leb_size;2044 lprops->flags = ubifs_categorize_lprops(c, lprops);2045 }2046 } else {2047 ubifs_assert(c, branch->lnum >= c->lpt_first &&2048 branch->lnum <= c->lpt_last);2049 ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size);2050 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,2051 c->pnode_sz, 1);2052 if (err)2053 return ERR_PTR(err);2054 err = unpack_pnode(c, buf, pnode);2055 if (err)2056 return ERR_PTR(err);2057 }2058 err = validate_pnode(c, pnode, parent, iip);2059 if (err)2060 return ERR_PTR(err);2061 if (!c->big_lpt)2062 pnode->num = calc_pnode_num_from_parent(c, parent, iip);2063 pnode->parent = parent;2064 pnode->iip = iip;2065 set_pnode_lnum(c, pnode);2066 return pnode;2067}2068 2069/**2070 * ubifs_lpt_scan_nolock - scan the LPT.2071 * @c: the UBIFS file-system description object2072 * @start_lnum: LEB number from which to start scanning2073 * @end_lnum: LEB number at which to stop scanning2074 * @scan_cb: callback function called for each lprops2075 * @data: data to be passed to the callback function2076 *2077 * This function returns %0 on success and a negative error code on failure.2078 */2079int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,2080 ubifs_lpt_scan_callback scan_cb, void *data)2081{2082 int err = 0, i, h, iip, shft;2083 struct ubifs_nnode *nnode;2084 struct ubifs_pnode *pnode;2085 struct lpt_scan_node *path;2086 2087 if (start_lnum == -1) {2088 start_lnum = end_lnum + 1;2089 if (start_lnum >= c->leb_cnt)2090 start_lnum = c->main_first;2091 }2092 2093 ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt);2094 ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt);2095 2096 if (!c->nroot) {2097 err = ubifs_read_nnode(c, NULL, 0);2098 if (err)2099 return err;2100 }2101 2102 path = kmalloc_array(c->lpt_hght + 1, sizeof(struct lpt_scan_node),2103 GFP_NOFS);2104 if (!path)2105 return -ENOMEM;2106 2107 path[0].ptr.nnode = c->nroot;2108 path[0].in_tree = 1;2109again:2110 /* Descend to the pnode containing start_lnum */2111 nnode = c->nroot;2112 i = start_lnum - c->main_first;2113 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;2114 for (h = 1; h < c->lpt_hght; h++) {2115 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));2116 shft -= UBIFS_LPT_FANOUT_SHIFT;2117 nnode = scan_get_nnode(c, path + h, nnode, iip);2118 if (IS_ERR(nnode)) {2119 err = PTR_ERR(nnode);2120 goto out;2121 }2122 }2123 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));2124 pnode = scan_get_pnode(c, path + h, nnode, iip);2125 if (IS_ERR(pnode)) {2126 err = PTR_ERR(pnode);2127 goto out;2128 }2129 iip = (i & (UBIFS_LPT_FANOUT - 1));2130 2131 /* Loop for each lprops */2132 while (1) {2133 struct ubifs_lprops *lprops = &pnode->lprops[iip];2134 int ret, lnum = lprops->lnum;2135 2136 ret = scan_cb(c, lprops, path[h].in_tree, data);2137 if (ret < 0) {2138 err = ret;2139 goto out;2140 }2141 if (ret & LPT_SCAN_ADD) {2142 /* Add all the nodes in path to the tree in memory */2143 for (h = 1; h < c->lpt_hght; h++) {2144 const size_t sz = sizeof(struct ubifs_nnode);2145 struct ubifs_nnode *parent;2146 2147 if (path[h].in_tree)2148 continue;2149 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS);2150 if (!nnode) {2151 err = -ENOMEM;2152 goto out;2153 }2154 parent = nnode->parent;2155 parent->nbranch[nnode->iip].nnode = nnode;2156 path[h].ptr.nnode = nnode;2157 path[h].in_tree = 1;2158 path[h + 1].cnode.parent = nnode;2159 }2160 if (path[h].in_tree)2161 ubifs_ensure_cat(c, lprops);2162 else {2163 const size_t sz = sizeof(struct ubifs_pnode);2164 struct ubifs_nnode *parent;2165 2166 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS);2167 if (!pnode) {2168 err = -ENOMEM;2169 goto out;2170 }2171 parent = pnode->parent;2172 parent->nbranch[pnode->iip].pnode = pnode;2173 path[h].ptr.pnode = pnode;2174 path[h].in_tree = 1;2175 update_cats(c, pnode);2176 c->pnodes_have += 1;2177 }2178 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)2179 c->nroot, 0, 0);2180 if (err)2181 goto out;2182 err = dbg_check_cats(c);2183 if (err)2184 goto out;2185 }2186 if (ret & LPT_SCAN_STOP) {2187 err = 0;2188 break;2189 }2190 /* Get the next lprops */2191 if (lnum == end_lnum) {2192 /*2193 * We got to the end without finding what we were2194 * looking for2195 */2196 err = -ENOSPC;2197 goto out;2198 }2199 if (lnum + 1 >= c->leb_cnt) {2200 /* Wrap-around to the beginning */2201 start_lnum = c->main_first;2202 goto again;2203 }2204 if (iip + 1 < UBIFS_LPT_FANOUT) {2205 /* Next lprops is in the same pnode */2206 iip += 1;2207 continue;2208 }2209 /* We need to get the next pnode. Go up until we can go right */2210 iip = pnode->iip;2211 while (1) {2212 h -= 1;2213 ubifs_assert(c, h >= 0);2214 nnode = path[h].ptr.nnode;2215 if (iip + 1 < UBIFS_LPT_FANOUT)2216 break;2217 iip = nnode->iip;2218 }2219 /* Go right */2220 iip += 1;2221 /* Descend to the pnode */2222 h += 1;2223 for (; h < c->lpt_hght; h++) {2224 nnode = scan_get_nnode(c, path + h, nnode, iip);2225 if (IS_ERR(nnode)) {2226 err = PTR_ERR(nnode);2227 goto out;2228 }2229 iip = 0;2230 }2231 pnode = scan_get_pnode(c, path + h, nnode, iip);2232 if (IS_ERR(pnode)) {2233 err = PTR_ERR(pnode);2234 goto out;2235 }2236 iip = 0;2237 }2238out:2239 kfree(path);2240 return err;2241}2242 2243/**2244 * dbg_chk_pnode - check a pnode.2245 * @c: the UBIFS file-system description object2246 * @pnode: pnode to check2247 * @col: pnode column2248 *2249 * This function returns %0 on success and a negative error code on failure.2250 */2251static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,2252 int col)2253{2254 int i;2255 2256 if (pnode->num != col) {2257 ubifs_err(c, "pnode num %d expected %d parent num %d iip %d",2258 pnode->num, col, pnode->parent->num, pnode->iip);2259 return -EINVAL;2260 }2261 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {2262 struct ubifs_lprops *lp, *lprops = &pnode->lprops[i];2263 int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i +2264 c->main_first;2265 int found, cat = lprops->flags & LPROPS_CAT_MASK;2266 struct ubifs_lpt_heap *heap;2267 struct list_head *list = NULL;2268 2269 if (lnum >= c->leb_cnt)2270 continue;2271 if (lprops->lnum != lnum) {2272 ubifs_err(c, "bad LEB number %d expected %d",2273 lprops->lnum, lnum);2274 return -EINVAL;2275 }2276 if (lprops->flags & LPROPS_TAKEN) {2277 if (cat != LPROPS_UNCAT) {2278 ubifs_err(c, "LEB %d taken but not uncat %d",2279 lprops->lnum, cat);2280 return -EINVAL;2281 }2282 continue;2283 }2284 if (lprops->flags & LPROPS_INDEX) {2285 switch (cat) {2286 case LPROPS_UNCAT:2287 case LPROPS_DIRTY_IDX:2288 case LPROPS_FRDI_IDX:2289 break;2290 default:2291 ubifs_err(c, "LEB %d index but cat %d",2292 lprops->lnum, cat);2293 return -EINVAL;2294 }2295 } else {2296 switch (cat) {2297 case LPROPS_UNCAT:2298 case LPROPS_DIRTY:2299 case LPROPS_FREE:2300 case LPROPS_EMPTY:2301 case LPROPS_FREEABLE:2302 break;2303 default:2304 ubifs_err(c, "LEB %d not index but cat %d",2305 lprops->lnum, cat);2306 return -EINVAL;2307 }2308 }2309 switch (cat) {2310 case LPROPS_UNCAT:2311 list = &c->uncat_list;2312 break;2313 case LPROPS_EMPTY:2314 list = &c->empty_list;2315 break;2316 case LPROPS_FREEABLE:2317 list = &c->freeable_list;2318 break;2319 case LPROPS_FRDI_IDX:2320 list = &c->frdi_idx_list;2321 break;2322 }2323 found = 0;2324 switch (cat) {2325 case LPROPS_DIRTY:2326 case LPROPS_DIRTY_IDX:2327 case LPROPS_FREE:2328 heap = &c->lpt_heap[cat - 1];2329 if (lprops->hpos < heap->cnt &&2330 heap->arr[lprops->hpos] == lprops)2331 found = 1;2332 break;2333 case LPROPS_UNCAT:2334 case LPROPS_EMPTY:2335 case LPROPS_FREEABLE:2336 case LPROPS_FRDI_IDX:2337 list_for_each_entry(lp, list, list)2338 if (lprops == lp) {2339 found = 1;2340 break;2341 }2342 break;2343 }2344 if (!found) {2345 ubifs_err(c, "LEB %d cat %d not found in cat heap/list",2346 lprops->lnum, cat);2347 return -EINVAL;2348 }2349 switch (cat) {2350 case LPROPS_EMPTY:2351 if (lprops->free != c->leb_size) {2352 ubifs_err(c, "LEB %d cat %d free %d dirty %d",2353 lprops->lnum, cat, lprops->free,2354 lprops->dirty);2355 return -EINVAL;2356 }2357 break;2358 case LPROPS_FREEABLE:2359 case LPROPS_FRDI_IDX:2360 if (lprops->free + lprops->dirty != c->leb_size) {2361 ubifs_err(c, "LEB %d cat %d free %d dirty %d",2362 lprops->lnum, cat, lprops->free,2363 lprops->dirty);2364 return -EINVAL;2365 }2366 break;2367 }2368 }2369 return 0;2370}2371 2372/**2373 * dbg_check_lpt_nodes - check nnodes and pnodes.2374 * @c: the UBIFS file-system description object2375 * @cnode: next cnode (nnode or pnode) to check2376 * @row: row of cnode (root is zero)2377 * @col: column of cnode (leftmost is zero)2378 *2379 * This function returns %0 on success and a negative error code on failure.2380 */2381int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,2382 int row, int col)2383{2384 struct ubifs_nnode *nnode, *nn;2385 struct ubifs_cnode *cn;2386 int num, iip = 0, err;2387 2388 if (!dbg_is_chk_lprops(c))2389 return 0;2390 2391 while (cnode) {2392 ubifs_assert(c, row >= 0);2393 nnode = cnode->parent;2394 if (cnode->level) {2395 /* cnode is a nnode */2396 num = calc_nnode_num(row, col);2397 if (cnode->num != num) {2398 ubifs_err(c, "nnode num %d expected %d parent num %d iip %d",2399 cnode->num, num,2400 (nnode ? nnode->num : 0), cnode->iip);2401 return -EINVAL;2402 }2403 nn = (struct ubifs_nnode *)cnode;2404 while (iip < UBIFS_LPT_FANOUT) {2405 cn = nn->nbranch[iip].cnode;2406 if (cn) {2407 /* Go down */2408 row += 1;2409 col <<= UBIFS_LPT_FANOUT_SHIFT;2410 col += iip;2411 iip = 0;2412 cnode = cn;2413 break;2414 }2415 /* Go right */2416 iip += 1;2417 }2418 if (iip < UBIFS_LPT_FANOUT)2419 continue;2420 } else {2421 struct ubifs_pnode *pnode;2422 2423 /* cnode is a pnode */2424 pnode = (struct ubifs_pnode *)cnode;2425 err = dbg_chk_pnode(c, pnode, col);2426 if (err)2427 return err;2428 }2429 /* Go up and to the right */2430 row -= 1;2431 col >>= UBIFS_LPT_FANOUT_SHIFT;2432 iip = cnode->iip + 1;2433 cnode = (struct ubifs_cnode *)nnode;2434 }2435 return 0;2436}2437