Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1230859 > unrolled thread

Re: [RFC v2 07/18] kthread: Allow to cancel kthread work

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Tejun Heo <tj@kernel.org> - 2015-09-22 21:40 +0200
    Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Petr Mladek <pmladek@suse.com> - 2015-09-25 13:30 +0200
      Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Tejun Heo <tj@kernel.org> - 2015-09-28 19:10 +0200
        Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Petr Mladek <pmladek@suse.com> - 2015-10-02 17:50 +0200
          Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Tejun Heo <tj@kernel.org> - 2015-10-02 21:30 +0200
            Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Petr Mladek <pmladek@suse.com> - 2015-10-05 12:10 +0200
              Re: [RFC v2 07/18] kthread: Allow to cancel kthread work Petr Mladek <pmladek@suse.com> - 2015-10-05 13:10 +0200

#1230859 — Re: [RFC v2 07/18] kthread: Allow to cancel kthread work

On Mon, Sep 21, 2015 at 03:03:48PM +0200, Petr Mladek wrote:
>  /**
> + * try_to_grab_pending_kthread_work - steal kthread work item from worklist,
> + *	and disable irq
> + * @work: work item to steal
> + * @is_dwork: @work is a delayed_work
> + * @flags: place to store irq state
> + *
> + * Try to grab PENDING bit of @work.  This function can handle @work in any
> + * stable state - idle, on timer or on worklist.
> + *
> + * Return:
> + *  1		if @work was pending and we successfully stole PENDING
> + *  0		if @work was idle and we claimed PENDING
> + *  -EAGAIN	if PENDING couldn't be grabbed at the moment, safe to busy-retry
> + *  -ENOENT	if someone else is canceling @work, this state may persist
> + *		for arbitrarily long
> + *
> + * Note:
> + * On >= 0 return, the caller owns @work's PENDING bit.  To avoid getting
> + * interrupted while holding PENDING and @work off queue, irq must be
> + * disabled on return.  This, combined with delayed_work->timer being
> + * irqsafe, ensures that we return -EAGAIN for finite short period of time.
> + *
> + * On successful return, >= 0, irq is disabled and the caller is
> + * responsible for releasing it using local_irq_restore(*@flags).
> + *
> + * This function is safe to call from any context including IRQ handler.
> + */

Ugh... I think this is way too much for kthread_worker.  Workqueue is
as complex as it is partly for historical reasons and partly because
it's used so widely and heavily.  kthread_worker is always guaranteed
to have a single worker and in most cases maybe several work items.
There's no reason to bring this level of complexity onto it.
Providing simliar semantics is fine but it should be possible to do
this in a lot simpler way if the requirements on space and concurrency
is this much lower.

e.g. always embed timer_list in a work item and use per-worker
spinlock to synchronize access to both the work item and timer and use
per-work-item mutex to synchronize multiple cancelers.  Let's please
keep it simple.

Thanks.

-- 
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1232724

On Tue 2015-09-22 15:35:13, Tejun Heo wrote:
> On Mon, Sep 21, 2015 at 03:03:48PM +0200, Petr Mladek wrote:
> >  /**
> > + * try_to_grab_pending_kthread_work - steal kthread work item from worklist,
> > + *	and disable irq
> > + * @work: work item to steal
> > + * @is_dwork: @work is a delayed_work
> > + * @flags: place to store irq state
> > + *
> > + * Try to grab PENDING bit of @work.  This function can handle @work in any
> > + * stable state - idle, on timer or on worklist.
> > + *
> > + * Return:
> > + *  1		if @work was pending and we successfully stole PENDING
> > + *  0		if @work was idle and we claimed PENDING
> > + *  -EAGAIN	if PENDING couldn't be grabbed at the moment, safe to busy-retry
> > + *  -ENOENT	if someone else is canceling @work, this state may persist
> > + *		for arbitrarily long
> > + *
> > + * Note:
> > + * On >= 0 return, the caller owns @work's PENDING bit.  To avoid getting
> > + * interrupted while holding PENDING and @work off queue, irq must be
> > + * disabled on return.  This, combined with delayed_work->timer being
> > + * irqsafe, ensures that we return -EAGAIN for finite short period of time.
> > + *
> > + * On successful return, >= 0, irq is disabled and the caller is
> > + * responsible for releasing it using local_irq_restore(*@flags).
> > + *
> > + * This function is safe to call from any context including IRQ handler.
> > + */
> 
> Ugh... I think this is way too much for kthread_worker.  Workqueue is
> as complex as it is partly for historical reasons and partly because
> it's used so widely and heavily.  kthread_worker is always guaranteed
> to have a single worker and in most cases maybe several work items.
> There's no reason to bring this level of complexity onto it.
> Providing simliar semantics is fine but it should be possible to do
> this in a lot simpler way if the requirements on space and concurrency
> is this much lower.
> 
> e.g. always embed timer_list in a work item and use per-worker
> spinlock to synchronize access to both the work item and timer and use
> per-work-item mutex to synchronize multiple cancelers.  Let's please
> keep it simple.

