// 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 commit-related functionality of the LEB properties * subsystem. */ #include <linux/crc16.h> #include <linux/slab.h> #include <linux/random.h> #include "ubifs.h" static int dbg_populate_lsave(struct ubifs_info *c); /** * first_dirty_cnode - find first dirty cnode. * @c: UBIFS file-system description object * @nnode: nnode at which to start * * This function returns the first dirty cnode or %NULL if there is not one. */ static struct ubifs_cnode *first_dirty_cnode(const struct ubifs_info *c, struct ubifs_nnode *nnode) { … } /** * next_dirty_cnode - find next dirty cnode. * @c: UBIFS file-system description object * @cnode: cnode from which to begin searching * * This function returns the next dirty cnode or %NULL if there is not one. */ static struct ubifs_cnode *next_dirty_cnode(const struct ubifs_info *c, struct ubifs_cnode *cnode) { … } /** * get_cnodes_to_commit - create list of dirty cnodes to commit. * @c: UBIFS file-system description object * * This function returns the number of cnodes to commit. */ static int get_cnodes_to_commit(struct ubifs_info *c) { … } /** * upd_ltab - update LPT LEB properties. * @c: UBIFS file-system description object * @lnum: LEB number * @free: amount of free space * @dirty: amount of dirty space to add */ static void upd_ltab(struct ubifs_info *c, int lnum, int free, int dirty) { … } /** * alloc_lpt_leb - allocate an LPT LEB that is empty. * @c: UBIFS file-system description object * @lnum: LEB number is passed and returned here * * This function finds the next empty LEB in the ltab starting from @lnum. If a * an empty LEB is found it is returned in @lnum and the function returns %0. * Otherwise the function returns -ENOSPC. Note however, that LPT is designed * never to run out of space. */ static int alloc_lpt_leb(struct ubifs_info *c, int *lnum) { … } /** * layout_cnodes - layout cnodes for commit. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ static int layout_cnodes(struct ubifs_info *c) { … } /** * realloc_lpt_leb - allocate an LPT LEB that is empty. * @c: UBIFS file-system description object * @lnum: LEB number is passed and returned here * * This function duplicates exactly the results of the function alloc_lpt_leb. * It is used during end commit to reallocate the same LEB numbers that were * allocated by alloc_lpt_leb during start commit. * * This function finds the next LEB that was allocated by the alloc_lpt_leb * function starting from @lnum. If a LEB is found it is returned in @lnum and * the function returns %0. Otherwise the function returns -ENOSPC. * Note however, that LPT is designed never to run out of space. */ static int realloc_lpt_leb(struct ubifs_info *c, int *lnum) { … } /** * write_cnodes - write cnodes for commit. * @c: UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ static int write_cnodes(struct ubifs_info *c) { … } /** * next_pnode_to_dirty - find next pnode to dirty. * @c: UBIFS file-system description object * @pnode: pnode * * This function returns the next pnode to dirty or %NULL if there are no more * pnodes. Note that pnodes that have never been written (lnum == 0) are * skipped. */ static struct ubifs_pnode *next_pnode_to_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * 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) { … } /** * do_make_pnode_dirty - mark a pnode dirty. * @c: UBIFS file-system description object * @pnode: pnode to mark dirty */ static void do_make_pnode_dirty(struct ubifs_info *c, struct ubifs_pnode *pnode) { … } /** * make_tree_dirty - mark the entire LEB properties tree dirty. * @c: UBIFS file-system description object * * This function is used by the "small" LPT model to cause the entire LEB * properties tree to be written. The "small" LPT model does not use LPT * garbage collection because it is more efficient to write the entire tree * (because it is small). * * This function returns %0 on success and a negative error code on failure. */ static int make_tree_dirty(struct ubifs_info *c) { … } /** * need_write_all - determine if the LPT area is running out of free space. * @c: UBIFS file-system description object * * This function returns %1 if the LPT area is running out of free space and %0 * if it is not. */ static int need_write_all(struct ubifs_info *c) { … } /** * lpt_tgc_start - start trivial garbage collection of LPT LEBs. * @c: UBIFS file-system description object * * LPT trivial garbage collection is where a LPT LEB contains only dirty and * free space and so may be reused as soon as the next commit is completed. * This function is called during start commit to mark LPT LEBs for trivial GC. */ static void lpt_tgc_start(struct ubifs_info *c) { … } /** * lpt_tgc_end - end trivial garbage collection of LPT LEBs. * @c: UBIFS file-system description object * * LPT trivial garbage collection is where a LPT LEB contains only dirty and * free space and so may be reused as soon as the next commit is completed. * This function is called after the commit is completed (master node has been * written) and un-maps LPT LEBs that were marked for trivial GC. */ static int lpt_tgc_end(struct ubifs_info *c) { … } /** * populate_lsave - fill the lsave array with important LEB numbers. * @c: the UBIFS file-system description object * * This function is only called for the "big" model. It records a small number * of LEB numbers of important LEBs. Important LEBs are ones that are (from * most important to least important): empty, freeable, freeable index, dirty * index, dirty or free. Upon mount, we read this list of LEB numbers and bring * their pnodes into memory. That will stop us from having to scan the LPT * straight away. For the "small" model we assume that scanning the LPT is no * big deal. */ static void populate_lsave(struct ubifs_info *c) { … } /** * nnode_lookup - lookup a nnode in the LPT. * @c: UBIFS file-system description object * @i: nnode number * * This function returns a pointer to the nnode on success or a negative * error code on failure. */ static struct ubifs_nnode *nnode_lookup(struct ubifs_info *c, int i) { … } /** * make_nnode_dirty - find a nnode and, if found, make it dirty. * @c: UBIFS file-system description object * @node_num: nnode number of nnode to make dirty * @lnum: LEB number where nnode was written * @offs: offset where nnode was written * * This function is used by LPT garbage collection. LPT garbage collection is * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection * simply involves marking all the nodes in the LEB being garbage-collected as * dirty. The dirty nodes are written next commit, after which the LEB is free * to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int make_nnode_dirty(struct ubifs_info *c, int node_num, int lnum, int offs) { … } /** * make_pnode_dirty - find a pnode and, if found, make it dirty. * @c: UBIFS file-system description object * @node_num: pnode number of pnode to make dirty * @lnum: LEB number where pnode was written * @offs: offset where pnode was written * * This function is used by LPT garbage collection. LPT garbage collection is * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection * simply involves marking all the nodes in the LEB being garbage-collected as * dirty. The dirty nodes are written next commit, after which the LEB is free * to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int make_pnode_dirty(struct ubifs_info *c, int node_num, int lnum, int offs) { … } /** * make_ltab_dirty - make ltab node dirty. * @c: UBIFS file-system description object * @lnum: LEB number where ltab was written * @offs: offset where ltab was written * * This function is used by LPT garbage collection. LPT garbage collection is * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection * simply involves marking all the nodes in the LEB being garbage-collected as * dirty. The dirty nodes are written next commit, after which the LEB is free * to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int make_ltab_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * make_lsave_dirty - make lsave node dirty. * @c: UBIFS file-system description object * @lnum: LEB number where lsave was written * @offs: offset where lsave was written * * This function is used by LPT garbage collection. LPT garbage collection is * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection * simply involves marking all the nodes in the LEB being garbage-collected as * dirty. The dirty nodes are written next commit, after which the LEB is free * to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int make_lsave_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * make_node_dirty - make node dirty. * @c: UBIFS file-system description object * @node_type: LPT node type * @node_num: node number * @lnum: LEB number where node was written * @offs: offset where node was written * * This function is used by LPT garbage collection. LPT garbage collection is * used only for the "big" LPT model (c->big_lpt == 1). Garbage collection * simply involves marking all the nodes in the LEB being garbage-collected as * dirty. The dirty nodes are written next commit, after which the LEB is free * to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int make_node_dirty(struct ubifs_info *c, int node_type, int node_num, int lnum, int offs) { … } /** * get_lpt_node_len - return the length of a node based on its type. * @c: UBIFS file-system description object * @node_type: LPT node type */ static int get_lpt_node_len(const struct ubifs_info *c, int node_type) { … } /** * get_pad_len - return the length of padding in a buffer. * @c: UBIFS file-system description object * @buf: buffer * @len: length of buffer */ static int get_pad_len(const struct ubifs_info *c, uint8_t *buf, int len) { … } /** * get_lpt_node_type - return type (and node number) of a node in a buffer. * @c: UBIFS file-system description object * @buf: buffer * @node_num: node number is returned here */ static int get_lpt_node_type(const struct ubifs_info *c, uint8_t *buf, int *node_num) { … } /** * is_a_node - determine if a buffer contains a node. * @c: UBIFS file-system description object * @buf: buffer * @len: length of buffer * * This function returns %1 if the buffer contains a node or %0 if it does not. */ static int is_a_node(const struct ubifs_info *c, uint8_t *buf, int len) { … } /** * lpt_gc_lnum - garbage collect a LPT LEB. * @c: UBIFS file-system description object * @lnum: LEB number to garbage collect * * LPT garbage collection is used only for the "big" LPT model * (c->big_lpt == 1). Garbage collection simply involves marking all the nodes * in the LEB being garbage-collected as dirty. The dirty nodes are written * next commit, after which the LEB is free to be reused. * * This function returns %0 on success and a negative error code on failure. */ static int lpt_gc_lnum(struct ubifs_info *c, int lnum) { … } /** * lpt_gc - LPT garbage collection. * @c: UBIFS file-system description object * * Select a LPT LEB for LPT garbage collection and call 'lpt_gc_lnum()'. * Returns %0 on success and a negative error code on failure. */ static int lpt_gc(struct ubifs_info *c) { … } /** * ubifs_lpt_start_commit - UBIFS commit starts. * @c: the UBIFS file-system description object * * This function has to be called when UBIFS starts the commit operation. * This function "freezes" all currently dirty LEB properties and does not * change them anymore. Further changes are saved and tracked separately * because they are not part of this commit. This function returns zero in case * of success and a negative error code in case of failure. */ int ubifs_lpt_start_commit(struct ubifs_info *c) { … } /** * free_obsolete_cnodes - free obsolete cnodes for commit end. * @c: UBIFS file-system description object */ static void free_obsolete_cnodes(struct ubifs_info *c) { … } /** * ubifs_lpt_end_commit - finish the commit operation. * @c: the UBIFS file-system description object * * This function has to be called when the commit operation finishes. It * flushes the changes which were "frozen" by 'ubifs_lprops_start_commit()' to * the media. Returns zero in case of success and a negative error code in case * of failure. */ int ubifs_lpt_end_commit(struct ubifs_info *c) { … } /** * ubifs_lpt_post_commit - post commit LPT trivial GC and LPT GC. * @c: UBIFS file-system description object * * LPT trivial GC is completed after a commit. Also LPT GC is done after a * commit for the "big" LPT model. */ int ubifs_lpt_post_commit(struct ubifs_info *c) { … } /** * first_nnode - find the first nnode in memory. * @c: UBIFS file-system description object * @hght: height of tree where nnode found is returned here * * This function returns a pointer to the nnode found or %NULL if no nnode is * found. This function is a helper to 'ubifs_lpt_free()'. */ static struct ubifs_nnode *first_nnode(struct ubifs_info *c, int *hght) { … } /** * next_nnode - find the next nnode in memory. * @c: UBIFS file-system description object * @nnode: nnode from which to start. * @hght: height of tree where nnode is, is passed and returned here * * This function returns a pointer to the nnode found or %NULL if no nnode is * found. This function is a helper to 'ubifs_lpt_free()'. */ static struct ubifs_nnode *next_nnode(struct ubifs_info *c, struct ubifs_nnode *nnode, int *hght) { … } /** * ubifs_lpt_free - free resources owned by the LPT. * @c: UBIFS file-system description object * @wr_only: free only resources used for writing */ void ubifs_lpt_free(struct ubifs_info *c, int wr_only) { … } /* * Everything below is related to debugging. */ /** * dbg_is_all_ff - determine if a buffer contains only 0xFF bytes. * @buf: buffer * @len: buffer length */ static int dbg_is_all_ff(uint8_t *buf, int len) { … } /** * dbg_is_nnode_dirty - determine if a nnode is dirty. * @c: the UBIFS file-system description object * @lnum: LEB number where nnode was written * @offs: offset where nnode was written */ static int dbg_is_nnode_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * dbg_is_pnode_dirty - determine if a pnode is dirty. * @c: the UBIFS file-system description object * @lnum: LEB number where pnode was written * @offs: offset where pnode was written */ static int dbg_is_pnode_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * dbg_is_ltab_dirty - determine if a ltab node is dirty. * @c: the UBIFS file-system description object * @lnum: LEB number where ltab node was written * @offs: offset where ltab node was written */ static int dbg_is_ltab_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * dbg_is_lsave_dirty - determine if a lsave node is dirty. * @c: the UBIFS file-system description object * @lnum: LEB number where lsave node was written * @offs: offset where lsave node was written */ static int dbg_is_lsave_dirty(struct ubifs_info *c, int lnum, int offs) { … } /** * dbg_is_node_dirty - determine if a node is dirty. * @c: the UBIFS file-system description object * @node_type: node type * @lnum: LEB number where node was written * @offs: offset where node was written */ static int dbg_is_node_dirty(struct ubifs_info *c, int node_type, int lnum, int offs) { … } /** * dbg_check_ltab_lnum - check the ltab for a LPT LEB number. * @c: the UBIFS file-system description object * @lnum: LEB number where node was written * * This function returns %0 on success and a negative error code on failure. */ static int dbg_check_ltab_lnum(struct ubifs_info *c, int lnum) { … } /** * dbg_check_ltab - check the free and dirty space in the ltab. * @c: the UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ int dbg_check_ltab(struct ubifs_info *c) { … } /** * dbg_chk_lpt_free_spc - check LPT free space is enough to write entire LPT. * @c: the UBIFS file-system description object * * This function returns %0 on success and a negative error code on failure. */ int dbg_chk_lpt_free_spc(struct ubifs_info *c) { … } /** * dbg_chk_lpt_sz - check LPT does not write more than LPT size. * @c: the UBIFS file-system description object * @action: what to do * @len: length written * * This function returns %0 on success and a negative error code on failure. * The @action argument may be one of: * o %0 - LPT debugging checking starts, initialize debugging variables; * o %1 - wrote an LPT node, increase LPT size by @len bytes; * o %2 - switched to a different LEB and wasted @len bytes; * o %3 - check that we've written the right number of bytes. * o %4 - wasted @len bytes; */ int dbg_chk_lpt_sz(struct ubifs_info *c, int action, int len) { … } /** * dump_lpt_leb - dump an LPT LEB. * @c: UBIFS file-system description object * @lnum: LEB number to dump * * This function dumps an LEB from LPT area. Nodes in this area are very * different to nodes in the main area (e.g., they do not have common headers, * they do not have 8-byte alignments, etc), so we have a separate function to * dump LPT area LEBs. Note, LPT has to be locked by the caller. */ static void dump_lpt_leb(const struct ubifs_info *c, int lnum) { … } /** * ubifs_dump_lpt_lebs - dump LPT lebs. * @c: UBIFS file-system description object * * This function dumps all LPT LEBs. The caller has to make sure the LPT is * locked. */ void ubifs_dump_lpt_lebs(const struct ubifs_info *c) { … } /** * dbg_populate_lsave - debugging version of 'populate_lsave()' * @c: UBIFS file-system description object * * This is a debugging version for 'populate_lsave()' which populates lsave * with random LEBs instead of useful LEBs, which is good for test coverage. * Returns zero if lsave has not been populated (this debugging feature is * disabled) an non-zero if lsave has been populated. */ static int dbg_populate_lsave(struct ubifs_info *c) { … }
Codebase Browser
linux