O problema das pizzas – Ou, o problema da ignorância da matemática elementar!?

Bem… não foi surpresa nenhuma pra mim perceber que algumas pessoas não conseguem aplicar conhecimentos fundamentais no dia a dia. Eis um problema (bem simples, que um estudando ensino fundamental deveria saber resolver, e um adulto também!) que propus, recentemente:

“Você resolveu comprar pizza para a família toda. Uma pizzaria oferece pizzas “médias” com raio de 30 cm e “grandes” com raio de 45 cm, ao preço de R$ 40,00 e R$ 50,00 cada uma, respectivamente. Você compraria duas pizzas médias ou uma grande?”

O detalhe é que o preço é irrelevante no problema. O que se quer saber é qual das duas configurações vai te dar mais pizza para comer: Duas médias ou uma grande?

Como disse, não é surpresa ver que a maioria das pessoas escolhe as duas pizzas médias, achando que terá mais pizza do que uma grande. Infelizmente a geometria plana elementar desmente isso, já que a “quantidade” de pizza é medida pela área da circunferência… Quanto a isso, obviamente o problema considera que uma pizza seja isto:

ISSO é uma pizza!

Fazendo um cálculo rápido, qualquer um pode observar que uma pizza grande, do problema proposto, é 12,5% maior que duas pizzas médias (área da pizza média. 900\pi, área da pizza grande, 2025\pi)! Isso levanta a questão: Será que estou perdendo dinheiro toda vez que compro pizzas? Quando é vantajoso comprar duas médias ao invés de uma grande? Well…

Considere r como sendo o raio da pizza média e R como sendo o raio da pizza grande. Valerá a pena comprar duas pizzas médias ao invés de uma grande se:

\displaystyle 2\pi r^2 > \pi R^2

Ou seja, \frac{R^2}{r^2} < 2 \Rightarrow R < r\sqrt{2} (estou ignorando o valor negativo que satisfaz a inequação por motivos óbvios!) . Isso quer dizer que o raio R tem que exceder menos que 41% do radio r para ser vantajoso comprar duas médias… No exemplo do problema, se a pizza grande tiver menos que 42 cm (30\sqrt{2}\approx42,4), vale à pena comprar duas médias…

Ahhh… Esse tipo de racionalização também deveria ser óbvio para qualquer pessoa que passou por uma escola…

Anúncios

Teimosia…

Tem gente teimosa que insiste em fazer as coisas da forma errada… Neste artigo eu informei a meus leitores, explicitamente, que a string que deve ser passada para a função setlocale segue os padrões ISO 639 e ISO 3166. Alguns acreditam que isso só vale para ambientes Unix e que no Windows a coisa é “mais fácil”… A insistência, é claro, é pela passagem de strings como “Portuguese” ou “Portugues”, como em:

// Isto está ERRADO!!!
setlocale(LC_ALL, "Portuguese");

A função setlocale(), como descrita na MSDN Library (aqui), diz claramente: “The set of locale names supported by setlocale are described in Locale Names, Languages, and Country/Region Strings.” e o tópico em questão nos diz: “The locale name form—for example, en-US for English (United States) or bs-Cyrl-BA for Bosnian (Cyrillic, Bosnia and Herzegovina)—is preferred“.

Mais um exemplo para comprovar que, mesmo o Windows, usa o padrão para locale, é usar uma função da Win32 API para obter o locale padrão do sistema:

#include <stdio.h>
#include <wchar.h>
#include <windows.h>

void main(void)
{
  wchar_t locale[LOCALE_NAME_MAX_LENGTH+1];

  // Usando Win32 API para obter o locale padrão!
  // GetSystemDefaultLocaleName() exige um ponteiro
  // para wide string.
  GetSystemDefaultLocaleName(locale, 
                             LOCALE_NAME_MAX_LENGTH);
  wprintf(L"%ls\n", locale);
}

Ao compilar e executar o programinha acima, usando o MinGW64, obtemos:

$ x86_64-w64-mingw32-gcc -O2 -o locale.exe locale.c
locales.c: In function ‘main’:
locales.c:8:3: warning: implicit declaration of function ‘GetSystemDefaultLocaleName’ [-Wimplicit-function-declaration]
   GetSystemDefaultLocaleName(locale, LOCALE_NAME_MAX_LENGTH);
   ^
... Copiando o locale.exe para o Windows e executando:
C:\Work> locale
pt_BR

Yep… tem esse aviso ai (provavelmente estou esquecendo de definir algum símbolo para compilar código para versão do Windows superior ao Vista), mas o linker não reclamou, então ele conseguiu resolver a referência corretamente…

Note que a própria Win32 API prefere o padrão ISO!

Mais uma vez: Nem sempre é bom desenvolver diretamente em assembly!!!

Sim… de fato, a máxima “Não existe melhor otimizador do que o está entre suas orelhas” continua sendo verdadeira, só que essa massa de carne nem sempre realiza o melhor trabalho. Eis um caso onde uma rotina simples deveria ser mais rápida se feita em ASM:

uint16_t cksum(void *data, size_t length)
{
  uint32_t sum;
  uint16_t *p = data;
  _Bool rem;

  sum = 0;
  rem = length & 1;
  length >>= 1;

  while (length--)
    sum += *p++;

  if (rem)
    sum += *(uint8_t *)p;

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

  return ~sum;
}

Essa é a implementação do cálculo de CHECKSUM de 16 bits, de acordo com a RFC 1071 (aqui). O código é bem simples e deveria gerar uma listagem em assembly tão simples quanto, mas quando você compila com a máxima otimização consegue ums listagem enorme que, inclusive, na plataforma x86-64, usa até SSE!