I thought about it a lot and I do not see a way how to make it easier
using the locks.

I guess that you are primary interested into the two rather
complicated things:


1) PENDING state plus -EAGAIN/busy loop cycle
---------------------------------------------

IMHO, we want to use the timer because it is an elegant solution.
Then we must release the lock when the timer is running. The lock
must be taken by the timer->function(). And there is a small window
when the timer is not longer pending but timer->function is not running:

CPU0                            CPU1

run_timer_softirq()
  __run_timers()
    detach_expired_timer()
      detach_timer()
	#clear_pending

				try_to_grab_pending_kthread_work()
				  del_timer()
				    # fails because not pending

				  test_and_set_bit(KTHREAD_WORK_PENDING_BIT)
				    # fails because already set

				  if (!list_empty(&work->node))
				    # fails because still not queued

			!!! problematic window !!!

    call_timer_fn()
     queue_kthraed_work()


2) CANCEL state plus custom waitqueue
-------------------------------------

cancel_kthread_work_sync() has to wait for the running work. It might take
quite some time. Therefore we could not block others by a spinlock.
Also others could not wait for the spin lock in a busy wait.


IMHO, the proposed and rather complex solutions are needed in both cases.

Or did I miss a possible trick, please?

Best Regards,
Petr
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1234302

Hello, Petr.

On Fri, Sep 25, 2015 at 01:26:17PM +0200, Petr Mladek wrote:
> 1) PENDING state plus -EAGAIN/busy loop cycle
> ---------------------------------------------
> 
> IMHO, we want to use the timer because it is an elegant solution.
> Then we must release the lock when the timer is running. The lock
> must be taken by the timer->function(). And there is a small window
> when the timer is not longer pending but timer->function is not running:
> 
> CPU0                            CPU1
> 
> run_timer_softirq()
>   __run_timers()
>     detach_expired_timer()
>       detach_timer()
> 	#clear_pending
> 
> 				try_to_grab_pending_kthread_work()
> 				  del_timer()
> 				    # fails because not pending
> 
> 				  test_and_set_bit(KTHREAD_WORK_PENDING_BIT)
> 				    # fails because already set
> 
> 				  if (!list_empty(&work->node))
> 				    # fails because still not queued
> 
> 			!!! problematic window !!!
> 
>     call_timer_fn()
>      queue_kthraed_work()

Let's say each work item has a state variable which is protected by a
lock and the state can be one of IDLE, PENDING, CANCELING.  Let's also
assume that all cancelers synchronize with each other via mutex, so we
only have to worry about a single canceler.  Wouldn't something like
the following work while being a lot simpler?

Delayed queueing and execution.

1. Lock and check whether state is IDLE.  If not, nothing to do.

2. Set state to PENDING and schedule the timer and unlock.

3. On expiration, timer_fn grabs the lock and see whether state is
   still PENDING.  If so, schedule the work item for execution;
   otherwise, nothing to do.

4. After dequeueing from execution queue with lock held, the worker is
   marked as executing the work item and state is reset to IDLE.

Canceling

1. Lock, dequeue and set the state to CANCELING.

2. Unlock and perform del_timer_sync().

