Bug 15679 - Segfault when printing deeply nested lists
Summary: Segfault when printing deeply nested lists
Status: CLOSED FIXED
Alias: None
Product: R
Classification: Unclassified
Component: Low-level (show other bugs)
Version: R 3.0.2
Hardware: x86_64/x64/amd64 (64-bit) Linux-Ubuntu
: P5 normal
Assignee: R-core
URL:
Depends on:
Blocks:
 
Reported: 2014-02-22 02:25 UTC by jmstuckman
Modified: 2014-03-05 12:51 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description jmstuckman 2014-02-22 02:25:05 UTC
I have encountered a consistently reproducible situation where printing deeply nested lists (~20 lists deep) segfaults, but only if the keys of the list elements have a certain number of characters. If the keys are too long or too short, then printing the list doesn't segfault, no matter how deeply the list is nested.

The segfault only occurs when printing the list with the print() function, or the default printer on the R command line. The act of creating this list does not cause a segfault, nor does viewing it with str(). Although the simple example that I include seems pointless, this is occurring in a real-world application that implements a tree data structure using lists.

I am using the precompiled version of R for Ubuntu from the CRAN APT source. The bug has been reproduced by using the same commands on other machines running the same version of R; however, I could not reproduce it on a machine running R 2.15.1. The machines are running Ubuntu 12.04.

*****
First, I start R and define a badstructure() function, which creates the offending data structure:
*****

R

R version 3.0.2 (2013-09-25) -- "Frisbee Sailing"
Copyright (C) 2013 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

  Natural language support but running in an English locale

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> sessionInfo()
R version 3.0.2 (2013-09-25)
Platform: x86_64-pc-linux-gnu (64-bit)

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C
 [9] LC_ADDRESS=C               LC_TELEPHONE=C
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base
> version
platform       x86_64-pc-linux-gnu
arch           x86_64
os             linux-gnu
system         x86_64, linux-gnu
status
major          3
minor          0.2
year           2013
month          09
day            25
svn rev        63987
language       R
version.string R version 3.0.2 (2013-09-25)
nickname       Frisbee Sailing
> badstructure <- function(depth,key)
+ {
+ if (depth==1) ch<-list()
+ else ch<-list(badstructure(depth-1,key))
+ r<-list()
+ r[[key]]<-ch
+ r
+ }
>

*****
I then invoke badstructure() with a case that does *not* crash, because the key of the list element has the wrong number of characters to induce the bug.
*****

> badstructure(30,"childre") #does not crash
$childre
$childre[[1]]
$childre[[1]]$childre
$childre[[1]]$childre[[1]]
$childre[[1]]$childre[[1]]$childre
$childre[[1]]$childre[[1]]$childre[[1]]
$childre[[1]]$childre[[1]]$childre[[1]]$childre
......

*****
I then invoke badstructure() with a longer key, which induces the error and crashes R while printing the list
*****

badstructure(20,"children") #crashes
$children
$children[[1]]
$children[[1]]$children
$children[[1]]$children[[1]]
$children[[1]]$children[[1]]$children
$children[[1]]$children[[1]]$children[[1]]
$children[[1]]$children[[1]]$children[[1]]$children
$children[[1]]$children[[1]]$children[[1]]$children[[1]]
...snip...
$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$children[[1]]$...[[1]]
list()

*** buffer overflow detected ***: /usr/lib/R/bin/exec/R terminated
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(__fortify_fail+0x37)[0x7f08a9192f47]
/lib/x86_64-linux-gnu/libc.so.6(+0x109e40)[0x7f08a9191e40]
/usr/lib/R/lib/libR.so(+0x132ffe)[0x7f08a9797ffe]
/usr/lib/R/lib/libR.so(+0x134093)[0x7f08a9799093]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
/usr/lib/R/lib/libR.so(+0x133f00)[0x7f08a9798f00]
/usr/lib/R/lib/libR.so(+0x1325eb)[0x7f08a97975eb]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:01 55189053                           /usr/lib/R/bin/exec/R
00600000-00601000 r--p 00000000 08:01 55189053                           /usr/lib/R/bin/exec/R
00601000-00602000 rw-p 00001000 08:01 55189053                           /usr/lib/R/bin/exec/R
01304000-02c55000 rw-p 00000000 00:00 0                                  [heap]
7f08a4bb1000-7f08a4be6000 r-xp 00000000 08:01 55055996                   /usr/lib/x86_64-linux-gnu/libquadmath.so.0.0.0
7f08a4be6000-7f08a4de5000 ---p 00035000 08:01 55055996                   /usr/lib/x86_64-linux-gnu/libquadmath.so.0.0.0
7f08a4de5000-7f08a4de6000 r--p 00034000 08:01 55055996                   /usr/lib/x86_64-linux-gnu/libquadmath.so.0.0.0
7f08a4de6000-7f08a4de7000 rw-p 00035000 08:01 55055996                   /usr/lib/x86_64-linux-gnu/libquadmath.so.0.0.0
7f08a4de7000-7f08a4dfc000 r-xp 00000000 08:01 5242924                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f08a4dfc000-7f08a4ffb000 ---p 00015000 08:01 5242924                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f08a4ffb000-7f08a4ffc000 r--p 00014000 08:01 5242924                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f08a4ffc000-7f08a4ffd000 rw-p 00015000 08:01 5242924                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7f08a4ffd000-7f08a5111000 r-xp 00000000 08:01 55056231                   /usr/lib/x86_64-linux-gnu/libgfortran.so.3.0.0
7f08a5111000-7f08a5311000 ---p 00114000 08:01 55056231                   /usr/lib/x86_64-linux-gnu/libgfortran.so.3.0.0
7f08a5311000-7f08a5312000 r--p 00114000 08:01 55056231                   /usr/lib/x86_64-linux-gnu/libgfortran.so.3.0.0
7f08a5312000-7f08a5314000 rw-p 00115000 08:01 55056231                   /usr/lib/x86_64-linux-gnu/libgfortran.so.3.0.0
7f08a5314000-7f08a5bf9000 r-xp 00000000 08:01 55187178                   /usr/lib/lapack/liblapack.so.3gf.0
7f08a5bf9000-7f08a5df8000 ---p 008e5000 08:01 55187178                   /usr/lib/lapack/liblapack.so.3gf.0
7f08a5df8000-7f08a5df9000 r--p 008e4000 08:01 55187178                   /usr/lib/lapack/liblapack.so.3gf.0
7f08a5df9000-7f08a5dfd000 rw-p 008e5000 08:01 55187178                   /usr/lib/lapack/liblapack.so.3gf.0Aborted (core dumped)

*****
Here are some other cases I tested with badstructure(), some which crash R and some that do not. Note that changing the length of the key affects if it crashes, and with some key lengths, very deep structures can be printed without a crash
*****

badstructure(99,"childre") #does not crash
badstructure(20,"childrenn") #does not crash
badstructure(30,"childr") #crashes
Comment 1 jmstuckman 2014-02-22 02:35:46 UTC
Also, note that, although I describe the problem as a "segfault", "buffer overflow detected" is the actual error I experience when running all these cases.
Comment 2 Brian Ripley 2014-03-05 12:51:06 UTC
A buffer was sized not allowing for the terminator.  Fixed for R 3.1.0.

However, I cannot reproduce it on that plafrom without ASAN: the allocation is normally rounded up to a multiple of 8.