fs/ubifs/find.c

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