// eventpoll.c — extracted functions for Round 4 of the GPB experiment
// Source: torvalds/linux master, fs/eventpoll.c
// This is NOT the full file — only the functions relevant to the bug.
// Line numbers are from the original file.

// ======================================================================
// EP_UNACTIVE_PTR definition (lines 224-225)
// ======================================================================
#define EP_UNACTIVE_PTR ((void *) -1L)


// ======================================================================
// struct epitems_head + ep_ctl_ctx (lines 420-470)
// ======================================================================
/*
 * Per-do_epoll_ctl() scratch for the loop / path checks. Allocated on
 * the caller's stack; populated by ep_ctl_lock() and the downward
 * walk; consumed by reverse_path_check(); released by ep_ctl_unlock().
 * Only valid while the caller holds epnested_mutex.
 */
struct ep_ctl_ctx {
	/*
	 * Outer eventpoll for one ep_loop_check(); if the downward walk
	 * reaches it the insert would form a cycle.
	 */
	struct eventpoll *inserting_into;

	/*
	 * Singly-linked list of epitems_head objects collected during
	 * ep_loop_check_proc(), then walked by reverse_path_check().
	 * Terminated by EP_UNACTIVE_PTR, not NULL: epitems_head->next
	 * doubles as a membership flag (a NULL ->next means "not on this
	 * list", see ep_remove_file()), so the list uses a non-NULL
	 * sentinel to keep the tail head distinguishable from an unlisted
	 * one.
	 */
	struct epitems_head *tfile_check_list;

	/*
	 * Per-depth wakeup-path tally used by reverse_path_check_proc();
	 * reinitialized to zero at the start of each reverse_path_check()
	 * iteration.
	 */
	int path_count[PATH_ARR_SIZE];
};

/* Slab cache used to allocate "struct epitem" */
static struct kmem_cache *epi_cache __ro_after_init;

/* Slab cache used to allocate "struct eppoll_entry" */
static struct kmem_cache *pwq_cache __ro_after_init;

/*
 * Wrapper anchor for file->f_ep when the watched file is not itself an
 * eventpoll; for the epoll-watches-epoll case, file->f_ep points at
 * &watched_ep->refs directly. The ->next field threads
 * ctx->tfile_check_list during one EPOLL_CTL_ADD path check. The ->file
 * field holds a reference to the associated file while the head is on
 * the list.
 */
struct epitems_head {
	struct hlist_head epitems;
	struct epitems_head *next;
	struct file *file;
};

// ======================================================================
// free_ephead (lines 474-478)
// ======================================================================
static inline void free_ephead(struct epitems_head *head)
{
	if (head)
		kmem_cache_free(ephead_cache, head);
}

// ======================================================================
// list_file (lines 475-500)
// ======================================================================
{
	if (head)
		kmem_cache_free(ephead_cache, head);
}

static void list_file(struct file *file, struct ep_ctl_ctx *ctx)
{
	struct epitems_head *head;

	head = container_of(file->f_ep, struct epitems_head, epitems);
	if (!head->next) {
		/*
		 * The caller owns a reference to @file or holds the ep->mtx for the
		 * epitem that led here. The latter blocks eventpoll_release_file()
		 * before the file allocation can be freed and reused. A dying leaf
		 * can be skipped since removing links cannot increase the reverse
		 * path count.
		 */
		if (!file_ref_get(&file->f_ref))
			return;
		head->file = file;
		head->next = ctx->tfile_check_list;
		ctx->tfile_check_list = head;
	}
}


// ======================================================================
// unlist_file (lines 500-520)
// ======================================================================

static void unlist_file(struct epitems_head *head)
{
	struct epitems_head *to_free = head;
	struct hlist_node *p = rcu_dereference(hlist_first_rcu(&head->epitems));
	struct file *file = head->file;
	if (p) {
		struct epitem *epi= container_of(p, struct epitem, fllink);
		spin_lock(&epi->ffd.file->f_lock);
		if (!hlist_empty(&head->epitems))
			to_free = NULL;
		head->next = NULL;
		head->file = NULL;
		spin_unlock(&epi->ffd.file->f_lock);
	}
	free_ephead(to_free);
	fput(file);
}

