gc-7.2/libatomic_ops/tests/test_stack.c

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