1 /* 2 * Copyright (c) 2012-2013 Paulo Alcantara <pcacjr (at) zytor.com> 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License as 6 * published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it would be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program; if not, write the Free Software Foundation, 15 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 16 */ 17 18 #include <cache.h> 19 #include <core.h> 20 #include <fs.h> 21 22 #include "xfs_types.h" 23 #include "xfs_sb.h" 24 #include "xfs_ag.h" 25 #include "misc.h" 26 #include "xfs.h" 27 #include "xfs_dinode.h" 28 29 #include "xfs_dir2.h" 30 31 #define XFS_DIR2_DIRBLKS_CACHE_SIZE 128 32 33 struct xfs_dir2_dirblks_cache { 34 block_t dc_startblock; 35 xfs_filblks_t dc_blkscount; 36 void *dc_area; 37 }; 38 39 static struct xfs_dir2_dirblks_cache dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE]; 40 static unsigned char dirblks_cached_count = 0; 41 42 uint32_t xfs_dir2_da_hashname(const uint8_t *name, int namelen) 43 { 44 uint32_t hash; 45 46 /* 47 * Do four characters at a time as long as we can. 48 */ 49 for (hash = 0; namelen >= 4; namelen -=4, name += 4) 50 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^ 51 (name[3] << 0) ^ rol32(hash, 7 * 4); 52 53 /* 54 * Now do the rest of the characters. 55 */ 56 switch (namelen) { 57 case 3: 58 return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^ 59 rol32(hash, 7 * 3); 60 case 2: 61 return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2); 62 case 1: 63 return (name[0] << 0) ^ rol32(hash, 7 * 1); 64 default: /* case 0: */ 65 return hash; 66 } 67 } 68 69 static void *get_dirblks(struct fs_info *fs, block_t startblock, 70 xfs_filblks_t c) 71 { 72 int count = c << XFS_INFO(fs)->dirblklog; 73 uint8_t *p; 74 uint8_t *buf; 75 off_t offset = 0; 76 77 buf = malloc(c * XFS_INFO(fs)->dirblksize); 78 if (!buf) 79 malloc_error("buffer memory"); 80 81 memset(buf, 0, XFS_INFO(fs)->dirblksize); 82 83 while (count--) { 84 p = (uint8_t *)get_cache(fs->fs_dev, startblock++); 85 memcpy(buf + offset, p, BLOCK_SIZE(fs)); 86 offset += BLOCK_SIZE(fs); 87 } 88 89 return buf; 90 } 91 92 const void *xfs_dir2_dirblks_get_cached(struct fs_info *fs, block_t startblock, 93 xfs_filblks_t c) 94 { 95 unsigned char i; 96 void *buf; 97 98 xfs_debug("fs %p startblock %llu (0x%llx) blkscount %lu", fs, startblock, 99 startblock, c); 100 101 if (!dirblks_cached_count) { 102 buf = get_dirblks(fs, startblock, c); 103 104 dirblks_cache[dirblks_cached_count].dc_startblock = startblock; 105 dirblks_cache[dirblks_cached_count].dc_blkscount = c; 106 dirblks_cache[dirblks_cached_count].dc_area = buf; 107 108 return dirblks_cache[dirblks_cached_count++].dc_area; 109 } else if (dirblks_cached_count == XFS_DIR2_DIRBLKS_CACHE_SIZE) { 110 for (i = 0; i < XFS_DIR2_DIRBLKS_CACHE_SIZE / 2; i++) { 111 unsigned char k = XFS_DIR2_DIRBLKS_CACHE_SIZE - (i + 1); 112 113 free(dirblks_cache[i].dc_area); 114 dirblks_cache[i] = dirblks_cache[k]; 115 memset(&dirblks_cache[k], 0, sizeof(dirblks_cache[k])); 116 } 117 118 buf = get_dirblks(fs, startblock, c); 119 120 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_startblock = 121 startblock; 122 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_blkscount = c; 123 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_area = buf; 124 125 dirblks_cached_count = XFS_DIR2_DIRBLKS_CACHE_SIZE / 2; 126 127 return dirblks_cache[dirblks_cached_count++].dc_area; 128 } else { 129 block_t block; 130 xfs_filblks_t count; 131 132 block = dirblks_cache[dirblks_cached_count - 1].dc_startblock; 133 count = dirblks_cache[dirblks_cached_count - 1].dc_blkscount; 134 135 if (block == startblock && count == c) { 136 return dirblks_cache[dirblks_cached_count - 1].dc_area; 137 } else { 138 for (i = 0; i < dirblks_cached_count; i++) { 139 block = dirblks_cache[i].dc_startblock; 140 count = dirblks_cache[i].dc_blkscount; 141 142 if (block == startblock && count == c) 143 return dirblks_cache[i].dc_area; 144 } 145 146 buf = get_dirblks(fs, startblock, c); 147 148 dirblks_cache[dirblks_cached_count].dc_startblock = startblock; 149 dirblks_cache[dirblks_cached_count].dc_blkscount = c; 150 dirblks_cache[dirblks_cached_count].dc_area = buf; 151 152 return dirblks_cache[dirblks_cached_count++].dc_area; 153 } 154 } 155 156 return NULL; 157 } 158 159 void xfs_dir2_dirblks_flush_cache(void) 160 { 161 unsigned char i; 162 163 for (i = 0; i < dirblks_cached_count; i++) { 164 free(dirblks_cache[i].dc_area); 165 memset(&dirblks_cache[i], 0, sizeof(dirblks_cache[i])); 166 } 167 168 dirblks_cached_count = 0; 169 } 170 171 struct inode *xfs_dir2_local_find_entry(const char *dname, struct inode *parent, 172 xfs_dinode_t *core) 173 { 174 xfs_dir2_sf_t *sf = (xfs_dir2_sf_t *)&core->di_literal_area[0]; 175 xfs_dir2_sf_entry_t *sf_entry; 176 uint8_t count = sf->hdr.i8count ? sf->hdr.i8count : sf->hdr.count; 177 struct fs_info *fs = parent->fs; 178 struct inode *inode; 179 xfs_intino_t ino; 180 xfs_dinode_t *ncore = NULL; 181 182 xfs_debug("dname %s parent %p core %p", dname, parent, core); 183 xfs_debug("count %hhu i8count %hhu", sf->hdr.count, sf->hdr.i8count); 184 185 sf_entry = (xfs_dir2_sf_entry_t *)((uint8_t *)&sf->list[0] - 186 (!sf->hdr.i8count ? 4 : 0)); 187 while (count--) { 188 uint8_t *start_name = &sf_entry->name[0]; 189 uint8_t *end_name = start_name + sf_entry->namelen; 190 191 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) { 192 xfs_debug("Found entry %s", dname); 193 goto found; 194 } 195 196 sf_entry = (xfs_dir2_sf_entry_t *)((uint8_t *)sf_entry + 197 offsetof(struct xfs_dir2_sf_entry, 198 name[0]) + 199 sf_entry->namelen + 200 (sf->hdr.i8count ? 8 : 4)); 201 } 202 203 return NULL; 204 205 found: 206 inode = xfs_new_inode(fs); 207 208 ino = xfs_dir2_sf_get_inumber(sf, (xfs_dir2_inou_t *)( 209 (uint8_t *)sf_entry + 210 offsetof(struct xfs_dir2_sf_entry, 211 name[0]) + 212 sf_entry->namelen)); 213 214 xfs_debug("entry inode's number %lu", ino); 215 216 ncore = xfs_dinode_get_core(fs, ino); 217 if (!ncore) { 218 xfs_error("Failed to get dinode!"); 219 goto out; 220 } 221 222 fill_xfs_inode_pvt(fs, inode, ino); 223 224 inode->ino = ino; 225 inode->size = be64_to_cpu(ncore->di_size); 226 227 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) { 228 inode->mode = DT_DIR; 229 xfs_debug("Found a directory inode!"); 230 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) { 231 inode->mode = DT_REG; 232 xfs_debug("Found a file inode!"); 233 xfs_debug("inode size %llu", inode->size); 234 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) { 235 inode->mode = DT_LNK; 236 xfs_debug("Found a symbolic link inode!"); 237 } 238 239 return inode; 240 241 out: 242 free(inode); 243 244 return NULL; 245 } 246 247 struct inode *xfs_dir2_block_find_entry(const char *dname, struct inode *parent, 248 xfs_dinode_t *core) 249 { 250 xfs_bmbt_irec_t r; 251 block_t dir_blk; 252 struct fs_info *fs = parent->fs; 253 const uint8_t *dirblk_buf; 254 uint8_t *p, *endp; 255 xfs_dir2_data_hdr_t *hdr; 256 struct inode *inode = NULL; 257 xfs_dir2_block_tail_t *btp; 258 xfs_dir2_data_unused_t *dup; 259 xfs_dir2_data_entry_t *dep; 260 xfs_intino_t ino; 261 xfs_dinode_t *ncore; 262 263 xfs_debug("dname %s parent %p core %p", dname, parent, core); 264 265 bmbt_irec_get(&r, (xfs_bmbt_rec_t *)&core->di_literal_area[0]); 266 dir_blk = fsblock_to_bytes(fs, r.br_startblock) >> BLOCK_SHIFT(fs); 267 268 dirblk_buf = xfs_dir2_dirblks_get_cached(fs, dir_blk, r.br_blockcount); 269 hdr = (xfs_dir2_data_hdr_t *)dirblk_buf; 270 if (be32_to_cpu(hdr->magic) != XFS_DIR2_BLOCK_MAGIC) { 271 xfs_error("Block directory header's magic number does not match!"); 272 xfs_debug("hdr->magic: 0x%lx", be32_to_cpu(hdr->magic)); 273 goto out; 274 } 275 276 p = (uint8_t *)(hdr + 1); 277 278 btp = xfs_dir2_block_tail_p(XFS_INFO(fs), hdr); 279 endp = (uint8_t *)((xfs_dir2_leaf_entry_t *)btp - be32_to_cpu(btp->count)); 280 281 while (p < endp) { 282 uint8_t *start_name; 283 uint8_t *end_name; 284 285 dup = (xfs_dir2_data_unused_t *)p; 286 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) { 287 p += be16_to_cpu(dup->length); 288 continue; 289 } 290 291 dep = (xfs_dir2_data_entry_t *)p; 292 293 start_name = &dep->name[0]; 294 end_name = start_name + dep->namelen; 295 296 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) { 297 xfs_debug("Found entry %s", dname); 298 goto found; 299 } 300 301 p += xfs_dir2_data_entsize(dep->namelen); 302 } 303 304 out: 305 return NULL; 306 307 found: 308 inode = xfs_new_inode(fs); 309 310 ino = be64_to_cpu(dep->inumber); 311 312 xfs_debug("entry inode's number %lu", ino); 313 314 ncore = xfs_dinode_get_core(fs, ino); 315 if (!ncore) { 316 xfs_error("Failed to get dinode!"); 317 goto failed; 318 } 319 320 fill_xfs_inode_pvt(fs, inode, ino); 321 322 inode->ino = ino; 323 XFS_PVT(inode)->i_ino_blk = ino_to_bytes(fs, ino) >> BLOCK_SHIFT(fs); 324 inode->size = be64_to_cpu(ncore->di_size); 325 326 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) { 327 inode->mode = DT_DIR; 328 xfs_debug("Found a directory inode!"); 329 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) { 330 inode->mode = DT_REG; 331 xfs_debug("Found a file inode!"); 332 xfs_debug("inode size %llu", inode->size); 333 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) { 334 inode->mode = DT_LNK; 335 xfs_debug("Found a symbolic link inode!"); 336 } 337 338 xfs_debug("entry inode's number %lu", ino); 339 340 return inode; 341 342 failed: 343 free(inode); 344 345 return NULL; 346 } 347 348 struct inode *xfs_dir2_leaf_find_entry(const char *dname, struct inode *parent, 349 xfs_dinode_t *core) 350 { 351 xfs_dir2_leaf_t *leaf; 352 xfs_bmbt_irec_t irec; 353 block_t leaf_blk, dir_blk; 354 xfs_dir2_leaf_entry_t *lep; 355 int low; 356 int high; 357 int mid = 0; 358 uint32_t hash = 0; 359 uint32_t hashwant; 360 uint32_t newdb, curdb = -1; 361 xfs_dir2_data_entry_t *dep; 362 struct inode *ip; 363 xfs_dir2_data_hdr_t *data_hdr; 364 uint8_t *start_name; 365 uint8_t *end_name; 366 xfs_intino_t ino; 367 xfs_dinode_t *ncore; 368 const uint8_t *buf = NULL; 369 370 xfs_debug("dname %s parent %p core %p", dname, parent, core); 371 372 bmbt_irec_get(&irec, ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + 373 be32_to_cpu(core->di_nextents) - 1); 374 leaf_blk = fsblock_to_bytes(parent->fs, irec.br_startblock) >> 375 BLOCK_SHIFT(parent->fs); 376 377 leaf = (xfs_dir2_leaf_t *)xfs_dir2_dirblks_get_cached(parent->fs, leaf_blk, 378 irec.br_blockcount); 379 if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR2_LEAF1_MAGIC) { 380 xfs_error("Single leaf block header's magic number does not match!"); 381 goto out; 382 } 383 384 if (!leaf->hdr.count) 385 goto out; 386 387 hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname)); 388 389 /* Binary search */ 390 for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1; 391 low <= high; ) { 392 mid = (low + high) >> 1; 393 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant) 394 break; 395 if (hash < hashwant) 396 low = mid + 1; 397 else 398 high = mid - 1; 399 } 400 401 /* If hash is not the one we want, then the directory does not contain the 402 * entry we're looking for and there is nothing to do anymore. 403 */ 404 if (hash != hashwant) 405 goto out; 406 407 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) 408 mid--; 409 410 for (lep = &leaf->ents[mid]; 411 mid < be16_to_cpu(leaf->hdr.count) && 412 be32_to_cpu(lep->hashval) == hashwant; 413 lep++, mid++) { 414 /* Skip over stale leaf entries. */ 415 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 416 continue; 417 418 newdb = xfs_dir2_dataptr_to_db(parent->fs, be32_to_cpu(lep->address)); 419 if (newdb != curdb) { 420 bmbt_irec_get(&irec, 421 ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + newdb); 422 dir_blk = fsblock_to_bytes(parent->fs, irec.br_startblock) >> 423 424 BLOCK_SHIFT(parent->fs); 425 buf = xfs_dir2_dirblks_get_cached(parent->fs, dir_blk, irec.br_blockcount); 426 data_hdr = (xfs_dir2_data_hdr_t *)buf; 427 if (be32_to_cpu(data_hdr->magic) != XFS_DIR2_DATA_MAGIC) { 428 xfs_error("Leaf directory's data magic No. does not match!"); 429 goto out; 430 } 431 432 curdb = newdb; 433 } 434 435 dep = (xfs_dir2_data_entry_t *)((char *)buf + 436 xfs_dir2_dataptr_to_off(parent->fs, be32_to_cpu(lep->address))); 437 438 start_name = &dep->name[0]; 439 end_name = start_name + dep->namelen; 440 441 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) { 442 xfs_debug("Found entry %s", dname); 443 goto found; 444 } 445 } 446 447 out: 448 return NULL; 449 450 found: 451 ip = xfs_new_inode(parent->fs); 452 453 ino = be64_to_cpu(dep->inumber); 454 455 xfs_debug("entry inode's number %lu", ino); 456 457 ncore = xfs_dinode_get_core(parent->fs, ino); 458 if (!ncore) { 459 xfs_error("Failed to get dinode!"); 460 goto failed; 461 } 462 463 fill_xfs_inode_pvt(parent->fs, ip, ino); 464 465 ip->ino = ino; 466 XFS_PVT(ip)->i_ino_blk = ino_to_bytes(parent->fs, ino) >> 467 BLOCK_SHIFT(parent->fs); 468 ip->size = be64_to_cpu(ncore->di_size); 469 470 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) { 471 ip->mode = DT_DIR; 472 xfs_debug("Found a directory inode!"); 473 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) { 474 ip->mode = DT_REG; 475 xfs_debug("Found a file inode!"); 476 xfs_debug("inode size %llu", ip->size); 477 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) { 478 ip->mode = DT_LNK; 479 xfs_debug("Found a symbolic link inode!"); 480 } 481 482 xfs_debug("entry inode's number %lu", ino); 483 484 return ip; 485 486 failed: 487 free(ip); 488 489 return ip; 490 } 491 492 static xfs_fsblock_t 493 select_child(xfs_dfiloff_t off, 494 xfs_bmbt_key_t *kp, 495 xfs_bmbt_ptr_t *pp, 496 int nrecs) 497 { 498 int i; 499 500 for (i = 0; i < nrecs; i++) { 501 if (be64_to_cpu(kp[i].br_startoff) == off) 502 return be64_to_cpu(pp[i]); 503 if (be64_to_cpu(kp[i].br_startoff) > off) { 504 if (i == 0) 505 return be64_to_cpu(pp[i]); 506 else 507 return be64_to_cpu(pp[i-1]); 508 } 509 } 510 511 return be64_to_cpu(pp[nrecs - 1]); 512 } 513 514 block_t xfs_dir2_get_right_blk(struct fs_info *fs, xfs_dinode_t *core, 515 block_t fsblkno, int *error) 516 { 517 uint32_t idx; 518 xfs_bmbt_irec_t irec; 519 block_t bno; 520 block_t nextbno; 521 xfs_bmdr_block_t *rblock; 522 int fsize; 523 int nextents; 524 xfs_bmbt_ptr_t *pp; 525 xfs_bmbt_key_t *kp; 526 xfs_btree_block_t *blk; 527 xfs_bmbt_rec_t *xp; 528 529 *error = 0; 530 if (core->di_format == XFS_DINODE_FMT_EXTENTS) { 531 xfs_debug("XFS_DINODE_FMT_EXTENTS"); 532 for (idx = 0; idx < be32_to_cpu(core->di_nextents); idx++) { 533 bmbt_irec_get(&irec, 534 ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + idx); 535 if (fsblkno >= irec.br_startoff && 536 fsblkno < irec.br_startoff + irec.br_blockcount) 537 break; 538 } 539 } else if (core->di_format == XFS_DINODE_FMT_BTREE) { 540 xfs_debug("XFS_DINODE_FMT_BTREE"); 541 bno = NULLFSBLOCK; 542 rblock = (xfs_bmdr_block_t *)&core->di_literal_area[0]; 543 fsize = XFS_DFORK_SIZE(core, fs, XFS_DATA_FORK); 544 pp = XFS_BMDR_PTR_ADDR(rblock, 1, xfs_bmdr_maxrecs(fsize, 0)); 545 kp = XFS_BMDR_KEY_ADDR(rblock, 1); 546 bno = fsblock_to_bytes(fs, 547 select_child(fsblkno, kp, pp, 548 be16_to_cpu(rblock->bb_numrecs))) >> BLOCK_SHIFT(fs); 549 550 /* Find the leaf */ 551 for (;;) { 552 blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno); 553 if (be16_to_cpu(blk->bb_level) == 0) 554 break; 555 pp = XFS_BMBT_PTR_ADDR(fs, blk, 1, 556 xfs_bmdr_maxrecs(XFS_INFO(fs)->blocksize, 0)); 557 kp = XFS_BMBT_KEY_ADDR(fs, blk, 1); 558 bno = fsblock_to_bytes(fs, 559 select_child(fsblkno, kp, pp, 560 be16_to_cpu(blk->bb_numrecs))) >> BLOCK_SHIFT(fs); 561 } 562 563 /* Find the records among leaves */ 564 for (;;) { 565 nextbno = be64_to_cpu(blk->bb_u.l.bb_rightsib); 566 nextents = be16_to_cpu(blk->bb_numrecs); 567 xp = (xfs_bmbt_rec_t *)XFS_BMBT_REC_ADDR(fs, blk, 1); 568 for (idx = 0; idx < nextents; idx++) { 569 bmbt_irec_get(&irec, xp + idx); 570 if (fsblkno >= irec.br_startoff && 571 fsblkno < irec.br_startoff + irec.br_blockcount) { 572 nextbno = NULLFSBLOCK; 573 break; 574 } 575 } 576 if (nextbno == NULLFSBLOCK) 577 break; 578 bno = fsblock_to_bytes(fs, nextbno) >> BLOCK_SHIFT(fs); 579 blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno); 580 } 581 } 582 583 if (fsblkno < irec.br_startoff || 584 fsblkno >= irec.br_startoff + irec.br_blockcount) 585 *error = 1; 586 587 return fsblock_to_bytes(fs, 588 fsblkno - irec.br_startoff + irec.br_startblock) >> 589 BLOCK_SHIFT(fs); 590 } 591 592 struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent, 593 xfs_dinode_t *core) 594 { 595 block_t fsblkno; 596 xfs_da_intnode_t *node = NULL; 597 uint32_t hashwant; 598 uint32_t hash = 0; 599 xfs_da_node_entry_t *btree; 600 uint16_t max; 601 uint16_t span; 602 uint16_t probe; 603 int error; 604 xfs_dir2_data_hdr_t *data_hdr; 605 xfs_dir2_leaf_t *leaf; 606 xfs_dir2_leaf_entry_t *lep; 607 xfs_dir2_data_entry_t *dep; 608 struct inode *ip; 609 uint8_t *start_name; 610 uint8_t *end_name; 611 int low; 612 int high; 613 int mid = 0; 614 uint32_t newdb, curdb = -1; 615 xfs_intino_t ino; 616 xfs_dinode_t *ncore; 617 const uint8_t *buf = NULL; 618 619 xfs_debug("dname %s parent %p core %p", dname, parent, core); 620 621 hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname)); 622 623 fsblkno = xfs_dir2_get_right_blk(parent->fs, core, 624 xfs_dir2_byte_to_db(parent->fs, XFS_DIR2_LEAF_OFFSET), 625 &error); 626 if (error) { 627 xfs_error("Cannot find right rec!"); 628 return NULL; 629 } 630 631 node = (xfs_da_intnode_t *)xfs_dir2_dirblks_get_cached(parent->fs, fsblkno, 632 1); 633 if (be16_to_cpu(node->hdr.info.magic) != XFS_DA_NODE_MAGIC) { 634 xfs_error("Node's magic number does not match!"); 635 goto out; 636 } 637 638 do { 639 if (!node->hdr.count) 640 goto out; 641 642 /* Given a hash to lookup, you read the node's btree array and first 643 * "hashval" in the array that exceeds the given hash and it can then 644 * be found in the block pointed by the "before" value. 645 */ 646 max = be16_to_cpu(node->hdr.count); 647 648 probe = span = max/2; 649 for (btree = &node->btree[probe]; 650 span > 4; btree = &node->btree[probe]) { 651 span /= 2; 652 hash = be32_to_cpu(btree->hashval); 653 654 if (hash < hashwant) 655 probe += span; 656 else if (hash > hashwant) 657 probe -= span; 658 else 659 break; 660 } 661 662 while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashwant)) { 663 btree--; 664 probe--; 665 } 666 667 while ((probe < max) && (be32_to_cpu(btree->hashval) < hashwant)) { 668 btree++; 669 probe++; 670 } 671 672 if (probe == max) 673 fsblkno = be32_to_cpu(node->btree[max-1].before); 674 else 675 fsblkno = be32_to_cpu(node->btree[probe].before); 676 677 fsblkno = xfs_dir2_get_right_blk(parent->fs, core, fsblkno, &error); 678 if (error) { 679 xfs_error("Cannot find right rec!"); 680 goto out; 681 } 682 683 node = (xfs_da_intnode_t *)xfs_dir2_dirblks_get_cached(parent->fs, 684 fsblkno, 1); 685 } while(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC); 686 687 leaf = (xfs_dir2_leaf_t*)node; 688 if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR2_LEAFN_MAGIC) { 689 xfs_error("Leaf's magic number does not match!"); 690 goto out; 691 } 692 693 if (!leaf->hdr.count) 694 goto out; 695 696 for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1; 697 low <= high; ) { 698 mid = (low + high) >> 1; 699 700 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant) 701 break; 702 if (hash < hashwant) 703 low = mid + 1; 704 else 705 high = mid - 1; 706 } 707 708 /* If hash is not the one we want, then the directory does not contain the 709 * entry we're looking for and there is nothing to do anymore. 710 */ 711 if (hash != hashwant) 712 goto out; 713 714 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) 715 mid--; 716 717 for (lep = &leaf->ents[mid]; 718 mid < be16_to_cpu(leaf->hdr.count) && 719 be32_to_cpu(lep->hashval) == hashwant; 720 lep++, mid++) { 721 /* Skip over stale leaf entries. */ 722 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 723 continue; 724 725 newdb = xfs_dir2_dataptr_to_db(parent->fs, be32_to_cpu(lep->address)); 726 if (newdb != curdb) { 727 fsblkno = xfs_dir2_get_right_blk(parent->fs, core, newdb, &error); 728 if (error) { 729 xfs_error("Cannot find data block!"); 730 goto out; 731 } 732 733 buf = xfs_dir2_dirblks_get_cached(parent->fs, fsblkno, 1); 734 data_hdr = (xfs_dir2_data_hdr_t *)buf; 735 if (be32_to_cpu(data_hdr->magic) != XFS_DIR2_DATA_MAGIC) { 736 xfs_error("Leaf directory's data magic No. does not match!"); 737 goto out; 738 } 739 740 curdb = newdb; 741 } 742 743 dep = (xfs_dir2_data_entry_t *)((char *)buf + 744 xfs_dir2_dataptr_to_off(parent->fs, be32_to_cpu(lep->address))); 745 746 start_name = &dep->name[0]; 747 end_name = start_name + dep->namelen; 748 749 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) { 750 xfs_debug("Found entry %s", dname); 751 goto found; 752 } 753 } 754 755 out: 756 return NULL; 757 758 found: 759 ip = xfs_new_inode(parent->fs); 760 ino = be64_to_cpu(dep->inumber); 761 ncore = xfs_dinode_get_core(parent->fs, ino); 762 if (!ncore) { 763 xfs_error("Failed to get dinode!"); 764 goto failed; 765 } 766 767 fill_xfs_inode_pvt(parent->fs, ip, ino); 768 ip->ino = ino; 769 XFS_PVT(ip)->i_ino_blk = ino_to_bytes(parent->fs, ino) >> 770 BLOCK_SHIFT(parent->fs); 771 ip->size = be64_to_cpu(ncore->di_size); 772 773 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) { 774 ip->mode = DT_DIR; 775 xfs_debug("Found a directory inode!"); 776 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) { 777 ip->mode = DT_REG; 778 xfs_debug("Found a file inode!"); 779 xfs_debug("inode size %llu", ip->size); 780 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) { 781 ip->mode = DT_LNK; 782 xfs_debug("Found a symbolic link inode!"); 783 } 784 785 xfs_debug("entry inode's number %lu", ino); 786 787 return ip; 788 789 failed: 790 free(ip); 791 792 return NULL; 793 } 794
