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