Basic personligt

Daniel Brahneborgs blogg

Nightly builds

Ett problem med vår testsvit är att den tar ganska många timmar att köra igenom. Att köra den annat än över natten är därför otänkbart. Det är inte alltid jag kommer ihåg att dra igång den innan jag går hem, eller så har jag ändrat i mer än en version under dagen, vilket gör att bara den ena versionen blir testad. För att inte riskera att någon version hamnar på efterkälken har jag därför sedan en tid tillbaka ett script som körs varje natt. Den hämtar ut senaste koden för en viss version, bygger och installerar den, och kör sedan testsviten. Olika versioner körs på olika dagar, och eftersom vi stödjer fyra olika arkitekturer testar varje maskin varsin version enligt ett rullande schema.

Nu skulle jag lägga till en ny version, och blev snabbt lite yr. Jag började med att skapa en liten matris, där jag fyllde i vilka versioner som testades vilka dagar, och på vilken maskin. Då blev det väldigt enkelt att flytta runt versionerna mellan dagarna för respektive maskin, så att de blev jämnt fördelade.

Nyare versioner kan testas lite hårdare och med fler grupper av tester än äldre, vilket styrdes med kommandoradsparametrar till scriptet. Med fler och fler parametrar började crontab-listorna se allmänt gräsliga ut, fulla med redundans. Nej, jag behöver inte säga till att Valgrind ska användas, eftersom man alltid kan göra det från och med en viss version (fast bara i Linux). Så, det kunde den få lista ut själv. En efter en försvann parametrarna, så till slut återstod bara versionsnumret.

Men, det går ju att vara ännu lite smartare.

I början av scriptet genereras namnet på en “OK”-label, unik för varje maskin. Om testerna går igenom utan några fel så sätts den labeln på den kod som hämtades ut. Innan man testar någonting, kan då scriptet kolla om labeln kanske redan är satt på det som hämtats ut. I så fall är ju den koden redan testad, och så behöver man inte göra något mer där. Med Perforce görs det genom att kolla om “p4 labelsync -n -l $labelname …” skriver ut “label in sync”.

Istället för att då bara testa en enskild version, kan scriptet gå igenom samtliga versioner en efter en. Den börjar med den äldsta, och så länge som det senast incheckade i den grenen redan är testat, går den vidare till nästa. Ändrar jag någonting i en av de äldre versionerna blir de testade med en gång på alla maskiner, och håller jag mig till den senaste versionen så testas även då allting direkt. I värsta fall tar det några dagar innan den är ikapp, men det gör ingenting.

Det är en skön känsla att veta att om jag gör något fel i koden någonstans, råkar använda en funktion som inte finns på alla plattformar eller något annat dumt, så kommer jag få ett mail om det morgonen efter. Gör jag rätt, möts jag istället av fyra mail med “All OK”. Checkar jag inte in någonting, finns inte heller något nytt att testa, vilket gör att jag slipper få massa ointressanta mail när jag är på semester.

En förutsättning för att allt det här ska fungera är så klart att testsviten är pålitlig. Om den rapporterar att någonting är fel, då ska det också verkligen vara fel, och inte bara att något script väntade någon sekund för lite.

March 31st, 2014 Posted by Daniel Brahneborg | blogg | no comments

Trådsäkert data

Det finns några olika sätt att skydda data i ett multitrådat program. Den senaste buggen jag fixade visade på det viktiga i att välja rätt. Att bara slänga ett lås runt allting funkar nämligen inte, och det beror inte enbart på att lås är tämligen dyra saker.

Data som initieras vid uppstart och sedan bara blir läst, kräver naturligtvis inga lås alls. Det är bara att läsa och vara glad. Full fart.

Data som man bara ändrar på ibland, är förhållandevis besvärligt. Visserligen kan man slänga ett normalt lås på det, men då kan man förlora väldigt mycket prestanda. I de fall då datat är stabilt, hade ju alla trådar kunna springa igenom det samtidigt utan problem, medan de med ett lås måste ställa sig i kö och vänta. Om det är mycket data som ska gås igenom, och/eller data som många trådar vill titta på, blir det inte så bra, eftersom mycket tid kommer gå åt helt i onödan till att göra precis ingenting. Ett bättre sätt att hantera det är att använda ett read-write-lås. De som vill arbeta med datat säger till om de vill läsa eller skriva, och så länge alla bara vill läsa, så släpps de in. Så fort någon vill skriva, väntar man tills alla läsare är klara, och kan därefter uppdatera i lugn och ro. Först när write-låset är släppt, släpper man in nya trådar igen. Visserligen har Posix egna read-write-lås (pthread_rwlock_t), men det är en kul övning att implementera dem på egen hand med hjälp av vanliga mutexar och listor. Det kräver minst dubbelt så många lås-anrop som en vanlig mutex (ett före och ett efter), så det funkar inte som defaultlösning.

