Index: head/sys/gnu/fs/reiserfs/reiserfs_namei.c =================================================================== --- head/sys/gnu/fs/reiserfs/reiserfs_namei.c (revision 170490) +++ head/sys/gnu/fs/reiserfs/reiserfs_namei.c (revision 170491) @@ -1,701 +1,701 @@ /*- * Copyright 2000 Hans Reiser * See README for licensing and copyright details * * Ported to FreeBSD by Jean-Sébastien Pédron * * $FreeBSD$ */ #include static int reiserfs_find_entry(struct reiserfs_node *dp, const char *name, int namelen, struct path * path_to_entry, struct reiserfs_dir_entry *de); MALLOC_DEFINE(M_REISERFSCOOKIES, "reiserfs_cookies", "ReiserFS VOP_READDIR cookies"); /* ------------------------------------------------------------------- * Lookup functions * -------------------------------------------------------------------*/ int reiserfs_lookup(struct vop_cachedlookup_args *ap) { int error, retval; struct vnode *vdp = ap->a_dvp; struct vnode **vpp = ap->a_vpp; struct componentname *cnp = ap->a_cnp; int flags = cnp->cn_flags; struct thread *td = cnp->cn_thread; struct cpu_key *saved_ino; struct vnode *vp; struct vnode *pdp; /* Saved dp during symlink work */ struct reiserfs_node *dp; struct reiserfs_dir_entry de; INITIALIZE_PATH(path_to_entry); char c = cnp->cn_nameptr[cnp->cn_namelen]; cnp->cn_nameptr[cnp->cn_namelen] = '\0'; reiserfs_log(LOG_DEBUG, "looking for `%s', %ld (%s)\n", cnp->cn_nameptr, cnp->cn_namelen, cnp->cn_pnbuf); cnp->cn_nameptr[cnp->cn_namelen] = c; vp = NULL; dp = VTOI(vdp); if (REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize) < cnp->cn_namelen) return (ENAMETOOLONG); reiserfs_log(LOG_DEBUG, "searching entry\n"); de.de_gen_number_bit_string = 0; retval = reiserfs_find_entry(dp, cnp->cn_nameptr, cnp->cn_namelen, &path_to_entry, &de); pathrelse(&path_to_entry); if (retval == NAME_FOUND) { reiserfs_log(LOG_DEBUG, "found\n"); } else { reiserfs_log(LOG_DEBUG, "not found\n"); } if (retval == NAME_FOUND) { #if 0 /* Hide the .reiserfs_priv directory */ if (reiserfs_xattrs(dp->i_reiserfs) && !old_format_only(dp->i_reiserfs) && REISERFS_SB(dp->i_reiserfs)->priv_root && REISERFS_SB(dp->i_reiserfs)->priv_root->d_inode && de.de_objectid == le32toh(INODE_PKEY(REISERFS_SB( dp->i_reiserfs)->priv_root->d_inode)->k_objectid)) { return (EACCES); } #endif reiserfs_log(LOG_DEBUG, "reading vnode\n"); pdp = vdp; if (flags & ISDOTDOT) { saved_ino = (struct cpu_key *)&(de.de_dir_id); VOP_UNLOCK(pdp, 0, td); error = reiserfs_iget(vdp->v_mount, saved_ino, &vp, td); vn_lock(pdp, LK_EXCLUSIVE | LK_RETRY, td); if (error != 0) return (error); *vpp = vp; } else if (de.de_objectid == dp->i_number && de.de_dir_id == dp->i_ino) { VREF(vdp); /* We want ourself, ie "." */ *vpp = vdp; } else { if ((error = reiserfs_iget(vdp->v_mount, (struct cpu_key *)&(de.de_dir_id), &vp, td)) != 0) return (error); *vpp = vp; } /* * Propogate the priv_object flag so we know we're in the * priv tree */ /*if (is_reiserfs_priv_object(dir)) REISERFS_I(inode)->i_flags |= i_priv_object;*/ } else { if (retval == IO_ERROR) { reiserfs_log(LOG_DEBUG, "IO error\n"); return (EIO); } return (ENOENT); } /* Insert name into cache if appropriate. */ if (cnp->cn_flags & MAKEENTRY) cache_enter(vdp, *vpp, cnp); reiserfs_log(LOG_DEBUG, "done\n"); return (0); } extern struct key MIN_KEY; int reiserfs_readdir(struct vop_readdir_args /* { struct vnode *a_vp; struct uio *a_uio; struct ucred *a_cred; int *a_eofflag; int *a_ncookies; u_long **a_cookies; } */*ap) { int error = 0; struct dirent dstdp; struct uio *uio = ap->a_uio; off_t next_pos; struct buf *bp; struct item_head *ih; struct cpu_key pos_key; const struct key *rkey; struct reiserfs_node *ip; struct reiserfs_dir_entry de; INITIALIZE_PATH(path_to_entry); int entry_num, item_num, search_res; /* The NFS part */ int ncookies = 0; u_long *cookies = NULL; /* * Form key for search the next directory entry using f_pos field of * file structure */ ip = VTOI(ap->a_vp); make_cpu_key(&pos_key, ip, uio->uio_offset ? uio->uio_offset : DOT_OFFSET, TYPE_DIRENTRY, 3); next_pos = cpu_key_k_offset(&pos_key); reiserfs_log(LOG_DEBUG, "listing entries for " "(objectid=%d, dirid=%d)\n", pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id); reiserfs_log(LOG_DEBUG, "uio_offset = %jd, uio_resid = %d\n", (intmax_t)uio->uio_offset, uio->uio_resid); if (ap->a_ncookies && ap->a_cookies) { cookies = (u_long *)malloc( uio->uio_resid / 16 * sizeof(u_long), M_REISERFSCOOKIES, M_WAITOK); } while (1) { //research: /* * Search the directory item, containing entry with * specified key */ reiserfs_log(LOG_DEBUG, "search directory to read\n"); search_res = search_by_entry_key(ip->i_reiserfs, &pos_key, &path_to_entry, &de); if (search_res == IO_ERROR) { error = EIO; goto out; } entry_num = de.de_entry_num; item_num = de.de_item_num; bp = de.de_bp; ih = de.de_ih; if (search_res == POSITION_FOUND || entry_num < I_ENTRY_COUNT(ih)) { /* * Go through all entries in the directory item * beginning from the entry, that has been found. */ struct reiserfs_de_head *deh = B_I_DEH(bp, ih) + entry_num; if (ap->a_ncookies == NULL) { cookies = NULL; } else { //ncookies = } reiserfs_log(LOG_DEBUG, "walking through directory entries\n"); for (; entry_num < I_ENTRY_COUNT(ih); entry_num++, deh++) { int d_namlen; char *d_name; off_t d_off; ino_t d_ino; if (!de_visible(deh)) { /* It is hidden entry */ continue; } d_namlen = entry_length(bp, ih, entry_num); d_name = B_I_DEH_ENTRY_FILE_NAME(bp, ih, deh); if (!d_name[d_namlen - 1]) d_namlen = strlen(d_name); reiserfs_log(LOG_DEBUG, " - `%s' (len=%d)\n", d_name, d_namlen); if (d_namlen > REISERFS_MAX_NAME( ip->i_reiserfs->s_blocksize)) { /* Too big to send back to VFS */ continue; } #if 0 /* Ignore the .reiserfs_priv entry */ if (reiserfs_xattrs(ip->i_reiserfs) && !old_format_only(ip->i_reiserfs) && filp->f_dentry == ip->i_reiserfs->s_root && REISERFS_SB(ip->i_reiserfs)->priv_root && REISERFS_SB(ip->i_reiserfs)->priv_root->d_inode && deh_objectid(deh) == le32toh(INODE_PKEY(REISERFS_SB( ip->i_reiserfs)->priv_root->d_inode)->k_objectid)) { continue; } #endif d_off = deh_offset(deh); d_ino = deh_objectid(deh); uio->uio_offset = d_off; /* Copy to user land */ dstdp.d_fileno = d_ino; dstdp.d_type = DT_UNKNOWN; dstdp.d_namlen = d_namlen; dstdp.d_reclen = GENERIC_DIRSIZ(&dstdp); bcopy(d_name, dstdp.d_name, dstdp.d_namlen); bzero(dstdp.d_name + dstdp.d_namlen, dstdp.d_reclen - offsetof(struct dirent, d_name) - dstdp.d_namlen); if (d_namlen > 0) { if (dstdp.d_reclen <= uio->uio_resid) { reiserfs_log(LOG_DEBUG, " copying to user land\n"); error = uiomove(&dstdp, dstdp.d_reclen, uio); if (error) goto end; if (cookies != NULL) { cookies[ncookies] = d_off; ncookies++; } } else break; } else { error = EIO; break; } next_pos = deh_offset(deh) + 1; } reiserfs_log(LOG_DEBUG, "...done\n"); } reiserfs_log(LOG_DEBUG, "checking item num (%d == %d ?)\n", item_num, B_NR_ITEMS(bp) - 1); if (item_num != B_NR_ITEMS(bp) - 1) { /* End of directory has been reached */ reiserfs_log(LOG_DEBUG, "end reached\n"); if (ap->a_eofflag) *ap->a_eofflag = 1; goto end; } /* * Item we went through is last item of node. Using right * delimiting key check is it directory end */ reiserfs_log(LOG_DEBUG, "get right key\n"); rkey = get_rkey(&path_to_entry, ip->i_reiserfs); reiserfs_log(LOG_DEBUG, "right key = (objectid=%d, dirid=%d)\n", rkey->k_objectid, rkey->k_dir_id); reiserfs_log(LOG_DEBUG, "compare it to MIN_KEY\n"); reiserfs_log(LOG_DEBUG, "MIN KEY = (objectid=%d, dirid=%d)\n", MIN_KEY.k_objectid, MIN_KEY.k_dir_id); if (comp_le_keys(rkey, &MIN_KEY) == 0) { /* Set pos_key to key, that is the smallest and greater * that key of the last entry in the item */ reiserfs_log(LOG_DEBUG, "continuing on the right\n"); set_cpu_key_k_offset(&pos_key, next_pos); continue; } reiserfs_log(LOG_DEBUG, "compare it to pos_key\n"); reiserfs_log(LOG_DEBUG, "pos key = (objectid=%d, dirid=%d)\n", pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id); if (COMP_SHORT_KEYS(rkey, &pos_key)) { /* End of directory has been reached */ reiserfs_log(LOG_DEBUG, "end reached (right)\n"); if (ap->a_eofflag) *ap->a_eofflag = 1; goto end; } /* Directory continues in the right neighboring block */ reiserfs_log(LOG_DEBUG, "continuing with a new offset\n"); set_cpu_key_k_offset(&pos_key, le_key_k_offset(KEY_FORMAT_3_5, rkey)); reiserfs_log(LOG_DEBUG, "new pos key = (objectid=%d, dirid=%d)\n", pos_key.on_disk_key.k_objectid, pos_key.on_disk_key.k_dir_id); } end: uio->uio_offset = next_pos; pathrelse(&path_to_entry); reiserfs_check_path(&path_to_entry); out: if (error && cookies != NULL) { free(cookies, M_REISERFSCOOKIES); } else if (ap->a_ncookies != NULL && ap->a_cookies != NULL) { *ap->a_ncookies = ncookies; *ap->a_cookies = cookies; } return (error); } /* ------------------------------------------------------------------- * Functions from linux/fs/reiserfs/namei.c * -------------------------------------------------------------------*/ /* * Directory item contains array of entry headers. This performs binary * search through that array. */ static int bin_search_in_dir_item(struct reiserfs_dir_entry *de, off_t off) { struct item_head *ih = de->de_ih; struct reiserfs_de_head *deh = de->de_deh; int rbound, lbound, j; lbound = 0; rbound = I_ENTRY_COUNT(ih) - 1; for (j = (rbound + lbound) / 2; lbound <= rbound; j = (rbound + lbound) / 2) { if (off < deh_offset(deh + j)) { rbound = j - 1; continue; } if (off > deh_offset(deh + j)) { lbound = j + 1; continue; } /* This is not name found, but matched third key component */ de->de_entry_num = j; return (NAME_FOUND); } de->de_entry_num = lbound; return (NAME_NOT_FOUND); } /* * Comment? Maybe something like set de to point to what the path * points to? */ static inline void set_de_item_location(struct reiserfs_dir_entry *de, struct path *path) { de->de_bp = get_last_bp(path); de->de_ih = get_ih(path); de->de_deh = B_I_DEH(de->de_bp, de->de_ih); de->de_item_num = PATH_LAST_POSITION(path); } /* * de_bh, de_ih, de_deh (points to first element of array), de_item_num * is set */ -inline void +void set_de_name_and_namelen(struct reiserfs_dir_entry *de) { struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num; if (de->de_entry_num >= ih_entry_count(de->de_ih)) { reiserfs_log(LOG_DEBUG, "BUG\n"); return; } de->de_entrylen = entry_length(de->de_bp, de->de_ih, de->de_entry_num); de->de_namelen = de->de_entrylen - (de_with_sd(deh) ? SD_SIZE : 0); de->de_name = B_I_PITEM(de->de_bp, de->de_ih) + deh_location(deh); if (de->de_name[de->de_namelen - 1] == 0) de->de_namelen = strlen(de->de_name); } /* What entry points to */ static inline void set_de_object_key(struct reiserfs_dir_entry *de) { if (de->de_entry_num >= ih_entry_count(de->de_ih)) { reiserfs_log(LOG_DEBUG, "BUG\n"); return; } de->de_dir_id = deh_dir_id(&(de->de_deh[de->de_entry_num])); de->de_objectid = deh_objectid(&(de->de_deh[de->de_entry_num])); } static inline void store_de_entry_key(struct reiserfs_dir_entry *de) { struct reiserfs_de_head *deh = de->de_deh + de->de_entry_num; if (de->de_entry_num >= ih_entry_count(de->de_ih)) { reiserfs_log(LOG_DEBUG, "BUG\n"); return; } /* Store key of the found entry */ de->de_entry_key.version = KEY_FORMAT_3_5; de->de_entry_key.on_disk_key.k_dir_id = le32toh(de->de_ih->ih_key.k_dir_id); de->de_entry_key.on_disk_key.k_objectid = le32toh(de->de_ih->ih_key.k_objectid); set_cpu_key_k_offset(&(de->de_entry_key), deh_offset(deh)); set_cpu_key_k_type(&(de->de_entry_key), TYPE_DIRENTRY); } /* * We assign a key to each directory item, and place multiple entries in * a single directory item. A directory item has a key equal to the key * of the first directory entry in it. * * This function first calls search_by_key, then, if item whose first * entry matches is not found it looks for the entry inside directory * item found by search_by_key. Fills the path to the entry, and to the * entry position in the item */ int search_by_entry_key(struct reiserfs_sb_info *sbi, const struct cpu_key *key, struct path *path, struct reiserfs_dir_entry *de) { int retval; reiserfs_log(LOG_DEBUG, "searching in (objectid=%d,dirid=%d)\n", key->on_disk_key.k_objectid, key->on_disk_key.k_dir_id); retval = search_item(sbi, key, path); switch (retval) { case ITEM_NOT_FOUND: if (!PATH_LAST_POSITION(path)) { reiserfs_log(LOG_DEBUG, "search_by_key returned item position == 0"); pathrelse(path); return (IO_ERROR); } PATH_LAST_POSITION(path)--; reiserfs_log(LOG_DEBUG, "search_by_key did not found it\n"); break; case ITEM_FOUND: reiserfs_log(LOG_DEBUG, "search_by_key found it\n"); break; case IO_ERROR: return (retval); default: pathrelse(path); reiserfs_log(LOG_DEBUG, "no path to here"); return (IO_ERROR); } reiserfs_log(LOG_DEBUG, "set item location\n"); set_de_item_location(de, path); /* * Binary search in directory item by third component of the * key. Sets de->de_entry_num of de */ reiserfs_log(LOG_DEBUG, "bin_search_in_dir_item\n"); retval = bin_search_in_dir_item(de, cpu_key_k_offset(key)); path->pos_in_item = de->de_entry_num; if (retval != NAME_NOT_FOUND) { /* * Ugly, but rename needs de_bp, de_deh, de_name, de_namelen, * de_objectid set */ set_de_name_and_namelen(de); set_de_object_key(de); reiserfs_log(LOG_DEBUG, "set (objectid=%d,dirid=%d)\n", de->de_objectid, de->de_dir_id); } return (retval); } static uint32_t get_third_component(struct reiserfs_sb_info *sbi, const char *name, int len) { uint32_t res; if (!len || (len == 1 && name[0] == '.')) return (DOT_OFFSET); if (len == 2 && name[0] == '.' && name[1] == '.') return (DOT_DOT_OFFSET); res = REISERFS_SB(sbi)->s_hash_function(name, len); /* Take bits from 7-th to 30-th including both bounds */ res = GET_HASH_VALUE(res); if (res == 0) /* * Needed to have no names before "." and ".." those have hash * value == 0 and generation counters 1 and 2 accordingly */ res = 128; return (res + MAX_GENERATION_NUMBER); } static int reiserfs_match(struct reiserfs_dir_entry *de, const char *name, int namelen) { int retval = NAME_NOT_FOUND; if ((namelen == de->de_namelen) && !memcmp(de->de_name, name, de->de_namelen)) retval = (de_visible(de->de_deh + de->de_entry_num) ? NAME_FOUND : NAME_FOUND_INVISIBLE); return (retval); } /* * de's de_bh, de_ih, de_deh, de_item_num, de_entry_num are set already * Used when hash collisions exist */ static int linear_search_in_dir_item(struct cpu_key *key, struct reiserfs_dir_entry *de, const char *name, int namelen) { int i; int retval; struct reiserfs_de_head * deh = de->de_deh; i = de->de_entry_num; if (i == I_ENTRY_COUNT(de->de_ih) || GET_HASH_VALUE(deh_offset(deh + i)) != GET_HASH_VALUE(cpu_key_k_offset(key))) { i--; } /*RFALSE( de->de_deh != B_I_DEH (de->de_bh, de->de_ih), "vs-7010: array of entry headers not found");*/ deh += i; for (; i >= 0; i--, deh--) { if (GET_HASH_VALUE(deh_offset(deh)) != GET_HASH_VALUE(cpu_key_k_offset(key))) { /* * Hash value does not match, no need to check * whole name */ reiserfs_log(LOG_DEBUG, "name `%s' not found\n", name); return (NAME_NOT_FOUND); } /* Mark that this generation number is used */ if (de->de_gen_number_bit_string) set_bit(GET_GENERATION_NUMBER(deh_offset(deh)), (unsigned long *)de->de_gen_number_bit_string); /* Calculate pointer to name and namelen */ de->de_entry_num = i; set_de_name_and_namelen(de); if ((retval = reiserfs_match(de, name, namelen)) != NAME_NOT_FOUND) { /* * de's de_name, de_namelen, de_recordlen are set. * Fill the rest: */ /* key of pointed object */ set_de_object_key(de); store_de_entry_key(de); /* retval can be NAME_FOUND or NAME_FOUND_INVISIBLE */ reiserfs_log(LOG_DEBUG, "reiserfs_match answered `%d'\n", retval); return (retval); } } if (GET_GENERATION_NUMBER(le_ih_k_offset(de->de_ih)) == 0) /* * We have reached left most entry in the node. In common * we have to go to the left neighbor, but if generation * counter is 0 already, we know for sure, that there is * no name with the same hash value */ /* FIXME: this work correctly only because hash value can * not be 0. Btw, in case of Yura's hash it is probably * possible, so, this is a bug */ return (NAME_NOT_FOUND); /*RFALSE(de->de_item_num, "vs-7015: two diritems of the same directory in one node?");*/ return (GOTO_PREVIOUS_ITEM); } /* * May return NAME_FOUND, NAME_FOUND_INVISIBLE, NAME_NOT_FOUND * FIXME: should add something like IOERROR */ static int reiserfs_find_entry(struct reiserfs_node *dp, const char *name, int namelen, struct path * path_to_entry, struct reiserfs_dir_entry *de) { struct cpu_key key_to_search; int retval; if (namelen > REISERFS_MAX_NAME(dp->i_reiserfs->s_blocksize)) return NAME_NOT_FOUND; /* We will search for this key in the tree */ make_cpu_key(&key_to_search, dp, get_third_component(dp->i_reiserfs, name, namelen), TYPE_DIRENTRY, 3); while (1) { reiserfs_log(LOG_DEBUG, "search by entry key\n"); retval = search_by_entry_key(dp->i_reiserfs, &key_to_search, path_to_entry, de); if (retval == IO_ERROR) { reiserfs_log(LOG_DEBUG, "IO error in %s\n", __FUNCTION__); return IO_ERROR; } /* Compare names for all entries having given hash value */ reiserfs_log(LOG_DEBUG, "linear search for `%s'\n", name); retval = linear_search_in_dir_item(&key_to_search, de, name, namelen); if (retval != GOTO_PREVIOUS_ITEM) { /* * There is no need to scan directory anymore. * Given entry found or does not exist */ reiserfs_log(LOG_DEBUG, "linear search returned " "(objectid=%d,dirid=%d)\n", de->de_objectid, de->de_dir_id); path_to_entry->pos_in_item = de->de_entry_num; return retval; } /* * There is left neighboring item of this directory and * given entry can be there */ set_cpu_key_k_offset(&key_to_search, le_ih_k_offset(de->de_ih) - 1); pathrelse(path_to_entry); } /* while (1) */ } Index: head/sys/gnu/fs/reiserfs/reiserfs_stree.c =================================================================== --- head/sys/gnu/fs/reiserfs/reiserfs_stree.c (revision 170490) +++ head/sys/gnu/fs/reiserfs/reiserfs_stree.c (revision 170491) @@ -1,760 +1,760 @@ /*- * Copyright 2000 Hans Reiser * See README for licensing and copyright details * * Ported to FreeBSD by Jean-Sébastien Pédron * * $FreeBSD$ */ #include /* Minimal possible key. It is never in the tree. */ const struct key MIN_KEY = { 0, 0, { {0, 0}, } }; /* Maximal possible key. It is never in the tree. */ const struct key MAX_KEY = { 0xffffffff, 0xffffffff, { {0xffffffff, 0xffffffff }, } }; /* Does the buffer contain a disk block which is in the tree. */ -inline int +int B_IS_IN_TREE(const struct buf *p_s_bp) { return (B_LEVEL(p_s_bp) != FREE_LEVEL); } /* To gets item head in le form */ -inline void +void copy_item_head(struct item_head *p_v_to, const struct item_head *p_v_from) { memcpy(p_v_to, p_v_from, IH_SIZE); } /* * k1 is pointer to on-disk structure which is stored in little-endian * form. k2 is pointer to cpu variable. For key of items of the same * object this returns 0. * Returns: -1 if key1 < key2, 0 if key1 == key2 or 1 if key1 > key2 */ /*inline*/ int comp_short_keys(const struct key *le_key, const struct cpu_key *cpu_key) { const uint32_t *p_s_le_u32, *p_s_cpu_u32; int n_key_length = REISERFS_SHORT_KEY_LEN; p_s_le_u32 = (const uint32_t *)le_key; p_s_cpu_u32 = (const uint32_t *)&cpu_key->on_disk_key; for(; n_key_length--; ++p_s_le_u32, ++p_s_cpu_u32) { if (le32toh(*p_s_le_u32) < *p_s_cpu_u32) return (-1); if (le32toh(*p_s_le_u32) > *p_s_cpu_u32) return (1); } return (0); } /* * k1 is pointer to on-disk structure which is stored in little-endian * form. k2 is pointer to cpu variable. Compare keys using all 4 key * fields. * Returns: -1 if key1 < key2, 0 if key1 = key2 or 1 if key1 > key2 */ /*inline*/ int comp_keys(const struct key *le_key, const struct cpu_key *cpu_key) { int retval; retval = comp_short_keys(le_key, cpu_key); if (retval) return retval; if (le_key_k_offset(le_key_version(le_key), le_key) < cpu_key_k_offset(cpu_key)) return (-1); if (le_key_k_offset(le_key_version(le_key), le_key) > cpu_key_k_offset(cpu_key)) return (1); if (cpu_key->key_length == 3) return (0); /* This part is needed only when tail conversion is in progress */ if (le_key_k_type(le_key_version(le_key), le_key) < cpu_key_k_type(cpu_key)) return (-1); if (le_key_k_type(le_key_version(le_key), le_key) > cpu_key_k_type(cpu_key)) return (1); return (0); } /* Release all buffers in the path. */ void pathrelse(struct path *p_s_search_path) { struct buf *bp; int n_path_offset = p_s_search_path->path_length; while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { bp = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--); free(bp->b_data, M_REISERFSPATH); free(bp, M_REISERFSPATH); } p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; } /* * This does not say which one is bigger, it only returns 1 if keys * are not equal, 0 otherwise */ -inline int +int comp_le_keys(const struct key *k1, const struct key *k2) { return (memcmp(k1, k2, sizeof(struct key))); } /* * Binary search toolkit function. Search for an item in the array by * the item key. * Returns: 1 if found, 0 if not found; * *p_n_pos = number of the searched element if found, else the * number of the first element that is larger than p_v_key. */ /* * For those not familiar with binary search: n_lbound is the leftmost * item that it could be, n_rbound the rightmost item that it could be. * We examine the item halfway between n_lbound and n_rbound, and that * tells us either that we can increase n_lbound, or decrease n_rbound, * or that we have found it, or if n_lbound <= n_rbound that there are * no possible items, and we have not found it. With each examination we * cut the number of possible items it could be by one more than half * rounded down, or we find it. */ -inline int +int bin_search(const void *p_v_key, /* Key to search for. */ const void *p_v_base, /* First item in the array. */ int p_n_num, /* Number of items in the array. */ int p_n_width, /* Item size in the array. searched. Lest the reader be confused, note that this is crafted as a general function, and when it is applied specifically to the array of item headers in a node, p_n_width is actually the item header size not the item size. */ int *p_n_pos) /* Number of the searched for element. */ { int n_rbound, n_lbound, n_j; for (n_j = ((n_rbound = p_n_num - 1) + (n_lbound = 0)) / 2; n_lbound <= n_rbound; n_j = (n_rbound + n_lbound) / 2) { switch (COMP_KEYS((const struct key *) ((const char *)p_v_base + n_j * p_n_width), (const struct cpu_key *)p_v_key)) { case -1: n_lbound = n_j + 1; continue; case 1: n_rbound = n_j - 1; continue; case 0: *p_n_pos = n_j; return (ITEM_FOUND); /* Key found in the array. */ } } /* * bin_search did not find given key, it returns position of key, * that is minimal and greater than the given one. */ *p_n_pos = n_lbound; return (ITEM_NOT_FOUND); } /* * Get delimiting key of the buffer by looking for it in the buffers in * the path, starting from the bottom of the path, and going upwards. We * must check the path's validity at each step. If the key is not in the * path, there is no delimiting key in the tree (buffer is first or last * buffer in tree), and in this case we return a special key, either * MIN_KEY or MAX_KEY. */ -inline const struct key * +const struct key * get_lkey(const struct path *p_s_chk_path, const struct reiserfs_sb_info *p_s_sbi) { struct buf *p_s_parent; int n_position, n_path_offset = p_s_chk_path->path_length; /* While not higher in path than first element. */ while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { /* Parent at the path is not in the tree now. */ if (!B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) return (&MAX_KEY); /* Check whether position in the parent is correct. */ if ((n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent)) return (&MAX_KEY); /* * Check whether parent at the path really points to * the child. */ if (B_N_CHILD_NUM(p_s_parent, n_position) != (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blkno / btodb(p_s_sbi->s_blocksize))) return (&MAX_KEY); /* * Return delimiting key if position in the parent is not * equal to zero. */ if (n_position) return (B_N_PDELIM_KEY(p_s_parent, n_position - 1)); } /* Return MIN_KEY if we are in the root of the buffer tree. */ if ((PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blkno / btodb(p_s_sbi->s_blocksize)) == SB_ROOT_BLOCK(p_s_sbi)) return (&MIN_KEY); return (&MAX_KEY); } /* Get delimiting key of the buffer at the path and its right neighbor. */ -inline const struct key * +const struct key * get_rkey(const struct path *p_s_chk_path, const struct reiserfs_sb_info *p_s_sbi) { struct buf *p_s_parent; int n_position, n_path_offset = p_s_chk_path->path_length; while (n_path_offset-- > FIRST_PATH_ELEMENT_OFFSET) { /* Parent at the path is not in the tree now. */ if (!B_IS_IN_TREE(p_s_parent = PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset))) return (&MIN_KEY); /* Check whether position in the parent is correct. */ if ((n_position = PATH_OFFSET_POSITION(p_s_chk_path, n_path_offset)) > B_NR_ITEMS(p_s_parent)) return (&MIN_KEY); /* * Check whether parent at the path really points to the * child. */ if (B_N_CHILD_NUM(p_s_parent, n_position) != (PATH_OFFSET_PBUFFER(p_s_chk_path, n_path_offset + 1)->b_blkno / btodb(p_s_sbi->s_blocksize))) return (&MIN_KEY); /* * Return delimiting key if position in the parent is not * the last one. */ if (n_position != B_NR_ITEMS(p_s_parent)) return (B_N_PDELIM_KEY(p_s_parent, n_position)); } /* Return MAX_KEY if we are in the root of the buffer tree. */ if ((PATH_OFFSET_PBUFFER(p_s_chk_path, FIRST_PATH_ELEMENT_OFFSET)->b_blkno / btodb(p_s_sbi->s_blocksize)) == SB_ROOT_BLOCK(p_s_sbi)) return (&MAX_KEY); return (&MIN_KEY); } int reiserfs_check_path(struct path *p) { if (p->path_length != ILLEGAL_PATH_ELEMENT_OFFSET) reiserfs_log(LOG_WARNING, "path not properly relsed\n"); return (0); } /* * Check whether a key is contained in the tree rooted from a buffer at * a path. This works by looking at the left and right delimiting keys * for the buffer in the last path_element in the path. These delimiting * keys are stored at least one level above that buffer in the tree. * If the buffer is the first or last node in the tree order then one * of the delimiting keys may be absent, and in this case get_lkey and * get_rkey return a special key which is MIN_KEY or MAX_KEY. */ static inline int key_in_buffer( struct path *p_s_chk_path, /* Path which should be checked. */ const struct cpu_key *p_s_key, /* Key which should be checked. */ struct reiserfs_sb_info *p_s_sbi) /* Super block pointer. */ { if (COMP_KEYS(get_lkey(p_s_chk_path, p_s_sbi), p_s_key) == 1) /* left delimiting key is bigger, that the key we look for */ return (0); if (COMP_KEYS(get_rkey(p_s_chk_path, p_s_sbi), p_s_key) != 1) /* p_s_key must be less than right delimitiing key */ return (0); return (1); } #if 0 /* XXX Il ne semble pas y avoir de compteur de référence dans struct buf */ inline void decrement_bcount(struct buf *p_s_bp) { if (p_s_bp) { if (atomic_read(&(p_s_bp->b_count))) { put_bh(p_s_bp); return; } } } #endif /* Decrement b_count field of the all buffers in the path. */ void decrement_counters_in_path(struct path *p_s_search_path) { pathrelse(p_s_search_path); #if 0 int n_path_offset = p_s_search_path->path_length; while (n_path_offset > ILLEGAL_PATH_ELEMENT_OFFSET) { struct buf *bp; bp = PATH_OFFSET_PBUFFER(p_s_search_path, n_path_offset--); decrement_bcount(bp); } p_s_search_path->path_length = ILLEGAL_PATH_ELEMENT_OFFSET; #endif } static int is_leaf(char *buf, int blocksize, struct buf *bp) { struct item_head *ih; struct block_head *blkh; int used_space, prev_location, i, nr; blkh = (struct block_head *)buf; if (blkh_level(blkh) != DISK_LEAF_NODE_LEVEL) { reiserfs_log(LOG_WARNING, "this should be caught earlier"); return (0); } nr = blkh_nr_item(blkh); if (nr < 1 || nr > ((blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN))) { /* Item number is too big or too small */ reiserfs_log(LOG_WARNING, "nr_item seems wrong\n"); return (0); } ih = (struct item_head *)(buf + BLKH_SIZE) + nr - 1; used_space = BLKH_SIZE + IH_SIZE * nr + (blocksize - ih_location(ih)); if (used_space != blocksize - blkh_free_space(blkh)) { /* * Free space does not match to calculated amount of * use space */ reiserfs_log(LOG_WARNING, "free space seems wrong\n"); return (0); } /* FIXME: it is_leaf will hit performance too much - we may have * return 1 here */ /* Check tables of item heads */ ih = (struct item_head *)(buf + BLKH_SIZE); prev_location = blocksize; for (i = 0; i < nr; i++, ih++) { if (le_ih_k_type(ih) == TYPE_ANY) { reiserfs_log(LOG_WARNING, "wrong item type for item\n"); return (0); } if (ih_location(ih) >= blocksize || ih_location(ih) < IH_SIZE * nr) { reiserfs_log(LOG_WARNING, "item location seems wrong\n"); return (0); } if (ih_item_len(ih) < 1 || ih_item_len(ih) > MAX_ITEM_LEN(blocksize)) { reiserfs_log(LOG_WARNING, "item length seems wrong\n"); return (0); } if (prev_location - ih_location(ih) != ih_item_len(ih)) { reiserfs_log(LOG_WARNING, "item location seems wrong (second one)\n"); return (0); } prev_location = ih_location(ih); } /* One may imagine much more checks */ return 1; } /* Returns 1 if buf looks like an internal node, 0 otherwise */ static int is_internal(char *buf, int blocksize, struct buf *bp) { int nr, used_space; struct block_head *blkh; blkh = (struct block_head *)buf; nr = blkh_level(blkh); if (nr <= DISK_LEAF_NODE_LEVEL || nr > MAX_HEIGHT) { /* This level is not possible for internal nodes */ reiserfs_log(LOG_WARNING, "this should be caught earlier\n"); return (0); } nr = blkh_nr_item(blkh); if (nr > (blocksize - BLKH_SIZE - DC_SIZE) / (KEY_SIZE + DC_SIZE)) { /* * For internal which is not root we might check min * number of keys */ reiserfs_log(LOG_WARNING, "number of key seems wrong\n"); return (0); } used_space = BLKH_SIZE + KEY_SIZE * nr + DC_SIZE * (nr + 1); if (used_space != blocksize - blkh_free_space(blkh)) { reiserfs_log(LOG_WARNING, "is_internal: free space seems wrong\n"); return (0); } /* One may imagine much more checks */ return (1); } /* * Make sure that bh contains formatted node of reiserfs tree of * 'level'-th level */ static int is_tree_node(struct buf *bp, int level) { if (B_LEVEL(bp) != level) { reiserfs_log(LOG_WARNING, "node level (%d) doesn't match to the " "expected one (%d)\n", B_LEVEL (bp), level); return (0); } if (level == DISK_LEAF_NODE_LEVEL) return (is_leaf(bp->b_data, bp->b_bcount, bp)); return (is_internal(bp->b_data, bp->b_bcount, bp)); } int search_by_key(struct reiserfs_sb_info *p_s_sbi, const struct cpu_key * p_s_key, /* Key to search. */ struct path * p_s_search_path, /* This structure was allocated and initialized by the calling function. It is filled up by this function. */ int n_stop_level) /* How far down the tree to search. To stop at leaf level - set to DISK_LEAF_NODE_LEVEL */ { int error; int n_node_level, n_retval; int n_block_number, expected_level, fs_gen; struct path_element *p_s_last_element; struct buf *p_s_bp, *tmp_bp; /* * As we add each node to a path we increase its count. This means that * we must be careful to release all nodes in a path before we either * discard the path struct or re-use the path struct, as we do here. */ decrement_counters_in_path(p_s_search_path); /* * With each iteration of this loop we search through the items in the * current node, and calculate the next current node(next path element) * for the next iteration of this loop... */ n_block_number = SB_ROOT_BLOCK(p_s_sbi); expected_level = -1; reiserfs_log(LOG_DEBUG, "root block: #%d\n", n_block_number); while (1) { /* Prep path to have another element added to it. */ reiserfs_log(LOG_DEBUG, "path element #%d\n", p_s_search_path->path_length); p_s_last_element = PATH_OFFSET_PELEMENT(p_s_search_path, ++p_s_search_path->path_length); fs_gen = get_generation(p_s_sbi); /* * Read the next tree node, and set the last element in the * path to have a pointer to it. */ reiserfs_log(LOG_DEBUG, "reading block #%d\n", n_block_number); if ((error = bread(p_s_sbi->s_devvp, n_block_number * btodb(p_s_sbi->s_blocksize), p_s_sbi->s_blocksize, NOCRED, &tmp_bp)) != 0) { reiserfs_log(LOG_DEBUG, "error reading block\n"); p_s_search_path->path_length--; pathrelse(p_s_search_path); return (IO_ERROR); } reiserfs_log(LOG_DEBUG, "blkno = %ju, lblkno = %ju\n", (intmax_t)tmp_bp->b_blkno, (intmax_t)tmp_bp->b_lblkno); /* * As i didn't found a way to handle the lock correctly, * i copy the data into a fake buffer */ reiserfs_log(LOG_DEBUG, "allocating p_s_bp\n"); p_s_bp = malloc(sizeof *p_s_bp, M_REISERFSPATH, M_WAITOK); if (!p_s_bp) { reiserfs_log(LOG_DEBUG, "error allocating memory\n"); p_s_search_path->path_length--; pathrelse(p_s_search_path); brelse(tmp_bp); return (IO_ERROR); } reiserfs_log(LOG_DEBUG, "copying struct buf\n"); bcopy(tmp_bp, p_s_bp, sizeof(struct buf)); reiserfs_log(LOG_DEBUG, "allocating p_s_bp->b_data\n"); p_s_bp->b_data = malloc(p_s_sbi->s_blocksize, M_REISERFSPATH, M_WAITOK); if (!p_s_bp->b_data) { reiserfs_log(LOG_DEBUG, "error allocating memory\n"); p_s_search_path->path_length--; pathrelse(p_s_search_path); free(p_s_bp, M_REISERFSPATH); brelse(tmp_bp); return (IO_ERROR); } reiserfs_log(LOG_DEBUG, "copying buffer data\n"); bcopy(tmp_bp->b_data, p_s_bp->b_data, p_s_sbi->s_blocksize); brelse(tmp_bp); tmp_bp = NULL; reiserfs_log(LOG_DEBUG, "...done\n"); p_s_last_element->pe_buffer = p_s_bp; if (expected_level == -1) expected_level = SB_TREE_HEIGHT(p_s_sbi); expected_level--; reiserfs_log(LOG_DEBUG, "expected level: %d (%d)\n", expected_level, SB_TREE_HEIGHT(p_s_sbi)); /* XXX */ /* * It is possible that schedule occurred. We must check * whether the key to search is still in the tree rooted * from the current buffer. If not then repeat search * from the root. */ if (fs_changed(fs_gen, p_s_sbi) && (!B_IS_IN_TREE(p_s_bp) || B_LEVEL(p_s_bp) != expected_level || !key_in_buffer(p_s_search_path, p_s_key, p_s_sbi))) { reiserfs_log(LOG_DEBUG, "the key isn't in the tree anymore\n"); decrement_counters_in_path(p_s_search_path); /* * Get the root block number so that we can repeat * the search starting from the root. */ n_block_number = SB_ROOT_BLOCK(p_s_sbi); expected_level = -1; /* Repeat search from the root */ continue; } /* * Make sure, that the node contents look like a node of * certain level */ if (!is_tree_node(p_s_bp, expected_level)) { reiserfs_log(LOG_WARNING, "invalid format found in block %ju. Fsck?", (intmax_t)p_s_bp->b_blkno); pathrelse (p_s_search_path); return (IO_ERROR); } /* Ok, we have acquired next formatted node in the tree */ n_node_level = B_LEVEL(p_s_bp); reiserfs_log(LOG_DEBUG, "block info:\n"); reiserfs_log(LOG_DEBUG, " node level: %d\n", n_node_level); reiserfs_log(LOG_DEBUG, " nb of items: %d\n", B_NR_ITEMS(p_s_bp)); reiserfs_log(LOG_DEBUG, " free space: %d bytes\n", B_FREE_SPACE(p_s_bp)); reiserfs_log(LOG_DEBUG, "bin_search with :\n" " p_s_key = (objectid=%d, dirid=%d)\n" " B_NR_ITEMS(p_s_bp) = %d\n" " p_s_last_element->pe_position = %d (path_length = %d)\n", p_s_key->on_disk_key.k_objectid, p_s_key->on_disk_key.k_dir_id, B_NR_ITEMS(p_s_bp), p_s_last_element->pe_position, p_s_search_path->path_length); n_retval = bin_search(p_s_key, B_N_PITEM_HEAD(p_s_bp, 0), B_NR_ITEMS(p_s_bp), (n_node_level == DISK_LEAF_NODE_LEVEL) ? IH_SIZE : KEY_SIZE, &(p_s_last_element->pe_position)); reiserfs_log(LOG_DEBUG, "bin_search result: %d\n", n_retval); if (n_node_level == n_stop_level) { reiserfs_log(LOG_DEBUG, "stop level reached (%s)\n", n_retval == ITEM_FOUND ? "found" : "not found"); return (n_retval); } /* We are not in the stop level */ if (n_retval == ITEM_FOUND) /* * Item has been found, so we choose the pointer * which is to the right of the found one */ p_s_last_element->pe_position++; /* * If item was not found we choose the position which is * to the left of the found item. This requires no code, * bin_search did it already. */ /* * So we have chosen a position in the current node which * is an internal node. Now we calculate child block number * by position in the node. */ n_block_number = B_N_CHILD_NUM(p_s_bp, p_s_last_element->pe_position); } reiserfs_log(LOG_DEBUG, "done\n"); return (0); } /* * Form the path to an item and position in this item which contains * file byte defined by p_s_key. If there is no such item corresponding * to the key, we point the path to the item with maximal key less than * p_s_key, and *p_n_pos_in_item is set to one past the last entry/byte * in the item. If searching for entry in a directory item, and it is * not found, *p_n_pos_in_item is set to one entry more than the entry * with maximal key which is less than the sought key. * * Note that if there is no entry in this same node which is one more, * then we point to an imaginary entry. For direct items, the position * is in units of bytes, for indirect items the position is in units * of blocknr entries, for directory items the position is in units of * directory entries. */ /* The function is NOT SCHEDULE-SAFE! */ int search_for_position_by_key(struct reiserfs_sb_info *p_s_sbi, const struct cpu_key *p_cpu_key, /* Key to search (cpu variable) */ struct path *p_s_search_path) /* Filled up by this function. */ { int retval, n_blk_size; off_t item_offset, offset; struct item_head *p_le_ih; /* Pointer to on-disk structure */ struct reiserfs_dir_entry de; /* If searching for directory entry. */ if (is_direntry_cpu_key(p_cpu_key)) return (search_by_entry_key(p_s_sbi, p_cpu_key, p_s_search_path, &de)); /* If not searching for directory entry. */ /* If item is found. */ retval = search_item(p_s_sbi, p_cpu_key, p_s_search_path); if (retval == IO_ERROR) return (retval); if (retval == ITEM_FOUND) { if (ih_item_len(B_N_PITEM_HEAD( PATH_PLAST_BUFFER(p_s_search_path), PATH_LAST_POSITION(p_s_search_path))) == 0) { reiserfs_log(LOG_WARNING, "item length equals zero\n"); } pos_in_item(p_s_search_path) = 0; return (POSITION_FOUND); } if (PATH_LAST_POSITION(p_s_search_path) == 0) { reiserfs_log(LOG_WARNING, "position equals zero\n"); } /* Item is not found. Set path to the previous item. */ p_le_ih = B_N_PITEM_HEAD(PATH_PLAST_BUFFER(p_s_search_path), --PATH_LAST_POSITION(p_s_search_path)); n_blk_size = p_s_sbi->s_blocksize; if (comp_short_keys(&(p_le_ih->ih_key), p_cpu_key)) { return (FILE_NOT_FOUND); } item_offset = le_ih_k_offset(p_le_ih); offset = cpu_key_k_offset(p_cpu_key); /* Needed byte is contained in the item pointed to by the path.*/ if (item_offset <= offset && item_offset + op_bytes_number(p_le_ih, n_blk_size) > offset) { pos_in_item(p_s_search_path) = offset - item_offset; if (is_indirect_le_ih(p_le_ih)) { pos_in_item(p_s_search_path) /= n_blk_size; } return (POSITION_FOUND); } /* Needed byte is not contained in the item pointed to by the * path. Set pos_in_item out of the item. */ if (is_indirect_le_ih(p_le_ih)) pos_in_item(p_s_search_path) = ih_item_len(p_le_ih) / UNFM_P_SIZE; else pos_in_item(p_s_search_path) = ih_item_len(p_le_ih); return (POSITION_NOT_FOUND); }