rust-lang / miri

An interpreter for Rust's mid-level intermediate representation
Apache License 2.0
4.6k stars 346 forks source link

memory leak deserializing Vec with serde #593

Closed nivkner closed 5 years ago

nivkner commented 5 years ago

when running this with miri, using cargo-miri, this example uses around 2.5 Gigabytes of ram as seen by the difference in system memory usage while executing the program.

static JSON: &str = r#"{"buffer":[-29,-42,-40,-37,-28,-5,-21,1,-24,-8,-20,4,-18,26,-24,44,-26,66,-30,86,-37,88,-41,72,-46,50,-31,28,23,14,64,16,51,26,32,34,39,42,48,35,58,0,72,-36,69,-59,58,-98,54,-124,36,-103,12,-110,5,-173,-19,-146,-59,-4,-42,51,1,-23,-6,-30,-6,45,46,47,70,6,55,19,60,38,62,42,47,61,46,40,42,-19,22,-34,6,-35,-50,-61,-141,-37,-171,17,-163,26,-180,46,-154,80,-63,48,-4,18,20,50,47,58,53,44,61,57,85,37,80,0,86,-8,106,-95,49,-213,-8,-131,47,49,63,40,-39,-69,-74,-37,-20,63,-12,58,-14,-12,25,-31,41,11,45,76,47,167,5,261,-37,277,-83,183,-172,35,-122,-79,138,-70,266,69,124,228,0,391,-29,594,-84,702,-78,627,-8,551,-13,509,13,372,120,352,125,622,127,691,223,362,126,386,-33,915,198,958,457,456,298,500,233,1027,469,1096,426,918,160,1067,141,1220,189,1245,164,1375,297,1378,503,1299,702,1550,929,1799,855,1752,547,1830,602,1928,832,1736,796,1735,933,1961,1385,1935,1562,2105,1485,2716,1449,2948,1305,2768,1205,2716,1346,2531,1450,2470,1653,3117,2111,3370,2176,2696,1947,2925,2305,3846,2658,2425,2184,-877,1981,-2261,2623,-1645,2908,-1876,2732,-2704,2953,-2484,3116,-2120,2954,-2442,3216,-2466,3499,-2192,3234,-2392,3361,-2497,3869,-2078,3772,-1858,3915,-2066,4438,-2285,2934,-2294,-280,-2066,-1762,-1992,-1412,-2298,-1535,-2399,-1789,-2223,-1419,-2244,-1334,-2092,-1476,-1777,-1396,-2014,-1571,-2199,-1574,-1843,-1167,-1910,-1446,-2007,-1818,-1506,-1331,-2526,-2048,-5535,-4573,-7148,-5828,-6422,-5327,-5840,-5488,-5992,-6144,-6014,-6164,-6109,-6234,-6271,-6388,-6288,-6156,-6517,-6249,-6794,-6602,-6822,-6418,-6788,-6245,-6490,-6560,-6394,-6794,-7920,-6937,-10397,-7140,-11428,-6972,-11019,-6610,-11141,-6665,-11913,-7046,-11979,-7235,-11599,-7015,-11854,-6912,-12161,-7441,-12136,-7761,-12861,-7292,-13390,-7254,-12345,-7809,-12490,-7463,-13983,-6969,-10489,-8465,-2382,-11054,1272,-12247,-270,-12060,-323,-12113,502,-12486,-697,-12251,-1086,-12141,-181,-13116,-670,-13509,-1173,-12592,-443,-12811,-449,-13698,-934,-12850,-747,-13083,-873,-15036,-1161,-11478,-1047,-2669,-1407,1006,-1658,-1146,-1195,-1297,-1421,-73,-1946,-977,-1590,-1499,-1577,-1010,-1862,-1256,-1389,-962,-1692,-509,-2613,-1317,-2087,-1359,-1997,-1034,-2891,-2024,-119,-84,5651,5723,8074,8306,7156,6870,6985,7106,7312,8403,7114,8096,7173,7848,7082,7827,6761,7189,6985,7368,7076,7835,6992,7297,7453,7260,7016,7755,6025,7429,8533,7352,14150,7628,17142,7077,16399,6947,15939,7475,16564,7069,16463,6882,16400,7602,17031,7233,16543,6517,15395,7018,15985,7104,16689,6869,15655,7622,16155,7198,17884,6022,14056,8856,5665,14484,1815,16782,3034,15786,3107,15664,2312,16517,2965,16443,3036,16120,2287,16584,2479,16720,2693,16073,2535,16159,2958,16609,3067,16086,2716,16579,3035,17752,3092,13704,2499,5265,2620,1452,2808,3024,2444,3275,2839,2267,3340,2857,2968,3232,3066,2867,3152,3072,2248,2961,2413,2807,3238,3237,2368,2699,2262,2392,3537,3339,827,823,-5020,-5359,-7095,-7857,-5973,-6274,-6208,-6279,-6934,-7181,-6893,-6647,-7146,-6687,-7026,-7328,-6451,-6924,-6763,-6535,-7109,-6639,-6926,-6559,-7188,-6799,-6727,-6955,-5786,-6554,-8543,-6796,-14465,-7190,-17356,-6641,-16372,-6529,-15941,-6898,-16526,-6434,-16219,-6520,-16222,-7449,-17077,-7097,-16665,-6476,-15675,-7026,-16498,-6848,-17147,-6271,-15894,-7069,-16266,-7032,-17817,-5991,-13796,-8594,-5421,-14349,-1649,-17288,-2847,-16525,-2974,-15945,-2324,-16482,-3022,-16593,-3097,-16451,-2420,-16780,-2649,-16641,-2836,-15900,-2660,-16214,-3050,-16827,-3111,-15993,-2741,-16151,-2994,-17537,-2933,-13812,-2314,-5216,-2475,-1125,-2648,-2801,-2290,-3285,-2796,-2243,-3415,-2642,-3109,-3000,-3271,-2839,-3408,-3161,-2497,-2876,-2603,-2570,-3351,-3173,-2416,-2832,-2235,-2408,-3405,-3186,-613,-768,5271,5201,7376,7644,6241,6176,6366,6275,6964,7124,6831,6508,6998,6566,6836,7230,6277,6777,6589,6376,6934,6536,6819,6494,7160,6749,6736,6900,5822,6476,8593,6747,14520,7204,17448,6637,16490,6483,16033,6906,16600,6511,16304,6568,16279,7438,17079,7072,16624,6463,15577,7028,16343,6877,16990,6331,15760,7121,16140,7023,17719,5944,13748,8575,5401,14336,1645,17210,2880,16419,3036,15896,2382,16483,3074,16584,3143,16425,2443,16782,2650,16695,2825,15978,2632,16272,3015,16880,3084,16096,2709,16289,2965,17641,2932,13887,2323,5330,2474,1286,2656,2954,2309,3410,2803,2373,3414,2795,3106,3151,3263,2952,3403,3241,2483,2969,2568,2681,3316,3245,2383,2837,2199,2390,3396,3165,641,706,-5230,-5323,-7307,-7790,-6136,-6317,-6268,-6419,-6884,-7278,-6766,-6666,-6976,-6731,-6853,-7406,-6308,-6958,-6636,-6553,-6978,-6703,-6829,-6647,-7156,-6883,-6737,-7017,-5814,-6581,-8575,-6833,-14490,-7270,-17411,-6699,-16466,-6539,-16016,-6931,-16571,-6504,-16257,-6551,-16202,-7408,-16983,-7021,-16545,-6410,-15512,-6976,-16305,-6803,-17017,-6243,-15820,-7037,-16197,-6923,-17802,-5820,-13840,-8455,-5475,-14227,-1724,-17099,-2923,-16314,-3008,-15801,-2362,-16392,-3088,-16506,-3163,-16356,-2503,-16700,-2717,-16605,-2855,-15904,-2710,-16226,-3108,-16870,-3089,-16101,-2747,-16257,-3087,-17584,-2975,-13868,-2324,-5343,-2548,-1275,-2673,-2917,-2213,-3363,-2694,-2311,-3251,-2744,-2867,-3129,-3034,-2939,-3190,-3234,-2346,-2964,-2639,-2658,-3558,-3241,-2670,-2892,-2453,-2437,-3564,-3175,-771,-779,5105,5171,7308,7655,6265,6204,6397,6288,7024,7172,6903,6586,7002,6627,6777,7308,6190,6889,6537,6465,7011,6613,6985,6631,7393,6934,7073,7072,6112,6615,8751,6859,14672,7282,17448,6652,16146,6448,15565,6899,16151,6547,15860,6591,16048,7446,17065,7064,16661,6368,15774,6857,16524,6677,16825,6071,15577,6900,16119,7040,17490,6118,13495,8696,5432,14446,1678,17366,3036,16488,3624,15834,3012,16382,3575,16465,3685,16301,2815,16708,2982,16679,3356,15952,2934,16049,3290,16352,3964,15605,3612,16222,3647,17764,4272,13865,3977,5384,3592,1580,3794,3243,3627,3670,3622,2758,4007,3130,3835,3294,3964,3065,4468,3408,3933,3234,3789,3118,4634,3643,4211,3174,4155,3176,5512,4400,2792,1730,-3702,-4499,-5940,-6691,-4265,-5094,-4381,-5215,-4918,-5746,-4217,-4871,-4402,-4981,-4479,-5525,-3732,-4968,-4118,-4924,-4300,-5349,-3422,-5021,-3876,-4886,-4087,-4860,-2790,-4254,-5025,-4196,-10898,-4415,-13419,-4007,-12198,-4121,-11995,-4413,-12471,-3808,-11937,-3920,-11792,-4583,-12284,-3776,-12085,-3107,-11421,-3583,-11226,-3081,-11157,-2768,-10580,-3914,-10424,-3197,-11040,-1715,-9822,-5144,-6189,-11154,-4236,-13029,-5134,-11598,-5507,-10949,-4921,-11142,-4999,-11180,-4883,-11184,-4366,-11090,-4548,-10887,-4818,-10708,-4866,-10534,-5253,-10272,-5179,-9894,-4633,-10029,-4773,-10382,-4977,-8674,-4668,-5292,-4651,-3928,-4629,-4465,-4312,-3994,-4459,-3528,-4570,-4400,-4272,-4601,-4482,-4035,-4627,-4334,-4080,-4498,-4045,-3835,-4204,-3526,-3695,-3646,-4045,-4101,-4856,-4628,-3338,-3235,-673,-508,28,147,-453,-639,11,0,8,-2,7,0,7,-3,11,-8,15,-9,17,-6,17,-5,13,-3,7,0,3,0,-2,0,-4,0,-4,-2,-6,0,-14,-2,-17,-4,-8,0,-7,5,-17,7,-18,10,-7,18,-2,25,-3,27,0,31,4,34,4,34,8,36,8,37,2,36,4,34,8,28,3,15,0,11,0,12,-5,8,-4,10,0,23,-4,31,-8,30,-2,30,0,26,-6,22,-6,20,-12,15,-19,10,-10,13,-14,6,-43,-13,-43,-16,-9,-12,-10,-29,-42,-40,-37,-28,-5,-21,1,-24,-8,-20,4,-18,26,-24,44,-26,66,-30,86,-37,88,-41,72,-46,50,-31,28,23,14,64,16,51,26,32,34,39,42,48,35,58,0,72,-36,69,-59,58,-98,54,-124,36,-103,12,-110,5,-173,-19,-146,-59,-4,-42,51,1,-23,-6,-30,-6,45,46,47,70,6,55,19,60,38,62,42,47,61,46,40,42,-19,22,-34,6,-35,-50,-61,-141,-37,-171,17,-163,26,-180,46,-154,80,-63,48,-4,18,20,50,47,58,53,44,61,57,85,37,80,0,86,-8,106,-95,49,-213,-8,-131,47,49,63,40,-39,-69,-74,-37,-20,63,-12,58,-14,-12,25,-31,41,11,45,76,47,167,5,261,-37,277,-83,183,-172,35,-122,-79,138,-70,266,69,124,228,0,391,-29,594,-84,702,-78,627,-8,551,-13,509,13,372,120,352,125,622,127,691,223,362,126,386,-33,915,198,958,457,456,298,500,233,1027,469,1096,426,918,160,1067,141,1220,189,1245,164,1375,297,1378,503,1299,702,1550,929,1799,855,1752,547,1830,602,1928,832,1736,796,1735,933,1961,1385,1935,1562,2105,1485,2716,1449,2948,1305,2768,1205,2716,1346,2531,1450,2470,1653,3117,2111,3370,2176,2696,1947,2925,2305,3846,2658,2425,2184,-877,1981,-2261,2623,-1645,2908,-1876,2732,-2704,2953,-2484,3116,-2120,2954,-2442,3216,-2466,3499,-2192,3234,-2392,3361,-2497,3869,-2078,3772,-1858,3915,-2066,4438,-2285,2934,-2294,-280,-2066,-1762,-1992,-1412,-2298,-1535,-2399,-1789,-2223,-1419,-2244,-1334,-2092,-1476,-1777,-1396,-2014,-1571,-2199,-1574,-1843,-1167,-1910,-1446,-2007,-1818,-1506,-1331,-2526,-2048,-5535,-4573,-7148,-5828,-6422,-5327,-5840,-5488,-5992,-6144,-6014,-6164,-6109,-6234,-6271,-6388,-6288,-6156,-6517,-6249,-6794,-6602,-6822,-6418,-6788,-6245,-6490,-6560,-6394,-6794,-7920,-6937,-10397,-7140,-11428,-6972,-11019,-6610,-11141,-6665,-11913,-7046,-11979,-7235,-11599,-7015,-11854,-6912,-12161,-7441,-12136,-7761,-12861,-7292,-13390,-7254,-12345,-7809,-12490,-7463,-13983,-6969,-10489,-8465,-2382,-11054,1272,-12247,-270,-12060,-323,-12113,502,-12486,-697,-12251,-1086,-12141,-181,-13116,-670,-13509,-1173,-12592,-443,-12811,-449,-13698,-934,-12850,-747,-13083,-873,-15036,-1161,-11478,-1047,-2669,-1407,1006,-1658,-1146,-1195,-1297,-1421,-73,-1946,-977,-1590,-1499,-1577,-1010,-1862,-1256,-1389,-962,-1692,-509,-2613,-1317,-2087,-1359,-1997,-1034,-2891,-2024,-119,-84,5651,5723,8074,8306,7156,6870,6985,7106,7312,8403,7114,8096,7173,7848,7082,7827,6761,7189,6985,7368]}"#;

