task.c 23.9 KB
Newer Older
Bob Halley's avatar
Bob Halley committed
1
/*
Bob Halley's avatar
Bob Halley committed
2
 * Copyright (C) 1998, 1999  Internet Software Consortium.
Bob Halley's avatar
Bob Halley committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
 * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 * SOFTWARE.
 */
Bob Halley's avatar
base  
Bob Halley committed
17

Bob Halley's avatar
Bob Halley committed
18 19 20 21
/*
 * Principal Author: Bob Halley
 */

22 23 24 25 26
/*
 * XXXRTH  Need to document the states a task can be in, and the rules
 * for changing states.
 */

Bob Halley's avatar
Bob Halley committed
27 28
#include <config.h>

Bob Halley's avatar
base  
Bob Halley committed
29
#include <isc/assertions.h>
30
#include <isc/boolean.h>
Bob Halley's avatar
Bob Halley committed
31
#include <isc/thread.h>
32 33
#include <isc/mutex.h>
#include <isc/condition.h>
34
#include <isc/error.h>
35
#include <isc/event.h>
Bob Halley's avatar
Bob Halley committed
36
#include <isc/task.h>
Bob Halley's avatar
base  
Bob Halley committed
37

38
#include "util.h"
Bob Halley's avatar
base  
Bob Halley committed
39

Bob Halley's avatar
Bob Halley committed
40
#ifdef ISC_TASK_TRACE
41 42 43 44 45 46
#define XTRACE(m)		printf("task %p thread %lu: %s\n", \
				       task, isc_thread_self(), (m))
#define XTTRACE(t, m)		printf("task %p thread %lu: %s\n", \
				       (t), isc_thread_self(), (m))
#define XTHREADTRACE(m)		printf("thread %lu: %s\n", \
				       isc_thread_self(), (m))
Bob Halley's avatar
Bob Halley committed
47 48
#else
#define XTRACE(m)
49
#define XTTRACE(t, m)
50
#define XTHREADTRACE(m)
Bob Halley's avatar
Bob Halley committed
51
#endif
Bob Halley's avatar
base  
Bob Halley committed
52

Bob Halley's avatar
Bob Halley committed
53
/***
Bob Halley's avatar
Bob Halley committed
54
 *** Types.
Bob Halley's avatar
Bob Halley committed
55 56
 ***/

Bob Halley's avatar
Bob Halley committed
57 58
typedef enum {
	task_state_idle, task_state_ready, task_state_running,
59
	task_state_done
Bob Halley's avatar
Bob Halley committed
60 61 62 63 64 65
} task_state_t;

#define TASK_MAGIC			0x5441534BU	/* TASK. */
#define VALID_TASK(t)			((t) != NULL && \
					 (t)->magic == TASK_MAGIC)

Bob Halley's avatar
Bob Halley committed
66
struct isc_task {
Bob Halley's avatar
Bob Halley committed
67 68
	/* Not locked. */
	unsigned int			magic;
Bob Halley's avatar
Bob Halley committed
69
	isc_taskmgr_t *			manager;
Bob Halley's avatar
Bob Halley committed
70
	isc_mutex_t			lock;
Bob Halley's avatar
Bob Halley committed
71
	isc_mem_t *			mctx;
Bob Halley's avatar
Bob Halley committed
72 73 74
	/* Locked by task lock. */
	task_state_t			state;
	unsigned int			references;
Bob Halley's avatar
Bob Halley committed
75
	isc_eventlist_t			events;
76
	isc_eventlist_t			on_shutdown;
Bob Halley's avatar
Bob Halley committed
77
	unsigned int			quantum;
78
	unsigned int			flags;
Bob Halley's avatar
Bob Halley committed
79
	/* Locked by task manager lock. */
Bob Halley's avatar
Bob Halley committed
80 81
	LINK(isc_task_t)		link;
	LINK(isc_task_t)		ready_link;
Bob Halley's avatar
Bob Halley committed
82 83
};

Bob Halley's avatar
Bob Halley committed
84
#define TASK_F_SHUTTINGDOWN		0x01
85

86 87
#define TASK_SHUTTINGDOWN(t)		(((t)->flags & TASK_F_SHUTTINGDOWN) \
					 != 0)
88

Bob Halley's avatar
Bob Halley committed
89 90 91 92
#define TASK_MANAGER_MAGIC		0x54534B4DU	/* TSKM. */
#define VALID_MANAGER(m)		((m) != NULL && \
					 (m)->magic == TASK_MANAGER_MAGIC)

Bob Halley's avatar
Bob Halley committed
93
struct isc_taskmgr {
Bob Halley's avatar
Bob Halley committed
94 95
	/* Not locked. */
	unsigned int			magic;
Bob Halley's avatar
Bob Halley committed
96
	isc_mem_t *			mctx;
Bob Halley's avatar
Bob Halley committed
97
	isc_mutex_t			lock;
98 99
	unsigned int			workers;
	isc_thread_t *			threads;
Bob Halley's avatar
Bob Halley committed
100 101
	/* Locked by task manager lock. */
	unsigned int			default_quantum;
Bob Halley's avatar
Bob Halley committed
102 103
	LIST(isc_task_t)		tasks;
	LIST(isc_task_t)		ready_tasks;
Bob Halley's avatar
Bob Halley committed
104
	isc_condition_t			work_available;
Bob Halley's avatar
Bob Halley committed
105
	isc_boolean_t			exiting;
Bob Halley's avatar
Bob Halley committed
106
};
Bob Halley's avatar
Bob Halley committed
107

