head	1.1;
access;
symbols
	LKML-branch:1.1.0.2;
locks; strict;
comment	@# @;


1.1
date	2006.10.24.06.14.17;	author jsipek;	state dead;
branches
	1.1.2.1;
next	;

1.1.2.1
date	2006.10.24.06.14.17;	author jsipek;	state Exp;
branches;
next	1.1.2.2;

1.1.2.2
date	2006.11.07.06.13.33;	author jsipek;	state Exp;
branches;
next	1.1.2.3;

1.1.2.3
date	2006.11.28.08.17.51;	author jsipek;	state Exp;
branches;
next	1.1.2.4;

1.1.2.4
date	2006.11.28.08.30.13;	author jsipek;	state Exp;
branches;
next	1.1.2.5;

1.1.2.5
date	2006.12.01.02.36.12;	author jsipek;	state Exp;
branches;
next	1.1.2.6;

1.1.2.6
date	2006.12.03.21.49.41;	author jsipek;	state Exp;
branches;
next	1.1.2.7;

1.1.2.7
date	2006.12.11.14.23.59;	author jsipek;	state Exp;
branches;
next	1.1.2.8;

1.1.2.8
date	2007.01.04.22.12.00;	author jsipek;	state Exp;
branches;
next	1.1.2.9;

1.1.2.9
date	2007.01.21.23.59.13;	author jsipek;	state Exp;
branches;
next	;


desc
@@


1.1
log
@file readdir was initially added on branch LKML-branch.
@
text
@@


1.1.2.1
log
@Move unionfs specific bits into a subdir
@
text
@a0 309
Unionfs: Readdir state

From: Josef "Jeff" Sipek <jsipek@@cs.sunysb.edu>

This file contains the routines for maintaining readdir state.

Signed-off-by: Josef "Jeff" Sipek <jsipek@@cs.sunysb.edu>
Signed-off-by: David Quigley <dquigley@@fsl.cs.sunysb.edu>
Signed-off-by: Erez Zadok <ezk@@cs.sunysb.edu>

