xnu-792.10.96.tar.gz

[apple/xnu.git] / bsd / miscfs / devfs / devfs_tree.c

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

/*
 * Copyright 1997,1998 Julian Elischer.  All rights reserved.
 * julian@freebsd.org
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *  1. Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright notice,
 *     this list of conditions and the following disclaimer in the documentation
 *     and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE HOLDER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * 
 * devfs_tree.c
 */

/*
 * HISTORY
 *  Dieter Siegmund (dieter@apple.com) Thu Apr  8 14:08:19 PDT 1999
 *  - removed mounting of "hidden" mountpoint
 *  - fixed problem in which devnode->dn_vn pointer was not
 *    updated with the vnode returned from checkalias()
 *  - replaced devfs_vntodn() with a macro VTODN()
 *  - rewrote dev_finddir() to not use recursion
 *  - added locking to avoid data structure corruption (DEVFS_(UN)LOCK())
 *  Dieter Siegmund (dieter@apple.com) Wed Jul 14 13:37:59 PDT 1999
 *  - fixed problem with devfs_dntovn() checking the v_id against the
 *    value cached in the device node; a union mount on top of us causes
 *    the v_id to get incremented thus, we would end up returning a new
 *    vnode instead of the existing one that has the mounted_here
 *    field filled in; the net effect was that the filesystem mounted
 *    on top of us would never show up
 *  - added devfs_stats to store how many data structures are actually 
 *    allocated
 */

/* SPLIT_DEVS means each devfs uses a different devnode for the same device */
/* Otherwise the same device always ends up at the same vnode even if  */
/* reached througgh a different devfs instance. The practical difference */
/* is that with the same vnode, chmods and chowns show up on all instances of */
/* a device. (etc) */

#define SPLIT_DEVS 1 /* maybe make this an option */
/*#define SPLIT_DEVS 1*/

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/conf.h>
#include <sys/malloc.h>
#include <sys/mount_internal.h>
#include <sys/proc.h>
#include <sys/vnode.h>
#include <stdarg.h>

#include "devfs.h"
#include "devfsdefs.h"

static void	devfs_release_busy(devnode_t *);
static void	dev_free_hier(devdirent_t *);
static int	devfs_propogate(devdirent_t *, devdirent_t *);
static int	dev_finddir(char *, devnode_t *, int, devnode_t **);
static int	dev_dup_entry(devnode_t *, devdirent_t *, devdirent_t **, struct devfsmount *);


lck_grp_t	* devfs_lck_grp;
lck_grp_attr_t	* devfs_lck_grp_attr;
lck_attr_t	* devfs_lck_attr;
lck_mtx_t  	  devfs_mutex;

devdirent_t *		dev_root = NULL; 	/* root of backing tree */
struct devfs_stats	devfs_stats;		/* hold stats */

#ifdef HIDDEN_MOUNTPOINT
static struct mount *devfs_hidden_mount;
#endif /* HIDDEN_MOINTPOINT */

static int devfs_ready = 0;

#define NOCREATE	FALSE
#define CREATE		TRUE

/*
 * Set up the root directory node in the backing plane
 * This is happenning before the vfs system has been
 * set up yet, so be careful about what we reference..
 * Notice that the ops are by indirection.. as they haven't
 * been set up yet!
 * DEVFS has a hidden mountpoint that is used as the anchor point
 * for the internal 'blueprint' version of the dev filesystem tree.
 */
/*proto*/
int
devfs_sinit(void)
{
    int error;

    devfs_lck_grp_attr = lck_grp_attr_alloc_init();
	devfs_lck_grp = lck_grp_alloc_init("devfs_lock", devfs_lck_grp_attr);

	devfs_lck_attr = lck_attr_alloc_init();

	lck_mtx_init(&devfs_mutex, devfs_lck_grp, devfs_lck_attr);

	DEVFS_LOCK();
        error = dev_add_entry("root", NULL, DEV_DIR, NULL, NULL, NULL, &dev_root);
	DEVFS_UNLOCK();

	if (error) {
	    printf("devfs_sinit: dev_add_entry failed ");
	    return (ENOTSUP);
	}
#ifdef HIDDEN_MOUNTPOINT
	MALLOC(devfs_hidden_mount, struct mount *, sizeof(struct mount),
	       M_MOUNT, M_WAITOK);
	bzero(devfs_hidden_mount,sizeof(struct mount));
	mount_lock_init(devfs_hidden_mount);
	TAILQ_INIT(&devfs_hidden_mount->mnt_vnodelist);
	TAILQ_INIT(&devfs_hidden_mount->mnt_workerqueue);
	TAILQ_INIT(&devfs_hidden_mount->mnt_newvnodes);

	/* Initialize the default IO constraints */
	mp->mnt_maxreadcnt = mp->mnt_maxwritecnt = MAXPHYS;
	mp->mnt_segreadcnt = mp->mnt_segwritecnt = 32;

	devfs_mount(devfs_hidden_mount,"dummy",NULL,NULL,NULL);
	dev_root->de_dnp->dn_dvm 
	    = (struct devfsmount *)devfs_hidden_mount->mnt_data;
#endif /* HIDDEN_MOUNTPOINT */
	devfs_ready = 1;
	return (0);
}

