linux/fs/xfs/libxfs/xfs_attr_leaf.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
 * Copyright (c) 2013 Red Hat, Inc.
 * All Rights Reserved.
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_sb.h"
#include "xfs_mount.h"
#include "xfs_da_format.h"
#include "xfs_da_btree.h"
#include "xfs_inode.h"
#include "xfs_trans.h"
#include "xfs_bmap_btree.h"
#include "xfs_bmap.h"
#include "xfs_attr_sf.h"
#include "xfs_attr.h"
#include "xfs_attr_remote.h"
#include "xfs_attr_leaf.h"
#include "xfs_error.h"
#include "xfs_trace.h"
#include "xfs_buf_item.h"
#include "xfs_dir2.h"
#include "xfs_log.h"
#include "xfs_ag.h"
#include "xfs_errortag.h"
#include "xfs_health.h"


/*
 * xfs_attr_leaf.c
 *
 * Routines to implement leaf blocks of attributes as Btrees of hashed names.
 */

/*========================================================================
 * Function prototypes for the kernel.
 *========================================================================*/

/*
 * Routines used for growing the Btree.
 */
STATIC int xfs_attr3_leaf_create(struct xfs_da_args *args,
				 xfs_dablk_t which_block, struct xfs_buf **bpp);
STATIC int xfs_attr3_leaf_add_work(struct xfs_buf *leaf_buffer,
				   struct xfs_attr3_icleaf_hdr *ichdr,
				   struct xfs_da_args *args, int freemap_index);
STATIC void xfs_attr3_leaf_compact(struct xfs_da_args *args,
				   struct xfs_attr3_icleaf_hdr *ichdr,
				   struct xfs_buf *leaf_buffer);
STATIC void xfs_attr3_leaf_rebalance(xfs_da_state_t *state,
						   xfs_da_state_blk_t *blk1,
						   xfs_da_state_blk_t *blk2);
STATIC int xfs_attr3_leaf_figure_balance(xfs_da_state_t *state,
			xfs_da_state_blk_t *leaf_blk_1,
			struct xfs_attr3_icleaf_hdr *ichdr1,
			xfs_da_state_blk_t *leaf_blk_2,
			struct xfs_attr3_icleaf_hdr *ichdr2,
			int *number_entries_in_blk1,
			int *number_usedbytes_in_blk1);

/*
 * Utility routines.
 */
STATIC void xfs_attr3_leaf_moveents(struct xfs_da_args *args,
			struct xfs_attr_leafblock *src_leaf,
			struct xfs_attr3_icleaf_hdr *src_ichdr, int src_start,
			struct xfs_attr_leafblock *dst_leaf,
			struct xfs_attr3_icleaf_hdr *dst_ichdr, int dst_start,
			int move_count);
STATIC int xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index);

/*
 * attr3 block 'firstused' conversion helpers.
 *
 * firstused refers to the offset of the first used byte of the nameval region
 * of an attr leaf block. The region starts at the tail of the block and expands
 * backwards towards the middle. As such, firstused is initialized to the block
 * size for an empty leaf block and is reduced from there.
 *
 * The attr3 block size is pegged to the fsb size and the maximum fsb is 64k.
 * The in-core firstused field is 32-bit and thus supports the maximum fsb size.
 * The on-disk field is only 16-bit, however, and overflows at 64k. Since this
 * only occurs at exactly 64k, we use zero as a magic on-disk value to represent
 * the attr block size. The following helpers manage the conversion between the
 * in-core and on-disk formats.
 */

static void
xfs_attr3_leaf_firstused_from_disk(
	struct xfs_da_geometry		*geo,
	struct xfs_attr3_icleaf_hdr	*to,
	struct xfs_attr_leafblock	*from)
{ … }

static void
xfs_attr3_leaf_firstused_to_disk(
	struct xfs_da_geometry		*geo,
	struct xfs_attr_leafblock	*to,
	struct xfs_attr3_icleaf_hdr	*from)
{ … }

void
xfs_attr3_leaf_hdr_from_disk(
	struct xfs_da_geometry		*geo,
	struct xfs_attr3_icleaf_hdr	*to,
	struct xfs_attr_leafblock	*from)
{ … }

void
xfs_attr3_leaf_hdr_to_disk(
	struct xfs_da_geometry		*geo,
	struct xfs_attr_leafblock	*to,
	struct xfs_attr3_icleaf_hdr	*from)
{ … }

static xfs_failaddr_t
xfs_attr3_leaf_verify_entry(
	struct xfs_mount			*mp,
	char					*buf_end,
	struct xfs_attr_leafblock		*leaf,
	struct xfs_attr3_icleaf_hdr		*leafhdr,
	struct xfs_attr_leaf_entry		*ent,
	int					idx,
	__u32					*last_hashval)
{ … }

