Invalid Basic Block form about mosa-project HOT 26 CLOSED

@tgiphil I seem to be having some issues with trying to fix this.
The first fix I had to make was to change a foreach loop to a for loop in PlatformIntrinsicTransformationStage.

Next I tried doing what you recommend but I keep getting OutOfRange exceptions on the instruction set when Context.IsEmpty is fetched.

Any idea whats causing it?

    public sealed class SpinLock : IIntrinsicPlatformMethod
    {
        #region Methods

        /// <summary>
        /// Splits the block. (Borrowed from BaseMethodCompilerStage)
        /// </summary>
        /// <param name="ctx">The context.</param>
        /// <returns></returns>
        private Context Split(Context ctx, BaseMethodCompiler methodCompiler)
        {
            Context current = ctx.Clone();

            Context next = ctx.Clone();
            next.AppendInstruction(IRInstruction.BlockStart);
            BasicBlock nextBlock = methodCompiler.BasicBlocks.CreateBlockWithAutoLabel(next.Index, current.BasicBlock.EndIndex);
            Context nextContext = new Context(methodCompiler.InstructionSet, nextBlock);

            foreach (BasicBlock block in current.BasicBlock.NextBlocks)
            {
                nextBlock.NextBlocks.Add(block);
                block.PreviousBlocks.Remove(current.BasicBlock);
                block.PreviousBlocks.Add(nextBlock);
            }

            current.BasicBlock.NextBlocks.Clear();

            current.AppendInstruction(IRInstruction.BlockEnd);
            current.BasicBlock.EndIndex = current.Index;

            return nextContext;
        }

        /// <summary>
        /// Links the blocks. (Borrowed from BaseMethodCompilerStage)
        /// </summary>
        /// <param name="source">The source.</param>
        /// <param name="destination">The destination.</param>
        private void LinkBlocks(Context source, Context destination, BaseMethodCompiler methodCompiler)
        {
            methodCompiler.BasicBlocks.LinkBlocks(source.BasicBlock, destination.BasicBlock);
        }

        /// <summary>
        /// Replaces the intrinsic call site
        /// </summary>
        /// <param name="context">The context.</param>
        /// <param name="typeSystem">The type system.</param>
        void IIntrinsicPlatformMethod.ReplaceIntrinsicCall(Context context, BaseMethodCompiler methodCompiler)
        {
            // Create constant operand and get pointer to lock variable
            Operand const1 = Operand.CreateConstantSignedInt(methodCompiler.TypeSystem, 0x1);
            Operand pointer = Operand.CreateMemoryAddress(context.Operand2.Type, context.Operand2, 0);

            // Create new retry block and continue block
            Context retryBlock = methodCompiler.InstructionSet.CreateNewBlock(methodCompiler.BasicBlocks);
            Context setLockBlock = methodCompiler.InstructionSet.CreateNewBlock(methodCompiler.BasicBlocks);
            Context continueBlock = Split(context, methodCompiler);

            // Jump from current context to retry block
            context.SetInstruction(X86.Jmp, retryBlock.BasicBlock);
            LinkBlocks(context, retryBlock, methodCompiler);

            // Test to acquire lock, if cant acquire jump to top, otherwise jump to continue block
            retryBlock.SetInstruction(X86.Test, null, pointer, const1);
            retryBlock.AppendInstruction(X86.Branch, ConditionCode.NotZero, retryBlock.BasicBlock);
            retryBlock.AppendInstruction(X86.Jmp, setLockBlock.BasicBlock);
            LinkBlocks(retryBlock, retryBlock, methodCompiler);
            LinkBlocks(retryBlock, setLockBlock, methodCompiler);

            // Finish off by setting the lock to true
            setLockBlock.SetInstruction(X86.Mov, pointer, const1);
            setLockBlock.AppendInstruction(X86.Jmp, continueBlock.BasicBlock);
            LinkBlocks(setLockBlock, continueBlock, methodCompiler);
        }

        #endregion Methods
    }

from mosa-project.

Sorry; I should have suggested this our earlier.

Write the spinlock in C# and use intrinsic instruction to emit a specific platform instruction, such as LOCK CMPXCHG or LOCK BTS.

from mosa-project.

@tgiphil I've implemented it using Cmov but I'm getting a weird issue.
It works in TinySimulator but when I try to run it in QEMU it doesn't work, any ideas?

Commit charsleysa@159e221
Here's the ASM for the SpinLock.Enter() function:

00405174  FFF5              push ebp
00405176  8BEC              mov ebp,esp
00405178  8B8D08000000      mov ecx,[ebp+0x8]
0040517E  C7C000000000      mov eax,0x0
00405184  F781000000000100  test dword [ecx+0x0],0x1
         -0000
