evilphk++

I FreeBSD kan man blive tildelt den tvivlsomme ærestitel "evil${USER}" når man har udvist kodeevner der objektivt set ikke burde være behov for i et civilizeret samfund.

Jeg fik mit første evilbit for mange år siden for at bruge vnode name-cachen til at optimere getcwd(3) via et opslag med sysctl(2).

"You really don't want to know" som vi plejer at sige.

Indtil nu har jeg ikke lavet noget i Varnish der kom i nærheden af et evilbit, der er ikke helt samme potientiale for den slags i et "almindeligt" server program.

Men nu er der ingen vej udenom: jeg er begyndt at lave real-time tekstbehandling med gzip filer uden at dekomprimere dem mens det står på.

Varnish understøtter "Edge Side Includes", hvilket groft sagt er '#include' for HTML sider.

Samtidig vil folk naturligvis gerne gzip'e deres web-trafik for at spare båndbredde.

Den naturlige måde at gøre det på er:

backend (gzip) ––-> gunzip –> textbehandling –> gzip ––-> client

Men det betyder at man skal køre en gzip for hver request fra hver client, det er der jo ikke skyggen af performance i.

Hvis man kigger nærmere på en GZIP fil (RFC1952) vil man opdage at en GZIP fil består af:

{HEADER} {DEFLATE-BLOCK} * {CRC}{LENGTH}

Komplikationerne er at den sidste deflate-blok har første bit sat, som "nu er vi færdige" markering og som default er deflate-blokkene ikke byte-aligned, men under komprimeringen kan man indsætte alignment points og man kan droppe context.

Deflate algoritmen virker ved at pege bagud i den ukrypterede fil og sige "gentag 4 bytes 125 bytes bagud". Når man dropper context er der ikke mere noget "bagud" og derfor kan man trygt starte dekomprimeringen fra dette sted, der vil ikke være referencer til noget forudgående.

Forestil jer nu et hoveddokument der indeholder:

Det var en mørk og...
esi:include src="sparky.html"
Jeg troede det var suppe da jeg pakkede.

Varnish modtager det gzip'et og er naturligvis nødt til at gunzip'e for at finde ud af hvad der står i det, men i stedet for at gemme den modtagne kopi, gemmer varnish et til formålet specialbygget gzip'et version:

{HDR}
deflate{"Det var en mørk og...", bytealign}
deflate{"esi:include src="underside.html"", bytealign, reset}
deflate{"Jeg troede det var suppe da jeg pakkede.", bytealign}
deflate{"", slut}
{CRC}
{LEN}

Hvis varnish har brug for at levere objektet uden at lave ESI expansion (typisk når man har varnish i flere lag) kan objektet bare sparkes afsted, det er en helt legal GZIP fil.

Når der skal laves ESI expansion, nøjes vi med at tage de stumper vi skal bruge, dvs, headeren og de to deflate sektioner med teksten, samt CRC + længde felterne.

Imellem de to sektioner med teksten, indsætter vi så den inkluderede fil som også er i gzip format:

{HDR}
deflate{"Charles voksede..."}
deflate{"...i 2000.", slut}
{CRC}
{LEN}

Vi skal ikke bruge dens header, vi skal nulstille "slut" bit'en og align'e til en byte efter den sidste deflate block. Derefter kombinerer vi dens CRC med den vi foreløbig er nået frem til (noget evilmath med modulus operationer) og accumulerer længden.

Efter den sidste deflate sektion sender vi en tom deflate block med "last" bit og vores nyudregnede CRC + længde felter:

{HDR}
deflate{"Det var en mørk og...", bytealign}
deflate{"Charles voksede..."}
deflate{"...i 2000.", slut}
deflate{"Jeg troede det var suppe da jeg pakkede.", bytealign}
deflate{"", slut}
{CRC}
{LEN}

Jeg har lige committed testcase e00023 som rent faktisk gennemfører ovenstående stunt for et specielt godartet tilfælde af alignments.

Implementeringen er temmelig interessant, for der kommer en masse specialtilfælde til. F.eks kan det inkluderede objekt selv være et ESI behandlet objekt, det kan være ukomprimeret og vi kan have en klient der ikke kan modtage gzip'ede data, foruden altså.

Og koden skal naturligvis gerne være effektiv.

Med til kodenopgaven hørte at lokke ud af zlib hvor den første deflate blok starter, hvor "last" bit'en er og hvor mange ubrugte bits der er efter den sidste deflate blok. Det er min hidtil laveste kodeproduktivitet: 9 linier koder på 9 timer.