/***********************************************************************\
*************************************************************************
*	Routines used to find our way to a point in the tree		*
*************************************************************************
\***********************************************************************/



/***************************************************************
 * Search down the linked list off a dir to find "name"		
 * return the devnode_t * for that node.
 *
 * called with DEVFS_LOCK held
 ***************************************************************/
devdirent_t *
dev_findname(devnode_t * dir, char *name)
{
	devdirent_t * newfp;
	if (dir->dn_type != DEV_DIR) return 0;/*XXX*/ /* printf?*/

	if (name[0] == '.')
	{
		if(name[1] == 0)
		{
			return dir->dn_typeinfo.Dir.myname;
		}
		if((name[1] == '.') && (name[2] == 0))
		{
			/* for root, .. == . */
			return dir->dn_typeinfo.Dir.parent->dn_typeinfo.Dir.myname;
		}
	}
	newfp = dir->dn_typeinfo.Dir.dirlist;

	while(newfp)
	{
		if(!(strcmp(name,newfp->de_name)))
			return newfp;
		newfp = newfp->de_next;
	}
	return NULL;
}

/***********************************************************************
 * Given a starting node (0 for root) and a pathname, return the node	
 * for the end item on the path. It MUST BE A DIRECTORY. If the 'CREATE'
 * option is true, then create any missing nodes in the path and create
 * and return the final node as well.					
 * This is used to set up a directory, before making nodes in it..
 *
 * called with DEVFS_LOCK held
 ***********************************************************************/
static int
dev_finddir(char * path, 
	    devnode_t * dirnode,
	    int create, 
	    devnode_t * * dn_pp)
{
	devnode_t *	dnp = NULL;
	int		error = 0;
	char *		scan;


	if (!dirnode) /* dirnode == NULL means start at root */
	    dirnode = dev_root->de_dnp;

	if (dirnode->dn_type != DEV_DIR) 
	    return ENOTDIR;

	if (strlen(path) > (DEVMAXPATHSIZE - 1)) 
	    return ENAMETOOLONG;

	scan = path;

	while (*scan == '/') 
	    scan++;

	*dn_pp = NULL;

	while (1) {
	    char		component[DEVMAXPATHSIZE];
	    devdirent_t *	dirent_p;
	    char * 		start;

	    if (*scan == 0) { 
		/* we hit the end of the string, we're done */
		*dn_pp = dirnode;
		break;
	    }
	    start = scan;
	    while (*scan != '/' && *scan)
		scan++;

	    strncpy(component, start, scan - start);
		component[ scan - start ] = '\0';
	    if (*scan == '/')
		scan++;

	    dirent_p = dev_findname(dirnode, component);
	    if (dirent_p) {
		dnp = dirent_p->de_dnp;
		if (dnp->dn_type != DEV_DIR) {
		    error = ENOTDIR;
		    break;
		}
	    }
	    else {
		if (!create) {
		    error = ENOENT;
		    break;
		}
		error = dev_add_entry(component, dirnode, 
				       DEV_DIR, NULL, NULL, NULL, &dirent_p);
		if (error)
		    break;
		dnp = dirent_p->de_dnp;
		devfs_propogate(dirnode->dn_typeinfo.Dir.myname, dirent_p);
	    }
	    dirnode = dnp; /* continue relative to this directory */
	}
	return (error);
}


/***********************************************************************
 * Add a new NAME element to the devfs
 * If we're creating a root node, then dirname is NULL
 * Basically this creates a new namespace entry for the device node
 *
 * Creates a name node, and links it to the supplied node
 *
 * called with DEVFS_LOCK held
 ***********************************************************************/
