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