xref: /openbmc/u-boot/fs/ubifs/lprops.c (revision a89c33db)
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: Adrian Hunter
20  *          Artem Bityutskiy (Битюцкий Артём)
21  */
22 
23 /*
24  * This file implements the functions that access LEB properties and their
25  * categories. LEBs are categorized based on the needs of UBIFS, and the
26  * categories are stored as either heaps or lists to provide a fast way of
27  * finding a LEB in a particular category. For example, UBIFS may need to find
28  * an empty LEB for the journal, or a very dirty LEB for garbage collection.
29  */
30 
31 #include "ubifs.h"
32 
33 /**
34  * get_heap_comp_val - get the LEB properties value for heap comparisons.
35  * @lprops: LEB properties
36  * @cat: LEB category
37  */
38 static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
39 {
40 	switch (cat) {
41 	case LPROPS_FREE:
42 		return lprops->free;
43 	case LPROPS_DIRTY_IDX:
44 		return lprops->free + lprops->dirty;
45 	default:
46 		return lprops->dirty;
47 	}
48 }
49 
50 /**
51  * move_up_lpt_heap - move a new heap entry up as far as possible.
52  * @c: UBIFS file-system description object
53  * @heap: LEB category heap
54  * @lprops: LEB properties to move
55  * @cat: LEB category
56  *
57  * New entries to a heap are added at the bottom and then moved up until the
58  * parent's value is greater.  In the case of LPT's category heaps, the value
59  * is either the amount of free space or the amount of dirty space, depending
60  * on the category.
61  */
62 static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
63 			     struct ubifs_lprops *lprops, int cat)
64 {
65 	int val1, val2, hpos;
66 
67 	hpos = lprops->hpos;
68 	if (!hpos)
69 		return; /* Already top of the heap */
70 	val1 = get_heap_comp_val(lprops, cat);
71 	/* Compare to parent and, if greater, move up the heap */
72 	do {
73 		int ppos = (hpos - 1) / 2;
74 
75 		val2 = get_heap_comp_val(heap->arr[ppos], cat);
76 		if (val2 >= val1)
77 			return;
78 		/* Greater than parent so move up */
79 		heap->arr[ppos]->hpos = hpos;
80 		heap->arr[hpos] = heap->arr[ppos];
81 		heap->arr[ppos] = lprops;
82 		lprops->hpos = ppos;
83 		hpos = ppos;
84 	} while (hpos);
85 }
86 
87 /**
88  * adjust_lpt_heap - move a changed heap entry up or down the heap.
89  * @c: UBIFS file-system description object
90  * @heap: LEB category heap
91  * @lprops: LEB properties to move
92  * @hpos: heap position of @lprops
93  * @cat: LEB category
94  *
95  * Changed entries in a heap are moved up or down until the parent's value is
96  * greater.  In the case of LPT's category heaps, the value is either the amount
97  * of free space or the amount of dirty space, depending on the category.
98  */
99 static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,
100 			    struct ubifs_lprops *lprops, int hpos, int cat)
101 {
102 	int val1, val2, val3, cpos;
103 
104 	val1 = get_heap_comp_val(lprops, cat);
105 	/* Compare to parent and, if greater than parent, move up the heap */
106 	if (hpos) {
107 		int ppos = (hpos - 1) / 2;
108 
109 		val2 = get_heap_comp_val(heap->arr[ppos], cat);
110 		if (val1 > val2) {
111 			/* Greater than parent so move up */
112 			while (1) {
113 				heap->arr[ppos]->hpos = hpos;
114 				heap->arr[hpos] = heap->arr[ppos];
115 				heap->arr[ppos] = lprops;
116 				lprops->hpos = ppos;
117 				hpos = ppos;
118 				if (!hpos)
119 					return;
120 				ppos = (hpos - 1) / 2;
121 				val2 = get_heap_comp_val(heap->arr[ppos], cat);
122 				if (val1 <= val2)
123 					return;
124 				/* Still greater than parent so keep going */
125 			}
126 		}
127 	}
128 
129 	/* Not greater than parent, so compare to children */
130 	while (1) {
131 		/* Compare to left child */
132 		cpos = hpos * 2 + 1;
133 		if (cpos >= heap->cnt)
134 			return;
135 		val2 = get_heap_comp_val(heap->arr[cpos], cat);
136 		if (val1 < val2) {
137 			/* Less than left child, so promote biggest child */
138 			if (cpos + 1 < heap->cnt) {
139 				val3 = get_heap_comp_val(heap->arr[cpos + 1],
140 							 cat);
141 				if (val3 > val2)
142 					cpos += 1; /* Right child is bigger */
143 			}
144 			heap->arr[cpos]->hpos = hpos;
145 			heap->arr[hpos] = heap->arr[cpos];
146 			heap->arr[cpos] = lprops;
147 			lprops->hpos = cpos;
148 			hpos = cpos;
149 			continue;
150 		}
151 		/* Compare to right child */
152 		cpos += 1;
153 		if (cpos >= heap->cnt)
154 			return;
155 		val3 = get_heap_comp_val(heap->arr[cpos], cat);
156 		if (val1 < val3) {
157 			/* Less than right child, so promote right child */
158 			heap->arr[cpos]->hpos = hpos;
159 			heap->arr[hpos] = heap->arr[cpos];
160 			heap->arr[cpos] = lprops;
161 			lprops->hpos = cpos;
162 			hpos = cpos;
163 			continue;
164 		}
165 		return;
166 	}
167 }
168 
169 /**
170  * add_to_lpt_heap - add LEB properties to a LEB category heap.
171  * @c: UBIFS file-system description object
172  * @lprops: LEB properties to add
173  * @cat: LEB category
174  *
175  * This function returns %1 if @lprops is added to the heap for LEB category
176  * @cat, otherwise %0 is returned because the heap is full.
177  */
178 static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,
179 			   int cat)
180 {
181 	struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
182 
183 	if (heap->cnt >= heap->max_cnt) {
184 		const int b = LPT_HEAP_SZ / 2 - 1;
185 		int cpos, val1, val2;
186 
187 		/* Compare to some other LEB on the bottom of heap */
188 		/* Pick a position kind of randomly */
189 		cpos = (((size_t)lprops >> 4) & b) + b;
190 		ubifs_assert(cpos >= b);
191 		ubifs_assert(cpos < LPT_HEAP_SZ);
192 		ubifs_assert(cpos < heap->cnt);
193 
194 		val1 = get_heap_comp_val(lprops, cat);
195 		val2 = get_heap_comp_val(heap->arr[cpos], cat);
196 		if (val1 > val2) {
197 			struct ubifs_lprops *lp;
198 
199 			lp = heap->arr[cpos];
200 			lp->flags &= ~LPROPS_CAT_MASK;
201 			lp->flags |= LPROPS_UNCAT;
202 			list_add(&lp->list, &c->uncat_list);
203 			lprops->hpos = cpos;
204 			heap->arr[cpos] = lprops;
205 			move_up_lpt_heap(c, heap, lprops, cat);
206 			dbg_check_heap(c, heap, cat, lprops->hpos);
207 			return 1; /* Added to heap */
208 		}
209 		dbg_check_heap(c, heap, cat, -1);
210 		return 0; /* Not added to heap */
211 	} else {
212 		lprops->hpos = heap->cnt++;
213 		heap->arr[lprops->hpos] = lprops;
214 		move_up_lpt_heap(c, heap, lprops, cat);
215 		dbg_check_heap(c, heap, cat, lprops->hpos);
216 		return 1; /* Added to heap */
217 	}
218 }
219 
220 /**
221  * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
222  * @c: UBIFS file-system description object
223  * @lprops: LEB properties to remove
224  * @cat: LEB category
225  */
226 static void remove_from_lpt_heap(struct ubifs_info *c,
227 				 struct ubifs_lprops *lprops, int cat)
228 {
229 	struct ubifs_lpt_heap *heap;
230 	int hpos = lprops->hpos;
231 
232 	heap = &c->lpt_heap[cat - 1];
233 	ubifs_assert(hpos >= 0 && hpos < heap->cnt);
234 	ubifs_assert(heap->arr[hpos] == lprops);
235 	heap->cnt -= 1;
236 	if (hpos < heap->cnt) {
237 		heap->arr[hpos] = heap->arr[heap->cnt];
238 		heap->arr[hpos]->hpos = hpos;
239 		adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);
240 	}
241 	dbg_check_heap(c, heap, cat, -1);
242 }
243 
244 /**
245  * lpt_heap_replace - replace lprops in a category heap.
246  * @c: UBIFS file-system description object
247  * @old_lprops: LEB properties to replace
248  * @new_lprops: LEB properties with which to replace
249  * @cat: LEB category
250  *
251  * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
252  * and the lprops that the pnode contains.  When that happens, references in
253  * the category heaps to those lprops must be updated to point to the new
254  * lprops.  This function does that.
255  */
256 static void lpt_heap_replace(struct ubifs_info *c,
257 			     struct ubifs_lprops *old_lprops,
258 			     struct ubifs_lprops *new_lprops, int cat)
259 {
260 	struct ubifs_lpt_heap *heap;
261 	int hpos = new_lprops->hpos;
262 
263 	heap = &c->lpt_heap[cat - 1];
264 	heap->arr[hpos] = new_lprops;
265 }
266 
267 /**
268  * ubifs_add_to_cat - add LEB properties to a category list or heap.
269  * @c: UBIFS file-system description object
270  * @lprops: LEB properties to add
271  * @cat: LEB category to which to add
272  *
273  * LEB properties are categorized to enable fast find operations.
274  */
275 void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,
276 		      int cat)
277 {
278 	switch (cat) {
279 	case LPROPS_DIRTY:
280 	case LPROPS_DIRTY_IDX:
281 	case LPROPS_FREE:
282 		if (add_to_lpt_heap(c, lprops, cat))
283 			break;
284 		/* No more room on heap so make it uncategorized */
285 		cat = LPROPS_UNCAT;
286 		/* Fall through */
287 	case LPROPS_UNCAT:
288 		list_add(&lprops->list, &c->uncat_list);
289 		break;
290 	case LPROPS_EMPTY:
291 		list_add(&lprops->list, &c->empty_list);
292 		break;
293 	case LPROPS_FREEABLE:
294 		list_add(&lprops->list, &c->freeable_list);
295 		c->freeable_cnt += 1;
296 		break;
297 	case LPROPS_FRDI_IDX:
298 		list_add(&lprops->list, &c->frdi_idx_list);
299 		break;
300 	default:
301 		ubifs_assert(0);
302 	}
303 	lprops->flags &= ~LPROPS_CAT_MASK;
304 	lprops->flags |= cat;
305 }
306 
307 /**
308  * ubifs_remove_from_cat - remove LEB properties from a category list or heap.
309  * @c: UBIFS file-system description object
310  * @lprops: LEB properties to remove
311  * @cat: LEB category from which to remove
312  *
313  * LEB properties are categorized to enable fast find operations.
314  */
315 static void ubifs_remove_from_cat(struct ubifs_info *c,
316 				  struct ubifs_lprops *lprops, int cat)
317 {
318 	switch (cat) {
319 	case LPROPS_DIRTY:
320 	case LPROPS_DIRTY_IDX:
321 	case LPROPS_FREE:
322 		remove_from_lpt_heap(c, lprops, cat);
323 		break;
324 	case LPROPS_FREEABLE:
325 		c->freeable_cnt -= 1;
326 		ubifs_assert(c->freeable_cnt >= 0);
327 		/* Fall through */
328 	case LPROPS_UNCAT:
329 	case LPROPS_EMPTY:
330 	case LPROPS_FRDI_IDX:
331 		ubifs_assert(!list_empty(&lprops->list));
332 		list_del(&lprops->list);
333 		break;
334 	default:
335 		ubifs_assert(0);
336 	}
337 }
338 
339 /**
340  * ubifs_replace_cat - replace lprops in a category list or heap.
341  * @c: UBIFS file-system description object
342  * @old_lprops: LEB properties to replace
343  * @new_lprops: LEB properties with which to replace
344  *
345  * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
346  * and the lprops that the pnode contains. When that happens, references in
347  * category lists and heaps must be replaced. This function does that.
348  */
349 void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,
350 		       struct ubifs_lprops *new_lprops)
351 {
352 	int cat;
353 
354 	cat = new_lprops->flags & LPROPS_CAT_MASK;
355 	switch (cat) {
356 	case LPROPS_DIRTY:
357 	case LPROPS_DIRTY_IDX:
358 	case LPROPS_FREE:
359 		lpt_heap_replace(c, old_lprops, new_lprops, cat);
360 		break;
361 	case LPROPS_UNCAT:
362 	case LPROPS_EMPTY:
363 	case LPROPS_FREEABLE:
364 	case LPROPS_FRDI_IDX:
365 		list_replace(&old_lprops->list, &new_lprops->list);
366 		break;
367 	default:
368 		ubifs_assert(0);
369 	}
370 }
371 
372 /**
373  * ubifs_ensure_cat - ensure LEB properties are categorized.
374  * @c: UBIFS file-system description object
375  * @lprops: LEB properties
376  *
377  * A LEB may have fallen off of the bottom of a heap, and ended up as
378  * uncategorized even though it has enough space for us now. If that is the case
379  * this function will put the LEB back onto a heap.
380  */
381 void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)
382 {
383 	int cat = lprops->flags & LPROPS_CAT_MASK;
384 
385 	if (cat != LPROPS_UNCAT)
386 		return;
387 	cat = ubifs_categorize_lprops(c, lprops);
388 	if (cat == LPROPS_UNCAT)
389 		return;
390 	ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);
391 	ubifs_add_to_cat(c, lprops, cat);
392 }
393 
394 /**
395  * ubifs_categorize_lprops - categorize LEB properties.
396  * @c: UBIFS file-system description object
397  * @lprops: LEB properties to categorize
398  *
399  * LEB properties are categorized to enable fast find operations. This function
400  * returns the LEB category to which the LEB properties belong. Note however
401  * that if the LEB category is stored as a heap and the heap is full, the
402  * LEB properties may have their category changed to %LPROPS_UNCAT.
403  */
404 int ubifs_categorize_lprops(const struct ubifs_info *c,
405 			    const struct ubifs_lprops *lprops)
406 {
407 	if (lprops->flags & LPROPS_TAKEN)
408 		return LPROPS_UNCAT;
409 
410 	if (lprops->free == c->leb_size) {
411 		ubifs_assert(!(lprops->flags & LPROPS_INDEX));
412 		return LPROPS_EMPTY;
413 	}
414 
415 	if (lprops->free + lprops->dirty == c->leb_size) {
416 		if (lprops->flags & LPROPS_INDEX)
417 			return LPROPS_FRDI_IDX;
418 		else
419 			return LPROPS_FREEABLE;
420 	}
421 
422 	if (lprops->flags & LPROPS_INDEX) {
423 		if (lprops->dirty + lprops->free >= c->min_idx_node_sz)
424 			return LPROPS_DIRTY_IDX;
425 	} else {
426 		if (lprops->dirty >= c->dead_wm &&
427 		    lprops->dirty > lprops->free)
428 			return LPROPS_DIRTY;
429 		if (lprops->free > 0)
430 			return LPROPS_FREE;
431 	}
432 
433 	return LPROPS_UNCAT;
434 }
435 
436 /**
437  * change_category - change LEB properties category.
438  * @c: UBIFS file-system description object
439  * @lprops: LEB properties to recategorize
440  *
441  * LEB properties are categorized to enable fast find operations. When the LEB
442  * properties change they must be recategorized.
443  */
444 static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)
445 {
446 	int old_cat = lprops->flags & LPROPS_CAT_MASK;
447 	int new_cat = ubifs_categorize_lprops(c, lprops);
448 
449 	if (old_cat == new_cat) {
450 		struct ubifs_lpt_heap *heap = &c->lpt_heap[new_cat - 1];
451 
452 		/* lprops on a heap now must be moved up or down */
453 		if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT)
454 			return; /* Not on a heap */
455 		heap = &c->lpt_heap[new_cat - 1];
456 		adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);
457 	} else {
458 		ubifs_remove_from_cat(c, lprops, old_cat);
459 		ubifs_add_to_cat(c, lprops, new_cat);
460 	}
461 }
462 
463 /**
464  * calc_dark - calculate LEB dark space size.
465  * @c: the UBIFS file-system description object
466  * @spc: amount of free and dirty space in the LEB
467  *
468  * This function calculates amount of dark space in an LEB which has @spc bytes
469  * of free and dirty space. Returns the calculations result.
470  *
471  * Dark space is the space which is not always usable - it depends on which
472  * nodes are written in which order. E.g., if an LEB has only 512 free bytes,
473  * it is dark space, because it cannot fit a large data node. So UBIFS cannot
474  * count on this LEB and treat these 512 bytes as usable because it is not true
475  * if, for example, only big chunks of uncompressible data will be written to
476  * the FS.
477  */
478 static int calc_dark(struct ubifs_info *c, int spc)
479 {
480 	ubifs_assert(!(spc & 7));
481 
482 	if (spc < c->dark_wm)
483 		return spc;
484 
485 	/*
486 	 * If we have slightly more space then the dark space watermark, we can
487 	 * anyway safely assume it we'll be able to write a node of the
488 	 * smallest size there.
489 	 */
490 	if (spc - c->dark_wm < MIN_WRITE_SZ)
491 		return spc - MIN_WRITE_SZ;
492 
493 	return c->dark_wm;
494 }
495 
496 /**
497  * is_lprops_dirty - determine if LEB properties are dirty.
498  * @c: the UBIFS file-system description object
499  * @lprops: LEB properties to test
500  */
501 static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)
502 {
503 	struct ubifs_pnode *pnode;
504 	int pos;
505 
506 	pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);
507 	pnode = (struct ubifs_pnode *)container_of(lprops - pos,
508 						   struct ubifs_pnode,
509 						   lprops[0]);
510 	return !test_bit(COW_ZNODE, &pnode->flags) &&
511 	       test_bit(DIRTY_CNODE, &pnode->flags);
512 }
513 
514 /**
515  * ubifs_change_lp - change LEB properties.
516  * @c: the UBIFS file-system description object
517  * @lp: LEB properties to change
518  * @free: new free space amount
519  * @dirty: new dirty space amount
520  * @flags: new flags
521  * @idx_gc_cnt: change to the count of idx_gc list
522  *
523  * This function changes LEB properties (@free, @dirty or @flag). However, the
524  * property which has the %LPROPS_NC value is not changed. Returns a pointer to
525  * the updated LEB properties on success and a negative error code on failure.
526  *
527  * Note, the LEB properties may have had to be copied (due to COW) and
528  * consequently the pointer returned may not be the same as the pointer
529  * passed.
530  */
531 const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,
532 					   const struct ubifs_lprops *lp,
533 					   int free, int dirty, int flags,
534 					   int idx_gc_cnt)
535 {
536 	/*
537 	 * This is the only function that is allowed to change lprops, so we
538 	 * discard the const qualifier.
539 	 */
540 	struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp;
541 
542 	dbg_lp("LEB %d, free %d, dirty %d, flags %d",
543 	       lprops->lnum, free, dirty, flags);
544 
545 	ubifs_assert(mutex_is_locked(&c->lp_mutex));
546 	ubifs_assert(c->lst.empty_lebs >= 0 &&
547 		     c->lst.empty_lebs <= c->main_lebs);
548 	ubifs_assert(c->freeable_cnt >= 0);
549 	ubifs_assert(c->freeable_cnt <= c->main_lebs);
550 	ubifs_assert(c->lst.taken_empty_lebs >= 0);
551 	ubifs_assert(c->lst.taken_empty_lebs <= c->lst.empty_lebs);
552 	ubifs_assert(!(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));
553 	ubifs_assert(!(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));
554 	ubifs_assert(!(c->lst.total_used & 7));
555 	ubifs_assert(free == LPROPS_NC || free >= 0);
556 	ubifs_assert(dirty == LPROPS_NC || dirty >= 0);
557 
558 	if (!is_lprops_dirty(c, lprops)) {
559 		lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);
560 		if (IS_ERR(lprops))
561 			return lprops;
562 	} else
563 		ubifs_assert(lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));
564 
565 	ubifs_assert(!(lprops->free & 7) && !(lprops->dirty & 7));
566 
567 	spin_lock(&c->space_lock);
568 	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
569 		c->lst.taken_empty_lebs -= 1;
570 
571 	if (!(lprops->flags & LPROPS_INDEX)) {
572 		int old_spc;
573 
574 		old_spc = lprops->free + lprops->dirty;
575 		if (old_spc < c->dead_wm)
576 			c->lst.total_dead -= old_spc;
577 		else
578 			c->lst.total_dark -= calc_dark(c, old_spc);
579 
580 		c->lst.total_used -= c->leb_size - old_spc;
581 	}
582 
583 	if (free != LPROPS_NC) {
584 		free = ALIGN(free, 8);
585 		c->lst.total_free += free - lprops->free;
586 
587 		/* Increase or decrease empty LEBs counter if needed */
588 		if (free == c->leb_size) {
589 			if (lprops->free != c->leb_size)
590 				c->lst.empty_lebs += 1;
591 		} else if (lprops->free == c->leb_size)
592 			c->lst.empty_lebs -= 1;
593 		lprops->free = free;
594 	}
595 
596 	if (dirty != LPROPS_NC) {
597 		dirty = ALIGN(dirty, 8);
598 		c->lst.total_dirty += dirty - lprops->dirty;
599 		lprops->dirty = dirty;
600 	}
601 
602 	if (flags != LPROPS_NC) {
603 		/* Take care about indexing LEBs counter if needed */
604 		if ((lprops->flags & LPROPS_INDEX)) {
605 			if (!(flags & LPROPS_INDEX))
606 				c->lst.idx_lebs -= 1;
607 		} else if (flags & LPROPS_INDEX)
608 			c->lst.idx_lebs += 1;
609 		lprops->flags = flags;
610 	}
611 
612 	if (!(lprops->flags & LPROPS_INDEX)) {
613 		int new_spc;
614 
615 		new_spc = lprops->free + lprops->dirty;
616 		if (new_spc < c->dead_wm)
617 			c->lst.total_dead += new_spc;
618 		else
619 			c->lst.total_dark += calc_dark(c, new_spc);
620 
621 		c->lst.total_used += c->leb_size - new_spc;
622 	}
623 
624 	if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
625 		c->lst.taken_empty_lebs += 1;
626 
627 	change_category(c, lprops);
628 	c->idx_gc_cnt += idx_gc_cnt;
629 	spin_unlock(&c->space_lock);
630 	return lprops;
631 }
632 
633 /**
634  * ubifs_get_lp_stats - get lprops statistics.
635  * @c: UBIFS file-system description object
636  * @st: return statistics
637  */
638 void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst)
639 {
640 	spin_lock(&c->space_lock);
641 	memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats));
642 	spin_unlock(&c->space_lock);
643 }
644 
645 /**
646  * ubifs_change_one_lp - change LEB properties.
647  * @c: the UBIFS file-system description object
648  * @lnum: LEB to change properties for
649  * @free: amount of free space
650  * @dirty: amount of dirty space
651  * @flags_set: flags to set
652  * @flags_clean: flags to clean
653  * @idx_gc_cnt: change to the count of idx_gc list
654  *
655  * This function changes properties of LEB @lnum. It is a helper wrapper over
656  * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the
657  * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and
658  * a negative error code in case of failure.
659  */
660 int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
661 			int flags_set, int flags_clean, int idx_gc_cnt)
662 {
663 	int err = 0, flags;
664 	const struct ubifs_lprops *lp;
665 
666 	ubifs_get_lprops(c);
667 
668 	lp = ubifs_lpt_lookup_dirty(c, lnum);
669 	if (IS_ERR(lp)) {
670 		err = PTR_ERR(lp);
671 		goto out;
672 	}
673 
674 	flags = (lp->flags | flags_set) & ~flags_clean;
675 	lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);
676 	if (IS_ERR(lp))
677 		err = PTR_ERR(lp);
678 
679 out:
680 	ubifs_release_lprops(c);
681 	return err;
682 }
683 
684 /**
685  * ubifs_update_one_lp - update LEB properties.
686  * @c: the UBIFS file-system description object
687  * @lnum: LEB to change properties for
688  * @free: amount of free space
689  * @dirty: amount of dirty space to add
690  * @flags_set: flags to set
691  * @flags_clean: flags to clean
692  *
693  * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
694  * current dirty space, not substitutes it.
695  */
696 int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
697 			int flags_set, int flags_clean)
698 {
699 	int err = 0, flags;
700 	const struct ubifs_lprops *lp;
701 
702 	ubifs_get_lprops(c);
703 
704 	lp = ubifs_lpt_lookup_dirty(c, lnum);
705 	if (IS_ERR(lp)) {
706 		err = PTR_ERR(lp);
707 		goto out;
708 	}
709 
710 	flags = (lp->flags | flags_set) & ~flags_clean;
711 	lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);
712 	if (IS_ERR(lp))
713 		err = PTR_ERR(lp);
714 
715 out:
716 	ubifs_release_lprops(c);
717 	return err;
718 }
719 
720 /**
721  * ubifs_read_one_lp - read LEB properties.
722  * @c: the UBIFS file-system description object
723  * @lnum: LEB to read properties for
724  * @lp: where to store read properties
725  *
726  * This helper function reads properties of a LEB @lnum and stores them in @lp.
727  * Returns zero in case of success and a negative error code in case of
728  * failure.
729  */
730 int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)
731 {
732 	int err = 0;
733 	const struct ubifs_lprops *lpp;
734 
735 	ubifs_get_lprops(c);
736 
737 	lpp = ubifs_lpt_lookup(c, lnum);
738 	if (IS_ERR(lpp)) {
739 		err = PTR_ERR(lpp);
740 		goto out;
741 	}
742 
743 	memcpy(lp, lpp, sizeof(struct ubifs_lprops));
744 
745 out:
746 	ubifs_release_lprops(c);
747 	return err;
748 }
749 
750 /**
751  * ubifs_fast_find_free - try to find a LEB with free space quickly.
752  * @c: the UBIFS file-system description object
753  *
754  * This function returns LEB properties for a LEB with free space or %NULL if
755  * the function is unable to find a LEB quickly.
756  */
757 const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)
758 {
759 	struct ubifs_lprops *lprops;
760 	struct ubifs_lpt_heap *heap;
761 
762 	ubifs_assert(mutex_is_locked(&c->lp_mutex));
763 
764 	heap = &c->lpt_heap[LPROPS_FREE - 1];
765 	if (heap->cnt == 0)
766 		return NULL;
767 
768 	lprops = heap->arr[0];
769 	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
770 	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
771 	return lprops;
772 }
773 
774 /**
775  * ubifs_fast_find_empty - try to find an empty LEB quickly.
776  * @c: the UBIFS file-system description object
777  *
778  * This function returns LEB properties for an empty LEB or %NULL if the
779  * function is unable to find an empty LEB quickly.
780  */
781 const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)
782 {
783 	struct ubifs_lprops *lprops;
784 
785 	ubifs_assert(mutex_is_locked(&c->lp_mutex));
786 
787 	if (list_empty(&c->empty_list))
788 		return NULL;
789 
790 	lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);
791 	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
792 	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
793 	ubifs_assert(lprops->free == c->leb_size);
794 	return lprops;
795 }
796 
797 /**
798  * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
799  * @c: the UBIFS file-system description object
800  *
801  * This function returns LEB properties for a freeable LEB or %NULL if the
802  * function is unable to find a freeable LEB quickly.
803  */
804 const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)
805 {
806 	struct ubifs_lprops *lprops;
807 
808 	ubifs_assert(mutex_is_locked(&c->lp_mutex));
809 
810 	if (list_empty(&c->freeable_list))
811 		return NULL;
812 
813 	lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);
814 	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
815 	ubifs_assert(!(lprops->flags & LPROPS_INDEX));
816 	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
817 	ubifs_assert(c->freeable_cnt > 0);
818 	return lprops;
819 }
820 
821 /**
822  * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
823  * @c: the UBIFS file-system description object
824  *
825  * This function returns LEB properties for a freeable index LEB or %NULL if the
826  * function is unable to find a freeable index LEB quickly.
827  */
828 const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)
829 {
830 	struct ubifs_lprops *lprops;
831 
832 	ubifs_assert(mutex_is_locked(&c->lp_mutex));
833 
834 	if (list_empty(&c->frdi_idx_list))
835 		return NULL;
836 
837 	lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);
838 	ubifs_assert(!(lprops->flags & LPROPS_TAKEN));
839 	ubifs_assert((lprops->flags & LPROPS_INDEX));
840 	ubifs_assert(lprops->free + lprops->dirty == c->leb_size);
841 	return lprops;
842 }
843