[linux.git] / fs / afs / dir_edit.c

// SPDX-License-Identifier: GPL-2.0-or-later
/* AFS filesystem directory editing
 *
 * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells ([email protected])
 */

#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/namei.h>
#include <linux/pagemap.h>
#include <linux/iversion.h>
#include "internal.h"
#include "xdr_fs.h"

/*
 * Find a number of contiguous clear bits in a directory block bitmask.
 *
 * There are 64 slots, which means we can load the entire bitmap into a
 * variable.  The first bit doesn't count as it corresponds to the block header
 * slot.  nr_slots is between 1 and 9.
 */
static int afs_find_contig_bits(union afs_xdr_dir_block *block, unsigned int nr_slots)
{
	u64 bitmap;
	u32 mask;
	int bit, n;

	bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
	bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
	bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
	bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
	bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
	bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
	bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
	bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;
	bitmap >>= 1; /* The first entry is metadata */
	bit = 1;
	mask = (1 << nr_slots) - 1;

	do {
		if (sizeof(unsigned long) == 8)
			n = ffz(bitmap);
		else
			n = ((u32)bitmap) != 0 ?
				ffz((u32)bitmap) :
				ffz((u32)(bitmap >> 32)) + 32;
		bitmap >>= n;
		bit += n;

		if ((bitmap & mask) == 0) {
			if (bit > 64 - nr_slots)
				return -1;
			return bit;
		}

		n = __ffs(bitmap);
		bitmap >>= n;
		bit += n;
	} while (bitmap);

	return -1;
}

/*
 * Set a number of contiguous bits in the directory block bitmap.
 */
static void afs_set_contig_bits(union afs_xdr_dir_block *block,
				int bit, unsigned int nr_slots)
{
	u64 mask;

	mask = (1 << nr_slots) - 1;
	mask <<= bit;

	block->hdr.bitmap[0] |= (u8)(mask >> 0 * 8);
	block->hdr.bitmap[1] |= (u8)(mask >> 1 * 8);
	block->hdr.bitmap[2] |= (u8)(mask >> 2 * 8);
	block->hdr.bitmap[3] |= (u8)(mask >> 3 * 8);
	block->hdr.bitmap[4] |= (u8)(mask >> 4 * 8);
	block->hdr.bitmap[5] |= (u8)(mask >> 5 * 8);
	block->hdr.bitmap[6] |= (u8)(mask >> 6 * 8);
	block->hdr.bitmap[7] |= (u8)(mask >> 7 * 8);
}

/*
 * Clear a number of contiguous bits in the directory block bitmap.
 */
static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
				  int bit, unsigned int nr_slots)
{
	u64 mask;

	mask = (1 << nr_slots) - 1;
	mask <<= bit;

	block->hdr.bitmap[0] &= ~(u8)(mask >> 0 * 8);
	block->hdr.bitmap[1] &= ~(u8)(mask >> 1 * 8);
	block->hdr.bitmap[2] &= ~(u8)(mask >> 2 * 8);
	block->hdr.bitmap[3] &= ~(u8)(mask >> 3 * 8);
	block->hdr.bitmap[4] &= ~(u8)(mask >> 4 * 8);
	block->hdr.bitmap[5] &= ~(u8)(mask >> 5 * 8);
	block->hdr.bitmap[6] &= ~(u8)(mask >> 6 * 8);
	block->hdr.bitmap[7] &= ~(u8)(mask >> 7 * 8);
}

/*
 * Get a new directory folio.
 */
static struct folio *afs_dir_get_folio(struct afs_vnode *vnode, pgoff_t index)
{
	struct address_space *mapping = vnode->vfs_inode.i_mapping;
	struct folio *folio;

	folio = __filemap_get_folio(mapping, index,
				    FGP_LOCK | FGP_ACCESSED | FGP_CREAT,
				    mapping->gfp_mask);
	if (!folio)
		clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	else if (folio && !folio_test_private(folio))
		folio_attach_private(folio, (void *)1);

