/* * This file is part of UBIFS. * * Copyright (C) 2006, 2007 Nokia Corporation. * * This program is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 as published by * the Free Software Foundation. * * This program is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. * * You should have received a copy of the GNU General Public License along with * this program; if not, write to the Free Software Foundation, Inc., 51 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA * * Authors: Adrian Hunter * Artem Bityutskiy */ #include "mkfs.ubifs.h" #ifdef WITH_CRYPTO #include <openssl/evp.h> #endif /** * do_calc_lpt_geom - calculate sizes for the LPT area. * @c: the UBIFS file-system description object * * Calculate the sizes of LPT bit fields, nodes, and tree, based on the * properties of the flash and whether LPT is "big" (c->big_lpt). */ static void do_calc_lpt_geom(struct ubifs_info *c) { int n, bits, per_leb_wastage; long long sz, tot_wastage; c->pnode_cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; n = (c->pnode_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; c->nnode_cnt = n; while (n > 1) { n = (n + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; c->nnode_cnt += n; } c->lpt_hght = 1; n = UBIFS_LPT_FANOUT; while (n < c->pnode_cnt) { c->lpt_hght += 1; n <<= UBIFS_LPT_FANOUT_SHIFT; } c->space_bits = fls(c->leb_size) - 3; c->lpt_lnum_bits = fls(c->lpt_lebs); c->lpt_offs_bits = fls(c->leb_size - 1); c->lpt_spc_bits = fls(c->leb_size); n = (c->max_leb_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; c->pcnt_bits = fls(n - 1); c->lnum_bits = fls(c->max_leb_cnt - 1); bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + (c->big_lpt ? c->pcnt_bits : 0) + (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT; c->pnode_sz = (bits + 7) / 8; bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + (c->big_lpt ? c->pcnt_bits : 0) + (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT; c->nnode_sz = (bits + 7) / 8; bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + c->lpt_lebs * c->lpt_spc_bits * 2; c->ltab_sz = (bits + 7) / 8; bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS + c->lnum_bits * c->lsave_cnt; c->lsave_sz = (bits + 7) / 8; /* Calculate the minimum LPT size */ c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz; c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz; c->lpt_sz += c->ltab_sz; c->lpt_sz += c->lsave_sz; /* Add wastage */ sz = c->lpt_sz; per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz); sz += per_leb_wastage; tot_wastage = per_leb_wastage; while (sz > c->leb_size) { sz += per_leb_wastage; sz -= c->leb_size; tot_wastage += per_leb_wastage; } tot_wastage += ALIGN(sz, c->min_io_size) - sz; c->lpt_sz += tot_wastage; } /** * calc_dflt_lpt_geom - calculate default LPT geometry. * @c: the UBIFS file-system description object * @main_lebs: number of main area LEBs is passed and returned here * @big_lpt: whether the LPT area is "big" is returned here * * The size of the LPT area depends on parameters that themselves are dependent * on the size of the LPT area. This function, successively recalculates the LPT * area geometry until the parameters and resultant geometry are consistent. * * This function returns %0 on success and a negative error code on failure. */ int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt) { int i, lebs_needed; long long sz; /* Start by assuming the minimum number of LPT LEBs */ c->lpt_lebs = UBIFS_MIN_LPT_LEBS; c->main_lebs = *main_lebs - c->lpt_lebs; if (c->main_lebs <= 0) return -EINVAL; /* And assume we will use the small LPT model */ c->big_lpt = 0; /* * Calculate the geometry based on assumptions above and then see if it * makes sense */ do_calc_lpt_geom(c); /* Small LPT model must have lpt_sz < leb_size */ if (c->lpt_sz > c->leb_size) { /* Nope, so try again using big LPT model */ c->big_lpt = 1; do_calc_lpt_geom(c); } /* Now check there are enough LPT LEBs */ for (i = 0; i < 64 ; i++) { sz = c->lpt_sz * 4; /* Allow 4 times the size */ sz += c->leb_size - 1; do_div(sz, c->leb_size); lebs_needed = sz; if (lebs_needed > c->lpt_lebs) { /* Not enough LPT LEBs so try again with more */ c->lpt_lebs = lebs_needed; c->main_lebs = *main_lebs - c->lpt_lebs; if (c->main_lebs <= 0) return -EINVAL; do_calc_lpt_geom(c); continue; } if (c->ltab_sz > c->leb_size) { err_msg("LPT ltab too big"); return -EINVAL; } *main_lebs = c->main_lebs; *big_lpt = c->big_lpt; return 0; } return -EINVAL; } /** * pack_bits - pack bit fields end-to-end. * @addr: address at which to pack (passed and next address returned) * @pos: bit position at which to pack (passed and next position returned) * @val: value to pack * @nrbits: number of bits of value to pack (1-32) */ static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits) { uint8_t *p = *addr; int b = *pos; if (b) { *p |= ((uint8_t)val) << b; nrbits += b; if (nrbits > 8) { *++p = (uint8_t)(val >>= (8 - b)); if (nrbits > 16) { *++p = (uint8_t)(val >>= 8); if (nrbits > 24) { *++p = (uint8_t)(val >>= 8); if (nrbits > 32) *++p = (uint8_t)(val >>= 8); } } } } else { *p = (uint8_t)val; if (nrbits > 8) { *++p = (uint8_t)(val >>= 8); if (nrbits > 16) { *++p = (uint8_t)(val >>= 8); if (nrbits > 24) *++p = (uint8_t)(val >>= 8); } } } b = nrbits & 7; if (b == 0) p++; *addr = p; *pos = b; } /** * pack_pnode - pack all the bit fields of a pnode. * @c: UBIFS file-system description object * @buf: buffer into which to pack * @pnode: pnode to pack */ static void pack_pnode(struct ubifs_info *c, void *buf, struct ubifs_pnode *pnode) { uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; int i, pos = 0; uint16_t crc; pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS); if (c->big_lpt) pack_bits(&addr, &pos, pnode->num, c->pcnt_bits); for (i = 0; i < UBIFS_LPT_FANOUT; i++) { pack_bits(&addr, &pos, pnode->lprops[i].free >> 3, c->space_bits); pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3, c->space_bits); if (pnode->lprops[i].flags & LPROPS_INDEX) pack_bits(&addr, &pos, 1, 1); else pack_bits(&addr, &pos, 0, 1); } crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, c->pnode_sz - UBIFS_LPT_CRC_BYTES); addr = buf; pos = 0; pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); } /** * pack_nnode - pack all the bit fields of a nnode. * @c: UBIFS file-system description object * @buf: buffer into which to pack * @nnode: nnode to pack */ static void pack_nnode(struct ubifs_info *c, void *buf, struct ubifs_nnode *nnode) { uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; int i, pos = 0; uint16_t crc; pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS); if (c->big_lpt) pack_bits(&addr, &pos, nnode->num, c->pcnt_bits); for (i = 0; i < UBIFS_LPT_FANOUT; i++) { int lnum = nnode->nbranch[i].lnum; if (lnum == 0) lnum = c->lpt_last + 1; pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits); pack_bits(&addr, &pos, nnode->nbranch[i].offs, c->lpt_offs_bits); } crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, c->nnode_sz - UBIFS_LPT_CRC_BYTES); addr = buf; pos = 0; pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); } /** * pack_ltab - pack the LPT's own lprops table. * @c: UBIFS file-system description object * @buf: buffer into which to pack * @ltab: LPT's own lprops table to pack */ static void pack_ltab(struct ubifs_info *c, void *buf, struct ubifs_lpt_lprops *ltab) { uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; int i, pos = 0; uint16_t crc; pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS); for (i = 0; i < c->lpt_lebs; i++) { pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits); pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits); } crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, c->ltab_sz - UBIFS_LPT_CRC_BYTES); addr = buf; pos = 0; pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); } /** * pack_lsave - pack the LPT's save table. * @c: UBIFS file-system description object * @buf: buffer into which to pack * @lsave: LPT's save table to pack */ static void pack_lsave(struct ubifs_info *c, void *buf, int *lsave) { uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES; int i, pos = 0; uint16_t crc; pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS); for (i = 0; i < c->lsave_cnt; i++) pack_bits(&addr, &pos, lsave[i], c->lnum_bits); crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES, c->lsave_sz - UBIFS_LPT_CRC_BYTES); addr = buf; pos = 0; pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS); } /** * set_ltab - set LPT LEB properties. * @c: UBIFS file-system description object * @lnum: LEB number * @free: amount of free space * @dirty: amount of dirty space */ static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty) { dbg_msg(3, "LEB %d free %d dirty %d to %d %d", lnum, c->ltab[lnum - c->lpt_first].free, c->ltab[lnum - c->lpt_first].dirty, free, dirty); c->ltab[lnum - c->lpt_first].free = free; c->ltab[lnum - c->lpt_first].dirty = dirty; } /** * calc_nnode_num - calculate nnode number. * @row: the row in the tree (root is zero) * @col: the column in the row (leftmost is zero) * * The nnode number is a number that uniquely identifies a nnode and can be used * easily to traverse the tree from the root to that nnode. * * This function calculates and returns the nnode number for the nnode at @row * and @col. */ static int calc_nnode_num(int row, int col) { int num, bits; num = 1; while (row--) { bits = (col & (UBIFS_LPT_FANOUT - 1)); col >>= UBIFS_LPT_FANOUT_SHIFT; num <<= UBIFS_LPT_FANOUT_SHIFT; num |= bits; } return num; } /** * create_lpt - create LPT. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ int create_lpt(struct ubifs_info *c) { int lnum, err = 0, i, j, cnt, len, alen, row; int blnum, boffs, bsz, bcnt; struct ubifs_pnode *pnode = NULL; struct ubifs_nnode *nnode = NULL; void *buf = NULL, *p; int *lsave = NULL; unsigned int md_len; pnode = malloc(sizeof(struct ubifs_pnode)); nnode = malloc(sizeof(struct ubifs_nnode)); buf = malloc(c->leb_size); lsave = malloc(sizeof(int) * c->lsave_cnt); if (!pnode || !nnode || !buf || !lsave) { err = -ENOMEM; goto out; } memset(pnode, 0 , sizeof(struct ubifs_pnode)); memset(nnode, 0 , sizeof(struct ubifs_nnode)); hash_digest_init(); c->lscan_lnum = c->main_first; lnum = c->lpt_first; p = buf; len = 0; /* Number of leaf nodes (pnodes) */ cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) >> UBIFS_LPT_FANOUT_SHIFT; //printf("pnode_cnt=%d\n",cnt); /* * To calculate the internal node branches, we keep information about * the level below. */ blnum = lnum; /* LEB number of level below */ boffs = 0; /* Offset of level below */ bcnt = cnt; /* Number of nodes in level below */ bsz = c->pnode_sz; /* Size of nodes in level below */ /* Add pnodes */ for (i = 0; i < cnt; i++) { if (len + c->pnode_sz > c->leb_size) { alen = ALIGN(len, c->min_io_size); set_ltab(c, lnum, c->leb_size - alen, alen - len); memset(p, 0xff, alen - len); err = write_leb(lnum++, alen, buf); if (err) goto out; p = buf; len = 0; } /* Fill in the pnode */ for (j = 0; j < UBIFS_LPT_FANOUT; j++) { int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j; if (k < c->main_lebs) pnode->lprops[j] = c->lpt[k]; else { pnode->lprops[j].free = c->leb_size; pnode->lprops[j].dirty = 0; pnode->lprops[j].flags = 0; } } pack_pnode(c, p, pnode); hash_digest_update(p, c->pnode_sz); p += c->pnode_sz; len += c->pnode_sz; /* * pnodes are simply numbered left to right starting at zero, * which means the pnode number can be used easily to traverse * down the tree to the corresponding pnode. */ pnode->num += 1; } hash_digest_final(c->lpt_hash, &md_len); row = c->lpt_hght - 1; /* Add all nnodes, one level at a time */ while (1) { /* Number of internal nodes (nnodes) at next level */ cnt = (cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT; if (cnt == 0) cnt = 1; for (i = 0; i < cnt; i++) { if (len + c->nnode_sz > c->leb_size) { alen = ALIGN(len, c->min_io_size); set_ltab(c, lnum, c->leb_size - alen, alen - len); memset(p, 0xff, alen - len); err = write_leb(lnum++, alen, buf); if (err) goto out; p = buf; len = 0; } /* The root is on row zero */ if (row == 0) { c->lpt_lnum = lnum; c->lpt_offs = len; } /* Set branches to the level below */ for (j = 0; j < UBIFS_LPT_FANOUT; j++) { if (bcnt) { if (boffs + bsz > c->leb_size) { blnum += 1; boffs = 0; } nnode->nbranch[j].lnum = blnum; nnode->nbranch[j].offs = boffs; boffs += bsz; bcnt--; } else { nnode->nbranch[j].lnum = 0; nnode->nbranch[j].offs = 0; } } nnode->num = calc_nnode_num(row, i); pack_nnode(c, p, nnode); p += c->nnode_sz; len += c->nnode_sz; } /* Row zero is the top row */ if (row == 0) break; /* Update the information about the level below */ bcnt = cnt; bsz = c->nnode_sz; row -= 1; } if (c->big_lpt) { /* Need to add LPT's save table */ if (len + c->lsave_sz > c->leb_size) { alen = ALIGN(len, c->min_io_size); set_ltab(c, lnum, c->leb_size - alen, alen - len); memset(p, 0xff, alen - len); err = write_leb(lnum++, alen, buf); if (err) goto out; p = buf; len = 0; } c->lsave_lnum = lnum; c->lsave_offs = len; for (i = 0; i < c->lsave_cnt; i++) lsave[i] = c->main_first + i; pack_lsave(c, p, lsave); p += c->lsave_sz; len += c->lsave_sz; } /* Need to add LPT's own LEB properties table */ if (len + c->ltab_sz > c->leb_size) { alen = ALIGN(len, c->min_io_size); set_ltab(c, lnum, c->leb_size - alen, alen - len); memset(p, 0xff, alen - len); err = write_leb(lnum++, alen, buf); if (err) goto out; p = buf; len = 0; } c->ltab_lnum = lnum; c->ltab_offs = len; /* Update ltab before packing it */ len += c->ltab_sz; alen = ALIGN(len, c->min_io_size); set_ltab(c, lnum, c->leb_size - alen, alen - len); pack_ltab(c, p, c->ltab); p += c->ltab_sz; /* Write remaining buffer */ memset(p, 0xff, alen - len); err = write_leb(lnum, alen, buf); if (err) goto out; c->nhead_lnum = lnum; c->nhead_offs = ALIGN(len, c->min_io_size); dbg_msg(1, "lpt_sz: %lld", c->lpt_sz); dbg_msg(1, "space_bits: %d", c->space_bits); dbg_msg(1, "lpt_lnum_bits: %d", c->lpt_lnum_bits); dbg_msg(1, "lpt_offs_bits: %d", c->lpt_offs_bits); dbg_msg(1, "lpt_spc_bits: %d", c->lpt_spc_bits); dbg_msg(1, "pcnt_bits: %d", c->pcnt_bits); dbg_msg(1, "lnum_bits: %d", c->lnum_bits); dbg_msg(1, "pnode_sz: %d", c->pnode_sz); dbg_msg(1, "nnode_sz: %d", c->nnode_sz); dbg_msg(1, "ltab_sz: %d", c->ltab_sz); dbg_msg(1, "lsave_sz: %d", c->lsave_sz); dbg_msg(1, "lsave_cnt: %d", c->lsave_cnt); dbg_msg(1, "lpt_hght: %d", c->lpt_hght); dbg_msg(1, "big_lpt: %d", c->big_lpt); dbg_msg(1, "LPT root is at %d:%d", c->lpt_lnum, c->lpt_offs); dbg_msg(1, "LPT head is at %d:%d", c->nhead_lnum, c->nhead_offs); dbg_msg(1, "LPT ltab is at %d:%d", c->ltab_lnum, c->ltab_offs); if (c->big_lpt) dbg_msg(1, "LPT lsave is at %d:%d", c->lsave_lnum, c->lsave_offs); out: free(lsave); free(buf); free(nnode); free(pnode); return err; }