[linux-2.6-block.git] / fs / afs / dir_edit.c

/* AFS filesystem directory editing
 *
 * Copyright (C) 2018 Red Hat, Inc. All Rights Reserved.
 * Written by David Howells (dhowells@redhat.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public Licence
 * as published by the Free Software Foundation; either version
 * 2 of the Licence, or (at your option) any later version.
 */

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