a strange but powerful interview question
Вставка
- Опубліковано 20 січ 2024
- Which way does the stack grow? What even IS a stack? In this video I'll talk about an interview question that still haunts me to this day.
🏫 COURSES 🏫 Learn to code in C at lowlevel.academy
📰 NEWSLETTER 📰 Sign up for our newsletter at mailchi.mp/lowlevel/the-low-down
🛒 GREAT BOOKS FOR THE LOWEST LEVEL🛒
Blue Fox: Arm Assembly Internals and Reverse Engineering: amzn.to/4394t87
Practical Reverse Engineering: x86, x64, ARM, Windows Kernel, Reversing Tools, and Obfuscation : amzn.to/3C1z4sk
Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software : amzn.to/3C1daFy
The Ghidra Book: The Definitive Guide: amzn.to/3WC2Vkg
🔥🔥🔥 SOCIALS 🔥🔥🔥
Low Level Merch!: lowlevel.store/
Follow me on Twitter: / lowleveltweets
Follow me on Twitch: / lowlevellearning
Join me on Discord!: / discord - Наука та технологія
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 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.
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
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.
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]
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."
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.
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.
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
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 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.
@@00jknight LOL, I thought I was going mad... now i am totally confused because of course you could be the one that is wrong since you agree with a noob like me :P
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.
@@Gregorius421 can you write a correct solution (as in one that you would write if you were FORCED to write SOMETHING in an interview)
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.
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?
@@aspuzling 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.
@@aspuzling 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.
@@zaper2904if you take an address of an object, it cannot be in register only.
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.
@@vytah where is that better solution?
@@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.
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.
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.
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.
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.
my favourite video of yours in a while, really liked this one
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;
still no guarantee that x is initialized first though right??
@@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.
@@henriksundt7148 Hmm. I am sceptical that you can guarantee that the compiler will not do something funny with the ordering of your code when it optimizes it.
It would seem that even WITH initialization you cannot guarantee the order of your code... at least according to some c experts on here that refer to the docs etc.
@@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.
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.
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.
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 loved this solution. Thanks. I am new to C but your channel has helped me step up by several orders of magnitude. You make the topic very interesting.
Isn't the logic of the first upordown function wrong? If x adress is greater than y address then the stack is decreasing
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.
Fascinating question I had not thought about before. Fantastic & concise explanation with great code example. Subscribed!
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.
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 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
The second you said recursion it all made sense. Super cool question.
The recursive solution is very clever! I hadn't considered compiler optimization. Thanks for sharing!
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.
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 didnt understand a single thing you have said through this entire video. loved it 👍
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
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
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"
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!
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.
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.
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.
Yes, this an interesting one, because (other than knowing what a stack is), the main issue is really the "fighting" against compiler optimizations, hence knowing about "volatile" etc... becomes important.
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"); }
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.
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...
That was a great exercise. Thanks!
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.
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.
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
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.
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.
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
Neat trick! Thanks for sharing!
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' 🙂
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.
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.
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...
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().😂😂
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
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.
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.
i like this. very well-explained.
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.
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.
Simply brilliant
My immediate idea was to use alloca()
Technically not a standard function, but the 3 only compilers that exist support it.
but some people on here have said that alloca() cannot be guaranteed to give the correct answer.
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. :)
@@alonamaloh IFF a stack exists right? and even then you can't guarantee that your alloca() does not get optimized away
@@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.
@@alonamaloh I think you should read Grigory Rechistov's posts under this video. He gives compelling arguments as to why alloca is neither a stable nor a guaranteed to be correct solution to this answer (and why no c program can be guaranteed to give the correct answer). He has posts in a few threads with his reasoning.
The syntax "if ([cond]) return true; else return false;" terrifies me. Just do "return [cond];".
Thanks!
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
@@gregorymorse8423 but also wrong apparently!
@@noomade prove it, don't be lame.
@@gregorymorse8423 huh? are you r-worded? There are like 20 posts under this video explaining why alloca() cannot be guaranteed to give you the correct answer. You clown 🤡
@@gregorymorse8423 alloca isn't standard C. It's not even in POSIX.
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
hai
rawr
please name the function is_up if it's going to return true when up for christ sake
Very cool demonstration
Great content!
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!
The best answer on here is the one that explains why this cant be done with any guarantees ( by Grigor)
Man thats really great Q for an interview.
my first thought was to create a function that takes in an int, returns a pointer to that, then in main create an int and 2 pointers to ints, set the first pointer to the int in main and set the second pointer to the result of theFunctionThatReturnsThePointerOfItsLocal(a) and then compare the 2
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).
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!
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.
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 jumped to recursion as my approach when you first posed the question so I'm putting C on my CV now!
but the C experts in the comments are saying that the recursive approach offers no guarantee either... and that even those that have gone a step further and used alloca() are also wrong :(
Languages: -C programming language-
IIRC popular c compiler like clang and gcc also have tail-call optimization, which can turn this kind of recursion into loop, which I believe can also break like int x, y hack? Disabling inlining might work?
It's funny that my initial solutioun was to use recursion and I had a total "duhdoy" moment when you mentioned just initializing two variables lol
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.
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.
Great video !
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.
Nice approach! I firstly figured using global variable that points local variable of main. Then in function upordown, compare its local variable's address with that global one.
I think this wouldn't reliably work because program globals are held in a read-write portion of where the code is loaded, independant from the stack. So what this would actually do is compare to see if the code is loaded above or below the stack.
I would've thought they were asking about the stack trace, so I would've written a function that throws and catches an exception then counts and returns the number of lines in the stack trace, a function that calls that function and returns the number that got returned to it, and then a function that calls both functions and compares the values.
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?
There is more to that. To account for the inlining and constant propagation you may need to let the number of recursion be dependent on a parameter that the compiler cannot evaluate at compile time, moreover optimization of C allows the compiler to do whatever they want with the pointer comparison, and since the variable are otherwise unused there is no guarantee that an aggressive optimization will not invent whatever result they want for your function. I would probably also use the pointer passed recursively to actually compute something that can't be optimized away (for example, you can keep a running total. I would also if possible rely on some syscall to make sure that the input of the recursive function cannot be guessed at compile time (i.e. using fopen to attempt reading a file) and to use the result of the computation so that it is not discarded and optimized.
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.