1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
/* 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_ */
|
