Detalhes importantes sobre aritmética inteira

Em uns artigos eu falei pra vocês sobre algumas armadilhas relativas ao uso de ponto flutuante. A ideia de que você lida com valores no domínio dos números “reais”, por exemplo, deve ser compreendida com muito cuidado… Bem… e não é que existem erros de interpretação por ai a respeito da aritmética inteira também?

Vejamos uma otimização muito comum:

#include <stdio.h>

void main( void )
{
  int a = -1;
  int b = a >> 1;
  int c = a / 2;

  printf("%d, %d\n", b, c );
}

Olhando para o código acima o leitor pode supor que ambos os valores impressos serão iguais. Afinal, parece que estamos apenas dividindo por 2 o valor de a, em ambas as expressões. No entanto, em arquiteturas onde existe a distinção entre shifts lógicos e shifts aritméticos, o resultado em b será -1, enquanto o resultado em c será, necessariamente, zero!

Ambas as expressões continuam usando shifts, por debaixo dos panos. Uma implementação possível, por parte do compilador, poderia ser essa:

main:
  ...
  mov  edx,-1   ; EAX = a = -1

  mov  ecx,edx
  sar  ecx,1    ; ECX = b = (a >> 1)

  mov  eax,edx  ; EDX = c (EAX é um temporário aqui).
  shr  eax,31
  add  edx,eax  ; if (b < 0) c++
  sar  edx,1    ; c >>= 1
  ...

Esse pequeno shift lógico e a adição “condicional” corrigem o problema do shift aritmético com relação ao valor -1. Note que todos os outros valores inteiros negativos continuarão funcionando corretamente.

Isso quer dizer que devemos tomar muito cuidado com deslocamentos para a direita. Afinal, a própria especificação da linguagem C (leia a ISO 9989:1999 em diante) afirma que deslocamentos para a direita de objetos integrais sinalizados é “dependente de implementação”.

Outro problema que é vastamente ignorado é o calculo de valores absolutos de um valor inteiro. A libc implementa a função abs() que deveria ser usada para esse propósito, mas é bem comum ver fragmentos de código como o abaixo:

int _abs( int x )
{
  if ( x < 0 )
    x = -x;

  return x;
}

Isso parece correto, mas considere o seguinte: Se tentarmos inverter o sinal do valor 0 (zero), obteremos o mesmo zero. Isso pode ser interpretado de duas maneiras. Ou o valor zero é “especial” e não tem sinal, ou existem dois zeros diferentes (um +0 e um -0). No caso dos valores inteiros sinalizados o msb define o sinal do valor… Assim, -0 não existe e, de fato, zero é um valor com características especiais. Mas, vamos assumir que ele possa ser interpretado como valor sinalizado, de acordo com a função acima… Existe outro valor com a mesma característica (ou seja, que possa ser negativo e positivo ao mesmo tempo)?

No caso do tipo int, o msb é o bit 31 e, como aprendemos sobre “complemento 2”, para obter o valor representado temos que inverter todos os bits e somar 1… 0xffffffff, por exemplo, representa -1. Mas, em 32 bits, existe um valor diferente de zero especial: 0x80000000 (o bit 31 setado e os demais zerados). Ao invertê-lo e somar um obtemos o mesmo valor, ou seja, existe um -2^{31} e um +2^{31}. Mas, como o msb é quem define o sinal, ao informar o argumento 0x80000000 para x, na chamada da função acima, obteremos o mesmíssimo valor.

A rotina acima, obviamente está errada! Já que o valor absoluto de -2147483648 não pode ser o mesmo valor! Infelizmente isso não tem uma solução fácil porque, com 32 bits, usando um objeto integral sinalizado, não há como obter o valor positivo oposto a -2147483648, dada a assimetria dos valores extremos dessa representação.

Minhas tentativas de otimizar o checksum16

Existe uma recomendação (RFC) que mostra como o checksum de 16 bits deve ser calculado para pacotes IP (por exemplo). No projeto T50 já fiz várias tentativas malsucedidas de otimizar a rotina, tentando usar uma métrica simples: Quantos ciclos de clock estão sendo gastos para “somar” cada byte do buffer? Aqui vou mostrar como o cálculo funciona, como otimizá-lo, erros de cometi e, depois de acertá-los, porque não o fiz…

A referida RFC é a 1071 (que pode ser obtida aqui). Essencialmente, o algoritmo deve agrupar os bytes em words (16 bits) e somá-los, juntamente com os carry-outs resultantes das somas parciais (o que é chamado de soma em complemento um). No contexto dos protocolos de rede a soma final têm todos os 16 bits invertidos e armazenados no pacote, de forma que, se um novo cálculo de checksum for feito com esse novo pacote, o resultado final será exatamente zero. A rotina original (desconsiderando o endianess) pode ser vista na RFC. A apresento com ligeira modificação abaixo…

Para efeitos de teste, da mesma maneira que citada na RFC, consideremos um buffer contendo os seguintes bytes:

uint8_t buffer[] = {
  0x00, 0x01, 0xf2, 0x03, 0xf4, 0xf5, 0xf6, 0xf7
};

Ao somar cada par de valores, temos:

  0001
  f203
  f4f5
+ f6f7
───────
 2ddf0

O ‘2’, além dos 16 bits inciais veio dos carry-outs das somas parciais e, portanto, deve ser somado aos 16 bits infereiores. O checksum resultante é 0xddf2. Note que essa soma ai em cima foi feita usando o modelo big endian. Em little endian a única coisa que muda é que devemos trocar os bytes de posição no final das contas:

  0100
  03f2
  f5f4
+ f7f6
───────
 1f2dc

O resultado, depois de adicionado os carry-outs do resultado, é 0xf2dd que, depois do swap, dá exatamente 0xddf2.

O buffer tem exatamente o tamanho de 4 words, mas se retirarmos 0xf7 do buffer teremos um tamanho impar, em bytes. Neste caso, note que em big endian o valor da última word deverá ser 0xf600, não 0x00f6. Assim, esse último byte já estará na posição correta em processadores Intel (por exemplo), mas deverá ser colocada no MSB em arquiteturas que lidam com big endian.

