linux/fs/ubifs/find.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: Artem Bityutskiy (Битюцкий Артём)
  20 *          Adrian Hunter
  21 */
  22
  23/*
  24 * This file contains functions for finding LEBs for various purposes e.g.
  25 * garbage collection. In general, lprops category heaps and lists are used
  26 * for fast access, falling back on scanning the LPT as a last resort.
  27 */
  28
  29#include <linux/sort.h>
  30#include "ubifs.h"
  31
  32/**
  33 * struct scan_data - data provided to scan callback functions
  34 * @min_space: minimum number of bytes for which to scan
  35 * @pick_free: whether it is OK to scan for empty LEBs
  36 * @lnum: LEB number found is returned here
  37 * @exclude_index: whether to exclude index LEBs
  38 */
  39struct scan_data {
  40        int min_space;
  41        int pick_free;
  42        int lnum;
  43        int exclude_index;
  44};
  45
  46/**
  47 * valuable - determine whether LEB properties are valuable.
  48 * @c: the UBIFS file-system description object
  49 * @lprops: LEB properties
  50 *
  51 * This function return %1 if the LEB properties should be added to the LEB
  52 * properties tree in memory. Otherwise %0 is returned.
  53 */
  54static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)
  55{
  56        int n, cat = lprops->flags & LPROPS_CAT_MASK;
  57        struct ubifs_lpt_heap *heap;
  58
  59        switch (cat) {
  60        case LPROPS_DIRTY:
  61        case LPROPS_DIRTY_IDX:
  62        case LPROPS_FREE:
  63                heap = &c->lpt_heap[cat - 1];
  64                if (heap->cnt < heap->max_cnt)
  65                        return 1;
  66                if (lprops->free + lprops->dirty >= c->dark_wm)
  67                        return 1;
  68                return 0;
  69        case LPROPS_EMPTY:
  70                n = c->lst.empty_lebs + c->freeable_cnt -
  71                    c->lst.taken_empty_lebs;
  72                if (n < c->lsave_cnt)
  73                        return 1;
  74                return 0;
  75        case LPROPS_FREEABLE:
  76                return 1;
  77        case LPROPS_FRDI_IDX:
  78                return 1;
  79        }
  80        return 0;
  81}
  82
  83/**
  84 * scan_for_dirty_cb - dirty space scan callback.
  85 * @c: the UBIFS file-system description object
  86 * @lprops: LEB properties to scan
  87 * @in_tree: whether the LEB properties are in main memory
  88 * @data: information passed to and from the caller of the scan
  89 *
  90 * This function returns a code that indicates whether the scan should continue
  91 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
  92 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
  93 * (%LPT_SCAN_STOP).
  94 */
  95static int scan_for_dirty_cb(struct ubifs_info *c,
  96                             const struct ubifs_lprops *lprops, int in_tree,
  97                             struct scan_data *data)
  98{
  99        int ret = LPT_SCAN_CONTINUE;
 100
 101        /* Exclude LEBs that are currently in use */
 102        if (lprops->flags & LPROPS_TAKEN)
 103                return LPT_SCAN_CONTINUE;
 104        /* Determine whether to add these LEB properties to the tree */
 105        if (!in_tree && valuable(c, lprops))
 106                ret |= LPT_SCAN_ADD;
 107        /* Exclude LEBs with too little space */
 108        if (lprops->free + lprops->dirty < data->min_space)
 109                return ret;
 110        /* If specified, exclude index LEBs */
 111        if (data->exclude_index && lprops->flags & LPROPS_INDEX)
 112                return ret;
 113        /* If specified, exclude empty or freeable LEBs */
 114        if (lprops->free + lprops->dirty == c->leb_size) {
 115                if (!data->pick_free)
 116                        return ret;
 117        /* Exclude LEBs with too little dirty space (unless it is empty) */
 118        } else if (lprops->dirty < c->dead_wm)
 119                return ret;
 120        /* Finally we found space */
 121        data->lnum = lprops->lnum;
 122        return LPT_SCAN_ADD | LPT_SCAN_STOP;
 123}
 124
 125/**
 126 * scan_for_dirty - find a data LEB with free space.
 127 * @c: the UBIFS file-system description object
 128 * @min_space: minimum amount free plus dirty space the returned LEB has to
 129 *             have
 130 * @pick_free: if it is OK to return a free or freeable LEB
 131 * @exclude_index: whether to exclude index LEBs
 132 *
 133 * This function returns a pointer to the LEB properties found or a negative
 134 * error code.
 135 */
 136static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,
 137                                                 int min_space, int pick_free,
 138                                                 int exclude_index)
 139{
 140        const struct ubifs_lprops *lprops;
 141        struct ubifs_lpt_heap *heap;
 142        struct scan_data data;
 143        int err, i;
 144
 145        /* There may be an LEB with enough dirty space on the free heap */
 146        heap = &c->lpt_heap[LPROPS_FREE - 1];
 147        for (i = 0; i < heap->cnt; i++) {
 148                lprops = heap->arr[i];
 149                if (lprops->free + lprops->dirty < min_space)
 150                        continue;
 151                if (lprops->dirty < c->dead_wm)
 152                        continue;
 153                return lprops;
 154        }
 155        /*
 156         * A LEB may have fallen off of the bottom of the dirty heap, and ended
 157         * up as uncategorized even though it has enough dirty space for us now,
 158         * so check the uncategorized list. N.B. neither empty nor freeable LEBs
 159         * can end up as uncategorized because they are kept on lists not
 160         * finite-sized heaps.
 161         */
 162        list_for_each_entry(lprops, &c->uncat_list, list) {
 163                if (lprops->flags & LPROPS_TAKEN)
 164                        continue;
 165                if (lprops->free + lprops->dirty < min_space)
 166                        continue;
 167                if (exclude_index && (lprops->flags & LPROPS_INDEX))
 168                        continue;
 169                if (lprops->dirty < c->dead_wm)
 170                        continue;
 171                return lprops;
 172        }
 173        /* We have looked everywhere in main memory, now scan the flash */
 174        if (c->pnodes_have >= c->pnode_cnt)
 175                /* All pnodes are in memory, so skip scan */
 176                return ERR_PTR(-ENOSPC);
 177        data.min_space = min_space;
 178        data.pick_free = pick_free;
 179        data.lnum = -1;
 180        data.exclude_index = exclude_index;
 181        err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
 182                                    (ubifs_lpt_scan_callback)scan_for_dirty_cb,
 183                                    &data);
 184        if (err)
 185                return ERR_PTR(err);
 186        ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
 187        c->lscan_lnum = data.lnum;
 188        lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
 189        if (IS_ERR(lprops))
 190                return lprops;
 191        ubifs_assert(lprops->lnum == data.lnum);
 192        ubifs_assert(lprops->free + lprops->dirty >= min_space);
 193        ubifs_assert(lprops->dirty >= c->dead_wm ||
 194                     (pick_free &&
 195                      lprops->free + lprops->dirty == c->leb_size));
 196        ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
 197        ubifs_assert(!exclude_index || !(lprops->flags & LPROPS_INDEX));
 198        return lprops;
 199}
 200
 201/**
 202 * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
 203 * @c: the UBIFS file-system description object
 204 * @ret_lp: LEB properties are returned here on exit
 205 * @min_space: minimum amount free plus dirty space the returned LEB has to
 206 *             have
 207 * @pick_free: controls whether it is OK to pick empty or index LEBs
 208 *
 209 * This function tries to find a dirty logical eraseblock which has at least
 210 * @min_space free and dirty space. It prefers to take an LEB from the dirty or
 211 * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
 212 * or do not have an LEB which satisfies the @min_space criteria.
 213 *
 214 * Note, LEBs which have less than dead watermark of free + dirty space are
 215 * never picked by this function.
 216 *
 217 * The additional @pick_free argument controls if this function has to return a
 218 * free or freeable LEB if one is present. For example, GC must to set it to %1,
 219 * when called from the journal space reservation function, because the
 220 * appearance of free space may coincide with the loss of enough dirty space
 221 * for GC to succeed anyway.
 222 *
 223 * In contrast, if the Garbage Collector is called from budgeting, it should
 224 * just make free space, not return LEBs which are already free or freeable.
 225 *
 226 * In addition @pick_free is set to %2 by the recovery process in order to
 227 * recover gc_lnum in which case an index LEB must not be returned.
 228 *
 229 * This function returns zero and the LEB properties of found dirty LEB in case
 230 * of success, %-ENOSPC if no dirty LEB was found and a negative error code in
 231 * case of other failures. The returned LEB is marked as "taken".
 232 */
 233int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp,
 234                         int min_space, int pick_free)
 235{
 236        int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0;
 237        const struct ubifs_lprops *lp = NULL, *idx_lp = NULL;
 238        struct ubifs_lpt_heap *heap, *idx_heap;
 239
 240        ubifs_get_lprops(c);
 241
 242        if (pick_free) {
 243                int lebs, rsvd_idx_lebs = 0;
 244
 245                spin_lock(&c->space_lock);
 246                lebs = c->lst.empty_lebs + c->idx_gc_cnt;
 247                lebs += c->freeable_cnt - c->lst.taken_empty_lebs;
 248
 249                /*
 250                 * Note, the index may consume more LEBs than have been reserved
 251                 * for it. It is OK because it might be consolidated by GC.
 252                 * But if the index takes fewer LEBs than it is reserved for it,
 253                 * this function must avoid picking those reserved LEBs.
 254                 */
 255                if (c->bi.min_idx_lebs >= c->lst.idx_lebs) {
 256                        rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;
 257                        exclude_index = 1;
 258                }
 259                spin_unlock(&c->space_lock);
 260
 261                /* Check if there are enough free LEBs for the index */
 262                if (rsvd_idx_lebs < lebs) {
 263                        /* OK, try to find an empty LEB */
 264                        lp = ubifs_fast_find_empty(c);
 265                        if (lp)
 266                                goto found;
 267
 268                        /* Or a freeable LEB */
 269                        lp = ubifs_fast_find_freeable(c);
 270                        if (lp)
 271                                goto found;
 272                } else
 273                        /*
 274                         * We cannot pick free/freeable LEBs in the below code.
 275                         */
 276                        pick_free = 0;
 277        } else {
 278                spin_lock(&c->space_lock);
 279                exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs);
 280                spin_unlock(&c->space_lock);
 281        }
 282
 283        /* Look on the dirty and dirty index heaps */
 284        heap = &c->lpt_heap[LPROPS_DIRTY - 1];
 285        idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 286
 287        if (idx_heap->cnt && !exclude_index) {
 288                idx_lp = idx_heap->arr[0];
 289                sum = idx_lp->free + idx_lp->dirty;
 290                /*
 291                 * Since we reserve thrice as much space for the index than it
 292                 * actually takes, it does not make sense to pick indexing LEBs
 293                 * with less than, say, half LEB of dirty space. May be half is
 294                 * not the optimal boundary - this should be tested and
 295                 * checked. This boundary should determine how much we use
 296                 * in-the-gaps to consolidate the index comparing to how much
 297                 * we use garbage collector to consolidate it. The "half"
 298                 * criteria just feels to be fine.
 299                 */
 300                if (sum < min_space || sum < c->half_leb_size)
 301                        idx_lp = NULL;
 302        }
 303
 304        if (heap->cnt) {
 305                lp = heap->arr[0];
 306                if (lp->dirty + lp->free < min_space)
 307                        lp = NULL;
 308        }
 309
 310        /* Pick the LEB with most space */
 311        if (idx_lp && lp) {
 312                if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty)
 313                        lp = idx_lp;
 314        } else if (idx_lp && !lp)
 315                lp = idx_lp;
 316
 317        if (lp) {
 318                ubifs_assert(lp->free + lp->dirty >= c->dead_wm);
 319                goto found;
 320        }
 321
 322        /* Did not find a dirty LEB on the dirty heaps, have to scan */
 323        dbg_find("scanning LPT for a dirty LEB");
 324        lp = scan_for_dirty(c, min_space, pick_free, exclude_index);
 325        if (IS_ERR(lp)) {
 326                err = PTR_ERR(lp);
 327                goto out;
 328        }
 329        ubifs_assert(lp->dirty >= c->dead_wm ||
 330                     (pick_free && lp->free + lp->dirty == c->leb_size));
 331
 332found:
 333        dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
 334                 lp->lnum, lp->free, lp->dirty, lp->flags);
 335
 336        lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 337                             lp->flags | LPROPS_TAKEN, 0);
 338        if (IS_ERR(lp)) {
 339                err = PTR_ERR(lp);
 340                goto out;
 341        }
 342
 343        memcpy(ret_lp, lp, sizeof(struct ubifs_lprops));
 344
 345out:
 346        ubifs_release_lprops(c);
 347        return err;
 348}
 349
 350/**
 351 * scan_for_free_cb - free space scan callback.
 352 * @c: the UBIFS file-system description object
 353 * @lprops: LEB properties to scan
 354 * @in_tree: whether the LEB properties are in main memory
 355 * @data: information passed to and from the caller of the scan
 356 *
 357 * This function returns a code that indicates whether the scan should continue
 358 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 359 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 360 * (%LPT_SCAN_STOP).
 361 */
 362static int scan_for_free_cb(struct ubifs_info *c,
 363                            const struct ubifs_lprops *lprops, int in_tree,
 364                            struct scan_data *data)
 365{
 366        int ret = LPT_SCAN_CONTINUE;
 367
 368        /* Exclude LEBs that are currently in use */
 369        if (lprops->flags & LPROPS_TAKEN)
 370                return LPT_SCAN_CONTINUE;
 371        /* Determine whether to add these LEB properties to the tree */
 372        if (!in_tree && valuable(c, lprops))
 373                ret |= LPT_SCAN_ADD;
 374        /* Exclude index LEBs */
 375        if (lprops->flags & LPROPS_INDEX)
 376                return ret;
 377        /* Exclude LEBs with too little space */
 378        if (lprops->free < data->min_space)
 379                return ret;
 380        /* If specified, exclude empty LEBs */
 381        if (!data->pick_free && lprops->free == c->leb_size)
 382                return ret;
 383        /*
 384         * LEBs that have only free and dirty space must not be allocated
 385         * because they may have been unmapped already or they may have data
 386         * that is obsolete only because of nodes that are still sitting in a
 387         * wbuf.
 388         */
 389        if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0)
 390                return ret;
 391        /* Finally we found space */
 392        data->lnum = lprops->lnum;
 393        return LPT_SCAN_ADD | LPT_SCAN_STOP;
 394}
 395
 396/**
 397 * do_find_free_space - find a data LEB with free space.
 398 * @c: the UBIFS file-system description object
 399 * @min_space: minimum amount of free space required
 400 * @pick_free: whether it is OK to scan for empty LEBs
 401 * @squeeze: whether to try to find space in a non-empty LEB first
 402 *
 403 * This function returns a pointer to the LEB properties found or a negative
 404 * error code.
 405 */
 406static
 407const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,
 408                                              int min_space, int pick_free,
 409                                              int squeeze)
 410{
 411        const struct ubifs_lprops *lprops;
 412        struct ubifs_lpt_heap *heap;
 413        struct scan_data data;
 414        int err, i;
 415
 416        if (squeeze) {
 417                lprops = ubifs_fast_find_free(c);
 418                if (lprops && lprops->free >= min_space)
 419                        return lprops;
 420        }
 421        if (pick_free) {
 422                lprops = ubifs_fast_find_empty(c);
 423                if (lprops)
 424                        return lprops;
 425        }
 426        if (!squeeze) {
 427                lprops = ubifs_fast_find_free(c);
 428                if (lprops && lprops->free >= min_space)
 429                        return lprops;
 430        }
 431        /* There may be an LEB with enough free space on the dirty heap */
 432        heap = &c->lpt_heap[LPROPS_DIRTY - 1];
 433        for (i = 0; i < heap->cnt; i++) {
 434                lprops = heap->arr[i];
 435                if (lprops->free >= min_space)
 436                        return lprops;
 437        }
 438        /*
 439         * A LEB may have fallen off of the bottom of the free heap, and ended
 440         * up as uncategorized even though it has enough free space for us now,
 441         * so check the uncategorized list. N.B. neither empty nor freeable LEBs
 442         * can end up as uncategorized because they are kept on lists not
 443         * finite-sized heaps.
 444         */
 445        list_for_each_entry(lprops, &c->uncat_list, list) {
 446                if (lprops->flags & LPROPS_TAKEN)
 447                        continue;
 448                if (lprops->flags & LPROPS_INDEX)
 449                        continue;
 450                if (lprops->free >= min_space)
 451                        return lprops;
 452        }
 453        /* We have looked everywhere in main memory, now scan the flash */
 454        if (c->pnodes_have >= c->pnode_cnt)
 455                /* All pnodes are in memory, so skip scan */
 456                return ERR_PTR(-ENOSPC);
 457        data.min_space = min_space;
 458        data.pick_free = pick_free;
 459        data.lnum = -1;
 460        err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
 461                                    (ubifs_lpt_scan_callback)scan_for_free_cb,
 462                                    &data);
 463        if (err)
 464                return ERR_PTR(err);
 465        ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
 466        c->lscan_lnum = data.lnum;
 467        lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
 468        if (IS_ERR(lprops))
 469                return lprops;
 470        ubifs_assert(lprops->lnum == data.lnum);
 471        ubifs_assert(lprops->free >= min_space);
 472        ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
 473        ubifs_assert(!(lprops->flags & LPROPS_INDEX));
 474        return lprops;
 475}
 476
 477/**
 478 * ubifs_find_free_space - find a data LEB with free space.
 479 * @c: the UBIFS file-system description object
 480 * @min_space: minimum amount of required free space
 481 * @offs: contains offset of where free space starts on exit
 482 * @squeeze: whether to try to find space in a non-empty LEB first
 483 *
 484 * This function looks for an LEB with at least @min_space bytes of free space.
 485 * It tries to find an empty LEB if possible. If no empty LEBs are available,
 486 * this function searches for a non-empty data LEB. The returned LEB is marked
 487 * as "taken".
 488 *
 489 * This function returns found LEB number in case of success, %-ENOSPC if it
 490 * failed to find a LEB with @min_space bytes of free space and other a negative
 491 * error codes in case of failure.
 492 */
 493int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs,
 494                          int squeeze)
 495{
 496        const struct ubifs_lprops *lprops;
 497        int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags;
 498
 499        dbg_find("min_space %d", min_space);
 500        ubifs_get_lprops(c);
 501
 502        /* Check if there are enough empty LEBs for commit */
 503        spin_lock(&c->space_lock);
 504        if (c->bi.min_idx_lebs > c->lst.idx_lebs)
 505                rsvd_idx_lebs = c->bi.min_idx_lebs -  c->lst.idx_lebs;
 506        else
 507                rsvd_idx_lebs = 0;
 508        lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt -
 509               c->lst.taken_empty_lebs;
 510        if (rsvd_idx_lebs < lebs)
 511                /*
 512                 * OK to allocate an empty LEB, but we still don't want to go
 513                 * looking for one if there aren't any.
 514                 */
 515                if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
 516                        pick_free = 1;
 517                        /*
 518                         * Because we release the space lock, we must account
 519                         * for this allocation here. After the LEB properties
 520                         * flags have been updated, we subtract one. Note, the
 521                         * result of this is that lprops also decreases
 522                         * @taken_empty_lebs in 'ubifs_change_lp()', so it is
 523                         * off by one for a short period of time which may
 524                         * introduce a small disturbance to budgeting
 525                         * calculations, but this is harmless because at the
 526                         * worst case this would make the budgeting subsystem
 527                         * be more pessimistic than needed.
 528                         *
 529                         * Fundamentally, this is about serialization of the
 530                         * budgeting and lprops subsystems. We could make the
 531                         * @space_lock a mutex and avoid dropping it before
 532                         * calling 'ubifs_change_lp()', but mutex is more
 533                         * heavy-weight, and we want budgeting to be as fast as
 534                         * possible.
 535                         */
 536                        c->lst.taken_empty_lebs += 1;
 537                }
 538        spin_unlock(&c->space_lock);
 539
 540        lprops = do_find_free_space(c, min_space, pick_free, squeeze);
 541        if (IS_ERR(lprops)) {
 542                err = PTR_ERR(lprops);
 543                goto out;
 544        }
 545
 546        lnum = lprops->lnum;
 547        flags = lprops->flags | LPROPS_TAKEN;
 548
 549        lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);
 550        if (IS_ERR(lprops)) {
 551                err = PTR_ERR(lprops);
 552                goto out;
 553        }
 554
 555        if (pick_free) {
 556                spin_lock(&c->space_lock);
 557                c->lst.taken_empty_lebs -= 1;
 558                spin_unlock(&c->space_lock);
 559        }
 560
 561        *offs = c->leb_size - lprops->free;
 562        ubifs_release_lprops(c);
 563
 564        if (*offs == 0) {
 565                /*
 566                 * Ensure that empty LEBs have been unmapped. They may not have
 567                 * been, for example, because of an unclean unmount.  Also
 568                 * LEBs that were freeable LEBs (free + dirty == leb_size) will
 569                 * not have been unmapped.
 570                 */
 571                err = ubifs_leb_unmap(c, lnum);
 572                if (err)
 573                        return err;
 574        }
 575
 576        dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs);
 577        ubifs_assert(*offs <= c->leb_size - min_space);
 578        return lnum;
 579
 580out:
 581        if (pick_free) {
 582                spin_lock(&c->space_lock);
 583                c->lst.taken_empty_lebs -= 1;
 584                spin_unlock(&c->space_lock);
 585        }
 586        ubifs_release_lprops(c);
 587        return err;
 588}
 589
 590/**
 591 * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
 592 * @c: the UBIFS file-system description object
 593 * @lprops: LEB properties to scan
 594 * @in_tree: whether the LEB properties are in main memory
 595 * @data: information passed to and from the caller of the scan
 596 *
 597 * This function returns a code that indicates whether the scan should continue
 598 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 599 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 600 * (%LPT_SCAN_STOP).
 601 */
 602static int scan_for_idx_cb(struct ubifs_info *c,
 603                           const struct ubifs_lprops *lprops, int in_tree,
 604                           struct scan_data *data)
 605{
 606        int ret = LPT_SCAN_CONTINUE;
 607
 608        /* Exclude LEBs that are currently in use */
 609        if (lprops->flags & LPROPS_TAKEN)
 610                return LPT_SCAN_CONTINUE;
 611        /* Determine whether to add these LEB properties to the tree */
 612        if (!in_tree && valuable(c, lprops))
 613                ret |= LPT_SCAN_ADD;
 614        /* Exclude index LEBS */
 615        if (lprops->flags & LPROPS_INDEX)
 616                return ret;
 617        /* Exclude LEBs that cannot be made empty */
 618        if (lprops->free + lprops->dirty != c->leb_size)
 619                return ret;
 620        /*
 621         * We are allocating for the index so it is safe to allocate LEBs with
 622         * only free and dirty space, because write buffers are sync'd at commit
 623         * start.
 624         */
 625        data->lnum = lprops->lnum;
 626        return LPT_SCAN_ADD | LPT_SCAN_STOP;
 627}
 628
 629/**
 630 * scan_for_leb_for_idx - scan for a free LEB for the index.
 631 * @c: the UBIFS file-system description object
 632 */
 633static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
 634{
 635        struct ubifs_lprops *lprops;
 636        struct scan_data data;
 637        int err;
 638
 639        data.lnum = -1;
 640        err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
 641                                    (ubifs_lpt_scan_callback)scan_for_idx_cb,
 642                                    &data);
 643        if (err)
 644                return ERR_PTR(err);
 645        ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
 646        c->lscan_lnum = data.lnum;
 647        lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
 648        if (IS_ERR(lprops))
 649                return lprops;
 650        ubifs_assert(lprops->lnum == data.lnum);
 651        ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
 652        ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
 653        ubifs_assert(!(lprops->flags & LPROPS_INDEX));
 654        return lprops;
 655}
 656
 657/**
 658 * ubifs_find_free_leb_for_idx - find a free LEB for the index.
 659 * @c: the UBIFS file-system description object
 660 *
 661 * This function looks for a free LEB and returns that LEB number. The returned
 662 * LEB is marked as "taken", "index".
 663 *
 664 * Only empty LEBs are allocated. This is for two reasons. First, the commit
 665 * calculates the number of LEBs to allocate based on the assumption that they
 666 * will be empty. Secondly, free space at the end of an index LEB is not
 667 * guaranteed to be empty because it may have been used by the in-the-gaps
 668 * method prior to an unclean unmount.
 669 *
 670 * If no LEB is found %-ENOSPC is returned. For other failures another negative
 671 * error code is returned.
 672 */
 673int ubifs_find_free_leb_for_idx(struct ubifs_info *c)
 674{
 675        const struct ubifs_lprops *lprops;
 676        int lnum = -1, err, flags;
 677
 678        ubifs_get_lprops(c);
 679
 680        lprops = ubifs_fast_find_empty(c);
 681        if (!lprops) {
 682                lprops = ubifs_fast_find_freeable(c);
 683                if (!lprops) {
 684                        ubifs_assert(c->freeable_cnt == 0);
 685                        if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
 686                                lprops = scan_for_leb_for_idx(c);
 687                                if (IS_ERR(lprops)) {
 688                                        err = PTR_ERR(lprops);
 689                                        goto out;
 690                                }
 691                        }
 692                }
 693        }
 694
 695        if (!lprops) {
 696                err = -ENOSPC;
 697                goto out;
 698        }
 699
 700        lnum = lprops->lnum;
 701
 702        dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
 703                 lnum, lprops->free, lprops->dirty, lprops->flags);
 704
 705        flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
 706        lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
 707        if (IS_ERR(lprops)) {
 708                err = PTR_ERR(lprops);
 709                goto out;
 710        }
 711
 712        ubifs_release_lprops(c);
 713
 714        /*
 715         * Ensure that empty LEBs have been unmapped. They may not have been,
 716         * for example, because of an unclean unmount. Also LEBs that were
 717         * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
 718         */
 719        err = ubifs_leb_unmap(c, lnum);
 720        if (err) {
 721                ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
 722                                    LPROPS_TAKEN | LPROPS_INDEX, 0);
 723                return err;
 724        }
 725
 726        return lnum;
 727
 728out:
 729        ubifs_release_lprops(c);
 730        return err;
 731}
 732
 733static int cmp_dirty_idx(const struct ubifs_lprops **a,
 734                         const struct ubifs_lprops **b)
 735{
 736        const struct ubifs_lprops *lpa = *a;
 737        const struct ubifs_lprops *lpb = *b;
 738
 739        return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
 740}
 741
 742static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
 743                           int size)
 744{
 745        struct ubifs_lprops *t = *a;
 746
 747        *a = *b;
 748        *b = t;
 749}
 750
 751/**
 752 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
 753 * @c: the UBIFS file-system description object
 754 *
 755 * This function is called each commit to create an array of LEB numbers of
 756 * dirty index LEBs sorted in order of dirty and free space.  This is used by
 757 * the in-the-gaps method of TNC commit.
 758 */
 759int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
 760{
 761        int i;
 762
 763        ubifs_get_lprops(c);
 764        /* Copy the LPROPS_DIRTY_IDX heap */
 765        c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
 766        memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
 767               sizeof(void *) * c->dirty_idx.cnt);
 768        /* Sort it so that the dirtiest is now at the end */
 769        sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
 770             (int (*)(const void *, const void *))cmp_dirty_idx,
 771             (void (*)(void *, void *, int))swap_dirty_idx);
 772        dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
 773        if (c->dirty_idx.cnt)
 774                dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
 775                         c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
 776                         c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
 777                         c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
 778        /* Replace the lprops pointers with LEB numbers */
 779        for (i = 0; i < c->dirty_idx.cnt; i++)
 780                c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
 781        ubifs_release_lprops(c);
 782        return 0;
 783}
 784
 785/**
 786 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
 787 * @c: the UBIFS file-system description object
 788 * @lprops: LEB properties to scan
 789 * @in_tree: whether the LEB properties are in main memory
 790 * @data: information passed to and from the caller of the scan
 791 *
 792 * This function returns a code that indicates whether the scan should continue
 793 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 794 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 795 * (%LPT_SCAN_STOP).
 796 */
 797static int scan_dirty_idx_cb(struct ubifs_info *c,
 798                           const struct ubifs_lprops *lprops, int in_tree,
 799                           struct scan_data *data)
 800{
 801        int ret = LPT_SCAN_CONTINUE;
 802
 803        /* Exclude LEBs that are currently in use */
 804        if (lprops->flags & LPROPS_TAKEN)
 805                return LPT_SCAN_CONTINUE;
 806        /* Determine whether to add these LEB properties to the tree */
 807        if (!in_tree && valuable(c, lprops))
 808                ret |= LPT_SCAN_ADD;
 809        /* Exclude non-index LEBs */
 810        if (!(lprops->flags & LPROPS_INDEX))
 811                return ret;
 812        /* Exclude LEBs with too little space */
 813        if (lprops->free + lprops->dirty < c->min_idx_node_sz)
 814                return ret;
 815        /* Finally we found space */
 816        data->lnum = lprops->lnum;
 817        return LPT_SCAN_ADD | LPT_SCAN_STOP;
 818}
 819
 820/**
 821 * find_dirty_idx_leb - find a dirty index LEB.
 822 * @c: the UBIFS file-system description object
 823 *
 824 * This function returns LEB number upon success and a negative error code upon
 825 * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
 826 * found.
 827 *
 828 * Note that this function scans the entire LPT but it is called very rarely.
 829 */
 830static int find_dirty_idx_leb(struct ubifs_info *c)
 831{
 832        const struct ubifs_lprops *lprops;
 833        struct ubifs_lpt_heap *heap;
 834        struct scan_data data;
 835        int err, i, ret;
 836
 837        /* Check all structures in memory first */
 838        data.lnum = -1;
 839        heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 840        for (i = 0; i < heap->cnt; i++) {
 841                lprops = heap->arr[i];
 842                ret = scan_dirty_idx_cb(c, lprops, 1, &data);
 843                if (ret & LPT_SCAN_STOP)
 844                        goto found;
 845        }
 846        list_for_each_entry(lprops, &c->frdi_idx_list, list) {
 847                ret = scan_dirty_idx_cb(c, lprops, 1, &data);
 848                if (ret & LPT_SCAN_STOP)
 849                        goto found;
 850        }
 851        list_for_each_entry(lprops, &c->uncat_list, list) {
 852                ret = scan_dirty_idx_cb(c, lprops, 1, &data);
 853                if (ret & LPT_SCAN_STOP)
 854                        goto found;
 855        }
 856        if (c->pnodes_have >= c->pnode_cnt)
 857                /* All pnodes are in memory, so skip scan */
 858                return -ENOSPC;
 859        err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
 860                                    (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
 861                                    &data);
 862        if (err)
 863                return err;
 864found:
 865        ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
 866        c->lscan_lnum = data.lnum;
 867        lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
 868        if (IS_ERR(lprops))
 869                return PTR_ERR(lprops);
 870        ubifs_assert(lprops->lnum == data.lnum);
 871        ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz);
 872        ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
 873        ubifs_assert((lprops->flags & LPROPS_INDEX));
 874
 875        dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
 876                 lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
 877
 878        lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
 879                                 lprops->flags | LPROPS_TAKEN, 0);
 880        if (IS_ERR(lprops))
 881                return PTR_ERR(lprops);
 882
 883        return lprops->lnum;
 884}
 885
 886/**
 887 * get_idx_gc_leb - try to get a LEB number from trivial GC.
 888 * @c: the UBIFS file-system description object
 889 */
 890static int get_idx_gc_leb(struct ubifs_info *c)
 891{
 892        const struct ubifs_lprops *lp;
 893        int err, lnum;
 894
 895        err = ubifs_get_idx_gc_leb(c);
 896        if (err < 0)
 897                return err;
 898        lnum = err;
 899        /*
 900         * The LEB was due to be unmapped after the commit but
 901         * it is needed now for this commit.
 902         */
 903        lp = ubifs_lpt_lookup_dirty(c, lnum);
 904        if (IS_ERR(lp))
 905                return PTR_ERR(lp);
 906        lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 907                             lp->flags | LPROPS_INDEX, -1);
 908        if (IS_ERR(lp))
 909                return PTR_ERR(lp);
 910        dbg_find("LEB %d, dirty %d and free %d flags %#x",
 911                 lp->lnum, lp->dirty, lp->free, lp->flags);
 912        return lnum;
 913}
 914
 915/**
 916 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
 917 * @c: the UBIFS file-system description object
 918 */
 919static int find_dirtiest_idx_leb(struct ubifs_info *c)
 920{
 921        const struct ubifs_lprops *lp;
 922        int lnum;
 923
 924        while (1) {
 925                if (!c->dirty_idx.cnt)
 926                        return -ENOSPC;
 927                /* The lprops pointers were replaced by LEB numbers */
 928                lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
 929                lp = ubifs_lpt_lookup(c, lnum);
 930                if (IS_ERR(lp))
 931                        return PTR_ERR(lp);
 932                if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
 933                        continue;
 934                lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 935                                     lp->flags | LPROPS_TAKEN, 0);
 936                if (IS_ERR(lp))
 937                        return PTR_ERR(lp);
 938                break;
 939        }
 940        dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
 941                 lp->free, lp->flags);
 942        ubifs_assert(lp->flags & LPROPS_TAKEN);
 943        ubifs_assert(lp->flags & LPROPS_INDEX);
 944        return lnum;
 945}
 946
 947/**
 948 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
 949 * @c: the UBIFS file-system description object
 950 *
 951 * This function attempts to find an untaken index LEB with the most free and
 952 * dirty space that can be used without overwriting index nodes that were in the
 953 * last index committed.
 954 */
 955int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
 956{
 957        int err;
 958
 959        ubifs_get_lprops(c);
 960
 961        /*
 962         * We made an array of the dirtiest index LEB numbers as at the start of
 963         * last commit.  Try that array first.
 964         */
 965        err = find_dirtiest_idx_leb(c);
 966
 967        /* Next try scanning the entire LPT */
 968        if (err == -ENOSPC)
 969                err = find_dirty_idx_leb(c);
 970
 971        /* Finally take any index LEBs awaiting trivial GC */
 972        if (err == -ENOSPC)
 973                err = get_idx_gc_leb(c);
 974
 975        ubifs_release_lprops(c);
 976        return err;
 977}
 978
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.