	return folio;
}

/*
 * Scan a directory block looking for a dirent of the right name.
 */
static int afs_dir_scan_block(union afs_xdr_dir_block *block, struct qstr *name,
			      unsigned int blocknum)
{
	union afs_xdr_dirent *de;
	u64 bitmap;
	int d, len, n;

	_enter("");

	bitmap  = (u64)block->hdr.bitmap[0] << 0 * 8;
	bitmap |= (u64)block->hdr.bitmap[1] << 1 * 8;
	bitmap |= (u64)block->hdr.bitmap[2] << 2 * 8;
	bitmap |= (u64)block->hdr.bitmap[3] << 3 * 8;
	bitmap |= (u64)block->hdr.bitmap[4] << 4 * 8;
	bitmap |= (u64)block->hdr.bitmap[5] << 5 * 8;
	bitmap |= (u64)block->hdr.bitmap[6] << 6 * 8;
	bitmap |= (u64)block->hdr.bitmap[7] << 7 * 8;

	for (d = (blocknum == 0 ? AFS_DIR_RESV_BLOCKS0 : AFS_DIR_RESV_BLOCKS);
	     d < AFS_DIR_SLOTS_PER_BLOCK;
	     d++) {
		if (!((bitmap >> d) & 1))
			continue;
		de = &block->dirents[d];
		if (de->u.valid != 1)
			continue;

		/* The block was NUL-terminated by afs_dir_check_page(). */
		len = strlen(de->u.name);
		if (len == name->len &&
		    memcmp(de->u.name, name->name, name->len) == 0)
			return d;

		n = round_up(12 + len + 1 + 4, AFS_DIR_DIRENT_SIZE);
		n /= AFS_DIR_DIRENT_SIZE;
		d += n - 1;
	}

	return -1;
}

/*
 * Initialise a new directory block.  Note that block 0 is special and contains
 * some extra metadata.
 */
static void afs_edit_init_block(union afs_xdr_dir_block *meta,
				union afs_xdr_dir_block *block, int block_num)
{
	memset(block, 0, sizeof(*block));
	block->hdr.npages = htons(1);
	block->hdr.magic = AFS_DIR_MAGIC;
	block->hdr.bitmap[0] = 1;

	if (block_num == 0) {
		block->hdr.bitmap[0] = 0xff;
		block->hdr.bitmap[1] = 0x1f;
		memset(block->meta.alloc_ctrs,
		       AFS_DIR_SLOTS_PER_BLOCK,
		       sizeof(block->meta.alloc_ctrs));
		meta->meta.alloc_ctrs[0] =
			AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS0;
	}

	if (block_num < AFS_DIR_BLOCKS_WITH_CTR)
		meta->meta.alloc_ctrs[block_num] =
			AFS_DIR_SLOTS_PER_BLOCK - AFS_DIR_RESV_BLOCKS;
}

/*
 * Edit a directory's file data to add a new directory entry.  Doing this after
 * create, mkdir, symlink, link or rename if the data version number is
 * incremented by exactly one avoids the need to re-download the entire
 * directory contents.
 *
 * The caller must hold the inode locked.
 */
void afs_edit_dir_add(struct afs_vnode *vnode,
		      struct qstr *name, struct afs_fid *new_fid,
		      enum afs_edit_dir_reason why)
{
	union afs_xdr_dir_block *meta, *block;
	union afs_xdr_dirent *de;
	struct folio *folio0, *folio;
	unsigned int need_slots, nr_blocks, b;
	pgoff_t index;
	loff_t i_size;
	int slot;

	_enter(",,{%d,%s},", name->len, name->name);

