Lines Matching +full:- +full:c
1 // SPDX-License-Identifier: GPL-2.0-only
5 * Copyright (C) 2006-2008 Nokia Corporation.
12 * This file implements the budgeting sub-system which is responsible for UBIFS
40 * shrink_liability - write-back some dirty pages/inodes.
41 * @c: UBIFS file-system description object
42 * @nr_to_write: how many dirty pages to write-back
48 * (@i_mutex) by the caller of the budgeting function, because write-back does
51 static void shrink_liability(struct ubifs_info *c, int nr_to_write) in shrink_liability() argument
53 down_read(&c->vfs_sb->s_umount); in shrink_liability()
54 writeback_inodes_sb_nr(c->vfs_sb, nr_to_write, WB_REASON_FS_FREE_SPACE); in shrink_liability()
55 up_read(&c->vfs_sb->s_umount); in shrink_liability()
59 * run_gc - run garbage collector.
60 * @c: UBIFS file-system description object
63 * zero if a free LEB has been produced, %-EAGAIN if commit is required, and a
66 static int run_gc(struct ubifs_info *c) in run_gc() argument
70 /* Make some free space by garbage-collecting dirty space */ in run_gc()
71 down_read(&c->commit_sem); in run_gc()
72 lnum = ubifs_garbage_collect(c, 1); in run_gc()
73 up_read(&c->commit_sem); in run_gc()
79 return ubifs_return_leb(c, lnum); in run_gc()
83 * get_liability - calculate current liability.
84 * @c: UBIFS file-system description object
89 static long long get_liability(struct ubifs_info *c) in get_liability() argument
93 spin_lock(&c->space_lock); in get_liability()
94 liab = c->bi.idx_growth + c->bi.data_growth + c->bi.dd_growth; in get_liability()
95 spin_unlock(&c->space_lock); in get_liability()
100 * make_free_space - make more free space on the file-system.
101 * @c: UBIFS file-system description object
106 * needed, so shrinking the liability is one way to make free space - the
112 * So this function tries to do the above. Returns %-EAGAIN if some free space
113 * was presumably made and the caller has to re-try budgeting the operation.
114 * Returns %-ENOSPC if it couldn't do more free space, and other negative error
117 static int make_free_space(struct ubifs_info *c) in make_free_space() argument
123 liab1 = get_liability(c); in make_free_space()
128 dbg_budg("liability %lld, run write-back", liab1); in make_free_space()
129 shrink_liability(c, NR_TO_WRITE); in make_free_space()
131 liab2 = get_liability(c); in make_free_space()
133 return -EAGAIN; in make_free_space()
139 err = run_gc(c); in make_free_space()
141 return -EAGAIN; in make_free_space()
143 if (err != -EAGAIN && err != -ENOSPC) in make_free_space()
148 err = ubifs_run_commit(c); in make_free_space()
153 return -ENOSPC; in make_free_space()
157 * ubifs_calc_min_idx_lebs - calculate amount of LEBs for the index.
158 * @c: UBIFS file-system description object
163 int ubifs_calc_min_idx_lebs(struct ubifs_info *c) in ubifs_calc_min_idx_lebs() argument
168 idx_size = c->bi.old_idx_sz + c->bi.idx_growth + c->bi.uncommitted_idx; in ubifs_calc_min_idx_lebs()
174 * have to do this costly 64-bit division on fast-path. in ubifs_calc_min_idx_lebs()
176 idx_lebs = div_u64(idx_size + c->idx_leb_size - 1, c->idx_leb_size); in ubifs_calc_min_idx_lebs()
178 * The index head is not available for the in-the-gaps method, so add an in ubifs_calc_min_idx_lebs()
188 * ubifs_calc_available - calculate available FS space.
189 * @c: UBIFS file-system description object
194 long long ubifs_calc_available(const struct ubifs_info *c, int min_idx_lebs) in ubifs_calc_available() argument
199 available = c->main_bytes - c->lst.total_used; in ubifs_calc_available()
215 subtract_lebs += c->jhead_cnt; in ubifs_calc_available()
220 available -= (long long)subtract_lebs * c->leb_size; in ubifs_calc_available()
223 available -= c->lst.total_dead; in ubifs_calc_available()
226 * Subtract dark space, which might or might not be usable - it depends in ubifs_calc_available()
228 * this is a lot of uncompressed or not-compressible data, the dark in ubifs_calc_available()
231 available -= c->lst.total_dark; in ubifs_calc_available()
239 if (c->lst.idx_lebs > min_idx_lebs) { in ubifs_calc_available()
240 subtract_lebs = c->lst.idx_lebs - min_idx_lebs; in ubifs_calc_available()
241 available -= subtract_lebs * c->dark_wm; in ubifs_calc_available()
249 * can_use_rp - check whether the user is allowed to use reserved pool.
250 * @c: UBIFS file-system description object
252 * UBIFS has so-called "reserved pool" which is flash space reserved
257 static int can_use_rp(struct ubifs_info *c) in can_use_rp() argument
259 if (uid_eq(current_fsuid(), c->rp_uid) || capable(CAP_SYS_RESOURCE) || in can_use_rp()
260 (!gid_eq(c->rp_gid, GLOBAL_ROOT_GID) && in_group_p(c->rp_gid))) in can_use_rp()
266 * do_budget_space - reserve flash space for index and data growth.
267 * @c: UBIFS file-system description object
274 * that the "in-the-gaps" commit method always succeeds and UBIFS will always
279 * Notes about @c->bi.min_idx_lebs and @c->lst.idx_lebs variables:
280 * o @c->lst.idx_lebs is the number of LEBs the index currently uses. It might
284 * o @c->bi.min_idx_lebs is the number of LEBS the index presumably takes. IOW,
285 * the index may be consolidated to take up to @c->bi.min_idx_lebs LEBs.
287 * This function returns zero in case of success, and %-ENOSPC in case of
290 static int do_budget_space(struct ubifs_info *c) in do_budget_space() argument
296 min_idx_lebs = ubifs_calc_min_idx_lebs(c); in do_budget_space()
299 if (min_idx_lebs > c->lst.idx_lebs) in do_budget_space()
300 rsvd_idx_lebs = min_idx_lebs - c->lst.idx_lebs; in do_budget_space()
307 * @c->lst.empty_lebs + @c->freeable_cnt + @c->idx_gc_cnt - in do_budget_space()
308 * @c->lst.taken_empty_lebs in do_budget_space()
310 * @c->lst.empty_lebs are available because they are empty. in do_budget_space()
311 * @c->freeable_cnt are available because they contain only free and in do_budget_space()
312 * dirty space, @c->idx_gc_cnt are available because they are index in do_budget_space()
314 * before they can be used. And the in-the-gaps method will grab these in do_budget_space()
315 * if it needs them. @c->lst.taken_empty_lebs are empty LEBs that have in do_budget_space()
318 * Note, @c->idx_gc_cnt is included to both @c->lst.empty_lebs (because in do_budget_space()
319 * these LEBs are empty) and to @c->lst.taken_empty_lebs (because they in do_budget_space()
322 * Note, @c->lst.taken_empty_lebs may temporarily be higher by one in do_budget_space()
326 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - in do_budget_space()
327 c->lst.taken_empty_lebs; in do_budget_space()
330 min_idx_lebs, c->bi.min_idx_lebs, rsvd_idx_lebs); in do_budget_space()
331 return -ENOSPC; in do_budget_space()
334 available = ubifs_calc_available(c, min_idx_lebs); in do_budget_space()
335 outstanding = c->bi.data_growth + c->bi.dd_growth; in do_budget_space()
340 return -ENOSPC; in do_budget_space()
343 if (available - outstanding <= c->rp_size && !can_use_rp(c)) in do_budget_space()
344 return -ENOSPC; in do_budget_space()
346 c->bi.min_idx_lebs = min_idx_lebs; in do_budget_space()
351 * calc_idx_growth - calculate approximate index growth from budgeting request.
352 * @c: UBIFS file-system description object
358 static int calc_idx_growth(const struct ubifs_info *c, in calc_idx_growth() argument
363 znodes = req->new_ino + (req->new_page << UBIFS_BLOCKS_PER_PAGE_SHIFT) + in calc_idx_growth()
364 req->new_dent; in calc_idx_growth()
365 return znodes * c->max_idx_node_sz; in calc_idx_growth()
369 * calc_data_growth - calculate approximate amount of new data from budgeting
371 * @c: UBIFS file-system description object
374 static int calc_data_growth(const struct ubifs_info *c, in calc_data_growth() argument
379 data_growth = req->new_ino ? c->bi.inode_budget : 0; in calc_data_growth()
380 if (req->new_page) in calc_data_growth()
381 data_growth += c->bi.page_budget; in calc_data_growth()
382 if (req->new_dent) in calc_data_growth()
383 data_growth += c->bi.dent_budget; in calc_data_growth()
384 data_growth += req->new_ino_d; in calc_data_growth()
389 * calc_dd_growth - calculate approximate amount of data which makes other data
391 * @c: UBIFS file-system description object
394 static int calc_dd_growth(const struct ubifs_info *c, in calc_dd_growth() argument
399 dd_growth = req->dirtied_page ? c->bi.page_budget : 0; in calc_dd_growth()
401 if (req->dirtied_ino) in calc_dd_growth()
402 dd_growth += c->bi.inode_budget * req->dirtied_ino; in calc_dd_growth()
403 if (req->mod_dent) in calc_dd_growth()
404 dd_growth += c->bi.dent_budget; in calc_dd_growth()
405 dd_growth += req->dirtied_ino_d; in calc_dd_growth()
410 * ubifs_budget_space - ensure there is enough space to complete an operation.
411 * @c: UBIFS file-system description object
418 * commit, garbage-collection or write-back. Returns zero in case of success,
419 * %-ENOSPC if there is no free space and other negative error codes in case of
422 int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req) in ubifs_budget_space() argument
426 ubifs_assert(c, req->new_page <= 1); in ubifs_budget_space()
427 ubifs_assert(c, req->dirtied_page <= 1); in ubifs_budget_space()
428 ubifs_assert(c, req->new_dent <= 1); in ubifs_budget_space()
429 ubifs_assert(c, req->mod_dent <= 1); in ubifs_budget_space()
430 ubifs_assert(c, req->new_ino <= 1); in ubifs_budget_space()
431 ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA); in ubifs_budget_space()
432 ubifs_assert(c, req->dirtied_ino <= 4); in ubifs_budget_space()
433 ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); in ubifs_budget_space()
434 ubifs_assert(c, !(req->new_ino_d & 7)); in ubifs_budget_space()
435 ubifs_assert(c, !(req->dirtied_ino_d & 7)); in ubifs_budget_space()
437 data_growth = calc_data_growth(c, req); in ubifs_budget_space()
438 dd_growth = calc_dd_growth(c, req); in ubifs_budget_space()
441 idx_growth = calc_idx_growth(c, req); in ubifs_budget_space()
444 spin_lock(&c->space_lock); in ubifs_budget_space()
445 ubifs_assert(c, c->bi.idx_growth >= 0); in ubifs_budget_space()
446 ubifs_assert(c, c->bi.data_growth >= 0); in ubifs_budget_space()
447 ubifs_assert(c, c->bi.dd_growth >= 0); in ubifs_budget_space()
449 if (unlikely(c->bi.nospace) && (c->bi.nospace_rp || !can_use_rp(c))) { in ubifs_budget_space()
451 spin_unlock(&c->space_lock); in ubifs_budget_space()
452 return -ENOSPC; in ubifs_budget_space()
455 c->bi.idx_growth += idx_growth; in ubifs_budget_space()
456 c->bi.data_growth += data_growth; in ubifs_budget_space()
457 c->bi.dd_growth += dd_growth; in ubifs_budget_space()
459 err = do_budget_space(c); in ubifs_budget_space()
461 req->idx_growth = idx_growth; in ubifs_budget_space()
462 req->data_growth = data_growth; in ubifs_budget_space()
463 req->dd_growth = dd_growth; in ubifs_budget_space()
464 spin_unlock(&c->space_lock); in ubifs_budget_space()
469 c->bi.idx_growth -= idx_growth; in ubifs_budget_space()
470 c->bi.data_growth -= data_growth; in ubifs_budget_space()
471 c->bi.dd_growth -= dd_growth; in ubifs_budget_space()
472 spin_unlock(&c->space_lock); in ubifs_budget_space()
474 if (req->fast) { in ubifs_budget_space()
479 err = make_free_space(c); in ubifs_budget_space()
481 if (err == -EAGAIN) { in ubifs_budget_space()
484 } else if (err == -ENOSPC) { in ubifs_budget_space()
487 dbg_budg("-ENOSPC, but anyway try once again"); in ubifs_budget_space()
490 dbg_budg("FS is full, -ENOSPC"); in ubifs_budget_space()
491 c->bi.nospace = 1; in ubifs_budget_space()
492 if (can_use_rp(c) || c->rp_size == 0) in ubifs_budget_space()
493 c->bi.nospace_rp = 1; in ubifs_budget_space()
496 ubifs_err(c, "cannot budget space, error %d", err); in ubifs_budget_space()
501 * ubifs_release_budget - release budgeted free space.
502 * @c: UBIFS file-system description object
506 * since the index changes (which were budgeted for in @req->idx_growth) will
508 * from @c->bi.idx_growth to @c->bi.uncommitted_idx. The latter will be zeroed
511 void ubifs_release_budget(struct ubifs_info *c, struct ubifs_budget_req *req) in ubifs_release_budget() argument
513 ubifs_assert(c, req->new_page <= 1); in ubifs_release_budget()
514 ubifs_assert(c, req->dirtied_page <= 1); in ubifs_release_budget()
515 ubifs_assert(c, req->new_dent <= 1); in ubifs_release_budget()
516 ubifs_assert(c, req->mod_dent <= 1); in ubifs_release_budget()
517 ubifs_assert(c, req->new_ino <= 1); in ubifs_release_budget()
518 ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA); in ubifs_release_budget()
519 ubifs_assert(c, req->dirtied_ino <= 4); in ubifs_release_budget()
520 ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); in ubifs_release_budget()
521 ubifs_assert(c, !(req->new_ino_d & 7)); in ubifs_release_budget()
522 ubifs_assert(c, !(req->dirtied_ino_d & 7)); in ubifs_release_budget()
523 if (!req->recalculate) { in ubifs_release_budget()
524 ubifs_assert(c, req->idx_growth >= 0); in ubifs_release_budget()
525 ubifs_assert(c, req->data_growth >= 0); in ubifs_release_budget()
526 ubifs_assert(c, req->dd_growth >= 0); in ubifs_release_budget()
529 if (req->recalculate) { in ubifs_release_budget()
530 req->data_growth = calc_data_growth(c, req); in ubifs_release_budget()
531 req->dd_growth = calc_dd_growth(c, req); in ubifs_release_budget()
532 req->idx_growth = calc_idx_growth(c, req); in ubifs_release_budget()
535 if (!req->data_growth && !req->dd_growth) in ubifs_release_budget()
538 c->bi.nospace = c->bi.nospace_rp = 0; in ubifs_release_budget()
541 spin_lock(&c->space_lock); in ubifs_release_budget()
542 c->bi.idx_growth -= req->idx_growth; in ubifs_release_budget()
543 c->bi.uncommitted_idx += req->idx_growth; in ubifs_release_budget()
544 c->bi.data_growth -= req->data_growth; in ubifs_release_budget()
545 c->bi.dd_growth -= req->dd_growth; in ubifs_release_budget()
546 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); in ubifs_release_budget()
548 ubifs_assert(c, c->bi.idx_growth >= 0); in ubifs_release_budget()
549 ubifs_assert(c, c->bi.data_growth >= 0); in ubifs_release_budget()
550 ubifs_assert(c, c->bi.dd_growth >= 0); in ubifs_release_budget()
551 ubifs_assert(c, c->bi.min_idx_lebs < c->main_lebs); in ubifs_release_budget()
552 ubifs_assert(c, !(c->bi.idx_growth & 7)); in ubifs_release_budget()
553 ubifs_assert(c, !(c->bi.data_growth & 7)); in ubifs_release_budget()
554 ubifs_assert(c, !(c->bi.dd_growth & 7)); in ubifs_release_budget()
555 spin_unlock(&c->space_lock); in ubifs_release_budget()
559 * ubifs_convert_page_budget - convert budget of a new page.
560 * @c: UBIFS file-system description object
564 * the former, so this function only does simple re-calculation and does not
565 * involve any write-back.
567 void ubifs_convert_page_budget(struct ubifs_info *c) in ubifs_convert_page_budget() argument
569 spin_lock(&c->space_lock); in ubifs_convert_page_budget()
571 c->bi.idx_growth -= c->max_idx_node_sz << UBIFS_BLOCKS_PER_PAGE_SHIFT; in ubifs_convert_page_budget()
573 c->bi.data_growth -= c->bi.page_budget; in ubifs_convert_page_budget()
575 c->bi.dd_growth += c->bi.page_budget; in ubifs_convert_page_budget()
576 /* And re-calculate the indexing space reservation */ in ubifs_convert_page_budget()
577 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); in ubifs_convert_page_budget()
578 spin_unlock(&c->space_lock); in ubifs_convert_page_budget()
582 * ubifs_release_dirty_inode_budget - release dirty inode budget.
583 * @c: UBIFS file-system description object
590 void ubifs_release_dirty_inode_budget(struct ubifs_info *c, in ubifs_release_dirty_inode_budget() argument
597 req.dd_growth = c->bi.inode_budget + ALIGN(ui->data_len, 8); in ubifs_release_dirty_inode_budget()
598 ubifs_release_budget(c, &req); in ubifs_release_dirty_inode_budget()
602 * ubifs_reported_space - calculate reported free space.
603 * @c: the UBIFS file-system description object
607 * user-space. User-space application tend to expect that if the file-system
621 long long ubifs_reported_space(const struct ubifs_info *c, long long free) in ubifs_reported_space() argument
631 * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number in ubifs_reported_space()
632 * of data nodes, f - fanout. Because effective UBIFS fanout is twice in ubifs_reported_space()
634 * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes. in ubifs_reported_space()
638 f = c->fanout > 3 ? c->fanout >> 1 : 2; in ubifs_reported_space()
641 divisor += (c->max_idx_node_sz * 3) / (f - 1); in ubifs_reported_space()
647 * ubifs_get_free_space_nolock - return amount of free space.
648 * @c: UBIFS file-system description object
650 * This function calculates amount of free space to report to user-space.
657 * to assume that if the file-system reports N bytes of free space, they would
659 * traditional file-systems, because they have way less overhead than UBIFS.
662 long long ubifs_get_free_space_nolock(struct ubifs_info *c) in ubifs_get_free_space_nolock() argument
667 ubifs_assert(c, c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c)); in ubifs_get_free_space_nolock()
668 outstanding = c->bi.data_growth + c->bi.dd_growth; in ubifs_get_free_space_nolock()
669 available = ubifs_calc_available(c, c->bi.min_idx_lebs); in ubifs_get_free_space_nolock()
672 * When reporting free space to user-space, UBIFS guarantees that it is in ubifs_get_free_space_nolock()
676 * LEBs we would waste only @c->leb_overhead bytes, not @c->dark_wm. in ubifs_get_free_space_nolock()
682 if (c->bi.min_idx_lebs > c->lst.idx_lebs) in ubifs_get_free_space_nolock()
683 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; in ubifs_get_free_space_nolock()
686 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - in ubifs_get_free_space_nolock()
687 c->lst.taken_empty_lebs; in ubifs_get_free_space_nolock()
688 lebs -= rsvd_idx_lebs; in ubifs_get_free_space_nolock()
689 available += lebs * (c->dark_wm - c->leb_overhead); in ubifs_get_free_space_nolock()
692 free = ubifs_reported_space(c, available - outstanding); in ubifs_get_free_space_nolock()
699 * ubifs_get_free_space - return amount of free space.
700 * @c: UBIFS file-system description object
703 * user-space.
705 long long ubifs_get_free_space(struct ubifs_info *c) in ubifs_get_free_space() argument
709 spin_lock(&c->space_lock); in ubifs_get_free_space()
710 free = ubifs_get_free_space_nolock(c); in ubifs_get_free_space()
711 spin_unlock(&c->space_lock); in ubifs_get_free_space()