y_iterate: invalid values in an iterator causing server to crash/freeze about ysi-includes

[Misiur]

Can someone confirm this testcase? I don't have my pawn stack handy.

[khalidahmedshalabi]

I do really need this solved soon...

[mokiding]

About testcase:

Pawn compiler 3.10.20150503-1-g1cca8af Copyright (c) 1997-2006, ITB CompuPhase

Header size: 1624 bytes
Code size: 192812 bytes
Data size: 50868 bytes
Stack/heap size: 16384 bytes; estimated max. usage: unknown, due to recursion
Total requirements: 261688 bytes

[Finished in 2.4s]

Compiling was ok.

Server is not crashing/freezing (console). But all i get is spamming the

[19:15:52] Values in 'test': 2
[19:15:52] << 2 is invalid index, must not be in the iterator >>

here is full serverlog. https://gist.github.com/m0k1/10f7cc71c78c04cd77ae

[khalidahmedshalabi]

Yeah, but it actually does freeze (not console), nothing can be executed (i.e sending text in chat); it's like the server is stuck in an endless loop.

[khalidahmedshalabi]

This is a critical bug now and it's affecting almost everything in YSI.

[maddinat0r]

I can confirm this. Here's an even smaller example to reproduce this bug:

#include <a_samp>
#include <YSI4\YSI\y_iterate>

new Iterator:test<5>;

main()
{
    Iter_Add(test, 1);
    Iter_Add(test, 2);
    Iter_Remove(test, 1);
    Iter_Remove(test, 2);

    foreach(new i : test)
    {
        //infinite loop
    }
}

I've tried to find the bug, this is how far I came:
The problem is very likely here in those two lines. The indices ((array[last] = array[value]) - 1) % size and value sometimes have the same value, thus the assignment array[value] = value; overwrites the previous assignment. However, that overwritten assignment is mandatory to keep the array correctly maintained. The second assignment is required to check if a value is already in the array or not.
I don't really see a perfect solution for this, maybe someone else like @Misiur or @Y-Less do though.

[maddinat0r]

Maybe setting the sign bit to 1 when inserting a value into the iterator array is a good idea to indicate that this slot is used, since inserting negative values isn't allowed anyway.

[Y-Less]

Using the sign bit will totally break iteration. However, that investigation is very useful. I thought I had considered all cases like this but clearly not! Give me a few minutes...

[Y-Less]

Try:

array[last] = array[value],
array[value] = value,
array[(array[last] - 1) % size] = (last + 1) % size;

[Y-Less]

You might also want to add a regression test:

Test:y_iter_infiniteLoop()
{
    new
        count = 0,
        Iterator:iter<20>;
    Iter_Add(iter, 1);
    Iter_Add(iter, 2);
    Iter_Remove(iter, 1);
    foreach (new i : iter)
    {
        ASSERT(count == 0);
        if (count++)
            return;
    }
}

That will detect an infinite loop, but not get stuck in it.

[Y-Less]

To expand on my comment about using the sign bit breaking things. Iterators are primarily designed for forwards iteration, everything else is secondary to that. I have improved reverse iteration, additions, and removals at no cost to the central feature, but that will affect it seriously. An iteration is just:

for (new i = sizeof (iter) - 1); (i = iter[i]) != sizeof (iter) - 1; )
{
}

That is the foreach macro at its core - as you can see every array element is a new index. If they were inverted they would no longer be valid indices.

Also, that bit is used by y_groups to identify groups over players, amongst other things.

[Y-Less]

Also, special iterators can have negative values - see Random.

[khalidahmedshalabi]

array[last] = array[value],
array[value] = value,
array[(array[last] - 1) % size] = (last + 1) % size;

This code seems to fix it; I tested it with my code (haven't tested it with maddinat0r's), and server never got stuck in an endless loop. Moreover, in this code

if(!Iter_Contains(test, i))
{
    printf("<<  %d is invalid index, must not be in the iterator  >>", i);
    return 1;
}

that message was never printed.

However, I have to test it with my main game-mode as well to see if there are still problems. I will come with result soon.

[maddinat0r]

Those three lines indeed solve this issue. Nice fix! I'll create a pull request ASAP.
I didn't really thought this through when I wrote that idea with the sign bit. I did see that values are used as array indices, negatives values of course wouldn't work (shame on me 😰).
Thank you Y_Less for helping out!

[Y-Less]

You've changed the test...

[maddinat0r]

Your test didn't triggered with the invalid code. After adding Iter_Remove(iter, 2); it did (and with the fixed code it didn't). I thought you just forgot to add that line, so I added it myself.

[Y-Less]

Hmm, I ran through the code on paper and couldn't actually see how the second one triggered the issue when the first didn't. However, I will believe you - in that case you need to change the ASSERT to some different condition, such as:

foreach (new i : iter)
{
    ASSERT(false);
    return;
}
ASSERT(true);

So something is checked.

[maddinat0r]

I've updated the test case, thanks.

Maybe this will help:

#include <a_samp>
#include <YSI4\YSI\y_iterate>

new Iterator:test<5>;

PrintArray()
{
    for(new i; i != sizeof(Iterator@test); ++i)
    {
        printf(" [%d]: %d", i, Iterator@test[i]);
    }
}

main()
{
    printf("Add(1): %d", Iter_Add(test, 1));
    printf("Add(2): %d", Iter_Add(test, 2));

    PrintArray();

    printf("Rem(1): %d", Iter_Remove(test, 1));
    PrintArray();
    printf("Rem(2): %d", Iter_Remove(test, 2));
    PrintArray();

}

---

Output:

Add(1): 1
Add(2): 2
 [0]: 0
 [1]: 2
 [2]: 5
 [3]: -5
 [4]: 3
 [5]: 1
Rem(1): 1
 [0]: 0
 [1]: 1
 [2]: 5
 [3]: -5
 [4]: 3
 [5]: 2
Rem(2): 2
 [0]: 5
 [1]: 1
 [2]: 2
 [3]: -5
 [4]: 1
 [5]: 2

[Misiur]

https://github.com/Misiur/YSI-Includes/pull/19 Feel free to close if resolved

[Y-Less]

I don't have SA:MP installed which is why I couldn't run the code.

[maddinat0r]

I almost thought so, that's why I posted the code and its output in the first place 😄
But well, this bug is now fixed. Again, thank you for your help Y_Less!

[khalidahmedshalabi]

My server doesn't crash/freeze anymore.