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 garbage collection. The procedure for garbage collection 25 * is different depending on whether a LEB as an index LEB (contains index 26 * nodes) or not. For non-index LEBs, garbage collection finds a LEB which 27 * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete 28 * nodes to the journal, at which point the garbage-collected LEB is free to be 29 * reused. For index LEBs, garbage collection marks the non-obsolete index nodes 30 * dirty in the TNC, and after the next commit, the garbage-collected LEB is 31 * to be reused. Garbage collection will cause the number of dirty index nodes 32 * to grow, however sufficient space is reserved for the index to ensure the 33 * commit will never run out of space. 34 * 35 * Notes about dead watermark. At current UBIFS implementation we assume that 36 * LEBs which have less than @c->dead_wm bytes of free + dirty space are full 37 * and not worth garbage-collecting. The dead watermark is one min. I/O unit 38 * size, or min. UBIFS node size, depending on what is greater. Indeed, UBIFS 39 * Garbage Collector has to synchronize the GC head's write buffer before 40 * returning, so this is about wasting one min. I/O unit. However, UBIFS GC can 41 * actually reclaim even very small pieces of dirty space by garbage collecting 42 * enough dirty LEBs, but we do not bother doing this at this implementation. 43 * 44 * Notes about dark watermark. The results of GC work depends on how big are 45 * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed, 46 * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would 47 * have to waste large pieces of free space at the end of LEB B, because nodes 48 * from LEB A would not fit. And the worst situation is when all nodes are of 49 * maximum size. So dark watermark is the amount of free + dirty space in LEB 50 * which are guaranteed to be reclaimable. If LEB has less space, the GC might 51 * be unable to reclaim it. So, LEBs with free + dirty greater than dark 52 * watermark are "good" LEBs from GC's point of few. The other LEBs are not so 53 * good, and GC takes extra care when moving them. 54 */ 55 56 #include <linux/pagemap.h> 57 #include <linux/list_sort.h> 58 #include "ubifs.h" 59 60 /* 61 * GC may need to move more than one LEB to make progress. The below constants 62 * define "soft" and "hard" limits on the number of LEBs the garbage collector 63 * may move. 64 */ 65 #define SOFT_LEBS_LIMIT 4 66 #define HARD_LEBS_LIMIT 32 67 68 /** 69 * switch_gc_head - switch the garbage collection journal head. 70 * @c: UBIFS file-system description object 71 * @buf: buffer to write 72 * @len: length of the buffer to write 73 * @lnum: LEB number written is returned here 74 * @offs: offset written is returned here 75 * 76 * This function switch the GC head to the next LEB which is reserved in 77 * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required, 78 * and other negative error code in case of failures. 79 */ 80 static int switch_gc_head(struct ubifs_info *c) 81 { 82 int err, gc_lnum = c->gc_lnum; 83 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; 84 85 ubifs_assert(gc_lnum != -1); 86 dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)", 87 wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum, 88 c->leb_size - wbuf->offs - wbuf->used); 89 90 err = ubifs_wbuf_sync_nolock(wbuf); 91 if (err) 92 return err; 93 94 /* 95 * The GC write-buffer was synchronized, we may safely unmap 96 * 'c->gc_lnum'. 97 */ 98 err = ubifs_leb_unmap(c, gc_lnum); 99 if (err) 100 return err; 101 102 err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0); 103 if (err) 104 return err; 105 106 c->gc_lnum = -1; 107 err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0, UBI_LONGTERM); 108 return err; 109 } 110 111 /** 112 * data_nodes_cmp - compare 2 data nodes. 113 * @priv: UBIFS file-system description object 114 * @a: first data node 115 * @a: second data node 116 * 117 * This function compares data nodes @a and @b. Returns %1 if @a has greater 118 * inode or block number, and %-1 otherwise. 119 */ 120 int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) 121 { 122 ino_t inuma, inumb; 123 struct ubifs_info *c = priv; 124 struct ubifs_scan_node *sa, *sb; 125 126 cond_resched(); 127 sa = list_entry(a, struct ubifs_scan_node, list); 128 sb = list_entry(b, struct ubifs_scan_node, list); 129 ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY); 130 ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY); 131 132 inuma = key_inum(c, &sa->key); 133 inumb = key_inum(c, &sb->key); 134 135 if (inuma == inumb) { 136 unsigned int blka = key_block(c, &sa->key); 137 unsigned int blkb = key_block(c, &sb->key); 138 139 if (blka <= blkb) 140 return -1; 141 } else if (inuma <= inumb) 142 return -1; 143 144 return 1; 145 } 146 147 /* 148 * nondata_nodes_cmp - compare 2 non-data nodes. 149 * @priv: UBIFS file-system description object 150 * @a: first node 151 * @a: second node 152 * 153 * This function compares nodes @a and @b. It makes sure that inode nodes go 154 * first and sorted by length in descending order. Directory entry nodes go 155 * after inode nodes and are sorted in ascending hash valuer order. 156 */ 157 int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) 158 { 159 int typea, typeb; 160 ino_t inuma, inumb; 161 struct ubifs_info *c = priv; 162 struct ubifs_scan_node *sa, *sb; 163 164 cond_resched(); 165 sa = list_entry(a, struct ubifs_scan_node, list); 166 sb = list_entry(b, struct ubifs_scan_node, list); 167 typea = key_type(c, &sa->key); 168 typeb = key_type(c, &sb->key); 169 ubifs_assert(typea != UBIFS_DATA_KEY && typeb != UBIFS_DATA_KEY); 170 171 /* Inodes go before directory entries */ 172 if (typea == UBIFS_INO_KEY) { 173 if (typeb == UBIFS_INO_KEY) 174 return sb->len - sa->len; 175 return -1; 176 } 177 if (typeb == UBIFS_INO_KEY) 178 return 1; 179 180 ubifs_assert(typea == UBIFS_DENT_KEY && typeb == UBIFS_DENT_KEY); 181 inuma = key_inum(c, &sa->key); 182 inumb = key_inum(c, &sb->key); 183 184 if (inuma == inumb) { 185 uint32_t hasha = key_hash(c, &sa->key); 186 uint32_t hashb = key_hash(c, &sb->key); 187 188 if (hasha <= hashb) 189 return -1; 190 } else if (inuma <= inumb) 191 return -1; 192 193 return 1; 194 } 195 196 /** 197 * sort_nodes - sort nodes for GC. 198 * @c: UBIFS file-system description object 199 * @sleb: describes nodes to sort and contains the result on exit 200 * @nondata: contains non-data nodes on exit 201 * @min: minimum node size is returned here 202 * 203 * This function sorts the list of inodes to garbage collect. First of all, it 204 * kills obsolete nodes and separates data and non-data nodes to the 205 * @sleb->nodes and @nondata lists correspondingly. 206 * 207 * Data nodes are then sorted in block number order - this is important for 208 * bulk-read; data nodes with lower inode number go before data nodes with 209 * higher inode number, and data nodes with lower block number go before data 210 * nodes with higher block number; 211 * 212 * Non-data nodes are sorted as follows. 213 * o First go inode nodes - they are sorted in descending length order. 214 * o Then go directory entry nodes - they are sorted in hash order, which 215 * should supposedly optimize 'readdir()'. Direntry nodes with lower parent 216 * inode number go before direntry nodes with higher parent inode number, 217 * and direntry nodes with lower name hash values go before direntry nodes 218 * with higher name hash values. 219 * 220 * This function returns zero in case of success and a negative error code in 221 * case of failure. 222 */ 223 static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb, 224 struct list_head *nondata, int *min) 225 { 226 struct ubifs_scan_node *snod, *tmp; 227 228 *min = INT_MAX; 229 230 /* Separate data nodes and non-data nodes */ 231 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { 232 int err; 233 234 ubifs_assert(snod->type != UBIFS_IDX_NODE); 235 ubifs_assert(snod->type != UBIFS_REF_NODE); 236 ubifs_assert(snod->type != UBIFS_CS_NODE); 237 238 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum, 239 snod->offs, 0); 240 if (err < 0) 241 return err; 242 243 if (!err) { 244 /* The node is obsolete, remove it from the list */ 245 list_del(&snod->list); 246 kfree(snod); 247 continue; 248 } 249 250 if (snod->len < *min) 251 *min = snod->len; 252 253 if (key_type(c, &snod->key) != UBIFS_DATA_KEY) 254 list_move_tail(&snod->list, nondata); 255 } 256 257 /* Sort data and non-data nodes */ 258 list_sort(c, &sleb->nodes, &data_nodes_cmp); 259 list_sort(c, nondata, &nondata_nodes_cmp); 260 return 0; 261 } 262 263 /** 264 * move_node - move a node. 265 * @c: UBIFS file-system description object 266 * @sleb: describes the LEB to move nodes from 267 * @snod: the mode to move 268 * @wbuf: write-buffer to move node to 269 * 270 * This function moves node @snod to @wbuf, changes TNC correspondingly, and 271 * destroys @snod. Returns zero in case of success and a negative error code in 272 * case of failure. 273 */ 274 static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb, 275 struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf) 276 { 277 int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used; 278 279 cond_resched(); 280 err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len); 281 if (err) 282 return err; 283 284 err = ubifs_tnc_replace(c, &snod->key, sleb->lnum, 285 snod->offs, new_lnum, new_offs, 286 snod->len); 287 list_del(&snod->list); 288 kfree(snod); 289 return err; 290 } 291 292 /** 293 * move_nodes - move nodes. 294 * @c: UBIFS file-system description object 295 * @sleb: describes the LEB to move nodes from 296 * 297 * This function moves valid nodes from data LEB described by @sleb to the GC 298 * journal head. This function returns zero in case of success, %-EAGAIN if 299 * commit is required, and other negative error codes in case of other 300 * failures. 301 */ 302 static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb) 303 { 304 int err, min; 305 LIST_HEAD(nondata); 306 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; 307 308 if (wbuf->lnum == -1) { 309 /* 310 * The GC journal head is not set, because it is the first GC 311 * invocation since mount. 312 */ 313 err = switch_gc_head(c); 314 if (err) 315 return err; 316 } 317 318 err = sort_nodes(c, sleb, &nondata, &min); 319 if (err) 320 goto out; 321 322 /* Write nodes to their new location. Use the first-fit strategy */ 323 while (1) { 324 int avail; 325 struct ubifs_scan_node *snod, *tmp; 326 327 /* Move data nodes */ 328 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { 329 avail = c->leb_size - wbuf->offs - wbuf->used; 330 if (snod->len > avail) 331 /* 332 * Do not skip data nodes in order to optimize 333 * bulk-read. 334 */ 335 break; 336 337 err = move_node(c, sleb, snod, wbuf); 338 if (err) 339 goto out; 340 } 341 342 /* Move non-data nodes */ 343 list_for_each_entry_safe(snod, tmp, &nondata, list) { 344 avail = c->leb_size - wbuf->offs - wbuf->used; 345 if (avail < min) 346 break; 347 348 if (snod->len > avail) { 349 /* 350 * Keep going only if this is an inode with 351 * some data. Otherwise stop and switch the GC 352 * head. IOW, we assume that data-less inode 353 * nodes and direntry nodes are roughly of the 354 * same size. 355 */ 356 if (key_type(c, &snod->key) == UBIFS_DENT_KEY || 357 snod->len == UBIFS_INO_NODE_SZ) 358 break; 359 continue; 360 } 361 362 err = move_node(c, sleb, snod, wbuf); 363 if (err) 364 goto out; 365 } 366 367 if (list_empty(&sleb->nodes) && list_empty(&nondata)) 368 break; 369 370 /* 371 * Waste the rest of the space in the LEB and switch to the 372 * next LEB. 373 */ 374 err = switch_gc_head(c); 375 if (err) 376 goto out; 377 } 378 379 return 0; 380 381 out: 382 list_splice_tail(&nondata, &sleb->nodes); 383 return err; 384 } 385 386 /** 387 * gc_sync_wbufs - sync write-buffers for GC. 388 * @c: UBIFS file-system description object 389 * 390 * We must guarantee that obsoleting nodes are on flash. Unfortunately they may 391 * be in a write-buffer instead. That is, a node could be written to a 392 * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is 393 * erased before the write-buffer is sync'd and then there is an unclean 394 * unmount, then an existing node is lost. To avoid this, we sync all 395 * write-buffers. 396 * 397 * This function returns %0 on success or a negative error code on failure. 398 */ 399 static int gc_sync_wbufs(struct ubifs_info *c) 400 { 401 int err, i; 402 403 for (i = 0; i < c->jhead_cnt; i++) { 404 if (i == GCHD) 405 continue; 406 err = ubifs_wbuf_sync(&c->jheads[i].wbuf); 407 if (err) 408 return err; 409 } 410 return 0; 411 } 412 413 /** 414 * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock. 415 * @c: UBIFS file-system description object 416 * @lp: describes the LEB to garbage collect 417 * 418 * This function garbage-collects an LEB and returns one of the @LEB_FREED, 419 * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is 420 * required, and other negative error codes in case of failures. 421 */ 422 int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp) 423 { 424 struct ubifs_scan_leb *sleb; 425 struct ubifs_scan_node *snod; 426 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; 427 int err = 0, lnum = lp->lnum; 428 429 ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 || 430 c->need_recovery); 431 ubifs_assert(c->gc_lnum != lnum); 432 ubifs_assert(wbuf->lnum != lnum); 433 434 /* 435 * We scan the entire LEB even though we only really need to scan up to 436 * (c->leb_size - lp->free). 437 */ 438 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); 439 if (IS_ERR(sleb)) 440 return PTR_ERR(sleb); 441 442 ubifs_assert(!list_empty(&sleb->nodes)); 443 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list); 444 445 if (snod->type == UBIFS_IDX_NODE) { 446 struct ubifs_gced_idx_leb *idx_gc; 447 448 dbg_gc("indexing LEB %d (free %d, dirty %d)", 449 lnum, lp->free, lp->dirty); 450 list_for_each_entry(snod, &sleb->nodes, list) { 451 struct ubifs_idx_node *idx = snod->node; 452 int level = le16_to_cpu(idx->level); 453 454 ubifs_assert(snod->type == UBIFS_IDX_NODE); 455 key_read(c, ubifs_idx_key(c, idx), &snod->key); 456 err = ubifs_dirty_idx_node(c, &snod->key, level, lnum, 457 snod->offs); 458 if (err) 459 goto out; 460 } 461 462 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS); 463 if (!idx_gc) { 464 err = -ENOMEM; 465 goto out; 466 } 467 468 idx_gc->lnum = lnum; 469 idx_gc->unmap = 0; 470 list_add(&idx_gc->list, &c->idx_gc); 471 472 /* 473 * Don't release the LEB until after the next commit, because 474 * it may contain data which is needed for recovery. So 475 * although we freed this LEB, it will become usable only after 476 * the commit. 477 */ 478 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 479 LPROPS_INDEX, 1); 480 if (err) 481 goto out; 482 err = LEB_FREED_IDX; 483 } else { 484 dbg_gc("data LEB %d (free %d, dirty %d)", 485 lnum, lp->free, lp->dirty); 486 487 err = move_nodes(c, sleb); 488 if (err) 489 goto out_inc_seq; 490 491 err = gc_sync_wbufs(c); 492 if (err) 493 goto out_inc_seq; 494 495 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0); 496 if (err) 497 goto out_inc_seq; 498 499 /* Allow for races with TNC */ 500 c->gced_lnum = lnum; 501 smp_wmb(); 502 c->gc_seq += 1; 503 smp_wmb(); 504 505 if (c->gc_lnum == -1) { 506 c->gc_lnum = lnum; 507 err = LEB_RETAINED; 508 } else { 509 err = ubifs_wbuf_sync_nolock(wbuf); 510 if (err) 511 goto out; 512 513 err = ubifs_leb_unmap(c, lnum); 514 if (err) 515 goto out; 516 517 err = LEB_FREED; 518 } 519 } 520 521 out: 522 ubifs_scan_destroy(sleb); 523 return err; 524 525 out_inc_seq: 526 /* We may have moved at least some nodes so allow for races with TNC */ 527 c->gced_lnum = lnum; 528 smp_wmb(); 529 c->gc_seq += 1; 530 smp_wmb(); 531 goto out; 532 } 533 534 /** 535 * ubifs_garbage_collect - UBIFS garbage collector. 536 * @c: UBIFS file-system description object 537 * @anyway: do GC even if there are free LEBs 538 * 539 * This function does out-of-place garbage collection. The return codes are: 540 * o positive LEB number if the LEB has been freed and may be used; 541 * o %-EAGAIN if the caller has to run commit; 542 * o %-ENOSPC if GC failed to make any progress; 543 * o other negative error codes in case of other errors. 544 * 545 * Garbage collector writes data to the journal when GC'ing data LEBs, and just 546 * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point 547 * commit may be required. But commit cannot be run from inside GC, because the 548 * caller might be holding the commit lock, so %-EAGAIN is returned instead; 549 * And this error code means that the caller has to run commit, and re-run GC 550 * if there is still no free space. 551 * 552 * There are many reasons why this function may return %-EAGAIN: 553 * o the log is full and there is no space to write an LEB reference for 554 * @c->gc_lnum; 555 * o the journal is too large and exceeds size limitations; 556 * o GC moved indexing LEBs, but they can be used only after the commit; 557 * o the shrinker fails to find clean znodes to free and requests the commit; 558 * o etc. 559 * 560 * Note, if the file-system is close to be full, this function may return 561 * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of 562 * the function. E.g., this happens if the limits on the journal size are too 563 * tough and GC writes too much to the journal before an LEB is freed. This 564 * might also mean that the journal is too large, and the TNC becomes to big, 565 * so that the shrinker is constantly called, finds not clean znodes to free, 566 * and requests commit. Well, this may also happen if the journal is all right, 567 * but another kernel process consumes too much memory. Anyway, infinite 568 * %-EAGAIN may happen, but in some extreme/misconfiguration cases. 569 */ 570 int ubifs_garbage_collect(struct ubifs_info *c, int anyway) 571 { 572 int i, err, ret, min_space = c->dead_wm; 573 struct ubifs_lprops lp; 574 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; 575 576 ubifs_assert_cmt_locked(c); 577 578 if (ubifs_gc_should_commit(c)) 579 return -EAGAIN; 580 581 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); 582 583 if (c->ro_media) { 584 ret = -EROFS; 585 goto out_unlock; 586 } 587 588 /* We expect the write-buffer to be empty on entry */ 589 ubifs_assert(!wbuf->used); 590 591 for (i = 0; ; i++) { 592 int space_before = c->leb_size - wbuf->offs - wbuf->used; 593 int space_after; 594 595 cond_resched(); 596 597 /* Give the commit an opportunity to run */ 598 if (ubifs_gc_should_commit(c)) { 599 ret = -EAGAIN; 600 break; 601 } 602 603 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) { 604 /* 605 * We've done enough iterations. Indexing LEBs were 606 * moved and will be available after the commit. 607 */ 608 dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN"); 609 ubifs_commit_required(c); 610 ret = -EAGAIN; 611 break; 612 } 613 614 if (i > HARD_LEBS_LIMIT) { 615 /* 616 * We've moved too many LEBs and have not made 617 * progress, give up. 618 */ 619 dbg_gc("hard limit, -ENOSPC"); 620 ret = -ENOSPC; 621 break; 622 } 623 624 /* 625 * Empty and freeable LEBs can turn up while we waited for 626 * the wbuf lock, or while we have been running GC. In that 627 * case, we should just return one of those instead of 628 * continuing to GC dirty LEBs. Hence we request 629 * 'ubifs_find_dirty_leb()' to return an empty LEB if it can. 630 */ 631 ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1); 632 if (ret) { 633 if (ret == -ENOSPC) 634 dbg_gc("no more dirty LEBs"); 635 break; 636 } 637 638 dbg_gc("found LEB %d: free %d, dirty %d, sum %d " 639 "(min. space %d)", lp.lnum, lp.free, lp.dirty, 640 lp.free + lp.dirty, min_space); 641 642 if (lp.free + lp.dirty == c->leb_size) { 643 /* An empty LEB was returned */ 644 dbg_gc("LEB %d is free, return it", lp.lnum); 645 /* 646 * ubifs_find_dirty_leb() doesn't return freeable index 647 * LEBs. 648 */ 649 ubifs_assert(!(lp.flags & LPROPS_INDEX)); 650 if (lp.free != c->leb_size) { 651 /* 652 * Write buffers must be sync'd before 653 * unmapping freeable LEBs, because one of them 654 * may contain data which obsoletes something 655 * in 'lp.pnum'. 656 */ 657 ret = gc_sync_wbufs(c); 658 if (ret) 659 goto out; 660 ret = ubifs_change_one_lp(c, lp.lnum, 661 c->leb_size, 0, 0, 0, 662 0); 663 if (ret) 664 goto out; 665 } 666 ret = ubifs_leb_unmap(c, lp.lnum); 667 if (ret) 668 goto out; 669 ret = lp.lnum; 670 break; 671 } 672 673 space_before = c->leb_size - wbuf->offs - wbuf->used; 674 if (wbuf->lnum == -1) 675 space_before = 0; 676 677 ret = ubifs_garbage_collect_leb(c, &lp); 678 if (ret < 0) { 679 if (ret == -EAGAIN || ret == -ENOSPC) { 680 /* 681 * These codes are not errors, so we have to 682 * return the LEB to lprops. But if the 683 * 'ubifs_return_leb()' function fails, its 684 * failure code is propagated to the caller 685 * instead of the original '-EAGAIN' or 686 * '-ENOSPC'. 687 */ 688 err = ubifs_return_leb(c, lp.lnum); 689 if (err) 690 ret = err; 691 break; 692 } 693 goto out; 694 } 695 696 if (ret == LEB_FREED) { 697 /* An LEB has been freed and is ready for use */ 698 dbg_gc("LEB %d freed, return", lp.lnum); 699 ret = lp.lnum; 700 break; 701 } 702 703 if (ret == LEB_FREED_IDX) { 704 /* 705 * This was an indexing LEB and it cannot be 706 * immediately used. And instead of requesting the 707 * commit straight away, we try to garbage collect some 708 * more. 709 */ 710 dbg_gc("indexing LEB %d freed, continue", lp.lnum); 711 continue; 712 } 713 714 ubifs_assert(ret == LEB_RETAINED); 715 space_after = c->leb_size - wbuf->offs - wbuf->used; 716 dbg_gc("LEB %d retained, freed %d bytes", lp.lnum, 717 space_after - space_before); 718 719 if (space_after > space_before) { 720 /* GC makes progress, keep working */ 721 min_space >>= 1; 722 if (min_space < c->dead_wm) 723 min_space = c->dead_wm; 724 continue; 725 } 726 727 dbg_gc("did not make progress"); 728 729 /* 730 * GC moved an LEB bud have not done any progress. This means 731 * that the previous GC head LEB contained too few free space 732 * and the LEB which was GC'ed contained only large nodes which 733 * did not fit that space. 734 * 735 * We can do 2 things: 736 * 1. pick another LEB in a hope it'll contain a small node 737 * which will fit the space we have at the end of current GC 738 * head LEB, but there is no guarantee, so we try this out 739 * unless we have already been working for too long; 740 * 2. request an LEB with more dirty space, which will force 741 * 'ubifs_find_dirty_leb()' to start scanning the lprops 742 * table, instead of just picking one from the heap 743 * (previously it already picked the dirtiest LEB). 744 */ 745 if (i < SOFT_LEBS_LIMIT) { 746 dbg_gc("try again"); 747 continue; 748 } 749 750 min_space <<= 1; 751 if (min_space > c->dark_wm) 752 min_space = c->dark_wm; 753 dbg_gc("set min. space to %d", min_space); 754 } 755 756 if (ret == -ENOSPC && !list_empty(&c->idx_gc)) { 757 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN"); 758 ubifs_commit_required(c); 759 ret = -EAGAIN; 760 } 761 762 err = ubifs_wbuf_sync_nolock(wbuf); 763 if (!err) 764 err = ubifs_leb_unmap(c, c->gc_lnum); 765 if (err) { 766 ret = err; 767 goto out; 768 } 769 out_unlock: 770 mutex_unlock(&wbuf->io_mutex); 771 return ret; 772 773 out: 774 ubifs_assert(ret < 0); 775 ubifs_assert(ret != -ENOSPC && ret != -EAGAIN); 776 ubifs_ro_mode(c, ret); 777 ubifs_wbuf_sync_nolock(wbuf); 778 mutex_unlock(&wbuf->io_mutex); 779 ubifs_return_leb(c, lp.lnum); 780 return ret; 781 } 782 783 /** 784 * ubifs_gc_start_commit - garbage collection at start of commit. 785 * @c: UBIFS file-system description object 786 * 787 * If a LEB has only dirty and free space, then we may safely unmap it and make 788 * it free. Note, we cannot do this with indexing LEBs because dirty space may 789 * correspond index nodes that are required for recovery. In that case, the 790 * LEB cannot be unmapped until after the next commit. 791 * 792 * This function returns %0 upon success and a negative error code upon failure. 793 */ 794 int ubifs_gc_start_commit(struct ubifs_info *c) 795 { 796 struct ubifs_gced_idx_leb *idx_gc; 797 const struct ubifs_lprops *lp; 798 int err = 0, flags; 799 800 ubifs_get_lprops(c); 801 802 /* 803 * Unmap (non-index) freeable LEBs. Note that recovery requires that all 804 * wbufs are sync'd before this, which is done in 'do_commit()'. 805 */ 806 while (1) { 807 lp = ubifs_fast_find_freeable(c); 808 if (IS_ERR(lp)) { 809 err = PTR_ERR(lp); 810 goto out; 811 } 812 if (!lp) 813 break; 814 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); 815 ubifs_assert(!(lp->flags & LPROPS_INDEX)); 816 err = ubifs_leb_unmap(c, lp->lnum); 817 if (err) 818 goto out; 819 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0); 820 if (IS_ERR(lp)) { 821 err = PTR_ERR(lp); 822 goto out; 823 } 824 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); 825 ubifs_assert(!(lp->flags & LPROPS_INDEX)); 826 } 827 828 /* Mark GC'd index LEBs OK to unmap after this commit finishes */ 829 list_for_each_entry(idx_gc, &c->idx_gc, list) 830 idx_gc->unmap = 1; 831 832 /* Record index freeable LEBs for unmapping after commit */ 833 while (1) { 834 lp = ubifs_fast_find_frdi_idx(c); 835 if (IS_ERR(lp)) { 836 err = PTR_ERR(lp); 837 goto out; 838 } 839 if (!lp) 840 break; 841 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS); 842 if (!idx_gc) { 843 err = -ENOMEM; 844 goto out; 845 } 846 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); 847 ubifs_assert(lp->flags & LPROPS_INDEX); 848 /* Don't release the LEB until after the next commit */ 849 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX; 850 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1); 851 if (IS_ERR(lp)) { 852 err = PTR_ERR(lp); 853 kfree(idx_gc); 854 goto out; 855 } 856 ubifs_assert(lp->flags & LPROPS_TAKEN); 857 ubifs_assert(!(lp->flags & LPROPS_INDEX)); 858 idx_gc->lnum = lp->lnum; 859 idx_gc->unmap = 1; 860 list_add(&idx_gc->list, &c->idx_gc); 861 } 862 out: 863 ubifs_release_lprops(c); 864 return err; 865 } 866 867 /** 868 * ubifs_gc_end_commit - garbage collection at end of commit. 869 * @c: UBIFS file-system description object 870 * 871 * This function completes out-of-place garbage collection of index LEBs. 872 */ 873 int ubifs_gc_end_commit(struct ubifs_info *c) 874 { 875 struct ubifs_gced_idx_leb *idx_gc, *tmp; 876 struct ubifs_wbuf *wbuf; 877 int err = 0; 878 879 wbuf = &c->jheads[GCHD].wbuf; 880 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); 881 list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list) 882 if (idx_gc->unmap) { 883 dbg_gc("LEB %d", idx_gc->lnum); 884 err = ubifs_leb_unmap(c, idx_gc->lnum); 885 if (err) 886 goto out; 887 err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC, 888 LPROPS_NC, 0, LPROPS_TAKEN, -1); 889 if (err) 890 goto out; 891 list_del(&idx_gc->list); 892 kfree(idx_gc); 893 } 894 out: 895 mutex_unlock(&wbuf->io_mutex); 896 return err; 897 } 898 899 /** 900 * ubifs_destroy_idx_gc - destroy idx_gc list. 901 * @c: UBIFS file-system description object 902 * 903 * This function destroys the @c->idx_gc list. It is called when unmounting 904 * so locks are not needed. Returns zero in case of success and a negative 905 * error code in case of failure. 906 */ 907 void ubifs_destroy_idx_gc(struct ubifs_info *c) 908 { 909 while (!list_empty(&c->idx_gc)) { 910 struct ubifs_gced_idx_leb *idx_gc; 911 912 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, 913 list); 914 c->idx_gc_cnt -= 1; 915 list_del(&idx_gc->list); 916 kfree(idx_gc); 917 } 918 } 919 920 /** 921 * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list. 922 * @c: UBIFS file-system description object 923 * 924 * Called during start commit so locks are not needed. 925 */ 926 int ubifs_get_idx_gc_leb(struct ubifs_info *c) 927 { 928 struct ubifs_gced_idx_leb *idx_gc; 929 int lnum; 930 931 if (list_empty(&c->idx_gc)) 932 return -ENOSPC; 933 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list); 934 lnum = idx_gc->lnum; 935 /* c->idx_gc_cnt is updated by the caller when lprops are updated */ 936 list_del(&idx_gc->list); 937 kfree(idx_gc); 938 return lnum; 939 } 940