	i_size = i_size_read(&vnode->vfs_inode);
	if (i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
	    (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
		clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
		return;
	}

	folio0 = afs_dir_get_folio(vnode, 0);
	if (!folio0) {
		_leave(" [fgp]");
		return;
	}

	/* Work out how many slots we're going to need. */
	need_slots = afs_dir_calc_slots(name->len);

	meta = kmap_local_folio(folio0, 0);
	if (i_size == 0)
		goto new_directory;
	nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;

	/* Find a block that has sufficient slots available.  Each folio
	 * contains two or more directory blocks.
	 */
	for (b = 0; b < nr_blocks + 1; b++) {
		/* If the directory extended into a new folio, then we need to
		 * tack a new folio on the end.
		 */
		index = b / AFS_DIR_BLOCKS_PER_PAGE;
		if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
			goto error;
		if (index >= folio_nr_pages(folio0)) {
			folio = afs_dir_get_folio(vnode, index);
			if (!folio)
				goto error;
		} else {
			folio = folio0;
		}

		block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));

		/* Abandon the edit if we got a callback break. */
		if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
			goto invalidated;

		_debug("block %u: %2u %3u %u",
		       b,
		       (b < AFS_DIR_BLOCKS_WITH_CTR) ? meta->meta.alloc_ctrs[b] : 99,
		       ntohs(block->hdr.npages),
		       ntohs(block->hdr.magic));

		/* Initialise the block if necessary. */
		if (b == nr_blocks) {
			_debug("init %u", b);
			afs_edit_init_block(meta, block, b);
			afs_set_i_size(vnode, (b + 1) * AFS_DIR_BLOCK_SIZE);
		}

		/* Only lower dir blocks have a counter in the header. */
		if (b >= AFS_DIR_BLOCKS_WITH_CTR ||
		    meta->meta.alloc_ctrs[b] >= need_slots) {
			/* We need to try and find one or more consecutive
			 * slots to hold the entry.
			 */
			slot = afs_find_contig_bits(block, need_slots);
			if (slot >= 0) {
				_debug("slot %u", slot);
				goto found_space;
			}
		}

