1/*
2 * Copyright (c) 2008 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 <sys/appleapiopts.h>
30#include <machine/cpu_capabilities.h>
31#include <machine/commpage.h>
32#include <mach/i386/syscall_sw.h>
33
34
35/* PREEMPTION FREE ZONE (PFZ)
36 *
37 * A portion of the commpage is speacial-cased by the kernel to be "preemption free",
38 * ie as if we had disabled interrupts in user mode.  This facilitates writing
39 * "nearly-lockless" code, for example code that must be serialized by a spinlock but
40 * which we do not want to preempt while the spinlock is held.
41 *
42 * The PFZ is implemented by collecting all the "preemption-free" code into a single
43 * contiguous region of the commpage.  Register %ebx is used as a flag register;
44 * before entering the PFZ, %ebx is cleared.  If some event occurs that would normally
45 * result in a premption while in the PFZ, the kernel sets %ebx nonzero instead of
46 * preempting.  Then, when the routine leaves the PFZ we check %ebx and
47 * if nonzero execute a special "pfz_exit" syscall to take the delayed preemption.
48 *
49 * PFZ code must bound the amount of time spent in the PFZ, in order to control
50 * latency.  Backward branches are dangerous and must not be used in a way that
51 * could inadvertently create a long-running loop.
52 *
53 * Because they cannot be implemented reasonably without a lock, we put the "atomic"
54 * FIFO enqueue and dequeue in the PFZ.  As long as we don't take a page fault trying to
55 * access queue elements, these implementations behave nearly-locklessly.
56 * But we still must take a spinlock to serialize, and in case of page faults.
57 */
58
59/* Work around 10062261 with a dummy non-local symbol */
60fifo_queue_dummy_symbol:
61
62/*
63 *	typedef	volatile struct {
64 *		void	*opaque1;  <-- ptr to first queue element or null
65 *		void	*opaque2;  <-- ptr to last queue element or null
66 *		int	 opaque3;  <-- spinlock
67 *	} OSFifoQueueHead;
68 *
69 * void  OSAtomicFifoEnqueue( OSFifoQueueHead *list, void *new, size_t offset);
70 */
71
72
73/* Subroutine to make a preempt syscall.  Called when we notice %ebx is
74 * nonzero after returning from a PFZ subroutine.
75 * When we enter kernel:
76 *	%edx = return address
77 *	%ecx = stack ptr
78 * Destroys %eax, %ecx, and %edx.
79 */
80COMMPAGE_FUNCTION_START(preempt, 32, 4)
81	popl	%edx		// get return address
82	movl	%esp,%ecx	// save stack ptr here
83	movl	$(-58),%eax	/* 58 = pfz_exit */
84	xorl	%ebx,%ebx	// clear "preemption pending" flag
85	sysenter
86COMMPAGE_DESCRIPTOR(preempt,_COMM_PAGE_PREEMPT)
87
88
89/* Subroutine to back off if we cannot get the spinlock.  Called
90 * after a few attempts inline in the PFZ subroutines.  This code is
91 * not in the PFZ.
92 *	%edi = ptr to queue head structure
93 *	%ebx = preemption flag (nonzero if preemption pending)
94 * Destroys %eax.
95 */
96COMMPAGE_FUNCTION_START(backoff, 32, 4)
97	testl	%ebx,%ebx	// does kernel want to preempt us?
98	jz	1f		// no
99	xorl	%ebx,%ebx	// yes, clear flag
100	pushl	%edx		// preserve regs used by preempt syscall
101	pushl	%ecx
102	COMMPAGE_CALL(_COMM_PAGE_PREEMPT,_COMM_PAGE_BACKOFF,backoff)
103	popl	%ecx
104	popl	%edx
1051:
106	pause			// SMT-friendly backoff
107	cmpl	$0,8(%edi)	// sniff the lockword
108	jnz	1b		// loop if still taken
109	ret			// lockword is free, so reenter PFZ
110COMMPAGE_DESCRIPTOR(backoff,_COMM_PAGE_BACKOFF)
111
112
113/* Preemption-free-zone routine to FIFO Enqueue:
114 *	%edi = ptr to queue head structure
115 *	%esi = ptr to element to enqueue
116 *	%edx = offset of link field in elements
117 *	%ebx = preemption flag (kernel sets nonzero if we should preempt)
118 */
119
120COMMPAGE_FUNCTION_START(pfz_enqueue, 32, 4)
121	movl	    $0,(%edx,%esi)  // zero forward link in new element
1221:
123	xorl	    %eax, %eax
124	orl	    $-1, %ecx
125	lock
126	cmpxchgl    %ecx, 8(%edi)   // try to take the spinlock
127	jz	    2f		    // got it
128
129	pause
130	xorl	    %eax, %eax
131	lock
132	cmpxchgl    %ecx, 8(%edi)   // try 2nd time to take the spinlock
133	jz	    2f		    // got it
134
135	pause
136	xorl	    %eax, %eax
137	lock
138	cmpxchgl    %ecx, 8(%edi)   // try 3rd time to take the spinlock
139	jz	    2f		    // got it
140
141	COMMPAGE_CALL(_COMM_PAGE_BACKOFF,_COMM_PAGE_PFZ_ENQUEUE,pfz_enqueue)
142	jmp	    1b		    // loop to try again
1432:
144	movl	    4(%edi),%ecx    // get ptr to last element in q
145	testl	    %ecx,%ecx	    // q null?
146	jnz	    3f		    // no
147	movl	    %esi,(%edi)	    // q empty so this is first element
148	jmp	    4f
1493:
150	movl	    %esi,(%edx,%ecx) // point to new element from last
1514:
152	movl	    %esi,4(%edi)    // new element becomes last in q
153	movl	    $0,8(%edi)	    // unlock spinlock
154	ret
155COMMPAGE_DESCRIPTOR(pfz_enqueue,_COMM_PAGE_PFZ_ENQUEUE)
156
157
158/* Preemption-free-zone routine to FIFO Dequeue:
159 *	%edi = ptr to queue head structure
160 *	%edx = offset of link field in elements
161 *	%ebx = preemption flag (kernel sets nonzero if we should preempt)
162 *
163 * Returns with next element (or 0) in %eax.
164 */
165
166COMMPAGE_FUNCTION_START(pfz_dequeue, 32, 4)
1671:
168	xorl	    %eax, %eax
169	orl	    $-1, %ecx
170	lock
171	cmpxchgl    %ecx, 8(%edi)   // try to take the spinlock
172	jz	    2f		    // got it
173
174	pause
175	xorl	    %eax, %eax
176	lock
177	cmpxchgl    %ecx, 8(%edi)   // try 2nd time to take the spinlock
178	jz	    2f		    // got it
179
180	pause
181	xorl	    %eax, %eax
182	lock
183	cmpxchgl    %ecx, 8(%edi)   // try 3rd time to take the spinlock
184	jz	    2f		    // got it
185
186	COMMPAGE_CALL(_COMM_PAGE_BACKOFF,_COMM_PAGE_PFZ_DEQUEUE,pfz_dequeue)
187	jmp	    1b		    // loop to try again
1882:
189	movl	    (%edi),%eax	    // get ptr to first element in q
190	testl	    %eax,%eax	    // q null?
191	jz	    4f		    // yes
192	movl	    (%edx,%eax),%esi// get ptr to 2nd element in q
193	testl	    %esi,%esi	    // is there a 2nd element?
194	jnz	    3f		    // yes
195	movl	    %esi,4(%edi)    // clear "last" field of q head
1963:
197	movl	    %esi,(%edi)	    // update "first" field of q head
1984:
199	movl	    $0,8(%edi)	    // unlock spinlock
200	ret
201COMMPAGE_DESCRIPTOR(pfz_dequeue,_COMM_PAGE_PFZ_DEQUEUE)
202
203
204
205
206/************************* x86_64 versions follow **************************/
207
208
209/*
210 *	typedef	volatile struct {
211 *		void	*opaque1;  <-- ptr to first queue element or null
212 *		void	*opaque2;  <-- ptr to last queue element or null
213 *		int	 opaque3;  <-- spinlock
214 *	} OSFifoQueueHead;
215 *
216 * void  OSAtomicFifoEnqueue( OSFifoQueueHead *list, void *new, size_t offset);
217 */
218
219
220/* Subroutine to make a preempt syscall.  Called when we notice %ebx is
221 * nonzero after returning from a PFZ subroutine.  Not in PFZ.
222 *
223 * All registers preserved (but does clear the %ebx preemption flag).
224 */
225COMMPAGE_FUNCTION_START(preempt_64, 64, 4)
226	pushq	%rax
227	pushq	%rcx
228	pushq	%r11
229	movl	$(SYSCALL_CONSTRUCT_MACH(58)),%eax	/* 58 = pfz_exit */
230	xorl	%ebx,%ebx
231	syscall
232	popq	%r11
233	popq	%rcx
234	popq	%rax
235	ret
236COMMPAGE_DESCRIPTOR(preempt_64,_COMM_PAGE_PREEMPT)
237
238
239/* Subroutine to back off if we cannot get the spinlock.  Called
240 * after a few attempts inline in the PFZ subroutines.  This code is
241 * not in the PFZ.
242 *	%rdi = ptr to queue head structure
243 *	%ebx = preemption flag (nonzero if preemption pending)
244 * Uses: %rax.
245 */
246COMMPAGE_FUNCTION_START(backoff_64, 64, 4)
247	testl	%ebx,%ebx	// does kernel want to preempt us?
248	jz	1f		// no
249	COMMPAGE_CALL(_COMM_PAGE_PREEMPT,_COMM_PAGE_BACKOFF,backoff_64)
2501:
251	pause			// SMT-friendly backoff
252	cmpl	$0,16(%rdi)	// sniff the lockword
253	jnz	1b		// loop if still taken
254	ret			// lockword is free, so reenter PFZ
255COMMPAGE_DESCRIPTOR(backoff_64,_COMM_PAGE_BACKOFF)
256
257
258/* Preemption-free-zone routine to FIFO Enqueue:
259 *	%rdi = ptr to queue head structure
260 *	%rsi = ptr to new element to enqueue
261 *	%rdx = offset of link field in elements
262 *	%ebx = preemption flag (kernel sets nonzero if we should preempt)
263 */
264
265COMMPAGE_FUNCTION_START(pfz_enqueue_64, 64, 4)
266	movq	    $0,(%rdx,%rsi)  // zero forward link in new element
2671:
268	xorl	    %eax, %eax
269	orl	    $-1, %ecx
270	lock
271	cmpxchgl    %ecx,16(%rdi)   // try to take the spinlock
272	jz	    2f		    // got it
273
274	pause
275	xorl	    %eax, %eax
276	lock
277	cmpxchgl    %ecx,16(%rdi)   // try 2nd time to take the spinlock
278	jz	    2f		    // got it
279
280	pause
281	xorl	    %eax, %eax
282	lock
283	cmpxchgl    %ecx,16(%rdi)   // try 3rd time to take the spinlock
284	jz	    2f		    // got it
285
286	COMMPAGE_CALL(_COMM_PAGE_BACKOFF,_COMM_PAGE_PFZ_ENQUEUE,pfz_enqueue_64)
287	jmp	    1b		    // loop to try again
2882:
289	movq	    8(%rdi),%rcx    // get ptr to last element in q
290	testq	    %rcx,%rcx	    // q null?
291	jnz	    3f		    // no
292	movq	    %rsi,(%rdi)	    // q empty so this is first element
293	jmp	    4f
2943:
295	movq	    %rsi,(%rdx,%rcx) // point to new element from last
2964:
297	movq	    %rsi,8(%rdi)    // new element becomes last in q
298	movl	    $0,16(%rdi)	    // unlock spinlock
299	ret
300COMMPAGE_DESCRIPTOR(pfz_enqueue_64,_COMM_PAGE_PFZ_ENQUEUE)
301
302
303
304/* Preemption-free-zone routine to FIFO Dequeue:
305 *	%rdi = ptr to queue head structure
306 *	%rdx = offset of link field in elements
307 *	%ebx = preemption flag (kernel sets nonzero if we should preempt)
308 *
309 * Returns with next element (or 0) in %rax.
310 */
311
312COMMPAGE_FUNCTION_START(pfz_dequeue_64, 64, 4)
3131:
314	xorl	    %eax, %eax
315	orl	    $-1, %ecx
316	lock
317	cmpxchgl    %ecx,16(%rdi)   // try to take the spinlock
318	jz	    2f		    // got it
319
320	pause
321	xorl	    %eax, %eax
322	lock
323	cmpxchgl    %ecx,16(%rdi)   // try 2nd time to take the spinlock
324	jz	    2f		    // got it
325
326	pause
327	xorl	    %eax, %eax
328	lock
329	cmpxchgl    %ecx,16(%rdi)   // try 3rd time to take the spinlock
330	jz	    2f		    // got it
331
332	COMMPAGE_CALL(_COMM_PAGE_BACKOFF,_COMM_PAGE_PFZ_DEQUEUE,pfz_dequeue_64)
333	jmp	    1b		    // loop to try again
3342:
335	movq	    (%rdi),%rax	    // get ptr to first element in q
336	testq	    %rax,%rax	    // q null?
337	jz	    4f		    // yes
338	movq	    (%rdx,%rax),%rsi// get ptr to 2nd element in q
339	testq	    %rsi,%rsi	    // is there a 2nd element?
340	jnz	    3f		    // yes
341	movq	    %rsi,8(%rdi)    // no - clear "last" field of q head
3423:
343	movq	    %rsi,(%rdi)	    // update "first" field of q head
3444:
345	movl	    $0,16(%rdi)	    // unlock spinlock
346	ret
347COMMPAGE_DESCRIPTOR(pfz_dequeue_64,_COMM_PAGE_PFZ_DEQUEUE)
348