sys/gnu/fs/reiserfs/reiserfs_namei.c

   1 /*-
   2  * Copyright 2000 Hans Reiser
   3  * See README for licensing and copyright details
   4  *
   5  * Ported to FreeBSD by Jean-Sébastien Pédron <jspedron@club-internet.fr>
   6  *
   7  * $FreeBSD$
   8  */
   9
  10 #include <gnu/fs/reiserfs/reiserfs_fs.h>
  11
  12 static int      reiserfs_find_entry(struct reiserfs_node *dp,
  13     const char *name, int namelen,
  14     struct path * path_to_entry, struct reiserfs_dir_entry *de);
  15
  16 MALLOC_DEFINE(M_REISERFSCOOKIES, "reiserfs_cookies",
  17     "ReiserFS VOP_READDIR cookies");
  18
  19 /* -------------------------------------------------------------------
  20  * Lookup functions
  21  * -------------------------------------------------------------------*/
  22
  23 int
  24 reiserfs_lookup(struct vop_cachedlookup_args *ap)
  25 {
  26         int error, retval;
  27         struct vnode *vdp         = ap->a_dvp;
  28         struct vnode **vpp        = ap->a_vpp;
  29         struct componentname *cnp = ap->a_cnp;
  30
  31         int flags         = cnp->cn_flags;
  32         struct thread *td = cnp->cn_thread;
  33         struct cpu_key *saved_ino;
  34
  35         struct vnode *vp;
  36         struct vnode *pdp;  /* Saved dp during symlink work */
  37         struct reiserfs_node *dp;
  38         struct reiserfs_dir_entry de;
  39         INITIALIZE_PATH(path_to_entry);
  40
  41         char c = cnp->cn_nameptr[cnp->cn_namelen];
  42         cnp->cn_nameptr[cnp->cn_namelen] = '\0';
  43         reiserfs_log(LOG_DEBUG, "looking for `%s', %ld (%s)\n",
  44             cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_pnbuf);
  45         cnp->cn_nameptr[cnp->cn_namelen] = c;
  46
  47         vp = NULL;
  48         dp = VTOI(vdp);
  49
  50         if (REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize) < cnp->cn_namelen)
  51                 return (ENAMETOOLONG);
  52
  53         reiserfs_log(LOG_DEBUG, "searching entry\n");
  54         de.de_gen_number_bit_string = 0;
  55         retval = reiserfs_find_entry(dp, cnp->cn_nameptr, cnp->cn_namelen,
  56             &path_to_entry, &de);
  57         pathrelse(&path_to_entry);
  58
  59         if (retval == NAME_FOUND) {
  60                 reiserfs_log(LOG_DEBUG, "found\n");
  61         } else {
  62                 reiserfs_log(LOG_DEBUG, "not found\n");
  63         }
  64
  65         if (retval == NAME_FOUND) {
  66 #if 0
  67                 /* Hide the .reiserfs_priv directory */
  68                 if (reiserfs_xattrs(dp->i_reiserfs) &&
  69                     !old_format_only(dp->i_reiserfs) &&
  70                     REISERFS_SB(dp->i_reiserfs)->priv_root &&
  71                     REISERFS_SB(dp->i_reiserfs)->priv_root->d_inode &&
  72                     de.de_objectid == le32toh(INODE_PKEY(REISERFS_SB(
  73                     dp->i_reiserfs)->priv_root->d_inode)->k_objectid)) {
  74                         return (EACCES);
  75                 }
  76 #endif
  77
  78                 reiserfs_log(LOG_DEBUG, "reading vnode\n");
  79                 pdp = vdp;
  80                 if (flags & ISDOTDOT) {
  81                         saved_ino = (struct cpu_key *)&(de.de_dir_id);
  82                         VOP_UNLOCK(pdp, 0);
  83                         error = reiserfs_iget(vdp->v_mount,
  84                             saved_ino, &vp, td);
  85                         vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY);
  86                         if (error != 0)
  87                                 return (error);
  88                         *vpp = vp;
  89                 } else if (de.de_objectid == dp->i_number &&
  90                     de.de_dir_id == dp->i_ino) {
  91                         VREF(vdp); /* We want ourself, ie "." */
  92                         *vpp = vdp;
  93                 } else {
  94                         if ((error = reiserfs_iget(vdp->v_mount,
  95                             (struct cpu_key *)&(de.de_dir_id), &vp, td)) != 0)
  96                                 return (error);
  97                         *vpp = vp;
  98                 }
  99
 100                 /*
 101                  * Propogate the priv_object flag so we know we're in the
 102                  * priv tree
 103                  */
 104                 /*if (is_reiserfs_priv_object(dir))
 105                         REISERFS_I(inode)->i_flags |= i_priv_object;*/
 106         } else {
 107                 if (retval == IO_ERROR) {
 108                         reiserfs_log(LOG_DEBUG, "IO error\n");
 109                         return (EIO);
 110                 }
 111
 112                 return (ENOENT);
 113         }
 114
 115         /* Insert name into cache if appropriate. */
 116         if (cnp->cn_flags & MAKEENTRY)
 117                 cache_enter(vdp, *vpp, cnp);
 118
 119         reiserfs_log(LOG_DEBUG, "done\n");
 120         return (0);
 121 }
 122
 123 extern struct key MIN_KEY;
 124
 125 int
 126 reiserfs_readdir(struct vop_readdir_args  /* {
 127                 struct vnode *a_vp;
 128                 struct uio *a_uio;
 129                 struct ucred *a_cred;
 130                 int *a_eofflag;
 131                 int *a_ncookies;
 132                 u_long **a_cookies;
 133         } */*ap)
 134 {
 135         int error = 0;
 136         struct dirent dstdp;
 137         struct uio *uio = ap->a_uio;
 138
 139         off_t next_pos;
 140         struct buf *bp;
 141         struct item_head *ih;
 142         struct cpu_key pos_key;
 143         const struct key *rkey;
 144         struct reiserfs_node *ip;
 145         struct reiserfs_dir_entry de;
 146         INITIALIZE_PATH(path_to_entry);
 147         int entry_num, item_num, search_res;
 148
 149         /* The NFS part */
 150         int ncookies = 0;
 151         u_long *cookies = NULL;
 152
 153         /*
 154          * Form key for search the next directory entry using f_pos field of
 155          * file structure
 156          */
 157         ip = VTOI(ap->a_vp);
 158         make_cpu_key(&pos_key,
 159             ip, uio->uio_offset ? uio->uio_offset : DOT_OFFSET,
 160             TYPE_DIRENTRY, 3);
 161         next_pos = cpu_key_k_offset(&pos_key);
 162
 163         reiserfs_log(LOG_DEBUG, "listing entries for "
 164             "(objectid=%d, dirid=%d)\n",
 165             pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id);
 166         reiserfs_log(LOG_DEBUG, "uio_offset = %jd, uio_resid = %d\n",
 167             (intmax_t)uio->uio_offset, uio->uio_resid);
 168
 169         if (ap->a_ncookies && ap->a_cookies) {
 170                 cookies = (u_long *)malloc(
 171                     uio->uio_resid / 16 * sizeof(u_long),
 172                     M_REISERFSCOOKIES, M_WAITOK);
 173         }
 174
 175         while (1) {
 176                 //research:
 177                 /*
 178                  * Search the directory item, containing entry with
 179                  * specified key
 180                  */
 181                 reiserfs_log(LOG_DEBUG, "search directory to read\n");
 182                 search_res = search_by_entry_key(ip->i_reiserfs, &pos_key,
 183                     &path_to_entry, &de);
 184                 if (search_res == IO_ERROR) {
 185                         error = EIO;
 186                         goto out;
 187                 }
 188
 189                 entry_num = de.de_entry_num;
 190                 item_num  = de.de_item_num;
 191                 bp = de.de_bp;
 192                 ih = de.de_ih;
 193
 194                 if (search_res == POSITION_FOUND ||
 195                     entry_num < I_ENTRY_COUNT(ih)) {
 196                         /*
 197                          * Go through all entries in the directory item
 198                          * beginning from the entry, that has been found.
 199                          */
 200                         struct reiserfs_de_head *deh = B_I_DEH(bp, ih) +
 201                             entry_num;
 202
 203                         if (ap->a_ncookies == NULL) {
 204                                 cookies = NULL;
 205                         } else {
 206                                 //ncookies =
 207                         }
 208
 209                         reiserfs_log(LOG_DEBUG,
 210                             "walking through directory entries\n");
 211                         for (; entry_num < I_ENTRY_COUNT(ih);
 212                             entry_num++, deh++) {
 213                                 int d_namlen;
 214                                 char *d_name;
 215                                 off_t d_off;
 216                                 ino_t d_ino;
 217
 218                                 if (!de_visible(deh)) {
 219                                         /* It is hidden entry */
 220                                         continue;
 221                                 }
 222
 223                                 d_namlen = entry_length(bp, ih, entry_num);
 224                                 d_name   = B_I_DEH_ENTRY_FILE_NAME(bp, ih, deh);
 225                                 if (!d_name[d_namlen - 1])
 226                                         d_namlen = strlen(d_name);
 227                                 reiserfs_log(LOG_DEBUG, "  - `%s' (len=%d)\n",
 228                                     d_name, d_namlen);
 229
 230                                 if (d_namlen > REISERFS_MAX_NAME(
 231                                     ip->i_reiserfs->s_blocksize)) {
 232                                         /* Too big to send back to VFS */
 233                                         continue;
 234                                 }
 235
 236 #if 0
 237                                 /* Ignore the .reiserfs_priv entry */
 238                                 if (reiserfs_xattrs(ip->i_reiserfs) &&
 239                                     !old_format_only(ip->i_reiserfs) &&
 240                                     filp->f_dentry == ip->i_reiserfs->s_root &&
 241                                     REISERFS_SB(ip->i_reiserfs)->priv_root &&
 242                                     REISERFS_SB(ip->i_reiserfs)->priv_root->d_inode &&
 243                                     deh_objectid(deh) ==
 244                                     le32toh(INODE_PKEY(REISERFS_SB(
 245                                     ip->i_reiserfs)->priv_root->d_inode)->k_objectid)) {
 246                                         continue;
 247                                 }
 248 #endif
 249
 250                                 d_off = deh_offset(deh);
 251                                 d_ino = deh_objectid(deh);
 252                                 uio->uio_offset = d_off;
 253
 254                                 /* Copy to user land */
 255                                 dstdp.d_fileno = d_ino;
 256                                 dstdp.d_type   = DT_UNKNOWN;
 257                                 dstdp.d_namlen = d_namlen;
 258                                 dstdp.d_reclen = GENERIC_DIRSIZ(&dstdp);
 259                                 bcopy(d_name, dstdp.d_name, dstdp.d_namlen);
 260                                 bzero(dstdp.d_name + dstdp.d_namlen,
 261                                     dstdp.d_reclen -
 262                                     offsetof(struct dirent, d_name) -
 263                                     dstdp.d_namlen);
 264
 265                                 if (d_namlen > 0) {
 266                                         if (dstdp.d_reclen <= uio->uio_resid) {
 267                                                 reiserfs_log(LOG_DEBUG, "     copying to user land\n");
 268                                                 error = uiomove(&dstdp,
 269                                                     dstdp.d_reclen, uio);
 270                                                 if (error)
 271                                                         goto end;
 272                                                 if (cookies != NULL) {
 273                                                         cookies[ncookies] =
 274                                                             d_off;
 275                                                         ncookies++;
 276                                                 }
 277                                         } else
 278                                                 break;
 279                                 } else {
 280                                         error = EIO;
 281                                         break;
 282                                 }
 283
 284                                 next_pos = deh_offset(deh) + 1;
 285                         }
 286                         reiserfs_log(LOG_DEBUG, "...done\n");
 287                 }
 288
 289                 reiserfs_log(LOG_DEBUG, "checking item num (%d == %d ?)\n",
 290                     item_num, B_NR_ITEMS(bp) - 1);
 291                 if (item_num != B_NR_ITEMS(bp) - 1) {
 292                         /* End of directory has been reached */
 293                         reiserfs_log(LOG_DEBUG, "end reached\n");
 294                         if (ap->a_eofflag)
 295                                 *ap->a_eofflag = 1;
 296                         goto end;
 297                 }
 298
 299                 /*
 300                  * Item we went through is last item of node. Using right
 301                  * delimiting key check is it directory end
 302                  */
 303                 reiserfs_log(LOG_DEBUG, "get right key\n");
 304                 rkey = get_rkey(&path_to_entry, ip->i_reiserfs);
 305                 reiserfs_log(LOG_DEBUG, "right key = (objectid=%d, dirid=%d)\n",
 306                     rkey->k_objectid, rkey->k_dir_id);
 307
 308                 reiserfs_log(LOG_DEBUG, "compare it to MIN_KEY\n");
 309                 reiserfs_log(LOG_DEBUG, "MIN KEY = (objectid=%d, dirid=%d)\n",
 310                     MIN_KEY.k_objectid, MIN_KEY.k_dir_id);
 311                 if (comp_le_keys(rkey, &MIN_KEY) == 0) {
 312                         /* Set pos_key to key, that is the smallest and greater
 313                          * that key of the last entry in the item */
 314                         reiserfs_log(LOG_DEBUG, "continuing on the right\n");
 315                         set_cpu_key_k_offset(&pos_key, next_pos);
 316                         continue;
 317                 }
 318
 319                 reiserfs_log(LOG_DEBUG, "compare it to pos_key\n");
 320                 reiserfs_log(LOG_DEBUG, "pos key = (objectid=%d, dirid=%d)\n",
 321                     pos_key.on_disk_key.k_objectid,
 322                     pos_key.on_disk_key.k_dir_id);
 323                 if (COMP_SHORT_KEYS(rkey, &pos_key)) {
 324                         /* End of directory has been reached */
 325                         reiserfs_log(LOG_DEBUG, "end reached (right)\n");
 326                         if (ap->a_eofflag)
 327                                 *ap->a_eofflag = 1;
 328                         goto end;
 329                 }
 330
 331                 /* Directory continues in the right neighboring block */
 332                 reiserfs_log(LOG_DEBUG, "continuing with a new offset\n");
 333                 set_cpu_key_k_offset(&pos_key,
 334                     le_key_k_offset(KEY_FORMAT_3_5, rkey));
 335                 reiserfs_log(LOG_DEBUG,
 336                     "new pos key = (objectid=%d, dirid=%d)\n",
 337                     pos_key.on_disk_key.k_objectid,
 338                     pos_key.on_disk_key.k_dir_id);
 339         }
 340
 341 end:
 342         uio->uio_offset = next_pos;
 343         pathrelse(&path_to_entry);
 344         reiserfs_check_path(&path_to_entry);
 345 out:
 346         if (error && cookies != NULL) {
 347                 free(cookies, M_REISERFSCOOKIES);
 348         } else if (ap->a_ncookies != NULL && ap->a_cookies != NULL) {
 349                 *ap->a_ncookies = ncookies;
 350                 *ap->a_cookies  = cookies;
 351         }
 352         return (error);
 353 }
 354
 355 /* -------------------------------------------------------------------
 356  * Functions from linux/fs/reiserfs/namei.c
 357  * -------------------------------------------------------------------*/
 358
 359
 360 /*
 361  * Directory item contains array of entry headers. This performs binary
 362  * search through that array.
 363  */
 364 static int
 365 bin_search_in_dir_item(struct reiserfs_dir_entry *de, off_t off)
 366 {
 367         struct item_head *ih = de->de_ih;
 368         struct reiserfs_de_head *deh = de->de_deh;
 369         int rbound, lbound, j;
 370
 371         lbound = 0;
 372         rbound = I_ENTRY_COUNT(ih) - 1;
 373
 374         for (j = (rbound + lbound) / 2; lbound <= rbound;
 375             j = (rbound + lbound) / 2) {
 376                 if (off < deh_offset(deh + j)) {
 377                         rbound = j - 1;
 378                         continue;
 379                 }
 380                 if (off > deh_offset(deh + j)) {
 381                         lbound = j + 1;
 382                         continue;
 383                 }
 384
 385                 /* This is not name found, but matched third key component */
 386                 de->de_entry_num = j;
 387                 return (NAME_FOUND);
 388         }
 389
 390         de->de_entry_num = lbound;
 391         return (NAME_NOT_FOUND);
 392 }
 393
 394 /*
 395  * Comment?  Maybe something like set de to point to what the path
 396  * points to?
 397  */
 398 static inline void
 399 set_de_item_location(struct reiserfs_dir_entry *de, struct path *path)
 400 {
 401
 402         de->de_bp       = get_last_bp(path);
 403         de->de_ih       = get_ih(path);
 404         de->de_deh      = B_I_DEH(de->de_bp, de->de_ih);
 405         de->de_item_num = PATH_LAST_POSITION(path);
 406 }
 407
 408 /*
 409  * de_bh, de_ih, de_deh (points to first element of array), de_item_num
 410  * is set
 411  */
 412 void
 413 set_de_name_and_namelen(struct reiserfs_dir_entry *de)
 414 {
 415         struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num;
 416
 417         if (de->de_entry_num >= ih_entry_count(de->de_ih)) {
 418                 reiserfs_log(LOG_DEBUG, "BUG\n");
 419                 return;
 420         }
 421
 422         de->de_entrylen = entry_length(de->de_bp, de->de_ih, de->de_entry_num);
 423         de->de_namelen  = de->de_entrylen - (de_with_sd(deh) ? SD_SIZE : 0);
 424         de->de_name     = B_I_PITEM(de->de_bp, de->de_ih) + deh_location(deh);
 425         if (de->de_name[de->de_namelen - 1] == 0)
 426                 de->de_namelen = strlen(de->de_name);
 427 }
 428
 429 /* What entry points to */
 430 static inline void
 431 set_de_object_key(struct reiserfs_dir_entry *de)
 432 {
 433
 434         if (de->de_entry_num >= ih_entry_count(de->de_ih)) {
 435                 reiserfs_log(LOG_DEBUG, "BUG\n");
 436                 return;
 437         }
 438         de->de_dir_id   = deh_dir_id(&(de->de_deh[de->de_entry_num]));
 439         de->de_objectid = deh_objectid(&(de->de_deh[de->de_entry_num]));
 440 }
 441
 442 static inline void
 443 store_de_entry_key(struct reiserfs_dir_entry *de)
 444 {
 445         struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num;
 446
 447         if (de->de_entry_num >= ih_entry_count(de->de_ih)) {
 448                 reiserfs_log(LOG_DEBUG, "BUG\n");
 449                 return;
 450         }
 451
 452         /* Store key of the found entry */
 453         de->de_entry_key.version = KEY_FORMAT_3_5;
 454         de->de_entry_key.on_disk_key.k_dir_id =
 455             le32toh(de->de_ih->ih_key.k_dir_id);
 456         de->de_entry_key.on_disk_key.k_objectid =
 457             le32toh(de->de_ih->ih_key.k_objectid);
 458         set_cpu_key_k_offset(&(de->de_entry_key), deh_offset(deh));
 459         set_cpu_key_k_type(&(de->de_entry_key), TYPE_DIRENTRY);
 460 }
 461
 462 /*
 463  * We assign a key to each directory item, and place multiple entries in
 464  * a single directory item. A directory item has a key equal to the key
 465  * of the first directory entry in it.
 466  *
 467  * This function first calls search_by_key, then, if item whose first
 468  * entry matches is not found it looks for the entry inside directory
 469  * item found by search_by_key. Fills the path to the entry, and to the
 470  * entry position in the item
 471  */
 472 int
 473 search_by_entry_key(struct reiserfs_sb_info *sbi,
 474     const struct cpu_key *key, struct path *path,
 475     struct reiserfs_dir_entry *de)
 476 {
 477         int retval;
 478
 479         reiserfs_log(LOG_DEBUG, "searching in (objectid=%d,dirid=%d)\n",
 480             key->on_disk_key.k_objectid, key->on_disk_key.k_dir_id);
 481         retval = search_item(sbi, key, path);
 482         switch (retval) {
 483         case ITEM_NOT_FOUND:
 484                 if (!PATH_LAST_POSITION(path)) {
 485                         reiserfs_log(LOG_DEBUG,
 486                             "search_by_key returned item position == 0");
 487                         pathrelse(path);
 488                         return (IO_ERROR);
 489                 }
 490                 PATH_LAST_POSITION(path)--;
 491                 reiserfs_log(LOG_DEBUG, "search_by_key did not found it\n");
 492                 break;
 493         case ITEM_FOUND:
 494                 reiserfs_log(LOG_DEBUG, "search_by_key found it\n");
 495                 break;
 496         case IO_ERROR:
 497                 return (retval);
 498         default:
 499                 pathrelse(path);
 500                 reiserfs_log(LOG_DEBUG, "no path to here");
 501                 return (IO_ERROR);
 502         }
 503
 504         reiserfs_log(LOG_DEBUG, "set item location\n");
 505         set_de_item_location(de, path);
 506
 507         /*
 508          * Binary search in directory item by third component of the
 509          * key. Sets de->de_entry_num of de
 510          */
 511         reiserfs_log(LOG_DEBUG, "bin_search_in_dir_item\n");
 512         retval = bin_search_in_dir_item(de, cpu_key_k_offset(key));
 513         path->pos_in_item = de->de_entry_num;
 514         if (retval != NAME_NOT_FOUND) {
 515                 /*
 516                  * Ugly, but rename needs de_bp, de_deh, de_name, de_namelen,
 517                  * de_objectid set
 518                  */
 519                 set_de_name_and_namelen(de);
 520                 set_de_object_key(de);
 521                 reiserfs_log(LOG_DEBUG, "set (objectid=%d,dirid=%d)\n",
 522                     de->de_objectid, de->de_dir_id);
 523         }
 524
 525         return (retval);
 526 }
 527
 528 static uint32_t
 529 get_third_component(struct reiserfs_sb_info *sbi, const char *name, int len)
 530 {
 531         uint32_t res;
 532
 533         if (!len || (len == 1 && name[0] == '.'))
 534                 return (DOT_OFFSET);
 535
 536         if (len == 2 && name[0] == '.' && name[1] == '.')
 537                 return (DOT_DOT_OFFSET);
 538
 539         res = REISERFS_SB(sbi)->s_hash_function(name, len);
 540
 541         /* Take bits from 7-th to 30-th including both bounds */
 542         res = GET_HASH_VALUE(res);
 543         if (res == 0)
 544                 /*
 545                  * Needed to have no names before "." and ".." those have hash
 546                  * value == 0 and generation counters 1 and 2 accordingly
 547                  */
 548                 res = 128;
 549
 550         return (res + MAX_GENERATION_NUMBER);
 551 }
 552
 553 static int
 554 reiserfs_match(struct reiserfs_dir_entry *de, const char *name, int namelen)
 555 {
 556         int retval = NAME_NOT_FOUND;
 557
 558         if ((namelen == de->de_namelen) &&
 559             !memcmp(de->de_name, name, de->de_namelen))
 560                 retval = (de_visible(de->de_deh + de->de_entry_num) ?
 561                     NAME_FOUND : NAME_FOUND_INVISIBLE);
 562
 563         return (retval);
 564 }
 565
 566 /*
 567  * de's de_bh, de_ih, de_deh, de_item_num, de_entry_num are set already
 568  * Used when hash collisions exist
 569  */
 570 static int
 571 linear_search_in_dir_item(struct cpu_key *key, struct reiserfs_dir_entry *de,
 572     const char *name, int namelen)
 573 {
 574         int i;
 575         int retval;
 576         struct reiserfs_de_head * deh = de->de_deh;
 577
 578         i = de->de_entry_num;
 579
 580         if (i == I_ENTRY_COUNT(de->de_ih) ||
 581             GET_HASH_VALUE(deh_offset(deh + i)) !=
 582             GET_HASH_VALUE(cpu_key_k_offset(key))) {
 583                 i--;
 584         }
 585
 586         /*RFALSE( de->de_deh != B_I_DEH (de->de_bh, de->de_ih),
 587           "vs-7010: array of entry headers not found");*/
 588
 589         deh += i;
 590
 591         for (; i >= 0; i--, deh--) {
 592                 if (GET_HASH_VALUE(deh_offset(deh)) !=
 593                     GET_HASH_VALUE(cpu_key_k_offset(key))) {
 594                         /*
 595                          * Hash value does not match, no need to check
 596                          * whole name
 597                          */
 598                         reiserfs_log(LOG_DEBUG, "name `%s' not found\n", name);
 599                         return (NAME_NOT_FOUND);
 600                 }
 601
 602                 /* Mark that this generation number is used */
 603                 if (de->de_gen_number_bit_string)
 604                         set_bit(GET_GENERATION_NUMBER(deh_offset(deh)),
 605                             (unsigned long *)de->de_gen_number_bit_string);
 606
 607                 /* Calculate pointer to name and namelen */
 608                 de->de_entry_num = i;
 609                 set_de_name_and_namelen(de);
 610
 611                 if ((retval = reiserfs_match(de, name, namelen)) !=
 612                     NAME_NOT_FOUND) {
 613                         /*
 614                          * de's de_name, de_namelen, de_recordlen are set.
 615                          * Fill the rest:
 616                          */
 617                         /* key of pointed object */
 618                         set_de_object_key(de);
 619                         store_de_entry_key(de);
 620
 621                         /* retval can be NAME_FOUND or NAME_FOUND_INVISIBLE */
 622                         reiserfs_log(LOG_DEBUG,
 623                             "reiserfs_match answered `%d'\n",
 624                             retval);
 625                         return (retval);
 626                 }
 627         }
 628
 629         if (GET_GENERATION_NUMBER(le_ih_k_offset(de->de_ih)) == 0)
 630                 /*
 631                  * We have reached left most entry in the node. In common
 632                  * we have to go to the left neighbor, but if generation
 633                  * counter is 0 already, we know for sure, that there is
 634                  * no name with the same hash value
 635                  */
 636                 /* FIXME: this work correctly only because hash value can
 637                  * not be 0. Btw, in case of Yura's hash it is probably
 638                  * possible, so, this is a bug
 639                  */
 640                 return (NAME_NOT_FOUND);
 641
 642         /*RFALSE(de->de_item_num,
 643             "vs-7015: two diritems of the same directory in one node?");*/
 644
 645         return (GOTO_PREVIOUS_ITEM);
 646 }
 647
 648 /*
 649  * May return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND
 650  * FIXME: should add something like IOERROR
 651  */
 652 static int
 653 reiserfs_find_entry(struct reiserfs_node *dp, const char *name, int namelen,
 654     struct path * path_to_entry, struct reiserfs_dir_entry *de)
 655 {
 656         struct cpu_key key_to_search;
 657         int retval;
 658
 659         if (namelen > REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize))
 660                 return NAME_NOT_FOUND;
 661
 662         /* We will search for this key in the tree */
 663         make_cpu_key(&key_to_search, dp,
 664             get_third_component(dp->i_reiserfs, name, namelen),
 665             TYPE_DIRENTRY, 3);
 666
 667         while (1) {
 668                 reiserfs_log(LOG_DEBUG, "search by entry key\n");
 669                 retval = search_by_entry_key(dp->i_reiserfs, &key_to_search,
 670                     path_to_entry, de);
 671                 if (retval == IO_ERROR) {
 672                         reiserfs_log(LOG_DEBUG, "IO error in %s\n",
 673                             __FUNCTION__);
 674                         return IO_ERROR;
 675                 }
 676
 677                 /* Compare names for all entries having given hash value */
 678                 reiserfs_log(LOG_DEBUG, "linear search for `%s'\n", name);
 679                 retval = linear_search_in_dir_item(&key_to_search, de,
 680                     name, namelen);
 681                 if (retval != GOTO_PREVIOUS_ITEM) {
 682                         /*
 683                          * There is no need to scan directory anymore.
 684                          * Given entry found or does not exist
 685                          */
 686                         reiserfs_log(LOG_DEBUG, "linear search returned "
 687                             "(objectid=%d,dirid=%d)\n",
 688                             de->de_objectid, de->de_dir_id);
 689                         path_to_entry->pos_in_item = de->de_entry_num;
 690                         return retval;
 691                 }
 692
 693                 /*
 694                  * There is left neighboring item of this directory and
 695                  * given entry can be there
 696                  */
 697                 set_cpu_key_k_offset(&key_to_search,
 698                     le_ih_k_offset(de->de_ih) - 1);
 699                 pathrelse(path_to_entry);
 700         } /* while (1) */
 701 }