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 bool 94 ConditionVariableEntry::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 117 inline void 118 ConditionVariableEntry::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 130 status_t 131 ConditionVariableEntry::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 185 status_t 186 ConditionVariableEntry::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 */ 200 void 201 ConditionVariable::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 214 void 215 ConditionVariable::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 237 void 238 ConditionVariable::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 265 void 266 ConditionVariable::Add(ConditionVariableEntry* entry) 267 { 268 InterruptsSpinLocker _(fLock); 269 entry->AddToLockedVariable(this); 270 } 271 272 273 status_t 274 ConditionVariable::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 283 ConditionVariable::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 296 ConditionVariable::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 308 void 309 ConditionVariable::_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 */ 326 void 327 ConditionVariable::_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 362 ConditionVariable::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 377 void 378 ConditionVariable::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 395 void 396 condition_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