task.c 24.5 KB
Newer Older
Bob Halley's avatar
Bob Halley committed
1
/*
Bob Halley's avatar
Bob Halley committed
2
 * Copyright (C) 1998, 1999, 2000  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>

29 30
#include <string.h>

Bob Halley's avatar
base  
Bob Halley committed
31
#include <isc/assertions.h>
32
#include <isc/boolean.h>
Bob Halley's avatar
Bob Halley committed
33
#include <isc/thread.h>
34 35
#include <isc/mutex.h>
#include <isc/condition.h>
36
#include <isc/error.h>
37
#include <isc/event.h>
Bob Halley's avatar
Bob Halley committed
38
#include <isc/task.h>
Michael Graff's avatar
Michael Graff committed
39
#include <isc/util.h>
Bob Halley's avatar
base  
Bob Halley committed
40

41 42
#define ISC_TASK_NAMES 1

Bob Halley's avatar
Bob Halley committed
43
#ifdef ISC_TASK_TRACE
44 45 46 47 48 49
#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
50 51
#else
#define XTRACE(m)
52
#define XTTRACE(t, m)
53
#define XTHREADTRACE(m)
Bob Halley's avatar
Bob Halley committed
54
#endif
Bob Halley's avatar
base  
Bob Halley committed
55

Bob Halley's avatar
Bob Halley committed
56
/***
Bob Halley's avatar
Bob Halley committed
57
 *** Types.
Bob Halley's avatar
Bob Halley committed
58 59
 ***/

Bob Halley's avatar
Bob Halley committed
60 61
typedef enum {
	task_state_idle, task_state_ready, task_state_running,
62
	task_state_done
Bob Halley's avatar
Bob Halley committed
63 64 65 66 67 68
} 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
69
struct isc_task {
Bob Halley's avatar
Bob Halley committed
70 71
	/* Not locked. */
	unsigned int			magic;
Bob Halley's avatar
Bob Halley committed
72
	isc_taskmgr_t *			manager;
Bob Halley's avatar
Bob Halley committed
73
	isc_mutex_t			lock;
Bob Halley's avatar
Bob Halley committed
74 75 76
	/* Locked by task lock. */
	task_state_t			state;
	unsigned int			references;
Bob Halley's avatar
Bob Halley committed
77
	isc_eventlist_t			events;
78
	isc_eventlist_t			on_shutdown;
Bob Halley's avatar
Bob Halley committed
79
	unsigned int			quantum;
80
	unsigned int			flags;
81 82 83 84
#ifdef ISC_TASK_NAMES
	char				name[16];
	void *				tag;
#endif
Bob Halley's avatar
Bob Halley committed
85
	/* Locked by task manager lock. */
Bob Halley's avatar
Bob Halley committed
86 87
	LINK(isc_task_t)		link;
	LINK(isc_task_t)		ready_link;
Bob Halley's avatar
Bob Halley committed
88 89
};

Bob Halley's avatar
Bob Halley committed
90
#define TASK_F_SHUTTINGDOWN		0x01
91

92 93
#define TASK_SHUTTINGDOWN(t)		(((t)->flags & TASK_F_SHUTTINGDOWN) \
					 != 0)
94

Bob Halley's avatar
Bob Halley committed
95 96 97 98
#define TASK_MANAGER_MAGIC		0x54534B4DU	/* TSKM. */
#define VALID_MANAGER(m)		((m) != NULL && \
					 (m)->magic == TASK_MANAGER_MAGIC)

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

Bob Halley's avatar
Bob Halley committed
114 115
#define DEFAULT_DEFAULT_QUANTUM		5
#define FINISHED(m)			((m)->exiting && EMPTY((m)->tasks))
Bob Halley's avatar
Bob Halley committed
116

Bob Halley's avatar
base  
Bob Halley committed
117 118 119 120 121
/***
 *** Tasks.
 ***/

