Wow so many posts just to describe
FCIMPL4 macro used within CoreCLR. In this post we are back to CLR code. As a reminder we are still in the CLR code inside
We are finally going to talk about code inside this method 1.
As implementation of FCall is complicated and difficult, you have to add a special code that makes sure your code follows special contract. I think this one is used on compile time (but I am not sure).
FCALL_CONTRACT is a shorthand to multiple flags: 2
Marks function as one that is able to Tolerate Stack Overflow. Tolerate doesn’t mean that
SO won’t happen in this code - it still can but it won’t be the end of the world whole system / process can still operate and recover. On the other spectrum there are functions that cannot tolerate SO -
SO_INTOLERANT this are additionaly proceted from SO - by protected it means that there are special mechanims to limit number of scenarios that this can happen.
Ffor SO_TOLERANR stack guard and stack probe is disabled. SO prode is a special piece of code that enhaances the function ( that is why you need to use special macro SO_INTOLERANT_XXX to generate probe code ). Probe adds checks that before function is executed it checks if there is enough space on the stack - this way it limits possibility of SO. 3
There are two types of SO - hard and soft (soft is when Stack Probe is acctive)
Stack guard on the other hand is a small piece of code that tries to force SO to happen at
convinient time which potentialy means not inside
By default a function is SO_INTOLERANT. SO that happens in that piece if code terminates proceess.
SO is handled in many different ways based on policies 4.
A GC_NOTRIGGER function cannot: 5
- Allocate managed memory
- Call managed code
- Enter a GC-safe point
- Toggle the GC mode
- Block for long periods of time
- Synchronize with the GC
- Explicitly trigger a GC (duh)
- Call any other function marked GC_TRIGGERS
- Call any other code that does these things
This safeguards are used to protect the code from introducting
A GC hole occurs when code inside the CLR creates a reference to a GC object, neglects to tell the GC about that reference, performs some operation that directly or indirectly triggers a GC, then tries to use the original reference. At this point, the reference points to garbage memory and the CLR will either read out a wrong value or corrupt whatever that reference is pointing to. 6
By putting all these limitations on the code you can get help from the runtime and protection to not introduce problems.
Sets GC modee on the function.
Consider two possible ways to schedule GC:
- Preemptive: Any thread that needs to do a GC can do one without regard for the state of other threads. The other threads run concurrently with the GC.
- Cooperative: A thread can only start a GC once all other threads agree to allow the GC. The thread attempting the GC is blocked until all other threads reach a state of agreement.7
Declares whether an exception can be thrown out of this function. Declaring NOTHROW puts the thread in a NOTHROW state for the duration of the function call. You will get an assert if you throw an exception or call a function declared THROWS. An EX_TRY/EX_CATCH construct however will lift the NOTHROW state for the duration of the TRY body. 8
Next on the list we have defensive coding mechanisms. It is a good practice to ensure that arguments are correct before we go next.
VALIDATEOBJECT uses another FCall
_ASSERTE -> https://msdn.microsoft.com/en-us/library/ezb1wyez.aspx
All right, now we are getting to something meaty. First thing to spot here - TODO mentioning that VB non zero based array support was not added and is not supported. If this is non zero based array we just return with False
Another two preconditions which may force the code to end prematurely.
- first checkin if the sorted array contain only primitive types
- second type of key is verified if has the same type as the items… wait what? arent’t we sorting array? Sure we are and that is why
itemsin this scenario is null thus we dont check the other preconditions. TrySZSort not only supports arrays with only items but also by SortedList that is implementation of IDictionary - has both keys and items. Entry point for this function is here
You cannot sort SortedList but when it is created it Uses
Array.Sort to generate initial sorted state. When new items are inserted Binary Serach is used to idenfity the index and place to insert new item.
left == right - cover scenario when slice of arrays is being sorted that has a length of
right have the same value in that case.
But what is
0xfffffffff? and why right is checked for it?
0xfffffffff is a represantion of
-1 in Two complement system. How is
To create value in two complement:
- take one complement value
- add + 1
if we take 32 bits values
then 1 in Binary will be -> 0x00000001 = 00000000 00000000 00000000 00000001
-1in the one complement is the opposite = 0xFFFFFFFE -> 11111111 11111111 11111111 1111110
to make it two complement we need to add +1 so
0xFFFFFFFE + 1 = 0xFFFFFFFF
To check if that is the correct value we do arithmetic
-1 = 0
Why then use
0xfffffffff instead of
-1. I got help from a friend krzaq with this one.
right argument is of type
UINT32. It is a unsiged value for which
-1 doesn’t exist. But in order to still be able to check if it is
-1 you have to use
-1 might work it would be depend on the compiler implementation how situation like that is handled. With
0xfffffffff you can be sure that code works correclty. more-details
I also checked how will compiler behave in scenario with 0xFFFFFFFF using Compiler Explorer
This switch statement is used to check which generic implementation of IntrospectiveSort will be used.
To find what does ELEMENT_TYPE_I1 there are two resources.
Based on that we get this nice mapping
IntPTR and UINTPTr is not supported.
For Float and Double there is a special case.
Before doing any sorting there is a Function
This function in O(n) iterates through the list and moves all the
NULL values to the left changing list start position to be the first element that is not
NULL. Why not treating
NULL as a value < 0 and just sort it with the rest of values? There is a crucial note for that.
Prepass is required to get rid of unspecified behaviour. If comparison to NaN always yields false then
1 >= Nan = false and
Nan >= 1 = false. It makes it imossible to make ‘deterministic’ comparisons.
This operation is O(n). Later on
IntroSort (more on it soon) algorithm is used to sort. It has oworst and average O(nlogn) so the complexity of doing
O(nlogn) + O(n). nlogn is bigger than O(n) so the overall complexity is O(nlogn) as with Big O notation the most significant component is taking over.
We have covered special scenario of Double types.
primitive type is simple integer, IntrospectiveSort function is called without any other logic.
Is it time to get to the sorting algorithm itself - yes it is.