1 // Copyright 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "mojo/system/core_impl.h" 6 7 #include <vector> 8 9 #include "base/logging.h" 10 #include "base/time/time.h" 11 #include "mojo/system/constants.h" 12 #include "mojo/system/data_pipe_consumer_dispatcher.h" 13 #include "mojo/system/data_pipe_producer_dispatcher.h" 14 #include "mojo/system/dispatcher.h" 15 #include "mojo/system/local_data_pipe.h" 16 #include "mojo/system/memory.h" 17 #include "mojo/system/message_pipe.h" 18 #include "mojo/system/message_pipe_dispatcher.h" 19 #include "mojo/system/waiter.h" 20 21 namespace mojo { 22 namespace system { 23 24 // Implementation notes 25 // 26 // Mojo primitives are implemented by the singleton |CoreImpl| object. Most 27 // calls are for a "primary" handle (the first argument). 28 // |CoreImpl::GetDispatcher()| is used to look up a |Dispatcher| object for a 29 // given handle. That object implements most primitives for that object. The 30 // wait primitives are not attached to objects and are implemented by |CoreImpl| 31 // itself. 32 // 33 // Some objects have multiple handles associated to them, e.g., message pipes 34 // (which have two). In such a case, there is still a |Dispatcher| (e.g., 35 // |MessagePipeDispatcher|) for each handle, with each handle having a strong 36 // reference to the common "secondary" object (e.g., |MessagePipe|). This 37 // secondary object does NOT have any references to the |Dispatcher|s (even if 38 // it did, it wouldn't be able to do anything with them due to lock order 39 // requirements -- see below). 40 // 41 // Waiting is implemented by having the thread that wants to wait call the 42 // |Dispatcher|s for the handles that it wants to wait on with a |Waiter| 43 // object; this |Waiter| object may be created on the stack of that thread or be 44 // kept in thread local storage for that thread (TODO(vtl): future improvement). 45 // The |Dispatcher| then adds the |Waiter| to a |WaiterList| that's either owned 46 // by that |Dispatcher| (see |SimpleDispatcher|) or by a secondary object (e.g., 47 // |MessagePipe|). To signal/wake a |Waiter|, the object in question -- either a 48 // |SimpleDispatcher| or a secondary object -- talks to its |WaiterList|. 49 50 // Thread-safety notes 51 // 52 // Mojo primitives calls are thread-safe. We achieve this with relatively 53 // fine-grained locking. There is a global handle table lock. This lock should 54 // be held as briefly as possible (TODO(vtl): a future improvement would be to 55 // switch it to a reader-writer lock). Each |Dispatcher| object then has a lock 56 // (which subclasses can use to protect their data). 57 // 58 // The lock ordering is as follows: 59 // 1. global handle table lock 60 // 2. |Dispatcher| locks 61 // 3. secondary object locks 62 // ... 63 // INF. |Waiter| locks 64 // 65 // Notes: 66 // - While holding a |Dispatcher| lock, you may not unconditionally attempt 67 // to take another |Dispatcher| lock. (This has consequences on the 68 // concurrency semantics of |MojoWriteMessage()| when passing handles.) 69 // Doing so would lead to deadlock. 70 // - Locks at the "INF" level may not have any locks taken while they are 71 // held. 72 73 CoreImpl::HandleTableEntry::HandleTableEntry() 74 : busy(false) { 75 } 76 77 CoreImpl::HandleTableEntry::HandleTableEntry( 78 const scoped_refptr<Dispatcher>& dispatcher) 79 : dispatcher(dispatcher), 80 busy(false) { 81 } 82 83 CoreImpl::HandleTableEntry::~HandleTableEntry() { 84 DCHECK(!busy); 85 } 86 87 // static 88 void CoreImpl::Init() { 89 CorePrivate::Init(new CoreImpl()); 90 } 91 92 MojoTimeTicks CoreImpl::GetTimeTicksNow() { 93 return base::TimeTicks::Now().ToInternalValue(); 94 } 95 96 MojoResult CoreImpl::Close(MojoHandle handle) { 97 if (handle == MOJO_HANDLE_INVALID) 98 return MOJO_RESULT_INVALID_ARGUMENT; 99 100 scoped_refptr<Dispatcher> dispatcher; 101 { 102 base::AutoLock locker(handle_table_lock_); 103 HandleTableMap::iterator it = handle_table_.find(handle); 104 if (it == handle_table_.end()) 105 return MOJO_RESULT_INVALID_ARGUMENT; 106 if (it->second.busy) 107 return MOJO_RESULT_BUSY; 108 dispatcher = it->second.dispatcher; 109 handle_table_.erase(it); 110 } 111 112 // The dispatcher doesn't have a say in being closed, but gets notified of it. 113 // Note: This is done outside of |handle_table_lock_|. As a result, there's a 114 // race condition that the dispatcher must handle; see the comment in 115 // |Dispatcher| in dispatcher.h. 116 return dispatcher->Close(); 117 } 118 119 MojoResult CoreImpl::Wait(MojoHandle handle, 120 MojoWaitFlags flags, 121 MojoDeadline deadline) { 122 return WaitManyInternal(&handle, &flags, 1, deadline); 123 } 124 125 MojoResult CoreImpl::WaitMany(const MojoHandle* handles, 126 const MojoWaitFlags* flags, 127 uint32_t num_handles, 128 MojoDeadline deadline) { 129 if (!VerifyUserPointer<MojoHandle>(handles, num_handles)) 130 return MOJO_RESULT_INVALID_ARGUMENT; 131 if (!VerifyUserPointer<MojoWaitFlags>(flags, num_handles)) 132 return MOJO_RESULT_INVALID_ARGUMENT; 133 if (num_handles < 1) 134 return MOJO_RESULT_INVALID_ARGUMENT; 135 if (num_handles > kMaxWaitManyNumHandles) 136 return MOJO_RESULT_RESOURCE_EXHAUSTED; 137 return WaitManyInternal(handles, flags, num_handles, deadline); 138 } 139 140 MojoResult CoreImpl::CreateMessagePipe(MojoHandle* message_pipe_handle_0, 141 MojoHandle* message_pipe_handle_1) { 142 if (!VerifyUserPointer<MojoHandle>(message_pipe_handle_0, 1)) 143 return MOJO_RESULT_INVALID_ARGUMENT; 144 if (!VerifyUserPointer<MojoHandle>(message_pipe_handle_1, 1)) 145 return MOJO_RESULT_INVALID_ARGUMENT; 146 147 scoped_refptr<MessagePipeDispatcher> dispatcher_0( 148 new MessagePipeDispatcher()); 149 scoped_refptr<MessagePipeDispatcher> dispatcher_1( 150 new MessagePipeDispatcher()); 151 152 MojoHandle h0, h1; 153 { 154 base::AutoLock locker(handle_table_lock_); 155 156 h0 = AddDispatcherNoLock(dispatcher_0); 157 if (h0 == MOJO_HANDLE_INVALID) 158 return MOJO_RESULT_RESOURCE_EXHAUSTED; 159 160 h1 = AddDispatcherNoLock(dispatcher_1); 161 if (h1 == MOJO_HANDLE_INVALID) { 162 handle_table_.erase(h0); 163 return MOJO_RESULT_RESOURCE_EXHAUSTED; 164 } 165 } 166 167 scoped_refptr<MessagePipe> message_pipe(new MessagePipe()); 168 dispatcher_0->Init(message_pipe, 0); 169 dispatcher_1->Init(message_pipe, 1); 170 171 *message_pipe_handle_0 = h0; 172 *message_pipe_handle_1 = h1; 173 return MOJO_RESULT_OK; 174 } 175 176 MojoResult CoreImpl::WriteMessage(MojoHandle message_pipe_handle, 177 const void* bytes, 178 uint32_t num_bytes, 179 const MojoHandle* handles, 180 uint32_t num_handles, 181 MojoWriteMessageFlags flags) { 182 scoped_refptr<Dispatcher> dispatcher(GetDispatcher(message_pipe_handle)); 183 if (!dispatcher.get()) 184 return MOJO_RESULT_INVALID_ARGUMENT; 185 186 // Easy case: not sending any handles. 187 if (num_handles == 0) 188 return dispatcher->WriteMessage(bytes, num_bytes, NULL, flags); 189 190 // We have to handle |handles| here, since we have to mark them busy in the 191 // global handle table. We can't delegate this to the dispatcher, since the 192 // handle table lock must be acquired before the dispatcher lock. 193 // 194 // (This leads to an oddity: |handles|/|num_handles| are always verified for 195 // validity, even for dispatchers that don't support |WriteMessage()| and will 196 // simply return failure unconditionally. It also breaks the usual 197 // left-to-right verification order of arguments.) 198 if (!VerifyUserPointer<MojoHandle>(handles, num_handles)) 199 return MOJO_RESULT_INVALID_ARGUMENT; 200 if (num_handles > kMaxMessageNumHandles) 201 return MOJO_RESULT_RESOURCE_EXHAUSTED; 202 203 // We'll need to hold on to the dispatchers so that we can pass them on to 204 // |WriteMessage()| and also so that we can unlock their locks afterwards 205 // without accessing the handle table. These can be dumb pointers, since their 206 // entries in the handle table won't get removed (since they'll be marked as 207 // busy). 208 std::vector<Dispatcher*> dispatchers(num_handles); 209 210 // When we pass handles, we have to try to take all their dispatchers' locks 211 // and mark the handles as busy. If the call succeeds, we then remove the 212 // handles from the handle table. 213 { 214 base::AutoLock locker(handle_table_lock_); 215 216 std::vector<HandleTableEntry*> entries(num_handles); 217 218 // First verify all the handles and get their dispatchers. 219 uint32_t i; 220 MojoResult error_result = MOJO_RESULT_INTERNAL; 221 for (i = 0; i < num_handles; i++) { 222 // Sending your own handle is not allowed (and, for consistency, returns 223 // "busy"). 224 if (handles[i] == message_pipe_handle) { 225 error_result = MOJO_RESULT_BUSY; 226 break; 227 } 228 229 HandleTableMap::iterator it = handle_table_.find(handles[i]); 230 if (it == handle_table_.end()) { 231 error_result = MOJO_RESULT_INVALID_ARGUMENT; 232 break; 233 } 234 235 entries[i] = &it->second; 236 if (entries[i]->busy) { 237 error_result = MOJO_RESULT_BUSY; 238 break; 239 } 240 // Note: By marking the handle as busy here, we're also preventing the 241 // same handle from being sent multiple times in the same message. 242 entries[i]->busy = true; 243 244 // Try to take the lock. 245 if (!entries[i]->dispatcher->lock().Try()) { 246 // Unset the busy flag (since it won't be unset below). 247 entries[i]->busy = false; 248 error_result = MOJO_RESULT_BUSY; 249 break; 250 } 251 252 // We shouldn't race with things that close dispatchers, since closing can 253 // only take place either under |handle_table_lock_| or when the handle is 254 // marked as busy. 255 DCHECK(!entries[i]->dispatcher->is_closed_no_lock()); 256 257 // Hang on to the pointer to the dispatcher (which we'll need to release 258 // the lock without going through the handle table). 259 dispatchers[i] = entries[i]->dispatcher; 260 } 261 if (i < num_handles) { 262 DCHECK_NE(error_result, MOJO_RESULT_INTERNAL); 263 264 // Unset the busy flags and release the locks. 265 for (uint32_t j = 0; j < i; j++) { 266 DCHECK(entries[j]->busy); 267 entries[j]->busy = false; 268 entries[j]->dispatcher->lock().Release(); 269 } 270 return error_result; 271 } 272 } 273 274 MojoResult rv = dispatcher->WriteMessage(bytes, num_bytes, 275 &dispatchers, 276 flags); 277 278 // We need to release the dispatcher locks before we take the handle table 279 // lock. 280 for (uint32_t i = 0; i < num_handles; i++) { 281 dispatchers[i]->lock().AssertAcquired(); 282 dispatchers[i]->lock().Release(); 283 } 284 285 if (rv == MOJO_RESULT_OK) { 286 base::AutoLock locker(handle_table_lock_); 287 288 // Succeeded, so the handles should be removed from the handle table. (The 289 // transferring to new dispatchers/closing must have already been done.) 290 for (uint32_t i = 0; i < num_handles; i++) { 291 HandleTableMap::iterator it = handle_table_.find(handles[i]); 292 DCHECK(it != handle_table_.end()); 293 DCHECK(it->second.busy); 294 it->second.busy = false; // For the sake of a |DCHECK()|. 295 handle_table_.erase(it); 296 } 297 } else { 298 base::AutoLock locker(handle_table_lock_); 299 300 // Failed, so the handles should go back to their normal state. 301 for (uint32_t i = 0; i < num_handles; i++) { 302 HandleTableMap::iterator it = handle_table_.find(handles[i]); 303 DCHECK(it != handle_table_.end()); 304 DCHECK(it->second.busy); 305 it->second.busy = false; 306 } 307 } 308 309 return rv; 310 } 311 312 MojoResult CoreImpl::ReadMessage(MojoHandle message_pipe_handle, 313 void* bytes, 314 uint32_t* num_bytes, 315 MojoHandle* handles, 316 uint32_t* num_handles, 317 MojoReadMessageFlags flags) { 318 scoped_refptr<Dispatcher> dispatcher(GetDispatcher(message_pipe_handle)); 319 if (!dispatcher.get()) 320 return MOJO_RESULT_INVALID_ARGUMENT; 321 322 if (num_handles) { 323 if (!VerifyUserPointer<uint32_t>(num_handles, 1)) 324 return MOJO_RESULT_INVALID_ARGUMENT; 325 if (!VerifyUserPointer<MojoHandle>(handles, *num_handles)) 326 return MOJO_RESULT_INVALID_ARGUMENT; 327 } 328 329 // Easy case: won't receive any handles. 330 if (!num_handles || *num_handles == 0) 331 return dispatcher->ReadMessage(bytes, num_bytes, NULL, num_handles, flags); 332 333 std::vector<scoped_refptr<Dispatcher> > dispatchers; 334 MojoResult rv = dispatcher->ReadMessage(bytes, num_bytes, 335 &dispatchers, num_handles, 336 flags); 337 if (!dispatchers.empty()) { 338 DCHECK_EQ(rv, MOJO_RESULT_OK); 339 DCHECK(num_handles); 340 DCHECK_LE(dispatchers.size(), static_cast<size_t>(*num_handles)); 341 342 base::AutoLock locker(handle_table_lock_); 343 344 for (size_t i = 0; i < dispatchers.size(); i++) { 345 // TODO(vtl): What should we do if we hit the maximum handle table size 346 // here? Currently, we'll just fill in those handles with 347 // |MOJO_HANDLE_INVALID| (and return success anyway). 348 handles[i] = AddDispatcherNoLock(dispatchers[i]); 349 } 350 } 351 352 return rv; 353 } 354 355 MojoResult CoreImpl::CreateDataPipe(const MojoCreateDataPipeOptions* options, 356 MojoHandle* data_pipe_producer_handle, 357 MojoHandle* data_pipe_consumer_handle) { 358 if (options && !VerifyUserPointer<void>(options, sizeof(*options))) 359 return MOJO_RESULT_INVALID_ARGUMENT; 360 if (!VerifyUserPointer<MojoHandle>(data_pipe_producer_handle, 1)) 361 return MOJO_RESULT_INVALID_ARGUMENT; 362 if (!VerifyUserPointer<MojoHandle>(data_pipe_consumer_handle, 1)) 363 return MOJO_RESULT_INVALID_ARGUMENT; 364 365 scoped_refptr<LocalDataPipe> data_pipe(new LocalDataPipe()); 366 MojoResult result = data_pipe->Init(options); 367 if (result != MOJO_RESULT_OK) 368 return result; 369 370 scoped_refptr<DataPipeProducerDispatcher> producer_dispatcher( 371 new DataPipeProducerDispatcher()); 372 scoped_refptr<DataPipeConsumerDispatcher> consumer_dispatcher( 373 new DataPipeConsumerDispatcher()); 374 375 MojoHandle producer_handle, consumer_handle; 376 { 377 base::AutoLock locker(handle_table_lock_); 378 379 producer_handle = AddDispatcherNoLock(producer_dispatcher); 380 if (producer_handle == MOJO_HANDLE_INVALID) 381 return MOJO_RESULT_RESOURCE_EXHAUSTED; 382 383 consumer_handle = AddDispatcherNoLock(consumer_dispatcher); 384 if (consumer_handle == MOJO_HANDLE_INVALID) { 385 handle_table_.erase(producer_handle); 386 return MOJO_RESULT_RESOURCE_EXHAUSTED; 387 } 388 } 389 390 producer_dispatcher->Init(data_pipe); 391 consumer_dispatcher->Init(data_pipe); 392 393 *data_pipe_producer_handle = producer_handle; 394 *data_pipe_consumer_handle = consumer_handle; 395 return MOJO_RESULT_OK; 396 } 397 398 MojoResult CoreImpl::WriteData(MojoHandle data_pipe_producer_handle, 399 const void* elements, 400 uint32_t* num_elements, 401 MojoWriteDataFlags flags) { 402 scoped_refptr<Dispatcher> dispatcher( 403 GetDispatcher(data_pipe_producer_handle)); 404 if (!dispatcher.get()) 405 return MOJO_RESULT_INVALID_ARGUMENT; 406 407 return dispatcher->WriteData(elements, num_elements, flags); 408 } 409 410 MojoResult CoreImpl::BeginWriteData(MojoHandle data_pipe_producer_handle, 411 void** buffer, 412 uint32_t* buffer_num_elements, 413 MojoWriteDataFlags flags) { 414 scoped_refptr<Dispatcher> dispatcher( 415 GetDispatcher(data_pipe_producer_handle)); 416 if (!dispatcher.get()) 417 return MOJO_RESULT_INVALID_ARGUMENT; 418 419 return dispatcher->BeginWriteData(buffer, buffer_num_elements, flags); 420 } 421 422 MojoResult CoreImpl::EndWriteData(MojoHandle data_pipe_producer_handle, 423 uint32_t num_elements_written) { 424 scoped_refptr<Dispatcher> dispatcher( 425 GetDispatcher(data_pipe_producer_handle)); 426 if (!dispatcher.get()) 427 return MOJO_RESULT_INVALID_ARGUMENT; 428 429 return dispatcher->EndWriteData(num_elements_written); 430 } 431 432 MojoResult CoreImpl::ReadData(MojoHandle data_pipe_consumer_handle, 433 void* elements, 434 uint32_t* num_elements, 435 MojoReadDataFlags flags) { 436 scoped_refptr<Dispatcher> dispatcher( 437 GetDispatcher(data_pipe_consumer_handle)); 438 if (!dispatcher.get()) 439 return MOJO_RESULT_INVALID_ARGUMENT; 440 441 return dispatcher->ReadData(elements, num_elements, flags); 442 } 443 444 MojoResult CoreImpl::BeginReadData(MojoHandle data_pipe_consumer_handle, 445 const void** buffer, 446 uint32_t* buffer_num_elements, 447 MojoReadDataFlags flags) { 448 scoped_refptr<Dispatcher> dispatcher( 449 GetDispatcher(data_pipe_consumer_handle)); 450 if (!dispatcher.get()) 451 return MOJO_RESULT_INVALID_ARGUMENT; 452 453 return dispatcher->BeginReadData(buffer, buffer_num_elements, flags); 454 } 455 456 MojoResult CoreImpl::EndReadData(MojoHandle data_pipe_consumer_handle, 457 uint32_t num_elements_read) { 458 scoped_refptr<Dispatcher> dispatcher( 459 GetDispatcher(data_pipe_consumer_handle)); 460 if (!dispatcher.get()) 461 return MOJO_RESULT_INVALID_ARGUMENT; 462 463 return dispatcher->EndReadData(num_elements_read); 464 } 465 466 CoreImpl::CoreImpl() 467 : next_handle_(MOJO_HANDLE_INVALID + 1) { 468 } 469 470 CoreImpl::~CoreImpl() { 471 // This should usually not be reached (the singleton lives forever), except in 472 // tests. 473 } 474 475 scoped_refptr<Dispatcher> CoreImpl::GetDispatcher(MojoHandle handle) { 476 if (handle == MOJO_HANDLE_INVALID) 477 return NULL; 478 479 base::AutoLock locker(handle_table_lock_); 480 HandleTableMap::iterator it = handle_table_.find(handle); 481 if (it == handle_table_.end()) 482 return NULL; 483 484 return it->second.dispatcher; 485 } 486 487 MojoHandle CoreImpl::AddDispatcherNoLock( 488 const scoped_refptr<Dispatcher>& dispatcher) { 489 DCHECK(dispatcher.get()); 490 handle_table_lock_.AssertAcquired(); 491 DCHECK_NE(next_handle_, MOJO_HANDLE_INVALID); 492 493 if (handle_table_.size() >= kMaxHandleTableSize) 494 return MOJO_HANDLE_INVALID; 495 496 // TODO(vtl): Maybe we want to do something different/smarter. (Or maybe try 497 // assigning randomly?) 498 while (handle_table_.find(next_handle_) != handle_table_.end()) { 499 next_handle_++; 500 if (next_handle_ == MOJO_HANDLE_INVALID) 501 next_handle_++; 502 } 503 504 MojoHandle new_handle = next_handle_; 505 handle_table_[new_handle] = HandleTableEntry(dispatcher); 506 507 next_handle_++; 508 if (next_handle_ == MOJO_HANDLE_INVALID) 509 next_handle_++; 510 511 return new_handle; 512 } 513 514 // Note: We allow |handles| to repeat the same handle multiple times, since 515 // different flags may be specified. 516 // TODO(vtl): This incurs a performance cost in |RemoveWaiter()|. Analyze this 517 // more carefully and address it if necessary. 518 MojoResult CoreImpl::WaitManyInternal(const MojoHandle* handles, 519 const MojoWaitFlags* flags, 520 uint32_t num_handles, 521 MojoDeadline deadline) { 522 DCHECK_GT(num_handles, 0u); 523 524 std::vector<scoped_refptr<Dispatcher> > dispatchers; 525 dispatchers.reserve(num_handles); 526 for (uint32_t i = 0; i < num_handles; i++) { 527 scoped_refptr<Dispatcher> dispatcher = GetDispatcher(handles[i]); 528 if (!dispatcher.get()) 529 return MOJO_RESULT_INVALID_ARGUMENT; 530 dispatchers.push_back(dispatcher); 531 } 532 533 // TODO(vtl): Should make the waiter live (permanently) in TLS. 534 Waiter waiter; 535 waiter.Init(); 536 537 uint32_t i; 538 MojoResult rv = MOJO_RESULT_OK; 539 for (i = 0; i < num_handles; i++) { 540 rv = dispatchers[i]->AddWaiter(&waiter, 541 flags[i], 542 static_cast<MojoResult>(i)); 543 if (rv != MOJO_RESULT_OK) 544 break; 545 } 546 uint32_t num_added = i; 547 548 if (rv == MOJO_RESULT_ALREADY_EXISTS) 549 rv = static_cast<MojoResult>(i); // The i-th one is already "triggered". 550 else if (rv == MOJO_RESULT_OK) 551 rv = waiter.Wait(deadline); 552 553 // Make sure no other dispatchers try to wake |waiter| for the current 554 // |Wait()|/|WaitMany()| call. (Only after doing this can |waiter| be 555 // destroyed, but this would still be required if the waiter were in TLS.) 556 for (i = 0; i < num_added; i++) 557 dispatchers[i]->RemoveWaiter(&waiter); 558 559 return rv; 560 } 561 562 } // namespace system 563 } // namespace mojo 564