A minha implementação da rotina acima, em puro assembly e “otimizada”, para a plataforma x86-64, seria essa:

  bits 64

  section .text

  global cksum2

; uint16_t cksum2(void *data, size_t length);
  align 16
cksum2:
  xor   eax,eax   ; sum = 0;
  xor   ecx,ecx   ; RCX será usado como índice...
  shr   rsi,1     ; # de words!
  jnc   .even     ; Se CF=0, RSI era par!

  ; Ao invés de adicionar o byte extra no final,
  ; optei pelo início.
  movzx dx,byte [rdi]
  add   ax,dx
  inc   rdi
  jmp   .even

  ; Loops geralmente são críticos. Note que optei
  ; por colocar o teste no final, deixando o salto
  ; conticional para trás para não ferir o
  ; algoritmo estático do "branch prediction".
  ; Também, o ponto de entrada alinhado aos 16 bytes
  ; ajuda com possíveis efeitos negativos com o 
  ; cache L1i...
  align 16
.loop:
  add   ax,[rdi+rcx*2]
  adc   ax,0
  dec   rsi        ; length--;
  inc   rcx        ; próxima word...
.even:
  test  rsi,rsi    ; length == 0?
  jnz   .loop      ; não! continua no loop.
  
  not   ax         ; sum = ~sum;
  ret

Compare essa minha rotina com a gerada pelo compilador:

cksum:
  mov   r11,rsi
  shr   rsi
  push  rbp
  and   r11d,1
  test  rsi,rsi
  push  rbx
  je    .L2
  mov   rdx,rdi
  lea   r10,[rsi-1]
  and   edx,15
  shr   rdx
  neg   rdx
  and   edx,7
  cmp   rdx,rsi
  cmova rdx,rsi
  cmp   rsi,10
  ja    .L74
  mov   rdx,rsi
.L3:
  cmp   rdx,1
  lea   rcx,[rdi+2]
  movzx eax,WORD PTR [rdi]
  lea   r8,[rsi-2]
  je    .L5
  movzx r8d,WORD PTR [rdi+2]
  lea   rcx,[rdi+4]
  add   eax,r8d
  cmp   rdx,2
  lea   r8,[rsi-3]
  je    .L5
  movzx r8d,WORD PTR [rdi+4]
  lea   rcx,[rdi+6]
  add   eax,r8d
  cmp   rdx,3
  lea   r8,[rsi-4]
  je    .L5
  movzx r8d,WORD PTR [rdi+6]
  lea   rcx,[rdi+8]
  add   eax,r8d
  cmp   rdx,4
  lea   r8,[rsi-5]
  je    .L5
  movzx r8d,WORD PTR [rdi+8]
  lea   rcx,[rdi+10]
  add   eax,r8d
  cmp   rdx,5
  lea   r8,[rsi-6]
  je    .L5
  movzx r8d,WORD PTR [rdi+10]
  lea   rcx,[rdi+12]
  add   eax,r8d
  cmp   rdx,6
  lea   r8,[rsi-7]
  je    .L5
  movzx r8d,WORD PTR [rdi+12]
  lea   rcx,[rdi+14]
  add   eax,r8d
  cmp   rdx,7
  lea   r8,[rsi-8]
  je    .L5
  movzx r8d,WORD PTR [rdi+14]
  lea   rcx,[rdi+16]
  add   eax,r8d
  cmp   rdx,8
  lea   r8,[rsi-9]
  je    .L5
  movzx r8d,WORD PTR [rdi+16]
  lea   rcx,[rdi+18]
  add   eax,r8d
  cmp   rdx,10
  lea   r8,[rsi-10]
  jne   .L5
  movzx r8d,WORD PTR [rdi+18]
  lea   rcx,[rdi+20]
  add   eax,r8d
  lea   r8,[rsi-11]
.L5:
  cmp   rsi,rdx
  je    .L6
.L4:
  mov   rbx,rsi
  sub   r10,rdx
  sub   rbx,rdx
  lea   r9,[rbx-8]
  shr   r9,3
  add   r9,1
  cmp   r10,6
  lea   rbp,[0+r9*8]
  jbe   .L7
  pxor  xmm0,xmm0
  lea   r10,[rdi+rdx*2]
  xor   edx,edx
  pxor  xmm2,xmm2
.L8:
  movdqa  xmm1,XMMWORD PTR [r10]
  add   rdx,1
  add   r10,16
  cmp   r9,rdx
  movdqa  xmm3,xmm1
  punpckhwd xmm1,xmm2
  punpcklwd xmm3,xmm2
  paddd xmm0,xmm3
  paddd xmm0,xmm1
  ja    .L8
  movdqa  xmm1,xmm0
  sub   r8,rbp
  lea   rcx,[rcx+rbp*2]
  psrldq  xmm1,8
  paddd xmm0,xmm1
  movdqa  xmm1,xmm0
  psrldq  xmm1,4
  paddd xmm0,xmm1
  movd  edx,xmm0
  add   eax,edx
  cmp   rbx,rbp
  je    .L6
.L7:
  movzx edx,WORD PTR [rcx]
  add   eax,edx
  test  r8,r8
  je    .L6
  movzx edx,WORD PTR [rcx+2]
  add   eax,edx
  cmp   r8,1
  je    .L6
  movzx edx,WORD PTR [rcx+4]
  add   eax,edx
  cmp   r8,2
  je    .L6
  movzx edx,WORD PTR [rcx+6]
  add   eax,edx
  cmp   r8,3
  je    .L6
  movzx edx,WORD PTR [rcx+8]
  add   eax,edx
  cmp   r8,4
  je    .L6
  movzx edx,WORD PTR [rcx+10]
  add   eax,edx
  cmp   r8,5
  je    .L6
  movzx edx,WORD PTR [rcx+12]
  add   eax,edx
