Ponteiros!

Outro dia no trabalho resolvemos brincar com ponteiros, não que o código que resultou da brincadeira seja algo bom, mas foi divertido. Basicamente tinhamos uma função que traduzia uma string interna passada para a string que utilizariamos em tela, software foi crescendo e mais traduções eram necessárias para a mesma string.

Então aos exemplos, do que tinhamos, da brincadeira que fizemos com os ponteiros e o que seria a melhor solução para o código. Antes algumas definições, a estrutura que contém as strings é a seguinte, basicamente um mapa 1 pra n:

enum {
	KERNEL = 1,
	WEB,
	CLI
};

struct test {
	int idx;
	char *kernel;
	char *web;
	char *cli;
};

struct test example[] = {
	{.idx = 0, .kernel = "eth0", .web = "Ethernet 0", .cli = "ethernet0" },
	{.idx = 1, .kernel = "eth1", .web = "Ethernet 1", .cli = "ethernet1" },
	{.idx = 2, .kernel = "eth2", .web = "Ethernet 2", .cli = "ethernet2" },
	{.idx = 3, .kernel = NULL, .web = NULL, .cli = NULL}
};

A versão original da função que procurava pela string correta era algo parecido com:

char *get_str_for_v1(const char *eth, enum str_type type)
{
	char *rtn = NULL;
	int i;
	
	switch (type) {
	case KERNEL:
		for (i = 0; i < sizeof (example); i++) {
			if (strcmp(eth, example&#91;i&#93;.kernel) == 0) {
				rtn = example&#91;i&#93;.kernel;
				break;
			}
		}
		break;
	case WEB:
		for (i = 0; i < sizeof (example); i++) {
			if (strcmp(eth, example&#91;i&#93;.kernel) == 0) {
				rtn = example&#91;i&#93;.web;
				break;
			}
		}
		break;
	case CLI:
		for (i = 0; i < sizeof (example); i++) {
			if (strcmp(eth, example&#91;i&#93;.kernel) == 0) {
				rtn = example&#91;i&#93;.cli;
				break;
			}
		}
		break;
	}
	
	return rtn;
}
&#91;/sourcecode&#93;

O que é obviamente muito feio! Com excesso de código repetido, péssimo de ler e dar manutenção. Vendo esse código propus o desafio de escrever a mesma função com um <code>for</code> só. Meu colega de trabalho resolveu usar ponteiros pra resolver isso, calculando o offset de cada um dos membros da estrutura e recuperando o ponteiro da string a partir do offset. Claro, isso parece muito simples de se fazer... mas na hora de escrever o código, demorou bem mais do que imaginavamos, mas foi bastante divertido entender como funcionam os casts em C.

O resultado foi o seguinte código, as macros eu adicionei para facilitar a leitura do código, mais sobre elas daqui um pouco...

#define member_offset(type, member) \
			((unsigned long)(&((type *)0)->member))
#define get_member_by_offset(ptr, type, offset) \
			((type *)((void *)(ptr) + offset))

char *get_str_for_pointer_fun(const char *eth, enum str_type type)
{
	int i;
	unsigned long offset;
	
	switch(type) {
	case KERNEL:
		offset = member_offset(struct test, kernel);
		break;
	case WEB:
		offset = member_offset(struct test, web);
		break;
	case CLI:
		offset = member_offset(struct test, cli);
		break;
	}
	
	for (i = 0; i < sizeof (example); i++) {
		if (strcmp(eth, example&#91;i&#93;.kernel) == 0) {
			return *get_member_by_offset(&example&#91;i&#93;, char *, offset);
		}
	}
	
	return NULL;
}
&#91;/sourcecode&#93;

Com certeza não é a melhor implementação possível, talvez seja a mais complexa de se entender, especialmente se não for utilizada uma macro para esconder a implementação. Mas é uma implementação divertida, ou pelo menos foi divertido tentar achar a combinação correta de ponteiros para gerá-la.

E finalmente o código que eu julgo o mais aceitável:
&#91;sourcecode lang="c"&#93;
char *get_str_for_v2(const char *eth, enum str_type type)
{
	int i;

	for (i = 0; i < sizeof (example); i++) {
		if (strcmp(eth, example&#91;i&#93;.kernel) == 0) {
			switch (type) {
			case KERNEL:
				return example&#91;i&#93;.kernel;
			case WEB:
				return example&#91;i&#93;.web;
			case CLI:
				return example&#91;i&#93;.cli;
			}
		}
	}
	
	return NULL;
}
&#91;/sourcecode&#93;

<h2>Macros</h2>
Bom, disse que ia explicar o funcionamento das duas macros utilizadas, então recapitulando elas:

#define member_offset(type, member) \
			((unsigned long)(&((type *)0)->member))

#define get_member_by_offset(ptr, type, offset) \
			((type *)((void *)(ptr) + offset))

A macro member_offset calcula o offset de um membro qualquer de um estrutura. Para fazer isso, ela dá um cast para um ponteiro do tipo da estrutura requerida ao valor 0. O que parece estranho a princípio, mas faz todo o sentido! Do ponteiro para zero até o membro requerido da estrutura existem os n bytes que representam o offset em memória do início da estrutura até o membro.

Munido do valor do offset, podemos então recuperar a estrutura que se encontra naquele offset utilizando a macro get_member_by_offset. Obviamente é necessário sabermos qual o tipo de dado que se encontra naquele offset! Então a partir do ponteiro (endereço) da estrura que queremos acessar podemos somar o offset do membro requerido. Mas só somar o offset não resolve, é necessário dar os casts apropriados.

Como queremos um que o endereço calculado (ponteiro original + offset) seja um ponteiro, é necessário indicar isto ao compilador, colocando um * no cast do cálculo. Além disso, é necessário indicar que tipo de ponteiro estamos recuperando naquele endereço, portanto o cast vira (type *). No exemplo, o cast é (char **) indicando corretamente que naquele endereço encontra-se uma string.

Esse mesmo método de recuperar um membro de uma estrutura é utilizado na implementação de listas no kernel do linux. A macro definida é um pouco diferente, uma vez que ela realiza estas duas operações de uma só vez, mas a explicação do seu funcionamento é a mesma! Segue a sua implementação:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Basicamente o que este código faz é recuperar o ponteiro para a estrutura a partir de um membro qualquer dela. No caso das listas, o membro utilizado para recuperar a estrutura original é o struct list_head. Com isso, é possível utilizar diversos struct list_head numa mesma estrutura, adicionando ou não a estrutura alocada a uma das listas.

Análise Estática com LLVM

LLVM é uma coleção de tecnologias de compiladores (ou algo assim, é que eles usam para se autodefinir), mas esse não é o ponto mais interessante – apesar de existirem diversos subprojetos bastante interessantes, a parte mais legal do LLVM é o subprojeto Clang Static Analyzer – ok, ele é parte do subprojeto Clang na verdade. O Clang utiliza as tecnologias oferecidas pelo LLVM para implementar um compilador completo, com algumas vantagens é extremamente rápido e dá ótimas mensagens de erro.

Meu interessante por análise estática surgiu primeiro quando eu ainda brincava de descompilar programas e entender o que eles faziam, afinal, quando se lê um código sem executá-lo estamos fazendo uma análise. Mas cansei de ler ASM, passei a programar mais e fui atrás de algo que fizesse algo parecido com o que eu fazia. Descobri várias ferramentas que fazem algum tipo de análise estática: lint, sparse e o clang. Sim, lint aquele programa velhão que verificava se um código C era bem formado fazia nada mais do que uma análise estática do código – ok, sem grandes interpretações do que o código fazia. O Sparse é um parser semântico para C, faz mais ou menos a mesma coisa que o lint fazia, mas é um código mais novo, originalmente escrito pelo Linus Torvalds. E finalmente há o Clang…

Clang Static Analyzer

Primeiro passo para testar e usar o Clang é obter os arquivos fonte e compilá-lo, pelo menos não achei uma versão para download (ok, há uma versão para Mac OSX). Há um bom passo-a-passo aqui. Em linhas gerais:

cd tools
svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
cd llvm/tools
svn co http://llvm.org/svn/llvm-project/cfe/trunk clang
cd ..
./configure
make
make install

Atualmente o Clang não instala os scripts scan-build e scan-view, então é necessário copiá-los manualmente. Instalei os scripts em $HOME/bin/, pois já tinha esse caminho no meu path. scan-build é a ferramenta responsável por criar o ambiente necessário para executar o Clang. Com a ferramenta instalada é hora de utilizá-la!

Ah, ele também tem um suporte bem legal a Objective-C, tanto para programas para Mac quanto para aplicativos de iPhone / iPad! Mas, ainda não testei essa funcionalidade.

Usando o Clang

Precisamos de um código com alguns problemas para testar o clang. Resolvi reutilizar o código do post sobre valgrind. Ok, não é o melhor código para demonstrar as funcionalidades do clang, mas é suficientemente bom. Há quatro bugs naquele código, todos foram corretamente identificados pelo valgrind. Quantos desses erros o Clang conseguirá identificar? Usando o scan-build, habilitando verificações experimentais, obtemos:

pedro@urubu:~/code$ scan-build --experimental-checks gcc -g -O1 -o valtest valtest.c
valtest.c:13:2: warning: Access out-of-bound array element (buffer overflow)
        x[5] = 'a';
        ^~~~
valtest.c:20:2: warning: Value stored to 'x' is never read
        x = malloc(5 * sizeof(char));
        ^   ~~~~~~~~~~~~~~~~~~~~~~~~
valtest.c:20:4: warning: Allocated memory never released. Potential memory leak.
        x = malloc(5 * sizeof(char));
        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
3 warnings generated.
scan-build: 3 bugs found.
scan-build: Run 'scan-view /tmp/scan-build-2010-06-01-4' to examine bug reports.

Dentro de /tmp/scan-build-2010-06-01-4 há um relatório em html com cada erro encontrado, basicamente o código fonte anotado. Um dos erros acima gerou o seguinte relatório:

clang-report

Exemplo de relatório gerado

Resultado, o Clang encontrou três problemas no código, sendo que dois são na mesma linha de código – gerados pelo mesmo problema. Então dos quatro bugs existentes no código a ferramenta identificou dois… nada mal para uma ferramenta que só analizou o código fonte! Claro, há outros bugs que a ferramenta irá identificar e o valgrind não. There is no silver bullet, mas várias ferramentas utilizadas em conjunto conseguem aumentar bastante a qualidade do código escrito.

Duas coisas para terminar este post, não utilizei o clang para gerar código, somente para fazer análise do código fonte, mas isso é perfeitamente viável. E para completar, se formos utilizar o Clang junto a um projeto com autotools, fariamos:

pedro@urubu:~/code/myproject$ scan-build ./configure
pedro@urubu:~/code/myproject$ scan-build make