		kunmap_local(block);
		if (folio != folio0) {
			folio_unlock(folio);
			folio_put(folio);
		}
	}

	/* There are no spare slots of sufficient size, yet the operation
	 * succeeded.  Download the directory again.
	 */
	trace_afs_edit_dir(vnode, why, afs_edit_dir_create_nospc, 0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	goto out_unmap;

new_directory:
	afs_edit_init_block(meta, meta, 0);
	i_size = AFS_DIR_BLOCK_SIZE;
	afs_set_i_size(vnode, i_size);
	slot = AFS_DIR_RESV_BLOCKS0;
	folio = folio0;
	block = kmap_local_folio(folio, 0);
	nr_blocks = 1;
	b = 0;

found_space:
	/* Set the dirent slot. */
	trace_afs_edit_dir(vnode, why, afs_edit_dir_create, b, slot,
			   new_fid->vnode, new_fid->unique, name->name);
	de = &block->dirents[slot];
	de->u.valid	= 1;
	de->u.unused[0]	= 0;
	de->u.hash_next	= 0; // TODO: Really need to maintain this
	de->u.vnode	= htonl(new_fid->vnode);
	de->u.unique	= htonl(new_fid->unique);
	memcpy(de->u.name, name->name, name->len + 1);
	de->u.name[name->len] = 0;

	/* Adjust the bitmap. */
	afs_set_contig_bits(block, slot, need_slots);
	kunmap_local(block);
	if (folio != folio0) {
		folio_unlock(folio);
		folio_put(folio);
	}

	/* Adjust the allocation counter. */
	if (b < AFS_DIR_BLOCKS_WITH_CTR)
		meta->meta.alloc_ctrs[b] -= need_slots;

	inode_inc_iversion_raw(&vnode->vfs_inode);
	afs_stat_v(vnode, n_dir_cr);
	_debug("Insert %s in %u[%u]", name->name, b, slot);

out_unmap:
	kunmap_local(meta);
	folio_unlock(folio0);
	folio_put(folio0);
	_leave("");
	return;

invalidated:
	trace_afs_edit_dir(vnode, why, afs_edit_dir_create_inval, 0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	kunmap_local(block);
	if (folio != folio0) {
		folio_unlock(folio);
		folio_put(folio);
	}
	goto out_unmap;

error:
	trace_afs_edit_dir(vnode, why, afs_edit_dir_create_error, 0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	goto out_unmap;
}

/*
 * Edit a directory's file data to remove a new directory entry.  Doing this
 * after unlink, rmdir or rename if the data version number is incremented by
 * exactly one avoids the need to re-download the entire directory contents.
 *
 * The caller must hold the inode locked.
 */
void afs_edit_dir_remove(struct afs_vnode *vnode,
			 struct qstr *name, enum afs_edit_dir_reason why)
{
	union afs_xdr_dir_block *meta, *block;
	union afs_xdr_dirent *de;
	struct folio *folio0, *folio;
	unsigned int need_slots, nr_blocks, b;
	pgoff_t index;
	loff_t i_size;
	int slot;

	_enter(",,{%d,%s},", name->len, name->name);

	i_size = i_size_read(&vnode->vfs_inode);
	if (i_size < AFS_DIR_BLOCK_SIZE ||
	    i_size > AFS_DIR_BLOCK_SIZE * AFS_DIR_MAX_BLOCKS ||
	    (i_size & (AFS_DIR_BLOCK_SIZE - 1))) {
		clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
		return;
	}
	nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;

	folio0 = afs_dir_get_folio(vnode, 0);
	if (!folio0) {
		_leave(" [fgp]");
		return;
	}

	/* Work out how many slots we're going to discard. */
	need_slots = afs_dir_calc_slots(name->len);

	meta = kmap_local_folio(folio0, 0);

	/* Find a block that has sufficient slots available.  Each folio
	 * contains two or more directory blocks.
	 */
	for (b = 0; b < nr_blocks; b++) {
		index = b / AFS_DIR_BLOCKS_PER_PAGE;
		if (index >= folio_nr_pages(folio0)) {
			folio = afs_dir_get_folio(vnode, index);
			if (!folio)
				goto error;
		} else {
			folio = folio0;
		}

		block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));

		/* Abandon the edit if we got a callback break. */
		if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
			goto invalidated;

		if (b > AFS_DIR_BLOCKS_WITH_CTR ||
		    meta->meta.alloc_ctrs[b] <= AFS_DIR_SLOTS_PER_BLOCK - 1 - need_slots) {
			slot = afs_dir_scan_block(block, name, b);
			if (slot >= 0)
				goto found_dirent;
		}

		kunmap_local(block);
		if (folio != folio0) {
			folio_unlock(folio);
			folio_put(folio);
		}
	}

	/* Didn't find the dirent to clobber.  Download the directory again. */
	trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_noent,
			   0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	goto out_unmap;

found_dirent:
	de = &block->dirents[slot];

	trace_afs_edit_dir(vnode, why, afs_edit_dir_delete, b, slot,
			   ntohl(de->u.vnode), ntohl(de->u.unique),
			   name->name);

	memset(de, 0, sizeof(*de) * need_slots);

	/* Adjust the bitmap. */
	afs_clear_contig_bits(block, slot, need_slots);
	kunmap_local(block);
	if (folio != folio0) {
		folio_unlock(folio);
		folio_put(folio);
	}

	/* Adjust the allocation counter. */
	if (b < AFS_DIR_BLOCKS_WITH_CTR)
		meta->meta.alloc_ctrs[b] += need_slots;

	inode_set_iversion_raw(&vnode->vfs_inode, vnode->status.data_version);
	afs_stat_v(vnode, n_dir_rm);
	_debug("Remove %s from %u[%u]", name->name, b, slot);

out_unmap:
	kunmap_local(meta);
	folio_unlock(folio0);
	folio_put(folio0);
	_leave("");
	return;

invalidated:
	trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_inval,
			   0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	kunmap_local(block);
	if (folio != folio0) {
		folio_unlock(folio);
		folio_put(folio);
	}
	goto out_unmap;

error:
	trace_afs_edit_dir(vnode, why, afs_edit_dir_delete_error,
			   0, 0, 0, 0, name->name);
	clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
	goto out_unmap;
}
Commit	Line	Data
b4d0d230	1	// SPDX-License-Identifier: GPL-2.0-or-later
63a4681f DH	2	/* AFS filesystem directory editing
	3	*
	4	* Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
	5	* Written by David Howells ([email protected])
63a4681f DH	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	*/
	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	*/
	68	static void afs_set_contig_bits(union afs_xdr_dir_block *block,
	69	int bit, unsigned int nr_slots)
