LCOV - code coverage report
Current view: top level - libubifs - lprops.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 292 312 93.6 %
Date: 2024-06-05 20:10:43 Functions: 19 20 95.0 %
Legend: Lines: hit not hit

          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             : }

Generated by: LCOV version 1.13