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 */ 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 */ 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 */ 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 */ 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 afs_dir_end_iter(iter); 79 80 if (dvnode->directory_size < blend) 81 goto fail; 82 83 if (!fq || blpos < fpos) { 84 fq = dvnode->directory; 85 slot = 0; 86 fpos = 0; 87 } 88 89 /* Search the folio queue for the folio containing the block... */ 90 for (; fq; fq = fq->next) { 91 for (; slot < folioq_count(fq); slot++) { 92 size_t fsize = folioq_folio_size(fq, slot); 93 94 if (blend <= fpos + fsize) { 95 /* ... and then return the mapped block. */ 96 folio = folioq_folio(fq, slot); 97 if (WARN_ON_ONCE(folio_pos(folio) != fpos)) 98 goto fail; 99 iter->fq = fq; 100 iter->fq_slot = slot; 101 iter->fpos = fpos; 102 iter->block = kmap_local_folio(folio, blpos - fpos); 103 return iter->block; 104 } 105 fpos += fsize; 106 } 107 slot = 0; 108 } 109 110 fail: 111 iter->fq = NULL; 112 iter->fq_slot = 0; 113 afs_invalidate_dir(dvnode, afs_dir_invalid_edit_get_block); 114 return NULL; 115 } 116 117 /* 118 * Search through a directory bucket. 119 */ 120 int afs_dir_search_bucket(struct afs_dir_iter *iter, const struct qstr *name, 121 struct afs_fid *_fid) 122 { 123 const union afs_xdr_dir_block *meta; 124 unsigned int entry; 125 int ret = -ESTALE; 126 127 meta = afs_dir_find_block(iter, 0); 128 if (!meta) 129 return -ESTALE; 130 131 entry = ntohs(meta->meta.hashtable[iter->bucket & (AFS_DIR_HASHTBL_SIZE - 1)]); 132 _enter("%x,%x", iter->bucket, entry); 133 134 while (entry) { 135 const union afs_xdr_dir_block *block; 136 const union afs_xdr_dirent *dire; 137 unsigned int blnum = entry / AFS_DIR_SLOTS_PER_BLOCK; 138 unsigned int slot = entry % AFS_DIR_SLOTS_PER_BLOCK; 139 unsigned int resv = (blnum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS); 140 141 _debug("search %x", entry); 142 143 if (slot < resv) { 144 kdebug("slot out of range h=%x rs=%2x sl=%2x-%2x", 145 iter->bucket, resv, slot, slot + iter->nr_slots - 1); 146 goto bad; 147 } 148 149 block = afs_dir_find_block(iter, blnum); 150 if (!block) 151 goto bad; 152 dire = &block->dirents[slot]; 153 154 if (slot + iter->nr_slots <= AFS_DIR_SLOTS_PER_BLOCK && 155 memcmp(dire->u.name, name->name, name->len) == 0 && 156 dire->u.name[name->len] == '\0') { 157 _fid->vnode = ntohl(dire->u.vnode); 158 _fid->unique = ntohl(dire->u.unique); 159 ret = entry; 160 goto found; 161 } 162 163 iter->prev_entry = entry; 164 entry = ntohs(dire->u.hash_next); 165 if (!--iter->loop_check) { 166 kdebug("dir chain loop h=%x", iter->bucket); 167 goto bad; 168 } 169 } 170 171 ret = -ENOENT; 172 found: 173 bad: 174 afs_dir_end_iter(iter); 175 if (ret == -ESTALE) 176 afs_invalidate_dir(iter->dvnode, afs_dir_invalid_iter_stale); 177 _leave(" = %d", ret); 178 return ret; 179 } 180 181 /* 182 * Search the appropriate hash chain in the contents of an AFS directory. 183 */ 184 int afs_dir_search(struct afs_vnode *dvnode, const struct qstr *name, 185 struct afs_fid *_fid, afs_dataversion_t *_dir_version) 186 { 187 struct afs_dir_iter iter = { .dvnode = dvnode, }; 188 int ret, retry_limit = 3; 189 190 _enter("{%llu},,,", dvnode->netfs.inode.i_ino); 191 192 if (!afs_dir_init_iter(&iter, name)) 193 return -ENOENT; 194 do { 195 if (--retry_limit < 0) { 196 pr_warn("afs_read_dir(): Too many retries\n"); 197 ret = -ESTALE; 198 break; 199 } 200 ret = afs_read_dir(dvnode, NULL); 201 if (ret < 0) { 202 if (ret != -ESTALE) 203 break; 204 if (test_bit(AFS_VNODE_DELETED, &dvnode->flags)) { 205 ret = -ESTALE; 206 break; 207 } 208 continue; 209 } 210 *_dir_version = inode_peek_iversion_raw(&dvnode->netfs.inode); 211 212 ret = afs_dir_search_bucket(&iter, name, _fid); 213 up_read(&dvnode->validate_lock); 214 if (ret == -ESTALE) 215 afs_dir_reset_iter(&iter); 216 } while (ret == -ESTALE); 217 218 _leave(" = %d", ret); 219 return ret; 220 } 221