| 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 ([email protected]) |
| 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 |
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 |
*/ |
| 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 |
*/ |
| 191 |
int afs_dir_search(struct afs_vnode *dvnode, const 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 |
} |