int
dev_add_name(char * name, devnode_t * dirnode, __unused devdirent_t * back, 
    devnode_t * dnp, devdirent_t * *dirent_pp)
{
	devdirent_t * 	dirent_p = NULL;

	if(dirnode != NULL ) {
		if(dirnode->dn_type != DEV_DIR) return(ENOTDIR);
	
		if( dev_findname(dirnode,name))
			return(EEXIST);
	}
	/*
	 * make sure the name is legal
	 * slightly misleading in the case of NULL
	 */
	if (!name || (strlen(name) > (DEVMAXNAMESIZE - 1)))
	    return (ENAMETOOLONG);

	/*
	 * Allocate and fill out a new directory entry 
	 */
	MALLOC(dirent_p, devdirent_t *, sizeof(devdirent_t), 
	       M_DEVFSNAME, M_WAITOK);
	if (!dirent_p) {
	    return ENOMEM;
	}
	bzero(dirent_p,sizeof(devdirent_t));

	/* inherrit our parent's mount info */ /*XXX*/
	/* a kludge but.... */
	if(dirnode && ( dnp->dn_dvm == NULL)) {
		dnp->dn_dvm = dirnode->dn_dvm;
		/* if(!dnp->dn_dvm) printf("parent had null dvm "); */
	}

	/*
	 * Link the two together
	 * include the implicit link in the count of links to the devnode..
	 * this stops it from being accidentally freed later.
	 */
	dirent_p->de_dnp = dnp;
	dnp->dn_links++ ; /* implicit from our own name-node */

	/* 
	 * Make sure that we can find all the links that reference a node
	 * so that we can get them all if we need to zap the node.
	 */
	if(dnp->dn_linklist) {
		dirent_p->de_nextlink = dnp->dn_linklist;
		dirent_p->de_prevlinkp = dirent_p->de_nextlink->de_prevlinkp;
		dirent_p->de_nextlink->de_prevlinkp = &(dirent_p->de_nextlink);
		*dirent_p->de_prevlinkp = dirent_p;
	} else {
		dirent_p->de_nextlink = dirent_p;
		dirent_p->de_prevlinkp = &(dirent_p->de_nextlink);
	}
	dnp->dn_linklist = dirent_p;

	/*
	 * If the node is a directory, then we need to handle the 
	 * creation of the .. link.
	 * A NULL dirnode indicates a root node, so point to ourself.
	 */
	if(dnp->dn_type == DEV_DIR) {
		dnp->dn_typeinfo.Dir.myname = dirent_p;
		/*
		 * If we are unlinking from an old dir, decrement its links
		 * as we point our '..' elsewhere
		 * Note: it's up to the calling code to remove the 
		 * us from the original directory's list
		 */
		if(dnp->dn_typeinfo.Dir.parent) {
			dnp->dn_typeinfo.Dir.parent->dn_links--;
		}
	 	if(dirnode) {
			dnp->dn_typeinfo.Dir.parent = dirnode;
		} else {
			dnp->dn_typeinfo.Dir.parent = dnp;
		}
		dnp->dn_typeinfo.Dir.parent->dn_links++; /* account for the new '..' */
	}

	/*
	 * put the name into the directory entry.
	 */
	strcpy(dirent_p->de_name, name);


	/*
	 * Check if we are not making a root node..
	 * (i.e. have parent)
	 */
	if(dirnode) {
		/*
	 	 * Put it on the END of the linked list of directory entries
	 	 */
		dirent_p->de_parent = dirnode; /* null for root */
		dirent_p->de_prevp = dirnode->dn_typeinfo.Dir.dirlast;
		dirent_p->de_next = *(dirent_p->de_prevp); /* should be NULL */ 
							/*right?*/
		*(dirent_p->de_prevp) = dirent_p;
		dirnode->dn_typeinfo.Dir.dirlast = &(dirent_p->de_next);
		dirnode->dn_typeinfo.Dir.entrycount++;
		dirnode->dn_len += strlen(name) + 8;/*ok, ok?*/
	}

	*dirent_pp = dirent_p;
	DEVFS_INCR_ENTRIES();
	return 0 ;
}


