task.c 24 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>
Michael Graff's avatar
Michael Graff committed
37
#include <isc/util.h>
Bob Halley's avatar
base  
Bob Halley committed
38

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

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

Bob Halley's avatar
Bob Halley committed
56 57
typedef enum {
	task_state_idle, task_state_ready, task_state_running,
58
	task_state_done
Bob Halley's avatar
Bob Halley committed
59 60 61 62 63 64
} 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
65
struct isc_task {
Bob Halley's avatar
Bob Halley committed
66 67
	/* Not locked. */
	unsigned int			magic;
Bob Halley's avatar
Bob Halley committed
68
	isc_taskmgr_t *			manager;
Bob Halley's avatar
Bob Halley committed
69
	isc_mutex_t			lock;
Bob Halley's avatar
Bob Halley committed
70
	isc_mem_t *			mctx;
Bob Halley's avatar
Bob Halley committed
71 72 73
	/* Locked by task lock. */
	task_state_t			state;
	unsigned int			references;
Bob Halley's avatar
Bob Halley committed
74
	isc_eventlist_t			events;
75
	isc_eventlist_t			on_shutdown;
Bob Halley's avatar
Bob Halley committed
76
	unsigned int			quantum;
77
	unsigned int			flags;
Bob Halley's avatar
Bob Halley committed
78
	/* Locked by task manager lock. */
Bob Halley's avatar
Bob Halley committed
79 80
	LINK(isc_task_t)		link;
	LINK(isc_task_t)		ready_link;
Bob Halley's avatar
Bob Halley committed
81 82
};

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

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

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

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

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

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

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

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

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

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

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

Bob Halley's avatar
Bob Halley committed
143
isc_result_t
Bob Halley's avatar
Bob Halley committed
144
isc_task_create(isc_taskmgr_t *manager, isc_mem_t *mctx, unsigned int quantum,
145
		isc_task_t **taskp)
Bob Halley's avatar
Bob Halley committed
146
{
Bob Halley's avatar
Bob Halley committed
147
	isc_task_t *task;
148
	isc_boolean_t exiting;
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
	INIT_LINK(task, link);
	INIT_LINK(task, ready_link);

176
	exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
177
	LOCK(&manager->lock);
178 179 180 181 182 183
	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
184 185
	UNLOCK(&manager->lock);

186 187 188 189 190 191
	if (exiting) {
		isc_mutex_destroy(&task->lock);
		isc_mem_put(mctx, task, sizeof *task);
		return (ISC_R_SHUTTINGDOWN);
	}

192
	task->magic = TASK_MAGIC;
Bob Halley's avatar
base  
Bob Halley committed
193 194
	*taskp = task;

Bob Halley's avatar
Bob Halley committed
195
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
196 197
}

Bob Halley's avatar
update  
Bob Halley committed
198
void
199
isc_task_attach(isc_task_t *source, isc_task_t **targetp) {
Bob Halley's avatar
base  
Bob Halley committed
200

201 202 203
	/*
	 * Attach *targetp to source.
	 */
Bob Halley's avatar
base  
Bob Halley committed
204

205 206
	REQUIRE(VALID_TASK(source));
	REQUIRE(targetp != NULL && *targetp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
207

208 209
	XTTRACE(source, "attach");

210 211 212 213 214
	LOCK(&source->lock);
	source->references++;
	UNLOCK(&source->lock);

	*targetp = source;
Bob Halley's avatar
base  
Bob Halley committed
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 261 262 263 264 265 266 267 268 269
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
270
static inline isc_boolean_t
271 272 273 274 275 276 277 278 279 280 281
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
282 283 284 285 286 287 288 289 290 291 292 293
	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);
294 295
	}

Bob Halley's avatar
Bob Halley committed
296
	return (ISC_FALSE);
297 298
}

Bob Halley's avatar
Bob Halley committed
299
void
Bob Halley's avatar
Bob Halley committed
300 301
isc_task_detach(isc_task_t **taskp) {
	isc_task_t *task;
Bob Halley's avatar
Bob Halley committed
302
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
303

304 305 306 307
	/*
	 * Detach *taskp from its task.
	 */

Bob Halley's avatar
base  
Bob Halley committed
308 309 310 311
	REQUIRE(taskp != NULL);
	task = *taskp;
	REQUIRE(VALID_TASK(task));

312 313
	XTRACE("isc_task_detach");

Bob Halley's avatar
base  
Bob Halley committed
314
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
315
	was_idle = task_detach(task);
Bob Halley's avatar
base  
Bob Halley committed
316 317
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
318
	if (was_idle)
319
		task_ready(task);
Bob Halley's avatar
base  
Bob Halley committed
320 321 322 323

	*taskp = NULL;
}