diff -r b360d2c89c11 fs/unionfs/rdstate.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fs/unionfs/rdstate.c	Sat Oct 07 00:32:19 2006 -0400
@@@@ -0,0 +1,295 @@@@
+/*
+ * Copyright (c) 2003-2006 Erez Zadok
+ * Copyright (c) 2003-2006 Charles P. Wright
+ * Copyright (c) 2005-2006 Josef 'Jeff' Sipek
+ * Copyright (c) 2005-2006 Junjiro Okajima
+ * Copyright (c) 2005      Arun M. Krishnakumar
+ * Copyright (c) 2004-2006 David P. Quigley
+ * Copyright (c) 2003-2004 Mohammad Nayyer Zubair
+ * Copyright (c) 2003      Puja Gupta
+ * Copyright (c) 2003      Harikesavan Krishnan
+ * Copyright (c) 2003-2006 Stony Brook University
+ * Copyright (c) 2003-2006 The Research Foundation of State University of New York
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include "union.h"
+
+/* This file contains the routines for maintaining readdir state. */
+/* There are two structures here, rdstate which is a hash table
+ * of the second structure which is a filldir_node. */
+
+/* This is a kmem_cache_t for filldir nodes, because we allocate a lot of them
+ * and they shouldn't waste memory.  If the node has a small name (as defined
+ * by the dentry structure), then we use an inline name to preserve kmalloc
+ * space. */
+static kmem_cache_t *unionfs_filldir_cachep;
+int init_filldir_cache(void)
+{
+	unionfs_filldir_cachep =
+	    kmem_cache_create("unionfs_filldir", sizeof(struct filldir_node), 0,
+			      SLAB_RECLAIM_ACCOUNT, NULL, NULL);
+
+	if (!unionfs_filldir_cachep)
+		return -ENOMEM;
+
+	return 0;
+}
+
+void destroy_filldir_cache(void)
+{
+	if (unionfs_filldir_cachep)
+		kmem_cache_destroy(unionfs_filldir_cachep);
+}
+
+/* This is a tuning parameter that tells us roughly how big to make the
+ * hash table in directory entries per page.  This isn't perfect, but
+ * at least we get a hash table size that shouldn't be too overloaded.
+ * The following averages are based on my home directory.
+ * 14.44693	Overall
+ * 12.29	Single Page Directories
+ * 117.93	Multi-page directories
+ */
+#define DENTPAGE 4096
+#define DENTPERONEPAGE 12
+#define DENTPERPAGE 118
+#define MINHASHSIZE 1
+static int guesstimate_hash_size(struct inode *inode)
+{
+	struct inode *hidden_inode;
+	int bindex;
+	int hashsize = MINHASHSIZE;
+
+	if (itopd(inode)->uii_hashsize > 0)
+		return itopd(inode)->uii_hashsize;
+
+	for (bindex = ibstart(inode); bindex <= ibend(inode); bindex++) {
+		if (!(hidden_inode = itohi_index(inode, bindex)))
+			continue;
+
+		if (hidden_inode->i_size == DENTPAGE) {
+			hashsize += DENTPERONEPAGE;
+		} else {
+			hashsize +=
+			    (hidden_inode->i_size / DENTPAGE) * DENTPERPAGE;
+		}
+	}
+
+	return hashsize;
+}
+
+int init_rdstate(struct file *file)
+{
+	BUG_ON(sizeof(loff_t) != (sizeof(unsigned int) + sizeof(unsigned int)));
+	BUG_ON(ftopd(file)->rdstate != NULL);
+
+	ftopd(file)->rdstate =
+	    alloc_rdstate(file->f_dentry->d_inode, fbstart(file));
+	if (!ftopd(file)->rdstate)
+		return -ENOMEM;
+	return 0;
+}
+
+struct unionfs_dir_state *find_rdstate(struct inode *inode, loff_t fpos)
+{
+	struct unionfs_dir_state *rdstate = NULL;
+	struct list_head *pos;
+
+	spin_lock(&itopd(inode)->uii_rdlock);
+	list_for_each(pos, &itopd(inode)->uii_readdircache) {
+		struct unionfs_dir_state *r =
+		    list_entry(pos, struct unionfs_dir_state, uds_cache);
+		if (fpos == rdstate2offset(r)) {
+			itopd(inode)->uii_rdcount--;
+			list_del(&r->uds_cache);
+			rdstate = r;
+			break;
+		}
+	}
+	spin_unlock(&itopd(inode)->uii_rdlock);
+	return rdstate;
+}
+
+struct unionfs_dir_state *alloc_rdstate(struct inode *inode, int bindex)
+{
+	int i = 0;
+	int hashsize;
+	int mallocsize = sizeof(struct unionfs_dir_state);
+	struct unionfs_dir_state *rdstate;
+
+	hashsize = guesstimate_hash_size(inode);
+	mallocsize += hashsize * sizeof(struct list_head);
+	/* Round it up to the next highest power of two. */
+	mallocsize--;
+	mallocsize |= mallocsize >> 1;
+	mallocsize |= mallocsize >> 2;
+	mallocsize |= mallocsize >> 4;
+	mallocsize |= mallocsize >> 8;
+	mallocsize |= mallocsize >> 16;
+	mallocsize++;
+
+	/* This should give us about 500 entries anyway. */
+	if (mallocsize > PAGE_SIZE)
+		mallocsize = PAGE_SIZE;
+
+	hashsize =
+	    (mallocsize -
+	     sizeof(struct unionfs_dir_state)) / sizeof(struct list_head);
+
+	rdstate = kmalloc(mallocsize, GFP_KERNEL);
+	if (!rdstate)
+		return NULL;
+
+	spin_lock(&itopd(inode)->uii_rdlock);
+	if (itopd(inode)->uii_cookie >= (MAXRDCOOKIE - 1))
+		itopd(inode)->uii_cookie = 1;
+	else
+		itopd(inode)->uii_cookie++;
+
+	rdstate->uds_cookie = itopd(inode)->uii_cookie;
+	spin_unlock(&itopd(inode)->uii_rdlock);
+	rdstate->uds_offset = 1;
+	rdstate->uds_access = jiffies;
+	rdstate->uds_bindex = bindex;
+	rdstate->uds_dirpos = 0;
+	rdstate->uds_hashentries = 0;
+	rdstate->uds_size = hashsize;
+	for (i = 0; i < rdstate->uds_size; i++)
+		INIT_LIST_HEAD(&rdstate->uds_list[i]);
+
+	return rdstate;
+}
+
+static void free_filldir_node(struct filldir_node *node)
+{
+	if (node->namelen >= DNAME_INLINE_LEN_MIN)
+		kfree(node->name);
+	kmem_cache_free(unionfs_filldir_cachep, node);
+}
+
+void free_rdstate(struct unionfs_dir_state *state)
+{
+	struct filldir_node *tmp;
+	int i;
+
+	for (i = 0; i < state->uds_size; i++) {
+		struct list_head *head = &(state->uds_list[i]);
+		struct list_head *pos, *n;
+
+		/* traverse the list and deallocate space */
+		list_for_each_safe(pos, n, head) {
+			tmp = list_entry(pos, struct filldir_node, file_list);
+			list_del(&tmp->file_list);
+			free_filldir_node(tmp);
+		}
+	}
+
+	kfree(state);
+}
+
+struct filldir_node *find_filldir_node(struct unionfs_dir_state *rdstate,
+				       const char *name, int namelen)
+{
+	int index;
+	unsigned int hash;
+	struct list_head *head;
+	struct list_head *pos;
+	struct filldir_node *cursor = NULL;
+	int found = 0;
+
+	BUG_ON(namelen <= 0);
+
+	hash = full_name_hash(name, namelen);
+	index = hash % rdstate->uds_size;
+
+	head = &(rdstate->uds_list[index]);
+	list_for_each(pos, head) {
+		cursor = list_entry(pos, struct filldir_node, file_list);
+
+		if (cursor->namelen == namelen && cursor->hash == hash
+		    && !strncmp(cursor->name, name, namelen)) {
+			/* a duplicate exists, and hence no need to create entry to the list */
+			found = 1;
+			/* if the duplicate is in this branch, then the file system is corrupted. */
+			if (cursor->bindex == rdstate->uds_bindex) {
+				//buf->error = err = -EIO;
+				printk(KERN_DEBUG
+				       "Possible I/O error unionfs_filldir: a file is duplicated in the same branch %d: %s\n",
+				       rdstate->uds_bindex, cursor->name);
+			}
+			break;
+		}
+	}
+
+	if (!found) {
+		cursor = NULL;
+	}
+	return cursor;
+}
+
+inline struct filldir_node *alloc_filldir_node(const char *name, int namelen,
+					       unsigned int hash, int bindex)
+{
+	struct filldir_node *newnode;
+
+	newnode =
+	    (struct filldir_node *)kmem_cache_alloc(unionfs_filldir_cachep,
+						    SLAB_KERNEL);
+	if (!newnode)
+		goto out;
+
+out:
+	return newnode;
+}
+
+int add_filldir_node(struct unionfs_dir_state *rdstate, const char *name,
+		     int namelen, int bindex, int whiteout)
+{
+	struct filldir_node *new;
+	unsigned int hash;
+	int index;
+	int err = 0;
+	struct list_head *head;
+
+	BUG_ON(namelen <= 0);
+
+	hash = full_name_hash(name, namelen);
+	index = hash % rdstate->uds_size;
+	head = &(rdstate->uds_list[index]);
+
+	new = alloc_filldir_node(name, namelen, hash, bindex);
+	if (!new) {
+		err = -ENOMEM;
+		goto out;
+	}
+
+	INIT_LIST_HEAD(&new->file_list);
+	new->namelen = namelen;
+	new->hash = hash;
+	new->bindex = bindex;
+	new->whiteout = whiteout;
+
+	if (namelen < DNAME_INLINE_LEN_MIN) {
+		new->name = new->iname;
+	} else {
+		new->name = kmalloc(namelen + 1, GFP_KERNEL);
+		if (!new->name) {
+			kmem_cache_free(unionfs_filldir_cachep, new);
+			new = NULL;
+			goto out;
+		}
+	}
+
+	memcpy(new->name, name, namelen);
+	new->name[namelen] = '\0';
+
+	rdstate->uds_hashentries++;
+
+	list_add(&(new->file_list), head);
+out:
+	return err;
+}
+
@