use serde::Deserialize;

#[derive(Deserialize)]
struct DeriveStruct {
    buffer: Vec<i16>,
}

fn main() {
    let info: DeriveStruct = serde_json::from_str(JSON).unwrap();
    println!("{}", info.buffer.len());
}

I think this is a memory leak because when simply pushing the same amount of elements (1795), there is barely a difference in memory usage.

use serde::Deserialize;

#[derive(Default, Deserialize)]
struct DeriveStruct {
    buffer: Vec<i16>,
}

fn main() {
    let mut info = DeriveStruct::default();
    for i in 0..1795 {
        info.buffer.push(i);
    }
    println!("{}", info.buffer.len());
}

this problem was originally found with a program that doesn't use serde, but this is the smallest example I found.

rustc 1.33.0-nightly (60e825389 2018-12-28)
binary: rustc
commit-hash: 60e825389db3cb7421afb7015b28cb9436c79bba
commit-date: 2018-12-28
host: x86_64-unknown-linux-gnu
release: 1.33.0-nightly
LLVM version: 8.0
oli-obk commented 5 years ago

We do have a memory leak detector for leaks in the interpreted code. It only works on linux, but you should be getting an error if memory was leaked.

If it's a memory leak in miri, it might be related to something other than the actual interpretation. Is the leak amount related to the size of the json array?

