xref: /illumos-gate/usr/src/lib/libslp/clib/slp_queue.c (revision 0daffde0)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
57c478bd9Sstevel@tonic-gate  * Common Development and Distribution License, Version 1.0 only
67c478bd9Sstevel@tonic-gate  * (the "License").  You may not use this file except in compliance
77c478bd9Sstevel@tonic-gate  * with the License.
87c478bd9Sstevel@tonic-gate  *
97c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
107c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
117c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
127c478bd9Sstevel@tonic-gate  * and limitations under the License.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
157c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
167c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
177c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
187c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
197c478bd9Sstevel@tonic-gate  *
207c478bd9Sstevel@tonic-gate  * CDDL HEADER END
217c478bd9Sstevel@tonic-gate  */
227c478bd9Sstevel@tonic-gate /*
237c478bd9Sstevel@tonic-gate  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
247c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
267c478bd9Sstevel@tonic-gate 
277c478bd9Sstevel@tonic-gate /*
287c478bd9Sstevel@tonic-gate  * A synchronized FIFO queue for inter-thread producer-consumer semantics.
297c478bd9Sstevel@tonic-gate  * This queue will handle multiple writers and readers simultaneously.
307c478bd9Sstevel@tonic-gate  *
317c478bd9Sstevel@tonic-gate  * The following operations are provided:
327c478bd9Sstevel@tonic-gate  * slp_new_queue:	create a new queue
337c478bd9Sstevel@tonic-gate  * slp_enqueue:		place a message at the end of the queue
347c478bd9Sstevel@tonic-gate  * slp_enqueue_at_head:	place a message the the start of the queue
357c478bd9Sstevel@tonic-gate  * slp_dequeue:		remove and return the next message on the queue
367c478bd9Sstevel@tonic-gate  *				(waits indefinately)
377c478bd9Sstevel@tonic-gate  * slp_dequeue_timed:	remove and return the next message on the queue
387c478bd9Sstevel@tonic-gate  *				(waits only for a specified time)
397c478bd9Sstevel@tonic-gate  * slp_flush_queue:	flushes and frees all messages on a queue
407c478bd9Sstevel@tonic-gate  * slp_destroy_queue:	frees an empty queue.
417c478bd9Sstevel@tonic-gate  */
427c478bd9Sstevel@tonic-gate 
437c478bd9Sstevel@tonic-gate #include <stdio.h>
447c478bd9Sstevel@tonic-gate #include <stdlib.h>
457c478bd9Sstevel@tonic-gate #include <thread.h>
467c478bd9Sstevel@tonic-gate #include <synch.h>
477c478bd9Sstevel@tonic-gate #include <syslog.h>
487c478bd9Sstevel@tonic-gate #include <slp.h>
497c478bd9Sstevel@tonic-gate #include <slp-internal.h>
507c478bd9Sstevel@tonic-gate 
517c478bd9Sstevel@tonic-gate /* Private implementation details */
527c478bd9Sstevel@tonic-gate struct queue_entry {
537c478bd9Sstevel@tonic-gate 	void *msg;
547c478bd9Sstevel@tonic-gate 	struct queue_entry *next;
557c478bd9Sstevel@tonic-gate };
567c478bd9Sstevel@tonic-gate typedef struct queue_entry slp_queue_entry_t;
577c478bd9Sstevel@tonic-gate 
587c478bd9Sstevel@tonic-gate struct queue {
597c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *head;
607c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *tail;
617c478bd9Sstevel@tonic-gate 	mutex_t *lock;
627c478bd9Sstevel@tonic-gate 	cond_t *wait;
637c478bd9Sstevel@tonic-gate 	int count;
647c478bd9Sstevel@tonic-gate };
657c478bd9Sstevel@tonic-gate 
667c478bd9Sstevel@tonic-gate /*
677c478bd9Sstevel@tonic-gate  * Creates, initializes, and returns a new queue.
687c478bd9Sstevel@tonic-gate  * If an initialization error occured, returns NULL and sets err to
697c478bd9Sstevel@tonic-gate  * the appropriate SLP error code.
707c478bd9Sstevel@tonic-gate  * queues can operate in one of two modes: timed-wait, and infinite
717c478bd9Sstevel@tonic-gate  * wait. The timeout parameter specifies which of these modes should
727c478bd9Sstevel@tonic-gate  * be enabled for the new queue.
737c478bd9Sstevel@tonic-gate  */
slp_new_queue(SLPError * err)747c478bd9Sstevel@tonic-gate slp_queue_t *slp_new_queue(SLPError *err) {
757c478bd9Sstevel@tonic-gate 	mutex_t *lock;
767c478bd9Sstevel@tonic-gate 	cond_t *wait;
777c478bd9Sstevel@tonic-gate 	struct queue *q;
787c478bd9Sstevel@tonic-gate 
797c478bd9Sstevel@tonic-gate 	*err = SLP_OK;
807c478bd9Sstevel@tonic-gate 
817c478bd9Sstevel@tonic-gate 	/* initialize new mutex and semaphore */
827c478bd9Sstevel@tonic-gate 	if ((lock = calloc(1, sizeof (*lock))) == NULL) {
837c478bd9Sstevel@tonic-gate 		*err = SLP_MEMORY_ALLOC_FAILED;
847c478bd9Sstevel@tonic-gate 		slp_err(LOG_CRIT, 0, "slp_new_queue", "out of memory");
857c478bd9Sstevel@tonic-gate 		return (NULL);
867c478bd9Sstevel@tonic-gate 	}
877c478bd9Sstevel@tonic-gate 
887c478bd9Sstevel@tonic-gate 	/* intialize condition vars */
897c478bd9Sstevel@tonic-gate 	if (!(wait = calloc(1, sizeof (*wait)))) {
907c478bd9Sstevel@tonic-gate 		*err = SLP_MEMORY_ALLOC_FAILED;
917c478bd9Sstevel@tonic-gate 		slp_err(LOG_CRIT, 0, "slp_new_queue", "out of memory");
927c478bd9Sstevel@tonic-gate 		return (NULL);
937c478bd9Sstevel@tonic-gate 	}
94*0daffde0SToomas Soome 	(void) cond_init(wait, USYNC_THREAD, NULL);
957c478bd9Sstevel@tonic-gate 
967c478bd9Sstevel@tonic-gate 	/* create the queue */
977c478bd9Sstevel@tonic-gate 	if ((q = malloc(sizeof (*q))) == NULL) {
987c478bd9Sstevel@tonic-gate 		*err = SLP_MEMORY_ALLOC_FAILED;
997c478bd9Sstevel@tonic-gate 		slp_err(LOG_CRIT, 0, "slp_new_queue", "out of memory");
1007c478bd9Sstevel@tonic-gate 		return (NULL);
1017c478bd9Sstevel@tonic-gate 	}
1027c478bd9Sstevel@tonic-gate 
1037c478bd9Sstevel@tonic-gate 	q->head = NULL;
1047c478bd9Sstevel@tonic-gate 	q->lock = lock;
1057c478bd9Sstevel@tonic-gate 	q->wait = wait;
1067c478bd9Sstevel@tonic-gate 	q->count = 0;
1077c478bd9Sstevel@tonic-gate 
1087c478bd9Sstevel@tonic-gate 	return (q);
1097c478bd9Sstevel@tonic-gate }
1107c478bd9Sstevel@tonic-gate 
1117c478bd9Sstevel@tonic-gate /*
1127c478bd9Sstevel@tonic-gate  * Adds msg to the tail of queue q.
1137c478bd9Sstevel@tonic-gate  * Returns an SLP error code: SLP_OK for no error, or SLP_MEMORY_ALLOC_FAILED
1147c478bd9Sstevel@tonic-gate  * if it couldn't allocate memory.
1157c478bd9Sstevel@tonic-gate  */
slp_enqueue(slp_queue_t * qa,void * msg)1167c478bd9Sstevel@tonic-gate SLPError slp_enqueue(slp_queue_t *qa, void *msg) {
1177c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *qe;
1187c478bd9Sstevel@tonic-gate 	struct queue *q = qa;
1197c478bd9Sstevel@tonic-gate 
1207c478bd9Sstevel@tonic-gate 	if ((qe = malloc(sizeof (*qe))) == NULL) {
1217c478bd9Sstevel@tonic-gate 		slp_err(LOG_CRIT, 0, "slp_enqueue", "out of memory");
1227c478bd9Sstevel@tonic-gate 		return (SLP_MEMORY_ALLOC_FAILED);
1237c478bd9Sstevel@tonic-gate 	}
1247c478bd9Sstevel@tonic-gate 
1257c478bd9Sstevel@tonic-gate 	(void) mutex_lock(q->lock);
1267c478bd9Sstevel@tonic-gate 	qe->msg = msg;
1277c478bd9Sstevel@tonic-gate 	qe->next = NULL;
1287c478bd9Sstevel@tonic-gate 	if (q->head != NULL) {	/* queue is not emptry */
1297c478bd9Sstevel@tonic-gate 		q->tail->next = qe;
1307c478bd9Sstevel@tonic-gate 		q->tail = qe;
1317c478bd9Sstevel@tonic-gate 	} else {		/* queue is empty */
1327c478bd9Sstevel@tonic-gate 		q->head = q->tail = qe;
1337c478bd9Sstevel@tonic-gate 	}
1347c478bd9Sstevel@tonic-gate 	q->count++;
1357c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(q->lock);
1367c478bd9Sstevel@tonic-gate 	(void) cond_signal(q->wait);
1377c478bd9Sstevel@tonic-gate 
1387c478bd9Sstevel@tonic-gate 	return (SLP_OK);
1397c478bd9Sstevel@tonic-gate }
1407c478bd9Sstevel@tonic-gate 
1417c478bd9Sstevel@tonic-gate /*
1427c478bd9Sstevel@tonic-gate  * Inserts a message at the head of the queue. This is useful for inserting
1437c478bd9Sstevel@tonic-gate  * things like cancel messages.
1447c478bd9Sstevel@tonic-gate  */
slp_enqueue_at_head(slp_queue_t * qa,void * msg)1457c478bd9Sstevel@tonic-gate SLPError slp_enqueue_at_head(slp_queue_t *qa, void *msg) {
1467c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *qe;
1477c478bd9Sstevel@tonic-gate 	struct queue *q = qa;
1487c478bd9Sstevel@tonic-gate 
1497c478bd9Sstevel@tonic-gate 	if ((qe = malloc(sizeof (*qe))) == NULL) {
1507c478bd9Sstevel@tonic-gate 		slp_err(LOG_CRIT, 0, "slp_enqueue", "out of memory");
1517c478bd9Sstevel@tonic-gate 		return (SLP_MEMORY_ALLOC_FAILED);
1527c478bd9Sstevel@tonic-gate 	}
1537c478bd9Sstevel@tonic-gate 
1547c478bd9Sstevel@tonic-gate 	(void) mutex_lock(q->lock);
1557c478bd9Sstevel@tonic-gate 	qe->msg = msg;
1567c478bd9Sstevel@tonic-gate 	qe->next = q->head;
1577c478bd9Sstevel@tonic-gate 	q->head = qe;
1587c478bd9Sstevel@tonic-gate 
1597c478bd9Sstevel@tonic-gate 	q->count++;
1607c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(q->lock);
1617c478bd9Sstevel@tonic-gate 	(void) cond_signal(q->wait);
1627c478bd9Sstevel@tonic-gate 
1637c478bd9Sstevel@tonic-gate 	return (SLP_OK);
1647c478bd9Sstevel@tonic-gate }
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate /*
1677c478bd9Sstevel@tonic-gate  * The core functionality for dequeue.
1687c478bd9Sstevel@tonic-gate  */
dequeue_nolock(struct queue * q)1697c478bd9Sstevel@tonic-gate static void *dequeue_nolock(struct queue *q) {
1707c478bd9Sstevel@tonic-gate 	void *msg;
1717c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *qe = q->head;
1727c478bd9Sstevel@tonic-gate 
1737c478bd9Sstevel@tonic-gate 	if (!qe)
1747c478bd9Sstevel@tonic-gate 		return (NULL);	/* shouldn't get here */
1757c478bd9Sstevel@tonic-gate 	msg = qe->msg;
1767c478bd9Sstevel@tonic-gate 	if (!qe->next)		/* last one in queue */
1777c478bd9Sstevel@tonic-gate 		q->head = q->tail = NULL;
1787c478bd9Sstevel@tonic-gate 	else
1797c478bd9Sstevel@tonic-gate 		q->head = qe->next;
1807c478bd9Sstevel@tonic-gate 	free(qe);
1817c478bd9Sstevel@tonic-gate 	q->count--;
1827c478bd9Sstevel@tonic-gate 	return (msg);
1837c478bd9Sstevel@tonic-gate }
1847c478bd9Sstevel@tonic-gate 
1857c478bd9Sstevel@tonic-gate /*
1867c478bd9Sstevel@tonic-gate  * Returns the first message waiting or arriving in the queue, or if no
1877c478bd9Sstevel@tonic-gate  * message is available after waiting the amount of time specified in
1887c478bd9Sstevel@tonic-gate  * 'to', returns NULL, and sets 'etimed' to true. If an error occured,
1897c478bd9Sstevel@tonic-gate  * returns NULL and sets 'etimed' to false.
1907c478bd9Sstevel@tonic-gate  */
slp_dequeue_timed(slp_queue_t * qa,timestruc_t * to,SLPBoolean * etimed)1917c478bd9Sstevel@tonic-gate void *slp_dequeue_timed(slp_queue_t *qa, timestruc_t *to, SLPBoolean *etimed) {
1927c478bd9Sstevel@tonic-gate 	int err;
1937c478bd9Sstevel@tonic-gate 	void *ans;
1947c478bd9Sstevel@tonic-gate 	struct queue *q = qa;
1957c478bd9Sstevel@tonic-gate 
1967c478bd9Sstevel@tonic-gate 	if (etimed)
1977c478bd9Sstevel@tonic-gate 		*etimed = SLP_FALSE;
1987c478bd9Sstevel@tonic-gate 
1997c478bd9Sstevel@tonic-gate 	(void) mutex_lock(q->lock);
2007c478bd9Sstevel@tonic-gate 	if (q->count > 0) {
2017c478bd9Sstevel@tonic-gate 		/* something's in the q, so no need to wait */
2027c478bd9Sstevel@tonic-gate 		goto msg_available;
2037c478bd9Sstevel@tonic-gate 	}
2047c478bd9Sstevel@tonic-gate 
2057c478bd9Sstevel@tonic-gate 	/* else wait */
2067c478bd9Sstevel@tonic-gate 	while (q->count == 0) {
2077c478bd9Sstevel@tonic-gate 		if (to) {
2087c478bd9Sstevel@tonic-gate 			err = cond_timedwait(q->wait, q->lock, to);
2097c478bd9Sstevel@tonic-gate 		} else {
2107c478bd9Sstevel@tonic-gate 			err = cond_wait(q->wait, q->lock);
2117c478bd9Sstevel@tonic-gate 		}
2127c478bd9Sstevel@tonic-gate 		if (err == ETIME) {
2137c478bd9Sstevel@tonic-gate 			(void) mutex_unlock(q->lock);
2147c478bd9Sstevel@tonic-gate 			*etimed = SLP_TRUE;
2157c478bd9Sstevel@tonic-gate 			return (NULL);
2167c478bd9Sstevel@tonic-gate 		}
2177c478bd9Sstevel@tonic-gate 	}
2187c478bd9Sstevel@tonic-gate 
2197c478bd9Sstevel@tonic-gate msg_available:
2207c478bd9Sstevel@tonic-gate 	ans = dequeue_nolock(q);
2217c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(q->lock);
2227c478bd9Sstevel@tonic-gate 	return (ans);
2237c478bd9Sstevel@tonic-gate }
2247c478bd9Sstevel@tonic-gate 
2257c478bd9Sstevel@tonic-gate /*
2267c478bd9Sstevel@tonic-gate  * Removes the first message from the queue and returns it.
2277c478bd9Sstevel@tonic-gate  * Returns NULL only on internal error.
2287c478bd9Sstevel@tonic-gate  */
slp_dequeue(slp_queue_t * qa)2297c478bd9Sstevel@tonic-gate void *slp_dequeue(slp_queue_t *qa) {
2307c478bd9Sstevel@tonic-gate 	return (slp_dequeue_timed(qa, NULL, NULL));
2317c478bd9Sstevel@tonic-gate }
2327c478bd9Sstevel@tonic-gate 
2337c478bd9Sstevel@tonic-gate /*
2347c478bd9Sstevel@tonic-gate  * Flushes the queue, using the caller-specified free function to
2357c478bd9Sstevel@tonic-gate  * free each message in the queue.
2367c478bd9Sstevel@tonic-gate  */
slp_flush_queue(slp_queue_t * qa,void (* free_f)(void *))2377c478bd9Sstevel@tonic-gate void slp_flush_queue(slp_queue_t *qa, void (*free_f)(void *)) {
2387c478bd9Sstevel@tonic-gate 	slp_queue_entry_t *p, *pn;
2397c478bd9Sstevel@tonic-gate 	struct queue *q = qa;
2407c478bd9Sstevel@tonic-gate 
2417c478bd9Sstevel@tonic-gate 	for (p = q->head; p; p = pn) {
2427c478bd9Sstevel@tonic-gate 		pn = p->next;
2437c478bd9Sstevel@tonic-gate 		free_f(p);
2447c478bd9Sstevel@tonic-gate 	}
2457c478bd9Sstevel@tonic-gate }
2467c478bd9Sstevel@tonic-gate 
2477c478bd9Sstevel@tonic-gate /*
2487c478bd9Sstevel@tonic-gate  * Frees a queue.
2497c478bd9Sstevel@tonic-gate  * The queue must be empty before it can be destroyed; slp_flush_queue
2507c478bd9Sstevel@tonic-gate  * can be used to empty a queue.
2517c478bd9Sstevel@tonic-gate  */
slp_destroy_queue(slp_queue_t * qa)2527c478bd9Sstevel@tonic-gate void slp_destroy_queue(slp_queue_t *qa) {
2537c478bd9Sstevel@tonic-gate 	struct queue *q = qa;
2547c478bd9Sstevel@tonic-gate 
2557c478bd9Sstevel@tonic-gate 	(void) mutex_destroy(q->lock);
2567c478bd9Sstevel@tonic-gate 	(void) cond_destroy(q->wait);
2577c478bd9Sstevel@tonic-gate 	free(q->lock);
2587c478bd9Sstevel@tonic-gate 	free(q->wait);
2597c478bd9Sstevel@tonic-gate 	free(q);
2607c478bd9Sstevel@tonic-gate }
261