Massacring C Pointers

The amount of students prevents us from real selection, instead we take exercises which failed tests (and that are not empty) and explain what was wrong, identify common mistakes or bad style and try to make it correct.

We had a very good feedback on this. And we saw an evolution in students' code. It was way better than trying to do collection of bad practice ...

The tutorials about these exercises were really cool, because we'd spend a short time wrapping up mistakes in the notation. But then he usually classified and grouped the different solutions according to the design decisions made and it would evolve into large discussions about tradeoffs of choices.

Someone might go "Well I figured the FSM would be smaller if I fail on the first wrong number, and it'd be user friendly because it fails early", and someone objects "But that's insecure!" and someone else figures "And also it'd be much easier to write up a control circuit that always expects three digits" and eventually everyone is confused if we're looking at the user input as a stream of tuples of three digits, instead of looking at the last three digits in a stream of digits.

It was a very instructive class.

Lastly, and this is taught by another professor, is my class for Linux. It includes bash and C++ programming and focuses a bit on the POSIX API. Our exam was last week and we had 3 parts. The first part was a theory exam by the professor that taught the class. It was about bash/POSIX commands and very little Linux specific stuff. He expected us to know all of the options from all of the commands you can think of: cut, split... You had to know all of them and off the top of your head. It's ridiculous. I'm pretty sure I failed that one, but I absolutely nailed the next part which was about bash scripting (where you could use if statements and the like, the first part did not allow it, only redirection and piping). The man is mad (hah man, that's what I needed during that first exam part).

That kind of righteous fury is very common in high school and undergrads. Teachers have to perform in front of a tough crowd.

You mean he gathered all of his students, colleagues, and superiors; officially admitted to faking knowledge where there was none, and solemnly apologized, promising never again to teach things he doesn't understand?

I somehow doubt it, even though teaching nonsense to eager youth from the position of authority is an offense damn close to sexual molestation of minors. Dealing with subtly (or not so subtly) twisted minds, and holes (and lies) in knowledge, of the corrupted students happens years later and is someone else's problem, but it's all caused by teachers like this. I don't see anything graceful in it, at all.

I spent a couple of months "hacking", just familiarizing myself with the microcontroller and its instruction set, and the tooling. (In fact, I had no source code to look at during this time, as he would not surrender it!) When I finally got his source, I rewrote it to a 100% functional equivalent in two weeks, 1/5 the size without all the unnecessary control path duplication and without pointless register moves. At the time I found the way he had used register moves particularly puzzling because it resembled the way an un-optimized compiler might work.

Months later after I was no longer on that project, I got a call from him. He was very flustered and wanted to know where I "got" a particular sequence of instructions from. I was like, come again? He said, "It's not in the book. You used a sequence of instructions that's not in the Book." (The Microchip programming manual.) He asked about another block of 3 or 4 instructions - also not in the book (in the combination I used them in).

Slowly it dawned on me - I'm quite certain he didn't understand what any individual instruction "did". That whole level level of abstraction didn't exist for him. He programmed in assembly, yes, but only using blocks of example instructions from the Book. Suddenly the pointless register moves made sense - he was acting as a human compiler, without an optimization step.

Years later I realized I should have asked him, "and how do you think the example code in the book was written?"

Ironically, I think this is one of the best lessons anyone can learn . . .

He did his best but I have taught my self faster than he did.

Though because I was on the CSE stream even though I got a grade 1 they wouldn't let me do computing at A level - as CSE kids where supposed to leave at 16.

> ... The Hacker News army is here.

"Screw You Bob" you do not speak for me. Hopefully, you don't speak for many people on HN.

Words fail me. Can't we let the dead rest in peace?

I wonder if these people ever got to know a bit about the things they didn't understand at the time. I also wonder if I'll ever get to know about the unknown unknowns in my life :)

That compiler uses a run-time call stack.

It copies s and then t to a fixed size buffer, without any checks. That will write to invalid memory (probably smashing the stack) if len(s), len(t) or len(s) + len(t) > 100.

It returns a stack allocated buffer (r) pointer to the caller. The array will be invalid when the function returns, as the automatic variables only live in the function scope (during the call), they are deallocated when the function returns.

To do this right you have various strategies.

