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  * Get a new directory folio.
109  */
afs_dir_get_folio(struct afs_vnode * vnode,pgoff_t index)110 static struct folio *afs_dir_get_folio(struct afs_vnode *vnode, pgoff_t index)
111 {
112 	struct address_space *mapping = vnode->netfs.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  */
afs_dir_scan_block(union afs_xdr_dir_block * block,struct qstr * name,unsigned int blocknum)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  */
afs_edit_init_block(union afs_xdr_dir_block * meta,union afs_xdr_dir_block * block,int block_num)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  */
afs_edit_dir_add(struct afs_vnode * vnode,struct qstr * name,struct afs_fid * new_fid,enum afs_edit_dir_reason why)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->netfs.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->netfs.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  */
afs_edit_dir_remove(struct afs_vnode * vnode,struct qstr * name,enum afs_edit_dir_reason why)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->netfs.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->netfs.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