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->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 */ 130static 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 */ 175static 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 */ 206void 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_file_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 305new_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 315found_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 344out_unmap: 345 kunmap_local(meta); 346 folio_unlock(folio0); 347 folio_put(folio0); 348 _leave(""); 349 return; 350 351invalidated: 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 361error: 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 */ 374void 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_file_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 446found_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 471out_unmap: 472 kunmap_local(meta); 473 folio_unlock(folio0); 474 folio_put(folio0); 475 _leave(""); 476 return; 477 478invalidated: 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 489error: 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} 495