Bob Halley's avatar
Bob Halley committed
324 325 326
isc_mem_t *
isc_task_mem(isc_task_t *task) {

327 328 329 330
	/*
	 * Get the task's memory context.
	 */

Bob Halley's avatar
Bob Halley committed
331 332 333 334 335
	REQUIRE(VALID_TASK(task));
	
	return (task->mctx);
}

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

Bob Halley's avatar
update  
Bob Halley committed
345 346
	REQUIRE(eventp != NULL);
	event = *eventp;
Bob Halley's avatar
base  
Bob Halley committed
347
	REQUIRE(event != NULL);
Bob Halley's avatar
Bob Halley committed
348 349
	REQUIRE(event->sender != NULL);
	REQUIRE(event->type > 0);
Bob Halley's avatar
Bob Halley committed
350
	REQUIRE(task->state != task_state_done);
Bob Halley's avatar
base  
Bob Halley committed
351

352 353
	XTRACE("task_send");

Bob Halley's avatar
Bob Halley committed
354 355 356 357
	if (task->state == task_state_idle) {
		was_idle = ISC_TRUE;
		INSIST(EMPTY(task->events));
		task->state = task_state_ready;
358
	}
Bob Halley's avatar
Bob Halley committed
359 360 361 362
	INSIST(task->state == task_state_ready ||
	       task->state == task_state_running);
	ENQUEUE(task->events, event, link);
	*eventp = NULL;
363

Bob Halley's avatar
Bob Halley committed
364 365
	return (was_idle);
}	
366

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

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

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

424
	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
425 426
	idle1 = task_send(task, eventp);
	idle2 = task_detach(task);
427 428
	UNLOCK(&task->lock);

Bob Halley's avatar
Bob Halley committed
429 430 431 432 433 434
	/*
	 * 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));
435

Bob Halley's avatar
Bob Halley committed
436 437
	if (idle1 || idle2)
		task_ready(task);
438 439

	*taskp = NULL;
Bob Halley's avatar
base  
Bob Halley committed
440 441
}

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

Bob Halley's avatar
Bob Halley committed
452
	REQUIRE(VALID_TASK(task));
453
	REQUIRE(last >= first);
Bob Halley's avatar
Bob Halley committed
454

455
	XTRACE("dequeue_events");
Bob Halley's avatar
Bob Halley committed
456

Bob Halley's avatar
Bob Halley committed
457
	/*
458 459 460
	 * 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.
461
	 *
462
	 * sender == NULL means "any sender", and tag == NULL means "any tag".
Bob Halley's avatar
Bob Halley committed
463 464 465
	 */

	LOCK(&task->lock);
466 467

	for (event = HEAD(task->events); event != NULL; event = next_event) {
Bob Halley's avatar
Bob Halley committed
468
		next_event = NEXT(event, link);
Bob Halley's avatar
Bob Halley committed
469 470
		if (event->type >= first && event->type <= last &&
		    (sender == NULL || event->sender == sender) &&
471 472
		    (tag == NULL || event->tag == tag) &&
		    (!purging || PURGE_OK(event))) {
Bob Halley's avatar
Bob Halley committed
473
			DEQUEUE(task->events, event, link);
474 475
			ENQUEUE(*events, event, link);
			count++;
Bob Halley's avatar
Bob Halley committed
476 477
		}
	}
478

Bob Halley's avatar
Bob Halley committed
479 480
	UNLOCK(&task->lock);

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

508 509 510 511 512
	/*
	 * Note that purging never changes the state of the task.
	 */

	return (count);
Bob Halley's avatar
Bob Halley committed
513 514
}

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

523 524
	XTRACE("isc_task_purge");

Bob Halley's avatar
Bob Halley committed
525
	return (isc_task_purgerange(task, sender, type, type, tag));
526 527
}

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

	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);
