Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-only
2 : /*
3 : * This file is part of UBIFS.
4 : *
5 : * Copyright (C) 2006-2008 Nokia Corporation.
6 : *
7 : * Authors: Adrian Hunter
8 : * Artem Bityutskiy (Битюцкий Артём)
9 : */
10 :
11 : /*
12 : * This file implements the functions that access LEB properties and their
13 : * categories. LEBs are categorized based on the needs of UBIFS, and the
14 : * categories are stored as either heaps or lists to provide a fast way of
15 : * finding a LEB in a particular category. For example, UBIFS may need to find
16 : * an empty LEB for the journal, or a very dirty LEB for garbage collection.
17 : */
18 :
19 : #include "linux_err.h"
20 : #include "bitops.h"
21 : #include "kmem.h"
22 : #include "ubifs.h"
23 : #include "defs.h"
24 : #include "debug.h"
25 : #include "misc.h"
26 :
27 : /**
28 : * get_heap_comp_val - get the LEB properties value for heap comparisons.
29 : * @lprops: LEB properties
30 : * @cat: LEB category
31 : */
32 : static int get_heap_comp_val(struct ubifs_lprops *lprops, int cat)
33 : {
34 24411283 : switch (cat) {
35 : case LPROPS_FREE:
36 : return lprops->free;
37 8951056 : case LPROPS_DIRTY_IDX:
38 8951056 : return lprops->free + lprops->dirty;
39 15311247 : default:
40 15311247 : return lprops->dirty;
41 : }
42 : }
43 :
44 : /**
45 : * move_up_lpt_heap - move a new heap entry up as far as possible.
46 : * @c: UBIFS file-system description object
47 : * @heap: LEB category heap
48 : * @lprops: LEB properties to move
49 : * @cat: LEB category
50 : *
51 : * New entries to a heap are added at the bottom and then moved up until the
52 : * parent's value is greater. In the case of LPT's category heaps, the value
53 : * is either the amount of free space or the amount of dirty space, depending
54 : * on the category.
55 : */
56 1052411 : static void move_up_lpt_heap(__unused struct ubifs_info *c,
57 : struct ubifs_lpt_heap *heap,
58 : struct ubifs_lprops *lprops, int cat)
59 : {
60 : int val1, val2, hpos;
61 :
62 1052411 : hpos = lprops->hpos;
63 1052411 : if (!hpos)
64 : return; /* Already top of the heap */
65 2090076 : val1 = get_heap_comp_val(lprops, cat);
66 : /* Compare to parent and, if greater, move up the heap */
67 : do {
68 2114900 : int ppos = (hpos - 1) / 2;
69 :
70 4229800 : val2 = get_heap_comp_val(heap->arr[ppos], cat);
71 2114900 : if (val2 >= val1)
72 : return;
73 : /* Greater than parent so move up */
74 1083385 : heap->arr[ppos]->hpos = hpos;
75 1083385 : heap->arr[hpos] = heap->arr[ppos];
76 1083385 : heap->arr[ppos] = lprops;
77 1083385 : lprops->hpos = ppos;
78 1083385 : hpos = ppos;
79 1083385 : } while (hpos);
80 : }
81 :
82 : /**
83 : * adjust_lpt_heap - move a changed heap entry up or down the heap.
84 : * @c: UBIFS file-system description object
85 : * @heap: LEB category heap
86 : * @lprops: LEB properties to move
87 : * @hpos: heap position of @lprops
88 : * @cat: LEB category
89 : *
90 : * Changed entries in a heap are moved up or down until the parent's value is
91 : * greater. In the case of LPT's category heaps, the value is either the amount
92 : * of free space or the amount of dirty space, depending on the category.
93 : */
94 3708643 : static void adjust_lpt_heap(__unused struct ubifs_info *c,
95 : struct ubifs_lpt_heap *heap,
96 : struct ubifs_lprops *lprops, int hpos, int cat)
97 : {
98 : int val1, val2, val3, cpos;
99 :
100 7417286 : val1 = get_heap_comp_val(lprops, cat);
101 : /* Compare to parent and, if greater than parent, move up the heap */
102 3708643 : if (hpos) {
103 3615096 : int ppos = (hpos - 1) / 2;
104 :
105 7230192 : val2 = get_heap_comp_val(heap->arr[ppos], cat);
106 3615096 : if (val1 > val2) {
107 : /* Greater than parent so move up */
108 : while (1) {
109 22297 : heap->arr[ppos]->hpos = hpos;
110 22297 : heap->arr[hpos] = heap->arr[ppos];
111 22297 : heap->arr[ppos] = lprops;
112 22297 : lprops->hpos = ppos;
113 22297 : hpos = ppos;
114 22297 : if (!hpos)
115 : return;
116 20705 : ppos = (hpos - 1) / 2;
117 41410 : val2 = get_heap_comp_val(heap->arr[ppos], cat);
118 20705 : if (val1 <= val2)
119 : return;
120 : /* Still greater than parent so keep going */
121 : }
122 : }
123 : }
124 :
125 : /* Not greater than parent, so compare to children */
126 : while (1) {
127 : /* Compare to left child */
128 3713367 : cpos = hpos * 2 + 1;
129 3713367 : if (cpos >= heap->cnt)
130 : return;
131 2804490 : val2 = get_heap_comp_val(heap->arr[cpos], cat);
132 1402245 : if (val1 < val2) {
133 : /* Less than left child, so promote biggest child */
134 24438 : if (cpos + 1 < heap->cnt) {
135 47386 : val3 = get_heap_comp_val(heap->arr[cpos + 1],
136 : cat);
137 23693 : if (val3 > val2)
138 10870 : cpos += 1; /* Right child is bigger */
139 : }
140 24438 : heap->arr[cpos]->hpos = hpos;
141 24438 : heap->arr[hpos] = heap->arr[cpos];
142 24438 : heap->arr[cpos] = lprops;
143 24438 : lprops->hpos = cpos;
144 24438 : hpos = cpos;
145 24438 : continue;
146 : }
147 : /* Compare to right child */
148 1377807 : cpos += 1;
149 1377807 : if (cpos >= heap->cnt)
150 : return;
151 2606578 : val3 = get_heap_comp_val(heap->arr[cpos], cat);
152 1303289 : if (val1 < val3) {
153 : /* Less than right child, so promote right child */
154 988 : heap->arr[cpos]->hpos = hpos;
155 988 : heap->arr[hpos] = heap->arr[cpos];
156 988 : heap->arr[cpos] = lprops;
157 988 : lprops->hpos = cpos;
158 988 : hpos = cpos;
159 988 : continue;
160 : }
161 : return;
162 : }
163 : }
164 :
165 : /**
166 : * add_to_lpt_heap - add LEB properties to a LEB category heap.
167 : * @c: UBIFS file-system description object
168 : * @lprops: LEB properties to add
169 : * @cat: LEB category
170 : *
171 : * This function returns %1 if @lprops is added to the heap for LEB category
172 : * @cat, otherwise %0 is returned because the heap is full.
173 : */
174 6019006 : static int add_to_lpt_heap(struct ubifs_info *c, struct ubifs_lprops *lprops,
175 : int cat)
176 : {
177 6019006 : struct ubifs_lpt_heap *heap = &c->lpt_heap[cat - 1];
178 :
179 6019006 : if (heap->cnt >= heap->max_cnt) {
180 5588837 : const int b = LPT_HEAP_SZ / 2 - 1;
181 : int cpos, val1, val2;
182 :
183 : /* Compare to some other LEB on the bottom of heap */
184 : /* Pick a position kind of randomly */
185 5588837 : cpos = (((size_t)lprops >> 4) & b) + b;
186 : ubifs_assert(c, cpos >= b);
187 : ubifs_assert(c, cpos < LPT_HEAP_SZ);
188 5588837 : ubifs_assert(c, cpos < heap->cnt);
189 :
190 11177674 : val1 = get_heap_comp_val(lprops, cat);
191 11177674 : val2 = get_heap_comp_val(heap->arr[cpos], cat);
192 5588837 : if (val1 > val2) {
193 : struct ubifs_lprops *lp;
194 :
195 622242 : lp = heap->arr[cpos];
196 622242 : lp->flags &= ~LPROPS_CAT_MASK;
197 : lp->flags |= LPROPS_UNCAT;
198 1244484 : list_add(&lp->list, &c->uncat_list);
199 622242 : lprops->hpos = cpos;
200 622242 : heap->arr[cpos] = lprops;
201 622242 : move_up_lpt_heap(c, heap, lprops, cat);
202 622242 : return 1; /* Added to heap */
203 : }
204 : return 0; /* Not added to heap */
205 : } else {
206 430169 : lprops->hpos = heap->cnt++;
207 430169 : heap->arr[lprops->hpos] = lprops;
208 430169 : move_up_lpt_heap(c, heap, lprops, cat);
209 430169 : return 1; /* Added to heap */
210 : }
211 : }
212 :
213 : /**
214 : * remove_from_lpt_heap - remove LEB properties from a LEB category heap.
215 : * @c: UBIFS file-system description object
216 : * @lprops: LEB properties to remove
217 : * @cat: LEB category
218 : */
219 12200 : static void remove_from_lpt_heap(struct ubifs_info *c,
220 : struct ubifs_lprops *lprops, int cat)
221 : {
222 : struct ubifs_lpt_heap *heap;
223 12200 : int hpos = lprops->hpos;
224 :
225 12200 : heap = &c->lpt_heap[cat - 1];
226 12200 : ubifs_assert(c, hpos >= 0 && hpos < heap->cnt);
227 12200 : ubifs_assert(c, heap->arr[hpos] == lprops);
228 12200 : heap->cnt -= 1;
229 12200 : if (hpos < heap->cnt) {
230 8103 : heap->arr[hpos] = heap->arr[heap->cnt];
231 8103 : heap->arr[hpos]->hpos = hpos;
232 8103 : adjust_lpt_heap(c, heap, heap->arr[hpos], hpos, cat);
233 : }
234 12200 : }
235 :
236 : /**
237 : * lpt_heap_replace - replace lprops in a category heap.
238 : * @c: UBIFS file-system description object
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 *new_lprops, int cat)
249 : {
250 : struct ubifs_lpt_heap *heap;
251 557 : int hpos = new_lprops->hpos;
252 :
253 557 : heap = &c->lpt_heap[cat - 1];
254 557 : heap->arr[hpos] = new_lprops;
255 : }
256 :
257 : /**
258 : * ubifs_add_to_cat - add LEB properties to a category list or heap.
259 : * @c: UBIFS file-system description object
260 : * @lprops: LEB properties to add
261 : * @cat: LEB category to which to add
262 : *
263 : * LEB properties are categorized to enable fast find operations.
264 : */
265 8684424 : void ubifs_add_to_cat(struct ubifs_info *c, struct ubifs_lprops *lprops,
266 : int cat)
267 : {
268 8684424 : switch (cat) {
269 6019006 : case LPROPS_DIRTY:
270 : case LPROPS_DIRTY_IDX:
271 : case LPROPS_FREE:
272 6019006 : if (add_to_lpt_heap(c, lprops, cat))
273 : break;
274 : /* No more room on heap so make it un-categorized */
275 : cat = LPROPS_UNCAT;
276 : fallthrough;
277 5285474 : case LPROPS_UNCAT:
278 5285474 : list_add(&lprops->list, &c->uncat_list);
279 : break;
280 2340555 : case LPROPS_EMPTY:
281 2340555 : list_add(&lprops->list, &c->empty_list);
282 : break;
283 5737 : case LPROPS_FREEABLE:
284 11474 : list_add(&lprops->list, &c->freeable_list);
285 5737 : c->freeable_cnt += 1;
286 5737 : break;
287 247 : case LPROPS_FRDI_IDX:
288 247 : list_add(&lprops->list, &c->frdi_idx_list);
289 : break;
290 : default:
291 0 : ubifs_assert(c, 0);
292 : }
293 :
294 8684424 : lprops->flags &= ~LPROPS_CAT_MASK;
295 8684424 : lprops->flags |= cat;
296 8684424 : c->in_a_category_cnt += 1;
297 8684424 : ubifs_assert(c, c->in_a_category_cnt <= c->main_lebs);
298 8684424 : }
299 :
300 : /**
301 : * ubifs_remove_from_cat - remove LEB properties from a category list or heap.
302 : * @c: UBIFS file-system description object
303 : * @lprops: LEB properties to remove
304 : * @cat: LEB category from which to remove
305 : *
306 : * LEB properties are categorized to enable fast find operations.
307 : */
308 1937185 : static void ubifs_remove_from_cat(struct ubifs_info *c,
309 : struct ubifs_lprops *lprops, int cat)
310 : {
311 : switch (cat) {
312 12200 : case LPROPS_DIRTY:
313 : case LPROPS_DIRTY_IDX:
314 : case LPROPS_FREE:
315 12200 : remove_from_lpt_heap(c, lprops, cat);
316 12200 : break;
317 4023 : case LPROPS_FREEABLE:
318 4023 : c->freeable_cnt -= 1;
319 4023 : ubifs_assert(c, c->freeable_cnt >= 0);
320 : fallthrough;
321 : case LPROPS_UNCAT:
322 : case LPROPS_EMPTY:
323 : case LPROPS_FRDI_IDX:
324 3849970 : ubifs_assert(c, !list_empty(&lprops->list));
325 1924985 : list_del(&lprops->list);
326 : break;
327 : default:
328 0 : ubifs_assert(c, 0);
329 : }
330 :
331 1937185 : c->in_a_category_cnt -= 1;
332 1937185 : ubifs_assert(c, c->in_a_category_cnt >= 0);
333 1937185 : }
334 :
335 : /**
336 : * ubifs_replace_cat - replace lprops in a category list or heap.
337 : * @c: UBIFS file-system description object
338 : * @old_lprops: LEB properties to replace
339 : * @new_lprops: LEB properties with which to replace
340 : *
341 : * During commit it is sometimes necessary to copy a pnode (see dirty_cow_pnode)
342 : * and the lprops that the pnode contains. When that happens, references in
343 : * category lists and heaps must be replaced. This function does that.
344 : */
345 7124 : void ubifs_replace_cat(struct ubifs_info *c, struct ubifs_lprops *old_lprops,
346 : struct ubifs_lprops *new_lprops)
347 : {
348 : int cat;
349 :
350 7124 : cat = new_lprops->flags & LPROPS_CAT_MASK;
351 : switch (cat) {
352 557 : case LPROPS_DIRTY:
353 : case LPROPS_DIRTY_IDX:
354 : case LPROPS_FREE:
355 : lpt_heap_replace(c, new_lprops, cat);
356 : break;
357 6567 : case LPROPS_UNCAT:
358 : case LPROPS_EMPTY:
359 : case LPROPS_FREEABLE:
360 : case LPROPS_FRDI_IDX:
361 6567 : list_replace(&old_lprops->list, &new_lprops->list);
362 : break;
363 : default:
364 0 : ubifs_assert(c, 0);
365 : }
366 7124 : }
367 :
368 : /**
369 : * ubifs_ensure_cat - ensure LEB properties are categorized.
370 : * @c: UBIFS file-system description object
371 : * @lprops: LEB properties
372 : *
373 : * A LEB may have fallen off of the bottom of a heap, and ended up as
374 : * un-categorized even though it has enough space for us now. If that is the
375 : * case this function will put the LEB back onto a heap.
376 : */
377 0 : void ubifs_ensure_cat(struct ubifs_info *c, struct ubifs_lprops *lprops)
378 : {
379 0 : int cat = lprops->flags & LPROPS_CAT_MASK;
380 :
381 0 : if (cat != LPROPS_UNCAT)
382 : return;
383 0 : cat = ubifs_categorize_lprops(c, lprops);
384 0 : if (cat == LPROPS_UNCAT)
385 : return;
386 0 : ubifs_remove_from_cat(c, lprops, LPROPS_UNCAT);
387 0 : ubifs_add_to_cat(c, lprops, cat);
388 : }
389 :
390 : /**
391 : * ubifs_categorize_lprops - categorize LEB properties.
392 : * @c: UBIFS file-system description object
393 : * @lprops: LEB properties to categorize
394 : *
395 : * LEB properties are categorized to enable fast find operations. This function
396 : * returns the LEB category to which the LEB properties belong. Note however
397 : * that if the LEB category is stored as a heap and the heap is full, the
398 : * LEB properties may have their category changed to %LPROPS_UNCAT.
399 : */
400 18708401 : int ubifs_categorize_lprops(const struct ubifs_info *c,
401 : const struct ubifs_lprops *lprops)
402 : {
403 18708401 : if (lprops->flags & LPROPS_TAKEN)
404 : return LPROPS_UNCAT;
405 :
406 18584984 : if (lprops->free == c->leb_size) {
407 4567918 : ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
408 : return LPROPS_EMPTY;
409 : }
410 :
411 14017066 : if (lprops->free + lprops->dirty == c->leb_size) {
412 7693 : if (lprops->flags & LPROPS_INDEX)
413 : return LPROPS_FRDI_IDX;
414 : else
415 7409 : return LPROPS_FREEABLE;
416 : }
417 :
418 14009373 : if (lprops->flags & LPROPS_INDEX) {
419 5100250 : if (lprops->dirty + lprops->free >= c->min_idx_node_sz)
420 : return LPROPS_DIRTY_IDX;
421 : } else {
422 8909123 : if (lprops->dirty >= c->dead_wm &&
423 : lprops->dirty > lprops->free)
424 : return LPROPS_DIRTY;
425 443462 : if (lprops->free > 0)
426 : return LPROPS_FREE;
427 : }
428 :
429 377725 : return LPROPS_UNCAT;
430 : }
431 :
432 : /**
433 : * change_category - change LEB properties category.
434 : * @c: UBIFS file-system description object
435 : * @lprops: LEB properties to re-categorize
436 : *
437 : * LEB properties are categorized to enable fast find operations. When the LEB
438 : * properties change they must be re-categorized.
439 : */
440 5786618 : static void change_category(struct ubifs_info *c, struct ubifs_lprops *lprops)
441 : {
442 5786618 : int old_cat = lprops->flags & LPROPS_CAT_MASK;
443 5786618 : int new_cat = ubifs_categorize_lprops(c, lprops);
444 :
445 5786618 : if (old_cat == new_cat) {
446 : struct ubifs_lpt_heap *heap;
447 :
448 : /* lprops on a heap now must be moved up or down */
449 3849433 : if (new_cat < 1 || new_cat > LPROPS_HEAP_CNT)
450 : return; /* Not on a heap */
451 3700540 : heap = &c->lpt_heap[new_cat - 1];
452 3700540 : adjust_lpt_heap(c, heap, lprops, lprops->hpos, new_cat);
453 : } else {
454 1937185 : ubifs_remove_from_cat(c, lprops, old_cat);
455 1937185 : ubifs_add_to_cat(c, lprops, new_cat);
456 : }
457 : }
458 :
459 : /**
460 : * ubifs_calc_dark - calculate LEB dark space size.
461 : * @c: the UBIFS file-system description object
462 : * @spc: amount of free and dirty space in the LEB
463 : *
464 : * This function calculates and returns amount of dark space in an LEB which
465 : * has @spc bytes of free and dirty space.
466 : *
467 : * UBIFS is trying to account the space which might not be usable, and this
468 : * space is called "dark space". For example, if an LEB has only %512 free
469 : * bytes, it is dark space, because it cannot fit a large data node.
470 : */
471 12100853 : int ubifs_calc_dark(const struct ubifs_info *c, int spc)
472 : {
473 12100853 : ubifs_assert(c, !(spc & 7));
474 :
475 12100853 : if (spc < c->dark_wm)
476 : return spc;
477 :
478 : /*
479 : * If we have slightly more space then the dark space watermark, we can
480 : * anyway safely assume it we'll be able to write a node of the
481 : * smallest size there.
482 : */
483 11892578 : if (spc - c->dark_wm < MIN_WRITE_SZ)
484 2168 : return spc - MIN_WRITE_SZ;
485 :
486 : return c->dark_wm;
487 : }
488 :
489 : /**
490 : * is_lprops_dirty - determine if LEB properties are dirty.
491 : * @c: the UBIFS file-system description object
492 : * @lprops: LEB properties to test
493 : */
494 : static int is_lprops_dirty(struct ubifs_info *c, struct ubifs_lprops *lprops)
495 : {
496 : struct ubifs_pnode *pnode;
497 : int pos;
498 :
499 5786618 : pos = (lprops->lnum - c->main_first) & (UBIFS_LPT_FANOUT - 1);
500 5786618 : pnode = (struct ubifs_pnode *)container_of(lprops - pos,
501 : struct ubifs_pnode,
502 : lprops[0]);
503 17359854 : return !test_bit(COW_CNODE, &pnode->flags) &&
504 11573236 : test_bit(DIRTY_CNODE, &pnode->flags);
505 : }
506 :
507 : /**
508 : * ubifs_change_lp - change LEB properties.
509 : * @c: the UBIFS file-system description object
510 : * @lp: LEB properties to change
511 : * @free: new free space amount
512 : * @dirty: new dirty space amount
513 : * @flags: new flags
514 : * @idx_gc_cnt: change to the count of @idx_gc list
515 : *
516 : * This function changes LEB properties (@free, @dirty or @flag). However, the
517 : * property which has the %LPROPS_NC value is not changed. Returns a pointer to
518 : * the updated LEB properties on success and a negative error code on failure.
519 : *
520 : * Note, the LEB properties may have had to be copied (due to COW) and
521 : * consequently the pointer returned may not be the same as the pointer
522 : * passed.
523 : */
524 5786618 : const struct ubifs_lprops *ubifs_change_lp(struct ubifs_info *c,
525 : const struct ubifs_lprops *lp,
526 : int free, int dirty, int flags,
527 : int idx_gc_cnt)
528 : {
529 : /*
530 : * This is the only function that is allowed to change lprops, so we
531 : * discard the "const" qualifier.
532 : */
533 5786618 : struct ubifs_lprops *lprops = (struct ubifs_lprops *)lp;
534 :
535 5786618 : dbg_lp("LEB %d, free %d, dirty %d, flags %d",
536 : lprops->lnum, free, dirty, flags);
537 :
538 5786618 : ubifs_assert(c, mutex_is_locked(&c->lp_mutex));
539 5786618 : ubifs_assert(c, c->lst.empty_lebs >= 0 &&
540 : c->lst.empty_lebs <= c->main_lebs);
541 5786618 : ubifs_assert(c, c->freeable_cnt >= 0);
542 5786618 : ubifs_assert(c, c->freeable_cnt <= c->main_lebs);
543 5786618 : ubifs_assert(c, c->lst.taken_empty_lebs >= 0);
544 5786618 : ubifs_assert(c, c->lst.taken_empty_lebs <= c->lst.empty_lebs);
545 5786618 : ubifs_assert(c, !(c->lst.total_free & 7) && !(c->lst.total_dirty & 7));
546 5786618 : ubifs_assert(c, !(c->lst.total_dead & 7) && !(c->lst.total_dark & 7));
547 5786618 : ubifs_assert(c, !(c->lst.total_used & 7));
548 5786618 : ubifs_assert(c, free == LPROPS_NC || free >= 0);
549 5786618 : ubifs_assert(c, dirty == LPROPS_NC || dirty >= 0);
550 :
551 5785604 : if (!is_lprops_dirty(c, lprops)) {
552 1014 : lprops = ubifs_lpt_lookup_dirty(c, lprops->lnum);
553 1014 : if (IS_ERR(lprops))
554 : return lprops;
555 : } else
556 5785604 : ubifs_assert(c, lprops == ubifs_lpt_lookup_dirty(c, lprops->lnum));
557 :
558 5786618 : ubifs_assert(c, !(lprops->free & 7) && !(lprops->dirty & 7));
559 :
560 5786618 : spin_lock(&c->space_lock);
561 5786618 : if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
562 904 : c->lst.taken_empty_lebs -= 1;
563 :
564 5786618 : if (!(lprops->flags & LPROPS_INDEX)) {
565 : int old_spc;
566 :
567 3532958 : old_spc = lprops->free + lprops->dirty;
568 3532958 : if (old_spc < c->dead_wm)
569 16172 : c->lst.total_dead -= old_spc;
570 : else
571 3516786 : c->lst.total_dark -= ubifs_calc_dark(c, old_spc);
572 :
573 3532958 : c->lst.total_used -= c->leb_size - old_spc;
574 : }
575 :
576 5786618 : if (free != LPROPS_NC) {
577 18155 : free = ALIGN(free, 8);
578 18155 : c->lst.total_free += free - lprops->free;
579 :
580 : /* Increase or decrease empty LEBs counter if needed */
581 18155 : if (free == c->leb_size) {
582 3898 : if (lprops->free != c->leb_size)
583 2122 : c->lst.empty_lebs += 1;
584 14257 : } else if (lprops->free == c->leb_size)
585 1167 : c->lst.empty_lebs -= 1;
586 18155 : lprops->free = free;
587 : }
588 :
589 5786618 : if (dirty != LPROPS_NC) {
590 5779076 : dirty = ALIGN(dirty, 8);
591 5779076 : c->lst.total_dirty += dirty - lprops->dirty;
592 5779076 : lprops->dirty = dirty;
593 : }
594 :
595 5786618 : if (flags != LPROPS_NC) {
596 : /* Take care about indexing LEBs counter if needed */
597 5786618 : if ((lprops->flags & LPROPS_INDEX)) {
598 2253660 : if (!(flags & LPROPS_INDEX))
599 547 : c->lst.idx_lebs -= 1;
600 3532958 : } else if (flags & LPROPS_INDEX)
601 755 : c->lst.idx_lebs += 1;
602 5786618 : lprops->flags = flags;
603 : }
604 :
605 5786618 : if (!(lprops->flags & LPROPS_INDEX)) {
606 : int new_spc;
607 :
608 3532750 : new_spc = lprops->free + lprops->dirty;
609 3532750 : if (new_spc < c->dead_wm)
610 15239 : c->lst.total_dead += new_spc;
611 : else
612 3517511 : c->lst.total_dark += ubifs_calc_dark(c, new_spc);
613 :
614 3532750 : c->lst.total_used += c->leb_size - new_spc;
615 : }
616 :
617 5786618 : if ((lprops->flags & LPROPS_TAKEN) && lprops->free == c->leb_size)
618 2474 : c->lst.taken_empty_lebs += 1;
619 :
620 5786618 : change_category(c, lprops);
621 5786618 : c->idx_gc_cnt += idx_gc_cnt;
622 5786618 : spin_unlock(&c->space_lock);
623 5786618 : return lprops;
624 : }
625 :
626 : /**
627 : * ubifs_get_lp_stats - get lprops statistics.
628 : * @c: UBIFS file-system description object
629 : * @lst: return statistics
630 : */
631 3428 : void ubifs_get_lp_stats(struct ubifs_info *c, struct ubifs_lp_stats *lst)
632 : {
633 3428 : spin_lock(&c->space_lock);
634 3428 : memcpy(lst, &c->lst, sizeof(struct ubifs_lp_stats));
635 3428 : spin_unlock(&c->space_lock);
636 3428 : }
637 :
638 : /**
639 : * ubifs_change_one_lp - change LEB properties.
640 : * @c: the UBIFS file-system description object
641 : * @lnum: LEB to change properties for
642 : * @free: amount of free space
643 : * @dirty: amount of dirty space
644 : * @flags_set: flags to set
645 : * @flags_clean: flags to clean
646 : * @idx_gc_cnt: change to the count of idx_gc list
647 : *
648 : * This function changes properties of LEB @lnum. It is a helper wrapper over
649 : * 'ubifs_change_lp()' which hides lprops get/release. The arguments are the
650 : * same as in case of 'ubifs_change_lp()'. Returns zero in case of success and
651 : * a negative error code in case of failure.
652 : */
653 6063 : int ubifs_change_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
654 : int flags_set, int flags_clean, int idx_gc_cnt)
655 : {
656 6063 : int err = 0, flags;
657 : const struct ubifs_lprops *lp;
658 :
659 6063 : if (!test_lpt_valid_callback(c, lnum, LPROPS_NC, LPROPS_NC, LPROPS_NC,
660 : LPROPS_NC))
661 : return 0;
662 :
663 6063 : ubifs_get_lprops(c);
664 :
665 6063 : lp = ubifs_lpt_lookup_dirty(c, lnum);
666 6063 : if (IS_ERR(lp)) {
667 0 : err = PTR_ERR(lp);
668 0 : if (test_and_clear_failure_reason_callback(c, FR_LPT_CORRUPTED) &&
669 0 : can_ignore_failure_callback(c, FR_LPT_CORRUPTED))
670 0 : err = 0;
671 : goto out;
672 : }
673 :
674 12126 : if (!test_lpt_valid_callback(c, lnum, lp->free, lp->dirty, free, dirty))
675 : goto out;
676 :
677 6063 : flags = (lp->flags | flags_set) & ~flags_clean;
678 6063 : lp = ubifs_change_lp(c, lp, free, dirty, flags, idx_gc_cnt);
679 6063 : if (IS_ERR(lp))
680 0 : err = PTR_ERR(lp);
681 :
682 12126 : out:
683 6063 : ubifs_release_lprops(c);
684 6063 : if (err)
685 0 : ubifs_err(c, "cannot change properties of LEB %d, error %d",
686 : lnum, err);
687 : return err;
688 : }
689 :
690 : /**
691 : * ubifs_update_one_lp - update LEB properties.
692 : * @c: the UBIFS file-system description object
693 : * @lnum: LEB to change properties for
694 : * @free: amount of free space
695 : * @dirty: amount of dirty space to add
696 : * @flags_set: flags to set
697 : * @flags_clean: flags to clean
698 : *
699 : * This function is the same as 'ubifs_change_one_lp()' but @dirty is added to
700 : * current dirty space, not substitutes it.
701 : */
702 5831029 : int ubifs_update_one_lp(struct ubifs_info *c, int lnum, int free, int dirty,
703 : int flags_set, int flags_clean)
704 : {
705 5831029 : int err = 0, flags;
706 : const struct ubifs_lprops *lp;
707 :
708 5831029 : if (!test_lpt_valid_callback(c, lnum, LPROPS_NC, LPROPS_NC, LPROPS_NC,
709 : LPROPS_NC))
710 : return 0;
711 :
712 5767614 : ubifs_get_lprops(c);
713 :
714 5767614 : lp = ubifs_lpt_lookup_dirty(c, lnum);
715 5767614 : if (IS_ERR(lp)) {
716 8 : err = PTR_ERR(lp);
717 16 : if (test_and_clear_failure_reason_callback(c, FR_LPT_CORRUPTED) &&
718 8 : can_ignore_failure_callback(c, FR_LPT_CORRUPTED))
719 8 : err = 0;
720 : goto out;
721 : }
722 :
723 11535212 : if (!test_lpt_valid_callback(c, lnum, lp->free, lp->dirty, free,
724 5767606 : lp->dirty + dirty))
725 : goto out;
726 :
727 5767606 : flags = (lp->flags | flags_set) & ~flags_clean;
728 5767606 : lp = ubifs_change_lp(c, lp, free, lp->dirty + dirty, flags, 0);
729 5767606 : if (IS_ERR(lp))
730 0 : err = PTR_ERR(lp);
731 :
732 11535220 : out:
733 5767614 : ubifs_release_lprops(c);
734 5767614 : if (err)
735 0 : ubifs_err(c, "cannot update properties of LEB %d, error %d",
736 : lnum, err);
737 : return err;
738 : }
739 :
740 : /**
741 : * ubifs_read_one_lp - read LEB properties.
742 : * @c: the UBIFS file-system description object
743 : * @lnum: LEB to read properties for
744 : * @lp: where to store read properties
745 : *
746 : * This helper function reads properties of a LEB @lnum and stores them in @lp.
747 : * Returns zero in case of success and a negative error code in case of
748 : * failure.
749 : */
750 2032 : int ubifs_read_one_lp(struct ubifs_info *c, int lnum, struct ubifs_lprops *lp)
751 : {
752 2032 : int err = 0;
753 : const struct ubifs_lprops *lpp;
754 :
755 2032 : ubifs_get_lprops(c);
756 :
757 2032 : lpp = ubifs_lpt_lookup(c, lnum);
758 2032 : if (IS_ERR(lpp)) {
759 0 : err = PTR_ERR(lpp);
760 0 : ubifs_err(c, "cannot read properties of LEB %d, error %d",
761 : lnum, err);
762 : goto out;
763 : }
764 :
765 2032 : memcpy(lp, lpp, sizeof(struct ubifs_lprops));
766 :
767 2032 : out:
768 2032 : ubifs_release_lprops(c);
769 2032 : return err;
770 : }
771 :
772 : /**
773 : * ubifs_fast_find_free - try to find a LEB with free space quickly.
774 : * @c: the UBIFS file-system description object
775 : *
776 : * This function returns LEB properties for a LEB with free space or %NULL if
777 : * the function is unable to find a LEB quickly.
778 : */
779 12 : const struct ubifs_lprops *ubifs_fast_find_free(struct ubifs_info *c)
780 : {
781 : struct ubifs_lprops *lprops;
782 : struct ubifs_lpt_heap *heap;
783 :
784 12 : ubifs_assert(c, mutex_is_locked(&c->lp_mutex));
785 :
786 12 : heap = &c->lpt_heap[LPROPS_FREE - 1];
787 12 : if (heap->cnt == 0)
788 : return NULL;
789 :
790 2 : lprops = heap->arr[0];
791 2 : ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
792 2 : ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
793 : return lprops;
794 : }
795 :
796 : /**
797 : * ubifs_fast_find_empty - try to find an empty LEB quickly.
798 : * @c: the UBIFS file-system description object
799 : *
800 : * This function returns LEB properties for an empty LEB or %NULL if the
801 : * function is unable to find an empty LEB quickly.
802 : */
803 1079 : const struct ubifs_lprops *ubifs_fast_find_empty(struct ubifs_info *c)
804 : {
805 : struct ubifs_lprops *lprops;
806 :
807 1079 : ubifs_assert(c, mutex_is_locked(&c->lp_mutex));
808 :
809 2158 : if (list_empty(&c->empty_list))
810 : return NULL;
811 :
812 980 : lprops = list_entry(c->empty_list.next, struct ubifs_lprops, list);
813 980 : ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
814 980 : ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
815 980 : ubifs_assert(c, lprops->free == c->leb_size);
816 : return lprops;
817 : }
818 :
819 : /**
820 : * ubifs_fast_find_freeable - try to find a freeable LEB quickly.
821 : * @c: the UBIFS file-system description object
822 : *
823 : * This function returns LEB properties for a freeable LEB or %NULL if the
824 : * function is unable to find a freeable LEB quickly.
825 : */
826 5445 : const struct ubifs_lprops *ubifs_fast_find_freeable(struct ubifs_info *c)
827 : {
828 : struct ubifs_lprops *lprops;
829 :
830 5445 : ubifs_assert(c, mutex_is_locked(&c->lp_mutex));
831 :
832 10890 : if (list_empty(&c->freeable_list))
833 : return NULL;
834 :
835 1924 : lprops = list_entry(c->freeable_list.next, struct ubifs_lprops, list);
836 1924 : ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
837 1924 : ubifs_assert(c, !(lprops->flags & LPROPS_INDEX));
838 1924 : ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);
839 1924 : ubifs_assert(c, c->freeable_cnt > 0);
840 : return lprops;
841 : }
842 :
843 : /**
844 : * ubifs_fast_find_frdi_idx - try to find a freeable index LEB quickly.
845 : * @c: the UBIFS file-system description object
846 : *
847 : * This function returns LEB properties for a freeable index LEB or %NULL if the
848 : * function is unable to find a freeable index LEB quickly.
849 : */
850 3564 : const struct ubifs_lprops *ubifs_fast_find_frdi_idx(struct ubifs_info *c)
851 : {
852 : struct ubifs_lprops *lprops;
853 :
854 3564 : ubifs_assert(c, mutex_is_locked(&c->lp_mutex));
855 :
856 7128 : if (list_empty(&c->frdi_idx_list))
857 : return NULL;
858 :
859 137 : lprops = list_entry(c->frdi_idx_list.next, struct ubifs_lprops, list);
860 137 : ubifs_assert(c, !(lprops->flags & LPROPS_TAKEN));
861 137 : ubifs_assert(c, (lprops->flags & LPROPS_INDEX));
862 137 : ubifs_assert(c, lprops->free + lprops->dirty == c->leb_size);
863 : return lprops;
864 : }
|