dir.c

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