Duas formas de implementar timeout para system calls que bloqueiam…

… e estou falando daquelas que usam file descriptors aqui, em ambiente Unix (Linux, FreeBSD, MacOS…).

A primeira e mais fácil é usando o sinal SIGALRM, como mostrei no artigo anterior, sobre uso de NTP:

  1. Escrevemos uma rotina de tratamento para SIGALRM;
  2. Chamamos alarm(segundos) antes da syscall que bloqueia;
  3. Chamos a syscall;
  4. Chamamos alarm(0) para desabilitar o disparo de SIGALRM.

Funciona que é uma beleza, mas tem um problema! A implementação da libc pode usar SIGALRM para algumas funções. É, talvez, o caso de sleep() — veja, por exemplo, no livro Advanced Programming in the UNIX Environment de Richard W. Stevens… Isso, é claro, atrapalha, já que sleep() escreverá sua própria rotina de tratamento de SIGALRM.

Outro método, mais seguro que funcione, é usar uma das syscalls de multiplexação (select, poll, epoll ou a biblioteca libevent). Para efeitos de simplicidade, usarei poll() aqui. A técnica é simples. Essas rotinas verificam se o file descriptor está pronto para escrita ou leitura, deixando a thread “dormente” enquanto não estão… Por exemplo, para verificar se o descritor contém dados para serem lidos, fazemos:

#define TIMEOUT_MS 3000

// Assume que sockfd seja nosso descritor...
struct pollfd pfd = { .fd = sockfd, .events = POLLIN };
sigset_t set, oldset;
int retcode, blocked;

sigfillset ( &set ); // todos os sinais...
sigprocmask ( SIG_BLOCK, &set, &oldset );
blocked = 1;

