Interview question !!!

[Mark McIntyre]

I think Seebs might have a problem with that.

Heck, roose could offer to help moderate it couldn't he?
=:-0

 

[Kelsey Bjarnason]

I wish *I* had thought of that. But still, the answer I gave in that
other thread was also a good one, right? Right? RIGHT?

Didn't see your answer... but his isn't a good one. It says "so that
_main_ should print something other than 20"; this "solution" doesn't meet
the requirements. main still prints 20; it's simply added onto the end of
other, unrelated output.

 

[Peter \Firefly\ Lund]

void fn(void)
{
/* add your code here so that main should print something
* other than 20
*/

#define printf(a,b) puts("7")

}

int main(void)
{
int i = 20;
fn();
printf("%d\n", i);
return 0;
}

-Peter

 

[Noah Roberts]

BTW, I'm only replying to ensure that anyone else reading this thread
will see that you are spouting rubbish.

Totally unnecissary. I think everyone here can see plainly that Roose
is choking to death on his own dung.

 

[Noah Roberts]

Ever heard of registers? A
*lot* of good compilers will store automatic variables in registers
where possible rather than on the stack.

Not to say that Roose is right (I can't even know everything he said as
I killfiled him already), but in the case when a stack is used in
function calls, wouldn't these registers again be saved on the stack in
preparation for the call to f()? I suppose a brilliant compiler would
know that rA (for example) is not going to be changed by the call to f()
but are compilers this smart? And at that point couldn't a knowledgable
programmer, someone who knows the inner workings of the compiler in
question, force the matter anyway? Or, if 'i' is located in a register,
use inline asm to alter that register.

Like I said before, requires a lot of knowledge about a particular
processor/environment/compiler and is entirely non-portable, but I think
it is probably always 'possible'. However, anyone stupid enough to code
like this should be fired immediately.

 

[Chris Torek]

... but in the case when a stack is used in function calls, wouldn't
these registers again be saved on the stack in preparation for the
call to f()?

Maybe; maybe not.

The example machine I used (the Pyramid, with its two stacks)
stores registers in one stack and "ordinary stack data" in the
other. So registers *are* saved on "the" stack -- it is just
the *wrong* stack.

Moreover, this was one of the early "register window" machines,
comparable to SPARCs today (the Pyramid probably came directly out
of Dave Patterson's SOAR group at Berkeley though, i.e., parallel
development to the SPARC). These machines do not actually move
the registers out of the CPU, into memory, until necessary. A
process switch (or even an interrupt) will force a register window
spill, as will a sufficient depth in the call stack or an explicit
register window flush operation. Until then, however, the register's
value has not been copied to its memory slot -- the only copy of
the value of the variable is in the CPU register, which is nominally
inaccessible. (The spill handler must of course access it, so
there is *a* way to get to it, just no *simple* one.)

Moving on from this example, consider machines that do not have
register windows, but do have large register files, such as the
MIPS. (You will find MIPS CPUs in a number of game consoles. I
am not sure if Sega use MIPS today, or Nintendo, or Sony Playstation,
but these are the sorts of devices I mean.) Here the registers
are partitioned in a relatively simple manner by convention, and:

I suppose a brilliant compiler would
know that rA (for example) is not going to be changed by the call to f()
but are compilers this smart?

On the MIPS, functions are divided into "leaf" and "non-leaf". A
"leaf" function is one that makes no subroutine calls. This is easy
to see at compile-time: a function either calls other functions, or
does not. (One ignores the possibility of x being 0 in "if (x)
subfn()" here; something that *could be* a call, *is* a call, for
testing leaf-ness. Of course the leaf testing should happen after
constant propagation and dead-code removal, so that "never call"
is *not* a call.)

Now, if a function is a leaf function, there is no need to:

- save the return-address register (r31), because there will
be no CALL instructions that overwrite it

- worry about called functions overwriting "temporary storage"
register contents

so in leaf functions the compiler will prefer to allocate variables
into the "temporary storage" registers. On the other hand, a
non-leaf function makes calls, so it should go ahead and use regular
"non-leaf" callee-save registers, saving their old values on its
own stack as needed.

