free() automático no GCC

Uma das coisas que os amantes de C++ e de linguagens gerenciadas mais gostam é a “limpeza automática” que códigos escritos nessas linguagens parecem fazer. No caso de C++, objetos alocados na pilha são “destruídos” quando há perda do escopo da função. No caso de C# e Java, por exemplo, quando o objeto não é referenciado por nenhum outro, o Garbage Collector tende a livrar-se dele. Em C, aparentemente, não temos esse benefício:

void f( void )
{
  char *bufferp;
  ...

  bufferp = malloc( SIZE );
  ...
  // MEMORY LEAK: O buffer alocado não foi liberado!
}

Nada tema! GCC tem a solução!

Existe um atributo para variáveis que pode ser usado para fazer esse tipo de liberação automática. Tudo o que temos que fazer é criar a função de liberação a atrelá-la à variável:

#define AUTOFREE \
  __attribute__(( cleanup( cleanup_func ) ))

void cleanup_func( void **p ) { free( *p ) }

void f( void )
{
  AUTOFREE char *bufferp;
  ...

  bufferp = malloc( SIZE );
  ...
  // O memory leak sumiu!
}

Graças a esse atributo, a função cleanup_func é chamada, com o argumento correto, sempre que a variável sai do escopo. Isso significa que não só quando a função termina, mas em casos como esse:

void f( void )
{
  ...
  {
    AUTOFREE char *bufferp;

    bufferp = malloc( SIZE );
    ...
    // bufferp é liberado aqui, AUTOMATICAMENTE!
  }
  ...
}

Para não ter que ficar codificando uma função de cleanup (que sempre recebe um ponteiro para um ponteiro), podemos usar a glib e a macro g_autofree:

g_autofree char *bufferp;

É claro, é prudente inicializar o ponteiro com NULL para o caso de nenhuma alocação ter sido feita… A especificação da linguagem C, ISO 9989, nos diz que se passarmos NULL para free, este simplesmente não faz nada (não causa segmentation fault).

ATENÇÃO! O atributo exige que o tipo informado seja um ponteiro para o ponteiro do mesmo tipo. No entanto, (void **) apontará para qualquer tipo e não haverá problema algum, mas o compilador emitirá avisos…

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.

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…

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…

Uma outra forma de explicar o “complemento 2”

Yep! Vira e mexe eu volto aos temas mais fundamentais. Eis-me aqui, de novo, falando de aritmética inteira binária pra você… Vou tentar explicar, de novo, mas de uma outra forma, o que significa usar “sinais” em valores binários inteiros e, para isso, vou recorrer à base numérica decimal. Aquela mesma a qual estamos mais que acostumados.

Números são representações simbólicas de quantidades e, portanto, não têm “sinal”. Você consegue contar 3 coisas (para citar um exemplo de quantidade), mas não consegue contar -3 coisas. O sinal ‘-‘ ai é usado para adicionar um sentido à quantidade. Pode ser que o sentido seja que “faltam” 3 coisas ou que você queira dizer 3, mas no sentido contrário ao convencional. No último caso a representação é relativa a algum ponto tomado como origem… O fato é que você adicionou o sinal ‘-‘ para colocar um sentido extra à quantidade 3. Isso significa que essa qualidade é “artificial”, em relação à quantidade de coisas… Ainda mais: significa que esse símbolo adicional complementa o significado da quantidade (lembre-se dessa palavra!).

