TARDIS!

Time and Relative Dimensions In Space“! Yep! Tornei-me um “Whovian”! Mas, não vou falar da série britânica aqui, e sim dos CACHES e dois conceitos fundamentais: Localidade Temporal e Localidade Espacial.

Você pode achar estranho que o “Continuum” (espaço-tempo), conceito aplicável à Física e às séries de Ficção Científica, seja aplicável também à programação. Seu processador também usa conceito semelhante no que se refere aos CACHES. Lembre-se que CACHE é uma memória intermediária entre aquela endereçável nos seus pentes de memória (e na ROM) e a acessada, internamente, pelo processador, através de uma instrução. No meio do caminho temos algumas memórias RAM, rápidas, que são divididas em “linhas”, onde cada linha tem, hoje em dia, 64 bytes de tamanho.

Isso significa que o processador carregará, da memória principal, 64 bytes para dentro do CACHE e passará a lidar com esses 64 bytes, ao invés de, toda vez que quiser ler/escrever dados na memória, torrar ciclos de clock “esperando” que o circuito de sua RAM (por exemplo) esteja pronto para receber/enviar dados… Acontece que cada um dos CACHES disponíveis no interior do processador (e os disponíveis fora dele, como o cache L3, hoje em dia) tem capacidade limitada… Estamos interessados no cache L1 (sempre!), quando falamos de performance e este tem, no máximo 64 KiB de tamanho…

Sendo o cache L1 é o mais curto dos caches, tendo apenas 1024 linhas, precisamos nos certificar que todas as linhas disponíveis estejam sendo usadas pelo maior tempo possível. Isso significa que, se todas as linhas estiverem sendo usadas, para acessar memória que não consta do cache, uma linha terá que ser escrita na memória física, externa, e outro bloco de 64 bytes terá que ser lido e colocado no lugar. Isso também significa que os seus dados têm localidade temporal, ou seja, as linhas dos caches podem não estar presente nele por muito tempo.

O macete para obter alta performance é manter as linhas mais acessadas no cache o maior tempo possível, evitando poluí-lo com trocas ou “despejos” de linhas desnecessários… Nem sempre isso é possível, já que o kernel também usa o cache e não temos nenhum controle sobre o que o kernel faz, do ponto de vista de nossos códigos no userspace.

Existe também o conceito de localidade espacial. Se uma linha tem 64 bytes de tamanho, então, se mantivermos os dados mais acessíveis o mais próximos possível, poderíamos garantir que eles estejam na mesma linha, ou “no mesmo espaço”. Isso também vale para as instruções sendo executadas pelo processador… Se mantivermos um loop dentro de uma única linha, não corremos o risco de outra linha ser usada para conter as instruções do loop e ser “despejada”, precisar ser recarregada em cada iteração do loop, desperdiçando ciclos de clock! Por esse motivo, quanto menos instruções usarmos, melhor. A mesma coisa vale para o tamanho das instruções…

O mesmo raciocínio pode ser feito com dados. Se uma estrutura tiver 64 bytes ou menos de tamanho, podemos garantir que ela esteja dentro de uma única linha de cache desde que não ultrapasse a fronteira de uma linha. Como podemos fazer isso? Já que toda linha tem 64 bytes de tamanho, o endereço linear que marca o início de uma linha sempre terá os 6 bits inferiores zerados e a linha terminará com o endereço contendo os 6 bits inferiores setados… Note que um dado em um endereço linear não necessariamente está localizado no cache. Ele só estará lá quando for acessado (mostro outro jeito mais adiante).

Eis um exemplo de um array de 64 bytes alinhado com o início de uma linha de cache:

  section .data

  global array
  align 64  ; Alinha com o início de uma
            ; linha de cache.
array:
  times 64 db 0

Aqui, é garantido que o array inteiro, de 64 bytes, estará alocado em uma única linha do cache L1 quando for acessado. No entanto, isso não é lá muito prático… Em primeiro lugar, se ficarmos alinhando tudo quanto é estruturas no início de uma linha termos muitos “buracos” em nosso segmento de dados. De fato, poderemos até mesmo ter mais “buracos” do que dados efetivos. Garantiremos que uma estrutura estrutura individual qualquer esteja toda no menor número de linhas possível, mas nosso segmento de dados poderá ficar enorme!

