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