static void
122
task_finished(isc_task_t *task) {
Bob Halley's avatar
Bob Halley committed
123
	isc_taskmgr_t *manager = task->manager;
Bob Halley's avatar
base  
Bob Halley committed
124 125

	REQUIRE(EMPTY(task->events));
126
	REQUIRE(EMPTY(task->on_shutdown));
127 128 129 130
	REQUIRE(task->references == 0);
	REQUIRE(task->state == task_state_done);

	XTRACE("task_finished");
Bob Halley's avatar
base  
Bob Halley committed
131 132 133 134 135 136 137 138 139 140 141 142 143

	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);
144

Bob Halley's avatar
Bob Halley committed
145
	(void)isc_mutex_destroy(&task->lock);
Bob Halley's avatar
base  
Bob Halley committed
146
	task->magic = 0;
147
	isc_mem_put(manager->mctx, task, sizeof *task);
Bob Halley's avatar
base  
Bob Halley committed
148 149
}

Bob Halley's avatar
Bob Halley committed
150
isc_result_t
151
isc_task_create(isc_taskmgr_t *manager, unsigned int quantum,
152
		isc_task_t **taskp)
Bob Halley's avatar
Bob Halley committed
153
{
Bob Halley's avatar
Bob Halley committed
154
	isc_task_t *task;
155
	isc_boolean_t exiting;
Bob Halley's avatar
base  
Bob Halley committed
156 157 158 159

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

160
	task = isc_mem_get(manager->mctx, sizeof *task);
Bob Halley's avatar
base  
Bob Halley committed
161
	if (task == NULL)
Bob Halley's avatar
Bob Halley committed
162
		return (ISC_R_NOMEMORY);
163
	XTRACE("create");
Bob Halley's avatar
base  
Bob Halley committed
164
	task->manager = manager;
Bob Halley's avatar
Bob Halley committed
165
	if (isc_mutex_init(&task->lock) != ISC_R_SUCCESS) {
166
		isc_mem_put(manager->mctx, task, sizeof *task);
Bob Halley's avatar
Bob Halley committed
167 168 169
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
170
	}
Bob Halley's avatar
base  
Bob Halley committed
171 172 173
	task->state = task_state_idle;
	task->references = 1;
	INIT_LIST(task->events);
174
	INIT_LIST(task->on_shutdown);
Bob Halley's avatar
base  
Bob Halley committed
175
	task->quantum = quantum;
Bob Halley's avatar
Bob Halley committed
176
	task->flags = 0;
177
#ifdef ISC_TASK_NAMES
Mark Andrews's avatar
Mark Andrews committed
178
	memset(task->name, 0, sizeof task->name);
179 180
	task->tag = NULL;
#endif
Bob Halley's avatar
base  
Bob Halley committed
181 182 183
	INIT_LINK(task, link);
	INIT_LINK(task, ready_link);

184
	exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
185
	LOCK(&manager->lock);
186 187 188 189 190 191
	if (!manager->exiting) {
		if (task->quantum == 0)
			task->quantum = manager->default_quantum;
		APPEND(manager->tasks, task, link);
	} else
		exiting = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
192 193
	UNLOCK(&manager->lock);

194 195
	if (exiting) {
		isc_mutex_destroy(&task->lock);
196
		isc_mem_put(manager->mctx, task, sizeof *task);
197 198 199
		return (ISC_R_SHUTTINGDOWN);
	}

200
	task->magic = TASK_MAGIC;
Bob Halley's avatar
base  
Bob Halley committed
201 202
	*taskp = task;

Bob Halley's avatar
Bob Halley committed
203
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
204 205
}

Bob Halley's avatar
update  
Bob Halley committed
206
void
207
isc_task_attach(isc_task_t *source, isc_task_t **targetp) {
Bob Halley's avatar
base  
Bob Halley committed
208

209 210 211
	/*
	 * Attach *targetp to source.
	 */
Bob Halley's avatar
base  
Bob Halley committed
212

213 214
	REQUIRE(VALID_TASK(source));
	REQUIRE(targetp != NULL && *targetp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
215

216 217
	XTTRACE(source, "attach");

218 219 220 221 222
	LOCK(&source->lock);
	source->references++;
	UNLOCK(&source->lock);

	*targetp = source;
Bob Halley's avatar
base  
Bob Halley committed
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
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) {
252 253 254
			prev = PREV(event, ev_link);
			DEQUEUE(task->on_shutdown, event, ev_link);
			ENQUEUE(task->events, event, ev_link);
255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
		}
	}

	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
