fs/ubifs/lpt_commit.c

   1 /*
   2  * This file is part of UBIFS.
   3  *
   4  * Copyright (C) 2006-2008 Nokia Corporation.
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License version 2 as published by
   8  * the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  13  * more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along with
  16  * this program; if not, write to the Free Software Foundation, Inc., 51
  17  * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18  *
  19  * Authors: Adrian Hunter
  20  *          Artem Bityutskiy (Битюцкий Артём)
  21  */
  22
  23 /*
  24  * This file implements commit-related functionality of the LEB properties
  25  * subsystem.
  26  */
  27
  28 #include <linux/crc16.h>
  29 #include "ubifs.h"
  30
  31 /**
  32  * first_dirty_cnode - find first dirty cnode.
  33  * @c: UBIFS file-system description object
  34  * @nnode: nnode at which to start
  35  *
  36  * This function returns the first dirty cnode or %NULL if there is not one.
  37  */
  38 static struct ubifs_cnode *first_dirty_cnode(struct ubifs_nnode *nnode)
  39 {
  40         ubifs_assert(nnode);
  41         while (1) {
  42                 int i, cont = 0;
  43
  44                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
  45                         struct ubifs_cnode *cnode;
  46
  47                         cnode = nnode->nbranch[i].cnode;
  48                         if (cnode &&
  49                             test_bit(DIRTY_CNODE, &cnode->flags)) {
  50                                 if (cnode->level == 0)
  51                                         return cnode;
  52                                 nnode = (struct ubifs_nnode *)cnode;
  53                                 cont = 1;
  54                                 break;
  55                         }
  56                 }
  57                 if (!cont)
  58                         return (struct ubifs_cnode *)nnode;
  59         }
  60 }
  61
  62 /**
  63  * next_dirty_cnode - find next dirty cnode.
  64  * @cnode: cnode from which to begin searching
  65  *
  66  * This function returns the next dirty cnode or %NULL if there is not one.
  67  */
  68 static struct ubifs_cnode *next_dirty_cnode(struct ubifs_cnode *cnode)
  69 {
  70         struct ubifs_nnode *nnode;
  71         int i;
  72
  73         ubifs_assert(cnode);
  74         nnode = cnode->parent;
  75         if (!nnode)
  76                 return NULL;
  77         for (i = cnode->iip + 1; i < UBIFS_LPT_FANOUT; i++) {
  78                 cnode = nnode->nbranch[i].cnode;
  79                 if (cnode && test_bit(DIRTY_CNODE, &cnode->flags)) {
  80                         if (cnode->level == 0)
  81                                 return cnode; /* cnode is a pnode */
  82                         /* cnode is a nnode */
  83                         return first_dirty_cnode((struct ubifs_nnode *)cnode);
  84                 }
  85         }
  86         return (struct ubifs_cnode *)nnode;
  87 }
  88
  89 /**
  90  * get_cnodes_to_commit - create list of dirty cnodes to commit.
  91  * @c: UBIFS file-system description object
  92  *
  93  * This function returns the number of cnodes to commit.
  94  */
  95 static int get_cnodes_to_commit(struct ubifs_info *c)
  96 {
  97         struct ubifs_cnode *cnode, *cnext;
  98         int cnt = 0;
  99
 100         if (!c->nroot)
 101                 return 0;
 102
 103         if (!test_bit(DIRTY_CNODE, &c->nroot->flags))
 104                 return 0;
 105
 106         c->lpt_cnext = first_dirty_cnode(c->nroot);
 107         cnode = c->lpt_cnext;
 108         if (!cnode)
 109                 return 0;
 110         cnt += 1;
 111         while (1) {
 112                 ubifs_assert(!test_bit(COW_ZNODE, &cnode->flags));
 113                 __set_bit(COW_ZNODE, &cnode->flags);
 114                 cnext = next_dirty_cnode(cnode);
 115                 if (!cnext) {
 116                         cnode->cnext = c->lpt_cnext;
 117                         break;
 118                 }
 119                 cnode->cnext = cnext;
 120                 cnode = cnext;
 121                 cnt += 1;
 122         }
 123         dbg_cmt("committing %d cnodes", cnt);
 124         dbg_lp("committing %d cnodes", cnt);
 125         ubifs_assert(cnt == c->dirty_nn_cnt + c->dirty_pn_cnt);
 126         return cnt;
 127 }
 128
 129 /**
 130  * upd_ltab - update LPT LEB properties.
 131  * @c: UBIFS file-system description object
 132  * @lnum: LEB number
 133  * @free: amount of free space
 134  * @dirty: amount of dirty space to add
 135  */
 136 static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
 137 {
 138         dbg_lp("LEB %d free %d dirty %d to %d +%d",
 139                lnum, c->ltab[lnum - c->lpt_first].free,
 140                c->ltab[lnum - c->lpt_first].dirty, free, dirty);
 141         ubifs_assert(lnum >= c->lpt_first && lnum <= c->lpt_last);
 142         c->ltab[lnum - c->lpt_first].free = free;
 143         c->ltab[lnum - c->lpt_first].dirty += dirty;
 144 }
 145
 146 /**
 147  * alloc_lpt_leb - allocate an LPT LEB that is empty.
 148  * @c: UBIFS file-system description object
 149  * @lnum: LEB number is passed and returned here
 150  *
 151  * This function finds the next empty LEB in the ltab starting from @lnum. If a
 152  * an empty LEB is found it is returned in @lnum and the function returns %0.
 153  * Otherwise the function returns -ENOSPC.  Note however, that LPT is designed
 154  * never to run out of space.
 155  */
 156 static int alloc_lpt_leb(struct ubifs_info *c, int *lnum)
 157 {
 158         int i, n;
 159
 160         n = *lnum - c->lpt_first + 1;
 161         for (i = n; i < c->lpt_lebs; i++) {
 162                 if (c->ltab[i].tgc || c->ltab[i].cmt)
 163                         continue;
 164                 if (c->ltab[i].free == c->leb_size) {
 165                         c->ltab[i].cmt = 1;
 166                         *lnum = i + c->lpt_first;
 167                         return 0;
 168                 }
 169         }
 170
 171         for (i = 0; i < n; i++) {
 172                 if (c->ltab[i].tgc || c->ltab[i].cmt)
 173                         continue;
 174                 if (c->ltab[i].free == c->leb_size) {
 175                         c->ltab[i].cmt = 1;
 176                         *lnum = i + c->lpt_first;
 177                         return 0;
 178                 }
 179         }
 180         dbg_err("last LEB %d", *lnum);
 181         dump_stack();
 182         return -ENOSPC;
 183 }
 184
 185 /**
 186  * layout_cnodes - layout cnodes for commit.
 187  * @c: UBIFS file-system description object
 188  *
 189  * This function returns %0 on success and a negative error code on failure.
 190  */
 191 static int layout_cnodes(struct ubifs_info *c)
 192 {
 193         int lnum, offs, len, alen, done_lsave, done_ltab, err;
 194         struct ubifs_cnode *cnode;
 195
 196         cnode = c->lpt_cnext;
 197         if (!cnode)
 198                 return 0;
 199         lnum = c->nhead_lnum;
 200         offs = c->nhead_offs;
 201         /* Try to place lsave and ltab nicely */
 202         done_lsave = !c->big_lpt;
 203         done_ltab = 0;
 204         if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
 205                 done_lsave = 1;
 206                 c->lsave_lnum = lnum;
 207                 c->lsave_offs = offs;
 208                 offs += c->lsave_sz;
 209         }
 210
 211         if (offs + c->ltab_sz <= c->leb_size) {
 212                 done_ltab = 1;
 213                 c->ltab_lnum = lnum;
 214                 c->ltab_offs = offs;
 215                 offs += c->ltab_sz;
 216         }
 217
 218         do {
 219                 if (cnode->level) {
 220                         len = c->nnode_sz;
 221                         c->dirty_nn_cnt -= 1;
 222                 } else {
 223                         len = c->pnode_sz;
 224                         c->dirty_pn_cnt -= 1;
 225                 }
 226                 while (offs + len > c->leb_size) {
 227                         alen = ALIGN(offs, c->min_io_size);
 228                         upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 229                         err = alloc_lpt_leb(c, &lnum);
 230                         if (err)
 231                                 return err;
 232                         offs = 0;
 233                         ubifs_assert(lnum >= c->lpt_first &&
 234                                      lnum <= c->lpt_last);
 235                         /* Try to place lsave and ltab nicely */
 236                         if (!done_lsave) {
 237                                 done_lsave = 1;
 238                                 c->lsave_lnum = lnum;
 239                                 c->lsave_offs = offs;
 240                                 offs += c->lsave_sz;
 241                                 continue;
 242                         }
 243                         if (!done_ltab) {
 244                                 done_ltab = 1;
 245                                 c->ltab_lnum = lnum;
 246                                 c->ltab_offs = offs;
 247                                 offs += c->ltab_sz;
 248                                 continue;
 249                         }
 250                         break;
 251                 }
 252                 if (cnode->parent) {
 253                         cnode->parent->nbranch[cnode->iip].lnum = lnum;
 254                         cnode->parent->nbranch[cnode->iip].offs = offs;
 255                 } else {
 256                         c->lpt_lnum = lnum;
 257                         c->lpt_offs = offs;
 258                 }
 259                 offs += 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                         err = alloc_lpt_leb(c, &lnum);
 269                         if (err)
 270                                 return err;
 271                         offs = 0;
 272                         ubifs_assert(lnum >= c->lpt_first &&
 273                                      lnum <= c->lpt_last);
 274                 }
 275                 done_lsave = 1;
 276                 c->lsave_lnum = lnum;
 277                 c->lsave_offs = offs;
 278                 offs += c->lsave_sz;
 279         }
 280
 281         /* Make sure to place LPT's own lprops table */
 282         if (!done_ltab) {
 283                 if (offs + c->ltab_sz > c->leb_size) {
 284                         alen = ALIGN(offs, c->min_io_size);
 285                         upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 286                         err = alloc_lpt_leb(c, &lnum);
 287                         if (err)
 288                                 return err;
 289                         offs = 0;
 290                         ubifs_assert(lnum >= c->lpt_first &&
 291                                      lnum <= c->lpt_last);
 292                 }
 293                 done_ltab = 1;
 294                 c->ltab_lnum = lnum;
 295                 c->ltab_offs = offs;
 296                 offs += c->ltab_sz;
 297         }
 298
 299         alen = ALIGN(offs, c->min_io_size);
 300         upd_ltab(c, lnum, c->leb_size - alen, alen - offs);
 301         return 0;
 302 }
 303
 304 /**
 305  * realloc_lpt_leb - allocate an LPT LEB that is empty.
 306  * @c: UBIFS file-system description object
 307  * @lnum: LEB number is passed and returned here
 308  *
 309  * This function duplicates exactly the results of the function alloc_lpt_leb.
 310  * It is used during end commit to reallocate the same LEB numbers that were
 311  * allocated by alloc_lpt_leb during start commit.
 312  *
 313  * This function finds the next LEB that was allocated by the alloc_lpt_leb
 314  * function starting from @lnum. If a LEB is found it is returned in @lnum and
 315  * the function returns %0. Otherwise the function returns -ENOSPC.
 316  * Note however, that LPT is designed never to run out of space.
 317  */
 318 static int realloc_lpt_leb(struct ubifs_info *c, int *lnum)
 319 {
 320         int i, n;
 321
 322         n = *lnum - c->lpt_first + 1;
 323         for (i = n; i < c->lpt_lebs; i++)
 324                 if (c->ltab[i].cmt) {
 325                         c->ltab[i].cmt = 0;
 326                         *lnum = i + c->lpt_first;
 327                         return 0;
 328                 }
 329
 330         for (i = 0; i < n; i++)
 331                 if (c->ltab[i].cmt) {
 332                         c->ltab[i].cmt = 0;
 333                         *lnum = i + c->lpt_first;
 334                         return 0;
 335                 }
 336         dbg_err("last LEB %d", *lnum);
 337         dump_stack();
 338         return -ENOSPC;
 339 }
 340
 341 /**
 342  * write_cnodes - write cnodes for commit.
 343  * @c: UBIFS file-system description object
 344  *
 345  * This function returns %0 on success and a negative error code on failure.
 346  */
 347 static int write_cnodes(struct ubifs_info *c)
 348 {
 349         int lnum, offs, len, from, err, wlen, alen, done_ltab, done_lsave;
 350         struct ubifs_cnode *cnode;
 351         void *buf = c->lpt_buf;
 352
 353         cnode = c->lpt_cnext;
 354         if (!cnode)
 355                 return 0;
 356         lnum = c->nhead_lnum;
 357         offs = c->nhead_offs;
 358         from = offs;
 359         /* Ensure empty LEB is unmapped */
 360         if (offs == 0) {
 361                 err = ubifs_leb_unmap(c, lnum);
 362                 if (err)
 363                         return err;
 364         }
 365         /* Try to place lsave and ltab nicely */
 366         done_lsave = !c->big_lpt;
 367         done_ltab = 0;
 368         if (!done_lsave && offs + c->lsave_sz <= c->leb_size) {
 369                 done_lsave = 1;
 370                 ubifs_pack_lsave(c, buf + offs, c->lsave);
 371                 offs += c->lsave_sz;
 372         }
 373
 374         if (offs + c->ltab_sz <= c->leb_size) {
 375                 done_ltab = 1;
 376                 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 377                 offs += c->ltab_sz;
 378         }
 379
 380         /* Loop for each cnode */
 381         do {
 382                 if (cnode->level)
 383                         len = c->nnode_sz;
 384                 else
 385                         len = c->pnode_sz;
 386                 while (offs + len > c->leb_size) {
 387                         wlen = offs - from;
 388                         if (wlen) {
 389                                 alen = ALIGN(wlen, c->min_io_size);
 390                                 memset(buf + offs, 0xff, alen - wlen);
 391                                 err = ubifs_leb_write(c, lnum, buf + from, from,
 392                                                        alen, UBI_SHORTTERM);
 393                                 if (err)
 394                                         return err;
 395                         }
 396                         err = realloc_lpt_leb(c, &lnum);
 397                         if (err)
 398                                 return err;
 399                         offs = 0;
 400                         from = 0;
 401                         ubifs_assert(lnum >= c->lpt_first &&
 402                                      lnum <= c->lpt_last);
 403                         err = ubifs_leb_unmap(c, lnum);
 404                         if (err)
 405                                 return err;
 406                         /* Try to place lsave and ltab nicely */
 407                         if (!done_lsave) {
 408                                 done_lsave = 1;
 409                                 ubifs_pack_lsave(c, buf + offs, c->lsave);
 410                                 offs += c->lsave_sz;
 411                                 continue;
 412                         }
 413                         if (!done_ltab) {
 414                                 done_ltab = 1;
 415                                 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 416                                 offs += c->ltab_sz;
 417                                 continue;
 418                         }
 419                         break;
 420                 }
 421                 if (cnode->level)
 422                         ubifs_pack_nnode(c, buf + offs,
 423                                          (struct ubifs_nnode *)cnode);
 424                 else
 425                         ubifs_pack_pnode(c, buf + offs,
 426                                          (struct ubifs_pnode *)cnode);
 427                 /*
 428                  * The reason for the barriers is the same as in case of TNC.
 429                  * See comment in 'write_index()'. 'dirty_cow_nnode()' and
 430                  * 'dirty_cow_pnode()' are the functions for which this is
 431                  * important.
 432                  */
 433                 clear_bit(DIRTY_CNODE, &cnode->flags);
 434                 smp_mb__before_clear_bit();
 435                 clear_bit(COW_ZNODE, &cnode->flags);
 436                 smp_mb__after_clear_bit();
 437                 offs += len;
 438                 cnode = cnode->cnext;
 439         } while (cnode && cnode != c->lpt_cnext);
 440
 441         /* Make sure to place LPT's save table */
 442         if (!done_lsave) {
 443                 if (offs + c->lsave_sz > c->leb_size) {
 444                         wlen = offs - from;
 445                         alen = ALIGN(wlen, c->min_io_size);
 446                         memset(buf + offs, 0xff, alen - wlen);
 447                         err = ubifs_leb_write(c, lnum, buf + from, from, alen,
 448                                               UBI_SHORTTERM);
 449                         if (err)
 450                                 return err;
 451                         err = realloc_lpt_leb(c, &lnum);
 452                         if (err)
 453                                 return err;
 454                         offs = 0;
 455                         ubifs_assert(lnum >= c->lpt_first &&
 456                                      lnum <= c->lpt_last);
 457                         err = ubifs_leb_unmap(c, lnum);
 458                         if (err)
 459                                 return err;
 460                 }
 461                 done_lsave = 1;
 462                 ubifs_pack_lsave(c, buf + offs, c->lsave);
 463                 offs += c->lsave_sz;
 464         }
 465
 466         /* Make sure to place LPT's own lprops table */
 467         if (!done_ltab) {
 468                 if (offs + c->ltab_sz > c->leb_size) {
 469                         wlen = offs - from;
 470                         alen = ALIGN(wlen, c->min_io_size);
 471                         memset(buf + offs, 0xff, alen - wlen);
 472                         err = ubifs_leb_write(c, lnum, buf + from, from, alen,
 473                                               UBI_SHORTTERM);
 474                         if (err)
 475                                 return err;
 476                         err = realloc_lpt_leb(c, &lnum);
 477                         if (err)
 478                                 return err;
 479                         offs = 0;
 480                         ubifs_assert(lnum >= c->lpt_first &&
 481                                      lnum <= c->lpt_last);
 482                         err = ubifs_leb_unmap(c, lnum);
 483                         if (err)
 484                                 return err;
 485                 }
 486                 done_ltab = 1;
 487                 ubifs_pack_ltab(c, buf + offs, c->ltab_cmt);
 488                 offs += c->ltab_sz;
 489         }
 490
 491         /* Write remaining data in buffer */
 492         wlen = offs - from;
 493         alen = ALIGN(wlen, c->min_io_size);
 494         memset(buf + offs, 0xff, alen - wlen);
 495         err = ubifs_leb_write(c, lnum, buf + from, from, alen, UBI_SHORTTERM);
 496         if (err)
 497                 return err;
 498         c->nhead_lnum = lnum;
 499         c->nhead_offs = ALIGN(offs, c->min_io_size);
 500
 501         dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
 502         dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
 503         dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
 504         if (c->big_lpt)
 505                 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
 506         return 0;
 507 }
 508
 509 /**
 510  * next_pnode - find next pnode.
 511  * @c: UBIFS file-system description object
 512  * @pnode: pnode
 513  *
 514  * This function returns the next pnode or %NULL if there are no more pnodes.
 515  */
 516 static struct ubifs_pnode *next_pnode(struct ubifs_info *c,
 517                                       struct ubifs_pnode *pnode)
 518 {
 519         struct ubifs_nnode *nnode;
 520         int iip;
 521
 522         /* Try to go right */
 523         nnode = pnode->parent;
 524         iip = pnode->iip + 1;
 525         if (iip < UBIFS_LPT_FANOUT) {
 526                 /* We assume here that LEB zero is never an LPT LEB */
 527                 if (nnode->nbranch[iip].lnum)
 528                         return ubifs_get_pnode(c, nnode, iip);
 529                 else
 530                         return NULL;
 531         }
 532
 533         /* Go up while can't go right */
 534         do {
 535                 iip = nnode->iip + 1;
 536                 nnode = nnode->parent;
 537                 if (!nnode)
 538                         return NULL;
 539                 /* We assume here that LEB zero is never an LPT LEB */
 540         } while (iip >= UBIFS_LPT_FANOUT || !nnode->nbranch[iip].lnum);
 541
 542         /* Go right */
 543         nnode = ubifs_get_nnode(c, nnode, iip);
 544         if (IS_ERR(nnode))
 545                 return (void *)nnode;
 546
 547         /* Go down to level 1 */
 548         while (nnode->level > 1) {
 549                 nnode = ubifs_get_nnode(c, nnode, 0);
 550                 if (IS_ERR(nnode))
 551                         return (void *)nnode;
 552         }
 553
 554         return ubifs_get_pnode(c, nnode, 0);
 555 }
 556
 557 /**
 558  * pnode_lookup - lookup a pnode in the LPT.
 559  * @c: UBIFS file-system description object
 560  * @i: pnode number (0 to main_lebs - 1)
 561  *
 562  * This function returns a pointer to the pnode on success or a negative
 563  * error code on failure.
 564  */
 565 static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
 566 {
 567         int err, h, iip, shft;
 568         struct ubifs_nnode *nnode;
 569
 570         if (!c->nroot) {
 571                 err = ubifs_read_nnode(c, NULL, 0);
 572                 if (err)
 573                         return ERR_PTR(err);
 574         }
 575         i <<= UBIFS_LPT_FANOUT_SHIFT;
 576         nnode = c->nroot;
 577         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
 578         for (h = 1; h < c->lpt_hght; h++) {
 579                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 580                 shft -= UBIFS_LPT_FANOUT_SHIFT;
 581                 nnode = ubifs_get_nnode(c, nnode, iip);
 582                 if (IS_ERR(nnode))
 583                         return ERR_PTR(PTR_ERR(nnode));
 584         }
 585         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 586         return ubifs_get_pnode(c, nnode, iip);
 587 }
 588
 589 /**
 590  * add_pnode_dirt - add dirty space to LPT LEB properties.
 591  * @c: UBIFS file-system description object
 592  * @pnode: pnode for which to add dirt
 593  */
 594 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
 595 {
 596         ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
 597                            c->pnode_sz);
 598 }
 599
 600 /**
 601  * do_make_pnode_dirty - mark a pnode dirty.
 602  * @c: UBIFS file-system description object
 603  * @pnode: pnode to mark dirty
 604  */
 605 static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
 606 {
 607         /* Assumes cnext list is empty i.e. not called during commit */
 608         if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
 609                 struct ubifs_nnode *nnode;
 610
 611                 c->dirty_pn_cnt += 1;
 612                 add_pnode_dirt(c, pnode);
 613                 /* Mark parent and ancestors dirty too */
 614                 nnode = pnode->parent;
 615                 while (nnode) {
 616                         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 617                                 c->dirty_nn_cnt += 1;
 618                                 ubifs_add_nnode_dirt(c, nnode);
 619                                 nnode = nnode->parent;
 620                         } else
 621                                 break;
 622                 }
 623         }
 624 }
 625
 626 /**
 627  * make_tree_dirty - mark the entire LEB properties tree dirty.
 628  * @c: UBIFS file-system description object
 629  *
 630  * This function is used by the "small" LPT model to cause the entire LEB
 631  * properties tree to be written.  The "small" LPT model does not use LPT
 632  * garbage collection because it is more efficient to write the entire tree
 633  * (because it is small).
 634  *
 635  * This function returns %0 on success and a negative error code on failure.
 636  */
 637 static int make_tree_dirty(struct ubifs_info *c)
 638 {
 639         struct ubifs_pnode *pnode;
 640
 641         pnode = pnode_lookup(c, 0);
 642         while (pnode) {
 643                 do_make_pnode_dirty(c, pnode);
 644                 pnode = next_pnode(c, pnode);
 645                 if (IS_ERR(pnode))
 646                         return PTR_ERR(pnode);
 647         }
 648         return 0;
 649 }
 650
 651 /**
 652  * need_write_all - determine if the LPT area is running out of free space.
 653  * @c: UBIFS file-system description object
 654  *
 655  * This function returns %1 if the LPT area is running out of free space and %0
 656  * if it is not.
 657  */
 658 static int need_write_all(struct ubifs_info *c)
 659 {
 660         long long free = 0;
 661         int i;
 662
 663         for (i = 0; i < c->lpt_lebs; i++) {
 664                 if (i + c->lpt_first == c->nhead_lnum)
 665                         free += c->leb_size - c->nhead_offs;
 666                 else if (c->ltab[i].free == c->leb_size)
 667                         free += c->leb_size;
 668                 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
 669                         free += c->leb_size;
 670         }
 671         /* Less than twice the size left */
 672         if (free <= c->lpt_sz * 2)
 673                 return 1;
 674         return 0;
 675 }
 676
 677 /**
 678  * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
 679  * @c: UBIFS file-system description object
 680  *
 681  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 682  * free space and so may be reused as soon as the next commit is completed.
 683  * This function is called during start commit to mark LPT LEBs for trivial GC.
 684  */
 685 static void lpt_tgc_start(struct ubifs_info *c)
 686 {
 687         int i;
 688
 689         for (i = 0; i < c->lpt_lebs; i++) {
 690                 if (i + c->lpt_first == c->nhead_lnum)
 691                         continue;
 692                 if (c->ltab[i].dirty > 0 &&
 693                     c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
 694                         c->ltab[i].tgc = 1;
 695                         c->ltab[i].free = c->leb_size;
 696                         c->ltab[i].dirty = 0;
 697                         dbg_lp("LEB %d", i + c->lpt_first);
 698                 }
 699         }
 700 }
 701
 702 /**
 703  * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
 704  * @c: UBIFS file-system description object
 705  *
 706  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 707  * free space and so may be reused as soon as the next commit is completed.
 708  * This function is called after the commit is completed (master node has been
 709  * written) and unmaps LPT LEBs that were marked for trivial GC.
 710  */
 711 static int lpt_tgc_end(struct ubifs_info *c)
 712 {
 713         int i, err;
 714
 715         for (i = 0; i < c->lpt_lebs; i++)
 716                 if (c->ltab[i].tgc) {
 717                         err = ubifs_leb_unmap(c, i + c->lpt_first);
 718                         if (err)
 719                                 return err;
 720                         c->ltab[i].tgc = 0;
 721                         dbg_lp("LEB %d", i + c->lpt_first);
 722                 }
 723         return 0;
 724 }
 725
 726 /**
 727  * populate_lsave - fill the lsave array with important LEB numbers.
 728  * @c: the UBIFS file-system description object
 729  *
 730  * This function is only called for the "big" model. It records a small number
 731  * of LEB numbers of important LEBs.  Important LEBs are ones that are (from
 732  * most important to least important): empty, freeable, freeable index, dirty
 733  * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
 734  * their pnodes into memory.  That will stop us from having to scan the LPT
 735  * straight away. For the "small" model we assume that scanning the LPT is no
 736  * big deal.
 737  */
 738 static void populate_lsave(struct ubifs_info *c)
 739 {
 740         struct ubifs_lprops *lprops;
 741         struct ubifs_lpt_heap *heap;
 742         int i, cnt = 0;
 743
 744         ubifs_assert(c->big_lpt);
 745         if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 746                 c->lpt_drty_flgs |= LSAVE_DIRTY;
 747                 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 748         }
 749         list_for_each_entry(lprops, &c->empty_list, list) {
 750                 c->lsave[cnt++] = lprops->lnum;
 751                 if (cnt >= c->lsave_cnt)
 752                         return;
 753         }
 754         list_for_each_entry(lprops, &c->freeable_list, list) {
 755                 c->lsave[cnt++] = lprops->lnum;
 756                 if (cnt >= c->lsave_cnt)
 757                         return;
 758         }
 759         list_for_each_entry(lprops, &c->frdi_idx_list, list) {
 760                 c->lsave[cnt++] = lprops->lnum;
 761                 if (cnt >= c->lsave_cnt)
 762                         return;
 763         }
 764         heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 765         for (i = 0; i < heap->cnt; i++) {
 766                 c->lsave[cnt++] = heap->arr[i]->lnum;
 767                 if (cnt >= c->lsave_cnt)
 768                         return;
 769         }
 770         heap = &c->lpt_heap[LPROPS_DIRTY - 1];
 771         for (i = 0; i < heap->cnt; i++) {
 772                 c->lsave[cnt++] = heap->arr[i]->lnum;
 773                 if (cnt >= c->lsave_cnt)
 774                         return;
 775         }
 776         heap = &c->lpt_heap[LPROPS_FREE - 1];
 777         for (i = 0; i < heap->cnt; i++) {
 778                 c->lsave[cnt++] = heap->arr[i]->lnum;
 779                 if (cnt >= c->lsave_cnt)
 780                         return;
 781         }
 782         /* Fill it up completely */
 783         while (cnt < c->lsave_cnt)
 784                 c->lsave[cnt++] = c->main_first;
 785 }
 786
 787 /**
 788  * nnode_lookup - lookup a nnode in the LPT.
 789  * @c: UBIFS file-system description object
 790  * @i: nnode number
 791  *
 792  * This function returns a pointer to the nnode on success or a negative
 793  * error code on failure.
 794  */
 795 static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
 796 {
 797         int err, iip;
 798         struct ubifs_nnode *nnode;
 799
 800         if (!c->nroot) {
 801                 err = ubifs_read_nnode(c, NULL, 0);
 802                 if (err)
 803                         return ERR_PTR(err);
 804         }
 805         nnode = c->nroot;
 806         while (1) {
 807                 iip = i & (UBIFS_LPT_FANOUT - 1);
 808                 i >>= UBIFS_LPT_FANOUT_SHIFT;
 809                 if (!i)
 810                         break;
 811                 nnode = ubifs_get_nnode(c, nnode, iip);
 812                 if (IS_ERR(nnode))
 813                         return nnode;
 814         }
 815         return nnode;
 816 }
 817
 818 /**
 819  * make_nnode_dirty - find a nnode and, if found, make it dirty.
 820  * @c: UBIFS file-system description object
 821  * @node_num: nnode number of nnode to make dirty
 822  * @lnum: LEB number where nnode was written
 823  * @offs: offset where nnode was written
 824  *
 825  * This function is used by LPT garbage collection.  LPT garbage collection is
 826  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 827  * simply involves marking all the nodes in the LEB being garbage-collected as
 828  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 829  * to be reused.
 830  *
 831  * This function returns %0 on success and a negative error code on failure.
 832  */
 833 static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 834                             int offs)
 835 {
 836         struct ubifs_nnode *nnode;
 837
 838         nnode = nnode_lookup(c, node_num);
 839         if (IS_ERR(nnode))
 840                 return PTR_ERR(nnode);
 841         if (nnode->parent) {
 842                 struct ubifs_nbranch *branch;
 843
 844                 branch = &nnode->parent->nbranch[nnode->iip];
 845                 if (branch->lnum != lnum || branch->offs != offs)
 846                         return 0; /* nnode is obsolete */
 847         } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
 848                         return 0; /* nnode is obsolete */
 849         /* Assumes cnext list is empty i.e. not called during commit */
 850         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 851                 c->dirty_nn_cnt += 1;
 852                 ubifs_add_nnode_dirt(c, nnode);
 853                 /* Mark parent and ancestors dirty too */
 854                 nnode = nnode->parent;
 855                 while (nnode) {
 856                         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 857                                 c->dirty_nn_cnt += 1;
 858                                 ubifs_add_nnode_dirt(c, nnode);
 859                                 nnode = nnode->parent;
 860                         } else
 861                                 break;
 862                 }
 863         }
 864         return 0;
 865 }
 866
 867 /**
 868  * make_pnode_dirty - find a pnode and, if found, make it dirty.
 869  * @c: UBIFS file-system description object
 870  * @node_num: pnode number of pnode to make dirty
 871  * @lnum: LEB number where pnode was written
 872  * @offs: offset where pnode was written
 873  *
 874  * This function is used by LPT garbage collection.  LPT garbage collection is
 875  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 876  * simply involves marking all the nodes in the LEB being garbage-collected as
 877  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 878  * to be reused.
 879  *
 880  * This function returns %0 on success and a negative error code on failure.
 881  */
 882 static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 883                             int offs)
 884 {
 885         struct ubifs_pnode *pnode;
 886         struct ubifs_nbranch *branch;
 887
 888         pnode = pnode_lookup(c, node_num);
 889         if (IS_ERR(pnode))
 890                 return PTR_ERR(pnode);
 891         branch = &pnode->parent->nbranch[pnode->iip];
 892         if (branch->lnum != lnum || branch->offs != offs)
 893                 return 0;
 894         do_make_pnode_dirty(c, pnode);
 895         return 0;
 896 }
 897
 898 /**
 899  * make_ltab_dirty - make ltab node dirty.
 900  * @c: UBIFS file-system description object
 901  * @lnum: LEB number where ltab was written
 902  * @offs: offset where ltab was written
 903  *
 904  * This function is used by LPT garbage collection.  LPT garbage collection is
 905  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 906  * simply involves marking all the nodes in the LEB being garbage-collected as
 907  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 908  * to be reused.
 909  *
 910  * This function returns %0 on success and a negative error code on failure.
 911  */
 912 static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
 913 {
 914         if (lnum != c->ltab_lnum || offs != c->ltab_offs)
 915                 return 0; /* This ltab node is obsolete */
 916         if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
 917                 c->lpt_drty_flgs |= LTAB_DIRTY;
 918                 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
 919         }
 920         return 0;
 921 }
 922
 923 /**
 924  * make_lsave_dirty - make lsave node dirty.
 925  * @c: UBIFS file-system description object
 926  * @lnum: LEB number where lsave was written
 927  * @offs: offset where lsave was written
 928  *
 929  * This function is used by LPT garbage collection.  LPT garbage collection is
 930  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 931  * simply involves marking all the nodes in the LEB being garbage-collected as
 932  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 933  * to be reused.
 934  *
 935  * This function returns %0 on success and a negative error code on failure.
 936  */
 937 static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
 938 {
 939         if (lnum != c->lsave_lnum || offs != c->lsave_offs)
 940                 return 0; /* This lsave node is obsolete */
 941         if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 942                 c->lpt_drty_flgs |= LSAVE_DIRTY;
 943                 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 944         }
 945         return 0;
 946 }
 947
 948 /**
 949  * make_node_dirty - make node dirty.
 950  * @c: UBIFS file-system description object
 951  * @node_type: LPT node type
 952  * @node_num: node number
 953  * @lnum: LEB number where node was written
 954  * @offs: offset where node 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_node_dirty(struct ubifs_info *c, int node_type, int node_num,
 965                            int lnum, int offs)
 966 {
 967         switch (node_type) {
 968         case UBIFS_LPT_NNODE:
 969                 return make_nnode_dirty(c, node_num, lnum, offs);
 970         case UBIFS_LPT_PNODE:
 971                 return make_pnode_dirty(c, node_num, lnum, offs);
 972         case UBIFS_LPT_LTAB:
 973                 return make_ltab_dirty(c, lnum, offs);
 974         case UBIFS_LPT_LSAVE:
 975                 return make_lsave_dirty(c, lnum, offs);
 976         }
 977         return -EINVAL;
 978 }
 979
 980 /**
 981  * get_lpt_node_len - return the length of a node based on its type.
 982  * @c: UBIFS file-system description object
 983  * @node_type: LPT node type
 984  */
 985 static int get_lpt_node_len(struct ubifs_info *c, int node_type)
 986 {
 987         switch (node_type) {
 988         case UBIFS_LPT_NNODE:
 989                 return c->nnode_sz;
 990         case UBIFS_LPT_PNODE:
 991                 return c->pnode_sz;
 992         case UBIFS_LPT_LTAB:
 993                 return c->ltab_sz;
 994         case UBIFS_LPT_LSAVE:
 995                 return c->lsave_sz;
 996         }
 997         return 0;
 998 }
 999
