inode.c

lustre 1.6.5 source code

/*
 *    This Cplant(TM) source code is the property of Sandia National
 *    Laboratories.
 *
 *    This Cplant(TM) source code is copyrighted by Sandia National
 *    Laboratories.
 *
 *    The redistribution of this Cplant(TM) source code is subject to the
 *    terms of the GNU Lesser General Public License
 *    (see cit/LGPL or http://www.gnu.org/licenses/lgpl.html)
 *
 *    Cplant(TM) Copyright 1998-2006 Sandia Corporation. 
 *    Under the terms of Contract DE-AC04-94AL85000, there is a non-exclusive
 *    license for use of this work by or on behalf of the US Government.
 *    Export of this program may require a license from the United States
 *    Government.
 */

/*
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * Questions or comments about this library should be sent to:
 *
 * Lee Ward
 * Sandia National Laboratories, New Mexico
 * P.O. Box 5800
 * Albuquerque, NM 87185-1110
 *
 * [e-mail]
 */

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/queue.h>

#include "sysio.h"
#include "fs.h"
#include "mount.h"
#include "inode.h"
#include "dev.h"

/*
 * Support for path and index nodes.
 */

/*
 * Size of all names bucket-hash table.
 */
#ifndef NAMES_TABLE_LEN
#define NAMES_TABLE_LEN		251
#endif

/*
 * Desired i-nodes cache size is MAX_INODES_MULTIPLIER times the number
 * of slots in the names hash table.
 */
#define MAX_INODES_MULTIPLIER	3

/*
 * Active i-nodes in the system and the number of same.
 */
struct inodes_head _sysio_inodes;
static size_t n_inodes = 0;
/*
 * Desired number of active i-nodes.
 */
static size_t max_inodes = (MAX_INODES_MULTIPLIER * NAMES_TABLE_LEN);

/*
 * System table for rapid access to component names.
 */
static LIST_HEAD(, pnode_base) names[NAMES_TABLE_LEN];
/*
 * Number of names tracked by the system.
 */
static size_t n_names = 0;
/*
 * Desired number of base path nodes to maintain.
 */
static size_t max_names = (2 * NAMES_TABLE_LEN);

/*
 * Number of pnodes to grab per memory allocation when filling the
 * free list.
 */
#define PNODES_PER_CHUNK ((8 * 1024) / sizeof(struct pnode) - 2)

#ifdef ZERO_SUM_MEMORY
/*
 * Allocation information for pnodes bulk allocation.
 */
struct pnodes_block {
	LIST_ENTRY(pnodes_block) pnblk_links;
	struct pnode pnblk_nodes[PNODES_PER_CHUNK];
};

static LIST_HEAD( ,pnodes_block) pnblocks;
#endif

/*
 * List of all path-nodes (aliases) referenced by any tree.
 */
struct pnodes_head _sysio_pnodes;

/*
 * Free path-nodes -- Not referenced by any tree for fas reuse.
 */
static LIST_HEAD( ,pnode) free_pnodes;

/*
 * The system root -- Aka `/'.
 */
struct pnode *_sysio_root = NULL;

/*
 * Initialize path and i-node support. Must be called before any other
 * routine in this module.
 */
int
_sysio_i_init()
{
	unsigned i;

	TAILQ_INIT(&_sysio_inodes);

	for (i = 0; i < NAMES_TABLE_LEN; i++)
		LIST_INIT(&names[i]);

#ifdef ZERO_SUM_MEMORY
	LIST_INIT(&pnblocks);
#endif
	TAILQ_INIT(&_sysio_pnodes);
	LIST_INIT(&free_pnodes);

	return 0;
}

/*
 * Garbage-collect idle i-nodes. We try to keep resource use limited to
 * MAX_INODES_MULTIPLIER * max_names.
 */
