fs/afs/dir_edit.c

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /* AFS filesystem directory editing
   3  *
   4  * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
   5  * Written by David Howells (dhowells@redhat.com)
   6  */
   7
   8 #include <linux/kernel.h>
   9 #include <linux/fs.h>
  10 #include <linux/namei.h>
  11 #include <linux/pagemap.h>
  12 #include <linux/iversion.h>
  13 #include "internal.h"
  14 #include "xdr_fs.h"
  15
  16 /*
  17  * Find a number of contiguous clear bits in a directory block bitmask.
  18  *
  19  * There are 64 slots, which means we can load the entire bitmap into a
  20  * variable.  The first bit doesn't count as it corresponds to the block header
  21  * slot.  nr_slots is between 1 and 9.
  22  */
  23 static int afs_find_contig_bits(union afs_xdr_dir_block *block, unsigned int nr_slots)
  24 {
  25         u64 bitmap;
  26         u32 mask;
  27         int bit, n;
  28
  29         bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
  30         bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
  31         bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
  32         bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
  33         bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
  34         bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
  35         bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
  36         bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
  37         bitmap >>= 1; /* The first entry is metadata */
  38         bit = 1;
  39         mask = (1 << nr_slots) - 1;
  40
  41         do {
  42                 if (sizeof(unsigned long) == 8)
  43                         n = ffz(bitmap);
  44                 else
  45                         n = ((u32)bitmap) != 0 ?
  46                                 ffz((u32)bitmap) :
  47                                 ffz((u32)(bitmap >> 32)) + 32;
  48                 bitmap >>= n;
  49                 bit += n;
  50
  51                 if ((bitmap & mask) == 0) {
  52                         if (bit > 64 - nr_slots)
  53                                 return -1;
  54                         return bit;
  55                 }
  56
  57                 n = __ffs(bitmap);
  58                 bitmap >>= n;
  59                 bit += n;
  60         } while (bitmap);
  61
  62         return -1;
  63 }
  64
  65 /*
  66  * Set a number of contiguous bits in the directory block bitmap.
  67  */
  68 static void afs_set_contig_bits(union afs_xdr_dir_block *block,
  69                                 int bit, unsigned int nr_slots)
  70 {
  71         u64 mask;
  72
  73         mask = (1 << nr_slots) - 1;
  74         mask <<= bit;
  75
  76         block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
  77         block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
  78         block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
  79         block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
  80         block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
  81         block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
  82         block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
  83         block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
  84 }
  85
  86 /*
  87  * Clear a number of contiguous bits in the directory block bitmap.
  88  */
  89 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
  90                                   int bit, unsigned int nr_slots)
  91 {
  92         u64 mask;
  93
  94         mask = (1 << nr_slots) - 1;
  95         mask <<= bit;
  96
  97         block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
  98         block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
  99         block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
 100         block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
 101         block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
 102         block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
 103         block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
 104         block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
 105 }
 106
 107 /*
 108  * Get a new directory folio.
 109  */
 110 static struct folio *afs_dir_get_folio(struct afs_vnode *vnode, pgoff_t index)
 111 {
 112         struct address_space *mapping = vnode->netfs.inode.i_mapping;
 113         struct folio *folio;
 114
 115         folio = __filemap_get_folio(mapping, index,
 116                                     FGP_LOCK | FGP_ACCESSED | FGP_CREAT,
 117                                     mapping->gfp_mask);
 118         if (IS_ERR(folio)) {
 119                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 120                 return NULL;
 121         }
 122         if (!folio_test_private(folio))
 123                 folio_attach_private(folio, (void *)1);
 124         return folio;
 125 }
 126
 127 /*
 128  * Scan a directory block looking for a dirent of the right name.
 129  */
 130 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
 131                               unsigned int blocknum)
 132 {
 133         union afs_xdr_dirent *de;
 134         u64 bitmap;
 135         int d, len, n;
 136
 137         _enter("");
 138
 139         bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
 140         bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
 141         bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
 142         bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
 143         bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
 144         bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
 145         bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
 146         bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
 147
 148         for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
 149              d < AFS_DIR_SLOTS_PER_BLOCK;
 150              d++) {
 151                 if (!((bitmap >> d) & 1))
 152                         continue;
 153                 de = &block->dirents[d];
 154                 if (de->u.valid != 1)
 155                         continue;
 156
 157                 /* The block was NUL-terminated by afs_dir_check_page(). */
 158                 len = strlen(de->u.name);
 159                 if (len == name->len &&
 160                     memcmp(de->u.name, name->name, name->len) == 0)
 161                         return d;
 162
 163                 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 164                 n /= AFS_DIR_DIRENT_SIZE;
 165                 d += n - 1;
 166         }
 167
 168         return -1;
 169 }
 170
 171 /*
 172  * Initialise a new directory block.  Note that block 0 is special and contains
 173  * some extra metadata.
 174  */
 175 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
 176                                 union afs_xdr_dir_block *block, int block_num)
 177 {
 178         memset(block, 0, sizeof(*block));
 179         block->hdr.npages = htons(1);
 180         block->hdr.magic = AFS_DIR_MAGIC;
 181         block->hdr.bitmap[0] = 1;
 182
 183         if (block_num == 0) {
 184                 block->hdr.bitmap[0] = 0xff;
 185                 block->hdr.bitmap[1] = 0x1f;
 186                 memset(block->meta.alloc_ctrs,
 187                        AFS_DIR_SLOTS_PER_BLOCK,
 188                        sizeof(block->meta.alloc_ctrs));
 189                 meta->meta.alloc_ctrs[0] =
 190                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
 191         }
 192
 193         if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
 194                 meta->meta.alloc_ctrs[block_num] =
 195                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
 196 }
 197
 198 /*
 199  * Edit a directory's file data to add a new directory entry.  Doing this after
 200  * create, mkdir, symlink, link or rename if the data version number is
 201  * incremented by exactly one avoids the need to re-download the entire
 202  * directory contents.
 203  *
 204  * The caller must hold the inode locked.
 205  */
 206 void afs_edit_dir_add(struct afs_vnode *vnode,
 207                       struct qstr *name, struct afs_fid *new_fid,
 208                       enum afs_edit_dir_reason why)
 209 {
 210         union afs_xdr_dir_block *meta, *block;
 211         union afs_xdr_dirent *de;
 212         struct folio *folio0, *folio;
 213         unsigned int need_slots, nr_blocks, b;
 214         pgoff_t index;
 215         loff_t i_size;
 216         int slot;
 217
 218         _enter(",,{%d,%s},", name->len, name->name);
 219
 220         i_size = i_size_read(&vnode->netfs.inode);
 221         if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 222             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 223                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 224                 return;
 225         }
 226
 227         folio0 = afs_dir_get_folio(vnode, 0);
 228         if (!folio0) {
 229                 _leave(" [fgp]");
 230                 return;
 231         }
 232
 233         /* Work out how many slots we're going to need. */
 234         need_slots = afs_dir_calc_slots(name->len);
 235
 236         meta = kmap_local_folio(folio0, 0);
 237         if (i_size == 0)
 238                 goto new_directory;
 239         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 240
 241         /* Find a block that has sufficient slots available.  Each folio
 242          * contains two or more directory blocks.
 243          */
 244         for (b = 0; b < nr_blocks + 1; b++) {
 245                 /* If the directory extended into a new folio, then we need to
 246                  * tack a new folio on the end.
 247                  */
 248                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 249                 if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
 250                         goto error;
 251                 if (index >= folio_nr_pages(folio0)) {
 252                         folio = afs_dir_get_folio(vnode, index);
 253                         if (!folio)
 254                                 goto error;
 255                 } else {
 256                         folio = folio0;
 257                 }
 258
 259                 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));
 260
 261                 /* Abandon the edit if we got a callback break. */
 262                 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
 263                         goto invalidated;
 264
 265                 _debug("block %u: %2u %3u %u",
 266                        b,
 267                        (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
 268                        ntohs(block->hdr.npages),
 269                        ntohs(block->hdr.magic));
 270
 271                 /* Initialise the block if necessary. */
 272                 if (b == nr_blocks) {
 273                         _debug("init %u", b);
 274                         afs_edit_init_block(meta, block, b);
 275                         afs_set_i_size(vnode, (b + 1) * AFS_DIR_BLOCK_SIZE);
 276                 }
 277
 278                 /* Only lower dir blocks have a counter in the header. */
 279                 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
 280                     meta->meta.alloc_ctrs[b] >= need_slots) {
 281                         /* We need to try and find one or more consecutive
 282                          * slots to hold the entry.
 283                          */
 284                         slot = afs_find_contig_bits(block, need_slots);
 285                         if (slot >= 0) {
 286                                 _debug("slot %u", slot);
 287                                 goto found_space;
 288                         }
 289                 }
 290
 291                 kunmap_local(block);
 292                 if (folio != folio0) {
 293                         folio_unlock(folio);
 294                         folio_put(folio);
 295                 }
 296         }
 297
 298         /* There are no spare slots of sufficient size, yet the operation
 299          * succeeded.  Download the directory again.
 300          */
 301         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
 302         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 303         goto out_unmap;
 304
 305 new_directory:
 306         afs_edit_init_block(meta, meta, 0);
 307         i_size = AFS_DIR_BLOCK_SIZE;
 308         afs_set_i_size(vnode, i_size);
 309         slot = AFS_DIR_RESV_BLOCKS0;
 310         folio = folio0;
 311         block = kmap_local_folio(folio, 0);
 312         nr_blocks = 1;
 313         b = 0;
 314
 315 found_space:
 316         /* Set the dirent slot. */
 317         trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
 318                            new_fid->vnode, new_fid->unique, name->name);
 319         de = &block->dirents[slot];
 320         de->u.valid     = 1;
 321         de->u.unused[0] = 0;
 322         de->u.hash_next = 0; // TODO: Really need to maintain this
 323         de->u.vnode     = htonl(new_fid->vnode);
 324         de->u.unique    = htonl(new_fid->unique);
 325         memcpy(de->u.name, name->name, name->len + 1);
 326         de->u.name[name->len] = 0;
 327
 328         /* Adjust the bitmap. */
 329         afs_set_contig_bits(block, slot, need_slots);
 330         kunmap_local(block);
 331         if (folio != folio0) {
 332                 folio_unlock(folio);
 333                 folio_put(folio);
 334         }
 335
 336         /* Adjust the allocation counter. */
 337         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 338                 meta->meta.alloc_ctrs[b] -= need_slots;
 339
 340         inode_inc_iversion_raw(&vnode->netfs.inode);
 341         afs_stat_v(vnode, n_dir_cr);
 342         _debug("Insert %s in %u[%u]", name->name, b, slot);
 343
 344 out_unmap:
 345         kunmap_local(meta);
 346         folio_unlock(folio0);
 347         folio_put(folio0);
 348         _leave("");
 349         return;
 350
 351 invalidated:
 352         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
 353         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 354         kunmap_local(block);
 355         if (folio != folio0) {
 356                 folio_unlock(folio);
 357                 folio_put(folio);
 358         }
 359         goto out_unmap;
 360
 361 error:
 362         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
 363         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 364         goto out_unmap;
 365 }
 366
 367 /*
 368  * Edit a directory's file data to remove a new directory entry.  Doing this
 369  * after unlink, rmdir or rename if the data version number is incremented by
 370  * exactly one avoids the need to re-download the entire directory contents.
 371  *
 372  * The caller must hold the inode locked.
 373  */
 374 void afs_edit_dir_remove(struct afs_vnode *vnode,
 375                          struct qstr *name, enum afs_edit_dir_reason why)
 376 {
 377         union afs_xdr_dir_block *meta, *block;
 378         union afs_xdr_dirent *de;
 379         struct folio *folio0, *folio;
 380         unsigned int need_slots, nr_blocks, b;
 381         pgoff_t index;
 382         loff_t i_size;
 383         int slot;
 384
 385         _enter(",,{%d,%s},", name->len, name->name);
 386
 387         i_size = i_size_read(&vnode->netfs.inode);
 388         if (i_size < AFS_DIR_BLOCK_SIZE ||
 389             i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 390             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 391                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 392                 return;
 393         }
 394         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 395
 396         folio0 = afs_dir_get_folio(vnode, 0);
 397         if (!folio0) {
 398                 _leave(" [fgp]");
 399                 return;
 400         }
 401
 402         /* Work out how many slots we're going to discard. */
 403         need_slots = afs_dir_calc_slots(name->len);
 404
 405         meta = kmap_local_folio(folio0, 0);
 406
 407         /* Find a block that has sufficient slots available.  Each folio
 408          * contains two or more directory blocks.
 409          */
 410         for (b = 0; b < nr_blocks; b++) {
 411                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 412                 if (index >= folio_nr_pages(folio0)) {
 413                         folio = afs_dir_get_folio(vnode, index);
 414                         if (!folio)
 415                                 goto error;
 416                 } else {
 417                         folio = folio0;
 418                 }
 419
 420                 block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_pos(folio));
 421
 422                 /* Abandon the edit if we got a callback break. */
 423                 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
 424                         goto invalidated;
 425
 426                 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
 427                     meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
 428                         slot = afs_dir_scan_block(block, name, b);
 429                         if (slot >= 0)
 430                                 goto found_dirent;
 431                 }
 432
 433                 kunmap_local(block);
 434                 if (folio != folio0) {
 435                         folio_unlock(folio);
 436                         folio_put(folio);
 437                 }
 438         }
 439
 440         /* Didn't find the dirent to clobber.  Download the directory again. */
 441         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
 442                            0, 0, 0, 0, name->name);
 443         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 444         goto out_unmap;
 445
 446 found_dirent:
 447         de = &block->dirents[slot];
 448
 449         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
 450                            ntohl(de->u.vnode), ntohl(de->u.unique),
 451                            name->name);
 452
 453         memset(de, 0, sizeof(*de) * need_slots);
 454
 455         /* Adjust the bitmap. */
 456         afs_clear_contig_bits(block, slot, need_slots);
 457         kunmap_local(block);
 458         if (folio != folio0) {
 459                 folio_unlock(folio);
 460                 folio_put(folio);
 461         }
 462
 463         /* Adjust the allocation counter. */
 464         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 465                 meta->meta.alloc_ctrs[b] += need_slots;
 466
 467         inode_set_iversion_raw(&vnode->netfs.inode, vnode->status.data_version);
 468         afs_stat_v(vnode, n_dir_rm);
 469         _debug("Remove %s from %u[%u]", name->name, b, slot);
 470
 471 out_unmap:
 472         kunmap_local(meta);
 473         folio_unlock(folio0);
 474         folio_put(folio0);
 475         _leave("");
 476         return;
 477
 478 invalidated:
 479         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
 480                            0, 0, 0, 0, name->name);
 481         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 482         kunmap_local(block);
 483         if (folio != folio0) {
 484                 folio_unlock(folio);
 485                 folio_put(folio);
 486         }
 487         goto out_unmap;
 488
 489 error:
 490         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
 491                            0, 0, 0, 0, name->name);
 492         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 493         goto out_unmap;
 494 }