A rotina final fica assim:

uint16_t cksum16( void *buffer, size_t size )
{
  uint16_t *ptr;
  uint32_t sum;

  sum = 0;
  for ( ptr = buffer; length > 1; length -= 2 )
    sum += *ptr++;

  if ( length > 0 )
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    sum += *( uint8_t *)ptr;
#else
    sum += ( ( uint16_t ) *( uint8_t *)ptr ) << 8;
#endif

  while ( sum >> 16 )
    sum = ( sum & 0xffffU ) + ( sum >> 16 );

  return ~htons(sum);
}

A rotina acima consegue calcular o checksum16 com a performance aproximada de 1,8 ciclos de clock para cada byte do buffer (para buffers grandes, como veremos mais adiante). Isso parece ser muito bom, mas, e se pudéssemos realizar o cálculo a cada 32 ou 64 bits por vez (ou até 128 ou 256, no caso de usarmos SSE ou AVX)? Isso pode ser feito facilmente, desde que os sub blocos de 16 bits do resultado final sejam somados de acordo com as mesmas regras que vimos até agora. Vejamos como a mesma sequência, em little endian, se comporta (isso também está na RFC):

  03f20100
+ f7f6f5f4
───────────
  fbe8f6f4   ⇒  fbe8 + f6f4 = 1F2DC

O valor final é o mesmo resultado que obtivemos, antes do swap, no exemplo para little endian anterior… O mesmo princípio da soma dos carry-outs nas somas parciais do buffer (em 32 bits) aplica-se aqui. No exemplo acima não houve carries na primeira soma ou, temos carry-outs igual a zero.

Em teoria, realizar a soma com grupos maiores pode ser uma boa ideia, mas há mais cuidados a serem levados em conta:

  1. Se o buffer não contiver uma quantidade de bytes múltipla do tamanho do bloco inicial, restarão de 1 a n-1 bytes finais (onde n é a quantidade de bytes do bloco parcial). Exemplo: Se tivermos um buffer de 9 bytes e usando somas parciais por dword (32 bits), sobrará 1 bytes final. Mas, se tivermos um buffer com 11 bytes, teremos 3;
  2. A mesma preocupação com padding que tivemos com 16 bits teremos que ter com mais bits, e graças a consideração acima, isso fica um pouquinho mais difícil;
  3. A variável de acumulação deve ser, necessariamente duas vezes maior, em tamanho, do que as somas parciais. Se usarmos somas parciais de 32 bits teremos que acumulá-las em uma variável de 64 para podermos separar os carry-outs.

Somente essas considerações tornam difícil melhorar a performance da rotina original, especialmente no que concerne à segunda e terceira… Mas, é claro, não é “impossível”… Vamos tentar…

Se formos usar dwords como limite superior de tamnho, temos que contar quantas existem no buffer. Isso é fácil, basta desconsiderar os 2 bits inferiores de size. Da mesma maneira, os 2 bits inferiores de size nos dizem se temos bytes extras no final do buffer:

A rotina para little endian fica assim:

uint16_t cksum16( void *buffer, uint32_t size )
{
  uint32_t *ptr;
  uint64_t sum;
  uint32_t dwcount;
  int wextra, bextra;

  // Quantas DWORDs temos?
  dwcount = size >> 2;

  // Temos uma WORD e/ou um BYTE extra?
  size &= 3;
  bextra = size & 1;  // byte?
  wextra = size >> 1; // word?

  // Soma as dwords.
  sum = 0;
  ptr = buffer;
  while ( dwcount-- )
    sum += *ptr++; 
  
  // Se temos uma word extra...
  if ( wextra )
  {
    sum += *( uint16_t *)ptr;

    buffer = ptr;   // Atualiza ptr.
    buffer += 2;
    ptr = buffer; 
  }

  // Se temos um byte extra...
  if ( bextra )
    sum += *( uint8_t *)ptr;

  // Interpreta tudo acima dos 16 bits inferiores
  // como carry-outs.
  while ( sum >> 16 )
    sum = ( sum & 0xffffU ) + ( sum >> 16 );

  return ~htons(sum);
}

Obviamente dá para melhorar a rotina, mas supostamente temos agora um avanço de performance. Se medirmos com o “medidor de ciclos do homem pobre” observamos que a coisa não é tão significativo assim.

Num dos PCs que tenho acesso, consegui aumento de 38% na performance (238 ciclos, contra 388 da rotina original), no modo x86-64… 38% não é lá grandes coisas, considerando que a rotina original já é bem rápida (388 ciclos num processador de 3.4 GHz nos dá cerca de 114 μs, contra os cerca de 70 μs da nova rotina). Implementar a rotina para obter uma qword de cada vez também não melhora lá muito. Obtive 306 ciclos, uma melhora de 20% em relação à rotina original, mas uma piora de 28% em relação à segunda! O motivo da piora da terceira rotina (que não vou nem colocar aqui) é que a acumulação exige 128 bits e não estamos lidando, necessariamente, com SSE aqui. Mesmo que usássemos, até onde sei, não existem instruções para adição de dois valores inteiros de 128 bits disponível…

Repare também que a afirmação que fiz anteriormente sobre a métrica de 1.8 ciclos por byte “não bate”, não é? Acontece que isso só é válido para buffers grandes. Com buffers pequenos o gasto de tempo das instruções fora dos loops têm peso no tempo gasto.

Como regra geral, se não consigo aumentar a performance em, pelo menos, 100%, não vale a pena a otimização. Especialmente porque existem outros fatores não considerados aqui:

  1. Cache misses
  2. Alinhamento do buffer
  3. Overrun da maneira como acumulamos os carry-outs

No caso do T50, a rotina do módulo que chama cksum() já colocou os dados do buffer no cache L1 (muito provavelmente) e, por isso, cache misses não é uma preocupação. Mas o alinhamento do buffer pode consumir alguns ciclos (pouco provável). O problema real é o terceiro item.