Em segundo lugar, o principio da localidade espacial nos indica que devemos agrupar a maior quantidade de dados possível dentro de uma única linha… Ou seja, evitarmos que seus dados cruzem a fronteira de uma linha e passem a pertencer a duas linhas… Estatisticamente, se alinharmos nossos dados de 16 em 16 bytes (\frac{1}{4} de linha), podemos conseguir esse efeito com a maioria dos dados. No entanto, pode ser prudente o alinhamento de 8 ou 4 bytes, de acordo com o tipo de dado. No exemplo anterior, o array tem 64 bytes, então faz todo sentido alinhá-lo com o início de uma linha do cache se seu acesso for crítico para performance…

Mas, e quanto ao princípio de localidade temporal? Bem… para não poluir o cache, evitando “despejos”, podemos, às vezes, usar instruções especiais que lêem/escrevem direto na memória. MOVNTA, por exemplo, é uma instrução SSE que faz o MOV “Não temporal”, ou seja, não passa pelo cache… Às vezes é útil, mas não é prudente abusar… Acessar memória diretamente implica em esperar pela leitura/escrita e isso pode ser lento! Na prática queremos usar MOVNTA apenas para evitar despejos desnecessários de pequenos blocos de dados.

Para retardar a temporalidade de uma linha, podemos fazer um prefetch, ou seja, pedir ao processador que carregue uma linha antecipadamente, com os seus 64 bytes, se eles já não estiverem no cache. Para isso existe a instrução PREFETCH, que toma um endereço como argumento. Qualquer endereço no interior da linha fará com que a linha inteira seja carregada para o cache… Mas, note… Existem 3 caches diferentes no seu processador: O L1, L2 e L3… Existem 3 instruções PREFETCH também: PREFETCHT0, PREFETCHT1, PREFETCHT2 que, em teoria, pede para o processador transfira uma linha de um cache para outro ou da memória para um dos caches… Existe também PREFETCHW, que faz a mesma coisa que o PREFETCHT0, mas prepara a linha para a escrita (apenas as linhas que foram “modificadas” são reescritas num cache de nível superior ou na memória do sistema – PREFETCHW, suponho, marca a linha como “suja”, forçando a escrita quando ela for “despejada”).

As instruções de prefetching são uma “dica” para o processador. Usar essas instruções não garante que as linhas do cache sejam preenchidas. Mas, pelo menos, informa a intenção e pode melhorar a performance um bocado… Quando você precisar forçar um prefetching, recomendo o uso de PREFETCHT0, que tentará carregar todos os caches com a linha correspondente…

Essas instruções são úteis se você tem uma grande quantidade de dados e quer organizar quais porções deverão estar presentes no cache. Por exemplo, suponha que você tenha duas matrizes 4×4, onde cada item seja do tipo float. Temos 16 floats e, portanto 64 bytes que, é claro, cabe exatamente numa linha!… Você pode querer colocar cada uma das matrizes no cache L1d antes de começar a manipulá-los… Suponha que queira multiplicar uma matriz por outra e obter uma terceira… Suponha também que as três matrizes estejam alinhadas com o início de uma linha de cache (endereço com os 6 bits inferiores zerados)… Antes de multiplicá-las você poderia fazer:

; Estou assumindo que mat1, mat2 e
; mat_result estejam alinhados com o início 
; de uma linha.
  ...
  ; faz o prefetching...
  prefetcht0 [mat1]
  prefetcht0 [mat2]
  prefetcht0 [mat_result]

  ; chama a função matrix_mult.
  lea rdi,[mat_result]
  lea rsi,[mat1]
  lea rdx,[mat2]
  call matrix_mult
  ...

