void * acqrel_thr(void *id)
{
  int me = (int)(long)id;

  int i;

  for (i = 0; i < NITERS; ++i)
    if (me & 1)
      {
        AO_T my_counter1;
	if (me != 1)
	  fprintf(stderr, "acqrel test: too many threads\n");
	my_counter1 = AO_load(&counter1);
	AO_store(&counter1, my_counter1 + 1);
	AO_store_release_write(&counter2, my_counter1 + 1);
      }
    else
      {
	AO_T my_counter2;
	AO_T my_counter1;
	my_counter2 = AO_load_acquire_read(&counter2);
	my_counter1 = AO_load(&counter1);
	if (my_counter1 < my_counter2)
	  {
	    fprintf(stderr, "Saw release store out of order: %lu < %lu\n",
		    (unsigned long)my_counter1, (unsigned long)my_counter2);
	    abort();
	  }
      }

  return 0;
}

/* get_buffers_from_BM: function used to get buffers to be used for reading data
 * off disks via DM_get
 */
void get_buffers_from_BM(uint64_t buffers_required,
	uri_entry_t *requested_object, nkn_buf_t *buffers[MAX_BUFFERS_FETCH_DM])
{
    nkn_buf_t *buffer = NULL, *attr_buffer_present = NULL;
    char *attr_uri_name = NULL;
    int counter = 0;
    //uint64_t append_offset = 0;
    //char buff[512];
    //memset(buff, 0, sizeof(buff));

    //append_offset = (requested_object->request_offset / DATA_BUFFER_SIZE) *
   //							DATA_BUFFER_SIZE;




    attr_buffer_present = g_hash_table_lookup(attr_hash_table,
					requested_object->uri_name);
    if (!attr_buffer_present) {
	//insert the entry in the hash;
	attr_buffer_present = getFreeAttrBuffer();
	//int len = strlen(requested_object->uri_name);
	attr_uri_name = (char*)calloc(MAX_URI_LEN,1);
	strncpy(attr_uri_name,requested_object->uri_name,
	                                             (MAX_URI_LEN-1));
	attr_buffer_present->uri_name = attr_uri_name;
	g_hash_table_insert(attr_hash_table,
	                             attr_uri_name,attr_buffer_present);
    }
    else if (AO_load(&(attr_buffer_present->ref)) == 0)
    {
       TAILQ_REMOVE(&attrbufferpool_queues[attr_buffer_present->flist],
                                     attr_buffer_present,attrbuffpoolentry);
       //if(present_buffer == buffer)
       //  attr_buffer_present->ref++;
       //                                                                  
    }
    requested_object->attrbuff = attr_buffer_present;
    while(buffers_required != 0) {

	pthread_mutex_lock(&bufferpool_queue_mutex);
	buffer = getFreeBuffer();
	pthread_mutex_unlock(&bufferpool_queue_mutex);
	assert(AO_load(&(buffer->ref))== 0);
	buffer->attrbuf = attr_buffer_present;
	buffers[counter] = buffer;
	buffers[counter]->use++;


	attr_buffer_present->use++;
	attr_buffer_present->use_ts = AO_load(&nkn_cur_ts);
	attr_buffer_present->provider = PROVIDER_DM;
	//append_offset += DATA_BUFFER_SIZE;
	buffers_required--;
	counter++;
    }



}

AO_t *
AO_stack_pop_explicit_aux_acquire(volatile AO_t *list, AO_stack_aux * a)
{
  unsigned i;
  int j = 0;
  AO_t first;
  AO_t * first_ptr;
  AO_t next;

 retry:
  first = AO_load(list);
  if (0 == first) return 0;
  /* Insert first into aux black list.                                  */
  /* This may spin if more than AO_BL_SIZE removals using auxiliary     */
  /* structure a are currently in progress.                             */
  for (i = 0; ; )
    {
      if (PRECHECK(a -> AO_stack_bl[i])
          AO_compare_and_swap_acquire(a->AO_stack_bl+i, 0, first))
        break;
      ++i;
      if ( i >= AO_BL_SIZE )
        {
          i = 0;
          AO_pause(++j);
        }
    }
  assert(i < AO_BL_SIZE);
  assert(a -> AO_stack_bl[i] == first);
  /* First is on the auxiliary black list.  It may be removed by        */
  /* another thread before we get to it, but a new insertion of x       */
  /* cannot be started here.                                            */
  /* Only we can remove it from the black list.                         */
  /* We need to make sure that first is still the first entry on the    */
  /* list.  Otherwise it's possible that a reinsertion of it was        */
  /* already started before we added the black list entry.              */
  if (AO_EXPECT_FALSE(first != AO_load(list))) {
    AO_store_release(a->AO_stack_bl+i, 0);
    goto retry;
  }
  first_ptr = AO_REAL_NEXT_PTR(first);
  next = AO_load(first_ptr);
  if (AO_EXPECT_FALSE(!AO_compare_and_swap_release(list, first, next))) {
    AO_store_release(a->AO_stack_bl+i, 0);
    goto retry;
  }
  assert(*list != first);
  /* Since we never insert an entry on the black list, this cannot have */
  /* succeeded unless first remained on the list while we were running. */
  /* Thus its next link cannot have changed out from under us, and we   */
  /* removed exactly one entry and preserved the rest of the list.      */
  /* Note that it is quite possible that an additional entry was        */
  /* inserted and removed while we were running; this is OK since the   */
  /* part of the list following first must have remained unchanged, and */
  /* first must again have been at the head of the list when the        */
  /* compare_and_swap succeeded.                                        */
  AO_store_release(a->AO_stack_bl+i, 0);
  return first_ptr;
}