nivkner commented 5 years ago

i ran the program with multiple configurations, here are the results:

value size (number of times the value repeats in buffer) memory (in Gigabytes)
0 1000 0.3
0 1500 0.6
0 2000 1.0
1500 1000 0.8
1500 1500 1.8
1500 2000 3.2

edit: changed column from repetitions to size and clarified

oli-obk commented 5 years ago

what is value and repetitions?

nivkner commented 5 years ago

i put a 1000 times the value 0 in the buffer for example

RalfJung commented 5 years ago

Is this max-RSS, or how do you measure memory consumption?

this problem was originally found with a program that doesn't use serde, but this is the smallest example I found.

If you had an example (even a bigger one) that does not depend on any other crates, that would be helpful.

oli-obk commented 5 years ago

Interpreting any serde related code could end up using a lot of memory because we're loading all the rlibs and metadata of those crates into miri in order to be able to evalute the MIR of the serde code. Why that would be affected by the size of the json is not clear to me.

nivkner commented 5 years ago

i pushed a version of the program that doesn't use serde here (it uses libc but only for the type aliases).

i measured the memory by monitoring the total memory usage, so for example:

with the browser closed i am on a stable 1.5 Gigabytes. when i run the program it rises to say 3.8 Gigabytes before the program is done, so the diff is what i write.

