Technically, we also make the assumtion that the architecture even *has* a stack. The C standard does not require a stack to be present at all. In fact the word "stack" is not even metioned in the C standard one single time. Instead the C standard requires the architecture to have some kind of mechanism to automatically allocate local variables. But this does not have to be a stack.
@@CallousCoder But it is not something that the C language requires. The C standard makes no assumptions about which target platform and what compiler will be used. E.g. I can compile my code with compiler options to randomize order of things that are usually allocated on the stack. Or even have a system which uses two or more stacks for data of different size and type. A well-formed program (without UB) without pieces relying on implementation-specific behavior will still be running correctly. Any solution to the question of the video is bound to rely on assumptions about implementation-specific behavior. I.e. such a solution will not be fully governed by what the C standard dictates about correct programs written in C.
@@PTh0rn Hardware may even have multiple separate stacks for e.g. code and data. It is not so exotic: x86's CET extension maintains a separate isolated stack for return addresses. If one has multiple stacks, then these stacks may theoretically grow in different directions, and the question of the video becomes invalid.
@@GrigoryRechistovYes I totally agree! It is more dictated by the ABI of the OS and even in a lesser extend by the hardware -- the hardware can help, but there's no requirement to use it. The OS ABI is more decisive in this.
All of your solutions use undefined behavior. The compiler is free to do whatever it wants because pointer comparison operators between objects that are not from the same array are undefined behavior.
Not only are they all undefined behavior, the attempted use of volatile was incorrect and gcc and clang remove the recursion and the code just winds up comparing two locations in the same stack frame anyway.
@@npip99 It's possible to avoid the UB by casting the pointers to intptr_t before comparing them. Then the best we can say that *if* the compiler has not inlined the function call and *if* the target ABI uses a stack and *if* the stack grows monotonically in one direction, then the function will return the right answer.
@@npip99Alternatives: 1. No need for recursion, use another function and add `___attribute___ ((noinline))` to avoid inlining. Works with gcc/clang. 2. Turn off optimization with `gcc -O0` (dash, capital O, zero). This also stops the compiler from reversing the order of local variables (as it happened in the video). 3. I'd use just one function and `alloca(10000)` (it's like malloc, but on the stack) because gcc does not change the order of alloca() -s: #include #include #include int main() { intptr_t a1 = (intptr_t)alloca(30000); intptr_t a2 = (intptr_t)alloca(20000); printf("a2-a1: %d ", a2-a1); } About undefined behavior (UB): Although the standard says to avoid UB, the reality of life is that we encounter UB regularly (the foundation of the C standard was designed in a different era, before we had much experience with portability and what works). Avoiding it is not always feasible, but mostly it just goes unnoticed. Each compiler has their own (maybe different) solution when implementing UB, so we can't assume what the compiler will do, but have to dig deep and find out. Different compilers will need different solutions to solve this challenge. Of course this effort often stops at the phase "it works on my computer" 😃
the C standard (ISO/IEC 9899) does not explicitly mandate the use of a stack for local variables. The standard describes the abstract machine, and the choice of using a stack or another method for managing local variables is left to the implementation.
no idea what the best solution is here - my naive guess is to ask about the ABI (specifically calling conventions), write a function with many parameters in the signature until they are no longer passed via register, then add another two parameters such that those two values are guaranteed to be passed by being pushed onto the stack, subtract their addresses (operand order dependant on calling convention), then return a value based on the sign of the subtraction result - abysmal style but ugly and correct is better than stylish and wrong right? (could honestly be ugly and wrong for all I know) edit: this is naive af considering access to ABI would contain the answer, down below someone suggested examining stack pointer directly via asm which is stylish and correct
I think the result you have there is still not quite enough. The compiler could try to reason about the function call and realize that since it'll always terminate within 2 recursive steps, that it can be inlined into itself, then this inlined version of the function can reorder the addresses of its local variables. The solution to this depends on the compiler. On gcc, you can set -O0 to prevent inlining entirely, or you could put __attribute__ ((noinline)) into the function signature to make sure it's actually allocating stack space.
@@EnterOne100 How can it inline, since the compiler no longer can prove that the recursion is finite? For all it knows, the volatile pointer could be set back to NULL between each recursive calls
I don't have much practical knowledge in C, but It's good to know what I've learnt in my university was enough to come up with the same reliable solution to this problem.
This is not a reliable solution. A compiler may still optimize away this recursive call because it can prove that the depth of recursion will always be two levels. So there is no guarantee that desired number of stack frames will be created. Not to mention that neither the presence of stack nor regular allocation strategy for placing objects on it are guaranteed at all.
@@GrigoryRechistov wouldn't the creation of stack frames (and thus their order in memory in this example) count as observable behavior that the compiler couldn't optimize away?
@@plesleron No, for at least two reasons. 1. No guarantees exist that a stack frame will be created for a given function call. Inlined functions have no own stack frame, and the compiler is free to inline any function (not just those marked with "inline" keyword). Recursive functions are not exempt from it. A compiler may partially inline recursive call or specializations of the function. E.g. I know for a fact that GCC will replace tail recursive calls with jumps when the conditions are right. All such tail-called functions will share the same stack frame. 2. You cannot access (neither read nor write) stack frames from a C program in a portable way. Their existence is not observable. No standard library call is defined for accessing them, and relying on a third-party library or inline assembly or such is outside the well defined portable behavior (i.e. it is not UB, thankfully, but the result is unspecified or implementation-defined).
@@GrigoryRechistov I would see that as the continuing part of the interview, where you discuss that this makes assumptions about compiling without optimizations, why those assumptions are necessary (your comment about deterministic optimization), and the depth of testing required/importance of getting the right answer to the problem every time versus the vast majority of the time. All of these engineering tradeoffs are important outside of the toy problem.
Comparing pointers that point to things that aren't part of the same object (ie two entries in the same array, or two members of the same struct) is undefined behaviour. The C compiler can make this code do whatever it wants. The spec reads: When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object types both point to the same object, or both point one past the last element of the same array object, they compare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.
I practiced this myself after seeing that error being pointed out in the comments. It doesn't even require recursion. 1) Declare a function where you will have a volatile two size array, this is done in order to invoke everything on the stack in C. Place two volatile int values with them inside of it. 2) Since you declared the array you know which one goes above and below so you can just compare the two locations of the array (&array[0] > &array[1]) which would be defined behaviour. 3) Do the return done in the video based on the difference of the two addresses and you're golden.
@@shroomer3867 - this was my first thought but with structs... but actually I don't think it would work. Since the elements always have to go in ascending order, the function would always return "up", regardless of whether the stack grows up or down. The stack growing down doesn't mean the actual data goes backwards (or changes endianness). This would only affect whether the head or tail of the array is closer to the base of the stack.
I'm not confident that after optimizations, there's any defined behavior that accurately describes the stack direction, especially since the stack is usually just an implementation detail so the compiler is free to not use one at all.
yeah that's one thing I'm not sure about here either. My first thought was to use a static array and compare &array[0] against &array[1] but the more I think about it a compiler could just sorta decide to work backwards for arrays compared to everything else, and it could decide to do *_anything_* backwards compared to everything else, so I'm not sure there is any architecturally-constant answer here.
You can always write inline assembly where you push two values onto the stack and compare their addresses. That way, you only have to trust the compiler not to optimize your assembly (which I assume it wont do), and the assembler to correctly assemble your code. You can also do it in only assembly as well.
@@Stormrage476 At that point, if you know which CPU architecture you're targeting, you might as well just check out the documentation and write code expecting the stack to behave in the way it's documented. In fact, I'd argue the most practical solution to this problem is just having a check at compile-time of the target architecture and compare it to a known database since that comes with no runtime overhead at all for what's effectively a compile-time constant.
@@robonator2945 Pretty sure arrays are laid out from lower to higher address, simply because the way to access them uses this assumption. C has no way of knowing to "pretend" when *(arr + i) should actually be *(arr - i) in cases of arrays because arrays frequently decay as pointers. Hence it MUST allocate them in the typical fashion.
Oh, that sounds like a nightmare. You're assuming a particular target processor, or you're writing assembly for every possible processor and using lines like #ifdef PROCESSOR_6502 to assemble the right code for the target processor. And my understanding of the problem was to do it "in C."
I think this is the only correct answer. In other words, "No I can't write a C program to determine the underlying architecture but I can write one in assembly".
@@almightyhydra even then you make the assumption that the function implementation uses a stack. C does not define that. So C would need to find a way to implement this without a stack when a CPU doesn't have a stack register or the running system doesn't have that concept.
the compiler cannot tail call optimize as the lifetime of the argument still needs to be maintained but it could inline it, in the end the code is bad an has undefined behavior you cannot compare two unrelated pointers.
In the 90's I wrote a function that could tell if a pointer was stack allocated but I solved it with inline assembly - just getting the SP register and comparing it to passed in pointer.
1. "int x, y = 0" only initializes 'y'. To initialize both variables, you have to write "int x=0, y=0". 2. 'Volatile' does not just mean "don't optimize", its semantics are actually quite narrow - writes and reads from volatile objects are considered as observable side effects, so the compiler has to preserve their order among themselves and relative to other I/O. Note that only actual reads and writes matter - if you allocate a 'volatile' variable, but never actually access its contents, then the compiler is allowed to remove it in its entirety. So, in your example, the 'volatile' qualifier only affects the initialization "y = 0", while 'volatile' on 'x' is literally useless. Also, as other comments noted, even the recursive function is still not safe. Firstly, a modern compiler is able to inline even recursive functions (so that you'd have many layers spelled out at once), which would bring both locals into the same scope and allow their reordering. Secondly, even without that - since all inputs to the function are known at compile time, the compiler may just interpret it right away on its own virtual machine, which might be completely different to the host, including the stack growth direction (this is also one of the reasons why you can't do reinterpret_cast in constexpr). So, to make sure your code actually gets run on the host, and the way you wrote it, you should also disable compiler optimizations.
Both solutions invoke undefined behavior: you are not allowed to compare unrelated pointers for which is greater, only for equality. A compiler is free to optimize those comparisons to an arbitrary constant, irrespective of the stack growing direction.
@@erikkonstas Yes, but knowing it is undefined behavior and not merely implementation-defined behavior means we cannot rely on the solution even if we know there is a stack and there is nothing complicated with pointer representation, as the compiler is free to do whatever. Someone commented under the video that the result depends on optimization settings on x86_64, one of the better behaved targets. Someone else in the comments posted a better solution which, while still technically invoking undefined behavior, at least survives optimizations, as it uses volatile function pointers, and it would work reliably under a few reasonably common conditions.
@@noomade Here is it, by @dekutree64 volatile int *ap, *bp; bool f1(){*ap=*bp=1; return bp>ap;} bool(*volatile fp1)()=f1; bool f2(){int b=0; bp=&b; return (*fp1)();} bool(*volatile fp2)()=f2; bool up(){int a=0; ap=&a; return (*fp2)();} The conditions I think this relies on are 1. the stack exists 2. both return addresses and local variables are stored on that stack 3. all pointers are comparable 4. for two separate allocations, either all pointers into one are less than all pointers into the other, or greater 5. C implements pointer comparison the simplest way 6. sizeof(size_t) == sizeof(uintptr_t) 7. compiler always respects volatile for globals. Maybe few more.
@@noomade Maybe allocate an array and compare adjacent elements? Well...no, that won't work either. The compiler is free to put either varaible "above" or "below" the other.
A few questions about your final solution: 1. Shouldn’t x still still be volatile? 2. Are you worried about if the compiler decides to do some form of optimization and removes the recursive call? 3. Why not get the stack pointer and compare it to the previous stack pointer?
1) doesn't matter, the solution is still wrong. 2) and it's wrong because of this. 3) there's no stack pointer (or requirement for existence of stack) in C
2:17 Security people will comment that int x, y = 0; only initializes y with 0, not x. It should be int x = 0, y = 0; One more issue is that with comma separated variable initialization, C does not specify the order that the initialization has to take place. Thus, to check the stack direction, it should be int x; int y;
@@noomade Even though in practice, most compilers initialize left-right, it is not defined as part of the C standard. E.g. if you do int x=0, y=x; you get a compiler error.
@@noomade Statements separated by semicolon are executed sequentially, thus int x=0; int y=0; is guaranteed to initialize x first. I think you are right that only declaring them by int x; int y; without initialization does not impose a specific order on the stack, it may be up to the compiler.
@@noomade There may even not be a stack, as other commenters here also discuss :) But if you assume there is a stack, and check the addresses right after a proper initialisation, I think you can be quite sure about the direction.
@@noomade To be sure, you could initialize x and y in succession with e.g. the current time as integers in nanoseconds. No way a compiler would optimize that to happen in reverse order, and it can even be checked. But I agree that without any dependency, the order is at the compilers discretion for what gives the best optimization.
I am a bit confused on the first approach? if the pointer to x is greater then y then wouldn't that mean the stack is growing down and getting more negative? Since the second value that was allocated on the stack, y, has a smaller address then x which was the first value allocated on the stack? Assuming no compiler optimizations are made.
You're right. The condition is mistakenly inverted, that is wrong. So why is the result as expected? The compiler allocated the variables in a different order than defined, or did some other optimization that fooled the logic. This is the danger of undefined behavior. Funny that the mistake masks the compiler's unexpected behavior, without the presenter's knowledge. In any case the challenge achieved its goal, we now know quite some about him: did not verify the logic (no testing, even mentally), wrote if () return true; else return false; instead of return (); Rookie mistakes.
Not a correct solution, but a better one which gives more insight to the compiler's actions. Undefined behavior is unavoidable due to the spec, so one has to dig deep into what the compiler actually does. I ran this with godbolt (executes it only on x86 unfortunately), compilers: gcc, clang, zig cc (results are slightly different). #include #include int main() { char* a1 = (char*)alloca(30000); char* a2 = (char*)alloca(20000); char* a3 = (char*)alloca(10000); char* a4 = (char*)alloca(1000); char* a5 = (char*)alloca(100); char* a6 = (char*)alloca(10); printf( "&a2-&a1: %ld ", (char*)&a2-(char*)&a1 ); printf( "&a3-&a2: %ld ", (char*)&a3-(char*)&a2 ); printf( "&a6-&a3: %ld ", (char*)&a6-(char*)&a3 ); printf( "a1-&a6: %ld ", a1-(char*)&a6 ); printf( "a2-a1: %ld ", a2-a1 ); printf( "a3-a2: %ld ", a3-a2 ); printf( "a4-a3: %ld ", a4-a3 ); printf( "a5-a4: %ld ", a5-a4 ); printf( "a6-a5: %ld ", a5-a4 ); } Seeing the stack grow with the exact size of the variables shows that the compiler did not just ignore our intent due to UB. Note: `-O1` compiler parameter keeps the original order of the variables (prints -8), `-O2` and `-O3` reverses their order. This is what happened in the video. abs(a2-a1) == 20000 (with clang) is also a sign of the stack growing down. It would be 30000 if it grew up. That gives a redundant confirmation for the validity of the results.
@@noomade a pointer for 64-bit cpus is 8 bytes (64bit), therefore the steps in allocation are -8 -8 -8 when the pointers are allocated in the order of declaration. -24 16 -24 means the compiler changed the order to something like a1, a3, ?, a2, a6, ? (I skipped a few, so the info is missing). a2-a1 = 20000 means (note: I made a typo and edited the comment, it's 10k vs. 30k): stack growing down: [a1:30000]
Ok, I don't exactly understand how the stack is pictured here. So in the first example, if the address of y is greater than of x, then in this example it's growing down. But if the y is allocated later, then why does this mean then it's growing down (ie more negative) if the latter variable address was higher? But if you take the recursive example it makes sense, since x is now the variable that's allocated later, because we are at the end of the recursion and "other" is the previously allocated variable (and it's now right side of the greater than sign). So this makes sense to me, and seemingly disagrees with the first example. Yet their print was the same.
This is the comment i was searching, in fact , if we suppose that x is pushed into the stack before y , then &x is greater than &y , therefore upordown() should return true.
I'm a little rusty so I may be wrong, but back when I studied assembly I noticed that some of the more common calling conventions will allocate a stack frame for a function call, and then will allocate the variables within the stack frame in the "reverse" direction. So if the stack grows down, the new stack frame is created at the bottom, and then the variables are allocated from bottom-up of that particular frame. This may be what's going on here as well.
Could you explain a bit more? Why is allocating an array different from allocating an int? Why does allocating a small array guarantee that it will be allocated on the stack? What do you mean by "small" exactly? Is there a threshold that means larger arrays get allocated to the heap instead and if so what is that threshold?
@@aspzx You can't store an array in registers and an array in C must be allocated sequentially in a continuous chunk of memory otherwise pointer arithmetic doesn't work. Small means just that I'd personally allocate maybe 100 numbers just in case but as far as I know even just 2 would be fine.
@@aspzx An int would be 32bits on 64bit machine. So, the compiler could easily put this in any available 64bit general purpose register. If you were to allocate an array of size say 8 ints 'int arr[8];' then it's not feasible to use registers to store. Regardless of size, would only go on heap if storing to an address returned with 'malloc()' and friends.
Most embedded C compilers would use Registers, not the Stack for temporary variables. Recursive probably would force it to use the stack as the compiler don't know how much space it needs. Side note, A Contant Int would force it to store it as ram variable, if you want it to be remembered for next call.
Recursion doesn't necessarily force variables to be allocated on the stack, taking their address with & operator does (because values on registers don't have addresses)
Wouldn't constant be most likely kept in flash though? Especially for some embedded architectures. Another way to make sure would be to create compile size array to go around registers being used. But I think volatile would stop it from happening and also calling for address of variable wouldn't make it use registers (I think).
@@anar.bastanov As return address is always store on the stack, would the test allow inline assemble? Have to make sure to use noinline for the function, and you would need to use correct asm for the platform. uint32_t sp; asm( "mov %%rsp, %0" : "=rm" ( sp )); return sp;
@@sorek__ Using the keyword Constant inside a function is different. Passing an array of like 20 vars, should force the use of the stack. And that is why passing a single pointer is betters, so you don't use 20 stack push/pop's
You can just use a print statement to guarantee the use of a variable’s address cannot be optimized away, this way you get an actual automatic variable rather than a register.
I actually thought of an extra function that has a variable and returns the address of the variable to UpOrDown and UpOrDown compares it to the address of its own variable. Recursion removes the need to create an extra function but adds the need for a pointer to be passed instead.
A single call to alloca() is not enough. It will return you a pointer to (allegedly) data on stack, yes. But then you need to compare it to another pointer allocated on the same stack. And this is where no guarantees are provided by the language about the order in which multiple alloca()'s or any other local allocations will happen.
@@GrigoryRechistovmaking second alloca conditional based on the first would guarantee the order int *first, *second; first=alloca(1); if (first) second=alloca(1); return first>second;
@@ic6406 There's no dependency on values below the call. `return upordown(&x)` can be easily tail-call-optimized into a simple jump because there is no additional work to do after the call returns and the return value of the callee is our return value.
For those wondering whether it is possible to have a C program run without a stack, I have an example for you. Early x86 firmware boot code has to run for some time *without any RAM all*. That is, no memory for either stack nor for heap. Program's code is read from read-only flash. That is because the memory controller device has not yet been properly programmed. The first thing the firmware might want to do it to make RAM available. But until that moment, one has to deal with lack of memory. One early solution to this was to have a C compiler to produce programs that allocate everything on processor's registers. Needless to say, maximum stack depth is very limited in this situation. But it does not mean you cannot have a standard-compliant compiler for such environment. You might not be able to use recursion at all, but that is because undefined behavior of exhausting implementation-defined recursion limit will kill it early. Which is standard-compliant behavior. For those curious if we still have to use such trick of allocating everything on registers today, then the answer is no. Firmware writers have learned to use CPU's caches as substitute for RAM in early boot. Caches require no configuration to become usable and provide several megabytes of addressable storage, which is much better than half a dozen of 4-byte registers.
2:50 the return is inverted. The compiler is also doing the opposite of what you expect it to do: `-O2` and `-O3` optimization reverses the order of the local variables. Thus the result is double wrong, which in boolean logic ends up being right 😄 Also, simply `return &x < &y` will do. `return true; else return false;` is also a telling sign for the interviewer.
I tried both local variables, volatile or otherwise, and with recursion, and they both had the same results. Normal compilations reported downward growth, but optimized compilations reported upward growth. Something to keep in mind.
This means that the either program's result is unspecified or undefined. Compiler optimization level or compiler choice should not affect outcomes of well-defined C programs. Ergo, this program is not well-defined (see other messages in the comments from many commentators what assumptions are wrong)
@@vytah True. Only pointers that refer to insides of the same array or struct/union may be compared, otherwise the C standard (6.5.8p5) explicitly marks the result as undefined behavior.
11 місяців тому+1
@@GrigoryRechistovone past the container is also still fine.
This is exactly my thought process when you asked the question - compare two variables addresses off the stack - but what if the compiler mucks with their order? - move the variables into function arguments, - but what if the compuler reverses function arguments? - use a function call to force a call frame onto the stack and compare addresses across the call frame
My first thought was to create a struct with two variables, initialize an instance and compare the pointers of the variables, as structs are required to keep their order.
Yes but that will answer about how structs are stored in memory, not how stack allocations are made. There is a difference, and the orders may be different.
@@matthewrossee Easily. The compiler is allowed to put them in any order or optimize them away. "volatile" will help with the latter but not with the former.
@@GrigoryRechistov ok that makes sense. What do you mean by optimizing them? From what I understand, the compiler can’t inline the values because then how could you take the address of these variables?
@@matthewrossee It cannot inline values of variables but it can values of addresses of variables inline (or make other conclusions like being NULL or non-NULL). Note that the code in the example does not dereference pointers in question, it only operates on addresses themselves.
I have a strong feeling that in the situation where i would need to know the direction of the stack there should be much better and reliable way to do it.
I was thinking in the same direction of multiple function stack frames. I was thinking of 2 functions: 1 basic upordown() function with no parameters which returns enum UP or DOWN. This upordown would simply call with the address of a variable in upordown another function checkIfStackIncreasesUp(int *reference_address) which returns bool by comparing the parameter received address with some internal variable's address. No recursion is needed :)
Probably better to not name it upordown because it's returning a bool. I'm legit inclined to name it doesStackGrowUp... And I've never used does in a function name before. lol Your teammates should ideally not have to read the code of the function to understand what it's doing. And comments are not an adequate substitute for good naming.
1. You don't need recursion, can have two functions, one calling the other. 2 You forgot about inlining functions, recursion unroll, register argument passing.
Of course, comparing to pointers not pointing into the same object or array for anything but (in)equality is undefined behaviour, and the compiler is allowed to do whatever it wants in that case. So in theory the program could output "nice try" instead. So the first assumption is that the optimizer does not take advantage of that undefined behaviour.
You didn't need to write a recursive function like that. Since all you care about are addresses, and you have no intention of dereferencing them, you can take the address of a variable on the stack in one function, and return that, as a pointer, to the calling function. Then compare that address to the address of a variable in the current function.
This is how I thought to solve it. Recusion works, but his function does two completely different behaviours based on arguments, which to me screams the need for a distinct separation of the methods, one to return the pointer for a variable on the stack, and another to call it and compare addresses.
I think i would ve used alloca() which allocates memory in the stack frame and compared the first and last element's address but your recursion based answer seems more platform proof.
@@4zv4l38I think you need to alloca() twice in sequence and compare their memories. If you use an array and compare its end and beginning, I think it should always show that last-first is positive (because that's the direction an array is oriented in).
@@4zv4l38 i might be wrong ( and probably am) but i feel like alloca would always allocate memory in the stack whereas variables and local arrays might be put into register without the volatile keyword also it's just another use case of alloca
The man page i have on alloca can be summarised as "alloca does something, and probably returns valid and unused stack memory in the process" I would only trust alloca when you know everything about the system. The whole purpose of this code is that you don't, so i doubt this is reliable
2:53 "if x is growing up, its getting more positive, but if x is grown down its getting more negative" then the if statement should be if (&x > &y) return false; //because the variable y has a lower address, which means it went down also in the recursion code this logic is flipped
Good video. My only issue is with a boolean function being called upordown. It makes the code read as "Is the stack growing up or down? Yes/No." and does not imply directionality which is the real question we're asking. Something like isGrowingUp() or isGrowingDown() would be better.
i dont think it "can't get optimised out because we're using recursion" volatile does permit the compiler to make optimisations, it's there for hardware the CPU isn't controlling. the compiler just isn't allowed to assume the value won't change on it's own. other optimisations may happen. there is __attribute__((optnone)) which might suit your use case better. i also think the use of recursion makes the example more complicated than it needs to be. it seems like the condition is the wrong way around (it returns true if the address from the older stack frame is greater. ie, "up" when it's going down.)
I think your second/recursive solution can be incorrect due to tail recursion optimizations (reusing the same stack frame when recursing!) That being said, I’m no expert, so I may be wrong
The reference itself is not destroyed, just the memory it points to is no longer "reserved". However, pleaee note that the code does not use a reference to a destroyed variable. The second recursive run determines the result, where the first instance of the variable (whose address is in the argument) is still exists. The second run returns the boolean outcome, not the address of its local variable which is going to be destroyed. So theoretically it is not an use-after-free error. Regardless of this, while the question itself is interesting, there is no way to write this program with 100% certainity that it will work in a defined way on all architectures.
If you look at the C11 reference for relational operators, section 6.5.8, this pointer comparison invokes undefined behavior since the variables aren't part of the same array or struct. So, a compiler would be allowed to optimize your function to lie about which way the stack grows. I'm not sure if any compilers actually do optimize this comparison.
There is also no concept of memory addresses in C. The numerical value of a pointer could be anything, as long as it can be dereferenced back to the original variable. Pointer arithmetic and comparison operations are guaranteed to work, though.
@@MrEdrftgyuji Pointer arithmetic and comparisons are not always guaranteed to wwork. As a rule of thumb, if you compare two pointers that aren't identical and don't point within the same array, the result is undefined behaviour.
As you asked the question, my first answer was to have two functions A() and B(). Where B returns the address of a stack variable and A returns if that is bigger than its own stack variable address. Two functions, but less code.
tail call is impossible in that case, or, rather, even if possible you should assume there is no tail call for that case, see david wragg c tail calls 2014
@@AnataBakkaso basically if the behavior is well defined without TCO but breaks if TCO is applied then it isn’t applied. This of course assumes the program is well defined which it would be as long as long as the pointers are casted before comparing them
@@natnial1 Yeah, that "well defined" part is where it all breaks; TCO does not "break" anything in regards to well-defined behavior, but here we actually want to tame UB.
You don't really need recursion there. You can make 1 function that returns the address of a volatile local variable as a usize_t (to not confuse people to dereference the invalid pointer/address) And then make the actual upordown function that compares the result of the other function to its volatile local variable. size_t nextStackframeAdrr() { volatile int x = 0; return (usize_t) &x; } bool upordown() { volatile int x = 0; volatile size_t addr = nextStackframeAddr(); volatile size_t addr2 = (size_t) &x; return addr2 < addr; }
does volatile enforce the order of operations too? from what I know, there is still nothing preventing the compiler from re-ordering things like variable declarations
Love your videos. I like to think I’m a semi-competent C hacker on a good day, but it’s amazing how much I’ve forgotten or don’t consciously think about regularly since college.
Haha, fun stuff. This was my one of my interview questions at Microsoft when I tried to intern there. I had limited to no knowledge about OS architecture. It wasn't even the position I was going for. Anyway, I failed it. My initial answer was create 2 variables and compare the address as you've said but it wasn't enough as they can be randomly allocated or as you said optimized. Create 2 functions and creating a variable inside each would be good as they get a full row of memory. Also, it can avoid any complexion like recursion. Still this question hunts me to this date. haha was over 6 years ago. Luck is a big factor in life. Knowledge is what brings that luck closer to us !~ Keep up the good stuff, interesting videos.
It's not just that they may be reordered. It's also that comparing pointers not part of the same array is undefined behavior. You could get back anything. You could get back that x is above y AND y is above x, because with undefined behavior logic does not apply.
How about using inline assembly? Save rsp at local variable in inline frame #1, allocate some new local variables, then check the changed rsp value at inline frame #2. Of course, the local variable should have storage class auto, since static class will make the assembler save variable in other space.
Great video! However I did find something I found interesting when trying to compile both of these solutions... I compiled a program with both of your solutions using gcc 11.4.0 and clang 14.0.0, For your first solution gcc gives Down while clang gives Up... For your second solution both compilers return Down. Edit: I am using pop-os 6.5.6 if anyone else wants to verify this
Feels pretty good that my initial instinct was "don't assume the compiler's ordering of local variables, force the creation of a new stackframe to grab a pointer we know has to be deeper in the stack" was completely correct
those are completely different things. here is a short explanation of two of them: volatile basically tells the compiler to not optimize whatever you've marked as volatile. I recommend messing around with it in godbolt. ## is some sort of an operator used in the CPP (C Preprocessor) that joins two tokens together, so imagine this: #define JOIN(a, b) a##b then `JOIN(hello,World)` would produce the token `helloWorld`.
It's been almost two decades since I've done programming like this. I ended up over-engineering it to allow the function to be called without any parameters. My brain switched the question to "write a function" rather than "write a program" and I didn't want users of my function to have to pass in NULL or anything else. Other than that, the solution was pretty much the same. Cool question!
@@minirop good point. Just curious. I am sure there are some things different architectures can’t do differently. I guess I am wondering why the his isn’t one of them.
Cars can drive on either side of the road, but it doesn't matter WHICH side as long as everyone agrees. In a similar way, a computing architecture can grow its stacks "up" or "down", as long as it sticks with one or the other. Stack growth is invisible to 99% of programmers anyway.
*Angry comment about function name not being something like StackIsGrowingUp, instead of upordown as it does not indicate that it is returning a bool* 4:19 My guess is an array because it is a contiguous chunk of memory and index 0 is always addressed before index 1. Edit: Aw, I think my method works tho, and from reading comments looks like it works better.
Wait, does up mean that x is stored at the address (base of the stack) + (some number)? If so wouldn't y be at &x + 1? So if the stack grows up wouldn't &x < &y?
My first idea wad using functions and checking a variable in their scope against eachother, however i didn't think about using recursion and i guess using recursion also eliminates (?) The possibility of the compiler inlining the function and breaking that logic
I think he did it to prevent a compiler optimization that just moves the function body of the helper function to its only call, therefore creating a similar situation as before, where the compiler can change the order of the variable declarations.
@@dennismuller1141 Hm, that kinda makes sense. Though I also wouldn't be surprised if the compiler could optimize the recursive call the same way. Tbh in general, I'm not sure there's anything stoping the compiler from optimizing this whole concept into whichever direction it wants, since stack direction doesn't seem to be something that's guaranteed by the spec.
@@dennismuller1141 You make a fair point. Compilers are free to inline functions like you describe. But I don't think the recursive solution is exempt from this. Compilers are pretty smart these days. They are free to "unroll" recursive calls as well as optimize away unreachable branches. So in the end, the same problem arises. The better approach would be to use some compiler annotation, such ass GCC's "noinline" annotation, to prevent such a compiler optimization.
I'd just write a few lines of c, compile with the S option, open gdb, and look at the assembly code. Then, the interviewer would know I knew C, assembly, and how to use a debugger other than printf().😂😂
You can't because the functions' code doesn't live in the stack but in the exact opposite side of memory (at least in x86), in the text segment. Only local variables and some other internal values (return address, last frame pointer) get placed in the stack.
The address of the functions won't be in any guaranteed order, but presuming you mean the address of a variable in main vs one in the upordown function, I believe he was trying to avoid the case where the compiler optimises out the call being made and therefore making the comparison not work as intended.
Just an excerpt: "The key thing to understand about the 8 bit PIC architecture is that the stack size is fixed. It varies from a depth of 2 for the really low end devices to 31 for the high end 8 bit devices. The most popular parts (such as the 16F877) have a stack size of 8." ^^and they do have C compilers. So there are totally devices with limited hardware stack sizes actually - otherwise its fun little excercise I agree, just sayin' 🙂
Upordown is a bad function name IMO. Expected behavior for me would be it nearly always returns true, unless the stack grows horizontally, or non linearly. I think these are better: bool stackGrowsUp bool isGrowingUp
I write almost no C or C++ and this was super fascinating. One of my favorite tech videos in a long, long time. Thank you helping me continually learn every day!
Wow, thanks for the video! The first implementation is the one that I had in my head. The only twist I could think of is that the function could be inlined, but that shouldn't affect anything.
I'm slightly confused with the stack example shown in the commented code block. In my head a stack is adding to the top, so y would be higher than x. Is it because the 'top' of the stack is actually the stack pointer. so when y is getting added "below" x, it's actually getting added to the "top" of the stack ,since that is where the stack pointer would be?
You could also just do volatile int x =0; int y=x+1; [rest of the first function] The optimizer cannot change the order since y is dependent on x and x might change between the lines.
The first thing I thought of was to compare rsp and rbp, For example: format ELF64 executable SYS_write equ 1 SYS_exit equ 60 STDOUT equ 1 segment readable executable entry _start _start: cmp rbp, rsp jle down ; up mov rsi, up_msg mov rdx, up_len jmp write down: mov rsi, down_msg mov rdx, down_len write: mov rax, SYS_write mov rdi, STDOUT syscall ; exit mov rax, SYS_exit mov rdi, 0 syscall segment readable writable up_msg db "Up", 10, 0 up_len = $ - up_msg down_msg db "Down", 10, 0 down_len = $ - down_msg You could use this by making an assembly function, and linking to it.
I’m confused. If a stack grows ”up” (i.e the stack pointer increments on an add), then (&x > &y) is False, because y was added after x and hence has a larger address, right? But you say that ”x is on top, x is more negative”, which makes no sense to me unless x is allocated after y and we are assuming a decrementing stack pointer. Does ”int x, y = 0;” not add x to the stack before y?
It frustrates me to no end that the names are so close together in intuitive meaning that I always forget the difference. A stack of paper is also a heap of paper. Especially annoying that when learning to code stacks, aka first in last out, I'm taught to think of it as stacking napkins up.
Not really to be fair, a heap of paper would be like if the sheets are thrown at random everywhere on the table, not ina neat pile. A face-down pile of sheets of paper is a stack, not a heap.
For me a heap of paper would be a bunch of paper sheets lying on the floor, all in different orientations and no discernible order. A stack on the other hand is all the papers neatly put together and you can clearly go from top to bottom. In that sense, yes, a stack is also a (ordered) heap, but a heap is not necessarily a stack
10 місяців тому+1
As far as I understand the C specification, comparing pointers in this way is undefined behavior, as already explained in other comments. The danger is that such an undefined behavior will probably often work, which makes it hard to discover the problem by testing. One of the most important C skills is to navigate around these undefined behaviors. Therefore, this answer to the interviewer's question arguably shows that, although the interviewee knows things, they more importantly feel too confident writing potentially dangerous code.
An idea i had in order to solve this was using inner scopes (i.e `int x; { int y; }`) in order to force the inner variable to be after the outer, but i'm not 100% sure that actually happens
@@veritas7010I think that's the point. You just need to ensure that variables are allocated in order. Hopefully, x is allocated before entering the scope and y is allocated in the scope such that &y-&x is always the direction of the stack.
Very cool stuff. I haven't touched C in about 10 years since I moved on to Python/JS/Web and I'm glad to know I could've gotten almost 80% of that in an actual interview, assuming I knew it was a C interview and had time to do a quick refresher, I owe it all to my CS101 teacher back in high school.
I'd use the first method mentioned in the video but mark the function as "__attribute__((optimize("O0")))"_ (I hope UA-cam doesn't mangle this). Many compilers have the option to _sometimes_ ignore volatile keyword in order to aggressively optimize all loops, allocations, and invocations using something like -O3. The _only_ way to prevent this is to mark the function as no-optimize. Also and importantly, I'd start my answer off with "assuming the architecture I'm on uses a stack." It's totally okay to point out assertions like that and let the interviewer press you on it. The important bit is that you point it out, not that you solve every tiny angle of the problem.
@@noomade Well, a stack must exist if the documentation of alloca says that it "allocates size bytes of space in the stack frame of the caller." If it did anything else, I would say the documentation is wrong. You might be right that an aggressive enough compiler might decide to optimize it away, because by most definitions this is not observable behavior.
Correct me here but if top is greater than bottom then isnt it growing downwards. If the location of the succeeding address is lesser than the preceding address isnt it growing downwards?
1: The stack pointer isn't growing "more negative" it's growing "less positive." 2: Your first method returns the wrong value. Note you return First-Variabe>Second-Variable but in the recursion method it's reversed. 3: @2:55 you mention X growing. X isn't growing. Neither is it's pointer. You mean if the difference between &X and &Y is growing. 4: @4:14 you say method one isn't the most efficient. The problem with method-one isn't efficiency, it's that it could be wrong. Big difference.
I like this question a lot. I'm not a C developer, so my first idea was that it would be way out of reach. But then I realized that I could write some pseudo-code. I didn't realize I could just use the addresses of local variables, so my pseudo code used some mysterious method to get the stack pointer. But I was using two separate functions, similar to your recursion (but in my opinion, more appropriate here than recursion, for readability reasons). The amount of reasoning you can do about this even if you don't have the full answer shows how well this question works!
Volatile won’t help here. Volatile means the compiler needs to assume every access to a variable has side effects, so will be very constrained if it wants to rearrange accesses, but has no effect on the location of variables in a stack frame. In any case, the order of variables in a frame (controlled by the compiler) has nothing to do with the order of frames on the stack (controlled by whether the processor stack grows up or down), so your first solution was pretty fundamentally flawed.
Yeah I've watched it over and over and when you said "x is on top, x is more negative" I'm pretty sure you misspoke. Y is the most recent variable, ie "y is on top" and "x > y" means "x is more positive"
I feel this would be better explained with the assembly listing and a memory view open. The stack could be initialized in different ways, also without the recursion there is pretty much no guarantee that it will grow the stack in any direction. The only correction I would make for intel is to say that the compiled code will use base pointer register offsets (EBP), and not the stack pointer directly, so between call frames there will be some stack preservation wrapper copying to and from EBP/ESP.
File-scope (aka. global) variables are usually not allocated on the stack. Those end up in the BSS or IBSS segment of a linked executable and it is going to be allocated directly on heap. The cause is that their size and existence is know at compile time, thus, this can be done because it is more efficient. The init code that runs before the main() zeroes out everithing or copies the initial values in a for loop. Local non-static variables are allocated on the stack, because it cannot be known at compile time how many of them will exist (same func called multiple times) even exist at all (never called).
Yay, I'm a non-C programmer who not only knew the first naive approach, but thought about how the compiler could possibly optimize it and ruin things. Didn't quite figure out a solution before I hit play, but I'm still just happy I was on the right track :)
In some OSes, there is no dedicated stack area but instead stack space is allocated in chunks from the normal memory manager. Therefore, the stack can jump back and forth in memory as it grows.
Not sure if my logic holds, but when you asked the question of a different approach to x,y my first thought was to make a local variable with an array size 2. Then compare element 0 to 1 in terms of address. My assumption is that the compiler would not mix the order of array elements, as part of the definition of an array is it is a serial length of memory. But I don't know specifically how array are allocated on the stack, it very well could be that the first element is stack positionally placed, but then the contained elements are serially placed.
I assume x is the first variable being allocated in the stack. If the adress of x is superior to y, then the second variable (y) would have been allocated "under" the first, thus growing down. The code does not reflect this, but the opposite. Anybody care to explain?
On some architectures the result can be non deterministic if called within the context of a larger more complex program ... in at least some implementations of ARM procedure call standards I was familiar with many years ago, stack frames are allocated on the heap as required, so if the inner function call uses the same allocation, the result would be as expected, but if it allocates a new frame on the heap, the result could be either direction.
this doesnt make sense to me to, in the first one the stack would look sth like 0 x +1 y in the second one wouldnt it be 0 other +1 x since other comes first, so why are we saying x > other when we in the first one we initially said x > y, can someone explain it to me
What's curious is that the equivalent impl in Rust (the recursive one), produces opposite results depending on whether you build in debug or release mode. I don't know why.
Here's my very crude impl, in case anyone is curious: fn main() { dbg!(stack_grows_up(None)); } fn stack_grows_up(other: Option) -> bool { let x = 0; let addr = &x as *const i32; match other { None => stack_grows_up(Some(addr)), Some(other_addr) => other_addr < addr, } }
It’s definitely based on some optimization, because adding a dbg! Of the addr in the Some branch causes it to produce the opposite value. I’m guessing it’s a tail recursion optimization but who knows
One thing thats crucial to mention is using -O0 when compiling. At -O3 the compiler can easily just return true or false since both are valid and comparing pointers is sensitive to inlining.
Comparing pointers like this in C is actually undefined behaviour (i.e. meaningless), not just sensitive. At -O0 the compiler would still be valid to produce code that prints up, down, segfaults, or anything else.
I agree it is an interesting question, to see what the interviewee knows. For example, I haven't used C in a long time and (once managed to set aside the "why do we care") I would have guessed the initial solution, and admitted that would be a guess. The then following explanation on, what is considered "common-knowledge" on the abilities or lack thereof of compilers. Is indeed something I would not have been able to contribute to. "Making assumptions on how the compiler treats effects triggered by a single command" (the 2 initializations) was easy to spot as "If the compiler breaks the plan. It would likely do so here". To which my first thought was: - initialize/assign - read address - initialize/assign - read address Might solve it, if we want to be more sure, we probably could: initialize/assign y, with the value of... the address of x. As this information needs to exist, the compiler would have even less room to outsmart the programmer. That C-compilers have a "magical, can't optimize beyond this"-border around recursion. Is not something I knew. (Again, making it a good question.)
One of my ideas was to check argument's address with local variable's address, there's huge chance that arguments pushes first before locals are allocated.
Technically, we also make the assumtion that the architecture even *has* a stack. The C standard does not require a stack to be present at all. In fact the word "stack" is not even metioned in the C standard one single time.
Instead the C standard requires the architecture to have some kind of mechanism to automatically allocate local variables. But this does not have to be a stack.
But doesn't the fact that you can do recursion automatically mean that there is a stack?
@@dasten123 no, frames could be allocated on the heap and freed automatically on return. some virtual machines do this iirc
@@CallousCoder But it is not something that the C language requires. The C standard makes no assumptions about which target platform and what compiler will be used.
E.g. I can compile my code with compiler options to randomize order of things that are usually allocated on the stack. Or even have a system which uses two or more stacks for data of different size and type. A well-formed program (without UB) without pieces relying on implementation-specific behavior will still be running correctly.
Any solution to the question of the video is bound to rely on assumptions about implementation-specific behavior. I.e. such a solution will not be fully governed by what the C standard dictates about correct programs written in C.
@@PTh0rn Hardware may even have multiple separate stacks for e.g. code and data. It is not so exotic: x86's CET extension maintains a separate isolated stack for return addresses. If one has multiple stacks, then these stacks may theoretically grow in different directions, and the question of the video becomes invalid.
@@GrigoryRechistovYes I totally agree! It is more dictated by the ABI of the OS and even in a lesser extend by the hardware -- the hardware can help, but there's no requirement to use it. The OS ABI is more decisive in this.
All of your solutions use undefined behavior. The compiler is free to do whatever it wants because pointer comparison operators between objects that are not from the same array are undefined behavior.
That's probably the reason why the mistakenly inverted condition still returned the expected result 😀
Not only are they all undefined behavior, the attempted use of volatile was incorrect and gcc and clang remove the recursion and the code just winds up comparing two locations in the same stack frame anyway.
How do you check which way the stack grows then? Obviously we assume the stack grows in a particular direction.
C doesn't require that at all.
@@npip99 It's possible to avoid the UB by casting the pointers to intptr_t before comparing them. Then the best we can say that *if* the compiler has not inlined the function call and *if* the target ABI uses a stack and *if* the stack grows monotonically in one direction, then the function will return the right answer.
@@npip99Alternatives:
1. No need for recursion, use another function and add `___attribute___ ((noinline))` to avoid inlining. Works with gcc/clang.
2. Turn off optimization with `gcc -O0` (dash, capital O, zero). This also stops the compiler from reversing the order of local variables (as it happened in the video).
3. I'd use just one function and `alloca(10000)` (it's like malloc, but on the stack) because gcc does not change the order of alloca() -s:
#include
#include
#include
int main() {
intptr_t a1 = (intptr_t)alloca(30000);
intptr_t a2 = (intptr_t)alloca(20000);
printf("a2-a1: %d
", a2-a1);
}
About undefined behavior (UB):
Although the standard says to avoid UB, the reality of life is that we encounter UB regularly (the foundation of the C standard was designed in a different era, before we had much experience with portability and what works). Avoiding it is not always feasible, but mostly it just goes unnoticed.
Each compiler has their own (maybe different) solution when implementing UB, so we can't assume what the compiler will do, but have to dig deep and find out. Different compilers will need different solutions to solve this challenge. Of course this effort often stops at the phase "it works on my computer" 😃
the C standard (ISO/IEC 9899) does not explicitly mandate the use of a stack for local variables. The standard describes the abstract machine, and the choice of using a stack or another method for managing local variables is left to the implementation.
no idea what the best solution is here - my naive guess is to ask about the ABI (specifically calling conventions), write a function with many parameters in the signature until they are no longer passed via register, then add another two parameters such that those two values are guaranteed to be passed by being pushed onto the stack, subtract their addresses (operand order dependant on calling convention), then return a value based on the sign of the subtraction result - abysmal style but ugly and correct is better than stylish and wrong right? (could honestly be ugly and wrong for all I know)
edit: this is naive af considering access to ABI would contain the answer, down below someone suggested examining stack pointer directly via asm which is stylish and correct
I don't remember, but do you even have to have a stack at all?
Academic C be like: the compiler implementation is left as an exercise to the reader
@quazar-omega 😂
@@ante646 It's UB to compare pointers from two different allocations.
I think the result you have there is still not quite enough. The compiler could try to reason about the function call and realize that since it'll always terminate within 2 recursive steps, that it can be inlined into itself, then this inlined version of the function can reorder the addresses of its local variables. The solution to this depends on the compiler. On gcc, you can set -O0 to prevent inlining entirely, or you could put __attribute__ ((noinline)) into the function signature to make sure it's actually allocating stack space.
You could also mark other as volatile, so the compiler cannot make that assumption anymore
It can. Inline, the reorder other allocations arbitrarily. The just make sure to perform the operations one after the other.
@@EnterOne100 How can it inline, since the compiler no longer can prove that the recursion is finite? For all it knows, the volatile pointer could be set back to NULL between each recursive calls
Maybe we can check the position of the return address with __builtin_frame_address(0)
@@shadamethyst1258 or you can take the variables from input
I don't have much practical knowledge in C, but It's good to know what I've learnt in my university was enough to come up with the same reliable solution to this problem.
This is not a reliable solution. A compiler may still optimize away this recursive call because it can prove that the depth of recursion will always be two levels. So there is no guarantee that desired number of stack frames will be created. Not to mention that neither the presence of stack nor regular allocation strategy for placing objects on it are guaranteed at all.
@@GrigoryRechistov wouldn't the creation of stack frames (and thus their order in memory in this example) count as observable behavior that the compiler couldn't optimize away?
@@plesleron No, for at least two reasons.
1. No guarantees exist that a stack frame will be created for a given function call. Inlined functions have no own stack frame, and the compiler is free to inline any function (not just those marked with "inline" keyword). Recursive functions are not exempt from it. A compiler may partially inline recursive call or specializations of the function. E.g. I know for a fact that GCC will replace tail recursive calls with jumps when the conditions are right. All such tail-called functions will share the same stack frame.
2. You cannot access (neither read nor write) stack frames from a C program in a portable way. Their existence is not observable. No standard library call is defined for accessing them, and relying on a third-party library or inline assembly or such is outside the well defined portable behavior (i.e. it is not UB, thankfully, but the result is unspecified or implementation-defined).
@@GrigoryRechistov What if you make it do recursion based on a rng value. Surely a compiler couldn't unroll this.
@@GrigoryRechistov I would see that as the continuing part of the interview, where you discuss that this makes assumptions about compiling without optimizations, why those assumptions are necessary (your comment about deterministic optimization), and the depth of testing required/importance of getting the right answer to the problem every time versus the vast majority of the time. All of these engineering tradeoffs are important outside of the toy problem.
Comparing pointers that point to things that aren't part of the same object (ie two entries in the same array, or two members of the same struct) is undefined behaviour. The C compiler can make this code do whatever it wants.
The spec reads:
When two pointers are compared, the result depends on the relative locations in the address space
of the objects pointed to. If two pointers to object types both point to the same object, or both point
one past the last element of the same array object, they compare equal. If the objects pointed to
are members of the same aggregate object, pointers to structure members declared later compare
greater than pointers to members declared earlier in the structure, and pointers to array elements
with larger subscript values compare greater than pointers to elements of the same array with lower
subscript values. All pointers to members of the same union object compare equal. If the expression
P points to an element of an array object and the expression Q points to the last element of the same
array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is
undefined.
I practiced this myself after seeing that error being pointed out in the comments. It doesn't even require recursion.
1) Declare a function where you will have a volatile two size array, this is done in order to invoke everything on the stack in C. Place two volatile int values with them inside of it.
2) Since you declared the array you know which one goes above and below so you can just compare the two locations of the array (&array[0] > &array[1]) which would be defined behaviour.
3) Do the return done in the video based on the difference of the two addresses and you're golden.
@@shroomer3867 - this was my first thought but with structs... but actually I don't think it would work. Since the elements always have to go in ascending order, the function would always return "up", regardless of whether the stack grows up or down.
The stack growing down doesn't mean the actual data goes backwards (or changes endianness). This would only affect whether the head or tail of the array is closer to the base of the stack.
I'm not confident that after optimizations, there's any defined behavior that accurately describes the stack direction, especially since the stack is usually just an implementation detail so the compiler is free to not use one at all.
yeah that's one thing I'm not sure about here either. My first thought was to use a static array and compare &array[0] against &array[1] but the more I think about it a compiler could just sorta decide to work backwards for arrays compared to everything else, and it could decide to do *_anything_* backwards compared to everything else, so I'm not sure there is any architecturally-constant answer here.
You can always write inline assembly where you push two values onto the stack and compare their addresses. That way, you only have to trust the compiler not to optimize your assembly (which I assume it wont do), and the assembler to correctly assemble your code.
You can also do it in only assembly as well.
@@Stormrage476 At that point, if you know which CPU architecture you're targeting, you might as well just check out the documentation and write code expecting the stack to behave in the way it's documented. In fact, I'd argue the most practical solution to this problem is just having a check at compile-time of the target architecture and compare it to a known database since that comes with no runtime overhead at all for what's effectively a compile-time constant.
@@robonator2945 Pretty sure arrays are laid out from lower to higher address, simply because the way to access them uses this assumption. C has no way of knowing to "pretend" when *(arr + i) should actually be *(arr - i) in cases of arrays because arrays frequently decay as pointers. Hence it MUST allocate them in the typical fashion.
Oh, that sounds like a nightmare. You're assuming a particular target processor, or you're writing assembly for every possible processor and using lines like #ifdef PROCESSOR_6502 to assemble the right code for the target processor. And my understanding of the problem was to do it "in C."
You can use inline assembly to see if ESP increases or decreases when you use the push instruction.
I think this is the only correct answer. In other words, "No I can't write a C program to determine the underlying architecture but I can write one in assembly".
you also need to already know the architecture to write assembly
That's putting the cart before the horse. In order to know what your stack pointer is to even reference it, you'd have to know the architecture.
Exactly
Lol if you know the machine language, you could also go to the Intel manual for x86 and see push eax pseudo code of [ESP]
it kinda hurts to see you return a boolean through an if-statement
I was explicit for the sake of the video but I understand what you’re saying :P
You mean the non-ternary approach?
Easily understandable code does add value
@@burndly But would that code change to not use the if else? Wouldnt you need the ? : operator?
Nop. You can just return the comparison. @@spacey6960
The recusive version wouldnt work either, since the compiler could perform tail call optimization.
Right, far simpler to use two functions and just disable compiler optimisations.
@@almightyhydra even then you make the assumption that the function implementation uses a stack. C does not define that. So C would need to find a way to implement this without a stack when a CPU doesn't have a stack register or the running system doesn't have that concept.
and far more explicit, but i understand, it's not good content for a video.
the compiler cannot tail call optimize as the lifetime of the argument still needs to be maintained but it could inline it, in the end the code is bad an has undefined behavior you cannot compare two unrelated pointers.
Only, if it’s actually a tail call.
In the 90's I wrote a function that could tell if a pointer was stack allocated but I solved it with inline assembly - just getting the SP register and comparing it to passed in pointer.
I actually really like that solution.
1. "int x, y = 0" only initializes 'y'. To initialize both variables, you have to write "int x=0, y=0".
2. 'Volatile' does not just mean "don't optimize", its semantics are actually quite narrow - writes and reads from volatile objects are considered as observable side effects, so the compiler has to preserve their order among themselves and relative to other I/O. Note that only actual reads and writes matter - if you allocate a 'volatile' variable, but never actually access its contents, then the compiler is allowed to remove it in its entirety. So, in your example, the 'volatile' qualifier only affects the initialization "y = 0", while 'volatile' on 'x' is literally useless.
Also, as other comments noted, even the recursive function is still not safe. Firstly, a modern compiler is able to inline even recursive functions (so that you'd have many layers spelled out at once), which would bring both locals into the same scope and allow their reordering. Secondly, even without that - since all inputs to the function are known at compile time, the compiler may just interpret it right away on its own virtual machine, which might be completely different to the host, including the stack growth direction (this is also one of the reasons why you can't do reinterpret_cast in constexpr). So, to make sure your code actually gets run on the host, and the way you wrote it, you should also disable compiler optimizations.
Both solutions invoke undefined behavior: you are not allowed to compare unrelated pointers for which is greater, only for equality. A compiler is free to optimize those comparisons to an arbitrary constant, irrespective of the stack growing direction.
LOL, we're already within UB territory with that problem statement alone (which assumes the existence of a stack), so...
@@erikkonstas Yes, but knowing it is undefined behavior and not merely implementation-defined behavior means we cannot rely on the solution even if we know there is a stack and there is nothing complicated with pointer representation, as the compiler is free to do whatever. Someone commented under the video that the result depends on optimization settings on x86_64, one of the better behaved targets. Someone else in the comments posted a better solution which, while still technically invoking undefined behavior, at least survives optimizations, as it uses volatile function pointers, and it would work reliably under a few reasonably common conditions.
@@vytah Yeah I agree, I'm saying the interviewer is asking a bit of an iffy question here.
@@noomade Here is it, by @dekutree64
volatile int *ap, *bp;
bool f1(){*ap=*bp=1; return bp>ap;}
bool(*volatile fp1)()=f1;
bool f2(){int b=0; bp=&b; return (*fp1)();}
bool(*volatile fp2)()=f2;
bool up(){int a=0; ap=&a; return (*fp2)();}
The conditions I think this relies on are 1. the stack exists 2. both return addresses and local variables are stored on that stack 3. all pointers are comparable 4. for two separate allocations, either all pointers into one are less than all pointers into the other, or greater 5. C implements pointer comparison the simplest way 6. sizeof(size_t) == sizeof(uintptr_t) 7. compiler always respects volatile for globals. Maybe few more.
@@noomade Maybe allocate an array and compare adjacent elements? Well...no, that won't work either. The compiler is free to put either varaible "above" or "below" the other.
A few questions about your final solution:
1. Shouldn’t x still still be volatile?
2. Are you worried about if the compiler decides to do some form of optimization and removes the recursive call?
3. Why not get the stack pointer and compare it to the previous stack pointer?
You cannot get the stack pointer (or anything resembling it) in C. You need to drop to assembly, which means you already know how your stack works.
@@vytah you can write inline assembly in C. Though this kinda defeats the purpose of writing it in C.
1) doesn't matter, the solution is still wrong. 2) and it's wrong because of this. 3) there's no stack pointer (or requirement for existence of stack) in C
@@shipweck6253 Not really given that the task is "impossible" in C. If the interviewer asked me such a question I would assume it's a trick question.
2:17 Security people will comment that int x, y = 0; only initializes y with 0, not x. It should be int x = 0, y = 0; One more issue is that with comma separated variable initialization, C does not specify the order that the initialization has to take place. Thus, to check the stack direction, it should be int x; int y;
@@noomade Even though in practice, most compilers initialize left-right, it is not defined as part of the C standard. E.g. if you do int x=0, y=x; you get a compiler error.
@@noomade Statements separated by semicolon are executed sequentially, thus int x=0; int y=0; is guaranteed to initialize x first. I think you are right that only declaring them by int x; int y; without initialization does not impose a specific order on the stack, it may be up to the compiler.
@@noomade There may even not be a stack, as other commenters here also discuss :) But if you assume there is a stack, and check the addresses right after a proper initialisation, I think you can be quite sure about the direction.
@@noomade To be sure, you could initialize x and y in succession with e.g. the current time as integers in nanoseconds. No way a compiler would optimize that to happen in reverse order, and it can even be checked. But I agree that without any dependency, the order is at the compilers discretion for what gives the best optimization.
I am a bit confused on the first approach? if the pointer to x is greater then y then wouldn't that mean the stack is growing down and getting more negative? Since the second value that was allocated on the stack, y, has a smaller address then x which was the first value allocated on the stack? Assuming no compiler optimizations are made.
I thought the same thing. Am I missing something obvious?
Agreed. I'm pretty sure his first example is not only incorrect, but he misspoke multiple times when talking about it.
You're right. The condition is mistakenly inverted, that is wrong. So why is the result as expected? The compiler allocated the variables in a different order than defined, or did some other optimization that fooled the logic. This is the danger of undefined behavior. Funny that the mistake masks the compiler's unexpected behavior, without the presenter's knowledge.
In any case the challenge achieved its goal, we now know quite some about him: did not verify the logic (no testing, even mentally), wrote if () return true; else return false; instead of return (); Rookie mistakes.
Not a correct solution, but a better one which gives more insight to the compiler's actions. Undefined behavior is unavoidable due to the spec, so one has to dig deep into what the compiler actually does. I ran this with godbolt (executes it only on x86 unfortunately), compilers: gcc, clang, zig cc (results are slightly different).
#include
#include
int main() {
char* a1 = (char*)alloca(30000);
char* a2 = (char*)alloca(20000);
char* a3 = (char*)alloca(10000);
char* a4 = (char*)alloca(1000);
char* a5 = (char*)alloca(100);
char* a6 = (char*)alloca(10);
printf( "&a2-&a1: %ld
", (char*)&a2-(char*)&a1 );
printf( "&a3-&a2: %ld
", (char*)&a3-(char*)&a2 );
printf( "&a6-&a3: %ld
", (char*)&a6-(char*)&a3 );
printf( "a1-&a6: %ld
", a1-(char*)&a6 );
printf( "a2-a1: %ld
", a2-a1 );
printf( "a3-a2: %ld
", a3-a2 );
printf( "a4-a3: %ld
", a4-a3 );
printf( "a5-a4: %ld
", a5-a4 );
printf( "a6-a5: %ld
", a5-a4 );
}
Seeing the stack grow with the exact size of the variables shows that the compiler did not just ignore our intent due to UB. Note: `-O1` compiler parameter keeps the original order of the variables (prints -8), `-O2` and `-O3` reverses their order. This is what happened in the video.
abs(a2-a1) == 20000 (with clang) is also a sign of the stack growing down. It would be 30000 if it grew up. That gives a redundant confirmation for the validity of the results.
@@noomade a pointer for 64-bit cpus is 8 bytes (64bit), therefore the steps in allocation are -8 -8 -8 when the pointers are allocated in the order of declaration.
-24 16 -24 means the compiler changed the order to something like a1, a3, ?, a2, a6, ? (I skipped a few, so the info is missing).
a2-a1 = 20000 means (note: I made a typo and edited the comment, it's 10k vs. 30k):
stack growing down:
[a1:30000]
Ok, I don't exactly understand how the stack is pictured here. So in the first example, if the address of y is greater than of x, then in this example it's growing down. But if the y is allocated later, then why does this mean then it's growing down (ie more negative) if the latter variable address was higher?
But if you take the recursive example it makes sense, since x is now the variable that's allocated later, because we are at the end of the recursion and "other" is the previously allocated variable (and it's now right side of the greater than sign). So this makes sense to me, and seemingly disagrees with the first example. Yet their print was the same.
This is the comment i was searching, in fact , if we suppose that x is pushed into the stack before y , then &x is greater than &y , therefore upordown() should return true.
I'm a little rusty so I may be wrong, but back when I studied assembly I noticed that some of the more common calling conventions will allocate a stack frame for a function call, and then will allocate the variables within the stack frame in the "reverse" direction. So if the stack grows down, the new stack frame is created at the bottom, and then the variables are allocated from bottom-up of that particular frame. This may be what's going on here as well.
i didnt understand a single thing you have said through this entire video. loved it 👍
I personally would allocate a small array to force the compiler to allocate on the stack.
Yeah that's seems like the simplest way to me too.
Could you explain a bit more? Why is allocating an array different from allocating an int? Why does allocating a small array guarantee that it will be allocated on the stack? What do you mean by "small" exactly? Is there a threshold that means larger arrays get allocated to the heap instead and if so what is that threshold?
@@aspzx You can't store an array in registers and an array in C must be allocated sequentially in a continuous chunk of memory otherwise pointer arithmetic doesn't work.
Small means just that I'd personally allocate maybe 100 numbers just in case but as far as I know even just 2 would be fine.
@@aspzx An int would be 32bits on 64bit machine. So, the compiler could easily put this in any available 64bit general purpose register. If you were to allocate an array of size say 8 ints 'int arr[8];' then it's not feasible to use registers to store. Regardless of size, would only go on heap if storing to an address returned with 'malloc()' and friends.
@@AlbatrossCommandoif you take an address of an object, it cannot be in register only.
Most embedded C compilers would use Registers, not the Stack for temporary variables.
Recursive probably would force it to use the stack as the compiler don't know how much space it needs.
Side note, A Contant Int would force it to store it as ram variable, if you want it to be remembered for next call.
Recursion doesn't necessarily force variables to be allocated on the stack, taking their address with & operator does (because values on registers don't have addresses)
Wouldn't constant be most likely kept in flash though? Especially for some embedded architectures.
Another way to make sure would be to create compile size array to go around registers being used. But I think volatile would stop it from happening and also calling for address of variable wouldn't make it use registers (I think).
@@anar.bastanov As return address is always store on the stack, would the test allow inline assemble? Have to make sure to use noinline for the function, and you would need to use correct asm for the platform.
uint32_t sp;
asm( "mov %%rsp, %0" : "=rm" ( sp ));
return sp;
@@sorek__ Using the keyword Constant inside a function is different. Passing an array of like 20 vars, should force the use of the stack. And that is why passing a single pointer is betters, so you don't use 20 stack push/pop's
You can just use a print statement to guarantee the use of a variable’s address cannot be optimized away, this way you get an actual automatic variable rather than a register.
I actually thought of an extra function that has a variable and returns the address of the variable to UpOrDown and UpOrDown compares it to the address of its own variable. Recursion removes the need to create an extra function but adds the need for a pointer to be passed instead.
Yeah, recursion unnecessarily confuses this IMO.
That's exactly how I approached the question:
typedef volatile int stackvar_t;
int comparestackpositions(stackvar_t *otherstackpointer) {
stackvar_t thisstackvariable;
return &thisstackvariable - otherstackpointer;
}
bool upordown(void) {
stackvar_t stackvariable;
if (comparestackpositions(&stackvariable) > 0)
return true;
return false;
}
I'd probably solve that problem using "alloca()", which allocates memory in the stack and return its as a pointer
A single call to alloca() is not enough. It will return you a pointer to (allegedly) data on stack, yes. But then you need to compare it to another pointer allocated on the same stack. And this is where no guarantees are provided by the language about the order in which multiple alloca()'s or any other local allocations will happen.
@@GrigoryRechistovmaking second alloca conditional based on the first would guarantee the order
int *first, *second;
first=alloca(1);
if (first) second=alloca(1);
return first>second;
I think it'd be slow in comparison
I doubt the speed is all that much of a factor here. @@rb1471
@@Henrix1998 alloca() never returns NULL, so in this case the conditional may be optimized away as always true. Then the allocations may be reversed.
Some compiler options optimize out using multiple stack frames for recursion, if possible
Probably the compiler doesn't have rights to optimize this case because recursive call depends on values below the call
@@ic6406 There's no dependency on values below the call. `return upordown(&x)` can be easily tail-call-optimized into a simple jump because there is no additional work to do after the call returns and the return value of the callee is our return value.
For those wondering whether it is possible to have a C program run without a stack, I have an example for you. Early x86 firmware boot code has to run for some time *without any RAM all*. That is, no memory for either stack nor for heap. Program's code is read from read-only flash. That is because the memory controller device has not yet been properly programmed. The first thing the firmware might want to do it to make RAM available. But until that moment, one has to deal with lack of memory.
One early solution to this was to have a C compiler to produce programs that allocate everything on processor's registers. Needless to say, maximum stack depth is very limited in this situation.
But it does not mean you cannot have a standard-compliant compiler for such environment. You might not be able to use recursion at all, but that is because undefined behavior of exhausting implementation-defined recursion limit will kill it early. Which is standard-compliant behavior.
For those curious if we still have to use such trick of allocating everything on registers today, then the answer is no. Firmware writers have learned to use CPU's caches as substitute for RAM in early boot. Caches require no configuration to become usable and provide several megabytes of addressable storage, which is much better than half a dozen of 4-byte registers.
2:50 the return is inverted. The compiler is also doing the opposite of what you expect it to do: `-O2` and `-O3` optimization reverses the order of the local variables.
Thus the result is double wrong, which in boolean logic ends up being right 😄
Also, simply `return &x < &y` will do. `return true; else return false;` is also a telling sign for the interviewer.
I'm pretty sure comparing pointers in this way is undefined behavior
Assuming there's a stack is also UB, so that's no "excuse" here 😂
I tried both local variables, volatile or otherwise, and with recursion, and they both had the same results. Normal compilations reported downward growth, but optimized compilations reported upward growth. Something to keep in mind.
This means that the either program's result is unspecified or undefined. Compiler optimization level or compiler choice should not affect outcomes of well-defined C programs. Ergo, this program is not well-defined (see other messages in the comments from many commentators what assumptions are wrong)
@@GrigoryRechistovit's the pointer comparison: comparing which of two unrelated pointers is greater is undefined behavior.
@@vytah True. Only pointers that refer to insides of the same array or struct/union may be compared, otherwise the C standard (6.5.8p5) explicitly marks the result as undefined behavior.
@@GrigoryRechistovone past the container is also still fine.
@ Agree. I always liked this "oh, we have this off-by one problem. All right, let's allow it everywhere"
This is exactly my thought process when you asked the question
- compare two variables addresses off the stack
- but what if the compiler mucks with their order?
- move the variables into function arguments,
- but what if the compuler reverses function arguments?
- use a function call to force a call frame onto the stack and compare addresses across the call frame
alloca...easy solution
@@noomade prove it, don't be lame.
@@gregorymorse8423 alloca isn't standard C. It's not even in POSIX.
My first thought was to create a struct with two variables, initialize an instance and compare the pointers of the variables, as structs are required to keep their order.
Yes but that will answer about how structs are stored in memory, not how stack allocations are made. There is a difference, and the orders may be different.
@@GrigoryRechistov How the order can be different?
@@matthewrossee Easily. The compiler is allowed to put them in any order or optimize them away. "volatile" will help with the latter but not with the former.
@@GrigoryRechistov ok that makes sense. What do you mean by optimizing them? From what I understand, the compiler can’t inline the values because then how could you take the address of these variables?
@@matthewrossee It cannot inline values of variables but it can values of addresses of variables inline (or make other conclusions like being NULL or non-NULL). Note that the code in the example does not dereference pointers in question, it only operates on addresses themselves.
I have a strong feeling that in the situation where i would need to know the direction of the stack there should be much better and reliable way to do it.
I was thinking in the same direction of multiple function stack frames.
I was thinking of 2 functions:
1 basic upordown() function with no parameters which returns enum UP or DOWN. This upordown would simply call with the address of a variable in upordown another function checkIfStackIncreasesUp(int *reference_address) which returns bool by comparing the parameter received address with some internal variable's address. No recursion is needed :)
Probably better to not name it upordown because it's returning a bool. I'm legit inclined to name it doesStackGrowUp... And I've never used does in a function name before. lol
Your teammates should ideally not have to read the code of the function to understand what it's doing.
And comments are not an adequate substitute for good naming.
Use `___attribute___ ((noinline))` to avoid inlining. No need for recursion. Alternatively `clang -O0` disables optimizations like inlining.
@@Leto2ndAtreides Yeah, the name was not really catchy. I thought about isUpOrNo() would get more interest.
1. You don't need recursion, can have two functions, one calling the other. 2 You forgot about inlining functions, recursion unroll, register argument passing.
Isn't the logic of the first upordown function wrong? If x adress is greater than y address then the stack is decreasing
His first implementation gave the correct result.
What does the function actually return? Is it "true" for up or down?
Of course, comparing to pointers not pointing into the same object or array for anything but (in)equality is undefined behaviour, and the compiler is allowed to do whatever it wants in that case. So in theory the program could output "nice try" instead. So the first assumption is that the optimizer does not take advantage of that undefined behaviour.
You didn't need to write a recursive function like that.
Since all you care about are addresses, and you have no intention of dereferencing them, you can take the address of a variable on the stack in one function, and return that, as a pointer, to the calling function.
Then compare that address to the address of a variable in the current function.
Cursed but I kinda like it
This is the initial version I wrote, thanks for confirming it's valid
This is how I thought to solve it. Recusion works, but his function does two completely different behaviours based on arguments, which to me screams the need for a distinct separation of the methods, one to return the pointer for a variable on the stack, and another to call it and compare addresses.
int main (int a, char *b[]) { puts (b > *b ? "UP" : "DOWN"); return 0; }
or, if system is freestanding:
void main (void) { char *a = alloca (1+(int) &main % 5), *b = alloca (1+(int) &main % 5); puts (a < b ? "UP" : "DOWN"); }
I think i would ve used alloca() which allocates memory in the stack frame and compared the first and last element's address but your recursion based answer seems more platform proof.
Why alloca instead of an array ?
@@4zv4l38I think you need to alloca() twice in sequence and compare their memories. If you use an array and compare its end and beginning, I think it should always show that last-first is positive (because that's the direction an array is oriented in).
@@dobacetr you are right otherwise indexing wouldn't work. I didn't think of that thank you !
@@4zv4l38 i might be wrong ( and probably am) but i feel like alloca would always allocate memory in the stack whereas variables and local arrays might be put into register without the volatile keyword also it's just another use case of alloca
The man page i have on alloca can be summarised as "alloca does something, and probably returns valid and unused stack memory in the process"
I would only trust alloca when you know everything about the system. The whole purpose of this code is that you don't, so i doubt this is reliable
2:53 "if x is growing up, its getting more positive, but if x is grown down its getting more negative"
then the if statement should be
if (&x > &y) return false; //because the variable y has a lower address, which means it went down
also in the recursion code this logic is flipped
also if you google "recursion" to check its spelling like a normal person, google will have you stuck in an infinite loop smh
Good video. My only issue is with a boolean function being called upordown. It makes the code read as "Is the stack growing up or down? Yes/No." and does not imply directionality which is the real question we're asking. Something like isGrowingUp() or isGrowingDown() would be better.
i dont think it "can't get optimised out because we're using recursion"
volatile does permit the compiler to make optimisations, it's there for hardware the CPU isn't controlling.
the compiler just isn't allowed to assume the value won't change on it's own. other optimisations may happen.
there is __attribute__((optnone)) which might suit your use case better.
i also think the use of recursion makes the example more complicated than it needs to be. it seems like the condition is the wrong way around (it returns true if the address from the older stack frame is greater. ie, "up" when it's going down.)
I think your second/recursive solution can be incorrect due to tail recursion optimizations (reusing the same stack frame when recursing!)
That being said, I’m no expert, so I may be wrong
The issue is, an address to a local variable was passed to the called function- destroying the stack would also destroy the reference.
The reference itself is not destroyed, just the memory it points to is no longer "reserved". However, pleaee note that the code does not use a reference to a destroyed variable. The second recursive run determines the result, where the first instance of the variable (whose address is in the argument) is still exists. The second run returns the boolean outcome, not the address of its local variable which is going to be destroyed. So theoretically it is not an use-after-free error.
Regardless of this, while the question itself is interesting, there is no way to write this program with 100% certainity that it will work in a defined way on all architectures.
If you look at the C11 reference for relational operators, section 6.5.8, this pointer comparison invokes undefined behavior since the variables aren't part of the same array or struct. So, a compiler would be allowed to optimize your function to lie about which way the stack grows. I'm not sure if any compilers actually do optimize this comparison.
Plot twist: there is no concept of stack (nor heap) in C standard.
Indeed it's an operating system and/or hardware implementation. The compiler conforms to that.
There is also no concept of memory addresses in C. The numerical value of a pointer could be anything, as long as it can be dereferenced back to the original variable.
Pointer arithmetic and comparison operations are guaranteed to work, though.
@@MrEdrftgyuji Pointer arithmetic and comparisons are not always guaranteed to wwork. As a rule of thumb, if you compare two pointers that aren't identical and don't point within the same array, the result is undefined behaviour.
As you asked the question, my first answer was to have two functions A() and B(). Where B returns the address of a stack variable and A returns if that is bigger than its own stack variable address.
Two functions, but less code.
Still haven't watched past 45 seconds, but main() is a function, so only one more function is needed.
@@TranscendentBentrue - but I - and the video - kinda assumed you'd want a function.
Actually, I'd also add a comment
/* Compile with -O0 */
Wouldn't that break if the compiler decides to do tail call optimisation?
tail call is impossible in that case, or, rather, even if possible you should assume there is no tail call for that case, see david wragg c tail calls 2014
@@AnataBakkaso basically if the behavior is well defined without TCO but breaks if TCO is applied then it isn’t applied.
This of course assumes the program is well defined which it would be as long as long as the pointers are casted before comparing them
@@natnial1 Yeah, that "well defined" part is where it all breaks; TCO does not "break" anything in regards to well-defined behavior, but here we actually want to tame UB.
A missing part of this is "compile without optimisation". Assuming that the computer won't, or can't, optimise a recursive function, is risky.
You could make it impossible to optimise.
A random finish condition would do.
As in recursively sum a random number of random numbers.
You don't really need recursion there.
You can make 1 function that returns the address of a volatile local variable as a usize_t (to not confuse people to dereference the invalid pointer/address)
And then make the actual upordown function that compares the result of the other function to its volatile local variable.
size_t nextStackframeAdrr() {
volatile int x = 0;
return (usize_t) &x;
}
bool upordown() {
volatile int x = 0;
volatile size_t addr = nextStackframeAddr();
volatile size_t addr2 = (size_t) &x;
return addr2 < addr;
}
does volatile enforce the order of operations too? from what I know, there is still nothing preventing the compiler from re-ordering things like variable declarations
@@pwii no. And I'm not sure if this code works korrekt in all cases. But it should work in all cases his version works.
@@pwii Indeed. You have to turn off optimizations to get it to work, and if you do, you have no need for the volatile keyword anyway.
usize_t is not a predefined or library type. There is size_t which is unsigned, and ssize_t which is signed.
@@var67 thanks I wasn't sure which way around it was. I usually code in rust where it's size and usize
Love your videos. I like to think I’m a semi-competent C hacker on a good day, but it’s amazing how much I’ve forgotten or don’t consciously think about regularly since college.
Haha, fun stuff. This was my one of my interview questions at Microsoft when I tried to intern there. I had limited to no knowledge about OS architecture. It wasn't even the position I was going for. Anyway, I failed it.
My initial answer was create 2 variables and compare the address as you've said but it wasn't enough as they can be randomly allocated or as you said optimized.
Create 2 functions and creating a variable inside each would be good as they get a full row of memory.
Also, it can avoid any complexion like recursion.
Still this question hunts me to this date. haha was over 6 years ago. Luck is a big factor in life. Knowledge is what brings that luck closer to us !~
Keep up the good stuff, interesting videos.
It's not just that they may be reordered. It's also that comparing pointers not part of the same array is undefined behavior.
You could get back anything. You could get back that x is above y AND y is above x, because with undefined behavior logic does not apply.
How about using inline assembly? Save rsp at local variable in inline frame #1, allocate some new local variables, then check the changed rsp value at inline frame #2.
Of course, the local variable should have storage class auto, since static class will make the assembler save variable in other space.
With this problem, the architecture itself is in question, and every ISA is different...
Great video! However I did find something I found interesting when trying to compile both of these solutions... I compiled a program with both of your solutions using gcc 11.4.0 and clang 14.0.0, For your first solution gcc gives Down while clang gives Up... For your second solution both compilers return Down. Edit: I am using pop-os 6.5.6 if anyone else wants to verify this
Feels pretty good that my initial instinct was "don't assume the compiler's ordering of local variables, force the creation of a new stackframe to grab a pointer we know has to be deeper in the stack" was completely correct
Nah, it's hard to force an optimizing compiler to do almost anything. :) See many other responses for why even the recursive solution doesn't work.
please make videos on volatile, __attribute__ and ## in C
those are completely different things. here is a short explanation of two of them:
volatile basically tells the compiler to not optimize whatever you've marked as volatile. I recommend messing around with it in godbolt.
## is some sort of an operator used in the CPP (C Preprocessor) that joins two tokens together, so imagine this:
#define JOIN(a, b) a##b
then `JOIN(hello,World)` would produce the token `helloWorld`.
@@arta6183 thanks for info😀 .. i just wanted to know how those features work under the hood...So i suggested separate videos on them
It's been almost two decades since I've done programming like this. I ended up over-engineering it to allow the function to be called without any parameters. My brain switched the question to "write a function" rather than "write a program" and I didn't want users of my function to have to pass in NULL or anything else. Other than that, the solution was pretty much the same. Cool question!
You mention that some architectures have the stack grow +/- differently. Why is this? Why wouldn’t the architectures be consistent with this concept?
Because they can? architectures are imcompatible with each other, why would they follow the same rules?
@@minirop good point. Just curious. I am sure there are some things different architectures can’t do differently. I guess I am wondering why the his isn’t one of them.
Cars can drive on either side of the road, but it doesn't matter WHICH side as long as everyone agrees. In a similar way, a computing architecture can grow its stacks "up" or "down", as long as it sticks with one or the other. Stack growth is invisible to 99% of programmers anyway.
*Angry comment about function name not being something like StackIsGrowingUp, instead of upordown as it does not indicate that it is returning a bool*
4:19 My guess is an array because it is a contiguous chunk of memory and index 0 is always addressed before index 1.
Edit: Aw, I think my method works tho, and from reading comments looks like it works better.
I love it! I would try to use inline asm and compare esp but recursion is honestly much better
alloca is much better and uses no function calls
Wait, does up mean that x is stored at the address (base of the stack) + (some number)? If so wouldn't y be at &x + 1? So if the stack grows up wouldn't &x < &y?
My first idea wad using functions and checking a variable in their scope against eachother, however i didn't think about using recursion and i guess using recursion also eliminates (?) The possibility of the compiler inlining the function and breaking that logic
On my machine, I get a different result with -O3 because gcc removes recursive call, so...
at the start you said "job interview" but it sounded too similar to "java interview" so I mishead it
and then you mentioned C, and I was like wtf
The use of recursion is unncessarily complicated. You only ever recurse one layer deep - just use a helper function.
Yeah, it's also confusing and makes the API worse since you have to pass in NULL to the call for no reason.
I think he did it to prevent a compiler optimization that just moves the function body of the helper function to its only call, therefore creating a similar situation as before, where the compiler can change the order of the variable declarations.
@@dennismuller1141 Hm, that kinda makes sense. Though I also wouldn't be surprised if the compiler could optimize the recursive call the same way. Tbh in general, I'm not sure there's anything stoping the compiler from optimizing this whole concept into whichever direction it wants, since stack direction doesn't seem to be something that's guaranteed by the spec.
@@dennismuller1141 You make a fair point. Compilers are free to inline functions like you describe.
But I don't think the recursive solution is exempt from this. Compilers are pretty smart these days. They are free to "unroll" recursive calls as well as optimize away unreachable branches. So in the end, the same problem arises.
The better approach would be to use some compiler annotation, such ass GCC's "noinline" annotation, to prevent such a compiler optimization.
I'd just write a few lines of c, compile with the S option, open gdb, and look at the assembly code. Then, the interviewer would know I knew C, assembly, and how to use a debugger other than printf().😂😂
Can't you also compare the address of main with the address of the upordown function?
You can't because the functions' code doesn't live in the stack but in the exact opposite side of memory (at least in x86), in the text segment. Only local variables and some other internal values (return address, last frame pointer) get placed in the stack.
I don't think that'd work, because the addresses of functions don't point to the stack at all.
The address of the functions won't be in any guaranteed order, but presuming you mean the address of a variable in main vs one in the upordown function, I believe he was trying to avoid the case where the compiler optimises out the call being made and therefore making the comparison not work as intended.
@@Elesario Oh, that would make more sense. That's actually a very good idea then.
Just an excerpt: "The key thing to understand about the 8 bit PIC architecture is that the stack size is fixed. It varies from a depth of 2 for the really low end devices to 31 for the high end 8 bit devices. The most popular parts (such as the 16F877) have a stack size of 8."
^^and they do have C compilers. So there are totally devices with limited hardware stack sizes actually - otherwise its fun little excercise I agree, just sayin' 🙂
Upordown is a bad function name IMO. Expected behavior for me would be it nearly always returns true, unless the stack grows horizontally, or non linearly.
I think these are better:
bool stackGrowsUp
bool isGrowingUp
I write almost no C or C++ and this was super fascinating. One of my favorite tech videos in a long, long time. Thank you helping me continually learn every day!
Wow, thanks for the video! The first implementation is the one that I had in my head. The only twist I could think of is that the function could be inlined, but that shouldn't affect anything.
I'm slightly confused with the stack example shown in the commented code block. In my head a stack is adding to the top, so y would be higher than x.
Is it because the 'top' of the stack is actually the stack pointer. so when y is getting added "below" x, it's actually getting added to the "top" of the stack ,since that is where the stack pointer would be?
You could also just do
volatile int x =0;
int y=x+1;
[rest of the first function]
The optimizer cannot change the order since y is dependent on x and x might change between the lines.
The first thing I thought of was to compare rsp and rbp,
For example:
format ELF64 executable
SYS_write equ 1
SYS_exit equ 60
STDOUT equ 1
segment readable executable
entry _start
_start:
cmp rbp, rsp
jle down
; up
mov rsi, up_msg
mov rdx, up_len
jmp write
down:
mov rsi, down_msg
mov rdx, down_len
write:
mov rax, SYS_write
mov rdi, STDOUT
syscall
; exit
mov rax, SYS_exit
mov rdi, 0
syscall
segment readable writable
up_msg db "Up", 10, 0
up_len = $ - up_msg
down_msg db "Down", 10, 0
down_len = $ - down_msg
You could use this by making an assembly function, and linking to it.
Ok but if you're writing in assembly you're typically targeting a particular architecture anyway
You have to do it in C, not in assembly.
The syntax "if ([cond]) return true; else return false;" terrifies me. Just do "return [cond];".
Thanks!
I’m confused. If a stack grows ”up” (i.e the stack pointer increments on an add), then (&x > &y) is False, because y was added after x and hence has a larger address, right? But you say that ”x is on top, x is more negative”, which makes no sense to me unless x is allocated after y and we are assuming a decrementing stack pointer. Does ”int x, y = 0;” not add x to the stack before y?
Bro I'm so confused, It's the opposite.
It frustrates me to no end that the names are so close together in intuitive meaning that I always forget the difference. A stack of paper is also a heap of paper. Especially annoying that when learning to code stacks, aka first in last out, I'm taught to think of it as stacking napkins up.
Not really to be fair, a heap of paper would be like if the sheets are thrown at random everywhere on the table, not ina neat pile. A face-down pile of sheets of paper is a stack, not a heap.
For me a heap of paper would be a bunch of paper sheets lying on the floor, all in different orientations and no discernible order. A stack on the other hand is all the papers neatly put together and you can clearly go from top to bottom.
In that sense, yes, a stack is also a (ordered) heap, but a heap is not necessarily a stack
As far as I understand the C specification, comparing pointers in this way is undefined behavior, as already explained in other comments. The danger is that such an undefined behavior will probably often work, which makes it hard to discover the problem by testing. One of the most important C skills is to navigate around these undefined behaviors. Therefore, this answer to the interviewer's question arguably shows that, although the interviewee knows things, they more importantly feel too confident writing potentially dangerous code.
An idea i had in order to solve this was using inner scopes (i.e `int x; { int y; }`) in order to force the inner variable to be after the outer, but i'm not 100% sure that actually happens
scopes in c don't allocate new stack frames
@@veritas7010I think that's the point. You just need to ensure that variables are allocated in order. Hopefully, x is allocated before entering the scope and y is allocated in the scope such that &y-&x is always the direction of the stack.
Very cool stuff. I haven't touched C in about 10 years since I moved on to Python/JS/Web and I'm glad to know I could've gotten almost 80% of that in an actual interview, assuming I knew it was a C interview and had time to do a quick refresher, I owe it all to my CS101 teacher back in high school.
please name the function is_up if it's going to return true when up for christ sake
I'd use the first method mentioned in the video but mark the function as "__attribute__((optimize("O0")))"_ (I hope UA-cam doesn't mangle this). Many compilers have the option to _sometimes_ ignore volatile keyword in order to aggressively optimize all loops, allocations, and invocations using something like -O3. The _only_ way to prevent this is to mark the function as no-optimize.
Also and importantly, I'd start my answer off with "assuming the architecture I'm on uses a stack."
It's totally okay to point out assertions like that and let the interviewer press you on it. The important bit is that you point it out, not that you solve every tiny angle of the problem.
Another assumption is that comparison of unrelated pointers is reliable, as it's comparison which is the undefined behaviour here.
My immediate idea was to use alloca()
Technically not a standard function, but the 3 only compilers that exist support it.
Me too! Unlike the C standard, the man page for alloca at least mentions the stack, so we have a better chance of getting the answer we expect. :)
@@noomade Well, a stack must exist if the documentation of alloca says that it "allocates size bytes of space in the stack frame of the caller." If it did anything else, I would say the documentation is wrong.
You might be right that an aggressive enough compiler might decide to optimize it away, because by most definitions this is not observable behavior.
@@noomadeI did read his posts and I agree with them. Thanks for pointing them out.
Correct me here but if top is greater than bottom then isnt it growing downwards.
If the location of the succeeding address is lesser than the preceding address isnt it growing downwards?
I think you have errors in your code and a number of incorrect/inaccurate statements in your verbalization.
1: The stack pointer isn't growing "more negative" it's growing "less positive."
2: Your first method returns the wrong value. Note you return First-Variabe>Second-Variable but in the recursion method it's reversed.
3: @2:55 you mention X growing. X isn't growing. Neither is it's pointer. You mean if the difference between &X and &Y is growing.
4: @4:14 you say method one isn't the most efficient. The problem with method-one isn't efficiency, it's that it could be wrong. Big difference.
I like this question a lot. I'm not a C developer, so my first idea was that it would be way out of reach. But then I realized that I could write some pseudo-code. I didn't realize I could just use the addresses of local variables, so my pseudo code used some mysterious method to get the stack pointer. But I was using two separate functions, similar to your recursion (but in my opinion, more appropriate here than recursion, for readability reasons).
The amount of reasoning you can do about this even if you don't have the full answer shows how well this question works!
hai
rawr
Volatile won’t help here. Volatile means the compiler needs to assume every access to a variable has side effects, so will be very constrained if it wants to rearrange accesses, but has no effect on the location of variables in a stack frame. In any case, the order of variables in a frame (controlled by the compiler) has nothing to do with the order of frames on the stack (controlled by whether the processor stack grows up or down), so your first solution was pretty fundamentally flawed.
Yeah I've watched it over and over and when you said "x is on top, x is more negative" I'm pretty sure you misspoke. Y is the most recent variable, ie "y is on top" and "x > y" means "x is more positive"
I feel this would be better explained with the assembly listing and a memory view open. The stack could be initialized in different ways, also without the recursion there is pretty much no guarantee that it will grow the stack in any direction. The only correction I would make for intel is to say that the compiled code will use base pointer register offsets (EBP), and not the stack pointer directly, so between call frames there will be some stack preservation wrapper copying to and from EBP/ESP.
2:16 This still leaves x undefined. But I like to think he was memeing us
Instead of recursion, can't we declare top scope variable and declaring an aditional block creating the second variable?
File-scope (aka. global) variables are usually not allocated on the stack. Those end up in the BSS or IBSS segment of a linked executable and it is going to be allocated directly on heap.
The cause is that their size and existence is know at compile time, thus, this can be done because it is more efficient. The init code that runs before the main() zeroes out everithing or copies the initial values in a for loop.
Local non-static variables are allocated on the stack, because it cannot be known at compile time how many of them will exist (same func called multiple times) even exist at all (never called).
Yay, I'm a non-C programmer who not only knew the first naive approach, but thought about how the compiler could possibly optimize it and ruin things. Didn't quite figure out a solution before I hit play, but I'm still just happy I was on the right track :)
There is no solution in portable C, because the C standard does not have "stack".
In some OSes, there is no dedicated stack area but instead stack space is allocated in chunks from the normal memory manager. Therefore, the stack can jump back and forth in memory as it grows.
Not sure if my logic holds, but when you asked the question of a different approach to x,y my first thought was to make a local variable with an array size 2. Then compare element 0 to 1 in terms of address. My assumption is that the compiler would not mix the order of array elements, as part of the definition of an array is it is a serial length of memory.
But I don't know specifically how array are allocated on the stack, it very well could be that the first element is stack positionally placed, but then the contained elements are serially placed.
The problem with this is that ((a + 1) - a) is always 1, it doesn't tell you anything.
I didn’t understand the question so I listened to the video and I can categorically state that I now understand it even less.
I assume x is the first variable being allocated in the stack.
If the adress of x is superior to y, then the second variable (y) would have been allocated "under" the first, thus growing down.
The code does not reflect this, but the opposite. Anybody care to explain?
On some architectures the result can be non deterministic if called within the context of a larger more complex program ... in at least some implementations of ARM procedure call standards I was familiar with many years ago, stack frames are allocated on the heap as required, so if the inner function call uses the same allocation, the result would be as expected, but if it allocates a new frame on the heap, the result could be either direction.
this doesnt make sense to me to, in the first one the stack would look sth like
0 x
+1 y
in the second one wouldnt it be
0 other
+1 x
since other comes first, so why are we saying x > other when we in the first one we initially said x > y, can someone explain it to me
What's curious is that the equivalent impl in Rust (the recursive one), produces opposite results depending on whether you build in debug or release mode. I don't know why.
Here's my very crude impl, in case anyone is curious:
fn main() {
dbg!(stack_grows_up(None));
}
fn stack_grows_up(other: Option) -> bool {
let x = 0;
let addr = &x as *const i32;
match other {
None => stack_grows_up(Some(addr)),
Some(other_addr) => other_addr < addr,
}
}
It’s definitely based on some optimization, because adding a dbg! Of the addr in the Some branch causes it to produce the opposite value. I’m guessing it’s a tail recursion optimization but who knows
One thing thats crucial to mention is using -O0 when compiling. At -O3 the compiler can easily just return true or false since both are valid and comparing pointers is sensitive to inlining.
Comparing pointers like this in C is actually undefined behaviour (i.e. meaningless), not just sensitive. At -O0 the compiler would still be valid to produce code that prints up, down, segfaults, or anything else.
I agree it is an interesting question, to see what the interviewee knows.
For example, I haven't used C in a long time and (once managed to set aside the "why do we care")
I would have guessed the initial solution, and admitted that would be a guess.
The then following explanation on, what is considered "common-knowledge" on the abilities or lack thereof of compilers.
Is indeed something I would not have been able to contribute to.
"Making assumptions on how the compiler treats effects triggered by a single command" (the 2 initializations) was easy to spot as
"If the compiler breaks the plan. It would likely do so here".
To which my first thought was:
- initialize/assign
- read address
- initialize/assign
- read address
Might solve it, if we want to be more sure, we probably could:
initialize/assign y, with the value of... the address of x.
As this information needs to exist, the compiler would have even less room to outsmart the programmer.
That C-compilers have a "magical, can't optimize beyond this"-border around recursion. Is not something I knew.
(Again, making it a good question.)
One of my ideas was to check argument's address with local variable's address, there's huge chance that arguments pushes first before locals are allocated.
The second you said recursion it all made sense. Super cool question.