[Homework 5] Recursive drop

[so-w-on]

For drop() function of the growable_array, I used a recursive function to drop all segments until height = 1.
But the problem is My condition to continue the recursivity is height >=1. But that generates an Invalid Memory reference error
I tried different things and it seems that putting the condition to height >=4 works.
Why is that ?
I think that I keep failing stress_concurrent because of that.

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

[tomtomjhj]

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?

cs431/homework/doc/hash_table.md

Lines 62 to 67 in 518270e

	the grader runs the tests with `cargo`, `cargo_asan`, and `cargo_tsan` in the following order.
	1. `stress_sequential` (5 points)
	1. `lookup_concurrent` (5 points)
	1. `insert_concurrent` (10 points)
	1. `stress_concurrent` (20 points)
	1. `log_concurrent` (30 points)

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

[so-w-on]

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.

[Lee-Janggun]

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.

[so-w-on]

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?

[Lee-Janggun]

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.

[so-w-on]

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

[Lee-Janggun]

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.

[so-w-on]

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

[tomtomjhj]

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.

[so-w-on]

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?

[Lee-Janggun]

That is correct.

[so-w-on]

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;
}

[Lee-Janggun]

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.

[so-w-on]

I see. Thank you!