555
		if (curr_event == event && PURGE_OK(event)) {
Bob Halley's avatar
Bob Halley committed
556 557 558 559 560 561 562 563 564 565 566 567 568 569
			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);
}

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 595 596 597 598
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));
}

599 600 601 602 603 604
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;

605 606 607 608 609
	/*
	 * Send a shutdown event with action 'action' and argument 'arg' when
	 * 'task' is shutdown.
	 */

610
	REQUIRE(VALID_TASK(task));
611
	REQUIRE(action != NULL);
612

613 614 615 616 617 618
	event = isc_event_allocate(task->mctx,
				   NULL,
				   ISC_TASKEVENT_SHUTDOWN,
				   action,
				   arg,
				   sizeof *event);
619 620 621 622
	if (event == NULL)
		return (ISC_R_NOMEMORY);

	LOCK(&task->lock);
Bob Halley's avatar
Bob Halley committed
623
	if (TASK_SHUTTINGDOWN(task)) {
624
		disallowed = ISC_TRUE;
625
		result = ISC_R_SHUTTINGDOWN;
626 627 628 629 630
	} else
		ENQUEUE(task->on_shutdown, event, link);
	UNLOCK(&task->lock);

	if (disallowed)
Bob Halley's avatar
Bob Halley committed
631
		isc_mem_put(task->mctx, event, sizeof *event);
632 633 634 635

	return (result);
}

Bob Halley's avatar
Bob Halley committed
636
void
Bob Halley's avatar
Bob Halley committed
637
isc_task_shutdown(isc_task_t *task) {
638
	isc_boolean_t was_idle;
Bob Halley's avatar
base  
Bob Halley committed
639

640 641 642 643
	/*
	 * Shutdown 'task'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
644 645 646
	REQUIRE(VALID_TASK(task));

	LOCK(&task->lock);
647
	was_idle = task_shutdown(task);
Bob Halley's avatar
base  
Bob Halley committed
648 649
	UNLOCK(&task->lock);

650 651
	if (was_idle)
		task_ready(task);
Bob Halley's avatar
Bob Halley committed
652
}
Bob Halley's avatar
base  
Bob Halley committed
653

Bob Halley's avatar
Bob Halley committed
654
void
Bob Halley's avatar
Bob Halley committed
655
isc_task_destroy(isc_task_t **taskp) {
Bob Halley's avatar
Bob Halley committed
656

657 658 659 660
	/*
	 * Destroy '*taskp'.
	 */

Bob Halley's avatar
Bob Halley committed
661 662
	REQUIRE(taskp != NULL);

Bob Halley's avatar
Bob Halley committed
663 664
	isc_task_shutdown(*taskp);
	isc_task_detach(taskp);
Bob Halley's avatar
base  
Bob Halley committed
665 666 667
}


Bob Halley's avatar
Bob Halley committed
668

Bob Halley's avatar
base  
Bob Halley committed
669 670 671 672
/***
 *** Task Manager.
 ***/

Bob Halley's avatar
update  
Bob Halley committed
673
static isc_threadresult_t
Bob Halley's avatar
Bob Halley committed
674 675 676
#ifdef _WIN32
WINAPI
#endif
Bob Halley's avatar
update  
Bob Halley committed
677
run(void *uap) {
Bob Halley's avatar
Bob Halley committed
678 679
	isc_taskmgr_t *manager = uap;
	isc_task_t *task;
Bob Halley's avatar
base  
Bob Halley committed
680

681
	XTHREADTRACE("start");
Bob Halley's avatar
base  
Bob Halley committed
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 730 731 732 733 734 735 736 737 738

	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
739
		 * isc_task_send() above, it is safe for us to dequeue
Bob Halley's avatar
base  
Bob Halley committed
740 741 742 743 744
		 * 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)) {
745
			XTHREADTRACE("wait");
Bob Halley's avatar
base  
Bob Halley committed
746
			WAIT(&manager->work_available, &manager->lock);
747
			XTHREADTRACE("awake");
Bob Halley's avatar
base  
Bob Halley committed
748
		}
749
		XTHREADTRACE("working");
