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 #include <IOKit/IOSharedDataQueue.h>
  30 #include <IOKit/IODataQueueShared.h>
  31 #include <IOKit/IOLib.h>
  32 #include <IOKit/IOMemoryDescriptor.h>
  33
  34 #ifdef enqueue
  35 #undef enqueue
  36 #endif
  37
  38 #ifdef dequeue
  39 #undef dequeue
  40 #endif
  41
  42 #define super IODataQueue
  43
  44 OSDefineMetaClassAndStructors(IOSharedDataQueue, IODataQueue)
  45
  46 IOSharedDataQueue *IOSharedDataQueue::withCapacity(UInt32 size)
  47 {
  48     IOSharedDataQueue *dataQueue = new IOSharedDataQueue;
  49
  50     if (dataQueue) {
  51         if  (!dataQueue->initWithCapacity(size)) {
  52             dataQueue->release();
  53             dataQueue = 0;
  54         }
  55     }
  56
  57     return dataQueue;
  58 }
  59
  60 IOSharedDataQueue *IOSharedDataQueue::withEntries(UInt32 numEntries, UInt32 entrySize)
  61 {
  62     IOSharedDataQueue *dataQueue = new IOSharedDataQueue;
  63
  64     if (dataQueue) {
  65         if (!dataQueue->initWithEntries(numEntries, entrySize)) {
  66             dataQueue->release();
  67             dataQueue = 0;
  68         }
  69     }
  70
  71     return dataQueue;
  72 }
  73
  74 Boolean IOSharedDataQueue::initWithCapacity(UInt32 size)
  75 {
  76     IODataQueueAppendix *   appendix;
  77     vm_size_t               allocSize;
  78
  79     if (!super::init()) {
  80         return false;
  81     }
  82
  83     _reserved = (ExpansionData *)IOMalloc(sizeof(struct ExpansionData));
  84     if (!_reserved) {
  85         return false;
  86     }
  87
  88     if (size > UINT32_MAX - DATA_QUEUE_MEMORY_HEADER_SIZE - DATA_QUEUE_MEMORY_APPENDIX_SIZE) {
  89         return false;
  90     }
  91
  92     allocSize = round_page(size + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE);
  93
  94     if (allocSize < size) {
  95         return false;
  96     }
  97
  98     dataQueue = (IODataQueueMemory *)IOMallocAligned(allocSize, PAGE_SIZE);
  99     if (dataQueue == 0) {
 100         return false;
 101     }
 102     bzero(dataQueue, allocSize);
 103
 104     dataQueue->queueSize    = size;
 105 //  dataQueue->head         = 0;
 106 //  dataQueue->tail         = 0;
 107
 108     if (!setQueueSize(size)) {
 109         return false;
 110     }
 111
 112     appendix            = (IODataQueueAppendix *)((UInt8 *)dataQueue + size + DATA_QUEUE_MEMORY_HEADER_SIZE);
 113     appendix->version   = 0;
 114
 115     if (!notifyMsg) {
 116         notifyMsg = IOMalloc(sizeof(mach_msg_header_t));
 117         if (!notifyMsg)
 118             return false;
 119     }
 120     bzero(notifyMsg, sizeof(mach_msg_header_t));
 121
 122     setNotificationPort(MACH_PORT_NULL);
 123
 124     return true;
 125 }
 126
 127 void IOSharedDataQueue::free()
 128 {
 129     if (dataQueue) {
 130         IOFreeAligned(dataQueue, round_page(getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE));
 131         dataQueue = NULL;
 132         if (notifyMsg) {
 133             IOFree(notifyMsg, sizeof(mach_msg_header_t));
 134             notifyMsg = NULL;
 135         }
 136     }
 137
 138     if (_reserved) {
 139         IOFree (_reserved, sizeof(struct ExpansionData));
 140         _reserved = NULL;
 141     }
 142
 143     super::free();
 144 }
 145
 146 IOMemoryDescriptor *IOSharedDataQueue::getMemoryDescriptor()
 147 {
 148     IOMemoryDescriptor *descriptor = 0;
 149
 150     if (dataQueue != 0) {
 151         descriptor = IOMemoryDescriptor::withAddress(dataQueue, getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE, kIODirectionOutIn);
 152     }
 153
 154     return descriptor;
 155 }
 156
 157
 158 IODataQueueEntry * IOSharedDataQueue::peek()
 159 {
 160     IODataQueueEntry *entry      = 0;
 161     UInt32            headOffset;
 162     UInt32            tailOffset;
 163
 164     if (!dataQueue) {
 165         return NULL;
 166     }
 167
 168     // Read head and tail with acquire barrier
 169     // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 170     headOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 171     tailOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_ACQUIRE);
 172
 173     if (headOffset != tailOffset) {
 174         IODataQueueEntry *  head        = 0;
 175         UInt32              headSize    = 0;
 176         UInt32              headOffset  = dataQueue->head;
 177         UInt32              queueSize   = getQueueSize();
 178
 179         if (headOffset >= queueSize) {
 180             return NULL;
 181         }
 182
 183         head         = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 184         headSize     = head->size;
 185
 186         // Check if there's enough room before the end of the queue for a header.
 187         // If there is room, check if there's enough room to hold the header and
 188         // the data.
 189
 190         if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 191             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 192             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 193             (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 194             // No room for the header or the data, wrap to the beginning of the queue.
 195             // Note: wrapping even with the UINT32_MAX checks, as we have to support
 196             // queueSize of UINT32_MAX
 197             entry = dataQueue->queue;
 198         } else {
 199             entry = head;
 200         }
 201     }
 202
 203     return entry;
 204 }
 205
 206 Boolean IOSharedDataQueue::enqueue(void * data, UInt32 dataSize)
 207 {
 208     UInt32             head;
 209     UInt32             tail;
 210     UInt32             newTail;
 211     const UInt32       entrySize = dataSize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 212     IODataQueueEntry * entry;
 213
 214     // Force a single read of head and tail
 215     // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 216     tail = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_RELAXED);
 217     head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_ACQUIRE);
 218
 219     // Check for overflow of entrySize
 220     if (dataSize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) {
 221         return false;
 222     }
 223     // Check for underflow of (getQueueSize() - tail)
 224     if (getQueueSize() < tail || getQueueSize() < head) {
 225         return false;
 226     }
 227
 228     if ( tail >= head )
 229     {
 230         // Is there enough room at the end for the entry?
 231         if ((entrySize <= UINT32_MAX - tail) &&
 232             ((tail + entrySize) <= getQueueSize()) )
 233         {
 234             entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 235
 236             entry->size = dataSize;
 237             memcpy(&entry->data, data, dataSize);
 238
 239             // The tail can be out of bound when the size of the new entry
 240             // exactly matches the available space at the end of the queue.
 241             // The tail can range from 0 to dataQueue->queueSize inclusive.
 242
 243             newTail = tail + entrySize;
 244         }
 245         else if ( head > entrySize )     // Is there enough room at the beginning?
 246         {
 247             // Wrap around to the beginning, but do not allow the tail to catch
 248             // up to the head.
 249
 250             dataQueue->queue->size = dataSize;
 251
 252             // We need to make sure that there is enough room to set the size before
 253             // doing this. The user client checks for this and will look for the size
 254             // at the beginning if there isn't room for it at the end.
 255
 256             if ( ( getQueueSize() - tail ) >= DATA_QUEUE_ENTRY_HEADER_SIZE )
 257             {
 258                 ((IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail))->size = dataSize;
 259             }
 260
 261             memcpy(&dataQueue->queue->data, data, dataSize);
 262             newTail = entrySize;
 263         }
 264         else
 265         {
 266             return false;    // queue is full
 267         }
 268     }
 269     else
 270     {
 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         {
 276             entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 277
 278             entry->size = dataSize;
 279             memcpy(&entry->data, data, dataSize);
 280             newTail = tail + entrySize;
 281         }
 282         else
 283         {
 284             return false;    // queue is full
 285         }
 286     }
 287
 288         // Publish the data we just enqueued
 289         __c11_atomic_store((_Atomic UInt32 *)&dataQueue->tail, newTail, __ATOMIC_RELEASE);
 290
 291         if (tail != head) {
 292                 //
 293                 // The memory barrier below paris with the one in ::dequeue
 294                 // so that either our store to the tail cannot be missed by
 295                 // the next dequeue attempt, or we will observe the dequeuer
 296                 // making the queue empty.
 297                 //
 298                 // Of course, if we already think the queue is empty,
 299                 // there's no point paying this extra cost.
 300                 //
 301                 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
 302                 head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 303         }
 304
 305         if (tail == head) {
 306                 // Send notification (via mach message) that data is now available.
 307                 sendDataAvailableNotification();
 308         }
 309         return true;
 310 }
 311
 312 Boolean IOSharedDataQueue::dequeue(void *data, UInt32 *dataSize)
 313 {
 314     Boolean             retVal          = TRUE;
 315     IODataQueueEntry *  entry           = 0;
 316     UInt32              entrySize       = 0;
 317     UInt32              headOffset      = 0;
 318     UInt32              tailOffset      = 0;
 319     UInt32              newHeadOffset   = 0;
 320
 321         if (!dataQueue || (data && !dataSize)) {
 322         return false;
 323     }
 324
 325     // Read head and tail with acquire barrier
 326     // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
 327     headOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
 328     tailOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_ACQUIRE);
 329
 330     if (headOffset != tailOffset) {
 331         IODataQueueEntry *  head        = 0;
 332         UInt32              headSize    = 0;
 333         UInt32              queueSize   = getQueueSize();
 334
 335         if (headOffset > queueSize) {
 336             return false;
 337         }
 338
 339         head         = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 340         headSize     = head->size;
 341
 342         // we wrapped around to beginning, so read from there
 343         // either there was not even room for the header
 344         if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 345             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 346             // or there was room for the header, but not for the data
 347             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 348             (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 349             // Note: we have to wrap to the beginning even with the UINT32_MAX checks
 350             // because we have to support a queueSize of UINT32_MAX.
 351             entry           = dataQueue->queue;
 352             entrySize       = entry->size;
 353             if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 354                 (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 355                 return false;
 356             }
 357             newHeadOffset   = entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 358             // else it is at the end
 359         } else {
 360             entry           = head;
 361             entrySize       = entry->size;
 362             if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 363                 (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headOffset) ||
 364                 (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE + headOffset > queueSize)) {
 365                 return false;
 366             }
 367             newHeadOffset   = headOffset + entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 368         }
 369         } else {
 370                 // empty queue
 371                 return false;
 372         }
 373
 374         if (data) {
 375                 if (entrySize > *dataSize) {
 376                         // not enough space
 377                         return false;
 378                 }
 379                 memcpy(data, &(entry->data), entrySize);
 380                 *dataSize = entrySize;
 381         }
 382
 383         __c11_atomic_store((_Atomic UInt32 *)&dataQueue->head, newHeadOffset, __ATOMIC_RELEASE);
 384
 385         if (newHeadOffset == tailOffset) {
 386                 //
 387                 // If we are making the queue empty, then we need to make sure
 388                 // that either the enqueuer notices, or we notice the enqueue
 389                 // that raced with our making of the queue empty.
 390                 //
 391                 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
 392         }
 393
 394     return retVal;
 395 }
 396
 397 UInt32 IOSharedDataQueue::getQueueSize()
 398 {
 399     if (!_reserved) {
 400         return 0;
 401     }
 402     return _reserved->queueSize;
 403 }
 404
 405 Boolean 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);