Lines Matching +full:- +full:c
4 * Copyright (C) 2006-2008 Nokia Corporation.
6 * SPDX-License-Identifier: GPL-2.0+
13 * This file implements the budgeting sub-system which is responsible for UBIFS
46 * shrink_liability - write-back some dirty pages/inodes.
47 * @c: UBIFS file-system description object
48 * @nr_to_write: how many dirty pages to write-back
54 * (@i_mutex) by the caller of the budgeting function, because write-back does
57 static void shrink_liability(struct ubifs_info *c, int nr_to_write) in shrink_liability() argument
59 down_read(&c->vfs_sb->s_umount); in shrink_liability()
60 writeback_inodes_sb(c->vfs_sb, WB_REASON_FS_FREE_SPACE); in shrink_liability()
61 up_read(&c->vfs_sb->s_umount); in shrink_liability()
65 * run_gc - run garbage collector.
66 * @c: UBIFS file-system description object
69 * zero if a free LEB has been produced, %-EAGAIN if commit is required, and a
72 static int run_gc(struct ubifs_info *c) in run_gc() argument
76 /* Make some free space by garbage-collecting dirty space */ in run_gc()
77 down_read(&c->commit_sem); in run_gc()
78 lnum = ubifs_garbage_collect(c, 1); in run_gc()
79 up_read(&c->commit_sem); in run_gc()
85 err = ubifs_return_leb(c, lnum); in run_gc()
92 * get_liability - calculate current liability.
93 * @c: UBIFS file-system description object
98 static long long get_liability(struct ubifs_info *c) in get_liability() argument
102 spin_lock(&c->space_lock); in get_liability()
103 liab = c->bi.idx_growth + c->bi.data_growth + c->bi.dd_growth; in get_liability()
104 spin_unlock(&c->space_lock); in get_liability()
109 * make_free_space - make more free space on the file-system.
110 * @c: UBIFS file-system description object
115 * needed, so shrinking the liability is one way to make free space - the
121 * So this function tries to do the above. Returns %-EAGAIN if some free space
122 * was presumably made and the caller has to re-try budgeting the operation.
123 * Returns %-ENOSPC if it couldn't do more free space, and other negative error
126 static int make_free_space(struct ubifs_info *c) in make_free_space() argument
132 liab1 = get_liability(c); in make_free_space()
137 dbg_budg("liability %lld, run write-back", liab1); in make_free_space()
138 shrink_liability(c, NR_TO_WRITE); in make_free_space()
140 liab2 = get_liability(c); in make_free_space()
142 return -EAGAIN; in make_free_space()
148 err = run_gc(c); in make_free_space()
150 return -EAGAIN; in make_free_space()
152 if (err != -EAGAIN && err != -ENOSPC) in make_free_space()
157 err = ubifs_run_commit(c); in make_free_space()
162 return -ENOSPC; in make_free_space()
167 * ubifs_calc_min_idx_lebs - calculate amount of LEBs for the index.
168 * @c: UBIFS file-system description object
173 int ubifs_calc_min_idx_lebs(struct ubifs_info *c) in ubifs_calc_min_idx_lebs() argument
178 idx_size = c->bi.old_idx_sz + c->bi.idx_growth + c->bi.uncommitted_idx; in ubifs_calc_min_idx_lebs()
184 * have to do this costly 64-bit division on fast-path. in ubifs_calc_min_idx_lebs()
186 idx_lebs = div_u64(idx_size + c->idx_leb_size - 1, c->idx_leb_size); in ubifs_calc_min_idx_lebs()
188 * The index head is not available for the in-the-gaps method, so add an in ubifs_calc_min_idx_lebs()
199 * ubifs_calc_available - calculate available FS space.
200 * @c: UBIFS file-system description object
205 long long ubifs_calc_available(const struct ubifs_info *c, int min_idx_lebs) in ubifs_calc_available() argument
210 available = c->main_bytes - c->lst.total_used; in ubifs_calc_available()
227 subtract_lebs += c->jhead_cnt - 1; in ubifs_calc_available()
232 available -= (long long)subtract_lebs * c->leb_size; in ubifs_calc_available()
235 available -= c->lst.total_dead; in ubifs_calc_available()
238 * Subtract dark space, which might or might not be usable - it depends in ubifs_calc_available()
240 * this is a lot of uncompressed or not-compressible data, the dark in ubifs_calc_available()
243 available -= c->lst.total_dark; in ubifs_calc_available()
251 if (c->lst.idx_lebs > min_idx_lebs) { in ubifs_calc_available()
252 subtract_lebs = c->lst.idx_lebs - min_idx_lebs; in ubifs_calc_available()
253 available -= subtract_lebs * c->dark_wm; in ubifs_calc_available()
261 * can_use_rp - check whether the user is allowed to use reserved pool.
262 * @c: UBIFS file-system description object
264 * UBIFS has so-called "reserved pool" which is flash space reserved
269 static int can_use_rp(struct ubifs_info *c) in can_use_rp() argument
271 if (uid_eq(current_fsuid(), c->rp_uid) || capable(CAP_SYS_RESOURCE) || in can_use_rp()
272 (!gid_eq(c->rp_gid, GLOBAL_ROOT_GID) && in_group_p(c->rp_gid))) in can_use_rp()
278 * do_budget_space - reserve flash space for index and data growth.
279 * @c: UBIFS file-system description object
286 * that the "in-the-gaps" commit method always succeeds and UBIFS will always
291 * Notes about @c->bi.min_idx_lebs and @c->lst.idx_lebs variables:
292 * o @c->lst.idx_lebs is the number of LEBs the index currently uses. It might
296 * o @c->bi.min_idx_lebs is the number of LEBS the index presumably takes. IOW,
297 * the index may be consolidated to take up to @c->bi.min_idx_lebs LEBs.
299 * This function returns zero in case of success, and %-ENOSPC in case of
302 static int do_budget_space(struct ubifs_info *c) in do_budget_space() argument
308 min_idx_lebs = ubifs_calc_min_idx_lebs(c); in do_budget_space()
311 if (min_idx_lebs > c->lst.idx_lebs) in do_budget_space()
312 rsvd_idx_lebs = min_idx_lebs - c->lst.idx_lebs; in do_budget_space()
319 * @c->lst.empty_lebs + @c->freeable_cnt + @c->idx_gc_cnt - in do_budget_space()
320 * @c->lst.taken_empty_lebs in do_budget_space()
322 * @c->lst.empty_lebs are available because they are empty. in do_budget_space()
323 * @c->freeable_cnt are available because they contain only free and in do_budget_space()
324 * dirty space, @c->idx_gc_cnt are available because they are index in do_budget_space()
326 * before they can be used. And the in-the-gaps method will grab these in do_budget_space()
327 * if it needs them. @c->lst.taken_empty_lebs are empty LEBs that have in do_budget_space()
330 * Note, @c->idx_gc_cnt is included to both @c->lst.empty_lebs (because in do_budget_space()
331 * these LEBs are empty) and to @c->lst.taken_empty_lebs (because they in do_budget_space()
334 * Note, @c->lst.taken_empty_lebs may temporarily be higher by one in do_budget_space()
338 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - in do_budget_space()
339 c->lst.taken_empty_lebs; in do_budget_space()
342 min_idx_lebs, c->bi.min_idx_lebs, rsvd_idx_lebs); in do_budget_space()
343 return -ENOSPC; in do_budget_space()
346 available = ubifs_calc_available(c, min_idx_lebs); in do_budget_space()
347 outstanding = c->bi.data_growth + c->bi.dd_growth; in do_budget_space()
352 return -ENOSPC; in do_budget_space()
355 if (available - outstanding <= c->rp_size && !can_use_rp(c)) in do_budget_space()
356 return -ENOSPC; in do_budget_space()
358 c->bi.min_idx_lebs = min_idx_lebs; in do_budget_space()
363 * calc_idx_growth - calculate approximate index growth from budgeting request.
364 * @c: UBIFS file-system description object
370 static int calc_idx_growth(const struct ubifs_info *c, in calc_idx_growth() argument
375 znodes = req->new_ino + (req->new_page << UBIFS_BLOCKS_PER_PAGE_SHIFT) + in calc_idx_growth()
376 req->new_dent; in calc_idx_growth()
377 return znodes * c->max_idx_node_sz; in calc_idx_growth()
381 * calc_data_growth - calculate approximate amount of new data from budgeting
383 * @c: UBIFS file-system description object
386 static int calc_data_growth(const struct ubifs_info *c, in calc_data_growth() argument
391 data_growth = req->new_ino ? c->bi.inode_budget : 0; in calc_data_growth()
392 if (req->new_page) in calc_data_growth()
393 data_growth += c->bi.page_budget; in calc_data_growth()
394 if (req->new_dent) in calc_data_growth()
395 data_growth += c->bi.dent_budget; in calc_data_growth()
396 data_growth += req->new_ino_d; in calc_data_growth()
401 * calc_dd_growth - calculate approximate amount of data which makes other data
403 * @c: UBIFS file-system description object
406 static int calc_dd_growth(const struct ubifs_info *c, in calc_dd_growth() argument
411 dd_growth = req->dirtied_page ? c->bi.page_budget : 0; in calc_dd_growth()
413 if (req->dirtied_ino) in calc_dd_growth()
414 dd_growth += c->bi.inode_budget << (req->dirtied_ino - 1); in calc_dd_growth()
415 if (req->mod_dent) in calc_dd_growth()
416 dd_growth += c->bi.dent_budget; in calc_dd_growth()
417 dd_growth += req->dirtied_ino_d; in calc_dd_growth()
422 * ubifs_budget_space - ensure there is enough space to complete an operation.
423 * @c: UBIFS file-system description object
430 * commit, garbage-collection or write-back. Returns zero in case of success,
431 * %-ENOSPC if there is no free space and other negative error codes in case of
434 int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req) in ubifs_budget_space() argument
438 ubifs_assert(req->new_page <= 1); in ubifs_budget_space()
439 ubifs_assert(req->dirtied_page <= 1); in ubifs_budget_space()
440 ubifs_assert(req->new_dent <= 1); in ubifs_budget_space()
441 ubifs_assert(req->mod_dent <= 1); in ubifs_budget_space()
442 ubifs_assert(req->new_ino <= 1); in ubifs_budget_space()
443 ubifs_assert(req->new_ino_d <= UBIFS_MAX_INO_DATA); in ubifs_budget_space()
444 ubifs_assert(req->dirtied_ino <= 4); in ubifs_budget_space()
445 ubifs_assert(req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); in ubifs_budget_space()
446 ubifs_assert(!(req->new_ino_d & 7)); in ubifs_budget_space()
447 ubifs_assert(!(req->dirtied_ino_d & 7)); in ubifs_budget_space()
449 data_growth = calc_data_growth(c, req); in ubifs_budget_space()
450 dd_growth = calc_dd_growth(c, req); in ubifs_budget_space()
453 idx_growth = calc_idx_growth(c, req); in ubifs_budget_space()
456 spin_lock(&c->space_lock); in ubifs_budget_space()
457 ubifs_assert(c->bi.idx_growth >= 0); in ubifs_budget_space()
458 ubifs_assert(c->bi.data_growth >= 0); in ubifs_budget_space()
459 ubifs_assert(c->bi.dd_growth >= 0); in ubifs_budget_space()
461 if (unlikely(c->bi.nospace) && (c->bi.nospace_rp || !can_use_rp(c))) { in ubifs_budget_space()
463 spin_unlock(&c->space_lock); in ubifs_budget_space()
464 return -ENOSPC; in ubifs_budget_space()
467 c->bi.idx_growth += idx_growth; in ubifs_budget_space()
468 c->bi.data_growth += data_growth; in ubifs_budget_space()
469 c->bi.dd_growth += dd_growth; in ubifs_budget_space()
471 err = do_budget_space(c); in ubifs_budget_space()
473 req->idx_growth = idx_growth; in ubifs_budget_space()
474 req->data_growth = data_growth; in ubifs_budget_space()
475 req->dd_growth = dd_growth; in ubifs_budget_space()
476 spin_unlock(&c->space_lock); in ubifs_budget_space()
481 c->bi.idx_growth -= idx_growth; in ubifs_budget_space()
482 c->bi.data_growth -= data_growth; in ubifs_budget_space()
483 c->bi.dd_growth -= dd_growth; in ubifs_budget_space()
484 spin_unlock(&c->space_lock); in ubifs_budget_space()
486 if (req->fast) { in ubifs_budget_space()
491 err = make_free_space(c); in ubifs_budget_space()
493 if (err == -EAGAIN) { in ubifs_budget_space()
496 } else if (err == -ENOSPC) { in ubifs_budget_space()
499 dbg_budg("-ENOSPC, but anyway try once again"); in ubifs_budget_space()
502 dbg_budg("FS is full, -ENOSPC"); in ubifs_budget_space()
503 c->bi.nospace = 1; in ubifs_budget_space()
504 if (can_use_rp(c) || c->rp_size == 0) in ubifs_budget_space()
505 c->bi.nospace_rp = 1; in ubifs_budget_space()
508 ubifs_err(c, "cannot budget space, error %d", err); in ubifs_budget_space()
513 * ubifs_release_budget - release budgeted free space.
514 * @c: UBIFS file-system description object
518 * since the index changes (which were budgeted for in @req->idx_growth) will
520 * from @c->bi.idx_growth to @c->bi.uncommitted_idx. The latter will be zeroed
523 void ubifs_release_budget(struct ubifs_info *c, struct ubifs_budget_req *req) in ubifs_release_budget() argument
525 ubifs_assert(req->new_page <= 1); in ubifs_release_budget()
526 ubifs_assert(req->dirtied_page <= 1); in ubifs_release_budget()
527 ubifs_assert(req->new_dent <= 1); in ubifs_release_budget()
528 ubifs_assert(req->mod_dent <= 1); in ubifs_release_budget()
529 ubifs_assert(req->new_ino <= 1); in ubifs_release_budget()
530 ubifs_assert(req->new_ino_d <= UBIFS_MAX_INO_DATA); in ubifs_release_budget()
531 ubifs_assert(req->dirtied_ino <= 4); in ubifs_release_budget()
532 ubifs_assert(req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); in ubifs_release_budget()
533 ubifs_assert(!(req->new_ino_d & 7)); in ubifs_release_budget()
534 ubifs_assert(!(req->dirtied_ino_d & 7)); in ubifs_release_budget()
535 if (!req->recalculate) { in ubifs_release_budget()
536 ubifs_assert(req->idx_growth >= 0); in ubifs_release_budget()
537 ubifs_assert(req->data_growth >= 0); in ubifs_release_budget()
538 ubifs_assert(req->dd_growth >= 0); in ubifs_release_budget()
541 if (req->recalculate) { in ubifs_release_budget()
542 req->data_growth = calc_data_growth(c, req); in ubifs_release_budget()
543 req->dd_growth = calc_dd_growth(c, req); in ubifs_release_budget()
544 req->idx_growth = calc_idx_growth(c, req); in ubifs_release_budget()
547 if (!req->data_growth && !req->dd_growth) in ubifs_release_budget()
550 c->bi.nospace = c->bi.nospace_rp = 0; in ubifs_release_budget()
553 spin_lock(&c->space_lock); in ubifs_release_budget()
554 c->bi.idx_growth -= req->idx_growth; in ubifs_release_budget()
555 c->bi.uncommitted_idx += req->idx_growth; in ubifs_release_budget()
556 c->bi.data_growth -= req->data_growth; in ubifs_release_budget()
557 c->bi.dd_growth -= req->dd_growth; in ubifs_release_budget()
558 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); in ubifs_release_budget()
560 ubifs_assert(c->bi.idx_growth >= 0); in ubifs_release_budget()
561 ubifs_assert(c->bi.data_growth >= 0); in ubifs_release_budget()
562 ubifs_assert(c->bi.dd_growth >= 0); in ubifs_release_budget()
563 ubifs_assert(c->bi.min_idx_lebs < c->main_lebs); in ubifs_release_budget()
564 ubifs_assert(!(c->bi.idx_growth & 7)); in ubifs_release_budget()
565 ubifs_assert(!(c->bi.data_growth & 7)); in ubifs_release_budget()
566 ubifs_assert(!(c->bi.dd_growth & 7)); in ubifs_release_budget()
567 spin_unlock(&c->space_lock); in ubifs_release_budget()
571 * ubifs_convert_page_budget - convert budget of a new page.
572 * @c: UBIFS file-system description object
576 * the former, so this function only does simple re-calculation and does not
577 * involve any write-back.
579 void ubifs_convert_page_budget(struct ubifs_info *c) in ubifs_convert_page_budget() argument
581 spin_lock(&c->space_lock); in ubifs_convert_page_budget()
583 c->bi.idx_growth -= c->max_idx_node_sz << UBIFS_BLOCKS_PER_PAGE_SHIFT; in ubifs_convert_page_budget()
585 c->bi.data_growth -= c->bi.page_budget; in ubifs_convert_page_budget()
587 c->bi.dd_growth += c->bi.page_budget; in ubifs_convert_page_budget()
588 /* And re-calculate the indexing space reservation */ in ubifs_convert_page_budget()
589 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); in ubifs_convert_page_budget()
590 spin_unlock(&c->space_lock); in ubifs_convert_page_budget()
594 * ubifs_release_dirty_inode_budget - release dirty inode budget.
595 * @c: UBIFS file-system description object
602 void ubifs_release_dirty_inode_budget(struct ubifs_info *c, in ubifs_release_dirty_inode_budget() argument
609 req.dd_growth = c->bi.inode_budget + ALIGN(ui->data_len, 8); in ubifs_release_dirty_inode_budget()
610 ubifs_release_budget(c, &req); in ubifs_release_dirty_inode_budget()
615 * ubifs_reported_space - calculate reported free space.
616 * @c: the UBIFS file-system description object
620 * user-space. User-space application tend to expect that if the file-system
634 long long ubifs_reported_space(const struct ubifs_info *c, long long free) in ubifs_reported_space() argument
644 * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number in ubifs_reported_space()
645 * of data nodes, f - fanout. Because effective UBIFS fanout is twice in ubifs_reported_space()
647 * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes. in ubifs_reported_space()
651 f = c->fanout > 3 ? c->fanout >> 1 : 2; in ubifs_reported_space()
654 divisor += (c->max_idx_node_sz * 3) / (f - 1); in ubifs_reported_space()
661 * ubifs_get_free_space_nolock - return amount of free space.
662 * @c: UBIFS file-system description object
664 * This function calculates amount of free space to report to user-space.
671 * to assume that if the file-system reports N bytes of free space, they would
673 * traditional file-systems, because they have way less overhead than UBIFS.
676 long long ubifs_get_free_space_nolock(struct ubifs_info *c) in ubifs_get_free_space_nolock() argument
681 ubifs_assert(c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c)); in ubifs_get_free_space_nolock()
682 outstanding = c->bi.data_growth + c->bi.dd_growth; in ubifs_get_free_space_nolock()
683 available = ubifs_calc_available(c, c->bi.min_idx_lebs); in ubifs_get_free_space_nolock()
686 * When reporting free space to user-space, UBIFS guarantees that it is in ubifs_get_free_space_nolock()
690 * LEBs we would waste only @c->leb_overhead bytes, not @c->dark_wm. in ubifs_get_free_space_nolock()
696 if (c->bi.min_idx_lebs > c->lst.idx_lebs) in ubifs_get_free_space_nolock()
697 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; in ubifs_get_free_space_nolock()
700 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - in ubifs_get_free_space_nolock()
701 c->lst.taken_empty_lebs; in ubifs_get_free_space_nolock()
702 lebs -= rsvd_idx_lebs; in ubifs_get_free_space_nolock()
703 available += lebs * (c->dark_wm - c->leb_overhead); in ubifs_get_free_space_nolock()
706 free = ubifs_reported_space(c, available - outstanding); in ubifs_get_free_space_nolock()
713 * ubifs_get_free_space - return amount of free space.
714 * @c: UBIFS file-system description object
717 * user-space.
719 long long ubifs_get_free_space(struct ubifs_info *c) in ubifs_get_free_space() argument
723 spin_lock(&c->space_lock); in ubifs_get_free_space()
724 free = ubifs_get_free_space_nolock(c); in ubifs_get_free_space()
725 spin_unlock(&c->space_lock); in ubifs_get_free_space()