278
static inline isc_boolean_t
279 280 281 282 283 284 285 286 287 288 289
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
290 291 292 293 294 295 296 297 298 299 300 301
	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);
302 303
	}

Bob Halley's avatar
Bob Halley committed
304
	return (ISC_FALSE);
305 306
}

Bob Halley's avatar
Bob Halley committed
307
void
Bob Halley's avatar
Bob Halley committed
308 309
isc_task_detach(isc_task_t **taskp) {
	isc_task_t *task;
Bob Halley's avatar
Bob Halley committed
310
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
311

312 313 314 315
	/*
	 * Detach *taskp from its task.
	 */

Bob Halley's avatar
base  
Bob Halley committed
316 317 318 319
	REQUIRE(taskp != NULL);
	task = *taskp;
	REQUIRE(VALID_TASK(task));

320 321
	XTRACE("isc_task_detach");

Bob Halley's avatar
base  
Bob Halley committed
322
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
323
	was_idle = task_detach(task);
Bob Halley's avatar
base  
Bob Halley committed
324 325
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
326
	if (was_idle)
327
		task_ready(task);
Bob Halley's avatar
base  
Bob Halley committed
328 329 330 331

	*taskp = NULL;
}

Bob Halley's avatar
Bob Halley committed
332 333 334
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
335
	isc_event_t *event;
336
	
337
	/*
338
	 * Caller must be holding the task lock.
339 340
	 */

Bob Halley's avatar
update  
Bob Halley committed
341 342
	REQUIRE(eventp != NULL);
	event = *eventp;
Bob Halley's avatar
base  
Bob Halley committed
343
	REQUIRE(event != NULL);
344 345
	REQUIRE(event->ev_sender != NULL);
	REQUIRE(event->ev_type > 0);
Bob Halley's avatar
Bob Halley committed
346
	REQUIRE(task->state != task_state_done);
Bob Halley's avatar
base  
Bob Halley committed
347

348 349
	XTRACE("task_send");

Bob Halley's avatar
Bob Halley committed
350 351 352 353
	if (task->state == task_state_idle) {
		was_idle = ISC_TRUE;
		INSIST(EMPTY(task->events));
		task->state = task_state_ready;
354
	}
Bob Halley's avatar
Bob Halley committed
355 356
	INSIST(task->state == task_state_ready ||
	       task->state == task_state_running);
357
	ENQUEUE(task->events, event, ev_link);
Bob Halley's avatar
Bob Halley committed
358
	*eventp = NULL;
359

Bob Halley's avatar
Bob Halley committed
360 361
	return (was_idle);
}	
362

Bob Halley's avatar
Bob Halley committed
363
void
364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
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
381
	was_idle = task_send(task, eventp);
Bob Halley's avatar
base  
Bob Halley committed
382 383 384 385 386 387
	UNLOCK(&task->lock);

	if (was_idle) {
		/*
		 * We need to add this task to the ready queue.
		 *
388 389 390
		 * 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
391 392
		 *
		 * We've changed the state to ready, so no one else will
393 394 395
		 * 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,
396
		 * removed, or a shutdown is started in the interval
397 398
		 * 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
399
		 */
400
		task_ready(task);
Bob Halley's avatar
base  
Bob Halley committed
401
	}
402 403
}