if ( ( retcode = poll ( &pfd, 1, TIMEOUT_MS ) > 0 )
{
  sigprocmask ( SIG_SETMASK, &oldset, NULL );
  blocked = 0;

  // chama read() para ler do descritor...
  ...
}

// Ainda temos os sinais bloquados, volta para o estado
// anterior!
if ( blocked )
{
  sigprocmask ( SIG_SETMASK, &oldset, NULL );
  blocked = 0;  // por garantia, caso usemos isso adiante.
}

// Ocorreu timeout ou erro em poll()?
switch ( retcode )
{
case -1: /* trata o erro aqui... */
         ...
         break;
case 0: /* trata o timeout aqui. */
        ...
}
...

Note que poll também é uma syscall e pode ser interrompida por um sinal. É conveniente bloquear os sinais enquanto ela estiver sendo executada. Isso é importante, especialmente se seu tratador de sinais não reinicia a syscall interrompida (default, quando se usa signal(), ajustável quando se usa sigaction() para registrar a rotina de tratamento de sinais usando o flag SA_RESTART)… Mas não está claro (para mim, pelo menos) nas man pages se, mesmo que poll seja reiniciada depois de interrompida, retornará ou não como interrompida (errno será EINTR) quando o argumento timeout não for negativo. Isso porque a documentação nos diz que poll desbloqueia em 3 condições:

  1. O file descriptor está “pronto”, de acordo com o evento na estruttura de pollfd;
  2. Um sinal a interrompe;
  3. O timeout expira.

Para não correr riscos, bloqueio todos os sinais para o processo (ou thread, se for o caso, mas, para isso temos pthread_sigmask() ou a função ppoll().

O método tradicional de multiplexing pode ser usado também (via select()) e é similar a poll, só tem aquele jeito esquisito de ajustar os eventos via macros FD_* e necessita da estrutura struct timespec para estabelecer o timeout (acho poll mais simples!).

O uso de epoll, que também é uma syscall, dizem, funciona bem melhor no Linux, mas é bem complicadinha… Dizem, por ai, também que libevent é a melhor maneira de lidar com eventos. De fato, se você está acostumado a lidar com o Apache HTTPD, lembrará dos “módulos de multi-processamento” (MPMs): prefork, worker e event. Hoje em dia, geralmente, prefere-se o MPM event no Apache… Dê uma pesquisada nesses dois últimos métodos (epoll e libevents). Se bem me lembro, o NGINX usa libevents por default.

Anúncios

Usando NTP…

Um dos métodos muito comuns em desenvolvimento de aplicações usando bancos de dados é o uso do relógio contido no host onde o banco está hospedado como se fosse “confiável”, como um método de sincronização de data/hora. No caso de sistemas que usam o Oracle é muito comum ver uma query assim:

SELECT SYSDATE FROM DUAL;

Algo semelhante é feito para o MS SQL Server e outros bancos de dados famosos:

SELECT GETDATE();  -- MS SQL Server
SELECT NOW();      -- MySQL e PostgreSQL

O problema é que todo momento em que seu código precise obter data e hora, terá que fazer uma consulta ao banco de dados. Lembre-se que uma consulta precisa ser decodificada pelo servidor antes de ser processada e há tratamento de conexão e acessos concorrentes. Sua data/hora obtida pode não ser precisa.

Felizmente existe uma solução, que já existe tem mais de duas décadas! NTP. O Network Time Protocol, além de fornecer a data/hora de fontes confiáveis, permite corrigir os atrasos na transmissão… A ideia do protocolo surgiu como ferramente de medição de performance (quanto tempo dura um roundtrip, ou seja, mandei um pacote e em quanto tempo ele chega?), bem como a obtenção de data e hora de fontes extremamente precisas e padronizadas.

A ideia não é nova. Durante as grandes guerras mundiais a necessidade do uso de relógios precisos é fator essencial para comunicações e até ações militares. Hoje em dia, em “tempo de paz”, a manutenção de horários precisos é essencial não apenas para o comércio, mas também para sistemas de posicionamento globais (GPS)… Não é incomum que as fontes de tempo sejam baseadas em “relógios atômicos”, por exemplo.

O protocolo, diferente de outros mais comuns como HTTP, não é do tipo stream ou baseado em caracter. É um padrão binário, onde o requisitante envia um pacote e recebe um pacote. Ainda, tudo trafega via UDP, ou seja, não exige a manutençao de uma conexão TCP — o que torna a transação bem rápida, em teoria… Basta enviar 48 bytes para o ntp server e ler 48 bytes que ele te enviar.

Isso pode parecer pior que enviar uma string de 25 bytes (no caso do Oracle) e obter uns 20 bytes de volta (se o retorno for do tipo “DD/MM/YYYY HH:MM:SS”), mas note, abaixo, que NTP leva em conta o atraso na rede e ainda temos a questão da confiabilidade da fonte…

Abaixo temos o código-fonte de um pequeno cliente NTP, escrito em C:

// ntp4.c
//
// Compilar com:
//  cc -O2 -o ntp4 ntp4.c
//

// _GNU_SOURCE necessário para usar a função basename()
// definida pela GNU, não a POSIX.
#define _GNU_SOURCE
#include <unistd.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <time.h>
#include <signal.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <netdb.h>

// Códigos ANSI CSI para "colorir" a saída...
#define RED    "\033[1;31m"
#define YELLOW "\033[1;33m"
#define DFL    "\033[0m"

// NTP usa "1º de janeiro de 1900, 0:00:00" como base de
// tempo. UNIX usa "1º de janeiro de 1970, 0:00:00".
// NTP_TIMESTEMP_DELTA é a diferença, em segundos.
// O macro NTP2UNIX_TIMESTAMP faz o que o nome diz.
#define NTP_TIMESTAMP_DELTA 2208988800U
#define NTP2UNIX_TIMESTAMP( x ) \
  ( time_t ) ( ( x ) - NTP_TIMESTAMP_DELTA )

// O protocolo NTP v3 usa essa estrutura.
// RFC-1305: https://tools.ietf.org/html/rfc1305
struct ntp_packet_s
{
  // +-+-+-+-+-+-+-+-+
  // |0|0|0|1|1|0|1|1|
  // +-+-+-+-+-+-+-+-+
  //  --- ----- -----
  //   |    |     |
  //   |    |     +------ Modo (3 para cliente)
  //   |    +------------ Versão (3)
  //   +----------------- Indicador de "leap second"
  //                      (do último minuto) (0)
  uint8_t li_vn_mode;

  uint8_t stratum;
  uint8_t poll;
  uint8_t precision;

  uint32_t rootDelay;
  uint32_t rootDispersion;

  uint32_t refId;
  uint32_t refTm_s;
  uint32_t refTm_f;
  uint32_t origTm_s;
  uint32_t origTm_f;

  uint32_t rxTm_s;
  uint32_t rxTm_f;
  // Os timestamps transmitidos pelo NTP estão nesses
  // dois valores.
  uint32_t txTm_s;
  uint32_t txTm_f;
};

// Usado como tempo de timeout para escrita/leitura.
// Em segundos.
#define TIMEOUT 3

// Nosso sinal usa essa variável para determinar
// para quem estamos atendendo o sinal SIGALRM.
static int sigop;         // 0 = write, 1 = read

// Protótipo local do tratador de SIGALRM.
static void timeout_handler ( int );

int main ( int argc, char *argv[] )
{
  // Restringi para IPv4.
  struct addrinfo ai_hint = { .ai_family = AF_INET };
  struct ntp_packet_s ntppkt = { .li_vn_mode = 033 };
  struct sigaction sa = {};

  struct addrinfo *resai;
  struct servent *se;
  struct sockaddr_in *sinp;
  time_t t;
  int fd;

  // Se o segundo argumento não foi informado, erro.
  if ( ! *++argv )
  {
    fprintf ( stderr, 
              YELLOW "Usage" DFL ": %s <\"addr\">\n", 
              basename( *(argv - 1) ) );
    return EXIT_FAILURE;
  }

  // Resolve o "nome"...
  if ( getaddrinfo ( *argv, NULL, &ai_hint, &resai ) )
  {
    perror ( "getaddrinfo" );
    return EXIT_FAILURE;
  }

  if ( ! resai )
  {
    fprintf ( stderr, 
              RED "ERROR" DFL ": Cannot resolve '%s'.\n", 
              *argv );
    return EXIT_SUCCESS;
  }

  // Cria o file descriptor.
  fd = socket ( AF_INET, SOCK_DGRAM, IPPROTO_UDP );
  if ( fd == -1 )
  {
    perror ( "socket" );
    freeaddrinfo ( resai );
    return EXIT_FAILURE;
  }

  // Pegamos a porta do serviço NTP de /etc/services.
  sinp = ( ( struct sockaddr_in * )resai->ai_addr;
  if ( se = getservbyname ( "ntp", NULL ) )
    sinp->sin_port = se->s_port;
  else
    // Se não achou, assume porta 123.
    sinp->sin_port = htons ( 123 );

  // read()/write() exigem que o file descriptor esteja
  // "conectado". Poderíamos usar sendto() e recvfrom()
  // e evitar isso... Para UDP connect() não "conecta",
  // mas apenas ajusta o descritor.
  if ( connect ( fd, 
                 resai->ai_addr, 
                 resai->ai_addrlen ) == -1 )
  {
    perror ( "connect" );
    freeaddrinfo ( resai );
    goto fail;
  }

  // Não preciso mais da lista
  // devolvida por getaddrinfo().
  freeaddrinfo ( resai );

  // Ajusta o tratador de sinal SIGALRM.
  sigfillset ( & ( sa.sa_mask ) );
  sa.sa_handler = timeout_handler;
  sigaction ( SIGALRM, &sa, NULL );

  // Tenta enviar o pacote...
  sigop = 0;
  alarm ( TIMEOUT );
  if ( write ( fd, &ntppkt, sizeof ntppkt ) == -1 )
  {
    perror ( "write" );
    goto fail;
  }
  alarm ( 0 );

  // Tenta obter uma resposta.
  sigop = 1;
  alarm ( TIMEOUT );
  if ( read ( fd, &ntppkt, sizeof ntppkt ) == -1 )
  {
    perror ( "write" );
    goto fail;
  }
  alarm ( 0 );

  // Calcula e mostra a data/hora.
  t = NTP2UNIX_TIMESTAMP( ntohl ( ntppkt.txTm_s ) );
  printf ( "%s\n", ctime ( &t ) );

  // SUCESSO!
  close ( fd );
  return EXIT_SUCCESS;

fail:
  // Não precisamos chamar alarm(0) aqui!
  close ( fd );
  return EXIT_FAILURE;
}

// Tratador de SIGALRM
void timeout_handler ( int signum )
{
  static const char *const msg[] =
  { RED "TIMEOUT" DFL ": ", 
    "sending request\n", 
    "receiving respospnse\n" };

  // Uso write() aqui porque printf() não é "AS-Safe".
  write ( STDERR_FILENO, msg[0], strlen ( msg[0] ) );
  write ( STDERR_FILENO, 
          msg[1 + sigop], 
          strlen ( msg[1 + sigop] ) );
  exit ( EXIT_FAILURE );
}

Nesse programinha você pode usar qualquer ntp server que esteja disponível para a sua rede. Por exemplo:

$ cc -O2 -o ntp4 ntp4.c
$ ./ntp4 a.ntp.br
Fri Jun 15 14:27:55 2018

Aqui, a.ntp.br é um dos ntp servers de estrato 2, em conformidade com o “horário legal” brasileiro. Eis a estrutura, como descrita em ntp.br (aqui):

Segundo a documentação e orientações de ntp.br, todos os servers do estrato 1 também são acessíveis publicamente… Qual a vantagem de usar ntp.br? A data e hora são as chamadas “horário legal” brasileiro… Isso levanta a questão de que para obter a data/hora “corretas” teríamos que realizar uma consulta na Internet… Não necessariamente.

Instalando e configurando seu próprio NTP server no Linux:

Com seu próprio ntp server você pode apontar todos os seus hosts para sincronização de horário por ele. Deixe-o ir até o ntp.br por você…

Nada mais simples:

  • Instale o pacote ntp:
$ sudo apt-get install ntp
  • Modifique /etc/ntp.conf:
# Retire as linhas contendo 'pool' e 'server' e as substitua por:
server a.st1.ntp.br iburst
server b.st1.ntp.br iburst
server c.st1.ntp.br iburst
server d.st1.ntp.br iburst
server gps.ntp.br iburst
server a.ntp.br iburst
server b.ntp.br iburst
server c.ntp.br iburst
  • Reinicie o serviço ntp.service:
$ sudo systemctl restart ntp.service

Pronto… Basta apenas liberar a porta 123 e, se quiser, registrar um nome para seu ntp server. Existem algumas configurações extras que você pode fazer para tornar seu servidor mais seguro, mas, essencialmente, isso é tudo.

Mifu…

Sabem aqueles grupos onde o pessoal costuma fazer perguntas de “problemas” de cursos de graduação de computação? Do tipo “faça um programa que some 5 números…”? Well… Eu acho isso enfadonho! Mas, recentemente, topei com um que, onde “me fudi” com uma resposta irônica de minha parte (e peço desculpas, porque a solução é mesmo interessante para o aprendiz!)…

O problema era esse ai mesmo que citei acima:

“Faça um programa que leia 5 valores inteiros e apresente a soma desses valores usando apenas uma variável

A parte em negrito é a que torna o problema interessante… Normalmente o estudante usa uma variável para ler os valores e outra para acumulá-los:

/* test1.c */
#include <stdio.h>

void main ( void )
{
  int sum, n;

  scanf ( "%d", &sum );
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;
  scanf ( "%d", &n ); sum += n;}

  printf( "%d\n", sum );
}

Claro, isso usa duas variáveis, o que invalida a solução. Poderíamos usar um array:

/* test2.c */
#include <stdio.h>

void main ( void )
{
  int n[2];

  scanf ( "%d", &n[0] );
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];
  scanf ( "%d", &n[1] ); n[0] += n[1];

  printf( "%d\n", n[0] );
}

O programa acima é, essencialmente, a mesma coisa que o anterior e o estudante pode pensar que está usando apenas uma “variável”. No entanto, um arry é uma “sequência” de variáveis (a tradução direta da palavra “array” significa “sequência”), ou seja, está usando duas variáveis. Isso invalida a parte “usar apenas uma variável” do problema. Eis a solução engenhosa:

/* test3.c */
#include <stdio.h>

void main ( void )
{
  long long n;  // n tem 64 bits de tamanho!

  scanf ( "%d", ( int * )&n );

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  scanf ( "%d", ( int *)&n + 1 ); 
  *( int * )&n += *( int * )(&n + 1);

  printf( "%d\n", *( int * )&n );
}

Ao fazer o casting ( int * ) usamos a aritmética de ponteiros envolvendo o tipo int, que tem 32 bits de tamanho. Assim, ( int * )&n + 1 é uma expressão que é resolvida para os 32 bits superiores de n, enquanto ( int * )&n aponta para os 32 bits inferiores. Ao derreferenciar esse ponteiro, acessamos o seu valor, na pilha.

Em essência, estamos mexendo com um array, mas usando apenas uma variável!!! Isso atende a ambas os requisitos do problema, mas causa um problema de performance… Quando declaramos uma variável local qualquer o compilador, se tiver sido chamado com opções de otimização, tenta usar os registradores da CPU ao invés da pilha. Ao usar o operador & (endereço-de) forçamos o compilador a manter a variável na pilha. Como os scanf precisam do endereço da variável lida, os três programas, acima, geral praticamente o mesmíssimo código… Assim, cada chamda a scanf e cada acumulação usará um ou mais acessos à memória que, mesmo estando no cache L1d, poderá adicionar 1 ciclo de clock adicional às instruções (resolução do endereço efetivo).

A rotina abaixo, mais tradicional, tem o potencial de ser bem mais rápida e gastar menos espaço no cache L1i:

/* test4.c 
   Compile com: 
     gcc -O2 -fno-stack-protector -w -o test4 test4.c 
*/
#include <stdio.h>

void main ( void )
{
  int sum, n, count;

  count = 5;
  sum = 0;
  while (count--)
  {
    scanf ( "%d", &n );
    sum += n;
  }

  printf( "%d\n", sum );
}

Posso mostrar que count e sum não são mantidos na memória, mas em registradores. Apenas n não é otimizado dessa forma por causa do operador &:

; test4.asm - equivale a test4.c.
bits 64
section .rodata
scanf_fmt:  db `%d`
printf_fmt: db `%d\n`

section .text
global main
main:
  push rbp
  push rbx

  xor  ebp,ebp  ; sum=0
  mov  ebx,5    ; count=5

  sub  rsp,24   ; reserva espaço na pilha, alinhando-a

.loop:
  lea  rsi,[rsp+12]  ; n está alocado na pilha em rsp+12.
  xor  eax,eax       ; scanf() precisa disso (porquê?)
                     ; EAX, aqui, NÃO é stdin!
  mov  edi,scanf_fmt
  call __isoc99_scanf

  add  ebp,[rsp+12]  ; sum += n;
  sub  ebx,1         ; --count;
  jne  .loop         ; if (count != 0) goto loop.

  mov  edx,ebp
  mov  esi,printf_fmt
  mov  edi,1         ; stdout
  xor  eax,eax       ; printf() precisa disso (porquê?)
  call __printf_chk

  add  rsp,24   ; dealoca espaço previamente alocado na pilha.

  pop  rbx
  pop  rbp
  ret

Se não fosse pela necessidade do scanf, n também seria mantido em um registrador (R12D, por exemplo). Mas, note que temos apenas UM acesso à memória por iteração do loop (em add ebp,[rsp+12], mas, é claro, scanf também acessa memória!). No caso de test3.c temos 9 indireções, além das causadas pelo scanf, no caso de test4.c, 5.

Ahhh… lea rsi,[rsp+12] não é uma indireção, mas somente o cálculo do endereço efetivo…

Embora o exercício seja interessante, não passa de curiosidade acadêmica…

TCP e UDP, uma técnica interessante (e perigosa)…

Há uns anos escrevi uns artigos aqui sobre o princípio da construção de um http server em C. Eis dois detalhes que deixei de mencionar: TCP é um protocolo de streaming que não oferece “fronteiras” entre mensagens. Isso quer dizer que vocẽ pode enviar 10 pacotes de 300 bytes de um lado e obtê-los na mesma ordem (com tamanhos diferentes), ou obter um único pacotão de 3000 bytes, de uma só vez. Não há garantias de como você receberá esses dados, a única garantia é que, se não houverem erros ou se a conexão não cair, vocẽ os receberá na ordem que foram enviados. Esse comportamento acontece porque sua placa de rede mantém um buffer (e o driver de rede também).

Outro problema é que, se você tentar ler mais dados do que foram enviados, a system call recv(), se o descritor de arquivos (socket) não estivar marcado como “non blocking“, ficará esperando novos dados “eternamente”. Então, só existem duas maneiras de sabermos quantos dados devem ser lidos:

  1. Se soubermos de antemão o tamanho da mensagem;
  2. Se a mensagem contiver “marcadores”.

O segundo caso é o usado pelo protocolo HTTP quando uma requisição é feita. Toda linha de uma requisição termina com “\r\n” e a última linha é vazia (tem apenas a marca de fim de linha)… Podem existir mais linhas, no caso de um método POST, mas ai o tamanho do conteúdo é informado na requisição via atributo “ContentLength”, no header.

Um jeito interessante de lidar com esse tipo de coisa é usando o modo streamming de arquivos, na linguagem C, ou seja, usando a estrutura opaca FILE. Suponha que fd seja o descritor de um socket. Podemos fazer algo assim:

FILE *fsock;

if ( ! ( fsock = fdopen ( fd, "r+" ) ) )
{ ... trata erro aqui ... }

E daqui para frente poderemos usar funções como fgetc, fgets, fputc fputs, fread e fwrite ou até mesmo fscanf e fprintf para lidar com o descritor. Note, por exemplo, que fgets pára de ler o stream quando encontra um ‘\n’, o que pode facilitar o desenvolvimento de um HTTP server…

Existem duas vantagens e uma desvantagem em usar a estrutura de streams de C. A primeira vantagem é que você deixa pra libc ler os caracteres. A desvantagem é que perderemos o controle da semântica de recv… Quando recv retorna 0, ele indica que a conexão “caiu”, quando retorna -1, houve um erro. No caso do retorno de 0 as funções de streaming podem ficar “esperando” pelos dados, simplesmente achando que não existem dados para serem lidos! Em teoria, não temos problemas com o retorno de -1, que será repassado, mas provavelmente errno não será ajustado de forma coerente. Assim, se as funções de streaming facilitam a manipulação de leitura/escrita, ela dificulta em outros detalhes (que não são intratáveis!).

A outra vantagem, a despeito da desvantagem da semântica, é que o gerenciamento do buffer do stream, feito pela libc, permite-nos usar a função ungetc para colocarmos de volta os bytes que, por ventura, tivermos lido, acidentalmente, além de algum “marcador”.

É importante notar, também, que, já que estamos trabalhando com double buffering aqui (o buffer do stream e o buffer da fila do driver de rede), temos que usar a função fflush para descarregarmos o stream quando estivermos escrevendo no socket via FILE.

fprintf ( fsocket, 
          "%d %s HTTP/1.1\r\n", 
          error_code, 
          error_str[error_code] );
fflush ( fsocket );
fclose ( fsocket );

O fclose chamará a system call close e fechará o socket normalmente, mas precisamos mesmo usar o fflush antes disso, senão a string poderá ficar “presa” no buffer do stream. Uma maneira de evitar isso, se o nosso marcador for ‘\n’, e marcar fsocket como line buffered, logo depois de criá-lo com fdopen:

setlinebuf ( fsock ); // disponível apenas na GNU libc

Ou controlando o tamanho do buffer de streaming, de maneira mais padronizada:

static char buffer[2048]; // buffer de 2 KiB...
setvbuf ( fsock, buffer, _IOLBF, sizeof buffer );

Mesmo assim, fflush pode ser necessário se estivermos enviando dados que não contenham ‘\n’ no fim da string.

Onde é que o UDP entra nisso tudo? Não entra! Esse método não deve ser usado com UDP, especialmente porque ele é feito para o envio de um pacote único, caso contrário, não há garantidas da ordem da recepção… Ou seja, UDP não é streaming.

O bom, o mal e o feio

Neste artigo vou tentar mostrar 3 coisas: O algoritmo mais óbvio raramente é o melhor possível, um bom algoritmo pode ser sempre melhorado e que essa melhoria nem sempre vem sem custos. A ideia é usar um algoritmo custoso, em termos de processamento e, para isso, aqui vão os famosos testes para determinação se um valor inteiro positivo é ou não um número primo.

Nesses testes usarei o tipo unsigned int porque ele tem 32 bits de tamanho em ambas as plataformas Linux (e na SysV ABI) e Windows, tanto para o modo de operação do processador, x86-64 e i386. É bom reparar nisso, porque a determinação desse tipo de parentesco (se é primo!) em valores inteiros com mais bits pode ser muito demorada. Por exemplo, quando lidamos com o esquema de criptografia assimétrica, é comum o uso de chaves de 2048 bits de tamanho, o que torna uma das otimizações inviável (veremos adiante).

O feio

O algoritmo clássico é varrer toda a faixa de valores menores que o valor sob teste e verificar se existe algum divisor exato. Algo assim:

// Método tradicional: Tenta dividir todos os valores 
// inferiores a 'n' e conta quantos o dividem...
NOINLINE
int ugly_is_prime ( unsigned int n )
{
  unsigned int count, i;

  // caso especial.
  if ( !n ) 
    return 0;

  count = 1;
  for ( i = 2; i < n; i++ )
    if ( ! ( n % i ) )
      count++;

  return (count == 1);
}

Por que chamei essa rotina de “o feio”? Ela testa por todos os valores inferiores a n, começando por 2, se n for diferente de zero! Suponha que n=4294967291. Esse valor é primo, mas para a rotina determinar isso terá que percorrer todos os valores entre 2 e 4294967290. Veremos que, para isso, a rotina gasta cerca de 47 bilhões de ciclos de clock!

O mau

É claro que não precisamos verificar todos os valores! Por exemplo, 2 é o único valor par que também é primo. De cara podemos testar se n é par e diferente de 2. Se for, com certeza não é primo. Isso nos deixa os valores ímpares para teste, o que diminui pela metade o esforço computacional.

Outra melhoria que podemos fazer é a de que, de acordo com o Princípio fundamental da aritmética, todo número pode ser fatorado em números primos… Por exemplo, 9=3\cdot3, 10=2\cdot5, 76=2\cdot\cdot2\cdot19 e assim por diante (voltaremos a isso no algoritmo “bom”). Ainda, “lembre-se que a ordem dos fatores não altera o produto”. Tome 10 como exemplo… Ele pode ser escrito como 10=2\cdot5=5\cdot2.

Não é evidente, mas graças a isso só precisamos testar por divisores ímpares menores ou iguais a raiz quadrada de n:

// Método "ruim" (mas, melhor que o acima).
// Faz a mesma coisa, mas só verifica os valores inferiores a 'n' 
// que sejam ímpares e menores ou iquais a raiz quadrada de 'n'.
int bad_is_prime ( unsigned int n )
{
  unsigned int sr;
  unsigned int i;

  // casos especiais.
  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  };

  // O único par primo é 2.
  if ( ! ( n & 1 ) )
    return 0;

  // Obtém o valor ímpar menor ou igual
  // à raíz quadrada de n.
  sr = sqrt(n);
  if ( ! ( sr & 1 ) ) 
    sr--;

  // Só precisamos testar os valores ímpares
  for ( i = 3; i <= sr; i += 2 )
    if ( ! ( n % i ) )
      return 0;

  return 1;
}