1000 /**
1001  * get_pad_len - return the length of padding in a buffer.
1002  * @c: UBIFS file-system description object
1003  * @buf: buffer
1004  * @len: length of buffer
1005  */
1006 static int get_pad_len(struct ubifs_info *c, uint8_t *buf, int len)
1007 {
1008         int offs, pad_len;
1009
1010         if (c->min_io_size == 1)
1011                 return 0;
1012         offs = c->leb_size - len;
1013         pad_len = ALIGN(offs, c->min_io_size) - offs;
1014         return pad_len;
1015 }
1016
1017 /**
1018  * get_lpt_node_type - return type (and node number) of a node in a buffer.
1019  * @c: UBIFS file-system description object
1020  * @buf: buffer
1021  * @node_num: node number is returned here
1022  */
1023 static int get_lpt_node_type(struct ubifs_info *c, uint8_t *buf, int *node_num)
1024 {
1025         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1026         int pos = 0, node_type;
1027
1028         node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1029         *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1030         return node_type;
1031 }
1032
1033 /**
1034  * is_a_node - determine if a buffer contains a node.
1035  * @c: UBIFS file-system description object
1036  * @buf: buffer
1037  * @len: length of buffer
1038  *
1039  * This function returns %1 if the buffer contains a node or %0 if it does not.
1040  */
1041 static int is_a_node(struct ubifs_info *c, uint8_t *buf, int len)
1042 {
1043         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1044         int pos = 0, node_type, node_len;
1045         uint16_t crc, calc_crc;
1046
1047         node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1048         if (node_type == UBIFS_LPT_NOT_A_NODE)
1049                 return 0;
1050         node_len = get_lpt_node_len(c, node_type);
1051         if (!node_len || node_len > len)
1052                 return 0;
1053         pos = 0;
1054         addr = buf;
1055         crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1056         calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1057                          node_len - UBIFS_LPT_CRC_BYTES);
1058         if (crc != calc_crc)
1059                 return 0;
1060         return 1;
1061 }
1062
1063
1064 /**
1065  * lpt_gc_lnum - garbage collect a LPT LEB.
1066  * @c: UBIFS file-system description object
1067  * @lnum: LEB number to garbage collect
1068  *
1069  * LPT garbage collection is used only for the "big" LPT model
1070  * (c->big_lpt == 1).  Garbage collection simply involves marking all the nodes
1071  * in the LEB being garbage-collected as dirty.  The dirty nodes are written
1072  * next commit, after which the LEB is free to be reused.
1073  *
1074  * This function returns %0 on success and a negative error code on failure.
1075  */
1076 static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1077 {
1078         int err, len = c->leb_size, node_type, node_num, node_len, offs;
1079         void *buf = c->lpt_buf;
1080
1081         dbg_lp("LEB %d", lnum);
1082         err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1083         if (err) {
1084                 ubifs_err("cannot read LEB %d, error %d", lnum, err);
1085                 return err;
1086         }
1087         while (1) {
1088                 if (!is_a_node(c, buf, len)) {
1089                         int pad_len;
1090
1091                         pad_len = get_pad_len(c, buf, len);
1092                         if (pad_len) {
1093                                 buf += pad_len;
1094                                 len -= pad_len;
1095                                 continue;
1096                         }
1097                         return 0;
1098                 }
1099                 node_type = get_lpt_node_type(c, buf, &node_num);
1100                 node_len = get_lpt_node_len(c, node_type);
1101                 offs = c->leb_size - len;
1102                 ubifs_assert(node_len != 0);
1103                 mutex_lock(&c->lp_mutex);
1104                 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1105                 mutex_unlock(&c->lp_mutex);
1106                 if (err)
1107                         return err;
1108                 buf += node_len;
1109                 len -= node_len;
1110         }
1111         return 0;
1112 }
1113
1114 /**
1115  * lpt_gc - LPT garbage collection.
1116  * @c: UBIFS file-system description object
1117  *
1118  * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1119  * Returns %0 on success and a negative error code on failure.
1120  */
1121 static int lpt_gc(struct ubifs_info *c)
1122 {
1123         int i, lnum = -1, dirty = 0;
1124
1125         mutex_lock(&c->lp_mutex);
1126         for (i = 0; i < c->lpt_lebs; i++) {
1127                 ubifs_assert(!c->ltab[i].tgc);
1128                 if (i + c->lpt_first == c->nhead_lnum ||
1129                     c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1130                         continue;
1131                 if (c->ltab[i].dirty > dirty) {
1132                         dirty = c->ltab[i].dirty;
1133                         lnum = i + c->lpt_first;
1134                 }
1135         }
1136         mutex_unlock(&c->lp_mutex);
1137         if (lnum == -1)
1138                 return -ENOSPC;
1139         return lpt_gc_lnum(c, lnum);
1140 }
1141
1142 /**
1143  * ubifs_lpt_start_commit - UBIFS commit starts.
1144  * @c: the UBIFS file-system description object
1145  *
1146  * This function has to be called when UBIFS starts the commit operation.
1147  * This function "freezes" all currently dirty LEB properties and does not
1148  * change them anymore. Further changes are saved and tracked separately
1149  * because they are not part of this commit. This function returns zero in case
1150  * of success and a negative error code in case of failure.
1151  */
1152 int ubifs_lpt_start_commit(struct ubifs_info *c)
1153 {
1154         int err, cnt;
1155
1156         dbg_lp("");
1157
1158         mutex_lock(&c->lp_mutex);
1159         err = dbg_check_ltab(c);
1160         if (err)
1161                 goto out;
1162
1163         if (c->check_lpt_free) {
1164                 /*
1165                  * We ensure there is enough free space in
1166                  * ubifs_lpt_post_commit() by marking nodes dirty. That
1167                  * information is lost when we unmount, so we also need
1168                  * to check free space once after mounting also.
1169                  */
1170                 c->check_lpt_free = 0;
1171                 while (need_write_all(c)) {
1172                         mutex_unlock(&c->lp_mutex);
1173                         err = lpt_gc(c);
1174                         if (err)
1175                                 return err;
1176                         mutex_lock(&c->lp_mutex);
1177                 }
1178         }
1179
1180         lpt_tgc_start(c);
1181
1182         if (!c->dirty_pn_cnt) {
1183                 dbg_cmt("no cnodes to commit");
1184                 err = 0;
1185                 goto out;
1186         }
1187
1188         if (!c->big_lpt && need_write_all(c)) {
1189                 /* If needed, write everything */
1190                 err = make_tree_dirty(c);
1191                 if (err)
1192                         goto out;
1193                 lpt_tgc_start(c);
1194         }
1195
1196         if (c->big_lpt)
1197                 populate_lsave(c);
1198
1199         cnt = get_cnodes_to_commit(c);
1200         ubifs_assert(cnt != 0);
1201
1202         err = layout_cnodes(c);
1203         if (err)
1204                 goto out;
1205
1206         /* Copy the LPT's own lprops for end commit to write */
1207         memcpy(c->ltab_cmt, c->ltab,
1208                sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1209         c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1210
1211 out:
1212         mutex_unlock(&c->lp_mutex);
1213         return err;
1214 }
1215
1216 /**
1217  * free_obsolete_cnodes - free obsolete cnodes for commit end.
1218  * @c: UBIFS file-system description object
1219  */
1220 static void free_obsolete_cnodes(struct ubifs_info *c)
1221 {
1222         struct ubifs_cnode *cnode, *cnext;
1223
1224         cnext = c->lpt_cnext;
1225         if (!cnext)
1226                 return;
1227         do {
1228                 cnode = cnext;
1229                 cnext = cnode->cnext;
1230                 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1231                         kfree(cnode);
1232                 else
1233                         cnode->cnext = NULL;
1234         } while (cnext != c->lpt_cnext);
1235         c->lpt_cnext = NULL;
1236 }
1237
1238 /**
1239  * ubifs_lpt_end_commit - finish the commit operation.
1240  * @c: the UBIFS file-system description object
1241  *
1242  * This function has to be called when the commit operation finishes. It
1243  * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1244  * the media. Returns zero in case of success and a negative error code in case
1245  * of failure.
1246  */
1247 int ubifs_lpt_end_commit(struct ubifs_info *c)
1248 {
1249         int err;
1250
1251         dbg_lp("");
1252
1253         if (!c->lpt_cnext)
1254                 return 0;
1255
1256         err = write_cnodes(c);
1257         if (err)
1258                 return err;
1259
1260         mutex_lock(&c->lp_mutex);
1261         free_obsolete_cnodes(c);
1262         mutex_unlock(&c->lp_mutex);
1263
1264         return 0;
1265 }
1266
1267 /**
1268  * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1269  * @c: UBIFS file-system description object
1270  *
1271  * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1272  * commit for the "big" LPT model.
1273  */
1274 int ubifs_lpt_post_commit(struct ubifs_info *c)
1275 {
1276         int err;
1277
1278         mutex_lock(&c->lp_mutex);
1279         err = lpt_tgc_end(c);
1280         if (err)
1281                 goto out;
1282         if (c->big_lpt)
1283                 while (need_write_all(c)) {
1284                         mutex_unlock(&c->lp_mutex);
1285                         err = lpt_gc(c);
1286                         if (err)
1287                                 return err;
1288                         mutex_lock(&c->lp_mutex);
1289                 }
1290 out:
1291         mutex_unlock(&c->lp_mutex);
1292         return err;
1293 }
1294
1295 /**
1296  * first_nnode - find the first nnode in memory.
1297  * @c: UBIFS file-system description object
1298  * @hght: height of tree where nnode found is returned here
1299  *
1300  * This function returns a pointer to the nnode found or %NULL if no nnode is
1301  * found. This function is a helper to 'ubifs_lpt_free()'.
1302  */
1303 static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1304 {
1305         struct ubifs_nnode *nnode;
1306         int h, i, found;
1307
1308         nnode = c->nroot;
1309         *hght = 0;
1310         if (!nnode)
1311                 return NULL;
1312         for (h = 1; h < c->lpt_hght; h++) {
1313                 found = 0;
1314                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1315                         if (nnode->nbranch[i].nnode) {
1316                                 found = 1;
1317                                 nnode = nnode->nbranch[i].nnode;
1318                                 *hght = h;
1319                                 break;
1320                         }
1321                 }
1322                 if (!found)
1323                         break;
1324         }
1325         return nnode;
1326 }
1327
1328 /**
1329  * next_nnode - find the next nnode in memory.
1330  * @c: UBIFS file-system description object
1331  * @nnode: nnode from which to start.
1332  * @hght: height of tree where nnode is, is passed and returned here
1333  *
1334  * This function returns a pointer to the nnode found or %NULL if no nnode is
1335  * found. This function is a helper to 'ubifs_lpt_free()'.
1336  */
1337 static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1338                                       struct ubifs_nnode *nnode, int *hght)
1339 {
1340         struct ubifs_nnode *parent;
1341         int iip, h, i, found;
1342
1343         parent = nnode->parent;
1344         if (!parent)
1345                 return NULL;
1346         if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1347                 *hght -= 1;
1348                 return parent;
1349         }
1350         for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1351                 nnode = parent->nbranch[iip].nnode;
1352                 if (nnode)
1353                         break;
1354         }
1355         if (!nnode) {
1356                 *hght -= 1;
1357                 return parent;
1358         }
1359         for (h = *hght + 1; h < c->lpt_hght; h++) {
1360                 found = 0;
1361                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1362                         if (nnode->nbranch[i].nnode) {
1363                                 found = 1;
1364                                 nnode = nnode->nbranch[i].nnode;
1365                                 *hght = h;
1366                                 break;
1367                         }
1368                 }
1369                 if (!found)
1370                         break;
1371         }
1372         return nnode;
1373 }
1374
1375 /**
1376  * ubifs_lpt_free - free resources owned by the LPT.
1377  * @c: UBIFS file-system description object
1378  * @wr_only: free only resources used for writing
1379  */
1380 void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1381 {
1382         struct ubifs_nnode *nnode;
1383         int i, hght;
1384
1385         /* Free write-only things first */
1386
1387         free_obsolete_cnodes(c); /* Leftover from a failed commit */
1388
1389         vfree(c->ltab_cmt);
1390         c->ltab_cmt = NULL;
1391         vfree(c->lpt_buf);
1392         c->lpt_buf = NULL;
1393         kfree(c->lsave);
1394         c->lsave = NULL;
1395
1396         if (wr_only)
1397                 return;
1398
1399         /* Now free the rest */
1400
1401         nnode = first_nnode(c, &hght);
1402         while (nnode) {
1403                 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1404                         kfree(nnode->nbranch[i].nnode);
1405                 nnode = next_nnode(c, nnode, &hght);
1406         }
1407         for (i = 0; i < LPROPS_HEAP_CNT; i++)
1408                 kfree(c->lpt_heap[i].arr);
1409         kfree(c->dirty_idx.arr);
1410         kfree(c->nroot);
1411         vfree(c->ltab);
1412         kfree(c->lpt_nod_buf);
1413 }
1414
1415 #ifdef CONFIG_UBIFS_FS_DEBUG
1416
1417 /**
1418  * dbg_is_all_ff - determine if a buffer contains only 0xff bytes.
1419  * @buf: buffer
1420  * @len: buffer length
1421  */
1422 static int dbg_is_all_ff(uint8_t *buf, int len)
1423 {
1424         int i;
1425
1426         for (i = 0; i < len; i++)
1427                 if (buf[i] != 0xff)
1428                         return 0;
1429         return 1;
1430 }
1431
1432 /**
1433  * dbg_is_nnode_dirty - determine if a nnode is dirty.
1434  * @c: the UBIFS file-system description object
1435  * @lnum: LEB number where nnode was written
1436  * @offs: offset where nnode was written
1437  */
1438 static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1439 {
1440         struct ubifs_nnode *nnode;
1441         int hght;
1442
1443         /* Entire tree is in memory so first_nnode / next_nnode are ok */
1444         nnode = first_nnode(c, &hght);
1445         for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1446                 struct ubifs_nbranch *branch;
1447
1448                 cond_resched();
1449                 if (nnode->parent) {
1450                         branch = &nnode->parent->nbranch[nnode->iip];
1451                         if (branch->lnum != lnum || branch->offs != offs)
1452                                 continue;
1453                         if (test_bit(DIRTY_CNODE, &nnode->flags))
1454                                 return 1;
1455                         return 0;
1456                 } else {
1457                         if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1458                                 continue;
1459                         if (test_bit(DIRTY_CNODE, &nnode->flags))
1460                                 return 1;
1461                         return 0;
1462                 }
1463         }
1464         return 1;
1465 }
1466
1467 /**
1468  * dbg_is_pnode_dirty - determine if a pnode is dirty.
1469  * @c: the UBIFS file-system description object
1470  * @lnum: LEB number where pnode was written
1471  * @offs: offset where pnode was written
1472  */
1473 static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1474 {
1475         int i, cnt;
1476
1477         cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1478         for (i = 0; i < cnt; i++) {
1479                 struct ubifs_pnode *pnode;
1480                 struct ubifs_nbranch *branch;
1481
1482                 cond_resched();
1483                 pnode = pnode_lookup(c, i);
1484                 if (IS_ERR(pnode))
1485                         return PTR_ERR(pnode);
1486                 branch = &pnode->parent->nbranch[pnode->iip];
1487                 if (branch->lnum != lnum || branch->offs != offs)
1488                         continue;
1489                 if (test_bit(DIRTY_CNODE, &pnode->flags))
1490                         return 1;
1491                 return 0;
1492         }
1493         return 1;
1494 }
1495
1496 /**
1497  * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1498  * @c: the UBIFS file-system description object
1499  * @lnum: LEB number where ltab node was written
1500  * @offs: offset where ltab node was written
1501  */
1502 static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1503 {
1504         if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1505                 return 1;
1506         return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1507 }
1508
1509 /**
1510  * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1511  * @c: the UBIFS file-system description object
1512  * @lnum: LEB number where lsave node was written
1513  * @offs: offset where lsave node was written
1514  */
1515 static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1516 {
1517         if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1518                 return 1;
1519         return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1520 }
1521
1522 /**
1523  * dbg_is_node_dirty - determine if a node is dirty.
1524  * @c: the UBIFS file-system description object
1525  * @node_type: node type
1526  * @lnum: LEB number where node was written
1527  * @offs: offset where node was written
1528  */
1529 static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1530                              int offs)
1531 {
1532         switch (node_type) {
1533         case UBIFS_LPT_NNODE:
1534                 return dbg_is_nnode_dirty(c, lnum, offs);
1535         case UBIFS_LPT_PNODE:
1536                 return dbg_is_pnode_dirty(c, lnum, offs);
1537         case UBIFS_LPT_LTAB:
1538                 return dbg_is_ltab_dirty(c, lnum, offs);
1539         case UBIFS_LPT_LSAVE:
1540                 return dbg_is_lsave_dirty(c, lnum, offs);
1541         }
1542         return 1;
1543 }
1544
1545 /**
1546  * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1547  * @c: the UBIFS file-system description object
1548  * @lnum: LEB number where node was written
1549  * @offs: offset where node was written
1550  *
1551  * This function returns %0 on success and a negative error code on failure.
1552  */
1553 static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1554 {
1555         int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1556         int ret;
1557         void *buf = c->dbg_buf;
1558
1559         dbg_lp("LEB %d", lnum);
1560         err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1561         if (err) {
1562                 dbg_msg("ubi_read failed, LEB %d, error %d", lnum, err);
1563                 return err;
1564         }
1565         while (1) {
1566                 if (!is_a_node(c, buf, len)) {
1567                         int i, pad_len;
1568
1569                         pad_len = get_pad_len(c, buf, len);
1570                         if (pad_len) {
1571                                 buf += pad_len;
1572                                 len -= pad_len;
1573                                 dirty += pad_len;
1574                                 continue;
1575                         }
1576                         if (!dbg_is_all_ff(buf, len)) {
1577                                 dbg_msg("invalid empty space in LEB %d at %d",
1578                                         lnum, c->leb_size - len);
1579                                 err = -EINVAL;
1580                         }
1581                         i = lnum - c->lpt_first;
1582                         if (len != c->ltab[i].free) {
1583                                 dbg_msg("invalid free space in LEB %d "
1584                                         "(free %d, expected %d)",
1585                                         lnum, len, c->ltab[i].free);
1586                                 err = -EINVAL;
1587                         }
1588                         if (dirty != c->ltab[i].dirty) {
1589                                 dbg_msg("invalid dirty space in LEB %d "
1590                                         "(dirty %d, expected %d)",
1591                                         lnum, dirty, c->ltab[i].dirty);
1592                                 err = -EINVAL;
1593                         }
1594                         return err;
1595                 }
1596                 node_type = get_lpt_node_type(c, buf, &node_num);
1597                 node_len = get_lpt_node_len(c, node_type);
1598                 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1599                 if (ret == 1)
1600                         dirty += node_len;
1601                 buf += node_len;
1602                 len -= node_len;
1603         }
1604 }
1605
1606 /**
1607  * dbg_check_ltab - check the free and dirty space in the ltab.
1608  * @c: the UBIFS file-system description object
1609  *
1610  * This function returns %0 on success and a negative error code on failure.
1611  */
1612 int dbg_check_ltab(struct ubifs_info *c)
1613 {
1614         int lnum, err, i, cnt;
1615
1616         if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1617                 return 0;
1618
1619         /* Bring the entire tree into memory */
1620         cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1621         for (i = 0; i < cnt; i++) {
1622                 struct ubifs_pnode *pnode;
1623
1624                 pnode = pnode_lookup(c, i);
1625                 if (IS_ERR(pnode))
1626                         return PTR_ERR(pnode);
1627                 cond_resched();
1628         }
1629
1630         /* Check nodes */
1631         err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1632         if (err)
1633                 return err;
1634
1635         /* Check each LEB */
1636         for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1637                 err = dbg_check_ltab_lnum(c, lnum);
1638                 if (err) {
1639                         dbg_err("failed at LEB %d", lnum);
1640                         return err;
1641                 }
1642         }
1643
1644         dbg_lp("succeeded");
1645         return 0;
1646 }
1647
1648 #endif /* CONFIG_UBIFS_FS_DEBUG */