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