1. Allocate a buffer of len(s) + len(t) + 1 with malloc, copy the strings and return it. Have the caller free it when it's done. It can be inapropiate because of the dynamic allocation.

2. Have the caller pass a destination buffer and its size. If you know the char *'s are zero terminated, check if you have space for them in the dest buffer. If not, truncate or error out. Most of the times, this is the prefered solution.

3. Use a static local buffer, and return it to the caller. You may need to truncate the copy too. Not recomended. This is not a good solution as the function also will not be reentrant (unsafe with multiple threads).

You can use libc functions like strncpy (C89+), snprintf (C99+) etc to make a "size-checked" copy with various automatic truncation semantics. You can refer to their man pages for details.

Edit: to the downvoters, please point out what is wrong in the comment.

1. Returns pointer to stack-allocated data, which immediately becomes invalid. Instead, it should be using some sort of allocation (e.g. 'malloc'), or taking in a destination pointer.

2. 'r' is arbitrarily set with length 100. Smaller strings don't need all that space, and larger strings definitely will overrun.

3. The function signature is really awkward. Without any of the surrounding textbook content, I'm not sure what behavior is supposed to happen. At first, I expected something like 'strcat', which takes two char* and appends the second one to the first one. But that isn't happening here and instead it seems to require dynamic allocation. (Hiding allocations inside a function is generally kind of weird. Usually the caller should be responsible for passing in a handle to the destination.)

4. There's no sensical limit on the loop iteration. If the input 't' doesn't have a null terminator, this is going to throw a ton of garbage into the stack space (because 'r' is stack-allocated to a fixed size). And also maybe run for a really long time.

5. 'strcpy' should usually be replaced by 'strncpy', which performs the same function but also requires you to provide a limit ("copy this string, but at most 'n' bytes"). That prevents a class of exploitable errors known as "buffer overruns". I don't know when the 'n' string functions were added to C or became popular, though.

This is a teaching exercise, so the fact that this is implemented as a separate function instead of calling 'strcat' from <string.h> doesn't seem like a big problem.

It returns a pointer to memory on the stack; but the stack will shrink when the function returns, and that piece of memory will get re-used. Which is consistent with the article's later claim that "I don’t think he understands the call stack."

Ok, so it's reasonable to think that this is supposed to be a teaching example and that considering these concepts might be a bit too early in the process. This leads into the second problem and one that is more subjective: this code is incredibly dense and relies on enough quirks of C that it's almost never going to be clear to a beginner reader what they are supposed to take away from it. It's maybe useful as a quiz question on C syntax and semantics, but there are enough barriers to understanding what the code is supposed to do that the amount of explaining the text would need to do to describe what the code is doing is most likely prohibitively long. Instructive examples should be unambiguous in what they are trying to show, otherwise students will be confused and potentially conflate issues in a way that is difficult to untangle later.

Edit: Ha! I spent so long looking at the first half of the function I totally missed that it was returning r! So, not only does this code have minor issues here and there from its careless implementation, it has a fundamental flaw that, if it were to work, would do so only by accident. I can only imagine that a student might walk away from this example thinking that C functions can return arrays and possibly misunderstand scoping in C.

* What happens if s or t are longer than 100 characters?

* What happens if s and t are both longer than 50 characters?

* What happens if no element of s == '\0'? How about t?

* r is allocated on the stack. What happens to the memory pointed at by r when you call another function after calling combine? Say you wanted to combine three strings; could you call combine twice to build up the result?

But,yeah... It's a massacare.

In one sentence: this guy managed to reinvent a variant of strcat and get it completely wrong.

Here's a somewhat better version:

    char *combine(char *s, char *t) {
        size_t m = strlen(s), n = strlen(t);
        char *ret = malloc(m + n + 1);
        if(ret) {
            memcpy(ret, s, m);
            strcpy(ret + m, t);
        }
        return ret;
    }

Furthermore, r is a fixed 100 bytes. There is no overflow checking whatsoever.

