1/*
2 * Copyright 2007-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2019, Haiku, Inc. All rights reserved.
4 * Distributed under the terms of the MIT License.
5 */
6
7#include <condition_variable.h>
8
9#include <new>
10#include <stdlib.h>
11#include <string.h>
12
13#include <debug.h>
14#include <kscheduler.h>
15#include <ksignal.h>
16#include <int.h>
17#include <listeners.h>
18#include <scheduling_analysis.h>
19#include <thread.h>
20#include <util/AutoLock.h>
21#include <util/atomic.h>
22
23
24#define STATUS_ADDED	1
25#define STATUS_WAITING	2
26
27
28static const int kConditionVariableHashSize = 512;
29
30
31struct ConditionVariableHashDefinition {
32	typedef const void* KeyType;
33	typedef	ConditionVariable ValueType;
34
35	size_t HashKey(const void* key) const
36		{ return (size_t)key; }
37	size_t Hash(ConditionVariable* variable) const
38		{ return (size_t)variable->fObject; }
39	bool Compare(const void* key, ConditionVariable* variable) const
40		{ return key == variable->fObject; }
41	ConditionVariable*& GetLink(ConditionVariable* variable) const
42		{ return variable->fNext; }
43};
44
45typedef BOpenHashTable<ConditionVariableHashDefinition> ConditionVariableHash;
46static ConditionVariableHash sConditionVariableHash;
47static rw_spinlock sConditionVariableHashLock;
48
49
50static int
51list_condition_variables(int argc, char** argv)
52{
53	ConditionVariable::ListAll();
54	return 0;
55}
56
57
58static int
59dump_condition_variable(int argc, char** argv)
60{
61	if (argc != 2) {
62		print_debugger_command_usage(argv[0]);
63		return 0;
64	}
65
66	addr_t address = parse_expression(argv[1]);
67	if (address == 0)
68		return 0;
69
70	ConditionVariable* variable = sConditionVariableHash.Lookup((void*)address);
71
72	if (variable == NULL) {
73		// It must be a direct pointer to a condition variable.
74		variable = (ConditionVariable*)address;
75	}
76
77	if (variable != NULL) {
78		variable->Dump();
79
80		set_debug_variable("_cvar", (addr_t)variable);
81		set_debug_variable("_object", (addr_t)variable->Object());
82
83	} else
84		kprintf("no condition variable at or with key %p\n", (void*)address);
85
86	return 0;
87}
88
89
90// #pragma mark - ConditionVariableEntry
91
92
93bool
94ConditionVariableEntry::Add(const void* object)
95{
96	ASSERT(object != NULL);
97
98	InterruptsLocker _;
99	ReadSpinLocker hashLocker(sConditionVariableHashLock);
100
101	ConditionVariable* variable = sConditionVariableHash.Lookup(object);
102
103	if (variable == NULL) {
104		fWaitStatus = B_ENTRY_NOT_FOUND;
105		return false;
106	}
107
108	SpinLocker variableLocker(variable->fLock);
109	hashLocker.Unlock();
110
111	AddToLockedVariable(variable);
112
113	return true;
114}
115
116
117inline void
118ConditionVariableEntry::AddToLockedVariable(ConditionVariable* variable)
119{
120	ASSERT(fVariable == NULL);
121
122	B_INITIALIZE_SPINLOCK(&fLock);
123	fThread = thread_get_current_thread();
124	fVariable = variable;
125	fWaitStatus = STATUS_ADDED;
126	fVariable->fEntries.Add(this);
127}
128
129
130status_t
131ConditionVariableEntry::Wait(uint32 flags, bigtime_t timeout)
132{
133#if KDEBUG
134	if (!are_interrupts_enabled()) {
135		panic("ConditionVariableEntry::Wait() called with interrupts "
136			"disabled, entry: %p, variable: %p", this, fVariable);
137		return B_ERROR;
138	}
139#endif
140
141	InterruptsLocker _;
142	SpinLocker entryLocker(fLock);
143
144	if (fVariable == NULL)
145		return fWaitStatus;
146
147	thread_prepare_to_block(fThread, flags,
148		THREAD_BLOCK_TYPE_CONDITION_VARIABLE, fVariable);
149
150	fWaitStatus = STATUS_WAITING;
151
152	entryLocker.Unlock();
153
154	status_t error;
155	if ((flags & (B_RELATIVE_TIMEOUT | B_ABSOLUTE_TIMEOUT)) != 0)
156		error = thread_block_with_timeout(flags, timeout);
157	else
158		error = thread_block();
159
160	entryLocker.Lock();
161
162	// Remove entry from variable, if not done yet.
163	if (fVariable != NULL) {
164		SpinLocker conditionLocker(fVariable->fLock);
165		if (fVariable->fEntries.Contains(this)) {
166			fVariable->fEntries.Remove(this);
167		} else {
168			entryLocker.Unlock();
169			// The variable's fEntries did not contain us, but we currently
170			// have the variable's lock acquired. This must mean we are in
171			// a race with the variable's Notify. It is possible we will be
172			// destroyed immediately upon returning here, so we need to
173			// spin until our fVariable member is unset by the Notify thread
174			// and then re-acquire our own lock to avoid a use-after-free.
175			while (atomic_pointer_get(&fVariable) != NULL) {}
176			entryLocker.Lock();
177		}
178		fVariable = NULL;
179	}
180
181	return error;
182}
183
184
185status_t
186ConditionVariableEntry::Wait(const void* object, uint32 flags,
187	bigtime_t timeout)
188{
189	if (Add(object))
190		return Wait(flags, timeout);
191	return B_ENTRY_NOT_FOUND;
192}
193
194
195// #pragma mark - ConditionVariable
196
197
198/*!	Initialization method for anonymous (unpublished) condition variables.
199*/
200void
201ConditionVariable::Init(const void* object, const char* objectType)
202{
203	fObject = object;
204	fObjectType = objectType;
205	new(&fEntries) EntryList;
206	B_INITIALIZE_SPINLOCK(&fLock);
207
208	T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType));
209	NotifyWaitObjectListeners(&WaitObjectListener::ConditionVariableInitialized,
210		this);
211}
212
213
214void
215ConditionVariable::Publish(const void* object, const char* objectType)
216{
217	ASSERT(object != NULL);
218
219	fObject = object;
220	fObjectType = objectType;
221	new(&fEntries) EntryList;
222	B_INITIALIZE_SPINLOCK(&fLock);
223
224	T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType));
225	NotifyWaitObjectListeners(&WaitObjectListener::ConditionVariableInitialized,
226		this);
227
228	InterruptsWriteSpinLocker _(sConditionVariableHashLock);
229
230	ASSERT_PRINT(sConditionVariableHash.Lookup(object) == NULL,
231		"condition variable: %p\n", sConditionVariableHash.Lookup(object));
232
233	sConditionVariableHash.InsertUnchecked(this);
234}
235
236
237void
238ConditionVariable::Unpublish()
239{
240	ASSERT(fObject != NULL);
241
242	InterruptsLocker _;
243	WriteSpinLocker hashLocker(sConditionVariableHashLock);
244	SpinLocker selfLocker(fLock);
245
246#if KDEBUG
247	ConditionVariable* variable = sConditionVariableHash.Lookup(fObject);
248	if (variable != this) {
249		panic("Condition variable %p not published, found: %p", this, variable);
250		return;
251	}
252#endif
253
254	sConditionVariableHash.RemoveUnchecked(this);
255	fObject = NULL;
256	fObjectType = NULL;
257
258	hashLocker.Unlock();
259
260	if (!fEntries.IsEmpty())
261		_NotifyLocked(true, B_ENTRY_NOT_FOUND);
262}
263
264
265void
266ConditionVariable::Add(ConditionVariableEntry* entry)
267{
268	InterruptsSpinLocker _(fLock);
269	entry->AddToLockedVariable(this);
270}
271
272
273status_t
274ConditionVariable::Wait(uint32 flags, bigtime_t timeout)
275{
276	ConditionVariableEntry entry;
277	Add(&entry);
278	return entry.Wait(flags, timeout);
279}
280
281
282/*static*/ void
283ConditionVariable::NotifyOne(const void* object, status_t result)
284{
285	InterruptsReadSpinLocker locker(sConditionVariableHashLock);
286	ConditionVariable* variable = sConditionVariableHash.Lookup(object);
287	locker.Unlock();
288	if (variable == NULL)
289		return;
290
291	variable->NotifyOne(result);
292}
293
294
295/*static*/ void
296ConditionVariable::NotifyAll(const void* object, status_t result)
297{
298	InterruptsReadSpinLocker locker(sConditionVariableHashLock);
299	ConditionVariable* variable = sConditionVariableHash.Lookup(object);
300	locker.Unlock();
301	if (variable == NULL)
302		return;
303
304	variable->NotifyAll(result);
305}
306
307
308void
309ConditionVariable::_Notify(bool all, status_t result)
310{
311	InterruptsSpinLocker _(fLock);
312
313	if (!fEntries.IsEmpty()) {
314		if (result > B_OK) {
315			panic("tried to notify with invalid result %" B_PRId32 "\n", result);
316			result = B_ERROR;
317		}
318
319		_NotifyLocked(all, result);
320	}
321}
322
323
324/*! Called with interrupts disabled and the condition variable's spinlock held.
325 */
326void
327ConditionVariable::_NotifyLocked(bool all, status_t result)
328{
329	// Dequeue and wake up the blocked threads.
330	// We *cannot* hold our own lock while acquiring the Entry's lock,
331	// as this leads to a (non-theoretical!) race between the Entry
332	// entering Wait() and acquiring its own lock, and then acquiring ours.
333	while (ConditionVariableEntry* entry = fEntries.RemoveHead()) {
334		release_spinlock(&fLock);
335		acquire_spinlock(&entry->fLock);
336
337		entry->fVariable = NULL;
338
339		if (entry->fWaitStatus <= 0) {
340			release_spinlock(&entry->fLock);
341			acquire_spinlock(&fLock);
342			continue;
343		}
344
345		if (entry->fWaitStatus == STATUS_WAITING) {
346			SpinLocker _(entry->fThread->scheduler_lock);
347			thread_unblock_locked(entry->fThread, result);
348		}
349
350		entry->fWaitStatus = result;
351
352		release_spinlock(&entry->fLock);
353		acquire_spinlock(&fLock);
354
355		if (!all)
356			break;
357	}
358}
359
360
361/*static*/ void
362ConditionVariable::ListAll()
363{
364	kprintf("  variable      object (type)                waiting threads\n");
365	kprintf("------------------------------------------------------------\n");
366	ConditionVariableHash::Iterator it(&sConditionVariableHash);
367	while (ConditionVariable* variable = it.Next()) {
368		// count waiting threads
369		int count = variable->fEntries.Count();
370
371		kprintf("%p  %p  %-20s %15d\n", variable, variable->fObject,
372			variable->fObjectType, count);
373	}
374}
375
376
377void
378ConditionVariable::Dump() const
379{
380	kprintf("condition variable %p\n", this);
381	kprintf("  object:  %p (%s)\n", fObject, fObjectType);
382	kprintf("  threads:");
383
384	for (EntryList::ConstIterator it = fEntries.GetIterator();
385		 ConditionVariableEntry* entry = it.Next();) {
386		kprintf(" %" B_PRId32, entry->fThread->id);
387	}
388	kprintf("\n");
389}
390
391
392// #pragma mark -
393
394
395void
396condition_variable_init()
397{
398	new(&sConditionVariableHash) ConditionVariableHash;
399
400	status_t error = sConditionVariableHash.Init(kConditionVariableHashSize);
401	if (error != B_OK) {
402		panic("condition_variable_init(): Failed to init hash table: %s",
403			strerror(error));
404	}
405
406	add_debugger_command_etc("cvar", &dump_condition_variable,
407		"Dump condition variable info",
408		"<address>\n"
409		"Prints info for the specified condition variable.\n"
410		"  <address>  - Address of the condition variable or the object it is\n"
411		"               associated with.\n", 0);
412	add_debugger_command_etc("cvars", &list_condition_variables,
413		"List condition variables",
414		"\n"
415		"Lists all existing condition variables\n", 0);
416}
417