#ifdef CONFIG_SYSCTL


// ======================================================================
// ep_remove_file (lines 1090-1135)
// ======================================================================
	return file;
}

/*
 * Takes &file->f_lock; returns with it released.
 */
static void ep_remove_file(struct eventpoll *ep, struct epitem *epi,
			     struct file *file)
{
	struct epitems_head *to_free = NULL;
	struct hlist_head *head;

	lockdep_assert_held(&ep->mtx);

	spin_lock(&file->f_lock);
	head = file->f_ep;
	if (hlist_is_singular_node(&epi->fllink, head)) {
		/*
		 * Last watcher: publish NULL so the eventpoll_release()
		 * fastpath in include/linux/eventpoll.h can skip the slow
		 * path on a future __fput(). Safe because every f_ep writer
		 * either holds a pin on @file via epi_fget() or is __fput()
		 * itself -- see the comment in eventpoll_release().
		 */
		WRITE_ONCE(file->f_ep, NULL);
		if (!is_file_epoll(file)) {
			struct epitems_head *v;
			v = container_of(head, struct epitems_head, epitems);
			if (!smp_load_acquire(&v->next))
				to_free = v;
		}
	}
	hlist_del_rcu(&epi->fllink);
	spin_unlock(&file->f_lock);
	free_ephead(to_free);
}

static void ep_remove_epi(struct eventpoll *ep, struct epitem *epi)
{
	lockdep_assert_held(&ep->mtx);

	rb_erase_cached(&epi->rbn, &ep->rbr);

	spin_lock_irq(&ep->lock);
	if (ep_is_linked(epi))
		list_del_init(&epi->rdllink);

// ======================================================================
// ep_remove (lines 1135-1170)
// ======================================================================
		list_del_init(&epi->rdllink);
	spin_unlock_irq(&ep->lock);

	wakeup_source_unregister(ep_wakeup_source(epi));
	/*
	 * At this point it is safe to free the eventpoll item. Use the union
	 * field epi->rcu, since we are trying to minimize the size of
	 * 'struct epitem'. The 'rbn' field is no longer in use. Protected by
	 * ep->mtx. The rcu read side, reverse_path_check_proc(), does not make
	 * use of the rbn field.
	 */
	kfree_rcu(epi, rcu);

	percpu_counter_dec(&ep->user->epoll_watches);
}

/*
 * ep_remove variant for callers owing an additional reference to the ep
 */
