1 /* $NetBSD: ext2fs_htree.c,v 1.1 2016/06/24 17:21:30 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org> 5 * Copyright (c) 2012, Vyacheslav Matyushin 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 * 29 * $FreeBSD: head/sys/fs/ext2fs/ext2_htree.c 294653 2016-01-24 02:41:49Z pfg $ 30 */ 31 #include <sys/cdefs.h> 32 __KERNEL_RCSID(0, "$NetBSD: ext2fs_htree.c,v 1.1 2016/06/24 17:21:30 christos Exp $"); 33 34 #include <sys/param.h> 35 #include <sys/systm.h> 36 #include <sys/resourcevar.h> 37 #include <sys/kernel.h> 38 #include <sys/file.h> 39 #include <sys/stat.h> 40 #include <sys/buf.h> 41 #include <sys/proc.h> 42 #include <sys/mount.h> 43 #include <sys/namei.h> 44 #include <sys/vnode.h> 45 #include <sys/lockf.h> 46 #include <sys/pool.h> 47 #include <sys/signalvar.h> 48 #include <sys/kauth.h> 49 50 #include <ufs/ufs/dir.h> 51 52 #include <ufs/ufs/inode.h> 53 #include <ufs/ufs/ufsmount.h> 54 #include <ufs/ext2fs/ext2fs.h> 55 56 #include <ufs/ext2fs/ext2fs_extern.h> 57 #include <ufs/ext2fs/ext2fs_dinode.h> 58 #include <ufs/ext2fs/ext2fs_dir.h> 59 #include <ufs/ext2fs/ext2fs_htree.h> 60 #include <ufs/ext2fs/ext2fs_hash.h> 61 62 int 63 ext2fs_htree_has_idx(struct inode *ip) 64 { 65 return EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) 66 && (ip->i_din.e2fs_din->e2di_flags & EXT2_INDEX); 67 } 68 69 static off_t 70 ext2fs_htree_get_block(struct ext2fs_htree_entry *ep) 71 { 72 return ep->h_blk & 0x00FFFFFF; 73 } 74 75 76 static void 77 ext2fs_htree_release(struct ext2fs_htree_lookup_info *info) 78 { 79 for (u_int i = 0; i < info->h_levels_num; i++) { 80 struct buf *bp = info->h_levels[i].h_bp; 81 if (bp != NULL) 82 brelse(bp, 0); 83 } 84 } 85 86 static uint16_t 87 ext2fs_htree_get_limit(struct ext2fs_htree_entry *ep) 88 { 89 return ((struct ext2fs_htree_count *)(ep))->h_entries_max; 90 } 91 92 static uint32_t 93 ext2fs_htree_root_limit(struct inode *ip, int len) 94 { 95 uint32_t space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) - 96 EXT2_DIR_REC_LEN(2) - len; 97 return space / sizeof(struct ext2fs_htree_entry); 98 } 99 100 static uint16_t 101 ext2fs_htree_get_count(struct ext2fs_htree_entry *ep) 102 { 103 return ((struct ext2fs_htree_count *)(ep))->h_entries_num; 104 } 105 106 static uint32_t 107 ext2fs_htree_get_hash(struct ext2fs_htree_entry *ep) 108 { 109 return ep->h_hash; 110 } 111 112 static int 113 ext2fs_htree_check_next(struct inode *ip, uint32_t hash, const char *name, 114 struct ext2fs_htree_lookup_info *info) 115 { 116 struct vnode *vp = ITOV(ip); 117 struct ext2fs_htree_lookup_level *level; 118 struct buf *bp; 119 uint32_t next_hash; 120 int idx = info->h_levels_num - 1; 121 int levels = 0; 122 123 for (;;) { 124 level = &info->h_levels[idx]; 125 level->h_entry++; 126 if (level->h_entry < level->h_entries + 127 ext2fs_htree_get_count(level->h_entries)) 128 break; 129 if (idx == 0) 130 return 0; 131 idx--; 132 levels++; 133 } 134 135 next_hash = ext2fs_htree_get_hash(level->h_entry); 136 if ((hash & 1) == 0) { 137 if (hash != (next_hash & ~1)) 138 return 0; 139 } 140 141 while (levels > 0) { 142 levels--; 143 if (ext2fs_blkatoff(vp, ext2fs_htree_get_block(level->h_entry) * 144 ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0) 145 return 0; 146 level = &info->h_levels[idx + 1]; 147 brelse(level->h_bp, 0); 148 level->h_bp = bp; 149 level->h_entry = level->h_entries = 150 ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 151 } 152 153 return 1; 154 } 155 156 static int 157 ext2fs_htree_find_leaf(struct inode *ip, const char *name, int namelen, 158 uint32_t *hash, uint8_t *hash_ver, 159 struct ext2fs_htree_lookup_info *info) 160 { 161 struct vnode *vp; 162 struct ext2fs *fs;/* F, G, and H are MD4 functions */ 163 struct m_ext2fs *m_fs; 164 struct buf *bp = NULL; 165 struct ext2fs_htree_root *rootp; 166 struct ext2fs_htree_entry *entp, *start, *end, *middle, *found; 167 struct ext2fs_htree_lookup_level *level_info; 168 uint32_t hash_major = 0, hash_minor = 0; 169 uint32_t levels, cnt; 170 uint8_t hash_version; 171 172 if (name == NULL || info == NULL) 173 return -1; 174 175 vp = ITOV(ip); 176 fs = &(ip->i_e2fs->e2fs); 177 m_fs = ip->i_e2fs; 178 179 if (ext2fs_blkatoff(vp, 0, NULL, &bp) != 0) 180 return -1; 181 182 info->h_levels_num = 1; 183 info->h_levels[0].h_bp = bp; 184 rootp = (struct ext2fs_htree_root *)bp->b_data; 185 if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY && 186 rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 && 187 rootp->h_info.h_hash_version != EXT2_HTREE_TEA) 188 goto error; 189 190 hash_version = rootp->h_info.h_hash_version; 191 if (hash_version <= EXT2_HTREE_TEA) 192 hash_version += m_fs->e2fs_uhash; 193 *hash_ver = hash_version; 194 195 ext2fs_htree_hash(name, namelen, fs->e3fs_hash_seed, 196 hash_version, &hash_major, &hash_minor); 197 *hash = hash_major; 198 199 if ((levels = rootp->h_info.h_ind_levels) > 1) 200 goto error; 201 202 entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) + 203 rootp->h_info.h_info_len); 204 205 if (ext2fs_htree_get_limit(entp) != 206 ext2fs_htree_root_limit(ip, rootp->h_info.h_info_len)) 207 goto error; 208 209 for (;;) { 210 cnt = ext2fs_htree_get_count(entp); 211 if (cnt == 0 || cnt > ext2fs_htree_get_limit(entp)) 212 goto error; 213 214 start = entp + 1; 215 end = entp + cnt - 1; 216 while (start <= end) { 217 middle = start + (end - start) / 2; 218 if (ext2fs_htree_get_hash(middle) > hash_major) 219 end = middle - 1; 220 else 221 start = middle + 1; 222 } 223 found = start - 1; 224 225 level_info = &(info->h_levels[info->h_levels_num - 1]); 226 level_info->h_bp = bp; 227 level_info->h_entries = entp; 228 level_info->h_entry = found; 229 if (levels == 0) 230 return (0); 231 levels--; 232 if (ext2fs_blkatoff(vp, 233 ext2fs_htree_get_block(found) * m_fs->e2fs_bsize, 234 NULL, &bp) != 0) 235 goto error; 236 entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries; 237 info->h_levels_num++; 238 info->h_levels[info->h_levels_num - 1].h_bp = bp; 239 } 240 241 error: 242 ext2fs_htree_release(info); 243 return -1; 244 } 245 246 /* 247 * Try to lookup a directory entry in HTree index 248 */ 249 int 250 ext2fs_htree_lookup(struct inode *ip, const char *name, int namelen, 251 struct buf **bpp, int *entryoffp, doff_t *offp, 252 doff_t *prevoffp, doff_t *endusefulp, struct ext2fs_searchslot *ss) 253 { 254 struct vnode *vp; 255 struct ext2fs_htree_lookup_info info; 256 struct ext2fs_htree_entry *leaf_node; 257 struct m_ext2fs *m_fs; 258 struct buf *bp; 259 uint32_t blk; 260 uint32_t dirhash; 261 uint32_t bsize; 262 uint8_t hash_version; 263 int search_next; 264 265 m_fs = ip->i_e2fs; 266 bsize = m_fs->e2fs_bsize; 267 vp = ITOV(ip); 268 269 /* TODO: print error msg because we don't lookup '.' and '..' */ 270 271 memset(&info, 0, sizeof(info)); 272 if (ext2fs_htree_find_leaf(ip, name, namelen, &dirhash, 273 &hash_version, &info)) { 274 return -1; 275 } 276 277 do { 278 leaf_node = info.h_levels[info.h_levels_num - 1].h_entry; 279 blk = ext2fs_htree_get_block(leaf_node); 280 if (ext2fs_blkatoff(vp, blk * bsize, NULL, &bp) != 0) { 281 ext2fs_htree_release(&info); 282 return -1; 283 } 284 285 *offp = blk * bsize; 286 *entryoffp = 0; 287 *prevoffp = blk * bsize; 288 *endusefulp = blk * bsize; 289 290 if (ss->slotstatus == NONE) { 291 ss->slotoffset = -1; 292 ss->slotfreespace = 0; 293 } 294 295 int found; 296 if (ext2fs_search_dirblock(ip, bp->b_data, &found, 297 name, namelen, entryoffp, offp, prevoffp, 298 endusefulp, ss) != 0) { 299 brelse(bp, 0); 300 ext2fs_htree_release(&info); 301 return -1; 302 } 303 304 if (found) { 305 *bpp = bp; 306 ext2fs_htree_release(&info); 307 return 0; 308 } 309 310 brelse(bp,0); 311 search_next = ext2fs_htree_check_next(ip, dirhash, name, &info); 312 } while (search_next); 313 314 ext2fs_htree_release(&info); 315 return ENOENT; 316 } 317