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 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
127void 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
146IOMemoryDescriptor *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
158IODataQueueEntry * 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
206Boolean 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
312Boolean 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
397UInt32 IOSharedDataQueue::getQueueSize()
398{
399 if (!_reserved) {
400 return 0;
401 }
402 return _reserved->queueSize;
403}
404
405Boolean IOSharedDataQueue::setQueueSize(UInt32 size)
406{
407 if (!_reserved) {
408 return false;
409 }
410 _reserved->queueSize = size;
411 return true;
412}
413
414OSMetaClassDefineReservedUnused(IOSharedDataQueue, 0);
415OSMetaClassDefineReservedUnused(IOSharedDataQueue, 1);
416OSMetaClassDefineReservedUnused(IOSharedDataQueue, 2);
417OSMetaClassDefineReservedUnused(IOSharedDataQueue, 3);
418OSMetaClassDefineReservedUnused(IOSharedDataQueue, 4);
419OSMetaClassDefineReservedUnused(IOSharedDataQueue, 5);
420OSMetaClassDefineReservedUnused(IOSharedDataQueue, 6);
421OSMetaClassDefineReservedUnused(IOSharedDataQueue, 7);
422