70	{
51590df4	71	u64 mask;
63a4681f DH	72
	73	mask = (1 << nr_slots) - 1;
	74	mask <<= bit;
	75
63a4681f DH	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);
63a4681f DH	84	}
	85
	86	/*
	87	* Clear a number of contiguous bits in the directory block bitmap.
	88	*/
	89	static void afs_clear_contig_bits(union afs_xdr_dir_block *block,
	90	int bit, unsigned int nr_slots)
	91	{
51590df4	92	u64 mask;
63a4681f DH	93
	94	mask = (1 << nr_slots) - 1;
	95	mask <<= bit;
	96
63a4681f DH	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);
63a4681f DH	105	}
63a4681f DH	106
255ed636 DH	107	/*
	108	* Get a new directory folio.
	109	*/
	110	static struct folio afs_dir_get_folio(struct afs_vnode vnode, pgoff_t index)
	111	{
	112	struct address_space *mapping = vnode->vfs_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
63a4681f DH	126	/*
	127	* Scan a directory block looking for a dirent of the right name.
	128	*/
	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	*/
	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	*/
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;
63a4681f	210	union afs_xdr_dirent *de;
255ed636	211	struct folio folio0, folio;
63a4681f DH	212	unsigned int need_slots, nr_blocks, b;
	213	pgoff_t index;
	214	loff_t i_size;
63a4681f DH	215	int slot;
	216
	217	_enter(",,{%d,%s},", name->len, name->name);
	218
	219	i_size = i_size_read(&vnode->vfs_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
255ed636 DH	226	folio0 = afs_dir_get_folio(vnode, 0);
255ed636 DH	227	if (!folio0) {
63a4681f DH	228	_leave(" [fgp]");
	229	return;
	230	}
	231
	232	/* Work out how many slots we're going to need. */
366911cd	233	need_slots = afs_dir_calc_slots(name->len);
63a4681f	234
255ed636	235	meta = kmap_local_folio(folio0, 0);
63a4681f DH	236	if (i_size == 0)
	237	goto new_directory;
	238	nr_blocks = i_size / AFS_DIR_BLOCK_SIZE;
	239
255ed636	240	/* Find a block that has sufficient slots available. Each folio
63a4681f DH	241	* contains two or more directory blocks.
	242	*/
	243	for (b = 0; b < nr_blocks + 1; b++) {
255ed636 DH	244	/* If the directory extended into a new folio, then we need to
255ed636 DH	245	* tack a new folio on the end.
63a4681f DH	246	*/
63a4681f DH	247	index = b / AFS_DIR_BLOCKS_PER_PAGE;
255ed636 DH	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)
63a4681f	253	goto error;
255ed636 DH	254	} else {
255ed636 DH	255	folio = folio0;
63a4681f DH	256	}
63a4681f DH	257
255ed636 DH	258	block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));
255ed636 DH	259
63a4681f DH	260	/* Abandon the edit if we got a callback break. */
	261	if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
	262	goto invalidated;
	263