Here, if main() calls f() but f() never calls anything, main()
might allocate register v0 (it has been years since I read any MIPS
assembly, but I think this is one of the callee-save registers) to
hold some local variable "i", while f() might use register t0 for
its own local variable "j". Because of the register and function
partitioning (into caller- and callee-save, for registers, and
leaf vs non-leaf, for functions), the compiler can be sure that
these two uses never collide.

And at that point couldn't a knowledgable programmer, someone who
knows the inner workings of the compiler in question, force the
matter anyway? Or, if 'i' is located in a register, use inline
asm to alter that register.

Perhaps. I would simply find a less risky method -- one defined
by the C standard -- myself, because even if you figure out that
main()'s i is in v0, there is no telling when the compiler might
move it to v1 instead.

Like I said before, requires a lot of knowledge about a particular
processor/environment/compiler and is entirely non-portable, but I think
it is probably always 'possible'. However, anyone stupid enough to code
like this should be fired immediately.

There are occasional excuses for oddities like this. I once spent
*days* tracking down a CPU bug in certain UltraSPARC 2 processors --
it turns out that, in a trap handler, if you do arithmetic on %sp
right after reading %tnpc into %l1, the ALU forwarding logic gets
confused and can put the new %sp value into %l1 instead of putting
%tnpc into %l1. But this was (necessarily) all hand-coded assembly
anyway. Still, it is related to the kind of thing one might be
asked, *if we turn the interview question around*.

As I wrote before, the interview question appears to have boiled
down to "find a defined way in which to cause undefined behavior",
and of course, there is none. But suppose we are, as before, given
code like this:

#include <stdio.h>

extern void f(void);

