LXR linux/fs/afs/dir

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