1/* 2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc. 3 * All Rights Reserved. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope that it would be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write the Free Software Foundation, 16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18#include "xfs.h" 19#include "xfs_fs.h" 20#include "xfs_types.h" 21#include "xfs_log.h" 22#include "xfs_inum.h" 23#include "xfs_trans.h" 24#include "xfs_sb.h" 25#include "xfs_dir2.h" 26#include "xfs_dmapi.h" 27#include "xfs_mount.h" 28#include "xfs_da_btree.h" 29#include "xfs_bmap_btree.h" 30#include "xfs_dir2_sf.h" 31#include "xfs_attr_sf.h" 32#include "xfs_dinode.h" 33#include "xfs_inode.h" 34#include "xfs_dir2_data.h" 35#include "xfs_dir2_leaf.h" 36#include "xfs_dir2_block.h" 37#include "xfs_error.h" 38 39#ifdef DEBUG 40/* 41 * Check the consistency of the data block. 42 * The input can also be a block-format directory. 43 * Pop an assert if we find anything bad. 44 */ 45void 46xfs_dir2_data_check( 47 xfs_inode_t *dp, /* incore inode pointer */ 48 xfs_dabuf_t *bp) /* data block's buffer */ 49{ 50 xfs_dir2_dataptr_t addr; /* addr for leaf lookup */ 51 xfs_dir2_data_free_t *bf; /* bestfree table */ 52 xfs_dir2_block_tail_t *btp=NULL; /* block tail */ 53 int count; /* count of entries found */ 54 xfs_dir2_data_t *d; /* data block pointer */ 55 xfs_dir2_data_entry_t *dep; /* data entry */ 56 xfs_dir2_data_free_t *dfp; /* bestfree entry */ 57 xfs_dir2_data_unused_t *dup; /* unused entry */ 58 char *endp; /* end of useful data */ 59 int freeseen; /* mask of bestfrees seen */ 60 xfs_dahash_t hash; /* hash of current name */ 61 int i; /* leaf index */ 62 int lastfree; /* last entry was unused */ 63 xfs_dir2_leaf_entry_t *lep=NULL; /* block leaf entries */ 64 xfs_mount_t *mp; /* filesystem mount point */ 65 char *p; /* current data position */ 66 int stale; /* count of stale leaves */ 67 68 mp = dp->i_mount; 69 d = bp->data; 70 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 71 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 72 bf = d->hdr.bestfree; 73 p = (char *)d->u; 74 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) { 75 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d); 76 lep = XFS_DIR2_BLOCK_LEAF_P(btp); 77 endp = (char *)lep; 78 } else 79 endp = (char *)d + mp->m_dirblksize; 80 count = lastfree = freeseen = 0; 81 /* 82 * Account for zero bestfree entries. 83 */ 84 if (!bf[0].length) { 85 ASSERT(!bf[0].offset); 86 freeseen |= 1 << 0; 87 } 88 if (!bf[1].length) { 89 ASSERT(!bf[1].offset); 90 freeseen |= 1 << 1; 91 } 92 if (!bf[2].length) { 93 ASSERT(!bf[2].offset); 94 freeseen |= 1 << 2; 95 } 96 ASSERT(be16_to_cpu(bf[0].length) >= be16_to_cpu(bf[1].length)); 97 ASSERT(be16_to_cpu(bf[1].length) >= be16_to_cpu(bf[2].length)); 98 /* 99 * Loop over the data/unused entries. 100 */ 101 while (p < endp) { 102 dup = (xfs_dir2_data_unused_t *)p; 103 /* 104 * If it's unused, look for the space in the bestfree table. 105 * If we find it, account for that, else make sure it 106 * doesn't need to be there. 107 */ 108 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 109 ASSERT(lastfree == 0); 110 ASSERT(be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup)) == 111 (char *)dup - (char *)d); 112 dfp = xfs_dir2_data_freefind(d, dup); 113 if (dfp) { 114 i = (int)(dfp - bf); 115 ASSERT((freeseen & (1 << i)) == 0); 116 freeseen |= 1 << i; 117 } else { 118 ASSERT(be16_to_cpu(dup->length) <= 119 be16_to_cpu(bf[2].length)); 120 } 121 p += be16_to_cpu(dup->length); 122 lastfree = 1; 123 continue; 124 } 125 /* 126 * It's a real entry. Validate the fields. 127 * If this is a block directory then make sure it's 128 * in the leaf section of the block. 129 * The linear search is crude but this is DEBUG code. 130 */ 131 dep = (xfs_dir2_data_entry_t *)p; 132 ASSERT(dep->namelen != 0); 133 ASSERT(xfs_dir_ino_validate(mp, be64_to_cpu(dep->inumber)) == 0); 134 ASSERT(be16_to_cpu(*XFS_DIR2_DATA_ENTRY_TAG_P(dep)) == 135 (char *)dep - (char *)d); 136 count++; 137 lastfree = 0; 138 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) { 139 addr = XFS_DIR2_DB_OFF_TO_DATAPTR(mp, mp->m_dirdatablk, 140 (xfs_dir2_data_aoff_t) 141 ((char *)dep - (char *)d)); 142 hash = xfs_da_hashname((char *)dep->name, dep->namelen); 143 for (i = 0; i < be32_to_cpu(btp->count); i++) { 144 if (be32_to_cpu(lep[i].address) == addr && 145 be32_to_cpu(lep[i].hashval) == hash) 146 break; 147 } 148 ASSERT(i < be32_to_cpu(btp->count)); 149 } 150 p += XFS_DIR2_DATA_ENTSIZE(dep->namelen); 151 } 152 /* 153 * Need to have seen all the entries and all the bestfree slots. 154 */ 155 ASSERT(freeseen == 7); 156 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) { 157 for (i = stale = 0; i < be32_to_cpu(btp->count); i++) { 158 if (be32_to_cpu(lep[i].address) == XFS_DIR2_NULL_DATAPTR) 159 stale++; 160 if (i > 0) 161 ASSERT(be32_to_cpu(lep[i].hashval) >= be32_to_cpu(lep[i - 1].hashval)); 162 } 163 ASSERT(count == be32_to_cpu(btp->count) - be32_to_cpu(btp->stale)); 164 ASSERT(stale == be32_to_cpu(btp->stale)); 165 } 166} 167#endif 168 169/* 170 * Given a data block and an unused entry from that block, 171 * return the bestfree entry if any that corresponds to it. 172 */ 173xfs_dir2_data_free_t * 174xfs_dir2_data_freefind( 175 xfs_dir2_data_t *d, /* data block */ 176 xfs_dir2_data_unused_t *dup) /* data unused entry */ 177{ 178 xfs_dir2_data_free_t *dfp; /* bestfree entry */ 179 xfs_dir2_data_aoff_t off; /* offset value needed */ 180#if defined(DEBUG) && defined(__KERNEL__) 181 int matched; /* matched the value */ 182 int seenzero; /* saw a 0 bestfree entry */ 183#endif 184 185 off = (xfs_dir2_data_aoff_t)((char *)dup - (char *)d); 186#if defined(DEBUG) && defined(__KERNEL__) 187 /* 188 * Validate some consistency in the bestfree table. 189 * Check order, non-overlapping entries, and if we find the 190 * one we're looking for it has to be exact. 191 */ 192 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 193 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 194 for (dfp = &d->hdr.bestfree[0], seenzero = matched = 0; 195 dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT]; 196 dfp++) { 197 if (!dfp->offset) { 198 ASSERT(!dfp->length); 199 seenzero = 1; 200 continue; 201 } 202 ASSERT(seenzero == 0); 203 if (be16_to_cpu(dfp->offset) == off) { 204 matched = 1; 205 ASSERT(dfp->length == dup->length); 206 } else if (off < be16_to_cpu(dfp->offset)) 207 ASSERT(off + be16_to_cpu(dup->length) <= be16_to_cpu(dfp->offset)); 208 else 209 ASSERT(be16_to_cpu(dfp->offset) + be16_to_cpu(dfp->length) <= off); 210 ASSERT(matched || be16_to_cpu(dfp->length) >= be16_to_cpu(dup->length)); 211 if (dfp > &d->hdr.bestfree[0]) 212 ASSERT(be16_to_cpu(dfp[-1].length) >= be16_to_cpu(dfp[0].length)); 213 } 214#endif 215 /* 216 * If this is smaller than the smallest bestfree entry, 217 * it can't be there since they're sorted. 218 */ 219 if (be16_to_cpu(dup->length) < 220 be16_to_cpu(d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT - 1].length)) 221 return NULL; 222 /* 223 * Look at the three bestfree entries for our guy. 224 */ 225 for (dfp = &d->hdr.bestfree[0]; 226 dfp < &d->hdr.bestfree[XFS_DIR2_DATA_FD_COUNT]; 227 dfp++) { 228 if (!dfp->offset) 229 return NULL; 230 if (be16_to_cpu(dfp->offset) == off) 231 return dfp; 232 } 233 /* 234 * Didn't find it. This only happens if there are duplicate lengths. 235 */ 236 return NULL; 237} 238 239/* 240 * Insert an unused-space entry into the bestfree table. 241 */ 242xfs_dir2_data_free_t * /* entry inserted */ 243xfs_dir2_data_freeinsert( 244 xfs_dir2_data_t *d, /* data block pointer */ 245 xfs_dir2_data_unused_t *dup, /* unused space */ 246 int *loghead) /* log the data header (out) */ 247{ 248 xfs_dir2_data_free_t *dfp; /* bestfree table pointer */ 249 xfs_dir2_data_free_t new; /* new bestfree entry */ 250 251#ifdef __KERNEL__ 252 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 253 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 254#endif 255 dfp = d->hdr.bestfree; 256 new.length = dup->length; 257 new.offset = cpu_to_be16((char *)dup - (char *)d); 258 /* 259 * Insert at position 0, 1, or 2; or not at all. 260 */ 261 if (be16_to_cpu(new.length) > be16_to_cpu(dfp[0].length)) { 262 dfp[2] = dfp[1]; 263 dfp[1] = dfp[0]; 264 dfp[0] = new; 265 *loghead = 1; 266 return &dfp[0]; 267 } 268 if (be16_to_cpu(new.length) > be16_to_cpu(dfp[1].length)) { 269 dfp[2] = dfp[1]; 270 dfp[1] = new; 271 *loghead = 1; 272 return &dfp[1]; 273 } 274 if (be16_to_cpu(new.length) > be16_to_cpu(dfp[2].length)) { 275 dfp[2] = new; 276 *loghead = 1; 277 return &dfp[2]; 278 } 279 return NULL; 280} 281 282/* 283 * Remove a bestfree entry from the table. 284 */ 285STATIC void 286xfs_dir2_data_freeremove( 287 xfs_dir2_data_t *d, /* data block pointer */ 288 xfs_dir2_data_free_t *dfp, /* bestfree entry pointer */ 289 int *loghead) /* out: log data header */ 290{ 291#ifdef __KERNEL__ 292 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 293 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 294#endif 295 /* 296 * It's the first entry, slide the next 2 up. 297 */ 298 if (dfp == &d->hdr.bestfree[0]) { 299 d->hdr.bestfree[0] = d->hdr.bestfree[1]; 300 d->hdr.bestfree[1] = d->hdr.bestfree[2]; 301 } 302 /* 303 * It's the second entry, slide the 3rd entry up. 304 */ 305 else if (dfp == &d->hdr.bestfree[1]) 306 d->hdr.bestfree[1] = d->hdr.bestfree[2]; 307 /* 308 * Must be the last entry. 309 */ 310 else 311 ASSERT(dfp == &d->hdr.bestfree[2]); 312 /* 313 * Clear the 3rd entry, must be zero now. 314 */ 315 d->hdr.bestfree[2].length = 0; 316 d->hdr.bestfree[2].offset = 0; 317 *loghead = 1; 318} 319 320/* 321 * Given a data block, reconstruct its bestfree map. 322 */ 323void 324xfs_dir2_data_freescan( 325 xfs_mount_t *mp, /* filesystem mount point */ 326 xfs_dir2_data_t *d, /* data block pointer */ 327 int *loghead) /* out: log data header */ 328{ 329 xfs_dir2_block_tail_t *btp; /* block tail */ 330 xfs_dir2_data_entry_t *dep; /* active data entry */ 331 xfs_dir2_data_unused_t *dup; /* unused data entry */ 332 char *endp; /* end of block's data */ 333 char *p; /* current entry pointer */ 334 335#ifdef __KERNEL__ 336 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 337 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 338#endif 339 /* 340 * Start by clearing the table. 341 */ 342 memset(d->hdr.bestfree, 0, sizeof(d->hdr.bestfree)); 343 *loghead = 1; 344 /* 345 * Set up pointers. 346 */ 347 p = (char *)d->u; 348 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC) { 349 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d); 350 endp = (char *)XFS_DIR2_BLOCK_LEAF_P(btp); 351 } else 352 endp = (char *)d + mp->m_dirblksize; 353 /* 354 * Loop over the block's entries. 355 */ 356 while (p < endp) { 357 dup = (xfs_dir2_data_unused_t *)p; 358 /* 359 * If it's a free entry, insert it. 360 */ 361 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 362 ASSERT((char *)dup - (char *)d == 363 be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup))); 364 xfs_dir2_data_freeinsert(d, dup, loghead); 365 p += be16_to_cpu(dup->length); 366 } 367 /* 368 * For active entries, check their tags and skip them. 369 */ 370 else { 371 dep = (xfs_dir2_data_entry_t *)p; 372 ASSERT((char *)dep - (char *)d == 373 be16_to_cpu(*XFS_DIR2_DATA_ENTRY_TAG_P(dep))); 374 p += XFS_DIR2_DATA_ENTSIZE(dep->namelen); 375 } 376 } 377} 378 379/* 380 * Initialize a data block at the given block number in the directory. 381 * Give back the buffer for the created block. 382 */ 383int /* error */ 384xfs_dir2_data_init( 385 xfs_da_args_t *args, /* directory operation args */ 386 xfs_dir2_db_t blkno, /* logical dir block number */ 387 xfs_dabuf_t **bpp) /* output block buffer */ 388{ 389 xfs_dabuf_t *bp; /* block buffer */ 390 xfs_dir2_data_t *d; /* pointer to block */ 391 xfs_inode_t *dp; /* incore directory inode */ 392 xfs_dir2_data_unused_t *dup; /* unused entry pointer */ 393 int error; /* error return value */ 394 int i; /* bestfree index */ 395 xfs_mount_t *mp; /* filesystem mount point */ 396 xfs_trans_t *tp; /* transaction pointer */ 397 int t; /* temp */ 398 399 dp = args->dp; 400 mp = dp->i_mount; 401 tp = args->trans; 402 /* 403 * Get the buffer set up for the block. 404 */ 405 error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, blkno), -1, &bp, 406 XFS_DATA_FORK); 407 if (error) { 408 return error; 409 } 410 ASSERT(bp != NULL); 411 /* 412 * Initialize the header. 413 */ 414 d = bp->data; 415 d->hdr.magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC); 416 d->hdr.bestfree[0].offset = cpu_to_be16(sizeof(d->hdr)); 417 for (i = 1; i < XFS_DIR2_DATA_FD_COUNT; i++) { 418 d->hdr.bestfree[i].length = 0; 419 d->hdr.bestfree[i].offset = 0; 420 } 421 /* 422 * Set up an unused entry for the block's body. 423 */ 424 dup = &d->u[0].unused; 425 dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG); 426 427 t=mp->m_dirblksize - (uint)sizeof(d->hdr); 428 d->hdr.bestfree[0].length = cpu_to_be16(t); 429 dup->length = cpu_to_be16(t); 430 *XFS_DIR2_DATA_UNUSED_TAG_P(dup) = cpu_to_be16((char *)dup - (char *)d); 431 /* 432 * Log it and return it. 433 */ 434 xfs_dir2_data_log_header(tp, bp); 435 xfs_dir2_data_log_unused(tp, bp, dup); 436 *bpp = bp; 437 return 0; 438} 439 440/* 441 * Log an active data entry from the block. 442 */ 443void 444xfs_dir2_data_log_entry( 445 xfs_trans_t *tp, /* transaction pointer */ 446 xfs_dabuf_t *bp, /* block buffer */ 447 xfs_dir2_data_entry_t *dep) /* data entry pointer */ 448{ 449 xfs_dir2_data_t *d; /* data block pointer */ 450 451 d = bp->data; 452 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 453 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 454 xfs_da_log_buf(tp, bp, (uint)((char *)dep - (char *)d), 455 (uint)((char *)(XFS_DIR2_DATA_ENTRY_TAG_P(dep) + 1) - 456 (char *)d - 1)); 457} 458 459/* 460 * Log a data block header. 461 */ 462void 463xfs_dir2_data_log_header( 464 xfs_trans_t *tp, /* transaction pointer */ 465 xfs_dabuf_t *bp) /* block buffer */ 466{ 467 xfs_dir2_data_t *d; /* data block pointer */ 468 469 d = bp->data; 470 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 471 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 472 xfs_da_log_buf(tp, bp, (uint)((char *)&d->hdr - (char *)d), 473 (uint)(sizeof(d->hdr) - 1)); 474} 475 476/* 477 * Log a data unused entry. 478 */ 479void 480xfs_dir2_data_log_unused( 481 xfs_trans_t *tp, /* transaction pointer */ 482 xfs_dabuf_t *bp, /* block buffer */ 483 xfs_dir2_data_unused_t *dup) /* data unused pointer */ 484{ 485 xfs_dir2_data_t *d; /* data block pointer */ 486 487 d = bp->data; 488 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 489 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 490 /* 491 * Log the first part of the unused entry. 492 */ 493 xfs_da_log_buf(tp, bp, (uint)((char *)dup - (char *)d), 494 (uint)((char *)&dup->length + sizeof(dup->length) - 495 1 - (char *)d)); 496 /* 497 * Log the end (tag) of the unused entry. 498 */ 499 xfs_da_log_buf(tp, bp, 500 (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d), 501 (uint)((char *)XFS_DIR2_DATA_UNUSED_TAG_P(dup) - (char *)d + 502 sizeof(xfs_dir2_data_off_t) - 1)); 503} 504 505/* 506 * Make a byte range in the data block unused. 507 * Its current contents are unimportant. 508 */ 509void 510xfs_dir2_data_make_free( 511 xfs_trans_t *tp, /* transaction pointer */ 512 xfs_dabuf_t *bp, /* block buffer */ 513 xfs_dir2_data_aoff_t offset, /* starting byte offset */ 514 xfs_dir2_data_aoff_t len, /* length in bytes */ 515 int *needlogp, /* out: log header */ 516 int *needscanp) /* out: regen bestfree */ 517{ 518 xfs_dir2_data_t *d; /* data block pointer */ 519 xfs_dir2_data_free_t *dfp; /* bestfree pointer */ 520 char *endptr; /* end of data area */ 521 xfs_mount_t *mp; /* filesystem mount point */ 522 int needscan; /* need to regen bestfree */ 523 xfs_dir2_data_unused_t *newdup; /* new unused entry */ 524 xfs_dir2_data_unused_t *postdup; /* unused entry after us */ 525 xfs_dir2_data_unused_t *prevdup; /* unused entry before us */ 526 527 mp = tp->t_mountp; 528 d = bp->data; 529 /* 530 * Figure out where the end of the data area is. 531 */ 532 if (be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC) 533 endptr = (char *)d + mp->m_dirblksize; 534 else { 535 xfs_dir2_block_tail_t *btp; /* block tail */ 536 537 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 538 btp = XFS_DIR2_BLOCK_TAIL_P(mp, (xfs_dir2_block_t *)d); 539 endptr = (char *)XFS_DIR2_BLOCK_LEAF_P(btp); 540 } 541 /* 542 * If this isn't the start of the block, then back up to 543 * the previous entry and see if it's free. 544 */ 545 if (offset > sizeof(d->hdr)) { 546 __be16 *tagp; /* tag just before us */ 547 548 tagp = (__be16 *)((char *)d + offset) - 1; 549 prevdup = (xfs_dir2_data_unused_t *)((char *)d + be16_to_cpu(*tagp)); 550 if (be16_to_cpu(prevdup->freetag) != XFS_DIR2_DATA_FREE_TAG) 551 prevdup = NULL; 552 } else 553 prevdup = NULL; 554 /* 555 * If this isn't the end of the block, see if the entry after 556 * us is free. 557 */ 558 if ((char *)d + offset + len < endptr) { 559 postdup = 560 (xfs_dir2_data_unused_t *)((char *)d + offset + len); 561 if (be16_to_cpu(postdup->freetag) != XFS_DIR2_DATA_FREE_TAG) 562 postdup = NULL; 563 } else 564 postdup = NULL; 565 ASSERT(*needscanp == 0); 566 needscan = 0; 567 /* 568 * Previous and following entries are both free, 569 * merge everything into a single free entry. 570 */ 571 if (prevdup && postdup) { 572 xfs_dir2_data_free_t *dfp2; /* another bestfree pointer */ 573 574 /* 575 * See if prevdup and/or postdup are in bestfree table. 576 */ 577 dfp = xfs_dir2_data_freefind(d, prevdup); 578 dfp2 = xfs_dir2_data_freefind(d, postdup); 579 /* 580 * We need a rescan unless there are exactly 2 free entries 581 * namely our two. Then we know what's happening, otherwise 582 * since the third bestfree is there, there might be more 583 * entries. 584 */ 585 needscan = (d->hdr.bestfree[2].length != 0); 586 /* 587 * Fix up the new big freespace. 588 */ 589 be16_add(&prevdup->length, len + be16_to_cpu(postdup->length)); 590 *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) = 591 cpu_to_be16((char *)prevdup - (char *)d); 592 xfs_dir2_data_log_unused(tp, bp, prevdup); 593 if (!needscan) { 594 /* 595 * Has to be the case that entries 0 and 1 are 596 * dfp and dfp2 (don't know which is which), and 597 * entry 2 is empty. 598 * Remove entry 1 first then entry 0. 599 */ 600 ASSERT(dfp && dfp2); 601 if (dfp == &d->hdr.bestfree[1]) { 602 dfp = &d->hdr.bestfree[0]; 603 ASSERT(dfp2 == dfp); 604 dfp2 = &d->hdr.bestfree[1]; 605 } 606 xfs_dir2_data_freeremove(d, dfp2, needlogp); 607 xfs_dir2_data_freeremove(d, dfp, needlogp); 608 /* 609 * Now insert the new entry. 610 */ 611 dfp = xfs_dir2_data_freeinsert(d, prevdup, needlogp); 612 ASSERT(dfp == &d->hdr.bestfree[0]); 613 ASSERT(dfp->length == prevdup->length); 614 ASSERT(!dfp[1].length); 615 ASSERT(!dfp[2].length); 616 } 617 } 618 /* 619 * The entry before us is free, merge with it. 620 */ 621 else if (prevdup) { 622 dfp = xfs_dir2_data_freefind(d, prevdup); 623 be16_add(&prevdup->length, len); 624 *XFS_DIR2_DATA_UNUSED_TAG_P(prevdup) = 625 cpu_to_be16((char *)prevdup - (char *)d); 626 xfs_dir2_data_log_unused(tp, bp, prevdup); 627 /* 628 * If the previous entry was in the table, the new entry 629 * is longer, so it will be in the table too. Remove 630 * the old one and add the new one. 631 */ 632 if (dfp) { 633 xfs_dir2_data_freeremove(d, dfp, needlogp); 634 (void)xfs_dir2_data_freeinsert(d, prevdup, needlogp); 635 } 636 /* 637 * Otherwise we need a scan if the new entry is big enough. 638 */ 639 else { 640 needscan = be16_to_cpu(prevdup->length) > 641 be16_to_cpu(d->hdr.bestfree[2].length); 642 } 643 } 644 /* 645 * The following entry is free, merge with it. 646 */ 647 else if (postdup) { 648 dfp = xfs_dir2_data_freefind(d, postdup); 649 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset); 650 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG); 651 newdup->length = cpu_to_be16(len + be16_to_cpu(postdup->length)); 652 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) = 653 cpu_to_be16((char *)newdup - (char *)d); 654 xfs_dir2_data_log_unused(tp, bp, newdup); 655 /* 656 * If the following entry was in the table, the new entry 657 * is longer, so it will be in the table too. Remove 658 * the old one and add the new one. 659 */ 660 if (dfp) { 661 xfs_dir2_data_freeremove(d, dfp, needlogp); 662 (void)xfs_dir2_data_freeinsert(d, newdup, needlogp); 663 } 664 /* 665 * Otherwise we need a scan if the new entry is big enough. 666 */ 667 else { 668 needscan = be16_to_cpu(newdup->length) > 669 be16_to_cpu(d->hdr.bestfree[2].length); 670 } 671 } 672 /* 673 * Neither neighbor is free. Make a new entry. 674 */ 675 else { 676 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset); 677 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG); 678 newdup->length = cpu_to_be16(len); 679 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) = 680 cpu_to_be16((char *)newdup - (char *)d); 681 xfs_dir2_data_log_unused(tp, bp, newdup); 682 (void)xfs_dir2_data_freeinsert(d, newdup, needlogp); 683 } 684 *needscanp = needscan; 685} 686 687/* 688 * Take a byte range out of an existing unused space and make it un-free. 689 */ 690void 691xfs_dir2_data_use_free( 692 xfs_trans_t *tp, /* transaction pointer */ 693 xfs_dabuf_t *bp, /* data block buffer */ 694 xfs_dir2_data_unused_t *dup, /* unused entry */ 695 xfs_dir2_data_aoff_t offset, /* starting offset to use */ 696 xfs_dir2_data_aoff_t len, /* length to use */ 697 int *needlogp, /* out: need to log header */ 698 int *needscanp) /* out: need regen bestfree */ 699{ 700 xfs_dir2_data_t *d; /* data block */ 701 xfs_dir2_data_free_t *dfp; /* bestfree pointer */ 702 int matchback; /* matches end of freespace */ 703 int matchfront; /* matches start of freespace */ 704 int needscan; /* need to regen bestfree */ 705 xfs_dir2_data_unused_t *newdup; /* new unused entry */ 706 xfs_dir2_data_unused_t *newdup2; /* another new unused entry */ 707 int oldlen; /* old unused entry's length */ 708 709 d = bp->data; 710 ASSERT(be32_to_cpu(d->hdr.magic) == XFS_DIR2_DATA_MAGIC || 711 be32_to_cpu(d->hdr.magic) == XFS_DIR2_BLOCK_MAGIC); 712 ASSERT(be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG); 713 ASSERT(offset >= (char *)dup - (char *)d); 714 ASSERT(offset + len <= (char *)dup + be16_to_cpu(dup->length) - (char *)d); 715 ASSERT((char *)dup - (char *)d == be16_to_cpu(*XFS_DIR2_DATA_UNUSED_TAG_P(dup))); 716 /* 717 * Look up the entry in the bestfree table. 718 */ 719 dfp = xfs_dir2_data_freefind(d, dup); 720 oldlen = be16_to_cpu(dup->length); 721 ASSERT(dfp || oldlen <= be16_to_cpu(d->hdr.bestfree[2].length)); 722 /* 723 * Check for alignment with front and back of the entry. 724 */ 725 matchfront = (char *)dup - (char *)d == offset; 726 matchback = (char *)dup + oldlen - (char *)d == offset + len; 727 ASSERT(*needscanp == 0); 728 needscan = 0; 729 /* 730 * If we matched it exactly we just need to get rid of it from 731 * the bestfree table. 732 */ 733 if (matchfront && matchback) { 734 if (dfp) { 735 needscan = (d->hdr.bestfree[2].offset != 0); 736 if (!needscan) 737 xfs_dir2_data_freeremove(d, dfp, needlogp); 738 } 739 } 740 /* 741 * We match the first part of the entry. 742 * Make a new entry with the remaining freespace. 743 */ 744 else if (matchfront) { 745 newdup = (xfs_dir2_data_unused_t *)((char *)d + offset + len); 746 newdup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG); 747 newdup->length = cpu_to_be16(oldlen - len); 748 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) = 749 cpu_to_be16((char *)newdup - (char *)d); 750 xfs_dir2_data_log_unused(tp, bp, newdup); 751 /* 752 * If it was in the table, remove it and add the new one. 753 */ 754 if (dfp) { 755 xfs_dir2_data_freeremove(d, dfp, needlogp); 756 dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp); 757 ASSERT(dfp != NULL); 758 ASSERT(dfp->length == newdup->length); 759 ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d); 760 /* 761 * If we got inserted at the last slot, 762 * that means we don't know if there was a better 763 * choice for the last slot, or not. Rescan. 764 */ 765 needscan = dfp == &d->hdr.bestfree[2]; 766 } 767 } 768 /* 769 * We match the last part of the entry. 770 * Trim the allocated space off the tail of the entry. 771 */ 772 else if (matchback) { 773 newdup = dup; 774 newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup); 775 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) = 776 cpu_to_be16((char *)newdup - (char *)d); 777 xfs_dir2_data_log_unused(tp, bp, newdup); 778 /* 779 * If it was in the table, remove it and add the new one. 780 */ 781 if (dfp) { 782 xfs_dir2_data_freeremove(d, dfp, needlogp); 783 dfp = xfs_dir2_data_freeinsert(d, newdup, needlogp); 784 ASSERT(dfp != NULL); 785 ASSERT(dfp->length == newdup->length); 786 ASSERT(be16_to_cpu(dfp->offset) == (char *)newdup - (char *)d); 787 /* 788 * If we got inserted at the last slot, 789 * that means we don't know if there was a better 790 * choice for the last slot, or not. Rescan. 791 */ 792 needscan = dfp == &d->hdr.bestfree[2]; 793 } 794 } 795 /* 796 * Poking out the middle of an entry. 797 * Make two new entries. 798 */ 799 else { 800 newdup = dup; 801 newdup->length = cpu_to_be16(((char *)d + offset) - (char *)newdup); 802 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup) = 803 cpu_to_be16((char *)newdup - (char *)d); 804 xfs_dir2_data_log_unused(tp, bp, newdup); 805 newdup2 = (xfs_dir2_data_unused_t *)((char *)d + offset + len); 806 newdup2->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG); 807 newdup2->length = cpu_to_be16(oldlen - len - be16_to_cpu(newdup->length)); 808 *XFS_DIR2_DATA_UNUSED_TAG_P(newdup2) = 809 cpu_to_be16((char *)newdup2 - (char *)d); 810 xfs_dir2_data_log_unused(tp, bp, newdup2); 811 /* 812 * If the old entry was in the table, we need to scan 813 * if the 3rd entry was valid, since these entries 814 * are smaller than the old one. 815 * If we don't need to scan that means there were 1 or 2 816 * entries in the table, and removing the old and adding 817 * the 2 new will work. 818 */ 819 if (dfp) { 820 needscan = (d->hdr.bestfree[2].length != 0); 821 if (!needscan) { 822 xfs_dir2_data_freeremove(d, dfp, needlogp); 823 (void)xfs_dir2_data_freeinsert(d, newdup, 824 needlogp); 825 (void)xfs_dir2_data_freeinsert(d, newdup2, 826 needlogp); 827 } 828 } 829 } 830 *needscanp = needscan; 831} 832