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