utsaslab / RECIPE

RECIPE : high-performance, concurrent indexes for persistent memory (SOSP 2019)
Apache License 2.0
197 stars 46 forks source link

Fix bug of memcmp of string keys whose length mod 8 < 4 #22

Closed g4197 closed 2 years ago

g4197 commented 2 years ago

The original way for P-Masstree to identify whether two strings are equal is using memcmp to compare only length-of-string bytes. However, if these strings are all of the length of 9 bytes, for bswap performed, the last byte of them are actually at the MSB of the second uint64_t. Therefore, we should compare fully on all these uint64_ts, not just length-of-string bytes.

Code which can cause error can be like this:

#include <iostream>
#include "masstree.h"
using namespace std;

int main() {
    masstree::masstree *tree = new masstree::masstree();
    auto info = tree->getThreadInfo();
    char *s1 = "123456789";
    tree->put(s1, 123, info);
    char *s2 = "123456780";
    tree->put(s2, 456, info);
    printf("%ld\n", (int64_t)tree->get(s1, info));
    printf("%ld\n", (int64_t)tree->get(s2, info));
}

Expected output:

123
456

Actual output:

456
456
SeKwonLee commented 2 years ago

@g4197, thank you for the contribution.