/* * Copyright (c) 2005 Hewlett-Packard Development Company, L.P. * * This file may be redistributed and/or modified under the * terms of the GNU General Public License as published by the Free Software * Foundation; either version 2, or (at your option) any later version. * * It is distributed in the hope that it will be useful, but WITHOUT ANY * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS * FOR A PARTICULAR PURPOSE. See the GNU General Public License in the * file COPYING for more details. */ #if defined(HAVE_CONFIG_H) # include "config.h" #endif #include #if defined(__vxworks) int main(void) { printf("test skipped\n"); return 0; } #else #if ((defined(_WIN32) && !defined(__CYGWIN32__) && !defined(__CYGWIN__)) \ || defined(_MSC_VER) || defined(_WIN32_WINCE)) \ && !defined(AO_USE_WIN32_PTHREADS) # define USE_WINTHREADS #endif #ifdef USE_WINTHREADS # include #else # include #endif #include #include "atomic_ops_stack.h" /* includes atomic_ops.h as well */ #if (defined(_WIN32_WCE) || defined(__MINGW32CE__)) && !defined(AO_HAVE_abort) # define abort() _exit(-1) /* there is no abort() in WinCE */ #endif #ifndef MAX_NTHREADS # define MAX_NTHREADS 100 #endif #ifndef DEFAULT_NTHREADS # define DEFAULT_NTHREADS 16 /* must be <= MAX_NTHREADS */ #endif #ifdef NO_TIMES # define get_msecs() 0 #elif (defined(USE_WINTHREADS) || defined(AO_USE_WIN32_PTHREADS)) \ && !defined(CPPCHECK) # include unsigned long get_msecs(void) { struct timeb tb; ftime(&tb); return (unsigned long)tb.time * 1000 + tb.millitm; } #else /* Unix */ # include # include unsigned long get_msecs(void) { struct timeval tv; gettimeofday(&tv, 0); return (unsigned long)tv.tv_sec * 1000 + tv.tv_usec/1000; } #endif /* !NO_TIMES */ typedef struct le { AO_t next; int data; } list_element; AO_stack_t the_list = AO_STACK_INITIALIZER; void add_elements(int n) { list_element * le; if (n == 0) return; add_elements(n-1); le = malloc(sizeof(list_element)); if (le == 0) { fprintf(stderr, "Out of memory\n"); exit(2); } le -> data = n; AO_stack_push(&the_list, (AO_t *)le); } #ifdef VERBOSE void print_list(void) { list_element *p; for (p = (list_element *)AO_REAL_HEAD_PTR(the_list); p != 0; p = (list_element *)AO_REAL_NEXT_PTR(p -> next)) printf("%d\n", p -> data); } #endif /* VERBOSE */ static char marks[MAX_NTHREADS * (MAX_NTHREADS + 1) / 2 + 1]; void check_list(int n) { list_element *p; int i; for (i = 1; i <= n; ++i) marks[i] = 0; for (p = (list_element *)AO_REAL_HEAD_PTR(the_list); p != 0; p = (list_element *)AO_REAL_NEXT_PTR(p -> next)) { i = p -> data; if (i > n || i <= 0) { fprintf(stderr, "Found erroneous list element %d\n", i); abort(); } if (marks[i] != 0) { fprintf(stderr, "Found duplicate list element %d\n", i); abort(); } marks[i] = 1; } for (i = 1; i <= n; ++i) if (marks[i] != 1) { fprintf(stderr, "Missing list element %d\n", i); abort(); } } volatile AO_t ops_performed = 0; #ifndef LIMIT /* Total number of push/pop ops in all threads per test. */ # ifdef AO_USE_PTHREAD_DEFS # define LIMIT 20000 # else # define LIMIT 1000000 # endif #endif #ifdef AO_HAVE_fetch_and_add # define fetch_and_add(addr, val) AO_fetch_and_add(addr, val) #else /* Fake it. This is really quite unacceptable for timing */ /* purposes. But as a correctness test, it should be OK. */ AO_INLINE AO_t fetch_and_add(volatile AO_t * addr, AO_t val) { AO_t result = AO_load(addr); AO_store(addr, result + val); return result; } #endif #ifdef USE_WINTHREADS DWORD WINAPI run_one_test(LPVOID arg) #else void * run_one_test(void * arg) #endif { list_element * t[MAX_NTHREADS + 1]; int index = (int)(size_t)arg; int i; # ifdef VERBOSE int j = 0; printf("starting thread %d\n", index); # endif while (fetch_and_add(&ops_performed, index + 1) + index + 1 < LIMIT) { for (i = 0; i < index + 1; ++i) { t[i] = (list_element *)AO_stack_pop(&the_list); if (0 == t[i]) { fprintf(stderr, "FAILED\n"); abort(); } } for (i = 0; i < index + 1; ++i) { AO_stack_push(&the_list, (AO_t *)t[i]); } # ifdef VERBOSE j += index + 1; # endif } # ifdef VERBOSE printf("finished thread %d: %d total ops\n", index, j); # endif return 0; } #ifndef N_EXPERIMENTS # define N_EXPERIMENTS 1 #endif unsigned long times[MAX_NTHREADS + 1][N_EXPERIMENTS]; int main(int argc, char **argv) { int nthreads; int max_nthreads; int exper_n; if (1 == argc) { max_nthreads = DEFAULT_NTHREADS; assert(max_nthreads <= MAX_NTHREADS); } else if (2 == argc) { max_nthreads = atoi(argv[1]); if (max_nthreads < 1 || max_nthreads > MAX_NTHREADS) { fprintf(stderr, "Invalid max # of threads argument\n"); exit(1); } } else { fprintf(stderr, "Usage: %s [max # of threads]\n", argv[0]); exit(1); } for (exper_n = 0; exper_n < N_EXPERIMENTS; ++ exper_n) for (nthreads = 1; nthreads <= max_nthreads; ++nthreads) { int i; # ifdef USE_WINTHREADS DWORD thread_id; HANDLE thread[MAX_NTHREADS]; # else pthread_t thread[MAX_NTHREADS]; # endif int list_length = nthreads*(nthreads+1)/2; unsigned long start_time; list_element * le; # ifdef VERBOSE printf("Before add_elements: exper_n=%d, nthreads=%d," " max_nthreads=%d, list_length=%d\n", exper_n, nthreads, max_nthreads, list_length); # endif add_elements(list_length); # ifdef VERBOSE printf("Initial list (nthreads = %d):\n", nthreads); print_list(); # endif ops_performed = 0; start_time = get_msecs(); for (i = 1; i < nthreads; ++i) { int code; # ifdef USE_WINTHREADS thread[i] = CreateThread(NULL, 0, run_one_test, (LPVOID)(size_t)i, 0, &thread_id); code = thread[i] != NULL ? 0 : (int)GetLastError(); # else code = pthread_create(&thread[i], 0, run_one_test, (void *)(size_t)i); # endif if (code != 0) { fprintf(stderr, "Thread creation failed %u\n", (unsigned)code); exit(3); } } /* We use the main thread to run one test. This allows gprof */ /* profiling to work, for example. */ run_one_test(0); for (i = 1; i < nthreads; ++i) { int code; # ifdef USE_WINTHREADS code = WaitForSingleObject(thread[i], INFINITE) == WAIT_OBJECT_0 ? 0 : (int)GetLastError(); # else code = pthread_join(thread[i], 0); # endif if (code != 0) { fprintf(stderr, "Thread join failed %u\n", (unsigned)code); abort(); } } times[nthreads][exper_n] = get_msecs() - start_time; # ifdef VERBOSE printf("nthreads=%d, time_ms=%lu\n", nthreads, times[nthreads][exper_n]); printf("final list (should be reordered initial list):\n"); print_list(); # endif check_list(list_length); while ((le = (list_element *)AO_stack_pop(&the_list)) != 0) free(le); } for (nthreads = 1; nthreads <= max_nthreads; ++nthreads) { # ifndef NO_TIMES unsigned long sum = 0; # endif printf("About %d pushes + %d pops in %d threads:", LIMIT, LIMIT, nthreads); # ifndef NO_TIMES for (exper_n = 0; exper_n < N_EXPERIMENTS; ++exper_n) { # ifdef VERBOSE printf(" [%lums]", times[nthreads][exper_n]); # endif sum += times[nthreads][exper_n]; } printf(" %lu msecs\n", (sum + N_EXPERIMENTS/2)/N_EXPERIMENTS); # else printf(" completed\n"); # endif } return 0; } #endif