1308 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * This file is part of UBIFS.4 *5 * Copyright (C) 2006-2008 Nokia Corporation.6 *7 * Authors: Adrian Hunter8 * Artem Bityutskiy (Битюцкий Артём)9 */10 11/*12 * This file implements the functions that access LEB properties and their13 * categories. LEBs are categorized based on the needs of UBIFS, and the14 * categories are stored as either heaps or lists to provide a fast way of15 * finding a LEB in a particular category. For example, UBIFS may need to find16 * an empty LEB for the journal, or a very dirty LEB for garbage collection.17 */18 19#include "ubifs.h"20 21/**22 * get_heap_comp_val - get the LEB properties value for heap comparisons.23 * @lprops: LEB properties24 * @cat: LEB category25 */26static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)27{28 switch (cat) {29 case LPROPS_FREE:30 return lprops->free;31 case LPROPS_DIRTY_IDX:32 return lprops->free + lprops->dirty;33 default:34 return lprops->dirty;35 }36}37 38/**39 * move_up_lpt_heap - move a new heap entry up as far as possible.40 * @c: UBIFS file-system description object41 * @heap: LEB category heap42 * @lprops: LEB properties to move43 * @cat: LEB category44 *45 * New entries to a heap are added at the bottom and then moved up until the46 * parent's value is greater. In the case of LPT's category heaps, the value47 * is either the amount of free space or the amount of dirty space, depending48 * on the category.49 */50static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,51 struct ubifs_lprops *lprops, int cat)52{53 int val1, val2, hpos;54 55 hpos = lprops->hpos;56 if (!hpos)57 return; /* Already top of the heap */58 val1 = get_heap_comp_val(lprops, cat);59 /* Compare to parent and, if greater, move up the heap */60 do {61 int ppos = (hpos - 1) / 2;62 63 val2 = get_heap_comp_val(heap->arr[ppos], cat);64 if (val2 >= val1)65 return;66 /* Greater than parent so move up */67 heap->arr[ppos]->hpos = hpos;68 heap->arr[hpos] = heap->arr[ppos];69 heap->arr[ppos] = lprops;70 lprops->hpos = ppos;71 hpos = ppos;72 } while (hpos);73}74 75/**76 * adjust_lpt_heap - move a changed heap entry up or down the heap.77 * @c: UBIFS file-system description object78 * @heap: LEB category heap79 * @lprops: LEB properties to move80 * @hpos: heap position of @lprops81 * @cat: LEB category82 *83 * Changed entries in a heap are moved up or down until the parent's value is84 * greater. In the case of LPT's category heaps, the value is either the amount85 * of free space or the amount of dirty space, depending on the category.86 */87static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap,88 struct ubifs_lprops *lprops, int hpos, int cat)89{90 int val1, val2, val3, cpos;91 92 val1 = get_heap_comp_val(lprops, cat);93 /* Compare to parent and, if greater than parent, move up the heap */94 if (hpos) {95 int ppos = (hpos - 1) / 2;96 97 val2 = get_heap_comp_val(heap->arr[ppos], cat);98 if (val1 > val2) {99 /* Greater than parent so move up */100 while (1) {101 heap->arr[ppos]->hpos = hpos;102 heap->arr[hpos] = heap->arr[ppos];103 heap->arr[ppos] = lprops;104 lprops->hpos = ppos;105 hpos = ppos;106 if (!hpos)107 return;108 ppos = (hpos - 1) / 2;109 val2 = get_heap_comp_val(heap->arr[ppos], cat);110 if (val1 <= val2)111 return;112 /* Still greater than parent so keep going */113 }114 }115 }116 117 /* Not greater than parent, so compare to children */118 while (1) {119 /* Compare to left child */120 cpos = hpos * 2 + 1;121 if (cpos >= heap->cnt)122 return;123 val2 = get_heap_comp_val(heap->arr[cpos], cat);124 if (val1 < val2) {125 /* Less than left child, so promote biggest child */126 if (cpos + 1 < heap->cnt) {127 val3 = get_heap_comp_val(heap->arr[cpos + 1],128 cat);129 if (val3 > val2)130 cpos += 1; /* Right child is bigger */131 }132 heap->arr[cpos]->hpos = hpos;133 heap->arr[hpos] = heap->arr[cpos];134 heap->arr[cpos] = lprops;135 lprops->hpos = cpos;136 hpos = cpos;137 continue;138 }139 /* Compare to right child */140 cpos += 1;141 if (cpos >= heap->cnt)142 return;143 val3 = get_heap_comp_val(heap->arr[cpos], cat);144 if (val1 < val3) {145 /* Less than right child, so promote right child */146 heap->arr[cpos]->hpos = hpos;147 heap->arr[hpos] = heap->arr[cpos];148 heap->arr[cpos] = lprops;149 lprops->hpos = cpos;150 hpos = cpos;151 continue;152 }153 return;154 }155}156 157/**158 * add_to_lpt_heap - add LEB properties to a LEB category heap.159 * @c: UBIFS file-system description object160 * @lprops: LEB properties to add161 * @cat: LEB category162 *163 * This function returns %1 if @lprops is added to the heap for LEB category164 * @cat, otherwise %0 is returned because the heap is full.165 */166static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,167 int cat)168{169 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];170 171 if (heap->cnt >= heap->max_cnt) {172 const int b = LPT_HEAP_SZ / 2 - 1;173 int cpos, val1, val2;174 175 /* Compare to some other LEB on the bottom of heap */176 /* Pick a position kind of randomly */177 cpos = (((size_t)lprops >> 4) & b) + b;178 ubifs_assert(c, cpos >= b);179 ubifs_assert(c, cpos < LPT_HEAP_SZ);180 ubifs_assert(c, cpos < heap->cnt);181 182 val1 = get_heap_comp_val(lprops, cat);183 val2 = get_heap_comp_val(heap->arr[cpos], cat);184 if (val1 > val2) {185 struct ubifs_lprops *lp;186 187 lp = heap->arr[cpos];188 lp->flags &= ~LPROPS_CAT_MASK;189 lp->flags |= LPROPS_UNCAT;190 list_add(&lp->list, &c->uncat_list);191 lprops->hpos = cpos;192 heap->arr[cpos] = lprops;193 move_up_lpt_heap(c, heap, lprops, cat);194 dbg_check_heap(c, heap, cat, lprops->hpos);195 return 1; /* Added to heap */196 }197 dbg_check_heap(c, heap, cat, -1);198 return 0; /* Not added to heap */199 } else {200 lprops->hpos = heap->cnt++;201 heap->arr[lprops->hpos] = lprops;202 move_up_lpt_heap(c, heap, lprops, cat);203 dbg_check_heap(c, heap, cat, lprops->hpos);204 return 1; /* Added to heap */205 }206}207 208/**209 * remove_from_lpt_heap - remove LEB properties from a LEB category heap.210 * @c: UBIFS file-system description object211 * @lprops: LEB properties to remove212 * @cat: LEB category213 */214static void remove_from_lpt_heap(struct ubifs_info *c,215 struct ubifs_lprops *lprops, int cat)216{217 struct ubifs_lpt_heap *heap;218 int hpos = lprops->hpos;219 220 heap = &c->lpt_heap[cat - 1];221 ubifs_assert(c, hpos >= 0 && hpos < heap->cnt);222 ubifs_assert(c, heap->arr[hpos] == lprops);223 heap->cnt -= 1;224 if (hpos < heap->cnt) {225 heap->arr[hpos] = heap->arr[heap->cnt];226 heap->arr[hpos]->hpos = hpos;227 adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);228 }229 dbg_check_heap(c, heap, cat, -1);230}231 232/**233 * lpt_heap_replace - replace lprops in a category heap.234 * @c: UBIFS file-system description object235 * @new_lprops: LEB properties with which to replace236 * @cat: LEB category237 *238 * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)239 * and the lprops that the pnode contains. When that happens, references in240 * the category heaps to those lprops must be updated to point to the new241 * lprops. This function does that.242 */243static void lpt_heap_replace(struct ubifs_info *c,244 struct ubifs_lprops *new_lprops, int cat)245{246 struct ubifs_lpt_heap *heap;247 int hpos = new_lprops->hpos;248 249 heap = &c->lpt_heap[cat - 1];250 heap->arr[hpos] = new_lprops;251}252 253/**254 * ubifs_add_to_cat - add LEB properties to a category list or heap.255 * @c: UBIFS file-system description object256 * @lprops: LEB properties to add257 * @cat: LEB category to which to add258 *259 * LEB properties are categorized to enable fast find operations.260 */261void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,262 int cat)263{264 switch (cat) {265 case LPROPS_DIRTY:266 case LPROPS_DIRTY_IDX:267 case LPROPS_FREE:268 if (add_to_lpt_heap(c, lprops, cat))269 break;270 /* No more room on heap so make it un-categorized */271 cat = LPROPS_UNCAT;272 fallthrough;273 case LPROPS_UNCAT:274 list_add(&lprops->list, &c->uncat_list);275 break;276 case LPROPS_EMPTY:277 list_add(&lprops->list, &c->empty_list);278 break;279 case LPROPS_FREEABLE:280 list_add(&lprops->list, &c->freeable_list);281 c->freeable_cnt += 1;282 break;283 case LPROPS_FRDI_IDX:284 list_add(&lprops->list, &c->frdi_idx_list);285 break;286 default:287 ubifs_assert(c, 0);288 }289 290 lprops->flags &= ~LPROPS_CAT_MASK;291 lprops->flags |= cat;292 c->in_a_category_cnt += 1;293 ubifs_assert(c, c->in_a_category_cnt <= c->main_lebs);294}295 296/**297 * ubifs_remove_from_cat - remove LEB properties from a category list or heap.298 * @c: UBIFS file-system description object299 * @lprops: LEB properties to remove300 * @cat: LEB category from which to remove301 *302 * LEB properties are categorized to enable fast find operations.303 */304static void ubifs_remove_from_cat(struct ubifs_info *c,305 struct ubifs_lprops *lprops, int cat)306{307 switch (cat) {308 case LPROPS_DIRTY:309 case LPROPS_DIRTY_IDX:310 case LPROPS_FREE:311 remove_from_lpt_heap(c, lprops, cat);312 break;313 case LPROPS_FREEABLE:314 c->freeable_cnt -= 1;315 ubifs_assert(c, c->freeable_cnt >= 0);316 fallthrough;317 case LPROPS_UNCAT:318 case LPROPS_EMPTY:319 case LPROPS_FRDI_IDX:320 ubifs_assert(c, !list_empty(&lprops->list));321 list_del(&lprops->list);322 break;323 default:324 ubifs_assert(c, 0);325 }326 327 c->in_a_category_cnt -= 1;328 ubifs_assert(c, c->in_a_category_cnt >= 0);329}330 331/**332 * ubifs_replace_cat - replace lprops in a category list or heap.333 * @c: UBIFS file-system description object334 * @old_lprops: LEB properties to replace335 * @new_lprops: LEB properties with which to replace336 *337 * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)338 * and the lprops that the pnode contains. When that happens, references in339 * category lists and heaps must be replaced. This function does that.340 */341void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,342 struct ubifs_lprops *new_lprops)343{344 int cat;345 346 cat = new_lprops->flags & LPROPS_CAT_MASK;347 switch (cat) {348 case LPROPS_DIRTY:349 case LPROPS_DIRTY_IDX:350 case LPROPS_FREE:351 lpt_heap_replace(c, new_lprops, cat);352 break;353 case LPROPS_UNCAT:354 case LPROPS_EMPTY:355 case LPROPS_FREEABLE:356 case LPROPS_FRDI_IDX:357 list_replace(&old_lprops->list, &new_lprops->list);358 break;359 default:360 ubifs_assert(c, 0);361 }362}363 364/**365 * ubifs_ensure_cat - ensure LEB properties are categorized.366 * @c: UBIFS file-system description object367 * @lprops: LEB properties368 *369 * A LEB may have fallen off of the bottom of a heap, and ended up as370 * un-categorized even though it has enough space for us now. If that is the371 * case this function will put the LEB back onto a heap.372 */373void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)374{375 int cat = lprops->flags & LPROPS_CAT_MASK;376 377 if (cat != LPROPS_UNCAT)378 return;379 cat = ubifs_categorize_lprops(c, lprops);380 if (cat == LPROPS_UNCAT)381 return;382 ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);383 ubifs_add_to_cat(c, lprops, cat);384}385 386/**387 * ubifs_categorize_lprops - categorize LEB properties.388 * @c: UBIFS file-system description object389 * @lprops: LEB properties to categorize390 *391 * LEB properties are categorized to enable fast find operations. This function392 * returns the LEB category to which the LEB properties belong. Note however393 * that if the LEB category is stored as a heap and the heap is full, the394 * LEB properties may have their category changed to %LPROPS_UNCAT.395 */396int ubifs_categorize_lprops(const struct ubifs_info *c,397 const struct ubifs_lprops *lprops)398{399 if (lprops->flags & LPROPS_TAKEN)400 return LPROPS_UNCAT;401 402 if (lprops->free == c->leb_size) {403 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));404 return LPROPS_EMPTY;405 }406 407 if (lprops->free + lprops->dirty == c->leb_size) {408 if (lprops->flags & LPROPS_INDEX)409 return LPROPS_FRDI_IDX;410 else411 return LPROPS_FREEABLE;412 }413 414 if (lprops->flags & LPROPS_INDEX) {415 if (lprops->dirty + lprops->free >= c->min_idx_node_sz)416 return LPROPS_DIRTY_IDX;417 } else {418 if (lprops->dirty >= c->dead_wm &&419 lprops->dirty > lprops->free)420 return LPROPS_DIRTY;421 if (lprops->free > 0)422 return LPROPS_FREE;423 }424 425 return LPROPS_UNCAT;426}427 428/**429 * change_category - change LEB properties category.430 * @c: UBIFS file-system description object431 * @lprops: LEB properties to re-categorize432 *433 * LEB properties are categorized to enable fast find operations. When the LEB434 * properties change they must be re-categorized.435 */436static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)437{438 int old_cat = lprops->flags & LPROPS_CAT_MASK;439 int new_cat = ubifs_categorize_lprops(c, lprops);440 441 if (old_cat == new_cat) {442 struct ubifs_lpt_heap *heap;443 444 /* lprops on a heap now must be moved up or down */445 if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT)446 return; /* Not on a heap */447 heap = &c->lpt_heap[new_cat - 1];448 adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);449 } else {450 ubifs_remove_from_cat(c, lprops, old_cat);451 ubifs_add_to_cat(c, lprops, new_cat);452 }453}454 455/**456 * ubifs_calc_dark - calculate LEB dark space size.457 * @c: the UBIFS file-system description object458 * @spc: amount of free and dirty space in the LEB459 *460 * This function calculates and returns amount of dark space in an LEB which461 * has @spc bytes of free and dirty space.462 *463 * UBIFS is trying to account the space which might not be usable, and this464 * space is called "dark space". For example, if an LEB has only %512 free465 * bytes, it is dark space, because it cannot fit a large data node.466 */467int ubifs_calc_dark(const struct ubifs_info *c, int spc)468{469 ubifs_assert(c, !(spc & 7));470 471 if (spc < c->dark_wm)472 return spc;473 474 /*475 * If we have slightly more space then the dark space watermark, we can476 * anyway safely assume it we'll be able to write a node of the477 * smallest size there.478 */479 if (spc - c->dark_wm < MIN_WRITE_SZ)480 return spc - MIN_WRITE_SZ;481 482 return c->dark_wm;483}484 485/**486 * is_lprops_dirty - determine if LEB properties are dirty.487 * @c: the UBIFS file-system description object488 * @lprops: LEB properties to test489 */490static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)491{492 struct ubifs_pnode *pnode;493 int pos;494 495 pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);496 pnode = (struct ubifs_pnode *)container_of(lprops - pos,497 struct ubifs_pnode,498 lprops[0]);499 return !test_bit(COW_CNODE, &pnode->flags) &&500 test_bit(DIRTY_CNODE, &pnode->flags);501}502 503/**504 * ubifs_change_lp - change LEB properties.505 * @c: the UBIFS file-system description object506 * @lp: LEB properties to change507 * @free: new free space amount508 * @dirty: new dirty space amount509 * @flags: new flags510 * @idx_gc_cnt: change to the count of @idx_gc list511 *512 * This function changes LEB properties (@free, @dirty or @flag). However, the513 * property which has the %LPROPS_NC value is not changed. Returns a pointer to514 * the updated LEB properties on success and a negative error code on failure.515 *516 * Note, the LEB properties may have had to be copied (due to COW) and517 * consequently the pointer returned may not be the same as the pointer518 * passed.519 */520const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,521 const struct ubifs_lprops *lp,522 int free, int dirty, int flags,523 int idx_gc_cnt)524{525 /*526 * This is the only function that is allowed to change lprops, so we527 * discard the "const" qualifier.528 */529 struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp;530 531 dbg_lp("LEB %d, free %d, dirty %d, flags %d",532 lprops->lnum, free, dirty, flags);533 534 ubifs_assert(c, mutex_is_locked(&c->lp_mutex));535 ubifs_assert(c, c->lst.empty_lebs >= 0 &&536 c->lst.empty_lebs <= c->main_lebs);537 ubifs_assert(c, c->freeable_cnt >= 0);538 ubifs_assert(c, c->freeable_cnt <= c->main_lebs);539 ubifs_assert(c, c->lst.taken_empty_lebs >= 0);540 ubifs_assert(c, c->lst.taken_empty_lebs <= c->lst.empty_lebs);541 ubifs_assert(c, !(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));542 ubifs_assert(c, !(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));543 ubifs_assert(c, !(c->lst.total_used & 7));544 ubifs_assert(c, free == LPROPS_NC || free >= 0);545 ubifs_assert(c, dirty == LPROPS_NC || dirty >= 0);546 547 if (!is_lprops_dirty(c, lprops)) {548 lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);549 if (IS_ERR(lprops))550 return lprops;551 } else552 ubifs_assert(c, lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));553 554 ubifs_assert(c, !(lprops->free & 7) && !(lprops->dirty & 7));555 556 spin_lock(&c->space_lock);557 if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)558 c->lst.taken_empty_lebs -= 1;559 560 if (!(lprops->flags & LPROPS_INDEX)) {561 int old_spc;562 563 old_spc = lprops->free + lprops->dirty;564 if (old_spc < c->dead_wm)565 c->lst.total_dead -= old_spc;566 else567 c->lst.total_dark -= ubifs_calc_dark(c, old_spc);568 569 c->lst.total_used -= c->leb_size - old_spc;570 }571 572 if (free != LPROPS_NC) {573 free = ALIGN(free, 8);574 c->lst.total_free += free - lprops->free;575 576 /* Increase or decrease empty LEBs counter if needed */577 if (free == c->leb_size) {578 if (lprops->free != c->leb_size)579 c->lst.empty_lebs += 1;580 } else if (lprops->free == c->leb_size)581 c->lst.empty_lebs -= 1;582 lprops->free = free;583 }584 585 if (dirty != LPROPS_NC) {586 dirty = ALIGN(dirty, 8);587 c->lst.total_dirty += dirty - lprops->dirty;588 lprops->dirty = dirty;589 }590 591 if (flags != LPROPS_NC) {592 /* Take care about indexing LEBs counter if needed */593 if ((lprops->flags & LPROPS_INDEX)) {594 if (!(flags & LPROPS_INDEX))595 c->lst.idx_lebs -= 1;596 } else if (flags & LPROPS_INDEX)597 c->lst.idx_lebs += 1;598 lprops->flags = flags;599 }600 601 if (!(lprops->flags & LPROPS_INDEX)) {602 int new_spc;603 604 new_spc = lprops->free + lprops->dirty;605 if (new_spc < c->dead_wm)606 c->lst.total_dead += new_spc;607 else608 c->lst.total_dark += ubifs_calc_dark(c, new_spc);609 610 c->lst.total_used += c->leb_size - new_spc;611 }612 613 if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)614 c->lst.taken_empty_lebs += 1;615 616 change_category(c, lprops);617 c->idx_gc_cnt += idx_gc_cnt;618 spin_unlock(&c->space_lock);619 return lprops;620}621 622/**623 * ubifs_get_lp_stats - get lprops statistics.624 * @c: UBIFS file-system description object625 * @lst: return statistics626 */627void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst)628{629 spin_lock(&c->space_lock);630 memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats));631 spin_unlock(&c->space_lock);632}633 634/**635 * ubifs_change_one_lp - change LEB properties.636 * @c: the UBIFS file-system description object637 * @lnum: LEB to change properties for638 * @free: amount of free space639 * @dirty: amount of dirty space640 * @flags_set: flags to set641 * @flags_clean: flags to clean642 * @idx_gc_cnt: change to the count of idx_gc list643 *644 * This function changes properties of LEB @lnum. It is a helper wrapper over645 * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the646 * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and647 * a negative error code in case of failure.648 */649int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,650 int flags_set, int flags_clean, int idx_gc_cnt)651{652 int err = 0, flags;653 const struct ubifs_lprops *lp;654 655 ubifs_get_lprops(c);656 657 lp = ubifs_lpt_lookup_dirty(c, lnum);658 if (IS_ERR(lp)) {659 err = PTR_ERR(lp);660 goto out;661 }662 663 flags = (lp->flags | flags_set) & ~flags_clean;664 lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);665 if (IS_ERR(lp))666 err = PTR_ERR(lp);667 668out:669 ubifs_release_lprops(c);670 if (err)671 ubifs_err(c, "cannot change properties of LEB %d, error %d",672 lnum, err);673 return err;674}675 676/**677 * ubifs_update_one_lp - update LEB properties.678 * @c: the UBIFS file-system description object679 * @lnum: LEB to change properties for680 * @free: amount of free space681 * @dirty: amount of dirty space to add682 * @flags_set: flags to set683 * @flags_clean: flags to clean684 *685 * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to686 * current dirty space, not substitutes it.687 */688int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,689 int flags_set, int flags_clean)690{691 int err = 0, flags;692 const struct ubifs_lprops *lp;693 694 ubifs_get_lprops(c);695 696 lp = ubifs_lpt_lookup_dirty(c, lnum);697 if (IS_ERR(lp)) {698 err = PTR_ERR(lp);699 goto out;700 }701 702 flags = (lp->flags | flags_set) & ~flags_clean;703 lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);704 if (IS_ERR(lp))705 err = PTR_ERR(lp);706 707out:708 ubifs_release_lprops(c);709 if (err)710 ubifs_err(c, "cannot update properties of LEB %d, error %d",711 lnum, err);712 return err;713}714 715/**716 * ubifs_read_one_lp - read LEB properties.717 * @c: the UBIFS file-system description object718 * @lnum: LEB to read properties for719 * @lp: where to store read properties720 *721 * This helper function reads properties of a LEB @lnum and stores them in @lp.722 * Returns zero in case of success and a negative error code in case of723 * failure.724 */725int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)726{727 int err = 0;728 const struct ubifs_lprops *lpp;729 730 ubifs_get_lprops(c);731 732 lpp = ubifs_lpt_lookup(c, lnum);733 if (IS_ERR(lpp)) {734 err = PTR_ERR(lpp);735 ubifs_err(c, "cannot read properties of LEB %d, error %d",736 lnum, err);737 goto out;738 }739 740 memcpy(lp, lpp, sizeof(struct ubifs_lprops));741 742out:743 ubifs_release_lprops(c);744 return err;745}746 747/**748 * ubifs_fast_find_free - try to find a LEB with free space quickly.749 * @c: the UBIFS file-system description object750 *751 * This function returns LEB properties for a LEB with free space or %NULL if752 * the function is unable to find a LEB quickly.753 */754const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)755{756 struct ubifs_lprops *lprops;757 struct ubifs_lpt_heap *heap;758 759 ubifs_assert(c, mutex_is_locked(&c->lp_mutex));760 761 heap = &c->lpt_heap[LPROPS_FREE - 1];762 if (heap->cnt == 0)763 return NULL;764 765 lprops = heap->arr[0];766 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));767 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));768 return lprops;769}770 771/**772 * ubifs_fast_find_empty - try to find an empty LEB quickly.773 * @c: the UBIFS file-system description object774 *775 * This function returns LEB properties for an empty LEB or %NULL if the776 * function is unable to find an empty LEB quickly.777 */778const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)779{780 struct ubifs_lprops *lprops;781 782 ubifs_assert(c, mutex_is_locked(&c->lp_mutex));783 784 if (list_empty(&c->empty_list))785 return NULL;786 787 lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);788 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));789 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));790 ubifs_assert(c, lprops->free == c->leb_size);791 return lprops;792}793 794/**795 * ubifs_fast_find_freeable - try to find a freeable LEB quickly.796 * @c: the UBIFS file-system description object797 *798 * This function returns LEB properties for a freeable LEB or %NULL if the799 * function is unable to find a freeable LEB quickly.800 */801const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)802{803 struct ubifs_lprops *lprops;804 805 ubifs_assert(c, mutex_is_locked(&c->lp_mutex));806 807 if (list_empty(&c->freeable_list))808 return NULL;809 810 lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);811 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));812 ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));813 ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);814 ubifs_assert(c, c->freeable_cnt > 0);815 return lprops;816}817 818/**819 * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.820 * @c: the UBIFS file-system description object821 *822 * This function returns LEB properties for a freeable index LEB or %NULL if the823 * function is unable to find a freeable index LEB quickly.824 */825const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)826{827 struct ubifs_lprops *lprops;828 829 ubifs_assert(c, mutex_is_locked(&c->lp_mutex));830 831 if (list_empty(&c->frdi_idx_list))832 return NULL;833 834 lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);835 ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));836 ubifs_assert(c, (lprops->flags & LPROPS_INDEX));837 ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);838 return lprops;839}840 841/*842 * Everything below is related to debugging.843 */844 845/**846 * dbg_check_cats - check category heaps and lists.847 * @c: UBIFS file-system description object848 *849 * This function returns %0 on success and a negative error code on failure.850 */851int dbg_check_cats(struct ubifs_info *c)852{853 struct ubifs_lprops *lprops;854 struct list_head *pos;855 int i, cat;856 857 if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))858 return 0;859 860 list_for_each_entry(lprops, &c->empty_list, list) {861 if (lprops->free != c->leb_size) {862 ubifs_err(c, "non-empty LEB %d on empty list (free %d dirty %d flags %d)",863 lprops->lnum, lprops->free, lprops->dirty,864 lprops->flags);865 return -EINVAL;866 }867 if (lprops->flags & LPROPS_TAKEN) {868 ubifs_err(c, "taken LEB %d on empty list (free %d dirty %d flags %d)",869 lprops->lnum, lprops->free, lprops->dirty,870 lprops->flags);871 return -EINVAL;872 }873 }874 875 i = 0;876 list_for_each_entry(lprops, &c->freeable_list, list) {877 if (lprops->free + lprops->dirty != c->leb_size) {878 ubifs_err(c, "non-freeable LEB %d on freeable list (free %d dirty %d flags %d)",879 lprops->lnum, lprops->free, lprops->dirty,880 lprops->flags);881 return -EINVAL;882 }883 if (lprops->flags & LPROPS_TAKEN) {884 ubifs_err(c, "taken LEB %d on freeable list (free %d dirty %d flags %d)",885 lprops->lnum, lprops->free, lprops->dirty,886 lprops->flags);887 return -EINVAL;888 }889 i += 1;890 }891 if (i != c->freeable_cnt) {892 ubifs_err(c, "freeable list count %d expected %d", i,893 c->freeable_cnt);894 return -EINVAL;895 }896 897 i = 0;898 list_for_each(pos, &c->idx_gc)899 i += 1;900 if (i != c->idx_gc_cnt) {901 ubifs_err(c, "idx_gc list count %d expected %d", i,902 c->idx_gc_cnt);903 return -EINVAL;904 }905 906 list_for_each_entry(lprops, &c->frdi_idx_list, list) {907 if (lprops->free + lprops->dirty != c->leb_size) {908 ubifs_err(c, "non-freeable LEB %d on frdi_idx list (free %d dirty %d flags %d)",909 lprops->lnum, lprops->free, lprops->dirty,910 lprops->flags);911 return -EINVAL;912 }913 if (lprops->flags & LPROPS_TAKEN) {914 ubifs_err(c, "taken LEB %d on frdi_idx list (free %d dirty %d flags %d)",915 lprops->lnum, lprops->free, lprops->dirty,916 lprops->flags);917 return -EINVAL;918 }919 if (!(lprops->flags & LPROPS_INDEX)) {920 ubifs_err(c, "non-index LEB %d on frdi_idx list (free %d dirty %d flags %d)",921 lprops->lnum, lprops->free, lprops->dirty,922 lprops->flags);923 return -EINVAL;924 }925 }926 927 for (cat = 1; cat <= LPROPS_HEAP_CNT; cat++) {928 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];929 930 for (i = 0; i < heap->cnt; i++) {931 lprops = heap->arr[i];932 if (!lprops) {933 ubifs_err(c, "null ptr in LPT heap cat %d", cat);934 return -EINVAL;935 }936 if (lprops->hpos != i) {937 ubifs_err(c, "bad ptr in LPT heap cat %d", cat);938 return -EINVAL;939 }940 if (lprops->flags & LPROPS_TAKEN) {941 ubifs_err(c, "taken LEB in LPT heap cat %d", cat);942 return -EINVAL;943 }944 }945 }946 947 return 0;948}949 950void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat,951 int add_pos)952{953 int i = 0, j, err = 0;954 955 if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c))956 return;957 958 for (i = 0; i < heap->cnt; i++) {959 struct ubifs_lprops *lprops = heap->arr[i];960 struct ubifs_lprops *lp;961 962 if (i != add_pos)963 if ((lprops->flags & LPROPS_CAT_MASK) != cat) {964 err = 1;965 goto out;966 }967 if (lprops->hpos != i) {968 err = 2;969 goto out;970 }971 lp = ubifs_lpt_lookup(c, lprops->lnum);972 if (IS_ERR(lp)) {973 err = 3;974 goto out;975 }976 if (lprops != lp) {977 ubifs_err(c, "lprops %zx lp %zx lprops->lnum %d lp->lnum %d",978 (size_t)lprops, (size_t)lp, lprops->lnum,979 lp->lnum);980 err = 4;981 goto out;982 }983 for (j = 0; j < i; j++) {984 lp = heap->arr[j];985 if (lp == lprops) {986 err = 5;987 goto out;988 }989 if (lp->lnum == lprops->lnum) {990 err = 6;991 goto out;992 }993 }994 }995out:996 if (err) {997 ubifs_err(c, "failed cat %d hpos %d err %d", cat, i, err);998 dump_stack();999 ubifs_dump_heap(c, heap, cat);1000 }1001}1002 1003/**1004 * scan_check_cb - scan callback.1005 * @c: the UBIFS file-system description object1006 * @lp: LEB properties to scan1007 * @in_tree: whether the LEB properties are in main memory1008 * @arg: lprops statistics to update1009 *1010 * This function returns a code that indicates whether the scan should continue1011 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree1012 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop1013 * (%LPT_SCAN_STOP).1014 */1015static int scan_check_cb(struct ubifs_info *c,1016 const struct ubifs_lprops *lp, int in_tree,1017 void *arg)1018{1019 struct ubifs_lp_stats *lst = arg;1020 struct ubifs_scan_leb *sleb;1021 struct ubifs_scan_node *snod;1022 int cat, lnum = lp->lnum, is_idx = 0, used = 0, free, dirty, ret;1023 void *buf = NULL;1024 1025 cat = lp->flags & LPROPS_CAT_MASK;1026 if (cat != LPROPS_UNCAT) {1027 cat = ubifs_categorize_lprops(c, lp);1028 if (cat != (lp->flags & LPROPS_CAT_MASK)) {1029 ubifs_err(c, "bad LEB category %d expected %d",1030 (lp->flags & LPROPS_CAT_MASK), cat);1031 return -EINVAL;1032 }1033 }1034 1035 /* Check lp is on its category list (if it has one) */1036 if (in_tree) {1037 struct list_head *list = NULL;1038 1039 switch (cat) {1040 case LPROPS_EMPTY:1041 list = &c->empty_list;1042 break;1043 case LPROPS_FREEABLE:1044 list = &c->freeable_list;1045 break;1046 case LPROPS_FRDI_IDX:1047 list = &c->frdi_idx_list;1048 break;1049 case LPROPS_UNCAT:1050 list = &c->uncat_list;1051 break;1052 }1053 if (list) {1054 struct ubifs_lprops *lprops;1055 int found = 0;1056 1057 list_for_each_entry(lprops, list, list) {1058 if (lprops == lp) {1059 found = 1;1060 break;1061 }1062 }1063 if (!found) {1064 ubifs_err(c, "bad LPT list (category %d)", cat);1065 return -EINVAL;1066 }1067 }1068 }1069 1070 /* Check lp is on its category heap (if it has one) */1071 if (in_tree && cat > 0 && cat <= LPROPS_HEAP_CNT) {1072 struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];1073 1074 if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) ||1075 lp != heap->arr[lp->hpos]) {1076 ubifs_err(c, "bad LPT heap (category %d)", cat);1077 return -EINVAL;1078 }1079 }1080 1081 /*1082 * After an unclean unmount, empty and freeable LEBs1083 * may contain garbage - do not scan them.1084 */1085 if (lp->free == c->leb_size) {1086 lst->empty_lebs += 1;1087 lst->total_free += c->leb_size;1088 lst->total_dark += ubifs_calc_dark(c, c->leb_size);1089 return LPT_SCAN_CONTINUE;1090 }1091 if (lp->free + lp->dirty == c->leb_size &&1092 !(lp->flags & LPROPS_INDEX)) {1093 lst->total_free += lp->free;1094 lst->total_dirty += lp->dirty;1095 lst->total_dark += ubifs_calc_dark(c, c->leb_size);1096 return LPT_SCAN_CONTINUE;1097 }1098 1099 buf = __vmalloc(c->leb_size, GFP_NOFS);1100 if (!buf)1101 return -ENOMEM;1102 1103 sleb = ubifs_scan(c, lnum, 0, buf, 0);1104 if (IS_ERR(sleb)) {1105 ret = PTR_ERR(sleb);1106 if (ret == -EUCLEAN) {1107 ubifs_dump_lprops(c);1108 ubifs_dump_budg(c, &c->bi);1109 }1110 goto out;1111 }1112 1113 is_idx = -1;1114 list_for_each_entry(snod, &sleb->nodes, list) {1115 int found, level = 0;1116 1117 cond_resched();1118 1119 if (is_idx == -1)1120 is_idx = (snod->type == UBIFS_IDX_NODE) ? 1 : 0;1121 1122 if (is_idx && snod->type != UBIFS_IDX_NODE) {1123 ubifs_err(c, "indexing node in data LEB %d:%d",1124 lnum, snod->offs);1125 goto out_destroy;1126 }1127 1128 if (snod->type == UBIFS_IDX_NODE) {1129 struct ubifs_idx_node *idx = snod->node;1130 1131 key_read(c, ubifs_idx_key(c, idx), &snod->key);1132 level = le16_to_cpu(idx->level);1133 }1134 1135 found = ubifs_tnc_has_node(c, &snod->key, level, lnum,1136 snod->offs, is_idx);1137 if (found) {1138 if (found < 0)1139 goto out_destroy;1140 used += ALIGN(snod->len, 8);1141 }1142 }1143 1144 free = c->leb_size - sleb->endpt;1145 dirty = sleb->endpt - used;1146 1147 if (free > c->leb_size || free < 0 || dirty > c->leb_size ||1148 dirty < 0) {1149 ubifs_err(c, "bad calculated accounting for LEB %d: free %d, dirty %d",1150 lnum, free, dirty);1151 goto out_destroy;1152 }1153 1154 if (lp->free + lp->dirty == c->leb_size &&1155 free + dirty == c->leb_size)1156 if ((is_idx && !(lp->flags & LPROPS_INDEX)) ||1157 (!is_idx && free == c->leb_size) ||1158 lp->free == c->leb_size) {1159 /*1160 * Empty or freeable LEBs could contain index1161 * nodes from an uncompleted commit due to an1162 * unclean unmount. Or they could be empty for1163 * the same reason. Or it may simply not have been1164 * unmapped.1165 */1166 free = lp->free;1167 dirty = lp->dirty;1168 is_idx = 0;1169 }1170 1171 if (is_idx && lp->free + lp->dirty == free + dirty &&1172 lnum != c->ihead_lnum) {1173 /*1174 * After an unclean unmount, an index LEB could have a different1175 * amount of free space than the value recorded by lprops. That1176 * is because the in-the-gaps method may use free space or1177 * create free space (as a side-effect of using ubi_leb_change1178 * and not writing the whole LEB). The incorrect free space1179 * value is not a problem because the index is only ever1180 * allocated empty LEBs, so there will never be an attempt to1181 * write to the free space at the end of an index LEB - except1182 * by the in-the-gaps method for which it is not a problem.1183 */1184 free = lp->free;1185 dirty = lp->dirty;1186 }1187 1188 if (lp->free != free || lp->dirty != dirty)1189 goto out_print;1190 1191 if (is_idx && !(lp->flags & LPROPS_INDEX)) {1192 if (free == c->leb_size)1193 /* Free but not unmapped LEB, it's fine */1194 is_idx = 0;1195 else {1196 ubifs_err(c, "indexing node without indexing flag");1197 goto out_print;1198 }1199 }1200 1201 if (!is_idx && (lp->flags & LPROPS_INDEX)) {1202 ubifs_err(c, "data node with indexing flag");1203 goto out_print;1204 }1205 1206 if (free == c->leb_size)1207 lst->empty_lebs += 1;1208 1209 if (is_idx)1210 lst->idx_lebs += 1;1211 1212 if (!(lp->flags & LPROPS_INDEX))1213 lst->total_used += c->leb_size - free - dirty;1214 lst->total_free += free;1215 lst->total_dirty += dirty;1216 1217 if (!(lp->flags & LPROPS_INDEX)) {1218 int spc = free + dirty;1219 1220 if (spc < c->dead_wm)1221 lst->total_dead += spc;1222 else1223 lst->total_dark += ubifs_calc_dark(c, spc);1224 }1225 1226 ubifs_scan_destroy(sleb);1227 vfree(buf);1228 return LPT_SCAN_CONTINUE;1229 1230out_print:1231 ubifs_err(c, "bad accounting of LEB %d: free %d, dirty %d flags %#x, should be free %d, dirty %d",1232 lnum, lp->free, lp->dirty, lp->flags, free, dirty);1233 ubifs_dump_leb(c, lnum);1234out_destroy:1235 ubifs_scan_destroy(sleb);1236 ret = -EINVAL;1237out:1238 vfree(buf);1239 return ret;1240}1241 1242/**1243 * dbg_check_lprops - check all LEB properties.1244 * @c: UBIFS file-system description object1245 *1246 * This function checks all LEB properties and makes sure they are all correct.1247 * It returns zero if everything is fine, %-EINVAL if there is an inconsistency1248 * and other negative error codes in case of other errors. This function is1249 * called while the file system is locked (because of commit start), so no1250 * additional locking is required. Note that locking the LPT mutex would cause1251 * a circular lock dependency with the TNC mutex.1252 */1253int dbg_check_lprops(struct ubifs_info *c)1254{1255 int i, err;1256 struct ubifs_lp_stats lst;1257 1258 if (!dbg_is_chk_lprops(c))1259 return 0;1260 1261 /*1262 * As we are going to scan the media, the write buffers have to be1263 * synchronized.1264 */1265 for (i = 0; i < c->jhead_cnt; i++) {1266 err = ubifs_wbuf_sync(&c->jheads[i].wbuf);1267 if (err)1268 return err;1269 }1270 1271 memset(&lst, 0, sizeof(struct ubifs_lp_stats));1272 err = ubifs_lpt_scan_nolock(c, c->main_first, c->leb_cnt - 1,1273 scan_check_cb, &lst);1274 if (err && err != -ENOSPC)1275 goto out;1276 1277 if (lst.empty_lebs != c->lst.empty_lebs ||1278 lst.idx_lebs != c->lst.idx_lebs ||1279 lst.total_free != c->lst.total_free ||1280 lst.total_dirty != c->lst.total_dirty ||1281 lst.total_used != c->lst.total_used) {1282 ubifs_err(c, "bad overall accounting");1283 ubifs_err(c, "calculated: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",1284 lst.empty_lebs, lst.idx_lebs, lst.total_free,1285 lst.total_dirty, lst.total_used);1286 ubifs_err(c, "read from lprops: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld",1287 c->lst.empty_lebs, c->lst.idx_lebs, c->lst.total_free,1288 c->lst.total_dirty, c->lst.total_used);1289 err = -EINVAL;1290 goto out;1291 }1292 1293 if (lst.total_dead != c->lst.total_dead ||1294 lst.total_dark != c->lst.total_dark) {1295 ubifs_err(c, "bad dead/dark space accounting");1296 ubifs_err(c, "calculated: total_dead %lld, total_dark %lld",1297 lst.total_dead, lst.total_dark);1298 ubifs_err(c, "read from lprops: total_dead %lld, total_dark %lld",1299 c->lst.total_dead, c->lst.total_dark);1300 err = -EINVAL;1301 goto out;1302 }1303 1304 err = dbg_check_cats(c);1305out:1306 return err;1307}1308