fs/ubifs/lpt.c

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