Seria mais “fácil” acumular os carry-outs em cada iteração do loop inicial, via o par de instruções ADD/ADC que, em teoria, eliminaria o loop final… Mas isso só pode ser conseguido em assembly, já que, em C, as operações aritméticas integrais são, em essência, carryless

Existe também o problema das arquiteturas. Na plataforma Intel posso realizar algumas otimizações que não estejam disponíveis em outras e vice-versa. A ideia do T50 é compilá-lo para qualquer uma das 24 (tem mais?) plataformas em que o Linux foi adaptado, de Intel x86 até Intel IA-64, MIPS, ARM, Atmel AVR, Motorola 68000, Power PC, SPARC etc… Para isso a segunda rotina pode até ser usada, mas aumentar a granulidade do loop inicial para além de 32 bits pode ser problemático para a performance nessas outras plataformas…

O erro de cometi…

Achou que eu ia deixar isso de fora? Na minha tentativa de otimizar a rotina original cometi o erro de pensar que a ordem dos bytes somados não interessava (de fato não interessa, se estivéssemos somando bytes!), mas a rotina é feita para somar words. O erro que cometi antes foi obter o byte do início do buffer caso tivéssemos um tamanho ímpar, em bytes e só depois acumular words. Isso simplificava a rotina, mas ao mesmo tempo a tornava errada… That’s it!

Dica: Filtrando pacotes de consulta de nomes usando iptables

Recentemente tive que filtrar uma série de consultas a um nameserver usando o módulo “string” dos filtros de matching do iptables. A minha primeira tentativa foi essa:

$ iptables -t mangle -A INPUT -p udp --dport 53 \
           -m string --algo bm --string 'exemplo.com' \
           -j DROP

A ideia aqui é não deixar passar nenhum pacote UDP contendo a substring “exemplo.com” destinada para a porta 53. Só que isso não funciona!

O detalhe  é que os nomes consultados são montados de forma diferente: O resolver substitui os ‘.’ pela quantidade de caracteres que o seguem (e, é claro, a primeia parte do nome também tem esse prefixo!)… Um nome como “www.exemplo.com” é montado como “\x03www\x07exemplo\x03com\0” (usando a notação da linguagem C aqui, para facilitar).

Isso pode ser facilmente percebido usando tcpdump:

myhost.local # sudo tcpdump -i eth0 -tX 'host myns.local && dst port 53'
listening on eth0, link-type EN10MB (Ethernet), capture size 262144 bytes
IP myhost.local.56114 > myns.local.53: 5291+ [1au] A? www.exemplo.com. (56)
	0x0000:  4500 0054 5371 0000 4011 8cfd 0a20 0c17  E..TSq..@.......
	0x0010:  0af3 7901 db32 0035 0040 9a7c 14ab 0120  ..y..2.5.@.|....
	0x0020:  0001 0000 0000 0001 0377 7777 0765 7865  .........www.exe
	0x0030:  6d70 6c6f 0363 6f6d 0000 0100 0100 0029  mplo.com.......)
	0x0040:  1000 0000 0000 000c 000a 0008 c0d9 832a  ...............*
	0x0050:  4f3c 534e                                O<SN

Em outro processo fiz apenas a consulta:

myhost.local $ dig @myns.local www.exemplo.com

Fica claro que precisamos de um jeito de levar em conta esses “caracteres especiais”. Para esse tipo de filtragem é necessário o uso da opção “--hex-string“, ao invés de “--string“:

$ iptables -t mangle -A INPUT -p udp --dport 53 \
           -m string --algo bm \
           --hex-string '|07|exemplo|03|com|00|' \
           -j DROP

Aqui, os caracteres cercados por ‘|’ são valores em hexadecimal… Dessa forma, qualquer sufixo “exemplo.com” será filtrado. Note que nomes como  “xexemplo.com” e “exemplo.com.br” não serão filtrados. Trata-se apenas de um teste de substring onde cada “pedaço” é testado precisamente… Podemos cercar o primeiro caso (*exempplo.com) não usando o “|07|” inicial. Mas, ai, você corre o risco de filtrar consultas legítimas…

Também deve ter reparado na opção “--algo bm“. Isso é importante… O filtro permite o uso de um dos dois mais rápidos algoritmos de teste por substring: Boyer-Morre e Knuth-Morris-Pratt sob as siglas “bm” ou “kmp”. Ambos são bastante eficientes: o algoritmo de Knuth-Morris-Pratt tende a ser mais performático em casos mais extremos. Ambos têm performance similar se a substring não se encontra na string procurada, mas o algoritmo kmp é um pouco melhor que o bm quando a substring está lá (O(n+m) contra O(nm) do Boyer-Moore). Acontece que o algoritmo kmp tem um pequeno overhead que, para pequenas strings, não compensa o uso. Por isso o algoritmo Boyer-Moore é o preferido…

É interessante notar, mesmo que nada tenha a ver com esse artigo, que a função strstr() da GNU libc implementa o algoritmo Knuth-Morris-Pratt.

PS: É interessante aplicar o filtro desejado tanto para UDP quanto para TCP!

A difícil arte de contar ciclos…

Postei aqui, para vocês, minha simples implementação de um “contador de ciclos do homem pobre” (aqui). É uma pequena ferramenta para contar os ciclos gastos de rotinas que deve ser usado com algum cuidado. Em primeiro lugar, qualquer um poderá observar que as contagens não são muito coerentes quando fazemos várias medidas e, por outro lado, ele não leva em consideração muitas das “melhorias” que o processador implementa para acelerar as instruções.

No artigo anterior falei sobre “gastar tempo” e, para isso, fiz-de-conta que a contagem de ciclos de algumas rotinas podem ser determinadas corretamente. Isso não é bem verdade. Existem efeitos que não devem ser desconsiderados, especialmente em sistemas operacionais que implementam multithreading:

