Merge tag 'scsi-sg' of git://git.kernel.org/pub/scm/linux/kernel/git/jejb/scsi
[platform/kernel/linux-rpi.git] / 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 }