Merge commit 'v2.6.27-rc6' into core/rcu
[linux-2.6] / fs / ubifs / find.c
1 /*
2  * This file is part of UBIFS.
3  *
4  * Copyright (C) 2006-2008 Nokia Corporation.
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License version 2 as published by
8  * the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
13  * more details.
14  *
15  * You should have received a copy of the GNU General Public License along with
16  * this program; if not, write to the Free Software Foundation, Inc., 51
17  * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  *
19  * Authors: Artem Bityutskiy (Битюцкий Артём)
20  *          Adrian Hunter
21  */
22
23 /*
24  * This file contains functions for finding LEBs for various purposes e.g.
25  * garbage collection. In general, lprops category heaps and lists are used
26  * for fast access, falling back on scanning the LPT as a last resort.
27  */
28
29 #include <linux/sort.h>
30 #include "ubifs.h"
31
32 /**
33  * struct scan_data - data provided to scan callback functions
34  * @min_space: minimum number of bytes for which to scan
35  * @pick_free: whether it is OK to scan for empty LEBs
36  * @lnum: LEB number found is returned here
37  * @exclude_index: whether to exclude index LEBs
38  */
39 struct scan_data {
40         int min_space;
41         int pick_free;
42         int lnum;
43         int exclude_index;
44 };
45
46 /**
47  * valuable - determine whether LEB properties are valuable.
48  * @c: the UBIFS file-system description object
49  * @lprops: LEB properties
50  *
51  * This function return %1 if the LEB properties should be added to the LEB
52  * properties tree in memory. Otherwise %0 is returned.
53  */
54 static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops)
55 {
56         int n, cat = lprops->flags & LPROPS_CAT_MASK;
57         struct ubifs_lpt_heap *heap;
58
59         switch (cat) {
60         case LPROPS_DIRTY:
61         case LPROPS_DIRTY_IDX:
62         case LPROPS_FREE:
63                 heap = &c->lpt_heap[cat - 1];
64                 if (heap->cnt < heap->max_cnt)
65                         return 1;
66                 if (lprops->free + lprops->dirty >= c->dark_wm)
67                         return 1;
68                 return 0;
69         case LPROPS_EMPTY:
70                 n = c->lst.empty_lebs + c->freeable_cnt -
71                     c->lst.taken_empty_lebs;
72                 if (n < c->lsave_cnt)
73                         return 1;
74                 return 0;
75         case LPROPS_FREEABLE:
76                 return 1;
77         case LPROPS_FRDI_IDX:
78                 return 1;
79         }
80         return 0;
81 }
82
83 /**
84  * scan_for_dirty_cb - dirty space scan callback.
85  * @c: the UBIFS file-system description object
86  * @lprops: LEB properties to scan
87  * @in_tree: whether the LEB properties are in main memory
88  * @data: information passed to and from the caller of the scan
89  *
90  * This function returns a code that indicates whether the scan should continue
91  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
92  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
93  * (%LPT_SCAN_STOP).
94  */
95 static int scan_for_dirty_cb(struct ubifs_info *c,
96                              const struct ubifs_lprops *lprops, int in_tree,
97                              struct scan_data *data)
98 {
99         int ret = LPT_SCAN_CONTINUE;
100
101         /* Exclude LEBs that are currently in use */
102         if (lprops->flags & LPROPS_TAKEN)
103                 return LPT_SCAN_CONTINUE;
104         /* Determine whether to add these LEB properties to the tree */
105         if (!in_tree && valuable(c, lprops))
106                 ret |= LPT_SCAN_ADD;
107         /* Exclude LEBs with too little space */
108         if (lprops->free + lprops->dirty < data->min_space)
109                 return ret;
110         /* If specified, exclude index LEBs */
111         if (data->exclude_index && lprops->flags & LPROPS_INDEX)
112                 return ret;
113         /* If specified, exclude empty or freeable LEBs */
114         if (lprops->free + lprops->dirty == c->leb_size) {
115                 if (!data->pick_free)
116                         return ret;
117         /* Exclude LEBs with too little dirty space (unless it is empty) */
118         } else if (lprops->dirty < c->dead_wm)
119                 return ret;
120         /* Finally we found space */
121         data->lnum = lprops->lnum;
122         return LPT_SCAN_ADD | LPT_SCAN_STOP;
123 }
124
125 /**
126  * scan_for_dirty - find a data LEB with free space.
127  * @c: the UBIFS file-system description object
128  * @min_space: minimum amount free plus dirty space the returned LEB has to
129  *             have
130  * @pick_free: if it is OK to return a free or freeable LEB
131  * @exclude_index: whether to exclude index LEBs
132  *
133  * This function returns a pointer to the LEB properties found or a negative
134  * error code.
135  */
136 static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c,
137                                                  int min_space, int pick_free,
138                                                  int exclude_index)
139 {
140         const struct ubifs_lprops *lprops;
141         struct ubifs_lpt_heap *heap;
142         struct scan_data data;
143         int err, i;
144
145         /* There may be an LEB with enough dirty space on the free heap */
146         heap = &c->lpt_heap[LPROPS_FREE - 1];
147         for (i = 0; i < heap->cnt; i++) {
148                 lprops = heap->arr[i];
149                 if (lprops->free + lprops->dirty < min_space)
150                         continue;
151                 if (lprops->dirty < c->dead_wm)
152                         continue;
153                 return lprops;
154         }
155         /*
156          * A LEB may have fallen off of the bottom of the dirty heap, and ended
157          * up as uncategorized even though it has enough dirty space for us now,
158          * so check the uncategorized list. N.B. neither empty nor freeable LEBs
159          * can end up as uncategorized because they are kept on lists not
160          * finite-sized heaps.
161          */
162         list_for_each_entry(lprops, &c->uncat_list, list) {
163                 if (lprops->flags & LPROPS_TAKEN)
164                         continue;
165                 if (lprops->free + lprops->dirty < min_space)
166                         continue;
167                 if (exclude_index && (lprops->flags & LPROPS_INDEX))
168                         continue;
169                 if (lprops->dirty < c->dead_wm)
170                         continue;
171                 return lprops;
172         }
173         /* We have looked everywhere in main memory, now scan the flash */
174         if (c->pnodes_have >= c->pnode_cnt)
175                 /* All pnodes are in memory, so skip scan */
176                 return ERR_PTR(-ENOSPC);
177         data.min_space = min_space;
178         data.pick_free = pick_free;
179         data.lnum = -1;
180         data.exclude_index = exclude_index;
181         err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
182                                     (ubifs_lpt_scan_callback)scan_for_dirty_cb,
183                                     &data);
184         if (err)
185                 return ERR_PTR(err);
186         ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
187         c->lscan_lnum = data.lnum;
188         lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
189         if (IS_ERR(lprops))
190                 return lprops;
191         ubifs_assert(lprops->lnum == data.lnum);
192         ubifs_assert(lprops->free + lprops->dirty >= min_space);
193         ubifs_assert(lprops->dirty >= c->dead_wm ||
194                      (pick_free &&
195                       lprops->free + lprops->dirty == c->leb_size));
196         ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
197         ubifs_assert(!exclude_index || !(lprops->flags & LPROPS_INDEX));
198         return lprops;
199 }
200
201 /**
202  * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector.
203  * @c: the UBIFS file-system description object
204  * @ret_lp: LEB properties are returned here on exit
205  * @min_space: minimum amount free plus dirty space the returned LEB has to
206  *             have
207  * @pick_free: controls whether it is OK to pick empty or index LEBs
208  *
209  * This function tries to find a dirty logical eraseblock which has at least
210  * @min_space free and dirty space. It prefers to take an LEB from the dirty or
211  * dirty index heap, and it falls-back to LPT scanning if the heaps are empty
212  * or do not have an LEB which satisfies the @min_space criteria.
213  *
214  * Note, 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->min_idx_lebs >= c->lst.idx_lebs) {
256                         rsvd_idx_lebs = c->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->min_idx_lebs >= c->lst.idx_lebs);
280                 spin_unlock(&c->space_lock);
281         }
282
283         /* Look on the dirty and dirty index heaps */
284         heap = &c->lpt_heap[LPROPS_DIRTY - 1];
285         idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
286
287         if (idx_heap->cnt && !exclude_index) {
288                 idx_lp = idx_heap->arr[0];
289                 sum = idx_lp->free + idx_lp->dirty;
290                 /*
291                  * Since we reserve thrice as much space for the index than it
292                  * actually takes, it does not make sense to pick indexing LEBs
293                  * with less than, say, half LEB of dirty space. May be half is
294                  * not the optimal boundary - this should be tested and
295                  * checked. This boundary should determine how much we use
296                  * in-the-gaps to consolidate the index comparing to how much
297                  * we use garbage collector to consolidate it. The "half"
298                  * criteria just feels to be fine.
299                  */
300                 if (sum < min_space || sum < c->half_leb_size)
301                         idx_lp = NULL;
302         }
303
304         if (heap->cnt) {
305                 lp = heap->arr[0];
306                 if (lp->dirty + lp->free < min_space)
307                         lp = NULL;
308         }
309
310         /* Pick the LEB with most space */
311         if (idx_lp && lp) {
312                 if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty)
313                         lp = idx_lp;
314         } else if (idx_lp && !lp)
315                 lp = idx_lp;
316
317         if (lp) {
318                 ubifs_assert(lp->free + lp->dirty >= c->dead_wm);
319                 goto found;
320         }
321
322         /* Did not find a dirty LEB on the dirty heaps, have to scan */
323         dbg_find("scanning LPT for a dirty LEB");
324         lp = scan_for_dirty(c, min_space, pick_free, exclude_index);
325         if (IS_ERR(lp)) {
326                 err = PTR_ERR(lp);
327                 goto out;
328         }
329         ubifs_assert(lp->dirty >= c->dead_wm ||
330                      (pick_free && lp->free + lp->dirty == c->leb_size));
331
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(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
466         c->lscan_lnum = data.lnum;
467         lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
468         if (IS_ERR(lprops))
469                 return lprops;
470         ubifs_assert(lprops->lnum == data.lnum);
471         ubifs_assert(lprops->free >= min_space);
472         ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
473         ubifs_assert(!(lprops->flags & LPROPS_INDEX));
474         return lprops;
475 }
476
477 /**
478  * ubifs_find_free_space - find a data LEB with free space.
479  * @c: the UBIFS file-system description object
480  * @min_space: minimum amount of required free space
481  * @free: contains amount of free space in the LEB 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 *free,
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->min_idx_lebs > c->lst.idx_lebs)
505                 rsvd_idx_lebs = c->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         ubifs_assert(lebs + c->lst.idx_lebs >= c->min_idx_lebs);
511         if (rsvd_idx_lebs < lebs)
512                 /*
513                  * OK to allocate an empty LEB, but we still don't want to go
514                  * looking for one if there aren't any.
515                  */
516                 if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
517                         pick_free = 1;
518                         /*
519                          * Because we release the space lock, we must account
520                          * for this allocation here. After the LEB properties
521                          * flags have been updated, we subtract one. Note, the
522                          * result of this is that lprops also decreases
523                          * @taken_empty_lebs in 'ubifs_change_lp()', so it is
524                          * off by one for a short period of time which may
525                          * introduce a small disturbance to budgeting
526                          * calculations, but this is harmless because at the
527                          * worst case this would make the budgeting subsystem
528                          * be more pessimistic than needed.
529                          *
530                          * Fundamentally, this is about serialization of the
531                          * budgeting and lprops subsystems. We could make the
532                          * @space_lock a mutex and avoid dropping it before
533                          * calling 'ubifs_change_lp()', but mutex is more
534                          * heavy-weight, and we want budgeting to be as fast as
535                          * possible.
536                          */
537                         c->lst.taken_empty_lebs += 1;
538                 }
539         spin_unlock(&c->space_lock);
540
541         lprops = do_find_free_space(c, min_space, pick_free, squeeze);
542         if (IS_ERR(lprops)) {
543                 err = PTR_ERR(lprops);
544                 goto out;
545         }
546
547         lnum = lprops->lnum;
548         flags = lprops->flags | LPROPS_TAKEN;
549
550         lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0);
551         if (IS_ERR(lprops)) {
552                 err = PTR_ERR(lprops);
553                 goto out;
554         }
555
556         if (pick_free) {
557                 spin_lock(&c->space_lock);
558                 c->lst.taken_empty_lebs -= 1;
559                 spin_unlock(&c->space_lock);
560         }
561
562         *free = lprops->free;
563         ubifs_release_lprops(c);
564
565         if (*free == c->leb_size) {
566                 /*
567                  * Ensure that empty LEBs have been unmapped. They may not have
568                  * been, for example, because of an unclean unmount.  Also
569                  * LEBs that were freeable LEBs (free + dirty == leb_size) will
570                  * not have been unmapped.
571                  */
572                 err = ubifs_leb_unmap(c, lnum);
573                 if (err)
574                         return err;
575         }
576
577         dbg_find("found LEB %d, free %d", lnum, *free);
578         ubifs_assert(*free >= min_space);
579         return lnum;
580
581 out:
582         if (pick_free) {
583                 spin_lock(&c->space_lock);
584                 c->lst.taken_empty_lebs -= 1;
585                 spin_unlock(&c->space_lock);
586         }
587         ubifs_release_lprops(c);
588         return err;
589 }
590
591 /**
592  * scan_for_idx_cb - callback used by the scan for a free LEB for the index.
593  * @c: the UBIFS file-system description object
594  * @lprops: LEB properties to scan
595  * @in_tree: whether the LEB properties are in main memory
596  * @data: information passed to and from the caller of the scan
597  *
598  * This function returns a code that indicates whether the scan should continue
599  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
600  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
601  * (%LPT_SCAN_STOP).
602  */
603 static int scan_for_idx_cb(struct ubifs_info *c,
604                            const struct ubifs_lprops *lprops, int in_tree,
605                            struct scan_data *data)
606 {
607         int ret = LPT_SCAN_CONTINUE;
608
609         /* Exclude LEBs that are currently in use */
610         if (lprops->flags & LPROPS_TAKEN)
611                 return LPT_SCAN_CONTINUE;
612         /* Determine whether to add these LEB properties to the tree */
613         if (!in_tree && valuable(c, lprops))
614                 ret |= LPT_SCAN_ADD;
615         /* Exclude index LEBS */
616         if (lprops->flags & LPROPS_INDEX)
617                 return ret;
618         /* Exclude LEBs that cannot be made empty */
619         if (lprops->free + lprops->dirty != c->leb_size)
620                 return ret;
621         /*
622          * We are allocating for the index so it is safe to allocate LEBs with
623          * only free and dirty space, because write buffers are sync'd at commit
624          * start.
625          */
626         data->lnum = lprops->lnum;
627         return LPT_SCAN_ADD | LPT_SCAN_STOP;
628 }
629
630 /**
631  * scan_for_leb_for_idx - scan for a free LEB for the index.
632  * @c: the UBIFS file-system description object
633  */
634 static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
635 {
636         struct ubifs_lprops *lprops;
637         struct scan_data data;
638         int err;
639
640         data.lnum = -1;
641         err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
642                                     (ubifs_lpt_scan_callback)scan_for_idx_cb,
643                                     &data);
644         if (err)
645                 return ERR_PTR(err);
646         ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
647         c->lscan_lnum = data.lnum;
648         lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
649         if (IS_ERR(lprops))
650                 return lprops;
651         ubifs_assert(lprops->lnum == data.lnum);
652         ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
653         ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
654         ubifs_assert(!(lprops->flags & LPROPS_INDEX));
655         return lprops;
656 }
657
658 /**
659  * ubifs_find_free_leb_for_idx - find a free LEB for the index.
660  * @c: the UBIFS file-system description object
661  *
662  * This function looks for a free LEB and returns that LEB number. The returned
663  * LEB is marked as "taken", "index".
664  *
665  * Only empty LEBs are allocated. This is for two reasons. First, the commit
666  * calculates the number of LEBs to allocate based on the assumption that they
667  * will be empty. Secondly, free space at the end of an index LEB is not
668  * guaranteed to be empty because it may have been used by the in-the-gaps
669  * method prior to an unclean unmount.
670  *
671  * If no LEB is found %-ENOSPC is returned. For other failures another negative
672  * error code is returned.
673  */
674 int ubifs_find_free_leb_for_idx(struct ubifs_info *c)
675 {
676         const struct ubifs_lprops *lprops;
677         int lnum = -1, err, flags;
678
679         ubifs_get_lprops(c);
680
681         lprops = ubifs_fast_find_empty(c);
682         if (!lprops) {
683                 lprops = ubifs_fast_find_freeable(c);
684                 if (!lprops) {
685                         ubifs_assert(c->freeable_cnt == 0);
686                         if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
687                                 lprops = scan_for_leb_for_idx(c);
688                                 if (IS_ERR(lprops)) {
689                                         err = PTR_ERR(lprops);
690                                         goto out;
691                                 }
692                         }
693                 }
694         }
695
696         if (!lprops) {
697                 err = -ENOSPC;
698                 goto out;
699         }
700
701         lnum = lprops->lnum;
702
703         dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
704                  lnum, lprops->free, lprops->dirty, lprops->flags);
705
706         flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
707         lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
708         if (IS_ERR(lprops)) {
709                 err = PTR_ERR(lprops);
710                 goto out;
711         }
712
713         ubifs_release_lprops(c);
714
715         /*
716          * Ensure that empty LEBs have been unmapped. They may not have been,
717          * for example, because of an unclean unmount. Also LEBs that were
718          * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
719          */
720         err = ubifs_leb_unmap(c, lnum);
721         if (err) {
722                 ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
723                                     LPROPS_TAKEN | LPROPS_INDEX, 0);
724                 return err;
725         }
726
727         return lnum;
728
729 out:
730         ubifs_release_lprops(c);
731         return err;
732 }
733
734 static int cmp_dirty_idx(const struct ubifs_lprops **a,
735                          const struct ubifs_lprops **b)
736 {
737         const struct ubifs_lprops *lpa = *a;
738         const struct ubifs_lprops *lpb = *b;
739
740         return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
741 }
742
743 static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
744                            int size)
745 {
746         struct ubifs_lprops *t = *a;
747
748         *a = *b;
749         *b = t;
750 }
751
752 /**
753  * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
754  * @c: the UBIFS file-system description object
755  *
756  * This function is called each commit to create an array of LEB numbers of
757  * dirty index LEBs sorted in order of dirty and free space.  This is used by
758  * the in-the-gaps method of TNC commit.
759  */
760 int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
761 {
762         int i;
763
764         ubifs_get_lprops(c);
765         /* Copy the LPROPS_DIRTY_IDX heap */
766         c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
767         memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
768                sizeof(void *) * c->dirty_idx.cnt);
769         /* Sort it so that the dirtiest is now at the end */
770         sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
771              (int (*)(const void *, const void *))cmp_dirty_idx,
772              (void (*)(void *, void *, int))swap_dirty_idx);
773         dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
774         if (c->dirty_idx.cnt)
775                 dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
776                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
777                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
778                          c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
779         /* Replace the lprops pointers with LEB numbers */
780         for (i = 0; i < c->dirty_idx.cnt; i++)
781                 c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
782         ubifs_release_lprops(c);
783         return 0;
784 }
785
786 /**
787  * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
788  * @c: the UBIFS file-system description object
789  * @lprops: LEB properties to scan
790  * @in_tree: whether the LEB properties are in main memory
791  * @data: information passed to and from the caller of the scan
792  *
793  * This function returns a code that indicates whether the scan should continue
794  * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
795  * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
796  * (%LPT_SCAN_STOP).
797  */
798 static int scan_dirty_idx_cb(struct ubifs_info *c,
799                            const struct ubifs_lprops *lprops, int in_tree,
800                            struct scan_data *data)
801 {
802         int ret = LPT_SCAN_CONTINUE;
803
804         /* Exclude LEBs that are currently in use */
805         if (lprops->flags & LPROPS_TAKEN)
806                 return LPT_SCAN_CONTINUE;
807         /* Determine whether to add these LEB properties to the tree */
808         if (!in_tree && valuable(c, lprops))
809                 ret |= LPT_SCAN_ADD;
810         /* Exclude non-index LEBs */
811         if (!(lprops->flags & LPROPS_INDEX))
812                 return ret;
813         /* Exclude LEBs with too little space */
814         if (lprops->free + lprops->dirty < c->min_idx_node_sz)
815                 return ret;
816         /* Finally we found space */
817         data->lnum = lprops->lnum;
818         return LPT_SCAN_ADD | LPT_SCAN_STOP;
819 }
820
821 /**
822  * find_dirty_idx_leb - find a dirty index LEB.
823  * @c: the UBIFS file-system description object
824  *
825  * This function returns LEB number upon success and a negative error code upon
826  * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
827  * found.
828  *
829  * Note that this function scans the entire LPT but it is called very rarely.
830  */
831 static int find_dirty_idx_leb(struct ubifs_info *c)
832 {
833         const struct ubifs_lprops *lprops;
834         struct ubifs_lpt_heap *heap;
835         struct scan_data data;
836         int err, i, ret;
837
838         /* Check all structures in memory first */
839         data.lnum = -1;
840         heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
841         for (i = 0; i < heap->cnt; i++) {
842                 lprops = heap->arr[i];
843                 ret = scan_dirty_idx_cb(c, lprops, 1, &data);
844                 if (ret & LPT_SCAN_STOP)
845                         goto found;
846         }
847         list_for_each_entry(lprops, &c->frdi_idx_list, list) {
848                 ret = scan_dirty_idx_cb(c, lprops, 1, &data);
849                 if (ret & LPT_SCAN_STOP)
850                         goto found;
851         }
852         list_for_each_entry(lprops, &c->uncat_list, list) {
853                 ret = scan_dirty_idx_cb(c, lprops, 1, &data);
854                 if (ret & LPT_SCAN_STOP)
855                         goto found;
856         }
857         if (c->pnodes_have >= c->pnode_cnt)
858                 /* All pnodes are in memory, so skip scan */
859                 return -ENOSPC;
860         err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
861                                     (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
862                                     &data);
863         if (err)
864                 return err;
865 found:
866         ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
867         c->lscan_lnum = data.lnum;
868         lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
869         if (IS_ERR(lprops))
870                 return PTR_ERR(lprops);
871         ubifs_assert(lprops->lnum == data.lnum);
872         ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz);
873         ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
874         ubifs_assert((lprops->flags & LPROPS_INDEX));
875
876         dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
877                  lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
878
879         lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
880                                  lprops->flags | LPROPS_TAKEN, 0);
881         if (IS_ERR(lprops))
882                 return PTR_ERR(lprops);
883
884         return lprops->lnum;
885 }
886
887 /**
888  * get_idx_gc_leb - try to get a LEB number from trivial GC.
889  * @c: the UBIFS file-system description object
890  */
891 static int get_idx_gc_leb(struct ubifs_info *c)
892 {
893         const struct ubifs_lprops *lp;
894         int err, lnum;
895
896         err = ubifs_get_idx_gc_leb(c);
897         if (err < 0)
898                 return err;
899         lnum = err;
900         /*
901          * The LEB was due to be unmapped after the commit but
902          * it is needed now for this commit.
903          */
904         lp = ubifs_lpt_lookup_dirty(c, lnum);
905         if (unlikely(IS_ERR(lp)))
906                 return PTR_ERR(lp);
907         lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
908                              lp->flags | LPROPS_INDEX, -1);
909         if (unlikely(IS_ERR(lp)))
910                 return PTR_ERR(lp);
911         dbg_find("LEB %d, dirty %d and free %d flags %#x",
912                  lp->lnum, lp->dirty, lp->free, lp->flags);
913         return lnum;
914 }
915
916 /**
917  * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
918  * @c: the UBIFS file-system description object
919  */
920 static int find_dirtiest_idx_leb(struct ubifs_info *c)
921 {
922         const struct ubifs_lprops *lp;
923         int lnum;
924
925         while (1) {
926                 if (!c->dirty_idx.cnt)
927                         return -ENOSPC;
928                 /* The lprops pointers were replaced by LEB numbers */
929                 lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
930                 lp = ubifs_lpt_lookup(c, lnum);
931                 if (IS_ERR(lp))
932                         return PTR_ERR(lp);
933                 if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
934                         continue;
935                 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
936                                      lp->flags | LPROPS_TAKEN, 0);
937                 if (IS_ERR(lp))
938                         return PTR_ERR(lp);
939                 break;
940         }
941         dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
942                  lp->free, lp->flags);
943         ubifs_assert(lp->flags | LPROPS_TAKEN);
944         ubifs_assert(lp->flags | LPROPS_INDEX);
945         return lnum;
946 }
947
948 /**
949  * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
950  * @c: the UBIFS file-system description object
951  *
952  * This function attempts to find an untaken index LEB with the most free and
953  * dirty space that can be used without overwriting index nodes that were in the
954  * last index committed.
955  */
956 int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
957 {
958         int err;
959
960         ubifs_get_lprops(c);
961
962         /*
963          * We made an array of the dirtiest index LEB numbers as at the start of
964          * last commit.  Try that array first.
965          */
966         err = find_dirtiest_idx_leb(c);
967
968         /* Next try scanning the entire LPT */
969         if (err == -ENOSPC)
970                 err = find_dirty_idx_leb(c);
971
972         /* Finally take any index LEBs awaiting trivial GC */
973         if (err == -ENOSPC)
974                 err = get_idx_gc_leb(c);
975
976         ubifs_release_lprops(c);
977         return err;
978 }