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