Bob Halley's avatar
base  
Bob Halley committed
750 751 752
		
		task = HEAD(manager->ready_tasks);
		if (task != NULL) {
Bob Halley's avatar
Bob Halley committed
753
			unsigned int dispatch_count = 0;
Bob Halley's avatar
Bob Halley committed
754 755
			isc_boolean_t done = ISC_FALSE;
			isc_boolean_t requeue = ISC_FALSE;
756
			isc_boolean_t finished = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
757
			isc_event_t *event;
Bob Halley's avatar
base  
Bob Halley committed
758 759 760 761 762 763 764 765 766 767 768 769

			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
770
			INSIST(task->state == task_state_ready);
771 772 773 774 775 776
			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
777

778 779 780 781 782 783 784 785 786 787
					/*
					 * Execute the event action.
					 */
					XTRACE("execute action");
					if (event->action != NULL) {
						UNLOCK(&task->lock);
						(event->action)(task, event);
						LOCK(&task->lock);
					}
					dispatch_count++;
788
				}
789

Bob Halley's avatar
Bob Halley committed
790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818
				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);
819 820
				}

821
				if (EMPTY(task->events)) {
Bob Halley's avatar
Bob Halley committed
822
					/*
823
					 * Nothing else to do for this task
Bob Halley's avatar
Bob Halley committed
824
					 * right now.
Bob Halley's avatar
Bob Halley committed
825
					 */
Bob Halley's avatar
Bob Halley committed
826
					XTRACE("empty");
Bob Halley's avatar
Bob Halley committed
827 828 829 830 831
					if (task->references == 0 &&
					    TASK_SHUTTINGDOWN(task)) {
						/*
						 * The task is done.
						 */
832
						XTRACE("done");
Bob Halley's avatar
Bob Halley committed
833
						finished = ISC_TRUE;
834
						task->state = task_state_done;
835 836
					} else
						task->state = task_state_idle;
Bob Halley's avatar
Bob Halley committed
837
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
838 839 840 841 842 843 844 845 846 847 848
				} 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
849
					XTRACE("quantum");
Bob Halley's avatar
base  
Bob Halley committed
850
					task->state = task_state_ready;
Bob Halley's avatar
Bob Halley committed
851 852
					requeue = ISC_TRUE;
					done = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
853
				}
854
			} while (!done);
Bob Halley's avatar
base  
Bob Halley committed
855 856
			UNLOCK(&task->lock);

857 858
			if (finished)
				task_finished(task);
Bob Halley's avatar
base  
Bob Halley committed
859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887

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

888
	XTHREADTRACE("exit");
Bob Halley's avatar
base  
Bob Halley committed
889

Bob Halley's avatar
update  
Bob Halley committed
890
	return ((isc_threadresult_t)0);
Bob Halley's avatar
base  
Bob Halley committed
891 892 893
}

static void
Bob Halley's avatar
Bob Halley committed
894
manager_free(isc_taskmgr_t *manager) {
Bob Halley's avatar
Bob Halley committed
895 896
	(void)isc_condition_destroy(&manager->work_available);
	(void)isc_mutex_destroy(&manager->lock);
897 898
	isc_mem_put(manager->mctx, manager->threads,
		    manager->workers * sizeof (isc_thread_t));
Bob Halley's avatar
base  
Bob Halley committed
899
	manager->magic = 0;
Bob Halley's avatar
Bob Halley committed
900
	isc_mem_put(manager->mctx, manager, sizeof *manager);
Bob Halley's avatar
base  
Bob Halley committed
901 902
}

Bob Halley's avatar
Bob Halley committed
903
isc_result_t
Bob Halley's avatar
Bob Halley committed
904
isc_taskmgr_create(isc_mem_t *mctx, unsigned int workers, 
Bob Halley's avatar
Bob Halley committed
905
		   unsigned int default_quantum, isc_taskmgr_t **managerp)
