linux/fs/ubifs/tnc_commit.c
<<
>>
Prefs
   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 (\xD0\x91\xD0\xB8\xD1\x82\xD1\x8E\xD1\x86\xD0\xBA\xD0\xB8\xD0\xB9 \xD0\x90\xD1\x80\xD1\x82\xD1\x91\xD0\xBC)
  21 */
  22
  23/* This file implements TNC functions for committing */
  24
  25#include "ubifs.h"
  26
  27/**
  28 * make_idx_node - make an index node for fill-the-gaps method of TNC commit.
  29 * @c: UBIFS file-system description object
  30 * @idx: buffer in which to place new index node
  31 * @znode: znode from which to make new index node
  32 * @lnum: LEB number where new index node will be written
  33 * @offs: offset where new index node will be written
  34 * @len: length of new index node
  35 */
  36static int make_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx,
  37                         struct ubifs_znode *znode, int lnum, int offs, int len)
  38{
  39        struct ubifs_znode *zp;
  40        int i, err;
  41
  42        /* Make index node */
  43        idx->ch.node_type = UBIFS_IDX_NODE;
  44        idx->child_cnt = cpu_to_le16(znode->child_cnt);
  45        idx->level = cpu_to_le16(znode->level);
  46        for (i = 0; i < znode->child_cnt; i++) {
  47                struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
  48                struct ubifs_zbranch *zbr = &znode->zbranch[i];
  49
  50                key_write_idx(c, &zbr->key, &br->key);
  51                br->lnum = cpu_to_le32(zbr->lnum);
  52                br->offs = cpu_to_le32(zbr->offs);
  53                br->len = cpu_to_le32(zbr->len);
  54                if (!zbr->lnum || !zbr->len) {
  55                        ubifs_err("bad ref in znode");
  56                        dbg_dump_znode(c, znode);
  57                        if (zbr->znode)
  58                                dbg_dump_znode(c, zbr->znode);
  59                }
  60        }
  61        ubifs_prepare_node(c, idx, len, 0);
  62
  63#ifdef CONFIG_UBIFS_FS_DEBUG
  64        znode->lnum = lnum;
  65        znode->offs = offs;
  66        znode->len = len;
  67#endif
  68
  69        err = insert_old_idx_znode(c, znode);
  70
  71        /* Update the parent */
  72        zp = znode->parent;
  73        if (zp) {
  74                struct ubifs_zbranch *zbr;
  75
  76                zbr = &zp->zbranch[znode->iip];
  77                zbr->lnum = lnum;
  78                zbr->offs = offs;
  79                zbr->len = len;
  80        } else {
  81                c->zroot.lnum = lnum;
  82                c->zroot.offs = offs;
  83                c->zroot.len = len;
  84        }
  85        c->calc_idx_sz += ALIGN(len, 8);
  86
  87        atomic_long_dec(&c->dirty_zn_cnt);
  88
  89        ubifs_assert(ubifs_zn_dirty(znode));
  90        ubifs_assert(test_bit(COW_ZNODE, &znode->flags));
  91
  92        __clear_bit(DIRTY_ZNODE, &znode->flags);
  93        __clear_bit(COW_ZNODE, &znode->flags);
  94
  95        return err;
  96}
  97
  98/**
  99 * fill_gap - make index nodes in gaps in dirty index LEBs.
 100 * @c: UBIFS file-system description object
 101 * @lnum: LEB number that gap appears in
 102 * @gap_start: offset of start of gap
 103 * @gap_end: offset of end of gap
 104 * @dirt: adds dirty space to this
 105 *
 106 * This function returns the number of index nodes written into the gap.
 107 */
 108static int fill_gap(struct ubifs_info *c, int lnum, int gap_start, int gap_end,
 109                    int *dirt)
 110{
 111        int len, gap_remains, gap_pos, written, pad_len;
 112
 113        ubifs_assert((gap_start & 7) == 0);
 114        ubifs_assert((gap_end & 7) == 0);
 115        ubifs_assert(gap_end >= gap_start);
 116
 117        gap_remains = gap_end - gap_start;
 118        if (!gap_remains)
 119                return 0;
 120        gap_pos = gap_start;
 121        written = 0;
 122        while (c->enext) {
 123                len = ubifs_idx_node_sz(c, c->enext->child_cnt);
 124                if (len < gap_remains) {
 125                        struct ubifs_znode *znode = c->enext;
 126                        const int alen = ALIGN(len, 8);
 127                        int err;
 128
 129                        ubifs_assert(alen <= gap_remains);
 130                        err = make_idx_node(c, c->ileb_buf + gap_pos, znode,
 131                                            lnum, gap_pos, len);
 132                        if (err)
 133                                return err;
 134                        gap_remains -= alen;
 135                        gap_pos += alen;
 136                        c->enext = znode->cnext;
 137                        if (c->enext == c->cnext)
 138                                c->enext = NULL;
 139                        written += 1;
 140                } else
 141                        break;
 142        }
 143        if (gap_end == c->leb_size) {
 144                c->ileb_len = ALIGN(gap_pos, c->min_io_size);
 145                /* Pad to end of min_io_size */
 146                pad_len = c->ileb_len - gap_pos;
 147        } else
 148                /* Pad to end of gap */
 149                pad_len = gap_remains;
 150        dbg_gc("LEB %d:%d to %d len %d nodes written %d wasted bytes %d",
 151               lnum, gap_start, gap_end, gap_end - gap_start, written, pad_len);
 152        ubifs_pad(c, c->ileb_buf + gap_pos, pad_len);
 153        *dirt += pad_len;
 154        return written;
 155}
 156
 157/**
 158 * find_old_idx - find an index node obsoleted since the last commit start.
 159 * @c: UBIFS file-system description object
 160 * @lnum: LEB number of obsoleted index node
 161 * @offs: offset of obsoleted index node
 162 *
 163 * Returns %1 if found and %0 otherwise.
 164 */
 165static int find_old_idx(struct ubifs_info *c, int lnum, int offs)
 166{
 167        struct ubifs_old_idx *o;
 168        struct rb_node *p;
 169
 170        p = c->old_idx.rb_node;
 171        while (p) {
 172                o = rb_entry(p, struct ubifs_old_idx, rb);
 173                if (lnum < o->lnum)
 174                        p = p->rb_left;
 175                else if (lnum > o->lnum)
 176                        p = p->rb_right;
 177                else if (offs < o->offs)
 178                        p = p->rb_left;
 179                else if (offs > o->offs)
 180                        p = p->rb_right;
 181                else
 182                        return 1;
 183        }
 184        return 0;
 185}
 186
 187/**
 188 * is_idx_node_in_use - determine if an index node can be overwritten.
 189 * @c: UBIFS file-system description object
 190 * @key: key of index node
 191 * @level: index node level
 192 * @lnum: LEB number of index node
 193 * @offs: offset of index node
 194 *
 195 * If @key / @lnum / @offs identify an index node that was not part of the old
 196 * index, then this function returns %0 (obsolete).  Else if the index node was
 197 * part of the old index but is now dirty %1 is returned, else if it is clean %2
 198 * is returned. A negative error code is returned on failure.
 199 */
 200static int is_idx_node_in_use(struct ubifs_info *c, union ubifs_key *key,
 201                              int level, int lnum, int offs)
 202{
 203        int ret;
 204
 205        ret = is_idx_node_in_tnc(c, key, level, lnum, offs);
 206        if (ret < 0)
 207                return ret; /* Error code */
 208        if (ret == 0)
 209                if (find_old_idx(c, lnum, offs))
 210                        return 1;
 211        return ret;
 212}
 213
 214/**
 215 * layout_leb_in_gaps - layout index nodes using in-the-gaps method.
 216 * @c: UBIFS file-system description object
 217 * @p: return LEB number here
 218 *
 219 * This function lays out new index nodes for dirty znodes using in-the-gaps
 220 * method of TNC commit.
 221 * This function merely puts the next znode into the next gap, making no attempt
 222 * to try to maximise the number of znodes that fit.
 223 * This function returns the number of index nodes written into the gaps, or a
 224 * negative error code on failure.
 225 */
 226static int layout_leb_in_gaps(struct ubifs_info *c, int *p)
 227{
 228        struct ubifs_scan_leb *sleb;
 229        struct ubifs_scan_node *snod;
 230        int lnum, dirt = 0, gap_start, gap_end, err, written, tot_written;
 231
 232        tot_written = 0;
 233        /* Get an index LEB with lots of obsolete index nodes */
 234        lnum = ubifs_find_dirty_idx_leb(c);
 235        if (lnum < 0)
 236                /*
 237                 * There also may be dirt in the index head that could be
 238                 * filled, however we do not check there at present.
 239                 */
 240                return lnum; /* Error code */
 241        *p = lnum;
 242        dbg_gc("LEB %d", lnum);
 243        /*
 244         * Scan the index LEB.  We use the generic scan for this even though
 245         * it is more comprehensive and less efficient than is needed for this
 246         * purpose.
 247         */
 248        sleb = ubifs_scan(c, lnum, 0, c->ileb_buf, 0);
 249        c->ileb_len = 0;
 250        if (IS_ERR(sleb))
 251                return PTR_ERR(sleb);
 252        gap_start = 0;
 253        list_for_each_entry(snod, &sleb->nodes, list) {
 254                struct ubifs_idx_node *idx;
 255                int in_use, level;
 256
 257                ubifs_assert(snod->type == UBIFS_IDX_NODE);
 258                idx = snod->node;
 259                key_read(c, ubifs_idx_key(c, idx), &snod->key);
 260                level = le16_to_cpu(idx->level);
 261                /* Determine if the index node is in use (not obsolete) */
 262                in_use = is_idx_node_in_use(c, &snod->key, level, lnum,
 263                                            snod->offs);
 264                if (in_use < 0) {
 265                        ubifs_scan_destroy(sleb);
 266                        return in_use; /* Error code */
 267                }
 268                if (in_use) {
 269                        if (in_use == 1)
 270                                dirt += ALIGN(snod->len, 8);
 271                        /*
 272                         * The obsolete index nodes form gaps that can be
 273                         * overwritten.  This gap has ended because we have
 274                         * found an index node that is still in use
 275                         * i.e. not obsolete
 276                         */
 277                        gap_end = snod->offs;
 278                        /* Try to fill gap */
 279                        written = fill_gap(c, lnum, gap_start, gap_end, &dirt);
 280                        if (written < 0) {
 281                                ubifs_scan_destroy(sleb);
 282                                return written; /* Error code */
 283                        }
 284                        tot_written += written;
 285                        gap_start = ALIGN(snod->offs + snod->len, 8);
 286                }
 287        }
 288        ubifs_scan_destroy(sleb);
 289        c->ileb_len = c->leb_size;
 290        gap_end = c->leb_size;
 291        /* Try to fill gap */
 292        written = fill_gap(c, lnum, gap_start, gap_end, &dirt);
 293        if (written < 0)
 294                return written; /* Error code */
 295        tot_written += written;
 296        if (tot_written == 0) {
 297                struct ubifs_lprops lp;
 298
 299                dbg_gc("LEB %d wrote %d index nodes", lnum, tot_written);
 300                err = ubifs_read_one_lp(c, lnum, &lp);
 301                if (err)
 302                        return err;
 303                if (lp.free == c->leb_size) {
 304                        /*
 305                         * We must have snatched this LEB from the idx_gc list
 306                         * so we need to correct the free and dirty space.
 307                         */
 308                        err = ubifs_change_one_lp(c, lnum,
 309                                                  c->leb_size - c->ileb_len,
 310                                                  dirt, 0, 0, 0);
 311                        if (err)
 312                                return err;
 313                }
 314                return 0;
 315        }
 316        err = ubifs_change_one_lp(c, lnum, c->leb_size - c->ileb_len, dirt,
 317                                  0, 0, 0);
 318        if (err)
 319                return err;
 320        err = ubifs_leb_change(c, lnum, c->ileb_buf, c->ileb_len,
 321                               UBI_SHORTTERM);
 322        if (err)
 323                return err;
 324        dbg_gc("LEB %d wrote %d index nodes", lnum, tot_written);
 325        return tot_written;
 326}
 327
 328/**
 329 * get_leb_cnt - calculate the number of empty LEBs needed to commit.
 330 * @c: UBIFS file-system description object
 331 * @cnt: number of znodes to commit
 332 *
 333 * This function returns the number of empty LEBs needed to commit @cnt znodes
 334 * to the current index head.  The number is not exact and may be more than
 335 * needed.
 336 */
 337static int get_leb_cnt(struct ubifs_info *c, int cnt)
 338{
 339        int d;
 340
 341        /* Assume maximum index node size (i.e. overestimate space needed) */
 342        cnt -= (c->leb_size - c->ihead_offs) / c->max_idx_node_sz;
 343        if (cnt < 0)
 344                cnt = 0;
 345        d = c->leb_size / c->max_idx_node_sz;
 346        return DIV_ROUND_UP(cnt, d);
 347}
 348
 349/**
 350 * layout_in_gaps - in-the-gaps method of committing TNC.
 351 * @c: UBIFS file-system description object
 352 * @cnt: number of dirty znodes to commit.
 353 *
 354 * This function lays out new index nodes for dirty znodes using in-the-gaps
 355 * method of TNC commit.
 356 *
 357 * This function returns %0 on success and a negative error code on failure.
 358 */
 359static int layout_in_gaps(struct ubifs_info *c, int cnt)
 360{
 361        int err, leb_needed_cnt, written, *p;
 362
 363        dbg_gc("%d znodes to write", cnt);
 364
 365        c->gap_lebs = kmalloc(sizeof(int) * (c->lst.idx_lebs + 1), GFP_NOFS);
 366        if (!c->gap_lebs)
 367                return -ENOMEM;
 368
 369        p = c->gap_lebs;
 370        do {
 371                ubifs_assert(p < c->gap_lebs + sizeof(int) * c->lst.idx_lebs);
 372                written = layout_leb_in_gaps(c, p);
 373                if (written < 0) {
 374                        err = written;
 375                        if (err != -ENOSPC) {
 376                                kfree(c->gap_lebs);
 377                                c->gap_lebs = NULL;
 378                                return err;
 379                        }
 380                        if (!dbg_force_in_the_gaps_enabled) {
 381                                /*
 382                                 * Do not print scary warnings if the debugging
 383                                 * option which forces in-the-gaps is enabled.
 384                                 */
 385                                ubifs_err("out of space");
 386                                spin_lock(&c->space_lock);
 387                                dbg_dump_budg(c);
 388                                spin_unlock(&c->space_lock);
 389                                dbg_dump_lprops(c);
 390                        }
 391                        /* Try to commit anyway */
 392                        err = 0;
 393                        break;
 394                }
 395                p++;
 396                cnt -= written;
 397                leb_needed_cnt = get_leb_cnt(c, cnt);
 398                dbg_gc("%d znodes remaining, need %d LEBs, have %d", cnt,
 399                       leb_needed_cnt, c->ileb_cnt);
 400        } while (leb_needed_cnt > c->ileb_cnt);
 401
 402        *p = -1;
 403        return 0;
 404}
 405
 406/**
 407 * layout_in_empty_space - layout index nodes in empty space.
 408 * @c: UBIFS file-system description object
 409 *
 410 * This function lays out new index nodes for dirty znodes using empty LEBs.
 411 *
 412 * This function returns %0 on success and a negative error code on failure.
 413 */
 414static int layout_in_empty_space(struct ubifs_info *c)
 415{
 416        struct ubifs_znode *znode, *cnext, *zp;
 417        int lnum, offs, len, next_len, buf_len, buf_offs, used, avail;
 418        int wlen, blen, err;
 419
 420        cnext = c->enext;
 421        if (!cnext)
 422                return 0;
 423
 424        lnum = c->ihead_lnum;
 425        buf_offs = c->ihead_offs;
 426
 427        buf_len = ubifs_idx_node_sz(c, c->fanout);
 428        buf_len = ALIGN(buf_len, c->min_io_size);
 429        used = 0;
 430        avail = buf_len;
 431
 432        /* Ensure there is enough room for first write */
 433        next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
 434        if (buf_offs + next_len > c->leb_size)
 435                lnum = -1;
 436
 437        while (1) {
 438                znode = cnext;
 439
 440                len = ubifs_idx_node_sz(c, znode->child_cnt);
 441
 442                /* Determine the index node position */
 443                if (lnum == -1) {
 444                        if (c->ileb_nxt >= c->ileb_cnt) {
 445                                ubifs_err("out of space");
 446                                return -ENOSPC;
 447                        }
 448                        lnum = c->ilebs[c->ileb_nxt++];
 449                        buf_offs = 0;
 450                        used = 0;
 451                        avail = buf_len;
 452                }
 453
 454                offs = buf_offs + used;
 455
 456#ifdef CONFIG_UBIFS_FS_DEBUG
 457                znode->lnum = lnum;
 458                znode->offs = offs;
 459                znode->len = len;
 460#endif
 461
 462                /* Update the parent */
 463                zp = znode->parent;
 464                if (zp) {
 465                        struct ubifs_zbranch *zbr;
 466                        int i;
 467
 468                        i = znode->iip;
 469                        zbr = &zp->zbranch[i];
 470                        zbr->lnum = lnum;
 471                        zbr->offs = offs;
 472                        zbr->len = len;
 473                } else {
 474                        c->zroot.lnum = lnum;
 475                        c->zroot.offs = offs;
 476                        c->zroot.len = len;
 477                }
 478                c->calc_idx_sz += ALIGN(len, 8);
 479
 480                /*
 481                 * Once lprops is updated, we can decrease the dirty znode count
 482                 * but it is easier to just do it here.
 483                 */
 484                atomic_long_dec(&c->dirty_zn_cnt);
 485
 486                /*
 487                 * Calculate the next index node length to see if there is
 488                 * enough room for it
 489                 */
 490                cnext = znode->cnext;
 491                if (cnext == c->cnext)
 492                        next_len = 0;
 493                else
 494                        next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
 495
 496                if (c->min_io_size == 1) {
 497                        buf_offs += ALIGN(len, 8);
 498                        if (next_len) {
 499                                if (buf_offs + next_len <= c->leb_size)
 500                                        continue;
 501                                err = ubifs_update_one_lp(c, lnum, 0,
 502                                                c->leb_size - buf_offs, 0, 0);
 503                                if (err)
 504                                        return err;
 505                                lnum = -1;
 506                                continue;
 507                        }
 508                        err = ubifs_update_one_lp(c, lnum,
 509                                        c->leb_size - buf_offs, 0, 0, 0);
 510                        if (err)
 511                                return err;
 512                        break;
 513                }
 514
 515                /* Update buffer positions */
 516                wlen = used + len;
 517                used += ALIGN(len, 8);
 518                avail -= ALIGN(len, 8);
 519
 520                if (next_len != 0 &&
 521                    buf_offs + used + next_len <= c->leb_size &&
 522                    avail > 0)
 523                        continue;
 524
 525                if (avail <= 0 && next_len &&
 526                    buf_offs + used + next_len <= c->leb_size)
 527                        blen = buf_len;
 528                else
 529                        blen = ALIGN(wlen, c->min_io_size);
 530
 531                /* The buffer is full or there are no more znodes to do */
 532                buf_offs += blen;
 533                if (next_len) {
 534                        if (buf_offs + next_len > c->leb_size) {
 535                                err = ubifs_update_one_lp(c, lnum,
 536                                        c->leb_size - buf_offs, blen - used,
 537                                        0, 0);
 538                                if (err)
 539                                        return err;
 540                                lnum = -1;
 541                        }
 542                        used -= blen;
 543                        if (used < 0)
 544                                used = 0;
 545                        avail = buf_len - used;
 546                        continue;
 547                }
 548                err = ubifs_update_one_lp(c, lnum, c->leb_size - buf_offs,
 549                                          blen - used, 0, 0);
 550                if (err)
 551                        return err;
 552                break;
 553        }
 554
 555#ifdef CONFIG_UBIFS_FS_DEBUG
 556        c->dbg->new_ihead_lnum = lnum;
 557        c->dbg->new_ihead_offs = buf_offs;
 558#endif
 559
 560        return 0;
 561}
 562
 563/**
 564 * layout_commit - determine positions of index nodes to commit.
 565 * @c: UBIFS file-system description object
 566 * @no_space: indicates that insufficient empty LEBs were allocated
 567 * @cnt: number of znodes to commit
 568 *
 569 * Calculate and update the positions of index nodes to commit.  If there were
 570 * an insufficient number of empty LEBs allocated, then index nodes are placed
 571 * into the gaps created by obsolete index nodes in non-empty index LEBs.  For
 572 * this purpose, an obsolete index node is one that was not in the index as at
 573 * the end of the last commit.  To write "in-the-gaps" requires that those index
 574 * LEBs are updated atomically in-place.
 575 */
 576static int layout_commit(struct ubifs_info *c, int no_space, int cnt)
 577{
 578        int err;
 579
 580        if (no_space) {
 581                err = layout_in_gaps(c, cnt);
 582                if (err)
 583                        return err;
 584        }
 585        err = layout_in_empty_space(c);
 586        return err;
 587}
 588
 589/**
 590 * find_first_dirty - find first dirty znode.
 591 * @znode: znode to begin searching from
 592 */
 593static struct ubifs_znode *find_first_dirty(struct ubifs_znode *znode)
 594{
 595        int i, cont;
 596
 597        if (!znode)
 598                return NULL;
 599
 600        while (1) {
 601                if (znode->level == 0) {
 602                        if (ubifs_zn_dirty(znode))
 603                                return znode;
 604                        return NULL;
 605                }
 606                cont = 0;
 607                for (i = 0; i < znode->child_cnt; i++) {
 608                        struct ubifs_zbranch *zbr = &znode->zbranch[i];
 609
 610                        if (zbr->znode && ubifs_zn_dirty(zbr->znode)) {
 611                                znode = zbr->znode;
 612                                cont = 1;
 613                                break;
 614                        }
 615                }
 616                if (!cont) {
 617                        if (ubifs_zn_dirty(znode))
 618                                return znode;
 619                        return NULL;
 620                }
 621        }
 622}
 623
 624/**
 625 * find_next_dirty - find next dirty znode.
 626 * @znode: znode to begin searching from
 627 */
 628static struct ubifs_znode *find_next_dirty(struct ubifs_znode *znode)
 629{
 630        int n = znode->iip + 1;
 631
 632        znode = znode->parent;
 633        if (!znode)
 634                return NULL;
 635        for (; n < znode->child_cnt; n++) {
 636                struct ubifs_zbranch *zbr = &znode->zbranch[n];
 637
 638                if (zbr->znode && ubifs_zn_dirty(zbr->znode))
 639                        return find_first_dirty(zbr->znode);
 640        }
 641        return znode;
 642}
 643
 644/**
 645 * get_znodes_to_commit - create list of dirty znodes to commit.
 646 * @c: UBIFS file-system description object
 647 *
 648 * This function returns the number of znodes to commit.
 649 */
 650static int get_znodes_to_commit(struct ubifs_info *c)
 651{
 652        struct ubifs_znode *znode, *cnext;
 653        int cnt = 0;
 654
 655        c->cnext = find_first_dirty(c->zroot.znode);
 656        znode = c->enext = c->cnext;
 657        if (!znode) {
 658                dbg_cmt("no znodes to commit");
 659                return 0;
 660        }
 661        cnt += 1;
 662        while (1) {
 663                ubifs_assert(!test_bit(COW_ZNODE, &znode->flags));
 664                __set_bit(COW_ZNODE, &znode->flags);
 665                znode->alt = 0;
 666                cnext = find_next_dirty(znode);
 667                if (!cnext) {
 668                        znode->cnext = c->cnext;
 669                        break;
 670                }
 671                znode->cnext = cnext;
 672                znode = cnext;
 673                cnt += 1;
 674        }
 675        dbg_cmt("committing %d znodes", cnt);
 676        ubifs_assert(cnt == atomic_long_read(&c->dirty_zn_cnt));
 677        return cnt;
 678}
 679
 680/**
 681 * alloc_idx_lebs - allocate empty LEBs to be used to commit.
 682 * @c: UBIFS file-system description object
 683 * @cnt: number of znodes to commit
 684 *
 685 * This function returns %-ENOSPC if it cannot allocate a sufficient number of
 686 * empty LEBs.  %0 is returned on success, otherwise a negative error code
 687 * is returned.
 688 */
 689static int alloc_idx_lebs(struct ubifs_info *c, int cnt)
 690{
 691        int i, leb_cnt, lnum;
 692
 693        c->ileb_cnt = 0;
 694        c->ileb_nxt = 0;
 695        leb_cnt = get_leb_cnt(c, cnt);
 696        dbg_cmt("need about %d empty LEBS for TNC commit", leb_cnt);
 697        if (!leb_cnt)
 698                return 0;
 699        c->ilebs = kmalloc(leb_cnt * sizeof(int), GFP_NOFS);
 700        if (!c->ilebs)
 701                return -ENOMEM;
 702        for (i = 0; i < leb_cnt; i++) {
 703                lnum = ubifs_find_free_leb_for_idx(c);
 704                if (lnum < 0)
 705                        return lnum;
 706                c->ilebs[c->ileb_cnt++] = lnum;
 707                dbg_cmt("LEB %d", lnum);
 708        }
 709        if (dbg_force_in_the_gaps())
 710                return -ENOSPC;
 711        return 0;
 712}
 713
 714/**
 715 * free_unused_idx_lebs - free unused LEBs that were allocated for the commit.
 716 * @c: UBIFS file-system description object
 717 *
 718 * It is possible that we allocate more empty LEBs for the commit than we need.
 719 * This functions frees the surplus.
 720 *
 721 * This function returns %0 on success and a negative error code on failure.
 722 */
 723static int free_unused_idx_lebs(struct ubifs_info *c)
 724{
 725        int i, err = 0, lnum, er;
 726
 727        for (i = c->ileb_nxt; i < c->ileb_cnt; i++) {
 728                lnum = c->ilebs[i];
 729                dbg_cmt("LEB %d", lnum);
 730                er = ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
 731                                         LPROPS_INDEX | LPROPS_TAKEN, 0);
 732                if (!err)
 733                        err = er;
 734        }
 735        return err;
 736}
 737
 738/**
 739 * free_idx_lebs - free unused LEBs after commit end.
 740 * @c: UBIFS file-system description object
 741 *
 742 * This function returns %0 on success and a negative error code on failure.
 743 */
 744static int free_idx_lebs(struct ubifs_info *c)
 745{
 746        int err;
 747
 748        err = free_unused_idx_lebs(c);
 749        kfree(c->ilebs);
 750        c->ilebs = NULL;
 751        return err;
 752}
 753
 754/**
 755 * ubifs_tnc_start_commit - start TNC commit.
 756 * @c: UBIFS file-system description object
 757 * @zroot: new index root position is returned here
 758 *
 759 * This function prepares the list of indexing nodes to commit and lays out
 760 * their positions on flash. If there is not enough free space it uses the
 761 * in-gap commit method. Returns zero in case of success and a negative error
 762 * code in case of failure.
 763 */
 764int ubifs_tnc_start_commit(struct ubifs_info *c, struct ubifs_zbranch *zroot)
 765{
 766        int err = 0, cnt;
 767
 768        mutex_lock(&c->tnc_mutex);
 769        err = dbg_check_tnc(c, 1);
 770        if (err)
 771                goto out;
 772        cnt = get_znodes_to_commit(c);
 773        if (cnt != 0) {
 774                int no_space = 0;
 775
 776                err = alloc_idx_lebs(c, cnt);
 777                if (err == -ENOSPC)
 778                        no_space = 1;
 779                else if (err)
 780                        goto out_free;
 781                err = layout_commit(c, no_space, cnt);
 782                if (err)
 783                        goto out_free;
 784                ubifs_assert(atomic_long_read(&c->dirty_zn_cnt) == 0);
 785                err = free_unused_idx_lebs(c);
 786                if (err)
 787                        goto out;
 788        }
 789        destroy_old_idx(c);
 790        memcpy(zroot, &c->zroot, sizeof(struct ubifs_zbranch));
 791
 792        err = ubifs_save_dirty_idx_lnums(c);
 793        if (err)
 794                goto out;
 795
 796        spin_lock(&c->space_lock);
 797        /*
 798         * Although we have not finished committing yet, update size of the
 799         * committed index ('c->old_idx_sz') and zero out the index growth
 800         * budget. It is OK to do this now, because we've reserved all the
 801         * space which is needed to commit the index, and it is save for the
 802         * budgeting subsystem to assume the index is already committed,
 803         * even though it is not.
 804         */
 805        ubifs_assert(c->min_idx_lebs == ubifs_calc_min_idx_lebs(c));
 806        c->old_idx_sz = c->calc_idx_sz;
 807        c->budg_uncommitted_idx = 0;
 808        c->min_idx_lebs = ubifs_calc_min_idx_lebs(c);
 809        spin_unlock(&c->space_lock);
 810        mutex_unlock(&c->tnc_mutex);
 811
 812        dbg_cmt("number of index LEBs %d", c->lst.idx_lebs);
 813        dbg_cmt("size of index %llu", c->calc_idx_sz);
 814        return err;
 815
 816out_free:
 817        free_idx_lebs(c);
 818out:
 819        mutex_unlock(&c->tnc_mutex);
 820        return err;
 821}
 822
 823/**
 824 * write_index - write index nodes.
 825 * @c: UBIFS file-system description object
 826 *
 827 * This function writes the index nodes whose positions were laid out in the
 828 * layout_in_empty_space function.
 829 */
 830static int write_index(struct ubifs_info *c)
 831{
 832        struct ubifs_idx_node *idx;
 833        struct ubifs_znode *znode, *cnext;
 834        int i, lnum, offs, len, next_len, buf_len, buf_offs, used;
 835        int avail, wlen, err, lnum_pos = 0;
 836
 837        cnext = c->enext;
 838        if (!cnext)
 839                return 0;
 840
 841        /*
 842         * Always write index nodes to the index head so that index nodes and
 843         * other types of nodes are never mixed in the same erase block.
 844         */
 845        lnum = c->ihead_lnum;
 846        buf_offs = c->ihead_offs;
 847
 848        /* Allocate commit buffer */
 849        buf_len = ALIGN(c->max_idx_node_sz, c->min_io_size);
 850        used = 0;
 851        avail = buf_len;
 852
 853        /* Ensure there is enough room for first write */
 854        next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
 855        if (buf_offs + next_len > c->leb_size) {
 856                err = ubifs_update_one_lp(c, lnum, LPROPS_NC, 0, 0,
 857                                          LPROPS_TAKEN);
 858                if (err)
 859                        return err;
 860                lnum = -1;
 861        }
 862
 863        while (1) {
 864                cond_resched();
 865
 866                znode = cnext;
 867                idx = c->cbuf + used;
 868
 869                /* Make index node */
 870                idx->ch.node_type = UBIFS_IDX_NODE;
 871                idx->child_cnt = cpu_to_le16(znode->child_cnt);
 872                idx->level = cpu_to_le16(znode->level);
 873                for (i = 0; i < znode->child_cnt; i++) {
 874                        struct ubifs_branch *br = ubifs_idx_branch(c, idx, i);
 875                        struct ubifs_zbranch *zbr = &znode->zbranch[i];
 876
 877                        key_write_idx(c, &zbr->key, &br->key);
 878                        br->lnum = cpu_to_le32(zbr->lnum);
 879                        br->offs = cpu_to_le32(zbr->offs);
 880                        br->len = cpu_to_le32(zbr->len);
 881                        if (!zbr->lnum || !zbr->len) {
 882                                ubifs_err("bad ref in znode");
 883                                dbg_dump_znode(c, znode);
 884                                if (zbr->znode)
 885                                        dbg_dump_znode(c, zbr->znode);
 886                        }
 887                }
 888                len = ubifs_idx_node_sz(c, znode->child_cnt);
 889                ubifs_prepare_node(c, idx, len, 0);
 890
 891                /* Determine the index node position */
 892                if (lnum == -1) {
 893                        lnum = c->ilebs[lnum_pos++];
 894                        buf_offs = 0;
 895                        used = 0;
 896                        avail = buf_len;
 897                }
 898                offs = buf_offs + used;
 899
 900#ifdef CONFIG_UBIFS_FS_DEBUG
 901                if (lnum != znode->lnum || offs != znode->offs ||
 902                    len != znode->len) {
 903                        ubifs_err("inconsistent znode posn");
 904                        return -EINVAL;
 905                }
 906#endif
 907
 908                /* Grab some stuff from znode while we still can */
 909                cnext = znode->cnext;
 910
 911                ubifs_assert(ubifs_zn_dirty(znode));
 912                ubifs_assert(test_bit(COW_ZNODE, &znode->flags));
 913
 914                /*
 915                 * It is important that other threads should see %DIRTY_ZNODE
 916                 * flag cleared before %COW_ZNODE. Specifically, it matters in
 917                 * the 'dirty_cow_znode()' function. This is the reason for the
 918                 * first barrier. Also, we want the bit changes to be seen to
 919                 * other threads ASAP, to avoid unnecesarry copying, which is
 920                 * the reason for the second barrier.
 921                 */
 922                clear_bit(DIRTY_ZNODE, &znode->flags);
 923                smp_mb__before_clear_bit();
 924                clear_bit(COW_ZNODE, &znode->flags);
 925                smp_mb__after_clear_bit();
 926
 927                /* Do not access znode from this point on */
 928
 929                /* Update buffer positions */
 930                wlen = used + len;
 931                used += ALIGN(len, 8);
 932                avail -= ALIGN(len, 8);
 933
 934                /*
 935                 * Calculate the next index node length to see if there is
 936                 * enough room for it
 937                 */
 938                if (cnext == c->cnext)
 939                        next_len = 0;
 940                else
 941                        next_len = ubifs_idx_node_sz(c, cnext->child_cnt);
 942
 943                if (c->min_io_size == 1) {
 944                        /*
 945                         * Write the prepared index node immediately if there is
 946                         * no minimum IO size
 947                         */
 948                        err = ubifs_leb_write(c, lnum, c->cbuf, buf_offs,
 949                                              wlen, UBI_SHORTTERM);
 950                        if (err)
 951                                return err;
 952                        buf_offs += ALIGN(wlen, 8);
 953                        if (next_len) {
 954                                used = 0;
 955                                avail = buf_len;
 956                                if (buf_offs + next_len > c->leb_size) {
 957                                        err = ubifs_update_one_lp(c, lnum,
 958                                                LPROPS_NC, 0, 0, LPROPS_TAKEN);
 959                                        if (err)
 960                                                return err;
 961                                        lnum = -1;
 962                                }
 963                                continue;
 964                        }
 965                } else {
 966                        int blen, nxt_offs = buf_offs + used + next_len;
 967
 968                        if (next_len && nxt_offs <= c->leb_size) {
 969                                if (avail > 0)
 970                                        continue;
 971                                else
 972                                        blen = buf_len;
 973                        } else {
 974                                wlen = ALIGN(wlen, 8);
 975                                blen = ALIGN(wlen, c->min_io_size);
 976                                ubifs_pad(c, c->cbuf + wlen, blen - wlen);
 977                        }
 978                        /*
 979                         * The buffer is full or there are no more znodes
 980                         * to do
 981                         */
 982                        err = ubifs_leb_write(c, lnum, c->cbuf, buf_offs,
 983                                              blen, UBI_SHORTTERM);
 984                        if (err)
 985                                return err;
 986                        buf_offs += blen;
 987                        if (next_len) {
 988                                if (nxt_offs > c->leb_size) {
 989                                        err = ubifs_update_one_lp(c, lnum,
 990                                                LPROPS_NC, 0, 0, LPROPS_TAKEN);
 991                                        if (err)
 992                                                return err;
 993                                        lnum = -1;
 994                                }
 995                                used -= blen;
 996                                if (used < 0)
 997                                        used = 0;
 998                                avail = buf_len - used;
 999                                memmove(c->cbuf, c->cbuf + blen, used);
1000                                continue;
1001                        }
1002                }
1003                break;
1004        }
1005
1006#ifdef CONFIG_UBIFS_FS_DEBUG
1007        if (lnum != c->dbg->new_ihead_lnum ||
1008            buf_offs != c->dbg->new_ihead_offs) {
1009                ubifs_err("inconsistent ihead");
1010                return -EINVAL;
1011        }
1012#endif
1013
1014        c->ihead_lnum = lnum;
1015        c->ihead_offs = buf_offs;
1016
1017        return 0;
1018}
1019
1020/**
1021 * free_obsolete_znodes - free obsolete znodes.
1022 * @c: UBIFS file-system description object
1023 *
1024 * At the end of commit end, obsolete znodes are freed.
1025 */
1026static void free_obsolete_znodes(struct ubifs_info *c)
1027{
1028        struct ubifs_znode *znode, *cnext;
1029
1030        cnext = c->cnext;
1031        do {
1032                znode = cnext;
1033                cnext = znode->cnext;
1034                if (test_bit(OBSOLETE_ZNODE, &znode->flags))
1035                        kfree(znode);
1036                else {
1037                        znode->cnext = NULL;
1038                        atomic_long_inc(&c->clean_zn_cnt);
1039                        atomic_long_inc(&ubifs_clean_zn_cnt);
1040                }
1041        } while (cnext != c->cnext);
1042}
1043
1044/**
1045 * return_gap_lebs - return LEBs used by the in-gap commit method.
1046 * @c: UBIFS file-system description object
1047 *
1048 * This function clears the "taken" flag for the LEBs which were used by the
1049 * "commit in-the-gaps" method.
1050 */
1051static int return_gap_lebs(struct ubifs_info *c)
1052{
1053        int *p, err;
1054
1055        if (!c->gap_lebs)
1056                return 0;
1057
1058        dbg_cmt("");
1059        for (p = c->gap_lebs; *p != -1; p++) {
1060                err = ubifs_change_one_lp(c, *p, LPROPS_NC, LPROPS_NC, 0,
1061                                          LPROPS_TAKEN, 0);
1062                if (err)
1063                        return err;
1064        }
1065
1066        kfree(c->gap_lebs);
1067        c->gap_lebs = NULL;
1068        return 0;
1069}
1070
1071/**
1072 * ubifs_tnc_end_commit - update the TNC for commit end.
1073 * @c: UBIFS file-system description object
1074 *
1075 * Write the dirty znodes.
1076 */
1077int ubifs_tnc_end_commit(struct ubifs_info *c)
1078{
1079        int err;
1080
1081        if (!c->cnext)
1082                return 0;
1083
1084        err = return_gap_lebs(c);
1085        if (err)
1086                return err;
1087
1088        err = write_index(c);
1089        if (err)
1090                return err;
1091
1092        mutex_lock(&c->tnc_mutex);
1093
1094        dbg_cmt("TNC height is %d", c->zroot.znode->level + 1);
1095
1096        free_obsolete_znodes(c);
1097
1098        c->cnext = NULL;
1099        kfree(c->ilebs);
1100        c->ilebs = NULL;
1101
1102        mutex_unlock(&c->tnc_mutex);
1103
1104        return 0;
1105}
1106