/* Copyright (C) 2004 David Decotigny
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
USA.
*/
#ifndef _SOS_KWAITQ_H_
#define _SOS_KWAITQ_H_
#include <sos/errno.h>
#include <sos/thread.h>
#include <sos/time.h>
/**
* @kwaitq.h
*
* Low-level functions to manage queues of threads waiting for a
* resource. These functions are public, except
* sos_kwaitq_change_priority() that is a callback for the thread
* subsystem. However, for higher-level synchronization primitives
* such as mutex, semaphores, conditions, ... prefer to look at the
* corresponding libraries.
*/
/**
* Define this if you want to know the names of the kwaitq
*/
// #define SOS_KWQ_DEBUG
/* Forward declaration */
struct sos_kwaitq_entry;
/**
* The threads in the kwaitqs can be ordered in FIFO or in decreasing
* priority order.
*/
typedef enum { SOS_KWQ_ORDER_FIFO, SOS_KWQ_ORDER_PRIO } sos_kwaitq_ordering_t;
#include <sos/sched.h>
/**
* Definition of a waitqueue. In a kwaitq, the threads can be ordererd
* either in FIFO order (SOS_KWQ_ORDER_FIFO) or in decreasing priority
* order (SOS_KWQ_ORDER_PRIO ; with FIFO ordering for same-prio
* threads).
*
* A more efficient method to store the threads ordered by their
* priority would have been to use 1 list for each priority level. But
* we have to be careful to the size of a kwaitq structure here:
* potentially there are thousands of kwaitq in a running system
* (basically: 1 per opened file !). The algorithm we use to order the
* threads in the kwaitq in this case is highly under-optimal (naive
* linear insertion): as an exercise, one can implement a more
* efficient algorithm (think of a heap).
*/
struct sos_kwaitq
{
#ifdef SOS_KWQ_DEBUG
# define SOS_KWQ_DEBUG_MAX_NAMELEN 32
char name[SOS_KWQ_DEBUG_MAX_NAMELEN];
#endif
sos_kwaitq_ordering_t ordering;
struct sos_kwaitq_entry *waiting_list;
};
/**
* Definition of an entry for a thread waiting in the waitqueue
*/
struct sos_kwaitq_entry
{
/** The thread associted with this entry */
struct sos_thread *thread;
/** The kwaitqueue this entry belongs to */
struct sos_kwaitq *kwaitq;
/** TRUE when somebody woke up this entry */
sos_bool_t wakeup_triggered;
/** The status of wakeup for this entry. @see wakeup_status argument
of sos_kwaitq_wakeup() */
sos_ret_t wakeup_status;
/** Other entries in this kwaitqueue */
struct sos_kwaitq_entry *prev_entry_in_kwaitq, *next_entry_in_kwaitq;
/** Other entries for the thread */
struct sos_kwaitq_entry *prev_entry_for_thread, *next_entry_for_thread;
};
/**
* Initialize an empty waitqueue.
*
* @param name Used only if SOS_KWQ_DEBUG is defined (safe [deep
* copied])
*/
sos_ret_t sos_kwaitq_init(struct sos_kwaitq *kwq,
const char *name,
sos_kwaitq_ordering_t ordering);
/**
* Release a waitqueue, making sure that no thread is in it.
*
* @return -SOS_EBUSY in case a thread is still in the waitqueue.
*/
sos_ret_t sos_kwaitq_dispose(struct sos_kwaitq *kwq);
/**
* Return whether there are no threads in the waitq
*/
sos_bool_t sos_kwaitq_is_empty(const struct sos_kwaitq *kwq);
/**
* Initialize a waitqueue entry. Mainly consists in updating the
* "thread" field of the entry (set to current running thread), and
* initializing the remaining of the entry as to indicate it does not
* belong to any waitq.
*/
sos_ret_t sos_kwaitq_init_entry(struct sos_kwaitq_entry *kwq_entry);
/**
* Add an entry (previously initialized with sos_kwaitq_init_entry())
* in the given waitqueue.
*
* @note: No state change/context switch can occur here ! Among other
* things: the current executing thread is not preempted.
*/
sos_ret_t sos_kwaitq_add_entry(struct sos_kwaitq *kwq,
struct sos_kwaitq_entry *kwq_entry);
/**
* Remove the given kwaitq_entry from the kwaitq.
*
* @note: No state change/context switch can occur here ! Among other
* things: the thread associated with the entry is not necessarilly
* the same as the one currently running, and does not preempt the
* current running thread if they are different.
*/
sos_ret_t sos_kwaitq_remove_entry(struct sos_kwaitq *kwq,
struct sos_kwaitq_entry *kwq_entry);
/**
* Helper function to make the current running thread block in the
* given kwaitq, waiting to be woken up by somedy else or by the given
* timeout. It calls the sos_kwaitq_add_entry() and
* sos_kwaitq_remove_entry().
*
* @param timeout The desired timeout (can be NULL => wait for
* ever). It is updated by the function to reflect the remaining
* timeout in case the thread has been woken-up prior to its
* expiration.
*
* @return -SOS_EINTR when the thread is resumed while it has not be
* explicitely woken up by someone calling sos_kwaitq_wakeup() upon
* the same waitqueue... This can only happen 1/ if the timeout
* expired, or 2/ if the current thread is also in another kwaitq
* different to "kwq". Otherwise return the value set by
* sos_kwaitq_wakeup(). The timeout remaining is updated in timeout.
*
* @note This is a BLOCKING FUNCTION
*/
sos_ret_t sos_kwaitq_wait(struct sos_kwaitq *kwq,
struct sos_time *timeout);
/**
* Wake up as much as nb_thread threads (SOS_KWQ_WAKEUP_ALL to wake
* up all threads) in the kwaitq kwq, in FIFO or decreasing priority
* order (depends on the ordering scheme selected at kwaitq
* initialization time).
*
* @param wakeup_status The value returned by sos_kwaitq_wait() when
* the thread will effectively woken up due to this wakeup.
*/
sos_ret_t sos_kwaitq_wakeup(struct sos_kwaitq *kwq,
unsigned int nb_threads,
sos_ret_t wakeup_status);
#define SOS_KWQ_WAKEUP_ALL (~((unsigned int)0))
/**
* @note INTERNAL function (in particular: interrupts not disabled) !
*
* @note: The use of this function is RESERVED (to thread.c). Do not
* call it directly: use sos_thread_set_priority() for that !
*/
sos_ret_t sos_kwaitq_change_priority(struct sos_kwaitq *kwq,
struct sos_kwaitq_entry *kwq_entry,
sos_sched_priority_t priority);
#endif /* _SOS_KWAITQ_H_ */
