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