1// SPDX-License-Identifier: GPL-2.0-only 2/* 3 * This file is part of UBIFS. 4 * 5 * Copyright (C) 2006-2008 Nokia Corporation. 6 * 7 * Authors: Adrian Hunter 8 * Artem Bityutskiy (Битюцкий Артём) 9 */ 10 11/* 12 * This file implements the budgeting sub-system which is responsible for UBIFS 13 * space management. 14 * 15 * Factors such as compression, wasted space at the ends of LEBs, space in other 16 * journal heads, the effect of updates on the index, and so on, make it 17 * impossible to accurately predict the amount of space needed. Consequently 18 * approximations are used. 19 */ 20 21#include "ubifs.h" 22#include <linux/writeback.h> 23#include <linux/math64.h> 24 25/* 26 * When pessimistic budget calculations say that there is no enough space, 27 * UBIFS starts writing back dirty inodes and pages, doing garbage collection, 28 * or committing. The below constant defines maximum number of times UBIFS 29 * repeats the operations. 30 */ 31#define MAX_MKSPC_RETRIES 3 32 33/* 34 * The below constant defines amount of dirty pages which should be written 35 * back at when trying to shrink the liability. 36 */ 37#define NR_TO_WRITE 16 38 39/** 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 43 * 44 * This function shrinks UBIFS liability by means of writing back some amount 45 * of dirty inodes and their pages. 46 * 47 * Note, this function synchronizes even VFS inodes which are locked 48 * (@i_mutex) by the caller of the budgeting function, because write-back does 49 * not touch @i_mutex. 50 */ 51static void shrink_liability(struct ubifs_info *c, int nr_to_write) 52{ 53 down_read(&c->vfs_sb->s_umount); 54 writeback_inodes_sb_nr(c->vfs_sb, nr_to_write, WB_REASON_FS_FREE_SPACE); 55 up_read(&c->vfs_sb->s_umount); 56} 57 58/** 59 * run_gc - run garbage collector. 60 * @c: UBIFS file-system description object 61 * 62 * This function runs garbage collector to make some more free space. Returns 63 * zero if a free LEB has been produced, %-EAGAIN if commit is required, and a 64 * negative error code in case of failure. 65 */ 66static int run_gc(struct ubifs_info *c) 67{ 68 int err, lnum; 69 70 /* Make some free space by garbage-collecting dirty space */ 71 down_read(&c->commit_sem); 72 lnum = ubifs_garbage_collect(c, 1); 73 up_read(&c->commit_sem); 74 if (lnum < 0) 75 return lnum; 76 77 /* GC freed one LEB, return it to lprops */ 78 dbg_budg("GC freed LEB %d", lnum); 79 err = ubifs_return_leb(c, lnum); 80 if (err) 81 return err; 82 return 0; 83} 84 85/** 86 * get_liability - calculate current liability. 87 * @c: UBIFS file-system description object 88 * 89 * This function calculates and returns current UBIFS liability, i.e. the 90 * amount of bytes UBIFS has "promised" to write to the media. 91 */ 92static long long get_liability(struct ubifs_info *c) 93{ 94 long long liab; 95 96 spin_lock(&c->space_lock); 97 liab = c->bi.idx_growth + c->bi.data_growth + c->bi.dd_growth; 98 spin_unlock(&c->space_lock); 99 return liab; 100} 101 102/** 103 * make_free_space - make more free space on the file-system. 104 * @c: UBIFS file-system description object 105 * 106 * This function is called when an operation cannot be budgeted because there 107 * is supposedly no free space. But in most cases there is some free space: 108 * o budgeting is pessimistic, so it always budgets more than it is actually 109 * needed, so shrinking the liability is one way to make free space - the 110 * cached data will take less space then it was budgeted for; 111 * o GC may turn some dark space into free space (budgeting treats dark space 112 * as not available); 113 * o commit may free some LEB, i.e., turn freeable LEBs into free LEBs. 114 * 115 * So this function tries to do the above. Returns %-EAGAIN if some free space 116 * was presumably made and the caller has to re-try budgeting the operation. 117 * Returns %-ENOSPC if it couldn't do more free space, and other negative error 118 * codes on failures. 119 */ 120static int make_free_space(struct ubifs_info *c) 121{ 122 int err, retries = 0; 123 long long liab1, liab2; 124 125 do { 126 liab1 = get_liability(c); 127 /* 128 * We probably have some dirty pages or inodes (liability), try 129 * to write them back. 130 */ 131 dbg_budg("liability %lld, run write-back", liab1); 132 shrink_liability(c, NR_TO_WRITE); 133 134 liab2 = get_liability(c); 135 if (liab2 < liab1) 136 return -EAGAIN; 137 138 dbg_budg("new liability %lld (not shrunk)", liab2); 139 140 /* Liability did not shrink again, try GC */ 141 dbg_budg("Run GC"); 142 err = run_gc(c); 143 if (!err) 144 return -EAGAIN; 145 146 if (err != -EAGAIN && err != -ENOSPC) 147 /* Some real error happened */ 148 return err; 149 150 dbg_budg("Run commit (retries %d)", retries); 151 err = ubifs_run_commit(c); 152 if (err) 153 return err; 154 } while (retries++ < MAX_MKSPC_RETRIES); 155 156 return -ENOSPC; 157} 158 159/** 160 * ubifs_calc_min_idx_lebs - calculate amount of LEBs for the index. 161 * @c: UBIFS file-system description object 162 * 163 * This function calculates and returns the number of LEBs which should be kept 164 * for index usage. 165 */ 166int ubifs_calc_min_idx_lebs(struct ubifs_info *c) 167{ 168 int idx_lebs; 169 long long idx_size; 170 171 idx_size = c->bi.old_idx_sz + c->bi.idx_growth + c->bi.uncommitted_idx; 172 /* And make sure we have thrice the index size of space reserved */ 173 idx_size += idx_size << 1; 174 /* 175 * We do not maintain 'old_idx_size' as 'old_idx_lebs'/'old_idx_bytes' 176 * pair, nor similarly the two variables for the new index size, so we 177 * have to do this costly 64-bit division on fast-path. 178 */ 179 idx_lebs = div_u64(idx_size + c->idx_leb_size - 1, c->idx_leb_size); 180 /* 181 * The index head is not available for the in-the-gaps method, so add an 182 * extra LEB to compensate. 183 */ 184 idx_lebs += 1; 185 if (idx_lebs < MIN_INDEX_LEBS) 186 idx_lebs = MIN_INDEX_LEBS; 187 return idx_lebs; 188} 189 190/** 191 * ubifs_calc_available - calculate available FS space. 192 * @c: UBIFS file-system description object 193 * @min_idx_lebs: minimum number of LEBs reserved for the index 194 * 195 * This function calculates and returns amount of FS space available for use. 196 */ 197long long ubifs_calc_available(const struct ubifs_info *c, int min_idx_lebs) 198{ 199 int subtract_lebs; 200 long long available; 201 202 available = c->main_bytes - c->lst.total_used; 203 204 /* 205 * Now 'available' contains theoretically available flash space 206 * assuming there is no index, so we have to subtract the space which 207 * is reserved for the index. 208 */ 209 subtract_lebs = min_idx_lebs; 210 211 /* Take into account that GC reserves one LEB for its own needs */ 212 subtract_lebs += 1; 213 214 /* 215 * Since different write types go to different heads, we should 216 * reserve one leb for each head. 217 */ 218 subtract_lebs += c->jhead_cnt; 219 220 /* We also reserve one LEB for deletions, which bypass budgeting */ 221 subtract_lebs += 1; 222 223 available -= (long long)subtract_lebs * c->leb_size; 224 225 /* Subtract the dead space which is not available for use */ 226 available -= c->lst.total_dead; 227 228 /* 229 * Subtract dark space, which might or might not be usable - it depends 230 * on the data which we have on the media and which will be written. If 231 * this is a lot of uncompressed or not-compressible data, the dark 232 * space cannot be used. 233 */ 234 available -= c->lst.total_dark; 235 236 /* 237 * However, there is more dark space. The index may be bigger than 238 * @min_idx_lebs. Those extra LEBs are assumed to be available, but 239 * their dark space is not included in total_dark, so it is subtracted 240 * here. 241 */ 242 if (c->lst.idx_lebs > min_idx_lebs) { 243 subtract_lebs = c->lst.idx_lebs - min_idx_lebs; 244 available -= subtract_lebs * c->dark_wm; 245 } 246 247 /* The calculations are rough and may end up with a negative number */ 248 return available > 0 ? available : 0; 249} 250 251/** 252 * can_use_rp - check whether the user is allowed to use reserved pool. 253 * @c: UBIFS file-system description object 254 * 255 * UBIFS has so-called "reserved pool" which is flash space reserved 256 * for the superuser and for uses whose UID/GID is recorded in UBIFS superblock. 257 * This function checks whether current user is allowed to use reserved pool. 258 * Returns %1 current user is allowed to use reserved pool and %0 otherwise. 259 */ 260static int can_use_rp(struct ubifs_info *c) 261{ 262 if (uid_eq(current_fsuid(), c->rp_uid) || capable(CAP_SYS_RESOURCE) || 263 (!gid_eq(c->rp_gid, GLOBAL_ROOT_GID) && in_group_p(c->rp_gid))) 264 return 1; 265 return 0; 266} 267 268/** 269 * do_budget_space - reserve flash space for index and data growth. 270 * @c: UBIFS file-system description object 271 * 272 * This function makes sure UBIFS has enough free LEBs for index growth and 273 * data. 274 * 275 * When budgeting index space, UBIFS reserves thrice as many LEBs as the index 276 * would take if it was consolidated and written to the flash. This guarantees 277 * that the "in-the-gaps" commit method always succeeds and UBIFS will always 278 * be able to commit dirty index. So this function basically adds amount of 279 * budgeted index space to the size of the current index, multiplies this by 3, 280 * and makes sure this does not exceed the amount of free LEBs. 281 * 282 * Notes about @c->bi.min_idx_lebs and @c->lst.idx_lebs variables: 283 * o @c->lst.idx_lebs is the number of LEBs the index currently uses. It might 284 * be large, because UBIFS does not do any index consolidation as long as 285 * there is free space. IOW, the index may take a lot of LEBs, but the LEBs 286 * will contain a lot of dirt. 287 * o @c->bi.min_idx_lebs is the number of LEBS the index presumably takes. IOW, 288 * the index may be consolidated to take up to @c->bi.min_idx_lebs LEBs. 289 * 290 * This function returns zero in case of success, and %-ENOSPC in case of 291 * failure. 292 */ 293static int do_budget_space(struct ubifs_info *c) 294{ 295 long long outstanding, available; 296 int lebs, rsvd_idx_lebs, min_idx_lebs; 297 298 /* First budget index space */ 299 min_idx_lebs = ubifs_calc_min_idx_lebs(c); 300 301 /* Now 'min_idx_lebs' contains number of LEBs to reserve */ 302 if (min_idx_lebs > c->lst.idx_lebs) 303 rsvd_idx_lebs = min_idx_lebs - c->lst.idx_lebs; 304 else 305 rsvd_idx_lebs = 0; 306 307 /* 308 * The number of LEBs that are available to be used by the index is: 309 * 310 * @c->lst.empty_lebs + @c->freeable_cnt + @c->idx_gc_cnt - 311 * @c->lst.taken_empty_lebs 312 * 313 * @c->lst.empty_lebs are available because they are empty. 314 * @c->freeable_cnt are available because they contain only free and 315 * dirty space, @c->idx_gc_cnt are available because they are index 316 * LEBs that have been garbage collected and are awaiting the commit 317 * before they can be used. And the in-the-gaps method will grab these 318 * if it needs them. @c->lst.taken_empty_lebs are empty LEBs that have 319 * already been allocated for some purpose. 320 * 321 * Note, @c->idx_gc_cnt is included to both @c->lst.empty_lebs (because 322 * these LEBs are empty) and to @c->lst.taken_empty_lebs (because they 323 * are taken until after the commit). 324 * 325 * Note, @c->lst.taken_empty_lebs may temporarily be higher by one 326 * because of the way we serialize LEB allocations and budgeting. See a 327 * comment in 'ubifs_find_free_space()'. 328 */ 329 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - 330 c->lst.taken_empty_lebs; 331 if (unlikely(rsvd_idx_lebs > lebs)) { 332 dbg_budg("out of indexing space: min_idx_lebs %d (old %d), rsvd_idx_lebs %d", 333 min_idx_lebs, c->bi.min_idx_lebs, rsvd_idx_lebs); 334 return -ENOSPC; 335 } 336 337 available = ubifs_calc_available(c, min_idx_lebs); 338 outstanding = c->bi.data_growth + c->bi.dd_growth; 339 340 if (unlikely(available < outstanding)) { 341 dbg_budg("out of data space: available %lld, outstanding %lld", 342 available, outstanding); 343 return -ENOSPC; 344 } 345 346 if (available - outstanding <= c->rp_size && !can_use_rp(c)) 347 return -ENOSPC; 348 349 c->bi.min_idx_lebs = min_idx_lebs; 350 return 0; 351} 352 353/** 354 * calc_idx_growth - calculate approximate index growth from budgeting request. 355 * @c: UBIFS file-system description object 356 * @req: budgeting request 357 * 358 * For now we assume each new node adds one znode. But this is rather poor 359 * approximation, though. 360 */ 361static int calc_idx_growth(const struct ubifs_info *c, 362 const struct ubifs_budget_req *req) 363{ 364 int znodes; 365 366 znodes = req->new_ino + (req->new_page << UBIFS_BLOCKS_PER_PAGE_SHIFT) + 367 req->new_dent; 368 return znodes * c->max_idx_node_sz; 369} 370 371/** 372 * calc_data_growth - calculate approximate amount of new data from budgeting 373 * request. 374 * @c: UBIFS file-system description object 375 * @req: budgeting request 376 */ 377static int calc_data_growth(const struct ubifs_info *c, 378 const struct ubifs_budget_req *req) 379{ 380 int data_growth; 381 382 data_growth = req->new_ino ? c->bi.inode_budget : 0; 383 if (req->new_page) 384 data_growth += c->bi.page_budget; 385 if (req->new_dent) 386 data_growth += c->bi.dent_budget; 387 data_growth += req->new_ino_d; 388 return data_growth; 389} 390 391/** 392 * calc_dd_growth - calculate approximate amount of data which makes other data 393 * dirty from budgeting request. 394 * @c: UBIFS file-system description object 395 * @req: budgeting request 396 */ 397static int calc_dd_growth(const struct ubifs_info *c, 398 const struct ubifs_budget_req *req) 399{ 400 int dd_growth; 401 402 dd_growth = req->dirtied_page ? c->bi.page_budget : 0; 403 404 if (req->dirtied_ino) 405 dd_growth += c->bi.inode_budget * req->dirtied_ino; 406 if (req->mod_dent) 407 dd_growth += c->bi.dent_budget; 408 dd_growth += req->dirtied_ino_d; 409 return dd_growth; 410} 411 412/** 413 * ubifs_budget_space - ensure there is enough space to complete an operation. 414 * @c: UBIFS file-system description object 415 * @req: budget request 416 * 417 * This function allocates budget for an operation. It uses pessimistic 418 * approximation of how much flash space the operation needs. The goal of this 419 * function is to make sure UBIFS always has flash space to flush all dirty 420 * pages, dirty inodes, and dirty znodes (liability). This function may force 421 * commit, garbage-collection or write-back. Returns zero in case of success, 422 * %-ENOSPC if there is no free space and other negative error codes in case of 423 * failures. 424 */ 425int ubifs_budget_space(struct ubifs_info *c, struct ubifs_budget_req *req) 426{ 427 int err, idx_growth, data_growth, dd_growth, retried = 0; 428 429 ubifs_assert(c, req->new_page <= 1); 430 ubifs_assert(c, req->dirtied_page <= 1); 431 ubifs_assert(c, req->new_dent <= 1); 432 ubifs_assert(c, req->mod_dent <= 1); 433 ubifs_assert(c, req->new_ino <= 1); 434 ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA); 435 ubifs_assert(c, req->dirtied_ino <= 4); 436 ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); 437 ubifs_assert(c, !(req->new_ino_d & 7)); 438 ubifs_assert(c, !(req->dirtied_ino_d & 7)); 439 440 data_growth = calc_data_growth(c, req); 441 dd_growth = calc_dd_growth(c, req); 442 if (!data_growth && !dd_growth) 443 return 0; 444 idx_growth = calc_idx_growth(c, req); 445 446again: 447 spin_lock(&c->space_lock); 448 ubifs_assert(c, c->bi.idx_growth >= 0); 449 ubifs_assert(c, c->bi.data_growth >= 0); 450 ubifs_assert(c, c->bi.dd_growth >= 0); 451 452 if (unlikely(c->bi.nospace) && (c->bi.nospace_rp || !can_use_rp(c))) { 453 dbg_budg("no space"); 454 spin_unlock(&c->space_lock); 455 return -ENOSPC; 456 } 457 458 c->bi.idx_growth += idx_growth; 459 c->bi.data_growth += data_growth; 460 c->bi.dd_growth += dd_growth; 461 462 err = do_budget_space(c); 463 if (likely(!err)) { 464 req->idx_growth = idx_growth; 465 req->data_growth = data_growth; 466 req->dd_growth = dd_growth; 467 spin_unlock(&c->space_lock); 468 return 0; 469 } 470 471 /* Restore the old values */ 472 c->bi.idx_growth -= idx_growth; 473 c->bi.data_growth -= data_growth; 474 c->bi.dd_growth -= dd_growth; 475 spin_unlock(&c->space_lock); 476 477 if (req->fast) { 478 dbg_budg("no space for fast budgeting"); 479 return err; 480 } 481 482 err = make_free_space(c); 483 cond_resched(); 484 if (err == -EAGAIN) { 485 dbg_budg("try again"); 486 goto again; 487 } else if (err == -ENOSPC) { 488 if (!retried) { 489 retried = 1; 490 dbg_budg("-ENOSPC, but anyway try once again"); 491 goto again; 492 } 493 dbg_budg("FS is full, -ENOSPC"); 494 c->bi.nospace = 1; 495 if (can_use_rp(c) || c->rp_size == 0) 496 c->bi.nospace_rp = 1; 497 smp_wmb(); 498 } else 499 ubifs_err(c, "cannot budget space, error %d", err); 500 return err; 501} 502 503/** 504 * ubifs_release_budget - release budgeted free space. 505 * @c: UBIFS file-system description object 506 * @req: budget request 507 * 508 * This function releases the space budgeted by 'ubifs_budget_space()'. Note, 509 * since the index changes (which were budgeted for in @req->idx_growth) will 510 * only be written to the media on commit, this function moves the index budget 511 * from @c->bi.idx_growth to @c->bi.uncommitted_idx. The latter will be zeroed 512 * by the commit operation. 513 */ 514void ubifs_release_budget(struct ubifs_info *c, struct ubifs_budget_req *req) 515{ 516 ubifs_assert(c, req->new_page <= 1); 517 ubifs_assert(c, req->dirtied_page <= 1); 518 ubifs_assert(c, req->new_dent <= 1); 519 ubifs_assert(c, req->mod_dent <= 1); 520 ubifs_assert(c, req->new_ino <= 1); 521 ubifs_assert(c, req->new_ino_d <= UBIFS_MAX_INO_DATA); 522 ubifs_assert(c, req->dirtied_ino <= 4); 523 ubifs_assert(c, req->dirtied_ino_d <= UBIFS_MAX_INO_DATA * 4); 524 ubifs_assert(c, !(req->new_ino_d & 7)); 525 ubifs_assert(c, !(req->dirtied_ino_d & 7)); 526 if (!req->recalculate) { 527 ubifs_assert(c, req->idx_growth >= 0); 528 ubifs_assert(c, req->data_growth >= 0); 529 ubifs_assert(c, req->dd_growth >= 0); 530 } 531 532 if (req->recalculate) { 533 req->data_growth = calc_data_growth(c, req); 534 req->dd_growth = calc_dd_growth(c, req); 535 req->idx_growth = calc_idx_growth(c, req); 536 } 537 538 if (!req->data_growth && !req->dd_growth) 539 return; 540 541 c->bi.nospace = c->bi.nospace_rp = 0; 542 smp_wmb(); 543 544 spin_lock(&c->space_lock); 545 c->bi.idx_growth -= req->idx_growth; 546 c->bi.uncommitted_idx += req->idx_growth; 547 c->bi.data_growth -= req->data_growth; 548 c->bi.dd_growth -= req->dd_growth; 549 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); 550 551 ubifs_assert(c, c->bi.idx_growth >= 0); 552 ubifs_assert(c, c->bi.data_growth >= 0); 553 ubifs_assert(c, c->bi.dd_growth >= 0); 554 ubifs_assert(c, c->bi.min_idx_lebs < c->main_lebs); 555 ubifs_assert(c, !(c->bi.idx_growth & 7)); 556 ubifs_assert(c, !(c->bi.data_growth & 7)); 557 ubifs_assert(c, !(c->bi.dd_growth & 7)); 558 spin_unlock(&c->space_lock); 559} 560 561/** 562 * ubifs_convert_page_budget - convert budget of a new page. 563 * @c: UBIFS file-system description object 564 * 565 * This function converts budget which was allocated for a new page of data to 566 * the budget of changing an existing page of data. The latter is smaller than 567 * the former, so this function only does simple re-calculation and does not 568 * involve any write-back. 569 */ 570void ubifs_convert_page_budget(struct ubifs_info *c) 571{ 572 spin_lock(&c->space_lock); 573 /* Release the index growth reservation */ 574 c->bi.idx_growth -= c->max_idx_node_sz << UBIFS_BLOCKS_PER_PAGE_SHIFT; 575 /* Release the data growth reservation */ 576 c->bi.data_growth -= c->bi.page_budget; 577 /* Increase the dirty data growth reservation instead */ 578 c->bi.dd_growth += c->bi.page_budget; 579 /* And re-calculate the indexing space reservation */ 580 c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); 581 spin_unlock(&c->space_lock); 582} 583 584/** 585 * ubifs_release_dirty_inode_budget - release dirty inode budget. 586 * @c: UBIFS file-system description object 587 * @ui: UBIFS inode to release the budget for 588 * 589 * This function releases budget corresponding to a dirty inode. It is usually 590 * called when after the inode has been written to the media and marked as 591 * clean. It also causes the "no space" flags to be cleared. 592 */ 593void ubifs_release_dirty_inode_budget(struct ubifs_info *c, 594 struct ubifs_inode *ui) 595{ 596 struct ubifs_budget_req req; 597 598 memset(&req, 0, sizeof(struct ubifs_budget_req)); 599 /* The "no space" flags will be cleared because dd_growth is > 0 */ 600 req.dd_growth = c->bi.inode_budget + ALIGN(ui->data_len, 8); 601 ubifs_release_budget(c, &req); 602} 603 604/** 605 * ubifs_reported_space - calculate reported free space. 606 * @c: the UBIFS file-system description object 607 * @free: amount of free space 608 * 609 * This function calculates amount of free space which will be reported to 610 * user-space. User-space application tend to expect that if the file-system 611 * (e.g., via the 'statfs()' call) reports that it has N bytes available, they 612 * are able to write a file of size N. UBIFS attaches node headers to each data 613 * node and it has to write indexing nodes as well. This introduces additional 614 * overhead, and UBIFS has to report slightly less free space to meet the above 615 * expectations. 616 * 617 * This function assumes free space is made up of uncompressed data nodes and 618 * full index nodes (one per data node, tripled because we always allow enough 619 * space to write the index thrice). 620 * 621 * Note, the calculation is pessimistic, which means that most of the time 622 * UBIFS reports less space than it actually has. 623 */ 624long long ubifs_reported_space(const struct ubifs_info *c, long long free) 625{ 626 int divisor, factor, f; 627 628 /* 629 * Reported space size is @free * X, where X is UBIFS block size 630 * divided by UBIFS block size + all overhead one data block 631 * introduces. The overhead is the node header + indexing overhead. 632 * 633 * Indexing overhead calculations are based on the following formula: 634 * I = N/(f - 1) + 1, where I - number of indexing nodes, N - number 635 * of data nodes, f - fanout. Because effective UBIFS fanout is twice 636 * as less than maximum fanout, we assume that each data node 637 * introduces 3 * @c->max_idx_node_sz / (@c->fanout/2 - 1) bytes. 638 * Note, the multiplier 3 is because UBIFS reserves thrice as more space 639 * for the index. 640 */ 641 f = c->fanout > 3 ? c->fanout >> 1 : 2; 642 factor = UBIFS_BLOCK_SIZE; 643 divisor = UBIFS_MAX_DATA_NODE_SZ; 644 divisor += (c->max_idx_node_sz * 3) / (f - 1); 645 free *= factor; 646 return div_u64(free, divisor); 647} 648 649/** 650 * ubifs_get_free_space_nolock - return amount of free space. 651 * @c: UBIFS file-system description object 652 * 653 * This function calculates amount of free space to report to user-space. 654 * 655 * Because UBIFS may introduce substantial overhead (the index, node headers, 656 * alignment, wastage at the end of LEBs, etc), it cannot report real amount of 657 * free flash space it has (well, because not all dirty space is reclaimable, 658 * UBIFS does not actually know the real amount). If UBIFS did so, it would 659 * bread user expectations about what free space is. Users seem to accustomed 660 * to assume that if the file-system reports N bytes of free space, they would 661 * be able to fit a file of N bytes to the FS. This almost works for 662 * traditional file-systems, because they have way less overhead than UBIFS. 663 * So, to keep users happy, UBIFS tries to take the overhead into account. 664 */ 665long long ubifs_get_free_space_nolock(struct ubifs_info *c) 666{ 667 int rsvd_idx_lebs, lebs; 668 long long available, outstanding, free; 669 670 ubifs_assert(c, c->bi.min_idx_lebs == ubifs_calc_min_idx_lebs(c)); 671 outstanding = c->bi.data_growth + c->bi.dd_growth; 672 available = ubifs_calc_available(c, c->bi.min_idx_lebs); 673 674 /* 675 * When reporting free space to user-space, UBIFS guarantees that it is 676 * possible to write a file of free space size. This means that for 677 * empty LEBs we may use more precise calculations than 678 * 'ubifs_calc_available()' is using. Namely, we know that in empty 679 * LEBs we would waste only @c->leb_overhead bytes, not @c->dark_wm. 680 * Thus, amend the available space. 681 * 682 * Note, the calculations below are similar to what we have in 683 * 'do_budget_space()', so refer there for comments. 684 */ 685 if (c->bi.min_idx_lebs > c->lst.idx_lebs) 686 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; 687 else 688 rsvd_idx_lebs = 0; 689 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - 690 c->lst.taken_empty_lebs; 691 lebs -= rsvd_idx_lebs; 692 available += lebs * (c->dark_wm - c->leb_overhead); 693 694 if (available > outstanding) 695 free = ubifs_reported_space(c, available - outstanding); 696 else 697 free = 0; 698 return free; 699} 700 701/** 702 * ubifs_get_free_space - return amount of free space. 703 * @c: UBIFS file-system description object 704 * 705 * This function calculates and returns amount of free space to report to 706 * user-space. 707 */ 708long long ubifs_get_free_space(struct ubifs_info *c) 709{ 710 long long free; 711 712 spin_lock(&c->space_lock); 713 free = ubifs_get_free_space_nolock(c); 714 spin_unlock(&c->space_lock); 715 716 return free; 717} 718