3. Flush the work item.

4. Lock and reset the state to IDLE and unlock.


> 2) CANCEL state plus custom waitqueue
> -------------------------------------
> 
> cancel_kthread_work_sync() has to wait for the running work. It might take
> quite some time. Therefore we could not block others by a spinlock.
> Also others could not wait for the spin lock in a busy wait.

Hmmm?  Cancelers can synchronize amongst them using a mutex and the
actual work item wait can use flushing.

> IMHO, the proposed and rather complex solutions are needed in both cases.
> 
> Or did I miss a possible trick, please?

I probably have missed something in the above and it is not completley
correct but I do think it can be way simpler than how workqueue does
it.

Thanks.

-- 
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1238368

On Mon 2015-09-28 13:03:14, Tejun Heo wrote:
> Hello, Petr.
> 
> On Fri, Sep 25, 2015 at 01:26:17PM +0200, Petr Mladek wrote:
> > 1) PENDING state plus -EAGAIN/busy loop cycle
> > ---------------------------------------------
> > 
> > IMHO, we want to use the timer because it is an elegant solution.
> > Then we must release the lock when the timer is running. The lock
> > must be taken by the timer->function(). And there is a small window
> > when the timer is not longer pending but timer->function is not running:
> > 
> > CPU0                            CPU1
> > 
> > run_timer_softirq()
> >   __run_timers()
> >     detach_expired_timer()
> >       detach_timer()
> > 	#clear_pending
> > 
> > 				try_to_grab_pending_kthread_work()
> > 				  del_timer()
> > 				    # fails because not pending
> > 
> > 				  test_and_set_bit(KTHREAD_WORK_PENDING_BIT)
> > 				    # fails because already set
> > 
> > 				  if (!list_empty(&work->node))
> > 				    # fails because still not queued
> > 
> > 			!!! problematic window !!!
> > 
> >     call_timer_fn()
> >      queue_kthraed_work()
> 
> Let's say each work item has a state variable which is protected by a
> lock and the state can be one of IDLE, PENDING, CANCELING.  Let's also
> assume that all cancelers synchronize with each other via mutex, so we
> only have to worry about a single canceler.  Wouldn't something like
> the following work while being a lot simpler?
> 
> Delayed queueing and execution.
> 
> 1. Lock and check whether state is IDLE.  If not, nothing to do.
> 
> 2. Set state to PENDING and schedule the timer and unlock.
> 
> 3. On expiration, timer_fn grabs the lock and see whether state is
>    still PENDING.  If so, schedule the work item for execution;
>    otherwise, nothing to do.
> 
> 4. After dequeueing from execution queue with lock held, the worker is
>    marked as executing the work item and state is reset to IDLE.
> 
> Canceling
> 
> 1. Lock, dequeue and set the state to CANCELING.
> 
> 2. Unlock and perform del_timer_sync().
> 
> 3. Flush the work item.
> 
> 4. Lock and reset the state to IDLE and unlock.
> 
> 
> > 2) CANCEL state plus custom waitqueue
> > -------------------------------------
> > 
> > cancel_kthread_work_sync() has to wait for the running work. It might take
> > quite some time. Therefore we could not block others by a spinlock.
> > Also others could not wait for the spin lock in a busy wait.
> 
> Hmmm?  Cancelers can synchronize amongst them using a mutex and the
> actual work item wait can use flushing.
> 
> > IMHO, the proposed and rather complex solutions are needed in both cases.
> > 
> > Or did I miss a possible trick, please?
> 
> I probably have missed something in the above and it is not completley
> correct but I do think it can be way simpler than how workqueue does
> it.

I have played with this idea and it opens a can of worms with locking
problems and it looks even more complicated.

Let me show this on a snippet of code:

struct kthread_worker {
	spinlock_t		lock;
	struct list_head	work_list;
	struct kthread_work	*current_work;
};

enum {
	KTHREAD_WORK_IDLE,
	KTHREAD_WORK_PENDING,
	KTHREAD_WORK_CANCELING,
};

