1 /* AFS filesystem directory editing
3 * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
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.
12 #include <linux/kernel.h>
14 #include <linux/namei.h>
15 #include <linux/pagemap.h>
16 #include <linux/iversion.h>
21 * Find a number of contiguous clear bits in a directory block bitmask.
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.
27 static int afs_find_contig_bits(union afs_xdr_dir_block *block, unsigned int nr_slots)
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 */
43 mask = (1 << nr_slots) - 1;
46 if (sizeof(unsigned long) == 8)
49 n = ((u32)bitmap) != 0 ?
51 ffz((u32)(bitmap >> 32)) + 32;
55 if ((bitmap & mask) == 0) {
56 if (bit > 64 - nr_slots)
70 * Set a number of contiguous bits in the directory block bitmap.
72 static void afs_set_contig_bits(union afs_xdr_dir_block *block,
73 int bit, unsigned int nr_slots)
77 mask = (1 << nr_slots) - 1;
80 block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
81 block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
82 block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
83 block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
84 block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
85 block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
86 block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
87 block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
91 * Clear a number of contiguous bits in the directory block bitmap.
93 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
94 int bit, unsigned int nr_slots)
98 mask = (1 << nr_slots) - 1;
101 block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
102 block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
103 block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
104 block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
105 block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
106 block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
107 block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
108 block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
112 * Scan a directory block looking for a dirent of the right name.
114 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
115 unsigned int blocknum)
117 union afs_xdr_dirent *de;
123 bitmap = (u64)block->hdr.bitmap[0] << 0 * 8;
124 bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
125 bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
126 bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
127 bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
128 bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
129 bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
130 bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
132 for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
133 d < AFS_DIR_SLOTS_PER_BLOCK;
135 if (!((bitmap >> d) & 1))
137 de = &block->dirents[d];
138 if (de->u.valid != 1)
141 /* The block was NUL-terminated by afs_dir_check_page(). */
142 len = strlen(de->u.name);
143 if (len == name->len &&
144 memcmp(de->u.name, name->name, name->len) == 0)
147 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
148 n /= AFS_DIR_DIRENT_SIZE;
156 * Initialise a new directory block. Note that block 0 is special and contains
157 * some extra metadata.
159 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
160 union afs_xdr_dir_block *block, int block_num)
162 memset(block, 0, sizeof(*block));
163 block->hdr.npages = htons(1);
164 block->hdr.magic = AFS_DIR_MAGIC;
165 block->hdr.bitmap[0] = 1;
167 if (block_num == 0) {
168 block->hdr.bitmap[0] = 0xff;
169 block->hdr.bitmap[1] = 0x1f;
170 memset(block->meta.alloc_ctrs,
171 AFS_DIR_SLOTS_PER_BLOCK,
172 sizeof(block->meta.alloc_ctrs));
173 meta->meta.alloc_ctrs[0] =
174 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
177 if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
178 meta->meta.alloc_ctrs[block_num] =
179 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
183 * Edit a directory's file data to add a new directory entry. Doing this after
184 * create, mkdir, symlink, link or rename if the data version number is
185 * incremented by exactly one avoids the need to re-download the entire
186 * directory contents.
188 * The caller must hold the inode locked.
190 void afs_edit_dir_add(struct afs_vnode *vnode,
191 struct qstr *name, struct afs_fid *new_fid,
192 enum afs_edit_dir_reason why)
194 union afs_xdr_dir_block *meta, *block;
195 struct afs_xdr_dir_page *meta_page, *dir_page;
196 union afs_xdr_dirent *de;
197 struct page *page0, *page;
198 unsigned int need_slots, nr_blocks, b;
204 _enter(",,{%d,%s},", name->len, name->name);
206 i_size = i_size_read(&vnode->vfs_inode);
207 if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
208 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
209 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
213 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
214 page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
216 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
221 /* Work out how many slots we're going to need. */
222 need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
223 need_slots /= AFS_DIR_DIRENT_SIZE;
225 meta_page = kmap(page0);
226 meta = &meta_page->blocks[0];
229 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
231 /* Find a block that has sufficient slots available. Each VM page
232 * contains two or more directory blocks.
234 for (b = 0; b < nr_blocks + 1; b++) {
235 /* If the directory extended into a new page, then we need to
236 * tack a new page on the end.
238 index = b / AFS_DIR_BLOCKS_PER_PAGE;
241 dir_page = meta_page;
243 if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
245 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
246 page = find_or_create_page(vnode->vfs_inode.i_mapping,
250 if (!PagePrivate(page)) {
251 set_page_private(page, 1);
252 SetPagePrivate(page);
254 dir_page = kmap(page);
257 /* Abandon the edit if we got a callback break. */
258 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
261 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
263 _debug("block %u: %2u %3u %u",
265 (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
266 ntohs(block->hdr.npages),
267 ntohs(block->hdr.magic));
269 /* Initialise the block if necessary. */
270 if (b == nr_blocks) {
271 _debug("init %u", b);
272 afs_edit_init_block(meta, block, b);
273 i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
276 /* Only lower dir pages have a counter in the header. */
277 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
278 meta->meta.alloc_ctrs[b] >= need_slots) {
279 /* We need to try and find one or more consecutive
280 * slots to hold the entry.
282 slot = afs_find_contig_bits(block, need_slots);
284 _debug("slot %u", slot);
296 /* There are no spare slots of sufficient size, yet the operation
297 * succeeded. Download the directory again.
299 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
300 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
304 afs_edit_init_block(meta, meta, 0);
305 i_size = AFS_DIR_BLOCK_SIZE;
306 i_size_write(&vnode->vfs_inode, i_size);
307 slot = AFS_DIR_RESV_BLOCKS0;
314 /* Set the dirent slot. */
315 trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
316 new_fid->vnode, new_fid->unique, name->name);
317 de = &block->dirents[slot];
320 de->u.hash_next = 0; // TODO: Really need to maintain this
321 de->u.vnode = htonl(new_fid->vnode);
322 de->u.unique = htonl(new_fid->unique);
323 memcpy(de->u.name, name->name, name->len + 1);
324 de->u.name[name->len] = 0;
326 /* Adjust the bitmap. */
327 afs_set_contig_bits(block, slot, need_slots);
334 /* Adjust the allocation counter. */
335 if (b < AFS_DIR_BLOCKS_WITH_CTR)
336 meta->meta.alloc_ctrs[b] -= need_slots;
338 inode_inc_iversion_raw(&vnode->vfs_inode);
339 afs_stat_v(vnode, n_dir_cr);
340 _debug("Insert %s in %u[%u]", name->name, b, slot);
350 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
351 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
359 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
360 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
365 * Edit a directory's file data to remove a new directory entry. Doing this
366 * after unlink, rmdir or rename if the data version number is incremented by
367 * exactly one avoids the need to re-download the entire directory contents.
369 * The caller must hold the inode locked.
371 void afs_edit_dir_remove(struct afs_vnode *vnode,
372 struct qstr *name, enum afs_edit_dir_reason why)
374 struct afs_xdr_dir_page *meta_page, *dir_page;
375 union afs_xdr_dir_block *meta, *block;
376 union afs_xdr_dirent *de;
377 struct page *page0, *page;
378 unsigned int need_slots, nr_blocks, b;
383 _enter(",,{%d,%s},", name->len, name->name);
385 i_size = i_size_read(&vnode->vfs_inode);
386 if (i_size < AFS_DIR_BLOCK_SIZE ||
387 i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
388 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
389 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
392 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
394 page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
396 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
401 /* Work out how many slots we're going to discard. */
402 need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
403 need_slots /= AFS_DIR_DIRENT_SIZE;
405 meta_page = kmap(page0);
406 meta = &meta_page->blocks[0];
408 /* Find a page that has sufficient slots available. Each VM page
409 * contains two or more directory blocks.
411 for (b = 0; b < nr_blocks; b++) {
412 index = b / AFS_DIR_BLOCKS_PER_PAGE;
414 page = find_lock_page(vnode->vfs_inode.i_mapping, index);
417 dir_page = kmap(page);
420 dir_page = meta_page;
423 /* Abandon the edit if we got a callback break. */
424 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
427 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
429 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
430 meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
431 slot = afs_dir_scan_block(block, name, b);
443 /* Didn't find the dirent to clobber. Download the directory again. */
444 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
445 0, 0, 0, 0, name->name);
446 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
450 de = &block->dirents[slot];
452 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
453 ntohl(de->u.vnode), ntohl(de->u.unique),
456 memset(de, 0, sizeof(*de) * need_slots);
458 /* Adjust the bitmap. */
459 afs_clear_contig_bits(block, slot, need_slots);
466 /* Adjust the allocation counter. */
467 if (b < AFS_DIR_BLOCKS_WITH_CTR)
468 meta->meta.alloc_ctrs[b] += need_slots;
470 inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
471 afs_stat_v(vnode, n_dir_rm);
472 _debug("Remove %s from %u[%u]", name->name, b, slot);
482 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
483 0, 0, 0, 0, name->name);
484 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
493 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
494 0, 0, 0, 0, name->name);
495 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);