Lines Matching +full:- +full:lp
1 // SPDX-License-Identifier: GPL-2.0
5 * Copyright (C) 2006-2008 Nokia Corporation.
14 * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
15 * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
16 * nodes to the journal, at which point the garbage-collected LEB is free to be
17 * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
18 * dirty in the TNC, and after the next commit, the garbage-collected LEB is
24 * LEBs which have less than @c->dead_wm bytes of free + dirty space are full
25 * and not worth garbage-collecting. The dead watermark is one min. I/O unit
60 * switch_gc_head - switch the garbage collection journal head.
61 * @c: UBIFS file-system description object
68 * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
73 int err, gc_lnum = c->gc_lnum; in switch_gc_head()
74 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in switch_gc_head()
76 ubifs_assert(gc_lnum != -1); in switch_gc_head()
78 wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum, in switch_gc_head()
79 c->leb_size - wbuf->offs - wbuf->used); in switch_gc_head()
86 * The GC write-buffer was synchronized, we may safely unmap in switch_gc_head()
87 * 'c->gc_lnum'. in switch_gc_head()
101 c->gc_lnum = -1; in switch_gc_head()
107 * data_nodes_cmp - compare 2 data nodes.
108 * @priv: UBIFS file-system description object
113 * inode or block number, and %-1 otherwise.
128 ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY); in data_nodes_cmp()
129 ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY); in data_nodes_cmp()
130 ubifs_assert(sa->type == UBIFS_DATA_NODE); in data_nodes_cmp()
131 ubifs_assert(sb->type == UBIFS_DATA_NODE); in data_nodes_cmp()
133 inuma = key_inum(c, &sa->key); in data_nodes_cmp()
134 inumb = key_inum(c, &sb->key); in data_nodes_cmp()
137 unsigned int blka = key_block(c, &sa->key); in data_nodes_cmp()
138 unsigned int blkb = key_block(c, &sb->key); in data_nodes_cmp()
141 return -1; in data_nodes_cmp()
143 return -1; in data_nodes_cmp()
149 * nondata_nodes_cmp - compare 2 non-data nodes.
150 * @priv: UBIFS file-system description object
172 ubifs_assert(key_type(c, &sa->key) != UBIFS_DATA_KEY && in nondata_nodes_cmp()
173 key_type(c, &sb->key) != UBIFS_DATA_KEY); in nondata_nodes_cmp()
174 ubifs_assert(sa->type != UBIFS_DATA_NODE && in nondata_nodes_cmp()
175 sb->type != UBIFS_DATA_NODE); in nondata_nodes_cmp()
178 if (sa->type == UBIFS_INO_NODE) { in nondata_nodes_cmp()
179 if (sb->type == UBIFS_INO_NODE) in nondata_nodes_cmp()
180 return sb->len - sa->len; in nondata_nodes_cmp()
181 return -1; in nondata_nodes_cmp()
183 if (sb->type == UBIFS_INO_NODE) in nondata_nodes_cmp()
186 ubifs_assert(key_type(c, &sa->key) == UBIFS_DENT_KEY || in nondata_nodes_cmp()
187 key_type(c, &sa->key) == UBIFS_XENT_KEY); in nondata_nodes_cmp()
188 ubifs_assert(key_type(c, &sb->key) == UBIFS_DENT_KEY || in nondata_nodes_cmp()
189 key_type(c, &sb->key) == UBIFS_XENT_KEY); in nondata_nodes_cmp()
190 ubifs_assert(sa->type == UBIFS_DENT_NODE || in nondata_nodes_cmp()
191 sa->type == UBIFS_XENT_NODE); in nondata_nodes_cmp()
192 ubifs_assert(sb->type == UBIFS_DENT_NODE || in nondata_nodes_cmp()
193 sb->type == UBIFS_XENT_NODE); in nondata_nodes_cmp()
195 inuma = key_inum(c, &sa->key); in nondata_nodes_cmp()
196 inumb = key_inum(c, &sb->key); in nondata_nodes_cmp()
199 uint32_t hasha = key_hash(c, &sa->key); in nondata_nodes_cmp()
200 uint32_t hashb = key_hash(c, &sb->key); in nondata_nodes_cmp()
203 return -1; in nondata_nodes_cmp()
205 return -1; in nondata_nodes_cmp()
211 * sort_nodes - sort nodes for GC.
212 * @c: UBIFS file-system description object
214 * @nondata: contains non-data nodes on exit
218 * kills obsolete nodes and separates data and non-data nodes to the
219 * @sleb->nodes and @nondata lists correspondingly.
221 * Data nodes are then sorted in block number order - this is important for
222 * bulk-read; data nodes with lower inode number go before data nodes with
226 * Non-data nodes are sorted as follows.
227 * o First go inode nodes - they are sorted in descending length order.
228 * o Then go directory entry nodes - they are sorted in hash order, which
245 /* Separate data nodes and non-data nodes */ in sort_nodes()
246 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { in sort_nodes()
247 ubifs_assert(snod->type == UBIFS_INO_NODE || in sort_nodes()
248 snod->type == UBIFS_DATA_NODE || in sort_nodes()
249 snod->type == UBIFS_DENT_NODE || in sort_nodes()
250 snod->type == UBIFS_XENT_NODE || in sort_nodes()
251 snod->type == UBIFS_TRUN_NODE); in sort_nodes()
253 if (snod->type != UBIFS_INO_NODE && in sort_nodes()
254 snod->type != UBIFS_DATA_NODE && in sort_nodes()
255 snod->type != UBIFS_DENT_NODE && in sort_nodes()
256 snod->type != UBIFS_XENT_NODE) { in sort_nodes()
258 list_del(&snod->list); in sort_nodes()
263 ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY || in sort_nodes()
264 key_type(c, &snod->key) == UBIFS_INO_KEY || in sort_nodes()
265 key_type(c, &snod->key) == UBIFS_DENT_KEY || in sort_nodes()
266 key_type(c, &snod->key) == UBIFS_XENT_KEY); in sort_nodes()
268 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum, in sort_nodes()
269 snod->offs, 0); in sort_nodes()
275 list_del(&snod->list); in sort_nodes()
280 if (snod->len < *min) in sort_nodes()
281 *min = snod->len; in sort_nodes()
283 if (key_type(c, &snod->key) != UBIFS_DATA_KEY) in sort_nodes()
284 list_move_tail(&snod->list, nondata); in sort_nodes()
287 /* Sort data and non-data nodes */ in sort_nodes()
288 list_sort(c, &sleb->nodes, &data_nodes_cmp); in sort_nodes()
291 err = dbg_check_data_nodes_order(c, &sleb->nodes); in sort_nodes()
301 * move_node - move a node.
302 * @c: UBIFS file-system description object
305 * @wbuf: write-buffer to move node to
314 int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used; in move_node()
317 err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len); in move_node()
321 err = ubifs_tnc_replace(c, &snod->key, sleb->lnum, in move_node()
322 snod->offs, new_lnum, new_offs, in move_node()
323 snod->len); in move_node()
324 list_del(&snod->list); in move_node()
330 * move_nodes - move nodes.
331 * @c: UBIFS file-system description object
335 * journal head. This function returns zero in case of success, %-EAGAIN if
343 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in move_nodes()
345 if (wbuf->lnum == -1) { in move_nodes()
359 /* Write nodes to their new location. Use the first-fit strategy */ in move_nodes()
365 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { in move_nodes()
366 avail = c->leb_size - wbuf->offs - wbuf->used; in move_nodes()
367 if (snod->len > avail) in move_nodes()
370 * bulk-read. in move_nodes()
379 /* Move non-data nodes */ in move_nodes()
381 avail = c->leb_size - wbuf->offs - wbuf->used; in move_nodes()
385 if (snod->len > avail) { in move_nodes()
389 * head. IOW, we assume that data-less inode in move_nodes()
393 if (key_type(c, &snod->key) == UBIFS_DENT_KEY || in move_nodes()
394 snod->len == UBIFS_INO_NODE_SZ) in move_nodes()
404 if (list_empty(&sleb->nodes) && list_empty(&nondata)) in move_nodes()
419 list_splice_tail(&nondata, &sleb->nodes); in move_nodes()
424 * gc_sync_wbufs - sync write-buffers for GC.
425 * @c: UBIFS file-system description object
428 * be in a write-buffer instead. That is, a node could be written to a
429 * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
430 * erased before the write-buffer is sync'd and then there is an unclean
432 * write-buffers.
440 for (i = 0; i < c->jhead_cnt; i++) { in gc_sync_wbufs()
443 err = ubifs_wbuf_sync(&c->jheads[i].wbuf); in gc_sync_wbufs()
451 * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
452 * @c: UBIFS file-system description object
453 * @lp: describes the LEB to garbage collect
455 * This function garbage-collects an LEB and returns one of the @LEB_FREED,
456 * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
459 int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp) in ubifs_garbage_collect_leb() argument
463 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in ubifs_garbage_collect_leb()
464 int err = 0, lnum = lp->lnum; in ubifs_garbage_collect_leb()
466 ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 || in ubifs_garbage_collect_leb()
467 c->need_recovery); in ubifs_garbage_collect_leb()
468 ubifs_assert(c->gc_lnum != lnum); in ubifs_garbage_collect_leb()
469 ubifs_assert(wbuf->lnum != lnum); in ubifs_garbage_collect_leb()
471 if (lp->free + lp->dirty == c->leb_size) { in ubifs_garbage_collect_leb()
472 /* Special case - a free LEB */ in ubifs_garbage_collect_leb()
473 dbg_gc("LEB %d is free, return it", lp->lnum); in ubifs_garbage_collect_leb()
474 ubifs_assert(!(lp->flags & LPROPS_INDEX)); in ubifs_garbage_collect_leb()
476 if (lp->free != c->leb_size) { in ubifs_garbage_collect_leb()
480 * which obsoletes something in 'lp->pnum'. in ubifs_garbage_collect_leb()
485 err = ubifs_change_one_lp(c, lp->lnum, c->leb_size, in ubifs_garbage_collect_leb()
490 err = ubifs_leb_unmap(c, lp->lnum); in ubifs_garbage_collect_leb()
494 if (c->gc_lnum == -1) { in ubifs_garbage_collect_leb()
495 c->gc_lnum = lnum; in ubifs_garbage_collect_leb()
504 * (c->leb_size - lp->free). in ubifs_garbage_collect_leb()
506 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); in ubifs_garbage_collect_leb()
510 ubifs_assert(!list_empty(&sleb->nodes)); in ubifs_garbage_collect_leb()
511 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list); in ubifs_garbage_collect_leb()
513 if (snod->type == UBIFS_IDX_NODE) { in ubifs_garbage_collect_leb()
517 lnum, lp->free, lp->dirty); in ubifs_garbage_collect_leb()
518 list_for_each_entry(snod, &sleb->nodes, list) { in ubifs_garbage_collect_leb()
519 struct ubifs_idx_node *idx = snod->node; in ubifs_garbage_collect_leb()
520 int level = le16_to_cpu(idx->level); in ubifs_garbage_collect_leb()
522 ubifs_assert(snod->type == UBIFS_IDX_NODE); in ubifs_garbage_collect_leb()
523 key_read(c, ubifs_idx_key(c, idx), &snod->key); in ubifs_garbage_collect_leb()
524 err = ubifs_dirty_idx_node(c, &snod->key, level, lnum, in ubifs_garbage_collect_leb()
525 snod->offs); in ubifs_garbage_collect_leb()
532 err = -ENOMEM; in ubifs_garbage_collect_leb()
536 idx_gc->lnum = lnum; in ubifs_garbage_collect_leb()
537 idx_gc->unmap = 0; in ubifs_garbage_collect_leb()
538 list_add(&idx_gc->list, &c->idx_gc); in ubifs_garbage_collect_leb()
546 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, in ubifs_garbage_collect_leb()
553 lnum, lp->free, lp->dirty); in ubifs_garbage_collect_leb()
563 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0); in ubifs_garbage_collect_leb()
568 c->gced_lnum = lnum; in ubifs_garbage_collect_leb()
570 c->gc_seq += 1; in ubifs_garbage_collect_leb()
573 if (c->gc_lnum == -1) { in ubifs_garbage_collect_leb()
574 c->gc_lnum = lnum; in ubifs_garbage_collect_leb()
595 c->gced_lnum = lnum; in ubifs_garbage_collect_leb()
597 c->gc_seq += 1; in ubifs_garbage_collect_leb()
603 * ubifs_garbage_collect - UBIFS garbage collector.
604 * @c: UBIFS file-system description object
607 * This function does out-of-place garbage collection. The return codes are:
609 * o %-EAGAIN if the caller has to run commit;
610 * o %-ENOSPC if GC failed to make any progress;
616 * caller might be holding the commit lock, so %-EAGAIN is returned instead;
617 * And this error code means that the caller has to run commit, and re-run GC
620 * There are many reasons why this function may return %-EAGAIN:
622 * @c->gc_lnum;
628 * Note, if the file-system is close to be full, this function may return
629 * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
636 * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
640 int i, err, ret, min_space = c->dead_wm; in ubifs_garbage_collect()
641 struct ubifs_lprops lp; in ubifs_garbage_collect() local
642 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in ubifs_garbage_collect()
645 ubifs_assert(!c->ro_media && !c->ro_mount); in ubifs_garbage_collect()
648 return -EAGAIN; in ubifs_garbage_collect()
650 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); in ubifs_garbage_collect()
652 if (c->ro_error) { in ubifs_garbage_collect()
653 ret = -EROFS; in ubifs_garbage_collect()
657 /* We expect the write-buffer to be empty on entry */ in ubifs_garbage_collect()
658 ubifs_assert(!wbuf->used); in ubifs_garbage_collect()
667 ret = -EAGAIN; in ubifs_garbage_collect()
671 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) { in ubifs_garbage_collect()
676 dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN"); in ubifs_garbage_collect()
678 ret = -EAGAIN; in ubifs_garbage_collect()
687 dbg_gc("hard limit, -ENOSPC"); in ubifs_garbage_collect()
688 ret = -ENOSPC; in ubifs_garbage_collect()
699 ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1); in ubifs_garbage_collect()
701 if (ret == -ENOSPC) in ubifs_garbage_collect()
707 lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty, in ubifs_garbage_collect()
710 space_before = c->leb_size - wbuf->offs - wbuf->used; in ubifs_garbage_collect()
711 if (wbuf->lnum == -1) in ubifs_garbage_collect()
714 ret = ubifs_garbage_collect_leb(c, &lp); in ubifs_garbage_collect()
716 if (ret == -EAGAIN) { in ubifs_garbage_collect()
721 * caller instead of the original '-EAGAIN'. in ubifs_garbage_collect()
723 err = ubifs_return_leb(c, lp.lnum); in ubifs_garbage_collect()
733 dbg_gc("LEB %d freed, return", lp.lnum); in ubifs_garbage_collect()
734 ret = lp.lnum; in ubifs_garbage_collect()
745 dbg_gc("indexing LEB %d freed, continue", lp.lnum); in ubifs_garbage_collect()
750 space_after = c->leb_size - wbuf->offs - wbuf->used; in ubifs_garbage_collect()
751 dbg_gc("LEB %d retained, freed %d bytes", lp.lnum, in ubifs_garbage_collect()
752 space_after - space_before); in ubifs_garbage_collect()
757 if (min_space < c->dead_wm) in ubifs_garbage_collect()
758 min_space = c->dead_wm; in ubifs_garbage_collect()
786 if (min_space > c->dark_wm) in ubifs_garbage_collect()
787 min_space = c->dark_wm; in ubifs_garbage_collect()
791 if (ret == -ENOSPC && !list_empty(&c->idx_gc)) { in ubifs_garbage_collect()
792 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN"); in ubifs_garbage_collect()
794 ret = -EAGAIN; in ubifs_garbage_collect()
799 err = ubifs_leb_unmap(c, c->gc_lnum); in ubifs_garbage_collect()
805 mutex_unlock(&wbuf->io_mutex); in ubifs_garbage_collect()
810 ubifs_assert(ret != -ENOSPC && ret != -EAGAIN); in ubifs_garbage_collect()
813 mutex_unlock(&wbuf->io_mutex); in ubifs_garbage_collect()
814 ubifs_return_leb(c, lp.lnum); in ubifs_garbage_collect()
819 * ubifs_gc_start_commit - garbage collection at start of commit.
820 * @c: UBIFS file-system description object
832 const struct ubifs_lprops *lp; in ubifs_gc_start_commit() local
838 * Unmap (non-index) freeable LEBs. Note that recovery requires that all in ubifs_gc_start_commit()
842 lp = ubifs_fast_find_freeable(c); in ubifs_gc_start_commit()
843 if (IS_ERR(lp)) { in ubifs_gc_start_commit()
844 err = PTR_ERR(lp); in ubifs_gc_start_commit()
847 if (!lp) in ubifs_gc_start_commit()
849 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
850 ubifs_assert(!(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
851 err = ubifs_leb_unmap(c, lp->lnum); in ubifs_gc_start_commit()
854 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0); in ubifs_gc_start_commit()
855 if (IS_ERR(lp)) { in ubifs_gc_start_commit()
856 err = PTR_ERR(lp); in ubifs_gc_start_commit()
859 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
860 ubifs_assert(!(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
864 list_for_each_entry(idx_gc, &c->idx_gc, list) in ubifs_gc_start_commit()
865 idx_gc->unmap = 1; in ubifs_gc_start_commit()
869 lp = ubifs_fast_find_frdi_idx(c); in ubifs_gc_start_commit()
870 if (IS_ERR(lp)) { in ubifs_gc_start_commit()
871 err = PTR_ERR(lp); in ubifs_gc_start_commit()
874 if (!lp) in ubifs_gc_start_commit()
878 err = -ENOMEM; in ubifs_gc_start_commit()
881 ubifs_assert(!(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
882 ubifs_assert(lp->flags & LPROPS_INDEX); in ubifs_gc_start_commit()
884 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX; in ubifs_gc_start_commit()
885 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1); in ubifs_gc_start_commit()
886 if (IS_ERR(lp)) { in ubifs_gc_start_commit()
887 err = PTR_ERR(lp); in ubifs_gc_start_commit()
891 ubifs_assert(lp->flags & LPROPS_TAKEN); in ubifs_gc_start_commit()
892 ubifs_assert(!(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
893 idx_gc->lnum = lp->lnum; in ubifs_gc_start_commit()
894 idx_gc->unmap = 1; in ubifs_gc_start_commit()
895 list_add(&idx_gc->list, &c->idx_gc); in ubifs_gc_start_commit()
903 * ubifs_gc_end_commit - garbage collection at end of commit.
904 * @c: UBIFS file-system description object
906 * This function completes out-of-place garbage collection of index LEBs.
914 wbuf = &c->jheads[GCHD].wbuf; in ubifs_gc_end_commit()
915 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); in ubifs_gc_end_commit()
916 list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list) in ubifs_gc_end_commit()
917 if (idx_gc->unmap) { in ubifs_gc_end_commit()
918 dbg_gc("LEB %d", idx_gc->lnum); in ubifs_gc_end_commit()
919 err = ubifs_leb_unmap(c, idx_gc->lnum); in ubifs_gc_end_commit()
922 err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC, in ubifs_gc_end_commit()
923 LPROPS_NC, 0, LPROPS_TAKEN, -1); in ubifs_gc_end_commit()
926 list_del(&idx_gc->list); in ubifs_gc_end_commit()
930 mutex_unlock(&wbuf->io_mutex); in ubifs_gc_end_commit()
935 * ubifs_destroy_idx_gc - destroy idx_gc list.
936 * @c: UBIFS file-system description object
938 * This function destroys the @c->idx_gc list. It is called when unmounting
944 while (!list_empty(&c->idx_gc)) { in ubifs_destroy_idx_gc()
947 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, in ubifs_destroy_idx_gc()
949 c->idx_gc_cnt -= 1; in ubifs_destroy_idx_gc()
950 list_del(&idx_gc->list); in ubifs_destroy_idx_gc()
956 * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
957 * @c: UBIFS file-system description object
966 if (list_empty(&c->idx_gc)) in ubifs_get_idx_gc_leb()
967 return -ENOSPC; in ubifs_get_idx_gc_leb()
968 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list); in ubifs_get_idx_gc_leb()
969 lnum = idx_gc->lnum; in ubifs_get_idx_gc_leb()
970 /* c->idx_gc_cnt is updated by the caller when lprops are updated */ in ubifs_get_idx_gc_leb()
971 list_del(&idx_gc->list); in ubifs_get_idx_gc_leb()