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->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 */ 129 static 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 */ 174 static 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 */ 205 void 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 304 new_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 314 found_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 343 out_unmap: 344 kunmap_local(meta); 345 folio_unlock(folio0); 346 folio_put(folio0); 347 _leave(""); 348 return; 349 350 invalidated: 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 360 error: 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 */ 373 void 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 445 found_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 470 out_unmap: 471 kunmap_local(meta); 472 folio_unlock(folio0); 473 folio_put(folio0); 474 _leave(""); 475 return; 476 477 invalidated: 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 488 error: 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