path: root/tests/test_stack.c

/*
 * 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

#if defined(__vxworks) || defined(_MSC_VER) || defined(_WIN32_WINCE) \
    || (defined(_WIN32) && !defined(__CYGWIN32__) && !defined(__CYGWIN__))

  /* Skip the test if no pthreads.  */
  int main(void)
  {
    return 0;
  }

#else

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

#ifndef MAX_NTHREADS
# define MAX_NTHREADS 100
#endif

#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));
  if (le == 0)
    {
      fprintf(stderr, "Out of memory\n");
      exit(2);
    }
  le -> data = n;
  AO_stack_push(&the_list, (AO_t *)le);
}

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

#ifndef N_EXPERIMENTS
# define N_EXPERIMENTS 1
#endif

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;
        list_element * le;

        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(3);
          }
        }
        /* 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 ((le = (list_element *)AO_stack_pop(&the_list)) != 0)
          free(le);
      }
# 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;
}

#endif /* !_MSC_VER */