← Back to branch summary

~ubuntu-branches/ubuntu/quantal/libgc/quantal

« back to all changes in this revision

Viewing changes to libatomic_ops-1.2/tests/test_stack.c

  • Committer: Bazaar Package Importer
  • Author(s): Christoph Egger
  • Date: 2011-02-19 12:19:56 UTC
  • mfrom: (1.3.2 upstream) (0.1.5 experimental)
  • mto: This revision was merged to the branch mainline in revision 14.
  • Revision ID: james.westby@ubuntu.com-20110219121956-67rb69xlt5nud3v2
Tags: 1:7.1-5
Upload to unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
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