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 */
afs_find_contig_bits(union afs_xdr_dir_block * block,unsigned int nr_slots)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 */
afs_set_contig_bits(union afs_xdr_dir_block * block,int bit,unsigned int nr_slots)72 static void afs_set_contig_bits(union afs_xdr_dir_block *block,
73 int bit, unsigned int nr_slots)
74 {
75 u64 mask;
76
77 mask = (1 << nr_slots) - 1;
78 mask <<= bit;
79
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);
88 }
89
90 /*
91 * Clear a number of contiguous bits in the directory block bitmap.
92 */
afs_clear_contig_bits(union afs_xdr_dir_block * block,int bit,unsigned int nr_slots)93 static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
94 int bit, unsigned int nr_slots)
95 {
96 u64 mask;
97
98 mask = (1 << nr_slots) - 1;
99 mask <<= bit;
100
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);
109 }
110
111 /*
112 * Scan a directory block looking for a dirent of the right name.
113 */
afs_dir_scan_block(union afs_xdr_dir_block * block,struct qstr * name,unsigned int blocknum)114 static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
115 unsigned int blocknum)
116 {
117 union afs_xdr_dirent *de;
118 u64 bitmap;
119 int d, len, n;
120
121 _enter("");
122
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;
131
132 for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
133 d < AFS_DIR_SLOTS_PER_BLOCK;
134 d++) {
135 if (!((bitmap >> d) & 1))
136 continue;
137 de = &block->dirents[d];
138 if (de->u.valid != 1)
139 continue;
140
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)
145 return d;
146
147 n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
148 n /= AFS_DIR_DIRENT_SIZE;
149 d += n - 1;
150 }
151
152 return -1;
153 }
154
155 /*
156 * Initialise a new directory block. Note that block 0 is special and contains
157 * some extra metadata.
158 */
afs_edit_init_block(union afs_xdr_dir_block * meta,union afs_xdr_dir_block * block,int block_num)159 static void afs_edit_init_block(union afs_xdr_dir_block *meta,
160 union afs_xdr_dir_block *block, int block_num)
161 {
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;
166
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;
175 }
176
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;
180 }
181
182 /*
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.
187 *
188 * The caller must hold the inode locked.
189 */
afs_edit_dir_add(struct afs_vnode * vnode,struct qstr * name,struct afs_fid * new_fid,enum afs_edit_dir_reason why)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)
193 {
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;
199 pgoff_t index;
200 loff_t i_size;
201 gfp_t gfp;
202 int slot;
203
204 _enter(",,{%d,%s},", name->len, name->name);
205
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);
210 return;
211 }
212
213 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
214 page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
215 if (!page0) {
216 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
217 _leave(" [fgp]");
218 return;
219 }
220
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;
224
225 meta_page = kmap(page0);
226 meta = &meta_page->blocks[0];
227 if (i_size == 0)
228 goto new_directory;
229 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
230
231 /* Find a block that has sufficient slots available. Each VM page
232 * contains two or more directory blocks.
233 */
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.
237 */
238 index = b / AFS_DIR_BLOCKS_PER_PAGE;
239 if (index == 0) {
240 page = page0;
241 dir_page = meta_page;
242 } else {
243 if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
244 goto error;
245 gfp = vnode->vfs_inode.i_mapping->gfp_mask;
246 page = find_or_create_page(vnode->vfs_inode.i_mapping,
247 index, gfp);
248 if (!page)
249 goto error;
250 if (!PagePrivate(page)) {
251 set_page_private(page, 1);
252 SetPagePrivate(page);
253 }
254 dir_page = kmap(page);
255 }
256
257 /* Abandon the edit if we got a callback break. */
258 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
259 goto invalidated;
260
261 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
262
263 _debug("block %u: %2u %3u %u",
264 b,
265 (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
266 ntohs(block->hdr.npages),
267 ntohs(block->hdr.magic));
268
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);
274 }
275
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.
281 */
282 slot = afs_find_contig_bits(block, need_slots);
283 if (slot >= 0) {
284 _debug("slot %u", slot);
285 goto found_space;
286 }
287 }
288
289 if (page != page0) {
290 unlock_page(page);
291 kunmap(page);
292 put_page(page);
293 }
294 }
295
296 /* There are no spare slots of sufficient size, yet the operation
297 * succeeded. Download the directory again.
298 */
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);
301 goto out_unmap;
302
303 new_directory:
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;
308 page = page0;
309 block = meta;
310 nr_blocks = 1;
311 b = 0;
312
313 found_space:
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];
318 de->u.valid = 1;
319 de->u.unused[0] = 0;
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;
325
326 /* Adjust the bitmap. */
327 afs_set_contig_bits(block, slot, need_slots);
328 if (page != page0) {
329 unlock_page(page);
330 kunmap(page);
331 put_page(page);
332 }
333
334 /* Adjust the allocation counter. */
335 if (b < AFS_DIR_BLOCKS_WITH_CTR)
336 meta->meta.alloc_ctrs[b] -= need_slots;
337
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);
341
342 out_unmap:
343 unlock_page(page0);
344 kunmap(page0);
345 put_page(page0);
346 _leave("");
347 return;
348
349 invalidated:
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);
352 if (page != page0) {
353 kunmap(page);
354 put_page(page);
355 }
356 goto out_unmap;
357
358 error:
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);
361 goto out_unmap;
362 }
363
364 /*
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.
368 *
369 * The caller must hold the inode locked.
370 */
afs_edit_dir_remove(struct afs_vnode * vnode,struct qstr * name,enum afs_edit_dir_reason why)371 void afs_edit_dir_remove(struct afs_vnode *vnode,
372 struct qstr *name, enum afs_edit_dir_reason why)
373 {
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;
379 pgoff_t index;
380 loff_t i_size;
381 int slot;
382
383 _enter(",,{%d,%s},", name->len, name->name);
384
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);
390 return;
391 }
392 nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
393
394 page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
395 if (!page0) {
396 clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
397 _leave(" [fgp]");
398 return;
399 }
400
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;
404
405 meta_page = kmap(page0);
406 meta = &meta_page->blocks[0];
407
408 /* Find a page that has sufficient slots available. Each VM page
409 * contains two or more directory blocks.
410 */
411 for (b = 0; b < nr_blocks; b++) {
412 index = b / AFS_DIR_BLOCKS_PER_PAGE;
413 if (index != 0) {
414 page = find_lock_page(vnode->vfs_inode.i_mapping, index);
415 if (!page)
416 goto error;
417 dir_page = kmap(page);
418 } else {
419 page = page0;
420 dir_page = meta_page;
421 }
422
423 /* Abandon the edit if we got a callback break. */
424 if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
425 goto invalidated;
426
427 block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];
428
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);
432 if (slot >= 0)
433 goto found_dirent;
434 }
435
436 if (page != page0) {
437 unlock_page(page);
438 kunmap(page);
439 put_page(page);
440 }
441 }
442
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);
447 goto out_unmap;
448
449 found_dirent:
450 de = &block->dirents[slot];
451
452 trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
453 ntohl(de->u.vnode), ntohl(de->u.unique),
454 name->name);
455
456 memset(de, 0, sizeof(*de) * need_slots);
457
458 /* Adjust the bitmap. */
459 afs_clear_contig_bits(block, slot, need_slots);
460 if (page != page0) {
461 unlock_page(page);
462 kunmap(page);
463 put_page(page);
464 }
465
466 /* Adjust the allocation counter. */
467 if (b < AFS_DIR_BLOCKS_WITH_CTR)
468 meta->meta.alloc_ctrs[b] += need_slots;
469
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);
473
474 out_unmap:
475 unlock_page(page0);
476 kunmap(page0);
477 put_page(page0);
478 _leave("");
479 return;
480
481 invalidated:
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);
485 if (page != page0) {
486 unlock_page(page);
487 kunmap(page);
488 put_page(page);
489 }
490 goto out_unmap;
491
492 error:
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);
496 goto out_unmap;
497 }
498