Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Array append sometimes segfaults #10011

Closed
elimisteve opened this issue May 5, 2021 · 17 comments
Closed

Array append sometimes segfaults #10011

elimisteve opened this issue May 5, 2021 · 17 comments
Assignees
@crthpl
Labels
Bug This tag is applied to issues which reports bugs.

Comments

@elimisteve
Copy link
Member

V version: V 0.2.2 99a2fd7
OS: Debian GNU/Linux 9.13 (stretch) x86_64

What did you do?

$ cat 01_05_MergeSort-vbug2-min.v
fn main() {
	println(fake_sort([4, 5, 6]))
}

fn fake_sort(nums []int) []int {
	dump(nums)
	if nums.len <= 1 {
		return nums
	}

	mid := nums.len / 2
	left := nums[..mid]
	right := nums[mid..]
	mut sorted := fake_sort(left)
	println('About to merge right == $right')
	sorted_right := fake_sort(right)
	println('Appending $sorted << $sorted_right (this blows up)')
	sorted << sorted_right
	println('Successfully appended (never reached)')
	return sorted
}

$ v run 01_05_MergeSort-vbug2-min.v

What did you expect to see?

A bunch of logging followed by

[4, 5, 6]

What did you see instead?

A bunch of logging followed by a segfault:

$ v run 01_05_MergeSort-vbug2-min.v
[01_05_MergeSort-vbug2-min.v:6] nums: [4, 5, 6]
[01_05_MergeSort-vbug2-min.v:6] nums: [4]
About to merge right == [5, 6]
[01_05_MergeSort-vbug2-min.v:6] nums: [5, 6]
[01_05_MergeSort-vbug2-min.v:6] nums: [5]
About to merge right == [6]
[01_05_MergeSort-vbug2-min.v:6] nums: [6]
Appending [5] << [6] (this blows up)
*** Error in `/home/user/django_projects/algorithms/01_05_MergeSort-vbug2-min': realloc(): invalid pointer: 0x0000000001ff0474 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x70bfb)[0x788f32b30bfb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76fc6)[0x788f32b36fc6]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x219)[0x788f32b3b7d9]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug2-min[0x416ad8]
======= Memory map: ========
00400000-0046d000 r-xp 00000000 ca:10 1528807                            /home/user/django_projects/algorithms/01_05_MergeSort-vbug2-min
0066c000-0066f000 rwxp 0006c000 ca:10 1528807                            /home/user/django_projects/algorithms/01_05_MergeSort-vbug2-min
01fec000-0200d000 rwxp 00000000 00:00 0                                  [heap]
788f2c000000-788f2c021000 rwxp 00000000 00:00 0 
788f2c021000-788f30000000 ---p 00000000 00:00 0 
788f32488000-788f3249e000 r-xp 00000000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
788f3249e000-788f3269d000 ---p 00016000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
788f3269d000-788f3269e000 r-xp 00015000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
788f3269e000-788f3269f000 rwxp 00016000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
788f3269f000-788f326a2000 r-xp 00000000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
788f326a2000-788f328a1000 ---p 00003000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
788f328a1000-788f328a2000 r-xp 00002000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
788f328a2000-788f328a3000 rwxp 00003000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
788f328a3000-788f328bb000 r-xp 00000000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
788f328bb000-788f32aba000 ---p 00018000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
788f32aba000-788f32abb000 r-xp 00017000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
788f32abb000-788f32abc000 rwxp 00018000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
788f32abc000-788f32ac0000 rwxp 00000000 00:00 0 
788f32ac0000-788f32c55000 r-xp 00000000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
788f32c55000-788f32e55000 ---p 00195000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
788f32e55000-788f32e59000 r-xp 00195000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
788f32e59000-788f32e5b000 rwxp 00199000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
788f32e5b000-788f32e5f000 rwxp 00000000 00:00 0 
788f32e5f000-788f32f62000 r-xp 00000000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
788f32f62000-788f33161000 ---p 00103000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
788f33161000-788f33162000 r-xp 00102000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
788f33162000-788f33163000 rwxp 00103000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
788f33163000-788f33186000 r-xp 00000000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
788f33369000-788f3336d000 rwxp 00000000 00:00 0 
788f33385000-788f33386000 rwxp 00000000 00:00 0 
788f33386000-788f33387000 r-xp 00023000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
788f33387000-788f33388000 rwxp 00024000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
788f33388000-788f33389000 rwxp 00000000 00:00 0 
7ffc6eebf000-7ffc6eee0000 rwxp 00000000 00:00 0                          [stack]
7ffc6ef80000-7ffc6ef83000 r--p 00000000 00:00 0                          [vvar]
7ffc6ef83000-7ffc6ef85000 r-xp 00000000 00:00 0                          [vdso]
788f32af2fff : at ???: RUNTIME ERROR: abort() called
788f32b36fc6 : by ???
3437343066663130 : by ???
0043d1a6 : at ???: RUNTIME ERROR: invalid memory access
0043cb29 : by ???
0043cdf3 : by ???
0043cfa7 : by ???
788f32af3060 : by ???
788f32b36fc6 : by ???
3437343066663130 : by ???
Segmentation fault
@elimisteve elimisteve added the Bug This tag is applied to issues which reports bugs. label May 5, 2021
@yuyi98
Copy link
Member

yuyi98 commented May 5, 2021

Add .clone():

fn main() {
	println(fake_sort([5, 4, 6]))
}

fn fake_sort(nums []int) []int {
	dump(nums)
	if nums.len <= 1 {
		return nums
	}

	mid := nums.len / 2
	left := nums[..mid].clone()
	right := nums[mid..].clone()
	mut sorted := fake_sort(left)
	println('About to merge right == $right')
	sorted_right := fake_sort(right)
	println('Appending $sorted << $sorted_right (this blows up)')
	sorted << sorted_right
	println('Successfully appended (never reached)')
	return sorted
}

PS D:\Test\v\tt1> v run .
[.\\tt1.v:6] nums: [4, 5, 6]
[.\\tt1.v:6] nums: [4]
About to merge right == [5, 6]
[.\\tt1.v:6] nums: [5, 6]
[.\\tt1.v:6] nums: [5]
About to merge right == [6]
[.\\tt1.v:6] nums: [6]
Appending [5] << [6] (this blows up)
Successfully appended (never reached)
Appending [4] << [5, 6] (this blows up)
Successfully appended (never reached)
[4, 5, 6]

@elimisteve
Copy link
Member Author

May be related to this, though cloning the arrays doesn't help in this case.

@elimisteve
Copy link
Member Author

Huh, I guess I didn't add .clone() in the right spots before... Thanks @yuyi98, I'll try that.

@dumblob
Copy link
Contributor

dumblob commented May 5, 2021

Sure .clone() helps here.

But this segfault shall by no means happen even if the slices/views are being used illogically. V is a safe language so no segfaults in apps which do not havy any unsafe{}. Let's not close this issue as it has to get fixed.

@elimisteve
Copy link
Member Author

@dumblob I don't think @yuyi98 was proposing that as a permanent solution 🙂

@atorr0
Copy link

atorr0 commented May 8, 2021

For sake of completeness:

alejandro@hpnegro:/tmp/tmp.VHh3GY3qXb
2021-05-08 19:58:50$ v -cg example.v 
alejandro@hpnegro:/tmp/tmp.VHh3GY3qXb
2021-05-08 19:58:56$ valgrind ./example 
==6898== Memcheck, a memory error detector
==6898== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6898== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==6898== Command: ./example
==6898== 
[example.v:6] nums: [4, 5, 6]
[example.v:6] nums: [4]
About to merge right == [5, 6]
[example.v:6] nums: [5, 6]
[example.v:6] nums: [5]
About to merge right == [6]
[example.v:6] nums: [6]
Appending [5] << [6] (this blows up)
==6898== Invalid free() / delete / delete[] / realloc()
==6898==    at 0x4C33D2F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6898==    by 0x41FA69: realloc_data (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x41A6DF: array_ensure_cap (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x41CD24: array_push_many (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x431E0D: main__fake_sort (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x431C89: main__fake_sort (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x4318E4: main__main (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x4441DB: main (in /tmp/tmp.VHh3GY3qXb/example)
==6898==  Address 0x59f4854 is 4 bytes inside a block of size 12 alloc'd
==6898==    at 0x4C33B25: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6898==    by 0x41FCEB: vcalloc (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x41A4B2: new_array_from_c_array (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x4318A6: main__main (in /tmp/tmp.VHh3GY3qXb/example)
==6898==    by 0x4441DB: main (in /tmp/tmp.VHh3GY3qXb/example)
==6898== 
================ V panic ================
   module: builtin
 function: realloc_data()
  message: realloc_data(94324820, 4, 8) failed
     file: /opt/v/vlib/builtin/builtin.c.v:345
   v hash: cbf30bd
=========================================
/tmp/v/example.7976284971752093656.tmp.c:5729: at panic_debug: Backtrace
/tmp/v/example.7976284971752093656.tmp.c:5946: by realloc_data
/tmp/v/example.7976284971752093656.tmp.c:5073: by array_ensure_cap
/tmp/v/example.7976284971752093656.tmp.c:5380: by array_push_many
/tmp/v/example.7976284971752093656.tmp.c:9544: by main__fake_sort
/tmp/v/example.7976284971752093656.tmp.c:9542: by main__fake_sort
/tmp/v/example.7976284971752093656.tmp.c:9519: by main__main
/tmp/v/example.7976284971752093656.tmp.c:9943: by main
==6898== 
==6898== HEAP SUMMARY:
==6898==     in use at exit: 18,702 bytes in 55 blocks
==6898==   total heap usage: 65 allocs, 10 frees, 18,840 bytes allocated
==6898== 
==6898== LEAK SUMMARY:
==6898==    definitely lost: 263 bytes in 23 blocks
==6898==    indirectly lost: 0 bytes in 0 blocks
==6898==      possibly lost: 0 bytes in 0 blocks
==6898==    still reachable: 18,439 bytes in 32 blocks
==6898==         suppressed: 0 bytes in 0 blocks
==6898== Rerun with --leak-check=full to see details of leaked memory
==6898== 
==6898== For counts of detected and suppressed errors, rerun with: -v
==6898== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
alejandro@hpnegro:/tmp/tmp.VHh3GY3qXb
2021-05-08 19:59:03$ v version
V 0.2.2 cbf30bd

@crthpl crthpl mentioned this issue May 16, 2021
Closed
@crthpl
Copy link
Member

crthpl commented May 16, 2021

The solution to this bug is either
a) raise the use 'array2 := array1.clone()' instead of 'array2 := array1' (or use 'unsafe') error
b) automatically add .clone() in gen.

The reason it is not raising the error in a), is because currently V only checks if they are both simple identifiers (so mut x := a.b would not raise an error, but c := a.b and then mut x := c would). The solution is to raise an error in all cases except both being non-mut. When I patched this, I got 21 errors running v self, let alone the entirety of vlib. I think that we should instead go for b) instead for this reason, and because it is easier to program in V like that (removing the low level details). What do you think @medvednikov?

@elimisteve
Copy link
Member Author

@crthpl Adding .clone() in gen unfortunately hides a O(n) operation, which is not ideal

@crthpl
Copy link
Member

crthpl commented May 17, 2021

@crthpl Adding .clone() in gen unfortunately hides a O(n) operation, which is not ideal

I would think that this is the same as #277 - if we decide to not use in in favour of .contains(), we should have explicit .clone(), otherwise we should have implicit .clone().

@elimisteve
Copy link
Member Author

My expectation as the programmer is that x in arr is likely O(n) but not necessarily that arr2 := arr is so inefficient.

@crthpl crthpl mentioned this issue May 17, 2021
Closed
@medvednikov
Copy link
Member

That's why V doesn't allow arr2 := arr and forces arr2 := arr.clone() right now (until a faster way is allowed).

@dumblob
Copy link
Contributor

dumblob commented May 17, 2021

Just a side note - x in arr can be made O(1) in many (most) cases - see #6991 (comment) .

@crthpl
Copy link
Member

crthpl commented May 17, 2021 •
edited
Loading

Just a side note - x in arr can be made O(1) in many (most) cases - see #6991 (comment) .

This is about .clone() speed, not in speed. Put this in #277 instead.

@elimisteve
Copy link
Member Author

As Alex has said elsewhere, algorithms that make lookups O(1) are actually slower than O(N) algos when N is small -- and N is usually small.

@crthpl
Copy link
Member

crthpl commented May 17, 2021

As Alex has said elsewhere, algorithms that make lookups O(1) are actually slower than O(N) algos when N is small -- and N is usually small.

Then V should check if N is small, and decide what algorigthm to use.

@elimisteve
Copy link
Member Author

That's true; that's what Go's std lib does when sorting slices, too.

@crthpl crthpl self-assigned this May 18, 2021
@crthpl crthpl mentioned this issue May 25, 2021
Closed
@elimisteve
Copy link
Member Author

Fixed by #10219 ! 😄

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@crthpl crthpl

Labels
Bug This tag is applied to issues which reports bugs.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

checker: have stricter checks for .clone() requirement, disallow empty maps crthpl/v
6 participants
@elimisteve @medvednikov @atorr0 @dumblob @yuyi98 @crthpl