If you're actually learning C and writing programs in it then the two best things to do would be turn compiler warnings up to 11 and run valgrind often. So you want -Wall and -Wpedantic when you compile and if possible run with valgrind as part of your build script or run it with your tests, just run it often (the longer between runs the harder it is to track back to which change you made).

   1 char *combine(s, t)
   2 char *s, *t;
   3 {
   4
   5   int x, y;
   6   char r[100];
   7
   8   strcpy(r, s);
   9   y = strlen(r);
  10   for (x = y; *t != '\0'; ++x)
  11     r[x] = *t++;
  12 
  13    r[x] = '\0';
  14
  15    return(r);
  16
  17 }

1) The function is returning the address of a local variable. This alone makes this function rubbish.

2) The pointers s and t are unknown length, we have no guarantees that concatenating them will fit in a 100 character array. Also, he probably should be using malloc to dynamically allocate the space.

3) Use of the function strcpy rather than strncpy. He should have measured the length of s first, and then use strncpy if s was longer than 99 characters (don't forget the null terminator!). Then, rather than using a for loop, call strncpy again to copy the rest into a safe buffer size (the for loop is rather silly). The reason for this is that strcpy will cheerfully start copying past the array 'boundaries', and in this case, since he's copying into a local variable on the stack, is setting himself up for a Remote Code Execution attack if this ever gets untrusted input.

So those are the critical errors. These tie directly into why Geoff argues that the author doesn't understand the stack.

So let's, for educational purposes, go into this. We're going to go a bit into the weeds here. Sorry about that. This would be easier with a whiteboard. :)

When you fire up a program, the programs machine instructions get copied into memory, let's pretend at the memory location 0x1000. Far away from that code, at the highest memory values (more complicated on modern virtual systems, but hey, let's go back in time here :) ), the computer keeps track of a location called the stack pointer.

I'm going to put forward 3 diagrams now. Please forgive any off by one errors.

  (Diagram a)
    Registers
    A 0
    B 0
    C 0
    SP 0xffff
    PC 0x1000

    Address  Mnemonic   DATA
  PC0x1000   MOV 1, A   0x00 0x01 0x01 0x01
    0x1004   MOV A, C   0x00 0x01 0x03 0x01
    0x1008   PUSH 3     0x01 0x00 0x00 0x03
    ...      ...
    ...      ...
    ...      ...
    0xfffc   XXXXXXXX   0x00 0x00 0x00 0x00 <-- Stack Pointer is here

  (Diagram b)
    Registers
    A 1
    B 0
    C 1
    SP 0xfffe
    PC 0x1000

    Address  Mnemonic   DATA
    0x1000   MOV 1, A   0x00 0x01 0x01 0x01
    0x1004   MOV A, C   0x00 0x01 0x03 0x01
  PC0x1008   PUSH 3     0x01 0x00 0x00 0x03
    ...      ...
    ...      ...
    ...      ...                     v------\
    0xfffc   XXXXXXXX   0x00 0x00 0x00 0x03 ^-- Stack Pointer is here

  void function() {
     int a = 5;
     int b = 2;
     return a;
  }

  void main() {
    return function();
  }

  (Diagram c)
    Registers
    A 5
    B 0
    C 0
    SP 0xfff8
    PC 0x2010

    Address  Mnemonic      DATA
    # Main starts here
    # (Note, in C, there is actually code that gets executed before this)
  PC0x1000   PUSH 0x1008   # We want to remember where to return to, so we push it to the stack.
    0x1004   JMP  0x2000
    0x1008   EXIT A        # In this implementation of C, the A register will propagate return values
    ...      ... 
    # Function 'function' is here
    0x2000   PUSH 5        # Local variables go on the stack.
    0x2004   PUSH 2
    0x2008   MOV [SP+2], A # Locally, we refer to local variables by
                           # offsets to the stack pointer, so if this function
                           # were to call itself, the stack would keep growing down
                           # but these values would be good.
    0x200c   MOV SP+2, SP  # Reset the stack before returning
  PC0x2010   JMP #SP       # Made up notation. Look at the value of the stack pointer, pop it, and jump to it.
                           # in x86, this is kinda what RET does.
    ...      ...
    ...      ...           ...
    ...      ...           ...         
    0xfff8   XXXXXXXX      0x00 0x00 0x00 0x00SP  
    0xfffc   XXXXXXXX      0x02 0x05 0x10 0x08

