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