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 */
 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, 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 */
233int 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(lp->free + lp->dirty >= c->dead_wm);
319		goto found;
320	}
321
322	/* Did not find a dirty LEB on the dirty heaps, have to scan */
323	dbg_find("scanning LPT for a dirty LEB");
324	lp = scan_for_dirty(c, min_space, pick_free, exclude_index);
325	if (IS_ERR(lp)) {
326		err = PTR_ERR(lp);
327		goto out;
328	}
329	ubifs_assert(lp->dirty >= c->dead_wm ||
330		     (pick_free && lp->free + lp->dirty == c->leb_size));
331
332found:
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
345out:
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 */
362static 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 */
406static
407const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c,
408					      int min_space, int pick_free,
409					      int squeeze)
410{
411	const struct ubifs_lprops *lprops;
412	struct ubifs_lpt_heap *heap;
413	struct scan_data data;
414	int err, i;
415
416	if (squeeze) {
417		lprops = ubifs_fast_find_free(c);
418		if (lprops && lprops->free >= min_space)
419			return lprops;
420	}
421	if (pick_free) {
422		lprops = ubifs_fast_find_empty(c);
423		if (lprops)
424			return lprops;
425	}
426	if (!squeeze) {
427		lprops = ubifs_fast_find_free(c);
428		if (lprops && lprops->free >= min_space)
429			return lprops;
430	}
431	/* There may be an LEB with enough free space on the dirty heap */
432	heap = &c->lpt_heap[LPROPS_DIRTY - 1];
433	for (i = 0; i < heap->cnt; i++) {
434		lprops = heap->arr[i];
435		if (lprops->free >= min_space)
436			return lprops;
437	}
438	/*
439	 * A LEB may have fallen off of the bottom of the free heap, and ended
440	 * up as uncategorized even though it has enough free space for us now,
441	 * so check the uncategorized list. N.B. neither empty nor freeable LEBs
442	 * can end up as uncategorized because they are kept on lists not
443	 * finite-sized heaps.
444	 */
445	list_for_each_entry(lprops, &c->uncat_list, list) {
446		if (lprops->flags & LPROPS_TAKEN)
447			continue;
448		if (lprops->flags & LPROPS_INDEX)
449			continue;
450		if (lprops->free >= min_space)
451			return lprops;
452	}
453	/* We have looked everywhere in main memory, now scan the flash */
454	if (c->pnodes_have >= c->pnode_cnt)
455		/* All pnodes are in memory, so skip scan */
456		return ERR_PTR(-ENOSPC);
457	data.min_space = min_space;
458	data.pick_free = pick_free;
459	data.lnum = -1;
460	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
461				    (ubifs_lpt_scan_callback)scan_for_free_cb,
462				    &data);
463	if (err)
464		return ERR_PTR(err);
465	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
466	c->lscan_lnum = data.lnum;
467	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
468	if (IS_ERR(lprops))
469		return lprops;
470	ubifs_assert(lprops->lnum == data.lnum);
471	ubifs_assert(lprops->free >= min_space);
472	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
473	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
474	return lprops;
475}
476
477/**
478 * ubifs_find_free_space - find a data LEB with free space.
479 * @c: the UBIFS file-system description object
480 * @min_space: minimum amount of required free space
481 * @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 */
493int 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(*offs <= c->leb_size - min_space);
578	return lnum;
579
580out:
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 */
602static 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 */
633static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c)
634{
635	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(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(lprops->lnum == data.lnum);
651	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
652	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
653	ubifs_assert(!(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 */
673int 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			ubifs_assert(c->freeable_cnt == 0);
685			if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) {
 
 
 
 
 
 
 
 
686				lprops = scan_for_leb_for_idx(c);
687				if (IS_ERR(lprops)) {
688					err = PTR_ERR(lprops);
689					goto out;
690				}
691			}
692		}
693	}
694
695	if (!lprops) {
696		err = -ENOSPC;
697		goto out;
698	}
699
700	lnum = lprops->lnum;
701
702	dbg_find("found LEB %d, free %d, dirty %d, flags %#x",
703		 lnum, lprops->free, lprops->dirty, lprops->flags);
704
705	flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX;
706	lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0);
707	if (IS_ERR(lprops)) {
708		err = PTR_ERR(lprops);
709		goto out;
710	}
711
712	ubifs_release_lprops(c);
713
714	/*
715	 * Ensure that empty LEBs have been unmapped. They may not have been,
716	 * for example, because of an unclean unmount. Also LEBs that were
717	 * freeable LEBs (free + dirty == leb_size) will not have been unmapped.
718	 */
719	err = ubifs_leb_unmap(c, lnum);
720	if (err) {
721		ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0,
722				    LPROPS_TAKEN | LPROPS_INDEX, 0);
723		return err;
724	}
725
726	return lnum;
727
728out:
729	ubifs_release_lprops(c);
730	return err;
731}
732
733static int cmp_dirty_idx(const struct ubifs_lprops **a,
734			 const struct ubifs_lprops **b)
735{
736	const struct ubifs_lprops *lpa = *a;
737	const struct ubifs_lprops *lpb = *b;
738
739	return lpa->dirty + lpa->free - lpb->dirty - lpb->free;
740}
741
742static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b,
743			   int size)
744{
745	struct ubifs_lprops *t = *a;
746
747	*a = *b;
748	*b = t;
749}
750
751/**
752 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos.
753 * @c: the UBIFS file-system description object
754 *
755 * This function is called each commit to create an array of LEB numbers of
756 * dirty index LEBs sorted in order of dirty and free space.  This is used by
757 * the in-the-gaps method of TNC commit.
758 */
759int ubifs_save_dirty_idx_lnums(struct ubifs_info *c)
760{
761	int i;
762
763	ubifs_get_lprops(c);
764	/* Copy the LPROPS_DIRTY_IDX heap */
765	c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt;
766	memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr,
767	       sizeof(void *) * c->dirty_idx.cnt);
768	/* Sort it so that the dirtiest is now at the end */
769	sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *),
770	     (int (*)(const void *, const void *))cmp_dirty_idx,
771	     (void (*)(void *, void *, int))swap_dirty_idx);
772	dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt);
773	if (c->dirty_idx.cnt)
774		dbg_find("dirtiest index LEB is %d with dirty %d and free %d",
775			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum,
776			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty,
777			 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free);
778	/* Replace the lprops pointers with LEB numbers */
779	for (i = 0; i < c->dirty_idx.cnt; i++)
780		c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum;
781	ubifs_release_lprops(c);
782	return 0;
783}
784
785/**
786 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB.
787 * @c: the UBIFS file-system description object
788 * @lprops: LEB properties to scan
789 * @in_tree: whether the LEB properties are in main memory
790 * @data: information passed to and from the caller of the scan
791 *
792 * This function returns a code that indicates whether the scan should continue
793 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
794 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
795 * (%LPT_SCAN_STOP).
796 */
797static int scan_dirty_idx_cb(struct ubifs_info *c,
798			   const struct ubifs_lprops *lprops, int in_tree,
799			   struct scan_data *data)
800{
801	int ret = LPT_SCAN_CONTINUE;
802
803	/* Exclude LEBs that are currently in use */
804	if (lprops->flags & LPROPS_TAKEN)
805		return LPT_SCAN_CONTINUE;
806	/* Determine whether to add these LEB properties to the tree */
807	if (!in_tree && valuable(c, lprops))
808		ret |= LPT_SCAN_ADD;
809	/* Exclude non-index LEBs */
810	if (!(lprops->flags & LPROPS_INDEX))
811		return ret;
812	/* Exclude LEBs with too little space */
813	if (lprops->free + lprops->dirty < c->min_idx_node_sz)
814		return ret;
815	/* Finally we found space */
816	data->lnum = lprops->lnum;
817	return LPT_SCAN_ADD | LPT_SCAN_STOP;
818}
819
820/**
821 * find_dirty_idx_leb - find a dirty index LEB.
822 * @c: the UBIFS file-system description object
823 *
824 * This function returns LEB number upon success and a negative error code upon
825 * failure.  In particular, -ENOSPC is returned if a dirty index LEB is not
826 * found.
827 *
828 * Note that this function scans the entire LPT but it is called very rarely.
829 */
830static int find_dirty_idx_leb(struct ubifs_info *c)
831{
832	const struct ubifs_lprops *lprops;
833	struct ubifs_lpt_heap *heap;
834	struct scan_data data;
835	int err, i, ret;
836
837	/* Check all structures in memory first */
838	data.lnum = -1;
839	heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1];
840	for (i = 0; i < heap->cnt; i++) {
841		lprops = heap->arr[i];
842		ret = scan_dirty_idx_cb(c, lprops, 1, &data);
843		if (ret & LPT_SCAN_STOP)
844			goto found;
845	}
846	list_for_each_entry(lprops, &c->frdi_idx_list, list) {
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->uncat_list, list) {
852		ret = scan_dirty_idx_cb(c, lprops, 1, &data);
853		if (ret & LPT_SCAN_STOP)
854			goto found;
855	}
856	if (c->pnodes_have >= c->pnode_cnt)
857		/* All pnodes are in memory, so skip scan */
858		return -ENOSPC;
859	err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum,
860				    (ubifs_lpt_scan_callback)scan_dirty_idx_cb,
861				    &data);
862	if (err)
863		return err;
864found:
865	ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt);
866	c->lscan_lnum = data.lnum;
867	lprops = ubifs_lpt_lookup_dirty(c, data.lnum);
868	if (IS_ERR(lprops))
869		return PTR_ERR(lprops);
870	ubifs_assert(lprops->lnum == data.lnum);
871	ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz);
872	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
873	ubifs_assert((lprops->flags & LPROPS_INDEX));
874
875	dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x",
876		 lprops->lnum, lprops->free, lprops->dirty, lprops->flags);
877
878	lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC,
879				 lprops->flags | LPROPS_TAKEN, 0);
880	if (IS_ERR(lprops))
881		return PTR_ERR(lprops);
882
883	return lprops->lnum;
884}
885
886/**
887 * get_idx_gc_leb - try to get a LEB number from trivial GC.
888 * @c: the UBIFS file-system description object
889 */
890static int get_idx_gc_leb(struct ubifs_info *c)
891{
892	const struct ubifs_lprops *lp;
893	int err, lnum;
894
895	err = ubifs_get_idx_gc_leb(c);
896	if (err < 0)
897		return err;
898	lnum = err;
899	/*
900	 * The LEB was due to be unmapped after the commit but
901	 * it is needed now for this commit.
902	 */
903	lp = ubifs_lpt_lookup_dirty(c, lnum);
904	if (IS_ERR(lp))
905		return PTR_ERR(lp);
906	lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
907			     lp->flags | LPROPS_INDEX, -1);
908	if (IS_ERR(lp))
909		return PTR_ERR(lp);
910	dbg_find("LEB %d, dirty %d and free %d flags %#x",
911		 lp->lnum, lp->dirty, lp->free, lp->flags);
912	return lnum;
913}
914
915/**
916 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array.
917 * @c: the UBIFS file-system description object
918 */
919static int find_dirtiest_idx_leb(struct ubifs_info *c)
920{
921	const struct ubifs_lprops *lp;
922	int lnum;
923
924	while (1) {
925		if (!c->dirty_idx.cnt)
926			return -ENOSPC;
927		/* The lprops pointers were replaced by LEB numbers */
928		lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt];
929		lp = ubifs_lpt_lookup(c, lnum);
930		if (IS_ERR(lp))
931			return PTR_ERR(lp);
932		if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX))
933			continue;
934		lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC,
935				     lp->flags | LPROPS_TAKEN, 0);
936		if (IS_ERR(lp))
937			return PTR_ERR(lp);
938		break;
939	}
940	dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty,
941		 lp->free, lp->flags);
942	ubifs_assert(lp->flags | LPROPS_TAKEN);
943	ubifs_assert(lp->flags | LPROPS_INDEX);
944	return lnum;
945}
946
947/**
948 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit.
949 * @c: the UBIFS file-system description object
950 *
951 * This function attempts to find an untaken index LEB with the most free and
952 * dirty space that can be used without overwriting index nodes that were in the
953 * last index committed.
954 */
955int ubifs_find_dirty_idx_leb(struct ubifs_info *c)
956{
957	int err;
958
959	ubifs_get_lprops(c);
960
961	/*
962	 * We made an array of the dirtiest index LEB numbers as at the start of
963	 * last commit.  Try that array first.
964	 */
965	err = find_dirtiest_idx_leb(c);
966
967	/* Next try scanning the entire LPT */
968	if (err == -ENOSPC)
969		err = find_dirty_idx_leb(c);
970
971	/* Finally take any index LEBs awaiting trivial GC */
972	if (err == -ENOSPC)
973		err = get_idx_gc_leb(c);
974
975	ubifs_release_lprops(c);
976	return err;
977}