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 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 */
afs_dir_search_bucket(struct afs_dir_iter * iter,const struct qstr * name,struct afs_fid * _fid)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 */
afs_dir_search(struct afs_vnode * dvnode,const struct qstr * name,struct afs_fid * _fid,afs_dataversion_t * _dir_version)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