.L6:
  test  r11,r11
  lea   rdi,[rdi+rsi*2]
  je    .L71
.L17:
  movzx edx,BYTE PTR [rdi]
  add   eax,edx
  mov   edx,eax
  shr   edx,16
  test  edx,edx
  je    .L75
.L49:
  movzx eax,ax
  add   eax,edx
.L71:
  mov   edx,eax
  shr   edx,16
  test  edx,edx
  jne   .L49
.L75:
  not   eax
.L67:
  pop   rbx
  pop   rbp
  ret
.L74:
  test  rdx,rdx
  jne   .L3
  mov   r8,r10
  mov   rcx,rdi
  xor   eax,eax
  jmp   .L4
.L2:
  test  r11,r11
  je    .L76
  xor   eax,eax
  jmp   .L17
.L76:
  mov   eax,-1
  jmp   .L67

UAU! Obviamente a minha rotina é mais rápida que esse caminhão de instruções, certo? (aliás, repare nas instruções entre os labels .L8 e .L7! hehe)

Infelizmente os testes mostram que não! Comparando o cálculo do checksum de um buffer de 2 KiB (menos 1 byte para termos um buffer de tamanho impar, ou seja, o pior caso), a minha rotina é 5 vezes mais lenta que a gerada pelo compilador! Num de minhas máquinas de teste obtive, para cksum(), 3432 ciclos e para cksum2(), 16872!

É interessante notar que se mudarmos o código em C para efetuar a adição do byte isolado, se houver um, a performance vai ser semelhante à obtida em cksum2():

uint16_t cksum3(void *data, size_t length)
{
  uint32_t sum;
  uint16_t *p = data;

  sum = 0;
  if (length & 1)
    sum += *(uint8_t *)p++;
  length >>= 1;

  while (length--)
    sum += *p++;

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

  return ~sum;
}

E, também, se mudar o meu código para efetuar a soma do byte adicional no final, se houver um, como na rotina original, a performance continuará tão ruim quanto:

  align 16
cksum4:
  xor   eax,eax
  xor   ecx,ecx
  mov   edx,esi
  and   edx,1
  shr   rsi,1
  jmp   .even

  align 16
.loop:
  add   ax,[rdi+rcx*2]
  adc   ax,0
  dec   rsi
  inc   rcx
.even:
  jnz   .loop
  test  edx,edx
  jz    .exit
  add   ax,[rdi+rcx*2]
  adc   ax,0
.exit:
  not   ax
  ret

Ou seja, o compilador está tomando conta dos possíveis efeitos no cache e desenrolando os loops para que atinja a melhor performance possível, mesmo que, para isso, gere um código bem maluco. Coisa que apenas com muita experiência eu ou você poderíamos fazer…

Novamente, sempre meça a performance de seus códigos e não pense que só porque está em “assembly” é que você conseguirá a melhor performance!

Ambientes gráficos – Não é tão simples como você pensa!

Um leitor amigo me pediu para falar um cadinho sobre ambientes gráficos. Infelizmente o assunto é tão extenso que é meio difícil cobrir aqui. Pretendo mostrar, superficialmente, uma técnica usada ma maioria das GUIs…

Já reparou como suas janelas são desenhadas na tela? Observe isso:

01-2-windows

Para os propósitos deste texto, esqueça os efeitos especiais como a sombra projetada da janela do terminal sobre a janela do browser e de ambas as janelas sobre o desktop.

A janela do browser, embaixo da do terminal, é parcialmente desenhada. O pedaço onde o terminal está não pode aparecer para o usuário (a não ser que você seja um daqueles que goste de usar terminais “transparentes”). No caso de janelas com conteúdos estáticos isso pode parecer bem simples de fazer. Mas, e quanto a vídeos?

Nada de dstrações com a beleza da moça!
Nada de distrações com a beleza da moça!

Vídeos são apenas sequências de imagens desenhadas em intervalos regulares para causar a sensação de movimento. No caso do vídeo da moça acima (linda, não?), o mesmo pedaço da janela, à esquerda, não é tocado pelas imagens que compõem o vídeo… Como isso é feito?

A GUI divide a janela sobreposta em “sub janelas” ou regiões. Ele faz isso porque só sabe manipular áreas retangulares e, então, a divisão em regiões da janela do vídeo fica assim:

grab3-2-regions

No exemplo acima usei as cores verde e azul para exemplificar a divisão da janela em regiões… Todos os pixels que não estão nessas áreas simplesmente não são desenhados. Mas, como fica quando temos várias janelas sobrepostas? A GUI monta uma lista de regiões retangulares, por exemplo:

03-3-regions

Aqui temos 3 “regiões” (verde, azul e vermelha).

Obviamente que quanto mais janelas na tela, mais complexa tende a ficar. Especialmente se algum efeito especial é usado (sombras e janelas não retangulares, por exemplo). Sem contar que, às vezes, teremos que lidar com casos onde a janela é subdividida em diversas regiões de apenas 1 pixel…

Hoje em dia é mais provável que as GUIs usem stencil buffers para mascarar os bits que não serão plotados. No caso do Linux, por exemplo, os ambientes X11 modernos costumam usar OpenGL para esse fim. É provável que cada janela tenha seu próprio stencil buffer e o sistema mantenha uma lista das janelas visíveis e suas coordenadas z (quem está na frente de quem). Assim, para cada janela, as janelas com z>z_{corrente} são desenhadas no stencil buffer da janela em questão (apenas os contornos e preenchidas de branco), criando a máscara.

