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