xref: /openbmc/linux/fs/kernfs/dir.c (revision 2a12187d)
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * fs/kernfs/dir.c - kernfs directory implementation
4  *
5  * Copyright (c) 2001-3 Patrick Mochel
6  * Copyright (c) 2007 SUSE Linux Products GmbH
7  * Copyright (c) 2007, 2013 Tejun Heo <tj@kernel.org>
8  */
9 
10 #include <linux/sched.h>
11 #include <linux/fs.h>
12 #include <linux/namei.h>
13 #include <linux/idr.h>
14 #include <linux/slab.h>
15 #include <linux/security.h>
16 #include <linux/hash.h>
17 
18 #include "kernfs-internal.h"
19 
20 static DEFINE_SPINLOCK(kernfs_rename_lock);	/* kn->parent and ->name */
21 /*
22  * Don't use rename_lock to piggy back on pr_cont_buf. We don't want to
23  * call pr_cont() while holding rename_lock. Because sometimes pr_cont()
24  * will perform wakeups when releasing console_sem. Holding rename_lock
25  * will introduce deadlock if the scheduler reads the kernfs_name in the
26  * wakeup path.
27  */
28 static DEFINE_SPINLOCK(kernfs_pr_cont_lock);
29 static char kernfs_pr_cont_buf[PATH_MAX];	/* protected by pr_cont_lock */
30 static DEFINE_SPINLOCK(kernfs_idr_lock);	/* root->ino_idr */
31 
32 #define rb_to_kn(X) rb_entry((X), struct kernfs_node, rb)
33 
34 static bool __kernfs_active(struct kernfs_node *kn)
35 {
36 	return atomic_read(&kn->active) >= 0;
37 }
38 
39 static bool kernfs_active(struct kernfs_node *kn)
40 {
41 	lockdep_assert_held(&kernfs_root(kn)->kernfs_rwsem);
42 	return __kernfs_active(kn);
43 }
44 
45 static bool kernfs_lockdep(struct kernfs_node *kn)
46 {
47 #ifdef CONFIG_DEBUG_LOCK_ALLOC
48 	return kn->flags & KERNFS_LOCKDEP;
49 #else
50 	return false;
51 #endif
52 }
53 
54 static int kernfs_name_locked(struct kernfs_node *kn, char *buf, size_t buflen)
55 {
56 	if (!kn)
57 		return strlcpy(buf, "(null)", buflen);
58 
59 	return strlcpy(buf, kn->parent ? kn->name : "/", buflen);
60 }
61 
62 /* kernfs_node_depth - compute depth from @from to @to */
63 static size_t kernfs_depth(struct kernfs_node *from, struct kernfs_node *to)
64 {
65 	size_t depth = 0;
66 
67 	while (to->parent && to != from) {
68 		depth++;
69 		to = to->parent;
70 	}
71 	return depth;
72 }
73 
74 static struct kernfs_node *kernfs_common_ancestor(struct kernfs_node *a,
75 						  struct kernfs_node *b)
76 {
77 	size_t da, db;
78 	struct kernfs_root *ra = kernfs_root(a), *rb = kernfs_root(b);
79 
80 	if (ra != rb)
81 		return NULL;
82 
83 	da = kernfs_depth(ra->kn, a);
84 	db = kernfs_depth(rb->kn, b);
85 
86 	while (da > db) {
87 		a = a->parent;
88 		da--;
89 	}
90 	while (db > da) {
91 		b = b->parent;
92 		db--;
93 	}
94 
95 	/* worst case b and a will be the same at root */
96 	while (b != a) {
97 		b = b->parent;
98 		a = a->parent;
99 	}
100 
101 	return a;
102 }
103 
104 /**
105  * kernfs_path_from_node_locked - find a pseudo-absolute path to @kn_to,
106  * where kn_from is treated as root of the path.
107  * @kn_from: kernfs node which should be treated as root for the path
108  * @kn_to: kernfs node to which path is needed
109  * @buf: buffer to copy the path into
110  * @buflen: size of @buf
111  *
112  * We need to handle couple of scenarios here:
113  * [1] when @kn_from is an ancestor of @kn_to at some level
114  * kn_from: /n1/n2/n3
115  * kn_to:   /n1/n2/n3/n4/n5
116  * result:  /n4/n5
117  *
118  * [2] when @kn_from is on a different hierarchy and we need to find common
119  * ancestor between @kn_from and @kn_to.
120  * kn_from: /n1/n2/n3/n4
121  * kn_to:   /n1/n2/n5
122  * result:  /../../n5
123  * OR
124  * kn_from: /n1/n2/n3/n4/n5   [depth=5]
125  * kn_to:   /n1/n2/n3         [depth=3]
126  * result:  /../..
127  *
128  * [3] when @kn_to is %NULL result will be "(null)"
129  *
130  * Return: the length of the full path.  If the full length is equal to or
131  * greater than @buflen, @buf contains the truncated path with the trailing
132  * '\0'.  On error, -errno is returned.
133  */
134 static int kernfs_path_from_node_locked(struct kernfs_node *kn_to,
135 					struct kernfs_node *kn_from,
136 					char *buf, size_t buflen)
137 {
138 	struct kernfs_node *kn, *common;
139 	const char parent_str[] = "/..";
140 	size_t depth_from, depth_to, len = 0;
141 	int i, j;
142 
143 	if (!kn_to)
144 		return strlcpy(buf, "(null)", buflen);
145 
146 	if (!kn_from)
147 		kn_from = kernfs_root(kn_to)->kn;
148 
149 	if (kn_from == kn_to)
150 		return strlcpy(buf, "/", buflen);
151 
152 	if (!buf)
153 		return -EINVAL;
154 
155 	common = kernfs_common_ancestor(kn_from, kn_to);
156 	if (WARN_ON(!common))
157 		return -EINVAL;
158 
159 	depth_to = kernfs_depth(common, kn_to);
160 	depth_from = kernfs_depth(common, kn_from);
161 
162 	buf[0] = '\0';
163 
164 	for (i = 0; i < depth_from; i++)
165 		len += strlcpy(buf + len, parent_str,
166 			       len < buflen ? buflen - len : 0);
167 
168 	/* Calculate how many bytes we need for the rest */
169 	for (i = depth_to - 1; i >= 0; i--) {
170 		for (kn = kn_to, j = 0; j < i; j++)
171 			kn = kn->parent;
172 		len += strlcpy(buf + len, "/",
173 			       len < buflen ? buflen - len : 0);
174 		len += strlcpy(buf + len, kn->name,
175 			       len < buflen ? buflen - len : 0);
176 	}
177 
178 	return len;
179 }
180 
181 /**
182  * kernfs_name - obtain the name of a given node
183  * @kn: kernfs_node of interest
184  * @buf: buffer to copy @kn's name into
185  * @buflen: size of @buf
186  *
187  * Copies the name of @kn into @buf of @buflen bytes.  The behavior is
188  * similar to strlcpy().
189  *
190  * Fills buffer with "(null)" if @kn is %NULL.
191  *
192  * Return: the length of @kn's name and if @buf isn't long enough,
193  * it's filled up to @buflen-1 and nul terminated.
194  *
195  * This function can be called from any context.
196  */
197 int kernfs_name(struct kernfs_node *kn, char *buf, size_t buflen)
198 {
199 	unsigned long flags;
200 	int ret;
201 
202 	spin_lock_irqsave(&kernfs_rename_lock, flags);
203 	ret = kernfs_name_locked(kn, buf, buflen);
204 	spin_unlock_irqrestore(&kernfs_rename_lock, flags);
205 	return ret;
206 }
207 
208 /**
209  * kernfs_path_from_node - build path of node @to relative to @from.
210  * @from: parent kernfs_node relative to which we need to build the path
211  * @to: kernfs_node of interest
212  * @buf: buffer to copy @to's path into
213  * @buflen: size of @buf
214  *
215  * Builds @to's path relative to @from in @buf. @from and @to must
216  * be on the same kernfs-root. If @from is not parent of @to, then a relative
217  * path (which includes '..'s) as needed to reach from @from to @to is
218  * returned.
219  *
220  * Return: the length of the full path.  If the full length is equal to or
221  * greater than @buflen, @buf contains the truncated path with the trailing
222  * '\0'.  On error, -errno is returned.
223  */
224 int kernfs_path_from_node(struct kernfs_node *to, struct kernfs_node *from,
225 			  char *buf, size_t buflen)
226 {
227 	unsigned long flags;
228 	int ret;
229 
230 	spin_lock_irqsave(&kernfs_rename_lock, flags);
231 	ret = kernfs_path_from_node_locked(to, from, buf, buflen);
232 	spin_unlock_irqrestore(&kernfs_rename_lock, flags);
233 	return ret;
234 }
235 EXPORT_SYMBOL_GPL(kernfs_path_from_node);
236 
237 /**
238  * pr_cont_kernfs_name - pr_cont name of a kernfs_node
239  * @kn: kernfs_node of interest
240  *
241  * This function can be called from any context.
242  */
243 void pr_cont_kernfs_name(struct kernfs_node *kn)
244 {
245 	unsigned long flags;
246 
247 	spin_lock_irqsave(&kernfs_pr_cont_lock, flags);
248 
249 	kernfs_name(kn, kernfs_pr_cont_buf, sizeof(kernfs_pr_cont_buf));
250 	pr_cont("%s", kernfs_pr_cont_buf);
251 
252 	spin_unlock_irqrestore(&kernfs_pr_cont_lock, flags);
253 }
254 
255 /**
256  * pr_cont_kernfs_path - pr_cont path of a kernfs_node
257  * @kn: kernfs_node of interest
258  *
259  * This function can be called from any context.
260  */
261 void pr_cont_kernfs_path(struct kernfs_node *kn)
262 {
263 	unsigned long flags;
264 	int sz;
265 
266 	spin_lock_irqsave(&kernfs_pr_cont_lock, flags);
267 
268 	sz = kernfs_path_from_node(kn, NULL, kernfs_pr_cont_buf,
269 				   sizeof(kernfs_pr_cont_buf));
270 	if (sz < 0) {
271 		pr_cont("(error)");
272 		goto out;
273 	}
274 
275 	if (sz >= sizeof(kernfs_pr_cont_buf)) {
276 		pr_cont("(name too long)");
277 		goto out;
278 	}
279 
280 	pr_cont("%s", kernfs_pr_cont_buf);
281 
282 out:
283 	spin_unlock_irqrestore(&kernfs_pr_cont_lock, flags);
284 }
285 
286 /**
287  * kernfs_get_parent - determine the parent node and pin it
288  * @kn: kernfs_node of interest
289  *
290  * Determines @kn's parent, pins and returns it.  This function can be
291  * called from any context.
292  *
293  * Return: parent node of @kn
294  */
295 struct kernfs_node *kernfs_get_parent(struct kernfs_node *kn)
296 {
297 	struct kernfs_node *parent;
298 	unsigned long flags;
299 
300 	spin_lock_irqsave(&kernfs_rename_lock, flags);
301 	parent = kn->parent;
302 	kernfs_get(parent);
303 	spin_unlock_irqrestore(&kernfs_rename_lock, flags);
304 
305 	return parent;
306 }
307 
308 /**
309  *	kernfs_name_hash - calculate hash of @ns + @name
310  *	@name: Null terminated string to hash
311  *	@ns:   Namespace tag to hash
312  *
313  *	Return: 31-bit hash of ns + name (so it fits in an off_t)
314  */
315 static unsigned int kernfs_name_hash(const char *name, const void *ns)
316 {
317 	unsigned long hash = init_name_hash(ns);
318 	unsigned int len = strlen(name);
319 	while (len--)
320 		hash = partial_name_hash(*name++, hash);
321 	hash = end_name_hash(hash);
322 	hash &= 0x7fffffffU;
323 	/* Reserve hash numbers 0, 1 and INT_MAX for magic directory entries */
324 	if (hash < 2)
325 		hash += 2;
326 	if (hash >= INT_MAX)
327 		hash = INT_MAX - 1;
328 	return hash;
329 }
330 
331 static int kernfs_name_compare(unsigned int hash, const char *name,
332 			       const void *ns, const struct kernfs_node *kn)
333 {
334 	if (hash < kn->hash)
335 		return -1;
336 	if (hash > kn->hash)
337 		return 1;
338 	if (ns < kn->ns)
339 		return -1;
340 	if (ns > kn->ns)
341 		return 1;
342 	return strcmp(name, kn->name);
343 }
344 
345 static int kernfs_sd_compare(const struct kernfs_node *left,
346 			     const struct kernfs_node *right)
347 {
348 	return kernfs_name_compare(left->hash, left->name, left->ns, right);
349 }
350 
351 /**
352  *	kernfs_link_sibling - link kernfs_node into sibling rbtree
353  *	@kn: kernfs_node of interest
354  *
355  *	Link @kn into its sibling rbtree which starts from
356  *	@kn->parent->dir.children.
357  *
358  *	Locking:
359  *	kernfs_rwsem held exclusive
360  *
361  *	Return:
362  *	%0 on success, -EEXIST on failure.
363  */
364 static int kernfs_link_sibling(struct kernfs_node *kn)
365 {
366 	struct rb_node **node = &kn->parent->dir.children.rb_node;
367 	struct rb_node *parent = NULL;
368 
369 	while (*node) {
370 		struct kernfs_node *pos;
371 		int result;
372 
373 		pos = rb_to_kn(*node);
374 		parent = *node;
375 		result = kernfs_sd_compare(kn, pos);
376 		if (result < 0)
377 			node = &pos->rb.rb_left;
378 		else if (result > 0)
379 			node = &pos->rb.rb_right;
380 		else
381 			return -EEXIST;
382 	}
383 
384 	/* add new node and rebalance the tree */
385 	rb_link_node(&kn->rb, parent, node);
386 	rb_insert_color(&kn->rb, &kn->parent->dir.children);
387 
388 	/* successfully added, account subdir number */
389 	if (kernfs_type(kn) == KERNFS_DIR)
390 		kn->parent->dir.subdirs++;
391 	kernfs_inc_rev(kn->parent);
392 
393 	return 0;
394 }
395 
396 /**
397  *	kernfs_unlink_sibling - unlink kernfs_node from sibling rbtree
398  *	@kn: kernfs_node of interest
399  *
400  *	Try to unlink @kn from its sibling rbtree which starts from
401  *	kn->parent->dir.children.
402  *
403  *	Return: %true if @kn was actually removed,
404  *	%false if @kn wasn't on the rbtree.
405  *
406  *	Locking:
407  *	kernfs_rwsem held exclusive
408  */
409 static bool kernfs_unlink_sibling(struct kernfs_node *kn)
410 {
411 	if (RB_EMPTY_NODE(&kn->rb))
412 		return false;
413 
414 	if (kernfs_type(kn) == KERNFS_DIR)
415 		kn->parent->dir.subdirs--;
416 	kernfs_inc_rev(kn->parent);
417 
418 	rb_erase(&kn->rb, &kn->parent->dir.children);
419 	RB_CLEAR_NODE(&kn->rb);
420 	return true;
421 }
422 
423 /**
424  *	kernfs_get_active - get an active reference to kernfs_node
425  *	@kn: kernfs_node to get an active reference to
426  *
427  *	Get an active reference of @kn.  This function is noop if @kn
428  *	is %NULL.
429  *
430  *	Return:
431  *	Pointer to @kn on success, %NULL on failure.
432  */
433 struct kernfs_node *kernfs_get_active(struct kernfs_node *kn)
434 {
435 	if (unlikely(!kn))
436 		return NULL;
437 
438 	if (!atomic_inc_unless_negative(&kn->active))
439 		return NULL;
440 
441 	if (kernfs_lockdep(kn))
442 		rwsem_acquire_read(&kn->dep_map, 0, 1, _RET_IP_);
443 	return kn;
444 }
445 
446 /**
447  *	kernfs_put_active - put an active reference to kernfs_node
448  *	@kn: kernfs_node to put an active reference to
449  *
450  *	Put an active reference to @kn.  This function is noop if @kn
451  *	is %NULL.
452  */
453 void kernfs_put_active(struct kernfs_node *kn)
454 {
455 	int v;
456 
457 	if (unlikely(!kn))
458 		return;
459 
460 	if (kernfs_lockdep(kn))
461 		rwsem_release(&kn->dep_map, _RET_IP_);
462 	v = atomic_dec_return(&kn->active);
463 	if (likely(v != KN_DEACTIVATED_BIAS))
464 		return;
465 
466 	wake_up_all(&kernfs_root(kn)->deactivate_waitq);
467 }
468 
469 /**
470  * kernfs_drain - drain kernfs_node
471  * @kn: kernfs_node to drain
472  *
473  * Drain existing usages and nuke all existing mmaps of @kn.  Multiple
474  * removers may invoke this function concurrently on @kn and all will
475  * return after draining is complete.
476  */
477 static void kernfs_drain(struct kernfs_node *kn)
478 	__releases(&kernfs_root(kn)->kernfs_rwsem)
479 	__acquires(&kernfs_root(kn)->kernfs_rwsem)
480 {
481 	struct kernfs_root *root = kernfs_root(kn);
482 
483 	lockdep_assert_held_write(&root->kernfs_rwsem);
484 	WARN_ON_ONCE(kernfs_active(kn));
485 
486 	/*
487 	 * Skip draining if already fully drained. This avoids draining and its
488 	 * lockdep annotations for nodes which have never been activated
489 	 * allowing embedding kernfs_remove() in create error paths without
490 	 * worrying about draining.
491 	 */
492 	if (atomic_read(&kn->active) == KN_DEACTIVATED_BIAS &&
493 	    !kernfs_should_drain_open_files(kn))
494 		return;
495 
496 	up_write(&root->kernfs_rwsem);
497 
498 	if (kernfs_lockdep(kn)) {
499 		rwsem_acquire(&kn->dep_map, 0, 0, _RET_IP_);
500 		if (atomic_read(&kn->active) != KN_DEACTIVATED_BIAS)
501 			lock_contended(&kn->dep_map, _RET_IP_);
502 	}
503 
504 	wait_event(root->deactivate_waitq,
505 		   atomic_read(&kn->active) == KN_DEACTIVATED_BIAS);
506 
507 	if (kernfs_lockdep(kn)) {
508 		lock_acquired(&kn->dep_map, _RET_IP_);
509 		rwsem_release(&kn->dep_map, _RET_IP_);
510 	}
511 
512 	if (kernfs_should_drain_open_files(kn))
513 		kernfs_drain_open_files(kn);
514 
515 	down_write(&root->kernfs_rwsem);
516 }
517 
518 /**
519  * kernfs_get - get a reference count on a kernfs_node
520  * @kn: the target kernfs_node
521  */
522 void kernfs_get(struct kernfs_node *kn)
523 {
524 	if (kn) {
525 		WARN_ON(!atomic_read(&kn->count));
526 		atomic_inc(&kn->count);
527 	}
528 }
529 EXPORT_SYMBOL_GPL(kernfs_get);
530 
531 /**
532  * kernfs_put - put a reference count on a kernfs_node
533  * @kn: the target kernfs_node
534  *
535  * Put a reference count of @kn and destroy it if it reached zero.
536  */
537 void kernfs_put(struct kernfs_node *kn)
538 {
539 	struct kernfs_node *parent;
540 	struct kernfs_root *root;
541 
542 	if (!kn || !atomic_dec_and_test(&kn->count))
543 		return;
544 	root = kernfs_root(kn);
545  repeat:
546 	/*
547 	 * Moving/renaming is always done while holding reference.
548 	 * kn->parent won't change beneath us.
549 	 */
550 	parent = kn->parent;
551 
552 	WARN_ONCE(atomic_read(&kn->active) != KN_DEACTIVATED_BIAS,
553 		  "kernfs_put: %s/%s: released with incorrect active_ref %d\n",
554 		  parent ? parent->name : "", kn->name, atomic_read(&kn->active));
555 
556 	if (kernfs_type(kn) == KERNFS_LINK)
557 		kernfs_put(kn->symlink.target_kn);
558 
559 	kfree_const(kn->name);
560 
561 	if (kn->iattr) {
562 		simple_xattrs_free(&kn->iattr->xattrs);
563 		kmem_cache_free(kernfs_iattrs_cache, kn->iattr);
564 	}
565 	spin_lock(&kernfs_idr_lock);
566 	idr_remove(&root->ino_idr, (u32)kernfs_ino(kn));
567 	spin_unlock(&kernfs_idr_lock);
568 	kmem_cache_free(kernfs_node_cache, kn);
569 
570 	kn = parent;
571 	if (kn) {
572 		if (atomic_dec_and_test(&kn->count))
573 			goto repeat;
574 	} else {
575 		/* just released the root kn, free @root too */
576 		idr_destroy(&root->ino_idr);
577 		kfree(root);
578 	}
579 }
580 EXPORT_SYMBOL_GPL(kernfs_put);
581 
582 /**
583  * kernfs_node_from_dentry - determine kernfs_node associated with a dentry
584  * @dentry: the dentry in question
585  *
586  * Return: the kernfs_node associated with @dentry.  If @dentry is not a
587  * kernfs one, %NULL is returned.
588  *
589  * While the returned kernfs_node will stay accessible as long as @dentry
590  * is accessible, the returned node can be in any state and the caller is
591  * fully responsible for determining what's accessible.
592  */
593 struct kernfs_node *kernfs_node_from_dentry(struct dentry *dentry)
594 {
595 	if (dentry->d_sb->s_op == &kernfs_sops)
596 		return kernfs_dentry_node(dentry);
597 	return NULL;
598 }
599 
600 static struct kernfs_node *__kernfs_new_node(struct kernfs_root *root,
601 					     struct kernfs_node *parent,
602 					     const char *name, umode_t mode,
603 					     kuid_t uid, kgid_t gid,
604 					     unsigned flags)
605 {
606 	struct kernfs_node *kn;
607 	u32 id_highbits;
608 	int ret;
609 
610 	name = kstrdup_const(name, GFP_KERNEL);
611 	if (!name)
612 		return NULL;
613 
614 	kn = kmem_cache_zalloc(kernfs_node_cache, GFP_KERNEL);
615 	if (!kn)
616 		goto err_out1;
617 
618 	idr_preload(GFP_KERNEL);
619 	spin_lock(&kernfs_idr_lock);
620 	ret = idr_alloc_cyclic(&root->ino_idr, kn, 1, 0, GFP_ATOMIC);
621 	if (ret >= 0 && ret < root->last_id_lowbits)
622 		root->id_highbits++;
623 	id_highbits = root->id_highbits;
624 	root->last_id_lowbits = ret;
625 	spin_unlock(&kernfs_idr_lock);
626 	idr_preload_end();
627 	if (ret < 0)
628 		goto err_out2;
629 
630 	kn->id = (u64)id_highbits << 32 | ret;
631 
632 	atomic_set(&kn->count, 1);
633 	atomic_set(&kn->active, KN_DEACTIVATED_BIAS);
634 	RB_CLEAR_NODE(&kn->rb);
635 
636 	kn->name = name;
637 	kn->mode = mode;
638 	kn->flags = flags;
639 
640 	if (!uid_eq(uid, GLOBAL_ROOT_UID) || !gid_eq(gid, GLOBAL_ROOT_GID)) {
641 		struct iattr iattr = {
642 			.ia_valid = ATTR_UID | ATTR_GID,
643 			.ia_uid = uid,
644 			.ia_gid = gid,
645 		};
646 
647 		ret = __kernfs_setattr(kn, &iattr);
648 		if (ret < 0)
649 			goto err_out3;
650 	}
651 
652 	if (parent) {
653 		ret = security_kernfs_init_security(parent, kn);
654 		if (ret)
655 			goto err_out3;
656 	}
657 
658 	return kn;
659 
660  err_out3:
661 	idr_remove(&root->ino_idr, (u32)kernfs_ino(kn));
662  err_out2:
663 	kmem_cache_free(kernfs_node_cache, kn);
664  err_out1:
665 	kfree_const(name);
666 	return NULL;
667 }
668 
669 struct kernfs_node *kernfs_new_node(struct kernfs_node *parent,
670 				    const char *name, umode_t mode,
671 				    kuid_t uid, kgid_t gid,
672 				    unsigned flags)
673 {
674 	struct kernfs_node *kn;
675 
676 	kn = __kernfs_new_node(kernfs_root(parent), parent,
677 			       name, mode, uid, gid, flags);
678 	if (kn) {
679 		kernfs_get(parent);
680 		kn->parent = parent;
681 	}
682 	return kn;
683 }
684 
685 /*
686  * kernfs_find_and_get_node_by_id - get kernfs_node from node id
687  * @root: the kernfs root
688  * @id: the target node id
689  *
690  * @id's lower 32bits encode ino and upper gen.  If the gen portion is
691  * zero, all generations are matched.
692  *
693  * Return: %NULL on failure,
694  * otherwise a kernfs node with reference counter incremented.
695  */
696 struct kernfs_node *kernfs_find_and_get_node_by_id(struct kernfs_root *root,
697 						   u64 id)
698 {
699 	struct kernfs_node *kn;
700 	ino_t ino = kernfs_id_ino(id);
701 	u32 gen = kernfs_id_gen(id);
702 
703 	spin_lock(&kernfs_idr_lock);
704 
705 	kn = idr_find(&root->ino_idr, (u32)ino);
706 	if (!kn)
707 		goto err_unlock;
708 
709 	if (sizeof(ino_t) >= sizeof(u64)) {
710 		/* we looked up with the low 32bits, compare the whole */
711 		if (kernfs_ino(kn) != ino)
712 			goto err_unlock;
713 	} else {
714 		/* 0 matches all generations */
715 		if (unlikely(gen && kernfs_gen(kn) != gen))
716 			goto err_unlock;
717 	}
718 
719 	/*
720 	 * We should fail if @kn has never been activated and guarantee success
721 	 * if the caller knows that @kn is active. Both can be achieved by
722 	 * __kernfs_active() which tests @kn->active without kernfs_rwsem.
723 	 */
724 	if (unlikely(!__kernfs_active(kn) || !atomic_inc_not_zero(&kn->count)))
725 		goto err_unlock;
726 
727 	spin_unlock(&kernfs_idr_lock);
728 	return kn;
729 err_unlock:
730 	spin_unlock(&kernfs_idr_lock);
731 	return NULL;
732 }
733 
734 /**
735  *	kernfs_add_one - add kernfs_node to parent without warning
736  *	@kn: kernfs_node to be added
737  *
738  *	The caller must already have initialized @kn->parent.  This
739  *	function increments nlink of the parent's inode if @kn is a
740  *	directory and link into the children list of the parent.
741  *
742  *	Return:
743  *	%0 on success, -EEXIST if entry with the given name already
744  *	exists.
745  */
746 int kernfs_add_one(struct kernfs_node *kn)
747 {
748 	struct kernfs_node *parent = kn->parent;
749 	struct kernfs_root *root = kernfs_root(parent);
750 	struct kernfs_iattrs *ps_iattr;
751 	bool has_ns;
752 	int ret;
753 
754 	down_write(&root->kernfs_rwsem);
755 
756 	ret = -EINVAL;
757 	has_ns = kernfs_ns_enabled(parent);
758 	if (WARN(has_ns != (bool)kn->ns, KERN_WARNING "kernfs: ns %s in '%s' for '%s'\n",
759 		 has_ns ? "required" : "invalid", parent->name, kn->name))
760 		goto out_unlock;
761 
762 	if (kernfs_type(parent) != KERNFS_DIR)
763 		goto out_unlock;
764 
765 	ret = -ENOENT;
766 	if (parent->flags & (KERNFS_REMOVING | KERNFS_EMPTY_DIR))
767 		goto out_unlock;
768 
769 	kn->hash = kernfs_name_hash(kn->name, kn->ns);
770 
771 	ret = kernfs_link_sibling(kn);
772 	if (ret)
773 		goto out_unlock;
774 
775 	/* Update timestamps on the parent */
776 	ps_iattr = parent->iattr;
777 	if (ps_iattr) {
778 		ktime_get_real_ts64(&ps_iattr->ia_ctime);
779 		ps_iattr->ia_mtime = ps_iattr->ia_ctime;
780 	}
781 
782 	up_write(&root->kernfs_rwsem);
783 
784 	/*
785 	 * Activate the new node unless CREATE_DEACTIVATED is requested.
786 	 * If not activated here, the kernfs user is responsible for
787 	 * activating the node with kernfs_activate().  A node which hasn't
788 	 * been activated is not visible to userland and its removal won't
789 	 * trigger deactivation.
790 	 */
791 	if (!(kernfs_root(kn)->flags & KERNFS_ROOT_CREATE_DEACTIVATED))
792 		kernfs_activate(kn);
793 	return 0;
794 
795 out_unlock:
796 	up_write(&root->kernfs_rwsem);
797 	return ret;
798 }
799 
800 /**
801  * kernfs_find_ns - find kernfs_node with the given name
802  * @parent: kernfs_node to search under
803  * @name: name to look for
804  * @ns: the namespace tag to use
805  *
806  * Look for kernfs_node with name @name under @parent.
807  *
808  * Return: pointer to the found kernfs_node on success, %NULL on failure.
809  */
810 static struct kernfs_node *kernfs_find_ns(struct kernfs_node *parent,
811 					  const unsigned char *name,
812 					  const void *ns)
813 {
814 	struct rb_node *node = parent->dir.children.rb_node;
815 	bool has_ns = kernfs_ns_enabled(parent);
816 	unsigned int hash;
817 
818 	lockdep_assert_held(&kernfs_root(parent)->kernfs_rwsem);
819 
820 	if (has_ns != (bool)ns) {
821 		WARN(1, KERN_WARNING "kernfs: ns %s in '%s' for '%s'\n",
822 		     has_ns ? "required" : "invalid", parent->name, name);
823 		return NULL;
824 	}
825 
826 	hash = kernfs_name_hash(name, ns);
827 	while (node) {
828 		struct kernfs_node *kn;
829 		int result;
830 
831 		kn = rb_to_kn(node);
832 		result = kernfs_name_compare(hash, name, ns, kn);
833 		if (result < 0)
834 			node = node->rb_left;
835 		else if (result > 0)
836 			node = node->rb_right;
837 		else
838 			return kn;
839 	}
840 	return NULL;
841 }
842 
843 static struct kernfs_node *kernfs_walk_ns(struct kernfs_node *parent,
844 					  const unsigned char *path,
845 					  const void *ns)
846 {
847 	size_t len;
848 	char *p, *name;
849 
850 	lockdep_assert_held_read(&kernfs_root(parent)->kernfs_rwsem);
851 
852 	spin_lock_irq(&kernfs_pr_cont_lock);
853 
854 	len = strlcpy(kernfs_pr_cont_buf, path, sizeof(kernfs_pr_cont_buf));
855 
856 	if (len >= sizeof(kernfs_pr_cont_buf)) {
857 		spin_unlock_irq(&kernfs_pr_cont_lock);
858 		return NULL;
859 	}
860 
861 	p = kernfs_pr_cont_buf;
862 
863 	while ((name = strsep(&p, "/")) && parent) {
864 		if (*name == '\0')
865 			continue;
866 		parent = kernfs_find_ns(parent, name, ns);
867 	}
868 
869 	spin_unlock_irq(&kernfs_pr_cont_lock);
870 
871 	return parent;
872 }
873 
874 /**
875  * kernfs_find_and_get_ns - find and get kernfs_node with the given name
876  * @parent: kernfs_node to search under
877  * @name: name to look for
878  * @ns: the namespace tag to use
879  *
880  * Look for kernfs_node with name @name under @parent and get a reference
881  * if found.  This function may sleep.
882  *
883  * Return: pointer to the found kernfs_node on success, %NULL on failure.
884  */
885 struct kernfs_node *kernfs_find_and_get_ns(struct kernfs_node *parent,
886 					   const char *name, const void *ns)
887 {
888 	struct kernfs_node *kn;
889 	struct kernfs_root *root = kernfs_root(parent);
890 
891 	down_read(&root->kernfs_rwsem);
892 	kn = kernfs_find_ns(parent, name, ns);
893 	kernfs_get(kn);
894 	up_read(&root->kernfs_rwsem);
895 
896 	return kn;
897 }
898 EXPORT_SYMBOL_GPL(kernfs_find_and_get_ns);
899 
900 /**
901  * kernfs_walk_and_get_ns - find and get kernfs_node with the given path
902  * @parent: kernfs_node to search under
903  * @path: path to look for
904  * @ns: the namespace tag to use
905  *
906  * Look for kernfs_node with path @path under @parent and get a reference
907  * if found.  This function may sleep.
908  *
909  * Return: pointer to the found kernfs_node on success, %NULL on failure.
910  */
911 struct kernfs_node *kernfs_walk_and_get_ns(struct kernfs_node *parent,
912 					   const char *path, const void *ns)
913 {
914 	struct kernfs_node *kn;
915 	struct kernfs_root *root = kernfs_root(parent);
916 
917 	down_read(&root->kernfs_rwsem);
918 	kn = kernfs_walk_ns(parent, path, ns);
919 	kernfs_get(kn);
920 	up_read(&root->kernfs_rwsem);
921 
922 	return kn;
923 }
924 
925 /**
926  * kernfs_create_root - create a new kernfs hierarchy
927  * @scops: optional syscall operations for the hierarchy
928  * @flags: KERNFS_ROOT_* flags
929  * @priv: opaque data associated with the new directory
930  *
931  * Return: the root of the new hierarchy on success, ERR_PTR() value on
932  * failure.
933  */
934 struct kernfs_root *kernfs_create_root(struct kernfs_syscall_ops *scops,
935 				       unsigned int flags, void *priv)
936 {
937 	struct kernfs_root *root;
938 	struct kernfs_node *kn;
939 
940 	root = kzalloc(sizeof(*root), GFP_KERNEL);
941 	if (!root)
942 		return ERR_PTR(-ENOMEM);
943 
944 	idr_init(&root->ino_idr);
945 	init_rwsem(&root->kernfs_rwsem);
946 	INIT_LIST_HEAD(&root->supers);
947 
948 	/*
949 	 * On 64bit ino setups, id is ino.  On 32bit, low 32bits are ino.
950 	 * High bits generation.  The starting value for both ino and
951 	 * genenration is 1.  Initialize upper 32bit allocation
952 	 * accordingly.
953 	 */
954 	if (sizeof(ino_t) >= sizeof(u64))
955 		root->id_highbits = 0;
956 	else
957 		root->id_highbits = 1;
958 
959 	kn = __kernfs_new_node(root, NULL, "", S_IFDIR | S_IRUGO | S_IXUGO,
960 			       GLOBAL_ROOT_UID, GLOBAL_ROOT_GID,
961 			       KERNFS_DIR);
962 	if (!kn) {
963 		idr_destroy(&root->ino_idr);
964 		kfree(root);
965 		return ERR_PTR(-ENOMEM);
966 	}
967 
968 	kn->priv = priv;
969 	kn->dir.root = root;
970 
971 	root->syscall_ops = scops;
972 	root->flags = flags;
973 	root->kn = kn;
974 	init_waitqueue_head(&root->deactivate_waitq);
975 
976 	if (!(root->flags & KERNFS_ROOT_CREATE_DEACTIVATED))
977 		kernfs_activate(kn);
978 
979 	return root;
980 }
981 
982 /**
983  * kernfs_destroy_root - destroy a kernfs hierarchy
984  * @root: root of the hierarchy to destroy
985  *
986  * Destroy the hierarchy anchored at @root by removing all existing
987  * directories and destroying @root.
988  */
989 void kernfs_destroy_root(struct kernfs_root *root)
990 {
991 	/*
992 	 *  kernfs_remove holds kernfs_rwsem from the root so the root
993 	 *  shouldn't be freed during the operation.
994 	 */
995 	kernfs_get(root->kn);
996 	kernfs_remove(root->kn);
997 	kernfs_put(root->kn); /* will also free @root */
998 }
999 
1000 /**
1001  * kernfs_root_to_node - return the kernfs_node associated with a kernfs_root
1002  * @root: root to use to lookup
1003  *
1004  * Return: @root's kernfs_node
1005  */
1006 struct kernfs_node *kernfs_root_to_node(struct kernfs_root *root)
1007 {
1008 	return root->kn;
1009 }
1010 
1011 /**
1012  * kernfs_create_dir_ns - create a directory
1013  * @parent: parent in which to create a new directory
1014  * @name: name of the new directory
1015  * @mode: mode of the new directory
1016  * @uid: uid of the new directory
1017  * @gid: gid of the new directory
1018  * @priv: opaque data associated with the new directory
1019  * @ns: optional namespace tag of the directory
1020  *
1021  * Return: the created node on success, ERR_PTR() value on failure.
1022  */
1023 struct kernfs_node *kernfs_create_dir_ns(struct kernfs_node *parent,
1024 					 const char *name, umode_t mode,
1025 					 kuid_t uid, kgid_t gid,
1026 					 void *priv, const void *ns)
1027 {
1028 	struct kernfs_node *kn;
1029 	int rc;
1030 
1031 	/* allocate */
1032 	kn = kernfs_new_node(parent, name, mode | S_IFDIR,
1033 			     uid, gid, KERNFS_DIR);
1034 	if (!kn)
1035 		return ERR_PTR(-ENOMEM);
1036 
1037 	kn->dir.root = parent->dir.root;
1038 	kn->ns = ns;
1039 	kn->priv = priv;
1040 
1041 	/* link in */
1042 	rc = kernfs_add_one(kn);
1043 	if (!rc)
1044 		return kn;
1045 
1046 	kernfs_put(kn);
1047 	return ERR_PTR(rc);
1048 }
1049 
1050 /**
1051  * kernfs_create_empty_dir - create an always empty directory
1052  * @parent: parent in which to create a new directory
1053  * @name: name of the new directory
1054  *
1055  * Return: the created node on success, ERR_PTR() value on failure.
1056  */
1057 struct kernfs_node *kernfs_create_empty_dir(struct kernfs_node *parent,
1058 					    const char *name)
1059 {
1060 	struct kernfs_node *kn;
1061 	int rc;
1062 
1063 	/* allocate */
1064 	kn = kernfs_new_node(parent, name, S_IRUGO|S_IXUGO|S_IFDIR,
1065 			     GLOBAL_ROOT_UID, GLOBAL_ROOT_GID, KERNFS_DIR);
1066 	if (!kn)
1067 		return ERR_PTR(-ENOMEM);
1068 
1069 	kn->flags |= KERNFS_EMPTY_DIR;
1070 	kn->dir.root = parent->dir.root;
1071 	kn->ns = NULL;
1072 	kn->priv = NULL;
1073 
1074 	/* link in */
1075 	rc = kernfs_add_one(kn);
1076 	if (!rc)
1077 		return kn;
1078 
1079 	kernfs_put(kn);
1080 	return ERR_PTR(rc);
1081 }
1082 
1083 static int kernfs_dop_revalidate(struct dentry *dentry, unsigned int flags)
1084 {
1085 	struct kernfs_node *kn;
1086 	struct kernfs_root *root;
1087 
1088 	if (flags & LOOKUP_RCU)
1089 		return -ECHILD;
1090 
1091 	/* Negative hashed dentry? */
1092 	if (d_really_is_negative(dentry)) {
1093 		struct kernfs_node *parent;
1094 
1095 		/* If the kernfs parent node has changed discard and
1096 		 * proceed to ->lookup.
1097 		 *
1098 		 * There's nothing special needed here when getting the
1099 		 * dentry parent, even if a concurrent rename is in
1100 		 * progress. That's because the dentry is negative so
1101 		 * it can only be the target of the rename and it will
1102 		 * be doing a d_move() not a replace. Consequently the
1103 		 * dentry d_parent won't change over the d_move().
1104 		 *
1105 		 * Also kernfs negative dentries transitioning from
1106 		 * negative to positive during revalidate won't happen
1107 		 * because they are invalidated on containing directory
1108 		 * changes and the lookup re-done so that a new positive
1109 		 * dentry can be properly created.
1110 		 */
1111 		root = kernfs_root_from_sb(dentry->d_sb);
1112 		down_read(&root->kernfs_rwsem);
1113 		parent = kernfs_dentry_node(dentry->d_parent);
1114 		if (parent) {
1115 			if (kernfs_dir_changed(parent, dentry)) {
1116 				up_read(&root->kernfs_rwsem);
1117 				return 0;
1118 			}
1119 		}
1120 		up_read(&root->kernfs_rwsem);
1121 
1122 		/* The kernfs parent node hasn't changed, leave the
1123 		 * dentry negative and return success.
1124 		 */
1125 		return 1;
1126 	}
1127 
1128 	kn = kernfs_dentry_node(dentry);
1129 	root = kernfs_root(kn);
1130 	down_read(&root->kernfs_rwsem);
1131 
1132 	/* The kernfs node has been deactivated */
1133 	if (!kernfs_active(kn))
1134 		goto out_bad;
1135 
1136 	/* The kernfs node has been moved? */
1137 	if (kernfs_dentry_node(dentry->d_parent) != kn->parent)
1138 		goto out_bad;
1139 
1140 	/* The kernfs node has been renamed */
1141 	if (strcmp(dentry->d_name.name, kn->name) != 0)
1142 		goto out_bad;
1143 
1144 	/* The kernfs node has been moved to a different namespace */
1145 	if (kn->parent && kernfs_ns_enabled(kn->parent) &&
1146 	    kernfs_info(dentry->d_sb)->ns != kn->ns)
1147 		goto out_bad;
1148 
1149 	up_read(&root->kernfs_rwsem);
1150 	return 1;
1151 out_bad:
1152 	up_read(&root->kernfs_rwsem);
1153 	return 0;
1154 }
1155 
1156 const struct dentry_operations kernfs_dops = {
1157 	.d_revalidate	= kernfs_dop_revalidate,
1158 };
1159 
1160 static struct dentry *kernfs_iop_lookup(struct inode *dir,
1161 					struct dentry *dentry,
1162 					unsigned int flags)
1163 {
1164 	struct kernfs_node *parent = dir->i_private;
1165 	struct kernfs_node *kn;
1166 	struct kernfs_root *root;
1167 	struct inode *inode = NULL;
1168 	const void *ns = NULL;
1169 
1170 	root = kernfs_root(parent);
1171 	down_read(&root->kernfs_rwsem);
1172 	if (kernfs_ns_enabled(parent))
1173 		ns = kernfs_info(dir->i_sb)->ns;
1174 
1175 	kn = kernfs_find_ns(parent, dentry->d_name.name, ns);
1176 	/* attach dentry and inode */
1177 	if (kn) {
1178 		/* Inactive nodes are invisible to the VFS so don't
1179 		 * create a negative.
1180 		 */
1181 		if (!kernfs_active(kn)) {
1182 			up_read(&root->kernfs_rwsem);
1183 			return NULL;
1184 		}
1185 		inode = kernfs_get_inode(dir->i_sb, kn);
1186 		if (!inode)
1187 			inode = ERR_PTR(-ENOMEM);
1188 	}
1189 	/*
1190 	 * Needed for negative dentry validation.
1191 	 * The negative dentry can be created in kernfs_iop_lookup()
1192 	 * or transforms from positive dentry in dentry_unlink_inode()
1193 	 * called from vfs_rmdir().
1194 	 */
1195 	if (!IS_ERR(inode))
1196 		kernfs_set_rev(parent, dentry);
1197 	up_read(&root->kernfs_rwsem);
1198 
1199 	/* instantiate and hash (possibly negative) dentry */
1200 	return d_splice_alias(inode, dentry);
1201 }
1202 
1203 static int kernfs_iop_mkdir(struct user_namespace *mnt_userns,
1204 			    struct inode *dir, struct dentry *dentry,
1205 			    umode_t mode)
1206 {
1207 	struct kernfs_node *parent = dir->i_private;
1208 	struct kernfs_syscall_ops *scops = kernfs_root(parent)->syscall_ops;
1209 	int ret;
1210 
1211 	if (!scops || !scops->mkdir)
1212 		return -EPERM;
1213 
1214 	if (!kernfs_get_active(parent))
1215 		return -ENODEV;
1216 
1217 	ret = scops->mkdir(parent, dentry->d_name.name, mode);
1218 
1219 	kernfs_put_active(parent);
1220 	return ret;
1221 }
1222 
1223 static int kernfs_iop_rmdir(struct inode *dir, struct dentry *dentry)
1224 {
1225 	struct kernfs_node *kn  = kernfs_dentry_node(dentry);
1226 	struct kernfs_syscall_ops *scops = kernfs_root(kn)->syscall_ops;
1227 	int ret;
1228 
1229 	if (!scops || !scops->rmdir)
1230 		return -EPERM;
1231 
1232 	if (!kernfs_get_active(kn))
1233 		return -ENODEV;
1234 
1235 	ret = scops->rmdir(kn);
1236 
1237 	kernfs_put_active(kn);
1238 	return ret;
1239 }
1240 
1241 static int kernfs_iop_rename(struct user_namespace *mnt_userns,
1242 			     struct inode *old_dir, struct dentry *old_dentry,
1243 			     struct inode *new_dir, struct dentry *new_dentry,
1244 			     unsigned int flags)
1245 {
1246 	struct kernfs_node *kn = kernfs_dentry_node(old_dentry);
1247 	struct kernfs_node *new_parent = new_dir->i_private;
1248 	struct kernfs_syscall_ops *scops = kernfs_root(kn)->syscall_ops;
1249 	int ret;
1250 
1251 	if (flags)
1252 		return -EINVAL;
1253 
1254 	if (!scops || !scops->rename)
1255 		return -EPERM;
1256 
1257 	if (!kernfs_get_active(kn))
1258 		return -ENODEV;
1259 
1260 	if (!kernfs_get_active(new_parent)) {
1261 		kernfs_put_active(kn);
1262 		return -ENODEV;
1263 	}
1264 
1265 	ret = scops->rename(kn, new_parent, new_dentry->d_name.name);
1266 
1267 	kernfs_put_active(new_parent);
1268 	kernfs_put_active(kn);
1269 	return ret;
1270 }
1271 
1272 const struct inode_operations kernfs_dir_iops = {
1273 	.lookup		= kernfs_iop_lookup,
1274 	.permission	= kernfs_iop_permission,
1275 	.setattr	= kernfs_iop_setattr,
1276 	.getattr	= kernfs_iop_getattr,
1277 	.listxattr	= kernfs_iop_listxattr,
1278 
1279 	.mkdir		= kernfs_iop_mkdir,
1280 	.rmdir		= kernfs_iop_rmdir,
1281 	.rename		= kernfs_iop_rename,
1282 };
1283 
1284 static struct kernfs_node *kernfs_leftmost_descendant(struct kernfs_node *pos)
1285 {
1286 	struct kernfs_node *last;
1287 
1288 	while (true) {
1289 		struct rb_node *rbn;
1290 
1291 		last = pos;
1292 
1293 		if (kernfs_type(pos) != KERNFS_DIR)
1294 			break;
1295 
1296 		rbn = rb_first(&pos->dir.children);
1297 		if (!rbn)
1298 			break;
1299 
1300 		pos = rb_to_kn(rbn);
1301 	}
1302 
1303 	return last;
1304 }
1305 
1306 /**
1307  * kernfs_next_descendant_post - find the next descendant for post-order walk
1308  * @pos: the current position (%NULL to initiate traversal)
1309  * @root: kernfs_node whose descendants to walk
1310  *
1311  * Find the next descendant to visit for post-order traversal of @root's
1312  * descendants.  @root is included in the iteration and the last node to be
1313  * visited.
1314  *
1315  * Return: the next descendant to visit or %NULL when done.
1316  */
1317 static struct kernfs_node *kernfs_next_descendant_post(struct kernfs_node *pos,
1318 						       struct kernfs_node *root)
1319 {
1320 	struct rb_node *rbn;
1321 
1322 	lockdep_assert_held_write(&kernfs_root(root)->kernfs_rwsem);
1323 
1324 	/* if first iteration, visit leftmost descendant which may be root */
1325 	if (!pos)
1326 		return kernfs_leftmost_descendant(root);
1327 
1328 	/* if we visited @root, we're done */
1329 	if (pos == root)
1330 		return NULL;
1331 
1332 	/* if there's an unvisited sibling, visit its leftmost descendant */
1333 	rbn = rb_next(&pos->rb);
1334 	if (rbn)
1335 		return kernfs_leftmost_descendant(rb_to_kn(rbn));
1336 
1337 	/* no sibling left, visit parent */
1338 	return pos->parent;
1339 }
1340 
1341 static void kernfs_activate_one(struct kernfs_node *kn)
1342 {
1343 	lockdep_assert_held_write(&kernfs_root(kn)->kernfs_rwsem);
1344 
1345 	kn->flags |= KERNFS_ACTIVATED;
1346 
1347 	if (kernfs_active(kn) || (kn->flags & (KERNFS_HIDDEN | KERNFS_REMOVING)))
1348 		return;
1349 
1350 	WARN_ON_ONCE(kn->parent && RB_EMPTY_NODE(&kn->rb));
1351 	WARN_ON_ONCE(atomic_read(&kn->active) != KN_DEACTIVATED_BIAS);
1352 
1353 	atomic_sub(KN_DEACTIVATED_BIAS, &kn->active);
1354 }
1355 
1356 /**
1357  * kernfs_activate - activate a node which started deactivated
1358  * @kn: kernfs_node whose subtree is to be activated
1359  *
1360  * If the root has KERNFS_ROOT_CREATE_DEACTIVATED set, a newly created node
1361  * needs to be explicitly activated.  A node which hasn't been activated
1362  * isn't visible to userland and deactivation is skipped during its
1363  * removal.  This is useful to construct atomic init sequences where
1364  * creation of multiple nodes should either succeed or fail atomically.
1365  *
1366  * The caller is responsible for ensuring that this function is not called
1367  * after kernfs_remove*() is invoked on @kn.
1368  */
1369 void kernfs_activate(struct kernfs_node *kn)
1370 {
1371 	struct kernfs_node *pos;
1372 	struct kernfs_root *root = kernfs_root(kn);
1373 
1374 	down_write(&root->kernfs_rwsem);
1375 
1376 	pos = NULL;
1377 	while ((pos = kernfs_next_descendant_post(pos, kn)))
1378 		kernfs_activate_one(pos);
1379 
1380 	up_write(&root->kernfs_rwsem);
1381 }
1382 
1383 /**
1384  * kernfs_show - show or hide a node
1385  * @kn: kernfs_node to show or hide
1386  * @show: whether to show or hide
1387  *
1388  * If @show is %false, @kn is marked hidden and deactivated. A hidden node is
1389  * ignored in future activaitons. If %true, the mark is removed and activation
1390  * state is restored. This function won't implicitly activate a new node in a
1391  * %KERNFS_ROOT_CREATE_DEACTIVATED root which hasn't been activated yet.
1392  *
1393  * To avoid recursion complexities, directories aren't supported for now.
1394  */
1395 void kernfs_show(struct kernfs_node *kn, bool show)
1396 {
1397 	struct kernfs_root *root = kernfs_root(kn);
1398 
1399 	if (WARN_ON_ONCE(kernfs_type(kn) == KERNFS_DIR))
1400 		return;
1401 
1402 	down_write(&root->kernfs_rwsem);
1403 
1404 	if (show) {
1405 		kn->flags &= ~KERNFS_HIDDEN;
1406 		if (kn->flags & KERNFS_ACTIVATED)
1407 			kernfs_activate_one(kn);
1408 	} else {
1409 		kn->flags |= KERNFS_HIDDEN;
1410 		if (kernfs_active(kn))
1411 			atomic_add(KN_DEACTIVATED_BIAS, &kn->active);
1412 		kernfs_drain(kn);
1413 	}
1414 
1415 	up_write(&root->kernfs_rwsem);
1416 }
1417 
1418 static void __kernfs_remove(struct kernfs_node *kn)
1419 {
1420 	struct kernfs_node *pos;
1421 
1422 	/* Short-circuit if non-root @kn has already finished removal. */
1423 	if (!kn)
1424 		return;
1425 
1426 	lockdep_assert_held_write(&kernfs_root(kn)->kernfs_rwsem);
1427 
1428 	/*
1429 	 * This is for kernfs_remove_self() which plays with active ref
1430 	 * after removal.
1431 	 */
1432 	if (kn->parent && RB_EMPTY_NODE(&kn->rb))
1433 		return;
1434 
1435 	pr_debug("kernfs %s: removing\n", kn->name);
1436 
1437 	/* prevent new usage by marking all nodes removing and deactivating */
1438 	pos = NULL;
1439 	while ((pos = kernfs_next_descendant_post(pos, kn))) {
1440 		pos->flags |= KERNFS_REMOVING;
1441 		if (kernfs_active(pos))
1442 			atomic_add(KN_DEACTIVATED_BIAS, &pos->active);
1443 	}
1444 
1445 	/* deactivate and unlink the subtree node-by-node */
1446 	do {
1447 		pos = kernfs_leftmost_descendant(kn);
1448 
1449 		/*
1450 		 * kernfs_drain() may drop kernfs_rwsem temporarily and @pos's
1451 		 * base ref could have been put by someone else by the time
1452 		 * the function returns.  Make sure it doesn't go away
1453 		 * underneath us.
1454 		 */
1455 		kernfs_get(pos);
1456 
1457 		kernfs_drain(pos);
1458 
1459 		/*
1460 		 * kernfs_unlink_sibling() succeeds once per node.  Use it
1461 		 * to decide who's responsible for cleanups.
1462 		 */
1463 		if (!pos->parent || kernfs_unlink_sibling(pos)) {
1464 			struct kernfs_iattrs *ps_iattr =
1465 				pos->parent ? pos->parent->iattr : NULL;
1466 
1467 			/* update timestamps on the parent */
1468 			if (ps_iattr) {
1469 				ktime_get_real_ts64(&ps_iattr->ia_ctime);
1470 				ps_iattr->ia_mtime = ps_iattr->ia_ctime;
1471 			}
1472 
1473 			kernfs_put(pos);
1474 		}
1475 
1476 		kernfs_put(pos);
1477 	} while (pos != kn);
1478 }
1479 
1480 /**
1481  * kernfs_remove - remove a kernfs_node recursively
1482  * @kn: the kernfs_node to remove
1483  *
1484  * Remove @kn along with all its subdirectories and files.
1485  */
1486 void kernfs_remove(struct kernfs_node *kn)
1487 {
1488 	struct kernfs_root *root;
1489 
1490 	if (!kn)
1491 		return;
1492 
1493 	root = kernfs_root(kn);
1494 
1495 	down_write(&root->kernfs_rwsem);
1496 	__kernfs_remove(kn);
1497 	up_write(&root->kernfs_rwsem);
1498 }
1499 
1500 /**
1501  * kernfs_break_active_protection - break out of active protection
1502  * @kn: the self kernfs_node
1503  *
1504  * The caller must be running off of a kernfs operation which is invoked
1505  * with an active reference - e.g. one of kernfs_ops.  Each invocation of
1506  * this function must also be matched with an invocation of
1507  * kernfs_unbreak_active_protection().
1508  *
1509  * This function releases the active reference of @kn the caller is
1510  * holding.  Once this function is called, @kn may be removed at any point
1511  * and the caller is solely responsible for ensuring that the objects it
1512  * dereferences are accessible.
1513  */
1514 void kernfs_break_active_protection(struct kernfs_node *kn)
1515 {
1516 	/*
1517 	 * Take out ourself out of the active ref dependency chain.  If
1518 	 * we're called without an active ref, lockdep will complain.
1519 	 */
1520 	kernfs_put_active(kn);
1521 }
1522 
1523 /**
1524  * kernfs_unbreak_active_protection - undo kernfs_break_active_protection()
1525  * @kn: the self kernfs_node
1526  *
1527  * If kernfs_break_active_protection() was called, this function must be
1528  * invoked before finishing the kernfs operation.  Note that while this
1529  * function restores the active reference, it doesn't and can't actually
1530  * restore the active protection - @kn may already or be in the process of
1531  * being removed.  Once kernfs_break_active_protection() is invoked, that
1532  * protection is irreversibly gone for the kernfs operation instance.
1533  *
1534  * While this function may be called at any point after
1535  * kernfs_break_active_protection() is invoked, its most useful location
1536  * would be right before the enclosing kernfs operation returns.
1537  */
1538 void kernfs_unbreak_active_protection(struct kernfs_node *kn)
1539 {
1540 	/*
1541 	 * @kn->active could be in any state; however, the increment we do
1542 	 * here will be undone as soon as the enclosing kernfs operation
1543 	 * finishes and this temporary bump can't break anything.  If @kn
1544 	 * is alive, nothing changes.  If @kn is being deactivated, the
1545 	 * soon-to-follow put will either finish deactivation or restore
1546 	 * deactivated state.  If @kn is already removed, the temporary
1547 	 * bump is guaranteed to be gone before @kn is released.
1548 	 */
1549 	atomic_inc(&kn->active);
1550 	if (kernfs_lockdep(kn))
1551 		rwsem_acquire(&kn->dep_map, 0, 1, _RET_IP_);
1552 }
1553 
1554 /**
1555  * kernfs_remove_self - remove a kernfs_node from its own method
1556  * @kn: the self kernfs_node to remove
1557  *
1558  * The caller must be running off of a kernfs operation which is invoked
1559  * with an active reference - e.g. one of kernfs_ops.  This can be used to
1560  * implement a file operation which deletes itself.
1561  *
1562  * For example, the "delete" file for a sysfs device directory can be
1563  * implemented by invoking kernfs_remove_self() on the "delete" file
1564  * itself.  This function breaks the circular dependency of trying to
1565  * deactivate self while holding an active ref itself.  It isn't necessary
1566  * to modify the usual removal path to use kernfs_remove_self().  The
1567  * "delete" implementation can simply invoke kernfs_remove_self() on self
1568  * before proceeding with the usual removal path.  kernfs will ignore later
1569  * kernfs_remove() on self.
1570  *
1571  * kernfs_remove_self() can be called multiple times concurrently on the
1572  * same kernfs_node.  Only the first one actually performs removal and
1573  * returns %true.  All others will wait until the kernfs operation which
1574  * won self-removal finishes and return %false.  Note that the losers wait
1575  * for the completion of not only the winning kernfs_remove_self() but also
1576  * the whole kernfs_ops which won the arbitration.  This can be used to
1577  * guarantee, for example, all concurrent writes to a "delete" file to
1578  * finish only after the whole operation is complete.
1579  *
1580  * Return: %true if @kn is removed by this call, otherwise %false.
1581  */
1582 bool kernfs_remove_self(struct kernfs_node *kn)
1583 {
1584 	bool ret;
1585 	struct kernfs_root *root = kernfs_root(kn);
1586 
1587 	down_write(&root->kernfs_rwsem);
1588 	kernfs_break_active_protection(kn);
1589 
1590 	/*
1591 	 * SUICIDAL is used to arbitrate among competing invocations.  Only
1592 	 * the first one will actually perform removal.  When the removal
1593 	 * is complete, SUICIDED is set and the active ref is restored
1594 	 * while kernfs_rwsem for held exclusive.  The ones which lost
1595 	 * arbitration waits for SUICIDED && drained which can happen only
1596 	 * after the enclosing kernfs operation which executed the winning
1597 	 * instance of kernfs_remove_self() finished.
1598 	 */
1599 	if (!(kn->flags & KERNFS_SUICIDAL)) {
1600 		kn->flags |= KERNFS_SUICIDAL;
1601 		__kernfs_remove(kn);
1602 		kn->flags |= KERNFS_SUICIDED;
1603 		ret = true;
1604 	} else {
1605 		wait_queue_head_t *waitq = &kernfs_root(kn)->deactivate_waitq;
1606 		DEFINE_WAIT(wait);
1607 
1608 		while (true) {
1609 			prepare_to_wait(waitq, &wait, TASK_UNINTERRUPTIBLE);
1610 
1611 			if ((kn->flags & KERNFS_SUICIDED) &&
1612 			    atomic_read(&kn->active) == KN_DEACTIVATED_BIAS)
1613 				break;
1614 
1615 			up_write(&root->kernfs_rwsem);
1616 			schedule();
1617 			down_write(&root->kernfs_rwsem);
1618 		}
1619 		finish_wait(waitq, &wait);
1620 		WARN_ON_ONCE(!RB_EMPTY_NODE(&kn->rb));
1621 		ret = false;
1622 	}
1623 
1624 	/*
1625 	 * This must be done while kernfs_rwsem held exclusive; otherwise,
1626 	 * waiting for SUICIDED && deactivated could finish prematurely.
1627 	 */
1628 	kernfs_unbreak_active_protection(kn);
1629 
1630 	up_write(&root->kernfs_rwsem);
1631 	return ret;
1632 }
1633 
1634 /**
1635  * kernfs_remove_by_name_ns - find a kernfs_node by name and remove it
1636  * @parent: parent of the target
1637  * @name: name of the kernfs_node to remove
1638  * @ns: namespace tag of the kernfs_node to remove
1639  *
1640  * Look for the kernfs_node with @name and @ns under @parent and remove it.
1641  *
1642  * Return: %0 on success, -ENOENT if such entry doesn't exist.
1643  */
1644 int kernfs_remove_by_name_ns(struct kernfs_node *parent, const char *name,
1645 			     const void *ns)
1646 {
1647 	struct kernfs_node *kn;
1648 	struct kernfs_root *root;
1649 
1650 	if (!parent) {
1651 		WARN(1, KERN_WARNING "kernfs: can not remove '%s', no directory\n",
1652 			name);
1653 		return -ENOENT;
1654 	}
1655 
1656 	root = kernfs_root(parent);
1657 	down_write(&root->kernfs_rwsem);
1658 
1659 	kn = kernfs_find_ns(parent, name, ns);
1660 	if (kn) {
1661 		kernfs_get(kn);
1662 		__kernfs_remove(kn);
1663 		kernfs_put(kn);
1664 	}
1665 
1666 	up_write(&root->kernfs_rwsem);
1667 
1668 	if (kn)
1669 		return 0;
1670 	else
1671 		return -ENOENT;
1672 }
1673 
1674 /**
1675  * kernfs_rename_ns - move and rename a kernfs_node
1676  * @kn: target node
1677  * @new_parent: new parent to put @sd under
1678  * @new_name: new name
1679  * @new_ns: new namespace tag
1680  *
1681  * Return: %0 on success, -errno on failure.
1682  */
1683 int kernfs_rename_ns(struct kernfs_node *kn, struct kernfs_node *new_parent,
1684 		     const char *new_name, const void *new_ns)
1685 {
1686 	struct kernfs_node *old_parent;
1687 	struct kernfs_root *root;
1688 	const char *old_name = NULL;
1689 	int error;
1690 
1691 	/* can't move or rename root */
1692 	if (!kn->parent)
1693 		return -EINVAL;
1694 
1695 	root = kernfs_root(kn);
1696 	down_write(&root->kernfs_rwsem);
1697 
1698 	error = -ENOENT;
1699 	if (!kernfs_active(kn) || !kernfs_active(new_parent) ||
1700 	    (new_parent->flags & KERNFS_EMPTY_DIR))
1701 		goto out;
1702 
1703 	error = 0;
1704 	if ((kn->parent == new_parent) && (kn->ns == new_ns) &&
1705 	    (strcmp(kn->name, new_name) == 0))
1706 		goto out;	/* nothing to rename */
1707 
1708 	error = -EEXIST;
1709 	if (kernfs_find_ns(new_parent, new_name, new_ns))
1710 		goto out;
1711 
1712 	/* rename kernfs_node */
1713 	if (strcmp(kn->name, new_name) != 0) {
1714 		error = -ENOMEM;
1715 		new_name = kstrdup_const(new_name, GFP_KERNEL);
1716 		if (!new_name)
1717 			goto out;
1718 	} else {
1719 		new_name = NULL;
1720 	}
1721 
1722 	/*
1723 	 * Move to the appropriate place in the appropriate directories rbtree.
1724 	 */
1725 	kernfs_unlink_sibling(kn);
1726 	kernfs_get(new_parent);
1727 
1728 	/* rename_lock protects ->parent and ->name accessors */
1729 	spin_lock_irq(&kernfs_rename_lock);
1730 
1731 	old_parent = kn->parent;
1732 	kn->parent = new_parent;
1733 
1734 	kn->ns = new_ns;
1735 	if (new_name) {
1736 		old_name = kn->name;
1737 		kn->name = new_name;
1738 	}
1739 
1740 	spin_unlock_irq(&kernfs_rename_lock);
1741 
1742 	kn->hash = kernfs_name_hash(kn->name, kn->ns);
1743 	kernfs_link_sibling(kn);
1744 
1745 	kernfs_put(old_parent);
1746 	kfree_const(old_name);
1747 
1748 	error = 0;
1749  out:
1750 	up_write(&root->kernfs_rwsem);
1751 	return error;
1752 }
1753 
1754 /* Relationship between mode and the DT_xxx types */
1755 static inline unsigned char dt_type(struct kernfs_node *kn)
1756 {
1757 	return (kn->mode >> 12) & 15;
1758 }
1759 
1760 static int kernfs_dir_fop_release(struct inode *inode, struct file *filp)
1761 {
1762 	kernfs_put(filp->private_data);
1763 	return 0;
1764 }
1765 
1766 static struct kernfs_node *kernfs_dir_pos(const void *ns,
1767 	struct kernfs_node *parent, loff_t hash, struct kernfs_node *pos)
1768 {
1769 	if (pos) {
1770 		int valid = kernfs_active(pos) &&
1771 			pos->parent == parent && hash == pos->hash;
1772 		kernfs_put(pos);
1773 		if (!valid)
1774 			pos = NULL;
1775 	}
1776 	if (!pos && (hash > 1) && (hash < INT_MAX)) {
1777 		struct rb_node *node = parent->dir.children.rb_node;
1778 		while (node) {
1779 			pos = rb_to_kn(node);
1780 
1781 			if (hash < pos->hash)
1782 				node = node->rb_left;
1783 			else if (hash > pos->hash)
1784 				node = node->rb_right;
1785 			else
1786 				break;
1787 		}
1788 	}
1789 	/* Skip over entries which are dying/dead or in the wrong namespace */
1790 	while (pos && (!kernfs_active(pos) || pos->ns != ns)) {
1791 		struct rb_node *node = rb_next(&pos->rb);
1792 		if (!node)
1793 			pos = NULL;
1794 		else
1795 			pos = rb_to_kn(node);
1796 	}
1797 	return pos;
1798 }
1799 
1800 static struct kernfs_node *kernfs_dir_next_pos(const void *ns,
1801 	struct kernfs_node *parent, ino_t ino, struct kernfs_node *pos)
1802 {
1803 	pos = kernfs_dir_pos(ns, parent, ino, pos);
1804 	if (pos) {
1805 		do {
1806 			struct rb_node *node = rb_next(&pos->rb);
1807 			if (!node)
1808 				pos = NULL;
1809 			else
1810 				pos = rb_to_kn(node);
1811 		} while (pos && (!kernfs_active(pos) || pos->ns != ns));
1812 	}
1813 	return pos;
1814 }
1815 
1816 static int kernfs_fop_readdir(struct file *file, struct dir_context *ctx)
1817 {
1818 	struct dentry *dentry = file->f_path.dentry;
1819 	struct kernfs_node *parent = kernfs_dentry_node(dentry);
1820 	struct kernfs_node *pos = file->private_data;
1821 	struct kernfs_root *root;
1822 	const void *ns = NULL;
1823 
1824 	if (!dir_emit_dots(file, ctx))
1825 		return 0;
1826 
1827 	root = kernfs_root(parent);
1828 	down_read(&root->kernfs_rwsem);
1829 
1830 	if (kernfs_ns_enabled(parent))
1831 		ns = kernfs_info(dentry->d_sb)->ns;
1832 
1833 	for (pos = kernfs_dir_pos(ns, parent, ctx->pos, pos);
1834 	     pos;
1835 	     pos = kernfs_dir_next_pos(ns, parent, ctx->pos, pos)) {
1836 		const char *name = pos->name;
1837 		unsigned int type = dt_type(pos);
1838 		int len = strlen(name);
1839 		ino_t ino = kernfs_ino(pos);
1840 
1841 		ctx->pos = pos->hash;
1842 		file->private_data = pos;
1843 		kernfs_get(pos);
1844 
1845 		up_read(&root->kernfs_rwsem);
1846 		if (!dir_emit(ctx, name, len, ino, type))
1847 			return 0;
1848 		down_read(&root->kernfs_rwsem);
1849 	}
1850 	up_read(&root->kernfs_rwsem);
1851 	file->private_data = NULL;
1852 	ctx->pos = INT_MAX;
1853 	return 0;
1854 }
1855 
1856 const struct file_operations kernfs_dir_fops = {
1857 	.read		= generic_read_dir,
1858 	.iterate_shared	= kernfs_fop_readdir,
1859 	.release	= kernfs_dir_fop_release,
1860 	.llseek		= generic_file_llseek,
1861 };
1862