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 */ 39struct 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 */ 54static 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 */ 95static 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 */ 136static 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 */ 233int 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->min_idx_lebs >= c->lst.idx_lebs) { 256 rsvd_idx_lebs = c->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->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 332found: 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 345out: 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 */ 362static 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 */ 406static 407const 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 */ 493int 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->min_idx_lebs > c->lst.idx_lebs) 505 rsvd_idx_lebs = c->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 580out: 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 */ 602static 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 */ 633static 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 */ 673int 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 ubifs_assert(c->freeable_cnt == 0); 685 if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { 686 lprops = scan_for_leb_for_idx(c); 687 if (IS_ERR(lprops)) { 688 err = PTR_ERR(lprops); 689 goto out; 690 } 691 } 692 } 693 } 694 695 if (!lprops) { 696 err = -ENOSPC; 697 goto out; 698 } 699 700 lnum = lprops->lnum; 701 702 dbg_find("found LEB %d, free %d, dirty %d, flags %#x", 703 lnum, lprops->free, lprops->dirty, lprops->flags); 704 705 flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; 706 lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0); 707 if (IS_ERR(lprops)) { 708 err = PTR_ERR(lprops); 709 goto out; 710 } 711 712 ubifs_release_lprops(c); 713 714 /* 715 * Ensure that empty LEBs have been unmapped. They may not have been, 716 * for example, because of an unclean unmount. Also LEBs that were 717 * freeable LEBs (free + dirty == leb_size) will not have been unmapped. 718 */ 719 err = ubifs_leb_unmap(c, lnum); 720 if (err) { 721 ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0, 722 LPROPS_TAKEN | LPROPS_INDEX, 0); 723 return err; 724 } 725 726 return lnum; 727 728out: 729 ubifs_release_lprops(c); 730 return err; 731} 732 733static int cmp_dirty_idx(const struct ubifs_lprops **a, 734 const struct ubifs_lprops **b) 735{ 736 const struct ubifs_lprops *lpa = *a; 737 const struct ubifs_lprops *lpb = *b; 738 739 return lpa->dirty + lpa->free - lpb->dirty - lpb->free; 740} 741 742static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b, 743 int size) 744{ 745 struct ubifs_lprops *t = *a; 746 747 *a = *b; 748 *b = t; 749} 750 751/** 752 * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos. 753 * @c: the UBIFS file-system description object 754 * 755 * This function is called each commit to create an array of LEB numbers of 756 * dirty index LEBs sorted in order of dirty and free space. This is used by 757 * the in-the-gaps method of TNC commit. 758 */ 759int ubifs_save_dirty_idx_lnums(struct ubifs_info *c) 760{ 761 int i; 762 763 ubifs_get_lprops(c); 764 /* Copy the LPROPS_DIRTY_IDX heap */ 765 c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; 766 memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, 767 sizeof(void *) * c->dirty_idx.cnt); 768 /* Sort it so that the dirtiest is now at the end */ 769 sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *), 770 (int (*)(const void *, const void *))cmp_dirty_idx, 771 (void (*)(void *, void *, int))swap_dirty_idx); 772 dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt); 773 if (c->dirty_idx.cnt) 774 dbg_find("dirtiest index LEB is %d with dirty %d and free %d", 775 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, 776 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, 777 c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); 778 /* Replace the lprops pointers with LEB numbers */ 779 for (i = 0; i < c->dirty_idx.cnt; i++) 780 c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; 781 ubifs_release_lprops(c); 782 return 0; 783} 784 785/** 786 * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB. 787 * @c: the UBIFS file-system description object 788 * @lprops: LEB properties to scan 789 * @in_tree: whether the LEB properties are in main memory 790 * @data: information passed to and from the caller of the scan 791 * 792 * This function returns a code that indicates whether the scan should continue 793 * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree 794 * in main memory (%LPT_SCAN_ADD), or whether the scan should stop 795 * (%LPT_SCAN_STOP). 796 */ 797static int scan_dirty_idx_cb(struct ubifs_info *c, 798 const struct ubifs_lprops *lprops, int in_tree, 799 struct scan_data *data) 800{ 801 int ret = LPT_SCAN_CONTINUE; 802 803 /* Exclude LEBs that are currently in use */ 804 if (lprops->flags & LPROPS_TAKEN) 805 return LPT_SCAN_CONTINUE; 806 /* Determine whether to add these LEB properties to the tree */ 807 if (!in_tree && valuable(c, lprops)) 808 ret |= LPT_SCAN_ADD; 809 /* Exclude non-index LEBs */ 810 if (!(lprops->flags & LPROPS_INDEX)) 811 return ret; 812 /* Exclude LEBs with too little space */ 813 if (lprops->free + lprops->dirty < c->min_idx_node_sz) 814 return ret; 815 /* Finally we found space */ 816 data->lnum = lprops->lnum; 817 return LPT_SCAN_ADD | LPT_SCAN_STOP; 818} 819 820/** 821 * find_dirty_idx_leb - find a dirty index LEB. 822 * @c: the UBIFS file-system description object 823 * 824 * This function returns LEB number upon success and a negative error code upon 825 * failure. In particular, -ENOSPC is returned if a dirty index LEB is not 826 * found. 827 * 828 * Note that this function scans the entire LPT but it is called very rarely. 829 */ 830static int find_dirty_idx_leb(struct ubifs_info *c) 831{ 832 const struct ubifs_lprops *lprops; 833 struct ubifs_lpt_heap *heap; 834 struct scan_data data; 835 int err, i, ret; 836 837 /* Check all structures in memory first */ 838 data.lnum = -1; 839 heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; 840 for (i = 0; i < heap->cnt; i++) { 841 lprops = heap->arr[i]; 842 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 843 if (ret & LPT_SCAN_STOP) 844 goto found; 845 } 846 list_for_each_entry(lprops, &c->frdi_idx_list, list) { 847 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 848 if (ret & LPT_SCAN_STOP) 849 goto found; 850 } 851 list_for_each_entry(lprops, &c->uncat_list, list) { 852 ret = scan_dirty_idx_cb(c, lprops, 1, &data); 853 if (ret & LPT_SCAN_STOP) 854 goto found; 855 } 856 if (c->pnodes_have >= c->pnode_cnt) 857 /* All pnodes are in memory, so skip scan */ 858 return -ENOSPC; 859 err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, 860 (ubifs_lpt_scan_callback)scan_dirty_idx_cb, 861 &data); 862 if (err) 863 return err; 864found: 865 ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); 866 c->lscan_lnum = data.lnum; 867 lprops = ubifs_lpt_lookup_dirty(c, data.lnum); 868 if (IS_ERR(lprops)) 869 return PTR_ERR(lprops); 870 ubifs_assert(lprops->lnum == data.lnum); 871 ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz); 872 ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); 873 ubifs_assert((lprops->flags & LPROPS_INDEX)); 874 875 dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x", 876 lprops->lnum, lprops->free, lprops->dirty, lprops->flags); 877 878 lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, 879 lprops->flags | LPROPS_TAKEN, 0); 880 if (IS_ERR(lprops)) 881 return PTR_ERR(lprops); 882 883 return lprops->lnum; 884} 885 886/** 887 * get_idx_gc_leb - try to get a LEB number from trivial GC. 888 * @c: the UBIFS file-system description object 889 */ 890static int get_idx_gc_leb(struct ubifs_info *c) 891{ 892 const struct ubifs_lprops *lp; 893 int err, lnum; 894 895 err = ubifs_get_idx_gc_leb(c); 896 if (err < 0) 897 return err; 898 lnum = err; 899 /* 900 * The LEB was due to be unmapped after the commit but 901 * it is needed now for this commit. 902 */ 903 lp = ubifs_lpt_lookup_dirty(c, lnum); 904 if (IS_ERR(lp)) 905 return PTR_ERR(lp); 906 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, 907 lp->flags | LPROPS_INDEX, -1); 908 if (IS_ERR(lp)) 909 return PTR_ERR(lp); 910 dbg_find("LEB %d, dirty %d and free %d flags %#x", 911 lp->lnum, lp->dirty, lp->free, lp->flags); 912 return lnum; 913} 914 915/** 916 * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array. 917 * @c: the UBIFS file-system description object 918 */ 919static int find_dirtiest_idx_leb(struct ubifs_info *c) 920{ 921 const struct ubifs_lprops *lp; 922 int lnum; 923 924 while (1) { 925 if (!c->dirty_idx.cnt) 926 return -ENOSPC; 927 /* The lprops pointers were replaced by LEB numbers */ 928 lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; 929 lp = ubifs_lpt_lookup(c, lnum); 930 if (IS_ERR(lp)) 931 return PTR_ERR(lp); 932 if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) 933 continue; 934 lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, 935 lp->flags | LPROPS_TAKEN, 0); 936 if (IS_ERR(lp)) 937 return PTR_ERR(lp); 938 break; 939 } 940 dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty, 941 lp->free, lp->flags); 942 ubifs_assert(lp->flags | LPROPS_TAKEN); 943 ubifs_assert(lp->flags | LPROPS_INDEX); 944 return lnum; 945} 946 947/** 948 * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit. 949 * @c: the UBIFS file-system description object 950 * 951 * This function attempts to find an untaken index LEB with the most free and 952 * dirty space that can be used without overwriting index nodes that were in the 953 * last index committed. 954 */ 955int ubifs_find_dirty_idx_leb(struct ubifs_info *c) 956{ 957 int err; 958 959 ubifs_get_lprops(c); 960 961 /* 962 * We made an array of the dirtiest index LEB numbers as at the start of 963 * last commit. Try that array first. 964 */ 965 err = find_dirtiest_idx_leb(c); 966 967 /* Next try scanning the entire LPT */ 968 if (err == -ENOSPC) 969 err = find_dirty_idx_leb(c); 970 971 /* Finally take any index LEBs awaiting trivial GC */ 972 if (err == -ENOSPC) 973 err = get_idx_gc_leb(c); 974 975 ubifs_release_lprops(c); 976 return err; 977} 978