fs/ubifs/lpt.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * This file is part of UBIFS.
0004  *
0005  * Copyright (C) 2006-2008 Nokia Corporation.
0006  *
0007  * Authors: Adrian Hunter
0008  *          Artem Bityutskiy (Битюцкий Артём)
0009  */
0010
0011 /*
0012  * This file implements the LEB properties tree (LPT) area. The LPT area
0013  * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and
0014  * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits
0015  * between the log and the orphan area.
0016  *
0017  * The LPT area is like a miniature self-contained file system. It is required
0018  * that it never runs out of space, is fast to access and update, and scales
0019  * logarithmically. The LEB properties tree is implemented as a wandering tree
0020  * much like the TNC, and the LPT area has its own garbage collection.
0021  *
0022  * The LPT has two slightly different forms called the "small model" and the
0023  * "big model". The small model is used when the entire LEB properties table
0024  * can be written into a single eraseblock. In that case, garbage collection
0025  * consists of just writing the whole table, which therefore makes all other
0026  * eraseblocks reusable. In the case of the big model, dirty eraseblocks are
0027  * selected for garbage collection, which consists of marking the clean nodes in
0028  * that LEB as dirty, and then only the dirty nodes are written out. Also, in
0029  * the case of the big model, a table of LEB numbers is saved so that the entire
0030  * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first
0031  * mounted.
0032  */
0033
0034 #include "ubifs.h"
0035 #include <linux/crc16.h>
0036 #include <linux/math64.h>
0037 #include <linux/slab.h>
0038
0039 /**
0040  * do_calc_lpt_geom - calculate sizes for the LPT area.
0041  * @c: the UBIFS file-system description object
0042  *
0043  * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
0044  * properties of the flash and whether LPT is "big" (c->big_lpt).
0045  */
0046 static void do_calc_lpt_geom(struct ubifs_info *c)
0047 {
0048     int i, n, bits, per_leb_wastage, max_pnode_cnt;
0049     long long sz, tot_wastage;
0050
0051     n = c->main_lebs + c->max_leb_cnt - c->leb_cnt;
0052     max_pnode_cnt = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
0053
0054     c->lpt_hght = 1;
0055     n = UBIFS_LPT_FANOUT;
0056     while (n < max_pnode_cnt) {
0057         c->lpt_hght += 1;
0058         n <<= UBIFS_LPT_FANOUT_SHIFT;
0059     }
0060
0061     c->pnode_cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT);
0062
0063     n = DIV_ROUND_UP(c->pnode_cnt, UBIFS_LPT_FANOUT);
0064     c->nnode_cnt = n;
0065     for (i = 1; i < c->lpt_hght; i++) {
0066         n = DIV_ROUND_UP(n, UBIFS_LPT_FANOUT);
0067         c->nnode_cnt += n;
0068     }
0069
0070     c->space_bits = fls(c->leb_size) - 3;
0071     c->lpt_lnum_bits = fls(c->lpt_lebs);
0072     c->lpt_offs_bits = fls(c->leb_size - 1);
0073     c->lpt_spc_bits = fls(c->leb_size);
0074
0075     n = DIV_ROUND_UP(c->max_leb_cnt, UBIFS_LPT_FANOUT);
0076     c->pcnt_bits = fls(n - 1);
0077
0078     c->lnum_bits = fls(c->max_leb_cnt - 1);
0079
0080     bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
0081            (c->big_lpt ? c->pcnt_bits : 0) +
0082            (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
0083     c->pnode_sz = (bits + 7) / 8;
0084
0085     bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
0086            (c->big_lpt ? c->pcnt_bits : 0) +
0087            (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
0088     c->nnode_sz = (bits + 7) / 8;
0089
0090     bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
0091            c->lpt_lebs * c->lpt_spc_bits * 2;
0092     c->ltab_sz = (bits + 7) / 8;
0093
0094     bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
0095            c->lnum_bits * c->lsave_cnt;
0096     c->lsave_sz = (bits + 7) / 8;
0097
0098     /* Calculate the minimum LPT size */
0099     c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
0100     c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
0101     c->lpt_sz += c->ltab_sz;
0102     if (c->big_lpt)
0103         c->lpt_sz += c->lsave_sz;
0104
0105     /* Add wastage */
0106     sz = c->lpt_sz;
0107     per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
0108     sz += per_leb_wastage;
0109     tot_wastage = per_leb_wastage;
0110     while (sz > c->leb_size) {
0111         sz += per_leb_wastage;
0112         sz -= c->leb_size;
0113         tot_wastage += per_leb_wastage;
0114     }
0115     tot_wastage += ALIGN(sz, c->min_io_size) - sz;
0116     c->lpt_sz += tot_wastage;
0117 }
0118
0119 /**
0120  * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area.
0121  * @c: the UBIFS file-system description object
0122  *
0123  * This function returns %0 on success and a negative error code on failure.
0124  */
0125 int ubifs_calc_lpt_geom(struct ubifs_info *c)
0126 {
0127     int lebs_needed;
0128     long long sz;
0129
0130     do_calc_lpt_geom(c);
0131
0132     /* Verify that lpt_lebs is big enough */
0133     sz = c->lpt_sz * 2; /* Must have at least 2 times the size */
0134     lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
0135     if (lebs_needed > c->lpt_lebs) {
0136         ubifs_err(c, "too few LPT LEBs");
0137         return -EINVAL;
0138     }
0139
0140     /* Verify that ltab fits in a single LEB (since ltab is a single node */
0141     if (c->ltab_sz > c->leb_size) {
0142         ubifs_err(c, "LPT ltab too big");
0143         return -EINVAL;
0144     }
0145
0146     c->check_lpt_free = c->big_lpt;
0147     return 0;
0148 }
0149
0150 /**
0151  * calc_dflt_lpt_geom - calculate default LPT geometry.
0152  * @c: the UBIFS file-system description object
0153  * @main_lebs: number of main area LEBs is passed and returned here
0154  * @big_lpt: whether the LPT area is "big" is returned here
0155  *
0156  * The size of the LPT area depends on parameters that themselves are dependent
0157  * on the size of the LPT area. This function, successively recalculates the LPT
0158  * area geometry until the parameters and resultant geometry are consistent.
0159  *
0160  * This function returns %0 on success and a negative error code on failure.
0161  */
0162 static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs,
0163                   int *big_lpt)
0164 {
0165     int i, lebs_needed;
0166     long long sz;
0167
0168     /* Start by assuming the minimum number of LPT LEBs */
0169     c->lpt_lebs = UBIFS_MIN_LPT_LEBS;
0170     c->main_lebs = *main_lebs - c->lpt_lebs;
0171     if (c->main_lebs <= 0)
0172         return -EINVAL;
0173
0174     /* And assume we will use the small LPT model */
0175     c->big_lpt = 0;
0176
0177     /*
0178      * Calculate the geometry based on assumptions above and then see if it
0179      * makes sense
0180      */
0181     do_calc_lpt_geom(c);
0182
0183     /* Small LPT model must have lpt_sz < leb_size */
0184     if (c->lpt_sz > c->leb_size) {
0185         /* Nope, so try again using big LPT model */
0186         c->big_lpt = 1;
0187         do_calc_lpt_geom(c);
0188     }
0189
0190     /* Now check there are enough LPT LEBs */
0191     for (i = 0; i < 64 ; i++) {
0192         sz = c->lpt_sz * 4; /* Allow 4 times the size */
0193         lebs_needed = div_u64(sz + c->leb_size - 1, c->leb_size);
0194         if (lebs_needed > c->lpt_lebs) {
0195             /* Not enough LPT LEBs so try again with more */
0196             c->lpt_lebs = lebs_needed;
0197             c->main_lebs = *main_lebs - c->lpt_lebs;
0198             if (c->main_lebs <= 0)
0199                 return -EINVAL;
0200             do_calc_lpt_geom(c);
0201             continue;
0202         }
0203         if (c->ltab_sz > c->leb_size) {
0204             ubifs_err(c, "LPT ltab too big");
0205             return -EINVAL;
0206         }
0207         *main_lebs = c->main_lebs;
0208         *big_lpt = c->big_lpt;
0209         return 0;
0210     }
0211     return -EINVAL;
0212 }
0213
0214 /**
0215  * pack_bits - pack bit fields end-to-end.
0216  * @c: UBIFS file-system description object
0217  * @addr: address at which to pack (passed and next address returned)
0218  * @pos: bit position at which to pack (passed and next position returned)
0219  * @val: value to pack
0220  * @nrbits: number of bits of value to pack (1-32)
0221  */
0222 static void pack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, uint32_t val, int nrbits)
0223 {
0224     uint8_t *p = *addr;
0225     int b = *pos;
0226
0227     ubifs_assert(c, nrbits > 0);
0228     ubifs_assert(c, nrbits <= 32);
0229     ubifs_assert(c, *pos >= 0);
0230     ubifs_assert(c, *pos < 8);
0231     ubifs_assert(c, (val >> nrbits) == 0 || nrbits == 32);
0232     if (b) {
0233         *p |= ((uint8_t)val) << b;
0234         nrbits += b;
0235         if (nrbits > 8) {
0236             *++p = (uint8_t)(val >>= (8 - b));
0237             if (nrbits > 16) {
0238                 *++p = (uint8_t)(val >>= 8);
0239                 if (nrbits > 24) {
0240                     *++p = (uint8_t)(val >>= 8);
0241                     if (nrbits > 32)
0242                         *++p = (uint8_t)(val >>= 8);
0243                 }
0244             }
0245         }
0246     } else {
0247         *p = (uint8_t)val;
0248         if (nrbits > 8) {
0249             *++p = (uint8_t)(val >>= 8);
0250             if (nrbits > 16) {
0251                 *++p = (uint8_t)(val >>= 8);
0252                 if (nrbits > 24)
0253                     *++p = (uint8_t)(val >>= 8);
0254             }
0255         }
0256     }
0257     b = nrbits & 7;
0258     if (b == 0)
0259         p++;
0260     *addr = p;
0261     *pos = b;
0262 }
0263
0264 /**
0265  * ubifs_unpack_bits - unpack bit fields.
0266  * @c: UBIFS file-system description object
0267  * @addr: address at which to unpack (passed and next address returned)
0268  * @pos: bit position at which to unpack (passed and next position returned)
0269  * @nrbits: number of bits of value to unpack (1-32)
0270  *
0271  * This functions returns the value unpacked.
0272  */
0273 uint32_t ubifs_unpack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, int nrbits)
0274 {
0275     const int k = 32 - nrbits;
0276     uint8_t *p = *addr;
0277     int b = *pos;
0278     uint32_t val;
0279     const int bytes = (nrbits + b + 7) >> 3;
0280
0281     ubifs_assert(c, nrbits > 0);
0282     ubifs_assert(c, nrbits <= 32);
0283     ubifs_assert(c, *pos >= 0);
0284     ubifs_assert(c, *pos < 8);
0285     if (b) {
0286         switch (bytes) {
0287         case 2:
0288             val = p[1];
0289             break;
0290         case 3:
0291             val = p[1] | ((uint32_t)p[2] << 8);
0292             break;
0293         case 4:
0294             val = p[1] | ((uint32_t)p[2] << 8) |
0295                      ((uint32_t)p[3] << 16);
0296             break;
0297         case 5:
0298             val = p[1] | ((uint32_t)p[2] << 8) |
0299                      ((uint32_t)p[3] << 16) |
0300                      ((uint32_t)p[4] << 24);
0301         }
0302         val <<= (8 - b);
0303         val |= *p >> b;
0304         nrbits += b;
0305     } else {
0306         switch (bytes) {
0307         case 1:
0308             val = p[0];
0309             break;
0310         case 2:
0311             val = p[0] | ((uint32_t)p[1] << 8);
0312             break;
0313         case 3:
0314             val = p[0] | ((uint32_t)p[1] << 8) |
0315                      ((uint32_t)p[2] << 16);
0316             break;
0317         case 4:
0318             val = p[0] | ((uint32_t)p[1] << 8) |
0319                      ((uint32_t)p[2] << 16) |
0320                      ((uint32_t)p[3] << 24);
0321             break;
0322         }
0323     }
0324     val <<= k;
0325     val >>= k;
0326     b = nrbits & 7;
0327     p += nrbits >> 3;
0328     *addr = p;
0329     *pos = b;
0330     ubifs_assert(c, (val >> nrbits) == 0 || nrbits - b == 32);
0331     return val;
0332 }
0333
0334 /**
0335  * ubifs_pack_pnode - pack all the bit fields of a pnode.
0336  * @c: UBIFS file-system description object
0337  * @buf: buffer into which to pack
0338  * @pnode: pnode to pack
0339  */
0340 void ubifs_pack_pnode(struct ubifs_info *c, void *buf,
0341               struct ubifs_pnode *pnode)
0342 {
0343     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
0344     int i, pos = 0;
0345     uint16_t crc;
0346
0347     pack_bits(c, &addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);
0348     if (c->big_lpt)
0349         pack_bits(c, &addr, &pos, pnode->num, c->pcnt_bits);
0350     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
0351         pack_bits(c, &addr, &pos, pnode->lprops[i].free >> 3,
0352               c->space_bits);
0353         pack_bits(c, &addr, &pos, pnode->lprops[i].dirty >> 3,
0354               c->space_bits);
0355         if (pnode->lprops[i].flags & LPROPS_INDEX)
0356             pack_bits(c, &addr, &pos, 1, 1);
0357         else
0358             pack_bits(c, &addr, &pos, 0, 1);
0359     }
0360     crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
0361             c->pnode_sz - UBIFS_LPT_CRC_BYTES);
0362     addr = buf;
0363     pos = 0;
0364     pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
0365 }
0366
0367 /**
0368  * ubifs_pack_nnode - pack all the bit fields of a nnode.
0369  * @c: UBIFS file-system description object
0370  * @buf: buffer into which to pack
0371  * @nnode: nnode to pack
0372  */
0373 void ubifs_pack_nnode(struct ubifs_info *c, void *buf,
0374               struct ubifs_nnode *nnode)
0375 {
0376     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
0377     int i, pos = 0;
0378     uint16_t crc;
0379
0380     pack_bits(c, &addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);
0381     if (c->big_lpt)
0382         pack_bits(c, &addr, &pos, nnode->num, c->pcnt_bits);
0383     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
0384         int lnum = nnode->nbranch[i].lnum;
0385
0386         if (lnum == 0)
0387             lnum = c->lpt_last + 1;
0388         pack_bits(c, &addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);
0389         pack_bits(c, &addr, &pos, nnode->nbranch[i].offs,
0390               c->lpt_offs_bits);
0391     }
0392     crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
0393             c->nnode_sz - UBIFS_LPT_CRC_BYTES);
0394     addr = buf;
0395     pos = 0;
0396     pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
0397 }
0398
0399 /**
0400  * ubifs_pack_ltab - pack the LPT's own lprops table.
0401  * @c: UBIFS file-system description object
0402  * @buf: buffer into which to pack
0403  * @ltab: LPT's own lprops table to pack
0404  */
0405 void ubifs_pack_ltab(struct ubifs_info *c, void *buf,
0406              struct ubifs_lpt_lprops *ltab)
0407 {
0408     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
0409     int i, pos = 0;
0410     uint16_t crc;
0411
0412     pack_bits(c, &addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);
0413     for (i = 0; i < c->lpt_lebs; i++) {
0414         pack_bits(c, &addr, &pos, ltab[i].free, c->lpt_spc_bits);
0415         pack_bits(c, &addr, &pos, ltab[i].dirty, c->lpt_spc_bits);
0416     }
0417     crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
0418             c->ltab_sz - UBIFS_LPT_CRC_BYTES);
0419     addr = buf;
0420     pos = 0;
0421     pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
0422 }
0423
0424 /**
0425  * ubifs_pack_lsave - pack the LPT's save table.
0426  * @c: UBIFS file-system description object
0427  * @buf: buffer into which to pack
0428  * @lsave: LPT's save table to pack
0429  */
0430 void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave)
0431 {
0432     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
0433     int i, pos = 0;
0434     uint16_t crc;
0435
0436     pack_bits(c, &addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);
0437     for (i = 0; i < c->lsave_cnt; i++)
0438         pack_bits(c, &addr, &pos, lsave[i], c->lnum_bits);
0439     crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
0440             c->lsave_sz - UBIFS_LPT_CRC_BYTES);
0441     addr = buf;
0442     pos = 0;
0443     pack_bits(c, &addr, &pos, crc, UBIFS_LPT_CRC_BITS);
0444 }
0445
0446 /**
0447  * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties.
0448  * @c: UBIFS file-system description object
0449  * @lnum: LEB number to which to add dirty space
0450  * @dirty: amount of dirty space to add
0451  */
0452 void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty)
0453 {
0454     if (!dirty || !lnum)
0455         return;
0456     dbg_lp("LEB %d add %d to %d",
0457            lnum, dirty, c->ltab[lnum - c->lpt_first].dirty);
0458     ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
0459     c->ltab[lnum - c->lpt_first].dirty += dirty;
0460 }
0461
0462 /**
0463  * set_ltab - set LPT LEB properties.
0464  * @c: UBIFS file-system description object
0465  * @lnum: LEB number
0466  * @free: amount of free space
0467  * @dirty: amount of dirty space
0468  */
0469 static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
0470 {
0471     dbg_lp("LEB %d free %d dirty %d to %d %d",
0472            lnum, c->ltab[lnum - c->lpt_first].free,
0473            c->ltab[lnum - c->lpt_first].dirty, free, dirty);
0474     ubifs_assert(c, lnum >= c->lpt_first && lnum <= c->lpt_last);
0475     c->ltab[lnum - c->lpt_first].free = free;
0476     c->ltab[lnum - c->lpt_first].dirty = dirty;
0477 }
0478
0479 /**
0480  * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties.
0481  * @c: UBIFS file-system description object
0482  * @nnode: nnode for which to add dirt
0483  */
0484 void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode)
0485 {
0486     struct ubifs_nnode *np = nnode->parent;
0487
0488     if (np)
0489         ubifs_add_lpt_dirt(c, np->nbranch[nnode->iip].lnum,
0490                    c->nnode_sz);
0491     else {
0492         ubifs_add_lpt_dirt(c, c->lpt_lnum, c->nnode_sz);
0493         if (!(c->lpt_drty_flgs & LTAB_DIRTY)) {
0494             c->lpt_drty_flgs |= LTAB_DIRTY;
0495             ubifs_add_lpt_dirt(c, c->ltab_lnum, c->ltab_sz);
0496         }
0497     }
0498 }
0499
0500 /**
0501  * add_pnode_dirt - add dirty space to LPT LEB properties.
0502  * @c: UBIFS file-system description object
0503  * @pnode: pnode for which to add dirt
0504  */
0505 static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode)
0506 {
0507     ubifs_add_lpt_dirt(c, pnode->parent->nbranch[pnode->iip].lnum,
0508                c->pnode_sz);
0509 }
0510
0511 /**
0512  * calc_nnode_num - calculate nnode number.
0513  * @row: the row in the tree (root is zero)
0514  * @col: the column in the row (leftmost is zero)
0515  *
0516  * The nnode number is a number that uniquely identifies a nnode and can be used
0517  * easily to traverse the tree from the root to that nnode.
0518  *
0519  * This function calculates and returns the nnode number for the nnode at @row
0520  * and @col.
0521  */
0522 static int calc_nnode_num(int row, int col)
0523 {
0524     int num, bits;
0525
0526     num = 1;
0527     while (row--) {
0528         bits = (col & (UBIFS_LPT_FANOUT - 1));
0529         col >>= UBIFS_LPT_FANOUT_SHIFT;
0530         num <<= UBIFS_LPT_FANOUT_SHIFT;
0531         num |= bits;
0532     }
0533     return num;
0534 }
0535
0536 /**
0537  * calc_nnode_num_from_parent - calculate nnode number.
0538  * @c: UBIFS file-system description object
0539  * @parent: parent nnode
0540  * @iip: index in parent
0541  *
0542  * The nnode number is a number that uniquely identifies a nnode and can be used
0543  * easily to traverse the tree from the root to that nnode.
0544  *
0545  * This function calculates and returns the nnode number based on the parent's
0546  * nnode number and the index in parent.
0547  */
0548 static int calc_nnode_num_from_parent(const struct ubifs_info *c,
0549                       struct ubifs_nnode *parent, int iip)
0550 {
0551     int num, shft;
0552
0553     if (!parent)
0554         return 1;
0555     shft = (c->lpt_hght - parent->level) * UBIFS_LPT_FANOUT_SHIFT;
0556     num = parent->num ^ (1 << shft);
0557     num |= (UBIFS_LPT_FANOUT + iip) << shft;
0558     return num;
0559 }
0560
0561 /**
0562  * calc_pnode_num_from_parent - calculate pnode number.
0563  * @c: UBIFS file-system description object
0564  * @parent: parent nnode
0565  * @iip: index in parent
0566  *
0567  * The pnode number is a number that uniquely identifies a pnode and can be used
0568  * easily to traverse the tree from the root to that pnode.
0569  *
0570  * This function calculates and returns the pnode number based on the parent's
0571  * nnode number and the index in parent.
0572  */
0573 static int calc_pnode_num_from_parent(const struct ubifs_info *c,
0574                       struct ubifs_nnode *parent, int iip)
0575 {
0576     int i, n = c->lpt_hght - 1, pnum = parent->num, num = 0;
0577
0578     for (i = 0; i < n; i++) {
0579         num <<= UBIFS_LPT_FANOUT_SHIFT;
0580         num |= pnum & (UBIFS_LPT_FANOUT - 1);
0581         pnum >>= UBIFS_LPT_FANOUT_SHIFT;
0582     }
0583     num <<= UBIFS_LPT_FANOUT_SHIFT;
0584     num |= iip;
0585     return num;
0586 }
0587
0588 /**
0589  * ubifs_create_dflt_lpt - create default LPT.
0590  * @c: UBIFS file-system description object
0591  * @main_lebs: number of main area LEBs is passed and returned here
0592  * @lpt_first: LEB number of first LPT LEB
0593  * @lpt_lebs: number of LEBs for LPT is passed and returned here
0594  * @big_lpt: use big LPT model is passed and returned here
0595  * @hash: hash of the LPT is returned here
0596  *
0597  * This function returns %0 on success and a negative error code on failure.
0598  */
0599 int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first,
0600               int *lpt_lebs, int *big_lpt, u8 *hash)
0601 {
0602     int lnum, err = 0, node_sz, iopos, i, j, cnt, len, alen, row;
0603     int blnum, boffs, bsz, bcnt;
0604     struct ubifs_pnode *pnode = NULL;
0605     struct ubifs_nnode *nnode = NULL;
0606     void *buf = NULL, *p;
0607     struct ubifs_lpt_lprops *ltab = NULL;
0608     int *lsave = NULL;
0609     struct shash_desc *desc;
0610
0611     err = calc_dflt_lpt_geom(c, main_lebs, big_lpt);
0612     if (err)
0613         return err;
0614     *lpt_lebs = c->lpt_lebs;
0615
0616     /* Needed by 'ubifs_pack_nnode()' and 'set_ltab()' */
0617     c->lpt_first = lpt_first;
0618     /* Needed by 'set_ltab()' */
0619     c->lpt_last = lpt_first + c->lpt_lebs - 1;
0620     /* Needed by 'ubifs_pack_lsave()' */
0621     c->main_first = c->leb_cnt - *main_lebs;
0622
0623     desc = ubifs_hash_get_desc(c);
0624     if (IS_ERR(desc))
0625         return PTR_ERR(desc);
0626
0627     lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_KERNEL);
0628     pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_KERNEL);
0629     nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_KERNEL);
0630     buf = vmalloc(c->leb_size);
0631     ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
0632                   c->lpt_lebs));
0633     if (!pnode || !nnode || !buf || !ltab || !lsave) {
0634         err = -ENOMEM;
0635         goto out;
0636     }
0637
0638     ubifs_assert(c, !c->ltab);
0639     c->ltab = ltab; /* Needed by set_ltab */
0640
0641     /* Initialize LPT's own lprops */
0642     for (i = 0; i < c->lpt_lebs; i++) {
0643         ltab[i].free = c->leb_size;
0644         ltab[i].dirty = 0;
0645         ltab[i].tgc = 0;
0646         ltab[i].cmt = 0;
0647     }
0648
0649     lnum = lpt_first;
0650     p = buf;
0651     /* Number of leaf nodes (pnodes) */
0652     cnt = c->pnode_cnt;
0653
0654     /*
0655      * The first pnode contains the LEB properties for the LEBs that contain
0656      * the root inode node and the root index node of the index tree.
0657      */
0658     node_sz = ALIGN(ubifs_idx_node_sz(c, 1), 8);
0659     iopos = ALIGN(node_sz, c->min_io_size);
0660     pnode->lprops[0].free = c->leb_size - iopos;
0661     pnode->lprops[0].dirty = iopos - node_sz;
0662     pnode->lprops[0].flags = LPROPS_INDEX;
0663
0664     node_sz = UBIFS_INO_NODE_SZ;
0665     iopos = ALIGN(node_sz, c->min_io_size);
0666     pnode->lprops[1].free = c->leb_size - iopos;
0667     pnode->lprops[1].dirty = iopos - node_sz;
0668
0669     for (i = 2; i < UBIFS_LPT_FANOUT; i++)
0670         pnode->lprops[i].free = c->leb_size;
0671
0672     /* Add first pnode */
0673     ubifs_pack_pnode(c, p, pnode);
0674     err = ubifs_shash_update(c, desc, p, c->pnode_sz);
0675     if (err)
0676         goto out;
0677
0678     p += c->pnode_sz;
0679     len = c->pnode_sz;
0680     pnode->num += 1;
0681
0682     /* Reset pnode values for remaining pnodes */
0683     pnode->lprops[0].free = c->leb_size;
0684     pnode->lprops[0].dirty = 0;
0685     pnode->lprops[0].flags = 0;
0686
0687     pnode->lprops[1].free = c->leb_size;
0688     pnode->lprops[1].dirty = 0;
0689
0690     /*
0691      * To calculate the internal node branches, we keep information about
0692      * the level below.
0693      */
0694     blnum = lnum; /* LEB number of level below */
0695     boffs = 0; /* Offset of level below */
0696     bcnt = cnt; /* Number of nodes in level below */
0697     bsz = c->pnode_sz; /* Size of nodes in level below */
0698
0699     /* Add all remaining pnodes */
0700     for (i = 1; i < cnt; i++) {
0701         if (len + c->pnode_sz > c->leb_size) {
0702             alen = ALIGN(len, c->min_io_size);
0703             set_ltab(c, lnum, c->leb_size - alen, alen - len);
0704             memset(p, 0xff, alen - len);
0705             err = ubifs_leb_change(c, lnum++, buf, alen);
0706             if (err)
0707                 goto out;
0708             p = buf;
0709             len = 0;
0710         }
0711         ubifs_pack_pnode(c, p, pnode);
0712         err = ubifs_shash_update(c, desc, p, c->pnode_sz);
0713         if (err)
0714             goto out;
0715
0716         p += c->pnode_sz;
0717         len += c->pnode_sz;
0718         /*
0719          * pnodes are simply numbered left to right starting at zero,
0720          * which means the pnode number can be used easily to traverse
0721          * down the tree to the corresponding pnode.
0722          */
0723         pnode->num += 1;
0724     }
0725
0726     row = 0;
0727     for (i = UBIFS_LPT_FANOUT; cnt > i; i <<= UBIFS_LPT_FANOUT_SHIFT)
0728         row += 1;
0729     /* Add all nnodes, one level at a time */
0730     while (1) {
0731         /* Number of internal nodes (nnodes) at next level */
0732         cnt = DIV_ROUND_UP(cnt, UBIFS_LPT_FANOUT);
0733         for (i = 0; i < cnt; i++) {
0734             if (len + c->nnode_sz > c->leb_size) {
0735                 alen = ALIGN(len, c->min_io_size);
0736                 set_ltab(c, lnum, c->leb_size - alen,
0737                         alen - len);
0738                 memset(p, 0xff, alen - len);
0739                 err = ubifs_leb_change(c, lnum++, buf, alen);
0740                 if (err)
0741                     goto out;
0742                 p = buf;
0743                 len = 0;
0744             }
0745             /* Only 1 nnode at this level, so it is the root */
0746             if (cnt == 1) {
0747                 c->lpt_lnum = lnum;
0748                 c->lpt_offs = len;
0749             }
0750             /* Set branches to the level below */
0751             for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
0752                 if (bcnt) {
0753                     if (boffs + bsz > c->leb_size) {
0754                         blnum += 1;
0755                         boffs = 0;
0756                     }
0757                     nnode->nbranch[j].lnum = blnum;
0758                     nnode->nbranch[j].offs = boffs;
0759                     boffs += bsz;
0760                     bcnt--;
0761                 } else {
0762                     nnode->nbranch[j].lnum = 0;
0763                     nnode->nbranch[j].offs = 0;
0764                 }
0765             }
0766             nnode->num = calc_nnode_num(row, i);
0767             ubifs_pack_nnode(c, p, nnode);
0768             p += c->nnode_sz;
0769             len += c->nnode_sz;
0770         }
0771         /* Only 1 nnode at this level, so it is the root */
0772         if (cnt == 1)
0773             break;
0774         /* Update the information about the level below */
0775         bcnt = cnt;
0776         bsz = c->nnode_sz;
0777         row -= 1;
0778     }
0779
0780     if (*big_lpt) {
0781         /* Need to add LPT's save table */
0782         if (len + c->lsave_sz > c->leb_size) {
0783             alen = ALIGN(len, c->min_io_size);
0784             set_ltab(c, lnum, c->leb_size - alen, alen - len);
0785             memset(p, 0xff, alen - len);
0786             err = ubifs_leb_change(c, lnum++, buf, alen);
0787             if (err)
0788                 goto out;
0789             p = buf;
0790             len = 0;
0791         }
0792
0793         c->lsave_lnum = lnum;
0794         c->lsave_offs = len;
0795
0796         for (i = 0; i < c->lsave_cnt && i < *main_lebs; i++)
0797             lsave[i] = c->main_first + i;
0798         for (; i < c->lsave_cnt; i++)
0799             lsave[i] = c->main_first;
0800
0801         ubifs_pack_lsave(c, p, lsave);
0802         p += c->lsave_sz;
0803         len += c->lsave_sz;
0804     }
0805
0806     /* Need to add LPT's own LEB properties table */
0807     if (len + c->ltab_sz > c->leb_size) {
0808         alen = ALIGN(len, c->min_io_size);
0809         set_ltab(c, lnum, c->leb_size - alen, alen - len);
0810         memset(p, 0xff, alen - len);
0811         err = ubifs_leb_change(c, lnum++, buf, alen);
0812         if (err)
0813             goto out;
0814         p = buf;
0815         len = 0;
0816     }
0817
0818     c->ltab_lnum = lnum;
0819     c->ltab_offs = len;
0820
0821     /* Update ltab before packing it */
0822     len += c->ltab_sz;
0823     alen = ALIGN(len, c->min_io_size);
0824     set_ltab(c, lnum, c->leb_size - alen, alen - len);
0825
0826     ubifs_pack_ltab(c, p, ltab);
0827     p += c->ltab_sz;
0828
0829     /* Write remaining buffer */
0830     memset(p, 0xff, alen - len);
0831     err = ubifs_leb_change(c, lnum, buf, alen);
0832     if (err)
0833         goto out;
0834
0835     err = ubifs_shash_final(c, desc, hash);
0836     if (err)
0837         goto out;
0838
0839     c->nhead_lnum = lnum;
0840     c->nhead_offs = ALIGN(len, c->min_io_size);
0841
0842     dbg_lp("space_bits %d", c->space_bits);
0843     dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
0844     dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
0845     dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
0846     dbg_lp("pcnt_bits %d", c->pcnt_bits);
0847     dbg_lp("lnum_bits %d", c->lnum_bits);
0848     dbg_lp("pnode_sz %d", c->pnode_sz);
0849     dbg_lp("nnode_sz %d", c->nnode_sz);
0850     dbg_lp("ltab_sz %d", c->ltab_sz);
0851     dbg_lp("lsave_sz %d", c->lsave_sz);
0852     dbg_lp("lsave_cnt %d", c->lsave_cnt);
0853     dbg_lp("lpt_hght %d", c->lpt_hght);
0854     dbg_lp("big_lpt %u", c->big_lpt);
0855     dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
0856     dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
0857     dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
0858     if (c->big_lpt)
0859         dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
0860 out:
0861     c->ltab = NULL;
0862     kfree(desc);
0863     kfree(lsave);
0864     vfree(ltab);
0865     vfree(buf);
0866     kfree(nnode);
0867     kfree(pnode);
0868     return err;
0869 }
0870
0871 /**
0872  * update_cats - add LEB properties of a pnode to LEB category lists and heaps.
0873  * @c: UBIFS file-system description object
0874  * @pnode: pnode
0875  *
0876  * When a pnode is loaded into memory, the LEB properties it contains are added,
0877  * by this function, to the LEB category lists and heaps.
0878  */
0879 static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode)
0880 {
0881     int i;
0882
0883     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
0884         int cat = pnode->lprops[i].flags & LPROPS_CAT_MASK;
0885         int lnum = pnode->lprops[i].lnum;
0886
0887         if (!lnum)
0888             return;
0889         ubifs_add_to_cat(c, &pnode->lprops[i], cat);
0890     }
0891 }
0892
0893 /**
0894  * replace_cats - add LEB properties of a pnode to LEB category lists and heaps.
0895  * @c: UBIFS file-system description object
0896  * @old_pnode: pnode copied
0897  * @new_pnode: pnode copy
0898  *
0899  * During commit it is sometimes necessary to copy a pnode
0900  * (see dirty_cow_pnode).  When that happens, references in
0901  * category lists and heaps must be replaced.  This function does that.
0902  */
0903 static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode,
0904              struct ubifs_pnode *new_pnode)
0905 {
0906     int i;
0907
0908     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
0909         if (!new_pnode->lprops[i].lnum)
0910             return;
0911         ubifs_replace_cat(c, &old_pnode->lprops[i],
0912                   &new_pnode->lprops[i]);
0913     }
0914 }
0915
0916 /**
0917  * check_lpt_crc - check LPT node crc is correct.
0918  * @c: UBIFS file-system description object
0919  * @buf: buffer containing node
0920  * @len: length of node
0921  *
0922  * This function returns %0 on success and a negative error code on failure.
0923  */
0924 static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len)
0925 {
0926     int pos = 0;
0927     uint8_t *addr = buf;
0928     uint16_t crc, calc_crc;
0929
0930     crc = ubifs_unpack_bits(c, &addr, &pos, UBIFS_LPT_CRC_BITS);
0931     calc_crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
0932              len - UBIFS_LPT_CRC_BYTES);
0933     if (crc != calc_crc) {
0934         ubifs_err(c, "invalid crc in LPT node: crc %hx calc %hx",
0935               crc, calc_crc);
0936         dump_stack();
0937         return -EINVAL;
0938     }
0939     return 0;
0940 }
0941
0942 /**
0943  * check_lpt_type - check LPT node type is correct.
0944  * @c: UBIFS file-system description object
0945  * @addr: address of type bit field is passed and returned updated here
0946  * @pos: position of type bit field is passed and returned updated here
0947  * @type: expected type
0948  *
0949  * This function returns %0 on success and a negative error code on failure.
0950  */
0951 static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr,
0952               int *pos, int type)
0953 {
0954     int node_type;
0955
0956     node_type = ubifs_unpack_bits(c, addr, pos, UBIFS_LPT_TYPE_BITS);
0957     if (node_type != type) {
0958         ubifs_err(c, "invalid type (%d) in LPT node type %d",
0959               node_type, type);
0960         dump_stack();
0961         return -EINVAL;
0962     }
0963     return 0;
0964 }
0965
0966 /**
0967  * unpack_pnode - unpack a pnode.
0968  * @c: UBIFS file-system description object
0969  * @buf: buffer containing packed pnode to unpack
0970  * @pnode: pnode structure to fill
0971  *
0972  * This function returns %0 on success and a negative error code on failure.
0973  */
0974 static int unpack_pnode(const struct ubifs_info *c, void *buf,
0975             struct ubifs_pnode *pnode)
0976 {
0977     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
0978     int i, pos = 0, err;
0979
0980     err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_PNODE);
0981     if (err)
0982         return err;
0983     if (c->big_lpt)
0984         pnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
0985     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
0986         struct ubifs_lprops * const lprops = &pnode->lprops[i];
0987
0988         lprops->free = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
0989         lprops->free <<= 3;
0990         lprops->dirty = ubifs_unpack_bits(c, &addr, &pos, c->space_bits);
0991         lprops->dirty <<= 3;
0992
0993         if (ubifs_unpack_bits(c, &addr, &pos, 1))
0994             lprops->flags = LPROPS_INDEX;
0995         else
0996             lprops->flags = 0;
0997         lprops->flags |= ubifs_categorize_lprops(c, lprops);
0998     }
0999     err = check_lpt_crc(c, buf, c->pnode_sz);
1000     return err;
1001 }
1002
1003 /**
1004  * ubifs_unpack_nnode - unpack a nnode.
1005  * @c: UBIFS file-system description object
1006  * @buf: buffer containing packed nnode to unpack
1007  * @nnode: nnode structure to fill
1008  *
1009  * This function returns %0 on success and a negative error code on failure.
1010  */
1011 int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf,
1012                struct ubifs_nnode *nnode)
1013 {
1014     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1015     int i, pos = 0, err;
1016
1017     err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_NNODE);
1018     if (err)
1019         return err;
1020     if (c->big_lpt)
1021         nnode->num = ubifs_unpack_bits(c, &addr, &pos, c->pcnt_bits);
1022     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1023         int lnum;
1024
1025         lnum = ubifs_unpack_bits(c, &addr, &pos, c->lpt_lnum_bits) +
1026                c->lpt_first;
1027         if (lnum == c->lpt_last + 1)
1028             lnum = 0;
1029         nnode->nbranch[i].lnum = lnum;
1030         nnode->nbranch[i].offs = ubifs_unpack_bits(c, &addr, &pos,
1031                              c->lpt_offs_bits);
1032     }
1033     err = check_lpt_crc(c, buf, c->nnode_sz);
1034     return err;
1035 }
1036
1037 /**
1038  * unpack_ltab - unpack the LPT's own lprops table.
1039  * @c: UBIFS file-system description object
1040  * @buf: buffer from which to unpack
1041  *
1042  * This function returns %0 on success and a negative error code on failure.
1043  */
1044 static int unpack_ltab(const struct ubifs_info *c, void *buf)
1045 {
1046     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1047     int i, pos = 0, err;
1048
1049     err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LTAB);
1050     if (err)
1051         return err;
1052     for (i = 0; i < c->lpt_lebs; i++) {
1053         int free = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
1054         int dirty = ubifs_unpack_bits(c, &addr, &pos, c->lpt_spc_bits);
1055
1056         if (free < 0 || free > c->leb_size || dirty < 0 ||
1057             dirty > c->leb_size || free + dirty > c->leb_size)
1058             return -EINVAL;
1059
1060         c->ltab[i].free = free;
1061         c->ltab[i].dirty = dirty;
1062         c->ltab[i].tgc = 0;
1063         c->ltab[i].cmt = 0;
1064     }
1065     err = check_lpt_crc(c, buf, c->ltab_sz);
1066     return err;
1067 }
1068
1069 /**
1070  * unpack_lsave - unpack the LPT's save table.
1071  * @c: UBIFS file-system description object
1072  * @buf: buffer from which to unpack
1073  *
1074  * This function returns %0 on success and a negative error code on failure.
1075  */
1076 static int unpack_lsave(const struct ubifs_info *c, void *buf)
1077 {
1078     uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
1079     int i, pos = 0, err;
1080
1081     err = check_lpt_type(c, &addr, &pos, UBIFS_LPT_LSAVE);
1082     if (err)
1083         return err;
1084     for (i = 0; i < c->lsave_cnt; i++) {
1085         int lnum = ubifs_unpack_bits(c, &addr, &pos, c->lnum_bits);
1086
1087         if (lnum < c->main_first || lnum >= c->leb_cnt)
1088             return -EINVAL;
1089         c->lsave[i] = lnum;
1090     }
1091     err = check_lpt_crc(c, buf, c->lsave_sz);
1092     return err;
1093 }
1094
1095 /**
1096  * validate_nnode - validate a nnode.
1097  * @c: UBIFS file-system description object
1098  * @nnode: nnode to validate
1099  * @parent: parent nnode (or NULL for the root nnode)
1100  * @iip: index in parent
1101  *
1102  * This function returns %0 on success and a negative error code on failure.
1103  */
1104 static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode,
1105               struct ubifs_nnode *parent, int iip)
1106 {
1107     int i, lvl, max_offs;
1108
1109     if (c->big_lpt) {
1110         int num = calc_nnode_num_from_parent(c, parent, iip);
1111
1112         if (nnode->num != num)
1113             return -EINVAL;
1114     }
1115     lvl = parent ? parent->level - 1 : c->lpt_hght;
1116     if (lvl < 1)
1117         return -EINVAL;
1118     if (lvl == 1)
1119         max_offs = c->leb_size - c->pnode_sz;
1120     else
1121         max_offs = c->leb_size - c->nnode_sz;
1122     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1123         int lnum = nnode->nbranch[i].lnum;
1124         int offs = nnode->nbranch[i].offs;
1125
1126         if (lnum == 0) {
1127             if (offs != 0)
1128                 return -EINVAL;
1129             continue;
1130         }
1131         if (lnum < c->lpt_first || lnum > c->lpt_last)
1132             return -EINVAL;
1133         if (offs < 0 || offs > max_offs)
1134             return -EINVAL;
1135     }
1136     return 0;
1137 }
1138
1139 /**
1140  * validate_pnode - validate a pnode.
1141  * @c: UBIFS file-system description object
1142  * @pnode: pnode to validate
1143  * @parent: parent nnode
1144  * @iip: index in parent
1145  *
1146  * This function returns %0 on success and a negative error code on failure.
1147  */
1148 static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode,
1149               struct ubifs_nnode *parent, int iip)
1150 {
1151     int i;
1152
1153     if (c->big_lpt) {
1154         int num = calc_pnode_num_from_parent(c, parent, iip);
1155
1156         if (pnode->num != num)
1157             return -EINVAL;
1158     }
1159     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1160         int free = pnode->lprops[i].free;
1161         int dirty = pnode->lprops[i].dirty;
1162
1163         if (free < 0 || free > c->leb_size || free % c->min_io_size ||
1164             (free & 7))
1165             return -EINVAL;
1166         if (dirty < 0 || dirty > c->leb_size || (dirty & 7))
1167             return -EINVAL;
1168         if (dirty + free > c->leb_size)
1169             return -EINVAL;
1170     }
1171     return 0;
1172 }
1173
1174 /**
1175  * set_pnode_lnum - set LEB numbers on a pnode.
1176  * @c: UBIFS file-system description object
1177  * @pnode: pnode to update
1178  *
1179  * This function calculates the LEB numbers for the LEB properties it contains
1180  * based on the pnode number.
1181  */
1182 static void set_pnode_lnum(const struct ubifs_info *c,
1183                struct ubifs_pnode *pnode)
1184 {
1185     int i, lnum;
1186
1187     lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + c->main_first;
1188     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1189         if (lnum >= c->leb_cnt)
1190             return;
1191         pnode->lprops[i].lnum = lnum++;
1192     }
1193 }
1194
1195 /**
1196  * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory.
1197  * @c: UBIFS file-system description object
1198  * @parent: parent nnode (or NULL for the root)
1199  * @iip: index in parent
1200  *
1201  * This function returns %0 on success and a negative error code on failure.
1202  */
1203 int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
1204 {
1205     struct ubifs_nbranch *branch = NULL;
1206     struct ubifs_nnode *nnode = NULL;
1207     void *buf = c->lpt_nod_buf;
1208     int err, lnum, offs;
1209
1210     if (parent) {
1211         branch = &parent->nbranch[iip];
1212         lnum = branch->lnum;
1213         offs = branch->offs;
1214     } else {
1215         lnum = c->lpt_lnum;
1216         offs = c->lpt_offs;
1217     }
1218     nnode = kzalloc(sizeof(struct ubifs_nnode), GFP_NOFS);
1219     if (!nnode) {
1220         err = -ENOMEM;
1221         goto out;
1222     }
1223     if (lnum == 0) {
1224         /*
1225          * This nnode was not written which just means that the LEB
1226          * properties in the subtree below it describe empty LEBs. We
1227          * make the nnode as though we had read it, which in fact means
1228          * doing almost nothing.
1229          */
1230         if (c->big_lpt)
1231             nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1232     } else {
1233         err = ubifs_leb_read(c, lnum, buf, offs, c->nnode_sz, 1);
1234         if (err)
1235             goto out;
1236         err = ubifs_unpack_nnode(c, buf, nnode);
1237         if (err)
1238             goto out;
1239     }
1240     err = validate_nnode(c, nnode, parent, iip);
1241     if (err)
1242         goto out;
1243     if (!c->big_lpt)
1244         nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1245     if (parent) {
1246         branch->nnode = nnode;
1247         nnode->level = parent->level - 1;
1248     } else {
1249         c->nroot = nnode;
1250         nnode->level = c->lpt_hght;
1251     }
1252     nnode->parent = parent;
1253     nnode->iip = iip;
1254     return 0;
1255
1256 out:
1257     ubifs_err(c, "error %d reading nnode at %d:%d", err, lnum, offs);
1258     dump_stack();
1259     kfree(nnode);
1260     return err;
1261 }
1262
1263 /**
1264  * read_pnode - read a pnode from flash and link it to the tree in memory.
1265  * @c: UBIFS file-system description object
1266  * @parent: parent nnode
1267  * @iip: index in parent
1268  *
1269  * This function returns %0 on success and a negative error code on failure.
1270  */
1271 static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip)
1272 {
1273     struct ubifs_nbranch *branch;
1274     struct ubifs_pnode *pnode = NULL;
1275     void *buf = c->lpt_nod_buf;
1276     int err, lnum, offs;
1277
1278     branch = &parent->nbranch[iip];
1279     lnum = branch->lnum;
1280     offs = branch->offs;
1281     pnode = kzalloc(sizeof(struct ubifs_pnode), GFP_NOFS);
1282     if (!pnode)
1283         return -ENOMEM;
1284
1285     if (lnum == 0) {
1286         /*
1287          * This pnode was not written which just means that the LEB
1288          * properties in it describe empty LEBs. We make the pnode as
1289          * though we had read it.
1290          */
1291         int i;
1292
1293         if (c->big_lpt)
1294             pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1295         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1296             struct ubifs_lprops * const lprops = &pnode->lprops[i];
1297
1298             lprops->free = c->leb_size;
1299             lprops->flags = ubifs_categorize_lprops(c, lprops);
1300         }
1301     } else {
1302         err = ubifs_leb_read(c, lnum, buf, offs, c->pnode_sz, 1);
1303         if (err)
1304             goto out;
1305         err = unpack_pnode(c, buf, pnode);
1306         if (err)
1307             goto out;
1308     }
1309     err = validate_pnode(c, pnode, parent, iip);
1310     if (err)
1311         goto out;
1312     if (!c->big_lpt)
1313         pnode->num = calc_pnode_num_from_parent(c, parent, iip);
1314     branch->pnode = pnode;
1315     pnode->parent = parent;
1316     pnode->iip = iip;
1317     set_pnode_lnum(c, pnode);
1318     c->pnodes_have += 1;
1319     return 0;
1320
1321 out:
1322     ubifs_err(c, "error %d reading pnode at %d:%d", err, lnum, offs);
1323     ubifs_dump_pnode(c, pnode, parent, iip);
1324     dump_stack();
1325     ubifs_err(c, "calc num: %d", calc_pnode_num_from_parent(c, parent, iip));
1326     kfree(pnode);
1327     return err;
1328 }
1329
1330 /**
1331  * read_ltab - read LPT's own lprops table.
1332  * @c: UBIFS file-system description object
1333  *
1334  * This function returns %0 on success and a negative error code on failure.
1335  */
1336 static int read_ltab(struct ubifs_info *c)
1337 {
1338     int err;
1339     void *buf;
1340
1341     buf = vmalloc(c->ltab_sz);
1342     if (!buf)
1343         return -ENOMEM;
1344     err = ubifs_leb_read(c, c->ltab_lnum, buf, c->ltab_offs, c->ltab_sz, 1);
1345     if (err)
1346         goto out;
1347     err = unpack_ltab(c, buf);
1348 out:
1349     vfree(buf);
1350     return err;
1351 }
1352
1353 /**
1354  * read_lsave - read LPT's save table.
1355  * @c: UBIFS file-system description object
1356  *
1357  * This function returns %0 on success and a negative error code on failure.
1358  */
1359 static int read_lsave(struct ubifs_info *c)
1360 {
1361     int err, i;
1362     void *buf;
1363
1364     buf = vmalloc(c->lsave_sz);
1365     if (!buf)
1366         return -ENOMEM;
1367     err = ubifs_leb_read(c, c->lsave_lnum, buf, c->lsave_offs,
1368                  c->lsave_sz, 1);
1369     if (err)
1370         goto out;
1371     err = unpack_lsave(c, buf);
1372     if (err)
1373         goto out;
1374     for (i = 0; i < c->lsave_cnt; i++) {
1375         int lnum = c->lsave[i];
1376         struct ubifs_lprops *lprops;
1377
1378         /*
1379          * Due to automatic resizing, the values in the lsave table
1380          * could be beyond the volume size - just ignore them.
1381          */
1382         if (lnum >= c->leb_cnt)
1383             continue;
1384         lprops = ubifs_lpt_lookup(c, lnum);
1385         if (IS_ERR(lprops)) {
1386             err = PTR_ERR(lprops);
1387             goto out;
1388         }
1389     }
1390 out:
1391     vfree(buf);
1392     return err;
1393 }
1394
1395 /**
1396  * ubifs_get_nnode - get a nnode.
1397  * @c: UBIFS file-system description object
1398  * @parent: parent nnode (or NULL for the root)
1399  * @iip: index in parent
1400  *
1401  * This function returns a pointer to the nnode on success or a negative error
1402  * code on failure.
1403  */
1404 struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c,
1405                     struct ubifs_nnode *parent, int iip)
1406 {
1407     struct ubifs_nbranch *branch;
1408     struct ubifs_nnode *nnode;
1409     int err;
1410
1411     branch = &parent->nbranch[iip];
1412     nnode = branch->nnode;
1413     if (nnode)
1414         return nnode;
1415     err = ubifs_read_nnode(c, parent, iip);
1416     if (err)
1417         return ERR_PTR(err);
1418     return branch->nnode;
1419 }
1420
1421 /**
1422  * ubifs_get_pnode - get a pnode.
1423  * @c: UBIFS file-system description object
1424  * @parent: parent nnode
1425  * @iip: index in parent
1426  *
1427  * This function returns a pointer to the pnode on success or a negative error
1428  * code on failure.
1429  */
1430 struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c,
1431                     struct ubifs_nnode *parent, int iip)
1432 {
1433     struct ubifs_nbranch *branch;
1434     struct ubifs_pnode *pnode;
1435     int err;
1436
1437     branch = &parent->nbranch[iip];
1438     pnode = branch->pnode;
1439     if (pnode)
1440         return pnode;
1441     err = read_pnode(c, parent, iip);
1442     if (err)
1443         return ERR_PTR(err);
1444     update_cats(c, branch->pnode);
1445     return branch->pnode;
1446 }
1447
1448 /**
1449  * ubifs_pnode_lookup - lookup a pnode in the LPT.
1450  * @c: UBIFS file-system description object
1451  * @i: pnode number (0 to (main_lebs - 1) / UBIFS_LPT_FANOUT)
1452  *
1453  * This function returns a pointer to the pnode on success or a negative
1454  * error code on failure.
1455  */
1456 struct ubifs_pnode *ubifs_pnode_lookup(struct ubifs_info *c, int i)
1457 {
1458     int err, h, iip, shft;
1459     struct ubifs_nnode *nnode;
1460
1461     if (!c->nroot) {
1462         err = ubifs_read_nnode(c, NULL, 0);
1463         if (err)
1464             return ERR_PTR(err);
1465     }
1466     i <<= UBIFS_LPT_FANOUT_SHIFT;
1467     nnode = c->nroot;
1468     shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1469     for (h = 1; h < c->lpt_hght; h++) {
1470         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1471         shft -= UBIFS_LPT_FANOUT_SHIFT;
1472         nnode = ubifs_get_nnode(c, nnode, iip);
1473         if (IS_ERR(nnode))
1474             return ERR_CAST(nnode);
1475     }
1476     iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1477     return ubifs_get_pnode(c, nnode, iip);
1478 }
1479
1480 /**
1481  * ubifs_lpt_lookup - lookup LEB properties in the LPT.
1482  * @c: UBIFS file-system description object
1483  * @lnum: LEB number to lookup
1484  *
1485  * This function returns a pointer to the LEB properties on success or a
1486  * negative error code on failure.
1487  */
1488 struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum)
1489 {
1490     int i, iip;
1491     struct ubifs_pnode *pnode;
1492
1493     i = lnum - c->main_first;
1494     pnode = ubifs_pnode_lookup(c, i >> UBIFS_LPT_FANOUT_SHIFT);
1495     if (IS_ERR(pnode))
1496         return ERR_CAST(pnode);
1497     iip = (i & (UBIFS_LPT_FANOUT - 1));
1498     dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1499            pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1500            pnode->lprops[iip].flags);
1501     return &pnode->lprops[iip];
1502 }
1503
1504 /**
1505  * dirty_cow_nnode - ensure a nnode is not being committed.
1506  * @c: UBIFS file-system description object
1507  * @nnode: nnode to check
1508  *
1509  * Returns dirtied nnode on success or negative error code on failure.
1510  */
1511 static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c,
1512                        struct ubifs_nnode *nnode)
1513 {
1514     struct ubifs_nnode *n;
1515     int i;
1516
1517     if (!test_bit(COW_CNODE, &nnode->flags)) {
1518         /* nnode is not being committed */
1519         if (!test_and_set_bit(DIRTY_CNODE, &nnode->flags)) {
1520             c->dirty_nn_cnt += 1;
1521             ubifs_add_nnode_dirt(c, nnode);
1522         }
1523         return nnode;
1524     }
1525
1526     /* nnode is being committed, so copy it */
1527     n = kmemdup(nnode, sizeof(struct ubifs_nnode), GFP_NOFS);
1528     if (unlikely(!n))
1529         return ERR_PTR(-ENOMEM);
1530
1531     n->cnext = NULL;
1532     __set_bit(DIRTY_CNODE, &n->flags);
1533     __clear_bit(COW_CNODE, &n->flags);
1534
1535     /* The children now have new parent */
1536     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1537         struct ubifs_nbranch *branch = &n->nbranch[i];
1538
1539         if (branch->cnode)
1540             branch->cnode->parent = n;
1541     }
1542
1543     ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &nnode->flags));
1544     __set_bit(OBSOLETE_CNODE, &nnode->flags);
1545
1546     c->dirty_nn_cnt += 1;
1547     ubifs_add_nnode_dirt(c, nnode);
1548     if (nnode->parent)
1549         nnode->parent->nbranch[n->iip].nnode = n;
1550     else
1551         c->nroot = n;
1552     return n;
1553 }
1554
1555 /**
1556  * dirty_cow_pnode - ensure a pnode is not being committed.
1557  * @c: UBIFS file-system description object
1558  * @pnode: pnode to check
1559  *
1560  * Returns dirtied pnode on success or negative error code on failure.
1561  */
1562 static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c,
1563                        struct ubifs_pnode *pnode)
1564 {
1565     struct ubifs_pnode *p;
1566
1567     if (!test_bit(COW_CNODE, &pnode->flags)) {
1568         /* pnode is not being committed */
1569         if (!test_and_set_bit(DIRTY_CNODE, &pnode->flags)) {
1570             c->dirty_pn_cnt += 1;
1571             add_pnode_dirt(c, pnode);
1572         }
1573         return pnode;
1574     }
1575
1576     /* pnode is being committed, so copy it */
1577     p = kmemdup(pnode, sizeof(struct ubifs_pnode), GFP_NOFS);
1578     if (unlikely(!p))
1579         return ERR_PTR(-ENOMEM);
1580
1581     p->cnext = NULL;
1582     __set_bit(DIRTY_CNODE, &p->flags);
1583     __clear_bit(COW_CNODE, &p->flags);
1584     replace_cats(c, pnode, p);
1585
1586     ubifs_assert(c, !test_bit(OBSOLETE_CNODE, &pnode->flags));
1587     __set_bit(OBSOLETE_CNODE, &pnode->flags);
1588
1589     c->dirty_pn_cnt += 1;
1590     add_pnode_dirt(c, pnode);
1591     pnode->parent->nbranch[p->iip].pnode = p;
1592     return p;
1593 }
1594
1595 /**
1596  * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT.
1597  * @c: UBIFS file-system description object
1598  * @lnum: LEB number to lookup
1599  *
1600  * This function returns a pointer to the LEB properties on success or a
1601  * negative error code on failure.
1602  */
1603 struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum)
1604 {
1605     int err, i, h, iip, shft;
1606     struct ubifs_nnode *nnode;
1607     struct ubifs_pnode *pnode;
1608
1609     if (!c->nroot) {
1610         err = ubifs_read_nnode(c, NULL, 0);
1611         if (err)
1612             return ERR_PTR(err);
1613     }
1614     nnode = c->nroot;
1615     nnode = dirty_cow_nnode(c, nnode);
1616     if (IS_ERR(nnode))
1617         return ERR_CAST(nnode);
1618     i = lnum - c->main_first;
1619     shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
1620     for (h = 1; h < c->lpt_hght; h++) {
1621         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1622         shft -= UBIFS_LPT_FANOUT_SHIFT;
1623         nnode = ubifs_get_nnode(c, nnode, iip);
1624         if (IS_ERR(nnode))
1625             return ERR_CAST(nnode);
1626         nnode = dirty_cow_nnode(c, nnode);
1627         if (IS_ERR(nnode))
1628             return ERR_CAST(nnode);
1629     }
1630     iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
1631     pnode = ubifs_get_pnode(c, nnode, iip);
1632     if (IS_ERR(pnode))
1633         return ERR_CAST(pnode);
1634     pnode = dirty_cow_pnode(c, pnode);
1635     if (IS_ERR(pnode))
1636         return ERR_CAST(pnode);
1637     iip = (i & (UBIFS_LPT_FANOUT - 1));
1638     dbg_lp("LEB %d, free %d, dirty %d, flags %d", lnum,
1639            pnode->lprops[iip].free, pnode->lprops[iip].dirty,
1640            pnode->lprops[iip].flags);
1641     ubifs_assert(c, test_bit(DIRTY_CNODE, &pnode->flags));
1642     return &pnode->lprops[iip];
1643 }
1644
1645 /**
1646  * ubifs_lpt_calc_hash - Calculate hash of the LPT pnodes
1647  * @c: UBIFS file-system description object
1648  * @hash: the returned hash of the LPT pnodes
1649  *
1650  * This function iterates over the LPT pnodes and creates a hash over them.
1651  * Returns 0 for success or a negative error code otherwise.
1652  */
1653 int ubifs_lpt_calc_hash(struct ubifs_info *c, u8 *hash)
1654 {
1655     struct ubifs_nnode *nnode, *nn;
1656     struct ubifs_cnode *cnode;
1657     struct shash_desc *desc;
1658     int iip = 0, i;
1659     int bufsiz = max_t(int, c->nnode_sz, c->pnode_sz);
1660     void *buf;
1661     int err;
1662
1663     if (!ubifs_authenticated(c))
1664         return 0;
1665
1666     if (!c->nroot) {
1667         err = ubifs_read_nnode(c, NULL, 0);
1668         if (err)
1669             return err;
1670     }
1671
1672     desc = ubifs_hash_get_desc(c);
1673     if (IS_ERR(desc))
1674         return PTR_ERR(desc);
1675
1676     buf = kmalloc(bufsiz, GFP_NOFS);
1677     if (!buf) {
1678         err = -ENOMEM;
1679         goto out;
1680     }
1681
1682     cnode = (struct ubifs_cnode *)c->nroot;
1683
1684     while (cnode) {
1685         nnode = cnode->parent;
1686         nn = (struct ubifs_nnode *)cnode;
1687         if (cnode->level > 1) {
1688             while (iip < UBIFS_LPT_FANOUT) {
1689                 if (nn->nbranch[iip].lnum == 0) {
1690                     /* Go right */
1691                     iip++;
1692                     continue;
1693                 }
1694
1695                 nnode = ubifs_get_nnode(c, nn, iip);
1696                 if (IS_ERR(nnode)) {
1697                     err = PTR_ERR(nnode);
1698                     goto out;
1699                 }
1700
1701                 /* Go down */
1702                 iip = 0;
1703                 cnode = (struct ubifs_cnode *)nnode;
1704                 break;
1705             }
1706             if (iip < UBIFS_LPT_FANOUT)
1707                 continue;
1708         } else {
1709             struct ubifs_pnode *pnode;
1710
1711             for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
1712                 if (nn->nbranch[i].lnum == 0)
1713                     continue;
1714                 pnode = ubifs_get_pnode(c, nn, i);
1715                 if (IS_ERR(pnode)) {
1716                     err = PTR_ERR(pnode);
1717                     goto out;
1718                 }
1719
1720                 ubifs_pack_pnode(c, buf, pnode);
1721                 err = ubifs_shash_update(c, desc, buf,
1722                              c->pnode_sz);
1723                 if (err)
1724                     goto out;
1725             }
1726         }
1727         /* Go up and to the right */
1728         iip = cnode->iip + 1;
1729         cnode = (struct ubifs_cnode *)nnode;
1730     }
1731
1732     err = ubifs_shash_final(c, desc, hash);
1733 out:
1734     kfree(desc);
1735     kfree(buf);
1736
1737     return err;
1738 }
1739
1740 /**
1741  * lpt_check_hash - check the hash of the LPT.
1742  * @c: UBIFS file-system description object
1743  *
1744  * This function calculates a hash over all pnodes in the LPT and compares it with
1745  * the hash stored in the master node. Returns %0 on success and a negative error
1746  * code on failure.
1747  */
1748 static int lpt_check_hash(struct ubifs_info *c)
1749 {
1750     int err;
1751     u8 hash[UBIFS_HASH_ARR_SZ];
1752
1753     if (!ubifs_authenticated(c))
1754         return 0;
1755
1756     err = ubifs_lpt_calc_hash(c, hash);
1757     if (err)
1758         return err;
1759
1760     if (ubifs_check_hash(c, c->mst_node->hash_lpt, hash)) {
1761         err = -EPERM;
1762         ubifs_err(c, "Failed to authenticate LPT");
1763     } else {
1764         err = 0;
1765     }
1766
1767     return err;
1768 }
1769
1770 /**
1771  * lpt_init_rd - initialize the LPT for reading.
1772  * @c: UBIFS file-system description object
1773  *
1774  * This function returns %0 on success and a negative error code on failure.
1775  */
1776 static int lpt_init_rd(struct ubifs_info *c)
1777 {
1778     int err, i;
1779
1780     c->ltab = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
1781                      c->lpt_lebs));
1782     if (!c->ltab)
1783         return -ENOMEM;
1784
1785     i = max_t(int, c->nnode_sz, c->pnode_sz);
1786     c->lpt_nod_buf = kmalloc(i, GFP_KERNEL);
1787     if (!c->lpt_nod_buf)
1788         return -ENOMEM;
1789
1790     for (i = 0; i < LPROPS_HEAP_CNT; i++) {
1791         c->lpt_heap[i].arr = kmalloc_array(LPT_HEAP_SZ,
1792                            sizeof(void *),
1793                            GFP_KERNEL);
1794         if (!c->lpt_heap[i].arr)
1795             return -ENOMEM;
1796         c->lpt_heap[i].cnt = 0;
1797         c->lpt_heap[i].max_cnt = LPT_HEAP_SZ;
1798     }
1799
1800     c->dirty_idx.arr = kmalloc_array(LPT_HEAP_SZ, sizeof(void *),
1801                      GFP_KERNEL);
1802     if (!c->dirty_idx.arr)
1803         return -ENOMEM;
1804     c->dirty_idx.cnt = 0;
1805     c->dirty_idx.max_cnt = LPT_HEAP_SZ;
1806
1807     err = read_ltab(c);
1808     if (err)
1809         return err;
1810
1811     err = lpt_check_hash(c);
1812     if (err)
1813         return err;
1814
1815     dbg_lp("space_bits %d", c->space_bits);
1816     dbg_lp("lpt_lnum_bits %d", c->lpt_lnum_bits);
1817     dbg_lp("lpt_offs_bits %d", c->lpt_offs_bits);
1818     dbg_lp("lpt_spc_bits %d", c->lpt_spc_bits);
1819     dbg_lp("pcnt_bits %d", c->pcnt_bits);
1820     dbg_lp("lnum_bits %d", c->lnum_bits);
1821     dbg_lp("pnode_sz %d", c->pnode_sz);
1822     dbg_lp("nnode_sz %d", c->nnode_sz);
1823     dbg_lp("ltab_sz %d", c->ltab_sz);
1824     dbg_lp("lsave_sz %d", c->lsave_sz);
1825     dbg_lp("lsave_cnt %d", c->lsave_cnt);
1826     dbg_lp("lpt_hght %d", c->lpt_hght);
1827     dbg_lp("big_lpt %u", c->big_lpt);
1828     dbg_lp("LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs);
1829     dbg_lp("LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs);
1830     dbg_lp("LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs);
1831     if (c->big_lpt)
1832         dbg_lp("LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs);
1833
1834     return 0;
1835 }
1836
1837 /**
1838  * lpt_init_wr - initialize the LPT for writing.
1839  * @c: UBIFS file-system description object
1840  *
1841  * 'lpt_init_rd()' must have been called already.
1842  *
1843  * This function returns %0 on success and a negative error code on failure.
1844  */
1845 static int lpt_init_wr(struct ubifs_info *c)
1846 {
1847     int err, i;
1848
1849     c->ltab_cmt = vmalloc(array_size(sizeof(struct ubifs_lpt_lprops),
1850                      c->lpt_lebs));
1851     if (!c->ltab_cmt)
1852         return -ENOMEM;
1853
1854     c->lpt_buf = vmalloc(c->leb_size);
1855     if (!c->lpt_buf)
1856         return -ENOMEM;
1857
1858     if (c->big_lpt) {
1859         c->lsave = kmalloc_array(c->lsave_cnt, sizeof(int), GFP_NOFS);
1860         if (!c->lsave)
1861             return -ENOMEM;
1862         err = read_lsave(c);
1863         if (err)
1864             return err;
1865     }
1866
1867     for (i = 0; i < c->lpt_lebs; i++)
1868         if (c->ltab[i].free == c->leb_size) {
1869             err = ubifs_leb_unmap(c, i + c->lpt_first);
1870             if (err)
1871                 return err;
1872         }
1873
1874     return 0;
1875 }
1876
1877 /**
1878  * ubifs_lpt_init - initialize the LPT.
1879  * @c: UBIFS file-system description object
1880  * @rd: whether to initialize lpt for reading
1881  * @wr: whether to initialize lpt for writing
1882  *
1883  * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true
1884  * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is
1885  * true.
1886  *
1887  * This function returns %0 on success and a negative error code on failure.
1888  */
1889 int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr)
1890 {
1891     int err;
1892
1893     if (rd) {
1894         err = lpt_init_rd(c);
1895         if (err)
1896             goto out_err;
1897     }
1898
1899     if (wr) {
1900         err = lpt_init_wr(c);
1901         if (err)
1902             goto out_err;
1903     }
1904
1905     return 0;
1906
1907 out_err:
1908     if (wr)
1909         ubifs_lpt_free(c, 1);
1910     if (rd)
1911         ubifs_lpt_free(c, 0);
1912     return err;
1913 }
1914
1915 /**
1916  * struct lpt_scan_node - somewhere to put nodes while we scan LPT.
1917  * @nnode: where to keep a nnode
1918  * @pnode: where to keep a pnode
1919  * @cnode: where to keep a cnode
1920  * @in_tree: is the node in the tree in memory
1921  * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in
1922  * the tree
1923  * @ptr.pnode: ditto for pnode
1924  * @ptr.cnode: ditto for cnode
1925  */
1926 struct lpt_scan_node {
1927     union {
1928         struct ubifs_nnode nnode;
1929         struct ubifs_pnode pnode;
1930         struct ubifs_cnode cnode;
1931     };
1932     int in_tree;
1933     union {
1934         struct ubifs_nnode *nnode;
1935         struct ubifs_pnode *pnode;
1936         struct ubifs_cnode *cnode;
1937     } ptr;
1938 };
1939
1940 /**
1941  * scan_get_nnode - for the scan, get a nnode from either the tree or flash.
1942  * @c: the UBIFS file-system description object
1943  * @path: where to put the nnode
1944  * @parent: parent of the nnode
1945  * @iip: index in parent of the nnode
1946  *
1947  * This function returns a pointer to the nnode on success or a negative error
1948  * code on failure.
1949  */
1950 static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c,
1951                       struct lpt_scan_node *path,
1952                       struct ubifs_nnode *parent, int iip)
1953 {
1954     struct ubifs_nbranch *branch;
1955     struct ubifs_nnode *nnode;
1956     void *buf = c->lpt_nod_buf;
1957     int err;
1958
1959     branch = &parent->nbranch[iip];
1960     nnode = branch->nnode;
1961     if (nnode) {
1962         path->in_tree = 1;
1963         path->ptr.nnode = nnode;
1964         return nnode;
1965     }
1966     nnode = &path->nnode;
1967     path->in_tree = 0;
1968     path->ptr.nnode = nnode;
1969     memset(nnode, 0, sizeof(struct ubifs_nnode));
1970     if (branch->lnum == 0) {
1971         /*
1972          * This nnode was not written which just means that the LEB
1973          * properties in the subtree below it describe empty LEBs. We
1974          * make the nnode as though we had read it, which in fact means
1975          * doing almost nothing.
1976          */
1977         if (c->big_lpt)
1978             nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1979     } else {
1980         err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
1981                      c->nnode_sz, 1);
1982         if (err)
1983             return ERR_PTR(err);
1984         err = ubifs_unpack_nnode(c, buf, nnode);
1985         if (err)
1986             return ERR_PTR(err);
1987     }
1988     err = validate_nnode(c, nnode, parent, iip);
1989     if (err)
1990         return ERR_PTR(err);
1991     if (!c->big_lpt)
1992         nnode->num = calc_nnode_num_from_parent(c, parent, iip);
1993     nnode->level = parent->level - 1;
1994     nnode->parent = parent;
1995     nnode->iip = iip;
1996     return nnode;
1997 }
1998
1999 /**
2000  * scan_get_pnode - for the scan, get a pnode from either the tree or flash.
2001  * @c: the UBIFS file-system description object
2002  * @path: where to put the pnode
2003  * @parent: parent of the pnode
2004  * @iip: index in parent of the pnode
2005  *
2006  * This function returns a pointer to the pnode on success or a negative error
2007  * code on failure.
2008  */
2009 static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c,
2010                       struct lpt_scan_node *path,
2011                       struct ubifs_nnode *parent, int iip)
2012 {
2013     struct ubifs_nbranch *branch;
2014     struct ubifs_pnode *pnode;
2015     void *buf = c->lpt_nod_buf;
2016     int err;
2017
2018     branch = &parent->nbranch[iip];
2019     pnode = branch->pnode;
2020     if (pnode) {
2021         path->in_tree = 1;
2022         path->ptr.pnode = pnode;
2023         return pnode;
2024     }
2025     pnode = &path->pnode;
2026     path->in_tree = 0;
2027     path->ptr.pnode = pnode;
2028     memset(pnode, 0, sizeof(struct ubifs_pnode));
2029     if (branch->lnum == 0) {
2030         /*
2031          * This pnode was not written which just means that the LEB
2032          * properties in it describe empty LEBs. We make the pnode as
2033          * though we had read it.
2034          */
2035         int i;
2036
2037         if (c->big_lpt)
2038             pnode->num = calc_pnode_num_from_parent(c, parent, iip);
2039         for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
2040             struct ubifs_lprops * const lprops = &pnode->lprops[i];
2041
2042             lprops->free = c->leb_size;
2043             lprops->flags = ubifs_categorize_lprops(c, lprops);
2044         }
2045     } else {
2046         ubifs_assert(c, branch->lnum >= c->lpt_first &&
2047                  branch->lnum <= c->lpt_last);
2048         ubifs_assert(c, branch->offs >= 0 && branch->offs < c->leb_size);
2049         err = ubifs_leb_read(c, branch->lnum, buf, branch->offs,
2050                      c->pnode_sz, 1);
2051         if (err)
2052             return ERR_PTR(err);
2053         err = unpack_pnode(c, buf, pnode);
2054         if (err)
2055             return ERR_PTR(err);
2056     }
2057     err = validate_pnode(c, pnode, parent, iip);
2058     if (err)
2059         return ERR_PTR(err);
2060     if (!c->big_lpt)
2061         pnode->num = calc_pnode_num_from_parent(c, parent, iip);
2062     pnode->parent = parent;
2063     pnode->iip = iip;
2064     set_pnode_lnum(c, pnode);
2065     return pnode;
2066 }
2067
2068 /**
2069  * ubifs_lpt_scan_nolock - scan the LPT.
2070  * @c: the UBIFS file-system description object
2071  * @start_lnum: LEB number from which to start scanning
2072  * @end_lnum: LEB number at which to stop scanning
2073  * @scan_cb: callback function called for each lprops
2074  * @data: data to be passed to the callback function
2075  *
2076  * This function returns %0 on success and a negative error code on failure.
2077  */
2078 int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum,
2079               ubifs_lpt_scan_callback scan_cb, void *data)
2080 {
2081     int err = 0, i, h, iip, shft;
2082     struct ubifs_nnode *nnode;
2083     struct ubifs_pnode *pnode;
2084     struct lpt_scan_node *path;
2085
2086     if (start_lnum == -1) {
2087         start_lnum = end_lnum + 1;
2088         if (start_lnum >= c->leb_cnt)
2089             start_lnum = c->main_first;
2090     }
2091
2092     ubifs_assert(c, start_lnum >= c->main_first && start_lnum < c->leb_cnt);
2093     ubifs_assert(c, end_lnum >= c->main_first && end_lnum < c->leb_cnt);
2094
2095     if (!c->nroot) {
2096         err = ubifs_read_nnode(c, NULL, 0);
2097         if (err)
2098             return err;
2099     }
2100
2101     path = kmalloc_array(c->lpt_hght + 1, sizeof(struct lpt_scan_node),
2102                  GFP_NOFS);
2103     if (!path)
2104         return -ENOMEM;
2105
2106     path[0].ptr.nnode = c->nroot;
2107     path[0].in_tree = 1;
2108 again:
2109     /* Descend to the pnode containing start_lnum */
2110     nnode = c->nroot;
2111     i = start_lnum - c->main_first;
2112     shft = c->lpt_hght * UBIFS_LPT_FANOUT_SHIFT;
2113     for (h = 1; h < c->lpt_hght; h++) {
2114         iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
2115         shft -= UBIFS_LPT_FANOUT_SHIFT;
2116         nnode = scan_get_nnode(c, path + h, nnode, iip);
2117         if (IS_ERR(nnode)) {
2118             err = PTR_ERR(nnode);
2119             goto out;
2120         }
2121     }
2122     iip = ((i >> shft) & (UBIFS_LPT_FANOUT - 1));
2123     pnode = scan_get_pnode(c, path + h, nnode, iip);
2124     if (IS_ERR(pnode)) {
2125         err = PTR_ERR(pnode);
2126         goto out;
2127     }
2128     iip = (i & (UBIFS_LPT_FANOUT - 1));
2129
2130     /* Loop for each lprops */
2131     while (1) {
2132         struct ubifs_lprops *lprops = &pnode->lprops[iip];
2133         int ret, lnum = lprops->lnum;
2134
2135         ret = scan_cb(c, lprops, path[h].in_tree, data);
2136         if (ret < 0) {
2137             err = ret;
2138             goto out;
2139         }
2140         if (ret & LPT_SCAN_ADD) {
2141             /* Add all the nodes in path to the tree in memory */
2142             for (h = 1; h < c->lpt_hght; h++) {
2143                 const size_t sz = sizeof(struct ubifs_nnode);
2144                 struct ubifs_nnode *parent;
2145
2146                 if (path[h].in_tree)
2147                     continue;
2148                 nnode = kmemdup(&path[h].nnode, sz, GFP_NOFS);
2149                 if (!nnode) {
2150                     err = -ENOMEM;
2151                     goto out;
2152                 }
2153                 parent = nnode->parent;
2154                 parent->nbranch[nnode->iip].nnode = nnode;
2155                 path[h].ptr.nnode = nnode;
2156                 path[h].in_tree = 1;
2157                 path[h + 1].cnode.parent = nnode;
2158             }
2159             if (path[h].in_tree)
2160                 ubifs_ensure_cat(c, lprops);
2161             else {
2162                 const size_t sz = sizeof(struct ubifs_pnode);
2163                 struct ubifs_nnode *parent;
2164
2165                 pnode = kmemdup(&path[h].pnode, sz, GFP_NOFS);
2166                 if (!pnode) {
2167                     err = -ENOMEM;
2168                     goto out;
2169                 }
2170                 parent = pnode->parent;
2171                 parent->nbranch[pnode->iip].pnode = pnode;
2172                 path[h].ptr.pnode = pnode;
2173                 path[h].in_tree = 1;
2174                 update_cats(c, pnode);
2175                 c->pnodes_have += 1;
2176             }
2177             err = dbg_check_lpt_nodes(c, (struct ubifs_cnode *)
2178                           c->nroot, 0, 0);
2179             if (err)
2180                 goto out;
2181             err = dbg_check_cats(c);
2182             if (err)
2183                 goto out;
2184         }
2185         if (ret & LPT_SCAN_STOP) {
2186             err = 0;
2187             break;
2188         }
2189         /* Get the next lprops */
2190         if (lnum == end_lnum) {
2191             /*
2192              * We got to the end without finding what we were
2193              * looking for
2194              */
2195             err = -ENOSPC;
2196             goto out;
2197         }
2198         if (lnum + 1 >= c->leb_cnt) {
2199             /* Wrap-around to the beginning */
2200             start_lnum = c->main_first;
2201             goto again;
2202         }
2203         if (iip + 1 < UBIFS_LPT_FANOUT) {
2204             /* Next lprops is in the same pnode */
2205             iip += 1;
2206             continue;
2207         }
2208         /* We need to get the next pnode. Go up until we can go right */
2209         iip = pnode->iip;
2210         while (1) {
2211             h -= 1;
2212             ubifs_assert(c, h >= 0);
2213             nnode = path[h].ptr.nnode;
2214             if (iip + 1 < UBIFS_LPT_FANOUT)
2215                 break;
2216             iip = nnode->iip;
2217         }
2218         /* Go right */
2219         iip += 1;
2220         /* Descend to the pnode */
2221         h += 1;
2222         for (; h < c->lpt_hght; h++) {
2223             nnode = scan_get_nnode(c, path + h, nnode, iip);
2224             if (IS_ERR(nnode)) {
2225                 err = PTR_ERR(nnode);
2226                 goto out;
2227             }
2228             iip = 0;
2229         }
2230         pnode = scan_get_pnode(c, path + h, nnode, iip);
2231         if (IS_ERR(pnode)) {
2232             err = PTR_ERR(pnode);
2233             goto out;
2234         }
2235         iip = 0;
2236     }
2237 out:
2238     kfree(path);
2239     return err;
2240 }
2241
2242 /**
2243  * dbg_chk_pnode - check a pnode.
2244  * @c: the UBIFS file-system description object
2245  * @pnode: pnode to check
2246  * @col: pnode column
2247  *
2248  * This function returns %0 on success and a negative error code on failure.
2249  */
2250 static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode,
2251              int col)
2252 {
2253     int i;
2254
2255     if (pnode->num != col) {
2256         ubifs_err(c, "pnode num %d expected %d parent num %d iip %d",
2257               pnode->num, col, pnode->parent->num, pnode->iip);
2258         return -EINVAL;
2259     }
2260     for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
2261         struct ubifs_lprops *lp, *lprops = &pnode->lprops[i];
2262         int lnum = (pnode->num << UBIFS_LPT_FANOUT_SHIFT) + i +
2263                c->main_first;
2264         int found, cat = lprops->flags & LPROPS_CAT_MASK;
2265         struct ubifs_lpt_heap *heap;
2266         struct list_head *list = NULL;
2267
2268         if (lnum >= c->leb_cnt)
2269             continue;
2270         if (lprops->lnum != lnum) {
2271             ubifs_err(c, "bad LEB number %d expected %d",
2272                   lprops->lnum, lnum);
2273             return -EINVAL;
2274         }
2275         if (lprops->flags & LPROPS_TAKEN) {
2276             if (cat != LPROPS_UNCAT) {
2277                 ubifs_err(c, "LEB %d taken but not uncat %d",
2278                       lprops->lnum, cat);
2279                 return -EINVAL;
2280             }
2281             continue;
2282         }
2283         if (lprops->flags & LPROPS_INDEX) {
2284             switch (cat) {
2285             case LPROPS_UNCAT:
2286             case LPROPS_DIRTY_IDX:
2287             case LPROPS_FRDI_IDX:
2288                 break;
2289             default:
2290                 ubifs_err(c, "LEB %d index but cat %d",
2291                       lprops->lnum, cat);
2292                 return -EINVAL;
2293             }
2294         } else {
2295             switch (cat) {
2296             case LPROPS_UNCAT:
2297             case LPROPS_DIRTY:
2298             case LPROPS_FREE:
2299             case LPROPS_EMPTY:
2300             case LPROPS_FREEABLE:
2301                 break;
2302             default:
2303                 ubifs_err(c, "LEB %d not index but cat %d",
2304                       lprops->lnum, cat);
2305                 return -EINVAL;
2306             }
2307         }
2308         switch (cat) {
2309         case LPROPS_UNCAT:
2310             list = &c->uncat_list;
2311             break;
2312         case LPROPS_EMPTY:
2313             list = &c->empty_list;
2314             break;
2315         case LPROPS_FREEABLE:
2316             list = &c->freeable_list;
2317             break;
2318         case LPROPS_FRDI_IDX:
2319             list = &c->frdi_idx_list;
2320             break;
2321         }
2322         found = 0;
2323         switch (cat) {
2324         case LPROPS_DIRTY:
2325         case LPROPS_DIRTY_IDX:
2326         case LPROPS_FREE:
2327             heap = &c->lpt_heap[cat - 1];
2328             if (lprops->hpos < heap->cnt &&
2329                 heap->arr[lprops->hpos] == lprops)
2330                 found = 1;
2331             break;
2332         case LPROPS_UNCAT:
2333         case LPROPS_EMPTY:
2334         case LPROPS_FREEABLE:
2335         case LPROPS_FRDI_IDX:
2336             list_for_each_entry(lp, list, list)
2337                 if (lprops == lp) {
2338                     found = 1;
2339                     break;
2340                 }
2341             break;
2342         }
2343         if (!found) {
2344             ubifs_err(c, "LEB %d cat %d not found in cat heap/list",
2345                   lprops->lnum, cat);
2346             return -EINVAL;
2347         }
2348         switch (cat) {
2349         case LPROPS_EMPTY:
2350             if (lprops->free != c->leb_size) {
2351                 ubifs_err(c, "LEB %d cat %d free %d dirty %d",
2352                       lprops->lnum, cat, lprops->free,
2353                       lprops->dirty);
2354                 return -EINVAL;
2355             }
2356             break;
2357         case LPROPS_FREEABLE:
2358         case LPROPS_FRDI_IDX:
2359             if (lprops->free + lprops->dirty != c->leb_size) {
2360                 ubifs_err(c, "LEB %d cat %d free %d dirty %d",
2361                       lprops->lnum, cat, lprops->free,
2362                       lprops->dirty);
2363                 return -EINVAL;
2364             }
2365             break;
2366         }
2367     }
2368     return 0;
2369 }
2370
2371 /**
2372  * dbg_check_lpt_nodes - check nnodes and pnodes.
2373  * @c: the UBIFS file-system description object
2374  * @cnode: next cnode (nnode or pnode) to check
2375  * @row: row of cnode (root is zero)
2376  * @col: column of cnode (leftmost is zero)
2377  *
2378  * This function returns %0 on success and a negative error code on failure.
2379  */
2380 int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode,
2381             int row, int col)
2382 {
2383     struct ubifs_nnode *nnode, *nn;
2384     struct ubifs_cnode *cn;
2385     int num, iip = 0, err;
2386
2387     if (!dbg_is_chk_lprops(c))
2388         return 0;
2389
2390     while (cnode) {
2391         ubifs_assert(c, row >= 0);
2392         nnode = cnode->parent;
2393         if (cnode->level) {
2394             /* cnode is a nnode */
2395             num = calc_nnode_num(row, col);
2396             if (cnode->num != num) {
2397                 ubifs_err(c, "nnode num %d expected %d parent num %d iip %d",
2398                       cnode->num, num,
2399                       (nnode ? nnode->num : 0), cnode->iip);
2400                 return -EINVAL;
2401             }
2402             nn = (struct ubifs_nnode *)cnode;
2403             while (iip < UBIFS_LPT_FANOUT) {
2404                 cn = nn->nbranch[iip].cnode;
2405                 if (cn) {
2406                     /* Go down */
2407                     row += 1;
2408                     col <<= UBIFS_LPT_FANOUT_SHIFT;
2409                     col += iip;
2410                     iip = 0;
2411                     cnode = cn;
2412                     break;
2413                 }
2414                 /* Go right */
2415                 iip += 1;
2416             }
2417             if (iip < UBIFS_LPT_FANOUT)
2418                 continue;
2419         } else {
2420             struct ubifs_pnode *pnode;
2421
2422             /* cnode is a pnode */
2423             pnode = (struct ubifs_pnode *)cnode;
2424             err = dbg_chk_pnode(c, pnode, col);
2425             if (err)
2426                 return err;
2427         }
2428         /* Go up and to the right */
2429         row -= 1;
2430         col >>= UBIFS_LPT_FANOUT_SHIFT;
2431         iip = cnode->iip + 1;
2432         cnode = (struct ubifs_cnode *)nnode;
2433     }
2434     return 0;
2435 }