Assim, quando a GUI for, de fato, desenhar a janela, basta aplicar o stencil… É como serigrafia: As áreas mascaradas não deixam passar a tinta… Isso evita a complicação de manter uma lista de regiões. E, como raster operations são o default nas placas de vídeo atuais, é pouco provável que existam problemas com processamento ao lidarmos com áreas grandes ou com múltiplas subdivisões.

Senhas

Acho que você, provavelmente, já topou com esse tipo de regra para criação de senhas: Mínimo de 6 caracteres, contendo letras, números e caracteres especiais. E troque a senha de tempos em tempos… A maioria das empresas que conheço usam essas regra simples. Sabe de onde elas vieram?

Tem um monte de gente que acha que isso é uma daquelas coisas de “senso comum”, mas a regra veio de uma recomendação do NIST (National Institute of Stantards and Technology), um instituto governamental norte-americano que dita normas usadas pelo governo e que acabam sendo acatadas pela indústria em geral… Pois bem, este padrão foi criado em 2009 e aposentado em 2016 (veja aqui) porque este tipo de metodologia não ajuda muita coisa, ao contrário do que pensam alguns “especialistas” em segurança! Na realidade, só atrapalham o maior interessado: o usuário!

Hoje, com GPUs mais poderosas, é possível “adivinhar” uma senha de 6 caracteres em poucos segundos, usando força bruta! Alguns algoritmos conseguem testar bilhões de senhas possíveis por segundo. Uma senha montada de acordo com a regra citada anteriormente, mesmo considerando que as letras possam ser diferenciadas entre maiúsculas e minúsculas, pode ser quebrada em menos de 1 dia num PC (alguns minutos num supercomputador ou num cluster de GPUs).

Recomendo que você dê uma olhada no site GPC’s Password Haystacks para avaliar a sua senha…

Um outro esquema usado é a transmissão e armazenamento de hashs (MD5 ainda é usado em aplicações, hoje em dia!) e, ainda por cima, com um “salzinho” para tornar a coisa mais difícil… Acontece que o argumento acima continua valendo: Embora uma senha com hash SHA256 seja mais difícil de “quebrar”, processadores e GPUs modernas são capazes de testarem, literalmente, bilhões de possibilidades por segundo… Se você usar um cluster de GPUs, através de OpenCL, literalmente trilhões de testes por segundo podem ser feitos… Eis um deles:

Computador do meio com 7 placas GTX1080 em SLi, só para cracking!</small)
Computador do meio com 7 placas GTX1080 em SLi, só para cracking!

O software usado? Está disponível gratuitamente e é FOSS. Por exemplo, o ocl-hashcat e o rainbowcrack.

Senhas de 6 caracteres e, hoje em dia, inferiores a 12 (até 2016, pelo menos!), são facilmente quebráveis… Mas, e quanto a trocar a senha frequentemente?

Existe o fator psicológico aqui… Forçar o usuário a trocar a senha frequentemente faz com que ele tenta a usar a mesma senha, com algumas pequenas modificações… Por exemplo, se a senha for “secreta” (exemplo de senha!), das próximas vezes ele mudará para “secreta2”, “secreta3”, “secreta!”, “secreta?!” etc. É claro que o usuário tende a fazer isso porque não precisará se lembrar das novas senhas, mas apenas da pequena modificação.

O que fazer?

A primeira coisa é evitar usar esquemas de autorização de acesso que peçam login/senha. Por exemplo, uma grande quantidade de sites vêm usando a estrutura de autenticação do Google e do Facebook para permitirem acesso de usuários… O Google e o Facebook tiveram um trabalhão para criarem um esquema de login que seja seguro o suficiente e, como eles fornecem isso como serviço, tendem a manter o esquema cada vez mais seguro… Se seu sistema é online, usar a autenticação do Google pode ser uma boa idéia, especialmente por causa do Android…

Mas, se sua aplicação não for online, ao invés de usar login e senha, vale a pena investir um pouco num “security token”… Esses “tokens” podem ser usados na forma de smartcards, cartões RFI ou pendrives. Em essência, você tem um certificado do usuário, assinado pelo proprietário do software, que lhe permitirá tanto verificar a autenticidade da identidade do usuário (assumindo que só ele tem o token) quanto a autorização para o acesso… NENHUMA SENHA É NECESSÁRIA!

Mas, mesmo que login/senha seja algo que você não quer abrir mão, forçar um conjunto de regras pode ser uma boa ideia desde que matematicamente eficientes (“senso comum” não vale de nada!)… Por exemplo: Forçar o mínimo de 6 caracteres com letras, números e especiais é boboca porque uma senha como “aaaa@1” é válida e, provavelmente, uma das primeiras que vai ser testada num método de força bruta… A regra mais interessante é garantir que a entropia da senha seja maior que um certo valor… Infelizmente, calcular entropia de informação é algo um tanto quanto complicado (veja aqui) e, quando se aplica a senhas, meio subjetivo…

Não tema! Um dos meios mais seguros, do ponto de vista do usuário, atualmente, é o uso de passphrases e pode ser exemplificado por essas tirinhas do xkcd:

password_strength

Como qualquer pessoa pode perceber, bolar uma frase sem sentido, engraçada e que lembre alguma coisa apenas para o usuário em questão, além de aumentar a quantidade de bits de entropia (calculado como n\lg\,c, onde c é a quantidade de caracteres que podem ser usados numa única posição e n é o tamanho da string), torna a senha muito mais fácil de lembrar e difícil de ser “adivinhada”.

Durante algum tempo usei a senha (cunhada por um conhecido) “chuta que dá, certo?”…

A arquitetura “maluca” dos PCs

