// 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 TNC (Tree Node Cache) which caches indexing nodes of * the UBIFS B-tree. * * At the moment the locking rules of the TNC tree are quite simple and * straightforward. We just have a mutex and lock it when we traverse the * tree. If a znode is not in memory, we read it from flash while still having * the mutex locked. */ #include <linux/crc32.h> #include <linux/slab.h> #include "ubifs.h" static int try_read_node(const struct ubifs_info *c, void *buf, int type, struct ubifs_zbranch *zbr); static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_zbranch *zbr, void *node); /* * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions. * @NAME_LESS: name corresponding to the first argument is less than second * @NAME_MATCHES: names match * @NAME_GREATER: name corresponding to the second argument is greater than * first * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media * * These constants were introduce to improve readability. */ enum { … }; static void do_insert_old_idx(struct ubifs_info *c, struct ubifs_old_idx *old_idx) { … } /** * insert_old_idx - record an index node obsoleted since the last commit start. * @c: UBIFS file-system description object * @lnum: LEB number of obsoleted index node * @offs: offset of obsoleted index node * * Returns %0 on success, and a negative error code on failure. * * For recovery, there must always be a complete intact version of the index on * flash at all times. That is called the "old index". It is the index as at the * time of the last successful commit. Many of the index nodes in the old index * may be dirty, but they must not be erased until the next successful commit * (at which point that index becomes the old index). * * That means that the garbage collection and the in-the-gaps method of * committing must be able to determine if an index node is in the old index. * Most of the old index nodes can be found by looking up the TNC using the * 'lookup_znode()' function. However, some of the old index nodes may have * been deleted from the current index or may have been changed so much that * they cannot be easily found. In those cases, an entry is added to an RB-tree. * That is what this function does. The RB-tree is ordered by LEB number and * offset because they uniquely identify the old index node. */ static int insert_old_idx(struct ubifs_info *c, int lnum, int offs) { … } /** * insert_old_idx_znode - record a znode obsoleted since last commit start. * @c: UBIFS file-system description object * @znode: znode of obsoleted index node * * Returns %0 on success, and a negative error code on failure. */ int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * ins_clr_old_idx_znode - record a znode obsoleted since last commit start. * @c: UBIFS file-system description object * @znode: znode of obsoleted index node * * Returns %0 on success, and a negative error code on failure. */ static int ins_clr_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * destroy_old_idx - destroy the old_idx RB-tree. * @c: UBIFS file-system description object * * During start commit, the old_idx RB-tree is used to avoid overwriting index * nodes that were in the index last commit but have since been deleted. This * is necessary for recovery i.e. the old index must be kept intact until the * new index is successfully written. The old-idx RB-tree is used for the * in-the-gaps method of writing index nodes and is destroyed every commit. */ void destroy_old_idx(struct ubifs_info *c) { … } /** * copy_znode - copy a dirty znode. * @c: UBIFS file-system description object * @znode: znode to copy * * A dirty znode being committed may not be changed, so it is copied. */ static struct ubifs_znode *copy_znode(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * add_idx_dirt - add dirt due to a dirty znode. * @c: UBIFS file-system description object * @lnum: LEB number of index node * @dirt: size of index node * * This function updates lprops dirty space and the new size of the index. */ static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt) { … } /** * replace_znode - replace old znode with new znode. * @c: UBIFS file-system description object * @new_zn: new znode * @old_zn: old znode * @zbr: the branch of parent znode * * Replace old znode with new znode in TNC. */ static void replace_znode(struct ubifs_info *c, struct ubifs_znode *new_zn, struct ubifs_znode *old_zn, struct ubifs_zbranch *zbr) { … } /** * dirty_cow_znode - ensure a znode is not being committed. * @c: UBIFS file-system description object * @zbr: branch of znode to check * * Returns dirtied znode on success or negative error code on failure. */ static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c, struct ubifs_zbranch *zbr) { … } /** * lnc_add - add a leaf node to the leaf node cache. * @c: UBIFS file-system description object * @zbr: zbranch of leaf node * @node: leaf node * * Leaf nodes are non-index nodes directory entry nodes or data nodes. The * purpose of the leaf node cache is to save re-reading the same leaf node over * and over again. Most things are cached by VFS, however the file system must * cache directory entries for readdir and for resolving hash collisions. The * present implementation of the leaf node cache is extremely simple, and * allows for error returns that are not used but that may be needed if a more * complex implementation is created. * * Note, this function does not add the @node object to LNC directly, but * allocates a copy of the object and adds the copy to LNC. The reason for this * is that @node has been allocated outside of the TNC subsystem and will be * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC * may be changed at any time, e.g. freed by the shrinker. */ static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr, const void *node) { … } /** * lnc_add_directly - add a leaf node to the leaf-node-cache. * @c: UBIFS file-system description object * @zbr: zbranch of leaf node * @node: leaf node * * This function is similar to 'lnc_add()', but it does not create a copy of * @node but inserts @node to TNC directly. */ static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr, void *node) { … } /** * lnc_free - remove a leaf node from the leaf node cache. * @zbr: zbranch of leaf node */ static void lnc_free(struct ubifs_zbranch *zbr) { … } /** * tnc_read_hashed_node - read a "hashed" leaf node. * @c: UBIFS file-system description object * @zbr: key and position of the node * @node: node is returned here * * This function reads a "hashed" node defined by @zbr from the leaf node cache * (in it is there) or from the hash media, in which case the node is also * added to LNC. Returns zero in case of success or a negative error * code in case of failure. */ static int tnc_read_hashed_node(struct ubifs_info *c, struct ubifs_zbranch *zbr, void *node) { … } /** * try_read_node - read a node if it is a node. * @c: UBIFS file-system description object * @buf: buffer to read to * @type: node type * @zbr: the zbranch describing the node to read * * This function tries to read a node of known type and length, checks it and * stores it in @buf. This function returns %1 if a node is present and %0 if * a node is not present. A negative error code is returned for I/O errors. * This function performs that same function as ubifs_read_node except that * it does not require that there is actually a node present and instead * the return code indicates if a node was read. * * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc * is true (it is controlled by corresponding mount option). However, if * @c->mounting or @c->remounting_rw is true (we are mounting or re-mounting to * R/W mode), @c->no_chk_data_crc is ignored and CRC is checked. This is * because during mounting or re-mounting from R/O mode to R/W mode we may read * journal nodes (when replying the journal or doing the recovery) and the * journal nodes may potentially be corrupted, so checking is required. */ static int try_read_node(const struct ubifs_info *c, void *buf, int type, struct ubifs_zbranch *zbr) { … } /** * fallible_read_node - try to read a leaf node. * @c: UBIFS file-system description object * @key: key of node to read * @zbr: position of node * @node: node returned * * This function tries to read a node and returns %1 if the node is read, %0 * if the node is not present, and a negative error code in the case of error. */ static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_zbranch *zbr, void *node) { … } /** * matches_name - determine if a direntry or xattr entry matches a given name. * @c: UBIFS file-system description object * @zbr: zbranch of dent * @nm: name to match * * This function checks if xentry/direntry referred by zbranch @zbr matches name * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case * of failure, a negative error code is returned. */ static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr, const struct fscrypt_name *nm) { … } /** * get_znode - get a TNC znode that may not be loaded yet. * @c: UBIFS file-system description object * @znode: parent znode * @n: znode branch slot number * * This function returns the znode or a negative error code. */ static struct ubifs_znode *get_znode(struct ubifs_info *c, struct ubifs_znode *znode, int n) { … } /** * tnc_next - find next TNC entry. * @c: UBIFS file-system description object * @zn: znode is passed and returned here * @n: znode branch slot number is passed and returned here * * This function returns %0 if the next TNC entry is found, %-ENOENT if there is * no next entry, or a negative error code otherwise. */ static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n) { … } /** * tnc_prev - find previous TNC entry. * @c: UBIFS file-system description object * @zn: znode is returned here * @n: znode branch slot number is passed and returned here * * This function returns %0 if the previous TNC entry is found, %-ENOENT if * there is no next entry, or a negative error code otherwise. */ static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n) { … } /** * resolve_collision - resolve a collision. * @c: UBIFS file-system description object * @key: key of a directory or extended attribute entry * @zn: znode is returned here * @n: zbranch number is passed and returned here * @nm: name of the entry * * This function is called for "hashed" keys to make sure that the found key * really corresponds to the looked up node (directory or extended attribute * entry). It returns %1 and sets @zn and @n if the collision is resolved. * %0 is returned if @nm is not found and @zn and @n are set to the previous * entry, i.e. to the entry after which @nm could follow if it were in TNC. * This means that @n may be set to %-1 if the leftmost key in @zn is the * previous one. A negative error code is returned on failures. */ static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_znode **zn, int *n, const struct fscrypt_name *nm) { … } /** * fallible_matches_name - determine if a dent matches a given name. * @c: UBIFS file-system description object * @zbr: zbranch of dent * @nm: name to match * * This is a "fallible" version of 'matches_name()' function which does not * panic if the direntry/xentry referred by @zbr does not exist on the media. * * This function checks if xentry/direntry referred by zbranch @zbr matches name * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA * if xentry/direntry referred by @zbr does not exist on the media. A negative * error code is returned in case of failure. */ static int fallible_matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr, const struct fscrypt_name *nm) { … } /** * fallible_resolve_collision - resolve a collision even if nodes are missing. * @c: UBIFS file-system description object * @key: key * @zn: znode is returned here * @n: branch number is passed and returned here * @nm: name of directory entry * @adding: indicates caller is adding a key to the TNC * * This is a "fallible" version of the 'resolve_collision()' function which * does not panic if one of the nodes referred to by TNC does not exist on the * media. This may happen when replaying the journal if a deleted node was * Garbage-collected and the commit was not done. A branch that refers to a node * that is not present is called a dangling branch. The following are the return * codes for this function: * o if @nm was found, %1 is returned and @zn and @n are set to the found * branch; * o if we are @adding and @nm was not found, %0 is returned; * o if we are not @adding and @nm was not found, but a dangling branch was * found, then %1 is returned and @zn and @n are set to the dangling branch; * o a negative error code is returned in case of failure. */ static int fallible_resolve_collision(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_znode **zn, int *n, const struct fscrypt_name *nm, int adding) { … } /** * matches_position - determine if a zbranch matches a given position. * @zbr: zbranch of dent * @lnum: LEB number of dent to match * @offs: offset of dent to match * * This function returns %1 if @lnum:@offs matches, and %0 otherwise. */ static int matches_position(struct ubifs_zbranch *zbr, int lnum, int offs) { … } /** * resolve_collision_directly - resolve a collision directly. * @c: UBIFS file-system description object * @key: key of directory entry * @zn: znode is passed and returned here * @n: zbranch number is passed and returned here * @lnum: LEB number of dent node to match * @offs: offset of dent node to match * * This function is used for "hashed" keys to make sure the found directory or * extended attribute entry node is what was looked for. It is used when the * flash address of the right node is known (@lnum:@offs) which makes it much * easier to resolve collisions (no need to read entries and match full * names). This function returns %1 and sets @zn and @n if the collision is * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the * previous directory entry. Otherwise a negative error code is returned. */ static int resolve_collision_directly(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_znode **zn, int *n, int lnum, int offs) { … } /** * dirty_cow_bottom_up - dirty a znode and its ancestors. * @c: UBIFS file-system description object * @znode: znode to dirty * * If we do not have a unique key that resides in a znode, then we cannot * dirty that znode from the top down (i.e. by using lookup_level0_dirty) * This function records the path back to the last dirty ancestor, and then * dirties the znodes on that path. */ static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * ubifs_lookup_level0 - search for zero-level znode. * @c: UBIFS file-system description object * @key: key to lookup * @zn: znode is returned here * @n: znode branch slot number is returned here * * This function looks up the TNC tree and search for zero-level znode which * refers key @key. The found zero-level znode is returned in @zn. There are 3 * cases: * o exact match, i.e. the found zero-level znode contains key @key, then %1 * is returned and slot number of the matched branch is stored in @n; * o not exact match, which means that zero-level znode does not contain * @key, then %0 is returned and slot number of the closest branch or %-1 * is stored in @n; In this case calling tnc_next() is mandatory. * o @key is so small that it is even less than the lowest key of the * leftmost zero-level node, then %0 is returned and %0 is stored in @n. * * Note, when the TNC tree is traversed, some znodes may be absent, then this * function reads corresponding indexing nodes and inserts them to TNC. In * case of failure, a negative error code is returned. */ int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_znode **zn, int *n) { … } /** * lookup_level0_dirty - search for zero-level znode dirtying. * @c: UBIFS file-system description object * @key: key to lookup * @zn: znode is returned here * @n: znode branch slot number is returned here * * This function looks up the TNC tree and search for zero-level znode which * refers key @key. The found zero-level znode is returned in @zn. There are 3 * cases: * o exact match, i.e. the found zero-level znode contains key @key, then %1 * is returned and slot number of the matched branch is stored in @n; * o not exact match, which means that zero-level znode does not contain @key * then %0 is returned and slot number of the closed branch is stored in * @n; * o @key is so small that it is even less than the lowest key of the * leftmost zero-level node, then %0 is returned and %-1 is stored in @n. * * Additionally all znodes in the path from the root to the located zero-level * znode are marked as dirty. * * Note, when the TNC tree is traversed, some znodes may be absent, then this * function reads corresponding indexing nodes and inserts them to TNC. In * case of failure, a negative error code is returned. */ static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_znode **zn, int *n) { … } /** * maybe_leb_gced - determine if a LEB may have been garbage collected. * @c: UBIFS file-system description object * @lnum: LEB number * @gc_seq1: garbage collection sequence number * * This function determines if @lnum may have been garbage collected since * sequence number @gc_seq1. If it may have been then %1 is returned, otherwise * %0 is returned. */ static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1) { … } /** * ubifs_tnc_locate - look up a file-system node and return it and its location. * @c: UBIFS file-system description object * @key: node key to lookup * @node: the node is returned here * @lnum: LEB number is returned here * @offs: offset is returned here * * This function looks up and reads node with key @key. The caller has to make * sure the @node buffer is large enough to fit the node. Returns zero in case * of success, %-ENOENT if the node was not found, and a negative error code in * case of failure. The node location can be returned in @lnum and @offs. */ int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key, void *node, int *lnum, int *offs) { … } /** * ubifs_tnc_get_bu_keys - lookup keys for bulk-read. * @c: UBIFS file-system description object * @bu: bulk-read parameters and results * * Lookup consecutive data node keys for the same inode that reside * consecutively in the same LEB. This function returns zero in case of success * and a negative error code in case of failure. * * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares * maximum possible amount of nodes for bulk-read. */ int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu) { … } /** * read_wbuf - bulk-read from a LEB with a wbuf. * @wbuf: wbuf that may overlap the read * @buf: buffer into which to read * @len: read length * @lnum: LEB number from which to read * @offs: offset from which to read * * This functions returns %0 on success or a negative error code on failure. */ static int read_wbuf(struct ubifs_wbuf *wbuf, void *buf, int len, int lnum, int offs) { … } /** * validate_data_node - validate data nodes for bulk-read. * @c: UBIFS file-system description object * @buf: buffer containing data node to validate * @zbr: zbranch of data node to validate * * This functions returns %0 on success or a negative error code on failure. */ static int validate_data_node(struct ubifs_info *c, void *buf, struct ubifs_zbranch *zbr) { … } /** * ubifs_tnc_bulk_read - read a number of data nodes in one go. * @c: UBIFS file-system description object * @bu: bulk-read parameters and results * * This functions reads and validates the data nodes that were identified by the * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success, * -EAGAIN to indicate a race with GC, or another negative error code on * failure. */ int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu) { … } /** * do_lookup_nm- look up a "hashed" node. * @c: UBIFS file-system description object * @key: node key to lookup * @node: the node is returned here * @nm: node name * * This function looks up and reads a node which contains name hash in the key. * Since the hash may have collisions, there may be many nodes with the same * key, so we have to sequentially look to all of them until the needed one is * found. This function returns zero in case of success, %-ENOENT if the node * was not found, and a negative error code in case of failure. */ static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key, void *node, const struct fscrypt_name *nm) { … } /** * ubifs_tnc_lookup_nm - look up a "hashed" node. * @c: UBIFS file-system description object * @key: node key to lookup * @node: the node is returned here * @nm: node name * * This function looks up and reads a node which contains name hash in the key. * Since the hash may have collisions, there may be many nodes with the same * key, so we have to sequentially look to all of them until the needed one is * found. This function returns zero in case of success, %-ENOENT if the node * was not found, and a negative error code in case of failure. */ int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key, void *node, const struct fscrypt_name *nm) { … } static int search_dh_cookie(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_dent_node *dent, uint32_t cookie, struct ubifs_znode **zn, int *n, int exact) { … } static int do_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, struct ubifs_dent_node *dent, uint32_t cookie) { … } /** * ubifs_tnc_lookup_dh - look up a "double hashed" node. * @c: UBIFS file-system description object * @key: node key to lookup * @node: the node is returned here * @cookie: node cookie for collision resolution * * This function looks up and reads a node which contains name hash in the key. * Since the hash may have collisions, there may be many nodes with the same * key, so we have to sequentially look to all of them until the needed one * with the same cookie value is found. * This function returns zero in case of success, %-ENOENT if the node * was not found, and a negative error code in case of failure. */ int ubifs_tnc_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, void *node, uint32_t cookie) { … } /** * correct_parent_keys - correct parent znodes' keys. * @c: UBIFS file-system description object * @znode: znode to correct parent znodes for * * This is a helper function for 'tnc_insert()'. When the key of the leftmost * zbranch changes, keys of parent znodes have to be corrected. This helper * function is called in such situations and corrects the keys if needed. */ static void correct_parent_keys(const struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * insert_zbranch - insert a zbranch into a znode. * @c: UBIFS file-system description object * @znode: znode into which to insert * @zbr: zbranch to insert * @n: slot number to insert to * * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in * znode's array of zbranches and keeps zbranches consolidated, so when a new * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th * slot, zbranches starting from @n have to be moved right. */ static void insert_zbranch(struct ubifs_info *c, struct ubifs_znode *znode, const struct ubifs_zbranch *zbr, int n) { … } /** * tnc_insert - insert a node into TNC. * @c: UBIFS file-system description object * @znode: znode to insert into * @zbr: branch to insert * @n: slot number to insert new zbranch to * * This function inserts a new node described by @zbr into znode @znode. If * znode does not have a free slot for new zbranch, it is split. Parent znodes * are splat as well if needed. Returns zero in case of success or a negative * error code in case of failure. */ static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode, struct ubifs_zbranch *zbr, int n) { … } /** * ubifs_tnc_add - add a node to TNC. * @c: UBIFS file-system description object * @key: key to add * @lnum: LEB number of node * @offs: node offset * @len: node length * @hash: The hash over the node * * This function adds a node with key @key to TNC. The node may be new or it may * obsolete some existing one. Returns %0 on success or negative error code on * failure. */ int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum, int offs, int len, const u8 *hash) { … } /** * ubifs_tnc_replace - replace a node in the TNC only if the old node is found. * @c: UBIFS file-system description object * @key: key to add * @old_lnum: LEB number of old node * @old_offs: old node offset * @lnum: LEB number of node * @offs: node offset * @len: node length * * This function replaces a node with key @key in the TNC only if the old node * is found. This function is called by garbage collection when node are moved. * Returns %0 on success or negative error code on failure. */ int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key, int old_lnum, int old_offs, int lnum, int offs, int len) { … } /** * ubifs_tnc_add_nm - add a "hashed" node to TNC. * @c: UBIFS file-system description object * @key: key to add * @lnum: LEB number of node * @offs: node offset * @len: node length * @hash: The hash over the node * @nm: node name * * This is the same as 'ubifs_tnc_add()' but it should be used with keys which * may have collisions, like directory entry keys. */ int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key, int lnum, int offs, int len, const u8 *hash, const struct fscrypt_name *nm) { … } /** * tnc_delete - delete a znode form TNC. * @c: UBIFS file-system description object * @znode: znode to delete from * @n: zbranch slot number to delete * * This function deletes a leaf node from @n-th slot of @znode. Returns zero in * case of success and a negative error code in case of failure. */ static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n) { … } /** * ubifs_tnc_remove - remove an index entry of a node. * @c: UBIFS file-system description object * @key: key of node * * Returns %0 on success or negative error code on failure. */ int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key) { … } /** * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node. * @c: UBIFS file-system description object * @key: key of node * @nm: directory entry name * * Returns %0 on success or negative error code on failure. */ int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key, const struct fscrypt_name *nm) { … } /** * ubifs_tnc_remove_dh - remove an index entry for a "double hashed" node. * @c: UBIFS file-system description object * @key: key of node * @cookie: node cookie for collision resolution * * Returns %0 on success or negative error code on failure. */ int ubifs_tnc_remove_dh(struct ubifs_info *c, const union ubifs_key *key, uint32_t cookie) { … } /** * key_in_range - determine if a key falls within a range of keys. * @c: UBIFS file-system description object * @key: key to check * @from_key: lowest key in range * @to_key: highest key in range * * This function returns %1 if the key is in range and %0 otherwise. */ static int key_in_range(struct ubifs_info *c, union ubifs_key *key, union ubifs_key *from_key, union ubifs_key *to_key) { … } /** * ubifs_tnc_remove_range - remove index entries in range. * @c: UBIFS file-system description object * @from_key: lowest key to remove * @to_key: highest key to remove * * This function removes index entries starting at @from_key and ending at * @to_key. This function returns zero in case of success and a negative error * code in case of failure. */ int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key, union ubifs_key *to_key) { … } /** * ubifs_tnc_remove_ino - remove an inode from TNC. * @c: UBIFS file-system description object * @inum: inode number to remove * * This function remove inode @inum and all the extended attributes associated * with the anode from TNC and returns zero in case of success or a negative * error code in case of failure. */ int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum) { … } /** * ubifs_tnc_next_ent - walk directory or extended attribute entries. * @c: UBIFS file-system description object * @key: key of last entry * @nm: name of last entry found or %NULL * * This function finds and reads the next directory or extended attribute entry * after the given key (@key) if there is one. @nm is used to resolve * collisions. * * If the name of the current entry is not known and only the key is known, * @nm->name has to be %NULL. In this case the semantics of this function is a * little bit different and it returns the entry corresponding to this key, not * the next one. If the key was not found, the closest "right" entry is * returned. * * If the fist entry has to be found, @key has to contain the lowest possible * key value for this inode and @name has to be %NULL. * * This function returns the found directory or extended attribute entry node * in case of success, %-ENOENT is returned if no entry was found, and a * negative error code is returned in case of failure. */ struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c, union ubifs_key *key, const struct fscrypt_name *nm) { … } /** * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit. * @c: UBIFS file-system description object * * Destroy left-over obsolete znodes from a failed commit. */ static void tnc_destroy_cnext(struct ubifs_info *c) { … } /** * ubifs_tnc_close - close TNC subsystem and free all related resources. * @c: UBIFS file-system description object */ void ubifs_tnc_close(struct ubifs_info *c) { … } /** * left_znode - get the znode to the left. * @c: UBIFS file-system description object * @znode: znode * * This function returns a pointer to the znode to the left of @znode or NULL if * there is not one. A negative error code is returned on failure. */ static struct ubifs_znode *left_znode(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * right_znode - get the znode to the right. * @c: UBIFS file-system description object * @znode: znode * * This function returns a pointer to the znode to the right of @znode or NULL * if there is not one. A negative error code is returned on failure. */ static struct ubifs_znode *right_znode(struct ubifs_info *c, struct ubifs_znode *znode) { … } /** * lookup_znode - find a particular indexing node from TNC. * @c: UBIFS file-system description object * @key: index node key to lookup * @level: index node level * @lnum: index node LEB number * @offs: index node offset * * This function searches an indexing node by its first key @key and its * address @lnum:@offs. It looks up the indexing tree by pulling all indexing * nodes it traverses to TNC. This function is called for indexing nodes which * were found on the media by scanning, for example when garbage-collecting or * when doing in-the-gaps commit. This means that the indexing node which is * looked for does not have to have exactly the same leftmost key @key, because * the leftmost key may have been changed, in which case TNC will contain a * dirty znode which still refers the same @lnum:@offs. This function is clever * enough to recognize such indexing nodes. * * Note, if a znode was deleted or changed too much, then this function will * not find it. For situations like this UBIFS has the old index RB-tree * (indexed by @lnum:@offs). * * This function returns a pointer to the znode found or %NULL if it is not * found. A negative error code is returned on failure. */ static struct ubifs_znode *lookup_znode(struct ubifs_info *c, union ubifs_key *key, int level, int lnum, int offs) { … } /** * is_idx_node_in_tnc - determine if an index node is in the TNC. * @c: UBIFS file-system description object * @key: key of index node * @level: index node level * @lnum: LEB number of index node * @offs: offset of index node * * This function returns %0 if the index node is not referred to in the TNC, %1 * if the index node is referred to in the TNC and the corresponding znode is * dirty, %2 if an index node is referred to in the TNC and the corresponding * znode is clean, and a negative error code in case of failure. * * Note, the @key argument has to be the key of the first child. Also note, * this function relies on the fact that 0:0 is never a valid LEB number and * offset for a main-area node. */ int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level, int lnum, int offs) { … } /** * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC. * @c: UBIFS file-system description object * @key: node key * @lnum: node LEB number * @offs: node offset * * This function returns %1 if the node is referred to in the TNC, %0 if it is * not, and a negative error code in case of failure. * * Note, this function relies on the fact that 0:0 is never a valid LEB number * and offset for a main-area node. */ static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int lnum, int offs) { … } /** * ubifs_tnc_has_node - determine whether a node is in the TNC. * @c: UBIFS file-system description object * @key: node key * @level: index node level (if it is an index node) * @lnum: node LEB number * @offs: node offset * @is_idx: non-zero if the node is an index node * * This function returns %1 if the node is in the TNC, %0 if it is not, and a * negative error code in case of failure. For index nodes, @key has to be the * key of the first child. An index node is considered to be in the TNC only if * the corresponding znode is clean or has not been loaded. */ int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level, int lnum, int offs, int is_idx) { … } /** * ubifs_dirty_idx_node - dirty an index node. * @c: UBIFS file-system description object * @key: index node key * @level: index node level * @lnum: index node LEB number * @offs: index node offset * * This function loads and dirties an index node so that it can be garbage * collected. The @key argument has to be the key of the first child. This * function relies on the fact that 0:0 is never a valid LEB number and offset * for a main-area node. Returns %0 on success and a negative error code on * failure. */ int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level, int lnum, int offs) { … } /** * dbg_check_inode_size - check if inode size is correct. * @c: UBIFS file-system description object * @inode: inode to check * @size: inode size * * This function makes sure that the inode size (@size) is correct and it does * not have any pages beyond @size. Returns zero if the inode is OK, %-EINVAL * if it has a data page beyond @size, and other negative error code in case of * other errors. */ int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode, loff_t size) { … }
Codebase Browser
linux