1// SPDX-License-Identifier: GPL-2.0-only 2/* 3 * This file is part of UBIFS. 4 * 5 * Copyright (C) 2006-2008 Nokia Corporation. 6 * 7 * Authors: Adrian Hunter 8 * Artem Bityutskiy (���������������� ����������) 9 */ 10 11/* 12 * This file implements the LEB properties tree (LPT) area. The LPT area 13 * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and 14 * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits 15 * between the log and the orphan area. 16 * 17 * The LPT area is like a miniature self-contained file system. It is required 18 * that it never runs out of space, is fast to access and update, and scales 19 * logarithmically. The LEB properties tree is implemented as a wandering tree 20 * 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 the 23 * "big model". The small model is used when the entire LEB properties table 24 * can be written into a single eraseblock. In that case, garbage collection 25 * consists of just writing the whole table, which therefore makes all other 26 * eraseblocks reusable. In the case of the big model, dirty eraseblocks are 27 * selected for garbage collection, which consists of marking the clean nodes in 28 * that LEB as dirty, and then only the dirty nodes are written out. Also, in 29 * the case of the big model, a table of LEB numbers is saved so that the entire 30 * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first 31 * 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 object 42 * 43 * Calculate the sizes of LPT bit fields, nodes, and tree, based on the 44 * 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 object 122 * 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 object 153 * @main_lebs: number of main area LEBs is passed and returned here 154 * @big_lpt: whether the LPT area is "big" is returned here 155 * 156 * The size of the LPT area depends on parameters that themselves are dependent 157 * on the size of the LPT area. This function, successively recalculates the LPT 158 * 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 it 179 * makes sense 180 */ 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 object 217 * @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 pack 220 * @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 object 267 * @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 object 337 * @buf: buffer into which to pack 338 * @pnode: pnode to pack 339 */ 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 else 358 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 object 370 * @buf: buffer into which to pack 371 * @nnode: nnode to pack 372 */ 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 object 402 * @buf: buffer into which to pack 403 * @ltab: LPT's own lprops table to pack 404 */ 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 object 427 * @buf: buffer into which to pack 428 * @lsave: LPT's save table to pack 429 */ 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 object 449 * @lnum: LEB number to which to add dirty space 450 * @dirty: amount of dirty space to add 451 */ 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 object 465 * @lnum: LEB number 466 * @free: amount of free space 467 * @dirty: amount of dirty space 468 */ 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 object 482 * @nnode: nnode for which to add dirt 483 */ 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 object 503 * @pnode: pnode for which to add dirt 504 */ 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 used 517 * 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 @row 520 * 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 object 539 * @parent: parent nnode 540 * @iip: index in parent 541 * 542 * The nnode number is a number that uniquely identifies a nnode and can be used 543 * 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's 546 * 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 object 564 * @parent: parent nnode 565 * @iip: index in parent 566 * 567 * The pnode number is a number that uniquely identifies a pnode and can be used 568 * 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's 571 * 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 object 591 * @main_lebs: number of main area LEBs is passed and returned here 592 * @lpt_first: LEB number of first LPT LEB 593 * @lpt_lebs: number of LEBs for LPT is passed and returned here 594 * @big_lpt: use big LPT model is passed and returned here 595 * @hash: hash of the LPT is returned here 596 * 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 contain 656 * 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 about 692 * 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 traverse 721 * 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 object 874 * @pnode: pnode 875 * 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 object 896 * @old_pnode: pnode copied 897 * @new_pnode: pnode copy 898 * 899 * During commit it is sometimes necessary to copy a pnode 900 * (see dirty_cow_pnode). When that happens, references in 901 * 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 object 919 * @buf: buffer containing node 920 * @len: length of node 921 * 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 object 945 * @addr: address of type bit field is passed and returned updated here 946 * @pos: position of type bit field is passed and returned updated here 947 * @type: expected type 948 * 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 object 969 * @buf: buffer containing packed pnode to unpack 970 * @pnode: pnode structure to fill 971 * 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 else 996 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 object 1006 * @buf: buffer containing packed nnode to unpack 1007 * @nnode: nnode structure to fill 1008 * 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 object 1040 * @buf: buffer from which to unpack 1041 * 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 object 1072 * @buf: buffer from which to unpack 1073 * 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 object 1098 * @nnode: nnode to validate 1099 * @parent: parent nnode (or NULL for the root nnode) 1100 * @iip: index in parent 1101 * 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 else 1121 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 object 1142 * @pnode: pnode to validate 1143 * @parent: parent nnode 1144 * @iip: index in parent 1145 * 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 object 1177 * @pnode: pnode to update 1178 * 1179 * This function calculates the LEB numbers for the LEB properties it contains 1180 * 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 object 1198 * @parent: parent nnode (or NULL for the root) 1199 * @iip: index in parent 1200 * 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 LEB 1226 * properties in the subtree below it describe empty LEBs. We 1227 * make the nnode as though we had read it, which in fact means 1228 * 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 object 1266 * @parent: parent nnode 1267 * @iip: index in parent 1268 * 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 LEB 1288 * properties in it describe empty LEBs. We make the pnode as 1289 * 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 object 1333 * 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 object 1356 * 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 table 1380 * 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 object 1398 * @parent: parent nnode (or NULL for the root) 1399 * @iip: index in parent 1400 * 1401 * This function returns a pointer to the nnode on success or a negative error 1402 * 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 object 1424 * @parent: parent nnode 1425 * @iip: index in parent 1426 * 1427 * This function returns a pointer to the pnode on success or a negative error 1428 * 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 object 1451 * @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 negative 1454 * 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 object 1483 * @lnum: LEB number to lookup 1484 * 1485 * This function returns a pointer to the LEB properties on success or a 1486 * 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 object 1507 * @nnode: nnode to check 1508 * 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 else 1551 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 object 1558 * @pnode: pnode to check 1559 * 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 object 1598 * @lnum: LEB number to lookup 1599 * 1600 * This function returns a pointer to the LEB properties on success or a 1601 * 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 pnodes 1647 * @c: UBIFS file-system description object 1648 * @hash: the returned hash of the LPT pnodes 1649 * 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 object 1743 * 1744 * This function calculates a hash over all pnodes in the LPT and compares it with 1745 * the hash stored in the master node. Returns %0 on success and a negative error 1746 * 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 object 1773 * 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 object 1840 * 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 object 1880 * @rd: whether to initialize lpt for reading 1881 * @wr: whether to initialize lpt for writing 1882 * 1883 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true 1884 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is 1885 * 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 nnode 1918 * @pnode: where to keep a pnode 1919 * @cnode: where to keep a cnode 1920 * @in_tree: is the node in the tree in memory 1921 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in 1922 * the tree 1923 * @ptr.pnode: ditto for pnode 1924 * @ptr.cnode: ditto for cnode 1925 */ 1926struct lpt_scan_node { 1927 union { 1928 struct ubifs_nnode nnode; 1929 struct ubifs_pnode pnode; 1930 struct ubifs_cnode cnode; 1931 }; 1932 int in_tree; 1933 union { 1934 struct ubifs_nnode *nnode; 1935 struct ubifs_pnode *pnode; 1936 struct ubifs_cnode *cnode; 1937 } ptr; 1938}; 1939 1940/** 1941 * scan_get_nnode - for the scan, get a nnode from either the tree or flash. 1942 * @c: the UBIFS file-system description object 1943 * @path: where to put the nnode 1944 * @parent: parent of the nnode 1945 * @iip: index in parent of the nnode 1946 * 1947 * This function returns a pointer to the nnode on success or a negative error 1948 * code on failure. 1949 */ 1950static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c, 1951 struct lpt_scan_node *path, 1952 struct ubifs_nnode *parent, int iip) 1953{ 1954 struct ubifs_nbranch *branch; 1955 struct ubifs_nnode *nnode; 1956 void *buf = c->lpt_nod_buf; 1957 int err; 1958 1959 branch = &parent->nbranch[iip]; 1960 nnode = branch->nnode; 1961 if (nnode) { 1962 path->in_tree = 1; 1963 path->ptr.nnode = nnode; 1964 return nnode; 1965 } 1966 nnode = &path->nnode; 1967 path->in_tree = 0; 1968 path->ptr.nnode = nnode; 1969 memset(nnode, 0, sizeof(struct ubifs_nnode)); 1970 if (branch->lnum == 0) { 1971 /* 1972 * This nnode was not written which just means that the LEB 1973 * properties in the subtree below it describe empty LEBs. We 1974 * make the nnode as though we had read it, which in fact means 1975 * doing almost nothing. 1976 */ 1977 if (c->big_lpt) 1978 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1979 } else { 1980 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs, 1981 c->nnode_sz, 1); 1982 if (err) 1983 return ERR_PTR(err); 1984 err = ubifs_unpack_nnode(c, buf, nnode); 1985 if (err) 1986 return ERR_PTR(err); 1987 } 1988 err = validate_nnode(c, nnode, parent, iip); 1989 if (err) 1990 return ERR_PTR(err); 1991 if (!c->big_lpt) 1992 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1993 nnode->level = parent->level - 1; 1994 nnode->parent = parent; 1995 nnode->iip = iip; 1996 return nnode; 1997} 1998 1999/** 2000 * scan_get_pnode - for the scan, get a pnode from either the tree or flash. 2001 * @c: the UBIFS file-system description object 2002 * @path: where to put the pnode 2003 * @parent: parent of the pnode 2004 * @iip: index in parent of the pnode 2005 * 2006 * This function returns a pointer to the pnode on success or a negative error 2007 * code on failure. 2008 */ 2009static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c, 2010 struct lpt_scan_node *path, 2011 struct ubifs_nnode *parent, int iip) 2012{ 2013 struct ubifs_nbranch *branch; 2014 struct ubifs_pnode *pnode; 2015 void *buf = c->lpt_nod_buf; 2016 int err; 2017 2018 branch = &parent->nbranch[iip]; 2019 pnode = branch->pnode; 2020 if (pnode) { 2021 path->in_tree = 1; 2022 path->ptr.pnode = pnode; 2023 return pnode; 2024 } 2025 pnode = &path->pnode; 2026 path->in_tree = 0; 2027 path->ptr.pnode = pnode; 2028 memset(pnode, 0, sizeof(struct ubifs_pnode)); 2029 if (branch->lnum == 0) { 2030 /* 2031 * This pnode was not written which just means that the LEB 2032 * properties in it describe empty LEBs. We make the pnode as 2033 * though we had read it. 2034 */ 2035 int i; 2036 2037 if (c->big_lpt) 2038 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 2039 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 2040 struct ubifs_lprops * const lprops = &pnode->lprops[i]; 2041 2042 lprops->free = c->leb_size; 2043 lprops->flags = ubifs_categorize_lprops(c, lprops); 2044 } 2045 } else { 2046 ubifs_assert(c, branch->lnum >= c->lpt_first && 2047 branch->lnum <= c->lpt_last); 2048 ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size); 2049 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs, 2050 c->pnode_sz, 1); 2051 if (err) 2052 return ERR_PTR(err); 2053 err = unpack_pnode(c, buf, pnode); 2054 if (err) 2055 return ERR_PTR(err); 2056 } 2057 err = validate_pnode(c, pnode, parent, iip); 2058 if (err) 2059 return ERR_PTR(err); 2060 if (!c->big_lpt) 2061 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 2062 pnode->parent = parent; 2063 pnode->iip = iip; 2064 set_pnode_lnum(c, pnode); 2065 return pnode; 2066} 2067 2068/** 2069 * ubifs_lpt_scan_nolock - scan the LPT. 2070 * @c: the UBIFS file-system description object 2071 * @start_lnum: LEB number from which to start scanning 2072 * @end_lnum: LEB number at which to stop scanning 2073 * @scan_cb: callback function called for each lprops 2074 * @data: data to be passed to the callback function 2075 * 2076 * This function returns %0 on success and a negative error code on failure. 2077 */ 2078int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum, 2079 ubifs_lpt_scan_callback scan_cb, void *data) 2080{ 2081 int err = 0, i, h, iip, shft; 2082 struct ubifs_nnode *nnode; 2083 struct ubifs_pnode *pnode; 2084 struct lpt_scan_node *path; 2085 2086 if (start_lnum == -1) { 2087 start_lnum = end_lnum + 1; 2088 if (start_lnum >= c->leb_cnt) 2089 start_lnum = c->main_first; 2090 } 2091 2092 ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt); 2093 ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt); 2094 2095 if (!c->nroot) { 2096 err = ubifs_read_nnode(c, NULL, 0); 2097 if (err) 2098 return err; 2099 } 2100 2101 path = kmalloc_array(c->lpt_hght + 1, sizeof(struct lpt_scan_node), 2102 GFP_NOFS); 2103 if (!path) 2104 return -ENOMEM; 2105 2106 path[0].ptr.nnode = c->nroot; 2107 path[0].in_tree = 1; 2108again: 2109 /* Descend to the pnode containing start_lnum */ 2110 nnode = c->nroot; 2111 i = start_lnum - c->main_first; 2112 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; 2113 for (h = 1; h < c->lpt_hght; h++) { 2114 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 2115 shft -= UBIFS_LPT_FANOUT_SHIFT; 2116 nnode = scan_get_nnode(c, path + h, nnode, iip); 2117 if (IS_ERR(nnode)) { 2118 err = PTR_ERR(nnode); 2119 goto out; 2120 } 2121 } 2122 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 2123 pnode = scan_get_pnode(c, path + h, nnode, iip); 2124 if (IS_ERR(pnode)) { 2125 err = PTR_ERR(pnode); 2126 goto out; 2127 } 2128 iip = (i & (UBIFS_LPT_FANOUT - 1)); 2129 2130 /* Loop for each lprops */ 2131 while (1) { 2132 struct ubifs_lprops *lprops = &pnode->lprops[iip]; 2133 int ret, lnum = lprops->lnum; 2134 2135 ret = scan_cb(c, lprops, path[h].in_tree, data); 2136 if (ret < 0) { 2137 err = ret; 2138 goto out; 2139 } 2140 if (ret & LPT_SCAN_ADD) { 2141 /* Add all the nodes in path to the tree in memory */ 2142 for (h = 1; h < c->lpt_hght; h++) { 2143 const size_t sz = sizeof(struct ubifs_nnode); 2144 struct ubifs_nnode *parent; 2145 2146 if (path[h].in_tree) 2147 continue; 2148 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS); 2149 if (!nnode) { 2150 err = -ENOMEM; 2151 goto out; 2152 } 2153 parent = nnode->parent; 2154 parent->nbranch[nnode->iip].nnode = nnode; 2155 path[h].ptr.nnode = nnode; 2156 path[h].in_tree = 1; 2157 path[h + 1].cnode.parent = nnode; 2158 } 2159 if (path[h].in_tree) 2160 ubifs_ensure_cat(c, lprops); 2161 else { 2162 const size_t sz = sizeof(struct ubifs_pnode); 2163 struct ubifs_nnode *parent; 2164 2165 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS); 2166 if (!pnode) { 2167 err = -ENOMEM; 2168 goto out; 2169 } 2170 parent = pnode->parent; 2171 parent->nbranch[pnode->iip].pnode = pnode; 2172 path[h].ptr.pnode = pnode; 2173 path[h].in_tree = 1; 2174 update_cats(c, pnode); 2175 c->pnodes_have += 1; 2176 } 2177 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *) 2178 c->nroot, 0, 0); 2179 if (err) 2180 goto out; 2181 err = dbg_check_cats(c); 2182 if (err) 2183 goto out; 2184 } 2185 if (ret & LPT_SCAN_STOP) { 2186 err = 0; 2187 break; 2188 } 2189 /* Get the next lprops */ 2190 if (lnum == end_lnum) { 2191 /* 2192 * We got to the end without finding what we were 2193 * looking for 2194 */ 2195 err = -ENOSPC; 2196 goto out; 2197 } 2198 if (lnum + 1 >= c->leb_cnt) { 2199 /* Wrap-around to the beginning */ 2200 start_lnum = c->main_first; 2201 goto again; 2202 } 2203 if (iip + 1 < UBIFS_LPT_FANOUT) { 2204 /* Next lprops is in the same pnode */ 2205 iip += 1; 2206 continue; 2207 } 2208 /* We need to get the next pnode. Go up until we can go right */ 2209 iip = pnode->iip; 2210 while (1) { 2211 h -= 1; 2212 ubifs_assert(c, h >= 0); 2213 nnode = path[h].ptr.nnode; 2214 if (iip + 1 < UBIFS_LPT_FANOUT) 2215 break; 2216 iip = nnode->iip; 2217 } 2218 /* Go right */ 2219 iip += 1; 2220 /* Descend to the pnode */ 2221 h += 1; 2222 for (; h < c->lpt_hght; h++) { 2223 nnode = scan_get_nnode(c, path + h, nnode, iip); 2224 if (IS_ERR(nnode)) { 2225 err = PTR_ERR(nnode); 2226 goto out; 2227 } 2228 iip = 0; 2229 } 2230 pnode = scan_get_pnode(c, path + h, nnode, iip); 2231 if (IS_ERR(pnode)) { 2232 err = PTR_ERR(pnode); 2233 goto out; 2234 } 2235 iip = 0; 2236 } 2237out: 2238 kfree(path); 2239 return err; 2240} 2241 2242/** 2243 * dbg_chk_pnode - check a pnode. 2244 * @c: the UBIFS file-system description object 2245 * @pnode: pnode to check 2246 * @col: pnode column 2247 * 2248 * This function returns %0 on success and a negative error code on failure. 2249 */ 2250static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode, 2251 int col) 2252{ 2253 int i; 2254 2255 if (pnode->num != col) { 2256 ubifs_err(c, "pnode num %d expected %d parent num %d iip %d", 2257 pnode->num, col, pnode->parent->num, pnode->iip); 2258 return -EINVAL; 2259 } 2260 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 2261 struct ubifs_lprops *lp, *lprops = &pnode->lprops[i]; 2262 int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i + 2263 c->main_first; 2264 int found, cat = lprops->flags & LPROPS_CAT_MASK; 2265 struct ubifs_lpt_heap *heap; 2266 struct list_head *list = NULL; 2267 2268 if (lnum >= c->leb_cnt) 2269 continue; 2270 if (lprops->lnum != lnum) { 2271 ubifs_err(c, "bad LEB number %d expected %d", 2272 lprops->lnum, lnum); 2273 return -EINVAL; 2274 } 2275 if (lprops->flags & LPROPS_TAKEN) { 2276 if (cat != LPROPS_UNCAT) { 2277 ubifs_err(c, "LEB %d taken but not uncat %d", 2278 lprops->lnum, cat); 2279 return -EINVAL; 2280 } 2281 continue; 2282 } 2283 if (lprops->flags & LPROPS_INDEX) { 2284 switch (cat) { 2285 case LPROPS_UNCAT: 2286 case LPROPS_DIRTY_IDX: 2287 case LPROPS_FRDI_IDX: 2288 break; 2289 default: 2290 ubifs_err(c, "LEB %d index but cat %d", 2291 lprops->lnum, cat); 2292 return -EINVAL; 2293 } 2294 } else { 2295 switch (cat) { 2296 case LPROPS_UNCAT: 2297 case LPROPS_DIRTY: 2298 case LPROPS_FREE: 2299 case LPROPS_EMPTY: 2300 case LPROPS_FREEABLE: 2301 break; 2302 default: 2303 ubifs_err(c, "LEB %d not index but cat %d", 2304 lprops->lnum, cat); 2305 return -EINVAL; 2306 } 2307 } 2308 switch (cat) { 2309 case LPROPS_UNCAT: 2310 list = &c->uncat_list; 2311 break; 2312 case LPROPS_EMPTY: 2313 list = &c->empty_list; 2314 break; 2315 case LPROPS_FREEABLE: 2316 list = &c->freeable_list; 2317 break; 2318 case LPROPS_FRDI_IDX: 2319 list = &c->frdi_idx_list; 2320 break; 2321 } 2322 found = 0; 2323 switch (cat) { 2324 case LPROPS_DIRTY: 2325 case LPROPS_DIRTY_IDX: 2326 case LPROPS_FREE: 2327 heap = &c->lpt_heap[cat - 1]; 2328 if (lprops->hpos < heap->cnt && 2329 heap->arr[lprops->hpos] == lprops) 2330 found = 1; 2331 break; 2332 case LPROPS_UNCAT: 2333 case LPROPS_EMPTY: 2334 case LPROPS_FREEABLE: 2335 case LPROPS_FRDI_IDX: 2336 list_for_each_entry(lp, list, list) 2337 if (lprops == lp) { 2338 found = 1; 2339 break; 2340 } 2341 break; 2342 } 2343 if (!found) { 2344 ubifs_err(c, "LEB %d cat %d not found in cat heap/list", 2345 lprops->lnum, cat); 2346 return -EINVAL; 2347 } 2348 switch (cat) { 2349 case LPROPS_EMPTY: 2350 if (lprops->free != c->leb_size) { 2351 ubifs_err(c, "LEB %d cat %d free %d dirty %d", 2352 lprops->lnum, cat, lprops->free, 2353 lprops->dirty); 2354 return -EINVAL; 2355 } 2356 break; 2357 case LPROPS_FREEABLE: 2358 case LPROPS_FRDI_IDX: 2359 if (lprops->free + lprops->dirty != c->leb_size) { 2360 ubifs_err(c, "LEB %d cat %d free %d dirty %d", 2361 lprops->lnum, cat, lprops->free, 2362 lprops->dirty); 2363 return -EINVAL; 2364 } 2365 break; 2366 } 2367 } 2368 return 0; 2369} 2370 2371/** 2372 * dbg_check_lpt_nodes - check nnodes and pnodes. 2373 * @c: the UBIFS file-system description object 2374 * @cnode: next cnode (nnode or pnode) to check 2375 * @row: row of cnode (root is zero) 2376 * @col: column of cnode (leftmost is zero) 2377 * 2378 * This function returns %0 on success and a negative error code on failure. 2379 */ 2380int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode, 2381 int row, int col) 2382{ 2383 struct ubifs_nnode *nnode, *nn; 2384 struct ubifs_cnode *cn; 2385 int num, iip = 0, err; 2386 2387 if (!dbg_is_chk_lprops(c)) 2388 return 0; 2389 2390 while (cnode) { 2391 ubifs_assert(c, row >= 0); 2392 nnode = cnode->parent; 2393 if (cnode->level) { 2394 /* cnode is a nnode */ 2395 num = calc_nnode_num(row, col); 2396 if (cnode->num != num) { 2397 ubifs_err(c, "nnode num %d expected %d parent num %d iip %d", 2398 cnode->num, num, 2399 (nnode ? nnode->num : 0), cnode->iip); 2400 return -EINVAL; 2401 } 2402 nn = (struct ubifs_nnode *)cnode; 2403 while (iip < UBIFS_LPT_FANOUT) { 2404 cn = nn->nbranch[iip].cnode; 2405 if (cn) { 2406 /* Go down */ 2407 row += 1; 2408 col <<= UBIFS_LPT_FANOUT_SHIFT; 2409 col += iip; 2410 iip = 0; 2411 cnode = cn; 2412 break; 2413 } 2414 /* Go right */ 2415 iip += 1; 2416 } 2417 if (iip < UBIFS_LPT_FANOUT) 2418 continue; 2419 } else { 2420 struct ubifs_pnode *pnode; 2421 2422 /* cnode is a pnode */ 2423 pnode = (struct ubifs_pnode *)cnode; 2424 err = dbg_chk_pnode(c, pnode, col); 2425 if (err) 2426 return err; 2427 } 2428 /* Go up and to the right */ 2429 row -= 1; 2430 col >>= UBIFS_LPT_FANOUT_SHIFT; 2431 iip = cnode->iip + 1; 2432 cnode = (struct ubifs_cnode *)nnode; 2433 } 2434 return 0; 2435} 2436