Caches

Processadores modernos da família Intel implementam 3 níveis de cache, chamados L1, L2 e L3. Os caches existem para acelerar o acesso à memória… Os pentes de memória do seu computdor são lentos, em comparação com a frequência em que seu processador trabalha, internamente e, por causa disso, é conveniente ter memórias “mais rápidas” dentro dele e, às vezes, fora.

O que não vale à pena é ter memória do sistema (RAM) rápidas, por motivos de custo. Memórias rápidas são caras e costumam esquentar pra caramba…

O cache L1 existe para cada processador lógico no seu “pacote” (é assim que é chamado o chip do “processador”) e tem apenas 64 KiB de tamanho (de novo, por processador lógico!) e é dividido em L1i e L1d. A primeira divisão é o cache de instruções e a segunda, de dados… Como todo cache é dividido em linhas de 64 bytes, cada uma dessas divisões têm 512 linhas… Quando um endereço é acessado, via, por exemplo:

mov eax,[myvar]

Onde myvar é o endereço do dado que queremos colocar em EAX, o processador verifica se a linha contendo esse endereço existe no cache L1d. Para isso, toda linha contém uma “etiqueta” (tag) que é o endereço inicial da linha, onde os 6 bits inferiores são zerados. Isso é a mesma coisa que dizer que cada linha é “alinhada” de 64 em 64 bytes… Se a tag existe, então o dado é lido e colocado em EAX e a instrução é executada muito rapidamente (veremos mais, adiante). Mas, se a linha com o tag não existe no cache L1d então o processador verifica se ela existe no cache L2.

Meu processador tem cache L2 de 256 KiB, o que nos dá 4096 linhas… No caso anterior, se a tag existe no cache L2 então ela é copiada para o cache L1d, mas, se o cache L1d estiver cheio (todas as linhas em uso), uma das linhas de L1d precisa ser “despejada” no cache L2 antes da cópia… Se a linha procurada inicialmente não estiver em L2, então a procura é feita em L3 (que, na minha máquina tem 8 MiB ou 131072 linhas) e o mesmo processo ocorre…

No caso de cache miss no L1d, o processador vai gastar uns 4 ciclos de clock na cópia de L2 para L1. No caso de cache miss também em L2, uns 12 ciclos e no caso de ocorrer no L3, uns 36 ou mais (dependo da memória). Esses são valores relacionados a caches que ainda possuem espaço disponível para preenchimento de linhas, os valores podem aumentar em uns 200 ciclos no caso de L3 estar cheio e ter que escrever na memória para liberar o espaço de uma linha.

Só que, não é apenas para dados que isso ai vale… lembra-se do L1i? O seu programa também fica nos caches! Se a próxima instrução a ser executada não estiver em L1i o mesmo processo ocorre e as mesmas penalidades, no caso de cache misses. Ou seja, a instrução acima pode ser executada em 0 ciclos (sim! zero! depois explico) até uns 400 ciclos ou mais, dependendo do estado dos caches.

Reordenação das instruções

Antes de serem executadas, um conjunto de instruções são carregadas para a pipeline de execução do processador onde elas são reordenadas. Isso é feito porque o processador possui unidades de execução especializadas. Por exemplo, instruções aritméticas e lógicas são executadas numa unidade diferente da que executa instruções que fazem saltos… Em arquiteturas como a Haswell, temos 8 dessas unidades especializadas, chamadas portas.

Isso permite que certas instruções sejam executadas em paralelo, desde que não existam dependências entre elas. Por exemplo, as duas instruções abaixo jamais poderão ser executadas em paralelo:

mov ebp,esp
mov eax,[ebp-4]

Por quê? A segunda instrução depende de EBP que está sendo modificado na primeira.

O processador tenta compensar isso mudando a ordem das instruções para permitir que o maior número possível de portas estejam em uso num determinado momento. Assim, ele vai tentar colocar instruções independentes para executar numa única tacada. Acontece que esse buffer é limitado, mesmo que esse limite seja grande! Na arquitetura Haswell cabem 192 instruções no buffer de reordenação.

Este é um dos motivos pelo qual uma instrução pode ser executa em “zero” ciclos. O tempo gasto será da instrução mais lenta do bloco que está sendo executado independentemente nas portas.

Previsão de saltos

A reordenação de até 192 instruções (Haswell) gera um problema com os saltos… Existem dois tipos de saltos que têm dependências: Saltos condicionais, que dependem do estado de um flag, e Saltos indiretos, que dependem do conteúdo de um registrador:

jnz .loop    ; salto condicional (salta se ZF=1).
jmp rbx      ; salto indireto (depende de RBX).
jmp [rax]    ; salto indireto (depende de RAX e 
             ; do valor contido no endereço dado por RAX).

O mesmo se aplica a instrução CALL quando ao saltos indiretos.

Nesses casos, o processador não tem como saber para onde o salto será feito de antemão. A solução é manter um buffer chamado BPB (Branch Prediction Buffer) que contém como tag um endereço para onde os saltos condicionais serão feitos e um flag dizendo se o salto foi realizado ou não, da última vez que instrução foi executada…. Assim, o processador assume que, da próxima vez, o salto será executado e a reordenação das instruções é feita levando-se esse detalhe em consideração.

Se o que o processador assumiu estiver errado, então ele volta atrás, recupera o estado anterior à previsão e tenta de novo… Isso, é claro, atrasa consideravelmente o processamento.

Note que falei dos saltos condicionais… Os saltos incondicionais diretos são sempre assumidos como feitos (não dependem da BPB) e os saltos indiretos são sempre assumidos como não feitos na primeira execução da instrução (onde a tag ainda não esteja no BPB)…

Temos mais um problema ai: Se dois saltos condicionais dentre aquelas 192 instruções, no buffer de reordenação, saltarem para o mesmo lugar, a previsão será feita para as duas, independente das condições… Por isso, é necessário que duas instruções saltem para o mesmo lugar para evitar gastos de ciclos inúteis…