Furthermore, if the input strings are longer than expected, than they can overwrite values on the stack itself, including the return addres, causing your program to jump to some (if you're lucky) random location in memory.

Honestly, some of the best ways to get intuition for how the stack works, and the things that can go wrong, are CTFS at overthewire.org.

Also, https://microcorruption.com/

http://overthewire.org/wargames/bandit/

http://overthewire.org/wargames/leviathan/

[1] Sorry, 'down' means lower memory addresses, even though the displays of memory layouts always have lower memory addresses "up". :(

The function in question:

    char *combine(s, t)
    char *s, *t;
    {
          int x, y;
          char r[100];

          strcpy(r, s);
          y = strlen(r);
          for (x = y; *t != '\0'; ++x)
               r[x] = *t++;
          r[x] = '\0';
          return(r);
    }

2. The array 'r' is allocated at a fixed size. This is okay if you know ahead of time that you know this size, however for this function we don't know the lengths of s and t, so the odds that we are allocating the right amount of memory is slim.

3. As a result of points 1 and 2, the strcpy and loop may cause a buffer overflow. This is a class of bug where it is possible to overwrite memory that should be unavailable to us. In this case, if the combined lengths of s and t happen to be equal or greater than 100 characters, we will be overwriting memory that does not belong to r, corrupting it, and potentially crashing the program. This may additionally be as security risk, as buffer overflows can be exploited to execute malicious code.

4. There are no checks to see whether s and t are valid pointers. If they are NULL then the function would generate a segmentation fault. This is a check that is often ignored in cases where it is deemed to potentially hinder performance if the function is used frequently.

saulrh also mentions the case where s or t are not NUL-terminated. This is often considered to be a pre-condition of the function in C, suggesting that providing the function strings that aren't NUL terminated is an issue for the user.

For some comparison the following would be my first cut at the same function. Note I the comments are only for illustrative purposes. I'd omit them in actual code.

    char* combine(const char *s, const char *t)
    {
        size_t slen, tlen;
        char *str;
        
        // optional checks for validity (point 4)
        if (NULL == s || NULL == t)
        {
            return NULL;
        }
        
        // get lengths of s and t, to calculate allocation size
        // also save them to use with memcpy later
        slen = strlen(s);
        tlen = strlen(t);
        
        // allocate to heap (point 1)
        // allocate correct size (point 2)
        str = malloc(slen + tlen + 1);
        if (NULL == str)
        {
            return NULL;
        }
        
        // use memcpy since we already know the size
        memcpy(str, s, slen);
        memcpy(str + slen, t, tlen);
        str[slen + tlen] = '\0';
        
        return str;
    }

Hmm, I'm starting to see a pattern. Is it possible BASIC, plus lack of internet back in the day, plus attrocious books are the reasons for truning poeple into terrible programmers? I happen to know only a couple of seniors but without exception their code, no matter what language written in today, is horrible on all fronts. I used to think it was a lack of attention to detail, their lack of wanting to strive for even the tiniest bit of more than just 'good enough for tady'. Possibly stemming from lack of education and lack of continuous self-education. But maybe there's more to it. Maybe they were influenced by a bad book. And/or by a not-so-optimal language like BASIC.

Using the Windows 'ZeroMemory' macro to assign bitwise zero over a newly declared object, rather than using a constructor like god intended.

In C++, null isn't required to be bitwise zero, so I'm fairly sure nasal demons are possible here. (Do we still have 'effective type' in C++?)

No, it's not. It is true that an expression of array type, when it is not the subject of either the unary-& or sizeof operators, evaluates to a pointer to the array's first element.

  sizeof array

  &array

I think it was this book (https://www.amazon.com/Flights-Fantasy-Programming-Video-Gam...) that taught me 3D programming better than anything else. The code was readable, the maths was well explained and it included sections on how to do things without those newfangled maths co-processors. I'd love to buy a copy now just to see if it really was a good book or if it led me astray.

There hasn't been a lot of activity on it recently so it's probably still wrong.

[1]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guid...

> I’m Geoff Wozniak, just one of those persons on the Internet. My blog is hosted here, but not much else at the moment.

"Regrettably, this insight was obscured by a regrettable poor choice of terminology ("bad" and "good"). The comments, azernik, has enough HN karma to suggest that this error ought be assigned to the casual, off-the-cuff nature of internet commenting, and that this comment is not up to the usual work (i.e. comments) of the author.