Det absolut enklaste scenariet är data som man både läser och skriver ofta, och inte ägnar så mycket tid åt varje gång. Då är det bara att lägga en mutex runt det hela.

Det fjärde fallet är knepigast, och rör data som helt och hållet kan tas bort. Sådant här data skapas, uppdateras, tittas på, och tas så småningom bort. Veckans exempel var en socket. Det besvärliga med dem är att man både kan läsa från och skriva till dem. Att skriva går fort, men när man vill läsa kanske man måste vänta några sekunder innan det kommer någonting. Att låsa hela socketen funkar därför inte, eftersom de som vill skriva till den då skulle behöva vänta helt i onödan. Att inte ha något lås alls funkar inte heller, eftersom det tillåter att tråd 2 stänger socketen medan tråd 1 läser från den. Sannolikheten att detta ska inträffa var i vårt program väldigt låg, vilket gjorde buggen nästan omöjlig att reproducera, och därmed knepig att hitta och fixa.

Istället får man använda en klassiker när det gäller resurshantering, nämligen referensräkning. Varje resurs (=socket) får då en siffra med antalet grejer (varken “trådar” eller “funktioner” är riktigt rätt i sammanhanget) som vill använda det. I början räknas siffran upp, och när de är klara räknas den ner. Räknaren börjar på 1. När socketen ska stängas, lämnar man tillbaka den en extra gång. Räknaren går då ner till 0, varvid socketen stängs. Om någon annan använder socketen samtidigt, är räknaren istället 2. Den som vill stänga socketen räknar bara ner den till 1. Först när den där andra grejen är klar och även den räknar ner räknaren, hamnar den på 0, och socketen stängs. Ingen kod riskerar därmed att data rycks bort under fötterna på dem medan de jobbar.

March 27th, 2014 Posted by Daniel Brahneborg | blogg | no comments

Bitfippel

En av referenserna till sidan om de Brujin handlade om bitfippel. Här är några av mina favoriter därifrån.

Sådan här kod ska naturligtvis alltid läggas bakom ett funktionsanrop, för läsbarhetens skull. Markerade med inline, så klart.

  • sign(v) => [ 0, 1 ]:
    -(v < 0);
  • sign(v) => [ -1, 0, 1 ]:
    (v > 0) - (v < 0);
  • bits_set(v) => c:
    for (c = 0; v; c++) { v &= v - 1; }
  • bits_set(v) => c, utan loop:
    v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
    c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
  • revert_bits(v):
    b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;
  • revert_bits(b): // use last two steps for ABCD => DCBA
    // swap odd and even bits
    v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
    // swap consecutive pairs
    v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
    // swap nibbles
    v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
    // swap bytes
    v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
    // swap 2-byte long pairs
    v = ( v >> 16             ) | ( v               << 16);

Jag älskar sådana här grejer dels för deras listighet, och dels för att de återigen visar det nära släktskapet mellan matematik och programmering. Släktskap och släktskap förresten, som jag ser det så är det på nivån “enäggstvillingar”.

March 18th, 2014 Posted by Daniel Brahneborg | blogg | no comments

Brute force dörrkod – löst!

Jag skrev tidigare om problemet att brute force-knäcka en dörrkod, för de fall där låset automatiskt godkänner de fyra sista siffrorna. Utan att veta vad man ska söka på, och utan att ha några matematiker i den nära bekantskapskretsen, kom jag inte så långt. Men så dök det upp en tweet från @standupmaths:

ABCDABCADBCABDCABACDBACBDACBADCBA is the shortest “superpermutation” containing all permutations of ABCD. The solution for ABCDE is unknown.

Aha! Frasen “superpermutation” går ju att söka på. Jag hittade så ett blogginlägg av Nathaniel Johnston, som förklarade det hela i mer detalj. Jag frågade om pinkoder i kommentarsfältet, och redan senare samma dag kom svaret. Problemet är mycket riktigt känt sedan länge, och kallas för en “de Brujin sekvens“.

Istället för 40000 knapptryckningar, krävs det tydligen bara 10003.