/***********************************************************************
 * Add a new element to the devfs plane.
 *
 * Creates a new dev_node to go with it if the prototype should not be
 * reused. (Is a DIR, or we select SPLIT_DEVS at compile time)
 * typeinfo gives us info to make our node if we don't have a prototype.
 * If typeinfo is null and proto exists, then the typeinfo field of
 * the proto is used intead in the CREATE case.
 * note the 'links' count is 0 (except if a dir)
 * but it is only cleared on a transition
 * so this is ok till we link it to something
 * Even in SPLIT_DEVS mode,
 * if the node already exists on the wanted plane, just return it
 *
 * called with DEVFS_LOCK held
***********************************************************************/
int
dev_add_node(int entrytype, devnode_type_t * typeinfo, devnode_t * proto,
	     devnode_t * *dn_pp, struct devfsmount *dvm)
{
	devnode_t *	dnp = NULL;

#if defined SPLIT_DEVS
	/*
	 * If we have a prototype, then check if there is already a sibling
	 * on the mount plane we are looking at, if so, just return it.
	 */
	if (proto) {
		dnp = proto->dn_nextsibling;
		while( dnp != proto) {
			if (dnp->dn_dvm == dvm) {
				*dn_pp = dnp;
				return (0);
			}
			dnp = dnp->dn_nextsibling;
		}
		if (typeinfo == NULL)
			typeinfo = &(proto->dn_typeinfo);
	}
#else	/* SPLIT_DEVS */
	if ( proto ) {
		switch (proto->type) {
			case DEV_BDEV:
			case DEV_CDEV:
				*dn_pp = proto;
				return 0;
		}
	}
#endif	/* SPLIT_DEVS */
	MALLOC(dnp, devnode_t *, sizeof(devnode_t), M_DEVFSNODE, M_WAITOK);
	if (!dnp) {
	    return ENOMEM;
	}

	/*
	 * If we have a proto, that means that we are duplicating some
	 * other device, which can only happen if we are not at the back plane
	 */
	if (proto) {
		bcopy(proto, dnp, sizeof(devnode_t));
		dnp->dn_links = 0;
		dnp->dn_linklist = NULL;
		dnp->dn_vn = NULL;
		dnp->dn_len = 0;
		/* add to END of siblings list */
		dnp->dn_prevsiblingp = proto->dn_prevsiblingp;
		*(dnp->dn_prevsiblingp) = dnp;
		dnp->dn_nextsibling = proto;
		proto->dn_prevsiblingp = &(dnp->dn_nextsibling);
	} else {
	        struct timeval tv;

		/* 
		 * We have no prototype, so start off with a clean slate
		 */
		microtime(&tv);
		bzero(dnp, sizeof(devnode_t));
		dnp->dn_type = entrytype;
		dnp->dn_nextsibling = dnp;
		dnp->dn_prevsiblingp = &(dnp->dn_nextsibling);
		dnp->dn_atime.tv_sec = tv.tv_sec;
		dnp->dn_mtime.tv_sec = tv.tv_sec;
		dnp->dn_ctime.tv_sec = tv.tv_sec;
	}
	dnp->dn_dvm = dvm;

	/*
	 * fill out the dev node according to type
	 */
	switch(entrytype) {
	case DEV_DIR:
		/*
		 * As it's a directory, make sure
		 * it has a null entries list
		 */
		dnp->dn_typeinfo.Dir.dirlast = &(dnp->dn_typeinfo.Dir.dirlist);
		dnp->dn_typeinfo.Dir.dirlist = (devdirent_t *)0;
		dnp->dn_typeinfo.Dir.entrycount = 0;
		/*  until we know better, it has a null parent pointer*/
		dnp->dn_typeinfo.Dir.parent = NULL;
		dnp->dn_links++; /* for .*/
		dnp->dn_typeinfo.Dir.myname = NULL;
		/*
		 * make sure that the ops associated with it are the ops
		 * that we use (by default) for directories
		 */
		dnp->dn_ops = &devfs_vnodeop_p;
		dnp->dn_mode |= 0555;	/* default perms */
		break;
	case DEV_SLNK:
		/*
		 * As it's a symlink allocate and store the link info
		 * Symlinks should only ever be created by the user,
		 * so they are not on the back plane and should not be 
		 * propogated forward.. a bit like directories in that way..
		 * A symlink only exists on one plane and has its own
		 * node.. therefore we might be on any random plane.
		 */
	    	MALLOC(dnp->dn_typeinfo.Slnk.name, char *, 
		       typeinfo->Slnk.namelen+1,
		       M_DEVFSNODE, M_WAITOK);
		if (!dnp->dn_typeinfo.Slnk.name) {
		    	FREE(dnp,M_DEVFSNODE);
			return ENOMEM;
		}
		strncpy(dnp->dn_typeinfo.Slnk.name, typeinfo->Slnk.name,
			typeinfo->Slnk.namelen);
		dnp->dn_typeinfo.Slnk.name[typeinfo->Slnk.namelen] = '\0';
		dnp->dn_typeinfo.Slnk.namelen = typeinfo->Slnk.namelen;
		DEVFS_INCR_STRINGSPACE(dnp->dn_typeinfo.Slnk.namelen + 1);
		dnp->dn_ops = &devfs_vnodeop_p;
		dnp->dn_mode |= 0555;	/* default perms */
		break;
	case DEV_CDEV:
	case DEV_BDEV:
		/*
		 * Make sure it has DEVICE type ops
		 * and device specific fields are correct
		 */
		dnp->dn_ops = &devfs_spec_vnodeop_p;
		dnp->dn_typeinfo.dev = typeinfo->dev;
		break;
	default:
		return EINVAL;
	}

	*dn_pp = dnp;
	DEVFS_INCR_NODES();
	return 0 ;
}


/***********************************************************************
 * called with DEVFS_LOCK held
 **********************************************************************/
void
devnode_free(devnode_t * dnp)
{
    if (dnp->dn_lflags & DN_BUSY) {
            dnp->dn_lflags |= DN_DELETE;
	    return;
    }
    if (dnp->dn_type == DEV_SLNK) {
        DEVFS_DECR_STRINGSPACE(dnp->dn_typeinfo.Slnk.namelen + 1);
	FREE(dnp->dn_typeinfo.Slnk.name, M_DEVFSNODE);
    }
    DEVFS_DECR_NODES();
    FREE(dnp, M_DEVFSNODE);
}