static void ep_remove(struct eventpoll *ep, struct epitem *epi)
{
	struct file *file __free(fput) = NULL;

	lockdep_assert_irqs_enabled();
	lockdep_assert_held(&ep->mtx);

	ep_unregister_pollwait(ep, epi);

	/*
	 * If we manage to grab a reference it means we're not in
	 * eventpoll_release_file() and aren't going to be: once @file's
	 * refcount has reached zero, file_ref_get() cannot bring it back.
	 */
	file = epi_fget(epi);
	if (!file)
		return;

// ======================================================================
// reverse_path_check (lines 1715-1740)
// ======================================================================
 *                      anchoring files with newly proposed links; make
 *                      sure those links don't push any path-length bucket
 *                      over its limit in path_limits[].
 * @ctx: Per-do_epoll_ctl() scratch for the loop / path checks.
 *
 * Return: %zero if the proposed links don't create too many paths,
 *	    %-1 otherwise.
 */
static int reverse_path_check(struct ep_ctl_ctx *ctx)
{
	struct epitems_head *p;

	for (p = ctx->tfile_check_list; p != EP_UNACTIVE_PTR; p = p->next) {
		int error;
		path_count_init(ctx);
		rcu_read_lock();
		error = reverse_path_check_proc(ctx, &p->epitems, 0);
		rcu_read_unlock();
		if (error)
			return error;
	}
	return 0;
}

static int ep_create_wakeup_source(struct epitem *epi)
{

// ======================================================================
// ep_attach_file / ep_register_epitem (lines 1785-1840)
// ======================================================================

	if (ep) {
		head = &ep->refs;
	} else if (!READ_ONCE(file->f_ep)) {
allocate:
		to_free = kmem_cache_zalloc(ephead_cache, GFP_KERNEL);
		if (!to_free)
			return -ENOMEM;
		head = &to_free->epitems;
	}
	spin_lock(&file->f_lock);
	if (!file->f_ep) {
		if (unlikely(!head)) {
			spin_unlock(&file->f_lock);
			goto allocate;
		}
		/* See eventpoll_release() for details. */
		WRITE_ONCE(file->f_ep, head);
		to_free = NULL;
	}
	hlist_add_head_rcu(&epi->fllink, file->f_ep);
	spin_unlock(&file->f_lock);
	free_ephead(to_free);
	return 0;
}

/*
 * Charge the user's epoll_watches quota, allocate a fresh epitem for
 * @tf, and initialize its fields. The returned item is not yet linked
 * into any data structure; the caller must install it via
 * ep_register_epitem() (which takes over on success) or kmem_cache_free()
 * it and decrement epoll_watches on its own.
 *
 * Returns ERR_PTR(-ENOSPC) if the quota is exceeded, ERR_PTR(-ENOMEM)
 * if the slab allocation fails.
 */
static struct epitem *ep_alloc_epitem(struct eventpoll *ep,
				      const struct epoll_event *event,
				      struct epoll_key *tf)
{
	struct epitem *epi;

	if (unlikely(percpu_counter_compare(&ep->user->epoll_watches,
					    max_user_watches) >= 0))
		return ERR_PTR(-ENOSPC);
	percpu_counter_inc(&ep->user->epoll_watches);

	epi = kmem_cache_zalloc(epi_cache, GFP_KERNEL);
	if (unlikely(!epi)) {
		percpu_counter_dec(&ep->user->epoll_watches);
		return ERR_PTR(-ENOMEM);
	}

	INIT_LIST_HEAD(&epi->rdllink);
	epi->ep = ep;
	epi->ffd = *tf;

// ======================================================================
// ep_insert (lines 1840-1960)
// ======================================================================
	epi->ffd = *tf;
	epi->event = *event;
	epi_clear_ovflist(epi);

	return epi;
}

/*
 * Install @epi into its target file's f_ep hlist and into @ep's rbtree,
 * taking one additional reference on @ep for the lifetime of the item.
 *
 * If @tep is non-NULL, the target file is itself an eventpoll; we hold
 * tep->mtx at subclass 1 across the attach + rbtree insert to serialize
 * with the target side. RB tree ops are protected by @ep->mtx, which
 * the caller already holds.
 *
 * On failure the epi is freed and the epoll_watches counter decremented,
 * matching ep_alloc_epitem()'s allocation. After this returns
 * successfully, ep_insert()'s later error paths use ep_remove() for
 * unwind; that cannot drop @ep's refcount to zero because the ep file
 * itself still holds the original reference.
 */
static int ep_register_epitem(struct ep_ctl_ctx *ctx, struct eventpoll *ep,
			      struct epitem *epi, struct eventpoll *tep,
			      int full_check)
{
	struct file *tfile = epi->ffd.file;
	int error;

	if (tep)
		mutex_lock_nested(&tep->mtx, 1);

	error = ep_attach_file(tfile, epi);
	if (unlikely(error)) {
		if (tep)
			mutex_unlock(&tep->mtx);
		kmem_cache_free(epi_cache, epi);
		percpu_counter_dec(&ep->user->epoll_watches);
		return error;
	}

	if (full_check && !tep)
		list_file(tfile, ctx);

	ep_rbtree_insert(ep, epi);

	if (tep)
		mutex_unlock(&tep->mtx);

	ep_get(ep);
	return 0;
}

/*
 * Must be called with "mtx" held.
 */
static int ep_insert(struct ep_ctl_ctx *ctx, struct eventpoll *ep,
		     const struct epoll_event *event, struct epoll_key *tf,
		     int full_check)
{
	int error, pwake = 0;
	__poll_t revents;
	struct epitem *epi;
	struct ep_pqueue epq;
	struct eventpoll *tep = NULL;

	if (is_file_epoll(tf->file))
		tep = tf->file->private_data;

	lockdep_assert_irqs_enabled();

	epi = ep_alloc_epitem(ep, event, tf);
	if (IS_ERR(epi))
		return PTR_ERR(epi);

	error = ep_register_epitem(ctx, ep, epi, tep, full_check);
	if (error)
		return error;

	/* Reject the insert if the new link would create too many back-paths. */
	if (unlikely(full_check && reverse_path_check(ctx))) {
		ep_remove(ep, epi);
		return -EINVAL;
	}

	if (epi->event.events & EPOLLWAKEUP) {
		error = ep_create_wakeup_source(epi);
		if (error) {
			ep_remove(ep, epi);
			return error;
		}
	}

	/* Initialize the poll table using the queue callback */
	epq.epi = epi;
	init_poll_funcptr(&epq.pt, ep_ptable_queue_proc);

	/*
	 * Attach the item to the poll hooks and get current event bits.
	 * We can safely use the file* here because its usage count has
	 * been increased by the caller of this function. Note that after
	 * this operation completes, the poll callback can start hitting
	 * the new item.
	 */
	revents = ep_item_poll(epi, &epq.pt, 1);

	/* ep_ptable_queue_proc() signals allocation failure by clearing epq.epi. */
	if (unlikely(!epq.epi)) {
		ep_remove(ep, epi);
		return -ENOMEM;
	}

	/* Drop the new item onto the ready list if it is already ready. */
	spin_lock_irq(&ep->lock);

	ep_set_busy_poll_napi_id(epi);

	if (revents && !ep_is_linked(epi)) {
		list_add_tail(&epi->rdllink, &ep->rdllist);
		ep_pm_stay_awake(epi);


// ======================================================================
// ep_loop_check_proc (lines 2380-2420)
// ======================================================================
 *                      epoll file does not create closed loops, and
 *                      determine the depth of the subtree starting at @ep
 *
 * @ctx: Per-do_epoll_ctl() scratch for the loop / path checks.
 * @ep: the &struct eventpoll to be currently checked.
 * @depth: Current depth of the path being checked.
 *
 * Return: depth of the subtree, or a value bigger than EP_MAX_NESTS if we found
 * a loop or went too deep.
 */
static int ep_loop_check_proc(struct ep_ctl_ctx *ctx,
			      struct eventpoll *ep, int depth)
{
	int result = 0;
	struct rb_node *rbp;
	struct epitem *epi;

	if (ep->gen == loop_check_gen)
		return ep->loop_check_depth;

	mutex_lock_nested(&ep->mtx, depth + 1);
	ep->gen = loop_check_gen;
	for (rbp = rb_first_cached(&ep->rbr); rbp; rbp = rb_next(rbp)) {
		epi = rb_entry(rbp, struct epitem, rbn);
		if (unlikely(is_file_epoll(epi->ffd.file))) {
			struct eventpoll *ep_tovisit;
			ep_tovisit = epi->ffd.file->private_data;
			if (ep_tovisit == ctx->inserting_into ||
			    depth > EP_MAX_NESTS)
				result = EP_MAX_NESTS+1;
			else
				result = max(result,
					     ep_loop_check_proc(ctx, ep_tovisit,
								depth + 1) + 1);
			if (result > EP_MAX_NESTS)
				break;
		} else {
			/*
			 * A non-epoll leaf. Queue it for the companion
			 * reverse_path_check() that runs after this walk so
			 * any new links we propose don't add too many wakeup

// ======================================================================
// clear_tfile_check_list (lines 2475-2500)
// ======================================================================
	rcu_read_unlock();

	return (depth+1+upwards_depth > EP_MAX_NESTS) ? -1 : 0;
}

static void clear_tfile_check_list(struct ep_ctl_ctx *ctx)
{
	rcu_read_lock();
	while (ctx->tfile_check_list != EP_UNACTIVE_PTR) {
		struct epitems_head *head = ctx->tfile_check_list;
		ctx->tfile_check_list = head->next;
		unlist_file(head);
	}
	rcu_read_unlock();
}

/*
 * Open an eventpoll file descriptor.
 */
static int do_epoll_create(int flags)
{
	int error;
	struct eventpoll *ep;

	/* Check the EPOLL_* constant for consistency.  */
	BUILD_BUG_ON(EPOLL_CLOEXEC != O_CLOEXEC);

// ======================================================================
// do_epoll_ctl_file / ep_ctl_lock / ep_ctl_unlock (lines 2590-2700)
// ======================================================================
	if (error)
		return error;

	if (op != EPOLL_CTL_ADD)
		return 0;
	if (!READ_ONCE(epfile->f_ep) && ep->gen != loop_check_gen &&
	    !is_file_epoll(tfile))
		return 0;

	/* Full check needed: drop ep->mtx so we can take epnested_mutex. */
	mutex_unlock(&ep->mtx);
	error = epoll_mutex_lock(&epnested_mutex, nonblock);
	if (error)
		return error;

	loop_check_gen++;

	if (is_file_epoll(tfile)) {
		tep = tfile->private_data;
		if (ep_loop_check(ctx, ep, tep) != 0) {
			error = -ELOOP;
			goto err_unlock_nested;
		}
	}

	error = epoll_mutex_lock(&ep->mtx, nonblock);
	if (error)
		goto err_unlock_nested;

	return 1;

err_unlock_nested:
	clear_tfile_check_list(ctx);
	loop_check_gen++;
	mutex_unlock(&epnested_mutex);
	return error;
}

static void ep_ctl_unlock(struct ep_ctl_ctx *ctx, struct eventpoll *ep,
			  int full_check)
{
	mutex_unlock(&ep->mtx);
	if (full_check) {
		clear_tfile_check_list(ctx);
		loop_check_gen++;
		mutex_unlock(&epnested_mutex);
	}
}

int do_epoll_ctl_file(struct file *f, int op, struct epoll_key *tf,
		      struct epoll_event *epds, bool nonblock)
{
	int error;
	int full_check;
	struct eventpoll *ep;
	struct epitem *epi;
	struct ep_ctl_ctx ctx = {
		.tfile_check_list = EP_UNACTIVE_PTR,
	};

	/* The target file descriptor must support poll */
	if (!file_can_poll(tf->file))
		return -EPERM;

	/* Check if EPOLLWAKEUP is allowed */
	if (ep_op_has_event(op))
		ep_take_care_of_epollwakeup(epds);

	/*
	 * The @f file must itself be an eventpoll, and we do not permit
	 * adding an epoll file descriptor inside itself.
	 */
	if (f == tf->file || !is_file_epoll(f))
		return -EINVAL;

	/*
	 * epoll adds to the wakeup queue at EPOLL_CTL_ADD time only,
	 * so EPOLLEXCLUSIVE is not allowed for a EPOLL_CTL_MOD operation.
	 * Also, nested exclusive wakeups are not supported.
	 */
	if (ep_op_has_event(op) && (epds->events & EPOLLEXCLUSIVE)) {
		if (op == EPOLL_CTL_MOD)
			return -EINVAL;
		if (op == EPOLL_CTL_ADD && (is_file_epoll(tf->file) ||
				(epds->events & ~EPOLLEXCLUSIVE_OK_BITS)))
			return -EINVAL;
	}

	ep = f->private_data;

	full_check = ep_ctl_lock(&ctx, ep, op, f, tf->file, nonblock);
	if (full_check < 0)
		return full_check;

	/*
	 * Look the target up in ep's RB tree. We hold ep->mtx, so the
	 * item stays valid until we release.
	 */
	epi = ep_find(ep, tf);

	error = -EINVAL;
	switch (op) {
	case EPOLL_CTL_ADD:
		if (!epi) {
			epds->events |= EPOLLERR | EPOLLHUP;
			error = ep_insert(&ctx, ep, epds, tf, full_check);
		} else
			error = -EEXIST;
		break;
	case EPOLL_CTL_DEL:
		if (epi) {