No sistema decimal isso é fácil fazer, especialmente quando você se acostuma com o conceito de “menos” (de falta ou “sentido contrário”), mas a coisa é mais difícil quando estamos falando de representações de valores no interior de um computador… Por exemplo, poderíamos ter bits  sinalizados se usássemos 3 níveis de tensão, por exemplo, +5 V, 0 e -5V. A tensão mais alta corresponderia a ‘1’ e a mais baixa a ‘-1’, mas, neste caso, deixaríamos de ter uma base binária para trabalharmos com um sistema ternário porque 3 níveis em cada “algarismo” caracteriza um sistema de base 3… Existe também um outro problema em usar a simbologia do ‘+’ ou ‘-‘: No sistema decimal podemos escrever a quantidade do tamanho que quisermos, se tivermos paciência e tempo, e só colocarmos o sinal ‘-‘ na frente para “inverter o sentido” do valor. Num computador, a quantidade de bits disponíveis para operações aritméticas é limitado. Então, em binário, em termos de circuitos eletrônicos, não dá para usar 3 níveis e também não dá para representar um valor indefinidamente. Um bit não pode ser “negativo” (em oposição a um “positivo”) e não podemos ter tantos bits quanto quisermos. É nesse sentido que sempre digo que não existem valores inteiros negativos em binário.

Acontece que precisamos, em certos casos, representar valores binários como se fossem negativos. Ao invés de usarmos um símbolo especial como ‘-‘ para isso usamos um bit extra… Por exemplo, com um único bit podemos representar apenas dois valores: 0 e 1. Mas, se usarmos 2 bits e fizermos de conta que o bit de mais alta ordem nos diz se o valor é positivo ou negativo, então temos a nossa representação sinalizada de um valor… Por convenção, se esse bit extra for 0, o outro bit representa um valor positivo (0b01 representa o valor +1), mas se esse bit extra for 1, então o outro bit representa um valor negativo (0b11 representa -1). É como se o último bit fosse + ou -. Mas há um problema ai…

E se tivermos uma quantidade maior de bits? O que significa 0b1111 (para citar um exemplo com apenas 4 bits) em termos de valor sinalizado? Se usarmos a definição simples de que o bit de alta ordem significa ‘-‘ e os demais bits nos dão o valor, esse exemplo deveria representar -7. Mas ele, de fato, representa -1. O bit de alta ordem complementa o significado do valor adicionando -2^N ao valor dos bits inferiores (no caso N=3, que corresponde à posição do bit “de sinal”, no valor). Ou seja, 0b1111 é convertido para decimal realizando a operação -2^3+(2^2+2^1+2^0)=-8+7=-1. Note que, no caso de usarmos 2 bits apenas, o complemento é -2. Então 0b11 é calculado como -2+1=-1… Se o bit de alta ordem for zero, o complemento simplesmente não é adicionado ao valor. Repare que, -2 é o valor 2 com a complementação ‘-‘ na frente, em decimal. Acredito que daí aparece o termo “complemento 2”.

