Skip to content
This repository
Fetching contributors…

Cannot retrieve contributors at this time

file 231 lines (207 sloc) 6.009 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
/*
* Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
* Original Author: Hans Boehm
*
* 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 doc/COPYING for more details.
*/

#if defined(HAVE_CONFIG_H)
# include "config.h"
#endif

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include "atomic_ops.h"
#include "atomic_ops_stack.h"
#define MAX_NTHREADS 100

#ifndef NO_TIMES
#include <time.h>
#include <sys/time.h>
/* Need 64-bit long long support */
long long
get_msecs(void)
{
  struct timeval tv;

  gettimeofday(&tv, 0);
  return (long long)tv.tv_sec * 1000 + tv.tv_usec/1000;
}
#else
# define get_msecs() 0
#endif

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));
  le -> data = n;
  AO_stack_push(&the_list, (AO_t *)le);
}

void print_list()
{
  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);
}

static char marks[MAX_NTHREADS * MAX_NTHREADS];

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))
    {
      if (p -> data > n || p -> data <= 0)
        fprintf(stderr, "Found erroneous list element %d\n", p -> data);
      if (marks[p -> data] != 0)
        fprintf(stderr, "Found duplicate list element %d\n", p -> data);
      marks[p -> data] = 1;
    }
  for (i = 1; i <= n; ++i)
    if (marks[i] != 1)
      fprintf(stderr, "Missing list element %d\n", i);
}
     
volatile AO_t ops_performed = 0;

#define LIMIT 1000000
/* Total number of push/pop ops in all threads per test. */

#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

void * run_one_test(void * arg)
{
  list_element * t[MAX_NTHREADS + 1];
  list_element * aux;
  long index = (long)arg;
  int i;
  int j = 0;

# ifdef VERBOSE
    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]);
        }
      j += (index + 1);
    }
# ifdef VERBOSE
    printf("finished thread %d: %d total ops\n", index, j);
# endif
  return 0;
}

#define N_EXPERIMENTS 1

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 = 4;
  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;
        pthread_t thread[MAX_NTHREADS];
        int list_length = nthreads*(nthreads+1)/2;
        long long start_time;
  
        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;
  
          if ((code = pthread_create(thread+i, 0, run_one_test,
   (void *)(long)i)) != 0) {
       fprintf(stderr, "Thread creation failed %u\n", code);
            exit(1);
          }
        }
        /* 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;
          if ((code = pthread_join(thread[i], 0)) != 0) {
       fprintf(stderr, "Thread join failed %u\n", code);
          }
        }
        times[nthreads][exper_n] = (unsigned long)(get_msecs() - start_time);
# ifdef VERBOSE
          printf("%d %lu\n", nthreads,
(unsigned long)(get_msecs() - start_time));
          printf("final list (should be reordered initial list):\n");
          print_list();
# endif
        check_list(list_length);
        while ((list_element *)AO_stack_pop(&the_list));
      }
# ifndef NO_TIMES
    for (nthreads = 1; nthreads <= max_nthreads; ++nthreads)
      {
        unsigned long sum = 0;

        printf("About %d pushes + %d pops in %d threads:",
LIMIT, LIMIT, nthreads);
        for (exper_n = 0; exper_n < N_EXPERIMENTS; ++exper_n)
{
# if defined(VERBOSE)
printf("[%lu] ", times[nthreads][exper_n]);
# endif
sum += times[nthreads][exper_n];
          }
        printf(" %lu msecs\n", (sum + N_EXPERIMENTS/2)/N_EXPERIMENTS);
      }
# endif /* NO_TIMES */
  return 0;
}
Something went wrong with that request. Please try again.