Aqui tomo um atalho para os 2 primeiros primos (1 e 2) para simplificar a rotina.

Mas, porque essa rotina é ? O problema aqui é que, mesmo eliminando testes, estamos testando muitos valores mais de uma vez… Por exemplo, se n não for divisível por 3 ele também não será para nenhum múltiplo de 3, como 9, 12, 15, 18, 21, 24, 27… No entanto, estamos testando esses valores também, se n for grande!

O bom

A solução, é claro, é eliminar todos os valores múltiplos dos anteriores, ou seja, usar apenas divisores primos. O problema é óbvio: Ora, bolas! Como é que eu vou fazer uma rotina que testa se um valor é primo usando como critério o teste se um divisor também o é?!

O método de Erastótenes (276 AEC ~ 194 AEC) mantém uma sequência onde marcamos os valores primos, percorrendo a lista do início ao fim, e verificando se os próximos valores são múltiplos. Se forem, marcamos como “não primo”. Na próxima interação, o próximo valor é, com certeza, primo e repetimos o processo, até que todo o array contenha apenas os primos “não marcados”. Isso exige que toda a faixa de valores seja colocada no array, mas os valores usados como base de testes podem ser limitados à valores menores ou iguais a raíz quadrada de n, como fizemos anteriormente.

O ponto negativo desse método, é claro, é o consumo excessivo de memória para conter todo o array, mas, e se mantivéssemos apenas um array com os valores primos ímpares inferiores ou iguais à raiz quadrada da faixa do tipo unsigned int? Isso não consumirá tanta memória quanto você pode imaginar: Em primeiro lugar, no pior caso, teríamos um array com \frac{\sqrt{2^{32}-1}}{2}\approx32767 itens. Se cada item tem 4 bytes de tamanho, aproximadamente 128 KiB serão usados para o array. No caso mais prático, vários valores desses 32767 são eliminados, porque não serão primos.

