Habemus printk?

Trabalhando com funções com argumentos variáveis

No post anterior nós conseguimos resolver o problema dos construtores. Agora me sinto mais confiante para usar outros recursos da linguagem C++, como namespaces etc. Aproveitei e dei uma organizada no código, e conto com o compilador para me impedir coisas que não posso (como RTTI, exceções, etc).

O meu código está bem longe do que é cobrado no P2, mas precisamos de um arcabouço de ferramentas para nos ajudar quando precisarmos colocar a mão na massa de verdade. E na parte de Hints é dito “Adding print_int and print_str to your program can help you debug.”.

Eu não poderia concordar mais. Consigo me virar bem com o GDB, mas nem sempre o código que vejo em C bate com o que eu faria em assembly, especialmente por causa das otimizações (parâmetro -O2 no g++ e ld). Uma função que mostra endereços e números na tela ajudaria bastante.

E se vamos fazer print_int e print_str, por que não fazer logo um clone (humilde, acalme-se) da função printf? E como estamos em kernel mode, da então nomeada printk!

E se estou escrevendo um post para isso, significa que há coisas a serem ditas sobre. Se você fez faculdade de computação, é possível que você já saiba do que eu estou falando e isso não seja novidade para você. Caso contrário, é uma ótima oportunidade para você entender de verdade como funcionam as funções com parâmetros variáveis.

Não é coisa de outro mundo, mas se a linguagem não permitir, você não consegue fazer esse tipo de implementação. No Java por exemplo, o printf só apareceu na versão 1.5 e foi necessário fazer alterações na arquitetura da JVM para acomodar essa mudança¹.

Mas então, qual é a treta? Lembrando que tudo o que eu vou falar aqui vale para a arquitetura x86 de 32 bits.

A assinatura da função printk é a seguinte:

void printk(const char *, ...);

E um uso dessa função seria, por exemplo:

printk("\tTesting line feed! %c %x %o\n%s", 'X', 0xb8000, 0700, test);

Se você nunca viu uma printf antes, calma que vou explicar tudo. Observe que o primeiro parâmetro é obrigatoriamente uma string (no caso, um ponteiro de caracteres: "\tTesting line feed! %c %x %o\n%s"). Mas os outros parâmetros podem ser qualquer coisa: string, inteiro, caracteres. Como você programa uma função sem saber de antemão quais são os parâmetros, ou, pior ainda, como acessá-los?

Bom, primeiro veja que o primeiro parâmetro dita o número de parâmetros que virão a seguir, e mais do que isso, seu tipo. Os parâmetros no primeiro parâmetro são identificados pelo caractere % seguido do tipo. Então, em nosso exemplo, temos os parâmetros:

• %c é o caractere 'X'

• %x é o número hexadecimal 0xb8000

• %o é o número octal 0700

• %s é a cadeia de caracteres armazenada na variável test. No meu código, eu defini essa variável um pouco antes dessa forma: char test[] = {'t', 'e', 's', 't', '\0'};

Além desses parâmetros, ainda seria possível usar mais dois: %d para números decimais e %% para o imprimir caractere ‘%’. Isso tudo é arbitrário, eu que defini que seria dessa forma, mas tentei manter um padrão parecido com a função printf original do C. Na função original do C, por exemplo, há vários outros tipos, como o tipo %f para números de ponto flutuante.

Ok, e e o que fazemos com isso? Bom, o algoritmo básico é basicamente percorrer a string do primeiro parâmetro imprimindo os caracteres. Caso você encontre um caractere especial (digamos, \n, \t ou %) ai é necessário fazer coisas adicionais. Vamos para os mais fáceis primeiro.

Para o \t, defini que a tabulação equivale a quatro espaços em branco na tela. Então, se um \t for encontrado, nada mais simples do que imprimir ‘ ‘ quatro vezes:

...
    case '\t':
      for (int i = 0; i < 4; i++) {
        Screen::print_char(' ');
      }
      break;
...

