Lines Matching +full:non +full:- +full:negative
1 // SPDX-License-Identifier: GPL-2.0-only
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
58 * switch_gc_head - switch the garbage collection journal head.
59 * @c: UBIFS file-system description object
62 * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
63 * and other negative error code in case of failures.
67 int err, gc_lnum = c->gc_lnum; in switch_gc_head()
68 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in switch_gc_head()
70 ubifs_assert(c, gc_lnum != -1); in switch_gc_head()
72 wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum, in switch_gc_head()
73 c->leb_size - wbuf->offs - wbuf->used); in switch_gc_head()
80 * The GC write-buffer was synchronized, we may safely unmap in switch_gc_head()
81 * 'c->gc_lnum'. in switch_gc_head()
91 c->gc_lnum = -1; in switch_gc_head()
97 * data_nodes_cmp - compare 2 data nodes.
98 * @priv: UBIFS file-system description object
103 * inode or block number, and %-1 otherwise.
119 ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DATA_KEY); in data_nodes_cmp()
120 ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DATA_KEY); in data_nodes_cmp()
121 ubifs_assert(c, sa->type == UBIFS_DATA_NODE); in data_nodes_cmp()
122 ubifs_assert(c, sb->type == UBIFS_DATA_NODE); in data_nodes_cmp()
124 inuma = key_inum(c, &sa->key); in data_nodes_cmp()
125 inumb = key_inum(c, &sb->key); in data_nodes_cmp()
128 unsigned int blka = key_block(c, &sa->key); in data_nodes_cmp()
129 unsigned int blkb = key_block(c, &sb->key); in data_nodes_cmp()
132 return -1; in data_nodes_cmp()
134 return -1; in data_nodes_cmp()
140 * nondata_nodes_cmp - compare 2 non-data nodes.
141 * @priv: UBIFS file-system description object
163 ubifs_assert(c, key_type(c, &sa->key) != UBIFS_DATA_KEY && in nondata_nodes_cmp()
164 key_type(c, &sb->key) != UBIFS_DATA_KEY); in nondata_nodes_cmp()
165 ubifs_assert(c, sa->type != UBIFS_DATA_NODE && in nondata_nodes_cmp()
166 sb->type != UBIFS_DATA_NODE); in nondata_nodes_cmp()
169 if (sa->type == UBIFS_INO_NODE) { in nondata_nodes_cmp()
170 if (sb->type == UBIFS_INO_NODE) in nondata_nodes_cmp()
171 return sb->len - sa->len; in nondata_nodes_cmp()
172 return -1; in nondata_nodes_cmp()
174 if (sb->type == UBIFS_INO_NODE) in nondata_nodes_cmp()
177 ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DENT_KEY || in nondata_nodes_cmp()
178 key_type(c, &sa->key) == UBIFS_XENT_KEY); in nondata_nodes_cmp()
179 ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DENT_KEY || in nondata_nodes_cmp()
180 key_type(c, &sb->key) == UBIFS_XENT_KEY); in nondata_nodes_cmp()
181 ubifs_assert(c, sa->type == UBIFS_DENT_NODE || in nondata_nodes_cmp()
182 sa->type == UBIFS_XENT_NODE); in nondata_nodes_cmp()
183 ubifs_assert(c, sb->type == UBIFS_DENT_NODE || in nondata_nodes_cmp()
184 sb->type == UBIFS_XENT_NODE); in nondata_nodes_cmp()
186 inuma = key_inum(c, &sa->key); in nondata_nodes_cmp()
187 inumb = key_inum(c, &sb->key); in nondata_nodes_cmp()
190 uint32_t hasha = key_hash(c, &sa->key); in nondata_nodes_cmp()
191 uint32_t hashb = key_hash(c, &sb->key); in nondata_nodes_cmp()
194 return -1; in nondata_nodes_cmp()
196 return -1; in nondata_nodes_cmp()
202 * sort_nodes - sort nodes for GC.
203 * @c: UBIFS file-system description object
205 * @nondata: contains non-data nodes on exit
209 * kills obsolete nodes and separates data and non-data nodes to the
210 * @sleb->nodes and @nondata lists correspondingly.
212 * Data nodes are then sorted in block number order - this is important for
213 * bulk-read; data nodes with lower inode number go before data nodes with
217 * Non-data nodes are sorted as follows.
218 * o First go inode nodes - they are sorted in descending length order.
219 * o Then go directory entry nodes - they are sorted in hash order, which
225 * This function returns zero in case of success and a negative error code in
236 /* Separate data nodes and non-data nodes */ in sort_nodes()
237 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { in sort_nodes()
238 ubifs_assert(c, snod->type == UBIFS_INO_NODE || in sort_nodes()
239 snod->type == UBIFS_DATA_NODE || in sort_nodes()
240 snod->type == UBIFS_DENT_NODE || in sort_nodes()
241 snod->type == UBIFS_XENT_NODE || in sort_nodes()
242 snod->type == UBIFS_TRUN_NODE || in sort_nodes()
243 snod->type == UBIFS_AUTH_NODE); in sort_nodes()
245 if (snod->type != UBIFS_INO_NODE && in sort_nodes()
246 snod->type != UBIFS_DATA_NODE && in sort_nodes()
247 snod->type != UBIFS_DENT_NODE && in sort_nodes()
248 snod->type != UBIFS_XENT_NODE) { in sort_nodes()
250 list_del(&snod->list); in sort_nodes()
255 ubifs_assert(c, key_type(c, &snod->key) == UBIFS_DATA_KEY || in sort_nodes()
256 key_type(c, &snod->key) == UBIFS_INO_KEY || in sort_nodes()
257 key_type(c, &snod->key) == UBIFS_DENT_KEY || in sort_nodes()
258 key_type(c, &snod->key) == UBIFS_XENT_KEY); in sort_nodes()
260 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum, in sort_nodes()
261 snod->offs, 0); in sort_nodes()
267 list_del(&snod->list); in sort_nodes()
272 if (snod->len < *min) in sort_nodes()
273 *min = snod->len; in sort_nodes()
275 if (key_type(c, &snod->key) != UBIFS_DATA_KEY) in sort_nodes()
276 list_move_tail(&snod->list, nondata); in sort_nodes()
279 /* Sort data and non-data nodes */ in sort_nodes()
280 list_sort(c, &sleb->nodes, &data_nodes_cmp); in sort_nodes()
283 err = dbg_check_data_nodes_order(c, &sleb->nodes); in sort_nodes()
293 * move_node - move a node.
294 * @c: UBIFS file-system description object
297 * @wbuf: write-buffer to move node to
300 * destroys @snod. Returns zero in case of success and a negative error code in
306 int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used; in move_node()
309 err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len); in move_node()
313 err = ubifs_tnc_replace(c, &snod->key, sleb->lnum, in move_node()
314 snod->offs, new_lnum, new_offs, in move_node()
315 snod->len); in move_node()
316 list_del(&snod->list); in move_node()
322 * move_nodes - move nodes.
323 * @c: UBIFS file-system description object
327 * journal head. This function returns zero in case of success, %-EAGAIN if
328 * commit is required, and other negative error codes in case of other
335 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in move_nodes()
337 if (wbuf->lnum == -1) { in move_nodes()
351 /* Write nodes to their new location. Use the first-fit strategy */ in move_nodes()
357 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { in move_nodes()
358 avail = c->leb_size - wbuf->offs - wbuf->used - in move_nodes()
360 if (snod->len > avail) in move_nodes()
363 * bulk-read. in move_nodes()
367 err = ubifs_shash_update(c, c->jheads[GCHD].log_hash, in move_nodes()
368 snod->node, snod->len); in move_nodes()
378 /* Move non-data nodes */ in move_nodes()
380 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()
399 err = ubifs_shash_update(c, c->jheads[GCHD].log_hash, in move_nodes()
400 snod->node, snod->len); in move_nodes()
415 err = -ENOMEM; in move_nodes()
420 c->jheads[GCHD].log_hash); in move_nodes()
433 ubifs_add_dirt(c, wbuf->lnum, ubifs_auth_node_sz(c)); in move_nodes()
436 if (list_empty(&sleb->nodes) && list_empty(&nondata)) in move_nodes()
451 list_splice_tail(&nondata, &sleb->nodes); in move_nodes()
456 * gc_sync_wbufs - sync write-buffers for GC.
457 * @c: UBIFS file-system description object
460 * be in a write-buffer instead. That is, a node could be written to a
461 * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
462 * erased before the write-buffer is sync'd and then there is an unclean
464 * write-buffers.
466 * This function returns %0 on success or a negative error code on failure.
472 for (i = 0; i < c->jhead_cnt; i++) { in gc_sync_wbufs()
475 err = ubifs_wbuf_sync(&c->jheads[i].wbuf); in gc_sync_wbufs()
483 * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
484 * @c: UBIFS file-system description object
487 * This function garbage-collects an LEB and returns one of the @LEB_FREED,
488 * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
489 * required, and other negative error codes in case of failures.
495 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in ubifs_garbage_collect_leb()
496 int err = 0, lnum = lp->lnum; in ubifs_garbage_collect_leb()
498 ubifs_assert(c, c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 || in ubifs_garbage_collect_leb()
499 c->need_recovery); in ubifs_garbage_collect_leb()
500 ubifs_assert(c, c->gc_lnum != lnum); in ubifs_garbage_collect_leb()
501 ubifs_assert(c, wbuf->lnum != lnum); in ubifs_garbage_collect_leb()
503 if (lp->free + lp->dirty == c->leb_size) { in ubifs_garbage_collect_leb()
504 /* Special case - a free LEB */ in ubifs_garbage_collect_leb()
505 dbg_gc("LEB %d is free, return it", lp->lnum); in ubifs_garbage_collect_leb()
506 ubifs_assert(c, !(lp->flags & LPROPS_INDEX)); in ubifs_garbage_collect_leb()
508 if (lp->free != c->leb_size) { in ubifs_garbage_collect_leb()
512 * which obsoletes something in 'lp->lnum'. in ubifs_garbage_collect_leb()
517 err = ubifs_change_one_lp(c, lp->lnum, c->leb_size, in ubifs_garbage_collect_leb()
522 err = ubifs_leb_unmap(c, lp->lnum); in ubifs_garbage_collect_leb()
526 if (c->gc_lnum == -1) { in ubifs_garbage_collect_leb()
527 c->gc_lnum = lnum; in ubifs_garbage_collect_leb()
536 * (c->leb_size - lp->free). in ubifs_garbage_collect_leb()
538 sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); in ubifs_garbage_collect_leb()
542 ubifs_assert(c, !list_empty(&sleb->nodes)); in ubifs_garbage_collect_leb()
543 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list); in ubifs_garbage_collect_leb()
545 if (snod->type == UBIFS_IDX_NODE) { in ubifs_garbage_collect_leb()
549 lnum, lp->free, lp->dirty); in ubifs_garbage_collect_leb()
550 list_for_each_entry(snod, &sleb->nodes, list) { in ubifs_garbage_collect_leb()
551 struct ubifs_idx_node *idx = snod->node; in ubifs_garbage_collect_leb()
552 int level = le16_to_cpu(idx->level); in ubifs_garbage_collect_leb()
554 ubifs_assert(c, snod->type == UBIFS_IDX_NODE); in ubifs_garbage_collect_leb()
555 key_read(c, ubifs_idx_key(c, idx), &snod->key); in ubifs_garbage_collect_leb()
556 err = ubifs_dirty_idx_node(c, &snod->key, level, lnum, in ubifs_garbage_collect_leb()
557 snod->offs); in ubifs_garbage_collect_leb()
564 err = -ENOMEM; in ubifs_garbage_collect_leb()
568 idx_gc->lnum = lnum; in ubifs_garbage_collect_leb()
569 idx_gc->unmap = 0; in ubifs_garbage_collect_leb()
570 list_add(&idx_gc->list, &c->idx_gc); in ubifs_garbage_collect_leb()
578 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, in ubifs_garbage_collect_leb()
585 lnum, lp->free, lp->dirty); in ubifs_garbage_collect_leb()
595 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0); in ubifs_garbage_collect_leb()
600 c->gced_lnum = lnum; in ubifs_garbage_collect_leb()
602 c->gc_seq += 1; in ubifs_garbage_collect_leb()
605 if (c->gc_lnum == -1) { in ubifs_garbage_collect_leb()
606 c->gc_lnum = lnum; in ubifs_garbage_collect_leb()
627 c->gced_lnum = lnum; in ubifs_garbage_collect_leb()
629 c->gc_seq += 1; in ubifs_garbage_collect_leb()
635 * ubifs_garbage_collect - UBIFS garbage collector.
636 * @c: UBIFS file-system description object
639 * This function does out-of-place garbage collection. The return codes are:
641 * o %-EAGAIN if the caller has to run commit;
642 * o %-ENOSPC if GC failed to make any progress;
643 * o other negative error codes in case of other errors.
648 * caller might be holding the commit lock, so %-EAGAIN is returned instead;
649 * And this error code means that the caller has to run commit, and re-run GC
652 * There are many reasons why this function may return %-EAGAIN:
654 * @c->gc_lnum;
660 * Note, if the file-system is close to be full, this function may return
661 * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
668 * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
672 int i, err, ret, min_space = c->dead_wm; in ubifs_garbage_collect()
674 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf; in ubifs_garbage_collect()
677 ubifs_assert(c, !c->ro_media && !c->ro_mount); in ubifs_garbage_collect()
680 return -EAGAIN; in ubifs_garbage_collect()
682 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); in ubifs_garbage_collect()
684 if (c->ro_error) { in ubifs_garbage_collect()
685 ret = -EROFS; in ubifs_garbage_collect()
689 /* We expect the write-buffer to be empty on entry */ in ubifs_garbage_collect()
690 ubifs_assert(c, !wbuf->used); in ubifs_garbage_collect()
696 lp.lnum = -1; in ubifs_garbage_collect()
702 ret = -EAGAIN; in ubifs_garbage_collect()
706 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) { in ubifs_garbage_collect()
711 dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN"); in ubifs_garbage_collect()
713 ret = -EAGAIN; in ubifs_garbage_collect()
722 dbg_gc("hard limit, -ENOSPC"); in ubifs_garbage_collect()
723 ret = -ENOSPC; in ubifs_garbage_collect()
736 if (ret == -ENOSPC) in ubifs_garbage_collect()
745 space_before = c->leb_size - wbuf->offs - wbuf->used; in ubifs_garbage_collect()
746 if (wbuf->lnum == -1) in ubifs_garbage_collect()
751 if (ret == -EAGAIN) { in ubifs_garbage_collect()
756 * caller instead of the original '-EAGAIN'. in ubifs_garbage_collect()
763 * so setting ubifs to read-only, in ubifs_garbage_collect()
765 * return -EROFS and enter the "out" in ubifs_garbage_collect()
771 lp.lnum = -1; in ubifs_garbage_collect()
796 space_after = c->leb_size - wbuf->offs - wbuf->used; in ubifs_garbage_collect()
798 space_after - space_before); in ubifs_garbage_collect()
803 if (min_space < c->dead_wm) in ubifs_garbage_collect()
804 min_space = c->dead_wm; in ubifs_garbage_collect()
832 if (min_space > c->dark_wm) in ubifs_garbage_collect()
833 min_space = c->dark_wm; in ubifs_garbage_collect()
837 if (ret == -ENOSPC && !list_empty(&c->idx_gc)) { in ubifs_garbage_collect()
838 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN"); in ubifs_garbage_collect()
840 ret = -EAGAIN; in ubifs_garbage_collect()
845 err = ubifs_leb_unmap(c, c->gc_lnum); in ubifs_garbage_collect()
851 mutex_unlock(&wbuf->io_mutex); in ubifs_garbage_collect()
856 ubifs_assert(c, ret != -ENOSPC && ret != -EAGAIN); in ubifs_garbage_collect()
859 mutex_unlock(&wbuf->io_mutex); in ubifs_garbage_collect()
860 if (lp.lnum != -1) in ubifs_garbage_collect()
866 * ubifs_gc_start_commit - garbage collection at start of commit.
867 * @c: UBIFS file-system description object
874 * This function returns %0 upon success and a negative error code upon failure.
885 * Unmap (non-index) freeable LEBs. Note that recovery requires that all in ubifs_gc_start_commit()
892 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
893 ubifs_assert(c, !(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
894 err = ubifs_leb_unmap(c, lp->lnum); in ubifs_gc_start_commit()
897 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0); in ubifs_gc_start_commit()
902 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
903 ubifs_assert(c, !(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
907 list_for_each_entry(idx_gc, &c->idx_gc, list) in ubifs_gc_start_commit()
908 idx_gc->unmap = 1; in ubifs_gc_start_commit()
921 err = -ENOMEM; in ubifs_gc_start_commit()
924 ubifs_assert(c, !(lp->flags & LPROPS_TAKEN)); in ubifs_gc_start_commit()
925 ubifs_assert(c, lp->flags & LPROPS_INDEX); in ubifs_gc_start_commit()
927 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX; in ubifs_gc_start_commit()
928 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1); in ubifs_gc_start_commit()
934 ubifs_assert(c, lp->flags & LPROPS_TAKEN); in ubifs_gc_start_commit()
935 ubifs_assert(c, !(lp->flags & LPROPS_INDEX)); in ubifs_gc_start_commit()
936 idx_gc->lnum = lp->lnum; in ubifs_gc_start_commit()
937 idx_gc->unmap = 1; in ubifs_gc_start_commit()
938 list_add(&idx_gc->list, &c->idx_gc); in ubifs_gc_start_commit()
946 * ubifs_gc_end_commit - garbage collection at end of commit.
947 * @c: UBIFS file-system description object
949 * This function completes out-of-place garbage collection of index LEBs.
957 wbuf = &c->jheads[GCHD].wbuf; in ubifs_gc_end_commit()
958 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead); in ubifs_gc_end_commit()
959 list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list) in ubifs_gc_end_commit()
960 if (idx_gc->unmap) { in ubifs_gc_end_commit()
961 dbg_gc("LEB %d", idx_gc->lnum); in ubifs_gc_end_commit()
962 err = ubifs_leb_unmap(c, idx_gc->lnum); in ubifs_gc_end_commit()
965 err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC, in ubifs_gc_end_commit()
966 LPROPS_NC, 0, LPROPS_TAKEN, -1); in ubifs_gc_end_commit()
969 list_del(&idx_gc->list); in ubifs_gc_end_commit()
973 mutex_unlock(&wbuf->io_mutex); in ubifs_gc_end_commit()
978 * ubifs_destroy_idx_gc - destroy idx_gc list.
979 * @c: UBIFS file-system description object
981 * This function destroys the @c->idx_gc list. It is called when unmounting
982 * so locks are not needed. Returns zero in case of success and a negative
987 while (!list_empty(&c->idx_gc)) { in ubifs_destroy_idx_gc()
990 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, in ubifs_destroy_idx_gc()
992 c->idx_gc_cnt -= 1; in ubifs_destroy_idx_gc()
993 list_del(&idx_gc->list); in ubifs_destroy_idx_gc()
999 * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
1000 * @c: UBIFS file-system description object
1009 if (list_empty(&c->idx_gc)) in ubifs_get_idx_gc_leb()
1010 return -ENOSPC; in ubifs_get_idx_gc_leb()
1011 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list); in ubifs_get_idx_gc_leb()
1012 lnum = idx_gc->lnum; in ubifs_get_idx_gc_leb()
1013 /* c->idx_gc_cnt is updated by the caller when lprops are updated */ in ubifs_get_idx_gc_leb()
1014 list_del(&idx_gc->list); in ubifs_get_idx_gc_leb()