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
47OSDefineMetaClassAndStructors(IOSharedDataQueue, IODataQueue)
48
49OSSharedPtr<IOSharedDataQueue>
50IOSharedDataQueue::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
63OSSharedPtr<IOSharedDataQueue>
64IOSharedDataQueue::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
77Boolean
78IOSharedDataQueue::initWithCapacity(UInt32 size)
79{
80 IODataQueueAppendix * appendix;
81 vm_size_t allocSize;
82 kern_return_t kr;
83
84 if (!super::init()) {
85 return false;
86 }
87
88 _reserved = IOMallocType(ExpansionData);
89 if (!_reserved) {
90 return false;
91 }
92
93 if (size > UINT32_MAX - DATA_QUEUE_MEMORY_HEADER_SIZE - DATA_QUEUE_MEMORY_APPENDIX_SIZE) {
94 return false;
95 }
96
97 allocSize = round_page(x: size + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE);
98
99 if (allocSize < size) {
100 return false;
101 }
102
103 kr = kmem_alloc(map: kernel_map, addrp: (vm_offset_t *)&dataQueue, size: allocSize,
104 flags: (kma_flags_t)(KMA_DATA | KMA_ZERO), tag: IOMemoryTag(map: kernel_map));
105 if (kr != KERN_SUCCESS) {
106 return false;
107 }
108
109 dataQueue->queueSize = size;
110// dataQueue->head = 0;
111// dataQueue->tail = 0;
112
113 if (!setQueueSize(size)) {
114 return false;
115 }
116
117 appendix = (IODataQueueAppendix *)((UInt8 *)dataQueue + size + DATA_QUEUE_MEMORY_HEADER_SIZE);
118 appendix->version = 0;
119
120 if (!notifyMsg) {
121 notifyMsg = IOMallocType(mach_msg_header_t);
122 if (!notifyMsg) {
123 return false;
124 }
125 }
126 bzero(s: notifyMsg, n: sizeof(mach_msg_header_t));
127
128 setNotificationPort(MACH_PORT_NULL);
129
130 return true;
131}
132
133void
134IOSharedDataQueue::free()
135{
136 if (dataQueue) {
137 kmem_free(map: kernel_map, addr: (vm_offset_t)dataQueue, size: round_page(x: getQueueSize() +
138 DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE));
139 dataQueue = NULL;
140 if (notifyMsg) {
141 IOFreeType(notifyMsg, mach_msg_header_t);
142 notifyMsg = NULL;
143 }
144 }
145
146 if (_reserved) {
147 IOFreeType(_reserved, ExpansionData);
148 _reserved = NULL;
149 }
150
151 super::free();
152}
153
154OSSharedPtr<IOMemoryDescriptor>
155IOSharedDataQueue::getMemoryDescriptor()
156{
157 OSSharedPtr<IOMemoryDescriptor> descriptor;
158
159 if (dataQueue != NULL) {
160 descriptor = IOMemoryDescriptor::withAddress(address: dataQueue, withLength: getQueueSize() + DATA_QUEUE_MEMORY_HEADER_SIZE + DATA_QUEUE_MEMORY_APPENDIX_SIZE, withDirection: kIODirectionOutIn);
161 }
162
163 return descriptor;
164}
165
166
167IODataQueueEntry *
168IOSharedDataQueue::peek()
169{
170 IODataQueueEntry *entry = NULL;
171 UInt32 headOffset;
172 UInt32 tailOffset;
173
174 if (!dataQueue) {
175 return NULL;
176 }
177
178 // Read head and tail with acquire barrier
179 // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
180 headOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
181 tailOffset = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_ACQUIRE);
182
183 if (headOffset != tailOffset) {
184 volatile IODataQueueEntry * head = NULL;
185 UInt32 headSize = 0;
186 UInt32 headOffset = dataQueue->head;
187 UInt32 queueSize = getQueueSize();
188
189 if (headOffset > queueSize) {
190 return NULL;
191 }
192
193 head = (IODataQueueEntry *)((char *)dataQueue->queue + headOffset);
194 headSize = head->size;
195
196 // Check if there's enough room before the end of the queue for a header.
197 // If there is room, check if there's enough room to hold the header and
198 // the data.
199
200 if ((headOffset > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) ||
201 (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize) ||
202 (headOffset + DATA_QUEUE_ENTRY_HEADER_SIZE > UINT32_MAX - headSize) ||
203 (headOffset + headSize + DATA_QUEUE_ENTRY_HEADER_SIZE > queueSize)) {
204 // No room for the header or the data, wrap to the beginning of the queue.
205 // Note: wrapping even with the UINT32_MAX checks, as we have to support
206 // queueSize of UINT32_MAX
207 entry = dataQueue->queue;
208 } else {
209 entry = (IODataQueueEntry *)head;
210 }
211 }
212
213 return entry;
214}
215
216Boolean
217IOSharedDataQueue::enqueue(void * data, UInt32 dataSize)
218{
219 UInt32 head;
220 UInt32 tail;
221 UInt32 newTail;
222 const UInt32 entrySize = dataSize + DATA_QUEUE_ENTRY_HEADER_SIZE;
223 IODataQueueEntry * entry;
224
225 // Force a single read of head and tail
226 // See rdar://problem/40780584 for an explanation of relaxed/acquire barriers
227 tail = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->tail, __ATOMIC_RELAXED);
228 head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_ACQUIRE);
229
230 // Check for overflow of entrySize
231 if (dataSize > UINT32_MAX - DATA_QUEUE_ENTRY_HEADER_SIZE) {
232 return false;
233 }
234 // Check for underflow of (getQueueSize() - tail)
235 if (getQueueSize() < tail || getQueueSize() < head) {
236 return false;
237 }
238
239 if (tail >= head) {
240 // Is there enough room at the end for the entry?
241 if ((entrySize <= UINT32_MAX - tail) &&
242 ((tail + entrySize) <= getQueueSize())) {
243 entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
244
245 entry->size = dataSize;
246 __nochk_memcpy(dst: &entry->data, src: data, n: dataSize);
247
248 // The tail can be out of bound when the size of the new entry
249 // exactly matches the available space at the end of the queue.
250 // The tail can range from 0 to dataQueue->queueSize inclusive.
251
252 newTail = tail + entrySize;
253 } else if (head > entrySize) { // Is there enough room at the beginning?
254 // Wrap around to the beginning, but do not allow the tail to catch
255 // up to the head.
256
257 dataQueue->queue->size = dataSize;
258
259 // We need to make sure that there is enough room to set the size before
260 // doing this. The user client checks for this and will look for the size
261 // at the beginning if there isn't room for it at the end.
262
263 if ((getQueueSize() - tail) >= DATA_QUEUE_ENTRY_HEADER_SIZE) {
264 ((IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail))->size = dataSize;
265 }
266
267 __nochk_memcpy(dst: &dataQueue->queue->data, src: data, n: dataSize);
268 newTail = entrySize;
269 } else {
270 return false; // queue is full
271 }
272 } else {
273 // Do not allow the tail to catch up to the head when the queue is full.
274 // That's why the comparison uses a '>' rather than '>='.
275
276 if ((head - tail) > entrySize) {
277 entry = (IODataQueueEntry *)((UInt8 *)dataQueue->queue + tail);
278
279 entry->size = dataSize;
280 __nochk_memcpy(dst: &entry->data, src: data, n: dataSize);
281 newTail = tail + entrySize;
282 } else {
283 return false; // queue is full
284 }
285 }
286
287 // Publish the data we just enqueued
288 __c11_atomic_store((_Atomic UInt32 *)&dataQueue->tail, newTail, __ATOMIC_RELEASE);
289
290 if (tail != head) {
291 //
292 // The memory barrier below paris with the one in ::dequeue
293 // so that either our store to the tail cannot be missed by
294 // the next dequeue attempt, or we will observe the dequeuer
295 // making the queue empty.
296 //
297 // Of course, if we already think the queue is empty,
298 // there's no point paying this extra cost.
299 //
300 __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
301 head = __c11_atomic_load((_Atomic UInt32 *)&dataQueue->head, __ATOMIC_RELAXED);
302 }
303
304 if (tail == head) {
305 // Send notification (via mach message) that data is now available.
306 sendDataAvailableNotification();
307 }
308 return true;
309}
310
311Boolean
312IOSharedDataQueue::dequeue(void *data, UInt32 *dataSize)
313{
314 Boolean retVal = TRUE;
315 volatile IODataQueueEntry * entry = NULL;
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 volatile IODataQueueEntry * head = NULL;
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 __nochk_memcpy(dst: data, src: (void *)entry->data, n: 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
398IOSharedDataQueue::getQueueSize()
399{
400 if (!_reserved) {
401 return 0;
402 }
403 return _reserved->queueSize;
404}
405
406Boolean
407IOSharedDataQueue::setQueueSize(UInt32 size)
408{
409 if (!_reserved) {
410 return false;
411 }
412 _reserved->queueSize = size;
413 return true;
414}
415
416OSMetaClassDefineReservedUnused(IOSharedDataQueue, 0);
417OSMetaClassDefineReservedUnused(IOSharedDataQueue, 1);
418OSMetaClassDefineReservedUnused(IOSharedDataQueue, 2);
419OSMetaClassDefineReservedUnused(IOSharedDataQueue, 3);
420OSMetaClassDefineReservedUnused(IOSharedDataQueue, 4);
421OSMetaClassDefineReservedUnused(IOSharedDataQueue, 5);
422OSMetaClassDefineReservedUnused(IOSharedDataQueue, 6);
423OSMetaClassDefineReservedUnused(IOSharedDataQueue, 7);
424