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