Checker
                                   -=-=-=-=-

          Hardware  met Software on the road to Changtse.  Software  said:
      "You  are the Yin and I am the  Yang. If we travel  together we will
      become  famous  and earn  vast  sums of money."  And so the pair set
      forth together, thinking to conquer the world.
          Presently, they met Firmware, who was dressed in tattered  rags,
      and hobbled along propped on a thorny stick.  Firmware said to them:
      "The  Tao  lies  beyond  Yin  and  Yang. It is silent  and  still as
      a pool of water. It does  not  seek  fame,  therefore  nobody  knows
      its presence. It does not seeks  fortune, for it is complete  within
      itself. It exists beyond space and time."
          Software and Hardware, ashamed, returned to their homes.
                  -- Geoffrey James, "The Tao of Programming"

          Checker je rozhodně  nejdůkladnějším  řešením, které jsem viděl.
      Jeho cílem je najít  prostě  všechno.  Vytváří si svoji mapu paměti,
      kde si o každém  byte  pamatuje,  zda je  přistupný,  inicializovaný
      apod.  Díky  tomu je schopný  odchytit  přístupy za hranicemi  bloku
      s  přesností  na  jeden  byte a dokonce  i čtení  neinicializovaných
      dat.  Toto  všechno  provádí  navíc  jak v haldě,  tak na  zásobníku
      i v inicializovaných  datech. Odchytí  například i takové věci, jako
      používání neinicializované proměnné.

          Toho všeho je docíleno  pomocí nemalého  patche do gcc. Naštěstí
      ale tento  patch je integrován  jak v gcc  2.8.1, tak v egcs a proto
      nemusíte  patchovat  překladač.  Vzniklý kód potom kontroluje  téměř
      všechny  přístupy do paměti a proto je hodně pomalý (autoři  uvádějí
      běh  asi  10x  pomalejší). To znamená,  že často  potřebujete  hodně
      trpělivosti  na to,  aby se  program  vůbec  spustil. U XaoSe  to je
      řádově  několik  minut. Je ale  pravda, že XaoS  na začátku  provádí
      poměrně agresivní alokace a proto je spomalení znatelné i u efence.

          Dalším  problémem je nutnost  uzavřenosti kódu. Kontrolovaný kód
      nelze  kombinovat  z  nekontrolovaným  kódem v knihovnách.  Naštěstí
      ale v neovějších  verzích  checkeru  není nutné  knihovny  specielne
      překládat,  protože  existují  tzv.  stubs.  Ty  zařizují  interface
      mezi  knihovní  funkcí  a  kontrolovaným  kódem.  Označí  byte  tak,
      jak je funkce použije a zavolají  původní  funkci. Takové stuby jsou
      napsány pro obdivuhodné  množství funkcí (veškeré  knihovní  funkce,
      curses a další  knihovny). U XaoSe  jsem  se  potýkal  z  problémem,
      že nejsou stuby pro Xlib. Musel jsem to nakonec vyřešit tak, že jsem
      zkompiloval aalib pro checker a použil curses.

          Zajímavý  je  také  garbage   collector.  To  je  velmi  šikovný
      mechanizmus na hledání  zapomenutých bloků. Checker  projde veškerou
      paměť a zjistí, na které  bloky má program  ještě  přístupné  odkazy
      a  vypíše  nepřístupné  bloky.  Ty  jsou  téměř  určitě  zapomenuté.
      Jediná možnost by snad byla, že by program ukazatel nějakým způsobem
      schoval - třeba uložil na disk. To se ale často neděje.

          Díky své robusnosti checker suktečně odhalil většinu chyb:

Chyby pro použití haldy
  zapomenuté naalokované bloky paměti       garbage collector najde oba bloky
  uvolnění nenaalokovaného bloku            (fbm) free called before malloc.
  vícenásobné uvolnění  bloku               (ffb) free an already free block.
  alokace a realokace bloku o velikosti 0   alloc vrátí 0, realloc funguje
  použití paměti bez testu na selhání malloc
Chyby pro použití ukazatelů
  použití uvolněného bloku pro zápis        (wfb) write/modify a free block.
  použití uvolněného bloku pro čtení        (rfb) read in a free block.
  zápis za koncem pole v zásobníku (buffer owerflow)
  zápis za koncem alokovaného bloku    (bvh) block bounds violation in the heap.
  čtení za koncem alokovaného bloku    (bvh) block bounds violation in the heap.
  zápis daleko za koncem alokovaného bloku
  zápis před koncem alokovaného bloku  (bvh) block bounds violation in the heap.
  čtení před koncem alokovaného bloku  (bvh) block bounds violation in the heap.
  čtení neinicalizované paměti      (ruh) read uninitialized byte(s) in a block.

          Poměrně mě překvapilo,  že checker  neobjevil  buffer  owerflow.
      Sice objeví neinicializované  čtení, ale neumisťuje "red zones" mezi
      pole na zásobníku (pouze při volání  funkcí). Je to ale v TODO a tak
      se toho snad brzo dočkáme  (podobně jako zón mezi statickými  poli).
      Také u zápisu  daleko  za koncem  se  podařilo  přestřelit z jednoho
      alokovaného  bloku do druhého.  Jinak  ale  checker  udělal  skvělou
      práci. Podobně jako u lclintu, možnosti checkeru nekončí objevováním
      chyb z mých  testů a  najde  i  mnoho  dalších  (špatné  zarovnávání
      apod.). Na požádání objeví například i tu chybu z alokací  velikosti
      0.

          Použití je už také poměrně  snadné. Díky integraci patche do gcc
      a stubům nyní stačí stáhnout asi 500KB  balík,  zkompilovat a ladit.
      Toto  řešení je ale bohužel  téměř  nepřenositelné a proto  existuje
      verze  pouze  pro  Linux na Intelu.  Samotný  checker je ale  napsán
      přenositelně a proto by asi nebyl problém napsat  podporu i pro jine
      operační systémy a architektury.

          Zdrojové kódy najdete na ftp.prep.ai.mit.edu/pub/gnu


            výheň