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