[Homework 5] Recursive drop about cs431 HOT 14 CLOSED

I tried different things and it seems that putting the condition to height >=4 works.

maybe related to the fact that growable_array test uses u32 for key, which is covered by depth 4 tree.

And another question is, why is it that even if I fail only stress_concurrent I get 0 in total?

If stress_concurrent is the only test that fails, then you will get 20. Can you confirm that your solution passes the earlier tests?

from cs431.

And how should I deal with trees of depth smaller than 4?
And even if the tree is of depth 4, at some point I have to free the heights 1, 2, 3.
So I think it causes a problem either way.

from cs431.

What we can say is that your drop implementation is incorrect. What you should do in deallocating a segment is take ownership from the segment, (with Atomic::{try_}into_owned or Shared::{try_}into_owned), loop through the inner array of the segments and free the next segments if it is really a segment.

That fact that your implementation does not pass when height is 1,2,3 suggests that the above process is not done correctly.

from cs431.

I see. Thank you!
But could it be that my get() implementation affects the correctness of drop? Given that the tags are modified in get()?
or are drop and get independent?

from cs431.

The purpose of drop is to prevent memory leaks, so if you don't implement anything for drop and your get is correct, it should pass the tests, assuming memory does not run out.

from cs431.

What if stress sequential fails because of invalid memory reference. Is it because of my drop implementation?

from cs431.

Mabye? Your get may also not getting to the proper node. If you are getting invalid memory reference even without deallocation, your get is problematic.

from cs431.

If I comment the drop function, I pass stress sequential, but in asan I get Memory Leak:

running 1 test
test stress_sequential ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.07s

Testing split_ordered_list stress_sequential with cargo --release, timeout 10s...

running 1 test
test stress_sequential ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.07s

Testing growable_array lookup_concurrent with cargo --release, timeout 10s...

running 1 test
test lookup_concurrent ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.24s

Testing split_ordered_list lookup_concurrent with cargo --release, timeout 10s...

running 1 test
test lookup_concurrent ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.38s

Testing growable_array insert_concurrent with cargo --release, timeout 10s...

running 1 test
test insert_concurrent ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 2.36s

Testing split_ordered_list insert_concurrent with cargo --release, timeout 10s...

running 1 test
test insert_concurrent ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 6.56s

Testing growable_array stress_concurrent with cargo --release, timeout 10s...

running 1 test
test stress_concurrent ... Test timed out: cargo test --release --test growable_array stress_concurrent
Testing split_ordered_list stress_concurrent with cargo --release, timeout 10s...

running 1 test
test stress_concurrent ... Test timed out: cargo test --release --test split_ordered_list stress_concurrent
Testing growable_array stress_sequential with cargo_asan, timeout 10s...

running 1 test
test stress_sequential ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.47s

Test failed: cargo_asan test --test growable_array stress_sequential
Testing split_ordered_list stress_sequential with cargo_asan, timeout 10s...

running 1 test
test stress_sequential ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 5 filtered out; finished in 0.50s

Test failed: cargo_asan test --test split_ordered_list stress_sequential
Score: 0 / 180

from cs431.

And even if the tree is of depth 4, at some point I have to free the heights 1, 2, 3.

Do you mean that the depth node of some leaf node is not the same as the height of the tree? When get is finished, the leaf nodes' depth are all the same.

from cs431.

yes. But what I understood is that to drop the segments of the growable_array (without the leafs) I have to drop all heights from root.tag to height = 1.
Is this wrong?

from cs431.

That is correct.

from cs431.

My main problem here is why recursive drop causes invalid memory reference in stress sequential, if i don't restrict the recursivity with:
if height <= 3 {
return;
}

from cs431.

That would mean that you are doing drop incorrectly, and if there is the restriction you don't have a problem because we don't make tress of heights larger than 3.

from cs431.

I see. Thank you!

from cs431.