uboot/fs/ubifs/lpt.c
<<
>>
Prefs
   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 */
  57static 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 */
 136int 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 */
 169uint32_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 */
 236void 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 */
 251void 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 */
 272static 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 */
 290static 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 */
 315static 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 */
 338static 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 */
 362static 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 */
 383static 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 */
 410static 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 */
 432static 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 */
 469int 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 */
 502static 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 */
 536static 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 */
 580static 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 */
 614static 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 */
 635int 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
 688out:
 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 */
 702static 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
 753out:
 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 */
 767static 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);
 779out:
 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 */
 793struct 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 */
 819struct 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 */
 845struct 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 */
 885static 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 */
 937static 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 */
 979struct 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 */
1028static 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 */
1094int 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}
1106