So, stories about undefined behavior have been making rounds again in my Twitter and RSS feeds (two things I was supposed not to be using, but anyway), which brought me some new thoughts and some other thoughts I meant to blog about ages ago but forgot about them.
The most recent one was this comment on Hacker News (via @pcwalton, via @jamesiry), which presents the following code, which is supposed to take a circular linked list, take note of the head of the list, and walk around the list freeing each node until it finds the node that points back to the head (and thus the end of the list):
void free_circularly_linked_list(struct node *head) {
struct node *tmp = head;
do {
struct node *next = tmp->next;
free(tmp);
tmp = next;
} while (tmp != head);
}
This looks (to me) as good C code as it gets. However, this code triggers undefined behavior: after the first iteration of the loop frees the node pointed to by head, it is undefined behavior to perform the tmp != head comparison, even though head is not dereferenced.
I don't know what is the rationale behind this. Maybe that would make it possible to run C in a garbage-collected environment where as soon as an object is freed, all references to it are zeroed out. (The fact that no one has ever done this (as far as I know) is mere detail. The fact that in a garbage-collected environment free would likely be a no-op is a mere detail too.)
The feeling I had after I read this is that C is in a kind of identity crisis: C allows you to do all sorts of unsafe operations because (I'd assume) it's supposed to let you do the kind of bit-bashing you often want to do in low-level code; at the same time, modern standards forbid that very bit-bashing. What is the point of programming in C anymore?
[Addendum: To be more clear, what is the purported goal of the C language? The feeling I have is that it has moved from its original function as a "higher-level assembly" that is good for systems programming, and is trying to serve a wider audience more preoccupied with performance, but in doing so it is not serving either audience very well.]
And the standards forbid these operations in the worst possible way: by claiming that the behavior is undefined, i.e., claiming that compilers are free to do whatever the hell they please with code perfoming such operations. Compilers keep becoming better and better at exploiting this sort of undefinedness to better "optimize" code (for speed, anyway). Meanwhile, they keep breaking existing code, and opening new and shiny security vulnerabilities in programs. The NSA probably loves this.
At this point, I'm beginning to think that C does not serve its purpose well anymore. The problem is that there seems to be no real alternative available. Maybe Rust can be it, although I don't really know how well Rust does in the bit-twiddling camp (e.g., can you easily perform bitwise and/or with a pointer in Rust? Well, come to think of it, even C does not allow that; you have to cast to an integer first.)
* * *
The other undefined behavior I've been reading about lately is signed overflow. In C, signed overflow is undefined, which means that code like:
if (value + increment < value) {
printf("Overflow occurred! Aborting!\n");
exit(1);
}
else {
printf("No overflow; proceeding normally\n");
value += increment;
}
is broken, because the compiler is likely to optimize the overflow check and the then branch away and just leave the else branch. I have seen two rationales given for that:
Pointer arithmetic. In the good old times, an int and a pointer used to have the same size. People happily used ints as array indices. Array indexing is just pointer arithmetic, and in some architectures (like x86), you can often perform the pointer arithmetic plus load in a single instruction.
Then came 64-bit architectures. For reasons I don't really get (compatibility?), on x86-64 and other 64-bit architectures ints remained 32-bit even though pointers became 64-bit. The problem now is that transformations that assumed integers and pointers to be the same size don't work anymore, because now their point of overflow is different. For example, suppose you had code like:
void walk_string(char *s) {
for (int i=0; s[i]; i++) {
do_something(s[i]);
}
}
Usually, the compiler would be able to replace this with:
void walk_string(char *s) {
for (; *s; s++) {
do_something(*s);
}
}
which is potentially more efficient. If ints and pointers have the same size, then this transformation is okay regardless of overflow, because the int would only overflow at the same point the pointer would anyway. Now, if ints are supposed to wrap at 32-bits but pointers wrap at 64-bits, then this transformation is not valid anymore, because the pointer version does not preserve the overflow behavior of the original. By making signed overflow undefined, the problem is sidestepped entirely, because now at the point of overflow the compiler is free to do whatever the hell it pleases, so the fact that the overflow behavior of the original is not preserved does not matter.
Now, there is a number of things wrong in this scenario:
Now ints cannot be used to index into an arbitrarily-sized array, only 232-element ones at most. In any sane language (I'd argue), the standard integer type would be one encompassing the full range of valid array indices. (Common Lisp explicitly requires fixnums to have at least that range, for instance.)
Unsigned overflow is defined. That's good, but at the same time it seems kinda strange that we have been using signed integers for array indices all this time, to the point that the undefinedness was chosen precisely to enable optimization of this usage, even though, come to think of it, it seems kinda wrong to use a signed integer in this circumstance (if your array takes more than half the memory space, this would be wrong, for instance).
Optimizations based on "real math". The other reason I am aware of for making signed overflow undefined is to enable optimizations based on the mathematical properties of actual mathematical integers. An example is assuming that x+1 > x, for instance (which is what breaks the overflow test mentioned before). Another example is assuming that in a loop like:
for (i=0; i<=limit; i++) { ... }
the halting condition i<=limit will eventually be true, and therefore the loop will finish; if i were defined to overflow, then this loop would be infinite when limit == INT_MAX. Knowing that a loop terminates enables some optimizations. The linked article mentions enabling use of loop-specific instructions which assume termination in some architectures. Another advantage of knowing that a loop terminates is enabling moving code around, because non-termination is an externally-visible effect and you may not be able to move code across the boundaries of an externally-visible event [please clarify]. Now, something that occurred to me back when I read that post is that it assumes a dichotomy between either treating overflow as undefined, or defining it to wrap around. But there are other possibilities not explored here. I don't necessarily claim that they are feasible or better, but it's interesting to think on what optimizations they would enable or preclude. For instance:
One possibility is to actually make integers behave like their mathematical counterparts. This is what Common Lisp and Python do, for instance, by automatically promoting fixnums to bignums when they exceed the representation capacity of fixnums. In this case, all optimizations based on actual arithmetic are not only possible but safe, because the language integers actually respect those properties. The drawback is that now you have to deal with bignums, and check whether a number is a fixnum or a bignum before performing arithmetic.
Another possibility is to make integer overflow trap, i.e., raise an exception, abort execution, or something along those lines. In this case, an assumption like x+1 > x is true as long as x+1 does not trap. This might not enable the same amount of optimization as claiming undefined behavior for overflow, but at least it enables knowing that a loop terminates (either by hitting the termination condition or by aborting on overflow). Although aborting on overflow is an externally-visible event too, so I don't know if you would be able to perform the aforementioned code moving. Actually, I'd need to see an example of code moving that would be benefited by knowing about termination. I need to research this. [I rememeber seeing some code involving multiple threads and the observable behavior of one thread from another, but (1) I'd have to find it; (2) I'd have to be convinced that the mentioned optimization would be a good idea anyway.]
Now, the problem with the trapping semantics is that you have to check for overflow on every operation. This could be costly, but there are people working on making it more efficient. Seriously, this is the kind of thing that would be trivial if only architectures would help a little bit. Having the processor trap on overflow (either by having special trapping arithmetic instructions, or by having a special mode/flag which would enable trapping) would make this essentially costless, I think. Another nice-to-have would be a set of arithmetic instructions which treated the lower bits of words specially as flags, and trapped when the flags were not, say, all zeros. This could drastically reduce the cost of having fixnums and bignums in the language; the instructions would trap on non-fixnums and invoke a handler to perform the bignum arithmetic (or even find out that the operands are not numbers at all, and signal a dynamic type error), and perform the fast integer arithmetic when the operands had the fixnum flag. Alas, unfortunately we cannot just invent our own instructions, as we typically want to be able to use our programming languages on existing platforms. We could try to lobby Intel/AMD, though (as if).
(At this point I'm not really thinking about semantics for C anymore, just about the possible semantics for integers in a new programming language. Even if, say, Clang incorporated an efficient mechanism for trapping integer overflow, the standard would still say that signed overflow is undefined, so I'm not sure there is much hope for C in this situation.)
Hoje apresentei uma palestra-relâmpago no FISL sobre undefined behavior em C.
A palestra foi horrível, mas os slides ficaram decentes.
Update: Well, parece que existe um vídeo da palestra (minha parte começa aos 12:27). E foi menos pior do que eu tinha pensado...
Em algum momento do ano passado, por falta de coisa melhor para fazer, eu me parei a ler o manual da GNU libc. Não cheguei a ir muito longe, mas descobri um bocado de coisas interessantes no processo.
A scanf é uma das primeiras funções que vemos quando aprendemos C. Por isso mesmo, acabamos vendo só a funcionalidade básica para sobrevivência. Aí achamos que conhecemos a scanf e nunca mais nos preocupamos com ela. Ela possui um bocado de features interessantes, entretanto:
Uma conseqüência disso é que um programa do tipo while (x!=0) scanf("%d", &x);, ao se deparar com uma entrada do tipo foo, entra em loop infinito (pois a scanf nunca consegue ler o %d, não altera o valor de x, e o foo fica para sempre no buffer de entrada).
char *string;
scanf("%as", &string);
Existe uma função getline(char **linha, size_t *tamanho, FILE *stream), que recebe um ponteiro para um buffer inicial e seu tamanho, lê uma linha de tamanho arbitrário, realocando o buffer e atualizando o tamanho automaticamente, e retorna o número de caracteres lidos (que pode ser menor que o buffer, em princípio). Se linha for um ponteiro para um ponteiro nulo, o buffer inicial será alocado automaticamente. E.g.:
char *buf = NULL; size_t bufsize, bytes_read; bytes_read = getline(&buf, &bufsize, stdin);
Também existe uma função getdelim, que faz a mesma coisa, mas usa um delimitador diferente de \n como fim da "linha".
Essas funções não são parte do C padrão, e sim das extensões do GNU e de versões recentes do POSIX.
A glibc tem muita coisa (a versão em PDF do manual tem cerca de mil páginas). Vale a pena dar uma olhada no manual, nem que seja apenas para descobrir que tipo de recursos ela fornece, caso um dia você precise de algum deles.
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.