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 44OSDefineMetaClassAndStructors(IOSharedDataQueue, IODataQueue) 45 46IOSharedDataQueue *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 60IOSharedDataQueue *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 74Boolean 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 119void 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 134IOMemoryDescriptor *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 146IODataQueueEntry * 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 183Boolean 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 270Boolean 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 349UInt32 IOSharedDataQueue::getQueueSize() 350{ 351 if (!_reserved) { 352 return 0; 353 } 354 return _reserved->queueSize; 355} 356 357Boolean IOSharedDataQueue::setQueueSize(UInt32 size) 358{ 359 if (!_reserved) { 360 return false; 361 } 362 _reserved->queueSize = size; 363 return true; 364} 365 366OSMetaClassDefineReservedUnused(IOSharedDataQueue, 0); 367OSMetaClassDefineReservedUnused(IOSharedDataQueue, 1); 368OSMetaClassDefineReservedUnused(IOSharedDataQueue, 2); 369OSMetaClassDefineReservedUnused(IOSharedDataQueue, 3); 370OSMetaClassDefineReservedUnused(IOSharedDataQueue, 4); 371OSMetaClassDefineReservedUnused(IOSharedDataQueue, 5); 372OSMetaClassDefineReservedUnused(IOSharedDataQueue, 6); 373OSMetaClassDefineReservedUnused(IOSharedDataQueue, 7); 374