Jag har en känsla av att man kan ha någon mer konkret nytta av det här också, fast jag vet ännu inte exakt vad. Det känns bra att äntligen ha fått ett namn på det hela, i alla fall.

March 17th, 2014 Posted by Daniel Brahneborg | blogg | no comments

En besvärlig bugg

Sedan ganska länge har vi en testsvit som för ett antal scenarier drar igång programmet, skickar in ett meddelande eller två, låter det hela snurra runt på lite olika sätt, och sedan jämför det som kommer ut med vad som förväntas. Några scenarier har vi hittat på själva, andra är tagna från kunders felrapporter. På det sättet kan vi vara säkra på att den grundläggande funktionaliteten inte går sönder, och att kundernas buggar inte återkommer. Senaste tiden har denna svit körts varje natt på våra olika plattformar, så att man direkt på morgonen ser om någonting måste åtgärdas.

Emellanåt är det något enstaka test som går sönder, men på ett sätt som nästan är omöjligt att reproducera. Kan inte felet framkallas på något annat sätt än att det händer av sig själv en gång i månaden är det nästan omöjligt att fixa. Jag gör en anteckning om vilket testfall det är, och går vidare med något annat. Häromdagen var det ett av testerna som hade gått sönder, och eftersom det var ett av de som gått sönder flera gånger förut, bestämde jag mig för att kolla närmare på det. Det var dessutom en minnesläcka, och för ett program som är tänkt att snurra i månader eller år i sträck, är sådant oacceptabelt. Inte mycket minne, och inte ofta, men ändå.

En av loggfilerna såg lite konstig ut. Programmet kopplade upp, loggade in, fick ok tillbaka, skickade ett meddelande, fick ok på det också, men när ett annat meddelande sedan var på väg åt andra hållet, skickades plötsligt ett logout-paket mitt i alltihop. Dafuq? Varför väntade den inte på svar? Jo, för att de där filerna med vad som förväntades, helt enkelt inte fanns. Efter att ha lagt till dem, gick testet igenom varje gång. Men, det löste ju faktiskt inte det riktiga problemet. Att A skickar ett meddelande till B samtidigt som B av någon anledning vill logga ut är helt normalt, och ska absolut inte ge några problem. Buggen inträffade bara när dessa två saker inträffade relativt samtidigt, vilket var skälet till att den var så svår att återskapa.

Analysverktyget, Valgrind, visste var det läckta minnet hade allokerats någonstans, så frågan var varför det inte lämnades tillbaka. Jag började med att logga adressen som allokerades, och fyllde sedan på med mer loggning på de olika ställen i programmet där det datat användes. Varje loggning gav nya ledtrådar till vad som hade hänt, och vilka andra delar som också borde logga lite mer. För varje nytt test krävdes runt ett dussin körningar innan felet uppstod igen, så det tog sin lilla tid att komma framåt.

Till slut fick jag bilden klar för mig. För alla paket som skickas (t.ex. inloggningar och meddelanden) sparas en del av informationen, så när svaret från andra sidan kommer tillbaka så vet man vilken operation det gäller. När uppkopplingen stängs ned, går man igenom den här listan för att lämna tillbaka minne och vad mer som nu behövs göras. Just för logoutoperationer fanns dock lite specialkod som kördes först. På grund av anledning så plockades i vissa fall fel data bort här, vilket skapade minnesläckan. Samtidigt fanns ju fortfarande den där generella funktionen kvar som tog hand om allt på rätt sätt, så rättningen blev att helt enkelt ta bort ett par rader kod som, precis som man vill göra med FRA och SLV, ersattes med ingenting alls.

I utvecklingsgrenen av programmet är en helt annan bugg fixad, som hittades med hjälp av allmän code review och refaktorering. Det var inte ens en bugg, utan mer en “vi gör så här istället, det är snäppet mer korrekt”. På grund av denna fix är sannolikheten praktiskt taget noll att minnesläckan ovan skulle dyka upp igen, vare sig i någon testsvit eller ute hos kund. Vilket, i och för sig, hade gjort den i det närmaste omöjlig att både detektera och hitta.

Lärdomar av detta?

  1. Specialkod suger. Generell kod ftw.
  2. Att testa att korrekta scenarier blir rätt, är enkelt. Att komma på (och testa) oväntade kombinationer är mycket svårare.
  3. Code review och återkommande refaktoreringar och städningar är Bra (TM).
  4. Ibland har man tur.

March 12th, 2014 Posted by Daniel Brahneborg | blogg | no comments

|