Outra explicação interessante é o do porquê do “macete” de inverter os bits e somar 1 se o último bit estiver setado, para obtermos a representação do valor como se fosse negativo. Note que, com dois bits, temos o conjunto de valores binários B={0b00, 0b01, 0b10, 0b11} que pode ser dividido em dois subconjuntos (P=\{0b00,0b01\} e M=\{0b10,0b11\}, onde B=P\cup M (dei o nome dos subconjuntos de P e M para significarem Plus e Minus, o conjunto B é dos Bits). O conjunto B é assimétrico no que se refere aos valores extremos! Do lado positivo temos, em decimal, 0 e +1, e do lado negativo, -1 e -2. Isso quer dizer que o valor -2 não pode ser “espelhado” para obtermos a representação “positiva” +2, usando apenas dois bits. Quer dizer mais ainda: temos 1 quantidade a mais do lado negativo. Assim, para obtermos -1 à partir de 1, já que temos uma quantidade extra do lado negativo, temos que “somar um” à inversão dos bits (“menos” 0b01 é o seu inverso, 0b10,  “mais 1”). No sentido contrário teremos que “tirar” esse um que colocamos, “somando” +1 ao valor negativo (x-(-1)=x+1)… Essa é a origem do “macete”.

Listas circulares, do jeito Knuth (e do Linux)…

Já falei sobre listas encadeadas ao estilo Sedgewick aqui, mas eis uma maneira de implementar listas que fica ainda mais simples… O header abaixo mostra a implementação atual do MyToyOS, devidamente copiado do estilo Knuth e Linus de listas circulares:

#ifndef __LIST_INCLUDED__
#define __LIST_INCLUDED__

// Essa é a estrutura de um nó de uma lista, 
// mas também do nó "batente" ou "cabeça" da
// lista. E, uma vez que mantemos o nó "cabeça",
// a lista é "circular", para facilitar a 
// manipulação (sempre haverá um nó cabeça!).
// A lista "vazia" tem apenas a cabeça, apontando
// para si própria.
//
// Note que a lista é double linked e circular.
//
// COMO USAR:
//
// Suponha que você queira manter uma "lista de
// retângulos", onde um retângulo tenha a estrutura:
//
//   struct rect {
//     int left, top, right, bottom;
//   };
//
// A lista pode ser definida como:
//
//  struct _list_head rect_list_head;
//  INIT_LIST_HEAD(&rect_list_head);
//
// É claro, podemos inicializar a lista diretamente:
//
//  struct _list_head rect_list_head = 
//             EMPTY_LIST(rect_list_head);
//
// A última forma é útil para inicialização de listas
// locais estáticas e globais.
//
// No exemplo dos retângulos, os nós da lista, DEVEM
// ser definidos como:
//
//   struct rect_node {
//     struct _list_head next_rect;  // Isso tem que estar
//                                   // no início!
//     struct rect rc;
//   };
//
// Para adicionar um retângulo no fim da lista:
//
//   _list_add_tail(&rect_list_head, 
//                  (struct _list_head *)&rc_node);
//
// Para adicionar um retângulo no início da lista:
//
//   _list_add_after(&rect_list_head, 
//                   (struct _list_head *)&rc_node);
//
// Para retirar um retângulo da lista:
//
//   _list_unlink((struct _list_head *)&rc_node);
//
// Para percorrer a lista, do início ao fim:
//
//   struct _list_head *p;
//   _list_foreach(p, &rect_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Para percorrer a lista do fim para o início:
//
//   struct _list_head *p;
//   _list_foreach_reverse(p, &rc_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Infelizmente AINDA não criei a rotina para 
// percorrer toda a lista à partir de um nó 
// específico. Mas, você pode fazer isso guardando
// o nó en questão, percorrendo a lista em uma
// direção até o nó head (_list_foreach*) e 
// depois percorrer do head para o nó guardado. 
// Por exemplo, para frente:
//
//  struct _list_head *p = (struct _list_head *)&rc_node;
//  struct _list_head *q = p->prev;
//  struct _list_head *r = p;
//  _list_foreach(r, q)
//  { ... }
//  _list_forearch(r, &rc_list_head)
//  {
//    if (r == q) break;
//  }
//
// Repare também que, embora tenhamos um "batente", o 
// macro aceita qualquer nó da lista como "alvo". Mas 
// é necessário cuidado porque o "batente" real não tem
// dados.
//

// Estrutura da "cabeça" da lista.
struct _list_head { 
  struct _list_head *next;
  struct _list_head *prev; // Funciona como 'tail' para a 
                           // cabeça da lista.
};

// Os macros citados acima...
#define INIT_LIST_HEAD(name) \
  { (name)->next = (name)->prev = (name); }
#define EMPTY_LIST(name) \
  { .next = .prev = &(name); }

// Essencialmente a mesma coisa que acima, mas lida com o
// ponteiro para a "cabeça" da lista.
static inline void _list_init(struct _list_head *head)
{
  head->next = head->prev = head;
}

// A lista está vazia? Se next aponta para a cabeça, está!
static inline _Bool _list_empty(struct _list_head *head)
{ return head == head->next; }

// Insere o novo item depois do item "prev".
static inline void _list_add_after(struct _list_head *prev, 
                                   struct _list_head *_new)
{
  struct _list_head *next;
  struct _list_head *prev;

  next = head->next;
  prev = head->prev;

  if (_list_empty(head)) // Caso especial!
    head->prev = _new;
  _new->next = next;
  _new->prev = prev;
  head->next = _new;
}

// Addiciona um item no fim da lista.
static inline void _list_add_tail(struct _list_head *head, 
                                  struct _list_head *_new)
{
  _list_add_after(head->prev, _new);
}

// Apaga um nó da lista.
// OBS: Cuidado ao usar free(). o nó pode ser a cabeça!
static inline void _list_unlink(struct _list_head *node)
{
  // Note que se a lista estiver vazia, nada acontece.
  struct _list_head *next;
  struct _list_head *prev;

  next = node->next;
  prev = node->prev;
  prev->next = node->next;
  next->prev = node->prev;
}

// Percorrer uma lista pode ser feito com:
//
// struct _list_head *p = &mylist;
//
// for (p = mylist->next; p != &mylist; p = p->next)
// { ... }
//
// Dai o macro abaixo (tanto p quanto head são ponteiros:
//
// OBS: É bom lembrar que a cada iteração do loop o 
//      ponteiro de controle apontará para o próximo
//      item da lista (ou para o anterior se o sentido
//      for reverso) até que ele retorne para a "cabeça".
//      Assim, usá-lo para deletar itens na lista deve
//      ser feito com cuidado.
#define _list_foreach(p,head) \
  for (p=head->next; p != head; p=p->next)

#define _list_foreach_reverse(p,head) \
  for (p=head->prev; p != head; p=p->prev)

#endif

Por que as funções estão definidas no header e não num módulo C separado? Ora, as rotinas são tão simples que posso fazê-las inline. Rotinas em módulos separados, necessariamente, não são “inlineáveis”. Os macros _list_foreach e _list_foreach_reverse não podem ser funções porque são atalhos para a construção do loop que percorrerá toda a lista… Aliás, um conselho: Cuidado com o código abaixo

struct _list_head *p;
_list_foreach(p, &list_of_rects)
{
  _list_unlink(p);
}

Dependendo do que você fizer com os ponteiros do nó apontado por p, o loop não fará o que você quer (mas, do jeito que está, deve funcionar, porque o componente next de p continua apontando para o próximo item, embora o nó não faça mais parte da lista… No fim das contas apenas o a cabeça da lista sobrará (não será “desligada” da lista)…

Note também que nenhuma das rotinas é responsável por alocar ou dealocar a estrutura de um nó. Tudo o que elas fazem são as ligações corretas para manter a lista. É sua responsabilidade alocar ou liberar nós, incluindo a “cabeça”, é sempre deixada na lista no caso do desligamento de todos os nós…

A característica circular da lista torna fácil algumas operações (principalmente _list_foreach e sua contraparte).

Um macete usando NULL pointers…

Você provavelmente aprendeu que ponteiros NULL são perigosos. Eles causam “segmentation faults” ou “General Protection Faults” e devem ser evitados. Eis o detalhe: Isso só acontece se o ponteiro for derreferenciado!

O macete abaixo mostra um jeito de obter o offset de um membro de uma estrutura sem usar o macro offsetof, definido em stddef.h, pelo menos desde a versão ISO 9989:1999 da linguagem C:

#define offsetof(T,member) \
  ( (unsigned int) &( (T *)0 )->member )

Notou o uso do NULL pointer? Pois é! Não estamos derreferenciando o bicho, só calculando o endereço efetivo do membro da estrutura… Se você fizer:

Yep! MS-DOS!

O membro z da estrutura S está no offset 8 (Faz sentido: x está no início da estrutura, portanto no offset 0. Como cada float ocupa 4 bytes, y estará no offset 4)… Fiz isso no MS-DOS, usando o Borland C++ 3.1 para mostrar para vocês que isso sempre foi válido, desde os primórdios.

O que essa macro faz, na verdade? Ora, o endereço efetivo é calculado com base no endereço do objeto, cujo endereço está no ponteiro… Ao usar o endereço 0 (zero), tudo o que temos é o offset do membro da estrutura!