note that this is for measuring the serde example. the program i linked to uses a much bigger buffer (20736) so you might have to prepare to kill the process.

oli-obk commented 5 years ago

So... I'm assuming you have 4GB of RAM? Your system getting stuck is probably due to your system starting to offload any additional memory to disk (swap).

Do note that miri is a few orders of magnitude slower than executing your program directly. Also it uses a few multiples of the amount of memory that your program uses in debug mode. You might simply be seeing the overhead.

I suggest to run miri with small buffers and few repetitions. Even if that isn't what your real program does, it should still show most of the same behavior.

nivkner commented 5 years ago

@oli-obk i pushed a commit to the example that reuses the same stack-allocated buffer throughout the entire loop, the memory usage keeps growing like before.

I measured the memory usage like before, i killed the process when the system memory usage was at 7.6 (I have a 8 GB system), but it was still growing.

oli-obk commented 5 years ago

I'll do some investigating, but it might just be expected, especially with the stacked borrows impl that the max memory usage explodes, because every time you take an address a few elements are pushed onto some stacks. Even if those are popped, the memory stays allocated until the entire allocation becomes unused.

Always clearing the capacity of the various datastructures we have would alleviate that, but most likely negatively impact performance.

RalfJung commented 5 years ago

@nivkner Could you try running as cargo miri run -- -Zmiri-disable-validation to check if the memory usage is caused by Stacked Borrows?

