]>
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 | /* | |
b364b41a | 293 | * Since we reserve trice as more space for the index than it |
1e51764a | 294 | * actually takes, it does not make sense to pick indexing LEBs |
b364b41a AB |
295 | * with less than, say, half LEB of dirty space. May be half is |
296 | * not the optimal boundary - this should be tested and | |
297 | * checked. This boundary should determine how much we use | |
298 | * in-the-gaps to consolidate the index comparing to how much | |
299 | * we use garbage collector to consolidate it. The "half" | |
300 | * criteria just feels to be fine. | |
1e51764a AB |
301 | */ |
302 | if (sum < min_space || sum < c->half_leb_size) | |
303 | idx_lp = NULL; | |
304 | } | |
305 | ||
306 | if (heap->cnt) { | |
307 | lp = heap->arr[0]; | |
308 | if (lp->dirty + lp->free < min_space) | |
309 | lp = NULL; | |
310 | } | |
311 | ||
312 | /* Pick the LEB with most space */ | |
313 | if (idx_lp && lp) { | |
314 | if (idx_lp->free + idx_lp->dirty >= lp->free + lp->dirty) | |
315 | lp = idx_lp; | |
316 | } else if (idx_lp && !lp) | |
317 | lp = idx_lp; | |
318 | ||
319 | if (lp) { | |
320 | ubifs_assert(lp->dirty >= c->dead_wm); | |
321 | goto found; | |
322 | } | |
323 | ||
324 | /* Did not find a dirty LEB on the dirty heaps, have to scan */ | |
325 | dbg_find("scanning LPT for a dirty LEB"); | |
326 | lp = scan_for_dirty(c, min_space, pick_free, exclude_index); | |
327 | if (IS_ERR(lp)) { | |
328 | err = PTR_ERR(lp); | |
329 | goto out; | |
330 | } | |
331 | ubifs_assert(lp->dirty >= c->dead_wm || | |
332 | (pick_free && lp->free + lp->dirty == c->leb_size)); | |
333 | ||
334 | found: | |
335 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x", | |
336 | lp->lnum, lp->free, lp->dirty, lp->flags); | |
337 | ||
338 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
339 | lp->flags | LPROPS_TAKEN, 0); | |
340 | if (IS_ERR(lp)) { | |
341 | err = PTR_ERR(lp); | |
342 | goto out; | |
343 | } | |
344 | ||
345 | memcpy(ret_lp, lp, sizeof(struct ubifs_lprops)); | |
346 | ||
347 | out: | |
348 | ubifs_release_lprops(c); | |
349 | return err; | |
350 | } | |
351 | ||
352 | /** | |
353 | * scan_for_free_cb - free space scan callback. | |
354 | * @c: the UBIFS file-system description object | |
355 | * @lprops: LEB properties to scan | |
356 | * @in_tree: whether the LEB properties are in main memory | |
357 | * @data: information passed to and from the caller of the scan | |
358 | * | |
359 | * This function returns a code that indicates whether the scan should continue | |
360 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
361 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
362 | * (%LPT_SCAN_STOP). | |
363 | */ | |
364 | static int scan_for_free_cb(struct ubifs_info *c, | |
365 | const struct ubifs_lprops *lprops, int in_tree, | |
366 | struct scan_data *data) | |
367 | { | |
368 | int ret = LPT_SCAN_CONTINUE; | |
369 | ||
370 | /* Exclude LEBs that are currently in use */ | |
371 | if (lprops->flags & LPROPS_TAKEN) | |
372 | return LPT_SCAN_CONTINUE; | |
373 | /* Determine whether to add these LEB properties to the tree */ | |
374 | if (!in_tree && valuable(c, lprops)) | |
375 | ret |= LPT_SCAN_ADD; | |
376 | /* Exclude index LEBs */ | |
377 | if (lprops->flags & LPROPS_INDEX) | |
378 | return ret; | |
379 | /* Exclude LEBs with too little space */ | |
380 | if (lprops->free < data->min_space) | |
381 | return ret; | |
382 | /* If specified, exclude empty LEBs */ | |
383 | if (!data->pick_free && lprops->free == c->leb_size) | |
384 | return ret; | |
385 | /* | |
386 | * LEBs that have only free and dirty space must not be allocated | |
387 | * because they may have been unmapped already or they may have data | |
388 | * that is obsolete only because of nodes that are still sitting in a | |
389 | * wbuf. | |
390 | */ | |
391 | if (lprops->free + lprops->dirty == c->leb_size && lprops->dirty > 0) | |
392 | return ret; | |
393 | /* Finally we found space */ | |
394 | data->lnum = lprops->lnum; | |
395 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
396 | } | |
397 | ||
398 | /** | |
399 | * do_find_free_space - find a data LEB with free space. | |
400 | * @c: the UBIFS file-system description object | |
401 | * @min_space: minimum amount of free space required | |
402 | * @pick_free: whether it is OK to scan for empty LEBs | |
403 | * @squeeze: whether to try to find space in a non-empty LEB first | |
404 | * | |
405 | * This function returns a pointer to the LEB properties found or a negative | |
406 | * error code. | |
407 | */ | |
408 | static | |
409 | const struct ubifs_lprops *do_find_free_space(struct ubifs_info *c, | |
410 | int min_space, int pick_free, | |
411 | int squeeze) | |
412 | { | |
413 | const struct ubifs_lprops *lprops; | |
414 | struct ubifs_lpt_heap *heap; | |
415 | struct scan_data data; | |
416 | int err, i; | |
417 | ||
418 | if (squeeze) { | |
419 | lprops = ubifs_fast_find_free(c); | |
420 | if (lprops && lprops->free >= min_space) | |
421 | return lprops; | |
422 | } | |
423 | if (pick_free) { | |
424 | lprops = ubifs_fast_find_empty(c); | |
425 | if (lprops) | |
426 | return lprops; | |
427 | } | |
428 | if (!squeeze) { | |
429 | lprops = ubifs_fast_find_free(c); | |
430 | if (lprops && lprops->free >= min_space) | |
431 | return lprops; | |
432 | } | |
433 | /* There may be an LEB with enough free space on the dirty heap */ | |
434 | heap = &c->lpt_heap[LPROPS_DIRTY - 1]; | |
435 | for (i = 0; i < heap->cnt; i++) { | |
436 | lprops = heap->arr[i]; | |
437 | if (lprops->free >= min_space) | |
438 | return lprops; | |
439 | } | |
440 | /* | |
441 | * A LEB may have fallen off of the bottom of the free heap, and ended | |
442 | * up as uncategorized even though it has enough free space for us now, | |
443 | * so check the uncategorized list. N.B. neither empty nor freeable LEBs | |
444 | * can end up as uncategorized because they are kept on lists not | |
445 | * finite-sized heaps. | |
446 | */ | |
447 | list_for_each_entry(lprops, &c->uncat_list, list) { | |
448 | if (lprops->flags & LPROPS_TAKEN) | |
449 | continue; | |
450 | if (lprops->flags & LPROPS_INDEX) | |
451 | continue; | |
452 | if (lprops->free >= min_space) | |
453 | return lprops; | |
454 | } | |
455 | /* We have looked everywhere in main memory, now scan the flash */ | |
456 | if (c->pnodes_have >= c->pnode_cnt) | |
457 | /* All pnodes are in memory, so skip scan */ | |
458 | return ERR_PTR(-ENOSPC); | |
459 | data.min_space = min_space; | |
460 | data.pick_free = pick_free; | |
461 | data.lnum = -1; | |
462 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
463 | (ubifs_lpt_scan_callback)scan_for_free_cb, | |
464 | &data); | |
465 | if (err) | |
466 | return ERR_PTR(err); | |
467 | ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); | |
468 | c->lscan_lnum = data.lnum; | |
469 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
470 | if (IS_ERR(lprops)) | |
471 | return lprops; | |
472 | ubifs_assert(lprops->lnum == data.lnum); | |
473 | ubifs_assert(lprops->free >= min_space); | |
474 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
475 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
476 | return lprops; | |
477 | } | |
478 | ||
479 | /** | |
480 | * ubifs_find_free_space - find a data LEB with free space. | |
481 | * @c: the UBIFS file-system description object | |
482 | * @min_space: minimum amount of required free space | |
483 | * @free: contains amount of free space in the LEB on exit | |
484 | * @squeeze: whether to try to find space in a non-empty LEB first | |
485 | * | |
486 | * This function looks for an LEB with at least @min_space bytes of free space. | |
487 | * It tries to find an empty LEB if possible. If no empty LEBs are available, | |
488 | * this function searches for a non-empty data LEB. The returned LEB is marked | |
489 | * as "taken". | |
490 | * | |
491 | * This function returns found LEB number in case of success, %-ENOSPC if it | |
492 | * failed to find a LEB with @min_space bytes of free space and other a negative | |
493 | * error codes in case of failure. | |
494 | */ | |
495 | int ubifs_find_free_space(struct ubifs_info *c, int min_space, int *free, | |
496 | int squeeze) | |
497 | { | |
498 | const struct ubifs_lprops *lprops; | |
499 | int lebs, rsvd_idx_lebs, pick_free = 0, err, lnum, flags; | |
500 | ||
501 | dbg_find("min_space %d", min_space); | |
502 | ubifs_get_lprops(c); | |
503 | ||
504 | /* Check if there are enough empty LEBs for commit */ | |
505 | spin_lock(&c->space_lock); | |
506 | if (c->min_idx_lebs > c->lst.idx_lebs) | |
507 | rsvd_idx_lebs = c->min_idx_lebs - c->lst.idx_lebs; | |
508 | else | |
509 | rsvd_idx_lebs = 0; | |
510 | lebs = c->lst.empty_lebs + c->freeable_cnt + c->idx_gc_cnt - | |
511 | c->lst.taken_empty_lebs; | |
512 | ubifs_assert(lebs + c->lst.idx_lebs >= c->min_idx_lebs); | |
513 | if (rsvd_idx_lebs < lebs) | |
514 | /* | |
515 | * OK to allocate an empty LEB, but we still don't want to go | |
516 | * looking for one if there aren't any. | |
517 | */ | |
518 | if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { | |
519 | pick_free = 1; | |
520 | /* | |
521 | * Because we release the space lock, we must account | |
522 | * for this allocation here. After the LEB properties | |
523 | * flags have been updated, we subtract one. Note, the | |
524 | * result of this is that lprops also decreases | |
525 | * @taken_empty_lebs in 'ubifs_change_lp()', so it is | |
526 | * off by one for a short period of time which may | |
527 | * introduce a small disturbance to budgeting | |
528 | * calculations, but this is harmless because at the | |
529 | * worst case this would make the budgeting subsystem | |
530 | * be more pessimistic than needed. | |
531 | * | |
532 | * Fundamentally, this is about serialization of the | |
533 | * budgeting and lprops subsystems. We could make the | |
534 | * @space_lock a mutex and avoid dropping it before | |
535 | * calling 'ubifs_change_lp()', but mutex is more | |
536 | * heavy-weight, and we want budgeting to be as fast as | |
537 | * possible. | |
538 | */ | |
539 | c->lst.taken_empty_lebs += 1; | |
540 | } | |
541 | spin_unlock(&c->space_lock); | |
542 | ||
543 | lprops = do_find_free_space(c, min_space, pick_free, squeeze); | |
544 | if (IS_ERR(lprops)) { | |
545 | err = PTR_ERR(lprops); | |
546 | goto out; | |
547 | } | |
548 | ||
549 | lnum = lprops->lnum; | |
550 | flags = lprops->flags | LPROPS_TAKEN; | |
551 | ||
552 | lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, flags, 0); | |
553 | if (IS_ERR(lprops)) { | |
554 | err = PTR_ERR(lprops); | |
555 | goto out; | |
556 | } | |
557 | ||
558 | if (pick_free) { | |
559 | spin_lock(&c->space_lock); | |
560 | c->lst.taken_empty_lebs -= 1; | |
561 | spin_unlock(&c->space_lock); | |
562 | } | |
563 | ||
564 | *free = lprops->free; | |
565 | ubifs_release_lprops(c); | |
566 | ||
567 | if (*free == c->leb_size) { | |
568 | /* | |
569 | * Ensure that empty LEBs have been unmapped. They may not have | |
570 | * been, for example, because of an unclean unmount. Also | |
571 | * LEBs that were freeable LEBs (free + dirty == leb_size) will | |
572 | * not have been unmapped. | |
573 | */ | |
574 | err = ubifs_leb_unmap(c, lnum); | |
575 | if (err) | |
576 | return err; | |
577 | } | |
578 | ||
579 | dbg_find("found LEB %d, free %d", lnum, *free); | |
580 | ubifs_assert(*free >= min_space); | |
581 | return lnum; | |
582 | ||
583 | out: | |
584 | if (pick_free) { | |
585 | spin_lock(&c->space_lock); | |
586 | c->lst.taken_empty_lebs -= 1; | |
587 | spin_unlock(&c->space_lock); | |
588 | } | |
589 | ubifs_release_lprops(c); | |
590 | return err; | |
591 | } | |
592 | ||
593 | /** | |
594 | * scan_for_idx_cb - callback used by the scan for a free LEB for the index. | |
595 | * @c: the UBIFS file-system description object | |
596 | * @lprops: LEB properties to scan | |
597 | * @in_tree: whether the LEB properties are in main memory | |
598 | * @data: information passed to and from the caller of the scan | |
599 | * | |
600 | * This function returns a code that indicates whether the scan should continue | |
601 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
602 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
603 | * (%LPT_SCAN_STOP). | |
604 | */ | |
605 | static int scan_for_idx_cb(struct ubifs_info *c, | |
606 | const struct ubifs_lprops *lprops, int in_tree, | |
607 | struct scan_data *data) | |
608 | { | |
609 | int ret = LPT_SCAN_CONTINUE; | |
610 | ||
611 | /* Exclude LEBs that are currently in use */ | |
612 | if (lprops->flags & LPROPS_TAKEN) | |
613 | return LPT_SCAN_CONTINUE; | |
614 | /* Determine whether to add these LEB properties to the tree */ | |
615 | if (!in_tree && valuable(c, lprops)) | |
616 | ret |= LPT_SCAN_ADD; | |
617 | /* Exclude index LEBS */ | |
618 | if (lprops->flags & LPROPS_INDEX) | |
619 | return ret; | |
620 | /* Exclude LEBs that cannot be made empty */ | |
621 | if (lprops->free + lprops->dirty != c->leb_size) | |
622 | return ret; | |
623 | /* | |
624 | * We are allocating for the index so it is safe to allocate LEBs with | |
625 | * only free and dirty space, because write buffers are sync'd at commit | |
626 | * start. | |
627 | */ | |
628 | data->lnum = lprops->lnum; | |
629 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
630 | } | |
631 | ||
632 | /** | |
633 | * scan_for_leb_for_idx - scan for a free LEB for the index. | |
634 | * @c: the UBIFS file-system description object | |
635 | */ | |
636 | static const struct ubifs_lprops *scan_for_leb_for_idx(struct ubifs_info *c) | |
637 | { | |
638 | struct ubifs_lprops *lprops; | |
639 | struct scan_data data; | |
640 | int err; | |
641 | ||
642 | data.lnum = -1; | |
643 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
644 | (ubifs_lpt_scan_callback)scan_for_idx_cb, | |
645 | &data); | |
646 | if (err) | |
647 | return ERR_PTR(err); | |
648 | ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); | |
649 | c->lscan_lnum = data.lnum; | |
650 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
651 | if (IS_ERR(lprops)) | |
652 | return lprops; | |
653 | ubifs_assert(lprops->lnum == data.lnum); | |
654 | ubifs_assert(lprops->free + lprops->dirty == c->leb_size); | |
655 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
656 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
657 | return lprops; | |
658 | } | |
659 | ||
660 | /** | |
661 | * ubifs_find_free_leb_for_idx - find a free LEB for the index. | |
662 | * @c: the UBIFS file-system description object | |
663 | * | |
664 | * This function looks for a free LEB and returns that LEB number. The returned | |
665 | * LEB is marked as "taken", "index". | |
666 | * | |
667 | * Only empty LEBs are allocated. This is for two reasons. First, the commit | |
668 | * calculates the number of LEBs to allocate based on the assumption that they | |
669 | * will be empty. Secondly, free space at the end of an index LEB is not | |
670 | * guaranteed to be empty because it may have been used by the in-the-gaps | |
671 | * method prior to an unclean unmount. | |
672 | * | |
673 | * If no LEB is found %-ENOSPC is returned. For other failures another negative | |
674 | * error code is returned. | |
675 | */ | |
676 | int ubifs_find_free_leb_for_idx(struct ubifs_info *c) | |
677 | { | |
678 | const struct ubifs_lprops *lprops; | |
679 | int lnum = -1, err, flags; | |
680 | ||
681 | ubifs_get_lprops(c); | |
682 | ||
683 | lprops = ubifs_fast_find_empty(c); | |
684 | if (!lprops) { | |
685 | lprops = ubifs_fast_find_freeable(c); | |
686 | if (!lprops) { | |
687 | ubifs_assert(c->freeable_cnt == 0); | |
688 | if (c->lst.empty_lebs - c->lst.taken_empty_lebs > 0) { | |
689 | lprops = scan_for_leb_for_idx(c); | |
690 | if (IS_ERR(lprops)) { | |
691 | err = PTR_ERR(lprops); | |
692 | goto out; | |
693 | } | |
694 | } | |
695 | } | |
696 | } | |
697 | ||
698 | if (!lprops) { | |
699 | err = -ENOSPC; | |
700 | goto out; | |
701 | } | |
702 | ||
703 | lnum = lprops->lnum; | |
704 | ||
705 | dbg_find("found LEB %d, free %d, dirty %d, flags %#x", | |
706 | lnum, lprops->free, lprops->dirty, lprops->flags); | |
707 | ||
708 | flags = lprops->flags | LPROPS_TAKEN | LPROPS_INDEX; | |
709 | lprops = ubifs_change_lp(c, lprops, c->leb_size, 0, flags, 0); | |
710 | if (IS_ERR(lprops)) { | |
711 | err = PTR_ERR(lprops); | |
712 | goto out; | |
713 | } | |
714 | ||
715 | ubifs_release_lprops(c); | |
716 | ||
717 | /* | |
718 | * Ensure that empty LEBs have been unmapped. They may not have been, | |
719 | * for example, because of an unclean unmount. Also LEBs that were | |
720 | * freeable LEBs (free + dirty == leb_size) will not have been unmapped. | |
721 | */ | |
722 | err = ubifs_leb_unmap(c, lnum); | |
723 | if (err) { | |
724 | ubifs_change_one_lp(c, lnum, LPROPS_NC, LPROPS_NC, 0, | |
725 | LPROPS_TAKEN | LPROPS_INDEX, 0); | |
726 | return err; | |
727 | } | |
728 | ||
729 | return lnum; | |
730 | ||
731 | out: | |
732 | ubifs_release_lprops(c); | |
733 | return err; | |
734 | } | |
735 | ||
736 | static int cmp_dirty_idx(const struct ubifs_lprops **a, | |
737 | const struct ubifs_lprops **b) | |
738 | { | |
739 | const struct ubifs_lprops *lpa = *a; | |
740 | const struct ubifs_lprops *lpb = *b; | |
741 | ||
742 | return lpa->dirty + lpa->free - lpb->dirty - lpb->free; | |
743 | } | |
744 | ||
745 | static void swap_dirty_idx(struct ubifs_lprops **a, struct ubifs_lprops **b, | |
746 | int size) | |
747 | { | |
748 | struct ubifs_lprops *t = *a; | |
749 | ||
750 | *a = *b; | |
751 | *b = t; | |
752 | } | |
753 | ||
754 | /** | |
755 | * ubifs_save_dirty_idx_lnums - save an array of the most dirty index LEB nos. | |
756 | * @c: the UBIFS file-system description object | |
757 | * | |
758 | * This function is called each commit to create an array of LEB numbers of | |
759 | * dirty index LEBs sorted in order of dirty and free space. This is used by | |
760 | * the in-the-gaps method of TNC commit. | |
761 | */ | |
762 | int ubifs_save_dirty_idx_lnums(struct ubifs_info *c) | |
763 | { | |
764 | int i; | |
765 | ||
766 | ubifs_get_lprops(c); | |
767 | /* Copy the LPROPS_DIRTY_IDX heap */ | |
768 | c->dirty_idx.cnt = c->lpt_heap[LPROPS_DIRTY_IDX - 1].cnt; | |
769 | memcpy(c->dirty_idx.arr, c->lpt_heap[LPROPS_DIRTY_IDX - 1].arr, | |
770 | sizeof(void *) * c->dirty_idx.cnt); | |
771 | /* Sort it so that the dirtiest is now at the end */ | |
772 | sort(c->dirty_idx.arr, c->dirty_idx.cnt, sizeof(void *), | |
773 | (int (*)(const void *, const void *))cmp_dirty_idx, | |
774 | (void (*)(void *, void *, int))swap_dirty_idx); | |
775 | dbg_find("found %d dirty index LEBs", c->dirty_idx.cnt); | |
776 | if (c->dirty_idx.cnt) | |
777 | dbg_find("dirtiest index LEB is %d with dirty %d and free %d", | |
778 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->lnum, | |
779 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->dirty, | |
780 | c->dirty_idx.arr[c->dirty_idx.cnt - 1]->free); | |
781 | /* Replace the lprops pointers with LEB numbers */ | |
782 | for (i = 0; i < c->dirty_idx.cnt; i++) | |
783 | c->dirty_idx.arr[i] = (void *)(size_t)c->dirty_idx.arr[i]->lnum; | |
784 | ubifs_release_lprops(c); | |
785 | return 0; | |
786 | } | |
787 | ||
788 | /** | |
789 | * scan_dirty_idx_cb - callback used by the scan for a dirty index LEB. | |
790 | * @c: the UBIFS file-system description object | |
791 | * @lprops: LEB properties to scan | |
792 | * @in_tree: whether the LEB properties are in main memory | |
793 | * @data: information passed to and from the caller of the scan | |
794 | * | |
795 | * This function returns a code that indicates whether the scan should continue | |
796 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
797 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
798 | * (%LPT_SCAN_STOP). | |
799 | */ | |
800 | static int scan_dirty_idx_cb(struct ubifs_info *c, | |
801 | const struct ubifs_lprops *lprops, int in_tree, | |
802 | struct scan_data *data) | |
803 | { | |
804 | int ret = LPT_SCAN_CONTINUE; | |
805 | ||
806 | /* Exclude LEBs that are currently in use */ | |
807 | if (lprops->flags & LPROPS_TAKEN) | |
808 | return LPT_SCAN_CONTINUE; | |
809 | /* Determine whether to add these LEB properties to the tree */ | |
810 | if (!in_tree && valuable(c, lprops)) | |
811 | ret |= LPT_SCAN_ADD; | |
812 | /* Exclude non-index LEBs */ | |
813 | if (!(lprops->flags & LPROPS_INDEX)) | |
814 | return ret; | |
815 | /* Exclude LEBs with too little space */ | |
816 | if (lprops->free + lprops->dirty < c->min_idx_node_sz) | |
817 | return ret; | |
818 | /* Finally we found space */ | |
819 | data->lnum = lprops->lnum; | |
820 | return LPT_SCAN_ADD | LPT_SCAN_STOP; | |
821 | } | |
822 | ||
823 | /** | |
824 | * find_dirty_idx_leb - find a dirty index LEB. | |
825 | * @c: the UBIFS file-system description object | |
826 | * | |
827 | * This function returns LEB number upon success and a negative error code upon | |
828 | * failure. In particular, -ENOSPC is returned if a dirty index LEB is not | |
829 | * found. | |
830 | * | |
831 | * Note that this function scans the entire LPT but it is called very rarely. | |
832 | */ | |
833 | static int find_dirty_idx_leb(struct ubifs_info *c) | |
834 | { | |
835 | const struct ubifs_lprops *lprops; | |
836 | struct ubifs_lpt_heap *heap; | |
837 | struct scan_data data; | |
838 | int err, i, ret; | |
839 | ||
840 | /* Check all structures in memory first */ | |
841 | data.lnum = -1; | |
842 | heap = &c->lpt_heap[LPROPS_DIRTY_IDX - 1]; | |
843 | for (i = 0; i < heap->cnt; i++) { | |
844 | lprops = heap->arr[i]; | |
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->frdi_idx_list, list) { | |
850 | ret = scan_dirty_idx_cb(c, lprops, 1, &data); | |
851 | if (ret & LPT_SCAN_STOP) | |
852 | goto found; | |
853 | } | |
854 | list_for_each_entry(lprops, &c->uncat_list, list) { | |
855 | ret = scan_dirty_idx_cb(c, lprops, 1, &data); | |
856 | if (ret & LPT_SCAN_STOP) | |
857 | goto found; | |
858 | } | |
859 | if (c->pnodes_have >= c->pnode_cnt) | |
860 | /* All pnodes are in memory, so skip scan */ | |
861 | return -ENOSPC; | |
862 | err = ubifs_lpt_scan_nolock(c, -1, c->lscan_lnum, | |
863 | (ubifs_lpt_scan_callback)scan_dirty_idx_cb, | |
864 | &data); | |
865 | if (err) | |
866 | return err; | |
867 | found: | |
868 | ubifs_assert(data.lnum >= c->main_first && data.lnum < c->leb_cnt); | |
869 | c->lscan_lnum = data.lnum; | |
870 | lprops = ubifs_lpt_lookup_dirty(c, data.lnum); | |
871 | if (IS_ERR(lprops)) | |
872 | return PTR_ERR(lprops); | |
873 | ubifs_assert(lprops->lnum == data.lnum); | |
874 | ubifs_assert(lprops->free + lprops->dirty >= c->min_idx_node_sz); | |
875 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
876 | ubifs_assert((lprops->flags & LPROPS_INDEX)); | |
877 | ||
878 | dbg_find("found dirty LEB %d, free %d, dirty %d, flags %#x", | |
879 | lprops->lnum, lprops->free, lprops->dirty, lprops->flags); | |
880 | ||
881 | lprops = ubifs_change_lp(c, lprops, LPROPS_NC, LPROPS_NC, | |
882 | lprops->flags | LPROPS_TAKEN, 0); | |
883 | if (IS_ERR(lprops)) | |
884 | return PTR_ERR(lprops); | |
885 | ||
886 | return lprops->lnum; | |
887 | } | |
888 | ||
889 | /** | |
890 | * get_idx_gc_leb - try to get a LEB number from trivial GC. | |
891 | * @c: the UBIFS file-system description object | |
892 | */ | |
893 | static int get_idx_gc_leb(struct ubifs_info *c) | |
894 | { | |
895 | const struct ubifs_lprops *lp; | |
896 | int err, lnum; | |
897 | ||
898 | err = ubifs_get_idx_gc_leb(c); | |
899 | if (err < 0) | |
900 | return err; | |
901 | lnum = err; | |
902 | /* | |
903 | * The LEB was due to be unmapped after the commit but | |
904 | * it is needed now for this commit. | |
905 | */ | |
906 | lp = ubifs_lpt_lookup_dirty(c, lnum); | |
907 | if (unlikely(IS_ERR(lp))) | |
908 | return PTR_ERR(lp); | |
909 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
910 | lp->flags | LPROPS_INDEX, -1); | |
911 | if (unlikely(IS_ERR(lp))) | |
912 | return PTR_ERR(lp); | |
913 | dbg_find("LEB %d, dirty %d and free %d flags %#x", | |
914 | lp->lnum, lp->dirty, lp->free, lp->flags); | |
915 | return lnum; | |
916 | } | |
917 | ||
918 | /** | |
919 | * find_dirtiest_idx_leb - find dirtiest index LEB from dirtiest array. | |
920 | * @c: the UBIFS file-system description object | |
921 | */ | |
922 | static int find_dirtiest_idx_leb(struct ubifs_info *c) | |
923 | { | |
924 | const struct ubifs_lprops *lp; | |
925 | int lnum; | |
926 | ||
927 | while (1) { | |
928 | if (!c->dirty_idx.cnt) | |
929 | return -ENOSPC; | |
930 | /* The lprops pointers were replaced by LEB numbers */ | |
931 | lnum = (size_t)c->dirty_idx.arr[--c->dirty_idx.cnt]; | |
932 | lp = ubifs_lpt_lookup(c, lnum); | |
933 | if (IS_ERR(lp)) | |
934 | return PTR_ERR(lp); | |
935 | if ((lp->flags & LPROPS_TAKEN) || !(lp->flags & LPROPS_INDEX)) | |
936 | continue; | |
937 | lp = ubifs_change_lp(c, lp, LPROPS_NC, LPROPS_NC, | |
938 | lp->flags | LPROPS_TAKEN, 0); | |
939 | if (IS_ERR(lp)) | |
940 | return PTR_ERR(lp); | |
941 | break; | |
942 | } | |
943 | dbg_find("LEB %d, dirty %d and free %d flags %#x", lp->lnum, lp->dirty, | |
944 | lp->free, lp->flags); | |
945 | ubifs_assert(lp->flags | LPROPS_TAKEN); | |
946 | ubifs_assert(lp->flags | LPROPS_INDEX); | |
947 | return lnum; | |
948 | } | |
949 | ||
950 | /** | |
951 | * ubifs_find_dirty_idx_leb - try to find dirtiest index LEB as at last commit. | |
952 | * @c: the UBIFS file-system description object | |
953 | * | |
954 | * This function attempts to find an untaken index LEB with the most free and | |
955 | * dirty space that can be used without overwriting index nodes that were in the | |
956 | * last index committed. | |
957 | */ | |
958 | int ubifs_find_dirty_idx_leb(struct ubifs_info *c) | |
959 | { | |
960 | int err; | |
961 | ||
962 | ubifs_get_lprops(c); | |
963 | ||
964 | /* | |
965 | * We made an array of the dirtiest index LEB numbers as at the start of | |
966 | * last commit. Try that array first. | |
967 | */ | |
968 | err = find_dirtiest_idx_leb(c); | |
969 | ||
970 | /* Next try scanning the entire LPT */ | |
971 | if (err == -ENOSPC) | |
972 | err = find_dirty_idx_leb(c); | |
973 | ||
974 | /* Finally take any index LEBs awaiting trivial GC */ | |
975 | if (err == -ENOSPC) | |
976 | err = get_idx_gc_leb(c); | |
977 | ||
978 | ubifs_release_lprops(c); | |
979 | return err; | |
980 | } |