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 28 static const int kConditionVariableHashSize = 512; 29 30 31 struct 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 45 typedef BOpenHashTable<ConditionVariableHashDefinition> ConditionVariableHash; 46 static ConditionVariableHash sConditionVariableHash; 47 static rw_spinlock sConditionVariableHashLock; 48 49 50 static int 51 list_condition_variables(int argc, char** argv) 52 { 53 ConditionVariable::ListAll(); 54 return 0; 55 } 56 57 58 static int 59 dump_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 93 ConditionVariableEntry::ConditionVariableEntry() 94 : fVariable(NULL) 95 { 96 } 97 98 99 ConditionVariableEntry::~ConditionVariableEntry() 100 { 101 if (fVariable != NULL) 102 _RemoveFromVariable(); 103 } 104 105 106 bool 107 ConditionVariableEntry::Add(const void* object) 108 { 109 ASSERT(object != NULL); 110 111 InterruptsLocker _; 112 ReadSpinLocker hashLocker(sConditionVariableHashLock); 113 114 ConditionVariable* variable = sConditionVariableHash.Lookup(object); 115 116 if (variable == NULL) { 117 fWaitStatus = B_ENTRY_NOT_FOUND; 118 return false; 119 } 120 121 SpinLocker variableLocker(variable->fLock); 122 hashLocker.Unlock(); 123 124 _AddToLockedVariable(variable); 125 126 return true; 127 } 128 129 130 inline void 131 ConditionVariableEntry::_AddToLockedVariable(ConditionVariable* variable) 132 { 133 ASSERT(fVariable == NULL); 134 135 B_INITIALIZE_SPINLOCK(&fLock); 136 fThread = thread_get_current_thread(); 137 fVariable = variable; 138 fWaitStatus = STATUS_ADDED; 139 fVariable->fEntries.Add(this); 140 } 141 142 143 void 144 ConditionVariableEntry::_RemoveFromVariable() 145 { 146 InterruptsLocker _; 147 SpinLocker entryLocker(fLock); 148 149 if (fVariable != NULL) { 150 SpinLocker conditionLocker(fVariable->fLock); 151 if (fVariable->fEntries.Contains(this)) { 152 fVariable->fEntries.Remove(this); 153 } else { 154 entryLocker.Unlock(); 155 // The variable's fEntries did not contain us, but we currently 156 // have the variable's lock acquired. This must mean we are in 157 // a race with the variable's Notify. It is possible we will be 158 // destroyed immediately upon returning here, so we need to 159 // spin until our fVariable member is unset by the Notify thread 160 // and then re-acquire our own lock to avoid a use-after-free. 161 while (atomic_pointer_get(&fVariable) != NULL) {} 162 entryLocker.Lock(); 163 } 164 fVariable = NULL; 165 } 166 } 167 168 169 status_t 170 ConditionVariableEntry::Wait(uint32 flags, bigtime_t timeout) 171 { 172 #if KDEBUG 173 if (!are_interrupts_enabled()) { 174 panic("ConditionVariableEntry::Wait() called with interrupts " 175 "disabled, entry: %p, variable: %p", this, fVariable); 176 return B_ERROR; 177 } 178 #endif 179 180 InterruptsLocker _; 181 SpinLocker entryLocker(fLock); 182 183 if (fVariable == NULL) 184 return fWaitStatus; 185 186 thread_prepare_to_block(fThread, flags, 187 THREAD_BLOCK_TYPE_CONDITION_VARIABLE, fVariable); 188 189 fWaitStatus = STATUS_WAITING; 190 191 entryLocker.Unlock(); 192 193 status_t error; 194 if ((flags & (B_RELATIVE_TIMEOUT | B_ABSOLUTE_TIMEOUT)) != 0) 195 error = thread_block_with_timeout(flags, timeout); 196 else 197 error = thread_block(); 198 199 _RemoveFromVariable(); 200 return error; 201 } 202 203 204 status_t 205 ConditionVariableEntry::Wait(const void* object, uint32 flags, 206 bigtime_t timeout) 207 { 208 if (Add(object)) 209 return Wait(flags, timeout); 210 return B_ENTRY_NOT_FOUND; 211 } 212 213 214 // #pragma mark - ConditionVariable 215 216 217 /*! Initialization method for anonymous (unpublished) condition variables. 218 */ 219 void 220 ConditionVariable::Init(const void* object, const char* objectType) 221 { 222 fObject = object; 223 fObjectType = objectType; 224 new(&fEntries) EntryList; 225 B_INITIALIZE_SPINLOCK(&fLock); 226 227 T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType)); 228 NotifyWaitObjectListeners(&WaitObjectListener::ConditionVariableInitialized, 229 this); 230 } 231 232 233 void 234 ConditionVariable::Publish(const void* object, const char* objectType) 235 { 236 ASSERT(object != NULL); 237 238 fObject = object; 239 fObjectType = objectType; 240 new(&fEntries) EntryList; 241 B_INITIALIZE_SPINLOCK(&fLock); 242 243 T_SCHEDULING_ANALYSIS(InitConditionVariable(this, object, objectType)); 244 NotifyWaitObjectListeners(&WaitObjectListener::ConditionVariableInitialized, 245 this); 246 247 InterruptsWriteSpinLocker _(sConditionVariableHashLock); 248 249 ASSERT_PRINT(sConditionVariableHash.Lookup(object) == NULL, 250 "condition variable: %p\n", sConditionVariableHash.Lookup(object)); 251 252 sConditionVariableHash.InsertUnchecked(this); 253 } 254 255 256 void 257 ConditionVariable::Unpublish() 258 { 259 ASSERT(fObject != NULL); 260 261 InterruptsLocker _; 262 WriteSpinLocker hashLocker(sConditionVariableHashLock); 263 SpinLocker selfLocker(fLock); 264 265 #if KDEBUG 266 ConditionVariable* variable = sConditionVariableHash.Lookup(fObject); 267 if (variable != this) { 268 panic("Condition variable %p not published, found: %p", this, variable); 269 return; 270 } 271 #endif 272 273 sConditionVariableHash.RemoveUnchecked(this); 274 fObject = NULL; 275 fObjectType = NULL; 276 277 hashLocker.Unlock(); 278 279 if (!fEntries.IsEmpty()) 280 _NotifyLocked(true, B_ENTRY_NOT_FOUND); 281 } 282 283 284 void 285 ConditionVariable::Add(ConditionVariableEntry* entry) 286 { 287 InterruptsSpinLocker _(fLock); 288 entry->_AddToLockedVariable(this); 289 } 290 291 292 status_t 293 ConditionVariable::Wait(uint32 flags, bigtime_t timeout) 294 { 295 ConditionVariableEntry entry; 296 Add(&entry); 297 return entry.Wait(flags, timeout); 298 } 299 300 301 /*static*/ void 302 ConditionVariable::NotifyOne(const void* object, status_t result) 303 { 304 InterruptsReadSpinLocker locker(sConditionVariableHashLock); 305 ConditionVariable* variable = sConditionVariableHash.Lookup(object); 306 locker.Unlock(); 307 if (variable == NULL) 308 return; 309 310 variable->NotifyOne(result); 311 } 312 313 314 /*static*/ void 315 ConditionVariable::NotifyAll(const void* object, status_t result) 316 { 317 InterruptsReadSpinLocker locker(sConditionVariableHashLock); 318 ConditionVariable* variable = sConditionVariableHash.Lookup(object); 319 locker.Unlock(); 320 if (variable == NULL) 321 return; 322 323 variable->NotifyAll(result); 324 } 325 326 327 void 328 ConditionVariable::_Notify(bool all, status_t result) 329 { 330 InterruptsSpinLocker _(fLock); 331 332 if (!fEntries.IsEmpty()) { 333 if (result > B_OK) { 334 panic("tried to notify with invalid result %" B_PRId32 "\n", result); 335 result = B_ERROR; 336 } 337 338 _NotifyLocked(all, result); 339 } 340 } 341 342 343 /*! Called with interrupts disabled and the condition variable's spinlock held. 344 */ 345 void 346 ConditionVariable::_NotifyLocked(bool all, status_t result) 347 { 348 // Dequeue and wake up the blocked threads. 349 // We *cannot* hold our own lock while acquiring the Entry's lock, 350 // as this leads to a (non-theoretical!) race between the Entry 351 // entering Wait() and acquiring its own lock, and then acquiring ours. 352 while (ConditionVariableEntry* entry = fEntries.RemoveHead()) { 353 release_spinlock(&fLock); 354 acquire_spinlock(&entry->fLock); 355 356 entry->fVariable = NULL; 357 358 if (entry->fWaitStatus <= 0) { 359 release_spinlock(&entry->fLock); 360 acquire_spinlock(&fLock); 361 continue; 362 } 363 364 if (entry->fWaitStatus == STATUS_WAITING) { 365 SpinLocker _(entry->fThread->scheduler_lock); 366 thread_unblock_locked(entry->fThread, result); 367 } 368 369 entry->fWaitStatus = result; 370 371 release_spinlock(&entry->fLock); 372 acquire_spinlock(&fLock); 373 374 if (!all) 375 break; 376 } 377 } 378 379 380 /*static*/ void 381 ConditionVariable::ListAll() 382 { 383 kprintf(" variable object (type) waiting threads\n"); 384 kprintf("------------------------------------------------------------\n"); 385 ConditionVariableHash::Iterator it(&sConditionVariableHash); 386 while (ConditionVariable* variable = it.Next()) { 387 // count waiting threads 388 int count = variable->fEntries.Count(); 389 390 kprintf("%p %p %-20s %15d\n", variable, variable->fObject, 391 variable->fObjectType, count); 392 } 393 } 394 395 396 void 397 ConditionVariable::Dump() const 398 { 399 kprintf("condition variable %p\n", this); 400 kprintf(" object: %p (%s)\n", fObject, fObjectType); 401 kprintf(" threads:"); 402 403 for (EntryList::ConstIterator it = fEntries.GetIterator(); 404 ConditionVariableEntry* entry = it.Next();) { 405 kprintf(" %" B_PRId32, entry->fThread->id); 406 } 407 kprintf("\n"); 408 } 409 410 411 // #pragma mark - 412 413 414 void 415 condition_variable_init() 416 { 417 new(&sConditionVariableHash) ConditionVariableHash; 418 419 status_t error = sConditionVariableHash.Init(kConditionVariableHashSize); 420 if (error != B_OK) { 421 panic("condition_variable_init(): Failed to init hash table: %s", 422 strerror(error)); 423 } 424 425 add_debugger_command_etc("cvar", &dump_condition_variable, 426 "Dump condition variable info", 427 "<address>\n" 428 "Prints info for the specified condition variable.\n" 429 " <address> - Address of the condition variable or the object it is\n" 430 " associated with.\n", 0); 431 add_debugger_command_etc("cvars", &list_condition_variables, 432 "List condition variables", 433 "\n" 434 "Lists all existing condition variables\n", 0); 435 } 436