Bob Halley's avatar
Bob Halley committed
108 109
#define DEFAULT_DEFAULT_QUANTUM		5
#define FINISHED(m)			((m)->exiting && EMPTY((m)->tasks))
Bob Halley's avatar
Bob Halley committed
110

Bob Halley's avatar
base  
Bob Halley committed
111 112 113 114 115
/***
 *** Tasks.
 ***/

static void
116
task_finished(isc_task_t *task) {
Bob Halley's avatar
Bob Halley committed
117
	isc_taskmgr_t *manager = task->manager;
Bob Halley's avatar
base  
Bob Halley committed
118 119

	REQUIRE(EMPTY(task->events));
120
	REQUIRE(EMPTY(task->on_shutdown));
121 122 123 124
	REQUIRE(task->references == 0);
	REQUIRE(task->state == task_state_done);

	XTRACE("task_finished");
Bob Halley's avatar
base  
Bob Halley committed
125 126 127 128 129 130 131 132 133 134 135 136 137

	LOCK(&manager->lock);
	UNLINK(manager->tasks, task, link);
	if (FINISHED(manager)) {
		/*
		 * All tasks have completed and the
		 * task manager is exiting.  Wake up
		 * any idle worker threads so they
		 * can exit.
		 */
		BROADCAST(&manager->work_available);
	}
	UNLOCK(&manager->lock);
138

Bob Halley's avatar
Bob Halley committed
139
	(void)isc_mutex_destroy(&task->lock);
Bob Halley's avatar
base  
Bob Halley committed
140
	task->magic = 0;
141
	isc_mem_put(task->mctx, task, sizeof *task);
Bob Halley's avatar
base  
Bob Halley committed
142 143
}

Bob Halley's avatar
Bob Halley committed
144
isc_result_t
Bob Halley's avatar
Bob Halley committed
145
isc_task_create(isc_taskmgr_t *manager, isc_mem_t *mctx, unsigned int quantum,
146
		isc_task_t **taskp)
Bob Halley's avatar
Bob Halley committed
147
{
Bob Halley's avatar
Bob Halley committed
148
	isc_task_t *task;
Bob Halley's avatar
base  
Bob Halley committed
149 150 151 152

	REQUIRE(VALID_MANAGER(manager));
	REQUIRE(taskp != NULL && *taskp == NULL);

Bob Halley's avatar
Bob Halley committed
153 154 155
	if (mctx == NULL)
		mctx = manager->mctx;
	task = isc_mem_get(mctx, sizeof *task);
Bob Halley's avatar
base  
Bob Halley committed
156
	if (task == NULL)
Bob Halley's avatar
Bob Halley committed
157
		return (ISC_R_NOMEMORY);
158
	XTRACE("create");
Bob Halley's avatar
base  
Bob Halley committed
159
	task->manager = manager;
Bob Halley's avatar
Bob Halley committed
160
	task->mctx = mctx;
Bob Halley's avatar
Bob Halley committed
161
	if (isc_mutex_init(&task->lock) != ISC_R_SUCCESS) {
Bob Halley's avatar
Bob Halley committed
162
		isc_mem_put(mctx, task, sizeof *task);
Bob Halley's avatar
Bob Halley committed
163 164 165
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
166
	}
Bob Halley's avatar
base  
Bob Halley committed
167 168 169
	task->state = task_state_idle;
	task->references = 1;
	INIT_LIST(task->events);
170
	INIT_LIST(task->on_shutdown);
Bob Halley's avatar
base  
Bob Halley committed
171
	task->quantum = quantum;
Bob Halley's avatar
Bob Halley committed
172
	task->flags = 0;
Bob Halley's avatar
base  
Bob Halley committed
173 174 175 176
	INIT_LINK(task, link);
	INIT_LINK(task, ready_link);

	LOCK(&manager->lock);
Bob Halley's avatar
Bob Halley committed
177
	/* XXX Should disallow if task manager is exiting. */
Bob Halley's avatar
base  
Bob Halley committed
178 179 180 181 182
	if (task->quantum == 0)
		task->quantum = manager->default_quantum;
	APPEND(manager->tasks, task, link);
	UNLOCK(&manager->lock);

183
	task->magic = TASK_MAGIC;
Bob Halley's avatar
base  
Bob Halley committed
184 185
	*taskp = task;

Bob Halley's avatar
Bob Halley committed
186
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
187 188
}

