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 */ 58static 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 */ 137int 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(c, "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(c, "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 */ 174static 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(c, "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 */ 233static 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 */ 283uint32_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 */ 350void 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 */ 383void 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 */ 415void 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 */ 440void 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 */ 462void 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 */ 479static 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 */ 494void 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 */ 515static 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 */ 532static 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 */ 558static 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 */ 583static 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 */ 608int 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); 851out: 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 */ 869static 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 */ 893static 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 */ 914static int check_lpt_crc(const struct ubifs_info *c, 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(c, "invalid crc in LPT node: crc %hx calc %hx", 925 crc, 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 */ 941static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr, 942 int *pos, int type) 943{ 944 int node_type; 945 946 node_type = ubifs_unpack_bits(addr, pos, UBIFS_LPT_TYPE_BITS); 947 if (node_type != type) { 948 ubifs_err(c, "invalid type (%d) in LPT node type %d", 949 node_type, type); 950 dump_stack(); 951 return -EINVAL; 952 } 953 return 0; 954} 955 956/** 957 * unpack_pnode - unpack a pnode. 958 * @c: UBIFS file-system description object 959 * @buf: buffer containing packed pnode to unpack 960 * @pnode: pnode structure to fill 961 * 962 * This function returns %0 on success and a negative error code on failure. 963 */ 964static int unpack_pnode(const struct ubifs_info *c, void *buf, 965 struct ubifs_pnode *pnode) 966{ 967 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; 968 int i, pos = 0, err; 969 970 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE); 971 if (err) 972 return err; 973 if (c->big_lpt) 974 pnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits); 975 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 976 struct ubifs_lprops * const lprops = &pnode->lprops[i]; 977 978 lprops->free = ubifs_unpack_bits(&addr, &pos, c->space_bits); 979 lprops->free <<= 3; 980 lprops->dirty = ubifs_unpack_bits(&addr, &pos, c->space_bits); 981 lprops->dirty <<= 3; 982 983 if (ubifs_unpack_bits(&addr, &pos, 1)) 984 lprops->flags = LPROPS_INDEX; 985 else 986 lprops->flags = 0; 987 lprops->flags |= ubifs_categorize_lprops(c, lprops); 988 } 989 err = check_lpt_crc(c, buf, c->pnode_sz); 990 return err; 991} 992 993/** 994 * ubifs_unpack_nnode - unpack a nnode. 995 * @c: UBIFS file-system description object 996 * @buf: buffer containing packed nnode to unpack 997 * @nnode: nnode structure to fill 998 * 999 * This function returns %0 on success and a negative error code on failure. 1000 */ 1001int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf, 1002 struct ubifs_nnode *nnode) 1003{ 1004 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; 1005 int i, pos = 0, err; 1006 1007 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE); 1008 if (err) 1009 return err; 1010 if (c->big_lpt) 1011 nnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits); 1012 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1013 int lnum; 1014 1015 lnum = ubifs_unpack_bits(&addr, &pos, c->lpt_lnum_bits) + 1016 c->lpt_first; 1017 if (lnum == c->lpt_last + 1) 1018 lnum = 0; 1019 nnode->nbranch[i].lnum = lnum; 1020 nnode->nbranch[i].offs = ubifs_unpack_bits(&addr, &pos, 1021 c->lpt_offs_bits); 1022 } 1023 err = check_lpt_crc(c, buf, c->nnode_sz); 1024 return err; 1025} 1026 1027/** 1028 * unpack_ltab - unpack the LPT's own lprops table. 1029 * @c: UBIFS file-system description object 1030 * @buf: buffer from which to unpack 1031 * 1032 * This function returns %0 on success and a negative error code on failure. 1033 */ 1034static int unpack_ltab(const struct ubifs_info *c, void *buf) 1035{ 1036 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; 1037 int i, pos = 0, err; 1038 1039 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB); 1040 if (err) 1041 return err; 1042 for (i = 0; i < c->lpt_lebs; i++) { 1043 int free = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits); 1044 int dirty = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits); 1045 1046 if (free < 0 || free > c->leb_size || dirty < 0 || 1047 dirty > c->leb_size || free + dirty > c->leb_size) 1048 return -EINVAL; 1049 1050 c->ltab[i].free = free; 1051 c->ltab[i].dirty = dirty; 1052 c->ltab[i].tgc = 0; 1053 c->ltab[i].cmt = 0; 1054 } 1055 err = check_lpt_crc(c, buf, c->ltab_sz); 1056 return err; 1057} 1058 1059/** 1060 * unpack_lsave - unpack the LPT's save table. 1061 * @c: UBIFS file-system description object 1062 * @buf: buffer from which to unpack 1063 * 1064 * This function returns %0 on success and a negative error code on failure. 1065 */ 1066static int unpack_lsave(const struct ubifs_info *c, void *buf) 1067{ 1068 uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; 1069 int i, pos = 0, err; 1070 1071 err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE); 1072 if (err) 1073 return err; 1074 for (i = 0; i < c->lsave_cnt; i++) { 1075 int lnum = ubifs_unpack_bits(&addr, &pos, c->lnum_bits); 1076 1077 if (lnum < c->main_first || lnum >= c->leb_cnt) 1078 return -EINVAL; 1079 c->lsave[i] = lnum; 1080 } 1081 err = check_lpt_crc(c, buf, c->lsave_sz); 1082 return err; 1083} 1084 1085/** 1086 * validate_nnode - validate a nnode. 1087 * @c: UBIFS file-system description object 1088 * @nnode: nnode to validate 1089 * @parent: parent nnode (or NULL for the root nnode) 1090 * @iip: index in parent 1091 * 1092 * This function returns %0 on success and a negative error code on failure. 1093 */ 1094static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode, 1095 struct ubifs_nnode *parent, int iip) 1096{ 1097 int i, lvl, max_offs; 1098 1099 if (c->big_lpt) { 1100 int num = calc_nnode_num_from_parent(c, parent, iip); 1101 1102 if (nnode->num != num) 1103 return -EINVAL; 1104 } 1105 lvl = parent ? parent->level - 1 : c->lpt_hght; 1106 if (lvl < 1) 1107 return -EINVAL; 1108 if (lvl == 1) 1109 max_offs = c->leb_size - c->pnode_sz; 1110 else 1111 max_offs = c->leb_size - c->nnode_sz; 1112 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1113 int lnum = nnode->nbranch[i].lnum; 1114 int offs = nnode->nbranch[i].offs; 1115 1116 if (lnum == 0) { 1117 if (offs != 0) 1118 return -EINVAL; 1119 continue; 1120 } 1121 if (lnum < c->lpt_first || lnum > c->lpt_last) 1122 return -EINVAL; 1123 if (offs < 0 || offs > max_offs) 1124 return -EINVAL; 1125 } 1126 return 0; 1127} 1128 1129/** 1130 * validate_pnode - validate a pnode. 1131 * @c: UBIFS file-system description object 1132 * @pnode: pnode to validate 1133 * @parent: parent nnode 1134 * @iip: index in parent 1135 * 1136 * This function returns %0 on success and a negative error code on failure. 1137 */ 1138static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode, 1139 struct ubifs_nnode *parent, int iip) 1140{ 1141 int i; 1142 1143 if (c->big_lpt) { 1144 int num = calc_pnode_num_from_parent(c, parent, iip); 1145 1146 if (pnode->num != num) 1147 return -EINVAL; 1148 } 1149 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1150 int free = pnode->lprops[i].free; 1151 int dirty = pnode->lprops[i].dirty; 1152 1153 if (free < 0 || free > c->leb_size || free % c->min_io_size || 1154 (free & 7)) 1155 return -EINVAL; 1156 if (dirty < 0 || dirty > c->leb_size || (dirty & 7)) 1157 return -EINVAL; 1158 if (dirty + free > c->leb_size) 1159 return -EINVAL; 1160 } 1161 return 0; 1162} 1163 1164/** 1165 * set_pnode_lnum - set LEB numbers on a pnode. 1166 * @c: UBIFS file-system description object 1167 * @pnode: pnode to update 1168 * 1169 * This function calculates the LEB numbers for the LEB properties it contains 1170 * based on the pnode number. 1171 */ 1172static void set_pnode_lnum(const struct ubifs_info *c, 1173 struct ubifs_pnode *pnode) 1174{ 1175 int i, lnum; 1176 1177 lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first; 1178 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1179 if (lnum >= c->leb_cnt) 1180 return; 1181 pnode->lprops[i].lnum = lnum++; 1182 } 1183} 1184 1185/** 1186 * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory. 1187 * @c: UBIFS file-system description object 1188 * @parent: parent nnode (or NULL for the root) 1189 * @iip: index in parent 1190 * 1191 * This function returns %0 on success and a negative error code on failure. 1192 */ 1193int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) 1194{ 1195 struct ubifs_nbranch *branch = NULL; 1196 struct ubifs_nnode *nnode = NULL; 1197 void *buf = c->lpt_nod_buf; 1198 int err, lnum, offs; 1199 1200 if (parent) { 1201 branch = &parent->nbranch[iip]; 1202 lnum = branch->lnum; 1203 offs = branch->offs; 1204 } else { 1205 lnum = c->lpt_lnum; 1206 offs = c->lpt_offs; 1207 } 1208 nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS); 1209 if (!nnode) { 1210 err = -ENOMEM; 1211 goto out; 1212 } 1213 if (lnum == 0) { 1214 /* 1215 * This nnode was not written which just means that the LEB 1216 * properties in the subtree below it describe empty LEBs. We 1217 * make the nnode as though we had read it, which in fact means 1218 * doing almost nothing. 1219 */ 1220 if (c->big_lpt) 1221 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1222 } else { 1223 err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1); 1224 if (err) 1225 goto out; 1226 err = ubifs_unpack_nnode(c, buf, nnode); 1227 if (err) 1228 goto out; 1229 } 1230 err = validate_nnode(c, nnode, parent, iip); 1231 if (err) 1232 goto out; 1233 if (!c->big_lpt) 1234 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1235 if (parent) { 1236 branch->nnode = nnode; 1237 nnode->level = parent->level - 1; 1238 } else { 1239 c->nroot = nnode; 1240 nnode->level = c->lpt_hght; 1241 } 1242 nnode->parent = parent; 1243 nnode->iip = iip; 1244 return 0; 1245 1246out: 1247 ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs); 1248 dump_stack(); 1249 kfree(nnode); 1250 return err; 1251} 1252 1253/** 1254 * read_pnode - read a pnode from flash and link it to the tree in memory. 1255 * @c: UBIFS file-system description object 1256 * @parent: parent nnode 1257 * @iip: index in parent 1258 * 1259 * This function returns %0 on success and a negative error code on failure. 1260 */ 1261static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) 1262{ 1263 struct ubifs_nbranch *branch; 1264 struct ubifs_pnode *pnode = NULL; 1265 void *buf = c->lpt_nod_buf; 1266 int err, lnum, offs; 1267 1268 branch = &parent->nbranch[iip]; 1269 lnum = branch->lnum; 1270 offs = branch->offs; 1271 pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS); 1272 if (!pnode) 1273 return -ENOMEM; 1274 1275 if (lnum == 0) { 1276 /* 1277 * This pnode was not written which just means that the LEB 1278 * properties in it describe empty LEBs. We make the pnode as 1279 * though we had read it. 1280 */ 1281 int i; 1282 1283 if (c->big_lpt) 1284 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 1285 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1286 struct ubifs_lprops * const lprops = &pnode->lprops[i]; 1287 1288 lprops->free = c->leb_size; 1289 lprops->flags = ubifs_categorize_lprops(c, lprops); 1290 } 1291 } else { 1292 err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1); 1293 if (err) 1294 goto out; 1295 err = unpack_pnode(c, buf, pnode); 1296 if (err) 1297 goto out; 1298 } 1299 err = validate_pnode(c, pnode, parent, iip); 1300 if (err) 1301 goto out; 1302 if (!c->big_lpt) 1303 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 1304 branch->pnode = pnode; 1305 pnode->parent = parent; 1306 pnode->iip = iip; 1307 set_pnode_lnum(c, pnode); 1308 c->pnodes_have += 1; 1309 return 0; 1310 1311out: 1312 ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs); 1313 ubifs_dump_pnode(c, pnode, parent, iip); 1314 dump_stack(); 1315 ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip)); 1316 kfree(pnode); 1317 return err; 1318} 1319 1320/** 1321 * read_ltab - read LPT's own lprops table. 1322 * @c: UBIFS file-system description object 1323 * 1324 * This function returns %0 on success and a negative error code on failure. 1325 */ 1326static int read_ltab(struct ubifs_info *c) 1327{ 1328 int err; 1329 void *buf; 1330 1331 buf = vmalloc(c->ltab_sz); 1332 if (!buf) 1333 return -ENOMEM; 1334 err = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1); 1335 if (err) 1336 goto out; 1337 err = unpack_ltab(c, buf); 1338out: 1339 vfree(buf); 1340 return err; 1341} 1342 1343/** 1344 * read_lsave - read LPT's save table. 1345 * @c: UBIFS file-system description object 1346 * 1347 * This function returns %0 on success and a negative error code on failure. 1348 */ 1349static int read_lsave(struct ubifs_info *c) 1350{ 1351 int err, i; 1352 void *buf; 1353 1354 buf = vmalloc(c->lsave_sz); 1355 if (!buf) 1356 return -ENOMEM; 1357 err = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs, 1358 c->lsave_sz, 1); 1359 if (err) 1360 goto out; 1361 err = unpack_lsave(c, buf); 1362 if (err) 1363 goto out; 1364 for (i = 0; i < c->lsave_cnt; i++) { 1365 int lnum = c->lsave[i]; 1366 struct ubifs_lprops *lprops; 1367 1368 /* 1369 * Due to automatic resizing, the values in the lsave table 1370 * could be beyond the volume size - just ignore them. 1371 */ 1372 if (lnum >= c->leb_cnt) 1373 continue; 1374 lprops = ubifs_lpt_lookup(c, lnum); 1375 if (IS_ERR(lprops)) { 1376 err = PTR_ERR(lprops); 1377 goto out; 1378 } 1379 } 1380out: 1381 vfree(buf); 1382 return err; 1383} 1384 1385/** 1386 * ubifs_get_nnode - get a nnode. 1387 * @c: UBIFS file-system description object 1388 * @parent: parent nnode (or NULL for the root) 1389 * @iip: index in parent 1390 * 1391 * This function returns a pointer to the nnode on success or a negative error 1392 * code on failure. 1393 */ 1394struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c, 1395 struct ubifs_nnode *parent, int iip) 1396{ 1397 struct ubifs_nbranch *branch; 1398 struct ubifs_nnode *nnode; 1399 int err; 1400 1401 branch = &parent->nbranch[iip]; 1402 nnode = branch->nnode; 1403 if (nnode) 1404 return nnode; 1405 err = ubifs_read_nnode(c, parent, iip); 1406 if (err) 1407 return ERR_PTR(err); 1408 return branch->nnode; 1409} 1410 1411/** 1412 * ubifs_get_pnode - get a pnode. 1413 * @c: UBIFS file-system description object 1414 * @parent: parent nnode 1415 * @iip: index in parent 1416 * 1417 * This function returns a pointer to the pnode on success or a negative error 1418 * code on failure. 1419 */ 1420struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c, 1421 struct ubifs_nnode *parent, int iip) 1422{ 1423 struct ubifs_nbranch *branch; 1424 struct ubifs_pnode *pnode; 1425 int err; 1426 1427 branch = &parent->nbranch[iip]; 1428 pnode = branch->pnode; 1429 if (pnode) 1430 return pnode; 1431 err = read_pnode(c, parent, iip); 1432 if (err) 1433 return ERR_PTR(err); 1434 update_cats(c, branch->pnode); 1435 return branch->pnode; 1436} 1437 1438/** 1439 * ubifs_lpt_lookup - lookup LEB properties in the LPT. 1440 * @c: UBIFS file-system description object 1441 * @lnum: LEB number to lookup 1442 * 1443 * This function returns a pointer to the LEB properties on success or a 1444 * negative error code on failure. 1445 */ 1446struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum) 1447{ 1448 int err, i, h, iip, shft; 1449 struct ubifs_nnode *nnode; 1450 struct ubifs_pnode *pnode; 1451 1452 if (!c->nroot) { 1453 err = ubifs_read_nnode(c, NULL, 0); 1454 if (err) 1455 return ERR_PTR(err); 1456 } 1457 nnode = c->nroot; 1458 i = lnum - c->main_first; 1459 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; 1460 for (h = 1; h < c->lpt_hght; h++) { 1461 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1462 shft -= UBIFS_LPT_FANOUT_SHIFT; 1463 nnode = ubifs_get_nnode(c, nnode, iip); 1464 if (IS_ERR(nnode)) 1465 return ERR_CAST(nnode); 1466 } 1467 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1468 pnode = ubifs_get_pnode(c, nnode, iip); 1469 if (IS_ERR(pnode)) 1470 return ERR_CAST(pnode); 1471 iip = (i & (UBIFS_LPT_FANOUT - 1)); 1472 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum, 1473 pnode->lprops[iip].free, pnode->lprops[iip].dirty, 1474 pnode->lprops[iip].flags); 1475 return &pnode->lprops[iip]; 1476} 1477 1478/** 1479 * dirty_cow_nnode - ensure a nnode is not being committed. 1480 * @c: UBIFS file-system description object 1481 * @nnode: nnode to check 1482 * 1483 * Returns dirtied nnode on success or negative error code on failure. 1484 */ 1485static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c, 1486 struct ubifs_nnode *nnode) 1487{ 1488 struct ubifs_nnode *n; 1489 int i; 1490 1491 if (!test_bit(COW_CNODE, &nnode->flags)) { 1492 /* nnode is not being committed */ 1493 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) { 1494 c->dirty_nn_cnt += 1; 1495 ubifs_add_nnode_dirt(c, nnode); 1496 } 1497 return nnode; 1498 } 1499 1500 /* nnode is being committed, so copy it */ 1501 n = kmalloc(sizeof(struct ubifs_nnode), GFP_NOFS); 1502 if (unlikely(!n)) 1503 return ERR_PTR(-ENOMEM); 1504 1505 memcpy(n, nnode, sizeof(struct ubifs_nnode)); 1506 n->cnext = NULL; 1507 __set_bit(DIRTY_CNODE, &n->flags); 1508 __clear_bit(COW_CNODE, &n->flags); 1509 1510 /* The children now have new parent */ 1511 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1512 struct ubifs_nbranch *branch = &n->nbranch[i]; 1513 1514 if (branch->cnode) 1515 branch->cnode->parent = n; 1516 } 1517 1518 ubifs_assert(!test_bit(OBSOLETE_CNODE, &nnode->flags)); 1519 __set_bit(OBSOLETE_CNODE, &nnode->flags); 1520 1521 c->dirty_nn_cnt += 1; 1522 ubifs_add_nnode_dirt(c, nnode); 1523 if (nnode->parent) 1524 nnode->parent->nbranch[n->iip].nnode = n; 1525 else 1526 c->nroot = n; 1527 return n; 1528} 1529 1530/** 1531 * dirty_cow_pnode - ensure a pnode is not being committed. 1532 * @c: UBIFS file-system description object 1533 * @pnode: pnode to check 1534 * 1535 * Returns dirtied pnode on success or negative error code on failure. 1536 */ 1537static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c, 1538 struct ubifs_pnode *pnode) 1539{ 1540 struct ubifs_pnode *p; 1541 1542 if (!test_bit(COW_CNODE, &pnode->flags)) { 1543 /* pnode is not being committed */ 1544 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) { 1545 c->dirty_pn_cnt += 1; 1546 add_pnode_dirt(c, pnode); 1547 } 1548 return pnode; 1549 } 1550 1551 /* pnode is being committed, so copy it */ 1552 p = kmalloc(sizeof(struct ubifs_pnode), GFP_NOFS); 1553 if (unlikely(!p)) 1554 return ERR_PTR(-ENOMEM); 1555 1556 memcpy(p, pnode, sizeof(struct ubifs_pnode)); 1557 p->cnext = NULL; 1558 __set_bit(DIRTY_CNODE, &p->flags); 1559 __clear_bit(COW_CNODE, &p->flags); 1560 replace_cats(c, pnode, p); 1561 1562 ubifs_assert(!test_bit(OBSOLETE_CNODE, &pnode->flags)); 1563 __set_bit(OBSOLETE_CNODE, &pnode->flags); 1564 1565 c->dirty_pn_cnt += 1; 1566 add_pnode_dirt(c, pnode); 1567 pnode->parent->nbranch[p->iip].pnode = p; 1568 return p; 1569} 1570 1571/** 1572 * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT. 1573 * @c: UBIFS file-system description object 1574 * @lnum: LEB number to lookup 1575 * 1576 * This function returns a pointer to the LEB properties on success or a 1577 * negative error code on failure. 1578 */ 1579struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum) 1580{ 1581 int err, i, h, iip, shft; 1582 struct ubifs_nnode *nnode; 1583 struct ubifs_pnode *pnode; 1584 1585 if (!c->nroot) { 1586 err = ubifs_read_nnode(c, NULL, 0); 1587 if (err) 1588 return ERR_PTR(err); 1589 } 1590 nnode = c->nroot; 1591 nnode = dirty_cow_nnode(c, nnode); 1592 if (IS_ERR(nnode)) 1593 return ERR_CAST(nnode); 1594 i = lnum - c->main_first; 1595 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; 1596 for (h = 1; h < c->lpt_hght; h++) { 1597 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1598 shft -= UBIFS_LPT_FANOUT_SHIFT; 1599 nnode = ubifs_get_nnode(c, nnode, iip); 1600 if (IS_ERR(nnode)) 1601 return ERR_CAST(nnode); 1602 nnode = dirty_cow_nnode(c, nnode); 1603 if (IS_ERR(nnode)) 1604 return ERR_CAST(nnode); 1605 } 1606 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1607 pnode = ubifs_get_pnode(c, nnode, iip); 1608 if (IS_ERR(pnode)) 1609 return ERR_CAST(pnode); 1610 pnode = dirty_cow_pnode(c, pnode); 1611 if (IS_ERR(pnode)) 1612 return ERR_CAST(pnode); 1613 iip = (i & (UBIFS_LPT_FANOUT - 1)); 1614 dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum, 1615 pnode->lprops[iip].free, pnode->lprops[iip].dirty, 1616 pnode->lprops[iip].flags); 1617 ubifs_assert(test_bit(DIRTY_CNODE, &pnode->flags)); 1618 return &pnode->lprops[iip]; 1619} 1620 1621/** 1622 * lpt_init_rd - initialize the LPT for reading. 1623 * @c: UBIFS file-system description object 1624 * 1625 * This function returns %0 on success and a negative error code on failure. 1626 */ 1627static int lpt_init_rd(struct ubifs_info *c) 1628{ 1629 int err, i; 1630 1631 c->ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs); 1632 if (!c->ltab) 1633 return -ENOMEM; 1634 1635 i = max_t(int, c->nnode_sz, c->pnode_sz); 1636 c->lpt_nod_buf = kmalloc(i, GFP_KERNEL); 1637 if (!c->lpt_nod_buf) 1638 return -ENOMEM; 1639 1640 for (i = 0; i < LPROPS_HEAP_CNT; i++) { 1641 c->lpt_heap[i].arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ, 1642 GFP_KERNEL); 1643 if (!c->lpt_heap[i].arr) 1644 return -ENOMEM; 1645 c->lpt_heap[i].cnt = 0; 1646 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ; 1647 } 1648 1649 c->dirty_idx.arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ, GFP_KERNEL); 1650 if (!c->dirty_idx.arr) 1651 return -ENOMEM; 1652 c->dirty_idx.cnt = 0; 1653 c->dirty_idx.max_cnt = LPT_HEAP_SZ; 1654 1655 err = read_ltab(c); 1656 if (err) 1657 return err; 1658 1659 dbg_lp("space_bits %d", c->space_bits); 1660 dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits); 1661 dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits); 1662 dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits); 1663 dbg_lp("pcnt_bits %d", c->pcnt_bits); 1664 dbg_lp("lnum_bits %d", c->lnum_bits); 1665 dbg_lp("pnode_sz %d", c->pnode_sz); 1666 dbg_lp("nnode_sz %d", c->nnode_sz); 1667 dbg_lp("ltab_sz %d", c->ltab_sz); 1668 dbg_lp("lsave_sz %d", c->lsave_sz); 1669 dbg_lp("lsave_cnt %d", c->lsave_cnt); 1670 dbg_lp("lpt_hght %d", c->lpt_hght); 1671 dbg_lp("big_lpt %d", c->big_lpt); 1672 dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs); 1673 dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs); 1674 dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs); 1675 if (c->big_lpt) 1676 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs); 1677 1678 return 0; 1679} 1680 1681/** 1682 * lpt_init_wr - initialize the LPT for writing. 1683 * @c: UBIFS file-system description object 1684 * 1685 * 'lpt_init_rd()' must have been called already. 1686 * 1687 * This function returns %0 on success and a negative error code on failure. 1688 */ 1689static int lpt_init_wr(struct ubifs_info *c) 1690{ 1691 int err, i; 1692 1693 c->ltab_cmt = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs); 1694 if (!c->ltab_cmt) 1695 return -ENOMEM; 1696 1697 c->lpt_buf = vmalloc(c->leb_size); 1698 if (!c->lpt_buf) 1699 return -ENOMEM; 1700 1701 if (c->big_lpt) { 1702 c->lsave = kmalloc(sizeof(int) * c->lsave_cnt, GFP_NOFS); 1703 if (!c->lsave) 1704 return -ENOMEM; 1705 err = read_lsave(c); 1706 if (err) 1707 return err; 1708 } 1709 1710 for (i = 0; i < c->lpt_lebs; i++) 1711 if (c->ltab[i].free == c->leb_size) { 1712 err = ubifs_leb_unmap(c, i + c->lpt_first); 1713 if (err) 1714 return err; 1715 } 1716 1717 return 0; 1718} 1719 1720/** 1721 * ubifs_lpt_init - initialize the LPT. 1722 * @c: UBIFS file-system description object 1723 * @rd: whether to initialize lpt for reading 1724 * @wr: whether to initialize lpt for writing 1725 * 1726 * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true 1727 * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is 1728 * true. 1729 * 1730 * This function returns %0 on success and a negative error code on failure. 1731 */ 1732int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr) 1733{ 1734 int err; 1735 1736 if (rd) { 1737 err = lpt_init_rd(c); 1738 if (err) 1739 goto out_err; 1740 } 1741 1742 if (wr) { 1743 err = lpt_init_wr(c); 1744 if (err) 1745 goto out_err; 1746 } 1747 1748 return 0; 1749 1750out_err: 1751 if (wr) 1752 ubifs_lpt_free(c, 1); 1753 if (rd) 1754 ubifs_lpt_free(c, 0); 1755 return err; 1756} 1757 1758/** 1759 * struct lpt_scan_node - somewhere to put nodes while we scan LPT. 1760 * @nnode: where to keep a nnode 1761 * @pnode: where to keep a pnode 1762 * @cnode: where to keep a cnode 1763 * @in_tree: is the node in the tree in memory 1764 * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in 1765 * the tree 1766 * @ptr.pnode: ditto for pnode 1767 * @ptr.cnode: ditto for cnode 1768 */ 1769struct lpt_scan_node { 1770 union { 1771 struct ubifs_nnode nnode; 1772 struct ubifs_pnode pnode; 1773 struct ubifs_cnode cnode; 1774 }; 1775 int in_tree; 1776 union { 1777 struct ubifs_nnode *nnode; 1778 struct ubifs_pnode *pnode; 1779 struct ubifs_cnode *cnode; 1780 } ptr; 1781}; 1782 1783/** 1784 * scan_get_nnode - for the scan, get a nnode from either the tree or flash. 1785 * @c: the UBIFS file-system description object 1786 * @path: where to put the nnode 1787 * @parent: parent of the nnode 1788 * @iip: index in parent of the nnode 1789 * 1790 * This function returns a pointer to the nnode on success or a negative error 1791 * code on failure. 1792 */ 1793static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c, 1794 struct lpt_scan_node *path, 1795 struct ubifs_nnode *parent, int iip) 1796{ 1797 struct ubifs_nbranch *branch; 1798 struct ubifs_nnode *nnode; 1799 void *buf = c->lpt_nod_buf; 1800 int err; 1801 1802 branch = &parent->nbranch[iip]; 1803 nnode = branch->nnode; 1804 if (nnode) { 1805 path->in_tree = 1; 1806 path->ptr.nnode = nnode; 1807 return nnode; 1808 } 1809 nnode = &path->nnode; 1810 path->in_tree = 0; 1811 path->ptr.nnode = nnode; 1812 memset(nnode, 0, sizeof(struct ubifs_nnode)); 1813 if (branch->lnum == 0) { 1814 /* 1815 * This nnode was not written which just means that the LEB 1816 * properties in the subtree below it describe empty LEBs. We 1817 * make the nnode as though we had read it, which in fact means 1818 * doing almost nothing. 1819 */ 1820 if (c->big_lpt) 1821 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1822 } else { 1823 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs, 1824 c->nnode_sz, 1); 1825 if (err) 1826 return ERR_PTR(err); 1827 err = ubifs_unpack_nnode(c, buf, nnode); 1828 if (err) 1829 return ERR_PTR(err); 1830 } 1831 err = validate_nnode(c, nnode, parent, iip); 1832 if (err) 1833 return ERR_PTR(err); 1834 if (!c->big_lpt) 1835 nnode->num = calc_nnode_num_from_parent(c, parent, iip); 1836 nnode->level = parent->level - 1; 1837 nnode->parent = parent; 1838 nnode->iip = iip; 1839 return nnode; 1840} 1841 1842/** 1843 * scan_get_pnode - for the scan, get a pnode from either the tree or flash. 1844 * @c: the UBIFS file-system description object 1845 * @path: where to put the pnode 1846 * @parent: parent of the pnode 1847 * @iip: index in parent of the pnode 1848 * 1849 * This function returns a pointer to the pnode on success or a negative error 1850 * code on failure. 1851 */ 1852static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c, 1853 struct lpt_scan_node *path, 1854 struct ubifs_nnode *parent, int iip) 1855{ 1856 struct ubifs_nbranch *branch; 1857 struct ubifs_pnode *pnode; 1858 void *buf = c->lpt_nod_buf; 1859 int err; 1860 1861 branch = &parent->nbranch[iip]; 1862 pnode = branch->pnode; 1863 if (pnode) { 1864 path->in_tree = 1; 1865 path->ptr.pnode = pnode; 1866 return pnode; 1867 } 1868 pnode = &path->pnode; 1869 path->in_tree = 0; 1870 path->ptr.pnode = pnode; 1871 memset(pnode, 0, sizeof(struct ubifs_pnode)); 1872 if (branch->lnum == 0) { 1873 /* 1874 * This pnode was not written which just means that the LEB 1875 * properties in it describe empty LEBs. We make the pnode as 1876 * though we had read it. 1877 */ 1878 int i; 1879 1880 if (c->big_lpt) 1881 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 1882 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 1883 struct ubifs_lprops * const lprops = &pnode->lprops[i]; 1884 1885 lprops->free = c->leb_size; 1886 lprops->flags = ubifs_categorize_lprops(c, lprops); 1887 } 1888 } else { 1889 ubifs_assert(branch->lnum >= c->lpt_first && 1890 branch->lnum <= c->lpt_last); 1891 ubifs_assert(branch->offs >= 0 && branch->offs < c->leb_size); 1892 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs, 1893 c->pnode_sz, 1); 1894 if (err) 1895 return ERR_PTR(err); 1896 err = unpack_pnode(c, buf, pnode); 1897 if (err) 1898 return ERR_PTR(err); 1899 } 1900 err = validate_pnode(c, pnode, parent, iip); 1901 if (err) 1902 return ERR_PTR(err); 1903 if (!c->big_lpt) 1904 pnode->num = calc_pnode_num_from_parent(c, parent, iip); 1905 pnode->parent = parent; 1906 pnode->iip = iip; 1907 set_pnode_lnum(c, pnode); 1908 return pnode; 1909} 1910 1911/** 1912 * ubifs_lpt_scan_nolock - scan the LPT. 1913 * @c: the UBIFS file-system description object 1914 * @start_lnum: LEB number from which to start scanning 1915 * @end_lnum: LEB number at which to stop scanning 1916 * @scan_cb: callback function called for each lprops 1917 * @data: data to be passed to the callback function 1918 * 1919 * This function returns %0 on success and a negative error code on failure. 1920 */ 1921int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum, 1922 ubifs_lpt_scan_callback scan_cb, void *data) 1923{ 1924 int err = 0, i, h, iip, shft; 1925 struct ubifs_nnode *nnode; 1926 struct ubifs_pnode *pnode; 1927 struct lpt_scan_node *path; 1928 1929 if (start_lnum == -1) { 1930 start_lnum = end_lnum + 1; 1931 if (start_lnum >= c->leb_cnt) 1932 start_lnum = c->main_first; 1933 } 1934 1935 ubifs_assert(start_lnum >= c->main_first && start_lnum < c->leb_cnt); 1936 ubifs_assert(end_lnum >= c->main_first && end_lnum < c->leb_cnt); 1937 1938 if (!c->nroot) { 1939 err = ubifs_read_nnode(c, NULL, 0); 1940 if (err) 1941 return err; 1942 } 1943 1944 path = kmalloc(sizeof(struct lpt_scan_node) * (c->lpt_hght + 1), 1945 GFP_NOFS); 1946 if (!path) 1947 return -ENOMEM; 1948 1949 path[0].ptr.nnode = c->nroot; 1950 path[0].in_tree = 1; 1951again: 1952 /* Descend to the pnode containing start_lnum */ 1953 nnode = c->nroot; 1954 i = start_lnum - c->main_first; 1955 shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT; 1956 for (h = 1; h < c->lpt_hght; h++) { 1957 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1958 shft -= UBIFS_LPT_FANOUT_SHIFT; 1959 nnode = scan_get_nnode(c, path + h, nnode, iip); 1960 if (IS_ERR(nnode)) { 1961 err = PTR_ERR(nnode); 1962 goto out; 1963 } 1964 } 1965 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1)); 1966 pnode = scan_get_pnode(c, path + h, nnode, iip); 1967 if (IS_ERR(pnode)) { 1968 err = PTR_ERR(pnode); 1969 goto out; 1970 } 1971 iip = (i & (UBIFS_LPT_FANOUT - 1)); 1972 1973 /* Loop for each lprops */ 1974 while (1) { 1975 struct ubifs_lprops *lprops = &pnode->lprops[iip]; 1976 int ret, lnum = lprops->lnum; 1977 1978 ret = scan_cb(c, lprops, path[h].in_tree, data); 1979 if (ret < 0) { 1980 err = ret; 1981 goto out; 1982 } 1983 if (ret & LPT_SCAN_ADD) { 1984 /* Add all the nodes in path to the tree in memory */ 1985 for (h = 1; h < c->lpt_hght; h++) { 1986 const size_t sz = sizeof(struct ubifs_nnode); 1987 struct ubifs_nnode *parent; 1988 1989 if (path[h].in_tree) 1990 continue; 1991 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS); 1992 if (!nnode) { 1993 err = -ENOMEM; 1994 goto out; 1995 } 1996 parent = nnode->parent; 1997 parent->nbranch[nnode->iip].nnode = nnode; 1998 path[h].ptr.nnode = nnode; 1999 path[h].in_tree = 1; 2000 path[h + 1].cnode.parent = nnode; 2001 } 2002 if (path[h].in_tree) 2003 ubifs_ensure_cat(c, lprops); 2004 else { 2005 const size_t sz = sizeof(struct ubifs_pnode); 2006 struct ubifs_nnode *parent; 2007 2008 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS); 2009 if (!pnode) { 2010 err = -ENOMEM; 2011 goto out; 2012 } 2013 parent = pnode->parent; 2014 parent->nbranch[pnode->iip].pnode = pnode; 2015 path[h].ptr.pnode = pnode; 2016 path[h].in_tree = 1; 2017 update_cats(c, pnode); 2018 c->pnodes_have += 1; 2019 } 2020 err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *) 2021 c->nroot, 0, 0); 2022 if (err) 2023 goto out; 2024 err = dbg_check_cats(c); 2025 if (err) 2026 goto out; 2027 } 2028 if (ret & LPT_SCAN_STOP) { 2029 err = 0; 2030 break; 2031 } 2032 /* Get the next lprops */ 2033 if (lnum == end_lnum) { 2034 /* 2035 * We got to the end without finding what we were 2036 * looking for 2037 */ 2038 err = -ENOSPC; 2039 goto out; 2040 } 2041 if (lnum + 1 >= c->leb_cnt) { 2042 /* Wrap-around to the beginning */ 2043 start_lnum = c->main_first; 2044 goto again; 2045 } 2046 if (iip + 1 < UBIFS_LPT_FANOUT) { 2047 /* Next lprops is in the same pnode */ 2048 iip += 1; 2049 continue; 2050 } 2051 /* We need to get the next pnode. Go up until we can go right */ 2052 iip = pnode->iip; 2053 while (1) { 2054 h -= 1; 2055 ubifs_assert(h >= 0); 2056 nnode = path[h].ptr.nnode; 2057 if (iip + 1 < UBIFS_LPT_FANOUT) 2058 break; 2059 iip = nnode->iip; 2060 } 2061 /* Go right */ 2062 iip += 1; 2063 /* Descend to the pnode */ 2064 h += 1; 2065 for (; h < c->lpt_hght; h++) { 2066 nnode = scan_get_nnode(c, path + h, nnode, iip); 2067 if (IS_ERR(nnode)) { 2068 err = PTR_ERR(nnode); 2069 goto out; 2070 } 2071 iip = 0; 2072 } 2073 pnode = scan_get_pnode(c, path + h, nnode, iip); 2074 if (IS_ERR(pnode)) { 2075 err = PTR_ERR(pnode); 2076 goto out; 2077 } 2078 iip = 0; 2079 } 2080out: 2081 kfree(path); 2082 return err; 2083} 2084 2085/** 2086 * dbg_chk_pnode - check a pnode. 2087 * @c: the UBIFS file-system description object 2088 * @pnode: pnode to check 2089 * @col: pnode column 2090 * 2091 * This function returns %0 on success and a negative error code on failure. 2092 */ 2093static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode, 2094 int col) 2095{ 2096 int i; 2097 2098 if (pnode->num != col) { 2099 ubifs_err(c, "pnode num %d expected %d parent num %d iip %d", 2100 pnode->num, col, pnode->parent->num, pnode->iip); 2101 return -EINVAL; 2102 } 2103 for (i = 0; i < UBIFS_LPT_FANOUT; i++) { 2104 struct ubifs_lprops *lp, *lprops = &pnode->lprops[i]; 2105 int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i + 2106 c->main_first; 2107 int found, cat = lprops->flags & LPROPS_CAT_MASK; 2108 struct ubifs_lpt_heap *heap; 2109 struct list_head *list = NULL; 2110 2111 if (lnum >= c->leb_cnt) 2112 continue; 2113 if (lprops->lnum != lnum) { 2114 ubifs_err(c, "bad LEB number %d expected %d", 2115 lprops->lnum, lnum); 2116 return -EINVAL; 2117 } 2118 if (lprops->flags & LPROPS_TAKEN) { 2119 if (cat != LPROPS_UNCAT) { 2120 ubifs_err(c, "LEB %d taken but not uncat %d", 2121 lprops->lnum, cat); 2122 return -EINVAL; 2123 } 2124 continue; 2125 } 2126 if (lprops->flags & LPROPS_INDEX) { 2127 switch (cat) { 2128 case LPROPS_UNCAT: 2129 case LPROPS_DIRTY_IDX: 2130 case LPROPS_FRDI_IDX: 2131 break; 2132 default: 2133 ubifs_err(c, "LEB %d index but cat %d", 2134 lprops->lnum, cat); 2135 return -EINVAL; 2136 } 2137 } else { 2138 switch (cat) { 2139 case LPROPS_UNCAT: 2140 case LPROPS_DIRTY: 2141 case LPROPS_FREE: 2142 case LPROPS_EMPTY: 2143 case LPROPS_FREEABLE: 2144 break; 2145 default: 2146 ubifs_err(c, "LEB %d not index but cat %d", 2147 lprops->lnum, cat); 2148 return -EINVAL; 2149 } 2150 } 2151 switch (cat) { 2152 case LPROPS_UNCAT: 2153 list = &c->uncat_list; 2154 break; 2155 case LPROPS_EMPTY: 2156 list = &c->empty_list; 2157 break; 2158 case LPROPS_FREEABLE: 2159 list = &c->freeable_list; 2160 break; 2161 case LPROPS_FRDI_IDX: 2162 list = &c->frdi_idx_list; 2163 break; 2164 } 2165 found = 0; 2166 switch (cat) { 2167 case LPROPS_DIRTY: 2168 case LPROPS_DIRTY_IDX: 2169 case LPROPS_FREE: 2170 heap = &c->lpt_heap[cat - 1]; 2171 if (lprops->hpos < heap->cnt && 2172 heap->arr[lprops->hpos] == lprops) 2173 found = 1; 2174 break; 2175 case LPROPS_UNCAT: 2176 case LPROPS_EMPTY: 2177 case LPROPS_FREEABLE: 2178 case LPROPS_FRDI_IDX: 2179 list_for_each_entry(lp, list, list) 2180 if (lprops == lp) { 2181 found = 1; 2182 break; 2183 } 2184 break; 2185 } 2186 if (!found) { 2187 ubifs_err(c, "LEB %d cat %d not found in cat heap/list", 2188 lprops->lnum, cat); 2189 return -EINVAL; 2190 } 2191 switch (cat) { 2192 case LPROPS_EMPTY: 2193 if (lprops->free != c->leb_size) { 2194 ubifs_err(c, "LEB %d cat %d free %d dirty %d", 2195 lprops->lnum, cat, lprops->free, 2196 lprops->dirty); 2197 return -EINVAL; 2198 } 2199 break; 2200 case LPROPS_FREEABLE: 2201 case LPROPS_FRDI_IDX: 2202 if (lprops->free + lprops->dirty != c->leb_size) { 2203 ubifs_err(c, "LEB %d cat %d free %d dirty %d", 2204 lprops->lnum, cat, lprops->free, 2205 lprops->dirty); 2206 return -EINVAL; 2207 } 2208 break; 2209 } 2210 } 2211 return 0; 2212} 2213 2214/** 2215 * dbg_check_lpt_nodes - check nnodes and pnodes. 2216 * @c: the UBIFS file-system description object 2217 * @cnode: next cnode (nnode or pnode) to check 2218 * @row: row of cnode (root is zero) 2219 * @col: column of cnode (leftmost is zero) 2220 * 2221 * This function returns %0 on success and a negative error code on failure. 2222 */ 2223int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode, 2224 int row, int col) 2225{ 2226 struct ubifs_nnode *nnode, *nn; 2227 struct ubifs_cnode *cn; 2228 int num, iip = 0, err; 2229 2230 if (!dbg_is_chk_lprops(c)) 2231 return 0; 2232 2233 while (cnode) { 2234 ubifs_assert(row >= 0); 2235 nnode = cnode->parent; 2236 if (cnode->level) { 2237 /* cnode is a nnode */ 2238 num = calc_nnode_num(row, col); 2239 if (cnode->num != num) { 2240 ubifs_err(c, "nnode num %d expected %d parent num %d iip %d", 2241 cnode->num, num, 2242 (nnode ? nnode->num : 0), cnode->iip); 2243 return -EINVAL; 2244 } 2245 nn = (struct ubifs_nnode *)cnode; 2246 while (iip < UBIFS_LPT_FANOUT) { 2247 cn = nn->nbranch[iip].cnode; 2248 if (cn) { 2249 /* Go down */ 2250 row += 1; 2251 col <<= UBIFS_LPT_FANOUT_SHIFT; 2252 col += iip; 2253 iip = 0; 2254 cnode = cn; 2255 break; 2256 } 2257 /* Go right */ 2258 iip += 1; 2259 } 2260 if (iip < UBIFS_LPT_FANOUT) 2261 continue; 2262 } else { 2263 struct ubifs_pnode *pnode; 2264 2265 /* cnode is a pnode */ 2266 pnode = (struct ubifs_pnode *)cnode; 2267 err = dbg_chk_pnode(c, pnode, col); 2268 if (err) 2269 return err; 2270 } 2271 /* Go up and to the right */ 2272 row -= 1; 2273 col >>= UBIFS_LPT_FANOUT_SHIFT; 2274 iip = cnode->iip + 1; 2275 cnode = (struct ubifs_cnode *)nnode; 2276 } 2277 return 0; 2278} 2279