However, Stacked Borrows should re-use memory when the items are popped and new items are pushed, so unless the stacks are for some reason growing really large I don't think this is it. My bet would be on the dead_alloc_map, which will just keep growing when things get allocated and deallocated again. There are probably clever ways to compress this...

I wonder if there is a good way to see which buffers are the ones that are growing so big.

nivkner commented 5 years ago

@RalfJung I ran the example with -Zmiri-disable-validation and the memory usage did not grow over time like with validation enabled

RalfJung commented 5 years ago

Thanks! Looks like my bet was wrong then.^^

That's still somewhat odd, why would it just keep growing?

RalfJung commented 5 years ago

It's definitely not memory still being used after the borrow stacks got popped, adding a shrink_to_fit does not make any noticeable difference (in the original example with serde).

RalfJung commented 5 years ago

https://github.com/solson/miri/pull/597 should help a lot -- on my system it cuts memory usage by 90%. Validation still almost doubles memory consumption, but that's way better than the factor of 15 or so that it used to cost before.^^

RalfJung commented 5 years ago

@nivkner you had another comment here that you deleted, saying my PR introduced a severe perf regression. Now the comment is gone. What's up with that?

nivkner commented 5 years ago

there is still a regression, here is the code to reproduce:

static EXPECTED: &[u8] = &[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 0, 0, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 1, 0, 255, 255, 1, 0, 255, 255, 1, 0, 255, 255, 1, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 255, 255, 0, 0, 254, 255, 0, 0, 254, 255, 0, 0, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 255, 255, 1, 0, 255, 255, 1, 0, 0, 0, 1, 0, 255, 255, 2, 0, 255, 255, 2, 0, 255, 255, 2, 0, 255, 255, 2, 0, 255, 255, 2, 0, 255, 255, 1, 0, 255, 255, 1, 0, 255, 255, 0, 0, 254, 255, 0, 0, 254, 255, 0, 0, 254, 255, 255, 255, 254, 255, 254, 255, 254, 255, 253, 255, 253, 255, 253, 255, 253, 255, 252, 255, 254, 255, 251, 255, 254, 255, 251, 255, 254, 255, 252, 255, 255, 255, 252, 255, 0, 0, 252, 255, 0, 0, 252, 255, 1, 0, 252, 255, 1, 0, 252, 255, 2, 0, 252, 255, 2, 0, 252, 255, 2, 0, 252, 255, 2, 0, 252, 255, 2, 0, 253, 255, 1, 0, 252, 255, 0, 0, 252, 255, 255, 255, 251, 255, 0, 0, 251, 255, 0, 0, 251, 255, 0, 0, 252, 255, 2, 0, 252, 255, 3, 0, 252, 255, 4, 0, 253, 255, 5, 0, 254, 255, 5, 0, 253, 255, 6, 0, 253, 255, 6, 0, 253, 255, 5, 0, 253, 255, 5, 0, 254, 255, 4, 0, 254, 255, 3, 0, 251, 255, 0, 0, 250, 255, 255, 255, 253, 255, 254, 255, 252, 255, 252, 255, 247, 255, 251, 255, 247, 255, 252, 255, 252, 255, 254, 255, 252, 255, 254, 255, 252, 255, 255, 255, 254, 255, 1, 0, 1, 0, 1, 0, 4, 0, 2, 0, 8, 0, 2, 0, 12, 0, 1, 0, 13, 0, 0, 0, 12, 0, 0, 0, 11, 0, 255, 255, 8, 0, 254, 255, 7, 0, 0, 0, 7, 0, 253, 255, 11, 0, 248, 255, 15, 0, 247, 255, 17, 0, 250, 255, 17, 0, 251, 255, 13, 0, 253, 255, 7, 0, 255, 255, 3, 0, 255, 255, 254, 255, 255, 255, 252, 255, 255, 255, 252, 255, 254, 255, 250, 255, 255, 255, 242, 255, 254, 255, 239, 255, 252, 255, 248, 255, 255, 255, 249, 255, 5, 0, 239, 255, 7, 0, 238, 255, 10, 0, 249, 255, 18, 0, 254, 255, 25, 0, 253, 255, 27, 0, 0, 0, 31, 0, 4, 0, 34, 0, 4, 0, 34, 0, 8, 0, 36, 0, 8, 0, 37, 0, 2, 0, 36, 0, 4, 0, 34, 0, 8, 0, 28, 0, 3, 0, 15, 0, 255, 255, 11, 0, 0, 0, 12, 0, 251, 255, 8, 0, 252, 255, 10, 0, 0, 0, 23, 0, 252, 255, 31, 0, 248, 255, 30, 0, 254, 255, 30, 0, 255, 255, 26, 0, 250, 255, 22, 0, 250, 255, 20, 0, 244, 255, 15, 0, 237, 255, 10, 0, 246, 255, 13, 0, 242, 255, 6, 0, 213, 255, 243, 255, 213, 255, 240, 255, 247, 255, 244, 255, 246, 255, 227, 255, 214, 255, 216, 255, 219, 255, 228, 255, 251, 255, 235, 255, 1, 0, 232, 255, 248, 255, 236, 255, 4, 0, 238, 255, 26, 0, 232, 255, 44, 0, 230, 255, 66, 0, 226, 255, 86, 0, 219, 255, 88, 0, 215, 255, 72, 0, 210, 255, 50, 0, 225, 255, 28, 0, 23, 0, 14, 0, 64, 0, 16, 0, 51, 0, 26, 0, 32, 0, 34, 0, 39, 0, 42, 0, 48, 0, 35, 0, 58, 0, 255, 255, 72, 0, 220, 255, 69, 0, 197, 255, 58, 0, 158, 255, 54, 0, 132, 255, 36, 0, 153, 255, 12, 0, 146, 255, 5, 0, 83, 255, 237, 255, 110, 255, 197, 255, 252, 255, 214, 255, 51, 0, 1, 0, 233, 255, 250, 255, 226, 255, 250, 255, 45, 0, 46, 0, 47, 0, 70, 0, 6, 0, 55, 0, 19, 0, 60, 0, 38, 0, 62, 0, 42, 0, 47, 0, 61, 0, 46, 0, 40, 0, 42, 0, 237, 255, 22, 0, 222, 255, 6, 0, 221, 255, 206, 255, 195, 255, 115, 255, 219, 255, 85, 255, 17, 0, 93, 255, 26, 0, 76, 255, 46, 0, 102, 255, 80, 0, 193, 255, 48, 0, 252, 255, 18, 0, 20, 0, 50, 0, 47, 0, 58, 0, 53, 0, 44, 0, 61, 0, 57, 0, 85, 0, 37, 0, 80, 0, 0, 0, 86, 0, 248, 255, 106, 0, 161, 255, 49, 0, 43, 255, 248, 255, 125, 255, 47, 0, 49, 0, 63, 0, 40, 0, 217, 255, 187, 255, 182, 255, 219, 255, 236, 255, 63, 0, 244, 255, 58, 0, 242, 255, 244, 255, 25, 0, 225, 255, 41, 0, 11, 0, 45, 0, 76, 0, 47, 0, 167, 0, 5, 0, 5, 1, 219, 255, 21, 1, 173, 255, 183, 0, 84, 255, 35, 0, 134, 255, 177, 255, 138, 0, 186, 255, 10, 1, 69, 0, 124, 0, 228, 0, 0, 0, 135, 1, 227, 255, 82, 2, 172, 255, 190, 2, 178, 255, 115, 2, 248, 255, 39, 2, 243, 255, 253, 1, 13, 0, 116, 1, 120, 0, 96, 1, 125, 0, 110, 2, 127, 0, 179, 2, 223, 0, 106, 1, 126, 0, 130, 1, 223, 255, 147, 3, 198, 0, 190, 3, 201, 1, 200, 1, 42, 1, 244, 1, 233, 0, 3, 4, 213, 1, 72, 4, 170, 1, 150, 3, 160, 0, 43, 4, 141, 0, 196, 4, 189, 0, 221, 4, 164, 0, 95, 5, 41, 1, 98, 5, 247, 1, 19, 5, 190, 2, 14, 6, 161, 3, 7, 7, 87, 3, 216, 6, 35, 2, 38, 7, 90, 2, 136, 7, 64, 3, 200, 6, 28, 3, 199, 6, 165, 3, 169, 7, 105, 5, 143, 7, 26, 6, 57, 8, 205, 5, 156, 10, 169, 5, 132, 11, 25, 5, 208, 10, 181, 4, 156, 10, 66, 5, 227, 9, 170, 5, 166, 9, 117, 6, 45, 12, 63, 8, 42, 13, 128, 8, 136, 10, 155, 7, 109, 11, 1, 9, 6, 15, 98, 10, 121, 9, 136, 8, 147, 252, 189, 7, 43, 247, 63, 10, 147, 249, 92, 11, 172, 248, 172, 10, 112, 245, 137, 11, 76, 246, 44, 12, 184, 247, 138, 11, 118, 246, 144, 12, 94, 246, 171, 13, 112, 247, 162, 12, 168, 246, 33, 13, 63, 246, 29, 15, 226, 247, 188, 14, 190, 248, 75, 15, 238, 247, 86, 17, 19, 247, 118, 11, 10, 247, 232, 254, 238, 247, 30, 249, 56, 248, 124, 250, 6, 247, 1, 250, 161, 246, 3, 249, 81, 247, 117, 250, 60, 247, 202, 250, 212, 247, 60, 250, 15, 249, 140, 250, 34, 248, 221, 249, 105, 247, 218, 249, 205, 248, 113, 251, 138, 248, 90, 250, 41, 248, 230, 248];
static PCM: &[i16] = &[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -2, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 1, 0, 1, 0, 0, -2, 0, -2, 0, -2, 0, -2, -2, -2, -3, -3, -3, -3, -4, -2, -5, -2, -5, -2, -4, 0, -4, 0, -4, 0, -4, 1, -4, 1, -4, 2, -4, 2, -4, 2, -4, 2, -4, 2, -3, 1, -4, 0, -4, 0, -5, 0, -5, 0, -5, 0, -4, 2, -4, 3, -4, 4, -3, 5, -2, 5, -3, 6, -3, 6, -3, 5, -3, 5, -2, 4, -2, 3, -5, 0, -6, 0, -3, -2, -4, -4, -9, -5, -9, -4, -4, -2, -4, -2, -4, 0, -2, 1, 1, 1, 4, 2, 8, 2, 12, 1, 13, 0, 12, 0, 11, 0, 8, -2, 7, 0, 7, -3, 11, -8, 15, -9, 17, -6, 17, -5, 13, -3, 7, 0, 3, 0, -2, 0, -4, 0, -4, -2, -6, 0, -14, -2, -17, -4, -8, 0, -7, 5, -17, 7, -18, 10, -7, 18, -2, 25, -3, 27, 0, 31, 4, 34, 4, 34, 8, 36, 8, 37, 2, 36, 4, 34, 8, 28, 3, 15, 0, 11, 0, 12, -5, 8, -4, 10, 0, 23, -4, 31, -8, 30, -2, 30, 0, 26, -6, 22, -6, 20, -12, 15, -19, 10, -10, 13, -14, 6, -43, -13, -43, -16, -9, -12, -10, -29, -42, -40, -37, -28, -5, -21, 1, -24, -8, -20, 4, -18, 26, -24, 44, -26, 66, -30, 86, -37, 88, -41, 72, -46, 50, -31, 28, 23, 14, 64, 16, 51, 26, 32, 34, 39, 42, 48, 35, 58, 0, 72, -36, 69, -59, 58, -98, 54, -124, 36, -103, 12, -110, 5, -173, -19, -146, -59, -4, -42, 51, 1, -23, -6, -30, -6, 45, 46, 47, 70, 6, 55, 19, 60, 38, 62, 42, 47, 61, 46, 40, 42, -19, 22, -34, 6, -35, -50, -61, -141, -37, -171, 17, -163, 26, -180, 46, -154, 80, -63, 48, -4, 18, 20, 50, 47, 58, 53, 44, 61, 57, 85, 37, 80, 0, 86, -8, 106, -95, 49, -213, -8, -131, 47, 49, 63, 40, -39, -69, -74, -37, -20, 63, -12, 58, -14, -12, 25, -31, 41, 11, 45, 76, 47, 167, 5, 261, -37, 277, -83, 183, -172, 35, -122, -79, 138, -70, 266, 69, 124, 228, 0, 391, -29, 594, -84, 702, -78, 627, -8, 551, -13, 509, 13, 372, 120, 352, 125, 622, 127, 691, 223, 362, 126, 386, -33, 915, 198, 958, 457, 456, 298, 500, 233, 1027, 469, 1096, 426, 918, 160, 1067, 141, 1220, 189, 1245, 164, 1375, 297, 1378, 503, 1299, 702, 1550, 929, 1799, 855, 1752, 547, 1830, 602, 1928, 832, 1736, 796, 1735, 933, 1961, 1385, 1935, 1562, 2105, 1485, 2716, 1449, 2948, 1305, 2768, 1205, 2716, 1346, 2531, 1450, 2470, 1653, 3117, 2111, 3370, 2176, 2696, 1947, 2925, 2305, 3846, 2658, 2425, 2184, -877, 1981, -2261, 2623, -1645, 2908, -1876, 2732, -2704, 2953, -2484, 3116, -2120, 2954, -2442, 3216, -2466, 3499, -2192, 3234, -2392, 3361, -2497, 3869, -2078, 3772, -1858, 3915, -2066, 4438, -2285, 2934, -2294, -280, -2066, -1762, -1992, -1412, -2298, -1535, -2399, -1789, -2223, -1419, -2244, -1334, -2092, -1476, -1777, -1396, -2014, -1571, -2199, -1574, -1843, -1167, -1910, -1446, -2007, -1818];