Bob Halley's avatar
Bob Halley committed
404
void
405
isc_task_sendanddetach(isc_task_t **taskp, isc_event_t **eventp) {
Bob Halley's avatar
Bob Halley committed
406
	isc_boolean_t idle1, idle2;
407 408 409 410 411 412 413 414 415 416 417 418
	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
419

420
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
421 422
	idle1 = task_send(task, eventp);
	idle2 = task_detach(task);
423 424
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
425 426 427 428 429 430
	/*
	 * 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));
431

Bob Halley's avatar
Bob Halley committed
432 433
	if (idle1 || idle2)
		task_ready(task);
434 435

	*taskp = NULL;
Bob Halley's avatar
base  
Bob Halley committed
436 437
}

438
#define PURGE_OK(event)	(((event)->ev_attributes & ISC_EVENTATTR_NOPURGE) == 0)
439 440 441 442 443

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)
444
{
Bob Halley's avatar
Bob Halley committed
445
	isc_event_t *event, *next_event;
446
	unsigned int count = 0;
447

Bob Halley's avatar
Bob Halley committed
448
	REQUIRE(VALID_TASK(task));
449
	REQUIRE(last >= first);
Bob Halley's avatar
Bob Halley committed
450

451
	XTRACE("dequeue_events");
Bob Halley's avatar
Bob Halley committed
452

Bob Halley's avatar
Bob Halley committed
453
	/*
454 455 456
	 * 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.
457
	 *
458
	 * sender == NULL means "any sender", and tag == NULL means "any tag".
Bob Halley's avatar
Bob Halley committed
459 460 461
	 */

	LOCK(&task->lock);
462 463

	for (event = HEAD(task->events); event != NULL; event = next_event) {
464 465 466 467
		next_event = NEXT(event, ev_link);
		if (event->ev_type >= first && event->ev_type <= last &&
		    (sender == NULL || event->ev_sender == sender) &&
		    (tag == NULL || event->ev_tag == tag) &&
468
		    (!purging || PURGE_OK(event))) {
469 470
			DEQUEUE(task->events, event, ev_link);
			ENQUEUE(*events, event, ev_link);
471
			count++;
Bob Halley's avatar
Bob Halley committed
472 473
		}
	}
474

Bob Halley's avatar
Bob Halley committed
475 476
	UNLOCK(&task->lock);

477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499
	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) {
500
		next_event = NEXT(event, ev_link);
Bob Halley's avatar
Bob Halley committed
501
		isc_event_free(&event);
Bob Halley's avatar
Bob Halley committed
502
	}
503

504 505 506 507 508
	/*
	 * Note that purging never changes the state of the task.
	 */

	return (count);
Bob Halley's avatar
Bob Halley committed
509 510
}

511
unsigned int
Bob Halley's avatar
Bob Halley committed
512
isc_task_purge(isc_task_t *task, void *sender, isc_eventtype_t type,
513
	       void *tag)
Bob Halley's avatar
Bob Halley committed
514
{
515 516 517 518
	/*
	 * Purge events from a task's event queue.
	 */

519 520
	XTRACE("isc_task_purge");

Bob Halley's avatar
Bob Halley committed
521
	return (isc_task_purgerange(task, sender, type, type, tag));
522 523
}

Bob Halley's avatar
Bob Halley committed
524 525 526 527 528 529
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.
530 531
	 *
	 * XXXRTH:  WARNING:  This method may be removed before beta.
Bob Halley's avatar
Bob Halley committed
532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
	 */

	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) {
550
		next_event = NEXT(curr_event, ev_link);
551
		if (curr_event == event && PURGE_OK(event)) {
552
			DEQUEUE(task->events, curr_event, ev_link);
Bob Halley's avatar
Bob Halley committed
553 554 555 556 557 558 559 560 561 562 563 564 565
			break;
		}
	}
	UNLOCK(&task->lock);

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

	isc_event_free(&curr_event);

	return (ISC_TRUE);
}

566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594
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));
}

595 596 597 598 599 600
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;

601 602 603 604 605
	/*
	 * Send a shutdown event with action 'action' and argument 'arg' when
	 * 'task' is shutdown.
	 */

606
	REQUIRE(VALID_TASK(task));
607
	REQUIRE(action != NULL);
608

