xref: /freebsd/sys/fs/tmpfs/tmpfs_subr.c (revision ddd5b8e9b4d8957fce018c520657cdfa4ecffad3)
1 /*	$NetBSD: tmpfs_subr.c,v 1.35 2007/07/09 21:10:50 ad Exp $	*/
2 
3 /*-
4  * Copyright (c) 2005 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to The NetBSD Foundation
8  * by Julio M. Merino Vidal, developed as part of Google's Summer of Code
9  * 2005 program.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
24  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30  * POSSIBILITY OF SUCH DAMAGE.
31  */
32 
33 /*
34  * Efficient memory file system supporting functions.
35  */
36 #include <sys/cdefs.h>
37 __FBSDID("$FreeBSD$");
38 
39 #include <sys/param.h>
40 #include <sys/fnv_hash.h>
41 #include <sys/lock.h>
42 #include <sys/namei.h>
43 #include <sys/priv.h>
44 #include <sys/proc.h>
45 #include <sys/rwlock.h>
46 #include <sys/stat.h>
47 #include <sys/systm.h>
48 #include <sys/sysctl.h>
49 #include <sys/vnode.h>
50 #include <sys/vmmeter.h>
51 
52 #include <vm/vm.h>
53 #include <vm/vm_param.h>
54 #include <vm/vm_object.h>
55 #include <vm/vm_page.h>
56 #include <vm/vm_pageout.h>
57 #include <vm/vm_pager.h>
58 #include <vm/vm_extern.h>
59 
60 #include <fs/tmpfs/tmpfs.h>
61 #include <fs/tmpfs/tmpfs_fifoops.h>
62 #include <fs/tmpfs/tmpfs_vnops.h>
63 
64 struct tmpfs_dir_cursor {
65 	struct tmpfs_dirent	*tdc_current;
66 	struct tmpfs_dirent	*tdc_tree;
67 };
68 
69 SYSCTL_NODE(_vfs, OID_AUTO, tmpfs, CTLFLAG_RW, 0, "tmpfs file system");
70 
71 static long tmpfs_pages_reserved = TMPFS_PAGES_MINRESERVED;
72 
73 static int
74 sysctl_mem_reserved(SYSCTL_HANDLER_ARGS)
75 {
76 	int error;
77 	long pages, bytes;
78 
79 	pages = *(long *)arg1;
80 	bytes = pages * PAGE_SIZE;
81 
82 	error = sysctl_handle_long(oidp, &bytes, 0, req);
83 	if (error || !req->newptr)
84 		return (error);
85 
86 	pages = bytes / PAGE_SIZE;
87 	if (pages < TMPFS_PAGES_MINRESERVED)
88 		return (EINVAL);
89 
90 	*(long *)arg1 = pages;
91 	return (0);
92 }
93 
94 SYSCTL_PROC(_vfs_tmpfs, OID_AUTO, memory_reserved, CTLTYPE_LONG|CTLFLAG_RW,
95     &tmpfs_pages_reserved, 0, sysctl_mem_reserved, "L",
96     "Amount of available memory and swap below which tmpfs growth stops");
97 
98 static __inline int tmpfs_dirtree_cmp(struct tmpfs_dirent *a,
99     struct tmpfs_dirent *b);
100 RB_PROTOTYPE_STATIC(tmpfs_dir, tmpfs_dirent, uh.td_entries, tmpfs_dirtree_cmp);
101 
102 size_t
103 tmpfs_mem_avail(void)
104 {
105 	vm_ooffset_t avail;
106 
107 	avail = swap_pager_avail + cnt.v_free_count + cnt.v_cache_count -
108 	    tmpfs_pages_reserved;
109 	if (__predict_false(avail < 0))
110 		avail = 0;
111 	return (avail);
112 }
113 
114 size_t
115 tmpfs_pages_used(struct tmpfs_mount *tmp)
116 {
117 	const size_t node_size = sizeof(struct tmpfs_node) +
118 	    sizeof(struct tmpfs_dirent);
119 	size_t meta_pages;
120 
121 	meta_pages = howmany((uintmax_t)tmp->tm_nodes_inuse * node_size,
122 	    PAGE_SIZE);
123 	return (meta_pages + tmp->tm_pages_used);
124 }
125 
126 static size_t
127 tmpfs_pages_check_avail(struct tmpfs_mount *tmp, size_t req_pages)
128 {
129 	if (tmpfs_mem_avail() < req_pages)
130 		return (0);
131 
132 	if (tmp->tm_pages_max != SIZE_MAX &&
133 	    tmp->tm_pages_max < req_pages + tmpfs_pages_used(tmp))
134 			return (0);
135 
136 	return (1);
137 }
138 
139 /* --------------------------------------------------------------------- */
140 
141 /*
142  * Allocates a new node of type 'type' inside the 'tmp' mount point, with
143  * its owner set to 'uid', its group to 'gid' and its mode set to 'mode',
144  * using the credentials of the process 'p'.
145  *
146  * If the node type is set to 'VDIR', then the parent parameter must point
147  * to the parent directory of the node being created.  It may only be NULL
148  * while allocating the root node.
149  *
150  * If the node type is set to 'VBLK' or 'VCHR', then the rdev parameter
151  * specifies the device the node represents.
152  *
153  * If the node type is set to 'VLNK', then the parameter target specifies
154  * the file name of the target file for the symbolic link that is being
155  * created.
156  *
157  * Note that new nodes are retrieved from the available list if it has
158  * items or, if it is empty, from the node pool as long as there is enough
159  * space to create them.
160  *
161  * Returns zero on success or an appropriate error code on failure.
162  */
163 int
164 tmpfs_alloc_node(struct tmpfs_mount *tmp, enum vtype type,
165     uid_t uid, gid_t gid, mode_t mode, struct tmpfs_node *parent,
166     char *target, dev_t rdev, struct tmpfs_node **node)
167 {
168 	struct tmpfs_node *nnode;
169 
170 	/* If the root directory of the 'tmp' file system is not yet
171 	 * allocated, this must be the request to do it. */
172 	MPASS(IMPLIES(tmp->tm_root == NULL, parent == NULL && type == VDIR));
173 
174 	MPASS(IFF(type == VLNK, target != NULL));
175 	MPASS(IFF(type == VBLK || type == VCHR, rdev != VNOVAL));
176 
177 	if (tmp->tm_nodes_inuse >= tmp->tm_nodes_max)
178 		return (ENOSPC);
179 	if (tmpfs_pages_check_avail(tmp, 1) == 0)
180 		return (ENOSPC);
181 
182 	nnode = (struct tmpfs_node *)uma_zalloc_arg(
183 				tmp->tm_node_pool, tmp, M_WAITOK);
184 
185 	/* Generic initialization. */
186 	nnode->tn_type = type;
187 	vfs_timestamp(&nnode->tn_atime);
188 	nnode->tn_birthtime = nnode->tn_ctime = nnode->tn_mtime =
189 	    nnode->tn_atime;
190 	nnode->tn_uid = uid;
191 	nnode->tn_gid = gid;
192 	nnode->tn_mode = mode;
193 	nnode->tn_id = alloc_unr(tmp->tm_ino_unr);
194 
195 	/* Type-specific initialization. */
196 	switch (nnode->tn_type) {
197 	case VBLK:
198 	case VCHR:
199 		nnode->tn_rdev = rdev;
200 		break;
201 
202 	case VDIR:
203 		RB_INIT(&nnode->tn_dir.tn_dirhead);
204 		LIST_INIT(&nnode->tn_dir.tn_dupindex);
205 		MPASS(parent != nnode);
206 		MPASS(IMPLIES(parent == NULL, tmp->tm_root == NULL));
207 		nnode->tn_dir.tn_parent = (parent == NULL) ? nnode : parent;
208 		nnode->tn_dir.tn_readdir_lastn = 0;
209 		nnode->tn_dir.tn_readdir_lastp = NULL;
210 		nnode->tn_links++;
211 		TMPFS_NODE_LOCK(nnode->tn_dir.tn_parent);
212 		nnode->tn_dir.tn_parent->tn_links++;
213 		TMPFS_NODE_UNLOCK(nnode->tn_dir.tn_parent);
214 		break;
215 
216 	case VFIFO:
217 		/* FALLTHROUGH */
218 	case VSOCK:
219 		break;
220 
221 	case VLNK:
222 		MPASS(strlen(target) < MAXPATHLEN);
223 		nnode->tn_size = strlen(target);
224 		nnode->tn_link = malloc(nnode->tn_size, M_TMPFSNAME,
225 		    M_WAITOK);
226 		memcpy(nnode->tn_link, target, nnode->tn_size);
227 		break;
228 
229 	case VREG:
230 		nnode->tn_reg.tn_aobj =
231 		    vm_pager_allocate(OBJT_SWAP, NULL, 0, VM_PROT_DEFAULT, 0,
232 			NULL /* XXXKIB - tmpfs needs swap reservation */);
233 		break;
234 
235 	default:
236 		panic("tmpfs_alloc_node: type %p %d", nnode, (int)nnode->tn_type);
237 	}
238 
239 	TMPFS_LOCK(tmp);
240 	LIST_INSERT_HEAD(&tmp->tm_nodes_used, nnode, tn_entries);
241 	tmp->tm_nodes_inuse++;
242 	TMPFS_UNLOCK(tmp);
243 
244 	*node = nnode;
245 	return 0;
246 }
247 
248 /* --------------------------------------------------------------------- */
249 
250 /*
251  * Destroys the node pointed to by node from the file system 'tmp'.
252  * If the node does not belong to the given mount point, the results are
253  * unpredicted.
254  *
255  * If the node references a directory; no entries are allowed because
256  * their removal could need a recursive algorithm, something forbidden in
257  * kernel space.  Furthermore, there is not need to provide such
258  * functionality (recursive removal) because the only primitives offered
259  * to the user are the removal of empty directories and the deletion of
260  * individual files.
261  *
262  * Note that nodes are not really deleted; in fact, when a node has been
263  * allocated, it cannot be deleted during the whole life of the file
264  * system.  Instead, they are moved to the available list and remain there
265  * until reused.
266  */
267 void
268 tmpfs_free_node(struct tmpfs_mount *tmp, struct tmpfs_node *node)
269 {
270 	vm_object_t uobj;
271 
272 #ifdef INVARIANTS
273 	TMPFS_NODE_LOCK(node);
274 	MPASS(node->tn_vnode == NULL);
275 	MPASS((node->tn_vpstate & TMPFS_VNODE_ALLOCATING) == 0);
276 	TMPFS_NODE_UNLOCK(node);
277 #endif
278 
279 	TMPFS_LOCK(tmp);
280 	LIST_REMOVE(node, tn_entries);
281 	tmp->tm_nodes_inuse--;
282 	TMPFS_UNLOCK(tmp);
283 
284 	switch (node->tn_type) {
285 	case VNON:
286 		/* Do not do anything.  VNON is provided to let the
287 		 * allocation routine clean itself easily by avoiding
288 		 * duplicating code in it. */
289 		/* FALLTHROUGH */
290 	case VBLK:
291 		/* FALLTHROUGH */
292 	case VCHR:
293 		/* FALLTHROUGH */
294 	case VDIR:
295 		/* FALLTHROUGH */
296 	case VFIFO:
297 		/* FALLTHROUGH */
298 	case VSOCK:
299 		break;
300 
301 	case VLNK:
302 		free(node->tn_link, M_TMPFSNAME);
303 		break;
304 
305 	case VREG:
306 		uobj = node->tn_reg.tn_aobj;
307 		if (uobj != NULL) {
308 			TMPFS_LOCK(tmp);
309 			tmp->tm_pages_used -= uobj->size;
310 			TMPFS_UNLOCK(tmp);
311 			vm_object_deallocate(uobj);
312 		}
313 		break;
314 
315 	default:
316 		panic("tmpfs_free_node: type %p %d", node, (int)node->tn_type);
317 	}
318 
319 	free_unr(tmp->tm_ino_unr, node->tn_id);
320 	uma_zfree(tmp->tm_node_pool, node);
321 }
322 
323 /* --------------------------------------------------------------------- */
324 
325 static __inline uint32_t
326 tmpfs_dirent_hash(const char *name, u_int len)
327 {
328 	uint32_t hash;
329 
330 	hash = fnv_32_buf(name, len, FNV1_32_INIT + len) & TMPFS_DIRCOOKIE_MASK;
331 #ifdef TMPFS_DEBUG_DIRCOOKIE_DUP
332 	hash &= 0xf;
333 #endif
334 	if (hash < TMPFS_DIRCOOKIE_MIN)
335 		hash += TMPFS_DIRCOOKIE_MIN;
336 
337 	return (hash);
338 }
339 
340 static __inline off_t
341 tmpfs_dirent_cookie(struct tmpfs_dirent *de)
342 {
343 	MPASS(de->td_cookie >= TMPFS_DIRCOOKIE_MIN);
344 
345 	return (de->td_cookie);
346 }
347 
348 static __inline boolean_t
349 tmpfs_dirent_dup(struct tmpfs_dirent *de)
350 {
351 	return ((de->td_cookie & TMPFS_DIRCOOKIE_DUP) != 0);
352 }
353 
354 static __inline boolean_t
355 tmpfs_dirent_duphead(struct tmpfs_dirent *de)
356 {
357 	return ((de->td_cookie & TMPFS_DIRCOOKIE_DUPHEAD) != 0);
358 }
359 
360 void
361 tmpfs_dirent_init(struct tmpfs_dirent *de, const char *name, u_int namelen)
362 {
363 	de->td_hash = de->td_cookie = tmpfs_dirent_hash(name, namelen);
364 	memcpy(de->ud.td_name, name, namelen);
365 	de->td_namelen = namelen;
366 }
367 
368 /*
369  * Allocates a new directory entry for the node node with a name of name.
370  * The new directory entry is returned in *de.
371  *
372  * The link count of node is increased by one to reflect the new object
373  * referencing it.
374  *
375  * Returns zero on success or an appropriate error code on failure.
376  */
377 int
378 tmpfs_alloc_dirent(struct tmpfs_mount *tmp, struct tmpfs_node *node,
379     const char *name, u_int len, struct tmpfs_dirent **de)
380 {
381 	struct tmpfs_dirent *nde;
382 
383 	nde = uma_zalloc(tmp->tm_dirent_pool, M_WAITOK);
384 	nde->td_node = node;
385 	if (name != NULL) {
386 		nde->ud.td_name = malloc(len, M_TMPFSNAME, M_WAITOK);
387 		tmpfs_dirent_init(nde, name, len);
388 	} else
389 		nde->td_namelen = 0;
390 	if (node != NULL)
391 		node->tn_links++;
392 
393 	*de = nde;
394 
395 	return 0;
396 }
397 
398 /* --------------------------------------------------------------------- */
399 
400 /*
401  * Frees a directory entry.  It is the caller's responsibility to destroy
402  * the node referenced by it if needed.
403  *
404  * The link count of node is decreased by one to reflect the removal of an
405  * object that referenced it.  This only happens if 'node_exists' is true;
406  * otherwise the function will not access the node referred to by the
407  * directory entry, as it may already have been released from the outside.
408  */
409 void
410 tmpfs_free_dirent(struct tmpfs_mount *tmp, struct tmpfs_dirent *de)
411 {
412 	struct tmpfs_node *node;
413 
414 	node = de->td_node;
415 	if (node != NULL) {
416 		MPASS(node->tn_links > 0);
417 		node->tn_links--;
418 	}
419 	if (!tmpfs_dirent_duphead(de) && de->ud.td_name != NULL)
420 		free(de->ud.td_name, M_TMPFSNAME);
421 	uma_zfree(tmp->tm_dirent_pool, de);
422 }
423 
424 /* --------------------------------------------------------------------- */
425 
426 /*
427  * Allocates a new vnode for the node node or returns a new reference to
428  * an existing one if the node had already a vnode referencing it.  The
429  * resulting locked vnode is returned in *vpp.
430  *
431  * Returns zero on success or an appropriate error code on failure.
432  */
433 int
434 tmpfs_alloc_vp(struct mount *mp, struct tmpfs_node *node, int lkflag,
435     struct vnode **vpp)
436 {
437 	int error = 0;
438 	struct vnode *vp;
439 
440 loop:
441 	TMPFS_NODE_LOCK(node);
442 	if ((vp = node->tn_vnode) != NULL) {
443 		MPASS((node->tn_vpstate & TMPFS_VNODE_DOOMED) == 0);
444 		VI_LOCK(vp);
445 		TMPFS_NODE_UNLOCK(node);
446 		error = vget(vp, lkflag | LK_INTERLOCK, curthread);
447 		if (error != 0) {
448 			vp = NULL;
449 			goto out;
450 		}
451 
452 		/*
453 		 * Make sure the vnode is still there after
454 		 * getting the interlock to avoid racing a free.
455 		 */
456 		if (node->tn_vnode == NULL || node->tn_vnode != vp) {
457 			vput(vp);
458 			goto loop;
459 		}
460 
461 		goto out;
462 	}
463 
464 	if ((node->tn_vpstate & TMPFS_VNODE_DOOMED) ||
465 	    (node->tn_type == VDIR && node->tn_dir.tn_parent == NULL)) {
466 		TMPFS_NODE_UNLOCK(node);
467 		error = ENOENT;
468 		vp = NULL;
469 		goto out;
470 	}
471 
472 	/*
473 	 * otherwise lock the vp list while we call getnewvnode
474 	 * since that can block.
475 	 */
476 	if (node->tn_vpstate & TMPFS_VNODE_ALLOCATING) {
477 		node->tn_vpstate |= TMPFS_VNODE_WANT;
478 		error = msleep((caddr_t) &node->tn_vpstate,
479 		    TMPFS_NODE_MTX(node), PDROP | PCATCH,
480 		    "tmpfs_alloc_vp", 0);
481 		if (error)
482 			return error;
483 
484 		goto loop;
485 	} else
486 		node->tn_vpstate |= TMPFS_VNODE_ALLOCATING;
487 
488 	TMPFS_NODE_UNLOCK(node);
489 
490 	/* Get a new vnode and associate it with our node. */
491 	error = getnewvnode("tmpfs", mp, &tmpfs_vnodeop_entries, &vp);
492 	if (error != 0)
493 		goto unlock;
494 	MPASS(vp != NULL);
495 
496 	(void) vn_lock(vp, lkflag | LK_RETRY);
497 
498 	vp->v_data = node;
499 	vp->v_type = node->tn_type;
500 
501 	/* Type-specific initialization. */
502 	switch (node->tn_type) {
503 	case VBLK:
504 		/* FALLTHROUGH */
505 	case VCHR:
506 		/* FALLTHROUGH */
507 	case VLNK:
508 		/* FALLTHROUGH */
509 	case VREG:
510 		/* FALLTHROUGH */
511 	case VSOCK:
512 		break;
513 	case VFIFO:
514 		vp->v_op = &tmpfs_fifoop_entries;
515 		break;
516 	case VDIR:
517 		MPASS(node->tn_dir.tn_parent != NULL);
518 		if (node->tn_dir.tn_parent == node)
519 			vp->v_vflag |= VV_ROOT;
520 		break;
521 
522 	default:
523 		panic("tmpfs_alloc_vp: type %p %d", node, (int)node->tn_type);
524 	}
525 
526 	vnode_pager_setsize(vp, node->tn_size);
527 	error = insmntque(vp, mp);
528 	if (error)
529 		vp = NULL;
530 
531 unlock:
532 	TMPFS_NODE_LOCK(node);
533 
534 	MPASS(node->tn_vpstate & TMPFS_VNODE_ALLOCATING);
535 	node->tn_vpstate &= ~TMPFS_VNODE_ALLOCATING;
536 	node->tn_vnode = vp;
537 
538 	if (node->tn_vpstate & TMPFS_VNODE_WANT) {
539 		node->tn_vpstate &= ~TMPFS_VNODE_WANT;
540 		TMPFS_NODE_UNLOCK(node);
541 		wakeup((caddr_t) &node->tn_vpstate);
542 	} else
543 		TMPFS_NODE_UNLOCK(node);
544 
545 out:
546 	*vpp = vp;
547 
548 #ifdef INVARIANTS
549 	if (error == 0) {
550 		MPASS(*vpp != NULL && VOP_ISLOCKED(*vpp));
551 		TMPFS_NODE_LOCK(node);
552 		MPASS(*vpp == node->tn_vnode);
553 		TMPFS_NODE_UNLOCK(node);
554 	}
555 #endif
556 
557 	return error;
558 }
559 
560 /* --------------------------------------------------------------------- */
561 
562 /*
563  * Destroys the association between the vnode vp and the node it
564  * references.
565  */
566 void
567 tmpfs_free_vp(struct vnode *vp)
568 {
569 	struct tmpfs_node *node;
570 
571 	node = VP_TO_TMPFS_NODE(vp);
572 
573 	mtx_assert(TMPFS_NODE_MTX(node), MA_OWNED);
574 	node->tn_vnode = NULL;
575 	vp->v_data = NULL;
576 }
577 
578 /* --------------------------------------------------------------------- */
579 
580 /*
581  * Allocates a new file of type 'type' and adds it to the parent directory
582  * 'dvp'; this addition is done using the component name given in 'cnp'.
583  * The ownership of the new file is automatically assigned based on the
584  * credentials of the caller (through 'cnp'), the group is set based on
585  * the parent directory and the mode is determined from the 'vap' argument.
586  * If successful, *vpp holds a vnode to the newly created file and zero
587  * is returned.  Otherwise *vpp is NULL and the function returns an
588  * appropriate error code.
589  */
590 int
591 tmpfs_alloc_file(struct vnode *dvp, struct vnode **vpp, struct vattr *vap,
592     struct componentname *cnp, char *target)
593 {
594 	int error;
595 	struct tmpfs_dirent *de;
596 	struct tmpfs_mount *tmp;
597 	struct tmpfs_node *dnode;
598 	struct tmpfs_node *node;
599 	struct tmpfs_node *parent;
600 
601 	MPASS(VOP_ISLOCKED(dvp));
602 	MPASS(cnp->cn_flags & HASBUF);
603 
604 	tmp = VFS_TO_TMPFS(dvp->v_mount);
605 	dnode = VP_TO_TMPFS_DIR(dvp);
606 	*vpp = NULL;
607 
608 	/* If the entry we are creating is a directory, we cannot overflow
609 	 * the number of links of its parent, because it will get a new
610 	 * link. */
611 	if (vap->va_type == VDIR) {
612 		/* Ensure that we do not overflow the maximum number of links
613 		 * imposed by the system. */
614 		MPASS(dnode->tn_links <= LINK_MAX);
615 		if (dnode->tn_links == LINK_MAX) {
616 			error = EMLINK;
617 			goto out;
618 		}
619 
620 		parent = dnode;
621 		MPASS(parent != NULL);
622 	} else
623 		parent = NULL;
624 
625 	/* Allocate a node that represents the new file. */
626 	error = tmpfs_alloc_node(tmp, vap->va_type, cnp->cn_cred->cr_uid,
627 	    dnode->tn_gid, vap->va_mode, parent, target, vap->va_rdev, &node);
628 	if (error != 0)
629 		goto out;
630 
631 	/* Allocate a directory entry that points to the new file. */
632 	error = tmpfs_alloc_dirent(tmp, node, cnp->cn_nameptr, cnp->cn_namelen,
633 	    &de);
634 	if (error != 0) {
635 		tmpfs_free_node(tmp, node);
636 		goto out;
637 	}
638 
639 	/* Allocate a vnode for the new file. */
640 	error = tmpfs_alloc_vp(dvp->v_mount, node, LK_EXCLUSIVE, vpp);
641 	if (error != 0) {
642 		tmpfs_free_dirent(tmp, de);
643 		tmpfs_free_node(tmp, node);
644 		goto out;
645 	}
646 
647 	/* Now that all required items are allocated, we can proceed to
648 	 * insert the new node into the directory, an operation that
649 	 * cannot fail. */
650 	if (cnp->cn_flags & ISWHITEOUT)
651 		tmpfs_dir_whiteout_remove(dvp, cnp);
652 	tmpfs_dir_attach(dvp, de);
653 
654 out:
655 
656 	return error;
657 }
658 
659 /* --------------------------------------------------------------------- */
660 
661 static struct tmpfs_dirent *
662 tmpfs_dir_first(struct tmpfs_node *dnode, struct tmpfs_dir_cursor *dc)
663 {
664 	struct tmpfs_dirent *de;
665 
666 	de = RB_MIN(tmpfs_dir, &dnode->tn_dir.tn_dirhead);
667 	dc->tdc_tree = de;
668 	if (de != NULL && tmpfs_dirent_duphead(de))
669 		de = LIST_FIRST(&de->ud.td_duphead);
670 	dc->tdc_current = de;
671 
672 	return (dc->tdc_current);
673 }
674 
675 static struct tmpfs_dirent *
676 tmpfs_dir_next(struct tmpfs_node *dnode, struct tmpfs_dir_cursor *dc)
677 {
678 	struct tmpfs_dirent *de;
679 
680 	MPASS(dc->tdc_tree != NULL);
681 	if (tmpfs_dirent_dup(dc->tdc_current)) {
682 		dc->tdc_current = LIST_NEXT(dc->tdc_current, uh.td_dup.entries);
683 		if (dc->tdc_current != NULL)
684 			return (dc->tdc_current);
685 	}
686 	dc->tdc_tree = dc->tdc_current = RB_NEXT(tmpfs_dir,
687 	    &dnode->tn_dir.tn_dirhead, dc->tdc_tree);
688 	if ((de = dc->tdc_current) != NULL && tmpfs_dirent_duphead(de)) {
689 		dc->tdc_current = LIST_FIRST(&de->ud.td_duphead);
690 		MPASS(dc->tdc_current != NULL);
691 	}
692 
693 	return (dc->tdc_current);
694 }
695 
696 /* Lookup directory entry in RB-Tree. Function may return duphead entry. */
697 static struct tmpfs_dirent *
698 tmpfs_dir_xlookup_hash(struct tmpfs_node *dnode, uint32_t hash)
699 {
700 	struct tmpfs_dirent *de, dekey;
701 
702 	dekey.td_hash = hash;
703 	de = RB_FIND(tmpfs_dir, &dnode->tn_dir.tn_dirhead, &dekey);
704 	return (de);
705 }
706 
707 /* Lookup directory entry by cookie, initialize directory cursor accordingly. */
708 static struct tmpfs_dirent *
709 tmpfs_dir_lookup_cookie(struct tmpfs_node *node, off_t cookie,
710     struct tmpfs_dir_cursor *dc)
711 {
712 	struct tmpfs_dir *dirhead = &node->tn_dir.tn_dirhead;
713 	struct tmpfs_dirent *de, dekey;
714 
715 	MPASS(cookie >= TMPFS_DIRCOOKIE_MIN);
716 
717 	if (cookie == node->tn_dir.tn_readdir_lastn &&
718 	    (de = node->tn_dir.tn_readdir_lastp) != NULL) {
719 		/* Protect against possible race, tn_readdir_last[pn]
720 		 * may be updated with only shared vnode lock held. */
721 		if (cookie == tmpfs_dirent_cookie(de))
722 			goto out;
723 	}
724 
725 	if ((cookie & TMPFS_DIRCOOKIE_DUP) != 0) {
726 		LIST_FOREACH(de, &node->tn_dir.tn_dupindex,
727 		    uh.td_dup.index_entries) {
728 			MPASS(tmpfs_dirent_dup(de));
729 			if (de->td_cookie == cookie)
730 				goto out;
731 			/* dupindex list is sorted. */
732 			if (de->td_cookie < cookie) {
733 				de = NULL;
734 				goto out;
735 			}
736 		}
737 		MPASS(de == NULL);
738 		goto out;
739 	}
740 
741 	MPASS((cookie & TMPFS_DIRCOOKIE_MASK) == cookie);
742 	dekey.td_hash = cookie;
743 	/* Recover if direntry for cookie was removed */
744 	de = RB_NFIND(tmpfs_dir, dirhead, &dekey);
745 	dc->tdc_tree = de;
746 	dc->tdc_current = de;
747 	if (de != NULL && tmpfs_dirent_duphead(de)) {
748 		dc->tdc_current = LIST_FIRST(&de->ud.td_duphead);
749 		MPASS(dc->tdc_current != NULL);
750 	}
751 	return (dc->tdc_current);
752 
753 out:
754 	dc->tdc_tree = de;
755 	dc->tdc_current = de;
756 	if (de != NULL && tmpfs_dirent_dup(de))
757 		dc->tdc_tree = tmpfs_dir_xlookup_hash(node,
758 		    de->td_hash);
759 	return (dc->tdc_current);
760 }
761 
762 /*
763  * Looks for a directory entry in the directory represented by node.
764  * 'cnp' describes the name of the entry to look for.  Note that the .
765  * and .. components are not allowed as they do not physically exist
766  * within directories.
767  *
768  * Returns a pointer to the entry when found, otherwise NULL.
769  */
770 struct tmpfs_dirent *
771 tmpfs_dir_lookup(struct tmpfs_node *node, struct tmpfs_node *f,
772     struct componentname *cnp)
773 {
774 	struct tmpfs_dir_duphead *duphead;
775 	struct tmpfs_dirent *de;
776 	uint32_t hash;
777 
778 	MPASS(IMPLIES(cnp->cn_namelen == 1, cnp->cn_nameptr[0] != '.'));
779 	MPASS(IMPLIES(cnp->cn_namelen == 2, !(cnp->cn_nameptr[0] == '.' &&
780 	    cnp->cn_nameptr[1] == '.')));
781 	TMPFS_VALIDATE_DIR(node);
782 
783 	hash = tmpfs_dirent_hash(cnp->cn_nameptr, cnp->cn_namelen);
784 	de = tmpfs_dir_xlookup_hash(node, hash);
785 	if (de != NULL && tmpfs_dirent_duphead(de)) {
786 		duphead = &de->ud.td_duphead;
787 		LIST_FOREACH(de, duphead, uh.td_dup.entries) {
788 			if (TMPFS_DIRENT_MATCHES(de, cnp->cn_nameptr,
789 			    cnp->cn_namelen))
790 				break;
791 		}
792 	} else if (de != NULL) {
793 		if (!TMPFS_DIRENT_MATCHES(de, cnp->cn_nameptr,
794 		    cnp->cn_namelen))
795 			de = NULL;
796 	}
797 	if (de != NULL && f != NULL && de->td_node != f)
798 		de = NULL;
799 
800 	return (de);
801 }
802 
803 /*
804  * Attach duplicate-cookie directory entry nde to dnode and insert to dupindex
805  * list, allocate new cookie value.
806  */
807 static void
808 tmpfs_dir_attach_dup(struct tmpfs_node *dnode,
809     struct tmpfs_dir_duphead *duphead, struct tmpfs_dirent *nde)
810 {
811 	struct tmpfs_dir_duphead *dupindex;
812 	struct tmpfs_dirent *de, *pde;
813 
814 	dupindex = &dnode->tn_dir.tn_dupindex;
815 	de = LIST_FIRST(dupindex);
816 	if (de == NULL || de->td_cookie < TMPFS_DIRCOOKIE_DUP_MAX) {
817 		if (de == NULL)
818 			nde->td_cookie = TMPFS_DIRCOOKIE_DUP_MIN;
819 		else
820 			nde->td_cookie = de->td_cookie + 1;
821 		MPASS(tmpfs_dirent_dup(nde));
822 		LIST_INSERT_HEAD(dupindex, nde, uh.td_dup.index_entries);
823 		LIST_INSERT_HEAD(duphead, nde, uh.td_dup.entries);
824 		return;
825 	}
826 
827 	/*
828 	 * Cookie numbers are near exhaustion. Scan dupindex list for unused
829 	 * numbers. dupindex list is sorted in descending order. Keep it so
830 	 * after inserting nde.
831 	 */
832 	while (1) {
833 		pde = de;
834 		de = LIST_NEXT(de, uh.td_dup.index_entries);
835 		if (de == NULL && pde->td_cookie != TMPFS_DIRCOOKIE_DUP_MIN) {
836 			/*
837 			 * Last element of the index doesn't have minimal cookie
838 			 * value, use it.
839 			 */
840 			nde->td_cookie = TMPFS_DIRCOOKIE_DUP_MIN;
841 			LIST_INSERT_AFTER(pde, nde, uh.td_dup.index_entries);
842 			LIST_INSERT_HEAD(duphead, nde, uh.td_dup.entries);
843 			return;
844 		} else if (de == NULL) {
845 			/*
846 			 * We are so lucky have 2^30 hash duplicates in single
847 			 * directory :) Return largest possible cookie value.
848 			 * It should be fine except possible issues with
849 			 * VOP_READDIR restart.
850 			 */
851 			nde->td_cookie = TMPFS_DIRCOOKIE_DUP_MAX;
852 			LIST_INSERT_HEAD(dupindex, nde,
853 			    uh.td_dup.index_entries);
854 			LIST_INSERT_HEAD(duphead, nde, uh.td_dup.entries);
855 			return;
856 		}
857 		if (de->td_cookie + 1 == pde->td_cookie ||
858 		    de->td_cookie >= TMPFS_DIRCOOKIE_DUP_MAX)
859 			continue;	/* No hole or invalid cookie. */
860 		nde->td_cookie = de->td_cookie + 1;
861 		MPASS(tmpfs_dirent_dup(nde));
862 		MPASS(pde->td_cookie > nde->td_cookie);
863 		MPASS(nde->td_cookie > de->td_cookie);
864 		LIST_INSERT_BEFORE(de, nde, uh.td_dup.index_entries);
865 		LIST_INSERT_HEAD(duphead, nde, uh.td_dup.entries);
866 		return;
867 	};
868 }
869 
870 /*
871  * Attaches the directory entry de to the directory represented by vp.
872  * Note that this does not change the link count of the node pointed by
873  * the directory entry, as this is done by tmpfs_alloc_dirent.
874  */
875 void
876 tmpfs_dir_attach(struct vnode *vp, struct tmpfs_dirent *de)
877 {
878 	struct tmpfs_node *dnode;
879 	struct tmpfs_dirent *xde, *nde;
880 
881 	ASSERT_VOP_ELOCKED(vp, __func__);
882 	MPASS(de->td_namelen > 0);
883 	MPASS(de->td_hash >= TMPFS_DIRCOOKIE_MIN);
884 	MPASS(de->td_cookie == de->td_hash);
885 
886 	dnode = VP_TO_TMPFS_DIR(vp);
887 	dnode->tn_dir.tn_readdir_lastn = 0;
888 	dnode->tn_dir.tn_readdir_lastp = NULL;
889 
890 	MPASS(!tmpfs_dirent_dup(de));
891 	xde = RB_INSERT(tmpfs_dir, &dnode->tn_dir.tn_dirhead, de);
892 	if (xde != NULL && tmpfs_dirent_duphead(xde))
893 		tmpfs_dir_attach_dup(dnode, &xde->ud.td_duphead, de);
894 	else if (xde != NULL) {
895 		/*
896 		 * Allocate new duphead. Swap xde with duphead to avoid
897 		 * adding/removing elements with the same hash.
898 		 */
899 		MPASS(!tmpfs_dirent_dup(xde));
900 		tmpfs_alloc_dirent(VFS_TO_TMPFS(vp->v_mount), NULL, NULL, 0,
901 		    &nde);
902 		/* *nde = *xde; XXX gcc 4.2.1 may generate invalid code. */
903 		memcpy(nde, xde, sizeof(*xde));
904 		xde->td_cookie |= TMPFS_DIRCOOKIE_DUPHEAD;
905 		LIST_INIT(&xde->ud.td_duphead);
906 		xde->td_namelen = 0;
907 		xde->td_node = NULL;
908 		tmpfs_dir_attach_dup(dnode, &xde->ud.td_duphead, nde);
909 		tmpfs_dir_attach_dup(dnode, &xde->ud.td_duphead, de);
910 	}
911 	dnode->tn_size += sizeof(struct tmpfs_dirent);
912 	dnode->tn_status |= TMPFS_NODE_ACCESSED | TMPFS_NODE_CHANGED | \
913 	    TMPFS_NODE_MODIFIED;
914 }
915 
916 /* --------------------------------------------------------------------- */
917 
918 /*
919  * Detaches the directory entry de from the directory represented by vp.
920  * Note that this does not change the link count of the node pointed by
921  * the directory entry, as this is done by tmpfs_free_dirent.
922  */
923 void
924 tmpfs_dir_detach(struct vnode *vp, struct tmpfs_dirent *de)
925 {
926 	struct tmpfs_mount *tmp;
927 	struct tmpfs_dir *head;
928 	struct tmpfs_node *dnode;
929 	struct tmpfs_dirent *xde;
930 
931 	ASSERT_VOP_ELOCKED(vp, __func__);
932 
933 	dnode = VP_TO_TMPFS_DIR(vp);
934 	head = &dnode->tn_dir.tn_dirhead;
935 	dnode->tn_dir.tn_readdir_lastn = 0;
936 	dnode->tn_dir.tn_readdir_lastp = NULL;
937 
938 	if (tmpfs_dirent_dup(de)) {
939 		/* Remove duphead if de was last entry. */
940 		if (LIST_NEXT(de, uh.td_dup.entries) == NULL) {
941 			xde = tmpfs_dir_xlookup_hash(dnode, de->td_hash);
942 			MPASS(tmpfs_dirent_duphead(xde));
943 		} else
944 			xde = NULL;
945 		LIST_REMOVE(de, uh.td_dup.entries);
946 		LIST_REMOVE(de, uh.td_dup.index_entries);
947 		if (xde != NULL) {
948 			if (LIST_EMPTY(&xde->ud.td_duphead)) {
949 				RB_REMOVE(tmpfs_dir, head, xde);
950 				tmp = VFS_TO_TMPFS(vp->v_mount);
951 				MPASS(xde->td_node == NULL);
952 				tmpfs_free_dirent(tmp, xde);
953 			}
954 		}
955 	} else
956 		RB_REMOVE(tmpfs_dir, head, de);
957 
958 	dnode->tn_size -= sizeof(struct tmpfs_dirent);
959 	dnode->tn_status |= TMPFS_NODE_ACCESSED | TMPFS_NODE_CHANGED | \
960 	    TMPFS_NODE_MODIFIED;
961 }
962 
963 void
964 tmpfs_dir_destroy(struct tmpfs_mount *tmp, struct tmpfs_node *dnode)
965 {
966 	struct tmpfs_dirent *de, *dde, *nde;
967 
968 	RB_FOREACH_SAFE(de, tmpfs_dir, &dnode->tn_dir.tn_dirhead, nde) {
969 		RB_REMOVE(tmpfs_dir, &dnode->tn_dir.tn_dirhead, de);
970 		/* Node may already be destroyed. */
971 		de->td_node = NULL;
972 		if (tmpfs_dirent_duphead(de)) {
973 			while ((dde = LIST_FIRST(&de->ud.td_duphead)) != NULL) {
974 				LIST_REMOVE(dde, uh.td_dup.entries);
975 				dde->td_node = NULL;
976 				tmpfs_free_dirent(tmp, dde);
977 			}
978 		}
979 		tmpfs_free_dirent(tmp, de);
980 	}
981 }
982 
983 /* --------------------------------------------------------------------- */
984 
985 /*
986  * Helper function for tmpfs_readdir.  Creates a '.' entry for the given
987  * directory and returns it in the uio space.  The function returns 0
988  * on success, -1 if there was not enough space in the uio structure to
989  * hold the directory entry or an appropriate error code if another
990  * error happens.
991  */
992 static int
993 tmpfs_dir_getdotdent(struct tmpfs_node *node, struct uio *uio)
994 {
995 	int error;
996 	struct dirent dent;
997 
998 	TMPFS_VALIDATE_DIR(node);
999 	MPASS(uio->uio_offset == TMPFS_DIRCOOKIE_DOT);
1000 
1001 	dent.d_fileno = node->tn_id;
1002 	dent.d_type = DT_DIR;
1003 	dent.d_namlen = 1;
1004 	dent.d_name[0] = '.';
1005 	dent.d_name[1] = '\0';
1006 	dent.d_reclen = GENERIC_DIRSIZ(&dent);
1007 
1008 	if (dent.d_reclen > uio->uio_resid)
1009 		error = EJUSTRETURN;
1010 	else
1011 		error = uiomove(&dent, dent.d_reclen, uio);
1012 
1013 	node->tn_status |= TMPFS_NODE_ACCESSED;
1014 
1015 	return error;
1016 }
1017 
1018 /* --------------------------------------------------------------------- */
1019 
1020 /*
1021  * Helper function for tmpfs_readdir.  Creates a '..' entry for the given
1022  * directory and returns it in the uio space.  The function returns 0
1023  * on success, -1 if there was not enough space in the uio structure to
1024  * hold the directory entry or an appropriate error code if another
1025  * error happens.
1026  */
1027 static int
1028 tmpfs_dir_getdotdotdent(struct tmpfs_node *node, struct uio *uio)
1029 {
1030 	int error;
1031 	struct dirent dent;
1032 
1033 	TMPFS_VALIDATE_DIR(node);
1034 	MPASS(uio->uio_offset == TMPFS_DIRCOOKIE_DOTDOT);
1035 
1036 	/*
1037 	 * Return ENOENT if the current node is already removed.
1038 	 */
1039 	TMPFS_ASSERT_LOCKED(node);
1040 	if (node->tn_dir.tn_parent == NULL) {
1041 		return (ENOENT);
1042 	}
1043 
1044 	TMPFS_NODE_LOCK(node->tn_dir.tn_parent);
1045 	dent.d_fileno = node->tn_dir.tn_parent->tn_id;
1046 	TMPFS_NODE_UNLOCK(node->tn_dir.tn_parent);
1047 
1048 	dent.d_type = DT_DIR;
1049 	dent.d_namlen = 2;
1050 	dent.d_name[0] = '.';
1051 	dent.d_name[1] = '.';
1052 	dent.d_name[2] = '\0';
1053 	dent.d_reclen = GENERIC_DIRSIZ(&dent);
1054 
1055 	if (dent.d_reclen > uio->uio_resid)
1056 		error = EJUSTRETURN;
1057 	else
1058 		error = uiomove(&dent, dent.d_reclen, uio);
1059 
1060 	node->tn_status |= TMPFS_NODE_ACCESSED;
1061 
1062 	return error;
1063 }
1064 
1065 /* --------------------------------------------------------------------- */
1066 
1067 /*
1068  * Helper function for tmpfs_readdir.  Returns as much directory entries
1069  * as can fit in the uio space.  The read starts at uio->uio_offset.
1070  * The function returns 0 on success, -1 if there was not enough space
1071  * in the uio structure to hold the directory entry or an appropriate
1072  * error code if another error happens.
1073  */
1074 int
1075 tmpfs_dir_getdents(struct tmpfs_node *node, struct uio *uio, int cnt,
1076     u_long *cookies, int *ncookies)
1077 {
1078 	struct tmpfs_dir_cursor dc;
1079 	struct tmpfs_dirent *de;
1080 	off_t off;
1081 	int error;
1082 
1083 	TMPFS_VALIDATE_DIR(node);
1084 
1085 	off = 0;
1086 	switch (uio->uio_offset) {
1087 	case TMPFS_DIRCOOKIE_DOT:
1088 		error = tmpfs_dir_getdotdent(node, uio);
1089 		if (error != 0)
1090 			return (error);
1091 		uio->uio_offset = TMPFS_DIRCOOKIE_DOTDOT;
1092 		if (cnt != 0)
1093 			cookies[(*ncookies)++] = off = uio->uio_offset;
1094 	case TMPFS_DIRCOOKIE_DOTDOT:
1095 		error = tmpfs_dir_getdotdotdent(node, uio);
1096 		if (error != 0)
1097 			return (error);
1098 		de = tmpfs_dir_first(node, &dc);
1099 		if (de == NULL)
1100 			uio->uio_offset = TMPFS_DIRCOOKIE_EOF;
1101 		else
1102 			uio->uio_offset = tmpfs_dirent_cookie(de);
1103 		if (cnt != 0)
1104 			cookies[(*ncookies)++] = off = uio->uio_offset;
1105 		if (de == NULL)
1106 			return (0);
1107 		break;
1108 	case TMPFS_DIRCOOKIE_EOF:
1109 		return (0);
1110 	default:
1111 		de = tmpfs_dir_lookup_cookie(node, uio->uio_offset, &dc);
1112 		if (de == NULL)
1113 			return (EINVAL);
1114 		if (cnt != 0)
1115 			off = tmpfs_dirent_cookie(de);
1116 	}
1117 
1118 	/* Read as much entries as possible; i.e., until we reach the end of
1119 	 * the directory or we exhaust uio space. */
1120 	do {
1121 		struct dirent d;
1122 
1123 		/* Create a dirent structure representing the current
1124 		 * tmpfs_node and fill it. */
1125 		if (de->td_node == NULL) {
1126 			d.d_fileno = 1;
1127 			d.d_type = DT_WHT;
1128 		} else {
1129 			d.d_fileno = de->td_node->tn_id;
1130 			switch (de->td_node->tn_type) {
1131 			case VBLK:
1132 				d.d_type = DT_BLK;
1133 				break;
1134 
1135 			case VCHR:
1136 				d.d_type = DT_CHR;
1137 				break;
1138 
1139 			case VDIR:
1140 				d.d_type = DT_DIR;
1141 				break;
1142 
1143 			case VFIFO:
1144 				d.d_type = DT_FIFO;
1145 				break;
1146 
1147 			case VLNK:
1148 				d.d_type = DT_LNK;
1149 				break;
1150 
1151 			case VREG:
1152 				d.d_type = DT_REG;
1153 				break;
1154 
1155 			case VSOCK:
1156 				d.d_type = DT_SOCK;
1157 				break;
1158 
1159 			default:
1160 				panic("tmpfs_dir_getdents: type %p %d",
1161 				    de->td_node, (int)de->td_node->tn_type);
1162 			}
1163 		}
1164 		d.d_namlen = de->td_namelen;
1165 		MPASS(de->td_namelen < sizeof(d.d_name));
1166 		(void)memcpy(d.d_name, de->ud.td_name, de->td_namelen);
1167 		d.d_name[de->td_namelen] = '\0';
1168 		d.d_reclen = GENERIC_DIRSIZ(&d);
1169 
1170 		/* Stop reading if the directory entry we are treating is
1171 		 * bigger than the amount of data that can be returned. */
1172 		if (d.d_reclen > uio->uio_resid) {
1173 			error = EJUSTRETURN;
1174 			break;
1175 		}
1176 
1177 		/* Copy the new dirent structure into the output buffer and
1178 		 * advance pointers. */
1179 		error = uiomove(&d, d.d_reclen, uio);
1180 		if (error == 0) {
1181 			de = tmpfs_dir_next(node, &dc);
1182 			if (cnt != 0) {
1183 				if (de == NULL)
1184 					off = TMPFS_DIRCOOKIE_EOF;
1185 				else
1186 					off = tmpfs_dirent_cookie(de);
1187 				MPASS(*ncookies < cnt);
1188 				cookies[(*ncookies)++] = off;
1189 			}
1190 		}
1191 	} while (error == 0 && uio->uio_resid > 0 && de != NULL);
1192 
1193 	/* Update the offset and cache. */
1194 	if (cnt == 0) {
1195 		if (de == NULL)
1196 			off = TMPFS_DIRCOOKIE_EOF;
1197 		else
1198 			off = tmpfs_dirent_cookie(de);
1199 	}
1200 
1201 	uio->uio_offset = off;
1202 	node->tn_dir.tn_readdir_lastn = off;
1203 	node->tn_dir.tn_readdir_lastp = de;
1204 
1205 	node->tn_status |= TMPFS_NODE_ACCESSED;
1206 	return error;
1207 }
1208 
1209 int
1210 tmpfs_dir_whiteout_add(struct vnode *dvp, struct componentname *cnp)
1211 {
1212 	struct tmpfs_dirent *de;
1213 	int error;
1214 
1215 	error = tmpfs_alloc_dirent(VFS_TO_TMPFS(dvp->v_mount), NULL,
1216 	    cnp->cn_nameptr, cnp->cn_namelen, &de);
1217 	if (error != 0)
1218 		return (error);
1219 	tmpfs_dir_attach(dvp, de);
1220 	return (0);
1221 }
1222 
1223 void
1224 tmpfs_dir_whiteout_remove(struct vnode *dvp, struct componentname *cnp)
1225 {
1226 	struct tmpfs_dirent *de;
1227 
1228 	de = tmpfs_dir_lookup(VP_TO_TMPFS_DIR(dvp), NULL, cnp);
1229 	MPASS(de != NULL && de->td_node == NULL);
1230 	tmpfs_dir_detach(dvp, de);
1231 	tmpfs_free_dirent(VFS_TO_TMPFS(dvp->v_mount), de);
1232 }
1233 
1234 /* --------------------------------------------------------------------- */
1235 
1236 /*
1237  * Resizes the aobj associated with the regular file pointed to by 'vp' to the
1238  * size 'newsize'.  'vp' must point to a vnode that represents a regular file.
1239  * 'newsize' must be positive.
1240  *
1241  * Returns zero on success or an appropriate error code on failure.
1242  */
1243 int
1244 tmpfs_reg_resize(struct vnode *vp, off_t newsize, boolean_t ignerr)
1245 {
1246 	struct tmpfs_mount *tmp;
1247 	struct tmpfs_node *node;
1248 	vm_object_t uobj;
1249 	vm_page_t m, ma[1];
1250 	vm_pindex_t idx, newpages, oldpages;
1251 	off_t oldsize;
1252 	int base, rv;
1253 
1254 	MPASS(vp->v_type == VREG);
1255 	MPASS(newsize >= 0);
1256 
1257 	node = VP_TO_TMPFS_NODE(vp);
1258 	uobj = node->tn_reg.tn_aobj;
1259 	tmp = VFS_TO_TMPFS(vp->v_mount);
1260 
1261 	/*
1262 	 * Convert the old and new sizes to the number of pages needed to
1263 	 * store them.  It may happen that we do not need to do anything
1264 	 * because the last allocated page can accommodate the change on
1265 	 * its own.
1266 	 */
1267 	oldsize = node->tn_size;
1268 	oldpages = OFF_TO_IDX(oldsize + PAGE_MASK);
1269 	MPASS(oldpages == uobj->size);
1270 	newpages = OFF_TO_IDX(newsize + PAGE_MASK);
1271 	if (newpages > oldpages &&
1272 	    tmpfs_pages_check_avail(tmp, newpages - oldpages) == 0)
1273 		return (ENOSPC);
1274 
1275 	VM_OBJECT_WLOCK(uobj);
1276 	if (newsize < oldsize) {
1277 		/*
1278 		 * Zero the truncated part of the last page.
1279 		 */
1280 		base = newsize & PAGE_MASK;
1281 		if (base != 0) {
1282 			idx = OFF_TO_IDX(newsize);
1283 retry:
1284 			m = vm_page_lookup(uobj, idx);
1285 			if (m != NULL) {
1286 				if ((m->oflags & VPO_BUSY) != 0 ||
1287 				    m->busy != 0) {
1288 					vm_page_sleep(m, "tmfssz");
1289 					goto retry;
1290 				}
1291 				MPASS(m->valid == VM_PAGE_BITS_ALL);
1292 			} else if (vm_pager_has_page(uobj, idx, NULL, NULL)) {
1293 				m = vm_page_alloc(uobj, idx, VM_ALLOC_NORMAL);
1294 				if (m == NULL) {
1295 					VM_OBJECT_WUNLOCK(uobj);
1296 					VM_WAIT;
1297 					VM_OBJECT_WLOCK(uobj);
1298 					goto retry;
1299 				} else if (m->valid != VM_PAGE_BITS_ALL) {
1300 					ma[0] = m;
1301 					rv = vm_pager_get_pages(uobj, ma, 1, 0);
1302 					m = vm_page_lookup(uobj, idx);
1303 				} else
1304 					/* A cached page was reactivated. */
1305 					rv = VM_PAGER_OK;
1306 				vm_page_lock(m);
1307 				if (rv == VM_PAGER_OK) {
1308 					vm_page_deactivate(m);
1309 					vm_page_unlock(m);
1310 					vm_page_wakeup(m);
1311 				} else {
1312 					vm_page_free(m);
1313 					vm_page_unlock(m);
1314 					if (ignerr)
1315 						m = NULL;
1316 					else {
1317 						VM_OBJECT_WUNLOCK(uobj);
1318 						return (EIO);
1319 					}
1320 				}
1321 			}
1322 			if (m != NULL) {
1323 				pmap_zero_page_area(m, base, PAGE_SIZE - base);
1324 				vm_page_dirty(m);
1325 				vm_pager_page_unswapped(m);
1326 			}
1327 		}
1328 
1329 		/*
1330 		 * Release any swap space and free any whole pages.
1331 		 */
1332 		if (newpages < oldpages) {
1333 			swap_pager_freespace(uobj, newpages, oldpages -
1334 			    newpages);
1335 			vm_object_page_remove(uobj, newpages, 0, 0);
1336 		}
1337 	}
1338 	uobj->size = newpages;
1339 	VM_OBJECT_WUNLOCK(uobj);
1340 
1341 	TMPFS_LOCK(tmp);
1342 	tmp->tm_pages_used += (newpages - oldpages);
1343 	TMPFS_UNLOCK(tmp);
1344 
1345 	node->tn_size = newsize;
1346 	vnode_pager_setsize(vp, newsize);
1347 	return (0);
1348 }
1349 
1350 /* --------------------------------------------------------------------- */
1351 
1352 /*
1353  * Change flags of the given vnode.
1354  * Caller should execute tmpfs_update on vp after a successful execution.
1355  * The vnode must be locked on entry and remain locked on exit.
1356  */
1357 int
1358 tmpfs_chflags(struct vnode *vp, u_long flags, struct ucred *cred,
1359     struct thread *p)
1360 {
1361 	int error;
1362 	struct tmpfs_node *node;
1363 
1364 	MPASS(VOP_ISLOCKED(vp));
1365 
1366 	node = VP_TO_TMPFS_NODE(vp);
1367 
1368 	if ((flags & ~(UF_NODUMP | UF_IMMUTABLE | UF_APPEND | UF_OPAQUE |
1369 	    UF_NOUNLINK | SF_ARCHIVED | SF_IMMUTABLE | SF_APPEND |
1370 	    SF_NOUNLINK)) != 0)
1371 		return (EOPNOTSUPP);
1372 
1373 	/* Disallow this operation if the file system is mounted read-only. */
1374 	if (vp->v_mount->mnt_flag & MNT_RDONLY)
1375 		return EROFS;
1376 
1377 	/*
1378 	 * Callers may only modify the file flags on objects they
1379 	 * have VADMIN rights for.
1380 	 */
1381 	if ((error = VOP_ACCESS(vp, VADMIN, cred, p)))
1382 		return (error);
1383 	/*
1384 	 * Unprivileged processes are not permitted to unset system
1385 	 * flags, or modify flags if any system flags are set.
1386 	 */
1387 	if (!priv_check_cred(cred, PRIV_VFS_SYSFLAGS, 0)) {
1388 		if (node->tn_flags &
1389 		    (SF_NOUNLINK | SF_IMMUTABLE | SF_APPEND)) {
1390 			error = securelevel_gt(cred, 0);
1391 			if (error)
1392 				return (error);
1393 		}
1394 	} else {
1395 		if (node->tn_flags &
1396 		    (SF_NOUNLINK | SF_IMMUTABLE | SF_APPEND) ||
1397 		    ((flags ^ node->tn_flags) & SF_SETTABLE))
1398 			return (EPERM);
1399 	}
1400 	node->tn_flags = flags;
1401 	node->tn_status |= TMPFS_NODE_CHANGED;
1402 
1403 	MPASS(VOP_ISLOCKED(vp));
1404 
1405 	return 0;
1406 }
1407 
1408 /* --------------------------------------------------------------------- */
1409 
1410 /*
1411  * Change access mode on the given vnode.
1412  * Caller should execute tmpfs_update on vp after a successful execution.
1413  * The vnode must be locked on entry and remain locked on exit.
1414  */
1415 int
1416 tmpfs_chmod(struct vnode *vp, mode_t mode, struct ucred *cred, struct thread *p)
1417 {
1418 	int error;
1419 	struct tmpfs_node *node;
1420 
1421 	MPASS(VOP_ISLOCKED(vp));
1422 
1423 	node = VP_TO_TMPFS_NODE(vp);
1424 
1425 	/* Disallow this operation if the file system is mounted read-only. */
1426 	if (vp->v_mount->mnt_flag & MNT_RDONLY)
1427 		return EROFS;
1428 
1429 	/* Immutable or append-only files cannot be modified, either. */
1430 	if (node->tn_flags & (IMMUTABLE | APPEND))
1431 		return EPERM;
1432 
1433 	/*
1434 	 * To modify the permissions on a file, must possess VADMIN
1435 	 * for that file.
1436 	 */
1437 	if ((error = VOP_ACCESS(vp, VADMIN, cred, p)))
1438 		return (error);
1439 
1440 	/*
1441 	 * Privileged processes may set the sticky bit on non-directories,
1442 	 * as well as set the setgid bit on a file with a group that the
1443 	 * process is not a member of.
1444 	 */
1445 	if (vp->v_type != VDIR && (mode & S_ISTXT)) {
1446 		if (priv_check_cred(cred, PRIV_VFS_STICKYFILE, 0))
1447 			return (EFTYPE);
1448 	}
1449 	if (!groupmember(node->tn_gid, cred) && (mode & S_ISGID)) {
1450 		error = priv_check_cred(cred, PRIV_VFS_SETGID, 0);
1451 		if (error)
1452 			return (error);
1453 	}
1454 
1455 
1456 	node->tn_mode &= ~ALLPERMS;
1457 	node->tn_mode |= mode & ALLPERMS;
1458 
1459 	node->tn_status |= TMPFS_NODE_CHANGED;
1460 
1461 	MPASS(VOP_ISLOCKED(vp));
1462 
1463 	return 0;
1464 }
1465 
1466 /* --------------------------------------------------------------------- */
1467 
1468 /*
1469  * Change ownership of the given vnode.  At least one of uid or gid must
1470  * be different than VNOVAL.  If one is set to that value, the attribute
1471  * is unchanged.
1472  * Caller should execute tmpfs_update on vp after a successful execution.
1473  * The vnode must be locked on entry and remain locked on exit.
1474  */
1475 int
1476 tmpfs_chown(struct vnode *vp, uid_t uid, gid_t gid, struct ucred *cred,
1477     struct thread *p)
1478 {
1479 	int error;
1480 	struct tmpfs_node *node;
1481 	uid_t ouid;
1482 	gid_t ogid;
1483 
1484 	MPASS(VOP_ISLOCKED(vp));
1485 
1486 	node = VP_TO_TMPFS_NODE(vp);
1487 
1488 	/* Assign default values if they are unknown. */
1489 	MPASS(uid != VNOVAL || gid != VNOVAL);
1490 	if (uid == VNOVAL)
1491 		uid = node->tn_uid;
1492 	if (gid == VNOVAL)
1493 		gid = node->tn_gid;
1494 	MPASS(uid != VNOVAL && gid != VNOVAL);
1495 
1496 	/* Disallow this operation if the file system is mounted read-only. */
1497 	if (vp->v_mount->mnt_flag & MNT_RDONLY)
1498 		return EROFS;
1499 
1500 	/* Immutable or append-only files cannot be modified, either. */
1501 	if (node->tn_flags & (IMMUTABLE | APPEND))
1502 		return EPERM;
1503 
1504 	/*
1505 	 * To modify the ownership of a file, must possess VADMIN for that
1506 	 * file.
1507 	 */
1508 	if ((error = VOP_ACCESS(vp, VADMIN, cred, p)))
1509 		return (error);
1510 
1511 	/*
1512 	 * To change the owner of a file, or change the group of a file to a
1513 	 * group of which we are not a member, the caller must have
1514 	 * privilege.
1515 	 */
1516 	if ((uid != node->tn_uid ||
1517 	    (gid != node->tn_gid && !groupmember(gid, cred))) &&
1518 	    (error = priv_check_cred(cred, PRIV_VFS_CHOWN, 0)))
1519 		return (error);
1520 
1521 	ogid = node->tn_gid;
1522 	ouid = node->tn_uid;
1523 
1524 	node->tn_uid = uid;
1525 	node->tn_gid = gid;
1526 
1527 	node->tn_status |= TMPFS_NODE_CHANGED;
1528 
1529 	if ((node->tn_mode & (S_ISUID | S_ISGID)) && (ouid != uid || ogid != gid)) {
1530 		if (priv_check_cred(cred, PRIV_VFS_RETAINSUGID, 0))
1531 			node->tn_mode &= ~(S_ISUID | S_ISGID);
1532 	}
1533 
1534 	MPASS(VOP_ISLOCKED(vp));
1535 
1536 	return 0;
1537 }
1538 
1539 /* --------------------------------------------------------------------- */
1540 
1541 /*
1542  * Change size of the given vnode.
1543  * Caller should execute tmpfs_update on vp after a successful execution.
1544  * The vnode must be locked on entry and remain locked on exit.
1545  */
1546 int
1547 tmpfs_chsize(struct vnode *vp, u_quad_t size, struct ucred *cred,
1548     struct thread *p)
1549 {
1550 	int error;
1551 	struct tmpfs_node *node;
1552 
1553 	MPASS(VOP_ISLOCKED(vp));
1554 
1555 	node = VP_TO_TMPFS_NODE(vp);
1556 
1557 	/* Decide whether this is a valid operation based on the file type. */
1558 	error = 0;
1559 	switch (vp->v_type) {
1560 	case VDIR:
1561 		return EISDIR;
1562 
1563 	case VREG:
1564 		if (vp->v_mount->mnt_flag & MNT_RDONLY)
1565 			return EROFS;
1566 		break;
1567 
1568 	case VBLK:
1569 		/* FALLTHROUGH */
1570 	case VCHR:
1571 		/* FALLTHROUGH */
1572 	case VFIFO:
1573 		/* Allow modifications of special files even if in the file
1574 		 * system is mounted read-only (we are not modifying the
1575 		 * files themselves, but the objects they represent). */
1576 		return 0;
1577 
1578 	default:
1579 		/* Anything else is unsupported. */
1580 		return EOPNOTSUPP;
1581 	}
1582 
1583 	/* Immutable or append-only files cannot be modified, either. */
1584 	if (node->tn_flags & (IMMUTABLE | APPEND))
1585 		return EPERM;
1586 
1587 	error = tmpfs_truncate(vp, size);
1588 	/* tmpfs_truncate will raise the NOTE_EXTEND and NOTE_ATTRIB kevents
1589 	 * for us, as will update tn_status; no need to do that here. */
1590 
1591 	MPASS(VOP_ISLOCKED(vp));
1592 
1593 	return error;
1594 }
1595 
1596 /* --------------------------------------------------------------------- */
1597 
1598 /*
1599  * Change access and modification times of the given vnode.
1600  * Caller should execute tmpfs_update on vp after a successful execution.
1601  * The vnode must be locked on entry and remain locked on exit.
1602  */
1603 int
1604 tmpfs_chtimes(struct vnode *vp, struct timespec *atime, struct timespec *mtime,
1605 	struct timespec *birthtime, int vaflags, struct ucred *cred, struct thread *l)
1606 {
1607 	int error;
1608 	struct tmpfs_node *node;
1609 
1610 	MPASS(VOP_ISLOCKED(vp));
1611 
1612 	node = VP_TO_TMPFS_NODE(vp);
1613 
1614 	/* Disallow this operation if the file system is mounted read-only. */
1615 	if (vp->v_mount->mnt_flag & MNT_RDONLY)
1616 		return EROFS;
1617 
1618 	/* Immutable or append-only files cannot be modified, either. */
1619 	if (node->tn_flags & (IMMUTABLE | APPEND))
1620 		return EPERM;
1621 
1622 	/* Determine if the user have proper privilege to update time. */
1623 	if (vaflags & VA_UTIMES_NULL) {
1624 		error = VOP_ACCESS(vp, VADMIN, cred, l);
1625 		if (error)
1626 			error = VOP_ACCESS(vp, VWRITE, cred, l);
1627 	} else
1628 		error = VOP_ACCESS(vp, VADMIN, cred, l);
1629 	if (error)
1630 		return (error);
1631 
1632 	if (atime->tv_sec != VNOVAL && atime->tv_nsec != VNOVAL)
1633 		node->tn_status |= TMPFS_NODE_ACCESSED;
1634 
1635 	if (mtime->tv_sec != VNOVAL && mtime->tv_nsec != VNOVAL)
1636 		node->tn_status |= TMPFS_NODE_MODIFIED;
1637 
1638 	if (birthtime->tv_nsec != VNOVAL && birthtime->tv_nsec != VNOVAL)
1639 		node->tn_status |= TMPFS_NODE_MODIFIED;
1640 
1641 	tmpfs_itimes(vp, atime, mtime);
1642 
1643 	if (birthtime->tv_nsec != VNOVAL && birthtime->tv_nsec != VNOVAL)
1644 		node->tn_birthtime = *birthtime;
1645 	MPASS(VOP_ISLOCKED(vp));
1646 
1647 	return 0;
1648 }
1649 
1650 /* --------------------------------------------------------------------- */
1651 /* Sync timestamps */
1652 void
1653 tmpfs_itimes(struct vnode *vp, const struct timespec *acc,
1654     const struct timespec *mod)
1655 {
1656 	struct tmpfs_node *node;
1657 	struct timespec now;
1658 
1659 	node = VP_TO_TMPFS_NODE(vp);
1660 
1661 	if ((node->tn_status & (TMPFS_NODE_ACCESSED | TMPFS_NODE_MODIFIED |
1662 	    TMPFS_NODE_CHANGED)) == 0)
1663 		return;
1664 
1665 	vfs_timestamp(&now);
1666 	if (node->tn_status & TMPFS_NODE_ACCESSED) {
1667 		if (acc == NULL)
1668 			 acc = &now;
1669 		node->tn_atime = *acc;
1670 	}
1671 	if (node->tn_status & TMPFS_NODE_MODIFIED) {
1672 		if (mod == NULL)
1673 			mod = &now;
1674 		node->tn_mtime = *mod;
1675 	}
1676 	if (node->tn_status & TMPFS_NODE_CHANGED) {
1677 		node->tn_ctime = now;
1678 	}
1679 	node->tn_status &=
1680 	    ~(TMPFS_NODE_ACCESSED | TMPFS_NODE_MODIFIED | TMPFS_NODE_CHANGED);
1681 }
1682 
1683 /* --------------------------------------------------------------------- */
1684 
1685 void
1686 tmpfs_update(struct vnode *vp)
1687 {
1688 
1689 	tmpfs_itimes(vp, NULL, NULL);
1690 }
1691 
1692 /* --------------------------------------------------------------------- */
1693 
1694 int
1695 tmpfs_truncate(struct vnode *vp, off_t length)
1696 {
1697 	int error;
1698 	struct tmpfs_node *node;
1699 
1700 	node = VP_TO_TMPFS_NODE(vp);
1701 
1702 	if (length < 0) {
1703 		error = EINVAL;
1704 		goto out;
1705 	}
1706 
1707 	if (node->tn_size == length) {
1708 		error = 0;
1709 		goto out;
1710 	}
1711 
1712 	if (length > VFS_TO_TMPFS(vp->v_mount)->tm_maxfilesize)
1713 		return (EFBIG);
1714 
1715 	error = tmpfs_reg_resize(vp, length, FALSE);
1716 	if (error == 0) {
1717 		node->tn_status |= TMPFS_NODE_CHANGED | TMPFS_NODE_MODIFIED;
1718 	}
1719 
1720 out:
1721 	tmpfs_update(vp);
1722 
1723 	return error;
1724 }
1725 
1726 static __inline int
1727 tmpfs_dirtree_cmp(struct tmpfs_dirent *a, struct tmpfs_dirent *b)
1728 {
1729 	if (a->td_hash > b->td_hash)
1730 		return (1);
1731 	else if (a->td_hash < b->td_hash)
1732 		return (-1);
1733 	return (0);
1734 }
1735 
1736 RB_GENERATE_STATIC(tmpfs_dir, tmpfs_dirent, uh.td_entries, tmpfs_dirtree_cmp);
1737