Thought: saving users from themselves in macros that explode

#1

You do NOT want to attempt to compile the following snippet:

macro_rules! blowup {
  ([$($t:tt)+]) => { blowup!{[ $($t:tt)+ ]} }; // note the :tt !
}

fn main() {
  blowup!([a]);
}

(note: the brackets are only there to work around a bug fixed in #52145 which slows down the parsing of $($t:tt)+)

If you try to build this and are on linux with a reasonably-sized swap partition, you are very likely to send yourself into complete and utter turmoil. You’ve probably experienced this before doing something else similarly dumb:

  • The program eventually requires so much memory (and is using it so actively) that memory for other absolutely essential things (like your window manager) are paged out to swap, causing your system to stop responding.
  • Soon, the program requires so much memory that not even all of its own memory can fit in physical memory. The program’s execution is slowed down so much by constant page faults that it can’t even reach the point where it would OOM.
  • …so basically you find yourself with a very warm brick for a few hours (or until you shut it off).

The prevailing philosophy in most circles is:

Well, then don’t do that!

but you know as well as I know that these things do not usually happen on purpose!


So maybe the compiler can help. Mind, we don’t have to solve the halting problem, all we need here is bang-for-the-buck; we want to head-off common deadly mistakes, like an extra :tt in an incremental muncher. Rust already has a #[recursion_limit] to help combat some forms of rogue macros, but it doesn’t help much with the above example.

A strawman proposal

@limira in this comment on #51754 suggests the following:

  1. Define a constant (like recursion_limit), maybe its name is: max_macro_grow_factor = 1024.
  2. Record the first number of tokens: n
  3. At each recursive call, check the new number of tokens: m
  4. If m > n * max_macro_grow_factor then
  • stop the macro-expansion process
  • report error to user
  • suggest them to check the involving rules
  • suggest them to increase max_macro_grow_factor = 2048 if they are sure there is no problem with their macro.

I’m going to push this forward as a starter for discussion. I don’t think that this precisely is the way to go, as there are subtleties like

  • what if a macro has no tokens as input?
  • it is common for macros that take small inputs to expand to very large outputs composed largely of fixed tokens
  • what about backwards compatibility? Is there a reasonable default factor we can pick such that no existing legitimately-working macro is liable to exceed it?

so I’m opening this thread as a place to toss around ideas. Any thoughts?

2 Likes

Proposal: Borrow #run idea from JAI
#2

Set a memory limit?

1 Like

#3

It would be nice if the limit was program-dependant, rather than platform dependant. That’s my problem with memory limits.

In general, I believe NFA regex parsers can explore an exponential number of pathes. Depending on the order of exploring paths, I think we could end up using exponential space in our macros parser (it’s basically a breath first search).

We could switch to something like depth-first search. Then you would only use linear memory and would just run into the recursion limit, right? On the other hand, we have the normal problems with DFS…

0 Likes

#4

This however is not a problem of exponential solution space. Each time blowup! expands it takes time and memory that is linear in the input; but the input itself grows exponentially with each call.

(but geeze, I wonder… are there pathological macros out there that the macro parser generates an exponential number of paths for? ISTM that the parser is too averse to ambiguities for this to actually occur)

0 Likes

#5

Would this be prevented by setting a maximum length of the macro input? One of the recursive calls would probably fail then. I don’t really see why we need to compute a growth rate etc instead of having a static limit.

1 Like

#6

I would still rather the limit be program dependant.

0 Likes

Proposal: Borrow #run idea from JAI
#7

I’d like to brag (let’s be honest here :)) ; ok, I’m also hoping that someone finds this useful) that while I’m not using a swap (disabled support in kernel) and with the anti-freeze-OS-when-memory-pressure linux kernel patch (aka le9d.patch) on 16G RAM, it takes 3mins 1sec for it to run(due to how slow blowup is eating memory) and then instantly get OOM-killed.
I haven’t tried WITH swap! but I can imagine some serious HDD thrashing(even with le9d.patch, or even because of it! WARNING: do not use le9d.patch if you use swap!) …

/tmp/blo 
$ time cargo run
!! LD_LIBRARY_PATH=/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage2/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage1/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage2/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage1/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib:
!! Executing '/home/xftroxgpx/build/2nonpkgs/rust.stuff/cargo/cargo//target/release//cargo' in pwd='/tmp/blo' with args: 'run'
   Compiling blo v0.1.0 (/tmp/blo)