609
	event = isc_event_allocate(task->manager->mctx,
610 611 612 613 614
				   NULL,
				   ISC_TASKEVENT_SHUTDOWN,
				   action,
				   arg,
				   sizeof *event);
615 616 617 618
	if (event == NULL)
		return (ISC_R_NOMEMORY);

	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
619
	if (TASK_SHUTTINGDOWN(task)) {
620
		disallowed = ISC_TRUE;
621
		result = ISC_R_SHUTTINGDOWN;
622
	} else
623
		ENQUEUE(task->on_shutdown, event, ev_link);
624 625 626
	UNLOCK(&task->lock);

	if (disallowed)
627
		isc_mem_put(task->manager->mctx, event, sizeof *event);
628 629 630 631

	return (result);
}

Bob Halley's avatar
Bob Halley committed
632
void
Bob Halley's avatar
Bob Halley committed
633
isc_task_shutdown(isc_task_t *task) {
634
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
635

636 637 638 639
	/*
	 * Shutdown 'task'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
640 641 642
	REQUIRE(VALID_TASK(task));

	LOCK(&task->lock);
643
	was_idle = task_shutdown(task);
Bob Halley's avatar
base  
Bob Halley committed
644 645
	UNLOCK(&task->lock);

646 647
	if (was_idle)
		task_ready(task);
Bob Halley's avatar
Bob Halley committed
648
}
Bob Halley's avatar
base  
Bob Halley committed
649

Bob Halley's avatar
Bob Halley committed
650
void
Bob Halley's avatar
Bob Halley committed
651
isc_task_destroy(isc_task_t **taskp) {
Bob Halley's avatar
Bob Halley committed
652

653 654 655 656
	/*
	 * Destroy '*taskp'.
	 */

Bob Halley's avatar
Bob Halley committed
657 658
	REQUIRE(taskp != NULL);

Bob Halley's avatar
Bob Halley committed
659 660
	isc_task_shutdown(*taskp);
	isc_task_detach(taskp);
Bob Halley's avatar
base  
Bob Halley committed
661 662
}

663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681
void
isc_task_setname(isc_task_t *task, char *name, void *tag) {

	/*
	 * Name 'task'.
	 */

	REQUIRE(VALID_TASK(task));

#ifdef ISC_TASK_NAMES
	LOCK(&task->lock);
	memset(task->name, 0, sizeof(task->name));
	strncpy(task->name, name, sizeof(task->name) - 1);
	task->tag = tag;
	UNLOCK(&task->lock);
#else
	(void)name;
	(void)tag;
#endif
Bob Halley's avatar
base  
Bob Halley committed
682

683
}
Bob Halley's avatar
Bob Halley committed
684

Bob Halley's avatar
base  
Bob Halley committed
685 686 687 688
/***
 *** Task Manager.
 ***/

Bob Halley's avatar
update  
Bob Halley committed
689
static isc_threadresult_t
Bob Halley's avatar
Bob Halley committed
690 691 692
#ifdef _WIN32
WINAPI
#endif
Bob Halley's avatar
update  
Bob Halley committed
693
run(void *uap) {
Bob Halley's avatar
Bob Halley committed
694 695
	isc_taskmgr_t *manager = uap;
	isc_task_t *task;
Bob Halley's avatar
base  
Bob Halley committed
696

697
	XTHREADTRACE("start");
Bob Halley's avatar
base  
Bob Halley committed
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 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754

	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
755
		 * isc_task_send() above, it is safe for us to dequeue
Bob Halley's avatar
base  
Bob Halley committed
756 757 758 759 760
		 * 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)) {
761
			XTHREADTRACE("wait");
Bob Halley's avatar
base  
Bob Halley committed
762
			WAIT(&manager->work_available, &manager->lock);
763
			XTHREADTRACE("awake");
Bob Halley's avatar
base  
Bob Halley committed
764
		}
765
		XTHREADTRACE("working");