O programinha abaixo, que usa o bad_is_prime(), acima, monta esse array:

// gentable.c
//
// Cria tabela contendo os inteiros, primos, menores ou iguais ao
// valor ímpar mais pŕoximo (porém menor) que a raiz quadrada de 2³²-1.
//
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

extern int bad_is_prime ( unsigned int );

#define ITEMS_PER_LINE 16

void main ( int argc, char *argv[] )
{
  FILE *f;
  unsigned int i, sr;
  unsigned int count = 0, cnt2 = 0;

  if ( ! *++argv )
  {
    fputs ( "Usage: gentable <cfile>\n", stderr );
    exit ( 1 );
  }

  if ( ! ( f = fopen ( *argv, "wt" ) ) )
  {
    fprintf ( stderr, 
              "ERROR opening file %s for writing.\n", 
              *argv );
    exit ( 1 );
  }

  fputs ( "// *** criado por gentable.c ***\n\n"
          "// tabela começa de 3...\n"
          "const unsigned int primes_table[] = {\n", f );

  // ~0U é o máximo valor de unsigned int.
  // Obtém a raiz quadrada ímpar...
  sr = sqrt(~0U);
  if (!(sr & 1)) 
    sr--;

  // Só precisamos dos inteiros ímpares e primos.
  for ( i = 3; i <= sr; i += 2 )
    if ( bad_is_prime ( i ) )
    {
      if ( count ) 
      {
        fputc( ',', f );

        if (++cnt2 == ITEMS_PER_LINE)
        {
          fputc ( '\n', f );
          cnt2 = 0;
        }
        else
          fputc ( ' ', f );
      }

      fprintf ( f, "%uU", i );
      count++;
    }

  fprintf ( f, "\n};\n\n"
            "// tabela ocupa %zu bytes.\n"
            "const unsigned int primes_table_items = %u;\n",
            sizeof ( unsigned int ) * count, 
            count );

  fclose ( f );
}

