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