LCOV - code coverage report
Current view: top level - libubifs - lpt.c (source / functions) Hit Total Coverage
Test: a simple test Lines: 863 1040 83.0 %
Date: 2024-06-05 20:10:43 Functions: 41 41 100.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 LEB properties tree (LPT) area. The LPT area
      13             :  * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
      14             :  * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
      15             :  * between the log and the orphan area.
      16             :  *
      17             :  * The LPT area is like a miniature self-contained file system. It is required
      18             :  * that it never runs out of space, is fast to access and update, and scales
      19             :  * logarithmically. The LEB properties tree is implemented as a wandering tree
      20             :  * much like the TNC, and the LPT area has its own garbage collection.
      21             :  *
      22             :  * The LPT has two slightly different forms called the "small model" and the
      23             :  * "big model". The small model is used when the entire LEB properties table
      24             :  * can be written into a single eraseblock. In that case, garbage collection
      25             :  * consists of just writing the whole table, which therefore makes all other
      26             :  * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
      27             :  * selected for garbage collection, which consists of marking the clean nodes in
      28             :  * that LEB as dirty, and then only the dirty nodes are written out. Also, in
      29             :  * the case of the big model, a table of LEB numbers is saved so that the entire
      30             :  * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
      31             :  * mounted.
      32             :  */
      33             : 
      34             : #include "linux_err.h"
      35             : #include "bitops.h"
      36             : #include "kmem.h"
      37             : #include "crc16.h"
      38             : #include "ubifs.h"
      39             : #include "defs.h"
      40             : #include "debug.h"
      41             : 
      42             : /**
      43             :  * do_calc_lpt_geom - calculate sizes for the LPT area.
      44             :  * @c: the UBIFS file-system description object
      45             :  *
      46             :  * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
      47             :  * properties of the flash and whether LPT is "big" (c->big_lpt).
      48             :  */
      49        2924 : static void do_calc_lpt_geom(struct ubifs_info *c)
      50             : {
      51             :         int i, n, bits, per_leb_wastage, max_pnode_cnt;
      52             :         long long sz, tot_wastage;
      53             : 
      54        2924 :         if (c->program_type != MKFS_PROGRAM_TYPE) {
      55        2284 :                 n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;
      56        2284 :                 max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
      57             :         } else {
      58             :                 /*
      59             :                  * Different from linux kernel.
      60             :                  *
      61             :                  * We change it, because 'c->leb_cnt' is not initialized in
      62             :                  * mkfs.ubifs when do_calc_lpt_geom() is invoked, 'c->main_lebs'
      63             :                  * is calculated by 'c->max_leb_cnt', so the 'c->lpt_hght'
      64             :                  * should be calculated by 'c->main_lebs'.
      65             :                  */
      66         640 :                 max_pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
      67             :         }
      68             : 
      69        2924 :         c->lpt_hght = 1;
      70        2924 :         n = UBIFS_LPT_FANOUT;
      71       15270 :         while (n < max_pnode_cnt) {
      72        9422 :                 c->lpt_hght += 1;
      73        9422 :                 n <<= UBIFS_LPT_FANOUT_SHIFT;
      74             :         }
      75             : 
      76        2924 :         c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
      77             : 
      78        2924 :         n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT);
      79        2924 :         c->nnode_cnt = n;
      80       12346 :         for (i = 1; i < c->lpt_hght; i++) {
      81        9422 :                 n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
      82        9422 :                 c->nnode_cnt += n;
      83             :         }
      84             : 
      85        2924 :         c->space_bits = fls(c->leb_size) - 3;
      86        2924 :         c->lpt_lnum_bits = fls(c->lpt_lebs);
      87        2924 :         c->lpt_offs_bits = fls(c->leb_size - 1);
      88        2924 :         c->lpt_spc_bits = fls(c->leb_size);
      89             : 
      90        2924 :         n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);
      91        2924 :         c->pcnt_bits = fls(n - 1);
      92             : 
      93        2924 :         c->lnum_bits = fls(c->max_leb_cnt - 1);
      94             : 
      95        5848 :         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
      96        2924 :                (c->big_lpt ? c->pcnt_bits : 0) +
      97        2924 :                (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
      98        2924 :         c->pnode_sz = (bits + 7) / 8;
      99             : 
     100        2924 :         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
     101             :                (c->big_lpt ? c->pcnt_bits : 0) +
     102        2924 :                (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
     103        2924 :         c->nnode_sz = (bits + 7) / 8;
     104             : 
     105        2924 :         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
     106        2924 :                c->lpt_lebs * c->lpt_spc_bits * 2;
     107        2924 :         c->ltab_sz = (bits + 7) / 8;
     108             : 
     109        2924 :         bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
     110        2924 :                c->lnum_bits * c->lsave_cnt;
     111        2924 :         c->lsave_sz = (bits + 7) / 8;
     112             : 
     113             :         /* Calculate the minimum LPT size */
     114        2924 :         c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
     115        2924 :         c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
     116        2924 :         c->lpt_sz += c->ltab_sz;
     117        2924 :         if (c->big_lpt)
     118          24 :                 c->lpt_sz += c->lsave_sz;
     119             : 
     120             :         /* Add wastage */
     121        2924 :         sz = c->lpt_sz;
     122        2924 :         per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
     123        2924 :         sz += per_leb_wastage;
     124        2924 :         tot_wastage = per_leb_wastage;
     125        5872 :         while (sz > c->leb_size) {
     126          24 :                 sz += per_leb_wastage;
     127          24 :                 sz -= c->leb_size;
     128          24 :                 tot_wastage += per_leb_wastage;
     129             :         }
     130        2924 :         tot_wastage += ALIGN(sz, c->min_io_size) - sz;
     131        2924 :         c->lpt_sz += tot_wastage;
     132        2924 : }
     133             : 
     134             : /**
     135             :  * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
     136             :  * @c: the UBIFS file-system description object
     137             :  *
     138             :  * This function returns %0 on success and a negative error code on failure.
     139             :  */
     140        2284 : int ubifs_calc_lpt_geom(struct ubifs_info *c)
     141             : {
     142             :         int lebs_needed;
     143             :         long long sz;
     144             : 
     145        2284 :         do_calc_lpt_geom(c);
     146             : 
     147             :         /* Verify that lpt_lebs is big enough */
     148        2284 :         sz = c->lpt_sz * 2; /* Must have at least 2 times the size */
     149        4568 :         lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
     150        2284 :         if (lebs_needed > c->lpt_lebs) {
     151           0 :                 ubifs_err(c, "too few LPT LEBs");
     152             :                 return -EINVAL;
     153             :         }
     154             : 
     155             :         /* Verify that ltab fits in a single LEB (since ltab is a single node */
     156        2284 :         if (c->ltab_sz > c->leb_size) {
     157           0 :                 ubifs_err(c, "LPT ltab too big");
     158             :                 return -EINVAL;
     159             :         }
     160             : 
     161        2284 :         c->check_lpt_free = c->big_lpt;
     162        2284 :         return 0;
     163             : }
     164             : 
     165             : /**
     166             :  * ubifs_calc_dflt_lpt_geom - calculate default LPT geometry.
     167             :  * @c: the UBIFS file-system description object
     168             :  * @main_lebs: number of main area LEBs is passed and returned here
     169             :  * @big_lpt: whether the LPT area is "big" is returned here
     170             :  *
     171             :  * The size of the LPT area depends on parameters that themselves are dependent
     172             :  * on the size of the LPT area. This function, successively recalculates the LPT
     173             :  * area geometry until the parameters and resultant geometry are consistent.
     174             :  *
     175             :  * This function returns %0 on success and a negative error code on failure.
     176             :  */
     177         640 : int ubifs_calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt)
     178             : {
     179             :         int i, lebs_needed;
     180             :         long long sz;
     181             : 
     182             :         /* Start by assuming the minimum number of LPT LEBs */
     183         640 :         c->lpt_lebs = UBIFS_MIN_LPT_LEBS;
     184         640 :         c->main_lebs = *main_lebs - c->lpt_lebs;
     185         640 :         if (c->main_lebs <= 0)
     186             :                 return -EINVAL;
     187             : 
     188             :         /* And assume we will use the small LPT model */
     189         640 :         c->big_lpt = 0;
     190             : 
     191             :         /*
     192             :          * Calculate the geometry based on assumptions above and then see if it
     193             :          * makes sense
     194             :          */
     195         640 :         do_calc_lpt_geom(c);
     196             : 
     197             :         /* Small LPT model must have lpt_sz < leb_size */
     198         640 :         if (c->lpt_sz > c->leb_size) {
     199             :                 /* Nope, so try again using big LPT model */
     200           0 :                 c->big_lpt = 1;
     201           0 :                 do_calc_lpt_geom(c);
     202             :         }
     203             : 
     204             :         /* Now check there are enough LPT LEBs */
     205         640 :         for (i = 0; i < 64 ; i++) {
     206         640 :                 sz = c->lpt_sz * 4; /* Allow 4 times the size */
     207        1280 :                 lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
     208         640 :                 if (lebs_needed > c->lpt_lebs) {
     209             :                         /* Not enough LPT LEBs so try again with more */
     210           0 :                         c->lpt_lebs = lebs_needed;
     211           0 :                         c->main_lebs = *main_lebs - c->lpt_lebs;
     212           0 :                         if (c->main_lebs <= 0)
     213             :                                 return -EINVAL;
     214           0 :                         do_calc_lpt_geom(c);
     215           0 :                         continue;
     216             :                 }
     217         640 :                 if (c->ltab_sz > c->leb_size) {
     218           0 :                         ubifs_err(c, "LPT ltab too big");
     219             :                         return -EINVAL;
     220             :                 }
     221         640 :                 *main_lebs = c->main_lebs;
     222         640 :                 *big_lpt = c->big_lpt;
     223         640 :                 return 0;
     224             :         }
     225             :         return -EINVAL;
     226             : }
     227             : 
     228             : /**
     229             :  * pack_bits - pack bit fields end-to-end.
     230             :  * @c: UBIFS file-system description object
     231             :  * @addr: address at which to pack (passed and next address returned)
     232             :  * @pos: bit position at which to pack (passed and next position returned)
     233             :  * @val: value to pack
     234             :  * @nrbits: number of bits of value to pack (1-32)
     235             :  */
     236     5036107 : static void pack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, uint32_t val, int nrbits)
     237             : {
     238     5036107 :         uint8_t *p = *addr;
     239     5036107 :         int b = *pos;
     240             : 
     241     5036107 :         ubifs_assert(c, nrbits > 0);
     242     5036107 :         ubifs_assert(c, nrbits <= 32);
     243     5036107 :         ubifs_assert(c, *pos >= 0);
     244     5036107 :         ubifs_assert(c, *pos < 8);
     245     5036107 :         ubifs_assert(c, (val >> nrbits) == 0 || nrbits == 32);
     246     5036107 :         if (b) {
     247     3594294 :                 *p |= ((uint8_t)val) << b;
     248     3594294 :                 nrbits += b;
     249     3594294 :                 if (nrbits > 8) {
     250     2467733 :                         *++p = (uint8_t)(val >>= (8 - b));
     251     2467733 :                         if (nrbits > 16) {
     252     1801490 :                                 *++p = (uint8_t)(val >>= 8);
     253     1801490 :                                 if (nrbits > 24) {
     254        8780 :                                         *++p = (uint8_t)(val >>= 8);
     255        8780 :                                         if (nrbits > 32)
     256           0 :                                                 *++p = (uint8_t)(val >>= 8);
     257             :                                 }
     258             :                         }
     259             :                 }
     260             :         } else {
     261     1441813 :                 *p = (uint8_t)val;
     262     1441813 :                 if (nrbits > 8) {
     263      595396 :                         *++p = (uint8_t)(val >>= 8);
     264      595396 :                         if (nrbits > 16) {
     265        8664 :                                 *++p = (uint8_t)(val >>= 8);
     266        8664 :                                 if (nrbits > 24)
     267           0 :                                         *++p = (uint8_t)(val >>= 8);
     268             :                         }
     269             :                 }
     270             :         }
     271     5036107 :         b = nrbits & 7;
     272     5036107 :         if (b == 0)
     273     1286544 :                 p++;
     274     5036107 :         *addr = p;
     275     5036107 :         *pos = b;
     276     5036107 : }
     277             : 
     278             : /**
     279             :  * ubifs_unpack_bits - unpack bit fields.
     280             :  * @c: UBIFS file-system description object
     281             :  * @addr: address at which to unpack (passed and next address returned)
     282             :  * @pos: bit position at which to unpack (passed and next position returned)
     283             :  * @nrbits: number of bits of value to unpack (1-32)
     284             :  *
     285             :  * This functions returns the value unpacked.
     286             :  */
     287    52255336 : uint32_t ubifs_unpack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, int nrbits)
     288             : {
     289    52255336 :         const int k = 32 - nrbits;
     290    52255336 :         uint8_t *p = *addr;
     291    52255336 :         int b = *pos;
     292    52255336 :         uint32_t val = 0;
     293    52255336 :         const int bytes = (nrbits + b + 7) >> 3;
     294             : 
     295    52255336 :         ubifs_assert(c, nrbits > 0);
     296    52255336 :         ubifs_assert(c, nrbits <= 32);
     297    52255336 :         ubifs_assert(c, *pos >= 0);
     298    52255336 :         ubifs_assert(c, *pos < 8);
     299    52255336 :         if (b) {
     300    25729771 :                 switch (bytes) {
     301     9596407 :                 case 2:
     302     9596407 :                         val = p[1];
     303     9596407 :                         break;
     304    10019363 :                 case 3:
     305    10019363 :                         val = p[1] | ((uint32_t)p[2] << 8);
     306    10019363 :                         break;
     307       47717 :                 case 4:
     308       95434 :                         val = p[1] | ((uint32_t)p[2] << 8) |
     309       47717 :                                      ((uint32_t)p[3] << 16);
     310       47717 :                         break;
     311           0 :                 case 5:
     312           0 :                         val = p[1] | ((uint32_t)p[2] << 8) |
     313           0 :                                      ((uint32_t)p[3] << 16) |
     314           0 :                                      ((uint32_t)p[4] << 24);
     315             :                 }
     316    25729771 :                 val <<= (8 - b);
     317    25729771 :                 val |= *p >> b;
     318    25729771 :                 nrbits += b;
     319             :         } else {
     320    26525565 :                 switch (bytes) {
     321    16898374 :                 case 1:
     322    16898374 :                         val = p[0];
     323    16898374 :                         break;
     324     9579489 :                 case 2:
     325     9579489 :                         val = p[0] | ((uint32_t)p[1] << 8);
     326     9579489 :                         break;
     327       47702 :                 case 3:
     328       95404 :                         val = p[0] | ((uint32_t)p[1] << 8) |
     329       47702 :                                      ((uint32_t)p[2] << 16);
     330       47702 :                         break;
     331           0 :                 case 4:
     332           0 :                         val = p[0] | ((uint32_t)p[1] << 8) |
     333           0 :                                      ((uint32_t)p[2] << 16) |
     334           0 :                                      ((uint32_t)p[3] << 24);
     335           0 :                         break;
     336             :                 }
     337             :         }
     338    52255336 :         val <<= k;
     339    52255336 :         val >>= k;
     340    52255336 :         b = nrbits & 7;
     341    52255336 :         p += nrbits >> 3;
     342    52255336 :         *addr = p;
     343    52255336 :         *pos = b;
     344    52255336 :         ubifs_assert(c, (val >> nrbits) == 0 || nrbits - b == 32);
     345    52255336 :         return val;
     346             : }
     347             : 
     348             : /**
     349             :  * ubifs_pack_pnode - pack all the bit fields of a pnode.
     350             :  * @c: UBIFS file-system description object
     351             :  * @buf: buffer into which to pack
     352             :  * @pnode: pnode to pack
     353             :  */
     354      241169 : void ubifs_pack_pnode(struct ubifs_info *c, void *buf,
     355             :                       struct ubifs_pnode *pnode)
     356             : {
     357      241169 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
     358      241169 :         int i, pos = 0;
     359             :         uint16_t crc;
     360             : 
     361      241169 :         pack_bits(c, &addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);
     362      241169 :         if (c->big_lpt)
     363       18769 :                 pack_bits(c, &addr, &pos, pnode->num, c->pcnt_bits);
     364      964676 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
     365      964676 :                 pack_bits(c, &addr, &pos, pnode->lprops[i].free >> 3,
     366             :                           c->space_bits);
     367      964676 :                 pack_bits(c, &addr, &pos, pnode->lprops[i].dirty >> 3,
     368             :                           c->space_bits);
     369      964676 :                 if (pnode->lprops[i].flags & LPROPS_INDEX)
     370      257201 :                         pack_bits(c, &addr, &pos, 1, 1);
     371             :                 else
     372      707475 :                         pack_bits(c, &addr, &pos, 0, 1);
     373             :         }
     374      241169 :         crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
     375      241169 :                     c->pnode_sz - UBIFS_LPT_CRC_BYTES);
     376      241169 :         addr = buf;
     377      241169 :         pos = 0;
     378      241169 :         pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
     379      241169 : }
     380             : 
     381             : /**
     382             :  * ubifs_pack_nnode - pack all the bit fields of a nnode.
     383             :  * @c: UBIFS file-system description object
     384             :  * @buf: buffer into which to pack
     385             :  * @nnode: nnode to pack
     386             :  */
     387      160367 : void ubifs_pack_nnode(struct ubifs_info *c, void *buf,
     388             :                       struct ubifs_nnode *nnode)
     389             : {
     390      160367 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
     391      160367 :         int i, pos = 0;
     392             :         uint16_t crc;
     393             : 
     394      160367 :         pack_bits(c, &addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);
     395      160367 :         if (c->big_lpt)
     396       10128 :                 pack_bits(c, &addr, &pos, nnode->num, c->pcnt_bits);
     397      641468 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
     398      641468 :                 int lnum = nnode->nbranch[i].lnum;
     399             : 
     400      641468 :                 if (lnum == 0)
     401       12894 :                         lnum = c->lpt_last + 1;
     402      641468 :                 pack_bits(c, &addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);
     403      641468 :                 pack_bits(c, &addr, &pos, nnode->nbranch[i].offs,
     404             :                           c->lpt_offs_bits);
     405             :         }
     406      160367 :         crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
     407      160367 :                     c->nnode_sz - UBIFS_LPT_CRC_BYTES);
     408      160367 :         addr = buf;
     409      160367 :         pos = 0;
     410      160367 :         pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
     411      160367 : }
     412             : 
     413             : /**
     414             :  * ubifs_pack_ltab - pack the LPT's own lprops table.
     415             :  * @c: UBIFS file-system description object
     416             :  * @buf: buffer into which to pack
     417             :  * @ltab: LPT's own lprops table to pack
     418             :  */
     419        2667 : void ubifs_pack_ltab(struct ubifs_info *c, void *buf,
     420             :                      struct ubifs_lpt_lprops *ltab)
     421             : {
     422        2667 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
     423        2667 :         int i, pos = 0;
     424             :         uint16_t crc;
     425             : 
     426        2667 :         pack_bits(c, &addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);
     427        8169 :         for (i = 0; i < c->lpt_lebs; i++) {
     428        5502 :                 pack_bits(c, &addr, &pos, ltab[i].free, c->lpt_spc_bits);
     429        5502 :                 pack_bits(c, &addr, &pos, ltab[i].dirty, c->lpt_spc_bits);
     430             :         }
     431        2667 :         crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
     432        2667 :                     c->ltab_sz - UBIFS_LPT_CRC_BYTES);
     433        2667 :         addr = buf;
     434        2667 :         pos = 0;
     435        2667 :         pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
     436        2667 : }
     437             : 
     438             : /**
     439             :  * ubifs_pack_lsave - pack the LPT's save table.
     440             :  * @c: UBIFS file-system description object
     441             :  * @buf: buffer into which to pack
     442             :  * @lsave: LPT's save table to pack
     443             :  */
     444          42 : void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave)
     445             : {
     446          42 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
     447          42 :         int i, pos = 0;
     448             :         uint16_t crc;
     449             : 
     450          42 :         pack_bits(c, &addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);
     451       10794 :         for (i = 0; i < c->lsave_cnt; i++)
     452       10752 :                 pack_bits(c, &addr, &pos, lsave[i], c->lnum_bits);
     453          42 :         crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
     454          42 :                     c->lsave_sz - UBIFS_LPT_CRC_BYTES);
     455          42 :         addr = buf;
     456          42 :         pos = 0;
     457          42 :         pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
     458          42 : }
     459             : 
     460             : /**
     461             :  * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
     462             :  * @c: UBIFS file-system description object
     463             :  * @lnum: LEB number to which to add dirty space
     464             :  * @dirty: amount of dirty space to add
     465             :  */
     466      307417 : void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)
     467             : {
     468      307417 :         if (!dirty || !lnum)
     469             :                 return;
     470      307417 :         dbg_lp("LEB %d add %d to %d",
     471             :                lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);
     472      307417 :         ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
     473      307417 :         c->ltab[lnum - c->lpt_first].dirty += dirty;
     474             : }
     475             : 
     476             : /**
     477             :  * set_ltab - set LPT LEB properties.
     478             :  * @c: UBIFS file-system description object
     479             :  * @lnum: LEB number
     480             :  * @free: amount of free space
     481             :  * @dirty: amount of dirty space
     482             :  */
     483         822 : static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
     484             : {
     485         822 :         dbg_lp("LEB %d free %d dirty %d to %d %d",
     486             :                lnum, c->ltab[lnum - c->lpt_first].free,
     487             :                c->ltab[lnum - c->lpt_first].dirty, free, dirty);
     488         822 :         ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
     489         822 :         c->ltab[lnum - c->lpt_first].free = free;
     490         822 :         c->ltab[lnum - c->lpt_first].dirty = dirty;
     491         822 : }
     492             : 
     493             : /**
     494             :  * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
     495             :  * @c: UBIFS file-system description object
     496             :  * @nnode: nnode for which to add dirt
     497             :  */
     498      138799 : void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)
     499             : {
     500      138799 :         struct ubifs_nnode *np = nnode->parent;
     501             : 
     502      138799 :         if (np)
     503      136183 :                 ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,
     504             :                                    c->nnode_sz);
     505             :         else {
     506        2616 :                 ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);
     507        2616 :                 if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
     508        2616 :                         c->lpt_drty_flgs |= LTAB_DIRTY;
     509        2616 :                         ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
     510             :                 }
     511             :         }
     512      138799 : }
     513             : 
     514             : /**
     515             :  * add_pnode_dirt - add dirty space to LPT LEB properties.
     516             :  * @c: UBIFS file-system description object
     517             :  * @pnode: pnode for which to add dirt
     518             :  */
     519             : static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
     520             : {
     521       80474 :         ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
     522             :                            c->pnode_sz);
     523             : }
     524             : 
     525             : /**
     526             :  * ubifs_calc_nnode_num - calculate nnode number.
     527             :  * @row: the row in the tree (root is zero)
     528             :  * @col: the column in the row (leftmost is zero)
     529             :  *
     530             :  * The nnode number is a number that uniquely identifies a nnode and can be used
     531             :  * easily to traverse the tree from the root to that nnode.
     532             :  *
     533             :  * This function calculates and returns the nnode number for the nnode at @row
     534             :  * and @col.
     535             :  */
     536     2688428 : int ubifs_calc_nnode_num(int row, int col)
     537             : {
     538             :         int num, bits;
     539             : 
     540     2688428 :         num = 1;
     541    17118739 :         while (row--) {
     542    11713053 :                 bits = (col & (UBIFS_LPT_FANOUT - 1));
     543    11713053 :                 col >>= UBIFS_LPT_FANOUT_SHIFT;
     544    11713053 :                 num <<= UBIFS_LPT_FANOUT_SHIFT;
     545    11713053 :                 num |= bits;
     546             :         }
     547     2688428 :         return num;
     548             : }
     549             : 
     550             : /**
     551             :  * calc_nnode_num_from_parent - calculate nnode number.
     552             :  * @c: UBIFS file-system description object
     553             :  * @parent: parent nnode
     554             :  * @iip: index in parent
     555             :  *
     556             :  * The nnode number is a number that uniquely identifies a nnode and can be used
     557             :  * easily to traverse the tree from the root to that nnode.
     558             :  *
     559             :  * This function calculates and returns the nnode number based on the parent's
     560             :  * nnode number and the index in parent.
     561             :  */
     562             : static int calc_nnode_num_from_parent(const struct ubifs_info *c,
     563             :                                       struct ubifs_nnode *parent, int iip)
     564             : {
     565             :         int num, shft;
     566             : 
     567      548296 :         if (!parent)
     568             :                 return 1;
     569      546051 :         shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;
     570      546051 :         num = parent->num ^ (1 << shft);
     571      546051 :         num |= (UBIFS_LPT_FANOUT + iip) << shft;
     572             :         return num;
     573             : }
     574             : 
     575             : /**
     576             :  * calc_pnode_num_from_parent - calculate pnode number.
     577             :  * @c: UBIFS file-system description object
     578             :  * @parent: parent nnode
     579             :  * @iip: index in parent
     580             :  *
     581             :  * The pnode number is a number that uniquely identifies a pnode and can be used
     582             :  * easily to traverse the tree from the root to that pnode.
     583             :  *
     584             :  * This function calculates and returns the pnode number based on the parent's
     585             :  * nnode number and the index in parent.
     586             :  */
     587             : static int calc_pnode_num_from_parent(const struct ubifs_info *c,
     588             :                                       struct ubifs_nnode *parent, int iip)
     589             : {
     590     1618599 :         int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;
     591             : 
     592     9142168 :         for (i = 0; i < n; i++) {
     593     7523569 :                 num <<= UBIFS_LPT_FANOUT_SHIFT;
     594     7523569 :                 num |= pnum & (UBIFS_LPT_FANOUT - 1);
     595     7523569 :                 pnum >>= UBIFS_LPT_FANOUT_SHIFT;
     596             :         }
     597     1618599 :         num <<= UBIFS_LPT_FANOUT_SHIFT;
     598     1618599 :         num |= iip;
     599             :         return num;
     600             : }
     601             : 
     602             : /**
     603             :  * ubifs_create_lpt - create lpt acccording to lprops array.
     604             :  * @c: UBIFS file-system description object
     605             :  * @lps: array of logical eraseblock properties
     606             :  * @lp_cnt: the length of @lps
     607             :  * @hash: hash of the LPT is returned here
     608             :  * @free_ltab: %true means to release c->ltab after creating lpt
     609             :  *
     610             :  * This function creates lpt, the pnode will be initialized based on
     611             :  * corresponding elements in @lps. If there are no corresponding lprops
     612             :  * (eg. @lp_cnt is smaller than @c->main_lebs), the LEB property is set
     613             :  * as free state.
     614             :  */
     615         810 : int ubifs_create_lpt(struct ubifs_info *c, struct ubifs_lprops *lps, int lp_cnt,
     616             :                      u8 *hash, bool free_ltab)
     617             : {
     618         810 :         int lnum, err = 0, i, j, cnt, len, alen, row;
     619             :         int blnum, boffs, bsz, bcnt;
     620         810 :         struct ubifs_pnode *pnode = NULL;
     621         810 :         struct ubifs_nnode *nnode = NULL;
     622         810 :         void *buf = NULL, *p;
     623         810 :         struct ubifs_lpt_lprops *ltab = NULL;
     624         810 :         int *lsave = NULL;
     625             :         struct shash_desc *desc;
     626             : 
     627         810 :         desc = ubifs_hash_get_desc(c);
     628         810 :         if (IS_ERR(desc))
     629           0 :                 return PTR_ERR(desc);
     630             : 
     631         810 :         lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_KERNEL);
     632         810 :         pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);
     633         810 :         nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);
     634         810 :         buf = vmalloc(c->leb_size);
     635        1620 :         ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
     636             :                                   c->lpt_lebs));
     637         810 :         if (!pnode || !nnode || !buf || !ltab || !lsave) {
     638             :                 err = -ENOMEM;
     639             :                 goto out;
     640             :         }
     641             : 
     642         810 :         ubifs_assert(c, !c->ltab);
     643         810 :         c->ltab = ltab; /* Needed by set_ltab */
     644             : 
     645             :         /* Initialize LPT's own lprops */
     646        2478 :         for (i = 0; i < c->lpt_lebs; i++) {
     647        1668 :                 ltab[i].free = c->leb_size;
     648        1668 :                 ltab[i].dirty = 0;
     649        1668 :                 ltab[i].tgc = 0;
     650        1668 :                 ltab[i].cmt = 0;
     651             :         }
     652             : 
     653         810 :         lnum = c->lpt_first;
     654         810 :         p = buf;
     655         810 :         len = 0;
     656             :         /*
     657             :          * Different from linux kernel. The number of leaf nodes (pnodes) should
     658             :          * be calculated by the number of current main LEBs. The 'c->pnode_cnt'
     659             :          * may not be equal to 'DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT)' in
     660             :          * mkfs when 'c->leb_cnt != c->max_leb_cnt' is true.
     661             :          */
     662         810 :         cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
     663             : 
     664             :         /*
     665             :          * To calculate the internal node branches, we keep information about
     666             :          * the level below.
     667             :          */
     668         810 :         blnum = lnum; /* LEB number of level below */
     669         810 :         boffs = 0; /* Offset of level below */
     670         810 :         bcnt = cnt; /* Number of nodes in level below */
     671         810 :         bsz = c->pnode_sz; /* Size of nodes in level below */
     672             : 
     673             :         /* Add all pnodes */
     674       80746 :         for (i = 0; i < cnt; i++) {
     675       79936 :                 if (len + c->pnode_sz > c->leb_size) {
     676          12 :                         alen = ALIGN(len, c->min_io_size);
     677          12 :                         set_ltab(c, lnum, c->leb_size - alen, alen - len);
     678             :                         /*
     679             :                          * Different from linux kernel.
     680             :                          * The mkfs may partially write data into a certain LEB
     681             :                          * of file image, the left unwritten area in the LEB
     682             :                          * should be filled with '0xFF'.
     683             :                          */
     684          12 :                         if (c->libubi) {
     685          12 :                                 memset(p, 0xff, alen - len);
     686          12 :                                 err = ubifs_leb_change(c, lnum++, buf, alen);
     687             :                         } else {
     688           0 :                                 memset(p, 0xff, c->leb_size - len);
     689           0 :                                 err = ubifs_leb_change(c, lnum++, buf, c->leb_size);
     690             :                         }
     691          12 :                         if (err)
     692             :                                 goto out;
     693             :                         p = buf;
     694             :                         len = 0;
     695             :                 }
     696             :                 /* Fill in the pnode */
     697      399680 :                 for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
     698      319744 :                         int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j;
     699             : 
     700      319744 :                         if (k < lp_cnt) {
     701      318598 :                                 pnode->lprops[j].free = lps[k].free;
     702      318598 :                                 pnode->lprops[j].dirty = lps[k].dirty;
     703      318598 :                                 pnode->lprops[j].flags = lps[k].flags;
     704             :                         } else {
     705        1146 :                                 pnode->lprops[j].free = c->leb_size;
     706        1146 :                                 pnode->lprops[j].dirty = 0;
     707        1146 :                                 pnode->lprops[j].flags = 0;
     708             :                         }
     709             :                 }
     710       79936 :                 ubifs_pack_pnode(c, p, pnode);
     711       79936 :                 err = ubifs_shash_update(c, desc, p, c->pnode_sz);
     712       79936 :                 if (err)
     713             :                         goto out;
     714             : 
     715       79936 :                 p += c->pnode_sz;
     716       79936 :                 len += c->pnode_sz;
     717             :                 /*
     718             :                  * pnodes are simply numbered left to right starting at zero,
     719             :                  * which means the pnode number can be used easily to traverse
     720             :                  * down the tree to the corresponding pnode.
     721             :                  */
     722       79936 :                 pnode->num += 1;
     723             :         }
     724             : 
     725             :         /*
     726             :          * Different from linux kernel. The 'c->lpt_hght' is calculated by the
     727             :          * 'c->max_leb_cnt', according to the implementation of function
     728             :          * ubifs_pnode_lookup(), there are at least 'c->lpt_hght' cnodes should
     729             :          * be created, otherwise the LPT looking up could be failed after
     730             :          * mouting.
     731             :          */
     732         810 :         row = c->lpt_hght - 1;
     733             :         /* Add all nnodes, one level at a time */
     734             :         while (1) {
     735             :                 /* Number of internal nodes (nnodes) at next level */
     736        5606 :                 cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);
     737        3208 :                 if (cnt == 0)
     738           0 :                         cnt = 1;
     739       32038 :                 for (i = 0; i < cnt; i++) {
     740       28830 :                         if (len + c->nnode_sz > c->leb_size) {
     741           0 :                                 alen = ALIGN(len, c->min_io_size);
     742           0 :                                 set_ltab(c, lnum, c->leb_size - alen,
     743             :                                             alen - len);
     744             :                                 /*
     745             :                                  * Different from linux kernel.
     746             :                                  * The mkfs may partially write data into a certain LEB
     747             :                                  * of file image, the left unwritten area in the LEB
     748             :                                  * should be filled with '0xFF'.
     749             :                                  */
     750           0 :                                 if (c->libubi) {
     751           0 :                                         memset(p, 0xff, alen - len);
     752           0 :                                         err = ubifs_leb_change(c, lnum++, buf, alen);
     753             :                                 } else {
     754           0 :                                         memset(p, 0xff, c->leb_size - len);
     755           0 :                                         err = ubifs_leb_change(c, lnum++, buf, c->leb_size);
     756             :                                 }
     757           0 :                                 if (err)
     758             :                                         goto out;
     759             :                                 p = buf;
     760             :                                 len = 0;
     761             :                         }
     762             :                         /* Only 1 nnode at this level, so it is the root */
     763       28830 :                         if (row == 0) {
     764         810 :                                 c->lpt_lnum = lnum;
     765         810 :                                 c->lpt_offs = len;
     766             :                         }
     767             :                         /* Set branches to the level below */
     768      115320 :                         for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
     769      115320 :                                 if (bcnt) {
     770      107956 :                                         if (boffs + bsz > c->leb_size) {
     771          12 :                                                 blnum += 1;
     772          12 :                                                 boffs = 0;
     773             :                                         }
     774      107956 :                                         nnode->nbranch[j].lnum = blnum;
     775      107956 :                                         nnode->nbranch[j].offs = boffs;
     776      107956 :                                         boffs += bsz;
     777      107956 :                                         bcnt--;
     778             :                                 } else {
     779        7364 :                                         nnode->nbranch[j].lnum = 0;
     780        7364 :                                         nnode->nbranch[j].offs = 0;
     781             :                                 }
     782             :                         }
     783       28830 :                         nnode->num = ubifs_calc_nnode_num(row, i);
     784       28830 :                         ubifs_pack_nnode(c, p, nnode);
     785       28830 :                         p += c->nnode_sz;
     786       28830 :                         len += c->nnode_sz;
     787             :                 }
     788             :                 /* Row zero  is the top row */
     789        3208 :                 if (row == 0)
     790             :                         break;
     791             :                 /* Update the information about the level below */
     792        2398 :                 bcnt = cnt;
     793        2398 :                 bsz = c->nnode_sz;
     794        2398 :                 row -= 1;
     795             :         }
     796             : 
     797         810 :         if (c->big_lpt) {
     798             :                 /* Need to add LPT's save table */
     799          12 :                 if (len + c->lsave_sz > c->leb_size) {
     800           0 :                         alen = ALIGN(len, c->min_io_size);
     801           0 :                         set_ltab(c, lnum, c->leb_size - alen, alen - len);
     802             :                         /*
     803             :                          * Different from linux kernel.
     804             :                          * The mkfs may partially write data into a certain LEB
     805             :                          * of file image, the left unwritten area in the LEB
     806             :                          * should be filled with '0xFF'.
     807             :                          */
     808           0 :                         if (c->libubi) {
     809           0 :                                 memset(p, 0xff, alen - len);
     810           0 :                                 err = ubifs_leb_change(c, lnum++, buf, alen);
     811             :                         } else {
     812           0 :                                 memset(p, 0xff, c->leb_size - len);
     813           0 :                                 err = ubifs_leb_change(c, lnum++, buf, c->leb_size);
     814             :                         }
     815           0 :                         if (err)
     816             :                                 goto out;
     817             :                         p = buf;
     818             :                         len = 0;
     819             :                 }
     820             : 
     821          12 :                 c->lsave_lnum = lnum;
     822          12 :                 c->lsave_offs = len;
     823             : 
     824        3084 :                 for (i = 0; i < c->lsave_cnt && i < c->main_lebs; i++)
     825        3072 :                         lsave[i] = c->main_first + i;
     826           0 :                 for (; i < c->lsave_cnt; i++)
     827           0 :                         lsave[i] = c->main_first;
     828             : 
     829          12 :                 ubifs_pack_lsave(c, p, lsave);
     830          12 :                 p += c->lsave_sz;
     831          12 :                 len += c->lsave_sz;
     832             :         }
     833             : 
     834             :         /* Need to add LPT's own LEB properties table */
     835         810 :         if (len + c->ltab_sz > c->leb_size) {
     836           0 :                 alen = ALIGN(len, c->min_io_size);
     837           0 :                 set_ltab(c, lnum, c->leb_size - alen, alen - len);
     838             :                 /*
     839             :                  * Different from linux kernel.
     840             :                  * The mkfs may partially write data into a certain LEB
     841             :                  * of file image, the left unwritten area in the LEB
     842             :                  * should be filled with '0xFF'.
     843             :                  */
     844           0 :                 if (c->libubi) {
     845           0 :                         memset(p, 0xff, alen - len);
     846           0 :                         err = ubifs_leb_change(c, lnum++, buf, alen);
     847             :                 } else {
     848           0 :                         memset(p, 0xff, c->leb_size - len);
     849           0 :                         err = ubifs_leb_change(c, lnum++, buf, c->leb_size);
     850             :                 }
     851           0 :                 if (err)
     852             :                         goto out;
     853             :                 p = buf;
     854             :                 len = 0;
     855             :         }
     856             : 
     857         810 :         c->ltab_lnum = lnum;
     858         810 :         c->ltab_offs = len;
     859             : 
     860             :         /* Update ltab before packing it */
     861         810 :         len += c->ltab_sz;
     862         810 :         alen = ALIGN(len, c->min_io_size);
     863         810 :         set_ltab(c, lnum, c->leb_size - alen, alen - len);
     864             : 
     865         810 :         ubifs_pack_ltab(c, p, ltab);
     866         810 :         p += c->ltab_sz;
     867             : 
     868             :         /* Write remaining buffer */
     869             :         /*
     870             :          * Different from linux kernel.
     871             :          * The mkfs may partially write data into a certain LEB
     872             :          * of file image, the left unwritten area in the LEB
     873             :          * should be filled with '0xFF'.
     874             :          */
     875         810 :         if (c->libubi) {
     876         554 :                 memset(p, 0xff, alen - len);
     877         554 :                 err = ubifs_leb_change(c, lnum, buf, alen);
     878             :         } else {
     879         256 :                 memset(p, 0xff, c->leb_size - len);
     880         256 :                 err = ubifs_leb_change(c, lnum, buf, c->leb_size);
     881             :         }
     882         810 :         if (err)
     883             :                 goto out;
     884             : 
     885         810 :         if (c->big_lpt && c->lsave)
     886           0 :                 memcpy(c->lsave, lsave, c->lsave_cnt * sizeof(int));
     887             : 
     888         810 :         err = ubifs_shash_final(c, desc, hash);
     889         810 :         if (err)
     890             :                 goto out;
     891             : 
     892         810 :         c->nhead_lnum = lnum;
     893         810 :         c->nhead_offs = ALIGN(len, c->min_io_size);
     894             : 
     895         810 :         dbg_lp("space_bits %d", c->space_bits);
     896         810 :         dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
     897         810 :         dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
     898         810 :         dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
     899         810 :         dbg_lp("pcnt_bits %d", c->pcnt_bits);
     900         810 :         dbg_lp("lnum_bits %d", c->lnum_bits);
     901         810 :         dbg_lp("pnode_sz %d", c->pnode_sz);
     902         810 :         dbg_lp("nnode_sz %d", c->nnode_sz);
     903         810 :         dbg_lp("ltab_sz %d", c->ltab_sz);
     904         810 :         dbg_lp("lsave_sz %d", c->lsave_sz);
     905         810 :         dbg_lp("lsave_cnt %d", c->lsave_cnt);
     906         810 :         dbg_lp("lpt_hght %d", c->lpt_hght);
     907         810 :         dbg_lp("big_lpt %u", c->big_lpt);
     908         810 :         dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
     909         810 :         dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
     910         810 :         dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
     911         810 :         if (c->big_lpt)
     912          12 :                 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
     913        1620 : out:
     914         810 :         if (free_ltab || err) {
     915         798 :                 c->ltab = NULL;
     916         798 :                 vfree(ltab);
     917             :         }
     918         810 :         kfree(desc);
     919         810 :         kfree(lsave);
     920         810 :         vfree(buf);
     921         810 :         kfree(nnode);
     922         810 :         kfree(pnode);
     923         810 :         return err;
     924             : }
     925             : 
     926             : /**
     927             :  * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
     928             :  * @c: UBIFS file-system description object
     929             :  * @pnode: pnode
     930             :  *
     931             :  * When a pnode is loaded into memory, the LEB properties it contains are added,
     932             :  * by this function, to the LEB category lists and heaps.
     933             :  */
     934     1618581 : static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
     935             : {
     936             :         int i;
     937             : 
     938     8091498 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
     939     6473664 :                 int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
     940     6473664 :                 int lnum = pnode->lprops[i].lnum;
     941             : 
     942     6473664 :                 if (!lnum)
     943             :                         return;
     944     6472917 :                 ubifs_add_to_cat(c, &pnode->lprops[i], cat);
     945             :         }
     946             : }
     947             : 
     948             : /**
     949             :  * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
     950             :  * @c: UBIFS file-system description object
     951             :  * @old_pnode: pnode copied
     952             :  * @new_pnode: pnode copy
     953             :  *
     954             :  * During commit it is sometimes necessary to copy a pnode
     955             :  * (see dirty_cow_pnode).  When that happens, references in
     956             :  * category lists and heaps must be replaced.  This function does that.
     957             :  */
     958             : static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
     959             :                          struct ubifs_pnode *new_pnode)
     960             : {
     961             :         int i;
     962             : 
     963        7124 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
     964        7124 :                 if (!new_pnode->lprops[i].lnum)
     965             :                         return;
     966        7124 :                 ubifs_replace_cat(c, &old_pnode->lprops[i],
     967             :                                   &new_pnode->lprops[i]);
     968             :         }
     969             : }
     970             : 
     971             : /**
     972             :  * check_lpt_crc - check LPT node crc is correct.
     973             :  * @c: UBIFS file-system description object
     974             :  * @buf: buffer containing node
     975             :  * @len: length of node
     976             :  *
     977             :  * This function returns %0 on success and a negative error code on failure.
     978             :  */
     979     2086539 : static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len)
     980             : {
     981     2086539 :         int pos = 0;
     982     2086539 :         uint8_t *addr = buf;
     983             :         uint16_t crc, calc_crc;
     984             : 
     985     2086539 :         crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);
     986     2086539 :         calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
     987     2086539 :                          len - UBIFS_LPT_CRC_BYTES);
     988     2086539 :         if (crc != calc_crc) {
     989           0 :                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
     990           0 :                 ubifs_err(c, "invalid crc in LPT node: crc %hx calc %hx",
     991             :                           crc, calc_crc);
     992           0 :                 dump_stack();
     993           0 :                 return -EINVAL;
     994             :         }
     995             :         return 0;
     996             : }
     997             : 
     998             : /**
     999             :  * check_lpt_type - check LPT node type is correct.
    1000             :  * @c: UBIFS file-system description object
    1001             :  * @addr: address of type bit field is passed and returned updated here
    1002             :  * @pos: position of type bit field is passed and returned updated here
    1003             :  * @type: expected type
    1004             :  *
    1005             :  * This function returns %0 on success and a negative error code on failure.
    1006             :  */
    1007     2086590 : static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr,
    1008             :                           int *pos, int type)
    1009             : {
    1010             :         int node_type;
    1011             : 
    1012     2086590 :         node_type = ubifs_unpack_bits(c, addr, pos, UBIFS_LPT_TYPE_BITS);
    1013     2086590 :         if (node_type != type) {
    1014          51 :                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1015          51 :                 ubifs_err(c, "invalid type (%d) in LPT node type %d",
    1016             :                           node_type, type);
    1017          51 :                 dump_stack();
    1018          51 :                 return -EINVAL;
    1019             :         }
    1020             :         return 0;
    1021             : }
    1022             : 
    1023             : /**
    1024             :  * unpack_pnode - unpack a pnode.
    1025             :  * @c: UBIFS file-system description object
    1026             :  * @buf: buffer containing packed pnode to unpack
    1027             :  * @pnode: pnode structure to fill
    1028             :  *
    1029             :  * This function returns %0 on success and a negative error code on failure.
    1030             :  */
    1031     1556087 : static int unpack_pnode(const struct ubifs_info *c, void *buf,
    1032             :                         struct ubifs_pnode *pnode)
    1033             : {
    1034     1556087 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
    1035     1556087 :         int i, pos = 0, err;
    1036             : 
    1037     1556087 :         err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE);
    1038     1556087 :         if (err)
    1039             :                 return err;
    1040     1556084 :         if (c->big_lpt)
    1041       14818 :                 pnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
    1042     6224336 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1043     6224336 :                 struct ubifs_lprops * const lprops = &pnode->lprops[i];
    1044             : 
    1045     6224336 :                 lprops->free = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
    1046     6224336 :                 lprops->free <<= 3;
    1047     6224336 :                 lprops->dirty = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
    1048     6224336 :                 lprops->dirty <<= 3;
    1049             : 
    1050     6224336 :                 if (ubifs_unpack_bits(c, &addr, &pos, 1))
    1051     1475423 :                         lprops->flags = LPROPS_INDEX;
    1052             :                 else
    1053     4748913 :                         lprops->flags = 0;
    1054     6224336 :                 lprops->flags |= ubifs_categorize_lprops(c, lprops);
    1055             :         }
    1056     1556084 :         err = check_lpt_crc(c, buf, c->pnode_sz);
    1057     1556084 :         return err;
    1058             : }
    1059             : 
    1060             : /**
    1061             :  * ubifs_unpack_nnode - unpack a nnode.
    1062             :  * @c: UBIFS file-system description object
    1063             :  * @buf: buffer containing packed nnode to unpack
    1064             :  * @nnode: nnode structure to fill
    1065             :  *
    1066             :  * This function returns %0 on success and a negative error code on failure.
    1067             :  */
    1068      528214 : int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
    1069             :                        struct ubifs_nnode *nnode)
    1070             : {
    1071      528214 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
    1072      528214 :         int i, pos = 0, err;
    1073             : 
    1074      528214 :         err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE);
    1075      528214 :         if (err)
    1076             :                 return err;
    1077      528190 :         if (c->big_lpt)
    1078        6959 :                 nnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
    1079     2112760 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1080             :                 int lnum;
    1081             : 
    1082     4225520 :                 lnum = ubifs_unpack_bits(c, &addr, &pos, c->lpt_lnum_bits) +
    1083     2112760 :                        c->lpt_first;
    1084     2112760 :                 if (lnum == c->lpt_last + 1)
    1085        9587 :                         lnum = 0;
    1086     2112760 :                 nnode->nbranch[i].lnum = lnum;
    1087     2112760 :                 nnode->nbranch[i].offs = ubifs_unpack_bits(c, &addr, &pos,
    1088             :                                                      c->lpt_offs_bits);
    1089             :         }
    1090      528190 :         err = check_lpt_crc(c, buf, c->nnode_sz);
    1091      528190 :         return err;
    1092             : }
    1093             : 
    1094             : /**
    1095             :  * unpack_ltab - unpack the LPT's own lprops table.
    1096             :  * @c: UBIFS file-system description object
    1097             :  * @buf: buffer from which to unpack
    1098             :  *
    1099             :  * This function returns %0 on success and a negative error code on failure.
    1100             :  */
    1101        2265 : static int unpack_ltab(const struct ubifs_info *c, void *buf)
    1102             : {
    1103        2265 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
    1104        2265 :         int i, pos = 0, err;
    1105             : 
    1106        2265 :         err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB);
    1107        2265 :         if (err)
    1108             :                 return err;
    1109        4578 :         for (i = 0; i < c->lpt_lebs; i++) {
    1110        4578 :                 int free = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
    1111        4578 :                 int dirty = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
    1112             : 
    1113        4578 :                 if (free < 0 || free > c->leb_size || dirty < 0 ||
    1114        4578 :                     dirty > c->leb_size || free + dirty > c->leb_size) {
    1115             :                         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1116             :                         return -EINVAL;
    1117             :                 }
    1118             : 
    1119        4578 :                 c->ltab[i].free = free;
    1120        4578 :                 c->ltab[i].dirty = dirty;
    1121        4578 :                 c->ltab[i].tgc = 0;
    1122        4578 :                 c->ltab[i].cmt = 0;
    1123             :         }
    1124        2241 :         err = check_lpt_crc(c, buf, c->ltab_sz);
    1125        2241 :         return err;
    1126             : }
    1127             : 
    1128             : /**
    1129             :  * unpack_lsave - unpack the LPT's save table.
    1130             :  * @c: UBIFS file-system description object
    1131             :  * @buf: buffer from which to unpack
    1132             :  *
    1133             :  * This function returns %0 on success and a negative error code on failure.
    1134             :  */
    1135          24 : static int unpack_lsave(const struct ubifs_info *c, void *buf)
    1136             : {
    1137          24 :         uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
    1138          24 :         int i, pos = 0, err;
    1139             : 
    1140          24 :         err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE);
    1141          24 :         if (err)
    1142             :                 return err;
    1143        6144 :         for (i = 0; i < c->lsave_cnt; i++) {
    1144        6144 :                 int lnum = ubifs_unpack_bits(c, &addr, &pos, c->lnum_bits);
    1145             : 
    1146        6144 :                 if (lnum < c->main_first || lnum >= c->leb_cnt) {
    1147             :                         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1148             :                         return -EINVAL;
    1149             :                 }
    1150        6144 :                 c->lsave[i] = lnum;
    1151             :         }
    1152          24 :         err = check_lpt_crc(c, buf, c->lsave_sz);
    1153          24 :         return err;
    1154             : }
    1155             : 
    1156             : /**
    1157             :  * validate_nnode - validate a nnode.
    1158             :  * @c: UBIFS file-system description object
    1159             :  * @nnode: nnode to validate
    1160             :  * @parent: parent nnode (or NULL for the root nnode)
    1161             :  * @iip: index in parent
    1162             :  *
    1163             :  * This function returns %0 on success and a negative error code on failure.
    1164             :  */
    1165      548302 : static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
    1166             :                           struct ubifs_nnode *parent, int iip)
    1167             : {
    1168             :         int i, lvl, max_offs;
    1169             : 
    1170      548302 :         if (c->big_lpt) {
    1171        6959 :                 int num = calc_nnode_num_from_parent(c, parent, iip);
    1172             : 
    1173        6959 :                 if (nnode->num != num)
    1174             :                         goto out_invalid;
    1175             :         }
    1176      548302 :         lvl = parent ? parent->level - 1 : c->lpt_hght;
    1177      548302 :         if (lvl < 1)
    1178             :                 goto out_invalid;
    1179      548302 :         if (lvl == 1)
    1180      407982 :                 max_offs = c->leb_size - c->pnode_sz;
    1181             :         else
    1182      140320 :                 max_offs = c->leb_size - c->nnode_sz;
    1183     2741510 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1184     2193208 :                 int lnum = nnode->nbranch[i].lnum;
    1185     2193208 :                 int offs = nnode->nbranch[i].offs;
    1186             : 
    1187     2193208 :                 if (lnum == 0) {
    1188       90035 :                         if (offs != 0)
    1189             :                                 goto out_invalid;
    1190       90035 :                         continue;
    1191             :                 }
    1192     4206346 :                 if (lnum < c->lpt_first || lnum > c->lpt_last)
    1193             :                         goto out_invalid;
    1194     2103173 :                 if (offs < 0 || offs > max_offs)
    1195             :                         goto out_invalid;
    1196             :         }
    1197             :         return 0;
    1198             : 
    1199           0 : out_invalid:
    1200             :         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1201             :         return -EINVAL;
    1202             : }
    1203             : 
    1204             : /**
    1205             :  * validate_pnode - validate a pnode.
    1206             :  * @c: UBIFS file-system description object
    1207             :  * @pnode: pnode to validate
    1208             :  * @parent: parent nnode
    1209             :  * @iip: index in parent
    1210             :  *
    1211             :  * This function returns %0 on success and a negative error code on failure.
    1212             :  */
    1213     1618596 : static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
    1214             :                           struct ubifs_nnode *parent, int iip)
    1215             : {
    1216             :         int i;
    1217             : 
    1218     1618596 :         if (c->big_lpt) {
    1219       29636 :                 int num = calc_pnode_num_from_parent(c, parent, iip);
    1220             : 
    1221       14818 :                 if (pnode->num != num)
    1222             :                         goto out_invalid;
    1223             :         }
    1224     6474348 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1225     6474363 :                 int free = pnode->lprops[i].free;
    1226     6474363 :                 int dirty = pnode->lprops[i].dirty;
    1227             : 
    1228    25897452 :                 if (free < 0 || free > c->leb_size || free % c->min_io_size ||
    1229     6474363 :                     (free & 7))
    1230             :                         goto out_invalid;
    1231    19423081 :                 if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
    1232             :                         goto out_invalid;
    1233     6474355 :                 if (dirty + free > c->leb_size)
    1234             :                         goto out_invalid;
    1235             :         }
    1236             :         return 0;
    1237             : 
    1238          15 : out_invalid:
    1239             :         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1240             :         return -EINVAL;
    1241             : }
    1242             : 
    1243             : /**
    1244             :  * set_pnode_lnum - set LEB numbers on a pnode.
    1245             :  * @c: UBIFS file-system description object
    1246             :  * @pnode: pnode to update
    1247             :  *
    1248             :  * This function calculates the LEB numbers for the LEB properties it contains
    1249             :  * based on the pnode number.
    1250             :  */
    1251             : static void set_pnode_lnum(const struct ubifs_info *c,
    1252             :                            struct ubifs_pnode *pnode)
    1253             : {
    1254             :         int i, lnum;
    1255             : 
    1256     1618581 :         lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
    1257     8091498 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1258     6473664 :                 if (lnum >= c->leb_cnt)
    1259             :                         return;
    1260     6472917 :                 pnode->lprops[i].lnum = lnum++;
    1261             :         }
    1262             : }
    1263             : 
    1264             : /**
    1265             :  * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
    1266             :  * @c: UBIFS file-system description object
    1267             :  * @parent: parent nnode (or NULL for the root)
    1268             :  * @iip: index in parent
    1269             :  *
    1270             :  * This function returns %0 on success and a negative error code on failure.
    1271             :  */
    1272      548320 : int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
    1273             : {
    1274      548320 :         struct ubifs_nbranch *branch = NULL;
    1275      548320 :         struct ubifs_nnode *nnode = NULL;
    1276      548320 :         void *buf = c->lpt_nod_buf;
    1277             :         int err, lnum, offs;
    1278             : 
    1279      548320 :         if (parent) {
    1280      546045 :                 branch = &parent->nbranch[iip];
    1281      546045 :                 lnum = branch->lnum;
    1282      546045 :                 offs = branch->offs;
    1283             :         } else {
    1284        2275 :                 lnum = c->lpt_lnum;
    1285        2275 :                 offs = c->lpt_offs;
    1286             :         }
    1287      548320 :         nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
    1288      548320 :         if (!nnode) {
    1289             :                 err = -ENOMEM;
    1290             :                 goto out;
    1291             :         }
    1292      548320 :         if (lnum == 0) {
    1293             :                 /*
    1294             :                  * This nnode was not written which just means that the LEB
    1295             :                  * properties in the subtree below it describe empty LEBs. We
    1296             :                  * make the nnode as though we had read it, which in fact means
    1297             :                  * doing almost nothing.
    1298             :                  */
    1299       20112 :                 if (c->big_lpt)
    1300           0 :                         nnode->num = calc_nnode_num_from_parent(c, parent, iip);
    1301             :         } else {
    1302      528208 :                 err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1);
    1303      528208 :                 if (err) {
    1304           0 :                         if (err == -EBADMSG)
    1305             :                                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1306             :                         goto out;
    1307             :                 }
    1308      528208 :                 err = ubifs_unpack_nnode(c, buf, nnode);
    1309      528208 :                 if (err)
    1310             :                         goto out;
    1311             :         }
    1312      548296 :         err = validate_nnode(c, nnode, parent, iip);
    1313      548296 :         if (err)
    1314             :                 goto out;
    1315      548296 :         if (!c->big_lpt)
    1316      541337 :                 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
    1317      548296 :         if (parent) {
    1318      546045 :                 branch->nnode = nnode;
    1319      546045 :                 nnode->level = parent->level - 1;
    1320             :         } else {
    1321        2251 :                 c->nroot = nnode;
    1322        2251 :                 nnode->level = c->lpt_hght;
    1323             :         }
    1324      548296 :         nnode->parent = parent;
    1325      548296 :         nnode->iip = iip;
    1326      548296 :         return 0;
    1327             : 
    1328          24 : out:
    1329          24 :         ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs);
    1330          24 :         dump_stack();
    1331          24 :         kfree(nnode);
    1332          24 :         return err;
    1333             : }
    1334             : 
    1335             : /**
    1336             :  * read_pnode - read a pnode from flash and link it to the tree in memory.
    1337             :  * @c: UBIFS file-system description object
    1338             :  * @parent: parent nnode
    1339             :  * @iip: index in parent
    1340             :  *
    1341             :  * This function returns %0 on success and a negative error code on failure.
    1342             :  */
    1343     1618597 : static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
    1344             : {
    1345             :         struct ubifs_nbranch *branch;
    1346     1618597 :         struct ubifs_pnode *pnode = NULL;
    1347     1618597 :         void *buf = c->lpt_nod_buf;
    1348             :         int err, lnum, offs;
    1349             : 
    1350     1618597 :         branch = &parent->nbranch[iip];
    1351     1618597 :         lnum = branch->lnum;
    1352     1618597 :         offs = branch->offs;
    1353     1618597 :         pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
    1354     1618597 :         if (!pnode)
    1355             :                 return -ENOMEM;
    1356             : 
    1357     1618597 :         if (lnum == 0) {
    1358             :                 /*
    1359             :                  * This pnode was not written which just means that the LEB
    1360             :                  * properties in it describe empty LEBs. We make the pnode as
    1361             :                  * though we had read it.
    1362             :                  */
    1363             :                 int i;
    1364             : 
    1365       62512 :                 if (c->big_lpt)
    1366           0 :                         pnode->num = calc_pnode_num_from_parent(c, parent, iip);
    1367      250048 :                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1368      250048 :                         struct ubifs_lprops * const lprops = &pnode->lprops[i];
    1369             : 
    1370      250048 :                         lprops->free = c->leb_size;
    1371      250048 :                         lprops->flags = ubifs_categorize_lprops(c, lprops);
    1372             :                 }
    1373             :         } else {
    1374     1556085 :                 err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1);
    1375     1556085 :                 if (err) {
    1376           0 :                         if (err == -EBADMSG)
    1377             :                                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1378             :                         goto out;
    1379             :                 }
    1380     1556085 :                 err = unpack_pnode(c, buf, pnode);
    1381     1556085 :                 if (err)
    1382             :                         goto out;
    1383             :         }
    1384     1618594 :         err = validate_pnode(c, pnode, parent, iip);
    1385     1618594 :         if (err)
    1386             :                 goto out;
    1387     1618579 :         if (!c->big_lpt)
    1388     3207522 :                 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
    1389     1618579 :         branch->pnode = pnode;
    1390     1618579 :         pnode->parent = parent;
    1391     1618579 :         pnode->iip = iip;
    1392     1618579 :         set_pnode_lnum(c, pnode);
    1393     1618579 :         c->pnodes_have += 1;
    1394     1618579 :         return 0;
    1395             : 
    1396          18 : out:
    1397          18 :         ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs);
    1398          18 :         ubifs_dump_pnode(c, pnode, parent, iip);
    1399          18 :         dump_stack();
    1400          36 :         ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
    1401          18 :         kfree(pnode);
    1402          18 :         return err;
    1403             : }
    1404             : 
    1405             : /**
    1406             :  * read_ltab - read LPT's own lprops table.
    1407             :  * @c: UBIFS file-system description object
    1408             :  *
    1409             :  * This function returns %0 on success and a negative error code on failure.
    1410             :  */
    1411        2265 : static int read_ltab(struct ubifs_info *c)
    1412             : {
    1413             :         int err;
    1414             :         void *buf;
    1415             : 
    1416        2265 :         buf = vmalloc(c->ltab_sz);
    1417        2265 :         if (!buf)
    1418             :                 return -ENOMEM;
    1419        2265 :         err = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1);
    1420        2265 :         if (err) {
    1421           0 :                 if (err == -EBADMSG)
    1422             :                         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1423             :                 goto out;
    1424             :         }
    1425        2265 :         err = unpack_ltab(c, buf);
    1426        2265 : out:
    1427        2265 :         vfree(buf);
    1428        2265 :         return err;
    1429             : }
    1430             : 
    1431             : /**
    1432             :  * read_lsave - read LPT's save table.
    1433             :  * @c: UBIFS file-system description object
    1434             :  *
    1435             :  * This function returns %0 on success and a negative error code on failure.
    1436             :  */
    1437          24 : static int read_lsave(struct ubifs_info *c)
    1438             : {
    1439             :         int err, i;
    1440             :         void *buf;
    1441             : 
    1442          24 :         buf = vmalloc(c->lsave_sz);
    1443          24 :         if (!buf)
    1444             :                 return -ENOMEM;
    1445          24 :         err = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs,
    1446             :                              c->lsave_sz, 1);
    1447          24 :         if (err) {
    1448           0 :                 if (err == -EBADMSG)
    1449             :                         set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    1450             :                 goto out;
    1451             :         }
    1452          24 :         err = unpack_lsave(c, buf);
    1453          24 :         if (err)
    1454             :                 goto out;
    1455        6144 :         for (i = 0; i < c->lsave_cnt; i++) {
    1456        6144 :                 int lnum = c->lsave[i];
    1457             :                 struct ubifs_lprops *lprops;
    1458             : 
    1459             :                 /*
    1460             :                  * Due to automatic resizing, the values in the lsave table
    1461             :                  * could be beyond the volume size - just ignore them.
    1462             :                  */
    1463        6144 :                 if (lnum >= c->leb_cnt)
    1464           0 :                         continue;
    1465        6144 :                 lprops = ubifs_lpt_lookup(c, lnum);
    1466        6144 :                 if (IS_ERR(lprops)) {
    1467           0 :                         err = PTR_ERR(lprops);
    1468           0 :                         goto out;
    1469             :                 }
    1470             :         }
    1471          24 : out:
    1472          24 :         vfree(buf);
    1473          24 :         return err;
    1474             : }
    1475             : 
    1476             : /**
    1477             :  * ubifs_get_nnode - get a nnode.
    1478             :  * @c: UBIFS file-system description object
    1479             :  * @parent: parent nnode (or NULL for the root)
    1480             :  * @iip: index in parent
    1481             :  *
    1482             :  * This function returns a pointer to the nnode on success or a negative error
    1483             :  * code on failure.
    1484             :  */
    1485      563377 : struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
    1486             :                                     struct ubifs_nnode *parent, int iip)
    1487             : {
    1488             :         struct ubifs_nbranch *branch;
    1489             :         struct ubifs_nnode *nnode;
    1490             :         int err;
    1491             : 
    1492 29482464346 :         branch = &parent->nbranch[iip];
    1493 29482464346 :         nnode = branch->nnode;
    1494 29482464346 :         if (nnode)
    1495             :                 return nnode;
    1496      546045 :         err = ubifs_read_nnode(c, parent, iip);
    1497      546045 :         if (err)
    1498           0 :                 return ERR_PTR(err);
    1499      546045 :         return branch->nnode;
    1500             : }
    1501             : 
    1502             : /**
    1503             :  * ubifs_get_pnode - get a pnode.
    1504             :  * @c: UBIFS file-system description object
    1505             :  * @parent: parent nnode
    1506             :  * @iip: index in parent
    1507             :  *
    1508             :  * This function returns a pointer to the pnode on success or a negative error
    1509             :  * code on failure.
    1510             :  */
    1511  6052125699 : struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
    1512             :                                     struct ubifs_nnode *parent, int iip)
    1513             : {
    1514             :         struct ubifs_nbranch *branch;
    1515             :         struct ubifs_pnode *pnode;
    1516             :         int err;
    1517             : 
    1518  6052125699 :         branch = &parent->nbranch[iip];
    1519  6052125699 :         pnode = branch->pnode;
    1520  6052125699 :         if (pnode)
    1521             :                 return pnode;
    1522     1618597 :         err = read_pnode(c, parent, iip);
    1523     1618597 :         if (err)
    1524          36 :                 return ERR_PTR(err);
    1525     1618579 :         update_cats(c, branch->pnode);
    1526     1618579 :         return branch->pnode;
    1527             : }
    1528             : 
    1529             : /**
    1530             :  * ubifs_pnode_lookup - lookup a pnode in the LPT.
    1531             :  * @c: UBIFS file-system description object
    1532             :  * @i: pnode number (0 to (main_lebs - 1) / UBIFS_LPT_FANOUT)
    1533             :  *
    1534             :  * This function returns a pointer to the pnode on success or a negative
    1535             :  * error code on failure.
    1536             :  */
    1537  6038921719 : struct ubifs_pnode *ubifs_pnode_lookup(struct ubifs_info *c, int i)
    1538             : {
    1539             :         int err, h, iip, shft;
    1540             :         struct ubifs_nnode *nnode;
    1541             : 
    1542  6038921719 :         if (!c->nroot) {
    1543         152 :                 err = ubifs_read_nnode(c, NULL, 0);
    1544         152 :                 if (err)
    1545           0 :                         return ERR_PTR(err);
    1546             :         }
    1547  6038921719 :         i <<= UBIFS_LPT_FANOUT_SHIFT;
    1548  6038921719 :         nnode = c->nroot;
    1549  6038921719 :         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
    1550 35466112538 :         for (h = 1; h < c->lpt_hght; h++) {
    1551 29427190819 :                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    1552 29427190819 :                 shft -= UBIFS_LPT_FANOUT_SHIFT;
    1553 29427190819 :                 nnode = ubifs_get_nnode(c, nnode, iip);
    1554 29427190819 :                 if (IS_ERR(nnode))
    1555             :                         return ERR_CAST(nnode);
    1556             :         }
    1557  6038921719 :         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    1558  6038921719 :         return ubifs_get_pnode(c, nnode, iip);
    1559             : }
    1560             : 
    1561             : /**
    1562             :  * ubifs_lpt_lookup - lookup LEB properties in the LPT.
    1563             :  * @c: UBIFS file-system description object
    1564             :  * @lnum: LEB number to lookup
    1565             :  *
    1566             :  * This function returns a pointer to the LEB properties on success or a
    1567             :  * negative error code on failure.
    1568             :  */
    1569      410677 : struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
    1570             : {
    1571             :         int i, iip;
    1572             :         struct ubifs_pnode *pnode;
    1573             : 
    1574      410677 :         i = lnum - c->main_first;
    1575      410677 :         pnode = ubifs_pnode_lookup(c, i >> UBIFS_LPT_FANOUT_SHIFT);
    1576      410677 :         if (IS_ERR(pnode))
    1577             :                 return ERR_CAST(pnode);
    1578      410677 :         iip = (i & (UBIFS_LPT_FANOUT - 1));
    1579      410677 :         dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
    1580             :                pnode->lprops[iip].free, pnode->lprops[iip].dirty,
    1581             :                pnode->lprops[iip].flags);
    1582      410677 :         return &pnode->lprops[iip];
    1583             : }
    1584             : 
    1585             : /**
    1586             :  * dirty_cow_nnode - ensure a nnode is not being committed.
    1587             :  * @c: UBIFS file-system description object
    1588             :  * @nnode: nnode to check
    1589             :  *
    1590             :  * Returns dirtied nnode on success or negative error code on failure.
    1591             :  */
    1592    66280408 : static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
    1593             :                                            struct ubifs_nnode *nnode)
    1594             : {
    1595             :         struct ubifs_nnode *n;
    1596             :         int i;
    1597             : 
    1598   132560816 :         if (!test_bit(COW_CNODE, &nnode->flags)) {
    1599             :                 /* nnode is not being committed */
    1600    66380852 :                 if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
    1601      105670 :                         c->dirty_nn_cnt += 1;
    1602      105670 :                         ubifs_add_nnode_dirt(c, nnode);
    1603             :                 }
    1604             :                 return nnode;
    1605             :         }
    1606             : 
    1607             :         /* nnode is being committed, so copy it */
    1608        5226 :         n = kmemdup(nnode, sizeof(struct ubifs_nnode), GFP_NOFS);
    1609        5226 :         if (unlikely(!n))
    1610             :                 return ERR_PTR(-ENOMEM);
    1611             : 
    1612        5226 :         n->cnext = NULL;
    1613       10452 :         __set_bit(DIRTY_CNODE, &n->flags);
    1614       10452 :         __clear_bit(COW_CNODE, &n->flags);
    1615             : 
    1616             :         /* The children now have new parent */
    1617       26130 :         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1618       20904 :                 struct ubifs_nbranch *branch = &n->nbranch[i];
    1619             : 
    1620       20904 :                 if (branch->cnode)
    1621       20752 :                         branch->cnode->parent = n;
    1622             :         }
    1623             : 
    1624       10452 :         ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &nnode->flags));
    1625       10452 :         __set_bit(OBSOLETE_CNODE, &nnode->flags);
    1626             : 
    1627        5226 :         c->dirty_nn_cnt += 1;
    1628        5226 :         ubifs_add_nnode_dirt(c, nnode);
    1629        5226 :         if (nnode->parent)
    1630        4959 :                 nnode->parent->nbranch[n->iip].nnode = n;
    1631             :         else
    1632         267 :                 c->nroot = n;
    1633             :         return n;
    1634             : }
    1635             : 
    1636             : /**
    1637             :  * dirty_cow_pnode - ensure a pnode is not being committed.
    1638             :  * @c: UBIFS file-system description object
    1639             :  * @pnode: pnode to check
    1640             :  *
    1641             :  * Returns dirtied pnode on success or negative error code on failure.
    1642             :  */
    1643    11570244 : static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
    1644             :                                            struct ubifs_pnode *pnode)
    1645             : {
    1646             :         struct ubifs_pnode *p;
    1647             : 
    1648    23140488 :         if (!test_bit(COW_CNODE, &pnode->flags)) {
    1649             :                 /* pnode is not being committed */
    1650    11647156 :                 if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
    1651       78693 :                         c->dirty_pn_cnt += 1;
    1652       78693 :                         add_pnode_dirt(c, pnode);
    1653             :                 }
    1654             :                 return pnode;
    1655             :         }
    1656             : 
    1657             :         /* pnode is being committed, so copy it */
    1658        1781 :         p = kmemdup(pnode, sizeof(struct ubifs_pnode), GFP_NOFS);
    1659        1781 :         if (unlikely(!p))
    1660             :                 return ERR_PTR(-ENOMEM);
    1661             : 
    1662        1781 :         p->cnext = NULL;
    1663        3562 :         __set_bit(DIRTY_CNODE, &p->flags);
    1664        1781 :         __clear_bit(COW_CNODE, &p->flags);
    1665        1781 :         replace_cats(c, pnode, p);
    1666             : 
    1667        3562 :         ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &pnode->flags));
    1668        3562 :         __set_bit(OBSOLETE_CNODE, &pnode->flags);
    1669             : 
    1670        1781 :         c->dirty_pn_cnt += 1;
    1671        3562 :         add_pnode_dirt(c, pnode);
    1672        1781 :         pnode->parent->nbranch[p->iip].pnode = p;
    1673        1781 :         return p;
    1674             : }
    1675             : 
    1676             : /**
    1677             :  * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
    1678             :  * @c: UBIFS file-system description object
    1679             :  * @lnum: LEB number to lookup
    1680             :  *
    1681             :  * This function returns a pointer to the LEB properties on success or a
    1682             :  * negative error code on failure.
    1683             :  */
    1684    11570282 : struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
    1685             : {
    1686             :         int err, i, h, iip, shft;
    1687             :         struct ubifs_nnode *nnode;
    1688             :         struct ubifs_pnode *pnode;
    1689             : 
    1690    11570282 :         if (!c->nroot) {
    1691        2123 :                 err = ubifs_read_nnode(c, NULL, 0);
    1692        2123 :                 if (err)
    1693          48 :                         return ERR_PTR(err);
    1694             :         }
    1695    11570258 :         nnode = c->nroot;
    1696    11570258 :         nnode = dirty_cow_nnode(c, nnode);
    1697    11570258 :         if (IS_ERR(nnode))
    1698             :                 return ERR_CAST(nnode);
    1699    11570258 :         i = lnum - c->main_first;
    1700    11570258 :         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
    1701    66280408 :         for (h = 1; h < c->lpt_hght; h++) {
    1702    54710150 :                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    1703    54710150 :                 shft -= UBIFS_LPT_FANOUT_SHIFT;
    1704    54710150 :                 nnode = ubifs_get_nnode(c, nnode, iip);
    1705    54710150 :                 if (IS_ERR(nnode))
    1706             :                         return ERR_CAST(nnode);
    1707    54710150 :                 nnode = dirty_cow_nnode(c, nnode);
    1708    54710150 :                 if (IS_ERR(nnode))
    1709             :                         return ERR_CAST(nnode);
    1710             :         }
    1711    11570258 :         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    1712    11570258 :         pnode = ubifs_get_pnode(c, nnode, iip);
    1713    11570258 :         if (IS_ERR(pnode))
    1714             :                 return ERR_CAST(pnode);
    1715    11570244 :         pnode = dirty_cow_pnode(c, pnode);
    1716    11570244 :         if (IS_ERR(pnode))
    1717             :                 return ERR_CAST(pnode);
    1718    11570244 :         iip = (i & (UBIFS_LPT_FANOUT - 1));
    1719    11570244 :         dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
    1720             :                pnode->lprops[iip].free, pnode->lprops[iip].dirty,
    1721             :                pnode->lprops[iip].flags);
    1722    23140488 :         ubifs_assert(c, test_bit(DIRTY_CNODE, &pnode->flags));
    1723    11570244 :         return &pnode->lprops[iip];
    1724             : }
    1725             : 
    1726             : /**
    1727             :  * ubifs_lpt_calc_hash - Calculate hash of the LPT pnodes
    1728             :  * @c: UBIFS file-system description object
    1729             :  * @hash: the returned hash of the LPT pnodes
    1730             :  *
    1731             :  * This function iterates over the LPT pnodes and creates a hash over them.
    1732             :  * Returns 0 for success or a negative error code otherwise.
    1733             :  */
    1734        1884 : int ubifs_lpt_calc_hash(struct ubifs_info *c, u8 *hash)
    1735             : {
    1736             :         struct ubifs_nnode *nnode, *nn;
    1737             :         struct ubifs_cnode *cnode;
    1738             :         struct shash_desc *desc;
    1739        1884 :         int iip = 0, i;
    1740        1884 :         int bufsiz = max_t(int, c->nnode_sz, c->pnode_sz);
    1741             :         void *buf;
    1742             :         int err;
    1743             : 
    1744        1884 :         if (!ubifs_authenticated(c))
    1745             :                 return 0;
    1746             : 
    1747           0 :         if (!c->nroot) {
    1748           0 :                 err = ubifs_read_nnode(c, NULL, 0);
    1749           0 :                 if (err)
    1750             :                         return err;
    1751             :         }
    1752             : 
    1753           0 :         desc = ubifs_hash_get_desc(c);
    1754           0 :         if (IS_ERR(desc))
    1755           0 :                 return PTR_ERR(desc);
    1756             : 
    1757           0 :         buf = kmalloc(bufsiz, GFP_NOFS);
    1758           0 :         if (!buf) {
    1759             :                 err = -ENOMEM;
    1760             :                 goto out;
    1761             :         }
    1762             : 
    1763           0 :         cnode = (struct ubifs_cnode *)c->nroot;
    1764             : 
    1765           0 :         while (cnode) {
    1766           0 :                 nnode = cnode->parent;
    1767           0 :                 nn = (struct ubifs_nnode *)cnode;
    1768           0 :                 if (cnode->level > 1) {
    1769           0 :                         while (iip < UBIFS_LPT_FANOUT) {
    1770           0 :                                 if (nn->nbranch[iip].lnum == 0) {
    1771             :                                         /* Go right */
    1772           0 :                                         iip++;
    1773           0 :                                         continue;
    1774             :                                 }
    1775             : 
    1776           0 :                                 nnode = ubifs_get_nnode(c, nn, iip);
    1777           0 :                                 if (IS_ERR(nnode)) {
    1778           0 :                                         err = PTR_ERR(nnode);
    1779           0 :                                         goto out;
    1780             :                                 }
    1781             : 
    1782             :                                 /* Go down */
    1783             :                                 iip = 0;
    1784             :                                 cnode = (struct ubifs_cnode *)nnode;
    1785             :                                 break;
    1786             :                         }
    1787           0 :                         if (iip < UBIFS_LPT_FANOUT)
    1788           0 :                                 continue;
    1789             :                 } else {
    1790             :                         struct ubifs_pnode *pnode;
    1791             : 
    1792           0 :                         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    1793           0 :                                 if (nn->nbranch[i].lnum == 0)
    1794           0 :                                         continue;
    1795           0 :                                 pnode = ubifs_get_pnode(c, nn, i);
    1796           0 :                                 if (IS_ERR(pnode)) {
    1797           0 :                                         err = PTR_ERR(pnode);
    1798           0 :                                         goto out;
    1799             :                                 }
    1800             : 
    1801           0 :                                 ubifs_pack_pnode(c, buf, pnode);
    1802           0 :                                 err = ubifs_shash_update(c, desc, buf,
    1803           0 :                                                          c->pnode_sz);
    1804           0 :                                 if (err)
    1805             :                                         goto out;
    1806             :                         }
    1807             :                 }
    1808             :                 /* Go up and to the right */
    1809           0 :                 iip = cnode->iip + 1;
    1810           0 :                 cnode = (struct ubifs_cnode *)nnode;
    1811             :         }
    1812             : 
    1813           0 :         err = ubifs_shash_final(c, desc, hash);
    1814           0 : out:
    1815           0 :         kfree(desc);
    1816           0 :         kfree(buf);
    1817             : 
    1818           0 :         return err;
    1819             : }
    1820             : 
    1821             : /**
    1822             :  * lpt_check_hash - check the hash of the LPT.
    1823             :  * @c: UBIFS file-system description object
    1824             :  *
    1825             :  * This function calculates a hash over all pnodes in the LPT and compares it with
    1826             :  * the hash stored in the master node. Returns %0 on success and a negative error
    1827             :  * code on failure.
    1828             :  */
    1829             : static int lpt_check_hash(struct ubifs_info *c)
    1830             : {
    1831             :         int err;
    1832             :         u8 hash[UBIFS_HASH_ARR_SZ];
    1833             : 
    1834        2265 :         if (!ubifs_authenticated(c))
    1835             :                 return 0;
    1836             : 
    1837           0 :         err = ubifs_lpt_calc_hash(c, hash);
    1838           0 :         if (err)
    1839             :                 return err;
    1840             : 
    1841           0 :         if (ubifs_check_hash(c, c->mst_node->hash_lpt, hash)) {
    1842             :                 err = -EPERM;
    1843             :                 ubifs_err(c, "Failed to authenticate LPT");
    1844             :         } else {
    1845           0 :                 err = 0;
    1846             :         }
    1847             : 
    1848             :         return err;
    1849             : }
    1850             : 
    1851             : /**
    1852             :  * lpt_init_rd - initialize the LPT for reading.
    1853             :  * @c: UBIFS file-system description object
    1854             :  *
    1855             :  * This function returns %0 on success and a negative error code on failure.
    1856             :  */
    1857        2265 : static int lpt_init_rd(struct ubifs_info *c)
    1858             : {
    1859             :         int err, i;
    1860             : 
    1861        4530 :         c->ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
    1862             :                                      c->lpt_lebs));
    1863        2265 :         if (!c->ltab)
    1864             :                 return -ENOMEM;
    1865             : 
    1866        2265 :         i = max_t(int, c->nnode_sz, c->pnode_sz);
    1867        2265 :         c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
    1868        2265 :         if (!c->lpt_nod_buf)
    1869             :                 return -ENOMEM;
    1870             : 
    1871        6795 :         for (i = 0; i < LPROPS_HEAP_CNT; i++) {
    1872        6795 :                 c->lpt_heap[i].arr = kmalloc_array(LPT_HEAP_SZ,
    1873             :                                                    sizeof(void *),
    1874             :                                                    GFP_KERNEL);
    1875        6795 :                 if (!c->lpt_heap[i].arr)
    1876             :                         return -ENOMEM;
    1877        6795 :                 c->lpt_heap[i].cnt = 0;
    1878        6795 :                 c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
    1879             :         }
    1880             : 
    1881        2265 :         c->dirty_idx.arr = kmalloc_array(LPT_HEAP_SZ, sizeof(void *),
    1882             :                                          GFP_KERNEL);
    1883        2265 :         if (!c->dirty_idx.arr)
    1884             :                 return -ENOMEM;
    1885        2265 :         c->dirty_idx.cnt = 0;
    1886        2265 :         c->dirty_idx.max_cnt = LPT_HEAP_SZ;
    1887             : 
    1888        2265 :         err = read_ltab(c);
    1889        2265 :         if (err) {
    1890          48 :                 if (test_and_clear_failure_reason_callback(c, FR_LPT_CORRUPTED) &&
    1891          24 :                     can_ignore_failure_callback(c, FR_LPT_CORRUPTED))
    1892             :                         err = 0;
    1893             :                 else
    1894             :                         return err;
    1895             :         }
    1896             : 
    1897           0 :         err = lpt_check_hash(c);
    1898             :         if (err)
    1899             :                 return err;
    1900             : 
    1901        2265 :         dbg_lp("space_bits %d", c->space_bits);
    1902        2265 :         dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
    1903        2265 :         dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
    1904        2265 :         dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
    1905        2265 :         dbg_lp("pcnt_bits %d", c->pcnt_bits);
    1906        2265 :         dbg_lp("lnum_bits %d", c->lnum_bits);
    1907        2265 :         dbg_lp("pnode_sz %d", c->pnode_sz);
    1908        2265 :         dbg_lp("nnode_sz %d", c->nnode_sz);
    1909        2265 :         dbg_lp("ltab_sz %d", c->ltab_sz);
    1910        2265 :         dbg_lp("lsave_sz %d", c->lsave_sz);
    1911        2265 :         dbg_lp("lsave_cnt %d", c->lsave_cnt);
    1912        2265 :         dbg_lp("lpt_hght %d", c->lpt_hght);
    1913        2265 :         dbg_lp("big_lpt %u", c->big_lpt);
    1914        2265 :         dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
    1915        2265 :         dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
    1916        2265 :         dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
    1917        2265 :         if (c->big_lpt)
    1918          24 :                 dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
    1919             : 
    1920             :         return 0;
    1921             : }
    1922             : 
    1923             : /**
    1924             :  * lpt_init_wr - initialize the LPT for writing.
    1925             :  * @c: UBIFS file-system description object
    1926             :  *
    1927             :  * 'lpt_init_rd()' must have been called already.
    1928             :  *
    1929             :  * This function returns %0 on success and a negative error code on failure.
    1930             :  */
    1931        2133 : static int lpt_init_wr(struct ubifs_info *c)
    1932             : {
    1933             :         int err, i;
    1934             : 
    1935        4266 :         c->ltab_cmt = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
    1936             :                                          c->lpt_lebs));
    1937        2133 :         if (!c->ltab_cmt)
    1938             :                 return -ENOMEM;
    1939             : 
    1940        2133 :         c->lpt_buf = vmalloc(c->leb_size);
    1941        2133 :         if (!c->lpt_buf)
    1942             :                 return -ENOMEM;
    1943             : 
    1944        2133 :         if (c->big_lpt) {
    1945          24 :                 c->lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_NOFS);
    1946          24 :                 if (!c->lsave)
    1947             :                         return -ENOMEM;
    1948          24 :                 err = read_lsave(c);
    1949          24 :                 if (err) {
    1950           0 :                         if (test_and_clear_failure_reason_callback(c, FR_LPT_CORRUPTED) &&
    1951           0 :                             can_ignore_failure_callback(c, FR_LPT_CORRUPTED))
    1952             :                                 err = 0;
    1953             :                         else
    1954             :                                 return err;
    1955             :                 }
    1956             :         }
    1957             : 
    1958        4362 :         for (i = 0; i < c->lpt_lebs; i++)
    1959        4362 :                 if (c->ltab[i].free == c->leb_size) {
    1960        1481 :                         err = ubifs_leb_unmap(c, i + c->lpt_first);
    1961        1481 :                         if (err)
    1962             :                                 return err;
    1963             :                 }
    1964             : 
    1965             :         return 0;
    1966             : }
    1967             : 
    1968             : /**
    1969             :  * ubifs_lpt_init - initialize the LPT.
    1970             :  * @c: UBIFS file-system description object
    1971             :  * @rd: whether to initialize lpt for reading
    1972             :  * @wr: whether to initialize lpt for writing
    1973             :  *
    1974             :  * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
    1975             :  * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
    1976             :  * true.
    1977             :  *
    1978             :  * This function returns %0 on success and a negative error code on failure.
    1979             :  */
    1980        2265 : int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
    1981             : {
    1982             :         int err;
    1983             : 
    1984        2265 :         if (rd) {
    1985        2265 :                 err = lpt_init_rd(c);
    1986        2265 :                 if (err)
    1987             :                         goto out_err;
    1988             :         }
    1989             : 
    1990        2265 :         if (wr) {
    1991        2133 :                 err = lpt_init_wr(c);
    1992        2133 :                 if (err)
    1993             :                         goto out_err;
    1994             :         }
    1995             : 
    1996             :         return 0;
    1997             : 
    1998           0 : out_err:
    1999           0 :         if (wr)
    2000           0 :                 ubifs_lpt_free(c, 1);
    2001           0 :         if (rd)
    2002           0 :                 ubifs_lpt_free(c, 0);
    2003             :         return err;
    2004             : }
    2005             : 
    2006             : /**
    2007             :  * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
    2008             :  * @nnode: where to keep a nnode
    2009             :  * @pnode: where to keep a pnode
    2010             :  * @cnode: where to keep a cnode
    2011             :  * @in_tree: is the node in the tree in memory
    2012             :  * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
    2013             :  * the tree
    2014             :  * @ptr.pnode: ditto for pnode
    2015             :  * @ptr.cnode: ditto for cnode
    2016             :  */
    2017             : struct lpt_scan_node {
    2018             :         union {
    2019             :                 struct ubifs_nnode nnode;
    2020             :                 struct ubifs_pnode pnode;
    2021             :                 struct ubifs_cnode cnode;
    2022             :         };
    2023             :         int in_tree;
    2024             :         union {
    2025             :                 struct ubifs_nnode *nnode;
    2026             :                 struct ubifs_pnode *pnode;
    2027             :                 struct ubifs_cnode *cnode;
    2028             :         } ptr;
    2029             : };
    2030             : 
    2031             : /**
    2032             :  * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
    2033             :  * @c: the UBIFS file-system description object
    2034             :  * @path: where to put the nnode
    2035             :  * @parent: parent of the nnode
    2036             :  * @iip: index in parent of the nnode
    2037             :  *
    2038             :  * This function returns a pointer to the nnode on success or a negative error
    2039             :  * code on failure.
    2040             :  */
    2041           6 : static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,
    2042             :                                           struct lpt_scan_node *path,
    2043             :                                           struct ubifs_nnode *parent, int iip)
    2044             : {
    2045             :         struct ubifs_nbranch *branch;
    2046             :         struct ubifs_nnode *nnode;
    2047           6 :         void *buf = c->lpt_nod_buf;
    2048             :         int err;
    2049             : 
    2050           6 :         branch = &parent->nbranch[iip];
    2051           6 :         nnode = branch->nnode;
    2052           6 :         if (nnode) {
    2053           0 :                 path->in_tree = 1;
    2054           0 :                 path->ptr.nnode = nnode;
    2055           0 :                 return nnode;
    2056             :         }
    2057           6 :         nnode = &path->nnode;
    2058           6 :         path->in_tree = 0;
    2059           6 :         path->ptr.nnode = nnode;
    2060           6 :         memset(nnode, 0, sizeof(struct ubifs_nnode));
    2061           6 :         if (branch->lnum == 0) {
    2062             :                 /*
    2063             :                  * This nnode was not written which just means that the LEB
    2064             :                  * properties in the subtree below it describe empty LEBs. We
    2065             :                  * make the nnode as though we had read it, which in fact means
    2066             :                  * doing almost nothing.
    2067             :                  */
    2068           0 :                 if (c->big_lpt)
    2069           0 :                         nnode->num = calc_nnode_num_from_parent(c, parent, iip);
    2070             :         } else {
    2071           6 :                 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
    2072             :                                      c->nnode_sz, 1);
    2073           6 :                 if (err) {
    2074           0 :                         if (err == -EBADMSG)
    2075             :                                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    2076           0 :                         return ERR_PTR(err);
    2077             :                 }
    2078           6 :                 err = ubifs_unpack_nnode(c, buf, nnode);
    2079           6 :                 if (err)
    2080           0 :                         return ERR_PTR(err);
    2081             :         }
    2082           6 :         err = validate_nnode(c, nnode, parent, iip);
    2083           6 :         if (err)
    2084           0 :                 return ERR_PTR(err);
    2085           6 :         if (!c->big_lpt)
    2086           6 :                 nnode->num = calc_nnode_num_from_parent(c, parent, iip);
    2087           6 :         nnode->level = parent->level - 1;
    2088           6 :         nnode->parent = parent;
    2089           6 :         nnode->iip = iip;
    2090           6 :         return nnode;
    2091             : }
    2092             : 
    2093             : /**
    2094             :  * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
    2095             :  * @c: the UBIFS file-system description object
    2096             :  * @path: where to put the pnode
    2097             :  * @parent: parent of the pnode
    2098             :  * @iip: index in parent of the pnode
    2099             :  *
    2100             :  * This function returns a pointer to the pnode on success or a negative error
    2101             :  * code on failure.
    2102             :  */
    2103           2 : static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,
    2104             :                                           struct lpt_scan_node *path,
    2105             :                                           struct ubifs_nnode *parent, int iip)
    2106             : {
    2107             :         struct ubifs_nbranch *branch;
    2108             :         struct ubifs_pnode *pnode;
    2109           2 :         void *buf = c->lpt_nod_buf;
    2110             :         int err;
    2111             : 
    2112           2 :         branch = &parent->nbranch[iip];
    2113           2 :         pnode = branch->pnode;
    2114           2 :         if (pnode) {
    2115           0 :                 path->in_tree = 1;
    2116           0 :                 path->ptr.pnode = pnode;
    2117           0 :                 return pnode;
    2118             :         }
    2119           2 :         pnode = &path->pnode;
    2120           2 :         path->in_tree = 0;
    2121           2 :         path->ptr.pnode = pnode;
    2122           2 :         memset(pnode, 0, sizeof(struct ubifs_pnode));
    2123           2 :         if (branch->lnum == 0) {
    2124             :                 /*
    2125             :                  * This pnode was not written which just means that the LEB
    2126             :                  * properties in it describe empty LEBs. We make the pnode as
    2127             :                  * though we had read it.
    2128             :                  */
    2129             :                 int i;
    2130             : 
    2131           0 :                 if (c->big_lpt)
    2132           0 :                         pnode->num = calc_pnode_num_from_parent(c, parent, iip);
    2133           0 :                 for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
    2134           0 :                         struct ubifs_lprops * const lprops = &pnode->lprops[i];
    2135             : 
    2136           0 :                         lprops->free = c->leb_size;
    2137           0 :                         lprops->flags = ubifs_categorize_lprops(c, lprops);
    2138             :                 }
    2139             :         } else {
    2140           2 :                 ubifs_assert(c, branch->lnum >= c->lpt_first &&
    2141             :                              branch->lnum <= c->lpt_last);
    2142           2 :                 ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size);
    2143           2 :                 err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
    2144             :                                      c->pnode_sz, 1);
    2145           2 :                 if (err) {
    2146           0 :                         if (err == -EBADMSG)
    2147             :                                 set_failure_reason_callback(c, FR_LPT_CORRUPTED);
    2148           0 :                         return ERR_PTR(err);
    2149             :                 }
    2150           2 :                 err = unpack_pnode(c, buf, pnode);
    2151           2 :                 if (err)
    2152           0 :                         return ERR_PTR(err);
    2153             :         }
    2154           2 :         err = validate_pnode(c, pnode, parent, iip);
    2155           2 :         if (err)
    2156           0 :                 return ERR_PTR(err);
    2157           2 :         if (!c->big_lpt)
    2158           4 :                 pnode->num = calc_pnode_num_from_parent(c, parent, iip);
    2159           2 :         pnode->parent = parent;
    2160           2 :         pnode->iip = iip;
    2161             :         set_pnode_lnum(c, pnode);
    2162             :         return pnode;
    2163             : }
    2164             : 
    2165             : /**
    2166             :  * ubifs_lpt_scan_nolock - scan the LPT.
    2167             :  * @c: the UBIFS file-system description object
    2168             :  * @start_lnum: LEB number from which to start scanning
    2169             :  * @end_lnum: LEB number at which to stop scanning
    2170             :  * @scan_cb: callback function called for each lprops
    2171             :  * @data: data to be passed to the callback function
    2172             :  *
    2173             :  * This function returns %0 on success and a negative error code on failure.
    2174             :  */
    2175           2 : int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,
    2176             :                           ubifs_lpt_scan_callback scan_cb, void *data)
    2177             : {
    2178           2 :         int err = 0, i, h, iip, shft;
    2179             :         struct ubifs_nnode *nnode;
    2180             :         struct ubifs_pnode *pnode;
    2181             :         struct lpt_scan_node *path;
    2182             : 
    2183           2 :         if (start_lnum == -1) {
    2184           2 :                 start_lnum = end_lnum + 1;
    2185           2 :                 if (start_lnum >= c->leb_cnt)
    2186           0 :                         start_lnum = c->main_first;
    2187             :         }
    2188             : 
    2189           2 :         ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt);
    2190           2 :         ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt);
    2191             : 
    2192           2 :         if (!c->nroot) {
    2193           0 :                 err = ubifs_read_nnode(c, NULL, 0);
    2194           0 :                 if (err)
    2195             :                         return err;
    2196             :         }
    2197             : 
    2198           2 :         path = kmalloc_array(c->lpt_hght + 1, sizeof(struct lpt_scan_node),
    2199             :                              GFP_NOFS);
    2200           2 :         if (!path)
    2201             :                 return -ENOMEM;
    2202             : 
    2203           2 :         path[0].ptr.nnode = c->nroot;
    2204           2 :         path[0].in_tree = 1;
    2205           2 : again:
    2206             :         /* Descend to the pnode containing start_lnum */
    2207           2 :         nnode = c->nroot;
    2208           2 :         i = start_lnum - c->main_first;
    2209           2 :         shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
    2210           8 :         for (h = 1; h < c->lpt_hght; h++) {
    2211           6 :                 iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    2212           6 :                 shft -= UBIFS_LPT_FANOUT_SHIFT;
    2213           6 :                 nnode = scan_get_nnode(c, path + h, nnode, iip);
    2214           6 :                 if (IS_ERR(nnode)) {
    2215           0 :                         err = PTR_ERR(nnode);
    2216           0 :                         goto out;
    2217             :                 }
    2218             :         }
    2219           2 :         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
    2220           2 :         pnode = scan_get_pnode(c, path + h, nnode, iip);
    2221           2 :         if (IS_ERR(pnode)) {
    2222           0 :                 err = PTR_ERR(pnode);
    2223           0 :                 goto out;
    2224             :         }
    2225           2 :         iip = (i & (UBIFS_LPT_FANOUT - 1));
    2226             : 
    2227             :         /* Loop for each lprops */
    2228             :         while (1) {
    2229           2 :                 struct ubifs_lprops *lprops = &pnode->lprops[iip];
    2230           2 :                 int ret, lnum = lprops->lnum;
    2231             : 
    2232           2 :                 ret = scan_cb(c, lprops, path[h].in_tree, data);
    2233           2 :                 if (ret < 0) {
    2234             :                         err = ret;
    2235             :                         goto out;
    2236             :                 }
    2237           2 :                 if (ret & LPT_SCAN_ADD) {
    2238             :                         /* Add all the nodes in path to the tree in memory */
    2239           6 :                         for (h = 1; h < c->lpt_hght; h++) {
    2240           6 :                                 const size_t sz = sizeof(struct ubifs_nnode);
    2241             :                                 struct ubifs_nnode *parent;
    2242             : 
    2243           6 :                                 if (path[h].in_tree)
    2244           0 :                                         continue;
    2245           6 :                                 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS);
    2246           6 :                                 if (!nnode) {
    2247             :                                         err = -ENOMEM;
    2248             :                                         goto out;
    2249             :                                 }
    2250           6 :                                 parent = nnode->parent;
    2251           6 :                                 parent->nbranch[nnode->iip].nnode = nnode;
    2252           6 :                                 path[h].ptr.nnode = nnode;
    2253           6 :                                 path[h].in_tree = 1;
    2254           6 :                                 path[h + 1].cnode.parent = nnode;
    2255             :                         }
    2256           2 :                         if (path[h].in_tree)
    2257           0 :                                 ubifs_ensure_cat(c, lprops);
    2258             :                         else {
    2259           2 :                                 const size_t sz = sizeof(struct ubifs_pnode);
    2260             :                                 struct ubifs_nnode *parent;
    2261             : 
    2262           2 :                                 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS);
    2263           2 :                                 if (!pnode) {
    2264             :                                         err = -ENOMEM;
    2265             :                                         goto out;
    2266             :                                 }
    2267           2 :                                 parent = pnode->parent;
    2268           2 :                                 parent->nbranch[pnode->iip].pnode = pnode;
    2269           2 :                                 path[h].ptr.pnode = pnode;
    2270           2 :                                 path[h].in_tree = 1;
    2271           2 :                                 update_cats(c, pnode);
    2272           2 :                                 c->pnodes_have += 1;
    2273             :                         }
    2274           2 :                         err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)
    2275           2 :                                                   c->nroot, 0, 0);
    2276             :                         if (err)
    2277             :                                 goto out;
    2278           2 :                         err = dbg_check_cats(c);
    2279             :                         if (err)
    2280             :                                 goto out;
    2281             :                 }
    2282           2 :                 if (ret & LPT_SCAN_STOP) {
    2283             :                         err = 0;
    2284             :                         break;
    2285             :                 }
    2286             :                 /* Get the next lprops */
    2287           0 :                 if (lnum == end_lnum) {
    2288             :                         /*
    2289             :                          * We got to the end without finding what we were
    2290             :                          * looking for
    2291             :                          */
    2292             :                         err = -ENOSPC;
    2293             :                         goto out;
    2294             :                 }
    2295           0 :                 if (lnum + 1 >= c->leb_cnt) {
    2296             :                         /* Wrap-around to the beginning */
    2297           0 :                         start_lnum = c->main_first;
    2298           0 :                         goto again;
    2299             :                 }
    2300           0 :                 if (iip + 1 < UBIFS_LPT_FANOUT) {
    2301             :                         /* Next lprops is in the same pnode */
    2302           0 :                         iip += 1;
    2303           0 :                         continue;
    2304             :                 }
    2305             :                 /* We need to get the next pnode. Go up until we can go right */
    2306           0 :                 iip = pnode->iip;
    2307             :                 while (1) {
    2308           0 :                         h -= 1;
    2309           0 :                         ubifs_assert(c, h >= 0);
    2310           0 :                         nnode = path[h].ptr.nnode;
    2311           0 :                         if (iip + 1 < UBIFS_LPT_FANOUT)
    2312             :                                 break;
    2313           0 :                         iip = nnode->iip;
    2314             :                 }
    2315             :                 /* Go right */
    2316           0 :                 iip += 1;
    2317             :                 /* Descend to the pnode */
    2318           0 :                 h += 1;
    2319           0 :                 for (; h < c->lpt_hght; h++) {
    2320           0 :                         nnode = scan_get_nnode(c, path + h, nnode, iip);
    2321           0 :                         if (IS_ERR(nnode)) {
    2322           0 :                                 err = PTR_ERR(nnode);
    2323           0 :                                 goto out;
    2324             :                         }
    2325           0 :                         iip = 0;
    2326             :                 }
    2327           0 :                 pnode = scan_get_pnode(c, path + h, nnode, iip);
    2328           0 :                 if (IS_ERR(pnode)) {
    2329           0 :                         err = PTR_ERR(pnode);
    2330           0 :                         goto out;
    2331             :                 }
    2332             :                 iip = 0;
    2333             :         }
    2334           2 : out:
    2335           2 :         kfree(path);
    2336           2 :         return err;
    2337             : }

Generated by: LCOV version 1.13