/***********************************************************************
 * called with DEVFS_LOCK held
 **********************************************************************/
static void
devfs_dn_free(devnode_t * dnp)
{
	if(--dnp->dn_links <= 0 ) /* can be -1 for initial free, on error */
	{
		/*probably need to do other cleanups XXX */
		if (dnp->dn_nextsibling != dnp) {
			devnode_t * * 	prevp = dnp->dn_prevsiblingp;
			*prevp = dnp->dn_nextsibling;
			dnp->dn_nextsibling->dn_prevsiblingp = prevp;
			
		}
		if (dnp->dn_vn == NULL) {
		    devnode_free(dnp); /* no accesses/references */
		}
		else {
		    dnp->dn_delete = TRUE;
		}
	}
}

/***********************************************************************\
*	Front Node Operations						* 
*	Add or delete a chain of front nodes				*
\***********************************************************************/


/***********************************************************************
 * Given a directory backing node, and a child backing node, add the
 * appropriate front nodes to the front nodes of the directory to
 * represent the child node to the user
 *
 * on failure, front nodes will either be correct or not exist for each
 * front dir, however dirs completed will not be stripped of completed
 * frontnodes on failure of a later frontnode
 *
 * This allows a new node to be propogated through all mounted planes
 *
 * called with DEVFS_LOCK held
 ***********************************************************************/
static int
devfs_propogate(devdirent_t * parent,devdirent_t * child)
{
	int	error;
	devdirent_t * newnmp;
	devnode_t *	dnp = child->de_dnp;
	devnode_t *	pdnp = parent->de_dnp;
	devnode_t *	adnp = parent->de_dnp;
	int type = child->de_dnp->dn_type;

	/***********************************************
	 * Find the other instances of the parent node
	 ***********************************************/
	for (adnp = pdnp->dn_nextsibling;
		adnp != pdnp;
		adnp = adnp->dn_nextsibling)
	{
		/*
		 * Make the node, using the original as a prototype)
		 * if the node already exists on that plane it won't be
		 * re-made..
		 */
		if ((error = dev_add_entry(child->de_name, adnp, type,
					   NULL, dnp, adnp->dn_dvm, 
					   &newnmp)) != 0) {
			printf("duplicating %s failed\n",child->de_name);
		}
	}
	return 0;	/* for now always succeed */
}


/***********************************************************************
 * remove all instances of this devicename [for backing nodes..]
 * note.. if there is another link to the node (non dir nodes only)
 * then the devfs_node will still exist as the ref count will be non-0
 * removing a directory node will remove all sup-nodes on all planes (ZAP)
 *
 * Used by device drivers to remove nodes that are no longer relevant
 * The argument is the 'cookie' they were given when they created the node
 * this function is exported.. see devfs.h
 ***********************************************************************/
void
devfs_remove(void *dirent_p)
{
	devnode_t * dnp = ((devdirent_t *)dirent_p)->de_dnp;
	devnode_t * dnp2;
	boolean_t   lastlink;

	DEVFS_LOCK();

	if (!devfs_ready) {
		printf("devfs_remove: not ready for devices!\n");
		goto out;
	}

	/* keep removing the next sibling till only we exist. */
	while ((dnp2 = dnp->dn_nextsibling) != dnp) {

		/*
		 * Keep removing the next front node till no more exist
		 */
		dnp->dn_nextsibling = dnp2->dn_nextsibling; 
		dnp->dn_nextsibling->dn_prevsiblingp = &(dnp->dn_nextsibling);
		dnp2->dn_nextsibling = dnp2;
		dnp2->dn_prevsiblingp = &(dnp2->dn_nextsibling);
		if (dnp2->dn_linklist) {
			do {
				lastlink = (1 == dnp2->dn_links);
				dev_free_name(dnp2->dn_linklist);
			} while (!lastlink);
		}
	}

	/*
	 * then free the main node
	 * If we are not running in SPLIT_DEVS mode, then
	 * THIS is what gets rid of the propogated nodes.
	 */
	if (dnp->dn_linklist) {
		do {
			lastlink = (1 == dnp->dn_links);
			dev_free_name(dnp->dn_linklist);
		} while (!lastlink);
	}
out:
	DEVFS_UNLOCK();

	return ;
}



/***************************************************************
 * duplicate the backing tree into a tree of nodes hung off the
 * mount point given as the argument. Do this by
 * calling dev_dup_entry which recurses all the way
 * up the tree..
 *
 * called with DEVFS_LOCK held
 **************************************************************/
int
dev_dup_plane(struct devfsmount *devfs_mp_p)
{
	devdirent_t *	new;
	int		error = 0;

	if ((error = dev_dup_entry(NULL, dev_root, &new, devfs_mp_p)))
	        return error;
	devfs_mp_p->plane_root = new;
	return error;
}



