brintos / linux-shallow public Read only

1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (c) 2000-2005 Silicon Graphics, Inc.4 * Copyright (c) 2013 Red Hat, Inc.5 * All Rights Reserved.6 */7#include "xfs.h"8#include "xfs_fs.h"9#include "xfs_shared.h"10#include "xfs_format.h"11#include "xfs_log_format.h"12#include "xfs_trans_resv.h"13#include "xfs_sb.h"14#include "xfs_mount.h"15#include "xfs_da_format.h"16#include "xfs_da_btree.h"17#include "xfs_inode.h"18#include "xfs_trans.h"19#include "xfs_bmap_btree.h"20#include "xfs_bmap.h"21#include "xfs_attr_sf.h"22#include "xfs_attr.h"23#include "xfs_attr_remote.h"24#include "xfs_attr_leaf.h"25#include "xfs_error.h"26#include "xfs_trace.h"27#include "xfs_buf_item.h"28#include "xfs_dir2.h"29#include "xfs_log.h"30#include "xfs_ag.h"31#include "xfs_errortag.h"32#include "xfs_health.h"33 34 35/*36 * xfs_attr_leaf.c37 *38 * Routines to implement leaf blocks of attributes as Btrees of hashed names.39 */40 41/*========================================================================42 * Function prototypes for the kernel.43 *========================================================================*/44 45/*46 * Routines used for growing the Btree.47 */48STATIC int xfs_attr3_leaf_create(struct xfs_da_args *args,49				 xfs_dablk_t which_block, struct xfs_buf **bpp);50STATIC void xfs_attr3_leaf_add_work(struct xfs_buf *leaf_buffer,51				   struct xfs_attr3_icleaf_hdr *ichdr,52				   struct xfs_da_args *args, int freemap_index);53STATIC void xfs_attr3_leaf_compact(struct xfs_da_args *args,54				   struct xfs_attr3_icleaf_hdr *ichdr,55				   struct xfs_buf *leaf_buffer);56STATIC void xfs_attr3_leaf_rebalance(xfs_da_state_t *state,57						   xfs_da_state_blk_t *blk1,58						   xfs_da_state_blk_t *blk2);59STATIC int xfs_attr3_leaf_figure_balance(xfs_da_state_t *state,60			xfs_da_state_blk_t *leaf_blk_1,61			struct xfs_attr3_icleaf_hdr *ichdr1,62			xfs_da_state_blk_t *leaf_blk_2,63			struct xfs_attr3_icleaf_hdr *ichdr2,64			int *number_entries_in_blk1,65			int *number_usedbytes_in_blk1);66 67/*68 * Utility routines.69 */70STATIC void xfs_attr3_leaf_moveents(struct xfs_da_args *args,71			struct xfs_attr_leafblock *src_leaf,72			struct xfs_attr3_icleaf_hdr *src_ichdr, int src_start,73			struct xfs_attr_leafblock *dst_leaf,74			struct xfs_attr3_icleaf_hdr *dst_ichdr, int dst_start,75			int move_count);76STATIC int xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index);77 78/*79 * attr3 block 'firstused' conversion helpers.80 *81 * firstused refers to the offset of the first used byte of the nameval region82 * of an attr leaf block. The region starts at the tail of the block and expands83 * backwards towards the middle. As such, firstused is initialized to the block84 * size for an empty leaf block and is reduced from there.85 *86 * The attr3 block size is pegged to the fsb size and the maximum fsb is 64k.87 * The in-core firstused field is 32-bit and thus supports the maximum fsb size.88 * The on-disk field is only 16-bit, however, and overflows at 64k. Since this89 * only occurs at exactly 64k, we use zero as a magic on-disk value to represent90 * the attr block size. The following helpers manage the conversion between the91 * in-core and on-disk formats.92 */93 94static void95xfs_attr3_leaf_firstused_from_disk(96	struct xfs_da_geometry		*geo,97	struct xfs_attr3_icleaf_hdr	*to,98	struct xfs_attr_leafblock	*from)99{100	struct xfs_attr3_leaf_hdr	*hdr3;101 102	if (from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC)) {103		hdr3 = (struct xfs_attr3_leaf_hdr *) from;104		to->firstused = be16_to_cpu(hdr3->firstused);105	} else {106		to->firstused = be16_to_cpu(from->hdr.firstused);107	}108 109	/*110	 * Convert from the magic fsb size value to actual blocksize. This111	 * should only occur for empty blocks when the block size overflows112	 * 16-bits.113	 */114	if (to->firstused == XFS_ATTR3_LEAF_NULLOFF) {115		ASSERT(!to->count && !to->usedbytes);116		ASSERT(geo->blksize > USHRT_MAX);117		to->firstused = geo->blksize;118	}119}120 121static void122xfs_attr3_leaf_firstused_to_disk(123	struct xfs_da_geometry		*geo,124	struct xfs_attr_leafblock	*to,125	struct xfs_attr3_icleaf_hdr	*from)126{127	struct xfs_attr3_leaf_hdr	*hdr3;128	uint32_t			firstused;129 130	/* magic value should only be seen on disk */131	ASSERT(from->firstused != XFS_ATTR3_LEAF_NULLOFF);132 133	/*134	 * Scale down the 32-bit in-core firstused value to the 16-bit on-disk135	 * value. This only overflows at the max supported value of 64k. Use the136	 * magic on-disk value to represent block size in this case.137	 */138	firstused = from->firstused;139	if (firstused > USHRT_MAX) {140		ASSERT(from->firstused == geo->blksize);141		firstused = XFS_ATTR3_LEAF_NULLOFF;142	}143 144	if (from->magic == XFS_ATTR3_LEAF_MAGIC) {145		hdr3 = (struct xfs_attr3_leaf_hdr *) to;146		hdr3->firstused = cpu_to_be16(firstused);147	} else {148		to->hdr.firstused = cpu_to_be16(firstused);149	}150}151 152void153xfs_attr3_leaf_hdr_from_disk(154	struct xfs_da_geometry		*geo,155	struct xfs_attr3_icleaf_hdr	*to,156	struct xfs_attr_leafblock	*from)157{158	int	i;159 160	ASSERT(from->hdr.info.magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||161	       from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));162 163	if (from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC)) {164		struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)from;165 166		to->forw = be32_to_cpu(hdr3->info.hdr.forw);167		to->back = be32_to_cpu(hdr3->info.hdr.back);168		to->magic = be16_to_cpu(hdr3->info.hdr.magic);169		to->count = be16_to_cpu(hdr3->count);170		to->usedbytes = be16_to_cpu(hdr3->usedbytes);171		xfs_attr3_leaf_firstused_from_disk(geo, to, from);172		to->holes = hdr3->holes;173 174		for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {175			to->freemap[i].base = be16_to_cpu(hdr3->freemap[i].base);176			to->freemap[i].size = be16_to_cpu(hdr3->freemap[i].size);177		}178		return;179	}180	to->forw = be32_to_cpu(from->hdr.info.forw);181	to->back = be32_to_cpu(from->hdr.info.back);182	to->magic = be16_to_cpu(from->hdr.info.magic);183	to->count = be16_to_cpu(from->hdr.count);184	to->usedbytes = be16_to_cpu(from->hdr.usedbytes);185	xfs_attr3_leaf_firstused_from_disk(geo, to, from);186	to->holes = from->hdr.holes;187 188	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {189		to->freemap[i].base = be16_to_cpu(from->hdr.freemap[i].base);190		to->freemap[i].size = be16_to_cpu(from->hdr.freemap[i].size);191	}192}193 194void195xfs_attr3_leaf_hdr_to_disk(196	struct xfs_da_geometry		*geo,197	struct xfs_attr_leafblock	*to,198	struct xfs_attr3_icleaf_hdr	*from)199{200	int				i;201 202	ASSERT(from->magic == XFS_ATTR_LEAF_MAGIC ||203	       from->magic == XFS_ATTR3_LEAF_MAGIC);204 205	if (from->magic == XFS_ATTR3_LEAF_MAGIC) {206		struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)to;207 208		hdr3->info.hdr.forw = cpu_to_be32(from->forw);209		hdr3->info.hdr.back = cpu_to_be32(from->back);210		hdr3->info.hdr.magic = cpu_to_be16(from->magic);211		hdr3->count = cpu_to_be16(from->count);212		hdr3->usedbytes = cpu_to_be16(from->usedbytes);213		xfs_attr3_leaf_firstused_to_disk(geo, to, from);214		hdr3->holes = from->holes;215		hdr3->pad1 = 0;216 217		for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {218			hdr3->freemap[i].base = cpu_to_be16(from->freemap[i].base);219			hdr3->freemap[i].size = cpu_to_be16(from->freemap[i].size);220		}221		return;222	}223	to->hdr.info.forw = cpu_to_be32(from->forw);224	to->hdr.info.back = cpu_to_be32(from->back);225	to->hdr.info.magic = cpu_to_be16(from->magic);226	to->hdr.count = cpu_to_be16(from->count);227	to->hdr.usedbytes = cpu_to_be16(from->usedbytes);228	xfs_attr3_leaf_firstused_to_disk(geo, to, from);229	to->hdr.holes = from->holes;230	to->hdr.pad1 = 0;231 232	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {233		to->hdr.freemap[i].base = cpu_to_be16(from->freemap[i].base);234		to->hdr.freemap[i].size = cpu_to_be16(from->freemap[i].size);235	}236}237 238static xfs_failaddr_t239xfs_attr3_leaf_verify_entry(240	struct xfs_mount			*mp,241	char					*buf_end,242	struct xfs_attr_leafblock		*leaf,243	struct xfs_attr3_icleaf_hdr		*leafhdr,244	struct xfs_attr_leaf_entry		*ent,245	int					idx,246	__u32					*last_hashval)247{248	struct xfs_attr_leaf_name_local		*lentry;249	struct xfs_attr_leaf_name_remote	*rentry;250	char					*name_end;251	unsigned int				nameidx;252	unsigned int				namesize;253	__u32					hashval;254 255	/* hash order check */256	hashval = be32_to_cpu(ent->hashval);257	if (hashval < *last_hashval)258		return __this_address;259	*last_hashval = hashval;260 261	nameidx = be16_to_cpu(ent->nameidx);262	if (nameidx < leafhdr->firstused || nameidx >= mp->m_attr_geo->blksize)263		return __this_address;264 265	/*266	 * Check the name information.  The namelen fields are u8 so we can't267	 * possibly exceed the maximum name length of 255 bytes.268	 */269	if (ent->flags & XFS_ATTR_LOCAL) {270		lentry = xfs_attr3_leaf_name_local(leaf, idx);271		namesize = xfs_attr_leaf_entsize_local(lentry->namelen,272				be16_to_cpu(lentry->valuelen));273		name_end = (char *)lentry + namesize;274		if (lentry->namelen == 0)275			return __this_address;276	} else {277		rentry = xfs_attr3_leaf_name_remote(leaf, idx);278		namesize = xfs_attr_leaf_entsize_remote(rentry->namelen);279		name_end = (char *)rentry + namesize;280		if (rentry->namelen == 0)281			return __this_address;282		if (!(ent->flags & XFS_ATTR_INCOMPLETE) &&283		    rentry->valueblk == 0)284			return __this_address;285	}286 287	if (name_end > buf_end)288		return __this_address;289 290	return NULL;291}292 293/*294 * Validate an attribute leaf block.295 *296 * Empty leaf blocks can occur under the following circumstances:297 *298 * 1. setxattr adds a new extended attribute to a file;299 * 2. The file has zero existing attributes;300 * 3. The attribute is too large to fit in the attribute fork;301 * 4. The attribute is small enough to fit in a leaf block;302 * 5. A log flush occurs after committing the transaction that creates303 *    the (empty) leaf block; and304 * 6. The filesystem goes down after the log flush but before the new305 *    attribute can be committed to the leaf block.306 *307 * Hence we need to ensure that we don't fail the validation purely308 * because the leaf is empty.309 */310static xfs_failaddr_t311xfs_attr3_leaf_verify(312	struct xfs_buf			*bp)313{314	struct xfs_attr3_icleaf_hdr	ichdr;315	struct xfs_mount		*mp = bp->b_mount;316	struct xfs_attr_leafblock	*leaf = bp->b_addr;317	struct xfs_attr_leaf_entry	*entries;318	struct xfs_attr_leaf_entry	*ent;319	char				*buf_end;320	uint32_t			end;	/* must be 32bit - see below */321	__u32				last_hashval = 0;322	int				i;323	xfs_failaddr_t			fa;324 325	xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr, leaf);326 327	fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);328	if (fa)329		return fa;330 331	/*332	 * firstused is the block offset of the first name info structure.333	 * Make sure it doesn't go off the block or crash into the header.334	 */335	if (ichdr.firstused > mp->m_attr_geo->blksize)336		return __this_address;337	if (ichdr.firstused < xfs_attr3_leaf_hdr_size(leaf))338		return __this_address;339 340	/* Make sure the entries array doesn't crash into the name info. */341	entries = xfs_attr3_leaf_entryp(bp->b_addr);342	if ((char *)&entries[ichdr.count] >343	    (char *)bp->b_addr + ichdr.firstused)344		return __this_address;345 346	/*347	 * NOTE: This verifier historically failed empty leaf buffers because348	 * we expect the fork to be in another format. Empty attr fork format349	 * conversions are possible during xattr set, however, and format350	 * conversion is not atomic with the xattr set that triggers it. We351	 * cannot assume leaf blocks are non-empty until that is addressed.352	*/353	buf_end = (char *)bp->b_addr + mp->m_attr_geo->blksize;354	for (i = 0, ent = entries; i < ichdr.count; ent++, i++) {355		fa = xfs_attr3_leaf_verify_entry(mp, buf_end, leaf, &ichdr,356				ent, i, &last_hashval);357		if (fa)358			return fa;359	}360 361	/*362	 * Quickly check the freemap information.  Attribute data has to be363	 * aligned to 4-byte boundaries, and likewise for the free space.364	 *365	 * Note that for 64k block size filesystems, the freemap entries cannot366	 * overflow as they are only be16 fields. However, when checking end367	 * pointer of the freemap, we have to be careful to detect overflows and368	 * so use uint32_t for those checks.369	 */370	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {371		if (ichdr.freemap[i].base > mp->m_attr_geo->blksize)372			return __this_address;373		if (ichdr.freemap[i].base & 0x3)374			return __this_address;375		if (ichdr.freemap[i].size > mp->m_attr_geo->blksize)376			return __this_address;377		if (ichdr.freemap[i].size & 0x3)378			return __this_address;379 380		/* be care of 16 bit overflows here */381		end = (uint32_t)ichdr.freemap[i].base + ichdr.freemap[i].size;382		if (end < ichdr.freemap[i].base)383			return __this_address;384		if (end > mp->m_attr_geo->blksize)385			return __this_address;386	}387 388	return NULL;389}390 391xfs_failaddr_t392xfs_attr3_leaf_header_check(393	struct xfs_buf		*bp,394	xfs_ino_t		owner)395{396	struct xfs_mount	*mp = bp->b_mount;397 398	if (xfs_has_crc(mp)) {399		struct xfs_attr3_leafblock *hdr3 = bp->b_addr;400 401		if (hdr3->hdr.info.hdr.magic !=402				cpu_to_be16(XFS_ATTR3_LEAF_MAGIC))403			return __this_address;404 405		if (be64_to_cpu(hdr3->hdr.info.owner) != owner)406			return __this_address;407	}408 409	return NULL;410}411 412static void413xfs_attr3_leaf_write_verify(414	struct xfs_buf	*bp)415{416	struct xfs_mount	*mp = bp->b_mount;417	struct xfs_buf_log_item	*bip = bp->b_log_item;418	struct xfs_attr3_leaf_hdr *hdr3 = bp->b_addr;419	xfs_failaddr_t		fa;420 421	fa = xfs_attr3_leaf_verify(bp);422	if (fa) {423		xfs_verifier_error(bp, -EFSCORRUPTED, fa);424		return;425	}426 427	if (!xfs_has_crc(mp))428		return;429 430	if (bip)431		hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);432 433	xfs_buf_update_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF);434}435 436/*437 * leaf/node format detection on trees is sketchy, so a node read can be done on438 * leaf level blocks when detection identifies the tree as a node format tree439 * incorrectly. In this case, we need to swap the verifier to match the correct440 * format of the block being read.441 */442static void443xfs_attr3_leaf_read_verify(444	struct xfs_buf		*bp)445{446	struct xfs_mount	*mp = bp->b_mount;447	xfs_failaddr_t		fa;448 449	if (xfs_has_crc(mp) &&450	     !xfs_buf_verify_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF))451		xfs_verifier_error(bp, -EFSBADCRC, __this_address);452	else {453		fa = xfs_attr3_leaf_verify(bp);454		if (fa)455			xfs_verifier_error(bp, -EFSCORRUPTED, fa);456	}457}458 459const struct xfs_buf_ops xfs_attr3_leaf_buf_ops = {460	.name = "xfs_attr3_leaf",461	.magic16 = { cpu_to_be16(XFS_ATTR_LEAF_MAGIC),462		     cpu_to_be16(XFS_ATTR3_LEAF_MAGIC) },463	.verify_read = xfs_attr3_leaf_read_verify,464	.verify_write = xfs_attr3_leaf_write_verify,465	.verify_struct = xfs_attr3_leaf_verify,466};467 468int469xfs_attr3_leaf_read(470	struct xfs_trans	*tp,471	struct xfs_inode	*dp,472	xfs_ino_t		owner,473	xfs_dablk_t		bno,474	struct xfs_buf		**bpp)475{476	xfs_failaddr_t		fa;477	int			err;478 479	err = xfs_da_read_buf(tp, dp, bno, 0, bpp, XFS_ATTR_FORK,480			&xfs_attr3_leaf_buf_ops);481	if (err || !(*bpp))482		return err;483 484	fa = xfs_attr3_leaf_header_check(*bpp, owner);485	if (fa) {486		__xfs_buf_mark_corrupt(*bpp, fa);487		xfs_trans_brelse(tp, *bpp);488		*bpp = NULL;489		xfs_dirattr_mark_sick(dp, XFS_ATTR_FORK);490		return -EFSCORRUPTED;491	}492 493	if (tp)494		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_ATTR_LEAF_BUF);495	return 0;496}497 498/*========================================================================499 * Namespace helper routines500 *========================================================================*/501 502/*503 * If we are in log recovery, then we want the lookup to ignore the INCOMPLETE504 * flag on disk - if there's an incomplete attr then recovery needs to tear it505 * down. If there's no incomplete attr, then recovery needs to tear that attr506 * down to replace it with the attr that has been logged. In this case, the507 * INCOMPLETE flag will not be set in attr->attr_filter, but rather508 * XFS_DA_OP_RECOVERY will be set in args->op_flags.509 */510static inline unsigned int xfs_attr_match_mask(const struct xfs_da_args *args)511{512	if (args->op_flags & XFS_DA_OP_RECOVERY)513		return XFS_ATTR_NSP_ONDISK_MASK;514	return XFS_ATTR_NSP_ONDISK_MASK | XFS_ATTR_INCOMPLETE;515}516 517static inline bool518xfs_attr_parent_match(519	const struct xfs_da_args	*args,520	const void			*value,521	unsigned int			valuelen)522{523	ASSERT(args->value != NULL);524 525	/* Parent pointers do not use remote values */526	if (!value)527		return false;528 529	/*530	 * The only value we support is a parent rec.  However, we'll accept531	 * any valuelen so that offline repair can delete ATTR_PARENT values532	 * that are not parent pointers.533	 */534	if (valuelen != args->valuelen)535		return false;536 537	return memcmp(args->value, value, valuelen) == 0;538}539 540static bool541xfs_attr_match(542	struct xfs_da_args	*args,543	unsigned int		attr_flags,544	const unsigned char	*name,545	unsigned int		namelen,546	const void		*value,547	unsigned int		valuelen)548{549	unsigned int		mask = xfs_attr_match_mask(args);550 551	if (args->namelen != namelen)552		return false;553	if ((args->attr_filter & mask) != (attr_flags & mask))554		return false;555	if (memcmp(args->name, name, namelen) != 0)556		return false;557 558	if (attr_flags & XFS_ATTR_PARENT)559		return xfs_attr_parent_match(args, value, valuelen);560 561	return true;562}563 564static int565xfs_attr_copy_value(566	struct xfs_da_args	*args,567	unsigned char		*value,568	int			valuelen)569{570	/*571	 * Parent pointer lookups require the caller to specify the name and572	 * value, so don't copy anything.573	 */574	if (args->attr_filter & XFS_ATTR_PARENT)575		return 0;576 577	/*578	 * No copy if all we have to do is get the length579	 */580	if (!args->valuelen) {581		args->valuelen = valuelen;582		return 0;583	}584 585	/*586	 * No copy if the length of the existing buffer is too small587	 */588	if (args->valuelen < valuelen) {589		args->valuelen = valuelen;590		return -ERANGE;591	}592 593	if (!args->value) {594		args->value = kvmalloc(valuelen, GFP_KERNEL | __GFP_NOLOCKDEP);595		if (!args->value)596			return -ENOMEM;597	}598	args->valuelen = valuelen;599 600	/* remote block xattr requires IO for copy-in */601	if (args->rmtblkno)602		return xfs_attr_rmtval_get(args);603 604	/*605	 * This is to prevent a GCC warning because the remote xattr case606	 * doesn't have a value to pass in. In that case, we never reach here,607	 * but GCC can't work that out and so throws a "passing NULL to608	 * memcpy" warning.609	 */610	if (!value)611		return -EINVAL;612	memcpy(args->value, value, valuelen);613	return 0;614}615 616/*========================================================================617 * External routines when attribute fork size < XFS_LITINO(mp).618 *========================================================================*/619 620/*621 * Query whether the total requested number of attr fork bytes of extended622 * attribute space will be able to fit inline.623 *624 * Returns zero if not, else the i_forkoff fork offset to be used in the625 * literal area for attribute data once the new bytes have been added.626 *627 * i_forkoff must be 8 byte aligned, hence is stored as a >>3 value;628 * special case for dev/uuid inodes, they have fixed size data forks.629 */630int631xfs_attr_shortform_bytesfit(632	struct xfs_inode	*dp,633	int			bytes)634{635	struct xfs_mount	*mp = dp->i_mount;636	int64_t			dsize;637	int			minforkoff;638	int			maxforkoff;639	int			offset;640 641	/*642	 * Check if the new size could fit at all first:643	 */644	if (bytes > XFS_LITINO(mp))645		return 0;646 647	/* rounded down */648	offset = (XFS_LITINO(mp) - bytes) >> 3;649 650	if (dp->i_df.if_format == XFS_DINODE_FMT_DEV) {651		minforkoff = roundup(sizeof(xfs_dev_t), 8) >> 3;652		return (offset >= minforkoff) ? minforkoff : 0;653	}654 655	/*656	 * If the requested numbers of bytes is smaller or equal to the657	 * current attribute fork size we can always proceed.658	 *659	 * Note that if_bytes in the data fork might actually be larger than660	 * the current data fork size is due to delalloc extents. In that661	 * case either the extent count will go down when they are converted662	 * to real extents, or the delalloc conversion will take care of the663	 * literal area rebalancing.664	 */665	if (bytes <= xfs_inode_attr_fork_size(dp))666		return dp->i_forkoff;667 668	/*669	 * For attr2 we can try to move the forkoff if there is space in the670	 * literal area, but for the old format we are done if there is no671	 * space in the fixed attribute fork.672	 */673	if (!xfs_has_attr2(mp))674		return 0;675 676	dsize = dp->i_df.if_bytes;677 678	switch (dp->i_df.if_format) {679	case XFS_DINODE_FMT_EXTENTS:680		/*681		 * If there is no attr fork and the data fork is extents,682		 * determine if creating the default attr fork will result683		 * in the extents form migrating to btree. If so, the684		 * minimum offset only needs to be the space required for685		 * the btree root.686		 */687		if (!dp->i_forkoff && dp->i_df.if_bytes >688		    xfs_default_attroffset(dp))689			dsize = xfs_bmdr_space_calc(MINDBTPTRS);690		break;691	case XFS_DINODE_FMT_BTREE:692		/*693		 * If we have a data btree then keep forkoff if we have one,694		 * otherwise we are adding a new attr, so then we set695		 * minforkoff to where the btree root can finish so we have696		 * plenty of room for attrs697		 */698		if (dp->i_forkoff) {699			if (offset < dp->i_forkoff)700				return 0;701			return dp->i_forkoff;702		}703		dsize = xfs_bmap_bmdr_space(dp->i_df.if_broot);704		break;705	}706 707	/*708	 * A data fork btree root must have space for at least709	 * MINDBTPTRS key/ptr pairs if the data fork is small or empty.710	 */711	minforkoff = max_t(int64_t, dsize, xfs_bmdr_space_calc(MINDBTPTRS));712	minforkoff = roundup(minforkoff, 8) >> 3;713 714	/* attr fork btree root can have at least this many key/ptr pairs */715	maxforkoff = XFS_LITINO(mp) - xfs_bmdr_space_calc(MINABTPTRS);716	maxforkoff = maxforkoff >> 3;	/* rounded down */717 718	if (offset >= maxforkoff)719		return maxforkoff;720	if (offset >= minforkoff)721		return offset;722	return 0;723}724 725/*726 * Switch on the ATTR2 superblock bit (implies also FEATURES2) unless:727 * - noattr2 mount option is set,728 * - on-disk version bit says it is already set, or729 * - the attr2 mount option is not set to enable automatic upgrade from attr1.730 */731STATIC void732xfs_sbversion_add_attr2(733	struct xfs_mount	*mp,734	struct xfs_trans	*tp)735{736	if (xfs_has_noattr2(mp))737		return;738	if (mp->m_sb.sb_features2 & XFS_SB_VERSION2_ATTR2BIT)739		return;740	if (!xfs_has_attr2(mp))741		return;742 743	spin_lock(&mp->m_sb_lock);744	xfs_add_attr2(mp);745	spin_unlock(&mp->m_sb_lock);746	xfs_log_sb(tp);747}748 749/*750 * Create the initial contents of a shortform attribute list.751 */752void753xfs_attr_shortform_create(754	struct xfs_da_args	*args)755{756	struct xfs_inode	*dp = args->dp;757	struct xfs_ifork	*ifp = &dp->i_af;758	struct xfs_attr_sf_hdr	*hdr;759 760	trace_xfs_attr_sf_create(args);761 762	ASSERT(ifp->if_bytes == 0);763	if (ifp->if_format == XFS_DINODE_FMT_EXTENTS)764		ifp->if_format = XFS_DINODE_FMT_LOCAL;765 766	hdr = xfs_idata_realloc(dp, sizeof(*hdr), XFS_ATTR_FORK);767	memset(hdr, 0, sizeof(*hdr));768	hdr->totsize = cpu_to_be16(sizeof(*hdr));769	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);770}771 772/*773 * Return the entry if the attr in args is found, or NULL if not.774 */775struct xfs_attr_sf_entry *776xfs_attr_sf_findname(777	struct xfs_da_args		*args)778{779	struct xfs_attr_sf_hdr		*sf = args->dp->i_af.if_data;780	struct xfs_attr_sf_entry	*sfe;781 782	for (sfe = xfs_attr_sf_firstentry(sf);783	     sfe < xfs_attr_sf_endptr(sf);784	     sfe = xfs_attr_sf_nextentry(sfe)) {785		if (xfs_attr_match(args, sfe->flags, sfe->nameval,786				sfe->namelen, &sfe->nameval[sfe->namelen],787				sfe->valuelen))788			return sfe;789	}790 791	return NULL;792}793 794/*795 * Add a name/value pair to the shortform attribute list.796 * Overflow from the inode has already been checked for.797 */798void799xfs_attr_shortform_add(800	struct xfs_da_args		*args,801	int				forkoff)802{803	struct xfs_inode		*dp = args->dp;804	struct xfs_mount		*mp = dp->i_mount;805	struct xfs_ifork		*ifp = &dp->i_af;806	struct xfs_attr_sf_hdr		*sf = ifp->if_data;807	struct xfs_attr_sf_entry	*sfe;808	int				size;809 810	trace_xfs_attr_sf_add(args);811 812	dp->i_forkoff = forkoff;813 814	ASSERT(ifp->if_format == XFS_DINODE_FMT_LOCAL);815	ASSERT(!xfs_attr_sf_findname(args));816 817	size = xfs_attr_sf_entsize_byname(args->namelen, args->valuelen);818	sf = xfs_idata_realloc(dp, size, XFS_ATTR_FORK);819 820	sfe = xfs_attr_sf_endptr(sf);821	sfe->namelen = args->namelen;822	sfe->valuelen = args->valuelen;823	sfe->flags = args->attr_filter;824	memcpy(sfe->nameval, args->name, args->namelen);825	memcpy(&sfe->nameval[args->namelen], args->value, args->valuelen);826	sf->count++;827	be16_add_cpu(&sf->totsize, size);828	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);829 830	xfs_sbversion_add_attr2(mp, args->trans);831}832 833/*834 * After the last attribute is removed revert to original inode format,835 * making all literal area available to the data fork once more.836 */837void838xfs_attr_fork_remove(839	struct xfs_inode	*ip,840	struct xfs_trans	*tp)841{842	ASSERT(ip->i_af.if_nextents == 0);843 844	xfs_ifork_zap_attr(ip);845	ip->i_forkoff = 0;846	xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);847}848 849/*850 * Remove an attribute from the shortform attribute list structure.851 */852int853xfs_attr_sf_removename(854	struct xfs_da_args		*args)855{856	struct xfs_inode		*dp = args->dp;857	struct xfs_mount		*mp = dp->i_mount;858	struct xfs_attr_sf_hdr		*sf = dp->i_af.if_data;859	struct xfs_attr_sf_entry	*sfe;860	uint16_t			totsize = be16_to_cpu(sf->totsize);861	void				*next, *end;862	int				size = 0;863 864	trace_xfs_attr_sf_remove(args);865 866	sfe = xfs_attr_sf_findname(args);867	if (!sfe) {868		/*869		 * If we are recovering an operation, finding nothing to remove870		 * is not an error, it just means there was nothing to clean up.871		 */872		if (args->op_flags & XFS_DA_OP_RECOVERY)873			return 0;874		return -ENOATTR;875	}876 877	/*878	 * Fix up the attribute fork data, covering the hole879	 */880	size = xfs_attr_sf_entsize(sfe);881	next = xfs_attr_sf_nextentry(sfe);882	end = xfs_attr_sf_endptr(sf);883	if (next < end)884		memmove(sfe, next, end - next);885	sf->count--;886	totsize -= size;887	sf->totsize = cpu_to_be16(totsize);888 889	/*890	 * Fix up the start offset of the attribute fork891	 */892	if (totsize == sizeof(struct xfs_attr_sf_hdr) && xfs_has_attr2(mp) &&893	    (dp->i_df.if_format != XFS_DINODE_FMT_BTREE) &&894	    !(args->op_flags & (XFS_DA_OP_ADDNAME | XFS_DA_OP_REPLACE)) &&895	    !xfs_has_parent(mp)) {896		xfs_attr_fork_remove(dp, args->trans);897	} else {898		xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);899		dp->i_forkoff = xfs_attr_shortform_bytesfit(dp, totsize);900		ASSERT(dp->i_forkoff);901		ASSERT(totsize > sizeof(struct xfs_attr_sf_hdr) ||902				(args->op_flags & XFS_DA_OP_ADDNAME) ||903				!xfs_has_attr2(mp) ||904				dp->i_df.if_format == XFS_DINODE_FMT_BTREE ||905				xfs_has_parent(mp));906		xfs_trans_log_inode(args->trans, dp,907					XFS_ILOG_CORE | XFS_ILOG_ADATA);908	}909 910	xfs_sbversion_add_attr2(mp, args->trans);911 912	return 0;913}914 915/*916 * Retrieve the attribute value and length.917 *918 * If args->valuelen is zero, only the length needs to be returned.  Unlike a919 * lookup, we only return an error if the attribute does not exist or we can't920 * retrieve the value.921 */922int923xfs_attr_shortform_getvalue(924	struct xfs_da_args		*args)925{926	struct xfs_attr_sf_entry	*sfe;927 928	ASSERT(args->dp->i_af.if_format == XFS_DINODE_FMT_LOCAL);929 930	trace_xfs_attr_sf_lookup(args);931 932	sfe = xfs_attr_sf_findname(args);933	if (!sfe)934		return -ENOATTR;935	return xfs_attr_copy_value(args, &sfe->nameval[args->namelen],936			sfe->valuelen);937}938 939/* Convert from using the shortform to the leaf format. */940int941xfs_attr_shortform_to_leaf(942	struct xfs_da_args		*args)943{944	struct xfs_inode		*dp = args->dp;945	struct xfs_ifork		*ifp = &dp->i_af;946	struct xfs_attr_sf_hdr		*sf = ifp->if_data;947	struct xfs_attr_sf_entry	*sfe;948	int				size = be16_to_cpu(sf->totsize);949	struct xfs_da_args		nargs;950	char				*tmpbuffer;951	int				error, i;952	xfs_dablk_t			blkno;953	struct xfs_buf			*bp;954 955	trace_xfs_attr_sf_to_leaf(args);956 957	tmpbuffer = kmalloc(size, GFP_KERNEL | __GFP_NOFAIL);958	memcpy(tmpbuffer, ifp->if_data, size);959	sf = (struct xfs_attr_sf_hdr *)tmpbuffer;960 961	xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);962	xfs_bmap_local_to_extents_empty(args->trans, dp, XFS_ATTR_FORK);963 964	bp = NULL;965	error = xfs_da_grow_inode(args, &blkno);966	if (error)967		goto out;968 969	ASSERT(blkno == 0);970	error = xfs_attr3_leaf_create(args, blkno, &bp);971	if (error)972		goto out;973 974	memset((char *)&nargs, 0, sizeof(nargs));975	nargs.dp = dp;976	nargs.geo = args->geo;977	nargs.total = args->total;978	nargs.whichfork = XFS_ATTR_FORK;979	nargs.trans = args->trans;980	nargs.op_flags = XFS_DA_OP_OKNOENT;981	nargs.owner = args->owner;982 983	sfe = xfs_attr_sf_firstentry(sf);984	for (i = 0; i < sf->count; i++) {985		nargs.name = sfe->nameval;986		nargs.namelen = sfe->namelen;987		nargs.value = &sfe->nameval[nargs.namelen];988		nargs.valuelen = sfe->valuelen;989		nargs.attr_filter = sfe->flags & XFS_ATTR_NSP_ONDISK_MASK;990		if (!xfs_attr_check_namespace(sfe->flags)) {991			xfs_da_mark_sick(args);992			error = -EFSCORRUPTED;993			goto out;994		}995		xfs_attr_sethash(&nargs);996		error = xfs_attr3_leaf_lookup_int(bp, &nargs); /* set a->index */997		ASSERT(error == -ENOATTR);998		if (!xfs_attr3_leaf_add(bp, &nargs))999			ASSERT(0);1000		sfe = xfs_attr_sf_nextentry(sfe);1001	}1002	error = 0;1003out:1004	kfree(tmpbuffer);1005	return error;1006}1007 1008/*1009 * Check a leaf attribute block to see if all the entries would fit into1010 * a shortform attribute list.1011 */1012int1013xfs_attr_shortform_allfit(1014	struct xfs_buf		*bp,1015	struct xfs_inode	*dp)1016{1017	struct xfs_attr_leafblock *leaf;1018	struct xfs_attr_leaf_entry *entry;1019	xfs_attr_leaf_name_local_t *name_loc;1020	struct xfs_attr3_icleaf_hdr leafhdr;1021	int			bytes;1022	int			i;1023	struct xfs_mount	*mp = bp->b_mount;1024 1025	leaf = bp->b_addr;1026	xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &leafhdr, leaf);1027	entry = xfs_attr3_leaf_entryp(leaf);1028 1029	bytes = sizeof(struct xfs_attr_sf_hdr);1030	for (i = 0; i < leafhdr.count; entry++, i++) {1031		if (entry->flags & XFS_ATTR_INCOMPLETE)1032			continue;		/* don't copy partial entries */1033		if (!(entry->flags & XFS_ATTR_LOCAL))1034			return 0;1035		name_loc = xfs_attr3_leaf_name_local(leaf, i);1036		if (name_loc->namelen >= XFS_ATTR_SF_ENTSIZE_MAX)1037			return 0;1038		if (be16_to_cpu(name_loc->valuelen) >= XFS_ATTR_SF_ENTSIZE_MAX)1039			return 0;1040		bytes += xfs_attr_sf_entsize_byname(name_loc->namelen,1041					be16_to_cpu(name_loc->valuelen));1042	}1043	if (xfs_has_attr2(dp->i_mount) &&1044	    (dp->i_df.if_format != XFS_DINODE_FMT_BTREE) &&1045	    (bytes == sizeof(struct xfs_attr_sf_hdr)))1046		return -1;1047	return xfs_attr_shortform_bytesfit(dp, bytes);1048}1049 1050/* Verify the consistency of a raw inline attribute fork. */1051xfs_failaddr_t1052xfs_attr_shortform_verify(1053	struct xfs_attr_sf_hdr		*sfp,1054	size_t				size)1055{1056	struct xfs_attr_sf_entry	*sfep = xfs_attr_sf_firstentry(sfp);1057	struct xfs_attr_sf_entry	*next_sfep;1058	char				*endp;1059	int				i;1060 1061	/*1062	 * Give up if the attribute is way too short.1063	 */1064	if (size < sizeof(struct xfs_attr_sf_hdr))1065		return __this_address;1066 1067	endp = (char *)sfp + size;1068 1069	/* Check all reported entries */1070	for (i = 0; i < sfp->count; i++) {1071		/*1072		 * struct xfs_attr_sf_entry has a variable length.1073		 * Check the fixed-offset parts of the structure are1074		 * within the data buffer.1075		 * xfs_attr_sf_entry is defined with a 1-byte variable1076		 * array at the end, so we must subtract that off.1077		 */1078		if (((char *)sfep + sizeof(*sfep)) >= endp)1079			return __this_address;1080 1081		/* Don't allow names with known bad length. */1082		if (sfep->namelen == 0)1083			return __this_address;1084 1085		/*1086		 * Check that the variable-length part of the structure is1087		 * within the data buffer.  The next entry starts after the1088		 * name component, so nextentry is an acceptable test.1089		 */1090		next_sfep = xfs_attr_sf_nextentry(sfep);1091		if ((char *)next_sfep > endp)1092			return __this_address;1093 1094		/*1095		 * Check for unknown flags.  Short form doesn't support1096		 * the incomplete or local bits, so we can use the namespace1097		 * mask here.1098		 */1099		if (sfep->flags & ~XFS_ATTR_NSP_ONDISK_MASK)1100			return __this_address;1101 1102		/*1103		 * Check for invalid namespace combinations.  We only allow1104		 * one namespace flag per xattr, so we can just count the1105		 * bits (i.e. hweight) here.1106		 */1107		if (!xfs_attr_check_namespace(sfep->flags))1108			return __this_address;1109 1110		sfep = next_sfep;1111	}1112	if ((void *)sfep != (void *)endp)1113		return __this_address;1114 1115	return NULL;1116}1117 1118/*1119 * Convert a leaf attribute list to shortform attribute list1120 */1121int1122xfs_attr3_leaf_to_shortform(1123	struct xfs_buf		*bp,1124	struct xfs_da_args	*args,1125	int			forkoff)1126{1127	struct xfs_attr_leafblock *leaf;1128	struct xfs_attr3_icleaf_hdr ichdr;1129	struct xfs_attr_leaf_entry *entry;1130	struct xfs_attr_leaf_name_local *name_loc;1131	struct xfs_da_args	nargs;1132	struct xfs_inode	*dp = args->dp;1133	char			*tmpbuffer;1134	int			error;1135	int			i;1136 1137	trace_xfs_attr_leaf_to_sf(args);1138 1139	tmpbuffer = kvmalloc(args->geo->blksize, GFP_KERNEL | __GFP_NOFAIL);1140	memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);1141 1142	leaf = (xfs_attr_leafblock_t *)tmpbuffer;1143	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);1144	entry = xfs_attr3_leaf_entryp(leaf);1145 1146	/* XXX (dgc): buffer is about to be marked stale - why zero it? */1147	memset(bp->b_addr, 0, args->geo->blksize);1148 1149	/*1150	 * Clean out the prior contents of the attribute list.1151	 */1152	error = xfs_da_shrink_inode(args, 0, bp);1153	if (error)1154		goto out;1155 1156	if (forkoff == -1) {1157		/*1158		 * Don't remove the attr fork if this operation is the first1159		 * part of a attr replace operations. We're going to add a new1160		 * attr immediately, so we need to keep the attr fork around in1161		 * this case.1162		 */1163		if (!(args->op_flags & XFS_DA_OP_REPLACE)) {1164			ASSERT(xfs_has_attr2(dp->i_mount));1165			ASSERT(dp->i_df.if_format != XFS_DINODE_FMT_BTREE);1166			xfs_attr_fork_remove(dp, args->trans);1167		}1168		goto out;1169	}1170 1171	xfs_attr_shortform_create(args);1172 1173	/*1174	 * Copy the attributes1175	 */1176	memset((char *)&nargs, 0, sizeof(nargs));1177	nargs.geo = args->geo;1178	nargs.dp = dp;1179	nargs.total = args->total;1180	nargs.whichfork = XFS_ATTR_FORK;1181	nargs.trans = args->trans;1182	nargs.op_flags = XFS_DA_OP_OKNOENT;1183	nargs.owner = args->owner;1184 1185	for (i = 0; i < ichdr.count; entry++, i++) {1186		if (entry->flags & XFS_ATTR_INCOMPLETE)1187			continue;	/* don't copy partial entries */1188		if (!entry->nameidx)1189			continue;1190		ASSERT(entry->flags & XFS_ATTR_LOCAL);1191		name_loc = xfs_attr3_leaf_name_local(leaf, i);1192		nargs.name = name_loc->nameval;1193		nargs.namelen = name_loc->namelen;1194		nargs.value = &name_loc->nameval[nargs.namelen];1195		nargs.valuelen = be16_to_cpu(name_loc->valuelen);1196		nargs.hashval = be32_to_cpu(entry->hashval);1197		nargs.attr_filter = entry->flags & XFS_ATTR_NSP_ONDISK_MASK;1198		xfs_attr_shortform_add(&nargs, forkoff);1199	}1200	error = 0;1201 1202out:1203	kvfree(tmpbuffer);1204	return error;1205}1206 1207/*1208 * Convert from using a single leaf to a root node and a leaf.1209 */1210int1211xfs_attr3_leaf_to_node(1212	struct xfs_da_args	*args)1213{1214	struct xfs_attr_leafblock *leaf;1215	struct xfs_attr3_icleaf_hdr icleafhdr;1216	struct xfs_attr_leaf_entry *entries;1217	struct xfs_da3_icnode_hdr icnodehdr;1218	struct xfs_da_intnode	*node;1219	struct xfs_inode	*dp = args->dp;1220	struct xfs_mount	*mp = dp->i_mount;1221	struct xfs_buf		*bp1 = NULL;1222	struct xfs_buf		*bp2 = NULL;1223	xfs_dablk_t		blkno;1224	int			error;1225 1226	trace_xfs_attr_leaf_to_node(args);1227 1228	if (XFS_TEST_ERROR(false, mp, XFS_ERRTAG_ATTR_LEAF_TO_NODE)) {1229		error = -EIO;1230		goto out;1231	}1232 1233	error = xfs_da_grow_inode(args, &blkno);1234	if (error)1235		goto out;1236	error = xfs_attr3_leaf_read(args->trans, dp, args->owner, 0, &bp1);1237	if (error)1238		goto out;1239 1240	error = xfs_da_get_buf(args->trans, dp, blkno, &bp2, XFS_ATTR_FORK);1241	if (error)1242		goto out;1243 1244	/*1245	 * Copy leaf to new buffer and log it.1246	 */1247	xfs_da_buf_copy(bp2, bp1, args->geo->blksize);1248	xfs_trans_log_buf(args->trans, bp2, 0, args->geo->blksize - 1);1249 1250	/*1251	 * Set up the new root node.1252	 */1253	error = xfs_da3_node_create(args, 0, 1, &bp1, XFS_ATTR_FORK);1254	if (error)1255		goto out;1256	node = bp1->b_addr;1257	xfs_da3_node_hdr_from_disk(mp, &icnodehdr, node);1258 1259	leaf = bp2->b_addr;1260	xfs_attr3_leaf_hdr_from_disk(args->geo, &icleafhdr, leaf);1261	entries = xfs_attr3_leaf_entryp(leaf);1262 1263	/* both on-disk, don't endian-flip twice */1264	icnodehdr.btree[0].hashval = entries[icleafhdr.count - 1].hashval;1265	icnodehdr.btree[0].before = cpu_to_be32(blkno);1266	icnodehdr.count = 1;1267	xfs_da3_node_hdr_to_disk(dp->i_mount, node, &icnodehdr);1268	xfs_trans_log_buf(args->trans, bp1, 0, args->geo->blksize - 1);1269	error = 0;1270out:1271	return error;1272}1273 1274/*========================================================================1275 * Routines used for growing the Btree.1276 *========================================================================*/1277 1278/*1279 * Create the initial contents of a leaf attribute list1280 * or a leaf in a node attribute list.1281 */1282STATIC int1283xfs_attr3_leaf_create(1284	struct xfs_da_args	*args,1285	xfs_dablk_t		blkno,1286	struct xfs_buf		**bpp)1287{1288	struct xfs_attr_leafblock *leaf;1289	struct xfs_attr3_icleaf_hdr ichdr;1290	struct xfs_inode	*dp = args->dp;1291	struct xfs_mount	*mp = dp->i_mount;1292	struct xfs_buf		*bp;1293	int			error;1294 1295	trace_xfs_attr_leaf_create(args);1296 1297	error = xfs_da_get_buf(args->trans, args->dp, blkno, &bp,1298					    XFS_ATTR_FORK);1299	if (error)1300		return error;1301	bp->b_ops = &xfs_attr3_leaf_buf_ops;1302	xfs_trans_buf_set_type(args->trans, bp, XFS_BLFT_ATTR_LEAF_BUF);1303	leaf = bp->b_addr;1304	memset(leaf, 0, args->geo->blksize);1305 1306	memset(&ichdr, 0, sizeof(ichdr));1307	ichdr.firstused = args->geo->blksize;1308 1309	if (xfs_has_crc(mp)) {1310		struct xfs_da3_blkinfo *hdr3 = bp->b_addr;1311 1312		ichdr.magic = XFS_ATTR3_LEAF_MAGIC;1313 1314		hdr3->blkno = cpu_to_be64(xfs_buf_daddr(bp));1315		hdr3->owner = cpu_to_be64(args->owner);1316		uuid_copy(&hdr3->uuid, &mp->m_sb.sb_meta_uuid);1317 1318		ichdr.freemap[0].base = sizeof(struct xfs_attr3_leaf_hdr);1319	} else {1320		ichdr.magic = XFS_ATTR_LEAF_MAGIC;1321		ichdr.freemap[0].base = sizeof(struct xfs_attr_leaf_hdr);1322	}1323	ichdr.freemap[0].size = ichdr.firstused - ichdr.freemap[0].base;1324 1325	xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);1326	xfs_trans_log_buf(args->trans, bp, 0, args->geo->blksize - 1);1327 1328	*bpp = bp;1329	return 0;1330}1331 1332/*1333 * Split the leaf node, rebalance, then add the new entry.1334 *1335 * Returns 0 if the entry was added, 1 if a further split is needed or a1336 * negative error number otherwise.1337 */1338int1339xfs_attr3_leaf_split(1340	struct xfs_da_state	*state,1341	struct xfs_da_state_blk	*oldblk,1342	struct xfs_da_state_blk	*newblk)1343{1344	bool			added;1345	xfs_dablk_t		blkno;1346	int			error;1347 1348	trace_xfs_attr_leaf_split(state->args);1349 1350	/*1351	 * Allocate space for a new leaf node.1352	 */1353	ASSERT(oldblk->magic == XFS_ATTR_LEAF_MAGIC);1354	error = xfs_da_grow_inode(state->args, &blkno);1355	if (error)1356		return error;1357	error = xfs_attr3_leaf_create(state->args, blkno, &newblk->bp);1358	if (error)1359		return error;1360	newblk->blkno = blkno;1361	newblk->magic = XFS_ATTR_LEAF_MAGIC;1362 1363	/*1364	 * Rebalance the entries across the two leaves.1365	 * NOTE: rebalance() currently depends on the 2nd block being empty.1366	 */1367	xfs_attr3_leaf_rebalance(state, oldblk, newblk);1368	error = xfs_da3_blk_link(state, oldblk, newblk);1369	if (error)1370		return error;1371 1372	/*1373	 * Save info on "old" attribute for "atomic rename" ops, leaf_add()1374	 * modifies the index/blkno/rmtblk/rmtblkcnt fields to show the1375	 * "new" attrs info.  Will need the "old" info to remove it later.1376	 *1377	 * Insert the "new" entry in the correct block.1378	 */1379	if (state->inleaf) {1380		trace_xfs_attr_leaf_add_old(state->args);1381		added = xfs_attr3_leaf_add(oldblk->bp, state->args);1382	} else {1383		trace_xfs_attr_leaf_add_new(state->args);1384		added = xfs_attr3_leaf_add(newblk->bp, state->args);1385	}1386 1387	/*1388	 * Update last hashval in each block since we added the name.1389	 */1390	oldblk->hashval = xfs_attr_leaf_lasthash(oldblk->bp, NULL);1391	newblk->hashval = xfs_attr_leaf_lasthash(newblk->bp, NULL);1392	if (!added)1393		return 1;1394	return 0;1395}1396 1397/*1398 * Add a name to the leaf attribute list structure.1399 */1400bool1401xfs_attr3_leaf_add(1402	struct xfs_buf		*bp,1403	struct xfs_da_args	*args)1404{1405	struct xfs_attr_leafblock *leaf;1406	struct xfs_attr3_icleaf_hdr ichdr;1407	int			tablesize;1408	int			entsize;1409	bool			added = true;1410	int			sum;1411	int			tmp;1412	int			i;1413 1414	trace_xfs_attr_leaf_add(args);1415 1416	leaf = bp->b_addr;1417	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);1418	ASSERT(args->index >= 0 && args->index <= ichdr.count);1419	entsize = xfs_attr_leaf_newentsize(args, NULL);1420 1421	/*1422	 * Search through freemap for first-fit on new name length.1423	 * (may need to figure in size of entry struct too)1424	 */1425	tablesize = (ichdr.count + 1) * sizeof(xfs_attr_leaf_entry_t)1426					+ xfs_attr3_leaf_hdr_size(leaf);1427	for (sum = 0, i = XFS_ATTR_LEAF_MAPSIZE - 1; i >= 0; i--) {1428		if (tablesize > ichdr.firstused) {1429			sum += ichdr.freemap[i].size;1430			continue;1431		}1432		if (!ichdr.freemap[i].size)1433			continue;	/* no space in this map */1434		tmp = entsize;1435		if (ichdr.freemap[i].base < ichdr.firstused)1436			tmp += sizeof(xfs_attr_leaf_entry_t);1437		if (ichdr.freemap[i].size >= tmp) {1438			xfs_attr3_leaf_add_work(bp, &ichdr, args, i);1439			goto out_log_hdr;1440		}1441		sum += ichdr.freemap[i].size;1442	}1443 1444	/*1445	 * If there are no holes in the address space of the block,1446	 * and we don't have enough freespace, then compaction will do us1447	 * no good and we should just give up.1448	 */1449	if (!ichdr.holes && sum < entsize)1450		return false;1451 1452	/*1453	 * Compact the entries to coalesce free space.1454	 * This may change the hdr->count via dropping INCOMPLETE entries.1455	 */1456	xfs_attr3_leaf_compact(args, &ichdr, bp);1457 1458	/*1459	 * After compaction, the block is guaranteed to have only one1460	 * free region, in freemap[0].  If it is not big enough, give up.1461	 */1462	if (ichdr.freemap[0].size < (entsize + sizeof(xfs_attr_leaf_entry_t))) {1463		added = false;1464		goto out_log_hdr;1465	}1466 1467	xfs_attr3_leaf_add_work(bp, &ichdr, args, 0);1468 1469out_log_hdr:1470	xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);1471	xfs_trans_log_buf(args->trans, bp,1472		XFS_DA_LOGRANGE(leaf, &leaf->hdr,1473				xfs_attr3_leaf_hdr_size(leaf)));1474	return added;1475}1476 1477/*1478 * Add a name to a leaf attribute list structure.1479 */1480STATIC void1481xfs_attr3_leaf_add_work(1482	struct xfs_buf		*bp,1483	struct xfs_attr3_icleaf_hdr *ichdr,1484	struct xfs_da_args	*args,1485	int			mapindex)1486{1487	struct xfs_attr_leafblock *leaf;1488	struct xfs_attr_leaf_entry *entry;1489	struct xfs_attr_leaf_name_local *name_loc;1490	struct xfs_attr_leaf_name_remote *name_rmt;1491	struct xfs_mount	*mp;1492	int			tmp;1493	int			i;1494 1495	trace_xfs_attr_leaf_add_work(args);1496 1497	leaf = bp->b_addr;1498	ASSERT(mapindex >= 0 && mapindex < XFS_ATTR_LEAF_MAPSIZE);1499	ASSERT(args->index >= 0 && args->index <= ichdr->count);1500 1501	/*1502	 * Force open some space in the entry array and fill it in.1503	 */1504	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];1505	if (args->index < ichdr->count) {1506		tmp  = ichdr->count - args->index;1507		tmp *= sizeof(xfs_attr_leaf_entry_t);1508		memmove(entry + 1, entry, tmp);1509		xfs_trans_log_buf(args->trans, bp,1510		    XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));1511	}1512	ichdr->count++;1513 1514	/*1515	 * Allocate space for the new string (at the end of the run).1516	 */1517	mp = args->trans->t_mountp;1518	ASSERT(ichdr->freemap[mapindex].base < args->geo->blksize);1519	ASSERT((ichdr->freemap[mapindex].base & 0x3) == 0);1520	ASSERT(ichdr->freemap[mapindex].size >=1521		xfs_attr_leaf_newentsize(args, NULL));1522	ASSERT(ichdr->freemap[mapindex].size < args->geo->blksize);1523	ASSERT((ichdr->freemap[mapindex].size & 0x3) == 0);1524 1525	ichdr->freemap[mapindex].size -= xfs_attr_leaf_newentsize(args, &tmp);1526 1527	entry->nameidx = cpu_to_be16(ichdr->freemap[mapindex].base +1528				     ichdr->freemap[mapindex].size);1529	entry->hashval = cpu_to_be32(args->hashval);1530	entry->flags = args->attr_filter;1531	if (tmp)1532		entry->flags |= XFS_ATTR_LOCAL;1533	if (args->op_flags & XFS_DA_OP_REPLACE) {1534		if (!(args->op_flags & XFS_DA_OP_LOGGED))1535			entry->flags |= XFS_ATTR_INCOMPLETE;1536		if ((args->blkno2 == args->blkno) &&1537		    (args->index2 <= args->index)) {1538			args->index2++;1539		}1540	}1541	xfs_trans_log_buf(args->trans, bp,1542			  XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));1543	ASSERT((args->index == 0) ||1544	       (be32_to_cpu(entry->hashval) >= be32_to_cpu((entry-1)->hashval)));1545	ASSERT((args->index == ichdr->count - 1) ||1546	       (be32_to_cpu(entry->hashval) <= be32_to_cpu((entry+1)->hashval)));1547 1548	/*1549	 * For "remote" attribute values, simply note that we need to1550	 * allocate space for the "remote" value.  We can't actually1551	 * allocate the extents in this transaction, and we can't decide1552	 * which blocks they should be as we might allocate more blocks1553	 * as part of this transaction (a split operation for example).1554	 */1555	if (entry->flags & XFS_ATTR_LOCAL) {1556		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);1557		name_loc->namelen = args->namelen;1558		name_loc->valuelen = cpu_to_be16(args->valuelen);1559		memcpy((char *)name_loc->nameval, args->name, args->namelen);1560		memcpy((char *)&name_loc->nameval[args->namelen], args->value,1561				   be16_to_cpu(name_loc->valuelen));1562	} else {1563		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);1564		name_rmt->namelen = args->namelen;1565		memcpy((char *)name_rmt->name, args->name, args->namelen);1566		entry->flags |= XFS_ATTR_INCOMPLETE;1567		/* just in case */1568		name_rmt->valuelen = 0;1569		name_rmt->valueblk = 0;1570		args->rmtblkno = 1;1571		args->rmtblkcnt = xfs_attr3_rmt_blocks(mp, args->valuelen);1572		args->rmtvaluelen = args->valuelen;1573	}1574	xfs_trans_log_buf(args->trans, bp,1575	     XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),1576				   xfs_attr_leaf_entsize(leaf, args->index)));1577 1578	/*1579	 * Update the control info for this leaf node1580	 */1581	if (be16_to_cpu(entry->nameidx) < ichdr->firstused)1582		ichdr->firstused = be16_to_cpu(entry->nameidx);1583 1584	ASSERT(ichdr->firstused >= ichdr->count * sizeof(xfs_attr_leaf_entry_t)1585					+ xfs_attr3_leaf_hdr_size(leaf));1586	tmp = (ichdr->count - 1) * sizeof(xfs_attr_leaf_entry_t)1587					+ xfs_attr3_leaf_hdr_size(leaf);1588 1589	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {1590		if (ichdr->freemap[i].base == tmp) {1591			ichdr->freemap[i].base += sizeof(xfs_attr_leaf_entry_t);1592			ichdr->freemap[i].size -=1593				min_t(uint16_t, ichdr->freemap[i].size,1594						sizeof(xfs_attr_leaf_entry_t));1595		}1596	}1597	ichdr->usedbytes += xfs_attr_leaf_entsize(leaf, args->index);1598}1599 1600/*1601 * Garbage collect a leaf attribute list block by copying it to a new buffer.1602 */1603STATIC void1604xfs_attr3_leaf_compact(1605	struct xfs_da_args	*args,1606	struct xfs_attr3_icleaf_hdr *ichdr_dst,1607	struct xfs_buf		*bp)1608{1609	struct xfs_attr_leafblock *leaf_src;1610	struct xfs_attr_leafblock *leaf_dst;1611	struct xfs_attr3_icleaf_hdr ichdr_src;1612	struct xfs_trans	*trans = args->trans;1613	char			*tmpbuffer;1614 1615	trace_xfs_attr_leaf_compact(args);1616 1617	tmpbuffer = kvmalloc(args->geo->blksize, GFP_KERNEL | __GFP_NOFAIL);1618	memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);1619	memset(bp->b_addr, 0, args->geo->blksize);1620	leaf_src = (xfs_attr_leafblock_t *)tmpbuffer;1621	leaf_dst = bp->b_addr;1622 1623	/*1624	 * Copy the on-disk header back into the destination buffer to ensure1625	 * all the information in the header that is not part of the incore1626	 * header structure is preserved.1627	 */1628	memcpy(bp->b_addr, tmpbuffer, xfs_attr3_leaf_hdr_size(leaf_src));1629 1630	/* Initialise the incore headers */1631	ichdr_src = *ichdr_dst;	/* struct copy */1632	ichdr_dst->firstused = args->geo->blksize;1633	ichdr_dst->usedbytes = 0;1634	ichdr_dst->count = 0;1635	ichdr_dst->holes = 0;1636	ichdr_dst->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_src);1637	ichdr_dst->freemap[0].size = ichdr_dst->firstused -1638						ichdr_dst->freemap[0].base;1639 1640	/* write the header back to initialise the underlying buffer */1641	xfs_attr3_leaf_hdr_to_disk(args->geo, leaf_dst, ichdr_dst);1642 1643	/*1644	 * Copy all entry's in the same (sorted) order,1645	 * but allocate name/value pairs packed and in sequence.1646	 */1647	xfs_attr3_leaf_moveents(args, leaf_src, &ichdr_src, 0,1648				leaf_dst, ichdr_dst, 0, ichdr_src.count);1649	/*1650	 * this logs the entire buffer, but the caller must write the header1651	 * back to the buffer when it is finished modifying it.1652	 */1653	xfs_trans_log_buf(trans, bp, 0, args->geo->blksize - 1);1654 1655	kvfree(tmpbuffer);1656}1657 1658/*1659 * Compare two leaf blocks "order".1660 * Return 0 unless leaf2 should go before leaf1.1661 */1662static int1663xfs_attr3_leaf_order(1664	struct xfs_buf	*leaf1_bp,1665	struct xfs_attr3_icleaf_hdr *leaf1hdr,1666	struct xfs_buf	*leaf2_bp,1667	struct xfs_attr3_icleaf_hdr *leaf2hdr)1668{1669	struct xfs_attr_leaf_entry *entries1;1670	struct xfs_attr_leaf_entry *entries2;1671 1672	entries1 = xfs_attr3_leaf_entryp(leaf1_bp->b_addr);1673	entries2 = xfs_attr3_leaf_entryp(leaf2_bp->b_addr);1674	if (leaf1hdr->count > 0 && leaf2hdr->count > 0 &&1675	    ((be32_to_cpu(entries2[0].hashval) <1676	      be32_to_cpu(entries1[0].hashval)) ||1677	     (be32_to_cpu(entries2[leaf2hdr->count - 1].hashval) <1678	      be32_to_cpu(entries1[leaf1hdr->count - 1].hashval)))) {1679		return 1;1680	}1681	return 0;1682}1683 1684int1685xfs_attr_leaf_order(1686	struct xfs_buf	*leaf1_bp,1687	struct xfs_buf	*leaf2_bp)1688{1689	struct xfs_attr3_icleaf_hdr ichdr1;1690	struct xfs_attr3_icleaf_hdr ichdr2;1691	struct xfs_mount *mp = leaf1_bp->b_mount;1692 1693	xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr1, leaf1_bp->b_addr);1694	xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr2, leaf2_bp->b_addr);1695	return xfs_attr3_leaf_order(leaf1_bp, &ichdr1, leaf2_bp, &ichdr2);1696}1697 1698/*1699 * Redistribute the attribute list entries between two leaf nodes,1700 * taking into account the size of the new entry.1701 *1702 * NOTE: if new block is empty, then it will get the upper half of the1703 * old block.  At present, all (one) callers pass in an empty second block.1704 *1705 * This code adjusts the args->index/blkno and args->index2/blkno2 fields1706 * to match what it is doing in splitting the attribute leaf block.  Those1707 * values are used in "atomic rename" operations on attributes.  Note that1708 * the "new" and "old" values can end up in different blocks.1709 */1710STATIC void1711xfs_attr3_leaf_rebalance(1712	struct xfs_da_state	*state,1713	struct xfs_da_state_blk	*blk1,1714	struct xfs_da_state_blk	*blk2)1715{1716	struct xfs_da_args	*args;1717	struct xfs_attr_leafblock *leaf1;1718	struct xfs_attr_leafblock *leaf2;1719	struct xfs_attr3_icleaf_hdr ichdr1;1720	struct xfs_attr3_icleaf_hdr ichdr2;1721	struct xfs_attr_leaf_entry *entries1;1722	struct xfs_attr_leaf_entry *entries2;1723	int			count;1724	int			totallen;1725	int			max;1726	int			space;1727	int			swap;1728 1729	/*1730	 * Set up environment.1731	 */1732	ASSERT(blk1->magic == XFS_ATTR_LEAF_MAGIC);1733	ASSERT(blk2->magic == XFS_ATTR_LEAF_MAGIC);1734	leaf1 = blk1->bp->b_addr;1735	leaf2 = blk2->bp->b_addr;1736	xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr1, leaf1);1737	xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr2, leaf2);1738	ASSERT(ichdr2.count == 0);1739	args = state->args;1740 1741	trace_xfs_attr_leaf_rebalance(args);1742 1743	/*1744	 * Check ordering of blocks, reverse if it makes things simpler.1745	 *1746	 * NOTE: Given that all (current) callers pass in an empty1747	 * second block, this code should never set "swap".1748	 */1749	swap = 0;1750	if (xfs_attr3_leaf_order(blk1->bp, &ichdr1, blk2->bp, &ichdr2)) {1751		swap(blk1, blk2);1752 1753		/* swap structures rather than reconverting them */1754		swap(ichdr1, ichdr2);1755 1756		leaf1 = blk1->bp->b_addr;1757		leaf2 = blk2->bp->b_addr;1758		swap = 1;1759	}1760 1761	/*1762	 * Examine entries until we reduce the absolute difference in1763	 * byte usage between the two blocks to a minimum.  Then get1764	 * the direction to copy and the number of elements to move.1765	 *1766	 * "inleaf" is true if the new entry should be inserted into blk1.1767	 * If "swap" is also true, then reverse the sense of "inleaf".1768	 */1769	state->inleaf = xfs_attr3_leaf_figure_balance(state, blk1, &ichdr1,1770						      blk2, &ichdr2,1771						      &count, &totallen);1772	if (swap)1773		state->inleaf = !state->inleaf;1774 1775	/*1776	 * Move any entries required from leaf to leaf:1777	 */1778	if (count < ichdr1.count) {1779		/*1780		 * Figure the total bytes to be added to the destination leaf.1781		 */1782		/* number entries being moved */1783		count = ichdr1.count - count;1784		space  = ichdr1.usedbytes - totallen;1785		space += count * sizeof(xfs_attr_leaf_entry_t);1786 1787		/*1788		 * leaf2 is the destination, compact it if it looks tight.1789		 */1790		max  = ichdr2.firstused - xfs_attr3_leaf_hdr_size(leaf1);1791		max -= ichdr2.count * sizeof(xfs_attr_leaf_entry_t);1792		if (space > max)1793			xfs_attr3_leaf_compact(args, &ichdr2, blk2->bp);1794 1795		/*1796		 * Move high entries from leaf1 to low end of leaf2.1797		 */1798		xfs_attr3_leaf_moveents(args, leaf1, &ichdr1,1799				ichdr1.count - count, leaf2, &ichdr2, 0, count);1800 1801	} else if (count > ichdr1.count) {1802		/*1803		 * I assert that since all callers pass in an empty1804		 * second buffer, this code should never execute.1805		 */1806		ASSERT(0);1807 1808		/*1809		 * Figure the total bytes to be added to the destination leaf.1810		 */1811		/* number entries being moved */1812		count -= ichdr1.count;1813		space  = totallen - ichdr1.usedbytes;1814		space += count * sizeof(xfs_attr_leaf_entry_t);1815 1816		/*1817		 * leaf1 is the destination, compact it if it looks tight.1818		 */1819		max  = ichdr1.firstused - xfs_attr3_leaf_hdr_size(leaf1);1820		max -= ichdr1.count * sizeof(xfs_attr_leaf_entry_t);1821		if (space > max)1822			xfs_attr3_leaf_compact(args, &ichdr1, blk1->bp);1823 1824		/*1825		 * Move low entries from leaf2 to high end of leaf1.1826		 */1827		xfs_attr3_leaf_moveents(args, leaf2, &ichdr2, 0, leaf1, &ichdr1,1828					ichdr1.count, count);1829	}1830 1831	xfs_attr3_leaf_hdr_to_disk(state->args->geo, leaf1, &ichdr1);1832	xfs_attr3_leaf_hdr_to_disk(state->args->geo, leaf2, &ichdr2);1833	xfs_trans_log_buf(args->trans, blk1->bp, 0, args->geo->blksize - 1);1834	xfs_trans_log_buf(args->trans, blk2->bp, 0, args->geo->blksize - 1);1835 1836	/*1837	 * Copy out last hashval in each block for B-tree code.1838	 */1839	entries1 = xfs_attr3_leaf_entryp(leaf1);1840	entries2 = xfs_attr3_leaf_entryp(leaf2);1841	blk1->hashval = be32_to_cpu(entries1[ichdr1.count - 1].hashval);1842	blk2->hashval = be32_to_cpu(entries2[ichdr2.count - 1].hashval);1843 1844	/*1845	 * Adjust the expected index for insertion.1846	 * NOTE: this code depends on the (current) situation that the1847	 * second block was originally empty.1848	 *1849	 * If the insertion point moved to the 2nd block, we must adjust1850	 * the index.  We must also track the entry just following the1851	 * new entry for use in an "atomic rename" operation, that entry1852	 * is always the "old" entry and the "new" entry is what we are1853	 * inserting.  The index/blkno fields refer to the "old" entry,1854	 * while the index2/blkno2 fields refer to the "new" entry.1855	 */1856	if (blk1->index > ichdr1.count) {1857		ASSERT(state->inleaf == 0);1858		blk2->index = blk1->index - ichdr1.count;1859		args->index = args->index2 = blk2->index;1860		args->blkno = args->blkno2 = blk2->blkno;1861	} else if (blk1->index == ichdr1.count) {1862		if (state->inleaf) {1863			args->index = blk1->index;1864			args->blkno = blk1->blkno;1865			args->index2 = 0;1866			args->blkno2 = blk2->blkno;1867		} else {1868			/*1869			 * On a double leaf split, the original attr location1870			 * is already stored in blkno2/index2, so don't1871			 * overwrite it overwise we corrupt the tree.1872			 */1873			blk2->index = blk1->index - ichdr1.count;1874			args->index = blk2->index;1875			args->blkno = blk2->blkno;1876			if (!state->extravalid) {1877				/*1878				 * set the new attr location to match the old1879				 * one and let the higher level split code1880				 * decide where in the leaf to place it.1881				 */1882				args->index2 = blk2->index;1883				args->blkno2 = blk2->blkno;1884			}1885		}1886	} else {1887		ASSERT(state->inleaf == 1);1888		args->index = args->index2 = blk1->index;1889		args->blkno = args->blkno2 = blk1->blkno;1890	}1891}1892 1893/*1894 * Examine entries until we reduce the absolute difference in1895 * byte usage between the two blocks to a minimum.1896 * GROT: Is this really necessary?  With other than a 512 byte blocksize,1897 * GROT: there will always be enough room in either block for a new entry.1898 * GROT: Do a double-split for this case?1899 */1900STATIC int1901xfs_attr3_leaf_figure_balance(1902	struct xfs_da_state		*state,1903	struct xfs_da_state_blk		*blk1,1904	struct xfs_attr3_icleaf_hdr	*ichdr1,1905	struct xfs_da_state_blk		*blk2,1906	struct xfs_attr3_icleaf_hdr	*ichdr2,1907	int				*countarg,1908	int				*usedbytesarg)1909{1910	struct xfs_attr_leafblock	*leaf1 = blk1->bp->b_addr;1911	struct xfs_attr_leafblock	*leaf2 = blk2->bp->b_addr;1912	struct xfs_attr_leaf_entry	*entry;1913	int				count;1914	int				max;1915	int				index;1916	int				totallen = 0;1917	int				half;1918	int				lastdelta;1919	int				foundit = 0;1920	int				tmp;1921 1922	/*1923	 * Examine entries until we reduce the absolute difference in1924	 * byte usage between the two blocks to a minimum.1925	 */1926	max = ichdr1->count + ichdr2->count;1927	half = (max + 1) * sizeof(*entry);1928	half += ichdr1->usedbytes + ichdr2->usedbytes +1929			xfs_attr_leaf_newentsize(state->args, NULL);1930	half /= 2;1931	lastdelta = state->args->geo->blksize;1932	entry = xfs_attr3_leaf_entryp(leaf1);1933	for (count = index = 0; count < max; entry++, index++, count++) {1934 1935#define XFS_ATTR_ABS(A)	(((A) < 0) ? -(A) : (A))1936		/*1937		 * The new entry is in the first block, account for it.1938		 */1939		if (count == blk1->index) {1940			tmp = totallen + sizeof(*entry) +1941				xfs_attr_leaf_newentsize(state->args, NULL);1942			if (XFS_ATTR_ABS(half - tmp) > lastdelta)1943				break;1944			lastdelta = XFS_ATTR_ABS(half - tmp);1945			totallen = tmp;1946			foundit = 1;1947		}1948 1949		/*1950		 * Wrap around into the second block if necessary.1951		 */1952		if (count == ichdr1->count) {1953			leaf1 = leaf2;1954			entry = xfs_attr3_leaf_entryp(leaf1);1955			index = 0;1956		}1957 1958		/*1959		 * Figure out if next leaf entry would be too much.1960		 */1961		tmp = totallen + sizeof(*entry) + xfs_attr_leaf_entsize(leaf1,1962									index);1963		if (XFS_ATTR_ABS(half - tmp) > lastdelta)1964			break;1965		lastdelta = XFS_ATTR_ABS(half - tmp);1966		totallen = tmp;1967#undef XFS_ATTR_ABS1968	}1969 1970	/*1971	 * Calculate the number of usedbytes that will end up in lower block.1972	 * If new entry not in lower block, fix up the count.1973	 */1974	totallen -= count * sizeof(*entry);1975	if (foundit) {1976		totallen -= sizeof(*entry) +1977				xfs_attr_leaf_newentsize(state->args, NULL);1978	}1979 1980	*countarg = count;1981	*usedbytesarg = totallen;1982	return foundit;1983}1984 1985/*========================================================================1986 * Routines used for shrinking the Btree.1987 *========================================================================*/1988 1989/*1990 * Check a leaf block and its neighbors to see if the block should be1991 * collapsed into one or the other neighbor.  Always keep the block1992 * with the smaller block number.1993 * If the current block is over 50% full, don't try to join it, return 0.1994 * If the block is empty, fill in the state structure and return 2.1995 * If it can be collapsed, fill in the state structure and return 1.1996 * If nothing can be done, return 0.1997 *1998 * GROT: allow for INCOMPLETE entries in calculation.1999 */2000int2001xfs_attr3_leaf_toosmall(2002	struct xfs_da_state	*state,2003	int			*action)2004{2005	struct xfs_attr_leafblock *leaf;2006	struct xfs_da_state_blk	*blk;2007	struct xfs_attr3_icleaf_hdr ichdr;2008	struct xfs_buf		*bp;2009	xfs_dablk_t		blkno;2010	int			bytes;2011	int			forward;2012	int			error;2013	int			retval;2014	int			i;2015 2016	trace_xfs_attr_leaf_toosmall(state->args);2017 2018	/*2019	 * Check for the degenerate case of the block being over 50% full.2020	 * If so, it's not worth even looking to see if we might be able2021	 * to coalesce with a sibling.2022	 */2023	blk = &state->path.blk[ state->path.active-1 ];2024	leaf = blk->bp->b_addr;2025	xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr, leaf);2026	bytes = xfs_attr3_leaf_hdr_size(leaf) +2027		ichdr.count * sizeof(xfs_attr_leaf_entry_t) +2028		ichdr.usedbytes;2029	if (bytes > (state->args->geo->blksize >> 1)) {2030		*action = 0;	/* blk over 50%, don't try to join */2031		return 0;2032	}2033 2034	/*2035	 * Check for the degenerate case of the block being empty.2036	 * If the block is empty, we'll simply delete it, no need to2037	 * coalesce it with a sibling block.  We choose (arbitrarily)2038	 * to merge with the forward block unless it is NULL.2039	 */2040	if (ichdr.count == 0) {2041		/*2042		 * Make altpath point to the block we want to keep and2043		 * path point to the block we want to drop (this one).2044		 */2045		forward = (ichdr.forw != 0);2046		memcpy(&state->altpath, &state->path, sizeof(state->path));2047		error = xfs_da3_path_shift(state, &state->altpath, forward,2048						 0, &retval);2049		if (error)2050			return error;2051		if (retval) {2052			*action = 0;2053		} else {2054			*action = 2;2055		}2056		return 0;2057	}2058 2059	/*2060	 * Examine each sibling block to see if we can coalesce with2061	 * at least 25% free space to spare.  We need to figure out2062	 * whether to merge with the forward or the backward block.2063	 * We prefer coalescing with the lower numbered sibling so as2064	 * to shrink an attribute list over time.2065	 */2066	/* start with smaller blk num */2067	forward = ichdr.forw < ichdr.back;2068	for (i = 0; i < 2; forward = !forward, i++) {2069		struct xfs_attr3_icleaf_hdr ichdr2;2070		if (forward)2071			blkno = ichdr.forw;2072		else2073			blkno = ichdr.back;2074		if (blkno == 0)2075			continue;2076		error = xfs_attr3_leaf_read(state->args->trans, state->args->dp,2077					state->args->owner, blkno, &bp);2078		if (error)2079			return error;2080 2081		xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr2, bp->b_addr);2082 2083		bytes = state->args->geo->blksize -2084			(state->args->geo->blksize >> 2) -2085			ichdr.usedbytes - ichdr2.usedbytes -2086			((ichdr.count + ichdr2.count) *2087					sizeof(xfs_attr_leaf_entry_t)) -2088			xfs_attr3_leaf_hdr_size(leaf);2089 2090		xfs_trans_brelse(state->args->trans, bp);2091		if (bytes >= 0)2092			break;	/* fits with at least 25% to spare */2093	}2094	if (i >= 2) {2095		*action = 0;2096		return 0;2097	}2098 2099	/*2100	 * Make altpath point to the block we want to keep (the lower2101	 * numbered block) and path point to the block we want to drop.2102	 */2103	memcpy(&state->altpath, &state->path, sizeof(state->path));2104	if (blkno < blk->blkno) {2105		error = xfs_da3_path_shift(state, &state->altpath, forward,2106						 0, &retval);2107	} else {2108		error = xfs_da3_path_shift(state, &state->path, forward,2109						 0, &retval);2110	}2111	if (error)2112		return error;2113	if (retval) {2114		*action = 0;2115	} else {2116		*action = 1;2117	}2118	return 0;2119}2120 2121/*2122 * Remove a name from the leaf attribute list structure.2123 *2124 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.2125 * If two leaves are 37% full, when combined they will leave 25% free.2126 */2127int2128xfs_attr3_leaf_remove(2129	struct xfs_buf		*bp,2130	struct xfs_da_args	*args)2131{2132	struct xfs_attr_leafblock *leaf;2133	struct xfs_attr3_icleaf_hdr ichdr;2134	struct xfs_attr_leaf_entry *entry;2135	int			before;2136	int			after;2137	int			smallest;2138	int			entsize;2139	int			tablesize;2140	int			tmp;2141	int			i;2142 2143	trace_xfs_attr_leaf_remove(args);2144 2145	leaf = bp->b_addr;2146	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);2147 2148	ASSERT(ichdr.count > 0 && ichdr.count < args->geo->blksize / 8);2149	ASSERT(args->index >= 0 && args->index < ichdr.count);2150	ASSERT(ichdr.firstused >= ichdr.count * sizeof(*entry) +2151					xfs_attr3_leaf_hdr_size(leaf));2152 2153	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];2154 2155	ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);2156	ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);2157 2158	/*2159	 * Scan through free region table:2160	 *    check for adjacency of free'd entry with an existing one,2161	 *    find smallest free region in case we need to replace it,2162	 *    adjust any map that borders the entry table,2163	 */2164	tablesize = ichdr.count * sizeof(xfs_attr_leaf_entry_t)2165					+ xfs_attr3_leaf_hdr_size(leaf);2166	tmp = ichdr.freemap[0].size;2167	before = after = -1;2168	smallest = XFS_ATTR_LEAF_MAPSIZE - 1;2169	entsize = xfs_attr_leaf_entsize(leaf, args->index);2170	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {2171		ASSERT(ichdr.freemap[i].base < args->geo->blksize);2172		ASSERT(ichdr.freemap[i].size < args->geo->blksize);2173		if (ichdr.freemap[i].base == tablesize) {2174			ichdr.freemap[i].base -= sizeof(xfs_attr_leaf_entry_t);2175			ichdr.freemap[i].size += sizeof(xfs_attr_leaf_entry_t);2176		}2177 2178		if (ichdr.freemap[i].base + ichdr.freemap[i].size ==2179				be16_to_cpu(entry->nameidx)) {2180			before = i;2181		} else if (ichdr.freemap[i].base ==2182				(be16_to_cpu(entry->nameidx) + entsize)) {2183			after = i;2184		} else if (ichdr.freemap[i].size < tmp) {2185			tmp = ichdr.freemap[i].size;2186			smallest = i;2187		}2188	}2189 2190	/*2191	 * Coalesce adjacent freemap regions,2192	 * or replace the smallest region.2193	 */2194	if ((before >= 0) || (after >= 0)) {2195		if ((before >= 0) && (after >= 0)) {2196			ichdr.freemap[before].size += entsize;2197			ichdr.freemap[before].size += ichdr.freemap[after].size;2198			ichdr.freemap[after].base = 0;2199			ichdr.freemap[after].size = 0;2200		} else if (before >= 0) {2201			ichdr.freemap[before].size += entsize;2202		} else {2203			ichdr.freemap[after].base = be16_to_cpu(entry->nameidx);2204			ichdr.freemap[after].size += entsize;2205		}2206	} else {2207		/*2208		 * Replace smallest region (if it is smaller than free'd entry)2209		 */2210		if (ichdr.freemap[smallest].size < entsize) {2211			ichdr.freemap[smallest].base = be16_to_cpu(entry->nameidx);2212			ichdr.freemap[smallest].size = entsize;2213		}2214	}2215 2216	/*2217	 * Did we remove the first entry?2218	 */2219	if (be16_to_cpu(entry->nameidx) == ichdr.firstused)2220		smallest = 1;2221	else2222		smallest = 0;2223 2224	/*2225	 * Compress the remaining entries and zero out the removed stuff.2226	 */2227	memset(xfs_attr3_leaf_name(leaf, args->index), 0, entsize);2228	ichdr.usedbytes -= entsize;2229	xfs_trans_log_buf(args->trans, bp,2230	     XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),2231				   entsize));2232 2233	tmp = (ichdr.count - args->index) * sizeof(xfs_attr_leaf_entry_t);2234	memmove(entry, entry + 1, tmp);2235	ichdr.count--;2236	xfs_trans_log_buf(args->trans, bp,2237	    XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(xfs_attr_leaf_entry_t)));2238 2239	entry = &xfs_attr3_leaf_entryp(leaf)[ichdr.count];2240	memset(entry, 0, sizeof(xfs_attr_leaf_entry_t));2241 2242	/*2243	 * If we removed the first entry, re-find the first used byte2244	 * in the name area.  Note that if the entry was the "firstused",2245	 * then we don't have a "hole" in our block resulting from2246	 * removing the name.2247	 */2248	if (smallest) {2249		tmp = args->geo->blksize;2250		entry = xfs_attr3_leaf_entryp(leaf);2251		for (i = ichdr.count - 1; i >= 0; entry++, i--) {2252			ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);2253			ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);2254 2255			if (be16_to_cpu(entry->nameidx) < tmp)2256				tmp = be16_to_cpu(entry->nameidx);2257		}2258		ichdr.firstused = tmp;2259		ASSERT(ichdr.firstused != 0);2260	} else {2261		ichdr.holes = 1;	/* mark as needing compaction */2262	}2263	xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);2264	xfs_trans_log_buf(args->trans, bp,2265			  XFS_DA_LOGRANGE(leaf, &leaf->hdr,2266					  xfs_attr3_leaf_hdr_size(leaf)));2267 2268	/*2269	 * Check if leaf is less than 50% full, caller may want to2270	 * "join" the leaf with a sibling if so.2271	 */2272	tmp = ichdr.usedbytes + xfs_attr3_leaf_hdr_size(leaf) +2273	      ichdr.count * sizeof(xfs_attr_leaf_entry_t);2274 2275	return tmp < args->geo->magicpct; /* leaf is < 37% full */2276}2277 2278/*2279 * Move all the attribute list entries from drop_leaf into save_leaf.2280 */2281void2282xfs_attr3_leaf_unbalance(2283	struct xfs_da_state	*state,2284	struct xfs_da_state_blk	*drop_blk,2285	struct xfs_da_state_blk	*save_blk)2286{2287	struct xfs_attr_leafblock *drop_leaf = drop_blk->bp->b_addr;2288	struct xfs_attr_leafblock *save_leaf = save_blk->bp->b_addr;2289	struct xfs_attr3_icleaf_hdr drophdr;2290	struct xfs_attr3_icleaf_hdr savehdr;2291	struct xfs_attr_leaf_entry *entry;2292 2293	trace_xfs_attr_leaf_unbalance(state->args);2294 2295	xfs_attr3_leaf_hdr_from_disk(state->args->geo, &drophdr, drop_leaf);2296	xfs_attr3_leaf_hdr_from_disk(state->args->geo, &savehdr, save_leaf);2297	entry = xfs_attr3_leaf_entryp(drop_leaf);2298 2299	/*2300	 * Save last hashval from dying block for later Btree fixup.2301	 */2302	drop_blk->hashval = be32_to_cpu(entry[drophdr.count - 1].hashval);2303 2304	/*2305	 * Check if we need a temp buffer, or can we do it in place.2306	 * Note that we don't check "leaf" for holes because we will2307	 * always be dropping it, toosmall() decided that for us already.2308	 */2309	if (savehdr.holes == 0) {2310		/*2311		 * dest leaf has no holes, so we add there.  May need2312		 * to make some room in the entry array.2313		 */2314		if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,2315					 drop_blk->bp, &drophdr)) {2316			xfs_attr3_leaf_moveents(state->args,2317						drop_leaf, &drophdr, 0,2318						save_leaf, &savehdr, 0,2319						drophdr.count);2320		} else {2321			xfs_attr3_leaf_moveents(state->args,2322						drop_leaf, &drophdr, 0,2323						save_leaf, &savehdr,2324						savehdr.count, drophdr.count);2325		}2326	} else {2327		/*2328		 * Destination has holes, so we make a temporary copy2329		 * of the leaf and add them both to that.2330		 */2331		struct xfs_attr_leafblock *tmp_leaf;2332		struct xfs_attr3_icleaf_hdr tmphdr;2333 2334		tmp_leaf = kvzalloc(state->args->geo->blksize,2335				GFP_KERNEL | __GFP_NOFAIL);2336 2337		/*2338		 * Copy the header into the temp leaf so that all the stuff2339		 * not in the incore header is present and gets copied back in2340		 * once we've moved all the entries.2341		 */2342		memcpy(tmp_leaf, save_leaf, xfs_attr3_leaf_hdr_size(save_leaf));2343 2344		memset(&tmphdr, 0, sizeof(tmphdr));2345		tmphdr.magic = savehdr.magic;2346		tmphdr.forw = savehdr.forw;2347		tmphdr.back = savehdr.back;2348		tmphdr.firstused = state->args->geo->blksize;2349 2350		/* write the header to the temp buffer to initialise it */2351		xfs_attr3_leaf_hdr_to_disk(state->args->geo, tmp_leaf, &tmphdr);2352 2353		if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,2354					 drop_blk->bp, &drophdr)) {2355			xfs_attr3_leaf_moveents(state->args,2356						drop_leaf, &drophdr, 0,2357						tmp_leaf, &tmphdr, 0,2358						drophdr.count);2359			xfs_attr3_leaf_moveents(state->args,2360						save_leaf, &savehdr, 0,2361						tmp_leaf, &tmphdr, tmphdr.count,2362						savehdr.count);2363		} else {2364			xfs_attr3_leaf_moveents(state->args,2365						save_leaf, &savehdr, 0,2366						tmp_leaf, &tmphdr, 0,2367						savehdr.count);2368			xfs_attr3_leaf_moveents(state->args,2369						drop_leaf, &drophdr, 0,2370						tmp_leaf, &tmphdr, tmphdr.count,2371						drophdr.count);2372		}2373		memcpy(save_leaf, tmp_leaf, state->args->geo->blksize);2374		savehdr = tmphdr; /* struct copy */2375		kvfree(tmp_leaf);2376	}2377 2378	xfs_attr3_leaf_hdr_to_disk(state->args->geo, save_leaf, &savehdr);2379	xfs_trans_log_buf(state->args->trans, save_blk->bp, 0,2380					   state->args->geo->blksize - 1);2381 2382	/*2383	 * Copy out last hashval in each block for B-tree code.2384	 */2385	entry = xfs_attr3_leaf_entryp(save_leaf);2386	save_blk->hashval = be32_to_cpu(entry[savehdr.count - 1].hashval);2387}2388 2389/*========================================================================2390 * Routines used for finding things in the Btree.2391 *========================================================================*/2392 2393/*2394 * Look up a name in a leaf attribute list structure.2395 * This is the internal routine, it uses the caller's buffer.2396 *2397 * Note that duplicate keys are allowed, but only check within the2398 * current leaf node.  The Btree code must check in adjacent leaf nodes.2399 *2400 * Return in args->index the index into the entry[] array of either2401 * the found entry, or where the entry should have been (insert before2402 * that entry).2403 *2404 * Don't change the args->value unless we find the attribute.2405 */2406int2407xfs_attr3_leaf_lookup_int(2408	struct xfs_buf		*bp,2409	struct xfs_da_args	*args)2410{2411	struct xfs_attr_leafblock *leaf;2412	struct xfs_attr3_icleaf_hdr ichdr;2413	struct xfs_attr_leaf_entry *entry;2414	struct xfs_attr_leaf_entry *entries;2415	struct xfs_attr_leaf_name_local *name_loc;2416	struct xfs_attr_leaf_name_remote *name_rmt;2417	xfs_dahash_t		hashval;2418	int			probe;2419	int			span;2420 2421	trace_xfs_attr_leaf_lookup(args);2422 2423	leaf = bp->b_addr;2424	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);2425	entries = xfs_attr3_leaf_entryp(leaf);2426	if (ichdr.count >= args->geo->blksize / 8) {2427		xfs_buf_mark_corrupt(bp);2428		xfs_da_mark_sick(args);2429		return -EFSCORRUPTED;2430	}2431 2432	/*2433	 * Binary search.  (note: small blocks will skip this loop)2434	 */2435	hashval = args->hashval;2436	probe = span = ichdr.count / 2;2437	for (entry = &entries[probe]; span > 4; entry = &entries[probe]) {2438		span /= 2;2439		if (be32_to_cpu(entry->hashval) < hashval)2440			probe += span;2441		else if (be32_to_cpu(entry->hashval) > hashval)2442			probe -= span;2443		else2444			break;2445	}2446	if (!(probe >= 0 && (!ichdr.count || probe < ichdr.count))) {2447		xfs_buf_mark_corrupt(bp);2448		xfs_da_mark_sick(args);2449		return -EFSCORRUPTED;2450	}2451	if (!(span <= 4 || be32_to_cpu(entry->hashval) == hashval)) {2452		xfs_buf_mark_corrupt(bp);2453		xfs_da_mark_sick(args);2454		return -EFSCORRUPTED;2455	}2456 2457	/*2458	 * Since we may have duplicate hashval's, find the first matching2459	 * hashval in the leaf.2460	 */2461	while (probe > 0 && be32_to_cpu(entry->hashval) >= hashval) {2462		entry--;2463		probe--;2464	}2465	while (probe < ichdr.count &&2466	       be32_to_cpu(entry->hashval) < hashval) {2467		entry++;2468		probe++;2469	}2470	if (probe == ichdr.count || be32_to_cpu(entry->hashval) != hashval) {2471		args->index = probe;2472		return -ENOATTR;2473	}2474 2475	/*2476	 * Duplicate keys may be present, so search all of them for a match.2477	 */2478	for (; probe < ichdr.count && (be32_to_cpu(entry->hashval) == hashval);2479			entry++, probe++) {2480/*2481 * GROT: Add code to remove incomplete entries.2482 */2483		if (entry->flags & XFS_ATTR_LOCAL) {2484			name_loc = xfs_attr3_leaf_name_local(leaf, probe);2485			if (!xfs_attr_match(args, entry->flags,2486					name_loc->nameval, name_loc->namelen,2487					&name_loc->nameval[name_loc->namelen],2488					be16_to_cpu(name_loc->valuelen)))2489				continue;2490			args->index = probe;2491			return -EEXIST;2492		} else {2493			unsigned int	valuelen;2494 2495			name_rmt = xfs_attr3_leaf_name_remote(leaf, probe);2496			valuelen = be32_to_cpu(name_rmt->valuelen);2497			if (!xfs_attr_match(args, entry->flags, name_rmt->name,2498					name_rmt->namelen, NULL, valuelen))2499				continue;2500			args->index = probe;2501			args->rmtvaluelen = valuelen;2502			args->rmtblkno = be32_to_cpu(name_rmt->valueblk);2503			args->rmtblkcnt = xfs_attr3_rmt_blocks(2504							args->dp->i_mount,2505							args->rmtvaluelen);2506			return -EEXIST;2507		}2508	}2509	args->index = probe;2510	return -ENOATTR;2511}2512 2513/*2514 * Get the value associated with an attribute name from a leaf attribute2515 * list structure.2516 *2517 * If args->valuelen is zero, only the length needs to be returned.  Unlike a2518 * lookup, we only return an error if the attribute does not exist or we can't2519 * retrieve the value.2520 */2521int2522xfs_attr3_leaf_getvalue(2523	struct xfs_buf		*bp,2524	struct xfs_da_args	*args)2525{2526	struct xfs_attr_leafblock *leaf;2527	struct xfs_attr3_icleaf_hdr ichdr;2528	struct xfs_attr_leaf_entry *entry;2529	struct xfs_attr_leaf_name_local *name_loc;2530	struct xfs_attr_leaf_name_remote *name_rmt;2531 2532	leaf = bp->b_addr;2533	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);2534	ASSERT(ichdr.count < args->geo->blksize / 8);2535	ASSERT(args->index < ichdr.count);2536 2537	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];2538	if (entry->flags & XFS_ATTR_LOCAL) {2539		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);2540		ASSERT(name_loc->namelen == args->namelen);2541		ASSERT(memcmp(args->name, name_loc->nameval, args->namelen) == 0);2542		return xfs_attr_copy_value(args,2543					&name_loc->nameval[args->namelen],2544					be16_to_cpu(name_loc->valuelen));2545	}2546 2547	name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);2548	ASSERT(name_rmt->namelen == args->namelen);2549	ASSERT(memcmp(args->name, name_rmt->name, args->namelen) == 0);2550	args->rmtvaluelen = be32_to_cpu(name_rmt->valuelen);2551	args->rmtblkno = be32_to_cpu(name_rmt->valueblk);2552	args->rmtblkcnt = xfs_attr3_rmt_blocks(args->dp->i_mount,2553					       args->rmtvaluelen);2554	return xfs_attr_copy_value(args, NULL, args->rmtvaluelen);2555}2556 2557/*========================================================================2558 * Utility routines.2559 *========================================================================*/2560 2561/*2562 * Move the indicated entries from one leaf to another.2563 * NOTE: this routine modifies both source and destination leaves.2564 */2565/*ARGSUSED*/2566STATIC void2567xfs_attr3_leaf_moveents(2568	struct xfs_da_args		*args,2569	struct xfs_attr_leafblock	*leaf_s,2570	struct xfs_attr3_icleaf_hdr	*ichdr_s,2571	int				start_s,2572	struct xfs_attr_leafblock	*leaf_d,2573	struct xfs_attr3_icleaf_hdr	*ichdr_d,2574	int				start_d,2575	int				count)2576{2577	struct xfs_attr_leaf_entry	*entry_s;2578	struct xfs_attr_leaf_entry	*entry_d;2579	int				desti;2580	int				tmp;2581	int				i;2582 2583	/*2584	 * Check for nothing to do.2585	 */2586	if (count == 0)2587		return;2588 2589	/*2590	 * Set up environment.2591	 */2592	ASSERT(ichdr_s->magic == XFS_ATTR_LEAF_MAGIC ||2593	       ichdr_s->magic == XFS_ATTR3_LEAF_MAGIC);2594	ASSERT(ichdr_s->magic == ichdr_d->magic);2595	ASSERT(ichdr_s->count > 0 && ichdr_s->count < args->geo->blksize / 8);2596	ASSERT(ichdr_s->firstused >= (ichdr_s->count * sizeof(*entry_s))2597					+ xfs_attr3_leaf_hdr_size(leaf_s));2598	ASSERT(ichdr_d->count < args->geo->blksize / 8);2599	ASSERT(ichdr_d->firstused >= (ichdr_d->count * sizeof(*entry_d))2600					+ xfs_attr3_leaf_hdr_size(leaf_d));2601 2602	ASSERT(start_s < ichdr_s->count);2603	ASSERT(start_d <= ichdr_d->count);2604	ASSERT(count <= ichdr_s->count);2605 2606 2607	/*2608	 * Move the entries in the destination leaf up to make a hole?2609	 */2610	if (start_d < ichdr_d->count) {2611		tmp  = ichdr_d->count - start_d;2612		tmp *= sizeof(xfs_attr_leaf_entry_t);2613		entry_s = &xfs_attr3_leaf_entryp(leaf_d)[start_d];2614		entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d + count];2615		memmove(entry_d, entry_s, tmp);2616	}2617 2618	/*2619	 * Copy all entry's in the same (sorted) order,2620	 * but allocate attribute info packed and in sequence.2621	 */2622	entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];2623	entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d];2624	desti = start_d;2625	for (i = 0; i < count; entry_s++, entry_d++, desti++, i++) {2626		ASSERT(be16_to_cpu(entry_s->nameidx) >= ichdr_s->firstused);2627		tmp = xfs_attr_leaf_entsize(leaf_s, start_s + i);2628#ifdef GROT2629		/*2630		 * Code to drop INCOMPLETE entries.  Difficult to use as we2631		 * may also need to change the insertion index.  Code turned2632		 * off for 6.2, should be revisited later.2633		 */2634		if (entry_s->flags & XFS_ATTR_INCOMPLETE) { /* skip partials? */2635			memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);2636			ichdr_s->usedbytes -= tmp;2637			ichdr_s->count -= 1;2638			entry_d--;	/* to compensate for ++ in loop hdr */2639			desti--;2640			if ((start_s + i) < offset)2641				result++;	/* insertion index adjustment */2642		} else {2643#endif /* GROT */2644			ichdr_d->firstused -= tmp;2645			/* both on-disk, don't endian flip twice */2646			entry_d->hashval = entry_s->hashval;2647			entry_d->nameidx = cpu_to_be16(ichdr_d->firstused);2648			entry_d->flags = entry_s->flags;2649			ASSERT(be16_to_cpu(entry_d->nameidx) + tmp2650							<= args->geo->blksize);2651			memmove(xfs_attr3_leaf_name(leaf_d, desti),2652				xfs_attr3_leaf_name(leaf_s, start_s + i), tmp);2653			ASSERT(be16_to_cpu(entry_s->nameidx) + tmp2654							<= args->geo->blksize);2655			memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);2656			ichdr_s->usedbytes -= tmp;2657			ichdr_d->usedbytes += tmp;2658			ichdr_s->count -= 1;2659			ichdr_d->count += 1;2660			tmp = ichdr_d->count * sizeof(xfs_attr_leaf_entry_t)2661					+ xfs_attr3_leaf_hdr_size(leaf_d);2662			ASSERT(ichdr_d->firstused >= tmp);2663#ifdef GROT2664		}2665#endif /* GROT */2666	}2667 2668	/*2669	 * Zero out the entries we just copied.2670	 */2671	if (start_s == ichdr_s->count) {2672		tmp = count * sizeof(xfs_attr_leaf_entry_t);2673		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];2674		ASSERT(((char *)entry_s + tmp) <=2675		       ((char *)leaf_s + args->geo->blksize));2676		memset(entry_s, 0, tmp);2677	} else {2678		/*2679		 * Move the remaining entries down to fill the hole,2680		 * then zero the entries at the top.2681		 */2682		tmp  = (ichdr_s->count - count) * sizeof(xfs_attr_leaf_entry_t);2683		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s + count];2684		entry_d = &xfs_attr3_leaf_entryp(leaf_s)[start_s];2685		memmove(entry_d, entry_s, tmp);2686 2687		tmp = count * sizeof(xfs_attr_leaf_entry_t);2688		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[ichdr_s->count];2689		ASSERT(((char *)entry_s + tmp) <=2690		       ((char *)leaf_s + args->geo->blksize));2691		memset(entry_s, 0, tmp);2692	}2693 2694	/*2695	 * Fill in the freemap information2696	 */2697	ichdr_d->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_d);2698	ichdr_d->freemap[0].base += ichdr_d->count * sizeof(xfs_attr_leaf_entry_t);2699	ichdr_d->freemap[0].size = ichdr_d->firstused - ichdr_d->freemap[0].base;2700	ichdr_d->freemap[1].base = 0;2701	ichdr_d->freemap[2].base = 0;2702	ichdr_d->freemap[1].size = 0;2703	ichdr_d->freemap[2].size = 0;2704	ichdr_s->holes = 1;	/* leaf may not be compact */2705}2706 2707/*2708 * Pick up the last hashvalue from a leaf block.2709 */2710xfs_dahash_t2711xfs_attr_leaf_lasthash(2712	struct xfs_buf	*bp,2713	int		*count)2714{2715	struct xfs_attr3_icleaf_hdr ichdr;2716	struct xfs_attr_leaf_entry *entries;2717	struct xfs_mount *mp = bp->b_mount;2718 2719	xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr, bp->b_addr);2720	entries = xfs_attr3_leaf_entryp(bp->b_addr);2721	if (count)2722		*count = ichdr.count;2723	if (!ichdr.count)2724		return 0;2725	return be32_to_cpu(entries[ichdr.count - 1].hashval);2726}2727 2728/*2729 * Calculate the number of bytes used to store the indicated attribute2730 * (whether local or remote only calculate bytes in this block).2731 */2732STATIC int2733xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index)2734{2735	struct xfs_attr_leaf_entry *entries;2736	xfs_attr_leaf_name_local_t *name_loc;2737	xfs_attr_leaf_name_remote_t *name_rmt;2738	int size;2739 2740	entries = xfs_attr3_leaf_entryp(leaf);2741	if (entries[index].flags & XFS_ATTR_LOCAL) {2742		name_loc = xfs_attr3_leaf_name_local(leaf, index);2743		size = xfs_attr_leaf_entsize_local(name_loc->namelen,2744						   be16_to_cpu(name_loc->valuelen));2745	} else {2746		name_rmt = xfs_attr3_leaf_name_remote(leaf, index);2747		size = xfs_attr_leaf_entsize_remote(name_rmt->namelen);2748	}2749	return size;2750}2751 2752/*2753 * Calculate the number of bytes that would be required to store the new2754 * attribute (whether local or remote only calculate bytes in this block).2755 * This routine decides as a side effect whether the attribute will be2756 * a "local" or a "remote" attribute.2757 */2758int2759xfs_attr_leaf_newentsize(2760	struct xfs_da_args	*args,2761	int			*local)2762{2763	int			size;2764 2765	size = xfs_attr_leaf_entsize_local(args->namelen, args->valuelen);2766	if (size < xfs_attr_leaf_entsize_local_max(args->geo->blksize)) {2767		if (local)2768			*local = 1;2769		return size;2770	}2771	if (local)2772		*local = 0;2773	return xfs_attr_leaf_entsize_remote(args->namelen);2774}2775 2776 2777/*========================================================================2778 * Manage the INCOMPLETE flag in a leaf entry2779 *========================================================================*/2780 2781/*2782 * Clear the INCOMPLETE flag on an entry in a leaf block.2783 */2784int2785xfs_attr3_leaf_clearflag(2786	struct xfs_da_args	*args)2787{2788	struct xfs_attr_leafblock *leaf;2789	struct xfs_attr_leaf_entry *entry;2790	struct xfs_attr_leaf_name_remote *name_rmt;2791	struct xfs_buf		*bp;2792	int			error;2793#ifdef DEBUG2794	struct xfs_attr3_icleaf_hdr ichdr;2795	xfs_attr_leaf_name_local_t *name_loc;2796	int namelen;2797	char *name;2798#endif /* DEBUG */2799 2800	trace_xfs_attr_leaf_clearflag(args);2801	/*2802	 * Set up the operation.2803	 */2804	error = xfs_attr3_leaf_read(args->trans, args->dp, args->owner,2805			args->blkno, &bp);2806	if (error)2807		return error;2808 2809	leaf = bp->b_addr;2810	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];2811	ASSERT(entry->flags & XFS_ATTR_INCOMPLETE);2812 2813#ifdef DEBUG2814	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);2815	ASSERT(args->index < ichdr.count);2816	ASSERT(args->index >= 0);2817 2818	if (entry->flags & XFS_ATTR_LOCAL) {2819		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);2820		namelen = name_loc->namelen;2821		name = (char *)name_loc->nameval;2822	} else {2823		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);2824		namelen = name_rmt->namelen;2825		name = (char *)name_rmt->name;2826	}2827	ASSERT(be32_to_cpu(entry->hashval) == args->hashval);2828	ASSERT(namelen == args->namelen);2829	ASSERT(memcmp(name, args->name, namelen) == 0);2830#endif /* DEBUG */2831 2832	entry->flags &= ~XFS_ATTR_INCOMPLETE;2833	xfs_trans_log_buf(args->trans, bp,2834			 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));2835 2836	if (args->rmtblkno) {2837		ASSERT((entry->flags & XFS_ATTR_LOCAL) == 0);2838		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);2839		name_rmt->valueblk = cpu_to_be32(args->rmtblkno);2840		name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);2841		xfs_trans_log_buf(args->trans, bp,2842			 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));2843	}2844 2845	return 0;2846}2847 2848/*2849 * Set the INCOMPLETE flag on an entry in a leaf block.2850 */2851int2852xfs_attr3_leaf_setflag(2853	struct xfs_da_args	*args)2854{2855	struct xfs_attr_leafblock *leaf;2856	struct xfs_attr_leaf_entry *entry;2857	struct xfs_attr_leaf_name_remote *name_rmt;2858	struct xfs_buf		*bp;2859	int error;2860#ifdef DEBUG2861	struct xfs_attr3_icleaf_hdr ichdr;2862#endif2863 2864	trace_xfs_attr_leaf_setflag(args);2865 2866	/*2867	 * Set up the operation.2868	 */2869	error = xfs_attr3_leaf_read(args->trans, args->dp, args->owner,2870			args->blkno, &bp);2871	if (error)2872		return error;2873 2874	leaf = bp->b_addr;2875#ifdef DEBUG2876	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);2877	ASSERT(args->index < ichdr.count);2878	ASSERT(args->index >= 0);2879#endif2880	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];2881 2882	ASSERT((entry->flags & XFS_ATTR_INCOMPLETE) == 0);2883	entry->flags |= XFS_ATTR_INCOMPLETE;2884	xfs_trans_log_buf(args->trans, bp,2885			XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));2886	if ((entry->flags & XFS_ATTR_LOCAL) == 0) {2887		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);2888		name_rmt->valueblk = 0;2889		name_rmt->valuelen = 0;2890		xfs_trans_log_buf(args->trans, bp,2891			 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));2892	}2893 2894	return 0;2895}2896 2897/*2898 * In a single transaction, clear the INCOMPLETE flag on the leaf entry2899 * given by args->blkno/index and set the INCOMPLETE flag on the leaf2900 * entry given by args->blkno2/index2.2901 *2902 * Note that they could be in different blocks, or in the same block.2903 */2904int2905xfs_attr3_leaf_flipflags(2906	struct xfs_da_args	*args)2907{2908	struct xfs_attr_leafblock *leaf1;2909	struct xfs_attr_leafblock *leaf2;2910	struct xfs_attr_leaf_entry *entry1;2911	struct xfs_attr_leaf_entry *entry2;2912	struct xfs_attr_leaf_name_remote *name_rmt;2913	struct xfs_buf		*bp1;2914	struct xfs_buf		*bp2;2915	int error;2916#ifdef DEBUG2917	struct xfs_attr3_icleaf_hdr ichdr1;2918	struct xfs_attr3_icleaf_hdr ichdr2;2919	xfs_attr_leaf_name_local_t *name_loc;2920	int namelen1, namelen2;2921	char *name1, *name2;2922#endif /* DEBUG */2923 2924	trace_xfs_attr_leaf_flipflags(args);2925 2926	/*2927	 * Read the block containing the "old" attr2928	 */2929	error = xfs_attr3_leaf_read(args->trans, args->dp, args->owner,2930			args->blkno, &bp1);2931	if (error)2932		return error;2933 2934	/*2935	 * Read the block containing the "new" attr, if it is different2936	 */2937	if (args->blkno2 != args->blkno) {2938		error = xfs_attr3_leaf_read(args->trans, args->dp, args->owner,2939				args->blkno2, &bp2);2940		if (error)2941			return error;2942	} else {2943		bp2 = bp1;2944	}2945 2946	leaf1 = bp1->b_addr;2947	entry1 = &xfs_attr3_leaf_entryp(leaf1)[args->index];2948 2949	leaf2 = bp2->b_addr;2950	entry2 = &xfs_attr3_leaf_entryp(leaf2)[args->index2];2951 2952#ifdef DEBUG2953	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr1, leaf1);2954	ASSERT(args->index < ichdr1.count);2955	ASSERT(args->index >= 0);2956 2957	xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr2, leaf2);2958	ASSERT(args->index2 < ichdr2.count);2959	ASSERT(args->index2 >= 0);2960 2961	if (entry1->flags & XFS_ATTR_LOCAL) {2962		name_loc = xfs_attr3_leaf_name_local(leaf1, args->index);2963		namelen1 = name_loc->namelen;2964		name1 = (char *)name_loc->nameval;2965	} else {2966		name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);2967		namelen1 = name_rmt->namelen;2968		name1 = (char *)name_rmt->name;2969	}2970	if (entry2->flags & XFS_ATTR_LOCAL) {2971		name_loc = xfs_attr3_leaf_name_local(leaf2, args->index2);2972		namelen2 = name_loc->namelen;2973		name2 = (char *)name_loc->nameval;2974	} else {2975		name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);2976		namelen2 = name_rmt->namelen;2977		name2 = (char *)name_rmt->name;2978	}2979	ASSERT(be32_to_cpu(entry1->hashval) == be32_to_cpu(entry2->hashval));2980	ASSERT(namelen1 == namelen2);2981	ASSERT(memcmp(name1, name2, namelen1) == 0);2982#endif /* DEBUG */2983 2984	ASSERT(entry1->flags & XFS_ATTR_INCOMPLETE);2985	ASSERT((entry2->flags & XFS_ATTR_INCOMPLETE) == 0);2986 2987	entry1->flags &= ~XFS_ATTR_INCOMPLETE;2988	xfs_trans_log_buf(args->trans, bp1,2989			  XFS_DA_LOGRANGE(leaf1, entry1, sizeof(*entry1)));2990	if (args->rmtblkno) {2991		ASSERT((entry1->flags & XFS_ATTR_LOCAL) == 0);2992		name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);2993		name_rmt->valueblk = cpu_to_be32(args->rmtblkno);2994		name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);2995		xfs_trans_log_buf(args->trans, bp1,2996			 XFS_DA_LOGRANGE(leaf1, name_rmt, sizeof(*name_rmt)));2997	}2998 2999	entry2->flags |= XFS_ATTR_INCOMPLETE;3000	xfs_trans_log_buf(args->trans, bp2,3001			  XFS_DA_LOGRANGE(leaf2, entry2, sizeof(*entry2)));3002	if ((entry2->flags & XFS_ATTR_LOCAL) == 0) {3003		name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);3004		name_rmt->valueblk = 0;3005		name_rmt->valuelen = 0;3006		xfs_trans_log_buf(args->trans, bp2,3007			 XFS_DA_LOGRANGE(leaf2, name_rmt, sizeof(*name_rmt)));3008	}3009 3010	return 0;3011}3012