0040518E  0F448100000000    cmovz eax,[ecx+0x0]
00405195  0100              add [eax],eax
00405197  0000              add [eax],al
00405199  0F44C0            cmovz eax,eax
0040519C  0100              add [eax],eax
0040519E  0000              add [eax],al
004051A0  C7C100000000      mov ecx,0x0
004051A6  81F800000000      cmp eax,0x0
004051AC  0F94C1            setz cl
004051AF  8BC1              mov eax,ecx
004051B1  81F800000000      cmp eax,0x0
004051B7  0F85BBFFFFFF      jnz dword 0x405178
004051BD  90                nop
004051BE  5D                pop ebp
004051BF  C3                ret

from mosa-project.

The emitted binary for cmovz is incorrect - that's why there are two add instructions after the cmovz. TinySimulator won't catch this type of error.

Also, need a Lock instruction before the Test instruction (except if the address is memory aligned).

from mosa-project.

I've taken a look at the Cmov instructions and I can't find anything wrong, but I'll take another look to see if I missed anything.

Also I thought the Lock instruction was limited to a small set of instructions which does not include the Test instruction, if this is not the case then I'll add a lock before the test.

from mosa-project.

Also, there is a race condition between the TEST and CMOVZ instruction.

An atomic compare and set instruction, like CMPXCHG or BTS, must be used.

from mosa-project.

See: http://wiki.osdev.org/Spinlock

from mosa-project.

Note: The generated code will look a bit cleaner once the SSA Optimizations are able to combine the following statements such as:

L_000F IR.IntegerCompare [equal] V_5<0> [Int32] <= V_3<0> [Int32], const {0} [System.Int32]
L_0013 IR.IntegerCompareBranch [not equal] V_5<0> [Int32], const {0} [Int32] L_XXXX

It's on my TODO list.

from mosa-project.

The CMOVxx instructions can not accept an immediate value (constant) as an operand.

Use SETcc instead.

from mosa-project.

What we need is something a similar to GCC's __sync_bool_compare_and_swap intrinsic method.

More references - read the top answers.

http://stackoverflow.com/questions/6935442/x86-spinlock-using-cmpxchg
http://stackoverflow.com/questions/9799880/whats-the-difference-between-gcc-sync-bool-compare-and-swap-and-cmpxchg

from mosa-project.

@tgiphil Ok so I wrapped my head around how cmpxchg works and I got the following (I assume its correct):

; BIG NOTE:
; cmpxchg is always comparing the accumulator (eax) not the source and when not equal writes to the accumulator (eax)

                        ; eax = 0, ebx = 1, [pointer] = 0
cmpxchg [pointer], ebx  ; is equal, set ZF = 1, set [pointer] = ebx
sete [return]           ; set [return] = ZF

                        ; eax = 0, ebx = 1, [pointer] = 1
cmpxchg [pointer], ebx  ; is not equal, set ZF = 0, set eax = [pointer]
sete [return]           ; set [return] = ZF

And so I've wound up with the following ASM which I assume is correct (though it doesn't work):

00405174  FFF5              push ebp
00405176  8BEC              mov ebp,esp
00405178  8B8D08000000      mov ecx,[ebp+0x8]
0040517E  33C0              xor eax,eax
00405180  33DB              xor ebx,ebx
00405182  FFC3              inc ebx
00405184  F00FB19900000000  lock cmpxchg [ecx+0x0],ebx
0040518C  0F94C2            setz dl
0040518F  C7C100000000      mov ecx,0x0
00405195  81FA00000000      cmp edx,0x0
0040519B  0F94C1            setz cl
0040519E  81F900000000      cmp ecx,0x0
004051A4  0F85CEFFFFFF      jnz dword 0x405178
004051AA  90                nop
004051AB  5D                pop ebp
004051AC  C3                ret

I had to forcefully coerce the compiler into not using eax.

Commit charsleysa@8baf36a

from mosa-project.

@tgiphil I have seem to encountered a weird bug in the compiler.
The SpinLock struct seems to have its bLock boolean variable set to true by default, either that or there is an address bug and the pointer isn't correct.

Heres the ASM for SpinLock.Enter():

004079B6  FFF5              push ebp
004079B8  8BEC              mov ebp,esp
004079BA  8B9508000000      mov edx,[ebp+0x8]
004079C0  C7C301000000      mov ebx,0x1
004079C6  C7C100000000      mov ecx,0x0
004079CC  C7C000000000      mov eax,0x0
004079D2  F00FB19A00000000  lock cmpxchg [edx+0x0],ebx
004079DA  0F94C1            setz cl
004079DD  C7C000000000      mov eax,0x0
004079E3  81F900000000      cmp ecx,0x0
004079E9  0F94C0            setz al
004079EC  81F800000000      cmp eax,0x0
004079F2  0F85C2FFFFFF      jnz dword 0x4079ba
004079F8  90                nop
004079F9  5D                pop ebp
004079FA  C3                ret

