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