Com os 3 primeiros prefetches você dá a dica ao processador de que precisa dos 3 blocos de dados nos caches. Especialmente no cache L1! Claro, se matrix_mult “consumir muita memória”, esses prefetches serão “perdidos” (temporalidade!), mas aqui estamos usando apenas 192 bytes, ou 3 linhas do cache L1, que tem 1024…

Aí está! Espaço e Tempo são importantes quando lidamos com caches.

Quem tem medo de otimizações?

Já me disseram que eu não deveria usar as opções -O3 ou -Ofast em meus projetos. Bem… elas tendem a oferecer as melhores otimizações possíveis e, na tabela abaixo, mostro a diferença entre elas e a compilação sem opções de otimização (que chamei de “generic”) e a opção de “nenhuma” otimização (-O0). A opção -Os, em teoria, gera código pequeno (‘s’ de smaller), mas essencialmente, ele é a mesma coisa que -O2, exceto pela possível otimização de chamadas à strlen (que, na minha experiência, quase nunca o compilador consegue otimizar):

generic -Os -O0 -O1 -O2 -O3 -Ofast
-faggressive-loop-optimizations
-fasynchronous-unwind-tables
-fauto-inc-dec
-fchkp-check-incomplete-type
-fchkp-check-read
-fchkp-check-write
-fchkp-instrument-calls
-fchkp-narrow-bounds
-fchkp-optimize
-fchkp-store-bounds
-fchkp-use-static-bounds
-fchkp-use-static-const-bounds
-fchkp-use-wrappers
-fcommon
-fearly-inlining
-ffunction-cse
-fgcse-lm
-fira-hoist-pressure
-fira-share-save-slots
-fira-share-spill-slots
-fivopts
-fkeep-static-consts
-fleading-underscore
-flifetime-dse
-flto-odr-type-merging
-fpeephole
-fprefetch-loop-arrays
-freg-struct-return
-fsched-critical-path-heuristic
-fsched-dep-count-heuristic
-fsched-group-heuristic
-fsched-interblock
-fsched-last-insn-heuristic
-fsched-rank-heuristic
-fsched-spec
-fsched-spec-insn-heuristic
-fsched-stalled-insns-dep
-fschedule-fusion
-fsemantic-interposition
-fshow-column
-fsplit-ivs-in-unroller
-fstack-protector-strong
-fstdarg-opt
-fstrict-volatile-bitfields
-fsync-libcalls
-ftree-loop-if-convert
-ftree-loop-im
-ftree-loop-ivcanon
-ftree-loop-optimize
-ftree-parallelize-loops
-ftree-phiprop
-ftree-reassoc
-ftree-scev-cprop
-funit-at-a-time
-funwind-tables
-malign-stringops
-mavx256-split-unaligned-load
-mavx256-split-unaligned-store
-mfancy-math-387
-mfp-ret-in-387
-mfxsr
-mglibc
-mno-sse4
-mpush-args
-mred-zone
-msse
-msse2
-mtls-direct-seg-refs
-mvzeroupper
-fsigned-zeroes
-fdelete-null-pointer-checks
-fident
-finline-atomics
-ftrapping-math
-fbranch-count-reg
-fcombine-stack-adjustments
-fcompare_elim
-fcprop-registers
-fdefer-pop
-fforward-propagate
-fguess-branch-probability
-fhoist-adjacent-loads
-fif-conversion
-fif-conversion2
-finline
-finline-functions-called-once
-fipa-profile
-fipa-pure-const
-fipa-reference
-fmerge-constants
-fmove-loop-invariants
-fomit-frame-pointer
-fshrink-wrap
-fsplit-wide-types
-fssa-phiopt
-ftoplevel-reorder
-ftree-bit-ccp
-ftree-ccp
-ftree-ch
-ftree-coalesce-vars
-ftree-copy-prop
-ftree-copyrename
-ftree-cselim
-ftree-dce
-ftree-dominator-opts
-ftree-dse
-ftree-forwprop
-ftree-fre
-ftree-pta
-ftree-sink
-ftree-slsr
-ftree-sra
-ftree-ter
-falign-labels
-fcaller-saves
-fcrossjumping
-fcse-follow-jumps
-fdevirtualize
-fdevirtualize-speculatively
-fexpensive-optimizations
-fgcse
-findirect-inlining
-finline-small-functions
-fipa-cp
-fipa-cp-alignment
-fipa-icf
-fipa-icf-functions
-fipa-icf-variables
-fipa-ra
-fipa-sra
-fisolate-erroneous-paths-dereference
-flra-remat
-foptimize-sibling-calls
-fpartial-inlining
-fpeephole2
-free
-freorder-blocks
-freorder-blocks-and-partition
-freorder-functions
-frerun-cse-after-loop
-fschedule-insns2
-fstrict-aliasing
-fstrict-overflow
-fthread-jumps
-ftree-builtin-call-dce
-ftree-switch-conversion
-ftree-tail-merge
-ftree-vrp
-foptimize-strlen
-ftree-pre
-finline-functions
-fgcse-after-reload
-fipa-cp-clone
-fpredictive-commoning
-ftree-loop-distribute-patterns
-ftree-loop-vectorize
-ftree-partial-pre
-ftree-slp-vectorize
-funswitch-loops
-fassociative-math
-fcx-limited-range
-ffinite-math-only
-freciprocal-math
-funsafe-math-optimizations

