Possible undefined behavior with arm64

[jlmelville]

I maintain the R wrapper for hnswlib at https://cran.r-project.org/package=RcppHNSW. Today I received a message from CRAN indicating that they had found an undefined behavior error running UBSan on an M1 Mac:

../inst/include/hnswalg.h:1203:16: runtime error: store to misaligned address 0x62a000078294 for type 'labeltype *' (aka 'unsigned long *'), which requires 8 byte alignment
0x62a000078294: note: pointer points here
  00 00 00 00 00 00 00 00  00 00 00 00 be be be be  be be be be be be be be  be be be be be be be be
              ^ 
    #0 0x00010bd29940 in hnswlib::HierarchicalNSW<float>::addPoint(void const*, unsigned long, int)+0x16e4 (RcppHNSW.so:arm64+0x5d940)
    #1 0x00010bd1aecc in hnswlib::HierarchicalNSW<float>::addPoint(void const*, unsigned long, bool)+0x5a4 (RcppHNSW.so:arm64+0x4eecc)
    #2 0x00010bd5b374 in Hnsw<float, hnswlib::L2Space, false>::addItemImpl(std::__1::vector<float, std::__1::allocator<float>>&, unsigned long)+0x88 (RcppHNSW.so:arm64+0x8f374)
    #3 0x00010bd5fe6c in Hnsw<float, hnswlib::L2Space, false>::addItems(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&)::'lambda'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const+0x350 (RcppHNSW.so:arm64+0x93e6c)
    #4 0x00010bd5f3b8 in void RcppPerpendicular::parallel_for<Hnsw<float, hnswlib::L2Space, false>::addItems(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&)::'lambda'(unsigned long, unsigned long)>(unsigned long, unsigned long, Hnsw<float, hnswlib::L2Space, false>::addItems(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&)::'lambda'(unsigned long, unsigned long)&, unsigned long, unsigned long)+0x288 (RcppHNSW.so:arm64+0x933b8)
    #5 0x00010bcd119c in Hnsw<float, hnswlib::L2Space, false>::addItems(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&)+0x2cc (RcppHNSW.so:arm64+0x519c)
    #6 0x00010bd652d4 in SEXPREC* Rcpp::internal::call_impl<Rcpp::CppMethodImplN<false, Hnsw<float, hnswlib::L2Space, false>, void, Rcpp::Matrix<14, Rcpp::PreserveStorage> const&>::operator()(Hnsw<float, hnswlib::L2Space, false>*, SEXPREC**)::'lambda'(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&), void, Rcpp::Matrix<14, Rcpp::PreserveStorage> const&, 0, (void*)0>(Rcpp::CppMethodImplN<false, Hnsw<float, hnswlib::L2Space, false>, void, Rcpp::Matrix<14, Rcpp::PreserveStorage> const&>::operator()(Hnsw<float, hnswlib::L2Space, false>*, SEXPREC**)::'lambda'(Rcpp::Matrix<14, Rcpp::PreserveStorage> const&) const&, SEXPREC**, Rcpp::internal::type_pack<void, Rcpp::Matrix<14, Rcpp::PreserveStorage> const&>, Rcpp::traits::index_sequence<0>)+0x1b8 (RcppHNSW.so:arm64+0x992d4)
    #7 0x00010bd64ea4 in Rcpp::CppMethodImplN<false, Hnsw<float, hnswlib::L2Space, false>, void, Rcpp::Matrix<14, Rcpp::PreserveStorage> const&>::operator()(Hnsw<float, hnswlib::L2Space, false>*, SEXPREC**)+0xf0 (RcppHNSW.so:arm64+0x98ea4)
    #8 0x00010bce8c34 in Rcpp::class_<Hnsw<float, hnswlib::L2Space, false>>::invoke_void(SEXPREC*, SEXPREC*, SEXPREC**, int)+0x2a8 (RcppHNSW.so:arm64+0x1cc34)
    #9 0x00010ad22e5c in CppMethod__invoke_void(SEXPREC*)+0xf4 (Rcpp.so:arm64+0x3ee5c)
    #10 0x000102782fcc in do_External dotcode.c:576
    #11 0x000102978b98 in Rf_eval eval.c:1260
    #12 0x00010298d408 in do_begin eval.c:2992
    #13 0x000102978838 in Rf_eval eval.c:1232
    #14 0x00010298360c in R_execClosure eval.c:2389
    #15 0x00010297eb2c in applyClosure_core eval.c:2302
    #16 0x0001029d336c in bcEval_loop eval.c:8103
    #17 0x00010297a2a8 in bcEval eval.c:7515
    #18 0x00010297844c in Rf_eval eval.c:1167
    #19 0x00010298360c in R_execClosure eval.c:2389
    #20 0x00010297eb2c in applyClosure_core eval.c:2302
    #21 0x000102978d64 in Rf_eval eval.c:1280
    #22 0x000102991730 in do_set eval.c:3581
    #23 0x000102978838 in Rf_eval eval.c:1232
    #24 0x000102accc90 in Rf_ReplIteration main.c:264
    #25 0x000102ad0cf4 in R_ReplConsole main.c:317
    #26 0x000102ad0af0 in run_Rmainloop main.c:1235
    #27 0x000102ad0e10 in Rf_mainloop main.c:1242
    #28 0x000100ff55ec in main Rmain.c:29
    #29 0x00018435dd50 in start+0x1c0c (dyld:arm64e+0x8d50)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../inst/include/hnswalg.h:1203:16 

The error is at:

hnswlib/hnswlib/hnswalg.h

Line 1202 in d9b3608

memcpy(getExternalLabeLp(cur_c), &label, sizeof(labeltype));

I think what is happening here is that with default M = 16, the link block is 32 * 4 + 4 = 132 bytes. The example data above uses data with 4 float features, so the data block is 16 bytes and hence the label is at offset 148. That is not 8-byte aligned for labeltype == size_t so the cast to labeltype* is triggering the UBSan.

I think the safe fix is to change the line to:

setExternalLabel(cur_c, label);

I was able to reproduce this locally on Linux using clang++ -std=gnu++17 -U_FORTIFY_SOURCE -fsanitize=undefined -fno-sanitize-recover=undefined -fno-omit-frame-pointer.

No PR for this yet, because I haven't actually reproduced this directly in the hnswlib repo (my build goes through the R ecosystem toolchain). But happy to work on one if this seems real.