Missing keys

[1angkawi]

We found a missing keys issue recently. After inserted some keys, then iterate the table, and the number of items traversed is smaller than the size. However I cannot reproduce it stably. May I ask how to debug in this case? Is there any case the it will lead to missing keys? Thanks

[manugoyal]

Hi @1angkawi. That is certainly unexpected. I can try to help with debugging if you are able to provide some sort of reproduction (and perhaps the details of the machine you're using).

It is true that the size of the table (computed here) does not actually inspect the contents of the table, so it may be possible that some bug is causing the lock counters to get out of sync with the bucket contents. But I am not spotting anything from a quick inspection of the code.

Otherwise, maybe another debugging idea is just to print out the values of the elem_counters as they are updated in the code (generally here and here), and see if that aligns with the insertion of keys.

[acmore]

Hi @manugoyal Thanks for your reply. Actually I think the size by summing up the elem_counters are correct, because it equals to the actual key size. However, it has less keys when I try to iterate over the table.

I added a debug method to check the number of slots that are occupied:

  // Debug
  void debug_info() {
    size_t total = 0;

    for (size_t i = 0; i < buckets_.size(); i++) {
        const auto& bucket = buckets_[i];
        size_t count = 0;
        for (int s = 0; s < slot_per_bucket(); s++) {
                if (bucket.occupied(s)) {
                        count++;
                }
        }
        total += count;
    }
    std::cout << "table size: " << size() << ", actual size: " << total << "\n";
  }

And I can see that the size is greater than the total. And I did try to iterate the table again immediately after the first iteration, and sometimes the size is correct on the second iteration. Is it possible that there is some post operation that is still in progress after the insert_or_assign function returns?

Here is the cpu info of my machine:

Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   46 bits physical, 57 bits virtual
CPU(s):                          144
On-line CPU(s) list:             0-143
Thread(s) per core:              2
Core(s) per socket:              36
Socket(s):                       2
NUMA node(s):                    2
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           106
Model name:                      Intel(R) Xeon(R) Platinum 8352V CPU @ 2.10GHz
Stepping:                        6
CPU MHz:                         2100.000
CPU max MHz:                     3500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4200.00
Virtualization:                  VT-x
L1d cache:                       3.4 MiB
L1i cache:                       2.3 MiB
L2 cache:                        90 MiB
L3 cache:                        108 MiB
NUMA node0 CPU(s):               0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,
                                 130,132,134,136,138,140,142
NUMA node1 CPU(s):               1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119,121,123,125,127,129,
                                 131,133,135,137,139,141,143
Vulnerability Itlb multihit:     Not affected
Vulnerability L1tf:              Not affected
Vulnerability Mds:               Not affected
Vulnerability Meltdown:          Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Enhanced IBRS, IBPB conditional, RSB filling
Vulnerability Srbds:             Not affected
Vulnerability Tsx async abort:   Not affected
Flags:                           fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xto
                                 pology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand
                                  lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l3 invpcid_single intel_ppin ssbd mba ibrs ibpb stibp ibrs_enhanced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms
                                 invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb intel_pt avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local spl
                                 it_lock_detect wbnoinvd dtherm ida arat pln pts hwp hwp_act_window hwp_epp hwp_pkg_req avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg tme avx512_vpopcntdq la57 rdpid
                                 fsrm md_clear pconfig flush_l1d arch_capabilities

[manugoyal]

Is it possible that there is some post operation that is still in progress after the insert_or_assign function returns

Yes, since neither the size() method nor your debug method are locking the table, if there are any insertion/deletion/etc operations happening concurrently on the table, the returned size may not be completely up to date.

The safest way to check for consistency between table size and table contents is by locking the table. We have a locked_table API to do this, which also exposes an STL-compatible iterator interface over the table. So you should be able to check something like:

// Locks are released when the |locked_table| object goes out of scope.
auto locked_table = my_table.lock_table();
std::cout << "size() = " << locked_table.size() << "\n";
size_t total = 0;
for (const auto& [key, value] : locked_table) {
  std::cout << "key: " << key << " -> value: " << value << "\n";
  ++total;
}
std::cout << "total = " << total << "\n";