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