2 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3 * Copyright (c) 2013 Red Hat, Inc.
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.
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.
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
21 #include "xfs_shared.h"
22 #include "xfs_format.h"
23 #include "xfs_log_format.h"
24 #include "xfs_trans_resv.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"
35 #include "xfs_attr_sf.h"
36 #include "xfs_attr_remote.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"
50 * Routines to implement leaf blocks of attributes as Btrees of hashed names.
53 /*========================================================================
54 * Function prototypes for the kernel.
55 *========================================================================*/
58 * Routines used for growing the Btree.
60 STATIC int xfs_attr3_leaf_create(struct xfs_da_args *args,
61 xfs_dablk_t which_block, struct xfs_buf **bpp);
62 STATIC int xfs_attr3_leaf_add_work(struct xfs_buf *leaf_buffer,
63 struct xfs_attr3_icleaf_hdr *ichdr,
64 struct xfs_da_args *args, int freemap_index);
65 STATIC void xfs_attr3_leaf_compact(struct xfs_da_args *args,
66 struct xfs_attr3_icleaf_hdr *ichdr,
67 struct xfs_buf *leaf_buffer);
68 STATIC void xfs_attr3_leaf_rebalance(xfs_da_state_t *state,
69 xfs_da_state_blk_t *blk1,
70 xfs_da_state_blk_t *blk2);
71 STATIC int xfs_attr3_leaf_figure_balance(xfs_da_state_t *state,
72 xfs_da_state_blk_t *leaf_blk_1,
73 struct xfs_attr3_icleaf_hdr *ichdr1,
74 xfs_da_state_blk_t *leaf_blk_2,
75 struct xfs_attr3_icleaf_hdr *ichdr2,
76 int *number_entries_in_blk1,
77 int *number_usedbytes_in_blk1);
82 STATIC void xfs_attr3_leaf_moveents(struct xfs_da_args *args,
83 struct xfs_attr_leafblock *src_leaf,
84 struct xfs_attr3_icleaf_hdr *src_ichdr, int src_start,
85 struct xfs_attr_leafblock *dst_leaf,
86 struct xfs_attr3_icleaf_hdr *dst_ichdr, int dst_start,
88 STATIC int xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index);
91 * attr3 block 'firstused' conversion helpers.
93 * firstused refers to the offset of the first used byte of the nameval region
94 * of an attr leaf block. The region starts at the tail of the block and expands
95 * backwards towards the middle. As such, firstused is initialized to the block
96 * size for an empty leaf block and is reduced from there.
98 * The attr3 block size is pegged to the fsb size and the maximum fsb is 64k.
99 * The in-core firstused field is 32-bit and thus supports the maximum fsb size.
100 * The on-disk field is only 16-bit, however, and overflows at 64k. Since this
101 * only occurs at exactly 64k, we use zero as a magic on-disk value to represent
102 * the attr block size. The following helpers manage the conversion between the
103 * in-core and on-disk formats.
107 xfs_attr3_leaf_firstused_from_disk(
108 struct xfs_da_geometry *geo,
109 struct xfs_attr3_icleaf_hdr *to,
110 struct xfs_attr_leafblock *from)
112 struct xfs_attr3_leaf_hdr *hdr3;
114 if (from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC)) {
115 hdr3 = (struct xfs_attr3_leaf_hdr *) from;
116 to->firstused = be16_to_cpu(hdr3->firstused);
118 to->firstused = be16_to_cpu(from->hdr.firstused);
122 * Convert from the magic fsb size value to actual blocksize. This
123 * should only occur for empty blocks when the block size overflows
126 if (to->firstused == XFS_ATTR3_LEAF_NULLOFF) {
127 ASSERT(!to->count && !to->usedbytes);
128 ASSERT(geo->blksize > USHRT_MAX);
129 to->firstused = geo->blksize;
134 xfs_attr3_leaf_firstused_to_disk(
135 struct xfs_da_geometry *geo,
136 struct xfs_attr_leafblock *to,
137 struct xfs_attr3_icleaf_hdr *from)
139 struct xfs_attr3_leaf_hdr *hdr3;
142 /* magic value should only be seen on disk */
143 ASSERT(from->firstused != XFS_ATTR3_LEAF_NULLOFF);
146 * Scale down the 32-bit in-core firstused value to the 16-bit on-disk
147 * value. This only overflows at the max supported value of 64k. Use the
148 * magic on-disk value to represent block size in this case.
150 firstused = from->firstused;
151 if (firstused > USHRT_MAX) {
152 ASSERT(from->firstused == geo->blksize);
153 firstused = XFS_ATTR3_LEAF_NULLOFF;
156 if (from->magic == XFS_ATTR3_LEAF_MAGIC) {
157 hdr3 = (struct xfs_attr3_leaf_hdr *) to;
158 hdr3->firstused = cpu_to_be16(firstused);
160 to->hdr.firstused = cpu_to_be16(firstused);
165 xfs_attr3_leaf_hdr_from_disk(
166 struct xfs_da_geometry *geo,
167 struct xfs_attr3_icleaf_hdr *to,
168 struct xfs_attr_leafblock *from)
172 ASSERT(from->hdr.info.magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
173 from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
175 if (from->hdr.info.magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC)) {
176 struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)from;
178 to->forw = be32_to_cpu(hdr3->info.hdr.forw);
179 to->back = be32_to_cpu(hdr3->info.hdr.back);
180 to->magic = be16_to_cpu(hdr3->info.hdr.magic);
181 to->count = be16_to_cpu(hdr3->count);
182 to->usedbytes = be16_to_cpu(hdr3->usedbytes);
183 xfs_attr3_leaf_firstused_from_disk(geo, to, from);
184 to->holes = hdr3->holes;
186 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
187 to->freemap[i].base = be16_to_cpu(hdr3->freemap[i].base);
188 to->freemap[i].size = be16_to_cpu(hdr3->freemap[i].size);
192 to->forw = be32_to_cpu(from->hdr.info.forw);
193 to->back = be32_to_cpu(from->hdr.info.back);
194 to->magic = be16_to_cpu(from->hdr.info.magic);
195 to->count = be16_to_cpu(from->hdr.count);
196 to->usedbytes = be16_to_cpu(from->hdr.usedbytes);
197 xfs_attr3_leaf_firstused_from_disk(geo, to, from);
198 to->holes = from->hdr.holes;
200 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
201 to->freemap[i].base = be16_to_cpu(from->hdr.freemap[i].base);
202 to->freemap[i].size = be16_to_cpu(from->hdr.freemap[i].size);
207 xfs_attr3_leaf_hdr_to_disk(
208 struct xfs_da_geometry *geo,
209 struct xfs_attr_leafblock *to,
210 struct xfs_attr3_icleaf_hdr *from)
214 ASSERT(from->magic == XFS_ATTR_LEAF_MAGIC ||
215 from->magic == XFS_ATTR3_LEAF_MAGIC);
217 if (from->magic == XFS_ATTR3_LEAF_MAGIC) {
218 struct xfs_attr3_leaf_hdr *hdr3 = (struct xfs_attr3_leaf_hdr *)to;
220 hdr3->info.hdr.forw = cpu_to_be32(from->forw);
221 hdr3->info.hdr.back = cpu_to_be32(from->back);
222 hdr3->info.hdr.magic = cpu_to_be16(from->magic);
223 hdr3->count = cpu_to_be16(from->count);
224 hdr3->usedbytes = cpu_to_be16(from->usedbytes);
225 xfs_attr3_leaf_firstused_to_disk(geo, to, from);
226 hdr3->holes = from->holes;
229 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
230 hdr3->freemap[i].base = cpu_to_be16(from->freemap[i].base);
231 hdr3->freemap[i].size = cpu_to_be16(from->freemap[i].size);
235 to->hdr.info.forw = cpu_to_be32(from->forw);
236 to->hdr.info.back = cpu_to_be32(from->back);
237 to->hdr.info.magic = cpu_to_be16(from->magic);
238 to->hdr.count = cpu_to_be16(from->count);
239 to->hdr.usedbytes = cpu_to_be16(from->usedbytes);
240 xfs_attr3_leaf_firstused_to_disk(geo, to, from);
241 to->hdr.holes = from->holes;
244 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
245 to->hdr.freemap[i].base = cpu_to_be16(from->freemap[i].base);
246 to->hdr.freemap[i].size = cpu_to_be16(from->freemap[i].size);
251 xfs_attr3_leaf_verify(
254 struct xfs_mount *mp = bp->b_target->bt_mount;
255 struct xfs_attr_leafblock *leaf = bp->b_addr;
256 struct xfs_attr3_icleaf_hdr ichdr;
258 xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr, leaf);
260 if (xfs_sb_version_hascrc(&mp->m_sb)) {
261 struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
263 if (ichdr.magic != XFS_ATTR3_LEAF_MAGIC)
266 if (!uuid_equal(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid))
268 if (be64_to_cpu(hdr3->info.blkno) != bp->b_bn)
270 if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->info.lsn)))
273 if (ichdr.magic != XFS_ATTR_LEAF_MAGIC)
276 if (ichdr.count == 0)
279 /* XXX: need to range check rest of attr header values */
280 /* XXX: hash order check? */
286 xfs_attr3_leaf_write_verify(
289 struct xfs_mount *mp = bp->b_target->bt_mount;
290 struct xfs_buf_log_item *bip = bp->b_fspriv;
291 struct xfs_attr3_leaf_hdr *hdr3 = bp->b_addr;
293 if (!xfs_attr3_leaf_verify(bp)) {
294 xfs_buf_ioerror(bp, -EFSCORRUPTED);
295 xfs_verifier_error(bp);
299 if (!xfs_sb_version_hascrc(&mp->m_sb))
303 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
305 xfs_buf_update_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF);
309 * leaf/node format detection on trees is sketchy, so a node read can be done on
310 * leaf level blocks when detection identifies the tree as a node format tree
311 * incorrectly. In this case, we need to swap the verifier to match the correct
312 * format of the block being read.
315 xfs_attr3_leaf_read_verify(
318 struct xfs_mount *mp = bp->b_target->bt_mount;
320 if (xfs_sb_version_hascrc(&mp->m_sb) &&
321 !xfs_buf_verify_cksum(bp, XFS_ATTR3_LEAF_CRC_OFF))
322 xfs_buf_ioerror(bp, -EFSBADCRC);
323 else if (!xfs_attr3_leaf_verify(bp))
324 xfs_buf_ioerror(bp, -EFSCORRUPTED);
327 xfs_verifier_error(bp);
330 const struct xfs_buf_ops xfs_attr3_leaf_buf_ops = {
331 .name = "xfs_attr3_leaf",
332 .verify_read = xfs_attr3_leaf_read_verify,
333 .verify_write = xfs_attr3_leaf_write_verify,
338 struct xfs_trans *tp,
339 struct xfs_inode *dp,
341 xfs_daddr_t mappedbno,
342 struct xfs_buf **bpp)
346 err = xfs_da_read_buf(tp, dp, bno, mappedbno, bpp,
347 XFS_ATTR_FORK, &xfs_attr3_leaf_buf_ops);
349 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_ATTR_LEAF_BUF);
353 /*========================================================================
354 * Namespace helper routines
355 *========================================================================*/
358 * If namespace bits don't match return 0.
359 * If all match then return 1.
362 xfs_attr_namesp_match(int arg_flags, int ondisk_flags)
364 return XFS_ATTR_NSP_ONDISK(ondisk_flags) == XFS_ATTR_NSP_ARGS_TO_ONDISK(arg_flags);
368 /*========================================================================
369 * External routines when attribute fork size < XFS_LITINO(mp).
370 *========================================================================*/
373 * Query whether the requested number of additional bytes of extended
374 * attribute space will be able to fit inline.
376 * Returns zero if not, else the di_forkoff fork offset to be used in the
377 * literal area for attribute data once the new bytes have been added.
379 * di_forkoff must be 8 byte aligned, hence is stored as a >>3 value;
380 * special case for dev/uuid inodes, they have fixed size data forks.
383 xfs_attr_shortform_bytesfit(xfs_inode_t *dp, int bytes)
386 int minforkoff; /* lower limit on valid forkoff locations */
387 int maxforkoff; /* upper limit on valid forkoff locations */
389 xfs_mount_t *mp = dp->i_mount;
392 offset = (XFS_LITINO(mp, dp->i_d.di_version) - bytes) >> 3;
394 switch (dp->i_d.di_format) {
395 case XFS_DINODE_FMT_DEV:
396 minforkoff = roundup(sizeof(xfs_dev_t), 8) >> 3;
397 return (offset >= minforkoff) ? minforkoff : 0;
398 case XFS_DINODE_FMT_UUID:
399 minforkoff = roundup(sizeof(uuid_t), 8) >> 3;
400 return (offset >= minforkoff) ? minforkoff : 0;
404 * If the requested numbers of bytes is smaller or equal to the
405 * current attribute fork size we can always proceed.
407 * Note that if_bytes in the data fork might actually be larger than
408 * the current data fork size is due to delalloc extents. In that
409 * case either the extent count will go down when they are converted
410 * to real extents, or the delalloc conversion will take care of the
411 * literal area rebalancing.
413 if (bytes <= XFS_IFORK_ASIZE(dp))
414 return dp->i_d.di_forkoff;
417 * For attr2 we can try to move the forkoff if there is space in the
418 * literal area, but for the old format we are done if there is no
419 * space in the fixed attribute fork.
421 if (!(mp->m_flags & XFS_MOUNT_ATTR2))
424 dsize = dp->i_df.if_bytes;
426 switch (dp->i_d.di_format) {
427 case XFS_DINODE_FMT_EXTENTS:
429 * If there is no attr fork and the data fork is extents,
430 * determine if creating the default attr fork will result
431 * in the extents form migrating to btree. If so, the
432 * minimum offset only needs to be the space required for
435 if (!dp->i_d.di_forkoff && dp->i_df.if_bytes >
436 xfs_default_attroffset(dp))
437 dsize = XFS_BMDR_SPACE_CALC(MINDBTPTRS);
439 case XFS_DINODE_FMT_BTREE:
441 * If we have a data btree then keep forkoff if we have one,
442 * otherwise we are adding a new attr, so then we set
443 * minforkoff to where the btree root can finish so we have
444 * plenty of room for attrs
446 if (dp->i_d.di_forkoff) {
447 if (offset < dp->i_d.di_forkoff)
449 return dp->i_d.di_forkoff;
451 dsize = XFS_BMAP_BROOT_SPACE(mp, dp->i_df.if_broot);
456 * A data fork btree root must have space for at least
457 * MINDBTPTRS key/ptr pairs if the data fork is small or empty.
459 minforkoff = MAX(dsize, XFS_BMDR_SPACE_CALC(MINDBTPTRS));
460 minforkoff = roundup(minforkoff, 8) >> 3;
462 /* attr fork btree root can have at least this many key/ptr pairs */
463 maxforkoff = XFS_LITINO(mp, dp->i_d.di_version) -
464 XFS_BMDR_SPACE_CALC(MINABTPTRS);
465 maxforkoff = maxforkoff >> 3; /* rounded down */
467 if (offset >= maxforkoff)
469 if (offset >= minforkoff)
475 * Switch on the ATTR2 superblock bit (implies also FEATURES2)
478 xfs_sbversion_add_attr2(xfs_mount_t *mp, xfs_trans_t *tp)
480 if ((mp->m_flags & XFS_MOUNT_ATTR2) &&
481 !(xfs_sb_version_hasattr2(&mp->m_sb))) {
482 spin_lock(&mp->m_sb_lock);
483 if (!xfs_sb_version_hasattr2(&mp->m_sb)) {
484 xfs_sb_version_addattr2(&mp->m_sb);
485 spin_unlock(&mp->m_sb_lock);
488 spin_unlock(&mp->m_sb_lock);
493 * Create the initial contents of a shortform attribute list.
496 xfs_attr_shortform_create(xfs_da_args_t *args)
498 xfs_attr_sf_hdr_t *hdr;
502 trace_xfs_attr_sf_create(args);
508 ASSERT(ifp->if_bytes == 0);
509 if (dp->i_d.di_aformat == XFS_DINODE_FMT_EXTENTS) {
510 ifp->if_flags &= ~XFS_IFEXTENTS; /* just in case */
511 dp->i_d.di_aformat = XFS_DINODE_FMT_LOCAL;
512 ifp->if_flags |= XFS_IFINLINE;
514 ASSERT(ifp->if_flags & XFS_IFINLINE);
516 xfs_idata_realloc(dp, sizeof(*hdr), XFS_ATTR_FORK);
517 hdr = (struct xfs_attr_sf_hdr *)ifp->if_u1.if_data;
518 memset(hdr, 0, sizeof(*hdr));
519 hdr->totsize = cpu_to_be16(sizeof(*hdr));
520 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
524 * Add a name/value pair to the shortform attribute list.
525 * Overflow from the inode has already been checked for.
528 xfs_attr_shortform_add(xfs_da_args_t *args, int forkoff)
530 xfs_attr_shortform_t *sf;
531 xfs_attr_sf_entry_t *sfe;
537 trace_xfs_attr_sf_add(args);
541 dp->i_d.di_forkoff = forkoff;
544 ASSERT(ifp->if_flags & XFS_IFINLINE);
545 sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
547 for (i = 0; i < sf->hdr.count; sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
549 if (sfe->namelen != args->namelen)
551 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
553 if (!xfs_attr_namesp_match(args->flags, sfe->flags))
559 offset = (char *)sfe - (char *)sf;
560 size = XFS_ATTR_SF_ENTSIZE_BYNAME(args->namelen, args->valuelen);
561 xfs_idata_realloc(dp, size, XFS_ATTR_FORK);
562 sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
563 sfe = (xfs_attr_sf_entry_t *)((char *)sf + offset);
565 sfe->namelen = args->namelen;
566 sfe->valuelen = args->valuelen;
567 sfe->flags = XFS_ATTR_NSP_ARGS_TO_ONDISK(args->flags);
568 memcpy(sfe->nameval, args->name, args->namelen);
569 memcpy(&sfe->nameval[args->namelen], args->value, args->valuelen);
571 be16_add_cpu(&sf->hdr.totsize, size);
572 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_ADATA);
574 xfs_sbversion_add_attr2(mp, args->trans);
578 * After the last attribute is removed revert to original inode format,
579 * making all literal area available to the data fork once more.
582 xfs_attr_fork_remove(
583 struct xfs_inode *ip,
584 struct xfs_trans *tp)
586 xfs_idestroy_fork(ip, XFS_ATTR_FORK);
587 ip->i_d.di_forkoff = 0;
588 ip->i_d.di_aformat = XFS_DINODE_FMT_EXTENTS;
590 ASSERT(ip->i_d.di_anextents == 0);
591 ASSERT(ip->i_afp == NULL);
593 xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
597 * Remove an attribute from the shortform attribute list structure.
600 xfs_attr_shortform_remove(xfs_da_args_t *args)
602 xfs_attr_shortform_t *sf;
603 xfs_attr_sf_entry_t *sfe;
604 int base, size=0, end, totsize, i;
608 trace_xfs_attr_sf_remove(args);
612 base = sizeof(xfs_attr_sf_hdr_t);
613 sf = (xfs_attr_shortform_t *)dp->i_afp->if_u1.if_data;
616 for (i = 0; i < end; sfe = XFS_ATTR_SF_NEXTENTRY(sfe),
618 size = XFS_ATTR_SF_ENTSIZE(sfe);
619 if (sfe->namelen != args->namelen)
621 if (memcmp(sfe->nameval, args->name, args->namelen) != 0)
623 if (!xfs_attr_namesp_match(args->flags, sfe->flags))
631 * Fix up the attribute fork data, covering the hole
634 totsize = be16_to_cpu(sf->hdr.totsize);
636 memmove(&((char *)sf)[base], &((char *)sf)[end], totsize - end);
638 be16_add_cpu(&sf->hdr.totsize, -size);
641 * Fix up the start offset of the attribute fork
644 if (totsize == sizeof(xfs_attr_sf_hdr_t) &&
645 (mp->m_flags & XFS_MOUNT_ATTR2) &&
646 (dp->i_d.di_format != XFS_DINODE_FMT_BTREE) &&
647 !(args->op_flags & XFS_DA_OP_ADDNAME)) {
648 xfs_attr_fork_remove(dp, args->trans);
650 xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
651 dp->i_d.di_forkoff = xfs_attr_shortform_bytesfit(dp, totsize);
652 ASSERT(dp->i_d.di_forkoff);
653 ASSERT(totsize > sizeof(xfs_attr_sf_hdr_t) ||
654 (args->op_flags & XFS_DA_OP_ADDNAME) ||
655 !(mp->m_flags & XFS_MOUNT_ATTR2) ||
656 dp->i_d.di_format == XFS_DINODE_FMT_BTREE);
657 xfs_trans_log_inode(args->trans, dp,
658 XFS_ILOG_CORE | XFS_ILOG_ADATA);
661 xfs_sbversion_add_attr2(mp, args->trans);
667 * Look up a name in a shortform attribute list structure.
671 xfs_attr_shortform_lookup(xfs_da_args_t *args)
673 xfs_attr_shortform_t *sf;
674 xfs_attr_sf_entry_t *sfe;
678 trace_xfs_attr_sf_lookup(args);
680 ifp = args->dp->i_afp;
681 ASSERT(ifp->if_flags & XFS_IFINLINE);
682 sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
684 for (i = 0; i < sf->hdr.count;
685 sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
686 if (sfe->namelen != args->namelen)
688 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
690 if (!xfs_attr_namesp_match(args->flags, sfe->flags))
698 * Look up a name in a shortform attribute list structure.
702 xfs_attr_shortform_getvalue(xfs_da_args_t *args)
704 xfs_attr_shortform_t *sf;
705 xfs_attr_sf_entry_t *sfe;
708 ASSERT(args->dp->i_afp->if_flags == XFS_IFINLINE);
709 sf = (xfs_attr_shortform_t *)args->dp->i_afp->if_u1.if_data;
711 for (i = 0; i < sf->hdr.count;
712 sfe = XFS_ATTR_SF_NEXTENTRY(sfe), i++) {
713 if (sfe->namelen != args->namelen)
715 if (memcmp(args->name, sfe->nameval, args->namelen) != 0)
717 if (!xfs_attr_namesp_match(args->flags, sfe->flags))
719 if (args->flags & ATTR_KERNOVAL) {
720 args->valuelen = sfe->valuelen;
723 if (args->valuelen < sfe->valuelen) {
724 args->valuelen = sfe->valuelen;
727 args->valuelen = sfe->valuelen;
728 memcpy(args->value, &sfe->nameval[args->namelen],
736 * Convert from using the shortform to the leaf.
739 xfs_attr_shortform_to_leaf(xfs_da_args_t *args)
742 xfs_attr_shortform_t *sf;
743 xfs_attr_sf_entry_t *sfe;
751 trace_xfs_attr_sf_to_leaf(args);
755 sf = (xfs_attr_shortform_t *)ifp->if_u1.if_data;
756 size = be16_to_cpu(sf->hdr.totsize);
757 tmpbuffer = kmem_alloc(size, KM_SLEEP);
758 ASSERT(tmpbuffer != NULL);
759 memcpy(tmpbuffer, ifp->if_u1.if_data, size);
760 sf = (xfs_attr_shortform_t *)tmpbuffer;
762 xfs_idata_realloc(dp, -size, XFS_ATTR_FORK);
763 xfs_bmap_local_to_extents_empty(dp, XFS_ATTR_FORK);
766 error = xfs_da_grow_inode(args, &blkno);
769 * If we hit an IO error middle of the transaction inside
770 * grow_inode(), we may have inconsistent data. Bail out.
774 xfs_idata_realloc(dp, size, XFS_ATTR_FORK); /* try to put */
775 memcpy(ifp->if_u1.if_data, tmpbuffer, size); /* it back */
780 error = xfs_attr3_leaf_create(args, blkno, &bp);
782 /* xfs_attr3_leaf_create may not have instantiated a block */
783 if (bp && (xfs_da_shrink_inode(args, 0, bp) != 0))
785 xfs_idata_realloc(dp, size, XFS_ATTR_FORK); /* try to put */
786 memcpy(ifp->if_u1.if_data, tmpbuffer, size); /* it back */
790 memset((char *)&nargs, 0, sizeof(nargs));
792 nargs.geo = args->geo;
793 nargs.firstblock = args->firstblock;
794 nargs.flist = args->flist;
795 nargs.total = args->total;
796 nargs.whichfork = XFS_ATTR_FORK;
797 nargs.trans = args->trans;
798 nargs.op_flags = XFS_DA_OP_OKNOENT;
801 for (i = 0; i < sf->hdr.count; i++) {
802 nargs.name = sfe->nameval;
803 nargs.namelen = sfe->namelen;
804 nargs.value = &sfe->nameval[nargs.namelen];
805 nargs.valuelen = sfe->valuelen;
806 nargs.hashval = xfs_da_hashname(sfe->nameval,
808 nargs.flags = XFS_ATTR_NSP_ONDISK_TO_ARGS(sfe->flags);
809 error = xfs_attr3_leaf_lookup_int(bp, &nargs); /* set a->index */
810 ASSERT(error == -ENOATTR);
811 error = xfs_attr3_leaf_add(bp, &nargs);
812 ASSERT(error != -ENOSPC);
815 sfe = XFS_ATTR_SF_NEXTENTRY(sfe);
820 kmem_free(tmpbuffer);
825 * Check a leaf attribute block to see if all the entries would fit into
826 * a shortform attribute list.
829 xfs_attr_shortform_allfit(
831 struct xfs_inode *dp)
833 struct xfs_attr_leafblock *leaf;
834 struct xfs_attr_leaf_entry *entry;
835 xfs_attr_leaf_name_local_t *name_loc;
836 struct xfs_attr3_icleaf_hdr leafhdr;
839 struct xfs_mount *mp = bp->b_target->bt_mount;
842 xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &leafhdr, leaf);
843 entry = xfs_attr3_leaf_entryp(leaf);
845 bytes = sizeof(struct xfs_attr_sf_hdr);
846 for (i = 0; i < leafhdr.count; entry++, i++) {
847 if (entry->flags & XFS_ATTR_INCOMPLETE)
848 continue; /* don't copy partial entries */
849 if (!(entry->flags & XFS_ATTR_LOCAL))
851 name_loc = xfs_attr3_leaf_name_local(leaf, i);
852 if (name_loc->namelen >= XFS_ATTR_SF_ENTSIZE_MAX)
854 if (be16_to_cpu(name_loc->valuelen) >= XFS_ATTR_SF_ENTSIZE_MAX)
856 bytes += sizeof(struct xfs_attr_sf_entry) - 1
858 + be16_to_cpu(name_loc->valuelen);
860 if ((dp->i_mount->m_flags & XFS_MOUNT_ATTR2) &&
861 (dp->i_d.di_format != XFS_DINODE_FMT_BTREE) &&
862 (bytes == sizeof(struct xfs_attr_sf_hdr)))
864 return xfs_attr_shortform_bytesfit(dp, bytes);
868 * Convert a leaf attribute list to shortform attribute list
871 xfs_attr3_leaf_to_shortform(
873 struct xfs_da_args *args,
876 struct xfs_attr_leafblock *leaf;
877 struct xfs_attr3_icleaf_hdr ichdr;
878 struct xfs_attr_leaf_entry *entry;
879 struct xfs_attr_leaf_name_local *name_loc;
880 struct xfs_da_args nargs;
881 struct xfs_inode *dp = args->dp;
886 trace_xfs_attr_leaf_to_sf(args);
888 tmpbuffer = kmem_alloc(args->geo->blksize, KM_SLEEP);
892 memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);
894 leaf = (xfs_attr_leafblock_t *)tmpbuffer;
895 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
896 entry = xfs_attr3_leaf_entryp(leaf);
898 /* XXX (dgc): buffer is about to be marked stale - why zero it? */
899 memset(bp->b_addr, 0, args->geo->blksize);
902 * Clean out the prior contents of the attribute list.
904 error = xfs_da_shrink_inode(args, 0, bp);
909 ASSERT(dp->i_mount->m_flags & XFS_MOUNT_ATTR2);
910 ASSERT(dp->i_d.di_format != XFS_DINODE_FMT_BTREE);
911 xfs_attr_fork_remove(dp, args->trans);
915 xfs_attr_shortform_create(args);
918 * Copy the attributes
920 memset((char *)&nargs, 0, sizeof(nargs));
921 nargs.geo = args->geo;
923 nargs.firstblock = args->firstblock;
924 nargs.flist = args->flist;
925 nargs.total = args->total;
926 nargs.whichfork = XFS_ATTR_FORK;
927 nargs.trans = args->trans;
928 nargs.op_flags = XFS_DA_OP_OKNOENT;
930 for (i = 0; i < ichdr.count; entry++, i++) {
931 if (entry->flags & XFS_ATTR_INCOMPLETE)
932 continue; /* don't copy partial entries */
935 ASSERT(entry->flags & XFS_ATTR_LOCAL);
936 name_loc = xfs_attr3_leaf_name_local(leaf, i);
937 nargs.name = name_loc->nameval;
938 nargs.namelen = name_loc->namelen;
939 nargs.value = &name_loc->nameval[nargs.namelen];
940 nargs.valuelen = be16_to_cpu(name_loc->valuelen);
941 nargs.hashval = be32_to_cpu(entry->hashval);
942 nargs.flags = XFS_ATTR_NSP_ONDISK_TO_ARGS(entry->flags);
943 xfs_attr_shortform_add(&nargs, forkoff);
948 kmem_free(tmpbuffer);
953 * Convert from using a single leaf to a root node and a leaf.
956 xfs_attr3_leaf_to_node(
957 struct xfs_da_args *args)
959 struct xfs_attr_leafblock *leaf;
960 struct xfs_attr3_icleaf_hdr icleafhdr;
961 struct xfs_attr_leaf_entry *entries;
962 struct xfs_da_node_entry *btree;
963 struct xfs_da3_icnode_hdr icnodehdr;
964 struct xfs_da_intnode *node;
965 struct xfs_inode *dp = args->dp;
966 struct xfs_mount *mp = dp->i_mount;
967 struct xfs_buf *bp1 = NULL;
968 struct xfs_buf *bp2 = NULL;
972 trace_xfs_attr_leaf_to_node(args);
974 error = xfs_da_grow_inode(args, &blkno);
977 error = xfs_attr3_leaf_read(args->trans, dp, 0, -1, &bp1);
981 error = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp2, XFS_ATTR_FORK);
985 /* copy leaf to new buffer, update identifiers */
986 xfs_trans_buf_set_type(args->trans, bp2, XFS_BLFT_ATTR_LEAF_BUF);
987 bp2->b_ops = bp1->b_ops;
988 memcpy(bp2->b_addr, bp1->b_addr, args->geo->blksize);
989 if (xfs_sb_version_hascrc(&mp->m_sb)) {
990 struct xfs_da3_blkinfo *hdr3 = bp2->b_addr;
991 hdr3->blkno = cpu_to_be64(bp2->b_bn);
993 xfs_trans_log_buf(args->trans, bp2, 0, args->geo->blksize - 1);
996 * Set up the new root node.
998 error = xfs_da3_node_create(args, 0, 1, &bp1, XFS_ATTR_FORK);
1002 dp->d_ops->node_hdr_from_disk(&icnodehdr, node);
1003 btree = dp->d_ops->node_tree_p(node);
1006 xfs_attr3_leaf_hdr_from_disk(args->geo, &icleafhdr, leaf);
1007 entries = xfs_attr3_leaf_entryp(leaf);
1009 /* both on-disk, don't endian-flip twice */
1010 btree[0].hashval = entries[icleafhdr.count - 1].hashval;
1011 btree[0].before = cpu_to_be32(blkno);
1012 icnodehdr.count = 1;
1013 dp->d_ops->node_hdr_to_disk(node, &icnodehdr);
1014 xfs_trans_log_buf(args->trans, bp1, 0, args->geo->blksize - 1);
1020 /*========================================================================
1021 * Routines used for growing the Btree.
1022 *========================================================================*/
1025 * Create the initial contents of a leaf attribute list
1026 * or a leaf in a node attribute list.
1029 xfs_attr3_leaf_create(
1030 struct xfs_da_args *args,
1032 struct xfs_buf **bpp)
1034 struct xfs_attr_leafblock *leaf;
1035 struct xfs_attr3_icleaf_hdr ichdr;
1036 struct xfs_inode *dp = args->dp;
1037 struct xfs_mount *mp = dp->i_mount;
1041 trace_xfs_attr_leaf_create(args);
1043 error = xfs_da_get_buf(args->trans, args->dp, blkno, -1, &bp,
1047 bp->b_ops = &xfs_attr3_leaf_buf_ops;
1048 xfs_trans_buf_set_type(args->trans, bp, XFS_BLFT_ATTR_LEAF_BUF);
1050 memset(leaf, 0, args->geo->blksize);
1052 memset(&ichdr, 0, sizeof(ichdr));
1053 ichdr.firstused = args->geo->blksize;
1055 if (xfs_sb_version_hascrc(&mp->m_sb)) {
1056 struct xfs_da3_blkinfo *hdr3 = bp->b_addr;
1058 ichdr.magic = XFS_ATTR3_LEAF_MAGIC;
1060 hdr3->blkno = cpu_to_be64(bp->b_bn);
1061 hdr3->owner = cpu_to_be64(dp->i_ino);
1062 uuid_copy(&hdr3->uuid, &mp->m_sb.sb_meta_uuid);
1064 ichdr.freemap[0].base = sizeof(struct xfs_attr3_leaf_hdr);
1066 ichdr.magic = XFS_ATTR_LEAF_MAGIC;
1067 ichdr.freemap[0].base = sizeof(struct xfs_attr_leaf_hdr);
1069 ichdr.freemap[0].size = ichdr.firstused - ichdr.freemap[0].base;
1071 xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);
1072 xfs_trans_log_buf(args->trans, bp, 0, args->geo->blksize - 1);
1079 * Split the leaf node, rebalance, then add the new entry.
1082 xfs_attr3_leaf_split(
1083 struct xfs_da_state *state,
1084 struct xfs_da_state_blk *oldblk,
1085 struct xfs_da_state_blk *newblk)
1090 trace_xfs_attr_leaf_split(state->args);
1093 * Allocate space for a new leaf node.
1095 ASSERT(oldblk->magic == XFS_ATTR_LEAF_MAGIC);
1096 error = xfs_da_grow_inode(state->args, &blkno);
1099 error = xfs_attr3_leaf_create(state->args, blkno, &newblk->bp);
1102 newblk->blkno = blkno;
1103 newblk->magic = XFS_ATTR_LEAF_MAGIC;
1106 * Rebalance the entries across the two leaves.
1107 * NOTE: rebalance() currently depends on the 2nd block being empty.
1109 xfs_attr3_leaf_rebalance(state, oldblk, newblk);
1110 error = xfs_da3_blk_link(state, oldblk, newblk);
1115 * Save info on "old" attribute for "atomic rename" ops, leaf_add()
1116 * modifies the index/blkno/rmtblk/rmtblkcnt fields to show the
1117 * "new" attrs info. Will need the "old" info to remove it later.
1119 * Insert the "new" entry in the correct block.
1121 if (state->inleaf) {
1122 trace_xfs_attr_leaf_add_old(state->args);
1123 error = xfs_attr3_leaf_add(oldblk->bp, state->args);
1125 trace_xfs_attr_leaf_add_new(state->args);
1126 error = xfs_attr3_leaf_add(newblk->bp, state->args);
1130 * Update last hashval in each block since we added the name.
1132 oldblk->hashval = xfs_attr_leaf_lasthash(oldblk->bp, NULL);
1133 newblk->hashval = xfs_attr_leaf_lasthash(newblk->bp, NULL);
1138 * Add a name to the leaf attribute list structure.
1143 struct xfs_da_args *args)
1145 struct xfs_attr_leafblock *leaf;
1146 struct xfs_attr3_icleaf_hdr ichdr;
1153 trace_xfs_attr_leaf_add(args);
1156 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
1157 ASSERT(args->index >= 0 && args->index <= ichdr.count);
1158 entsize = xfs_attr_leaf_newentsize(args, NULL);
1161 * Search through freemap for first-fit on new name length.
1162 * (may need to figure in size of entry struct too)
1164 tablesize = (ichdr.count + 1) * sizeof(xfs_attr_leaf_entry_t)
1165 + xfs_attr3_leaf_hdr_size(leaf);
1166 for (sum = 0, i = XFS_ATTR_LEAF_MAPSIZE - 1; i >= 0; i--) {
1167 if (tablesize > ichdr.firstused) {
1168 sum += ichdr.freemap[i].size;
1171 if (!ichdr.freemap[i].size)
1172 continue; /* no space in this map */
1174 if (ichdr.freemap[i].base < ichdr.firstused)
1175 tmp += sizeof(xfs_attr_leaf_entry_t);
1176 if (ichdr.freemap[i].size >= tmp) {
1177 tmp = xfs_attr3_leaf_add_work(bp, &ichdr, args, i);
1180 sum += ichdr.freemap[i].size;
1184 * If there are no holes in the address space of the block,
1185 * and we don't have enough freespace, then compaction will do us
1186 * no good and we should just give up.
1188 if (!ichdr.holes && sum < entsize)
1192 * Compact the entries to coalesce free space.
1193 * This may change the hdr->count via dropping INCOMPLETE entries.
1195 xfs_attr3_leaf_compact(args, &ichdr, bp);
1198 * After compaction, the block is guaranteed to have only one
1199 * free region, in freemap[0]. If it is not big enough, give up.
1201 if (ichdr.freemap[0].size < (entsize + sizeof(xfs_attr_leaf_entry_t))) {
1206 tmp = xfs_attr3_leaf_add_work(bp, &ichdr, args, 0);
1209 xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);
1210 xfs_trans_log_buf(args->trans, bp,
1211 XFS_DA_LOGRANGE(leaf, &leaf->hdr,
1212 xfs_attr3_leaf_hdr_size(leaf)));
1217 * Add a name to a leaf attribute list structure.
1220 xfs_attr3_leaf_add_work(
1222 struct xfs_attr3_icleaf_hdr *ichdr,
1223 struct xfs_da_args *args,
1226 struct xfs_attr_leafblock *leaf;
1227 struct xfs_attr_leaf_entry *entry;
1228 struct xfs_attr_leaf_name_local *name_loc;
1229 struct xfs_attr_leaf_name_remote *name_rmt;
1230 struct xfs_mount *mp;
1234 trace_xfs_attr_leaf_add_work(args);
1237 ASSERT(mapindex >= 0 && mapindex < XFS_ATTR_LEAF_MAPSIZE);
1238 ASSERT(args->index >= 0 && args->index <= ichdr->count);
1241 * Force open some space in the entry array and fill it in.
1243 entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
1244 if (args->index < ichdr->count) {
1245 tmp = ichdr->count - args->index;
1246 tmp *= sizeof(xfs_attr_leaf_entry_t);
1247 memmove(entry + 1, entry, tmp);
1248 xfs_trans_log_buf(args->trans, bp,
1249 XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));
1254 * Allocate space for the new string (at the end of the run).
1256 mp = args->trans->t_mountp;
1257 ASSERT(ichdr->freemap[mapindex].base < args->geo->blksize);
1258 ASSERT((ichdr->freemap[mapindex].base & 0x3) == 0);
1259 ASSERT(ichdr->freemap[mapindex].size >=
1260 xfs_attr_leaf_newentsize(args, NULL));
1261 ASSERT(ichdr->freemap[mapindex].size < args->geo->blksize);
1262 ASSERT((ichdr->freemap[mapindex].size & 0x3) == 0);
1264 ichdr->freemap[mapindex].size -= xfs_attr_leaf_newentsize(args, &tmp);
1266 entry->nameidx = cpu_to_be16(ichdr->freemap[mapindex].base +
1267 ichdr->freemap[mapindex].size);
1268 entry->hashval = cpu_to_be32(args->hashval);
1269 entry->flags = tmp ? XFS_ATTR_LOCAL : 0;
1270 entry->flags |= XFS_ATTR_NSP_ARGS_TO_ONDISK(args->flags);
1271 if (args->op_flags & XFS_DA_OP_RENAME) {
1272 entry->flags |= XFS_ATTR_INCOMPLETE;
1273 if ((args->blkno2 == args->blkno) &&
1274 (args->index2 <= args->index)) {
1278 xfs_trans_log_buf(args->trans, bp,
1279 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
1280 ASSERT((args->index == 0) ||
1281 (be32_to_cpu(entry->hashval) >= be32_to_cpu((entry-1)->hashval)));
1282 ASSERT((args->index == ichdr->count - 1) ||
1283 (be32_to_cpu(entry->hashval) <= be32_to_cpu((entry+1)->hashval)));
1286 * For "remote" attribute values, simply note that we need to
1287 * allocate space for the "remote" value. We can't actually
1288 * allocate the extents in this transaction, and we can't decide
1289 * which blocks they should be as we might allocate more blocks
1290 * as part of this transaction (a split operation for example).
1292 if (entry->flags & XFS_ATTR_LOCAL) {
1293 name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
1294 name_loc->namelen = args->namelen;
1295 name_loc->valuelen = cpu_to_be16(args->valuelen);
1296 memcpy((char *)name_loc->nameval, args->name, args->namelen);
1297 memcpy((char *)&name_loc->nameval[args->namelen], args->value,
1298 be16_to_cpu(name_loc->valuelen));
1300 name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
1301 name_rmt->namelen = args->namelen;
1302 memcpy((char *)name_rmt->name, args->name, args->namelen);
1303 entry->flags |= XFS_ATTR_INCOMPLETE;
1305 name_rmt->valuelen = 0;
1306 name_rmt->valueblk = 0;
1308 args->rmtblkcnt = xfs_attr3_rmt_blocks(mp, args->valuelen);
1309 args->rmtvaluelen = args->valuelen;
1311 xfs_trans_log_buf(args->trans, bp,
1312 XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),
1313 xfs_attr_leaf_entsize(leaf, args->index)));
1316 * Update the control info for this leaf node
1318 if (be16_to_cpu(entry->nameidx) < ichdr->firstused)
1319 ichdr->firstused = be16_to_cpu(entry->nameidx);
1321 ASSERT(ichdr->firstused >= ichdr->count * sizeof(xfs_attr_leaf_entry_t)
1322 + xfs_attr3_leaf_hdr_size(leaf));
1323 tmp = (ichdr->count - 1) * sizeof(xfs_attr_leaf_entry_t)
1324 + xfs_attr3_leaf_hdr_size(leaf);
1326 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
1327 if (ichdr->freemap[i].base == tmp) {
1328 ichdr->freemap[i].base += sizeof(xfs_attr_leaf_entry_t);
1329 ichdr->freemap[i].size -=
1330 min_t(uint16_t, ichdr->freemap[i].size,
1331 sizeof(xfs_attr_leaf_entry_t));
1334 ichdr->usedbytes += xfs_attr_leaf_entsize(leaf, args->index);
1339 * Garbage collect a leaf attribute list block by copying it to a new buffer.
1342 xfs_attr3_leaf_compact(
1343 struct xfs_da_args *args,
1344 struct xfs_attr3_icleaf_hdr *ichdr_dst,
1347 struct xfs_attr_leafblock *leaf_src;
1348 struct xfs_attr_leafblock *leaf_dst;
1349 struct xfs_attr3_icleaf_hdr ichdr_src;
1350 struct xfs_trans *trans = args->trans;
1353 trace_xfs_attr_leaf_compact(args);
1355 tmpbuffer = kmem_alloc(args->geo->blksize, KM_SLEEP);
1356 memcpy(tmpbuffer, bp->b_addr, args->geo->blksize);
1357 memset(bp->b_addr, 0, args->geo->blksize);
1358 leaf_src = (xfs_attr_leafblock_t *)tmpbuffer;
1359 leaf_dst = bp->b_addr;
1362 * Copy the on-disk header back into the destination buffer to ensure
1363 * all the information in the header that is not part of the incore
1364 * header structure is preserved.
1366 memcpy(bp->b_addr, tmpbuffer, xfs_attr3_leaf_hdr_size(leaf_src));
1368 /* Initialise the incore headers */
1369 ichdr_src = *ichdr_dst; /* struct copy */
1370 ichdr_dst->firstused = args->geo->blksize;
1371 ichdr_dst->usedbytes = 0;
1372 ichdr_dst->count = 0;
1373 ichdr_dst->holes = 0;
1374 ichdr_dst->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_src);
1375 ichdr_dst->freemap[0].size = ichdr_dst->firstused -
1376 ichdr_dst->freemap[0].base;
1378 /* write the header back to initialise the underlying buffer */
1379 xfs_attr3_leaf_hdr_to_disk(args->geo, leaf_dst, ichdr_dst);
1382 * Copy all entry's in the same (sorted) order,
1383 * but allocate name/value pairs packed and in sequence.
1385 xfs_attr3_leaf_moveents(args, leaf_src, &ichdr_src, 0,
1386 leaf_dst, ichdr_dst, 0, ichdr_src.count);
1388 * this logs the entire buffer, but the caller must write the header
1389 * back to the buffer when it is finished modifying it.
1391 xfs_trans_log_buf(trans, bp, 0, args->geo->blksize - 1);
1393 kmem_free(tmpbuffer);
1397 * Compare two leaf blocks "order".
1398 * Return 0 unless leaf2 should go before leaf1.
1401 xfs_attr3_leaf_order(
1402 struct xfs_buf *leaf1_bp,
1403 struct xfs_attr3_icleaf_hdr *leaf1hdr,
1404 struct xfs_buf *leaf2_bp,
1405 struct xfs_attr3_icleaf_hdr *leaf2hdr)
1407 struct xfs_attr_leaf_entry *entries1;
1408 struct xfs_attr_leaf_entry *entries2;
1410 entries1 = xfs_attr3_leaf_entryp(leaf1_bp->b_addr);
1411 entries2 = xfs_attr3_leaf_entryp(leaf2_bp->b_addr);
1412 if (leaf1hdr->count > 0 && leaf2hdr->count > 0 &&
1413 ((be32_to_cpu(entries2[0].hashval) <
1414 be32_to_cpu(entries1[0].hashval)) ||
1415 (be32_to_cpu(entries2[leaf2hdr->count - 1].hashval) <
1416 be32_to_cpu(entries1[leaf1hdr->count - 1].hashval)))) {
1423 xfs_attr_leaf_order(
1424 struct xfs_buf *leaf1_bp,
1425 struct xfs_buf *leaf2_bp)
1427 struct xfs_attr3_icleaf_hdr ichdr1;
1428 struct xfs_attr3_icleaf_hdr ichdr2;
1429 struct xfs_mount *mp = leaf1_bp->b_target->bt_mount;
1431 xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr1, leaf1_bp->b_addr);
1432 xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr2, leaf2_bp->b_addr);
1433 return xfs_attr3_leaf_order(leaf1_bp, &ichdr1, leaf2_bp, &ichdr2);
1437 * Redistribute the attribute list entries between two leaf nodes,
1438 * taking into account the size of the new entry.
1440 * NOTE: if new block is empty, then it will get the upper half of the
1441 * old block. At present, all (one) callers pass in an empty second block.
1443 * This code adjusts the args->index/blkno and args->index2/blkno2 fields
1444 * to match what it is doing in splitting the attribute leaf block. Those
1445 * values are used in "atomic rename" operations on attributes. Note that
1446 * the "new" and "old" values can end up in different blocks.
1449 xfs_attr3_leaf_rebalance(
1450 struct xfs_da_state *state,
1451 struct xfs_da_state_blk *blk1,
1452 struct xfs_da_state_blk *blk2)
1454 struct xfs_da_args *args;
1455 struct xfs_attr_leafblock *leaf1;
1456 struct xfs_attr_leafblock *leaf2;
1457 struct xfs_attr3_icleaf_hdr ichdr1;
1458 struct xfs_attr3_icleaf_hdr ichdr2;
1459 struct xfs_attr_leaf_entry *entries1;
1460 struct xfs_attr_leaf_entry *entries2;
1468 * Set up environment.
1470 ASSERT(blk1->magic == XFS_ATTR_LEAF_MAGIC);
1471 ASSERT(blk2->magic == XFS_ATTR_LEAF_MAGIC);
1472 leaf1 = blk1->bp->b_addr;
1473 leaf2 = blk2->bp->b_addr;
1474 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr1, leaf1);
1475 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr2, leaf2);
1476 ASSERT(ichdr2.count == 0);
1479 trace_xfs_attr_leaf_rebalance(args);
1482 * Check ordering of blocks, reverse if it makes things simpler.
1484 * NOTE: Given that all (current) callers pass in an empty
1485 * second block, this code should never set "swap".
1488 if (xfs_attr3_leaf_order(blk1->bp, &ichdr1, blk2->bp, &ichdr2)) {
1489 struct xfs_da_state_blk *tmp_blk;
1490 struct xfs_attr3_icleaf_hdr tmp_ichdr;
1496 /* struct copies to swap them rather than reconverting */
1501 leaf1 = blk1->bp->b_addr;
1502 leaf2 = blk2->bp->b_addr;
1507 * Examine entries until we reduce the absolute difference in
1508 * byte usage between the two blocks to a minimum. Then get
1509 * the direction to copy and the number of elements to move.
1511 * "inleaf" is true if the new entry should be inserted into blk1.
1512 * If "swap" is also true, then reverse the sense of "inleaf".
1514 state->inleaf = xfs_attr3_leaf_figure_balance(state, blk1, &ichdr1,
1518 state->inleaf = !state->inleaf;
1521 * Move any entries required from leaf to leaf:
1523 if (count < ichdr1.count) {
1525 * Figure the total bytes to be added to the destination leaf.
1527 /* number entries being moved */
1528 count = ichdr1.count - count;
1529 space = ichdr1.usedbytes - totallen;
1530 space += count * sizeof(xfs_attr_leaf_entry_t);
1533 * leaf2 is the destination, compact it if it looks tight.
1535 max = ichdr2.firstused - xfs_attr3_leaf_hdr_size(leaf1);
1536 max -= ichdr2.count * sizeof(xfs_attr_leaf_entry_t);
1538 xfs_attr3_leaf_compact(args, &ichdr2, blk2->bp);
1541 * Move high entries from leaf1 to low end of leaf2.
1543 xfs_attr3_leaf_moveents(args, leaf1, &ichdr1,
1544 ichdr1.count - count, leaf2, &ichdr2, 0, count);
1546 } else if (count > ichdr1.count) {
1548 * I assert that since all callers pass in an empty
1549 * second buffer, this code should never execute.
1554 * Figure the total bytes to be added to the destination leaf.
1556 /* number entries being moved */
1557 count -= ichdr1.count;
1558 space = totallen - ichdr1.usedbytes;
1559 space += count * sizeof(xfs_attr_leaf_entry_t);
1562 * leaf1 is the destination, compact it if it looks tight.
1564 max = ichdr1.firstused - xfs_attr3_leaf_hdr_size(leaf1);
1565 max -= ichdr1.count * sizeof(xfs_attr_leaf_entry_t);
1567 xfs_attr3_leaf_compact(args, &ichdr1, blk1->bp);
1570 * Move low entries from leaf2 to high end of leaf1.
1572 xfs_attr3_leaf_moveents(args, leaf2, &ichdr2, 0, leaf1, &ichdr1,
1573 ichdr1.count, count);
1576 xfs_attr3_leaf_hdr_to_disk(state->args->geo, leaf1, &ichdr1);
1577 xfs_attr3_leaf_hdr_to_disk(state->args->geo, leaf2, &ichdr2);
1578 xfs_trans_log_buf(args->trans, blk1->bp, 0, args->geo->blksize - 1);
1579 xfs_trans_log_buf(args->trans, blk2->bp, 0, args->geo->blksize - 1);
1582 * Copy out last hashval in each block for B-tree code.
1584 entries1 = xfs_attr3_leaf_entryp(leaf1);
1585 entries2 = xfs_attr3_leaf_entryp(leaf2);
1586 blk1->hashval = be32_to_cpu(entries1[ichdr1.count - 1].hashval);
1587 blk2->hashval = be32_to_cpu(entries2[ichdr2.count - 1].hashval);
1590 * Adjust the expected index for insertion.
1591 * NOTE: this code depends on the (current) situation that the
1592 * second block was originally empty.
1594 * If the insertion point moved to the 2nd block, we must adjust
1595 * the index. We must also track the entry just following the
1596 * new entry for use in an "atomic rename" operation, that entry
1597 * is always the "old" entry and the "new" entry is what we are
1598 * inserting. The index/blkno fields refer to the "old" entry,
1599 * while the index2/blkno2 fields refer to the "new" entry.
1601 if (blk1->index > ichdr1.count) {
1602 ASSERT(state->inleaf == 0);
1603 blk2->index = blk1->index - ichdr1.count;
1604 args->index = args->index2 = blk2->index;
1605 args->blkno = args->blkno2 = blk2->blkno;
1606 } else if (blk1->index == ichdr1.count) {
1607 if (state->inleaf) {
1608 args->index = blk1->index;
1609 args->blkno = blk1->blkno;
1611 args->blkno2 = blk2->blkno;
1614 * On a double leaf split, the original attr location
1615 * is already stored in blkno2/index2, so don't
1616 * overwrite it overwise we corrupt the tree.
1618 blk2->index = blk1->index - ichdr1.count;
1619 args->index = blk2->index;
1620 args->blkno = blk2->blkno;
1621 if (!state->extravalid) {
1623 * set the new attr location to match the old
1624 * one and let the higher level split code
1625 * decide where in the leaf to place it.
1627 args->index2 = blk2->index;
1628 args->blkno2 = blk2->blkno;
1632 ASSERT(state->inleaf == 1);
1633 args->index = args->index2 = blk1->index;
1634 args->blkno = args->blkno2 = blk1->blkno;
1639 * Examine entries until we reduce the absolute difference in
1640 * byte usage between the two blocks to a minimum.
1641 * GROT: Is this really necessary? With other than a 512 byte blocksize,
1642 * GROT: there will always be enough room in either block for a new entry.
1643 * GROT: Do a double-split for this case?
1646 xfs_attr3_leaf_figure_balance(
1647 struct xfs_da_state *state,
1648 struct xfs_da_state_blk *blk1,
1649 struct xfs_attr3_icleaf_hdr *ichdr1,
1650 struct xfs_da_state_blk *blk2,
1651 struct xfs_attr3_icleaf_hdr *ichdr2,
1655 struct xfs_attr_leafblock *leaf1 = blk1->bp->b_addr;
1656 struct xfs_attr_leafblock *leaf2 = blk2->bp->b_addr;
1657 struct xfs_attr_leaf_entry *entry;
1668 * Examine entries until we reduce the absolute difference in
1669 * byte usage between the two blocks to a minimum.
1671 max = ichdr1->count + ichdr2->count;
1672 half = (max + 1) * sizeof(*entry);
1673 half += ichdr1->usedbytes + ichdr2->usedbytes +
1674 xfs_attr_leaf_newentsize(state->args, NULL);
1676 lastdelta = state->args->geo->blksize;
1677 entry = xfs_attr3_leaf_entryp(leaf1);
1678 for (count = index = 0; count < max; entry++, index++, count++) {
1680 #define XFS_ATTR_ABS(A) (((A) < 0) ? -(A) : (A))
1682 * The new entry is in the first block, account for it.
1684 if (count == blk1->index) {
1685 tmp = totallen + sizeof(*entry) +
1686 xfs_attr_leaf_newentsize(state->args, NULL);
1687 if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1689 lastdelta = XFS_ATTR_ABS(half - tmp);
1695 * Wrap around into the second block if necessary.
1697 if (count == ichdr1->count) {
1699 entry = xfs_attr3_leaf_entryp(leaf1);
1704 * Figure out if next leaf entry would be too much.
1706 tmp = totallen + sizeof(*entry) + xfs_attr_leaf_entsize(leaf1,
1708 if (XFS_ATTR_ABS(half - tmp) > lastdelta)
1710 lastdelta = XFS_ATTR_ABS(half - tmp);
1716 * Calculate the number of usedbytes that will end up in lower block.
1717 * If new entry not in lower block, fix up the count.
1719 totallen -= count * sizeof(*entry);
1721 totallen -= sizeof(*entry) +
1722 xfs_attr_leaf_newentsize(state->args, NULL);
1726 *usedbytesarg = totallen;
1730 /*========================================================================
1731 * Routines used for shrinking the Btree.
1732 *========================================================================*/
1735 * Check a leaf block and its neighbors to see if the block should be
1736 * collapsed into one or the other neighbor. Always keep the block
1737 * with the smaller block number.
1738 * If the current block is over 50% full, don't try to join it, return 0.
1739 * If the block is empty, fill in the state structure and return 2.
1740 * If it can be collapsed, fill in the state structure and return 1.
1741 * If nothing can be done, return 0.
1743 * GROT: allow for INCOMPLETE entries in calculation.
1746 xfs_attr3_leaf_toosmall(
1747 struct xfs_da_state *state,
1750 struct xfs_attr_leafblock *leaf;
1751 struct xfs_da_state_blk *blk;
1752 struct xfs_attr3_icleaf_hdr ichdr;
1761 trace_xfs_attr_leaf_toosmall(state->args);
1764 * Check for the degenerate case of the block being over 50% full.
1765 * If so, it's not worth even looking to see if we might be able
1766 * to coalesce with a sibling.
1768 blk = &state->path.blk[ state->path.active-1 ];
1769 leaf = blk->bp->b_addr;
1770 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr, leaf);
1771 bytes = xfs_attr3_leaf_hdr_size(leaf) +
1772 ichdr.count * sizeof(xfs_attr_leaf_entry_t) +
1774 if (bytes > (state->args->geo->blksize >> 1)) {
1775 *action = 0; /* blk over 50%, don't try to join */
1780 * Check for the degenerate case of the block being empty.
1781 * If the block is empty, we'll simply delete it, no need to
1782 * coalesce it with a sibling block. We choose (arbitrarily)
1783 * to merge with the forward block unless it is NULL.
1785 if (ichdr.count == 0) {
1787 * Make altpath point to the block we want to keep and
1788 * path point to the block we want to drop (this one).
1790 forward = (ichdr.forw != 0);
1791 memcpy(&state->altpath, &state->path, sizeof(state->path));
1792 error = xfs_da3_path_shift(state, &state->altpath, forward,
1805 * Examine each sibling block to see if we can coalesce with
1806 * at least 25% free space to spare. We need to figure out
1807 * whether to merge with the forward or the backward block.
1808 * We prefer coalescing with the lower numbered sibling so as
1809 * to shrink an attribute list over time.
1811 /* start with smaller blk num */
1812 forward = ichdr.forw < ichdr.back;
1813 for (i = 0; i < 2; forward = !forward, i++) {
1814 struct xfs_attr3_icleaf_hdr ichdr2;
1821 error = xfs_attr3_leaf_read(state->args->trans, state->args->dp,
1826 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &ichdr2, bp->b_addr);
1828 bytes = state->args->geo->blksize -
1829 (state->args->geo->blksize >> 2) -
1830 ichdr.usedbytes - ichdr2.usedbytes -
1831 ((ichdr.count + ichdr2.count) *
1832 sizeof(xfs_attr_leaf_entry_t)) -
1833 xfs_attr3_leaf_hdr_size(leaf);
1835 xfs_trans_brelse(state->args->trans, bp);
1837 break; /* fits with at least 25% to spare */
1845 * Make altpath point to the block we want to keep (the lower
1846 * numbered block) and path point to the block we want to drop.
1848 memcpy(&state->altpath, &state->path, sizeof(state->path));
1849 if (blkno < blk->blkno) {
1850 error = xfs_da3_path_shift(state, &state->altpath, forward,
1853 error = xfs_da3_path_shift(state, &state->path, forward,
1867 * Remove a name from the leaf attribute list structure.
1869 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1870 * If two leaves are 37% full, when combined they will leave 25% free.
1873 xfs_attr3_leaf_remove(
1875 struct xfs_da_args *args)
1877 struct xfs_attr_leafblock *leaf;
1878 struct xfs_attr3_icleaf_hdr ichdr;
1879 struct xfs_attr_leaf_entry *entry;
1888 trace_xfs_attr_leaf_remove(args);
1891 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
1893 ASSERT(ichdr.count > 0 && ichdr.count < args->geo->blksize / 8);
1894 ASSERT(args->index >= 0 && args->index < ichdr.count);
1895 ASSERT(ichdr.firstused >= ichdr.count * sizeof(*entry) +
1896 xfs_attr3_leaf_hdr_size(leaf));
1898 entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
1900 ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);
1901 ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);
1904 * Scan through free region table:
1905 * check for adjacency of free'd entry with an existing one,
1906 * find smallest free region in case we need to replace it,
1907 * adjust any map that borders the entry table,
1909 tablesize = ichdr.count * sizeof(xfs_attr_leaf_entry_t)
1910 + xfs_attr3_leaf_hdr_size(leaf);
1911 tmp = ichdr.freemap[0].size;
1912 before = after = -1;
1913 smallest = XFS_ATTR_LEAF_MAPSIZE - 1;
1914 entsize = xfs_attr_leaf_entsize(leaf, args->index);
1915 for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; i++) {
1916 ASSERT(ichdr.freemap[i].base < args->geo->blksize);
1917 ASSERT(ichdr.freemap[i].size < args->geo->blksize);
1918 if (ichdr.freemap[i].base == tablesize) {
1919 ichdr.freemap[i].base -= sizeof(xfs_attr_leaf_entry_t);
1920 ichdr.freemap[i].size += sizeof(xfs_attr_leaf_entry_t);
1923 if (ichdr.freemap[i].base + ichdr.freemap[i].size ==
1924 be16_to_cpu(entry->nameidx)) {
1926 } else if (ichdr.freemap[i].base ==
1927 (be16_to_cpu(entry->nameidx) + entsize)) {
1929 } else if (ichdr.freemap[i].size < tmp) {
1930 tmp = ichdr.freemap[i].size;
1936 * Coalesce adjacent freemap regions,
1937 * or replace the smallest region.
1939 if ((before >= 0) || (after >= 0)) {
1940 if ((before >= 0) && (after >= 0)) {
1941 ichdr.freemap[before].size += entsize;
1942 ichdr.freemap[before].size += ichdr.freemap[after].size;
1943 ichdr.freemap[after].base = 0;
1944 ichdr.freemap[after].size = 0;
1945 } else if (before >= 0) {
1946 ichdr.freemap[before].size += entsize;
1948 ichdr.freemap[after].base = be16_to_cpu(entry->nameidx);
1949 ichdr.freemap[after].size += entsize;
1953 * Replace smallest region (if it is smaller than free'd entry)
1955 if (ichdr.freemap[smallest].size < entsize) {
1956 ichdr.freemap[smallest].base = be16_to_cpu(entry->nameidx);
1957 ichdr.freemap[smallest].size = entsize;
1962 * Did we remove the first entry?
1964 if (be16_to_cpu(entry->nameidx) == ichdr.firstused)
1970 * Compress the remaining entries and zero out the removed stuff.
1972 memset(xfs_attr3_leaf_name(leaf, args->index), 0, entsize);
1973 ichdr.usedbytes -= entsize;
1974 xfs_trans_log_buf(args->trans, bp,
1975 XFS_DA_LOGRANGE(leaf, xfs_attr3_leaf_name(leaf, args->index),
1978 tmp = (ichdr.count - args->index) * sizeof(xfs_attr_leaf_entry_t);
1979 memmove(entry, entry + 1, tmp);
1981 xfs_trans_log_buf(args->trans, bp,
1982 XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(xfs_attr_leaf_entry_t)));
1984 entry = &xfs_attr3_leaf_entryp(leaf)[ichdr.count];
1985 memset(entry, 0, sizeof(xfs_attr_leaf_entry_t));
1988 * If we removed the first entry, re-find the first used byte
1989 * in the name area. Note that if the entry was the "firstused",
1990 * then we don't have a "hole" in our block resulting from
1991 * removing the name.
1994 tmp = args->geo->blksize;
1995 entry = xfs_attr3_leaf_entryp(leaf);
1996 for (i = ichdr.count - 1; i >= 0; entry++, i--) {
1997 ASSERT(be16_to_cpu(entry->nameidx) >= ichdr.firstused);
1998 ASSERT(be16_to_cpu(entry->nameidx) < args->geo->blksize);
2000 if (be16_to_cpu(entry->nameidx) < tmp)
2001 tmp = be16_to_cpu(entry->nameidx);
2003 ichdr.firstused = tmp;
2004 ASSERT(ichdr.firstused != 0);
2006 ichdr.holes = 1; /* mark as needing compaction */
2008 xfs_attr3_leaf_hdr_to_disk(args->geo, leaf, &ichdr);
2009 xfs_trans_log_buf(args->trans, bp,
2010 XFS_DA_LOGRANGE(leaf, &leaf->hdr,
2011 xfs_attr3_leaf_hdr_size(leaf)));
2014 * Check if leaf is less than 50% full, caller may want to
2015 * "join" the leaf with a sibling if so.
2017 tmp = ichdr.usedbytes + xfs_attr3_leaf_hdr_size(leaf) +
2018 ichdr.count * sizeof(xfs_attr_leaf_entry_t);
2020 return tmp < args->geo->magicpct; /* leaf is < 37% full */
2024 * Move all the attribute list entries from drop_leaf into save_leaf.
2027 xfs_attr3_leaf_unbalance(
2028 struct xfs_da_state *state,
2029 struct xfs_da_state_blk *drop_blk,
2030 struct xfs_da_state_blk *save_blk)
2032 struct xfs_attr_leafblock *drop_leaf = drop_blk->bp->b_addr;
2033 struct xfs_attr_leafblock *save_leaf = save_blk->bp->b_addr;
2034 struct xfs_attr3_icleaf_hdr drophdr;
2035 struct xfs_attr3_icleaf_hdr savehdr;
2036 struct xfs_attr_leaf_entry *entry;
2038 trace_xfs_attr_leaf_unbalance(state->args);
2040 drop_leaf = drop_blk->bp->b_addr;
2041 save_leaf = save_blk->bp->b_addr;
2042 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &drophdr, drop_leaf);
2043 xfs_attr3_leaf_hdr_from_disk(state->args->geo, &savehdr, save_leaf);
2044 entry = xfs_attr3_leaf_entryp(drop_leaf);
2047 * Save last hashval from dying block for later Btree fixup.
2049 drop_blk->hashval = be32_to_cpu(entry[drophdr.count - 1].hashval);
2052 * Check if we need a temp buffer, or can we do it in place.
2053 * Note that we don't check "leaf" for holes because we will
2054 * always be dropping it, toosmall() decided that for us already.
2056 if (savehdr.holes == 0) {
2058 * dest leaf has no holes, so we add there. May need
2059 * to make some room in the entry array.
2061 if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,
2062 drop_blk->bp, &drophdr)) {
2063 xfs_attr3_leaf_moveents(state->args,
2064 drop_leaf, &drophdr, 0,
2065 save_leaf, &savehdr, 0,
2068 xfs_attr3_leaf_moveents(state->args,
2069 drop_leaf, &drophdr, 0,
2070 save_leaf, &savehdr,
2071 savehdr.count, drophdr.count);
2075 * Destination has holes, so we make a temporary copy
2076 * of the leaf and add them both to that.
2078 struct xfs_attr_leafblock *tmp_leaf;
2079 struct xfs_attr3_icleaf_hdr tmphdr;
2081 tmp_leaf = kmem_zalloc(state->args->geo->blksize, KM_SLEEP);
2084 * Copy the header into the temp leaf so that all the stuff
2085 * not in the incore header is present and gets copied back in
2086 * once we've moved all the entries.
2088 memcpy(tmp_leaf, save_leaf, xfs_attr3_leaf_hdr_size(save_leaf));
2090 memset(&tmphdr, 0, sizeof(tmphdr));
2091 tmphdr.magic = savehdr.magic;
2092 tmphdr.forw = savehdr.forw;
2093 tmphdr.back = savehdr.back;
2094 tmphdr.firstused = state->args->geo->blksize;
2096 /* write the header to the temp buffer to initialise it */
2097 xfs_attr3_leaf_hdr_to_disk(state->args->geo, tmp_leaf, &tmphdr);
2099 if (xfs_attr3_leaf_order(save_blk->bp, &savehdr,
2100 drop_blk->bp, &drophdr)) {
2101 xfs_attr3_leaf_moveents(state->args,
2102 drop_leaf, &drophdr, 0,
2103 tmp_leaf, &tmphdr, 0,
2105 xfs_attr3_leaf_moveents(state->args,
2106 save_leaf, &savehdr, 0,
2107 tmp_leaf, &tmphdr, tmphdr.count,
2110 xfs_attr3_leaf_moveents(state->args,
2111 save_leaf, &savehdr, 0,
2112 tmp_leaf, &tmphdr, 0,
2114 xfs_attr3_leaf_moveents(state->args,
2115 drop_leaf, &drophdr, 0,
2116 tmp_leaf, &tmphdr, tmphdr.count,
2119 memcpy(save_leaf, tmp_leaf, state->args->geo->blksize);
2120 savehdr = tmphdr; /* struct copy */
2121 kmem_free(tmp_leaf);
2124 xfs_attr3_leaf_hdr_to_disk(state->args->geo, save_leaf, &savehdr);
2125 xfs_trans_log_buf(state->args->trans, save_blk->bp, 0,
2126 state->args->geo->blksize - 1);
2129 * Copy out last hashval in each block for B-tree code.
2131 entry = xfs_attr3_leaf_entryp(save_leaf);
2132 save_blk->hashval = be32_to_cpu(entry[savehdr.count - 1].hashval);
2135 /*========================================================================
2136 * Routines used for finding things in the Btree.
2137 *========================================================================*/
2140 * Look up a name in a leaf attribute list structure.
2141 * This is the internal routine, it uses the caller's buffer.
2143 * Note that duplicate keys are allowed, but only check within the
2144 * current leaf node. The Btree code must check in adjacent leaf nodes.
2146 * Return in args->index the index into the entry[] array of either
2147 * the found entry, or where the entry should have been (insert before
2150 * Don't change the args->value unless we find the attribute.
2153 xfs_attr3_leaf_lookup_int(
2155 struct xfs_da_args *args)
2157 struct xfs_attr_leafblock *leaf;
2158 struct xfs_attr3_icleaf_hdr ichdr;
2159 struct xfs_attr_leaf_entry *entry;
2160 struct xfs_attr_leaf_entry *entries;
2161 struct xfs_attr_leaf_name_local *name_loc;
2162 struct xfs_attr_leaf_name_remote *name_rmt;
2163 xfs_dahash_t hashval;
2167 trace_xfs_attr_leaf_lookup(args);
2170 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
2171 entries = xfs_attr3_leaf_entryp(leaf);
2172 ASSERT(ichdr.count < args->geo->blksize / 8);
2175 * Binary search. (note: small blocks will skip this loop)
2177 hashval = args->hashval;
2178 probe = span = ichdr.count / 2;
2179 for (entry = &entries[probe]; span > 4; entry = &entries[probe]) {
2181 if (be32_to_cpu(entry->hashval) < hashval)
2183 else if (be32_to_cpu(entry->hashval) > hashval)
2188 ASSERT(probe >= 0 && (!ichdr.count || probe < ichdr.count));
2189 ASSERT(span <= 4 || be32_to_cpu(entry->hashval) == hashval);
2192 * Since we may have duplicate hashval's, find the first matching
2193 * hashval in the leaf.
2195 while (probe > 0 && be32_to_cpu(entry->hashval) >= hashval) {
2199 while (probe < ichdr.count &&
2200 be32_to_cpu(entry->hashval) < hashval) {
2204 if (probe == ichdr.count || be32_to_cpu(entry->hashval) != hashval) {
2205 args->index = probe;
2210 * Duplicate keys may be present, so search all of them for a match.
2212 for (; probe < ichdr.count && (be32_to_cpu(entry->hashval) == hashval);
2215 * GROT: Add code to remove incomplete entries.
2218 * If we are looking for INCOMPLETE entries, show only those.
2219 * If we are looking for complete entries, show only those.
2221 if ((args->flags & XFS_ATTR_INCOMPLETE) !=
2222 (entry->flags & XFS_ATTR_INCOMPLETE)) {
2225 if (entry->flags & XFS_ATTR_LOCAL) {
2226 name_loc = xfs_attr3_leaf_name_local(leaf, probe);
2227 if (name_loc->namelen != args->namelen)
2229 if (memcmp(args->name, name_loc->nameval,
2230 args->namelen) != 0)
2232 if (!xfs_attr_namesp_match(args->flags, entry->flags))
2234 args->index = probe;
2237 name_rmt = xfs_attr3_leaf_name_remote(leaf, probe);
2238 if (name_rmt->namelen != args->namelen)
2240 if (memcmp(args->name, name_rmt->name,
2241 args->namelen) != 0)
2243 if (!xfs_attr_namesp_match(args->flags, entry->flags))
2245 args->index = probe;
2246 args->rmtvaluelen = be32_to_cpu(name_rmt->valuelen);
2247 args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2248 args->rmtblkcnt = xfs_attr3_rmt_blocks(
2254 args->index = probe;
2259 * Get the value associated with an attribute name from a leaf attribute
2263 xfs_attr3_leaf_getvalue(
2265 struct xfs_da_args *args)
2267 struct xfs_attr_leafblock *leaf;
2268 struct xfs_attr3_icleaf_hdr ichdr;
2269 struct xfs_attr_leaf_entry *entry;
2270 struct xfs_attr_leaf_name_local *name_loc;
2271 struct xfs_attr_leaf_name_remote *name_rmt;
2275 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
2276 ASSERT(ichdr.count < args->geo->blksize / 8);
2277 ASSERT(args->index < ichdr.count);
2279 entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2280 if (entry->flags & XFS_ATTR_LOCAL) {
2281 name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
2282 ASSERT(name_loc->namelen == args->namelen);
2283 ASSERT(memcmp(args->name, name_loc->nameval, args->namelen) == 0);
2284 valuelen = be16_to_cpu(name_loc->valuelen);
2285 if (args->flags & ATTR_KERNOVAL) {
2286 args->valuelen = valuelen;
2289 if (args->valuelen < valuelen) {
2290 args->valuelen = valuelen;
2293 args->valuelen = valuelen;
2294 memcpy(args->value, &name_loc->nameval[args->namelen], valuelen);
2296 name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2297 ASSERT(name_rmt->namelen == args->namelen);
2298 ASSERT(memcmp(args->name, name_rmt->name, args->namelen) == 0);
2299 args->rmtvaluelen = be32_to_cpu(name_rmt->valuelen);
2300 args->rmtblkno = be32_to_cpu(name_rmt->valueblk);
2301 args->rmtblkcnt = xfs_attr3_rmt_blocks(args->dp->i_mount,
2303 if (args->flags & ATTR_KERNOVAL) {
2304 args->valuelen = args->rmtvaluelen;
2307 if (args->valuelen < args->rmtvaluelen) {
2308 args->valuelen = args->rmtvaluelen;
2311 args->valuelen = args->rmtvaluelen;
2316 /*========================================================================
2318 *========================================================================*/
2321 * Move the indicated entries from one leaf to another.
2322 * NOTE: this routine modifies both source and destination leaves.
2326 xfs_attr3_leaf_moveents(
2327 struct xfs_da_args *args,
2328 struct xfs_attr_leafblock *leaf_s,
2329 struct xfs_attr3_icleaf_hdr *ichdr_s,
2331 struct xfs_attr_leafblock *leaf_d,
2332 struct xfs_attr3_icleaf_hdr *ichdr_d,
2336 struct xfs_attr_leaf_entry *entry_s;
2337 struct xfs_attr_leaf_entry *entry_d;
2343 * Check for nothing to do.
2349 * Set up environment.
2351 ASSERT(ichdr_s->magic == XFS_ATTR_LEAF_MAGIC ||
2352 ichdr_s->magic == XFS_ATTR3_LEAF_MAGIC);
2353 ASSERT(ichdr_s->magic == ichdr_d->magic);
2354 ASSERT(ichdr_s->count > 0 && ichdr_s->count < args->geo->blksize / 8);
2355 ASSERT(ichdr_s->firstused >= (ichdr_s->count * sizeof(*entry_s))
2356 + xfs_attr3_leaf_hdr_size(leaf_s));
2357 ASSERT(ichdr_d->count < args->geo->blksize / 8);
2358 ASSERT(ichdr_d->firstused >= (ichdr_d->count * sizeof(*entry_d))
2359 + xfs_attr3_leaf_hdr_size(leaf_d));
2361 ASSERT(start_s < ichdr_s->count);
2362 ASSERT(start_d <= ichdr_d->count);
2363 ASSERT(count <= ichdr_s->count);
2367 * Move the entries in the destination leaf up to make a hole?
2369 if (start_d < ichdr_d->count) {
2370 tmp = ichdr_d->count - start_d;
2371 tmp *= sizeof(xfs_attr_leaf_entry_t);
2372 entry_s = &xfs_attr3_leaf_entryp(leaf_d)[start_d];
2373 entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d + count];
2374 memmove(entry_d, entry_s, tmp);
2378 * Copy all entry's in the same (sorted) order,
2379 * but allocate attribute info packed and in sequence.
2381 entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2382 entry_d = &xfs_attr3_leaf_entryp(leaf_d)[start_d];
2384 for (i = 0; i < count; entry_s++, entry_d++, desti++, i++) {
2385 ASSERT(be16_to_cpu(entry_s->nameidx) >= ichdr_s->firstused);
2386 tmp = xfs_attr_leaf_entsize(leaf_s, start_s + i);
2389 * Code to drop INCOMPLETE entries. Difficult to use as we
2390 * may also need to change the insertion index. Code turned
2391 * off for 6.2, should be revisited later.
2393 if (entry_s->flags & XFS_ATTR_INCOMPLETE) { /* skip partials? */
2394 memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);
2395 ichdr_s->usedbytes -= tmp;
2396 ichdr_s->count -= 1;
2397 entry_d--; /* to compensate for ++ in loop hdr */
2399 if ((start_s + i) < offset)
2400 result++; /* insertion index adjustment */
2403 ichdr_d->firstused -= tmp;
2404 /* both on-disk, don't endian flip twice */
2405 entry_d->hashval = entry_s->hashval;
2406 entry_d->nameidx = cpu_to_be16(ichdr_d->firstused);
2407 entry_d->flags = entry_s->flags;
2408 ASSERT(be16_to_cpu(entry_d->nameidx) + tmp
2409 <= args->geo->blksize);
2410 memmove(xfs_attr3_leaf_name(leaf_d, desti),
2411 xfs_attr3_leaf_name(leaf_s, start_s + i), tmp);
2412 ASSERT(be16_to_cpu(entry_s->nameidx) + tmp
2413 <= args->geo->blksize);
2414 memset(xfs_attr3_leaf_name(leaf_s, start_s + i), 0, tmp);
2415 ichdr_s->usedbytes -= tmp;
2416 ichdr_d->usedbytes += tmp;
2417 ichdr_s->count -= 1;
2418 ichdr_d->count += 1;
2419 tmp = ichdr_d->count * sizeof(xfs_attr_leaf_entry_t)
2420 + xfs_attr3_leaf_hdr_size(leaf_d);
2421 ASSERT(ichdr_d->firstused >= tmp);
2428 * Zero out the entries we just copied.
2430 if (start_s == ichdr_s->count) {
2431 tmp = count * sizeof(xfs_attr_leaf_entry_t);
2432 entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2433 ASSERT(((char *)entry_s + tmp) <=
2434 ((char *)leaf_s + args->geo->blksize));
2435 memset(entry_s, 0, tmp);
2438 * Move the remaining entries down to fill the hole,
2439 * then zero the entries at the top.
2441 tmp = (ichdr_s->count - count) * sizeof(xfs_attr_leaf_entry_t);
2442 entry_s = &xfs_attr3_leaf_entryp(leaf_s)[start_s + count];
2443 entry_d = &xfs_attr3_leaf_entryp(leaf_s)[start_s];
2444 memmove(entry_d, entry_s, tmp);
2446 tmp = count * sizeof(xfs_attr_leaf_entry_t);
2447 entry_s = &xfs_attr3_leaf_entryp(leaf_s)[ichdr_s->count];
2448 ASSERT(((char *)entry_s + tmp) <=
2449 ((char *)leaf_s + args->geo->blksize));
2450 memset(entry_s, 0, tmp);
2454 * Fill in the freemap information
2456 ichdr_d->freemap[0].base = xfs_attr3_leaf_hdr_size(leaf_d);
2457 ichdr_d->freemap[0].base += ichdr_d->count * sizeof(xfs_attr_leaf_entry_t);
2458 ichdr_d->freemap[0].size = ichdr_d->firstused - ichdr_d->freemap[0].base;
2459 ichdr_d->freemap[1].base = 0;
2460 ichdr_d->freemap[2].base = 0;
2461 ichdr_d->freemap[1].size = 0;
2462 ichdr_d->freemap[2].size = 0;
2463 ichdr_s->holes = 1; /* leaf may not be compact */
2467 * Pick up the last hashvalue from a leaf block.
2470 xfs_attr_leaf_lasthash(
2474 struct xfs_attr3_icleaf_hdr ichdr;
2475 struct xfs_attr_leaf_entry *entries;
2476 struct xfs_mount *mp = bp->b_target->bt_mount;
2478 xfs_attr3_leaf_hdr_from_disk(mp->m_attr_geo, &ichdr, bp->b_addr);
2479 entries = xfs_attr3_leaf_entryp(bp->b_addr);
2481 *count = ichdr.count;
2484 return be32_to_cpu(entries[ichdr.count - 1].hashval);
2488 * Calculate the number of bytes used to store the indicated attribute
2489 * (whether local or remote only calculate bytes in this block).
2492 xfs_attr_leaf_entsize(xfs_attr_leafblock_t *leaf, int index)
2494 struct xfs_attr_leaf_entry *entries;
2495 xfs_attr_leaf_name_local_t *name_loc;
2496 xfs_attr_leaf_name_remote_t *name_rmt;
2499 entries = xfs_attr3_leaf_entryp(leaf);
2500 if (entries[index].flags & XFS_ATTR_LOCAL) {
2501 name_loc = xfs_attr3_leaf_name_local(leaf, index);
2502 size = xfs_attr_leaf_entsize_local(name_loc->namelen,
2503 be16_to_cpu(name_loc->valuelen));
2505 name_rmt = xfs_attr3_leaf_name_remote(leaf, index);
2506 size = xfs_attr_leaf_entsize_remote(name_rmt->namelen);
2512 * Calculate the number of bytes that would be required to store the new
2513 * attribute (whether local or remote only calculate bytes in this block).
2514 * This routine decides as a side effect whether the attribute will be
2515 * a "local" or a "remote" attribute.
2518 xfs_attr_leaf_newentsize(
2519 struct xfs_da_args *args,
2524 size = xfs_attr_leaf_entsize_local(args->namelen, args->valuelen);
2525 if (size < xfs_attr_leaf_entsize_local_max(args->geo->blksize)) {
2532 return xfs_attr_leaf_entsize_remote(args->namelen);
2536 /*========================================================================
2537 * Manage the INCOMPLETE flag in a leaf entry
2538 *========================================================================*/
2541 * Clear the INCOMPLETE flag on an entry in a leaf block.
2544 xfs_attr3_leaf_clearflag(
2545 struct xfs_da_args *args)
2547 struct xfs_attr_leafblock *leaf;
2548 struct xfs_attr_leaf_entry *entry;
2549 struct xfs_attr_leaf_name_remote *name_rmt;
2553 struct xfs_attr3_icleaf_hdr ichdr;
2554 xfs_attr_leaf_name_local_t *name_loc;
2559 trace_xfs_attr_leaf_clearflag(args);
2561 * Set up the operation.
2563 error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp);
2568 entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2569 ASSERT(entry->flags & XFS_ATTR_INCOMPLETE);
2572 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
2573 ASSERT(args->index < ichdr.count);
2574 ASSERT(args->index >= 0);
2576 if (entry->flags & XFS_ATTR_LOCAL) {
2577 name_loc = xfs_attr3_leaf_name_local(leaf, args->index);
2578 namelen = name_loc->namelen;
2579 name = (char *)name_loc->nameval;
2581 name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2582 namelen = name_rmt->namelen;
2583 name = (char *)name_rmt->name;
2585 ASSERT(be32_to_cpu(entry->hashval) == args->hashval);
2586 ASSERT(namelen == args->namelen);
2587 ASSERT(memcmp(name, args->name, namelen) == 0);
2590 entry->flags &= ~XFS_ATTR_INCOMPLETE;
2591 xfs_trans_log_buf(args->trans, bp,
2592 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2594 if (args->rmtblkno) {
2595 ASSERT((entry->flags & XFS_ATTR_LOCAL) == 0);
2596 name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2597 name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2598 name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);
2599 xfs_trans_log_buf(args->trans, bp,
2600 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2604 * Commit the flag value change and start the next trans in series.
2606 return xfs_trans_roll(&args->trans, args->dp);
2610 * Set the INCOMPLETE flag on an entry in a leaf block.
2613 xfs_attr3_leaf_setflag(
2614 struct xfs_da_args *args)
2616 struct xfs_attr_leafblock *leaf;
2617 struct xfs_attr_leaf_entry *entry;
2618 struct xfs_attr_leaf_name_remote *name_rmt;
2622 struct xfs_attr3_icleaf_hdr ichdr;
2625 trace_xfs_attr_leaf_setflag(args);
2628 * Set up the operation.
2630 error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp);
2636 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr, leaf);
2637 ASSERT(args->index < ichdr.count);
2638 ASSERT(args->index >= 0);
2640 entry = &xfs_attr3_leaf_entryp(leaf)[args->index];
2642 ASSERT((entry->flags & XFS_ATTR_INCOMPLETE) == 0);
2643 entry->flags |= XFS_ATTR_INCOMPLETE;
2644 xfs_trans_log_buf(args->trans, bp,
2645 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
2646 if ((entry->flags & XFS_ATTR_LOCAL) == 0) {
2647 name_rmt = xfs_attr3_leaf_name_remote(leaf, args->index);
2648 name_rmt->valueblk = 0;
2649 name_rmt->valuelen = 0;
2650 xfs_trans_log_buf(args->trans, bp,
2651 XFS_DA_LOGRANGE(leaf, name_rmt, sizeof(*name_rmt)));
2655 * Commit the flag value change and start the next trans in series.
2657 return xfs_trans_roll(&args->trans, args->dp);
2661 * In a single transaction, clear the INCOMPLETE flag on the leaf entry
2662 * given by args->blkno/index and set the INCOMPLETE flag on the leaf
2663 * entry given by args->blkno2/index2.
2665 * Note that they could be in different blocks, or in the same block.
2668 xfs_attr3_leaf_flipflags(
2669 struct xfs_da_args *args)
2671 struct xfs_attr_leafblock *leaf1;
2672 struct xfs_attr_leafblock *leaf2;
2673 struct xfs_attr_leaf_entry *entry1;
2674 struct xfs_attr_leaf_entry *entry2;
2675 struct xfs_attr_leaf_name_remote *name_rmt;
2676 struct xfs_buf *bp1;
2677 struct xfs_buf *bp2;
2680 struct xfs_attr3_icleaf_hdr ichdr1;
2681 struct xfs_attr3_icleaf_hdr ichdr2;
2682 xfs_attr_leaf_name_local_t *name_loc;
2683 int namelen1, namelen2;
2684 char *name1, *name2;
2687 trace_xfs_attr_leaf_flipflags(args);
2690 * Read the block containing the "old" attr
2692 error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno, -1, &bp1);
2697 * Read the block containing the "new" attr, if it is different
2699 if (args->blkno2 != args->blkno) {
2700 error = xfs_attr3_leaf_read(args->trans, args->dp, args->blkno2,
2708 leaf1 = bp1->b_addr;
2709 entry1 = &xfs_attr3_leaf_entryp(leaf1)[args->index];
2711 leaf2 = bp2->b_addr;
2712 entry2 = &xfs_attr3_leaf_entryp(leaf2)[args->index2];
2715 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr1, leaf1);
2716 ASSERT(args->index < ichdr1.count);
2717 ASSERT(args->index >= 0);
2719 xfs_attr3_leaf_hdr_from_disk(args->geo, &ichdr2, leaf2);
2720 ASSERT(args->index2 < ichdr2.count);
2721 ASSERT(args->index2 >= 0);
2723 if (entry1->flags & XFS_ATTR_LOCAL) {
2724 name_loc = xfs_attr3_leaf_name_local(leaf1, args->index);
2725 namelen1 = name_loc->namelen;
2726 name1 = (char *)name_loc->nameval;
2728 name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);
2729 namelen1 = name_rmt->namelen;
2730 name1 = (char *)name_rmt->name;
2732 if (entry2->flags & XFS_ATTR_LOCAL) {
2733 name_loc = xfs_attr3_leaf_name_local(leaf2, args->index2);
2734 namelen2 = name_loc->namelen;
2735 name2 = (char *)name_loc->nameval;
2737 name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);
2738 namelen2 = name_rmt->namelen;
2739 name2 = (char *)name_rmt->name;
2741 ASSERT(be32_to_cpu(entry1->hashval) == be32_to_cpu(entry2->hashval));
2742 ASSERT(namelen1 == namelen2);
2743 ASSERT(memcmp(name1, name2, namelen1) == 0);
2746 ASSERT(entry1->flags & XFS_ATTR_INCOMPLETE);
2747 ASSERT((entry2->flags & XFS_ATTR_INCOMPLETE) == 0);
2749 entry1->flags &= ~XFS_ATTR_INCOMPLETE;
2750 xfs_trans_log_buf(args->trans, bp1,
2751 XFS_DA_LOGRANGE(leaf1, entry1, sizeof(*entry1)));
2752 if (args->rmtblkno) {
2753 ASSERT((entry1->flags & XFS_ATTR_LOCAL) == 0);
2754 name_rmt = xfs_attr3_leaf_name_remote(leaf1, args->index);
2755 name_rmt->valueblk = cpu_to_be32(args->rmtblkno);
2756 name_rmt->valuelen = cpu_to_be32(args->rmtvaluelen);
2757 xfs_trans_log_buf(args->trans, bp1,
2758 XFS_DA_LOGRANGE(leaf1, name_rmt, sizeof(*name_rmt)));
2761 entry2->flags |= XFS_ATTR_INCOMPLETE;
2762 xfs_trans_log_buf(args->trans, bp2,
2763 XFS_DA_LOGRANGE(leaf2, entry2, sizeof(*entry2)));
2764 if ((entry2->flags & XFS_ATTR_LOCAL) == 0) {
2765 name_rmt = xfs_attr3_leaf_name_remote(leaf2, args->index2);
2766 name_rmt->valueblk = 0;
2767 name_rmt->valuelen = 0;
2768 xfs_trans_log_buf(args->trans, bp2,
2769 XFS_DA_LOGRANGE(leaf2, name_rmt, sizeof(*name_rmt)));
2773 * Commit the flag value change and start the next trans in series.
2775 error = xfs_trans_roll(&args->trans, args->dp);