struct kthread_work {
	unsigned int		flags;
	spinlock_t		lock;
	struct list_head	node;
	kthread_work_func_t	func;
	struct kthread_worker	*worker;
};


/* the main kthread worker cycle */
int kthread_worker_fn(void *worker_ptr)
{
	struct kthread_worker *worker = worker_ptr;
	struct kthread_work *work;

repeat:

	work = NULL;
	spin_lock_irq(&worker->lock);
	if (!list_empty(&worker->work_list)) {
		work = list_first_entry(&worker->work_list,
					struct kthread_work, node);
		spin_lock(&work->lock);
		list_del_init(&work->node);
		work->flags = KTHREAD_WORK_IDLE;
		spin_unlock(&work->lock);
	}
	worker->current_work = work;
	spin_unlock_irq(&worker->lock);

	if (work) {
		__set_current_state(TASK_RUNNING);
		work->func(work);
	} else if (!freezing(current))
		schedule();

	goto repeat;
}
EXPORT_SYMBOL_GPL(kthread_worker_fn);


static void __queue_kthread_work(struct kthread_worker *worker,
			  struct kthread_work *work)
{
	list_add_tail(&work->node, pos);
	work->worker = worker;
}


bool queue_kthread_work(struct kthread_worker *worker,
			struct kthread_work *work)
{
	bool ret = false;
	unsigned long flags;

	/*
	 * Lock worker first to avoid ABBA deadlock.
	 * What if the work is already queued to another worker?
	 */
	spin_lock_irqsave(&worker->lock, flags);
	spin_lock(&work->lock);

	if (work->flags != KTHREAD_WORK_IDLE)
		goto unlock_out;

	__queue_kthread_work(worker, work);
	ret = true;

unlock_out:
	spin_unlock(&work->lock);
	spin_unlock_irqrestore(&worker->lock, flags);
out:
	return ret;
}

bool cancel_kthread_work_sync(struct kthread_work *work)
{
	struct kthread_worker *worker;
	bool flush = true;
	unsigned long flags;

again:
	worker = ACCESS_ONCE(work->worker);

	if (worker)
		spin_lock_irqsave(&worker->lock, flags);
	else
		local_irq_save(flags);

	spin_lock(&work->lock);

	if (worker && worker != work->worker) {
		spin_unlock(&work->lock);
		spin_unlock_irqrestore(&worker->lock, flags);
		goto again;
	}

	switch (work->flags) {
	case KTHREAD_WORK_PENDING:
		list_del_init(&work->node);
	case KTHREAD_WORK_IDLE:
		work->flags = KTHREAD_WORK_CANCELING;
		break;
	case KTHREAD_WORK_CANCELING:
		/*
		 * Some other work is canceling. Let's wait in a
		 * custom waitqueue until the work is flushed.
		 */
		prepare_to_wait_exclusive(&cancel_waitq, &cwait.wait,
						  TASK_UNINTERRUPTIBLE);
		flush = false;
		break;
	}

	spin_unlock(&work->lock);
	if (worker)
		spin_unlock_irqrestore(&worker->lock, flags);
	else
		local_irq_restore(flags);

	if (flush) {
		kthread_work_flush(work);
		/*
		 * We are the cancel leader. Nobody else could manipulate the
		 * work.
		 */
		work->flags = KTHREAD_WORK_IDLE;
		/*
		 * Paired with prepare_to_wait() above so that either
		 * waitqueue_active() is visible here or CANCELING bit is
		 * visible there.
		 */
		smp_mb();
		if (waitqueue_active(&cancel_waitq))
			__wake_up(&cancel_waitq, TASK_NORMAL, 1, work);
	} elseif (READ_ONCE(work->flags) == KTHREAD_WORK_CANCELING) {
	       schedule();
	}
}


IMHO, we need both locks. The worker manipulates more works and
need its own lock. We need work-specific lock because the work
might be assigned to different workers and we need to be sure
that the operations are really serialized, e.g. queuing.

Now, worker_fn() needs to get the first work from the the worker list
and then manipulate the work => it needs to get the worker->lock
and then work->lock.

It means that most other functions would need to take both locks
in this order to avoid ABBA deadlock. This causes quite some
complications, e.g. in cancel_work().

