fs/ubifs/lpt.c

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