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
 103     dataQueue->queueSize    = size;
 104     dataQueue->head         = 0;
 105     dataQueue->tail         = 0;
 106
 107     if (!setQueueSize(size)) {
 108         return false;
 109     }
 110
 111     appendix            = (IODataQueueAppendix *)((UInt8 *)dataQueue + size + DATA_QUEUE_MEMORY_HEADER_SIZE);
 112     appendix->version   = 0;
 113     notifyMsg           = &(appendix->msgh);
 114     setNotificationPort(MACH_PORT_NULL);
 115
 116     return true;
 117 }
 118
 119 void IOSharedDataQueue::free()
 120 {
 121     if (dataQueue) {
 122         IOFreeAligned(dataQueue, round_page(getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE));
 123         dataQueue = NULL;
 124     }
 125
 126     if (_reserved) {
 127         IOFree (_reserved, sizeof(struct ExpansionData));
 128         _reserved = NULL;
 129     }
 130
 131     super::free();
 132 }
 133
 134 IOMemoryDescriptor *IOSharedDataQueue::getMemoryDescriptor()
 135 {
 136     IOMemoryDescriptor *descriptor = 0;
 137
 138     if (dataQueue != 0) {
 139         descriptor = IOMemoryDescriptor::withAddress(dataQueue, getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE, kIODirectionOutIn);
 140     }
 141
 142     return descriptor;
 143 }
 144
 145
 146 IODataQueueEntry * IOSharedDataQueue::peek()
 147 {
 148     IODataQueueEntry *entry = 0;
 149
 150     if (dataQueue && (dataQueue->head != dataQueue->tail)) {
 151         IODataQueueEntry *  head                = 0;
 152         UInt32              headSize    = 0;
 153         UInt32              headOffset  = dataQueue->head;
 154         UInt32              queueSize   = getQueueSize();
 155
 156         if (headOffset >= queueSize) {
 157             return NULL;
 158         }
 159
 160         head            = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 161         headSize        = head->size;
 162
 163                 // Check if there's enough room before the end of the queue for a header.
 164         // If there is room, check if there's enough room to hold the header and
 165         // the data.
 166
 167         if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 168             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 169             (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 170             (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 171             // No room for the header or the data, wrap to the beginning of the queue.
 172             // Note: wrapping even with the UINT32_MAX checks, as we have to support
 173             // queueSize of UINT32_MAX
 174             entry = dataQueue->queue;
 175         } else {
 176             entry = head;
 177         }
 178     }
 179
 180     return entry;
 181 }
 182
 183 Boolean IOSharedDataQueue::enqueue(void * data, UInt32 dataSize)
 184 {
 185     const UInt32       head      = dataQueue->head;  // volatile
 186     const UInt32       tail      = dataQueue->tail;
 187     const UInt32       entrySize = dataSize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 188     IODataQueueEntry * entry;
 189
 190     // Check for overflow of entrySize
 191     if (dataSize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) {
 192         return false;
 193     }
 194     // Check for underflow of (getQueueSize() - tail)
 195     if (getQueueSize() < tail) {
 196         return false;
 197     }
 198
 199     if ( tail >= head )
 200     {
 201         // Is there enough room at the end for the entry?
 202         if ((entrySize <= UINT32_MAX - tail) &&
 203             ((tail + entrySize) <= getQueueSize()) )
 204         {
 205             entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 206
 207             entry->size = dataSize;
 208             memcpy(&entry->data, data, dataSize);
 209
 210             // The tail can be out of bound when the size of the new entry
 211             // exactly matches the available space at the end of the queue.
 212             // The tail can range from 0 to dataQueue->queueSize inclusive.
 213
 214             OSAddAtomic(entrySize, (SInt32 *)&dataQueue->tail);
 215         }
 216         else if ( head > entrySize )     // Is there enough room at the beginning?
 217         {
 218             // Wrap around to the beginning, but do not allow the tail to catch
 219             // up to the head.
 220
 221             dataQueue->queue->size = dataSize;
 222
 223             // We need to make sure that there is enough room to set the size before
 224             // doing this. The user client checks for this and will look for the size
 225             // at the beginning if there isn't room for it at the end.
 226
 227             if ( ( getQueueSize() - tail ) >= DATA_QUEUE_ENTRY_HEADER_SIZE )
 228             {
 229                 ((IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail))->size = dataSize;
 230             }
 231
 232             memcpy(&dataQueue->queue->data, data, dataSize);
 233             OSCompareAndSwap(dataQueue->tail, entrySize, &dataQueue->tail);
 234         }
 235         else
 236         {
 237             return false;    // queue is full
 238         }
 239     }
 240     else
 241     {
 242         // Do not allow the tail to catch up to the head when the queue is full.
 243         // That's why the comparison uses a '>' rather than '>='.
 244
 245         if ( (head - tail) > entrySize )
 246         {
 247             entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
 248
 249             entry->size = dataSize;
 250             memcpy(&entry->data, data, dataSize);
 251             OSAddAtomic(entrySize, (SInt32 *)&dataQueue->tail);
 252         }
 253         else
 254         {
 255             return false;    // queue is full
 256         }
 257     }
 258
 259     // Send notification (via mach message) that data is available.
 260
 261     if ( ( head == tail )                                                   /* queue was empty prior to enqueue() */
 262         ||   ( dataQueue->head == tail ) )   /* queue was emptied during enqueue() */
 263     {
 264         sendDataAvailableNotification();
 265     }
 266
 267     return true;
 268 }
 269
 270 Boolean IOSharedDataQueue::dequeue(void *data, UInt32 *dataSize)
 271 {
 272     Boolean             retVal          = TRUE;
 273     IODataQueueEntry *  entry           = 0;
 274     UInt32              entrySize       = 0;
 275     UInt32              newHeadOffset   = 0;
 276
 277     if (dataQueue) {
 278         if (dataQueue->head != dataQueue->tail) {
 279             IODataQueueEntry *  head            = 0;
 280             UInt32              headSize    = 0;
 281             UInt32              headOffset  = dataQueue->head;
 282             UInt32              queueSize   = getQueueSize();
 283
 284             if (headOffset > queueSize) {
 285                 return false;
 286             }
 287
 288             head                = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
 289             headSize    = head->size;
 290
 291             // we wrapped around to beginning, so read from there
 292             // either there was not even room for the header
 293             if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 294                 (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
 295                 // or there was room for the header, but not for the data
 296                 (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
 297                 (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 298                 // Note: we have to wrap to the beginning even with the UINT32_MAX checks
 299                 // because we have to support a queueSize of UINT32_MAX.
 300                 entry           = dataQueue->queue;
 301                 entrySize       = entry->size;
 302                 if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 303                     (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
 304                     return false;
 305                 }
 306                 newHeadOffset   = entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 307                 // else it is at the end
 308             } else {
 309                 entry           = head;
 310                 entrySize       = entry->size;
 311                 if ((entrySize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
 312                     (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headOffset) ||
 313                     (entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE + headOffset > queueSize)) {
 314                     return false;
 315                 }
 316                 newHeadOffset   = headOffset + entrySize + DATA_QUEUE_ENTRY_HEADER_SIZE;
 317             }
 318         }
 319
 320         if (entry) {
 321             if (data) {
 322                 if (dataSize) {
 323                     if (entrySize <= *dataSize) {
 324                         memcpy(data, &(entry->data), entrySize);
 325                         OSCompareAndSwap( dataQueue->head, newHeadOffset, (SInt32 *)&dataQueue->head);
 326                     } else {
 327                         retVal = FALSE;
 328                     }
 329                 } else {
 330                     retVal = FALSE;
 331                 }
 332             } else {
 333                 OSCompareAndSwap( dataQueue->head, newHeadOffset, (SInt32 *)&dataQueue->head);
 334             }
 335
 336             if (dataSize) {
 337                 *dataSize = entrySize;
 338             }
 339         } else {
 340             retVal = FALSE;
 341         }
 342     } else {
 343         retVal = FALSE;
 344     }
 345
 346     return retVal;
 347 }
 348
 349 UInt32 IOSharedDataQueue::getQueueSize()
 350 {
 351     if (!_reserved) {
 352         return 0;
 353     }
 354     return _reserved->queueSize;
 355 }
 356
 357 Boolean IOSharedDataQueue::setQueueSize(UInt32 size)
 358 {
 359     if (!_reserved) {
 360         return false;
 361     }
 362     _reserved->queueSize = size;
 363     return true;
 364 }
 365
 366 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 0);
 367 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 1);
 368 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 2);
 369 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 3);
 370 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 4);
 371 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 5);
 372 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 6);
 373 OSMetaClassDefineReservedUnused(IOSharedDataQueue, 7);