!! LD_LIBRARY_PATH=/tmp/blo/target/debug/deps:/home/xftroxgpx/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage2/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage1/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage2/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/build/2nonpkgs/rust.stuff/rust/rust/build/x86_64-unknown-linux-gnu/stage1/lib/rustlib/x86_64-unknown-linux-gnu/lib:/home/xftroxgpx/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib:
!! Executing '/home/xftroxgpx/.cargo/bin/rustc' in pwd='/tmp/blo' with args: '--edition=2018 --crate-name blo /tmp/blo/src/main.rs --color always --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=7ec1425a3afaa712 -C extra-filename=-7ec1425a3afaa712 --out-dir /tmp/blo/target/debug/deps -C incremental=/tmp/blo/target/debug/incremental -L dependency=/tmp/blo/target/debug/deps'
error: Could not compile `blo`.

Caused by:
  process didn't exit successfully: `rustc --edition=2018 --crate-name blo /tmp/blo/src/main.rs --color always --crate-type bin --emit=dep-info,link -C debuginfo=2 -C metadata=7ec1425a3afaa712 -C extra-filename=-7ec1425a3afaa712 --out-dir /tmp/blo/target/debug/deps -C incremental=/tmp/blo/target/debug/incremental -L dependency=/tmp/blo/target/debug/deps` (signal: 9, SIGKILL: kill)

real	3m1.251s
user	2m47.760s
sys	0m9.656s

dmesg:

[90226.015042] rustc invoked oom-killer: gfp_mask=0x6280ca(GFP_HIGHUSER_MOVABLE|__GFP_ZERO), order=0, oom_score_adj=0
[90226.015049] CPU: 2 PID: 23149 Comm: rustc Kdump: loaded Tainted: G          I       5.0.0-rc1-gbfeffd155283 #33
[90226.015051] Hardware name: LENOVO Sabine/Torpedo, BIOS 54CN18WW 07/20/2011
[90226.015052] Call Trace:
[90226.015059]  dump_stack+0x46/0x60
[90226.015063]  dump_header+0x4f/0x369
[90226.015065]  ? sched_clock_local+0x12/0x90
[90226.015068]  oom_kill_process.cold.7+0xb/0x1e0
[90226.015070]  out_of_memory+0x195/0x560
[90226.015072]  __alloc_pages_nodemask+0xbbe/0xf00
[90226.015076]  alloc_pages_vma+0xa9/0x2a0
[90226.015078]  __handle_mm_fault+0xd7d/0x17b0
[90226.015080]  handle_mm_fault+0xee/0x270
[90226.015083]  __do_page_fault+0x188/0x430
[90226.015086]  ? page_fault+0x5/0x20
[90226.015087]  page_fault+0x1b/0x20
[90226.015090] RIP: 0033:0x7f421868821b
[90226.015093] Code: 8d 34 39 49 89 75 60 48 8d 15 61 ca 13 00 49 39 d5 0f 95 c2 0f b6 d2 48 c1 e2 02 4c 09 fa 48 83 ca 01 48 89 51 08 48 83 c8 01 <48> 89 46 08 e9 ef fe ff ff 48 8b 72 28 48 8b 7e 08 48 89 fa 48 83
[90226.015095] RSP: 002b:00007f421210b430 EFLAGS: 00010202
[90226.015097] RAX: 0000000000000f01 RBX: fffffffffffffec0 RCX: 00007f3ea58b6ff0
[90226.015098] RDX: 0000000000000115 RSI: 00007f3ea58b7100 RDI: 0000000000000004
[90226.015099] RBP: 00007f421210b4f0 R08: 0000000000000003 R09: 00007f4204000080
[90226.015100] R10: 00007f42040008d0 R11: 000000000000000f R12: 00007f4204000080
[90226.015101] R13: 00007f4204000020 R14: 0000000000000000 R15: 0000000000000110
[90226.015103] Mem-Info:
[90226.015108] active_anon:3417110 inactive_anon:32950 isolated_anon:0
                active_file:317214 inactive_file:9 isolated_file:0
                unevictable:8 dirty:212 writeback:0 unstable:0
                slab_reclaimable:77419 slab_unreclaimable:16944
                mapped:77330 shmem:33495 pagetables:12686 bounce:0
                free:34214 free_pcp:210 free_cma:0
