src/mm/boehm-gc/libatomic_ops-1.2/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 #include <pthread.h>
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22 #include "atomic_ops.h"
  23 #include "atomic_ops_stack.h"
  24 #define MAX_NTHREADS 100
  25
  26 #ifndef NO_TIMES
  27 #include <time.h>
  28 #include <sys/time.h>
  29 /* Need 64-bit long long support */
  30 long long
  31 get_msecs(void)
  32 {
  33   struct timeval tv;
  34
  35   gettimeofday(&tv, 0);
  36   return (long long)tv.tv_sec * 1000 + tv.tv_usec/1000;
  37 }
  38 #else
  39 # define get_msecs() 0
  40 #endif
  41
  42 typedef struct le {
  43     AO_t next;
  44     int data;
  45 } list_element;
  46
  47 AO_stack_t the_list = AO_STACK_INITIALIZER;
  48
  49 void add_elements(int n)
  50 {
  51   list_element * le;
  52   if (n == 0) return;
  53   add_elements(n-1);
  54   le = malloc(sizeof(list_element));
  55   le -> data = n;
  56   AO_stack_push(&the_list, (AO_t *)le);
  57 }
  58
  59 void print_list()
  60 {
  61   list_element *p;
  62
  63   for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
  64        p != 0;
  65        p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
  66     printf("%d\n", p -> data);
  67 }
  68
  69 static char marks[MAX_NTHREADS * MAX_NTHREADS];
  70
  71 void check_list(int n)
  72 {
  73   list_element *p;
  74   int i;
  75
  76   for (i = 1; i <= n; ++i) marks[i] = 0;
  77   for (p = (list_element *)AO_REAL_HEAD_PTR(the_list);
  78        p != 0;
  79        p = (list_element *)AO_REAL_NEXT_PTR(p -> next))
  80     {
  81       if (p -> data > n || p -> data <= 0)
  82         fprintf(stderr, "Found erroneous list element %d\n", p -> data);
  83       if (marks[p -> data] != 0)
  84         fprintf(stderr, "Found duplicate list element %d\n", p -> data);
  85       marks[p -> data] = 1;
  86     }
  87   for (i = 1; i <= n; ++i)
  88     if (marks[i] != 1)
  89       fprintf(stderr, "Missing list element %d\n", i);
  90 }
  91
  92 volatile AO_t ops_performed = 0;
  93
  94 #define LIMIT 1000000
  95         /* Total number of push/pop ops in all threads per test. */
  96
  97 #ifdef AO_HAVE_fetch_and_add
  98 # define fetch_and_add(addr, val) AO_fetch_and_add(addr, val)
  99 #else
 100   /* Fake it.  This is really quite unacceptable for timing     */
 101   /* purposes.  But as a correctness test, it should be OK.     */
 102   AO_INLINE AO_t fetch_and_add(volatile AO_t * addr, AO_t val)
 103   {
 104     AO_t result = AO_load(addr);
 105     AO_store(addr, result + val);
 106     return result;
 107   }
 108 #endif
 109
 110 void * run_one_test(void * arg)
 111 {
 112   list_element * t[MAX_NTHREADS + 1];
 113   list_element * aux;
 114   long index = (long)arg;
 115   int i;
 116   int j = 0;
 117
 118 # ifdef VERBOSE
 119     printf("starting thread %d\n", index);
 120 # endif
 121   while (fetch_and_add(&ops_performed, index + 1) + index + 1 < LIMIT)
 122     {
 123       for (i = 0; i < index + 1; ++i)
 124         {
 125           t[i] = (list_element *)AO_stack_pop(&the_list);
 126           if (0 == t[i])
 127             {
 128               fprintf(stderr, "FAILED\n");
 129               abort();
 130             }
 131         }
 132       for (i = 0; i < index + 1; ++i)
 133         {
 134           AO_stack_push(&the_list, (AO_t *)t[i]);
 135         }
 136       j += (index + 1);
 137     }
 138 # ifdef VERBOSE
 139     printf("finished thread %d: %d total ops\n", index, j);
 140 # endif
 141   return 0;
 142 }
 143
 144 #define N_EXPERIMENTS 1
 145
 146 unsigned long times[MAX_NTHREADS + 1][N_EXPERIMENTS];
 147
 148 int main(int argc, char **argv)
 149 {
 150   int nthreads;
 151   int max_nthreads;
 152   int exper_n;
 153
 154   if (1 == argc)
 155     max_nthreads = 4;
 156   else if (2 == argc)
 157     {
 158       max_nthreads = atoi(argv[1]);
 159       if (max_nthreads < 1 || max_nthreads > MAX_NTHREADS)
 160         {
 161           fprintf(stderr, "Invalid max # of threads argument\n");
 162           exit(1);
 163         }
 164     }
 165   else
 166     {
 167       fprintf(stderr, "Usage: %s [max # of threads]\n", argv[0]);
 168       exit(1);
 169     }
 170   for (exper_n = 0; exper_n < N_EXPERIMENTS; ++ exper_n)
 171     for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
 172       {
 173         int i;
 174         pthread_t thread[MAX_NTHREADS];
 175         int list_length = nthreads*(nthreads+1)/2;
 176         long long start_time;
 177
 178         add_elements(list_length);
 179   #     ifdef VERBOSE
 180           printf("Initial list (nthreads = %d):\n", nthreads);
 181           print_list();
 182   #     endif
 183         ops_performed = 0;
 184         start_time = get_msecs();
 185         for (i = 1; i < nthreads; ++i) {
 186         int code;
 187
 188           if ((code = pthread_create(thread+i, 0, run_one_test,
 189             (void *)(long)i)) != 0) {
 190               fprintf(stderr, "Thread creation failed %u\n", code);
 191             exit(1);
 192           }
 193         }
 194         /* We use the main thread to run one test.  This allows gprof   */
 195         /* profiling to work, for example.                              */
 196           run_one_test(0);
 197         for (i = 1; i < nthreads; ++i) {
 198           int code;
 199           if ((code = pthread_join(thread[i], 0)) != 0) {
 200             fprintf(stderr, "Thread join failed %u\n", code);
 201           }
 202         }
 203         times[nthreads][exper_n] = (unsigned long)(get_msecs() - start_time);
 204   #     ifdef VERBOSE
 205           printf("%d %lu\n", nthreads,
 206                              (unsigned long)(get_msecs() - start_time));
 207           printf("final list (should be reordered initial list):\n");
 208           print_list();
 209   #     endif
 210         check_list(list_length);
 211         while ((list_element *)AO_stack_pop(&the_list));
 212       }
 213 # ifndef NO_TIMES
 214     for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
 215       {
 216         unsigned long sum = 0;
 217
 218         printf("About %d pushes + %d pops in %d threads:",
 219                 LIMIT, LIMIT, nthreads);
 220         for (exper_n = 0; exper_n < N_EXPERIMENTS; ++exper_n)
 221           {
 222 #           if defined(VERBOSE)
 223               printf("[%lu] ", times[nthreads][exper_n]);
 224 #           endif
 225             sum += times[nthreads][exper_n];
 226           }
 227         printf(" %lu msecs\n", (sum + N_EXPERIMENTS/2)/N_EXPERIMENTS);
 228       }
 229 # endif /* NO_TIMES */
 230   return 0;
 231 }
 232