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         }
 575
 576         /* Go up while can't go right */
 577         do {
 578                 iip = nnode->iip + 1;
 579                 nnode = nnode->parent;
 580                 if (!nnode)
 581                         return NULL;
 582                 /* We assume here that LEB zero is never an LPT LEB */
 583         } while (iip >= UBIFS_LPT_FANOUT || !nnode->nbranch[iip].lnum);
 584
 585         /* Go right */
 586         nnode = ubifs_get_nnode(c, nnode, iip);
 587         if (IS_ERR(nnode))
 588                 return (void *)nnode;
 589
 590         /* Go down to level 1 */
 591         while (nnode->level > 1) {
 592                 nnode = ubifs_get_nnode(c, nnode, 0);
 593                 if (IS_ERR(nnode))
 594                         return (void *)nnode;
 595         }
 596
 597         return ubifs_get_pnode(c, nnode, 0);
 598 }
 599
 600 /**
 601  * pnode_lookup - lookup a pnode in the LPT.
 602  * @c: UBIFS file-system description object
 603  * @i: pnode number (0 to main_lebs - 1)
 604  *
 605  * This function returns a pointer to the pnode on success or a negative
 606  * error code on failure.
 607  */
 608 static struct ubifs_pnode *pnode_lookup(struct ubifs_info *c, int i)
 609 {
 610         int err, h, iip, shft;
 611         struct ubifs_nnode *nnode;
 612
 613         if (!c->nroot) {
 614                 err = ubifs_read_nnode(c, NULL, 0);
 615                 if (err)
 616                         return ERR_PTR(err);
 617         }
 618         i <<= UBIFS_LPT_FANOUT_SHIFT;
 619         nnode = c->nroot;
 620         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
 621         for (h = 1; h < c->lpt_hght; h++) {
 622                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 623                 shft -= UBIFS_LPT_FANOUT_SHIFT;
 624                 nnode = ubifs_get_nnode(c, nnode, iip);
 625                 if (IS_ERR(nnode))
 626                         return ERR_PTR(PTR_ERR(nnode));
 627         }
 628         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
 629         return ubifs_get_pnode(c, nnode, iip);
 630 }
 631
 632 /**
 633  * add_pnode_dirt - add dirty space to LPT LEB properties.
 634  * @c: UBIFS file-system description object
 635  * @pnode: pnode for which to add dirt
 636  */
 637 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
 638 {
 639         ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
 640                            c->pnode_sz);
 641 }
 642
 643 /**
 644  * do_make_pnode_dirty - mark a pnode dirty.
 645  * @c: UBIFS file-system description object
 646  * @pnode: pnode to mark dirty
 647  */
 648 static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode)
 649 {
 650         /* Assumes cnext list is empty i.e. not called during commit */
 651         if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
 652                 struct ubifs_nnode *nnode;
 653
 654                 c->dirty_pn_cnt += 1;
 655                 add_pnode_dirt(c, pnode);
 656                 /* Mark parent and ancestors dirty too */
 657                 nnode = pnode->parent;
 658                 while (nnode) {
 659                         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 660                                 c->dirty_nn_cnt += 1;
 661                                 ubifs_add_nnode_dirt(c, nnode);
 662                                 nnode = nnode->parent;
 663                         } else
 664                                 break;
 665                 }
 666         }
 667 }
 668
 669 /**
 670  * make_tree_dirty - mark the entire LEB properties tree dirty.
 671  * @c: UBIFS file-system description object
 672  *
 673  * This function is used by the "small" LPT model to cause the entire LEB
 674  * properties tree to be written.  The "small" LPT model does not use LPT
 675  * garbage collection because it is more efficient to write the entire tree
 676  * (because it is small).
 677  *
 678  * This function returns %0 on success and a negative error code on failure.
 679  */
 680 static int make_tree_dirty(struct ubifs_info *c)
 681 {
 682         struct ubifs_pnode *pnode;
 683
 684         pnode = pnode_lookup(c, 0);
 685         while (pnode) {
 686                 do_make_pnode_dirty(c, pnode);
 687                 pnode = next_pnode(c, pnode);
 688                 if (IS_ERR(pnode))
 689                         return PTR_ERR(pnode);
 690         }
 691         return 0;
 692 }
 693
 694 /**
 695  * need_write_all - determine if the LPT area is running out of free space.
 696  * @c: UBIFS file-system description object
 697  *
 698  * This function returns %1 if the LPT area is running out of free space and %0
 699  * if it is not.
 700  */
 701 static int need_write_all(struct ubifs_info *c)
 702 {
 703         long long free = 0;
 704         int i;
 705
 706         for (i = 0; i < c->lpt_lebs; i++) {
 707                 if (i + c->lpt_first == c->nhead_lnum)
 708                         free += c->leb_size - c->nhead_offs;
 709                 else if (c->ltab[i].free == c->leb_size)
 710                         free += c->leb_size;
 711                 else if (c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
 712                         free += c->leb_size;
 713         }
 714         /* Less than twice the size left */
 715         if (free <= c->lpt_sz * 2)
 716                 return 1;
 717         return 0;
 718 }
 719
 720 /**
 721  * lpt_tgc_start - start trivial garbage collection of LPT LEBs.
 722  * @c: UBIFS file-system description object
 723  *
 724  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 725  * free space and so may be reused as soon as the next commit is completed.
 726  * This function is called during start commit to mark LPT LEBs for trivial GC.
 727  */
 728 static void lpt_tgc_start(struct ubifs_info *c)
 729 {
 730         int i;
 731
 732         for (i = 0; i < c->lpt_lebs; i++) {
 733                 if (i + c->lpt_first == c->nhead_lnum)
 734                         continue;
 735                 if (c->ltab[i].dirty > 0 &&
 736                     c->ltab[i].free + c->ltab[i].dirty == c->leb_size) {
 737                         c->ltab[i].tgc = 1;
 738                         c->ltab[i].free = c->leb_size;
 739                         c->ltab[i].dirty = 0;
 740                         dbg_lp("LEB %d", i + c->lpt_first);
 741                 }
 742         }
 743 }
 744
 745 /**
 746  * lpt_tgc_end - end trivial garbage collection of LPT LEBs.
 747  * @c: UBIFS file-system description object
 748  *
 749  * LPT trivial garbage collection is where a LPT LEB contains only dirty and
 750  * free space and so may be reused as soon as the next commit is completed.
 751  * This function is called after the commit is completed (master node has been
 752  * written) and unmaps LPT LEBs that were marked for trivial GC.
 753  */
 754 static int lpt_tgc_end(struct ubifs_info *c)
 755 {
 756         int i, err;
 757
 758         for (i = 0; i < c->lpt_lebs; i++)
 759                 if (c->ltab[i].tgc) {
 760                         err = ubifs_leb_unmap(c, i + c->lpt_first);
 761                         if (err)
 762                                 return err;
 763                         c->ltab[i].tgc = 0;
 764                         dbg_lp("LEB %d", i + c->lpt_first);
 765                 }
 766         return 0;
 767 }
 768
 769 /**
 770  * populate_lsave - fill the lsave array with important LEB numbers.
 771  * @c: the UBIFS file-system description object
 772  *
 773  * This function is only called for the "big" model. It records a small number
 774  * of LEB numbers of important LEBs.  Important LEBs are ones that are (from
 775  * most important to least important): empty, freeable, freeable index, dirty
 776  * index, dirty or free. Upon mount, we read this list of LEB numbers and bring
 777  * their pnodes into memory.  That will stop us from having to scan the LPT
 778  * straight away. For the "small" model we assume that scanning the LPT is no
 779  * big deal.
 780  */
 781 static void populate_lsave(struct ubifs_info *c)
 782 {
 783         struct ubifs_lprops *lprops;
 784         struct ubifs_lpt_heap *heap;
 785         int i, cnt = 0;
 786
 787         ubifs_assert(c->big_lpt);
 788         if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 789                 c->lpt_drty_flgs |= LSAVE_DIRTY;
 790                 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 791         }
 792         list_for_each_entry(lprops, &c->empty_list, list) {
 793                 c->lsave[cnt++] = lprops->lnum;
 794                 if (cnt >= c->lsave_cnt)
 795                         return;
 796         }
 797         list_for_each_entry(lprops, &c->freeable_list, list) {
 798                 c->lsave[cnt++] = lprops->lnum;
 799                 if (cnt >= c->lsave_cnt)
 800                         return;
 801         }
 802         list_for_each_entry(lprops, &c->frdi_idx_list, list) {
 803                 c->lsave[cnt++] = lprops->lnum;
 804                 if (cnt >= c->lsave_cnt)
 805                         return;
 806         }
 807         heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 808         for (i = 0; i < heap->cnt; i++) {
 809                 c->lsave[cnt++] = heap->arr[i]->lnum;
 810                 if (cnt >= c->lsave_cnt)
 811                         return;
 812         }
 813         heap = &c->lpt_heap[LPROPS_DIRTY - 1];
 814         for (i = 0; i < heap->cnt; i++) {
 815                 c->lsave[cnt++] = heap->arr[i]->lnum;
 816                 if (cnt >= c->lsave_cnt)
 817                         return;
 818         }
 819         heap = &c->lpt_heap[LPROPS_FREE - 1];
 820         for (i = 0; i < heap->cnt; i++) {
 821                 c->lsave[cnt++] = heap->arr[i]->lnum;
 822                 if (cnt >= c->lsave_cnt)
 823                         return;
 824         }
 825         /* Fill it up completely */
 826         while (cnt < c->lsave_cnt)
 827                 c->lsave[cnt++] = c->main_first;
 828 }
 829
 830 /**
 831  * nnode_lookup - lookup a nnode in the LPT.
 832  * @c: UBIFS file-system description object
 833  * @i: nnode number
 834  *
 835  * This function returns a pointer to the nnode on success or a negative
 836  * error code on failure.
 837  */
 838 static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i)
 839 {
 840         int err, iip;
 841         struct ubifs_nnode *nnode;
 842
 843         if (!c->nroot) {
 844                 err = ubifs_read_nnode(c, NULL, 0);
 845                 if (err)
 846                         return ERR_PTR(err);
 847         }
 848         nnode = c->nroot;
 849         while (1) {
 850                 iip = i & (UBIFS_LPT_FANOUT - 1);
 851                 i >>= UBIFS_LPT_FANOUT_SHIFT;
 852                 if (!i)
 853                         break;
 854                 nnode = ubifs_get_nnode(c, nnode, iip);
 855                 if (IS_ERR(nnode))
 856                         return nnode;
 857         }
 858         return nnode;
 859 }
 860
 861 /**
 862  * make_nnode_dirty - find a nnode and, if found, make it dirty.
 863  * @c: UBIFS file-system description object
 864  * @node_num: nnode number of nnode to make dirty
 865  * @lnum: LEB number where nnode was written
 866  * @offs: offset where nnode was written
 867  *
 868  * This function is used by LPT garbage collection.  LPT garbage collection is
 869  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 870  * simply involves marking all the nodes in the LEB being garbage-collected as
 871  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 872  * to be reused.
 873  *
 874  * This function returns %0 on success and a negative error code on failure.
 875  */
 876 static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 877                             int offs)
 878 {
 879         struct ubifs_nnode *nnode;
 880
 881         nnode = nnode_lookup(c, node_num);
 882         if (IS_ERR(nnode))
 883                 return PTR_ERR(nnode);
 884         if (nnode->parent) {
 885                 struct ubifs_nbranch *branch;
 886
 887                 branch = &nnode->parent->nbranch[nnode->iip];
 888                 if (branch->lnum != lnum || branch->offs != offs)
 889                         return 0; /* nnode is obsolete */
 890         } else if (c->lpt_lnum != lnum || c->lpt_offs != offs)
 891                         return 0; /* nnode is obsolete */
 892         /* Assumes cnext list is empty i.e. not called during commit */
 893         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 894                 c->dirty_nn_cnt += 1;
 895                 ubifs_add_nnode_dirt(c, nnode);
 896                 /* Mark parent and ancestors dirty too */
 897                 nnode = nnode->parent;
 898                 while (nnode) {
 899                         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
 900                                 c->dirty_nn_cnt += 1;
 901                                 ubifs_add_nnode_dirt(c, nnode);
 902                                 nnode = nnode->parent;
 903                         } else
 904                                 break;
 905                 }
 906         }
 907         return 0;
 908 }
 909
 910 /**
 911  * make_pnode_dirty - find a pnode and, if found, make it dirty.
 912  * @c: UBIFS file-system description object
 913  * @node_num: pnode number of pnode to make dirty
 914  * @lnum: LEB number where pnode was written
 915  * @offs: offset where pnode was written
 916  *
 917  * This function is used by LPT garbage collection.  LPT garbage collection is
 918  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 919  * simply involves marking all the nodes in the LEB being garbage-collected as
 920  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 921  * to be reused.
 922  *
 923  * This function returns %0 on success and a negative error code on failure.
 924  */
 925 static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum,
 926                             int offs)
 927 {
 928         struct ubifs_pnode *pnode;
 929         struct ubifs_nbranch *branch;
 930
 931         pnode = pnode_lookup(c, node_num);
 932         if (IS_ERR(pnode))
 933                 return PTR_ERR(pnode);
 934         branch = &pnode->parent->nbranch[pnode->iip];
 935         if (branch->lnum != lnum || branch->offs != offs)
 936                 return 0;
 937         do_make_pnode_dirty(c, pnode);
 938         return 0;
 939 }
 940
 941 /**
 942  * make_ltab_dirty - make ltab node dirty.
 943  * @c: UBIFS file-system description object
 944  * @lnum: LEB number where ltab was written
 945  * @offs: offset where ltab was written
 946  *
 947  * This function is used by LPT garbage collection.  LPT garbage collection is
 948  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 949  * simply involves marking all the nodes in the LEB being garbage-collected as
 950  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 951  * to be reused.
 952  *
 953  * This function returns %0 on success and a negative error code on failure.
 954  */
 955 static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
 956 {
 957         if (lnum != c->ltab_lnum || offs != c->ltab_offs)
 958                 return 0; /* This ltab node is obsolete */
 959         if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
 960                 c->lpt_drty_flgs |= LTAB_DIRTY;
 961                 ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
 962         }
 963         return 0;
 964 }
 965
 966 /**
 967  * make_lsave_dirty - make lsave node dirty.
 968  * @c: UBIFS file-system description object
 969  * @lnum: LEB number where lsave was written
 970  * @offs: offset where lsave was written
 971  *
 972  * This function is used by LPT garbage collection.  LPT garbage collection is
 973  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
 974  * simply involves marking all the nodes in the LEB being garbage-collected as
 975  * dirty.  The dirty nodes are written next commit, after which the LEB is free
 976  * to be reused.
 977  *
 978  * This function returns %0 on success and a negative error code on failure.
 979  */
 980 static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
 981 {
 982         if (lnum != c->lsave_lnum || offs != c->lsave_offs)
 983                 return 0; /* This lsave node is obsolete */
 984         if (!(c->lpt_drty_flgs & LSAVE_DIRTY)) {
 985                 c->lpt_drty_flgs |= LSAVE_DIRTY;
 986                 ubifs_add_lpt_dirt(c, c->lsave_lnum, c->lsave_sz);
 987         }
 988         return 0;
 989 }
 990
 991 /**
 992  * make_node_dirty - make node dirty.
 993  * @c: UBIFS file-system description object
 994  * @node_type: LPT node type
 995  * @node_num: node number
 996  * @lnum: LEB number where node was written
 997  * @offs: offset where node was written
 998  *
 999  * This function is used by LPT garbage collection.  LPT garbage collection is
1000  * used only for the "big" LPT model (c->big_lpt == 1).  Garbage collection
1001  * simply involves marking all the nodes in the LEB being garbage-collected as
1002  * dirty.  The dirty nodes are written next commit, after which the LEB is free
1003  * to be reused.
1004  *
1005  * This function returns %0 on success and a negative error code on failure.
1006  */
1007 static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num,
1008                            int lnum, int offs)
1009 {
1010         switch (node_type) {
1011         case UBIFS_LPT_NNODE:
1012                 return make_nnode_dirty(c, node_num, lnum, offs);
1013         case UBIFS_LPT_PNODE:
1014                 return make_pnode_dirty(c, node_num, lnum, offs);
1015         case UBIFS_LPT_LTAB:
1016                 return make_ltab_dirty(c, lnum, offs);
1017         case UBIFS_LPT_LSAVE:
1018                 return make_lsave_dirty(c, lnum, offs);
1019         }
1020         return -EINVAL;
1021 }
1022
1023 /**
1024  * get_lpt_node_len - return the length of a node based on its type.
1025  * @c: UBIFS file-system description object
1026  * @node_type: LPT node type
1027  */
1028 static int get_lpt_node_len(struct ubifs_info *c, int node_type)
1029 {
1030         switch (node_type) {
1031         case UBIFS_LPT_NNODE:
1032                 return c->nnode_sz;
1033         case UBIFS_LPT_PNODE:
1034                 return c->pnode_sz;
1035         case UBIFS_LPT_LTAB:
1036                 return c->ltab_sz;
1037         case UBIFS_LPT_LSAVE:
1038                 return c->lsave_sz;
1039         }
1040         return 0;
1041 }
1042
1043 /**
1044  * get_pad_len - return the length of padding in a buffer.
1045  * @c: UBIFS file-system description object
1046  * @buf: buffer
1047  * @len: length of buffer
1048  */
1049 static int get_pad_len(struct ubifs_info *c, uint8_t *buf, int len)
1050 {
1051         int offs, pad_len;
1052
1053         if (c->min_io_size == 1)
1054                 return 0;
1055         offs = c->leb_size - len;
1056         pad_len = ALIGN(offs, c->min_io_size) - offs;
1057         return pad_len;
1058 }
1059
1060 /**
1061  * get_lpt_node_type - return type (and node number) of a node in a buffer.
1062  * @c: UBIFS file-system description object
1063  * @buf: buffer
1064  * @node_num: node number is returned here
1065  */
1066 static int get_lpt_node_type(struct ubifs_info *c, uint8_t *buf, int *node_num)
1067 {
1068         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1069         int pos = 0, node_type;
1070
1071         node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1072         *node_num = ubifs_unpack_bits(&addr, &pos, c->pcnt_bits);
1073         return node_type;
1074 }
1075
1076 /**
1077  * is_a_node - determine if a buffer contains a node.
1078  * @c: UBIFS file-system description object
1079  * @buf: buffer
1080  * @len: length of buffer
1081  *
1082  * This function returns %1 if the buffer contains a node or %0 if it does not.
1083  */
1084 static int is_a_node(struct ubifs_info *c, uint8_t *buf, int len)
1085 {
1086         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1087         int pos = 0, node_type, node_len;
1088         uint16_t crc, calc_crc;
1089
1090         if (len < UBIFS_LPT_CRC_BYTES + (UBIFS_LPT_TYPE_BITS + 7) / 8)
1091                 return 0;
1092         node_type = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_TYPE_BITS);
1093         if (node_type == UBIFS_LPT_NOT_A_NODE)
1094                 return 0;
1095         node_len = get_lpt_node_len(c, node_type);
1096         if (!node_len || node_len > len)
1097                 return 0;
1098         pos = 0;
1099         addr = buf;
1100         crc = ubifs_unpack_bits(&addr, &pos, UBIFS_LPT_CRC_BITS);
1101         calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
1102                          node_len - UBIFS_LPT_CRC_BYTES);
1103         if (crc != calc_crc)
1104                 return 0;
1105         return 1;
1106 }
1107
1108
1109 /**
1110  * lpt_gc_lnum - garbage collect a LPT LEB.
1111  * @c: UBIFS file-system description object
1112  * @lnum: LEB number to garbage collect
1113  *
1114  * LPT garbage collection is used only for the "big" LPT model
1115  * (c->big_lpt == 1).  Garbage collection simply involves marking all the nodes
1116  * in the LEB being garbage-collected as dirty.  The dirty nodes are written
1117  * next commit, after which the LEB is free to be reused.
1118  *
1119  * This function returns %0 on success and a negative error code on failure.
1120  */
1121 static int lpt_gc_lnum(struct ubifs_info *c, int lnum)
1122 {
1123         int err, len = c->leb_size, node_type, node_num, node_len, offs;
1124         void *buf = c->lpt_buf;
1125
1126         dbg_lp("LEB %d", lnum);
1127         err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1128         if (err) {
1129                 ubifs_err("cannot read LEB %d, error %d", lnum, err);
1130                 return err;
1131         }
1132         while (1) {
1133                 if (!is_a_node(c, buf, len)) {
1134                         int pad_len;
1135
1136                         pad_len = get_pad_len(c, buf, len);
1137                         if (pad_len) {
1138                                 buf += pad_len;
1139                                 len -= pad_len;
1140                                 continue;
1141                         }
1142                         return 0;
1143                 }
1144                 node_type = get_lpt_node_type(c, buf, &node_num);
1145                 node_len = get_lpt_node_len(c, node_type);
1146                 offs = c->leb_size - len;
1147                 ubifs_assert(node_len != 0);
1148                 mutex_lock(&c->lp_mutex);
1149                 err = make_node_dirty(c, node_type, node_num, lnum, offs);
1150                 mutex_unlock(&c->lp_mutex);
1151                 if (err)
1152                         return err;
1153                 buf += node_len;
1154                 len -= node_len;
1155         }
1156         return 0;
1157 }
1158
1159 /**
1160  * lpt_gc - LPT garbage collection.
1161  * @c: UBIFS file-system description object
1162  *
1163  * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'.
1164  * Returns %0 on success and a negative error code on failure.
1165  */
1166 static int lpt_gc(struct ubifs_info *c)
1167 {
1168         int i, lnum = -1, dirty = 0;
1169
1170         mutex_lock(&c->lp_mutex);
1171         for (i = 0; i < c->lpt_lebs; i++) {
1172                 ubifs_assert(!c->ltab[i].tgc);
1173                 if (i + c->lpt_first == c->nhead_lnum ||
1174                     c->ltab[i].free + c->ltab[i].dirty == c->leb_size)
1175                         continue;
1176                 if (c->ltab[i].dirty > dirty) {
1177                         dirty = c->ltab[i].dirty;
1178                         lnum = i + c->lpt_first;
1179                 }
1180         }
1181         mutex_unlock(&c->lp_mutex);
1182         if (lnum == -1)
1183                 return -ENOSPC;
1184         return lpt_gc_lnum(c, lnum);
1185 }
1186
1187 /**
1188  * ubifs_lpt_start_commit - UBIFS commit starts.
1189  * @c: the UBIFS file-system description object
1190  *
1191  * This function has to be called when UBIFS starts the commit operation.
1192  * This function "freezes" all currently dirty LEB properties and does not
1193  * change them anymore. Further changes are saved and tracked separately
1194  * because they are not part of this commit. This function returns zero in case
1195  * of success and a negative error code in case of failure.
1196  */
1197 int ubifs_lpt_start_commit(struct ubifs_info *c)
1198 {
1199         int err, cnt;
1200
1201         dbg_lp("");
1202
1203         mutex_lock(&c->lp_mutex);
1204         err = dbg_chk_lpt_free_spc(c);
1205         if (err)
1206                 goto out;
1207         err = dbg_check_ltab(c);
1208         if (err)
1209                 goto out;
1210
1211         if (c->check_lpt_free) {
1212                 /*
1213                  * We ensure there is enough free space in
1214                  * ubifs_lpt_post_commit() by marking nodes dirty. That
1215                  * information is lost when we unmount, so we also need
1216                  * to check free space once after mounting also.
1217                  */
1218                 c->check_lpt_free = 0;
1219                 while (need_write_all(c)) {
1220                         mutex_unlock(&c->lp_mutex);
1221                         err = lpt_gc(c);
1222                         if (err)
1223                                 return err;
1224                         mutex_lock(&c->lp_mutex);
1225                 }
1226         }
1227
1228         lpt_tgc_start(c);
1229
1230         if (!c->dirty_pn_cnt) {
1231                 dbg_cmt("no cnodes to commit");
1232                 err = 0;
1233                 goto out;
1234         }
1235
1236         if (!c->big_lpt && need_write_all(c)) {
1237                 /* If needed, write everything */
1238                 err = make_tree_dirty(c);
1239                 if (err)
1240                         goto out;
1241                 lpt_tgc_start(c);
1242         }
1243
1244         if (c->big_lpt)
1245                 populate_lsave(c);
1246
1247         cnt = get_cnodes_to_commit(c);
1248         ubifs_assert(cnt != 0);
1249
1250         err = layout_cnodes(c);
1251         if (err)
1252                 goto out;
1253
1254         /* Copy the LPT's own lprops for end commit to write */
1255         memcpy(c->ltab_cmt, c->ltab,
1256                sizeof(struct ubifs_lpt_lprops) * c->lpt_lebs);
1257         c->lpt_drty_flgs &= ~(LTAB_DIRTY | LSAVE_DIRTY);
1258
1259 out:
1260         mutex_unlock(&c->lp_mutex);
1261         return err;
1262 }
1263
1264 /**
1265  * free_obsolete_cnodes - free obsolete cnodes for commit end.
1266  * @c: UBIFS file-system description object
1267  */
1268 static void free_obsolete_cnodes(struct ubifs_info *c)
1269 {
1270         struct ubifs_cnode *cnode, *cnext;
1271
1272         cnext = c->lpt_cnext;
1273         if (!cnext)
1274                 return;
1275         do {
1276                 cnode = cnext;
1277                 cnext = cnode->cnext;
1278                 if (test_bit(OBSOLETE_CNODE, &cnode->flags))
1279                         kfree(cnode);
1280                 else
1281                         cnode->cnext = NULL;
1282         } while (cnext != c->lpt_cnext);
1283         c->lpt_cnext = NULL;
1284 }
1285
1286 /**
1287  * ubifs_lpt_end_commit - finish the commit operation.
1288  * @c: the UBIFS file-system description object
1289  *
1290  * This function has to be called when the commit operation finishes. It
1291  * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to
1292  * the media. Returns zero in case of success and a negative error code in case
1293  * of failure.
1294  */
1295 int ubifs_lpt_end_commit(struct ubifs_info *c)
1296 {
1297         int err;
1298
1299         dbg_lp("");
1300
1301         if (!c->lpt_cnext)
1302                 return 0;
1303
1304         err = write_cnodes(c);
1305         if (err)
1306                 return err;
1307
1308         mutex_lock(&c->lp_mutex);
1309         free_obsolete_cnodes(c);
1310         mutex_unlock(&c->lp_mutex);
1311
1312         return 0;
1313 }
1314
1315 /**
1316  * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC.
1317  * @c: UBIFS file-system description object
1318  *
1319  * LPT trivial GC is completed after a commit. Also LPT GC is done after a
1320  * commit for the "big" LPT model.
1321  */
1322 int ubifs_lpt_post_commit(struct ubifs_info *c)
1323 {
1324         int err;
1325
1326         mutex_lock(&c->lp_mutex);
1327         err = lpt_tgc_end(c);
1328         if (err)
1329                 goto out;
1330         if (c->big_lpt)
1331                 while (need_write_all(c)) {
1332                         mutex_unlock(&c->lp_mutex);
1333                         err = lpt_gc(c);
1334                         if (err)
1335                                 return err;
1336                         mutex_lock(&c->lp_mutex);
1337                 }
1338 out:
1339         mutex_unlock(&c->lp_mutex);
1340         return err;
1341 }
1342
1343 /**
1344  * first_nnode - find the first nnode in memory.
1345  * @c: UBIFS file-system description object
1346  * @hght: height of tree where nnode found is returned here
1347  *
1348  * This function returns a pointer to the nnode found or %NULL if no nnode is
1349  * found. This function is a helper to 'ubifs_lpt_free()'.
1350  */
1351 static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght)
1352 {
1353         struct ubifs_nnode *nnode;
1354         int h, i, found;
1355
1356         nnode = c->nroot;
1357         *hght = 0;
1358         if (!nnode)
1359                 return NULL;
1360         for (h = 1; h < c->lpt_hght; h++) {
1361                 found = 0;
1362                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1363                         if (nnode->nbranch[i].nnode) {
1364                                 found = 1;
1365                                 nnode = nnode->nbranch[i].nnode;
1366                                 *hght = h;
1367                                 break;
1368                         }
1369                 }
1370                 if (!found)
1371                         break;
1372         }
1373         return nnode;
1374 }
1375
1376 /**
1377  * next_nnode - find the next nnode in memory.
1378  * @c: UBIFS file-system description object
1379  * @nnode: nnode from which to start.
1380  * @hght: height of tree where nnode is, is passed and returned here
1381  *
1382  * This function returns a pointer to the nnode found or %NULL if no nnode is
1383  * found. This function is a helper to 'ubifs_lpt_free()'.
1384  */
1385 static struct ubifs_nnode *next_nnode(struct ubifs_info *c,
1386                                       struct ubifs_nnode *nnode, int *hght)
1387 {
1388         struct ubifs_nnode *parent;
1389         int iip, h, i, found;
1390
1391         parent = nnode->parent;
1392         if (!parent)
1393                 return NULL;
1394         if (nnode->iip == UBIFS_LPT_FANOUT - 1) {
1395                 *hght -= 1;
1396                 return parent;
1397         }
1398         for (iip = nnode->iip + 1; iip < UBIFS_LPT_FANOUT; iip++) {
1399                 nnode = parent->nbranch[iip].nnode;
1400                 if (nnode)
1401                         break;
1402         }
1403         if (!nnode) {
1404                 *hght -= 1;
1405                 return parent;
1406         }
1407         for (h = *hght + 1; h < c->lpt_hght; h++) {
1408                 found = 0;
1409                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1410                         if (nnode->nbranch[i].nnode) {
1411                                 found = 1;
1412                                 nnode = nnode->nbranch[i].nnode;
1413                                 *hght = h;
1414                                 break;
1415                         }
1416                 }
1417                 if (!found)
1418                         break;
1419         }
1420         return nnode;
1421 }
1422
1423 /**
1424  * ubifs_lpt_free - free resources owned by the LPT.
1425  * @c: UBIFS file-system description object
1426  * @wr_only: free only resources used for writing
1427  */
1428 void ubifs_lpt_free(struct ubifs_info *c, int wr_only)
1429 {
1430         struct ubifs_nnode *nnode;
1431         int i, hght;
1432
1433         /* Free write-only things first */
1434
1435         free_obsolete_cnodes(c); /* Leftover from a failed commit */
1436
1437         vfree(c->ltab_cmt);
1438         c->ltab_cmt = NULL;
1439         vfree(c->lpt_buf);
1440         c->lpt_buf = NULL;
1441         kfree(c->lsave);
1442         c->lsave = NULL;
1443
1444         if (wr_only)
1445                 return;
1446
1447         /* Now free the rest */
1448
1449         nnode = first_nnode(c, &hght);
1450         while (nnode) {
1451                 for (i = 0; i < UBIFS_LPT_FANOUT; i++)
1452                         kfree(nnode->nbranch[i].nnode);
1453                 nnode = next_nnode(c, nnode, &hght);
1454         }
1455         for (i = 0; i < LPROPS_HEAP_CNT; i++)
1456                 kfree(c->lpt_heap[i].arr);
1457         kfree(c->dirty_idx.arr);
1458         kfree(c->nroot);
1459         vfree(c->ltab);
1460         kfree(c->lpt_nod_buf);
1461 }
1462
1463 #ifdef CONFIG_UBIFS_FS_DEBUG
1464
1465 /**
1466  * dbg_is_all_ff - determine if a buffer contains only 0xff bytes.
1467  * @buf: buffer
1468  * @len: buffer length
1469  */
1470 static int dbg_is_all_ff(uint8_t *buf, int len)
1471 {
1472         int i;
1473
1474         for (i = 0; i < len; i++)
1475                 if (buf[i] != 0xff)
1476                         return 0;
1477         return 1;
1478 }
1479
1480 /**
1481  * dbg_is_nnode_dirty - determine if a nnode is dirty.
1482  * @c: the UBIFS file-system description object
1483  * @lnum: LEB number where nnode was written
1484  * @offs: offset where nnode was written
1485  */
1486 static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs)
1487 {
1488         struct ubifs_nnode *nnode;
1489         int hght;
1490
1491         /* Entire tree is in memory so first_nnode / next_nnode are ok */
1492         nnode = first_nnode(c, &hght);
1493         for (; nnode; nnode = next_nnode(c, nnode, &hght)) {
1494                 struct ubifs_nbranch *branch;
1495
1496                 cond_resched();
1497                 if (nnode->parent) {
1498                         branch = &nnode->parent->nbranch[nnode->iip];
1499                         if (branch->lnum != lnum || branch->offs != offs)
1500                                 continue;
1501                         if (test_bit(DIRTY_CNODE, &nnode->flags))
1502                                 return 1;
1503                         return 0;
1504                 } else {
1505                         if (c->lpt_lnum != lnum || c->lpt_offs != offs)
1506                                 continue;
1507                         if (test_bit(DIRTY_CNODE, &nnode->flags))
1508                                 return 1;
1509                         return 0;
1510                 }
1511         }
1512         return 1;
1513 }
1514
1515 /**
1516  * dbg_is_pnode_dirty - determine if a pnode is dirty.
1517  * @c: the UBIFS file-system description object
1518  * @lnum: LEB number where pnode was written
1519  * @offs: offset where pnode was written
1520  */
1521 static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs)
1522 {
1523         int i, cnt;
1524
1525         cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1526         for (i = 0; i < cnt; i++) {
1527                 struct ubifs_pnode *pnode;
1528                 struct ubifs_nbranch *branch;
1529
1530                 cond_resched();
1531                 pnode = pnode_lookup(c, i);
1532                 if (IS_ERR(pnode))
1533                         return PTR_ERR(pnode);
1534                 branch = &pnode->parent->nbranch[pnode->iip];
1535                 if (branch->lnum != lnum || branch->offs != offs)
1536                         continue;
1537                 if (test_bit(DIRTY_CNODE, &pnode->flags))
1538                         return 1;
1539                 return 0;
1540         }
1541         return 1;
1542 }
1543
1544 /**
1545  * dbg_is_ltab_dirty - determine if a ltab node is dirty.
1546  * @c: the UBIFS file-system description object
1547  * @lnum: LEB number where ltab node was written
1548  * @offs: offset where ltab node was written
1549  */
1550 static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs)
1551 {
1552         if (lnum != c->ltab_lnum || offs != c->ltab_offs)
1553                 return 1;
1554         return (c->lpt_drty_flgs & LTAB_DIRTY) != 0;
1555 }
1556
1557 /**
1558  * dbg_is_lsave_dirty - determine if a lsave node is dirty.
1559  * @c: the UBIFS file-system description object
1560  * @lnum: LEB number where lsave node was written
1561  * @offs: offset where lsave node was written
1562  */
1563 static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs)
1564 {
1565         if (lnum != c->lsave_lnum || offs != c->lsave_offs)
1566                 return 1;
1567         return (c->lpt_drty_flgs & LSAVE_DIRTY) != 0;
1568 }
1569
1570 /**
1571  * dbg_is_node_dirty - determine if a node is dirty.
1572  * @c: the UBIFS file-system description object
1573  * @node_type: node type
1574  * @lnum: LEB number where node was written
1575  * @offs: offset where node was written
1576  */
1577 static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum,
1578                              int offs)
1579 {
1580         switch (node_type) {
1581         case UBIFS_LPT_NNODE:
1582                 return dbg_is_nnode_dirty(c, lnum, offs);
1583         case UBIFS_LPT_PNODE:
1584                 return dbg_is_pnode_dirty(c, lnum, offs);
1585         case UBIFS_LPT_LTAB:
1586                 return dbg_is_ltab_dirty(c, lnum, offs);
1587         case UBIFS_LPT_LSAVE:
1588                 return dbg_is_lsave_dirty(c, lnum, offs);
1589         }
1590         return 1;
1591 }
1592
1593 /**
1594  * dbg_check_ltab_lnum - check the ltab for a LPT LEB number.
1595  * @c: the UBIFS file-system description object
1596  * @lnum: LEB number where node was written
1597  * @offs: offset where node was written
1598  *
1599  * This function returns %0 on success and a negative error code on failure.
1600  */
1601 static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum)
1602 {
1603         int err, len = c->leb_size, dirty = 0, node_type, node_num, node_len;
1604         int ret;
1605         void *buf = c->dbg_buf;
1606
1607         dbg_lp("LEB %d", lnum);
1608         err = ubi_read(c->ubi, lnum, buf, 0, c->leb_size);
1609         if (err) {
1610                 dbg_msg("ubi_read failed, LEB %d, error %d", lnum, err);
1611                 return err;
1612         }
1613         while (1) {
1614                 if (!is_a_node(c, buf, len)) {
1615                         int i, pad_len;
1616
1617                         pad_len = get_pad_len(c, buf, len);
1618                         if (pad_len) {
1619                                 buf += pad_len;
1620                                 len -= pad_len;
1621                                 dirty += pad_len;
1622                                 continue;
1623                         }
1624                         if (!dbg_is_all_ff(buf, len)) {
1625                                 dbg_msg("invalid empty space in LEB %d at %d",
1626                                         lnum, c->leb_size - len);
1627                                 err = -EINVAL;
1628                         }
1629                         i = lnum - c->lpt_first;
1630                         if (len != c->ltab[i].free) {
1631                                 dbg_msg("invalid free space in LEB %d "
1632                                         "(free %d, expected %d)",
1633                                         lnum, len, c->ltab[i].free);
1634                                 err = -EINVAL;
1635                         }
1636                         if (dirty != c->ltab[i].dirty) {
1637                                 dbg_msg("invalid dirty space in LEB %d "
1638                                         "(dirty %d, expected %d)",
1639                                         lnum, dirty, c->ltab[i].dirty);
1640                                 err = -EINVAL;
1641                         }
1642                         return err;
1643                 }
1644                 node_type = get_lpt_node_type(c, buf, &node_num);
1645                 node_len = get_lpt_node_len(c, node_type);
1646                 ret = dbg_is_node_dirty(c, node_type, lnum, c->leb_size - len);
1647                 if (ret == 1)
1648                         dirty += node_len;
1649                 buf += node_len;
1650                 len -= node_len;
1651         }
1652 }
1653
1654 /**
1655  * dbg_check_ltab - check the free and dirty space in the ltab.
1656  * @c: the UBIFS file-system description object
1657  *
1658  * This function returns %0 on success and a negative error code on failure.
1659  */
1660 int dbg_check_ltab(struct ubifs_info *c)
1661 {
1662         int lnum, err, i, cnt;
1663
1664         if (!(ubifs_chk_flags & UBIFS_CHK_LPROPS))
1665                 return 0;
1666
1667         /* Bring the entire tree into memory */
1668         cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
1669         for (i = 0; i < cnt; i++) {
1670                 struct ubifs_pnode *pnode;
1671
1672                 pnode = pnode_lookup(c, i);
1673                 if (IS_ERR(pnode))
1674                         return PTR_ERR(pnode);
1675                 cond_resched();
1676         }
1677
1678         /* Check nodes */
1679         err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)c->nroot, 0, 0);
1680         if (err)
1681                 return err;
1682
1683         /* Check each LEB */
1684         for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) {
1685                 err = dbg_check_ltab_lnum(c, lnum);
1686                 if (err) {
1687                         dbg_err("failed at LEB %d", lnum);
1688                         return err;
1689                 }
1690         }
1691
1692         dbg_lp("succeeded");
1693         return 0;
1694 }
1695
1696 /**
1697  * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT.
1698  * @c: the UBIFS file-system description object
1699  *
1700  * This function returns %0 on success and a negative error code on failure.
1701  */
1702 int dbg_chk_lpt_free_spc(struct ubifs_info *c)
1703 {
1704         long long free = 0;
1705         int i;
1706
1707         for (i = 0; i < c->lpt_lebs; i++) {
1708                 if (c->ltab[i].tgc || c->ltab[i].cmt)
1709                         continue;
1710                 if (i + c->lpt_first == c->nhead_lnum)
1711                         free += c->leb_size - c->nhead_offs;
1712                 else if (c->ltab[i].free == c->leb_size)
1713                         free += c->leb_size;
1714         }
1715         if (free < c->lpt_sz) {
1716                 dbg_err("LPT space error: free %lld lpt_sz %lld",
1717                         free, c->lpt_sz);
1718                 dbg_dump_lpt_info(c);
1719                 return -EINVAL;
1720         }
1721         return 0;
1722 }
1723
1724 /**
1725  * dbg_chk_lpt_sz - check LPT does not write more than LPT size.
1726  * @c: the UBIFS file-system description object
1727  * @action: action
1728  * @len: length written
1729  *
1730  * This function returns %0 on success and a negative error code on failure.
1731  */
1732 int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len)
1733 {
1734         long long chk_lpt_sz, lpt_sz;
1735         int err = 0;
1736
1737         switch (action) {
1738         case 0:
1739                 c->chk_lpt_sz = 0;
1740                 c->chk_lpt_sz2 = 0;
1741                 c->chk_lpt_lebs = 0;
1742                 c->chk_lpt_wastage = 0;
1743                 if (c->dirty_pn_cnt > c->pnode_cnt) {
1744                         dbg_err("dirty pnodes %d exceed max %d",
1745                                 c->dirty_pn_cnt, c->pnode_cnt);
1746                         err = -EINVAL;
1747                 }
1748                 if (c->dirty_nn_cnt > c->nnode_cnt) {
1749                         dbg_err("dirty nnodes %d exceed max %d",
1750                                 c->dirty_nn_cnt, c->nnode_cnt);
1751                         err = -EINVAL;
1752                 }
1753                 return err;
1754         case 1:
1755                 c->chk_lpt_sz += len;
1756                 return 0;
1757         case 2:
1758                 c->chk_lpt_sz += len;
1759                 c->chk_lpt_wastage += len;
1760                 c->chk_lpt_lebs += 1;
1761                 return 0;
1762         case 3:
1763                 chk_lpt_sz = c->leb_size;
1764                 chk_lpt_sz *= c->chk_lpt_lebs;
1765                 chk_lpt_sz += len - c->nhead_offs;
1766                 if (c->chk_lpt_sz != chk_lpt_sz) {
1767                         dbg_err("LPT wrote %lld but space used was %lld",
1768                                 c->chk_lpt_sz, chk_lpt_sz);
1769                         err = -EINVAL;
1770                 }
1771                 if (c->chk_lpt_sz > c->lpt_sz) {
1772                         dbg_err("LPT wrote %lld but lpt_sz is %lld",
1773                                 c->chk_lpt_sz, c->lpt_sz);
1774                         err = -EINVAL;
1775                 }
1776                 if (c->chk_lpt_sz2 && c->chk_lpt_sz != c->chk_lpt_sz2) {
1777                         dbg_err("LPT layout size %lld but wrote %lld",
1778                                 c->chk_lpt_sz, c->chk_lpt_sz2);
1779                         err = -EINVAL;
1780                 }
1781                 if (c->chk_lpt_sz2 && c->new_nhead_offs != len) {
1782                         dbg_err("LPT new nhead offs: expected %d was %d",
1783                                 c->new_nhead_offs, len);
1784                         err = -EINVAL;
1785                 }
1786                 lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
1787                 lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
1788                 lpt_sz += c->ltab_sz;
1789                 if (c->big_lpt)
1790                         lpt_sz += c->lsave_sz;
1791                 if (c->chk_lpt_sz - c->chk_lpt_wastage > lpt_sz) {
1792                         dbg_err("LPT chk_lpt_sz %lld + waste %lld exceeds %lld",
1793                                 c->chk_lpt_sz, c->chk_lpt_wastage, lpt_sz);
1794                         err = -EINVAL;
1795                 }
1796                 if (err)
1797                         dbg_dump_lpt_info(c);
1798                 c->chk_lpt_sz2 = c->chk_lpt_sz;
1799                 c->chk_lpt_sz = 0;
1800                 c->chk_lpt_wastage = 0;
1801                 c->chk_lpt_lebs = 0;
1802                 c->new_nhead_offs = len;
1803                 return err;
1804         case 4:
1805                 c->chk_lpt_sz += len;
1806                 c->chk_lpt_wastage += len;
1807                 return 0;
1808         default:
1809                 return -EINVAL;
1810         }
1811 }
1812
1813 #endif /* CONFIG_UBIFS_FS_DEBUG */