Men nu er der hul igennem, så skal alle "XXX" stederne bare fyldes ud.

evilphk

Kommentarer (11)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#2 Jesper Louis Andersen

Og koden skal naturligvis gerne være effektiv.

Det bliver nok ikke svært at slå en gunzip-edit-gzip cocktail med et pænt stykke med ovenstående. Heller ikke hvis man tager højde for alle specialtilfældende. Det er bestemt heller ikke en dårlig ide.

Men hvorfor synes du at den godtgør en evilbit? Jeg din vnode-cache hacking er da langt værre efter min mening :)

  • 0
  • 0
#3 Lasse Reinholt

Med til kodenopgaven hørte at lokke ud af zlib hvor den første deflate blok starter, hvor "last" bit'en er og hvor mange ubrugte bits der er efter den sidste deflate blok. Det er min hidtil laveste kodeproduktivitet: 9 linier koder på 9 timer.

zlib er det værste mareridt, jeg nogen sinde har rørt.

Set fra en applikationsudvikler virker dokumentationen nogen lunde ved første øjekast.

Men prøver man at emulere zlib, så opdager man, at dokumentationen er overordentlig mangelfuld og modsiger hvad Mark Adler poster af addendums som igen modsiger kildekoden.

Så går det op for en, at alverdens software, som anvender zlib, kun virker på grund af lige dele formodninger, antagelser og held :)

Man kan se mit forsøg på et zlib plug-in replacement på http://quicklz.com/wrap/

  • 0
  • 0
#4 Poul-Henning Kamp Blogger

Lasse: Hvis du har det dårligt med zlib, så må du endelig ikke kigge på openssl.

Jesper: Evilbit'en kvalificeres af hvorledes folk ser ud i ansigtet når du forklarer dem hvad du har gang i.

Poul-Henning

  • 0
  • 0
#5 Jesper Louis Andersen

Hvis du har det dårligt med zlib, så må du endelig ikke kigge på openssl.

OpenSSL er [i]uhyggeligt[/i]. Der er lange historier på internettet om hvor slemt og hvor sygt i hovedet det er. Og på trods af det, så er sikker cryptokode der ikke åbner en sidechannel på størrelse med en ladeport nærmest umuligt at skrive. Så det der med at gå igang selv er ikke en god ide med mindre man sætter sig ind i hvad man gør.

Se f.eks. Go's compare for byte equality

http://golang.org/src/pkg/crypto/subtle/constant_time.go?s=895:934#L17

.. og alt andet i crypto/subtle modulet :)

  • 0
  • 0
#8 Peter Makholm Blogger

Jeg sidder med et andet projekt hvor jeg overvejer lidt at gøre noget tilsvarende. Mit problem er dog ikke så meget dynamsik content, men at jeg skal supportere ranges, så klienten kun forespørger dele af filen.

Er det noget jeg med fordel kunne finde inspiration til i Varnish? (Eller er det endda noget som Varnish allerede gør for mig?)

Jeg har egentligt overvejet at det "bare" er at lave en ZLIB FULL FLUSH med jævne mellemrum og så "bare" håndtere de to yderblokke i en range specielt. Nogen der har en ide om hvor overkommeligt det er?

  • 0
  • 0
#10 Peter Makholm Blogger

Det kan være begge dele. Hvis man bruger gzip som content encoding er det range(gzip) og hvis man bruger gzip som transfer encoding er det gzip(range).

RFC 2616 afsnit 14.35.1:

Byte range specifications in HTTP apply to the sequence of bytes in the entity-body (not necessarily the same as the message-body).

RFC 2616 afsnit 4.3:

The message-body (if any) of an HTTP message is used to carry the entity-body associated with the request or response. The message-body differs from the entity-body only when a transfer-coding has been applied, as indicated by the Transfer-Encoding header field (section 14.41).

   message-body = entity-body    
                | <entity-body encoded as per Transfer-Encoding>  

Specifikt tillades det er at applicationer undervejs i request/response-kæden ændrer transfer-encoding efter behov. Jeg tror at Content-Encoding er mere tænkt end-to-end, dog uden lige at falder over det.

  • 0
  • 0
#11 Poul-Henning Kamp Blogger

range(content::gzip) er der naturligvis ingen ben i.

transfer::gzip(range) er noget mere tricky, men hvis du virkelig har brug for det kunne det godt lade sig gøre at lave det ved at holde styr på alle gzip blokke (offset, length, gunzip-length, crc32) og så sende et helt antal af dem der overstiger det Range der bliver bedt om.

Poul-Henning

  • 0
  • 0
Log ind eller Opret konto for at kommentere