static void
i_reclaim()
{
	struct inode *next, *ino;
	size_t	t;

	/*
	 * I just can't figure out a good way to reclaim these well without
	 * getting really fancy and using complex algorithms. The
	 * base nodes hold references on them for a long time and then
	 * release them. Those will age to the front of the queue and
	 * we have to skip over them. Oh well...
	 */
	t = MAX_INODES_MULTIPLIER * max_names;
	if (max_inodes < t) {
		/*
		 * Oops. Nope. We want more inodes than names entries.
		 */
		max_inodes = t;
		return;
	}
	next = _sysio_inodes.tqh_first;
	if (!next)
		return;
	t = max_inodes / 2;
	do {
		ino = next;
		next = ino->i_nodes.tqe_next;
		if (ino->i_ref || ino->i_immune)
			continue;
		_sysio_i_gone(ino);
	} while (next && n_inodes > t);

	if (n_inodes > t)
		max_inodes += t;
}

static unsigned
hash(struct file_identifier *fid)
{
	size_t	n;
	unsigned char *ucp;
	unsigned hkey;

	n = fid->fid_len;
	ucp = fid->fid_data;
	hkey = 0;
	do {
		hkey <<= 1;
		hkey += *ucp++;
	} while (--n);
	return hkey;
}

/*
 * Allocate and initialize a new i-node. Returned i-node is referenced.
 *
 * NB: The passed file identifier is not copied. It is, therefor, up to the
 * caller to assure that the value is static until the inode is destroyed.
 */
struct inode *
_sysio_i_new(struct filesys *fs,
	     struct file_identifier *fid,
	     struct intnl_stat *stat,
	     unsigned immunity,
	     struct inode_ops *ops,
	     void *private)
{
	struct inode *ino;
	struct itable_entry *head;
	struct inode_ops operations;

	if (n_inodes > max_inodes) {
		/*
		 * Try to limit growth.
		 */
		i_reclaim();
	}

	ino = malloc(sizeof(struct inode));
	if (!ino)
		return NULL;
	ino->i_ops = *ops;
	operations = *ops;
	if (S_ISBLK(stat->st_mode) ||
	    S_ISCHR(stat->st_mode) ||
	    S_ISFIFO(stat->st_mode)) {
		struct inode_ops *o;

		/*
		 * Replace some operations sent with
		 * those from the device table.
		 */
		o = _sysio_dev_lookup(stat->st_mode, stat->st_rdev);
		operations.inop_open = o->inop_open;
		operations.inop_close = o->inop_close;
		operations.inop_read = o->inop_read;
		operations.inop_write = o->inop_write;
		operations.inop_pos = o->inop_pos;
		operations.inop_iodone = o->inop_iodone;
		operations.inop_fcntl = o->inop_fcntl;
		operations.inop_datasync = o->inop_datasync;
		operations.inop_ioctl = o->inop_ioctl;
	}
	I_INIT(ino, fs, stat, &operations, fid, immunity, private);
	ino->i_ref = 1;
	TAILQ_INSERT_TAIL(&_sysio_inodes, ino, i_nodes);
	head = &fs->fs_itbl[hash(fid) % FS_ITBLSIZ];
	LIST_INSERT_HEAD(head, ino, i_link);

	n_inodes++;
	assert(n_inodes);

	return ino;
}

/*
 * Find existing i-node given i-number and pointers to FS record
 * and identifier.
 */
struct inode *
_sysio_i_find(struct filesys *fs, struct file_identifier *fid)
{
	struct inode *ino;
	struct itable_entry *head;

	head = &fs->fs_itbl[hash(fid) % FS_ITBLSIZ];
	/*
	 * Look for existing.
	 */
	for (ino = head->lh_first; ino; ino = ino->i_link.le_next)
		if (ino->i_fid->fid_len == fid->fid_len &&
		    memcmp(ino->i_fid->fid_data,
			   fid->fid_data,
			   fid->fid_len) == 0) {
			I_REF(ino);
			break;
		}

	return ino;
}

/*
 * Force reclaim of idle i-node.
 */
void
_sysio_i_gone(struct inode *ino)
{

	if (ino->i_ref)
		abort();
	if (!ino->i_zombie) 
		LIST_REMOVE(ino, i_link);
	TAILQ_REMOVE(&_sysio_inodes, ino, i_nodes);
	(*ino->i_ops.inop_gone)(ino);
	free(ino);

	assert(n_inodes);
	n_inodes--;
}

/*
 * Stale inode, zombie it and move it out of the way 
 */