Basta compilar e executar o programinha para gerar um arquivo texto contendo o código fonte de uma tabela com apenas as raízes quadradas desejadas! No caso, gerarei table.c que, como pode ser observado, contém 6541 valores, ocupando apenas 25.5 KiB:

// *** criado por gentable.c ***

// tabela começa de 3...
const unsigned int primes_table[] = {
3U, 5U, 7U, 11U, 13U, 17U, 19U, 23U,
29U, 31U, 37U, 41U, 43U, 47U, 53U, 59U, 
61U, 67U, 71U, 73U, 79U, 83U, 89U, 97U,
...
... 65447U, 65449U, 65479U, 65497U, 65519U, 65521U
}; 

// tabela ocupa 26164 bytes.
const unsigned int primes_table_items = 6541;

Para essa tabela de raízes o processamento é rápido. Considere o caso de valores de 64 bits. A máxima raiz quadrada é 4294967295. Como verificar se um valor é primo é relativamente lento, pré-calcular toda a tabela pode demorar um bocado… Existe ainda o fator espaço, que explico abaixo.

Usando essa tabela, a nossa rotina de teste good_is_prime fica assim:

extern const unsigned int primes_table[];
extern const unsigned int primes_table_items;

// Método "melhor": Faz quase a mesma coisa que acima, mas
// usa uma tabela pré calculada.
int good_is_prime ( unsigned int n )
{
  unsigned int i, sr, *p;

  switch ( n )
  {
    case 1:
    case 2:
      return 1;
  }

  if ( ! ( n & 1 ) )
    return 0;

  sr = sqrt(n);

  for ( i = 0, p = (unsigned int *)primes_table; 
        i < primes_table_items && *p <= sr; 
        i++, p++ )
  {
    if ( ! ( n % *p ) )
      return 0;
  }

  return 1;
}