Bob Halley's avatar
base  
Bob Halley committed
766 767 768
		
		task = HEAD(manager->ready_tasks);
		if (task != NULL) {
Bob Halley's avatar
Bob Halley committed
769
			unsigned int dispatch_count = 0;
Bob Halley's avatar
Bob Halley committed
770 771
			isc_boolean_t done = ISC_FALSE;
			isc_boolean_t requeue = ISC_FALSE;
772
			isc_boolean_t finished = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
773
			isc_event_t *event;
Bob Halley's avatar
base  
Bob Halley committed
774 775 776 777 778 779 780 781 782 783 784 785

			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
786
			INSIST(task->state == task_state_ready);
787 788 789 790 791
			task->state = task_state_running;
			XTRACE("running");
			do {
				if (!EMPTY(task->events)) {
					event = HEAD(task->events);
792
					DEQUEUE(task->events, event, ev_link);
Bob Halley's avatar
base  
Bob Halley committed
793

794 795 796 797
					/*
					 * Execute the event action.
					 */
					XTRACE("execute action");
798
					if (event->ev_action != NULL) {
799
						UNLOCK(&task->lock);
800
						(event->ev_action)(task,event);
801 802 803
						LOCK(&task->lock);
					}
					dispatch_count++;
804
				}
805

Bob Halley's avatar
Bob Halley committed
806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834
				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);
835 836
				}

837
				if (EMPTY(task->events)) {
Bob Halley's avatar
Bob Halley committed
838
					/*
839
					 * Nothing else to do for this task
Bob Halley's avatar
Bob Halley committed
840
					 * right now.
Bob Halley's avatar
Bob Halley committed
841
					 */
Bob Halley's avatar
Bob Halley committed
842
					XTRACE("empty");
Bob Halley's avatar
Bob Halley committed
843 844 845 846 847
					if (task->references == 0 &&
					    TASK_SHUTTINGDOWN(task)) {
						/*
						 * The task is done.
						 */
848
						XTRACE("done");
Bob Halley's avatar
Bob Halley committed
849
						finished = ISC_TRUE;
850
						task->state = task_state_done;
851 852
					} else
						task->state = task_state_idle;
Bob Halley's avatar
Bob Halley committed
853
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
854 855 856 857 858 859 860 861 862 863 864
				} 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
865
					XTRACE("quantum");
Bob Halley's avatar
base  
Bob Halley committed
866
					task->state = task_state_ready;
Bob Halley's avatar
Bob Halley committed
867 868
					requeue = ISC_TRUE;
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
869
				}
870
			} while (!done);
Bob Halley's avatar
base  
Bob Halley committed
871 872
			UNLOCK(&task->lock);

873 874
			if (finished)
				task_finished(task);
Bob Halley's avatar
base  
Bob Halley committed
875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903

			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);

904
	XTHREADTRACE("exit");
Bob Halley's avatar
base  
Bob Halley committed
905

Bob Halley's avatar
update  
Bob Halley committed
906
	return ((isc_threadresult_t)0);
Bob Halley's avatar
base  
Bob Halley committed
907 908 909
}

static void
Bob Halley's avatar
Bob Halley committed
910
manager_free(isc_taskmgr_t *manager) {
911 912
	isc_mem_t *mctx;

Bob Halley's avatar
Bob Halley committed
913 914
	(void)isc_condition_destroy(&manager->work_available);
	(void)isc_mutex_destroy(&manager->lock);
915 916
	isc_mem_put(manager->mctx, manager->threads,
		    manager->workers * sizeof (isc_thread_t));
Bob Halley's avatar
base  
Bob Halley committed
917
	manager->magic = 0;
918 919 920
	mctx = manager->mctx;
	isc_mem_put(mctx, manager, sizeof *manager);
	isc_mem_detach(&mctx);
Bob Halley's avatar
base  
Bob Halley committed
921 922
}

Bob Halley's avatar
Bob Halley committed
923
isc_result_t
Bob Halley's avatar
Bob Halley committed
924
isc_taskmgr_create(isc_mem_t *mctx, unsigned int workers, 
Bob Halley's avatar
Bob Halley committed
925
		   unsigned int default_quantum, isc_taskmgr_t **managerp)