void rtsched_queue_dump_counters(void)
{
    printf("\nglob_rtsched_runnable_q_pushes = %ld",
	    AO_load(&glob_rtsched_runnable_q_pushes));
    printf("\nglob_rtsched_runnable_q_pops = %ld",
	    AO_load(&glob_rtsched_runnable_q_pops));
    printf("\nglob_rtsched_cleanup_q_pushes = %ld",
	    AO_load(&glob_rtsched_cleanup_q_pushes));
    printf("\nglob_rtsched_cleanup_q_pops = %ld", glob_rtsched_cleanup_q_pops);
}

/* may cause starvation ... */
int AO_wait_lock_g( AO_lock_ptr_t lock, AO_lock_val_t self ) {
    AO_lock_t lk_val;
    if( AO_load((ao_t*) lock) == (ao_t) self ) return 0;
    while( AO_compare_and_swap_release((ao_t *)lock,(ao_t )0,(ao_t) self) == 0 ) {
        lk_val = AO_load((ao_t*) lock);
        if( lk_val  == 0 ) continue;
        futex_wait(lock,lk_val);
    }
    return 1;
}

/* pointers with extra bits "or"ed into the low order bits.             */
void
AO_stack_push_explicit_aux_release(volatile AO_t *list, AO_t *x,
                                   AO_stack_aux *a)
{
  AO_t x_bits = (AO_t)x;
  AO_t next;

  /* No deletions of x can start here, since x is not currently in the  */
  /* list.                                                              */
 retry:
# if AO_BL_SIZE == 2
  {
    /* Start all loads as close to concurrently as possible. */
    AO_t entry1 = AO_load(a -> AO_stack_bl);
    AO_t entry2 = AO_load(a -> AO_stack_bl + 1);
    if (entry1 == x_bits || entry2 == x_bits)
      {
        /* Entry is currently being removed.  Change it a little.       */
          ++x_bits;
          if ((x_bits & AO_BIT_MASK) == 0)
            /* Version count overflowed;         */
            /* EXTREMELY unlikely, but possible. */
            x_bits = (AO_t)x;
        goto retry;
      }
  }
# else
  {
    int i;
    for (i = 0; i < AO_BL_SIZE; ++i)
      {
        if (AO_load(a -> AO_stack_bl + i) == x_bits)
          {
            /* Entry is currently being removed.  Change it a little.   */
              ++x_bits;
              if ((x_bits & AO_BIT_MASK) == 0)
                /* Version count overflowed;         */
                /* EXTREMELY unlikely, but possible. */
                x_bits = (AO_t)x;
            goto retry;
          }
      }
  }
# endif
  /* x_bits is not currently being deleted */
  do
    {
      next = AO_load(list);
      *x = next;
    }
  while (AO_EXPECT_FALSE(!AO_compare_and_swap_release(list, next, x_bits)));
}

/* return_buffers_to_client: used to simulate the communication after a DM_get
 * to send buffers back to the client.
 * Also stores the buffers into the cache. (only if the buffer was not 
 * previously present in the cache
 */