Ela é bem parecida com bad_is_prime, mas usa uma tabela contendo apenas valores primos para os testes!

Nem sempre usar tabelas pré-calculadas é uma boa ideia

Em primeiro lugar, poderíamos usar uma tabela pré-calculada com todos os valores primos na faixa e a rotina final poderia ser uma simples busca binária, daí a performance da rotina seria proporcional a \log_2{n}, mas é claro que a tabela final seria enorme. Daí, escolhi armazenar apenas os valores que serão usados para verificar o divisor, eliminando os múltiplos…

A quantidade de valores primos, dado um valor máximo, pode ser aproximado (de longe!) por:

\displaystyle \Pi(x)\sim\frac{x}{\log{x}-1}

Assim, se quisermos montar uma tabela com todos os primos inferiores ou iguais à raiz quadrada do maior valor possível para um tipo, como no exemplo de unsigned int (que assume o valor máximo de 2^{32}-1), temos que o maior valor para a tabela é r_{max}=\lfloor\sqrt{2^{32}-1}\rfloor e, portanto, usando a aproximação acima, teríamos uma tabela com cerca de 17171 itens. Cada item cabe em 2 bytes (unsigned short), já que r_{max}=65535. O que nos daria um array de, no máximo, 33.5 KiB. Se usarmos unsigned int (como fiz) o array estimado ficaria com 67 KiB.