Interrupções e Memória Virtual

O caso das interrupções é óbvio: Seu processador pode “pausar” o processamento de uma rotina para atender a um pedido de interrupção externo (teclado, mouse, ..) ou não… O caso das exceções é parecido, mas uma delas é mais sutil: Page Faults.

Uma página é um bloco de 4 KiB (existem páginas maiores, mas este é o default) e sua memória física é dividida em páginas contíguas. Cada página pode ser mapeada num desses blocos de 4 KiB da memória física ou pode ser mapeado para lugar nenhum (é uma analogia com NULL, em C). Isso significa que o endereço de uma página (tanto físico quando nesse “mapeamento”) tem seus 12 bits inferiores zerados (2^{12}=4096).

De movo grosseiro, um endereço “linear” (que será traduzido para um endereço “físico”), numa arquitetura de 32 bits, tem 20 bits contendo um índice para uma tabela de páginas e 12 bits do offset da página, onde queremos ler/escrever um dado. Uma page fault ocorre quando o endereço “linear” aponta para uma página nula (NULL) na tabela de páginas, literalmente avisando o sistema operacional que “tá faltando uma página ali!”.

Page faults podem ocorrer por outros motivos: Por exemplo, se o privilégio necessário para acessar a página não é suficiente (ring 3 não consegue acessar páginas marcadas como acessíveis apenas para o ring 0).

Assim, page faults são interrupções “especiais” que servem para que o sistema operacional tome alguma decisão sobre o que fazer a respeito… Ao seu processo, por exemplo, é dado um número limitado de páginas para conter a pilha… se o stack pointer apontar para uma página não existente e você ainda não ultrapassou o limite máximo do tamanho da pilha (8 MiB, por default, nos “Linuxes” x86-64 em que testei), então a interrupção da page fault pode resolver alocar uma página na tabela de páginas para você, caso contrário, vai te devolver uma exceção (outra interrupção) de stack overflow.

Note que a rotina de page fault pode ser complicada e gastar centenas ou milhares de ciclos de clock… Enquanto isso seu programa está “dormindo”, esperando…

Threads

Embora os processadores modernos tenham “núcleos” ou “processadores lógicos” (são coisas diferentes, eu sei!), o próprio sistema operacional usa threads em alguns momentos. Assim, as chances do seu processo ser interrompido é bem grande… Essencialmente, em multithreading assimétrico o que ocorre é que, de tempos em tempos, ocorre uma interrupção onde uma rotina chamada scheduler é chamada para decidir se é hora de “colocar” um processo para dormir e acordar outro.

Isso funciona do mesmo jeito que as interrupções, mas é um pouco pior: Para ser eficiente, a interrupção precisa ser feita de uma forma temporizada e o mais espaçada possível, para garantir alguma performance compartilhada das várias threads… Na maioria dos sistemas operacionais modernos, o tempo entre uma interrupção e outra é de cerca de 10 ms (às vezes 20 ms).

Isso significa que seu processo pode ficar N\cdot0.01 segundos “dormindo”, onde N é o número de threads assimétricas (processos, por exemplo) concorrentes (que concorrem, competem, entre si).

DMA e refresh da RAM dinâmica

Além das interrupções e threads, o processador é “interrompido” de outra forma: Quando um dispositivo externo requer o controle do barramento de endereços/dados do hardware.

É o caso, por exemplo, do circuito que realiza refresh das RAMs dinâmicas. De tempos em tempos ele pede que o processador entregue o controle do barramento para que ele (o circuito externo) dê manutenção nos dados dos pentes de memória…

Felizmente, isso não afeta o processamento que está sendo feito usando os caches e o processador entrega esse controle felizmente, continuando o processamento… mas, se o dado ou instrução não se encontram nos caches e o DMA está em ação, o processador não pode fazer mais nada senão ir domir e acordar quando tudo estiver em ordem de novo…

Outros circuitos que, geralmente, usa DMA são:

  • Placa de vídeo: O framebuffer (ou outros buffers especializados) é disponibilizado para ambos o processador e a GPU. Só um deles pode ter controle dessa região da memória…
  • Placa de rede: O ring buffer contendo os dados recebidos ou a serem enviados é comum à placa de rede e à CPU;
  • Placa de som: Vários buffers, mesmo problema;
  • USB: Embora sejam dispositivos seriais, existem buffers de transferência… Já reparou que se você está fazendo um download com taxa de transferência alta e começa a copiar dados para um pendrive a taxa cai? Culpa do DMA (e das interrupções).

Mouse e teclado não têm esse problema (são dispositivos seriais, onde o processador lida com eles de forma serial).

O que fazer com o contador do homem probre?

Não há muito o que fazer… Minha dica: Meça várias vezes e tome os menores valores obtidos. Os excessos são efeitos colaterais que não podem ser facilmente mitigados. Embora, conhecê-los pode te dar uma chance de melhorar a performance. Exemplos disso são rotinas como essa:

unsigned int sum(unsigned char *buffer, size_t size)
{
  unsigned int sum = 0;

  while ( size-- )
    sum += *buffer++;

  return sum;
}

Parece que não podemos melhorar isso mais do que está, mas, se o buffer for muito grande, teremos o efeito colateral de cache misses, especialmente no cache L1d… Aliás, isso pode acontecer com buffers pequenos também, basta que blocos de 64 bytes do buffer não estejam no cache. Suponha que tenhamos que chamar a rotina contra um buffer de 4 KiB. O que poderíamos fazer para mitigar os efeitos de cache miss é fazer uma “pré-carga” do buffer para o cache:

void preload_buffer(void *buffer, ssize_t size)
{
  while ( size > 0 )
  {
    __builtin_prefetch(buffer);
    buffer += 64;
    size -= 64;
  }
}

Com um buffer de 4 KiB teremos a “pré-carga” de 64 linhas no cache L1d. Perfeitamente factível, já que esse cache suporta 512 linhas.