There might be even more problems if we try to queue the same work
into more workers and we start mixing the locks from different
workers.

I do not know. It is possible that you prefer this solution than
the atomic bit operations. Also it is possible that there exists
a trick that might make it easier.

I would personally prefer to use the tricks from the workqueues.
They are proven to work and they make the code faster. I think
that we might need to queue the work in a sensitive fast path.

IMHO, the code already is much easier than the workqueues because
there are no pools of kthreads behind each worker.

Best Regards,
Petr
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1238551

Hello,

On Fri, Oct 02, 2015 at 05:43:36PM +0200, Petr Mladek wrote:
> IMHO, we need both locks. The worker manipulates more works and
> need its own lock. We need work-specific lock because the work
> might be assigned to different workers and we need to be sure
> that the operations are really serialized, e.g. queuing.

I don't think we need per-work lock.  Do we have such usage in kernel
at all?  If you're worried, let the first queueing record the worker
and trigger warning if someone tries to queue it anywhere else.  This
doesn't need to be full-on general like workqueue.  Let's make
reasonable trade-offs where possible.

Thanks.

-- 
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239407

On Fri 2015-10-02 15:24:53, Tejun Heo wrote:
> Hello,
> 
> On Fri, Oct 02, 2015 at 05:43:36PM +0200, Petr Mladek wrote:
> > IMHO, we need both locks. The worker manipulates more works and
> > need its own lock. We need work-specific lock because the work
> > might be assigned to different workers and we need to be sure
> > that the operations are really serialized, e.g. queuing.
> 
> I don't think we need per-work lock.  Do we have such usage in kernel
> at all?  If you're worried, let the first queueing record the worker
> and trigger warning if someone tries to queue it anywhere else.  This
> doesn't need to be full-on general like workqueue.  Let's make
> reasonable trade-offs where possible.

I actually thought about this simplification as well. But then I am
in doubts about the API. It would make sense to assign the worker
when the work is being initialized and avoid the duplicate information
when the work is being queued:

	init_kthread_work(work, fn, worker);
	queue_work(work);

Or would you prefer to keep the API similar to workqueues even when
it makes less sense here?


In each case, we need a way to switch the worker if the old one
is destroyed and a new one is started later. We would need
something like:

	reset_work(work, worker)
or
	reinit_work(work, fn, worker)


Thanks for feedback.

Best Regards,
Petr
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1239466

On Mon 2015-10-05 12:07:58, Petr Mladek wrote:
> On Fri 2015-10-02 15:24:53, Tejun Heo wrote:
> > Hello,
> > 
> > On Fri, Oct 02, 2015 at 05:43:36PM +0200, Petr Mladek wrote:
> > > IMHO, we need both locks. The worker manipulates more works and
> > > need its own lock. We need work-specific lock because the work
> > > might be assigned to different workers and we need to be sure
> > > that the operations are really serialized, e.g. queuing.
> > 
> > I don't think we need per-work lock.  Do we have such usage in kernel
> > at all?  If you're worried, let the first queueing record the worker
> > and trigger warning if someone tries to queue it anywhere else.  This
> > doesn't need to be full-on general like workqueue.  Let's make
> > reasonable trade-offs where possible.
> 
> I actually thought about this simplification as well. But then I am
> in doubts about the API. It would make sense to assign the worker
> when the work is being initialized and avoid the duplicate information
> when the work is being queued:
> 
> 	init_kthread_work(work, fn, worker);
> 	queue_work(work);
> 
> Or would you prefer to keep the API similar to workqueues even when
> it makes less sense here?
> 
> 
> In each case, we need a way to switch the worker if the old one
> is destroyed and a new one is started later. We would need
> something like:
> 
> 	reset_work(work, worker)
> or
> 	reinit_work(work, fn, worker)

I was too fast. We could set "work->worker = NULL" when the work
finishes and it is not pending. It means that it will be connected
to the particular worker only when used. Then we could keep the
workqueues-like API and do not need reset_work().

I am going to play with this. I feel that it might work.

Best Regards,
Petr
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web