Note que somente com as opções -O3 e -Ofast podemos ter o recurso de vetorização de um loop que, é claro, poderia ser “ligada” usando a chave -ftree-loop-vectorize, mas, de qualquer maneira, Essas duas opções oferencem muitas vantagens, tanto do ponto de vista da performance e do tamanho do código gerado pelo compilador.

Se você usa apenas a opção -O2, note que algumas coisas não são oferecidas, como o recurso de organizar funções de pouco uso como inline, algumas otimizações inter process também são são realizadas e além da vetorização, algumas eliminações de sub expressões globais e da previsão de loops (para auxiliar no branching predition) podem ficar seriamente comprometidas.

Tá certo que a opção -Ofast só é realmente útil em dois pontos: Quando não precisamos da conformidade estrita com IEEE 754 e quanto otimizações ainda mais agressivas (porém “unsafe”) sejam interessantes. Eu evitaria o -Ofast a não ser que você saiba o que faz. Mas adotaria -O3 como padrão.

UPDATE: Eu já tinha observado isso antes mas fiz questão de fazer alguns testes… Ao que parece, -O2 realmente gera código mais rápido que -O3 ou -Ofast!

As estruturas dos tipos de ponto flutuante definidas para o padrão IEEE 754:2008

A linguagem C, via padrão ISO 9899:1999 ou superior, define 4 tipos de “ponto flutuante”: float, double, long double e __float128. Eis a estrutura de cada uma delas:

Tipo Bits significativos Bits do expoente “Bias” do expoente
float 24 8 2^7-1=127
double 53 11 2^{10}-1=1023
long double 64 15 2^{14}-1=16383
__float128 113 15 2^{14}-1=16383

Todos eles funcionam da mesma forma, exceto pelo tipo long double: Existe um bit 1, inteiro, implícito nos bits significativos e, por isso, no tipo float a soma dos bits dá 32, considerando o bit de sinal teríamos 33 bits, mas com o bit implícito, voltamos para o limite de 32 bits ou um DWORD.

Com o tipo double o tamanho é de 64 bits. E com o tipo __float128 se passa o mesmo, mas para 128 bits. O tipo long double foge a regra porque o bit “implícito” é “explícito”, ele faz parte da representação, daí os 79 bits mais o bit de sinal nos dá exatamente 80 bits (10 bytes).

Como de praxe, expoentes que tem “bias” máximo negativo (ou seja, seu valor binário é zero!) expressam o valor 0.0 se a parte fracionária dos bits significativos também forem zero (e, no caso do long double, se o bit inteiro também for zero!) ou, caso contrário, um valor subnormal… Se o “bias” for máximo (todos os bits setados), indica um NaN ou um dos infinitos, dependendo do sinal.