1.1.2.2
log
@Git generates slightly different diffs - same information, just little
different
@
text
@d11 3
a13 5
diff --git a/fs/unionfs/rdstate.c b/fs/unionfs/rdstate.c
new file mode 100644
index 0000000..f3d4e9d
--- /dev/null
+++ b/fs/unionfs/rdstate.c
@


1.1.2.3
log
@Collapse unionfs-struct_kmem_cache
@
text
@d14 2
a15 4

diff -r b04a9e0f7c89 fs/unionfs/rdstate.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fs/unionfs/rdstate.c	Tue Nov 28 03:11:04 2006 -0500
d41 5
a45 5
+/* This is a struct kmem_cache for filldir nodes, because we allocate a lot
+ * of them and they shouldn't waste memory.  If the node has a small name
+ * (as defined by the dentry structure), then we use an inline name to
+ * preserve kmalloc space. */
+static struct kmem_cache *unionfs_filldir_cachep;
@


1.1.2.4
log
@Collapsed: struct_path-unionfs unionfs-fix-comments unionfs-kill-wrappers
@
text
@d15 1
a15 1
diff -r c40a33160b7b fs/unionfs/rdstate.c
d17 2
a18 2
+++ b/fs/unionfs/rdstate.c	Tue Nov 28 03:18:27 2006 -0500
@@@@ -0,0 +1,294 @@@@
d236 1
@