/*
 * Validate an attribute leaf block.
 *
 * Empty leaf blocks can occur under the following circumstances:
 *
 * 1. setxattr adds a new extended attribute to a file;
 * 2. The file has zero existing attributes;
 * 3. The attribute is too large to fit in the attribute fork;
 * 4. The attribute is small enough to fit in a leaf block;
 * 5. A log flush occurs after committing the transaction that creates
 *    the (empty) leaf block; and
 * 6. The filesystem goes down after the log flush but before the new
 *    attribute can be committed to the leaf block.
 *
 * Hence we need to ensure that we don't fail the validation purely
 * because the leaf is empty.
 */
static xfs_failaddr_t
xfs_attr3_leaf_verify(
	struct xfs_buf			*bp)
{ … }

xfs_failaddr_t
xfs_attr3_leaf_header_check(
	struct xfs_buf		*bp,
	xfs_ino_t		owner)
{ … }

static void
xfs_attr3_leaf_write_verify(
	struct xfs_buf	*bp)
{ … }

/*
 * leaf/node format detection on trees is sketchy, so a node read can be done on
 * leaf level blocks when detection identifies the tree as a node format tree
 * incorrectly. In this case, we need to swap the verifier to match the correct
 * format of the block being read.
 */
static void
xfs_attr3_leaf_read_verify(
	struct xfs_buf		*bp)
{ … }

const struct xfs_buf_ops xfs_attr3_leaf_buf_ops = …;

int
xfs_attr3_leaf_read(
	struct xfs_trans	*tp,
	struct xfs_inode	*dp,
	xfs_ino_t		owner,
	xfs_dablk_t		bno,
	struct xfs_buf		**bpp)
{ … }

/*========================================================================
 * Namespace helper routines
 *========================================================================*/

/*
 * If we are in log recovery, then we want the lookup to ignore the INCOMPLETE
 * flag on disk - if there's an incomplete attr then recovery needs to tear it
 * down. If there's no incomplete attr, then recovery needs to tear that attr
 * down to replace it with the attr that has been logged. In this case, the
 * INCOMPLETE flag will not be set in attr->attr_filter, but rather
 * XFS_DA_OP_RECOVERY will be set in args->op_flags.
 */
static inline unsigned int xfs_attr_match_mask(const struct xfs_da_args *args)
{ … }

static inline bool
xfs_attr_parent_match(
	const struct xfs_da_args	*args,
	const void			*value,
	unsigned int			valuelen)
{ … }

static bool
xfs_attr_match(
	struct xfs_da_args	*args,
	unsigned int		attr_flags,
	const unsigned char	*name,
	unsigned int		namelen,
	const void		*value,
	unsigned int		valuelen)
{ … }

static int
xfs_attr_copy_value(
	struct xfs_da_args	*args,
	unsigned char		*value,
	int			valuelen)
{ … }

/*========================================================================
 * External routines when attribute fork size < XFS_LITINO(mp).
 *========================================================================*/

/*
 * Query whether the total requested number of attr fork bytes of extended
 * attribute space will be able to fit inline.
 *
 * Returns zero if not, else the i_forkoff fork offset to be used in the
 * literal area for attribute data once the new bytes have been added.
 *
 * i_forkoff must be 8 byte aligned, hence is stored as a >>3 value;
 * special case for dev/uuid inodes, they have fixed size data forks.
 */
int
xfs_attr_shortform_bytesfit(
	struct xfs_inode	*dp,
	int			bytes)
{ … }

/*
 * Switch on the ATTR2 superblock bit (implies also FEATURES2) unless:
 * - noattr2 mount option is set,
 * - on-disk version bit says it is already set, or
 * - the attr2 mount option is not set to enable automatic upgrade from attr1.
 */
STATIC void
xfs_sbversion_add_attr2(
	struct xfs_mount	*mp,
	struct xfs_trans	*tp)
{ … }

/*
 * Create the initial contents of a shortform attribute list.
 */
void
xfs_attr_shortform_create(
	struct xfs_da_args	*args)
{ … }

/*
 * Return the entry if the attr in args is found, or NULL if not.
 */
struct xfs_attr_sf_entry *
xfs_attr_sf_findname(
	struct xfs_da_args		*args)
{ … }

/*
 * Add a name/value pair to the shortform attribute list.
 * Overflow from the inode has already been checked for.
 */
void
xfs_attr_shortform_add(
	struct xfs_da_args		*args,
	int				forkoff)
{ … }

/*
 * After the last attribute is removed revert to original inode format,
 * making all literal area available to the data fork once more.
 */
void
xfs_attr_fork_remove(
	struct xfs_inode	*ip,
	struct xfs_trans	*tp)
{ … }