Quanto ao “bias”, vale lembrar que, num float, E=e-127, onde e é o valor inteiro sem sinal expresso no expoente… No caso do double, E=e-1023, no caso do long double e do __float128, E=e-16383… Quando e=0 o valor subnormal é multiplicado pela escala 2^{E+1}.

IEEE 754:2008 define, ainda, o tipo binary256, mas esse não é implementado na especificação do C, pelo menos até a versão mais recente.

O império contra-ataca…

Péssima piadinha no título. Sorry. Mas eu explico adiante.

O título é para referenciar um antigo artigo neste blog – “Witty” – Um webserver em C++ – onde se propunha:

…. Mas, já pensou se pudéssemos desenvolver nossas aplicações web em C++?

Pois é. Era Jan/2012 e acho que não sabíamos que o “Império”, a.k.a Google, já estava planejando “um contra-ataque” ao Javascript, iniciando em Out/2011, o desenvolvimento da linguagem: Dart. Não o “Vader”, é claro, mas aparentemente com muitos poderes.

Piada explicada – sem graça, é lógico – apresento uma solução à questão supracitada, proposta pelo Fred.

Descobri, esta linguagem hoje, quando buscava sistemas de padrões para caracteres ASCII, no site do ECMA . O ECMA, para quem não conhece é uma associação européia para elaborar e gerir padrões estilo ISO/ANSI.

O último documento de standart, é a especificação da linguagem. O que me deixou curioso foi o nome e em seguida o site da linguagem. Quando busquei no Google, encontrei um “pad” onde podemos rodar o código e ver o resultado ao lado em formato de consoles ou de saída HTML. Tem o PI-Montecarlo , o Solar, o Spirodraw, e outros.

Se Fred ficou impressionado com o Wintty, eu desta vez tive a mesma epifania com este site, por alguns motivos:

  • Gosto de usar scripts.
  • Ultimamente estou fazendo alguma coisa com o AWK (i.e. GAWK), por que se parece com “C”, é de um dos autores do C,  e é bom usar C (E no Gawk, dá até para usar o gdb, sério!)
  • Gosto de Python, mas sempre acho muito “verboso” e tenho sempre a sensação que “alguns chips estão desalinhados”, apesar do enorme poder do Python.
  • Gosto de resultados rápidos e facilidade de provas de conceito: nada mais imediato do que colocar o código e o resultado numa tela e apresentar.
  • Entre outras coisas, possui um SDK, possibilidade de compilar para Javascript, é mais performático (ver: c|net sobre Dart).
  • E por fim – como programo em C, raramente me sinto confortável, por muito tempo, em outro ambiente, sempre tô voltando.

Fica a dica:

150px-dart-logo

 

Tecnologia CMOS

Vimos como funciona o MOSFET no artigo anterior… O capacitor formado entre o substrato e  a placa metálica, separados por um fino filme de óxido isolante “expulsa” os portadores de carga majoritários do substrato formando um “canal” ou um “campo” entre os cristais da fonte e do dreno, diminuindo a resistência elétrica entre esses terminais.

Como existem dois tipos de transístores MOSFET: O de canal N e o de canal P, onde a carga do Gate, em relação ao substrato, é complementar, nada mais justo que usar esses dois tipos para construir circuitos lógicos.

Para efeitos de comparação, eis o circuito lógico da mesma porta inversora que mostrei quando expliquei a tecnologia TTL:

Inverter CMOS

Simples assim…

Se A for GND, o gate do MOSFET canal N estará descarregado, oferecendo grande resistência elétrica entre S e D, mas o gate do MOSFET canal P estará carregado de forma tal a formar um canal P (V_G < V_B), fazendo com que ele conduza, ligando V_{DD} à saída Y. E, veja que o caso contrário também ocorre…

Não tem diodos, resistores e o circuito é extremamente simples.

Assim como nos TTLs, temos que obedecer faixas onde o sinal A será interpretado como sendo de nível baixo e alto. Mas, diferente dos TTLs, como não há correntes de polarização ou, pelo menos, só no tempo ínfimo de carga dos “capacitores”, não temos resistores grandes que adicionariam divisores de tensão ao circuito. As faixas são simétricas! O nível baixo é, praticamente, a faixa de 0 V até \frac{1}{3} de V_{DD}. O nível alto, de \frac{2}{3} até V_{DD}.

