Tuesday, 21 July 2015

Don't use Variable Length Arrays

Hi kids! I'm here to tell you about why to never play with fire! You see, fire is dangerous, hot, and can destroy your house and all your toys!

By fire I mean, the misfeature in C99 called "Variable Length Arrays." You may ask, "Why is this a misfeature? They're so convenient zomg!!!" The answer is simple really: they are ridiculously unsafe.

Take this for example:

#include <stdio.h>
#include <string.h>
#include <math.h>

void huge_vla(size_t size)
{
        int vla[size];
        while(--size) vla[size] = rand();
        printf("Ensure the compiler doesn't optimise it away\n",
                (char *)vla);
}

int main(int argc, char **argv)
{
        int power;
        printf("Input a large number: ");
        scanf("%d", &power);
        huge_vla((size_t)powl(2, power));
        return 0;
}



Looks harmless, although maybe a little contrived. If you're paying attention, you'll probably notice right away that large powers of 2 will certainly exceed the machine's memory.

Now here's where the problem comes into play:

elizabeth@catherine ~ $ ./test
Input a large number: 2
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 10
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 16
Ensure the compiler doesn't optimise it away
elizabeth@catherine ~ $ ./test
Input a large number: 24
Segmentation fault  

 
You might think, "well 2^24 is pretty big anyway." But, it's only 16,777,216 bytes. Odds are pretty good your average Wikipedia article (excluding stubs) has well more than that if you count images.

The reason it is is so low is because of this:

0000000000400776 <huge_vla>:
  400776:       55                      push   %rbp
  400777:       48 89 e5                mov    %rsp,%rbp
  40077a:       53                      push   %rbx
  40077b:       48 83 ec 38             sub    $0x38,%rsp
  40077f:       48 89 7d c8             mov    %rdi,-0x38(%rbp)
  400783:       64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
  40078a:       00 00
  40078c:       48 89 45 e8             mov    %rax,-0x18(%rbp)
  400790:       31 c0                   xor    %eax,%eax
  400792:       48 89 e0                mov    %rsp,%rax
  400795:       48 89 c3                mov    %rax,%rbx
  400798:       48 8b 45 c8             mov    -0x38(%rbp),%rax
  40079c:       48 89 c2                mov    %rax,%rdx
  40079f:       48 83 ea 01             sub    $0x1,%rdx
  4007a3:       48 89 55 d8             mov    %rdx,-0x28(%rbp)
  4007a7:       49 89 c2                mov    %rax,%r10
  4007aa:       41 bb 00 00 00 00       mov    $0x0,%r11d
  4007b0:       49 89 c0                mov    %rax,%r8
  4007b3:       41 b9 00 00 00 00       mov    $0x0,%r9d
  4007b9:       48 c1 e0 02             shl    $0x2,%rax
  4007bd:       48 8d 50 03             lea    0x3(%rax),%rdx
  4007c1:       b8 10 00 00 00          mov    $0x10,%eax
  4007c6:       48 83 e8 01             sub    $0x1,%rax
  4007ca:       48 01 d0                add    %rdx,%rax
  4007cd:       be 10 00 00 00          mov    $0x10,%esi
  4007d2:       ba 00 00 00 00          mov    $0x0,%edx
  4007d7:       48 f7 f6                div    %rsi
  4007da:       48 6b c0 10             imul   $0x10,%rax,%rax
  4007de:       48 29 c4                sub    %rax,%rsp
  4007e1:       48 89 e0                mov    %rsp,%rax
  4007e4:       48 83 c0 03             add    $0x3,%rax
  4007e8:       48 c1 e8 02             shr    $0x2,%rax
  4007ec:       48 c1 e0 02             shl    $0x2,%rax
  4007f0:       48 89 45 e0             mov    %rax,-0x20(%rbp)
  4007f4:       eb 17                   jmp    40080d <huge_vla+0x97>
  4007f6:       b8 00 00 00 00          mov    $0x0,%eax
  4007fb:       e8 70 fe ff ff          callq  400670 <rand@plt>
  400800:       89 c1                   mov    %eax,%ecx
  400802:       48 8b 45 e0             mov    -0x20(%rbp),%rax
  400806:       48 8b 55 c8             mov    -0x38(%rbp),%rdx
  40080a:       89 0c 90                mov    %ecx,(%rax,%rdx,4)
  40080d:       48 83 6d c8 01          subq   $0x1,-0x38(%rbp)
  400812:       48 83 7d c8 00          cmpq   $0x0,-0x38(%rbp)
  400817:       75 dd                   jne    4007f6 <huge_vla+0x80>
  400819:       48 8b 45 e0             mov    -0x20(%rbp),%rax
  40081d:       48 89 c6                mov    %rax,%rsi
  400820:       bf c0 09 40 00          mov    $0x4009c0,%edi
  400825:       b8 00 00 00 00          mov    $0x0,%eax
  40082a:       e8 f1 fd ff ff          callq  400620 <printf@plt>
  40082f:       48 89 dc                mov    %rbx,%rsp
  400832:       48 8b 45 e8             mov    -0x18(%rbp),%rax
  400836:       64 48 33 04 25 28 00    xor    %fs:0x28,%rax
  40083d:       00 00
  40083f:       74 05                   je     400846 <huge_vla+0xd0>
  400841:       e8 ca fd ff ff          callq  400610 <__stack_chk_fail@plt>
  400846:       48 8b 5d f8             mov    -0x8(%rbp),%rbx
  40084a:       c9                      leaveq
  40084b:       c3                      retq


