[linux-2.6-block.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 (dhowells@redhat.com)
 */

#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, before, after;

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

	before = *(u64 *)block->hdr.bitmap;

	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);

	after = *(u64 *)block->hdr.bitmap;
}

/*
 * 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, before, after;

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

	before = *(u64 *)block->hdr.bitmap;

	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);

	after = *(u64 *)block->hdr.bitmap;
}

/*
 * 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;
	struct afs_xdr_dir_page *meta_page, *dir_page;
	union afs_xdr_dirent *de;
	struct page *page0, *page;
	unsigned int need_slots, nr_blocks, b;
	pgoff_t index;
	loff_t i_size;
	gfp_t gfp;
	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;
	}

	gfp = vnode->vfs_inode.i_mapping->gfp_mask;
	page0 = find_or_create_page(vnode->vfs_inode.i_mapping, 0, gfp);
	if (!page0) {
		clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
		_leave(" [fgp]");
		return;
	}

	/* Work out how many slots we're going to need. */
	need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
	need_slots /= AFS_DIR_DIRENT_SIZE;

	meta_page = kmap(page0);
	meta = &meta_page->blocks[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 VM page
	 * contains two or more directory blocks.
	 */
	for (b = 0; b < nr_blocks + 1; b++) {
		/* If the directory extended into a new page, then we need to
		 * tack a new page on the end.
		 */
		index = b / AFS_DIR_BLOCKS_PER_PAGE;
		if (index == 0) {
			page = page0;
			dir_page = meta_page;
		} else {
			if (nr_blocks >= AFS_DIR_MAX_BLOCKS)
				goto error;
			gfp = vnode->vfs_inode.i_mapping->gfp_mask;
			page = find_or_create_page(vnode->vfs_inode.i_mapping,
						   index, gfp);
			if (!page)
				goto error;
			if (!PagePrivate(page)) {
				set_page_private(page, 1);
				SetPagePrivate(page);
			}
			dir_page = kmap(page);
		}

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

		block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];

		_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);
			i_size_write(&vnode->vfs_inode, (b + 1) * AFS_DIR_BLOCK_SIZE);
		}

		/* Only lower dir pages 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;
			}
		}

		if (page != page0) {
			unlock_page(page);
			kunmap(page);
			put_page(page);
		}
	}

	/* 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;
	i_size_write(&vnode->vfs_inode, i_size);
	slot = AFS_DIR_RESV_BLOCKS0;
	page = page0;
	block = meta;
	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);
	if (page != page0) {
		unlock_page(page);
		kunmap(page);
		put_page(page);
	}

	/* 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:
	unlock_page(page0);
	kunmap(page0);
	put_page(page0);
	_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);
	if (page != page0) {
		kunmap(page);
		put_page(page);
	}
	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)
{
	struct afs_xdr_dir_page *meta_page, *dir_page;
	union afs_xdr_dir_block *meta, *block;
	union afs_xdr_dirent *de;
	struct page *page0, *page;
	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;

	page0 = find_lock_page(vnode->vfs_inode.i_mapping, 0);
	if (!page0) {
		clear_bit(AFS_VNODE_DIR_VALID, &vnode->flags);
		_leave(" [fgp]");
		return;
	}

	/* Work out how many slots we're going to discard. */
	need_slots = round_up(12 + name->len + 1 + 4, AFS_DIR_DIRENT_SIZE);
	need_slots /= AFS_DIR_DIRENT_SIZE;

	meta_page = kmap(page0);
	meta = &meta_page->blocks[0];

	/* Find a page that has sufficient slots available.  Each VM page
	 * contains two or more directory blocks.
	 */
	for (b = 0; b < nr_blocks; b++) {
		index = b / AFS_DIR_BLOCKS_PER_PAGE;
		if (index != 0) {
			page = find_lock_page(vnode->vfs_inode.i_mapping, index);
			if (!page)
				goto error;
			dir_page = kmap(page);
		} else {
			page = page0;
			dir_page = meta_page;
		}

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

		block = &dir_page->blocks[b % AFS_DIR_BLOCKS_PER_PAGE];

		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;
		}

		if (page != page0) {
			unlock_page(page);
			kunmap(page);
			put_page(page);
		}
	}

	/* 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);
	if (page != page0) {
		unlock_page(page);
		kunmap(page);
		put_page(page);
	}

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