1/*
2 * Copyright (C) 2010 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*
18 * This provides a handful of correctness and speed tests on our atomic
19 * operations.
20 *
21 * This doesn't really belong here, but we currently lack a better place
22 * for it, so this will do for now.
23 */
24#include "Dalvik.h"
25
26#include <stdlib.h>
27#include <stdio.h>
28#include <pthread.h>
29#include <unistd.h>
30#include <cutils/atomic.h>
31#ifdef __arm__
32# include <machine/cpu-features.h>
33#endif
34
35#define USE_ATOMIC      1
36#define THREAD_COUNT    10
37#define ITERATION_COUNT 500000
38
39#ifdef HAVE_ANDROID_OS
40/*#define TEST_BIONIC 1*/
41#endif
42
43
44#ifdef TEST_BIONIC
45extern int __atomic_cmpxchg(int old, int _new, volatile int *ptr);
46extern int __atomic_swap(int _new, volatile int *ptr);
47extern int __atomic_dec(volatile int *ptr);
48extern int __atomic_inc(volatile int *ptr);
49#endif
50
51static pthread_mutex_t waitLock = PTHREAD_MUTEX_INITIALIZER;
52static pthread_cond_t waitCond = PTHREAD_COND_INITIALIZER;
53
54static volatile int threadsStarted = 0;
55
56/* results */
57static int incTest = 0;
58static int decTest = 0;
59static int addTest = 0;
60static int andTest = 0;
61static int orTest = 0;
62static int casTest = 0;
63static int failingCasTest = 0;
64static int64_t wideCasTest = 0x6600000077000000LL;
65
66/*
67 * Get a relative time value.
68 */
69static int64_t getRelativeTimeNsec()
70{
71#define HAVE_POSIX_CLOCKS
72#ifdef HAVE_POSIX_CLOCKS
73    struct timespec now;
74    clock_gettime(CLOCK_MONOTONIC, &now);
75    return (int64_t) now.tv_sec*1000000000LL + now.tv_nsec;
76#else
77    struct timeval now;
78    gettimeofday(&now, NULL);
79    return (int64_t) now.tv_sec*1000000000LL + now.tv_usec * 1000LL;
80#endif
81}
82
83
84/*
85 * Non-atomic implementations, for comparison.
86 *
87 * If these get inlined the compiler may figure out what we're up to and
88 * completely elide the operations.
89 */
90static void incr() __attribute__((noinline));
91static void decr() __attribute__((noinline));
92static void add(int addVal) __attribute__((noinline));
93static int compareAndSwap(int oldVal, int newVal, int* addr) __attribute__((noinline));
94static int compareAndSwapWide(int64_t oldVal, int64_t newVal, int64_t* addr) __attribute__((noinline));
95
96static void incr()
97{
98    incTest++;
99}
100static void decr()
101{
102    decTest--;
103}
104static void add(int32_t addVal)
105{
106    addTest += addVal;
107}
108static int compareAndSwap(int32_t oldVal, int32_t newVal, int32_t* addr)
109{
110    if (*addr == oldVal) {
111        *addr = newVal;
112        return 0;
113    }
114    return 1;
115}
116static int compareAndSwapWide(int64_t oldVal, int64_t newVal, int64_t* addr)
117{
118    if (*addr == oldVal) {
119        *addr = newVal;
120        return 0;
121    }
122    return 1;
123}
124
125/*
126 * Exercise several of the atomic ops.
127 */
128static void doAtomicTest(int num)
129{
130    int addVal = (num & 0x01) + 1;
131
132    int i;
133    for (i = 0; i < ITERATION_COUNT; i++) {
134        if (USE_ATOMIC) {
135            android_atomic_inc(&incTest);
136            android_atomic_dec(&decTest);
137            android_atomic_add(addVal, &addTest);
138
139            int val;
140            do {
141                val = casTest;
142            } while (android_atomic_release_cas(val, val+3, &casTest) != 0);
143            do {
144                val = casTest;
145            } while (android_atomic_acquire_cas(val, val-1, &casTest) != 0);
146
147            int64_t wval;
148            do {
149                wval = dvmQuasiAtomicRead64(&wideCasTest);
150            } while (dvmQuasiAtomicCas64(wval,
151                        wval + 0x0000002000000001LL, &wideCasTest) != 0);
152            do {
153                wval = dvmQuasiAtomicRead64(&wideCasTest);
154            } while (dvmQuasiAtomicCas64(wval,
155                        wval - 0x0000002000000001LL, &wideCasTest) != 0);
156        } else {
157            incr();
158            decr();
159            add(addVal);
160
161            int val;
162            do {
163                val = casTest;
164            } while (compareAndSwap(val, val+3, &casTest) != 0);
165            do {
166                val = casTest;
167            } while (compareAndSwap(val, val-1, &casTest) != 0);
168
169            int64_t wval;
170            do {
171                wval = wideCasTest;
172            } while (compareAndSwapWide(wval,
173                        wval + 0x0000002000000001LL, &wideCasTest) != 0);
174            do {
175                wval = wideCasTest;
176            } while (compareAndSwapWide(wval,
177                        wval - 0x0000002000000001LL, &wideCasTest) != 0);
178        }
179    }
180}
181
182/*
183 * Entry point for multi-thread test.
184 */
185static void* atomicTest(void* arg)
186{
187    pthread_mutex_lock(&waitLock);
188    threadsStarted++;
189    pthread_cond_wait(&waitCond, &waitLock);
190    pthread_mutex_unlock(&waitLock);
191
192    doAtomicTest((int) arg);
193
194    return NULL;
195}
196
197/* lifted from a VM test */
198static int64_t testAtomicSpeedSub(int repeatCount)
199{
200    static int value = 7;
201    int* valuePtr = &value;
202    int64_t start, end;
203    int i;
204
205    start = getRelativeTimeNsec();
206
207    for (i = repeatCount / 10; i != 0; i--) {
208        if (USE_ATOMIC) {
209            // succeed 10x
210            android_atomic_release_cas(7, 7, valuePtr);
211            android_atomic_release_cas(7, 7, valuePtr);
212            android_atomic_release_cas(7, 7, valuePtr);
213            android_atomic_release_cas(7, 7, valuePtr);
214            android_atomic_release_cas(7, 7, valuePtr);
215            android_atomic_release_cas(7, 7, valuePtr);
216            android_atomic_release_cas(7, 7, valuePtr);
217            android_atomic_release_cas(7, 7, valuePtr);
218            android_atomic_release_cas(7, 7, valuePtr);
219            android_atomic_release_cas(7, 7, valuePtr);
220        } else {
221            // succeed 10x
222            compareAndSwap(7, 7, valuePtr);
223            compareAndSwap(7, 7, valuePtr);
224            compareAndSwap(7, 7, valuePtr);
225            compareAndSwap(7, 7, valuePtr);
226            compareAndSwap(7, 7, valuePtr);
227            compareAndSwap(7, 7, valuePtr);
228            compareAndSwap(7, 7, valuePtr);
229            compareAndSwap(7, 7, valuePtr);
230            compareAndSwap(7, 7, valuePtr);
231            compareAndSwap(7, 7, valuePtr);
232        }
233    }
234
235    end = getRelativeTimeNsec();
236
237    dvmFprintf(stdout, ".");
238    fflush(stdout);
239    return end - start;
240}
241
242static void testAtomicSpeed()
243{
244    static const int kIterations = 10;
245    static const int kRepeatCount = 5 * 1000 * 1000;
246    static const int kDelay = 50 * 1000;
247    int64_t results[kIterations];
248    int i;
249
250    for (i = 0; i < kIterations; i++) {
251        results[i] = testAtomicSpeedSub(kRepeatCount);
252        usleep(kDelay);
253    }
254
255    dvmFprintf(stdout, "\n");
256    dvmFprintf(stdout, "%s speed test results (%d per iteration):\n",
257        USE_ATOMIC ? "Atomic" : "Non-atomic", kRepeatCount);
258    for (i = 0; i < kIterations; i++) {
259        dvmFprintf(stdout,
260            " %2d: %.3fns\n", i, (double) results[i] / kRepeatCount);
261    }
262}
263
264/*
265 * Start tests, show results.
266 */
267bool dvmTestAtomicSpeed()
268{
269    pthread_t threads[THREAD_COUNT];
270    void *(*startRoutine)(void*) = atomicTest;
271    int64_t startWhen, endWhen;
272
273#if defined(__ARM_ARCH__)
274    dvmFprintf(stdout, "__ARM_ARCH__ is %d\n", __ARM_ARCH__);
275#endif
276#if defined(ANDROID_SMP)
277    dvmFprintf(stdout, "ANDROID_SMP is %d\n", ANDROID_SMP);
278#endif
279    dvmFprintf(stdout, "Creating threads\n");
280
281    int i;
282    for (i = 0; i < THREAD_COUNT; i++) {
283        void* arg = (void*) i;
284        if (pthread_create(&threads[i], NULL, startRoutine, arg) != 0) {
285            dvmFprintf(stderr, "thread create failed\n");
286        }
287    }
288
289    /* wait for all the threads to reach the starting line */
290    while (1) {
291        pthread_mutex_lock(&waitLock);
292        if (threadsStarted == THREAD_COUNT) {
293            dvmFprintf(stdout, "Starting test\n");
294            startWhen = getRelativeTimeNsec();
295            pthread_cond_broadcast(&waitCond);
296            pthread_mutex_unlock(&waitLock);
297            break;
298        }
299        pthread_mutex_unlock(&waitLock);
300        usleep(100000);
301    }
302
303    for (i = 0; i < THREAD_COUNT; i++) {
304        void* retval;
305        if (pthread_join(threads[i], &retval) != 0) {
306            dvmFprintf(stderr, "thread join (%d) failed\n", i);
307        }
308    }
309
310    endWhen = getRelativeTimeNsec();
311    dvmFprintf(stdout, "All threads stopped, time is %.6fms\n",
312        (endWhen - startWhen) / 1000000.0);
313
314    /*
315     * Show results; expecting:
316     *
317     * incTest = 5000000
318     * decTest = -5000000
319     * addTest = 7500000
320     * casTest = 10000000
321     * wideCasTest = 0x6600000077000000
322     */
323    dvmFprintf(stdout, "incTest = %d\n", incTest);
324    dvmFprintf(stdout, "decTest = %d\n", decTest);
325    dvmFprintf(stdout, "addTest = %d\n", addTest);
326    dvmFprintf(stdout, "casTest = %d\n", casTest);
327    dvmFprintf(stdout, "wideCasTest = 0x%llx\n", wideCasTest);
328
329    /* do again, serially (SMP check) */
330    startWhen = getRelativeTimeNsec();
331    for (i = 0; i < THREAD_COUNT; i++) {
332        doAtomicTest(i);
333    }
334    endWhen = getRelativeTimeNsec();
335    dvmFprintf(stdout, "Same iterations done serially: time is %.6fms\n",
336        (endWhen - startWhen) / 1000000.0);
337
338    /*
339     * Hard to do a meaningful thrash test on these, so just do a simple
340     * function test.
341     */
342    andTest = 0xffd7fa96;
343    orTest = 0x122221ff;
344    android_atomic_and(0xfffdaf96, &andTest);
345    android_atomic_or(0xdeaaeb00, &orTest);
346    if (android_atomic_release_cas(failingCasTest+1, failingCasTest-1,
347            &failingCasTest) == 0)
348        dvmFprintf(stdout, "failing test did not fail!\n");
349
350    dvmFprintf(stdout, "andTest = %#x\n", andTest);
351    dvmFprintf(stdout, "orTest = %#x\n", orTest);
352    dvmFprintf(stdout, "failingCasTest = %d\n", failingCasTest);
353
354#ifdef TEST_BIONIC
355    /*
356     * Quick function test on the bionic ops.
357     */
358    int prev;
359    int tester = 7;
360    prev = __atomic_inc(&tester);
361    __atomic_inc(&tester);
362    __atomic_inc(&tester);
363    dvmFprintf(stdout, "bionic 3 inc: %d -> %d\n", prev, tester);
364    prev = __atomic_dec(&tester);
365    __atomic_dec(&tester);
366    __atomic_dec(&tester);
367    dvmFprintf(stdout, "bionic 3 dec: %d -> %d\n", prev, tester);
368    prev = __atomic_swap(27, &tester);
369    dvmFprintf(stdout, "bionic swap: %d -> %d\n", prev, tester);
370    int swapok = __atomic_cmpxchg(27, 72, &tester);
371    dvmFprintf(stdout, "bionic cmpxchg: %d (%d)\n", tester, swapok);
372#endif
373
374    testAtomicSpeed();
375
376    return 0;
377}
378