Note que aqui os níveis de tensão de alimentação são V_{DD} e V_{SS}. O “D” vem de “drain” e o “S” de “source”, em referência aos pinos dos MOSFETS. E, o importante é que a diferença de pontencial entre eles, não o valor “absoluto”… No TTL, tanto os CIs quanto todo o resto do circuito externo, tem que ser alimentados entre +5 V e 0 V (terra ou “ground”)… Nos CMOS, desde que a diferença V_{DD}-V_{SS} esteja dentro do limite, pode-se usar qualquer valor.

Existem, é claro, limites para as correntes de saída do circuito. Dependendo do circuito integrado elas podem ser um pouco mais altas do que as portas equivalentes TTL… E, por falar em TTL, existem CIs da família 74 que são são implementações em CMOS! Esses CIs tem nomenclatura “HC” depois do 74, como o 74HC04, que suporta correntes de saída (tanto no nível baixo quanto alto) de, no máximo, cerca de 25 mA… Compare com a limitação de 16 mA e 400 μA da série 74 “normal”…

A antiga desvantagem dos CMOS:

Na época em que circuitos integrados lógicos eram, basicamente, divididos entre as famílias 74 (TTL) e 40 (CMOS), os CMOS tinam a desvantagem de serem mais lentos. Isso porque o capacitor formado entre o Gate e Body é relativamente maior do que a capacitância oferecida pelos BJTs. Com capacitâncias maiores, aumenta-se a constante de tempo de carga/descarga dos capacitores e introduz-se um atraso considerável na resposta dos circuitos lógicos.

Esse não é mais um problema… A tecnologia MOS permite miniaturização quase a nível molecular, enquanto BJTs não oferecem tal feature.

A outra vantagem da tecnologia MOS é que os circuitos podem ser construídos em camadas. Note que um MOSFET canal N é construído “cavando” o espaço onde ficarão os cristais N da fonte e dreno. Esses outros cristais são colocados no lugar por algum processo químico… depois, coloca-se uma máscara isolante de óxido de silício e, por fim, outra máscara de metal… voilà, temos um circuito lógico.

Nos TTLs, hoje em dia, algo desse jeito também é feito, mas a configuração é mais difícil e tornou-se mais custosa.

Ahhh… sim, tem ainda outra vantagem. Circuitos lógicos da família 40 costumam suportar uma faixa bem variada de tensões de alimentação do CI. de +3 até +15 V. É outro contrate com a lógica TTL, que só permite, em sua forma padrão, +5 V.

PCs são a pior arquitetura possível…

… especialmente para desenvolvimento de sistemas operacionais. Essa afirmação pode ser surpreendente para o usuário comum, mas é a mais pura realidade! Considere que existem “trocentos” fabricantes diferentes de hardware, usando componentes específicos para seus próprios hardwares e, muitas vezes, com pequenos tweaks na ROM-BIOS: Dell, HP, LeNovo, IBM, Intel, Asus, Gigabyte, Biostar, Micro-Star, AOpen, Abit… Sem contar com fabricantes de dispositivos como HDs: IBM, Seagate, Western Digital, Maxtor (se é que algum desses ainda existe por ai); Placas de vídeo: ATI, nVidia, Asus, EVGA, Creative Labs, …; Placas e chipsets de Audio: Creative Labs, Yamaha, Intel, …; Não vou nem falar de chips controladores aqui para não cansar o leitor…

Existem padrões, é claro, mas eles costumam ser “corrompidos” de tempos em tempos. Por exemplo: A espeficação do bootstrap do PC nos diz que o primeiro setor de um disco é carregado para o endereço físico (em 16 bits) 0x0000:0x7C00 e o registrador DL contém o número do drive… Em algumas BIOS o endereço é 0x07C0:0x0000 e/ou DH contém lixo… Além disso, deve-se levar em consideração, hoje, o padrão UEFI, que executa um programinha com header Mark Zbikowski (O antigo .EXE do MS-DOS), junto com um header Portable Executable (“PE”), usado pelo Win32.

