task.c 24.6 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>
33
#include <isc/condition.h>
34
#include <isc/error.h>
35
#include <isc/event.h>
36 37
#include <isc/mem.h>
#include <isc/mutex.h>
Bob Halley's avatar
Bob Halley committed
38
#include <isc/task.h>
39
#include <isc/thread.h>
Michael Graff's avatar
Michael Graff committed
40
#include <isc/util.h>
Bob Halley's avatar
base  
Bob Halley committed
41

42 43
#define ISC_TASK_NAMES 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

185
	exiting = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
186
	LOCK(&manager->lock);
187 188 189 190 191 192
	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
193 194
	UNLOCK(&manager->lock);

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

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

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

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

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

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

217 218
	XTTRACE(source, "attach");

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

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

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

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

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

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

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

321 322
	XTRACE("isc_task_detach");

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

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

	*taskp = NULL;
}

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

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

349 350
	XTRACE("task_send");

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	LOCK(&task->lock);
463 464

	for (event = HEAD(task->events); event != NULL; event = next_event) {
465 466 467 468
		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) &&
469
		    (!purging || PURGE_OK(event))) {
470 471
			DEQUEUE(task->events, event, ev_link);
			ENQUEUE(*events, event, ev_link);
472
			count++;
Bob Halley's avatar
Bob Halley committed
473 474
		}
	}
475

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

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

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

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

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

520 521
	XTRACE("isc_task_purge");

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

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

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

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

	isc_event_free(&curr_event);

	return (ISC_TRUE);
}

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

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

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

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

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

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

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

	return (result);
}

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

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

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

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

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

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

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

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

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

664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682
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
683

684
}
Bob Halley's avatar
Bob Halley committed
685

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

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

698
	XTHREADTRACE("start");
Bob Halley's avatar
base  
Bob Halley committed
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 755

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

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

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

Bob Halley's avatar
Bob Halley committed
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 835
				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);
836 837
				}

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

874 875
			if (finished)
				task_finished(task);
Bob Halley's avatar
base  
Bob Halley committed
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 904

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

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

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

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

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

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

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

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

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

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

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

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

	*managerp = manager;

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

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

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

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

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

	/*
1041
	 * Post shutdown event(s) to every task (if they haven't already been
Bob Halley's avatar
update  
Bob Halley committed
1042
	 * posted).
Bob Halley's avatar
base  
Bob Halley committed
1043