1147476Sdumbbell/*- 2147476Sdumbbell * Copyright 2000 Hans Reiser 3147476Sdumbbell * See README for licensing and copyright details 4147476Sdumbbell * 5147476Sdumbbell * Ported to FreeBSD by Jean-S�bastien P�dron <jspedron@club-internet.fr> 6147476Sdumbbell * 7147476Sdumbbell * $FreeBSD$ 8147476Sdumbbell */ 9147476Sdumbbell 10147476Sdumbbell#include <gnu/fs/reiserfs/reiserfs_fs.h> 11147476Sdumbbell 12147476Sdumbbellstatic int reiserfs_find_entry(struct reiserfs_node *dp, 13147476Sdumbbell const char *name, int namelen, 14147476Sdumbbell struct path * path_to_entry, struct reiserfs_dir_entry *de); 15147476Sdumbbell 16151897SrwatsonMALLOC_DEFINE(M_REISERFSCOOKIES, "reiserfs_cookies", 17147476Sdumbbell "ReiserFS VOP_READDIR cookies"); 18147476Sdumbbell 19147476Sdumbbell/* ------------------------------------------------------------------- 20147476Sdumbbell * Lookup functions 21147476Sdumbbell * -------------------------------------------------------------------*/ 22147476Sdumbbell 23147476Sdumbbellint 24147476Sdumbbellreiserfs_lookup(struct vop_cachedlookup_args *ap) 25147476Sdumbbell{ 26147476Sdumbbell int error, retval; 27147476Sdumbbell struct vnode *vdp = ap->a_dvp; 28147476Sdumbbell struct vnode **vpp = ap->a_vpp; 29147476Sdumbbell struct componentname *cnp = ap->a_cnp; 30147476Sdumbbell 31147476Sdumbbell int flags = cnp->cn_flags; 32147476Sdumbbell struct thread *td = cnp->cn_thread; 33151532Sdumbbell struct cpu_key *saved_ino; 34147476Sdumbbell 35147476Sdumbbell struct vnode *vp; 36147476Sdumbbell struct vnode *pdp; /* Saved dp during symlink work */ 37147476Sdumbbell struct reiserfs_node *dp; 38147476Sdumbbell struct reiserfs_dir_entry de; 39147476Sdumbbell INITIALIZE_PATH(path_to_entry); 40147476Sdumbbell 41147476Sdumbbell char c = cnp->cn_nameptr[cnp->cn_namelen]; 42147476Sdumbbell cnp->cn_nameptr[cnp->cn_namelen] = '\0'; 43147476Sdumbbell reiserfs_log(LOG_DEBUG, "looking for `%s', %ld (%s)\n", 44147476Sdumbbell cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_pnbuf); 45147476Sdumbbell cnp->cn_nameptr[cnp->cn_namelen] = c; 46147476Sdumbbell 47147476Sdumbbell vp = NULL; 48147476Sdumbbell dp = VTOI(vdp); 49147476Sdumbbell 50147476Sdumbbell if (REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize) < cnp->cn_namelen) 51147476Sdumbbell return (ENAMETOOLONG); 52147476Sdumbbell 53147476Sdumbbell reiserfs_log(LOG_DEBUG, "searching entry\n"); 54147476Sdumbbell de.de_gen_number_bit_string = 0; 55147476Sdumbbell retval = reiserfs_find_entry(dp, cnp->cn_nameptr, cnp->cn_namelen, 56147476Sdumbbell &path_to_entry, &de); 57147476Sdumbbell pathrelse(&path_to_entry); 58147476Sdumbbell 59147476Sdumbbell if (retval == NAME_FOUND) { 60147476Sdumbbell reiserfs_log(LOG_DEBUG, "found\n"); 61147476Sdumbbell } else { 62147476Sdumbbell reiserfs_log(LOG_DEBUG, "not found\n"); 63147476Sdumbbell } 64147476Sdumbbell 65147476Sdumbbell if (retval == NAME_FOUND) { 66147476Sdumbbell#if 0 67147476Sdumbbell /* Hide the .reiserfs_priv directory */ 68147476Sdumbbell if (reiserfs_xattrs(dp->i_reiserfs) && 69147476Sdumbbell !old_format_only(dp->i_reiserfs) && 70147476Sdumbbell REISERFS_SB(dp->i_reiserfs)->priv_root && 71147476Sdumbbell REISERFS_SB(dp->i_reiserfs)->priv_root->d_inode && 72147476Sdumbbell de.de_objectid == le32toh(INODE_PKEY(REISERFS_SB( 73147476Sdumbbell dp->i_reiserfs)->priv_root->d_inode)->k_objectid)) { 74147476Sdumbbell return (EACCES); 75147476Sdumbbell } 76147476Sdumbbell#endif 77147476Sdumbbell 78147476Sdumbbell reiserfs_log(LOG_DEBUG, "reading vnode\n"); 79147476Sdumbbell pdp = vdp; 80147476Sdumbbell if (flags & ISDOTDOT) { 81151532Sdumbbell saved_ino = (struct cpu_key *)&(de.de_dir_id); 82175294Sattilio VOP_UNLOCK(pdp, 0); 83147476Sdumbbell error = reiserfs_iget(vdp->v_mount, 84151532Sdumbbell saved_ino, &vp, td); 85175202Sattilio vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY); 86147476Sdumbbell if (error != 0) 87147476Sdumbbell return (error); 88147476Sdumbbell *vpp = vp; 89147476Sdumbbell } else if (de.de_objectid == dp->i_number && 90147476Sdumbbell de.de_dir_id == dp->i_ino) { 91147476Sdumbbell VREF(vdp); /* We want ourself, ie "." */ 92147476Sdumbbell *vpp = vdp; 93147476Sdumbbell } else { 94147476Sdumbbell if ((error = reiserfs_iget(vdp->v_mount, 95147476Sdumbbell (struct cpu_key *)&(de.de_dir_id), &vp, td)) != 0) 96147476Sdumbbell return (error); 97147476Sdumbbell *vpp = vp; 98147476Sdumbbell } 99147476Sdumbbell 100147476Sdumbbell /* 101147476Sdumbbell * Propogate the priv_object flag so we know we're in the 102147476Sdumbbell * priv tree 103147476Sdumbbell */ 104147476Sdumbbell /*if (is_reiserfs_priv_object(dir)) 105147476Sdumbbell REISERFS_I(inode)->i_flags |= i_priv_object;*/ 106147476Sdumbbell } else { 107147476Sdumbbell if (retval == IO_ERROR) { 108147476Sdumbbell reiserfs_log(LOG_DEBUG, "IO error\n"); 109147476Sdumbbell return (EIO); 110147476Sdumbbell } 111147476Sdumbbell 112147476Sdumbbell return (ENOENT); 113147476Sdumbbell } 114147476Sdumbbell 115147476Sdumbbell /* Insert name into cache if appropriate. */ 116147476Sdumbbell if (cnp->cn_flags & MAKEENTRY) 117147476Sdumbbell cache_enter(vdp, *vpp, cnp); 118147476Sdumbbell 119147476Sdumbbell reiserfs_log(LOG_DEBUG, "done\n"); 120147476Sdumbbell return (0); 121147476Sdumbbell} 122147476Sdumbbell 123147476Sdumbbellextern struct key MIN_KEY; 124147476Sdumbbell 125147476Sdumbbellint 126147476Sdumbbellreiserfs_readdir(struct vop_readdir_args /* { 127147476Sdumbbell struct vnode *a_vp; 128147476Sdumbbell struct uio *a_uio; 129147476Sdumbbell struct ucred *a_cred; 130147476Sdumbbell int *a_eofflag; 131147476Sdumbbell int *a_ncookies; 132147476Sdumbbell u_long **a_cookies; 133147476Sdumbbell } */*ap) 134147476Sdumbbell{ 135147476Sdumbbell int error = 0; 136147476Sdumbbell struct dirent dstdp; 137147476Sdumbbell struct uio *uio = ap->a_uio; 138147476Sdumbbell 139147476Sdumbbell off_t next_pos; 140147476Sdumbbell struct buf *bp; 141147476Sdumbbell struct item_head *ih; 142147476Sdumbbell struct cpu_key pos_key; 143147476Sdumbbell const struct key *rkey; 144147476Sdumbbell struct reiserfs_node *ip; 145147476Sdumbbell struct reiserfs_dir_entry de; 146147476Sdumbbell INITIALIZE_PATH(path_to_entry); 147147476Sdumbbell int entry_num, item_num, search_res; 148147476Sdumbbell 149147476Sdumbbell /* The NFS part */ 150147476Sdumbbell int ncookies = 0; 151147476Sdumbbell u_long *cookies = NULL; 152147476Sdumbbell 153147476Sdumbbell /* 154147476Sdumbbell * Form key for search the next directory entry using f_pos field of 155147476Sdumbbell * file structure 156147476Sdumbbell */ 157147476Sdumbbell ip = VTOI(ap->a_vp); 158147476Sdumbbell make_cpu_key(&pos_key, 159147476Sdumbbell ip, uio->uio_offset ? uio->uio_offset : DOT_OFFSET, 160147476Sdumbbell TYPE_DIRENTRY, 3); 161147476Sdumbbell next_pos = cpu_key_k_offset(&pos_key); 162147476Sdumbbell 163147476Sdumbbell reiserfs_log(LOG_DEBUG, "listing entries for " 164147476Sdumbbell "(objectid=%d, dirid=%d)\n", 165147476Sdumbbell pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id); 166147476Sdumbbell reiserfs_log(LOG_DEBUG, "uio_offset = %jd, uio_resid = %d\n", 167147476Sdumbbell (intmax_t)uio->uio_offset, uio->uio_resid); 168147476Sdumbbell 169147476Sdumbbell if (ap->a_ncookies && ap->a_cookies) { 170147476Sdumbbell cookies = (u_long *)malloc( 171147476Sdumbbell uio->uio_resid / 16 * sizeof(u_long), 172147476Sdumbbell M_REISERFSCOOKIES, M_WAITOK); 173147476Sdumbbell } 174147476Sdumbbell 175147476Sdumbbell while (1) { 176147476Sdumbbell //research: 177147476Sdumbbell /* 178147476Sdumbbell * Search the directory item, containing entry with 179147476Sdumbbell * specified key 180147476Sdumbbell */ 181147476Sdumbbell reiserfs_log(LOG_DEBUG, "search directory to read\n"); 182147476Sdumbbell search_res = search_by_entry_key(ip->i_reiserfs, &pos_key, 183147476Sdumbbell &path_to_entry, &de); 184147476Sdumbbell if (search_res == IO_ERROR) { 185147476Sdumbbell error = EIO; 186147476Sdumbbell goto out; 187147476Sdumbbell } 188147476Sdumbbell 189147476Sdumbbell entry_num = de.de_entry_num; 190147476Sdumbbell item_num = de.de_item_num; 191147476Sdumbbell bp = de.de_bp; 192147476Sdumbbell ih = de.de_ih; 193147476Sdumbbell 194147476Sdumbbell if (search_res == POSITION_FOUND || 195147476Sdumbbell entry_num < I_ENTRY_COUNT(ih)) { 196147476Sdumbbell /* 197147476Sdumbbell * Go through all entries in the directory item 198147476Sdumbbell * beginning from the entry, that has been found. 199147476Sdumbbell */ 200147476Sdumbbell struct reiserfs_de_head *deh = B_I_DEH(bp, ih) + 201147476Sdumbbell entry_num; 202147476Sdumbbell 203147476Sdumbbell if (ap->a_ncookies == NULL) { 204147476Sdumbbell cookies = NULL; 205147476Sdumbbell } else { 206147476Sdumbbell //ncookies = 207147476Sdumbbell } 208147476Sdumbbell 209147476Sdumbbell reiserfs_log(LOG_DEBUG, 210147476Sdumbbell "walking through directory entries\n"); 211147476Sdumbbell for (; entry_num < I_ENTRY_COUNT(ih); 212147476Sdumbbell entry_num++, deh++) { 213147476Sdumbbell int d_namlen; 214147476Sdumbbell char *d_name; 215147476Sdumbbell off_t d_off; 216147476Sdumbbell ino_t d_ino; 217147476Sdumbbell 218147476Sdumbbell if (!de_visible(deh)) { 219147476Sdumbbell /* It is hidden entry */ 220147476Sdumbbell continue; 221147476Sdumbbell } 222147476Sdumbbell 223147476Sdumbbell d_namlen = entry_length(bp, ih, entry_num); 224147476Sdumbbell d_name = B_I_DEH_ENTRY_FILE_NAME(bp, ih, deh); 225147476Sdumbbell if (!d_name[d_namlen - 1]) 226147476Sdumbbell d_namlen = strlen(d_name); 227147476Sdumbbell reiserfs_log(LOG_DEBUG, " - `%s' (len=%d)\n", 228147476Sdumbbell d_name, d_namlen); 229147476Sdumbbell 230147476Sdumbbell if (d_namlen > REISERFS_MAX_NAME( 231147476Sdumbbell ip->i_reiserfs->s_blocksize)) { 232147476Sdumbbell /* Too big to send back to VFS */ 233147476Sdumbbell continue; 234147476Sdumbbell } 235147476Sdumbbell 236147476Sdumbbell#if 0 237147476Sdumbbell /* Ignore the .reiserfs_priv entry */ 238147476Sdumbbell if (reiserfs_xattrs(ip->i_reiserfs) && 239147476Sdumbbell !old_format_only(ip->i_reiserfs) && 240147476Sdumbbell filp->f_dentry == ip->i_reiserfs->s_root && 241147476Sdumbbell REISERFS_SB(ip->i_reiserfs)->priv_root && 242147476Sdumbbell REISERFS_SB(ip->i_reiserfs)->priv_root->d_inode && 243147476Sdumbbell deh_objectid(deh) == 244147476Sdumbbell le32toh(INODE_PKEY(REISERFS_SB( 245147476Sdumbbell ip->i_reiserfs)->priv_root->d_inode)->k_objectid)) { 246147476Sdumbbell continue; 247147476Sdumbbell } 248147476Sdumbbell#endif 249147476Sdumbbell 250147476Sdumbbell d_off = deh_offset(deh); 251147476Sdumbbell d_ino = deh_objectid(deh); 252147476Sdumbbell uio->uio_offset = d_off; 253147476Sdumbbell 254147476Sdumbbell /* Copy to user land */ 255147476Sdumbbell dstdp.d_fileno = d_ino; 256147476Sdumbbell dstdp.d_type = DT_UNKNOWN; 257147476Sdumbbell dstdp.d_namlen = d_namlen; 258147476Sdumbbell dstdp.d_reclen = GENERIC_DIRSIZ(&dstdp); 259147476Sdumbbell bcopy(d_name, dstdp.d_name, dstdp.d_namlen); 260147476Sdumbbell bzero(dstdp.d_name + dstdp.d_namlen, 261147476Sdumbbell dstdp.d_reclen - 262147476Sdumbbell offsetof(struct dirent, d_name) - 263147476Sdumbbell dstdp.d_namlen); 264147476Sdumbbell 265147476Sdumbbell if (d_namlen > 0) { 266147476Sdumbbell if (dstdp.d_reclen <= uio->uio_resid) { 267147476Sdumbbell reiserfs_log(LOG_DEBUG, " copying to user land\n"); 268147476Sdumbbell error = uiomove(&dstdp, 269147476Sdumbbell dstdp.d_reclen, uio); 270147476Sdumbbell if (error) 271147476Sdumbbell goto end; 272147476Sdumbbell if (cookies != NULL) { 273147476Sdumbbell cookies[ncookies] = 274147476Sdumbbell d_off; 275147476Sdumbbell ncookies++; 276147476Sdumbbell } 277147476Sdumbbell } else 278147476Sdumbbell break; 279147476Sdumbbell } else { 280147476Sdumbbell error = EIO; 281147476Sdumbbell break; 282147476Sdumbbell } 283147476Sdumbbell 284147476Sdumbbell next_pos = deh_offset(deh) + 1; 285147476Sdumbbell } 286147476Sdumbbell reiserfs_log(LOG_DEBUG, "...done\n"); 287147476Sdumbbell } 288147476Sdumbbell 289147476Sdumbbell reiserfs_log(LOG_DEBUG, "checking item num (%d == %d ?)\n", 290147476Sdumbbell item_num, B_NR_ITEMS(bp) - 1); 291147476Sdumbbell if (item_num != B_NR_ITEMS(bp) - 1) { 292147476Sdumbbell /* End of directory has been reached */ 293147476Sdumbbell reiserfs_log(LOG_DEBUG, "end reached\n"); 294147476Sdumbbell if (ap->a_eofflag) 295147476Sdumbbell *ap->a_eofflag = 1; 296147476Sdumbbell goto end; 297147476Sdumbbell } 298147476Sdumbbell 299147476Sdumbbell /* 300147476Sdumbbell * Item we went through is last item of node. Using right 301147476Sdumbbell * delimiting key check is it directory end 302147476Sdumbbell */ 303147476Sdumbbell reiserfs_log(LOG_DEBUG, "get right key\n"); 304147476Sdumbbell rkey = get_rkey(&path_to_entry, ip->i_reiserfs); 305147476Sdumbbell reiserfs_log(LOG_DEBUG, "right key = (objectid=%d, dirid=%d)\n", 306147476Sdumbbell rkey->k_objectid, rkey->k_dir_id); 307147476Sdumbbell 308147476Sdumbbell reiserfs_log(LOG_DEBUG, "compare it to MIN_KEY\n"); 309147476Sdumbbell reiserfs_log(LOG_DEBUG, "MIN KEY = (objectid=%d, dirid=%d)\n", 310147476Sdumbbell MIN_KEY.k_objectid, MIN_KEY.k_dir_id); 311147476Sdumbbell if (comp_le_keys(rkey, &MIN_KEY) == 0) { 312147476Sdumbbell /* Set pos_key to key, that is the smallest and greater 313147476Sdumbbell * that key of the last entry in the item */ 314147476Sdumbbell reiserfs_log(LOG_DEBUG, "continuing on the right\n"); 315147476Sdumbbell set_cpu_key_k_offset(&pos_key, next_pos); 316147476Sdumbbell continue; 317147476Sdumbbell } 318147476Sdumbbell 319147476Sdumbbell reiserfs_log(LOG_DEBUG, "compare it to pos_key\n"); 320147476Sdumbbell reiserfs_log(LOG_DEBUG, "pos key = (objectid=%d, dirid=%d)\n", 321147476Sdumbbell pos_key.on_disk_key.k_objectid, 322147476Sdumbbell pos_key.on_disk_key.k_dir_id); 323147476Sdumbbell if (COMP_SHORT_KEYS(rkey, &pos_key)) { 324147476Sdumbbell /* End of directory has been reached */ 325147476Sdumbbell reiserfs_log(LOG_DEBUG, "end reached (right)\n"); 326147476Sdumbbell if (ap->a_eofflag) 327147476Sdumbbell *ap->a_eofflag = 1; 328147476Sdumbbell goto end; 329147476Sdumbbell } 330147476Sdumbbell 331147476Sdumbbell /* Directory continues in the right neighboring block */ 332147476Sdumbbell reiserfs_log(LOG_DEBUG, "continuing with a new offset\n"); 333147476Sdumbbell set_cpu_key_k_offset(&pos_key, 334147476Sdumbbell le_key_k_offset(KEY_FORMAT_3_5, rkey)); 335147476Sdumbbell reiserfs_log(LOG_DEBUG, 336147476Sdumbbell "new pos key = (objectid=%d, dirid=%d)\n", 337147476Sdumbbell pos_key.on_disk_key.k_objectid, 338147476Sdumbbell pos_key.on_disk_key.k_dir_id); 339147476Sdumbbell } 340147476Sdumbbell 341147476Sdumbbellend: 342147476Sdumbbell uio->uio_offset = next_pos; 343147476Sdumbbell pathrelse(&path_to_entry); 344147476Sdumbbell reiserfs_check_path(&path_to_entry); 345147476Sdumbbellout: 346147476Sdumbbell if (error && cookies != NULL) { 347147476Sdumbbell free(cookies, M_REISERFSCOOKIES); 348147476Sdumbbell } else if (ap->a_ncookies != NULL && ap->a_cookies != NULL) { 349147476Sdumbbell *ap->a_ncookies = ncookies; 350147476Sdumbbell *ap->a_cookies = cookies; 351147476Sdumbbell } 352147476Sdumbbell return (error); 353147476Sdumbbell} 354147476Sdumbbell 355147476Sdumbbell/* ------------------------------------------------------------------- 356147476Sdumbbell * Functions from linux/fs/reiserfs/namei.c 357147476Sdumbbell * -------------------------------------------------------------------*/ 358147476Sdumbbell 359147476Sdumbbell 360147476Sdumbbell/* 361147476Sdumbbell * Directory item contains array of entry headers. This performs binary 362147476Sdumbbell * search through that array. 363147476Sdumbbell */ 364147476Sdumbbellstatic int 365147476Sdumbbellbin_search_in_dir_item(struct reiserfs_dir_entry *de, off_t off) 366147476Sdumbbell{ 367147476Sdumbbell struct item_head *ih = de->de_ih; 368147476Sdumbbell struct reiserfs_de_head *deh = de->de_deh; 369147476Sdumbbell int rbound, lbound, j; 370147476Sdumbbell 371147476Sdumbbell lbound = 0; 372147476Sdumbbell rbound = I_ENTRY_COUNT(ih) - 1; 373147476Sdumbbell 374147476Sdumbbell for (j = (rbound + lbound) / 2; lbound <= rbound; 375147476Sdumbbell j = (rbound + lbound) / 2) { 376147476Sdumbbell if (off < deh_offset(deh + j)) { 377147476Sdumbbell rbound = j - 1; 378147476Sdumbbell continue; 379147476Sdumbbell } 380147476Sdumbbell if (off > deh_offset(deh + j)) { 381147476Sdumbbell lbound = j + 1; 382147476Sdumbbell continue; 383147476Sdumbbell } 384147476Sdumbbell 385147476Sdumbbell /* This is not name found, but matched third key component */ 386147476Sdumbbell de->de_entry_num = j; 387147476Sdumbbell return (NAME_FOUND); 388147476Sdumbbell } 389147476Sdumbbell 390147476Sdumbbell de->de_entry_num = lbound; 391147476Sdumbbell return (NAME_NOT_FOUND); 392147476Sdumbbell} 393147476Sdumbbell 394147476Sdumbbell/* 395147476Sdumbbell * Comment? Maybe something like set de to point to what the path 396147476Sdumbbell * points to? 397147476Sdumbbell */ 398147476Sdumbbellstatic inline void 399147476Sdumbbellset_de_item_location(struct reiserfs_dir_entry *de, struct path *path) 400147476Sdumbbell{ 401147476Sdumbbell 402147476Sdumbbell de->de_bp = get_last_bp(path); 403147476Sdumbbell de->de_ih = get_ih(path); 404147476Sdumbbell de->de_deh = B_I_DEH(de->de_bp, de->de_ih); 405147476Sdumbbell de->de_item_num = PATH_LAST_POSITION(path); 406147476Sdumbbell} 407147476Sdumbbell 408147476Sdumbbell/* 409147476Sdumbbell * de_bh, de_ih, de_deh (points to first element of array), de_item_num 410147476Sdumbbell * is set 411147476Sdumbbell */ 412170491Smjacobvoid 413147476Sdumbbellset_de_name_and_namelen(struct reiserfs_dir_entry *de) 414147476Sdumbbell{ 415147476Sdumbbell struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num; 416147476Sdumbbell 417147476Sdumbbell if (de->de_entry_num >= ih_entry_count(de->de_ih)) { 418147476Sdumbbell reiserfs_log(LOG_DEBUG, "BUG\n"); 419147476Sdumbbell return; 420147476Sdumbbell } 421147476Sdumbbell 422147476Sdumbbell de->de_entrylen = entry_length(de->de_bp, de->de_ih, de->de_entry_num); 423147476Sdumbbell de->de_namelen = de->de_entrylen - (de_with_sd(deh) ? SD_SIZE : 0); 424147476Sdumbbell de->de_name = B_I_PITEM(de->de_bp, de->de_ih) + deh_location(deh); 425147476Sdumbbell if (de->de_name[de->de_namelen - 1] == 0) 426147476Sdumbbell de->de_namelen = strlen(de->de_name); 427147476Sdumbbell} 428147476Sdumbbell 429147476Sdumbbell/* What entry points to */ 430147476Sdumbbellstatic inline void 431147476Sdumbbellset_de_object_key(struct reiserfs_dir_entry *de) 432147476Sdumbbell{ 433147476Sdumbbell 434147476Sdumbbell if (de->de_entry_num >= ih_entry_count(de->de_ih)) { 435147476Sdumbbell reiserfs_log(LOG_DEBUG, "BUG\n"); 436147476Sdumbbell return; 437147476Sdumbbell } 438147476Sdumbbell de->de_dir_id = deh_dir_id(&(de->de_deh[de->de_entry_num])); 439147476Sdumbbell de->de_objectid = deh_objectid(&(de->de_deh[de->de_entry_num])); 440147476Sdumbbell} 441147476Sdumbbell 442147476Sdumbbellstatic inline void 443147476Sdumbbellstore_de_entry_key(struct reiserfs_dir_entry *de) 444147476Sdumbbell{ 445147476Sdumbbell struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num; 446147476Sdumbbell 447147476Sdumbbell if (de->de_entry_num >= ih_entry_count(de->de_ih)) { 448147476Sdumbbell reiserfs_log(LOG_DEBUG, "BUG\n"); 449147476Sdumbbell return; 450147476Sdumbbell } 451147476Sdumbbell 452147476Sdumbbell /* Store key of the found entry */ 453147476Sdumbbell de->de_entry_key.version = KEY_FORMAT_3_5; 454147476Sdumbbell de->de_entry_key.on_disk_key.k_dir_id = 455147476Sdumbbell le32toh(de->de_ih->ih_key.k_dir_id); 456147476Sdumbbell de->de_entry_key.on_disk_key.k_objectid = 457147476Sdumbbell le32toh(de->de_ih->ih_key.k_objectid); 458147476Sdumbbell set_cpu_key_k_offset(&(de->de_entry_key), deh_offset(deh)); 459147476Sdumbbell set_cpu_key_k_type(&(de->de_entry_key), TYPE_DIRENTRY); 460147476Sdumbbell} 461147476Sdumbbell 462147476Sdumbbell/* 463147476Sdumbbell * We assign a key to each directory item, and place multiple entries in 464147476Sdumbbell * a single directory item. A directory item has a key equal to the key 465147476Sdumbbell * of the first directory entry in it. 466147476Sdumbbell * 467147476Sdumbbell * This function first calls search_by_key, then, if item whose first 468147476Sdumbbell * entry matches is not found it looks for the entry inside directory 469147476Sdumbbell * item found by search_by_key. Fills the path to the entry, and to the 470147476Sdumbbell * entry position in the item 471147476Sdumbbell */ 472147476Sdumbbellint 473147476Sdumbbellsearch_by_entry_key(struct reiserfs_sb_info *sbi, 474147476Sdumbbell const struct cpu_key *key, struct path *path, 475147476Sdumbbell struct reiserfs_dir_entry *de) 476147476Sdumbbell{ 477147476Sdumbbell int retval; 478147476Sdumbbell 479147476Sdumbbell reiserfs_log(LOG_DEBUG, "searching in (objectid=%d,dirid=%d)\n", 480147476Sdumbbell key->on_disk_key.k_objectid, key->on_disk_key.k_dir_id); 481147476Sdumbbell retval = search_item(sbi, key, path); 482147476Sdumbbell switch (retval) { 483147476Sdumbbell case ITEM_NOT_FOUND: 484147476Sdumbbell if (!PATH_LAST_POSITION(path)) { 485147476Sdumbbell reiserfs_log(LOG_DEBUG, 486147476Sdumbbell "search_by_key returned item position == 0"); 487147476Sdumbbell pathrelse(path); 488147476Sdumbbell return (IO_ERROR); 489147476Sdumbbell } 490147476Sdumbbell PATH_LAST_POSITION(path)--; 491147476Sdumbbell reiserfs_log(LOG_DEBUG, "search_by_key did not found it\n"); 492147476Sdumbbell break; 493147476Sdumbbell case ITEM_FOUND: 494147476Sdumbbell reiserfs_log(LOG_DEBUG, "search_by_key found it\n"); 495147476Sdumbbell break; 496147476Sdumbbell case IO_ERROR: 497147476Sdumbbell return (retval); 498147476Sdumbbell default: 499147476Sdumbbell pathrelse(path); 500147476Sdumbbell reiserfs_log(LOG_DEBUG, "no path to here"); 501147476Sdumbbell return (IO_ERROR); 502147476Sdumbbell } 503147476Sdumbbell 504147476Sdumbbell reiserfs_log(LOG_DEBUG, "set item location\n"); 505147476Sdumbbell set_de_item_location(de, path); 506147476Sdumbbell 507147476Sdumbbell /* 508147476Sdumbbell * Binary search in directory item by third component of the 509147476Sdumbbell * key. Sets de->de_entry_num of de 510147476Sdumbbell */ 511147476Sdumbbell reiserfs_log(LOG_DEBUG, "bin_search_in_dir_item\n"); 512147476Sdumbbell retval = bin_search_in_dir_item(de, cpu_key_k_offset(key)); 513147476Sdumbbell path->pos_in_item = de->de_entry_num; 514147476Sdumbbell if (retval != NAME_NOT_FOUND) { 515147476Sdumbbell /* 516147476Sdumbbell * Ugly, but rename needs de_bp, de_deh, de_name, de_namelen, 517147476Sdumbbell * de_objectid set 518147476Sdumbbell */ 519147476Sdumbbell set_de_name_and_namelen(de); 520147476Sdumbbell set_de_object_key(de); 521147476Sdumbbell reiserfs_log(LOG_DEBUG, "set (objectid=%d,dirid=%d)\n", 522147476Sdumbbell de->de_objectid, de->de_dir_id); 523147476Sdumbbell } 524147476Sdumbbell 525147476Sdumbbell return (retval); 526147476Sdumbbell} 527147476Sdumbbell 528147476Sdumbbellstatic uint32_t 529147476Sdumbbellget_third_component(struct reiserfs_sb_info *sbi, const char *name, int len) 530147476Sdumbbell{ 531147476Sdumbbell uint32_t res; 532147476Sdumbbell 533147476Sdumbbell if (!len || (len == 1 && name[0] == '.')) 534147476Sdumbbell return (DOT_OFFSET); 535147476Sdumbbell 536147476Sdumbbell if (len == 2 && name[0] == '.' && name[1] == '.') 537147476Sdumbbell return (DOT_DOT_OFFSET); 538147476Sdumbbell 539147476Sdumbbell res = REISERFS_SB(sbi)->s_hash_function(name, len); 540147476Sdumbbell 541147476Sdumbbell /* Take bits from 7-th to 30-th including both bounds */ 542147476Sdumbbell res = GET_HASH_VALUE(res); 543147476Sdumbbell if (res == 0) 544147476Sdumbbell /* 545147476Sdumbbell * Needed to have no names before "." and ".." those have hash 546147476Sdumbbell * value == 0 and generation counters 1 and 2 accordingly 547147476Sdumbbell */ 548147476Sdumbbell res = 128; 549147476Sdumbbell 550147476Sdumbbell return (res + MAX_GENERATION_NUMBER); 551147476Sdumbbell} 552147476Sdumbbell 553147476Sdumbbellstatic int 554147476Sdumbbellreiserfs_match(struct reiserfs_dir_entry *de, const char *name, int namelen) 555147476Sdumbbell{ 556147476Sdumbbell int retval = NAME_NOT_FOUND; 557147476Sdumbbell 558147476Sdumbbell if ((namelen == de->de_namelen) && 559147476Sdumbbell !memcmp(de->de_name, name, de->de_namelen)) 560147476Sdumbbell retval = (de_visible(de->de_deh + de->de_entry_num) ? 561147476Sdumbbell NAME_FOUND : NAME_FOUND_INVISIBLE); 562147476Sdumbbell 563147476Sdumbbell return (retval); 564147476Sdumbbell} 565147476Sdumbbell 566147476Sdumbbell/* 567147476Sdumbbell * de's de_bh, de_ih, de_deh, de_item_num, de_entry_num are set already 568147476Sdumbbell * Used when hash collisions exist 569147476Sdumbbell */ 570147476Sdumbbellstatic int 571147476Sdumbbelllinear_search_in_dir_item(struct cpu_key *key, struct reiserfs_dir_entry *de, 572147476Sdumbbell const char *name, int namelen) 573147476Sdumbbell{ 574147476Sdumbbell int i; 575147476Sdumbbell int retval; 576147476Sdumbbell struct reiserfs_de_head * deh = de->de_deh; 577147476Sdumbbell 578147476Sdumbbell i = de->de_entry_num; 579147476Sdumbbell 580147476Sdumbbell if (i == I_ENTRY_COUNT(de->de_ih) || 581147476Sdumbbell GET_HASH_VALUE(deh_offset(deh + i)) != 582147476Sdumbbell GET_HASH_VALUE(cpu_key_k_offset(key))) { 583147476Sdumbbell i--; 584147476Sdumbbell } 585147476Sdumbbell 586147476Sdumbbell /*RFALSE( de->de_deh != B_I_DEH (de->de_bh, de->de_ih), 587147476Sdumbbell "vs-7010: array of entry headers not found");*/ 588147476Sdumbbell 589147476Sdumbbell deh += i; 590147476Sdumbbell 591147476Sdumbbell for (; i >= 0; i--, deh--) { 592147476Sdumbbell if (GET_HASH_VALUE(deh_offset(deh)) != 593147476Sdumbbell GET_HASH_VALUE(cpu_key_k_offset(key))) { 594147476Sdumbbell /* 595147476Sdumbbell * Hash value does not match, no need to check 596147476Sdumbbell * whole name 597147476Sdumbbell */ 598147476Sdumbbell reiserfs_log(LOG_DEBUG, "name `%s' not found\n", name); 599147476Sdumbbell return (NAME_NOT_FOUND); 600147476Sdumbbell } 601147476Sdumbbell 602147476Sdumbbell /* Mark that this generation number is used */ 603147476Sdumbbell if (de->de_gen_number_bit_string) 604147476Sdumbbell set_bit(GET_GENERATION_NUMBER(deh_offset(deh)), 605147476Sdumbbell (unsigned long *)de->de_gen_number_bit_string); 606147476Sdumbbell 607147476Sdumbbell /* Calculate pointer to name and namelen */ 608147476Sdumbbell de->de_entry_num = i; 609147476Sdumbbell set_de_name_and_namelen(de); 610147476Sdumbbell 611147476Sdumbbell if ((retval = reiserfs_match(de, name, namelen)) != 612147476Sdumbbell NAME_NOT_FOUND) { 613147476Sdumbbell /* 614147476Sdumbbell * de's de_name, de_namelen, de_recordlen are set. 615147476Sdumbbell * Fill the rest: 616147476Sdumbbell */ 617147476Sdumbbell /* key of pointed object */ 618147476Sdumbbell set_de_object_key(de); 619147476Sdumbbell store_de_entry_key(de); 620147476Sdumbbell 621147476Sdumbbell /* retval can be NAME_FOUND or NAME_FOUND_INVISIBLE */ 622147476Sdumbbell reiserfs_log(LOG_DEBUG, 623147476Sdumbbell "reiserfs_match answered `%d'\n", 624147476Sdumbbell retval); 625147476Sdumbbell return (retval); 626147476Sdumbbell } 627147476Sdumbbell } 628147476Sdumbbell 629147476Sdumbbell if (GET_GENERATION_NUMBER(le_ih_k_offset(de->de_ih)) == 0) 630147476Sdumbbell /* 631147476Sdumbbell * We have reached left most entry in the node. In common 632147476Sdumbbell * we have to go to the left neighbor, but if generation 633147476Sdumbbell * counter is 0 already, we know for sure, that there is 634147476Sdumbbell * no name with the same hash value 635147476Sdumbbell */ 636147476Sdumbbell /* FIXME: this work correctly only because hash value can 637147476Sdumbbell * not be 0. Btw, in case of Yura's hash it is probably 638147476Sdumbbell * possible, so, this is a bug 639147476Sdumbbell */ 640147476Sdumbbell return (NAME_NOT_FOUND); 641147476Sdumbbell 642147476Sdumbbell /*RFALSE(de->de_item_num, 643147476Sdumbbell "vs-7015: two diritems of the same directory in one node?");*/ 644147476Sdumbbell 645147476Sdumbbell return (GOTO_PREVIOUS_ITEM); 646147476Sdumbbell} 647147476Sdumbbell 648147476Sdumbbell/* 649147476Sdumbbell * May return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND 650147476Sdumbbell * FIXME: should add something like IOERROR 651147476Sdumbbell */ 652147476Sdumbbellstatic int 653147476Sdumbbellreiserfs_find_entry(struct reiserfs_node *dp, const char *name, int namelen, 654147476Sdumbbell struct path * path_to_entry, struct reiserfs_dir_entry *de) 655147476Sdumbbell{ 656147476Sdumbbell struct cpu_key key_to_search; 657147476Sdumbbell int retval; 658147476Sdumbbell 659147476Sdumbbell if (namelen > REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize)) 660147476Sdumbbell return NAME_NOT_FOUND; 661147476Sdumbbell 662147476Sdumbbell /* We will search for this key in the tree */ 663147476Sdumbbell make_cpu_key(&key_to_search, dp, 664147476Sdumbbell get_third_component(dp->i_reiserfs, name, namelen), 665147476Sdumbbell TYPE_DIRENTRY, 3); 666147476Sdumbbell 667147476Sdumbbell while (1) { 668147476Sdumbbell reiserfs_log(LOG_DEBUG, "search by entry key\n"); 669147476Sdumbbell retval = search_by_entry_key(dp->i_reiserfs, &key_to_search, 670147476Sdumbbell path_to_entry, de); 671147476Sdumbbell if (retval == IO_ERROR) { 672147476Sdumbbell reiserfs_log(LOG_DEBUG, "IO error in %s\n", 673147476Sdumbbell __FUNCTION__); 674147476Sdumbbell return IO_ERROR; 675147476Sdumbbell } 676147476Sdumbbell 677147476Sdumbbell /* Compare names for all entries having given hash value */ 678147476Sdumbbell reiserfs_log(LOG_DEBUG, "linear search for `%s'\n", name); 679147476Sdumbbell retval = linear_search_in_dir_item(&key_to_search, de, 680147476Sdumbbell name, namelen); 681147476Sdumbbell if (retval != GOTO_PREVIOUS_ITEM) { 682147476Sdumbbell /* 683147476Sdumbbell * There is no need to scan directory anymore. 684147476Sdumbbell * Given entry found or does not exist 685147476Sdumbbell */ 686147476Sdumbbell reiserfs_log(LOG_DEBUG, "linear search returned " 687147476Sdumbbell "(objectid=%d,dirid=%d)\n", 688147476Sdumbbell de->de_objectid, de->de_dir_id); 689147476Sdumbbell path_to_entry->pos_in_item = de->de_entry_num; 690147476Sdumbbell return retval; 691147476Sdumbbell } 692147476Sdumbbell 693147476Sdumbbell /* 694147476Sdumbbell * There is left neighboring item of this directory and 695147476Sdumbbell * given entry can be there 696147476Sdumbbell */ 697147476Sdumbbell set_cpu_key_k_offset(&key_to_search, 698147476Sdumbbell le_ih_k_offset(de->de_ih) - 1); 699147476Sdumbbell pathrelse(path_to_entry); 700147476Sdumbbell } /* while (1) */ 701147476Sdumbbell} 702