fs/afs/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  */
  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, 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 }