lpd-epfl / clht Goto Github PK

Hi, how can use iterators in clht hashtable?

Hello. CLHT hash table have concurrent editing in one of the modes with or without lock?
If not, Do you have a solution?

Thanks in advance!

Hello,

I'm considering to port CLHT to Golang and I have a question on the atomic snapshot logic which is present in reads:

	  clht_val_t val = bucket->val[j];
#ifdef __tile__
	  _mm_lfence();
#endif
	  if (bucket->key[j] == key) // Line 1
	    {
	      if (likely(bucket->val[j] == val)) // Line 2
		{
		  return val;
		}
	      else
		{
		  return 0; // Line 3
		}
	    }

Let's consider the following scenario. We have three threads doing the following operations:

Thread A: |	put(key, val1)	|
Thread B: 			| put(key, val2) |
Thread C: 	|	get(key)	|
--> time

It may happen that thread C reads the key and val1 due to Thread A's put outcomes once it's at the Line 1. Then it reads the value at Line 2 and sees val2 since Thread B has started its put. Values don't match and we go into the else block returning 0 at the Line 3, while the result should be either val1 (latest finished put) or val2 (concurrent put).

This logic seems wrong to me since get should return the latest (or the previously known) value. If thread C did a previous put for the same key, it'll get 0 instead of the stored value and thus linearizability will be broken. Am I missing something?

Aim to use clht_lb_res as external static link, get undefined reference error

App: RocksDB

Steps:

CLHT$ make libclht_lb_res.a
CLHT$ ar -r libclht_lb_res.a libclht_lb_res.o
CLHT$ cp libclht_lb_res.a xxx_rocksdb_dir/

Then link libclht_lb_res.a in CMakeLists.txt

target_link_libraries(${ROCKSDB_SHARED_LIB} ${PROJECT_SOURCE_DIR}/libclht_lb_res.a)

include libclht_lb_res.h

Error message:

/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_gc_thread_init(clht*, int)'
/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_create(unsigned long)'
/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_put(clht*, unsigned long, char*)'
/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_get(clht_hashtable_s*, unsigned long)'
/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_gc_get_id()'
/usr/bin/ld: xxx_rocksdb_dir/build/lib64/librocksdb.so: undefined reference to `clht_gc_destroy(clht*)'
collect2: error: ld returned 1 exit status

I am seeing a segfault during the resize operation in CLHT_LB_RES. Here's the log and stack trace.

Any help is much appreciated.
Thanks!

It seems it is coming from here:

279       ssmem_release(clht_alloc, (void*) cur);

[STATUS-13421772] #bu: 22369622 / #elems: 111384397 / full%: 165.9757% / expands: 22369622 / max expands:  6
[RESIZE-13421772] to #bu 89478488 = MB: 5461.33    | took:   28889809354 ti = 13.757052 s

Thread 10 "main" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7ffdbbbbe700 (LWP 139857)]
0x000055555555ab6f in ssmem_release ()
(gdb) bt
#0  0x000055555555ab6f in ssmem_release ()
#1  0x0000555555559f70 in clht_gc_release (hashtable=hashtable@entry=0x555555572000)
    at src/clht_gc.c:279
#2  0x00005555555598df in ht_resize_pes (h=h@entry=0x555555571f00, 
    is_increase=is_increase@entry=1, by=<optimized out>) at src/clht_lb_res.c:593
#3  0x00005555555593de in ht_status (h=h@entry=0x555555571f00, 
    resize_increase=resize_increase@entry=1, just_print=just_print@entry=0)
    at src/clht_lb_res.c:707
#4  0x0000555555559771 in clht_put (h=0x555555571f00, key=7536092987517542395, 
    val=<optimized out>) at src/clht_lb_res.c:355
#5  0x0000555555557b56 in do_inserts (id=<optimized out>, keys=0x7fff2888d010, 
    values=0x7ffeaeef3010, start=<optimized out>, n=<optimized out>) at main.cc:32
#6  0x00007ffff7bddde4 in ?? () from /lib/x86_64-linux-gnu/libstdc++.so.6
#7  0x00007ffff7ad2609 in start_thread (arg=<optimized out>) at pthread_create.c:477
#8  0x00007ffff79f9293 in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

hello, I've meet some problem while using clht

at first, I chose the clht_lb_res in my application, and then I got a core dump caused by ht_resize().

then I changed to clht_lb, and init the hashtable like clht_create(5000), and then I got a checksum mismatch(this comes from an asseet in my own application ), so I print all the item in the hashtable(I used it like int --> char*).

and the problem is the char* is all right, but the content char* point to is changed.

I'am sure that it's clht's problem because after I changed the hashtable to SPTAG(another hashtable implementation), the problem disappeared

so i guess that there may be some hidden bugs in the ssmem part of your program。it maybe implicitly change the contents of the memory, or conflicts with the memory management of my application

i read some clht_lf_res.c code, i cannot found some collision code, if key value that hash function calculate is the same .

Is there any c++ implementation of CLHT? If not how can I use it inside of a c++ program?

Thanks in advance!

1. I have not found my processor version in utils.h, so I am wondering how to set config for my processor 80 Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz.
2. Could you please explain more about the meaning of such parameters, e.g. NOP_DURATION and the_cores[]? And how can I get the right infomation to set such config?

#elif defined(XEON2)
#  define NUMBER_OF_SOCKETS 2
#  define CORES_PER_SOCKET 20
#  define CACHE_LINE_SIZE 64
#  define NOP_DURATION 2

#  define USE_HYPERTRHEADS 1

#  if USE_HYPERTRHEADS == 0
  static uint8_t  __attribute__ ((unused)) the_cores[] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 
  };
#  else
  static uint8_t  __attribute__ ((unused)) the_cores[] = {
    0, 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, 
  };
#  endif