/*
 * Remove an attribute from the shortform attribute list structure.
 */
int
xfs_attr_sf_removename(
	struct xfs_da_args		*args)
{ … }

/*
 * Retrieve the attribute value and length.
 *
 * If args->valuelen is zero, only the length needs to be returned.  Unlike a
 * lookup, we only return an error if the attribute does not exist or we can't
 * retrieve the value.
 */
int
xfs_attr_shortform_getvalue(
	struct xfs_da_args		*args)
{ … }

/* Convert from using the shortform to the leaf format. */
int
xfs_attr_shortform_to_leaf(
	struct xfs_da_args		*args)
{ … }

/*
 * Check a leaf attribute block to see if all the entries would fit into
 * a shortform attribute list.
 */
int
xfs_attr_shortform_allfit(
	struct xfs_buf		*bp,
	struct xfs_inode	*dp)
{ … }

/* Verify the consistency of a raw inline attribute fork. */
xfs_failaddr_t
xfs_attr_shortform_verify(
	struct xfs_attr_sf_hdr		*sfp,
	size_t				size)
{ … }

/*
 * Convert a leaf attribute list to shortform attribute list
 */
int
xfs_attr3_leaf_to_shortform(
	struct xfs_buf		*bp,
	struct xfs_da_args	*args,
	int			forkoff)
{ … }

/*
 * Convert from using a single leaf to a root node and a leaf.
 */
int
xfs_attr3_leaf_to_node(
	struct xfs_da_args	*args)
{ … }

/*========================================================================
 * Routines used for growing the Btree.
 *========================================================================*/

/*
 * Create the initial contents of a leaf attribute list
 * or a leaf in a node attribute list.
 */
STATIC int
xfs_attr3_leaf_create(
	struct xfs_da_args	*args,
	xfs_dablk_t		blkno,
	struct xfs_buf		**bpp)
{ … }

/*
 * Split the leaf node, rebalance, then add the new entry.
 */
int
xfs_attr3_leaf_split(
	struct xfs_da_state	*state,
	struct xfs_da_state_blk	*oldblk,
	struct xfs_da_state_blk	*newblk)
{ … }

/*
 * Add a name to the leaf attribute list structure.
 */
int
xfs_attr3_leaf_add(
	struct xfs_buf		*bp,
	struct xfs_da_args	*args)
{ … }

/*
 * Add a name to a leaf attribute list structure.
 */
STATIC int
xfs_attr3_leaf_add_work(
	struct xfs_buf		*bp,
	struct xfs_attr3_icleaf_hdr *ichdr,
	struct xfs_da_args	*args,
	int			mapindex)
{ … }

/*
 * Garbage collect a leaf attribute list block by copying it to a new buffer.
 */
STATIC void
xfs_attr3_leaf_compact(
	struct xfs_da_args	*args,
	struct xfs_attr3_icleaf_hdr *ichdr_dst,
	struct xfs_buf		*bp)
{ … }

/*
 * Compare two leaf blocks "order".
 * Return 0 unless leaf2 should go before leaf1.
 */
static int
xfs_attr3_leaf_order(
	struct xfs_buf	*leaf1_bp,
	struct xfs_attr3_icleaf_hdr *leaf1hdr,
	struct xfs_buf	*leaf2_bp,
	struct xfs_attr3_icleaf_hdr *leaf2hdr)
{ … }

int
xfs_attr_leaf_order(
	struct xfs_buf	*leaf1_bp,
	struct xfs_buf	*leaf2_bp)
{ … }

/*
 * Redistribute the attribute list entries between two leaf nodes,
 * taking into account the size of the new entry.
 *
 * NOTE: if new block is empty, then it will get the upper half of the
 * old block.  At present, all (one) callers pass in an empty second block.
 *
 * This code adjusts the args->index/blkno and args->index2/blkno2 fields
 * to match what it is doing in splitting the attribute leaf block.  Those
 * values are used in "atomic rename" operations on attributes.  Note that
 * the "new" and "old" values can end up in different blocks.
 */
STATIC void
xfs_attr3_leaf_rebalance(
	struct xfs_da_state	*state,
	struct xfs_da_state_blk	*blk1,
	struct xfs_da_state_blk	*blk2)
{ … }

/*
 * Examine entries until we reduce the absolute difference in
 * byte usage between the two blocks to a minimum.
 * GROT: Is this really necessary?  With other than a 512 byte blocksize,
 * GROT: there will always be enough room in either block for a new entry.
 * GROT: Do a double-split for this case?
 */
