2 * This file is part of UBIFS.
4 * Copyright (C) 2006-2008 Nokia Corporation.
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.
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
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
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
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.
34 * get_heap_comp_val - get the LEB properties value for heap comparisons.
35 * @lprops: LEB properties
38 static int get_heap_comp_val(struct ubifs_lprops
*lprops
, int cat
)
43 case LPROPS_DIRTY_IDX
:
44 return lprops
->free
+ lprops
->dirty
;
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
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
62 static void move_up_lpt_heap(struct ubifs_info
*c
, struct ubifs_lpt_heap
*heap
,
63 struct ubifs_lprops
*lprops
, int cat
)
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 */
73 int ppos
= (hpos
- 1) / 2;
75 val2
= get_heap_comp_val(heap
->arr
[ppos
], cat
);
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
;
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
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.
99 static void adjust_lpt_heap(struct ubifs_info
*c
, struct ubifs_lpt_heap
*heap
,
100 struct ubifs_lprops
*lprops
, int hpos
, int cat
)
102 int val1
, val2
, val3
, cpos
;
104 val1
= get_heap_comp_val(lprops
, cat
);
105 /* Compare to parent and, if greater than parent, move up the heap */
107 int ppos
= (hpos
- 1) / 2;
109 val2
= get_heap_comp_val(heap
->arr
[ppos
], cat
);
111 /* Greater than parent so move up */
113 heap
->arr
[ppos
]->hpos
= hpos
;
114 heap
->arr
[hpos
] = heap
->arr
[ppos
];
115 heap
->arr
[ppos
] = lprops
;
120 ppos
= (hpos
- 1) / 2;
121 val2
= get_heap_comp_val(heap
->arr
[ppos
], cat
);
124 /* Still greater than parent so keep going */
129 /* Not greater than parent, so compare to children */
131 /* Compare to left child */
133 if (cpos
>= heap
->cnt
)
135 val2
= get_heap_comp_val(heap
->arr
[cpos
], cat
);
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],
142 cpos
+= 1; /* Right child is bigger */
144 heap
->arr
[cpos
]->hpos
= hpos
;
145 heap
->arr
[hpos
] = heap
->arr
[cpos
];
146 heap
->arr
[cpos
] = lprops
;
151 /* Compare to right child */
153 if (cpos
>= heap
->cnt
)
155 val3
= get_heap_comp_val(heap
->arr
[cpos
], cat
);
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
;
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
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.
178 static int add_to_lpt_heap(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
,
181 struct ubifs_lpt_heap
*heap
= &c
->lpt_heap
[cat
- 1];
183 if (heap
->cnt
>= heap
->max_cnt
) {
184 const int b
= LPT_HEAP_SZ
/ 2 - 1;
185 int cpos
, val1
, val2
;
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
);
194 val1
= get_heap_comp_val(lprops
, cat
);
195 val2
= get_heap_comp_val(heap
->arr
[cpos
], cat
);
197 struct ubifs_lprops
*lp
;
199 lp
= heap
->arr
[cpos
];
200 lp
->flags
&= ~LPROPS_CAT_MASK
;
201 lp
->flags
|= LPROPS_UNCAT
;
202 list_add(&lp
->list
, &c
->uncat_list
);
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 */
209 dbg_check_heap(c
, heap
, cat
, -1);
210 return 0; /* Not added to heap */
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 */
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
226 static void remove_from_lpt_heap(struct ubifs_info
*c
,
227 struct ubifs_lprops
*lprops
, int cat
)
229 struct ubifs_lpt_heap
*heap
;
230 int hpos
= lprops
->hpos
;
232 heap
= &c
->lpt_heap
[cat
- 1];
233 ubifs_assert(hpos
>= 0 && hpos
< heap
->cnt
);
234 ubifs_assert(heap
->arr
[hpos
] == lprops
);
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
);
241 dbg_check_heap(c
, heap
, cat
, -1);
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
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.
256 static void lpt_heap_replace(struct ubifs_info
*c
,
257 struct ubifs_lprops
*old_lprops
,
258 struct ubifs_lprops
*new_lprops
, int cat
)
260 struct ubifs_lpt_heap
*heap
;
261 int hpos
= new_lprops
->hpos
;
263 heap
= &c
->lpt_heap
[cat
- 1];
264 heap
->arr
[hpos
] = new_lprops
;
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
273 * LEB properties are categorized to enable fast find operations.
275 void ubifs_add_to_cat(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
,
280 case LPROPS_DIRTY_IDX
:
282 if (add_to_lpt_heap(c
, lprops
, cat
))
284 /* No more room on heap so make it un-categorized */
288 list_add(&lprops
->list
, &c
->uncat_list
);
291 list_add(&lprops
->list
, &c
->empty_list
);
293 case LPROPS_FREEABLE
:
294 list_add(&lprops
->list
, &c
->freeable_list
);
295 c
->freeable_cnt
+= 1;
297 case LPROPS_FRDI_IDX
:
298 list_add(&lprops
->list
, &c
->frdi_idx_list
);
303 lprops
->flags
&= ~LPROPS_CAT_MASK
;
304 lprops
->flags
|= cat
;
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
313 * LEB properties are categorized to enable fast find operations.
315 static void ubifs_remove_from_cat(struct ubifs_info
*c
,
316 struct ubifs_lprops
*lprops
, int cat
)
320 case LPROPS_DIRTY_IDX
:
322 remove_from_lpt_heap(c
, lprops
, cat
);
324 case LPROPS_FREEABLE
:
325 c
->freeable_cnt
-= 1;
326 ubifs_assert(c
->freeable_cnt
>= 0);
330 case LPROPS_FRDI_IDX
:
331 ubifs_assert(!list_empty(&lprops
->list
));
332 list_del(&lprops
->list
);
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
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.
349 void ubifs_replace_cat(struct ubifs_info
*c
, struct ubifs_lprops
*old_lprops
,
350 struct ubifs_lprops
*new_lprops
)
354 cat
= new_lprops
->flags
& LPROPS_CAT_MASK
;
357 case LPROPS_DIRTY_IDX
:
359 lpt_heap_replace(c
, old_lprops
, new_lprops
, cat
);
363 case LPROPS_FREEABLE
:
364 case LPROPS_FRDI_IDX
:
365 list_replace(&old_lprops
->list
, &new_lprops
->list
);
373 * ubifs_ensure_cat - ensure LEB properties are categorized.
374 * @c: UBIFS file-system description object
375 * @lprops: LEB properties
377 * A LEB may have fallen off of the bottom of a heap, and ended up as
378 * un-categorized even though it has enough space for us now. If that is the
379 * case this function will put the LEB back onto a heap.
381 void ubifs_ensure_cat(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
)
383 int cat
= lprops
->flags
& LPROPS_CAT_MASK
;
385 if (cat
!= LPROPS_UNCAT
)
387 cat
= ubifs_categorize_lprops(c
, lprops
);
388 if (cat
== LPROPS_UNCAT
)
390 ubifs_remove_from_cat(c
, lprops
, LPROPS_UNCAT
);
391 ubifs_add_to_cat(c
, lprops
, cat
);
395 * ubifs_categorize_lprops - categorize LEB properties.
396 * @c: UBIFS file-system description object
397 * @lprops: LEB properties to categorize
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.
404 int ubifs_categorize_lprops(const struct ubifs_info
*c
,
405 const struct ubifs_lprops
*lprops
)
407 if (lprops
->flags
& LPROPS_TAKEN
)
410 if (lprops
->free
== c
->leb_size
) {
411 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
415 if (lprops
->free
+ lprops
->dirty
== c
->leb_size
) {
416 if (lprops
->flags
& LPROPS_INDEX
)
417 return LPROPS_FRDI_IDX
;
419 return LPROPS_FREEABLE
;
422 if (lprops
->flags
& LPROPS_INDEX
) {
423 if (lprops
->dirty
+ lprops
->free
>= c
->min_idx_node_sz
)
424 return LPROPS_DIRTY_IDX
;
426 if (lprops
->dirty
>= c
->dead_wm
&&
427 lprops
->dirty
> lprops
->free
)
429 if (lprops
->free
> 0)
437 * change_category - change LEB properties category.
438 * @c: UBIFS file-system description object
439 * @lprops: LEB properties to re-categorize
441 * LEB properties are categorized to enable fast find operations. When the LEB
442 * properties change they must be re-categorized.
444 static void change_category(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
)
446 int old_cat
= lprops
->flags
& LPROPS_CAT_MASK
;
447 int new_cat
= ubifs_categorize_lprops(c
, lprops
);
449 if (old_cat
== new_cat
) {
450 struct ubifs_lpt_heap
*heap
;
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
);
458 ubifs_remove_from_cat(c
, lprops
, old_cat
);
459 ubifs_add_to_cat(c
, lprops
, new_cat
);
464 * ubifs_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
468 * This function calculates and returns amount of dark space in an LEB which
469 * has @spc bytes of free and dirty space.
471 * UBIFS is trying to account the space which might not be usable, and this
472 * space is called "dark space". For example, if an LEB has only %512 free
473 * bytes, it is dark space, because it cannot fit a large data node.
475 int ubifs_calc_dark(const struct ubifs_info
*c
, int spc
)
477 ubifs_assert(!(spc
& 7));
479 if (spc
< c
->dark_wm
)
483 * If we have slightly more space then the dark space watermark, we can
484 * anyway safely assume it we'll be able to write a node of the
485 * smallest size there.
487 if (spc
- c
->dark_wm
< MIN_WRITE_SZ
)
488 return spc
- MIN_WRITE_SZ
;
494 * is_lprops_dirty - determine if LEB properties are dirty.
495 * @c: the UBIFS file-system description object
496 * @lprops: LEB properties to test
498 static int is_lprops_dirty(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
)
500 struct ubifs_pnode
*pnode
;
503 pos
= (lprops
->lnum
- c
->main_first
) & (UBIFS_LPT_FANOUT
- 1);
504 pnode
= (struct ubifs_pnode
*)container_of(lprops
- pos
,
507 return !test_bit(COW_CNODE
, &pnode
->flags
) &&
508 test_bit(DIRTY_CNODE
, &pnode
->flags
);
512 * ubifs_change_lp - change LEB properties.
513 * @c: the UBIFS file-system description object
514 * @lp: LEB properties to change
515 * @free: new free space amount
516 * @dirty: new dirty space amount
518 * @idx_gc_cnt: change to the count of @idx_gc list
520 * This function changes LEB properties (@free, @dirty or @flag). However, the
521 * property which has the %LPROPS_NC value is not changed. Returns a pointer to
522 * the updated LEB properties on success and a negative error code on failure.
524 * Note, the LEB properties may have had to be copied (due to COW) and
525 * consequently the pointer returned may not be the same as the pointer
528 const struct ubifs_lprops
*ubifs_change_lp(struct ubifs_info
*c
,
529 const struct ubifs_lprops
*lp
,
530 int free
, int dirty
, int flags
,
534 * This is the only function that is allowed to change lprops, so we
535 * discard the "const" qualifier.
537 struct ubifs_lprops
*lprops
= (struct ubifs_lprops
*)lp
;
539 dbg_lp("LEB %d, free %d, dirty %d, flags %d",
540 lprops
->lnum
, free
, dirty
, flags
);
542 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
543 ubifs_assert(c
->lst
.empty_lebs
>= 0 &&
544 c
->lst
.empty_lebs
<= c
->main_lebs
);
545 ubifs_assert(c
->freeable_cnt
>= 0);
546 ubifs_assert(c
->freeable_cnt
<= c
->main_lebs
);
547 ubifs_assert(c
->lst
.taken_empty_lebs
>= 0);
548 ubifs_assert(c
->lst
.taken_empty_lebs
<= c
->lst
.empty_lebs
);
549 ubifs_assert(!(c
->lst
.total_free
& 7) && !(c
->lst
.total_dirty
& 7));
550 ubifs_assert(!(c
->lst
.total_dead
& 7) && !(c
->lst
.total_dark
& 7));
551 ubifs_assert(!(c
->lst
.total_used
& 7));
552 ubifs_assert(free
== LPROPS_NC
|| free
>= 0);
553 ubifs_assert(dirty
== LPROPS_NC
|| dirty
>= 0);
555 if (!is_lprops_dirty(c
, lprops
)) {
556 lprops
= ubifs_lpt_lookup_dirty(c
, lprops
->lnum
);
560 ubifs_assert(lprops
== ubifs_lpt_lookup_dirty(c
, lprops
->lnum
));
562 ubifs_assert(!(lprops
->free
& 7) && !(lprops
->dirty
& 7));
564 spin_lock(&c
->space_lock
);
565 if ((lprops
->flags
& LPROPS_TAKEN
) && lprops
->free
== c
->leb_size
)
566 c
->lst
.taken_empty_lebs
-= 1;
568 if (!(lprops
->flags
& LPROPS_INDEX
)) {
571 old_spc
= lprops
->free
+ lprops
->dirty
;
572 if (old_spc
< c
->dead_wm
)
573 c
->lst
.total_dead
-= old_spc
;
575 c
->lst
.total_dark
-= ubifs_calc_dark(c
, old_spc
);
577 c
->lst
.total_used
-= c
->leb_size
- old_spc
;
580 if (free
!= LPROPS_NC
) {
581 free
= ALIGN(free
, 8);
582 c
->lst
.total_free
+= free
- lprops
->free
;
584 /* Increase or decrease empty LEBs counter if needed */
585 if (free
== c
->leb_size
) {
586 if (lprops
->free
!= c
->leb_size
)
587 c
->lst
.empty_lebs
+= 1;
588 } else if (lprops
->free
== c
->leb_size
)
589 c
->lst
.empty_lebs
-= 1;
593 if (dirty
!= LPROPS_NC
) {
594 dirty
= ALIGN(dirty
, 8);
595 c
->lst
.total_dirty
+= dirty
- lprops
->dirty
;
596 lprops
->dirty
= dirty
;
599 if (flags
!= LPROPS_NC
) {
600 /* Take care about indexing LEBs counter if needed */
601 if ((lprops
->flags
& LPROPS_INDEX
)) {
602 if (!(flags
& LPROPS_INDEX
))
603 c
->lst
.idx_lebs
-= 1;
604 } else if (flags
& LPROPS_INDEX
)
605 c
->lst
.idx_lebs
+= 1;
606 lprops
->flags
= flags
;
609 if (!(lprops
->flags
& LPROPS_INDEX
)) {
612 new_spc
= lprops
->free
+ lprops
->dirty
;
613 if (new_spc
< c
->dead_wm
)
614 c
->lst
.total_dead
+= new_spc
;
616 c
->lst
.total_dark
+= ubifs_calc_dark(c
, new_spc
);
618 c
->lst
.total_used
+= c
->leb_size
- new_spc
;
621 if ((lprops
->flags
& LPROPS_TAKEN
) && lprops
->free
== c
->leb_size
)
622 c
->lst
.taken_empty_lebs
+= 1;
624 change_category(c
, lprops
);
625 c
->idx_gc_cnt
+= idx_gc_cnt
;
626 spin_unlock(&c
->space_lock
);
631 * ubifs_get_lp_stats - get lprops statistics.
632 * @c: UBIFS file-system description object
633 * @st: return statistics
635 void ubifs_get_lp_stats(struct ubifs_info
*c
, struct ubifs_lp_stats
*lst
)
637 spin_lock(&c
->space_lock
);
638 memcpy(lst
, &c
->lst
, sizeof(struct ubifs_lp_stats
));
639 spin_unlock(&c
->space_lock
);
643 * ubifs_change_one_lp - change LEB properties.
644 * @c: the UBIFS file-system description object
645 * @lnum: LEB to change properties for
646 * @free: amount of free space
647 * @dirty: amount of dirty space
648 * @flags_set: flags to set
649 * @flags_clean: flags to clean
650 * @idx_gc_cnt: change to the count of idx_gc list
652 * This function changes properties of LEB @lnum. It is a helper wrapper over
653 * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the
654 * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and
655 * a negative error code in case of failure.
657 int ubifs_change_one_lp(struct ubifs_info
*c
, int lnum
, int free
, int dirty
,
658 int flags_set
, int flags_clean
, int idx_gc_cnt
)
661 const struct ubifs_lprops
*lp
;
665 lp
= ubifs_lpt_lookup_dirty(c
, lnum
);
671 flags
= (lp
->flags
| flags_set
) & ~flags_clean
;
672 lp
= ubifs_change_lp(c
, lp
, free
, dirty
, flags
, idx_gc_cnt
);
677 ubifs_release_lprops(c
);
679 ubifs_err("cannot change properties of LEB %d, error %d",
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
693 * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
694 * current dirty space, not substitutes it.
696 int ubifs_update_one_lp(struct ubifs_info
*c
, int lnum
, int free
, int dirty
,
697 int flags_set
, int flags_clean
)
700 const struct ubifs_lprops
*lp
;
704 lp
= ubifs_lpt_lookup_dirty(c
, lnum
);
710 flags
= (lp
->flags
| flags_set
) & ~flags_clean
;
711 lp
= ubifs_change_lp(c
, lp
, free
, lp
->dirty
+ dirty
, flags
, 0);
716 ubifs_release_lprops(c
);
718 ubifs_err("cannot update properties of LEB %d, error %d",
724 * ubifs_read_one_lp - read LEB properties.
725 * @c: the UBIFS file-system description object
726 * @lnum: LEB to read properties for
727 * @lp: where to store read properties
729 * This helper function reads properties of a LEB @lnum and stores them in @lp.
730 * Returns zero in case of success and a negative error code in case of
733 int ubifs_read_one_lp(struct ubifs_info
*c
, int lnum
, struct ubifs_lprops
*lp
)
736 const struct ubifs_lprops
*lpp
;
740 lpp
= ubifs_lpt_lookup(c
, lnum
);
743 ubifs_err("cannot read properties of LEB %d, error %d",
748 memcpy(lp
, lpp
, sizeof(struct ubifs_lprops
));
751 ubifs_release_lprops(c
);
756 * ubifs_fast_find_free - try to find a LEB with free space quickly.
757 * @c: the UBIFS file-system description object
759 * This function returns LEB properties for a LEB with free space or %NULL if
760 * the function is unable to find a LEB quickly.
762 const struct ubifs_lprops
*ubifs_fast_find_free(struct ubifs_info
*c
)
764 struct ubifs_lprops
*lprops
;
765 struct ubifs_lpt_heap
*heap
;
767 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
769 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
773 lprops
= heap
->arr
[0];
774 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
775 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
780 * ubifs_fast_find_empty - try to find an empty LEB quickly.
781 * @c: the UBIFS file-system description object
783 * This function returns LEB properties for an empty LEB or %NULL if the
784 * function is unable to find an empty LEB quickly.
786 const struct ubifs_lprops
*ubifs_fast_find_empty(struct ubifs_info
*c
)
788 struct ubifs_lprops
*lprops
;
790 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
792 if (list_empty(&c
->empty_list
))
795 lprops
= list_entry(c
->empty_list
.next
, struct ubifs_lprops
, list
);
796 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
797 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
798 ubifs_assert(lprops
->free
== c
->leb_size
);
803 * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
804 * @c: the UBIFS file-system description object
806 * This function returns LEB properties for a freeable LEB or %NULL if the
807 * function is unable to find a freeable LEB quickly.
809 const struct ubifs_lprops
*ubifs_fast_find_freeable(struct ubifs_info
*c
)
811 struct ubifs_lprops
*lprops
;
813 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
815 if (list_empty(&c
->freeable_list
))
818 lprops
= list_entry(c
->freeable_list
.next
, struct ubifs_lprops
, list
);
819 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
820 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
821 ubifs_assert(lprops
->free
+ lprops
->dirty
== c
->leb_size
);
822 ubifs_assert(c
->freeable_cnt
> 0);
827 * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
828 * @c: the UBIFS file-system description object
830 * This function returns LEB properties for a freeable index LEB or %NULL if the
831 * function is unable to find a freeable index LEB quickly.
833 const struct ubifs_lprops
*ubifs_fast_find_frdi_idx(struct ubifs_info
*c
)
835 struct ubifs_lprops
*lprops
;
837 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
839 if (list_empty(&c
->frdi_idx_list
))
842 lprops
= list_entry(c
->frdi_idx_list
.next
, struct ubifs_lprops
, list
);
843 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
844 ubifs_assert((lprops
->flags
& LPROPS_INDEX
));
845 ubifs_assert(lprops
->free
+ lprops
->dirty
== c
->leb_size
);
850 * Everything below is related to debugging.
854 * dbg_check_cats - check category heaps and lists.
855 * @c: UBIFS file-system description object
857 * This function returns %0 on success and a negative error code on failure.
859 int dbg_check_cats(struct ubifs_info
*c
)
861 struct ubifs_lprops
*lprops
;
862 struct list_head
*pos
;
865 if (!dbg_is_chk_gen(c
) && !dbg_is_chk_lprops(c
))
868 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
869 if (lprops
->free
!= c
->leb_size
) {
870 ubifs_err("non-empty LEB %d on empty list (free %d dirty %d flags %d)",
871 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
875 if (lprops
->flags
& LPROPS_TAKEN
) {
876 ubifs_err("taken LEB %d on empty list (free %d dirty %d flags %d)",
877 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
884 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
885 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
886 ubifs_err("non-freeable LEB %d on freeable list (free %d dirty %d flags %d)",
887 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
891 if (lprops
->flags
& LPROPS_TAKEN
) {
892 ubifs_err("taken LEB %d on freeable list (free %d dirty %d flags %d)",
893 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
899 if (i
!= c
->freeable_cnt
) {
900 ubifs_err("freeable list count %d expected %d", i
,
906 list_for_each(pos
, &c
->idx_gc
)
908 if (i
!= c
->idx_gc_cnt
) {
909 ubifs_err("idx_gc list count %d expected %d", i
,
914 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
915 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
916 ubifs_err("non-freeable LEB %d on frdi_idx list (free %d dirty %d flags %d)",
917 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
921 if (lprops
->flags
& LPROPS_TAKEN
) {
922 ubifs_err("taken LEB %d on frdi_idx list (free %d dirty %d flags %d)",
923 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
927 if (!(lprops
->flags
& LPROPS_INDEX
)) {
928 ubifs_err("non-index LEB %d on frdi_idx list (free %d dirty %d flags %d)",
929 lprops
->lnum
, lprops
->free
, lprops
->dirty
,
935 for (cat
= 1; cat
<= LPROPS_HEAP_CNT
; cat
++) {
936 struct ubifs_lpt_heap
*heap
= &c
->lpt_heap
[cat
- 1];
938 for (i
= 0; i
< heap
->cnt
; i
++) {
939 lprops
= heap
->arr
[i
];
941 ubifs_err("null ptr in LPT heap cat %d", cat
);
944 if (lprops
->hpos
!= i
) {
945 ubifs_err("bad ptr in LPT heap cat %d", cat
);
948 if (lprops
->flags
& LPROPS_TAKEN
) {
949 ubifs_err("taken LEB in LPT heap cat %d", cat
);
958 void dbg_check_heap(struct ubifs_info
*c
, struct ubifs_lpt_heap
*heap
, int cat
,
961 int i
= 0, j
, err
= 0;
963 if (!dbg_is_chk_gen(c
) && !dbg_is_chk_lprops(c
))
966 for (i
= 0; i
< heap
->cnt
; i
++) {
967 struct ubifs_lprops
*lprops
= heap
->arr
[i
];
968 struct ubifs_lprops
*lp
;
971 if ((lprops
->flags
& LPROPS_CAT_MASK
) != cat
) {
975 if (lprops
->hpos
!= i
) {
979 lp
= ubifs_lpt_lookup(c
, lprops
->lnum
);
985 ubifs_err("lprops %zx lp %zx lprops->lnum %d lp->lnum %d",
986 (size_t)lprops
, (size_t)lp
, lprops
->lnum
,
991 for (j
= 0; j
< i
; j
++) {
997 if (lp
->lnum
== lprops
->lnum
) {
1005 ubifs_err("failed cat %d hpos %d err %d", cat
, i
, err
);
1007 ubifs_dump_heap(c
, heap
, cat
);
1012 * scan_check_cb - scan callback.
1013 * @c: the UBIFS file-system description object
1014 * @lp: LEB properties to scan
1015 * @in_tree: whether the LEB properties are in main memory
1016 * @lst: lprops statistics to update
1018 * This function returns a code that indicates whether the scan should continue
1019 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
1020 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
1023 static int scan_check_cb(struct ubifs_info
*c
,
1024 const struct ubifs_lprops
*lp
, int in_tree
,
1025 struct ubifs_lp_stats
*lst
)
1027 struct ubifs_scan_leb
*sleb
;
1028 struct ubifs_scan_node
*snod
;
1029 int cat
, lnum
= lp
->lnum
, is_idx
= 0, used
= 0, free
, dirty
, ret
;
1032 cat
= lp
->flags
& LPROPS_CAT_MASK
;
1033 if (cat
!= LPROPS_UNCAT
) {
1034 cat
= ubifs_categorize_lprops(c
, lp
);
1035 if (cat
!= (lp
->flags
& LPROPS_CAT_MASK
)) {
1036 ubifs_err("bad LEB category %d expected %d",
1037 (lp
->flags
& LPROPS_CAT_MASK
), cat
);
1042 /* Check lp is on its category list (if it has one) */
1044 struct list_head
*list
= NULL
;
1048 list
= &c
->empty_list
;
1050 case LPROPS_FREEABLE
:
1051 list
= &c
->freeable_list
;
1053 case LPROPS_FRDI_IDX
:
1054 list
= &c
->frdi_idx_list
;
1057 list
= &c
->uncat_list
;
1061 struct ubifs_lprops
*lprops
;
1064 list_for_each_entry(lprops
, list
, list
) {
1071 ubifs_err("bad LPT list (category %d)", cat
);
1077 /* Check lp is on its category heap (if it has one) */
1078 if (in_tree
&& cat
> 0 && cat
<= LPROPS_HEAP_CNT
) {
1079 struct ubifs_lpt_heap
*heap
= &c
->lpt_heap
[cat
- 1];
1081 if ((lp
->hpos
!= -1 && heap
->arr
[lp
->hpos
]->lnum
!= lnum
) ||
1082 lp
!= heap
->arr
[lp
->hpos
]) {
1083 ubifs_err("bad LPT heap (category %d)", cat
);
1088 buf
= __vmalloc(c
->leb_size
, GFP_NOFS
, PAGE_KERNEL
);
1093 * After an unclean unmount, empty and freeable LEBs
1094 * may contain garbage - do not scan them.
1096 if (lp
->free
== c
->leb_size
) {
1097 lst
->empty_lebs
+= 1;
1098 lst
->total_free
+= c
->leb_size
;
1099 lst
->total_dark
+= ubifs_calc_dark(c
, c
->leb_size
);
1100 return LPT_SCAN_CONTINUE
;
1102 if (lp
->free
+ lp
->dirty
== c
->leb_size
&&
1103 !(lp
->flags
& LPROPS_INDEX
)) {
1104 lst
->total_free
+= lp
->free
;
1105 lst
->total_dirty
+= lp
->dirty
;
1106 lst
->total_dark
+= ubifs_calc_dark(c
, c
->leb_size
);
1107 return LPT_SCAN_CONTINUE
;
1110 sleb
= ubifs_scan(c
, lnum
, 0, buf
, 0);
1112 ret
= PTR_ERR(sleb
);
1113 if (ret
== -EUCLEAN
) {
1114 ubifs_dump_lprops(c
);
1115 ubifs_dump_budg(c
, &c
->bi
);
1121 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
1122 int found
, level
= 0;
1127 is_idx
= (snod
->type
== UBIFS_IDX_NODE
) ? 1 : 0;
1129 if (is_idx
&& snod
->type
!= UBIFS_IDX_NODE
) {
1130 ubifs_err("indexing node in data LEB %d:%d",
1135 if (snod
->type
== UBIFS_IDX_NODE
) {
1136 struct ubifs_idx_node
*idx
= snod
->node
;
1138 key_read(c
, ubifs_idx_key(c
, idx
), &snod
->key
);
1139 level
= le16_to_cpu(idx
->level
);
1142 found
= ubifs_tnc_has_node(c
, &snod
->key
, level
, lnum
,
1143 snod
->offs
, is_idx
);
1147 used
+= ALIGN(snod
->len
, 8);
1151 free
= c
->leb_size
- sleb
->endpt
;
1152 dirty
= sleb
->endpt
- used
;
1154 if (free
> c
->leb_size
|| free
< 0 || dirty
> c
->leb_size
||
1156 ubifs_err("bad calculated accounting for LEB %d: free %d, dirty %d",
1161 if (lp
->free
+ lp
->dirty
== c
->leb_size
&&
1162 free
+ dirty
== c
->leb_size
)
1163 if ((is_idx
&& !(lp
->flags
& LPROPS_INDEX
)) ||
1164 (!is_idx
&& free
== c
->leb_size
) ||
1165 lp
->free
== c
->leb_size
) {
1167 * Empty or freeable LEBs could contain index
1168 * nodes from an uncompleted commit due to an
1169 * unclean unmount. Or they could be empty for
1170 * the same reason. Or it may simply not have been
1178 if (is_idx
&& lp
->free
+ lp
->dirty
== free
+ dirty
&&
1179 lnum
!= c
->ihead_lnum
) {
1181 * After an unclean unmount, an index LEB could have a different
1182 * amount of free space than the value recorded by lprops. That
1183 * is because the in-the-gaps method may use free space or
1184 * create free space (as a side-effect of using ubi_leb_change
1185 * and not writing the whole LEB). The incorrect free space
1186 * value is not a problem because the index is only ever
1187 * allocated empty LEBs, so there will never be an attempt to
1188 * write to the free space at the end of an index LEB - except
1189 * by the in-the-gaps method for which it is not a problem.
1195 if (lp
->free
!= free
|| lp
->dirty
!= dirty
)
1198 if (is_idx
&& !(lp
->flags
& LPROPS_INDEX
)) {
1199 if (free
== c
->leb_size
)
1200 /* Free but not unmapped LEB, it's fine */
1203 ubifs_err("indexing node without indexing flag");
1208 if (!is_idx
&& (lp
->flags
& LPROPS_INDEX
)) {
1209 ubifs_err("data node with indexing flag");
1213 if (free
== c
->leb_size
)
1214 lst
->empty_lebs
+= 1;
1219 if (!(lp
->flags
& LPROPS_INDEX
))
1220 lst
->total_used
+= c
->leb_size
- free
- dirty
;
1221 lst
->total_free
+= free
;
1222 lst
->total_dirty
+= dirty
;
1224 if (!(lp
->flags
& LPROPS_INDEX
)) {
1225 int spc
= free
+ dirty
;
1227 if (spc
< c
->dead_wm
)
1228 lst
->total_dead
+= spc
;
1230 lst
->total_dark
+= ubifs_calc_dark(c
, spc
);
1233 ubifs_scan_destroy(sleb
);
1235 return LPT_SCAN_CONTINUE
;
1238 ubifs_err("bad accounting of LEB %d: free %d, dirty %d flags %#x, should be free %d, dirty %d",
1239 lnum
, lp
->free
, lp
->dirty
, lp
->flags
, free
, dirty
);
1240 ubifs_dump_leb(c
, lnum
);
1242 ubifs_scan_destroy(sleb
);
1250 * dbg_check_lprops - check all LEB properties.
1251 * @c: UBIFS file-system description object
1253 * This function checks all LEB properties and makes sure they are all correct.
1254 * It returns zero if everything is fine, %-EINVAL if there is an inconsistency
1255 * and other negative error codes in case of other errors. This function is
1256 * called while the file system is locked (because of commit start), so no
1257 * additional locking is required. Note that locking the LPT mutex would cause
1258 * a circular lock dependency with the TNC mutex.
1260 int dbg_check_lprops(struct ubifs_info
*c
)
1263 struct ubifs_lp_stats lst
;
1265 if (!dbg_is_chk_lprops(c
))
1269 * As we are going to scan the media, the write buffers have to be
1272 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
1273 err
= ubifs_wbuf_sync(&c
->jheads
[i
].wbuf
);
1278 memset(&lst
, 0, sizeof(struct ubifs_lp_stats
));
1279 err
= ubifs_lpt_scan_nolock(c
, c
->main_first
, c
->leb_cnt
- 1,
1280 (ubifs_lpt_scan_callback
)scan_check_cb
,
1282 if (err
&& err
!= -ENOSPC
)
1285 if (lst
.empty_lebs
!= c
->lst
.empty_lebs
||
1286 lst
.idx_lebs
!= c
->lst
.idx_lebs
||
1287 lst
.total_free
!= c
->lst
.total_free
||
1288 lst
.total_dirty
!= c
->lst
.total_dirty
||
1289 lst
.total_used
!= c
->lst
.total_used
) {
1290 ubifs_err("bad overall accounting");
1291 ubifs_err("calculated: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",
1292 lst
.empty_lebs
, lst
.idx_lebs
, lst
.total_free
,
1293 lst
.total_dirty
, lst
.total_used
);
1294 ubifs_err("read from lprops: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",
1295 c
->lst
.empty_lebs
, c
->lst
.idx_lebs
, c
->lst
.total_free
,
1296 c
->lst
.total_dirty
, c
->lst
.total_used
);
1301 if (lst
.total_dead
!= c
->lst
.total_dead
||
1302 lst
.total_dark
!= c
->lst
.total_dark
) {
1303 ubifs_err("bad dead/dark space accounting");
1304 ubifs_err("calculated: total_dead %lld, total_dark %lld",
1305 lst
.total_dead
, lst
.total_dark
);
1306 ubifs_err("read from lprops: total_dead %lld, total_dark %lld",
1307 c
->lst
.total_dead
, c
->lst
.total_dark
);
1312 err
= dbg_check_cats(c
);