linux/fs/ubifs/lpt_commit.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * This file is part of UBIFS.
   4 *
   5 * Copyright (C) 2006-2008 Nokia Corporation.
   6 *
   7 * Authors: Adrian Hunter
   8 *          Artem Bityutskiy (Битюцкий Артём)
   9 */
  10
  11/*
  12 * This file implements commit-related functionality of the LEB properties
  13 * subsystem.
  14 */
  15
  16#include <linux/crc16.h>
  17#include <linux/slab.h>
  18#include <linux/random.h>
  19#include "ubifs.h"
  20
  21static int dbg_populate_lsave(struct ubifs_info *c);
  22
  23/**
  24 * first_dirty_cnode - find first dirty cnode.
  25 * @c: UBIFS file-system description object
  26 * @nnode: nnode at which to start
  27 *
  28 * This function returns the first dirty cnode or %NULL if there is not one.
  29 */
  30static struct ubifs_cnode *first_dirty_cnode(const struct ubifs_info *c, struct ubifs_nnode *nnode)
  31{
  32        ubifs_assert(c, nnode);
  33        while (1) {
  34                int i, cont = 0;
  35
  36                for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  37                        struct ubifs_cnode *cnode;
  38
  39                        cnode = nnode->nbranch[i].cnode;
  40                        if (cnode &&
  41                            test_bit(DIRTY_CNODE, &cnode->flags)) {
  42                                if (cnode->level == 0)
  43                                        return cnode;
  44                                nnode = (struct ubifs_nnode *)cnode;
  45                                cont = 1;
  46                                break;
  47                        }
  48                }
  49                if (!cont)
  50                        return (struct ubifs_cnode *)nnode;
  51        }
  52}
  53
  54/**
  55 * next_dirty_cnode - find next dirty cnode.
  56 * @c: UBIFS file-system description object
  57 * @cnode: cnode from which to begin searching
  58 *
  59 * This function returns the next dirty cnode or %NULL if there is not one.
  60 */
  61static struct ubifs_cnode *next_dirty_cnode(const struct ubifs_info *c, struct ubifs_cnode *cnode)
  62{
  63        struct ubifs_nnode *nnode;
  64        int i;
  65
  66        ubifs_assert(c, cnode);
  67        nnode = cnode->parent;
  68        if (!nnode)
  69                return NULL;
  70        for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {
  71                cnode = nnode->nbranch[i].cnode;
  72                if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {
  73                        if (cnode->level == 0)
  74                                return cnode; /* cnode is a pnode */
  75                        /* cnode is a nnode */
  76                        return first_dirty_cnode(c, (struct ubifs_nnode *)cnode);
  77                }
  78        }
  79        return (struct ubifs_cnode *)nnode;
  80}
  81
  82/**
  83 * get_cnodes_to_commit - create list of dirty cnodes to commit.
  84 * @c: UBIFS file-system description object
  85 *
  86 * This function returns the number of cnodes to commit.
  87 */
  88static int get_cnodes_to_commit(struct ubifs_info *c)
  89{
  90        struct ubifs_cnode *cnode, *cnext;
  91        int cnt = 0;
  92
  93        if (!c->nroot)
  94                return 0;
  95
  96        if (!test_bit(DIRTY_CNODE, &c->nroot->flags))
  97                return 0;
  98
  99        c->lpt_cnext = first_dirty_cnode(c, c->nroot);
 100        cnode = c->lpt_cnext;
 101        if (!cnode)
 102                return 0;
 103        cnt += 1;
 104        while (1) {
 105                ubifs_assert(c, !test_bit(COW_CNODE, &cnode->flags));
 106                __set_bit(COW_CNODE, &cnode->flags);
 107                cnext = next_dirty_cnode(c, cnode);
 108                if (!cnext) {
 109                        cnode->cnext = c->lpt_cnext;
 110                        break;
 111                }
 112                cnode->cnext = cnext;
 113                cnode = cnext;
 114                cnt += 1;
 115        }
 116        dbg_cmt("committing %d cnodes", cnt);
 117        dbg_lp("committing %d cnodes", cnt);
 118        ubifs_assert(c, cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);
 119        return cnt;
 120}
 121
 122/**
 123 * upd_ltab - update LPT LEB properties.
 124 * @c: UBIFS file-system description object
 125 * @lnum: LEB number
 126 * @free: amount of free space
 127 * @dirty: amount of dirty space to add
 128 */
 129static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
 130{
 131        dbg_lp("LEB %d free %d dirty %d to %d +%d",
 132               lnum, c->ltab[lnum - c->lpt_first].free,
 133               c->ltab[lnum - c->lpt_first].dirty, free, dirty);
 134        ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
 135        c->ltab[lnum - c->lpt_first].free = free;
 136        c->ltab[lnum - c->lpt_first].dirty += dirty;
 137}
 138
 139/**
 140 * alloc_lpt_leb - allocate an LPT LEB that is empty.
 141 * @c: UBIFS file-system description object
 142 * @lnum: LEB number is passed and returned here
 143 *
 144 * This function finds the next empty LEB in the ltab starting from @lnum. If a
 145 * an empty LEB is found it is returned in @lnum and the function returns %0.
 146 * Otherwise the function returns -ENOSPC.  Note however, that LPT is designed
 147 * never to run out of space.
 148 */
 149static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)
 150{
 151        int i, n;
 152
 153        n = *lnum - c->lpt_first + 1;
 154        for (i = n; i < c->lpt_lebs; i++) {
 155                if (c->ltab[i].tgc || c->ltab[i].cmt)
 156                        continue;
 157                if (c->ltab[i].free == c->leb_size) {
 158                        c->ltab[i].cmt = 1;
 159                        *lnum = i + c->lpt_first;
 160                        return 0;
 161                }
 162        }
 163
 164        for (i = 0; i < n; i++) {
 165                if (c->ltab[i].tgc || c->ltab[i].cmt)
 166                        continue;
 167                if (c->ltab[i].free == c->leb_size) {
 168                        c->ltab[i].cmt = 1;
 169                        *lnum = i + c->lpt_first;
 170                        return 0;
 171                }
 172        }
 173        return -ENOSPC;
 174}
 175
 176/**
 177 * layout_cnodes - layout cnodes for commit.
 178 * @c: UBIFS file-system description object
 179 *
 180 * This function returns %0 on success and a negative error code on failure.
 181 */
 182static int layout_cnodes(struct ubifs_info *c)
 183{
 184        int lnum, offs, len, alen, done_lsave, done_ltab, err;
 185        struct ubifs_cnode *cnode;
 186
 187        err = dbg_chk_lpt_sz(c, 0, 0);
 188        if (err)
 189                return err;
 190        cnode = c->lpt_cnext;
 191        if (!cnode)
 192                return 0;
 193        lnum = c->nhead_lnum;
 194        offs = c->nhead_offs;
 195        /* Try to place lsave and ltab nicely */
 196        done_lsave = !c->big_lpt;
 197        done_ltab = 0;
 198        if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
 199                done_lsave = 1;
 200                c->lsave_lnum = lnum;
 201                c->lsave_offs = offs;
 202                offs += c->lsave_sz;
 203                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 204        }
 205
 206        if (offs + c->ltab_sz <= c->leb_size) {
 207                done_ltab = 1;
 208                c->ltab_lnum = lnum;
 209                c->ltab_offs = offs;
 210                offs += c->ltab_sz;
 211                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 212        }
 213
 214        do {
 215                if (cnode->level) {
 216                        len = c->nnode_sz;
 217                        c->dirty_nn_cnt -= 1;
 218                } else {
 219                        len = c->pnode_sz;
 220                        c->dirty_pn_cnt -= 1;
 221                }
 222                while (offs + len > c->leb_size) {
 223                        alen = ALIGN(offs, c->min_io_size);
 224                        upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 225                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 226                        err = alloc_lpt_leb(c, &lnum);
 227                        if (err)
 228                                goto no_space;
 229                        offs = 0;
 230                        ubifs_assert(c, lnum >= c->lpt_first &&
 231                                     lnum <= c->lpt_last);
 232                        /* Try to place lsave and ltab nicely */
 233                        if (!done_lsave) {
 234                                done_lsave = 1;
 235                                c->lsave_lnum = lnum;
 236                                c->lsave_offs = offs;
 237                                offs += c->lsave_sz;
 238                                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 239                                continue;
 240                        }
 241                        if (!done_ltab) {
 242                                done_ltab = 1;
 243                                c->ltab_lnum = lnum;
 244                                c->ltab_offs = offs;
 245                                offs += c->ltab_sz;
 246                                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 247                                continue;
 248                        }
 249                        break;
 250                }
 251                if (cnode->parent) {
 252                        cnode->parent->nbranch[cnode->iip].lnum = lnum;
 253                        cnode->parent->nbranch[cnode->iip].offs = offs;
 254                } else {
 255                        c->lpt_lnum = lnum;
 256                        c->lpt_offs = offs;
 257                }
 258                offs += len;
 259                dbg_chk_lpt_sz(c, 1, len);
 260                cnode = cnode->cnext;
 261        } while (cnode && cnode != c->lpt_cnext);
 262
 263        /* Make sure to place LPT's save table */
 264        if (!done_lsave) {
 265                if (offs + c->lsave_sz > c->leb_size) {
 266                        alen = ALIGN(offs, c->min_io_size);
 267                        upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 268                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 269                        err = alloc_lpt_leb(c, &lnum);
 270                        if (err)
 271                                goto no_space;
 272                        offs = 0;
 273                        ubifs_assert(c, lnum >= c->lpt_first &&
 274                                     lnum <= c->lpt_last);
 275                }
 276                done_lsave = 1;
 277                c->lsave_lnum = lnum;
 278                c->lsave_offs = offs;
 279                offs += c->lsave_sz;
 280                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 281        }
 282
 283        /* Make sure to place LPT's own lprops table */
 284        if (!done_ltab) {
 285                if (offs + c->ltab_sz > c->leb_size) {
 286                        alen = ALIGN(offs, c->min_io_size);
 287                        upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 288                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 289                        err = alloc_lpt_leb(c, &lnum);
 290                        if (err)
 291                                goto no_space;
 292                        offs = 0;
 293                        ubifs_assert(c, lnum >= c->lpt_first &&
 294                                     lnum <= c->lpt_last);
 295                }
 296                c->ltab_lnum = lnum;
 297                c->ltab_offs = offs;
 298                offs += c->ltab_sz;
 299                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 300        }
 301
 302        alen = ALIGN(offs, c->min_io_size);
 303        upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 304        dbg_chk_lpt_sz(c, 4, alen - offs);
 305        err = dbg_chk_lpt_sz(c, 3, alen);
 306        if (err)
 307                return err;
 308        return 0;
 309
 310no_space:
 311        ubifs_err(c, "LPT out of space at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
 312                  lnum, offs, len, done_ltab, done_lsave);
 313        ubifs_dump_lpt_info(c);
 314        ubifs_dump_lpt_lebs(c);
 315        dump_stack();
 316        return err;
 317}
 318
 319/**
 320 * realloc_lpt_leb - allocate an LPT LEB that is empty.
 321 * @c: UBIFS file-system description object
 322 * @lnum: LEB number is passed and returned here
 323 *
 324 * This function duplicates exactly the results of the function alloc_lpt_leb.
 325 * It is used during end commit to reallocate the same LEB numbers that were
 326 * allocated by alloc_lpt_leb during start commit.
 327 *
 328 * This function finds the next LEB that was allocated by the alloc_lpt_leb
 329 * function starting from @lnum. If a LEB is found it is returned in @lnum and
 330 * the function returns %0. Otherwise the function returns -ENOSPC.
 331 * Note however, that LPT is designed never to run out of space.
 332 */
 333static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
 334{
 335        int i, n;
 336
 337        n = *lnum - c->lpt_first + 1;
 338        for (i = n; i < c->lpt_lebs; i++)
 339                if (c->ltab[i].cmt) {
 340                        c->ltab[i].cmt = 0;
 341                        *lnum = i + c->lpt_first;
 342                        return 0;
 343                }
 344
 345        for (i = 0; i < n; i++)
 346                if (c->ltab[i].cmt) {
 347                        c->ltab[i].cmt = 0;
 348                        *lnum = i + c->lpt_first;
 349                        return 0;
 350                }
 351        return -ENOSPC;
 352}
 353
 354/**
 355 * write_cnodes - write cnodes for commit.
 356 * @c: UBIFS file-system description object
 357 *
 358 * This function returns %0 on success and a negative error code on failure.
 359 */
 360static int write_cnodes(struct ubifs_info *c)
 361{
 362        int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
 363        struct ubifs_cnode *cnode;
 364        void *buf = c->lpt_buf;
 365
 366        cnode = c->lpt_cnext;
 367        if (!cnode)
 368                return 0;
 369        lnum = c->nhead_lnum;
 370        offs = c->nhead_offs;
 371        from = offs;
 372        /* Ensure empty LEB is unmapped */
 373        if (offs == 0) {
 374                err = ubifs_leb_unmap(c, lnum);
 375                if (err)
 376                        return err;
 377        }
 378        /* Try to place lsave and ltab nicely */
 379        done_lsave = !c->big_lpt;
 380        done_ltab = 0;
 381        if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
 382                done_lsave = 1;
 383                ubifs_pack_lsave(c, buf + offs, c->lsave);
 384                offs += c->lsave_sz;
 385                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 386        }
 387
 388        if (offs + c->ltab_sz <= c->leb_size) {
 389                done_ltab = 1;
 390                ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 391                offs += c->ltab_sz;
 392                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 393        }
 394
 395        /* Loop for each cnode */
 396        do {
 397                if (cnode->level)
 398                        len = c->nnode_sz;
 399                else
 400                        len = c->pnode_sz;
 401                while (offs + len > c->leb_size) {
 402                        wlen = offs - from;
 403                        if (wlen) {
 404                                alen = ALIGN(wlen, c->min_io_size);
 405                                memset(buf + offs, 0xff, alen - wlen);
 406                                err = ubifs_leb_write(c, lnum, buf + from, from,
 407                                                       alen);
 408                                if (err)
 409                                        return err;
 410                        }
 411                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 412                        err = realloc_lpt_leb(c, &lnum);
 413                        if (err)
 414                                goto no_space;
 415                        offs = from = 0;
 416                        ubifs_assert(c, lnum >= c->lpt_first &&
 417                                     lnum <= c->lpt_last);
 418                        err = ubifs_leb_unmap(c, lnum);
 419                        if (err)
 420                                return err;
 421                        /* Try to place lsave and ltab nicely */
 422                        if (!done_lsave) {
 423                                done_lsave = 1;
 424                                ubifs_pack_lsave(c, buf + offs, c->lsave);
 425                                offs += c->lsave_sz;
 426                                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 427                                continue;
 428                        }
 429                        if (!done_ltab) {
 430                                done_ltab = 1;
 431                                ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 432                                offs += c->ltab_sz;
 433                                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 434                                continue;
 435                        }
 436                        break;
 437                }
 438                if (cnode->level)
 439                        ubifs_pack_nnode(c, buf + offs,
 440                                         (struct ubifs_nnode *)cnode);
 441                else
 442                        ubifs_pack_pnode(c, buf + offs,
 443                                         (struct ubifs_pnode *)cnode);
 444                /*
 445                 * The reason for the barriers is the same as in case of TNC.
 446                 * See comment in 'write_index()'. 'dirty_cow_nnode()' and
 447                 * 'dirty_cow_pnode()' are the functions for which this is
 448                 * important.
 449                 */
 450                clear_bit(DIRTY_CNODE, &cnode->flags);
 451                smp_mb__before_atomic();
 452                clear_bit(COW_CNODE, &cnode->flags);
 453                smp_mb__after_atomic();
 454                offs += len;
 455                dbg_chk_lpt_sz(c, 1, len);
 456                cnode = cnode->cnext;
 457        } while (cnode && cnode != c->lpt_cnext);
 458
 459        /* Make sure to place LPT's save table */
 460        if (!done_lsave) {
 461                if (offs + c->lsave_sz > c->leb_size) {
 462                        wlen = offs - from;
 463                        alen = ALIGN(wlen, c->min_io_size);
 464                        memset(buf + offs, 0xff, alen - wlen);
 465                        err = ubifs_leb_write(c, lnum, buf + from, from, alen);
 466                        if (err)
 467                                return err;
 468                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 469                        err = realloc_lpt_leb(c, &lnum);
 470                        if (err)
 471                                goto no_space;
 472                        offs = from = 0;
 473                        ubifs_assert(c, lnum >= c->lpt_first &&
 474                                     lnum <= c->lpt_last);
 475                        err = ubifs_leb_unmap(c, lnum);
 476                        if (err)
 477                                return err;
 478                }
 479                done_lsave = 1;
 480                ubifs_pack_lsave(c, buf + offs, c->lsave);
 481                offs += c->lsave_sz;
 482                dbg_chk_lpt_sz(c, 1, c->lsave_sz);
 483        }
 484
 485        /* Make sure to place LPT's own lprops table */
 486        if (!done_ltab) {
 487                if (offs + c->ltab_sz > c->leb_size) {
 488                        wlen = offs - from;
 489                        alen = ALIGN(wlen, c->min_io_size);
 490                        memset(buf + offs, 0xff, alen - wlen);
 491                        err = ubifs_leb_write(c, lnum, buf + from, from, alen);
 492                        if (err)
 493                                return err;
 494                        dbg_chk_lpt_sz(c, 2, c->leb_size - offs);
 495                        err = realloc_lpt_leb(c, &lnum);
 496                        if (err)
 497                                goto no_space;
 498                        offs = from = 0;
 499                        ubifs_assert(c, lnum >= c->lpt_first &&
 500                                     lnum <= c->lpt_last);
 501                        err = ubifs_leb_unmap(c, lnum);
 502                        if (err)
 503                                return err;
 504                }
 505                ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 506                offs += c->ltab_sz;
 507                dbg_chk_lpt_sz(c, 1, c->ltab_sz);
 508        }
 509
 510        /* Write remaining data in buffer */
 511        wlen = offs - from;
 512        alen = ALIGN(wlen, c->min_io_size);
 513        memset(buf + offs, 0xff, alen - wlen);
 514        err = ubifs_leb_write(c, lnum, buf + from, from, alen);
 515        if (err)
 516                return err;
 517
 518        dbg_chk_lpt_sz(c, 4, alen - wlen);
 519        err = dbg_chk_lpt_sz(c, 3, ALIGN(offs, c->min_io_size));
 520        if (err)
 521                return err;
 522
 523        c->nhead_lnum = lnum;
 524        c->nhead_offs = ALIGN(offs, c->min_io_size);
 525
 526        dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
 527        dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
 528        dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
 529        if (c->big_lpt)
 530                dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
 531
 532        return 0;
 533
 534no_space:
 535        ubifs_err(c, "LPT out of space mismatch at LEB %d:%d needing %d, done_ltab %d, done_lsave %d",
 536                  lnum, offs, len, done_ltab, done_lsave);
 537        ubifs_dump_lpt_info(c);
 538        ubifs_dump_lpt_lebs(c);
 539        dump_stack();
 540        return err;
 541}
 542
 543/**
 544 * next_pnode_to_dirty - find next pnode to dirty.
 545 * @c: UBIFS file-system description object
 546 * @pnode: pnode
 547 *
 548 * This function returns the next pnode to dirty or %NULL if there are no more
 549 * pnodes.  Note that pnodes that have never been written (lnum == 0) are
 550 * skipped.
 551 */
 552static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c,
 553                                               struct ubifs_pnode *pnode)
 554{
 555        struct ubifs_nnode *nnode;
 556        int iip;
 557
 558        /* Try to go right */
 559        nnode = pnode->parent;
 560        for (iip = pnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
 561                if (nnode->nbranch[iip].lnum)
 562                        return ubifs_get_pnode(c, nnode, iip);
 563        }
 564
 565        /* Go up while can't go right */
 566        do {
 567                iip = nnode->iip + 1;
 568                nnode = nnode->parent;
 569                if (!nnode)
 570                        return NULL;
 571                for (; iip < UBIFS_LPT_FANOUT; iip++) {
 572                        if (nnode->nbranch[iip].lnum)
 573                                break;
 574                }
 575        } while (iip >= UBIFS_LPT_FANOUT);
 576
 577        /* Go right */
 578        nnode = ubifs_get_nnode(c, nnode, iip);
 579        if (IS_ERR(nnode))
 580                return (void *)nnode;
 581
 582        /* Go down to level 1 */
 583        while (nnode->level > 1) {
 584                for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++) {
 585                        if (nnode->nbranch[iip].lnum)
 586                                break;
 587                }
 588                if (iip >= UBIFS_LPT_FANOUT) {
 589                        /*
 590                         * Should not happen, but we need to keep going
 591                         * if it does.
 592                         */
 593                        iip = 0;
 594                }
 595                nnode = ubifs_get_nnode(c, nnode, iip);
 596                if (IS_ERR(nnode))
 597                        return (void *)nnode;
 598        }
 599
 600        for (iip = 0; iip < UBIFS_LPT_FANOUT; iip++)
 601                if (nnode->nbranch[iip].lnum)
 602                        break;
 603        if (iip >= UBIFS_LPT_FANOUT)
 604                /* Should not happen, but we need to keep going if it does */
 605                iip = 0;
 606        return ubifs_get_pnode(c, nnode, iip);
 607}
 608
 609/**
 610 * add_pnode_dirt - add dirty space to LPT LEB properties.
 611 * @c: UBIFS file-system description object
 612 * @pnode: pnode for which to add dirt
 613 */
 614static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
 615{
 616        ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
 617                           c->pnode_sz);
 618}
 619
 620/**
 621 * do_make_pnode_dirty - mark a pnode dirty.
 622 * @c: UBIFS file-system description object
 623 * @pnode: pnode to mark dirty
 624 */
 625static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
 626{
 627        /* Assumes cnext list is empty i.e. not called during commit */
 628        if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
 629                struct ubifs_nnode *nnode;
 630
 631                c->dirty_pn_cnt += 1;
 632                add_pnode_dirt(c, pnode);
 633                /* Mark parent and ancestors dirty too */
 634                nnode = pnode->parent;
 635                while (nnode) {
 636                        if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 637                                c->dirty_nn_cnt += 1;
 638                                ubifs_add_nnode_dirt(c, nnode);
 639                                nnode = nnode->parent;
 640                        } else
 641                                break;
 642                }
 643        }
 644}
 645
 646/**
 647 * make_tree_dirty - mark the entire LEB properties tree dirty.
 648 * @c: UBIFS file-system description object
 649 *
 650 * This function is used by the "small" LPT model to cause the entire LEB
 651 * properties tree to be written.  The "small" LPT model does not use LPT
 652 * garbage collection because it is more efficient to write the entire tree
 653 * (because it is small).
 654 *
 655 * This function returns %0 on success and a negative error code on failure.
 656 */
 657static int make_tree_dirty(struct ubifs_info *c)
 658{
 659        struct ubifs_pnode *pnode;
 660
 661        pnode = ubifs_pnode_lookup(c, 0);
 662        if (IS_ERR(pnode))
 663                return PTR_ERR(pnode);
 664
 665        while (pnode) {
 666                do_make_pnode_dirty(c, pnode);
 667                pnode = next_pnode_to_dirty(c, pnode);
 668                if (IS_ERR(pnode))
 669                        return PTR_ERR(pnode);
 670        }
 671        return 0;
 672}
 673
 674/**
 675 * need_write_all - determine if the LPT area is running out of free space.
 676 * @c: UBIFS file-system description object
 677 *
 678 * This function returns %1 if the LPT area is running out of free space and %0
 679 * if it is not.
 680 */
 681static int need_write_all(struct ubifs_info *c)
 682{
 683        long long free = 0;
 684        int i;
 685
 686        for (i = 0; i < c->lpt_lebs; i++) {
 687                if (i + c->lpt_first == c->nhead_lnum)
 688                        free += c->leb_size - c->nhead_offs;
 689                else if (c->ltab[i].free == c->leb_size)
 690                        free += c->leb_size;
 691                else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
 692                        free += c->leb_size;
 693        }
 694        /* Less than twice the size left */
 695        if (free <= c->lpt_sz * 2)
 696                return 1;
 697        return 0;
 698}
 699
 700/**
 701 * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
 702 * @c: UBIFS file-system description object
 703 *
 704 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 705 * free space and so may be reused as soon as the next commit is completed.
 706 * This function is called during start commit to mark LPT LEBs for trivial GC.
 707 */
 708static void lpt_tgc_start(struct ubifs_info *c)
 709{
 710        int i;
 711
 712        for (i = 0; i < c->lpt_lebs; i++) {
 713                if (i + c->lpt_first == c->nhead_lnum)
 714                        continue;
 715                if (c->ltab[i].dirty > 0 &&
 716                    c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
 717                        c->ltab[i].tgc = 1;
 718                        c->ltab[i].free = c->leb_size;
 719                        c->ltab[i].dirty = 0;
 720                        dbg_lp("LEB %d", i + c->lpt_first);
 721                }
 722        }
 723}
 724
 725/**
 726 * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
 727 * @c: UBIFS file-system description object
 728 *
 729 * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 730 * free space and so may be reused as soon as the next commit is completed.
 731 * This function is called after the commit is completed (master node has been
 732 * written) and un-maps LPT LEBs that were marked for trivial GC.
 733 */
 734static int lpt_tgc_end(struct ubifs_info *c)
 735{
 736        int i, err;
 737
 738        for (i = 0; i < c->lpt_lebs; i++)
 739                if (c->ltab[i].tgc) {
 740                        err = ubifs_leb_unmap(c, i + c->lpt_first);
 741                        if (err)
 742                                return err;
 743                        c->ltab[i].tgc = 0;
 744                        dbg_lp("LEB %d", i + c->lpt_first);
 745                }
 746        return 0;
 747}
 748
 749/**
 750 * populate_lsave - fill the lsave array with important LEB numbers.
 751 * @c: the UBIFS file-system description object
 752 *
 753 * This function is only called for the "big" model. It records a small number
 754 * of LEB numbers of important LEBs.  Important LEBs are ones that are (from
 755 * most important to least important): empty, freeable, freeable index, dirty
 756 * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
 757 * their pnodes into memory.  That will stop us from having to scan the LPT
 758 * straight away. For the "small" model we assume that scanning the LPT is no
 759 * big deal.
 760 */
 761static void populate_lsave(struct ubifs_info *c)
 762{
 763        struct ubifs_lprops *lprops;
 764        struct ubifs_lpt_heap *heap;
 765        int i, cnt = 0;
 766
 767        ubifs_assert(c, c->big_lpt);
 768        if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 769                c->lpt_drty_flgs |= LSAVE_DIRTY;
 770                ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 771        }
 772
 773        if (dbg_populate_lsave(c))
 774                return;
 775
 776        list_for_each_entry(lprops, &c->empty_list, list) {
 777                c->lsave[cnt++] = lprops->lnum;
 778                if (cnt >= c->lsave_cnt)
 779                        return;
 780        }
 781        list_for_each_entry(lprops, &c->freeable_list, list) {
 782                c->lsave[cnt++] = lprops->lnum;
 783                if (cnt >= c->lsave_cnt)
 784                        return;
 785        }
 786        list_for_each_entry(lprops, &c->frdi_idx_list, list) {
 787                c->lsave[cnt++] = lprops->lnum;
 788                if (cnt >= c->lsave_cnt)
 789                        return;
 790        }
 791        heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 792        for (i = 0; i < heap->cnt; i++) {
 793                c->lsave[cnt++] = heap->arr[i]->lnum;
 794                if (cnt >= c->lsave_cnt)
 795                        return;
 796        }
 797        heap = &c->lpt_heap[LPROPS_DIRTY - 1];
 798        for (i = 0; i < heap->cnt; i++) {
 799                c->lsave[cnt++] = heap->arr[i]->lnum;
 800                if (cnt >= c->lsave_cnt)
 801                        return;
 802        }
 803        heap = &c->lpt_heap[LPROPS_FREE - 1];
 804        for (i = 0; i < heap->cnt; i++) {
 805                c->lsave[cnt++] = heap->arr[i]->lnum;
 806                if (cnt >= c->lsave_cnt)
 807                        return;
 808        }
 809        /* Fill it up completely */
 810        while (cnt < c->lsave_cnt)
 811                c->lsave[cnt++] = c->main_first;
 812}
 813
 814/**
 815 * nnode_lookup - lookup a nnode in the LPT.
 816 * @c: UBIFS file-system description object
 817 * @i: nnode number
 818 *
 819 * This function returns a pointer to the nnode on success or a negative
 820 * error code on failure.
 821 */
 822static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
 823{
 824        int err, iip;
 825        struct ubifs_nnode *nnode;
 826
 827        if (!c->nroot) {
 828                err = ubifs_read_nnode(c, NULL, 0);
 829                if (err)
 830                        return ERR_PTR(err);
 831        }
 832        nnode = c->nroot;
 833        while (1) {
 834                iip = i & (UBIFS_LPT_FANOUT - 1);
 835                i >>= UBIFS_LPT_FANOUT_SHIFT;
 836                if (!i)
 837                        break;
 838                nnode = ubifs_get_nnode(c, nnode, iip);
 839                if (IS_ERR(nnode))
 840                        return nnode;
 841        }
 842        return nnode;
 843}
 844
 845/**
 846 * make_nnode_dirty - find a nnode and, if found, make it dirty.
 847 * @c: UBIFS file-system description object
 848 * @node_num: nnode number of nnode to make dirty
 849 * @lnum: LEB number where nnode was written
 850 * @offs: offset where nnode was written
 851 *
 852 * This function is used by LPT garbage collection.  LPT garbage collection is
 853 * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 854 * simply involves marking all the nodes in the LEB being garbage-collected as
 855 * dirty.  The dirty nodes are written next commit, after which the LEB is free
 856 * to be reused.
 857 *
 858 * This function returns %0 on success and a negative error code on failure.
 859 */
 860static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 861                            int offs)
 862{
 863        struct ubifs_nnode *nnode;
 864
 865        nnode = nnode_lookup(c, node_num);
 866        if (IS_ERR(nnode))
 867                return PTR_ERR(nnode);
 868        if (nnode->parent) {
 869                struct ubifs_nbranch *branch;
 870
 871                branch = &nnode->parent->nbranch[nnode->iip];
 872                if (branch->lnum != lnum || branch->offs != offs)
 873                        return 0; /* nnode is obsolete */
 874        } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
 875                        return 0; /* nnode is obsolete */
 876        /* Assumes cnext list is empty i.e. not called during commit */
 877        if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 878                c->dirty_nn_cnt += 1;
 879                ubifs_add_nnode_dirt(c, nnode);
 880                /* Mark parent and ancestors dirty too */
 881                nnode = nnode->parent;
 882                while (nnode) {
 883                        if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 884                                c->dirty_nn_cnt += 1;
 885                                ubifs_add_nnode_dirt(c, nnode);
 886                                nnode = nnode->parent;
 887                        } else
 888                                break;
 889                }
 890        }
 891        return 0;
 892}
 893
 894/**
 895 * make_pnode_dirty - find a pnode and, if found, make it dirty.
 896 * @c: UBIFS file-system description object
 897 * @node_num: pnode number of pnode to make dirty
 898 * @lnum: LEB number where pnode was written
 899 * @offs: offset where pnode was written
 900 *
 901 * This function is used by LPT garbage collection.  LPT garbage collection is
 902 * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 903 * simply involves marking all the nodes in the LEB being garbage-collected as
 904 * dirty.  The dirty nodes are written next commit, after which the LEB is free
 905 * to be reused.
 906 *
 907 * This function returns %0 on success and a negative error code on failure.
 908 */
 909static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 910                            int offs)
 911{
 912        struct ubifs_pnode *pnode;
 913        struct ubifs_nbranch *branch;
 914
 915        pnode = ubifs_pnode_lookup(c, node_num);
 916        if (IS_ERR(pnode))
 917                return PTR_ERR(pnode);
 918        branch = &pnode->parent->nbranch[pnode->iip];
 919        if (branch->lnum != lnum || branch->offs != offs)
 920                return 0;
 921        do_make_pnode_dirty(c, pnode);
 922        return 0;
 923}
 924
 925/**
 926 * make_ltab_dirty - make ltab node dirty.
 927 * @c: UBIFS file-system description object
 928 * @lnum: LEB number where ltab was written
 929 * @offs: offset where ltab was written
 930 *
 931 * This function is used by LPT garbage collection.  LPT garbage collection is
 932 * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 933 * simply involves marking all the nodes in the LEB being garbage-collected as
 934 * dirty.  The dirty nodes are written next commit, after which the LEB is free
 935 * to be reused.
 936 *
 937 * This function returns %0 on success and a negative error code on failure.
 938 */
 939static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
 940{
 941        if (lnum != c->ltab_lnum || offs != c->ltab_offs)
 942                return 0; /* This ltab node is obsolete */
 943        if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
 944                c->lpt_drty_flgs |= LTAB_DIRTY;
 945                ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
 946        }
 947        return 0;
 948}
 949
 950/**
 951 * make_lsave_dirty - make lsave node dirty.
 952 * @c: UBIFS file-system description object
 953 * @lnum: LEB number where lsave was written
 954 * @offs: offset where lsave was written
 955 *
 956 * This function is used by LPT garbage collection.  LPT garbage collection is
 957 * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 958 * simply involves marking all the nodes in the LEB being garbage-collected as
 959 * dirty.  The dirty nodes are written next commit, after which the LEB is free
 960 * to be reused.
 961 *
 962 * This function returns %0 on success and a negative error code on failure.
 963 */
 964static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
 965{
 966        if (lnum != c->lsave_lnum || offs != c->lsave_offs)
 967                return 0; /* This lsave node is obsolete */
 968        if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 969                c->lpt_drty_flgs |= LSAVE_DIRTY;
 970                ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 971        }
 972        return 0;
 973}
 974
 975/**
 976 * make_node_dirty - make node dirty.
 977 * @c: UBIFS file-system description object
 978 * @node_type: LPT node type
 979 * @node_num: node number
 980 * @lnum: LEB number where node was written
 981 * @offs: offset where node was written
 982 *
 983 * This function is used by LPT garbage collection.  LPT garbage collection is
 984 * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 985 * simply involves marking all the nodes in the LEB being garbage-collected as
 986 * dirty.  The dirty nodes are written next commit, after which the LEB is free
 987 * to be reused.
 988 *
 989 * This function returns %0 on success and a negative error code on failure.
 990 */
 991static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
 992                           int lnum, int offs)
 993{
 994        switch (node_type) {
 995        case UBIFS_LPT_NNODE:
 996                return make_nnode_dirty(c, node_num, lnum, offs);
 997        case UBIFS_LPT_PNODE:
 998                return make_pnode_dirty(c, node_num, lnum, offs);
 999        case UBIFS_LPT_LTAB:
1000                return make_ltab_dirty(c, lnum, offs);
1001        case UBIFS_LPT_LSAVE:
1002                return make_lsave_dirty(c, lnum, offs);
1003        }
1004        return -EINVAL;
1005}
1006
1007/**
1008 * get_lpt_node_len - return the length of a node based on its type.
1009 * @c: UBIFS file-system description object
1010 * @node_type: LPT node type
1011 */
1012static int get_lpt_node_len(const struct ubifs_info *c, int node_type)
1013{
1014        switch (node_type) {
1015        case UBIFS_LPT_NNODE:
1016                return c->nnode_sz;
1017        case UBIFS_LPT_PNODE:
1018                return c->pnode_sz;
1019        case UBIFS_LPT_LTAB:
1020                return c->ltab_sz;
1021        case UBIFS_LPT_LSAVE:
1022                return c->lsave_sz;
1023        }
1024        return 0;
1025}
1026
1027/**
1028 * get_pad_len - return the length of padding in a buffer.
1029 * @c: UBIFS file-system description object
1030 * @buf: buffer
1031 * @len: length of buffer
1032 */
1033static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len)
1034{
1035        int offs, pad_len;
1036
1037        if (c->min_io_size == 1)
1038                return 0;
1039        offs = c->leb_size - len;
1040        pad_len = ALIGN(offs, c->min_io_size) - offs;
1041        return pad_len;
1042}
1043
1044/**
1045 * get_lpt_node_type - return type (and node number) of a node in a buffer.
1046 * @c: UBIFS file-system description object
1047 * @buf: buffer
1048 * @node_num: node number is returned here
1049 */
1050static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf,
1051                             int *node_num)
1052{
1053        uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1054        int pos = 0, node_type;
1055
1056        node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);
1057        *node_num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
1058        return node_type;
1059}
1060
1061/**
1062 * is_a_node - determine if a buffer contains a node.
1063 * @c: UBIFS file-system description object
1064 * @buf: buffer
1065 * @len: length of buffer
1066 *
1067 * This function returns %1 if the buffer contains a node or %0 if it does not.
1068 */
1069static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len)
1070{
1071        uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1072        int pos = 0, node_type, node_len;
1073        uint16_t crc, calc_crc;
1074
1075        if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1076                return 0;
1077        node_type = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_TYPE_BITS);
1078        if (node_type == UBIFS_LPT_NOT_A_NODE)
1079                return 0;
1080        node_len = get_lpt_node_len(c, node_type);
1081        if (!node_len || node_len > len)
1082                return 0;
1083        pos = 0;
1084        addr = buf;
1085        crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);
1086        calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1087                         node_len - UBIFS_LPT_CRC_BYTES);
1088        if (crc != calc_crc)
1089                return 0;
1090        return 1;
1091}
1092
1093/**
1094 * lpt_gc_lnum - garbage collect a LPT LEB.
1095 * @c: UBIFS file-system description object
1096 * @lnum: LEB number to garbage collect
1097 *
1098 * LPT garbage collection is used only for the "big" LPT model
1099 * (c->big_lpt == 1).  Garbage collection simply involves marking all the nodes
1100 * in the LEB being garbage-collected as dirty.  The dirty nodes are written
1101 * next commit, after which the LEB is free to be reused.
1102 *
1103 * This function returns %0 on success and a negative error code on failure.
1104 */
1105static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1106{
1107        int err, len = c->leb_size, node_type, node_num, node_len, offs;
1108        void *buf = c->lpt_buf;
1109
1110        dbg_lp("LEB %d", lnum);
1111
1112        err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1113        if (err)
1114                return err;
1115
1116        while (1) {
1117                if (!is_a_node(c, buf, len)) {
1118                        int pad_len;
1119
1120                        pad_len = get_pad_len(c, buf, len);
1121                        if (pad_len) {
1122                                buf += pad_len;
1123                                len -= pad_len;
1124                                continue;
1125                        }
1126                        return 0;
1127                }
1128                node_type = get_lpt_node_type(c, buf, &node_num);
1129                node_len = get_lpt_node_len(c, node_type);
1130                offs = c->leb_size - len;
1131                ubifs_assert(c, node_len != 0);
1132                mutex_lock(&c->lp_mutex);
1133                err = make_node_dirty(c, node_type, node_num, lnum, offs);
1134                mutex_unlock(&c->lp_mutex);
1135                if (err)
1136                        return err;
1137                buf += node_len;
1138                len -= node_len;
1139        }
1140        return 0;
1141}
1142
1143/**
1144 * lpt_gc - LPT garbage collection.
1145 * @c: UBIFS file-system description object
1146 *
1147 * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1148 * Returns %0 on success and a negative error code on failure.
1149 */
1150static int lpt_gc(struct ubifs_info *c)
1151{
1152        int i, lnum = -1, dirty = 0;
1153
1154        mutex_lock(&c->lp_mutex);
1155        for (i = 0; i < c->lpt_lebs; i++) {
1156                ubifs_assert(c, !c->ltab[i].tgc);
1157                if (i + c->lpt_first == c->nhead_lnum ||
1158                    c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1159                        continue;
1160                if (c->ltab[i].dirty > dirty) {
1161                        dirty = c->ltab[i].dirty;
1162                        lnum = i + c->lpt_first;
1163                }
1164        }
1165        mutex_unlock(&c->lp_mutex);
1166        if (lnum == -1)
1167                return -ENOSPC;
1168        return lpt_gc_lnum(c, lnum);
1169}
1170
1171/**
1172 * ubifs_lpt_start_commit - UBIFS commit starts.
1173 * @c: the UBIFS file-system description object
1174 *
1175 * This function has to be called when UBIFS starts the commit operation.
1176 * This function "freezes" all currently dirty LEB properties and does not
1177 * change them anymore. Further changes are saved and tracked separately
1178 * because they are not part of this commit. This function returns zero in case
1179 * of success and a negative error code in case of failure.
1180 */
1181int ubifs_lpt_start_commit(struct ubifs_info *c)
1182{
1183        int err, cnt;
1184
1185        dbg_lp("");
1186
1187        mutex_lock(&c->lp_mutex);
1188        err = dbg_chk_lpt_free_spc(c);
1189        if (err)
1190                goto out;
1191        err = dbg_check_ltab(c);
1192        if (err)
1193                goto out;
1194
1195        if (c->check_lpt_free) {
1196                /*
1197                 * We ensure there is enough free space in
1198                 * ubifs_lpt_post_commit() by marking nodes dirty. That
1199                 * information is lost when we unmount, so we also need
1200                 * to check free space once after mounting also.
1201                 */
1202                c->check_lpt_free = 0;
1203                while (need_write_all(c)) {
1204                        mutex_unlock(&c->lp_mutex);
1205                        err = lpt_gc(c);
1206                        if (err)
1207                                return err;
1208                        mutex_lock(&c->lp_mutex);
1209                }
1210        }
1211
1212        lpt_tgc_start(c);
1213
1214        if (!c->dirty_pn_cnt) {
1215                dbg_cmt("no cnodes to commit");
1216                err = 0;
1217                goto out;
1218        }
1219
1220        if (!c->big_lpt && need_write_all(c)) {
1221                /* If needed, write everything */
1222                err = make_tree_dirty(c);
1223                if (err)
1224                        goto out;
1225                lpt_tgc_start(c);
1226        }
1227
1228        if (c->big_lpt)
1229                populate_lsave(c);
1230
1231        cnt = get_cnodes_to_commit(c);
1232        ubifs_assert(c, cnt != 0);
1233
1234        err = layout_cnodes(c);
1235        if (err)
1236                goto out;
1237
1238        err = ubifs_lpt_calc_hash(c, c->mst_node->hash_lpt);
1239        if (err)
1240                goto out;
1241
1242        /* Copy the LPT's own lprops for end commit to write */
1243        memcpy(c->ltab_cmt, c->ltab,
1244               sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1245        c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1246
1247out:
1248        mutex_unlock(&c->lp_mutex);
1249        return err;
1250}
1251
1252/**
1253 * free_obsolete_cnodes - free obsolete cnodes for commit end.
1254 * @c: UBIFS file-system description object
1255 */
1256static void free_obsolete_cnodes(struct ubifs_info *c)
1257{
1258        struct ubifs_cnode *cnode, *cnext;
1259
1260        cnext = c->lpt_cnext;
1261        if (!cnext)
1262                return;
1263        do {
1264                cnode = cnext;
1265                cnext = cnode->cnext;
1266                if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1267                        kfree(cnode);
1268                else
1269                        cnode->cnext = NULL;
1270        } while (cnext != c->lpt_cnext);
1271        c->lpt_cnext = NULL;
1272}
1273
1274/**
1275 * ubifs_lpt_end_commit - finish the commit operation.
1276 * @c: the UBIFS file-system description object
1277 *
1278 * This function has to be called when the commit operation finishes. It
1279 * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1280 * the media. Returns zero in case of success and a negative error code in case
1281 * of failure.
1282 */
1283int ubifs_lpt_end_commit(struct ubifs_info *c)
1284{
1285        int err;
1286
1287        dbg_lp("");
1288
1289        if (!c->lpt_cnext)
1290                return 0;
1291
1292        err = write_cnodes(c);
1293        if (err)
1294                return err;
1295
1296        mutex_lock(&c->lp_mutex);
1297        free_obsolete_cnodes(c);
1298        mutex_unlock(&c->lp_mutex);
1299
1300        return 0;
1301}
1302
1303/**
1304 * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1305 * @c: UBIFS file-system description object
1306 *
1307 * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1308 * commit for the "big" LPT model.
1309 */
1310int ubifs_lpt_post_commit(struct ubifs_info *c)
1311{
1312        int err;
1313
1314        mutex_lock(&c->lp_mutex);
1315        err = lpt_tgc_end(c);
1316        if (err)
1317                goto out;
1318        if (c->big_lpt)
1319                while (need_write_all(c)) {
1320                        mutex_unlock(&c->lp_mutex);
1321                        err = lpt_gc(c);
1322                        if (err)
1323                                return err;
1324                        mutex_lock(&c->lp_mutex);
1325                }
1326out:
1327        mutex_unlock(&c->lp_mutex);
1328        return err;
1329}
1330
1331/**
1332 * first_nnode - find the first nnode in memory.
1333 * @c: UBIFS file-system description object
1334 * @hght: height of tree where nnode found is returned here
1335 *
1336 * This function returns a pointer to the nnode found or %NULL if no nnode is
1337 * found. This function is a helper to 'ubifs_lpt_free()'.
1338 */
1339static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1340{
1341        struct ubifs_nnode *nnode;
1342        int h, i, found;
1343
1344        nnode = c->nroot;
1345        *hght = 0;
1346        if (!nnode)
1347                return NULL;
1348        for (h = 1; h < c->lpt_hght; h++) {
1349                found = 0;
1350                for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1351                        if (nnode->nbranch[i].nnode) {
1352                                found = 1;
1353                                nnode = nnode->nbranch[i].nnode;
1354                                *hght = h;
1355                                break;
1356                        }
1357                }
1358                if (!found)
1359                        break;
1360        }
1361        return nnode;
1362}
1363
1364/**
1365 * next_nnode - find the next nnode in memory.
1366 * @c: UBIFS file-system description object
1367 * @nnode: nnode from which to start.
1368 * @hght: height of tree where nnode is, is passed and returned here
1369 *
1370 * This function returns a pointer to the nnode found or %NULL if no nnode is
1371 * found. This function is a helper to 'ubifs_lpt_free()'.
1372 */
1373static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1374                                      struct ubifs_nnode *nnode, int *hght)
1375{
1376        struct ubifs_nnode *parent;
1377        int iip, h, i, found;
1378
1379        parent = nnode->parent;
1380        if (!parent)
1381                return NULL;
1382        if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1383                *hght -= 1;
1384                return parent;
1385        }
1386        for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1387                nnode = parent->nbranch[iip].nnode;
1388                if (nnode)
1389                        break;
1390        }
1391        if (!nnode) {
1392                *hght -= 1;
1393                return parent;
1394        }
1395        for (h = *hght + 1; h < c->lpt_hght; h++) {
1396                found = 0;
1397                for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1398                        if (nnode->nbranch[i].nnode) {
1399                                found = 1;
1400                                nnode = nnode->nbranch[i].nnode;
1401                                *hght = h;
1402                                break;
1403                        }
1404                }
1405                if (!found)
1406                        break;
1407        }
1408        return nnode;
1409}
1410
1411/**
1412 * ubifs_lpt_free - free resources owned by the LPT.
1413 * @c: UBIFS file-system description object
1414 * @wr_only: free only resources used for writing
1415 */
1416void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1417{
1418        struct ubifs_nnode *nnode;
1419        int i, hght;
1420
1421        /* Free write-only things first */
1422
1423        free_obsolete_cnodes(c); /* Leftover from a failed commit */
1424
1425        vfree(c->ltab_cmt);
1426        c->ltab_cmt = NULL;
1427        vfree(c->lpt_buf);
1428        c->lpt_buf = NULL;
1429        kfree(c->lsave);
1430        c->lsave = NULL;
1431
1432        if (wr_only)
1433                return;
1434
1435        /* Now free the rest */
1436
1437        nnode = first_nnode(c, &hght);
1438        while (nnode) {
1439                for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1440                        kfree(nnode->nbranch[i].nnode);
1441                nnode = next_nnode(c, nnode, &hght);
1442        }
1443        for (i = 0; i < LPROPS_HEAP_CNT; i++)
1444                kfree(c->lpt_heap[i].arr);
1445        kfree(c->dirty_idx.arr);
1446        kfree(c->nroot);
1447        vfree(c->ltab);
1448        kfree(c->lpt_nod_buf);
1449}
1450
1451/*
1452 * Everything below is related to debugging.
1453 */
1454
1455/**
1456 * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes.
1457 * @buf: buffer
1458 * @len: buffer length
1459 */
1460static int dbg_is_all_ff(uint8_t *buf, int len)
1461{
1462        int i;
1463
1464        for (i = 0; i < len; i++)
1465                if (buf[i] != 0xff)
1466                        return 0;
1467        return 1;
1468}
1469
1470/**
1471 * dbg_is_nnode_dirty - determine if a nnode is dirty.
1472 * @c: the UBIFS file-system description object
1473 * @lnum: LEB number where nnode was written
1474 * @offs: offset where nnode was written
1475 */
1476static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1477{
1478        struct ubifs_nnode *nnode;
1479        int hght;
1480
1481        /* Entire tree is in memory so first_nnode / next_nnode are OK */
1482        nnode = first_nnode(c, &hght);
1483        for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1484                struct ubifs_nbranch *branch;
1485
1486                cond_resched();
1487                if (nnode->parent) {
1488                        branch = &nnode->parent->nbranch[nnode->iip];
1489                        if (branch->lnum != lnum || branch->offs != offs)
1490                                continue;
1491                        if (test_bit(DIRTY_CNODE, &nnode->flags))
1492                                return 1;
1493                        return 0;
1494                } else {
1495                        if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1496                                continue;
1497                        if (test_bit(DIRTY_CNODE, &nnode->flags))
1498                                return 1;
1499                        return 0;
1500                }
1501        }
1502        return 1;
1503}
1504
1505/**
1506 * dbg_is_pnode_dirty - determine if a pnode is dirty.
1507 * @c: the UBIFS file-system description object
1508 * @lnum: LEB number where pnode was written
1509 * @offs: offset where pnode was written
1510 */
1511static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1512{
1513        int i, cnt;
1514
1515        cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1516        for (i = 0; i < cnt; i++) {
1517                struct ubifs_pnode *pnode;
1518                struct ubifs_nbranch *branch;
1519
1520                cond_resched();
1521                pnode = ubifs_pnode_lookup(c, i);
1522                if (IS_ERR(pnode))
1523                        return PTR_ERR(pnode);
1524                branch = &pnode->parent->nbranch[pnode->iip];
1525                if (branch->lnum != lnum || branch->offs != offs)
1526                        continue;
1527                if (test_bit(DIRTY_CNODE, &pnode->flags))
1528                        return 1;
1529                return 0;
1530        }
1531        return 1;
1532}
1533
1534/**
1535 * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1536 * @c: the UBIFS file-system description object
1537 * @lnum: LEB number where ltab node was written
1538 * @offs: offset where ltab node was written
1539 */
1540static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1541{
1542        if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1543                return 1;
1544        return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1545}
1546
1547/**
1548 * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1549 * @c: the UBIFS file-system description object
1550 * @lnum: LEB number where lsave node was written
1551 * @offs: offset where lsave node was written
1552 */
1553static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1554{
1555        if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1556                return 1;
1557        return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1558}
1559
1560/**
1561 * dbg_is_node_dirty - determine if a node is dirty.
1562 * @c: the UBIFS file-system description object
1563 * @node_type: node type
1564 * @lnum: LEB number where node was written
1565 * @offs: offset where node was written
1566 */
1567static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1568                             int offs)
1569{
1570        switch (node_type) {
1571        case UBIFS_LPT_NNODE:
1572                return dbg_is_nnode_dirty(c, lnum, offs);
1573        case UBIFS_LPT_PNODE:
1574                return dbg_is_pnode_dirty(c, lnum, offs);
1575        case UBIFS_LPT_LTAB:
1576                return dbg_is_ltab_dirty(c, lnum, offs);
1577        case UBIFS_LPT_LSAVE:
1578                return dbg_is_lsave_dirty(c, lnum, offs);
1579        }
1580        return 1;
1581}
1582
1583/**
1584 * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1585 * @c: the UBIFS file-system description object
1586 * @lnum: LEB number where node was written
1587 *
1588 * This function returns %0 on success and a negative error code on failure.
1589 */
1590static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1591{
1592        int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1593        int ret;
1594        void *buf, *p;
1595
1596        if (!dbg_is_chk_lprops(c))
1597                return 0;
1598
1599        buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
1600        if (!buf) {
1601                ubifs_err(c, "cannot allocate memory for ltab checking");
1602                return 0;
1603        }
1604
1605        dbg_lp("LEB %d", lnum);
1606
1607        err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1608        if (err)
1609                goto out;
1610
1611        while (1) {
1612                if (!is_a_node(c, p, len)) {
1613                        int i, pad_len;
1614
1615                        pad_len = get_pad_len(c, p, len);
1616                        if (pad_len) {
1617                                p += pad_len;
1618                                len -= pad_len;
1619                                dirty += pad_len;
1620                                continue;
1621                        }
1622                        if (!dbg_is_all_ff(p, len)) {
1623                                ubifs_err(c, "invalid empty space in LEB %d at %d",
1624                                          lnum, c->leb_size - len);
1625                                err = -EINVAL;
1626                        }
1627                        i = lnum - c->lpt_first;
1628                        if (len != c->ltab[i].free) {
1629                                ubifs_err(c, "invalid free space in LEB %d (free %d, expected %d)",
1630                                          lnum, len, c->ltab[i].free);
1631                                err = -EINVAL;
1632                        }
1633                        if (dirty != c->ltab[i].dirty) {
1634                                ubifs_err(c, "invalid dirty space in LEB %d (dirty %d, expected %d)",
1635                                          lnum, dirty, c->ltab[i].dirty);
1636                                err = -EINVAL;
1637                        }
1638                        goto out;
1639                }
1640                node_type = get_lpt_node_type(c, p, &node_num);
1641                node_len = get_lpt_node_len(c, node_type);
1642                ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1643                if (ret == 1)
1644                        dirty += node_len;
1645                p += node_len;
1646                len -= node_len;
1647        }
1648
1649        err = 0;
1650out:
1651        vfree(buf);
1652        return err;
1653}
1654
1655/**
1656 * dbg_check_ltab - check the free and dirty space in the ltab.
1657 * @c: the UBIFS file-system description object
1658 *
1659 * This function returns %0 on success and a negative error code on failure.
1660 */
1661int dbg_check_ltab(struct ubifs_info *c)
1662{
1663        int lnum, err, i, cnt;
1664
1665        if (!dbg_is_chk_lprops(c))
1666                return 0;
1667
1668        /* Bring the entire tree into memory */
1669        cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1670        for (i = 0; i < cnt; i++) {
1671                struct ubifs_pnode *pnode;
1672
1673                pnode = ubifs_pnode_lookup(c, i);
1674                if (IS_ERR(pnode))
1675                        return PTR_ERR(pnode);
1676                cond_resched();
1677        }
1678
1679        /* Check nodes */
1680        err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1681        if (err)
1682                return err;
1683
1684        /* Check each LEB */
1685        for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1686                err = dbg_check_ltab_lnum(c, lnum);
1687                if (err) {
1688                        ubifs_err(c, "failed at LEB %d", lnum);
1689                        return err;
1690                }
1691        }
1692
1693        dbg_lp("succeeded");
1694        return 0;
1695}
1696
1697/**
1698 * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1699 * @c: the UBIFS file-system description object
1700 *
1701 * This function returns %0 on success and a negative error code on failure.
1702 */
1703int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1704{
1705        long long free = 0;
1706        int i;
1707
1708        if (!dbg_is_chk_lprops(c))
1709                return 0;
1710
1711        for (i = 0; i < c->lpt_lebs; i++) {
1712                if (c->ltab[i].tgc || c->ltab[i].cmt)
1713                        continue;
1714                if (i + c->lpt_first == c->nhead_lnum)
1715                        free += c->leb_size - c->nhead_offs;
1716                else if (c->ltab[i].free == c->leb_size)
1717                        free += c->leb_size;
1718        }
1719        if (free < c->lpt_sz) {
1720                ubifs_err(c, "LPT space error: free %lld lpt_sz %lld",
1721                          free, c->lpt_sz);
1722                ubifs_dump_lpt_info(c);
1723                ubifs_dump_lpt_lebs(c);
1724                dump_stack();
1725                return -EINVAL;
1726        }
1727        return 0;
1728}
1729
1730/**
1731 * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1732 * @c: the UBIFS file-system description object
1733 * @action: what to do
1734 * @len: length written
1735 *
1736 * This function returns %0 on success and a negative error code on failure.
1737 * The @action argument may be one of:
1738 *   o %0 - LPT debugging checking starts, initialize debugging variables;
1739 *   o %1 - wrote an LPT node, increase LPT size by @len bytes;
1740 *   o %2 - switched to a different LEB and wasted @len bytes;
1741 *   o %3 - check that we've written the right number of bytes.
1742 *   o %4 - wasted @len bytes;
1743 */
1744int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1745{
1746        struct ubifs_debug_info *d = c->dbg;
1747        long long chk_lpt_sz, lpt_sz;
1748        int err = 0;
1749
1750        if (!dbg_is_chk_lprops(c))
1751                return 0;
1752
1753        switch (action) {
1754        case 0:
1755                d->chk_lpt_sz = 0;
1756                d->chk_lpt_sz2 = 0;
1757                d->chk_lpt_lebs = 0;
1758                d->chk_lpt_wastage = 0;
1759                if (c->dirty_pn_cnt > c->pnode_cnt) {
1760                        ubifs_err(c, "dirty pnodes %d exceed max %d",
1761                                  c->dirty_pn_cnt, c->pnode_cnt);
1762                        err = -EINVAL;
1763                }
1764                if (c->dirty_nn_cnt > c->nnode_cnt) {
1765                        ubifs_err(c, "dirty nnodes %d exceed max %d",
1766                                  c->dirty_nn_cnt, c->nnode_cnt);
1767                        err = -EINVAL;
1768                }
1769                return err;
1770        case 1:
1771                d->chk_lpt_sz += len;
1772                return 0;
1773        case 2:
1774                d->chk_lpt_sz += len;
1775                d->chk_lpt_wastage += len;
1776                d->chk_lpt_lebs += 1;
1777                return 0;
1778        case 3:
1779                chk_lpt_sz = c->leb_size;
1780                chk_lpt_sz *= d->chk_lpt_lebs;
1781                chk_lpt_sz += len - c->nhead_offs;
1782                if (d->chk_lpt_sz != chk_lpt_sz) {
1783                        ubifs_err(c, "LPT wrote %lld but space used was %lld",
1784                                  d->chk_lpt_sz, chk_lpt_sz);
1785                        err = -EINVAL;
1786                }
1787                if (d->chk_lpt_sz > c->lpt_sz) {
1788                        ubifs_err(c, "LPT wrote %lld but lpt_sz is %lld",
1789                                  d->chk_lpt_sz, c->lpt_sz);
1790                        err = -EINVAL;
1791                }
1792                if (d->chk_lpt_sz2 && d->chk_lpt_sz != d->chk_lpt_sz2) {
1793                        ubifs_err(c, "LPT layout size %lld but wrote %lld",
1794                                  d->chk_lpt_sz, d->chk_lpt_sz2);
1795                        err = -EINVAL;
1796                }
1797                if (d->chk_lpt_sz2 && d->new_nhead_offs != len) {
1798                        ubifs_err(c, "LPT new nhead offs: expected %d was %d",
1799                                  d->new_nhead_offs, len);
1800                        err = -EINVAL;
1801                }
1802                lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1803                lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1804                lpt_sz += c->ltab_sz;
1805                if (c->big_lpt)
1806                        lpt_sz += c->lsave_sz;
1807                if (d->chk_lpt_sz - d->chk_lpt_wastage > lpt_sz) {
1808                        ubifs_err(c, "LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1809                                  d->chk_lpt_sz, d->chk_lpt_wastage, lpt_sz);
1810                        err = -EINVAL;
1811                }
1812                if (err) {
1813                        ubifs_dump_lpt_info(c);
1814                        ubifs_dump_lpt_lebs(c);
1815                        dump_stack();
1816                }
1817                d->chk_lpt_sz2 = d->chk_lpt_sz;
1818                d->chk_lpt_sz = 0;
1819                d->chk_lpt_wastage = 0;
1820                d->chk_lpt_lebs = 0;
1821                d->new_nhead_offs = len;
1822                return err;
1823        case 4:
1824                d->chk_lpt_sz += len;
1825                d->chk_lpt_wastage += len;
1826                return 0;
1827        default:
1828                return -EINVAL;
1829        }
1830}
1831
1832/**
1833 * dump_lpt_leb - dump an LPT LEB.
1834 * @c: UBIFS file-system description object
1835 * @lnum: LEB number to dump
1836 *
1837 * This function dumps an LEB from LPT area. Nodes in this area are very
1838 * different to nodes in the main area (e.g., they do not have common headers,
1839 * they do not have 8-byte alignments, etc), so we have a separate function to
1840 * dump LPT area LEBs. Note, LPT has to be locked by the caller.
1841 */
1842static void dump_lpt_leb(const struct ubifs_info *c, int lnum)
1843{
1844        int err, len = c->leb_size, node_type, node_num, node_len, offs;
1845        void *buf, *p;
1846
1847        pr_err("(pid %d) start dumping LEB %d\n", current->pid, lnum);
1848        buf = p = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL);
1849        if (!buf) {
1850                ubifs_err(c, "cannot allocate memory to dump LPT");
1851                return;
1852        }
1853
1854        err = ubifs_leb_read(c, lnum, buf, 0, c->leb_size, 1);
1855        if (err)
1856                goto out;
1857
1858        while (1) {
1859                offs = c->leb_size - len;
1860                if (!is_a_node(c, p, len)) {
1861                        int pad_len;
1862
1863                        pad_len = get_pad_len(c, p, len);
1864                        if (pad_len) {
1865                                pr_err("LEB %d:%d, pad %d bytes\n",
1866                                       lnum, offs, pad_len);
1867                                p += pad_len;
1868                                len -= pad_len;
1869                                continue;
1870                        }
1871                        if (len)
1872                                pr_err("LEB %d:%d, free %d bytes\n",
1873                                       lnum, offs, len);
1874                        break;
1875                }
1876
1877                node_type = get_lpt_node_type(c, p, &node_num);
1878                switch (node_type) {
1879                case UBIFS_LPT_PNODE:
1880                {
1881                        node_len = c->pnode_sz;
1882                        if (c->big_lpt)
1883                                pr_err("LEB %d:%d, pnode num %d\n",
1884                                       lnum, offs, node_num);
1885                        else
1886                                pr_err("LEB %d:%d, pnode\n", lnum, offs);
1887                        break;
1888                }
1889                case UBIFS_LPT_NNODE:
1890                {
1891                        int i;
1892                        struct ubifs_nnode nnode;
1893
1894                        node_len = c->nnode_sz;
1895                        if (c->big_lpt)
1896                                pr_err("LEB %d:%d, nnode num %d, ",
1897                                       lnum, offs, node_num);
1898                        else
1899                                pr_err("LEB %d:%d, nnode, ",
1900                                       lnum, offs);
1901                        err = ubifs_unpack_nnode(c, p, &nnode);
1902                        if (err) {
1903                                pr_err("failed to unpack_node, error %d\n",
1904                                       err);
1905                                break;
1906                        }
1907                        for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1908                                pr_cont("%d:%d", nnode.nbranch[i].lnum,
1909                                       nnode.nbranch[i].offs);
1910                                if (i != UBIFS_LPT_FANOUT - 1)
1911                                        pr_cont(", ");
1912                        }
1913                        pr_cont("\n");
1914                        break;
1915                }
1916                case UBIFS_LPT_LTAB:
1917                        node_len = c->ltab_sz;
1918                        pr_err("LEB %d:%d, ltab\n", lnum, offs);
1919                        break;
1920                case UBIFS_LPT_LSAVE:
1921                        node_len = c->lsave_sz;
1922                        pr_err("LEB %d:%d, lsave len\n", lnum, offs);
1923                        break;
1924                default:
1925                        ubifs_err(c, "LPT node type %d not recognized", node_type);
1926                        goto out;
1927                }
1928
1929                p += node_len;
1930                len -= node_len;
1931        }
1932
1933        pr_err("(pid %d) finish dumping LEB %d\n", current->pid, lnum);
1934out:
1935        vfree(buf);
1936        return;
1937}
1938
1939/**
1940 * ubifs_dump_lpt_lebs - dump LPT lebs.
1941 * @c: UBIFS file-system description object
1942 *
1943 * This function dumps all LPT LEBs. The caller has to make sure the LPT is
1944 * locked.
1945 */
1946void ubifs_dump_lpt_lebs(const struct ubifs_info *c)
1947{
1948        int i;
1949
1950        pr_err("(pid %d) start dumping all LPT LEBs\n", current->pid);
1951        for (i = 0; i < c->lpt_lebs; i++)
1952                dump_lpt_leb(c, i + c->lpt_first);
1953        pr_err("(pid %d) finish dumping all LPT LEBs\n", current->pid);
1954}
1955
1956/**
1957 * dbg_populate_lsave - debugging version of 'populate_lsave()'
1958 * @c: UBIFS file-system description object
1959 *
1960 * This is a debugging version for 'populate_lsave()' which populates lsave
1961 * with random LEBs instead of useful LEBs, which is good for test coverage.
1962 * Returns zero if lsave has not been populated (this debugging feature is
1963 * disabled) an non-zero if lsave has been populated.
1964 */
1965static int dbg_populate_lsave(struct ubifs_info *c)
1966{
1967        struct ubifs_lprops *lprops;
1968        struct ubifs_lpt_heap *heap;
1969        int i;
1970
1971        if (!dbg_is_chk_gen(c))
1972                return 0;
1973        if (prandom_u32() & 3)
1974                return 0;
1975
1976        for (i = 0; i < c->lsave_cnt; i++)
1977                c->lsave[i] = c->main_first;
1978
1979        list_for_each_entry(lprops, &c->empty_list, list)
1980                c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1981        list_for_each_entry(lprops, &c->freeable_list, list)
1982                c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1983        list_for_each_entry(lprops, &c->frdi_idx_list, list)
1984                c->lsave[prandom_u32() % c->lsave_cnt] = lprops->lnum;
1985
1986        heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
1987        for (i = 0; i < heap->cnt; i++)
1988                c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1989        heap = &c->lpt_heap[LPROPS_DIRTY - 1];
1990        for (i = 0; i < heap->cnt; i++)
1991                c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1992        heap = &c->lpt_heap[LPROPS_FREE - 1];
1993        for (i = 0; i < heap->cnt; i++)
1994                c->lsave[prandom_u32() % c->lsave_cnt] = heap->arr[i]->lnum;
1995
1996        return 1;
1997}
1998