[90226.015112] Node 0 active_anon:13668440kB inactive_anon:131800kB active_file:1268856kB inactive_file:36kB unevictable:32kB isolated(anon):0kB isolated(file):0kB mapped:309320kB dirty:848kB writeback:0kB shmem:133980kB shmem_thp: 0kB shmem_pmdmapped: 0kB anon_thp: 925696kB writeback_tmp:0kB unstable:0kB all_unreclaimable? yes
[90226.015114] Node 0 DMA free:15900kB min:68kB low:84kB high:100kB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:0kB writepending:0kB present:15984kB managed:15900kB mlocked:0kB kernel_stack:0kB pagetables:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB
[90226.015118] lowmem_reserve[]: 0 2810 15303 15303
[90226.015120] Node 0 DMA32 free:62176kB min:12396kB low:15492kB high:18588kB active_anon:2856340kB inactive_anon:40kB active_file:0kB inactive_file:88kB unevictable:0kB writepending:0kB present:3119616kB managed:2923008kB mlocked:0kB kernel_stack:16kB pagetables:2968kB bounce:0kB free_pcp:744kB local_pcp:488kB free_cma:0kB
[90226.015123] lowmem_reserve[]: 0 0 12492 12492
[90226.015125] Node 0 Normal free:58780kB min:59212kB low:72988kB high:86764kB active_anon:10811848kB inactive_anon:131760kB active_file:1268800kB inactive_file:84kB unevictable:32kB writepending:848kB present:13090816kB managed:12797060kB mlocked:32kB kernel_stack:8784kB pagetables:47776kB bounce:0kB free_pcp:96kB local_pcp:44kB free_cma:0kB
[90226.015128] lowmem_reserve[]: 0 0 0 0
[90226.015130] Node 0 DMA: 1*4kB (U) 1*8kB (U) 1*16kB (U) 0*32kB 2*64kB (U) 1*128kB (U) 1*256kB (U) 0*512kB 1*1024kB (U) 1*2048kB (M) 3*4096kB (M) = 15900kB
[90226.015136] Node 0 DMA32: 167*4kB (U) 265*8kB (UM) 285*16kB (U) 245*32kB (U) 175*64kB (U) 98*128kB (U) 61*256kB (U) 13*512kB (U) 1*1024kB (U) 0*2048kB 0*4096kB = 62228kB
[90226.015142] Node 0 Normal: 2225*4kB (UME) 527*8kB (UE) 966*16kB (UME) 691*32kB (UME) 79*64kB (UME) 27*128kB (ME) 0*256kB 0*512kB 0*1024kB 0*2048kB 0*4096kB = 59196kB
[90226.015148] Node 0 hugepages_total=0 hugepages_free=0 hugepages_surp=0 hugepages_size=1048576kB
[90226.015150] Node 0 hugepages_total=0 hugepages_free=0 hugepages_surp=0 hugepages_size=2048kB
[90226.015151] 350315 total pagecache pages
[90226.015152] 4056604 pages RAM
[90226.015152] 0 pages HighMem/MovableOnly
[90226.015153] 122612 pages reserved
[90226.015154] 0 pages cma reserved
[90226.015155] Tasks state (memory values in pages):
[90226.015155] [  pid  ]   uid  tgid total_vm      rss pgtables_bytes swapents oom_score_adj name
[90226.015160] [    244]     0   244   385365     4023  3076096        0             0 systemd-journal
[90226.015163] [    272]     0   272     9930     1813   102400        0         -1000 systemd-udevd
[90226.015165] [    424]    81   424     2788     1072    65536        0          -900 dbus-daemon
[90226.015167] [    427]     0   427      606       21    45056        0             0 gpm
[90226.015169] [    430]     0   430     7361     1542    94208        0             0 systemd-logind
[90226.015171] [    494]     0   494    12301      836   135168        0             0 login
[90226.015173] [    622]  1000   622     8250     2095   102400        0             0 systemd
[90226.015175] [    623]  1000   623    17413      501   163840        0             0 (sd-pam)
[90226.015177] [    632]  1000   632     4545     3658    77824        0             0 bash
[90226.015179] [    783]  1000   783     1807      881    49152        0             0 startx
[90226.015181] [    805]  1000   805     1983      274    57344        0             0 xinit
[90226.015183] [    806]  1000   806   102012    21360   462848        0             0 Xorg
[90226.015185] [    811]  1000   811   141222    13898   421888        0             0 xfce4-session
[90226.015187] [    815]  1000   815     2786      715    57344        0             0 dbus-daemon
[90226.015189] [    819]  1000   819    77595     1584   102400        0             0 at-spi-bus-laun
[90226.015191] [    825]  1000   825     2737     1041    53248        0             0 dbus-daemon
[90226.015192] [    828]  1000   828    42521     1592   102400        0             0 at-spi2-registr
[90226.015194] [    831]  1000   831    57836     1426    77824        0             0 xfconfd
[90226.015196] [    838]   102   838   494820     5670   229376        0             0 polkitd
[90226.015198] [    854]  1000   854     1453      119    45056        0             0 ssh-agent
[90226.015200] [    859]  1000   859    39185      827    65536        0             0 gpg-agent
[90226.015202] [    862]  1000   862   127425    18420   458752        0             0 xfwm4
[90226.015203] [    866]  1000   866    76923     8686   241664        0             0 xfce4-panel
[90226.015205] [    869]  1000   869    74053     5454   212992        0             0 Thunar
[90226.015207] [    871]  1000   871    76902     8493   245760        0             0 xfdesktop
[90226.015209] [    873]  1000   873   119087     9506   266240        0             0 xfce4-terminal
[90226.015211] [    874]  1000   874   120220    20772   368640        0             0 xfce4-terminal
[90226.015213] [    885]  1000   885    53662     5038   188416        0             0 polkit-gnome-au
[90226.015215] [    892]  1000   892   257244     3500   290816        0             0 pulseaudio
[90226.015216] [    894]  1000   894    55847     6567   208896        0             0 xfce4-power-man
[90226.015218] [    897]   133   897    38715      668    65536        0             0 rtkit-daemon
[90226.015220] [    905]  1000   905     2671      841    61440        0             0 dbus-daemon
[90226.015222] [    908]  1000   908    73800     6626   212992        0             0 xfce4-notifyd
[90226.015224] [    914]     0   914    65190     2312   122880        0             0 upowerd
[90226.015226] [    930]  1000   930   156584    11495   307200        0             0 panel-16-whiske
[90226.015228] [    931]  1000   931    63049     1677   122880        0             0 gsettings-helpe
[90226.015230] [    943]  1000   943    67215     7390   237568        0             0 panel-22-screen
[90226.015231] [    948]  1000   948    55081     5966   196608        0             0 panel-12-system
[90226.015233] [    952]  1000   952    52638     3720   176128        0             0 panel-24-cpugra
[90226.015235] [    963]  1000   963    64016     5139   225280        0             0 xfsettingsd
[90226.015237] [    971]  1000   971    84494    35561   442368        0             0 panel-20-cpufre
[90226.015239] [    976]     0   976    11307     1492   122880        0             0 sudo
[90226.015241] [    989]  1000   989    55080     5997   204800        0             0 panel-13-netloa
[90226.015242] [    995]  1000   995    55070     5947   204800        0             0 panel-10-diskpe
[90226.015244] [   1012]  1000  1012    55077     5934   208896        0             0 panel-4-diskper
[90226.015246] [   1014]  1000  1014    55302     6188   204800        0             0 panel-8-xfce4-s
[90226.015248] [   1022]  1000  1022    54817     5305   204800        0             0 panel-6-systray
[90226.015250] [   1026]  1000  1026    52353     4234   180224        0             0 panel-25-xfce4-
[90226.015252] [   1029]  1000  1029    55124     6121   204800        0             0 panel-2-actions
[90226.015253] [   1061]     0  1061     1839      889    49152        0             0 cpuvary
[90226.015255] [   1079]     0  1079     1839      751    49152        0             0 cpuvary
[90226.015257] [   1011]  1000  1011    39342     1841    65536        0             0 dconf-service
[90226.015259] [  32469]  1000 32469     4550     3712    81920        0             0 bash
[90226.015261] [   6899]  1000  6899     1807      853    53248        0             0 v
[90226.015263] [   6907]  1000  6907     4889     2624    81920        0             0 vim
[90226.015265] [  10189]  1000 10189     4558     3751    86016        0             0 bash
[90226.015267] [  10542]     0 10542    11307     1502   126976        0             0 sudo
[90226.015269] [  10619]     0 10619     1841      943    53248        0             0 freepagecachepa
[90226.015270] [  19277]  1000 19277     4555     3670    81920        0             0 bash
[90226.015272] [  19492]  1000 19492     1809      851    49152        0             0 v
[90226.015274] [  19500]  1000 19500     4891     2623    81920        0             0 vim
[90226.015276] [  12198]  1000 12198     1843      964    53248        0             0 ccachewatch
[90226.015278] [  29108]  1000 29108     4556     3700    81920        0             0 bash
[90226.015280] [  29695]  1000 29695     1842      981    49152        0             0 earl
[90226.015282] [  29703]  1000 29703   471717    29831   700416        0             0 vlc
[90226.015284] [  16882]  1000 16882     4556     3690    77824        0             0 bash
[90226.015286] [  17034]  1000 17034     1842      959    49152        0             0 chro2
[90226.015288] [  17079]  1000 17079     1842      963    53248        0             0 chro
[90226.015290] [  17085]  1000 17085     1336      191    53248        0             0 tail
[90226.015292] [  17086]  1000 17086     2468      557    57344        0             0 sed
[90226.015294] [  17087]  1000 17087     2468      557    61440        0             0 sed
[90226.015296] [  17092]  1000 17092   214921    46419   909312        0             0 chromium
[90226.015298] [  17137]  1000 17137    52121     8375   327680        0             0 chromium
[90226.015300] [  17168]  1000 17168    52121     1950   229376        0             0 chromium
[90226.015302] [  17302]  1000 17302   172144    23140  1085440        0           300 chromium
[90226.015304] [  17391]  1000 17391   165225    17645  1216512        0           300 chromium
[90226.015306] [  17419]  1000 17419   178886    25315  1507328        0           300 chromium
[90226.015308] [  17823]  1000 17823   212661    39830  2691072        0           300 chromium
[90226.015310] [  17937]  1000 17937   184832    20550  1208320        0           300 chromium
[90226.015312] [  18106]  1000 18106   185088    21443  1261568        0           300 chromium
[90226.015313] [  18123]  1000 18123   163993    21905  1196032        0           300 chromium
[90226.015315] [  22945]  1000 22945   205783    45995  2412544        0           300 chromium
[90226.015317] [  25232]  1000 25232   190036    28565  1519616        0           300 chromium
[90226.015319] [  30814]  1000 30814   196907    34834  1822720        0           300 chromium
[90226.015321] [   3535]  1000  3535   173888    19992  1081344        0           300 chromium
[90226.015323] [   6365]  1000  6365   190421    29221  1507328        0           300 chromium
[90226.015325] [  14817]  1000 14817   162486    15613   847872        0           300 chromium
[90226.015327] [  21025]  1000 21025   181996    23917  1544192        0           300 chromium
[90226.015329] [   9318]  1000  9318   196007    33045  1683456        0           300 chromium
[90226.015331] [  21166]  1000 21166     4589     3782    86016        0             0 bash
[90226.015333] [  22693]  1000 22693     4556     3722    81920        0             0 bash
[90226.015335] [  22783]  1000 22783     3403      952    69632        0             0 top
[90226.015337] [  23133]  1000 23133    43107     3760   118784        0             0 cargo
[90226.015339] [  23142]  1000 23142  3519630  3070599 24883200        0             0 rustc
[90226.015341] [  24817]  1000 24817     4736     3887    77824        0             0 bash
[90226.015343] [  25014]  1000 25014     1503      686    49152        0             0 watch
[90226.015345] [  29721]  1000 29721     1328      176    49152        0             0 sleep
[90226.015347] [  31821]  1000 31821     4556     3672    77824        0             0 bash
[90226.015349] [  31951]  1000 31951     1528      676    49152        0             0 dmesg
[90226.015351] [   2223]     0  2223     1325      191    49152        0             0 sleep
[90226.015353] [   2493]     0  2493     1325      174    49152        0             0 sleep
[90226.015354] oom-kill:constraint=CONSTRAINT_NONE,nodemask=(null),cpuset=/,mems_allowed=0,global_oom,task_memcg=/user.slice/user-1000.slice/session-c1.scope,task=rustc,pid=23142,uid=1000
[90226.015362] Out of memory: Kill process 23142 (rustc) score 782 or sacrifice child
[90226.015375] Killed process 23142 (rustc) total-vm:14078520kB, anon-rss:12236960kB, file-rss:45436kB, shmem-rss:0kB
[90226.404344] oom_reaper: reaped process 23142 (rustc), now anon-rss:0kB, file-rss:0kB, shmem-rss:0kB


0 Likes

closed #8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

0 Likes