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