void return_buffers_to_client(uint64_t buffers_required,
    uri_entry_t *requested_object, nkn_buf_t *buffers[MAX_BUFFERS_FETCH_DM])
{

    uint64_t counter = 0;
    nkn_buf_t *present_buffer = NULL;

    while(counter != buffers_required)
    {

	//total_dup_bytes_delivered += (buffers[counter])->length;
	//total_bytes_delivered += (buffers[counter])->length;
	present_buffer = g_hash_table_lookup(uri_hash_table,
		(buffers[counter])->uri_name);

	if (present_buffer == NULL) {

	    //this is a new buffer
	    //insert into the hash table
	    //insert into requested_obj->databufs
	    //inc ref count
	    //inc attrbuff refcount
	    //inc total bytes in ram
	    g_hash_table_insert(uri_hash_table, buffers[counter]->uri_name,
					 buffers[counter]);

	    requested_object->data_bufs[requested_object->buffer_fetch_count++]=
							    buffers[counter];
	    AO_fetch_and_add1(&((buffers[counter])->ref));
	    assert(AO_load(&((buffers[counter])->ref)) == 1);
	    ((buffers[counter])->attrbuf)->buffer_count++;
	    AO_fetch_and_add1(&(((buffers[counter])->attrbuf)->ref));

	    total_bytes_in_ram += (buffers[counter])->length;

	}
	else {
	    free((buffers[counter])->uri_name);
	    assert(AO_load(&(buffers[counter]->ref)) == 0);
	    makeBufferAvailable(buffers[counter]);

	}
	counter++;
    }





}

int main(void)
{
    int i;
# ifdef GC_PTHREADS
    int err;
    pthread_t th[INITIAL_THREAD_COUNT];
# else
    HANDLE th[INITIAL_THREAD_COUNT];
# endif

    GC_INIT();
    for (i = 0; i < INITIAL_THREAD_COUNT; ++i) {
#     ifdef GC_PTHREADS
        err = pthread_create(&th[i], NULL, entry, 0);
        if (err) {
            fprintf(stderr, "Thread creation failed: %s", strerror(err));
            exit(1);
        }
#     else
        DWORD thread_id;
        th[i] = CreateThread(NULL, 0, entry, 0, 0, &thread_id);
        if (th[i] == NULL) {
            printf("Thread creation failed: %d\n", (int)GetLastError());
            exit(1);
        }
#     endif
    }

    for (i = 0; i < INITIAL_THREAD_COUNT; ++i) {
#     ifdef GC_PTHREADS
        void *res;
        err = pthread_join(th[i], &res);
        if (err) {
            fprintf(stderr, "Failed to join thread: %s", strerror(err));
            exit(1);
        }
#     else
        if (WaitForSingleObject(th[i], INFINITE) != WAIT_OBJECT_0) {
            printf("Failed to join thread: %d\n", (int)GetLastError());
            CloseHandle(th[i]);
            exit(1);
        }
        CloseHandle(th[i]);
#     endif
    }
  printf("subthread_create: created %d threads (%d ended)\n",
         (int)AO_load(&thread_created_cnt), (int)AO_load(&thread_ended_cnt));
  return 0;
}

int  AO_unlock( AO_lock_ptr_t lock ) {
    pthread_t self = pthread_self();
    if( AO_load((ao_t*) lock) != (ao_t) self ) return 0;
    AO_store_release(lock,0);
    futex_wake(lock,1); // wake up exactly one thread
    return 1;
}

int
ns_stat_add(ns_stat_token_t	stoken,
            ns_stat_category_t	stat_type,
            int64_t		add_val,
            int64_t		*old_val)
{
    int64_t  tmp_val;
    uint32_t ns_index = stoken.u.stat_token_data.val;
    uint32_t gen = stoken.u.stat_token_data.gen;
    uint32_t curr_gen;

    curr_gen = (uint32_t) AO_load(&ns_token_gen[ns_index]);
    if (curr_gen != gen) {
        glob_ns_stat_add_gen_mismatch_err++;
        return NKN_STAT_GEN_MISMATCH;
    }

    if (stat_type >= NS_STAT_MAX) {
        glob_ns_stat_add_type_einval_err++;
        return NKN_STAT_TYPE_EINVAL;
    }

    tmp_val = AO_fetch_and_add(&ns_stats[ns_index][stat_type], add_val);

    if (old_val)
        *old_val = tmp_val;
    return 0;
}	/* ns_stat_add */

static inline int traces_obtain_log_line_number(void)
{
	int linenum;

	while (1) {
		/* wait for buffer to be emptied */
		while (AO_load(&traces->logcnt) > LAST_LOGLINE);

		while (AO_test_and_set(&traces->lock) == AO_TS_SET);
		
		/* new line will be used! */
		AO_fetch_and_add1(&traces->usecnt);
		
		/* get log line number */
		linenum = AO_fetch_and_add1(&traces->logcnt);

		AO_CLEAR(&traces->lock);

		/* line number with valid properties has been acquired so leave */
		if (linenum <= LAST_LOGLINE)
			break;
		
		/* release non-existing line number */
		AO_fetch_and_sub1(&traces->usecnt);
	}
	
	DEBUG("linenum = %d", linenum);

	/* linenum is storing now a unique number n, such as 0 <= n <= LAST_LOGLINE */
	return linenum;
}

