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