blob: 9832f9abe28e08af3c444f03bb31b9bc0f84f3db [file] [log] [blame]
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001/*
2 * This file is part of UBIFS.
3 *
4 * Copyright (C) 2006-2008 Nokia Corporation.
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 as published by
8 * the Free Software Foundation.
9 *
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 * more details.
14 *
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 *
19 * Authors: Adrian Hunter
20 * Artem Bityutskiy (Битюцкий Артём)
21 */
22
23/*
24 * This file implements garbage collection. The procedure for garbage collection
25 * is different depending on whether a LEB as an index LEB (contains index
26 * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
27 * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
28 * nodes to the journal, at which point the garbage-collected LEB is free to be
29 * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
30 * dirty in the TNC, and after the next commit, the garbage-collected LEB is
31 * to be reused. Garbage collection will cause the number of dirty index nodes
32 * to grow, however sufficient space is reserved for the index to ensure the
33 * commit will never run out of space.
34 */
35
36#include <linux/pagemap.h>
37#include "ubifs.h"
38
39/*
40 * GC tries to optimize the way it fit nodes to available space, and it sorts
41 * nodes a little. The below constants are watermarks which define "large",
42 * "medium", and "small" nodes.
43 */
44#define MEDIUM_NODE_WM (UBIFS_BLOCK_SIZE / 4)
45#define SMALL_NODE_WM UBIFS_MAX_DENT_NODE_SZ
46
47/*
Frederik Schwarzer025dfda2008-10-16 19:02:37 +020048 * GC may need to move more than one LEB to make progress. The below constants
Artem Bityutskiy1e517642008-07-14 19:08:37 +030049 * define "soft" and "hard" limits on the number of LEBs the garbage collector
50 * may move.
51 */
52#define SOFT_LEBS_LIMIT 4
53#define HARD_LEBS_LIMIT 32
54
55/**
56 * switch_gc_head - switch the garbage collection journal head.
57 * @c: UBIFS file-system description object
58 * @buf: buffer to write
59 * @len: length of the buffer to write
60 * @lnum: LEB number written is returned here
61 * @offs: offset written is returned here
62 *
63 * This function switch the GC head to the next LEB which is reserved in
64 * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
65 * and other negative error code in case of failures.
66 */
67static int switch_gc_head(struct ubifs_info *c)
68{
69 int err, gc_lnum = c->gc_lnum;
70 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
71
72 ubifs_assert(gc_lnum != -1);
73 dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
74 wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
75 c->leb_size - wbuf->offs - wbuf->used);
76
77 err = ubifs_wbuf_sync_nolock(wbuf);
78 if (err)
79 return err;
80
81 /*
82 * The GC write-buffer was synchronized, we may safely unmap
83 * 'c->gc_lnum'.
84 */
85 err = ubifs_leb_unmap(c, gc_lnum);
86 if (err)
87 return err;
88
89 err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
90 if (err)
91 return err;
92
93 c->gc_lnum = -1;
94 err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0, UBI_LONGTERM);
95 return err;
96}
97
98/**
Adrian Hunter46773be2008-09-11 12:57:49 +030099 * joinup - bring data nodes for an inode together.
100 * @c: UBIFS file-system description object
101 * @sleb: describes scanned LEB
102 * @inum: inode number
103 * @blk: block number
104 * @data: list to which to add data nodes
105 *
106 * This function looks at the first few nodes in the scanned LEB @sleb and adds
107 * them to @data if they are data nodes from @inum and have a larger block
108 * number than @blk. This function returns %0 on success and a negative error
109 * code on failure.
110 */
111static int joinup(struct ubifs_info *c, struct ubifs_scan_leb *sleb, ino_t inum,
112 unsigned int blk, struct list_head *data)
113{
114 int err, cnt = 6, lnum = sleb->lnum, offs;
115 struct ubifs_scan_node *snod, *tmp;
116 union ubifs_key *key;
117
118 list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
119 key = &snod->key;
120 if (key_inum(c, key) == inum &&
121 key_type(c, key) == UBIFS_DATA_KEY &&
122 key_block(c, key) > blk) {
123 offs = snod->offs;
124 err = ubifs_tnc_has_node(c, key, 0, lnum, offs, 0);
125 if (err < 0)
126 return err;
127 list_del(&snod->list);
128 if (err) {
129 list_add_tail(&snod->list, data);
130 blk = key_block(c, key);
131 } else
132 kfree(snod);
133 cnt = 6;
134 } else if (--cnt == 0)
135 break;
136 }
137 return 0;
138}
139
140/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300141 * move_nodes - move nodes.
142 * @c: UBIFS file-system description object
143 * @sleb: describes nodes to move
144 *
145 * This function moves valid nodes from data LEB described by @sleb to the GC
146 * journal head. The obsolete nodes are dropped.
147 *
148 * When moving nodes we have to deal with classical bin-packing problem: the
149 * space in the current GC journal head LEB and in @c->gc_lnum are the "bins",
150 * where the nodes in the @sleb->nodes list are the elements which should be
151 * fit optimally to the bins. This function uses the "first fit decreasing"
152 * strategy, although it does not really sort the nodes but just split them on
153 * 3 classes - large, medium, and small, so they are roughly sorted.
154 *
155 * This function returns zero in case of success, %-EAGAIN if commit is
156 * required, and other negative error codes in case of other failures.
157 */
158static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
159{
160 struct ubifs_scan_node *snod, *tmp;
Adrian Hunter46773be2008-09-11 12:57:49 +0300161 struct list_head data, large, medium, small;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300162 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
163 int avail, err, min = INT_MAX;
Adrian Hunter46773be2008-09-11 12:57:49 +0300164 unsigned int blk = 0;
165 ino_t inum = 0;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300166
Adrian Hunter46773be2008-09-11 12:57:49 +0300167 INIT_LIST_HEAD(&data);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300168 INIT_LIST_HEAD(&large);
169 INIT_LIST_HEAD(&medium);
170 INIT_LIST_HEAD(&small);
171
Adrian Hunter46773be2008-09-11 12:57:49 +0300172 while (!list_empty(&sleb->nodes)) {
173 struct list_head *lst = sleb->nodes.next;
174
175 snod = list_entry(lst, struct ubifs_scan_node, list);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300176
177 ubifs_assert(snod->type != UBIFS_IDX_NODE);
178 ubifs_assert(snod->type != UBIFS_REF_NODE);
179 ubifs_assert(snod->type != UBIFS_CS_NODE);
180
181 err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
182 snod->offs, 0);
183 if (err < 0)
184 goto out;
185
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300186 list_del(lst);
187 if (!err) {
188 /* The node is obsolete, remove it from the list */
189 kfree(snod);
190 continue;
191 }
192
193 /*
Adrian Hunter46773be2008-09-11 12:57:49 +0300194 * Sort the list of nodes so that data nodes go first, large
195 * nodes go second, and small nodes go last.
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300196 */
Adrian Hunter46773be2008-09-11 12:57:49 +0300197 if (key_type(c, &snod->key) == UBIFS_DATA_KEY) {
198 if (inum != key_inum(c, &snod->key)) {
199 if (inum) {
200 /*
201 * Try to move data nodes from the same
202 * inode together.
203 */
204 err = joinup(c, sleb, inum, blk, &data);
205 if (err)
206 goto out;
207 }
208 inum = key_inum(c, &snod->key);
209 blk = key_block(c, &snod->key);
210 }
211 list_add_tail(lst, &data);
212 } else if (snod->len > MEDIUM_NODE_WM)
213 list_add_tail(lst, &large);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300214 else if (snod->len > SMALL_NODE_WM)
Adrian Hunter46773be2008-09-11 12:57:49 +0300215 list_add_tail(lst, &medium);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300216 else
Adrian Hunter46773be2008-09-11 12:57:49 +0300217 list_add_tail(lst, &small);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300218
219 /* And find the smallest node */
220 if (snod->len < min)
221 min = snod->len;
222 }
223
224 /*
225 * Join the tree lists so that we'd have one roughly sorted list
226 * ('large' will be the head of the joined list).
227 */
Adrian Hunter46773be2008-09-11 12:57:49 +0300228 list_splice(&data, &large);
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300229 list_splice(&medium, large.prev);
230 list_splice(&small, large.prev);
231
232 if (wbuf->lnum == -1) {
233 /*
234 * The GC journal head is not set, because it is the first GC
235 * invocation since mount.
236 */
237 err = switch_gc_head(c);
238 if (err)
239 goto out;
240 }
241
242 /* Write nodes to their new location. Use the first-fit strategy */
243 while (1) {
244 avail = c->leb_size - wbuf->offs - wbuf->used;
245 list_for_each_entry_safe(snod, tmp, &large, list) {
246 int new_lnum, new_offs;
247
248 if (avail < min)
249 break;
250
251 if (snod->len > avail)
252 /* This node does not fit */
253 continue;
254
255 cond_resched();
256
257 new_lnum = wbuf->lnum;
258 new_offs = wbuf->offs + wbuf->used;
259 err = ubifs_wbuf_write_nolock(wbuf, snod->node,
260 snod->len);
261 if (err)
262 goto out;
263 err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
264 snod->offs, new_lnum, new_offs,
265 snod->len);
266 if (err)
267 goto out;
268
269 avail = c->leb_size - wbuf->offs - wbuf->used;
270 list_del(&snod->list);
271 kfree(snod);
272 }
273
274 if (list_empty(&large))
275 break;
276
277 /*
278 * Waste the rest of the space in the LEB and switch to the
279 * next LEB.
280 */
281 err = switch_gc_head(c);
282 if (err)
283 goto out;
284 }
285
286 return 0;
287
288out:
289 list_for_each_entry_safe(snod, tmp, &large, list) {
290 list_del(&snod->list);
291 kfree(snod);
292 }
293 return err;
294}
295
296/**
297 * gc_sync_wbufs - sync write-buffers for GC.
298 * @c: UBIFS file-system description object
299 *
300 * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
301 * be in a write-buffer instead. That is, a node could be written to a
302 * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
303 * erased before the write-buffer is sync'd and then there is an unclean
304 * unmount, then an existing node is lost. To avoid this, we sync all
305 * write-buffers.
306 *
307 * This function returns %0 on success or a negative error code on failure.
308 */
309static int gc_sync_wbufs(struct ubifs_info *c)
310{
311 int err, i;
312
313 for (i = 0; i < c->jhead_cnt; i++) {
314 if (i == GCHD)
315 continue;
316 err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
317 if (err)
318 return err;
319 }
320 return 0;
321}
322
323/**
324 * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
325 * @c: UBIFS file-system description object
326 * @lp: describes the LEB to garbage collect
327 *
328 * This function garbage-collects an LEB and returns one of the @LEB_FREED,
329 * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
330 * required, and other negative error codes in case of failures.
331 */
332int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
333{
334 struct ubifs_scan_leb *sleb;
335 struct ubifs_scan_node *snod;
336 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
337 int err = 0, lnum = lp->lnum;
338
339 ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
340 c->need_recovery);
341 ubifs_assert(c->gc_lnum != lnum);
342 ubifs_assert(wbuf->lnum != lnum);
343
344 /*
345 * We scan the entire LEB even though we only really need to scan up to
346 * (c->leb_size - lp->free).
347 */
348 sleb = ubifs_scan(c, lnum, 0, c->sbuf);
349 if (IS_ERR(sleb))
350 return PTR_ERR(sleb);
351
352 ubifs_assert(!list_empty(&sleb->nodes));
353 snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
354
355 if (snod->type == UBIFS_IDX_NODE) {
356 struct ubifs_gced_idx_leb *idx_gc;
357
358 dbg_gc("indexing LEB %d (free %d, dirty %d)",
359 lnum, lp->free, lp->dirty);
360 list_for_each_entry(snod, &sleb->nodes, list) {
361 struct ubifs_idx_node *idx = snod->node;
362 int level = le16_to_cpu(idx->level);
363
364 ubifs_assert(snod->type == UBIFS_IDX_NODE);
365 key_read(c, ubifs_idx_key(c, idx), &snod->key);
366 err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
367 snod->offs);
368 if (err)
369 goto out;
370 }
371
372 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
373 if (!idx_gc) {
374 err = -ENOMEM;
375 goto out;
376 }
377
378 idx_gc->lnum = lnum;
379 idx_gc->unmap = 0;
380 list_add(&idx_gc->list, &c->idx_gc);
381
382 /*
383 * Don't release the LEB until after the next commit, because
384 * it may contain date which is needed for recovery. So
385 * although we freed this LEB, it will become usable only after
386 * the commit.
387 */
388 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
389 LPROPS_INDEX, 1);
390 if (err)
391 goto out;
392 err = LEB_FREED_IDX;
393 } else {
394 dbg_gc("data LEB %d (free %d, dirty %d)",
395 lnum, lp->free, lp->dirty);
396
397 err = move_nodes(c, sleb);
398 if (err)
Adrian Hunter6dcfac42008-09-12 12:27:47 +0300399 goto out_inc_seq;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300400
401 err = gc_sync_wbufs(c);
402 if (err)
Adrian Hunter6dcfac42008-09-12 12:27:47 +0300403 goto out_inc_seq;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300404
405 err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
406 if (err)
Adrian Hunter6dcfac42008-09-12 12:27:47 +0300407 goto out_inc_seq;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300408
Adrian Hunter601c0bc2008-08-22 14:23:35 +0300409 /* Allow for races with TNC */
410 c->gced_lnum = lnum;
411 smp_wmb();
412 c->gc_seq += 1;
413 smp_wmb();
414
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300415 if (c->gc_lnum == -1) {
416 c->gc_lnum = lnum;
417 err = LEB_RETAINED;
418 } else {
419 err = ubifs_wbuf_sync_nolock(wbuf);
420 if (err)
421 goto out;
422
423 err = ubifs_leb_unmap(c, lnum);
424 if (err)
425 goto out;
426
427 err = LEB_FREED;
428 }
429 }
430
431out:
432 ubifs_scan_destroy(sleb);
433 return err;
Adrian Hunter6dcfac42008-09-12 12:27:47 +0300434
435out_inc_seq:
436 /* We may have moved at least some nodes so allow for races with TNC */
437 c->gced_lnum = lnum;
438 smp_wmb();
439 c->gc_seq += 1;
440 smp_wmb();
441 goto out;
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300442}
443
444/**
445 * ubifs_garbage_collect - UBIFS garbage collector.
446 * @c: UBIFS file-system description object
447 * @anyway: do GC even if there are free LEBs
448 *
449 * This function does out-of-place garbage collection. The return codes are:
450 * o positive LEB number if the LEB has been freed and may be used;
451 * o %-EAGAIN if the caller has to run commit;
452 * o %-ENOSPC if GC failed to make any progress;
453 * o other negative error codes in case of other errors.
454 *
455 * Garbage collector writes data to the journal when GC'ing data LEBs, and just
456 * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
457 * commit may be required. But commit cannot be run from inside GC, because the
458 * caller might be holding the commit lock, so %-EAGAIN is returned instead;
459 * And this error code means that the caller has to run commit, and re-run GC
460 * if there is still no free space.
461 *
462 * There are many reasons why this function may return %-EAGAIN:
463 * o the log is full and there is no space to write an LEB reference for
464 * @c->gc_lnum;
465 * o the journal is too large and exceeds size limitations;
466 * o GC moved indexing LEBs, but they can be used only after the commit;
467 * o the shrinker fails to find clean znodes to free and requests the commit;
468 * o etc.
469 *
470 * Note, if the file-system is close to be full, this function may return
471 * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
472 * the function. E.g., this happens if the limits on the journal size are too
473 * tough and GC writes too much to the journal before an LEB is freed. This
474 * might also mean that the journal is too large, and the TNC becomes to big,
475 * so that the shrinker is constantly called, finds not clean znodes to free,
476 * and requests commit. Well, this may also happen if the journal is all right,
477 * but another kernel process consumes too much memory. Anyway, infinite
478 * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
479 */
480int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
481{
482 int i, err, ret, min_space = c->dead_wm;
483 struct ubifs_lprops lp;
484 struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
485
486 ubifs_assert_cmt_locked(c);
487
488 if (ubifs_gc_should_commit(c))
489 return -EAGAIN;
490
491 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
492
493 if (c->ro_media) {
494 ret = -EROFS;
495 goto out_unlock;
496 }
497
498 /* We expect the write-buffer to be empty on entry */
499 ubifs_assert(!wbuf->used);
500
501 for (i = 0; ; i++) {
502 int space_before = c->leb_size - wbuf->offs - wbuf->used;
503 int space_after;
504
505 cond_resched();
506
507 /* Give the commit an opportunity to run */
508 if (ubifs_gc_should_commit(c)) {
509 ret = -EAGAIN;
510 break;
511 }
512
513 if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
514 /*
515 * We've done enough iterations. Indexing LEBs were
516 * moved and will be available after the commit.
517 */
518 dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
519 ubifs_commit_required(c);
520 ret = -EAGAIN;
521 break;
522 }
523
524 if (i > HARD_LEBS_LIMIT) {
525 /*
526 * We've moved too many LEBs and have not made
527 * progress, give up.
528 */
529 dbg_gc("hard limit, -ENOSPC");
530 ret = -ENOSPC;
531 break;
532 }
533
534 /*
535 * Empty and freeable LEBs can turn up while we waited for
536 * the wbuf lock, or while we have been running GC. In that
537 * case, we should just return one of those instead of
538 * continuing to GC dirty LEBs. Hence we request
539 * 'ubifs_find_dirty_leb()' to return an empty LEB if it can.
540 */
541 ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
542 if (ret) {
543 if (ret == -ENOSPC)
544 dbg_gc("no more dirty LEBs");
545 break;
546 }
547
548 dbg_gc("found LEB %d: free %d, dirty %d, sum %d "
549 "(min. space %d)", lp.lnum, lp.free, lp.dirty,
550 lp.free + lp.dirty, min_space);
551
552 if (lp.free + lp.dirty == c->leb_size) {
553 /* An empty LEB was returned */
554 dbg_gc("LEB %d is free, return it", lp.lnum);
555 /*
556 * ubifs_find_dirty_leb() doesn't return freeable index
557 * LEBs.
558 */
559 ubifs_assert(!(lp.flags & LPROPS_INDEX));
560 if (lp.free != c->leb_size) {
561 /*
562 * Write buffers must be sync'd before
563 * unmapping freeable LEBs, because one of them
564 * may contain data which obsoletes something
565 * in 'lp.pnum'.
566 */
567 ret = gc_sync_wbufs(c);
568 if (ret)
569 goto out;
570 ret = ubifs_change_one_lp(c, lp.lnum,
571 c->leb_size, 0, 0, 0,
572 0);
573 if (ret)
574 goto out;
575 }
576 ret = ubifs_leb_unmap(c, lp.lnum);
577 if (ret)
578 goto out;
579 ret = lp.lnum;
580 break;
581 }
582
583 space_before = c->leb_size - wbuf->offs - wbuf->used;
584 if (wbuf->lnum == -1)
585 space_before = 0;
586
587 ret = ubifs_garbage_collect_leb(c, &lp);
588 if (ret < 0) {
589 if (ret == -EAGAIN || ret == -ENOSPC) {
590 /*
591 * These codes are not errors, so we have to
592 * return the LEB to lprops. But if the
593 * 'ubifs_return_leb()' function fails, its
594 * failure code is propagated to the caller
595 * instead of the original '-EAGAIN' or
596 * '-ENOSPC'.
597 */
598 err = ubifs_return_leb(c, lp.lnum);
599 if (err)
600 ret = err;
601 break;
602 }
603 goto out;
604 }
605
606 if (ret == LEB_FREED) {
607 /* An LEB has been freed and is ready for use */
608 dbg_gc("LEB %d freed, return", lp.lnum);
609 ret = lp.lnum;
610 break;
611 }
612
613 if (ret == LEB_FREED_IDX) {
614 /*
615 * This was an indexing LEB and it cannot be
616 * immediately used. And instead of requesting the
617 * commit straight away, we try to garbage collect some
618 * more.
619 */
620 dbg_gc("indexing LEB %d freed, continue", lp.lnum);
621 continue;
622 }
623
624 ubifs_assert(ret == LEB_RETAINED);
625 space_after = c->leb_size - wbuf->offs - wbuf->used;
626 dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
627 space_after - space_before);
628
629 if (space_after > space_before) {
630 /* GC makes progress, keep working */
631 min_space >>= 1;
632 if (min_space < c->dead_wm)
633 min_space = c->dead_wm;
634 continue;
635 }
636
637 dbg_gc("did not make progress");
638
639 /*
640 * GC moved an LEB bud have not done any progress. This means
641 * that the previous GC head LEB contained too few free space
642 * and the LEB which was GC'ed contained only large nodes which
643 * did not fit that space.
644 *
645 * We can do 2 things:
646 * 1. pick another LEB in a hope it'll contain a small node
647 * which will fit the space we have at the end of current GC
648 * head LEB, but there is no guarantee, so we try this out
649 * unless we have already been working for too long;
650 * 2. request an LEB with more dirty space, which will force
651 * 'ubifs_find_dirty_leb()' to start scanning the lprops
652 * table, instead of just picking one from the heap
653 * (previously it already picked the dirtiest LEB).
654 */
655 if (i < SOFT_LEBS_LIMIT) {
656 dbg_gc("try again");
657 continue;
658 }
659
660 min_space <<= 1;
661 if (min_space > c->dark_wm)
662 min_space = c->dark_wm;
663 dbg_gc("set min. space to %d", min_space);
664 }
665
666 if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
667 dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
668 ubifs_commit_required(c);
669 ret = -EAGAIN;
670 }
671
672 err = ubifs_wbuf_sync_nolock(wbuf);
673 if (!err)
674 err = ubifs_leb_unmap(c, c->gc_lnum);
675 if (err) {
676 ret = err;
677 goto out;
678 }
679out_unlock:
680 mutex_unlock(&wbuf->io_mutex);
681 return ret;
682
683out:
684 ubifs_assert(ret < 0);
685 ubifs_assert(ret != -ENOSPC && ret != -EAGAIN);
686 ubifs_ro_mode(c, ret);
687 ubifs_wbuf_sync_nolock(wbuf);
688 mutex_unlock(&wbuf->io_mutex);
689 ubifs_return_leb(c, lp.lnum);
690 return ret;
691}
692
693/**
694 * ubifs_gc_start_commit - garbage collection at start of commit.
695 * @c: UBIFS file-system description object
696 *
697 * If a LEB has only dirty and free space, then we may safely unmap it and make
698 * it free. Note, we cannot do this with indexing LEBs because dirty space may
699 * correspond index nodes that are required for recovery. In that case, the
700 * LEB cannot be unmapped until after the next commit.
701 *
702 * This function returns %0 upon success and a negative error code upon failure.
703 */
704int ubifs_gc_start_commit(struct ubifs_info *c)
705{
706 struct ubifs_gced_idx_leb *idx_gc;
707 const struct ubifs_lprops *lp;
708 int err = 0, flags;
709
710 ubifs_get_lprops(c);
711
712 /*
713 * Unmap (non-index) freeable LEBs. Note that recovery requires that all
714 * wbufs are sync'd before this, which is done in 'do_commit()'.
715 */
716 while (1) {
717 lp = ubifs_fast_find_freeable(c);
Hirofumi Nakagawa8d47aef2008-08-21 17:16:40 +0300718 if (IS_ERR(lp)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300719 err = PTR_ERR(lp);
720 goto out;
721 }
722 if (!lp)
723 break;
724 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
725 ubifs_assert(!(lp->flags & LPROPS_INDEX));
726 err = ubifs_leb_unmap(c, lp->lnum);
727 if (err)
728 goto out;
729 lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
Hirofumi Nakagawa8d47aef2008-08-21 17:16:40 +0300730 if (IS_ERR(lp)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300731 err = PTR_ERR(lp);
732 goto out;
733 }
734 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
735 ubifs_assert(!(lp->flags & LPROPS_INDEX));
736 }
737
738 /* Mark GC'd index LEBs OK to unmap after this commit finishes */
739 list_for_each_entry(idx_gc, &c->idx_gc, list)
740 idx_gc->unmap = 1;
741
742 /* Record index freeable LEBs for unmapping after commit */
743 while (1) {
744 lp = ubifs_fast_find_frdi_idx(c);
Hirofumi Nakagawa8d47aef2008-08-21 17:16:40 +0300745 if (IS_ERR(lp)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300746 err = PTR_ERR(lp);
747 goto out;
748 }
749 if (!lp)
750 break;
751 idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
752 if (!idx_gc) {
753 err = -ENOMEM;
754 goto out;
755 }
756 ubifs_assert(!(lp->flags & LPROPS_TAKEN));
757 ubifs_assert(lp->flags & LPROPS_INDEX);
758 /* Don't release the LEB until after the next commit */
759 flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
760 lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
Hirofumi Nakagawa8d47aef2008-08-21 17:16:40 +0300761 if (IS_ERR(lp)) {
Artem Bityutskiy1e517642008-07-14 19:08:37 +0300762 err = PTR_ERR(lp);
763 kfree(idx_gc);
764 goto out;
765 }
766 ubifs_assert(lp->flags & LPROPS_TAKEN);
767 ubifs_assert(!(lp->flags & LPROPS_INDEX));
768 idx_gc->lnum = lp->lnum;
769 idx_gc->unmap = 1;
770 list_add(&idx_gc->list, &c->idx_gc);
771 }
772out:
773 ubifs_release_lprops(c);
774 return err;
775}
776
777/**
778 * ubifs_gc_end_commit - garbage collection at end of commit.
779 * @c: UBIFS file-system description object
780 *
781 * This function completes out-of-place garbage collection of index LEBs.
782 */
783int ubifs_gc_end_commit(struct ubifs_info *c)
784{
785 struct ubifs_gced_idx_leb *idx_gc, *tmp;
786 struct ubifs_wbuf *wbuf;
787 int err = 0;
788
789 wbuf = &c->jheads[GCHD].wbuf;
790 mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
791 list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
792 if (idx_gc->unmap) {
793 dbg_gc("LEB %d", idx_gc->lnum);
794 err = ubifs_leb_unmap(c, idx_gc->lnum);
795 if (err)
796 goto out;
797 err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
798 LPROPS_NC, 0, LPROPS_TAKEN, -1);
799 if (err)
800 goto out;
801 list_del(&idx_gc->list);
802 kfree(idx_gc);
803 }
804out:
805 mutex_unlock(&wbuf->io_mutex);
806 return err;
807}
808
809/**
810 * ubifs_destroy_idx_gc - destroy idx_gc list.
811 * @c: UBIFS file-system description object
812 *
813 * This function destroys the idx_gc list. It is called when unmounting or
814 * remounting read-only so locks are not needed.
815 */
816void ubifs_destroy_idx_gc(struct ubifs_info *c)
817{
818 while (!list_empty(&c->idx_gc)) {
819 struct ubifs_gced_idx_leb *idx_gc;
820
821 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
822 list);
823 c->idx_gc_cnt -= 1;
824 list_del(&idx_gc->list);
825 kfree(idx_gc);
826 }
827
828}
829
830/**
831 * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
832 * @c: UBIFS file-system description object
833 *
834 * Called during start commit so locks are not needed.
835 */
836int ubifs_get_idx_gc_leb(struct ubifs_info *c)
837{
838 struct ubifs_gced_idx_leb *idx_gc;
839 int lnum;
840
841 if (list_empty(&c->idx_gc))
842 return -ENOSPC;
843 idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
844 lnum = idx_gc->lnum;
845 /* c->idx_gc_cnt is updated by the caller when lprops are updated */
846 list_del(&idx_gc->list);
847 kfree(idx_gc);
848 return lnum;
849}