// SPDX-License-Identifier: GPL-2.0-only /* * This file is part of UBIFS. * * Copyright (C) 2006-2008 Nokia Corporation. * * Authors: Adrian Hunter * Artem Bityutskiy (Битюцкий Артём) */ /* * This file implements the LEB properties tree (LPT) area. The LPT area * contains the LEB properties tree, a table of LPT area eraseblocks (ltab), and * (for the "big" model) a table of saved LEB numbers (lsave). The LPT area sits * between the log and the orphan area. * * The LPT area is like a miniature self-contained file system. It is required * that it never runs out of space, is fast to access and update, and scales * logarithmically. The LEB properties tree is implemented as a wandering tree * much like the TNC, and the LPT area has its own garbage collection. * * The LPT has two slightly different forms called the "small model" and the * "big model". The small model is used when the entire LEB properties table * can be written into a single eraseblock. In that case, garbage collection * consists of just writing the whole table, which therefore makes all other * eraseblocks reusable. In the case of the big model, dirty eraseblocks are * selected for garbage collection, which consists of marking the clean nodes in * that LEB as dirty, and then only the dirty nodes are written out. Also, in * the case of the big model, a table of LEB numbers is saved so that the entire * LPT does not to be scanned looking for empty eraseblocks when UBIFS is first * mounted. */ #include "ubifs.h" #include <linux/crc16.h> #include <linux/math64.h> #include <linux/slab.h> /** * 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) { … } /** * ubifs_calc_lpt_geom - calculate and check sizes for the LPT area. * @c: the UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ int ubifs_calc_lpt_geom(struct ubifs_info *c) { … } /** * 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. */ static int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt) { … } /** * pack_bits - pack bit fields end-to-end. * @c: UBIFS file-system description object * @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(const struct ubifs_info *c, uint8_t **addr, int *pos, uint32_t val, int nrbits) { … } /** * ubifs_unpack_bits - unpack bit fields. * @c: UBIFS file-system description object * @addr: address at which to unpack (passed and next address returned) * @pos: bit position at which to unpack (passed and next position returned) * @nrbits: number of bits of value to unpack (1-32) * * This functions returns the value unpacked. */ uint32_t ubifs_unpack_bits(const struct ubifs_info *c, uint8_t **addr, int *pos, int nrbits) { … } /** * ubifs_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 */ void ubifs_pack_pnode(struct ubifs_info *c, void *buf, struct ubifs_pnode *pnode) { … } /** * ubifs_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 */ void ubifs_pack_nnode(struct ubifs_info *c, void *buf, struct ubifs_nnode *nnode) { … } /** * ubifs_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 */ void ubifs_pack_ltab(struct ubifs_info *c, void *buf, struct ubifs_lpt_lprops *ltab) { … } /** * ubifs_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 */ void ubifs_pack_lsave(struct ubifs_info *c, void *buf, int *lsave) { … } /** * ubifs_add_lpt_dirt - add dirty space to LPT LEB properties. * @c: UBIFS file-system description object * @lnum: LEB number to which to add dirty space * @dirty: amount of dirty space to add */ void ubifs_add_lpt_dirt(struct ubifs_info *c, int lnum, int dirty) { … } /** * 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) { … } /** * ubifs_add_nnode_dirt - add dirty space to LPT LEB properties. * @c: UBIFS file-system description object * @nnode: nnode for which to add dirt */ void ubifs_add_nnode_dirt(struct ubifs_info *c, struct ubifs_nnode *nnode) { … } /** * add_pnode_dirt - add dirty space to LPT LEB properties. * @c: UBIFS file-system description object * @pnode: pnode for which to add dirt */ static void add_pnode_dirt(struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * 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) { … } /** * calc_nnode_num_from_parent - calculate nnode number. * @c: UBIFS file-system description object * @parent: parent nnode * @iip: index in parent * * 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 based on the parent's * nnode number and the index in parent. */ static int calc_nnode_num_from_parent(const struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * calc_pnode_num_from_parent - calculate pnode number. * @c: UBIFS file-system description object * @parent: parent nnode * @iip: index in parent * * The pnode number is a number that uniquely identifies a pnode and can be used * easily to traverse the tree from the root to that pnode. * * This function calculates and returns the pnode number based on the parent's * nnode number and the index in parent. */ static int calc_pnode_num_from_parent(const struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * ubifs_create_dflt_lpt - create default LPT. * @c: UBIFS file-system description object * @main_lebs: number of main area LEBs is passed and returned here * @lpt_first: LEB number of first LPT LEB * @lpt_lebs: number of LEBs for LPT is passed and returned here * @big_lpt: use big LPT model is passed and returned here * @hash: hash of the LPT is returned here * * This function returns %0 on success and a negative error code on failure. */ int ubifs_create_dflt_lpt(struct ubifs_info *c, int *main_lebs, int lpt_first, int *lpt_lebs, int *big_lpt, u8 *hash) { … } /** * update_cats - add LEB properties of a pnode to LEB category lists and heaps. * @c: UBIFS file-system description object * @pnode: pnode * * When a pnode is loaded into memory, the LEB properties it contains are added, * by this function, to the LEB category lists and heaps. */ static void update_cats(struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * replace_cats - add LEB properties of a pnode to LEB category lists and heaps. * @c: UBIFS file-system description object * @old_pnode: pnode copied * @new_pnode: pnode copy * * During commit it is sometimes necessary to copy a pnode * (see dirty_cow_pnode). When that happens, references in * category lists and heaps must be replaced. This function does that. */ static void replace_cats(struct ubifs_info *c, struct ubifs_pnode *old_pnode, struct ubifs_pnode *new_pnode) { … } /** * check_lpt_crc - check LPT node crc is correct. * @c: UBIFS file-system description object * @buf: buffer containing node * @len: length of node * * This function returns %0 on success and a negative error code on failure. */ static int check_lpt_crc(const struct ubifs_info *c, void *buf, int len) { … } /** * check_lpt_type - check LPT node type is correct. * @c: UBIFS file-system description object * @addr: address of type bit field is passed and returned updated here * @pos: position of type bit field is passed and returned updated here * @type: expected type * * This function returns %0 on success and a negative error code on failure. */ static int check_lpt_type(const struct ubifs_info *c, uint8_t **addr, int *pos, int type) { … } /** * unpack_pnode - unpack a pnode. * @c: UBIFS file-system description object * @buf: buffer containing packed pnode to unpack * @pnode: pnode structure to fill * * This function returns %0 on success and a negative error code on failure. */ static int unpack_pnode(const struct ubifs_info *c, void *buf, struct ubifs_pnode *pnode) { … } /** * ubifs_unpack_nnode - unpack a nnode. * @c: UBIFS file-system description object * @buf: buffer containing packed nnode to unpack * @nnode: nnode structure to fill * * This function returns %0 on success and a negative error code on failure. */ int ubifs_unpack_nnode(const struct ubifs_info *c, void *buf, struct ubifs_nnode *nnode) { … } /** * unpack_ltab - unpack the LPT's own lprops table. * @c: UBIFS file-system description object * @buf: buffer from which to unpack * * This function returns %0 on success and a negative error code on failure. */ static int unpack_ltab(const struct ubifs_info *c, void *buf) { … } /** * unpack_lsave - unpack the LPT's save table. * @c: UBIFS file-system description object * @buf: buffer from which to unpack * * This function returns %0 on success and a negative error code on failure. */ static int unpack_lsave(const struct ubifs_info *c, void *buf) { … } /** * validate_nnode - validate a nnode. * @c: UBIFS file-system description object * @nnode: nnode to validate * @parent: parent nnode (or NULL for the root nnode) * @iip: index in parent * * This function returns %0 on success and a negative error code on failure. */ static int validate_nnode(const struct ubifs_info *c, struct ubifs_nnode *nnode, struct ubifs_nnode *parent, int iip) { … } /** * validate_pnode - validate a pnode. * @c: UBIFS file-system description object * @pnode: pnode to validate * @parent: parent nnode * @iip: index in parent * * This function returns %0 on success and a negative error code on failure. */ static int validate_pnode(const struct ubifs_info *c, struct ubifs_pnode *pnode, struct ubifs_nnode *parent, int iip) { … } /** * set_pnode_lnum - set LEB numbers on a pnode. * @c: UBIFS file-system description object * @pnode: pnode to update * * This function calculates the LEB numbers for the LEB properties it contains * based on the pnode number. */ static void set_pnode_lnum(const struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * ubifs_read_nnode - read a nnode from flash and link it to the tree in memory. * @c: UBIFS file-system description object * @parent: parent nnode (or NULL for the root) * @iip: index in parent * * This function returns %0 on success and a negative error code on failure. */ int ubifs_read_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * read_pnode - read a pnode from flash and link it to the tree in memory. * @c: UBIFS file-system description object * @parent: parent nnode * @iip: index in parent * * This function returns %0 on success and a negative error code on failure. */ static int read_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * read_ltab - read LPT's own lprops table. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ static int read_ltab(struct ubifs_info *c) { … } /** * read_lsave - read LPT's save table. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ static int read_lsave(struct ubifs_info *c) { … } /** * ubifs_get_nnode - get a nnode. * @c: UBIFS file-system description object * @parent: parent nnode (or NULL for the root) * @iip: index in parent * * This function returns a pointer to the nnode on success or a negative error * code on failure. */ struct ubifs_nnode *ubifs_get_nnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * ubifs_get_pnode - get a pnode. * @c: UBIFS file-system description object * @parent: parent nnode * @iip: index in parent * * This function returns a pointer to the pnode on success or a negative error * code on failure. */ struct ubifs_pnode *ubifs_get_pnode(struct ubifs_info *c, struct ubifs_nnode *parent, int iip) { … } /** * ubifs_pnode_lookup - lookup a pnode in the LPT. * @c: UBIFS file-system description object * @i: pnode number (0 to (main_lebs - 1) / UBIFS_LPT_FANOUT) * * This function returns a pointer to the pnode on success or a negative * error code on failure. */ struct ubifs_pnode *ubifs_pnode_lookup(struct ubifs_info *c, int i) { … } /** * ubifs_lpt_lookup - lookup LEB properties in the LPT. * @c: UBIFS file-system description object * @lnum: LEB number to lookup * * This function returns a pointer to the LEB properties on success or a * negative error code on failure. */ struct ubifs_lprops *ubifs_lpt_lookup(struct ubifs_info *c, int lnum) { … } /** * dirty_cow_nnode - ensure a nnode is not being committed. * @c: UBIFS file-system description object * @nnode: nnode to check * * Returns dirtied nnode on success or negative error code on failure. */ static struct ubifs_nnode *dirty_cow_nnode(struct ubifs_info *c, struct ubifs_nnode *nnode) { … } /** * dirty_cow_pnode - ensure a pnode is not being committed. * @c: UBIFS file-system description object * @pnode: pnode to check * * Returns dirtied pnode on success or negative error code on failure. */ static struct ubifs_pnode *dirty_cow_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * ubifs_lpt_lookup_dirty - lookup LEB properties in the LPT. * @c: UBIFS file-system description object * @lnum: LEB number to lookup * * This function returns a pointer to the LEB properties on success or a * negative error code on failure. */ struct ubifs_lprops *ubifs_lpt_lookup_dirty(struct ubifs_info *c, int lnum) { … } /** * ubifs_lpt_calc_hash - Calculate hash of the LPT pnodes * @c: UBIFS file-system description object * @hash: the returned hash of the LPT pnodes * * This function iterates over the LPT pnodes and creates a hash over them. * Returns 0 for success or a negative error code otherwise. */ int ubifs_lpt_calc_hash(struct ubifs_info *c, u8 *hash) { … } /** * lpt_check_hash - check the hash of the LPT. * @c: UBIFS file-system description object * * This function calculates a hash over all pnodes in the LPT and compares it with * the hash stored in the master node. Returns %0 on success and a negative error * code on failure. */ static int lpt_check_hash(struct ubifs_info *c) { … } /** * lpt_init_rd - initialize the LPT for reading. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ static int lpt_init_rd(struct ubifs_info *c) { … } /** * lpt_init_wr - initialize the LPT for writing. * @c: UBIFS file-system description object * * 'lpt_init_rd()' must have been called already. * * This function returns %0 on success and a negative error code on failure. */ static int lpt_init_wr(struct ubifs_info *c) { … } /** * ubifs_lpt_init - initialize the LPT. * @c: UBIFS file-system description object * @rd: whether to initialize lpt for reading * @wr: whether to initialize lpt for writing * * For mounting 'rw', @rd and @wr are both true. For mounting 'ro', @rd is true * and @wr is false. For mounting from 'ro' to 'rw', @rd is false and @wr is * true. * * This function returns %0 on success and a negative error code on failure. */ int ubifs_lpt_init(struct ubifs_info *c, int rd, int wr) { … } /** * struct lpt_scan_node - somewhere to put nodes while we scan LPT. * @nnode: where to keep a nnode * @pnode: where to keep a pnode * @cnode: where to keep a cnode * @in_tree: is the node in the tree in memory * @ptr: union of node pointers * @ptr.nnode: pointer to the nnode (if it is an nnode) which may be here or in * the tree * @ptr.pnode: ditto for pnode * @ptr.cnode: ditto for cnode */ struct lpt_scan_node { … }; /** * scan_get_nnode - for the scan, get a nnode from either the tree or flash. * @c: the UBIFS file-system description object * @path: where to put the nnode * @parent: parent of the nnode * @iip: index in parent of the nnode * * This function returns a pointer to the nnode on success or a negative error * code on failure. */ static struct ubifs_nnode *scan_get_nnode(struct ubifs_info *c, struct lpt_scan_node *path, struct ubifs_nnode *parent, int iip) { … } /** * scan_get_pnode - for the scan, get a pnode from either the tree or flash. * @c: the UBIFS file-system description object * @path: where to put the pnode * @parent: parent of the pnode * @iip: index in parent of the pnode * * This function returns a pointer to the pnode on success or a negative error * code on failure. */ static struct ubifs_pnode *scan_get_pnode(struct ubifs_info *c, struct lpt_scan_node *path, struct ubifs_nnode *parent, int iip) { … } /** * ubifs_lpt_scan_nolock - scan the LPT. * @c: the UBIFS file-system description object * @start_lnum: LEB number from which to start scanning * @end_lnum: LEB number at which to stop scanning * @scan_cb: callback function called for each lprops * @data: data to be passed to the callback function * * This function returns %0 on success and a negative error code on failure. */ int ubifs_lpt_scan_nolock(struct ubifs_info *c, int start_lnum, int end_lnum, ubifs_lpt_scan_callback scan_cb, void *data) { … } /** * dbg_chk_pnode - check a pnode. * @c: the UBIFS file-system description object * @pnode: pnode to check * @col: pnode column * * This function returns %0 on success and a negative error code on failure. */ static int dbg_chk_pnode(struct ubifs_info *c, struct ubifs_pnode *pnode, int col) { … } /** * dbg_check_lpt_nodes - check nnodes and pnodes. * @c: the UBIFS file-system description object * @cnode: next cnode (nnode or pnode) to check * @row: row of cnode (root is zero) * @col: column of cnode (leftmost is zero) * * This function returns %0 on success and a negative error code on failure. */ int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode, int row, int col) { … }
Codebase Browser
linux