Line data Source code
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: Adrian Hunter
8 : * Artem Bityutskiy (Битюцкий Артём)
9 : */
10 :
11 : /*
12 : * This file implements garbage collection. The procedure for garbage collection
13 : * is different depending on whether a LEB as an index LEB (contains index
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
19 : * to be reused. Garbage collection will cause the number of dirty index nodes
20 : * to grow, however sufficient space is reserved for the index to ensure the
21 : * commit will never run out of space.
22 : *
23 : * Notes about dead watermark. At current UBIFS implementation we assume that
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
26 : * size, or min. UBIFS node size, depending on what is greater. Indeed, UBIFS
27 : * Garbage Collector has to synchronize the GC head's write buffer before
28 : * returning, so this is about wasting one min. I/O unit. However, UBIFS GC can
29 : * actually reclaim even very small pieces of dirty space by garbage collecting
30 : * enough dirty LEBs, but we do not bother doing this at this implementation.
31 : *
32 : * Notes about dark watermark. The results of GC work depends on how big are
33 : * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
34 : * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
35 : * have to waste large pieces of free space at the end of LEB B, because nodes
36 : * from LEB A would not fit. And the worst situation is when all nodes are of
37 : * maximum size. So dark watermark is the amount of free + dirty space in LEB
38 : * which are guaranteed to be reclaimable. If LEB has less space, the GC might
39 : * be unable to reclaim it. So, LEBs with free + dirty greater than dark
40 : * watermark are "good" LEBs from GC's point of view. The other LEBs are not so
41 : * good, and GC takes extra care when moving them.
42 : */
43 :
44 : #include "linux_err.h"
45 : #include "bitops.h"
46 : #include "kmem.h"
47 : #include "ubifs.h"
48 : #include "defs.h"
49 : #include "debug.h"
50 : #include "key.h"
51 : #include "misc.h"
52 :
53 : /*
54 : * GC may need to move more than one LEB to make progress. The below constants
55 : * define "soft" and "hard" limits on the number of LEBs the garbage collector
56 : * may move.
57 : */
58 : #define SOFT_LEBS_LIMIT 4
59 : #define HARD_LEBS_LIMIT 32
60 :
61 : /**
62 : * switch_gc_head - switch the garbage collection journal head.
63 : * @c: UBIFS file-system description object
64 : *
65 : * This function switch the GC head to the next LEB which is reserved in
66 : * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
67 : * and other negative error code in case of failures.
68 : */
69 0 : static int switch_gc_head(struct ubifs_info *c)
70 : {
71 0 : int err, gc_lnum = c->gc_lnum;
72 0 : struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
73 :
74 0 : ubifs_assert(c, gc_lnum != -1);
75 0 : dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
76 : wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
77 : c->leb_size - wbuf->offs - wbuf->used);
78 :
79 0 : err = ubifs_wbuf_sync_nolock(wbuf);
80 0 : if (err)
81 : return err;
82 :
83 : /*
84 : * The GC write-buffer was synchronized, we may safely unmap
85 : * 'c->gc_lnum'.
86 : */
87 0 : err = ubifs_leb_unmap(c, gc_lnum);
88 0 : if (err)
89 : return err;
90 :
91 0 : err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
92 0 : if (err)
93 : return err;
94 :
95 0 : c->gc_lnum = -1;
96 0 : err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0);
97 0 : return err;
98 : }
99 :
100 : /**
101 : * data_nodes_cmp - compare 2 data nodes.
102 : * @priv: UBIFS file-system description object
103 : * @a: first data node
104 : * @b: second data node
105 : *
106 : * This function compares data nodes @a and @b. Returns %1 if @a has greater
107 : * inode or block number, and %-1 otherwise.
108 : */
109 3 : static int data_nodes_cmp(void *priv, const struct list_head *a,
110 : const struct list_head *b)
111 : {
112 : ino_t inuma, inumb;
113 3 : struct ubifs_info *c = priv;
114 : struct ubifs_scan_node *sa, *sb;
115 :
116 : cond_resched();
117 3 : if (a == b)
118 : return 0;
119 :
120 3 : sa = list_entry(a, struct ubifs_scan_node, list);
121 3 : sb = list_entry(b, struct ubifs_scan_node, list);
122 :
123 6 : ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DATA_KEY);
124 6 : ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DATA_KEY);
125 3 : ubifs_assert(c, sa->type == UBIFS_DATA_NODE);
126 3 : ubifs_assert(c, sb->type == UBIFS_DATA_NODE);
127 :
128 6 : inuma = key_inum(c, &sa->key);
129 6 : inumb = key_inum(c, &sb->key);
130 :
131 3 : if (inuma == inumb) {
132 0 : unsigned int blka = key_block(c, &sa->key);
133 0 : unsigned int blkb = key_block(c, &sb->key);
134 :
135 0 : if (blka <= blkb)
136 : return -1;
137 3 : } else if (inuma <= inumb)
138 : return -1;
139 :
140 : return 1;
141 : }
142 :
143 : /*
144 : * nondata_nodes_cmp - compare 2 non-data nodes.
145 : * @priv: UBIFS file-system description object
146 : * @a: first node
147 : * @a: second node
148 : *
149 : * This function compares nodes @a and @b. It makes sure that inode nodes go
150 : * first and sorted by length in descending order. Directory entry nodes go
151 : * after inode nodes and are sorted in ascending hash valuer order.
152 : */
153 29637 : static int nondata_nodes_cmp(void *priv, const struct list_head *a,
154 : const struct list_head *b)
155 : {
156 : ino_t inuma, inumb;
157 29637 : struct ubifs_info *c = priv;
158 : struct ubifs_scan_node *sa, *sb;
159 :
160 : cond_resched();
161 29637 : if (a == b)
162 : return 0;
163 :
164 29637 : sa = list_entry(a, struct ubifs_scan_node, list);
165 29637 : sb = list_entry(b, struct ubifs_scan_node, list);
166 :
167 88911 : ubifs_assert(c, key_type(c, &sa->key) != UBIFS_DATA_KEY &&
168 : key_type(c, &sb->key) != UBIFS_DATA_KEY);
169 29637 : ubifs_assert(c, sa->type != UBIFS_DATA_NODE &&
170 : sb->type != UBIFS_DATA_NODE);
171 :
172 : /* Inodes go before directory entries */
173 29637 : if (sa->type == UBIFS_INO_NODE) {
174 10599 : if (sb->type == UBIFS_INO_NODE)
175 8800 : return sb->len - sa->len;
176 : return -1;
177 : }
178 19038 : if (sb->type == UBIFS_INO_NODE)
179 : return 1;
180 :
181 30194 : ubifs_assert(c, key_type(c, &sa->key) == UBIFS_DENT_KEY ||
182 : key_type(c, &sa->key) == UBIFS_XENT_KEY);
183 30194 : ubifs_assert(c, key_type(c, &sb->key) == UBIFS_DENT_KEY ||
184 : key_type(c, &sb->key) == UBIFS_XENT_KEY);
185 15097 : ubifs_assert(c, sa->type == UBIFS_DENT_NODE ||
186 : sa->type == UBIFS_XENT_NODE);
187 15097 : ubifs_assert(c, sb->type == UBIFS_DENT_NODE ||
188 : sb->type == UBIFS_XENT_NODE);
189 :
190 30194 : inuma = key_inum(c, &sa->key);
191 30194 : inumb = key_inum(c, &sb->key);
192 :
193 15097 : if (inuma == inumb) {
194 60 : uint32_t hasha = key_hash(c, &sa->key);
195 60 : uint32_t hashb = key_hash(c, &sb->key);
196 :
197 30 : if (hasha <= hashb)
198 : return -1;
199 15067 : } else if (inuma <= inumb)
200 : return -1;
201 :
202 : return 1;
203 : }
204 :
205 : /**
206 : * sort_nodes - sort nodes for GC.
207 : * @c: UBIFS file-system description object
208 : * @sleb: describes nodes to sort and contains the result on exit
209 : * @nondata: contains non-data nodes on exit
210 : * @min: minimum node size is returned here
211 : *
212 : * This function sorts the list of inodes to garbage collect. First of all, it
213 : * kills obsolete nodes and separates data and non-data nodes to the
214 : * @sleb->nodes and @nondata lists correspondingly.
215 : *
216 : * Data nodes are then sorted in block number order - this is important for
217 : * bulk-read; data nodes with lower inode number go before data nodes with
218 : * higher inode number, and data nodes with lower block number go before data
219 : * nodes with higher block number;
220 : *
221 : * Non-data nodes are sorted as follows.
222 : * o First go inode nodes - they are sorted in descending length order.
223 : * o Then go directory entry nodes - they are sorted in hash order, which
224 : * should supposedly optimize 'readdir()'. Direntry nodes with lower parent
225 : * inode number go before direntry nodes with higher parent inode number,
226 : * and direntry nodes with lower name hash values go before direntry nodes
227 : * with higher name hash values.
228 : *
229 : * This function returns zero in case of success and a negative error code in
230 : * case of failure.
231 : */
232 50 : static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
233 : struct list_head *nondata, int *min)
234 : {
235 : int err;
236 : struct ubifs_scan_node *snod, *tmp;
237 :
238 50 : *min = INT_MAX;
239 :
240 : /* Separate data nodes and non-data nodes */
241 38326 : list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
242 38276 : ubifs_assert(c, snod->type == UBIFS_INO_NODE ||
243 : snod->type == UBIFS_DATA_NODE ||
244 : snod->type == UBIFS_DENT_NODE ||
245 : snod->type == UBIFS_XENT_NODE ||
246 : snod->type == UBIFS_TRUN_NODE ||
247 : snod->type == UBIFS_AUTH_NODE);
248 :
249 76552 : if (snod->type != UBIFS_INO_NODE &&
250 : snod->type != UBIFS_DATA_NODE &&
251 38276 : snod->type != UBIFS_DENT_NODE &&
252 : snod->type != UBIFS_XENT_NODE) {
253 : /* Probably truncation node, zap it */
254 350 : list_del(&snod->list);
255 175 : kfree(snod);
256 175 : continue;
257 : }
258 :
259 76202 : ubifs_assert(c, key_type(c, &snod->key) == UBIFS_DATA_KEY ||
260 : key_type(c, &snod->key) == UBIFS_INO_KEY ||
261 : key_type(c, &snod->key) == UBIFS_DENT_KEY ||
262 : key_type(c, &snod->key) == UBIFS_XENT_KEY);
263 :
264 38101 : err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
265 : snod->offs, 0);
266 38101 : if (err < 0)
267 : return err;
268 :
269 38101 : if (!err) {
270 : /* The node is obsolete, remove it from the list */
271 65266 : list_del(&snod->list);
272 32633 : kfree(snod);
273 32633 : continue;
274 : }
275 :
276 5468 : if (snod->len < *min)
277 94 : *min = snod->len;
278 :
279 10936 : if (key_type(c, &snod->key) != UBIFS_DATA_KEY)
280 5450 : list_move_tail(&snod->list, nondata);
281 : }
282 :
283 : /* Sort data and non-data nodes */
284 50 : list_sort(c, &sleb->nodes, &data_nodes_cmp);
285 50 : list_sort(c, nondata, &nondata_nodes_cmp);
286 :
287 50 : err = dbg_check_data_nodes_order(c, &sleb->nodes);
288 : if (err)
289 : return err;
290 50 : err = dbg_check_nondata_nodes_order(c, nondata);
291 : if (err)
292 : return err;
293 : return 0;
294 : }
295 :
296 : /**
297 : * move_node - move a node.
298 : * @c: UBIFS file-system description object
299 : * @sleb: describes the LEB to move nodes from
300 : * @snod: the mode to move
301 : * @wbuf: write-buffer to move node to
302 : *
303 : * This function moves node @snod to @wbuf, changes TNC correspondingly, and
304 : * destroys @snod. Returns zero in case of success and a negative error code in
305 : * case of failure.
306 : */
307 5468 : static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
308 : struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf)
309 : {
310 5468 : int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;
311 :
312 : cond_resched();
313 5468 : err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);
314 5468 : if (err)
315 : return err;
316 :
317 5468 : err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
318 : snod->offs, new_lnum, new_offs,
319 : snod->len);
320 10936 : list_del(&snod->list);
321 5468 : kfree(snod);
322 : return err;
323 : }
324 :
325 : /**
326 : * move_nodes - move nodes.
327 : * @c: UBIFS file-system description object
328 : * @sleb: describes the LEB to move nodes from
329 : *
330 : * This function moves valid nodes from data LEB described by @sleb to the GC
331 : * journal head. This function returns zero in case of success, %-EAGAIN if
332 : * commit is required, and other negative error codes in case of other
333 : * failures.
334 : */
335 50 : static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
336 : {
337 : int err, min;
338 50 : LIST_HEAD(nondata);
339 50 : struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
340 :
341 50 : if (wbuf->lnum == -1) {
342 : /*
343 : * The GC journal head is not set, because it is the first GC
344 : * invocation since mount.
345 : */
346 0 : err = switch_gc_head(c);
347 0 : if (err)
348 : return err;
349 : }
350 :
351 50 : err = sort_nodes(c, sleb, &nondata, &min);
352 50 : if (err)
353 : goto out;
354 :
355 : /* Write nodes to their new location. Use the first-fit strategy */
356 : while (1) {
357 50 : int avail, moved = 0;
358 : struct ubifs_scan_node *snod, *tmp;
359 :
360 : /* Move data nodes */
361 68 : list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
362 36 : avail = c->leb_size - wbuf->offs - wbuf->used -
363 18 : ubifs_auth_node_sz(c);
364 18 : if (snod->len > avail)
365 : /*
366 : * Do not skip data nodes in order to optimize
367 : * bulk-read.
368 : */
369 : break;
370 :
371 36 : err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,
372 18 : snod->node, snod->len);
373 18 : if (err)
374 : goto out;
375 :
376 18 : err = move_node(c, sleb, snod, wbuf);
377 18 : if (err)
378 : goto out;
379 18 : moved = 1;
380 : }
381 :
382 : /* Move non-data nodes */
383 5500 : list_for_each_entry_safe(snod, tmp, &nondata, list) {
384 10900 : avail = c->leb_size - wbuf->offs - wbuf->used -
385 5450 : ubifs_auth_node_sz(c);
386 5450 : if (avail < min)
387 : break;
388 :
389 5450 : if (snod->len > avail) {
390 : /*
391 : * Keep going only if this is an inode with
392 : * some data. Otherwise stop and switch the GC
393 : * head. IOW, we assume that data-less inode
394 : * nodes and direntry nodes are roughly of the
395 : * same size.
396 : */
397 0 : if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||
398 : snod->len == UBIFS_INO_NODE_SZ)
399 : break;
400 0 : continue;
401 : }
402 :
403 10900 : err = ubifs_shash_update(c, c->jheads[GCHD].log_hash,
404 5450 : snod->node, snod->len);
405 5450 : if (err)
406 : goto out;
407 :
408 5450 : err = move_node(c, sleb, snod, wbuf);
409 5450 : if (err)
410 : goto out;
411 : moved = 1;
412 : }
413 :
414 50 : if (ubifs_authenticated(c) && moved) {
415 : struct ubifs_auth_node *auth;
416 :
417 0 : auth = kmalloc(ubifs_auth_node_sz(c), GFP_NOFS);
418 0 : if (!auth) {
419 : err = -ENOMEM;
420 : goto out;
421 : }
422 :
423 0 : err = ubifs_prepare_auth_node(c, auth,
424 0 : c->jheads[GCHD].log_hash);
425 : if (err) {
426 : kfree(auth);
427 : goto out;
428 : }
429 :
430 0 : err = ubifs_wbuf_write_nolock(wbuf, auth,
431 : ubifs_auth_node_sz(c));
432 0 : if (err) {
433 : kfree(auth);
434 : goto out;
435 : }
436 :
437 0 : ubifs_add_dirt(c, wbuf->lnum, ubifs_auth_node_sz(c));
438 : }
439 :
440 150 : if (list_empty(&sleb->nodes) && list_empty(&nondata))
441 : break;
442 :
443 : /*
444 : * Waste the rest of the space in the LEB and switch to the
445 : * next LEB.
446 : */
447 0 : err = switch_gc_head(c);
448 0 : if (err)
449 : goto out;
450 : }
451 :
452 : return 0;
453 :
454 0 : out:
455 0 : list_splice_tail(&nondata, &sleb->nodes);
456 : return err;
457 : }
458 :
459 : /**
460 : * gc_sync_wbufs - sync write-buffers for GC.
461 : * @c: UBIFS file-system description object
462 : *
463 : * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
464 : * be in a write-buffer instead. That is, a node could be written to a
465 : * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
466 : * erased before the write-buffer is sync'd and then there is an unclean
467 : * unmount, then an existing node is lost. To avoid this, we sync all
468 : * write-buffers.
469 : *
470 : * This function returns %0 on success or a negative error code on failure.
471 : */
472 51 : static int gc_sync_wbufs(struct ubifs_info *c)
473 : {
474 : int err, i;
475 :
476 204 : for (i = 0; i < c->jhead_cnt; i++) {
477 153 : if (i == GCHD)
478 51 : continue;
479 102 : err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
480 102 : if (err)
481 : return err;
482 : }
483 : return 0;
484 : }
485 :
486 : /**
487 : * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
488 : * @c: UBIFS file-system description object
489 : * @lp: describes the LEB to garbage collect
490 : *
491 : * This function garbage-collects an LEB and returns one of the @LEB_FREED,
492 : * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
493 : * required, and other negative error codes in case of failures.
494 : */
495 272 : int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
496 : {
497 : struct ubifs_scan_leb *sleb;
498 : struct ubifs_scan_node *snod;
499 272 : struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
500 272 : int err = 0, lnum = lp->lnum;
501 :
502 272 : ubifs_assert(c, c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
503 : c->need_recovery);
504 272 : ubifs_assert(c, c->gc_lnum != lnum);
505 272 : ubifs_assert(c, wbuf->lnum != lnum);
506 :
507 272 : if (lp->free + lp->dirty == c->leb_size) {
508 : /* Special case - a free LEB */
509 222 : dbg_gc("LEB %d is free, return it", lp->lnum);
510 222 : ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
511 :
512 222 : if (lp->free != c->leb_size) {
513 : /*
514 : * Write buffers must be sync'd before unmapping
515 : * freeable LEBs, because one of them may contain data
516 : * which obsoletes something in 'lp->lnum'.
517 : */
518 1 : err = gc_sync_wbufs(c);
519 1 : if (err)
520 : return err;
521 1 : err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,
522 : 0, 0, 0, 0);
523 1 : if (err)
524 : return err;
525 : }
526 222 : err = ubifs_leb_unmap(c, lp->lnum);
527 222 : if (err)
528 : return err;
529 :
530 222 : if (c->gc_lnum == -1) {
531 222 : c->gc_lnum = lnum;
532 222 : return LEB_RETAINED;
533 : }
534 :
535 : return LEB_FREED;
536 : }
537 :
538 : /*
539 : * We scan the entire LEB even though we only really need to scan up to
540 : * (c->leb_size - lp->free).
541 : */
542 50 : sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
543 50 : if (IS_ERR(sleb))
544 0 : return PTR_ERR(sleb);
545 :
546 100 : ubifs_assert(c, !list_empty(&sleb->nodes));
547 50 : snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
548 :
549 50 : if (snod->type == UBIFS_IDX_NODE) {
550 : struct ubifs_gced_idx_leb *idx_gc;
551 :
552 0 : dbg_gc("indexing LEB %d (free %d, dirty %d)",
553 : lnum, lp->free, lp->dirty);
554 0 : list_for_each_entry(snod, &sleb->nodes, list) {
555 0 : struct ubifs_idx_node *idx = snod->node;
556 0 : int level = le16_to_cpu(idx->level);
557 :
558 0 : ubifs_assert(c, snod->type == UBIFS_IDX_NODE);
559 0 : key_read(c, ubifs_idx_key(c, idx), &snod->key);
560 0 : err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
561 : snod->offs);
562 0 : if (err)
563 : goto out;
564 : }
565 :
566 0 : idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
567 0 : if (!idx_gc) {
568 : err = -ENOMEM;
569 : goto out;
570 : }
571 :
572 0 : idx_gc->lnum = lnum;
573 0 : idx_gc->unmap = 0;
574 0 : list_add(&idx_gc->list, &c->idx_gc);
575 :
576 : /*
577 : * Don't release the LEB until after the next commit, because
578 : * it may contain data which is needed for recovery. So
579 : * although we freed this LEB, it will become usable only after
580 : * the commit.
581 : */
582 0 : err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
583 : LPROPS_INDEX, 1);
584 0 : if (err)
585 : goto out;
586 0 : err = LEB_FREED_IDX;
587 : } else {
588 50 : dbg_gc("data LEB %d (free %d, dirty %d)",
589 : lnum, lp->free, lp->dirty);
590 :
591 50 : err = move_nodes(c, sleb);
592 50 : if (err)
593 : goto out_inc_seq;
594 :
595 50 : err = gc_sync_wbufs(c);
596 50 : if (err)
597 : goto out_inc_seq;
598 :
599 50 : err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
600 50 : if (err)
601 : goto out_inc_seq;
602 :
603 : /* Allow for races with TNC */
604 50 : c->gced_lnum = lnum;
605 : smp_wmb();
606 50 : c->gc_seq += 1;
607 : smp_wmb();
608 :
609 50 : if (c->gc_lnum == -1) {
610 50 : c->gc_lnum = lnum;
611 50 : err = LEB_RETAINED;
612 : } else {
613 0 : err = ubifs_wbuf_sync_nolock(wbuf);
614 0 : if (err)
615 : goto out;
616 :
617 0 : err = ubifs_leb_unmap(c, lnum);
618 0 : if (err)
619 : goto out;
620 :
621 0 : err = LEB_FREED;
622 : }
623 : }
624 :
625 50 : out:
626 50 : ubifs_scan_destroy(sleb);
627 50 : return err;
628 :
629 0 : out_inc_seq:
630 : /* We may have moved at least some nodes so allow for races with TNC */
631 0 : c->gced_lnum = lnum;
632 : smp_wmb();
633 0 : c->gc_seq += 1;
634 : smp_wmb();
635 0 : goto out;
636 : }
637 :
638 : /**
639 : * ubifs_garbage_collect - UBIFS garbage collector.
640 : * @c: UBIFS file-system description object
641 : * @anyway: do GC even if there are free LEBs
642 : *
643 : * This function does out-of-place garbage collection. The return codes are:
644 : * o positive LEB number if the LEB has been freed and may be used;
645 : * o %-EAGAIN if the caller has to run commit;
646 : * o %-ENOSPC if GC failed to make any progress;
647 : * o other negative error codes in case of other errors.
648 : *
649 : * Garbage collector writes data to the journal when GC'ing data LEBs, and just
650 : * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
651 : * commit may be required. But commit cannot be run from inside GC, because the
652 : * caller might be holding the commit lock, so %-EAGAIN is returned instead;
653 : * And this error code means that the caller has to run commit, and re-run GC
654 : * if there is still no free space.
655 : *
656 : * There are many reasons why this function may return %-EAGAIN:
657 : * o the log is full and there is no space to write an LEB reference for
658 : * @c->gc_lnum;
659 : * o the journal is too large and exceeds size limitations;
660 : * o GC moved indexing LEBs, but they can be used only after the commit;
661 : * o the shrinker fails to find clean znodes to free and requests the commit;
662 : * o etc.
663 : *
664 : * Note, if the file-system is close to be full, this function may return
665 : * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
666 : * the function. E.g., this happens if the limits on the journal size are too
667 : * tough and GC writes too much to the journal before an LEB is freed. This
668 : * might also mean that the journal is too large, and the TNC becomes to big,
669 : * so that the shrinker is constantly called, finds not clean znodes to free,
670 : * and requests commit. Well, this may also happen if the journal is all right,
671 : * but another kernel process consumes too much memory. Anyway, infinite
672 : * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
673 : */
674 0 : int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
675 : {
676 0 : int i, err, ret, min_space = c->dead_wm;
677 : struct ubifs_lprops lp;
678 0 : struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
679 :
680 0 : ubifs_assert_cmt_locked(c);
681 0 : ubifs_assert(c, !c->ro_media && !c->ro_mount);
682 :
683 0 : if (ubifs_gc_should_commit(c))
684 : return -EAGAIN;
685 :
686 0 : mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
687 :
688 0 : if (c->ro_error) {
689 : ret = -EROFS;
690 : goto out_unlock;
691 : }
692 :
693 : /* We expect the write-buffer to be empty on entry */
694 0 : ubifs_assert(c, !wbuf->used);
695 :
696 0 : for (i = 0; ; i++) {
697 : int space_before, space_after;
698 :
699 : /* Maybe continue after find and break before find */
700 0 : lp.lnum = -1;
701 :
702 : cond_resched();
703 :
704 : /* Give the commit an opportunity to run */
705 0 : if (ubifs_gc_should_commit(c)) {
706 : ret = -EAGAIN;
707 : break;
708 : }
709 :
710 0 : if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
711 : /*
712 : * We've done enough iterations. Indexing LEBs were
713 : * moved and will be available after the commit.
714 : */
715 0 : dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
716 0 : ubifs_commit_required(c);
717 0 : ret = -EAGAIN;
718 : break;
719 : }
720 :
721 0 : if (i > HARD_LEBS_LIMIT) {
722 : /*
723 : * We've moved too many LEBs and have not made
724 : * progress, give up.
725 : */
726 0 : dbg_gc("hard limit, -ENOSPC");
727 : ret = -ENOSPC;
728 : break;
729 : }
730 :
731 : /*
732 : * Empty and freeable LEBs can turn up while we waited for
733 : * the wbuf lock, or while we have been running GC. In that
734 : * case, we should just return one of those instead of
735 : * continuing to GC dirty LEBs. Hence we request
736 : * 'ubifs_find_dirty_leb()' to return an empty LEB if it can.
737 : */
738 0 : ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
739 0 : if (ret) {
740 0 : if (ret == -ENOSPC)
741 0 : dbg_gc("no more dirty LEBs");
742 : break;
743 : }
744 :
745 0 : dbg_gc("found LEB %d: free %d, dirty %d, sum %d (min. space %d)",
746 : lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty,
747 : min_space);
748 :
749 0 : space_before = c->leb_size - wbuf->offs - wbuf->used;
750 0 : if (wbuf->lnum == -1)
751 0 : space_before = 0;
752 :
753 0 : ret = ubifs_garbage_collect_leb(c, &lp);
754 0 : if (ret < 0) {
755 0 : if (ret == -EAGAIN) {
756 : /*
757 : * This is not error, so we have to return the
758 : * LEB to lprops. But if 'ubifs_return_leb()'
759 : * fails, its failure code is propagated to the
760 : * caller instead of the original '-EAGAIN'.
761 : */
762 0 : err = ubifs_return_leb(c, lp.lnum);
763 0 : if (err) {
764 0 : ret = err;
765 : /*
766 : * An LEB may always be "taken",
767 : * so setting ubifs to read-only,
768 : * and then executing sync wbuf will
769 : * return -EROFS and enter the "out"
770 : * error branch.
771 : */
772 0 : ubifs_ro_mode(c, ret);
773 : }
774 : /* Maybe double return LEB if goto out */
775 0 : lp.lnum = -1;
776 0 : break;
777 : }
778 : goto out;
779 : }
780 :
781 0 : if (ret == LEB_FREED) {
782 : /* An LEB has been freed and is ready for use */
783 0 : dbg_gc("LEB %d freed, return", lp.lnum);
784 0 : ret = lp.lnum;
785 0 : break;
786 : }
787 :
788 0 : if (ret == LEB_FREED_IDX) {
789 : /*
790 : * This was an indexing LEB and it cannot be
791 : * immediately used. And instead of requesting the
792 : * commit straight away, we try to garbage collect some
793 : * more.
794 : */
795 0 : dbg_gc("indexing LEB %d freed, continue", lp.lnum);
796 0 : continue;
797 : }
798 :
799 0 : ubifs_assert(c, ret == LEB_RETAINED);
800 0 : space_after = c->leb_size - wbuf->offs - wbuf->used;
801 0 : dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
802 : space_after - space_before);
803 :
804 0 : if (space_after > space_before) {
805 : /* GC makes progress, keep working */
806 0 : min_space >>= 1;
807 0 : if (min_space < c->dead_wm)
808 0 : min_space = c->dead_wm;
809 0 : continue;
810 : }
811 :
812 0 : dbg_gc("did not make progress");
813 :
814 : /*
815 : * GC moved an LEB bud have not done any progress. This means
816 : * that the previous GC head LEB contained too few free space
817 : * and the LEB which was GC'ed contained only large nodes which
818 : * did not fit that space.
819 : *
820 : * We can do 2 things:
821 : * 1. pick another LEB in a hope it'll contain a small node
822 : * which will fit the space we have at the end of current GC
823 : * head LEB, but there is no guarantee, so we try this out
824 : * unless we have already been working for too long;
825 : * 2. request an LEB with more dirty space, which will force
826 : * 'ubifs_find_dirty_leb()' to start scanning the lprops
827 : * table, instead of just picking one from the heap
828 : * (previously it already picked the dirtiest LEB).
829 : */
830 0 : if (i < SOFT_LEBS_LIMIT) {
831 0 : dbg_gc("try again");
832 0 : continue;
833 : }
834 :
835 0 : min_space <<= 1;
836 0 : if (min_space > c->dark_wm)
837 0 : min_space = c->dark_wm;
838 0 : dbg_gc("set min. space to %d", min_space);
839 : }
840 :
841 0 : if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
842 0 : dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
843 0 : ubifs_commit_required(c);
844 0 : ret = -EAGAIN;
845 : }
846 :
847 0 : err = ubifs_wbuf_sync_nolock(wbuf);
848 0 : if (!err)
849 0 : err = ubifs_leb_unmap(c, c->gc_lnum);
850 0 : if (err) {
851 : ret = err;
852 : goto out;
853 : }
854 0 : out_unlock:
855 0 : mutex_unlock(&wbuf->io_mutex);
856 0 : return ret;
857 :
858 0 : out:
859 0 : ubifs_assert(c, ret < 0);
860 0 : ubifs_assert(c, ret != -ENOSPC && ret != -EAGAIN);
861 0 : ubifs_wbuf_sync_nolock(wbuf);
862 0 : ubifs_ro_mode(c, ret);
863 0 : mutex_unlock(&wbuf->io_mutex);
864 0 : if (lp.lnum != -1)
865 0 : ubifs_return_leb(c, lp.lnum);
866 : return ret;
867 : }
868 :
869 : /**
870 : * ubifs_gc_start_commit - garbage collection at start of commit.
871 : * @c: UBIFS file-system description object
872 : *
873 : * If a LEB has only dirty and free space, then we may safely unmap it and make
874 : * it free. Note, we cannot do this with indexing LEBs because dirty space may
875 : * correspond index nodes that are required for recovery. In that case, the
876 : * LEB cannot be unmapped until after the next commit.
877 : *
878 : * This function returns %0 upon success and a negative error code upon failure.
879 : */
880 3427 : int ubifs_gc_start_commit(struct ubifs_info *c)
881 : {
882 : struct ubifs_gced_idx_leb *idx_gc;
883 : const struct ubifs_lprops *lp;
884 3427 : int err = 0, flags;
885 :
886 : ubifs_get_lprops(c);
887 :
888 : /*
889 : * Unmap (non-index) freeable LEBs. Note that recovery requires that all
890 : * wbufs are sync'd before this, which is done in 'do_commit()'.
891 : */
892 : while (1) {
893 5346 : lp = ubifs_fast_find_freeable(c);
894 5346 : if (!lp)
895 : break;
896 1919 : ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
897 1919 : ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
898 1919 : err = ubifs_leb_unmap(c, lp->lnum);
899 1919 : if (err)
900 : goto out;
901 1919 : lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
902 1919 : if (IS_ERR(lp)) {
903 0 : err = PTR_ERR(lp);
904 0 : goto out;
905 : }
906 1919 : ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
907 1919 : ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
908 : }
909 :
910 : /* Mark GC'd index LEBs OK to unmap after this commit finishes */
911 3427 : list_for_each_entry(idx_gc, &c->idx_gc, list)
912 0 : idx_gc->unmap = 1;
913 :
914 : /* Record index freeable LEBs for unmapping after commit */
915 : while (1) {
916 3564 : lp = ubifs_fast_find_frdi_idx(c);
917 3564 : if (IS_ERR(lp)) {
918 0 : err = PTR_ERR(lp);
919 0 : goto out;
920 : }
921 3564 : if (!lp)
922 : break;
923 137 : idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
924 137 : if (!idx_gc) {
925 : err = -ENOMEM;
926 : goto out;
927 : }
928 137 : ubifs_assert(c, !(lp->flags & LPROPS_TAKEN));
929 137 : ubifs_assert(c, lp->flags & LPROPS_INDEX);
930 : /* Don't release the LEB until after the next commit */
931 137 : flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
932 137 : lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
933 137 : if (IS_ERR(lp)) {
934 0 : err = PTR_ERR(lp);
935 : kfree(idx_gc);
936 : goto out;
937 : }
938 137 : ubifs_assert(c, lp->flags & LPROPS_TAKEN);
939 137 : ubifs_assert(c, !(lp->flags & LPROPS_INDEX));
940 137 : idx_gc->lnum = lp->lnum;
941 137 : idx_gc->unmap = 1;
942 137 : list_add(&idx_gc->list, &c->idx_gc);
943 : }
944 3427 : out:
945 3427 : ubifs_release_lprops(c);
946 3427 : return err;
947 : }
948 :
949 : /**
950 : * ubifs_gc_end_commit - garbage collection at end of commit.
951 : * @c: UBIFS file-system description object
952 : *
953 : * This function completes out-of-place garbage collection of index LEBs.
954 : */
955 3398 : int ubifs_gc_end_commit(struct ubifs_info *c)
956 : {
957 : struct ubifs_gced_idx_leb *idx_gc, *tmp;
958 : struct ubifs_wbuf *wbuf;
959 3398 : int err = 0;
960 :
961 3398 : wbuf = &c->jheads[GCHD].wbuf;
962 3398 : mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
963 3535 : list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
964 137 : if (idx_gc->unmap) {
965 137 : dbg_gc("LEB %d", idx_gc->lnum);
966 137 : err = ubifs_leb_unmap(c, idx_gc->lnum);
967 137 : if (err)
968 : goto out;
969 137 : err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
970 : LPROPS_NC, 0, LPROPS_TAKEN, -1);
971 137 : if (err)
972 : goto out;
973 274 : list_del(&idx_gc->list);
974 : kfree(idx_gc);
975 : }
976 3398 : out:
977 3398 : mutex_unlock(&wbuf->io_mutex);
978 3398 : return err;
979 : }
980 :
981 : /**
982 : * ubifs_destroy_idx_gc - destroy idx_gc list.
983 : * @c: UBIFS file-system description object
984 : *
985 : * This function destroys the @c->idx_gc list. It is called when unmounting
986 : * so locks are not needed. Returns zero in case of success and a negative
987 : * error code in case of failure.
988 : */
989 1951 : void ubifs_destroy_idx_gc(struct ubifs_info *c)
990 : {
991 5853 : while (!list_empty(&c->idx_gc)) {
992 : struct ubifs_gced_idx_leb *idx_gc;
993 :
994 0 : idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
995 : list);
996 0 : c->idx_gc_cnt -= 1;
997 0 : list_del(&idx_gc->list);
998 : kfree(idx_gc);
999 : }
1000 1951 : }
1001 :
1002 : /**
1003 : * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
1004 : * @c: UBIFS file-system description object
1005 : *
1006 : * Called during start commit so locks are not needed.
1007 : */
1008 0 : int ubifs_get_idx_gc_leb(struct ubifs_info *c)
1009 : {
1010 : struct ubifs_gced_idx_leb *idx_gc;
1011 : int lnum;
1012 :
1013 0 : if (list_empty(&c->idx_gc))
1014 : return -ENOSPC;
1015 0 : idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
1016 0 : lnum = idx_gc->lnum;
1017 : /* c->idx_gc_cnt is updated by the caller when lprops are updated */
1018 0 : list_del(&idx_gc->list);
1019 0 : kfree(idx_gc);
1020 0 : return lnum;
1021 : }
|