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 of marking the clean nodes in
  40  * that LEB as dirty, and then only the dirty nodes are written out. Also, in
  41  * the case of the big model, a table of LEB numbers is saved so that the entire
  42  * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
  43  * mounted.
  44  */
  45
  46 #include "ubifs.h"
  47 #include "crc16.h"
  48 #include <linux/math64.h>
  49
  50 /**
  51  * do_calc_lpt_geom - calculate sizes for the LPT area.
  52  * @c: the UBIFS file-system description object
  53  *
  54  * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
  55  * properties of the flash and whether LPT is "big" (c->big_lpt).
  56  */
  57 static void do_calc_lpt_geom(struct ubifs_info *c)
  58 {
  59         int i, n, bits, per_leb_wastage, max_pnode_cnt;
  60         long long sz, tot_wastage;
  61
  62         n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;
  63         max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
  64
  65         c->lpt_hght = 1;
  66         n = UBIFS_LPT_FANOUT;
  67         while (n < max_pnode_cnt) {
  68                 c->lpt_hght += 1;
  69                 n <<= UBIFS_LPT_FANOUT_SHIFT;
  70         }
  71
  72         c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
  73
  74         n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT);
  75         c->nnode_cnt = n;
  76         for (i = 1; i < c->lpt_hght; i++) {
  77                 n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
  78                 c->nnode_cnt += n;
  79         }
  80
  81         c->space_bits = fls(c->leb_size) - 3;
  82         c->lpt_lnum_bits = fls(c->lpt_lebs);
  83         c->lpt_offs_bits = fls(c->leb_size - 1);
  84         c->lpt_spc_bits = fls(c->leb_size);
  85
  86         n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);
  87         c->pcnt_bits = fls(n - 1);
  88
  89         c->lnum_bits = fls(c->max_leb_cnt - 1);
  90
  91         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  92                (c->big_lpt ? c->pcnt_bits : 0) +
  93                (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
  94         c->pnode_sz = (bits + 7) / 8;
  95
  96         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
  97                (c->big_lpt ? c->pcnt_bits : 0) +
  98                (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
  99         c->nnode_sz = (bits + 7) / 8;
 100
 101         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
 102                c->lpt_lebs * c->lpt_spc_bits * 2;
 103         c->ltab_sz = (bits + 7) / 8;
 104
 105         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
 106                c->lnum_bits * c->lsave_cnt;
 107         c->lsave_sz = (bits + 7) / 8;
 108
 109         /* Calculate the minimum LPT size */
 110         c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
 111         c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
 112         c->lpt_sz += c->ltab_sz;
 113         if (c->big_lpt)
 114                 c->lpt_sz += c->lsave_sz;
 115
 116         /* Add wastage */
 117         sz = c->lpt_sz;
 118         per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
 119         sz += per_leb_wastage;
 120         tot_wastage = per_leb_wastage;
 121         while (sz > c->leb_size) {
 122                 sz += per_leb_wastage;
 123                 sz -= c->leb_size;
 124                 tot_wastage += per_leb_wastage;
 125         }
 126         tot_wastage += ALIGN(sz, c->min_io_size) - sz;
 127         c->lpt_sz += tot_wastage;
 128 }
 129
 130 /**
 131  * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
 132  * @c: the UBIFS file-system description object
 133  *
 134  * This function returns %0 on success and a negative error code on failure.
 135  */
 136 int ubifs_calc_lpt_geom(struct ubifs_info *c)
 137 {
 138         int lebs_needed;
 139         long long sz;
 140
 141         do_calc_lpt_geom(c);
 142
 143         /* Verify that lpt_lebs is big enough */
 144         sz = c->lpt_sz * 2; /* Must have at least 2 times the size */
 145         lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
 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         return 0;
 159 }
 160
 161 /**
 162  * ubifs_unpack_bits - unpack bit fields.
 163  * @addr: address at which to unpack (passed and next address returned)
 164  * @pos: bit position at which to unpack (passed and next position returned)
 165  * @nrbits: number of bits of value to unpack (1-32)
 166  *
 167  * This functions returns the value unpacked.
 168  */
 169 uint32_t ubifs_unpack_bits(uint8_t **addr, int *pos, int nrbits)
 170 {
 171         const int k = 32 - nrbits;
 172         uint8_t *p = *addr;
 173         int b = *pos;
 174         uint32_t uninitialized_var(val);
 175         const int bytes = (nrbits + b + 7) >> 3;
 176
 177         ubifs_assert(nrbits > 0);
 178         ubifs_assert(nrbits <= 32);
 179         ubifs_assert(*pos >= 0);
 180         ubifs_assert(*pos < 8);
 181         if (b) {
 182                 switch (bytes) {
 183                 case 2:
 184                         val = p[1];
 185                         break;
 186                 case 3:
 187                         val = p[1] | ((uint32_t)p[2] << 8);
 188                         break;
 189                 case 4:
 190                         val = p[1] | ((uint32_t)p[2] << 8) |
 191                                      ((uint32_t)p[3] << 16);
 192                         break;
 193                 case 5:
 194                         val = p[1] | ((uint32_t)p[2] << 8) |
 195                                      ((uint32_t)p[3] << 16) |
 196                                      ((uint32_t)p[4] << 24);
 197                 }
 198                 val <<= (8 - b);
 199                 val |= *p >> b;
 200                 nrbits += b;
 201         } else {
 202                 switch (bytes) {
 203                 case 1:
 204                         val = p[0];
 205                         break;
 206                 case 2:
 207                         val = p[0] | ((uint32_t)p[1] << 8);
 208                         break;
 209                 case 3:
 210                         val = p[0] | ((uint32_t)p[1] << 8) |
 211                                      ((uint32_t)p[2] << 16);
 212                         break;
 213                 case 4:
 214                         val = p[0] | ((uint32_t)p[1] << 8) |
 215                                      ((uint32_t)p[2] << 16) |
 216                                      ((uint32_t)p[3] << 24);
 217                         break;
 218                 }
 219         }
 220         val <<= k;
 221         val >>= k;
 222         b = nrbits & 7;
 223         p += nrbits >> 3;
 224         *addr = p;
 225         *pos = b;
 226         ubifs_assert((val >> nrbits) == 0 || nrbits - b == 32);
 227         return val;
 228 }
 229
 230 /**
 231  * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
 232  * @c: UBIFS file-system description object
 233  * @lnum: LEB number to which to add dirty space
 234  * @dirty: amount of dirty space to add
 235  */
 236 void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)
 237 {
 238         if (!dirty || !lnum)
 239                 return;
 240         dbg_lp("LEB %d add %d to %d",
 241                lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);
 242         ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
 243         c->ltab[lnum - c->lpt_first].dirty += dirty;
 244 }
 245
 246 /**
 247  * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
 248  * @c: UBIFS file-system description object
 249  * @nnode: nnode for which to add dirt
 250  */
 251 void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)
 252 {
 253         struct ubifs_nnode *np = nnode->parent;
 254
 255         if (np)
 256                 ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,
 257                                    c->nnode_sz);
 258         else {
 259                 ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);
 260                 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
 261                         c->lpt_drty_flgs |= LTAB_DIRTY;
 262                         ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
 263                 }
 264         }
 265 }
 266
 267 /**
 268  * add_pnode_dirt - add dirty space to LPT LEB properties.
 269  * @c: UBIFS file-system description object
 270  * @pnode: pnode for which to add dirt
 271  */
 272 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
 273 {
 274         ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
 275                            c->pnode_sz);
 276 }
 277
 278 /**
 279  * calc_nnode_num_from_parent - calculate nnode number.
 280  * @c: UBIFS file-system description object
 281  * @parent: parent nnode
 282  * @iip: index in parent
 283  *
 284  * The nnode number is a number that uniquely identifies a nnode and can be used
 285  * easily to traverse the tree from the root to that nnode.
 286  *
 287  * This function calculates and returns the nnode number based on the parent's
 288  * nnode number and the index in parent.
 289  */
 290 static int calc_nnode_num_from_parent(const struct ubifs_info *c,
 291                                       struct ubifs_nnode *parent, int iip)
 292 {
 293         int num, shft;
 294
 295         if (!parent)
 296                 return 1;
 297         shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;
 298         num = parent->num ^ (1 << shft);
 299         num |= (UBIFS_LPT_FANOUT + iip) << shft;
 300         return num;
 301 }
 302
 303 /**
 304  * calc_pnode_num_from_parent - calculate pnode number.
 305  * @c: UBIFS file-system description object
 306  * @parent: parent nnode
 307  * @iip: index in parent
 308  *
 309  * The pnode number is a number that uniquely identifies a pnode and can be used
 310  * easily to traverse the tree from the root to that pnode.
 311  *
 312  * This function calculates and returns the pnode number based on the parent's
 313  * nnode number and the index in parent.
 314  */
 315 static int calc_pnode_num_from_parent(const struct ubifs_info *c,
 316                                       struct ubifs_nnode *parent, int iip)
 317 {
 318         int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;
 319
 320         for (i = 0; i < n; i++) {
 321                 num <<= UBIFS_LPT_FANOUT_SHIFT;
 322                 num |= pnum & (UBIFS_LPT_FANOUT - 1);
 323                 pnum >>= UBIFS_LPT_FANOUT_SHIFT;
 324         }
 325         num <<= UBIFS_LPT_FANOUT_SHIFT;
 326         num |= iip;
 327         return num;
 328 }
 329
 330 /**
 331  * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
 332  * @c: UBIFS file-system description object
 333  * @pnode: pnode
 334  *
 335  * When a pnode is loaded into memory, the LEB properties it contains are added,
 336  * by this function, to the LEB category lists and heaps.
 337  */
 338 static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
 339 {
 340         int i;
 341
 342         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 343                 int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
 344                 int lnum = pnode->lprops[i].lnum;
 345
 346                 if (!lnum)
 347                         return;
 348                 ubifs_add_to_cat(c, &pnode->lprops[i], cat);
 349         }
 350 }
 351
 352 /**
 353  * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
 354  * @c: UBIFS file-system description object
 355  * @old_pnode: pnode copied
 356  * @new_pnode: pnode copy
 357  *
 358  * During commit it is sometimes necessary to copy a pnode
 359  * (see dirty_cow_pnode).  When that happens, references in
 360  * category lists and heaps must be replaced.  This function does that.
 361  */
 362 static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
 363                          struct ubifs_pnode *new_pnode)
 364 {
 365         int i;
 366
 367         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 368                 if (!new_pnode->lprops[i].lnum)
 369                         return;
 370                 ubifs_replace_cat(c, &old_pnode->lprops[i],
 371                                   &new_pnode->lprops[i]);
 372         }
 373 }
 374
 375 /**
 376  * check_lpt_crc - check LPT node crc is correct.
 377  * @c: UBIFS file-system description object
 378  * @buf: buffer containing node
 379  * @len: length of node
 380  *
 381  * This function returns %0 on success and a negative error code on failure.
 382  */
 383 static int check_lpt_crc(void *buf, int len)
 384 {
 385         int pos = 0;
 386         uint8_t *addr = buf;
 387         uint16_t crc, calc_crc;
 388
 389         crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
 390         calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
 391                          len - UBIFS_LPT_CRC_BYTES);
 392         if (crc != calc_crc) {
 393                 ubifs_err("invalid crc in LPT node: crc %hx calc %hx", crc,
 394                           calc_crc);
 395                 dbg_dump_stack();
 396                 return -EINVAL;
 397         }
 398         return 0;
 399 }
 400
 401 /**
 402  * check_lpt_type - check LPT node type is correct.
 403  * @c: UBIFS file-system description object
 404  * @addr: address of type bit field is passed and returned updated here
 405  * @pos: position of type bit field is passed and returned updated here
 406  * @type: expected type
 407  *
 408  * This function returns %0 on success and a negative error code on failure.
 409  */
 410 static int check_lpt_type(uint8_t **addr, int *pos, int type)
 411 {
 412         int node_type;
 413
 414         node_type = ubifs_unpack_bits(addr, pos, UBIFS_LPT_TYPE_BITS);
 415         if (node_type != type) {
 416                 ubifs_err("invalid type (%d) in LPT node type %d", node_type,
 417                           type);
 418                 dbg_dump_stack();
 419                 return -EINVAL;
 420         }
 421         return 0;
 422 }
 423
 424 /**
 425  * unpack_pnode - unpack a pnode.
 426  * @c: UBIFS file-system description object
 427  * @buf: buffer containing packed pnode to unpack
 428  * @pnode: pnode structure to fill
 429  *
 430  * This function returns %0 on success and a negative error code on failure.
 431  */
 432 static int unpack_pnode(const struct ubifs_info *c, void *buf,
 433                         struct ubifs_pnode *pnode)
 434 {
 435         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
 436         int i, pos = 0, err;
 437
 438         err = check_lpt_type(&addr, &pos, UBIFS_LPT_PNODE);
 439         if (err)
 440                 return err;
 441         if (c->big_lpt)
 442                 pnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
 443         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 444                 struct ubifs_lprops * const lprops = &pnode->lprops[i];
 445
 446                 lprops->free = ubifs_unpack_bits(&addr, &pos, c->space_bits);
 447                 lprops->free <<= 3;
 448                 lprops->dirty = ubifs_unpack_bits(&addr, &pos, c->space_bits);
 449                 lprops->dirty <<= 3;
 450
 451                 if (ubifs_unpack_bits(&addr, &pos, 1))
 452                         lprops->flags = LPROPS_INDEX;
 453                 else
 454                         lprops->flags = 0;
 455                 lprops->flags |= ubifs_categorize_lprops(c, lprops);
 456         }
 457         err = check_lpt_crc(buf, c->pnode_sz);
 458         return err;
 459 }
 460
 461 /**
 462  * ubifs_unpack_nnode - unpack a nnode.
 463  * @c: UBIFS file-system description object
 464  * @buf: buffer containing packed nnode to unpack
 465  * @nnode: nnode structure to fill
 466  *
 467  * This function returns %0 on success and a negative error code on failure.
 468  */
 469 int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
 470                        struct ubifs_nnode *nnode)
 471 {
 472         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
 473         int i, pos = 0, err;
 474
 475         err = check_lpt_type(&addr, &pos, UBIFS_LPT_NNODE);
 476         if (err)
 477                 return err;
 478         if (c->big_lpt)
 479                 nnode->num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
 480         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 481                 int lnum;
 482
 483                 lnum = ubifs_unpack_bits(&addr, &pos, c->lpt_lnum_bits) +
 484                        c->lpt_first;
 485                 if (lnum == c->lpt_last + 1)
 486                         lnum = 0;
 487                 nnode->nbranch[i].lnum = lnum;
 488                 nnode->nbranch[i].offs = ubifs_unpack_bits(&addr, &pos,
 489                                                      c->lpt_offs_bits);
 490         }
 491         err = check_lpt_crc(buf, c->nnode_sz);
 492         return err;
 493 }
 494
 495 /**
 496  * unpack_ltab - unpack the LPT's own lprops table.
 497  * @c: UBIFS file-system description object
 498  * @buf: buffer from which to unpack
 499  *
 500  * This function returns %0 on success and a negative error code on failure.
 501  */
 502 static int unpack_ltab(const struct ubifs_info *c, void *buf)
 503 {
 504         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
 505         int i, pos = 0, err;
 506
 507         err = check_lpt_type(&addr, &pos, UBIFS_LPT_LTAB);
 508         if (err)
 509                 return err;
 510         for (i = 0; i < c->lpt_lebs; i++) {
 511                 int free = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
 512                 int dirty = ubifs_unpack_bits(&addr, &pos, c->lpt_spc_bits);
 513
 514                 if (free < 0 || free > c->leb_size || dirty < 0 ||
 515                     dirty > c->leb_size || free + dirty > c->leb_size)
 516                         return -EINVAL;
 517
 518                 c->ltab[i].free = free;
 519                 c->ltab[i].dirty = dirty;
 520                 c->ltab[i].tgc = 0;
 521                 c->ltab[i].cmt = 0;
 522         }
 523         err = check_lpt_crc(buf, c->ltab_sz);
 524         return err;
 525 }
 526
 527 /**
 528  * validate_nnode - validate a nnode.
 529  * @c: UBIFS file-system description object
 530  * @nnode: nnode to validate
 531  * @parent: parent nnode (or NULL for the root nnode)
 532  * @iip: index in parent
 533  *
 534  * This function returns %0 on success and a negative error code on failure.
 535  */
 536 static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
 537                           struct ubifs_nnode *parent, int iip)
 538 {
 539         int i, lvl, max_offs;
 540
 541         if (c->big_lpt) {
 542                 int num = calc_nnode_num_from_parent(c, parent, iip);
 543
 544                 if (nnode->num != num)
 545                         return -EINVAL;
 546         }
 547         lvl = parent ? parent->level - 1 : c->lpt_hght;
 548         if (lvl < 1)
 549                 return -EINVAL;
 550         if (lvl == 1)
 551                 max_offs = c->leb_size - c->pnode_sz;
 552         else
 553                 max_offs = c->leb_size - c->nnode_sz;
 554         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 555                 int lnum = nnode->nbranch[i].lnum;
 556                 int offs = nnode->nbranch[i].offs;
 557
 558                 if (lnum == 0) {
 559                         if (offs != 0)
 560                                 return -EINVAL;
 561                         continue;
 562                 }
 563                 if (lnum < c->lpt_first || lnum > c->lpt_last)
 564                         return -EINVAL;
 565                 if (offs < 0 || offs > max_offs)
 566                         return -EINVAL;
 567         }
 568         return 0;
 569 }
 570
 571 /**
 572  * validate_pnode - validate a pnode.
 573  * @c: UBIFS file-system description object
 574  * @pnode: pnode to validate
 575  * @parent: parent nnode
 576  * @iip: index in parent
 577  *
 578  * This function returns %0 on success and a negative error code on failure.
 579  */
 580 static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
 581                           struct ubifs_nnode *parent, int iip)
 582 {
 583         int i;
 584
 585         if (c->big_lpt) {
 586                 int num = calc_pnode_num_from_parent(c, parent, iip);
 587
 588                 if (pnode->num != num)
 589                         return -EINVAL;
 590         }
 591         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 592                 int free = pnode->lprops[i].free;
 593                 int dirty = pnode->lprops[i].dirty;
 594
 595                 if (free < 0 || free > c->leb_size || free % c->min_io_size ||
 596                     (free & 7))
 597                         return -EINVAL;
 598                 if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
 599                         return -EINVAL;
 600                 if (dirty + free > c->leb_size)
 601                         return -EINVAL;
 602         }
 603         return 0;
 604 }
 605
 606 /**
 607  * set_pnode_lnum - set LEB numbers on a pnode.
 608  * @c: UBIFS file-system description object
 609  * @pnode: pnode to update
 610  *
 611  * This function calculates the LEB numbers for the LEB properties it contains
 612  * based on the pnode number.
 613  */
 614 static void set_pnode_lnum(const struct ubifs_info *c,
 615                            struct ubifs_pnode *pnode)
 616 {
 617         int i, lnum;
 618
 619         lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
 620         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 621                 if (lnum >= c->leb_cnt)
 622                         return;
 623                 pnode->lprops[i].lnum = lnum++;
 624         }
 625 }
 626
 627 /**
 628  * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
 629  * @c: UBIFS file-system description object
 630  * @parent: parent nnode (or NULL for the root)
 631  * @iip: index in parent
 632  *
 633  * This function returns %0 on success and a negative error code on failure.
 634  */
 635 int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
 636 {
 637         struct ubifs_nbranch *branch = NULL;
 638         struct ubifs_nnode *nnode = NULL;
 639         void *buf = c->lpt_nod_buf;
 640         int err, lnum, offs;
 641
 642         if (parent) {
 643                 branch = &parent->nbranch[iip];
 644                 lnum = branch->lnum;
 645                 offs = branch->offs;
 646         } else {
 647                 lnum = c->lpt_lnum;
 648                 offs = c->lpt_offs;
 649         }
 650         nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
 651         if (!nnode) {
 652                 err = -ENOMEM;
 653                 goto out;
 654         }
 655         if (lnum == 0) {
 656                 /*
 657                  * This nnode was not written which just means that the LEB
 658                  * properties in the subtree below it describe empty LEBs. We
 659                  * make the nnode as though we had read it, which in fact means
 660                  * doing almost nothing.
 661                  */
 662                 if (c->big_lpt)
 663                         nnode->num = calc_nnode_num_from_parent(c, parent, iip);
 664         } else {
 665                 err = ubi_read(c->ubi, lnum, buf, offs, c->nnode_sz);
 666                 if (err)
 667                         goto out;
 668                 err = ubifs_unpack_nnode(c, buf, nnode);
 669                 if (err)
 670                         goto out;
 671         }
 672         err = validate_nnode(c, nnode, parent, iip);
 673         if (err)
 674                 goto out;
 675         if (!c->big_lpt)
 676                 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
 677         if (parent) {
 678                 branch->nnode = nnode;
 679                 nnode->level = parent->level - 1;
 680         } else {
 681                 c->nroot = nnode;
 682                 nnode->level = c->lpt_hght;
 683         }
 684         nnode->parent = parent;
 685         nnode->iip = iip;
 686         return 0;
 687
 688 out:
 689         ubifs_err("error %d reading nnode at %d:%d", err, lnum, offs);
 690         kfree(nnode);
 691         return err;
 692 }
 693
 694 /**
 695  * read_pnode - read a pnode from flash and link it to the tree in memory.
 696  * @c: UBIFS file-system description object
 697  * @parent: parent nnode
 698  * @iip: index in parent
 699  *
 700  * This function returns %0 on success and a negative error code on failure.
 701  */
 702 static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
 703 {
 704         struct ubifs_nbranch *branch;
 705         struct ubifs_pnode *pnode = NULL;
 706         void *buf = c->lpt_nod_buf;
 707         int err, lnum, offs;
 708
 709         branch = &parent->nbranch[iip];
 710         lnum = branch->lnum;
 711         offs = branch->offs;
 712         pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
 713         if (!pnode) {
 714                 err = -ENOMEM;
 715                 goto out;
 716         }
 717         if (lnum == 0) {
 718                 /*
 719                  * This pnode was not written which just means that the LEB
 720                  * properties in it describe empty LEBs. We make the pnode as
 721                  * though we had read it.
 722                  */
 723                 int i;
 724
 725                 if (c->big_lpt)
 726                         pnode->num = calc_pnode_num_from_parent(c, parent, iip);
 727                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 728                         struct ubifs_lprops * const lprops = &pnode->lprops[i];
 729
 730                         lprops->free = c->leb_size;
 731                         lprops->flags = ubifs_categorize_lprops(c, lprops);
 732                 }
 733         } else {
 734                 err = ubi_read(c->ubi, lnum, buf, offs, c->pnode_sz);
 735                 if (err)
 736                         goto out;
 737                 err = unpack_pnode(c, buf, pnode);
 738                 if (err)
 739                         goto out;
 740         }
 741         err = validate_pnode(c, pnode, parent, iip);
 742         if (err)
 743                 goto out;
 744         if (!c->big_lpt)
 745                 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
 746         branch->pnode = pnode;
 747         pnode->parent = parent;
 748         pnode->iip = iip;
 749         set_pnode_lnum(c, pnode);
 750         c->pnodes_have += 1;
 751         return 0;
 752
 753 out:
 754         ubifs_err("error %d reading pnode at %d:%d", err, lnum, offs);
 755         dbg_dump_pnode(c, pnode, parent, iip);
 756         dbg_msg("calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
 757         kfree(pnode);
 758         return err;
 759 }
 760
 761 /**
 762  * read_ltab - read LPT's own lprops table.
 763  * @c: UBIFS file-system description object
 764  *
 765  * This function returns %0 on success and a negative error code on failure.
 766  */
 767 static int read_ltab(struct ubifs_info *c)
 768 {
 769         int err;
 770         void *buf;
 771
 772         buf = vmalloc(c->ltab_sz);
 773         if (!buf)
 774                 return -ENOMEM;
 775         err = ubi_read(c->ubi, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz);
 776         if (err)
 777                 goto out;
 778         err = unpack_ltab(c, buf);
 779 out:
 780         vfree(buf);
 781         return err;
 782 }
 783
 784 /**
 785  * ubifs_get_nnode - get a nnode.
 786  * @c: UBIFS file-system description object
 787  * @parent: parent nnode (or NULL for the root)
 788  * @iip: index in parent
 789  *
 790  * This function returns a pointer to the nnode on success or a negative error
 791  * code on failure.
 792  */
 793 struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
 794                                     struct ubifs_nnode *parent, int iip)
 795 {
 796         struct ubifs_nbranch *branch;
 797         struct ubifs_nnode *nnode;
 798         int err;
 799
 800         branch = &parent->nbranch[iip];
 801         nnode = branch->nnode;
 802         if (nnode)
 803                 return nnode;
 804         err = ubifs_read_nnode(c, parent, iip);
 805         if (err)
 806                 return ERR_PTR(err);
 807         return branch->nnode;
 808 }
 809
 810 /**
 811  * ubifs_get_pnode - get a pnode.
 812  * @c: UBIFS file-system description object
 813  * @parent: parent nnode
 814  * @iip: index in parent
 815  *
 816  * This function returns a pointer to the pnode on success or a negative error
 817  * code on failure.
 818  */
 819 struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
 820                                     struct ubifs_nnode *parent, int iip)
 821 {
 822         struct ubifs_nbranch *branch;
 823         struct ubifs_pnode *pnode;
 824         int err;
 825
 826         branch = &parent->nbranch[iip];
 827         pnode = branch->pnode;
 828         if (pnode)
 829                 return pnode;
 830         err = read_pnode(c, parent, iip);
 831         if (err)
 832                 return ERR_PTR(err);
 833         update_cats(c, branch->pnode);
 834         return branch->pnode;
 835 }
 836
 837 /**
 838  * ubifs_lpt_lookup - lookup LEB properties in the LPT.
 839  * @c: UBIFS file-system description object
 840  * @lnum: LEB number to lookup
 841  *
 842  * This function returns a pointer to the LEB properties on success or a
 843  * negative error code on failure.
 844  */
 845 struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
 846 {
 847         int err, i, h, iip, shft;
 848         struct ubifs_nnode *nnode;
 849         struct ubifs_pnode *pnode;
 850
 851         if (!c->nroot) {
 852                 err = ubifs_read_nnode(c, NULL, 0);
 853                 if (err)
 854                         return ERR_PTR(err);
 855         }
 856         nnode = c->nroot;
 857         i = lnum - c->main_first;
 858         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
 859         for (h = 1; h < c->lpt_hght; h++) {
 860                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 861                 shft -= UBIFS_LPT_FANOUT_SHIFT;
 862                 nnode = ubifs_get_nnode(c, nnode, iip);
 863                 if (IS_ERR(nnode))
 864                         return ERR_PTR(PTR_ERR(nnode));
 865         }
 866         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 867         shft -= UBIFS_LPT_FANOUT_SHIFT;
 868         pnode = ubifs_get_pnode(c, nnode, iip);
 869         if (IS_ERR(pnode))
 870                 return ERR_PTR(PTR_ERR(pnode));
 871         iip = (i & (UBIFS_LPT_FANOUT - 1));
 872         dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
 873                pnode->lprops[iip].free, pnode->lprops[iip].dirty,
 874                pnode->lprops[iip].flags);
 875         return &pnode->lprops[iip];
 876 }
 877
 878 /**
 879  * dirty_cow_nnode - ensure a nnode is not being committed.
 880  * @c: UBIFS file-system description object
 881  * @nnode: nnode to check
 882  *
 883  * Returns dirtied nnode on success or negative error code on failure.
 884  */
 885 static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
 886                                            struct ubifs_nnode *nnode)
 887 {
 888         struct ubifs_nnode *n;
 889         int i;
 890
 891         if (!test_bit(COW_CNODE, &nnode->flags)) {
 892                 /* nnode is not being committed */
 893                 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 894                         c->dirty_nn_cnt += 1;
 895                         ubifs_add_nnode_dirt(c, nnode);
 896                 }
 897                 return nnode;
 898         }
 899
 900         /* nnode is being committed, so copy it */
 901         n = kmalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
 902         if (unlikely(!n))
 903                 return ERR_PTR(-ENOMEM);
 904
 905         memcpy(n, nnode, sizeof(struct ubifs_nnode));
 906         n->cnext = NULL;
 907         __set_bit(DIRTY_CNODE, &n->flags);
 908         __clear_bit(COW_CNODE, &n->flags);
 909
 910         /* The children now have new parent */
 911         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
 912                 struct ubifs_nbranch *branch = &n->nbranch[i];
 913
 914                 if (branch->cnode)
 915                         branch->cnode->parent = n;
 916         }
 917
 918         ubifs_assert(!test_bit(OBSOLETE_CNODE, &nnode->flags));
 919         __set_bit(OBSOLETE_CNODE, &nnode->flags);
 920
 921         c->dirty_nn_cnt += 1;
 922         ubifs_add_nnode_dirt(c, nnode);
 923         if (nnode->parent)
 924                 nnode->parent->nbranch[n->iip].nnode = n;
 925         else
 926                 c->nroot = n;
 927         return n;
 928 }
 929
 930 /**
 931  * dirty_cow_pnode - ensure a pnode is not being committed.
 932  * @c: UBIFS file-system description object
 933  * @pnode: pnode to check
 934  *
 935  * Returns dirtied pnode on success or negative error code on failure.
 936  */
 937 static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
 938                                            struct ubifs_pnode *pnode)
 939 {
 940         struct ubifs_pnode *p;
 941
 942         if (!test_bit(COW_CNODE, &pnode->flags)) {
 943                 /* pnode is not being committed */
 944                 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
 945                         c->dirty_pn_cnt += 1;
 946                         add_pnode_dirt(c, pnode);
 947                 }
 948                 return pnode;
 949         }
 950
 951         /* pnode is being committed, so copy it */
 952         p = kmalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
 953         if (unlikely(!p))
 954                 return ERR_PTR(-ENOMEM);
 955
 956         memcpy(p, pnode, sizeof(struct ubifs_pnode));
 957         p->cnext = NULL;
 958         __set_bit(DIRTY_CNODE, &p->flags);
 959         __clear_bit(COW_CNODE, &p->flags);
 960         replace_cats(c, pnode, p);
 961
 962         ubifs_assert(!test_bit(OBSOLETE_CNODE, &pnode->flags));
 963         __set_bit(OBSOLETE_CNODE, &pnode->flags);
 964
 965         c->dirty_pn_cnt += 1;
 966         add_pnode_dirt(c, pnode);
 967         pnode->parent->nbranch[p->iip].pnode = p;
 968         return p;
 969 }
 970
 971 /**
 972  * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
 973  * @c: UBIFS file-system description object
 974  * @lnum: LEB number to lookup
 975  *
 976  * This function returns a pointer to the LEB properties on success or a
 977  * negative error code on failure.
 978  */
 979 struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
 980 {
 981         int err, i, h, iip, shft;
 982         struct ubifs_nnode *nnode;
 983         struct ubifs_pnode *pnode;
 984
 985         if (!c->nroot) {
 986                 err = ubifs_read_nnode(c, NULL, 0);
 987                 if (err)
 988                         return ERR_PTR(err);
 989         }
 990         nnode = c->nroot;
 991         nnode = dirty_cow_nnode(c, nnode);
 992         if (IS_ERR(nnode))
 993                 return ERR_PTR(PTR_ERR(nnode));
 994         i = lnum - c->main_first;
 995         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
 996         for (h = 1; h < c->lpt_hght; h++) {
 997                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 998                 shft -= UBIFS_LPT_FANOUT_SHIFT;
 999                 nnode = ubifs_get_nnode(c, nnode, iip);
1000                 if (IS_ERR(nnode))
1001                         return ERR_PTR(PTR_ERR(nnode));
1002                 nnode = dirty_cow_nnode(c, nnode);
1003                 if (IS_ERR(nnode))
1004                         return ERR_PTR(PTR_ERR(nnode));
1005         }
1006         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1007         shft -= UBIFS_LPT_FANOUT_SHIFT;
1008         pnode = ubifs_get_pnode(c, nnode, iip);
1009         if (IS_ERR(pnode))
1010                 return ERR_PTR(PTR_ERR(pnode));
1011         pnode = dirty_cow_pnode(c, pnode);
1012         if (IS_ERR(pnode))
1013                 return ERR_PTR(PTR_ERR(pnode));
1014         iip = (i & (UBIFS_LPT_FANOUT - 1));
1015         dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1016                pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1017                pnode->lprops[iip].flags);
1018         ubifs_assert(test_bit(DIRTY_CNODE, &pnode->flags));
1019         return &pnode->lprops[iip];
1020 }
1021
1022 /**
1023  * lpt_init_rd - initialize the LPT for reading.
1024  * @c: UBIFS file-system description object
1025  *
1026  * This function returns %0 on success and a negative error code on failure.
1027  */
1028 static int lpt_init_rd(struct ubifs_info *c)
1029 {
1030         int err, i;
1031
1032         c->ltab = vmalloc(sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1033         if (!c->ltab)
1034                 return -ENOMEM;
1035
1036         i = max_t(int, c->nnode_sz, c->pnode_sz);
1037         c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
1038         if (!c->lpt_nod_buf)
1039                 return -ENOMEM;
1040
1041         for (i = 0; i < LPROPS_HEAP_CNT; i++) {
1042                 c->lpt_heap[i].arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ,
1043                                              GFP_KERNEL);
1044                 if (!c->lpt_heap[i].arr)
1045                         return -ENOMEM;
1046                 c->lpt_heap[i].cnt = 0;
1047                 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
1048         }
1049
1050         c->dirty_idx.arr = kmalloc(sizeof(void *) * LPT_HEAP_SZ, GFP_KERNEL);
1051         if (!c->dirty_idx.arr)
1052                 return -ENOMEM;
1053         c->dirty_idx.cnt = 0;
1054         c->dirty_idx.max_cnt = LPT_HEAP_SZ;
1055
1056         err = read_ltab(c);
1057         if (err)
1058                 return err;
1059
1060         dbg_lp("space_bits %d", c->space_bits);
1061         dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
1062         dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
1063         dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
1064         dbg_lp("pcnt_bits %d", c->pcnt_bits);
1065         dbg_lp("lnum_bits %d", c->lnum_bits);
1066         dbg_lp("pnode_sz %d", c->pnode_sz);
1067         dbg_lp("nnode_sz %d", c->nnode_sz);
1068         dbg_lp("ltab_sz %d", c->ltab_sz);
1069         dbg_lp("lsave_sz %d", c->lsave_sz);
1070         dbg_lp("lsave_cnt %d", c->lsave_cnt);
1071         dbg_lp("lpt_hght %d", c->lpt_hght);
1072         dbg_lp("big_lpt %d", c->big_lpt);
1073         dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
1074         dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
1075         dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
1076         if (c->big_lpt)
1077                 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
1078
1079         return 0;
1080 }
1081
1082 /**
1083  * ubifs_lpt_init - initialize the LPT.
1084  * @c: UBIFS file-system description object
1085  * @rd: whether to initialize lpt for reading
1086  * @wr: whether to initialize lpt for writing
1087  *
1088  * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
1089  * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
1090  * true.
1091  *
1092  * This function returns %0 on success and a negative error code on failure.
1093  */
1094 int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
1095 {
1096         int err;
1097
1098         if (rd) {
1099                 err = lpt_init_rd(c);
1100                 if (err)
1101                         return err;
1102         }
1103
1104         return 0;
1105 }