Bob Halley's avatar
Bob Halley committed
906 907
{
	unsigned int i, started = 0;
Bob Halley's avatar
Bob Halley committed
908
	isc_taskmgr_t *manager;
909
	isc_thread_t *threads;
Bob Halley's avatar
Bob Halley committed
910

911 912 913 914
	/*
	 * Create a new task manager.
	 */

Bob Halley's avatar
Bob Halley committed
915
	REQUIRE(workers > 0);
Bob Halley's avatar
Bob Halley committed
916
	REQUIRE(managerp != NULL && *managerp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
917

Bob Halley's avatar
Bob Halley committed
918
	manager = isc_mem_get(mctx, sizeof *manager);
Bob Halley's avatar
base  
Bob Halley committed
919
	if (manager == NULL)
Bob Halley's avatar
Bob Halley committed
920
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
921 922
	manager->magic = TASK_MANAGER_MAGIC;
	manager->mctx = mctx;
923 924 925 926 927 928 929
	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
930
	if (isc_mutex_init(&manager->lock) != ISC_R_SUCCESS) {
931
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
932
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
933 934 935
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
936
	}
Bob Halley's avatar
base  
Bob Halley committed
937 938 939 940 941
	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
942 943
	if (isc_condition_init(&manager->work_available) != ISC_R_SUCCESS) {
		(void)isc_mutex_destroy(&manager->lock);
944
		isc_mem_put(mctx, threads, workers * sizeof (isc_thread_t));
Bob Halley's avatar
Bob Halley committed
945
		isc_mem_put(mctx, manager, sizeof *manager);
Bob Halley's avatar
Bob Halley committed
946 947 948
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_condition_init() failed");
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
949
	}
Bob Halley's avatar
Bob Halley committed
950
	manager->exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
951 952 953 954 955 956 957
	manager->workers = 0;

	LOCK(&manager->lock);
	/*
	 * Start workers.
	 */
	for (i = 0; i < workers; i++) {
958 959
		if (isc_thread_create(run, manager,
				      &manager->threads[manager->workers]) == 
Bob Halley's avatar
Bob Halley committed
960
		    ISC_R_SUCCESS) {
Bob Halley's avatar
base  
Bob Halley committed
961 962 963 964 965 966 967 968
			manager->workers++;
			started++;
		}
	}
	UNLOCK(&manager->lock);

	if (started == 0) {
		manager_free(manager);
Bob Halley's avatar
Bob Halley committed
969
		return (ISC_R_NOTHREADS);
Bob Halley's avatar
base  
Bob Halley committed
970 971 972 973
	}		

	*managerp = manager;

Bob Halley's avatar
Bob Halley committed
974
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
975 976
}

Bob Halley's avatar
update  
Bob Halley committed
977
void
Bob Halley's avatar
Bob Halley committed
978 979 980
isc_taskmgr_destroy(isc_taskmgr_t **managerp) {
	isc_taskmgr_t *manager;
	isc_task_t *task;
981
	unsigned int i;
Bob Halley's avatar
base  
Bob Halley committed
982

983 984 985 986
	/*
	 * Destroy '*managerp'.
	 */

Bob Halley's avatar
base  
Bob Halley committed
987 988 989 990
	REQUIRE(managerp != NULL);
	manager = *managerp;
	REQUIRE(VALID_MANAGER(manager));

991
	XTHREADTRACE("isc_taskmgr_destroy");
Bob Halley's avatar
base  
Bob Halley committed
992 993 994 995
	/*
	 * 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
996
	 * isc_taskmgr_destroy(), e.g. by signalling a condition variable
Bob Halley's avatar
base  
Bob Halley committed
997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
	 * 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
1015
	manager->exiting = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
1016 1017

	/*
1018
	 * Post shutdown event(s) to every task (if they haven't already been
Bob Halley's avatar
update  
Bob Halley committed
1019
	 * posted).
Bob Halley's avatar
base  
Bob Halley committed
1020 1021 1022 1023 1024
	 */
	for (task = HEAD(manager->tasks);
	     task != NULL;
	     task = NEXT(task, link)) {
		LOCK(&task->lock);
1025 1026
		if (task_shutdown(task))
			ENQUEUE(manager->ready_tasks, task, ready_link);
Bob Halley's avatar
base  
Bob Halley committed
1027 1028 1029 1030 1031 1032 1033 1034 1035
		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);
1036
	UNLOCK(&manager->lock);
Bob Halley's avatar
base  
Bob Halley committed
1037 1038 1039 1040

	/*
	 * Wait for all the worker threads to exit.
	 */
1041 1042
	for (i = 0; i < manager->workers; i++)
		(void)isc_thread_join(manager->threads[i], NULL);
Bob Halley's avatar
base  
Bob Halley committed
1043 1044 1045 1046 1047

	manager_free(manager);

	*managerp = NULL;
}