1 /*
2 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
3 *
4 * This file may be redistributed and/or modified under the
5 * terms of the GNU General Public License as published by the Free Software
6 * Foundation; either version 2, or (at your option) any later version.
7 *
8 * It is distributed in the hope that it will be useful, but WITHOUT ANY
9 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
10 * FOR A PARTICULAR PURPOSE. See the GNU General Public License in the
11 * file COPYING for more details.
12 */
13
14 #if defined(HAVE_CONFIG_H)
15 # include "config.h"
16 #endif
17
18 #include <stdio.h>
19
20 #if defined(__vxworks)
21
main(void)22 int main(void)
23 {
24 printf("test skipped\n");
25 return 0;
26 }
27
28 #else
29
30 #if ((defined(_WIN32) && !defined(__CYGWIN32__) && !defined(__CYGWIN__)) \
31 || defined(_MSC_VER) || defined(_WIN32_WINCE)) \
32 && !defined(AO_USE_WIN32_PTHREADS)
33 # define USE_WINTHREADS
34 #endif
35
36 #ifdef USE_WINTHREADS
37 # include <windows.h>
38 #else
39 # include <pthread.h>
40 #endif
41
42 #include <stdlib.h>
43
44 #include "atomic_ops_stack.h" /* includes atomic_ops.h as well */
45
46 #if (defined(_WIN32_WCE) || defined(__MINGW32CE__)) && !defined(abort)
47 # define abort() _exit(-1) /* there is no abort() in WinCE */
48 #endif
49
50 #ifndef MAX_NTHREADS
51 # define MAX_NTHREADS 100
52 #endif
53
54 #ifdef NO_TIMES
55 # define get_msecs() 0
56 #elif defined(USE_WINTHREADS) || defined(AO_USE_WIN32_PTHREADS)
57 # include <sys/timeb.h>
get_msecs(void)58 long long get_msecs(void)
59 {
60 struct timeb tb;
61
62 ftime(&tb);
63 return (long long)tb.time * 1000 + tb.millitm;
64 }
65 #else /* Unix */
66 # include <time.h>
67 # include <sys/time.h>
68 /* Need 64-bit long long support */
get_msecs(void)69 long long get_msecs(void)
70 {
71 struct timeval tv;
72
73 gettimeofday(&tv, 0);
74 return (long long)tv.tv_sec * 1000 + tv.tv_usec/1000;
75 }
76 #endif /* !NO_TIMES */
77
78 typedef struct le {
79 AO_t next;
80 int data;
81 } list_element;
82
83 AO_stack_t the_list = AO_STACK_INITIALIZER;
84
add_elements(int n)85 void add_elements(int n)
86 {
87 list_element * le;
88 if (n == 0) return;
89 add_elements(n-1);
90 le = malloc(sizeof(list_element));
91 if (le == 0)
92 {
93 fprintf(stderr, "Out of memory\n");
94 exit(2);
95 }
96 le -> data = n;
97 AO_stack_push(&the_list, (AO_t *)le);
98 }
99
print_list(void)100 void print_list(void)
101 {
102 list_element *p;
103
104 for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
105 p != 0;
106 p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
107 printf("%d\n", p -> data);
108 }
109
110 static char marks[MAX_NTHREADS * (MAX_NTHREADS + 1) / 2 + 1];
111
check_list(int n)112 void check_list(int n)
113 {
114 list_element *p;
115 int i;
116
117 for (i = 1; i <= n; ++i) marks[i] = 0;
118
119 for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
120 p != 0;
121 p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
122 {
123 i = p -> data;
124 if (i > n || i <= 0)
125 {
126 fprintf(stderr, "Found erroneous list element %d\n", i);
127 abort();
128 }
129 if (marks[i] != 0)
130 {
131 fprintf(stderr, "Found duplicate list element %d\n", i);
132 abort();
133 }
134 marks[i] = 1;
135 }
136
137 for (i = 1; i <= n; ++i)
138 if (marks[i] != 1)
139 {
140 fprintf(stderr, "Missing list element %d\n", i);
141 abort();
142 }
143 }
144
145 volatile AO_t ops_performed = 0;
146
147 #ifndef LIMIT
148 /* Total number of push/pop ops in all threads per test. */
149 # ifdef AO_USE_PTHREAD_DEFS
150 # define LIMIT 20000
151 # else
152 # define LIMIT 1000000
153 # endif
154 #endif
155
156 #ifdef AO_HAVE_fetch_and_add
157 # define fetch_and_add(addr, val) AO_fetch_and_add(addr, val)
158 #else
159 /* Fake it. This is really quite unacceptable for timing */
160 /* purposes. But as a correctness test, it should be OK. */
fetch_and_add(volatile AO_t * addr,AO_t val)161 AO_INLINE AO_t fetch_and_add(volatile AO_t * addr, AO_t val)
162 {
163 AO_t result = AO_load(addr);
164 AO_store(addr, result + val);
165 return result;
166 }
167 #endif
168
169 #ifdef USE_WINTHREADS
run_one_test(LPVOID arg)170 DWORD WINAPI run_one_test(LPVOID arg)
171 #else
172 void * run_one_test(void * arg)
173 #endif
174 {
175 list_element * t[MAX_NTHREADS + 1];
176 int index = (int)(size_t)arg;
177 int i;
178 # ifdef VERBOSE
179 int j = 0;
180
181 printf("starting thread %d\n", index);
182 # endif
183 while (fetch_and_add(&ops_performed, index + 1) + index + 1 < LIMIT)
184 {
185 for (i = 0; i < index + 1; ++i)
186 {
187 t[i] = (list_element *)AO_stack_pop(&the_list);
188 if (0 == t[i])
189 {
190 fprintf(stderr, "FAILED\n");
191 abort();
192 }
193 }
194 for (i = 0; i < index + 1; ++i)
195 {
196 AO_stack_push(&the_list, (AO_t *)t[i]);
197 }
198 # ifdef VERBOSE
199 j += index + 1;
200 # endif
201 }
202 # ifdef VERBOSE
203 printf("finished thread %d: %d total ops\n", index, j);
204 # endif
205 return 0;
206 }
207
208 #ifndef N_EXPERIMENTS
209 # define N_EXPERIMENTS 1
210 #endif
211
212 unsigned long times[MAX_NTHREADS + 1][N_EXPERIMENTS];
213
main(int argc,char ** argv)214 int main(int argc, char **argv)
215 {
216 int nthreads;
217 int max_nthreads;
218 int exper_n;
219
220 if (1 == argc)
221 max_nthreads = 4;
222 else if (2 == argc)
223 {
224 max_nthreads = atoi(argv[1]);
225 if (max_nthreads < 1 || max_nthreads > MAX_NTHREADS)
226 {
227 fprintf(stderr, "Invalid max # of threads argument\n");
228 exit(1);
229 }
230 }
231 else
232 {
233 fprintf(stderr, "Usage: %s [max # of threads]\n", argv[0]);
234 exit(1);
235 }
236 for (exper_n = 0; exper_n < N_EXPERIMENTS; ++ exper_n)
237 for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
238 {
239 int i;
240 # ifdef USE_WINTHREADS
241 DWORD thread_id;
242 HANDLE thread[MAX_NTHREADS];
243 # else
244 pthread_t thread[MAX_NTHREADS];
245 # endif
246 int list_length = nthreads*(nthreads+1)/2;
247 long long start_time;
248 list_element * le;
249
250 # ifdef VERBOSE
251 printf("Before add_elements: exper_n=%d, nthreads=%d,"
252 " max_nthreads=%d, list_length=%d\n",
253 exper_n, nthreads, max_nthreads, list_length);
254 # endif
255 add_elements(list_length);
256 # ifdef VERBOSE
257 printf("Initial list (nthreads = %d):\n", nthreads);
258 print_list();
259 # endif
260 ops_performed = 0;
261 start_time = get_msecs();
262 for (i = 1; i < nthreads; ++i) {
263 int code;
264
265 # ifdef USE_WINTHREADS
266 thread[i] = CreateThread(NULL, 0, run_one_test, (LPVOID)(size_t)i,
267 0, &thread_id);
268 code = thread[i] != NULL ? 0 : (int)GetLastError();
269 # else
270 code = pthread_create(&thread[i], 0, run_one_test,
271 (void *)(size_t)i);
272 # endif
273 if (code != 0) {
274 fprintf(stderr, "Thread creation failed %u\n", (unsigned)code);
275 exit(3);
276 }
277 }
278 /* We use the main thread to run one test. This allows gprof */
279 /* profiling to work, for example. */
280 run_one_test(0);
281 for (i = 1; i < nthreads; ++i) {
282 int code;
283
284 # ifdef USE_WINTHREADS
285 code = WaitForSingleObject(thread[i], INFINITE) == WAIT_OBJECT_0 ?
286 0 : (int)GetLastError();
287 # else
288 code = pthread_join(thread[i], 0);
289 # endif
290 if (code != 0) {
291 fprintf(stderr, "Thread join failed %u\n", (unsigned)code);
292 abort();
293 }
294 }
295 times[nthreads][exper_n] = (unsigned long)(get_msecs() - start_time);
296 # ifdef VERBOSE
297 printf("%d %lu\n", nthreads,
298 (unsigned long)(get_msecs() - start_time));
299 printf("final list (should be reordered initial list):\n");
300 print_list();
301 # endif
302 check_list(list_length);
303 while ((le = (list_element *)AO_stack_pop(&the_list)) != 0)
304 free(le);
305 }
306 for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
307 {
308 # ifndef NO_TIMES
309 unsigned long sum = 0;
310 # endif
311
312 printf("About %d pushes + %d pops in %d threads:",
313 LIMIT, LIMIT, nthreads);
314 # ifndef NO_TIMES
315 for (exper_n = 0; exper_n < N_EXPERIMENTS; ++exper_n) {
316 # if defined(VERBOSE)
317 printf(" [%lu]", times[nthreads][exper_n]);
318 # endif
319 sum += times[nthreads][exper_n];
320 }
321 printf(" %lu msecs\n", (sum + N_EXPERIMENTS/2)/N_EXPERIMENTS);
322 # else
323 printf(" completed\n");
324 # endif
325 }
326 return 0;
327 }
328
329 #endif
330