core/fs/xfs/xfs_dir2.c

   1 /*
   2  * Copyright (c) 2012-2013 Paulo Alcantara <pcacjr@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 }