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(c, 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(c, lprops->lnum == data.lnum);
 192         ubifs_assert(c, lprops->free + lprops->dirty >= min_space);
 193         ubifs_assert(c, lprops->dirty >= c->dead_wm ||
 194                      (pick_free &&
 195                       lprops->free + lprops->dirty == c->leb_size));
 196         ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
 197         ubifs_assert(c, !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  */
 233 int 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(c, 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(c, lp->dirty >= c->dead_wm ||
 330                      (pick_free && lp->free + lp->dirty == c->leb_size));
 331
 332 found:
 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
 345 out:
 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  */
 362 static 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  */
 406 static
 407 const 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(c, 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(c, lprops->lnum == data.lnum);
 471         ubifs_assert(c, lprops->free >= min_space);
 472         ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
 473         ubifs_assert(c, !(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  */
 493 int 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(c, *offs <= c->leb_size - min_space);
 578         return lnum;
 579
 580 out:
 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  */
 602 static 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  */
 633 static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
 634 {
 635         const 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(c, 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(c, lprops->lnum == data.lnum);
 651         ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);
 652         ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
 653         ubifs_assert(c, !(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  */
 673 int 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                         /*
 685                          * The first condition means the following: go scan the
 686                          * LPT if there are uncategorized lprops, which means
 687                          * there may be freeable LEBs there (UBIFS does not
 688                          * store the information about freeable LEBs in the
 689                          * master node).
 690                          */
 691                         if (c->in_a_category_cnt != c->main_lebs ||
 692                             c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
 693                                 ubifs_assert(c, c->freeable_cnt == 0);
 694                                 lprops = scan_for_leb_for_idx(c);
 695                                 if (IS_ERR(lprops)) {
 696                                         err = PTR_ERR(lprops);
 697                                         goto out;
 698                                 }
 699                         }
 700                 }
 701         }
 702
 703         if (!lprops) {
 704                 err = -ENOSPC;
 705                 goto out;
 706         }
 707
 708         lnum = lprops->lnum;
 709
 710         dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
 711                  lnum, lprops->free, lprops->dirty, lprops->flags);
 712
 713         flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
 714         lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
 715         if (IS_ERR(lprops)) {
 716                 err = PTR_ERR(lprops);
 717                 goto out;
 718         }
 719
 720         ubifs_release_lprops(c);
 721
 722         /*
 723          * Ensure that empty LEBs have been unmapped. They may not have been,
 724          * for example, because of an unclean unmount. Also LEBs that were
 725          * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
 726          */
 727         err = ubifs_leb_unmap(c, lnum);
 728         if (err) {
 729                 ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
 730                                     LPROPS_TAKEN | LPROPS_INDEX, 0);
 731                 return err;
 732         }
 733
 734         return lnum;
 735
 736 out:
 737         ubifs_release_lprops(c);
 738         return err;
 739 }
 740
 741 static int cmp_dirty_idx(const struct ubifs_lprops **a,
 742                          const struct ubifs_lprops **b)
 743 {
 744         const struct ubifs_lprops *lpa = *a;
 745         const struct ubifs_lprops *lpb = *b;
 746
 747         return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
 748 }
 749
 750 static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
 751                            int size)
 752 {
 753         swap(*a, *b);
 754 }
 755
 756 /**
 757  * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
 758  * @c: the UBIFS file-system description object
 759  *
 760  * This function is called each commit to create an array of LEB numbers of
 761  * dirty index LEBs sorted in order of dirty and free space.  This is used by
 762  * the in-the-gaps method of TNC commit.
 763  */
 764 int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
 765 {
 766         int i;
 767
 768         ubifs_get_lprops(c);
 769         /* Copy the LPROPS_DIRTY_IDX heap */
 770         c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
 771         memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
 772                sizeof(void *) * c->dirty_idx.cnt);
 773         /* Sort it so that the dirtiest is now at the end */
 774         sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
 775              (int (*)(const void *, const void *))cmp_dirty_idx,
 776              (void (*)(void *, void *, int))swap_dirty_idx);
 777         dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
 778         if (c->dirty_idx.cnt)
 779                 dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
 780                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
 781                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
 782                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
 783         /* Replace the lprops pointers with LEB numbers */
 784         for (i = 0; i < c->dirty_idx.cnt; i++)
 785                 c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
 786         ubifs_release_lprops(c);
 787         return 0;
 788 }
 789
 790 /**
 791  * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
 792  * @c: the UBIFS file-system description object
 793  * @lprops: LEB properties to scan
 794  * @in_tree: whether the LEB properties are in main memory
 795  * @data: information passed to and from the caller of the scan
 796  *
 797  * This function returns a code that indicates whether the scan should continue
 798  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
 799  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
 800  * (%LPT_SCAN_STOP).
 801  */
 802 static int scan_dirty_idx_cb(struct ubifs_info *c,
 803                            const struct ubifs_lprops *lprops, int in_tree,
 804                            struct scan_data *data)
 805 {
 806         int ret = LPT_SCAN_CONTINUE;
 807
 808         /* Exclude LEBs that are currently in use */
 809         if (lprops->flags & LPROPS_TAKEN)
 810                 return LPT_SCAN_CONTINUE;
 811         /* Determine whether to add these LEB properties to the tree */
 812         if (!in_tree && valuable(c, lprops))
 813                 ret |= LPT_SCAN_ADD;
 814         /* Exclude non-index LEBs */
 815         if (!(lprops->flags & LPROPS_INDEX))
 816                 return ret;
 817         /* Exclude LEBs with too little space */
 818         if (lprops->free + lprops->dirty < c->min_idx_node_sz)
 819                 return ret;
 820         /* Finally we found space */
 821         data->lnum = lprops->lnum;
 822         return LPT_SCAN_ADD | LPT_SCAN_STOP;
 823 }
 824
 825 /**
 826  * find_dirty_idx_leb - find a dirty index LEB.
 827  * @c: the UBIFS file-system description object
 828  *
 829  * This function returns LEB number upon success and a negative error code upon
 830  * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
 831  * found.
 832  *
 833  * Note that this function scans the entire LPT but it is called very rarely.
 834  */
 835 static int find_dirty_idx_leb(struct ubifs_info *c)
 836 {
 837         const struct ubifs_lprops *lprops;
 838         struct ubifs_lpt_heap *heap;
 839         struct scan_data data;
 840         int err, i, ret;
 841
 842         /* Check all structures in memory first */
 843         data.lnum = -1;
 844         heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
 845         for (i = 0; i < heap->cnt; i++) {
 846                 lprops = heap->arr[i];
 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->frdi_idx_list, list) {
 852                 ret = scan_dirty_idx_cb(c, lprops, 1, &data);
 853                 if (ret & LPT_SCAN_STOP)
 854                         goto found;
 855         }
 856         list_for_each_entry(lprops, &c->uncat_list, list) {
 857                 ret = scan_dirty_idx_cb(c, lprops, 1, &data);
 858                 if (ret & LPT_SCAN_STOP)
 859                         goto found;
 860         }
 861         if (c->pnodes_have >= c->pnode_cnt)
 862                 /* All pnodes are in memory, so skip scan */
 863                 return -ENOSPC;
 864         err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
 865                                     (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
 866                                     &data);
 867         if (err)
 868                 return err;
 869 found:
 870         ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt);
 871         c->lscan_lnum = data.lnum;
 872         lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
 873         if (IS_ERR(lprops))
 874                 return PTR_ERR(lprops);
 875         ubifs_assert(c, lprops->lnum == data.lnum);
 876         ubifs_assert(c, lprops->free + lprops->dirty >= c->min_idx_node_sz);
 877         ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
 878         ubifs_assert(c, (lprops->flags & LPROPS_INDEX));
 879
 880         dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
 881                  lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
 882
 883         lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
 884                                  lprops->flags | LPROPS_TAKEN, 0);
 885         if (IS_ERR(lprops))
 886                 return PTR_ERR(lprops);
 887
 888         return lprops->lnum;
 889 }
 890
 891 /**
 892  * get_idx_gc_leb - try to get a LEB number from trivial GC.
 893  * @c: the UBIFS file-system description object
 894  */
 895 static int get_idx_gc_leb(struct ubifs_info *c)
 896 {
 897         const struct ubifs_lprops *lp;
 898         int err, lnum;
 899
 900         err = ubifs_get_idx_gc_leb(c);
 901         if (err < 0)
 902                 return err;
 903         lnum = err;
 904         /*
 905          * The LEB was due to be unmapped after the commit but
 906          * it is needed now for this commit.
 907          */
 908         lp = ubifs_lpt_lookup_dirty(c, lnum);
 909         if (IS_ERR(lp))
 910                 return PTR_ERR(lp);
 911         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 912                              lp->flags | LPROPS_INDEX, -1);
 913         if (IS_ERR(lp))
 914                 return PTR_ERR(lp);
 915         dbg_find("LEB %d, dirty %d and free %d flags %#x",
 916                  lp->lnum, lp->dirty, lp->free, lp->flags);
 917         return lnum;
 918 }
 919
 920 /**
 921  * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
 922  * @c: the UBIFS file-system description object
 923  */
 924 static int find_dirtiest_idx_leb(struct ubifs_info *c)
 925 {
 926         const struct ubifs_lprops *lp;
 927         int lnum;
 928
 929         while (1) {
 930                 if (!c->dirty_idx.cnt)
 931                         return -ENOSPC;
 932                 /* The lprops pointers were replaced by LEB numbers */
 933                 lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
 934                 lp = ubifs_lpt_lookup(c, lnum);
 935                 if (IS_ERR(lp))
 936                         return PTR_ERR(lp);
 937                 if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
 938                         continue;
 939                 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
 940                                      lp->flags | LPROPS_TAKEN, 0);
 941                 if (IS_ERR(lp))
 942                         return PTR_ERR(lp);
 943                 break;
 944         }
 945         dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
 946                  lp->free, lp->flags);
 947         ubifs_assert(c, lp->flags & LPROPS_TAKEN);
 948         ubifs_assert(c, lp->flags & LPROPS_INDEX);
 949         return lnum;
 950 }
 951
 952 /**
 953  * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
 954  * @c: the UBIFS file-system description object
 955  *
 956  * This function attempts to find an untaken index LEB with the most free and
 957  * dirty space that can be used without overwriting index nodes that were in the
 958  * last index committed.
 959  */
 960 int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
 961 {
 962         int err;
 963
 964         ubifs_get_lprops(c);
 965
 966         /*
 967          * We made an array of the dirtiest index LEB numbers as at the start of
 968          * last commit.  Try that array first.
 969          */
 970         err = find_dirtiest_idx_leb(c);
 971
 972         /* Next try scanning the entire LPT */
 973         if (err == -ENOSPC)
 974                 err = find_dirty_idx_leb(c);
 975
 976         /* Finally take any index LEBs awaiting trivial GC */
 977         if (err == -ENOSPC)
 978                 err = get_idx_gc_leb(c);
 979
 980         ubifs_release_lprops(c);
 981         return err;
 982 }