Essa precarga pode gastar algum tempo além da simples pré-carga, já que se o cache L1d estiver cheio, aquelas “trocas” com o cache L2 terão que ser feitas… Pior ainda, se nenhum dos caches contiver os dados do buffer, toda a cadeia de caches terá que ser carregada… Mas, como aqui estamos apenas lendo, podemos assumir que, no máximo, uns 32 ciclos por linha serão gastos, ou seja, 2048 ciclos.

Depois de carregados, chamamos a rotina sum que, em teoria, não sofrerá os efeitos de cache miss.

Claro… a coisa fica mais complicada se o buffer for maior que 32 KiB (ou alguma fração disso, lembre-se que a pilha também está no cache… No modo i386 os argumentos das funções são passados pela pilha!). Mas, pode ser feito, agrupando blocos razoáveis em etapas de pré-carga…

Mas, e quanto a page faults? A única coisa que você pode fazer é tentar respeitar os limites impostos pelo sistema operacional. Costumo usar a seguinte tática: Se posso usar menos memória, pra quê usar mais? Isso garante, do ponto de vista da pilha, por exemplo, que não terei muitos page faults

Quanto às interrupções, nada pode ser feito. Especialmente se sua aplicação é executada no user space. Mesmo no kernel space, algumas interrupções não podem serem mascaradas ao bel prazer, sob pena do hardware não funcionar direito ou do próprio sistema desmoronar…

Também não há grandes coisas que possamos fazer quanto ao DMA…

MyToyOS: Estratégias para gastar tempo…

Anteriormente eu tinha escrito sobre o uso do PIT (Programable Interval Timer) e falei alguma coisa sobre o LAPIC (Local Advanced Interrupt Controller). No último caso (o LAPIC) temos um High Resolution Timer embutido que nos provê resoluções de temporização na ordem de algumas centenas de nanossegundos (em teoria!)…

Temporização de eventos, quando lidamos com hardware, muitas vezes é crucial. Por exemplo, os dispositivos ATA (discos) precisam de um tempo de cerca de 400 ns entre o envio do comando para a leitura de setores e a verificação da validade… No caso desses dispositivos, a especificação nos garante que qualquer leitura dos registradores de status gastará 100 ns, no mínimo, e assim, ler um desses registradores 4 vezes nos garante o gasto de 400 ns que precisamos. No entanto, existem outros dispositivos em que isso não é garantido.

Eis as 3 estratégias principais (não são as únicas) para “gastar tempo” que pode-se usar num kernel, onde garantimos o gasto controlado de tempo:

Estratégia nº 1: Ler/escrever num registrador inócuo do controlador de DMA gasta, de acordo com a especificação dos PCs, cerca de 1 μs. De fato, ler/escrever em qualquer endereço do espaço de I/O gasta esse tempo, já que as instruções IN e OUT são bem lentas (Em processadores como o Pentium 4 ou superiores a Intel garante que as instruções gastarão, no mínimo, 1000 ciclos de clock). Assim, a função inline, abaixo, pode ser usada para gastar tempo em intervalos aproximados de 1 μs:

inline void udelay( unsigned int count )
{
  while ( count-- )
    __asm__ __volatile__ ( "outb %%al,$0x80" );
}

A porta 0x80, do DMAC, é supostamente destinada o endereçamento de uma transferência, mas ela não é usada (é um scratch register). Podemos usá-la para temporização de grandeza da ordem de microssegundos. A função acima, provavelmente será compilada inline como algo assim, assumindo que ECX seja usado como contador:

...
  ; Se o compilador resolver colocar
  ; counte em ECX...
  test  ecx,ecx  ; gasta 1 clock
  jmp  .check    ; gasta 3 clocks.
.loop:
  out   0x80,al   ; gasta "count" microssegundos. 
  sub   ecx,1     ; gasta "count" clocks.
.check:
  jne   .loop     ; gasta 2*(count-1)+3 clocks

O salto para .check está ai para garantir que o código aproveite o recurso de branch prediction… Repare que, além do gasto de “count” microssegundos a função gasta 2\cdot count + 5 ciclos de clock, onde cada ciclo de clock gasta cerca de 0.1% de cada microssegundo. Ou seja, o tempo “gasto” tem um pequeno erro “para cima” de 0.1%, o que é insignificante para pequenos intervalos.

Dando uma olhada na rotina, podemos usar contagens até 2^{32}-1, o que nos daria uma espera máxima teórica de 4295 segundos, o erro será de aproximadamente 8.6 segundos. Para um “delay” que supostamente tem precisão de microssegundos, o erro é muito significativo! Dai esse método não deve ser usado para esperas muito longas. É recomendável que seja usado para valores máximos bem menores, por exemplo, até uns 10 ms.

Estratégia nº2: Para intervalos com granularidade maior ou igual a 10 ms podemos usar o PIT. A ideia é contar a quantidade de interrupções ocorridas e permanecer em um loop enquanto a contagem não “zera”. Eis um pseudo-código de exemplo:

static volatile int count;

// Habilita e desabilita a ISR do timer.
extern void enable_timer0_isr( void );
extern void disable_timer0_isr( void );

// Esse tratador será chamado a cada interrupção do timer.
// A ISR mesmo tem que ser implementada em assembly, já que
// o GCC não implementa direito o atributo "interrupt".
static void timer0_handler(void) { count--; }

void delay_ms(unsigned int cnt)
{
  // Nosa "precisão" é da ordem de 10 ms aqui!
  cnt /= 10;

  // Intervalos manores que 10 são ignorados.
  if ( cnt )
  {
    count = cnt;

    enable_timer0_isr();
    while ( count )
    {
      // NOP, aqui, existe para não deixar o processador
      // ficar "com fome". Poderíamos usar a instrução
      // PAUSE.
      __asm__ __volatile__ ( "nop" );
    }
    disable_timer0_isr();
  }
}