Observe o contraste com o que encontramos através de gentable.c… Temos menos da metade dessa quantidade! Mas isso não é garantido! Temos que assumir que a aproximação acima é uma quantidade média e usarmos como critério para estimar o custo da rotina.

Considere agora, 64 bits. Usando o mesmo critério, r_{max}=\lfloor\sqrt{2^{64}-1}\rfloor=4294967295, que cabe num unsigned int. Daí \Pi(r_{max})\approx497508081 itens com 4 bytes cada, ou seja, quase 2 GiB de array. Repare que dobramos o número de bits da faixa sob teste, mas o tamanho da tabela aumentou quase de 29 mil vezes.

Isso é esperado porque a estimativa é exponencial (proporcional a \frac{1}{\log{x}-1})… Então, não recomendo o método good_is_prime para valores com mais de 32 bits.

O quão bom é o “bom”?

No pior caso bad_is_prime é 10 milhões de vezes mais rápida que ugly_is_prime e good_is_prime é quase 4 vezes mais rápida que bad_is_prime (o que faz dela quase 40 milhões de vezes mais rápida que ugle_is_prime).

Estou informando esses valores, mas os medi, usando meu “contador de ciclos do homem pobre” em alguns casos:

  • Melhor caso: Um valor não primo pequeno;
  • Pior caso: Um valor primo muito grande: 4294967291
  • Um valor não primo grande cujos fatores sejam primos grandes: 144795733, por exemplo, pode ser fatorado em 12343 e 11731.

Em alguns casos, no “melhor caso” e somente às vezes, bad_is_prime ganha de good_is_prime, mas isso ocorre, provavelmente, por causa dos efeitos do cache L1 (que só tem 32 KiB!). Isso, talvez, possa ser compensado fazendo um prefetch da tabela antes de executar a rotina… Esse é especialmente o problema quando o valor não é primo! Quando a rotina precisa varrer grande parte do o array os efeitos do cache L1 entram em ação e ela fica um pouco mais lenta que a “má” rotina…

Atualização de “converter vídeos”…

Neste post aqui, escrito em 2012, usava uma versão mais antiga do ffmpeg e, de lá para cá, meu script deu uma melhorada… Eis o mais recente:

#!/bin/bash

# Agora o script aceita diversos vídeos...
if [ -z "$1" ]; then 
  echo -e "\e[1;33mUsage\e[0m: vid2mp4 <video1> [... <videoN>]";
  exit 1; 
fi

interruption() {
  [[ -e "${TMPFNAME}" ]] && rm "${TMPFNAME}"
}

# Apaga o arquivo temporário em caso de interrupção...
trap interruption INT

# Retira metadados do vídeo destino.
EXTRA_PARAMS="-map_metadata -1"