Bob Halley's avatar
Bob Halley committed
926 927
{
	unsigned int i, started = 0;
Bob Halley's avatar
Bob Halley committed
928
	isc_taskmgr_t *manager;
929
	isc_thread_t *threads;
Bob Halley's avatar
Bob Halley committed
930

931 932 933 934
	/*
	 * Create a new task manager.
	 */

Bob Halley's avatar
Bob Halley committed
935
	REQUIRE(workers > 0);
Bob Halley's avatar
Bob Halley committed
936
	REQUIRE(managerp != NULL && *managerp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
937

Bob Halley's avatar
Bob Halley committed
938
	manager = isc_mem_get(mctx, sizeof *manager);
Bob Halley's avatar
base  
Bob Halley committed
939
	if (manager == NULL)
Bob Halley's avatar
Bob Halley committed
940
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
941
	manager->magic = TASK_MANAGER_MAGIC;
942
	manager->mctx = NULL;
943 944 945 946 947 948 949
	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
950
	if (isc_mutex_init(&manager->lock) != ISC_R_SUCCESS) {
951
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
952
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
953 954 955
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
956
	}
Bob Halley's avatar
base  
Bob Halley committed
957 958 959 960 961
	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
962 963
	if (isc_condition_init(&manager->work_available) != ISC_R_SUCCESS) {
		(void)isc_mutex_destroy(&manager->lock);
964
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
965
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
966 967 968
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_condition_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
969
	}
Bob Halley's avatar
Bob Halley committed
970
	manager->exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
971 972
	manager->workers = 0;

973 974
	isc_mem_attach(mctx, &manager->mctx);

Bob Halley's avatar
base  
Bob Halley committed
975 976 977 978 979
	LOCK(&manager->lock);
	/*
	 * Start workers.
	 */
	for (i = 0; i < workers; i++) {
980 981
		if (isc_thread_create(run, manager,
				      &manager->threads[manager->workers]) == 
Bob Halley's avatar
Bob Halley committed
982
		    ISC_R_SUCCESS) {
Bob Halley's avatar
base  
Bob Halley committed
983 984 985 986 987 988 989 990
			manager->workers++;
			started++;
		}
	}
	UNLOCK(&manager->lock);

	if (started == 0) {
		manager_free(manager);
Bob Halley's avatar
Bob Halley committed
991
		return (ISC_R_NOTHREADS);
Bob Halley's avatar
base  
Bob Halley committed
992 993 994 995
	}		

	*managerp = manager;

Bob Halley's avatar
Bob Halley committed
996
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
997 998
}

Bob Halley's avatar
update  
Bob Halley committed
999
void
Bob Halley's avatar
Bob Halley committed
1000 1001 1002
isc_taskmgr_destroy(isc_taskmgr_t **managerp) {
	isc_taskmgr_t *manager;
	isc_task_t *task;
1003
	unsigned int i;
Bob Halley's avatar
base  
Bob Halley committed
1004

1005 1006 1007 1008
	/*
	 * Destroy '*managerp'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
1009 1010 1011 1012
	REQUIRE(managerp != NULL);
	manager = *managerp;
	REQUIRE(VALID_MANAGER(manager));

1013
	XTHREADTRACE("isc_taskmgr_destroy");
Bob Halley's avatar
base  
Bob Halley committed
1014 1015 1016 1017
	/*
	 * 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
1018
	 * isc_taskmgr_destroy(), e.g. by signalling a condition variable
Bob Halley's avatar
base  
Bob Halley committed
1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036
	 * 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
1037
	manager->exiting = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
1038 1039

	/*
1040
	 * Post shutdown event(s) to every task (if they haven't already been
Bob Halley's avatar
update  
Bob Halley committed
1041
	 * posted).
Bob Halley's avatar
base  
Bob Halley committed
1042 1043 1044 1045 1046
	 */
	for (task = HEAD(manager->tasks);
	     task != NULL;
	     task = NEXT(task, link)) {