Claro que a rotina acima não é perfeita e pode ser bastante melhorada, mas a garantia que cada contagem será feita em intervalos regulares é dada por hardware (pelo PIT). Só que ele tem resolução fixa graças a frequência de clock usada pelo controlador (1.1931818… MHz) que, originalmente, era para ser usada como base de tempo do sinal de cor para o adaptador CGA, no padrão NTSC, nos primeiros PCs. A frequência permanece a mesma até hoje. Repare que é uma frequência com uma dizima periódica, trata-se de um valor racional de \frac{105}{88} MHz. Se você acha isso estranho, lembre-se que, mesmo que um triângulo retângulo tenha seus catetos exatamente iguais a 1, a hipotenusa tem tamanho irracional (\sqrt{2}). Um cristal piezoelétrico com frequência racional, mas não exata, é fácil de obter!

Graças a essa limitação o PIT pode, em teoria, temporizar eventos da ordem de 838 μs até 54.93 ms, dependendo do valor da contagem programada. É óbvio que nenhum desses dois valores, por mais “exatos” que sejam, é preciso. O macete é encontrar um intervalo de tempo integral (sem valores fracionários) ou um que se aproxime muito dele… Já que a base de tempo derivada de uma frequência de 1.1931818… MHz (ou \frac{105}{88} MHz), usar um contador ajustado em 11932 nos dará um valor com muito boa aproximação de 10 ms (uns 10.00015 ms). Para temporizações mais “finas” temos que recorrer a timers mais precisos. É o caso do “timer de alta resolução”, que estava dentro do seu processador o tempo todo!

Estratégia nº 3: A primeira estratégia nos dá um gasto aproximado de 1 μs por iteração. A estratégia número 2 nos dá 10 ms por iteração. O único problema com o PIT é a precisão. Com uma base de tempo na ordem de MHz, não há precisão para temporização menor que cerca de 1 ms. O HPet (High PErformance Timer), dentro do seu processador, resolve isso do jeito mais simples possível: Ele usa uma base de tempo quase 100 vezes mais rápida que o PIT: O clock do barramento do processador!

O princípio é o mesmo: Informamos para o HPet um valor que vai ser decrementado a cada clock até chegar em zero e, ai o timer gera uma interrupção…. A diferença do HPet para o PIT é que ele usa o clock do barramento (fixado em 100 MHz), ao invés da frequẽncia “maluca” de 1.19318… MHz e existem 32 timers no Local APIC.

Um detalhe adicional é que o HPet permite o uso de um divisor de frequência. A base de tempo pode ser dividida por 1 até 128, em porências de 2 (de 2^0 até 2^7). A frequência base pode ser de 100 MHz até 781,25 kHz (\frac{100}{128} MHz), ou seja, a maior resolução é da ordem de 10 ns.

A estratégia burra!

O leitor pode pensar: “Mas e quanto a um loop simples?”, como:

// test.c
void delay( unsigned int count )
{
  while ( count-- );
}

Isso pode parecer que gasta tempo, não é? Mas existem dois problemas:

Evidentemente não temos controle sobre o tempo gasto… quanto tempo “perderemos” em cada iteração do loop? O outro problema é menos evidente e só pode ser vista em assembly:

$ cc -O2 -c -o test.o test.c
$ objdump -dM intel test.o
test2.o:     file format elf64-x86-64
Disassembly of section .text:

0000000000000000 :
   0: f3 c3    repz ret

Ué?! Cadê o loop?! Esse repz está ai apenas para alinhamento e não faz absolutamente nada…

Sem a opção de otimização (-O2) o loop aparecerá, mas a rotina pode ficar mais lenta do que o necessário:

$ cc -c -o test.o test.c
$ objdump -dM intel test.o
test2.o:     file format elf64-x86-64
Disassembly of section .text:

   0:	55                   	push   rbp
   1:	48 89 e5             	mov    rbp,rsp
   4:	89 7d fc             	mov    DWORD PTR [rbp-0x4],edi
   7:	90                   	nop
   8:	8b 45 fc             	mov    eax,DWORD PTR [rbp-0x4]
   b:	8d 50 ff             	lea    edx,[rax-0x1]
   e:	89 55 fc             	mov    DWORD PTR [rbp-0x4],edx
  11:	85 c0                	test   eax,eax
  13:	75 f3                	jne    8 <delay+0x8>
  15:	90                   	nop
  16:	5d                   	pop    rbp

Ok… esse é um código gerado para o modo x86-64, mas o modo i386 é ainda pior. Estou usando isso para ilustrar… O detalhe aqui é se perguntar pra quê esse monte de copias para a pilha? Se count é passado em EDI a rotina deveria ser algo assim:

delay:
  jmp   .check
.loop:
  sub   edi,1
.check:
  test  edi,edi
  jnz   .loop
  ret

No caso do modo i386, o valor é passado pela pilha, mas poderíamos usar o atributo regparm(1) para a função, forçando a passagem por EAX. Isso não melhora grandes coisas:

delay:
  push ebp
  mov  ebp,esp
  sub  esp,4
  call __x86.get_pc_thunk.dx
  add  edx,2
  mov  [ebp-4],eax
  nop
.loop:
  mov  ax,[ebp-4]
  lea  edx,[eax-1]
  mov  [ebp-4],edx
  test eax,eax
  jne  .loop
  nop
  leave
  ret

__x86.get_pc_thunk.dx:
  mov  edx,[esp]
  ret

Que droga é essa de __x86.get_pc_thunk.dx?

Ou seja, “gastar” tempo com loops assim é a receita para o desastre. Não faça isso!

Mais duas funções de manipulação de string essenciais…

Acho que é óbvio que as funções da standard library são abreviações simples de serem entendidas. A função printf vem de print formated ou “imprime formatado”. A função scanf, por analogia, vem de scan formated ou “varredura” formatada (obs: “scan” não é a mesma coisa que “input”, a função varre o stream — no caso, stdin — procurando pelos “formatos” nos bytes recebidos). Aqui vou falar de strspn e sua contraparte (guarde essa palavra!) strcspn.

