dir_search.c

  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 */
 21unsigned 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 */
 40static 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 */
 57bool 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 */
 67union 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
113fail:
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 */
123int 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;
175found:
176	if (iter->block) {
177		kunmap_local(iter->block);
178		iter->block = NULL;
179	}
180
181bad:
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 */
191int 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}