void
_sysio_i_undead(struct inode *ino)
{
	
	if (ino->i_zombie)
		return;
	LIST_REMOVE(ino, i_link);
	ino->i_zombie = 1;
}

/*
 * Garbage collect idle path (and base path) nodes tracked by the system.
 */
static void
p_reclaim()
{
	struct pnode *next, *pno;
	size_t	t;

	next = _sysio_pnodes.tqh_first;
	if (!next)
		return;
	t = max_names / 2;
	do {
		pno = next;
		if (pno->p_ref) {
			next = pno->p_nodes.tqe_next;
			continue;
		}
		pno->p_ref++;
		assert(pno->p_ref);
		(void )_sysio_p_prune(pno);
		next = pno->p_nodes.tqe_next;
		assert(pno->p_ref);
		pno->p_ref--;
		if (pno->p_ref)
			continue;
		(void )_sysio_p_prune(pno);
	} while (n_names > t && next);

	if (n_names > t)
		max_names += t;
}

/*
 * Allocate and initialize a new base path node.
 */
struct pnode_base *
_sysio_pb_new(struct qstr *name, struct pnode_base *parent, struct inode *ino)
{
	struct pnode_base *pb;

	if (n_names > max_names) {
		/*
		 * Try to limit growth.
		 */
		p_reclaim();
	}

	pb = malloc(sizeof(struct pnode_base) + name->len);
	if (!pb)
		return NULL;

	pb->pb_name.name = NULL;
	pb->pb_name.len = name->len;
	if (pb->pb_name.len) {
		char	*cp;

		/*
		 * Copy the passed name.
		 *
		 * We have put the space for the name immediately behind
		 * the record in order to maximize spatial locality.
		 */
		cp = (char *)pb + sizeof(struct pnode_base);
		(void )strncpy(cp, name->name, name->len);
		pb->pb_name.name = cp;
		assert(name->hashval);
		pb->pb_name.hashval = name->hashval;
		LIST_INSERT_HEAD(&names[name->hashval % NAMES_TABLE_LEN],
				 pb,
				 pb_names);
	}
	pb->pb_ino = ino;
	LIST_INIT(&pb->pb_children);
	LIST_INIT(&pb->pb_aliases);
	if (parent)
		LIST_INSERT_HEAD(&parent->pb_children, pb, pb_sibs);
	pb->pb_parent = parent;

	n_names++;
	assert(n_names);

	return pb;
}

/*
 * Destroy base path node, releasing resources back to the system.
 *
 * NB: Caller must release the inode referenced by the record.
 */
static void
pb_destroy(struct pnode_base *pb)
{

	assert(n_names);
	n_names--;

	assert(!pb->pb_aliases.lh_first);
	assert(!pb->pb_children.lh_first);
	assert(!pb->pb_ino);
	if (pb->pb_name.len)
		LIST_REMOVE(pb, pb_names);
	if (pb->pb_parent)
		LIST_REMOVE(pb, pb_sibs);

#ifndef NDEBUG
	/*
	 * This can help us catch pb-nodes that are free'd redundantly.
	 */
	pb->pb_name.hashval = 0;
#endif
	free(pb);
}

/*
 * Force reclaim of idle base path node.
 */
void
_sysio_pb_gone(struct pnode_base *pb)
{

	if (pb->pb_ino)
		I_RELE(pb->pb_ino);
	pb->pb_ino = NULL;

	pb_destroy(pb);
}

/*
 * Generate more path (alias) nodes for the fast allocator.
 */
static void
more_pnodes()
{
	size_t	n;
#ifdef ZERO_SUM_MEMORY
	struct pnodes_block *pnblk;
#endif
	struct pnode *pno;

#ifdef ZERO_SUM_MEMORY
	pnblk = malloc(sizeof(struct pnodes_block));
	pno = NULL;
	if (pnblk) {
		LIST_INSERT_HEAD(&pnblocks, pnblk, pnblk_links);
		pno = pnblk->pnblk_nodes;
	}
#else
	pno = malloc(PNODES_PER_CHUNK * sizeof(struct pnode));
#endif
	if (!pno)
		return;
	n = PNODES_PER_CHUNK;
	do {
		LIST_INSERT_HEAD(&free_pnodes, pno, p_links);
		pno++;
	} while (--n);
}