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 */
afs_find_contig_bits(union afs_xdr_dir_block * block,unsigned int nr_slots)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 */
afs_set_contig_bits(union afs_xdr_dir_block * block,int bit,unsigned int nr_slots)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 */
afs_clear_contig_bits(union afs_xdr_dir_block * block,int bit,unsigned int nr_slots)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 * Scan a directory block looking for a dirent of the right name.
109 */
afs_dir_scan_block(union afs_xdr_dir_block * block,struct qstr * name,unsigned int blocknum)110 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
111 unsigned int blocknum)
112 {
113 union afs_xdr_dirent *de;
114 u64 bitmap;
115 int d, len, n;
116
117 _enter("");
118
119 bitmap = (u64)block->hdr.bitmap[0] << 0 * 8;
120 bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
121 bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
122 bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
123 bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
124 bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
125 bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
126 bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
127
128 for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
129 d < AFS_DIR_SLOTS_PER_BLOCK;
130 d++) {
131 if (!((bitmap >> d) & 1))
132 continue;
133 de = &block->dirents[d];
134 if (de->u.valid != 1)
135 continue;
136
137 /* The block was NUL-terminated by afs_dir_check_page(). */
138 len = strlen(de->u.name);
139 if (len == name->len &&
140 memcmp(de->u.name, name->name, name->len) == 0)
141 return d;
142
143 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
144 n /= AFS_DIR_DIRENT_SIZE;
145 d += n - 1;
146 }
147
148 return -1;
149 }
150
151 /*
152 * Initialise a new directory block. Note that block 0 is special and contains
153 * some extra metadata.
154 */
afs_edit_init_block(union afs_xdr_dir_block * meta,union afs_xdr_dir_block * block,int block_num)155 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
156 union afs_xdr_dir_block *block, int block_num)
157 {
158 memset(block, 0, sizeof(*block));
159 block->hdr.npages = htons(1);
160 block->hdr.magic = AFS_DIR_MAGIC;
161 block->hdr.bitmap[0] = 1;
162
163 if (block_num == 0) {
164 block->hdr.bitmap[0] = 0xff;
165 block->hdr.bitmap[1] = 0x1f;
166 memset(block->meta.alloc_ctrs,
167 AFS_DIR_SLOTS_PER_BLOCK,
168 sizeof(block->meta.alloc_ctrs));
169 meta->meta.alloc_ctrs[0] =
170 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
171 }
172
173 if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
174 meta->meta.alloc_ctrs[block_num] =
175 AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
176 }
177
178 /*
179 * Edit a directory's file data to add a new directory entry. Doing this after
180 * create, mkdir, symlink, link or rename if the data version number is
181 * incremented by exactly one avoids the need to re-download the entire
182 * directory contents.
183 *
184 * The caller must hold the inode locked.
185 */
afs_edit_dir_add(struct afs_vnode * vnode,struct qstr * name,struct afs_fid * new_fid,enum afs_edit_dir_reason why)186 void afs_edit_dir_add(struct afs_vnode *vnode,
187 struct qstr *name, struct afs_fid *new_fid,
188 enum afs_edit_dir_reason why)
189 {
190 union afs_xdr_dir_block *meta, *block;
191 struct afs_xdr_dir_page *meta_page, *dir_page;
192 union afs_xdr_dirent *de;
193 struct page *page0, *page;
194 unsigned int need_slots, nr_blocks, b;
195 pgoff_t index;
196 loff_t i_size;
197 gfp_t gfp;
198 int slot;
199
200 _enter(",,{%d,%s},", name->len, name->name);
201
202 i_size = i_size_read(&vnode->vfs_inode);
203 if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
204 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
205 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
206 return;
207 }
208
209 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
210 page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
211 if (!page0) {
212 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
213 _leave(" [fgp]");
214 return;
215 }
216
217 /* Work out how many slots we're going to need. */
218 need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
219 need_slots /= AFS_DIR_DIRENT_SIZE;
220
221 meta_page = kmap(page0);
222 meta = &meta_page->blocks[0];
223 if (i_size == 0)
224 goto new_directory;
225 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
226
227 /* Find a block that has sufficient slots available. Each VM page
228 * contains two or more directory blocks.
229 */
230 for (b = 0; b < nr_blocks + 1; b++) {
231 /* If the directory extended into a new page, then we need to
232 * tack a new page on the end.
233 */
234 index = b / AFS_DIR_BLOCKS_PER_PAGE;
235 if (index == 0) {
236 page = page0;
237 dir_page = meta_page;
238 } else {
239 if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
240 goto error;
241 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
242 page = find_or_create_page(vnode->vfs_inode.i_mapping,
243 index, gfp);
244 if (!page)
245 goto error;
246 if (!PagePrivate(page))
247 attach_page_private(page, (void *)1);
248 dir_page = kmap(page);
249 }
250
251 /* Abandon the edit if we got a callback break. */
252 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
253 goto invalidated;
254
255 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
256
257 _debug("block %u: %2u %3u %u",
258 b,
259 (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
260 ntohs(block->hdr.npages),
261 ntohs(block->hdr.magic));
262
263 /* Initialise the block if necessary. */
264 if (b == nr_blocks) {
265 _debug("init %u", b);
266 afs_edit_init_block(meta, block, b);
267 i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
268 }
269
270 /* Only lower dir pages have a counter in the header. */
271 if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
272 meta->meta.alloc_ctrs[b] >= need_slots) {
273 /* We need to try and find one or more consecutive
274 * slots to hold the entry.
275 */
276 slot = afs_find_contig_bits(block, need_slots);
277 if (slot >= 0) {
278 _debug("slot %u", slot);
279 goto found_space;
280 }
281 }
282
283 if (page != page0) {
284 unlock_page(page);
285 kunmap(page);
286 put_page(page);
287 }
288 }
289
290 /* There are no spare slots of sufficient size, yet the operation
291 * succeeded. Download the directory again.
292 */
293 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
294 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
295 goto out_unmap;
296
297 new_directory:
298 afs_edit_init_block(meta, meta, 0);
299 i_size = AFS_DIR_BLOCK_SIZE;
300 i_size_write(&vnode->vfs_inode, i_size);
301 slot = AFS_DIR_RESV_BLOCKS0;
302 page = page0;
303 block = meta;
304 nr_blocks = 1;
305 b = 0;
306
307 found_space:
308 /* Set the dirent slot. */
309 trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
310 new_fid->vnode, new_fid->unique, name->name);
311 de = &block->dirents[slot];
312 de->u.valid = 1;
313 de->u.unused[0] = 0;
314 de->u.hash_next = 0; // TODO: Really need to maintain this
315 de->u.vnode = htonl(new_fid->vnode);
316 de->u.unique = htonl(new_fid->unique);
317 memcpy(de->u.name, name->name, name->len + 1);
318 de->u.name[name->len] = 0;
319
320 /* Adjust the bitmap. */
321 afs_set_contig_bits(block, slot, need_slots);
322 if (page != page0) {
323 unlock_page(page);
324 kunmap(page);
325 put_page(page);
326 }
327
328 /* Adjust the allocation counter. */
329 if (b < AFS_DIR_BLOCKS_WITH_CTR)
330 meta->meta.alloc_ctrs[b] -= need_slots;
331
332 inode_inc_iversion_raw(&vnode->vfs_inode);
333 afs_stat_v(vnode, n_dir_cr);
334 _debug("Insert %s in %u[%u]", name->name, b, slot);
335
336 out_unmap:
337 unlock_page(page0);
338 kunmap(page0);
339 put_page(page0);
340 _leave("");
341 return;
342
343 invalidated:
344 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
345 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
346 if (page != page0) {
347 kunmap(page);
348 put_page(page);
349 }
350 goto out_unmap;
351
352 error:
353 trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
354 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
355 goto out_unmap;
356 }
357
358 /*
359 * Edit a directory's file data to remove a new directory entry. Doing this
360 * after unlink, rmdir or rename if the data version number is incremented by
361 * exactly one avoids the need to re-download the entire directory contents.
362 *
363 * The caller must hold the inode locked.
364 */
afs_edit_dir_remove(struct afs_vnode * vnode,struct qstr * name,enum afs_edit_dir_reason why)365 void afs_edit_dir_remove(struct afs_vnode *vnode,
366 struct qstr *name, enum afs_edit_dir_reason why)
367 {
368 struct afs_xdr_dir_page *meta_page, *dir_page;
369 union afs_xdr_dir_block *meta, *block;
370 union afs_xdr_dirent *de;
371 struct page *page0, *page;
372 unsigned int need_slots, nr_blocks, b;
373 pgoff_t index;
374 loff_t i_size;
375 int slot;
376
377 _enter(",,{%d,%s},", name->len, name->name);
378
379 i_size = i_size_read(&vnode->vfs_inode);
380 if (i_size < AFS_DIR_BLOCK_SIZE ||
381 i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
382 (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
383 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
384 return;
385 }
386 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
387
388 page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
389 if (!page0) {
390 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
391 _leave(" [fgp]");
392 return;
393 }
394
395 /* Work out how many slots we're going to discard. */
396 need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
397 need_slots /= AFS_DIR_DIRENT_SIZE;
398
399 meta_page = kmap(page0);
400 meta = &meta_page->blocks[0];
401
402 /* Find a page that has sufficient slots available. Each VM page
403 * contains two or more directory blocks.
404 */
405 for (b = 0; b < nr_blocks; b++) {
406 index = b / AFS_DIR_BLOCKS_PER_PAGE;
407 if (index != 0) {
408 page = find_lock_page(vnode->vfs_inode.i_mapping, index);
409 if (!page)
410 goto error;
411 dir_page = kmap(page);
412 } else {
413 page = page0;
414 dir_page = meta_page;
415 }
416
417 /* Abandon the edit if we got a callback break. */
418 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
419 goto invalidated;
420
421 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
422
423 if (b > AFS_DIR_BLOCKS_WITH_CTR ||
424 meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
425 slot = afs_dir_scan_block(block, name, b);
426 if (slot >= 0)
427 goto found_dirent;
428 }
429
430 if (page != page0) {
431 unlock_page(page);
432 kunmap(page);
433 put_page(page);
434 }
435 }
436
437 /* Didn't find the dirent to clobber. Download the directory again. */
438 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
439 0, 0, 0, 0, name->name);
440 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
441 goto out_unmap;
442
443 found_dirent:
444 de = &block->dirents[slot];
445
446 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
447 ntohl(de->u.vnode), ntohl(de->u.unique),
448 name->name);
449
450 memset(de, 0, sizeof(*de) * need_slots);
451
452 /* Adjust the bitmap. */
453 afs_clear_contig_bits(block, slot, need_slots);
454 if (page != page0) {
455 unlock_page(page);
456 kunmap(page);
457 put_page(page);
458 }
459
460 /* Adjust the allocation counter. */
461 if (b < AFS_DIR_BLOCKS_WITH_CTR)
462 meta->meta.alloc_ctrs[b] += need_slots;
463
464 inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
465 afs_stat_v(vnode, n_dir_rm);
466 _debug("Remove %s from %u[%u]", name->name, b, slot);
467
468 out_unmap:
469 unlock_page(page0);
470 kunmap(page0);
471 put_page(page0);
472 _leave("");
473 return;
474
475 invalidated:
476 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
477 0, 0, 0, 0, name->name);
478 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
479 if (page != page0) {
480 unlock_page(page);
481 kunmap(page);
482 put_page(page);
483 }
484 goto out_unmap;
485
486 error:
487 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
488 0, 0, 0, 0, name->name);
489 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
490 goto out_unmap;
491 }
492