Well, GCC emits some pretty crummy code at -O0 I guess, though a lot of it is because memset was inlined. But if you look closely (and if you can't read x86 asm, I will simply tell you), you'll see it simply tosses it on the stack. It doesn't call malloc() and get anything from the program break or an mmaped region. Nope, it just uses the stack space, which is in short supply.

This is also why alloca() is considered unsafe, and anyone sensible should not be using it, no matter what that one thing Drepper wrote says.

Basically, you have a gratuitous stack overrun, and there is no real way to determine how much stack you even have left. Of course, you can see it adds guards to ensure the stack overrun can't do anything nasty, but on older systems, it won't do this at all.

Deeply nested calls or recursion could lower stack space further; more variables or arrays would do it too. Your limit may be a lot less than 2^24. You just don't know, and the compiler can't check for you (I'm not sure if GCC checks array bounds anyway), because it's only known at runtime what the size will be.

I suppose some tool will say, "why not use a SIGSEGV handler?" To which I say, "oh wow, I bet you write bug-free code which never has wild pointers that corrupt the SIGSEGV handler or anything like that, nope, that's not you." Never assume you're as good as you think you are. In any case, this is terrible practise, unusable in a library, and there is a special place in Hell reserved for people who abuse SIGSEGV in such a terrible way to hide the fact they're using unsafe practises.

Basically the takeaway is this: just use malloc(). At least when it fails, you know about it, and you can tell your user what went wrong with an "out of memory" error, versus "OH SHIT I JUST SHIT MY FUCKING PANTS!"

EDIT:

I would like to point out clang emits better code at -O0, but does the same thing, lest any of you Apple fans believe your infallible popes, His Holiness Tim Cook and the late Pontiff Steve Jobs can do no wrong:

0000000000400720 <huge_vla>:
  400720:       55                      push   %rbp
  400721:       48 89 e5                mov    %rsp,%rbp
  400724:       48 83 ec 20             sub    $0x20,%rsp
  400728:       48 89 7d f8             mov    %rdi,-0x8(%rbp)
  40072c:       48 89 e0                mov    %rsp,%rax
  40072f:       48 89 45 f0             mov    %rax,-0x10(%rbp)
  400733:       48 8d 04 bd 0f 00 00    lea    0xf(,%rdi,4),%rax
  40073a:       00
  40073b:       48 83 e0 f0             and    $0xfffffffffffffff0,%rax
  40073f:       48 89 e7                mov    %rsp,%rdi
  400742:       48 29 c7                sub    %rax,%rdi
  400745:       48 89 fc                mov    %rdi,%rsp
  400748:       48 89 7d e8             mov    %rdi,-0x18(%rbp)
  40074c:       48 8b 45 f8             mov    -0x8(%rbp),%rax
  400750:       48 05 ff ff ff ff       add    $0xffffffffffffffff,%rax
  400756:       48 89 45 f8             mov    %rax,-0x8(%rbp)
  40075a:       48 3d 00 00 00 00       cmp    $0x0,%rax
  400760:       0f 84 17 00 00 00       je     40077d <huge_vla+0x5d>
  400766:       b0 00                   mov    $0x0,%al
  400768:       e8 a3 fe ff ff          callq  400610 <rand@plt>
  40076d:       48 8b 4d f8             mov    -0x8(%rbp),%rcx
  400771:       48 8b 55 e8             mov    -0x18(%rbp),%rdx
  400775:       89 04 8a                mov    %eax,(%rdx,%rcx,4)
  400778:       e9 cf ff ff ff          jmpq   40074c <huge_vla+0x2c>
  40077d:       48 bf 0c 09 40 00 00    movabs $0x40090c,%rdi
  400784:       00 00 00
  400787:       48 8b 45 e8             mov    -0x18(%rbp),%rax
  40078b:       48 89 c6                mov    %rax,%rsi
  40078e:       b0 00                   mov    $0x0,%al
  400790:       e8 2b fe ff ff          callq  4005c0 <printf@plt>
  400795:       48 8b 75 f0             mov    -0x10(%rbp),%rsi
  400799:       48 89 f4                mov    %rsi,%rsp
  40079c:       89 45 e4                mov    %eax,-0x1c(%rbp)
  40079f:       48 89 ec                mov    %rbp,%rsp
  4007a2:       5d                      pop    %rbp
  4007a3:       c3                      retq  
  4007a4:       66 66 66 2e 0f 1f 84    data16 data16 nopw %cs:0x0(%rax,%rax,1)
  4007ab:       00 00 00 00 00


Different compiler, same old technique. Except sans stack protection.

Saturday, 31 January 2015

A simple admonition about patches

I understand FSUES is a real thing, I really do. But really, it's rude to tell your users, "patches welcome," then let their patch languish or ignore it.

Why not say what you really mean, "go fuck yourself, I don't care about your problem, and am not interested in any fixes for it?" It's really about as polite. I'd argue it's more polite, since explicit is better than implicit.

I would say OpenBSD gets this right, more or less, even though Theo de Raadt is an autistic wanker (to quote Captain Sensible, "I may talk a lot of shit, but this time I'm right! [Theo] is a fucking wanker!"). So does Linus Torvalds. :P

Thursday, 29 January 2015

Implementing missing Linux syscalls in the FreeBSD linuxulator

So I've taken the plunge and now run FreeBSD full-time on my laptop (11-CURRENT because I have never shied away from the bleeding edge, even if I shoot myself in the foot in the entire process). So far everything seems to work fine, though I have to load i915kms after boot completes, and I get the occasional lock-order reversal warning (so far nothing serious). Pretty nice.

What has bugged me though is the state of FreeBSD's linuxulator. It's reasonably complete enough to run flash, but I desire something a bit more. Here is the laundry list of things I want to do:

* Implement missing syscalls (at least the most commonly used ones) where appropriate
* 64-bit Linux (not just 32-on-64 bit) support (will need to investigate this a bit more, this will require some dark magic)

Currently I am implementing calls required to run Gentoo in a chroot. So far emerge doesn't work due to several unimplemented calls:
linux: pid 51309 (dircolors): syscall dup3 not implemented
linux: pid 51310 (python3.3): syscall prlimit64 not implemented
linux: pid 51310 (python3.3): syscall sendmmsg not implemented
linux: pid 51314 (rsync): syscall utimensat not implemented
linux: pid 51395 (python3.3): syscall prlimit64 not implemented
linux: pid 51395 (python3.3): syscall epoll_create not implemented
I have already implemented dup3 and will be sending patches to the mailing list. Anna has already implemented goodtimesutimensat. Next on my laundry list is probably the epoll_* family, which I intend to implement by translating all the calls to kqueue equivalents. I have no idea what the others are yet, but I am investigating.

Stay tuned...

Sunday, 11 January 2015

Regarding use of list(APPEND FOO_VAR "foo_value") in cmake

Although CMake's performance-tuning suggestions seem to imply that the following two statements are equivalent:

list(APPEND FOO_VAR "foovalue")
set(FOO_VAR "${FOO_VAR} foovalue")

They are in fact, not equivalent. This should have been a no-brainer, but I figured CMake lists were faked. I was wrong. Don't fall into this trap in your own projects.

Also, I'm glad to see CMake's documentation has at least improved compared to five years ago. It used to be nonexistent, and you were told to buy their book if you wanted documentation.

Saturday, 10 January 2015

An open letter to Richard M. Stallman

Dear Richard M. Stallman,

As illustrated in a recent thread on the emacs mailing list, you are opposed to GCC dumping the AST, as you are afraid proprietary programs will be created to modify GCC's AST output, which would not be open source.

Let me put your fears to rest: nobody cares about using GCC's AST for this purpose.

If anyone wanted to do so, they would already use the non-copylefted clang and LLVM. By being stubborn about this issue, you are actually harming the copyleft cause.

You see, if someone cares about the issue enough, GCC will be forked, a fork that does exactly what you're afraid of. Remember EGCS? Remember libc5? These alone demonstrate a fork of FSF software is not only possible, but easy to promote with sufficient clout. This is not a good state of affairs for the FSF's definition of FOSS, and is not good for GCC.

To put it simply: nothing stops someone from making a GCC fork with the needed modifications to dump the AST (though I believe GCC can already do so with a plugin). It is quite irrelevant if it's copylefted — vendors have enough clout to push it as the blessed fork if they truly cared.

The reason that this hasn't materialised is not because copyleft is magically protecting GCC. It is because clang already does what people want, and there is no need to modify the AST or IR to do specific optimisations. You can just modify the compiler directly.

All this is accomplishing is reducing the effectiveness of GCC as a weapon against non-FOSS software to the point of having the injury potential to non-free software equal to a mosquito. Given enough time, GCC will be doomed to obscurity, at the hands of people with far more clout than the FSF. Clang itself was created under such conditions, and has become dominant in academia and business. This is truly unfortunate, as clang and GCC ought to coexist, for the good of them both — competition breeds innovation.

I may not necessarily agree with the ideals of copyleft (I do not feel it is more free than a copycenter license with my definition of free), but I do not want to see GCC doomed to obscurity. I ask you to consider your position carefully, lest your walled copyleft city is simply abandoned.

Respectfully yours,

Elizabeth Myers

V-Blank timings are fixed in sgherm (and some thoughts on documentation in code)

Anna managed to fix LCDC timings by complete accident, and now Link's Awakening works. One minor caveat: the intro doesn't scroll properly. I think this is due to STAT interrupt timing or not firing (Link's Awakening doesn't use them), but this is progress! This makes me happy.

Incidentally, MESS's documentation is a disaster — I can't make heads nor tails of it, and it seems neither could they. They tried to write specifications intermixed with code, and failed so hard, I see why their GB emulation was never finished.

This is why I believe in a clean separation of specifications and code. Comments are for annotating code and explaining the reason something is done; specifications, theory, and higher-level views belong in a separate document. In the process of mixing code and specifications, the algorithms get lost, and with it, the clarity of what you're trying to do.

AdBlock plus keeps disabling itself

AdBlock plus seems to constantly keep disabling itself in Firefox (no, I am not going to use Chrome, thanks). I don't mean the plugin itself, just the ads filtering (icon turns grey, ads aren't blocked, etc.). Search results reveal two things:
  1. This is ridiculously common
  2. It's dismissed as an "antivirus software"/"user error" problem
Considering I use Linux, I really doubt an "antivirus" is to blame. Moreover, the idea that an antivirus program would disable a feature in a plugin like this arbitrarily is ridiculous.

Given that I'm not setting the knob, and it doesn't magically happen at restart (it seems to happen after I visit some pages), I think there's either an exploit (known or unknown) in AdBlock Plus, or some other functionality that allows pages to turn it off.

Given AdBlock Plus is a business, I wouldn't be surprised if they had such a thing, and were selling it to ad companies. Hell, knowing people in the ads business, and hearing their stories of the sleaziness of the ads industry, I'd be surprised if this wasn't going on.

I wish I could find the uBlock plugin for Firefox people are telling me exists, but searching is turning up nothing. I think it's just idiocy put out by "Chrome master race" users who don't actually have a clue.