from mosa-project.

Appears correct. Have you stepped through it with Boch?

from mosa-project.

@tgiphil Not yet, but the issue is quite obvious, just create a SpinLock instance and the check the IsHeld property and you'll find that its true when it should be false by default.

Edit: I can't seem to get the PeterBochs Debugger to work on my computer, is there a special setup required?

from mosa-project.

@charsleysa - If you already have Java installed, it should just be a matter of clicking on the batch script. What error message do you get?

from mosa-project.

@charsleysa Pull from MOSA master. A new SSA optimization will reduce the number of instructions for the spinlock.

from mosa-project.

@tgiphil I get some weird error message about pausebochs.exe and stopbochs.exe not being in the same directory as peterbochs jar file.

from mosa-project.

@charsleysa If you have any spaces in the MOSA path, remove them.

from mosa-project.

@charsleysa Take a look a my spinlock branch in my repo.

from mosa-project.

@tgiphil This maybe be a bit of a sidetrack but I just have a few comments and questions on a couple of things.

How come you choose to use a Method Plug instead of MethodImpl?
MethodImpl should be used in the Korlib for portability of the Korlib.

Also, I've been wondering whether it might be better to merge Mosa.Platform.Internal.xxx into the corresponding platform's kernel as it provide a much cleaner solution to accessing drivers and hardware, and reduce the need to use Method Plugs. Also all things native would be available in the Kernel's namespace without requiring a separate library.

from mosa-project.

@charsleysa I agree that using a Method Plug is not ideal. It was a forced since korlib can not directly reference other assemblies. And that's by design since korlib must be platform independent. I'm open to a more elegant solution.

I kept the kernel separate from Platform Internal - so the kernel could be swapped out with a different implementation.

from mosa-project.

@tgiphil I think the plug system and the intrinsic method replacement system are slightly redundant but both required since they perform the same job but implement it differently. Plugs are straight method swaps while intrinsic methods allow for customization of how the method is swapped out.

As for the separation of Platform internal and kernel, that seemed like a good idea but now that I look ahead at how we are going to implement Korlib it seems that it would be counter productive as we will need to access drivers, hardware, and kernel components.

What I'm proposing is that we keep the same structure of platform internal but place it into the Mosa.Kernel.xxx.Internal namespace and just have a list of runtime methods and the like that are required to be implemented.

The implementation is completely up to the kernel so we are not imposing restrictions on how the kernel should work, we are just imposing an interface between the kernel and the Korlib.

from mosa-project.

The code quality has improved:

0040CAE9  FFF5              push ebp
0040CAEB  8BEC              mov ebp,esp
0040CAED  C7C101000000      mov ecx,0x1
0040CAF3  C7C000000000      mov eax,0x0
0040CAF9  F00FB18900000000  lock cmpxchg [ecx+0x0],ecx
0040CB01  0F94C0            setz al
0040CB04  81F800000000      cmp eax,0x0
0040CB0A  0F84DDFFFFFF      jz dword 0x40caed
0040CB10  5D                pop ebp
0040CB11  C3                ret

Eventually, the following will be removed once added to the peephole optimizer, or higher level platform optimizer.

0040CB01  0F94C0            setz al
0040CB04  81F800000000      cmp eax,0x0

from mosa-project.

A few definitions:

• A Intrinsic method provides for the use of inlined platform specific opcode instruction.
• A MethodImpl attribute indicates that the method implement is elsewhere, most generally in the Virtual Execution System (VES).
• A Plug attribute replaces an existing method implementations. Typically used by the kernel or platform to hook into the korlib; such as for memory allocation.

These are some great utilities, but what we are really missing is the ability for corlib to elegantly access Kernel features, such as memory allocation, file handling, etc.. Plugs are one solution, but it's arguable not elegant.

However; I don't see a better solution at the moment. And I don't see how the proposal to merge kernel and platform solves that problem as well. But maybe I'm missing something.

from mosa-project.

@tgiphil Currently we use MethodImpl and Intrinsic Method for the Runtime, take for example the the allocation of strings. We also use VM Calls which do the same job but are for a fixed set of calls while we use Intrinsic Method for extending that list.

By placing Platform Internal into the Kernel we access things like CMOS, SMBIOS, Serial, etc more easily than we can currently. While I'm not saying to completely ditch the Plug system, we can mitigate its use just by having the Platform Internal inside the Kernel.

This may also make it easier to use drivers as well, we should be having the Kernel as the center where the Runtime can access what it needs easily and the Korlib just has to interface with the Runtime using MethodImpl.

On a separate note I managed to get SpinLock on TinySimulator, take a look at my latest commit.

from mosa-project.

Closing issue as it no longer exists.

from mosa-project.