]>
Commit | Line | Data |
---|---|---|
2b27bdcc | 1 | // SPDX-License-Identifier: GPL-2.0-only |
1e51764a AB |
2 | /* |
3 | * This file is part of UBIFS. | |
4 | * | |
5 | * Copyright (C) 2006-2008 Nokia Corporation. | |
6 | * | |
1e51764a AB |
7 | * Authors: Artem Bityutskiy (Битюцкий Артём) |
8 | * Adrian Hunter | |
9 | */ | |
10 | ||
11 | /* | |
12 | * This file contains functions for finding LEBs for various purposes e.g. | |
13 | * garbage collection. In general, lprops category heaps and lists are used | |
14 | * for fast access, falling back on scanning the LPT as a last resort. | |
15 | */ | |
16 | ||
17 | #include <linux/sort.h> | |
18 | #include "ubifs.h" | |
19 | ||
20 | /** | |
21 | * struct scan_data - data provided to scan callback functions | |
22 | * @min_space: minimum number of bytes for which to scan | |
23 | * @pick_free: whether it is OK to scan for empty LEBs | |
24 | * @lnum: LEB number found is returned here | |
25 | * @exclude_index: whether to exclude index LEBs | |
26 | */ | |
27 | struct scan_data { | |
28 | int min_space; | |
29 | int pick_free; | |
30 | int lnum; | |
31 | int exclude_index; | |
32 | }; | |
33 | ||
34 | /** | |
35 | * valuable - determine whether LEB properties are valuable. | |
36 | * @c: the UBIFS file-system description object | |
37 | * @lprops: LEB properties | |
38 | * | |
39 | * This function return %1 if the LEB properties should be added to the LEB | |
40 | * properties tree in memory. Otherwise %0 is returned. | |
41 | */ | |
42 | static int valuable(struct ubifs_info *c, const struct ubifs_lprops *lprops) | |
43 | { | |
44 | int n, cat = lprops->flags & LPROPS_CAT_MASK; | |
45 | struct ubifs_lpt_heap *heap; | |
46 | ||
47 | switch (cat) { | |
48 | case LPROPS_DIRTY: | |
49 | case LPROPS_DIRTY_IDX: | |
50 | case LPROPS_FREE: | |
51 | heap = &c->lpt_heap[cat - 1]; | |
52 | if (heap->cnt < heap->max_cnt) | |
53 | return 1; | |
54 | if (lprops->free + lprops->dirty >= c->dark_wm) | |
55 | return 1; | |
56 | return 0; | |
57 | case LPROPS_EMPTY: | |
58 | n = c->lst.empty_lebs + c->freeable_cnt - | |
59 | c->lst.taken_empty_lebs; | |
60 | if (n < c->lsave_cnt) | |
61 | return 1; | |
62 | return 0; | |
63 | case LPROPS_FREEABLE: | |
64 | return 1; | |
65 | case LPROPS_FRDI_IDX: | |
66 | return 1; | |
67 | } | |
68 | return 0; | |
69 | } | |
70 | ||
71 | /** | |
72 | * scan_for_dirty_cb - dirty space scan callback. | |
73 | * @c: the UBIFS file-system description object | |
74 | * @lprops: LEB properties to scan | |
75 | * @in_tree: whether the LEB properties are in main memory | |
76 | * @data: information passed to and from the caller of the scan | |
77 | * | |
78 | * This function returns a code that indicates whether the scan should continue | |
79 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
80 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
81 | * (%LPT_SCAN_STOP). | |
82 | */ | |
83 | static int scan_for_dirty_cb(struct ubifs_info *c, | |
84 | const struct ubifs_lprops *lprops, int in_tree, | |
85 | struct scan_data *data) | |
86 | { | |
87 | int ret = LPT_SCAN_CONTINUE; | |
88 | ||
89 | /* Exclude LEBs that are currently in use */ | |
90 | if (lprops->flags & LPROPS_TAKEN) | |
91 | return LPT_SCAN_CONTINUE; | |
92 | /* Determine whether to add these LEB properties to the tree */ | |
93 | if (!in_tree && valuable(c, lprops)) | |
94 | ret |= LPT_SCAN_ADD; | |
95 | /* Exclude LEBs with too little space */ | |
96 | if (lprops->free + lprops->dirty < data->min_space) | |
97 | return ret; | |
98 | /* If specified, exclude index LEBs */ | |
99 | if (data->exclude_index && lprops->flags & LPROPS_INDEX) | |
100 | return ret; | |
101 | /* If specified, exclude empty or freeable LEBs */ | |
102 | if (lprops->free + lprops->dirty == c->leb_size) { | |
103 | if (!data->pick_free) | |
104 | return ret; | |
105 | /* Exclude LEBs with too little dirty space (unless it is empty) */ | |
106 | } else if (lprops->dirty < c->dead_wm) | |
107 | return ret; | |
108 | /* Finally we found space */ | |
109 | data->lnum = lprops->lnum; | |
110 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
111 | } | |
112 | ||
113 | /** | |
114 | * scan_for_dirty - find a data LEB with free space. | |
115 | * @c: the UBIFS file-system description object | |
116 | * @min_space: minimum amount free plus dirty space the returned LEB has to | |
117 | * have | |
118 | * @pick_free: if it is OK to return a free or freeable LEB | |
119 | * @exclude_index: whether to exclude index LEBs | |
120 | * | |
121 | * This function returns a pointer to the LEB properties found or a negative | |
122 | * error code. | |
123 | */ | |
124 | static const struct ubifs_lprops *scan_for_dirty(struct ubifs_info *c, | |
125 | int min_space, int pick_free, | |
126 | int exclude_index) | |
127 | { | |
128 | const struct ubifs_lprops *lprops; | |
129 | struct ubifs_lpt_heap *heap; | |
130 | struct scan_data data; | |
131 | int err, i; | |
132 | ||
133 | /* There may be an LEB with enough dirty space on the free heap */ | |
134 | heap = &c->lpt_heap[LPROPS_FREE - 1]; | |
135 | for (i = 0; i < heap->cnt; i++) { | |
136 | lprops = heap->arr[i]; | |
137 | if (lprops->free + lprops->dirty < min_space) | |
138 | continue; | |
139 | if (lprops->dirty < c->dead_wm) | |
140 | continue; | |
141 | return lprops; | |
142 | } | |
143 | /* | |
144 | * A LEB may have fallen off of the bottom of the dirty heap, and ended | |
145 | * up as uncategorized even though it has enough dirty space for us now, | |
146 | * so check the uncategorized list. N.B. neither empty nor freeable LEBs | |
147 | * can end up as uncategorized because they are kept on lists not | |
148 | * finite-sized heaps. | |
149 | */ | |
150 | list_for_each_entry(lprops, &c->uncat_list, list) { | |
151 | if (lprops->flags & LPROPS_TAKEN) | |
152 | continue; | |
153 | if (lprops->free + lprops->dirty < min_space) | |
154 | continue; | |
155 | if (exclude_index && (lprops->flags & LPROPS_INDEX)) | |
156 | continue; | |
157 | if (lprops->dirty < c->dead_wm) | |
158 | continue; | |
159 | return lprops; | |
160 | } | |
161 | /* We have looked everywhere in main memory, now scan the flash */ | |
162 | if (c->pnodes_have >= c->pnode_cnt) | |
163 | /* All pnodes are in memory, so skip scan */ | |
164 | return ERR_PTR(-ENOSPC); | |
165 | data.min_space = min_space; | |
166 | data.pick_free = pick_free; | |
167 | data.lnum = -1; | |
168 | data.exclude_index = exclude_index; | |
169 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
170 | (ubifs_lpt_scan_callback)scan_for_dirty_cb, | |
171 | &data); | |
172 | if (err) | |
173 | return ERR_PTR(err); | |
6eb61d58 | 174 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
1e51764a AB |
175 | c->lscan_lnum = data.lnum; |
176 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
177 | if (IS_ERR(lprops)) | |
178 | return lprops; | |
6eb61d58 RW |
179 | ubifs_assert(c, lprops->lnum == data.lnum); |
180 | ubifs_assert(c, lprops->free + lprops->dirty >= min_space); | |
181 | ubifs_assert(c, lprops->dirty >= c->dead_wm || | |
1e51764a AB |
182 | (pick_free && |
183 | lprops->free + lprops->dirty == c->leb_size)); | |
6eb61d58 RW |
184 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); |
185 | ubifs_assert(c, !exclude_index || !(lprops->flags & LPROPS_INDEX)); | |
1e51764a AB |
186 | return lprops; |
187 | } | |
188 | ||
189 | /** | |
190 | * ubifs_find_dirty_leb - find a dirty LEB for the Garbage Collector. | |
191 | * @c: the UBIFS file-system description object | |
192 | * @ret_lp: LEB properties are returned here on exit | |
193 | * @min_space: minimum amount free plus dirty space the returned LEB has to | |
194 | * have | |
195 | * @pick_free: controls whether it is OK to pick empty or index LEBs | |
196 | * | |
197 | * This function tries to find a dirty logical eraseblock which has at least | |
198 | * @min_space free and dirty space. It prefers to take an LEB from the dirty or | |
199 | * dirty index heap, and it falls-back to LPT scanning if the heaps are empty | |
200 | * or do not have an LEB which satisfies the @min_space criteria. | |
201 | * | |
ad507653 AB |
202 | * Note, LEBs which have less than dead watermark of free + dirty space are |
203 | * never picked by this function. | |
1e51764a AB |
204 | * |
205 | * The additional @pick_free argument controls if this function has to return a | |
206 | * free or freeable LEB if one is present. For example, GC must to set it to %1, | |
207 | * when called from the journal space reservation function, because the | |
208 | * appearance of free space may coincide with the loss of enough dirty space | |
209 | * for GC to succeed anyway. | |
210 | * | |
211 | * In contrast, if the Garbage Collector is called from budgeting, it should | |
212 | * just make free space, not return LEBs which are already free or freeable. | |
213 | * | |
214 | * In addition @pick_free is set to %2 by the recovery process in order to | |
215 | * recover gc_lnum in which case an index LEB must not be returned. | |
ad507653 AB |
216 | * |
217 | * This function returns zero and the LEB properties of found dirty LEB in case | |
218 | * of success, %-ENOSPC if no dirty LEB was found and a negative error code in | |
219 | * case of other failures. The returned LEB is marked as "taken". | |
1e51764a AB |
220 | */ |
221 | int ubifs_find_dirty_leb(struct ubifs_info *c, struct ubifs_lprops *ret_lp, | |
222 | int min_space, int pick_free) | |
223 | { | |
224 | int err = 0, sum, exclude_index = pick_free == 2 ? 1 : 0; | |
225 | const struct ubifs_lprops *lp = NULL, *idx_lp = NULL; | |
226 | struct ubifs_lpt_heap *heap, *idx_heap; | |
227 | ||
228 | ubifs_get_lprops(c); | |
229 | ||
230 | if (pick_free) { | |
231 | int lebs, rsvd_idx_lebs = 0; | |
232 | ||
233 | spin_lock(&c->space_lock); | |
131130b9 | 234 | lebs = c->lst.empty_lebs + c->idx_gc_cnt; |
1e51764a AB |
235 | lebs += c->freeable_cnt - c->lst.taken_empty_lebs; |
236 | ||
237 | /* | |
238 | * Note, the index may consume more LEBs than have been reserved | |
239 | * for it. It is OK because it might be consolidated by GC. | |
240 | * But if the index takes fewer LEBs than it is reserved for it, | |
241 | * this function must avoid picking those reserved LEBs. | |
242 | */ | |
b137545c AB |
243 | if (c->bi.min_idx_lebs >= c->lst.idx_lebs) { |
244 | rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; | |
1e51764a AB |
245 | exclude_index = 1; |
246 | } | |
247 | spin_unlock(&c->space_lock); | |
248 | ||
249 | /* Check if there are enough free LEBs for the index */ | |
250 | if (rsvd_idx_lebs < lebs) { | |
251 | /* OK, try to find an empty LEB */ | |
252 | lp = ubifs_fast_find_empty(c); | |
253 | if (lp) | |
254 | goto found; | |
255 | ||
256 | /* Or a freeable LEB */ | |
257 | lp = ubifs_fast_find_freeable(c); | |
258 | if (lp) | |
259 | goto found; | |
260 | } else | |
261 | /* | |
262 | * We cannot pick free/freeable LEBs in the below code. | |
263 | */ | |
264 | pick_free = 0; | |
265 | } else { | |
266 | spin_lock(&c->space_lock); | |
b137545c | 267 | exclude_index = (c->bi.min_idx_lebs >= c->lst.idx_lebs); |
1e51764a AB |
268 | spin_unlock(&c->space_lock); |
269 | } | |
270 | ||
271 | /* Look on the dirty and dirty index heaps */ | |
272 | heap = &c->lpt_heap[LPROPS_DIRTY - 1]; | |
273 | idx_heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; | |
274 | ||
275 | if (idx_heap->cnt && !exclude_index) { | |
276 | idx_lp = idx_heap->arr[0]; | |
277 | sum = idx_lp->free + idx_lp->dirty; | |
278 | /* | |
3a13252c | 279 | * Since we reserve thrice as much space for the index than it |
1e51764a | 280 | * actually takes, it does not make sense to pick indexing LEBs |
b364b41a AB |
281 | * with less than, say, half LEB of dirty space. May be half is |
282 | * not the optimal boundary - this should be tested and | |
283 | * checked. This boundary should determine how much we use | |
284 | * in-the-gaps to consolidate the index comparing to how much | |
285 | * we use garbage collector to consolidate it. The "half" | |
286 | * criteria just feels to be fine. | |
1e51764a AB |
287 | */ |
288 | if (sum < min_space || sum < c->half_leb_size) | |
289 | idx_lp = NULL; | |
290 | } | |
291 | ||
292 | if (heap->cnt) { | |
293 | lp = heap->arr[0]; | |
294 | if (lp->dirty + lp->free < min_space) | |
295 | lp = NULL; | |
296 | } | |
297 | ||
298 | /* Pick the LEB with most space */ | |
299 | if (idx_lp && lp) { | |
300 | if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty) | |
301 | lp = idx_lp; | |
302 | } else if (idx_lp && !lp) | |
303 | lp = idx_lp; | |
304 | ||
305 | if (lp) { | |
6eb61d58 | 306 | ubifs_assert(c, lp->free + lp->dirty >= c->dead_wm); |
1e51764a AB |
307 | goto found; |
308 | } | |
309 | ||
310 | /* Did not find a dirty LEB on the dirty heaps, have to scan */ | |
311 | dbg_find("scanning LPT for a dirty LEB"); | |
312 | lp = scan_for_dirty(c, min_space, pick_free, exclude_index); | |
313 | if (IS_ERR(lp)) { | |
314 | err = PTR_ERR(lp); | |
315 | goto out; | |
316 | } | |
6eb61d58 | 317 | ubifs_assert(c, lp->dirty >= c->dead_wm || |
1e51764a AB |
318 | (pick_free && lp->free + lp->dirty == c->leb_size)); |
319 | ||
320 | found: | |
321 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x", | |
322 | lp->lnum, lp->free, lp->dirty, lp->flags); | |
323 | ||
324 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
325 | lp->flags | LPROPS_TAKEN, 0); | |
326 | if (IS_ERR(lp)) { | |
327 | err = PTR_ERR(lp); | |
328 | goto out; | |
329 | } | |
330 | ||
331 | memcpy(ret_lp, lp, sizeof(struct ubifs_lprops)); | |
332 | ||
333 | out: | |
334 | ubifs_release_lprops(c); | |
335 | return err; | |
336 | } | |
337 | ||
338 | /** | |
339 | * scan_for_free_cb - free space scan callback. | |
340 | * @c: the UBIFS file-system description object | |
341 | * @lprops: LEB properties to scan | |
342 | * @in_tree: whether the LEB properties are in main memory | |
343 | * @data: information passed to and from the caller of the scan | |
344 | * | |
345 | * This function returns a code that indicates whether the scan should continue | |
346 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
347 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
348 | * (%LPT_SCAN_STOP). | |
349 | */ | |
350 | static int scan_for_free_cb(struct ubifs_info *c, | |
351 | const struct ubifs_lprops *lprops, int in_tree, | |
352 | struct scan_data *data) | |
353 | { | |
354 | int ret = LPT_SCAN_CONTINUE; | |
355 | ||
356 | /* Exclude LEBs that are currently in use */ | |
357 | if (lprops->flags & LPROPS_TAKEN) | |
358 | return LPT_SCAN_CONTINUE; | |
359 | /* Determine whether to add these LEB properties to the tree */ | |
360 | if (!in_tree && valuable(c, lprops)) | |
361 | ret |= LPT_SCAN_ADD; | |
362 | /* Exclude index LEBs */ | |
363 | if (lprops->flags & LPROPS_INDEX) | |
364 | return ret; | |
365 | /* Exclude LEBs with too little space */ | |
366 | if (lprops->free < data->min_space) | |
367 | return ret; | |
368 | /* If specified, exclude empty LEBs */ | |
369 | if (!data->pick_free && lprops->free == c->leb_size) | |
370 | return ret; | |
371 | /* | |
372 | * LEBs that have only free and dirty space must not be allocated | |
373 | * because they may have been unmapped already or they may have data | |
374 | * that is obsolete only because of nodes that are still sitting in a | |
375 | * wbuf. | |
376 | */ | |
377 | if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0) | |
378 | return ret; | |
379 | /* Finally we found space */ | |
380 | data->lnum = lprops->lnum; | |
381 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
382 | } | |
383 | ||
384 | /** | |
385 | * do_find_free_space - find a data LEB with free space. | |
386 | * @c: the UBIFS file-system description object | |
387 | * @min_space: minimum amount of free space required | |
388 | * @pick_free: whether it is OK to scan for empty LEBs | |
389 | * @squeeze: whether to try to find space in a non-empty LEB first | |
390 | * | |
391 | * This function returns a pointer to the LEB properties found or a negative | |
392 | * error code. | |
393 | */ | |
394 | static | |
395 | const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c, | |
396 | int min_space, int pick_free, | |
397 | int squeeze) | |
398 | { | |
399 | const struct ubifs_lprops *lprops; | |
400 | struct ubifs_lpt_heap *heap; | |
401 | struct scan_data data; | |
402 | int err, i; | |
403 | ||
404 | if (squeeze) { | |
405 | lprops = ubifs_fast_find_free(c); | |
406 | if (lprops && lprops->free >= min_space) | |
407 | return lprops; | |
408 | } | |
409 | if (pick_free) { | |
410 | lprops = ubifs_fast_find_empty(c); | |
411 | if (lprops) | |
412 | return lprops; | |
413 | } | |
414 | if (!squeeze) { | |
415 | lprops = ubifs_fast_find_free(c); | |
416 | if (lprops && lprops->free >= min_space) | |
417 | return lprops; | |
418 | } | |
419 | /* There may be an LEB with enough free space on the dirty heap */ | |
420 | heap = &c->lpt_heap[LPROPS_DIRTY - 1]; | |
421 | for (i = 0; i < heap->cnt; i++) { | |
422 | lprops = heap->arr[i]; | |
423 | if (lprops->free >= min_space) | |
424 | return lprops; | |
425 | } | |
426 | /* | |
427 | * A LEB may have fallen off of the bottom of the free heap, and ended | |
428 | * up as uncategorized even though it has enough free space for us now, | |
429 | * so check the uncategorized list. N.B. neither empty nor freeable LEBs | |
430 | * can end up as uncategorized because they are kept on lists not | |
431 | * finite-sized heaps. | |
432 | */ | |
433 | list_for_each_entry(lprops, &c->uncat_list, list) { | |
434 | if (lprops->flags & LPROPS_TAKEN) | |
435 | continue; | |
436 | if (lprops->flags & LPROPS_INDEX) | |
437 | continue; | |
438 | if (lprops->free >= min_space) | |
439 | return lprops; | |
440 | } | |
441 | /* We have looked everywhere in main memory, now scan the flash */ | |
442 | if (c->pnodes_have >= c->pnode_cnt) | |
443 | /* All pnodes are in memory, so skip scan */ | |
444 | return ERR_PTR(-ENOSPC); | |
445 | data.min_space = min_space; | |
446 | data.pick_free = pick_free; | |
447 | data.lnum = -1; | |
448 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
449 | (ubifs_lpt_scan_callback)scan_for_free_cb, | |
450 | &data); | |
451 | if (err) | |
452 | return ERR_PTR(err); | |
6eb61d58 | 453 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
1e51764a AB |
454 | c->lscan_lnum = data.lnum; |
455 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
456 | if (IS_ERR(lprops)) | |
457 | return lprops; | |
6eb61d58 RW |
458 | ubifs_assert(c, lprops->lnum == data.lnum); |
459 | ubifs_assert(c, lprops->free >= min_space); | |
460 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); | |
461 | ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); | |
1e51764a AB |
462 | return lprops; |
463 | } | |
464 | ||
465 | /** | |
466 | * ubifs_find_free_space - find a data LEB with free space. | |
467 | * @c: the UBIFS file-system description object | |
468 | * @min_space: minimum amount of required free space | |
3edaae7c | 469 | * @offs: contains offset of where free space starts on exit |
1e51764a AB |
470 | * @squeeze: whether to try to find space in a non-empty LEB first |
471 | * | |
472 | * This function looks for an LEB with at least @min_space bytes of free space. | |
473 | * It tries to find an empty LEB if possible. If no empty LEBs are available, | |
474 | * this function searches for a non-empty data LEB. The returned LEB is marked | |
475 | * as "taken". | |
476 | * | |
477 | * This function returns found LEB number in case of success, %-ENOSPC if it | |
478 | * failed to find a LEB with @min_space bytes of free space and other a negative | |
479 | * error codes in case of failure. | |
480 | */ | |
3edaae7c | 481 | int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *offs, |
1e51764a AB |
482 | int squeeze) |
483 | { | |
484 | const struct ubifs_lprops *lprops; | |
485 | int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags; | |
486 | ||
487 | dbg_find("min_space %d", min_space); | |
488 | ubifs_get_lprops(c); | |
489 | ||
490 | /* Check if there are enough empty LEBs for commit */ | |
491 | spin_lock(&c->space_lock); | |
b137545c AB |
492 | if (c->bi.min_idx_lebs > c->lst.idx_lebs) |
493 | rsvd_idx_lebs = c->bi.min_idx_lebs - c->lst.idx_lebs; | |
1e51764a AB |
494 | else |
495 | rsvd_idx_lebs = 0; | |
496 | lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - | |
497 | c->lst.taken_empty_lebs; | |
1e51764a AB |
498 | if (rsvd_idx_lebs < lebs) |
499 | /* | |
500 | * OK to allocate an empty LEB, but we still don't want to go | |
501 | * looking for one if there aren't any. | |
502 | */ | |
503 | if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { | |
504 | pick_free = 1; | |
505 | /* | |
506 | * Because we release the space lock, we must account | |
507 | * for this allocation here. After the LEB properties | |
508 | * flags have been updated, we subtract one. Note, the | |
509 | * result of this is that lprops also decreases | |
510 | * @taken_empty_lebs in 'ubifs_change_lp()', so it is | |
511 | * off by one for a short period of time which may | |
512 | * introduce a small disturbance to budgeting | |
513 | * calculations, but this is harmless because at the | |
514 | * worst case this would make the budgeting subsystem | |
515 | * be more pessimistic than needed. | |
516 | * | |
517 | * Fundamentally, this is about serialization of the | |
518 | * budgeting and lprops subsystems. We could make the | |
519 | * @space_lock a mutex and avoid dropping it before | |
520 | * calling 'ubifs_change_lp()', but mutex is more | |
521 | * heavy-weight, and we want budgeting to be as fast as | |
522 | * possible. | |
523 | */ | |
524 | c->lst.taken_empty_lebs += 1; | |
525 | } | |
526 | spin_unlock(&c->space_lock); | |
527 | ||
528 | lprops = do_find_free_space(c, min_space, pick_free, squeeze); | |
529 | if (IS_ERR(lprops)) { | |
530 | err = PTR_ERR(lprops); | |
531 | goto out; | |
532 | } | |
533 | ||
534 | lnum = lprops->lnum; | |
535 | flags = lprops->flags | LPROPS_TAKEN; | |
536 | ||
537 | lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0); | |
538 | if (IS_ERR(lprops)) { | |
539 | err = PTR_ERR(lprops); | |
540 | goto out; | |
541 | } | |
542 | ||
543 | if (pick_free) { | |
544 | spin_lock(&c->space_lock); | |
545 | c->lst.taken_empty_lebs -= 1; | |
546 | spin_unlock(&c->space_lock); | |
547 | } | |
548 | ||
3edaae7c | 549 | *offs = c->leb_size - lprops->free; |
1e51764a AB |
550 | ubifs_release_lprops(c); |
551 | ||
3edaae7c | 552 | if (*offs == 0) { |
1e51764a AB |
553 | /* |
554 | * Ensure that empty LEBs have been unmapped. They may not have | |
555 | * been, for example, because of an unclean unmount. Also | |
556 | * LEBs that were freeable LEBs (free + dirty == leb_size) will | |
557 | * not have been unmapped. | |
558 | */ | |
559 | err = ubifs_leb_unmap(c, lnum); | |
560 | if (err) | |
561 | return err; | |
562 | } | |
563 | ||
3edaae7c | 564 | dbg_find("found LEB %d, free %d", lnum, c->leb_size - *offs); |
6eb61d58 | 565 | ubifs_assert(c, *offs <= c->leb_size - min_space); |
1e51764a AB |
566 | return lnum; |
567 | ||
568 | out: | |
569 | if (pick_free) { | |
570 | spin_lock(&c->space_lock); | |
571 | c->lst.taken_empty_lebs -= 1; | |
572 | spin_unlock(&c->space_lock); | |
573 | } | |
574 | ubifs_release_lprops(c); | |
575 | return err; | |
576 | } | |
577 | ||
578 | /** | |
579 | * scan_for_idx_cb - callback used by the scan for a free LEB for the index. | |
580 | * @c: the UBIFS file-system description object | |
581 | * @lprops: LEB properties to scan | |
582 | * @in_tree: whether the LEB properties are in main memory | |
583 | * @data: information passed to and from the caller of the scan | |
584 | * | |
585 | * This function returns a code that indicates whether the scan should continue | |
586 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
587 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
588 | * (%LPT_SCAN_STOP). | |
589 | */ | |
590 | static int scan_for_idx_cb(struct ubifs_info *c, | |
591 | const struct ubifs_lprops *lprops, int in_tree, | |
592 | struct scan_data *data) | |
593 | { | |
594 | int ret = LPT_SCAN_CONTINUE; | |
595 | ||
596 | /* Exclude LEBs that are currently in use */ | |
597 | if (lprops->flags & LPROPS_TAKEN) | |
598 | return LPT_SCAN_CONTINUE; | |
599 | /* Determine whether to add these LEB properties to the tree */ | |
600 | if (!in_tree && valuable(c, lprops)) | |
601 | ret |= LPT_SCAN_ADD; | |
602 | /* Exclude index LEBS */ | |
603 | if (lprops->flags & LPROPS_INDEX) | |
604 | return ret; | |
605 | /* Exclude LEBs that cannot be made empty */ | |
606 | if (lprops->free + lprops->dirty != c->leb_size) | |
607 | return ret; | |
608 | /* | |
609 | * We are allocating for the index so it is safe to allocate LEBs with | |
610 | * only free and dirty space, because write buffers are sync'd at commit | |
611 | * start. | |
612 | */ | |
613 | data->lnum = lprops->lnum; | |
614 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
615 | } | |
616 | ||
617 | /** | |
618 | * scan_for_leb_for_idx - scan for a free LEB for the index. | |
619 | * @c: the UBIFS file-system description object | |
620 | */ | |
621 | static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c) | |
622 | { | |
cc194783 | 623 | const struct ubifs_lprops *lprops; |
1e51764a AB |
624 | struct scan_data data; |
625 | int err; | |
626 | ||
627 | data.lnum = -1; | |
628 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
629 | (ubifs_lpt_scan_callback)scan_for_idx_cb, | |
630 | &data); | |
631 | if (err) | |
632 | return ERR_PTR(err); | |
6eb61d58 | 633 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
1e51764a AB |
634 | c->lscan_lnum = data.lnum; |
635 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
636 | if (IS_ERR(lprops)) | |
637 | return lprops; | |
6eb61d58 RW |
638 | ubifs_assert(c, lprops->lnum == data.lnum); |
639 | ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size); | |
640 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); | |
641 | ubifs_assert(c, !(lprops->flags & LPROPS_INDEX)); | |
1e51764a AB |
642 | return lprops; |
643 | } | |
644 | ||
645 | /** | |
646 | * ubifs_find_free_leb_for_idx - find a free LEB for the index. | |
647 | * @c: the UBIFS file-system description object | |
648 | * | |
649 | * This function looks for a free LEB and returns that LEB number. The returned | |
650 | * LEB is marked as "taken", "index". | |
651 | * | |
652 | * Only empty LEBs are allocated. This is for two reasons. First, the commit | |
653 | * calculates the number of LEBs to allocate based on the assumption that they | |
654 | * will be empty. Secondly, free space at the end of an index LEB is not | |
655 | * guaranteed to be empty because it may have been used by the in-the-gaps | |
656 | * method prior to an unclean unmount. | |
657 | * | |
658 | * If no LEB is found %-ENOSPC is returned. For other failures another negative | |
659 | * error code is returned. | |
660 | */ | |
661 | int ubifs_find_free_leb_for_idx(struct ubifs_info *c) | |
662 | { | |
663 | const struct ubifs_lprops *lprops; | |
664 | int lnum = -1, err, flags; | |
665 | ||
666 | ubifs_get_lprops(c); | |
667 | ||
668 | lprops = ubifs_fast_find_empty(c); | |
669 | if (!lprops) { | |
670 | lprops = ubifs_fast_find_freeable(c); | |
671 | if (!lprops) { | |
a28ad42a AB |
672 | /* |
673 | * The first condition means the following: go scan the | |
674 | * LPT if there are uncategorized lprops, which means | |
675 | * there may be freeable LEBs there (UBIFS does not | |
676 | * store the information about freeable LEBs in the | |
677 | * master node). | |
678 | */ | |
679 | if (c->in_a_category_cnt != c->main_lebs || | |
680 | c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { | |
6eb61d58 | 681 | ubifs_assert(c, c->freeable_cnt == 0); |
1e51764a AB |
682 | lprops = scan_for_leb_for_idx(c); |
683 | if (IS_ERR(lprops)) { | |
684 | err = PTR_ERR(lprops); | |
685 | goto out; | |
686 | } | |
687 | } | |
688 | } | |
689 | } | |
690 | ||
691 | if (!lprops) { | |
692 | err = -ENOSPC; | |
693 | goto out; | |
694 | } | |
695 | ||
696 | lnum = lprops->lnum; | |
697 | ||
698 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x", | |
699 | lnum, lprops->free, lprops->dirty, lprops->flags); | |
700 | ||
701 | flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; | |
702 | lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0); | |
703 | if (IS_ERR(lprops)) { | |
704 | err = PTR_ERR(lprops); | |
705 | goto out; | |
706 | } | |
707 | ||
708 | ubifs_release_lprops(c); | |
709 | ||
710 | /* | |
711 | * Ensure that empty LEBs have been unmapped. They may not have been, | |
712 | * for example, because of an unclean unmount. Also LEBs that were | |
713 | * freeable LEBs (free + dirty == leb_size) will not have been unmapped. | |
714 | */ | |
715 | err = ubifs_leb_unmap(c, lnum); | |
716 | if (err) { | |
717 | ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0, | |
718 | LPROPS_TAKEN | LPROPS_INDEX, 0); | |
719 | return err; | |
720 | } | |
721 | ||
722 | return lnum; | |
723 | ||
724 | out: | |
725 | ubifs_release_lprops(c); | |
726 | return err; | |
727 | } | |
728 | ||
729 | static int cmp_dirty_idx(const struct ubifs_lprops **a, | |
730 | const struct ubifs_lprops **b) | |
731 | { | |
732 | const struct ubifs_lprops *lpa = *a; | |
733 | const struct ubifs_lprops *lpb = *b; | |
734 | ||
735 | return lpa->dirty + lpa->free - lpb->dirty - lpb->free; | |
736 | } | |
737 | ||
1e51764a AB |
738 | /** |
739 | * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos. | |
740 | * @c: the UBIFS file-system description object | |
741 | * | |
742 | * This function is called each commit to create an array of LEB numbers of | |
743 | * dirty index LEBs sorted in order of dirty and free space. This is used by | |
744 | * the in-the-gaps method of TNC commit. | |
745 | */ | |
746 | int ubifs_save_dirty_idx_lnums(struct ubifs_info *c) | |
747 | { | |
748 | int i; | |
749 | ||
750 | ubifs_get_lprops(c); | |
751 | /* Copy the LPROPS_DIRTY_IDX heap */ | |
752 | c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; | |
753 | memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, | |
754 | sizeof(void *) * c->dirty_idx.cnt); | |
755 | /* Sort it so that the dirtiest is now at the end */ | |
756 | sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *), | |
257bb924 | 757 | (int (*)(const void *, const void *))cmp_dirty_idx, NULL); |
1e51764a AB |
758 | dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt); |
759 | if (c->dirty_idx.cnt) | |
760 | dbg_find("dirtiest index LEB is %d with dirty %d and free %d", | |
761 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, | |
762 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, | |
763 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); | |
764 | /* Replace the lprops pointers with LEB numbers */ | |
765 | for (i = 0; i < c->dirty_idx.cnt; i++) | |
766 | c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; | |
767 | ubifs_release_lprops(c); | |
768 | return 0; | |
769 | } | |
770 | ||
771 | /** | |
772 | * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB. | |
773 | * @c: the UBIFS file-system description object | |
774 | * @lprops: LEB properties to scan | |
775 | * @in_tree: whether the LEB properties are in main memory | |
776 | * @data: information passed to and from the caller of the scan | |
777 | * | |
778 | * This function returns a code that indicates whether the scan should continue | |
779 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
780 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
781 | * (%LPT_SCAN_STOP). | |
782 | */ | |
783 | static int scan_dirty_idx_cb(struct ubifs_info *c, | |
784 | const struct ubifs_lprops *lprops, int in_tree, | |
785 | struct scan_data *data) | |
786 | { | |
787 | int ret = LPT_SCAN_CONTINUE; | |
788 | ||
789 | /* Exclude LEBs that are currently in use */ | |
790 | if (lprops->flags & LPROPS_TAKEN) | |
791 | return LPT_SCAN_CONTINUE; | |
792 | /* Determine whether to add these LEB properties to the tree */ | |
793 | if (!in_tree && valuable(c, lprops)) | |
794 | ret |= LPT_SCAN_ADD; | |
795 | /* Exclude non-index LEBs */ | |
796 | if (!(lprops->flags & LPROPS_INDEX)) | |
797 | return ret; | |
798 | /* Exclude LEBs with too little space */ | |
799 | if (lprops->free + lprops->dirty < c->min_idx_node_sz) | |
800 | return ret; | |
801 | /* Finally we found space */ | |
802 | data->lnum = lprops->lnum; | |
803 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
804 | } | |
805 | ||
806 | /** | |
807 | * find_dirty_idx_leb - find a dirty index LEB. | |
808 | * @c: the UBIFS file-system description object | |
809 | * | |
810 | * This function returns LEB number upon success and a negative error code upon | |
811 | * failure. In particular, -ENOSPC is returned if a dirty index LEB is not | |
812 | * found. | |
813 | * | |
814 | * Note that this function scans the entire LPT but it is called very rarely. | |
815 | */ | |
816 | static int find_dirty_idx_leb(struct ubifs_info *c) | |
817 | { | |
818 | const struct ubifs_lprops *lprops; | |
819 | struct ubifs_lpt_heap *heap; | |
820 | struct scan_data data; | |
821 | int err, i, ret; | |
822 | ||
823 | /* Check all structures in memory first */ | |
824 | data.lnum = -1; | |
825 | heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; | |
826 | for (i = 0; i < heap->cnt; i++) { | |
827 | lprops = heap->arr[i]; | |
828 | ret = scan_dirty_idx_cb(c, lprops, 1, &data); | |
829 | if (ret & LPT_SCAN_STOP) | |
830 | goto found; | |
831 | } | |
832 | list_for_each_entry(lprops, &c->frdi_idx_list, list) { | |
833 | ret = scan_dirty_idx_cb(c, lprops, 1, &data); | |
834 | if (ret & LPT_SCAN_STOP) | |
835 | goto found; | |
836 | } | |
837 | list_for_each_entry(lprops, &c->uncat_list, list) { | |
838 | ret = scan_dirty_idx_cb(c, lprops, 1, &data); | |
839 | if (ret & LPT_SCAN_STOP) | |
840 | goto found; | |
841 | } | |
842 | if (c->pnodes_have >= c->pnode_cnt) | |
843 | /* All pnodes are in memory, so skip scan */ | |
844 | return -ENOSPC; | |
845 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
846 | (ubifs_lpt_scan_callback)scan_dirty_idx_cb, | |
847 | &data); | |
848 | if (err) | |
849 | return err; | |
850 | found: | |
6eb61d58 | 851 | ubifs_assert(c, data.lnum >= c->main_first && data.lnum < c->leb_cnt); |
1e51764a AB |
852 | c->lscan_lnum = data.lnum; |
853 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
854 | if (IS_ERR(lprops)) | |
855 | return PTR_ERR(lprops); | |
6eb61d58 RW |
856 | ubifs_assert(c, lprops->lnum == data.lnum); |
857 | ubifs_assert(c, lprops->free + lprops->dirty >= c->min_idx_node_sz); | |
858 | ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN)); | |
859 | ubifs_assert(c, (lprops->flags & LPROPS_INDEX)); | |
1e51764a AB |
860 | |
861 | dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x", | |
862 | lprops->lnum, lprops->free, lprops->dirty, lprops->flags); | |
863 | ||
864 | lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, | |
865 | lprops->flags | LPROPS_TAKEN, 0); | |
866 | if (IS_ERR(lprops)) | |
867 | return PTR_ERR(lprops); | |
868 | ||
869 | return lprops->lnum; | |
870 | } | |
871 | ||
872 | /** | |
873 | * get_idx_gc_leb - try to get a LEB number from trivial GC. | |
874 | * @c: the UBIFS file-system description object | |
875 | */ | |
876 | static int get_idx_gc_leb(struct ubifs_info *c) | |
877 | { | |
878 | const struct ubifs_lprops *lp; | |
879 | int err, lnum; | |
880 | ||
881 | err = ubifs_get_idx_gc_leb(c); | |
882 | if (err < 0) | |
883 | return err; | |
884 | lnum = err; | |
885 | /* | |
886 | * The LEB was due to be unmapped after the commit but | |
887 | * it is needed now for this commit. | |
888 | */ | |
889 | lp = ubifs_lpt_lookup_dirty(c, lnum); | |
8d47aef4 | 890 | if (IS_ERR(lp)) |
1e51764a AB |
891 | return PTR_ERR(lp); |
892 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
893 | lp->flags | LPROPS_INDEX, -1); | |
8d47aef4 | 894 | if (IS_ERR(lp)) |
1e51764a AB |
895 | return PTR_ERR(lp); |
896 | dbg_find("LEB %d, dirty %d and free %d flags %#x", | |
897 | lp->lnum, lp->dirty, lp->free, lp->flags); | |
898 | return lnum; | |
899 | } | |
900 | ||
901 | /** | |
902 | * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array. | |
903 | * @c: the UBIFS file-system description object | |
904 | */ | |
905 | static int find_dirtiest_idx_leb(struct ubifs_info *c) | |
906 | { | |
907 | const struct ubifs_lprops *lp; | |
908 | int lnum; | |
909 | ||
910 | while (1) { | |
911 | if (!c->dirty_idx.cnt) | |
912 | return -ENOSPC; | |
913 | /* The lprops pointers were replaced by LEB numbers */ | |
914 | lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; | |
915 | lp = ubifs_lpt_lookup(c, lnum); | |
916 | if (IS_ERR(lp)) | |
917 | return PTR_ERR(lp); | |
918 | if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) | |
919 | continue; | |
920 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
921 | lp->flags | LPROPS_TAKEN, 0); | |
922 | if (IS_ERR(lp)) | |
923 | return PTR_ERR(lp); | |
924 | break; | |
925 | } | |
926 | dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty, | |
927 | lp->free, lp->flags); | |
6eb61d58 RW |
928 | ubifs_assert(c, lp->flags & LPROPS_TAKEN); |
929 | ubifs_assert(c, lp->flags & LPROPS_INDEX); | |
1e51764a AB |
930 | return lnum; |
931 | } | |
932 | ||
933 | /** | |
934 | * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit. | |
935 | * @c: the UBIFS file-system description object | |
936 | * | |
937 | * This function attempts to find an untaken index LEB with the most free and | |
938 | * dirty space that can be used without overwriting index nodes that were in the | |
939 | * last index committed. | |
940 | */ | |
941 | int ubifs_find_dirty_idx_leb(struct ubifs_info *c) | |
942 | { | |
943 | int err; | |
944 | ||
945 | ubifs_get_lprops(c); | |
946 | ||
947 | /* | |
948 | * We made an array of the dirtiest index LEB numbers as at the start of | |
949 | * last commit. Try that array first. | |
950 | */ | |
951 | err = find_dirtiest_idx_leb(c); | |
952 | ||
953 | /* Next try scanning the entire LPT */ | |
954 | if (err == -ENOSPC) | |
955 | err = find_dirty_idx_leb(c); | |
956 | ||
957 | /* Finally take any index LEBs awaiting trivial GC */ | |
958 | if (err == -ENOSPC) | |
959 | err = get_idx_gc_leb(c); | |
960 | ||
961 | ubifs_release_lprops(c); | |
962 | return err; | |
963 | } |