12  * This file implements TNC (Tree Node Cache) which caches indexing nodes of
37  * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media
49  * insert_old_idx - record an index node obsoleted since the last commit start.
51  * @lnum: LEB number of obsoleted index node
52  * @offs: offset of obsoleted index node
63  * committing must be able to determine if an index node is in the old index.
69  * offset because they uniquely identify the old index node.
108  * @znode: znode of obsoleted index node
130  * @znode: znode of obsoleted index node
227  * @lnum: LEB number of index node
228  * @dirt: size of index node
288  * lnc_add - add a leaf node to the leaf node cache.
290  * @zbr: zbranch of leaf node
291  * @node: leaf node
294  * purpose of the leaf node cache is to save re-reading the same leaf node over
297  * present implementation of the leaf node cache is extremely simple, and
301  * Note, this function does not add the @node object to LNC directly, but
303  * is that @node has been allocated outside of the TNC subsystem and will be
308 		   const void *node)  in lnc_add()  argument
312 	const struct ubifs_dent_node *dent = node;  in lnc_add()
325 	lnc_node = kmemdup(node, zbr->len, GFP_NOFS);  in lnc_add()
335  * lnc_add_directly - add a leaf node to the leaf-node-cache.
337  * @zbr: zbranch of leaf node
338  * @node: leaf node
341  * @node but inserts @node to TNC directly.
344 			    void *node)  in lnc_add_directly()  argument
351 	err = ubifs_validate_entry(c, node);  in lnc_add_directly()
354 		ubifs_dump_node(c, node);  in lnc_add_directly()
358 	zbr->leaf = node;  in lnc_add_directly()
363  * lnc_free - remove a leaf node from the leaf node cache.
364  * @zbr: zbranch of leaf node
365  * @node: leaf node
376  * tnc_read_node_nm - read a "hashed" leaf node.
378  * @zbr: key and position of the node
379  * @node: node is returned here
381  * This function reads a "hashed" node defined by @zbr from the leaf node cache
382  * (in it is there) or from the hash media, in which case the node is also
387 			    void *node)  in tnc_read_node_nm()  argument
394 		/* Read from the leaf node cache */  in tnc_read_node_nm()
396 		memcpy(node, zbr->leaf, zbr->len);  in tnc_read_node_nm()
400 	err = ubifs_tnc_read_node(c, zbr, node);  in tnc_read_node_nm()
404 	/* Add the node to the leaf node cache */  in tnc_read_node_nm()
405 	err = lnc_add(c, zbr, node);  in tnc_read_node_nm()
410  * try_read_node - read a node if it is a node.
413  * @type: node type
414  * @len: node length (not aligned)
415  * @lnum: LEB number of node to read
416  * @offs: offset of node to read
418  * This function tries to read a node of known type and length, checks it and
419  * stores it in @buf. This function returns %1 if a node is present and %0 if
420  * a node is not present. A negative error code is returned for I/O errors.
422  * it does not require that there is actually a node present and instead
423  * the return code indicates if a node was read.
444 		ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d",  in try_read_node()
472  * fallible_read_node - try to read a leaf node.
474  * @key:  key of node to read
475  * @zbr:  position of node
476  * @node: node returned
478  * This function tries to read a node and returns %1 if the node is read, %0
479  * if the node is not present, and a negative error code in the case of error.
482 			      struct ubifs_zbranch *zbr, void *node)  in fallible_read_node()  argument
488 	ret = try_read_node(c, node, key_type(c, key), zbr->len, zbr->lnum,  in fallible_read_node()
492 		struct ubifs_dent_node *dent = node;  in fallible_read_node()
522 	/* If possible, match against the dent in the leaf node cache */  in matches_name()
532 		/* Add the node to the leaf node cache */  in matches_name()
678  * really corresponds to the looked up node (directory or extended attribute
810 	/* If possible, match against the dent in the leaf node cache */  in fallible_matches_name()
820 			/* The node was not present */  in fallible_matches_name()
862  * media. This may happen when replaying the journal if a deleted node was
863  * Garbage-collected and the commit was not done. A branch that refers to a node
1006  * @lnum: LEB number of dent node to match
1007  * @offs: offset of dent node to match
1010  * extended attribute entry node is what was looked for. It is used when the
1011  * flash address of the right node is known (@lnum:@offs) which makes it much
1147  *     leftmost zero-level node, then %0 is returned and %0 is stored in @n.
1237 	 * parent node, which would introduce additional complications. Namely,  in ubifs_lookup_level0()
1280  *     leftmost zero-level node, then %0 is returned and %-1 is stored in @n.
1416  * ubifs_tnc_locate - look up a file-system node and return it and its location.
1418  * @key: node key to lookup
1419  * @node: the node is returned here
1423  * This function looks up and reads node with key @key. The caller has to make
1424  * sure the @node buffer is large enough to fit the node. Returns zero in case
1425  * of success, %-ENOENT if the node was not found, and a negative error code in
1426  * case of failure. The node location can be returned in @lnum and @offs.
1429 		     void *node, int *lnum, int *offs)  in ubifs_tnc_locate()  argument
1452 		 * In this case the leaf node cache gets used, so we pass the  in ubifs_tnc_locate()
1455 		err = tnc_read_node_nm(c, zt, node);  in ubifs_tnc_locate()
1459 		err = ubifs_tnc_read_node(c, zt, node);  in ubifs_tnc_locate()
1469 		err = ubifs_tnc_read_node(c, &zbr, node);  in ubifs_tnc_locate()
1473 	err = fallible_read_node(c, key, &zbr, node);  in ubifs_tnc_locate()
1476 		 * The node may have been GC'ed out from under us so try again  in ubifs_tnc_locate()
1494  * Lookup consecutive data node keys for the same inode that reside
1521 		/* The buffer must be big enough for at least 1 node */  in ubifs_tnc_get_bu_keys()
1672  * @buf: buffer containing data node to validate
1673  * @zbr: zbranch of data node to validate
1685 		ubifs_err(c, "bad node type (%d but expected %d)",  in validate_data_node()
1692 		ubifs_err(c, "expected node type %d", UBIFS_DATA_NODE);  in validate_data_node()
1698 		ubifs_err(c, "bad node length %d, expected %d", len, zbr->len);  in validate_data_node()
1702 	/* Make sure the key of the read node is correct */  in validate_data_node()
1705 		ubifs_err(c, "bad key in node at LEB %d:%d",  in validate_data_node()
1708 		dbg_tnck(&key1, "found node's key ");  in validate_data_node()
1717 	ubifs_err(c, "bad node at LEB %d:%d", zbr->lnum, zbr->offs);  in validate_data_node()
1778  * do_lookup_nm- look up a "hashed" node.
1780  * @key: node key to lookup
1781  * @node: the node is returned here
1782  * @nm: node name
1784  * This function look up and reads a node which contains name hash in the key.
1787  * found. This function returns zero in case of success, %-ENOENT if the node
1791 			void *node, const struct qstr *nm)  in do_lookup_nm()  argument
1818 	err = tnc_read_node_nm(c, &znode->zbranch[n], node);  in do_lookup_nm()
1826  * ubifs_tnc_lookup_nm - look up a "hashed" node.
1828  * @key: node key to lookup
1829  * @node: the node is returned here
1830  * @nm: node name
1832  * This function look up and reads a node which contains name hash in the key.
1835  * found. This function returns zero in case of success, %-ENOENT if the node
1839 			void *node, const struct qstr *nm)  in ubifs_tnc_lookup_nm()  argument
1842 	const struct ubifs_dent_node *dent = node;  in ubifs_tnc_lookup_nm()
1848 	err = ubifs_tnc_lookup(c, key, node);  in ubifs_tnc_lookup_nm()
1860 	return do_lookup_nm(c, key, node, nm);  in ubifs_tnc_lookup_nm()
1932 	 * TNC using the key from the index node on flash. That is bad because  in insert_zbranch()
1945  * tnc_insert - insert a node into TNC.
1951  * This function inserts a new node described by @zbr into znode @znode. If
2137  * ubifs_tnc_add - add a node to TNC.
2140  * @lnum: LEB number of node
2141  * @offs: node offset
2142  * @len: node length
2144  * This function adds a node with key @key to TNC. The node may be new or it may
2184  * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
2187  * @old_lnum: LEB number of old node
2188  * @old_offs: old node offset
2189  * @lnum: LEB number of node
2190  * @offs: node offset
2191  * @len: node length
2193  * This function replaces a node with key @key in the TNC only if the old node
2194  * is found.  This function is called by garbage collection when node are moved.
2269  * ubifs_tnc_add_nm - add a "hashed" node to TNC.
2272  * @lnum: LEB number of node
2273  * @offs: node offset
2274  * @len: node length
2275  * @nm: node name
2369  * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2479  * ubifs_tnc_remove - remove an index entry of a node.
2481  * @key: key of node
2508  * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
2510  * @key: key of node
2743  * This function returns the found directory or extended attribute entry node
2946  * lookup_znode - find a particular indexing node from TNC.
2948  * @key: index node key to lookup
2949  * @level: index node level
2950  * @lnum: index node LEB number
2951  * @offs: index node offset
2953  * This function searches an indexing node by its first key @key and its
2957  * when doing in-the-gaps commit. This means that the indexing node which is
3083  * is_idx_node_in_tnc - determine if an index node is in the TNC.
3085  * @key: key of index node
3086  * @level: index node level
3087  * @lnum: LEB number of index node
3088  * @offs: offset of index node
3090  * This function returns %0 if the index node is not referred to in the TNC, %1
3091  * if the index node is referred to in the TNC and the corresponding znode is
3092  * dirty, %2 if an index node is referred to in the TNC and the corresponding
3097  * offset for a main-area node.
3116  * @key: node key
3117  * @lnum: node LEB number
3118  * @offs: node offset
3120  * This function returns %1 if the node is referred to in the TNC, %0 if it is
3124  * and offset for a main-area node.
3183  * ubifs_tnc_has_node - determine whether a node is in the TNC.
3185  * @key: node key
3186  * @level: index node level (if it is an index node)
3187  * @lnum: node LEB number
3188  * @offs: node offset
3189  * @is_idx: non-zero if the node is an index node
3191  * This function returns %1 if the node is in the TNC, %0 if it is not, and a
3193  * key of the first child. An index node is considered to be in the TNC only if
3207 			/* The index node was found but it was dirty */  in ubifs_tnc_has_node()
3210 			/* The index node was found and it was clean */  in ubifs_tnc_has_node()
3223  * ubifs_dirty_idx_node - dirty an index node.
3225  * @key: index node key
3226  * @level: index node level
3227  * @lnum: index node LEB number
3228  * @offs: index node offset
3230  * This function loads and dirties an index node so that it can be garbage
3233  * for a main-area node. Returns %0 on success and a negative error code on