# Para todos os vídeos informados na linha de comando (aceita 'globs').
for i in "$@"; do
  # Se o arquivo não existe, mostra e tenta o próximo...
  if [ ! -f "$i" ]; then
    echo -e "\e[1;31mERROR\e[0m: Cannot find '$i'."
    continue
  fi

  # Pega o nome do codec de vídeo.
  # OBS: mediainfo poderia ser mais fácil...
  VCODEC="$(ffprobe -v quiet -select_streams v:0 -show_entries stream=codec_name -of default=nw=1:nk=1 "$i")"

  # Ajusta parâmetros de compressão para h264
  # Uso Constant Rate Frame porque me dá boa qualidade...
  VPARAMS="-c:v libx264 -crf 18"
  if [ "$VCODEC" == "h264" ]; then
    VPARAMS="-c:v copy"
  fi

  # Gosto de AC3, stereo e 160 kbps de bitrate para audio.
  APARAMS="-c:a ac3 -b:a 160k -ac 2"

  TMPFNAME="$(mktemp /tmp/tmp_XXXXXXXXXX.mp4)"
  OFNAME="${i%.*}.mp4"

  # Mostra algumas infos sobre o arquivo (usa mediainfo).
  DURATION="$(mediainfo --Inform="Video;%Duration/String3%" "$i")"
  LENGTH="$(du -h "$i" | cur -f1)"
  echo -e "\e[1;33mConverting \e[1;37m'$i'\e[0m (Duration: ${DURATION}; Size: ${LENGTH})..."

  # Finalmente, converte.
  ffmpeg -hide_banner -v quiet -stats -y -i "$i" $VPARAMS $APARAMS $EXTRA_PARAMS $TMPFNAME && \
    rm "$i" && \
    mv "$TMPFNAME" "$OFNAME"
done

O tipo NUMBER, no ORACLE Database, em C

Recentemente tenho tido a oportunidade de começar a portar um código escrito totalmente usando Oracle Call Interface, sem o uso de qualquer framework. A ideia é criar um daemon que execute processamento veloz (não necessáriamente relacionado com as consultas ao banco de dados)… Eis a primeira dúvida: Quais são os limites do tipo NUMBER, numa DDL (Data Definition Language)), em SQL?

Do manual da Oracle:

The NUMBER datatype stores fixed and floating-point numbers. Numbers of virtually any magnitude can be stored and are guaranteed portable among different systems operating Oracle Database, up to 38 digits of precision.

UAU! 38 digitos de precisão! 38 digitos em decimal, que fique bem claro! Isso é bem maior que o equivalente teórico do tipo double, da especificação IEEE 754, que tem 53 bits de precisão e, por consequência, 16 algarismos decimais:

\displaystyle d_{decimal}\approx\lceil n_{bits}\cdot\log_{10}{2}\rceil

Se n_{bits}=53, para ponto flutuante normalizados, então temos, aproximadamente, os 16 algarismos decimais significativos para o tipo double.

Adicione a essa extrema precisão o esquema de armazenamento interno para NUMBER, que é, também de acordo com os manuais, estruturado como um expoente de 1 byte seguido de uma mantissa de 20 bytes! Ou seja, a precisão binária da parte fracionária é de 161 bits (se tivermos o 1.0, implícito, como no caso de float e double). Estranhamente, isso nos daria uma precisão de 48 algarismos, não apenas 38… Suponho que a Oracle reserve os 10 bits inferiores para arredondamentos (um exagero, mas C’est la vie!).

Nos casos em que NUMBER é um inteiro, e se tiver mais que 18 algarismos, podemos usar mpz_t. No caso de não inteiros, com mais de 16 algarismos, mpf_t. Assim, quando NUMBER tem menos que 19 algarismos podemos usar int64_t (ou o tipo sb8, definido pela OCI), se tiver menos que 10, int32_t. Claro, se tivermos “escala”, com menos de 16 algarismos é seguro usar double e com menos de 8, float.

Como já discuti por esse blog, algumas vezes, não é nada prático usarmos o tipo “extendido” long double em nossos códigos. Em primeiro lugar, a precisão (em algarismos) não é lá grande coisa: 19, o que nos dá uma garantia de precisão se tivermos NUMBER, com casas decimais e precisão de até 18 algarismos… A lentidão das rotinas de ponto flutuante, que serão obrigadas a usar as instruções 80×87, não compensa esse “ganho” de apenas 2 algarismos decimais!

Embora para faixas maiores possamos usar libgmp, a conversão de dados e processamento ficarão um pouco prejudicados:

  1. Não temos como usar o tipo __int128 na OCI;
  2. Para usar a libgmp teremos que obter os dados em formato de string!

O primeiro item está ai justamente porque __int128 suporta 39 algarismos decimais em sua estrutura, para o caso de lidarmos apenas com valores inteiros, mas a OCI não o suporta!… O limite superior de __int128 é 2^{127}-1, ou 170141183460469231731687303715884105727, mas existe um outro problema: Sem alguma extensão específica, a glibc não suporta o tipo __int128 (embora o compilador o suporte)! Lembre-se que o valor pode ter parte fracionária também.

Obter o campo em forma de string não é problema. A OCI faz a conversão automaticamente à partir do momento que o campo é descrito previamente como do tipo SQLT_STR. Lembre-se apenas que o valor terá que caber no buffer da string… Embora a precisão nos diga o número de algarismos, temos que levar em conta que o valor pode ser negativo. Assim, para colocar um NUMBER(12,0) numa string teremos que ter um buffer de, pelo menos, 14 chars (os 12 algarismos, o sinal de ‘-‘, se houver, e o NUL char final). Teremos que adicionar um caracter extra ao buffer para o caso dele possuir parte fracionária, por causa do caracter ‘.’. Assim, um NUMBER(13,2) terá que ser colocado um char buffer[13+3];.

Mas, é claro, essas conversões de NUMBER para string e para mpz_t ou mpf_t (e ao contrário também) são lentas! Mas, infelizmente, se quisermos manter precisão, não tem outro jeito fácil…