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