Skip to content

Commit 6c976ac

Browse files
authored
GH-51198: [R] ALTREP crash in base R due to use-after-free (#51288)
### Rationale for this change Segfault triggered in certain circumstances when creating an ALTREP string column and garbage collection runs ### What changes are included in this PR? Cache string ALTREP value pointer to prevent problematic reallocation after garbage collection ### Are these changes tested? Yeah ### Are there any user-facing changes? Increased memory usage in some circumstances but see benchmarks below * GitHub Issue: #51198 Authored-by: Nic Crane <[email protected]> Signed-off-by: Nic Crane <[email protected]>
1 parent 7299fdc commit 6c976ac

2 files changed

Lines changed: 162 additions & 8 deletions

File tree

‎r/src/altrep.cpp‎

Lines changed: 97 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -857,29 +857,111 @@ struct AltrepVectorString : public AltrepVectorBase<AltrepVectorString<Type>> {
857857
std::string_view view_;
858858
};
859859

860-
// Get a single string as a CHARSXP SEXP
861-
static SEXP Elt(SEXP alt, R_xlen_t i) {
862-
if (Base::IsMaterialized(alt)) {
863-
return STRING_ELT(Representation(alt), i);
860+
// Strings created by Elt() must stay reachable for as long as the altrep
861+
// vector does: base R may hold the CHARSXP returned by STRING_ELT() across
862+
// a later allocation, and a CHARSXP that nothing references is collected
863+
// (GH-51198). Until the vector is materialized they are kept in fixed-size
864+
// STRSXP blocks hanging off a VECSXP stored in the protected slot of the
865+
// data1 external pointer. Blocks are allocated on first touch, so sparse
866+
// access costs one block rather than a full-length vector. Within a block,
867+
// R_BlankString marks a slot that has not been converted yet: the empty
868+
// string is a permanent singleton, so converting it again is harmless.
869+
static constexpr R_xlen_t kCacheBlockShift = 10;
870+
static constexpr R_xlen_t kCacheBlockSize = R_xlen_t(1) << kCacheBlockShift;
871+
static constexpr R_xlen_t kCacheBlockMask = kCacheBlockSize - 1;
872+
873+
// The cache block holding element i, allocating it (and the list of
874+
// blocks) on first use. Only valid while the vector is not materialized.
875+
static SEXP CacheBlock(SEXP alt, R_xlen_t i) {
876+
SEXP data1 = R_altrep_data1(alt);
877+
R_xlen_t length = GetChunkedArray(alt)->length();
878+
879+
SEXP blocks = R_ExternalPtrProtected(data1);
880+
if (Rf_isNull(blocks)) {
881+
R_xlen_t n_blocks = (length + kCacheBlockMask) >> kCacheBlockShift;
882+
blocks = PROTECT(Rf_allocVector(VECSXP, n_blocks));
883+
R_SetExternalPtrProtected(data1, blocks);
884+
UNPROTECT(1);
864885
}
865886

887+
R_xlen_t b = i >> kCacheBlockShift;
888+
SEXP block = VECTOR_ELT(blocks, b);
889+
if (Rf_isNull(block)) {
890+
R_xlen_t block_length = std::min(kCacheBlockSize, length - (b << kCacheBlockShift));
891+
block = PROTECT(Rf_allocVector(STRSXP, block_length));
892+
SET_VECTOR_ELT(blocks, b, block);
893+
UNPROTECT(1);
894+
}
895+
896+
return block;
897+
}
898+
899+
// Copy every string already produced by Elt() into `data2`, so that
900+
// materializing does not convert them a second time and so that CHARSXPs
901+
// handed out earlier stay reachable once the cache is dropped.
902+
static void CopyCacheInto(SEXP alt, SEXP data2) {
903+
SEXP blocks = R_ExternalPtrProtected(R_altrep_data1(alt));
904+
if (Rf_isNull(blocks)) {
905+
return;
906+
}
907+
908+
R_xlen_t n_blocks = Rf_xlength(blocks);
909+
for (R_xlen_t b = 0; b < n_blocks; b++) {
910+
SEXP block = VECTOR_ELT(blocks, b);
911+
if (Rf_isNull(block)) {
912+
continue;
913+
}
914+
915+
R_xlen_t offset = b << kCacheBlockShift;
916+
R_xlen_t block_length = Rf_xlength(block);
917+
for (R_xlen_t j = 0; j < block_length; j++) {
918+
SEXP s = STRING_ELT(block, j);
919+
if (s != R_BlankString) {
920+
SET_STRING_ELT(data2, offset + j, s);
921+
}
922+
}
923+
}
924+
}
925+
926+
// Convert the i'th string of the (not materialized) vector to a CHARSXP.
927+
// The result is not reachable from anywhere: the caller must anchor it
928+
// before doing anything that can allocate.
929+
static SEXP ConvertElt(SEXP alt, R_xlen_t i) {
866930
auto altrep_data =
867931
reinterpret_cast<ArrowAltrepData*>(R_ExternalPtrAddr(R_altrep_data1(alt)));
868932
auto resolve = altrep_data->locate(i);
869933
const auto& array =
870934
altrep_data->chunked_array()->chunk(static_cast<int>(resolve.chunk_index));
871935
auto j = resolve.index_in_chunk;
872936

873-
SEXP s = NA_STRING;
874937
RStringViewer& r_string_viewer = string_viewer();
875938
r_string_viewer.SetArray(array);
876939
// Note: we don't check GetBoolOption("arrow.skip_nul", false) here
877940
// because it is too expensive to do so. We do set this value whenever
878941
// an altrep string; however, there is a chance that this value could
879942
// be out of date by the time a value in the vector is accessed.
880943
r_string_viewer.reset_null_was_stripped();
881-
s = r_string_viewer.Convert(j);
882-
if (r_string_viewer.nul_was_stripped()) {
944+
return r_string_viewer.Convert(j);
945+
}
946+
947+
// Get a single string as a CHARSXP SEXP
948+
static SEXP Elt(SEXP alt, R_xlen_t i) {
949+
if (Base::IsMaterialized(alt)) {
950+
return STRING_ELT(Representation(alt), i);
951+
}
952+
953+
SEXP block = CacheBlock(alt, i);
954+
R_xlen_t j = i & kCacheBlockMask;
955+
SEXP s = STRING_ELT(block, j);
956+
if (s != R_BlankString) {
957+
return s;
958+
}
959+
960+
s = PROTECT(ConvertElt(alt, i));
961+
SET_STRING_ELT(block, j, s);
962+
UNPROTECT(1); // s: now reachable through the cache
963+
964+
if (string_viewer().nul_was_stripped()) {
883965
Rf_warning("Stripping '\\0' (nul) from character vector");
884966
}
885967

@@ -899,6 +981,11 @@ struct AltrepVectorString : public AltrepVectorBase<AltrepVectorString<Type>> {
899981
SEXP data2 = PROTECT(Rf_allocVector(STRSXP, chunked_array->length()));
900982
MARK_NOT_MUTABLE(data2);
901983

984+
// Reuse what Elt() has already converted, then fill in the rest. The
985+
// cache is dropped together with data1 below, so the CHARSXPs it holds
986+
// must be in data2 by then.
987+
CopyCacheInto(alt, data2);
988+
902989
R_xlen_t i = 0;
903990
RStringViewer& r_string_viewer = string_viewer();
904991
r_string_viewer.reset_null_was_stripped();
@@ -908,7 +995,9 @@ struct AltrepVectorString : public AltrepVectorBase<AltrepVectorString<Type>> {
908995

909996
auto ni = array->length();
910997
for (R_xlen_t j = 0; j < ni; j++, i++) {
911-
SET_STRING_ELT(data2, i, r_string_viewer.Convert(j));
998+
if (STRING_ELT(data2, i) == R_BlankString) {
999+
SET_STRING_ELT(data2, i, r_string_viewer.Convert(j));
1000+
}
9121001
}
9131002
}
9141003

‎r/tests/testthat/test-altrep.R‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -654,3 +654,68 @@ test_that("Materialized ALTREP arrays don't cause arrow to crash when attempting
654654
expect_equal(infer_type(b_int), int32())
655655
expect_equal(as_arrow_array(b_int), a_int)
656656
})
657+
658+
test_that("strings returned by ALTREP Elt() survive garbage collection", {
659+
# Base R may hold the CHARSXP returned by STRING_ELT() across an allocation,
660+
# so an unmaterialized ALTREP string vector must keep every string it has
661+
# handed out reachable (GH-51198). Reproducer adapted from
662+
# https://gist.github.com/traversc/a5204821451198d457edc38cceda9d90
663+
withr::local_options(list(arrow.use_altrep = TRUE))
664+
skip_on_cran()
665+
666+
# Build the string inside Arrow so that this R session never holds a CHARSXP
667+
# with these contents: the only one is the one Elt() creates. It is large so
668+
# that R returns its memory to the OS when it is freed, which turns a silent
669+
# read of freed memory into a crash.
670+
input <- call_function(
671+
"binary_repeat",
672+
Array$create("a"),
673+
Array$create(16L * 1024L * 1024L)
674+
)$as_vector()
675+
expect_true(is_arrow_altrep(input))
676+
expect_false(test_arrow_altrep_is_materialized(input))
677+
678+
# A latin1 target makes charmatch() allocate (for UTF-8 translation) while
679+
# it still holds the pointer to the element of `input`.
680+
target <- rawToChar(as.raw(c(rep.int(0x61L, 64L), 0xe9L)))
681+
Encoding(target) <- "latin1"
682+
target <- rep.int(target, 256L)
683+
684+
gctorture(TRUE)
685+
on.exit(gctorture(FALSE), add = TRUE)
686+
observed <- charmatch(input, target, nomatch = NA_integer_)
687+
# Turn torture off before the expectation: with a GC on every allocation a
688+
# single expect_identical() takes almost a minute instead of a fraction of a
689+
# second. The on.exit() above only covers the case where charmatch() errors.
690+
gctorture(FALSE)
691+
692+
expect_identical(observed, NA_integer_)
693+
})
694+
695+
test_that("ALTREP string vectors reuse cached strings when materializing", {
696+
skip_on_cran()
697+
withr::local_options(list(arrow.use_altrep = TRUE))
698+
values <- c("a", NA, "", "d", NA, "f")
699+
700+
for (x in list(Array$create(values), ChunkedArray$create(values[1:2], values[3:6]))) {
701+
alt <- x$as_vector()
702+
expect_true(is_arrow_altrep(alt))
703+
704+
# Element access goes through Elt() and fills the cache
705+
expect_identical(alt[c(1, 2, 3)], values[c(1, 2, 3)])
706+
expect_false(test_arrow_altrep_is_materialized(alt))
707+
708+
# Materializing must reuse the cached strings and convert only the rest
709+
expect_true(test_arrow_altrep_force_materialize(alt))
710+
expect_true(test_arrow_altrep_is_materialized(alt))
711+
expect_identical(alt, values)
712+
expect_identical(test_arrow_altrep_copy_by_element(alt), values)
713+
}
714+
715+
# Large string type shares the implementation
716+
alt <- Array$create(values, type = large_utf8())$as_vector()
717+
expect_true(is_arrow_altrep(alt))
718+
expect_identical(alt[c(6, 1)], values[c(6, 1)])
719+
expect_true(test_arrow_altrep_force_materialize(alt))
720+
expect_identical(alt, values)
721+
})

0 commit comments

Comments
 (0)