1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* Search a directory's hash table. 3 * 4 * Copyright (C) 2024 Red Hat, Inc. All Rights Reserved. 5 * Written by David Howells (dhowells@redhat.com) 6 * 7 * https://tools.ietf.org/html/draft-keiser-afs3-directory-object-00 8 */ 9 10 #include <linux/kernel.h> 11 #include <linux/fs.h> 12 #include <linux/namei.h> 13 #include <linux/iversion.h> 14 #include "internal.h" 15 #include "afs_fs.h" 16 #include "xdr_fs.h" 17 18 /* 19 * Calculate the name hash. 20 */ afs_dir_hash_name(const struct qstr * name)21 unsigned int afs_dir_hash_name(const struct qstr *name) 22 { 23 const unsigned char *p = name->name; 24 unsigned int hash = 0, i; 25 int bucket; 26 27 for (i = 0; i < name->len; i++) 28 hash = (hash * 173) + p[i]; 29 bucket = hash & (AFS_DIR_HASHTBL_SIZE - 1); 30 if (hash > INT_MAX) { 31 bucket = AFS_DIR_HASHTBL_SIZE - bucket; 32 bucket &= (AFS_DIR_HASHTBL_SIZE - 1); 33 } 34 return bucket; 35 } 36 37 /* 38 * Reset a directory iterator. 39 */ afs_dir_reset_iter(struct afs_dir_iter * iter)40 static bool afs_dir_reset_iter(struct afs_dir_iter *iter) 41 { 42 unsigned long long i_size = i_size_read(&iter->dvnode->netfs.inode); 43 unsigned int nblocks; 44 45 /* Work out the maximum number of steps we can take. */ 46 nblocks = umin(i_size / AFS_DIR_BLOCK_SIZE, AFS_DIR_MAX_BLOCKS); 47 if (!nblocks) 48 return false; 49 iter->loop_check = nblocks * (AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS); 50 iter->prev_entry = 0; /* Hash head is previous */ 51 return true; 52 } 53 54 /* 55 * Initialise a directory iterator for looking up a name. 56 */ afs_dir_init_iter(struct afs_dir_iter * iter,const struct qstr * name)57 bool afs_dir_init_iter(struct afs_dir_iter *iter, const struct qstr *name) 58 { 59 iter->nr_slots = afs_dir_calc_slots(name->len); 60 iter->bucket = afs_dir_hash_name(name); 61 return afs_dir_reset_iter(iter); 62 } 63 64 /* 65 * Get a specific block. 66 */ afs_dir_find_block(struct afs_dir_iter * iter,size_t block)67 union afs_xdr_dir_block *afs_dir_find_block(struct afs_dir_iter *iter, size_t block) 68 { 69 struct folio_queue *fq = iter->fq; 70 struct afs_vnode *dvnode = iter->dvnode; 71 struct folio *folio; 72 size_t blpos = block * AFS_DIR_BLOCK_SIZE; 73 size_t blend = (block + 1) * AFS_DIR_BLOCK_SIZE, fpos = iter->fpos; 74 int slot = iter->fq_slot; 75 76 _enter("%zx,%d", block, slot); 77 78 if (iter->block) { 79 kunmap_local(iter->block); 80 iter->block = NULL; 81 } 82 83 if (dvnode->directory_size < blend) 84 goto fail; 85 86 if (!fq || blpos < fpos) { 87 fq = dvnode->directory; 88 slot = 0; 89 fpos = 0; 90 } 91 92 /* Search the folio queue for the folio containing the block... */ 93 for (; fq; fq = fq->next) { 94 for (; slot < folioq_count(fq); slot++) { 95 size_t fsize = folioq_folio_size(fq, slot); 96 97 if (blend <= fpos + fsize) { 98 /* ... and then return the mapped block. */ 99 folio = folioq_folio(fq, slot); 100 if (WARN_ON_ONCE(folio_pos(folio) != fpos)) 101 goto fail; 102 iter->fq = fq; 103 iter->fq_slot = slot; 104 iter->fpos = fpos; 105 iter->block = kmap_local_folio(folio, blpos - fpos); 106 return iter->block; 107 } 108 fpos += fsize; 109 } 110 slot = 0; 111 } 112 113 fail: 114 iter->fq = NULL; 115 iter->fq_slot = 0; 116 afs_invalidate_dir(dvnode, afs_dir_invalid_edit_get_block); 117 return NULL; 118 } 119 120 /* 121 * Search through a directory bucket. 122 */ afs_dir_search_bucket(struct afs_dir_iter * iter,const struct qstr * name,struct afs_fid * _fid)123 int afs_dir_search_bucket(struct afs_dir_iter *iter, const struct qstr *name, 124 struct afs_fid *_fid) 125 { 126 const union afs_xdr_dir_block *meta; 127 unsigned int entry; 128 int ret = -ESTALE; 129 130 meta = afs_dir_find_block(iter, 0); 131 if (!meta) 132 return -ESTALE; 133 134 entry = ntohs(meta->meta.hashtable[iter->bucket & (AFS_DIR_HASHTBL_SIZE - 1)]); 135 _enter("%x,%x", iter->bucket, entry); 136 137 while (entry) { 138 const union afs_xdr_dir_block *block; 139 const union afs_xdr_dirent *dire; 140 unsigned int blnum = entry / AFS_DIR_SLOTS_PER_BLOCK; 141 unsigned int slot = entry % AFS_DIR_SLOTS_PER_BLOCK; 142 unsigned int resv = (blnum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS); 143 144 _debug("search %x", entry); 145 146 if (slot < resv) { 147 kdebug("slot out of range h=%x rs=%2x sl=%2x-%2x", 148 iter->bucket, resv, slot, slot + iter->nr_slots - 1); 149 goto bad; 150 } 151 152 block = afs_dir_find_block(iter, blnum); 153 if (!block) 154 goto bad; 155 dire = &block->dirents[slot]; 156 157 if (slot + iter->nr_slots <= AFS_DIR_SLOTS_PER_BLOCK && 158 memcmp(dire->u.name, name->name, name->len) == 0 && 159 dire->u.name[name->len] == '\0') { 160 _fid->vnode = ntohl(dire->u.vnode); 161 _fid->unique = ntohl(dire->u.unique); 162 ret = entry; 163 goto found; 164 } 165 166 iter->prev_entry = entry; 167 entry = ntohs(dire->u.hash_next); 168 if (!--iter->loop_check) { 169 kdebug("dir chain loop h=%x", iter->bucket); 170 goto bad; 171 } 172 } 173 174 ret = -ENOENT; 175 found: 176 if (iter->block) { 177 kunmap_local(iter->block); 178 iter->block = NULL; 179 } 180 181 bad: 182 if (ret == -ESTALE) 183 afs_invalidate_dir(iter->dvnode, afs_dir_invalid_iter_stale); 184 _leave(" = %d", ret); 185 return ret; 186 } 187 188 /* 189 * Search the appropriate hash chain in the contents of an AFS directory. 190 */ afs_dir_search(struct afs_vnode * dvnode,struct qstr * name,struct afs_fid * _fid,afs_dataversion_t * _dir_version)191 int afs_dir_search(struct afs_vnode *dvnode, struct qstr *name, 192 struct afs_fid *_fid, afs_dataversion_t *_dir_version) 193 { 194 struct afs_dir_iter iter = { .dvnode = dvnode, }; 195 int ret, retry_limit = 3; 196 197 _enter("{%lu},,,", dvnode->netfs.inode.i_ino); 198 199 if (!afs_dir_init_iter(&iter, name)) 200 return -ENOENT; 201 do { 202 if (--retry_limit < 0) { 203 pr_warn("afs_read_dir(): Too many retries\n"); 204 ret = -ESTALE; 205 break; 206 } 207 ret = afs_read_dir(dvnode, NULL); 208 if (ret < 0) { 209 if (ret != -ESTALE) 210 break; 211 if (test_bit(AFS_VNODE_DELETED, &dvnode->flags)) { 212 ret = -ESTALE; 213 break; 214 } 215 continue; 216 } 217 *_dir_version = inode_peek_iversion_raw(&dvnode->netfs.inode); 218 219 ret = afs_dir_search_bucket(&iter, name, _fid); 220 up_read(&dvnode->validate_lock); 221 if (ret == -ESTALE) 222 afs_dir_reset_iter(&iter); 223 } while (ret == -ESTALE); 224 225 _leave(" = %d", ret); 226 return ret; 227 } 228