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, before, after;
  72
  73         mask = (1 << nr_slots) - 1;
  74         mask <<= bit;
  75
  76         before = *(u64 *)block->hdr.bitmap;
  77
  78         block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
  79         block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
  80         block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
  81         block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
  82         block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
  83         block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
  84         block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
  85         block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
  86
  87         after = *(u64 *)block->hdr.bitmap;
  88 }
  89
  90 /*
  91  * Clear a number of contiguous bits in the directory block bitmap.
  92  */
  93 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
  94                                   int bit, unsigned int nr_slots)
  95 {
  96         u64 mask, before, after;
  97
  98         mask = (1 << nr_slots) - 1;
  99         mask <<= bit;
 100
 101         before = *(u64 *)block->hdr.bitmap;
 102
 103         block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
 104         block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
 105         block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
 106         block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
 107         block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
 108         block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
 109         block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
 110         block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
 111
 112         after = *(u64 *)block->hdr.bitmap;
 113 }
 114
 115 /*
 116  * Scan a directory block looking for a dirent of the right name.
 117  */
 118 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
 119                               unsigned int blocknum)
 120 {
 121         union afs_xdr_dirent *de;
 122         u64 bitmap;
 123         int d, len, n;
 124
 125         _enter("");
 126
 127         bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
 128         bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
 129         bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
 130         bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
 131         bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
 132         bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
 133         bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
 134         bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
 135
 136         for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
 137              d < AFS_DIR_SLOTS_PER_BLOCK;
 138              d++) {
 139                 if (!((bitmap >> d) & 1))
 140                         continue;
 141                 de = &block->dirents[d];
 142                 if (de->u.valid != 1)
 143                         continue;
 144
 145                 /* The block was NUL-terminated by afs_dir_check_page(). */
 146                 len = strlen(de->u.name);
 147                 if (len == name->len &&
 148                     memcmp(de->u.name, name->name, name->len) == 0)
 149                         return d;
 150
 151                 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 152                 n /= AFS_DIR_DIRENT_SIZE;
 153                 d += n - 1;
 154         }
 155
 156         return -1;
 157 }
 158
 159 /*
 160  * Initialise a new directory block.  Note that block 0 is special and contains
 161  * some extra metadata.
 162  */
 163 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
 164                                 union afs_xdr_dir_block *block, int block_num)
 165 {
 166         memset(block, 0, sizeof(*block));
 167         block->hdr.npages = htons(1);
 168         block->hdr.magic = AFS_DIR_MAGIC;
 169         block->hdr.bitmap[0] = 1;
 170
 171         if (block_num == 0) {
 172                 block->hdr.bitmap[0] = 0xff;
 173                 block->hdr.bitmap[1] = 0x1f;
 174                 memset(block->meta.alloc_ctrs,
 175                        AFS_DIR_SLOTS_PER_BLOCK,
 176                        sizeof(block->meta.alloc_ctrs));
 177                 meta->meta.alloc_ctrs[0] =
 178                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
 179         }
 180
 181         if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
 182                 meta->meta.alloc_ctrs[block_num] =
 183                         AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
 184 }
 185
 186 /*
 187  * Edit a directory's file data to add a new directory entry.  Doing this after
 188  * create, mkdir, symlink, link or rename if the data version number is
 189  * incremented by exactly one avoids the need to re-download the entire
 190  * directory contents.
 191  *
 192  * The caller must hold the inode locked.
 193  */
 194 void afs_edit_dir_add(struct afs_vnode *vnode,
 195                       struct qstr *name, struct afs_fid *new_fid,
 196                       enum afs_edit_dir_reason why)
 197 {
 198         union afs_xdr_dir_block *meta, *block;
 199         struct afs_xdr_dir_page *meta_page, *dir_page;
 200         union afs_xdr_dirent *de;
 201         struct page *page0, *page;
 202         unsigned int need_slots, nr_blocks, b;
 203         pgoff_t index;
 204         loff_t i_size;
 205         gfp_t gfp;
 206         int slot;
 207
 208         _enter(",,{%d,%s},", name->len, name->name);
 209
 210         i_size = i_size_read(&vnode->vfs_inode);
 211         if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 212             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 213                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 214                 return;
 215         }
 216
 217         gfp = vnode->vfs_inode.i_mapping->gfp_mask;
 218         page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
 219         if (!page0) {
 220                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 221                 _leave(" [fgp]");
 222                 return;
 223         }
 224
 225         /* Work out how many slots we're going to need. */
 226         need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 227         need_slots /= AFS_DIR_DIRENT_SIZE;
 228
 229         meta_page = kmap(page0);
 230         meta = &meta_page->blocks[0];
 231         if (i_size == 0)
 232                 goto new_directory;
 233         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 234
 235         /* Find a block that has sufficient slots available.  Each VM page
 236          * contains two or more directory blocks.
 237          */
 238         for (b = 0; b < nr_blocks + 1; b++) {
 239                 /* If the directory extended into a new page, then we need to
 240                  * tack a new page on the end.
 241                  */
 242                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 243                 if (index == 0) {
 244                         page = page0;
 245                         dir_page = meta_page;
 246                 } else {
 247                         if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
 248                                 goto error;
 249                         gfp = vnode->vfs_inode.i_mapping->gfp_mask;
 250                         page = find_or_create_page(vnode->vfs_inode.i_mapping,
 251                                                    index, gfp);
 252                         if (!page)
 253                                 goto error;
 254                         if (!PagePrivate(page)) {
 255                                 set_page_private(page, 1);
 256                                 SetPagePrivate(page);
 257                         }
 258                         dir_page = kmap(page);
 259                 }
 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                 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
 266
 267                 _debug("block %u: %2u %3u %u",
 268                        b,
 269                        (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
 270                        ntohs(block->hdr.npages),
 271                        ntohs(block->hdr.magic));
 272
 273                 /* Initialise the block if necessary. */
 274                 if (b == nr_blocks) {
 275                         _debug("init %u", b);
 276                         afs_edit_init_block(meta, block, b);
 277                         i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
 278                 }
 279
 280                 /* Only lower dir pages have a counter in the header. */
 281                 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
 282                     meta->meta.alloc_ctrs[b] >= need_slots) {
 283                         /* We need to try and find one or more consecutive
 284                          * slots to hold the entry.
 285                          */
 286                         slot = afs_find_contig_bits(block, need_slots);
 287                         if (slot >= 0) {
 288                                 _debug("slot %u", slot);
 289                                 goto found_space;
 290                         }
 291                 }
 292
 293                 if (page != page0) {
 294                         unlock_page(page);
 295                         kunmap(page);
 296                         put_page(page);
 297                 }
 298         }
 299
 300         /* There are no spare slots of sufficient size, yet the operation
 301          * succeeded.  Download the directory again.
 302          */
 303         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
 304         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 305         goto out_unmap;
 306
 307 new_directory:
 308         afs_edit_init_block(meta, meta, 0);
 309         i_size = AFS_DIR_BLOCK_SIZE;
 310         i_size_write(&vnode->vfs_inode, i_size);
 311         slot = AFS_DIR_RESV_BLOCKS0;
 312         page = page0;
 313         block = meta;
 314         nr_blocks = 1;
 315         b = 0;
 316
 317 found_space:
 318         /* Set the dirent slot. */
 319         trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
 320                            new_fid->vnode, new_fid->unique, name->name);
 321         de = &block->dirents[slot];
 322         de->u.valid     = 1;
 323         de->u.unused[0] = 0;
 324         de->u.hash_next = 0; // TODO: Really need to maintain this
 325         de->u.vnode     = htonl(new_fid->vnode);
 326         de->u.unique    = htonl(new_fid->unique);
 327         memcpy(de->u.name, name->name, name->len + 1);
 328         de->u.name[name->len] = 0;
 329
 330         /* Adjust the bitmap. */
 331         afs_set_contig_bits(block, slot, need_slots);
 332         if (page != page0) {
 333                 unlock_page(page);
 334                 kunmap(page);
 335                 put_page(page);
 336         }
 337
 338         /* Adjust the allocation counter. */
 339         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 340                 meta->meta.alloc_ctrs[b] -= need_slots;
 341
 342         inode_inc_iversion_raw(&vnode->vfs_inode);
 343         afs_stat_v(vnode, n_dir_cr);
 344         _debug("Insert %s in %u[%u]", name->name, b, slot);
 345
 346 out_unmap:
 347         unlock_page(page0);
 348         kunmap(page0);
 349         put_page(page0);
 350         _leave("");
 351         return;
 352
 353 invalidated:
 354         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
 355         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 356         if (page != page0) {
 357                 kunmap(page);
 358                 put_page(page);
 359         }
 360         goto out_unmap;
 361
 362 error:
 363         trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
 364         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 365         goto out_unmap;
 366 }
 367
 368 /*
 369  * Edit a directory's file data to remove a new directory entry.  Doing this
 370  * after unlink, rmdir or rename if the data version number is incremented by
 371  * exactly one avoids the need to re-download the entire directory contents.
 372  *
 373  * The caller must hold the inode locked.
 374  */
 375 void afs_edit_dir_remove(struct afs_vnode *vnode,
 376                          struct qstr *name, enum afs_edit_dir_reason why)
 377 {
 378         struct afs_xdr_dir_page *meta_page, *dir_page;
 379         union afs_xdr_dir_block *meta, *block;
 380         union afs_xdr_dirent *de;
 381         struct page *page0, *page;
 382         unsigned int need_slots, nr_blocks, b;
 383         pgoff_t index;
 384         loff_t i_size;
 385         int slot;
 386
 387         _enter(",,{%d,%s},", name->len, name->name);
 388
 389         i_size = i_size_read(&vnode->vfs_inode);
 390         if (i_size < AFS_DIR_BLOCK_SIZE ||
 391             i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
 392             (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
 393                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 394                 return;
 395         }
 396         nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
 397
 398         page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
 399         if (!page0) {
 400                 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 401                 _leave(" [fgp]");
 402                 return;
 403         }
 404
 405         /* Work out how many slots we're going to discard. */
 406         need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
 407         need_slots /= AFS_DIR_DIRENT_SIZE;
 408
 409         meta_page = kmap(page0);
 410         meta = &meta_page->blocks[0];
 411
 412         /* Find a page that has sufficient slots available.  Each VM page
 413          * contains two or more directory blocks.
 414          */
 415         for (b = 0; b < nr_blocks; b++) {
 416                 index = b / AFS_DIR_BLOCKS_PER_PAGE;
 417                 if (index != 0) {
 418                         page = find_lock_page(vnode->vfs_inode.i_mapping, index);
 419                         if (!page)
 420                                 goto error;
 421                         dir_page = kmap(page);
 422                 } else {
 423                         page = page0;
 424                         dir_page = meta_page;
 425                 }
 426
 427                 /* Abandon the edit if we got a callback break. */
 428                 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
 429                         goto invalidated;
 430
 431                 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
 432
 433                 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
 434                     meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
 435                         slot = afs_dir_scan_block(block, name, b);
 436                         if (slot >= 0)
 437                                 goto found_dirent;
 438                 }
 439
 440                 if (page != page0) {
 441                         unlock_page(page);
 442                         kunmap(page);
 443                         put_page(page);
 444                 }
 445         }
 446
 447         /* Didn't find the dirent to clobber.  Download the directory again. */
 448         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
 449                            0, 0, 0, 0, name->name);
 450         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 451         goto out_unmap;
 452
 453 found_dirent:
 454         de = &block->dirents[slot];
 455
 456         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
 457                            ntohl(de->u.vnode), ntohl(de->u.unique),
 458                            name->name);
 459
 460         memset(de, 0, sizeof(*de) * need_slots);
 461
 462         /* Adjust the bitmap. */
 463         afs_clear_contig_bits(block, slot, need_slots);
 464         if (page != page0) {
 465                 unlock_page(page);
 466                 kunmap(page);
 467                 put_page(page);
 468         }
 469
 470         /* Adjust the allocation counter. */
 471         if (b < AFS_DIR_BLOCKS_WITH_CTR)
 472                 meta->meta.alloc_ctrs[b] += need_slots;
 473
 474         inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
 475         afs_stat_v(vnode, n_dir_rm);
 476         _debug("Remove %s from %u[%u]", name->name, b, slot);
 477
 478 out_unmap:
 479         unlock_page(page0);
 480         kunmap(page0);
 481         put_page(page0);
 482         _leave("");
 483         return;
 484
 485 invalidated:
 486         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
 487                            0, 0, 0, 0, name->name);
 488         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 489         if (page != page0) {
 490                 unlock_page(page);
 491                 kunmap(page);
 492                 put_page(page);
 493         }
 494         goto out_unmap;
 495
 496 error:
 497         trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
 498                            0, 0, 0, 0, name->name);
 499         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
 500         goto out_unmap;
 501 }