Uma das grandes dificuldades de desenvolver hardware e software de baixo nível (sistemas operacionais) para o PC-AT é a arquitetura dessa “Advanced Technology” (o AT, depois do PC). Hoje os PCs tinham que ser conhecidos como PC-PT (Patched Tecnology ou “tecnologia remendada”, não confundir com o partido, senão eu estaria usando um Mac aqui!) .Os PCs são monstrengos que carregam características legadas desde seu surgimento, em 1981.

Eis alguns exemplos…

Acesso à memória:

Até o início dos anos 80 os microcomputadores que reinavam eram os de 8 bits, baseados em processadores da Zilog (Z-80) ou MOS Technology (6502). Em 1981 a IBM lançou o PC original, totalmente “open source”, digamos assim, como o primeiro computador pessoal (Personal Computer, ou PC) com arquitetura de 16 bits, baseado no processador da Intel 8088… Isso foi novidade porque:

  • Era um computador da IBM, ora bolas;
  • Tinha duas vezes mais bits!!!
  • Processadores Intel não eram considerados tão bons assim;
  • Finalmente existia um padrão a ser seguido…

A terceira afirmação vem do fato de que, diz a lenda, a Zilog foi uma empresa formada de engenheiros dissidentes da Intel — os mesmos do projeto do 8080. Eles melhoraram um bocado os barramentos (nada daquela história de multiplexar dados com endereços!), algumas instruções de manipulação de 16 bits foram adicionadas e o conjunto de instruções ficou mais interessante: Pelo menos no contexto dos mnemônicos, nada da diferença entre MVI e MOV, por exemplo.

Também diz a lenda que a escolha pelo processador da Intel para os PCs deveu-se ao aconselhamento da Microsoft (maldição!), que tinha sido contratada para desenvolver o PC-DOS (mais tarde renomeado de MS-DOS)… A ideia original da IBM era adotar o CP/M como padrão, mas a Digital Research, dona do sistema, não conseguiu entregar no prazo o CP/M-86… Não é à toa que o MS-DOS lembre muito o CP/M… Suspeito, mas não tenho como confirmar, que a IBM, antes de adotar os processadores Intel, tinha a intenção de criar o PC com base nos MC68000 — o que seria uma jogada de mestre, já que esse processador já era usado em alguns mainframes!

