xref: /openbmc/linux/fs/xfs/libxfs/xfs_attr_leaf.c (revision c819e2cf)
1 /*
2  * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3  * Copyright (c) 2013 Red Hat, Inc.
4  * All Rights Reserved.
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License as
8  * published by the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it would be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write the Free Software Foundation,
17  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18  */
19 #include "xfs.h"
20 #include "xfs_fs.h"
21 #include "xfs_shared.h"
22 #include "xfs_format.h"
23 #include "xfs_log_format.h"
24 #include "xfs_trans_resv.h"
25 #include "xfs_bit.h"
26 #include "xfs_sb.h"
27 #include "xfs_mount.h"
28 #include "xfs_da_format.h"
29 #include "xfs_da_btree.h"
30 #include "xfs_inode.h"
31 #include "xfs_trans.h"
32 #include "xfs_inode_item.h"
33 #include "xfs_bmap_btree.h"
34 #include "xfs_bmap.h"
35 #include "xfs_attr_sf.h"
36 #include "xfs_attr_remote.h"
37 #include "xfs_attr.h"
38 #include "xfs_attr_leaf.h"
39 #include "xfs_error.h"
40 #include "xfs_trace.h"
41 #include "xfs_buf_item.h"
42 #include "xfs_cksum.h"
43 #include "xfs_dir2.h"
44 
45 
46 /*
47  * xfs_attr_leaf.c
48  *
49  * Routines to implement leaf blocks of attributes as Btrees of hashed names.
50  */
51 
52 /*========================================================================
53  * Function prototypes for the kernel.
54  *========================================================================*/
55 
56 /*
57  * Routines used for growing the Btree.
58  */
59 STATIC int xfs_attr3_leaf_create(struct xfs_da_args *args,
60 				 xfs_dablk_t which_block, struct xfs_buf **bpp);
61 STATIC int xfs_attr3_leaf_add_work(struct xfs_buf *leaf_buffer,
62 				   struct xfs_attr3_icleaf_hdr *ichdr,
63 				   struct xfs_da_args *args, int freemap_index);
64 STATIC void xfs_attr3_leaf_compact(struct xfs_da_args *args,
65 				   struct xfs_attr3_icleaf_hdr *ichdr,
66 				   struct xfs_buf *leaf_buffer);
67 STATIC void xfs_attr3_leaf_rebalance(xfs_da_state_t *state,
68 						   xfs_da_state_blk_t *blk1,
69 						   xfs_da_state_blk_t *blk2);
70 STATIC int xfs_attr3_leaf_figure_balance(xfs_da_state_t *state,
71 			xfs_da_state_blk_t *leaf_blk_1,
72 			struct xfs_attr3_icleaf_hdr *ichdr1,
73 			xfs_da_state_blk_t *leaf_blk_2,
74 			struct xfs_attr3_icleaf_hdr *ichdr2,
75 			int *number_entries_in_blk1,
76 			int *number_usedbytes_in_blk1);
77 
78 /*
79  * Utility routines.
80  */
81 STATIC void xfs_attr3_leaf_moveents(struct xfs_da_args *args,
82 			struct xfs_attr_leafblock *src_leaf,
83 			struct xfs_attr3_icleaf_hdr *src_ichdr, int src_start,
84 			struct xfs_attr_leafblock *dst_leaf,
85 			struct xfs_attr3_icleaf_hdr *dst_ichdr, int dst_start,
86 			int move_count);
87 STATIC int xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index);
88 
89 void
90 xfs_attr3_leaf_hdr_from_disk(
91 	struct xfs_attr3_icleaf_hdr	*to,
92 	struct xfs_attr_leafblock	*from)
93 {
94 	int	i;
95 
96 	ASSERT(from->hdr.info.magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
97 	       from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
98 
99 	if (from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC)) {
100 		struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)from;
101 
102 		to->forw = be32_to_cpu(hdr3->info.hdr.forw);
103 		to->back = be32_to_cpu(hdr3->info.hdr.back);
104 		to->magic = be16_to_cpu(hdr3->info.hdr.magic);
105 		to->count = be16_to_cpu(hdr3->count);
106 		to->usedbytes = be16_to_cpu(hdr3->usedbytes);
107 		to->firstused = be16_to_cpu(hdr3->firstused);
108 		to->holes = hdr3->holes;
109 
110 		for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
111 			to->freemap[i].base = be16_to_cpu(hdr3->freemap[i].base);
112 			to->freemap[i].size = be16_to_cpu(hdr3->freemap[i].size);
113 		}
114 		return;
115 	}
116 	to->forw = be32_to_cpu(from->hdr.info.forw);
117 	to->back = be32_to_cpu(from->hdr.info.back);
118 	to->magic = be16_to_cpu(from->hdr.info.magic);
119 	to->count = be16_to_cpu(from->hdr.count);
120 	to->usedbytes = be16_to_cpu(from->hdr.usedbytes);
121 	to->firstused = be16_to_cpu(from->hdr.firstused);
122 	to->holes = from->hdr.holes;
123 
124 	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
125 		to->freemap[i].base = be16_to_cpu(from->hdr.freemap[i].base);
126 		to->freemap[i].size = be16_to_cpu(from->hdr.freemap[i].size);
127 	}
128 }
129 
130 void
131 xfs_attr3_leaf_hdr_to_disk(
132 	struct xfs_attr_leafblock	*to,
133 	struct xfs_attr3_icleaf_hdr	*from)
134 {
135 	int	i;
136 
137 	ASSERT(from->magic == XFS_ATTR_LEAF_MAGIC ||
138 	       from->magic == XFS_ATTR3_LEAF_MAGIC);
139 
140 	if (from->magic == XFS_ATTR3_LEAF_MAGIC) {
141 		struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)to;
142 
143 		hdr3->info.hdr.forw = cpu_to_be32(from->forw);
144 		hdr3->info.hdr.back = cpu_to_be32(from->back);
145 		hdr3->info.hdr.magic = cpu_to_be16(from->magic);
146 		hdr3->count = cpu_to_be16(from->count);
147 		hdr3->usedbytes = cpu_to_be16(from->usedbytes);
148 		hdr3->firstused = cpu_to_be16(from->firstused);
149 		hdr3->holes = from->holes;
150 		hdr3->pad1 = 0;
151 
152 		for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
153 			hdr3->freemap[i].base = cpu_to_be16(from->freemap[i].base);
154 			hdr3->freemap[i].size = cpu_to_be16(from->freemap[i].size);
155 		}
156 		return;
157 	}
158 	to->hdr.info.forw = cpu_to_be32(from->forw);
159 	to->hdr.info.back = cpu_to_be32(from->back);
160 	to->hdr.info.magic = cpu_to_be16(from->magic);
161 	to->hdr.count = cpu_to_be16(from->count);
162 	to->hdr.usedbytes = cpu_to_be16(from->usedbytes);
163 	to->hdr.firstused = cpu_to_be16(from->firstused);
164 	to->hdr.holes = from->holes;
165 	to->hdr.pad1 = 0;
166 
167 	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
168 		to->hdr.freemap[i].base = cpu_to_be16(from->freemap[i].base);
169 		to->hdr.freemap[i].size = cpu_to_be16(from->freemap[i].size);
170 	}
171 }
172 
173 static bool
174 xfs_attr3_leaf_verify(
175 	struct xfs_buf		*bp)
176 {
177 	struct xfs_mount	*mp = bp->b_target->bt_mount;
178 	struct xfs_attr_leafblock *leaf = bp->b_addr;
179 	struct xfs_attr3_icleaf_hdr ichdr;
180 
181 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
182 
183 	if (xfs_sb_version_hascrc(&mp->m_sb)) {
184 		struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
185 
186 		if (ichdr.magic != XFS_ATTR3_LEAF_MAGIC)
187 			return false;
188 
189 		if (!uuid_equal(&hdr3->info.uuid, &mp->m_sb.sb_uuid))
190 			return false;
191 		if (be64_to_cpu(hdr3->info.blkno) != bp->b_bn)
192 			return false;
193 	} else {
194 		if (ichdr.magic != XFS_ATTR_LEAF_MAGIC)
195 			return false;
196 	}
197 	if (ichdr.count == 0)
198 		return false;
199 
200 	/* XXX: need to range check rest of attr header values */
201 	/* XXX: hash order check? */
202 
203 	return true;
204 }
205 
206 static void
207 xfs_attr3_leaf_write_verify(
208 	struct xfs_buf	*bp)
209 {
210 	struct xfs_mount	*mp = bp->b_target->bt_mount;
211 	struct xfs_buf_log_item	*bip = bp->b_fspriv;
212 	struct xfs_attr3_leaf_hdr *hdr3 = bp->b_addr;
213 
214 	if (!xfs_attr3_leaf_verify(bp)) {
215 		xfs_buf_ioerror(bp, -EFSCORRUPTED);
216 		xfs_verifier_error(bp);
217 		return;
218 	}
219 
220 	if (!xfs_sb_version_hascrc(&mp->m_sb))
221 		return;
222 
223 	if (bip)
224 		hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
225 
226 	xfs_buf_update_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF);
227 }
228 
229 /*
230  * leaf/node format detection on trees is sketchy, so a node read can be done on
231  * leaf level blocks when detection identifies the tree as a node format tree
232  * incorrectly. In this case, we need to swap the verifier to match the correct
233  * format of the block being read.
234  */
235 static void
236 xfs_attr3_leaf_read_verify(
237 	struct xfs_buf		*bp)
238 {
239 	struct xfs_mount	*mp = bp->b_target->bt_mount;
240 
241 	if (xfs_sb_version_hascrc(&mp->m_sb) &&
242 	     !xfs_buf_verify_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF))
243 		xfs_buf_ioerror(bp, -EFSBADCRC);
244 	else if (!xfs_attr3_leaf_verify(bp))
245 		xfs_buf_ioerror(bp, -EFSCORRUPTED);
246 
247 	if (bp->b_error)
248 		xfs_verifier_error(bp);
249 }
250 
251 const struct xfs_buf_ops xfs_attr3_leaf_buf_ops = {
252 	.verify_read = xfs_attr3_leaf_read_verify,
253 	.verify_write = xfs_attr3_leaf_write_verify,
254 };
255 
256 int
257 xfs_attr3_leaf_read(
258 	struct xfs_trans	*tp,
259 	struct xfs_inode	*dp,
260 	xfs_dablk_t		bno,
261 	xfs_daddr_t		mappedbno,
262 	struct xfs_buf		**bpp)
263 {
264 	int			err;
265 
266 	err = xfs_da_read_buf(tp, dp, bno, mappedbno, bpp,
267 				XFS_ATTR_FORK, &xfs_attr3_leaf_buf_ops);
268 	if (!err && tp)
269 		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_ATTR_LEAF_BUF);
270 	return err;
271 }
272 
273 /*========================================================================
274  * Namespace helper routines
275  *========================================================================*/
276 
277 /*
278  * If namespace bits don't match return 0.
279  * If all match then return 1.
280  */
281 STATIC int
282 xfs_attr_namesp_match(int arg_flags, int ondisk_flags)
283 {
284 	return XFS_ATTR_NSP_ONDISK(ondisk_flags) == XFS_ATTR_NSP_ARGS_TO_ONDISK(arg_flags);
285 }
286 
287 
288 /*========================================================================
289  * External routines when attribute fork size < XFS_LITINO(mp).
290  *========================================================================*/
291 
292 /*
293  * Query whether the requested number of additional bytes of extended
294  * attribute space will be able to fit inline.
295  *
296  * Returns zero if not, else the di_forkoff fork offset to be used in the
297  * literal area for attribute data once the new bytes have been added.
298  *
299  * di_forkoff must be 8 byte aligned, hence is stored as a >>3 value;
300  * special case for dev/uuid inodes, they have fixed size data forks.
301  */
302 int
303 xfs_attr_shortform_bytesfit(xfs_inode_t *dp, int bytes)
304 {
305 	int offset;
306 	int minforkoff;	/* lower limit on valid forkoff locations */
307 	int maxforkoff;	/* upper limit on valid forkoff locations */
308 	int dsize;
309 	xfs_mount_t *mp = dp->i_mount;
310 
311 	/* rounded down */
312 	offset = (XFS_LITINO(mp, dp->i_d.di_version) - bytes) >> 3;
313 
314 	switch (dp->i_d.di_format) {
315 	case XFS_DINODE_FMT_DEV:
316 		minforkoff = roundup(sizeof(xfs_dev_t), 8) >> 3;
317 		return (offset >= minforkoff) ? minforkoff : 0;
318 	case XFS_DINODE_FMT_UUID:
319 		minforkoff = roundup(sizeof(uuid_t), 8) >> 3;
320 		return (offset >= minforkoff) ? minforkoff : 0;
321 	}
322 
323 	/*
324 	 * If the requested numbers of bytes is smaller or equal to the
325 	 * current attribute fork size we can always proceed.
326 	 *
327 	 * Note that if_bytes in the data fork might actually be larger than
328 	 * the current data fork size is due to delalloc extents. In that
329 	 * case either the extent count will go down when they are converted
330 	 * to real extents, or the delalloc conversion will take care of the
331 	 * literal area rebalancing.
332 	 */
333 	if (bytes <= XFS_IFORK_ASIZE(dp))
334 		return dp->i_d.di_forkoff;
335 
336 	/*
337 	 * For attr2 we can try to move the forkoff if there is space in the
338 	 * literal area, but for the old format we are done if there is no
339 	 * space in the fixed attribute fork.
340 	 */
341 	if (!(mp->m_flags & XFS_MOUNT_ATTR2))
342 		return 0;
343 
344 	dsize = dp->i_df.if_bytes;
345 
346 	switch (dp->i_d.di_format) {
347 	case XFS_DINODE_FMT_EXTENTS:
348 		/*
349 		 * If there is no attr fork and the data fork is extents,
350 		 * determine if creating the default attr fork will result
351 		 * in the extents form migrating to btree. If so, the
352 		 * minimum offset only needs to be the space required for
353 		 * the btree root.
354 		 */
355 		if (!dp->i_d.di_forkoff && dp->i_df.if_bytes >
356 		    xfs_default_attroffset(dp))
357 			dsize = XFS_BMDR_SPACE_CALC(MINDBTPTRS);
358 		break;
359 	case XFS_DINODE_FMT_BTREE:
360 		/*
361 		 * If we have a data btree then keep forkoff if we have one,
362 		 * otherwise we are adding a new attr, so then we set
363 		 * minforkoff to where the btree root can finish so we have
364 		 * plenty of room for attrs
365 		 */
366 		if (dp->i_d.di_forkoff) {
367 			if (offset < dp->i_d.di_forkoff)
368 				return 0;
369 			return dp->i_d.di_forkoff;
370 		}
371 		dsize = XFS_BMAP_BROOT_SPACE(mp, dp->i_df.if_broot);
372 		break;
373 	}
374 
375 	/*
376 	 * A data fork btree root must have space for at least
377 	 * MINDBTPTRS key/ptr pairs if the data fork is small or empty.
378 	 */
379 	minforkoff = MAX(dsize, XFS_BMDR_SPACE_CALC(MINDBTPTRS));
380 	minforkoff = roundup(minforkoff, 8) >> 3;
381 
382 	/* attr fork btree root can have at least this many key/ptr pairs */
383 	maxforkoff = XFS_LITINO(mp, dp->i_d.di_version) -
384 			XFS_BMDR_SPACE_CALC(MINABTPTRS);
385 	maxforkoff = maxforkoff >> 3;	/* rounded down */
386 
387 	if (offset >= maxforkoff)
388 		return maxforkoff;
389 	if (offset >= minforkoff)
390 		return offset;
391 	return 0;
392 }
393 
394 /*
395  * Switch on the ATTR2 superblock bit (implies also FEATURES2)
396  */
397 STATIC void
398 xfs_sbversion_add_attr2(xfs_mount_t *mp, xfs_trans_t *tp)
399 {
400 	if ((mp->m_flags & XFS_MOUNT_ATTR2) &&
401 	    !(xfs_sb_version_hasattr2(&mp->m_sb))) {
402 		spin_lock(&mp->m_sb_lock);
403 		if (!xfs_sb_version_hasattr2(&mp->m_sb)) {
404 			xfs_sb_version_addattr2(&mp->m_sb);
405 			spin_unlock(&mp->m_sb_lock);
406 			xfs_mod_sb(tp, XFS_SB_VERSIONNUM | XFS_SB_FEATURES2);
407 		} else
408 			spin_unlock(&mp->m_sb_lock);
409 	}
410 }
411 
412 /*
413  * Create the initial contents of a shortform attribute list.
414  */
415 void
416 xfs_attr_shortform_create(xfs_da_args_t *args)
417 {
418 	xfs_attr_sf_hdr_t *hdr;
419 	xfs_inode_t *dp;
420 	xfs_ifork_t *ifp;
421 
422 	trace_xfs_attr_sf_create(args);
423 
424 	dp = args->dp;
425 	ASSERT(dp != NULL);
426 	ifp = dp->i_afp;
427 	ASSERT(ifp != NULL);
428 	ASSERT(ifp->if_bytes == 0);
429 	if (dp->i_d.di_aformat == XFS_DINODE_FMT_EXTENTS) {
430 		ifp->if_flags &= ~XFS_IFEXTENTS;	/* just in case */
431 		dp->i_d.di_aformat = XFS_DINODE_FMT_LOCAL;
432 		ifp->if_flags |= XFS_IFINLINE;
433 	} else {
434 		ASSERT(ifp->if_flags & XFS_IFINLINE);
435 	}
436 	xfs_idata_realloc(dp, sizeof(*hdr), XFS_ATTR_FORK);
437 	hdr = (xfs_attr_sf_hdr_t *)ifp->if_u1.if_data;
438 	hdr->count = 0;
439 	hdr->totsize = cpu_to_be16(sizeof(*hdr));
440 	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
441 }
442 
443 /*
444  * Add a name/value pair to the shortform attribute list.
445  * Overflow from the inode has already been checked for.
446  */
447 void
448 xfs_attr_shortform_add(xfs_da_args_t *args, int forkoff)
449 {
450 	xfs_attr_shortform_t *sf;
451 	xfs_attr_sf_entry_t *sfe;
452 	int i, offset, size;
453 	xfs_mount_t *mp;
454 	xfs_inode_t *dp;
455 	xfs_ifork_t *ifp;
456 
457 	trace_xfs_attr_sf_add(args);
458 
459 	dp = args->dp;
460 	mp = dp->i_mount;
461 	dp->i_d.di_forkoff = forkoff;
462 
463 	ifp = dp->i_afp;
464 	ASSERT(ifp->if_flags & XFS_IFINLINE);
465 	sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
466 	sfe = &sf->list[0];
467 	for (i = 0; i < sf->hdr.count; sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
468 #ifdef DEBUG
469 		if (sfe->namelen != args->namelen)
470 			continue;
471 		if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
472 			continue;
473 		if (!xfs_attr_namesp_match(args->flags, sfe->flags))
474 			continue;
475 		ASSERT(0);
476 #endif
477 	}
478 
479 	offset = (char *)sfe - (char *)sf;
480 	size = XFS_ATTR_SF_ENTSIZE_BYNAME(args->namelen, args->valuelen);
481 	xfs_idata_realloc(dp, size, XFS_ATTR_FORK);
482 	sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
483 	sfe = (xfs_attr_sf_entry_t *)((char *)sf + offset);
484 
485 	sfe->namelen = args->namelen;
486 	sfe->valuelen = args->valuelen;
487 	sfe->flags = XFS_ATTR_NSP_ARGS_TO_ONDISK(args->flags);
488 	memcpy(sfe->nameval, args->name, args->namelen);
489 	memcpy(&sfe->nameval[args->namelen], args->value, args->valuelen);
490 	sf->hdr.count++;
491 	be16_add_cpu(&sf->hdr.totsize, size);
492 	xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
493 
494 	xfs_sbversion_add_attr2(mp, args->trans);
495 }
496 
497 /*
498  * After the last attribute is removed revert to original inode format,
499  * making all literal area available to the data fork once more.
500  */
501 STATIC void
502 xfs_attr_fork_reset(
503 	struct xfs_inode	*ip,
504 	struct xfs_trans	*tp)
505 {
506 	xfs_idestroy_fork(ip, XFS_ATTR_FORK);
507 	ip->i_d.di_forkoff = 0;
508 	ip->i_d.di_aformat = XFS_DINODE_FMT_EXTENTS;
509 
510 	ASSERT(ip->i_d.di_anextents == 0);
511 	ASSERT(ip->i_afp == NULL);
512 
513 	xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
514 }
515 
516 /*
517  * Remove an attribute from the shortform attribute list structure.
518  */
519 int
520 xfs_attr_shortform_remove(xfs_da_args_t *args)
521 {
522 	xfs_attr_shortform_t *sf;
523 	xfs_attr_sf_entry_t *sfe;
524 	int base, size=0, end, totsize, i;
525 	xfs_mount_t *mp;
526 	xfs_inode_t *dp;
527 
528 	trace_xfs_attr_sf_remove(args);
529 
530 	dp = args->dp;
531 	mp = dp->i_mount;
532 	base = sizeof(xfs_attr_sf_hdr_t);
533 	sf = (xfs_attr_shortform_t *)dp->i_afp->if_u1.if_data;
534 	sfe = &sf->list[0];
535 	end = sf->hdr.count;
536 	for (i = 0; i < end; sfe = XFS_ATTR_SF_NEXTENTRY(sfe),
537 					base += size, i++) {
538 		size = XFS_ATTR_SF_ENTSIZE(sfe);
539 		if (sfe->namelen != args->namelen)
540 			continue;
541 		if (memcmp(sfe->nameval, args->name, args->namelen) != 0)
542 			continue;
543 		if (!xfs_attr_namesp_match(args->flags, sfe->flags))
544 			continue;
545 		break;
546 	}
547 	if (i == end)
548 		return -ENOATTR;
549 
550 	/*
551 	 * Fix up the attribute fork data, covering the hole
552 	 */
553 	end = base + size;
554 	totsize = be16_to_cpu(sf->hdr.totsize);
555 	if (end != totsize)
556 		memmove(&((char *)sf)[base], &((char *)sf)[end], totsize - end);
557 	sf->hdr.count--;
558 	be16_add_cpu(&sf->hdr.totsize, -size);
559 
560 	/*
561 	 * Fix up the start offset of the attribute fork
562 	 */
563 	totsize -= size;
564 	if (totsize == sizeof(xfs_attr_sf_hdr_t) &&
565 	    (mp->m_flags & XFS_MOUNT_ATTR2) &&
566 	    (dp->i_d.di_format != XFS_DINODE_FMT_BTREE) &&
567 	    !(args->op_flags & XFS_DA_OP_ADDNAME)) {
568 		xfs_attr_fork_reset(dp, args->trans);
569 	} else {
570 		xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
571 		dp->i_d.di_forkoff = xfs_attr_shortform_bytesfit(dp, totsize);
572 		ASSERT(dp->i_d.di_forkoff);
573 		ASSERT(totsize > sizeof(xfs_attr_sf_hdr_t) ||
574 				(args->op_flags & XFS_DA_OP_ADDNAME) ||
575 				!(mp->m_flags & XFS_MOUNT_ATTR2) ||
576 				dp->i_d.di_format == XFS_DINODE_FMT_BTREE);
577 		xfs_trans_log_inode(args->trans, dp,
578 					XFS_ILOG_CORE | XFS_ILOG_ADATA);
579 	}
580 
581 	xfs_sbversion_add_attr2(mp, args->trans);
582 
583 	return 0;
584 }
585 
586 /*
587  * Look up a name in a shortform attribute list structure.
588  */
589 /*ARGSUSED*/
590 int
591 xfs_attr_shortform_lookup(xfs_da_args_t *args)
592 {
593 	xfs_attr_shortform_t *sf;
594 	xfs_attr_sf_entry_t *sfe;
595 	int i;
596 	xfs_ifork_t *ifp;
597 
598 	trace_xfs_attr_sf_lookup(args);
599 
600 	ifp = args->dp->i_afp;
601 	ASSERT(ifp->if_flags & XFS_IFINLINE);
602 	sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
603 	sfe = &sf->list[0];
604 	for (i = 0; i < sf->hdr.count;
605 				sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
606 		if (sfe->namelen != args->namelen)
607 			continue;
608 		if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
609 			continue;
610 		if (!xfs_attr_namesp_match(args->flags, sfe->flags))
611 			continue;
612 		return -EEXIST;
613 	}
614 	return -ENOATTR;
615 }
616 
617 /*
618  * Look up a name in a shortform attribute list structure.
619  */
620 /*ARGSUSED*/
621 int
622 xfs_attr_shortform_getvalue(xfs_da_args_t *args)
623 {
624 	xfs_attr_shortform_t *sf;
625 	xfs_attr_sf_entry_t *sfe;
626 	int i;
627 
628 	ASSERT(args->dp->i_afp->if_flags == XFS_IFINLINE);
629 	sf = (xfs_attr_shortform_t *)args->dp->i_afp->if_u1.if_data;
630 	sfe = &sf->list[0];
631 	for (i = 0; i < sf->hdr.count;
632 				sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
633 		if (sfe->namelen != args->namelen)
634 			continue;
635 		if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
636 			continue;
637 		if (!xfs_attr_namesp_match(args->flags, sfe->flags))
638 			continue;
639 		if (args->flags & ATTR_KERNOVAL) {
640 			args->valuelen = sfe->valuelen;
641 			return -EEXIST;
642 		}
643 		if (args->valuelen < sfe->valuelen) {
644 			args->valuelen = sfe->valuelen;
645 			return -ERANGE;
646 		}
647 		args->valuelen = sfe->valuelen;
648 		memcpy(args->value, &sfe->nameval[args->namelen],
649 						    args->valuelen);
650 		return -EEXIST;
651 	}
652 	return -ENOATTR;
653 }
654 
655 /*
656  * Convert from using the shortform to the leaf.
657  */
658 int
659 xfs_attr_shortform_to_leaf(xfs_da_args_t *args)
660 {
661 	xfs_inode_t *dp;
662 	xfs_attr_shortform_t *sf;
663 	xfs_attr_sf_entry_t *sfe;
664 	xfs_da_args_t nargs;
665 	char *tmpbuffer;
666 	int error, i, size;
667 	xfs_dablk_t blkno;
668 	struct xfs_buf *bp;
669 	xfs_ifork_t *ifp;
670 
671 	trace_xfs_attr_sf_to_leaf(args);
672 
673 	dp = args->dp;
674 	ifp = dp->i_afp;
675 	sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
676 	size = be16_to_cpu(sf->hdr.totsize);
677 	tmpbuffer = kmem_alloc(size, KM_SLEEP);
678 	ASSERT(tmpbuffer != NULL);
679 	memcpy(tmpbuffer, ifp->if_u1.if_data, size);
680 	sf = (xfs_attr_shortform_t *)tmpbuffer;
681 
682 	xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
683 	xfs_bmap_local_to_extents_empty(dp, XFS_ATTR_FORK);
684 
685 	bp = NULL;
686 	error = xfs_da_grow_inode(args, &blkno);
687 	if (error) {
688 		/*
689 		 * If we hit an IO error middle of the transaction inside
690 		 * grow_inode(), we may have inconsistent data. Bail out.
691 		 */
692 		if (error == -EIO)
693 			goto out;
694 		xfs_idata_realloc(dp, size, XFS_ATTR_FORK);	/* try to put */
695 		memcpy(ifp->if_u1.if_data, tmpbuffer, size);	/* it back */
696 		goto out;
697 	}
698 
699 	ASSERT(blkno == 0);
700 	error = xfs_attr3_leaf_create(args, blkno, &bp);
701 	if (error) {
702 		error = xfs_da_shrink_inode(args, 0, bp);
703 		bp = NULL;
704 		if (error)
705 			goto out;
706 		xfs_idata_realloc(dp, size, XFS_ATTR_FORK);	/* try to put */
707 		memcpy(ifp->if_u1.if_data, tmpbuffer, size);	/* it back */
708 		goto out;
709 	}
710 
711 	memset((char *)&nargs, 0, sizeof(nargs));
712 	nargs.dp = dp;
713 	nargs.geo = args->geo;
714 	nargs.firstblock = args->firstblock;
715 	nargs.flist = args->flist;
716 	nargs.total = args->total;
717 	nargs.whichfork = XFS_ATTR_FORK;
718 	nargs.trans = args->trans;
719 	nargs.op_flags = XFS_DA_OP_OKNOENT;
720 
721 	sfe = &sf->list[0];
722 	for (i = 0; i < sf->hdr.count; i++) {
723 		nargs.name = sfe->nameval;
724 		nargs.namelen = sfe->namelen;
725 		nargs.value = &sfe->nameval[nargs.namelen];
726 		nargs.valuelen = sfe->valuelen;
727 		nargs.hashval = xfs_da_hashname(sfe->nameval,
728 						sfe->namelen);
729 		nargs.flags = XFS_ATTR_NSP_ONDISK_TO_ARGS(sfe->flags);
730 		error = xfs_attr3_leaf_lookup_int(bp, &nargs); /* set a->index */
731 		ASSERT(error == -ENOATTR);
732 		error = xfs_attr3_leaf_add(bp, &nargs);
733 		ASSERT(error != -ENOSPC);
734 		if (error)
735 			goto out;
736 		sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
737 	}
738 	error = 0;
739 
740 out:
741 	kmem_free(tmpbuffer);
742 	return error;
743 }
744 
745 /*
746  * Check a leaf attribute block to see if all the entries would fit into
747  * a shortform attribute list.
748  */
749 int
750 xfs_attr_shortform_allfit(
751 	struct xfs_buf		*bp,
752 	struct xfs_inode	*dp)
753 {
754 	struct xfs_attr_leafblock *leaf;
755 	struct xfs_attr_leaf_entry *entry;
756 	xfs_attr_leaf_name_local_t *name_loc;
757 	struct xfs_attr3_icleaf_hdr leafhdr;
758 	int			bytes;
759 	int			i;
760 
761 	leaf = bp->b_addr;
762 	xfs_attr3_leaf_hdr_from_disk(&leafhdr, leaf);
763 	entry = xfs_attr3_leaf_entryp(leaf);
764 
765 	bytes = sizeof(struct xfs_attr_sf_hdr);
766 	for (i = 0; i < leafhdr.count; entry++, i++) {
767 		if (entry->flags & XFS_ATTR_INCOMPLETE)
768 			continue;		/* don't copy partial entries */
769 		if (!(entry->flags & XFS_ATTR_LOCAL))
770 			return 0;
771 		name_loc = xfs_attr3_leaf_name_local(leaf, i);
772 		if (name_loc->namelen >= XFS_ATTR_SF_ENTSIZE_MAX)
773 			return 0;
774 		if (be16_to_cpu(name_loc->valuelen) >= XFS_ATTR_SF_ENTSIZE_MAX)
775 			return 0;
776 		bytes += sizeof(struct xfs_attr_sf_entry) - 1
777 				+ name_loc->namelen
778 				+ be16_to_cpu(name_loc->valuelen);
779 	}
780 	if ((dp->i_mount->m_flags & XFS_MOUNT_ATTR2) &&
781 	    (dp->i_d.di_format != XFS_DINODE_FMT_BTREE) &&
782 	    (bytes == sizeof(struct xfs_attr_sf_hdr)))
783 		return -1;
784 	return xfs_attr_shortform_bytesfit(dp, bytes);
785 }
786 
787 /*
788  * Convert a leaf attribute list to shortform attribute list
789  */
790 int
791 xfs_attr3_leaf_to_shortform(
792 	struct xfs_buf		*bp,
793 	struct xfs_da_args	*args,
794 	int			forkoff)
795 {
796 	struct xfs_attr_leafblock *leaf;
797 	struct xfs_attr3_icleaf_hdr ichdr;
798 	struct xfs_attr_leaf_entry *entry;
799 	struct xfs_attr_leaf_name_local *name_loc;
800 	struct xfs_da_args	nargs;
801 	struct xfs_inode	*dp = args->dp;
802 	char			*tmpbuffer;
803 	int			error;
804 	int			i;
805 
806 	trace_xfs_attr_leaf_to_sf(args);
807 
808 	tmpbuffer = kmem_alloc(args->geo->blksize, KM_SLEEP);
809 	if (!tmpbuffer)
810 		return -ENOMEM;
811 
812 	memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);
813 
814 	leaf = (xfs_attr_leafblock_t *)tmpbuffer;
815 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
816 	entry = xfs_attr3_leaf_entryp(leaf);
817 
818 	/* XXX (dgc): buffer is about to be marked stale - why zero it? */
819 	memset(bp->b_addr, 0, args->geo->blksize);
820 
821 	/*
822 	 * Clean out the prior contents of the attribute list.
823 	 */
824 	error = xfs_da_shrink_inode(args, 0, bp);
825 	if (error)
826 		goto out;
827 
828 	if (forkoff == -1) {
829 		ASSERT(dp->i_mount->m_flags & XFS_MOUNT_ATTR2);
830 		ASSERT(dp->i_d.di_format != XFS_DINODE_FMT_BTREE);
831 		xfs_attr_fork_reset(dp, args->trans);
832 		goto out;
833 	}
834 
835 	xfs_attr_shortform_create(args);
836 
837 	/*
838 	 * Copy the attributes
839 	 */
840 	memset((char *)&nargs, 0, sizeof(nargs));
841 	nargs.geo = args->geo;
842 	nargs.dp = dp;
843 	nargs.firstblock = args->firstblock;
844 	nargs.flist = args->flist;
845 	nargs.total = args->total;
846 	nargs.whichfork = XFS_ATTR_FORK;
847 	nargs.trans = args->trans;
848 	nargs.op_flags = XFS_DA_OP_OKNOENT;
849 
850 	for (i = 0; i < ichdr.count; entry++, i++) {
851 		if (entry->flags & XFS_ATTR_INCOMPLETE)
852 			continue;	/* don't copy partial entries */
853 		if (!entry->nameidx)
854 			continue;
855 		ASSERT(entry->flags & XFS_ATTR_LOCAL);
856 		name_loc = xfs_attr3_leaf_name_local(leaf, i);
857 		nargs.name = name_loc->nameval;
858 		nargs.namelen = name_loc->namelen;
859 		nargs.value = &name_loc->nameval[nargs.namelen];
860 		nargs.valuelen = be16_to_cpu(name_loc->valuelen);
861 		nargs.hashval = be32_to_cpu(entry->hashval);
862 		nargs.flags = XFS_ATTR_NSP_ONDISK_TO_ARGS(entry->flags);
863 		xfs_attr_shortform_add(&nargs, forkoff);
864 	}
865 	error = 0;
866 
867 out:
868 	kmem_free(tmpbuffer);
869 	return error;
870 }
871 
872 /*
873  * Convert from using a single leaf to a root node and a leaf.
874  */
875 int
876 xfs_attr3_leaf_to_node(
877 	struct xfs_da_args	*args)
878 {
879 	struct xfs_attr_leafblock *leaf;
880 	struct xfs_attr3_icleaf_hdr icleafhdr;
881 	struct xfs_attr_leaf_entry *entries;
882 	struct xfs_da_node_entry *btree;
883 	struct xfs_da3_icnode_hdr icnodehdr;
884 	struct xfs_da_intnode	*node;
885 	struct xfs_inode	*dp = args->dp;
886 	struct xfs_mount	*mp = dp->i_mount;
887 	struct xfs_buf		*bp1 = NULL;
888 	struct xfs_buf		*bp2 = NULL;
889 	xfs_dablk_t		blkno;
890 	int			error;
891 
892 	trace_xfs_attr_leaf_to_node(args);
893 
894 	error = xfs_da_grow_inode(args, &blkno);
895 	if (error)
896 		goto out;
897 	error = xfs_attr3_leaf_read(args->trans, dp, 0, -1, &bp1);
898 	if (error)
899 		goto out;
900 
901 	error = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp2, XFS_ATTR_FORK);
902 	if (error)
903 		goto out;
904 
905 	/* copy leaf to new buffer, update identifiers */
906 	xfs_trans_buf_set_type(args->trans, bp2, XFS_BLFT_ATTR_LEAF_BUF);
907 	bp2->b_ops = bp1->b_ops;
908 	memcpy(bp2->b_addr, bp1->b_addr, args->geo->blksize);
909 	if (xfs_sb_version_hascrc(&mp->m_sb)) {
910 		struct xfs_da3_blkinfo *hdr3 = bp2->b_addr;
911 		hdr3->blkno = cpu_to_be64(bp2->b_bn);
912 	}
913 	xfs_trans_log_buf(args->trans, bp2, 0, args->geo->blksize - 1);
914 
915 	/*
916 	 * Set up the new root node.
917 	 */
918 	error = xfs_da3_node_create(args, 0, 1, &bp1, XFS_ATTR_FORK);
919 	if (error)
920 		goto out;
921 	node = bp1->b_addr;
922 	dp->d_ops->node_hdr_from_disk(&icnodehdr, node);
923 	btree = dp->d_ops->node_tree_p(node);
924 
925 	leaf = bp2->b_addr;
926 	xfs_attr3_leaf_hdr_from_disk(&icleafhdr, leaf);
927 	entries = xfs_attr3_leaf_entryp(leaf);
928 
929 	/* both on-disk, don't endian-flip twice */
930 	btree[0].hashval = entries[icleafhdr.count - 1].hashval;
931 	btree[0].before = cpu_to_be32(blkno);
932 	icnodehdr.count = 1;
933 	dp->d_ops->node_hdr_to_disk(node, &icnodehdr);
934 	xfs_trans_log_buf(args->trans, bp1, 0, args->geo->blksize - 1);
935 	error = 0;
936 out:
937 	return error;
938 }
939 
940 /*========================================================================
941  * Routines used for growing the Btree.
942  *========================================================================*/
943 
944 /*
945  * Create the initial contents of a leaf attribute list
946  * or a leaf in a node attribute list.
947  */
948 STATIC int
949 xfs_attr3_leaf_create(
950 	struct xfs_da_args	*args,
951 	xfs_dablk_t		blkno,
952 	struct xfs_buf		**bpp)
953 {
954 	struct xfs_attr_leafblock *leaf;
955 	struct xfs_attr3_icleaf_hdr ichdr;
956 	struct xfs_inode	*dp = args->dp;
957 	struct xfs_mount	*mp = dp->i_mount;
958 	struct xfs_buf		*bp;
959 	int			error;
960 
961 	trace_xfs_attr_leaf_create(args);
962 
963 	error = xfs_da_get_buf(args->trans, args->dp, blkno, -1, &bp,
964 					    XFS_ATTR_FORK);
965 	if (error)
966 		return error;
967 	bp->b_ops = &xfs_attr3_leaf_buf_ops;
968 	xfs_trans_buf_set_type(args->trans, bp, XFS_BLFT_ATTR_LEAF_BUF);
969 	leaf = bp->b_addr;
970 	memset(leaf, 0, args->geo->blksize);
971 
972 	memset(&ichdr, 0, sizeof(ichdr));
973 	ichdr.firstused = args->geo->blksize;
974 
975 	if (xfs_sb_version_hascrc(&mp->m_sb)) {
976 		struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
977 
978 		ichdr.magic = XFS_ATTR3_LEAF_MAGIC;
979 
980 		hdr3->blkno = cpu_to_be64(bp->b_bn);
981 		hdr3->owner = cpu_to_be64(dp->i_ino);
982 		uuid_copy(&hdr3->uuid, &mp->m_sb.sb_uuid);
983 
984 		ichdr.freemap[0].base = sizeof(struct xfs_attr3_leaf_hdr);
985 	} else {
986 		ichdr.magic = XFS_ATTR_LEAF_MAGIC;
987 		ichdr.freemap[0].base = sizeof(struct xfs_attr_leaf_hdr);
988 	}
989 	ichdr.freemap[0].size = ichdr.firstused - ichdr.freemap[0].base;
990 
991 	xfs_attr3_leaf_hdr_to_disk(leaf, &ichdr);
992 	xfs_trans_log_buf(args->trans, bp, 0, args->geo->blksize - 1);
993 
994 	*bpp = bp;
995 	return 0;
996 }
997 
998 /*
999  * Split the leaf node, rebalance, then add the new entry.
1000  */
1001 int
1002 xfs_attr3_leaf_split(
1003 	struct xfs_da_state	*state,
1004 	struct xfs_da_state_blk	*oldblk,
1005 	struct xfs_da_state_blk	*newblk)
1006 {
1007 	xfs_dablk_t blkno;
1008 	int error;
1009 
1010 	trace_xfs_attr_leaf_split(state->args);
1011 
1012 	/*
1013 	 * Allocate space for a new leaf node.
1014 	 */
1015 	ASSERT(oldblk->magic == XFS_ATTR_LEAF_MAGIC);
1016 	error = xfs_da_grow_inode(state->args, &blkno);
1017 	if (error)
1018 		return error;
1019 	error = xfs_attr3_leaf_create(state->args, blkno, &newblk->bp);
1020 	if (error)
1021 		return error;
1022 	newblk->blkno = blkno;
1023 	newblk->magic = XFS_ATTR_LEAF_MAGIC;
1024 
1025 	/*
1026 	 * Rebalance the entries across the two leaves.
1027 	 * NOTE: rebalance() currently depends on the 2nd block being empty.
1028 	 */
1029 	xfs_attr3_leaf_rebalance(state, oldblk, newblk);
1030 	error = xfs_da3_blk_link(state, oldblk, newblk);
1031 	if (error)
1032 		return error;
1033 
1034 	/*
1035 	 * Save info on "old" attribute for "atomic rename" ops, leaf_add()
1036 	 * modifies the index/blkno/rmtblk/rmtblkcnt fields to show the
1037 	 * "new" attrs info.  Will need the "old" info to remove it later.
1038 	 *
1039 	 * Insert the "new" entry in the correct block.
1040 	 */
1041 	if (state->inleaf) {
1042 		trace_xfs_attr_leaf_add_old(state->args);
1043 		error = xfs_attr3_leaf_add(oldblk->bp, state->args);
1044 	} else {
1045 		trace_xfs_attr_leaf_add_new(state->args);
1046 		error = xfs_attr3_leaf_add(newblk->bp, state->args);
1047 	}
1048 
1049 	/*
1050 	 * Update last hashval in each block since we added the name.
1051 	 */
1052 	oldblk->hashval = xfs_attr_leaf_lasthash(oldblk->bp, NULL);
1053 	newblk->hashval = xfs_attr_leaf_lasthash(newblk->bp, NULL);
1054 	return error;
1055 }
1056 
1057 /*
1058  * Add a name to the leaf attribute list structure.
1059  */
1060 int
1061 xfs_attr3_leaf_add(
1062 	struct xfs_buf		*bp,
1063 	struct xfs_da_args	*args)
1064 {
1065 	struct xfs_attr_leafblock *leaf;
1066 	struct xfs_attr3_icleaf_hdr ichdr;
1067 	int			tablesize;
1068 	int			entsize;
1069 	int			sum;
1070 	int			tmp;
1071 	int			i;
1072 
1073 	trace_xfs_attr_leaf_add(args);
1074 
1075 	leaf = bp->b_addr;
1076 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
1077 	ASSERT(args->index >= 0 && args->index <= ichdr.count);
1078 	entsize = xfs_attr_leaf_newentsize(args, NULL);
1079 
1080 	/*
1081 	 * Search through freemap for first-fit on new name length.
1082 	 * (may need to figure in size of entry struct too)
1083 	 */
1084 	tablesize = (ichdr.count + 1) * sizeof(xfs_attr_leaf_entry_t)
1085 					+ xfs_attr3_leaf_hdr_size(leaf);
1086 	for (sum = 0, i = XFS_ATTR_LEAF_MAPSIZE - 1; i >= 0; i--) {
1087 		if (tablesize > ichdr.firstused) {
1088 			sum += ichdr.freemap[i].size;
1089 			continue;
1090 		}
1091 		if (!ichdr.freemap[i].size)
1092 			continue;	/* no space in this map */
1093 		tmp = entsize;
1094 		if (ichdr.freemap[i].base < ichdr.firstused)
1095 			tmp += sizeof(xfs_attr_leaf_entry_t);
1096 		if (ichdr.freemap[i].size >= tmp) {
1097 			tmp = xfs_attr3_leaf_add_work(bp, &ichdr, args, i);
1098 			goto out_log_hdr;
1099 		}
1100 		sum += ichdr.freemap[i].size;
1101 	}
1102 
1103 	/*
1104 	 * If there are no holes in the address space of the block,
1105 	 * and we don't have enough freespace, then compaction will do us
1106 	 * no good and we should just give up.
1107 	 */
1108 	if (!ichdr.holes && sum < entsize)
1109 		return -ENOSPC;
1110 
1111 	/*
1112 	 * Compact the entries to coalesce free space.
1113 	 * This may change the hdr->count via dropping INCOMPLETE entries.
1114 	 */
1115 	xfs_attr3_leaf_compact(args, &ichdr, bp);
1116 
1117 	/*
1118 	 * After compaction, the block is guaranteed to have only one
1119 	 * free region, in freemap[0].  If it is not big enough, give up.
1120 	 */
1121 	if (ichdr.freemap[0].size < (entsize + sizeof(xfs_attr_leaf_entry_t))) {
1122 		tmp = -ENOSPC;
1123 		goto out_log_hdr;
1124 	}
1125 
1126 	tmp = xfs_attr3_leaf_add_work(bp, &ichdr, args, 0);
1127 
1128 out_log_hdr:
1129 	xfs_attr3_leaf_hdr_to_disk(leaf, &ichdr);
1130 	xfs_trans_log_buf(args->trans, bp,
1131 		XFS_DA_LOGRANGE(leaf, &leaf->hdr,
1132 				xfs_attr3_leaf_hdr_size(leaf)));
1133 	return tmp;
1134 }
1135 
1136 /*
1137  * Add a name to a leaf attribute list structure.
1138  */
1139 STATIC int
1140 xfs_attr3_leaf_add_work(
1141 	struct xfs_buf		*bp,
1142 	struct xfs_attr3_icleaf_hdr *ichdr,
1143 	struct xfs_da_args	*args,
1144 	int			mapindex)
1145 {
1146 	struct xfs_attr_leafblock *leaf;
1147 	struct xfs_attr_leaf_entry *entry;
1148 	struct xfs_attr_leaf_name_local *name_loc;
1149 	struct xfs_attr_leaf_name_remote *name_rmt;
1150 	struct xfs_mount	*mp;
1151 	int			tmp;
1152 	int			i;
1153 
1154 	trace_xfs_attr_leaf_add_work(args);
1155 
1156 	leaf = bp->b_addr;
1157 	ASSERT(mapindex >= 0 && mapindex < XFS_ATTR_LEAF_MAPSIZE);
1158 	ASSERT(args->index >= 0 && args->index <= ichdr->count);
1159 
1160 	/*
1161 	 * Force open some space in the entry array and fill it in.
1162 	 */
1163 	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
1164 	if (args->index < ichdr->count) {
1165 		tmp  = ichdr->count - args->index;
1166 		tmp *= sizeof(xfs_attr_leaf_entry_t);
1167 		memmove(entry + 1, entry, tmp);
1168 		xfs_trans_log_buf(args->trans, bp,
1169 		    XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));
1170 	}
1171 	ichdr->count++;
1172 
1173 	/*
1174 	 * Allocate space for the new string (at the end of the run).
1175 	 */
1176 	mp = args->trans->t_mountp;
1177 	ASSERT(ichdr->freemap[mapindex].base < args->geo->blksize);
1178 	ASSERT((ichdr->freemap[mapindex].base & 0x3) == 0);
1179 	ASSERT(ichdr->freemap[mapindex].size >=
1180 		xfs_attr_leaf_newentsize(args, NULL));
1181 	ASSERT(ichdr->freemap[mapindex].size < args->geo->blksize);
1182 	ASSERT((ichdr->freemap[mapindex].size & 0x3) == 0);
1183 
1184 	ichdr->freemap[mapindex].size -= xfs_attr_leaf_newentsize(args, &tmp);
1185 
1186 	entry->nameidx = cpu_to_be16(ichdr->freemap[mapindex].base +
1187 				     ichdr->freemap[mapindex].size);
1188 	entry->hashval = cpu_to_be32(args->hashval);
1189 	entry->flags = tmp ? XFS_ATTR_LOCAL : 0;
1190 	entry->flags |= XFS_ATTR_NSP_ARGS_TO_ONDISK(args->flags);
1191 	if (args->op_flags & XFS_DA_OP_RENAME) {
1192 		entry->flags |= XFS_ATTR_INCOMPLETE;
1193 		if ((args->blkno2 == args->blkno) &&
1194 		    (args->index2 <= args->index)) {
1195 			args->index2++;
1196 		}
1197 	}
1198 	xfs_trans_log_buf(args->trans, bp,
1199 			  XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
1200 	ASSERT((args->index == 0) ||
1201 	       (be32_to_cpu(entry->hashval) >= be32_to_cpu((entry-1)->hashval)));
1202 	ASSERT((args->index == ichdr->count - 1) ||
1203 	       (be32_to_cpu(entry->hashval) <= be32_to_cpu((entry+1)->hashval)));
1204 
1205 	/*
1206 	 * For "remote" attribute values, simply note that we need to
1207 	 * allocate space for the "remote" value.  We can't actually
1208 	 * allocate the extents in this transaction, and we can't decide
1209 	 * which blocks they should be as we might allocate more blocks
1210 	 * as part of this transaction (a split operation for example).
1211 	 */
1212 	if (entry->flags & XFS_ATTR_LOCAL) {
1213 		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
1214 		name_loc->namelen = args->namelen;
1215 		name_loc->valuelen = cpu_to_be16(args->valuelen);
1216 		memcpy((char *)name_loc->nameval, args->name, args->namelen);
1217 		memcpy((char *)&name_loc->nameval[args->namelen], args->value,
1218 				   be16_to_cpu(name_loc->valuelen));
1219 	} else {
1220 		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
1221 		name_rmt->namelen = args->namelen;
1222 		memcpy((char *)name_rmt->name, args->name, args->namelen);
1223 		entry->flags |= XFS_ATTR_INCOMPLETE;
1224 		/* just in case */
1225 		name_rmt->valuelen = 0;
1226 		name_rmt->valueblk = 0;
1227 		args->rmtblkno = 1;
1228 		args->rmtblkcnt = xfs_attr3_rmt_blocks(mp, args->valuelen);
1229 		args->rmtvaluelen = args->valuelen;
1230 	}
1231 	xfs_trans_log_buf(args->trans, bp,
1232 	     XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),
1233 				   xfs_attr_leaf_entsize(leaf, args->index)));
1234 
1235 	/*
1236 	 * Update the control info for this leaf node
1237 	 */
1238 	if (be16_to_cpu(entry->nameidx) < ichdr->firstused)
1239 		ichdr->firstused = be16_to_cpu(entry->nameidx);
1240 
1241 	ASSERT(ichdr->firstused >= ichdr->count * sizeof(xfs_attr_leaf_entry_t)
1242 					+ xfs_attr3_leaf_hdr_size(leaf));
1243 	tmp = (ichdr->count - 1) * sizeof(xfs_attr_leaf_entry_t)
1244 					+ xfs_attr3_leaf_hdr_size(leaf);
1245 
1246 	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
1247 		if (ichdr->freemap[i].base == tmp) {
1248 			ichdr->freemap[i].base += sizeof(xfs_attr_leaf_entry_t);
1249 			ichdr->freemap[i].size -= sizeof(xfs_attr_leaf_entry_t);
1250 		}
1251 	}
1252 	ichdr->usedbytes += xfs_attr_leaf_entsize(leaf, args->index);
1253 	return 0;
1254 }
1255 
1256 /*
1257  * Garbage collect a leaf attribute list block by copying it to a new buffer.
1258  */
1259 STATIC void
1260 xfs_attr3_leaf_compact(
1261 	struct xfs_da_args	*args,
1262 	struct xfs_attr3_icleaf_hdr *ichdr_dst,
1263 	struct xfs_buf		*bp)
1264 {
1265 	struct xfs_attr_leafblock *leaf_src;
1266 	struct xfs_attr_leafblock *leaf_dst;
1267 	struct xfs_attr3_icleaf_hdr ichdr_src;
1268 	struct xfs_trans	*trans = args->trans;
1269 	char			*tmpbuffer;
1270 
1271 	trace_xfs_attr_leaf_compact(args);
1272 
1273 	tmpbuffer = kmem_alloc(args->geo->blksize, KM_SLEEP);
1274 	memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);
1275 	memset(bp->b_addr, 0, args->geo->blksize);
1276 	leaf_src = (xfs_attr_leafblock_t *)tmpbuffer;
1277 	leaf_dst = bp->b_addr;
1278 
1279 	/*
1280 	 * Copy the on-disk header back into the destination buffer to ensure
1281 	 * all the information in the header that is not part of the incore
1282 	 * header structure is preserved.
1283 	 */
1284 	memcpy(bp->b_addr, tmpbuffer, xfs_attr3_leaf_hdr_size(leaf_src));
1285 
1286 	/* Initialise the incore headers */
1287 	ichdr_src = *ichdr_dst;	/* struct copy */
1288 	ichdr_dst->firstused = args->geo->blksize;
1289 	ichdr_dst->usedbytes = 0;
1290 	ichdr_dst->count = 0;
1291 	ichdr_dst->holes = 0;
1292 	ichdr_dst->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_src);
1293 	ichdr_dst->freemap[0].size = ichdr_dst->firstused -
1294 						ichdr_dst->freemap[0].base;
1295 
1296 	/* write the header back to initialise the underlying buffer */
1297 	xfs_attr3_leaf_hdr_to_disk(leaf_dst, ichdr_dst);
1298 
1299 	/*
1300 	 * Copy all entry's in the same (sorted) order,
1301 	 * but allocate name/value pairs packed and in sequence.
1302 	 */
1303 	xfs_attr3_leaf_moveents(args, leaf_src, &ichdr_src, 0,
1304 				leaf_dst, ichdr_dst, 0, ichdr_src.count);
1305 	/*
1306 	 * this logs the entire buffer, but the caller must write the header
1307 	 * back to the buffer when it is finished modifying it.
1308 	 */
1309 	xfs_trans_log_buf(trans, bp, 0, args->geo->blksize - 1);
1310 
1311 	kmem_free(tmpbuffer);
1312 }
1313 
1314 /*
1315  * Compare two leaf blocks "order".
1316  * Return 0 unless leaf2 should go before leaf1.
1317  */
1318 static int
1319 xfs_attr3_leaf_order(
1320 	struct xfs_buf	*leaf1_bp,
1321 	struct xfs_attr3_icleaf_hdr *leaf1hdr,
1322 	struct xfs_buf	*leaf2_bp,
1323 	struct xfs_attr3_icleaf_hdr *leaf2hdr)
1324 {
1325 	struct xfs_attr_leaf_entry *entries1;
1326 	struct xfs_attr_leaf_entry *entries2;
1327 
1328 	entries1 = xfs_attr3_leaf_entryp(leaf1_bp->b_addr);
1329 	entries2 = xfs_attr3_leaf_entryp(leaf2_bp->b_addr);
1330 	if (leaf1hdr->count > 0 && leaf2hdr->count > 0 &&
1331 	    ((be32_to_cpu(entries2[0].hashval) <
1332 	      be32_to_cpu(entries1[0].hashval)) ||
1333 	     (be32_to_cpu(entries2[leaf2hdr->count - 1].hashval) <
1334 	      be32_to_cpu(entries1[leaf1hdr->count - 1].hashval)))) {
1335 		return 1;
1336 	}
1337 	return 0;
1338 }
1339 
1340 int
1341 xfs_attr_leaf_order(
1342 	struct xfs_buf	*leaf1_bp,
1343 	struct xfs_buf	*leaf2_bp)
1344 {
1345 	struct xfs_attr3_icleaf_hdr ichdr1;
1346 	struct xfs_attr3_icleaf_hdr ichdr2;
1347 
1348 	xfs_attr3_leaf_hdr_from_disk(&ichdr1, leaf1_bp->b_addr);
1349 	xfs_attr3_leaf_hdr_from_disk(&ichdr2, leaf2_bp->b_addr);
1350 	return xfs_attr3_leaf_order(leaf1_bp, &ichdr1, leaf2_bp, &ichdr2);
1351 }
1352 
1353 /*
1354  * Redistribute the attribute list entries between two leaf nodes,
1355  * taking into account the size of the new entry.
1356  *
1357  * NOTE: if new block is empty, then it will get the upper half of the
1358  * old block.  At present, all (one) callers pass in an empty second block.
1359  *
1360  * This code adjusts the args->index/blkno and args->index2/blkno2 fields
1361  * to match what it is doing in splitting the attribute leaf block.  Those
1362  * values are used in "atomic rename" operations on attributes.  Note that
1363  * the "new" and "old" values can end up in different blocks.
1364  */
1365 STATIC void
1366 xfs_attr3_leaf_rebalance(
1367 	struct xfs_da_state	*state,
1368 	struct xfs_da_state_blk	*blk1,
1369 	struct xfs_da_state_blk	*blk2)
1370 {
1371 	struct xfs_da_args	*args;
1372 	struct xfs_attr_leafblock *leaf1;
1373 	struct xfs_attr_leafblock *leaf2;
1374 	struct xfs_attr3_icleaf_hdr ichdr1;
1375 	struct xfs_attr3_icleaf_hdr ichdr2;
1376 	struct xfs_attr_leaf_entry *entries1;
1377 	struct xfs_attr_leaf_entry *entries2;
1378 	int			count;
1379 	int			totallen;
1380 	int			max;
1381 	int			space;
1382 	int			swap;
1383 
1384 	/*
1385 	 * Set up environment.
1386 	 */
1387 	ASSERT(blk1->magic == XFS_ATTR_LEAF_MAGIC);
1388 	ASSERT(blk2->magic == XFS_ATTR_LEAF_MAGIC);
1389 	leaf1 = blk1->bp->b_addr;
1390 	leaf2 = blk2->bp->b_addr;
1391 	xfs_attr3_leaf_hdr_from_disk(&ichdr1, leaf1);
1392 	xfs_attr3_leaf_hdr_from_disk(&ichdr2, leaf2);
1393 	ASSERT(ichdr2.count == 0);
1394 	args = state->args;
1395 
1396 	trace_xfs_attr_leaf_rebalance(args);
1397 
1398 	/*
1399 	 * Check ordering of blocks, reverse if it makes things simpler.
1400 	 *
1401 	 * NOTE: Given that all (current) callers pass in an empty
1402 	 * second block, this code should never set "swap".
1403 	 */
1404 	swap = 0;
1405 	if (xfs_attr3_leaf_order(blk1->bp, &ichdr1, blk2->bp, &ichdr2)) {
1406 		struct xfs_da_state_blk	*tmp_blk;
1407 		struct xfs_attr3_icleaf_hdr tmp_ichdr;
1408 
1409 		tmp_blk = blk1;
1410 		blk1 = blk2;
1411 		blk2 = tmp_blk;
1412 
1413 		/* struct copies to swap them rather than reconverting */
1414 		tmp_ichdr = ichdr1;
1415 		ichdr1 = ichdr2;
1416 		ichdr2 = tmp_ichdr;
1417 
1418 		leaf1 = blk1->bp->b_addr;
1419 		leaf2 = blk2->bp->b_addr;
1420 		swap = 1;
1421 	}
1422 
1423 	/*
1424 	 * Examine entries until we reduce the absolute difference in
1425 	 * byte usage between the two blocks to a minimum.  Then get
1426 	 * the direction to copy and the number of elements to move.
1427 	 *
1428 	 * "inleaf" is true if the new entry should be inserted into blk1.
1429 	 * If "swap" is also true, then reverse the sense of "inleaf".
1430 	 */
1431 	state->inleaf = xfs_attr3_leaf_figure_balance(state, blk1, &ichdr1,
1432 						      blk2, &ichdr2,
1433 						      &count, &totallen);
1434 	if (swap)
1435 		state->inleaf = !state->inleaf;
1436 
1437 	/*
1438 	 * Move any entries required from leaf to leaf:
1439 	 */
1440 	if (count < ichdr1.count) {
1441 		/*
1442 		 * Figure the total bytes to be added to the destination leaf.
1443 		 */
1444 		/* number entries being moved */
1445 		count = ichdr1.count - count;
1446 		space  = ichdr1.usedbytes - totallen;
1447 		space += count * sizeof(xfs_attr_leaf_entry_t);
1448 
1449 		/*
1450 		 * leaf2 is the destination, compact it if it looks tight.
1451 		 */
1452 		max  = ichdr2.firstused - xfs_attr3_leaf_hdr_size(leaf1);
1453 		max -= ichdr2.count * sizeof(xfs_attr_leaf_entry_t);
1454 		if (space > max)
1455 			xfs_attr3_leaf_compact(args, &ichdr2, blk2->bp);
1456 
1457 		/*
1458 		 * Move high entries from leaf1 to low end of leaf2.
1459 		 */
1460 		xfs_attr3_leaf_moveents(args, leaf1, &ichdr1,
1461 				ichdr1.count - count, leaf2, &ichdr2, 0, count);
1462 
1463 	} else if (count > ichdr1.count) {
1464 		/*
1465 		 * I assert that since all callers pass in an empty
1466 		 * second buffer, this code should never execute.
1467 		 */
1468 		ASSERT(0);
1469 
1470 		/*
1471 		 * Figure the total bytes to be added to the destination leaf.
1472 		 */
1473 		/* number entries being moved */
1474 		count -= ichdr1.count;
1475 		space  = totallen - ichdr1.usedbytes;
1476 		space += count * sizeof(xfs_attr_leaf_entry_t);
1477 
1478 		/*
1479 		 * leaf1 is the destination, compact it if it looks tight.
1480 		 */
1481 		max  = ichdr1.firstused - xfs_attr3_leaf_hdr_size(leaf1);
1482 		max -= ichdr1.count * sizeof(xfs_attr_leaf_entry_t);
1483 		if (space > max)
1484 			xfs_attr3_leaf_compact(args, &ichdr1, blk1->bp);
1485 
1486 		/*
1487 		 * Move low entries from leaf2 to high end of leaf1.
1488 		 */
1489 		xfs_attr3_leaf_moveents(args, leaf2, &ichdr2, 0, leaf1, &ichdr1,
1490 					ichdr1.count, count);
1491 	}
1492 
1493 	xfs_attr3_leaf_hdr_to_disk(leaf1, &ichdr1);
1494 	xfs_attr3_leaf_hdr_to_disk(leaf2, &ichdr2);
1495 	xfs_trans_log_buf(args->trans, blk1->bp, 0, args->geo->blksize - 1);
1496 	xfs_trans_log_buf(args->trans, blk2->bp, 0, args->geo->blksize - 1);
1497 
1498 	/*
1499 	 * Copy out last hashval in each block for B-tree code.
1500 	 */
1501 	entries1 = xfs_attr3_leaf_entryp(leaf1);
1502 	entries2 = xfs_attr3_leaf_entryp(leaf2);
1503 	blk1->hashval = be32_to_cpu(entries1[ichdr1.count - 1].hashval);
1504 	blk2->hashval = be32_to_cpu(entries2[ichdr2.count - 1].hashval);
1505 
1506 	/*
1507 	 * Adjust the expected index for insertion.
1508 	 * NOTE: this code depends on the (current) situation that the
1509 	 * second block was originally empty.
1510 	 *
1511 	 * If the insertion point moved to the 2nd block, we must adjust
1512 	 * the index.  We must also track the entry just following the
1513 	 * new entry for use in an "atomic rename" operation, that entry
1514 	 * is always the "old" entry and the "new" entry is what we are
1515 	 * inserting.  The index/blkno fields refer to the "old" entry,
1516 	 * while the index2/blkno2 fields refer to the "new" entry.
1517 	 */
1518 	if (blk1->index > ichdr1.count) {
1519 		ASSERT(state->inleaf == 0);
1520 		blk2->index = blk1->index - ichdr1.count;
1521 		args->index = args->index2 = blk2->index;
1522 		args->blkno = args->blkno2 = blk2->blkno;
1523 	} else if (blk1->index == ichdr1.count) {
1524 		if (state->inleaf) {
1525 			args->index = blk1->index;
1526 			args->blkno = blk1->blkno;
1527 			args->index2 = 0;
1528 			args->blkno2 = blk2->blkno;
1529 		} else {
1530 			/*
1531 			 * On a double leaf split, the original attr location
1532 			 * is already stored in blkno2/index2, so don't
1533 			 * overwrite it overwise we corrupt the tree.
1534 			 */
1535 			blk2->index = blk1->index - ichdr1.count;
1536 			args->index = blk2->index;
1537 			args->blkno = blk2->blkno;
1538 			if (!state->extravalid) {
1539 				/*
1540 				 * set the new attr location to match the old
1541 				 * one and let the higher level split code
1542 				 * decide where in the leaf to place it.
1543 				 */
1544 				args->index2 = blk2->index;
1545 				args->blkno2 = blk2->blkno;
1546 			}
1547 		}
1548 	} else {
1549 		ASSERT(state->inleaf == 1);
1550 		args->index = args->index2 = blk1->index;
1551 		args->blkno = args->blkno2 = blk1->blkno;
1552 	}
1553 }
1554 
1555 /*
1556  * Examine entries until we reduce the absolute difference in
1557  * byte usage between the two blocks to a minimum.
1558  * GROT: Is this really necessary?  With other than a 512 byte blocksize,
1559  * GROT: there will always be enough room in either block for a new entry.
1560  * GROT: Do a double-split for this case?
1561  */
1562 STATIC int
1563 xfs_attr3_leaf_figure_balance(
1564 	struct xfs_da_state		*state,
1565 	struct xfs_da_state_blk		*blk1,
1566 	struct xfs_attr3_icleaf_hdr	*ichdr1,
1567 	struct xfs_da_state_blk		*blk2,
1568 	struct xfs_attr3_icleaf_hdr	*ichdr2,
1569 	int				*countarg,
1570 	int				*usedbytesarg)
1571 {
1572 	struct xfs_attr_leafblock	*leaf1 = blk1->bp->b_addr;
1573 	struct xfs_attr_leafblock	*leaf2 = blk2->bp->b_addr;
1574 	struct xfs_attr_leaf_entry	*entry;
1575 	int				count;
1576 	int				max;
1577 	int				index;
1578 	int				totallen = 0;
1579 	int				half;
1580 	int				lastdelta;
1581 	int				foundit = 0;
1582 	int				tmp;
1583 
1584 	/*
1585 	 * Examine entries until we reduce the absolute difference in
1586 	 * byte usage between the two blocks to a minimum.
1587 	 */
1588 	max = ichdr1->count + ichdr2->count;
1589 	half = (max + 1) * sizeof(*entry);
1590 	half += ichdr1->usedbytes + ichdr2->usedbytes +
1591 			xfs_attr_leaf_newentsize(state->args, NULL);
1592 	half /= 2;
1593 	lastdelta = state->args->geo->blksize;
1594 	entry = xfs_attr3_leaf_entryp(leaf1);
1595 	for (count = index = 0; count < max; entry++, index++, count++) {
1596 
1597 #define XFS_ATTR_ABS(A)	(((A) < 0) ? -(A) : (A))
1598 		/*
1599 		 * The new entry is in the first block, account for it.
1600 		 */
1601 		if (count == blk1->index) {
1602 			tmp = totallen + sizeof(*entry) +
1603 				xfs_attr_leaf_newentsize(state->args, NULL);
1604 			if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1605 				break;
1606 			lastdelta = XFS_ATTR_ABS(half - tmp);
1607 			totallen = tmp;
1608 			foundit = 1;
1609 		}
1610 
1611 		/*
1612 		 * Wrap around into the second block if necessary.
1613 		 */
1614 		if (count == ichdr1->count) {
1615 			leaf1 = leaf2;
1616 			entry = xfs_attr3_leaf_entryp(leaf1);
1617 			index = 0;
1618 		}
1619 
1620 		/*
1621 		 * Figure out if next leaf entry would be too much.
1622 		 */
1623 		tmp = totallen + sizeof(*entry) + xfs_attr_leaf_entsize(leaf1,
1624 									index);
1625 		if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1626 			break;
1627 		lastdelta = XFS_ATTR_ABS(half - tmp);
1628 		totallen = tmp;
1629 #undef XFS_ATTR_ABS
1630 	}
1631 
1632 	/*
1633 	 * Calculate the number of usedbytes that will end up in lower block.
1634 	 * If new entry not in lower block, fix up the count.
1635 	 */
1636 	totallen -= count * sizeof(*entry);
1637 	if (foundit) {
1638 		totallen -= sizeof(*entry) +
1639 				xfs_attr_leaf_newentsize(state->args, NULL);
1640 	}
1641 
1642 	*countarg = count;
1643 	*usedbytesarg = totallen;
1644 	return foundit;
1645 }
1646 
1647 /*========================================================================
1648  * Routines used for shrinking the Btree.
1649  *========================================================================*/
1650 
1651 /*
1652  * Check a leaf block and its neighbors to see if the block should be
1653  * collapsed into one or the other neighbor.  Always keep the block
1654  * with the smaller block number.
1655  * If the current block is over 50% full, don't try to join it, return 0.
1656  * If the block is empty, fill in the state structure and return 2.
1657  * If it can be collapsed, fill in the state structure and return 1.
1658  * If nothing can be done, return 0.
1659  *
1660  * GROT: allow for INCOMPLETE entries in calculation.
1661  */
1662 int
1663 xfs_attr3_leaf_toosmall(
1664 	struct xfs_da_state	*state,
1665 	int			*action)
1666 {
1667 	struct xfs_attr_leafblock *leaf;
1668 	struct xfs_da_state_blk	*blk;
1669 	struct xfs_attr3_icleaf_hdr ichdr;
1670 	struct xfs_buf		*bp;
1671 	xfs_dablk_t		blkno;
1672 	int			bytes;
1673 	int			forward;
1674 	int			error;
1675 	int			retval;
1676 	int			i;
1677 
1678 	trace_xfs_attr_leaf_toosmall(state->args);
1679 
1680 	/*
1681 	 * Check for the degenerate case of the block being over 50% full.
1682 	 * If so, it's not worth even looking to see if we might be able
1683 	 * to coalesce with a sibling.
1684 	 */
1685 	blk = &state->path.blk[ state->path.active-1 ];
1686 	leaf = blk->bp->b_addr;
1687 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
1688 	bytes = xfs_attr3_leaf_hdr_size(leaf) +
1689 		ichdr.count * sizeof(xfs_attr_leaf_entry_t) +
1690 		ichdr.usedbytes;
1691 	if (bytes > (state->args->geo->blksize >> 1)) {
1692 		*action = 0;	/* blk over 50%, don't try to join */
1693 		return 0;
1694 	}
1695 
1696 	/*
1697 	 * Check for the degenerate case of the block being empty.
1698 	 * If the block is empty, we'll simply delete it, no need to
1699 	 * coalesce it with a sibling block.  We choose (arbitrarily)
1700 	 * to merge with the forward block unless it is NULL.
1701 	 */
1702 	if (ichdr.count == 0) {
1703 		/*
1704 		 * Make altpath point to the block we want to keep and
1705 		 * path point to the block we want to drop (this one).
1706 		 */
1707 		forward = (ichdr.forw != 0);
1708 		memcpy(&state->altpath, &state->path, sizeof(state->path));
1709 		error = xfs_da3_path_shift(state, &state->altpath, forward,
1710 						 0, &retval);
1711 		if (error)
1712 			return error;
1713 		if (retval) {
1714 			*action = 0;
1715 		} else {
1716 			*action = 2;
1717 		}
1718 		return 0;
1719 	}
1720 
1721 	/*
1722 	 * Examine each sibling block to see if we can coalesce with
1723 	 * at least 25% free space to spare.  We need to figure out
1724 	 * whether to merge with the forward or the backward block.
1725 	 * We prefer coalescing with the lower numbered sibling so as
1726 	 * to shrink an attribute list over time.
1727 	 */
1728 	/* start with smaller blk num */
1729 	forward = ichdr.forw < ichdr.back;
1730 	for (i = 0; i < 2; forward = !forward, i++) {
1731 		struct xfs_attr3_icleaf_hdr ichdr2;
1732 		if (forward)
1733 			blkno = ichdr.forw;
1734 		else
1735 			blkno = ichdr.back;
1736 		if (blkno == 0)
1737 			continue;
1738 		error = xfs_attr3_leaf_read(state->args->trans, state->args->dp,
1739 					blkno, -1, &bp);
1740 		if (error)
1741 			return error;
1742 
1743 		xfs_attr3_leaf_hdr_from_disk(&ichdr2, bp->b_addr);
1744 
1745 		bytes = state->args->geo->blksize -
1746 			(state->args->geo->blksize >> 2) -
1747 			ichdr.usedbytes - ichdr2.usedbytes -
1748 			((ichdr.count + ichdr2.count) *
1749 					sizeof(xfs_attr_leaf_entry_t)) -
1750 			xfs_attr3_leaf_hdr_size(leaf);
1751 
1752 		xfs_trans_brelse(state->args->trans, bp);
1753 		if (bytes >= 0)
1754 			break;	/* fits with at least 25% to spare */
1755 	}
1756 	if (i >= 2) {
1757 		*action = 0;
1758 		return 0;
1759 	}
1760 
1761 	/*
1762 	 * Make altpath point to the block we want to keep (the lower
1763 	 * numbered block) and path point to the block we want to drop.
1764 	 */
1765 	memcpy(&state->altpath, &state->path, sizeof(state->path));
1766 	if (blkno < blk->blkno) {
1767 		error = xfs_da3_path_shift(state, &state->altpath, forward,
1768 						 0, &retval);
1769 	} else {
1770 		error = xfs_da3_path_shift(state, &state->path, forward,
1771 						 0, &retval);
1772 	}
1773 	if (error)
1774 		return error;
1775 	if (retval) {
1776 		*action = 0;
1777 	} else {
1778 		*action = 1;
1779 	}
1780 	return 0;
1781 }
1782 
1783 /*
1784  * Remove a name from the leaf attribute list structure.
1785  *
1786  * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1787  * If two leaves are 37% full, when combined they will leave 25% free.
1788  */
1789 int
1790 xfs_attr3_leaf_remove(
1791 	struct xfs_buf		*bp,
1792 	struct xfs_da_args	*args)
1793 {
1794 	struct xfs_attr_leafblock *leaf;
1795 	struct xfs_attr3_icleaf_hdr ichdr;
1796 	struct xfs_attr_leaf_entry *entry;
1797 	int			before;
1798 	int			after;
1799 	int			smallest;
1800 	int			entsize;
1801 	int			tablesize;
1802 	int			tmp;
1803 	int			i;
1804 
1805 	trace_xfs_attr_leaf_remove(args);
1806 
1807 	leaf = bp->b_addr;
1808 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
1809 
1810 	ASSERT(ichdr.count > 0 && ichdr.count < args->geo->blksize / 8);
1811 	ASSERT(args->index >= 0 && args->index < ichdr.count);
1812 	ASSERT(ichdr.firstused >= ichdr.count * sizeof(*entry) +
1813 					xfs_attr3_leaf_hdr_size(leaf));
1814 
1815 	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
1816 
1817 	ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);
1818 	ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);
1819 
1820 	/*
1821 	 * Scan through free region table:
1822 	 *    check for adjacency of free'd entry with an existing one,
1823 	 *    find smallest free region in case we need to replace it,
1824 	 *    adjust any map that borders the entry table,
1825 	 */
1826 	tablesize = ichdr.count * sizeof(xfs_attr_leaf_entry_t)
1827 					+ xfs_attr3_leaf_hdr_size(leaf);
1828 	tmp = ichdr.freemap[0].size;
1829 	before = after = -1;
1830 	smallest = XFS_ATTR_LEAF_MAPSIZE - 1;
1831 	entsize = xfs_attr_leaf_entsize(leaf, args->index);
1832 	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
1833 		ASSERT(ichdr.freemap[i].base < args->geo->blksize);
1834 		ASSERT(ichdr.freemap[i].size < args->geo->blksize);
1835 		if (ichdr.freemap[i].base == tablesize) {
1836 			ichdr.freemap[i].base -= sizeof(xfs_attr_leaf_entry_t);
1837 			ichdr.freemap[i].size += sizeof(xfs_attr_leaf_entry_t);
1838 		}
1839 
1840 		if (ichdr.freemap[i].base + ichdr.freemap[i].size ==
1841 				be16_to_cpu(entry->nameidx)) {
1842 			before = i;
1843 		} else if (ichdr.freemap[i].base ==
1844 				(be16_to_cpu(entry->nameidx) + entsize)) {
1845 			after = i;
1846 		} else if (ichdr.freemap[i].size < tmp) {
1847 			tmp = ichdr.freemap[i].size;
1848 			smallest = i;
1849 		}
1850 	}
1851 
1852 	/*
1853 	 * Coalesce adjacent freemap regions,
1854 	 * or replace the smallest region.
1855 	 */
1856 	if ((before >= 0) || (after >= 0)) {
1857 		if ((before >= 0) && (after >= 0)) {
1858 			ichdr.freemap[before].size += entsize;
1859 			ichdr.freemap[before].size += ichdr.freemap[after].size;
1860 			ichdr.freemap[after].base = 0;
1861 			ichdr.freemap[after].size = 0;
1862 		} else if (before >= 0) {
1863 			ichdr.freemap[before].size += entsize;
1864 		} else {
1865 			ichdr.freemap[after].base = be16_to_cpu(entry->nameidx);
1866 			ichdr.freemap[after].size += entsize;
1867 		}
1868 	} else {
1869 		/*
1870 		 * Replace smallest region (if it is smaller than free'd entry)
1871 		 */
1872 		if (ichdr.freemap[smallest].size < entsize) {
1873 			ichdr.freemap[smallest].base = be16_to_cpu(entry->nameidx);
1874 			ichdr.freemap[smallest].size = entsize;
1875 		}
1876 	}
1877 
1878 	/*
1879 	 * Did we remove the first entry?
1880 	 */
1881 	if (be16_to_cpu(entry->nameidx) == ichdr.firstused)
1882 		smallest = 1;
1883 	else
1884 		smallest = 0;
1885 
1886 	/*
1887 	 * Compress the remaining entries and zero out the removed stuff.
1888 	 */
1889 	memset(xfs_attr3_leaf_name(leaf, args->index), 0, entsize);
1890 	ichdr.usedbytes -= entsize;
1891 	xfs_trans_log_buf(args->trans, bp,
1892 	     XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),
1893 				   entsize));
1894 
1895 	tmp = (ichdr.count - args->index) * sizeof(xfs_attr_leaf_entry_t);
1896 	memmove(entry, entry + 1, tmp);
1897 	ichdr.count--;
1898 	xfs_trans_log_buf(args->trans, bp,
1899 	    XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(xfs_attr_leaf_entry_t)));
1900 
1901 	entry = &xfs_attr3_leaf_entryp(leaf)[ichdr.count];
1902 	memset(entry, 0, sizeof(xfs_attr_leaf_entry_t));
1903 
1904 	/*
1905 	 * If we removed the first entry, re-find the first used byte
1906 	 * in the name area.  Note that if the entry was the "firstused",
1907 	 * then we don't have a "hole" in our block resulting from
1908 	 * removing the name.
1909 	 */
1910 	if (smallest) {
1911 		tmp = args->geo->blksize;
1912 		entry = xfs_attr3_leaf_entryp(leaf);
1913 		for (i = ichdr.count - 1; i >= 0; entry++, i--) {
1914 			ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);
1915 			ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);
1916 
1917 			if (be16_to_cpu(entry->nameidx) < tmp)
1918 				tmp = be16_to_cpu(entry->nameidx);
1919 		}
1920 		ichdr.firstused = tmp;
1921 		if (!ichdr.firstused)
1922 			ichdr.firstused = tmp - XFS_ATTR_LEAF_NAME_ALIGN;
1923 	} else {
1924 		ichdr.holes = 1;	/* mark as needing compaction */
1925 	}
1926 	xfs_attr3_leaf_hdr_to_disk(leaf, &ichdr);
1927 	xfs_trans_log_buf(args->trans, bp,
1928 			  XFS_DA_LOGRANGE(leaf, &leaf->hdr,
1929 					  xfs_attr3_leaf_hdr_size(leaf)));
1930 
1931 	/*
1932 	 * Check if leaf is less than 50% full, caller may want to
1933 	 * "join" the leaf with a sibling if so.
1934 	 */
1935 	tmp = ichdr.usedbytes + xfs_attr3_leaf_hdr_size(leaf) +
1936 	      ichdr.count * sizeof(xfs_attr_leaf_entry_t);
1937 
1938 	return tmp < args->geo->magicpct; /* leaf is < 37% full */
1939 }
1940 
1941 /*
1942  * Move all the attribute list entries from drop_leaf into save_leaf.
1943  */
1944 void
1945 xfs_attr3_leaf_unbalance(
1946 	struct xfs_da_state	*state,
1947 	struct xfs_da_state_blk	*drop_blk,
1948 	struct xfs_da_state_blk	*save_blk)
1949 {
1950 	struct xfs_attr_leafblock *drop_leaf = drop_blk->bp->b_addr;
1951 	struct xfs_attr_leafblock *save_leaf = save_blk->bp->b_addr;
1952 	struct xfs_attr3_icleaf_hdr drophdr;
1953 	struct xfs_attr3_icleaf_hdr savehdr;
1954 	struct xfs_attr_leaf_entry *entry;
1955 
1956 	trace_xfs_attr_leaf_unbalance(state->args);
1957 
1958 	drop_leaf = drop_blk->bp->b_addr;
1959 	save_leaf = save_blk->bp->b_addr;
1960 	xfs_attr3_leaf_hdr_from_disk(&drophdr, drop_leaf);
1961 	xfs_attr3_leaf_hdr_from_disk(&savehdr, save_leaf);
1962 	entry = xfs_attr3_leaf_entryp(drop_leaf);
1963 
1964 	/*
1965 	 * Save last hashval from dying block for later Btree fixup.
1966 	 */
1967 	drop_blk->hashval = be32_to_cpu(entry[drophdr.count - 1].hashval);
1968 
1969 	/*
1970 	 * Check if we need a temp buffer, or can we do it in place.
1971 	 * Note that we don't check "leaf" for holes because we will
1972 	 * always be dropping it, toosmall() decided that for us already.
1973 	 */
1974 	if (savehdr.holes == 0) {
1975 		/*
1976 		 * dest leaf has no holes, so we add there.  May need
1977 		 * to make some room in the entry array.
1978 		 */
1979 		if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,
1980 					 drop_blk->bp, &drophdr)) {
1981 			xfs_attr3_leaf_moveents(state->args,
1982 						drop_leaf, &drophdr, 0,
1983 						save_leaf, &savehdr, 0,
1984 						drophdr.count);
1985 		} else {
1986 			xfs_attr3_leaf_moveents(state->args,
1987 						drop_leaf, &drophdr, 0,
1988 						save_leaf, &savehdr,
1989 						savehdr.count, drophdr.count);
1990 		}
1991 	} else {
1992 		/*
1993 		 * Destination has holes, so we make a temporary copy
1994 		 * of the leaf and add them both to that.
1995 		 */
1996 		struct xfs_attr_leafblock *tmp_leaf;
1997 		struct xfs_attr3_icleaf_hdr tmphdr;
1998 
1999 		tmp_leaf = kmem_zalloc(state->args->geo->blksize, KM_SLEEP);
2000 
2001 		/*
2002 		 * Copy the header into the temp leaf so that all the stuff
2003 		 * not in the incore header is present and gets copied back in
2004 		 * once we've moved all the entries.
2005 		 */
2006 		memcpy(tmp_leaf, save_leaf, xfs_attr3_leaf_hdr_size(save_leaf));
2007 
2008 		memset(&tmphdr, 0, sizeof(tmphdr));
2009 		tmphdr.magic = savehdr.magic;
2010 		tmphdr.forw = savehdr.forw;
2011 		tmphdr.back = savehdr.back;
2012 		tmphdr.firstused = state->args->geo->blksize;
2013 
2014 		/* write the header to the temp buffer to initialise it */
2015 		xfs_attr3_leaf_hdr_to_disk(tmp_leaf, &tmphdr);
2016 
2017 		if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,
2018 					 drop_blk->bp, &drophdr)) {
2019 			xfs_attr3_leaf_moveents(state->args,
2020 						drop_leaf, &drophdr, 0,
2021 						tmp_leaf, &tmphdr, 0,
2022 						drophdr.count);
2023 			xfs_attr3_leaf_moveents(state->args,
2024 						save_leaf, &savehdr, 0,
2025 						tmp_leaf, &tmphdr, tmphdr.count,
2026 						savehdr.count);
2027 		} else {
2028 			xfs_attr3_leaf_moveents(state->args,
2029 						save_leaf, &savehdr, 0,
2030 						tmp_leaf, &tmphdr, 0,
2031 						savehdr.count);
2032 			xfs_attr3_leaf_moveents(state->args,
2033 						drop_leaf, &drophdr, 0,
2034 						tmp_leaf, &tmphdr, tmphdr.count,
2035 						drophdr.count);
2036 		}
2037 		memcpy(save_leaf, tmp_leaf, state->args->geo->blksize);
2038 		savehdr = tmphdr; /* struct copy */
2039 		kmem_free(tmp_leaf);
2040 	}
2041 
2042 	xfs_attr3_leaf_hdr_to_disk(save_leaf, &savehdr);
2043 	xfs_trans_log_buf(state->args->trans, save_blk->bp, 0,
2044 					   state->args->geo->blksize - 1);
2045 
2046 	/*
2047 	 * Copy out last hashval in each block for B-tree code.
2048 	 */
2049 	entry = xfs_attr3_leaf_entryp(save_leaf);
2050 	save_blk->hashval = be32_to_cpu(entry[savehdr.count - 1].hashval);
2051 }
2052 
2053 /*========================================================================
2054  * Routines used for finding things in the Btree.
2055  *========================================================================*/
2056 
2057 /*
2058  * Look up a name in a leaf attribute list structure.
2059  * This is the internal routine, it uses the caller's buffer.
2060  *
2061  * Note that duplicate keys are allowed, but only check within the
2062  * current leaf node.  The Btree code must check in adjacent leaf nodes.
2063  *
2064  * Return in args->index the index into the entry[] array of either
2065  * the found entry, or where the entry should have been (insert before
2066  * that entry).
2067  *
2068  * Don't change the args->value unless we find the attribute.
2069  */
2070 int
2071 xfs_attr3_leaf_lookup_int(
2072 	struct xfs_buf		*bp,
2073 	struct xfs_da_args	*args)
2074 {
2075 	struct xfs_attr_leafblock *leaf;
2076 	struct xfs_attr3_icleaf_hdr ichdr;
2077 	struct xfs_attr_leaf_entry *entry;
2078 	struct xfs_attr_leaf_entry *entries;
2079 	struct xfs_attr_leaf_name_local *name_loc;
2080 	struct xfs_attr_leaf_name_remote *name_rmt;
2081 	xfs_dahash_t		hashval;
2082 	int			probe;
2083 	int			span;
2084 
2085 	trace_xfs_attr_leaf_lookup(args);
2086 
2087 	leaf = bp->b_addr;
2088 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
2089 	entries = xfs_attr3_leaf_entryp(leaf);
2090 	ASSERT(ichdr.count < args->geo->blksize / 8);
2091 
2092 	/*
2093 	 * Binary search.  (note: small blocks will skip this loop)
2094 	 */
2095 	hashval = args->hashval;
2096 	probe = span = ichdr.count / 2;
2097 	for (entry = &entries[probe]; span > 4; entry = &entries[probe]) {
2098 		span /= 2;
2099 		if (be32_to_cpu(entry->hashval) < hashval)
2100 			probe += span;
2101 		else if (be32_to_cpu(entry->hashval) > hashval)
2102 			probe -= span;
2103 		else
2104 			break;
2105 	}
2106 	ASSERT(probe >= 0 && (!ichdr.count || probe < ichdr.count));
2107 	ASSERT(span <= 4 || be32_to_cpu(entry->hashval) == hashval);
2108 
2109 	/*
2110 	 * Since we may have duplicate hashval's, find the first matching
2111 	 * hashval in the leaf.
2112 	 */
2113 	while (probe > 0 && be32_to_cpu(entry->hashval) >= hashval) {
2114 		entry--;
2115 		probe--;
2116 	}
2117 	while (probe < ichdr.count &&
2118 	       be32_to_cpu(entry->hashval) < hashval) {
2119 		entry++;
2120 		probe++;
2121 	}
2122 	if (probe == ichdr.count || be32_to_cpu(entry->hashval) != hashval) {
2123 		args->index = probe;
2124 		return -ENOATTR;
2125 	}
2126 
2127 	/*
2128 	 * Duplicate keys may be present, so search all of them for a match.
2129 	 */
2130 	for (; probe < ichdr.count && (be32_to_cpu(entry->hashval) == hashval);
2131 			entry++, probe++) {
2132 /*
2133  * GROT: Add code to remove incomplete entries.
2134  */
2135 		/*
2136 		 * If we are looking for INCOMPLETE entries, show only those.
2137 		 * If we are looking for complete entries, show only those.
2138 		 */
2139 		if ((args->flags & XFS_ATTR_INCOMPLETE) !=
2140 		    (entry->flags & XFS_ATTR_INCOMPLETE)) {
2141 			continue;
2142 		}
2143 		if (entry->flags & XFS_ATTR_LOCAL) {
2144 			name_loc = xfs_attr3_leaf_name_local(leaf, probe);
2145 			if (name_loc->namelen != args->namelen)
2146 				continue;
2147 			if (memcmp(args->name, name_loc->nameval,
2148 							args->namelen) != 0)
2149 				continue;
2150 			if (!xfs_attr_namesp_match(args->flags, entry->flags))
2151 				continue;
2152 			args->index = probe;
2153 			return -EEXIST;
2154 		} else {
2155 			name_rmt = xfs_attr3_leaf_name_remote(leaf, probe);
2156 			if (name_rmt->namelen != args->namelen)
2157 				continue;
2158 			if (memcmp(args->name, name_rmt->name,
2159 							args->namelen) != 0)
2160 				continue;
2161 			if (!xfs_attr_namesp_match(args->flags, entry->flags))
2162 				continue;
2163 			args->index = probe;
2164 			args->rmtvaluelen = be32_to_cpu(name_rmt->valuelen);
2165 			args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2166 			args->rmtblkcnt = xfs_attr3_rmt_blocks(
2167 							args->dp->i_mount,
2168 							args->rmtvaluelen);
2169 			return -EEXIST;
2170 		}
2171 	}
2172 	args->index = probe;
2173 	return -ENOATTR;
2174 }
2175 
2176 /*
2177  * Get the value associated with an attribute name from a leaf attribute
2178  * list structure.
2179  */
2180 int
2181 xfs_attr3_leaf_getvalue(
2182 	struct xfs_buf		*bp,
2183 	struct xfs_da_args	*args)
2184 {
2185 	struct xfs_attr_leafblock *leaf;
2186 	struct xfs_attr3_icleaf_hdr ichdr;
2187 	struct xfs_attr_leaf_entry *entry;
2188 	struct xfs_attr_leaf_name_local *name_loc;
2189 	struct xfs_attr_leaf_name_remote *name_rmt;
2190 	int			valuelen;
2191 
2192 	leaf = bp->b_addr;
2193 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
2194 	ASSERT(ichdr.count < args->geo->blksize / 8);
2195 	ASSERT(args->index < ichdr.count);
2196 
2197 	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2198 	if (entry->flags & XFS_ATTR_LOCAL) {
2199 		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
2200 		ASSERT(name_loc->namelen == args->namelen);
2201 		ASSERT(memcmp(args->name, name_loc->nameval, args->namelen) == 0);
2202 		valuelen = be16_to_cpu(name_loc->valuelen);
2203 		if (args->flags & ATTR_KERNOVAL) {
2204 			args->valuelen = valuelen;
2205 			return 0;
2206 		}
2207 		if (args->valuelen < valuelen) {
2208 			args->valuelen = valuelen;
2209 			return -ERANGE;
2210 		}
2211 		args->valuelen = valuelen;
2212 		memcpy(args->value, &name_loc->nameval[args->namelen], valuelen);
2213 	} else {
2214 		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2215 		ASSERT(name_rmt->namelen == args->namelen);
2216 		ASSERT(memcmp(args->name, name_rmt->name, args->namelen) == 0);
2217 		args->rmtvaluelen = be32_to_cpu(name_rmt->valuelen);
2218 		args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2219 		args->rmtblkcnt = xfs_attr3_rmt_blocks(args->dp->i_mount,
2220 						       args->rmtvaluelen);
2221 		if (args->flags & ATTR_KERNOVAL) {
2222 			args->valuelen = args->rmtvaluelen;
2223 			return 0;
2224 		}
2225 		if (args->valuelen < args->rmtvaluelen) {
2226 			args->valuelen = args->rmtvaluelen;
2227 			return -ERANGE;
2228 		}
2229 		args->valuelen = args->rmtvaluelen;
2230 	}
2231 	return 0;
2232 }
2233 
2234 /*========================================================================
2235  * Utility routines.
2236  *========================================================================*/
2237 
2238 /*
2239  * Move the indicated entries from one leaf to another.
2240  * NOTE: this routine modifies both source and destination leaves.
2241  */
2242 /*ARGSUSED*/
2243 STATIC void
2244 xfs_attr3_leaf_moveents(
2245 	struct xfs_da_args		*args,
2246 	struct xfs_attr_leafblock	*leaf_s,
2247 	struct xfs_attr3_icleaf_hdr	*ichdr_s,
2248 	int				start_s,
2249 	struct xfs_attr_leafblock	*leaf_d,
2250 	struct xfs_attr3_icleaf_hdr	*ichdr_d,
2251 	int				start_d,
2252 	int				count)
2253 {
2254 	struct xfs_attr_leaf_entry	*entry_s;
2255 	struct xfs_attr_leaf_entry	*entry_d;
2256 	int				desti;
2257 	int				tmp;
2258 	int				i;
2259 
2260 	/*
2261 	 * Check for nothing to do.
2262 	 */
2263 	if (count == 0)
2264 		return;
2265 
2266 	/*
2267 	 * Set up environment.
2268 	 */
2269 	ASSERT(ichdr_s->magic == XFS_ATTR_LEAF_MAGIC ||
2270 	       ichdr_s->magic == XFS_ATTR3_LEAF_MAGIC);
2271 	ASSERT(ichdr_s->magic == ichdr_d->magic);
2272 	ASSERT(ichdr_s->count > 0 && ichdr_s->count < args->geo->blksize / 8);
2273 	ASSERT(ichdr_s->firstused >= (ichdr_s->count * sizeof(*entry_s))
2274 					+ xfs_attr3_leaf_hdr_size(leaf_s));
2275 	ASSERT(ichdr_d->count < args->geo->blksize / 8);
2276 	ASSERT(ichdr_d->firstused >= (ichdr_d->count * sizeof(*entry_d))
2277 					+ xfs_attr3_leaf_hdr_size(leaf_d));
2278 
2279 	ASSERT(start_s < ichdr_s->count);
2280 	ASSERT(start_d <= ichdr_d->count);
2281 	ASSERT(count <= ichdr_s->count);
2282 
2283 
2284 	/*
2285 	 * Move the entries in the destination leaf up to make a hole?
2286 	 */
2287 	if (start_d < ichdr_d->count) {
2288 		tmp  = ichdr_d->count - start_d;
2289 		tmp *= sizeof(xfs_attr_leaf_entry_t);
2290 		entry_s = &xfs_attr3_leaf_entryp(leaf_d)[start_d];
2291 		entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d + count];
2292 		memmove(entry_d, entry_s, tmp);
2293 	}
2294 
2295 	/*
2296 	 * Copy all entry's in the same (sorted) order,
2297 	 * but allocate attribute info packed and in sequence.
2298 	 */
2299 	entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2300 	entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d];
2301 	desti = start_d;
2302 	for (i = 0; i < count; entry_s++, entry_d++, desti++, i++) {
2303 		ASSERT(be16_to_cpu(entry_s->nameidx) >= ichdr_s->firstused);
2304 		tmp = xfs_attr_leaf_entsize(leaf_s, start_s + i);
2305 #ifdef GROT
2306 		/*
2307 		 * Code to drop INCOMPLETE entries.  Difficult to use as we
2308 		 * may also need to change the insertion index.  Code turned
2309 		 * off for 6.2, should be revisited later.
2310 		 */
2311 		if (entry_s->flags & XFS_ATTR_INCOMPLETE) { /* skip partials? */
2312 			memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);
2313 			ichdr_s->usedbytes -= tmp;
2314 			ichdr_s->count -= 1;
2315 			entry_d--;	/* to compensate for ++ in loop hdr */
2316 			desti--;
2317 			if ((start_s + i) < offset)
2318 				result++;	/* insertion index adjustment */
2319 		} else {
2320 #endif /* GROT */
2321 			ichdr_d->firstused -= tmp;
2322 			/* both on-disk, don't endian flip twice */
2323 			entry_d->hashval = entry_s->hashval;
2324 			entry_d->nameidx = cpu_to_be16(ichdr_d->firstused);
2325 			entry_d->flags = entry_s->flags;
2326 			ASSERT(be16_to_cpu(entry_d->nameidx) + tmp
2327 							<= args->geo->blksize);
2328 			memmove(xfs_attr3_leaf_name(leaf_d, desti),
2329 				xfs_attr3_leaf_name(leaf_s, start_s + i), tmp);
2330 			ASSERT(be16_to_cpu(entry_s->nameidx) + tmp
2331 							<= args->geo->blksize);
2332 			memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);
2333 			ichdr_s->usedbytes -= tmp;
2334 			ichdr_d->usedbytes += tmp;
2335 			ichdr_s->count -= 1;
2336 			ichdr_d->count += 1;
2337 			tmp = ichdr_d->count * sizeof(xfs_attr_leaf_entry_t)
2338 					+ xfs_attr3_leaf_hdr_size(leaf_d);
2339 			ASSERT(ichdr_d->firstused >= tmp);
2340 #ifdef GROT
2341 		}
2342 #endif /* GROT */
2343 	}
2344 
2345 	/*
2346 	 * Zero out the entries we just copied.
2347 	 */
2348 	if (start_s == ichdr_s->count) {
2349 		tmp = count * sizeof(xfs_attr_leaf_entry_t);
2350 		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2351 		ASSERT(((char *)entry_s + tmp) <=
2352 		       ((char *)leaf_s + args->geo->blksize));
2353 		memset(entry_s, 0, tmp);
2354 	} else {
2355 		/*
2356 		 * Move the remaining entries down to fill the hole,
2357 		 * then zero the entries at the top.
2358 		 */
2359 		tmp  = (ichdr_s->count - count) * sizeof(xfs_attr_leaf_entry_t);
2360 		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s + count];
2361 		entry_d = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2362 		memmove(entry_d, entry_s, tmp);
2363 
2364 		tmp = count * sizeof(xfs_attr_leaf_entry_t);
2365 		entry_s = &xfs_attr3_leaf_entryp(leaf_s)[ichdr_s->count];
2366 		ASSERT(((char *)entry_s + tmp) <=
2367 		       ((char *)leaf_s + args->geo->blksize));
2368 		memset(entry_s, 0, tmp);
2369 	}
2370 
2371 	/*
2372 	 * Fill in the freemap information
2373 	 */
2374 	ichdr_d->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_d);
2375 	ichdr_d->freemap[0].base += ichdr_d->count * sizeof(xfs_attr_leaf_entry_t);
2376 	ichdr_d->freemap[0].size = ichdr_d->firstused - ichdr_d->freemap[0].base;
2377 	ichdr_d->freemap[1].base = 0;
2378 	ichdr_d->freemap[2].base = 0;
2379 	ichdr_d->freemap[1].size = 0;
2380 	ichdr_d->freemap[2].size = 0;
2381 	ichdr_s->holes = 1;	/* leaf may not be compact */
2382 }
2383 
2384 /*
2385  * Pick up the last hashvalue from a leaf block.
2386  */
2387 xfs_dahash_t
2388 xfs_attr_leaf_lasthash(
2389 	struct xfs_buf	*bp,
2390 	int		*count)
2391 {
2392 	struct xfs_attr3_icleaf_hdr ichdr;
2393 	struct xfs_attr_leaf_entry *entries;
2394 
2395 	xfs_attr3_leaf_hdr_from_disk(&ichdr, bp->b_addr);
2396 	entries = xfs_attr3_leaf_entryp(bp->b_addr);
2397 	if (count)
2398 		*count = ichdr.count;
2399 	if (!ichdr.count)
2400 		return 0;
2401 	return be32_to_cpu(entries[ichdr.count - 1].hashval);
2402 }
2403 
2404 /*
2405  * Calculate the number of bytes used to store the indicated attribute
2406  * (whether local or remote only calculate bytes in this block).
2407  */
2408 STATIC int
2409 xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index)
2410 {
2411 	struct xfs_attr_leaf_entry *entries;
2412 	xfs_attr_leaf_name_local_t *name_loc;
2413 	xfs_attr_leaf_name_remote_t *name_rmt;
2414 	int size;
2415 
2416 	entries = xfs_attr3_leaf_entryp(leaf);
2417 	if (entries[index].flags & XFS_ATTR_LOCAL) {
2418 		name_loc = xfs_attr3_leaf_name_local(leaf, index);
2419 		size = xfs_attr_leaf_entsize_local(name_loc->namelen,
2420 						   be16_to_cpu(name_loc->valuelen));
2421 	} else {
2422 		name_rmt = xfs_attr3_leaf_name_remote(leaf, index);
2423 		size = xfs_attr_leaf_entsize_remote(name_rmt->namelen);
2424 	}
2425 	return size;
2426 }
2427 
2428 /*
2429  * Calculate the number of bytes that would be required to store the new
2430  * attribute (whether local or remote only calculate bytes in this block).
2431  * This routine decides as a side effect whether the attribute will be
2432  * a "local" or a "remote" attribute.
2433  */
2434 int
2435 xfs_attr_leaf_newentsize(
2436 	struct xfs_da_args	*args,
2437 	int			*local)
2438 {
2439 	int			size;
2440 
2441 	size = xfs_attr_leaf_entsize_local(args->namelen, args->valuelen);
2442 	if (size < xfs_attr_leaf_entsize_local_max(args->geo->blksize)) {
2443 		if (local)
2444 			*local = 1;
2445 		return size;
2446 	}
2447 	if (local)
2448 		*local = 0;
2449 	return xfs_attr_leaf_entsize_remote(args->namelen);
2450 }
2451 
2452 
2453 /*========================================================================
2454  * Manage the INCOMPLETE flag in a leaf entry
2455  *========================================================================*/
2456 
2457 /*
2458  * Clear the INCOMPLETE flag on an entry in a leaf block.
2459  */
2460 int
2461 xfs_attr3_leaf_clearflag(
2462 	struct xfs_da_args	*args)
2463 {
2464 	struct xfs_attr_leafblock *leaf;
2465 	struct xfs_attr_leaf_entry *entry;
2466 	struct xfs_attr_leaf_name_remote *name_rmt;
2467 	struct xfs_buf		*bp;
2468 	int			error;
2469 #ifdef DEBUG
2470 	struct xfs_attr3_icleaf_hdr ichdr;
2471 	xfs_attr_leaf_name_local_t *name_loc;
2472 	int namelen;
2473 	char *name;
2474 #endif /* DEBUG */
2475 
2476 	trace_xfs_attr_leaf_clearflag(args);
2477 	/*
2478 	 * Set up the operation.
2479 	 */
2480 	error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp);
2481 	if (error)
2482 		return error;
2483 
2484 	leaf = bp->b_addr;
2485 	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2486 	ASSERT(entry->flags & XFS_ATTR_INCOMPLETE);
2487 
2488 #ifdef DEBUG
2489 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
2490 	ASSERT(args->index < ichdr.count);
2491 	ASSERT(args->index >= 0);
2492 
2493 	if (entry->flags & XFS_ATTR_LOCAL) {
2494 		name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
2495 		namelen = name_loc->namelen;
2496 		name = (char *)name_loc->nameval;
2497 	} else {
2498 		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2499 		namelen = name_rmt->namelen;
2500 		name = (char *)name_rmt->name;
2501 	}
2502 	ASSERT(be32_to_cpu(entry->hashval) == args->hashval);
2503 	ASSERT(namelen == args->namelen);
2504 	ASSERT(memcmp(name, args->name, namelen) == 0);
2505 #endif /* DEBUG */
2506 
2507 	entry->flags &= ~XFS_ATTR_INCOMPLETE;
2508 	xfs_trans_log_buf(args->trans, bp,
2509 			 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2510 
2511 	if (args->rmtblkno) {
2512 		ASSERT((entry->flags & XFS_ATTR_LOCAL) == 0);
2513 		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2514 		name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2515 		name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);
2516 		xfs_trans_log_buf(args->trans, bp,
2517 			 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2518 	}
2519 
2520 	/*
2521 	 * Commit the flag value change and start the next trans in series.
2522 	 */
2523 	return xfs_trans_roll(&args->trans, args->dp);
2524 }
2525 
2526 /*
2527  * Set the INCOMPLETE flag on an entry in a leaf block.
2528  */
2529 int
2530 xfs_attr3_leaf_setflag(
2531 	struct xfs_da_args	*args)
2532 {
2533 	struct xfs_attr_leafblock *leaf;
2534 	struct xfs_attr_leaf_entry *entry;
2535 	struct xfs_attr_leaf_name_remote *name_rmt;
2536 	struct xfs_buf		*bp;
2537 	int error;
2538 #ifdef DEBUG
2539 	struct xfs_attr3_icleaf_hdr ichdr;
2540 #endif
2541 
2542 	trace_xfs_attr_leaf_setflag(args);
2543 
2544 	/*
2545 	 * Set up the operation.
2546 	 */
2547 	error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp);
2548 	if (error)
2549 		return error;
2550 
2551 	leaf = bp->b_addr;
2552 #ifdef DEBUG
2553 	xfs_attr3_leaf_hdr_from_disk(&ichdr, leaf);
2554 	ASSERT(args->index < ichdr.count);
2555 	ASSERT(args->index >= 0);
2556 #endif
2557 	entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2558 
2559 	ASSERT((entry->flags & XFS_ATTR_INCOMPLETE) == 0);
2560 	entry->flags |= XFS_ATTR_INCOMPLETE;
2561 	xfs_trans_log_buf(args->trans, bp,
2562 			XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2563 	if ((entry->flags & XFS_ATTR_LOCAL) == 0) {
2564 		name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2565 		name_rmt->valueblk = 0;
2566 		name_rmt->valuelen = 0;
2567 		xfs_trans_log_buf(args->trans, bp,
2568 			 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2569 	}
2570 
2571 	/*
2572 	 * Commit the flag value change and start the next trans in series.
2573 	 */
2574 	return xfs_trans_roll(&args->trans, args->dp);
2575 }
2576 
2577 /*
2578  * In a single transaction, clear the INCOMPLETE flag on the leaf entry
2579  * given by args->blkno/index and set the INCOMPLETE flag on the leaf
2580  * entry given by args->blkno2/index2.
2581  *
2582  * Note that they could be in different blocks, or in the same block.
2583  */
2584 int
2585 xfs_attr3_leaf_flipflags(
2586 	struct xfs_da_args	*args)
2587 {
2588 	struct xfs_attr_leafblock *leaf1;
2589 	struct xfs_attr_leafblock *leaf2;
2590 	struct xfs_attr_leaf_entry *entry1;
2591 	struct xfs_attr_leaf_entry *entry2;
2592 	struct xfs_attr_leaf_name_remote *name_rmt;
2593 	struct xfs_buf		*bp1;
2594 	struct xfs_buf		*bp2;
2595 	int error;
2596 #ifdef DEBUG
2597 	struct xfs_attr3_icleaf_hdr ichdr1;
2598 	struct xfs_attr3_icleaf_hdr ichdr2;
2599 	xfs_attr_leaf_name_local_t *name_loc;
2600 	int namelen1, namelen2;
2601 	char *name1, *name2;
2602 #endif /* DEBUG */
2603 
2604 	trace_xfs_attr_leaf_flipflags(args);
2605 
2606 	/*
2607 	 * Read the block containing the "old" attr
2608 	 */
2609 	error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp1);
2610 	if (error)
2611 		return error;
2612 
2613 	/*
2614 	 * Read the block containing the "new" attr, if it is different
2615 	 */
2616 	if (args->blkno2 != args->blkno) {
2617 		error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno2,
2618 					   -1, &bp2);
2619 		if (error)
2620 			return error;
2621 	} else {
2622 		bp2 = bp1;
2623 	}
2624 
2625 	leaf1 = bp1->b_addr;
2626 	entry1 = &xfs_attr3_leaf_entryp(leaf1)[args->index];
2627 
2628 	leaf2 = bp2->b_addr;
2629 	entry2 = &xfs_attr3_leaf_entryp(leaf2)[args->index2];
2630 
2631 #ifdef DEBUG
2632 	xfs_attr3_leaf_hdr_from_disk(&ichdr1, leaf1);
2633 	ASSERT(args->index < ichdr1.count);
2634 	ASSERT(args->index >= 0);
2635 
2636 	xfs_attr3_leaf_hdr_from_disk(&ichdr2, leaf2);
2637 	ASSERT(args->index2 < ichdr2.count);
2638 	ASSERT(args->index2 >= 0);
2639 
2640 	if (entry1->flags & XFS_ATTR_LOCAL) {
2641 		name_loc = xfs_attr3_leaf_name_local(leaf1, args->index);
2642 		namelen1 = name_loc->namelen;
2643 		name1 = (char *)name_loc->nameval;
2644 	} else {
2645 		name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);
2646 		namelen1 = name_rmt->namelen;
2647 		name1 = (char *)name_rmt->name;
2648 	}
2649 	if (entry2->flags & XFS_ATTR_LOCAL) {
2650 		name_loc = xfs_attr3_leaf_name_local(leaf2, args->index2);
2651 		namelen2 = name_loc->namelen;
2652 		name2 = (char *)name_loc->nameval;
2653 	} else {
2654 		name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);
2655 		namelen2 = name_rmt->namelen;
2656 		name2 = (char *)name_rmt->name;
2657 	}
2658 	ASSERT(be32_to_cpu(entry1->hashval) == be32_to_cpu(entry2->hashval));
2659 	ASSERT(namelen1 == namelen2);
2660 	ASSERT(memcmp(name1, name2, namelen1) == 0);
2661 #endif /* DEBUG */
2662 
2663 	ASSERT(entry1->flags & XFS_ATTR_INCOMPLETE);
2664 	ASSERT((entry2->flags & XFS_ATTR_INCOMPLETE) == 0);
2665 
2666 	entry1->flags &= ~XFS_ATTR_INCOMPLETE;
2667 	xfs_trans_log_buf(args->trans, bp1,
2668 			  XFS_DA_LOGRANGE(leaf1, entry1, sizeof(*entry1)));
2669 	if (args->rmtblkno) {
2670 		ASSERT((entry1->flags & XFS_ATTR_LOCAL) == 0);
2671 		name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);
2672 		name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2673 		name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);
2674 		xfs_trans_log_buf(args->trans, bp1,
2675 			 XFS_DA_LOGRANGE(leaf1, name_rmt, sizeof(*name_rmt)));
2676 	}
2677 
2678 	entry2->flags |= XFS_ATTR_INCOMPLETE;
2679 	xfs_trans_log_buf(args->trans, bp2,
2680 			  XFS_DA_LOGRANGE(leaf2, entry2, sizeof(*entry2)));
2681 	if ((entry2->flags & XFS_ATTR_LOCAL) == 0) {
2682 		name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);
2683 		name_rmt->valueblk = 0;
2684 		name_rmt->valuelen = 0;
2685 		xfs_trans_log_buf(args->trans, bp2,
2686 			 XFS_DA_LOGRANGE(leaf2, name_rmt, sizeof(*name_rmt)));
2687 	}
2688 
2689 	/*
2690 	 * Commit the flag value change and start the next trans in series.
2691 	 */
2692 	error = xfs_trans_roll(&args->trans, args->dp);
2693 
2694 	return error;
2695 }
2696