A função strspn conta quantos caracteres, a partir do início do buffer, constam (spans) no conjunto passado como segundo argumento. O protótipo é:

size_t strspn( const char *s, const char *accept );

Se você chamar a função assim:

size_t n;

n = strspn( "frederico", "efr" );

A variável n será 3, indicando que os 3 caracteres iniciais do buffer constam na string informada em accept.

A função strcspn, cujo protótipo é similar:

size_t strcspn( const char *s, const char *reject );

É o contraponto de strspn ou, de outra forma, “counter span” ou “complementary span”. Ou seja, ela conta quantos bytes da primeira string não constam em nenhum caracter da segunda:

n = strcspn( "frederico", "oi" );

Neste caso, n será 6 porque “freder” não contém nem ‘i’ e nem ‘o’.

Note que as funções devolvem um valor sem sinal e inteiro (do tipo size_t). Existe uma função equivalente de strcspn, mas que devolve o pronteiro do primeiro caracter encontrado: strpbrk. No entanto, essa função retorna NULL se não conseguir encontrar caracter algum.

Costumo usar essa para apagar qualquer sequência “\r\n” do final de um buffer lido por getline:

char *line;
size_t line_size;

line = NULL;
line_size = 0;
if ( getline( &line, &line_size, stdin ) != -1 )
{
  char *p;

  // Sim! está correto! É um = mesmo!
  // se strpbrk() não achar nenhum dos
  // dois caracteres ele retorna NULL,
  // que é a mesma coisa que retornar 0.
  // Qualquer outro ponteiro será encarado
  // como 'true' pela expressão.
  if ( p = strpbrk( line, "\r\n" ) )
    *p = '\0';

  ... faz algo ...

  free( line );
}

Sim, eu poderia aproveitar o tamanho obtido em line_size para verificar se os últimos 2 chars são ‘\r’ ou ‘\n’, mas, desse jeito, o primeiro que strpbrk achar recebe o NUL char. Ahhh… e o pbrk tem o significado do tipo retornado (um ponteiro) e que ele aponta para onde a varredura “parou” (breaks), se qualquer caracter da segunda string for encontrado na primeira.

Diferenças entre strtok() e strsep()

Ambas as funções são padronizadas. A segunda, strsep() é definida no padrão 4.4BSD e, elas parecem equivalentes. Ambas procuram por delimitadores numa string, não é? Eis um testezinho:

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

// Caracteres usados como delimitadores.
#define DELIM "\t ,"

static void test_strtok( char * );
static void test_strsep( char * );

int main( void )
{
  // Nossa string de teste.
  static char s[] = "1, 2, 3";

  printf( "Original String: \"%s\"\n", s );

  test_strtok(s);
  test_strsep(s);

  return EXIT_SUCCESS;
}

void test_strtok( char *s )
{
  char *cpy, *state, *p;

  // Cria uma cópia para não bagunçar o buffer original.
  if ( ! ( cpy = strdup( s ) ) )
  {
    perror( "strdup" );
    exit ( EXIT_FAILURE );
  }

  puts( "\nstrtok_r:" );

  p = strtok_r( cpy, DELIM, &state );
  while ( p )
  {
    printf( "\"%s\"\n", p );
    p = strtok_r( NULL, DELIM, &state );
  }

  free( cpy );
}

void test_strsep( char *s )
{
  char *cpy, *p, *q;

  // Cria uma cópia para não bagunçar o buffer original.
  if ( ! ( cpy = strdup( s ) ) )
  {
    perror( "strdup" );
    exit( EXIT_FAILURE );
  }

  puts( "\nstrsep:" );

  // Como o ponteiro para o próximo 'token' será alterado,
  // não podemos modificar 'cpy' para podermos nos livrar 
  // do buffer, no fim das contas...
  q = cpy;
  while ( p = strsep( &q, DELIM ) )
    printf( "\"%s\"\n", p );

  free( cpy );
}

É fácil perceber que as duas funções não fazem a mesma coisa:

$ cc -o test test.c./test
Original String: "1, 2, 3"

strtok_r:
"1"
"2"
"3"

strsep:
"1"
""
"2"
""
"3"

A diferença de significado é explícito no próprio nome das funções: “tok” de strtok significa token ou, numa tradução livre, “símbolo”, e é isso que a função procura, usando os caracteres na segunda string como delimitadores. Já strsep procura pelos “separadores” (não pelos tokens). Para strsep, como entre “1, 2” temos dois separadores (uma ‘,’ e um espaço), entre eles tem que haver uma string vazia.

Assim, se vários caracteres delimitadores aparecerem em sequência, strtok simplesmente os ignorará, mas strsep nos dará strings vazias, de acordo com a quantidade de delimitadores sequenciados. Altere a string para "1, 2, 3," (colocando uma ‘,’ extra no final), por exemplo, e verifique os resultados…

Note que usei strtok_r aqui. Fiz isso porque strtok mantém o estado da última procura em uma variável global na libc, exigindo que as demais chamadas passem NULL como argumento para usar esse “estado”, o que a torna thread unsafe. strtok_r acerta isso permitindo que informemos onde este estado será mantido. A função strsep, por outro lado, não sofre desse problema porque ela modifica o argumento do início da busca a cada chamada. O “estado” é o próprio início do buffer onde os separadores estão sendo buscados.

As últimas notas são as de que ambas strtok e strsep alteram o buffer onde a pesquisa está sendo feita, substituindo o próximo separador por '\0' e retornando o ponteiro após o separador anterior. Isso, é claro, exige que o ponteiro do primeiro argumento das funções (exceto o NULL além da primeira chamada de strtok) aponte para um buffer que possa ser escrito… Isso aqui embaixo vai causar um “segmentation fault“:

char *s = "1, 2, 3";
char *p;

// Causará SIGSEGV! buffer apontado por s
// não pode ser escrito!
p = strtok( s, "\t ," );

Então, para evitar “poluir” a string original, fiz uma cópia usando strdup, que exige que o novo buffer seja liberado com free para evitar memory leakage.