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