Bob Halley's avatar
update  
Bob Halley committed
189
void
190
isc_task_attach(isc_task_t *source, isc_task_t **targetp) {
Bob Halley's avatar
base  
Bob Halley committed
191

192 193 194
	/*
	 * Attach *targetp to source.
	 */
Bob Halley's avatar
base  
Bob Halley committed
195

196 197
	REQUIRE(VALID_TASK(source));
	REQUIRE(targetp != NULL && *targetp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
198

199 200
	XTTRACE(source, "attach");

201 202 203 204 205
	LOCK(&source->lock);
	source->references++;
	UNLOCK(&source->lock);

	*targetp = source;
Bob Halley's avatar
base  
Bob Halley committed
206 207
}

208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
static inline isc_boolean_t
task_shutdown(isc_task_t *task) {
	isc_boolean_t was_idle = ISC_FALSE;
	isc_event_t *event, *prev;
	
	/*
	 * Caller must be holding the task's lock.
	 */

	XTRACE("task_shutdown");

	if (! TASK_SHUTTINGDOWN(task)) {
		XTRACE("shutting down");
		task->flags |= TASK_F_SHUTTINGDOWN;
		if (task->state == task_state_idle) {
			INSIST(EMPTY(task->events));
			task->state = task_state_ready;
			was_idle = ISC_TRUE;
		}
		INSIST(task->state == task_state_ready ||
		       task->state == task_state_running);
		/*
		 * Note that we post shutdown events LIFO.
		 */
		for (event = TAIL(task->on_shutdown);
		     event != NULL;
		     event = prev) {
			prev = PREV(event, link);
			DEQUEUE(task->on_shutdown, event, link);
			ENQUEUE(task->events, event, link);
		}
	}

	return (was_idle);
}

static inline void
task_ready(isc_task_t *task) {
	isc_taskmgr_t *manager = task->manager;

	REQUIRE(VALID_MANAGER(manager));
	REQUIRE(task->state == task_state_ready);

	XTRACE("task_ready");

	LOCK(&manager->lock);

	ENQUEUE(manager->ready_tasks, task, ready_link);
	SIGNAL(&manager->work_available);

	UNLOCK(&manager->lock);
}

Bob Halley's avatar
Bob Halley committed
261
static inline isc_boolean_t
262 263 264 265 266 267 268 269 270 271 272
task_detach(isc_task_t *task) {

	/*
	 * Caller must be holding the task lock.
	 */

	REQUIRE(task->references > 0);

	XTRACE("detach");

	task->references--;
Bob Halley's avatar
Bob Halley committed
273 274 275 276 277 278 279 280 281 282 283 284
	if (task->references == 0 && task->state == task_state_idle) {
		INSIST(EMPTY(task->events));
		/*
		 * There are no references to this task, and no
		 * pending events.  We could try to optimize and
		 * either initiate shutdown or clean up the task,
		 * depending on its state, but it's easier to just
		 * make the task ready and allow run() to deal with
		 * shutting down and termination.
		 */
		task->state = task_state_ready;
		return (ISC_TRUE);
285 286
	}

Bob Halley's avatar
Bob Halley committed
287
	return (ISC_FALSE);
288 289
}

Bob Halley's avatar
Bob Halley committed
290
void
Bob Halley's avatar
Bob Halley committed
291 292
isc_task_detach(isc_task_t **taskp) {
	isc_task_t *task;
Bob Halley's avatar
Bob Halley committed
293
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
294

295 296 297 298
	/*
	 * Detach *taskp from its task.
	 */

Bob Halley's avatar
base  
Bob Halley committed
299 300 301 302
	REQUIRE(taskp != NULL);
	task = *taskp;
	REQUIRE(VALID_TASK(task));

303 304
	XTRACE("isc_task_detach");

Bob Halley's avatar
base  
Bob Halley committed
305
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
306
	was_idle = task_detach(task);
Bob Halley's avatar
base  
Bob Halley committed
307 308
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
309
	if (was_idle)
310
		task_ready(task);
Bob Halley's avatar
base  
Bob Halley committed
311 312 313 314

	*taskp = NULL;
}

Bob Halley's avatar
Bob Halley committed
315 316 317
isc_mem_t *
isc_task_mem(isc_task_t *task) {

318 319 320 321
	/*
	 * Get the task's memory context.
	 */

Bob Halley's avatar
Bob Halley committed
322 323 324 325 326
	REQUIRE(VALID_TASK(task));
	
	return (task->mctx);
}

Bob Halley's avatar
Bob Halley committed
327 328 329
static inline isc_boolean_t
task_send(isc_task_t *task, isc_event_t **eventp) {
	isc_boolean_t was_idle = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
330
	isc_event_t *event;
331
	
332
	/*
333
	 * Caller must be holding the task lock.
334 335
	 */

Bob Halley's avatar
update  
Bob Halley committed
336 337
	REQUIRE(eventp != NULL);
	event = *eventp;
Bob Halley's avatar
base  
Bob Halley committed
338
	REQUIRE(event != NULL);
Bob Halley's avatar
Bob Halley committed
339 340
	REQUIRE(event->sender != NULL);
	REQUIRE(event->type > 0);
Bob Halley's avatar
Bob Halley committed
341
	REQUIRE(task->state != task_state_done);
Bob Halley's avatar
base  
Bob Halley committed
342

343 344
	XTRACE("task_send");

Bob Halley's avatar
Bob Halley committed
345 346 347 348
	if (task->state == task_state_idle) {
		was_idle = ISC_TRUE;
		INSIST(EMPTY(task->events));
		task->state = task_state_ready;
349
	}
Bob Halley's avatar
Bob Halley committed
350 351 352 353
	INSIST(task->state == task_state_ready ||
	       task->state == task_state_running);
	ENQUEUE(task->events, event, link);
	*eventp = NULL;
354

Bob Halley's avatar
Bob Halley committed
355 356
	return (was_idle);
}	
357

Bob Halley's avatar
Bob Halley committed
358
void
359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
isc_task_send(isc_task_t *task, isc_event_t **eventp) {
	isc_boolean_t was_idle;

	/*
	 * Send '*event' to 'task'.
	 */

	REQUIRE(VALID_TASK(task));

	XTRACE("isc_task_send");

	/*
	 * We're trying hard to hold locks for as short a time as possible.
	 * We're also trying to hold as few locks as possible.  This is why
	 * some processing is deferred until after the lock is released.
	 */
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
376
	was_idle = task_send(task, eventp);
Bob Halley's avatar
base  
Bob Halley committed
377 378 379 380 381 382
	UNLOCK(&task->lock);

	if (was_idle) {
		/*
		 * We need to add this task to the ready queue.
		 *
383 384 385
		 * We've waited until now to do it because making a task
		 * ready requires locking the manager.  If we tried to do
		 * this while holding the task lock, we could deadlock.
Bob Halley's avatar
base  
Bob Halley committed
386 387
		 *
		 * We've changed the state to ready, so no one else will
388 389 390
		 * be trying to add this task to the ready queue.  The
		 * only way to leave the ready state is by executing the
		 * task.  It thus doesn't matter if events are added,
391
		 * removed, or a shutdown is started in the interval
392 393
		 * between the time we released the task lock, and the time
		 * we add the task to the ready queue.
Bob Halley's avatar
base  
Bob Halley committed
394
		 */
395
		task_ready(task);
Bob Halley's avatar
base  
Bob Halley committed
396
	}
397 398
}

Bob Halley's avatar
Bob Halley committed
399
void
400
isc_task_sendanddetach(isc_task_t **taskp, isc_event_t **eventp) {
Bob Halley's avatar
Bob Halley committed
401
	isc_boolean_t idle1, idle2;
402 403 404 405 406 407 408 409 410 411 412 413
	isc_task_t *task;

	/*
	 * Send '*event' to '*taskp' and then detach '*taskp' from its
	 * task.
	 */

	REQUIRE(taskp != NULL);
	task = *taskp;
	REQUIRE(VALID_TASK(task));

	XTRACE("isc_task_sendanddetach");
Bob Halley's avatar
update  
Bob Halley committed
414

415
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
416 417
	idle1 = task_send(task, eventp);
	idle2 = task_detach(task);
418 419
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
420 421 422 423 424 425
	/*
	 * If idle1, then idle2 shouldn't be true as well since we're holding
	 * the task lock, and thus the task cannot switch from ready back to
	 * idle.
	 */
	INSIST(!(idle1 && idle2));
426

Bob Halley's avatar
Bob Halley committed
427 428
	if (idle1 || idle2)
		task_ready(task);
429 430

	*taskp = NULL;
Bob Halley's avatar
base  
Bob Halley committed
431 432
}

433 434 435 436 437 438
#define PURGE_OK(event)	(((event)->attributes & ISC_EVENTATTR_NOPURGE) == 0)

static unsigned int
dequeue_events(isc_task_t *task, void *sender, isc_eventtype_t first,
	       isc_eventtype_t last, void *tag,
	       isc_eventlist_t *events, isc_boolean_t purging)
439
{
Bob Halley's avatar
Bob Halley committed
440
	isc_event_t *event, *next_event;
441
	unsigned int count = 0;
442

Bob Halley's avatar
Bob Halley committed
443
	REQUIRE(VALID_TASK(task));
444
	REQUIRE(last >= first);
Bob Halley's avatar
Bob Halley committed
445

446
	XTRACE("dequeue_events");
Bob Halley's avatar
Bob Halley committed
447

Bob Halley's avatar
Bob Halley committed
448
	/*
449 450 451
	 * Events matching 'sender', whose type is >= first and <= last, and
	 * whose tag is 'tag' will be dequeued.  If 'purging', matching events
	 * which are marked as unpurgable will not be dequeued.
452
	 *
453
	 * sender == NULL means "any sender", and tag == NULL means "any tag".
Bob Halley's avatar
Bob Halley committed
454 455 456
	 */

	LOCK(&task->lock);
457 458

	for (event = HEAD(task->events); event != NULL; event = next_event) {
Bob Halley's avatar
Bob Halley committed
459
		next_event = NEXT(event, link);
Bob Halley's avatar
Bob Halley committed
460 461
		if (event->type >= first && event->type <= last &&
		    (sender == NULL || event->sender == sender) &&
462 463
		    (tag == NULL || event->tag == tag) &&
		    (!purging || PURGE_OK(event))) {
Bob Halley's avatar
Bob Halley committed
464
			DEQUEUE(task->events, event, link);
465 466
			ENQUEUE(*events, event, link);
			count++;
Bob Halley's avatar
Bob Halley committed
467 468
		}
	}
469

Bob Halley's avatar
Bob Halley committed
470 471
	UNLOCK(&task->lock);

472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
	return (count);
}

unsigned int
isc_task_purgerange(isc_task_t *task, void *sender, isc_eventtype_t first,
		    isc_eventtype_t last, void *tag)
{
	unsigned int count;
	isc_eventlist_t events;
	isc_event_t *event, *next_event;

	/*
	 * Purge events from a task's event queue.
	 */

	XTRACE("isc_task_purgerange");

	ISC_LIST_INIT(events);

	count = dequeue_events(task, sender, first, last, tag, &events,
			       ISC_TRUE);

	for (event = HEAD(events); event != NULL; event = next_event) {
Bob Halley's avatar
Bob Halley committed
495
		next_event = NEXT(event, link);
Bob Halley's avatar
Bob Halley committed
496
		isc_event_free(&event);
Bob Halley's avatar
Bob Halley committed
497
	}
498

499 500 501 502 503
	/*
	 * Note that purging never changes the state of the task.
	 */

	return (count);
Bob Halley's avatar
Bob Halley committed
504 505
}

506
unsigned int
Bob Halley's avatar
Bob Halley committed
507
isc_task_purge(isc_task_t *task, void *sender, isc_eventtype_t type,
508
	       void *tag)
Bob Halley's avatar
Bob Halley committed
509
{
510 511 512 513
	/*
	 * Purge events from a task's event queue.
	 */

514 515
	XTRACE("isc_task_purge");

Bob Halley's avatar
Bob Halley committed
516
	return (isc_task_purgerange(task, sender, type, type, tag));
517 518
}

Bob Halley's avatar
Bob Halley committed
519 520 521 522 523 524
isc_boolean_t
isc_task_purgeevent(isc_task_t *task, isc_event_t *event) {
	isc_event_t *curr_event, *next_event;

	/*
	 * Purge 'event' from a task's event queue.
525 526
	 *
	 * XXXRTH:  WARNING:  This method may be removed before beta.
Bob Halley's avatar
Bob Halley committed
527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545
	 */

	REQUIRE(VALID_TASK(task));

	/*
	 * If 'event' is on the task's event queue, it will be purged,
	 * unless it is marked as unpurgeable.  'event' does not have to be
	 * on the task's event queue; in fact, it can even be an invalid
	 * pointer.  Purging only occurs if the event is actually on the task's
	 * event queue.
	 *
	 * Purging never changes the state of the task.
	 */

	LOCK(&task->lock);
	for (curr_event = HEAD(task->events);
	     curr_event != NULL;
	     curr_event = next_event) {
		next_event = NEXT(curr_event, link);
546
		if (curr_event == event && PURGE_OK(event)) {
Bob Halley's avatar
Bob Halley committed
547 548 549 550 551 552 553 554 555 556 557 558 559 560
			DEQUEUE(task->events, curr_event, link);
			break;
		}
	}
	UNLOCK(&task->lock);

	if (curr_event == NULL)
		return (ISC_FALSE);

	isc_event_free(&curr_event);

	return (ISC_TRUE);
}

561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589
unsigned int
isc_task_unsendrange(isc_task_t *task, void *sender, isc_eventtype_t first,
		     isc_eventtype_t last, void *tag,
		     isc_eventlist_t *events)
{
	/*
	 * Remove events from a task's event queue.
	 */

	XTRACE("isc_task_unsendrange");

	return (dequeue_events(task, sender, first, last, tag, events,
			       ISC_FALSE));
}

unsigned int
isc_task_unsend(isc_task_t *task, void *sender, isc_eventtype_t type,
		void *tag, isc_eventlist_t *events)
{
	/*
	 * Remove events from a task's event queue.
	 */

	XTRACE("isc_task_unsend");

	return (dequeue_events(task, sender, type, type, tag, events,
			       ISC_FALSE));
}

590 591 592 593 594 595
isc_result_t
isc_task_onshutdown(isc_task_t *task, isc_taskaction_t action, void *arg) {
	isc_boolean_t disallowed = ISC_FALSE;
	isc_result_t result = ISC_R_SUCCESS;
	isc_event_t *event;

596 597 598 599 600
	/*
	 * Send a shutdown event with action 'action' and argument 'arg' when
	 * 'task' is shutdown.
	 */

601
	REQUIRE(VALID_TASK(task));
602
	REQUIRE(action != NULL);
603

604 605 606 607 608 609
	event = isc_event_allocate(task->mctx,
				   NULL,
				   ISC_TASKEVENT_SHUTDOWN,
				   action,
				   arg,
				   sizeof *event);
610 611 612 613
	if (event == NULL)
		return (ISC_R_NOMEMORY);

	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
614
	if (TASK_SHUTTINGDOWN(task)) {
615
		disallowed = ISC_TRUE;
616
		result = ISC_R_SHUTTINGDOWN;
617 618 619 620 621
	} else
		ENQUEUE(task->on_shutdown, event, link);
	UNLOCK(&task->lock);

	if (disallowed)
Bob Halley's avatar
Bob Halley committed
622
		isc_mem_put(task->mctx, event, sizeof *event);
623 624 625 626

	return (result);
}

Bob Halley's avatar
Bob Halley committed
627
void
Bob Halley's avatar
Bob Halley committed
628
isc_task_shutdown(isc_task_t *task) {
629
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
630

631 632 633 634
	/*
	 * Shutdown 'task'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
635 636 637
	REQUIRE(VALID_TASK(task));

	LOCK(&task->lock);
638
	was_idle = task_shutdown(task);
Bob Halley's avatar
base  
Bob Halley committed
639 640
	UNLOCK(&task->lock);

641 642
	if (was_idle)
		task_ready(task);
Bob Halley's avatar
Bob Halley committed
643
}
Bob Halley's avatar
base  
Bob Halley committed
644

Bob Halley's avatar
Bob Halley committed
645
void
Bob Halley's avatar
Bob Halley committed
646
isc_task_destroy(isc_task_t **taskp) {
Bob Halley's avatar
Bob Halley committed
647

648 649 650 651
	/*
	 * Destroy '*taskp'.
	 */

Bob Halley's avatar
Bob Halley committed
652 653
	REQUIRE(taskp != NULL);

Bob Halley's avatar
Bob Halley committed
654 655
	isc_task_shutdown(*taskp);
	isc_task_detach(taskp);
Bob Halley's avatar
base  
Bob Halley committed
656 657 658
}


Bob Halley's avatar
Bob Halley committed
659

Bob Halley's avatar
base  
Bob Halley committed
660 661 662 663
/***
 *** Task Manager.
 ***/

Bob Halley's avatar
update  
Bob Halley committed
664
static isc_threadresult_t
Bob Halley's avatar
Bob Halley committed
665 666 667
#ifdef _WIN32
WINAPI
#endif
Bob Halley's avatar
update  
Bob Halley committed
668
run(void *uap) {
Bob Halley's avatar
Bob Halley committed
669 670
	isc_taskmgr_t *manager = uap;
	isc_task_t *task;
Bob Halley's avatar
base  
Bob Halley committed
671

672
	XTHREADTRACE("start");
Bob Halley's avatar
base  
Bob Halley committed
673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729

	REQUIRE(VALID_MANAGER(manager));

	/*
	 * Again we're trying to hold the lock for as short a time as possible
	 * and to do as little locking and unlocking as possible.
	 * 
	 * In both while loops, the appropriate lock must be held before the
	 * while body starts.  Code which acquired the lock at the top of
	 * the loop would be more readable, but would result in a lot of
	 * extra locking.  Compare:
	 *
	 * Straightforward:
	 *
	 *	LOCK();
	 *	...
	 *	UNLOCK();
	 *	while (expression) {
	 *		LOCK();
	 *		...
	 *		UNLOCK();
	 *
	 *	       	Unlocked part here...
	 *
	 *		LOCK();
	 *		...
	 *		UNLOCK();
	 *	}
	 *
	 * Note how if the loop continues we unlock and then immediately lock.
	 * For N iterations of the loop, this code does 2N+1 locks and 2N+1
	 * unlocks.  Also note that the lock is not held when the while
	 * condition is tested, which may or may not be important, depending
	 * on the expression.
	 * 
	 * As written:
	 *
	 *	LOCK();
	 *	while (expression) {
	 *		...
	 *		UNLOCK();
	 *
	 *	       	Unlocked part here...
	 *
	 *		LOCK();
	 *		...
	 *	}
	 *	UNLOCK();
	 *
	 * For N iterations of the loop, this code does N+1 locks and N+1
	 * unlocks.  The while expression is always protected by the lock.
	 */

	LOCK(&manager->lock);
	while (!FINISHED(manager)) {
		/*
		 * For reasons similar to those given in the comment in
730
		 * isc_task_send() above, it is safe for us to dequeue
Bob Halley's avatar
base  
Bob Halley committed
731 732 733 734 735
		 * the task while only holding the manager lock, and then
		 * change the task to running state while only holding the
		 * task lock.
		 */
		while (EMPTY(manager->ready_tasks) && !FINISHED(manager)) {
736
			XTHREADTRACE("wait");
Bob Halley's avatar
base  
Bob Halley committed
737
			WAIT(&manager->work_available, &manager->lock);
738
			XTHREADTRACE("awake");
Bob Halley's avatar
base  
Bob Halley committed
739
		}
740
		XTHREADTRACE("working");
Bob Halley's avatar
base  
Bob Halley committed
741 742 743
		
		task = HEAD(manager->ready_tasks);
		if (task != NULL) {
Bob Halley's avatar
Bob Halley committed
744
			unsigned int dispatch_count = 0;
Bob Halley's avatar
Bob Halley committed
745 746
			isc_boolean_t done = ISC_FALSE;
			isc_boolean_t requeue = ISC_FALSE;
747
			isc_boolean_t finished = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
748
			isc_event_t *event;
Bob Halley's avatar
base  
Bob Halley committed
749 750 751 752 753 754 755 756 757 758 759 760

			INSIST(VALID_TASK(task));

			/*
			 * Note we only unlock the manager lock if we actually
			 * have a task to do.  We must reacquire the manager 
			 * lock before exiting the 'if (task != NULL)' block.
			 */
			DEQUEUE(manager->ready_tasks, task, ready_link);
			UNLOCK(&manager->lock);

			LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
761
			INSIST(task->state == task_state_ready);
762 763 764 765 766 767
			task->state = task_state_running;
			XTRACE("running");
			do {
				if (!EMPTY(task->events)) {
					event = HEAD(task->events);
					DEQUEUE(task->events, event, link);
Bob Halley's avatar
base  
Bob Halley committed
768

769 770 771 772 773 774 775 776 777 778
					/*
					 * Execute the event action.
					 */
					XTRACE("execute action");
					if (event->action != NULL) {
						UNLOCK(&task->lock);
						(event->action)(task, event);
						LOCK(&task->lock);
					}
					dispatch_count++;
779
				}
780

Bob Halley's avatar
Bob Halley committed
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809
				if (task->references == 0 &&
				    EMPTY(task->events) &&
				    !TASK_SHUTTINGDOWN(task)) {
					isc_boolean_t was_idle;
					
					/*
					 * There are no references and no
					 * pending events for this task,
					 * which means it will not become
					 * runnable again via an external
					 * action (such as sending an event
					 * or detaching).
					 *
					 * We initiate shutdown to prevent
					 * it from becoming a zombie.
					 *
					 * We do this here instead of in
					 * the "if EMPTY(task->events)" block
					 * below because:
					 *
					 *	If we post no shutdown events,
					 *	we want the task to finish.
					 *
					 *	If we did post shutdown events,
					 *	will still want the task's
					 *	quantum to be applied.
					 */
					was_idle = task_shutdown(task);
					INSIST(!was_idle);
810 811
				}

812
				if (EMPTY(task->events)) {
Bob Halley's avatar
Bob Halley committed
813
					/*
814
					 * Nothing else to do for this task
Bob Halley's avatar
Bob Halley committed
815
					 * right now.
Bob Halley's avatar
Bob Halley committed
816
					 */
Bob Halley's avatar
Bob Halley committed
817
					XTRACE("empty");
Bob Halley's avatar
Bob Halley committed
818 819 820 821 822
					if (task->references == 0 &&
					    TASK_SHUTTINGDOWN(task)) {
						/*
						 * The task is done.
						 */
823
						XTRACE("done");
Bob Halley's avatar
Bob Halley committed
824
						finished = ISC_TRUE;
825
						task->state = task_state_done;
826 827
					} else
						task->state = task_state_idle;
Bob Halley's avatar
Bob Halley committed
828
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
829 830 831 832 833 834 835 836 837 838 839
				} else if (dispatch_count >= task->quantum) {
					/*
					 * Our quantum has expired, but
					 * there is more work to be done.
					 * We'll requeue it to the ready
					 * queue later.
					 *
					 * We don't check quantum until
					 * dispatching at least one event,
					 * so the minimum quantum is one.
					 */
Bob Halley's avatar
Bob Halley committed
840
					XTRACE("quantum");
Bob Halley's avatar
base  
Bob Halley committed
841
					task->state = task_state_ready;
Bob Halley's avatar
Bob Halley committed
842 843
					requeue = ISC_TRUE;
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
844
				}
845
			} while (!done);
Bob Halley's avatar
base  
Bob Halley committed
846 847
			UNLOCK(&task->lock);

848 849
			if (finished)
				task_finished(task);
Bob Halley's avatar
base  
Bob Halley committed
850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878

			LOCK(&manager->lock);
			if (requeue) {
				/*
				 * We know we're awake, so we don't have
				 * to wakeup any sleeping threads if the
				 * ready queue is empty before we requeue.
				 *
				 * A possible optimization if the queue is
				 * empty is to 'goto' the 'if (task != NULL)'
				 * block, avoiding the ENQUEUE of the task
				 * and the subsequent immediate DEQUEUE
				 * (since it is the only executable task).
				 * We don't do this because then we'd be
				 * skipping the exit_requested check.  The
				 * cost of ENQUEUE is low anyway, especially
				 * when you consider that we'd have to do
				 * an extra EMPTY check to see if we could
				 * do the optimization.  If the ready queue
				 * were usually nonempty, the 'optimization'
				 * might even hurt rather than help.
				 */
				ENQUEUE(manager->ready_tasks, task,
					ready_link);
			}
		}
	}
	UNLOCK(&manager->lock);

879
	XTHREADTRACE("exit");
Bob Halley's avatar
base  
Bob Halley committed
880

Bob Halley's avatar
update  
Bob Halley committed
881
	return ((isc_threadresult_t)0);
Bob Halley's avatar
base  
Bob Halley committed
882 883 884
}

static void
Bob Halley's avatar
Bob Halley committed
885
manager_free(isc_taskmgr_t *manager) {
Bob Halley's avatar
Bob Halley committed
886 887
	(void)isc_condition_destroy(&manager->work_available);
	(void)isc_mutex_destroy(&manager->lock);
888 889
	isc_mem_put(manager->mctx, manager->threads,
		    manager->workers * sizeof (isc_thread_t));
Bob Halley's avatar
base  
Bob Halley committed
890
	manager->magic = 0;
Bob Halley's avatar
Bob Halley committed
891
	isc_mem_put(manager->mctx, manager, sizeof *manager);
Bob Halley's avatar
base  
Bob Halley committed
892 893
}

Bob Halley's avatar
Bob Halley committed
894
isc_result_t
Bob Halley's avatar
Bob Halley committed
895
isc_taskmgr_create(isc_mem_t *mctx, unsigned int workers, 
Bob Halley's avatar
Bob Halley committed
896
		   unsigned int default_quantum, isc_taskmgr_t **managerp)
Bob Halley's avatar
Bob Halley committed
897 898
{
	unsigned int i, started = 0;
Bob Halley's avatar
Bob Halley committed
899
	isc_taskmgr_t *manager;
900
	isc_thread_t *threads;
Bob Halley's avatar
Bob Halley committed
901

902 903 904 905
	/*
	 * Create a new task manager.
	 */

Bob Halley's avatar
Bob Halley committed
906
	REQUIRE(workers > 0);
Bob Halley's avatar
Bob Halley committed
907
	REQUIRE(managerp != NULL && *managerp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
908

Bob Halley's avatar
Bob Halley committed
909
	manager = isc_mem_get(mctx, sizeof *manager);
Bob Halley's avatar
base  
Bob Halley committed
910
	if (manager == NULL)
Bob Halley's avatar
Bob Halley committed
911
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
912 913
	manager->magic = TASK_MANAGER_MAGIC;
	manager->mctx = mctx;
914 915 916 917 918 919 920
	threads = isc_mem_get(mctx, workers * sizeof (isc_thread_t));
	if (threads == NULL) {
		isc_mem_put(mctx, manager, sizeof *manager);
		return (ISC_R_NOMEMORY);
	}
	manager->threads = threads;
	manager->workers = 0;
Bob Halley's avatar
Bob Halley committed
921
	if (isc_mutex_init(&manager->lock) != ISC_R_SUCCESS) {
922
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
923
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
924 925 926
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
927
	}
Bob Halley's avatar
base  
Bob Halley committed
928 929 930 931 932
	if (default_quantum == 0)
		default_quantum = DEFAULT_DEFAULT_QUANTUM;
	manager->default_quantum = default_quantum;
	INIT_LIST(manager->tasks);
	INIT_LIST(manager->ready_tasks);
Bob Halley's avatar
Bob Halley committed
933 934
	if (isc_condition_init(&manager->work_available) != ISC_R_SUCCESS) {
		(void)isc_mutex_destroy(&manager->lock);
935
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
936
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
937 938 939
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_condition_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
940
	}
Bob Halley's avatar
Bob Halley committed
941
	manager->exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
942 943 944 945 946 947 948
	manager->workers = 0;

	LOCK(&manager->lock);
	/*
	 * Start workers.
	 */
	for (i = 0; i < workers; i++) {
949 950
		if (isc_thread_create(run, manager,
				      &manager->threads[manager->workers]) == 
Bob Halley's avatar
Bob Halley committed
951
		    ISC_R_SUCCESS) {
Bob Halley's avatar
base  
Bob Halley committed
952 953 954 955 956 957 958 959
			manager->workers++;
			started++;
		}
	}
	UNLOCK(&manager->lock);

	if (started == 0) {
		manager_free(manager);
Bob Halley's avatar
Bob Halley committed
960
		return (ISC_R_NOTHREADS);
Bob Halley's avatar
base  
Bob Halley committed
961 962 963 964
	}		

	*managerp = manager;

Bob Halley's avatar
Bob Halley committed
965
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
966 967
}

Bob Halley's avatar
update  
Bob Halley committed
968
void
Bob Halley's avatar
Bob Halley committed
969 970 971
isc_taskmgr_destroy(isc_taskmgr_t **managerp) {
	isc_taskmgr_t *manager;
	isc_task_t *task;
972
	unsigned int i;
Bob Halley's avatar
base  
Bob Halley committed
973

974 975 976 977
	/*
	 * Destroy '*managerp'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
978 979 980 981
	REQUIRE(managerp != NULL);
	manager = *managerp;
	REQUIRE(VALID_MANAGER(manager));

982
	XTHREADTRACE("isc_taskmgr_destroy");
Bob Halley's avatar
base  
Bob Halley committed
983 984 985 986
	/*
	 * Only one non-worker thread may ever call this routine.
	 * If a worker thread wants to initiate shutdown of the
	 * task manager, it should ask some non-worker thread to call
Bob Halley's avatar
Bob Halley committed
987
	 * isc_taskmgr_destroy(), e.g. by signalling a condition variable
Bob Halley's avatar
base  
Bob Halley committed
988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005
	 * that the startup thread is sleeping on.
	 */

	/*
	 * Unlike elsewhere, we're going to hold this lock a long time.
	 * We need to do so, because otherwise the list of tasks could
	 * change while we were traversing it.
	 *
	 * This is also the only function where we will hold both the
	 * task manager lock and a task lock at the same time.
	 */

	LOCK(&manager->lock);

	/*
	 * Make sure we only get called once.
	 */
	INSIST(!manager->exiting);
Bob Halley's avatar
Bob Halley committed
1006
	manager->exiting = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
1007 1008

	/*
1009
	 * Post shutdown event(s) to every task (if they haven't already been
Bob Halley's avatar
update  
Bob Halley committed
1010
	 * posted).
Bob Halley's avatar
base  
Bob Halley committed
1011 1012 1013 1014 1015
	 */
	for (task = HEAD(manager->tasks);
	     task != NULL;
	     task = NEXT(task, link)) {
		LOCK(&task->lock);
1016 1017
		if (task_shutdown(task))
			ENQUEUE(manager->ready_tasks, task, ready_link);
Bob Halley's avatar
base  
Bob Halley committed
1018 1019 1020 1021 1022 1023 1024 1025 1026
		UNLOCK(&task->lock);
	}

	/*
	 * Wake up any sleeping workers.  This ensures we get work done if
	 * there's work left to do, and if there are already no tasks left
	 * it will cause the workers to see manager->exiting.
	 */
	BROADCAST(&manager->work_available);
1027
	UNLOCK(&manager->lock);
Bob Halley's avatar
base  
Bob Halley committed
1028 1029 1030 1031

	/*
	 * Wait for all the worker threads to exit.
	 */
1032 1033
	for (i = 0; i < manager->workers; i++)
		(void)isc_thread_join(manager->threads[i], NULL);
Bob Halley's avatar
base  
Bob Halley committed
1034 1035 1036 1037 1038

	manager_free(manager);

	*managerp = NULL;
}