STATIC int
xfs_attr3_leaf_figure_balance(
	struct xfs_da_state		*state,
	struct xfs_da_state_blk		*blk1,
	struct xfs_attr3_icleaf_hdr	*ichdr1,
	struct xfs_da_state_blk		*blk2,
	struct xfs_attr3_icleaf_hdr	*ichdr2,
	int				*countarg,
	int				*usedbytesarg)
{ … }

/*========================================================================
 * Routines used for shrinking the Btree.
 *========================================================================*/

/*
 * Check a leaf block and its neighbors to see if the block should be
 * collapsed into one or the other neighbor.  Always keep the block
 * with the smaller block number.
 * If the current block is over 50% full, don't try to join it, return 0.
 * If the block is empty, fill in the state structure and return 2.
 * If it can be collapsed, fill in the state structure and return 1.
 * If nothing can be done, return 0.
 *
 * GROT: allow for INCOMPLETE entries in calculation.
 */
int
xfs_attr3_leaf_toosmall(
	struct xfs_da_state	*state,
	int			*action)
{ … }

/*
 * Remove a name from the leaf attribute list structure.
 *
 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
 * If two leaves are 37% full, when combined they will leave 25% free.
 */
int
xfs_attr3_leaf_remove(
	struct xfs_buf		*bp,
	struct xfs_da_args	*args)
{ … }

/*
 * Move all the attribute list entries from drop_leaf into save_leaf.
 */
void
xfs_attr3_leaf_unbalance(
	struct xfs_da_state	*state,
	struct xfs_da_state_blk	*drop_blk,
	struct xfs_da_state_blk	*save_blk)
{ … }

/*========================================================================
 * Routines used for finding things in the Btree.
 *========================================================================*/

/*
 * Look up a name in a leaf attribute list structure.
 * This is the internal routine, it uses the caller's buffer.
 *
 * Note that duplicate keys are allowed, but only check within the
 * current leaf node.  The Btree code must check in adjacent leaf nodes.
 *
 * Return in args->index the index into the entry[] array of either
 * the found entry, or where the entry should have been (insert before
 * that entry).
 *
 * Don't change the args->value unless we find the attribute.
 */
int
xfs_attr3_leaf_lookup_int(
	struct xfs_buf		*bp,
	struct xfs_da_args	*args)
{ … }

/*
 * Get the value associated with an attribute name from a leaf attribute
 * list structure.
 *
 * If args->valuelen is zero, only the length needs to be returned.  Unlike a
 * lookup, we only return an error if the attribute does not exist or we can't
 * retrieve the value.
 */
int
xfs_attr3_leaf_getvalue(
	struct xfs_buf		*bp,
	struct xfs_da_args	*args)
{ … }

/*========================================================================
 * Utility routines.
 *========================================================================*/

/*
 * Move the indicated entries from one leaf to another.
 * NOTE: this routine modifies both source and destination leaves.
 */
/*ARGSUSED*/
STATIC void
xfs_attr3_leaf_moveents(
	struct xfs_da_args		*args,
	struct xfs_attr_leafblock	*leaf_s,
	struct xfs_attr3_icleaf_hdr	*ichdr_s,
	int				start_s,
	struct xfs_attr_leafblock	*leaf_d,
	struct xfs_attr3_icleaf_hdr	*ichdr_d,
	int				start_d,
	int				count)
{ … }

/*
 * Pick up the last hashvalue from a leaf block.
 */
xfs_dahash_t
xfs_attr_leaf_lasthash(
	struct xfs_buf	*bp,
	int		*count)
{ … }

/*
 * Calculate the number of bytes used to store the indicated attribute
 * (whether local or remote only calculate bytes in this block).
 */
STATIC int
xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index)
{ … }

/*
 * Calculate the number of bytes that would be required to store the new
 * attribute (whether local or remote only calculate bytes in this block).
 * This routine decides as a side effect whether the attribute will be
 * a "local" or a "remote" attribute.
 */
int
xfs_attr_leaf_newentsize(
	struct xfs_da_args	*args,
	int			*local)
{ … }


/*========================================================================
 * Manage the INCOMPLETE flag in a leaf entry
 *========================================================================*/

/*
 * Clear the INCOMPLETE flag on an entry in a leaf block.
 */
int
xfs_attr3_leaf_clearflag(
	struct xfs_da_args	*args)
{ … }

/*
 * Set the INCOMPLETE flag on an entry in a leaf block.
 */
int
xfs_attr3_leaf_setflag(
	struct xfs_da_args	*args)
{ … }

/*
 * In a single transaction, clear the INCOMPLETE flag on the leaf entry
 * given by args->blkno/index and set the INCOMPLETE flag on the leaf
 * entry given by args->blkno2/index2.
 *
 * Note that they could be in different blocks, or in the same block.
 */
int
xfs_attr3_leaf_flipflags(
	struct xfs_da_args	*args)
{ … }