/***************************************************************
 * Free a whole plane
 *
 * called with DEVFS_LOCK held
 ***************************************************************/
void
devfs_free_plane(struct devfsmount *devfs_mp_p)
{
	devdirent_t * dirent_p;

	dirent_p = devfs_mp_p->plane_root;
	if (dirent_p) {
		dev_free_hier(dirent_p);
		dev_free_name(dirent_p);
	}
	devfs_mp_p->plane_root = NULL;
}


/***************************************************************
 * Create and link in a new front element..
 * Parent can be 0 for a root node
 * Not presently usable to make a symlink XXX
 * (Ok, symlinks don't propogate)
 * recursively will create subnodes corresponding to equivalent
 * child nodes in the base level
 *
 * called with DEVFS_LOCK held
 ***************************************************************/
static int
dev_dup_entry(devnode_t * parent, devdirent_t * back, devdirent_t * *dnm_pp,
	      struct devfsmount *dvm)
{
	devdirent_t *	entry_p;
	devdirent_t *	newback;
	devdirent_t *	newfront;
	int	error;
	devnode_t *	dnp = back->de_dnp;
	int type = dnp->dn_type;

	/*
	 * go get the node made (if we need to)
	 * use the back one as a prototype
	 */
	if ((error = dev_add_entry(back->de_name, parent, type,
				NULL, dnp,
				parent?parent->dn_dvm:dvm, &entry_p)) != 0) {
		printf("duplicating %s failed\n",back->de_name);
	}

	/*
	 * If we have just made the root, then insert the pointer to the
	 * mount information
	 */
	if(dvm) {
		entry_p->de_dnp->dn_dvm = dvm;
	}

	/*
	 * If it is a directory, then recurse down all the other
	 * subnodes in it....
	 * note that this time we don't pass on the mount info..
	 */
	if (type == DEV_DIR)
	{
		for(newback = back->de_dnp->dn_typeinfo.Dir.dirlist;
				newback; newback = newback->de_next)
		{
			if((error = dev_dup_entry(entry_p->de_dnp,
					    newback, &newfront, NULL)) != 0)
			{
				break; /* back out with an error */
			}
		}
	}
	*dnm_pp = entry_p;
	return error;
}


/***************************************************************
 * Free a name node
 * remember that if there are other names pointing to the
 * dev_node then it may not get freed yet
 * can handle if there is no dnp
 *
 * called with DEVFS_LOCK held
 ***************************************************************/

int
dev_free_name(devdirent_t * dirent_p)
{
	devnode_t *	parent = dirent_p->de_parent;
	devnode_t *	dnp = dirent_p->de_dnp;

	if(dnp) {
		if(dnp->dn_type == DEV_DIR)
		{
		    	devnode_t * p;

			if(dnp->dn_typeinfo.Dir.dirlist)
				return (ENOTEMPTY);
			p = dnp->dn_typeinfo.Dir.parent;
			devfs_dn_free(dnp); 	/* account for '.' */
			devfs_dn_free(p); 	/* '..' */
		}
		/*
		 * unlink us from the list of links for this node
		 * If we are the only link, it's easy!
		 * if we are a DIR of course there should not be any
		 * other links.
	 	 */
		if(dirent_p->de_nextlink == dirent_p) {
				dnp->dn_linklist = NULL;
		} else {
			if(dnp->dn_linklist == dirent_p) {
				dnp->dn_linklist = dirent_p->de_nextlink;
			}
			dirent_p->de_nextlink->de_prevlinkp 
			    = dirent_p->de_prevlinkp;
			*dirent_p->de_prevlinkp = dirent_p->de_nextlink;
		}
		devfs_dn_free(dnp);
	}

	/*
	 * unlink ourselves from the directory on this plane
	 */
	if(parent) /* if not fs root */
	{
		if( (*dirent_p->de_prevp = dirent_p->de_next) )/* yes, assign */
		{
			dirent_p->de_next->de_prevp = dirent_p->de_prevp;
		}
		else
		{
			parent->dn_typeinfo.Dir.dirlast
				= dirent_p->de_prevp;
		}
		parent->dn_typeinfo.Dir.entrycount--;
		parent->dn_len -= strlen(dirent_p->de_name) + 8;
	}

	DEVFS_DECR_ENTRIES();
	FREE(dirent_p, M_DEVFSNAME);
	return 0;
}


/***************************************************************
 * Free a hierarchy starting at a directory node name
 * remember that if there are other names pointing to the
 * dev_node then it may not get freed yet
 * can handle if there is no dnp
 * leave the node itself allocated.
 *
 * called with DEVFS_LOCK held
 ***************************************************************/