Do ponto de vista de software, o hardware não ajuda muito, pois com tanta diversidade eles tendem a ser diferentes. Tomemos o exemplo da compatibilidade retroativa com os antigos PC-ATs baseados no processador 80286… O barramento de endereços desses antigos processadores tinha 20 bits de tamanho e era impossível acessar mais que 1 MiB de memória física. Com o surgimento dos 386s, em meados dos anos 80, o barramento de endereços passou a ter 32 bits de tamanho, mas a IBM achou por bem restringi-lo a 20 bits no modo real… Surge a noção do “gate A20“. Mesmo em nossas máquinas com processadores i7, capazes de endereçar até 4 PiB (4, seguido de quinze zeros, aproximadamente), no modo real você ainda não pode endereçar mais que 1 MiB… Mesmo que sistemas como MS-DOS estejam, na prática, mortos a quase 20 anos. O motivo é que esse sinal, “gate A20” mascara os bits superiores de um endereço físico… Precisamos “habilitar” os bits superiores para acessarmos toda a capacidade de memória da máquina!

De novo, embora existam maneiras padronizadas para ajustar o gate A20, elas não são homogêneas de arquitetura para arquitetura. Inicialmente o ajuste era feito através do lugar menos provável: Via controlador de teclado! Depois, separaram um bit numa porta específica (porta 0x92), no padrão ISA, para ligar/desligar o “fast gate A20“. Isso porque o chip 8042 é lento por natureza (não há motivos para que um controlador de teclado seja rápido!). Finalmente criaram serviços da BIOS que fazem a mágica por nós, que não estão disponíveis em todas as BIOS. Exemplos disso são os serviços 0x88 (Get Extended Memory Size) e 0xE801 (Get Extended Memory Size for Large Configurations) da interrupção por software 0x15 que, nas máquinas modernas, tendem a retornar com o flag CF setado (erro). Ainda, o serviço 0xE820 (Query System Address Map) não está presente em máquinas mais antigas, que usam o antigo 486 ou processador inferior.

Além do gate A20 temos outros exemplos de padrões “despadronizados”… Seu PC tem um chipset (um conjunto de circuitos integrados) que realizam tarefas específicas: Controlador de teclado, timer, disco, portas seriais, portas paralelas, etc… Muitos desses “chips” estão, hoje em dia, amalgamados num único chip chamado I/O Controller Hub (ou ICH, para os íntimos)… Mas, o ICH é proprietário da Intel, existem outros Hubs, de outros fabricantes, com características específicas. O desenvolvedor de sistemas operacionais e BIOS devem levar isso em consideração. O ICH não é o único “hub” da Intel… Temos PCHs (Peripheral Controller Hubs), GCHs (Graphical Controller Hubs) e MCHs (Memory Controller Hubs)…

Em resumo… Um PC é um ambiente bastante hostil para o desenvolvedor em baixo nível, mas, infelizmente, é o “padrão despadronizado” adotado pela indústria e pelos usuários. Para garantir que seu OS funcione numa grande quantidade de PCs é necessário criar códigos redundantes que façam, antes, testes sobre as idiossincrasias de cada arquitetura pretendida ou então, que tenha como alvo uma arquitetura específica (mas que leve em conta os diversos fabricantes).

O truque dos campos bit-mapeados

No artigo passado mostrei como um valor double pode ser recodificado para caber em 32 bits usando campos bit-mapeados em uma estrutura:

struct fp_s {
  int value:25;
  int expoent:7;
} __attribute__((packed));

O que não é muito intuitivo é o fato de que o compilador consegue lidar com o membro value como se ele fosse um int, mas que tenha apenas 25 bits de tamanho! Ou seja, se colocarmos -1 nele, o valor armazenado será 0x1ffffff e valores menores que -16777216 sofrerão underflow, como acontece com qualquer valor inteiro! Mas, como é que o compilador faz essa mágica?

