]>
Commit | Line | Data |
---|---|---|
9eefe2a2 SR |
1 | /* |
2 | * This file is part of UBIFS. | |
3 | * | |
4 | * Copyright (C) 2006-2008 Nokia Corporation. | |
5 | * | |
ff94bc40 | 6 | * SPDX-License-Identifier: GPL-2.0+ |
9eefe2a2 SR |
7 | * |
8 | * Authors: Adrian Hunter | |
9 | * Artem Bityutskiy (Битюцкий Артём) | |
10 | */ | |
11 | ||
12 | /* | |
13 | * This file implements the functions that access LEB properties and their | |
14 | * categories. LEBs are categorized based on the needs of UBIFS, and the | |
15 | * categories are stored as either heaps or lists to provide a fast way of | |
16 | * finding a LEB in a particular category. For example, UBIFS may need to find | |
17 | * an empty LEB for the journal, or a very dirty LEB for garbage collection. | |
18 | */ | |
19 | ||
ff94bc40 HS |
20 | #define __UBOOT__ |
21 | #ifdef __UBOOT__ | |
22 | #include <linux/err.h> | |
23 | #endif | |
9eefe2a2 SR |
24 | #include "ubifs.h" |
25 | ||
26 | /** | |
27 | * get_heap_comp_val - get the LEB properties value for heap comparisons. | |
28 | * @lprops: LEB properties | |
29 | * @cat: LEB category | |
30 | */ | |
31 | static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat) | |
32 | { | |
33 | switch (cat) { | |
34 | case LPROPS_FREE: | |
35 | return lprops->free; | |
36 | case LPROPS_DIRTY_IDX: | |
37 | return lprops->free + lprops->dirty; | |
38 | default: | |
39 | return lprops->dirty; | |
40 | } | |
41 | } | |
42 | ||
43 | /** | |
44 | * move_up_lpt_heap - move a new heap entry up as far as possible. | |
45 | * @c: UBIFS file-system description object | |
46 | * @heap: LEB category heap | |
47 | * @lprops: LEB properties to move | |
48 | * @cat: LEB category | |
49 | * | |
50 | * New entries to a heap are added at the bottom and then moved up until the | |
51 | * parent's value is greater. In the case of LPT's category heaps, the value | |
52 | * is either the amount of free space or the amount of dirty space, depending | |
53 | * on the category. | |
54 | */ | |
55 | static void move_up_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, | |
56 | struct ubifs_lprops *lprops, int cat) | |
57 | { | |
58 | int val1, val2, hpos; | |
59 | ||
60 | hpos = lprops->hpos; | |
61 | if (!hpos) | |
62 | return; /* Already top of the heap */ | |
63 | val1 = get_heap_comp_val(lprops, cat); | |
64 | /* Compare to parent and, if greater, move up the heap */ | |
65 | do { | |
66 | int ppos = (hpos - 1) / 2; | |
67 | ||
68 | val2 = get_heap_comp_val(heap->arr[ppos], cat); | |
69 | if (val2 >= val1) | |
70 | return; | |
71 | /* Greater than parent so move up */ | |
72 | heap->arr[ppos]->hpos = hpos; | |
73 | heap->arr[hpos] = heap->arr[ppos]; | |
74 | heap->arr[ppos] = lprops; | |
75 | lprops->hpos = ppos; | |
76 | hpos = ppos; | |
77 | } while (hpos); | |
78 | } | |
79 | ||
80 | /** | |
81 | * adjust_lpt_heap - move a changed heap entry up or down the heap. | |
82 | * @c: UBIFS file-system description object | |
83 | * @heap: LEB category heap | |
84 | * @lprops: LEB properties to move | |
85 | * @hpos: heap position of @lprops | |
86 | * @cat: LEB category | |
87 | * | |
88 | * Changed entries in a heap are moved up or down until the parent's value is | |
89 | * greater. In the case of LPT's category heaps, the value is either the amount | |
90 | * of free space or the amount of dirty space, depending on the category. | |
91 | */ | |
92 | static void adjust_lpt_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, | |
93 | struct ubifs_lprops *lprops, int hpos, int cat) | |
94 | { | |
95 | int val1, val2, val3, cpos; | |
96 | ||
97 | val1 = get_heap_comp_val(lprops, cat); | |
98 | /* Compare to parent and, if greater than parent, move up the heap */ | |
99 | if (hpos) { | |
100 | int ppos = (hpos - 1) / 2; | |
101 | ||
102 | val2 = get_heap_comp_val(heap->arr[ppos], cat); | |
103 | if (val1 > val2) { | |
104 | /* Greater than parent so move up */ | |
105 | while (1) { | |
106 | heap->arr[ppos]->hpos = hpos; | |
107 | heap->arr[hpos] = heap->arr[ppos]; | |
108 | heap->arr[ppos] = lprops; | |
109 | lprops->hpos = ppos; | |
110 | hpos = ppos; | |
111 | if (!hpos) | |
112 | return; | |
113 | ppos = (hpos - 1) / 2; | |
114 | val2 = get_heap_comp_val(heap->arr[ppos], cat); | |
115 | if (val1 <= val2) | |
116 | return; | |
117 | /* Still greater than parent so keep going */ | |
118 | } | |
119 | } | |
120 | } | |
121 | ||
122 | /* Not greater than parent, so compare to children */ | |
123 | while (1) { | |
124 | /* Compare to left child */ | |
125 | cpos = hpos * 2 + 1; | |
126 | if (cpos >= heap->cnt) | |
127 | return; | |
128 | val2 = get_heap_comp_val(heap->arr[cpos], cat); | |
129 | if (val1 < val2) { | |
130 | /* Less than left child, so promote biggest child */ | |
131 | if (cpos + 1 < heap->cnt) { | |
132 | val3 = get_heap_comp_val(heap->arr[cpos + 1], | |
133 | cat); | |
134 | if (val3 > val2) | |
135 | cpos += 1; /* Right child is bigger */ | |
136 | } | |
137 | heap->arr[cpos]->hpos = hpos; | |
138 | heap->arr[hpos] = heap->arr[cpos]; | |
139 | heap->arr[cpos] = lprops; | |
140 | lprops->hpos = cpos; | |
141 | hpos = cpos; | |
142 | continue; | |
143 | } | |
144 | /* Compare to right child */ | |
145 | cpos += 1; | |
146 | if (cpos >= heap->cnt) | |
147 | return; | |
148 | val3 = get_heap_comp_val(heap->arr[cpos], cat); | |
149 | if (val1 < val3) { | |
150 | /* Less than right child, so promote right child */ | |
151 | heap->arr[cpos]->hpos = hpos; | |
152 | heap->arr[hpos] = heap->arr[cpos]; | |
153 | heap->arr[cpos] = lprops; | |
154 | lprops->hpos = cpos; | |
155 | hpos = cpos; | |
156 | continue; | |
157 | } | |
158 | return; | |
159 | } | |
160 | } | |
161 | ||
162 | /** | |
163 | * add_to_lpt_heap - add LEB properties to a LEB category heap. | |
164 | * @c: UBIFS file-system description object | |
165 | * @lprops: LEB properties to add | |
166 | * @cat: LEB category | |
167 | * | |
168 | * This function returns %1 if @lprops is added to the heap for LEB category | |
169 | * @cat, otherwise %0 is returned because the heap is full. | |
170 | */ | |
171 | static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops, | |
172 | int cat) | |
173 | { | |
174 | struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1]; | |
175 | ||
176 | if (heap->cnt >= heap->max_cnt) { | |
177 | const int b = LPT_HEAP_SZ / 2 - 1; | |
178 | int cpos, val1, val2; | |
179 | ||
180 | /* Compare to some other LEB on the bottom of heap */ | |
181 | /* Pick a position kind of randomly */ | |
182 | cpos = (((size_t)lprops >> 4) & b) + b; | |
183 | ubifs_assert(cpos >= b); | |
184 | ubifs_assert(cpos < LPT_HEAP_SZ); | |
185 | ubifs_assert(cpos < heap->cnt); | |
186 | ||
187 | val1 = get_heap_comp_val(lprops, cat); | |
188 | val2 = get_heap_comp_val(heap->arr[cpos], cat); | |
189 | if (val1 > val2) { | |
190 | struct ubifs_lprops *lp; | |
191 | ||
192 | lp = heap->arr[cpos]; | |
193 | lp->flags &= ~LPROPS_CAT_MASK; | |
194 | lp->flags |= LPROPS_UNCAT; | |
195 | list_add(&lp->list, &c->uncat_list); | |
196 | lprops->hpos = cpos; | |
197 | heap->arr[cpos] = lprops; | |
198 | move_up_lpt_heap(c, heap, lprops, cat); | |
199 | dbg_check_heap(c, heap, cat, lprops->hpos); | |
200 | return 1; /* Added to heap */ | |
201 | } | |
202 | dbg_check_heap(c, heap, cat, -1); | |
203 | return 0; /* Not added to heap */ | |
204 | } else { | |
205 | lprops->hpos = heap->cnt++; | |
206 | heap->arr[lprops->hpos] = lprops; | |
207 | move_up_lpt_heap(c, heap, lprops, cat); | |
208 | dbg_check_heap(c, heap, cat, lprops->hpos); | |
209 | return 1; /* Added to heap */ | |
210 | } | |
211 | } | |
212 | ||
213 | /** | |
214 | * remove_from_lpt_heap - remove LEB properties from a LEB category heap. | |
215 | * @c: UBIFS file-system description object | |
216 | * @lprops: LEB properties to remove | |
217 | * @cat: LEB category | |
218 | */ | |
219 | static void remove_from_lpt_heap(struct ubifs_info *c, | |
220 | struct ubifs_lprops *lprops, int cat) | |
221 | { | |
222 | struct ubifs_lpt_heap *heap; | |
223 | int hpos = lprops->hpos; | |
224 | ||
225 | heap = &c->lpt_heap[cat - 1]; | |
226 | ubifs_assert(hpos >= 0 && hpos < heap->cnt); | |
227 | ubifs_assert(heap->arr[hpos] == lprops); | |
228 | heap->cnt -= 1; | |
229 | if (hpos < heap->cnt) { | |
230 | heap->arr[hpos] = heap->arr[heap->cnt]; | |
231 | heap->arr[hpos]->hpos = hpos; | |
232 | adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat); | |
233 | } | |
234 | dbg_check_heap(c, heap, cat, -1); | |
235 | } | |
236 | ||
237 | /** | |
238 | * lpt_heap_replace - replace lprops in a category heap. | |
239 | * @c: UBIFS file-system description object | |
240 | * @old_lprops: LEB properties to replace | |
241 | * @new_lprops: LEB properties with which to replace | |
242 | * @cat: LEB category | |
243 | * | |
244 | * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode) | |
245 | * and the lprops that the pnode contains. When that happens, references in | |
246 | * the category heaps to those lprops must be updated to point to the new | |
247 | * lprops. This function does that. | |
248 | */ | |
249 | static void lpt_heap_replace(struct ubifs_info *c, | |
250 | struct ubifs_lprops *old_lprops, | |
251 | struct ubifs_lprops *new_lprops, int cat) | |
252 | { | |
253 | struct ubifs_lpt_heap *heap; | |
254 | int hpos = new_lprops->hpos; | |
255 | ||
256 | heap = &c->lpt_heap[cat - 1]; | |
257 | heap->arr[hpos] = new_lprops; | |
258 | } | |
259 | ||
260 | /** | |
261 | * ubifs_add_to_cat - add LEB properties to a category list or heap. | |
262 | * @c: UBIFS file-system description object | |
263 | * @lprops: LEB properties to add | |
264 | * @cat: LEB category to which to add | |
265 | * | |
266 | * LEB properties are categorized to enable fast find operations. | |
267 | */ | |
268 | void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops, | |
269 | int cat) | |
270 | { | |
271 | switch (cat) { | |
272 | case LPROPS_DIRTY: | |
273 | case LPROPS_DIRTY_IDX: | |
274 | case LPROPS_FREE: | |
275 | if (add_to_lpt_heap(c, lprops, cat)) | |
276 | break; | |
ff94bc40 | 277 | /* No more room on heap so make it un-categorized */ |
9eefe2a2 SR |
278 | cat = LPROPS_UNCAT; |
279 | /* Fall through */ | |
280 | case LPROPS_UNCAT: | |
281 | list_add(&lprops->list, &c->uncat_list); | |
282 | break; | |
283 | case LPROPS_EMPTY: | |
284 | list_add(&lprops->list, &c->empty_list); | |
285 | break; | |
286 | case LPROPS_FREEABLE: | |
287 | list_add(&lprops->list, &c->freeable_list); | |
288 | c->freeable_cnt += 1; | |
289 | break; | |
290 | case LPROPS_FRDI_IDX: | |
291 | list_add(&lprops->list, &c->frdi_idx_list); | |
292 | break; | |
293 | default: | |
294 | ubifs_assert(0); | |
295 | } | |
ff94bc40 | 296 | |
9eefe2a2 SR |
297 | lprops->flags &= ~LPROPS_CAT_MASK; |
298 | lprops->flags |= cat; | |
ff94bc40 HS |
299 | c->in_a_category_cnt += 1; |
300 | ubifs_assert(c->in_a_category_cnt <= c->main_lebs); | |
9eefe2a2 SR |
301 | } |
302 | ||
303 | /** | |
304 | * ubifs_remove_from_cat - remove LEB properties from a category list or heap. | |
305 | * @c: UBIFS file-system description object | |
306 | * @lprops: LEB properties to remove | |
307 | * @cat: LEB category from which to remove | |
308 | * | |
309 | * LEB properties are categorized to enable fast find operations. | |
310 | */ | |
311 | static void ubifs_remove_from_cat(struct ubifs_info *c, | |
312 | struct ubifs_lprops *lprops, int cat) | |
313 | { | |
314 | switch (cat) { | |
315 | case LPROPS_DIRTY: | |
316 | case LPROPS_DIRTY_IDX: | |
317 | case LPROPS_FREE: | |
318 | remove_from_lpt_heap(c, lprops, cat); | |
319 | break; | |
320 | case LPROPS_FREEABLE: | |
321 | c->freeable_cnt -= 1; | |
322 | ubifs_assert(c->freeable_cnt >= 0); | |
323 | /* Fall through */ | |
324 | case LPROPS_UNCAT: | |
325 | case LPROPS_EMPTY: | |
326 | case LPROPS_FRDI_IDX: | |
327 | ubifs_assert(!list_empty(&lprops->list)); | |
328 | list_del(&lprops->list); | |
329 | break; | |
330 | default: | |
331 | ubifs_assert(0); | |
332 | } | |
ff94bc40 HS |
333 | |
334 | c->in_a_category_cnt -= 1; | |
335 | ubifs_assert(c->in_a_category_cnt >= 0); | |
9eefe2a2 SR |
336 | } |
337 | ||
338 | /** | |
339 | * ubifs_replace_cat - replace lprops in a category list or heap. | |
340 | * @c: UBIFS file-system description object | |
341 | * @old_lprops: LEB properties to replace | |
342 | * @new_lprops: LEB properties with which to replace | |
343 | * | |
344 | * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode) | |
345 | * and the lprops that the pnode contains. When that happens, references in | |
346 | * category lists and heaps must be replaced. This function does that. | |
347 | */ | |
348 | void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops, | |
349 | struct ubifs_lprops *new_lprops) | |
350 | { | |
351 | int cat; | |
352 | ||
353 | cat = new_lprops->flags & LPROPS_CAT_MASK; | |
354 | switch (cat) { | |
355 | case LPROPS_DIRTY: | |
356 | case LPROPS_DIRTY_IDX: | |
357 | case LPROPS_FREE: | |
358 | lpt_heap_replace(c, old_lprops, new_lprops, cat); | |
359 | break; | |
360 | case LPROPS_UNCAT: | |
361 | case LPROPS_EMPTY: | |
362 | case LPROPS_FREEABLE: | |
363 | case LPROPS_FRDI_IDX: | |
364 | list_replace(&old_lprops->list, &new_lprops->list); | |
365 | break; | |
366 | default: | |
367 | ubifs_assert(0); | |
368 | } | |
369 | } | |
370 | ||
371 | /** | |
372 | * ubifs_ensure_cat - ensure LEB properties are categorized. | |
373 | * @c: UBIFS file-system description object | |
374 | * @lprops: LEB properties | |
375 | * | |
376 | * A LEB may have fallen off of the bottom of a heap, and ended up as | |
ff94bc40 HS |
377 | * un-categorized even though it has enough space for us now. If that is the |
378 | * case this function will put the LEB back onto a heap. | |
9eefe2a2 SR |
379 | */ |
380 | void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops) | |
381 | { | |
382 | int cat = lprops->flags & LPROPS_CAT_MASK; | |
383 | ||
384 | if (cat != LPROPS_UNCAT) | |
385 | return; | |
386 | cat = ubifs_categorize_lprops(c, lprops); | |
387 | if (cat == LPROPS_UNCAT) | |
388 | return; | |
389 | ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT); | |
390 | ubifs_add_to_cat(c, lprops, cat); | |
391 | } | |
392 | ||
393 | /** | |
394 | * ubifs_categorize_lprops - categorize LEB properties. | |
395 | * @c: UBIFS file-system description object | |
396 | * @lprops: LEB properties to categorize | |
397 | * | |
398 | * LEB properties are categorized to enable fast find operations. This function | |
399 | * returns the LEB category to which the LEB properties belong. Note however | |
400 | * that if the LEB category is stored as a heap and the heap is full, the | |
401 | * LEB properties may have their category changed to %LPROPS_UNCAT. | |
402 | */ | |
403 | int ubifs_categorize_lprops(const struct ubifs_info *c, | |
404 | const struct ubifs_lprops *lprops) | |
405 | { | |
406 | if (lprops->flags & LPROPS_TAKEN) | |
407 | return LPROPS_UNCAT; | |
408 | ||
409 | if (lprops->free == c->leb_size) { | |
410 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
411 | return LPROPS_EMPTY; | |
412 | } | |
413 | ||
414 | if (lprops->free + lprops->dirty == c->leb_size) { | |
415 | if (lprops->flags & LPROPS_INDEX) | |
416 | return LPROPS_FRDI_IDX; | |
417 | else | |
418 | return LPROPS_FREEABLE; | |
419 | } | |
420 | ||
421 | if (lprops->flags & LPROPS_INDEX) { | |
422 | if (lprops->dirty + lprops->free >= c->min_idx_node_sz) | |
423 | return LPROPS_DIRTY_IDX; | |
424 | } else { | |
425 | if (lprops->dirty >= c->dead_wm && | |
426 | lprops->dirty > lprops->free) | |
427 | return LPROPS_DIRTY; | |
428 | if (lprops->free > 0) | |
429 | return LPROPS_FREE; | |
430 | } | |
431 | ||
432 | return LPROPS_UNCAT; | |
433 | } | |
434 | ||
435 | /** | |
436 | * change_category - change LEB properties category. | |
437 | * @c: UBIFS file-system description object | |
ff94bc40 | 438 | * @lprops: LEB properties to re-categorize |
9eefe2a2 SR |
439 | * |
440 | * LEB properties are categorized to enable fast find operations. When the LEB | |
ff94bc40 | 441 | * properties change they must be re-categorized. |
9eefe2a2 SR |
442 | */ |
443 | static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops) | |
444 | { | |
445 | int old_cat = lprops->flags & LPROPS_CAT_MASK; | |
446 | int new_cat = ubifs_categorize_lprops(c, lprops); | |
447 | ||
448 | if (old_cat == new_cat) { | |
ff94bc40 | 449 | struct ubifs_lpt_heap *heap; |
9eefe2a2 SR |
450 | |
451 | /* lprops on a heap now must be moved up or down */ | |
452 | if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT) | |
453 | return; /* Not on a heap */ | |
454 | heap = &c->lpt_heap[new_cat - 1]; | |
455 | adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat); | |
456 | } else { | |
457 | ubifs_remove_from_cat(c, lprops, old_cat); | |
458 | ubifs_add_to_cat(c, lprops, new_cat); | |
459 | } | |
460 | } | |
461 | ||
462 | /** | |
ff94bc40 | 463 | * ubifs_calc_dark - calculate LEB dark space size. |
9eefe2a2 SR |
464 | * @c: the UBIFS file-system description object |
465 | * @spc: amount of free and dirty space in the LEB | |
466 | * | |
ff94bc40 HS |
467 | * This function calculates and returns amount of dark space in an LEB which |
468 | * has @spc bytes of free and dirty space. | |
9eefe2a2 | 469 | * |
ff94bc40 HS |
470 | * UBIFS is trying to account the space which might not be usable, and this |
471 | * space is called "dark space". For example, if an LEB has only %512 free | |
472 | * bytes, it is dark space, because it cannot fit a large data node. | |
9eefe2a2 | 473 | */ |
ff94bc40 | 474 | int ubifs_calc_dark(const struct ubifs_info *c, int spc) |
9eefe2a2 SR |
475 | { |
476 | ubifs_assert(!(spc & 7)); | |
477 | ||
478 | if (spc < c->dark_wm) | |
479 | return spc; | |
480 | ||
481 | /* | |
482 | * If we have slightly more space then the dark space watermark, we can | |
483 | * anyway safely assume it we'll be able to write a node of the | |
484 | * smallest size there. | |
485 | */ | |
486 | if (spc - c->dark_wm < MIN_WRITE_SZ) | |
487 | return spc - MIN_WRITE_SZ; | |
488 | ||
489 | return c->dark_wm; | |
490 | } | |
491 | ||
492 | /** | |
493 | * is_lprops_dirty - determine if LEB properties are dirty. | |
494 | * @c: the UBIFS file-system description object | |
495 | * @lprops: LEB properties to test | |
496 | */ | |
497 | static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops) | |
498 | { | |
499 | struct ubifs_pnode *pnode; | |
500 | int pos; | |
501 | ||
502 | pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1); | |
503 | pnode = (struct ubifs_pnode *)container_of(lprops - pos, | |
504 | struct ubifs_pnode, | |
505 | lprops[0]); | |
ff94bc40 | 506 | return !test_bit(COW_CNODE, &pnode->flags) && |
9eefe2a2 SR |
507 | test_bit(DIRTY_CNODE, &pnode->flags); |
508 | } | |
509 | ||
510 | /** | |
511 | * ubifs_change_lp - change LEB properties. | |
512 | * @c: the UBIFS file-system description object | |
513 | * @lp: LEB properties to change | |
514 | * @free: new free space amount | |
515 | * @dirty: new dirty space amount | |
516 | * @flags: new flags | |
ff94bc40 | 517 | * @idx_gc_cnt: change to the count of @idx_gc list |
9eefe2a2 SR |
518 | * |
519 | * This function changes LEB properties (@free, @dirty or @flag). However, the | |
520 | * property which has the %LPROPS_NC value is not changed. Returns a pointer to | |
521 | * the updated LEB properties on success and a negative error code on failure. | |
522 | * | |
523 | * Note, the LEB properties may have had to be copied (due to COW) and | |
524 | * consequently the pointer returned may not be the same as the pointer | |
525 | * passed. | |
526 | */ | |
527 | const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c, | |
528 | const struct ubifs_lprops *lp, | |
529 | int free, int dirty, int flags, | |
530 | int idx_gc_cnt) | |
531 | { | |
532 | /* | |
533 | * This is the only function that is allowed to change lprops, so we | |
ff94bc40 | 534 | * discard the "const" qualifier. |
9eefe2a2 SR |
535 | */ |
536 | struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp; | |
537 | ||
538 | dbg_lp("LEB %d, free %d, dirty %d, flags %d", | |
539 | lprops->lnum, free, dirty, flags); | |
540 | ||
541 | ubifs_assert(mutex_is_locked(&c->lp_mutex)); | |
542 | ubifs_assert(c->lst.empty_lebs >= 0 && | |
543 | c->lst.empty_lebs <= c->main_lebs); | |
544 | ubifs_assert(c->freeable_cnt >= 0); | |
545 | ubifs_assert(c->freeable_cnt <= c->main_lebs); | |
546 | ubifs_assert(c->lst.taken_empty_lebs >= 0); | |
547 | ubifs_assert(c->lst.taken_empty_lebs <= c->lst.empty_lebs); | |
548 | ubifs_assert(!(c->lst.total_free & 7) && !(c->lst.total_dirty & 7)); | |
549 | ubifs_assert(!(c->lst.total_dead & 7) && !(c->lst.total_dark & 7)); | |
550 | ubifs_assert(!(c->lst.total_used & 7)); | |
551 | ubifs_assert(free == LPROPS_NC || free >= 0); | |
552 | ubifs_assert(dirty == LPROPS_NC || dirty >= 0); | |
553 | ||
554 | if (!is_lprops_dirty(c, lprops)) { | |
555 | lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum); | |
556 | if (IS_ERR(lprops)) | |
557 | return lprops; | |
558 | } else | |
559 | ubifs_assert(lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum)); | |
560 | ||
561 | ubifs_assert(!(lprops->free & 7) && !(lprops->dirty & 7)); | |
562 | ||
563 | spin_lock(&c->space_lock); | |
564 | if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size) | |
565 | c->lst.taken_empty_lebs -= 1; | |
566 | ||
567 | if (!(lprops->flags & LPROPS_INDEX)) { | |
568 | int old_spc; | |
569 | ||
570 | old_spc = lprops->free + lprops->dirty; | |
571 | if (old_spc < c->dead_wm) | |
572 | c->lst.total_dead -= old_spc; | |
573 | else | |
ff94bc40 | 574 | c->lst.total_dark -= ubifs_calc_dark(c, old_spc); |
9eefe2a2 SR |
575 | |
576 | c->lst.total_used -= c->leb_size - old_spc; | |
577 | } | |
578 | ||
579 | if (free != LPROPS_NC) { | |
580 | free = ALIGN(free, 8); | |
581 | c->lst.total_free += free - lprops->free; | |
582 | ||
583 | /* Increase or decrease empty LEBs counter if needed */ | |
584 | if (free == c->leb_size) { | |
585 | if (lprops->free != c->leb_size) | |
586 | c->lst.empty_lebs += 1; | |
587 | } else if (lprops->free == c->leb_size) | |
588 | c->lst.empty_lebs -= 1; | |
589 | lprops->free = free; | |
590 | } | |
591 | ||
592 | if (dirty != LPROPS_NC) { | |
593 | dirty = ALIGN(dirty, 8); | |
594 | c->lst.total_dirty += dirty - lprops->dirty; | |
595 | lprops->dirty = dirty; | |
596 | } | |
597 | ||
598 | if (flags != LPROPS_NC) { | |
599 | /* Take care about indexing LEBs counter if needed */ | |
600 | if ((lprops->flags & LPROPS_INDEX)) { | |
601 | if (!(flags & LPROPS_INDEX)) | |
602 | c->lst.idx_lebs -= 1; | |
603 | } else if (flags & LPROPS_INDEX) | |
604 | c->lst.idx_lebs += 1; | |
605 | lprops->flags = flags; | |
606 | } | |
607 | ||
608 | if (!(lprops->flags & LPROPS_INDEX)) { | |
609 | int new_spc; | |
610 | ||
611 | new_spc = lprops->free + lprops->dirty; | |
612 | if (new_spc < c->dead_wm) | |
613 | c->lst.total_dead += new_spc; | |
614 | else | |
ff94bc40 | 615 | c->lst.total_dark += ubifs_calc_dark(c, new_spc); |
9eefe2a2 SR |
616 | |
617 | c->lst.total_used += c->leb_size - new_spc; | |
618 | } | |
619 | ||
620 | if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size) | |
621 | c->lst.taken_empty_lebs += 1; | |
622 | ||
623 | change_category(c, lprops); | |
624 | c->idx_gc_cnt += idx_gc_cnt; | |
625 | spin_unlock(&c->space_lock); | |
626 | return lprops; | |
627 | } | |
628 | ||
629 | /** | |
630 | * ubifs_get_lp_stats - get lprops statistics. | |
631 | * @c: UBIFS file-system description object | |
632 | * @st: return statistics | |
633 | */ | |
634 | void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst) | |
635 | { | |
636 | spin_lock(&c->space_lock); | |
637 | memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats)); | |
638 | spin_unlock(&c->space_lock); | |
639 | } | |
640 | ||
641 | /** | |
642 | * ubifs_change_one_lp - change LEB properties. | |
643 | * @c: the UBIFS file-system description object | |
644 | * @lnum: LEB to change properties for | |
645 | * @free: amount of free space | |
646 | * @dirty: amount of dirty space | |
647 | * @flags_set: flags to set | |
648 | * @flags_clean: flags to clean | |
649 | * @idx_gc_cnt: change to the count of idx_gc list | |
650 | * | |
651 | * This function changes properties of LEB @lnum. It is a helper wrapper over | |
652 | * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the | |
653 | * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and | |
654 | * a negative error code in case of failure. | |
655 | */ | |
656 | int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty, | |
657 | int flags_set, int flags_clean, int idx_gc_cnt) | |
658 | { | |
659 | int err = 0, flags; | |
660 | const struct ubifs_lprops *lp; | |
661 | ||
662 | ubifs_get_lprops(c); | |
663 | ||
664 | lp = ubifs_lpt_lookup_dirty(c, lnum); | |
665 | if (IS_ERR(lp)) { | |
666 | err = PTR_ERR(lp); | |
667 | goto out; | |
668 | } | |
669 | ||
670 | flags = (lp->flags | flags_set) & ~flags_clean; | |
671 | lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt); | |
672 | if (IS_ERR(lp)) | |
673 | err = PTR_ERR(lp); | |
674 | ||
675 | out: | |
676 | ubifs_release_lprops(c); | |
ff94bc40 HS |
677 | if (err) |
678 | ubifs_err("cannot change properties of LEB %d, error %d", | |
679 | lnum, err); | |
9eefe2a2 SR |
680 | return err; |
681 | } | |
682 | ||
683 | /** | |
684 | * ubifs_update_one_lp - update LEB properties. | |
685 | * @c: the UBIFS file-system description object | |
686 | * @lnum: LEB to change properties for | |
687 | * @free: amount of free space | |
688 | * @dirty: amount of dirty space to add | |
689 | * @flags_set: flags to set | |
690 | * @flags_clean: flags to clean | |
691 | * | |
692 | * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to | |
693 | * current dirty space, not substitutes it. | |
694 | */ | |
695 | int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty, | |
696 | int flags_set, int flags_clean) | |
697 | { | |
698 | int err = 0, flags; | |
699 | const struct ubifs_lprops *lp; | |
700 | ||
701 | ubifs_get_lprops(c); | |
702 | ||
703 | lp = ubifs_lpt_lookup_dirty(c, lnum); | |
704 | if (IS_ERR(lp)) { | |
705 | err = PTR_ERR(lp); | |
706 | goto out; | |
707 | } | |
708 | ||
709 | flags = (lp->flags | flags_set) & ~flags_clean; | |
710 | lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0); | |
711 | if (IS_ERR(lp)) | |
712 | err = PTR_ERR(lp); | |
713 | ||
714 | out: | |
715 | ubifs_release_lprops(c); | |
ff94bc40 HS |
716 | if (err) |
717 | ubifs_err("cannot update properties of LEB %d, error %d", | |
718 | lnum, err); | |
9eefe2a2 SR |
719 | return err; |
720 | } | |
721 | ||
722 | /** | |
723 | * ubifs_read_one_lp - read LEB properties. | |
724 | * @c: the UBIFS file-system description object | |
725 | * @lnum: LEB to read properties for | |
726 | * @lp: where to store read properties | |
727 | * | |
728 | * This helper function reads properties of a LEB @lnum and stores them in @lp. | |
729 | * Returns zero in case of success and a negative error code in case of | |
730 | * failure. | |
731 | */ | |
732 | int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp) | |
733 | { | |
734 | int err = 0; | |
735 | const struct ubifs_lprops *lpp; | |
736 | ||
737 | ubifs_get_lprops(c); | |
738 | ||
739 | lpp = ubifs_lpt_lookup(c, lnum); | |
740 | if (IS_ERR(lpp)) { | |
741 | err = PTR_ERR(lpp); | |
ff94bc40 HS |
742 | ubifs_err("cannot read properties of LEB %d, error %d", |
743 | lnum, err); | |
9eefe2a2 SR |
744 | goto out; |
745 | } | |
746 | ||
747 | memcpy(lp, lpp, sizeof(struct ubifs_lprops)); | |
748 | ||
749 | out: | |
750 | ubifs_release_lprops(c); | |
751 | return err; | |
752 | } | |
753 | ||
754 | /** | |
755 | * ubifs_fast_find_free - try to find a LEB with free space quickly. | |
756 | * @c: the UBIFS file-system description object | |
757 | * | |
758 | * This function returns LEB properties for a LEB with free space or %NULL if | |
759 | * the function is unable to find a LEB quickly. | |
760 | */ | |
761 | const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c) | |
762 | { | |
763 | struct ubifs_lprops *lprops; | |
764 | struct ubifs_lpt_heap *heap; | |
765 | ||
766 | ubifs_assert(mutex_is_locked(&c->lp_mutex)); | |
767 | ||
768 | heap = &c->lpt_heap[LPROPS_FREE - 1]; | |
769 | if (heap->cnt == 0) | |
770 | return NULL; | |
771 | ||
772 | lprops = heap->arr[0]; | |
773 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
774 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
775 | return lprops; | |
776 | } | |
777 | ||
778 | /** | |
779 | * ubifs_fast_find_empty - try to find an empty LEB quickly. | |
780 | * @c: the UBIFS file-system description object | |
781 | * | |
782 | * This function returns LEB properties for an empty LEB or %NULL if the | |
783 | * function is unable to find an empty LEB quickly. | |
784 | */ | |
785 | const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c) | |
786 | { | |
787 | struct ubifs_lprops *lprops; | |
788 | ||
789 | ubifs_assert(mutex_is_locked(&c->lp_mutex)); | |
790 | ||
791 | if (list_empty(&c->empty_list)) | |
792 | return NULL; | |
793 | ||
794 | lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list); | |
795 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
796 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
797 | ubifs_assert(lprops->free == c->leb_size); | |
798 | return lprops; | |
799 | } | |
800 | ||
801 | /** | |
802 | * ubifs_fast_find_freeable - try to find a freeable LEB quickly. | |
803 | * @c: the UBIFS file-system description object | |
804 | * | |
805 | * This function returns LEB properties for a freeable LEB or %NULL if the | |
806 | * function is unable to find a freeable LEB quickly. | |
807 | */ | |
808 | const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c) | |
809 | { | |
810 | struct ubifs_lprops *lprops; | |
811 | ||
812 | ubifs_assert(mutex_is_locked(&c->lp_mutex)); | |
813 | ||
814 | if (list_empty(&c->freeable_list)) | |
815 | return NULL; | |
816 | ||
817 | lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list); | |
818 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
819 | ubifs_assert(!(lprops->flags & LPROPS_INDEX)); | |
820 | ubifs_assert(lprops->free + lprops->dirty == c->leb_size); | |
821 | ubifs_assert(c->freeable_cnt > 0); | |
822 | return lprops; | |
823 | } | |
824 | ||
825 | /** | |
826 | * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly. | |
827 | * @c: the UBIFS file-system description object | |
828 | * | |
829 | * This function returns LEB properties for a freeable index LEB or %NULL if the | |
830 | * function is unable to find a freeable index LEB quickly. | |
831 | */ | |
832 | const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c) | |
833 | { | |
834 | struct ubifs_lprops *lprops; | |
835 | ||
836 | ubifs_assert(mutex_is_locked(&c->lp_mutex)); | |
837 | ||
838 | if (list_empty(&c->frdi_idx_list)) | |
839 | return NULL; | |
840 | ||
841 | lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list); | |
842 | ubifs_assert(!(lprops->flags & LPROPS_TAKEN)); | |
843 | ubifs_assert((lprops->flags & LPROPS_INDEX)); | |
844 | ubifs_assert(lprops->free + lprops->dirty == c->leb_size); | |
845 | return lprops; | |
846 | } | |
ff94bc40 HS |
847 | |
848 | /* | |
849 | * Everything below is related to debugging. | |
850 | */ | |
851 | ||
852 | /** | |
853 | * dbg_check_cats - check category heaps and lists. | |
854 | * @c: UBIFS file-system description object | |
855 | * | |
856 | * This function returns %0 on success and a negative error code on failure. | |
857 | */ | |
858 | int dbg_check_cats(struct ubifs_info *c) | |
859 | { | |
860 | struct ubifs_lprops *lprops; | |
861 | struct list_head *pos; | |
862 | int i, cat; | |
863 | ||
864 | if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c)) | |
865 | return 0; | |
866 | ||
867 | list_for_each_entry(lprops, &c->empty_list, list) { | |
868 | if (lprops->free != c->leb_size) { | |
869 | ubifs_err("non-empty LEB %d on empty list (free %d dirty %d flags %d)", | |
870 | lprops->lnum, lprops->free, lprops->dirty, | |
871 | lprops->flags); | |
872 | return -EINVAL; | |
873 | } | |
874 | if (lprops->flags & LPROPS_TAKEN) { | |
875 | ubifs_err("taken LEB %d on empty list (free %d dirty %d flags %d)", | |
876 | lprops->lnum, lprops->free, lprops->dirty, | |
877 | lprops->flags); | |
878 | return -EINVAL; | |
879 | } | |
880 | } | |
881 | ||
882 | i = 0; | |
883 | list_for_each_entry(lprops, &c->freeable_list, list) { | |
884 | if (lprops->free + lprops->dirty != c->leb_size) { | |
885 | ubifs_err("non-freeable LEB %d on freeable list (free %d dirty %d flags %d)", | |
886 | lprops->lnum, lprops->free, lprops->dirty, | |
887 | lprops->flags); | |
888 | return -EINVAL; | |
889 | } | |
890 | if (lprops->flags & LPROPS_TAKEN) { | |
891 | ubifs_err("taken LEB %d on freeable list (free %d dirty %d flags %d)", | |
892 | lprops->lnum, lprops->free, lprops->dirty, | |
893 | lprops->flags); | |
894 | return -EINVAL; | |
895 | } | |
896 | i += 1; | |
897 | } | |
898 | if (i != c->freeable_cnt) { | |
899 | ubifs_err("freeable list count %d expected %d", i, | |
900 | c->freeable_cnt); | |
901 | return -EINVAL; | |
902 | } | |
903 | ||
904 | i = 0; | |
905 | list_for_each(pos, &c->idx_gc) | |
906 | i += 1; | |
907 | if (i != c->idx_gc_cnt) { | |
908 | ubifs_err("idx_gc list count %d expected %d", i, | |
909 | c->idx_gc_cnt); | |
910 | return -EINVAL; | |
911 | } | |
912 | ||
913 | list_for_each_entry(lprops, &c->frdi_idx_list, list) { | |
914 | if (lprops->free + lprops->dirty != c->leb_size) { | |
915 | ubifs_err("non-freeable LEB %d on frdi_idx list (free %d dirty %d flags %d)", | |
916 | lprops->lnum, lprops->free, lprops->dirty, | |
917 | lprops->flags); | |
918 | return -EINVAL; | |
919 | } | |
920 | if (lprops->flags & LPROPS_TAKEN) { | |
921 | ubifs_err("taken LEB %d on frdi_idx list (free %d dirty %d flags %d)", | |
922 | lprops->lnum, lprops->free, lprops->dirty, | |
923 | lprops->flags); | |
924 | return -EINVAL; | |
925 | } | |
926 | if (!(lprops->flags & LPROPS_INDEX)) { | |
927 | ubifs_err("non-index LEB %d on frdi_idx list (free %d dirty %d flags %d)", | |
928 | lprops->lnum, lprops->free, lprops->dirty, | |
929 | lprops->flags); | |
930 | return -EINVAL; | |
931 | } | |
932 | } | |
933 | ||
934 | for (cat = 1; cat <= LPROPS_HEAP_CNT; cat++) { | |
935 | struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1]; | |
936 | ||
937 | for (i = 0; i < heap->cnt; i++) { | |
938 | lprops = heap->arr[i]; | |
939 | if (!lprops) { | |
940 | ubifs_err("null ptr in LPT heap cat %d", cat); | |
941 | return -EINVAL; | |
942 | } | |
943 | if (lprops->hpos != i) { | |
944 | ubifs_err("bad ptr in LPT heap cat %d", cat); | |
945 | return -EINVAL; | |
946 | } | |
947 | if (lprops->flags & LPROPS_TAKEN) { | |
948 | ubifs_err("taken LEB in LPT heap cat %d", cat); | |
949 | return -EINVAL; | |
950 | } | |
951 | } | |
952 | } | |
953 | ||
954 | return 0; | |
955 | } | |
956 | ||
957 | void dbg_check_heap(struct ubifs_info *c, struct ubifs_lpt_heap *heap, int cat, | |
958 | int add_pos) | |
959 | { | |
960 | int i = 0, j, err = 0; | |
961 | ||
962 | if (!dbg_is_chk_gen(c) && !dbg_is_chk_lprops(c)) | |
963 | return; | |
964 | ||
965 | for (i = 0; i < heap->cnt; i++) { | |
966 | struct ubifs_lprops *lprops = heap->arr[i]; | |
967 | struct ubifs_lprops *lp; | |
968 | ||
969 | if (i != add_pos) | |
970 | if ((lprops->flags & LPROPS_CAT_MASK) != cat) { | |
971 | err = 1; | |
972 | goto out; | |
973 | } | |
974 | if (lprops->hpos != i) { | |
975 | err = 2; | |
976 | goto out; | |
977 | } | |
978 | lp = ubifs_lpt_lookup(c, lprops->lnum); | |
979 | if (IS_ERR(lp)) { | |
980 | err = 3; | |
981 | goto out; | |
982 | } | |
983 | if (lprops != lp) { | |
984 | ubifs_err("lprops %zx lp %zx lprops->lnum %d lp->lnum %d", | |
985 | (size_t)lprops, (size_t)lp, lprops->lnum, | |
986 | lp->lnum); | |
987 | err = 4; | |
988 | goto out; | |
989 | } | |
990 | for (j = 0; j < i; j++) { | |
991 | lp = heap->arr[j]; | |
992 | if (lp == lprops) { | |
993 | err = 5; | |
994 | goto out; | |
995 | } | |
996 | if (lp->lnum == lprops->lnum) { | |
997 | err = 6; | |
998 | goto out; | |
999 | } | |
1000 | } | |
1001 | } | |
1002 | out: | |
1003 | if (err) { | |
1004 | ubifs_err("failed cat %d hpos %d err %d", cat, i, err); | |
1005 | dump_stack(); | |
1006 | ubifs_dump_heap(c, heap, cat); | |
1007 | } | |
1008 | } | |
1009 | ||
1010 | /** | |
1011 | * scan_check_cb - scan callback. | |
1012 | * @c: the UBIFS file-system description object | |
1013 | * @lp: LEB properties to scan | |
1014 | * @in_tree: whether the LEB properties are in main memory | |
1015 | * @lst: lprops statistics to update | |
1016 | * | |
1017 | * This function returns a code that indicates whether the scan should continue | |
1018 | * (%LPT_SCAN_CONTINUE), whether the LEB properties should be added to the tree | |
1019 | * in main memory (%LPT_SCAN_ADD), or whether the scan should stop | |
1020 | * (%LPT_SCAN_STOP). | |
1021 | */ | |
1022 | static int scan_check_cb(struct ubifs_info *c, | |
1023 | const struct ubifs_lprops *lp, int in_tree, | |
1024 | struct ubifs_lp_stats *lst) | |
1025 | { | |
1026 | struct ubifs_scan_leb *sleb; | |
1027 | struct ubifs_scan_node *snod; | |
1028 | int cat, lnum = lp->lnum, is_idx = 0, used = 0, freef, dirty, ret; | |
1029 | void *buf = NULL; | |
1030 | ||
1031 | cat = lp->flags & LPROPS_CAT_MASK; | |
1032 | if (cat != LPROPS_UNCAT) { | |
1033 | cat = ubifs_categorize_lprops(c, lp); | |
1034 | if (cat != (lp->flags & LPROPS_CAT_MASK)) { | |
1035 | ubifs_err("bad LEB category %d expected %d", | |
1036 | (lp->flags & LPROPS_CAT_MASK), cat); | |
1037 | return -EINVAL; | |
1038 | } | |
1039 | } | |
1040 | ||
1041 | /* Check lp is on its category list (if it has one) */ | |
1042 | if (in_tree) { | |
1043 | struct list_head *list = NULL; | |
1044 | ||
1045 | switch (cat) { | |
1046 | case LPROPS_EMPTY: | |
1047 | list = &c->empty_list; | |
1048 | break; | |
1049 | case LPROPS_FREEABLE: | |
1050 | list = &c->freeable_list; | |
1051 | break; | |
1052 | case LPROPS_FRDI_IDX: | |
1053 | list = &c->frdi_idx_list; | |
1054 | break; | |
1055 | case LPROPS_UNCAT: | |
1056 | list = &c->uncat_list; | |
1057 | break; | |
1058 | } | |
1059 | if (list) { | |
1060 | struct ubifs_lprops *lprops; | |
1061 | int found = 0; | |
1062 | ||
1063 | list_for_each_entry(lprops, list, list) { | |
1064 | if (lprops == lp) { | |
1065 | found = 1; | |
1066 | break; | |
1067 | } | |
1068 | } | |
1069 | if (!found) { | |
1070 | ubifs_err("bad LPT list (category %d)", cat); | |
1071 | return -EINVAL; | |
1072 | } | |
1073 | } | |
1074 | } | |
1075 | ||
1076 | /* Check lp is on its category heap (if it has one) */ | |
1077 | if (in_tree && cat > 0 && cat <= LPROPS_HEAP_CNT) { | |
1078 | struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1]; | |
1079 | ||
1080 | if ((lp->hpos != -1 && heap->arr[lp->hpos]->lnum != lnum) || | |
1081 | lp != heap->arr[lp->hpos]) { | |
1082 | ubifs_err("bad LPT heap (category %d)", cat); | |
1083 | return -EINVAL; | |
1084 | } | |
1085 | } | |
1086 | ||
1087 | buf = __vmalloc(c->leb_size, GFP_NOFS, PAGE_KERNEL); | |
1088 | if (!buf) | |
1089 | return -ENOMEM; | |
1090 | ||
1091 | /* | |
1092 | * After an unclean unmount, empty and freeable LEBs | |
1093 | * may contain garbage - do not scan them. | |
1094 | */ | |
1095 | if (lp->free == c->leb_size) { | |
1096 | lst->empty_lebs += 1; | |
1097 | lst->total_free += c->leb_size; | |
1098 | lst->total_dark += ubifs_calc_dark(c, c->leb_size); | |
1099 | return LPT_SCAN_CONTINUE; | |
1100 | } | |
1101 | if (lp->free + lp->dirty == c->leb_size && | |
1102 | !(lp->flags & LPROPS_INDEX)) { | |
1103 | lst->total_free += lp->free; | |
1104 | lst->total_dirty += lp->dirty; | |
1105 | lst->total_dark += ubifs_calc_dark(c, c->leb_size); | |
1106 | return LPT_SCAN_CONTINUE; | |
1107 | } | |
1108 | ||
1109 | sleb = ubifs_scan(c, lnum, 0, buf, 0); | |
1110 | if (IS_ERR(sleb)) { | |
1111 | ret = PTR_ERR(sleb); | |
1112 | if (ret == -EUCLEAN) { | |
1113 | ubifs_dump_lprops(c); | |
1114 | ubifs_dump_budg(c, &c->bi); | |
1115 | } | |
1116 | goto out; | |
1117 | } | |
1118 | ||
1119 | is_idx = -1; | |
1120 | list_for_each_entry(snod, &sleb->nodes, list) { | |
1121 | int found, level = 0; | |
1122 | ||
1123 | cond_resched(); | |
1124 | ||
1125 | if (is_idx == -1) | |
1126 | is_idx = (snod->type == UBIFS_IDX_NODE) ? 1 : 0; | |
1127 | ||
1128 | if (is_idx && snod->type != UBIFS_IDX_NODE) { | |
1129 | ubifs_err("indexing node in data LEB %d:%d", | |
1130 | lnum, snod->offs); | |
1131 | goto out_destroy; | |
1132 | } | |
1133 | ||
1134 | if (snod->type == UBIFS_IDX_NODE) { | |
1135 | struct ubifs_idx_node *idx = snod->node; | |
1136 | ||
1137 | key_read(c, ubifs_idx_key(c, idx), &snod->key); | |
1138 | level = le16_to_cpu(idx->level); | |
1139 | } | |
1140 | ||
1141 | found = ubifs_tnc_has_node(c, &snod->key, level, lnum, | |
1142 | snod->offs, is_idx); | |
1143 | if (found) { | |
1144 | if (found < 0) | |
1145 | goto out_destroy; | |
1146 | used += ALIGN(snod->len, 8); | |
1147 | } | |
1148 | } | |
1149 | ||
1150 | freef = c->leb_size - sleb->endpt; | |
1151 | dirty = sleb->endpt - used; | |
1152 | ||
1153 | if (freef > c->leb_size || freef < 0 || dirty > c->leb_size || | |
1154 | dirty < 0) { | |
1155 | ubifs_err("bad calculated accounting for LEB %d: free %d, dirty %d", | |
1156 | lnum, freef, dirty); | |
1157 | goto out_destroy; | |
1158 | } | |
1159 | ||
1160 | if (lp->free + lp->dirty == c->leb_size && | |
1161 | freef + dirty == c->leb_size) | |
1162 | if ((is_idx && !(lp->flags & LPROPS_INDEX)) || | |
1163 | (!is_idx && freef == c->leb_size) || | |
1164 | lp->free == c->leb_size) { | |
1165 | /* | |
1166 | * Empty or freeable LEBs could contain index | |
1167 | * nodes from an uncompleted commit due to an | |
1168 | * unclean unmount. Or they could be empty for | |
1169 | * the same reason. Or it may simply not have been | |
1170 | * unmapped. | |
1171 | */ | |
1172 | freef = lp->free; | |
1173 | dirty = lp->dirty; | |
1174 | is_idx = 0; | |
1175 | } | |
1176 | ||
1177 | if (is_idx && lp->free + lp->dirty == freef + dirty && | |
1178 | lnum != c->ihead_lnum) { | |
1179 | /* | |
1180 | * After an unclean unmount, an index LEB could have a different | |
1181 | * amount of free space than the value recorded by lprops. That | |
1182 | * is because the in-the-gaps method may use free space or | |
1183 | * create free space (as a side-effect of using ubi_leb_change | |
1184 | * and not writing the whole LEB). The incorrect free space | |
1185 | * value is not a problem because the index is only ever | |
1186 | * allocated empty LEBs, so there will never be an attempt to | |
1187 | * write to the free space at the end of an index LEB - except | |
1188 | * by the in-the-gaps method for which it is not a problem. | |
1189 | */ | |
1190 | freef = lp->free; | |
1191 | dirty = lp->dirty; | |
1192 | } | |
1193 | ||
1194 | if (lp->free != freef || lp->dirty != dirty) | |
1195 | goto out_print; | |
1196 | ||
1197 | if (is_idx && !(lp->flags & LPROPS_INDEX)) { | |
1198 | if (freef == c->leb_size) | |
1199 | /* Free but not unmapped LEB, it's fine */ | |
1200 | is_idx = 0; | |
1201 | else { | |
1202 | ubifs_err("indexing node without indexing flag"); | |
1203 | goto out_print; | |
1204 | } | |
1205 | } | |
1206 | ||
1207 | if (!is_idx && (lp->flags & LPROPS_INDEX)) { | |
1208 | ubifs_err("data node with indexing flag"); | |
1209 | goto out_print; | |
1210 | } | |
1211 | ||
1212 | if (freef == c->leb_size) | |
1213 | lst->empty_lebs += 1; | |
1214 | ||
1215 | if (is_idx) | |
1216 | lst->idx_lebs += 1; | |
1217 | ||
1218 | if (!(lp->flags & LPROPS_INDEX)) | |
1219 | lst->total_used += c->leb_size - freef - dirty; | |
1220 | lst->total_free += freef; | |
1221 | lst->total_dirty += dirty; | |
1222 | ||
1223 | if (!(lp->flags & LPROPS_INDEX)) { | |
1224 | int spc = freef + dirty; | |
1225 | ||
1226 | if (spc < c->dead_wm) | |
1227 | lst->total_dead += spc; | |
1228 | else | |
1229 | lst->total_dark += ubifs_calc_dark(c, spc); | |
1230 | } | |
1231 | ||
1232 | ubifs_scan_destroy(sleb); | |
1233 | vfree(buf); | |
1234 | return LPT_SCAN_CONTINUE; | |
1235 | ||
1236 | out_print: | |
1237 | ubifs_err("bad accounting of LEB %d: free %d, dirty %d flags %#x, should be free %d, dirty %d", | |
1238 | lnum, lp->free, lp->dirty, lp->flags, freef, dirty); | |
1239 | ubifs_dump_leb(c, lnum); | |
1240 | out_destroy: | |
1241 | ubifs_scan_destroy(sleb); | |
1242 | ret = -EINVAL; | |
1243 | out: | |
1244 | vfree(buf); | |
1245 | return ret; | |
1246 | } | |
1247 | ||
1248 | /** | |
1249 | * dbg_check_lprops - check all LEB properties. | |
1250 | * @c: UBIFS file-system description object | |
1251 | * | |
1252 | * This function checks all LEB properties and makes sure they are all correct. | |
1253 | * It returns zero if everything is fine, %-EINVAL if there is an inconsistency | |
1254 | * and other negative error codes in case of other errors. This function is | |
1255 | * called while the file system is locked (because of commit start), so no | |
1256 | * additional locking is required. Note that locking the LPT mutex would cause | |
1257 | * a circular lock dependency with the TNC mutex. | |
1258 | */ | |
1259 | int dbg_check_lprops(struct ubifs_info *c) | |
1260 | { | |
1261 | int i, err; | |
1262 | struct ubifs_lp_stats lst; | |
1263 | ||
1264 | if (!dbg_is_chk_lprops(c)) | |
1265 | return 0; | |
1266 | ||
1267 | /* | |
1268 | * As we are going to scan the media, the write buffers have to be | |
1269 | * synchronized. | |
1270 | */ | |
1271 | for (i = 0; i < c->jhead_cnt; i++) { | |
1272 | err = ubifs_wbuf_sync(&c->jheads[i].wbuf); | |
1273 | if (err) | |
1274 | return err; | |
1275 | } | |
1276 | ||
1277 | memset(&lst, 0, sizeof(struct ubifs_lp_stats)); | |
1278 | err = ubifs_lpt_scan_nolock(c, c->main_first, c->leb_cnt - 1, | |
1279 | (ubifs_lpt_scan_callback)scan_check_cb, | |
1280 | &lst); | |
1281 | if (err && err != -ENOSPC) | |
1282 | goto out; | |
1283 | ||
1284 | if (lst.empty_lebs != c->lst.empty_lebs || | |
1285 | lst.idx_lebs != c->lst.idx_lebs || | |
1286 | lst.total_free != c->lst.total_free || | |
1287 | lst.total_dirty != c->lst.total_dirty || | |
1288 | lst.total_used != c->lst.total_used) { | |
1289 | ubifs_err("bad overall accounting"); | |
1290 | ubifs_err("calculated: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld", | |
1291 | lst.empty_lebs, lst.idx_lebs, lst.total_free, | |
1292 | lst.total_dirty, lst.total_used); | |
1293 | ubifs_err("read from lprops: empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld, total_used %lld", | |
1294 | c->lst.empty_lebs, c->lst.idx_lebs, c->lst.total_free, | |
1295 | c->lst.total_dirty, c->lst.total_used); | |
1296 | err = -EINVAL; | |
1297 | goto out; | |
1298 | } | |
1299 | ||
1300 | if (lst.total_dead != c->lst.total_dead || | |
1301 | lst.total_dark != c->lst.total_dark) { | |
1302 | ubifs_err("bad dead/dark space accounting"); | |
1303 | ubifs_err("calculated: total_dead %lld, total_dark %lld", | |
1304 | lst.total_dead, lst.total_dark); | |
1305 | ubifs_err("read from lprops: total_dead %lld, total_dark %lld", | |
1306 | c->lst.total_dead, c->lst.total_dark); | |
1307 | err = -EINVAL; | |
1308 | goto out; | |
1309 | } | |
1310 | ||
1311 | err = dbg_check_cats(c); | |
1312 | out: | |
1313 | return err; | |
1314 | } |