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