static void *
_gcollect_proc(void *arg)
{
    while (AO_load(&pending))
	GC_gcollect();
    return NULL;
}

static void traces_log_write_out(void)
{
	DEBUG("begin");
	
	/* disallow to obtain new lines */
	while (AO_test_and_set(&traces->lock) == AO_TS_SET);

	/* if any line is still used, wait for it to be released */
	while (AO_load(&traces->usecnt) > 0);

	int lines = (traces->logcnt >= LAST_LOGLINE) ? (LAST_LOGLINE - 1) : traces->logcnt;
	
	if (lines > 0) {
		if (write(traces->logfd, &traces->logs, lines * sizeof(traces_log_t)) == -1)
			perror("traces: writing out failed: ");
		else
			DEBUG("written out %d lines", lines);
	}
	
	memset(&traces->logs, 0, (LAST_LOGLINE - 1) * sizeof(traces_log_t));

	/* reset line log counter */
	AO_store(&traces->logcnt, 0);
	AO_CLEAR(&traces->lock);
	
	DEBUG("finished");
}

void * acqrel_thr(void *id)
{
  int me = (int)(AO_PTRDIFF_T)id;

  int i;

  for (i = 0; i < NITERS; ++i)
    if (me & 1)
      {
        AO_t my_counter1;
        if (me != 1)
          {
            fprintf(stderr, "acqrel test: too many threads\n");
            abort();
          }
        my_counter1 = AO_load(&counter1);
        AO_store(&counter1, my_counter1 + 1);
        AO_store_release_write(&counter2, my_counter1 + 1);
      }
    else
      {
        AO_t my_counter1a, my_counter2a;
        AO_t my_counter1b, my_counter2b;

        my_counter2a = AO_load_acquire_read(&counter2);
        my_counter1a = AO_load(&counter1);
        /* Redo this, to make sure that the second load of counter1 */
        /* is not viewed as a common subexpression.         */
        my_counter2b = AO_load_acquire_read(&counter2);
        my_counter1b = AO_load(&counter1);
        if (my_counter1a < my_counter2a)
          {
            fprintf(stderr, "Saw release store out of order: %lu < %lu\n",
                (unsigned long)my_counter1a, (unsigned long)my_counter2a);
            abort();
          }
        if (my_counter1b < my_counter2b)
          {
            fprintf(stderr,
                "Saw release store out of order (bad CSE?): %lu < %lu\n",
                (unsigned long)my_counter1b, (unsigned long)my_counter2b);
            abort();
          }
      }

  return 0;
}

static void traces_register_at_exit(void)
{
	/* atexit uses internally malloc ! */
	if ((traces != NULL) && (AO_load(&initcnt) == 0) && (AO_fetch_and_add1(&initcnt) == 0)) {
		DEBUG("initializing atexit handler");
		atexit(&traces_at_exit);
		DEBUG("initialized atexit handler");
	}
}

void
ecl_atomic_push(cl_object *slot, cl_object c)
{
        cl_object cons = ecl_list1(c), car;
        do {
                car = (cl_object)AO_load((AO_t*)slot);
                ECL_RPLACD(cons, car);
        } while (!AO_compare_and_swap_full((AO_t*)slot, (AO_t)car, (AO_t)cons));
}

cl_object
ecl_atomic_get(cl_object *slot)
{
	cl_object old;
	do {
		old = (cl_object)AO_load((AO_t*)slot);
	} while (!AO_compare_and_swap_full((AO_t*)slot, (AO_t)old, (AO_t)ECL_NIL));
	return old;
}

void
dm2_dec_write_cnt_on_cache_dev(dm2_cache_info_t *freespace_ci)
{
    NKN_ASSERT(AO_load(&freespace_ci->ci_update_cnt));
    AO_fetch_and_sub1(&freespace_ci->ci_update_cnt);
#if 0
    DBG_DM2E("dec update cnt: %s %d",
	     freespace_ci->mgmt_name, freespace_ci->ci_update_cnt);
#endif
}	/* dm2_dec_write_cnt_on_cache_dev */

cl_object
ecl_atomic_pop(cl_object *slot)
{
        cl_object cons, rest;
        do {
                cons = (cl_object)AO_load((AO_t*)slot);
		rest = CDR(cons);
        } while (!AO_compare_and_swap_full((AO_t*)slot, (AO_t)cons, (AO_t)rest));
        return cons;
}

cl_index
ecl_atomic_index_incf(cl_index *slot)
{
	AO_t old;
	AO_t next;
	do {
		old = AO_load((AO_t*)slot);
		next = old+1;
	} while (!AO_compare_and_swap_full((AO_t*)slot, (AO_t)old, (AO_t)next));
	return (cl_index)next;
}