Para o \n, estou usando o padrão do Linux. Significa que ele faz um Line Feed e um Carrier Return ao mesmo tempo. Dada uma posição do cursor na tela, se você somar a essa posição o número de colunas do display, você obrigatoriamente parará na próxima linha. Depois, basta recuar para a posição zero dessa linha (recua o número de caracteres igual a posição atual menos o resto da divisão da posição atual com o número de colunas. Fica assim:

util.cpp
...
    case '\n':
      Screen::line_feed();
      break;
...

screen.cpp
void Screen::line_feed() {
  current_position += NUM_COLUMNS;
  current_position -= current_position % NUM_COLUMNS;
  current_position = current_position % (NUM_ROWS * NUM_COLUMNS);
}

A última linha é necessária quando o cursor estoura o tamanho máximo do display, e no caso ele é recolocado na tela.

Fácil? Até agora não foi necessário acessar parâmetro nenhum adicional, além do primeiro. Vamos dificultar um pouco. Se encontrarmos um ‘%’, precisamos avançar e ver o próximo caractere, para identificar o tipo do parâmetro. E para desvendar o mistério sem mostrar o código, precisamos relembrar de algumas coisas no que diz respeito a ABI dos compiladores C/C++ para a arquitetura x86 de 32 bits:

1. A pilha cresce para baixo

2. Os parâmetros são empilhados na ordem inversa da declaração

3. Cada elemento na pilha ocupa 32 bits (4 bytes)

Com base nisso, vamos ver como está a pilha quando a função é invocada com os parâmetros do nosso exemplo na imagem abaixo.

Então, quando chamamos printk("\tTesting line feed! %c %x %o\n%s", 'X', 0xb8000, 0700, test);, o compilador:

1. Empilha o endereço da variável test

2. Empilha o valor 0700 (octal)

3. Empilha o valor 0xb8000 (hexadecimal)

4. Empilha o caractere ‘X’. Observe que o caractere ‘X’ só ocupa 1 byte. Ainda assim, 4 bytes são usados e o restante dos 24 bits mais significativos são zerados

5. Empilha o endereço da string "\tTesting line feed! %c %x %o\n%s"

6. Chama a função printk. A instrução call automaticamente empilha o endereço de retorno

7. Já na função printk, a primeira coisa que é feita é ajustar a pilha, ou seja criar o registro de ativação dessa nova função. A função empilha o endereço base da função que chamou (caller ebp → instrução push ebp) e altera seu valor para o mesmo do topo da pilha (callee esp → mov ebp, esp). Esse é o novo endereço base da pilha da função printk (ebp) e permanece inalterado até a função retornar. Já o ponteiro do topo da pilha (esp) pode ser alterado (e provavelmente vai, se houver variáveis locais ou chamadas de outras funções).

O segredo todo está em apontar para o endereço da única variável que temos certeza que existe, a primeira. Como o ebp agora é a nossa âncora da pilha, observe na imagem abaixo os endereços indexados pelo registrador ebp.

O segredo é portanto definir uma âncora no único parâmetro que temos certeza, o fmt address [ebp+8]. Ao percorrer a string fmt, toda vez que encontrarmos um novo % indicando ser um parâmetro, basta pegar essa âncora e incrementar 4 para ir voltando na pilha. Assim, partindo do fmt address [ebp+8], para chegar em ‘X’, incrementamos 4 e chegamos em [ebp+12]. Para chegar em 0xb8000, incrementamos 4 e chegamos em [ebp+16] e assim por diante.

O problema todo é que não conseguimos manipular diretamente a pilha em C, pelo menos não da forma como programamos. Inclusive, esse era o problema de não ter printf no Java antes da versão 1.5.

E como a gente resolve isso? Uma alternativa é trabalhar com o endereço da variável fmt. Note, não é o endereço para onde fmt aponta, mas sim o endereço do fmt em si. Isso porque o endereço dele, como vimos, é a pilha. Você pode trabalhar com aritmética de ponteiros para isso, vai funcionar. O cuidado que se precisa ter é que há alguns tipos de dados que podem ocupar mais que 4 bytes (um long long talvez?).

Para facilitar, há algumas macros que nos auxiliam nisso, chamadas variadic functions², que são macros declaradas no arquivo stdarg.h ou cstdarg para C++, que é o nosso caso. Faremos tal qual eu disse antes. Primeiro, declaramos a variável âncora.

std::va_list args;

Essas macros são independentes de arquitetura e por isso o *USO* deve ser tal qual eu vou mostrar aqui, mesmo que no fim das contas, algumas macros não façam nada na nossa arquitetura. Isso porque existem arquiteturas que guardam alguns parâmetros em registradores e outros na pilha, e há arquiteturas que possuem tantos registradores que é bem possível que a pilha nem seja usada. Dessa forma. se usarmos como manda o manual, não teremos problema. De qualquer forma, explicarei o que acontece na nossa arquitetura x86 32bit.

Voltando então, por trás dos panos, na nossa arquitetura, essa declaração expande para um char*³. Por enquanto, ela não armazena endereço nenhum. Precisamos agora obter nossa âncora:

va_start(args, fmt);

Essa macro, na nossa arquitetura, armazena o endereço de fmt na variável args, ou seja, temos em args o valor ebp+8.

Quando precisarmos do próximo elemento, basta chamar a macro va_arg, passando a âncora e o tipo do dado. Por exemplo, se o próximo parâmetro é um int, então:

n = va_arg(args, int);

Simples assim. A variável n conterá o dado solicitado, e a âncora é atualizada, e ficará pronta para o próximo parâmetro. Digamos que agora queiramos o próximo parâmetro, que é uma string. Assim, basta fazer:

char *s = va_arg(args, char *)

E o processo se repete. Quando tivermos percorrido todos os parâmetros na pilha, precisamos encerrar o processo chamando va_end(args);.

Na arquitetura x86, essa macro pode não fazer nada. Ou pode anular o valor de args propositalmente para que novos acessos a ele sejam inválidos. Isso vai depender do compilador. O fato é que, por questões de compatibilidade com outras arquiteturas e aderência ao padrão proposto, invocamos essa macro também. É inclusive bom para deixar o código legível e ver os limites da utilização dessa variável no código. O início da função fica como a seguir, e o restante é só repetição mas para tipos de dados diferentes.

void Util::printk(const char *fmt, ...) {
  std::va_list args;
...
  va_start(args, fmt);
  for (const char *c = fmt; *c != NULL; ++c) {
    switch (*c) {
    case '%':
      switch (*++c) {
      case 's':
        for (const char *s = va_arg(args, const char *); *s != NULL; ++s) {
          Screen::print_char(*s);
        }
        break;
...

A mágica perdeu o encanto? Excelente, essa é a ideia. Só tem um detalhezinho que ainda não abordamos: Se o parâmetro for um número (decimal, hexadecimal, octal, que seja), como a função imprime esse valor?

Não entendeu a pergunta? Eu te explico: Quando falamos de memória de vídeo nesse artigo AQUI, dissemos que passamos dois bytes para cada caractere: um para o caractere em si, outro para o atributo de cores de frente e fundo. Tudo muito bonito, mas estamos trabalhando com números de 32 bits (4 bytes) na pilha e nos registradores. Como encaixamos isso em um byte para escrever na memória de vídeo?

Mais do que isso, não podemos escrever o “valor” do caractere diretamente. Isso porque a memória de vídeo obedece a tabela ASCII. Se você quiser escrever o caractere zero (0) na tela, na verdade o valor do byte deve ser 48 ou 0x30.

Precisamos de um algoritmo para transformar um número de 32 bits em uma cadeia de caracteres que seja a representação desse número. Se você trabalha com computação, você já deve ter aprendido o algoritmo de mudança de base. Por exemplo, para transformar o número 159 em binário, basta aplicar divisões sucessivas pela base (na base binária, por 2) e recuperar os restos da divisão em ordem contrária. O mesmo serve para a conversão para hexadecimal ou octal. Observe a imagem abaixo.

Observe que para hexadecimal há uma pegadinha, que você já deve saber mas que não custa falar anyway. A base 16 indica que temos dezesseis símbolos que a representam. Contudo, só temos 10 símbolos para números: de 0 a 9. Portanto, para a base 16, quando temos dígitos que seriam de 10 a 15, pegamos emprestado do alfabeto as primeiras letras: 10 vira A, 11 vira B, e vai assim até 15 virar F.

Criamos então a função itoa (int to ascii). Essa função provavelmente está em toda função de biblioteca, de várias linguagens diferentes. Mas como essa função não é definida em ANSI-C e não é parte do C++ (apesar de ser suportada por alguns compiladores), nós criamos nós mesmos a função. Veja o código abaixo.

char *Util::itoa(int number, int radix, char *tmpBuff) {
  int i = 0;
  int j = 0;
  char tmp[100];
  if (number < 0) {
    tmpBuff[i++] = '-';
    number *= -1;
  }
  if (radix == 8 || radix == 16) {
    tmpBuff[i++] = '0';
  }
  if (radix == 16) {
    tmpBuff[i++] = 'x';
  }

  do {
    char c = number % radix;
    if (radix == 16 && c >= 10) {
      c = c + 'A' - 10;
    } else {
      c = c + '0';
    }
    tmp[j++] = c;
    number /= radix;
  } while (number > 0);

  while (--j >= 0) {
    tmpBuff[i++] = tmp[j];
  }
  if (radix == 2) {
    tmpBuff[i++] = 'b';
  }

  tmpBuff[i++] = '\0';
  return tmpBuff;
}

Começamos verificando se o número é negativo. Afinal, é importante o sinal de menos quando isso acontece certo? Se sim, adicionamos esse símbolo em um vetor temporário de caracteres. E depois, invertemos o número para prosseguir com o algoritmo.

Depois, verificamos a base. Por conversão, números na base octal recebem um zero antes, e números hexadecimais, 0x, e números binários possuem um b ao final (por isso seu teste é feito ao final).

Por fim, aplicamos o algoritmo da imagem acima. Pegamos o número inicial e obtemos o resto. Com esse resto, descobrimos o equivalente da tabela ASCII. Para os números normais de 0 a 9, caso eu some a esse número o valor de ‘0’ na tabela (48), vamos resultar com o caractere desejado. Por exemplo, caso eu deseje escrever o caractere 4 na tela, de posse do número 4, ao somar ‘0’ (portanto 48) resulta em 52. Veja que 52 decimal na tabela ASCII é igual ao caractere 4.

Para os caracteres hexadecimais, se o número for 12 por exemplo, não basta aplicar o mesmo raciocínio e somar ‘A’ (65). Isso vai resultar em 77 que na tabela ASCII é igual ao ‘M’. Basta tirar 10, que chegamos em 67 e ao caractere ‘C’, agora sim, correto.

Depois de armazenar o resto, atualizamos o número para o divisor da divisão anterior. E repetimos o processo até o número ser igual a zero.

Acabou? Não, observe a imagem, esse vetor de caracteres temporários está guardando os caracteres de trás pra frente. Somente quando o número chega a zero que temos o primeiro dígito. Então, basta percorrer o vetor de trás para frente e ir copiando os dados para o destino.

Pronto, terminamos. O resultado do código da função kernel.cpp abaixo

extern "C" void _start() {
  _init();
  GDT::install_gdt();

  char test[] = {'t', 'e', 's', 't', '\0'};

  Screen::set_colors(Screen::RED, Screen::YELLOW);
  Screen::clear_screen();
  Util::printk("Hello %s %d!\n", "Rodrigo", -42);
  Util::printk("\tTesting line feed! %c %x %o\n%s\n", 'X', 0xb8000, 0700, test);
  Util::printk("%d in binary is %b\n", 75, 75);

  while (true) {
    /* BUSY LOOP*/
  }

  /*If it reaches here, something very wrong happened...*/
  _fini();
}

resulta em

Essa nem foi tão difícil, até porque tem pouca coisa de Sistemas Operacionais ou kernel. Os próximos posts voltarão para o tópico de interesse. O código até o momento pode ser visto AQUI. Até mais!

1. https://en.wikipedia.org/wiki/Printf

2. https://en.cppreference.com/w/cpp/utility/variadic

3. https://en.cppreference.com/w/cpp/utility/variadic/va_list