Outra grande vantagem é que, mesmo sendo um microcomputador com arquitetura de 16 bits, o barramento de endereços permitia o uso de 20 bits, ou 1 MiB de memória acessível. Na época, os computadores de 8 bits tinham, no máximo, 64 KiB de memória (alguns usavam o esquema de chaveamento de bancos de memória para usar mais, mas era raro!)… Eu mesmo já tive um Apple ][+ com 48 KiB de RAM!

Acontece que para conseguir um endereço de 20 bits usando registradores de 16 bits foi necessário adotar um esquema estranho, típico das gambiarras da Intel… A memória era dividida em blocos de 64 KiB, mas, cada bloco começa num endereço físico múltiplo de 16. Ou seja, existem “segmentos” de memória com 64 KiB de tamanho… O endereço físico é, então, calculado com base em dois registradores: Um “seletor” de segmento e um offset:

\displaystyle Addr_{fisico}=(segmento\,shl\,4)+offset

Tanto “segmento” quando “offset” têm 16 bits de tamanho. Isso cria um problema: Se ambos forem 0xffff, o endereço físico resultante terá 21 bits de tamanho: (0xffff\,shl\,4)+0xffff=0x1ffef. Repare no ‘1’, mais à esquerda!

A intel resolveu incorporar esse “problema” na nova geração de processadores, o 80286 e o “bug” virou “feature”… Surge também o PC-AT que, para manter compatibilidade com o velho PC, incorporou um sinal chamado “Gate A20“. O “gate” aqui é uma porta lógica AND que mascara o bit A20 do barramento de endereços. Ou seja, se o sinal do “Gate A20” estiver desabilitado, o bit A20 será automaticamente zerado, senão a porta deixará passar o A20 fornecido pelo processador.

Numa época onde temos capacidade de memória acima de 8 GiB o Gate A20 perdeu sua serventia, não é? Infelizmente não! Ele ainda existe!

Outro problema com o esquema segmento:offset é que é possível codificar o mesmo endereço físico de memória de várias formas possíveis. Tomemos o exemplo do endereço físico de 20 bits 0x00123… Ele pode ser escrito como 0x0012:0x0003, 0x0011:0x0013, 0x0010:0x0023, … 0x0000:0x0123. Isso, para quem está aprendendo assembly é uma confusão dos diabos!

No modo protegido isso foi corrigido mudando-se a semântica do que seria um “segmento”. A parte “segmetno” virou um “seletor” de uma tabela que descreve o bloco de memória acessível pelo offset (mais uma gambiarra da Intel).

Diversos “modos” de operação diferentes:

Seu processador pode funcionar em 4 modos diferentes:

  • Modo real: Igualzinho ao velho PC com o 8088, mas usando os registradores e instruções estendidas (EAX, EBX, …). Ainda é possível acessar apenas 1 MiB de memória física (mais 64 KiB se o gate A20 estiver habilitado);
  • Modo protegido (32 bits): O esquema segmento:offset é completamente diferente. Pode-se acessar até 4 GiB de memória física (ou 64 GiB de memória virtual). Existem privilégios e isolamento de código e dados entre processos. Suporta multithreading com auxílio do processador;
  • Modo protegido (32 bits com extensões de 64 bits): Mesma coisa que o modo de 32 bits acima, mas permite acessar mais memória (até 256 TiB de memória física, ou 4 PiB de memória virtual). Estende os registradores para 64 bits (RAX, RBX, …). Adiciona mais registradores… No entanto, continua sendo um modo de 32 bits, chamado pela Intel de IA-32e;
  • Modo Virtual 8086: Emula o modo real dentro do modo protegido;
  • Modo SMM (System Management Mode): Usado para diagnósticos e é um modo completamente diferente dos acima.

Nos modos protegidos os registradores seletores de segmento indicam uma entrada numa tabela que contém a descrição do bloco de memória que pode ser endereçado… É como se você dissesse: “use o segmento nº 1” e, na primeira entrada da tabela, temos: “este segmento começa em 0x00000000, tem 4 GiB de tamanho, só pode ser lido e pode conter instruções executáveis, e só pode ser acessado por processos com privilégio 0″… Se um processo com privilégio 3 (o menor possível) tentar acessar um dado deste segmento, acontece um erro. Se qualquer processo tentar escrever nesse segmento, acontece um erro. Se usarmos um offset que não esteja dentro da faixa de endereços permitidos para esse segmento, acontece um erro…

É uma ideia interessante… mas, porque diabos continuar suportando todos os modos de operação legados? Em modo protegido as instruções continuam funcionando como antes, somente com restrições sobre o seletor, como mostrei acima, e estendendo o tamanho dos segmentos… Dessa forma, o modo real é completamente supérfluo, mas os PCs continuam a usá-lo e os processadores continuam entrando nesse modo, por default, durante o power up… Para que isso funcione a Intel teve que fazer mais uma gambiarra. Dê uma olhada abaixo:

; No modo real:
B8 00 00          MOV AX,0
66 B8 00 00 00 00 MOV EAX,0

; No modo protegido:
66 B8 00 00       MOV AX,0
B8 00 00 00 00    MOV EAX,0

Reparou que o prefixo 0x66 tem significados diferentes, de acordo com o modo de operação? No modo real ele diz ao processador que o registrador é EAX, ao invés de AX, para o micro-código 0xB8 (MOV AX,imm). Já no modo protegido é o contrário… Isso torna os códigos em assembly incompatíveis para os dois modos principais do mesmo processador! E isso, meus amigos, é o que eu chamo de gambiarra!

Para mim, os processadores modernos deveriam entrar no modo protegido, ajustando apenas 2 segmentos no ring 0: código e dados. Toda a BIOS poderia ser em modo protegido e não precisaríamos fazer a transição para esse modo… Se precisássemos executar código legado em 16 bits, existe o modo Virtual 8086!!! Assim, apenas 2 modos seriam necessários: O modo protegido de 32 bits, com as extensões de 64 bits, e o Virtual 8086.

Dispositivos:

A necessidade de manter hardware compatível com padrões é comendável, mas o PC leva isso ao extremo… Os antigos controladores de temporização (PIT), interrupção (PIC) e DMA (DMAC) continuam acessíveis, mesmo que de forma emulada… De fato, pode-se dizer que o barramento ISA (que surgiu no PC padrão) continua existindo até os dias de hoje… Isso só faz sentido por causa do modo real..

Mesmo assim, o PIT legado continua tendo uma base de tempo muito inferior (e com um valor maluco) do que o clock do sistema (1.19187 MHz, para ser exato!). O PIC continua suportando apenas 14 requisições de interrupção e o DMAC continua podendo realizar transferências de blocos com, no máximo, 64 KiB de tamanho… Quanto ao DMAC, embora o circuito integrado aceite transferências de memória para memória, isso não é implementado no PC!

O DMAC é um exemplo da busca eterna por compatibilidade reversa levada ao extremo. Mesmo que hoje tenhamos PCHs (Platform Controller Hubs) que fazem o trabalho de refresh das DRAMs, de forma transparente, o canal 0 (zero) do DMAC ainda é reservado para esse motivo…

Claro que existem versões mais modernas do DMAC, implementadas nos PCHs, mas elas são acessíveis apenas no modo protegido porque o acesso a esses recursos é feito em I/O mapeada no topo da memória, dentro dos primeiros 4 GiB. Lembre-se que o modo real só acessa 1 MiB + 64 KiB.

Cada um faz como quer

Ok… mesmo com essas tranqueiras, existem padrões, certo?

Acontece que fabricantes diferentes costumam fazer as coisas de formas diferentes… Um exemplo é o modo de habilitar o sinal Gate A20: Alguns exigem o uso do bit A20M da porta de controle A (PS/2 em diante), outros exigem que o controlador de teclado (heim!? o que o teclado tem a ver com memória?! gambiarra!!!) habilite esse sinal. Outros, nem isso… alguns escondem como A20M possa ser habilitado e exigem que seja feito pela BIOS! Outras estranhezas: Alguns fabricantes criam um buraco de 15 MiB acima do primeiro MiB (IBM Thinkpad e alguns Compaq, por exemplo). A maioria não faz isso…

Existem diversos pequenos quirks de fabricante para fabricante e para manter o sistema operacional funcionando em todos é necessário uma série de verificações… O código, obviamente, tende a ficar maior que o necessário!

MyToyOS: Acesso direto à memória

Continuando a série sobre controladores, além das requisições de interrupções alguns dispositivos podem pedir para o processador que este libere os seus barramentos de endereço e dados para que o próprio dispositivo lide com blocos de dados contidos na memória… É o caso de HDs, por exemplo, quando pedimos para que alguns setores sejam lidos o circuito do HD pode colocar esses dados diretamente na memória, sem a interferência do processador…

Da mesma forma que ocorre com as interrupções, o processador tem apenas um sinal de pedido de liberação do barramento (DRQ, de DMA Request, ou HREQ, de Hold [Bus] Request). No entanto, podemos ter n dispositivos que podem pedir que o processador entregue o controle. Como fazer para lidar com todos eles? Novamente entra a figura de um controlador, o DMAC (Direct Memory Access Controller).

Vou esboçar aqui o Intel 8237A (datasheet pode ser baixado aqui), que é o controlador de DMA legado da arquitetura dos PCs. Esse chip tem sérias limitações porque acompanha os PCs desde sua primeira concepção, na época em que usávamos o processador 8086, de 16 bits (a mesma coisa acontece com o PIC, descrito nos artigos anterior)… Por exemplo: Esse circuito integrado só permite transferências de blocos de dados de, no máximo, 64 KiB e o endereço base também está limitado em 16 bits. Isso significa que, se usarmos o DMAC legado (que ainda está presente de forma emulada) nos sistemas atuais, o buffer onde os dados serão transferidos só podem ser localizados na memória baixa.

Em outro artigo descreverei o novo DMAC, que permite transferências com tamanhos de 32 bits… Este “novo” DMAC está presente em chipsets especializados e depende da arquitetura, por isso o DMAC tradicional, diferente do que acontece com o PIC e o APIC, ainda é o mais usado…

Como o DMA funciona?

Desconsiderando o DMAC, um dispositivo coloca, no sinal HREQ, um sinal de nível 1 pedindo ao processador que este libere o barramento (coloque os barramentos de dados, endereço e controle, em estado de alta impedância). O processador, quando resolver atender o pedido, coloca nível 0 no sinal HACK# (Hold Acknowledge) e abre os circuitos dos barramentos… Neste ponto o dispositivo tem total controle do acesso à memória. Quando o sinal HREQ for zerado, o processador assume, de volta, o controle do barramento.

E como o DMAC ajuda?

O 8237A possui 4 entradas de requisição de DMA, nomeadas de DRQ0 até DRQ3. Da mesma forma como ocorre com o PIC, esses DMA são priorizados (se dois ocorrerem, um deles será atendido antes do outro). Em essência, o DMAC pedirá ou enviará dados de ou para o dispositivo, bem como de ou para a memória e, quando acabar, informa o fim do processo (sinal EOP# ou End Of Process) e, por sua vez, libera os barramentos de volta para o processador.

O DMAC também substitui, do ponto de vista do dispositivo, os sinais HREQ e HACK#, do processador, pelos sinais DRQn e DACKn#, onde n corresponde ao canal de DMA usado pelo dispositivo. É fácil perceber que o 8237A funciona, então, como um “agente”, do ponto de vista dos dispositivos.

De acordo com a especificação, a transferências da memória e para a própria memória também é possível. Mas, ao que parece, isso não foi implementado nos PCs… Não dá para pedir pro DMAC copiar, por demanda de software, um bloco de memória de um lugar para o outro. Em teoria isso seria uma boa ideia para aliviar alguma pressão em loops de cópias de dados, por parte do processador. Na prática, o 8237A é bem lento, permitindo transferências com uma taxa máxima de 2,5 MiB/s (existem versões com taxas de 5 MiB/s, mas, hoje em dia, isso não é lá muito rápido!).

Outro detalhe interessante são os modos de operação do DMAC… Alguns dispositivos são bem lentos e, por isso, aceitam apenas transferências simples, uma palavra (byte?) por vez… Outros, são rápidos, e permitem a transferência de um bloco de dados inteiro, mas ainda existem outros que precisam de algumas requisições para completar a transferência (transferem por demanda). Esses diferentes modos de operação o 8237A aceita e o PC está preparado para elas.

PCs adicionam um detalhe ao endereço base de transferência:

Note que, até aqui, o endereço base de transferência tem apenas 16 bits de tamanho. Isso limitaria o uso do DMAC a um único segmento da memória. Não é assim que funciona nos PCs… O padrão ISA adiciona o conceito de “página de DMA”, estendendo o endereço físico em 8 bits… Assim, o endereço base tem 24 bits de tamanho.

Isso não significa que podemos transferir, via DMA, blocos de 16 MiB! Os blocos continuam limitados a 64 KiB, e a página é fixa, mesmo quando há um overflow (ou underflow) no endereço. Por exemplo, se a página for 0xB8 (como é o caso com os antigos circuitos de vídeo VGA, no modo texto), se o DMAC transferir um byte do endereço físico 0xB8FFFF, o próximo endereço não será 0xB90000, mas 0xB80000. A página não muda.

O que é preciso para programar o DMAC?

O DMAC tem 12 tipos diferentes de registradores. Neles podemos ajustar o endereço base da transferência, a quantidade de bytes a serem copiados e o modo como esses dados serão transferidos (em bloco? um byte por vez?). Existem, ainda, registradores de status e máscara de requisições (do mesmo jeito que ocorre no PIC, exceto que apenas 3 bits são usados – os dois bits inferiores selecionam o canal e o bit 2 ajusta a máscara).

Para programar um canal do DMAC precisamos informar o endereço base (veja abaixo), a quantidade de bytes a serem transferidos, o modo de transferência e desmascarar o canal… O dispositivo requisitando a transferência vai indicar a transferência via sinal DRQn (uma vez que o DMAC responda com o DACKn).

É costumeiro que o dispositivo, depois de terminar a transferência envie uma interrupção ao processador para que o tratador saiba que existem dados colocados no buffer, pelo DMAC… É o caso de transferências feitas por HDs, sem o uso do modo PIO, por exemplo (por isso as IRQs 14 e 15 são alocadas para as duas controladoras possíveis de HD!)… É claro, as IRQs podem ocorrer por outro motivo e, neste caso, o tratador poderá ler o status do respectivo canal do DMAC para determinar o término da transferência…

As portas de I/O:

Existem dois DMACs no seu PC. As portas de 0x00 até 0x0F são usadas para o DMAC1, já as portas 0xC0 até 0xCF para o DMAC2… O primeiro DMAC lida com os canais de 0 até 3, o segundo, com os canais de 4 até 5, onde o canal 4 não é usável (o DMAC2 é escravo do DMAC1 via canal 4). Eis uma listagem para o DMAC1:

Porta Tamanho Registrador
0x00 word Start Address (Channel 0)
0x01 word Count (Channel 0)
0x02 word Start Address (Channel 1)
0x03 word Count (Channel 1)
0x04 word Start Address (Channel 2)
0x05 word Count (Channel 2)
0x06 word Start Address (Channel 3)
0x07 word Count (Channel 3)
0x08 byte Status(R)/Command(W)
0x09 byte Request
0x0a byte Single Channel Mask
0x0b byte Mode
0x0c byte Flip-Flop Reset
0x0d byte Intermediate(R)/Master Reset(W)
0x0e byte Mask Reset
0x0f byte Multi Channel Mask

Um cuidado ao lidar com o 8237A é que os registradores de 16 bits devem ser acessados 8 bits de cada vez, enviando (ou lendo) o LSB, primeiro e depois o MSB. Mas é importante que antes escrevamos qualquer valor no registrador Flip-flop reset. Isso deve ser feito porque o 8237A não muda o estado do flip-flop interno e, se não o fizermos “manualmente”, a próxima escrita num registrador de 16 bits ficará escrevendo apenas o MSB. Ao escrever em Flip-flop reset este flip-flop interno é resetado.

A porta Master Reset coloca o DMAC num estado inicial, como se tivéssemos feito um Power on reset. Não é interessante mexer nele. A porta Mask reset zera as máscaras de requisição de todos os canais do DMAC. Isso quer dizer que todos os canais estarão “desmascarados”…

As portas Single Channel Mask e Multi Channel Mask ligam ou desligam a máscara de requisições. A primeira o faz com apenas um canal, a última com todos os quatro, ao mesmo tempo. A porta Single Channel Mask recebe, nos dois primeiros bits (bits 0 e 1), o número do canal (de 0 a 3), tanto para o DMAC1, quanto para o DMAC2. e o bit 2 indica se a requisição para esse canal deve ser mascarada ou não. No caso de Multi Channel Mask, os bits de 0 a 3 são as máscaras de cada canal correspondnte.

Os registradores Request e Command são inúteis… O registrador Status devolve, nos 4 primeiros bits o estado da contagem… Para cada byte transferido a contagem decrementa. Se ela chega a zero, o bit correspondente ao canal estará setado, indicando um “término de contagem”. Já os quatro bits superiores indicam se existe alguma requisição de DMA pendente para o canal correspondente (bit 4 para o canal 0 até o bit 7, para o canal 3)… Ao lermos esse registrador, os bits TCn (terminal count) que estiverem setados serão automaticamente zerados.

As portas com as páginas de DMA, para o DMAC1, são as listadas abaixo e todas têm apenas 1 byte de tamanho. Note que a perfeita sequência que existe, acima, não existe aqui:

Porta Registrador
0x87 Page (Channel 0)
0x82 Page (Channel 1)
0x81 Page (Channel 2)
0x82 Page (Channel 3)

No caso do DMAC2 os endereços de I/O desses registradores assumem os valores de 0x8f (não usável), 0x8b, 0x89 e 0x8a (o mesmo que acima, mas com o bit 3 setado).

Resta-nos entender o registrador de modo… Para isso, é prudente que você consulte a documentação do 8237A. No contexto desse artigo, basta que eu diga que, geralmente, o modo usado por dispositivos são demand ou block. A não ser que o dispositivo seja bem velho, como antigos floppy drives, talvez o modo single seja útil… Ainda, nos PCs, o modo de autoinicialização não é usado por dispositivo algum e, geralmente, o endereço de transferência cresce (ao inves de ser decrementado)… No registrador de modo temos que dizer a direção que o DMAC vai trafegar os dados (do dispositivo para memória, da memória para o dispositivo ou da memória para a própria memória). As transferências Memória⇒memória geralmente não são suportadas e devem ser evitadas… Assim como no registrador Single Channel Mask, os 2 bits inferiores indicam para qual canal o modo se aplica.

ATENÇÃO: Novamente o leitor e amigo atento, Axey, vem em meu auxílio e indica que há uma diferença essencial nos datasheets da AMD (do link que forneci) e o da Intel (link aqui). No datasheet da Intel o “Terminal Count” é sinalizado quado o contador corrente vai de zero a 0xffff, ou seja, quando ha um underflow. Para o datasheet da Intel isso parece estranho, porque ao atingir zero nenhuma transferência adicional deveria ser feita, bem como decremento do contador… Considere a transferência de um bloco de 1 único byte: O DMAC faz algo assim:

...
while (current_count > 0)
{
  transfer_data(current_address++);
  current_count--;
}

No entanto, se esse for o caso, como poderíamos transferir 65536 bytes, ou exatamente 64 KiB? Segundo o datasheet da AMD seria impossível, já que o contador base tem 16 bits de tamnho. O contador máximo seria 65535… No caso da Intel, o contador base contém o valor da contagem requerida mais um byte. O que faz todo sentido… Para transferir 1 único byte teríamos que colocar 0 neste contador!

De fato, isso é descrito em ambos os datasheets, mas no da AMD eles esquecem de dizer que o terminal count é sinalizado no underflow. Afinal, não tem muito sentido programar o DMAC para transferir 0 bytes, tem?

Valeu, de novo, Axey!