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