1*83d290c5STom Rini // SPDX-License-Identifier: GPL-2.0
2040cc7b3SAnton Habegger /*
3040cc7b3SAnton Habegger * This file is part of UBIFS.
4040cc7b3SAnton Habegger *
5040cc7b3SAnton Habegger * Copyright (C) 2006-2008 Nokia Corporation.
6040cc7b3SAnton Habegger *
7040cc7b3SAnton Habegger * Authors: Adrian Hunter
8040cc7b3SAnton Habegger * Artem Bityutskiy (Битюцкий Артём)
9040cc7b3SAnton Habegger */
10040cc7b3SAnton Habegger
11040cc7b3SAnton Habegger /*
12040cc7b3SAnton Habegger * This file implements garbage collection. The procedure for garbage collection
13040cc7b3SAnton Habegger * is different depending on whether a LEB as an index LEB (contains index
14040cc7b3SAnton Habegger * nodes) or not. For non-index LEBs, garbage collection finds a LEB which
15040cc7b3SAnton Habegger * contains a lot of dirty space (obsolete nodes), and copies the non-obsolete
16040cc7b3SAnton Habegger * nodes to the journal, at which point the garbage-collected LEB is free to be
17040cc7b3SAnton Habegger * reused. For index LEBs, garbage collection marks the non-obsolete index nodes
18040cc7b3SAnton Habegger * dirty in the TNC, and after the next commit, the garbage-collected LEB is
19040cc7b3SAnton Habegger * to be reused. Garbage collection will cause the number of dirty index nodes
20040cc7b3SAnton Habegger * to grow, however sufficient space is reserved for the index to ensure the
21040cc7b3SAnton Habegger * commit will never run out of space.
22040cc7b3SAnton Habegger *
23040cc7b3SAnton Habegger * Notes about dead watermark. At current UBIFS implementation we assume that
24040cc7b3SAnton Habegger * LEBs which have less than @c->dead_wm bytes of free + dirty space are full
25040cc7b3SAnton Habegger * and not worth garbage-collecting. The dead watermark is one min. I/O unit
26040cc7b3SAnton Habegger * size, or min. UBIFS node size, depending on what is greater. Indeed, UBIFS
27040cc7b3SAnton Habegger * Garbage Collector has to synchronize the GC head's write buffer before
28040cc7b3SAnton Habegger * returning, so this is about wasting one min. I/O unit. However, UBIFS GC can
29040cc7b3SAnton Habegger * actually reclaim even very small pieces of dirty space by garbage collecting
30040cc7b3SAnton Habegger * enough dirty LEBs, but we do not bother doing this at this implementation.
31040cc7b3SAnton Habegger *
32040cc7b3SAnton Habegger * Notes about dark watermark. The results of GC work depends on how big are
33040cc7b3SAnton Habegger * the UBIFS nodes GC deals with. Large nodes make GC waste more space. Indeed,
34040cc7b3SAnton Habegger * if GC move data from LEB A to LEB B and nodes in LEB A are large, GC would
35040cc7b3SAnton Habegger * have to waste large pieces of free space at the end of LEB B, because nodes
36040cc7b3SAnton Habegger * from LEB A would not fit. And the worst situation is when all nodes are of
37040cc7b3SAnton Habegger * maximum size. So dark watermark is the amount of free + dirty space in LEB
38040cc7b3SAnton Habegger * which are guaranteed to be reclaimable. If LEB has less space, the GC might
39040cc7b3SAnton Habegger * be unable to reclaim it. So, LEBs with free + dirty greater than dark
40040cc7b3SAnton Habegger * watermark are "good" LEBs from GC's point of few. The other LEBs are not so
41040cc7b3SAnton Habegger * good, and GC takes extra care when moving them.
42040cc7b3SAnton Habegger */
43040cc7b3SAnton Habegger #ifndef __UBOOT__
44040cc7b3SAnton Habegger #include <linux/slab.h>
45040cc7b3SAnton Habegger #include <linux/pagemap.h>
46040cc7b3SAnton Habegger #include <linux/list_sort.h>
47040cc7b3SAnton Habegger #endif
48040cc7b3SAnton Habegger #include "ubifs.h"
49040cc7b3SAnton Habegger
50040cc7b3SAnton Habegger #ifndef __UBOOT__
51040cc7b3SAnton Habegger /*
52040cc7b3SAnton Habegger * GC may need to move more than one LEB to make progress. The below constants
53040cc7b3SAnton Habegger * define "soft" and "hard" limits on the number of LEBs the garbage collector
54040cc7b3SAnton Habegger * may move.
55040cc7b3SAnton Habegger */
56040cc7b3SAnton Habegger #define SOFT_LEBS_LIMIT 4
57040cc7b3SAnton Habegger #define HARD_LEBS_LIMIT 32
58040cc7b3SAnton Habegger
59040cc7b3SAnton Habegger /**
60040cc7b3SAnton Habegger * switch_gc_head - switch the garbage collection journal head.
61040cc7b3SAnton Habegger * @c: UBIFS file-system description object
62040cc7b3SAnton Habegger * @buf: buffer to write
63040cc7b3SAnton Habegger * @len: length of the buffer to write
64040cc7b3SAnton Habegger * @lnum: LEB number written is returned here
65040cc7b3SAnton Habegger * @offs: offset written is returned here
66040cc7b3SAnton Habegger *
67040cc7b3SAnton Habegger * This function switch the GC head to the next LEB which is reserved in
68040cc7b3SAnton Habegger * @c->gc_lnum. Returns %0 in case of success, %-EAGAIN if commit is required,
69040cc7b3SAnton Habegger * and other negative error code in case of failures.
70040cc7b3SAnton Habegger */
switch_gc_head(struct ubifs_info * c)71040cc7b3SAnton Habegger static int switch_gc_head(struct ubifs_info *c)
72040cc7b3SAnton Habegger {
73040cc7b3SAnton Habegger int err, gc_lnum = c->gc_lnum;
74040cc7b3SAnton Habegger struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
75040cc7b3SAnton Habegger
76040cc7b3SAnton Habegger ubifs_assert(gc_lnum != -1);
77040cc7b3SAnton Habegger dbg_gc("switch GC head from LEB %d:%d to LEB %d (waste %d bytes)",
78040cc7b3SAnton Habegger wbuf->lnum, wbuf->offs + wbuf->used, gc_lnum,
79040cc7b3SAnton Habegger c->leb_size - wbuf->offs - wbuf->used);
80040cc7b3SAnton Habegger
81040cc7b3SAnton Habegger err = ubifs_wbuf_sync_nolock(wbuf);
82040cc7b3SAnton Habegger if (err)
83040cc7b3SAnton Habegger return err;
84040cc7b3SAnton Habegger
85040cc7b3SAnton Habegger /*
86040cc7b3SAnton Habegger * The GC write-buffer was synchronized, we may safely unmap
87040cc7b3SAnton Habegger * 'c->gc_lnum'.
88040cc7b3SAnton Habegger */
89040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, gc_lnum);
90040cc7b3SAnton Habegger if (err)
91040cc7b3SAnton Habegger return err;
92040cc7b3SAnton Habegger
93040cc7b3SAnton Habegger err = ubifs_wbuf_sync_nolock(wbuf);
94040cc7b3SAnton Habegger if (err)
95040cc7b3SAnton Habegger return err;
96040cc7b3SAnton Habegger
97040cc7b3SAnton Habegger err = ubifs_add_bud_to_log(c, GCHD, gc_lnum, 0);
98040cc7b3SAnton Habegger if (err)
99040cc7b3SAnton Habegger return err;
100040cc7b3SAnton Habegger
101040cc7b3SAnton Habegger c->gc_lnum = -1;
102040cc7b3SAnton Habegger err = ubifs_wbuf_seek_nolock(wbuf, gc_lnum, 0);
103040cc7b3SAnton Habegger return err;
104040cc7b3SAnton Habegger }
105040cc7b3SAnton Habegger
106040cc7b3SAnton Habegger /**
107040cc7b3SAnton Habegger * data_nodes_cmp - compare 2 data nodes.
108040cc7b3SAnton Habegger * @priv: UBIFS file-system description object
109040cc7b3SAnton Habegger * @a: first data node
110040cc7b3SAnton Habegger * @a: second data node
111040cc7b3SAnton Habegger *
112040cc7b3SAnton Habegger * This function compares data nodes @a and @b. Returns %1 if @a has greater
113040cc7b3SAnton Habegger * inode or block number, and %-1 otherwise.
114040cc7b3SAnton Habegger */
data_nodes_cmp(void * priv,struct list_head * a,struct list_head * b)115040cc7b3SAnton Habegger static int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
116040cc7b3SAnton Habegger {
117040cc7b3SAnton Habegger ino_t inuma, inumb;
118040cc7b3SAnton Habegger struct ubifs_info *c = priv;
119040cc7b3SAnton Habegger struct ubifs_scan_node *sa, *sb;
120040cc7b3SAnton Habegger
121040cc7b3SAnton Habegger cond_resched();
122040cc7b3SAnton Habegger if (a == b)
123040cc7b3SAnton Habegger return 0;
124040cc7b3SAnton Habegger
125040cc7b3SAnton Habegger sa = list_entry(a, struct ubifs_scan_node, list);
126040cc7b3SAnton Habegger sb = list_entry(b, struct ubifs_scan_node, list);
127040cc7b3SAnton Habegger
128040cc7b3SAnton Habegger ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
129040cc7b3SAnton Habegger ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY);
130040cc7b3SAnton Habegger ubifs_assert(sa->type == UBIFS_DATA_NODE);
131040cc7b3SAnton Habegger ubifs_assert(sb->type == UBIFS_DATA_NODE);
132040cc7b3SAnton Habegger
133040cc7b3SAnton Habegger inuma = key_inum(c, &sa->key);
134040cc7b3SAnton Habegger inumb = key_inum(c, &sb->key);
135040cc7b3SAnton Habegger
136040cc7b3SAnton Habegger if (inuma == inumb) {
137040cc7b3SAnton Habegger unsigned int blka = key_block(c, &sa->key);
138040cc7b3SAnton Habegger unsigned int blkb = key_block(c, &sb->key);
139040cc7b3SAnton Habegger
140040cc7b3SAnton Habegger if (blka <= blkb)
141040cc7b3SAnton Habegger return -1;
142040cc7b3SAnton Habegger } else if (inuma <= inumb)
143040cc7b3SAnton Habegger return -1;
144040cc7b3SAnton Habegger
145040cc7b3SAnton Habegger return 1;
146040cc7b3SAnton Habegger }
147040cc7b3SAnton Habegger
148040cc7b3SAnton Habegger /*
149040cc7b3SAnton Habegger * nondata_nodes_cmp - compare 2 non-data nodes.
150040cc7b3SAnton Habegger * @priv: UBIFS file-system description object
151040cc7b3SAnton Habegger * @a: first node
152040cc7b3SAnton Habegger * @a: second node
153040cc7b3SAnton Habegger *
154040cc7b3SAnton Habegger * This function compares nodes @a and @b. It makes sure that inode nodes go
155040cc7b3SAnton Habegger * first and sorted by length in descending order. Directory entry nodes go
156040cc7b3SAnton Habegger * after inode nodes and are sorted in ascending hash valuer order.
157040cc7b3SAnton Habegger */
nondata_nodes_cmp(void * priv,struct list_head * a,struct list_head * b)158040cc7b3SAnton Habegger static int nondata_nodes_cmp(void *priv, struct list_head *a,
159040cc7b3SAnton Habegger struct list_head *b)
160040cc7b3SAnton Habegger {
161040cc7b3SAnton Habegger ino_t inuma, inumb;
162040cc7b3SAnton Habegger struct ubifs_info *c = priv;
163040cc7b3SAnton Habegger struct ubifs_scan_node *sa, *sb;
164040cc7b3SAnton Habegger
165040cc7b3SAnton Habegger cond_resched();
166040cc7b3SAnton Habegger if (a == b)
167040cc7b3SAnton Habegger return 0;
168040cc7b3SAnton Habegger
169040cc7b3SAnton Habegger sa = list_entry(a, struct ubifs_scan_node, list);
170040cc7b3SAnton Habegger sb = list_entry(b, struct ubifs_scan_node, list);
171040cc7b3SAnton Habegger
172040cc7b3SAnton Habegger ubifs_assert(key_type(c, &sa->key) != UBIFS_DATA_KEY &&
173040cc7b3SAnton Habegger key_type(c, &sb->key) != UBIFS_DATA_KEY);
174040cc7b3SAnton Habegger ubifs_assert(sa->type != UBIFS_DATA_NODE &&
175040cc7b3SAnton Habegger sb->type != UBIFS_DATA_NODE);
176040cc7b3SAnton Habegger
177040cc7b3SAnton Habegger /* Inodes go before directory entries */
178040cc7b3SAnton Habegger if (sa->type == UBIFS_INO_NODE) {
179040cc7b3SAnton Habegger if (sb->type == UBIFS_INO_NODE)
180040cc7b3SAnton Habegger return sb->len - sa->len;
181040cc7b3SAnton Habegger return -1;
182040cc7b3SAnton Habegger }
183040cc7b3SAnton Habegger if (sb->type == UBIFS_INO_NODE)
184040cc7b3SAnton Habegger return 1;
185040cc7b3SAnton Habegger
186040cc7b3SAnton Habegger ubifs_assert(key_type(c, &sa->key) == UBIFS_DENT_KEY ||
187040cc7b3SAnton Habegger key_type(c, &sa->key) == UBIFS_XENT_KEY);
188040cc7b3SAnton Habegger ubifs_assert(key_type(c, &sb->key) == UBIFS_DENT_KEY ||
189040cc7b3SAnton Habegger key_type(c, &sb->key) == UBIFS_XENT_KEY);
190040cc7b3SAnton Habegger ubifs_assert(sa->type == UBIFS_DENT_NODE ||
191040cc7b3SAnton Habegger sa->type == UBIFS_XENT_NODE);
192040cc7b3SAnton Habegger ubifs_assert(sb->type == UBIFS_DENT_NODE ||
193040cc7b3SAnton Habegger sb->type == UBIFS_XENT_NODE);
194040cc7b3SAnton Habegger
195040cc7b3SAnton Habegger inuma = key_inum(c, &sa->key);
196040cc7b3SAnton Habegger inumb = key_inum(c, &sb->key);
197040cc7b3SAnton Habegger
198040cc7b3SAnton Habegger if (inuma == inumb) {
199040cc7b3SAnton Habegger uint32_t hasha = key_hash(c, &sa->key);
200040cc7b3SAnton Habegger uint32_t hashb = key_hash(c, &sb->key);
201040cc7b3SAnton Habegger
202040cc7b3SAnton Habegger if (hasha <= hashb)
203040cc7b3SAnton Habegger return -1;
204040cc7b3SAnton Habegger } else if (inuma <= inumb)
205040cc7b3SAnton Habegger return -1;
206040cc7b3SAnton Habegger
207040cc7b3SAnton Habegger return 1;
208040cc7b3SAnton Habegger }
209040cc7b3SAnton Habegger
210040cc7b3SAnton Habegger /**
211040cc7b3SAnton Habegger * sort_nodes - sort nodes for GC.
212040cc7b3SAnton Habegger * @c: UBIFS file-system description object
213040cc7b3SAnton Habegger * @sleb: describes nodes to sort and contains the result on exit
214040cc7b3SAnton Habegger * @nondata: contains non-data nodes on exit
215040cc7b3SAnton Habegger * @min: minimum node size is returned here
216040cc7b3SAnton Habegger *
217040cc7b3SAnton Habegger * This function sorts the list of inodes to garbage collect. First of all, it
218040cc7b3SAnton Habegger * kills obsolete nodes and separates data and non-data nodes to the
219040cc7b3SAnton Habegger * @sleb->nodes and @nondata lists correspondingly.
220040cc7b3SAnton Habegger *
221040cc7b3SAnton Habegger * Data nodes are then sorted in block number order - this is important for
222040cc7b3SAnton Habegger * bulk-read; data nodes with lower inode number go before data nodes with
223040cc7b3SAnton Habegger * higher inode number, and data nodes with lower block number go before data
224040cc7b3SAnton Habegger * nodes with higher block number;
225040cc7b3SAnton Habegger *
226040cc7b3SAnton Habegger * Non-data nodes are sorted as follows.
227040cc7b3SAnton Habegger * o First go inode nodes - they are sorted in descending length order.
228040cc7b3SAnton Habegger * o Then go directory entry nodes - they are sorted in hash order, which
229040cc7b3SAnton Habegger * should supposedly optimize 'readdir()'. Direntry nodes with lower parent
230040cc7b3SAnton Habegger * inode number go before direntry nodes with higher parent inode number,
231040cc7b3SAnton Habegger * and direntry nodes with lower name hash values go before direntry nodes
232040cc7b3SAnton Habegger * with higher name hash values.
233040cc7b3SAnton Habegger *
234040cc7b3SAnton Habegger * This function returns zero in case of success and a negative error code in
235040cc7b3SAnton Habegger * case of failure.
236040cc7b3SAnton Habegger */
sort_nodes(struct ubifs_info * c,struct ubifs_scan_leb * sleb,struct list_head * nondata,int * min)237040cc7b3SAnton Habegger static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
238040cc7b3SAnton Habegger struct list_head *nondata, int *min)
239040cc7b3SAnton Habegger {
240040cc7b3SAnton Habegger int err;
241040cc7b3SAnton Habegger struct ubifs_scan_node *snod, *tmp;
242040cc7b3SAnton Habegger
243040cc7b3SAnton Habegger *min = INT_MAX;
244040cc7b3SAnton Habegger
245040cc7b3SAnton Habegger /* Separate data nodes and non-data nodes */
246040cc7b3SAnton Habegger list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
247040cc7b3SAnton Habegger ubifs_assert(snod->type == UBIFS_INO_NODE ||
248040cc7b3SAnton Habegger snod->type == UBIFS_DATA_NODE ||
249040cc7b3SAnton Habegger snod->type == UBIFS_DENT_NODE ||
250040cc7b3SAnton Habegger snod->type == UBIFS_XENT_NODE ||
251040cc7b3SAnton Habegger snod->type == UBIFS_TRUN_NODE);
252040cc7b3SAnton Habegger
253040cc7b3SAnton Habegger if (snod->type != UBIFS_INO_NODE &&
254040cc7b3SAnton Habegger snod->type != UBIFS_DATA_NODE &&
255040cc7b3SAnton Habegger snod->type != UBIFS_DENT_NODE &&
256040cc7b3SAnton Habegger snod->type != UBIFS_XENT_NODE) {
257040cc7b3SAnton Habegger /* Probably truncation node, zap it */
258040cc7b3SAnton Habegger list_del(&snod->list);
259040cc7b3SAnton Habegger kfree(snod);
260040cc7b3SAnton Habegger continue;
261040cc7b3SAnton Habegger }
262040cc7b3SAnton Habegger
263040cc7b3SAnton Habegger ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY ||
264040cc7b3SAnton Habegger key_type(c, &snod->key) == UBIFS_INO_KEY ||
265040cc7b3SAnton Habegger key_type(c, &snod->key) == UBIFS_DENT_KEY ||
266040cc7b3SAnton Habegger key_type(c, &snod->key) == UBIFS_XENT_KEY);
267040cc7b3SAnton Habegger
268040cc7b3SAnton Habegger err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
269040cc7b3SAnton Habegger snod->offs, 0);
270040cc7b3SAnton Habegger if (err < 0)
271040cc7b3SAnton Habegger return err;
272040cc7b3SAnton Habegger
273040cc7b3SAnton Habegger if (!err) {
274040cc7b3SAnton Habegger /* The node is obsolete, remove it from the list */
275040cc7b3SAnton Habegger list_del(&snod->list);
276040cc7b3SAnton Habegger kfree(snod);
277040cc7b3SAnton Habegger continue;
278040cc7b3SAnton Habegger }
279040cc7b3SAnton Habegger
280040cc7b3SAnton Habegger if (snod->len < *min)
281040cc7b3SAnton Habegger *min = snod->len;
282040cc7b3SAnton Habegger
283040cc7b3SAnton Habegger if (key_type(c, &snod->key) != UBIFS_DATA_KEY)
284040cc7b3SAnton Habegger list_move_tail(&snod->list, nondata);
285040cc7b3SAnton Habegger }
286040cc7b3SAnton Habegger
287040cc7b3SAnton Habegger /* Sort data and non-data nodes */
288040cc7b3SAnton Habegger list_sort(c, &sleb->nodes, &data_nodes_cmp);
289040cc7b3SAnton Habegger list_sort(c, nondata, &nondata_nodes_cmp);
290040cc7b3SAnton Habegger
291040cc7b3SAnton Habegger err = dbg_check_data_nodes_order(c, &sleb->nodes);
292040cc7b3SAnton Habegger if (err)
293040cc7b3SAnton Habegger return err;
294040cc7b3SAnton Habegger err = dbg_check_nondata_nodes_order(c, nondata);
295040cc7b3SAnton Habegger if (err)
296040cc7b3SAnton Habegger return err;
297040cc7b3SAnton Habegger return 0;
298040cc7b3SAnton Habegger }
299040cc7b3SAnton Habegger
300040cc7b3SAnton Habegger /**
301040cc7b3SAnton Habegger * move_node - move a node.
302040cc7b3SAnton Habegger * @c: UBIFS file-system description object
303040cc7b3SAnton Habegger * @sleb: describes the LEB to move nodes from
304040cc7b3SAnton Habegger * @snod: the mode to move
305040cc7b3SAnton Habegger * @wbuf: write-buffer to move node to
306040cc7b3SAnton Habegger *
307040cc7b3SAnton Habegger * This function moves node @snod to @wbuf, changes TNC correspondingly, and
308040cc7b3SAnton Habegger * destroys @snod. Returns zero in case of success and a negative error code in
309040cc7b3SAnton Habegger * case of failure.
310040cc7b3SAnton Habegger */
move_node(struct ubifs_info * c,struct ubifs_scan_leb * sleb,struct ubifs_scan_node * snod,struct ubifs_wbuf * wbuf)311040cc7b3SAnton Habegger static int move_node(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
312040cc7b3SAnton Habegger struct ubifs_scan_node *snod, struct ubifs_wbuf *wbuf)
313040cc7b3SAnton Habegger {
314040cc7b3SAnton Habegger int err, new_lnum = wbuf->lnum, new_offs = wbuf->offs + wbuf->used;
315040cc7b3SAnton Habegger
316040cc7b3SAnton Habegger cond_resched();
317040cc7b3SAnton Habegger err = ubifs_wbuf_write_nolock(wbuf, snod->node, snod->len);
318040cc7b3SAnton Habegger if (err)
319040cc7b3SAnton Habegger return err;
320040cc7b3SAnton Habegger
321040cc7b3SAnton Habegger err = ubifs_tnc_replace(c, &snod->key, sleb->lnum,
322040cc7b3SAnton Habegger snod->offs, new_lnum, new_offs,
323040cc7b3SAnton Habegger snod->len);
324040cc7b3SAnton Habegger list_del(&snod->list);
325040cc7b3SAnton Habegger kfree(snod);
326040cc7b3SAnton Habegger return err;
327040cc7b3SAnton Habegger }
328040cc7b3SAnton Habegger
329040cc7b3SAnton Habegger /**
330040cc7b3SAnton Habegger * move_nodes - move nodes.
331040cc7b3SAnton Habegger * @c: UBIFS file-system description object
332040cc7b3SAnton Habegger * @sleb: describes the LEB to move nodes from
333040cc7b3SAnton Habegger *
334040cc7b3SAnton Habegger * This function moves valid nodes from data LEB described by @sleb to the GC
335040cc7b3SAnton Habegger * journal head. This function returns zero in case of success, %-EAGAIN if
336040cc7b3SAnton Habegger * commit is required, and other negative error codes in case of other
337040cc7b3SAnton Habegger * failures.
338040cc7b3SAnton Habegger */
move_nodes(struct ubifs_info * c,struct ubifs_scan_leb * sleb)339040cc7b3SAnton Habegger static int move_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb)
340040cc7b3SAnton Habegger {
341040cc7b3SAnton Habegger int err, min;
342040cc7b3SAnton Habegger LIST_HEAD(nondata);
343040cc7b3SAnton Habegger struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
344040cc7b3SAnton Habegger
345040cc7b3SAnton Habegger if (wbuf->lnum == -1) {
346040cc7b3SAnton Habegger /*
347040cc7b3SAnton Habegger * The GC journal head is not set, because it is the first GC
348040cc7b3SAnton Habegger * invocation since mount.
349040cc7b3SAnton Habegger */
350040cc7b3SAnton Habegger err = switch_gc_head(c);
351040cc7b3SAnton Habegger if (err)
352040cc7b3SAnton Habegger return err;
353040cc7b3SAnton Habegger }
354040cc7b3SAnton Habegger
355040cc7b3SAnton Habegger err = sort_nodes(c, sleb, &nondata, &min);
356040cc7b3SAnton Habegger if (err)
357040cc7b3SAnton Habegger goto out;
358040cc7b3SAnton Habegger
359040cc7b3SAnton Habegger /* Write nodes to their new location. Use the first-fit strategy */
360040cc7b3SAnton Habegger while (1) {
361040cc7b3SAnton Habegger int avail;
362040cc7b3SAnton Habegger struct ubifs_scan_node *snod, *tmp;
363040cc7b3SAnton Habegger
364040cc7b3SAnton Habegger /* Move data nodes */
365040cc7b3SAnton Habegger list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
366040cc7b3SAnton Habegger avail = c->leb_size - wbuf->offs - wbuf->used;
367040cc7b3SAnton Habegger if (snod->len > avail)
368040cc7b3SAnton Habegger /*
369040cc7b3SAnton Habegger * Do not skip data nodes in order to optimize
370040cc7b3SAnton Habegger * bulk-read.
371040cc7b3SAnton Habegger */
372040cc7b3SAnton Habegger break;
373040cc7b3SAnton Habegger
374040cc7b3SAnton Habegger err = move_node(c, sleb, snod, wbuf);
375040cc7b3SAnton Habegger if (err)
376040cc7b3SAnton Habegger goto out;
377040cc7b3SAnton Habegger }
378040cc7b3SAnton Habegger
379040cc7b3SAnton Habegger /* Move non-data nodes */
380040cc7b3SAnton Habegger list_for_each_entry_safe(snod, tmp, &nondata, list) {
381040cc7b3SAnton Habegger avail = c->leb_size - wbuf->offs - wbuf->used;
382040cc7b3SAnton Habegger if (avail < min)
383040cc7b3SAnton Habegger break;
384040cc7b3SAnton Habegger
385040cc7b3SAnton Habegger if (snod->len > avail) {
386040cc7b3SAnton Habegger /*
387040cc7b3SAnton Habegger * Keep going only if this is an inode with
388040cc7b3SAnton Habegger * some data. Otherwise stop and switch the GC
389040cc7b3SAnton Habegger * head. IOW, we assume that data-less inode
390040cc7b3SAnton Habegger * nodes and direntry nodes are roughly of the
391040cc7b3SAnton Habegger * same size.
392040cc7b3SAnton Habegger */
393040cc7b3SAnton Habegger if (key_type(c, &snod->key) == UBIFS_DENT_KEY ||
394040cc7b3SAnton Habegger snod->len == UBIFS_INO_NODE_SZ)
395040cc7b3SAnton Habegger break;
396040cc7b3SAnton Habegger continue;
397040cc7b3SAnton Habegger }
398040cc7b3SAnton Habegger
399040cc7b3SAnton Habegger err = move_node(c, sleb, snod, wbuf);
400040cc7b3SAnton Habegger if (err)
401040cc7b3SAnton Habegger goto out;
402040cc7b3SAnton Habegger }
403040cc7b3SAnton Habegger
404040cc7b3SAnton Habegger if (list_empty(&sleb->nodes) && list_empty(&nondata))
405040cc7b3SAnton Habegger break;
406040cc7b3SAnton Habegger
407040cc7b3SAnton Habegger /*
408040cc7b3SAnton Habegger * Waste the rest of the space in the LEB and switch to the
409040cc7b3SAnton Habegger * next LEB.
410040cc7b3SAnton Habegger */
411040cc7b3SAnton Habegger err = switch_gc_head(c);
412040cc7b3SAnton Habegger if (err)
413040cc7b3SAnton Habegger goto out;
414040cc7b3SAnton Habegger }
415040cc7b3SAnton Habegger
416040cc7b3SAnton Habegger return 0;
417040cc7b3SAnton Habegger
418040cc7b3SAnton Habegger out:
419040cc7b3SAnton Habegger list_splice_tail(&nondata, &sleb->nodes);
420040cc7b3SAnton Habegger return err;
421040cc7b3SAnton Habegger }
422040cc7b3SAnton Habegger
423040cc7b3SAnton Habegger /**
424040cc7b3SAnton Habegger * gc_sync_wbufs - sync write-buffers for GC.
425040cc7b3SAnton Habegger * @c: UBIFS file-system description object
426040cc7b3SAnton Habegger *
427040cc7b3SAnton Habegger * We must guarantee that obsoleting nodes are on flash. Unfortunately they may
428040cc7b3SAnton Habegger * be in a write-buffer instead. That is, a node could be written to a
429040cc7b3SAnton Habegger * write-buffer, obsoleting another node in a LEB that is GC'd. If that LEB is
430040cc7b3SAnton Habegger * erased before the write-buffer is sync'd and then there is an unclean
431040cc7b3SAnton Habegger * unmount, then an existing node is lost. To avoid this, we sync all
432040cc7b3SAnton Habegger * write-buffers.
433040cc7b3SAnton Habegger *
434040cc7b3SAnton Habegger * This function returns %0 on success or a negative error code on failure.
435040cc7b3SAnton Habegger */
gc_sync_wbufs(struct ubifs_info * c)436040cc7b3SAnton Habegger static int gc_sync_wbufs(struct ubifs_info *c)
437040cc7b3SAnton Habegger {
438040cc7b3SAnton Habegger int err, i;
439040cc7b3SAnton Habegger
440040cc7b3SAnton Habegger for (i = 0; i < c->jhead_cnt; i++) {
441040cc7b3SAnton Habegger if (i == GCHD)
442040cc7b3SAnton Habegger continue;
443040cc7b3SAnton Habegger err = ubifs_wbuf_sync(&c->jheads[i].wbuf);
444040cc7b3SAnton Habegger if (err)
445040cc7b3SAnton Habegger return err;
446040cc7b3SAnton Habegger }
447040cc7b3SAnton Habegger return 0;
448040cc7b3SAnton Habegger }
449040cc7b3SAnton Habegger
450040cc7b3SAnton Habegger /**
451040cc7b3SAnton Habegger * ubifs_garbage_collect_leb - garbage-collect a logical eraseblock.
452040cc7b3SAnton Habegger * @c: UBIFS file-system description object
453040cc7b3SAnton Habegger * @lp: describes the LEB to garbage collect
454040cc7b3SAnton Habegger *
455040cc7b3SAnton Habegger * This function garbage-collects an LEB and returns one of the @LEB_FREED,
456040cc7b3SAnton Habegger * @LEB_RETAINED, etc positive codes in case of success, %-EAGAIN if commit is
457040cc7b3SAnton Habegger * required, and other negative error codes in case of failures.
458040cc7b3SAnton Habegger */
ubifs_garbage_collect_leb(struct ubifs_info * c,struct ubifs_lprops * lp)459040cc7b3SAnton Habegger int ubifs_garbage_collect_leb(struct ubifs_info *c, struct ubifs_lprops *lp)
460040cc7b3SAnton Habegger {
461040cc7b3SAnton Habegger struct ubifs_scan_leb *sleb;
462040cc7b3SAnton Habegger struct ubifs_scan_node *snod;
463040cc7b3SAnton Habegger struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
464040cc7b3SAnton Habegger int err = 0, lnum = lp->lnum;
465040cc7b3SAnton Habegger
466040cc7b3SAnton Habegger ubifs_assert(c->gc_lnum != -1 || wbuf->offs + wbuf->used == 0 ||
467040cc7b3SAnton Habegger c->need_recovery);
468040cc7b3SAnton Habegger ubifs_assert(c->gc_lnum != lnum);
469040cc7b3SAnton Habegger ubifs_assert(wbuf->lnum != lnum);
470040cc7b3SAnton Habegger
471040cc7b3SAnton Habegger if (lp->free + lp->dirty == c->leb_size) {
472040cc7b3SAnton Habegger /* Special case - a free LEB */
473040cc7b3SAnton Habegger dbg_gc("LEB %d is free, return it", lp->lnum);
474040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_INDEX));
475040cc7b3SAnton Habegger
476040cc7b3SAnton Habegger if (lp->free != c->leb_size) {
477040cc7b3SAnton Habegger /*
478040cc7b3SAnton Habegger * Write buffers must be sync'd before unmapping
479040cc7b3SAnton Habegger * freeable LEBs, because one of them may contain data
480040cc7b3SAnton Habegger * which obsoletes something in 'lp->pnum'.
481040cc7b3SAnton Habegger */
482040cc7b3SAnton Habegger err = gc_sync_wbufs(c);
483040cc7b3SAnton Habegger if (err)
484040cc7b3SAnton Habegger return err;
485040cc7b3SAnton Habegger err = ubifs_change_one_lp(c, lp->lnum, c->leb_size,
486040cc7b3SAnton Habegger 0, 0, 0, 0);
487040cc7b3SAnton Habegger if (err)
488040cc7b3SAnton Habegger return err;
489040cc7b3SAnton Habegger }
490040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, lp->lnum);
491040cc7b3SAnton Habegger if (err)
492040cc7b3SAnton Habegger return err;
493040cc7b3SAnton Habegger
494040cc7b3SAnton Habegger if (c->gc_lnum == -1) {
495040cc7b3SAnton Habegger c->gc_lnum = lnum;
496040cc7b3SAnton Habegger return LEB_RETAINED;
497040cc7b3SAnton Habegger }
498040cc7b3SAnton Habegger
499040cc7b3SAnton Habegger return LEB_FREED;
500040cc7b3SAnton Habegger }
501040cc7b3SAnton Habegger
502040cc7b3SAnton Habegger /*
503040cc7b3SAnton Habegger * We scan the entire LEB even though we only really need to scan up to
504040cc7b3SAnton Habegger * (c->leb_size - lp->free).
505040cc7b3SAnton Habegger */
506040cc7b3SAnton Habegger sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0);
507040cc7b3SAnton Habegger if (IS_ERR(sleb))
508040cc7b3SAnton Habegger return PTR_ERR(sleb);
509040cc7b3SAnton Habegger
510040cc7b3SAnton Habegger ubifs_assert(!list_empty(&sleb->nodes));
511040cc7b3SAnton Habegger snod = list_entry(sleb->nodes.next, struct ubifs_scan_node, list);
512040cc7b3SAnton Habegger
513040cc7b3SAnton Habegger if (snod->type == UBIFS_IDX_NODE) {
514040cc7b3SAnton Habegger struct ubifs_gced_idx_leb *idx_gc;
515040cc7b3SAnton Habegger
516040cc7b3SAnton Habegger dbg_gc("indexing LEB %d (free %d, dirty %d)",
517040cc7b3SAnton Habegger lnum, lp->free, lp->dirty);
518040cc7b3SAnton Habegger list_for_each_entry(snod, &sleb->nodes, list) {
519040cc7b3SAnton Habegger struct ubifs_idx_node *idx = snod->node;
520040cc7b3SAnton Habegger int level = le16_to_cpu(idx->level);
521040cc7b3SAnton Habegger
522040cc7b3SAnton Habegger ubifs_assert(snod->type == UBIFS_IDX_NODE);
523040cc7b3SAnton Habegger key_read(c, ubifs_idx_key(c, idx), &snod->key);
524040cc7b3SAnton Habegger err = ubifs_dirty_idx_node(c, &snod->key, level, lnum,
525040cc7b3SAnton Habegger snod->offs);
526040cc7b3SAnton Habegger if (err)
527040cc7b3SAnton Habegger goto out;
528040cc7b3SAnton Habegger }
529040cc7b3SAnton Habegger
530040cc7b3SAnton Habegger idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
531040cc7b3SAnton Habegger if (!idx_gc) {
532040cc7b3SAnton Habegger err = -ENOMEM;
533040cc7b3SAnton Habegger goto out;
534040cc7b3SAnton Habegger }
535040cc7b3SAnton Habegger
536040cc7b3SAnton Habegger idx_gc->lnum = lnum;
537040cc7b3SAnton Habegger idx_gc->unmap = 0;
538040cc7b3SAnton Habegger list_add(&idx_gc->list, &c->idx_gc);
539040cc7b3SAnton Habegger
540040cc7b3SAnton Habegger /*
541040cc7b3SAnton Habegger * Don't release the LEB until after the next commit, because
542040cc7b3SAnton Habegger * it may contain data which is needed for recovery. So
543040cc7b3SAnton Habegger * although we freed this LEB, it will become usable only after
544040cc7b3SAnton Habegger * the commit.
545040cc7b3SAnton Habegger */
546040cc7b3SAnton Habegger err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0,
547040cc7b3SAnton Habegger LPROPS_INDEX, 1);
548040cc7b3SAnton Habegger if (err)
549040cc7b3SAnton Habegger goto out;
550040cc7b3SAnton Habegger err = LEB_FREED_IDX;
551040cc7b3SAnton Habegger } else {
552040cc7b3SAnton Habegger dbg_gc("data LEB %d (free %d, dirty %d)",
553040cc7b3SAnton Habegger lnum, lp->free, lp->dirty);
554040cc7b3SAnton Habegger
555040cc7b3SAnton Habegger err = move_nodes(c, sleb);
556040cc7b3SAnton Habegger if (err)
557040cc7b3SAnton Habegger goto out_inc_seq;
558040cc7b3SAnton Habegger
559040cc7b3SAnton Habegger err = gc_sync_wbufs(c);
560040cc7b3SAnton Habegger if (err)
561040cc7b3SAnton Habegger goto out_inc_seq;
562040cc7b3SAnton Habegger
563040cc7b3SAnton Habegger err = ubifs_change_one_lp(c, lnum, c->leb_size, 0, 0, 0, 0);
564040cc7b3SAnton Habegger if (err)
565040cc7b3SAnton Habegger goto out_inc_seq;
566040cc7b3SAnton Habegger
567040cc7b3SAnton Habegger /* Allow for races with TNC */
568040cc7b3SAnton Habegger c->gced_lnum = lnum;
569040cc7b3SAnton Habegger smp_wmb();
570040cc7b3SAnton Habegger c->gc_seq += 1;
571040cc7b3SAnton Habegger smp_wmb();
572040cc7b3SAnton Habegger
573040cc7b3SAnton Habegger if (c->gc_lnum == -1) {
574040cc7b3SAnton Habegger c->gc_lnum = lnum;
575040cc7b3SAnton Habegger err = LEB_RETAINED;
576040cc7b3SAnton Habegger } else {
577040cc7b3SAnton Habegger err = ubifs_wbuf_sync_nolock(wbuf);
578040cc7b3SAnton Habegger if (err)
579040cc7b3SAnton Habegger goto out;
580040cc7b3SAnton Habegger
581040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, lnum);
582040cc7b3SAnton Habegger if (err)
583040cc7b3SAnton Habegger goto out;
584040cc7b3SAnton Habegger
585040cc7b3SAnton Habegger err = LEB_FREED;
586040cc7b3SAnton Habegger }
587040cc7b3SAnton Habegger }
588040cc7b3SAnton Habegger
589040cc7b3SAnton Habegger out:
590040cc7b3SAnton Habegger ubifs_scan_destroy(sleb);
591040cc7b3SAnton Habegger return err;
592040cc7b3SAnton Habegger
593040cc7b3SAnton Habegger out_inc_seq:
594040cc7b3SAnton Habegger /* We may have moved at least some nodes so allow for races with TNC */
595040cc7b3SAnton Habegger c->gced_lnum = lnum;
596040cc7b3SAnton Habegger smp_wmb();
597040cc7b3SAnton Habegger c->gc_seq += 1;
598040cc7b3SAnton Habegger smp_wmb();
599040cc7b3SAnton Habegger goto out;
600040cc7b3SAnton Habegger }
601040cc7b3SAnton Habegger
602040cc7b3SAnton Habegger /**
603040cc7b3SAnton Habegger * ubifs_garbage_collect - UBIFS garbage collector.
604040cc7b3SAnton Habegger * @c: UBIFS file-system description object
605040cc7b3SAnton Habegger * @anyway: do GC even if there are free LEBs
606040cc7b3SAnton Habegger *
607040cc7b3SAnton Habegger * This function does out-of-place garbage collection. The return codes are:
608040cc7b3SAnton Habegger * o positive LEB number if the LEB has been freed and may be used;
609040cc7b3SAnton Habegger * o %-EAGAIN if the caller has to run commit;
610040cc7b3SAnton Habegger * o %-ENOSPC if GC failed to make any progress;
611040cc7b3SAnton Habegger * o other negative error codes in case of other errors.
612040cc7b3SAnton Habegger *
613040cc7b3SAnton Habegger * Garbage collector writes data to the journal when GC'ing data LEBs, and just
614040cc7b3SAnton Habegger * marking indexing nodes dirty when GC'ing indexing LEBs. Thus, at some point
615040cc7b3SAnton Habegger * commit may be required. But commit cannot be run from inside GC, because the
616040cc7b3SAnton Habegger * caller might be holding the commit lock, so %-EAGAIN is returned instead;
617040cc7b3SAnton Habegger * And this error code means that the caller has to run commit, and re-run GC
618040cc7b3SAnton Habegger * if there is still no free space.
619040cc7b3SAnton Habegger *
620040cc7b3SAnton Habegger * There are many reasons why this function may return %-EAGAIN:
621040cc7b3SAnton Habegger * o the log is full and there is no space to write an LEB reference for
622040cc7b3SAnton Habegger * @c->gc_lnum;
623040cc7b3SAnton Habegger * o the journal is too large and exceeds size limitations;
624040cc7b3SAnton Habegger * o GC moved indexing LEBs, but they can be used only after the commit;
625040cc7b3SAnton Habegger * o the shrinker fails to find clean znodes to free and requests the commit;
626040cc7b3SAnton Habegger * o etc.
627040cc7b3SAnton Habegger *
628040cc7b3SAnton Habegger * Note, if the file-system is close to be full, this function may return
629040cc7b3SAnton Habegger * %-EAGAIN infinitely, so the caller has to limit amount of re-invocations of
630040cc7b3SAnton Habegger * the function. E.g., this happens if the limits on the journal size are too
631040cc7b3SAnton Habegger * tough and GC writes too much to the journal before an LEB is freed. This
632040cc7b3SAnton Habegger * might also mean that the journal is too large, and the TNC becomes to big,
633040cc7b3SAnton Habegger * so that the shrinker is constantly called, finds not clean znodes to free,
634040cc7b3SAnton Habegger * and requests commit. Well, this may also happen if the journal is all right,
635040cc7b3SAnton Habegger * but another kernel process consumes too much memory. Anyway, infinite
636040cc7b3SAnton Habegger * %-EAGAIN may happen, but in some extreme/misconfiguration cases.
637040cc7b3SAnton Habegger */
ubifs_garbage_collect(struct ubifs_info * c,int anyway)638040cc7b3SAnton Habegger int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
639040cc7b3SAnton Habegger {
640040cc7b3SAnton Habegger int i, err, ret, min_space = c->dead_wm;
641040cc7b3SAnton Habegger struct ubifs_lprops lp;
642040cc7b3SAnton Habegger struct ubifs_wbuf *wbuf = &c->jheads[GCHD].wbuf;
643040cc7b3SAnton Habegger
644040cc7b3SAnton Habegger ubifs_assert_cmt_locked(c);
645040cc7b3SAnton Habegger ubifs_assert(!c->ro_media && !c->ro_mount);
646040cc7b3SAnton Habegger
647040cc7b3SAnton Habegger if (ubifs_gc_should_commit(c))
648040cc7b3SAnton Habegger return -EAGAIN;
649040cc7b3SAnton Habegger
650040cc7b3SAnton Habegger mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
651040cc7b3SAnton Habegger
652040cc7b3SAnton Habegger if (c->ro_error) {
653040cc7b3SAnton Habegger ret = -EROFS;
654040cc7b3SAnton Habegger goto out_unlock;
655040cc7b3SAnton Habegger }
656040cc7b3SAnton Habegger
657040cc7b3SAnton Habegger /* We expect the write-buffer to be empty on entry */
658040cc7b3SAnton Habegger ubifs_assert(!wbuf->used);
659040cc7b3SAnton Habegger
660040cc7b3SAnton Habegger for (i = 0; ; i++) {
661040cc7b3SAnton Habegger int space_before, space_after;
662040cc7b3SAnton Habegger
663040cc7b3SAnton Habegger cond_resched();
664040cc7b3SAnton Habegger
665040cc7b3SAnton Habegger /* Give the commit an opportunity to run */
666040cc7b3SAnton Habegger if (ubifs_gc_should_commit(c)) {
667040cc7b3SAnton Habegger ret = -EAGAIN;
668040cc7b3SAnton Habegger break;
669040cc7b3SAnton Habegger }
670040cc7b3SAnton Habegger
671040cc7b3SAnton Habegger if (i > SOFT_LEBS_LIMIT && !list_empty(&c->idx_gc)) {
672040cc7b3SAnton Habegger /*
673040cc7b3SAnton Habegger * We've done enough iterations. Indexing LEBs were
674040cc7b3SAnton Habegger * moved and will be available after the commit.
675040cc7b3SAnton Habegger */
676040cc7b3SAnton Habegger dbg_gc("soft limit, some index LEBs GC'ed, -EAGAIN");
677040cc7b3SAnton Habegger ubifs_commit_required(c);
678040cc7b3SAnton Habegger ret = -EAGAIN;
679040cc7b3SAnton Habegger break;
680040cc7b3SAnton Habegger }
681040cc7b3SAnton Habegger
682040cc7b3SAnton Habegger if (i > HARD_LEBS_LIMIT) {
683040cc7b3SAnton Habegger /*
684040cc7b3SAnton Habegger * We've moved too many LEBs and have not made
685040cc7b3SAnton Habegger * progress, give up.
686040cc7b3SAnton Habegger */
687040cc7b3SAnton Habegger dbg_gc("hard limit, -ENOSPC");
688040cc7b3SAnton Habegger ret = -ENOSPC;
689040cc7b3SAnton Habegger break;
690040cc7b3SAnton Habegger }
691040cc7b3SAnton Habegger
692040cc7b3SAnton Habegger /*
693040cc7b3SAnton Habegger * Empty and freeable LEBs can turn up while we waited for
694040cc7b3SAnton Habegger * the wbuf lock, or while we have been running GC. In that
695040cc7b3SAnton Habegger * case, we should just return one of those instead of
696040cc7b3SAnton Habegger * continuing to GC dirty LEBs. Hence we request
697040cc7b3SAnton Habegger * 'ubifs_find_dirty_leb()' to return an empty LEB if it can.
698040cc7b3SAnton Habegger */
699040cc7b3SAnton Habegger ret = ubifs_find_dirty_leb(c, &lp, min_space, anyway ? 0 : 1);
700040cc7b3SAnton Habegger if (ret) {
701040cc7b3SAnton Habegger if (ret == -ENOSPC)
702040cc7b3SAnton Habegger dbg_gc("no more dirty LEBs");
703040cc7b3SAnton Habegger break;
704040cc7b3SAnton Habegger }
705040cc7b3SAnton Habegger
706040cc7b3SAnton Habegger dbg_gc("found LEB %d: free %d, dirty %d, sum %d (min. space %d)",
707040cc7b3SAnton Habegger lp.lnum, lp.free, lp.dirty, lp.free + lp.dirty,
708040cc7b3SAnton Habegger min_space);
709040cc7b3SAnton Habegger
710040cc7b3SAnton Habegger space_before = c->leb_size - wbuf->offs - wbuf->used;
711040cc7b3SAnton Habegger if (wbuf->lnum == -1)
712040cc7b3SAnton Habegger space_before = 0;
713040cc7b3SAnton Habegger
714040cc7b3SAnton Habegger ret = ubifs_garbage_collect_leb(c, &lp);
715040cc7b3SAnton Habegger if (ret < 0) {
716040cc7b3SAnton Habegger if (ret == -EAGAIN) {
717040cc7b3SAnton Habegger /*
718040cc7b3SAnton Habegger * This is not error, so we have to return the
719040cc7b3SAnton Habegger * LEB to lprops. But if 'ubifs_return_leb()'
720040cc7b3SAnton Habegger * fails, its failure code is propagated to the
721040cc7b3SAnton Habegger * caller instead of the original '-EAGAIN'.
722040cc7b3SAnton Habegger */
723040cc7b3SAnton Habegger err = ubifs_return_leb(c, lp.lnum);
724040cc7b3SAnton Habegger if (err)
725040cc7b3SAnton Habegger ret = err;
726040cc7b3SAnton Habegger break;
727040cc7b3SAnton Habegger }
728040cc7b3SAnton Habegger goto out;
729040cc7b3SAnton Habegger }
730040cc7b3SAnton Habegger
731040cc7b3SAnton Habegger if (ret == LEB_FREED) {
732040cc7b3SAnton Habegger /* An LEB has been freed and is ready for use */
733040cc7b3SAnton Habegger dbg_gc("LEB %d freed, return", lp.lnum);
734040cc7b3SAnton Habegger ret = lp.lnum;
735040cc7b3SAnton Habegger break;
736040cc7b3SAnton Habegger }
737040cc7b3SAnton Habegger
738040cc7b3SAnton Habegger if (ret == LEB_FREED_IDX) {
739040cc7b3SAnton Habegger /*
740040cc7b3SAnton Habegger * This was an indexing LEB and it cannot be
741040cc7b3SAnton Habegger * immediately used. And instead of requesting the
742040cc7b3SAnton Habegger * commit straight away, we try to garbage collect some
743040cc7b3SAnton Habegger * more.
744040cc7b3SAnton Habegger */
745040cc7b3SAnton Habegger dbg_gc("indexing LEB %d freed, continue", lp.lnum);
746040cc7b3SAnton Habegger continue;
747040cc7b3SAnton Habegger }
748040cc7b3SAnton Habegger
749040cc7b3SAnton Habegger ubifs_assert(ret == LEB_RETAINED);
750040cc7b3SAnton Habegger space_after = c->leb_size - wbuf->offs - wbuf->used;
751040cc7b3SAnton Habegger dbg_gc("LEB %d retained, freed %d bytes", lp.lnum,
752040cc7b3SAnton Habegger space_after - space_before);
753040cc7b3SAnton Habegger
754040cc7b3SAnton Habegger if (space_after > space_before) {
755040cc7b3SAnton Habegger /* GC makes progress, keep working */
756040cc7b3SAnton Habegger min_space >>= 1;
757040cc7b3SAnton Habegger if (min_space < c->dead_wm)
758040cc7b3SAnton Habegger min_space = c->dead_wm;
759040cc7b3SAnton Habegger continue;
760040cc7b3SAnton Habegger }
761040cc7b3SAnton Habegger
762040cc7b3SAnton Habegger dbg_gc("did not make progress");
763040cc7b3SAnton Habegger
764040cc7b3SAnton Habegger /*
765040cc7b3SAnton Habegger * GC moved an LEB bud have not done any progress. This means
766040cc7b3SAnton Habegger * that the previous GC head LEB contained too few free space
767040cc7b3SAnton Habegger * and the LEB which was GC'ed contained only large nodes which
768040cc7b3SAnton Habegger * did not fit that space.
769040cc7b3SAnton Habegger *
770040cc7b3SAnton Habegger * We can do 2 things:
771040cc7b3SAnton Habegger * 1. pick another LEB in a hope it'll contain a small node
772040cc7b3SAnton Habegger * which will fit the space we have at the end of current GC
773040cc7b3SAnton Habegger * head LEB, but there is no guarantee, so we try this out
774040cc7b3SAnton Habegger * unless we have already been working for too long;
775040cc7b3SAnton Habegger * 2. request an LEB with more dirty space, which will force
776040cc7b3SAnton Habegger * 'ubifs_find_dirty_leb()' to start scanning the lprops
777040cc7b3SAnton Habegger * table, instead of just picking one from the heap
778040cc7b3SAnton Habegger * (previously it already picked the dirtiest LEB).
779040cc7b3SAnton Habegger */
780040cc7b3SAnton Habegger if (i < SOFT_LEBS_LIMIT) {
781040cc7b3SAnton Habegger dbg_gc("try again");
782040cc7b3SAnton Habegger continue;
783040cc7b3SAnton Habegger }
784040cc7b3SAnton Habegger
785040cc7b3SAnton Habegger min_space <<= 1;
786040cc7b3SAnton Habegger if (min_space > c->dark_wm)
787040cc7b3SAnton Habegger min_space = c->dark_wm;
788040cc7b3SAnton Habegger dbg_gc("set min. space to %d", min_space);
789040cc7b3SAnton Habegger }
790040cc7b3SAnton Habegger
791040cc7b3SAnton Habegger if (ret == -ENOSPC && !list_empty(&c->idx_gc)) {
792040cc7b3SAnton Habegger dbg_gc("no space, some index LEBs GC'ed, -EAGAIN");
793040cc7b3SAnton Habegger ubifs_commit_required(c);
794040cc7b3SAnton Habegger ret = -EAGAIN;
795040cc7b3SAnton Habegger }
796040cc7b3SAnton Habegger
797040cc7b3SAnton Habegger err = ubifs_wbuf_sync_nolock(wbuf);
798040cc7b3SAnton Habegger if (!err)
799040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, c->gc_lnum);
800040cc7b3SAnton Habegger if (err) {
801040cc7b3SAnton Habegger ret = err;
802040cc7b3SAnton Habegger goto out;
803040cc7b3SAnton Habegger }
804040cc7b3SAnton Habegger out_unlock:
805040cc7b3SAnton Habegger mutex_unlock(&wbuf->io_mutex);
806040cc7b3SAnton Habegger return ret;
807040cc7b3SAnton Habegger
808040cc7b3SAnton Habegger out:
809040cc7b3SAnton Habegger ubifs_assert(ret < 0);
810040cc7b3SAnton Habegger ubifs_assert(ret != -ENOSPC && ret != -EAGAIN);
811040cc7b3SAnton Habegger ubifs_wbuf_sync_nolock(wbuf);
812040cc7b3SAnton Habegger ubifs_ro_mode(c, ret);
813040cc7b3SAnton Habegger mutex_unlock(&wbuf->io_mutex);
814040cc7b3SAnton Habegger ubifs_return_leb(c, lp.lnum);
815040cc7b3SAnton Habegger return ret;
816040cc7b3SAnton Habegger }
817040cc7b3SAnton Habegger
818040cc7b3SAnton Habegger /**
819040cc7b3SAnton Habegger * ubifs_gc_start_commit - garbage collection at start of commit.
820040cc7b3SAnton Habegger * @c: UBIFS file-system description object
821040cc7b3SAnton Habegger *
822040cc7b3SAnton Habegger * If a LEB has only dirty and free space, then we may safely unmap it and make
823040cc7b3SAnton Habegger * it free. Note, we cannot do this with indexing LEBs because dirty space may
824040cc7b3SAnton Habegger * correspond index nodes that are required for recovery. In that case, the
825040cc7b3SAnton Habegger * LEB cannot be unmapped until after the next commit.
826040cc7b3SAnton Habegger *
827040cc7b3SAnton Habegger * This function returns %0 upon success and a negative error code upon failure.
828040cc7b3SAnton Habegger */
ubifs_gc_start_commit(struct ubifs_info * c)829040cc7b3SAnton Habegger int ubifs_gc_start_commit(struct ubifs_info *c)
830040cc7b3SAnton Habegger {
831040cc7b3SAnton Habegger struct ubifs_gced_idx_leb *idx_gc;
832040cc7b3SAnton Habegger const struct ubifs_lprops *lp;
833040cc7b3SAnton Habegger int err = 0, flags;
834040cc7b3SAnton Habegger
835040cc7b3SAnton Habegger ubifs_get_lprops(c);
836040cc7b3SAnton Habegger
837040cc7b3SAnton Habegger /*
838040cc7b3SAnton Habegger * Unmap (non-index) freeable LEBs. Note that recovery requires that all
839040cc7b3SAnton Habegger * wbufs are sync'd before this, which is done in 'do_commit()'.
840040cc7b3SAnton Habegger */
841040cc7b3SAnton Habegger while (1) {
842040cc7b3SAnton Habegger lp = ubifs_fast_find_freeable(c);
843040cc7b3SAnton Habegger if (IS_ERR(lp)) {
844040cc7b3SAnton Habegger err = PTR_ERR(lp);
845040cc7b3SAnton Habegger goto out;
846040cc7b3SAnton Habegger }
847040cc7b3SAnton Habegger if (!lp)
848040cc7b3SAnton Habegger break;
849040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_TAKEN));
850040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_INDEX));
851040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, lp->lnum);
852040cc7b3SAnton Habegger if (err)
853040cc7b3SAnton Habegger goto out;
854040cc7b3SAnton Habegger lp = ubifs_change_lp(c, lp, c->leb_size, 0, lp->flags, 0);
855040cc7b3SAnton Habegger if (IS_ERR(lp)) {
856040cc7b3SAnton Habegger err = PTR_ERR(lp);
857040cc7b3SAnton Habegger goto out;
858040cc7b3SAnton Habegger }
859040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_TAKEN));
860040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_INDEX));
861040cc7b3SAnton Habegger }
862040cc7b3SAnton Habegger
863040cc7b3SAnton Habegger /* Mark GC'd index LEBs OK to unmap after this commit finishes */
864040cc7b3SAnton Habegger list_for_each_entry(idx_gc, &c->idx_gc, list)
865040cc7b3SAnton Habegger idx_gc->unmap = 1;
866040cc7b3SAnton Habegger
867040cc7b3SAnton Habegger /* Record index freeable LEBs for unmapping after commit */
868040cc7b3SAnton Habegger while (1) {
869040cc7b3SAnton Habegger lp = ubifs_fast_find_frdi_idx(c);
870040cc7b3SAnton Habegger if (IS_ERR(lp)) {
871040cc7b3SAnton Habegger err = PTR_ERR(lp);
872040cc7b3SAnton Habegger goto out;
873040cc7b3SAnton Habegger }
874040cc7b3SAnton Habegger if (!lp)
875040cc7b3SAnton Habegger break;
876040cc7b3SAnton Habegger idx_gc = kmalloc(sizeof(struct ubifs_gced_idx_leb), GFP_NOFS);
877040cc7b3SAnton Habegger if (!idx_gc) {
878040cc7b3SAnton Habegger err = -ENOMEM;
879040cc7b3SAnton Habegger goto out;
880040cc7b3SAnton Habegger }
881040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_TAKEN));
882040cc7b3SAnton Habegger ubifs_assert(lp->flags & LPROPS_INDEX);
883040cc7b3SAnton Habegger /* Don't release the LEB until after the next commit */
884040cc7b3SAnton Habegger flags = (lp->flags | LPROPS_TAKEN) ^ LPROPS_INDEX;
885040cc7b3SAnton Habegger lp = ubifs_change_lp(c, lp, c->leb_size, 0, flags, 1);
886040cc7b3SAnton Habegger if (IS_ERR(lp)) {
887040cc7b3SAnton Habegger err = PTR_ERR(lp);
888040cc7b3SAnton Habegger kfree(idx_gc);
889040cc7b3SAnton Habegger goto out;
890040cc7b3SAnton Habegger }
891040cc7b3SAnton Habegger ubifs_assert(lp->flags & LPROPS_TAKEN);
892040cc7b3SAnton Habegger ubifs_assert(!(lp->flags & LPROPS_INDEX));
893040cc7b3SAnton Habegger idx_gc->lnum = lp->lnum;
894040cc7b3SAnton Habegger idx_gc->unmap = 1;
895040cc7b3SAnton Habegger list_add(&idx_gc->list, &c->idx_gc);
896040cc7b3SAnton Habegger }
897040cc7b3SAnton Habegger out:
898040cc7b3SAnton Habegger ubifs_release_lprops(c);
899040cc7b3SAnton Habegger return err;
900040cc7b3SAnton Habegger }
901040cc7b3SAnton Habegger
902040cc7b3SAnton Habegger /**
903040cc7b3SAnton Habegger * ubifs_gc_end_commit - garbage collection at end of commit.
904040cc7b3SAnton Habegger * @c: UBIFS file-system description object
905040cc7b3SAnton Habegger *
906040cc7b3SAnton Habegger * This function completes out-of-place garbage collection of index LEBs.
907040cc7b3SAnton Habegger */
ubifs_gc_end_commit(struct ubifs_info * c)908040cc7b3SAnton Habegger int ubifs_gc_end_commit(struct ubifs_info *c)
909040cc7b3SAnton Habegger {
910040cc7b3SAnton Habegger struct ubifs_gced_idx_leb *idx_gc, *tmp;
911040cc7b3SAnton Habegger struct ubifs_wbuf *wbuf;
912040cc7b3SAnton Habegger int err = 0;
913040cc7b3SAnton Habegger
914040cc7b3SAnton Habegger wbuf = &c->jheads[GCHD].wbuf;
915040cc7b3SAnton Habegger mutex_lock_nested(&wbuf->io_mutex, wbuf->jhead);
916040cc7b3SAnton Habegger list_for_each_entry_safe(idx_gc, tmp, &c->idx_gc, list)
917040cc7b3SAnton Habegger if (idx_gc->unmap) {
918040cc7b3SAnton Habegger dbg_gc("LEB %d", idx_gc->lnum);
919040cc7b3SAnton Habegger err = ubifs_leb_unmap(c, idx_gc->lnum);
920040cc7b3SAnton Habegger if (err)
921040cc7b3SAnton Habegger goto out;
922040cc7b3SAnton Habegger err = ubifs_change_one_lp(c, idx_gc->lnum, LPROPS_NC,
923040cc7b3SAnton Habegger LPROPS_NC, 0, LPROPS_TAKEN, -1);
924040cc7b3SAnton Habegger if (err)
925040cc7b3SAnton Habegger goto out;
926040cc7b3SAnton Habegger list_del(&idx_gc->list);
927040cc7b3SAnton Habegger kfree(idx_gc);
928040cc7b3SAnton Habegger }
929040cc7b3SAnton Habegger out:
930040cc7b3SAnton Habegger mutex_unlock(&wbuf->io_mutex);
931040cc7b3SAnton Habegger return err;
932040cc7b3SAnton Habegger }
933040cc7b3SAnton Habegger #endif
934040cc7b3SAnton Habegger /**
935040cc7b3SAnton Habegger * ubifs_destroy_idx_gc - destroy idx_gc list.
936040cc7b3SAnton Habegger * @c: UBIFS file-system description object
937040cc7b3SAnton Habegger *
938040cc7b3SAnton Habegger * This function destroys the @c->idx_gc list. It is called when unmounting
939040cc7b3SAnton Habegger * so locks are not needed. Returns zero in case of success and a negative
940040cc7b3SAnton Habegger * error code in case of failure.
941040cc7b3SAnton Habegger */
ubifs_destroy_idx_gc(struct ubifs_info * c)942040cc7b3SAnton Habegger void ubifs_destroy_idx_gc(struct ubifs_info *c)
943040cc7b3SAnton Habegger {
944040cc7b3SAnton Habegger while (!list_empty(&c->idx_gc)) {
945040cc7b3SAnton Habegger struct ubifs_gced_idx_leb *idx_gc;
946040cc7b3SAnton Habegger
947040cc7b3SAnton Habegger idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb,
948040cc7b3SAnton Habegger list);
949040cc7b3SAnton Habegger c->idx_gc_cnt -= 1;
950040cc7b3SAnton Habegger list_del(&idx_gc->list);
951040cc7b3SAnton Habegger kfree(idx_gc);
952040cc7b3SAnton Habegger }
953040cc7b3SAnton Habegger }
954040cc7b3SAnton Habegger #ifndef __UBOOT__
955040cc7b3SAnton Habegger /**
956040cc7b3SAnton Habegger * ubifs_get_idx_gc_leb - get a LEB from GC'd index LEB list.
957040cc7b3SAnton Habegger * @c: UBIFS file-system description object
958040cc7b3SAnton Habegger *
959040cc7b3SAnton Habegger * Called during start commit so locks are not needed.
960040cc7b3SAnton Habegger */
ubifs_get_idx_gc_leb(struct ubifs_info * c)961040cc7b3SAnton Habegger int ubifs_get_idx_gc_leb(struct ubifs_info *c)
962040cc7b3SAnton Habegger {
963040cc7b3SAnton Habegger struct ubifs_gced_idx_leb *idx_gc;
964040cc7b3SAnton Habegger int lnum;
965040cc7b3SAnton Habegger
966040cc7b3SAnton Habegger if (list_empty(&c->idx_gc))
967040cc7b3SAnton Habegger return -ENOSPC;
968040cc7b3SAnton Habegger idx_gc = list_entry(c->idx_gc.next, struct ubifs_gced_idx_leb, list);
969040cc7b3SAnton Habegger lnum = idx_gc->lnum;
970040cc7b3SAnton Habegger /* c->idx_gc_cnt is updated by the caller when lprops are updated */
971040cc7b3SAnton Habegger list_del(&idx_gc->list);
972040cc7b3SAnton Habegger kfree(idx_gc);
973040cc7b3SAnton Habegger return lnum;
974040cc7b3SAnton Habegger }
975040cc7b3SAnton Habegger #endif
976