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: Artem Bityutskiy (Битюцкий Артём) 20 * Adrian Hunter 21 */ 22 23 /* 24 * This file contains functions for finding LEBs for various purposes e.g. 25 * garbage collection. In general, lprops category heaps and lists are used 26 * for fast access, falling back on scanning the LPT as a last resort. 27 */ 28 29 #include <linux/sort.h> 30 #include "ubifs.h" 31 32 /** 33 * struct scan_data - data provided to scan callback functions 34 * @min_space: minimum number of bytes for which to scan 35 * @pick_free: whether it is OK to scan for empty LEBs 36 * @lnum: LEB number found is returned here 37 * @exclude_index: whether to exclude index LEBs 38 */ 39 struct scan_data { 40 int min_space; 41 int pick_free; 42 int lnum; 43 int exclude_index; 44 }; 45 46 /** 47 * valuable - determine whether LEB properties are valuable. 48 * @c: the UBIFS file-system description object 49 * @lprops: LEB properties 50 * 51 * This function return %1 if the LEB properties should be added to the LEB 52 * properties tree in memory. Otherwise %0 is returned. 53 */ 54 static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops) 55 { 56 int n, cat = lprops->flags & LPROPS_CAT_MASK; 57 struct ubifs_lpt_heap *heap; 58 59 switch (cat) { 60 case LPROPS_DIRTY: 61 case LPROPS_DIRTY_IDX: 62 case LPROPS_FREE: 63 heap = &c->lpt_heap[cat - 1]; 64 if (heap->cnt < heap->max_cnt) 65 return 1; 66 if (lprops->free + lprops->dirty >= c->dark_wm) 67 return 1; 68 return 0; 69 case LPROPS_EMPTY: 70 n = c->lst.empty_lebs + c->freeable_cnt - 71 c->lst.taken_empty_lebs; 72 if (n < c->lsave_cnt) 73 return 1; 74 return 0; 75 case LPROPS_FREEABLE: 76 return 1; 77 case LPROPS_FRDI_IDX: 78 return 1; 79 } 80 return 0; 81 } 82 83 /** 84 * scan_for_dirty_cb - dirty space scan callback. 85 * @c: the UBIFS file-system description object 86 * @lprops: LEB properties to scan 87 * @in_tree: whether the LEB properties are in main memory 88 * @data: information passed to and from the caller of the scan 89 * 90 * This function returns a code that indicates whether the scan should continue 91 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree 92 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop 93 * (%LPT_SCAN_STOP). 94 */ 95 static int scan_for_dirty_cb(struct ubifs_info *c, 96 const struct ubifs_lprops *lprops, int in_tree, 97 struct scan_data *data) 98 { 99 int ret = LPT_SCAN_CONTINUE; 100 101 /* Exclude LEBs that are currently in use */ 102 if (lprops->flags & LPROPS_TAKEN) 103 return LPT_SCAN_CONTINUE; 104 /* Determine whether to add these LEB properties to the tree */ 105 if (!in_tree && valuable(c, lprops)) 106 ret |= LPT_SCAN_ADD; 107 /* Exclude LEBs with too little space */ 108 if (lprops->free + lprops->dirty < data->min_space) 109 return ret; 110 /* If specified, exclude index LEBs */ 111 if (data->exclude_index && lprops->flags & LPROPS_INDEX) 112 return ret; 113 /* If specified, exclude empty or freeable LEBs */ 114 if (lprops->free + lprops->dirty == c->leb_size) { 115 if (!data->pick_free) 116 return ret; 117 /* Exclude LEBs with too little dirty space (unless it is empty) */ 118 } else if (lprops->dirty < c->dead_wm) 119 return ret; 120 /* Finally we found space */ 121 data->lnum = lprops->lnum; 122 return LPT_SCAN_ADD | LPT_SCAN_STOP; 123 } 124 125 /** 126 * scan_for_dirty - find a data LEB with free space. 127 * @c: the UBIFS file-system description object 128 * @min_space: minimum amount free plus dirty space the returned LEB has to 129 * have 130 * @pick_free: if it is OK to return a free or freeable LEB 131 * @exclude_index: whether to exclude index LEBs 132 * 133 * This function returns a pointer to the LEB properties found or a negative 134 * error code. 135 */ 136 static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c, 137 int min_space, int pick_free, 138 int exclude_index) 139 { 140 const struct ubifs_lprops *lprops; 141 struct ubifs_lpt_heap *heap; 142 struct scan_data data; 143 int err, i; 144 145 /* There may be an LEB with enough dirty space on the free heap */ 146 heap = &c->lpt_heap[LPROPS_FREE - 1]; 147 for (i = 0; i < heap->cnt; i++) { 148 lprops = heap->arr[i]; 149 if (lprops->free + lprops->dirty < min_space) 150 continue; 151 if (lprops->dirty < c->dead_wm) 152 continue; 153 return lprops; 154 } 155 /* 156 * A LEB may have fallen off of the bottom of the dirty heap, and ended 157 * up as uncategorized even though it has enough dirty space for us now, 158 * so check the uncategorized list. N.B. neither empty nor freeable LEBs 159 * can end up as uncategorized because they are kept on lists not 160 * finite-sized heaps. 161 */ 162 list_for_each_entry(lprops, &c->uncat_list, list) { 163 if (lprops->flags & LPROPS_TAKEN) 164 continue; 165 if (lprops->free + lprops->dirty < min_space) 166 continue; 167 if (exclude_index && (lprops->flags & LPROPS_INDEX)) 168 continue; 169 if (lprops->dirty < c->dead_wm) 170 continue; 171 return lprops; 172 } 173 /* We have looked everywhere in main memory, now scan the flash */ 174 if (c->pnodes_have >= c->pnode_cnt) 175 /* All pnodes are in memory, so skip scan */ 176 return ERR_PTR(-ENOSPC); 177 data.min_space = min_space; 178 data.pick_free = pick_free; 179 data.lnum = -1; 180 data.exclude_index = exclude_index; 181 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, 182 (ubifs_lpt_scan_callback)scan_for_dirty_cb, 183 &data); 184 if (err) 185 return ERR_PTR(err); 186 ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); 187 c->lscan_lnum = data.lnum; 188 lprops = ubifs_lpt_lookup_dirty(c, data.lnum); 189 if (IS_ERR(lprops)) 190 return lprops; 191 ubifs_assert(lprops->lnum == data.lnum); 192 ubifs_assert(lprops->free + lprops->dirty >= min_space); 193 ubifs_assert(lprops->dirty >= c->dead_wm || 194 (pick_free && 195 lprops->free + lprops->dirty == c->leb_size)); 196 ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); 197 ubifs_assert(!exclude_index || !(lprops->flags & LPROPS_INDEX)); 198 return lprops; 199 } 200 201 /** 202 * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector. 203 * @c: the UBIFS file-system description object 204 * @ret_lp: LEB properties are returned here on exit 205 * @min_space: minimum amount free plus dirty space the returned LEB has to 206 * have 207 * @pick_free: controls whether it is OK to pick empty or index LEBs 208 * 209 * This function tries to find a dirty logical eraseblock which has at least 210 * @min_space free and dirty space. It prefers to take an LEB from the dirty or 211 * dirty index heap, and it falls-back to LPT scanning if the heaps are empty 212 * or do not have an LEB which satisfies the @min_space criteria. 213 * 214 * Note, LEBs which have less than dead watermark of free + dirty space are 215 * never picked by this function. 216 * 217 * The additional @pick_free argument controls if this function has to return a 218 * free or freeable LEB if one is present. For example, GC must to set it to %1, 219 * when called from the journal space reservation function, because the 220 * appearance of free space may coincide with the loss of enough dirty space 221 * for GC to succeed anyway. 222 * 223 * In contrast, if the Garbage Collector is called from budgeting, it should 224 * just make free space, not return LEBs which are already free or freeable. 225 * 226 * In addition @pick_free is set to %2 by the recovery process in order to 227 * recover gc_lnum in which case an index LEB must not be returned. 228 * 229 * This function returns zero and the LEB properties of found dirty LEB in case 230 * of success, %-ENOSPC if no dirty LEB was found and a negative error code in 231 * case of other failures. The returned LEB is marked as "taken". 232 */ 233 int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp, 234 int min_space, int pick_free) 235 { 236 int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0; 237 const struct ubifs_lprops *lp = NULL, *idx_lp = NULL; 238 struct ubifs_lpt_heap *heap, *idx_heap; 239 240 ubifs_get_lprops(c); 241 242 if (pick_free) { 243 int lebs, rsvd_idx_lebs = 0; 244 245 spin_lock(&c->space_lock); 246 lebs = c->lst.empty_lebs + c->idx_gc_cnt; 247 lebs += c->freeable_cnt - c->lst.taken_empty_lebs; 248 249 /* 250 * Note, the index may consume more LEBs than have been reserved 251 * for it. It is OK because it might be consolidated by GC. 252 * But if the index takes fewer LEBs than it is reserved for it, 253 * this function must avoid picking those reserved LEBs. 254 */ 255 if (c->bi.min_idx_lebs >= c->lst.idx_lebs) { 256 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; 257 exclude_index = 1; 258 } 259 spin_unlock(&c->space_lock); 260 261 /* Check if there are enough free LEBs for the index */ 262 if (rsvd_idx_lebs < lebs) { 263 /* OK, try to find an empty LEB */ 264 lp = ubifs_fast_find_empty(c); 265 if (lp) 266 goto found; 267 268 /* Or a freeable LEB */ 269 lp = ubifs_fast_find_freeable(c); 270 if (lp) 271 goto found; 272 } else 273 /* 274 * We cannot pick free/freeable LEBs in the below code. 275 */ 276 pick_free = 0; 277 } else { 278 spin_lock(&c->space_lock); 279 exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs); 280 spin_unlock(&c->space_lock); 281 } 282 283 /* Look on the dirty and dirty index heaps */ 284 heap = &c->lpt_heap[LPROPS_DIRTY - 1]; 285 idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; 286 287 if (idx_heap->cnt && !exclude_index) { 288 idx_lp = idx_heap->arr[0]; 289 sum = idx_lp->free + idx_lp->dirty; 290 /* 291 * Since we reserve thrice as much space for the index than it 292 * actually takes, it does not make sense to pick indexing LEBs 293 * with less than, say, half LEB of dirty space. May be half is 294 * not the optimal boundary - this should be tested and 295 * checked. This boundary should determine how much we use 296 * in-the-gaps to consolidate the index comparing to how much 297 * we use garbage collector to consolidate it. The "half" 298 * criteria just feels to be fine. 299 */ 300 if (sum < min_space || sum < c->half_leb_size) 301 idx_lp = NULL; 302 } 303 304 if (heap->cnt) { 305 lp = heap->arr[0]; 306 if (lp->dirty + lp->free < min_space) 307 lp = NULL; 308 } 309 310 /* Pick the LEB with most space */ 311 if (idx_lp && lp) { 312 if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty) 313 lp = idx_lp; 314 } else if (idx_lp && !lp) 315 lp = idx_lp; 316 317 if (lp) { 318 ubifs_assert(lp->free + lp->dirty >= c->dead_wm); 319 goto found; 320 } 321 322 /* Did not find a dirty LEB on the dirty heaps, have to scan */ 323 dbg_find("scanning LPT for a dirty LEB"); 324 lp = scan_for_dirty(c, min_space, pick_free, exclude_index); 325 if (IS_ERR(lp)) { 326 err = PTR_ERR(lp); 327 goto out; 328 } 329 ubifs_assert(lp->dirty >= c->dead_wm || 330 (pick_free && lp->free + lp->dirty == c->leb_size)); 331 332 found: 333 dbg_find("found LEB %d, free %d, dirty %d, flags %#x", 334 lp->lnum, lp->free, lp->dirty, lp->flags); 335 336 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, 337 lp->flags | LPROPS_TAKEN, 0); 338 if (IS_ERR(lp)) { 339 err = PTR_ERR(lp); 340 goto out; 341 } 342 343 memcpy(ret_lp, lp, sizeof(struct ubifs_lprops)); 344 345 out: 346 ubifs_release_lprops(c); 347 return err; 348 } 349 350 /** 351 * scan_for_free_cb - free space scan callback. 352 * @c: the UBIFS file-system description object 353 * @lprops: LEB properties to scan 354 * @in_tree: whether the LEB properties are in main memory 355 * @data: information passed to and from the caller of the scan 356 * 357 * This function returns a code that indicates whether the scan should continue 358 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree 359 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop 360 * (%LPT_SCAN_STOP). 361 */ 362 static int scan_for_free_cb(struct ubifs_info *c, 363 const struct ubifs_lprops *lprops, int in_tree, 364 struct scan_data *data) 365 { 366 int ret = LPT_SCAN_CONTINUE; 367 368 /* Exclude LEBs that are currently in use */ 369 if (lprops->flags & LPROPS_TAKEN) 370 return LPT_SCAN_CONTINUE; 371 /* Determine whether to add these LEB properties to the tree */ 372 if (!in_tree && valuable(c, lprops)) 373 ret |= LPT_SCAN_ADD; 374 /* Exclude index LEBs */ 375 if (lprops->flags & LPROPS_INDEX) 376 return ret; 377 /* Exclude LEBs with too little space */ 378 if (lprops->free < data->min_space) 379 return ret; 380 /* If specified, exclude empty LEBs */ 381 if (!data->pick_free && lprops->free == c->leb_size) 382 return ret; 383 /* 384 * LEBs that have only free and dirty space must not be allocated 385 * because they may have been unmapped already or they may have data 386 * that is obsolete only because of nodes that are still sitting in a 387 * wbuf. 388 */ 389 if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0) 390 return ret; 391 /* Finally we found space */ 392 data->lnum = lprops->lnum; 393 return LPT_SCAN_ADD | LPT_SCAN_STOP; 394 } 395 396 /** 397 * do_find_free_space - find a data LEB with free space. 398 * @c: the UBIFS file-system description object 399 * @min_space: minimum amount of free space required 400 * @pick_free: whether it is OK to scan for empty LEBs 401 * @squeeze: whether to try to find space in a non-empty LEB first 402 * 403 * This function returns a pointer to the LEB properties found or a negative 404 * error code. 405 */ 406 static 407 const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c, 408 int min_space, int pick_free, 409 int squeeze) 410 { 411 const struct ubifs_lprops *lprops; 412 struct ubifs_lpt_heap *heap; 413 struct scan_data data; 414 int err, i; 415 416 if (squeeze) { 417 lprops = ubifs_fast_find_free(c); 418 if (lprops && lprops->free >= min_space) 419 return lprops; 420 } 421 if (pick_free) { 422 lprops = ubifs_fast_find_empty(c); 423 if (lprops) 424 return lprops; 425 } 426 if (!squeeze) { 427 lprops = ubifs_fast_find_free(c); 428 if (lprops && lprops->free >= min_space) 429 return lprops; 430 } 431 /* There may be an LEB with enough free space on the dirty heap */ 432 heap = &c->lpt_heap[LPROPS_DIRTY - 1]; 433 for (i = 0; i < heap->cnt; i++) { 434 lprops = heap->arr[i]; 435 if (lprops->free >= min_space) 436 return lprops; 437 } 438 /* 439 * A LEB may have fallen off of the bottom of the free heap, and ended 440 * up as uncategorized even though it has enough free space for us now, 441 * so check the uncategorized list. N.B. neither empty nor freeable LEBs 442 * can end up as uncategorized because they are kept on lists not 443 * finite-sized heaps. 444 */ 445 list_for_each_entry(lprops, &c->uncat_list, list) { 446 if (lprops->flags & LPROPS_TAKEN) 447 continue; 448 if (lprops->flags & LPROPS_INDEX) 449 continue; 450 if (lprops->free >= min_space) 451 return lprops; 452 } 453 /* We have looked everywhere in main memory, now scan the flash */ 454 if (c->pnodes_have >= c->pnode_cnt) 455 /* All pnodes are in memory, so skip scan */ 456 return ERR_PTR(-ENOSPC); 457 data.min_space = min_space; 458 data.pick_free = pick_free; 459 data.lnum = -1; 460 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, 461 (ubifs_lpt_scan_callback)scan_for_free_cb, 462 &data); 463 if (err) 464 return ERR_PTR(err); 465 ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); 466 c->lscan_lnum = data.lnum; 467 lprops = ubifs_lpt_lookup_dirty(c, data.lnum); 468 if (IS_ERR(lprops)) 469 return lprops; 470 ubifs_assert(lprops->lnum == data.lnum); 471 ubifs_assert(lprops->free >= min_space); 472 ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); 473 ubifs_assert(!(lprops->flags & LPROPS_INDEX)); 474 return lprops; 475 } 476 477 /** 478 * ubifs_find_free_space - find a data LEB with free space. 479 * @c: the UBIFS file-system description object 480 * @min_space: minimum amount of required free space 481 * @offs: contains offset of where free space starts on exit 482 * @squeeze: whether to try to find space in a non-empty LEB first 483 * 484 * This function looks for an LEB with at least @min_space bytes of free space. 485 * It tries to find an empty LEB if possible. If no empty LEBs are available, 486 * this function searches for a non-empty data LEB. The returned LEB is marked 487 * as "taken". 488 * 489 * This function returns found LEB number in case of success, %-ENOSPC if it 490 * failed to find a LEB with @min_space bytes of free space and other a negative 491 * error codes in case of failure. 492 */ 493 int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs, 494 int squeeze) 495 { 496 const struct ubifs_lprops *lprops; 497 int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags; 498 499 dbg_find("min_space %d", min_space); 500 ubifs_get_lprops(c); 501 502 /* Check if there are enough empty LEBs for commit */ 503 spin_lock(&c->space_lock); 504 if (c->bi.min_idx_lebs > c->lst.idx_lebs) 505 rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; 506 else 507 rsvd_idx_lebs = 0; 508 lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - 509 c->lst.taken_empty_lebs; 510 if (rsvd_idx_lebs < lebs) 511 /* 512 * OK to allocate an empty LEB, but we still don't want to go 513 * looking for one if there aren't any. 514 */ 515 if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { 516 pick_free = 1; 517 /* 518 * Because we release the space lock, we must account 519 * for this allocation here. After the LEB properties 520 * flags have been updated, we subtract one. Note, the 521 * result of this is that lprops also decreases 522 * @taken_empty_lebs in 'ubifs_change_lp()', so it is 523 * off by one for a short period of time which may 524 * introduce a small disturbance to budgeting 525 * calculations, but this is harmless because at the 526 * worst case this would make the budgeting subsystem 527 * be more pessimistic than needed. 528 * 529 * Fundamentally, this is about serialization of the 530 * budgeting and lprops subsystems. We could make the 531 * @space_lock a mutex and avoid dropping it before 532 * calling 'ubifs_change_lp()', but mutex is more 533 * heavy-weight, and we want budgeting to be as fast as 534 * possible. 535 */ 536 c->lst.taken_empty_lebs += 1; 537 } 538 spin_unlock(&c->space_lock); 539 540 lprops = do_find_free_space(c, min_space, pick_free, squeeze); 541 if (IS_ERR(lprops)) { 542 err = PTR_ERR(lprops); 543 goto out; 544 } 545 546 lnum = lprops->lnum; 547 flags = lprops->flags | LPROPS_TAKEN; 548 549 lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0); 550 if (IS_ERR(lprops)) { 551 err = PTR_ERR(lprops); 552 goto out; 553 } 554 555 if (pick_free) { 556 spin_lock(&c->space_lock); 557 c->lst.taken_empty_lebs -= 1; 558 spin_unlock(&c->space_lock); 559 } 560 561 *offs = c->leb_size - lprops->free; 562 ubifs_release_lprops(c); 563 564 if (*offs == 0) { 565 /* 566 * Ensure that empty LEBs have been unmapped. They may not have 567 * been, for example, because of an unclean unmount. Also 568 * LEBs that were freeable LEBs (free + dirty == leb_size) will 569 * not have been unmapped. 570 */ 571 err = ubifs_leb_unmap(c, lnum); 572 if (err) 573 return err; 574 } 575 576 dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs); 577 ubifs_assert(*offs <= c->leb_size - min_space); 578 return lnum; 579 580 out: 581 if (pick_free) { 582 spin_lock(&c->space_lock); 583 c->lst.taken_empty_lebs -= 1; 584 spin_unlock(&c->space_lock); 585 } 586 ubifs_release_lprops(c); 587 return err; 588 } 589 590 /** 591 * scan_for_idx_cb - callback used by the scan for a free LEB for the index. 592 * @c: the UBIFS file-system description object 593 * @lprops: LEB properties to scan 594 * @in_tree: whether the LEB properties are in main memory 595 * @data: information passed to and from the caller of the scan 596 * 597 * This function returns a code that indicates whether the scan should continue 598 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree 599 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop 600 * (%LPT_SCAN_STOP). 601 */ 602 static int scan_for_idx_cb(struct ubifs_info *c, 603 const struct ubifs_lprops *lprops, int in_tree, 604 struct scan_data *data) 605 { 606 int ret = LPT_SCAN_CONTINUE; 607 608 /* Exclude LEBs that are currently in use */ 609 if (lprops->flags & LPROPS_TAKEN) 610 return LPT_SCAN_CONTINUE; 611 /* Determine whether to add these LEB properties to the tree */ 612 if (!in_tree && valuable(c, lprops)) 613 ret |= LPT_SCAN_ADD; 614 /* Exclude index LEBS */ 615 if (lprops->flags & LPROPS_INDEX) 616 return ret; 617 /* Exclude LEBs that cannot be made empty */ 618 if (lprops->free + lprops->dirty != c->leb_size) 619 return ret; 620 /* 621 * We are allocating for the index so it is safe to allocate LEBs with 622 * only free and dirty space, because write buffers are sync'd at commit 623 * start. 624 */ 625 data->lnum = lprops->lnum; 626 return LPT_SCAN_ADD | LPT_SCAN_STOP; 627 } 628 629 /** 630 * scan_for_leb_for_idx - scan for a free LEB for the index. 631 * @c: the UBIFS file-system description object 632 */ 633 static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c) 634 { 635 struct ubifs_lprops *lprops; 636 struct scan_data data; 637 int err; 638 639 data.lnum = -1; 640 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, 641 (ubifs_lpt_scan_callback)scan_for_idx_cb, 642 &data); 643 if (err) 644 return ERR_PTR(err); 645 ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); 646 c->lscan_lnum = data.lnum; 647 lprops = ubifs_lpt_lookup_dirty(c, data.lnum); 648 if (IS_ERR(lprops)) 649 return lprops; 650 ubifs_assert(lprops->lnum == data.lnum); 651 ubifs_assert(lprops->free + lprops->dirty == c->leb_size); 652 ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); 653 ubifs_assert(!(lprops->flags & LPROPS_INDEX)); 654 return lprops; 655 } 656 657 /** 658 * ubifs_find_free_leb_for_idx - find a free LEB for the index. 659 * @c: the UBIFS file-system description object 660 * 661 * This function looks for a free LEB and returns that LEB number. The returned 662 * LEB is marked as "taken", "index". 663 * 664 * Only empty LEBs are allocated. This is for two reasons. First, the commit 665 * calculates the number of LEBs to allocate based on the assumption that they 666 * will be empty. Secondly, free space at the end of an index LEB is not 667 * guaranteed to be empty because it may have been used by the in-the-gaps 668 * method prior to an unclean unmount. 669 * 670 * If no LEB is found %-ENOSPC is returned. For other failures another negative 671 * error code is returned. 672 */ 673 int ubifs_find_free_leb_for_idx(struct ubifs_info *c) 674 { 675 const struct ubifs_lprops *lprops; 676 int lnum = -1, err, flags; 677 678 ubifs_get_lprops(c); 679 680 lprops = ubifs_fast_find_empty(c); 681 if (!lprops) { 682 lprops = ubifs_fast_find_freeable(c); 683 if (!lprops) { 684 /* 685 * The first condition means the following: go scan the 686 * LPT if there are uncategorized lprops, which means 687 * there may be freeable LEBs there (UBIFS does not 688 * store the information about freeable LEBs in the 689 * master node). 690 */ 691 if (c->in_a_category_cnt != c->main_lebs || 692 c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { 693 ubifs_assert(c->freeable_cnt == 0); 694 lprops = scan_for_leb_for_idx(c); 695 if (IS_ERR(lprops)) { 696 err = PTR_ERR(lprops); 697 goto out; 698 } 699 } 700 } 701 } 702 703 if (!lprops) { 704 err = -ENOSPC; 705 goto out; 706 } 707 708 lnum = lprops->lnum; 709 710 dbg_find("found LEB %d, free %d, dirty %d, flags %#x", 711 lnum, lprops->free, lprops->dirty, lprops->flags); 712 713 flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; 714 lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0); 715 if (IS_ERR(lprops)) { 716 err = PTR_ERR(lprops); 717 goto out; 718 } 719 720 ubifs_release_lprops(c); 721 722 /* 723 * Ensure that empty LEBs have been unmapped. They may not have been, 724 * for example, because of an unclean unmount. Also LEBs that were 725 * freeable LEBs (free + dirty == leb_size) will not have been unmapped. 726 */ 727 err = ubifs_leb_unmap(c, lnum); 728 if (err) { 729 ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0, 730 LPROPS_TAKEN | LPROPS_INDEX, 0); 731 return err; 732 } 733 734 return lnum; 735 736 out: 737 ubifs_release_lprops(c); 738 return err; 739 } 740 741 static int cmp_dirty_idx(const struct ubifs_lprops **a, 742 const struct ubifs_lprops **b) 743 { 744 const struct ubifs_lprops *lpa = *a; 745 const struct ubifs_lprops *lpb = *b; 746 747 return lpa->dirty + lpa->free - lpb->dirty - lpb->free; 748 } 749 750 static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b, 751 int size) 752 { 753 struct ubifs_lprops *t = *a; 754 755 *a = *b; 756 *b = t; 757 } 758 759 /** 760 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos. 761 * @c: the UBIFS file-system description object 762 * 763 * This function is called each commit to create an array of LEB numbers of 764 * dirty index LEBs sorted in order of dirty and free space. This is used by 765 * the in-the-gaps method of TNC commit. 766 */ 767 int ubifs_save_dirty_idx_lnums(struct ubifs_info *c) 768 { 769 int i; 770 771 ubifs_get_lprops(c); 772 /* Copy the LPROPS_DIRTY_IDX heap */ 773 c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; 774 memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, 775 sizeof(void *) * c->dirty_idx.cnt); 776 /* Sort it so that the dirtiest is now at the end */ 777 sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *), 778 (int (*)(const void *, const void *))cmp_dirty_idx, 779 (void (*)(void *, void *, int))swap_dirty_idx); 780 dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt); 781 if (c->dirty_idx.cnt) 782 dbg_find("dirtiest index LEB is %d with dirty %d and free %d", 783 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, 784 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, 785 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); 786 /* Replace the lprops pointers with LEB numbers */ 787 for (i = 0; i < c->dirty_idx.cnt; i++) 788 c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; 789 ubifs_release_lprops(c); 790 return 0; 791 } 792 793 /** 794 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB. 795 * @c: the UBIFS file-system description object 796 * @lprops: LEB properties to scan 797 * @in_tree: whether the LEB properties are in main memory 798 * @data: information passed to and from the caller of the scan 799 * 800 * This function returns a code that indicates whether the scan should continue 801 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree 802 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop 803 * (%LPT_SCAN_STOP). 804 */ 805 static int scan_dirty_idx_cb(struct ubifs_info *c, 806 const struct ubifs_lprops *lprops, int in_tree, 807 struct scan_data *data) 808 { 809 int ret = LPT_SCAN_CONTINUE; 810 811 /* Exclude LEBs that are currently in use */ 812 if (lprops->flags & LPROPS_TAKEN) 813 return LPT_SCAN_CONTINUE; 814 /* Determine whether to add these LEB properties to the tree */ 815 if (!in_tree && valuable(c, lprops)) 816 ret |= LPT_SCAN_ADD; 817 /* Exclude non-index LEBs */ 818 if (!(lprops->flags & LPROPS_INDEX)) 819 return ret; 820 /* Exclude LEBs with too little space */ 821 if (lprops->free + lprops->dirty < c->min_idx_node_sz) 822 return ret; 823 /* Finally we found space */ 824 data->lnum = lprops->lnum; 825 return LPT_SCAN_ADD | LPT_SCAN_STOP; 826 } 827 828 /** 829 * find_dirty_idx_leb - find a dirty index LEB. 830 * @c: the UBIFS file-system description object 831 * 832 * This function returns LEB number upon success and a negative error code upon 833 * failure. In particular, -ENOSPC is returned if a dirty index LEB is not 834 * found. 835 * 836 * Note that this function scans the entire LPT but it is called very rarely. 837 */ 838 static int find_dirty_idx_leb(struct ubifs_info *c) 839 { 840 const struct ubifs_lprops *lprops; 841 struct ubifs_lpt_heap *heap; 842 struct scan_data data; 843 int err, i, ret; 844 845 /* Check all structures in memory first */ 846 data.lnum = -1; 847 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; 848 for (i = 0; i < heap->cnt; i++) { 849 lprops = heap->arr[i]; 850 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 851 if (ret & LPT_SCAN_STOP) 852 goto found; 853 } 854 list_for_each_entry(lprops, &c->frdi_idx_list, list) { 855 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 856 if (ret & LPT_SCAN_STOP) 857 goto found; 858 } 859 list_for_each_entry(lprops, &c->uncat_list, list) { 860 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 861 if (ret & LPT_SCAN_STOP) 862 goto found; 863 } 864 if (c->pnodes_have >= c->pnode_cnt) 865 /* All pnodes are in memory, so skip scan */ 866 return -ENOSPC; 867 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, 868 (ubifs_lpt_scan_callback)scan_dirty_idx_cb, 869 &data); 870 if (err) 871 return err; 872 found: 873 ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); 874 c->lscan_lnum = data.lnum; 875 lprops = ubifs_lpt_lookup_dirty(c, data.lnum); 876 if (IS_ERR(lprops)) 877 return PTR_ERR(lprops); 878 ubifs_assert(lprops->lnum == data.lnum); 879 ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz); 880 ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); 881 ubifs_assert((lprops->flags & LPROPS_INDEX)); 882 883 dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x", 884 lprops->lnum, lprops->free, lprops->dirty, lprops->flags); 885 886 lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, 887 lprops->flags | LPROPS_TAKEN, 0); 888 if (IS_ERR(lprops)) 889 return PTR_ERR(lprops); 890 891 return lprops->lnum; 892 } 893 894 /** 895 * get_idx_gc_leb - try to get a LEB number from trivial GC. 896 * @c: the UBIFS file-system description object 897 */ 898 static int get_idx_gc_leb(struct ubifs_info *c) 899 { 900 const struct ubifs_lprops *lp; 901 int err, lnum; 902 903 err = ubifs_get_idx_gc_leb(c); 904 if (err < 0) 905 return err; 906 lnum = err; 907 /* 908 * The LEB was due to be unmapped after the commit but 909 * it is needed now for this commit. 910 */ 911 lp = ubifs_lpt_lookup_dirty(c, lnum); 912 if (IS_ERR(lp)) 913 return PTR_ERR(lp); 914 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, 915 lp->flags | LPROPS_INDEX, -1); 916 if (IS_ERR(lp)) 917 return PTR_ERR(lp); 918 dbg_find("LEB %d, dirty %d and free %d flags %#x", 919 lp->lnum, lp->dirty, lp->free, lp->flags); 920 return lnum; 921 } 922 923 /** 924 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array. 925 * @c: the UBIFS file-system description object 926 */ 927 static int find_dirtiest_idx_leb(struct ubifs_info *c) 928 { 929 const struct ubifs_lprops *lp; 930 int lnum; 931 932 while (1) { 933 if (!c->dirty_idx.cnt) 934 return -ENOSPC; 935 /* The lprops pointers were replaced by LEB numbers */ 936 lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; 937 lp = ubifs_lpt_lookup(c, lnum); 938 if (IS_ERR(lp)) 939 return PTR_ERR(lp); 940 if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) 941 continue; 942 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, 943 lp->flags | LPROPS_TAKEN, 0); 944 if (IS_ERR(lp)) 945 return PTR_ERR(lp); 946 break; 947 } 948 dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty, 949 lp->free, lp->flags); 950 ubifs_assert(lp->flags & LPROPS_TAKEN); 951 ubifs_assert(lp->flags & LPROPS_INDEX); 952 return lnum; 953 } 954 955 /** 956 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit. 957 * @c: the UBIFS file-system description object 958 * 959 * This function attempts to find an untaken index LEB with the most free and 960 * dirty space that can be used without overwriting index nodes that were in the 961 * last index committed. 962 */ 963 int ubifs_find_dirty_idx_leb(struct ubifs_info *c) 964 { 965 int err; 966 967 ubifs_get_lprops(c); 968 969 /* 970 * We made an array of the dirtiest index LEB numbers as at the start of 971 * last commit. Try that array first. 972 */ 973 err = find_dirtiest_idx_leb(c); 974 975 /* Next try scanning the entire LPT */ 976 if (err == -ENOSPC) 977 err = find_dirty_idx_leb(c); 978 979 /* Finally take any index LEBs awaiting trivial GC */ 980 if (err == -ENOSPC) 981 err = get_idx_gc_leb(c); 982 983 ubifs_release_lprops(c); 984 return err; 985 } 986