fn main() {
    for _ in 0..10 {
        mse(PCM.len(), PCM, EXPECTED);
    }
}

fn read_i16(buffer: &[u8], index: usize) -> i16 {
    const SIZE: usize = std::mem::size_of::<i16>();
    let mut bytes: [u8; SIZE] = [0u8; SIZE];
    bytes.copy_from_slice(&buffer[(index * SIZE)..(index * SIZE + SIZE)]);
    unsafe { std::mem::transmute(bytes) }
}

fn mse(samples: usize, frame_buf: &[i16], buf_ref: &[u8]) -> f64 {
    let mut MSE = 0.0;
    let max_samples = std::cmp::min(buf_ref.len() / 2, samples as usize);
    for i in 0..max_samples {
        let ref_res = read_i16(buf_ref, i);
        let info_res = frame_buf[i as usize];
        let diff = (ref_res - info_res).abs();
        MSE += f64::from(diff.pow(2));
    }
    MSE / max_samples as f64
}

sorry for deleting

oli-obk commented 5 years ago

so this code has gotten worse? Or it's just still bad?

RalfJung commented 5 years ago

This latest one has gotten worse with the PR.

I think what's happening is that it just tries merging things all the time when there is nothing to merge...

nivkner commented 5 years ago

i don't think the PR solves the problem of memory usage growing over time.

you can see this by running the mse benchmark in loops:

iterations memory (kbytes) memory with -Zmiri-disable-validation (kbytes)
1 275988 129548
2 448164 131372
3 590356 134160

this means that even if the memory actually being used at any given time is small, trying to run the same function for different buffers (or the same buffer in this case) exhausts all available memory eventually.

RalfJung commented 5 years ago

Fair enough.

However, I am not sure if that is a bug. The issue with global static arrays is that each time you access them, you create a new pointer that is allowed to access this array -- but all previous pointers remain valid! It is globally shared, after all. So during program execution, you accumulate many many pointers that are allowed to access this memory.

You can see that already with this simple program:

static S: u8 = 0;

fn main() {
    for i in 0..0xFFFF_FFFFusize {
        let _val = &S;
    }
}

Memory consumption just keeps growing while this program runs.

This is an inherent property of Stacked Borrows. We could do some kind of garbage collection, or maybe start approximating "old" pointers at some point, but no trivial implementation change will fix this.