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