63a4681f DH	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);
9d37e1ca	274	afs_set_i_size(vnode, (b + 1) * AFS_DIR_BLOCK_SIZE);
63a4681f DH	275	}
63a4681f DH	276
255ed636	277	/* Only lower dir blocks have a counter in the header. */
63a4681f DH	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
255ed636 DH	290	kunmap_local(block);
	291	if (folio != folio0) {
	292	folio_unlock(folio);
	293	folio_put(folio);
63a4681f DH	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;
9d37e1ca	307	afs_set_i_size(vnode, i_size);
63a4681f	308	slot = AFS_DIR_RESV_BLOCKS0;
255ed636 DH	309	folio = folio0;
255ed636 DH	310	block = kmap_local_folio(folio, 0);
63a4681f DH	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);
255ed636 DH	329	kunmap_local(block);
	330	if (folio != folio0) {
	331	folio_unlock(folio);
	332	folio_put(folio);
63a4681f DH	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->vfs_inode);
	340	afs_stat_v(vnode, n_dir_cr);
	341	_debug("Insert %s in %u[%u]", name->name, b, slot);
	342
	343	out_unmap:
255ed636 DH	344	kunmap_local(meta);
	345	folio_unlock(folio0);
	346	folio_put(folio0);
63a4681f DH	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);
255ed636 DH	353	kunmap_local(block);
	354	if (folio != folio0) {
	355	folio_unlock(folio);
	356	folio_put(folio);
63a4681f DH	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	*/
	373	void afs_edit_dir_remove(struct afs_vnode *vnode,
	374	struct qstr *name, enum afs_edit_dir_reason why)
	375	{
63a4681f DH	376	union afs_xdr_dir_block meta, block;
63a4681f DH	377	union afs_xdr_dirent *de;
255ed636	378	struct folio folio0, folio;
63a4681f DH	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->vfs_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
255ed636 DH	395	folio0 = afs_dir_get_folio(vnode, 0);
255ed636 DH	396	if (!folio0) {
63a4681f DH	397	_leave(" [fgp]");
	398	return;
	399	}
	400
	401	/* Work out how many slots we're going to discard. */
366911cd	402	need_slots = afs_dir_calc_slots(name->len);
63a4681f	403
255ed636	404	meta = kmap_local_folio(folio0, 0);
63a4681f	405
255ed636	406	/* Find a block that has sufficient slots available. Each folio
63a4681f DH	407	* contains two or more directory blocks.
	408	*/
	409	for (b = 0; b < nr_blocks; b++) {
	410	index = b / AFS_DIR_BLOCKS_PER_PAGE;
255ed636 DH	411	if (index >= folio_nr_pages(folio0)) {
	412	folio = afs_dir_get_folio(vnode, index);
	413	if (!folio)
63a4681f	414	goto error;
63a4681f	415	} else {
255ed636	416	folio = folio0;
63a4681f DH	417	}
63a4681f DH	418
255ed636 DH	419	block = kmap_local_folio(folio, b * AFS_DIR_BLOCK_SIZE - folio_file_pos(folio));
255ed636 DH	420
63a4681f DH	421	/* Abandon the edit if we got a callback break. */
	422	if (!test_bit(AFS_VNODE_DIR_VALID, &vnode->flags))
	423	goto invalidated;
	424
63a4681f DH	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
255ed636 DH	432	kunmap_local(block);
	433	if (folio != folio0) {
	434	folio_unlock(folio);
	435	folio_put(folio);
63a4681f DH	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);
255ed636 DH	456	kunmap_local(block);
	457	if (folio != folio0) {
	458	folio_unlock(folio);
	459	folio_put(folio);
63a4681f DH	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->vfs_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:
255ed636 DH	471	kunmap_local(meta);
	472	folio_unlock(folio0);
	473	folio_put(folio0);
63a4681f DH	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);
255ed636 DH	481	kunmap_local(block);
	482	if (folio != folio0) {
	483	folio_unlock(folio);
	484	folio_put(folio);
63a4681f DH	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	}