fs/ubifs/lpt_commit.c

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
first_dirty_cnode
next_dirty_cnode
get_cnodes_to_commit
upd_ltab
alloc_lpt_leb
layout_cnodes
realloc_lpt_leb
write_cnodes
next_pnode_to_dirty
add_pnode_dirt
do_make_pnode_dirty
make_tree_dirty
need_write_all
lpt_tgc_start
lpt_tgc_end
populate_lsave
nnode_lookup
make_nnode_dirty
make_pnode_dirty
make_ltab_dirty
make_lsave_dirty
make_node_dirty
get_lpt_node_len
get_pad_len
get_lpt_node_type
is_a_node
lpt_gc_lnum
lpt_gc
ubifs_lpt_start_commit
free_obsolete_cnodes
ubifs_lpt_end_commit
ubifs_lpt_post_commit
first_nnode
next_nnode
ubifs_lpt_free
dbg_is_all_ff
dbg_is_nnode_dirty
dbg_is_pnode_dirty
dbg_is_ltab_dirty
dbg_is_lsave_dirty
dbg_is_node_dirty
dbg_check_ltab_lnum
dbg_check_ltab
dbg_chk_lpt_free_spc
dbg_chk_lpt_sz
dump_lpt_leb
ubifs_dump_lpt_lebs
dbg_populate_lsave
   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 
  21 static 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  */
  30 static 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  */
  61 static 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  */
  88 static 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  */
 129 static 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  */
 149 static 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  */
 182 static 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 
 310 no_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  */
 333 static 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  */
 360 static 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 
 534 no_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  */
 552 static 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  */
 614 static 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  */
 625 static 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  */
 657 static 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  */
 681 static 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  */
 708 static 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  */
 734 static 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  */
 761 static 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  */
 822 static 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  */
 860 static 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  */
 909 static 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  */
 939 static 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  */
 964 static 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  */
 991 static 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  */
1012 static 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  */
1033 static 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  */
1050 static 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  */
1069 static 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  */
1105 static 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  */
1150 static 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  */
1181 int 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 
1247 out:
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  */
1256 static 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  */
1283 int 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  */
1310 int 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                 }
1326 out:
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  */
1339 static 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  */
1373 static 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  */
1416 void 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  */
1460 static 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  */
1476 static 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  */
1511 static 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  */
1540 static 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  */
1553 static 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  */
1567 static 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  */
1590 static 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;
1650 out:
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  */
1661 int 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  */
1703 int 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  */
1744 int 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  */
1842 static 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);
1934 out:
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  */
1946 void 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  */
1965 static 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 }
/* [<][>][^][v][top][bottom][index][help] */
root/fs/ubifs/lpt_commit.c

DEFINITIONS
