Out of bounds errors in apsp

[mewais]

Hi, as the title suggests, I think there's an out of bound error in apsp (although possibly on other benchmarks too, I haven't actually looked there yet).

Here's the details:

• In do_work there's a posix_memalign((void**) &D, 64, N * sizeof(int)) and a similar one for Q. This clearly allocates an N sized array.
• In initialize_single_source there's a for (int i = 0; i < N + 1; i++) which obviously works on an N+1 sized array.
• In initialize_single_source there's also a D[source] = 0; where in the last iteration source is N rather than N-1. So also an N+1 sized array.
• In do_work, the way next_source is defined and incremented also makes the while loop go from 0 to N+1, which is what actually causes the previous issue to arise.

Now, there's only one thing I am not clear on, basically what is the proper fix? Is the allocation supposed to allocate an N+1 sized array? Or are the indices wrong and should only go from 0 to N?

PS: for help debugging this, compile with -fsanitize=address and these errors will be detected as you run.

Thanks

[masabahmad]

Hi, an easy fix that comes to mind is to allocate N+1 elements using posix_memalign(), or limit the iterations to N in the initialize function. Let me know if that fixes it (you can pull/fix/push and then I can merge the request).

[mewais]

Yeah both are easy fixes, I am just trying to find out which is more "correct" as I no graph processing expert. Based on your answer, it seems that N + 1 is incorrect, so I should limit the loops to N. I will go with that solution.

I will submit a PR later with this fix for apsp and any other benchmakrs that may have the same issue.

[mewais]

I just submitted a pull request for this. It is also worth noting, some benchmarks leak memory by not freeing their allocations, I did not fix this in the PR.

[mewais]

Any updates?

[masabahmad]

I accepted the request. I also wanted to ask if you ran a few tests on these changes?

On Mon, Jul 18, 2022 at 1:14 AM Mohammad Ewais @.***> wrote:

Message sent from a system outside of UConn.

Any updates?

— Reply to this email directly, view it on GitHub https://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmasabahmad%2FCRONO%2Fissues%2F9%23issuecomment-1186806715&data=05%7C01%7C%7Ca568e6a316324ca2222708da6884b688%7C17f1a87e2a254eaab9df9d439034b080%7C0%7C0%7C637937216443625120%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=HeG3xymopS2cBEcT7rrQh8jDtJ6YhFVQaFWpciFQbJI%3D&reserved=0, or unsubscribe https://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FABYE2QOQ4U3YMNZ7K4CQ3M3VUTY2XANCNFSM53TPEYUA&data=05%7C01%7C%7Ca568e6a316324ca2222708da6884b688%7C17f1a87e2a254eaab9df9d439034b080%7C0%7C0%7C637937216443625120%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=dSekowc%2BWMnzJJKmFz450pGAf6G9%2FExQcjaoeK%2BZ7W8%3D&reserved=0 . You are receiving this because you commented.Message ID: @.***>

[mewais]

Hey, sorry I didn't see the replies. I ran tests with the sample.txt as long as the full roadNet-CA. But only for the benchmarks that give an output. So, I couldn't test apsp or bc for example.

[masabahmad]

ok should be fine. I'll test on my side as well and then close this thread. Thanks for your help!

On Thu, Jul 21, 2022 at 12:04 PM Mohammad Ewais @.***> wrote:

Message sent from a system outside of UConn.

Hey, sorry I didn't see the replies. I ran tests with the sample.txt as long as the full roadNet-CA. But only for the benchmarks that give an output. So, I couldn't test apsp or bc for example.

— Reply to this email directly, view it on GitHub https://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fmasabahmad%2FCRONO%2Fissues%2F9%23issuecomment-1191731114&data=05%7C01%7C%7C4528e9c42a3e48d265e008da6b3b0509%7C17f1a87e2a254eaab9df9d439034b080%7C0%7C0%7C637940198467351224%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=eEcmQ5QYA4VbsZtvtsIX9sHCq%2BdC6I2dn9ACXfSZA20%3D&reserved=0, or unsubscribe https://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FABYE2QI576OQSGWHZW7HX7LVVF7ILANCNFSM53TPEYUA&data=05%7C01%7C%7C4528e9c42a3e48d265e008da6b3b0509%7C17f1a87e2a254eaab9df9d439034b080%7C0%7C0%7C637940198467351224%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=e%2FDCE5xRgah4ERkLhj7rwYG7NkfK0lbuF3LSF%2BdeGoQ%3D&reserved=0 . You are receiving this because you commented.Message ID: @.***>