static void
dev_free_hier(devdirent_t * dirent_p)
{
	devnode_t *	dnp = dirent_p->de_dnp;

	if(dnp) {
		if(dnp->dn_type == DEV_DIR)
		{
			while(dnp->dn_typeinfo.Dir.dirlist)
			{
				dev_free_hier(dnp->dn_typeinfo.Dir.dirlist);
				dev_free_name(dnp->dn_typeinfo.Dir.dirlist);
			}
		}
	}
}


/***************************************************************
 * given a dev_node, find the appropriate vnode if one is already
 * associated, or get a new one and associate it with the dev_node
 *
 * called with DEVFS_LOCK held
 ***************************************************************/
int
devfs_dntovn(devnode_t * dnp, struct vnode **vn_pp, __unused struct proc * p)
{
	struct vnode *vn_p;
	int error = 0;
	struct vnode_fsparam vfsp;
	enum vtype vtype = 0;
	int markroot = 0;

retry:
	*vn_pp = NULL;
	vn_p = dnp->dn_vn;

	dnp->dn_lflags |= DN_BUSY;

	if (vn_p) { /* already has a vnode */
	        uint32_t vid;
		
		vid = vnode_vid(vn_p);

		DEVFS_UNLOCK();

	        error = vnode_getwithvid(vn_p, vid);

	        DEVFS_LOCK();

		if (dnp->dn_lflags & DN_DELETE) {
		        /*
			 * our BUSY node got marked for
			 * deletion while the DEVFS lock
			 * was dropped...
			 */
		        if (error == 0) {
			        /*
				 * vnode_getwithvid returned a valid ref
				 * which we need to drop
				 */
			        vnode_put(vn_p);
			}
			/*
			 * set the error to EAGAIN
			 * which will cause devfs_lookup
			 * to retry this node
			 */
			error = EAGAIN;
		}
		if ( !error)
		        *vn_pp = vn_p;

		devfs_release_busy(dnp);

		return error;
	}

	if (dnp->dn_lflags & DN_CREATE) {
		dnp->dn_lflags |= DN_CREATEWAIT;
		msleep(&dnp->dn_lflags, &devfs_mutex, PRIBIO, 0 , 0);
		goto retry;
	}

	dnp->dn_lflags |= DN_CREATE;

	switch (dnp->dn_type) {
		case	DEV_SLNK:
			vtype = VLNK;
			break;
		case	DEV_DIR:
			if (dnp->dn_typeinfo.Dir.parent == dnp) {
				markroot = 1;
			}
			vtype = VDIR;
			break;
		case	DEV_BDEV:
		case	DEV_CDEV:
		    	vtype = (dnp->dn_type == DEV_BDEV) ? VBLK : VCHR;
			break;
	}
	vfsp.vnfs_mp = dnp->dn_dvm->mount;
	vfsp.vnfs_vtype = vtype;
	vfsp.vnfs_str = "devfs";
	vfsp.vnfs_dvp = 0;
	vfsp.vnfs_fsnode = dnp;
	vfsp.vnfs_cnp = 0;
	vfsp.vnfs_vops = *(dnp->dn_ops);
		
	if (vtype == VBLK || vtype == VCHR)
		vfsp.vnfs_rdev = dnp->dn_typeinfo.dev;
	else
		vfsp.vnfs_rdev = 0;
	vfsp.vnfs_filesize = 0;
	vfsp.vnfs_flags = VNFS_NOCACHE | VNFS_CANTCACHE;
	/* Tag system files */
	vfsp.vnfs_marksystem = 0;
	vfsp.vnfs_markroot = markroot;

	DEVFS_UNLOCK();

	error = vnode_create(VNCREATE_FLAVOR, VCREATESIZE, &vfsp, &vn_p);

	DEVFS_LOCK();

	if (error == 0) {
		if ((dnp->dn_vn)) {
			panic("devnode already has a vnode?");
		} else {
			dnp->dn_vn = vn_p;
			*vn_pp = vn_p;
			vnode_settag(vn_p, VT_DEVFS);
		}
	}

	dnp->dn_lflags &= ~DN_CREATE;

	if (dnp->dn_lflags & DN_CREATEWAIT) {
		dnp->dn_lflags &= ~DN_CREATEWAIT;
		wakeup(&dnp->dn_lflags);
	}

	devfs_release_busy(dnp);

	return error;
}


/***********************************************************************
 * called with DEVFS_LOCK held
 ***********************************************************************/
static void
devfs_release_busy(devnode_t *dnp) {

        dnp->dn_lflags &= ~DN_BUSY;

	if (dnp->dn_lflags & DN_DELETE)
	        devnode_free(dnp);
}

/***********************************************************************
 * add a whole device, with no prototype.. make name element and node
 * Used for adding the original device entries
 *
 * called with DEVFS_LOCK held
 ***********************************************************************/
