Can method parameters alias temporaries?

[mnicolella]

Hi,

I'm one of the developers still working on The Realm, which as you know uses the SCI engine. The PMachine implementation we have was adapted from the 16-bit interpreter to work on a 32-bit machine. All of the SCI values are still 16-bit, but the interpreter itself is written in 32-bit x86 asm.

I recently reimplemented the PMachine in C++ and removed all of the inline asm from our codebase. Further, I widened the SCI values to 64-bit, including the memory manager handles. We often hit the 64K handle limit, so this removes that limitation from us.

In doing so, I believe I discovered a bug in the way that function parameters and temporaries are laid out on the SCI stack, and was wondering if this was noticed in Sierra's implementation, and was just curious to know if this caused any bugs in real Sierra games.

When a method is called, the argc is pushed on the stack, followed by the parameters. After entering the function, if the function uses any temporaries, there is a 'link' opcode at the beginning of the function that indicates how many temporaries the function uses. Now, there isn't ever any validation performed on the number of arguments passed to a function. This is a 'feature', in that all functions are 'vararg' functions, and the &rest feature can be used to forward function arguments along. However - if, say, you have a function that expects 4 parameters, but you only pass 2, this is sometimes expected - SCI scripts can check 'argc' and realize this, and behave differently. But you're also allowed to -assign- to parameters. What I believe might happen, if you have a function that takes 4 arguments, and also declares two temporaries, but the -caller- only passes you two arguments, is that the memory for the two non-passed arguments and the temporaries are at the same location on the stack, and assigning to a parameter will change the value of the temporary, and vice versa.

Just something that came up while I was debugging my rewrite and thought you all would find it interesting.

[Kawa]

As I expected.

Code: [Select]

(procedure (AliasingTest A B C D &tmp T1 T2)
(FormatPrint "A = %d, B = %d, C = %d, D = %d, T1 = %d, T2 = %d" A B C D T1 T2)
(Print "Assigning to temp vars.")
(= T1 42)
(= T2 69)
(FormatPrint "A = %d, B = %d, C = %d, D = %d, T1 = %d, T2 = %d" A B C D T1 T2)
)
Run with arguments 1 2 3 4, and you get this:

A = 1, B = 2, C = 3, D = 4, T1 = 0, T2 = 200
Assigning to temp vars.
A = 1, B = 2, C = 3, D = 4, T1 = 42, T2 = 69

Run with arguments 5 6 directly afterwards, and you get this:

A = 5, B = 6, C = 3, D = 4, T1 = 3, T2 = 4
Assigning to temp vars.
A = 5, B = 6, C = 42, D = 69, T1 = 42, T2 = 69

So not only are C and D, which end up at the same location in memory, still 3 and 4, but T1 and T2 do in fact alias them. Which is exactly what I felt would happen.

I feel like you could easily write a diagram for this.

[mnicolella]

Ah yes, right, so that's another potential issue, is that temporaries aren't zero-initialized. Would have to check scripts to see if any of them read from temps before assigning to them. Would be an easy runtime check to implement in the interpreter. And again, I wonder if any scripts end up somewhat relying on this behavior.

[lskovlun]

Sounds great, that must mean you plan on keeping SCI around for some time! 

This whole discussion gave me a chuckle. These are issues that ScummVM and FreeSCI before it have struggled with. ScummVM performs strict bounds checking on stack reads and writes and requires workarounds for anything sketchy. The bounds checking stems from a rewrite of the PMachine in FreeSCI which we used to call Glutton (the original being rather more true to the Sierra implementation) which Christoph Reichenbach, original author of FreeSCI, implemented for student credit. He's now a university professor at a location relatively close to me; maybe I should catch up sometime.

From a software engineering perspective, these are bugs in SCI games even though they sometimes show no symptoms in original SCI due to its design. In the FreeSCI days we would have considered this out of scope and let the games crash, but ScummVM contains a workaround system (several, in fact) with much time spent on patching each individual bug. We have also had one here at sciprogramming, that seemed to stem from some manually entered code with a typo in it (remember that, Kawa?  ).

SCI32 handles are far more robust, but even SCI32 can have subtle memory-related bugs (in QfG4, a plane id is sometimes NULL and it works - I worked on that bug over Christmas in 2018).

[mnicolella]

Interesting, thanks. Yeah, no immediate plans to rewrite all of the SCI scripts in C++.

I'm fine with our implementation being more strict - we have the advantage of being able to recompile all of the SCI scripts, and even make modifications to the script compiler itself, so we don't have backwards compat to worry about. So far I haven't made compiler modifications while in this transition period. Had to do some redesign to handle the script fixups.

I also went a step further in my re-implementation, to try and catch more bugs. SCI values carry around type information ('id' or 'int'), and will assert if you try to execute a math op on an id (like op_add), or try to op_send to an int. This extends to all of the kernel functions, too - if we try to fetch an int out of an id, we will crash. In fact, even though the values are 64-bits wide, the int type is still restricted to 16-bit. That's because it's unclear whether loading $FFFF as an immediate should be sign extended as -1 or is meant to be the unsigned int 65535. This will require some script compiler modification to catch all of these cases so we can inspect them all and decide what to do. But I was able to widen handles to be 32-bit and that all seems to function fine, after fixing up a lot of places in the interpreter to not confuse ids with ints.

It's funny you mention planeId because I think that's the one place in the engine where planeId can either be a handle, or just some integer, so it caused a little bit of grief.

[OmerMor]

Cool discussion! :-)

Have you considered moving your re-implementation to ScummVM?

[mnicolella]

Hmm, I'm not sure I understand how ScummVM could benefit? Or, which part sounds interesting? The main reason for us to do this is to increase the number of available handles to us, but I would expect the existing games to largely fit within the original handle budget. Or is the preservation of int/id type information interesting? Are there many bugs in games that you all are trying to fix?

[OmerMor]

I was mainly thinking of adding support for The Realm in ScummVm...

[mnicolella]

Oh I see. I think that?s largely impractical. There is a lot of Realm-specific C++ code in the interpreter (virtually all of the user interface) that would have to be untangled and separated such that you could use an alternate SCI interpreter. We?re also close to finishing a rewrite of the graphics engine to replace the SCI software drawing routines with D3D, which will help us put more, higher quality stuff on-screen, and relax the palette restrictions that really impede our artwork.

I think it would be good to add networking support to an open SCI interpreter, though, if it doesn?t support it already? Does it run the INN client? Would mostly be useful for hobbyist creators, though.

[Collector]

I think it would be good to add networking support to an open SCI interpreter, though, if it doesn?t support it already? Does it run the INN client? Would mostly be useful for hobbyist creators, though.

Might want to get in touch with James Leiterman, who wrote the INN Barn server. You can probably find him on the ImagiNation Network Revival Facebook group. https://www.facebook.com/groups/69704136680/