int main(void) {
int x = 1;

f();
printf("x is now %d\", x);
return 0;
}

Instead of asking "how can f() modify x in a defined manner",
suppose we hear: "This program, when run, claimed that x was 42.
Assuming that f() did not print this and exit -- that the printf()
in main() was the one that printed the value of x -- what kinds of
undefined-behavior code often lead to such results? In other words,
what sorts of bugs would you suspect in f() or its callees?" In
this case, "improper use of pointers resulting in stack-smashing
behavior" would be an appropriate suspicion.

This is not something the C standard does, or even can, define,
but it is something that does occur in real programming. It could
therefore make a reasonable interview question.

(Someone else speculated that the question might have to do with
writing a debugger. Perhaps -- but debuggers are about the worst
possible, and least portable, subsystems you can ever work on. I
imagine that anyone qualified to work on a debugger would be well
past these sorts of simple interview questions. You would instead
be getting questions like "are you familiar with leaf vs non-leaf
stack frames; when and whether to use virtual frame pointers; what
sort of synchronzation operations are required before reading or
writing memory in alternate processes or address spaces; how to
interpret symbol tables, `STABS' strings, and `DWARF' information;
the formats of object files including relocations; the kinds of
optimizations compilers do and how to reverse them...".)

 

[Mark Gordon]

Totally unnecissary. I think everyone here can see plainly that Roose
is choking to death on his own dung.

I was think more of any unsuspecting newbie wandering through.

 

[Mark Gordon]

Not to say that Roose is right (I can't even know everything he said
as I killfiled him already), but in the case when a stack is used in
function calls, wouldn't these registers again be saved on the stack
in preparation for the call to f()?

In at least some implementations it is the responsibility of the called
function to save any registers it uses so you would have to ensure
somehow that function f() used all of the registers.

I suppose a brilliant compiler would
know that rA (for example) is not going to be changed by the call to
f() but are compilers this smart?

Again, some compilers will inline simple functions which would enable
them to ensure that there is no clash in register usage.

And at that point couldn't a
knowledgable programmer, someone who knows the inner workings of the
compiler in question, force the matter anyway? Or, if 'i' is located
in a register, use inline asm to alter that register.

Like I said before, requires a lot of knowledge about a particular
processor/environment/compiler and is entirely non-portable, but I
think it is probably always 'possible'.

Then someone makes any change in the code of compiler switches and it
breaks.

I'm sure that there is normally some way of affecting variables that
you should not, it is just vastly more fragile that implied by Roose.

However, anyone stupid enough
to code like this should be fired immediately.

Yes, I completely agree with you.

 

[NFish]

void fn (void);

main ()
{
int i = 20;
fn ();

printf ("%d\n",i);
}

void fn (void)
{
// add ur code only here so that i in main should print OTHER THAN 20
}
Is there any Legal solution for this?
Thanks,
Ashwath

No, but if the code were instead this minor variation:

#include <stdio.h>

void fn(void) {
/* add your code here */
}

main() {
int i=20;
fn();
printf("%d\n", i);
}

You could do this

void fn(void) {
#define fn() i=19
}

or a host of other things.

 

[Christian Bau]

Yes, I completely agree with you.

Aren't you guys completely missing the point of this interview question?

The interviewer wanted to know if the interviewee (the original poster)
was aware of the dangers of undefined behavior in C so he or she asked
how undefined behavior could reasonably lead to a very specific case of
unexpected behavior.

If any C programmer couldn't answer this question, I would suspect he
might have major problems finding bugs in programs invoking undefined
behavior.

 

[Mark Gordon]

Aren't you guys completely missing the point of this interview
question?

The interviewer wanted to know if the interviewee (the original
poster) was aware of the dangers of undefined behavior in C so he or
she asked how undefined behavior could reasonably lead to a very
specific case of unexpected behavior.

That is not the question as posted by the OP, although it *might* have
been the question as either asked or intended by the interviewer.
Equally, the interviewer may have intended checking whether the
interviewee understood that variables are passed by value and that to
modify the value of a variable in a function you pass a pointer to it.

If any C programmer couldn't answer this question, I would suspect he
might have major problems finding bugs in programs invoking undefined
behavior.

I agree that understanding what can happen on buffer overflows is useful
in debugging C code. However, understanding that what you expect to
happen on a buffer overflow might not happen is IMHO equally important.

 

[Tim Woodall]

Didn't see your answer... but his isn't a good one. It says "so that
_main_ should print something other than 20"; this "solution" doesn't meet
the requirements. main still prints 20; it's simply added onto the end of
other, unrelated output.

It's more subtle than that. On many platforms, main _will_ print 220.
(OT Try putting a fork() between fn() and printf() in main and you
will probably get
220\n220\n, not 220\n20\n or 20\n220\n although it's not guaranteed)

Tim.

 

[Noah Roberts]

That is not the question as posted by the OP, although it *might* have
been the question as either asked or intended by the interviewer.

I agree; if the intended result was to find out if the interviewee knows
what kind of bugs could cause i to be modified then the question should
have been worded better. Something like "What kind of things could be
happening in f() to make the result of the printf in main to be other
than 20?" Instead the question was "Write something that causes i to be
other than 20." The later question may be for a very specific venue
where it is important, but in most cases I would say it is a bad
question. It may be that the interviewer intended it to be a trick
question, which I disagree with as being a legitamate interviewing tactic.

 

[Joona I Palaste]

(e-mail address removed) (prashna) wrote in

This is invokes undefined behaviour, but may work on
some implementations (not mine):

void fn(void)
{
"%d\n"[0] = 'i';
}

If we go by that logic, then this will work too:

void fn(void) {
int i;
i=i++;
}

 

[Peter \Firefly\ Lund]

{
"%d\n"[0] = 'i';

Brilliant idea!

If we go by that logic, then this will work too:

void fn(void) {
int i;
i=i++;
}

Nope. Not at all.

If the compiler/linker combines literal strings and they are writable, the
hack should work.

Your "hack" also invokes undefined behaviour but the practical result will
almost invariably be that the i that is local to fn() will have a weird
value compared to whatever unknown value it had before. If the whole
thing doesn't get optimized away, of course. And anyway, it won't be
observable. Or affect the other i (in main).

-Peter

The cheapest, fastest, and most reliable components of a computer system
are those that aren't there.
--Gordon Bell

 

[Phil Tregoning]

(e-mail address removed) (prashna) wrote in

void fn (void);

main ()
{
int i = 20;
fn ();

printf ("%d\n",i);
}

void fn (void)
{
// add ur code only here so that i in main should print OTHER THAN 20
}
Is there any Legal solution for this?

This is invokes undefined behaviour, but may work on
some implementations (not mine):

void fn(void)
{
"%d\n"[0] = 'i';
}