1 /* 2 * Copyright 2007, Ingo Weinhold, bonefish@cs.tu-berlin.de. 3 * Distributed under the terms of the MIT License. 4 */ 5 6 #include <condition_variable.h> 7 8 #include <new> 9 #include <stdlib.h> 10 #include <string.h> 11 12 #include <debug.h> 13 #include <kscheduler.h> 14 #include <ksignal.h> 15 #include <int.h> 16 #include <thread.h> 17 #include <util/AutoLock.h> 18 19 20 static const int kConditionVariableHashSize = 512; 21 22 23 struct ConditionVariableHashDefinition { 24 typedef const void* KeyType; 25 typedef PrivateConditionVariable ValueType; 26 27 size_t HashKey(const void* key) const 28 { return (size_t)key; } 29 size_t Hash(PrivateConditionVariable* variable) const 30 { return (size_t)variable->fObject; } 31 bool Compare(const void* key, PrivateConditionVariable* variable) const 32 { return key == variable->fObject; } 33 HashTableLink<PrivateConditionVariable>* GetLink( 34 PrivateConditionVariable* variable) const 35 { return variable; } 36 }; 37 38 typedef OpenHashTable<ConditionVariableHashDefinition> ConditionVariableHash; 39 static ConditionVariableHash sConditionVariableHash; 40 static spinlock sConditionVariablesLock; 41 42 43 static int 44 list_condition_variables(int argc, char** argv) 45 { 46 PrivateConditionVariable::ListAll(); 47 return 0; 48 } 49 50 51 static int 52 dump_condition_variable(int argc, char** argv) 53 { 54 if (argc != 2) { 55 print_debugger_command_usage(argv[0]); 56 return 0; 57 } 58 59 addr_t address = parse_expression(argv[1]); 60 if (address == 0) 61 return 0; 62 63 PrivateConditionVariable* variable = sConditionVariableHash.Lookup( 64 (void*)address); 65 66 if (variable == NULL) { 67 // It might be a direct pointer to a condition variable. Search the 68 // hash. 69 ConditionVariableHash::Iterator it(&sConditionVariableHash); 70 while (PrivateConditionVariable* hashVariable = it.Next()) { 71 if (hashVariable == (void*)address) { 72 variable = hashVariable; 73 break; 74 } 75 } 76 } 77 78 if (variable != NULL) { 79 variable->Dump(); 80 81 set_debug_variable("_cvar", (addr_t)variable); 82 set_debug_variable("_object", (addr_t)variable->Object()); 83 84 } else 85 kprintf("no condition variable at or with key %p\n", (void*)address); 86 87 return 0; 88 } 89 90 91 // #pragma mark - PrivateConditionVariableEntry 92 93 94 bool 95 PrivateConditionVariableEntry::Add(const void* object, 96 PrivateConditionVariableEntry* threadNext) 97 { 98 ASSERT(object != NULL); 99 100 fThread = thread_get_current_thread(); 101 fFlags = 0; 102 fResult = B_OK; 103 104 InterruptsLocker _; 105 SpinLocker locker(sConditionVariablesLock); 106 107 // add to the list of entries for this thread 108 fThreadNext = threadNext; 109 if (threadNext) { 110 fThreadPrevious = threadNext->fThreadPrevious; 111 threadNext->fThreadPrevious = this; 112 if (fThreadPrevious) 113 fThreadPrevious->fThreadNext = this; 114 } else 115 fThreadPrevious = NULL; 116 117 // add to the queue for the variable 118 fVariable = sConditionVariableHash.Lookup(object); 119 if (fVariable) { 120 fVariableNext = fVariable->fEntries; 121 fVariable->fEntries = this; 122 } else 123 fResult = B_ENTRY_NOT_FOUND; 124 125 return (fVariable != NULL); 126 } 127 128 129 status_t 130 PrivateConditionVariableEntry::Wait(uint32 flags) 131 { 132 if (!are_interrupts_enabled()) { 133 panic("wait_for_condition_variable_entry() called with interrupts " 134 "disabled"); 135 return B_ERROR; 136 } 137 138 InterruptsLocker _; 139 SpinLocker threadLocker(thread_spinlock); 140 SpinLocker locker(sConditionVariablesLock); 141 142 // get first entry for this thread 143 PrivateConditionVariableEntry* firstEntry = this; 144 while (firstEntry->fThreadPrevious) 145 firstEntry = firstEntry->fThreadPrevious; 146 147 // check whether any entry has already been notified 148 // (set the flags while at it) 149 PrivateConditionVariableEntry* entry = firstEntry; 150 while (entry) { 151 if (entry->fVariable == NULL) 152 return entry->fResult; 153 154 entry->fFlags = flags; 155 156 entry = entry->fThreadNext; 157 } 158 159 // When interruptable, check pending signals first 160 struct thread* thread = thread_get_current_thread(); 161 if (((flags & B_CAN_INTERRUPT) 162 && (thread->sig_pending & ~thread->sig_block_mask) != 0) 163 || ((flags & B_KILL_CAN_INTERRUPT) 164 && (thread->sig_pending & KILL_SIGNALS))) { 165 // remove all of the thread's entries from their variables 166 entry = firstEntry; 167 while (entry) { 168 entry->_Remove(); 169 entry = entry->fThreadNext; 170 } 171 return B_INTERRUPTED; 172 } 173 174 // wait 175 thread->next_state = B_THREAD_WAITING; 176 thread->condition_variable_entry = firstEntry; 177 thread->sem.blocking = -1; 178 179 locker.Unlock(); 180 scheduler_reschedule(); 181 threadLocker.Unlock(); 182 183 return firstEntry->fResult; 184 } 185 186 187 status_t 188 PrivateConditionVariableEntry::Wait(const void* object, uint32 flags) 189 { 190 if (Add(object, NULL)) 191 return Wait(flags); 192 return B_ENTRY_NOT_FOUND; 193 } 194 195 196 /*! Removes the entry from its variable. 197 Interrupts must be disabled, sConditionVariablesLock must be held. 198 */ 199 void 200 PrivateConditionVariableEntry::_Remove() 201 { 202 if (!fVariable) 203 return; 204 205 // fast path, if we're first in queue 206 if (this == fVariable->fEntries) { 207 fVariable->fEntries = fVariableNext; 208 fVariableNext = NULL; 209 fVariable = NULL; 210 return; 211 } 212 213 // we're not the first entry -- find our previous entry 214 PrivateConditionVariableEntry* entry = fVariable->fEntries; 215 while (entry->fVariableNext) { 216 if (this == entry->fVariableNext) { 217 entry->fVariableNext = fVariableNext; 218 fVariableNext = NULL; 219 fVariable = NULL; 220 return; 221 } 222 223 entry = entry->fVariableNext; 224 } 225 } 226 227 228 class PrivateConditionVariableEntry::Private { 229 public: 230 inline Private(PrivateConditionVariableEntry& entry) 231 : fEntry(entry) 232 { 233 } 234 235 inline uint32 Flags() const { return fEntry.fFlags; } 236 inline void Remove() const { fEntry._Remove(); } 237 inline void SetResult(status_t result) { fEntry.fResult = result; } 238 239 private: 240 PrivateConditionVariableEntry& fEntry; 241 }; 242 243 244 // #pragma mark - PrivateConditionVariable 245 246 247 /*static*/ void 248 PrivateConditionVariable::ListAll() 249 { 250 kprintf(" variable object (type) waiting threads\n"); 251 kprintf("------------------------------------------------------------\n"); 252 ConditionVariableHash::Iterator it(&sConditionVariableHash); 253 while (PrivateConditionVariable* variable = it.Next()) { 254 // count waiting threads 255 int count = 0; 256 PrivateConditionVariableEntry* entry = variable->fEntries; 257 while (entry) { 258 count++; 259 entry = entry->fVariableNext; 260 } 261 262 kprintf("%p %p %-20s %15d\n", variable, variable->fObject, 263 variable->fObjectType, count); 264 } 265 } 266 267 268 void 269 PrivateConditionVariable::Dump() const 270 { 271 kprintf("condition variable %p\n", this); 272 kprintf(" object: %p (%s)\n", fObject, fObjectType); 273 kprintf(" threads:"); 274 PrivateConditionVariableEntry* entry = fEntries; 275 while (entry) { 276 kprintf(" %ld", entry->fThread->id); 277 entry = entry->fVariableNext; 278 } 279 kprintf("\n"); 280 } 281 282 283 void 284 PrivateConditionVariable::Publish(const void* object, const char* objectType) 285 { 286 ASSERT(object != NULL); 287 288 fObject = object; 289 fObjectType = objectType; 290 fEntries = NULL; 291 292 InterruptsLocker _; 293 SpinLocker locker(sConditionVariablesLock); 294 295 ASSERT_PRINT(sConditionVariableHash.Lookup(object) == NULL, 296 "condition variable: %p\n", sConditionVariableHash.Lookup(object)); 297 298 sConditionVariableHash.InsertUnchecked(this); 299 } 300 301 302 void 303 PrivateConditionVariable::Unpublish(bool threadsLocked) 304 { 305 ASSERT(fObject != NULL); 306 307 InterruptsLocker _; 308 SpinLocker threadLocker(threadsLocked ? NULL : &thread_spinlock); 309 SpinLocker locker(sConditionVariablesLock); 310 311 #if KDEBUG 312 PrivateConditionVariable* variable = sConditionVariableHash.Lookup(fObject); 313 if (variable != this) { 314 panic("Condition variable %p not published, found: %p", this, variable); 315 return; 316 } 317 #endif 318 319 sConditionVariableHash.RemoveUnchecked(this); 320 fObject = NULL; 321 fObjectType = NULL; 322 323 if (fEntries) 324 _Notify(true, B_ENTRY_NOT_FOUND); 325 } 326 327 328 void 329 PrivateConditionVariable::Notify(bool all, bool threadsLocked) 330 { 331 ASSERT(fObject != NULL); 332 333 InterruptsLocker _; 334 SpinLocker threadLocker(threadsLocked ? NULL : &thread_spinlock); 335 SpinLocker locker(sConditionVariablesLock); 336 337 #if KDEBUG 338 PrivateConditionVariable* variable = sConditionVariableHash.Lookup(fObject); 339 if (variable != this) { 340 panic("Condition variable %p not published, found: %p", this, variable); 341 return; 342 } 343 #endif 344 345 if (fEntries) 346 _Notify(all, B_OK); 347 } 348 349 350 /*! Called with interrupts disabled and the condition variable spinlock and 351 thread lock held. 352 */ 353 void 354 PrivateConditionVariable::_Notify(bool all, status_t result) 355 { 356 // dequeue and wake up the blocked threads 357 while (PrivateConditionVariableEntry* entry = fEntries) { 358 fEntries = entry->fVariableNext; 359 entry->fVariableNext = NULL; 360 entry->fVariable = NULL; 361 362 struct thread* thread = entry->fThread; 363 364 if (thread->condition_variable_entry != NULL) 365 thread->condition_variable_entry->fResult = result; 366 367 // remove other entries of this thread from their respective variables 368 PrivateConditionVariableEntry* otherEntry = entry->fThreadPrevious; 369 while (otherEntry) { 370 otherEntry->_Remove(); 371 otherEntry = otherEntry->fThreadPrevious; 372 } 373 374 otherEntry = entry->fThreadNext; 375 while (otherEntry) { 376 otherEntry->_Remove(); 377 otherEntry = otherEntry->fThreadNext; 378 } 379 380 // wake up the thread 381 thread->condition_variable_entry = NULL; 382 if (thread->state == B_THREAD_WAITING) 383 scheduler_enqueue_in_run_queue(thread); 384 385 if (!all) 386 break; 387 } 388 } 389 390 391 // #pragma mark - 392 393 394 /*! Interrupts must be disabled, thread lock must be held. 395 */ 396 status_t 397 condition_variable_interrupt_thread(struct thread* thread) 398 { 399 SpinLocker locker(sConditionVariablesLock); 400 401 if (thread == NULL || thread->state != B_THREAD_WAITING 402 || thread->condition_variable_entry == NULL) { 403 return B_BAD_VALUE; 404 } 405 406 PrivateConditionVariableEntry* entry = thread->condition_variable_entry; 407 uint32 flags = PrivateConditionVariableEntry::Private(*entry).Flags(); 408 409 // interruptable? 410 if ((flags & B_CAN_INTERRUPT) == 0 411 && ((flags & B_KILL_CAN_INTERRUPT) == 0 412 || (thread->sig_pending & KILL_SIGNALS) == 0)) { 413 return B_NOT_ALLOWED; 414 } 415 416 PrivateConditionVariableEntry::Private(*entry).SetResult(B_INTERRUPTED); 417 418 // remove all of the thread's entries from their variables 419 ASSERT(entry->ThreadPrevious() == NULL); 420 while (entry) { 421 PrivateConditionVariableEntry::Private(*entry).Remove(); 422 entry = entry->ThreadNext(); 423 } 424 425 // wake up the thread 426 thread->condition_variable_entry = NULL; 427 scheduler_enqueue_in_run_queue(thread); 428 429 return B_OK; 430 } 431 432 433 void 434 condition_variable_init() 435 { 436 new(&sConditionVariableHash) ConditionVariableHash( 437 kConditionVariableHashSize); 438 439 status_t error = sConditionVariableHash.InitCheck(); 440 if (error != B_OK) { 441 panic("condition_variable_init(): Failed to init hash table: %s", 442 strerror(error)); 443 } 444 445 add_debugger_command_etc("cvar", &dump_condition_variable, 446 "Dump condition variable info", 447 "<address>\n" 448 "Prints info for the specified condition variable.\n" 449 " <address> - Address of the condition variable or the object it is\n" 450 " associated with.\n", 0); 451 add_debugger_command_etc("cvars", &list_condition_variables, 452 "List condition variables", 453 "\n" 454 "Lists all existing condition variables\n", 0); 455 } 456 457