1.1.2.5
log
@Remove git crud & nicer makefile
@
text
@d11 4
@


1.1.2.6
log
@Collapsed macro patch into unionfs proper
@
text
@d11 1
a11 1
diff -r a5db3fd894d3 fs/unionfs/rdstate.c
d13 2
a14 2
+++ b/fs/unionfs/rdstate.c	Sun Dec 03 16:38:47 2006 -0500
@@@@ -0,0 +1,282 @@@@
d50 4
a53 1
+	return (unionfs_filldir_cachep ? 0 : -ENOMEM);
d80 2
a81 2
+	if (UNIONFS_I(inode)->hashsize > 0)
+		return UNIONFS_I(inode)->hashsize;
d84 1
a84 1
+		if (!(hidden_inode = unionfs_lower_inode_idx(inode, bindex)))
d87 1
a87 1
+		if (hidden_inode->i_size == DENTPAGE)
d89 4
a92 2
+		else
+			hashsize += (hidden_inode->i_size / DENTPAGE) * DENTPERPAGE;
d101 1
a101 1
+	BUG_ON(UNIONFS_F(file)->rdstate != NULL);
d103 5
a107 4
+	UNIONFS_F(file)->rdstate = alloc_rdstate(file->f_dentry->d_inode,
+						 fbstart(file));
+	
+	return (UNIONFS_F(file)->rdstate ? 0 : -ENOMEM);
d115 2
a116 2
+	spin_lock(&UNIONFS_I(inode)->rdlock);
+	list_for_each(pos, &UNIONFS_I(inode)->readdircache) {
d118 1
a118 1
+		    list_entry(pos, struct unionfs_dir_state, cache);
d120 2
a121 2
+			UNIONFS_I(inode)->rdcount--;
+			list_del(&r->cache);
d126 1
a126 1
+	spin_unlock(&UNIONFS_I(inode)->rdlock);
d152 2
a153 1
+	hashsize = (mallocsize -
d160 3
a162 3
+	spin_lock(&UNIONFS_I(inode)->rdlock);
+	if (UNIONFS_I(inode)->cookie >= (MAXRDCOOKIE - 1))
+		UNIONFS_I(inode)->cookie = 1;
d164 1
a164 1
+		UNIONFS_I(inode)->cookie++;
d166 10
a175 10
+	rdstate->cookie = UNIONFS_I(inode)->cookie;
+	spin_unlock(&UNIONFS_I(inode)->rdlock);
+	rdstate->offset = 1;
+	rdstate->access = jiffies;
+	rdstate->bindex = bindex;
+	rdstate->dirpos = 0;
+	rdstate->hashentries = 0;
+	rdstate->size = hashsize;
+	for (i = 0; i < rdstate->size; i++)
+		INIT_LIST_HEAD(&rdstate->list[i]);
d192 2
a193 2
+	for (i = 0; i < state->size; i++) {
+		struct list_head *head = &(state->list[i]);
d220 1
a220 1
+	index = hash % rdstate->size;
d222 1
a222 1
+	head = &(rdstate->list[index]);
d226 3
a228 4
+		if (cursor->namelen == namelen && cursor->hash == hash &&
+		    !strncmp(cursor->name, name, namelen)) {
+			/* a duplicate exists, and hence no need to create
+			 * entry to the list */
d230 5
a234 8
+
+			/* if the duplicate is in this branch, then the file
+			 * system is corrupted. */
+			if (cursor->bindex == rdstate->bindex) {
+				printk(KERN_DEBUG "Possible I/O error "
+					"unionfs_filldir: a file is duplicated "
+					"in the same branch %d: %s\n",
+					rdstate->bindex, cursor->name);
d240 1
a240 1
+	if (!found)
d242 1
a242 1
+
d249 10
a258 1
+	return kmem_cache_alloc(unionfs_filldir_cachep, SLAB_KERNEL);
d273 2
a274 2
+	index = hash % rdstate->size;
+	head = &(rdstate->list[index]);
d288 1
a288 1
+	if (namelen < DNAME_INLINE_LEN_MIN)
d290 1
a290 1
+	else {
d302 1
a302 1
+	rdstate->hashentries++;
@


1.1.2.7
log
@Folded unionfs-lkml-comments-jan
@
text
@d11 1
a11 1
diff -r f7f702fbcf19 fs/unionfs/rdstate.c
d13 2
a14 2
+++ b/fs/unionfs/rdstate.c	Mon Dec 11 09:06:47 2006 -0500
@@@@ -0,0 +1,288 @@@@
a35 1
+
d37 1
a37 2
+ * of the second structure which is a filldir_node.
+ */
d42 1
a42 2
+ * preserve kmalloc space.
+ */
d44 1
a44 2
+
+int unionfs_init_filldir_cache(void)
d53 1
a53 1
+void unionfs_destroy_filldir_cache(void)
d222 1
a222 2
+			 * entry to the list
+			 */
d226 1
a226 2
+			 * system is corrupted.
+			 */
@


1.1.2.8
log
@2.6.20-rc compile fixes
@
text
@d11 3
a13 5
diff --git a/fs/unionfs/rdstate.c b/fs/unionfs/rdstate.c
new file mode 100644
index 0000000..a970346
--- /dev/null
+++ b/fs/unionfs/rdstate.c
d252 1
a252 1
+	return kmem_cache_alloc(unionfs_filldir_cachep, GFP_KERNEL);
@


1.1.2.9
log
@A. Bunk's patch, more akpm comments, new copyright
@
text
@d13 1
a13 1
index 0000000..7f11ae2
d18 1
a18 1
+ * Copyright (c) 2003-2007 Erez Zadok
d20 1
a20 1
+ * Copyright (c) 2005-2007 Josef 'Jeff' Sipek
d27 2
a28 2
+ * Copyright (c) 2003-2007 Stony Brook University
+ * Copyright (c) 2003-2007 The Research Foundation of State University of New York
@


