Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /* AFS filesystem directory editing
0003  *
0004  * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
0005  * Written by David Howells (dhowells@redhat.com)
0006  */
0007 
0008 #include <linux/kernel.h>
0009 #include <linux/fs.h>
0010 #include <linux/namei.h>
0011 #include <linux/pagemap.h>
0012 #include <linux/iversion.h>
0013 #include "internal.h"
0014 #include "xdr_fs.h"
0015 
0016 /*
0017  * Find a number of contiguous clear bits in a directory block bitmask.
0018  *
0019  * There are 64 slots, which means we can load the entire bitmap into a
0020  * variable.  The first bit doesn't count as it corresponds to the block header
0021  * slot.  nr_slots is between 1 and 9.
0022  */
0023 static int afs_find_contig_bits(union afs_xdr_dir_block *block, unsigned int nr_slots)
0024 {
0025     u64 bitmap;
0026     u32 mask;
0027     int bit, n;
0028 
0029     bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
0030     bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
0031     bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
0032     bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
0033     bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
0034     bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
0035     bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
0036     bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
0037     bitmap >>= 1; /* The first entry is metadata */
0038     bit = 1;
0039     mask = (1 << nr_slots) - 1;
0040 
0041     do {
0042         if (sizeof(unsigned long) == 8)
0043             n = ffz(bitmap);
0044         else
0045             n = ((u32)bitmap) != 0 ?
0046                 ffz((u32)bitmap) :
0047                 ffz((u32)(bitmap >> 32)) + 32;
0048         bitmap >>= n;
0049         bit += n;
0050 
0051         if ((bitmap & mask) == 0) {
0052             if (bit > 64 - nr_slots)
0053                 return -1;
0054             return bit;
0055         }
0056 
0057         n = __ffs(bitmap);
0058         bitmap >>= n;
0059         bit += n;
0060     } while (bitmap);
0061 
0062     return -1;
0063 }
0064 
0065 /*
0066  * Set a number of contiguous bits in the directory block bitmap.
0067  */
0068 static void afs_set_contig_bits(union afs_xdr_dir_block *block,
0069                 int bit, unsigned int nr_slots)
0070 {
0071     u64 mask;
0072 
0073     mask = (1 << nr_slots) - 1;
0074     mask <<= bit;
0075 
0076     block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
0077     block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
0078     block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
0079     block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
0080     block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
0081     block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
0082     block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
0083     block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
0084 }
0085 
0086 /*
0087  * Clear a number of contiguous bits in the directory block bitmap.
0088  */
0089 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
0090                   int bit, unsigned int nr_slots)
0091 {
0092     u64 mask;
0093 
0094     mask = (1 << nr_slots) - 1;
0095     mask <<= bit;
0096 
0097     block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
0098     block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
0099     block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
0100     block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
0101     block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
0102     block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
0103     block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
0104     block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
0105 }
0106 
0107 /*
0108  * Get a new directory folio.
0109  */
0110 static struct folio *afs_dir_get_folio(struct afs_vnode *vnode, pgoff_t index)
0111 {
0112     struct address_space *mapping = vnode->netfs.inode.i_mapping;
0113     struct folio *folio;
0114 
0115     folio = __filemap_get_folio(mapping, index,
0116                     FGP_LOCK | FGP_ACCESSED | FGP_CREAT,
0117                     mapping->gfp_mask);
0118     if (!folio)
0119         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0120     else if (folio && !folio_test_private(folio))
0121         folio_attach_private(folio, (void *)1);
0122 
0123     return folio;
0124 }
0125 
0126 /*
0127  * Scan a directory block looking for a dirent of the right name.
0128  */
0129 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
0130                   unsigned int blocknum)
0131 {
0132     union afs_xdr_dirent *de;
0133     u64 bitmap;
0134     int d, len, n;
0135 
0136     _enter("");
0137 
0138     bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
0139     bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
0140     bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
0141     bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
0142     bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
0143     bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
0144     bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
0145     bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
0146 
0147     for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
0148          d < AFS_DIR_SLOTS_PER_BLOCK;
0149          d++) {
0150         if (!((bitmap >> d) & 1))
0151             continue;
0152         de = &block->dirents[d];
0153         if (de->u.valid != 1)
0154             continue;
0155 
0156         /* The block was NUL-terminated by afs_dir_check_page(). */
0157         len = strlen(de->u.name);
0158         if (len == name->len &&
0159             memcmp(de->u.name, name->name, name->len) == 0)
0160             return d;
0161 
0162         n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
0163         n /= AFS_DIR_DIRENT_SIZE;
0164         d += n - 1;
0165     }
0166 
0167     return -1;
0168 }
0169 
0170 /*
0171  * Initialise a new directory block.  Note that block 0 is special and contains
0172  * some extra metadata.
0173  */
0174 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
0175                 union afs_xdr_dir_block *block, int block_num)
0176 {
0177     memset(block, 0, sizeof(*block));
0178     block->hdr.npages = htons(1);
0179     block->hdr.magic = AFS_DIR_MAGIC;
0180     block->hdr.bitmap[0] = 1;
0181 
0182     if (block_num == 0) {
0183         block->hdr.bitmap[0] = 0xff;
0184         block->hdr.bitmap[1] = 0x1f;
0185         memset(block->meta.alloc_ctrs,
0186                AFS_DIR_SLOTS_PER_BLOCK,
0187                sizeof(block->meta.alloc_ctrs));
0188         meta->meta.alloc_ctrs[0] =
0189             AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
0190     }
0191 
0192     if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
0193         meta->meta.alloc_ctrs[block_num] =
0194             AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
0195 }
0196 
0197 /*
0198  * Edit a directory's file data to add a new directory entry.  Doing this after
0199  * create, mkdir, symlink, link or rename if the data version number is
0200  * incremented by exactly one avoids the need to re-download the entire
0201  * directory contents.
0202  *
0203  * The caller must hold the inode locked.
0204  */
0205 void afs_edit_dir_add(struct afs_vnode *vnode,
0206               struct qstr *name, struct afs_fid *new_fid,
0207               enum afs_edit_dir_reason why)
0208 {
0209     union afs_xdr_dir_block *meta, *block;
0210     union afs_xdr_dirent *de;
0211     struct folio *folio0, *folio;
0212     unsigned int need_slots, nr_blocks, b;
0213     pgoff_t index;
0214     loff_t i_size;
0215     int slot;
0216 
0217     _enter(",,{%d,%s},", name->len, name->name);
0218 
0219     i_size = i_size_read(&vnode->netfs.inode);
0220     if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
0221         (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
0222         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0223         return;
0224     }
0225 
0226     folio0 = afs_dir_get_folio(vnode, 0);
0227     if (!folio0) {
0228         _leave(" [fgp]");
0229         return;
0230     }
0231 
0232     /* Work out how many slots we're going to need. */
0233     need_slots = afs_dir_calc_slots(name->len);
0234 
0235     meta = kmap_local_folio(folio0, 0);
0236     if (i_size == 0)
0237         goto new_directory;
0238     nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
0239 
0240     /* Find a block that has sufficient slots available.  Each folio
0241      * contains two or more directory blocks.
0242      */
0243     for (b = 0; b < nr_blocks + 1; b++) {
0244         /* If the directory extended into a new folio, then we need to
0245          * tack a new folio on the end.
0246          */
0247         index = b / AFS_DIR_BLOCKS_PER_PAGE;
0248         if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
0249             goto error;
0250         if (index >= folio_nr_pages(folio0)) {
0251             folio = afs_dir_get_folio(vnode, index);
0252             if (!folio)
0253                 goto error;
0254         } else {
0255             folio = folio0;
0256         }
0257 
0258         block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));
0259 
0260         /* Abandon the edit if we got a callback break. */
0261         if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
0262             goto invalidated;
0263 
0264         _debug("block %u: %2u %3u %u",
0265                b,
0266                (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
0267                ntohs(block->hdr.npages),
0268                ntohs(block->hdr.magic));
0269 
0270         /* Initialise the block if necessary. */
0271         if (b == nr_blocks) {
0272             _debug("init %u", b);
0273             afs_edit_init_block(meta, block, b);
0274             afs_set_i_size(vnode, (b + 1) * AFS_DIR_BLOCK_SIZE);
0275         }
0276 
0277         /* Only lower dir blocks have a counter in the header. */
0278         if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
0279             meta->meta.alloc_ctrs[b] >= need_slots) {
0280             /* We need to try and find one or more consecutive
0281              * slots to hold the entry.
0282              */
0283             slot = afs_find_contig_bits(block, need_slots);
0284             if (slot >= 0) {
0285                 _debug("slot %u", slot);
0286                 goto found_space;
0287             }
0288         }
0289 
0290         kunmap_local(block);
0291         if (folio != folio0) {
0292             folio_unlock(folio);
0293             folio_put(folio);
0294         }
0295     }
0296 
0297     /* There are no spare slots of sufficient size, yet the operation
0298      * succeeded.  Download the directory again.
0299      */
0300     trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
0301     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0302     goto out_unmap;
0303 
0304 new_directory:
0305     afs_edit_init_block(meta, meta, 0);
0306     i_size = AFS_DIR_BLOCK_SIZE;
0307     afs_set_i_size(vnode, i_size);
0308     slot = AFS_DIR_RESV_BLOCKS0;
0309     folio = folio0;
0310     block = kmap_local_folio(folio, 0);
0311     nr_blocks = 1;
0312     b = 0;
0313 
0314 found_space:
0315     /* Set the dirent slot. */
0316     trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
0317                new_fid->vnode, new_fid->unique, name->name);
0318     de = &block->dirents[slot];
0319     de->u.valid = 1;
0320     de->u.unused[0] = 0;
0321     de->u.hash_next = 0; // TODO: Really need to maintain this
0322     de->u.vnode = htonl(new_fid->vnode);
0323     de->u.unique    = htonl(new_fid->unique);
0324     memcpy(de->u.name, name->name, name->len + 1);
0325     de->u.name[name->len] = 0;
0326 
0327     /* Adjust the bitmap. */
0328     afs_set_contig_bits(block, slot, need_slots);
0329     kunmap_local(block);
0330     if (folio != folio0) {
0331         folio_unlock(folio);
0332         folio_put(folio);
0333     }
0334 
0335     /* Adjust the allocation counter. */
0336     if (b < AFS_DIR_BLOCKS_WITH_CTR)
0337         meta->meta.alloc_ctrs[b] -= need_slots;
0338 
0339     inode_inc_iversion_raw(&vnode->netfs.inode);
0340     afs_stat_v(vnode, n_dir_cr);
0341     _debug("Insert %s in %u[%u]", name->name, b, slot);
0342 
0343 out_unmap:
0344     kunmap_local(meta);
0345     folio_unlock(folio0);
0346     folio_put(folio0);
0347     _leave("");
0348     return;
0349 
0350 invalidated:
0351     trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
0352     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0353     kunmap_local(block);
0354     if (folio != folio0) {
0355         folio_unlock(folio);
0356         folio_put(folio);
0357     }
0358     goto out_unmap;
0359 
0360 error:
0361     trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
0362     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0363     goto out_unmap;
0364 }
0365 
0366 /*
0367  * Edit a directory's file data to remove a new directory entry.  Doing this
0368  * after unlink, rmdir or rename if the data version number is incremented by
0369  * exactly one avoids the need to re-download the entire directory contents.
0370  *
0371  * The caller must hold the inode locked.
0372  */
0373 void afs_edit_dir_remove(struct afs_vnode *vnode,
0374              struct qstr *name, enum afs_edit_dir_reason why)
0375 {
0376     union afs_xdr_dir_block *meta, *block;
0377     union afs_xdr_dirent *de;
0378     struct folio *folio0, *folio;
0379     unsigned int need_slots, nr_blocks, b;
0380     pgoff_t index;
0381     loff_t i_size;
0382     int slot;
0383 
0384     _enter(",,{%d,%s},", name->len, name->name);
0385 
0386     i_size = i_size_read(&vnode->netfs.inode);
0387     if (i_size < AFS_DIR_BLOCK_SIZE ||
0388         i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
0389         (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
0390         clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0391         return;
0392     }
0393     nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
0394 
0395     folio0 = afs_dir_get_folio(vnode, 0);
0396     if (!folio0) {
0397         _leave(" [fgp]");
0398         return;
0399     }
0400 
0401     /* Work out how many slots we're going to discard. */
0402     need_slots = afs_dir_calc_slots(name->len);
0403 
0404     meta = kmap_local_folio(folio0, 0);
0405 
0406     /* Find a block that has sufficient slots available.  Each folio
0407      * contains two or more directory blocks.
0408      */
0409     for (b = 0; b < nr_blocks; b++) {
0410         index = b / AFS_DIR_BLOCKS_PER_PAGE;
0411         if (index >= folio_nr_pages(folio0)) {
0412             folio = afs_dir_get_folio(vnode, index);
0413             if (!folio)
0414                 goto error;
0415         } else {
0416             folio = folio0;
0417         }
0418 
0419         block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));
0420 
0421         /* Abandon the edit if we got a callback break. */
0422         if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
0423             goto invalidated;
0424 
0425         if (b > AFS_DIR_BLOCKS_WITH_CTR ||
0426             meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
0427             slot = afs_dir_scan_block(block, name, b);
0428             if (slot >= 0)
0429                 goto found_dirent;
0430         }
0431 
0432         kunmap_local(block);
0433         if (folio != folio0) {
0434             folio_unlock(folio);
0435             folio_put(folio);
0436         }
0437     }
0438 
0439     /* Didn't find the dirent to clobber.  Download the directory again. */
0440     trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
0441                0, 0, 0, 0, name->name);
0442     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0443     goto out_unmap;
0444 
0445 found_dirent:
0446     de = &block->dirents[slot];
0447 
0448     trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
0449                ntohl(de->u.vnode), ntohl(de->u.unique),
0450                name->name);
0451 
0452     memset(de, 0, sizeof(*de) * need_slots);
0453 
0454     /* Adjust the bitmap. */
0455     afs_clear_contig_bits(block, slot, need_slots);
0456     kunmap_local(block);
0457     if (folio != folio0) {
0458         folio_unlock(folio);
0459         folio_put(folio);
0460     }
0461 
0462     /* Adjust the allocation counter. */
0463     if (b < AFS_DIR_BLOCKS_WITH_CTR)
0464         meta->meta.alloc_ctrs[b] += need_slots;
0465 
0466     inode_set_iversion_raw(&vnode->netfs.inode, vnode->status.data_version);
0467     afs_stat_v(vnode, n_dir_rm);
0468     _debug("Remove %s from %u[%u]", name->name, b, slot);
0469 
0470 out_unmap:
0471     kunmap_local(meta);
0472     folio_unlock(folio0);
0473     folio_put(folio0);
0474     _leave("");
0475     return;
0476 
0477 invalidated:
0478     trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
0479                0, 0, 0, 0, name->name);
0480     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0481     kunmap_local(block);
0482     if (folio != folio0) {
0483         folio_unlock(folio);
0484         folio_put(folio);
0485     }
0486     goto out_unmap;
0487 
0488 error:
0489     trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
0490                0, 0, 0, 0, name->name);
0491     clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
0492     goto out_unmap;
0493 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!