Para facilitar a compreensão lidaremos com duas estruturas menores, de apenas 1 byte de tamanho cada, e uma função de leitura e outra de escrita para o membro a dessas estruturas:

struct S1 {
  char a:5;
  char b:3;
} __attribute__((packed));

struct S2 {
  unsigned char a:5;
  unsigned char b:3;
} __attribute__((packed));

char S1read(struct S1 s)
{ return s.a; }

struct S1 S1write(char c)
{ struct S1 s = { c }; return s; }

char S2read(struct S2 s)
{ return s.a; }

struct S2 S2write(char c)
{ struct S2 s = { c }; return s; }

Eis o código equivalente de cada uma das funções:

S1read:
  lea eax,[rdi*8]
  sar al,3
  ret

S1write:
  mov eax,edi
  and eax,0x1f
  ret

S2read:
  mov eax,edi
  and eax,0x1f
  ret

S2write:
  mov eax,edi
  and eax,0x1f
  ret

Deu pra perceber que apenas a função S1read() é diferente? As outras três simplesmente zeram os bits acima dos 5 primeiros (que é o que mandamos fazer!)… A primeira rotina, S1read é diferente porque ela tem que levar em conta o sinal do membro a do argumento s. Ao fazer LEA EAX,[RDI*8] o compilador está deslocando RDI 3 posições para a esquerda, ou seja, colocando o bit 5 de EDI no bit 7:

EDI original : 0b000snnnn
Depois de LEA: 0bsnnnn000
Depois de SAR: 0bssssnnnn

Onde s é o bit de sinal e n são os bits restantes do valor de 5 bits.

Depois do LEA, qualquer operação pode ser feita como se a tivesse, de fato, 8 bits de tamanho (o tamanho de um char), desde que, no fim das contas, desloquemos o valor obtido de volta em 3 bits para a direita… É exatamente isso que o compilador faz, mas usando a instrução SAR (Shift Arithmetic Right). A diferença entre as instruções SHR e SAR é que a primeira colocará zeros no bit mais a esquerda, depois do shift, enquanto a segunda copiará o bit de mais alta ordem. Isso garante que o sinal do valor seja mantido, enquanto nos livramos dos 3 bits inferiores.

Na escrita, via função S1write() não precisamos nos preocupar com isso. O compilador simplesmente colocará zero nos bits superiores porque mandamos zerar b. Se tivéssemos feito:

struct S1 S1write(char a, char b)
{ struct S1 s = { a, b }; return s; }

O compilador criaria algo assim:

S1write:
  mov eax, edi
  sal esi, 5
  and eax, 31
  or  eax, esi
  ret

No modo x86_64 os registradores RDI e RSI são usados como primeiro e segundo argumentos da função, de acordo com a convenção de chamada POSIX. O compilador isolará b, deslocando-o 5 bits para a esquerda e zerará os 3 bits superiores de a. Logo depois ele faz um OR para misturar os dois. A mesma coisa aconteceria se mudássemos S2write do mesmo jeito… E aqui o uso a instrução SAL não é diferente de usarmos SHL. Ambas colocarão zeros à direita (aliás, elas têm o mesmo μop).

Isso tudo para te dizer que o verdadeiro problema está apenas na transformação da menor quantidade de bits para a maior e quando os tipos forem sinalizados. Mas a solução deslocamento-para-esquerda, operações e deslocamento-para-direita, resolve o problema facilmente… Em tipos sem sinal basta isolar os bits…

Outro ponto que pode causar estranheza é por que o compilador escolheu LEA ao invés de um simples SAL ou SHL? A resposta não é intuitiva: Dois deslocamentos consecutivos não podem ser executados em paralelo na mesma unidade de execução. O compilador escolheu uma operação aritmética, fazendo o cálculo de um endereço efetivo, seguido de um deslocamento porque essas instruções podem ser emparelhadas! Não que isso tenha alguma diferença aqui, já que ambas lidam com RAX como registrador destino.