iokit/Kernel/IOSharedDataQueue.cpp

   1 /*
   2  * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #define IOKIT_ENABLE_SHARED_PTR
  30
  31 #include <IOKit/IOSharedDataQueue.h>
  32 #include <IOKit/IODataQueueShared.h>
  33 #include <IOKit/IOLib.h>
  34 #include <IOKit/IOMemoryDescriptor.h>
  35 #include <libkern/c++/OSSharedPtr.h>
  36
  37 #ifdef enqueue
  38 #undef enqueue
  39 #endif
  40
  41 #ifdef dequeue
  42 #undef dequeue
  43 #endif
  44
  45 #define super IODataQueue
  46
  47 OSDefineMetaClassAndStructors(IOSharedDataQueue, IODataQueue)
  48
  49 OSSharedPtr<IOSharedDataQueue>
  50 IOSharedDataQueue::withCapacity(UInt32 size)
  51 {
  52         OSSharedPtr<IOSharedDataQueue> dataQueue = OSMakeShared<IOSharedDataQueue>();
  53
  54         if (dataQueue) {
  55                 if (!dataQueue->initWithCapacity(size)) {
  56                         return nullptr;
  57                 }
  58         }
  59
  60         return dataQueue;
  61 }
  62
  63 OSSharedPtr<IOSharedDataQueue>
  64 IOSharedDataQueue::withEntries(UInt32 numEntries, UInt32 entrySize)
  65 {
  66         OSSharedPtr<IOSharedDataQueue> dataQueue = OSMakeShared<IOSharedDataQueue>();
  67
  68         if (dataQueue) {
  69                 if (!dataQueue->initWithEntries(numEntries, entrySize)) {
  70                         return nullptr;
  71                 }
  72         }
  73
  74         return dataQueue;
  75 }
  76
  77 Boolean
  78 IOSharedDataQueue::initWithCapacity(UInt32 size)
  79 {
  80         IODataQueueAppendix *   appendix;
  81         vm_size_t               allocSize;
  82
  83         if (!super::init()) {
  84                 return false;
  85         }
  86
  87         _reserved = (ExpansionData *)IOMalloc(sizeof(struct ExpansionData));
  88         if (!_reserved) {
  89                 return false;
  90         }
  91
  92         if (size > UINT32_MAX - DATA_QUEUE_MEMORY_HEADER_SIZE - DATA_QUEUE_MEMORY_APPENDIX_SIZE) {
  93                 return false;
  94         }
  95
  96         allocSize = round_page(size + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE);
  97
  98         if (allocSize < size) {
  99                 return false;
 100         }
 101
 102         dataQueue = (IODataQueueMemory *)IOMallocAligned(allocSize, PAGE_SIZE);
 103         if (dataQueue == NULL) {
 104                 return false;
 105         }
 106         bzero(dataQueue, allocSize);
 107
 108         dataQueue->queueSize    = size;
 109 //  dataQueue->head         = 0;
 110 //  dataQueue->tail         = 0;
 111
 112         if (!setQueueSize(size)) {
 113                 return false;
 114         }
 115
 116         appendix            = (IODataQueueAppendix *)((UInt8 *)dataQueue + size + DATA_QUEUE_MEMORY_HEADER_SIZE);
 117         appendix->version   = 0;
 118
 119         if (!notifyMsg) {
 120                 notifyMsg = IOMalloc(sizeof(mach_msg_header_t));
 121                 if (!notifyMsg) {
 122                         return false;
 123                 }
 124         }
 125         bzero(notifyMsg, sizeof(mach_msg_header_t));
 126
 127         setNotificationPort(MACH_PORT_NULL);
 128
 129         return true;
 130 }
 131
 132 void
 133 IOSharedDataQueue::free()
 134 {
 135         if (dataQueue) {
 136                 IOFreeAligned(dataQueue, round_page(getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE));
 137                 dataQueue = NULL;
 138                 if (notifyMsg) {
 139                         IOFree(notifyMsg, sizeof(mach_msg_header_t));
 140                         notifyMsg = NULL;
 141                 }
 142         }
 143
 144         if (_reserved) {
 145                 IOFree(_reserved, sizeof(struct ExpansionData));
 146                 _reserved = NULL;
 147         }
 148
 149         super::free();
 150 }
 151
 152 OSSharedPtr<IOMemoryDescriptor>
 153 IOSharedDataQueue::getMemoryDescriptor()
 154 {
 155         OSSharedPtr<IOMemoryDescriptor> descriptor;
 156
 157         if (dataQueue != NULL) {
 158                 descriptor = IOMemoryDescriptor::withAddress(dataQueue, getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE, kIODirectionOutIn);
 159         }
 160
 161         return descriptor;
 162 }
 163
 164
 165 IODataQueueEntry *
 166 IOSharedDataQueue::peek()
 167 {
 168         IODataQueueEntry *entry      = NULL;
 169         UInt32            headOffset;
 170         UInt32            tailOffset;
 171
 172         if (!dataQueue) {
 173                 return NULL;
 174         }
 175
 176         // Read head and tail with acquire barrier
 177         // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 178         headOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 179         tailOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_ACQUIRE);
 180
 181         if (headOffset != tailOffset) {
 182                 volatile IODataQueueEntry * head = NULL;
 183                 UInt32              headSize     = 0;
 184                 UInt32              headOffset   = dataQueue->head;
 185                 UInt32              queueSize    = getQueueSize();
 186
 187                 if (headOffset > queueSize) {
 188                         return NULL;
 189                 }
 190
 191                 head         = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 192                 headSize     = head->size;
 193
 194                 // Check if there's enough room before the end of the queue for a header.
 195                 // If there is room, check if there's enough room to hold the header and
 196                 // the data.
 197
 198                 if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 199                     (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 200                     (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 201                     (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 202                         // No room for the header or the data, wrap to the beginning of the queue.
 203                         // Note: wrapping even with the UINT32_MAX checks, as we have to support
 204                         // queueSize of UINT32_MAX
 205                         entry = dataQueue->queue;
 206                 } else {
 207                         entry = (IODataQueueEntry *)head;
 208                 }
 209         }
 210
 211         return entry;
 212 }
 213
 214 Boolean
 215 IOSharedDataQueue::enqueue(void * data, UInt32 dataSize)
 216 {
 217         UInt32             head;
 218         UInt32             tail;
 219         UInt32             newTail;
 220         const UInt32       entrySize = dataSize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 221         IODataQueueEntry * entry;
 222
 223         // Force a single read of head and tail
 224         // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 225         tail = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_RELAXED);
 226         head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_ACQUIRE);
 227
 228         // Check for overflow of entrySize
 229         if (dataSize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) {
 230                 return false;
 231         }
 232         // Check for underflow of (getQueueSize() - tail)
 233         if (getQueueSize() < tail || getQueueSize() < head) {
 234                 return false;
 235         }
 236
 237         if (tail >= head) {
 238                 // Is there enough room at the end for the entry?
 239                 if ((entrySize <= UINT32_MAX - tail) &&
 240                     ((tail + entrySize) <= getQueueSize())) {
 241                         entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 242
 243                         entry->size = dataSize;
 244                         __nochk_memcpy(&entry->data, data, dataSize);
 245
 246                         // The tail can be out of bound when the size of the new entry
 247                         // exactly matches the available space at the end of the queue.
 248                         // The tail can range from 0 to dataQueue->queueSize inclusive.
 249
 250                         newTail = tail + entrySize;
 251                 } else if (head > entrySize) { // Is there enough room at the beginning?
 252                         // Wrap around to the beginning, but do not allow the tail to catch
 253                         // up to the head.
 254
 255                         dataQueue->queue->size = dataSize;
 256
 257                         // We need to make sure that there is enough room to set the size before
 258                         // doing this. The user client checks for this and will look for the size
 259                         // at the beginning if there isn't room for it at the end.
 260
 261                         if ((getQueueSize() - tail) >= DATA_QUEUE_ENTRY_HEADER_SIZE) {
 262                                 ((IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail))->size = dataSize;
 263                         }
 264
 265                         __nochk_memcpy(&dataQueue->queue->data, data, dataSize);
 266                         newTail = entrySize;
 267                 } else {
 268                         return false; // queue is full
 269                 }
 270         } else {
 271                 // Do not allow the tail to catch up to the head when the queue is full.
 272                 // That's why the comparison uses a '>' rather than '>='.
 273
 274                 if ((head - tail) > entrySize) {
 275                         entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 276
 277                         entry->size = dataSize;
 278                         __nochk_memcpy(&entry->data, data, dataSize);
 279                         newTail = tail + entrySize;
 280                 } else {
 281                         return false; // queue is full
 282                 }
 283         }
 284
 285         // Publish the data we just enqueued
 286         __c11_atomic_store((_Atomic UInt32 *)&dataQueue->tail, newTail, __ATOMIC_RELEASE);
 287
 288         if (tail != head) {
 289                 //
 290                 // The memory barrier below paris with the one in ::dequeue
 291                 // so that either our store to the tail cannot be missed by
 292                 // the next dequeue attempt, or we will observe the dequeuer
 293                 // making the queue empty.
 294                 //
 295                 // Of course, if we already think the queue is empty,
 296                 // there's no point paying this extra cost.
 297                 //
 298                 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
 299                 head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 300         }
 301
 302         if (tail == head) {
 303                 // Send notification (via mach message) that data is now available.
 304                 sendDataAvailableNotification();
 305         }
 306         return true;
 307 }
 308
 309 Boolean
 310 IOSharedDataQueue::dequeue(void *data, UInt32 *dataSize)
 311 {
 312         Boolean             retVal          = TRUE;
 313         volatile IODataQueueEntry *  entry  = NULL;
 314         UInt32              entrySize       = 0;
 315         UInt32              headOffset      = 0;
 316         UInt32              tailOffset      = 0;
 317         UInt32              newHeadOffset   = 0;
 318
 319         if (!dataQueue || (data && !dataSize)) {
 320                 return false;
 321         }
 322
 323         // Read head and tail with acquire barrier
 324         // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 325         headOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 326         tailOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_ACQUIRE);
 327
 328         if (headOffset != tailOffset) {
 329                 volatile IODataQueueEntry * head = NULL;
 330                 UInt32              headSize     = 0;
 331                 UInt32              queueSize    = getQueueSize();
 332
 333                 if (headOffset > queueSize) {
 334                         return false;
 335                 }
 336
 337                 head         = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 338                 headSize     = head->size;
 339
 340                 // we wrapped around to beginning, so read from there
 341                 // either there was not even room for the header
 342                 if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 343                     (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 344                     // or there was room for the header, but not for the data
 345                     (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 346                     (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 347                         // Note: we have to wrap to the beginning even with the UINT32_MAX checks
 348                         // because we have to support a queueSize of UINT32_MAX.
 349                         entry           = dataQueue->queue;
 350                         entrySize       = entry->size;
 351                         if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 352                             (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 353                                 return false;
 354                         }
 355                         newHeadOffset   = entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 356                         // else it is at the end
 357                 } else {
 358                         entry           = head;
 359                         entrySize       = entry->size;
 360                         if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 361                             (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headOffset) ||
 362                             (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE + headOffset > queueSize)) {
 363                                 return false;
 364                         }
 365                         newHeadOffset   = headOffset + entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 366                 }
 367         } else {
 368                 // empty queue
 369                 return false;
 370         }
 371
 372         if (data) {
 373                 if (entrySize > *dataSize) {
 374                         // not enough space
 375                         return false;
 376                 }
 377                 __nochk_memcpy(data, (void *)entry->data, entrySize);
 378                 *dataSize = entrySize;
 379         }
 380
 381         __c11_atomic_store((_Atomic UInt32 *)&dataQueue->head, newHeadOffset, __ATOMIC_RELEASE);
 382
 383         if (newHeadOffset == tailOffset) {
 384                 //
 385                 // If we are making the queue empty, then we need to make sure
 386                 // that either the enqueuer notices, or we notice the enqueue
 387                 // that raced with our making of the queue empty.
 388                 //
 389                 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
 390         }
 391
 392         return retVal;
 393 }
 394
 395 UInt32
 396 IOSharedDataQueue::getQueueSize()
 397 {
 398         if (!_reserved) {
 399                 return 0;
 400         }
 401         return _reserved->queueSize;
 402 }
 403
 404 Boolean
 405 IOSharedDataQueue::setQueueSize(UInt32 size)
 406 {
 407         if (!_reserved) {
 408                 return false;
 409         }
 410         _reserved->queueSize = size;
 411         return true;
 412 }
 413
 414 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 0);
 415 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 1);
 416 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 2);
 417 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 3);
 418 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 4);
 419 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 5);
 420 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 6);
 421 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 7);