main.c

是一个linux下面实现的非阻塞的堆

/*================================ main.c ===================================*/
#include <stdio.h>
#include <sys/param.h>
#include <sys/types.h>
#include <sys/times.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sysmp.h>
#include <sys/wait.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <ulocks.h>
#include <unistd.h>
#include <math.h>
#include <sys/cachectl.h>

#define MAIN
#include "heap.h"

static	struct tms 	tim2;
static	double		t1,t2;
/*===========================================================================*/
usptr_t *	lock_handle;
usptr_t *	barrier_handle;
barrier_t *	Barrier;
/*---------------------------------------------------------------------------*/
char* share_malloc (unsigned);
void share_malloc_init(unsigned);
void remove_shmem();
/*---------------------------------------------------------------------------*/
void check_heap();
/*---------------------------------------------------------------------------*/
void single_ins(int priority,int data,shared_mem_t *smp,element_t *heap);
void single_del(int *priority,int *data,shared_mem_t *smp,element_t *heap);
void hetal_ins(int priority,int data,shared_mem_t *smp,element_t *heap);
void hetal_del(int *priority,int *data,shared_mem_t *smp,element_t *heap);
void rk_ins(int priority,int data,shared_mem_t *smp,element_t *heap);
void rk_del(int *priority,int *data,shared_mem_t *smp,element_t *heap);
void rkb_ins(int priority,int data,shared_mem_t *smp,element_t *heap);
void rkb_del(int *priority,int *data,shared_mem_t *smp,element_t *heap);
/*---------------------------------------------------------------------------*/
void setup_shmem()
{
  share_malloc_init (25000000);
}
/*---------------------------------------------------------------------------*/
int  	procs = 1;
int     number = 10;
int     iterations;
int	delay = 1;
int	runhog = 0;
int	debug = 0;
int     algorithms = 0xf;
int     initial = 0x0;
int     repetitions = 1;
/*---------------------------------------------------------------------------*/
element_t* heap;
shared_mem_t* smp;
/*---------------------------------------------------------------------------*/
int fork_procs(int procs, void (*task)(void))
{
  for (pid = 10; pid > 11-procs; pid--)
  {
  int rc;
    fflush (stdout);
    fflush (stderr);
    rc = fork();
    if(rc==0)
    {
      if(runhog)
	sysmp(MP_MUSTRUN, pid);    
      (*task)(); exit(0);
    }
    else
    {
      if(rc==-1){
	perror("can't create process");
	exit (-1);
      }
    }
  }
  pid = 11;
  if(runhog)
    sysmp(MP_MUSTRUN, pid);
  (*task)();
}
/*---------------------------------------------------------------------------*/
void check_heap()
{
int  broken = 0;
int         i, l, r;
register    element_t*      ip;
register    element_t*      lp;
register    element_t*      rp;

  for(i=1;i<=smp->l_lst;i++)
  {
    l = i << 1;
    r = l + 1;
    if (l > smp->l_lst) l = 0;
    if (r > smp->l_lst) r = 0;
    ip = &heap[i];
    if (l) lp = &heap[l];
    if (r) rp = &heap[r];
        
    if (debug || 
         (l && (ip->i_pri > lp->i_pri)) || (r && (ip->i_pri > rp->i_pri)))
    {
      if ((l && (ip->i_pri > lp->i_pri)) || (r && (ip->i_pri > rp->i_pri)))
      {
        printf("----");
        broken++;
      }
      printf("!p[%5d] = %d/%5d", i, ip->i_tag, ip->i_pri);
      if (l) printf("   l[%5d] = %d/%5d", l, lp->i_tag, lp->i_pri);
      if (r) printf("   r[%5d] = %d/%5d", r, rp->i_tag, rp->i_pri);
      printf("\n");
    }
  }
  if (broken)
    printf("Broken %d, [last = %d] *****\n", broken, smp->l_lst);
}
/*---------------------------------------------------------------------------*/
void check_shuffle_heap()
{
int  broken = 0;
int         i, l, r;
register    element_t*      ip;
register    element_t*      lp;
register    element_t*      rp;

  for(i=1;i<=smp->l_lst;i++)
  {
    l = i << 1;
    r = l + 1;
    if (l >= size) l = 0;
    if (r >= size) r = 0;
    ip = &heap[SHUFFLE(i)];
    if(ip->i_tag != T_PRESENT)
      continue;
    if (l) lp = &heap[SHUFFLE(l)];
    if (r) rp = &heap[SHUFFLE(r)];
    if (l && lp->i_tag == T_EMPTY) l = 0;
    if (r && rp->i_tag == T_EMPTY) r = 0;
        
    if ((l && (ip->i_pri > lp->i_pri)) || (r && (ip->i_pri > rp->i_pri)))
    {
      printf("!p[%5d] = %d/%5d", i, ip->i_tag, ip->i_pri);
      if (l) printf("   l[%5d] = %d/%5d", l, lp->i_tag, lp->i_pri);
      if (r) printf("   r[%5d] = %d/%5d", r, rp->i_tag, rp->i_pri);
      printf("\n");
      broken++;
    }
  }
  if (broken)
    printf("Broken %d, [last = %d] *****\n", broken, smp->l_lst);
}
/*---------------------------------------------------------------------------*/
typedef void (*fn_ins)(int, int, shared_mem_t *,element_t *);
typedef void (*fn_del)(int *,int *,shared_mem_t *,element_t *);
/*---------------------------------------------------------------------------*/
void time_test(fn_ins ins_fn, fn_del del_fn, char *test_name,int test_num)
{
int i,j;
struct tms time_val;
clock_t t1, t2;
int data, priority;

  /*q_delay = pid;*/
  srandom (pid*pid);
  barrier(Barrier, procs);
  if(pid==11)
  {
    smp->l_lst = 0;
    smp->l_ful = 0;
    smp->l_lck = 0;
    smp->b_value = 1;
    for(i=0;i<size;i++)
    {
      heap[i].i_tag = T_EMPTY;
      heap[i].i_pri = MAXINT;
      heap[i].i_lck = 0;
    }
    for(i=0;i<initial;i++)
    {
      priority = (random() % 899999) + 10;
      data = priority + 1;
      ins_fn(priority, data,smp,heap);
    }
    switch(test_num)
    {
      case 1: check_heap(); break;
      case 2: case 3: case 4: check_shuffle_heap(); break;
    }
  }
  cacheflush(smp,sizeof(shared_mem_t),DCACHE);
  cacheflush(heap,sizeof(element_t)*size,DCACHE);
  barrier(Barrier, procs);
  if(pid==11)
  {
    t1=times(&time_val);
  }
  barrier(Barrier,procs);
  for(i=0;i<iterations;i++)
  {
    priority = (random() % 899999) + 10;
    data = priority + 1;
    /*for(j=0;j<10;j++)*/
      ins_fn(priority, data, smp, heap);
    /*for(j=0;j<10;j++)*/
    /*  del_fn(&priority, &data, smp,heap);*/
  }
  barrier(Barrier,procs);
  if(pid==11)
  {
    t2=times(&time_val);
    printf("%s: %.3f seconds\n", test_name, (t2-t1)/(double)HZ);
    fflush(stdout);
    switch(test_num)
    {
      case 1: check_heap(); break;
      case 2: case 3: case 4: check_shuffle_heap(); break;
    }
    fflush(stdout);
  }
}
/*---------------------------------------------------------------------------*/
void main_task(void)
{
int i;

  for(i=0;i<repetitions;i++)
  {
    if(algorithms & 1)  time_test(single_ins,single_del,"single lock",1);
    if(algorithms & 2)  time_test(hetal_ins,hetal_del,  "h&etalQ    ",2);
    if(algorithms & 4)  time_test(rk_ins,rk_del,        "r&kQ       ",3);
    if(algorithms & 8)  time_test(rkb_ins,rkb_del,      "r&kbQ      ",4);
  }
}
/*---------------------------------------------------------------------------*/
void parse_args(int argc,char **argv)
{
extern char * optarg; 
int c; 

  while ((c=getopt(argc,argv,"p:h:n:s:d:a:i:r:"))!=EOF)
    switch(c)
    {
      case 'p': procs = atoi(optarg);  break;
      case 'h': runhog = atoi(optarg); break;
      case 'n': number = atoi(optarg); break;
      case 's': size = 1<<atoi(optarg); break;
      case 'd': debug = atoi(optarg); break;
      case 'a': algorithms = atoi(optarg); break;
      case 'i': initial = atoi(optarg); break;
      case 'r': repetitions = atoi(optarg); break;
      default: 
        fprintf(stderr,"Usage: blah blah\n",argv[0]);
        exit(-1);
   }
}
/*---------------------------------------------------------------------------*/
int main (int argc, char **argv)
{
int		broken;
    
  size = 0x40000;
  parse_args(argc, argv);
  iterations = number / procs;
  fprintf(stdout, "# %s, procs(-p%d) iters(-i%d) = %d, runhog(%d)\n"
	   , argv[0], procs, iterations, procs*iterations, runhog);

  setup_shmem();

    smp = (shared_mem_t*) share_malloc(sizeof(shared_mem_t));
    heap = (element_t*) share_malloc(sizeof(element_t)*size);

    lock_handle = usinit("/tmp/mmm_foo_lck");
    smp->l_lock = usnewlock(lock_handle);

    barrier_handle = usinit("/tmp/mmm_foo_bar");
    Barrier = new_barrier(barrier_handle);
    init_barrier(Barrier);

    fork_procs(procs,main_task);
    fflush(stdout); /* This has to be here for some strange reason! */
    usfreelock(smp->l_lock, lock_handle);
    usdetach(lock_handle);
    unlink("/tmp/mmm_foo_lck");
    free_barrier(Barrier);
    usdetach(barrier_handle);
    unlink("/tmp/mmm_foo_bar");
    remove_shmem();
}
/*---------------------------------------------------------------------------*/