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 uncategorized */
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 * 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.
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 recategorize
441 * LEB properties are categorized to enable fast find operations. When the LEB
442 * properties change they must be recategorized.
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
= &c
->lpt_heap
[new_cat
- 1];
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 * 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 amount of dark space in an LEB which has @spc bytes
469 * of free and dirty space. Returns the calculations result.
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
478 static int calc_dark(struct ubifs_info
*c
, int spc
)
480 ubifs_assert(!(spc
& 7));
482 if (spc
< c
->dark_wm
)
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.
490 if (spc
- c
->dark_wm
< MIN_WRITE_SZ
)
491 return spc
- MIN_WRITE_SZ
;
497 * is_lprops_dirty - determine if LEB properties are dirty.
498 * @c: the UBIFS file-system description object
499 * @lprops: LEB properties to test
501 static int is_lprops_dirty(struct ubifs_info
*c
, struct ubifs_lprops
*lprops
)
503 struct ubifs_pnode
*pnode
;
506 pos
= (lprops
->lnum
- c
->main_first
) & (UBIFS_LPT_FANOUT
- 1);
507 pnode
= (struct ubifs_pnode
*)container_of(lprops
- pos
,
510 return !test_bit(COW_ZNODE
, &pnode
->flags
) &&
511 test_bit(DIRTY_CNODE
, &pnode
->flags
);
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
521 * @idx_gc_cnt: change to the count of idx_gc list
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.
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
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
,
537 * This is the only function that is allowed to change lprops, so we
538 * discard the const qualifier.
540 struct ubifs_lprops
*lprops
= (struct ubifs_lprops
*)lp
;
542 dbg_lp("LEB %d, free %d, dirty %d, flags %d",
543 lprops
->lnum
, free
, dirty
, flags
);
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);
558 if (!is_lprops_dirty(c
, lprops
)) {
559 lprops
= ubifs_lpt_lookup_dirty(c
, lprops
->lnum
);
563 ubifs_assert(lprops
== ubifs_lpt_lookup_dirty(c
, lprops
->lnum
));
565 ubifs_assert(!(lprops
->free
& 7) && !(lprops
->dirty
& 7));
567 spin_lock(&c
->space_lock
);
568 if ((lprops
->flags
& LPROPS_TAKEN
) && lprops
->free
== c
->leb_size
)
569 c
->lst
.taken_empty_lebs
-= 1;
571 if (!(lprops
->flags
& LPROPS_INDEX
)) {
574 old_spc
= lprops
->free
+ lprops
->dirty
;
575 if (old_spc
< c
->dead_wm
)
576 c
->lst
.total_dead
-= old_spc
;
578 c
->lst
.total_dark
-= calc_dark(c
, old_spc
);
580 c
->lst
.total_used
-= c
->leb_size
- old_spc
;
583 if (free
!= LPROPS_NC
) {
584 free
= ALIGN(free
, 8);
585 c
->lst
.total_free
+= free
- lprops
->free
;
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;
596 if (dirty
!= LPROPS_NC
) {
597 dirty
= ALIGN(dirty
, 8);
598 c
->lst
.total_dirty
+= dirty
- lprops
->dirty
;
599 lprops
->dirty
= dirty
;
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
;
612 if (!(lprops
->flags
& LPROPS_INDEX
)) {
615 new_spc
= lprops
->free
+ lprops
->dirty
;
616 if (new_spc
< c
->dead_wm
)
617 c
->lst
.total_dead
+= new_spc
;
619 c
->lst
.total_dark
+= calc_dark(c
, new_spc
);
621 c
->lst
.total_used
+= c
->leb_size
- new_spc
;
624 if ((lprops
->flags
& LPROPS_TAKEN
) && lprops
->free
== c
->leb_size
)
625 c
->lst
.taken_empty_lebs
+= 1;
627 change_category(c
, lprops
);
628 c
->idx_gc_cnt
+= idx_gc_cnt
;
629 spin_unlock(&c
->space_lock
);
634 * ubifs_get_lp_stats - get lprops statistics.
635 * @c: UBIFS file-system description object
636 * @st: return statistics
638 void ubifs_get_lp_stats(struct ubifs_info
*c
, struct ubifs_lp_stats
*lst
)
640 spin_lock(&c
->space_lock
);
641 memcpy(lst
, &c
->lst
, sizeof(struct ubifs_lp_stats
));
642 spin_unlock(&c
->space_lock
);
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
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.
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
)
664 const struct ubifs_lprops
*lp
;
668 lp
= ubifs_lpt_lookup_dirty(c
, lnum
);
674 flags
= (lp
->flags
| flags_set
) & ~flags_clean
;
675 lp
= ubifs_change_lp(c
, lp
, free
, dirty
, flags
, idx_gc_cnt
);
680 ubifs_release_lprops(c
);
682 ubifs_err("cannot change properties of LEB %d, error %d",
688 * ubifs_update_one_lp - update LEB properties.
689 * @c: the UBIFS file-system description object
690 * @lnum: LEB to change properties for
691 * @free: amount of free space
692 * @dirty: amount of dirty space to add
693 * @flags_set: flags to set
694 * @flags_clean: flags to clean
696 * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
697 * current dirty space, not substitutes it.
699 int ubifs_update_one_lp(struct ubifs_info
*c
, int lnum
, int free
, int dirty
,
700 int flags_set
, int flags_clean
)
703 const struct ubifs_lprops
*lp
;
707 lp
= ubifs_lpt_lookup_dirty(c
, lnum
);
713 flags
= (lp
->flags
| flags_set
) & ~flags_clean
;
714 lp
= ubifs_change_lp(c
, lp
, free
, lp
->dirty
+ dirty
, flags
, 0);
719 ubifs_release_lprops(c
);
721 ubifs_err("cannot update properties of LEB %d, error %d",
727 * ubifs_read_one_lp - read LEB properties.
728 * @c: the UBIFS file-system description object
729 * @lnum: LEB to read properties for
730 * @lp: where to store read properties
732 * This helper function reads properties of a LEB @lnum and stores them in @lp.
733 * Returns zero in case of success and a negative error code in case of
736 int ubifs_read_one_lp(struct ubifs_info
*c
, int lnum
, struct ubifs_lprops
*lp
)
739 const struct ubifs_lprops
*lpp
;
743 lpp
= ubifs_lpt_lookup(c
, lnum
);
746 ubifs_err("cannot read properties of LEB %d, error %d",
751 memcpy(lp
, lpp
, sizeof(struct ubifs_lprops
));
754 ubifs_release_lprops(c
);
759 * ubifs_fast_find_free - try to find a LEB with free space quickly.
760 * @c: the UBIFS file-system description object
762 * This function returns LEB properties for a LEB with free space or %NULL if
763 * the function is unable to find a LEB quickly.
765 const struct ubifs_lprops
*ubifs_fast_find_free(struct ubifs_info
*c
)
767 struct ubifs_lprops
*lprops
;
768 struct ubifs_lpt_heap
*heap
;
770 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
772 heap
= &c
->lpt_heap
[LPROPS_FREE
- 1];
776 lprops
= heap
->arr
[0];
777 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
778 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
783 * ubifs_fast_find_empty - try to find an empty LEB quickly.
784 * @c: the UBIFS file-system description object
786 * This function returns LEB properties for an empty LEB or %NULL if the
787 * function is unable to find an empty LEB quickly.
789 const struct ubifs_lprops
*ubifs_fast_find_empty(struct ubifs_info
*c
)
791 struct ubifs_lprops
*lprops
;
793 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
795 if (list_empty(&c
->empty_list
))
798 lprops
= list_entry(c
->empty_list
.next
, struct ubifs_lprops
, list
);
799 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
800 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
801 ubifs_assert(lprops
->free
== c
->leb_size
);
806 * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
807 * @c: the UBIFS file-system description object
809 * This function returns LEB properties for a freeable LEB or %NULL if the
810 * function is unable to find a freeable LEB quickly.
812 const struct ubifs_lprops
*ubifs_fast_find_freeable(struct ubifs_info
*c
)
814 struct ubifs_lprops
*lprops
;
816 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
818 if (list_empty(&c
->freeable_list
))
821 lprops
= list_entry(c
->freeable_list
.next
, struct ubifs_lprops
, list
);
822 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
823 ubifs_assert(!(lprops
->flags
& LPROPS_INDEX
));
824 ubifs_assert(lprops
->free
+ lprops
->dirty
== c
->leb_size
);
825 ubifs_assert(c
->freeable_cnt
> 0);
830 * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
831 * @c: the UBIFS file-system description object
833 * This function returns LEB properties for a freeable index LEB or %NULL if the
834 * function is unable to find a freeable index LEB quickly.
836 const struct ubifs_lprops
*ubifs_fast_find_frdi_idx(struct ubifs_info
*c
)
838 struct ubifs_lprops
*lprops
;
840 ubifs_assert(mutex_is_locked(&c
->lp_mutex
));
842 if (list_empty(&c
->frdi_idx_list
))
845 lprops
= list_entry(c
->frdi_idx_list
.next
, struct ubifs_lprops
, list
);
846 ubifs_assert(!(lprops
->flags
& LPROPS_TAKEN
));
847 ubifs_assert((lprops
->flags
& LPROPS_INDEX
));
848 ubifs_assert(lprops
->free
+ lprops
->dirty
== c
->leb_size
);
852 #ifdef CONFIG_UBIFS_FS_DEBUG
855 * dbg_check_cats - check category heaps and lists.
856 * @c: UBIFS file-system description object
858 * This function returns %0 on success and a negative error code on failure.
860 int dbg_check_cats(struct ubifs_info
*c
)
862 struct ubifs_lprops
*lprops
;
863 struct list_head
*pos
;
866 if (!(ubifs_chk_flags
& (UBIFS_CHK_GEN
| UBIFS_CHK_LPROPS
)))
869 list_for_each_entry(lprops
, &c
->empty_list
, list
) {
870 if (lprops
->free
!= c
->leb_size
) {
871 ubifs_err("non-empty LEB %d on empty list "
872 "(free %d dirty %d flags %d)", lprops
->lnum
,
873 lprops
->free
, lprops
->dirty
, lprops
->flags
);
876 if (lprops
->flags
& LPROPS_TAKEN
) {
877 ubifs_err("taken LEB %d on empty list "
878 "(free %d dirty %d flags %d)", lprops
->lnum
,
879 lprops
->free
, lprops
->dirty
, lprops
->flags
);
885 list_for_each_entry(lprops
, &c
->freeable_list
, list
) {
886 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
887 ubifs_err("non-freeable LEB %d on freeable list "
888 "(free %d dirty %d flags %d)", lprops
->lnum
,
889 lprops
->free
, lprops
->dirty
, lprops
->flags
);
892 if (lprops
->flags
& LPROPS_TAKEN
) {
893 ubifs_err("taken LEB %d on freeable list "
894 "(free %d dirty %d flags %d)", lprops
->lnum
,
895 lprops
->free
, lprops
->dirty
, lprops
->flags
);
900 if (i
!= c
->freeable_cnt
) {
901 ubifs_err("freeable list count %d expected %d", i
,
907 list_for_each(pos
, &c
->idx_gc
)
909 if (i
!= c
->idx_gc_cnt
) {
910 ubifs_err("idx_gc list count %d expected %d", i
,
915 list_for_each_entry(lprops
, &c
->frdi_idx_list
, list
) {
916 if (lprops
->free
+ lprops
->dirty
!= c
->leb_size
) {
917 ubifs_err("non-freeable LEB %d on frdi_idx list "
918 "(free %d dirty %d flags %d)", lprops
->lnum
,
919 lprops
->free
, lprops
->dirty
, lprops
->flags
);
922 if (lprops
->flags
& LPROPS_TAKEN
) {
923 ubifs_err("taken LEB %d on frdi_idx list "
924 "(free %d dirty %d flags %d)", lprops
->lnum
,
925 lprops
->free
, lprops
->dirty
, lprops
->flags
);
928 if (!(lprops
->flags
& LPROPS_INDEX
)) {
929 ubifs_err("non-index LEB %d on frdi_idx list "
930 "(free %d dirty %d flags %d)", lprops
->lnum
,
931 lprops
->free
, lprops
->dirty
, lprops
->flags
);
936 for (cat
= 1; cat
<= LPROPS_HEAP_CNT
; cat
++) {
937 struct ubifs_lpt_heap
*heap
= &c
->lpt_heap
[cat
- 1];
939 for (i
= 0; i
< heap
->cnt
; i
++) {
940 lprops
= heap
->arr
[i
];
942 ubifs_err("null ptr in LPT heap cat %d", cat
);
945 if (lprops
->hpos
!= i
) {
946 ubifs_err("bad ptr in LPT heap cat %d", cat
);
949 if (lprops
->flags
& LPROPS_TAKEN
) {
950 ubifs_err("taken LEB in LPT heap cat %d", cat
);
959 void dbg_check_heap(struct ubifs_info
*c
, struct ubifs_lpt_heap
*heap
, int cat
,
962 int i
= 0, j
, err
= 0;
964 if (!(ubifs_chk_flags
& (UBIFS_CHK_GEN
| UBIFS_CHK_LPROPS
)))
967 for (i
= 0; i
< heap
->cnt
; i
++) {
968 struct ubifs_lprops
*lprops
= heap
->arr
[i
];
969 struct ubifs_lprops
*lp
;
972 if ((lprops
->flags
& LPROPS_CAT_MASK
) != cat
) {
976 if (lprops
->hpos
!= i
) {
980 lp
= ubifs_lpt_lookup(c
, lprops
->lnum
);
986 dbg_msg("lprops %zx lp %zx lprops->lnum %d lp->lnum %d",
987 (size_t)lprops
, (size_t)lp
, lprops
->lnum
,
992 for (j
= 0; j
< i
; j
++) {
998 if (lp
->lnum
== lprops
->lnum
) {
1006 dbg_msg("failed cat %d hpos %d err %d", cat
, i
, err
);
1008 dbg_dump_heap(c
, heap
, cat
);
1013 * struct scan_check_data - data provided to scan callback function.
1014 * @lst: LEB properties statistics
1017 struct scan_check_data
{
1018 struct ubifs_lp_stats lst
;
1023 * scan_check_cb - scan callback.
1024 * @c: the UBIFS file-system description object
1025 * @lp: LEB properties to scan
1026 * @in_tree: whether the LEB properties are in main memory
1027 * @data: information passed to and from the caller of the scan
1029 * This function returns a code that indicates whether the scan should continue
1030 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree
1031 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop
1034 static int scan_check_cb(struct ubifs_info
*c
,
1035 const struct ubifs_lprops
*lp
, int in_tree
,
1036 struct scan_check_data
*data
)
1038 struct ubifs_scan_leb
*sleb
;
1039 struct ubifs_scan_node
*snod
;
1040 struct ubifs_lp_stats
*lst
= &data
->lst
;
1041 int cat
, lnum
= lp
->lnum
, is_idx
= 0, used
= 0, free
, dirty
;
1043 cat
= lp
->flags
& LPROPS_CAT_MASK
;
1044 if (cat
!= LPROPS_UNCAT
) {
1045 cat
= ubifs_categorize_lprops(c
, lp
);
1046 if (cat
!= (lp
->flags
& LPROPS_CAT_MASK
)) {
1047 ubifs_err("bad LEB category %d expected %d",
1048 (lp
->flags
& LPROPS_CAT_MASK
), cat
);
1053 /* Check lp is on its category list (if it has one) */
1055 struct list_head
*list
= NULL
;
1059 list
= &c
->empty_list
;
1061 case LPROPS_FREEABLE
:
1062 list
= &c
->freeable_list
;
1064 case LPROPS_FRDI_IDX
:
1065 list
= &c
->frdi_idx_list
;
1068 list
= &c
->uncat_list
;
1072 struct ubifs_lprops
*lprops
;
1075 list_for_each_entry(lprops
, list
, list
) {
1082 ubifs_err("bad LPT list (category %d)", cat
);
1088 /* Check lp is on its category heap (if it has one) */
1089 if (in_tree
&& cat
> 0 && cat
<= LPROPS_HEAP_CNT
) {
1090 struct ubifs_lpt_heap
*heap
= &c
->lpt_heap
[cat
- 1];
1092 if ((lp
->hpos
!= -1 && heap
->arr
[lp
->hpos
]->lnum
!= lnum
) ||
1093 lp
!= heap
->arr
[lp
->hpos
]) {
1094 ubifs_err("bad LPT heap (category %d)", cat
);
1099 sleb
= ubifs_scan(c
, lnum
, 0, c
->dbg
->buf
);
1102 * After an unclean unmount, empty and freeable LEBs
1103 * may contain garbage.
1105 if (lp
->free
== c
->leb_size
) {
1106 ubifs_err("scan errors were in empty LEB "
1107 "- continuing checking");
1108 lst
->empty_lebs
+= 1;
1109 lst
->total_free
+= c
->leb_size
;
1110 lst
->total_dark
+= calc_dark(c
, c
->leb_size
);
1111 return LPT_SCAN_CONTINUE
;
1114 if (lp
->free
+ lp
->dirty
== c
->leb_size
&&
1115 !(lp
->flags
& LPROPS_INDEX
)) {
1116 ubifs_err("scan errors were in freeable LEB "
1117 "- continuing checking");
1118 lst
->total_free
+= lp
->free
;
1119 lst
->total_dirty
+= lp
->dirty
;
1120 lst
->total_dark
+= calc_dark(c
, c
->leb_size
);
1121 return LPT_SCAN_CONTINUE
;
1123 data
->err
= PTR_ERR(sleb
);
1124 return LPT_SCAN_STOP
;
1128 list_for_each_entry(snod
, &sleb
->nodes
, list
) {
1129 int found
, level
= 0;
1134 is_idx
= (snod
->type
== UBIFS_IDX_NODE
) ? 1 : 0;
1136 if (is_idx
&& snod
->type
!= UBIFS_IDX_NODE
) {
1137 ubifs_err("indexing node in data LEB %d:%d",
1142 if (snod
->type
== UBIFS_IDX_NODE
) {
1143 struct ubifs_idx_node
*idx
= snod
->node
;
1145 key_read(c
, ubifs_idx_key(c
, idx
), &snod
->key
);
1146 level
= le16_to_cpu(idx
->level
);
1149 found
= ubifs_tnc_has_node(c
, &snod
->key
, level
, lnum
,
1150 snod
->offs
, is_idx
);
1154 used
+= ALIGN(snod
->len
, 8);
1158 free
= c
->leb_size
- sleb
->endpt
;
1159 dirty
= sleb
->endpt
- used
;
1161 if (free
> c
->leb_size
|| free
< 0 || dirty
> c
->leb_size
||
1163 ubifs_err("bad calculated accounting for LEB %d: "
1164 "free %d, dirty %d", lnum
, free
, dirty
);
1168 if (lp
->free
+ lp
->dirty
== c
->leb_size
&&
1169 free
+ dirty
== c
->leb_size
)
1170 if ((is_idx
&& !(lp
->flags
& LPROPS_INDEX
)) ||
1171 (!is_idx
&& free
== c
->leb_size
) ||
1172 lp
->free
== c
->leb_size
) {
1174 * Empty or freeable LEBs could contain index
1175 * nodes from an uncompleted commit due to an
1176 * unclean unmount. Or they could be empty for
1177 * the same reason. Or it may simply not have been
1185 if (is_idx
&& lp
->free
+ lp
->dirty
== free
+ dirty
&&
1186 lnum
!= c
->ihead_lnum
) {
1188 * After an unclean unmount, an index LEB could have a different
1189 * amount of free space than the value recorded by lprops. That
1190 * is because the in-the-gaps method may use free space or
1191 * create free space (as a side-effect of using ubi_leb_change
1192 * and not writing the whole LEB). The incorrect free space
1193 * value is not a problem because the index is only ever
1194 * allocated empty LEBs, so there will never be an attempt to
1195 * write to the free space at the end of an index LEB - except
1196 * by the in-the-gaps method for which it is not a problem.
1202 if (lp
->free
!= free
|| lp
->dirty
!= dirty
)
1205 if (is_idx
&& !(lp
->flags
& LPROPS_INDEX
)) {
1206 if (free
== c
->leb_size
)
1207 /* Free but not unmapped LEB, it's fine */
1210 ubifs_err("indexing node without indexing "
1216 if (!is_idx
&& (lp
->flags
& LPROPS_INDEX
)) {
1217 ubifs_err("data node with indexing flag");
1221 if (free
== c
->leb_size
)
1222 lst
->empty_lebs
+= 1;
1227 if (!(lp
->flags
& LPROPS_INDEX
))
1228 lst
->total_used
+= c
->leb_size
- free
- dirty
;
1229 lst
->total_free
+= free
;
1230 lst
->total_dirty
+= dirty
;
1232 if (!(lp
->flags
& LPROPS_INDEX
)) {
1233 int spc
= free
+ dirty
;
1235 if (spc
< c
->dead_wm
)
1236 lst
->total_dead
+= spc
;
1238 lst
->total_dark
+= calc_dark(c
, spc
);
1241 ubifs_scan_destroy(sleb
);
1242 return LPT_SCAN_CONTINUE
;
1245 ubifs_err("bad accounting of LEB %d: free %d, dirty %d flags %#x, "
1246 "should be free %d, dirty %d",
1247 lnum
, lp
->free
, lp
->dirty
, lp
->flags
, free
, dirty
);
1248 dbg_dump_leb(c
, lnum
);
1250 ubifs_scan_destroy(sleb
);
1252 data
->err
= -EINVAL
;
1253 return LPT_SCAN_STOP
;
1257 * dbg_check_lprops - check all LEB properties.
1258 * @c: UBIFS file-system description object
1260 * This function checks all LEB properties and makes sure they are all correct.
1261 * It returns zero if everything is fine, %-EINVAL if there is an inconsistency
1262 * and other negative error codes in case of other errors. This function is
1263 * called while the file system is locked (because of commit start), so no
1264 * additional locking is required. Note that locking the LPT mutex would cause
1265 * a circular lock dependency with the TNC mutex.
1267 int dbg_check_lprops(struct ubifs_info
*c
)
1270 struct scan_check_data data
;
1271 struct ubifs_lp_stats
*lst
= &data
.lst
;
1273 if (!(ubifs_chk_flags
& UBIFS_CHK_LPROPS
))
1277 * As we are going to scan the media, the write buffers have to be
1280 for (i
= 0; i
< c
->jhead_cnt
; i
++) {
1281 err
= ubifs_wbuf_sync(&c
->jheads
[i
].wbuf
);
1286 memset(lst
, 0, sizeof(struct ubifs_lp_stats
));
1289 err
= ubifs_lpt_scan_nolock(c
, c
->main_first
, c
->leb_cnt
- 1,
1290 (ubifs_lpt_scan_callback
)scan_check_cb
,
1292 if (err
&& err
!= -ENOSPC
)
1299 if (lst
->empty_lebs
!= c
->lst
.empty_lebs
||
1300 lst
->idx_lebs
!= c
->lst
.idx_lebs
||
1301 lst
->total_free
!= c
->lst
.total_free
||
1302 lst
->total_dirty
!= c
->lst
.total_dirty
||
1303 lst
->total_used
!= c
->lst
.total_used
) {
1304 ubifs_err("bad overall accounting");
1305 ubifs_err("calculated: empty_lebs %d, idx_lebs %d, "
1306 "total_free %lld, total_dirty %lld, total_used %lld",
1307 lst
->empty_lebs
, lst
->idx_lebs
, lst
->total_free
,
1308 lst
->total_dirty
, lst
->total_used
);
1309 ubifs_err("read from lprops: empty_lebs %d, idx_lebs %d, "
1310 "total_free %lld, total_dirty %lld, total_used %lld",
1311 c
->lst
.empty_lebs
, c
->lst
.idx_lebs
, c
->lst
.total_free
,
1312 c
->lst
.total_dirty
, c
->lst
.total_used
);
1317 if (lst
->total_dead
!= c
->lst
.total_dead
||
1318 lst
->total_dark
!= c
->lst
.total_dark
) {
1319 ubifs_err("bad dead/dark space accounting");
1320 ubifs_err("calculated: total_dead %lld, total_dark %lld",
1321 lst
->total_dead
, lst
->total_dark
);
1322 ubifs_err("read from lprops: total_dead %lld, total_dark %lld",
1323 c
->lst
.total_dead
, c
->lst
.total_dark
);
1328 err
= dbg_check_cats(c
);
1333 #endif /* CONFIG_UBIFS_FS_DEBUG */
This page took 0.075026 seconds and 5 git commands to generate.