int
dev_add_entry(char *name, devnode_t * parent, int type, devnode_type_t * typeinfo,
	      devnode_t * proto, struct devfsmount *dvm, devdirent_t * *nm_pp)
{
	devnode_t *	dnp;
	int	error = 0;

	if ((error = dev_add_node(type, typeinfo, proto, &dnp, 
			(parent?parent->dn_dvm:dvm))) != 0)
	{
		printf("devfs: %s: base node allocation failed (Errno=%d)\n",
			name,error);
		return error;
	}
	if ((error = dev_add_name(name ,parent ,NULL, dnp, nm_pp)) != 0)
	{
		devfs_dn_free(dnp); /* 1->0 for dir, 0->(-1) for other */
		printf("devfs: %s: name slot allocation failed (Errno=%d)\n",
		       name,error);
		
	}
	return error;
}


/*
 * Function: devfs_make_node
 *
 * Purpose
 *   Create a device node with the given pathname in the devfs namespace.
 *
 * Parameters:
 *   dev 	- the dev_t value to associate
 *   chrblk	- block or character device (DEVFS_CHAR or DEVFS_BLOCK)
 *   uid, gid	- ownership
 *   perms	- permissions
 *   fmt, ...	- path format string with printf args to format the path name
 * Returns:
 *   A handle to a device node if successful, NULL otherwise.
 */
void *
devfs_make_node(dev_t dev, int chrblk, uid_t uid,
		gid_t gid, int perms, const char *fmt, ...)
{
	devdirent_t *	new_dev = NULL;
	devnode_t *	dnp;	/* devnode for parent directory */
	devnode_type_t	typeinfo;

	char *name, *path, buf[256]; /* XXX */
	int i;
	va_list ap;


	DEVFS_LOCK();

	if (!devfs_ready) {
		printf("devfs_make_node: not ready for devices!\n");
		goto out;
	}
	if (chrblk != DEVFS_CHAR && chrblk != DEVFS_BLOCK)
		goto out;

	DEVFS_UNLOCK();

	va_start(ap, fmt);
	vsnprintf(buf, sizeof(buf), fmt, ap);
	va_end(ap);

	name = NULL;

	for(i=strlen(buf); i>0; i--)
		if(buf[i] == '/') {
			name=&buf[i];
			buf[i]=0;
			break;
		}

	if (name) {
		*name++ = '\0';
		path = buf;
	} else {
		name = buf;
		path = "/";
	}
	DEVFS_LOCK();

	/* find/create directory path ie. mkdir -p */
	if (dev_finddir(path, NULL, CREATE, &dnp) == 0) {
	    typeinfo.dev = dev;
	    if (dev_add_entry(name, dnp, 
			      (chrblk == DEVFS_CHAR) ? DEV_CDEV : DEV_BDEV, 
			      &typeinfo, NULL, NULL, &new_dev) == 0) {
		new_dev->de_dnp->dn_gid = gid;
		new_dev->de_dnp->dn_uid = uid;
		new_dev->de_dnp->dn_mode |= perms;
		devfs_propogate(dnp->dn_typeinfo.Dir.myname, new_dev);
	    }
	}
out:
	DEVFS_UNLOCK();

	return new_dev;
}

/*
 * Function: devfs_make_link
 *
 * Purpose:
 *   Create a link to a previously created device node.
 *
 * Returns:
 *   0 if successful, -1 if failed
 */
int
devfs_make_link(void *original, char *fmt, ...)
{
	devdirent_t *	new_dev = NULL;
	devdirent_t *	orig = (devdirent_t *) original;
	devnode_t *	dirnode;	/* devnode for parent directory */

	va_list ap;
	char *p, buf[256]; /* XXX */
	int i;

	DEVFS_LOCK();

	if (!devfs_ready) {
		printf("devfs_make_link: not ready for devices!\n");
		goto out;
	}
	DEVFS_UNLOCK();

	va_start(ap, fmt);
	vsnprintf(buf, sizeof(buf), fmt, ap);
	va_end(ap);

	p = NULL;

	for(i=strlen(buf); i>0; i--) {
		if(buf[i] == '/') {
				p=&buf[i];
				buf[i]=0;
				break;
		}
	}
	DEVFS_LOCK();

	if (p) {
	        *p++ = '\0';

		if (dev_finddir(buf, NULL, CREATE, &dirnode)
		    || dev_add_name(p, dirnode, NULL, orig->de_dnp, &new_dev))
		        goto fail;
	} else {
	        if (dev_finddir("", NULL, CREATE, &dirnode)
		    || dev_add_name(buf, dirnode, NULL, orig->de_dnp, &new_dev))
		        goto fail;
	}
	devfs_propogate(dirnode->dn_typeinfo.Dir.myname, new_dev);
fail:
out:
	DEVFS_UNLOCK();

	return ((new_dev != NULL) ? 0 : -1);
}